PagedAttention: Solving LLM KV Cache Memory Fragmentation

In the previous two chapters, we explored how KV caches accelerate autoregressive generation by avoiding redundant computation, and we examined the substantial memory costs this optimization incurs. As we saw, a single 70B parameter model can require over 2.5 GB of KV cache memory per sequence at full context length. When serving multiple concurrent requests, this memory demand becomes the primary bottleneck limiting throughput. The KV cache was supposed to be a performance win, and it is, but the way most systems implemented it created a new and equally severe problem that canceled out much of that gain.

The problem is memory fragmentation. Even when the GPU has sufficient total free memory, the way that memory is allocated and deallocated can leave large portions of it unusable. Imagine a parking lot where every car must park in a space exactly as large as the longest car ever recorded, even if the actual car is a compact. Most of that parking lot will be empty, and yet you'll keep turning away new cars because there's "no room." That is essentially what happens with traditional KV cache implementations, which can waste 60-80% of available GPU memory, dramatically reducing the number of sequences a server can process simultaneously.

PagedAttention, introduced by the vLLM project in 2023, solves this fragmentation problem by borrowing a basic concept from operating systems: virtual memory with paging. Instead of allocating contiguous memory blocks for each sequence's KV cache, PagedAttention breaks the cache into fixed-size pages that can be stored anywhere in memory. A simple translation table then maps the logical view of each sequence (a tidy, contiguous cache) to the physical reality (blocks scattered wherever space is available). This simple but powerful idea enables near-optimal memory utilization and has become the foundation for most modern LLM serving systems.

The impact of this design choice is concrete and dramatic. Systems using PagedAttention routinely achieve 2-4x higher request throughput compared to naive implementations, using exactly the same hardware and model. This improvement comes entirely from using memory more intelligently, not from any change to the model itself or to the underlying attention algorithm. You do not need a bigger GPU; you need a smarter allocator.

In this chapter, we build from the ground up. We start with why traditional allocation fails so badly, work through the paging concept in detail, examine how the attention algorithm must be modified to accommodate non-contiguous storage, and then look at how vLLM puts all these pieces together into a production serving system. Along the way, we work through concrete numerical examples and build a simulator that makes the abstract concepts tangible. By the end, you will understand what PagedAttention does, why it works, and when its trade-offs matter.

To understand why fragmentation occurs, we need to examine how traditional KV cache systems allocate memory. When a new request arrives, the system must reserve memory for the KV cache that will grow as tokens are generated. But here is the challenge: the system does not know in advance how long the final sequence will be. A user asking for a one-sentence summary and a user asking for a detailed technical report both arrive as requests, and the system must accommodate both without knowing which is which ahead of time.

The naïve solution is to reserve the maximum possible amount of memory upfront. If your model supports 4,096 tokens, reserve space for 4,096 KV pairs for every single request, regardless of what the request will generate. This approach is safe in the sense that you will never run out of space mid-generation, but it is profligate. Most requests generate only a few hundred tokens, leaving the large majority of the reserved memory permanently empty.

Think of traditional KV cache allocation as a hotel that gives every guest the presidential suite, regardless of how long they are staying. A business traveler checking in for one night gets the same 3,000-square-foot suite as a family staying for a week. The hotel (your GPU) fills up quickly, and yet most of the space is sitting completely empty. The correct solution is to give guests rooms that match their actual needs, and expand to a larger room only if they ask for more space. That is exactly what PagedAttention does.

Two distinct types of fragmentation compound to make this problem severe. Internal fragmentation occurs when the unused portion within a single reservation is wasted. External fragmentation occurs when completed requests free their reservations, leaving gaps in memory that are too small or too scattered to accommodate new requests. Both types are endemic to contiguous-allocation schemes, and together they can make a GPU with 40 GB of memory behave as if it has only 8-16 GB available.

Traditional systems handle uncertainty about output length by pre-allocating memory based on the maximum possible sequence length. If your model supports 4,096 tokens, the system reserves space for all 4,096 KV pairs for each sequence, even if most requests only generate a few hundred tokens. The logic is defensible: if you don't reserve enough space, generation will fail or require expensive memory reallocation mid-flight. But the cost is enormous wasted capacity.

The issue goes deeper than just wasted space on the current request. Because all that reserved memory is locked up, it cannot be used for other requests. A GPU that could theoretically serve forty concurrent requests might be limited to eight or ten, because each request holds ninety percent of its reservation empty. This directly translates to lower throughput: fewer requests per second, higher latency for queued requests, and underutilized compute hardware.

External fragmentation is the second and often more damaging type of memory waste. It occurs not within a single allocation but in the gaps between allocations that form as requests complete and free their memory. Even if every individual request used every byte of its reservation perfectly, the pattern of arrivals and completions over time would still fragment the available memory.

Consider what happens over time in a busy serving system. Requests A, B, C, and D all start at roughly the same time and are allocated contiguous memory blocks. Then A finishes, freeing its block. Then C finishes, freeing its block. Now the memory looks like a checkerboard: used, free, used, free. A new request E arrives needing slightly more memory than either gap provides. The allocator cannot give E a single contiguous region, even though the total free space is more than sufficient.

Think of external fragmentation like trying to fit a long sofa into a truck where someone has already loaded boxes of equal size on each end, leaving two separate gaps in the middle. Each gap is half the sofa's length, but the sofa cannot be split, so it won't fit. The truck looks half-empty, but you cannot use the empty space for the furniture you have.

This is external fragmentation: the memory has 20 free slots, but they're split into two non-contiguous regions of 10 slots each. A new request requiring 12 contiguous slots cannot be served, even though sufficient total memory exists. In practice, with many concurrent requests starting and completing at different times, this fragmentation can become severe. The system will decline new requests not because it has run out of memory in any absolute sense, but because the available memory has been sliced into pieces too small to use.

Internal fragmentation compounds the problem further. Even if we could perfectly eliminate external fragmentation, we would still waste memory within every single allocation. When we allocate based on maximum sequence length but the actual sequence is shorter, the unused portion within the allocation is wasted for the duration of that request. This waste is guaranteed: unless every request uses exactly the maximum number of tokens, some capacity within each block is always empty.

Internal fragmentation is hardest to avoid with fixed pre-allocation because it is a direct consequence of not knowing the future. You reserved 4,096 tokens; the sequence only used 312. The remaining 3,784 tokens worth of KV cache memory sit idle, warming the GPU's memory banks while giving no useful work.

The combination of internal and external fragmentation means traditional serving systems achieve only 20-40% memory efficiency. For a GPU with 40 GB of KV cache capacity, this translates to effectively having only 8-16 GB available for actual use. The rest is statistically certain to be wasted, regardless of how cleverly you schedule requests. This is the problem PagedAttention was designed to solve, and it solves it by attacking the root cause: the requirement for contiguous allocation.

The solution comes from a technique that operating systems have used for decades: virtual memory with paging. Instead of requiring contiguous physical memory, paging allows data to be stored in fixed-size blocks (pages) scattered anywhere in memory, with a page table tracking where each piece resides. This technique changed operating system design in the 1960s, and it proves equally effective for managing KV caches in modern LLM serving systems.

The paging philosophy separates two views of memory. The logical view is the programmer's (or in our case, the sequence's) idealized picture: a contiguous array of token slots numbered 0 through N. The physical view is the hardware's reality: a collection of fixed-size blocks sitting at various physical addresses. A page table bridges these views by recording, for each logical block, which physical block holds that data. Neither view changes the other; the translation happens transparently at access time.

Think of paging like a library's call number system. Every book has a shelf number (logical address) that tells you how the library has organized its collection. But physically, books can be moved between branches, stored in offsite warehouses, or placed on reserve shelves. The catalog (page table) always knows where each book is, regardless of what call number it carries. You look up the call number, the catalog tells you the physical location, and you retrieve the book. You never need to know that your 600-series science book is physically sitting in a different wing from your neighboring 601-series book.

The key insight is that the fragmentation problem arose precisely because we required the logical and physical layouts to match. By decoupling them, we eliminate that requirement. Physical blocks can come from anywhere in the free pool, and the logical sequence still appears perfectly ordered through the page table. No fragmentation is possible because there is no requirement for contiguity in physical memory.

To understand how paging solves fragmentation, we must distinguish between logical and physical memory organization. A sequence's KV cache appears contiguous from a logical perspective, with tokens numbered 0, 1, 2, and so on. However, the actual physical storage need not mirror this logical arrangement. As long as we maintain a mapping that tells us where each piece of data resides in physical memory, we can store the data anywhere we like.

In the context of KV caches, paging works through four key concepts that build on each other:

• Physical blocks: GPU memory is divided into fixed-size blocks, each capable of holding a small number of KV pairs (typically 16 tokens worth). These blocks represent the actual memory locations where data is stored. All physical blocks are identical in size, which means any sequence can use any block.
• Logical blocks: Each sequence's KV cache is divided into logical blocks of the same size. These represent the abstract, contiguous view of the sequence's cache. Logical block 0 holds the first 16 tokens' KV pairs, logical block 1 holds the next 16, and so on.
• Block table: A mapping from logical block indices to physical block locations. This data structure is the key that enables the translation between the sequence's logical view and the scattered physical reality. Each sequence has its own block table, typically a short array of physical block indices.
• Dynamic allocation: Physical blocks are allocated only when needed, not pre-allocated. This on-demand approach means we never reserve memory for tokens that haven't been generated yet.

This approach decouples how we think about the data (logically contiguous per sequence) from how we store it (potentially scattered across physical memory). Let's implement a simulator to see these concepts in action:

No fragmentation. Request E was allocated using freed blocks from requests A and C, even though those freed blocks are non-contiguous in physical memory.

The key insight is that request E's blocks do not need to be contiguous in physical memory. The block table maintains the logical ordering, while physical blocks can be scattered anywhere. This eliminates external fragmentation entirely. When the simulator freed sequences A and C, their physical blocks returned to the free pool. Request E then claimed blocks from this pool, assembling its logical sequence from whatever physical locations happened to be available. From request E's perspective, it has a perfectly contiguous cache; the block table handles all the translation behind the scenes.

The block table is the data structure that enables this flexibility. For each sequence, it maintains an ordered list of physical block indices. The position in this list corresponds to the logical block number, while the value at that position indicates where in physical memory that block resides.

The address translation happens in two steps. First, given a token position $t$ in a sequence, we compute the logical block number as $\lfloor t / B \rfloor$, where $B$ is the block size in tokens. We also compute the offset within that block as $t \bmod B$. Second, we look up the physical block index by reading position $\lfloor t / B \rfloor$ from the block table. Combining the physical block address with the within-block offset gives us the exact location of the KV pair for token $t$.

where:

• $t$: the token index within the sequence (0-indexed)
• $B$: the block size in tokens (e.g., 16)
• $\text{block\_table}[\cdot]$: the array mapping logical block index to physical block index
• $\lfloor t / B \rfloor$: the logical block number for token $t$
• $t \bmod B$: the position of token $t$ within its logical block

This formula looks like pointer arithmetic, but the intuition is simple: divide the token index by the block size to find which block it belongs to, look up that block's physical location in the table, and then add the remainder to find the slot within the block. The formula applies identically regardless of how scattered the physical blocks are.

To visualize this concept, consider a sequence whose KV cache spans three logical blocks. The block table might contain the entries [7, 2, 15], showing that logical block 0 is stored in physical block 7, logical block 1 is stored in physical block 2, and logical block 2 is stored in physical block 15. When the attention mechanism needs to access the key for token 20 (which falls in logical block 1, since each block holds 16 tokens), it consults the block table, finds that logical block 1 maps to physical block 2, and reads the data from that location. The physical blocks are numbered 7, 2, and 15, which is a completely non-sequential arrangement, but the lookup is just an array index operation and takes constant time.

This indirection through the block table introduces a small amount of overhead: every memory access must first look up the physical location. However, this cost is negligible compared to the enormous benefits of eliminating fragmentation. The block table itself is small, typically fitting entirely in fast GPU memory or cache, making lookups extremely fast. For a sequence with 1,000 tokens and a block size of 16, the block table contains only 63 entries, each a single integer. The memory footprint of all block tables in a serving system is measured in kilobytes, not gigabytes.

With KV cache data potentially scattered across non-contiguous memory locations, we need to modify the attention computation to work with this new layout. The PagedAttention algorithm handles this by fetching keys and values according to the block table during attention calculation. This modification preserves the mathematical correctness of attention while accommodating the scattered physical layout.

The modification is conceptually straightforward: instead of indexing into a contiguous key-value tensor using the token position directly, we first compute the logical block number and within-block offset, look up the physical block from the block table, and then index into the KV cache using the physical block address. The attention score computation and the softmax normalization are identical to standard attention; only the data access pattern changes.

Think of the change as the difference between reading a book straight through versus reading it by consulting an index first. The content you read is identical, and you understand it the same way. The only difference is that you now follow a lookup step before accessing each page. The lookup is fast, and the content is exactly what standard attention would have read from a contiguous layout.

The key insight is that attention only needs the keys and values for a specific sequence, in order. It does not care what their physical addresses are, only what values they hold. The block table gives us exactly what we need: a translation from the logical "token 25 in sequence 3" to the physical "slot 9 in GPU memory block 47." Once we have the value, the computation proceeds identically.

In standard attention, keys and values are stored in contiguous tensors. For a sequence of length $n$, the attention mechanism computes a weighted sum of values based on the similarity between the query and keys:

where:

• $Q$: the query matrix, typically for the single current token being generated (shape $1 \times d_k$ for autoregressive decoding)
• $K$: the key matrix containing keys for all tokens in the context (contiguous tensor of shape $n \times d_k$)
• $V$: the value matrix containing values for all tokens in the context (contiguous tensor of shape $n \times d_v$)
• $d_k$: the dimension of the key vectors, used for scaling
• $d_v$: the dimension of the value vectors
• $n$: the sequence length (all previously generated tokens plus the prompt)
• $\text{softmax}$: the function that normalizes raw similarity scores into a probability distribution summing to 1

The formula consists of three computational stages. First, the dot product $QK^T$ measures the similarity between the query and each key. Intuitively, this operation asks: "how relevant is each previous token to the token we are currently generating?" Keys that are more similar to the query receive higher scores, showing greater relevance. The result is a vector of raw similarity scores, one for each position in the sequence.

The second stage applies the $\text{softmax}$ function to these raw scores. This normalization turns the arbitrary similarity values into a proper probability distribution that sums to 1. The softmax operation accentuates differences: high scores become relatively higher, and low scores become relatively lower. The output is the attention weights, which tell us how much to attend to each previous position. A weight of 0.8 on token 5 means we draw heavily from that token's value vector; a weight of 0.001 means that token contributes almost nothing to the output.

The third stage multiplies these attention weights by the value matrix $V$, computing a weighted average of the value vectors. Tokens with higher attention weights contribute more to the final output, while tokens with lower weights contribute less. This mechanism allows the model to selectively focus on the most relevant information from the entire context window, regardless of how long that window is.

The division by $\sqrt{d_k}$ in the formula ensures numerical stability. Without this scaling factor, the dot products between queries and keys tend to grow large as the dimension $d_k$ increases. Large dot products cause the softmax function to saturate, creating attention distributions that are nearly one-hot (all attention concentrated on a single token). The scaling factor keeps the dot products in a reasonable range, letting the softmax to produce more fine-grained attention patterns and improving gradient flow during training.

In PagedAttention, $K$ and $V$ are stored in non-contiguous blocks rather than contiguous tensors. The attention computation must gather the relevant blocks according to the block table. While the mathematical operation remains identical, the implementation must navigate the scattered physical layout:

This reference implementation shows the core idea: before computing attention, we gather the keys and values from their physical locations according to the block table. The attention computation itself remains unchanged. The gathering process iterates through logical block indices, looks up the corresponding physical block in the block table, and fetches the data from that physical location. Once all the keys and values are assembled into contiguous tensors, the standard attention formula applies exactly as before.

Let's verify that PagedAttention produces correct results even when blocks are scattered:

The reference implementation above gathers blocks into contiguous memory before computing attention. This defeats some of the purpose of paging, as it requires temporary memory allocation for the gathered keys and values. Production implementations like vLLM use custom CUDA kernels that compute attention directly on the paged data structure, avoiding the explicit gather step entirely.

The core challenge in writing these kernels is that standard attention kernels, including FlashAttention, assume contiguous tensors. A custom paged attention kernel must interleave block-table lookups with the attention computation, load blocks into fast shared memory, and then compute scores and apply the weighted sum, all without ever assembling a full contiguous KV tensor.

The key optimization insight is that attention can be computed incrementally as blocks are loaded, rather than requiring all data to be assembled first. This approach uses the online softmax algorithm (also known as the flash attention technique covered in the efficient attention chapter) to maintain numerical stability while processing blocks one at a time. The online softmax technique keeps a running maximum and a running sum, updating them as each new block is processed. This allows the kernel to compute the final attention output without ever needing to store all the keys and values in a contiguous buffer.

The necessary optimization is computing attention incrementally as blocks are loaded, rather than gathering all blocks first. By processing blocks sequentially and maintaining running statistics about the maximum score seen so far and the running normalization denominator, the kernel achieves the same mathematical result as gathering all keys first, but with dramatically reduced memory requirements. This combination of paging and incremental attention computation is what makes PagedAttention both memory-efficient and computationally practical on real hardware.

To make the block table mechanism concrete, let us trace a specific attention computation step by step. This example uses small numbers to keep the arithmetic manageable, but the same procedure applies at full production scale.

Suppose we have a sequence that has generated 38 tokens so far. The block size is 16 tokens. The sequence's block table contains three entries: [7, 2, 15]. We want to compute the attention score between the query for the current (39th) token and the key for token 20.

Step 1: Identify the logical block. Token 20 falls in logical block $\lfloor 20 / 16 \rfloor = 1$ (the second block, zero-indexed). Its position within that block is $20 \bmod 16 = 4$ (the fifth slot in the block).

Step 2: Look up the physical block. We read entry 1 from the block table: $\text{block\_table}[1] = 2$. So logical block 1 is stored in physical block 2.

Step 3: Compute the physical address. The key for token 20 lives at physical block 2, slot 4. If each block stores keys for one attention head in a contiguous sub-array of shape $[16, d_k]$, the exact memory address is: physical block 2's base address + 4 * (size of one key vector).

Step 4: Compute the attention score. Load the key vector from that physical address. Compute the dot product with the current query vector and divide by $\sqrt{d_k}$.

Step 5: Repeat for all 38 tokens. The same lookup applies for tokens 0 through 37. Tokens 0-15 live in physical block 7, tokens 16-31 live in physical block 2, and tokens 32-37 live in the first six slots of physical block 15. The scores for all 38 tokens are computed by following block-table lookups for each one.

Step 6: Apply softmax and weighted sum. Once all 38 scores are computed, apply softmax to get attention weights, then compute the weighted sum of value vectors (retrieved using the same physical block lookups).

The entire computation is mathematically identical to standard attention on a contiguous 38-token KV tensor. The only difference is that instead of reading keys[20] directly, we follow the two-level addressing: block table lookup, then within-block offset. On GPU hardware, this extra indirection costs only a tiny fraction of the total compute time because the block tables fit in shared memory or registers and the block lookups can be pipelined with the arithmetic.

Let us verify this numerically with a small concrete example:

The output confirms that the block-table indirection correctly assembles the full key and value tensors. Each token's KV data was retrieved by first mapping its position to a logical block number, then looking up the physical block, and finally reading from the correct within-block slot. The attention scores and the weighted output are computed identically to standard attention, and the result is mathematically exact regardless of how scattered the physical blocks are.

vLLM (Variably Large Language Model serving) is the framework that introduced PagedAttention. Understanding its architecture reveals how paging integrates into a complete serving system. vLLM is a full inference engine that uses PagedAttention as the foundation for higher-level serving features, including continuous batching, preemption, and beam search. Each of these features builds on the paging abstraction in a different way.

The vLLM architecture separates concerns cleanly. A scheduler decides which requests to process in each batch, a block space manager handles physical memory allocation, and the model executor runs the actual transformer forward pass using PagedAttention kernels. The three components communicate through block tables: the block space manager maintains them, and the executor reads them at inference time.

Think of vLLM as an operating system for LLM serving. Just as a general-purpose OS virtualizes CPU time and memory for many processes simultaneously, vLLM virtualizes GPU compute and KV cache memory for many concurrent inference requests. The paging mechanism is the memory virtualization layer, and the scheduler is the process scheduler. The model itself is just one of the "programs" running on this virtualized infrastructure.

The vLLM BlockSpaceManager handles physical block allocation. Its design closely parallels the page frame allocator in an operating system kernel: it maintains a pool of free physical blocks, allocates them on demand to sequences, and returns them to the pool when sequences complete. The reference-counting mechanism it uses for shared blocks (described in the copy-on-write section below) mirrors how operating systems handle shared memory pages.

The key design decision in the BlockSpaceManager is that allocation is always at block granularity, never sub-block. A sequence that needs 17 tokens gets two blocks (32 token slots), not one block plus 1 extra slot. This avoids the complexity of sub-block allocation while keeping internal fragmentation bounded to at most one partially filled block per sequence, which is a small and predictable overhead.

Freed blocks from sequence 1 are immediately available for reuse. The simulation illustrates the manager's efficiency: when Sequence 1 completes, its blocks are returned to the free pool in constant time, with no compaction or reorganization required. These reclaimed blocks are then available for Sequence 0's expansion or new requests, preventing the memory fragmentation issues seen in static allocation. The block table for Sequence 0 grows by three entries during generation, recording the three newly acquired blocks, and this growth is also constant-time per block.

One elegant feature of paged memory is letting copy-on-write (CoW) semantics for parallel decoding strategies like beam search. This technique addresses a basic challenge in beam search: multiple candidate sequences (beams) that share a common prefix would traditionally require duplicating the KV cache data for that prefix, even though it is identical across all beams. With a 48-token prompt and a beam width of 8, that is eight identical copies of 48 tokens' worth of KV data, consuming roughly 8x the necessary memory for that portion of the cache.

With copy-on-write, when multiple beams share a common prefix, they share the same physical blocks for that prefix rather than duplicating the data. The block manager tracks reference counts for each physical block. When a block has multiple references, multiple sequences are sharing that block. Only when a sequence needs to write new data to a shared block does the system create a private copy for that sequence. The write (the generation of new tokens that differ between beams) is the trigger for the copy; hence, copy-on-write.

To understand why this matters, consider a beam search with width 4. Without copy-on-write, each beam would need its own complete copy of the KV cache for the shared prefix, requiring 4x the memory for that prefix. With copy-on-write, all four beams point to the same physical blocks for the prompt. Memory is only allocated separately when the beams diverge and begin generating different tokens. Since beams often share long prefixes (the entire user prompt is shared), the savings can be substantial.

This 56% memory reduction highlights the efficiency of copy-on-write. By letting multiple beams share the same physical blocks for their common prefix, we significantly reduce memory footprint compared to duplicating the data for each beam. The savings become even more dramatic with longer prompts or wider beam widths, as the shared prefix represents a larger fraction of the total cache. A system serving beam search requests with prompt lengths of 512 tokens and beam width 8 could reduce its KV cache usage for those requests by over 90%, since nearly all of the cache is shared prefix.

Let's see how PagedAttention benefits manifest when using vLLM for inference. From a user perspective, vLLM exposes a simple API that feels like any other inference library. The PagedAttention machinery is entirely internal: you do not manage block tables or physical blocks directly. You simply submit requests, and vLLM handles all the memory management transparently.

Understanding the key parameters that control PagedAttention behavior helps you tune vLLM for your specific workload. The right settings depend heavily on your request distribution, target latency, and available hardware.

The key parameters for vLLM related to PagedAttention are:

• block_size: Number of tokens per physical block. Smaller blocks (8 or less) reduce internal fragmentation but increase block table size and lookup overhead. Larger blocks (32 or more) are more cache-friendly but waste more memory on partially filled final blocks. The default of 16 is a well-tuned starting point for most workloads.
• gpu_memory_utilization: Fraction of GPU memory reserved for KV cache. Higher values enable more concurrent sequences but leave less memory for activations and model weights. Setting this too high can cause out-of-memory errors during forward passes.
• max_num_seqs: Maximum concurrent sequences. PagedAttention enables much higher limits than traditional approaches because it eliminates fragmentation. In practice, this is often limited by the number of free blocks rather than any artificial cap.
• swap_space: CPU memory for block swapping when GPU memory is exhausted. vLLM can swap the KV cache blocks for lower-priority requests to CPU memory, letting the GPU to serve higher-priority requests. This adds latency for swapped requests but prevents starvation.

The interplay between these parameters is important. A large gpu_memory_utilization with a small block_size maximizes the number of sequences you can serve but increases the overhead per attention step. For latency-sensitive workloads, prefer slightly larger blocks and slightly lower utilization to reduce per-step overhead. For throughput-optimized batch serving, push utilization higher and accept more block table overhead.

Let's quantify the improvement PagedAttention provides over traditional allocation. This comparison is useful for understanding the magnitude of the problem that PagedAttention solves and for setting expectations about real-world throughput improvements.

The comparison is inherently unfair to traditional allocation because traditional allocation was never designed for dynamic request serving. It was designed for static, pre-known workloads. PagedAttention is specifically designed for the dynamic, variable-length nature of LLM inference. The numbers below reflect this design mismatch.

These results show the massive inefficiency of contiguous allocation. The exact values printed above come from the executed deterministic workload: paged allocation approaches full utilization while contiguous pre-allocation uses only a small fraction of its reserved capacity. The reported capacity multiplier shows how many more sequences the same memory could hold under this workload. It bears stressing that this improvement requires no changes to the model, no new hardware, and no change in the quality of the generated output. It is a pure systems optimization.

PagedAttention provides several interconnected benefits that compound to deliver substantial throughput improvements. Understanding how these benefits interact helps you predict the gains you will see in your own deployment and identify which workload characteristics make PagedAttention most effective.

The most direct benefit is higher batch sizes, which translates to higher GPU utilization. Modern GPUs are designed to process large batches efficiently; the hardware has enough parallelism to handle hundreds of requests simultaneously. Traditional KV cache allocation prevented systems from filling the GPU because memory was being wasted on fragmentation. PagedAttention removes that constraint. When batch size doubles, throughput typically more than doubles, because larger batches improve the arithmetic intensity of the computation and allow the GPU's memory bandwidth to be used more efficiently.

A secondary but important benefit is reduced latency for queued requests. With traditional allocation, a server that is nominally at capacity may have most of its GPU memory sitting empty. New requests queue up not because the GPU is busy computing but because there is nowhere to put their KV caches. PagedAttention eliminates this artificial queuing, allowing the server to accept and begin processing more requests immediately.

The most direct benefit is the ability to serve more concurrent sequences. With 5x better memory utilization, a serving system can batch 5x more requests simultaneously. Since transformer inference is typically compute-bound for large batches, higher batch sizes improve GPU utilization:

The throughput improvement demonstrates that memory efficiency directly translates to performance. By fitting more sequences into the GPU simultaneously, we operate in a regime of higher compute intensity, extracting more value from the hardware with each forward pass.

Paged memory enables continuous batching (which we will explore in an upcoming chapter), where new requests can join an ongoing batch as old ones complete. With traditional contiguous allocation, adding a new request requires finding a large enough contiguous memory region. With paging, new requests simply acquire free blocks as needed, and those free blocks can come from anywhere in the pool, including from requests that just completed.

This property is what makes continuous batching viable at scale. In a continuous batching system, the scheduler maintains a running batch and swaps completed sequences out while adding newly arrived sequences in. Each swap requires only returning the old sequence's blocks to the free pool and allocating new blocks for the new sequence. Both operations are constant time with paged allocation, making continuous batching tractable even at very high request rates.

Paged allocation significantly outperforms the traditional approach in dynamic settings. While the traditional allocator quickly becomes constrained by its small batch capacity, the paged allocator continuously reuses freed blocks, maintaining high throughput across the entire simulation. The difference in total processed requests reflects the basic capacity advantage that paging provides in dynamic workloads.

With paged memory, preempting a low-priority request to serve a high-priority one becomes straightforward and efficient. The preempted request's blocks can be either swapped to CPU memory or simply marked as reusable if the request can be restarted from the prompt. When the request resumes, it reloads its KV cache from the saved state and continues generation from where it left off.

This preemption capability enables sophisticated scheduling policies that traditional contiguous allocation cannot support. A system with preemption can guarantee quality-of-service for high-priority users, implement latency-sensitive queuing policies like SRPT (shortest remaining processing time), and avoid head-of-line blocking where one long request prevents shorter requests from being served. These scheduling capabilities are not specific to PagedAttention, but PagedAttention makes them practical by so that preemption and resumption are efficient operations rather than expensive memory copies.

While PagedAttention represents a major advancement in LLM serving efficiency, it comes with trade-offs and limitations worth understanding in depth. No technique is universally superior, and a clear-eyed view of PagedAttention's limitations helps you make better deployment decisions and anticipate where the technique may not deliver its advertised benefits.

The most basic overhead is the block table indirection itself. Every attention computation must look up physical block locations from the block table before reading the KV data. On GPU hardware, this means an extra pointer dereference per block, which disrupts the memory access pattern that standard attention kernels have been optimized for. Modern GPU memory systems work best with sequential, coalesced access patterns; paged access introduces non-sequential accesses that can reduce effective memory bandwidth. For very short sequences (50-100 tokens), this overhead can outweigh the memory savings, because short sequences fit in one or two blocks and the fragmentation savings are minimal. Most serving workloads involve longer sequences where the memory efficiency gains far exceed the indexing overhead, but if your workload consists primarily of short requests, you should benchmark carefully before assuming PagedAttention will help.

Block size selection presents a tuning challenge with no universally correct answer. Smaller block sizes (8 or fewer tokens per block) reduce internal fragmentation: the worst case is that the last block is only partially filled, so smaller blocks limit the maximum wasted space. But smaller blocks mean longer block tables, more block-table lookups per attention step, and potentially worse memory access locality as more physical block boundaries are crossed during a single attention computation. Larger block sizes (32 tokens or more) are more efficient for the memory access pattern but guarantee more waste at block boundaries. The default block size of 16 tokens in vLLM represents a carefully chosen balance, tuned against real serving workloads, but your specific workload distribution may benefit from a different value. Workloads with highly variable sequence lengths often benefit from smaller blocks; uniform-length workloads can use larger blocks without meaningful fragmentation cost.

Implementing PagedAttention from scratch is complex. Custom CUDA kernels must handle the non-contiguous memory access patterns efficiently while maintaining the performance characteristics of optimized attention implementations. The kernel must correctly implement the online softmax algorithm, handle partial last blocks, and coalesce memory accesses as much as possible across threads within the same warp. These are non-trivial requirements, and subtle bugs can produce incorrect results that are difficult to detect without careful testing. This is why you should use established frameworks like vLLM, TensorRT-LLM, or similar rather than implementing PagedAttention from scratch. The engineering investment to get a production-quality implementation right is substantial.

A subtler limitation is that PagedAttention addresses memory capacity constraints but not the basic memory bandwidth limitations of KV cache access. Even with perfect memory utilization, the KV cache still requires significant memory bandwidth to read during attention computation. For long sequences and large models, this bandwidth cost can be the dominant bottleneck, and no amount of clever allocation can reduce it. Techniques covered in later chapters, such as KV cache compression, quantization, and multi-query attention, complement PagedAttention by reducing the amount of data that must be transferred, rather than just improving how that data is laid out.

Finally, there is a coordination overhead in multi-GPU serving. When a model is distributed across multiple GPUs using tensor parallelism, each GPU must maintain consistent block tables for the KV shards it holds. Block allocation and deallocation must be coordinated across all GPUs simultaneously, which adds communication overhead and complexity. Single-GPU serving enjoys the simplest possible block management, while large multi-GPU deployments must handle this synchronization carefully to avoid inconsistencies.

PagedAttention transforms LLM inference efficiency by applying virtual memory principles to KV cache management. The key insights and techniques include:

• The fragmentation problem arises because traditional KV cache allocation reserves contiguous memory based on maximum sequence length. This causes internal fragmentation (unused space within allocations) and external fragmentation (scattered free blocks that cannot be combined). Together, these issues can waste 60-80% of available memory.

• Page-based allocation divides memory into fixed-size blocks that can be assigned to any sequence. A block table maps each sequence's logical blocks to their physical locations. This approach eliminates external fragmentation entirely and reduces internal fragmentation to at most one partial block per sequence.

• The PagedAttention algorithm modifies attention computation to work with non-contiguous KV storage. During attention, keys and values are gathered according to the block table. Optimized CUDA kernels perform this gathering efficiently using online softmax techniques, processing blocks one at a time without requiring an explicit gather step.

• Copy-on-write semantics enable memory-efficient beam search and other parallel decoding strategies. Sequences can share physical blocks for common prefixes, with new blocks allocated only when sequences diverge. This can reduce KV cache memory for beam search by 50% or more.

• Practical benefits include 2-4x higher throughput from increased batch sizes, support for continuous batching with dynamic request handling, preemption capabilities for priority scheduling, and near-optimal memory utilization that removes the capacity waste endemic to contiguous allocation.

• Limitations include block-table lookup overhead (small but non-zero), the complexity of choosing optimal block sizes, the implementation difficulty of production-quality paged attention CUDA kernels, and the fact that paging addresses capacity but not bandwidth.

These improvements have made PagedAttention the foundation of modern LLM serving systems including vLLM, TensorRT-LLM, and others. Understanding its design helps you configure these systems effectively, predict where they will perform well, and recognize the workload characteristics that determine how much benefit you will see in practice.

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about PagedAttention and memory management for LLM serving.