Admission reserves future obligations instead of trusting an average output length
Separate live physical blocks from unmaterialized promises, account for sharing and speculative state, and release canceled work only at safe lifetime boundaries.
On this page
The question for today
What you’ll understand
- Maintain a nonoverlapping block-pool admission invariant.
- Distinguish forecasted generation length from a bounded resource commitment.
- Track materialization, rollback, cancellation, and asynchronous reclamation without double-counting capacity.
An inference request can fit now and still exhaust the pool when its next tokens arrive. Admission therefore needs a policy for future growth, concurrent prompts, speculative branches, and workspace peaks. A prediction can improve utilization, but it is not a bound unless a hard limit or recovery mechanism enforces the assumption. State the resource being protected and keep committed blocks, promised future blocks, and safety margin separate so the scheduler cannot accidentally sell the same capacity to several requests.
Define one resource ledger with nonoverlapping categories
For a fixed KV pool, count unique blocks that cannot currently be reclaimed, additional blocks promised but not yet materialized, and an explicit safety margin. Shared physical prefixes belong in the committed count once; each consumer's private future growth still needs its own accounting. Idle evictable cache contents can supply capacity only after their identities are safely removed and pending access is resolved. Do not add a request's full future maximum on top of blocks already counted as committed, and do not treat a logical reference as another complete physical allocation.
A pool invariant protects only that pool. Device workspace, graph capture, communication buffers, restoration staging, and allocations outside the framework need separate simultaneous bounds or margins at the device boundary. Even a mathematically correct KV ledger can coexist with a CUDA allocation failure elsewhere. The original PagedAttention design and the cited vLLM manager illustrate admission decisions based on available blocks, while the CUDA and allocator contracts explain why successful slot accounting is not the entire memory-safety argument. Make those boundaries visible in telemetry and incident reports.
Predictions need an explicit exceedance policy
A request with a known hard maximum can reserve a conservative upper bound on new blocks, subject to model context limits and the exact generation contract. A mean or percentile forecast can instead support a statistical admission policy, but the system must define what happens when the forecast is exceeded: pause, preempt, recompute, offload, reject further growth, or otherwise enforce a limit. A ninety-ninth percentile does not mean no request exceeds it, particularly across many concurrent requests or shifted workloads. Measure calibration and exceedance behavior separately from average throughput.
For an unshared sequence without speculative state or copy-on-write, ceiling differences count future block growth under a specified token bound. Shared tails can require additional private copies, and speculative proposals may temporarily occupy state beyond accepted tokens. Reserve those separately rather than pretending every proposed token is already a permanent committed continuation. Multi-rank execution must make compatible admission decisions where distributed work requires it; free capacity on one rank cannot compensate for an exhausted required peer. A rollback policy must preserve the accepted prefix and safe kernel lifetimes while removing abandoned state.
Move obligations through materialization and cleanup exactly once
When a promised block becomes live, transfer its count from the unmaterialized ledger to the committed ledger instead of increasing both. When a request ends, release unused promises once no further launches can consume them. Its physical blocks remain protected until all asynchronous kernels and copies complete, and shared blocks remain protected for other owners. Cancellation and timeout can arrive during allocation, prefix lookup, copy-on-write, transfer, or speculative verification, so test each transition for double release and leaked obligations. A user-visible canceled status is not itself a device-completion event.
The probability lab illustrates why forecasts are not hard bounds. Reset, explicitly set BOTH individual exceedance probability p=0.05 and n=20, predict at least one exceedance with probability about 0.6415, then Play or Step. Reset and re-set BOTH p=0.1 and n=20; predict about 0.8784. Edits retain t; playback highlights exact independent counts. The toy has no block ledger, length model, correlated requests, or recovery mechanism. Its assumed p is not measured by the slider, and a real workload's dependence can change the aggregate risk.
Work it through
Preserve the ledger through materialization and cancellation
A forty-block pool has A=18 unreclaimable blocks, R=10 additional promises, and S=4 safety blocks. A proposed request needs five additional promised blocks. After admission, three promised blocks materialize. Later a canceled request owns two private committed blocks and four unmaterialized promises.
Initial accounted use is 18+10+4=32, leaving eight blocks for new promises. Five fit: R becomes fifteen and accounted use becomes 18+15+4=37.
When three promised blocks materialize, A becomes twenty-one and R becomes twelve. The sum stays 21+12+4=37; the same capacity has not been counted twice.
After cancellation prevents further launches, remove its four unused promises, giving R=8. Keep its two private blocks in A until outstanding accesses finish; then A falls to nineteen and accounted use becomes 19+8+4=31.
The reservation ledger changes at explicit ownership boundaries, preserving both capacity accounting and safe asynchronous lifetimes.
The living notebook
Explore the model
Interactive lab · probability
Per-request forecast misses accumulate across concurrent opportunities
For EACH run Reset, set BOTH p and n, predict, then Play or Step. At n=20, hypothetical exceedance p=0.05 gives P(K≥1)≈0.6415; p=0.1 gives≈0.8784. Edits retain t. This exact iid count model does not implement predictions, pool admission, cancellation, reservations, or recovery.
- Mean · np
- 5
- Variance · np(1−p)
- 2.5
- Total probability
- 1
These are exact binomial probabilities for independent trials with one fixed success probability. Playback tours the distribution; it does not resample outcomes. 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 forA forecasted length needs an exceedance policy; a small assumed tail probability is not a deterministic memory bound.
Pause & reason
Check your understanding
Your turn
Try it yourself
An unshared request has seventeen retained tokens in eight-token blocks and an enforced maximum of ten additional retained tokens. Calculate new blocks required. If the request instead shares a writable partial tail, what extra issue must the ledger consider?
Take a moment to make a prediction or work it out on paper. Open a hint when you need one.
Give me a hint
Compare ceiling counts at lengths seventeen and twenty-seven; then consider private write ownership.
Compare with the solution
Current count is ceil(17/8)=3 and bounded final count is ceil(27/8)=4, so one new growth block is required in the stated unshared case. A shared writable tail may additionally require copy-on-write capacity and safe copy completion; the simple ceiling difference does not include that obligation.
Keep the idea
Take it with you
- A correct admission invariant uses nonoverlapping committed, promised, and safety categories.
- Predicted generation lengths need an explicit exceedance policy rather than being called bounds.
- Materialization, rollback, and cancellation must preserve ownership until asynchronous access is finished.
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.