Radix trees
Identify reusable prompt prefixes, calculate saved prefill work and distinguish token savings from hit rates.
THE IDEA
Radix trees
A different way to find the longest shared prefix is a tree in which each path from the root spells a cached sequence, so shared beginnings are stored once. A radix tree additionally merges chains of single-child nodes into one edge, which keeps it small. Lookup walks down the tree as far as the new prompt matches.
└ 1
└ 2
└ 3
└ 4
└ 5
└ 6The tree is an index: it finds the longest shared prefix fast. Which entries to keep or evict is a separate policy; a safe evictable entry is a leaf, because removing an inner node would cut off the sequences below it.
Predict first. Does a tree lookup itself decide which GPU block to evict?
Chapter context
Prefix caching reuses compatible KV state for a repeated beginning of a prompt. A repeated suffix alone is not enough, because causal hidden states depend on the preceding context.
TRY IT YOURSELF
Part 1. Do it hands-on
Count nodes and edges for three sequences, then build a trie with longest-prefix lookup and leaf detection.
└ 1
└ 2
└ 3
└ 4
└ 5
└ 6The tree is an index: it finds the longest shared prefix fast. Which entries to keep or evict is a separate policy; a safe evictable entry is a leaf, because removing an inner node would cut off the sequences below it.
- To do: Cached sequences [1,2,3,4], [1,2,3,5] and [1,2,6]. In a plain tree with one node per token (the shared tokens stored once), how many nodes (not counting the root)?
- To do: A radix tree merges chains of single-child nodes into one edge. Edges are: [1,2], [3], [4], [5], [6]. How many edges?
- To do: The tree shows what is shared; it does NOT decide what to evict. If you evict by least-recently-used, which kind of node can be removed without breaking other cached sequences: a leaf, or a node with children? Type the word
Part 2. Do it in code
- new_trie(): an empty trie, represented as a dict of children (token → child dict).
- insert(trie, seq): add the sequence, creating nodes only where needed.
- longest_prefix(trie, seq): how many leading tokens of seq are stored in the trie.
- node_count(trie): the number of nodes (not counting the root).
- radix_edge_count(trie): the number of edges after merging chains of single-child nodes. A node is kept as a boundary if it has two or more children, no children (a leaf), or is the end of an inserted sequence; pass the set of full sequences stored as ends via the second argument.
- evictable_leaves(trie): the sequences (as tuples) of all leaf nodes. Only leaves can be removed without cutting off other cached sequences.
Stuck, or something not working? You can come back to it any time.
CHECK YOUR UNDERSTANDING
Does a tree lookup itself decide which GPU block to evict?
Chapter reference: math, worked example & code
This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.
Math and notation
A simple saved-token estimate is
where H is the number of hits reusing P prefix tokens. If all R requests contain P prefix and U unique tokens, the baseline prompt work is and the nominal fraction saved is . This models token work, not directly wall-clock speed.
Worked example
One hundred requests each contain a 500-token common prefix and a 300-token unique suffix. Eighty hits reuse the entire prefix. Saved prefill tokens are 80×500=40,000 out of 100×800=80,000 baseline tokens: 50% token work saved despite an 80% request hit rate. Cache lookup and new-output generation still take work.
Reference code
The following example uses the Python standard library and does not call a remote service.
requests,hits,prefix,unique=100,80,500,300
saved=hits*prefix
baseline=requests*(prefix+unique)
assert saved == 40000 and baseline == 80000
assert saved/baseline == .5
assert hits/requests == .8
Python examples are provided for study and local execution; this page does not execute Python.
Common mistakes
Textual similarity is not cache identity. A common suffix is not a common causal prefix. Hit rates need definitions and do not directly translate into end-to-end speedups.