Third Deep Dive post, and a change of layer: the last two were about making one attention computation faster on one GPU (FlashAttention, FP8 in WGMMA). PagedAttention isn't a faster kernel — it's a different way to allocate memory for the KV cache, and it's the core idea behind vLLM, one of the most widely used LLM serving engines. The two problems are complementary, not competing: FlashAttention makes each attention computation cheaper, PagedAttention makes it possible to fit far more concurrent requests in memory in the first place.

The problem: nobody knows how long a response will be

Before generating a single token, a serving system has to reserve GPU memory for that request's KV cache. The obvious approach — reserve a contiguous block sized for the maximum possible sequence length — has to guess, because the actual output length isn't known until generation stops. Guess too high (which is the safe default) and most of that reservation goes unused. Different requests also finish at different lengths and get freed at different times, so even memory that is eventually released ends up fragmented — fixed-size gaps between other requests' allocations, too small individually to fit a new request's reservation.

The PagedAttention paper (Kwon et al., SOSP 2023) puts a number on this: existing systems waste 60–80% of allocated KV cache memory this way — before accounting for any actual computation.

The idea: borrow paging from operating systems

Operating systems solved almost this exact problem decades ago for program memory: instead of requiring a process's memory to be one contiguous region, physical RAM is split into fixed-size pages, and a per-process page table maps logical addresses to wherever those pages actually live.

PagedAttention applies the same idea to the KV cache:

Diagram comparing naive KV cache allocation, which reserves a large contiguous block per request and wastes most of it, against PagedAttention's fixed-size blocks allocated on demand, including a block shared between two requests via copy-on-write

  • The KV cache is split into fixed-size blocks — 16 tokens each by default in vLLM, though it's configurable.
  • Each sequence has a block table mapping its logical token positions to physical blocks, exactly the logical-to-physical indirection a CuTe Layout does for tensor memory, just applied to allocation instead of addressing.
  • Blocks are allocated on demand as the sequence generates new tokens, not reserved upfront for a worst-case length.

Because nothing has to be contiguous, a request only ever wastes space in its current last block — everything before that is fully used. The paper reports this brings waste down to under 4%.

The part that isn't just about waste: sharing

Paging buys something beyond eliminating fragmentation: multiple sequences can point their logical blocks at the same physical block. This is useful whenever generation branches from a common prefix — several parallel samples from one prompt, or beam search candidates that share their early tokens. Those requests' block tables just point at identical physical blocks for the shared portion; a block is only copied (copy-on-write) once one of the branches actually needs to write something different into it.

The vLLM team reports this cuts memory usage for parallel sampling and beam search by up to 55%, and that reduction alone is worth up to a 2.2x throughput improvement — memory saved on shared prefixes is memory available for more concurrent requests.

What it adds up to

Combining reduced waste with sharing, the original vLLM benchmarks report 2–4x higher throughput than FasterTransformer and Orca at equivalent latency, and vLLM's own announcement post cites up to 24x higher throughput than a naive HuggingFace Transformers serving loop, and up to 3.5x over HuggingFace's TGI, depending on the workload.

Why this is worth knowing even if you never write a memory allocator

It's tempting to read "faster LLM serving" as one undifferentiated category, but the last three Deep Dive posts on this blog have each been about a genuinely different bottleneck: FlashAttention rewrites how an attention computation moves data through memory during a single kernel; FP8 in WGMMA is about register-level data layout inside that kernel; PagedAttention doesn't touch the attention computation at all — it changes how memory gets allocated before any computation starts. All three matter for the same end goal (serve more requests per GPU, faster), and none of them substitute for the others. That's the pattern worth taking away: "make LLM inference faster" is never one fix, it's a stack of fixes, each addressing a bottleneck at its own layer.

References

Block diagram above is original artwork made for this post.