How does prefix-aware routing across LLM replicas raise cache hit rate?

## Why the cache does not follow the request An engine's prefix cache stores KV blocks computed for a token sequence and reuses them when a later request starts with the same tokens. Those blocks physically occupy the GPU memory of one process. There is no shared cache tier across replicas: replica B cannot use replica A's blocks, and nothing replicates them. Cache locality is therefore entirely a routing property. This matters because the workloads with the most to gain are exactly the ones with long repeated prefixes: - **A shared system prompt or tool schema.** Every request carries the same 2,000-token preamble. - **Few-shot prompting.** The examples are identical across calls. - **Multi-turn chat.** Turn *k* is turn *k−1*'s prompt plus the reply plus the new message — the longest prefix match in the corpus. - **Agent loops.** Each step re-sends the whole trace so far. For these, prefill can be the majority of the request's cost, and a hit turns a multi-second TTFT into a fraction of a second. ## The round-robin failure Spread a conversation's turns over N replicas at random and the probability that turn *k* lands where turn *k−1* did is 1/N. At eight replicas, seven out of eight continuations pay a full prefill of the entire history — and that history grows every turn, so the waste compounds. The cache is enabled, the dashboards show it exists, and it does almost nothing. This is one of the few situations where scaling out makes each individual request *slower*. ## How prefix-aware routing works The router computes a key from the front of the request and maps the key to a replica: - **Key choice.** Hash a fixed-length prefix of the tokenized prompt (block-aligned to the engine's KV block size so partial blocks do not spoil matches), or use a session/conversation id that the client already carries, or a tenant id when tenants share a system prompt. Session ids are cheap and accurate for chat; content hashing generalizes to stateless callers. - **Consistent hashing.** Map keys onto a ring (ring-hash or maglev in an Envoy-class proxy) so that adding or removing a replica moves only about 1/N of keys. Naive modulo-by-replica-count remaps nearly everything on any membership change, which throws away every cache in the fleet during a rollout — exactly when you can least afford it. - **Longest-prefix routing.** More sophisticated routers keep an approximate index of which prefixes each replica has recently served and pick the replica with the longest match, which handles branching conversations better than a single fixed-length hash. ## The tension with balance Pure affinity is a load-balancing policy chosen without reference to load, so it will hotspot. Two shapes recur. If one prefix is enormously popular — a single shared system prompt in front of every request — hashing on it sends everything to one replica. Fix that by including a discriminator (session or tenant) in the key, or by hashing a prefix long enough to differ across callers. And if one tenant is simply much busier than the others, its shard is hot by construction; that tenant may need several replicas in its own hash group. The robust design treats affinity as a preference with an escape hatch: among replicas whose queue depth and KV-cache occupancy are below a threshold, pick the best prefix match; if the affine replica is saturated or preempting, take the least-busy replica and accept the cold prefill. That single rule captures most of the cache benefit while keeping the tail latency behaviour of a load-aware balancer. ## Cache lifetime is not a guarantee Cached blocks are evicted under memory pressure and lost entirely on restart. Routing affinity raises the *probability* of a hit; it never promises one. So never make correctness depend on it — the request must carry the full prompt and be servable by any replica — and be aware that during a rolling deploy your hit rate goes to zero for a while, which shows up as a TTFT spike that is not a regression. ## Measuring it Judge the change on the engine's own prefix-cache hit-rate counters and on TTFT p95 for the affected traffic, broken down per replica. Watch the balance metrics at the same time: if hit rate rises while one replica's queue depth diverges from the rest, you have traded a latency win for a hotspot, and the threshold on the escape hatch is the knob to adjust. Expect the win to be large for long shared prefixes and negligible for short, unique prompts — routing complexity is only worth it when the prefixes are genuinely long and genuinely shared.