The Radix Tree
That Serves the Fleet

A 2,048-token system prompt served a million times a day is two billion tokens of prefill computing attention over the exact same text, over and over. Prefix caching computes it once and reuses the key-value state. The radix tree is the data structure that makes that reuse automatic — no annotations, no cache keys, just the longest matching prefix, found in microseconds.

01 Where Prefixes Repeat

The redundancy audit: five places your fleet recomputes the same tokens.

Every production inference fleet has a dirty secret: most of what it computes during prefill, it has computed before. Not approximately — token-for-token, byte-for-byte identical. The redundancy concentrates in five places, and each one has a characteristic size:

Put a number on it. Take a 2,048-token system prompt on a 70-billion-parameter model. A forward pass costs roughly 2 FLOPs per parameter per token — 140 GFLOP per token, or 287 TFLOP for the full prompt. An H100 delivers about 989 TFLOPS of dense BF16; at a realistic 60% model FLOPs utilization that is ~590 TFLOPS of sustained throughput, so the system prompt alone costs ~0.48 seconds of prefill per request. Serve it a million times a day and you have burned 483,000 GPU-seconds — 134 H100-hours, every day — recomputing attention over text that has not changed by a single token.

That is the prize, and it is large because prefill is compute-bound. Prefill is one giant matrix multiplication with high arithmetic intensity: the FLOPs are the scarce resource, and on a serving GPU those FLOPs are shared with decode. Skipping prefill does not just cut latency; it frees the exact resource the rest of the fleet is fighting over. This is why prefix caching punches above its apparent weight in throughput benchmarks: the SGLang paper reports cache hit rates of 50–99% across its benchmark suite and up to 6.4× higher end-to-end throughput versus the inference systems it compared against, with the cache-aware scheduler landing within ~96% of the optimal hit rate on average. The wins concentrate wherever the same prefix fans out — few-shot evals, multi-turn chat, agent templates, RAG pipelines.

The uncomfortable corollary: if your fleet does not cache prefixes, you are renting a meaningful fraction of your GPUs to re-derive key-value tensors you already derived this morning. The rest of this essay is about the data structure that stops that, the routing layer that keeps it working past one server, and the arithmetic that tells you how much cache to buy.

02 RadixAttention Mechanics

A tree of token sequences, where every shared prefix is stored exactly once.

SGLang's RadixAttention stores the KV cache in a radix tree keyed by token sequences. Each edge of the tree carries a run of tokens; each node holds the KV blocks for its token span. Inserting a request means walking the tree from the root, consuming the request's tokens against edge labels. When the walk stops matching mid-edge, the edge splits — the classic radix-tree insertion — and the unmatched suffix becomes a new child node whose KV is computed by prefilling only that suffix. Lookup is the same walk: the longest match wins, the matched nodes' KV is referenced instead of recomputed, and only the divergent tail goes through the model.

Three properties make this more than a trie with extra steps. First, granularity is the token, not the block: SGLang's page size defaults to a single token, so a match can end at any token boundary. If two requests share 2,047 of 2,048 system-prompt tokens, the radix tree reuses 2,047 tokens' worth of KV. Second, matches are longest-prefix by construction, and the tree is position-aware — a node at depth k holds KV computed at absolute positions 0..k, which is exactly where the next request's prefix sits. Third, the tree grows during decode: as a request generates tokens, its new tokens extend the tree, so the next turn of the same conversation finds its entire history already cached. Multi-turn reuse is not a special case; it falls out of the insert path.

Memory management is reference counting plus LRU, and the order matters. Each tree node carries a lock reference count incremented by every active request holding its prefix. Eviction only considers nodes with a zero count — you never yank KV out from under a running decode — and among those, the least-recently-used leaf goes first. When a new request needs KV blocks and the pool is full, the tree sheds its coldest unreferenced leaves until the allocation fits. In SGLang this all lives in the same paged KV pool as active requests, which means the prefix cache and the running batch compete for the same HBM. That competition is the entire subject of section 04.

The contrast that matters is with vLLM's automatic prefix caching, because the two designs optimize different things:

vLLM's design is worth understanding on its own terms. Each 16-token block is hashed together with its parent block's hash, so a block's hash fingerprints the entire prefix up to that block — two identical blocks at different positions hash differently, which is what makes reuse position-safe. Lookup is a hash-table probe per block: O(prefix / 16) probes, effectively free next to prefill. The v1 engine reports under 1% throughput overhead even at a 0% hit rate, which is why it ships enabled by default. The price of that simplicity is coarseness: only full blocks are cached, and a single token differing mid-prefix kills the match from that block onward, even if everything after it is identical. The radix tree has no such cliff — it matches up to the divergent token and prefills only the rest. That is the fundamental tradeoff: hash blocks buy O(1) lookups and trivial bookkeeping; the radix tree buys the longest possible match at the cost of a tree walk and node bookkeeping per token span.

The tree walk itself is cheap, but it is worth knowing where it runs. Lookup and insert are O(prefix length) edge comparisons executed on the scheduler CPU per request — microseconds against a prefill that costs milliseconds to seconds, which is why the radix design can afford token granularity where a GPU-side structure could not. SGLang exposes the granularity knob as --page-size: the default of 1 keeps edges per-token, while raising it makes the edge list per-page, trading fine-grained matches for cheaper bookkeeping. Raise it and a 2,047-of-2,048 shared prompt starts behaving like the block-hashed design — the cliff returns. The default is 1 for a reason.

One more mechanism worth naming: the hash chain's extra_keys. vLLM folds LoRA adapter IDs, multimodal input hashes, and per-tenant cache salts into the block hash, so the same token sequence under a different adapter or a different tenant simply hashes differently and never collides. Keep that in mind for section 05 — it is the cheapest correct answer to the multi-tenancy problem.

The tree stores the 2,048-token system prompt exactly once (blue trunk, referenced by three live sessions) and branches per conversation (green). Chat A's fourth turn extends its own branch — that extension is what the next turn will hit. The gray leaf is a dead RAG chunk: zero references, oldest access time, evicted to make room. Note the asymmetry that makes the whole scheme work — the trunk's KV is hot and shared, the leaves are cold and disposable, and the tree knows which is which without any application hint.

03 Cache-Aware Routing

One server's tree is not enough: the fleet-level scheduler.

A radix tree lives inside a single server process. Put four of those servers behind a round-robin load balancer and watch what happens to locality. A globally shared prefix — the system prompt every request carries — is harmless: each of the four trees absorbs one cold prefill, then keeps hitting. The cost is four copies of the KV instead of one, not a hit-rate collapse. What round-robin genuinely destroys is session-scoped locality: a multi-turn conversation's growing context, a per-tenant document block, an agent's trajectory. Those prefixes live on exactly one worker, so a follow-up request has roughly a 1/N chance of landing where its prefix is cached. With eight data-parallel workers, seven out of eight follow-ups recompute a prefix that is sitting warm in another server's HBM. The tree did its job; the router threw the win away.

The fix is a router that knows what each worker has cached. SGLang ships one as a separate component — installable via sglang-router, launched with --policy cache_aware — that keeps an approximate prefix tree of what every worker has recently served and routes each incoming request to the worker holding its longest matching prefix, blended with load. The router's tree is approximate on purpose: it tracks hashes of served prefixes, not the KV itself, so it stays small and fast. The Gateway v0.3.1 release notes quantify the engineering that went into that approximation — 216,000 cache insertions per second (up from 18,900), 4.6 microseconds per operation (down from 52.9), 124,000 prefix-match operations per second across 10,000 tree entries, and per-node memory cut from ~180 KB to ~1.4 KB, so 10,000 tracked prefixes cost about 14 MB instead of 1.8 GB. At that budget the router's bookkeeping is noise next to inference.

The same idea appears in disaggregated architectures, where it matters doubly. Mooncake's scheduler is KVCache-centric: it maintains a global view of prefix locations and uses it to place prefill work where the prefix already lives. When prefill and decode run on different hardware, a missed prefix does not just cost recompute — it costs the recompute plus the KV transfer from the prefill worker to the decode worker over NVLink or RDMA. Disaggregation makes the prefill side the natural home of the radix tree (that is where the KV is born) and makes the router's placement decision load-bearing for interconnect bandwidth, not just FLOPs. The principle generalizes beyond any one system: the radix tree is a per-server index, and a fleet needs a fleet-level index over those indexes — a two-level lookup where the router resolves which server and the server resolves which nodes.

Affinity and load balance now fight, and the router has to referee. Pure prefix affinity piles every request sharing a hot system prompt onto the smallest set of servers that hold it, and those servers drown while the rest idle. Three mechanisms keep the peace. First, bounded affinity: prefer the affined worker, but fall back to the least-loaded worker when the queue-depth delta exceeds a threshold — locality is a preference, not a prison. Second, replication of hot roots: the router deliberately warms the hottest prefixes (the system prompt, the top few RAG headers) onto multiple workers, trading a few redundant copies of a 2K-token KV for the ability to spread the requests that share it. Third, overlap-aware admission: a request whose longest match is twelve tokens should not be steered to a loaded server for twelve tokens of savings; the router should weigh expected prefill savings against queueing delay. None of this requires machine learning. It requires the router to know two numbers per worker — longest match length, current load — and a policy for trading them off.

How do you know any of this is working on your traffic? SGLang ships the experiment: its bench_serving load generator includes a generated-shared-prefix dataset that synthesizes request groups sharing a long system prompt, with knobs for group count, prompts per group, and prompt lengths. Run it once normally and once with --disable-radix-cache; the delta in throughput and time-to-first-token is the value of prefix caching on your traffic shape. Do the same A/B with the router's cache-aware policy on and off to isolate the routing contribution from the tree contribution. If you cannot measure the two separately, you cannot tune the tradeoff between them.

The router holds an approximate prefix tree per worker — hashes of served prefixes, not KV — and steers each request to its longest match. Blue arrows carry the hot system prompt to the two workers holding it (orange); green carries a session prefix to its home worker; the orange arrow shows bounded affinity in action, spilling a RAG-header request to worker 3 because worker 2 is loaded. The numbers in the router box are from SGLang's Gateway v0.3.1 release: the approximate index is small enough (1.4 KB per node) and fast enough (microseconds per match) that routing on prefix affinity costs essentially nothing. The takeaway is architectural: prefix caching is a two-level lookup — the router resolves which server, the server's radix tree resolves which nodes — and skipping the first level silently forfeits the second.

04 Hit-Rate Math

Sizing the cache: how many gigabytes buy how much hit rate.

Prefix popularity in production is Zipf-ish: a small head of prefixes — the system prompt, the top few RAG headers, the active conversations — absorbs most requests, and a long tail of one-off prompts absorbs the rest. That shape is what makes prefix caching viable at all, because the cache itself is shockingly small when measured in prompts. The accounting starts with per-token KV bytes: 2 (K and V) × layers × KV heads × head dimension × bytes per element.

Read the middle row carefully: ten gigabytes of prefix cache holds about 32,768 tokens of Llama-70B KV — sixteen distinct 2,048-token system prompts. That is the entire cache, in prompt-count terms, and it is why the Zipf head matters more than the raw capacity. You do not need to cache every prefix; you need the head of the distribution resident, because the head is where the requests are. DeepSeek's multi-head latent attention is worth a row in this table for a different reason: by compressing KV to ~70 KB per token, MLA makes the same ten gigabytes hold roughly 150K tokens — nearly 5× the prefixes. Architecture choices upstream of serving show up directly as cache capacity downstream.

The curve this produces has a knee, and the knee is where you should operate. Early gigabytes capture the hottest prefixes and hit rate climbs steeply; past the knee you are caching the long tail, and each additional gigabyte buys single-digit basis points. The exact position of the knee is workload-specific — it is a property of your prefix distribution, not of the hardware — which is why the honest version of this diagram is one you draw from your own traffic: log prefix hashes per request for a day, sort by frequency, and plot cumulative request coverage against cumulative KV bytes. The two numbers that matter are the hit rate at your HBM budget and the slope past it. If the slope is flat, stop buying cache.

And the budget is real, because the cache does not get its own memory. In SGLang the radix tree lives in the same paged KV pool as active requests: when a new request needs blocks and the pool is full, the tree evicts its coldest unreferenced leaves to make room. Every gigabyte of prefix cache is a gigabyte not available to the running batch, which means oversizing the cache directly shrinks maximum batch size — the very throughput you were trying to buy. Size the cache as HBM minus the working set of your running batch at target concurrency, not as a fixed fraction of the card.

The latency side of the math is simpler. A full hit skips prefill entirely, so time-to-first-token collapses to scheduling delay plus one decode step. For the 2K-token system prompt on the 70B model from section 01, that is roughly 480 ms of prefill replaced by ~45 ms of decode — a 10× TTFT cut on the exact requests (short outputs, chatty agents) where TTFT dominates user experience. A partial hit is proportional: match 1,500 of 2,000 prefix tokens and you prefill only the 500-token suffix, paying a quarter of the prefill. This is also why the radix tree's token granularity beats block hashing on latency: the longest match is, by definition, the shortest suffix, and prefill cost scales with the suffix.

Chunked prefill composes with all of this in a way that is easy to miss. A request whose prompt ends mid-block leaves a partial block that hash-based caches cannot publish — only full blocks are immutable and therefore cacheable. Chunked prefill lets the scheduler fill that partial block with tokens from the next request's prefill chunk, completing the block so it becomes eligible for the cache. In other words, chunking does not just smooth prefill latency; it converts would-be-wasted partial blocks into future hits. If you run vLLM with prefix caching on and chunked prefill off, you are systematically discarding the tail block of every prompt.

The curve is drawn from a modeled Zipf working set, not measured traffic — treat the shape as the argument and the numbers as illustration. The shape is the point: hit rate climbs steeply while the cache absorbs the hot head of the prefix distribution, then flattens at the knee (here ~8 GB / 85%, roughly thirteen 2K-token 70B prefixes). The red dashed line is the real constraint: the cache lives in the same HBM as the running batch, so the budget is HBM minus working memory at target concurrency. Operating between the knee and the budget line is the whole game; gigabytes past the knee buy basis points. The TTFT annotation from the text belongs on this chart too: at a full hit, that 480 ms prefill becomes ~45 ms of decode, which is why the steep part of this curve is worth more than any other optimization you can buy with 8 GB of HBM.

05 Sharp Edges

What breaks: pollution, position encodings, and other tenants.

The first failure mode is cache pollution, and the arithmetic is unforgiving. A single one-off request carrying a 100K-token document does 100,000 × 320 KiB ≈ 32 GB of KV writes on a 70B model — it evicts a 10 GB prefix cache more than three times over, flushing every hot system prompt to make room for a prefix that will never be requested again. The defense is admission control, and the cheapest effective policy is frequency-gated insertion: do not cache a prefix until it has been seen twice. The first sighting only records the hash; the second one earns residency. Complementary policies: a minimum prefix length (short prefixes save little prefill and cost tree bookkeeping), and segmented trees — a small protected segment for prefixes with proven high frequency that the general LRU cannot evict. Without admission control, your hit rate is at the mercy of whoever sends the longest prompt.

The second failure mode is correctness, and it lives in the position encodings. Rotary position embeddings rotate queries and keys by absolute position, so cached KV is only valid at the exact positions where it was computed. Prefix caching satisfies this by construction — a prefix always occupies positions 0..k — which is why the radix tree never attempts to reuse a non-prefix span. The invariant breaks when the position mapping changes between write and read: switch YaRN scaling factors on a long-context deployment and every cached entry was computed under a different position-to-rotation mapping, silently producing wrong attention. The operational rule is blunt — any change to RoPE scaling, context-window extension, or position scheme invalidates the entire tree — and the tree must be flushed, not trusted. Sliding-window attention adds its own wrinkle: with a finite window, a token's effective context is the window behind it, so reuse across different absolute positions is wrong even when the tokens match; prefix-only caching stays safe because the window contents coincide, but it is exactly the kind of invariant that deserves a test rather than an assumption. What does not affect KV validity is worth stating too: sampling temperature, top-p, and penalties never touch the key-value tensors, so varying them across requests sharing a prefix is always safe, as is sharing across different LoRA adapters only when the adapter ID is part of the cache key — which is precisely what vLLM's extra_keys are for.

The third failure mode is other tenants. When two users share a cached prefix, the second user's time-to-first-token reveals whether the first user warmed it — a timing side channel leaking the fact that someone sent that prefix recently. For a public system prompt the leak is vacuous (the text is identical for everyone by design), but for per-tenant RAG headers or private document chunks it is a real, if narrow, information disclosure: presence in the cache is presence in someone's recent traffic. The mitigations are, in increasing order of paranoia: scope caches per tenant (vLLM's per-tenant cache salts make cross-tenant hits cryptographically impossible by salting the block hash); partition the tree so sensitive tenants get private subtrees; or disable cross-request caching for the sensitive prefix classes while keeping it for the public ones. Note the asymmetry with the pollution problem — here the fix is less sharing, and the cost is measured in duplicated hot prefixes, which section 04's math says are cheap because the head of the distribution is small.

It is worth contrasting all of this with the managed-service model, because Anthropic's prompt caching is prefix caching with the tree replaced by explicit programmer intent. You mark up to four cache_control breakpoints in a request; each segment must clear a minimum length — 1,024 tokens on most models, 4,096 on the newest — and the provider caches the prefix up to each breakpoint. Pricing makes the economics explicit: cache writes cost 1.25× the base input price (2× for the 1-hour TTL option), cache reads cost 0.10×, and the default TTL is five minutes. The operational skill is breakpoint placement: put them at stability boundaries — system prompt, tool definitions, stable conversation history — with the most volatile content last, because everything after the first changed byte is recomputed. It is the manual analogue of the radix tree's automatic longest-prefix match, and the comparison is instructive: automatic caching wins when prefixes are unpredictable, explicit breakpoints win when you know exactly where stability ends and you want the bill itemized.

06 Open Questions

Where the next wins are: colder tiers, prediction, and prefix-aware scaling.

The tree in HBM is the hot tier, but there is no law saying the prefix store ends at the GPU. vLLM's offloading connector and LMCache-style designs add colder tiers — CPU DRAM, then NVMe — with coarser chunks (256 tokens is the common granularity) and an inclusive write-down policy: every completed block is written to the cold tier on a dedicated stream precisely so the write cannot delay token generation, while reads back into HBM cost real latency and are only worth it for long prefixes. The open engineering question is the admission policy between tiers: which prefixes deserve the HBM tree, which the DRAM tier, which nothing at all — a three-level version of the frequency gating in section 05, with the added wrinkle that a cold-tier hit still skips GPU prefill compute at the cost of PCIe/NVMe transfer time.

Prediction is the second frontier. An agent's next tool call is often predictable — the trajectory so far plus the tool schema strongly constrains what comes next — which means the router could warm the likely prefix onto a worker before the request arrives, turning a cold start into a hit. The same applies to RAG: if the retriever runs ahead of the generator, the retrieved chunks can be prefetched into the tree while the user is still reading. Prefetching trades memory bandwidth for latency on a speculative basis, so it needs a confidence threshold, but the mechanism is just a cache fill with a predicted key.

The third is prefix-aware autoscaling. Today's autoscalers watch queue depth and GPU utilization; a prefix-aware one watches the tree. When a new hot prefix appears — a viral prompt template, a fresh RAG index — the fleet should replicate that prefix's root across workers before affinity piles all its traffic onto one server, and scale up the workers holding hot prefixes rather than the fleet uniformly. The telemetry for this already exists in the router's approximate tree; nobody has quite closed the loop into the cluster autoscaler yet. When they do, "scale the fleet" will mean "scale the hot subtrees," and the radix tree will have quietly become a load signal as well as a cache.