Overview: Eliminating redundant prefill computation across batched prompts using a Radix Tree (compact trie) in nanoGPT, the node-splitting algorithm, snapshotting intermediate KV cache tensors, and evaluating the core systems trade-off: trading GPU memory for prefill compute.
In real-world LLM serving applications, prompts submitted by users or agents frequently share extensive token prefixes:
In standard inference engines without prefix caching, each prompt in a batch of size $M$ independently prefills the entire prompt through all model layers from scratch:
$$\text{Prefill FLOPs} = M \times (\text{Prefix Length} + \text{Suffix Length})$$If 8 prompts share a 256-token system prompt, the GPU runs the linear transformations and attention layers for those 256 tokens 8 separate times, performing $8 \times 256 = 2,048$ token forward passes instead of 256!
A Radix Tree (compact trie) merges common prefix edges so that each unique prefix token chunk is represented by a single node:
[Root: Empty]
│
["You are a helpful AI..."] (Shared System Prompt: 256 tokens)
[KV Cache Snapshotted Here]
/ │ \
["Summarize X"] ["Translate Y"] ["Explain Z"] (Unique User Suffixes)
│ │ │
[Decode Tokens] [Decode Tokens] [Decode Tokens]
class RadixNode:
def __init__(self, tokens):
self.tokens = tokens # This node's token chunk (excludes ancestors)
self.children = {} # first token id of child chunk -> RadixNode
self.kv_cache = None # List of (cache_k, cache_v) tensors across all blocks
self.end_prompts = [] # Prompt indices ending exactly at this node
Unlike a naive trie that stores one token per node, a radix tree edges store variable-length token slices. When inserting a new prompt, if the prompt matches only a prefix of an existing child's token slice, the child node must be split:
This ensures maximal prefix compression with minimal tree depth.
The generation pipeline (`generate_radix_shared`) traverses the tree using Depth-First Search (DFS):
logits, _ = model(chunk, pos_offset=parent_len)
node.kv_cache = model.get_kv_cache()
| Device | Num Prompts | Independent Time | Radix-Shared Time | Speedup |
|---|---|---|---|---|
| CPU | 2 | 530.2 ms | 462.8 ms | 1.15x |
| CPU | 4 | 1011.9 ms | 1008.4 ms | 1.00x |
| CPU | 8 | 1927.1 ms | 1771.6 ms | 1.09x |
| CUDA | 2 | 158.0 ms | 162.8 ms | 0.97x |
| CUDA | 8 | 684.1 ms | 665.2 ms | 1.03x |
To isolate the prefill optimization, we kept output length small ($O=4$) and swept shared prefix length from 32 to 256 tokens:
| Device | Shared Prefix Length | Independent Time | Radix-Shared Time | Speedup |
|---|---|---|---|---|
| CPU | 32 | 572.5 ms | 494.2 ms | 1.16x |
| CPU | 128 | 1032.7 ms | 576.4 ms | 1.79x |
| CPU | 256 | 1524.5 ms | 752.3 ms | 2.03x |
| CUDA | 32 | 181.1 ms | 167.5 ms | 1.08x |
| CUDA | 128 | 207.5 ms | 175.8 ms | 1.18x |
| CUDA | 256 | 257.4 ms | 206.3 ms | 1.25x |
The Clear Trend: As the shared prefix length grows, independent processing scales linearly with $8 \times \text{prefix\_len}$. Radix-shared processing scales as $1 \times \text{prefix\_len}$. The speedup climbs monotonically to 1.25x on GPU and 2.03x on CPU.
Our benchmark uncovered a crucial architectural insight:
| Device | Strategy | Num Prompts | Peak Allocated VRAM |
|---|---|---|---|
| CUDA | Independent | 2 / 4 / 8 | 496.0 MB (Flat) |
| CUDA | Radix-Shared | 2 | 510.5 MB |
| CUDA | Radix-Shared | 4 | 521.7 MB |
| CUDA | Radix-Shared | 8 | 544.2 MB |