This is my favourite kind of bug, in the sense that I found it genuinely instructive and would rather not meet it again. A KV-aware router was returning worse cache hit rates than it should have. Nothing was down. No error rate moved. The only symptom was that prefill work which should have been free was being done again, and the degradation had been getting slowly worse for a while before anyone put a number on it.
The cause was high availability. Specifically, the second replica.
How KV-aware routing works
A KV-aware router keeps a radix tree of which prefix blocks live on which worker, so an incoming request can be sent to the machine that already holds most of its prompt. Workers publish events as blocks are stored and evicted, and the router applies those events to its tree. When it works, a long shared system prompt is prefilled once and reused by everyone, which is the cheapest win in serving.
Run one router and this is a closed loop. Run two, for availability, and each replica maintains its own copy of that tree. They are not a cluster with a shared state machine. They are two independent observers of the same event stream, and the design's claim is that because they see the same events they will hold the same view.
The assumption that does not survive load
The event transport is publish-subscribe and fire-and-forget. It is lossy by design, and the documentation is honest about this: events drop when a subscriber cannot keep pace. That is a reasonable trade for a transport carrying cache metadata, and it is fine as long as loss is repaired.
There is repair. Events carry monotonically increasing sequence numbers, so a consumer that receives 42 and then 45 knows it missed two, and can request retransmission from a bounded replay buffer, or in Dynamo's case fall back to a full tree snapshot from a healthy peer. On paper the tree converges.
The word doing the work is bounded. The replay buffer holds a fixed number of recent batches. If the drop rate stays high for long enough that missed events age out of that window before the gap is repaired, the repair path cannot run and the divergence becomes permanent rather than transient.
Under sustained high concurrency that is exactly the regime you are in. The subscriber falls behind because there is a lot of load, and there is a lot of load precisely when cache hit rate matters most. The failure is correlated with the moment you need the thing to work.
Why it is invisible
Every property that makes this hard to catch is a consequence of the same design choice.
- Dropping an event is not an error. Fire-and-forget means the publisher never learns, and the subscriber only learns via a sequence gap it may or may not be able to repair. Nothing throws.
- A stale tree still returns an answer. A router with a wrong view does not fail, it routes to the second-best worker. The request succeeds. It just pays for a prefill that another machine had already done.
- Round-robin hides it. With requests split across two replicas, half your traffic gets good decisions and half gets degraded ones. The aggregate hit rate sags rather than falling off a cliff, which reads as workload drift rather than a bug.
- It only shows past the first turn. Single-turn traffic has little to reuse. The damage concentrates in multi-turn sessions, which is where the cache was supposed to earn its keep.
What I take from it
Reducing to a single router replica restores correct behaviour immediately, and a controlled test against one replica returns essentially full hits on a repeated prompt. That is a diagnosis, not a fix: it trades the availability the second replica was added for, and nothing prevents a single replica from falling behind the same way under enough load.
The deeper point is that this is a distributed systems problem wearing a serving problem's clothes. Two replicas holding independent mutable state, updated over a lossy channel, with a bounded repair window and no periodic reconciliation, will diverge. That is not a bug in an implementation, it is what that architecture does. The available directions are the usual ones: make the index authoritative in one place and have replicas read from it, or keep local copies but add reconciliation that runs on a timer rather than only on gap detection.
What I would want before choosing is instrumentation, because the thing that genuinely bothers me here is not that the drift happened. It is that it was happening for a while, visible only in debug logs, with no metric whose job was to say so. A per-replica hit-rate comparison would have caught it, and it costs almost nothing.
If two replicas are supposed to agree, something has to be measuring whether they do. Otherwise the first time you find out is when the bill arrives.
Sources
- KV event replay, Dynamo against vLLM: the fire-and-forget transport, sequence-number gap detection, the bounded replay buffer and the snapshot fallback.
- KV cache aware routing: what the router is trying to do and why a stale tree still returns a plausible answer.
- Router design: the replica model and the stated consistency expectations.