Prefix caching, radix trees and the KV hierarchy

Most prompts are not unique

The training guide's KV cache section introduced the cache as an optimisation inside one request: token t+1 needs every earlier token's key and value vectors, so we store them instead of recomputing them. The serving-scale implication is different in kind. A chat request carries a fixed system prompt, a tool schema, a policy block and a conversation history. Every one of those is text the model has already seen, and in a production fleet it has already been prefilled, usually thousands of times. Reusing that work is the single highest-leverage optimisation available to a serving system, because prefill is compute-bound: the prompt tokens are the expensive ones, and they are overwhelmingly shared.

The numbers are not subtle. On realistic Codex-style agentic traces, vLLM with the Mooncake Store moved the prefix cache hit rate from 1.7% to 92.2%, which produced 3.8× higher throughput and 46× lower P50 TTFT on the same 12 GB200 GPUs. SGLang's RadixAttention, which is what most of this part describes, reported up to 6.4× higher throughput than the prior state of the art on structured workloads where prefixes repeat. An agent that calls a tool twenty times in a loop resends the same growing transcript twenty times; without a prefix cache, nineteen of those prefill passes are pure waste. This is why agent workloads invert the prefill-to-decode ratio: they are mostly input, mostly repeated, and mostly cacheable.

From a flat block table to a tree of shared prefixes

With PagedAttention (Part 5), the KV cache is already a set of fixed-size blocks — typically 16 tokens each — addressed by a block table. That makes prefix sharing almost free to add: hash the token contents of a block together with its parent block's hash, and two requests that produced the same tokens get the same block key. On a hit the engine points the new request's block table at the existing physical block instead of allocating one, so the memory cost of a shared prefix is paid once. Full-block hashing is exactly what vLLM's automatic prefix caching does; the chain of parent hashes is what makes a block's identity depend on its whole prefix, not just its own 16 tokens.

A radix tree generalises this to variable-length shared prefixes. Each node owns a token span, children branch where prefixes diverge, and a request's prefill walks the tree as far as it can before it has to compute anything new. That walk length is the number of prefill tokens avoided. The animation below feeds a seeded agent trace — one system prompt, one tool schema, eight user turns — through a radix tree and tracks what fraction of every prompt was already present. Node radius scales with the token count on the edge; colour runs from old (blue) to just-used (magenta).

A shared cache has to forget, and it should forget leaves first

A prefix cache that never evicts is a memory leak. The naive policy — least-recently-used over all nodes — has a specific pathology in a tree: evicting an interior node orphans every subtree beneath it, including children that were used seconds ago. RadixAttention's answer is to evict leaf-first: only a node with no children is a candidate, and among candidates the least-recently-used leaf goes first. Interior (shared) nodes survive because they are what makes the cache valuable, and a leaf's parent becomes a candidate only once all its children are gone. The result is that long, heavily shared system prompts persist while one-off tails churn.

Drive the cache past its capacity below. A new request is inserted, the tree grows, and whenever the leaf count exceeds the limit the oldest leaf is dropped and its token span must be recomputed on the next hit. Watch the count of evicted tokens: that number, multiplied by the per-token prefill cost, is the price of an undersized cache.

A local cache gets you nothing if the next request lands elsewhere

Prefix caching inside one replica only helps requests that come back to that replica. Put eight replicas behind a load balancer and route each request to whichever worker is least busy, and every worker sees every prefix occasionally while none of them builds a useful cache. The cache is only as good as the router that feeds it. This is the same tension as scheduler fairness, one level up: affinity maximises hit rate, balance minimises queueing, and you cannot have both at once.

Four policies are compared below under identical traffic. Round-robin ignores the prefix entirely. Least-loaded balances queue depth but is prefix-blind. Consistent hashing sends a prefix to a fixed replica, which builds strong affinity but concentrates hot prefixes on a few workers and lets collisions evict. KV-aware routing looks at which replica already holds the longest matching prefix, falls back to load when nothing matches, and gets both. The headline is the ratio in the readout: round-robin captures roughly one-eighth of the KV-aware hit rate across eight replicas — the 1/N you would expect from assigning independently of content.

2,100 ms on a miss, 190 ms on a hit

The user-visible payoff of a cache hit is time to first token. Prefilling a roughly 2,000-token prompt from scratch on a small model costs on the order of 2,100 ms; reading the already-computed KV blocks and starting decode brings the same request's TTFT down to about 190 ms, an order-of-magnitude difference that is the difference between an agent that feels responsive and one that does not. The effect compounds in agent loops: every tool call re-sends the transcript, so a hit on turn twenty saves the entire history's prefill again.

The cost side is a pricing problem as much as an engineering one. Every major API prices cached input below fresh input — DeepSeek-V3 at 0.07 versus 0.27 USD per million tokens, Anthropic's prompt-cache reads at a tenth of the base input price, Gemini's cached input at a quarter. Move the hit-rate slider and the prompt length and watch both the blended TTFT and the input bill; the model selector pulls the actual list prices (historically dated, see the source note) so the arithmetic is the vendor's, not an assertion.

LMCache and Mooncake Store turn a cache into a storage tier

HBM is the tier that actually feeds attention, and it is the smallest and most expensive. When the prefix cache outgrows it, the obvious extension is a hierarchy: keep the hot blocks in HBM, spill the rest to host DRAM, then to local NVMe, then to a remote store shared by the whole fleet. LMCache does exactly this for vLLM, and Mooncake Store is the distributed KV store behind the Kimi/Mooncake results cited above; both make the cache a multi-tier object whose blocks can be fetched back when a request returns to them. The latency ladder is the familiar one — HBM is nanoseconds-to-microseconds away, DRAM is around a hundred microseconds, local NVMe around a millisecond, a remote fetch several milliseconds — and each tier down costs roughly an order of magnitude in access latency while buying one or two orders in capacity and a large factor in cost per byte.

The decision that matters for every request is whether to fetch the missing prefix from a lower tier or to recompute it. Recompute scales with token count — you re-run the prefill matmuls — while a fetch pays a roughly fixed access latency plus a bandwidth term that is far cheaper per token. That makes fetch beat recompute for long prefixes and lose for short ones, and the crossover for an NVMe-tier fetch sits near 1,900 tokens: below that, recomputing is genuinely faster than going to disk and back. Pick a tier and move the prefix length to find the decision point.

Caches are about time, not just space

Eviction is spatial pressure; TTL is temporal. Anthropic's prompt cache defaults to a five-minute lifetime and has to be refreshed or it silently misses, and every provider that charges for cache writes is pricing exactly this trade: hold a prefix longer and more requests hit it, but you occupy memory that a hot new request cannot use. Agent workloads stretch both axes hard. A long-running agent pauses for the model, for tools, for a human, for a network round trip; if the pause exceeds the TTL the next turn is a full cold prefill of the entire transcript, and the user pays both the latency and the uncached input price. The right TTL is a function of the inter-turn gap distribution, which is why cache-aware gateways now measure it rather than guessing. Set a TTL and a typical gap below to see the survive probability and what a miss costs in TTFT.

The numbers and mechanisms

References

• Zheng et al., "SGLang: Efficient Execution of Structured Language Model Programs" — RadixAttention and the leaf-first eviction policy.
• Kwon et al., "Efficient Memory Management for Large Language Model Serving with PagedAttention" — the block table that prefix hashing builds on.
• vLLM blog, "Serving Agentic Workloads at Scale with vLLM x Mooncake" — 3.8× throughput and 46× lower P50 TTFT.
• Qin et al., "Mooncake: A KVCache-centric Disaggregated Architecture for LLM Serving" — the distributed KV store used as the remote tier.
• LMCache project documentation, github.com/LMCache/LMCache — HBM/DRAM/NVMe tiering for vLLM.