Paged Attention

Paged Attention partitions the KV cache into fixed-size blocks, analogous to pages in an operating system's virtual memory. Each block stores the key and value tensors for a contiguous subsequence of tokens. The block table maps logical sequences to physical blocks, allowing non-contiguous storage without requiring large contiguous memory allocations. This eliminates internal and external fragmentation, ensuring that memory is wasted only in the last block of a sequence—typically less than 4% overhead.

Blocks can be shared across multiple sequences through a copy-on-write mechanism. When parallel sampling generates multiple outputs from a single prompt, all output sequences share the prompt's KV cache blocks. A block is only copied when a sequence writes to it, drastically reducing memory duplication. This is critical for techniques like beam search and parallel decoding, where dozens of sequences share a common prefix.

Unlike traditional serving systems that pre-allocate a fixed maximum-length KV cache slot per sequence, Paged Attention allocates blocks on demand as generation proceeds. This enables the scheduler to oversubscribe GPU memory, packing more concurrent sequences than physically possible under static allocation. When memory is exhausted, blocks from preempted sequences can be swapped to CPU RAM and later restored, enabling graceful handling of memory pressure without request failure.

By eliminating fragmentation and enabling memory sharing, Paged Attention achieves near-optimal memory utilization. The vLLM serving engine, which implements this algorithm, demonstrates up to 24x higher throughput compared to Hugging Face Transformers and 2-4x improvement over previous state-of-the-art systems like FasterTransformer. This throughput gain comes entirely from better memory management, not from modifying the attention computation itself.

Paged Attention enables continuous batching by allowing new sequences to join a running batch without waiting for existing sequences to complete. When GPU memory is exhausted, the scheduler can preempt low-priority sequences by evicting their blocks to CPU memory. When memory becomes available, blocks are swapped back in, and generation resumes exactly where it left off. This cooperative preemption avoids the all-or-nothing eviction of traditional systems.

The key-value cache stores the computed attention keys and values from all previous tokens during autoregressive generation. Without it, the model would recompute attention for the entire sequence at each step, resulting in quadratic complexity. PagedAttention directly manages this cache by partitioning it into non-contiguous blocks, eliminating the memory fragmentation that plagues traditional contiguous allocation schemes.

A serving technique that maximizes GPU utilization by appending new sequences to a running batch immediately upon arrival, rather than waiting for the entire batch to complete. When combined with PagedAttention, continuous batching can seamlessly evict and reallocate KV cache blocks as sequences finish, allowing the freed memory to serve new requests without fragmentation penalties.

An optimization that stores and reuses the computed KV cache for a shared prompt prefix across multiple generation requests. When multiple users share a common system prompt, PagedAttention's block-based structure allows the prefix's KV blocks to be shared by reference rather than copied, dramatically reducing memory consumption and eliminating redundant computation for identical prompt segments.

An IO-aware exact attention algorithm that minimizes high-bandwidth memory (HBM) reads and writes by tiling the computation in GPU SRAM. While Flash Attention optimizes the computation of attention, PagedAttention optimizes the storage of its outputs. The two techniques are complementary and often deployed together in production serving stacks to maximize both speed and memory efficiency.

An attention mechanism that uses a single set of key-value heads shared across multiple query heads, reducing the size of the KV cache proportionally. For example, Llama 2 70B uses 8 key-value heads for 64 query heads, cutting KV cache memory by 8x. GQA directly reduces the memory pressure that PagedAttention must manage, enabling larger batch sizes and longer context windows.