Modern LLMs rely on quantization, pruning, distillation, and faster attention kernels, but production performance often depends most on KV cache management. As context windows grow, the cache consumes significant GPU memory, limiting concurrency, throughput, and latency. Two breakthroughs transformed this challenge: PagedAttention improves memory allocation, while RadixAttention enables efficient prefix reuse.<\/p>\n
Together, these techniques make LLM serving faster and more memory-efficient. In this article, we examine how PagedAttention and RadixAttention work, why they matter, and how they enable high-performance LLM serving.<\/p>\n
Why the KV Cache Is the Real Bottleneck<\/h2>\n
Every transformer generates text one token at a time. For each new token, the model must attend to all previously generated tokens by using their key (K) and value (V) vectors. Recomputing these vectors at every step would make generation prohibitively expensive, so serving engines store them in memory as the KV cache. This cache eliminates redundant computation and makes autoregressive decoding practical, but it introduces a new challenge: memory consumption grows linearly with sequence length. For long-context models, the KV cache often becomes the largest dynamic consumer of GPU memory, determining how many requests can run simultaneously.<\/p>\n
Why memory becomes the limiting factor<\/h3>\n
The size of the KV cache depends on the model architecture and the number of tokens stored. The per-token memory requirement is:<\/p>\n
\n
<\/figure>\n<\/div>\n
Where:<\/p>\n
\n
\n\n
\n
Symbol<\/strong><\/th>\n
Meaning<\/strong><\/th>\n<\/tr>\n<\/thead>\n\n
\n
L<\/td>\n
Number of transformer layers<\/td>\n<\/tr>\n
\n
Hkv<\/td>\n
Number of KV heads<\/td>\n<\/tr>\n
\n
D<\/td>\n
Head dimension<\/td>\n<\/tr>\n
\n
B<\/td>\n
Bytes per value (2 for FP16)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
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 requires nearly 12.8 GiB of memory before considering batching or additional requests.<\/p>\n
The two fundamental problems<\/h3>\n
As GPU memory fills with KV tensors, serving systems encounter two distinct bottlenecks:<\/p>\n
\n
Memory fragmentation: <\/strong>This occurs when the system allocates KV memory inefficiently, leaving large portions of GPU memory unusable and reducing the number of concurrent requests.<\/li>\n
Redundant computation: <\/strong>Identical prompt prefixes are repeatedly prefetched and encoded, even though their KV states have already been computed.<\/li>\n<\/ul>\n
These problems are independent, and each inspired a different solution. PagedAttention addresses efficient memory allocation, while RadixAttention focuses on reusing previously computed KV cache across requests. Together, they define the foundation of modern LLM serving.<\/p>\n
PagedAttention: Solving the Memory Allocation Problem<\/h2>\n
By 2023, the industry identified the biggest inefficiency in LLM serving as the storage method of the KV cache rather than attention itself. The system allocated one large contiguous block of GPU memory to hold the entire KV cache for every request. Since the serving engine could not predict how long a response would be, it typically reserved space close to the model\u2019s maximum context length. Most of that memory remained unused throughout the request, drastically reducing the number of sequences that could be served simultaneously.<\/p>\n
The problem with contiguous allocation<\/h3>\n
Traditional allocation creates two forms of fragmentation:<\/p>\n
\n
Internal fragmentation:<\/strong> A request reserves thousands of token slots but generates only a small response, leaving most of the allocated memory idle.<\/li>\n
External fragmentation: <\/strong>As requests of different lengths finish, scattered gaps appear across GPU memory. Although the total free memory may be sufficient, it is no longer available as one contiguous block for new requests.<\/li>\n<\/ul>\n
The result is poor GPU utilization and lower throughput, even when plenty of memory technically remains available.<\/p>\n
How PagedAttention Works<\/h2>\n
The core idea behind PagedAttention is simple: allocate KV memory only when it is needed. Instead, the system divides the KV cache into fixed-size blocks (typically 16 or 32 tokens) rather than reserving one large contiguous buffer for an entire sequence. As generation progresses, new blocks are allocated only after the previous one becomes full, allowing memory to grow incrementally rather than being over-provisioned from the start.<\/p>\n
Step 1: Divide the KV cache into blocks<\/h3>\n
The system splits each sequence into equal-sized logical blocks, while the system can store the actual blocks anywhere in GPU memory.<\/p>\n
\n
<\/figure>\n<\/div>\n
Step 2: Use a block table for address translation<\/strong><\/h3>\n
Every request maintains a block table that maps logical block IDs to their physical locations in GPU memory. During attention, the kernel consults this table to gather the required keys and values, making the sequence appear continuous even though its data is physically scattered.<\/p>\n
In fact, this indirection draws inspiration from page tables in operating systems: the model operates on a logical sequence, while the serving engine manages physical placement.<\/p>\n
Step 3: Grow memory on demand<\/strong><\/h3>\n
Instead of allocating space for thousands of future tokens, PagedAttention expands the KV cache one block at a time.<\/p>\n
A request generating 60 tokens occupies only the blocks required for those 60 tokens. No memory is reserved for tokens that may never be produced, which dramatically reduces internal fragmentation.<\/p>\n
Step 4: Share blocks with copy-on-write<\/strong><\/h3>\n
One of the most powerful features of PagedAttention is block sharing. If multiple requests begin with the same prompt, they reference the same physical KV blocks instead of storing duplicate tensors.<\/p>\n
When two requests eventually diverge, the system copies the shared block only at the point of modification, a mechanism known as copy-on-write. This makes prefix sharing highly memory-efficient for beam search, parallel sampling, and concurrent requests with identical system prompts.<\/p>\n
Why this changed LLM serving<\/strong><\/h3>\n
PagedAttention does not change the attention algorithm or the model\u2019s outputs. Its innovation is purely architectural: it replaces inefficient contiguous allocation with a paged memory layout.<\/em> The result is dramatically lower memory waste, higher GPU utilization, and the ability to serve many more concurrent requests on the same hardware.<\/p>\n
RadixAttention: Solving the Prefix Reuse Problem<\/h2>\n
PagedAttention made GPU memory efficient, but it left another major inefficiency untouched: the system still recomputed identical prefixes for every new request. In real production workloads, requests are rarely independent. Thousands of users share the same system prompt, chat conversations repeatedly include their entire history, and agent workflows continuously append to an existing context. Consequently, the system spends much of the expensive prefill phase generating KV tensors that already exist.<\/p>\n
The authors introduced RadixAttention to eliminate this redundant computation by turning the KV cache into a searchable, reusable index rather than a temporary memory buffer.<\/p>\n
The key idea: Store prefixes in a radix tree<\/h3>\n
Instead of discarding KV tensors when a request finishes, RadixAttention retains them inside a radix tree a compressed trie where each edge represents a sequence of tokens. The system stores every unique prompt prefix once, while different requests branch only where their tokens begin to differ.<\/p>\n
\n
<\/figure>\n<\/div>\n
For example, three requests may begin with the same system prompt:<\/p>\n
System:<\/strong> You are a helpful assistant.User:<\/strong> What is AI?System: <\/strong>You are a helpful assistant.User:<\/strong> What is Machine Learning?System: <\/strong>You are a helpful assistant.User:<\/strong> What is Deep Learning?<\/pre>\n
Rather than storing three identical copies of the shared prefix, the radix tree keeps it once and creates separate branches only for the final user query.<\/p>\n
How prefix matching works<\/h3>\n
When a new request arrives, RadixAttention performs three operations:<\/p>\n
\n
Match:<\/strong> Find the longest token prefix already present in the radix tree.<\/li>\n
Reuse:<\/strong> Load the existing KV tensors for that matched prefix instead of recomputing them.<\/li>\n
Insert:<\/strong> Compute only the unmatched suffix and append it back into the tree for future requests.<\/li>\n<\/ol>\n
\n
<\/figure>\n<\/div>\n
The longer the shared prefix, the less work the model performs during prefill. This directly reduces Time to First Token (TTFT), especially for long conversations and agentic applications.<\/p>\n
Why it matters<\/h3>\n
Unlike PagedAttention, which improves memory utilization, RadixAttention improves computational efficiency. It transforms repeated prompts into cache hits, allowing serving engines to skip thousands of identical transformer computations. The benefit is largest in workloads with stable system prompts, multi-turn chat, RAG pipelines, coding assistants, and agent loops where contexts evolve incrementally instead of being rewritten from scratch.<\/p>\n
How RadixAttention Works<\/h2>\n
Unlike PagedAttention, which organizes memory, RadixAttention organizes knowledge. Its goal answers one question efficiently: How much of this prompt has the system already computed? To do that, it maintains a global radix tree that indexes token sequences and their corresponding KV cache entries. Every new request either reuses an existing prefix or adds only the missing suffix.<\/p>\n
Step 1: Find the longest matching prefix<\/h3>\n
When a request arrives, the serving engine traverses the radix tree token by token to find the longest prefix that already exists. Instead of comparing entire prompts, it simply follows the matching path through the tree.<\/p>\n
\n
<\/figure>\n<\/div>\n
If 1,900 tokens of a 2,000-token prompt already exist, the model immediately reuses those KV tensors and computes only the remaining 100 tokens.<\/p>\n
Step 2: Compute only the unmatched suffix<\/strong><\/h3>\n
Next, once the system identifies the shared prefix, prefill begins exactly where the match ends. The system loads the reusable KV states from cache, while only the new tokens pass through the transformer.<\/p>\n
\n
<\/figure>\n<\/div>\n
This is why RadixAttention primarily improves Time to First Token (TTFT) rather than memory efficiency it eliminates redundant transformer computation.<\/p>\n
Step 3: Insert the new path into the tree<\/strong><\/h3>\n
Finally, after prefill (and later during generation), the system inserts the newly computed KV tensors back into the radix tree. Future requests can now reuse this longer prefix, allowing the cache to grow organically as real traffic arrives.<\/p>\n
\n
<\/figure>\n<\/div>\n
Rather than treating completed requests as disposable, RadixAttention turns them into reusable cache entries for subsequent requests.<\/p>\n
Because GPU memory is finite, the system cannot retain every cached prefix forever. RadixAttention uses leaf-based eviction, where the system removes the least recently used branches first while it protects shared interior prefixes.<\/p>\n
\n
<\/figure>\n<\/div>\n
This strategy preserves the prefixes that benefit the largest number of requests and maximizes cache hit rate over time.<\/p>\n
Why this changed LLM serving<\/strong><\/h3>\n
RadixAttention transforms the KV cache from a temporary memory structure into a persistent prefix cache. Instead of accelerating attention itself, it reduces the amount of attention the model needs to compute. For workloads such as chatbots, coding assistants, RAG systems, and autonomous agents where prompt prefixes repeat constantly the result is substantially lower prefill latency and much higher overall throughput.<\/p>\n
PagedAttention vs. RadixAttention: What\u2019s the Difference?<\/h2>\n
In contrast, developers often describe PagedAttention and RadixAttention as competing algorithms, but they solve completely different problems. PagedAttention focuses on how the system stores the KV cache in GPU memory, while RadixAttention focuses on how the system reuses previously computed KV states across requests. One is a memory allocation strategy; the other is a caching strategy. In modern LLM serving, they are complementary and are frequently used together.<\/p>\n
Think of them as two different layers<\/strong>RadixAttention : Prefix cache & reuse<\/h3>\n
A useful way to think about the serving stack is as two layers. PagedAttention sits at the memory layer, deciding where KV blocks live inside GPU memory. RadixAttention sits above it, deciding whether those KV blocks already exist and can be reused. The radix tree simply points to KV blocks that are managed by the paged allocator.<\/p>\n
A practical example<\/strong><\/h3>\n
Imagine three users start their conversations with the same system prompt.<\/p>\n
\n
<\/figure>\n<\/div>\n
Without RadixAttention, the serving engine computes the shared prefix three separate times. Without PagedAttention, each request also reserves an oversized contiguous memory region, wasting GPU memory. When both techniques are combined, the shared prefix is computed once, stored efficiently in paged KV blocks, and reused by every matching request.<\/p>\n
The key takeaway<\/strong><\/h3>\n
PagedAttention improves memory efficiency. RadixAttention improves computational efficiency. Together, they address the two biggest bottlenecks in LLM inference: storing the KV cache efficiently and avoiding unnecessary recomputation. Modern serving frameworks such as vLLM and SGLang increasingly combine these ideas to maximize both throughput and latency.<\/p>\n
How vLLM Implements Prefix Caching<\/strong><\/h3>\n
A common misconception is that RadixAttention is the only way to achieve prefix caching. In reality, vLLM also supports automatic prefix reuse, but it uses a different data structure. Instead of maintaining a radix tree, vLLM identifies KV blocks using chain hashing, allowing identical prefixes to be reused without storing them in a tree.<\/p>\n
The core idea: Every KV block gets a unique hash<\/strong><\/h3>\n
As a prompt is processed, each completed KV block receives a hash generated from three pieces of information:<\/p>\n
\n
the hash of its parent block<\/li>\n
the block\u2019s own token IDs<\/li>\n
optional metadata such as a LoRA ID or multimodal input hash<\/li>\n<\/ul>\n
Because each block depends on its parent, the hash uniquely represents the entire prefix leading to that block. If another request produces the same sequence of tokens, it generates exactly the same chain of hashes and immediately finds the cached KV blocks.<\/p>\n
\n
<\/figure>\n<\/div>\n
How cache lookup works<\/strong><\/h3>\n
When a new request arrives, vLLM computes block hashes in order and checks whether each one already exists in the global cache.<\/p>\n
\n
Hash match: Reuse the existing KV block.<\/li>\n
First miss: Allocate new blocks for the remaining suffix.<\/li>\n
Generation: Newly completed blocks are added back into the cache for future requests.<\/li>\n<\/ul>\n
This produces the same practical behavior as RadixAttention: repeated prefixes skip expensive prefill computation and reduce Time to First Token.<\/p>\n
Radix tree vs. Chain hashing<\/strong><\/h3>\n
Although both systems achieve automatic prefix caching, their underlying designs are different.<\/p>\n
For most applications, the difference is largely architectural rather than functional. Both engines automatically reuse identical prompt prefixes, making repeated requests significantly more efficient without changing model outputs.<\/p>\n
Security Considerations: Can Prefix Caching Leak Data?<\/strong><\/h3>\n
Prefix caching is designed to improve performance, but it also introduces an important security challenge. In a multi-tenant LLM service, cached KV blocks may be shared across requests from different users. If an identical prefix is served noticeably faster because it already exists in the cache, an attacker could potentially infer whether that prompt was processed recently. This is known as a prefix cache side channel.<\/p>\n
How the side channel works<\/strong><\/h3>\n
Imagine two users interacting with the same LLM service.<\/p>\n
If User B repeatedly sends carefully chosen prompts and observes unusually low Time to First Token (TTFT), they may infer that User A previously submitted the same prefix. The model\u2019s output is never exposed, but the cache itself becomes a source of information leakage.<\/p>\n
Modern serving frameworks solve this by introducing cache salting. Instead of hashing only the prompt tokens, the serving engine also includes a tenant-specific salt when generating cache identifiers.<\/p>\n
With cache salting:<\/p>\n
\n
Requests from the same tenant reuse cached prefixes normally.<\/li>\n
Requests from different tenants generate different cache keys, even identical prompts.<\/li>\n
Cross-tenant cache hits are eliminated, preventing timing-based information leakage.<\/li>\n<\/ul>\n
Why it matters<\/strong><\/h3>\n
For single-user or self-hosted deployments, prefix caching is primarily a performance optimization. In shared cloud infrastructure, however, it is also a security feature that must be configured correctly. Separating cache entries by tenant preserves the latency benefits of prefix caching while ensuring that one customer\u2019s requests cannot reveal information about another\u2019s.<\/p>\n
What Came Next: Beyond Paged and Radix Attention<\/strong><\/h3>\n
PagedAttention and RadixAttention solved the two fundamental problems of KV cache management efficient storage and prefix reuse. However, as context windows expanded to hundreds of thousands of tokens and LLMs began powering long-running agents, a new challenge emerged: the KV cache became too large to fit entirely in GPU memory. Modern serving systems therefore evolved from managing a single cache into managing a hierarchy of caches across GPUs, CPUs, and distributed storage.<\/p>\n
1. Hierarchical KV Caching<\/strong><\/h3>\n
Instead of treating GPU memory as the only cache, modern engines organize KV data into multiple storage tiers. Frequently accessed prefixes remain in high-bandwidth GPU memory, while older or less active prefixes are moved to host RAM or remote storage and fetched back only when needed.<\/p>\n
\n
<\/figure>\n<\/div>\n
This hierarchy behaves much like a processor cache:<\/p>\n
\n
\n\n
\n
Tier<\/strong><\/th>\n
Storage<\/strong><\/th>\n
Purpose<\/strong><\/th>\n<\/tr>\n<\/thead>\n\n
\n
L1<\/td>\n
GPU HBM<\/td>\n
Active KV blocks for ongoing requests<\/td>\n<\/tr>\n
The serving engine automatically migrates KV pages between tiers, allowing much larger effective context windows without requiring enormous GPU memory.<\/p>\n
2. Cache-Aware Routing<\/strong><\/h3>\n
Prefix caching is valuable only if related requests reach the same serving replica. In a distributed deployment, a conventional round-robin load balancer may send consecutive turns of the same conversation to different GPUs, resulting in cache misses despite identical prefixes.<\/p>\n
\n<\/figure>\n<\/div>\n
Cache-aware routing solves this by directing incoming requests toward the replica that already contains the required KV cache. Rather than balancing solely by load, the router also considers cache locality, reducing prefill latency and improving overall throughput.<\/p>\n
Another direction of research questioned PagedAttention itself. Instead of implementing paging inside the serving framework, newer approaches use CUDA Virtual Memory Management (VMM) to let the GPU provide virtual-to-physical address translation directly.<\/p>\n
\n<\/figure>\n<\/div>\n
The idea is simple: maintain a contiguous virtual KV cache while allowing physical pages to remain scattered underneath<\/em>. This preserves compatibility with existing attention kernels and reduces the engineering overhead of maintaining specialized paged kernels.<\/p>\n
Conclusion<\/h2>\n
PagedAttention and RadixAttention solve two different but equally important challenges in modern LLM serving. PagedAttention maximizes GPU memory efficiency by replacing contiguous KV allocation with a paged memory layout, while RadixAttention reduces latency by reusing previously computed prompt prefixes instead of recomputing them. <\/p>\n
Together, they improve throughput, increase concurrency, and lower the cost of long-context inference without changing model outputs. As LLM applications continue to scale, efficient KV cache management has become as important as model architecture itself. For developers, well-structured prompts and stable prefixes are now genuine performance optimizations.<\/p>\n
![\"Formula](\"https:\/\/cdn.analyticsvidhya.com\/wp-content\/uploads\/2026\/08\/image-1-7eqxqe.webp\")
<\/figure>\n<\/div>\n![\"Logical](\"https:\/\/cdn.analyticsvidhya.com\/wp-content\/uploads\/2026\/08\/image-2-7eqxqe.webp\")
<\/figure>\n<\/div>\n![\"Radix](\"https:\/\/cdn.analyticsvidhya.com\/wp-content\/uploads\/2026\/08\/image-4-7eqxqe.webp\")
<\/figure>\n<\/div>\n![\"Comparison](\"https:\/\/cdn.analyticsvidhya.com\/wp-content\/uploads\/2026\/08\/image-5-7eqxqe.webp\")
<\/figure>\n<\/div>\n![\"Process](\"https:\/\/cdn.analyticsvidhya.com\/wp-content\/uploads\/2026\/08\/image-6-7eqxqe.webp\")
<\/figure>\n<\/div>\n![\"KV](\"https:\/\/cdn.analyticsvidhya.com\/wp-content\/uploads\/2026\/08\/image-7-7eqxqe.webp\")
<\/figure>\n<\/div>\n![\"Radix](\"https:\/\/cdn.analyticsvidhya.com\/wp-content\/uploads\/2026\/08\/image-8-7eqxqe.webp\")
<\/figure>\n<\/div>\n![\"Least](\"https:\/\/cdn.analyticsvidhya.com\/wp-content\/uploads\/2026\/08\/image-9-7eqxqe.webp\")
<\/figure>\n<\/div>\n![\"Prefix](\"https:\/\/cdn.analyticsvidhya.com\/wp-content\/uploads\/2026\/08\/image-10-7eqxqe.webp\")
<\/figure>\n<\/div>\n![\"KV](\"https:\/\/cdn.analyticsvidhya.com\/wp-content\/uploads\/2026\/08\/image-11-7eqxqe.webp\")
<\/figure>\n<\/div>\n![\"Hierarchical](\"https:\/\/cdn.analyticsvidhya.com\/wp-content\/uploads\/2026\/08\/image-12-7eqxqe.webp\")
<\/figure>\n<\/div>\n![\"Distributed](\"https:\/\/cdn.analyticsvidhya.com\/wp-content\/uploads\/2026\/08\/image-13-7eqxqe.webp\")
<\/figure>\n<\/div>\n![\"Virtual](\"https:\/\/cdn.analyticsvidhya.com\/wp-content\/uploads\/2026\/08\/image-14-7eqxqe.webp\")
<\/figure>\n<\/div>\n![\"Janvi](\"https:\/\/av-eks-lekhak.s3.amazonaws.com\/media\/lekhak-profile-images\/converted_image_ToTu2tx.webp\")