KV cache management

Continuous batching established that KV cache memory sets your batch ceiling, and that fixing it is the largest single multiple in this book. This chapter is about the two distinct mechanisms inside that fix, because they help different workloads — and about a number that is very easy to quote wrongly.

Two different numbers, two different baselines

The PagedAttention paper's own abstract states the improvement precisely:

vLLM improves the throughput of popular LLMs by 2-4× with the same level of latency compared to the state-of-the-art systems, such as FasterTransformer and Orca.

That is not the 14–24× figure quoted in the batching chapter. Both are real; they measure against different things:

If you are on a modern serving stack, your remaining headroom is 2–4×, not 24×. Quoting the larger number to a team already running a real serving system will produce a migration that disappoints by roughly an order of magnitude, and it is the most common way this research gets misused in a business case.

Get the baseline right before you promise anything. The honest question is not "what did vLLM achieve" but "what am I running today."

Mechanism one: paging kills waste

The paper names two failure modes in the same sentence: memory "significantly wasted by fragmentation and redundant duplication."

Paging addresses the first. Partition each sequence's KV cache into fixed-size blocks that need not be contiguous, and the two classical fragmentation problems dissolve:

• Internal fragmentation shrinks to at most one partly-filled block per sequence, instead of a reservation sized for the maximum possible output length.
• External fragmentation disappears entirely, because blocks are interchangeable — the same reason operating systems adopted paging decades ago.

The paper's claim for the result is "near-zero waste in KV cache memory." That phrase is doing real work: the 60–80% waste that classical allocators exhibit is not reduced, it is largely eliminated.

This mechanism helps every workload, because every workload has sequences of unpredictable length.

Mechanism two: sharing kills duplication

The second half of the paper's contribution is different in kind: "flexible sharing of KV cache within and across requests."

When multiple sequences share a prefix, they can share the physical blocks holding that prefix's keys and values rather than each holding a copy. The obvious case is parallel sampling — generating several candidate completions from one prompt — where the entire prompt's KV cache is computed and stored once instead of n times. Beam search is the stronger case, because beams share not just the prompt but long stretches of the generated sequence, and the shared region grows as decoding proceeds.

Here is the part that matters for your architecture decision: this mechanism does nothing for a workload that has no shared prefixes. A chatbot serving unrelated users gets the paging win and none of the sharing win. An agent framework that fans out five candidate tool calls from identical context gets both.

The paper says as much about where its gains concentrate:

The improvement is more pronounced with longer sequences, larger models, and more complex decoding algorithms.

Read that as a targeting rule. Long contexts, big models, and beam search or parallel sampling are precisely the conditions under which KV cache dominates memory — and precisely where you should expect the upper end of the range. Short prompts, small model, single greedy completion: expect the lower end.

Why this is a memory chapter, not a speed chapter

Nothing here makes a single token generate faster. Every gain is indirect and runs through one variable: how many sequences fit in memory at once.

More sequences per batch means the model weights — streamed from memory once per decode step regardless of batch size, as memory bandwidth is the product explains — are amortised across more output tokens. The accelerator bills by the hour either way. Cost per token falls only because the denominator rose.

Which is why "we upgraded to a bigger GPU and throughput barely moved" is such a common report. If KV cache management is your binding constraint, more FLOPS buys nothing. More memory buys batch size, and better memory management buys batch size for free.

The diagnostic

1. What are you actually running today? A transformers loop, or vLLM / SGLang / TensorRT-LLM / a managed endpoint built on one? This single answer decides whether your headroom is ~24× or ~2–4×.
2. Do your requests share prefixes? Parallel sampling, beam search, or many users hitting one large system prompt say yes — the sharing mechanism is live for you. Unrelated single-completion requests say no.
3. How long are your sequences, and how big is the model? The paper is explicit that gains scale with both. A 7B model at 512-token context will not show what a 70B at long context shows.
4. Is your batch size memory-bound or scheduler-bound? If observed concurrency sits in single digits while requests queue, memory is the constraint and this chapter is your chapter.

What this chapter is not saying

It is not saying paging is optional if you have plenty of memory. Fragmentation waste is proportional, not absolute — a bigger GPU wastes 60–80% of a bigger number.

And it is not a claim that 2–4× is the ceiling for a modern stack. That figure is from a 2023 SOSP paper measured against the systems of that moment; serving stacks have moved since, in both directions. It is the right number for this specific comparison, which is exactly why the baseline matters more than the multiple.