Topic 03: Radix-Tree Shared-Prefix KV Cache Architecture

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.


1. The Problem: Redundant Prompt Prefill

In real-world LLM serving applications, prompts submitted by users or agents frequently share extensive token prefixes:

The Redundancy in Standard Independent Serving

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!


2. The Radix-Tree Architecture

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]

Node Structure (`RadixNode` in `radix_cache.py`)

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

3. The Node-Splitting Insertion Algorithm

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:

  1. Find the longest common prefix of length $j$ between the child's `tokens` and the incoming token slice.
  2. Create a new `split` node containing the first $j$ shared tokens: `split = RadixNode(child.tokens[:j])`.
  3. Truncate the existing child to keep only the remaining tokens: `child.tokens = child.tokens[j:]`.
  4. Attach `child` as a child of `split`: `split.children[child.tokens[0]] = child`.
  5. Attach `split` to the parent node.

This ensures maximal prefix compression with minimal tree depth.


4. Execution Flow: Prefill Once, Snapshot, and Fork

The generation pipeline (`generate_radix_shared`) traverses the tree using Depth-First Search (DFS):

  1. Restore Parent State: Before processing a node's tokens, restore the parent node's KV cache snapshot using `model.set_kv_cache(parent_cache)`.
  2. Forward Suffix Chunk: Pass `node.tokens` into the model with position offset `pos_offset = parent_len`:
    logits, _ = model(chunk, pos_offset=parent_len)
  3. Snapshot Node Cache: Snapshot the newly accumulated per-block KV cache tensors into the node:
    node.kv_cache = model.get_kv_cache()
  4. Decode Continuations: For all prompts terminating at this node (`end_prompts`), launch autoregressive decoding using the free first-token logits produced by the prefix forward pass.
  5. Recurse Children: Recurse into child branches, passing `node.kv_cache` as their base parent cache.

5. Empirical Benchmark Analysis & The Two Sweeps

Sweep 1: Effect of Number of Prompts (Prefix=64, Suffix=16, Output=16)

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
⚠️ Why was the speedup small in Sweep 1?
Notice that each prompt generated 16 output tokens. Autoregressive token decoding cannot be shared across prompts—each generated token requires its own distinct forward pass. When decoding 16 tokens across 8 prompts ($8 \times 16 = 128$ decode steps), the decode phase dominates the runtime. The prefill savings from sharing a short 64-token prefix were diluted by the identical decode cost.

Sweep 2: Isolating the Prefill Phase (Prompts=8, Suffix=16, Output=4)

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.


6. The Core Systems Trade-Off: Memory vs. Compute

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

7. Interview Takeaway & Soundbite

🎯 Interview Answer — "How does your radix-tree cache compare to production systems like SGLang or vLLM?"
“Our implementation operates as an offline radix tree over a static batch of prompts, demonstrating the core algorithmic gain: saving prefill FLOPs by snapshotting KV states. Production systems like SGLang's RadixAttention and vLLM's Chunked Prefill take this concept further into continuous serving. They maintain a global, dynamic radix tree in GPU memory across independent incoming HTTP requests, combining it with an LRU cache eviction policy and PagedAttention to discard stale branch caches when VRAM is tight.”