A serving engine cannot know exactly how many output tokens every request will produce. Reserving each request’s maximum possible KV cache is simple, but idle capacity inside those reservations limits how many requests fit.
PagedAttention addresses the organization of that state. It lets attention operate over KV blocks that need not occupy one contiguous physical allocation per sequence. The important idea is an indirection between the sequence’s logical token positions and the blocks holding their keys and values.
Borrow the abstraction, not the entire operating system
Virtual memory gives programs a convenient address space without requiring matching physical layout. The analogy here is useful but limited: a serving engine’s KV block table is not necessarily an OS page table, and PagedAttention does not imply disk paging or hardware page faults.
Logical sequence: block 0 -> block 1 -> block 2
Physical storage: slot 7 slot 2 slot 11The attention kernel uses the mapping to find the relevant KV data. Token order is preserved logically even though physical blocks are scattered. This changes memory management and kernel addressing, not the model’s causal ordering.
The linked vLLM kernel walkthrough is explicitly historical, not a map of its current source tree. Modern attention backends can implement the same block-table idea differently. Match implementation-level claims to the engine revision and backend you are actually using.
Grow allocation with the sequence
Suppose a teaching allocator uses 16-token blocks and a request currently holds 33 tokens. It needs three blocks, with 15 token positions unused in the last block. A 32-token request would need two blocks exactly.
This is internal slack, not a measured runtime overhead. Real allocation includes metadata, alignment, implementation details, and possibly model-specific cache groups. The KV calculator deliberately models only conventional uniform layers and independent sequences.
Smaller blocks can reduce final-block slack but increase mapping and bookkeeping work. Larger blocks can simplify some operations while wasting more capacity for short or irregular sequences. A claim about “zero fragmentation” should specify which kind of waste is being discussed.
Shared blocks need ownership rules
If two requests share an identical reusable prefix, immutable prefix blocks can be referenced by both rather than stored twice. Reference counting and copy-on-write-style handling can protect shared state when sequences diverge.
The word identical matters. KV states depend on the model and preceding context, not just a matching substring. Prefix reuse also requires compatibility with the runtime’s tokenization, positional handling, adapters, and supported architecture.
Paging enables a useful representation for sharing; it does not establish every cache-key or isolation rule. The prefix caching article covers that separate problem.
Reproduce the allocation reasoning first
In the visualizer, set one sequence, block size 16, and context 33. Compare the live tensor bytes with rounded allocation. Change context to 32 and observe slack disappear. Increase concurrency and note that the calculator duplicates all sequences because it does not assume sharing.
For a real runtime experiment, record the engine version, model revision, attention backend, precision, block configuration, prompt/output length distribution, and hardware. Then compare peak KV usage, active requests, preemptions, throughput, and latency under the same workload.
Read the paper’s measurements alongside its hardware and workload description. Use the allocation example here to reason about capacity, then measure the serving configuration you intend to use.
What paging does not remove
The model still needs to access relevant KV state during attention. Long contexts can increase memory traffic and attention work even when allocation is efficient. Model weights, activations, temporary buffers, and communication also consume resources.
More requests fitting in memory can improve batching opportunities, but a larger batch may change latency. Allocation efficiency is an input to scheduling, not a promise that every request finishes sooner. Evaluate it alongside continuous batching, rather than treating memory utilization as the final performance objective.
Further reading
Primary references behind this explanation. Consult documentation for the version and environment you actually run.