What problem does PagedAttention solve for the KV cache in vLLM?

## What the KV cache is During autoregressive decoding, every previously generated token's key and value vectors must be available for the attention computation of the next token. Recomputing them each step would be quadratic, so servers cache them. The cache grows by one entry per token per layer, and it is the dominant *variable* memory cost of serving — model weights are fixed, KV cache scales with context length times concurrency. ## The pre-paging allocation problem Early serving stacks allocated the KV cache as one contiguous tensor per sequence. The size had to be chosen at admission time, before a single token had been generated, so implementations reserved room for the maximum possible length. Three kinds of waste followed: - **Internal waste**: a sequence that reserves 4096 slots and emits 60 tokens leaves ~98% of its reservation untouched for its whole lifetime. - **Reservation waste**: the space is unusable by anyone else even though it is provably empty. - **External fragmentation**: variable-sized contiguous reservations leave holes too small for the next request even when total free memory is ample. Measurements in the vLLM paper found that only a small fraction of KV memory in such systems held live tokens; the rest was reserved or fragmented. Since KV capacity determines how many sequences can run at once, that waste directly caps throughput. ## The paging idea Operating systems solved the identical problem with virtual memory: give each process a logical address space, split physical memory into fixed-size pages, and keep a page table mapping one to the other. Physical pages need not be contiguous, and they are allocated lazily. PagedAttention applies this to attention. The GPU's KV memory is a pool of fixed-size **blocks**, each holding a small number of tokens' keys and values for all layers and heads (vLLM's default block size is 16 tokens). Each sequence owns a **block table**: an ordered list of physical block ids for its logical positions. The attention kernel is written to gather keys and values through that table rather than assuming contiguity — this is the part that required a custom CUDA kernel, not just a bookkeeping change. Allocation is now incremental. A sequence starts with just enough blocks for its prompt, gains one block every 16 generated tokens, and returns all of them when it terminates. Waste per sequence is at most one partially filled block — a few tokens instead of thousands — and because every block is the same size, any free block satisfies any request, so external fragmentation cannot occur. ## Sharing, the second dividend Once a sequence's view of memory is an indirection table, two sequences can list the *same* physical block. Two use cases follow directly: - **Parallel sampling and beam search**: N candidates from one prompt share the prompt's blocks instead of holding N copies. When a shared block must diverge, the engine copies it first — copy-on-write, with a per-block reference count. - **Prefix caching**: many production prompts share a long fixed preamble — a system prompt, a tool catalogue, a retrieved document. If the tokens match, the blocks holding their KV state can be reused across requests, skipping that part of prefill entirely. vLLM exposes this as prefix caching; it cuts both time-to-first-token and prefill compute for prompt-heavy workloads. ## Operational consequences The headline effect is that a given GPU sustains a much larger running batch, which is precisely what continuous batching needs to pay off — the two features are complementary, not alternatives. vLLM sizes the block pool from the memory left after weights and activations, governed by `--gpu-memory-utilization`, and it will refuse to start if the remaining pool cannot hold even one sequence at `--max-model-len`. Under sustained overload the pool still fills. vLLM then **preempts** sequences: their blocks are freed and their state is either recomputed on readmission or swapped out. Preemption shows up in the server's metrics and as latency spikes, and it is the signal to lower max context, raise the memory fraction, quantize, or add capacity. Note also that paging removes *waste*, not *demand*: a workload that genuinely uses 128k-token contexts needs that memory regardless. TGI and other modern servers implement equivalent paged KV management, so the concept is portable across stacks rather than a vLLM-only trick.