Paged KV Cache
Contiguous per-sequence cache allocation wastes most of its memory to internal fragmentation. Store the cache in fixed-size blocks with an indirection table instead.
This entry is a stub. The maths has not been rederived by hand, or the implementation has not been run on real tensors, so it is recorded here as an open question rather than an answer.
Read what follows as a pointer to the sources, not as a settled account.
Reserving a contiguous cache per sequence means reserving for the longest completion the sequence might produce. Most sequences stop far short of it, and the reservation is unusable by anyone else in the meantime — the reported waste runs to 60–80% of allocated cache.
Paging fixes it the way operating systems did: fixed-size blocks, a per-sequence block table, and physical blocks handed out on demand. Sharing follows almost for free, since two sequences with a common prefix can point at the same blocks with a reference count.
This is a stub because the attention kernel that reads through the block table has not been rederived here, and it is the part that decides whether the scheme costs anything at run time.