RadixAttention: Prefix-Aware KV Cache Reuse for 10x LLM Serving Throughput

Every token generated by a large language model carries a hidden cost: the entire KV cache for all preceding tokens must be resident in GPU memory. When thousands of requests share a common system prompt, few-shot examples, or conversation history, naive serving engines recompute identical prefixes from scratch for every request. SGLang's RadixAttention (Zheng et al., 2024) eliminates this redundancy through an elegant data structure choice: a radix tree over token sequences that enables automatic, fine-grained KV cache sharing across requests.

The Redundant Computation Problem

Consider a production LLM deployment handling multi-turn chat. A typical request carries:

[system prompt: ~500 tokens] + [few-shot examples: ~2000 tokens] + [conversation history: ~1000 tokens] + [new user message: ~50 tokens]

For 100 concurrent users sharing the same system prompt and few-shot examples, a naive serving engine computes the KV cache for those 2,500 shared tokens 100 separate times. At 30ms per 1K tokens of prefill on an A100, that is 7.5 seconds of wasted GPU compute per batch.

Existing solutions like PagedAttention (vLLM) solve memory fragmentation via paged allocation but do not address cross-request prefix sharing. Manual prompt caching requires explicit API annotations and cannot adapt to arbitrary sharing patterns.

Radix Trees: The Right Abstraction

A radix tree (also called a Patricia trie) is a compressed trie where single-child nodes are merged with their parents. RadixAttention repurposes this structure to index token sequences, where:

• Each edge represents a sequence of tokens
• Each node stores a pointer to the corresponding KV cache blocks in GPU memory
• Prefix matching is an O(L) traversal where L is the length of the query sequence

Root
├── [sys_prompt tokens 0..511] → Node A (KV blocks 0-3)
│   ├── [few_shot tokens 0..2047] → Node B (KV blocks 4-19)
│   │   ├── [user_1_history] → Node C (KV blocks 20-27)
│   │   └── [user_2_history] → Node D (KV blocks 20-25)
│   └── [different_few_shot] → Node E (KV blocks 4-11)
└── [different_sys_prompt] → Node F (KV blocks 0-5)

When a new request arrives, the scheduler traverses the radix tree to find the longest matching prefix. If the request shares the system prompt and few-shot examples with existing cache entries, it immediately reuses those KV blocks and only computes the novel suffix.

Core Algorithm

The RadixAttention runtime operates in three phases per request:

1. Prefix Matching

def match_prefix(radix_tree, token_ids):
    """Find longest cached prefix for a token sequence."""
    node = radix_tree.root
    matched_length = 0
    
    while matched_length < len(token_ids):
        # Find child edge matching next tokens
        child = node.find_child(token_ids[matched_length:])
        if child is None:
            break
        
        edge_tokens = child.edge_label
        # Check how many tokens on this edge match
        match_len = common_prefix_length(
            edge_tokens, 
            token_ids[matched_length:matched_length + len(edge_tokens)]
        )
        matched_length += match_len
        
        if match_len < len(edge_tokens):
            break  # Partial edge match
        node = child
    
    return matched_length, node.kv_cache_blocks[:matched_length // BLOCK_SIZE]

2. Selective Prefill

Only the unmatched suffix requires GPU computation. For a 3,500-token request where 2,500 tokens match cached prefixes, only 1,000 tokens go through prefill, a 71% reduction in compute.

3. Cache Insertion

After generating the KV cache for the novel suffix, the tree is updated:

def insert_into_tree(radix_tree, token_ids, kv_blocks):
    """Insert newly computed KV cache into the radix tree."""
    matched_len, matched_node = match_prefix(radix_tree, token_ids)
    remaining_tokens = token_ids[matched_len:]
    
    if len(remaining_tokens) == 0:
        return  # Already fully cached
    
    # Split edge if partial match occurred
    if needs_split(matched_node, token_ids, matched_len):
        split_node(matched_node, matched_len)
    
    # Insert new edge for the suffix
    new_node = RadixNode(
        edge_label=remaining_tokens,
        kv_cache_blocks=kv_blocks[matched_len // BLOCK_SIZE:]
    )
    matched_node.add_child(new_node)

LRU Eviction with Reference Counting

GPU memory is finite. RadixAttention implements eviction through a leaf-first LRU policy with reference counting:

• Active requests increment reference counts on their cached nodes
• Eviction only targets nodes with zero references (no active request uses them)
• Leaf nodes are evicted first, preserving shared prefixes that serve multiple branches
• When a node is evicted, its KV blocks are freed and the edge is removed from the tree

This naturally preserves the most-shared prefixes (system prompts) while evicting rarely-reused conversation tails.

Continuous Batching Integration

RadixAttention composes cleanly with continuous batching. The scheduler maintains a priority queue ordered by:

1. Requests with longest prefix matches (cheapest to process)
2. Requests whose matched prefixes have the most co-references (preserving hot cache entries)

This admission policy maximizes cache hit rates at the batch level:

def schedule_next_batch(pending_requests, radix_tree, max_batch_tokens):
    # Score each request by cache reuse potential
    scored = []
    for req in pending_requests:
        match_len, _ = match_prefix(radix_tree, req.token_ids)
        novel_tokens = len(req.token_ids) - match_len
        scored.append((novel_tokens, req))  # Lower novel tokens = higher priority
    
    scored.sort(key=lambda x: x[0])
    
    batch, total_tokens = [], 0
    for novel_len, req in scored:
        if total_tokens + novel_len > max_batch_tokens:
            break
        batch.append(req)
        total_tokens += novel_len
    
    return batch

Performance Characteristics

Benchmarks from the SGLang paper on multi-turn chat workloads (ShareGPT dataset, Llama-2-70B, 8xA100):

Metric	vLLM (PagedAttention)	SGLang (RadixAttention)	Improvement
Throughput (req/s)	2.1	8.4	4.0x
Median TTFT (ms)	1,840	312	5.9x
P99 TTFT (ms)	4,200	890	4.7x
Cache hit rate	0%	78%	—

For structured generation workloads (JSON schema constrained decoding with shared grammar prefixes), improvements reach 10x due to the highly repetitive prefix structure.

When RadixAttention Excels

The technique provides maximum benefit when:

• Multi-turn conversations: Each turn shares the full history prefix with the previous turn
• Shared system prompts: High-traffic deployments where thousands of requests share identical preambles
• Few-shot learning: The same examples prefix is reused across requests
• Tree-of-thought / branching: Multiple continuations from the same reasoning prefix
• Structured outputs: Constrained decoding with shared grammar state

It provides minimal benefit for single-turn, unique-prompt workloads where no prefix sharing exists.

Implementation Considerations

Token granularity vs. block granularity: RadixAttention operates at block boundaries (typically 16 or 64 tokens) rather than individual tokens. This trades slightly coarser matching for O(1) block operations and alignment with GPU memory allocation.

Hash-based edge lookup: Rather than comparing full token sequences, edges are indexed by a rolling hash of their first few tokens, making child lookup O(1) amortized.

Copy-on-write semantics: When a cached prefix is extended by a new request, the tree uses copy-on-write for the KV blocks at the split point, avoiding data corruption from concurrent reads and writes.

Multi-GPU sharding: The radix tree is replicated across all GPUs in a tensor-parallel group. Since all GPUs process the same token sequence, prefix matching decisions are consistent without cross-GPU coordination.

Comparison with Explicit Prompt Caching

Cloud providers now offer explicit prompt caching APIs (e.g., cache breakpoints in the prompt). RadixAttention differs in a fundamental way: it requires zero user annotation. The sharing pattern is discovered automatically from the workload, adapts dynamically as traffic patterns change, and works for arbitrary prefix overlap, not just pre-declared cache boundaries.

This automatic approach also captures sharing patterns that humans would not annotate, such as partial overlaps between different system prompts or shared reasoning chains across unrelated requests.

Implications for System Design

RadixAttention demonstrates a broader principle: the right data structure can eliminate entire categories of systems problems. By modeling KV cache sharing as a prefix tree problem, it transforms a memory management challenge into a traversal algorithm with well-understood complexity bounds. For engineers building inference systems, the lesson is to look for structural sharing in workloads before reaching for brute-force solutions like simply adding more GPUs.