PagedAttention: the KV cache was the bottleneck all along

The number that made us read the code

A group at Berkeley led by Woosuk Kwon and Zhuohan Li released vLLM last week with a blog post claiming up to 24 times the throughput of Hugging Face Transformers and up to 3.5 times that of Text Generation Inference on the same hardware. The models were LLaMA-7B on an A10G and LLaMA-13B on a 40 GB A100, with request lengths drawn from ShareGPT conversations. Gains like that from a serving layer, with no change to the weights, usually mean the baseline was doing something wasteful. The post says what it was.

Every token a decoder generates needs the keys and values of every earlier token in the sequence. That is the KV cache, and for a single LLaMA-13B sequence it can reach 1.7 GB. Existing systems allocated it as one contiguous block sized for the maximum possible sequence, because nobody knows in advance how long a generation will run. The vLLM team measured the result and found that 60 to 80 percent of KV cache memory in those systems was wasted through fragmentation and over-reservation. Memory, not compute, was capping how many requests fit on a GPU at once, and batch size is throughput.

Virtual memory for attention

PagedAttention is the operating systems idea applied directly. Instead of one contiguous region per sequence, the cache is split into fixed-size blocks, each holding the keys and values for a fixed number of tokens, and the blocks for a sequence need not be adjacent in physical memory. A block table maps logical positions to physical blocks, exactly as a page table maps virtual to physical addresses. A sequence acquires blocks as it grows, and the only waste is the unfilled tail of its final block, which the post puts at under 4 percent.

The attention kernel had to be rewritten to gather keys and values from scattered blocks, which is the real engineering in the project, but the payoff is that memory is allocated on demand. A GPU that could hold a handful of worst-case sequences can now hold as many as actually fit, and the scheduler can batch far more requests per forward pass. That is where the throughput comes from.

The second thing paging gives you is sharing. In parallel sampling, where a user asks for several completions of one prompt, every completion shares the prompt's blocks and copies only when it diverges, in the manner of copy-on-write. Beam search shares even more, since beams share long prefixes and are constantly forked and discarded. The post reports memory savings of up to 55 percent and throughput gains of up to 2.2 times for these decoding modes, which is why the improvement over TGI grows from about 2.2 times with a single output to about 3.3 to 3.5 times with three.

The Vicuna deployment as evidence

The proof that this is a practical result rather than a benchmark curiosity is that LMSYS has been running it. Chatbot Arena and the Vicuna demo have served a daily average of 30,000 requests with peaks of 60,000, and the team reports that switching from an initial Hugging Face backend to vLLM cut the number of GPUs used by half while handling up to five times the traffic. The internal figure is up to 30 times the throughput of the original backend. That is the sort of cost line that decides whether a free demo stays up.

We think this is the clearest example this year of where the constraint on LLM products actually sits. The models have been good enough for a wide range of tasks since March. What has limited who could deploy them is the cost per served token, and the biggest single term in that cost was an allocation strategy borrowed from training, where sequence lengths are fixed and padding is normal, applied to serving, where they are not.

What is left

The design has obvious next questions. Block size trades kernel efficiency against tail waste, and the post does not report a sweep. Behaviour under memory pressure, when more sequences are running than blocks remain, is where we would expect the first production surprises, and the post does not say much about it. And the comparison is against Hugging Face and TGI, so it would be good to see numbers against FasterTransformer and Orca, which is the comparison the forthcoming paper is presumably built around.

For a small lab the immediate consequence is that serving a 13B model for internal tools moved from needing several GPUs to needing one, without touching quality. We would like to see the same idea pushed into the prompt side, with shared blocks for common system prompts across users, and we would like someone to measure how much of the remaining cost per token is the attention gather versus the matrix multiplies, because that tells us whether the next order of magnitude comes from kernels or from the model.