Prefix caching and RadixAttention

Prefix caching keeps the KV cache of finished requests in GPU memory and reuses it when a new request starts with the same tokens. A system prompt, a block of few-shot examples, a retrieved document, or the earlier turns of a conversation are prefilled once and then served from memory, so the next request only computes attention states for its new suffix. Because keys and values at a position depend only on the tokens up to that position, reuse is exact: the output is identical to recomputing. RadixAttention, from the SGLang system, organises the cached sequences as a radix tree with least-recently-used eviction and a scheduler that orders requests to maximise reuse. vLLM's automatic prefix caching achieves the same with hashed paged blocks. For chat, agent and retrieval workloads with long shared context, it is often the largest single cut to time to first token and prefill compute that a serving engine offers.

The bottleneck it attacks#

Prefill is compute-bound, and its cost is linear in prompt length plus a quadratic attention term (see the roofline article). For a prompt of $n$ tokens of which the first $m$ are already cached, the remaining prefill work is

where $P$ is the parameter count and $L,n_h,d_h$ are layers, query heads and head dimension. The second term counts attention for the $n-m$ new tokens over all $n$ positions with a causal mask. Time to first token is $F(n,m)$ divided by the achieved FLOP rate plus queueing, so a cache hit of fraction $h=m/n$ removes roughly fraction $h$ of prefill time. Every saved prefill FLOP also frees the GPU for other requests' decode steps, which is where the throughput gains in the papers come from.

Production prompts are highly repetitive. Applications prepend the same instructions, tool definitions and examples to every call. A multi-turn chat resends the whole history every turn, so turn $k$ repeats turns 1 to $k-1$ verbatim. Agents call the model dozens of times with a growing shared transcript. Parallel samples, best-of-n and tree search branch from one prompt.

Where it came from#

Kwon et al. (2023) already supported sharing a prefix among sequences in vLLM through reference-counted blocks, and described shared prefixes for system prompts as a use case. Gim et al. (2023), Prompt Cache, precomputed attention states for reusable prompt modules declared in a schema, reporting time-to-first-token improvements from 8× on GPU to 60× on CPU; because modules can appear at non-prefix positions and are encoded independently, that approach changes the computation rather than reproducing it exactly. Zheng et al. (2023) introduced SGLang and RadixAttention: retain the cache of every finished request in a radix tree, match each new request's longest cached prefix automatically, evict least-recently-used leaves, and schedule requests in an order that keeps hits high. SGLang reported up to 6.4× higher throughput than prior systems on agent, reasoning, few-shot, JSON, retrieval and multi-turn chat workloads. ChunkAttention (Ye et al., 2024) and Hydragen (Juravsky et al., 2024) attacked the decode-side cost of shared prefixes, and Preble (Srivatsa et al., 2024) extended prefix-aware scheduling across many GPUs.

How RadixAttention works#

A radix tree is a trie whose edges are labelled with runs of tokens rather than single tokens. Each node owns the KV cache of the tokens on its incoming edge, so the path from the root to a node spells out a token prefix and the nodes along it hold that prefix's cache.

on request(tokens):
    node, m = tree.match_longest_prefix(tokens)       # walk edges; split an edge if the match ends inside it
    pin(path to node)                                 # reference counts: in-use nodes cannot be evicted
    prefill(tokens[m:], past = cache along path)      # only the suffix is computed
    decode until done
    tree.insert(tokens + output, kv)                  # keep the result for future requests
    unpin(path); update last-access time on the path

on memory pressure:
    while free memory < needed:
        evict the least recently used leaf with reference count 0 (its parent may become a leaf)

Matching and splitting. If a request matches only part of an edge, the edge is split at the divergence point and the shared part becomes a new internal node. Lookups cost time linear in the matched length, and SGLang measured the tree management overhead at 0.2 seconds of a 74.3-second run with no reuse at all, under 0.3%, which is why it is on by default.

Eviction. Only unreferenced leaves are evicted, so a shared system prompt stays as long as any conversation under it is still useful. The policy is LRU over leaves.

Cache-aware scheduling. When many requests wait, the order matters. Serving them first-come-first-served interleaves unrelated prefixes and thrashes a small cache. SGLang sorts waiting requests by matched prefix length (longest shared prefix first) and proves that, for a batch of requests with cache at least as large as the longest request, visiting the radix tree in depth-first order achieves the optimal hit rate, which longest-shared-prefix-first approximates. On their benchmarks hit rates ranged from 50 to 99% and the scheduler reached 96% of the optimal hit rate on average. In a month of serving open-weight models to a public chatbot arena, they observed hit rates of 52.4% for one model and 74.1% for another, cutting first-token latency by 1.7× on average for the latter.

The paged-block alternative

vLLM's automatic prefix caching stores the same information without an explicit tree. Each full block of tokens (16 by default) is identified by a hash of its parent block's hash, the tokens in the block, and extra keys including LoRA IDs, multimodal input hashes and an optional cache salt for isolating tenants. A new request hashes its prompt block by block and reuses every leading block whose hash is present. Freed blocks go into an LRU free queue, added in reverse order so that the deepest blocks of a request, which are least likely to be reused, are evicted first. Only full blocks are cached, so a request reuses at most the largest multiple of the block size within its matching prefix. In our simulation below, that granularity cost 0.4 percentage points of hit rate (94.6% against 95.0% for token-level matching).

Shared prefixes in decode

Prefix caching saves prefill. In decode, every sequence in a batch still reads the shared prefix's keys and values once per step, separately, because standard attention kernels process each sequence independently. Hydragen splits attention into a prefix part and a suffix part, batches all queries against the shared prefix into one matrix-matrix product, and merges the two parts with their log-sum-exp (the same rule as split-KV decoding in FlashAttention). It reports up to 32× end-to-end throughput for CodeLlama-13b with large batches and long shared prefixes. ChunkAttention reports 3.2 to 4.8× faster attention kernels with shared system prompts of 1,024 to 4,096 tokens. FlashInfer (Ye et al., 2025) supports the same shared-prefix decomposition through composable block-sparse formats in a production kernel library.

Worked example by hand#

A product built on a fine-tuned Llama 3 8B sends a 1,500-token system prompt with every request plus about 100 tokens of user input: $n=1,600$. With $P=8.03\times 10^9$ and $L{n}_h{d}_h=32\times 32\times 128=131,072$:

No cache. $F=2(8.03\times 10^9)(1600)+2(131,072)(1600^2)=25.70+0.67=26.37$ TFLOP. At 50% of an H100's 989 dense BF16 TFLOP/s that is 53.3 ms.

With a cached prefix. With 16-token blocks the reusable prefix is the largest multiple of 16 inside the 1,500 shared tokens, $m=1,488$, so 112 tokens remain: $F=2(8.03\times 10^9)(112)+2(131,072)(1600^2-1488^2)=1.80+0.09=1.89$ TFLOP, 3.8 ms. Prefill is 14× faster.

Memory. The cached prefix holds $1,488\times 131,072$ bytes = 195 MB of GPU memory, once, for all requests that share it. The trade is cache memory against prefill compute: 195 MB saves 24.5 TFLOP per request.

At scale. At 20 requests per second, the uncached system spends about 1.07 GPU-seconds per second on prefill alone, more than one H100's worth; the cached system spends 0.08. That difference goes straight into decode capacity, which is why cost per million tokens for template-heavy workloads drops sharply with prefix caching.

Simulation: hit rate, cache size and scheduling#

We simulated a block-hash prefix cache with LRU eviction on a synthetic chat workload (seeded numpy): 400 conversations over an hour, each using one of 10 system prompts of 300 to 2,000 tokens, with a geometric number of turns (mean 4, at most 12), user messages log-normal around 80 tokens and replies around 250 tokens, each turn resending the full history. That gave 1,603 requests and 3.44M prompt tokens (mean 2,147 per request). Every finished request inserts its prompt and reply into the cache, as both SGLang and vLLM do. We varied the cache budget and compared serving the waiting queue (window of 32 requests) first-come-first-served against longest-cached-prefix-first. Prefill time uses $F(n,m)$ above at 50% MFU on an H100.

With unlimited cache, 94.6% of prompt tokens came from cache and mean prefill time fell from 73.2 ms to 4.0 ms. Most of that reuse is conversation history, not system prompts, which is typical of chat. Capacity mattered sharply: with 13.1 GB of cache (100,000 tokens) the hit rate was 94.2%, at 6.6 GB 80.4%, at 2.6 GB 45.9% and at 1.3 GB 24.8% under first-come-first-served. Scheduling mattered exactly where capacity was short: longest-prefix-first raised the 1.3 GB hit rate from 24.8% to 73.4% (mean prefill from 55.3 to 19.7 ms) and the 2.6 GB rate from 45.9% to 76.5%, and made no difference once the cache was large. Token-level matching (a radix tree with no block rounding) beat 16-token blocks by 0.4 points. The lesson for capacity planning is to measure the working set of reusable prefixes, the tokens that will be asked for again before they would be evicted, and size the cache to hold it.

The scheduling result has a cost the simulation does not show: always serving the request with the longest match can starve requests with no match. SGLang's paper notes the starvation risk of greedy cache-aware scheduling; production schedulers bound it with priorities or ageing.

Fine-tuned models, adapters and templates#

Cache keys must include the weights. Keys and values depend on every weight up to the attention layer. A cached prefix computed under one fine-tune or LoRA adapter is wrong for another, even if the tokens are identical. vLLM includes LoRA IDs in its block hashes; any custom caching layer must also include model version and adapter identity, or it will silently serve one tenant's attention states to another.

Many adapters fragment the cache. We reran the simulation with each conversation assigned to one of $N$ adapters and the adapter ID folded into the hash. With a 6.6 GB cache, the hit rate fell from 80.3% with one model to 69.5% with 4 adapters, 57.6% with 16 and 54.8% with 64; with 2.6 GB, from 45.9% to 24.9% at 64 adapters. System prompts that were shared across the fleet are now cached once per adapter. If a product serves many adapters behind a common system prompt, consider whether the adapters need to touch the layers that process it, or whether a merged model with per-customer prompting would reuse more. See multi-LoRA serving and merge versus adapter.

Templates decide whether prefixes match. A prefix hit needs identical tokens from the first position. A chat template that puts a timestamp, request ID or user name at the top of the system prompt defeats caching for everything after it. So does a tokenizer change between model versions, or a fine-tune trained with a different template from the one the serving layer applies. Put stable content first and variable content last: tools and instructions, then retrieved documents, then the user turn. This is a post-training decision as much as a serving one, because the model must be trained with the template it will be served with.

Reasoning traces and agent transcripts are reusable. In multi-step agents, each call extends the previous transcript, so the cache from the previous call covers nearly the whole prompt. Templates that strip earlier reasoning from the history before the next turn change the prefix and turn hits into misses; that trade between context length and reuse is worth measuring.

Positional encodings are part of the prefix. Reuse is exact only when the prefix sits at the same positions. Moving a cached document to a different offset requires recomputation, or approximate approaches such as Prompt Cache's modules.

Tuning knobs#

The last row matters at scale. With $R$ replicas and random routing, each replica sees a random $1/R$ of requests, so a conversation's history is cached on whichever replica served its last turn; the next turn lands elsewhere with probability $(R-1)/R$. Session affinity or prefix-aware routing, as in Preble, which reports 1.5× to 14.5× lower average latency than the serving systems it was compared with, restores the hit rate.

Failure modes and how to detect them#

Low hit rate despite shared prompts. Look for a varying token near the start of the prompt: timestamps, IDs, shuffled tool lists, or whitespace differences from string formatting. Log the hit rate (cached prompt tokens over prompt tokens) per route; SGLang and vLLM expose it as a metric.

Cache thrash. Hit rate collapses under load while it is fine at low traffic. The working set exceeds the cache, or FCFS interleaving evicts prefixes before reuse. Enlarge the cache share, use cache-aware scheduling, or route by prefix.

Stale state after a deploy. Swapping weights or adapters behind the same model name without clearing or re-keying the cache produces outputs that mix old and new models. Include the weight version in the key and flush on deploy.

Cross-tenant timing side channels. A shared cache makes requests with a cached prefix measurably faster, which can reveal whether another tenant recently sent the same prefix. Use per-tenant salts where prompts are sensitive.

Decode still slow with long shared prefixes. Prefix caching does not reduce per-step reads of the prefix by every sequence. If TPOT is dominated by a long shared context, a prefix-aware decode kernel is the fix, not a bigger cache.

When it helps and when it does not#

Minimal implementation#

A block-hash prefix cache with LRU fits in a few dozen lines; this is the structure the simulation used.

from collections import OrderedDict

class PrefixCache:
    def __init__(self, capacity_blocks, block=16):
        self.block, self.cap = block, capacity_blocks
        self.blocks = OrderedDict()                   # hash -> physical block id, LRU order

    def _hashes(self, tokens, extra):
        h, out = hash(extra), []                      # extra: (model version, adapter id, tenant salt)
        for i in range(0, len(tokens) - len(tokens) % self.block, self.block):
            h = hash((h, tuple(tokens[i:i + self.block])))
            out.append(h)
        return out

    def match(self, tokens, extra):
        hit = []
        for h in self._hashes(tokens, extra):
            if h not in self.blocks: break
            self.blocks.move_to_end(h); hit.append(self.blocks[h])
        return hit                                    # reuse these blocks; prefill tokens[len(hit) * block:]

    def insert(self, tokens, extra, block_ids):       # after the request finishes (prompt + output)
        for h, b in zip(self._hashes(tokens, extra), block_ids):
            self.blocks[h] = b; self.blocks.move_to_end(h)
        while len(self.blocks) > self.cap:
            self.blocks.popitem(last=False)          # real engines skip blocks still referenced

In practice, use the engine's implementation: SGLang enables RadixAttention by default and vLLM enables automatic prefix caching with an engine option; both report hit rates. In POFE, the chat template and system prompt used during fine-tuning are stored with the model so the serving template matches token for token, which is what keeps these hits from silently disappearing after a fine-tune.

Further reading#

Zheng et al. (2023) introduces SGLang and RadixAttention, with the scheduling theorem and the production hit rates quoted here. The vLLM design documentation describes hash-based automatic prefix caching, including what goes into the block hash and the eviction order. Kwon et al. (2023) provides the paged, reference-counted blocks it is built on. Gim et al. (2023) explores modular reuse beyond strict prefixes. Juravsky et al. (2024) and Ye, Tao, Huang and Li (2024) address the decode-time cost of shared prefixes, and Srivatsa et al. (2024) extends prefix-aware scheduling to distributed serving.

Frequently asked questions#

References#

1. Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Chuyue Sun, Jeff Huang, Cody Hao Yu, Shiyi Cao, Christos Kozyrakis, Ion Stoica, Joseph E. Gonzalez, Clark Barrett, Ying Sheng (2023). SGLang: Efficient Execution of Structured Language Model Programs. arxiv.org/abs/2312.07104
2. Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, Ion Stoica (2023). Efficient Memory Management for Large Language Model Serving with PagedAttention. arxiv.org/abs/2309.06180
3. vLLM project (2025). vLLM design documentation: Automatic Prefix Caching. docs.vllm.ai/en/latest/design/prefix_caching.html
4. In Gim, Guojun Chen, Seung-seob Lee, Nikhil Sarda, Anurag Khandelwal, Lin Zhong (2023). Prompt Cache: Modular Attention Reuse for Low-Latency Inference. arxiv.org/abs/2311.04934
5. Jordan Juravsky, Bradley Brown, Ryan Ehrlich, Daniel Y. Fu, Christopher Ré, Azalia Mirhoseini (2024). Hydragen: High-Throughput LLM Inference with Shared Prefixes. arxiv.org/abs/2402.05099
6. Lu Ye, Ze Tao, Yong Huang, Yang Li (2024). ChunkAttention: Efficient Self-Attention with Prefix-Aware KV Cache and Two-Phase Partition. arxiv.org/abs/2402.15220
7. Vikranth Srivatsa, Zijian He, Reyna Abhyankar, Dongming Li, Yiying Zhang (2024). Preble: Efficient Distributed Prompt Scheduling for LLM Serving. arxiv.org/abs/2407.00023
8. Zihao Ye, Lequn Chen, Ruihang Lai, Wuwei Lin, Yineng Zhang, Stephanie Wang, Tianqi Chen, Baris Kasikci, Vinod Grover, Arvind Krishnamurthy, Luis Ceze (2025). FlashInfer: Efficient and Customizable Attention Engine for LLM Inference Serving. arxiv.org/abs/2501.01005

Related reading