Radix Cache

Many requests share common prefixes: a policy document, a few-shot pack, the same tool list on every agent step.

Radix caching reuses KV cache across requests that share prefixes. The engine skips work it has already done.

In this post I cover:

Why prefixes are worth caching
The radix tree that holds KV cache
How matching and eviction work

The expensive part is the prefix

When an LLM runs a prompt, it builds a KV cache — keys and values for every token it has seen so far. The next token attends over that cache instead of recomputing the whole prompt.

That is cheap inside one request. The usual waste is across requests.

The engine finishes a reply, then throws the cache away. The next call arrives with the same long document on top. Prefill starts from zero again.

Prefix sharing, with a policy bot

Imagine an internal bot that always loads the same refund policy, then answers a ticket.

Ticket A:

[Refund policy — 4 pages]
How many days does a customer have to request a refund?

Ticket B, a few seconds later:

[Refund policy — 4 pages]
Can I refund a charge paid with a corporate card?

The policy text is identical. Only the question changes.

Without a radix cache, both tickets prefill the full prompt. You pay twice for those four pages.

With a radix cache, ticket B reuses the KV for the policy and only computes the new question.

The same pattern shows up everywhere:

Workload	Shared prefix
Chat with a doc	The uploaded file, different questions
Few-shot	The labeled examples you put before every ticket
Multi-turn chat	The system rules plus earlier turns in that thread
Agents	The same tool list on every step

The new text is often a sentence. The shared prefix is often pages. That is why reuse helps so much.

The engine sees token ids

The tree does not store English. It stores token ids. Those two tickets look like this:

policy = [81, 14, 33, 90, 2, 77]          # the refund document

ticket_a = policy + [55, 12]              # "... request a refund?"
ticket_b = policy + [61, 8, 19]           # "... corporate card?"

[81, 14, 33, 90, 2, 77] is the shared prefix. Everything after that is unique.

Each token also has a KV slot — an index into GPU memory. After ticket A, those slots might be [400, 401, 402, 403, 404, 405, 406, 407]. Token 81 lives in slot 400, token 14 in 401, and so on.

Why not a hashmap of full prompts?

A natural first idea: store the whole prompt as a key.

cache[tuple(ticket_a)] = slots_a
cache[tuple(ticket_b)] = slots_b

cache.get(tuple(ticket_b))  # miss — the keys are not equal

Those two keys are different, so you get zero hits. The prompts share a prefix, but the map only matches exact lists.

You need a structure that can answer: what is the longest prefix of this new request that I have already computed?

That is a tree problem.

The radix tree

A radix tree (a compressed prefix tree) stores a sequence of tokens on each edge, plus the KV slots for those tokens.

class Node:
    tokens: list[int]          # this edge, not a single token
    next: dict[int, Node]      # first token of each child → child
    slots: list[int]           # slots[i] is the KV index for tokens[i]

After ticket A, the tree is one path:

root
└── [81, 14, 33, 90, 2, 77, 55, 12]  slots=[400…407]

When ticket B arrives, the walk matches [81, 14, 33, 90, 2, 77] and stops. The stored edge continues 55, the new prompt continues 61. One edge cannot hold both, so insert splits:

root
└── [81, 14, 33, 90, 2, 77]  slots=[400…405]     # policy, stored once
    ├── [55, 12]             slots=[406, 407]    # ticket A
    └── [61, 8, 19]          slots=[410, 411, 412]  # ticket B

In code, that split is: cut the old node at the mismatch, keep the prefix, hang the old tail and the new tail as siblings.

# node was [81, 14, 33, 90, 2, 77, 55, 12]; they share the first 6 tokens
cut = 6
old_tail = Node(
    tokens=node.tokens[cut:],     # [55, 12]
    slots=node.slots[cut:],       # [406, 407]
    next=node.next,
)
node.tokens = node.tokens[:cut]   # [81, 14, 33, 90, 2, 77]
node.slots = node.slots[:cut]
node.next = {55: old_tail, 61: Node(tokens=[61, 8, 19], slots=[410, 411, 412])}

A few details that matter:

Edges hold many tokens, not one. Fewer nodes, faster walks. That is the radix part.
Values are indices, not copies of the tensors. The bytes stay in a memory pool.
"Refund" and "refund" are different if they tokenize differently. The tree compares ids.

Matching: find the longest reusable prefix

A new request does not search for an exact prompt. It walks from the root and takes the longest path whose tokens match.

n, slots = longest_hit(ticket_b)
# n     == 6
# slots == [400, 401, 402, 403, 404, 405]

Ticket B can skip prefill for the policy and only compute [61, 8, 19].

Incoming:  [81, 14, 33, 90, 2, 77, 61, 8, 19]
Walk:      match × 6, stop (55 ≠ 61)
Result:    reuse the policy, prefill the question

That is a longest prefix match.

def longest_hit(tokens):
    node = root
    hit, slots = 0, []
    i = 0
    while i < len(tokens) and tokens[i] in node.next:
        child = node.next[tokens[i]]
        k = how_far_equal(child.tokens, tokens[i:])
        slots.extend(child.slots[:k])
        hit += k
        i += k
        if k < len(child.tokens):
            break          # mismatch in the middle of an edge
        node = child       # finished this edge, keep walking
    return hit, slots

It stops in two ways:

No child for the next token — nothing left to follow.
Mid-edge mismatch — still return the tokens that did match.

A third ticket over a shipping policy starts with different ids. Hit length is 0. You prefill the whole prompt and insert a new branch from the root.

If everything matches — same thread, next user message — you skip almost all of prefill.

Two limits:

Tokens must be identical, in order, from the start. One different token and the walk stops.
Match length is often rounded to a page. Production KV is stored in pages (for example 16 tokens). A leftover 3-token tail may not be reusable until it fills a page. The idea is the same. The unit is just coarser.

After the request finishes, insert the new suffix so later tickets can reuse it too.

Eviction: the tree cannot keep everything

GPU memory is finite. When the next request needs KV slots and the pool is full, the cache has to free some.

SGLang's default for this is LRU — least recently used. When the GPU KV pool fills up, it evicts the least recently used leaf nodes first. That is --radix-eviction-policy lru. You can switch the heap to priority so low-priority leaves go first, and equal priority falls back to LRU. NVIDIA's Dynamo notes on SGLang describe the same split: LRU by default, priority as an option. That is an SGLang flag, not a property of every radix tree.

The constraint underneath both policies is the same: only evict a leaf that no live request is using.

A node is evictable when both are true:

nothing is running on that path (lock_ref / pin count is 0)
it has no children left (it is a leaf)

On this bot, after both tickets have finished:

root
└── [81, 14, 33, 90, 2, 77]     # policy — not a leaf, two children
    ├── [55, 12]                # ticket A — leaf
    └── [61, 8, 19]             # ticket B — leaf

The allocator needs room. Eviction looks at the two leaves, picks the colder one (ticket A, if B ran more recently), and frees those slots.

The policy trunk does not go in that same step. It still has a child, so it is not in the evictable set. Recency is not what saves it here. Being an interior node is.

After A's leaf is gone:

root
└── [81, 14, 33, 90, 2, 77]
    └── [61, 8, 19]             # ticket B — only leaf left

If the pool still needs more space, B's leaf goes next. Now the trunk has no children. It becomes a leaf. If nothing is pinned on it, the next eviction can take the policy too. That walk up the tree is how a prefix finally disappears — after every branch under it is gone, not by deleting a parent first.

While ticket B is still generating, the matched path is pinned. Eviction skips those nodes even if they look old. Otherwise a live request would lose the KV it is attending over.

One related point, not part of eviction itself: the scheduler can prefer waiting requests that already hit the tree. That keeps the hot trunk busy, so you evict stale questions instead of the policy. The tree only helps if the batcher feeds it hits.

What you feel as a user

A prefix hit does not change the answer. It changes the wait.

TTFT (time to first token) drops, because prefill is shorter.
Throughput goes up, because the GPU is not recomputing the same four-page policy all afternoon.
A cold request is unchanged. Walking the tree is cheap compared to attention.

The win is largest when many requests share a long, stable prefix. A unique one-off prompt will miss. That is expected.

A compact picture

Ticket A:  [ refund policy ][ days to request? ]
Ticket B:  [ refund policy ][ corporate card? ]
                 ▲ reused         ▲ computed

Tree:       [81, 14, 33, 90, 2, 77]
            ├── [55, 12]           # ticket A
            └── [61, 8, 19]        # ticket B

Keep the shared work in a tree. Match the longest prefix. Evict what went cold.

That is a radix cache.