As Large Language Models (LLMs) transition from research breakthroughs to the backbone of enterprise production environments, the focus of technical optimization has shifted from model architecture to the underlying serving infrastructure. While techniques such as quantization, pruning, and distillation have historically been the primary methods for reducing model size, the most significant bottleneck in modern high-concurrency environments is the management of the Key-Value (KV) cache. For long-context models, the KV cache often becomes the largest dynamic consumer of GPU memory, effectively dictating the limits of throughput and latency. Two specific architectural innovations—PagedAttention and RadixAttention—have redefined how serving engines handle this memory burden, transforming the economic and operational feasibility of deploying LLMs at scale.
The Architectural Crisis: Why the KV Cache Is the Real Bottleneck
In the autoregressive decoding process used by transformer-based models, text is generated one token at a time. To produce each new token, the model must attend to the representations of all previously generated tokens. These representations, stored as Key (K) and Value (V) vectors, are computationally expensive to regenerate at every step. Consequently, serving engines store these vectors in the GPU memory as the KV cache. While this eliminates redundant computation, it introduces a memory management crisis: the cache grows linearly with the sequence length.
For a modern model like the Llama-3 8B, which features 32 transformer layers, 8 KV heads, and a 128-dimensional head architecture, the memory requirements are substantial. Utilizing 16-bit precision (FP16), each token requires approximately 128 KiB of memory. In a scenario involving a 100,000-token context—a standard requirement for modern document analysis—the KV cache for a single request occupies nearly 12.8 GiB of GPU memory. When factoring in batching—where dozens of requests are processed simultaneously—the memory demand quickly exceeds the capacity of even high-end hardware like the NVIDIA H100, leading to "Out of Memory" (OOM) errors or severely restricted concurrency.
A Chronology of Innovation in LLM Serving
The evolution of KV cache management follows a distinct timeline of addressing specific inefficiencies within the inference pipeline.
- The Pre-2023 Era (Static Allocation): Early serving systems used contiguous memory allocation. For every request, the engine would reserve a block of memory equal to the model’s maximum context length. Because most responses are shorter than the maximum limit, up to 60-80% of reserved GPU memory remained unused, leading to massive internal fragmentation.
- September 2023 (The PagedAttention Breakthrough): Researchers from UC Berkeley introduced vLLM and the PagedAttention algorithm. Inspired by virtual memory in operating systems, this approach moved away from contiguous allocation, allowing memory to be managed in non-contiguous "pages."
- Early 2024 (The Rise of RadixAttention): As applications like Retrieval-Augmented Generation (RAG) and multi-turn chatbots became dominant, the industry identified a new inefficiency: redundant computation of identical prefixes. SGLang introduced RadixAttention to allow the system to "remember" and reuse previously computed KV states across different user requests.
PagedAttention: Resolving the Memory Allocation Crisis
The primary innovation of PagedAttention is the decoupling of the logical sequence from its physical storage. In traditional systems, if a sequence was expected to reach 2,048 tokens, the system would pre-allocate a contiguous block for 2,048 tokens. If the actual generation only reached 500 tokens, the remaining 1,548 slots were wasted.
PagedAttention solves this by dividing the KV cache into fixed-size blocks, typically containing 16 or 32 tokens. These blocks are mapped via a "block table," similar to how an operating system’s page table maps virtual memory to physical RAM.
Key Mechanisms of PagedAttention:
- On-Demand Allocation: Memory is only allocated when a block is filled. This eliminates internal fragmentation because no space is reserved for tokens that haven’t been generated yet.
- Physical Flexibility: Because the blocks are tracked via a table, they do not need to be adjacent in GPU memory. This eliminates external fragmentation, as the engine can utilize any free "page" regardless of its location.
- Copy-on-Write (CoW): PagedAttention enables efficient "branching." If a user requests multiple outputs from the same prompt (parallel sampling), the system points all requests to the same physical blocks for the prompt. Only when the outputs diverge does the system copy the block to create a new unique path.
Data from the original vLLM research indicates that PagedAttention can increase throughput by 2x to 4x compared to traditional systems like HuggingFace Text Generation Inference (TGI) by allowing significantly larger batch sizes on the same hardware.
RadixAttention: Tackling Redundant Computation
While PagedAttention optimized where the memory was stored, it did not address what was being computed. In production environments, many requests share identical prefixes—such as a 2,000-token system prompt or a long document in a RAG pipeline. Without RadixAttention, the model must perform the "prefill" phase (computing KV tensors) for that same 2,000-token prompt every single time a new user asks a question.
RadixAttention treats the KV cache as a persistent, searchable index. It utilizes a Radix Tree—a compressed trie data structure—to store token sequences. Each node in the tree represents a sequence of tokens and points to its corresponding KV cache blocks in memory.
The Operational Flow of RadixAttention:
- Prefix Matching: When a new request arrives, the engine traverses the Radix Tree to find the longest matching prefix already stored in the cache.
- Cache Hit and Reuse: If a match is found (e.g., a shared system prompt), the engine skips the computation for those tokens and simply links to the existing KV blocks.
- Incremental Update: The model only computes the "suffix" (the new part of the prompt). Once computed, this new sequence is added to the Radix Tree as a new branch, making it available for the next request.
This technique dramatically reduces the "Time to First Token" (TTFT). For a request with a 4,000-token shared prefix, RadixAttention can reduce the prefill latency from several seconds to a few milliseconds, as the "computation" is replaced by a simple memory pointer lookup.
Comparative Analysis: vLLM Hashing vs. SGLang Radix Trees
While both vLLM and SGLang (the primary proponent of RadixAttention) offer prefix caching, their underlying implementations differ. vLLM utilizes "Chain Hashing," where each KV block is assigned a hash based on its tokens and the hash of the preceding block. If a new request generates the same hash chain, the system identifies a cache hit.
In contrast, RadixAttention’s tree structure is more suited for complex branching scenarios, such as agentic workflows where a model might explore multiple reasoning paths. However, both systems achieve the same goal: transforming the KV cache from a temporary buffer into a reusable asset.
Security Implications: The Prefix Cache Side-Channel
The efficiency of prefix caching introduces a unique security consideration: the "cache side-channel." In a multi-tenant environment, if User B submits a prompt and receives a response with an exceptionally low TTFT, they could theoretically infer that User A (or another previous user) had submitted the same prompt recently.
To mitigate this, enterprise-grade serving engines are implementing "Cache Salting." By incorporating a tenant-specific or user-specific "salt" into the hash or tree lookup, providers ensure that User B can only hit the cache for prefixes they have personally used, preventing data leakage across different accounts while maintaining performance for individual users.
The Future of KV Management: Hierarchical and Distributed Caching
As context windows move toward the million-token mark (as seen in Google’s Gemini 1.5 Pro), even paged GPU memory is insufficient. The next frontier in serving technology is Hierarchical KV Caching. This involves a three-tier storage strategy:
- L1 (GPU Memory): Stores the active blocks for the current generation.
- L2 (Host RAM): Stores recently used but currently inactive prefixes.
- L3 (NVMe/Distributed Storage): Stores massive libraries of prefixes (e.g., entire books or codebases) that can be swapped into RAM as needed.
Additionally, "Cache-Aware Routing" is becoming a standard feature in load balancers. Instead of sending a request to the least-busy GPU, the load balancer identifies which GPU already has the required prefix in its Radix Tree and routes the request accordingly, maximizing the global cache hit rate.
Conclusion and Industry Impact
The transition from contiguous memory to PagedAttention and the shift from disposable caches to RadixAttention represent a fundamental maturing of the AI stack. These technologies move the needle from "making LLMs work" to "making LLMs affordable." For developers and enterprises, the implications are clear: the structure of prompts now directly impacts the cost and speed of the application. By using stable, reusable prefixes and leveraging engines like vLLM or SGLang, organizations can achieve a level of efficiency that was previously impossible, paving the way for more complex, long-context, and agentic AI systems.
