PagedAttention vs RadixAttention: Solving KV Cache Fragmentation and Redundancy

Large Language Model (LLM) inference is fundamentally constrained by GPU memory bandwidth and capacity. The key-value (KV) cache, which stores the attention states for previous tokens, grows linearly with sequence length. For long contexts, this cache dominates GPU memory usage, leading to two distinct engineering problems: memory fragmentation (wasted space within the physical memory) and context redundancy (duplicate storage of shared prefixes).

PagedAttention and RadixAttention address these problems using different mechanisms. PagedAttention treats the KV cache like virtual memory, eliminating fragmentation. RadixAttention treats the KV cache like a file system index, eliminating redundancy. Understanding both is essential for building high-throughput inference engines.

The Fragmentation Problem and PagedAttention

In traditional tensor-based frameworks (e.g., early PyTorch implementations), the KV cache is allocated as a contiguous block of memory. When a batch of requests generates sequences of varying lengths, the system must allocate memory for the maximum possible length for every request. This leads to severe external fragmentation, where holes of free memory exist between allocated blocks but are too small or non-contiguous to satisfy new allocation requests.

Consider a batch of 10 requests. If one request generates 4096 tokens and another generates 100, the framework might allocate space for 4096 tokens for both. The second request wastes significant memory. As requests terminate, they leave behind "holes" in the physical memory that are too small to fit new, large allocations, leading to Out-Of-Memory (OOM) errors despite available free memory. Contiguous allocation fails in practice because modern GPUs have limited memory bandwidth and capacity; you cannot simply "compact" memory on the fly without stalling the GPU.

PagedAttention solves this by introducing a block-based virtual memory abstraction. Instead of allocating a contiguous array, the KV cache is divided into fixed-size blocks (e.g., 16 or 64 tokens). Each request maintains a block table, which is an array of indices pointing to physical memory blocks. The block size is chosen as a trade-off: smaller blocks reduce internal fragmentation (unused space in the last block of a sequence) but increase metadata overhead, while larger blocks reduce overhead but waste more space per sequence.

# Conceptual representation of PagedAttention's block table
# Request A (length 50) maps to physical blocks [101, 102, 103]
# Request B (length 120) maps to physical blocks [205, 206, 207, 208, 209, 210]
block_table = {
    "request_A": [101, 102, 103],
    "request_B": [205, 206, 207, 208, 209, 210]
}

When a new token is generated, the kernel checks if the current block is full. If so, it allocates a new physical block from a free list and appends its index to the block table. This allows:

1. Dynamic Allocation: Memory is allocated only as needed.
2. Non-Contiguous Storage: Physical blocks do not need to be contiguous, eliminating external fragmentation.
3. Swapping: Blocks can be swapped to CPU memory if GPU memory is exhausted, similar to OS paging.

The mechanism relies on a custom CUDA kernel that gathers the KV tensors from non-contiguous physical blocks based on the block table indices before performing the attention computation. This indirection adds negligible overhead but drastically improves memory utilization efficiency. Note that while external fragmentation is eliminated, internal fragmentation still exists (the unused portion of the last block in any given sequence), but this is minimized by choosing an appropriate block size relative to average sequence lengths.

The Redundancy Problem and RadixAttention

While PagedAttention optimizes internal memory usage, it does not address external redundancy. In many inference workloads, such as multi-turn conversations or branching storylines, multiple requests share the same prefix.

For example, if 100 users ask the same question ("What is the capital of France?"), the KV cache for the prompt "What is the capital of France?" is computed and stored 100 times. This is wasteful because the attention states for these shared tokens are identical across all requests. In multi-turn chat or batched generation of similar prompts, this redundancy scales linearly with the number of concurrent users, quickly exhausting GPU memory.

RadixAttention addresses this by organizing the KV cache into a radix tree (prefix tree). In this structure, nodes represent tokens or blocks of tokens, and edges represent transitions. If two requests share a common prefix, their paths in the radix tree merge, and they share the same physical memory blocks for the overlapping portion.

Radix Tree Structure:
Root -> "What is the capital" (Shared Block 101)
       ├── of France?" -> "Paris" (Block 102)
       └── of Spain?" -> "Madrid" (Block 103)

In this example, the blocks for "What is the capital" are stored only once. Requests for France and Spain share Block 101 but diverge into separate blocks for the answer. This reduces memory usage proportionally to the degree of prefix sharing in the workload.

RadixAttention achieves this by maintaining a global radix tree of blocks. When a new request arrives, the system traverses the tree to find the longest matching prefix. If a match is found, the new request inherits the physical block references from the existing node. If not, new blocks are allocated. However, this comes at the cost of tree traversal complexity. Unlike the simple array indexing of PagedAttention, RadixAttention requires navigating a graph structure, which can introduce CPU overhead and requires careful synchronization when multiple threads access the tree concurrently.

Mechanism Comparison: Block Table vs. Radix Tree

The core difference lies in the data structure used to manage physical memory references.

PagedAttention is a prerequisite for RadixAttention. Without the block-based abstraction, sharing physical memory between requests would require complex byte-level offset calculations and synchronization. PagedAttention provides a coarse-grained, block-aligned view of memory, making it feasible to share entire blocks without worrying about misaligned accesses.

Engineering Tradeoffs

Implementing these techniques involves significant engineering complexity.

1. Kernel Complexity: PagedAttention requires a custom attention kernel that can gather data from non-contiguous memory locations. RadixAttention adds another layer: the kernel must handle tree traversal logic or rely on CPU-side management to resolve block references. This increases the risk of bugs and makes optimization harder.
2. Latency vs. Throughput: PagedAttention improves throughput by allowing larger batches, but the indirect memory access can slightly increase latency per token. RadixAttention reduces memory footprint, allowing even larger batches, but the tree traversal and reference counting add CPU overhead. In practice, RadixAttention shines in workloads with high prefix reuse (e.g., chatbots, code generation with common libraries).
3. Memory Overhead: Both methods introduce metadata overhead. PagedAttention requires storing the block table for each request. RadixAttention requires storing the tree structure, node counts, and reference counts. For short sequences, this overhead can negate the benefits.

Common Pitfalls

Engineers often overlook the subtle costs associated with these optimizations. A common mistake is ignoring the metadata overhead of RadixAttention for short sequences. If most requests are very short (e.g., < 10 tokens), the size of the tree nodes and reference counts can exceed the memory saved by sharing, leading to net memory inflation.

Another pitfall is assuming PagedAttention alone solves all memory issues. While it prevents OOM errors due to fragmentation, it does not prevent OOM due to total memory exhaustion. If the batch size is too large or sequences are too long, PagedAttention will simply swap blocks to CPU, causing severe performance degradation. Engineers must still carefully tune batch sizes and consider RadixAttention or other compression techniques when total memory capacity is the bottleneck.

Practical Takeaways

1. PagedAttention is foundational: It is now a standard requirement for any production-grade LLM serving engine to handle variable-length sequences efficiently.
2. RadixAttention is an optimization: It yields significant memory savings only in workloads with high context reuse, such as multi-turn chat or batched generation of similar prompts.
3. Choice depends on patterns: Evaluate your specific sequence length distribution and prefix sharing patterns. If reuse is low, the overhead of RadixAttention may not be justified.

FAQ

Does PagedAttention work with static batch sizes? Yes. While PagedAttention is often associated with dynamic batching (where batch size varies per step), it works perfectly with static batch sizes. It simply manages the memory for a fixed number of requests more efficiently than contiguous allocation, preventing internal and external fragmentation within that fixed set.

Is RadixAttention compatible with existing PagedAttention implementations? Yes. RadixAttention builds on top of the block-based abstraction provided by PagedAttention. It does not replace the block table mechanism but rather adds a layer of sharing on top of it. Many modern inference engines implement both, using PagedAttention for individual request management and RadixAttention for global prefix sharing.

How much memory overhead does the Radix tree add? The overhead depends on the tree structure and the number of unique prefixes. Typically, it involves storing node headers, parent pointers, and reference counts. For workloads with high prefix reuse, the memory saved by sharing blocks far outweighs the overhead. For workloads with low reuse, the overhead can be significant, potentially increasing memory usage by 5-10% compared to a pure PagedAttention setup without sharing.