PagedAttention stores the KV cache in fixed-size non-contiguous blocks mapped by a block table — borrowing OS virtual memory to kill fragmentation and pack more sequences onto a GPU.
Imagine a library that insisted every book's chapters sit on one unbroken stretch of shelf. To be safe it reserves a huge run of empty shelf per book, just in case the book turns out long. Most books are short, so most of that reserved shelf sits empty — wasted. PagedAttention instead lets a book's chapters live on any scattered shelf slots, with an index card saying where each chapter is. Now almost no shelf space is wasted, and far more books fit. That index-card trick is exactly how operating systems manage computer memory.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Ask a serving engineer what limits how many requests a single GPU can handle, and the answer is almost always the KV cache. Every active sequence keeps a cache of keys and values for the tokens it has already processed, the cache grows one token at a time, and on a busy server the sum of all those caches is what saturates GPU memory first — before compute, before bandwidth.
That makes KV-cache layout a first-class system design problem, not a detail. And the layout that early serving systems chose — one contiguous block per sequence — turns out to waste a startling fraction of GPU memory, because you have to reserve space for an output length you can't predict.
PagedAttention's insight is that this is a problem operating systems already solved fifty years ago. The exact scenario — logically contiguous data that should be allowed to live in scattered physical chunks to avoid reserving worst-case space — is what virtual memory and paging were invented for. This section traces the KV cache's memory cost, why contiguous allocation wastes it, how borrowing the page-table idea fixes it, and the bonus capability — cheap KV sharing — that the indirection unlocks almost for free.
Why the KV cache is the resource that runs out
During generation, attention at each step needs the keys and values of every previous token. Recomputing them every step would be quadratic and wasteful, so the server caches them — that's the KV cache. It holds two tensors (K and V) per token, per layer, per attention head.
The size adds up fast. The cache for one sequence scales with the number of tokens times layers times heads times head dimension times two (K and V) times the bytes per value:
For a large model with long context, a single sequence's cache can run to gigabytes, and you're serving many sequences at once. So total KV memory, not FLOPs, is what caps concurrency.
The awkward part is T, the token count: you don't know it in advance, because the model generates until it decides to stop. That uncertainty is the root of the allocation problem. Any scheme that needs to commit memory up front has to guess how long each sequence will get — and guessing wrong is exactly where the waste comes from.
Situations where this technique stops working.
2–4 min · Everything important, quickly.
| Aspect | Contiguous KV cache | PagedAttention |
|---|---|---|
| Allocation | One block per sequence, max-sized | Fixed-size blocks on demand |
| Internal fragmentation | Large reserved but unused tails | At most one partial block per sequence |
| Concurrency | Capped by wasted memory | Far higher; memory near-fully used |
| KV sharing | Hard; blocks are private | Easy via shared blocks + copy on write |
Real products, models, and research that use this idea.
- vLLM is the serving engine that introduced PagedAttention and ships it as the default KV-cache manager.
- Hugging Face TGI and other modern serving stacks adopted paged KV-cache management following vLLM.
What an interviewer would ask next. Try answering before peeking at the approach.
QHow does the attention kernel change when K and V no longer live in one contiguous tensor?
The kernel must gather keys and values across scattered physical blocks using the block table, instead of indexing a single contiguous array.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Thinking PagedAttention is a faster attention kernel, when it's really a memory-management scheme for the KV cache modeled on OS paging.
60 second bullets to scan on the way to the call.
What the KV cache stores and why it grows with sequence length
Why contiguous per-sequence allocation causes internal fragmentation
Primary sources. Browse if you want the original framing.
Same topic, related formats. Practice these next.