skip to content

KV Cache and Paged Attention

4 roadmaps6 questions

You will learn how a contiguous KV cache fragments VRAM and how PagedAttention borrows virtual-memory paging to pack many sequences into one GPU, plus what the engine does when it runs out — evict, recompute, or swap. Interviewers probe this because KV-cache capacity, not model weights, is what usually caps your concurrency.

on this pageshow

explore

questions

6

How does a PagedAttention block table let one sequence's KV cache be non-contiguous?

level: middleimportance: must knowfreq 66%

answer

  1. indirection, like an OS page table
  2. fixed-size blocks of a few tokens
  3. logical index maps to physical index
  4. reference counts make sharing possible
  5. identical output, different addressing

basics

~20 s

PagedAttention splits the KV cache into fixed-size blocks, each holding a set number of tokens. Every sequence keeps a block table listing which physical blocks hold its logical positions, and the attention kernel follows that table instead of striding through one range.

solid answer

~50 s

The engine carves the KV region into many equal-sized physical blocks, each storing the keys and values for a fixed token count — vLLM exposes this as `block_size`, typically 16. A sequence no longer owns a range; it owns a *block table*, an array mapping logical block index to physical block index. Blocks are appended one at a time as the sequence decodes, so allocation is incremental and any free block fits any sequence. The attention kernel takes the block table as an argument and gathers keys and values per block, which is what makes the physical scatter invisible to the math — the attention output is identical to a contiguous implementation. Two sequences can point at the same physical block, so identical prefixes are stored once; each block carries a reference count, and a block that must diverge is copied first (copy-on-write). This is the same indirection an OS page table provides for virtual memory.

code

python · 9 lines
python
BLOCK_SIZE = 16
block_table = [412, 7, 1180]   # logical block -> physical block

def locate(token_pos):
    logical, offset = divmod(token_pos, BLOCK_SIZE)
    return block_table[logical], offset

print(locate(20))   # (7, 4): physical block 7, slot 4
print(locate(35))   # (1180, 3)

go deeper

for a junior

Know that the cache is split into fixed-size blocks and each sequence keeps a table saying which blocks are its own, so its memory need not be one continuous piece.

for a middle

Be ready to walk the mapping out loud: logical block index plus offset, resolved through the table to a physical block, with one block appended each time the tail fills.

for a senior

Demonstrate the consequences — reference counting enables prefix sharing and copy-on-write, freeing is bookkeeping with no compaction, and admission becomes a free-block count rather than a reservation.

for a principal

Frame the indirection as the classic virtual-memory tradeoff: a few percent of kernel efficiency bought a multiple in batch size, and that ratio is what makes the cost per served token defensible.

## The mapping The GPU's KV region is pre-carved at startup into N identical physical blocks. One block holds the keys and values for a fixed number of consecutive tokens, for every layer and every KV head — so "block" means a slot in a token dimension, not a slice of the model. vLLM names this knob `block_size` and picks a platform-appropriate default; 16 tokens is the common value on CUDA. A sequence's state is then just a list. Logical block 0 covers its tokens 0–15, logical block 1 covers tokens 16–31, and so on. The block table says where each logical block physically lives — for example logical 0 at physical 412, logical 1 at physical 7, logical 2 at physical 1180. Nothing requires 412, 7 and 1180 to be adjacent, or even close. To find the keys for token 20, the kernel computes logical block 1 and offset 4, reads the table entry, and addresses physical block 7 at offset 4. ## What the kernel actually does The attention computation itself is unchanged: query dotted with all cached keys, softmax, weighted sum of values. What changes is the memory access pattern. A paged attention kernel is written to iterate block by block, loading the block index from the table before each chunk, computing partial attention scores over that block, and combining partial results across blocks with the same online-softmax accumulation flash-style kernels already use. The output is the same mathematics as the contiguous version, modulo floating-point reduction order. Candidates sometimes assume paging is an approximation that trades quality for memory — it is not; it is purely an allocation and addressing change. ## Growth during decode At each decode step, the sequence gains one token. If the current tail block still has room, the new key and value are written into the next slot and nothing is allocated. If the tail block is exactly full, the scheduler pops one block off the free list and appends its index to the block table. So the allocation granularity is one block per block-size tokens, and the only stranded space at any moment is the unfilled remainder of the tail block — bounded by the block size minus one token per sequence rather than by thousands of reserved positions. If the free list is empty when a block is needed, the scheduler cannot grow that sequence, and it must make room by preempting some running request. That is a distinct mechanism from the mapping itself. ## Sharing and copy-on-write Because the table is indirection, two sequences' tables can hold the *same* physical block index. Each physical block carries a reference count. Shared blocks are read-only in practice: as long as the count is above one, no sequence may write into the block. When a sequence needs to append into a block it shares — for example, two samples of the same prompt that have now generated different tokens — the engine allocates a fresh block, copies the shared block's contents into it, points that one sequence's table at the copy, and decrements the original's count. That is copy-on-write, and it is what makes parallel sampling from one prompt cost one copy of the prompt's cache rather than n copies. The same reference counting underpins prefix reuse across *different* requests, which engines expose as automatic prefix caching in vLLM and as `enable_block_reuse` in TensorRT-LLM's KV-cache configuration. ## Freeing When a request finishes, the engine walks its block table and decrements each block's reference count. Blocks that reach zero return to the free list — or, when prefix caching is on, stay in a cache keyed by content hash and are reclaimed later in least-recently-used order if the memory is needed. Freeing is therefore pointer bookkeeping proportional to the block count, with no compaction pass and no copying. ## Costs of the indirection There are real costs. The kernel does an extra dependent load per block, gathers rather than strides, and gets less perfect coalescing than a dense read. There is host-side bookkeeping — a table per sequence, reference counts per block, a free list — that grows with concurrency. In practice these cost single-digit percentages of kernel time while the recovered memory multiplies batch size several-fold, and larger batches are what make bandwidth-bound decode steps efficient. That is why every serious serving engine adopted the design.

  • Does going through a block table change the numbers the attention layer produces?
    No. Paging changes where keys and values are stored and how they are addressed, not what is computed. The kernel accumulates partial attention over blocks and combines them, so the result matches a contiguous implementation up to floating-point reduction order. Treating paged attention as a quality-for-memory tradeoff is a misconception — the tradeoff it makes is kernel efficiency for memory efficiency.
  • What happens when two sequences share a block and one of them needs to write into it?
    Copy-on-write. Shared blocks carry a reference count above one and are effectively read-only, so the engine allocates a new block, copies the shared block's contents, repoints the writing sequence's block table at the copy, and drops the original's reference count. Only the one partially-filled boundary block is duplicated; every full block before it stays shared.
  • How does the scheduler know how many requests it can admit at once?
    It counts free blocks. Total blocks are fixed at startup from the memory left after weights and activations, and each running sequence consumes one block per block-size tokens, rounded up. Admission is therefore a block-availability check rather than a per-request reservation, which is why a paged engine's concurrency tracks actual sequence lengths instead of the advertised maximum context.

A book whose chapters are stored on whatever library shelves were free, with an index card listing where each chapter sits — readers follow the card instead of walking one shelf.

saying these in an interview costs you the question

  • Thinks paging approximates attention or drops distant tokens
  • Believes a block holds one layer rather than a span of tokens
  • Says each sequence still needs its blocks to be adjacent
  • Assumes shared blocks can be written in place by either sequence
  • Confuses the block size with batch size or with maximum context length

context

resolving links…

open as a page

Why does a contiguous per-request KV cache waste most of an LLM server's VRAM?

level: middleimportance: must knowfreq 62%

basics

~20 s

A contiguous allocator must reserve one slab per request sized for the longest output that request could produce. Most requests never grow into it, so the reserved tail sits idle, and the leftover gaps between slabs are too small for the next request to use.

open as a page

When does automatic prefix caching cut TTFT, and when does it silently miss?

level: middleimportance: must knowfreq 58%

basics

~20 s

Prefix caching reuses already-computed KV blocks when a new request starts with the exact same tokens as an earlier one, skipping that part of prefill. It misses whenever the prompt differs at the front, when the shared run is shorter than one block, or when those blocks have already been evicted.

open as a page

What happens to a running request when the KV cache runs out of free blocks?

level: seniorimportance: must knowfreq 52%

basics

~20 s

The scheduler preempts a running sequence: it frees that sequence's blocks and returns it to the waiting queue, either discarding its cache to recompute later or copying it to host memory. The client sees a stall, not an error, and tokens already streamed are never taken back.

open as a page

In a paged KV cache, what does raising the block size gain and cost?

level: seniorimportance: should knowfreq 38%

basics

~20 s

Bigger blocks mean fewer table entries and longer contiguous reads, so kernels and bookkeeping get cheaper. The cost is coarser granularity: more wasted space in each sequence's partly-filled tail block, and prefix sharing that only matches in larger chunks.

open as a page

Between chat turns, should the server keep a session's KV blocks resident or recompute?

level: principalimportance: should knowfreq 34%

basics

~20 s

Pinning blocks through a user's think time blocks capacity for every idle session, so it only pays for short gaps and high-value sessions. The usual answer is neither extreme: free the blocks but leave them in the prefix cache, where they are reused if still present and recomputed if not.

open as a page