LLM: PagedAttention and RadixAttention Optimize KV Cache

Two technical advancements address the Achilles' heel of LLM services: KV cache management. PagedAttention reshapes memory allocation, while RadixAttention capitalizes on prefix reuse. Together, they aim for a more competitive, GPU-efficient, and responsive service without altering the attention algorithm itself.

RadixAttention reduces computation by reusing prefixes

RadixAttention transforms the KV cache into a reusable index rather than a simple temporary buffer. Prefixes are stored in a radix tree, a compressed trie where each edge represents a sequence of tokens, allowing each prompt prefix to be retained only once and branching only where tokens differ. When a new request arrives, the system searches for the longest existing prefix, reuses the corresponding KV tensors, and only computes the missing suffix, which it inserts into the tree for future requests. The longer the shared prefix, the shorter the pre-filling phase, which directly reduces the Time to First Token, especially for extended conversations and agent applications. Unlike PagedAttention, which targets memory usage, this approach focuses on computational efficiency and converts repeated prompts into cache accesses, avoiding thousands of identical transformer computations. An illustrative example mentions three requests sharing the same system prompt, consolidated into a common trunk with branches only on the user question.

PagedAttention addresses memory: block allocation and address table

PagedAttention is based on a simple idea: allocate KV memory only on demand. The cache is divided into fixed-size blocks, often 16 or 32 tokens, and new blocks are reserved only once the previous one is filled, making growth truly incremental. Each sequence is viewed as a series of logical blocks that can reside anywhere in GPU memory. A block table, unique to each request, associates logical identifiers with physical locations; the attention kernel consults it to gather keys and values, creating the illusion of continuity despite dispersion. Inspired by page tables in operating systems, this architecture replaces contiguous allocation with block paging, without altering the attention algorithm or the model's outputs. The expected effects include reduced memory waste, better GPU utilization, and more concurrent requests on the same hardware.

Two independent problems: fragmentation and recomputation

Two distinct bottlenecks hinder LLM workloads: memory fragmentation and recomputation of prefixes. PagedAttention specifically targets efficient allocation to limit fragmentation, while RadixAttention addresses inter-request reuse of already encoded prefixes. Even after adopting a more rational memory paging approach, recomputation persisted: in production, many requests share a system prompt, conversations reinject their history, and agents continuously add context. A costly part of pre-filling thus regenerated existing KV tensors, necessitating a dedicated solution on the computation side.

The size of the KV cache sets service concurrency

Autoregressive decoding occurs token by token, with each new token consulting all past keys and values. Recomputing these vectors at each step would be prohibitive, hence the KV cache, which eliminates redundancies and makes generation feasible. This benefit comes at a cost: the memory used grows linearly with sequence length. In long-context models, the KV cache often becomes the primary dynamic memory component on the GPU and limits the number of simultaneous requests. The need per token depends on the number of layers, KV heads, head dimension, and bytes per value, with, for example, 2 bytes in FP16. For a model in the Llama‑3 8B class with 32 layers, 8 KV heads, and heads of dimension 128 in FP16, the occupancy is estimated at around 128 KiB per token, and a context of 100,000 tokens approaches 12.8 GiB, even before any batching. In practice, performance in production often depends primarily on the management of this cache, which impacts concurrency, throughput, and latency.

Why contiguous allocation limits workloads

In 2023, the community identified the method of storing the KV cache as the primary source of service inefficiency, more so than attention itself. Engines then allocated large contiguous blocks per request while often reserving a capacity close to the maximum context, due to not knowing the final response length. A significant portion of this memory remained unused, reducing the number of parallel sequences. Two forms of fragmentation ensued: internal, when thousands of reserved slots remained empty for small responses; and external, when the ends of requests of varying lengths left scattered holes, making it impossible to allocate a new large contiguous block despite a sufficient total free memory. The combined effect was poor GPU utilization and reduced throughput, even as memory remained available.

Block sharing and copy-on-write for common prompts

In addition to on-demand allocation by fixed blocks, PagedAttention allows block sharing: requests starting with the same prompt point to the same physical blocks, avoiding duplicates. When two sequences diverge, a copy occurs only at the point of modification, following a copy-on-write mechanism. This prefix sharing proves particularly memory-efficient for beam search, parallel sampling, or concurrent requests with a common system prompt. In this model, new blocks are reserved only after the previous ones are filled, and a request that produces only 60 tokens occupies only the blocks necessary for those 60 tokens, limiting internal fragmentation.