Running a large language model for many users at once is mostly a memory problem. Every request has a growing pile of notes, the KV cache, in which the model keeps the key and value vectors for every token it has already read or written, so it does not have to recompute them. The paper gives a sense of the scale: for a 13-billion-parameter model, the cache for a single token takes about 800 kilobytes, and a request of 2,048 tokens can take as much as 1.6 gigabytes.
A GPU only has tens of gigabytes. So how many requests you can run at once, the batch size, and therefore how much money each answer costs, depends on how cleverly you store those notes. The vLLM paper noticed that existing systems wasted most of that memory, and borrowed a 1960s idea from operating systems to fix it.
PagedAttention stores the KV cache in small fixed-size blocks that can be anywhere in memory, tracked by a block table, just like virtual memory pages. Waste drops to near zero, requests can share blocks, and the paper's system vLLM serves 2 to 4 times more requests at the same latency.
The problem: the KV cache grows, and nobody knows how far
When a model generates text, the KV cache of a request grows one token at a time, and no one knows ahead of time how long the answer will be. Existing systems stored each request's cache in one contiguous chunk of memory, as deep-learning frameworks expect tensors to be. To be safe, they reserved space for the maximum possible length.
The paper identifies three kinds of waste:
- Reserved space. Slots held for tokens that have not been generated yet.
- Internal fragmentation. Space reserved for a long output that turns out to be short, and which stays unused.
- External fragmentation. Gaps between requests too small to hold another whole chunk.
Their profiling found that in existing systems only 20.4% to 38.2% of the KV cache memory stored actual token data. The rest was wasted. Less usable memory means a smaller batch, and a smaller batch means lower throughput.
