Page the KV Cache
Map a continuous context onto paged memory
Use a block table to separate logical token positions from physical cache blocks.
A sequence can be logically continuous without occupying contiguous physical blocks.
01Why contiguous allocation is hard to manage
A request’s final output length is usually unknown. Reserving a large contiguous KV region wastes memory, while reallocating as it grows causes copies. Paging divides the cache into fixed-size blocks and stores a logical-to-physical mapping per request. Growth adds a block, and completion releases the blocks. A partially filled final block still wastes space, making block size a tradeoff.
# Framework pseudocode for block-table responsibilities.
def resolve_position(request, token_position):
logical = token_position // block_size
offset = token_position % block_size
return request.block_table[logical], offset
required = ceil_div(computed_positions + planned_tokens, block_size)
new_blocks = pool.reserve(max(0, required - len(request.block_table)))
request.block_table.extend(new_blocks)
# Reservation does not mean these positions were computed.
for block in finished_request.block_table:
pool.release_reference(block)
# Reclaim storage only after the final reference is released.02Address translation applies to both reads and writes
Divide a token position by block size to obtain its logical block and remainder, then consult the block table for the physical block. New K/V writes and historical K/V reads must use the same mapping. Failed allocation must not advance length, and shared blocks cannot be released twice. Real paged attention also requires kernels that consume block tables directly instead of rebuilding contiguous tensors each step.
03Separate block management from model cache layouts
DeepInfer’s block_manager.hpp manages free blocks, reference counts, and allocation constraints; device-side CacheEngine determines tensor layouts. V4 caches also involve model-specific formats and state, so a plain GQA K/V array cannot determine their byte sizes. This excerpt explains address translation only, without implementing upstream paged kernels, concurrency locks, or the full cache lifecycle.
Make it yours
With block size 4 and block table [7,2,9], calculate the addresses of tokens 0, 5, and 10. Explain what must happen before writing token 12.