Skip to content
Published on

Inside vLLM (2) — Why PagedAttention Splits the KV Cache Into Pages

🇰🇷KO🇺🇸EN🇯🇵JA🇨🇳ZH
Split View필사 모드
Share
Authors

Why Bring Up Paging Again

Part 1 mapped out the path a request travels. This part looks at the piece of that path that eats the most GPU memory: the KV cache.

A single request being generated has to hold the key and value tensors for every token it has seen so far. Throw that away, and every additional token would require recomputing the entire sequence from scratch. The problem is that this chunk of memory is a different size for every request, and it keeps growing as generation proceeds. There is no way to know in advance how much it will grow, because there is no way to know in advance when the model will stop.

The problem of continually appending to data whose final size is unknown is not new. Computer science has solved it before, in the form of an operating system's virtual memory and paging. The PagedAttention paper states outright that it brought exactly that idea over to attention.

Everything here was verified against the official documentation and source on 2026-08-12. vLLM moves fast, so re-check settings and behavior against the documentation for the version you are running.

Two Kinds of Waste That Contiguous Allocation Creates

Looking at the pre-paging approach first makes clear why paging was needed. A naive implementation reserves a contiguous block of memory sized to "the maximum length this request could ever use" as soon as the request arrives. It is safe, and it is easy to implement. It is also enormously wasteful.

Assuming a max of 2048 tokens, contiguous space reserved in advance for each request

Request A: [■■■■■□□□□□□□□□□□□□□□□□□□]  used 320  / reserved 2048
Request B: [■■□□□□□□□□□□□□□□□□□□□□□□]  used 96   / reserved 2048
Request C: [■■■■■■■■■■■■■■□□□□□□□□□□]  used 1180 / reserved 2048

■ space actually used   □ reserved but unused (internal fragmentation)

This creates two kinds of waste.

The first is internal fragmentation. It is every empty square in the picture above. Request B finished after using only 96 tokens, yet it held on to a 2048-token slot the whole time. The more a service leans toward short answers, the bigger this loss gets. And that space cannot be used by any other request, because it already belongs to B.

The second is external fragmentation. As requests finish, small holes open up here and there, but each hole is small while a new request needs one large contiguous span. This is how you end up with "out of memory" even though the total free memory, added up, would have been enough.

The Block Table: Logically Contiguous, Physically Scattered

PagedAttention's solution is to stop handing a request one large contiguous span. Instead, the KV cache is cut into fixed-size blocks, and a request is handed one block at a time as it needs them, wherever that block physically happens to sit.

So how does the attention kernel see these scattered pieces as a single sequence? The block table bridges the gap. Each request keeps a mapping like "my block 3 is physical block 41," and the kernel follows this table to find the block it needs. It is the same job an operating system's page table does.

Request A's view (logical)      Block table        Actual GPU memory (physical)
┌───────────────────────┐                       ┌────┬────┬────┬────┐
│ logical block 0 1 2 3 │   0 → physical 7      │ 0  │ 1  │ 2  │ 3  │
│ one unbroken sentence │   1 → physical 2      ├────┼────┼────┼────┤
└───────────────────────┘   2 → physical 19     │ 4  │ 5  │ 6  │ 7  │
                            3 → physical 4      ├────┼────┼────┼────┤
                                                │ …  │ 19 │ …  │ …  │
                                                └────┴────┴────┴────┘

This structure eliminates both kinds of waste at once. External fragmentation disappears by definition, because every block is the same size, so any free block can go to any request. Internal fragmentation shrinks down to just the leftover space in the last block, at most the block size minus one token per request. This is the basis for the paper's claim that it reduces KV cache waste to near zero.

The vLLM design documentation specifically notes that this kind of block is a different concept from a GPU thread block. It is an easy point to confuse when reading the docs, so the authors call out the distinction up front.

The Block Size Trade-off

So how is block size decided? vLLM has a --block-size argument. In the source, though, CacheConfig declares this value without a fixed default, and the documentation only says that a default is used if you do not supply one. The number that actually gets applied is decided by the platform and the attention backend. So this post will not name a specific number as the default. The default varies by version and environment, so check your startup logs and the documentation for the version you are running.

The direction of the trade-off, though, is clear.

Set the block size large, and the number of blocks drops, which lightens management overhead and table lookups. In exchange, more space gets wasted in the last block. And because prefix caching, covered in part 5, only reuses blocks that are completely full, a larger block size makes it easier to miss the whole block over a small difference in the prompt.

Set it small, and waste goes down and cache hits align more finely. In exchange, representing the same sequence takes more blocks, and the block table gets longer.

In practice, this is rarely the first value you touch. Adjusting --gpu-memory-utilization and the length limits first usually has a bigger effect. Still, it is worth remembering that block size belongs on the suspect list when prefix cache hit rate comes in lower than expected.

Sharing: A Second Effect That Cuts Waste

Managing memory in blocks brings one more benefit along with it: multiple requests can point to the same block if it holds identical content. The paper places this flexible sharing alongside its other results as a core contribution.

Picture a hundred requests arriving at once, all sharing the same system prompt. Under contiguous allocation, that same leading segment gets computed a hundred times and stored a hundred times. Under the block scheme, you keep just one copy of the blocks that make up that leading segment, and a hundred block tables all point at the same physical blocks. Extending this idea across requests is prefix caching, the topic of part 5.

What the Original Paper Actually Claims

To avoid overstating anything, here is the source stated precisely. The original paper is arXiv:2309.06180, titled Efficient Memory Management for Large Language Model Serving with PagedAttention. Written by Woosuk Kwon and others, it introduced PagedAttention and vLLM together for the first time.

The results the abstract states are these: it nearly eliminates KV cache memory waste, it shares KV cache flexibly within and across requests, and at the same level of latency it raised throughput 2 to 4 times over the state-of-the-art systems of the time.

One thing to be careful about here. That 2 to 4 times figure comes from a 2023 paper comparing against the baselines of that time. It is not a number your deployment will produce today. vLLM itself has been substantially rewritten since then, and every comparison target has moved forward too. It is more accurate to read this paper as the rationale for a design, not as a performance guarantee.

Try It Yourself

References

Discuss on Twitter • View on GitHub