Past-Future Scheduler for LLM Serving under SLA Guarantees

A language model server must decide whether to admit a waiting request without knowing how much memory it will eventually need, because nobody knows how long the answer will be until it is written; existing systems either assume the worst and leave most of the GPU idle, or assume the best and later have to throw a half-finished request out — and the Past-Future scheduler (Beihang, SenseTime, Peking) instead samples each length from the distribution of requests that finished recently, and computes not the total memory but the peak across every future moment a request might complete.

Why this problem is worth solving

The memory a request occupies grows as it is answered, which is what makes admission a gamble.

Throughput is not the metric; throughput that met its deadlines is.

What people did before, and where it broke

• Reserve memory for the maximum answer length. The safe assumption, used by several production frameworks: admit a request only if there is room for its prompt plus the largest answer it is permitted to generate. Where it broke. Real answers are almost never that long, so memory utilisation falls to 58 to 72 percent depending on workload, requests queue, and the first-token deadline is missed — a failure of the agreement that looks like a slow service.
• Reserve the maximum, but over-commit. Pretend the GPU has more memory than it does, to claw back some of the waste. Where it broke. It works until it does not: pushed to 125 percent on a balanced workload the eviction rate reaches 84 percent of requests, because the estimate was never tracking anything real.
• Admit on prompt length alone. The aggressive approach in widespread use: if the prompt fits, take the request, and deal with the consequences later. Where it broke. The consequences are evictions — at a 99 percent memory watermark on a decode-heavy workload, evictions equivalent to 94 percent of requests — each costing a re-queue and a recomputation, and each visible to a user as a stall.
• Tune the watermark or the over-commit ratio. Both knobs trade utilisation against evictions, so surely some setting is right. Where it broke. Measured across the range, neither family reaches the frontier the distribution-based approach occupies, because neither can sense the actual load — evictions rise sharply as memory fills, regardless of where the threshold sits.
• Predict each request’s output length with a model. Classify the prompt, or fine-tune the language model to emit a length estimate. Where it broke. It adds inference cost to every request, and the predictor is tied to a model and a workload, so it does not generalise to a service running many models for many purposes.
• The gap. Every approach treats the unknown length as a number to guess — pessimistically, optimistically, or with a learned predictor. None uses the fact that the service has just finished thousands of requests whose lengths it knows exactly.

How you budget memory for text nobody has written yet

The idea

The unknown quantity is unpredictable per request and highly predictable in aggregate. Every prior approach treats a request’s answer length as a number to be guessed, and the two production strategies are simply the two extreme guesses — the maximum permitted, or nothing at all. Both are wrong in the same structural way: they replace a distribution with a point. What the trace analysis here establishes is that while any individual length is genuinely unpredictable, the distribution over a window of about a thousand requests closely matches the distribution over the next window, across conversation services, code completion and mixed API traffic. That holds even where the distribution drifts substantially over hours, because the drift is slow relative to the window. So the scheduler simply keeps a histogram of what recently finished and draws from it — nothing trained, nothing tied to a model, no extra inference. The refinement that makes it work in practice is conditioning: a request that has already produced 500 tokens has its length redrawn from the part of the distribution above 500, so the estimate tightens as the request runs and stays biased upward. Using the recent past as a model of the immediate future, and relying on distributions that are stable over minutes while drifting over hours, is exactly the observation the memory tiering work covered elsewhere on this site builds on when it tracks both long-run frequency and short-run momentum because hot data goes cold within minutes.

What the batch needs is a peak, not a total, and the difference is most of the GPU. This is the second half, and it is the one that recovers the utilisation. A running batch of requests does not need memory equal to the sum of what each will eventually occupy, because they do not all finish at the same time — the longest-running request is still holding memory long after the short ones have released theirs. What the batch actually needs is the largest occupancy reached at any future moment, and those moments are exactly the instants when a request completes, since between completions occupancy only grows. So the requests are sorted by remaining length, the occupancy at each completion instant is computed, and the maximum is taken. That number is provably sufficient to finish the batch and it is well below the sum, which is why this scheduler reaches 92 percent memory utilisation against a theoretical ceiling of 95 while a conservative scheduler sits at 58. Discovering that the cost of a workload is set by a maximum rather than a sum, so that the right question is about the worst moment rather than the total volume, is the same structural insight the sparse matrix scheduling work covered elsewhere on this site turns into a colouring problem, where the schedule length is fixed by the busiest row rather than by the number of non-zeros.

Once you can project the peak, admission becomes a question of timing. The consequence that falls out of computing memory at future moments is that admitting a request now and admitting it two steps from now are genuinely different decisions with different peaks, because in the interim something may finish and release its memory. The aggressive scheduler cannot see this and admits immediately, discovering the shortfall later when the only remedy is eviction — throwing away a partly generated answer, re-queueing it and recomputing from scratch. The conservative scheduler cannot see it either and waits until a request has actually completed, which is far later than necessary. The Past-Future scheduler waits a handful of decoding steps, which costs almost nothing, and avoids the eviction entirely. The two prior families are not merely differently tuned but structurally unable to reach the same frontier: measured across the full range of watermarks and over-commit ratios, neither trades evictions against decoding steps as favourably, because neither is sensing the load at all. Being forced to choose between two failure modes that a knob cannot reconcile is the same predicament the near-data processing work covered elsewhere on this site describes, where placing work by data locality creates hotspots and stealing work for balance doubles remote traffic.

Following one queued request to the moment it is admitted

A thousand was chosen because it balances conversation traffic, whose distribution is stable, against mixed API traffic, whose distribution drifts; further tuning made negligible difference. At startup the histogram is seeded with the maximum permitted length and converges within minutes.

Why it works

• Individual answer lengths are unpredictable but their distribution is not. Any one request may stop at any token, which is why per-request prediction requires a trained model and still generalises poorly → but across a window of a thousand requests the distribution closely matches the next window, in conversation, code and mixed API traces alike → so a plain histogram of what recently finished is a usable model, with no training, no model dependence and no added inference.
• Conditioning on progress makes a crude estimate sharpen over time. A single draw from a distribution is a poor estimate of one request → but redrawing each step from the part of the distribution above what the request has already produced excludes everything now impossible → so the estimate tightens as generation proceeds and remains biased upward, which is the direction that avoids evictions.
• A batch never needs the sum of what its requests will occupy. Requests finish at different times and release memory as they go, so the total overstates the requirement badly → and occupancy only grows between completions, so the peak must occur at a completion instant → giving an exact calculation from a sort and a walk, cheap enough to run every generation step.
• Timing is a free variable that the old schedulers could not see. The peak caused by admitting a request depends on when it joins, because a completion in the interim changes everything after it → so a request that is unaffordable now may be affordable two steps later → and waiting a few steps costs almost nothing while an eviction costs a re-queue, a recomputation, and a visible stall.
• The metric has to be the worst gap, not the average one. An eviction produces one enormous pause in an otherwise healthy stream → which an average or even a 99th-percentile gap would smooth away entirely → so measuring the maximum gap within a request is what makes the eviction-driven failure mode visible at all.

What it costs (trade-offs and scope)

• The comparison against other frameworks uses versions from December 2023. The paper states this in a footnote and notes each framework has progressed significantly since. For a field moving this fast that materially weakens the cross-framework numbers; the controlled comparison, three schedulers inside the same framework, is the one that carries weight.
• The prediction is a sample and it is sometimes wrong. Even the best configuration evicts 3.4 percent of requests on decode-heavy traffic. Driving evictions to zero requires reserving 10 percent of memory, which drops utilisation from 92 to 87 percent against a theoretical ceiling of 95.
• A reserve parameter remains. Three, five and ten percent trade evictions against decoding steps. The claim made is the right one — it beats both alternatives at every setting rather than at one lucky setting — and a knob is still a knob.
• The load-bearing assumption is distributional stability, and the paper’s own data shows it is weaker for mixed API traffic, where the global distribution varies considerably and only the adjacent-window similarity holds. A genuine step change in workload is tested by concatenating four datasets, which is reassuring; a sudden shift within a window is not.
• Public evidence for the mixed-workload case is thin. The paper notes there are no further publicly available traces for API or hybrid task services, so that category rests on one public dataset plus in-house traces.
• Startup is conservative. The histogram is seeded with the maximum permitted length and takes a few minutes to converge, so the system behaves like the pessimistic scheduler until it does.
• Small batches need repeated sampling to stabilise the estimate, which the paper acknowledges — a handful of draws is a noisy view of a distribution.
• Lengths are drawn independently per request from a marginal distribution, so correlations between simultaneous requests, such as a burst of similar prompts, are not modelled.
• The theoretical optimum is defined as knowing the true lengths, which makes it a genuine upper bound and not something any scheduler could reach.
• Main results use one model family. Llama 2 at three sizes, plus two multimodal models, on four hardware platforms. No mixture-of-experts models and no architectures whose cache does not grow uniformly per token, which is the assumption the memory arithmetic rests on.
• One conservative baseline is the authors’ own implementation for a vendor inference backend, since that backend did not ship a comparable scheduler.

The evaluation

Check yourself

Sources

The paper is “Past-Future Scheduler for LLM Serving under SLA Guarantees” by Ruihao Gong, Shihao Bai, Siyu Wu, Yunqian Fan, Zaijun Wang, Xiuhong Li, Hailong Yang and Xianglong Liu, published at ASPLOS 2025, pages 798-813, DOI 10.1145/3676641.3716011. The authors are at Beihang University, SenseTime and Peking University, and the serving framework is open source as LightLLM.

This explainer is written from the full text, drawn from the arXiv preprint arXiv:2507.10150 and the published version. Everything above comes from the paper’s own sections: the background on the two generation phases and the KV cache, on block-based memory management, on continuous batching and how the attention operator handles varying sequence lengths, and on the two existing scheduler families; the statement of the service agreement metrics and why the maximum gap between tokens is used rather than an average or a 99th percentile; the trace analysis across six datasets showing the cosine similarity of output length distributions between time windows, with the finding that adjacent windows are similar even where the global distribution varies, and the sweep over historical and running window sizes that fixes the window at a thousand requests; the prediction method with its probability distribution over recent lengths and its per-step conditional resampling; the future memory estimation with its sorting by remaining length, its per-completion occupancy formula and its maximum, together with the worked example showing that the same request admitted at different steps produces different peaks; the implementation notes on GPU-parallel computation, overhead, repeated sampling for small batches and startup initialisation; and the evaluation covering the four workload distributions, the ablation table of decoding steps, memory utilisation, future required memory and eviction rates across parameter settings for all three schedulers plus a theoretical optimum, the parameter sweep showing neither alternative reaches the same frontier, the end-to-end comparison against four other serving frameworks on four hardware platforms with its dating footnote, and the multimodal results.