PagedAttention

PagedAttention is the memory management idea that made high throughput open source LLM serving practical. It came out of UC Berkeley's vLLM project in June 2023, and the paper behind it, "Efficient Memory Management for Large Language Model Serving with PagedAttention" by Kwon and colleagues, won the best paper award at SOSP 2023. The idea is borrowed directly from operating systems: treat the attention KV cache like virtual memory, split it into fixed size pages, and let each sequence's keys and values live in small blocks scattered wherever free space exists.

The fragmentation problem#

Before PagedAttention, serving engines stored each request's KV cache in one contiguous slab of GPU memory. Because the engine cannot know how long a response will run, it reserved the slab for the maximum possible context length up front. That design fails in two ways. Internal fragmentation: a request that reserves room for 32,768 tokens but generates a 400 token answer strands everything it did not use. External fragmentation: slabs of different sizes come and go, leaving gaps between them that are individually too small to hold a new request even when they add up to gigabytes.

The numbers were brutal. Profiling systems like FasterTransformer and Orca, the vLLM authors found that only 20 to 40 percent of KV cache memory held actual token state; the remaining 60 to 80 percent was lost to reservations and gaps. Work the example for Llama 3 70B, which needs about 320 KB of cache per token. An engine configured for a 32,768 token maximum reserves roughly 10 GB per request. A median chat turn that ends at 2,000 tokens actually uses 640 MB, so about 94 percent of the reservation sits idle while new requests queue outside.

Paging, borrowed from the operating system#

Operating systems solved this exact problem decades ago. A process sees one contiguous virtual address space, but the physical RAM behind it is divided into fixed size pages that can live anywhere, with a page table doing the translation. PagedAttention applies the same trick to the KV cache. GPU memory is carved into uniform blocks, 16 tokens each by default in vLLM, and every sequence carries a small block table mapping its logical token positions to whichever physical blocks happened to be free. Blocks are allocated one at a time as decoding produces tokens, and released the moment the sequence finishes.

Waste collapses to the unfilled tail of each sequence's last block. The 2,000 token conversation from above now occupies 125 blocks of about 5 MB each for Llama 3 70B, and the worst possible slack is 15 empty token slots, under 1 percent of the sequence. Measured end to end, the paper puts total waste under 4 percent, against 60 to 80 percent for contiguous allocation. The widget below lets you watch blocks get allocated, shared, and freed as sequences arrive and complete.

Why batch size and throughput jump#

The KV cache, not compute, is what caps how many requests a GPU serves at once: whatever memory is left after the model weights is the cache budget, and concurrency is that budget divided by the per-request cache cost. The decisive change is which cost you divide by. A contiguous engine divides by the reservation; a paged engine divides by actual usage. With a 40 GB cache budget and the Llama 3 70B numbers above, contiguous allocation fits 4 concurrent requests at 10 GB each, while paged allocation fits roughly 60 at their real 640 MB footprints.

That fifteen-fold jump in feasible batch size converts almost directly into throughput, because the decode phase is memory bandwidth bound: each step streams all the model weights from HBM whether 4 sequences ride along or 60, as covered in prefill vs decode. The vLLM paper measured 2 to 4x higher throughput than FasterTransformer and Orca at the same latency, and up to 24x over naive HuggingFace Transformers serving. PagedAttention supplies the free memory; continuous batching is the scheduler that spends it by slotting new requests into the batch every step.

Sharing blocks across requests#

The block table indirection has a second payoff: two sequences can map the same physical block, with copy-on-write when one of them needs to diverge. Parallel sampling that draws 4 candidate answers from one prompt stores the prompt's cache once instead of 4 times, and beam search shares even mid-generation prefixes; the paper measured up to 55 percent memory savings on these workloads.

The same mechanism powers prefix caching. Suppose 100 concurrent conversations share a 5,000 token system prompt. At 320 KB per token, materializing that prefix separately per request would burn 160 GB; mapping every request's first 313 blocks to one shared copy costs 1.6 GB. This is the self-hosted analogue of what prompt caching sells at the API level, and it also skips recomputing the shared prefill.

The cost, and where it landed#

Nothing is free: attention kernels must gather keys and values through the block table instead of marching down contiguous memory, which requires custom CUDA kernels and adds some per-lookup overhead. Block size is the tuning knob, since tiny blocks mean bigger tables and less coalesced reads while huge blocks reinvent internal fragmentation; 16 tokens is the settled default. The verdict came quickly anyway: paged KV management shipped in vLLM first and is now baseline in TensorRT-LLM, Hugging Face TGI, SGLang, and LMDeploy. It also stacks cleanly with FP8 KV quantization, which halves bytes per block, and the two together roughly double again what fits.

Practical takeaways#

Size deployments by used tokens, not reserved ones: expected context length x bytes per token x target concurrency against your post-weights memory budget. Any mainstream engine gives you PagedAttention by default, so the real action is in what it enables: turn on prefix caching when requests share long system prompts, add KV quantization when long contexts still do not fit, and watch preemption counts in your serving metrics, because preemptions mean the block pool ran dry and your batch size ceiling has arrived.