Contiguous reservation
Allocate logical token blocks to physical KV-cache blocks and quantify internal waste and shared-prefix behavior.
THE IDEA
The problem with reserving the maximum
The simplest way to store a sequence's KV cache is a single contiguous region sized for the longest the sequence could get. But most sequences are shorter than that and they grow slowly. The unused part of each region is reserved but empty, and under a reservation scheme it stays exclusive to its sequence: no other request can use it.
Under a reservation scheme the idle part stays exclusive to its sequence, so another request cannot use it even if it needs memory right now.
Predict first. Does unused reserved capacity automatically become usable by another sequence?
Chapter context
Contiguous reservation can waste memory when sequence lengths differ or grow unpredictably. Paging separates a sequence's logical block order from the physical blocks storing its cache.
TRY IT YOURSELF
Part 1. Do it hands-on
Count reserved and wasted slots, then compare with a paged allocation in code.
Under a reservation scheme the idle part stays exclusive to its sequence, so another request cannot use it even if it needs memory right now.
- To do: A server reserves a contiguous region of 100 token slots per sequence, whatever its real length. Three sequences are running with 20, 35 and 10 tokens so far. Slots reserved?
- To do: Slots reserved but not (yet) holding a token?
- To do: The pool has 400 slots in total. How many MORE 100-slot reservations can be made while those three are running?
Part 2. Do it in code
- reserved_slots(n_seq, max_len): slots reserved when every sequence gets a contiguous max_len region.
- used_slots(lengths): tokens actually present (the sum of lengths). ValueError if any length exceeds max_len when max_len is given as a second argument.
- waste_fraction(lengths, max_len): the share of reserved slots that hold no token.
- extra_reservations(pool, max_len, n_running): how many more full reservations fit in the pool.
- paged_slots(lengths, block): the slots a paged allocator would hand out for the same sequences (each rounded up to whole blocks).
Stuck, or something not working? You can come back to it any time.
CHECK YOUR UNDERSTANDING
Does unused reserved capacity automatically become usable by another sequence?
Chapter reference: math, worked example & code
This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.
Math and notation
For length T and block capacity P:
Slack as a fraction of allocated slots is slack/slots. State the denominator when reporting waste percentages.
Worked example
A sequence has 33 tokens and blocks hold 16. It requires ceil(33/16)=3 blocks, allocating 48 token slots. Fifteen slots are unused, so internal slack is 15/48=31.25% of this allocation. It is not 31.25% of all GPU memory, and shared blocks change total ownership accounting.
Reference code
The following example uses the Python standard library and does not call a remote service.
from math import ceil,isclose
tokens,capacity=33,16
blocks=ceil(tokens/capacity)
slots=blocks*capacity
assert blocks == 3 and slots == 48
assert slots-tokens == 15
assert isclose((slots-tokens)/slots,.3125)
Python examples are provided for study and local execution; this page does not execute Python.
Common mistakes
Paging improves allocation flexibility but does not make memory unlimited. Logical block order differs from physical layout. Internal slack and external fragmentation are different kinds of waste.