How PagedAttention Eliminates KV-Cache Fragmentation

PagedAttention, the core technology behind the vLLM serving engine, revolutionizes how Large Language Models (LLMs) manage GPU memory during inference. By borrowing classical virtual memory and paging concepts directly from computer operating systems, PagedAttention solves the critical bottleneck of Key-Value (KV) cache fragmentation. This article explains the mechanics of the KV-cache problem, how PagedAttention decouples logical and physical memory blocks to eliminate waste, and why this directly leads to massive increases in AI serving throughput.

The KV-Cache Bottleneck in LLM Serving

During the autoregressive generation phase of an LLM, the model generates text one token at a time. To avoid recalculating past data for every new token, the system stores the attention keys and values of previous tokens in GPU memory. This storage is known as the KV-cache.

Traditionally, deep learning frameworks require the KV-cache for a single request to be stored in contiguous (unbroken) blocks of physical GPU memory. Because the system cannot predict how long an LLM's output will be in advance, it must pre-allocate a contiguous chunk of memory based on the maximum possible sequence length. This creates three severe forms of memory waste:

  • Internal Fragmentation: Memory is over-allocated for the maximum length, leaving vast amounts of unused space if the generated response is short.
  • Reservation Waste: Memory reserved for future tokens in an active sequence sits idle and cannot be used by other requests until those tokens are actually generated.
  • External Fragmentation: As requests of varying sizes start and finish, the physical GPU memory becomes splintered into small, non-contiguous gaps that are too small to fit new, large contiguous allocations.

Borrowing from Operating Systems: Virtual Memory and Paging

Operating systems solved this exact contiguous memory problem decades ago using virtual memory and paging. An OS allows a program to see its memory as a single, contiguous space (virtual memory), while actually storing the data in small, fixed-size chunks (pages) scattered across the physical RAM. A page table maps the virtual addresses to the physical addresses.

PagedAttention applies this exact architecture to the KV-cache in GPU memory:

  • KV Blocks (Pages): PagedAttention divides a request's KV-cache into small, fixed-size blocks. Each block holds the attention keys and values for a fixed number of tokens (for example, 16 or 32 tokens).
  • Logical vs. Physical Blocks: To the LLM computation, the tokens appear to be in contiguous "logical blocks." However, in the actual GPU VRAM, these are stored as non-contiguous "physical blocks."
  • The Block Table (Page Table): vLLM maintains a Block Table that dynamically maps a request's logical blocks to the scattered physical blocks in the GPU memory.

How PagedAttention Eliminates Fragmentation

By removing the requirement for contiguous physical memory, PagedAttention allocates memory strictly on-demand.

When a new request arrives, vLLM does not pre-allocate memory for the maximum sequence length. Instead, it allocates just enough physical blocks to hold the initial prompt. As the model generates new tokens, they are written to the current physical block. Only when that block becomes completely full does the system allocate a new physical block from anywhere in the available GPU memory and update the Block Table.

This mechanism completely resolves the three types of memory waste:

  • Zero External Fragmentation: Because all physical blocks are the exact same size, any free block can be assigned to any request. There are no unusable gaps between memory allocations.
  • Zero Reservation Waste: Memory is never held hostage for future tokens. It is only claimed the exact moment a new token requires it.
  • Near-Zero Internal Fragmentation: The only wasted memory in the entire system occurs in the very last block of a sequence, which might only be partially filled when the model finishes generating text. Because blocks are tiny, this waste is typically less than 4% of the total memory.

Advanced Memory Sharing and Copy-on-Write

Just as operating systems allow different processes to share the same physical memory pages for common code libraries, PagedAttention enables different LLM requests to share physical KV blocks.

In advanced decoding scenarios like parallel sampling (generating multiple completions for the same prompt) or beam search, multiple outputs share the exact same initial prompt. Instead of duplicating the prompt's KV-cache in physical memory for every single candidate output, PagedAttention maps the logical blocks of all candidates to the exact same physical blocks.

The physical blocks keep a reference count of how many logical blocks point to them. When a specific candidate needs to modify a shared block by adding a unique generated token, PagedAttention triggers an OS-style Copy-on-Write (CoW) mechanism. It allocates a new physical block, copies the original data over, decrements the reference count on the shared block, and writes the new data to the newly created block.

The Impact on AI Serving

By eliminating KV-cache fragmentation and enabling block-level memory sharing, PagedAttention reclaims over 60% to 80% of the GPU memory that was previously wasted by traditional serving systems. This newly freed memory allows vLLM to batch significantly more concurrent requests together at the same time, multiplying overall serving throughput without requiring any changes to the underlying model architecture.