PagedAttention

PagedAttention is a way of managing the KV cache, the memory where a model server keeps the keys and values of every token a request has seen so far. It splits that memory into small fixed-size blocks and gives each request blocks only as its tokens arrive, the way an operating system pages memory. A request no longer reserves room for the longest answer it might give.

It came from UC Berkeley's vLLM project, announced in June 2023, and the paper behind it, by Kwon and colleagues, appeared at SOSP 2023. Every mainstream open serving engine now manages its KV cache in pages, so a team serving its own model already has it, and the work is in sizing around it.

The fragmentation problem#

Before paging, engines stored each request's KV cache in one contiguous slab of GPU memory. The engine cannot know how long an answer will run, so it reserved the slab for the maximum context up front. That fails in two ways. A request that reserves 32,768 tokens and writes a 400-token answer strands everything it did not use. And slabs of different sizes come and go, leaving gaps between them that are each too small for a new request, even when together they add up to gigabytes.

The vLLM paper measured only 20.4 to 38.2 percent of KV-cache memory in existing systems holding actual token state, and the launch post put the waste at 60 to 80 percent. Work an example for Llama 3 70B, which with keys and values stored at 16 bits needs about 320 KB of cache per token. An engine configured for a 32,768-token maximum reserves about 10 GB per request. A typical chat turn that ends at 2,000 tokens uses about 640 MB, so about 94 percent of the reservation sits idle while new requests wait outside.

Paging, borrowed from the operating system#

An operating system gives each process one contiguous view of memory, while the physical memory behind it is cut into fixed-size pages that can sit anywhere, with a page table translating between the two. PagedAttention does the same for the KV cache. GPU memory is cut into uniform blocks, 16 tokens each by default in vLLM, and each sequence keeps a small block table that maps its token positions to whichever physical blocks were free. Blocks are allocated one at a time as decoding produces tokens and released when the sequence finishes.

Waste shrinks to the unfilled end of each sequence's last block. The 2,000-token conversation above occupies 125 blocks of about 5 MB each for Llama 3 70B, and the most slack any sequence can carry is 15 empty token slots, under 1 percent of this one. The vLLM launch post puts total waste under 4 percent. The widget below shows blocks being allocated, shared and freed as sequences arrive and finish.

Why batch size and throughput jump#

The KV cache, not compute, sets how many requests a GPU can serve at once. The memory left after the weights is the cache budget, and concurrency is that budget divided by what each request costs. A contiguous engine divides by the reservation, and a paged engine divides by what is actually used. With a 40 GB cache budget and the Llama 3 70B figures above, contiguous allocation fits 4 requests at 10 GB each, while paged allocation fits about 60 at their real 640 MB.

A larger batch turns almost directly into throughput, because each decode step streams all the model's weights from memory whether 4 sequences ride along or 60, as covered in prefill vs decode. The paper measured 2 to 4 times the throughput of FasterTransformer and Orca at the same latency, and the launch post reported up to 24 times the throughput of serving with plain Hugging Face Transformers. Paging supplies the free memory, and continuous batching is the scheduler that fills it by admitting a new request into the batch at every step.

Sharing blocks across requests#

Because every sequence reaches its memory through a block table, two sequences can point at the same physical block and copy it only when one of them needs to change it. Beam search shares prefixes even mid-generation, and the paper measured 37.6 to 55.2 percent memory savings on beam search and 6.1 to 9.8 percent on parallel sampling.

The same mechanism gives prefix caching. Suppose 100 concurrent conversations share a 5,000-token system prompt. At 320 KB per token, a separate copy of that prefix per request would take 160 GB, while pointing every request's first 313 blocks at one shared copy takes 1.6 GB, and the shared prefill is not recomputed. As of October 2026, vLLM turns prefix caching on by default. It is the self-hosted counterpart of what prompt caching sells through an API, and it rewards the same habit: put the shared part of every prompt first and keep it byte-identical.

What paging costs#

Attention kernels have to gather keys and values through the block table instead of reading one contiguous run of memory, which takes custom kernels and adds some overhead per lookup. Block size is the tuning setting: small blocks mean larger tables and less efficient reads, and large blocks bring back waste at the end of each sequence. vLLM defaults to 16 tokens and TensorRT-LLM to 32. Paging also combines with 8-bit KV quantization, which halves the bytes per block and roughly doubles again what fits.

Size by used tokens, then watch preemption#

Bigcircle recommends sizing a self-hosted deployment from the tokens requests actually use: expected context length times bytes per token times target concurrency, checked against the memory left after the weights. A plan built on maximum context lengths buys hardware for reservations nobody makes. Once the server is live, watch preemption in its metrics. A preemption means the block pool ran out and the scheduler evicted a request to recompute it later, which users see as a latency spike. Persistent preemption means you have reached the batch size the memory allows, and the next step is KV quantization, a smaller context limit or more memory, not a scheduler setting.