PagedAttention is the idea that made vLLM the default high-throughput serving engine, and it is borrowed almost verbatim from an operating system. Classic serving reserves one big contiguous slab of GPU memory for each sequence’s KV cache, sized to the maximum possible length — and then wastes most of it, because real sequences are shorter and finish at unpredictable times. PagedAttention instead chops the KV cache into small fixed-size blocks, hands each sequence a block table that maps its logical token positions onto physical blocks scattered anywhere in memory, and lets the attention kernel gather those non-contiguous blocks on the fly. Memory waste falls from tens of percent to almost nothing, which translates directly into more sequences in flight and higher throughput. This piece walks the mechanism from first principles: why contiguous allocation bleeds memory, what a block and a block table are, how both fragmentation modes disappear, how copy-on-write shares prefixes for free, and what the kernel does to read a contiguous sequence out of physically scattered pages.
Why contiguous KV allocation bleeds memory
During autoregressive decoding, every token a model has already seen contributes a key and a value vector per layer per head that must be kept around — the KV cache. Its size grows with the sequence length, and the naive way to store it is one contiguous buffer per sequence. But you do not know in advance how long a sequence will be, so a request that could reach the 4096-token context limit forces you to reserve room for 4096 tokens up front.
Most requests never get close. A chat reply might be 200 tokens; you reserved 4096. The other 3896 slots sit allocated but empty, unusable by any other sequence because they belong to a contiguous reservation. Across a batch this compounds: the GPU reports its KV memory as full while useful occupancy is a fraction of that. The vLLM authors measured real systems wasting 60–80% of KV memory this way — and that wasted memory is the hard cap on how many sequences you can serve at once, and therefore on throughput.
The operating-system analogy
This is exactly the problem virtual memory solved for processes fifty years ago. A program wants to believe it has one long contiguous address space; physical RAM is finite and shared. The OS reconciles the two with paging: it splits memory into fixed-size pages, lets a process’s logically contiguous addresses map to physically scattered page frames, and keeps a page table to record the mapping.
PagedAttention lifts this design directly. A sequence’s KV cache is the ‘address space’ it wants to see as contiguous. A KV block is the page — a fixed-size chunk holding keys and values for a small number of tokens (commonly 16). The block table is the page table, mapping each logical block to a physical block in the GPU’s KV pool. Because the mapping is indirected through the table, physical blocks need not be adjacent, and memory is handed out one block at a time, on demand, as tokens are generated.
Anatomy of a KV block
A block is the unit of allocation. If the block size is B tokens, one block for one layer holds a tensor of keys shaped [B, n_kv_heads, d_head] and an identically shaped tensor of values. The full KV memory is a large pool of these fixed-size slots, allocated once at startup and never fragmented afterward because every block is the same size. A sequence acquires blocks lazily: it starts with none, and each time it fills its current last block it requests one more. Block size B is the one tuning knob — small blocks minimize wasted tail and sharpen prefix sharing but inflate the block table and shrink each memory read; values around 16 balance the two for typical GPUs. A 200-token reply thus holds ⌈200 / 16⌉ = 13 blocks — not the 256 a 4096-token reservation would have pinned.
The block table: logical to physical mapping
Each running sequence owns a small block table: an array indexed by logical block number whose entries are physical block numbers into the shared pool. Logical block 0 is the sequence’s first B tokens, logical block 1 the next B, and so on; the table says where each one physically lives.
To locate the KV for token position t, the runtime computes logical_block = t // B and offset = t % B, looks up physical = block_table[logical_block], and indexes into that block at offset. The logical view is perfectly contiguous while the physical blocks are scattered arbitrarily across the pool. This indirection is the whole trick: it decouples the sequence’s apparent layout from where bytes sit, so the allocator can reuse any freed block for any sequence without ever needing a contiguous run.
Both fragmentation modes disappear
Internal fragmentation is space reserved for a sequence but not yet used. Under contiguous allocation it was catastrophic: reserve 4096 slots, use 200, waste 3896. Under paging it is bounded by the block size, because a sequence only holds blocks it has begun to fill and the sole waste is the unfilled tail of its last block. With B = 16 that is at most 15 token-slots — for a 200-token sequence, 8 wasted slots out of 208, under 4% versus over 95% before. The waste no longer scales with the context-length limit; it is a small constant per sequence.
External fragmentation is the other classic failure: free memory exists but is broken into pieces too small or scattered to satisfy a request needing a contiguous run — and contiguous KV allocation suffers badly, as sequences of different sizes start and finish at different times, carving the pool into a patchwork of holes. Paging eliminates it by construction: every block is the same size, so any free block satisfies any request and no free space can ever become unusable. Removing both modes, leaving only the bounded last-block remainder, is the deeper reason PagedAttention reaches near-zero waste.
Copy-on-write for shared prefixes
Because blocks are addressed indirectly, two sequences can point their block tables at the same physical block. That makes prefix sharing almost free. When you sample several completions from one prompt, or many requests reuse a long shared system prompt, the identical prefix tokens produce identical KV, so all those sequences can share the physical blocks holding the prefix — storing it once instead of N times.
The sharing is made safe with copy-on-write, again straight from OS paging. Each physical block carries a reference count, and reads by any number of sharers are fine. The moment one sequence needs to write into a shared block — because its generated tokens now diverge from the siblings — the runtime copies that single block, gives the writer a private copy, and decrements the original’s reference count. Only the one block at the point of divergence is copied; everything before it stays shared. For parallel sampling and shared-prompt workloads this cuts KV memory dramatically.
The PagedAttention kernel: gathering scattered blocks
Indirection is cheap to describe and hard to make fast, because a GPU attention kernel wants to stream contiguous memory. If a sequence’s KV is scattered across non-adjacent physical blocks, a naive kernel stalls chasing pointers. The PagedAttention kernel is written specifically to handle this: it takes the sequence’s block table as an input and, for each block of keys and values it needs, looks up the physical block number and reads from there.
Concretely, the kernel iterates over the logical blocks of the sequence; for each it dereferences block_table[i] to find the physical location, loads that block’s B keys, computes the QK^T scores for those positions, and accumulates into a running softmax — the same online-softmax accumulation used by FlashAttention, so no full score matrix is ever materialized. The gather happens at whole-block granularity, keeping each read large enough to be efficient while the block table absorbs the scattering — so logically contiguous attention runs correctly over physically fragmented memory at near-contiguous speed.
Worked example: waste before and after
Put numbers on it. Serve 40 concurrent chat requests on a model with a 4096-token context limit, and suppose their lengths average 300 tokens. Under contiguous allocation each reserves 4096 token-slots, pinning 40 × 4096 = 163,840 slots while genuinely using 40 × 300 = 12,000 — about 7.3% occupancy. Over 92% of KV memory is reserved-but-idle, and that idle memory is what stops you admitting a 41st request.
Under PagedAttention each request holds only ⌈300 / 16⌉ = 19 blocks — 304 slots — totaling 40 × 304 = 12,160 slots at about 98.7% occupancy, the residual being sub-block tails. The same GPU that held 40 sequences contiguously now fits roughly 163,840 / 304 ≈ 539 sequences’ worth of blocks. That order-of-magnitude jump in admissible concurrency is the throughput win — purely from not reserving memory you are not using yet.
Implications for small models and constrained memory
The lesson generalizes well beyond giant GPUs. Any setting where KV memory is the binding constraint — a small language model on a modest accelerator, or CPU-side serving with tight RAM — benefits from the same discipline: allocate KV in fixed blocks on demand, indirect through a block table, and never reserve for the worst-case context length. On memory-starved hardware the difference between 7% and 98% KV occupancy can be the difference between serving one request and serving a useful batch.
The pitfalls are practical. The block-table lookup adds an indirection the kernel must handle, so paging only pays off with a kernel written for it. Reference counting for copy-on-write must be exact, or you get corruption or leaks. Handle those, and PagedAttention turns KV memory from a coarse, wasteful reservation into a densely packed, OS-style paged pool — which is why it underpins essentially every high-throughput inference server.