PagedAttention

In traditional KV cache allocation, memory is reserved as a contiguous block for each request's maximum possible sequence length, leading to significant internal fragmentation as most sequences are shorter than the maximum. PagedAttention allocates memory in fixed-size blocks (e.g., 16 tokens). The KV cache for a sequence occupies only the exact number of blocks needed, with the final block partially filled. This results in near-zero waste, allowing more concurrent requests to fit in GPU memory.

PagedAttention's block-based design allows the KV cache to be shared across multiple sequences or beam search candidates. This is crucial for two scenarios:

• Prompt Sharing: In a multi-tenant server, if two users submit the same system prompt, a single set of KV cache blocks can be referenced by both request contexts.
• Beam Search: Different beams in a search can share the KV cache blocks for their common prefix, avoiding duplicate storage. This sharing reduces total memory consumption and decreases memory I/O, directly improving throughput.

Just like virtual memory, PagedAttention decouples the logical sequence of tokens from their physical storage. A sequence's KV cache is represented by a logical block table that maps to physical blocks which can be scattered throughout GPU memory. This allows:

• Flexible Allocation/Deallocation: Blocks for completed sequences can be freed and reused without complex memory compaction.
• Efficient Cache Eviction: For sequences exceeding the context window, a policy like Least-Recently-Used (LRU) can evict individual blocks, not entire sequences.
• Offloading to CPU/NVMe: "Cold" blocks can be swapped to slower, larger memory tiers, enabling effectively infinite context lengths.

PagedAttention is the foundational enabler for high-performance continuous batching (also known as iterative or rolling batching). Because memory is allocated in small, independent blocks:

• Dynamic Joining/Exiting: New requests can be added to the batch by allocating new blocks. Completed sequences free their blocks, making room for others, without stopping the batch.
• Variable Sequence Lengths: The batch can efficiently contain requests with vastly different context lengths (e.g., 50 tokens vs. 8000 tokens) because each uses only the blocks it needs. This leads to near-100% GPU utilization and dramatically higher throughput compared to static batching.

PagedAttention directly applies decades of operating system research to the KV cache problem. Key parallels include:

• Block/Page Table: The logical block table acts as a page table, translating logical token positions to physical block addresses.
• Demand Paging: Blocks can be allocated on-demand as the sequence grows, rather than pre-allocating the maximum.
• Copy-on-Write: For shared prompts, blocks are marked as read-only; if a sequence needs to modify a shared block (e.g., during fine-grained attention), a private copy is created. This proven architecture provides a robust, predictable framework for cache management.

By managing memory in fixed-size pages, PagedAttention facilitates techniques for handling sequences that exceed physical GPU memory. This is critical for applications requiring long-context windows, such as:

• Document analysis and summarization of lengthy reports or codebases.
• Long-form conversational agents that maintain context over extended dialogues.
• Research and legal review tools that process multi-document inputs. The paging mechanism allows for efficient KV cache offloading to CPU RAM or NVMe when context length outstrips GPU VRAM.

In cloud-based Model-as-a-Service (MaaS) platforms, PagedAttention optimizes resource sharing across multiple users and requests. Its block-based management enables:

• Strong performance isolation by preventing one user's long sequence from fragmenting memory for others.
• Predictable memory allocation, allowing service providers to accurately provision capacity and guarantee Quality of Service (QoS).
• Efficient context switching between heterogeneous workloads with varying sequence lengths and request patterns.

The paging abstraction simplifies the implementation of complex, memory-efficient attention mechanisms that rely on non-contiguous or dynamic KV cache access patterns. Examples include:

• Sliding Window Attention, where only a local window of recent tokens is kept active.
• StreamingLLM frameworks, which use attention sink tokens to stabilize infinite-length generation.
• Speculative decoding, where the KV cache for draft tokens must be managed separately from the target model's verification pass.

PagedAttention has become a canonical reference in research for optimizing systems operating in a memory-bound regime. It demonstrates how OS-inspired virtual memory concepts can solve modern hardware bottlenecks. This influences work on:

• Novel caching policies for dynamic neural network states.
• Scheduling algorithms that are cache-aware to improve locality.
• Hardware-software co-design for future accelerators, where efficient, fine-grained memory management is a first-class design constraint.

The KV cache is a memory buffer that stores computed key and value tensors from previous tokens during the autoregressive decoding phase of a transformer. Its primary purpose is to eliminate redundant computation: instead of recomputing keys and values for all prior tokens on each new generation step, the model reads them from this cache, dramatically reducing latency.

• Structure: For a model with multiple layers and attention heads, the cache holds separate key and value tensors for each.
• Memory Footprint: The cache size scales linearly with batch size, sequence length, and model dimensions, making it a primary bottleneck for long-context inference.
• Management Challenge: Efficiently allocating, sharing, and evicting data in the KV cache is the central problem that PagedAttention solves.

Continuous batching is a dynamic request scheduling technique that maximizes GPU utilization by allowing new inference requests to join a running batch and completed sequences to exit independently. This is in contrast to static batching, where the entire batch must finish before a new one can begin.

PagedAttention is the enabling technology for efficient continuous batching in systems like vLLM. It allows:

• Non-contiguous Memory Allocation: Requests of different sequence lengths can share GPU memory without internal fragmentation.
• Independent Completion: When one sequence in the batch finishes generation, its allocated cache blocks can be immediately freed and reused for a new request, without stalling the entire batch.

vLLM is a high-throughput, memory-efficient open-source inference serving engine for large language models. It is the canonical implementation that popularized the PagedAttention algorithm.

• Core Innovation: vLLM treats the KV cache as virtual memory, dividing it into fixed-size blocks. This allows for zero internal fragmentation and efficient sharing of physical memory across multiple requests.
• Performance Impact: By eliminating wasted memory, vLLM can support batch sizes that are 2-4x larger than previous systems, leading to dramatically higher throughput.
• Ecosystem Role: It serves as a reference architecture for modern, efficient inference serving, demonstrating the practical application of OS-inspired memory management to AI systems.

An attention sink is a phenomenon observed in streaming language models, where the initial tokens of a sequence (often the first few) receive disproportionately high attention scores from all subsequent tokens. This effect is leveraged by frameworks like StreamingLLM to enable infinite-length generation without model retraining.

• Connection to PagedAttention: Managing very long contexts requires efficient cache policies. The attention sink concept informs cache eviction strategies; evicting middle tokens while preserving the initial "sink" tokens can maintain generation quality far beyond the model's original training window.
• Practical Implication: Understanding attention sinks is crucial for designing systems that handle long dialogues or documents, as it dictates which parts of the KV cache are most critical to retain.

Transformer inference is split into two distinct computational phases:

• Prefill Phase: The initial, compute-bound stage where the entire input prompt is processed in parallel. All prompt tokens attend to each other, and the initial KV cache for the entire prompt is computed and stored.
• Decode Phase: The subsequent, memory-bound stage where tokens are generated one-by-one (autoregressively). In this phase, the model attends to the cached keys and values from all previous tokens to predict the next token.

PagedAttention's Role: It optimizes memory management primarily for the decode phase, where efficient, random-access reads from the KV cache are the performance bottleneck. The non-contiguous paging allows the decode phase to handle highly variable sequence lengths efficiently within a continuous batch.

A system is in a memory-bound regime when its performance is limited by the speed of memory accesses (bandwidth or latency) rather than by the speed of its arithmetic logic units (ALUs). Autoregressive decoding in large language models is a classic example of a memory-bound workload.

• The Bottleneck: The primary operation during decoding is attention, which involves reading the massive KV cache from GPU memory. The time spent waiting for this data often far exceeds the time spent on the actual matrix multiplications.
• PagedAttention as a Solution: By organizing the cache into blocks and reducing fragmentation, PagedAttention improves effective memory bandwidth utilization. It ensures that memory fetches are as efficient as possible, directly alleviating the memory-bound bottleneck and increasing decode throughput.