Why OS Virtual Memory Paging Saved LLM Inference: The vLLM Breakthrough

In high-throughput Large Language Model (LLM) serving, the primary hardware bottleneck is rarely raw compute (FLOPs)—it is GPU High-Bandwidth Memory (VRAM).

Specifically, the auto-regressive generation of tokens requires saving the Key and Value attention matrices for every preceding token: the KV Cache.

Until the introduction of PagedAttention (vLLM) in 2023, standard serving systems (like HuggingFace and v1 inference engines) wasted between 60% and 80% of all GPU memory.

The solution didn't come from new AI algorithms; it came from a 50-year-old operating systems concept: Virtual Memory Paging.

1. The Contiguous Allocation Problem

In standard self-attention, the key and value vectors of a sequence must be stored in contiguous physical memory so that CUDA matrix kernels can execute efficiently.

Because the system cannot predict how many tokens an LLM will generate before emitting the <EOS> stop token, traditional engines pre-allocated contiguous memory slots for the maximum request length (e.g., 2,048 or 4,096 tokens).

Two Forms of Memory Waste:

  1. Internal Fragmentation: If a request pre-allocates 2,048 tokens but stops after 150 tokens, the remaining 1,898 slots sit reserved and completely idle.
  2. External Fragmentation: Because requests start and finish dynamically, allocating contiguous variable-sized memory blocks creates fragmented holes in GPU VRAM, preventing new batches from scheduling.

2. The PagedAttention Architecture

PagedAttention resolves this by relaxing the requirement that KV vectors be stored in contiguous physical memory.

  • KV Blocks: The KV cache is divided into fixed-size physical blocks (e.g., 16 tokens per block).
  • Block Table: Identical to an Operating System's Page Table, the engine maintains a mapping between logical token positions and physical GPU memory blocks.
  • On-Demand Allocation: Physical blocks are allocated one by one only as new tokens are generated.

When computing attention for a newly generated token, the custom CUDA kernel looks up the physical block addresses in the block table, fetching key-value vectors on the fly from non-contiguous memory locations.

3. Copy-on-Write for Prompt Sharing

PagedAttention also implements Copy-on-Write (COW):

  • In parallel sampling (generating multiple answers for the same prompt) or beam search, all branches share the exact same physical prompt KV blocks.
  • Only when a specific branch generates a new token does it allocate its own private block.

Memory waste plummets from 80% to under 4%, enabling servers to double or quadruple active batch sizes.

Read the full deep-dive with interactive architectural schematics at Binary Dose.