PagedAttention

Traditional KV cache allocation reserves a contiguous block of memory for the maximum possible sequence length of each request, leading to severe internal fragmentation as most sequences are shorter. PagedAttention allocates memory in fixed-size blocks (pages). Only the blocks actually containing KV data are allocated, dramatically reducing wasted memory. This allows more concurrent requests to be served on the same GPU hardware.

PagedAttention's block-level abstraction enables powerful optimizations:

• Shared Prompts: In multi-tenant or chatbot scenarios, many requests may share a common system prompt or context. PagedAttention allows these shared tokens' KV caches to be stored in read-only memory blocks, referenced by all relevant requests. This eliminates redundant storage and computation.
• Beam Search: During beam search, multiple candidate sequences share a common prefix. PagedAttention stores the prefix's KV cache once, with all beams holding references to the same physical blocks.

Real-world LLM workloads are highly variable; input prompts and output generations have unpredictable lengths. PagedAttention's paged design is inherently flexible:

• New blocks are allocated on-demand as generation progresses.
• Finished requests release their blocks immediately, making memory available for new requests.
• This dynamic allocation is analogous to an operating system managing heap memory for processes, providing optimal utilization for irregular, real-time workloads.

By drastically reducing memory waste, PagedAttention directly increases the number of concurrent requests a single GPU can handle. This translates to higher Tokens Per Second (TPS) at the system level and lower cost per token. For example, vLLM demonstrated throughput increases of up to 24x compared to prior systems like Hugging Face Transformers by leveraging PagedAttention to serve more users simultaneously without additional hardware.

PagedAttention's mechanism is a direct translation of OS virtual memory concepts to the KV cache:

• KV Cache Block = Physical Memory Page: A fixed-size unit of storage.
• Logical Block Table = Page Table: Each request maintains a table mapping its logical token positions to physical block IDs.
• Block Allocation = Memory Allocation: The system manages a free list of available blocks. This proven abstraction provides a robust, predictable foundation for managing the LLM's most memory-intensive component during inference.

PagedAttention manages the KV (Key-Value) cache by dividing it into fixed-size blocks, analogous to memory pages in an operating system. These blocks are allocated non-contiguously in physical GPU memory.

• Block Table: Each request's sequence is tracked via a block table that maps logical blocks to physical memory addresses.
• On-Demand Allocation: Blocks are allocated only when new tokens are generated, eliminating pre-allocation waste.
• Shared Memory: Identical prompt prefixes across requests can share the same physical blocks, a powerful form of memory deduplication. This virtual memory abstraction is what enables vLLM to achieve near-zero memory waste and support very long context windows efficiently.

The primary engineering benefit of PagedAttention is the drastic reduction of memory fragmentation, which directly translates to cost savings and higher concurrency.

• Traditional Problem: Sequential, contiguous allocation for variable-length sequences leads to unusable gaps between requests (external fragmentation) and wasted reserved space within requests (internal fragmentation).
• PagedAttention Solution: By using small, fixed-size blocks, free memory is pooled and can be allocated to any request. This eliminates external fragmentation and minimizes internal waste to at most one block per request.
• Result: GPU memory utilization can approach 99%, allowing more concurrent requests or longer contexts on the same hardware.

PagedAttention's block-level abstraction unlocks sophisticated serving optimizations that are difficult or impossible with contiguous cache management.

• Shared Prompts: As mentioned, common system prompts or few-shot examples are stored once in physical memory and referenced by multiple user requests.
• Parallel Sampling: Techniques like beam search or parallel sampling of multiple outputs from a single prompt can share the cached prompt context blocks.
• Efficient Cache Eviction & Swapping: The block table enables LRU (Least Recently Used) or other policies to evict or swap out less-used blocks to CPU RAM, enabling effective management of extremely long contexts that exceed GPU memory.

PagedAttention is highly synergistic with continuous batching (or in-flight batching), forming the core of modern serving stacks.

• Dynamic Workloads: Continuous batching groups requests of different lengths and adds new requests to a running batch. PagedAttention's non-contiguous allocation is essential to handle this dynamic, heterogeneous mix efficiently.
• Eliminating Padding: Without PagedAttention, variable-length sequences in a batch require padding to the longest sequence, wasting compute and memory. PagedAttention's block-based approach inherently requires no padding for the KV cache.
• Combined Benefit: Together, they maximize GPU utilization for both compute (through batching) and memory (through paging), delivering optimal throughput.

The success of PagedAttention has influenced the design of other inference systems and sparked research into related optimizations.

• Inspired Systems: Frameworks like LMDeploy (by InternLM) and TensorRT-LLM have incorporated similar block-based KV cache management strategies, validating the core concept.
• Research Extensions: Work like FlashInfer explores kernel-level optimizations for PagedAttention-like operations. VLLM's Blocked KV Cache design is a direct influence.
• Hardware Considerations: The algorithm influences thinking about future GPU memory architectures, highlighting the importance of efficient, fine-grained memory management for LLM inference. This ecosystem growth confirms PagedAttention as a foundational primitive for efficient LLM serving.

The KV Cache (Key-Value Cache) is the memory structure that PagedAttention manages. During autoregressive generation, a transformer model computes and stores key and value tensors for each previously generated token. The KV cache prevents redundant computation for these past tokens, drastically reducing latency. However, it can consume gigabytes of memory per concurrent request, making its efficient management—via techniques like PagedAttention—critical for high-throughput serving.

• Purpose: Stores intermediate computations to avoid recomputation.
• Memory Footprint: Grows linearly with sequence length and batch size.
• Optimization Target: The primary target for memory savings in inference engines like vLLM.

Continuous Batching (or in-flight batching) is an inference optimization technique that dynamically adds new requests to a running batch as previous requests finish generation. This maximizes GPU utilization by eliminating idle time. PagedAttention complements continuous batching by efficiently handling the variable and unpredictable memory demands of this dynamic scheduling.

• Mechanism: Batches are updated in real-time, not statically formed.
• Efficiency: Achieves much higher GPU utilization than static batching.
• Synergy with PagedAttention: Allows flexible memory allocation for requests entering and exiting the batch at different times.

Memory Fragmentation occurs when free memory is broken into small, non-contiguous blocks that are unusable for larger allocations. In LLM serving, traditional KV cache management leads to severe fragmentation as variable-length sequences finish, leaving gaps in GPU memory. PagedAttention solves this by using a paging system, analogous to operating systems, where cache blocks can be allocated non-contiguously and reused.

• Problem: Wastes up to 80% of reserved KV cache memory in naive systems.
• Analogy: Similar to disk fragmentation in hard drives.
• Solution: PagedAttention's block-based management allows efficient reuse of freed memory.

Inference Cost is the total financial expenditure of running a trained model to make predictions. For LLMs, this is dominated by GPU memory and compute time. PagedAttention directly reduces inference cost by allowing more concurrent requests (higher throughput) to run on the same GPU hardware, thereby lowering the cost per token.

• Drivers: GPU instance hours, memory footprint, and throughput.
• Key Metric: Cost per thousand tokens ($/1K tokens).
• Impact of PagedAttention: Increases tokens per second (TPS) for a fixed hardware budget, driving down unit economics.

Tokens Per Second (TPS) is the primary throughput metric for LLM serving, measuring how many output tokens a system can generate per second. Higher TPS means lower latency and cost for users. PagedAttention boosts TPS by enabling higher levels of request concurrency within the same GPU memory constraints, as it minimizes wasted memory from fragmentation.

• Business Impact: Directly correlates with user experience and infrastructure cost.
• Optimization Goal: Maximize TPS for a given hardware profile.
• Influence of Memory Management: Efficient KV cache usage (via PagedAttention) is a major lever for improving TPS.