KV Cache Administration: PagedAttention & RadixAttention

Trendy LLMs depend on quantization, pruning, distillation, and sooner consideration kernels, however manufacturing efficiency usually 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 remodeled this problem: PagedAttention improves reminiscence allocation, whereas RadixAttention permits environment friendly prefix reuse.

Collectively, these methods make LLM serving sooner and extra memory-efficient. On this article, we look at how PagedAttention and RadixAttention work, why they matter, and the way they permit 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 technology 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 usually turns into the most important dynamic client of GPU reminiscence, figuring out what number of requests can run concurrently.

Why reminiscence turns into the limiting issue

The scale of the KV cache will depend on 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 practically 12.8 GiB of reminiscence earlier than contemplating batching or extra requests.

The 2 elementary issues

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

• Reminiscence fragmentation: This happens when the system allocates KV reminiscence inefficiently, leaving giant parts of GPU reminiscence unusable and decreasing the variety of concurrent requests.
• Redundant computation: Equivalent immediate prefixes are repeatedly prefetched and encoded, though 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 recent LLM serving.

PagedAttention: Fixing the Reminiscence Allocation Downside

By 2023, the trade recognized the most important inefficiency in LLM serving because the storage technique of the KV cache relatively than consideration itself. The system allotted one giant contiguous block of GPU reminiscence to carry the whole KV cache for each request. For the reason that serving engine couldn’t predict how lengthy a response could be, it sometimes reserved area 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:

• Inside 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 overall free reminiscence could also be ample, it’s now not out there as one contiguous block for brand new requests.

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

How PagedAttention Works

The core concept behind PagedAttention is easy: 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) relatively than reserving one giant contiguous buffer for a whole sequence. As technology progresses, new blocks are allotted solely after the earlier one turns into full, permitting reminiscence to develop incrementally relatively 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 handle 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 collect the required keys and values, making the sequence seem steady though its knowledge is bodily scattered.

Actually, this indirection attracts inspiration from web page tables in working programs: 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 area 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 which will by no means be produced, which dramatically reduces inner fragmentation.

Step 4: Share blocks with copy-on-write

One of the crucial 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 finally 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 an identical system prompts.

Why this modified LLM serving

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

RadixAttention: Fixing the Prefix Reuse Downside

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

The authors launched RadixAttention to eradicate this redundant computation by turning the KV cache right into a searchable, reusable index relatively than a brief reminiscence buffer.

The important thing concept: 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.
Consumer: What's AI?
System: You're a useful assistant.
Consumer: What's Machine Studying?
System: You're a useful assistant.
Consumer: What's Deep Studying?

Relatively than storing three an identical copies of the shared prefix, the radix tree retains it as soon as and creates separate branches just for the ultimate consumer 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 present KV tensors for that matched prefix as a substitute of recomputing them.
3. Insert: Compute solely the unequalled 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 purposes.

Why it issues

In contrast to PagedAttention, which improves reminiscence utilization, RadixAttention improves computational effectivity. It transforms repeated prompts into cache hits, permitting serving engines to skip hundreds of an identical 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

In contrast to 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 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 unequalled 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 the transformer.

Because of this RadixAttention primarily improves Time to First Token (TTFT) relatively than reminiscence effectivity it eliminates redundant transformer computation.

Step 3: Insert the brand new path into the tree

Lastly, after prefill (and later throughout technology), 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 site visitors arrives.

Relatively 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 not retain each cached prefix eternally. 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 most important variety of requests and maximizes cache hit charge over time.

Why this modified LLM serving

RadixAttention transforms the KV cache from a brief 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 programs, and autonomous brokers the place immediate prefixes repeat continuously the result’s considerably decrease prefill latency and far increased total throughput.

PagedAttention vs. RadixAttention: What’s the Distinction?

In distinction, builders usually describe PagedAttention and RadixAttention as competing algorithms, however they remedy fully 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 ceaselessly used collectively.

A side-by-side comparability

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

A helpful means to consider the serving stack is as two layers. PagedAttention sits on the reminiscence layer, deciding the place KV blocks dwell 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 methods 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 handle the 2 greatest bottlenecks in LLM inference: storing the KV cache effectively and avoiding pointless recomputation. Trendy 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 option to obtain prefix caching. In actuality, vLLM additionally helps automated prefix reuse, nevertheless it makes use of a unique knowledge construction. As a substitute of sustaining a radix tree, vLLM identifies KV blocks utilizing chain hashing, permitting an identical prefixes to be reused with out storing them in a tree.

The core concept: Each KV block will get a novel hash

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

• 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 will depend on its dad or mum, the hash uniquely represents the whole 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 world cache.

• Hash match: Reuse the present KV block.
• First miss: Allocate new blocks for the remaining suffix.
• Technology: 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 programs obtain automated prefix caching, their underlying designs are completely different.

For many purposes, the distinction is basically architectural relatively than practical. Each engines mechanically reuse an identical immediate prefixes, making repeated requests considerably extra environment friendly with out altering mannequin outputs.

Safety Issues: Can Prefix Caching Leak Knowledge?

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 an identical prefix is served noticeably sooner 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 Consumer B repeatedly sends rigorously chosen prompts and observes unusually low Time to First Token (TTFT), they could infer that Consumer A beforehand submitted the identical prefix. The mannequin’s output isn’t uncovered, however the cache itself turns into a supply of knowledge leakage.

Cache salting prevents cross-tenant reuse

Trendy serving frameworks remedy 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 an identical 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, nonetheless, it’s also a safety function that should be configured accurately. Separating cache entries by tenant preserves the latency advantages of prefix caching whereas guaranteeing that one buyer’s requests can not reveal details about one other’s.

What Got here Subsequent: Past Paged and Radix Consideration

PagedAttention and RadixAttention solved the 2 elementary issues of KV cache administration environment friendly storage and prefix reuse. Nonetheless, 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 grew to become too giant to suit fully in GPU reminiscence. Trendy serving programs 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 set up KV knowledge into a number of storage tiers. Often 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 like 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 effective 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 an identical prefixes.

Cache-aware routing solves this by directing incoming requests towards the duplicate that already accommodates the required KV cache. Relatively than balancing solely by load, the router additionally considers cache locality, decreasing prefill latency and enhancing 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 handle translation instantly.

The concept is easy: preserve 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 remedy 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, enhance concurrency, and decrease the price of long-context inference with out altering mannequin outputs. As LLM purposes proceed to scale, environment friendly KV cache administration has grow to be as essential as mannequin structure itself. For builders, well-structured prompts and secure prefixes are actually real efficiency optimizations.

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

Often Requested Questions

Hello, I’m Janvi, a passionate knowledge science fanatic at present working at Analytics Vidhya. My journey into the world of knowledge started with a deep curiosity about how we will extract significant insights from complicated datasets.