PagedAttention vs. RadixAttention: Optimizing LLM KV Cache Management

Fashionable LLMs depend on quantization, pruning, distillation, and quicker consideration kernels, however manufacturing efficiency typically relies upon most on KV cache administration. As context home windows develop, the cache consumes vital GPU reminiscence, limiting concurrency, throughput, and latency. Two breakthroughs reworked this problem: PagedAttention improves reminiscence allocation, whereas RadixAttention allows environment friendly prefix reuse.

Collectively, these strategies make LLM serving quicker and extra memory-efficient. On this article, we look at how PagedAttention and RadixAttention work, why they matter, and the way they allow high-performance LLM serving.

Why the KV Cache Is the Actual Bottleneck

Each transformer generates textual content one token at a time. For every new token, the mannequin should attend to all beforehand generated tokens through the use of their key (Ok) and worth (V) vectors. Recomputing these vectors at each step would make era prohibitively costly, so serving engines retailer them in reminiscence because the KV cache. This cache eliminates redundant computation and makes autoregressive decoding sensible, nevertheless it introduces a brand new problem: reminiscence consumption grows linearly with sequence size. For long-context fashions, the KV cache typically turns into the biggest dynamic shopper of GPU reminiscence, figuring out what number of requests can run concurrently.

Why reminiscence turns into the limiting issue

The dimensions of the KV cache depends upon the mannequin structure and the variety of tokens saved. The per-token reminiscence requirement is:

The place:

For a Llama-3 8B class mannequin with 32 layers, 8 KV heads, 128-dimensional heads, and FP16 precision, every token occupies roughly 128 KiB of KV cache. A 100,000-token context due to this fact requires almost 12.8 GiB of reminiscence earlier than contemplating batching or extra requests.

The 2 basic issues

As GPU reminiscence fills with KV tensors, serving methods encounter two distinct bottlenecks:

• Reminiscence fragmentation: This happens when the system allocates KV reminiscence inefficiently, leaving massive parts of GPU reminiscence unusable and decreasing the variety of concurrent requests.
• Redundant computation: An identical immediate prefixes are repeatedly prefetched and encoded, regardless that their KV states have already been computed.

These issues are unbiased, and every impressed a unique resolution. PagedAttention addresses environment friendly reminiscence allocation, whereas RadixAttention focuses on reusing beforehand computed KV cache throughout requests. Collectively, they outline the muse of contemporary LLM serving.

PagedAttention: Fixing the Reminiscence Allocation Drawback

By 2023, the trade recognized the largest inefficiency in LLM serving because the storage technique of the KV cache somewhat than consideration itself. The system allotted one massive contiguous block of GPU reminiscence to carry your complete KV cache for each request. For the reason that serving engine couldn’t predict how lengthy a response could be, it sometimes reserved house near the mannequin’s most context size. Most of that reminiscence remained unused all through the request, drastically decreasing the variety of sequences that may very well be served concurrently.

The issue with contiguous allocation

Conventional allocation creates two types of fragmentation:

• Inner fragmentation: A request reserves hundreds of token slots however generates solely a small response, leaving many of the allotted reminiscence idle.
• Exterior fragmentation: As requests of various lengths end, scattered gaps seem throughout GPU reminiscence. Though the full free reminiscence could also be ample, it’s not accessible as one contiguous block for brand new requests.

The result’s poor GPU utilization and decrease throughput, even when loads of reminiscence technically stays accessible.

How PagedAttention Works

The core thought behind PagedAttention is straightforward: allocate KV reminiscence solely when it’s wanted. As a substitute, the system divides the KV cache into fixed-size blocks (sometimes 16 or 32 tokens) somewhat than reserving one massive contiguous buffer for a complete sequence. As era progresses, new blocks are allotted solely after the earlier one turns into full, permitting reminiscence to develop incrementally somewhat than being over-provisioned from the beginning.

Step 1: Divide the KV cache into blocks

The system splits every sequence into equal-sized logical blocks, whereas the system can retailer the precise blocks wherever in GPU reminiscence.

Step 2: Use a block desk for deal with translation

Each request maintains a block desk that maps logical block IDs to their bodily areas in GPU reminiscence. Throughout consideration, the kernel consults this desk to assemble the required keys and values, making the sequence seem steady regardless that its information is bodily scattered.

The truth is, this indirection attracts inspiration from web page tables in working methods: the mannequin operates on a logical sequence, whereas the serving engine manages bodily placement.

Step 3: Develop reminiscence on demand

As a substitute of allocating house for hundreds of future tokens, PagedAttention expands the KV cache one block at a time.

A request producing 60 tokens occupies solely the blocks required for these 60 tokens. No reminiscence is reserved for tokens that will by no means be produced, which dramatically reduces inner fragmentation.

Step 4: Share blocks with copy-on-write

Probably the most highly effective options of PagedAttention is block sharing. If a number of requests start with the identical immediate, they reference the identical bodily KV blocks as a substitute of storing duplicate tensors.

When two requests ultimately diverge, the system copies the shared block solely on the level of modification, a mechanism often known as copy-on-write. This makes prefix sharing extremely memory-efficient for beam search, parallel sampling, and concurrent requests with similar system prompts.

Why this modified LLM serving

PagedAttention doesn’t change the eye algorithm or the mannequin’s outputs. Its innovation is only architectural: it replaces inefficient contiguous allocation with a paged reminiscence format. The result’s dramatically decrease reminiscence waste, greater GPU utilization, and the flexibility to serve many extra concurrent requests on the identical {hardware}.

RadixAttention: Fixing the Prefix Reuse Drawback

PagedAttention made GPU reminiscence environment friendly, nevertheless it left one other main inefficiency untouched: the system nonetheless recomputed similar prefixes for each new request. In actual manufacturing workloads, requests are hardly ever unbiased. Hundreds of customers share the identical system immediate, chat conversations repeatedly embody their whole historical past, and agent workflows repeatedly append to an present context. Consequently, the system spends a lot of the costly prefill section producing KV tensors that exist already.

The authors launched RadixAttention to get rid of this redundant computation by turning the KV cache right into a searchable, reusable index somewhat than a short lived reminiscence buffer.

The important thing thought: Retailer prefixes in a radix tree

As a substitute of discarding KV tensors when a request finishes, RadixAttention retains them inside a radix tree a compressed trie the place every edge represents a sequence of tokens. The system shops each distinctive immediate prefix as soon as, whereas completely different requests department solely the place their tokens start to vary.

For instance, three requests could start with the identical system immediate:

System: You're a useful assistant.
Person: What's AI?
System: You're a useful assistant.
Person: What's Machine Studying?
System: You're a useful assistant.
Person: What's Deep Studying?

Fairly than storing three similar copies of the shared prefix, the radix tree retains it as soon as and creates separate branches just for the ultimate person question.

How prefix matching works

When a brand new request arrives, RadixAttention performs three operations:

1. Match: Discover the longest token prefix already current within the radix tree.
2. Reuse: Load the prevailing KV tensors for that matched prefix as a substitute of recomputing them.
3. Insert: Compute solely the unrivaled suffix and append it again into the tree for future requests.

The longer the shared prefix, the much less work the mannequin performs throughout prefill. This instantly reduces Time to First Token (TTFT), particularly for lengthy conversations and agentic functions.

Why it issues

Not like PagedAttention, which improves reminiscence utilization, RadixAttention improves computational effectivity. It transforms repeated prompts into cache hits, permitting serving engines to skip hundreds of similar transformer computations. The profit is largest in workloads with secure system prompts, multi-turn chat, RAG pipelines, coding assistants, and agent loops the place contexts evolve incrementally as a substitute of being rewritten from scratch.

How RadixAttention Works

Not like PagedAttention, which organizes reminiscence, RadixAttention organizes information. Its purpose solutions one query effectively: How a lot of this immediate has the system already computed? To do this, it maintains a world radix tree that indexes token sequences and their corresponding KV cache entries. Each new request both reuses an present prefix or provides solely the lacking suffix.

Step 1: Discover the longest matching prefix

When a request arrives, the serving engine traverses the radix tree token by token to search out the longest prefix that already exists. As a substitute of evaluating whole prompts, it merely follows the matching path by way of the tree.

If 1,900 tokens of a 2,000-token immediate exist already, the mannequin instantly reuses these KV tensors and computes solely the remaining 100 tokens.

Step 2: Compute solely the unrivaled suffix

Subsequent, as soon as the system identifies the shared prefix, prefill begins precisely the place the match ends. The system hundreds the reusable KV states from cache, whereas solely the brand new tokens move by way of the transformer.

This is the reason RadixAttention primarily improves Time to First Token (TTFT) somewhat than reminiscence effectivity it eliminates redundant transformer computation.

Step 3: Insert the brand new path into the tree

Lastly, after prefill (and later throughout era), the system inserts the newly computed KV tensors again into the radix tree. Future requests can now reuse this longer prefix, permitting the cache to develop organically as actual visitors arrives.

Fairly than treating accomplished requests as disposable, RadixAttention turns them into reusable cache entries for subsequent requests.

Step 4: Evict unused prefixes intelligently

As a result of GPU reminiscence is finite, the system can’t retain each cached prefix endlessly. RadixAttention makes use of leaf-based eviction, the place the system removes the least not too long ago used branches first whereas it protects shared inside prefixes.

This technique preserves the prefixes that profit the biggest variety of requests and maximizes cache hit charge over time.

Why this modified LLM serving

RadixAttention transforms the KV cache from a short lived reminiscence construction right into a persistent prefix cache. As a substitute of accelerating consideration itself, it reduces the quantity of consideration the mannequin must compute. For workloads resembling chatbots, coding assistants, RAG methods, and autonomous brokers the place immediate prefixes repeat consistently the result’s considerably decrease prefill latency and far greater total throughput.

PagedAttention vs. RadixAttention: What’s the Distinction?

In distinction, builders typically describe PagedAttention and RadixAttention as competing algorithms, however they resolve utterly completely different issues. PagedAttention focuses on how the system shops the KV cache in GPU reminiscence, whereas RadixAttention focuses on how the system reuses beforehand computed KV states throughout requests. One is a reminiscence allocation technique; the opposite is a caching technique. In fashionable LLM serving, they’re complementary and are often used collectively.

A side-by-side comparability

Consider them as two completely different layersRadixAttention : Prefix cache & reuse

A helpful approach to consider the serving stack is as two layers. PagedAttention sits on the reminiscence layer, deciding the place KV blocks reside inside GPU reminiscence. RadixAttention sits above it, deciding whether or not these KV blocks exist already and could be reused. The radix tree merely factors to KV blocks which can be managed by the paged allocator.

A sensible instance

Think about three customers begin their conversations with the identical system immediate.

With out RadixAttention, the serving engine computes the shared prefix three separate instances. With out PagedAttention, every request additionally reserves an outsized contiguous reminiscence area, losing GPU reminiscence. When each strategies are mixed, the shared prefix is computed as soon as, saved effectively in paged KV blocks, and reused by each matching request.

The important thing takeaway

PagedAttention improves reminiscence effectivity. RadixAttention improves computational effectivity. Collectively, they deal with the 2 greatest bottlenecks in LLM inference: storing the KV cache effectively and avoiding pointless recomputation. Fashionable serving frameworks resembling vLLM and SGLang more and more mix these concepts to maximise each throughput and latency.

How vLLM Implements Prefix Caching

A standard false impression is that RadixAttention is the one approach to obtain prefix caching. In actuality, vLLM additionally helps computerized prefix reuse, nevertheless it makes use of a unique information construction. As a substitute of sustaining a radix tree, vLLM identifies KV blocks utilizing chain hashing, permitting similar prefixes to be reused with out storing them in a tree.

The core thought: Each KV block will get a singular hash

As a immediate is processed, every accomplished KV block receives a hash generated from three items of data:

• the hash of its dad or mum block
• the block’s personal token IDs
• optionally available metadata resembling a LoRA ID or multimodal enter hash

As a result of every block depends upon its dad or mum, the hash uniquely represents your complete prefix resulting in that block. If one other request produces the identical sequence of tokens, it generates precisely the identical chain of hashes and instantly finds the cached KV blocks.

How cache lookup works

When a brand new request arrives, vLLM computes block hashes so as and checks whether or not each already exists within the international cache.

• Hash match: Reuse the prevailing KV block.
• First miss: Allocate new blocks for the remaining suffix.
• Era: Newly accomplished blocks are added again into the cache for future requests.

This produces the identical sensible conduct as RadixAttention: repeated prefixes skip costly prefill computation and cut back Time to First Token.

Radix tree vs. Chain hashing

Though each methods obtain computerized prefix caching, their underlying designs are completely different.

For many functions, the distinction is essentially architectural somewhat than useful. Each engines mechanically reuse similar immediate prefixes, making repeated requests considerably extra environment friendly with out altering mannequin outputs.

Safety Concerns: Can Prefix Caching Leak Information?

Prefix caching is designed to enhance efficiency, nevertheless it additionally introduces an essential safety problem. In a multi-tenant LLM service, cached KV blocks could also be shared throughout requests from completely different customers. If an similar prefix is served noticeably quicker as a result of it already exists within the cache, an attacker might probably infer whether or not that immediate was processed not too long ago. This is called a prefix cache aspect channel.

How the aspect channel works

Think about two customers interacting with the identical LLM service.

If Person B repeatedly sends rigorously chosen prompts and observes unusually low Time to First Token (TTFT), they could infer that Person A beforehand submitted the identical prefix. The mannequin’s output isn’t uncovered, however the cache itself turns into a supply of data leakage.

Cache salting prevents cross-tenant reuse

Fashionable serving frameworks resolve this by introducing cache salting. As a substitute of hashing solely the immediate tokens, the serving engine additionally features a tenant-specific salt when producing cache identifiers.

With cache salting:

• Requests from the identical tenant reuse cached prefixes usually.
• Requests from completely different tenants generate completely different cache keys, even similar prompts.
• Cross-tenant cache hits are eradicated, stopping timing-based info leakage.

Why it issues

For single-user or self-hosted deployments, prefix caching is primarily a efficiency optimization. In shared cloud infrastructure, nevertheless, additionally it is a safety characteristic that should be configured appropriately. Separating cache entries by tenant preserves the latency advantages of prefix caching whereas guaranteeing that one buyer’s requests can’t reveal details about one other’s.

What Got here Subsequent: Past Paged and Radix Consideration

PagedAttention and RadixAttention solved the 2 basic issues of KV cache administration environment friendly storage and prefix reuse. Nevertheless, as context home windows expanded to lots of of hundreds of tokens and LLMs started powering long-running brokers, a brand new problem emerged: the KV cache turned too massive to suit fully in GPU reminiscence. Fashionable serving methods due to this fact developed from managing a single cache into managing a hierarchy of caches throughout GPUs, CPUs, and distributed storage.

1. Hierarchical KV Caching

As a substitute of treating GPU reminiscence as the one cache, fashionable engines arrange KV information into a number of storage tiers. Incessantly accessed prefixes stay in high-bandwidth GPU reminiscence, whereas older or much less energetic prefixes are moved to host RAM or distant storage and fetched again solely when wanted.

This hierarchy behaves very similar to a processor cache:

The serving engine mechanically migrates KV pages between tiers, permitting a lot bigger efficient context home windows with out requiring monumental GPU reminiscence.

2. Cache-Conscious Routing

Prefix caching is efficacious provided that associated requests attain the identical serving duplicate. In a distributed deployment, a standard round-robin load balancer could ship consecutive turns of the identical dialog to completely different GPUs, leading to cache misses regardless of similar prefixes.

Cache-aware routing solves this by directing incoming requests towards the duplicate that already accommodates the required KV cache. Fairly than balancing solely by load, the router additionally considers cache locality, decreasing prefill latency and bettering total throughput.

3. Digital Reminiscence-Primarily based KV Administration

One other course of analysis questioned PagedAttention itself. As a substitute of implementing paging contained in the serving framework, newer approaches use CUDA Digital Reminiscence Administration (VMM) to let the GPU present virtual-to-physical deal with translation instantly.

The concept is straightforward: keep a contiguous digital KV cache whereas permitting bodily pages to stay scattered beneath. This preserves compatibility with present consideration kernels and reduces the engineering overhead of sustaining specialised paged kernels.

Conclusion

PagedAttention and RadixAttention resolve two completely different however equally essential challenges in fashionable LLM serving. PagedAttention maximizes GPU reminiscence effectivity by changing contiguous KV allocation with a paged reminiscence format, whereas RadixAttention reduces latency by reusing beforehand computed immediate prefixes as a substitute of recomputing them.

Collectively, they enhance throughput, improve concurrency, and decrease the price of long-context inference with out altering mannequin outputs. As LLM functions proceed to scale, environment friendly KV cache administration has turn out to be as essential as mannequin structure itself. For builders, well-structured prompts and secure prefixes at the moment are real efficiency optimizations.

Learn extra: How Baidu Limitless-OCR Works: Fixing Lengthy-Doc Transcription

Incessantly Requested Questions