What are uncertainty-calibrated output-length bounds?

They are per-request ceilings on how many tokens a model will emit, produced by taking a raw length prediction and calibrating it *toward* a chosen coverage target — the true length is meant to land at or below the ceiling, say, 9 times in 10. The scheduler gets a number it can plan against plus a target rate for how often that number is exceeded, rather than a guarantee.

Why not just predict the output length directly?

Because the cost of being wrong is asymmetric. Over-predicting means a decode instance is packed a little loosely; under-predicting means a long request lands where a short one was promised capacity, which rebuilds the head-of-line blocking the prediction was meant to remove. A point estimate carries no commitment about which side it errs on, so nothing stops it walking into the expensive one; a calibrated bound is built to err in the cheap direction at a rate you choose.

How does this relate to prefill-decode disaggregation?

Disaggregation is what makes the problem acute. Once decode runs on its own memory-bound pool, those machines receive requests they never prefilled and hold each one's KV cache until the last token, so placement depends entirely on a duration nobody measured. MAPS supplies that missing duration as a bound. [More on the split](/ai-explained/amd-atom-prefill-decode-disaggregation)

Is this the same as speculative decoding?

No — only the word speculative is shared. Speculative decoding guesses the token values a draft model would produce and verifies them in a batch, to make one request faster. MAPS speculatively predicts how many tokens a response will contain, to decide where and in what order requests should run. One targets a single request's speed, the other targets contention between requests.

How much does it actually improve latency?

The paper reports a 42.6% reduction in average end-to-end latency and up to an 84.8% reduction in tail latency, measured across two real-world workloads and two LLMs against three existing systems. The paper does not explain the gap between the two figures, but it is the shape you would expect: head-of-line blocking damages a few requests severely rather than all requests slightly, so easing it shows up in the far percentiles far more than in the mean.

LLM· 2026-09-15

MAPS cuts LLM tail latency up to 84.8% — Uncertainty-calibrated output-length bounds — What does it mean?

TL;DR

What is it: MAPS is a scheduling framework for disaggregated LLM serving, published in a September 2026 arXiv paper and built on uncertainty-calibrated output-length bounds — a per-request ceiling on how many tokens the model will emit, computed before decoding starts.
Why it’s needed: A decode instance holds a request's KV cache until its last token is emitted, so admitting work without knowing how long it runs is what produces queue buildup between decoders and head-of-line blocking inside one — the paper reports 42.6% lower average end-to-end latency and up to 84.8% lower tail latency once the scheduler is given a length signal it can trust.
vs previous: Length-aware schedulers usually hand the scheduler a point estimate of output length, which says nothing about which direction it is wrong in, and an under-estimate quietly rebuilds the overload the prediction was bought to prevent; MAPS instead derives an upper bound with a target coverage rate — a prediction with a chosen error direction and a chosen error rate.

Jargon

Prefill and decode: The two phases of serving a request. Prefill reads the whole prompt in one compute-heavy pass; decode then emits one token at a time, each pass re-reading the cache. Walk the split
KV cache: The stored keys and values for every token seen so far, kept so decode does not recompute the prompt on each step. It grows with every token emitted, so a long request is a long-lived memory reservation. See the memory cost
Prefill-decode disaggregation: Running prefill and decode on separate pools of machines so a compute-heavy prefill cannot stall a memory-bound decode. Full explainer
Head-of-line blocking: Work at the front of a queue holding up everything behind it that could otherwise have run. In serving it is the short request stuck behind a long one purely because of arrival order, not because the system is out of capacity — which is how a well-utilised server still ends up with a terrible tail.
Tail latency: The slow end of the latency distribution, usually quoted as P95 or P99 — the experience of the unluckiest 1 in 20 or 1 in 100 requests, not the typical one. Why the tail is the product
Coverage (in calibration): The fraction of requests whose true value actually falls at or below a predicted bound. Calibration targets a chosen fraction rather than guaranteeing it — a 90% bound is built to be exceeded about 1 time in 10, and that rate can drift when the workload moves away from what it was calibrated on.
SLO (service level objective): The latency target a service commits to, almost always written against a percentile — "P99 under two seconds" — rather than an average, because an average hides the requests users actually complain about. How an SLO shapes the system
Speculative output-length prediction: Guessing the response length ahead of time so the schedule can use it. Despite the shared word it is unrelated to speculative decoding, which guesses the token values to go faster.

The news. On 14 September 2026 a paper titled MAPS: Memory-Aware Predictive Scheduling Framework for Large Language Model Serving was posted to arXiv. It targets a gap that opens up once you split prefill and decode onto separate machines: the decode pool is memory-bound, and output lengths are unknown when requests arrive, so decoders drift into persistent load imbalance. MAPS predicts each request's length with help from the user's device, overlapped with cloud-side prefill; calibrates that into an upper bound with target coverage; and feeds the bound to a hierarchical global-local scheduler. Measured on two real-world workloads and two LLMs against three existing systems, it reports 42.6% lower average latency and up to 84.8% lower tail latency. Read the paper →

The host's problem is not that the restaurant is full. It is that every party is an open-ended reservation. A table is handed over the moment someone sits down, and it comes back at an hour nobody wrote on the booking sheet. Seat a two-hour party at the only table the 8 o'clock booking could have used and the room is still half empty while a line forms at the door.

A decode instance is that table. Once a request lands on it, the instance carries that request's KV cache until the last token is emitted, and the cache grows with every one of those tokens — so the question "how much of this machine is spoken for?" cannot be answered without knowing the output length. That length is the one number the system does not have. The prompt is right there and can be measured exactly; the response has not been written yet. This is what the MAPS authors mean by memory-bound decoders suffering persistent load imbalance: it is not a transient burst, it is the scheduler structurally flying blind, request after request.

Prefill-decode disaggregation makes this sharper rather than softer. Splitting the phases fixes the interference between a compute-heavy prefill and a memory-bound decode, but it also means the decode pool now receives requests it never prefilled, carrying little beyond "here is a KV cache, finish it." The scheduler that places those requests — the component the inference engine builds its whole loop around — is choosing which table to fill with no idea how long anyone is staying.

So ask the party in the car. That is the first of the paper's three moves, and the clever part is when it happens rather than that it happens. MAPS runs the length prediction with the user's own device assisting, overlapped with cloud-side prefill, which is why it can claim what the abstract calls negligible latency overhead: prefill is busy work the cloud has to do anyway, so the guess is timed to land before the decoder needs it. The prediction is close to free because it hides inside a phase that was already running — negligible, in the abstract's own word, rather than nothing.

The second move is the one worth taking away, because it generalises far past this paper. A predictor that hands the scheduler a single number — this will be about 480 tokens — is silent about which direction it is wrong in, and the two directions of error do not cost the same. Guess too high and you under-pack a machine; you lose a little throughput. Guess too low and you seat a marathon party at the table you promised to someone else, which is precisely the head-of-line blocking the prediction was bought to prevent. An estimate tuned to be right on average is the wrong instrument for an asymmetric loss.

MAPS therefore applies uncertainty-aware calibration to turn the raw estimate into an output-length upper bound with target coverage — a ceiling the true length is designed to stay under a chosen fraction of the time, say 9 times in 10. The host does not announce when the party will leave. The host writes back by 9:15 on the sheet and is rarely embarrassed. That is what the abstract means by enabling safe scheduling decisions: not that the bound is never exceeded, but that being exceeded is a budgeted outcome with a target rate, not an accident. The third move, a hierarchical global-local scheduler, is what consumes it — the global level choosing which decoder a request goes to, the local level working inside a single decoder, which is where the abstract puts inter-decoder queue buildup and intra-decoder head-of-line blocking respectively.

Scheduling signal	What the scheduler knows	How it fails
None (arrival order)	Nothing beyond the queue position	Long and short requests are interleaved blindly; the tail is whatever luck deals
Prompt length as a proxy	How big the input was	Input size barely constrains output size — a one-line prompt can request an essay
Point estimate of output length	A single predicted number per request	Under-predictions land on the expensive side of an asymmetric loss and rebuild the blocking
Calibrated upper bound (MAPS)	A ceiling plus the target rate at which that ceiling may be exceeded	Bounds set too loosely under-pack the machine, trading throughput for a safer tail
Oracle (true length)	Everything, but only in a replay	Not obtainable online — it is an upper limit for measuring the others against, not a system

What the bound actually buys you

Hold three things fixed (illustrative — the paper publishes no such breakdown): two decode instances, each running one request at a time at 50 tokens per second, and four requests arriving together — one long request A at 3,000 tokens (60 s of decode) and three short ones B, C and D at 200 tokens each (4 s of decode).

A scheduler with no length signal cannot tell the four apart, so it round-robins by arrival order: A then C onto decoder 1, B then D onto decoder 2. Decoder 1 finishes A at 60 s and only then starts C, which completes at 64 s. Decoder 2 finishes B at 4 s and D at 8 s. Average completion is (60 + 4 + 64 + 8) / 4 = 34 s, and C — four seconds of actual work — spent 60 of its 64 seconds waiting, finishing at 16× its own service time.

Now give the scheduler a length signal it trusts: A's bound comes back near 3,000, the other three near 250. It isolates A on decoder 1 and packs B, C and D onto decoder 2, which runs them back to back at 4, 8 and 12 s. Average completion is (60 + 4 + 8 + 12) / 4 = 21 s, and C now finishes at 8 s instead of 64. Same hardware, same requests, same total work done; the only thing that changed is that the scheduler knew which party was staying.

Be precise about what that shows, though. So far it is the value of telling lengths apart at all — an accurate point estimate would have produced exactly the same placement. Calibration earns its keep one level down, in what happens when the signal is wrong. Give the scheduler a rule — isolate anything predicted longer than 500 tokens, pack the rest — and the two directions of error stop behaving alike. Return 400 for A and A is no longer isolated, so C goes back behind it and lands at 64 s again: the whole gain is gone. Over-predict instead and the scheduler holds room it turns out not to need — it packs the fleet more loosely and gives up some throughput, but nobody is left waiting behind a marathon. A bound does not make the predictor more accurate; it decides which way the inaccuracy that is left leans.

violations: 2.6%

TTFT distribution (synthetic) · p50 257ms · p90 670ms · p99 1179ms · the same shape, three different SLO targets — watch the red cohort grow as you tighten the line.

This is also why the paper's two headline numbers differ so much. Average end-to-end latency falls 42.6%, which is respectable; tail latency falls by up to 84.8%, which is the real result. The paper does not break that gap down, but the shape is what queueing behaviour would predict: head-of-line blocking is a tail pathology by construction — it does not slow every request a little, it destroys a few of them completely — so easing it moves the far percentiles much more than it moves the mean. If your SLO is written against a percentile rather than an average, which is the normal case, that gap is the whole point of the work.

Two honest limits. The prediction path is device-assisted, and read plainly that suits the on-device application workload the paper opens with — a server-only deployment with no client model to lean on would have to find the prediction budget somewhere else. And a coverage target is a dial, not a constant: tighten it and the bounds grow, the machines pack more loosely, and throughput is what you spend to buy the tail back. The contribution is not a free lunch — it is a knob whose units the scheduler can finally reason about.

Goes deeper in: LLM Serving → The Inference Engine → The Scheduler

Related explainers

AMD ATOM + ATOMesh — Prefill/decode disaggregation on ROCm — the split that creates the blind decode pool MAPS is scheduling
Spec-decode latency paper — Load-dependent latency model — why serving latency is a function of load, not a constant per request
ELDR routes MoE decode by expert locality — a different signal for the same decision: which decoder should take this request

Frequently Asked Questions

Check what you knowMap your AI & GPU knowledge across every track — free, role-based