PagedAttention & Continuous Batching

Prior to 2023, LLM inference engines pre-allocated contiguous GPU memory tensors sized to the maximum possible sequence length of each request, wasting 60% to 80% of KV cache capacity on unused reservation slots and fragmentation. Building on Orca’s iteration-level scheduling (OSDI 2022), researchers at UC Berkeley introduced PagedAttention and the vLLM engine in June 2023 (SOSP 2023). By mapping logical KV token blocks to physical GPU memory pages through a block table, PagedAttention enabled near-zero memory waste and copy-on-write prefix sharing. The mechanism was rapidly adopted across TensorRT-LLM, Text Generation Inference (TGI), SGLang, and llama.cpp.

Sources: s1, s2, s3

During autoregressive generation, GPU memory capacity—not raw FLOPs—typically limits how many concurrent requests a server can batch together. Because output lengths are unknown in advance, contiguous memory allocation forces servers to run tiny batch sizes, leaving GPU compute units idle. PagedAttention frees that stranded memory so the scheduler can pack 2x to 4x more concurrent sequences into a single continuous batch, directly multiplying serving throughput and enabling zero-copy sharing of common system prompts or parallel beam/sample prefixes.

Sources: s1, s2

When ten concurrent users query a customer-support model that shares a 4,000-token system prompt, a vLLM server stores the system prompt’s KV blocks once in physical GPU pages and points all ten requests’ logical block tables to those shared read-only pages. As each user generates a different response, new physical pages are allocated on demand in 16-token blocks, and as soon as one request emits its end-of-sequence token, its pages are immediately reclaimed and assigned to a newly arriving request on the very next forward pass.

Sources: s1, s3

Non-contiguous memory lookups introduce pointer-indirection overhead inside custom attention kernels, which requires carefully tuned CUDA/Triton block sizes and can slightly increase per-step kernel latency compared with contiguous FlashAttention when batch sizes are small. Moreover, paging manages memory layout but does not shrink the total number of KV bytes required by a single ultra-long sequence unless combined with quantization or architectural compression such as GQA or MLA.

Sources: s2, s3