Two teams look at the same slow LLM serving endpoint and reach for different tools. One profiles the attention kernel — tiling, fused softmax, occupancy. The other notices that every incoming request re-runs the same 900-token system prompt and asks why. The second team is about to recover work the first team can never touch, because the fastest attention kernel in the world still has to execute if you compute the prefix at all.

That is the whole argument for a radix cache in one sentence. It is not a faster way to do the prefill. It is a way to not do prefill for the parts of the prompt you have already seen. When many requests share long common prefixes — a fixed system prompt, a few-shot preamble, a retrieval preamble bolted onto every RAG query — the shared tokens produce identical key/value state every time. A radix cache stores that state, keyed by the token prefix, and hands it back instead of recomputing it. The divergence from kernel tuning is structural, not incremental, and knowing which lever you are pulling is the difference between a real speedup and a wasted sprint.

What is a radix cache, and what does it mean in practice?

A radix cache is a data structure — a radix tree (a compressed prefix trie) — that indexes cached KV-cache blocks by the token sequence that produced them. In a transformer, prefill computes the key and value tensors for every input token; those tensors are the “KV cache” the decode phase reads from. Crucially, the KV state of token n depends only on tokens 0..n under causal attention. So if two requests begin with the same 300 tokens, the KV blocks for those 300 tokens are bit-identical. There is no reason to compute them twice.

The radix tree exploits exactly that property. Each edge in the tree carries a run of tokens; each node points at the KV-cache blocks for the prefix spelled out by the path from the root. When a new request arrives, the scheduler walks the tree matching the request’s tokens against existing edges. The matched prefix is a cache hit — those blocks are already resident in GPU memory (typically HBM) and are simply attended to. Only the divergent suffix — the part unique to this request — goes through prefill.

In practice this is the mechanism behind RadixAttention as SGLang implements it, and it is the concrete thing people mean when they say a serving stack “does prefix caching.” The user-visible effect: a request that shares a long preamble skips most of its prefill and starts generating tokens almost immediately.

Why prefix reuse is an algorithmic change, not a kernel optimization

Here is the distinction that matters for anyone deciding where to spend engineering time. Kernel tuning makes a fixed amount of computation run faster: it packs more FLOPs into each SM-cycle, fuses passes so you touch HBM fewer times, and raises the fraction of peak throughput you actually achieve. FlashAttention, torch.compile graph fusion, TensorRT’s kernel autotuning — all of these operate on work you have decided to do. They shrink the constant in front of the operation count. They never change the operation count itself.

Prefix reuse changes the operation count. It removes prefill FLOPs from the workload entirely, before any kernel runs. That is why we file it as a C2 (algorithmic restructuring) intervention rather than a kernel line item: the win comes from a different data structure and a smarter scheduler, not from a tighter inner loop. This is the same boundary that separates algorithmic and kernel-level levers throughout our GPU performance work on the wider inference cost problem — and it is why the two levers compose rather than compete. You can run a radix-cache hit and have the divergent suffix processed by an optimally tuned FlashAttention kernel. Cache reuse and kernel tuning are orthogonal.

The reason the distinction is not academic: the two levers have different ceilings. Kernel tuning is bounded by how far your achieved throughput sits below peak — often a factor of two or so, once the obvious stalls are gone. Prefix reuse is bounded by how much of your workload is shared prefix. In a RAG deployment where every query carries a 1,200-token instruction-and-context preamble and asks a 40-token question, the shared fraction is enormous, and no amount of kernel work touches it. Confusing the two is how teams spend a quarter shaving 15% off prefill latency when the same prefill was 90% redundant.

Which serving workloads benefit — and which see nothing?

The value of a radix cache is a direct function of workload structure. It is worth being blunt about this, because the failure mode is deploying it where it cannot pay off and then carrying its bookkeeping cost for no return.

Workload	Prefix structure	Radix-cache payoff
RAG with a fixed instruction preamble	Long shared prefix, short unique query	High — often the dominant lever
Few-shot prompting with a fixed exemplar block	Long shared few-shot preamble	High
Multi-turn chat (same conversation)	Growing shared prefix across turns	High — each turn reuses the whole history
Batch classification with a shared system prompt	Moderate shared prefix	Moderate
High-diversity single-turn queries, no system prompt	Prefixes nearly all unique	None — pure overhead
Long unique documents summarised once each	No cross-request sharing	None

(Evidence class: observed-pattern — this reflects the workload shapes we see across GPU serving engagements, not a single benchmarked figure. The direction is robust; the magnitude depends on your prefix-length distribution.)

The rule underneath the table is simple. Prefix reuse only recovers work that is genuinely repeated across requests. If your prefixes are all distinct — say, a summarisation service where each request is a different document with no shared instruction block — the radix tree fills up with single-use entries, every lookup misses, and you have added tree-walk and memory-management overhead with nothing to show for it. In that regime, kernel-level tuning remains the correct lever, and the honest answer to “should we add prefix caching?” is no.

How much throughput and time-to-first-time-token can prefix reuse deliver?

The honest framing is that the improvement is bounded by the redundancy you remove, so quote it against your own prefix distribution rather than someone else’s headline number. The mechanism gives you two connected wins.

First, time-to-first-token (TTFT) drops for cache-hit requests because prefill is the phase that stands between arrival and the first generated token. If 90% of a request’s input tokens are a cached prefix, roughly 90% of its prefill FLOPs disappear, and TTFT falls toward the cost of prefilling only the divergent suffix. Second, those recovered FLOPs are now available for other requests, so requests-per-second at a fixed GPU count rises — you are serving more traffic on the same hardware because you stopped paying for redundant prefill.

A worked example makes the shape concrete. Assume a serving endpoint where each request is a 1,000-token prompt: a 900-token shared preamble plus a 100-token unique tail. Without caching, every request prefills 1,000 tokens. With a warm radix cache, cache-hit requests prefill only the 100-token tail — a roughly 90% reduction in prefill work for those requests. Prefill is not the whole cost of a request (decode still runs token by token), so the end-to-end latency improvement is smaller than 90% and depends on your output length. But for prefill-dominated, short-output workloads — which is exactly what RAG and classification often are — the effect on TTFT and on sustained requests-per-second is large. This is illustrative arithmetic, not a benchmark; the point is that the ceiling scales with the shared fraction, and you can estimate your own before deploying anything by measuring your prefix-length distribution the way you would when profiling where inference cost actually lives.

How the radix tree keys KV blocks by token prefix

The elegant part is that a radix tree is the natural index for this problem. Ordinary prefix caching with a flat hash keyed on the full prompt only hits when two requests are identical. A radix tree hits on the longest matching prefix, which is what you actually want: two requests that share the first 900 tokens and diverge after should share 900 tokens of cache, not zero.

Concretely, edges are labelled with token runs and the tree is kept in a compressed form so a shared preamble is one long edge rather than 900 single-token hops. Insertion of a new request splits an edge at the point of divergence: the common part stays shared, and a new branch holds the unique suffix. Lookup is a walk from the root consuming the request’s tokens until no edge matches; everything consumed is a hit. Because the KV blocks referenced by shared nodes are physically shared in GPU memory rather than copied, the memory cost of a shared prefix is paid once no matter how many requests reference it — which is where the throughput win and the memory story connect.

How does radix cache interact with GPU memory and eviction?

This is the constraint that turns a clean idea into an engineering problem. KV-cache blocks live in HBM, and HBM is finite. Under high concurrency, the radix tree wants to retain every prefix it has seen so future requests can hit — but the same HBM is needed to hold the KV state of in-flight decode requests. Those two demands compete for the same fixed capacity.

So the cache needs an eviction policy, and eviction is where the design earns or loses its keep. A least-recently-used policy over tree nodes is the common baseline: when memory pressure rises, evict the leaf prefixes nobody has touched recently, keeping the hot shared preambles resident. The subtlety is that you must never evict a prefix whose blocks are currently referenced by a running request, and you want to protect high-fan-out nodes (a system prompt shared by thousands of requests) far more aggressively than a one-off suffix. Get the policy wrong and you thrash: you evict a hot preamble under a load spike, the next request misses and re-prefills it, and you have paid both the eviction bookkeeping and the recomputation.

There is also an interaction with how prefill and decode are scheduled. Separating those phases — as SGLang’s prefill/decode disaggregation does — changes which requests are competing for cache-resident memory at any moment, and a radix cache that ignores that scheduling reality will make eviction decisions that look locally sensible and globally wrong. The cache, the scheduler, and the memory manager are one system; tuning them in isolation is how prefix caching quietly underdelivers.

FAQ

What matters most about radix cache in practice?

A radix cache stores computed KV-cache blocks in a radix tree (a compressed prefix trie) keyed by the token sequence that produced them. When a new request arrives, the scheduler matches its tokens against the tree; the longest matching prefix is a cache hit, so only the divergent suffix runs through prefill. In practice this means requests sharing a long preamble skip most of their prefill and start generating almost immediately.

Why is radix-cache prefix reuse an algorithmic change rather than a kernel-level optimization?

Kernel tuning makes a fixed amount of computation run faster — it shrinks the constant in front of the operation count. Prefix reuse removes prefill FLOPs from the workload entirely, before any kernel runs, so it changes the operation count itself. That is why it is a C2 algorithmic intervention: the win comes from a different data structure and scheduler, and it composes with kernel tuning rather than competing with it.

Which LLM serving workloads benefit most from radix caching, and which see no gain?

Workloads with long shared prefixes benefit most: RAG with a fixed instruction preamble, few-shot prompting with a shared exemplar block, and multi-turn chat where each turn reuses the conversation history. Workloads with nearly unique prefixes — high-diversity single-turn queries with no system prompt, or one-off document summarisation — see no gain and only pay the tree-walk and memory overhead. There, kernel tuning remains the right lever.

What throughput and time-to-first-token improvements can prefix reuse realistically deliver?

The improvement is bounded by the fraction of your workload that is shared prefix. For a cache-hit request whose prompt is 90% cached preamble, roughly 90% of prefill FLOPs disappear, driving time-to-first-token toward the cost of the divergent suffix alone. Recovered FLOPs raise requests-per-second at a fixed GPU count. End-to-end gains are smaller than the prefill reduction because decode still runs token by token, so estimate against your own prefix-length distribution rather than a headline figure.

When would kernel tuning still beat radix caching for a given serving workload?

When prefixes are nearly all unique, the radix tree fills with single-use entries, lookups miss, and caching adds overhead without payoff. In that regime — high-diversity single-turn traffic or unique-document workloads — the redundant-work lever does not exist, so making the necessary prefill run faster with FlashAttention, torch.compile, or TensorRT autotuning is the correct place to spend effort.

How does radix cache interact with GPU memory capacity and eviction under high request concurrency?

KV blocks live in finite HBM, and the cache competes with in-flight decode requests for the same capacity. Under load it needs an eviction policy — typically LRU over tree nodes — that protects hot high-fan-out prefixes, never evicts blocks referenced by a running request, and avoids thrashing (evicting a hot preamble under a spike only to re-prefill it). The cache, scheduler, and memory manager behave as one system, so eviction must account for how prefill and decode are scheduled.

The question worth carrying into your own deployment is not “should we add a radix cache?” but “what fraction of our prefill is redundant, and is that fraction stable under our real traffic?” Measure the prefix-length distribution first. If it is fat, prefix reuse is the largest lever you have and kernel tuning is a rounding error next to it; if it is thin, the reverse holds. A GPU Performance Audit records prefix-reuse caching as an estimated C2 intervention precisely because that measurement — not a rule of thumb — decides whether the algorithmic lever or the kernel lever earns the sprint.