Prefix-Aware Routing and KV Cache Reuse
Why load-balancing LLM requests round-robin throws away computed KV cache, and how routing on prompt prefix turns a fleet's caches into a shared asset.
Round-robin load balancing is correct for stateless HTTP and wrong for LLM serving, because an LLM replica is not stateless. It holds a KV cache, and if the request it receives shares a prefix with something that replica computed recently, the prefill for that prefix is already done. Send the request elsewhere and the fleet pays to recompute what it already has.
This matters because real prompts are extremely repetitive at the front. A system prompt with tool definitions, a few-shot block, a document being discussed across turns, an agent's accumulated trajectory: agent and RAG workloads routinely have thousands of shared tokens before the first differing byte.
Radix trees and automatic prefix caching
The enabling mechanism is prefix caching inside a replica. SGLang's RadixAttention keeps KV cache blocks in a radix tree keyed by token sequence, so any new request automatically reuses the longest matching cached prefix instead of requiring the user to declare a cache boundary (Zheng et al., 2023, SGLang, arXiv:2312.07104). vLLM's automatic prefix caching does the equivalent over paged KV blocks, hashing block contents so identical prefixes map to the same physical blocks.
A cache hit skips prefill for the matched span. For a 10,000-token shared prefix with a 100-token new suffix, that is close to the entire prefill cost, so TTFT can fall by an order of magnitude. This is the same mechanism exposed commercially as prompt caching.
The routing problem
Per-replica caching only pays off if requests reach the replica holding the right blocks. With \(N\) replicas and round-robin, the chance of landing on the one with a warm prefix is \(1/N\), and every replica ends up caching the same popular prefixes, wasting capacity \(N\) times over.
A prefix-aware router computes a hash chain or radix key over the prompt's leading blocks and picks a replica by a two-term objective:
Overlap alone creates a hotspot, because the most popular prefix attracts all traffic to one replica. Load alone is round-robin. NVIDIA's Dynamo KV router scores workers on exactly this pairing, weighing the prefill cost of newly computed blocks against decode cost from active blocks, and llm-d implements a comparable cache-aware scheduler on Kubernetes.
Sticky sessions are the poor-relation version: route by conversation id so a multi-turn chat returns to the same replica. It captures most of the benefit for chat and none of it for a fleet of agents sharing one system prompt.
Cache tiers
GPU HBM is the fastest and smallest place to keep KV blocks. Once evicted, the alternative to recomputation is a slower tier: CPU DRAM, local NVMe, or a cluster-wide store. LMCache and Mooncake both build this tiering, treating KV cache as a first-class storage object that outlives the request that produced it. The economics are simple: reloading a cached prefix over a fast interconnect beats recomputing it whenever transfer bandwidth exceeds effective prefill throughput, which for long prefixes it usually does.
When it breaks
- Prefix caching is not free memory. Cached blocks occupy KV space that active sequences want. An aggressive cache raises hit rate and lowers the maximum concurrent batch, and the crossover is workload-specific.
- Anything at the front that varies kills it. A timestamp, a request id, or a user's name interpolated into the system prompt moves the divergence point to token zero. Put volatile content at the end of the prompt, always.
- Hotspots. Popular prefixes concentrate load. Without the load term, a cache-aware router will happily overload one replica while others idle.
- Multi-tenant leakage risk. Sharing blocks across tenants by content hash is efficient and creates a cross-tenant timing side channel: a fast TTFT reveals that someone else recently sent the same prefix. Partition the cache namespace per tenant when that matters. See multi-tenant serving isolation.
12 flashcards for this concept
Click a card to reveal the answer.