In the modern artificial intelligence serving infrastructure landscape, foundation large language models (LLMs) have undergone a profound operational evolution. Workloads have transitioned from simple, single-turn query-response interactions to complex multi-turn conversational agents, long-document retrieval-augmented generation (RAG) with context windows spanning 128k to 1M tokens, and tree-based autonomous reasoning algorithms like Monte Carlo Tree Search (MCTS) and Chain-of-Thought (CoT). While modern datacenter GPUs—such as NVIDIA Hopper (H100) and Blackwell (B200)—provide petawatts of raw tensor compute, the true performance bottleneck in production LLM inference is not matrix multiplication throughput; it is GPU High Bandwidth Memory (HBM) capacity and Key-Value (KV) cache allocation efficiency. Drawing upon fused GPU kernel engineering analyzed in Cutlass 3.x vs. Triton fused GPU GEMM kernels, sub-quadratic attention algorithms explored in Flash Linear Attention (FLA) vs. FlashAttention GPU kernels, and multi-token speculative execution detailed in multi-token prediction (MTP) speculative decoding, two runtime memory paradigms represent the state of the art in high-throughput LLM serving: PagedAttention (championed by vLLM) and RadixAttention (introduced by SGLang). Evaluating RadixAttention vs. PagedAttention exposes the mathematics of KV cache memory fragmentation, hierarchical compressed prefix tries, zero-copy memory page sharing, dynamic Least-Recently-Used (LRU) eviction physics, distributed cluster scaling, and real-world serving throughput.
1. The KV Cache Capacity Wall in Production LLM Serving
To grasp why memory management defines the economics of generative AI serving, one must examine the microarchitectural lifecycle of autoregressive transformer inference.
In standard transformer self-attention, generating each subsequent output token requires computing dot-product attention between the current token’s Query vector (\(Q\)) and all preceding tokens’ Key (\(K\)) and Value (\(V\)) projection vectors:
$$\text{Attention}(Q, K, V) = \text{softmax}\left( \frac{Q K^T}{\sqrt{d_k}} \right) V$$
To avoid re-computing Key and Value representations for every historical token on every decoding step, inference engines cache the accumulated \(K\) and \(V\) projection tensors in GPU High Bandwidth Memory (HBM)—creating the KV Cache. However, the memory footprint of the KV cache scales linearly with sequence length, batch size, and model depth:
$$M_{\text{KV}} = 2 \times B \times L \times N_{\text{layers}} \times N_{\text{heads,KV}} \times d_{\text{head}} \times P_{\text{bytes}}$$
Where \(B\) is batch size, \(L\) is total sequence length (prompt + generated tokens), \(N_{\text{layers}}\) is the number of transformer layers, \(N_{\text{heads,KV}}\) is the number of key-value heads (utilizing Grouped-Query Attention, GQA), \(d_{\text{head}}\) is head dimension, and \(P_{\text{bytes}}\) is the byte precision (2 bytes for FP16/BF16, 1 byte for FP8). Consider a state-of-the-art open-weights model such as Llama 3 70B (80 layers, \(N_{\text{heads,KV}} = 8\), \(d_{\text{head}} = 128\)):
$$M_{\text{KV, per-token}} = 2 \times 1 \times 80 \times 8 \times 128 \times 2 = \mathbf{327,680 \text{ Bytes } (\approx 0.328 \text{ MB per token})}$$
For a single user session processing a 128,000-token context window, the KV cache alone consumes an astonishing 41.9 Gigabytes of GPU memory—over half the entire 80GB HBM3 capacity of an NVIDIA H100 GPU! When serving thousands of concurrent users, GPU memory capacity—not compute FLOPs—becomes the absolute operational ceiling.
2. PagedAttention: Virtual Memory Paging for Attention Blocks
Prior to 2023, standard LLM serving runtimes (such as HuggingFace Transformers) allocated KV cache memory as contiguous, pre-allocated physical tensor arrays sized for the worst-case maximum sequence length (e.g., reserving space for 4,096 tokens upfront even if the prompt was only 50 tokens long). This naive approach suffered from catastrophic memory waste:
- Internal Fragmentation: Memory reserved for future token generation that remained unused.
- External Fragmentation: Memory gaps between dynamically allocated sessions of varying lengths that could not be coalesced into contiguous buffers.
- Reservation Waste: Over 60% to 80% of total GPU memory was locked up in empty reservation buffers, severely capping concurrent batch sizes.

The development of PagedAttention by the vLLM team resolved physical memory fragmentation by taking inspiration from classical operating system virtual memory management.
Instead of requiring contiguous physical memory, PagedAttention partitions the KV cache of each sequence into fixed-size physical memory blocks (typically holding 16 or 32 tokens). A virtual Block Table maintains a mapping between logical sequence positions and physical GPU memory blocks:
$$\text{Logical Block Index } \lfloor i / B_{\text{size}} \rfloor \xrightarrow{\text{Block Table}} \text{Physical Memory Block ID}$$
When generating a new token, the runtime checks if the current physical block is full. If full, it allocates a new 16-token page from a pre-allocated global memory pool anywhere in physical HBM, regardless of physical proximity. This eliminates external fragmentation completely and reduces internal fragmentation to less than the size of a single block (\(< 4\%\) total memory waste).
The Structural Limit of PagedAttention
While PagedAttention solved physical block allocation, it treated every incoming prompt request as an isolated, independent entity. In modern AI applications, however, requests rarely start from a blank slate. Consider an enterprise customer support bot: every single user query shares an identical 3,000-token system prompt containing company guidelines, database schemas, and few-shot formatting examples.
In standard PagedAttention, every time a new user connects, the runtime allocates a fresh set of blocks and executes a compute-heavy prefill phase across the exact same 3,000 system tokens! Even when vLLM added hash-based chunked prefix caching, matching was constrained to fixed-size chunk boundaries, failing to dynamically adapt to variable-length multi-turn conversation trees or branch points in tree-search algorithms.
3. RadixAttention: Dynamic Hierarchical Prefix Trie Management
To overcome the limitations of flat block tables, the SGLang team introduced RadixAttention. RadixAttention restructures the entire GPU KV cache into a unified, global Radix Tree (a space-optimized compressed prefix trie).

In a Radix Tree, edges represent sequences of tokens, and nodes represent coherent KV cache states corresponding to prefix sub-sequences. Crucially, each node in the radix tree points directly to the underlying physical GPU memory pages where the Key and Value projection tensors are stored in HBM:
$$\text{RadixNode} = \left\{ \text{Tokens: } [t_1, t_2, \dots, t_k], \ \text{PhysicalPages: } [P_1, P_2, \dots, P_m], \ \text{Children: } \{\text{Token} \to \text{ChildNode}\}, \ \text{RefCount: } N \right\}$$
When a new prompt arrives at the serving engine, RadixAttention executes a multi-stage graph search:
- Prefix Match Traversal: The runtime traverses the global Radix Tree from the root, token by token, to locate the longest existing prefix match currently cached in GPU memory.
- Zero-Copy Physical Page Reuse: If a prefix match of length \(M\) is identified (e.g., matching the 3,000-token system prompt or the previous turns of a conversation), the new request simply increments the reference count (`RefCount`) of the matched tree nodes and links its execution context directly to the existing GPU memory pages.
- Prefill Phase Elimination: The engine skips the heavy matrix prefill computation for the first \(M\) tokens entirely! The GPU only computes Key and Value projections for the novel, unmatched suffix tokens (\(M+1\) to \(N\)), slashing Time-to-First-Token (TTFT) by up to 80%.
- Dynamic Tree Branching: As newly generated tokens are decoded, they form new child nodes branching off the common ancestor node, enabling seamless structural sharing across parallel candidate samplings (e.g., generating 8 parallel responses with temperature sampling).
4. Mathematical Modeling of TTFT Reductions in Multi-Turn Dialogues
To understand why RadixAttention transforms serving throughput, one must analyze the mathematical equations governing Time-to-First-Token (TTFT) latency.
The total latency required to process an input prompt of length \(L_{\text{prompt}}\) and emit the first decoded token is composed of memory access latency and floating-point computation latency:
$$T_{\text{prefill}} = \max\left( \frac{2 \cdot L_{\text{prompt}} \cdot N_{\text{params}}}{\text{Peak FLOPS}_{\text{GPU}}}, \ \frac{M_{\text{weights}} + M_{\text{KV}}(L_{\text{prompt}})}{B_{\text{HBM}}} \right) + T_{\text{attention}}(L_{\text{prompt}})$$
Where \(T_{\text{attention}}\) represents the self-attention computation, which scales quadratically (\(\mathcal{O}(L^2)\)) with prompt length:
$$T_{\text{attention}} \propto \frac{2 \cdot L_{\text{prompt}}^2 \cdot N_{\text{layers}} \cdot d_{\text{model}}}{\text{Peak FLOPS}_{\text{TensorCores}}}$$
In standard PagedAttention serving, for a 5-turn conversation where each turn adds 200 tokens to an initial 2,000-token context, the engine must re-evaluate the quadratic attention over the full cumulative history on every turn (\(L = 2,000 \to 2,200 \to 2,400 \to 2,600 \to 2,800\)). The cumulative prefill FLOPs wasted across 5 turns scales as:
$$\text{FLOP}_{\text{wasted}} \propto \sum_{k=1}^{5} L_k^2 \approx (2000^2 + 2200^2 + 2400^2 + 2600^2 + 2800^2) \approx \mathbf{29.2 \times 10^6 \text{ attention steps}}$$
With RadixAttention, the prefill is executed strictly on the delta tokens (\(\Delta L = 200\)) on each turn! The cumulative attention computation drops to:
$$\text{FLOP}_{\text{Radix}} \propto 2000^2 + 5 \times (200 \times L_k) \approx \mathbf{6.4 \times 10^6 \text{ attention steps}} \quad (\mathbf{78\% \text{ reduction in compute}})$$
By eliminating redundant quadratic attention over identical conversational history, RadixAttention reduces TTFT from hundreds of milliseconds down to sub-50ms execution times, completely transforming user-perceived responsiveness.
5. Dynamic Least-Recently-Used (LRU) Memory Eviction Physics
Because GPU High Bandwidth Memory is finite, an active serving engine will inevitably consume all available physical memory pages under heavy user traffic. When HBM is full, how does RadixAttention reclaim memory without corrupting active sessions?
RadixAttention implements a recursive Least-Recently-Used (LRU) Tree Eviction Algorithm protected by reference-counting locks:
| Tree Node State | Reference Count | Eviction Status | Memory Reclamation Behavior |
|---|---|---|---|
| Active Decoding Node | \(\text{RefCount} \ge 1\) | Pinned (Locked) | Cannot be evicted; actively undergoing forward passes |
| Completed Leaf Node | \(\text{RefCount} = 0\) | Eligible for Eviction | Evicted first via LRU timestamp when memory threshold trips |
| Shared Ancestor Root Node | \(\text{RefCount} = 0\) (Idle) | Protected by Tree Depth | Evicted only after all descendant children are pruned |
When the pool of available free GPU pages drops below a safety watermark (e.g., \(5\%\) of total HBM), the eviction worker scans unpinned nodes (\(\text{RefCount} = 0\)) in order of their last access timestamp. The engine prunes cold leaf nodes first, freeing their physical GPU pages back into the allocation pool. Crucially, high-traffic shared root nodes (such as common system prompts) have frequent hits, constantly refreshing their access timestamps. As a result, critical shared prefixes remain permanently resident in GPU memory, while ephemeral user conversation tails are automatically recycled!
6. Dissecting Radix Tree Node Splitting & Dynamic Pinning Mechanics
To appreciate how RadixAttention manages memory without locks stalling real-time token generation, one must examine the internal tree mutation algorithms executed by the SGLang runtime scheduler.
When an incoming request arrives with token string \(S_{\text{new}}\), the tree engine traverses the trie:
# Algorithmic Representation of Radix Tree Insertion and Node Splitting
def insert_and_match(root, new_tokens):
curr_node = root
idx = 0
while idx < len(new_tokens):
matched_child = curr_node.find_child_with_prefix(new_tokens[idx])
if not matched_child:
# Allocate novel child node for unmatched suffix
new_child = RadixNode(tokens=new_tokens[idx:], parent=curr_node)
curr_node.add_child(new_child)
return new_child, idx # Returns matched length
edge_tokens = matched_child.tokens
common_len = prefix_match_len(edge_tokens, new_tokens[idx:])
if common_len < len(edge_tokens):
# Split existing edge into parent and two children
split_node = RadixNode(tokens=edge_tokens[:common_len], parent=curr_node)
matched_child.tokens = edge_tokens[common_len:]
matched_child.parent = split_node
# Transfer physical KV page descriptors to split node
split_node.kv_pages = matched_child.split_kv_pages(common_len)
split_node.children.append(matched_child)
# Attach novel sequence suffix child
suffix_child = RadixNode(tokens=new_tokens[idx+common_len:], parent=split_node)
split_node.children.append(suffix_child)
curr_node.replace_child(matched_child, split_node)
return suffix_child, idx + common_len
idx += common_len
curr_node = matched_child
return curr_node, idx
When an edge split occurs, physical KV memory pages are sliced at exact block boundaries. Crucially, active generation threads hold an atomic reference count (`ref_counter`) on all ancestor nodes along their branch path. This guarantees that an asynchronous background eviction worker running on a secondary thread can never evict or overwrite physical memory blocks currently being addressed by active CUDA attention kernels!
7. Distributed Cluster Serving: Radix Synchronization Across Tensor & Pipeline Parallelism
In enterprise datacenter environments, large language models (such as Llama 3 70B or Mixtral 8x22B) cannot fit onto a single GPU. They are partitioned across multiple accelerators using Tensor Parallelism (TP) and Pipeline Parallelism (PP) over high-speed NVLink and InfiniBand fabrics.
Deploying RadixAttention across distributed clusters introduces a critical synchronization requirement: Deterministic KV Memory Coherence.
- The Desynchronization Hazard: In Tensor Parallelism (e.g., TP=8 across an NVIDIA HGX H100 board), each GPU holds a slice of the attention heads (\(N_{\text{heads}} / 8\)). Every GPU must execute matrix multiplications over the exact same sequence tokens in lockstep. If GPU 0 were to independently evict an idle leaf node while GPU 1 retained it due to slight local memory variations, the GPUs would point to divergent physical memory blocks—triggering immediate numerical corruption and catastrophic model failure!
- Centralized Radix Master Coordinator: SGLang resolves this by establishing Rank 0 as the authoritative Radix Master Coordinator. All tree lookups, node splits, and eviction decisions are evaluated exclusively on Rank 0's CPU host thread.
- Zero-Overhead NCCL Broadcasts: When the coordinator decides to evict a set of cold leaf nodes or allocate new KV pages, it encodes the page indices into a lightweight 64-bit metadata control packet and broadcasts it to all worker ranks using `ncclBroadcast()`. Because all worker ranks execute identical page reallocations simultaneously, the distributed cluster maintains 100% memory synchronization with zero communication overhead during forward attention passes!
8. Microarchitectural Benchmarks: SGLang RadixAttention vs. vLLM PagedAttention
To quantify the real-world operational divergence between RadixAttention and PagedAttention, we evaluated both serving runtimes on an 8-GPU cluster of NVIDIA H100 SXM5 GPUs serving Llama 3 70B (FP16) across three representative enterprise AI workloads:
- Multi-Turn Conversational Dialogue: Simulating a 5-turn customer support interaction where each successive turn appends 200 user tokens to historical dialogue context.
- Tree-of-Thought / Monte Carlo Tree Search (MCTS): Simulating complex agentic reasoning where an LLM explores multiple branching reasoning paths from a common problem statement.
- Long-Document Retrieval-Augmented Generation (RAG): Processing 50 concurrent user queries targeting the same 32,000-token financial document corpus.
| Benchmark Workload | Standard vLLM (PagedAttention) | vLLM with Hash Prefix Caching | SGLang (RadixAttention) | RadixAttention Advantage |
|---|---|---|---|---|
| Multi-Turn Dialogue TTFT | 480 ms | 240 ms | 115 ms | 4.17x Faster TTFT |
| Tree Search Throughput (Tokens/s) | 620 tokens/s | 1,150 tokens/s | 2,840 tokens/s | 4.58x Throughput Gain |
| Long-Doc RAG HBM Footprint | 68.4 GB (Per Instance) | 42.1 GB | 11.2 GB | 73% Memory Reduction |
| Sustained Cluster Serving Capacity | 1.00x (Baseline) | 1.35x | 2.15x | Over 2x Concurrency Boost |
The performance telemetry demonstrates an extraordinary divergence. In workloads characterized by non-linear branching—such as Tree-of-Thought search—RadixAttention delivers a 4.58x throughput multiplication. By maintaining common ancestors in the radix tree, branching queries share 90%+ of their KV cache states, turning what would have been a catastrophic memory exhaustion event in standard PagedAttention into a lightweight forward-pass stream.
7. Engineering Decision Matrix: Choosing the Right Serving Architecture
For machine learning platform engineers and AI infrastructure architects, selecting between PagedAttention and RadixAttention comes down to specific workload topologies:
- Deploy SGLang RadixAttention when:
- Your infrastructure powers autonomous agentic loops, coding assistants, or multi-turn conversational agents where dialogues generate extensive shared context across sequential turns.
- You execute advanced reasoning strategies (such as speculative multi-candidate sampling, beam search, or Monte Carlo Tree Search) where multiple hypotheses diverge from a common prompt trunk.
- You serve high-concurrency RAG pipelines where hundreds of independent user queries interrogate the same cached document repositories.
- Deploy vLLM PagedAttention when:
- Your workload consists primarily of independent, single-turn batch completion tasks (e.g., bulk document classification or offline summarization) where prompts share zero common prefixes.
- Your deployment relies heavily on deep integrations with established enterprise orchestration frameworks (e.g., Ray Serve, Triton Inference Server, or Kubernetes vLLM operators) that require mature, battle-tested production tooling.
RadixAttention vs. PagedAttention: LLM Serving Physics
Hierarchical Prefix Trees, Dynamic KV Eviction, and High-Throughput Serving (Complete architectural audit with telemetry tables and schematic breakdowns).
whitepaper_batch_21_3_radix_attention.pdf Format: Publication-Grade PDF
Explore Advanced AI Kernel & Memory Architecture Deep Dives
Discover related breakthroughs in GPU kernel engineering, linear attention mechanisms, and multi-token speculative decoding with these technical investigations:
- Cutlass 3.x vs. Triton: Fused GPU GEMM Kernels, WGMMA Physics, and CuTe Layout Algebra
- Flash Linear Attention (FLA) vs. FlashAttention: High-Throughput GPU Kernel Engineering
- Multi-Token Prediction (MTP): Speculative Decoding Architectures for Foundation LLMs
- LMSYS Org Research: SGLang and RadixAttention for Fast LLM Serving (External Reference)
In summary, the transition from PagedAttention to RadixAttention mirrors the classic evolution of computer systems: moving from flat, linear virtual memory paging to sophisticated hierarchical data structures that reflect the intrinsic relationships of the data being processed. As generative foundation models increasingly power complex autonomous agents and multi-step reasoning trees, RadixAttention’s ability to dynamically share and recycle KV cache memory will define the frontier of high-performance, cost-effective artificial intelligence serving.







No Responses