The vLLM paper on PagedAttention (SOSP 2023) reports 2 to 4 times the throughput of the then state-of-the-art serving systems at the same latency, with larger gains for longer sequences and more complex decoding, from managing the key-value cache in fixed-size blocks like operating-system pages rather than as one contiguous per-request reservation. Its profiling of existing systems found only roughly 20 to 38% of key-value cache memory holding actual token state. What was the real constraint, what did the change buy, and where would copying the lesson be a mistake?

The situation

A transformer serving a request keeps a key-value cache whose size grows with the sequence. Earlier serving systems reserved a contiguous region per request, sized for the maximum tokens that request might generate.

That produces two kinds of waste, and the paper's profiling quantifies the result: only about a fifth to two-fifths of key-value cache memory held real token state.

• Internal waste: a request that might generate 2,048 tokens but generates 200 holds the reservation for 2,048 anyway, for its whole life.
• External waste: freed regions of varying sizes leave gaps too small for the next request, the classic fragmentation problem.

Why that was the binding constraint

On an accelerator, concurrency is limited by memory, not by compute. Weights occupy a fixed amount; what remains is key-value cache, and the cache per sequence determines how many sequences fit. Batch size follows directly from that, and decode throughput follows from batch size.

So wasting three-quarters of the cache is not a memory-efficiency footnote - it divides the achievable batch size, and therefore the throughput, by about the same factor. That is why a memory-layout change produces a 2 to 4 times throughput result rather than a few percent.

What the change bought

Fixed-size blocks plus a block table per sequence, exactly like virtual memory pages:

• No internal waste beyond one partial block, so a request occupies what it has actually generated.
• No external fragmentation, because every free block is interchangeable.
• Sharing between sequences. Blocks holding an identical prefix can be referenced by several sequences with copy-on-write, which is what makes a shared system prompt, parallel sampling and beam search cheap. The paper notes larger gains for more complex decoding for exactly this reason.

What it cost

An indirection on every attention step, which needs a custom kernel to stay fast; a block manager with allocation, eviction and preemption policies; and the need to swap or recompute blocks when memory runs out under load, which is a scheduling problem the contiguous design did not have. The complexity is real and it is concentrated in one component, which is the trade that made it worth doing.

Where copying the lesson would be a mistake

• If you consume a hosted model API, none of this is yours to build. The transferable lesson is the constraint, not the mechanism: your throughput and your cost are governed by how well the provider can batch your traffic and reuse your prefix, so the levers you have are prompt structure for cache reuse and concurrency shape, not memory layout.
• If you self-host at low concurrency - a handful of simultaneous requests on a dedicated accelerator - memory is not your constraint and the paging machinery buys nothing. Your constraint is per-token latency, and the relevant techniques are the decode-side ones.
• Do not generalise "2 to 4 times" into a number you expect. It was measured against specific baselines, with longer sequences and complex decoding giving the larger figures. The reproducible part is the reasoning: find what limits batch size, and fix that.

The general principle

Find the resource that bounds concurrency, then ask what fraction of it is doing useful work. Here the answer was a fifth to two-fifths, and the fix was a decades-old operating-systems idea applied to a new workload. That question - what proportion of the binding resource is actually in use - is the one worth carrying to any serving system.

Common weak answers

• "Buy more accelerators." Quadruples the bill to work around memory that was three-quarters idle.
• "Use a smaller model." Changes the product to solve a layout problem.
• "Set max_tokens lower so reservations are smaller." A real mitigation under the contiguous design and an admission of it: it makes the user's output limit a function of your memory allocator.
• "Adopt the serving stack and expect 2 to 4 times." The figure was measured against specific baselines with particular sequence lengths; prefer measuring your own batch-size ceiling before and after to the published multiple.