Paged Attention as a Memory Manager

Before PagedAttention, a 13B-parameter model running on an A100 80 GB card typically wasted between 60% and 80% of its KV-cache memory. The tokens were there; the GPU memory was available. The waste came from the same fragmentation that plagued early malloc implementations: blocks reserved upfront for sequences that turned out shorter than expected, gaps between allocations that were too small to reuse, and no mechanism for two requests to share identical prefix cache entries. Fixing that was not an algorithmic problem. It was a memory-management problem, and the solution lifted the idea almost verbatim from operating-system virtual memory.

The KV-Cache Fragmentation Problem

During autoregressive decoding, every token's key and value projections must be retained for the full lifetime of the sequence. A naive implementation pre-allocates a contiguous slab of GPU memory large enough for the maximum sequence length the model supports. Three things go wrong.

Internal fragmentation. If the maximum context is 4096 tokens but the average request completes at 512 tokens, roughly 87% of each reserved block is never touched.

External fragmentation. As requests finish and their slabs are freed, the free memory exists as scattered holes that cannot be combined to satisfy a new large request.

No prefix sharing. Two requests that start with the same system prompt independently store identical key-value tensors. There is no mechanism to deduplicate them.

The result is that the actual throughput-limiting resource is not compute: it is the allocator's inability to pack live KV entries densely.

Virtual Memory as the Blueprint

The OS virtual memory system solved the same class of problem in 1962. Physical RAM is divided into fixed-size pages (typically 4 KB). Processes see a contiguous virtual address space. The kernel maintains a page table that maps virtual page numbers to physical page frames. Allocation is granular; the physical layout is invisible to the process; copy-on-write lets two processes share a physical page until one of them writes to it.

PagedAttention maps this design onto the KV cache with minimal translation:

The block size (number of tokens per KV block) is a compile-time constant. Typical values are 8, 16, or 32. Smaller blocks improve packing density; larger blocks improve GPU memory access coalescing. The tradeoff is hardware-specific and is usually tuned empirically.

How the Kernel Executes Paged Attention

During the prefill phase, each new sequence is assigned logical block indices sequentially. The block manager allocates physical KV blocks on demand from a free-list and writes entries into the block table.

During decoding, at each step the attention kernel must compute:

score_i = (q · k_i) / sqrt(d_k)

for every past token i. The challenge is that k_i is no longer at a predictable offset from q. It lives in a physical KV block whose address is given by the block table. The CUDA kernel handles this with an indirection step that is worth understanding in detail.

Thread group layout. A warp of 32 threads is split into thread groups of size THREAD_GROUP_SIZE (often 2 or 4). Each group is responsible for one key token. The group collectively loads the 128-dimensional (or similar) key vector from its KV block address.

Block-level loop. Each warp iterates over KV blocks. For each block it: 1. Reads the block's physical address from the sequence's block table. 2. Loads BLOCK_SIZE key vectors. 3. Computes dot products with the query vector. 4. Applies masking for padding tokens within the block.

Softmax and output reduction. After all blocks are processed, threads reduce across the max logit for numerical stability, then accumulate the weighted sum of value vectors. The reduction happens in shared memory across the warp.

The indirection through the block table adds roughly one extra global memory read per KV block visited. On a modern A100 with 2 TB/s HBM bandwidth and a block size of 16, the overhead is typically under 1% of total decoding latency. The memory efficiency gains are orders of magnitude larger in value.

A simplified pseudo-trace:

# Pseudocode - not actual vLLM kernel code
for block_idx in range(num_blocks):
    phys_addr = block_table[seq_id, block_idx]      # indirection
    keys = load_kv_block(phys_addr, "key")          # coalesced HBM read
    scores = dot(query, keys) / sqrt(d_k)           # FMA in registers
    update_running_max_and_sum(scores)

output = reduce_weighted_values(block_table, running_softmax)

Prefix Caching and Copy-on-Write

Because physical KV blocks are individually addressable, two sequences that share a common prefix (same system prompt, same few-shot examples) can point their first N logical blocks at the same physical blocks. The block manager simply increments a reference count. No data is duplicated.

When one of those sequences needs to write a new KV entry into a shared block (because it has diverged), the runtime performs copy-on-write: it allocates a fresh physical block, copies the existing content, decrements the old block's reference count, and updates the block table. This is exactly the OS semantics. Prefix sharing can cut memory consumption by 30-55% for workloads with long shared prefixes, such as document QA with a fixed system prompt.

When It Falls Down

Short sequences in small batches. When each sequence is only a few hundred tokens and the batch size is 1 or 2, paging adds bookkeeping overhead with no real fragmentation to cure. Contiguous allocation in that regime is both simpler and faster.

Block-size misalignment with sequence length. If sequence_length mod block_size != 0, the last block is partially filled. With block size 16 and a 17-token sequence, memory utilisation for that sequence is ~53%. Smaller block sizes alleviate this but hurt coalescing.

CPU-side block-table management. The block table lives in CPU memory and is transferred to GPU before each forward pass. At very high batch sizes (hundreds of sequences) this transfer can become a measurable latency contributor. Proposals to maintain the block table in GPU memory exist but add synchronisation complexity.

Continuous batching dependency. PagedAttention realises most of its throughput benefit when paired with continuous batching (also called iteration-level scheduling), where new requests are inserted mid-batch as slots become available. Without it, the memory savings exist but the throughput multiplier is far smaller, because GPUs sit idle waiting for the slowest sequence in a batch.

Fragmentation floor. Paged allocation is not zero-waste. The last block of each sequence is on average half-empty. With block size 16 and a large batch, the expected waste is roughly block_size / 2 tokens per sequence. vLLM's own measurements show under 4% waste in practice, but this is not zero and grows slightly with larger block sizes.

Kernel complexity. The indirection-aware attention kernel is significantly harder to maintain and extend than a standard FlashAttention kernel. Integrating new attention variants (sliding window, ALiBi, grouped-query) requires re-deriving the block-table traversal logic for each.

Further Reading

• Efficient Memory Management for Large Language Model Serving with PagedAttention (Kwon et al., SOSP 2023)
• vLLM blog: Easy, Fast, and Cheap LLM Serving with PagedAttention
• vLLM design doc: PagedAttention kernel internals