Large Language Model (LLM) inference is often limited by GPU memory, not just computing power. A significant portion of this memory is consumed by the Key-Value (KV) cache, which grows with every token generated. The paged attention technique used in the vLLM system addresses this memory bottleneck directly. By intelligently managing the KV cache, it allows more requests to run concurrently on the same hardware, leading to higher overall throughput.
This article explains the mechanics of the PagedAttention algorithm, how it fits into the vLLM serving architecture, and how it compares to other methods.
Key takeaways
- PagedAttention is a memory management algorithm that organizes an LLM's KV cache into non-contiguous, fixed-size blocks, inspired by virtual memory in operating systems (according to the original paper).
- It drastically reduces memory waste by allocating memory in small chunks on demand, rather than reserving one large, contiguous memory block for each request's maximum possible length.
- vLLM is a high-throughput serving system built around PagedAttention. It combines the algorithm's memory efficiency with a dynamic scheduler to process more requests simultaneously.
- A "block table" is the core data structure that maps a request's logical token blocks to their physical locations in GPU memory (as defined in the vLLM documentation).
- The benefits are most significant for workloads with varying sequence lengths, long contexts, and complex decoding methods like beam search.
What Problem Does PagedAttention Solve? The Trouble with Contiguous Caches
PagedAttention solves the severe memory waste caused by traditional KV cache management during LLM inference. In older systems, memory for each request was reserved as a single, contiguous block. This simple approach creates significant fragmentation and inefficiency, which limits the number of concurrent users a server can handle.
LLM inference is a memory-bound process. The KV cache, which stores intermediate attention data, can consume most of a GPU’s memory during generation. You can learn more about its function in our guide to the KV cache in LLMs.
Traditional serving systems pre-allocate a contiguous memory block for each request. To be safe, this block must be large enough to hold the KV cache for the maximum possible sequence length (e.g., 4096 or more tokens). This leads to two major problems:
Internal Fragmentation: Most sequences finish long before reaching the maximum length. As an illustrative calculation, if a system reserves space for 4096 tokens but a request only generates 200, nearly 95% (
(4096 - 200) / 4096) of the memory allocated for that specific request sits idle and wasted. This is internal fragmentation—unused memory within an allocated block.External Fragmentation: As requests of different sizes start and finish, they leave holes in the GPU memory. A new request might fail if the system cannot find a single contiguous block large enough for it, even if the total amount of free memory is sufficient. This is external fragmentation—free memory that is broken into small, unusable pieces.
This wasted memory is the primary bottleneck that PagedAttention was designed to eliminate. By avoiding large, contiguous allocations, it allows the system to pack more requests into memory and increase overall throughput.
How PagedAttention Works: From Virtual Memory to GPU Blocks
PagedAttention manages the KV cache by dividing it into small, fixed-size blocks and using a lookup table to track their locations. This method, inspired by virtual memory paging in operating systems, avoids the need for large, contiguous memory allocations and allows for flexible, on-demand memory use (as detailed in the vLLM paper).
The core idea is to decouple the logical sequence of tokens from their physical storage in GPU memory. A program on your computer sees its memory as a single, continuous space (virtual memory), but the operating system actually stores it in scattered physical RAM chips. PagedAttention applies the same concept to the KV cache.
Here is the process, step by step:
Partition into Blocks: The system logically partitions each sequence's KV cache into "blocks." A block is a fixed-size container that can hold the key and value tensors for a set number of tokens, such as 16. The block size is a configurable parameter (a configurable vLLM parameter).
Create a Physical Pool: At startup, vLLM allocates a large pool of GPU memory and divides it into thousands of physical blocks of the same fixed size. This pool serves as the total available memory for all KV caches.
Build the Block Table: Each incoming request is assigned a "block table." This is a lookup table that maps the logical blocks of the sequence to physical blocks in the memory pool. For example, it might state that logical block #0 of a sequence is stored in physical block #58, logical block #1 is in physical block #1024, and so on.
Allocate On-Demand: When a request arrives, the system processes its prompt tokens (the prefill step). The memory allocator assigns just enough physical blocks from the pool to store the prompt's KV cache and records these assignments in the sequence's block table. As the model generates new tokens one by one (the decode step), a new physical block is allocated only when the previous one becomes full.
Compute Attention with Indirection: During the attention calculation, the custom GPU kernel cannot assume a contiguous memory layout. It performs an indirection step: it first consults the sequence's block table to look up the physical memory addresses for the required logical blocks. This lookup adds a small computational overhead compared to directly accessing a single, large block. Only after resolving these addresses can the kernel fetch data from scattered memory locations to perform the computation.
This on-demand, block-based allocation nearly eliminates internal fragmentation. Memory is only used as needed, freeing the system to serve many more requests simultaneously.
Efficient Sharing with Copy-on-Write
Beyond reducing waste, the block-based structure enables efficient sharing of memory. For complex decoding strategies like beam search or parallel sampling, multiple candidate sequences can share the same initial KV cache blocks. When one branch diverges and generates a different token, PagedAttention uses a copy-on-write mechanism. It only duplicates the specific block being modified, while all other, unchanged blocks remain shared. This significantly reduces memory consumption for parallel generation paths (a memory-saving feature of the architecture).
A Worked Example: Mapping Tokens to Memory Blocks
To make this concrete, let's trace a single request step-by-step. Imagine a block size of 4 tokens.
A user sends a prompt with 9 tokens: "The quick brown fox jumps over the lazy dog".
Prompt Processing (Prefill): The system processes these 9 tokens at once. To store their KV cache, it needs
ceiling(9 / 4) = 3logical blocks.- Logical Block 0: Holds tokens 1-4
- Logical Block 1: Holds tokens 5-8
- Logical Block 2: Holds token 9 (partially filled)
Physical Allocation: The vLLM block allocator finds three free physical blocks from its global pool. Let's say it assigns physical blocks #7, #23, and #15.
Block Table Creation: The system creates a block table for this sequence that maps the logical blocks to their new physical homes:
Logical Block 0 -> Physical Block #7Logical Block 1 -> Physical Block #23Logical Block 2 -> Physical Block #15The physical blocks #7, #23, and #15 can be anywhere in GPU memory; they do not need to be next to each other.
Decoding Step 1 (Token #10): The LLM generates its first new token. The KV cache for this 10th token needs to be stored. The system sees that the last allocated block (Physical Block #15) has space. It now holds KV data for tokens 9 and 10. The block table does not change.
Decoding Steps 2 & 3 (Tokens #11, #12): The same process repeats. The KVs for tokens 11 and 12 are added to Physical Block #15. After token #12 is stored, Physical Block #15 is now full (holding tokens 9, 10, 11, and 12). The block table remains unchanged.
Decoding Step 4 (Token #13): The model generates the 13th token. The system tries to store its KV cache in the last block, but Physical Block #15 is full. The allocator is called again. It grabs a new free block—say, #42—from the pool.
Block Table Update: The block table for the sequence is updated to map the next logical block:
Logical Block 3 -> Physical Block #42The KV cache for token #13 is written into this new block. The generation process continues, allocating new blocks only as they are needed.
How Does vLLM Use PagedAttention in Its Architecture?
PagedAttention is the core memory management algorithm within the broader vLLM serving system, but vLLM's high performance comes from combining this algorithm with a sophisticated scheduler. The memory efficiency of PagedAttention enables the scheduler to make better decisions, leading to higher overall throughput.
The vLLM architecture has several key components that work together (according to the project's architecture design):
- KV Cache Manager: This component implements the PagedAttention algorithm. It manages the pool of physical memory blocks, handles allocation and deallocation requests, and maintains the block tables for every active sequence.
- Scheduler: This is the brain of the operation. It decides which requests to include in the next processing batch. Unlike simpler systems that use static batching, vLLM's scheduler uses continuous batching.
- Model Execution Workers: These are the processes that run the LLM on the GPUs, performing the actual computations.
PagedAttention and the scheduler are deeply intertwined. At each step, the scheduler queries the KV cache manager to see how many free physical blocks are available. Based on this information, it builds a batch of requests. Because PagedAttention minimizes memory waste, more free blocks are available at any given time.
This allows the scheduler to add new requests to a running batch the moment other requests finish and free their blocks. This process, often called continuous batching, keeps the GPU constantly busy with useful work. PagedAttention's efficient memory use directly enables this dynamic and highly-utilized batching strategy, which is a primary driver of vLLM's impressive throughput gains (a key finding of the original paper).
PagedAttention vs. Alternatives: How Does It Compare?
PagedAttention is a specific strategy for managing memory, and it's useful to compare it with other techniques in the LLM ecosystem.
| Technique | Primary Goal | Memory Allocation | Key Characteristic |
|---|---|---|---|
| Contiguous Allocation | Simplicity | One large, contiguous block per request. | Simple to implement but suffers from high internal and external fragmentation, leading to wasted memory. |
| PagedAttention | Memory Efficiency | Small, fixed-size blocks from a shared pool. | Uses a block table for non-contiguous storage, nearly eliminating fragmentation and enabling efficient sharing. |
| vAttention | Alternative Design | Dynamic management of contiguous allocations. | A different approach to dynamic memory management that does not use the block-based paging model of PagedAttention (as described by Microsoft Research). |
| FlashAttention | Computation Speed | Not a memory manager. | An I/O-aware attention algorithm that optimizes the computation itself by restructuring memory access, reducing reads/writes to slow VRAM. |
A common point of confusion is the difference between PagedAttention and FlashAttention. They are not mutually exclusive and solve different problems. PagedAttention optimizes how the KV cache is stored and managed, while FlashAttention optimizes how the attention score is calculated. A system can potentially use both: PagedAttention for memory allocation and a FlashAttention-style kernel for the computation.
What Are the Limitations and Trade-offs?
While powerful, PagedAttention is not a magic bullet and comes with its own set of trade-offs.
- Kernel Complexity and Overhead: The attention kernel must be custom-built to handle non-contiguous memory. Instead of reading from a single memory slab, it must perform lookups in the block table to find the physical addresses of the required keys and values. This indirection adds a small amount of computational overhead.
- Block Size Tuning: The size of the memory blocks is a critical tuning parameter.
- Small blocks reduce wasted memory in partially filled blocks but increase the size of the block tables and the number of lookups required.
- Large blocks reduce metadata overhead but can increase waste if sequences often end with a block mostly empty. The optimal size can vary based on workload and hardware (according to performance analyses).
- Not Always the Fastest Kernel: PagedAttention prioritizes memory efficiency to enable higher throughput at the system level. However, the computation kernel itself might not always be the fastest for a single, isolated attention calculation. For instance, a 2024 study reported that in some scenarios, an evaluated PagedAttention kernel could be slower than a highly optimized contiguous kernel like FlashAttention-2.
PagedAttention is most beneficial for serving workloads with high concurrency and diverse request lengths. For offline, single-batch processing where all sequences have the same length, the benefits of dynamic allocation are less pronounced, and a simpler contiguous allocation strategy might be sufficient.
What to learn next
- Semantic Caching LLM: A Production Guide - Learn how a semantic caching LLM system reduces cost and latency. This guide covers safe implementation, choosing thresholds, and avoiding c
- vLLM vs TensorRT LLM: Which Inference Engine is Better? - Get a clear comparison of vLLM vs TensorRT LLM. This guide explains key differences, helping you choose the best LLM inference engine for yo
- How LLM Inference Works: From Prompt to Token Stream: Understand the two main phases of generation—prefill and decode—and how they impact performance.
- Continuous Batching LLM: How It Works & Boosts Throughput: Learn more about the scheduling technique that PagedAttention enables to achieve high throughput.
- Transformer Architecture Explained: From Tokens to Logits: Go back to the fundamentals of the model architecture that powers today's LLMs.
Sources and further reading
- Efficient Memory Management for Large Language Model Serving with PagedAttention
- Paged Attention — vLLM documentation
- vAttention: Dynamic Memory Management for Serving LLMs without PagedAttention
- BlockTable — vLLM documentation
- Up to 2.8× slower than FlashAttention-2 for the evaluated PagedAttention kernel in one later study
