Efficient Memory Management for Large Language Model Serving with PagedAttention

LLM serving is often limited by KV-cache memory, not by leftover FLOPs. Autoregressive decode appends key/value vectors every token. Systems that pre-allocate a contiguous cache for each request’s maximum length waste huge slabs when prompts are short or generations finish early. Fragmentation and reservation overhead mean the GPU sits under-batched even though average sequence length would fit.

PagedAttention (and the vLLM system built around it) borrows the OS idea of virtual memory: store KV in fixed-size blocks, track them with a block table, and allocate physical blocks on demand. Requests no longer need one giant contiguous reservation.

What this paper explains

In attention, each sequence needs keys and values for all prior tokens. Classical serving stores those as a contiguous tensor shaped like $[\text{max\_len}, \ldots]$. Problems:

1. Internal fragmentation — reserved but unused slots inside a sequence’s allocation.
2. External fragmentation — free holes that are the wrong shape for the next reservation.
3. Sharing difficulty — even identical prompt prefixes are hard to share when layouts are rigid.

PagedAttention splits KV into blocks of $B$ tokens (vLLM often uses $B=16$). A per-sequence block table maps logical token positions → physical block IDs. Attention kernels gather K/V through that mapping. When a sequence grows, allocate another block; when it finishes, free its blocks for reuse.

Prior limits

• Static pre-allocation per request max length — simple, extremely wasteful under realistic length distributions.
• Batching only equal-length or padded sequences — padding burns memory and compute.
• Copy-on-growth contiguous realloc — expensive and still fragments.

Prior LLM servers (FasterTransformer-era continuous batching systems, etc.) improved scheduling but still fought contiguous KV layouts.

The mechanism

Logical sequence positions $0..L-1$ live in $\lceil L/B\rceil$ blocks. Physical GPU memory is a pool of blocks. The attention kernel, given the block table, loads the right pages for that sequence — analogous to walking page-table entries.

Because blocks are uniform, the allocator is simple and utilization climbs toward the average live tokens rather than the sum of worst-case reservations. Prefix sharing becomes natural: two sequences can point at the same physical blocks for a shared prompt until a fork (copy-on-write style).

Algorithm / figure walkthrough

1. Choose block size $B$.
2. On request arrival, allocate blocks for the prompt (sharing if possible).
3. Each decode step: if the last block is full, allocate a new free block and append its ID to the block table.
4. Attention reads K/V via block-table indirection instead of a single base pointer + contiguous stride.
5. On finish (or preempt), return blocks to the free pool.

The opening visual contrasts one fat contiguous slab (mostly empty) with a compact grid of filled pages.

What to notice when reading

• Paging is an OS analogy, not approximate attention.
• Throughput gains come from higher effective batch size once memory waste drops.
• Block size trades indirection overhead vs fragmentation granularity.

Results and evidence

The SOSP paper shows that PagedAttention enables near-zero KV waste from reservation/fragmentation relative to contiguous allocators, and that vLLM delivers substantially higher serving throughput — often about 2–4× vs prior state-of-the-art systems on their benchmarks — by packing more concurrent sequences into the same GPU memory. Exact speedups depend on model, arrival pattern, and length distribution; use the paper’s figures as the authoritative measurements.

Limitations

• Block-table indirection adds kernel complexity vs naive contiguous attention.
• Very small blocks increase mapping overhead; very large blocks reintroduce internal waste.
• Does not by itself fix compute inefficiencies (those need FlashAttention-style kernels, quantization, etc.).
• Scheduling / preemption policies remain system-level concerns alongside paging.

How to read the paper

1. Abstract + §1 — fragmentation problem in LLM serving.
2. §2–3 — PagedAttention design and block tables.
3. §4 — vLLM system (scheduling, scheduling with paging).
4. §5 — throughput and memory experiments.
5. Related work — OS paging vs prior inference engines.

Knowledge check

Keep reading

1. Original paper (arXiv:2309.06180)
2. Related Fanout Daily: FlashAttention, Orca continuous batching, GQA.

Sources

• Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention, SOSP 2023 — arXiv:2309.06180