PagedAttention & KV-Cache ManagementOpen in Colab
ML project loop
Data·Hypothesis space·Objective·Optimization·Evaluation·Deployment feedback

PagedAttention & KV-Cache Management

The KV-cache (not the model weights), usually decides how many requests a GPU can serve concurrently. A naive allocator reserves one contiguous slab of max_seq_len cache per request the moment it arrives; since real responses are far shorter than the maximum and lengths are unknowable in advance, 60–80% of that memory sits reserved-but-unused. PagedAttention (the algorithm at the core of vLLM) applies the oldest trick in operating systems: break the cache into small fixed-size blocks, map logical positions to physical blocks through a per-sequence block table, and allocate blocks only when tokens actually exist.

Why contiguous allocation fails

Three kinds of waste, mirroring classic memory management:

  • Internal fragmentation: a request allocated 4096 slots that generates 350 tokens wastes 3746 slots for its entire lifetime.
  • External fragmentation: variable-size contiguous slabs leave unusable gaps between allocations; free memory exists but no hole is big enough.
  • No sharing: two requests with an identical 5k-token system prompt each store a full private copy of the same K/V tensors.

The cache is also append-only and per-token — a perfect match for paging, because a sequence only ever grows one token at a time at its tail.

The paged design

Physical HBM is carved into NN blocks of BB tokens each (B=16B = 16 in vLLM). Each sequence holds a block table:

physical address of token t  =  block_table ⁣[⌊t/B⌋]⋅B+(t mod B)\text{physical address of token } t \;=\; \text{block\_table}\!\left[\lfloor t / B \rfloor\right] \cdot B + (t \bmod B)

Allocation procedure:

  1. On admission, allocate ⌈sprompt/B⌉\lceil s_{\text{prompt}} / B \rceil blocks from the free list and prefill into them.
  2. Each decode step appends one token to the last block; only when it fills is one new block popped from the free list.
  3. On completion, all of the sequence's blocks return to the free list (subject to refcounts, below).

Blocks need not be contiguous — the attention kernel gathers K/V through the block table (one extra indirection, a few percent kernel overhead). Waste collapses to at most B−1B - 1 slots per sequence (the unfilled tail of the last block): for B=16B = 16 against a 4096-token reservation, worst-case waste drops from ~90% to under 0.4%.

Watch it run

The allocator on the trace below, block by block — admission, on-demand growth, a shared prefix, and the copy-on-write that keeps it safe:

PagedAttention — block tables, prefix sharing, copy-on-write

1/8

Physical HBM carved into 10 blocks of 4 tokens each, all free. Nothing is reserved in advance — this is the entire departure from the naive allocator, which hands each arriving request one contiguous slab of max_seq_len and hopes.

python
1def admit(seq, prompt, B, free, hashes):
2 table = []
3 for blk in chunks(prompt, B):
4 h = hash(blk)
5 if len(blk) == B and h in hashes:
6 table.append(hashes[h]) # prefix hit
7 refcount[hashes[h]] += 1
8 continue
9 p = free.pop() # fresh block
10 table.append(p)
11 if len(blk) == B:
12 hashes[h] = p
13 return table
14
15def append(seq, token, B, free):
16 if len(seq) % B == 0: # tail is full
17 seq.table.append(free.pop()) # one block
18
19def write(seq, i, B, free):
20 p = seq.table[i // B]
21 if refcount[p] > 1: # shared
22 q = free.pop() # copy-on-write
23 copy(p, q); refcount[p] -= 1
24 seq.table[i // B] = q
state
physical blocks (B = 4 tokens each)
P0free
P1free
P2free
P3free
P4free
P5free
P6free
P7free
P8free
P9free

The KV-cache is append-only and grows one token at a time at the tail — which is exactly the access pattern paging was invented for.

KV-cache allocation the way an OS allocates RAM, on the worked trace above: blocks handed out on demand, a prefix shared between two requests by refcount rather than by copying, and a single block duplicated when one of them finally writes. The last step measures the claim that motivates the whole design — 256 realistic requests allocated both ways, contiguous against paged.

What to notice as you step:

  • Growth is one block, on demand. A decode step that lands in an existing block's spare slot allocates nothing at all; only a full tail block triggers a single pop from the free list. There is never a re-reservation or a copy of the sequence.
  • Only full blocks can be shared. A partially-filled block has no stable content hash (the next token would change it), so prefix sharing operates at block granularity, which is one reason BB is small.
  • Copy-on-write copies exactly one block, not the prefix and not the sequence. That is what makes parallel sampling branches cheap.
  • The final step measures the motivation: 256 requests with a realistic length mix, allocated both ways. Contiguous reservation leaves 72% of the cache reserved-and-untouched; paged allocation reaches 99.4% utilization and 3.5× the concurrent capacity on the same GPU.

Prefix sharing and copy-on-write

Because blocks are content-addressable units, identical prefixes can share physical blocks:

  • Each full block is hashed by (prefix so far → block contents). A new request whose prompt matches an existing hash chain simply points its block table at the existing physical blocks and increments their reference counts — those tokens are never prefilled again. This is prefix caching (the big TTFT lever for RAG workloads).
  • Shared blocks are read-only. If a sequence must write into a block with refcount > 1 (e.g. parallel sampling branches diverging), the allocator performs copy-on-write: copy that one block, decrement the original's refcount, write to the private copy.
  • Freeing decrements refcounts; a block returns to the free list only at refcount 0. Evicted-but-hashed blocks can linger as a cache and be revived on a later hash hit (LRU eviction).

Worked trace

Block size B=4B = 4 (small for readability). Request A arrives with a 10-token prompt, then generates; request B arrives sharing A's first 8 prompt tokens:

Code
physical blocks:   P0      P1      P2       P3      P4
                 [t0–t3] [t4–t7] [t8,t9,·,·]
A block table:     P0      P1      P2               ← 3 blocks, 2 slots slack
                                                       (t8,t9 = A-specific tokens)

B arrives, prompt = A's first 8 tokens + 3 new tokens:
  hash(t0–t3) hit → share P0 (refcount 2)
  hash(t4–t7) hit → share P1 (refcount 2)
  3 new tokens    → allocate P3: [u0,u1,u2,·]
B block table:     P0      P1      P3

B's prefill work: 3 tokens instead of 11 (73% saved).
A generates t10, t11 → P2 fills; next token pops P4. B never sees it.
A finishes → P2,P4 freed; P0,P1 drop to refcount 1 (B still holds them).

Preemption: when blocks run out

Under load the free list can empty while sequences still need to grow. The scheduler must preempt a victim (vLLM picks most-recently-arrived first, so oldest requests finish):

  • Swap: copy the victim's blocks to CPU RAM, restore later. Cost = PCIe transfer both ways; sane for long sequences.
  • Recompute: drop the blocks and re-prefill the victim from its tokens when rescheduled. Counter-intuitively often cheaper for short-to-medium sequences, because prefill is compute-bound and fast while PCIe is slow.

Preemption is why a paged server degrades gracefully under overload (tail latency rises) instead of OOM-crashing.

What it buys, measured

MetricContiguous allocatorPaged (B = 16)
Reserved-but-unused cache60–80%< 4%
Concurrent sequences on fixed HBM1×typically 2–4×
Shared system prompt (k requests)k full copies1 copy + refcounts
Throughput (chat traffic)1×2–4× (more batch slots to fill)

Gotchas

  • Block size trades waste against overhead: smaller BB → less tail slack but bigger block tables and more gather overhead; 16 is the sweet spot vLLM converged on.
  • Sharing requires identical token prefixes — one differing token (a timestamp in the system prompt, a user ID early in the template) breaks the entire hash chain after it. Put volatile content at the end of the prompt.
  • Watch gpu_cache_usage and preemption counters: a high preemption rate silently converts throughput into recompute work; the fix is more replicas, KV quantization, or shorter contexts.

Related concepts

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

RelatedReferenced by
PagedAttention & KV-Cache Managem…Continuous BatchingInference Optimization & …Optimizing LLM InferenceMemory & Performance Opti…