radixattentionsglangkv-cachellm-inferencetutorial
RadixAttention: Tree-Structured KV Cache Guide for 2026
The Problem: The Inefficiency of Linear KV Caching in Multi-Turn and Branching AI
In modern AI agent frameworks, autonomous data pipelines, and interactive workspaces like AiFetchly, generative workloads rarely consist of isolated, single-turn prompts.
Instead, production applications exhibit complex branching access patterns:
- Multi-Turn Conversational Chains: User turns continuously append new queries to historical conversation turns, re-sending the same system prompt, tool definitions, and chat logs.
- Tree-of-Thought & Reasoning Search: High-accuracy reasoning workflows generate multiple competing hypothesis branches (e.g., self-consistency sampling, Monte Carlo Tree Search, or parallel tool calls) from the exact same prefix.
- Few-Shot Examples and Static System Context: Thousands of independent user requests share identical system instructions, API documentation, or few-shot demonstration tables.
Why Standard PagedAttention and Linear Caching Break Down
While PagedAttention (popularized by early vLLM versions) resolved physical GPU memory fragmentation by mapping non-contiguous virtual memory blocks, it historically treated KV cache allocation through a flat, linear lens.
Traditional serving systems employ basic hash-based prefix caching that matches linear token prefixes from left to right. When deployed across complex agentic workloads, this linear paradigm breaks down:
- Inability to Branch Dynamically: When an agent explores two alternate reasoning pathways (Branch A vs. Branch B), a linear cache cannot easily track the shared fork point. If the context diverges slightly, subsequent common suffix tokens must be recomputed from scratch.
- Coarse Cache Eviction: Linear caches treat sessions as monolithic blocks. When GPU memory pressure spikes, the eviction engine must evict either an entire conversation history or arbitrary recent blocks, prematurely evicting expensive system prompts and shared tool schemas.
- Redundant Prefill Overhead: In a 10-step agent loop, the agent re-computes the initial system prompt and tool definitions on every single iteration, wasting up to 80% of GPU compute solely recalculating known Key-Value states.
The Architecture: Radix Trees for KV Cache Organization
To unlock full memory sharing across arbitrary conversational trees, the team behind SGLang introduced RadixAttention.
Rather than storing cached tokens in a flat hash map, RadixAttention organizes the entire GPU Key-Value cache as a Radix Tree (compact prefix trie) where each edge represents a sequence of tokens, and each tree node references physical GPU page blocks.
The Three Operational Mechanics of RadixAttention
- Prefix Matching and Zero-Computation Reuse: When a new prompt arrives, the serving engine tokenizes the input and traverses the radix tree from the root. If a matching prefix path is discovered, the engine retrieves the pre-computed KV cache page pointers directly from the tree nodes. The model skips the prefill phase entirely for those tokens, slashing Time-to-First-Token (TTFT) from hundreds of milliseconds down to near-zero latency.
- Dynamic Edge Splitting: When a prompt shares an initial prefix with an existing edge but diverges partway through, RadixAttention automatically splits the edge:
- A new parent node is created containing the common token prefix and its corresponding GPU memory blocks.
- Two child branch nodes are spawned—one preserving the original branch and one accommodating the new divergent prompt.
- This structural mutation occurs entirely in CPU metadata without copying or modifying the underlying GPU VRAM pages.
- Reference Counting with LRU Eviction: Every node in the radix tree maintains an active reference counter ($\text{ref_count}$):
- When a request is actively generating tokens, all nodes along its prefix path have $\text{ref_count} > 0$ and are strictly pinned in GPU VRAM.
- Once a request finishes, the reference counts decrement back to zero, but the memory blocks remain resident in the tree.
- When GPU memory capacity is reached, an automated Least Recently Used (LRU) eviction walker prunes unreferenced leaf nodes ($\text{ref_count} == 0$), recycling physical GPU pages while preserving highly frequented root nodes (such as enterprise system prompts and tool schemas).
Comparing KV Cache Memory Architectures
| Feature / Metric | Traditional Linear Cache | PagedAttention (vLLM v1) | RadixAttention (SGLang) |
|---|---|---|---|
| Data Structure | Flat contiguous buffer | Virtual memory page table | Radix Tree (Compact Prefix Trie) |
| Branching Support | None (1:1 request mapping) | Manual cloning required | Native multi-branch & tree reuse |
| Multi-Turn Cache Hit Rate | Low to moderate (~30%) | Moderate (~55%) | Exceptional (85% – 95% on agent loops) |
| Edge Splitting | Unsupported | Unsupported | Instant zero-copy metadata split |
| Eviction Granularity | Full sequence eviction | Linear block LRU | Hierarchical leaf-first LRU eviction |
| TTFT on Follow-up Turns | High (Reprocesses past turns) | Moderate | Instant (< 15ms zero-prefill reuse) |
Implementation: Building a Working RadixAttention Tree in Python
Let us implement a complete Python simulation of a RadixAttention cache manager demonstrating prefix matching, dynamic edge splitting, reference counting, and LRU leaf eviction.
Step 1: Define the Radix Tree Node and Page Metadata
import time
from typing import List, Dict, Optional, Tuple
class RadixNode:
def __init__(self, token_slice: List[int], page_ids: List[int], parent: Optional['RadixNode'] = None):
self.token_slice: List[int] = token_slice
self.page_ids: List[int] = page_ids # Physical GPU page block indices
self.parent: Optional['RadixNode'] = parent
self.children: Dict[int, 'RadixNode'] = {} # Keyed by the first token of child's slice
self.ref_count: int = 0 # Number of active requests reading this node
self.last_accessed: float = time.perf_counter()
@property
def is_leaf(self) -> bool:
return len(self.children) == 0
def touch(self):
self.last_accessed = time.perf_counter() Step 2: Implement the RadixAttention Tree Manager
class RadixAttentionManager:
def __init__(self, total_gpu_pages: int = 100):
self.root = RadixNode(token_slice=[], page_ids=[])
self.total_gpu_pages = total_gpu_pages
self.allocated_page_counter = 0
def _allocate_pages(self, count: int) -> List[int]:
pages = list(range(self.allocated_page_counter, self.allocated_page_counter + count))
self.allocated_page_counter += count
return pages
def match_prefix(self, tokens: List[int]) -> Tuple[List['RadixNode'], int]:
"""Traverses tree to find longest matching prefix. Returns (matched_nodes, matched_token_count)."""
curr = self.root
matched_nodes = []
token_idx = 0
while token_idx < len(tokens):
first_tok = tokens[token_idx]
if first_tok not in curr.children:
break
child = curr.children[first_tok]
child_tokens = child.token_slice
# Compare token by token along the edge
common_len = 0
while (common_len < len(child_tokens) and
token_idx + common_len < len(tokens) and
child_tokens[common_len] == tokens[token_idx + common_len]):
common_len += 1
if common_len == len(child_tokens):
# Full edge matched
matched_nodes.append(child)
token_idx += common_len
curr = child
else:
# Partial match -> edge must split
token_idx += common_len
break
return matched_nodes, token_idx
def insert_prompt(self, tokens: List[int]) -> Tuple[List[int], int]:
"""
Inserts a prompt into the radix tree.
Returns: (all_page_ids, reused_token_count)
"""
matched_nodes, matched_tokens = self.match_prefix(tokens)
# Collect existing pages from matched nodes
reused_pages = []
curr = self.root
for node in matched_nodes:
node.touch()
reused_pages.extend(node.page_ids)
curr = node
remaining_tokens = tokens[matched_tokens:]
if not remaining_tokens:
return reused_pages, matched_tokens
# Check if we diverged mid-edge in a child node
first_tok = remaining_tokens[0]
if first_tok in curr.children:
child = curr.children[first_tok]
# Find common prefix length
common_len = 0
while (common_len < len(child.token_slice) and
common_len < len(remaining_tokens) and
child.token_slice[common_len] == remaining_tokens[common_len]):
common_len += 1
# Split child edge
parent_slice = child.token_slice[:common_len]
child_slice = child.token_slice[common_len:]
parent_pages = child.page_ids[:common_len]
child_pages = child.page_ids[common_len:]
# Create intermediate split node
split_node = RadixNode(parent_slice, parent_pages, parent=curr)
split_node.children[child_slice[0]] = child
child.token_slice = child_slice
child.page_ids = child_pages
child.parent = split_node
curr.children[parent_slice[0]] = split_node
reused_pages.extend(parent_pages)
matched_tokens += common_len
remaining_tokens = remaining_tokens[common_len:]
curr = split_node
# Allocate new pages for genuinely new tokens
if remaining_tokens:
new_pages = self._allocate_pages(len(remaining_tokens))
new_leaf = RadixNode(remaining_tokens, new_pages, parent=curr)
curr.children[remaining_tokens[0]] = new_leaf
reused_pages.extend(new_pages)
return reused_pages, matched_tokens Step 3: Implement LRU Leaf Eviction
def evict_lru_leaf(self) -> bool:
"""Finds and evicts the unreferenced leaf node with the oldest timestamp."""
lru_node = None
oldest_time = float('inf')
# Depth-First Search for unreferenced leaves
def dfs(node: RadixNode):
nonlocal lru_node, oldest_time
if node.is_leaf and node.ref_count == 0 and node != self.root:
if node.last_accessed < oldest_time:
oldest_time = node.last_accessed
lru_node = node
for child in node.children.values():
dfs(child)
dfs(self.root)
if lru_node and lru_node.parent:
parent = lru_node.parent
first_tok = lru_node.token_slice[0]
del parent.children[first_tok]
print(f"[Eviction] Pruned leaf node with {len(lru_node.token_slice)} tokens (Pages freed: {len(lru_node.page_ids)})")
return True
return False Step 4: Run a Multi-Turn Branching Benchmark
def run_radix_benchmark():
manager = RadixAttentionManager(total_gpu_pages=1000)
# 1. System prompt (Shared by all user turns)
system_prompt = [101, 2045, 1024, 3056, 4012] # 5 tokens
# 2. Turn 1: User asks question A
turn_1_prompt = system_prompt + [5001, 5002, 5003] # 8 tokens total
pages_1, reused_1 = manager.insert_prompt(turn_1_prompt)
print(f"Request 1: Ingested {len(turn_1_prompt)} tokens -> Reused: {reused_1} tokens (Prefill: {len(turn_1_prompt) - reused_1} tokens)")
# 3. Turn 2: User follow-up in same conversation
turn_2_prompt = turn_1_prompt + [9001, 9002] # Continues conversation 1
pages_2, reused_2 = manager.insert_prompt(turn_2_prompt)
print(f"Request 2 (Follow-up): Ingested {len(turn_2_prompt)} tokens -> Reused: {reused_2} tokens (Prefill: {len(turn_2_prompt) - reused_2} tokens)")
# 4. Turn 3: Alternate branching query (e.g. Tree of Thought / Alternate user)
branch_prompt = turn_1_prompt + [8888, 8889] # Diverges from Turn 1
pages_3, reused_3 = manager.insert_prompt(branch_prompt)
print(f"Request 3 (Branch): Ingested {len(branch_prompt)} tokens -> Reused: {reused_3} tokens (Prefill: {len(branch_prompt) - reused_3} tokens)")
# 5. Simulate memory pressure eviction
manager.evict_lru_leaf()
run_radix_benchmark() Production Serving and Deployment Trade-offs in 2026
When architecting production LLM serving stacks with SGLang and RadixAttention:
- Prompt Engineering for Maximum Prefix Hit Rates: To maximize radix cache hit ratios, developers must enforce strict prompt canonicalization. Dynamic variables (such as timestamps, session UUIDs, and randomized user greetings) should always be placed at the end of the prompt. Placing a variable timestamp at the top of a prompt alters the root tokens, invalidating the entire subsequent radix tree.
- Ordered Tool Definitions: When defining Model Context Protocol (MCP) or JSON tool schemas, sort tool definitions deterministically (e.g., alphabetically by tool name). Non-deterministic tool serialization creates spurious branch splits that fragment GPU cache memory.
- SGLang vs. vLLM in 2026: For simple batch processing of independent single-turn documents, standard vLLM remains straightforward. For multi-turn conversational agents, complex agent loops, code completion infilling, and Tree-of-Thought reasoning engines, SGLang’s RadixAttention consistently delivers 3x to 5x higher serving throughput by eliminating redundant prefill computation.
Conclusion
RadixAttention represents a fundamental evolution in generative AI memory management. By structuring the Key-Value cache as a dynamic radix tree with zero-copy edge splitting and hierarchical LRU eviction, SGLang enables seamless, high-throughput prefix reuse across complex multi-turn chats and agentic workflows—delivering dramatic TTFT reductions and optimal GPU utilization at enterprise scale.