TL;DR: PagedAttention stores each sequence's KV cache in fixed-size blocks (16 tokens each in vLLM) that need not be contiguous, with a per-sequence block table mapping logical positions to physical blocks, exactly as an OS maps virtual pages to frames. That removes the reservation waste of contiguous allocation, which can idle half of GPU memory, and it makes prefix sharing and copy-on-write a table edit instead of a memcpy.
How to approach it
State the problem before the mechanism: KV cache size is unknown at admission because output length is unknown, so a contiguous allocator must reserve for the worst case. Ask what the engine's max sequence length and typical output are, since those two numbers set the waste. Then describe the block table, do the fragmentation arithmetic for a concrete model, and finish with what non-contiguous storage buys beyond packing: shared prefixes, beam forks and cheap swap.
A strong answer
A typical situation: an engine reports its KV pool 95% allocated and serves 12 concurrent users on hardware that should hold 40. The memory is reserved for tokens that were never generated, and the fix came from operating systems rather than from machine learning.
A sequence's cache grows by one token per decode step, and nobody knows at admission how many steps it will take. Pre-vLLM engines handled that by allocating max_seq_len × per-token bytes as one contiguous slab per request. The waste has three parts: internal fragmentation (space reserved past where the sequence stops), external fragmentation (gaps between slabs of different sizes that no new request fits into), and reservation (memory held for a request that will never use it). A typical measurement in the vLLM paper (Kwon et al., SOSP 2023) found 60 to 80 percent of KV memory wasted this way.
inputs: Llama 3.1 70B bf16, KV per token = 328 KB, engine max_seq_len = 8,192
a chat request: prompt 600 tokens, output 250 tokens, total used = 850 tokens
contiguous reservation = 8,192 × 328 KB ≈ 2.69 GB per request
actually used = 850 × 328 KB ≈ 0.28 GB
waste per request ≈ 2.41 GB, about 90% of the reservation
KV budget on 8 × H100 after weights ≈ 435 GB
contiguous: 435 ÷ 2.69 ≈ 161 concurrent requests, most of the pool idle
paged (16-token blocks, 5.2 MB each): 850 tokens → 54 blocks ≈ 0.28 GB
435 ÷ 0.28 ≈ 1,550 concurrent requests of this shape
sanity: the usable concurrency rose close to 10x, which matches the throughput
gains the paper reports on short-output workloads
The mechanism is the OS page table. Physical GPU memory is carved into blocks of 16 tokens' worth of K and V for one layer (vLLM keeps one block pool per layer, or a layered layout, depending on version). Each sequence owns a block table: logical block 0 maps to physical block 731, logical block 1 to 12, and so on. The attention kernel takes the table, gathers the right physical blocks for each query, and computes scores across them. Only the last block is partially filled, so internal waste is at most 15 tokens per sequence, and there is no external fragmentation because every block is the same size.
The block table is what makes three other features cheap:
| Feature | Without paging | With paging |
|---|---|---|
| Shared system prompt across N requests | N copies of the prefix KV | one set of blocks, N tables point to it, refcount per block |
| Beam search or parallel sampling fork | copy the whole cache per branch | share blocks; copy-on-write only the block that diverges |
| Preemption under memory pressure | evict whole slab, recompute | swap blocks to host memory or drop and recompute; both at block granularity |
The prefix-sharing case matters most in production. A 2,000-token system prompt at 328 KB per token is 656 MB. Shared across 200 concurrent conversations that is 131 GB of duplicate cache under contiguous allocation and 656 MB under paging with refcounts. That is the memory side of Prefix Caching and KV Reuse; the compute side (skipping the prefill) comes for free once the blocks are addressable by content hash.
The costs are real but small. The gather adds indirection to the attention kernel, which is why the first vLLM kernels were slower per token than a contiguous FlashAttention path until FlashAttention 2 and FlashInfer added native paged support. Block size trades internal waste (large blocks) against table size and gather overhead (small blocks); 16 tokens is the common compromise, with 32 and 64 used on some kernels.
Decision: any engine serving variable-length requests should page. The engine's gpu-memory-utilization and its reported KV block count are where you watch this working. The reversal condition: a single-tenant, fixed-length, batch-1 deployment where contiguous storage and a plain FlashAttention kernel are marginally faster and waste nothing.
What interviewers probe next
- "What is the OS analogy exactly?" Virtual pages are logical blocks, physical frames are pool blocks, the page table is the block table, and copy-on-write works the same way when a fork writes into a shared block.
- "How does the engine decide it can admit a request?" It needs free blocks for ceil(prompt tokens ÷ 16) plus at least one block to grow into; vLLM also watermarks a small reserve so decode steps do not immediately starve.
- "What happens when the pool runs dry mid-decode?" The scheduler preempts the lowest-priority sequence, either swapping its blocks to pinned host memory over PCIe or freeing them and recomputing the prefix later; both show as an ITL spike and a preemption counter.
Common mistakes
- Describing PagedAttention as a compression technique; it changes nothing about bytes per token.
- Forgetting that the attention kernel had to change, which is the engineering half of the paper.
- Claiming zero waste; the last block of every sequence is partial.
- Not connecting the block table to prefix sharing, which is the feature interviewers at SGLang-style shops care about most.
Key takeaways
- Contiguous KV allocation reserves max_seq_len per request; at 8k max and 850 used, about 90% is wasted.
- Paging uses 16-token blocks and a per-sequence block table; internal waste falls to under one block per sequence.
- The block table makes prefix sharing, copy-on-write forks and block-level swap cheap.
- Admission needs ceil(prompt ÷ block size) + 1 free blocks; preemption counters reveal an undersized pool.