What a Radix Tree Saves on a Shared Prompt

An SGLang deployment serves a product where every request carries the same 2,000-token system prompt and few-shot block, followed by a user turn averaging 100 unique tokens. RadixAttention keeps a radix tree mapping token sequences to paged KV blocks, and evicts the least recently used leaf first.

Across 1,000 requests, what changes, and what does the leaf-first eviction rule protect?

Decode gets about 95% faster and prefill is unaffected, since the cache is only consulted while generating.

Prefill drops about 95%, and the saving grows as user turns get longer, since longer turns share more of the tree.

Prefill drops from about 2.1M tokens to about 102K, roughly 95% less prefill work, since only the 100 unshared tokens per request need computing. Evicting leaves first keeps the shared ancestor path resident as long as any branch still depends on it.

Nothing changes unless two requests are byte-identical end to end: a cache hit needs the whole prompt to match.

Prefill drops about 95%, but LRU eviction keeps deleting the shared prefix, because it is the oldest node in the tree.