Block tables and KV pages

PagedAttention splits the KV cache into fixed-size blocks, which act like memory pages. Each sequence keeps a block table. The table maps the sequence's token positions to physical blocks in GPU memory. Blocks are allocated only as the sequence grows, and they do not have to sit next to each other.

The big idea

An operating system gives each program a neat, continuous address space. Behind the scenes, it maps each page to a physical frame, and those frames can be anywhere in RAM. PagedAttention does the same for KV:

The picture breaks in one place. A CPU page table lookup happens in hardware. Here the attention kernel does the lookup in software, so the kernel has to be written for it.

Walking through a growing sequence

Take a block size of 16 tokens. The block IDs below are made up for illustration.

Prompt of 40 tokens         -> 3 blocks (16 + 16 + 8)
Block table                 -> [7, 2, 9]
Generate tokens 41 to 48    -> fill block 9 up to position 48
Token 49                    -> last block is full: take block 31 from the free pool
Block table                 -> [7, 2, 9, 31]

Old blocks never move. Growth only appends a new table entry. The most a sequence can waste is the empty tail of its last block, at most 15 slots here.

Why this helps throughput

Continuous batching only helps if the scheduler can admit a new request when a slot frees up. With paged blocks, freed memory is usable in any size the scheduler needs.

Here is the capacity sketch, with about 250 KB of KV per token (illustrative):

Free KV memory: 40 GB
Contiguous reservation at max 8,192 tokens: 8,192 × 250 KB = about 2 GB per request
  -> about 20 concurrent requests, even if each uses only 500 tokens
Paged blocks, 50 requests at 500 tokens each:
  50 × 500 × 250 KB = 6.25 GB
  -> plenty of room for bursts and longer tails

Choosing the block size

Typical block sizes are 16 or 32 tokens. Smaller blocks waste less at the tail. They also make bigger block tables and more kernel indirection. Larger blocks do the opposite. Engine defaults are chosen for this trade-off, so change them only with a benchmark.

Common mistakes

• Shrinking blocks to save tail space. Tiny blocks add table lookups and kernel overhead.
• Confusing this with activation checkpointing. Checkpointing recomputes activations during training. Paging manages KV memory across tokens during inference.
• Reading the block table as a length limit. It only tracks what is allocated. Length limits are a separate setting.

Check yourself

1. With 16-token blocks, what is the most KV space one sequence can waste in its last block? Answer: 15 token slots, because the last block can be one position short of full.
2. When a sequence grows, why does the engine not move its existing KV? Answer: the block table just gains a new entry that points to a free block. The old blocks stay put.

Key takeaways

• A block table maps a sequence's token positions to fixed-size physical blocks.
• Blocks are allocated on demand, so waste is limited to the last block of each sequence.
• Paging makes free memory usable, which lets continuous batching admit more requests.
• The attention kernel has to follow the block table, which is why engines provide the kernels.

Further learning

Next, read copy-on-write sharing to see how blocks are shared between sequences. The MLSys seminar talk by the PagedAttention authors walks through the design.