Paged attention

KV cache as a page table

Paper: Efficient Memory Management for Large Language Model Serving with PagedAttention — Kwon et al., 2023

vLLM’s best-known contribution is taking an idea that operating systems have used to manage RAM since the 1960s (virtual memory with paging) and applying it to the KV cache. The result, PagedAttention, improves KV-cache packing and can substantially increase achievable concurrency. This section is about why a page table is a useful data structure for the KV cache, and how it changes what “running out of memory” means.

The problem with naive contiguous allocation

Before vLLM, the standard approach was: when a request arrives, allocate a contiguous slab of KV memory big enough for its maximum expected sequence length. So if your model supports 4k context, every request reserves 4k tokens worth of KV space immediately, even if it only ends up generating 200 tokens.

This is catastrophically wasteful:

• Internal fragmentationfragmentationWasted memory from allocations that don’t fit cleanly. Paging trades internal fragmentation (≤1 page per request) for none of the external kind.See in glossary →: almost every request leaves most of its reserved slab unused.
• External fragmentation: when a request finishes, its slab is freed, but the next request might need a slightly different size and can’t reuse the hole cleanly. Memory becomes Swiss cheese over time.
• Hard limits on concurrency: you can fit far fewer concurrent requests in HBM than your actual KV-cache contents would require, because you have to reserve worst-case for each.

The 2023 vLLM paper (“Efficient Memory Management for Large Language Model Serving with PagedAttention”) measured this. Real workloads were leaving 60–80% of allocated KV memory unused.

The page table trick

Here’s the move. Stop allocating contiguous slabs at all. Instead:

1. Split HBM’s KV-cache region into a pool of fixed-size pagespageA fixed-size slab of KV cache memory (e.g. 16 tokens). The unit vLLM allocates and frees.See in glossary → (often 16 tokens per block; the block size is configurable). For Llama-3-8B with GQA at fp16, a 16-token block across all 32 layers is about 2 MB.
2. Each request maintains a page tablepage tablePer-sequence mapping from logical position → physical page in the KV cache. Same idea as OS virtual memory, applied to attention.See in glossary →: a small list mapping the request’s logical position (token 0…N) to the physical block in the pool that holds those tokens’ KV.
3. When the request grows by another decode step, it writes into its last partially filled page or allocates a new page when that page is full.
4. When the request finishes, its pages return to the free pool.

Internal fragmentation now caps at less than one page per request: for this Llama-3-8B GQA example, at most about 2 MB regardless of the request’s total length. External fragmentation from variable-size allocation is eliminated because every allocation and free is the same size.

Modifying the attention kernel

The catch is that the GPU’s attention kernel now has to do an indirection: every key/value access goes through the page table. The vLLM team wrote a custom CUDA kernel called paged_attention that takes the per-request page table as input and walks it during the QKᵀ dot products and value combinations.

The indirection has an implementation cost, and its performance depends on the attention kernel and workload. The vLLM paper reports 2–4× system throughput improvements over the compared serving systems at similar latency, driven by improved KV-cache utilization and sharing; that is a workload-specific system result, not a universal per-kernel multiplier.

Try it

Below is a simplified paged allocator: 24 physical blocks of 4 tokens each (real vLLM uses ~16 tokens/page, but 4 fits on screen). Add requests, decode steps, finish them, and watch:

• The block grid on the left shows physical block occupancy. Empty (dashed) blocks are free.
• The page tables on the right show each request’s logical → physical mapping.
• Try toggling prefix caching on, then add multiple requests with + With shared prefix. The same physical blocks back several requests’ page tables. You’ll see a teal “shared” badge on those blocks. That’s the next section’s idea.

The free-block queue

Conceptually, the allocator maintains a pool of free physical blocks. Fixed-size blocks avoid a search for a suitably sized region, compaction, or a defragmentation pass. The exact free-list policy and implementation can vary by vLLM version.

The scheduler asks the allocator “do you have K free blocks?” before deciding to admit a request. If not, it can wait or preempt work. Depending on the engine and configuration, preemption may drop KV state for later recomputation or move it to another memory tier.

Preemption and swap

Two preemption modes:

1. Recompute: drop the KV cache for the preempted request entirely; when it comes back, re-run prefill. Cheap to free, expensive to resume. Good when KV is small relative to recompute cost.

2. Swap: copy the KV pages down to host RAM via PCIe; when the request comes back, copy them back up. Slower on each side but avoids the recompute. Good for long contexts where recomputing prefill is expensive.

Which mode is available or selected depends on the serving-engine version and policy.

What this enables

PagedAttention alone is “memory hygiene”: better packing and no variable-size allocation fragmentation. Its block structure also makes it efficient to reference-count and share physical blocks across requests. Prefix caching builds on that capability in the next section.