RadixAttention

Find and reuse the shared prefix

The first handbook question has finished. Its KV cache is no longer needed to produce that answer, but the next question may begin with exactly the same handbook. Returning every slot to the allocator immediately would throw away useful computation. Keeping everything forever would eventually prevent new requests from running.

RadixAttentionRadixAttentionSGLang’s prefix-reuse mechanism, which indexes cached model state in a compressed prefix tree and manages its lifetime.See in glossary → treats those intermediate results as a reusable cache. Its defining data structure is a radix tree: a prefix tree in which an edge can represent several consecutive tokens. The original paper explains the algorithm; the implementation details below are grounded in the release-pinned radix cache source.

Draw the shared history

Use five toy token IDs, displayed as words for readability:

Request A: SYS DOC A ask cost
Request B: SYS DOC A ask date
Request C: SYS DOC B ask cost

After A, the tree can have one edge holding its entire sequence. Inserting B discovers a match through ask, then a difference at the last token. The edge splits. The common beginning belongs to both requests; each final token has its own child.

root
 └─ SYS DOC A ask
     ├─ cost
     └─ date

C matches only SYS DOC. Inserting it splits the earlier edge again:

root
 └─ SYS DOC
     ├─ A ask
     │   ├─ cost
     │   └─ date
     └─ B ask cost

The final word cost appears in two branches. Its text is identical, but its preceding history differs. The KV associated with the first occurrence cannot simply replace the KV associated with the second. Each path from the root describes the context that produced the state.

This is the benefit of representing prefixes explicitly. A path captures both the token sequence and where it diverged. Edge compression avoids storing a separate branching object for every token in a long unbranched span. It does not compress the numerical contents of the KV tensors.

Matching and extending

The runtime walks from the root while the next token spans agree. The result is a longest reusable prefix plus an uncached suffix. It can associate the matched prefix with the request and arrange storage for the missing tokens. After model execution computes new KV, the new state becomes eligible for insertion into the tree.

For A and B, there are four reusable toy tokens and one new token. For A and C, there are two reusable tokens and three new ones. Reordering C’s words to make its ending resemble A does not help the prefix match. Reuse ends at the first divergence even if later token IDs happen to coincide.

A full input hit deserves care. A KV cache stores keys and values, not necessarily the final next-token logits. The engine may still need a small amount of execution at the boundary to produce the first output. Page alignment and supported cache layouts can also limit the exact reusable length. Our toy tree counts matching token slots; it does not promise that every matched token removes every possible operation.

Try inserting A and B below. Finish A, then evict eligible leaves. The shared beginning must survive while B still depends on it. Insert C to see an earlier branching point, and D to demonstrate that a matching suffix does not imply a matching prefix.

The tree is metadata; KV is data

The tree tells the runtime which token span corresponds to which cached values. The numerical K and V arrays occupy memory managed by the engine’s pools and allocators. Walking an edge means following metadata; using a cache hit means making the model’s attention computation refer to the appropriate physical values.

This separates three questions that are sometimes mixed together:

RadixAttention names the reuse mechanism. It does not mean that every attention operation is executed by a special tree-traversing GPU kernel. Once a request has its usable KV locations, an attention backend performs the numerical computation.

The vLLM prefix-caching chapter described another way to index reusable state: chained hashes of token blocks. Both approaches must account for preceding context and physical ownership. Their metadata structures differ; exact-prefix reuse is an objective shared by both. Neither data structure alone guarantees higher end-to-end throughput on every workload.

Protect live requests; reclaim idle state

An active request may need its prefix on every decode step. Evicting those values because they were created a long time ago would break execution. The cache therefore distinguishes retained values that are reclaimable from values protected by active users. In the pinned implementation, node lock references participate in that protection, and eligible leaves are tracked for eviction. Radix cache implementation

Think of three requests sharing the handbook. If one finishes, the other two still depend on the shared nodes. Finishing the last request makes retained state eligible for reclamation; it does not necessarily erase it immediately. That interval between completion and eviction is where future requests obtain hits.

Eviction proceeds from eligible leaves so that a retained descendant is not left without its prefix. Removing a leaf can make its parent eligible. This is also why a useful common beginning can survive after one rare suffix is reclaimed. The original design used least-recently-used eviction; current implementations expose policy choices, so “the least recently used node always goes first” is not a universal statement about every configuration. SGLang eviction-policy documentation

For a concrete memory budget, suppose a completed conversation contains a 10,000-token common prefix and a 500-token unique answer. Another request needs 300 slots. Reclaiming part of the unused suffix may suffice while leaving the valuable beginning resident. The exact allocation unit changes the mechanics, but the economic question stays the same: which retained computation is least worth keeping relative to the next request’s needs?

Identity is more than visible text

Two copies of the same displayed document can produce different token sequences if their surrounding templates differ. Even matching token IDs cannot justify sharing arbitrary states across different model weights, adapters, positions, or other settings that change the computation. An engine must preserve the relevant identity and isolation rules.

Our examples assume one fixed model, tokenizer, template, and attention configuration. They are about reuse within that compatible setting. They do not imply that a service should merge unrelated tenants’ state just because a few words match. Treat namespace and isolation requirements as part of the deployment, not something the diagram resolves.

The physical state representation matters too. A dense full-attention model has a relatively direct token-to-KV story. Sliding-window or recurrent components can require additional state and different reuse boundaries. The existing recurrent-attention chapter explains why preserving the history of a hybrid model requires more than copying conventional K and V arrays.

Build prompts that expose honest reuse

For the handbook assistant, a stable system message followed by the handbook and then the individual question creates a reusable beginning. A timestamp before the handbook may destroy most of that opportunity. Moving that timestamp later can help only if doing so preserves the intended prompt semantics. Cache efficiency is not a reason to silently change what the model is asked to do.

Measure reuse in tokens, not just requests. Nine short requests with complete hits can coexist with one very long miss that accounts for most of the prompt work. A high request hit rate then tells a comforting but incomplete story. Similarly, a warm-cache benchmark with the exact same question repeated indefinitely says little about a service whose popular documents change hourly.

The tree gives the scheduler information about reusable work. It does not decide on its own whether a warm request should run ahead of an older cold request. That choice introduces queueing and fairness—the subject of the next chapter.

Sources and further reading

• Original RadixAttention design, SGLang paper §3 and Appendix A.
• Radix cache at v0.5.20: matching, splitting, locking, and eviction.
• Cache eviction policies: policy selection in the online documentation, checked September 24, 2026.