TL;DR: A sequence only ever has one block that is not full, its last one, so paging wastes at most tokens per sequence: 15 tokens, 4.7 MiB, for Llama 3.3 70B at vLLM's default of 16. Pick the size by trading that waste (which grows linearly with ) against per-block overhead in the attention kernel and the block table, and against prefix-cache granularity, since only full blocks can be shared.
How to approach it
Prove the bound first, because it takes two sentences, then spend the time on the choice. Ask what attention kernel the engine uses (some fix the page size), how many sequences run at once, how long they are, and whether prefix caching matters for this workload. Those four answers decide whether 16 is right or whether 64 is.
A strong answer
A paged allocator hands a sequence a new block only when its current last block is full. Every block before the last is therefore completely filled, and the last holds between 1 and tokens. The unused slots in a sequence are all in that one block:
The expectation assumes final lengths land uniformly within a block, which is close to true for real traffic. There is no external fragmentation either, since blocks are uniform in size and any free block can serve any sequence. Compare the alternative the bound replaced: a contiguous reservation at the maximum length.
Llama 3.3 70B KV per token (BF16) = 2 x 80 x 8 x 128 x 2 B = 327,680 B
pool, 4 x H100 at 0.92, BF16 weights = 431,190 tokens (see the 010 budget)
contiguous, reserve 8,192 per request = 431,190 / 8,192 = 52 requests
paged, mean length 1,500 tokens = 431,190 / (1,500 + 7.5) = 286 requests
sanity: reserved-but-unused share at 1,500 mean = 1 - 1,500 / 8,192 = 82%
That 5.5x is the paging win. The block size question is about what you pay for it.
waste per sequence at 70B, 327,680 B per token
s = 16 : worst 15 tok = 4.69 MiB mean 7.5 tok = 2.34 MiB
s = 128: worst 127 tok = 39.7 MiB mean 63.5 tok = 19.8 MiB
256 running sequences, mean waste: s=16 -> 0.59 GiB, s=128 -> 4.96 GiB
sanity: 256 x 63.5 = 16,256 tokens, about two 8K conversations lost
Waste is the cost of a large block. Small blocks cost elsewhere:
| Block size | Waste, 256 seqs (70B) | Block-table entries at 128K | Prefix match granularity |
|---|---|---|---|
| 16 | 0.59 GiB | 8,192 | 16 tokens |
| 64 | 2.46 GiB | 2,048 | 64 tokens |
| 128 | 4.96 GiB | 1,024 | 128 tokens |
The attention kernel walks the block table and gathers one block at a time. Per layer and KV head, a 16-token BF16 key block with head dimension 128 is 4 KiB, large enough for efficient loads, so 16 costs little in bandwidth. Much smaller blocks turn each fetch into many short, scattered reads and an indirection per few tokens. The scheduler side scales with block count: allocation, freeing and, with prefix caching on, one hash per full block. A 128K-token sequence at 16 tokens per block is 8,192 table entries and 8,192 hashes.
Prefix caching shares only full blocks, because a block's hash covers exactly its tokens plus its parent's hash. A 1,000-token system prompt shares 992 tokens at and 896 at , so 104 tokens are recomputed on every hit at the larger size.
The decision: keep 16 (vLLM v0.31's default, checked October 2026) for mixed chat traffic with many sequences and prefix reuse. The reversal: move to 64 or larger when the kernel requires it (DeepSeek's FlashMLA README specifies 64-token pages for its paged MLA kernel) or when the workload is few, very long sequences, where 128 tokens of tail waste on a 128K sequence is 0.1% and the shorter block table and fewer hashes are worth more.
What interviewers probe next
"Does the bound still hold with beam search or parallel sampling?" Per sequence, yes. Forked sequences share full blocks by reference count and each owns at most one partial tail block, so copy-on-write keeps the waste at one block per branch, not per prompt copy.
"Does vLLM allocate one block across all layers or one per layer?" The block is a logical unit of 16 token positions, and each layer's KV tensor holds its own slice of it: 64 KiB per layer for Llama 70B at TP=1. One block id indexes all of them, so the table is shared across layers.
"Then why not block size 1?" Waste vanishes but the table grows 16x, every hash and allocation happens per token, and the kernel's gathers shrink to 256-byte rows. Some kernels support page size 1 for the flexibility, and they pay for it in indirection.
How it's scored
Weak: says paging "removes fragmentation" without the one-partial-block argument, or cannot name any cost of a small block.
Hire: proves the bound, puts a byte figure on it for a named model, and explains that larger blocks trade waste for fewer table entries and cheaper kernel gathers.
Strong Hire: adds prefix-cache granularity (only full blocks share), quantifies the waste across the running batch rather than per sequence, and names when 16 is wrong: a kernel that fixes the page size, or a few very long sequences.
Common mistakes
- Computing waste per layer and then multiplying by layers again; the 4.7 MiB figure already includes all 80 layers.
- Claiming paging has zero waste. The tail block is real, and at 128-token blocks across 256 sequences it is about 5 GiB.
- Treating the expected waste as . The worst case is , the mean is about half that, and capacity planning uses the mean.
- Forgetting that prefix caching hashes whole blocks, so a larger block also lowers the hit rate on short shared prompts.