TL;DR: PagedAttention maps a sequence's logical KV blocks to separate physical blocks, so its cache can grow without reserving one maximum-length slab. The attention kernel reads through the block table. This reduces reservation waste and supports sharing, but partially filled tails, table management and copy-on-write still cost memory or work.
How to approach it
Explain the KV Cache first: attention state retained for consumed tokens. Ask how much state requests actually retain, what length the allocator reserves, and what cache budget remains after weights and runtime memory. Trace one address through a block table, calculate the capacity change, then separate that capacity from measured throughput.
A strong answer
Suppose the allocator, the part of the serving engine that hands out GPU memory for each request's cache, reserves 8,192 positions for every request, while the requests currently retain only 850 each. Much of the reservation is waiting for possible future growth. PagedAttention allows growth in smaller pieces, without relocating an entire cache to find one larger contiguous region.
The PagedAttention paper describes a per-sequence block table that translates logical blocks into physical locations, plus an attention kernel that can read this layout. The operating-system analogy explains the indirection. Here the attention implementation follows the table explicitly; GPU hardware is not transparently paging an ordinary contiguous tensor.
Choose 16 positions per block for this example, not as a universal default. At 850 retained positions, indices run from 0 to 849:
blocks needed = ceil(850 / 16) = 54
last position = 849
logical block = 849 // 16 = 53
slot in block = 849 % 16 = 1
physical block = table[53] # suppose this entry is 11
The kernel reads position 849 from slot 1 of physical block 11. The next fourteen positions fit in the existing tail. Consuming position 864 needs a new block. The table preserves sequence order even if the allocator supplies blocks in an arbitrary physical order.
Now calculate payload capacity. Use Llama 3.1 70B's 80 layers, 8 KV heads and 128 dimensions per head, with an assumed BF16 cache, two bytes per value. These dimensions are available in NVIDIA's published model configuration; its FP8 weight format does not establish our cache precision.
KV bytes per retained position
= 2 (K and V) × 80 layers × 8 heads × 128 dimensions × 2 bytes
= 327,680 bytes = 320 KiB
16-position block = 16 × 320 KiB = 5 MiB
850 retained positions → 54 blocks × 5 MiB = 270 MiB
useful payload = 850 × 320 KiB = 265.625 MiB
tail waste = 14 × 320 KiB = 4.375 MiB
Assume a hypothetical 40 GiB budget already available for this cache payload, after weights and other allocations. No sharing or replication; all requests have 850 retained positions. A distributed layout would need per-device capacity checks too.
| Allocation policy | Per request | Payload-only capacity |
|---|---|---|
| Reserve 8,192 positions | 2.5 GiB | 16 requests |
| Page in 16-position blocks | 270 MiB | 151 requests |
| Page in 256-position blocks | 320 MiB | 128 requests |
The middle row is floor(40 × 1024 / 270) = 151. Sanity check: 151 requests use 40,770 MiB, leaving only 190 MiB. That can buy 38 additional five-MiB blocks, not one for each of the 151 requests. Fitting now does not mean every request can keep growing. These counts exclude metadata and growth headroom and predict no throughput multiplier.
Two compatible sequences can point to the same computed prefix blocks, with reference counts recording that shared ownership. Writing into a shared, partially filled tail needs care. If one generation branch appends a token, first copy the existing tail state into a private block, then update that branch's mapping and write its new state. Pointing it at an empty block would discard the history that attention still needs.
The fork below uses four positions per block to make the write visible. A and B stand for computed state in a compatible shared context. This is a generation fork, not a claim that every engine reuses partial blocks across unrelated requests.
Predict the next allocation: R can consume one more position in block 9. Consuming a fifth position needs another block; its existing block does not move. S can keep reading block 7 throughout. The mapping must become usable only after the required copy and write dependencies are satisfied.
Across separate requests, Prefix Caching and KV Reuse also needs a match for the preceding context and relevant model inputs, resident data, and a reuse policy. vLLM's prefix-cache design describes full-block reuse keyed by prior prefix, block tokens and extra context. Addressable blocks alone do not make prefill free.
I would choose paging for a variable-length service where reservations or duplicated compatible state constrain admission. I would reconsider the added complexity for a fixed-shape workload with little waste or sharing, based on end-to-end measurements. Inspect block availability, growth demand, preemptions and token gaps; more admitted requests can make each stream slower. Block size must also suit the attention backend, so memory rounding is only one part of that choice.
What interviewers probe next
- “Does a smaller block always save memory?” No. At 500 retained positions, both 16- and 256-position blocks round to 512 slots. Smaller blocks can improve rounding across a workload, but this request's payload allocation is identical.
- “Can the scheduler admit whenever a block is free?” It needs enough new blocks for the work being scheduled, considering cache hits, existing tails and planned growth. Sequence and token-work budgets also matter. There is no universal prompt-block-count-plus-one rule.
- “What happens when growth runs out of blocks?” Work may wait or be preempted, with later recomputation or transfer depending on the engine. Investigate its actual policy and latency consequences rather than assuming a particular victim or swap path.
Common mistakes
- Counting only output tokens and omitting retained prompt state.
- Calling paging compression: the 320 KiB per-position payload stays the same.
- Saying copy-on-write changes only a pointer, losing the old partial tail's data.
- Turning 151 versus 16 payload slots into a claimed 9.4× throughput benchmark.
Key takeaways
- With 16-position blocks, position 849 uses logical block 53 and slot 1; the table supplies its physical address.
- The example allocates 270 MiB for 850 retained positions, including 4.375 MiB of tail waste.
- A 40 GiB payload budget fits 151 such allocations, but its remaining space cannot fund one new block for every request.
- Sharing requires compatible state; growth requires capacity; useful throughput requires meeting latency targets.