The most useful lesson in PagedAttention is not simply that it borrows paging from operating systems. It is a more counterintuitive result. In the paper’s microbenchmark, block-table lookups and variable-length handling make its attention kernel 20–26% slower than a highly optimized contiguous-memory implementation. Yet vLLM, the serving system built around it, achieves substantially higher end-to-end throughput.

How can a slower local operator produce a faster system? Online inference is often constrained less by a few microseconds in one attention call than by how many growing sequences fit in GPU memory at once. PagedAttention pays for indirection to waste less KV-cache memory, build larger dynamic batches, and share prefixes safely. It optimizes system-level concurrency rather than one formula.

A KV Cache Is a Set of Live Objects with Unknown Lengths

Autoregressive decoding emits one token at a time. Keys and values from earlier tokens stay in GPU memory so the next query does not recompute them. This KV cache begins with the prompt, grows at every step, and disappears when the sequence ends.

That object has three inconvenient properties: its final length is unknown, requests arrive and finish independently, and every decoding step needs fast access to all preceding state. Earlier serving systems commonly reserved one contiguous region per sequence, sized by a maximum length or an output-length estimate. The layout was friendly to ordinary tensor kernels but created three kinds of waste: space reserved for tokens that did not exist yet, unused capacity inside allocations, and external holes left among differently sized allocations.

In the PagedAttention paper’s baseline experiments, only 20.4%–38.2% of allocated KV-cache memory stored actual token state. This is not a universal production ratio. It does expose the systems problem: unchanged model weights and unchanged arithmetic can still leave requests outside the batch because allocation wastes the remaining memory.

The Block Table Separates Logical from Physical Contiguity

PagedAttention divides a sequence’s KV cache into logical blocks, each covering a fixed number of tokens. GPU memory is divided into equal-size physical blocks. Logical blocks 0, 1, and 2 remain consecutive from the request’s perspective, but they may map to physical blocks 7, 1, and 3. A block table stores that mapping.

At admission, the system allocates only enough physical blocks for the prompt. New tokens fill the last block. Only after that block becomes full does the manager take another block from the free pool and append a mapping. Memory grows with the real sequence instead of its maximum possible future.

Paging does not eliminate internal fragmentation. The final block of every active sequence may still be partially empty. It confines the waste to at most one block, rather than an entire maximum-length reservation. The official launch post reported less than 4% waste in its tests. Blocks are not free to shrink indefinitely: smaller blocks reduce tail waste but add table entries and addressing overhead; larger blocks improve parallel access but increase fragmentation. The paper found a 16-token block to work well for its workloads. That is an empirical operating point, not a constant for every model and accelerator.

The attention kernel must understand this layout. It can no longer sweep one contiguous KV tensor. It follows the table, fetches separate K/V blocks, and performs scores, softmax, and weighted sums block by block. Attention mathematics is unchanged; address discovery is not. Indirection, branches, and variable lengths explain part of the paper’s 20–26% kernel-latency penalty.

One Physical Block Can Safely Belong to Several Sequences

Paging also makes sharing natural. Parallel samples, beams, and requests with an identical prompt contain the same prefix KV cache. Copying that prefix into every branch wastes both memory and bandwidth. With block tables, several logical sequences can point their prefix entries at the same physical blocks.

vLLM maintains a reference count per physical block. Read-only prefix sharing needs no copy. If one branch must modify a shared tail block, the system performs copy-on-write: copy that block, update only that branch’s table, then write. Earlier full blocks remain shared. The paper reports up to 55% KV-cache memory savings in its beam-search setting. That gain follows the sharing pattern and should not be projected onto every sampling workload.

vLLM’s later automatic prefix caching turns “blocks can be shared” into “blocks can be found.” A full KV block is identified from its parent hash, block tokens, and extra context such as LoRA IDs, multimodal hashes, or a cache salt. When a new request matches an existing prefix, it can reuse those KV blocks and skip the corresponding prefill computation. The layers should remain distinct: PagedAttention supplies block-level storage and mapping; prefix caching additionally needs content addressing, eviction, and tenant-isolation policy.

Larger Effective Batches Are the Throughput Transmission

Decode is commonly memory-bound. Each step adds one token but reads model weights and an expanding cache. Executing more requests together amortizes weight traffic and scheduling overhead. Yet request lengths differ: one request enters prefill, another has decoded hundreds of steps, and a third finishes now.

Iteration-level scheduling, often called continuous batching, lets the engine remove completed requests and admit new ones after each iteration. PagedAttention did not invent that scheduler. It makes the scheduler’s changing batch practical by letting memory be recomposed as requests enter, grow, fork, and exit. The causal chain is:

On-demand blocks and sharing → less KV waste → more simultaneous sequences → larger effective batches → higher GPU utilization and serving throughput.

In its 2023 OPT and LLaMA experiments on hardware including A100 and A10G, the paper reports roughly 2–4× throughput over FasterTransformer and its Orca reproduction. In ShareGPT basic sampling, vLLM sustained 1.7–2.7× higher request rates than the infeasible Orca Oracle, which knew output lengths in advance. That comparison makes the point sharply: dynamic memory management can outweigh a slower attention kernel.

Those multipliers belong to particular models, traces, hardware, and baselines. A modern engine must also be judged by time to first token, time per output token, tail latency, concurrency, prompt/output distributions, quantization, and scheduling policy. Throughput without these conditions is not portable.

FlashAttention and PagedAttention Pay Different Bills

Both names contain “Attention,” and both care about memory, but they attack different problems.

FlashAttention reorganizes data movement inside one attention operation. Tiling and online softmax avoid materializing the full score and probability matrices in HBM. PagedAttention organizes KV caches across many requests. Block tables let a logically contiguous sequence occupy non-contiguous physical memory and support on-demand growth and sharing. One changes operator dataflow; the other changes serving data structures and resource management.

They can coexist. Prefill needs efficient processing of large query tiles; decode especially needs growing KV state, scheduling, and efficient paged-decode kernels. Modern vLLM also supports multiple attention backends, so its performance should not be reduced to one paper-era CUDA kernel. PagedAttention’s durable impact is the idea that KV cache is a dynamic resource requiring operating-system-like management.

Paging Is Not a Free Lunch

The tradeoffs are concrete. Block translation and non-contiguous access increase kernel complexity and can hurt locality; the paper’s microbenchmark says so directly. Block size is workload-dependent, and short sequences, long contexts, GQA/MLA, and hybrid attention models may want different layouts. GPU capacity is only one bottleneck: prefill compute, inter-GPU communication, CPU frontend work, sampling, queues, and service-level objectives may dominate next.

Paging also answers “where is this state stored?” rather than “which state deserves to stay?” Prefix-cache hit rate, eviction, tenant isolation, and cache salts affect both efficiency and security. Cross-tenant reuse can even create timing side channels. Block management is infrastructure, not a complete caching policy.

That systems view is precisely the contribution. PagedAttention does not reduce parameter count or remove attention’s mathematical complexity. It redefines KV cache—often treated as a tensor detail—as a runtime object that must be allocated, mapped, reference-counted, copied on write, and coordinated with scheduling.

There is therefore no contradiction in a slower local kernel making the whole system faster. Once the objective changes from “finish one operator soonest” to “use finite memory for the most useful concurrent work,” indirection is no longer pure overhead. It is the price of buying concurrency—and the central design lesson of vLLM and PagedAttention.

References

1. Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention, SOSP 2023.
2. vLLM Team, vLLM: Easy, Fast, and Cheap LLM Serving with PagedAttention, 2023.
3. vLLM Project, vLLM official repository.
4. vLLM Documentation, Automatic Prefix Caching.
5. vLLM Team, Inside vLLM: Anatomy of a High-Throughput LLM Inference System, 2025.