PagedAttention

PagedAttention divides the KV cache for each sequence into fixed-size blocks, analogous to memory pages. These blocks can be allocated in non-contiguous physical memory (GPU DRAM). This eliminates the need for large, contiguous memory reservations and prevents fragmentation when sequences are of different lengths or are processed in continuous batching.

• Key Benefit: Enables efficient sharing of GPU memory across multiple requests.
• Analogy: Similar to how an OS allows a program's memory to be scattered across physical RAM.

The algorithm enables two powerful forms of memory sharing, drastically reducing total memory consumption:

• Shared Prompts: In multi-user or multi-tenant scenarios, identical system prompts or shared context across requests (e.g., a document preamble) are stored in read-only KV cache blocks. All sequences referencing this context point to the same physical memory.
• Parallel Sampling: When generating multiple outputs (candidates) from a single prompt (e.g., for beam search or sampling), the shared prompt's KV cache is not duplicated. Each candidate sequence reuses these blocks, diverging only in newly generated tokens.

This sharing is managed via a block table that maps logical blocks in a sequence to physical blocks in memory.

Each sequence maintains a block table, a central data structure that acts as a page table. It maps the sequence's logical KV cache blocks to physical blocks in GPU memory.

• Logical Blocks: Represent the sequence's KV cache in order.
• Physical Blocks: The actual allocated memory locations, which may be non-contiguous or shared.
• Function: During attention computation, the kernel uses this table to gather the required keys and values from potentially scattered physical blocks, performing the equivalent of a virtual-to-physical address translation.

This indirection is what enables flexible allocation, sharing, and on-the-fly memory optimization.

PagedAttention requires custom GPU kernels to execute efficiently. These kernels are designed to:

• Interpret Block Tables: Read the mapping and gather KV data from the dispersed physical blocks.
• Handle Variable-Length Sequences: Seamlessly compute attention for sequences where the last block may be partially filled.
• Minimize Overhead: The gather operation is fused into the attention computation, avoiding significant performance penalties compared to naive implementations.

These kernels are a key enabler, making the paging abstraction practical for high-performance inference.

Blocks are allocated dynamically as a sequence generates more tokens. When GPU memory is exhausted, vLLM can employ eviction policies to reclaim space.

• Allocation: New blocks are assigned from a free pool as needed.
• Eviction: Least-recently-used (LRU) or other policies can swap out blocks of completed or low-priority sequences. In a future extension, blocks could be paged to CPU RAM.
• Benefit: This allows the system to serve more concurrent requests than would fit if all KV caches were pre-allocated contiguously, maximizing GPU utilization and throughput.

PagedAttention is foundational for continuous batching (iteration-level scheduling). In this paradigm, new requests are added to a running batch as others finish, creating a ragged batch of sequences at different generation stages.

• Challenge: Traditional contiguous KV cache management cannot handle this efficiently.
• Solution: PagedAttention's block-based approach allows each sequence to manage its cache independently. The scheduler can add a new sequence by simply allocating a new block table and a few initial blocks, without reorganizing the memory of existing sequences.

This combination is what allows vLLM to achieve near-100% GPU utilization during inference.

An inference scheduling strategy that dynamically groups incoming requests into a running batch. Unlike static batching, new sequences are added to the batch as others finish generation, maximizing GPU utilization. This is the scheduling layer that PagedAttention optimizes for, as it efficiently manages the KV cache for sequences of variable and unpredictable lengths within the continuous batch.

The Key-Value (KV) Cache is a memory buffer that stores the computed key and value vectors for previous tokens in a sequence during autoregressive generation. This avoids recomputing these vectors for every new token, dramatically reducing computational cost. PagedAttention is an algorithm specifically designed to manage this cache efficiently in non-contiguous, paged memory blocks.

An I/O-aware, exact attention algorithm that reduces memory reads/writes between GPU SRAM and HBM. While PagedAttention optimizes memory management between attention computations (the KV cache), FlashAttention optimizes the computation of attention itself. They are complementary techniques: FlashAttention speeds up the attention operation, and PagedAttention efficiently manages the memory for its inputs/outputs across many concurrent requests.

A state where free memory is broken into small, non-contiguous blocks, preventing the allocation of larger contiguous buffers despite sufficient total free space. In LLM serving, variable-length sequences cause severe external fragmentation of the KV cache. PagedAttention solves this by allocating memory in fixed-size blocks (pages), eliminating fragmentation and allowing memory to be shared (e.g., for prompt sharing between requests).

The two primary performance metrics for model serving. Latency is the time to process a single request. Throughput is the number of requests processed per unit of time. PagedAttention primarily optimizes for throughput by enabling higher GPU utilization through efficient continuous batching and reduced memory waste. It can also reduce latency in high-load scenarios by preventing queueing delays.