Explainer
The load balancer decides the hit rate
A prefix cache lives in one replica’s memory. Put eight replicas behind a load balancer that spreads requests evenly and a session’s next turn lands where its history is cached about one time in eight. llm-d measured 11%. The cache code was fine; the router was throwing it away. Below, the same sessions against the same fleet under three routers.
The hit rate page showed that whether a turn finds its prefix is decided by how many sessions share one memory. Add replicas and a second question appears: which memory. Round-robin ignores it. Sticky sessions answer it and then cannot move a session off a replica that has filled up. A cache-aware router asks each replica what it holds and routes to the longest match, unless the queues have drifted apart, and then it balances.
each bar is one replica: seconds of prefill it did over the run, the work that queues a first token
| router | hit rate | mean TTFT | p90 TTFT | busiest / mean | fleet prefill |
|---|---|---|---|---|---|
| round-robin | 6% | 1.95 s | 4.09 s | 1.07x | 903 s |
| sticky sessions | 45% | 1.29 s | 3.48 s | 2.06x | 533 s |
| cache-aware | 44% | 882 ms | 1.97 s | 1.04x | 541 s |
16 sessions per replica is more than the 10 whose full history fits in 22 GB of cache, so every router is evicting. Round-robin hits 6%, sticky 45%, cache-aware 44%. Routing cannot make a cache that does not fit; that is the working-set problem from the hit rate page, and the fix is more memory or fewer sessions.
Round-robin turns one cache into N stale slices. Every replica a session visits keeps the history up to the turn it saw, so the next turn finds a partial match at best and prefills the rest. That is why the measured number at eight pods was 11% and not zero, and why it gets worse as the fleet grows: the fraction of a session any one replica has seen is about 1/N. The fleet does N times the prefill it needed to, and the queue of that prefill is what the p90 time to first token is made of.
Sticky sessions buy locality with balance. Hash the session to a replica and every turn finds the whole history, until the replica it hashed to has more history than memory or more turns than time. Sessions are not the same size, long agent sessions cluster wherever the hash puts them, and a router that cannot move them watches one replica saturate while its neighbours idle. Ray’s description of the failure is that the hash balances sessions and perceives them uniformly. Adding a replica reshuffles the ring and cold-starts everyone.
Cache-aware routing is locality with an escape hatch. SGLang’s router keeps an approximate radix tree per worker and routes to the longest match unless the busiest worker’s load exceeds the least busy by a threshold, then routes by queue. Dynamo’s KV router scores each worker as the prefill blocks it would have to do, less the blocks it already holds, plus its decode load, and takes the cheapest. The Kubernetes inference gateway and llm-d do the same with a global index of which prefixes went where. The measured results are of a kind: SGLang reports the hit rate on a shared-prefix workload going from 20 to 75%, llm-d a p90 first token of 0.5 seconds against 31 for approximate routing and 92 for random, Baseten a 50% cut in first-token latency on 50K-token inputs across four replicas.
What this model leaves out
Moving the cache instead of the request. A global KV store, the approach of Mooncake, LMCache and Dynamo’s KVBM, lets any replica fetch a prefix from wherever it was made. At 400 Gb/s the transfer runs near 50 GB/s, so a 70B model’s 320 KB per token moves in about six microseconds a token against a hundred to recompute it. That is a different trade, memory and network for routing freedom, and vLLM with Mooncake reports 95% hit rates with plain round-robin at sixty GPUs once it is made.
Replicas here are single-request prefill queues. Real engines batch prefill chunks with decode and admit several prompts at once, which shortens the queue this page draws but does not change what fills it. Decode load is left out of the routing decision entirely, and the newer routers weigh it: llm-d’s token-aware scoring counts uncached tokens in flight, and Dynamo adds decode blocks to the cost.
The cache-aware router here has perfect knowledge of every replica’s cache. Real ones work from an approximation, a tree the router updates as it routes, or from events the engines publish, and the gap between approximate and precise is the difference llm-d measured between 31 seconds and half a second at the p90.
Read next
- explainers/
- The hit rate is the workload
One replica: how many sessions one memory can hold before they evict each other.
- Compute the system prompt once
What a prefix cache is and what a hit saves.
- Cross-Model KV Cache Transfer in LLM Families
The other way a request can leave its cache behind: by changing model.
- feed/
- KV-Cache Wins You Can See
llm-d. Random, approximate and precise routing on eight pods: 92 seconds, 31 and half a second at the p90.
- SGLang v0.4: Zero-Overhead Batch Scheduler, Cache-Aware Load Balancer
The radix-tree router and its thresholds; hit rate 20 to 75% on a shared-prefix workload.
- NVIDIA Dynamo: Router Design
The cost function: prefill blocks less cached blocks, plus decode load.
- Preble: Efficient Distributed Prompt Scheduling for LLM Serving
Srivatsa and others, 2024. Reuse when the tokens saved exceed the tokens still to compute.
- Mooncake: A KVCache-centric Disaggregated Architecture for LLM Serving
The alternative: move the cache, not the request.
- glossary/