PagedAttention

PagedAttention does not make the KV cache smaller. Not by one byte. It stores exactly the same keys and values, computes exactly the same numbers, and reads exactly the same bytes on every decode step. What it changes is who owns the memory a request has not filled yet — and on a real workload that is most of the pool.

The KV cache is the per-layer keys and values a transformer keeps so it never recomputes the past; the KV cache lesson does the arithmetic that fixes its size. A serving engine has to put that cache somewhere. Until 2023 every engine put each request's cache in one contiguous slab, because that is what attention kernels needed, and it had to size that slab when the request arrived — before knowing how long the answer would be. So it sized it for the client's declared max_tokens.

A request that declares max_tokens: 2048 and writes a 280-token answer holds 1,768 token slots that nothing will ever be written into, for its entire lifetime. Kwon et al. measured this on real traces and found that only 20.4% to 38.2% of KV cache memory in existing systems was holding actual token states. The rest was reservation, rounding and holes.

PagedAttention's answer is the one operating systems reached in 1962: give up contiguity. Cut the pool into fixed-size blocks of 16 tokens, hand a request blocks as it fills them, and keep a per-sequence block table — a small array mapping the sequence's logical block n to whatever physical block currently holds it. The attention kernel is rewritten to walk that table instead of striding through a slab.

Below is that allocator, running against a saturated queue. Switch between the three policies and watch the memory map. Then move declared max_tokens — the one number the engine does not control.

Start at the defaults. The contiguous allocator holds 44 sequences and gets 43.7 tokens per step, with 48% of the memory it is holding actually holding tokens. Switch to paged: 95 sequences, 95.4 tokens per step, 99.8% effective. Nothing about the model, the GPU or the requests changed. The same 55.65 GiB now holds twice the work because the allocator stopped holding space for tokens that had not been asked for yet.

Now drag declared max_tokens to 16,384 — a client-side default nobody thinks about, on requests that still write 256-token answers. The contiguous allocator collapses to 12 sequences and 12.0 tokens per step, at 13.5% effective. Paged does not move: 95.4. The gap went from 2.2× to 7.9× and the only thing that changed was a number in the request body. That is the shape of this mechanism. Its value is not a property of PagedAttention; it is a property of how badly your clients over-declare.

Three wastes wearing one name

"Fragmentation" is doing too much work in most explanations of this. The vLLM paper separates three things, and they respond to different fixes.

• Reserved. Slots the request will eventually use, held from the moment it is admitted. Not waste in the end — but held for the whole lifetime, so nobody else can use them meanwhile. Set declared max_tokens to 256 and this nearly vanishes: the contiguous allocator recovers to 60.0 tokens per step and 66% effective.
• Internal fragmentation. The slots inside a request's chunk that it will never reach, because the chunk was sized for a maximum it did not approach. This is the one that scales with over-declaration, and it is only known to be waste after the request has finished.
• External fragmentation. Free slots that exist but are in the wrong places. Turn off round chunks up to a power of two and set output-length spread to 100 with the oracle allocator — an allocator that magically knows each request's true output length in advance. It still cannot reach the pool it can see. The log prints the moment it first happened: request 96 needed 2,712 contiguous slots, 3,881 slots were free, and they were split across three runs whose largest was 1,689. The request at the head of the queue was blocked for that reason on 2,938 of the run's 3,000 steps.

Paging kills the second and third outright. Internal fragmentation is bounded at one partial block per sequence — at block_size 16 that is at most 15 token slots per sequence, or 2.11 MiB of key-value cache, so at most 200 MiB across 95 resident sequences. The simulation measures 101 MiB held-and-empty on average, because a partial block is on average about half full. External fragmentation cannot exist, because every block is the same size and therefore interchangeable; there is no such thing as a hole that is the wrong shape. Reserved memory it removes by simply not reserving: a request holds blocks for the tokens it has written and not one more.

This is the same trade Postgres made with its free space map — fixed 8 KiB pages plus a map of who has room, instead of variable-length contiguous extents. Fixed-size units plus an indirection is the standard answer to a variable-size allocation problem, and it has been since virtual memory. The novelty in PagedAttention is not the idea. It is that attention kernels had always assumed contiguity, so somebody had to write the kernel that does not.

Notice what is not on the list: the cache itself. Bytes per token are set by layers, KV head count and dtype — see grouped-query attention for the head-count term and quantization for the dtype term. Paging does not touch any of them. If your problem is that one 32k-token request costs 4.5 GiB, paging will not help you; it helps when you are holding memory for requests that are not using it.

What the block table costs

Three costs, in increasing order of how much they actually matter.

The table itself is negligible, and this surprises people. In vLLM it is one dense int32 tensor of shape [max_num_reqs, max_num_blocks_per_req]. With max_num_seqs 128, a 40,960-token context and block_size 16 that is 128 × 2,560 × 4 bytes = 1.25 MiB, against a 55.65 GiB pool: 0.002%. Watch the block table readout as you drag block_size down to 1 — it grows to 20 MiB, which is still nothing. The block table is not why block_size is 16.

The kernel is the real cost. A contiguous attention kernel reads keys and values with a single strided load. A paged one must read the block table, resolve each logical block to a physical one, and gather. The paper measures it directly: 20–26% higher attention-kernel latency than FasterTransformer's contiguous implementation. That penalty is paid on every decode step of every sequence, forever, and it is not in the simulation above. It is worth paying when the batch doubles. It is not worth paying when the batch does not.

The scheduler now has to be able to fail. A contiguous engine makes one decision per request, at admission, and once a request is in it can never run out of memory. A paged engine allocates a block at a time, so a request can be running happily and then find, at token 900, that there is no block left. vLLM's answer is to preempt: under the default first-come-first-served policy it pops the most recently admitted request off the running list, frees all of its blocks, and puts it back at the front of the queue to recompute from the prompt. Every token it had generated is discarded.

You can see this in the simulation. In paged mode the decision log prints each preemption, naming the request that needed the block, the victim, and how many tokens went in the bin. It is the same optimistic-admission bargain as pod preemption in Kubernetes: you admit more than you can guarantee, and you accept eviction as the price. The difference in an inference server is that the evicted work is not merely delayed — it is repeated.

Where paging stops helping

Set the allocator to oracle, turn round chunks up to a power of two off, and drag output-length spread to 0. Now every request generates exactly 256 tokens, the allocator knows it in advance, and it reserves precisely that much with no rounding.

The contiguous allocator gets 96.7 tokens per step at 96.9% effective. Paged gets 96.3. Paging is behind — and that is before charging it the 20–26% kernel penalty. The log applies the penalty as a 0.77× factor: 74.2 effective tokens per step against the contiguous allocator's 96.7, which is roughly a quarter behind on wall-clock throughput. Every one of PagedAttention's gains came from uncertainty about output length. Remove the uncertainty and there is nothing left to recover, only overhead to pay.

This is not a hypothetical corner. It is what a fixed-shape batch inference job looks like: 50,000 documents, one classification token each, output length known exactly. It is also roughly the regime the paper itself reports for OPT-175B on the Alpaca trace, where vLLM's advantage over Orca (Oracle) shrinks because there is enough KV memory and the sequences are short — the system becomes compute-bound, and memory management stops being the question.

The other boundary is preemption. Because paging admits on the prompt's blocks alone, the pool can be full and every resident request still needs a new block every block_size tokens. At the defaults the simulation preempts 45 times over its 2,000-step measurement window and throws away 120 generated tokens, against the 190,800 it delivers in the same window. That is a rounding error. Push output-length spread to 0 and it climbs to 83 preemptions and 4,917 discarded tokens, because identical output lengths make every request start and finish in lockstep, so demand for new blocks arrives in synchronised waves instead of being smeared out. Uniform workloads are harder on this allocator than varied ones, which is the opposite of what most people expect.

Preemption is also where paging and scheduling get confused for each other. Continuous batching decides when a request joins the batch; paging decides how much memory it holds while it is there. You can have either without the other — Orca had iteration-level scheduling and contiguous reservation, which is exactly the "contiguous, reserve max_tokens" row above running at 43.7 tokens per step. The two mechanisms shipped a year apart and are routinely credited with each other's numbers.

So what does block_size trade? Not memory, mostly. Drag it from 16 to 256 and throughput falls from 95.4 to 93.0 — a 2.5% loss to bigger partial blocks. The paper's own ablation found block sizes from 16 to 128 all performed well on the ShareGPT trace, and that only the Alpaca trace, whose sequences are shorter than the larger blocks, degraded badly. Two things it does trade:

• Kernel parallelism. A very small block hands the kernel too few KV positions per gather to keep the GPU's threads busy. vLLM never left that to the user: the CUDA kernel compiled exactly three block sizes. In csrc/attention/attention_kernels.cu at v0.2.0 the launcher switches on case 8, case 16 and case 32; 1, 2, 4, 64, 128 and 256 sit in the file as commented-out cases and fall through to TORCH_CHECK(false, "Unsupported block size: ", block_size). That is the RuntimeError: Unsupported block size: 64 people hit when they ask for a bigger block. The default is 16 rather than 1 even though 1 has zero internal fragmentation.
• Sharing granularity. Turn on share the system prompt's blocks. Blocks are shared whole or not at all, so a 1,000-token system prompt shares 992 tokens at block_size 16 and only 768 at 256 — the remainder falls in a partial block that each request must own privately. Throughput goes 122.9 versus 112.6. Bigger blocks quietly cost you sharing.

Sharing is the part that pays twice

A block table is a level of indirection, and the moment you have one, two sequences can point their logical block 0 at the same physical block. Add a reference count and copy-on-write for the block that diverges, and you get sharing for free — this is the second half of the paper and the reason PagedAttention outlived the specific throughput numbers.

In the simulation, turning sharing on takes 95.4 tokens per step to 122.9, a 29% gain, purely because 1,000 tokens of identical system prompt are stored once instead of 95 times. The paper measures the same effect on real traces: 6.1%–9.8% memory saved on parallel sampling and 37.6%–55.2% on beam search with the Alpaca trace, rising to 16.2%–30.5% and 44.3%–66.3% on ShareGPT. For a workload where prompts share a long prefix it reports 1.67× the throughput of Orca (Oracle) with an 80-token shared prefix and 3.58× with a 341-token one.

Note what the simulation does not model: it only saves the memory. The larger win in practice is that the shared prefix does not have to be recomputed at all, which is prefix caching — a separate mechanism that paging makes possible, enabled by default in vLLM since the V1 engine. That one attacks time to first token rather than memory, and it is usually the cheapest win in a serving stack.

One thing to keep straight: FlashAttention and PagedAttention are not alternatives and are not competitors. FlashAttention removes the materialised N × N attention-score matrix by tiling the softmax; PagedAttention removes allocator waste from the KV cache. Both compute numerically exact attention. Modern kernels do both at once — which is worth saying explicitly, because "is paged attention an exact attention" is a question people ask and nobody answers. Yes. The block-wise softmax is rescaled and combined exactly as FlashAttention's is; splitting the sum over blocks does not change it.

Checking it on a real system

Read the boot line first. vLLM prints the pool it carved out and what that means for concurrency:

GPU KV cache size: 405,239 tokens, Maximum concurrency
for 40,960 tokens per request: 9.89x

That "maximum concurrency" is computed against max_model_len, not against your actual prompts. If your p95 request is 4k tokens rather than 41k, your real ceiling is ten times what the line says. Divide the token count by your real p95 context to get the number that matters.

Then, under load, watch two fields in the steady-state log line — GPU KV cache usage and Preemptions. The second only appears once preemption has actually happened, so its mere presence is the alert. In Prometheus they are vllm:kv_cache_usage_perc and the counter registered as vllm:num_preemptions, exported with a _total suffix. A steady non-zero preemption rate means you are paying for prompts twice.

If you see it, the fix is almost never --block-size. In order:

1. Cap max_tokens server-side. On a paged engine this does not reserve memory, so it is not the lever it was on Orca — but it stops one runaway generation holding blocks for an hour. Move the slider above to see what the same cap would have cost you on a contiguous allocator.
2. Lower max_num_seqs. Preemption means the scheduler admitted more sequences than the pool can grow. Fewer residents, each with room to grow, beats more residents thrashing. This is the one knob that directly trades the two.
3. Check the prefix cache hit rate before adding hardware. If your requests share a system prompt and the hit rate is low, something is defeating the block hash — a per-request timestamp in the prompt, a user id at the front instead of the back, or a prefix shorter than one block. Blocks hash whole, so a 12-token shared prefix at block_size 16 shares nothing at all.
4. Then look at the cache itself: FP8 KV, fewer KV heads, shorter contexts, more cards. Those change bytes per token, which is the term paging never touches.

And if you are comparing engines, compare on your output-length distribution. A benchmark with fixed max_tokens equal to the real output length is the boundary case above: it measures the kernel penalty and none of the benefit, and it will tell you paging is a regression.

Next: the scheduler that decides who is in the batch at all, continuous batching; the mechanism that makes a shared prefix free rather than merely small, prefix caching; and the other way to spend a decode step's idle arithmetic, speculative decoding. If your prefills are stalling decodes rather than starving them of memory, that is chunked prefill.