Skip to content
AI360XpertBeta

Paged Attention

Your GPU saves every past token's keys and values so it never recomputes them, and that store grows with each token you generate. Paged attention chops the store into small fixed blocks tracked by a table, so memory fills slot by slot and almost none of it sits empty.

Paged attention stores 10 tokens in 3 fixed blocks mapped through a block table, so only 2 slots sit empty instead of 6
Paged attention stores 10 tokens in 3 fixed blocks mapped through a block table, so only 2 slots sit empty instead of 6

Why Does This Exist?

Serving a model is usually a memory contest, not a math contest. The KV cache is why: every token you generate appends one fresh key vector and one fresh value vector per layer and head, and every later token reuses them instead of recomputing the past. That cache is the best deal in serving, until you ask where it lives.

The quick refresher, since everything below assumes it: during decoding the model keeps all past keys and values around, so each step computes a single new pair and looks up the rest. Memory therefore grows with sequence length, one slice per token. The full story of what the cache stores and why it works lives on the KV cache page.

The old answer for placement was one long contiguous slab per sequence, sized for the longest reply you allow. Most replies come up short, so the tail of the slab sits reserved but empty. Worse, growing slabs mid-generation scatters free memory into gaps that no new slab fits into, and the server starts refusing requests it had the math to handle.

This page is about the fix for the placement, not the cache itself. You will page the cache into small blocks, map them with a table, and count exactly how much waste survives.

Think of It Like This

Tables, not benches

A restaurant seats parties on long fixed benches. A party of two arrives and warns that eight more friends might show up, so the host ropes off a ten-seat bench. Two friends come. Eight seats sit roped off all night while new guests pile up at the door. That is contiguous allocation: reserved for the maximum, wasted on the average.

Paged attention runs the room on small four-top tables plus a host's map. The party of two gets one table. When three friends arrive, they get a second table wherever one happens to be free, and the map records that this party sits at tables 2 and 0. Nobody waits for a ten-seat stretch to open up, because no party needs its tables to sit together.

The map is where the analogy stops. A host glances at it once; your GPU consults the block table on every single decoding step, inside a custom kernel, and each lookup costs a little time. Paging buys you throughput, not a free lunch.

How It Actually Works

The attention math does not change one bit: each query still scores every past key, the weights still sum to 1, and the output is still the weighted blend of values. Paging changes where those keys and values live.

Blocks and the block table

Pick a fixed block size BB, measured in tokens per block. Sixteen is the usual pick and the default in vLLM, the serving engine that introduced the technique.

Now number each sequence's blocks twice. A logical block is the block's position in the sequence: logical block j=0j = 0 holds the first BB tokens, block j=1j = 1 holds the next BB, and so on. A physical block is an actual slab of GPU memory, sitting wherever it fit. The block table TT is the map between them: T[j]T[j] is the physical block currently holding logical block jj.

A prompt of NN tokens needs ⌈N/B⌉\lceil N / B \rceil blocks up front (the ceiling brackets mean round up). Each new token drops into the current block. When that block fills, the allocator grabs one fresh physical block from anywhere and appends it to the table. Memory grows one block at a time, exactly when needed, and two sequences sharing a prefix simply point their tables at the same physical blocks instead of storing them twice. That sharing is the whole trick behind prefix caching.

What one decoding step reads

Call the new token's query vector qq: its question about the past. Call the stored keys KK and values VV. The PagedAttention kernel walks the block table, gathers each block's keys from wherever they physically sit, scores qq against all of them, normalises the scores into weights aia_i with ∑iai=1\sum_i a_i = 1, and blends VV with those weights. Same weighted average as always. The only new work is the address translation, one table lookup per block.

Worked example: 10 tokens in blocks of 4

Take N=10N = 10 tokens with B=4B = 4, the fixture drawn above. Logical blocks: ⌈10/4⌉=3\lceil 10 / 4 \rceil = 3, named L0, L1, L2. Slots: 3×4=123 \times 4 = 12. Empty: 12−10=212 - 10 = 2. The table reads L0 to P2, L1 to P0, L2 to P4, so the three blocks land scattered across physical memory with two empty slots left in P4.

Now weigh it in bytes. One sequence's KV cache costs:

M=2⋅L⋅H⋅d⋅N⋅bM = 2 \cdot L \cdot H \cdot d \cdot N \cdot b

In plain words: MM is total bytes; the leading 2 counts keys plus values; LL is the number of layers; HH is the number of KV heads per layer; dd is the numbers stored per head; NN is the token count; bb is the bytes per number. Take a toy model with L=2L = 2, H=2H = 2, d=8d = 8, and b=2b = 2 bytes for half precision. One token costs 2⋅2⋅2⋅8⋅2=1282 \cdot 2 \cdot 2 \cdot 8 \cdot 2 = 128 bytes. Ten tokens use 1,2801{,}280 bytes. The 2 paged slots wasted cost 2⋅128=2562 \cdot 128 = 256 bytes.

Compare with reserving a 16-slot contiguous buffer for the same 10 tokens: 16−10=616 - 10 = 6 slots wasted, costing 6⋅128=7686 \cdot 128 = 768 bytes. Paging wastes one third as much here, and the gap widens as the reserved maximum grows, because paged waste can never exceed B−1B - 1 slots while reserved waste grows with the maximum length you feared.

The price is the lookup per block, which sets the trade-off. Shrink BB and waste shrinks but lookups multiply; grow BB and lookups shrink but the last block's empty tail grows. That is why blocks stay small, around 16 tokens, and why you skip paging entirely when serving one short request on an empty card: with nothing to pack, the table is pure overhead.

Code

This snippet models the only two ideas that matter: the table that turns logical blocks into physical addresses, and the waste arithmetic from the worked example.

def blocks_needed(tokens: int, block: int) -> int:    return (tokens + block - 1) // block  # ceil(tokens / block)

def waste_slots(tokens: int, block: int, reserved: int) -> tuple[int, int]:    paged = blocks_needed(tokens, block) * block - tokens    naive = reserved - tokens    return paged, naive

table: dict[int, int] = {0: 2, 1: 0, 2: 4}  # logical block -> physical blockprint(table[1])  # -> 0print(blocks_needed(10, 4))  # -> 3print(waste_slots(10, 4, 16))  # -> (2, 6)

Logical block 1 lives in physical block 0. Ten tokens at four per block need 3 blocks. And the waste check agrees with the hand computation: 2 slots paged against 6 reserved.

Watch Out For

Judging it by single-request speed

Serve one prompt and time it: latency looks identical, sometimes a hair worse, and paging looks pointless. That benchmark measures the wrong thing. The table lookup is real overhead, and a lone request has no packing problem to solve, so nothing pays for it.

The win is throughput under load. Freed memory turns into bigger batches and shared prefix blocks, and tokens per second across concurrent requests is the number that moves. If you evaluate paging, load the server with parallel requests first, then compare.

Writing to a block two sequences share

Sharing is safe only while everybody reads. Say two requests point at physical block P7 through their own tables, and request A appends a token that lands in P7. Request B's history just changed under it. The symptom is unmistakable once you know it: beams in a search collapse into identical text, or a second request returns continuations that belong to the first.

The fix is reference counting plus copy-on-write: track how many tables point at each block, and duplicate a shared block before letting anyone write to it. Read together, copy before writing.

The Quick Version

  • Paged attention stores the KV cache in fixed-size blocks and finds them through a per-sequence block table, so no sequence needs one long contiguous slab.
  • Ten tokens in blocks of four use 3 blocks and waste 2 slots; a reserved 16-slot buffer wastes 6.
  • The attention math is unchanged: one query, weights over all past keys summing to 1, blended values. Only the addresses are indirect.
  • Freed memory goes to bigger batches and shared prefix blocks, which is where the throughput win comes from.
  • Small blocks waste less but cost more lookups, and 16 tokens per block is the usual balance. Skip paging for one short request on an empty card.
  • Shared blocks are read-only until copied: write to a shared block and you corrupt every sequence pointing at it.