Guide

Core optimizations

RadixAttention

SGLang stores retained KV in a radix tree keyed by token sequences. Shared prefixes are shared paths from the root, with LRU eviction at the leaves.

72 of 138 · 2 min read

SGLang's RadixAttention stores retained KV in a radix tree (a compact trie) keyed by token sequences. Edges hold token spans. Nodes point at paged KV for that span. Shared prefixes are literally shared paths from the root.

Insertion: after a request completes, or as it runs, merge its token path into the tree, reusing nodes where prefixes match. Lookup: match the longest cached prefix of a new request; only the suffix needs prefill. Eviction: GPU memory is finite. RadixAttention uses LRU among leaves, roughly evicting least-recently-used leaves and folding the tree, so popular trunks like the system prompt stay while one-off tails drop.

Concept

A radix tree is a compact prefix tree. Each edge stores a span of tokens, not a single token, so long shared heads collapse into one path.

The big idea

Think of a filing cabinet whose drawers are labeled by the start of the filename. Every file that begins "ACME / policy /" shares that drawer. A one-off customer letter lives in its own thin folder at the end, and those folders get tossed first.

The picture breaks at memory. The tree lives in HBM unless you add lower tiers. A popular trunk is cheap to keep. A long unique tail is expensive.

Walking through a hit

A new request starts with the same system prompt as everyone else, then a new user turn. Lookup walks root → system prompt as a hit, then misses at the user node. Prefill runs only on the user suffix. After the request, that suffix is inserted as a new branch. Tomorrow, if the same user continues the chat, the assistant node can hit too.

The LMSYS SGLang writeup reported large throughput and TTFT wins on workloads with shared prompts and multi-turn structure — exactly where a tree beats a single flat "last prompt" cache.

Trade-off

GPU-only radix cache vs a larger multi-tier cache. Keeping everything in HBM maximizes hit speed but limits the working set. Evicting to CPU or SSD raises hit rate for long-lived sessions at the cost of reload latency. Interactive SLOs often keep hot trunks in GPU and demote cold sessions downward. See multi-tier prefix cache.

Common mistakes

  • Treating the tree as a full-history store. Leaves get evicted. Only popular trunks are safe to assume.
  • Comparing it to a single-slot "last prompt" cache. A tree shares one system prompt across many users at once.
  • Ignoring insertion cost. A huge unique completion still occupies nodes until LRU drops it.

Check yourself

  1. Two users share a system prompt and then diverge. How many copies of the system KV does the tree keep? Answer: one. Both paths share the trunk from the root.
  2. Why evict leaves first, not the trunk? Answer: the trunk is the common prefix. Evicting it would miss for everyone. Leaves are one-off tails.

Key takeaways

  • RadixAttention stores prefixes in a radix tree of paged KV.
  • Lookup is longest-prefix match. Only the suffix prefills.
  • LRU at the leaves keeps popular trunks and drops one-off tails.
  • A tree beats a flat last-prompt cache on shared and multi-turn traffic.

Further learning

SGLang paper and the LMSYS RadixAttention blog. Next, cache-aware routing.

Prefix caching

Reusing KV across requests that share prompts. Block hashing, RadixAttention, cache-aware routing, and why cached input tokens are billed cheaply.

Automatic prefix caching

With paged KV, each block is hashed from its tokens. Identical spans reuse the same physical blocks, so prefill can skip work without an application change.

Multi-tier prefix cache

Extend a radix or block cache from GPU HBM to host DRAM and then SSD. Larger working sets, slower hits. Worth it for long-lived sessions, not short one-offs.