Variable lengths create several different forms of unusable capacity
Quantify fixed-block tail slack and contiguous-hole failures, then separate KV-pool occupancy from framework allocator fragmentation and workload reservation policy.
On this page
The question for today
What you’ll understand
- Calculate total tail slack across heterogeneous request lengths.
- Distinguish internal slack, contiguous-allocation fragmentation, and future-token reservations.
- Evaluate block-size tradeoffs without assuming uniformly distributed length remainders.
Free memory is not always usable memory for the next allocation. A request can leave unused slots inside its last KV block, a general allocator can hold separated holes that do not fit one contiguous object, and a scheduler can reserve space for tokens not yet generated. These effects have different causes and remedies. Name the exact boundary before reporting fragmentation, especially when a fixed device pool remains allocated even as requests finish and its application-level block occupancy falls.
Count internal slack across actual request lengths
In a fixed-token block pool, round each unshared positive request length upward separately. Rounding the sum of all lengths can underestimate capacity because a private tail usually cannot be filled with another request's state. Each request wastes fewer than one block of token slots under this narrow on-demand model, but many short or nearly full-plus-one lengths can make total slack significant. Sharing, speculative reserves, sliding windows, and preallocation change the relevant count, so state which are excluded before applying a simple bound.
The average slack is not automatically half a block. That familiar result requires a suitable distribution of integer length remainders. Workloads with templated prompts, fixed maximum generation lengths, or many boundary-adjacent completions can be strongly nonuniform. Measure actual retained lengths and active-request counts over time rather than only final output lengths. A large fraction of one block can be small in bytes for one model and costly for another, because layer count, KV heads, width, and dtype determine each token slot's physical payload.
External holes and pool slack are not the same problem
A general contiguous allocator can have eight MiB free as holes of three, three, and two MiB yet fail a four-MiB allocation without a way to combine or remap those holes. An equal-size KV pool avoids that particular requirement for contiguous logical request storage: any suitable free block can satisfy the next block request. This does not eliminate fragmentation in the allocator backing the pool, other workspaces, or separate pools with incompatible layouts. An idle block from one cache dtype or layer group may not be interchangeable with a required block from another.
PyTorch 2.9 distinguishes native allocator behavior from its cudaMallocAsync backend, and some tuning options are backend-specific. Its native split-block statistics can help diagnose particular OOM patterns; a large reserved-minus-allocated number alone does not prove fragmentation. The difference can be ordinary reusable cache, pending frees, or incompatible sizes. Inspect allocation histories and pool categories before applying a tuning change. Similarly, reserving maximum output capacity is an admission policy choice, not an allocator defect, even though it can leave substantial device capacity unavailable to other requests.
Choose block size using both byte efficiency and execution costs
Smaller blocks reduce the maximum tail slack but increase table entries and can alter kernel access patterns, copy overhead, and prefix-reuse granularity. Compare total bytes including metadata and measured service latency on representative traces. Keep block count, token slots, and bytes in separate columns so a format change cannot masquerade as a workload improvement. Test long and short requests together: a configuration that looks efficient on a uniform batch can behave differently under arrivals, completions, branches, and cancellation. There is no universal block size that simultaneously minimizes every cost.
The modular lab tests the assumption about remainders. Reset, explicitly set BOTH m=8 and a=3, predict all eight residues in one orbit, then Play or Step; interpreted on paper as length remainders, their slacks average 3.5 slots. Reset and re-set BOTH m=8 and a=4; only residues zero and four occur, averaging two slack slots. Edits retain t; iteration n=min(2000000,floor(2t)). This orbit is not an allocation trace or a workload distribution. It shows why different supported remainder sets need not justify the same half-block expectation.
Work it through
Compare two block sizes on the same three lengths
Three unshared requests retain five, nine, and seventeen tokens. Compare on-demand block sizes eight and four. Assume each block table entry is four bytes and ignore other metadata; token-slot payload is unchanged.
At B=8, counts are ceil(5/8)=1, ceil(9/8)=2, and ceil(17/8)=3. Six blocks provide 48 slots for 31 valid tokens, leaving seventeen slack slots.
At B=4, counts are two, three, and five. Ten blocks provide forty slots and leave nine slack slots, saving eight token slots relative to B=8.
The simplified tables grow from 6×4=24 bytes to 10×4=40 bytes, an extra sixteen bytes. Whether the saved payload and changed access behavior improve service still requires the actual bytes-per-slot layout and measured kernel costs.
A smaller block improves this trace's tail utilization while increasing table count; the best operational choice cannot be determined from slack alone.
The living notebook
Explore the model
Interactive lab · modular
Remainder coverage determines a hypothetical average slack
For EACH run Reset, set BOTH m and a, predict, then Play or Step. At m=8, a=3 has period 8/all residues and paper slack mean 3.5; a=4 has period 2/residues{0,4} and mean 2. Edits retain t; n=min(2000000,floor(2t)). This deterministic orbit does not generate request lengths, allocate GPU memory, or diagnose allocator fragmentation.
- Residue r0
- 0
- Orbit period · m/gcd(m,a)
- 12
- Distinct residues visited
- 1 of 12
Addition modulo m starts at zero: rₙ = na mod m. Playback advances two additions per second. The orbit has period m/gcd(m,a), including period one for a = 0. This is not a cryptographic security test or a primality algorithm. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.
Look forHalf-block average waste is a distributional assumption, not a consequence of ceiling division alone.
Pause & reason
Check your understanding
Your turn
Try it yourself
Two requests have lengths eight and nine with block size eight. Calculate tail slack and compare it with rounding their combined length once. Does the aggregate shortcut always give the correct capacity?
Take a moment to make a prediction or work it out on paper. Open a hint when you need one.
Give me a hint
Private tails are rounded separately rather than packed across requests.
Compare with the solution
Separate allocation uses one plus two blocks, or 24 slots, for seventeen valid tokens: seven slack slots. Rounding seventeen once also yields three blocks here, so the counts coincide accidentally. The shortcut is not general: lengths nine and nine need four separate blocks, while rounding eighteen once gives three; one request cannot normally use the other's private tail.
Keep the idea
Take it with you
- Tail slack, contiguous-hole fragmentation, and future-token reservation are different capacity costs.
- Actual length remainders determine average fixed-block waste.
- Block-size choices require metadata and runtime measurements as well as payload accounting.
Read further
Original sources and deeper explanations to follow at your own pace.
Optional progress, saved in this browser when available. Revisit any lesson at any time.
Lesson not marked complete.