Kwon et al. (2023) — ARXIV-2309.06180
Key takeaways
- The bottleneck is KV cache memory management, not compute. Each request’s cache is large and grows and shrinks dynamically; allocating it contiguously for a worst-case length wastes memory to fragmentation and duplication, and that caps the batch size
- PagedAttention applies OS paging: fixed-size blocks, a per-sequence block table mapping logical to physical, and an attention kernel that reads from non-contiguous memory
- Near-zero waste, with the residual bounded by internal fragmentation in the last partially filled block — the design’s accepted trade
- Sharing within and across requests via the block table, with copy-on-write when one sharer diverges. This is where parallel sampling and beam search stop duplicating the prompt’s cache
- 2–4× throughput at the same latency against FasterTransformer and Orca, and the gain grows with longer sequences, larger models, and more complex decoding algorithms
- Iteration-level scheduling is background here, not a contribution — described in §2 and attributed to Orca, which is also one of the baselines
Standing in the anthology
The source of SOTA-105.
Read in full for #114; the reading is NOTE-023.
SOTA-113 — use continuous batching for inference — moved off this note to Orca (LIT-224), which introduced it and which was missing from the record entirely. This paper cites Orca for it. The drift has a cause worth naming: “continuous batching” is the field’s name and appears in neither paper, so nothing tied the practice to its origin.