advanced27 min studyLesson 706 in Engineering

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

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.

Stotal=∑j=1q(B⌈TjB⌉−Tj),0≤Stotal<qBS_{\rm total}=\sum_{j=1}^{q}\left(B\left\lceil\frac{T_j}{B}\right\rceil-T_j\right),\qquad 0\le S_{\rm total}<qB
For q positive-length unshared requests, integer lengths T_j, and fixed positive integer token capacity B, S_total counts internal unused token slots. The strict bound concerns tail rounding only. Multiply by a specified bytes-per-slot layout to obtain payload slack; metadata and reservations are excluded.↔ Scroll wide equations horizontally.

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.

∑khk≥R⟹̸max⁡khk≥R\sum_k h_k\ge R\quad\not\Longrightarrow\quad\max_k h_k\ge R
h_k are free-hole sizes and R a requested contiguous allocation size, all in the same byte unit. Total free capacity need not contain one fitting hole. This illustrates a contiguous-allocation constraint, not a universal CUDA failure rule: allocator remapping, pool design, and backend behavior can change what is possible.↔ Scroll wide equations horizontally.

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.

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.

  1. 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.

  2. 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.

  3. 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.

The result

A smaller block improves this trace's tail utilization while increasing table count; the best operational choice cannot be determined from slack alone.

Explore the model

Interactive lab

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.

Remainder coverage determines a hypothetical average slackAddition 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. Current readings: Residue r0: 0; Orbit period · m/gcd(m,a): 12; Distinct residues visited: 1 of 12. All parameters are adjustable with the labeled controls below.Repeated addition modulo 12: the current residue is 0, and the orbit period is 12.01234567891011+ 5mod 12An additive orbitn = 0rₙ = 0Period = 12Cycle starts at 0:0 → 5 → 10 → 3 →8 → 1 → 6 → 11 →4 → 9 → 2 → 7 → 0Exact residues · two additions per second
Additive orbitCurrent residue / next edge
Residue r0
0
Orbit period · m/gcd(m,a)
12
Distinct residues visited
1 of 12
t = 0 s

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.

Check your understanding

A worker reports a large gap between allocator-reserved and tensor-allocated bytes. Which conclusion is justified before inspecting allocation state?

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.

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.