PagedAttention Block Allocation (as used in vLLM)

The problem, from first principles

Naively, each sequence's KV cache is pre-allocated as one contiguous buffer sized for the maximum sequence length, wasting huge amounts of memory whenever actual generations are shorter than the max — extremely common. PagedAttention (as used in vLLM) borrows the operating-system idea of paged virtual memory: the KV cache is divided into fixed-size physical blocks, and each sequence gets a logical-to-physical block table it appends to as it grows, allocating new physical blocks on demand and freeing them when the sequence finishes.

From theory to code

n_blocks_needed = ceil(L / block_size)     -- L = sequence length so far
used_bytes = (sum of allocated_blocks over live sequences) * bytes_per_block

Constraints

• Process a list of events in order: ('append', seq_id) adds one token to that sequence (allocating a new block only if the current last block is full or the sequence has none yet), and ('free', seq_id) releases all of that sequence's blocks back to the free pool.
• Report an out-of-memory condition if an append needs a new block but none are free — stop processing further events at that point.
• Return, after processing all events: each live sequence's logical block table (ordered list of physical block ids) and the number of free blocks remaining.

Hints