RadixAttention indexes cached GPU KV-cache blocks in a compressed prefix trie (Radix Tree) with LRU eviction, enabling zero-copy prefix sharing across concurrent and sequential LLM requests.
TL;DR30-second simplified summary▾
In production LLM workloads—multi-turn chat, RAG pipelines, agent tool-use loops, and few-shot prompting—requests repeatedly share long token prefixes (e.g., a 4,000-token system prompt + tool schema). Recomputing the Key-Value (KV) tensors for those prefix tokens on every request wastes massive GPU HBM bandwidth and inflates Time-To-First-Token (TTFT).
RadixAttention (pioneered in SGLang and vLLM Automatic Prefix Caching) replaces per-request ephemeral KV buffers with a persistent Radix Tree (compressed prefix trie) in GPU HBM. Each edge represents a sequence of token IDs pointing to physical PagedAttention KV blocks, annotated with a reference count (ref_count) and last-access timestamp.
When a new prompt arrives, the scheduler traverses the Radix Tree to find the longest matching prefix in O(prompt_len), increments ref_count on those shared physical pages (zero-copy!), and only runs prefill compute on the divergent user suffix. Completed pages with ref_count == 0 remain cached in HBM and are evicted lazily via leaf-first LRU only when GPU memory is needed.
From patterns to decisions.
Eliminate redundant quadratic prefill compute and cut Time-To-First-Token (TTFT) by sharing immutable KV-cache pages in a reference-counted Radix Tree.
Why Identical Token Prefixes Produce Bit-Identical KV Tensors.
In a causal decoder-only Transformer, token i's Key and Value vectors (K_i, V_i) depend strictly on tokens 0..i and never on tokens > i.
Therefore, if Request A and Request B share an identical prefix of 2,048 tokens (with identical LoRA adapter and positional encoding), their first 2,048 KV vectors are mathematically identical—allowing 100% zero-copy reuse.
Causal Mask Prefix Invariance
1.Stage Objective: Understand the mathematical property of causal masking that makes prefix KV sharing exact.
2.Level (Foundation): In a causal decoder-only Transformer, token `i`'s Key and Value vectors (`K_i, V_i`) depend strictly on tokens `0..i` and never on tokens `>
3.Operational Invariant: Causal attention guarantees prefix KV tensors are independent of any divergent suffix tokens.
Caption: Causal attention guarantees prefix KV tensors are independent of any divergent suffix tokens.
Compressed Prefix Trie Mapping Token Edges to Physical KV Pages.
Each node in the Radix Tree represents a contiguous span of cached tokens mapped to fixed-size GPU KV pages (e.g., 16 tokens/page). When a new prompt diverges mid-edge (e.g., matching 1,000 of 1,500 tokens on an edge), the engine splits the edge at token 1,000 into a shared parent node and two child branches—without copying any GPU tensors.
Radix Tree Prefix Splitting
1.Stage Objective: See how a Radix Tree merges linear chains and splits nodes dynamically on divergent suffixes.
2.Level (Foundation): Each node in the Radix Tree represents a contiguous span of cached tokens mapped to fixed-size GPU KV pages (e.g., 16 tokens/page). When a n
3.Operational Invariant: Splitting a tree edge on divergent suffixes shares parent KV pages with zero GPU memory copies.
Caption: Splitting a tree edge on divergent suffixes shares parent KV pages with zero GPU memory copies.
Reference Counting & Leaf-First LRU Eviction.
Active requests pin their matched prefix path by incrementing ref_count += 1 on every ancestor node, preventing eviction mid-generation. When a request finishes, ref_count decrements.
Only leaf nodes with ref_count == 0 sit in the LRU eviction queue; evicting a leaf frees its KV pages and may turn its parent into an evictable leaf.
Leaf-First LRU Eviction
1.Stage Objective: Manage finite GPU HBM safely across active requests and cached idle prefixes.
2.Level (Intermediate): Active requests pin their matched prefix path by incrementing `ref_count += 1` on every ancestor node, preventing eviction mid-generation. W
3.Operational Invariant: Active requests pin shared nodes via ref_count > 0 while idle leaves evict in LRU order.
Caption: Active requests pin shared nodes via ref_count > 0 while idle leaves evict in LRU order.
Implementing Longest-Prefix Match & Node Splitting.
from dataclasses import dataclass, field
@dataclass
class RadixNode:
tokens: tuple[int, ...]
kv_page_ids: list[int]
ref_count: int = 0
children: dict[int, 'RadixNode'] = field(default_factory=dict)
class RadixPrefixCache:
def __init__(self) -> None:
self.root = RadixNode(tokens=(), kv_page_ids=[])
def match_prefix(self, prompt_tokens: tuple[int, ...]) -> tuple[list[int], int, list[RadixNode]]:
if not prompt_tokens:
return [], 0, []
node = self.root
idx = 0
matched_pages: list[int] = []
pinned_nodes: list[RadixNode] = []
while idx < len(prompt_tokens):
first_tok = prompt_tokens[idx]
child = node.children.get(first_tok)
if child is None:
break
common = 0
limit = min(len(child.tokens), len(prompt_tokens) - idx)
while common < limit and child.tokens[common] == prompt_tokens[idx + common]:
common += 1
if common < len(child.tokens):
# Partial edge match: caller stops at split boundary
break
matched_pages.extend(child.kv_page_ids)
child.ref_count += 1
pinned_nodes.append(child)
idx += common
node = child
return matched_pages, idx, pinned_nodesPrefix Match & Pinning Flow
1.Stage Objective: Write the core Radix Tree prefix-matching and reference-pinning logic.
2.Level (Intermediate): from dataclasses import dataclass, field
3.Operational Invariant: Longest-prefix traversal pins matched nodes in O(prompt_len) and returns reusable GPU page IDs.
Caption: Longest-prefix traversal pins matched nodes in O(prompt_len) and returns reusable GPU page IDs.
Longest-Prefix-First Scheduling vs. FCFS Starvation.
In a busy queue, FCFS execution can thrash the LRU cache if unrelated prompts interleave. Longest-Prefix-First (LPF) scheduling batches requests sharing the same active Radix branch together, maximizing KV reuse.
To prevent starvation of unique prompts, pair LPF with an aging boost so requests waiting > max_wait_ms promote to the front.
Longest-Prefix-First with Aging
1.Stage Objective: Boost cache hit rates by reordering queued requests without starving unique prompts.
2.Level (Advanced): In a busy queue, FCFS execution can thrash the LRU cache if unrelated prompts interleave. **Longest-Prefix-First (LPF)** scheduling batches
3.Operational Invariant: Grouping queued prompts by shared prefix boosts hit rates while aging prevents tail starvation.
Caption: Grouping queued prompts by shared prefix boosts hit rates while aging prevents tail starvation.
Page-Boundary Alignment & Tiered CPU-DRAM Offloading.
PagedAttention aligns KV blocks to fixed sizes (e.g., 16 tokens). Partial trailing tokens (< 16) are either recomputed or padded at system-prompt boundaries.
When GPU HBM fills, hot evicted KV pages can asynchronously offload over PCIe/NVLink to CPU DRAM (L2 KV Cache) rather than discarding them, reloading 5x faster than cold prefill.
GPU HBM -> CPU DRAM KV Tiering
1.Stage Objective: Handle unaligned token boundaries and extend cache capacity beyond GPU HBM.
2.Level (Advanced): PagedAttention aligns KV blocks to fixed sizes (e.g., 16 tokens). Partial trailing tokens (< 16) are either recomputed or padded at system-p
3.Operational Invariant: Async PCIe offload preserves evicted prefix pages in CPU DRAM for fast reload on future hits.
Caption: Async PCIe offload preserves evicted prefix pages in CPU DRAM for fast reload on future hits.
Preventing Cross-Tenant Cache Leaks & Timing Side Channels.
Sharing a global Radix Tree without tenant isolation exposes a subtle TTFT timing side channel: Tenant B can probe whether Tenant A recently sent a secret system prompt by measuring faster TTFT on a cache hit! Always salt every Radix Tree root or block hash with tenant_id (and lora_id) so cross-tenant sharing is strictly disabled.
Tenant-Salted Radix Isolation
1.Stage Objective: Isolate cached KV prefixes across tenants in shared inference clusters.
2.Level (Advanced): Sharing a global Radix Tree without tenant isolation exposes a subtle **TTFT timing side channel**: Tenant B can probe whether Tenant A rece
3.Operational Invariant: Prefixing keys with tenant_id + lora_id eliminates cross-tenant TTFT timing side channels.
Caption: Prefixing keys with tenant_id + lora_id eliminates cross-tenant TTFT timing side channels.
Practice: Make the trade-off yourself.
Why must only leaf nodes with `ref_count == 0` be evicted from the RadixAttention LRU queue?