Prefix Caching With Radix Trees: Reusing Prompt Work Across Requests

What a cache hit saves

Prefill is the forward pass over the prompt that produces its KV cache and the first output token. Its cost is roughly linear in the number of prompt tokens for moderate lengths, and it sets time to first token (TTFT). If a GPU prefills about 10,000 tokens per second for a given model (an illustrative figure; measure your own), a 1,500-token system prompt costs 150 ms of GPU time every time it is recomputed: 150 GPU-seconds per thousand requests spent producing state that already existed.

Multi-turn chat makes it worse, because the prompt grows with every turn. Take a conversation with a 1,500-token system prompt, user messages of 150 tokens and answers of 250 tokens:

turn  prompt tokens (no cache)          new tokens (with cache)
1     1500 + 150              = 1650     1650   (cold)
2     1650 + 250 + 150        = 2050      150   (answer 1 was inserted into the tree)
3     2050 + 400              = 2450      150
4     2850                                 150
5     3250                                 150
6     3650                                 150
total 15,900 prefill tokens                2,400 prefill tokens  -> 85% less (calculated)

Without caching, total prefill over a conversation grows quadratically with the number of turns; with caching it grows linearly. The saving shows up in two places: lower TTFT for the user, and fewer GPU-seconds of prefill, which in a disaggregated or autoscaled deployment is directly fewer GPUs. It costs memory: the cached KV for that 1,500-token prefix at 128 KiB per token is about 190 MiB, which has to stay resident to be useful.

The radix tree: one path per distinct prefix

A radix tree (a compressed trie) stores sequences so that shared beginnings are stored once. Each edge is labelled with a run of tokens, and each node points at the KV cache for those tokens. Inserting a prompt walks down from the root, following edges whose tokens match; where the prompt diverges, the edge is split and a new branch is added. Matching a new prompt is the same walk, and the length of the walk is the number of tokens whose KV can be reused.

def match_prefix(root, tokens):
    node, i, kv = root, 0, []
    while i < len(tokens):
        child = node.children.get(tokens[i])          # edges are keyed by their first token
        if child is None:
            break
        n = common_prefix_len(child.tokens, tokens[i:])
        kv.append(child.kv[:n]); i += n
        if n < len(child.tokens):                    # diverged inside the edge: split it on insert
            break
        node = child; node.last_access = now()
    return i, kv                                      # i tokens are cached; prefill tokens[i:] only

Three properties make this fit an inference server. First, the tree is naturally hierarchical in the way prompts are: system prompt at the top, then per-conversation history, then the newest turn. Second, generated tokens are inserted when a request finishes, so the next turn of a chat matches through its own previous answer. Third, eviction is simple: SGLang evicts least-recently-used leaves, so the shared system prompt near the root survives while old conversation tails go first. Nodes in use by running requests are reference-counted and cannot be evicted.

vLLM's automatic prefix caching gets the same effect differently. Each full KV block is identified by a hash of its tokens together with the hash of every block before it, so equal prefixes produce equal block hashes and the block table of a new request can point at existing physical blocks. Freed blocks with a hash stay in the pool as cache until their memory is needed. The practical difference is granularity: block hashing reuses whole blocks only (a 16-token block size means up to 15 tokens of a match are recomputed), while a token-level radix tree can match to the exact token.

Cache memory is borrowed, not reserved

In both designs the cache lives in the same KV pool as running sequences. A cached prefix with no active users is just a set of blocks that have not been reclaimed yet. When a new sequence needs memory, the allocator evicts cached entries before it preempts anyone. This is elegant, but it means the effective cache size is whatever is left over after the running batch, and it shrinks exactly when traffic peaks.

Size the working set to know whether that leftover is enough. With 6 distinct system prompts of 1,500 tokens, the shared part is 9,000 tokens, about 1.1 GiB at 128 KiB per token: trivial. Conversation history is the expensive part. At 16 requests per second with 4 turns per chat and 8 to 10 seconds between turns, roughly 100 to 150 conversations are open at any time, each holding 1,000 to 3,000 tokens of history: 200,000 to 400,000 tokens, or 25 to 50 GiB across the fleet. If the cache on each replica is a few GiB, most history is evicted between turns and only the system prompts reliably hit. The lab's evicted-tokens tile makes this visible: when it climbs, recomputation is happening because the tree forgot.

What silently breaks the hit rate

A prefix cache matches from the first token. Anything that differs early in the prompt invalidates everything after it, no matter how much identical text follows. The common culprits:

The timestamp is the classic incident because it looks harmless in code review. In the lab, mission two reproduces it: a release adds the time to the second inside the system prompt, and with 200 tokens before it and 1,300 after, every request after that second recomputes the system prompt body and its entire history. The hit rate on the same traffic falls from the mid-70s to the low 40s in percent. Nothing errors. TTFT and prefill cost just rise.

Detection needs a metric for it. vLLM and SGLang both report prefix cache hit rates; plot the hit rate per model and per application and alert on a step change after deploys. Also log a hash of the first few hundred tokens of each prompt template so that a template change is easy to correlate.

Routing: a cache only helps where the request lands

Each replica has its own tree. With round-robin routing across R replicas, the next turn of a conversation lands on the replica holding its history with probability 1/R; with 6 replicas, about 17% of the time. Meanwhile every replica caches its own copy of every system prompt, so the fleet stores the same prefixes R times and the per-replica cache available for history shrinks accordingly.

There are three practical routing strategies, in increasing order of cleverness:

• Session affinity. Hash a session or conversation ID to a replica. Cheap and effective for chat history. It does nothing for prefixes shared across sessions, and it rebalances badly when replicas are added or removed unless you use consistent hashing.
• Prefix hashing. Hash the first N tokens (or the template ID) to choose the replica, so each system prompt lives on one replica. Good for many-tenant traffic; creates hot spots when one prefix dominates.
• Cache-aware routing. The router keeps an approximate copy of each replica's tree, routes to the replica with the longest match, and falls back to the least-loaded replica when the load gap between them exceeds a threshold. SGLang's router implements this policy, with thresholds for the minimum match ratio and for absolute and relative load imbalance; check the flag names for your version.

The threshold is the interesting knob because it is a genuine trade-off. Pure affinity maximises hits but sends the biggest tenant's traffic to one replica, whose queue then sets p95 TTFT for everyone it serves. Pure load balancing equalises queues but scatters prefixes. Mission three asks you to serve the same load on fewer replicas by routing on prefixes; mission four adds a tenant surge and a burst so that the right spill threshold is neither zero nor infinite.

Scheduling inside one replica

Within a replica, the order in which waiting requests are admitted also affects hits. SGLang's cache-aware scheduling sorts the waiting queue so that requests with the longest cached prefix go first; this keeps hot branches in the tree and avoids evicting a prefix just before a waiting request would have used it. Longest-prefix-first can starve requests with cold prompts under sustained load, so implementations fall back to first-come-first-served when the queue is long. If you see a small population of requests with much worse TTFT than the rest, and they are the ones with unusual prompts, this is a likely cause.

Prefix caching also interacts with chunked prefill and with speculative decoding, LoRA adapters and multimodal inputs. Cached KV is only valid for the same model weights, the same adapter and the same preceding tokens, so servers key the cache accordingly; a fleet serving many adapters has many separate trees. Images and audio usually enter the cache through placeholder tokens plus a content hash, which differs between servers. Check your version's documentation before assuming a feature combination is cached.

Security and isolation

A shared cache is observable. If two tenants share a replica and tenant A's prompt makes tenant B's prompt faster, B can in principle infer that A sent a prompt with a given prefix by timing TTFT. For most single-application deployments the shared content is your own system prompt and this does not matter. For multi-tenant platforms it does. Mitigations are to partition caches per tenant (separate replicas, or a per-tenant salt mixed into the cache key where the server supports it) and to avoid sharing caches across trust boundaries. Hosted model APIs implement their own prompt caching with their own isolation and pricing rules; read the provider documentation rather than assuming they behave like your self-hosted server.

A worked example: Belgavi's Book Store support chat

The hypothetical Belgavi's Book Store runs a support chat at 30 requests per second on a fleet where each replica prefills about 10,000 tokens per second. Prompts carry one of six 1,500-token system prompts (one per help topic) and an average of about 550 tokens of history, so about 2,050 tokens per prompt. Without caching, a request costs 15 ms of overhead plus about 205 ms of prefill, so the fleet needs about 6.6 replica-seconds of prefill per second: seven replicas just to keep up, with no headroom.

With a radix cache of 1 GB per replica and round-robin routing over six replicas, every replica caches the system prompts, but history lands on the right replica only one time in six and is often evicted anyway, so in the lab's model just under half the prompt tokens come from cache and prefill costs about 120 GPU-seconds per thousand requests. With cache-aware routing on three replicas and a 200 ms spill threshold, about two thirds of prompt tokens hit and prefill falls to roughly 83 GPU-seconds per thousand requests, while p95 TTFT stays under 0.4 s. Same traffic, less than half the prefill capacity. These are calculated with the lab's illustrative constants, not measured, but the structure of the result is what you should expect: caching removes the system prompt cost, and routing decides whether you also remove the history cost.

Common mistakes

• Turning on prefix caching and never checking the hit rate, so a template change that broke it goes unnoticed for months.
• Putting per-request values (date, user ID, request ID, retrieved documents) before stable instructions.
• Load balancing an LLM fleet with a generic round-robin proxy, which scatters conversations and multiplies cache memory by the number of replicas.
• Pinning by prefix without a spill rule, creating one hot replica per popular tenant.
• Benchmarking with unique random prompts, which hides caching benefits, or with one repeated prompt, which overstates them. Replay real prompt structure.

Run the lab: Prefix caching: keep the KV you already paid for

The lab generates sixty seconds of synthetic multi-turn chats. Every replica keeps a real radix tree over prompt segments (system prompt, each user turn, each answer) with least-recently-used leaf eviction, and a router chooses the replica for each request. The left of the canvas shows recent prompts on each replica as bars: green is the cached prefix, orange the part that had to be prefilled. On wide screens the right side draws the tree on replica one halfway through the run. Start with the cache off, then work through the missions.

Prefer a full-width view? Open the standalone lab. Your stars are saved in this browser and shown on the series hub.

What to do next

1. Enable prefix caching in a canary (check whether your server version already enables it by default) and record the hit-rate metric it exposes.
2. Audit your prompt templates: list every value that changes per request and move it after the stable instructions and tool definitions.
3. Serialise tool and schema definitions deterministically so equivalent prompts produce identical tokens.
4. Measure what share of chat turns land on the replica that served the previous turn; if it is about 1/R, add session or cache-aware routing.
5. If you use cache-aware routing, tune the load-imbalance threshold with a burst test and watch p95 TTFT on the busiest replica.
6. Decide whether tenants may share a cache, and partition or salt cache keys where they must not.

Sources and further reading

• SGLang: Efficient Execution of Structured Language Model Programs (RadixAttention)
• Efficient Memory Management for Large Language Model Serving with PagedAttention (SOSP 2023)
• vLLM documentation: engine arguments
• SGLang documentation

Related in this series:

• PagedAttention Block Tables: How vLLM Ends KV Cache Fragmentation
• Semantic Caching for LLMs: Similarity Thresholds and the Wrong-Answer Risk
• KV Cache Capacity Planning: How Many Concurrent Users Fit on One GPU

Diagrams, examples and the lab model are original educational material. Lab numbers are calculated by a synthetic model, not measured on real hardware or services.

Views are my own and do not represent any employer, past or present.