PagedAttention vs RadixAttention: How LLMs Tame the KV Cache

KV cache management has become one of the most consequential engineering problems in production LLM deployment. As context windows extend and multi-turn workloads proliferate, the cache that stores key and value tensors between decoding steps consumes GPU memory at a rate that directly caps concurrency and throughput. Two architectural approaches — PagedAttention and RadixAttention — attack this constraint from different angles.

The Memory Arithmetic Behind the Problem

The per-token KV cache footprint is determined by four variables: transformer layers (L), KV heads (H_kv), head dimension (D), and bytes per value (B, equal to 2 for FP16). For a Llama-3 8B-class model with 32 layers, 8 KV heads, 128-dimensional heads, and FP16 precision, each token occupies approximately 128 KiB of KV cache. A 100,000-token context therefore demands nearly 12.8 GiB before any batching overhead.

The waste manifests as two distinct pathologies. Internal fragmentation occurs when a request reserves thousands of token slots but generates a short response, leaving the allocated region mostly idle. External fragmentation occurs as requests of varying lengths complete and leave scattered gaps that are individually too small to satisfy new allocations. Separately, workloads with shared system prompts force the prefill stage to recompute identical KV tensors for every new request — inflating Time to First Token (TTFT) with no benefit.

PagedAttention: Paged Memory for KV Tensors

PagedAttention, introduced in 2023, resolves the allocation problem by borrowing the operating system's page-table abstraction. Rather than reserving one contiguous buffer per request, the serving engine divides the KV cache into fixed-size blocks — typically 16 or 32 tokens — and allocates them incrementally as generation proceeds. Each request maintains a block table mapping logical block IDs to physical locations anywhere in GPU memory, so the attention kernel can reconstruct a logically contiguous sequence from physically scattered pages.

A request generating 60 tokens occupies only the blocks required for those 60 tokens. When multiple requests share the same prompt prefix, they reference the same physical KV blocks. Divergence triggers a copy-on-write: the shared block is duplicated only at the point where the two sequences begin to differ, making beam search and parallel sampling substantially cheaper in memory terms. PagedAttention changes nothing about the attention algorithm or model outputs — its entire contribution is architectural, replacing the contiguous allocator with a paged one.

RadixAttention: Prefix Cache as a Searchable Index

PagedAttention does not prevent recomputation of identical prefixes — it only ensures that whatever KV tensors are computed are stored without fragmentation. RadixAttention, introduced in SGLang, addresses the recomputation problem by treating completed requests as persistent cache entries rather than discarding them.

The mechanism is a radix tree — a compressed trie where each edge represents a token sequence. When a new request arrives, the serving engine traverses the tree to find the longest matching prefix, loads those KV tensors directly, and runs prefill only on the unmatched suffix. If 1,900 tokens of a 2,000-token prompt already exist in the tree, the model computes only the remaining 100 tokens. After prefill, the newly computed suffix is inserted back into the tree for subsequent requests. Because GPU memory is finite, eviction follows a leaf-first, least-recently-used policy that protects shared interior nodes while reclaiming branches used least recently. The primary observable effect is lower TTFT, not reduced memory footprint.

vLLM achieves semantically equivalent behaviour through chain hashing rather than a radix tree. Each completed KV block receives a hash derived from its parent block's hash, its own token IDs, and optional metadata such as a LoRA ID. Identical token sequences produce identical hash chains, enabling cache lookups without tree traversal. Both systems skip prefill for matched prefixes and produce no change in model outputs.

Comparison, Security Surface, and Serving Stack Implications

Prefix caching introduces a security consideration for multi-tenant deployments. If one user's cached prefix causes a measurably faster TTFT for a second user submitting the same prompt, the cache becomes a timing side-channel. Modern serving frameworks counter this with cache salting: the hash or tree key incorporates a tenant-specific salt, so identical prompts from different tenants produce different cache identifiers and never share KV blocks. Single-tenant and self-hosted deployments are unaffected, but shared cloud infrastructure requires salting to prevent cross-tenant information leakage. This is one of the less-discussed operational concerns when automating LLM prompt optimization in production — prefix structure now has both performance and security dimensions.

As context windows extend into hundreds of thousands of tokens, neither technique alone keeps the KV cache inside GPU DRAM. The serving stack is evolving toward hierarchical caching across GPU HBM, host RAM, and distributed storage, and toward cache-aware routing that directs consecutive conversation turns to the replica already holding the relevant KV blocks rather than distributing by load alone. These extensions treat KV state as a first-class distributed resource — a shift that reframes inference infrastructure closer to storage system engineering than to pure ML operations.