PagedAttention

Here's a thing I think about a lot: very occasionally, an idea from one subfield of computer science walks across the room, taps another subfield on the shoulder, and changes everything. PagedAttention is one of those moments. The idea is just virtual memory, the thing operating systems have been doing since the 1960s, transplanted onto the KV cache of a language model. That's it. That single observation is why a modern inference engine can serve two to four times more users per GPU than the naive approach.

This post is about that crossover. I want to build the intuition for why the KV cache wastes so much memory by default, why virtual memory is exactly the right analogy, and how PagedAttention implements the idea in a way that attention kernels can still work with.

A quick refresher: the KV cache is the per-request store of attention keys and values. It lets the model avoid recomputing them at every decoding step. It grows linearly with sequence length and at long contexts it eats more GPU memory than the model weights themselves. So it's the scarce resource. Every serving-system innovation in this arc is, in one way or another, about managing this one resource better.

Fragmented memory, wasted GPU

When you serve an LLM, you don't know in advance how long each request will be. User A might generate 25 tokens. User B might keep going for 2,000. Your service promises to support, say, 2,048 tokens per request, and you have no idea which user will use all of it. So a naive serving system does the obvious thing: reserve max_context slots of KV cache for each active request. If the model is 70B and the context is 32k tokens, that's gigabytes of GPU memory per request, reserved up front, most of it unused.

Two things go wrong here, and they compound.

The first is internal fragmentation. A request that only generates 47 tokens still holds onto 2,048 slots of cache. 2,001 slots sit empty the entire time. Multiply by 30 concurrent requests and you've reserved 60k token slots for what, in aggregate, is maybe 1–2k filled. That's unused memory you can't hand to another request, because it's already spoken for.

The second is external fragmentation. Requests show up and leave at different times. When request A finishes, its contiguous 2,048-slot chunk becomes available. But if you have a new request that also wants 2,048 slots, and the only free regions are a 1,500-slot hole from A and an 800-slot hole from someone else, you can't use them together. The free memory is the right size in total but the wrong shape. Either you defragment (copy stuff around, which is expensive and disruptive) or you sit on unusable memory.

Kwon et al.'s original vLLM paper puts real numbers on the waste. On production workloads they measured KV-cache utilization around 20–40%, which means 60–80% of the most expensive memory on the most expensive GPU in the cluster was sitting there doing nothing. That's the problem PagedAttention set out to fix.

This is just virtual memory

The moment the vLLM paper clicked for me was when I realized the problem it's solving is exactly the same problem operating systems solved decades ago.

In the early days of multiprogramming, every process asked for a contiguous chunk of RAM. The OS had to decide where to put it. Processes of different sizes came and went. Over time the free memory turned into a jigsaw of unusable fragments. Programs couldn't fit even when there was plenty of free RAM in total. The solution, pioneered on the Atlas at Manchester and refined by the 1970s, was virtual memory.

Here's how virtual memory works, boiled down: each process sees a contiguous virtual address space, but the operating system chops it into fixed-size pages (typically 4 KB) and stores them wherever it likes in physical memory. A per-process page table maps virtual page numbers to physical frame numbers. When the process reads virtual address 0x1000, the CPU (with help from the MMU) looks up the translation in the page table and fetches the data from whatever scattered physical frame is actually holding it. The process never knows the pages aren't contiguous. The OS gets to pack physical memory however it likes.

Now read that paragraph again and replace "process" with "request", "page" with "KV block", "physical frame" with "physical block in the GPU KV-cache pool", and "page table" with "block table". That's PagedAttention. The whole thing is a one-to-one correspondence.

OS virtual memory        →   PagedAttention
------------------------------   -----------------------------
process                  →   request (one prompt + generation)
page (4 KB)              →   KV block (e.g. 16 tokens)
page table               →   block table (logical → physical block idx)
physical frame           →   physical KV block in the shared pool
page fault / alloc       →   allocate a new block on demand
copy-on-write            →   copy-on-write for shared prefixes

I think this is the most useful mental model for the entire post. If you remember "it's virtual memory for the KV cache", you can reconstruct most of the mechanics on a napkin.

PagedAttention in one picture

Here's the machinery. The KV cache is no longer one big contiguous array per request. Instead:

• GPU memory holds a shared pool of fixed-size physical blocks. A typical block is 16 tokens. Each block can hold the K and V vectors for 16 consecutive positions of one request. Blocks are allocated from the pool as requests need them and freed back to the pool when they're done.
• Each request has a logical sequence of blocks: L0, L1, L2, ... arranged in order. The first 16 tokens go in L0, the next 16 in L1, and so on.
• Each request has a small block table that maps logical block index → physical block index. table[0] = 7 means "logical block 0 of this request lives at physical block 7 in the pool".

When attention runs, the kernel doesn't assume keys and values are contiguous. It walks the block table: "logical block 0 is physical block 7, logical block 1 is physical block 3, ..." and gathers the K and V vectors from wherever they actually live. There's a little indirection cost per block, but because blocks are substantial (16 tokens × hidden dimension), the fixed cost of the lookup is amortized across many arithmetic operations. The overhead ends up in the single-digit percent range.

The payoff is that you only ever allocate what you use, rounded up to block size. A request of 47 tokens takes three blocks (48 slots). Waste per request is bounded by BLOCK_SIZE - 1 tokens, so total waste across the system is small and constant instead of growing with max_context. Kwon et al. measured the resulting cache utilization at ~96% on production-like workloads, up from 20–40%.

Copy-on-write: when two requests share a prefix

Here is where the analogy pays off twice. Operating systems have a lovely trick called copy-on-write (COW): when a process forks, instead of duplicating its entire memory, the kernel shares the parent's pages with the child and marks them read-only. The child only gets its own copy of a page the instant it writes to one. Memory stays shared as long as nobody actually modifies it, which is most of the time.

This trick transfers directly. In LLM serving, many requests share a prefix. A chat app might prepend the same 800-token system prompt to every user message. Parallel sampling (the same prompt, multiple sampled continuations) shares every token up to the first sample token. Beam search is the same, at a finer grain: beams share everything except their most recent divergent token. If every one of those shared prefixes gets its own copy of the KV cache, you're paying for the same work many times over.

With PagedAttention, the scheduler can point multiple block tables at the same physical block. Each physical block maintains a reference count. As long as the count is greater than 1, nobody is allowed to write into the block in place. The moment one request needs to write (say, because it's about to generate a new token in a block still shared with another request), the engine clones that one block, decrements the refcount on the original, and updates the writing request's table to point at the clone. Everybody else keeps pointing at the original.

Why the attention kernel works at all

One thing that bothered me when I first read the paper was: attention is a dense matrix operation. How can it possibly work on non-contiguous memory without falling apart?

The answer is that attention, at the kernel level, is already a loop that walks over keys and values one chunk at a time. FlashAttention, for example, tiles the K and V matrices into blocks that fit in SRAM and processes them iteratively. PagedAttention aligns its block size with the tile size the kernel uses anyway. Inside each block, memory is contiguous. Across blocks, you just look up the next physical block address from the block table and continue. The kernel does a little more pointer arithmetic. It doesn't rewrite attention from scratch.

Misconceptions

"PagedAttention changes the model output." No. It doesn't touch the math at all. Attention produces the exact same logits regardless of whether the K and V tensors are laid out contiguously or scattered through a pool. The only change is in how the kernel fetches memory.

"Smaller blocks are always better because they reduce waste." It's more of a tradeoff. Smaller blocks reduce internal fragmentation (less padding in the last block per request) but inflate the block-table size and add per-block overhead inside the attention kernel. They also spread memory accesses more randomly, which can hurt cache performance. Kwon et al. found 16 tokens to be a strong default.

"Copy-on-write is mostly a beam-search optimization." The paper emphasizes beam search, but in production the dominant source of shared prefixes is system prompts. One prompt, many users, many concurrent requests all starting with the same 500–2000 tokens. COW there means the cached prefix lives exactly once in GPU memory across all of them.