A serving stack makes two separate decisions about every request. The first is admission: should this request be let in at all? The second is ordering: among the requests already inside, which one gets the next slice of GPU work? This article is entirely about the second. Ordering by arrival time is fair and blind: it treats a chat request with a 300 ms first-token budget like a batch summarization job nobody is watching. SLO-aware scheduling replaces that with an explicit per-request deadline and reorders the queue so the requests closest to breaking their promise go first. The idea is well understood in real-time systems; what makes it hard in LLM serving is that you do not know how much work a request has left.
Who runs next, not who gets in
Draw the boundary first, because the two mechanisms fail in opposite ways. Admission control owns the front door: queue caps, load shedding, returning 429 when the backlog already implies a miss, and refusing work the cluster cannot absorb. It is a yes or no decision made once, at arrival.
SLO-aware scheduling owns everything after that yes. Every request in the running set has been promised service; the only question left is the order in which the engine spends its next iteration’s compute on them. So this layer can never fix an overloaded cluster. No ordering discipline creates throughput — reordering is zero-sum, and every request you rescue is paid for by one you delay. Ordering decides which requests miss, not how many. That is still valuable: it concentrates misses on traffic that tolerates them. But when you are tuning priorities to make a capacity shortfall go away, the problem is upstream of here.
Turning an SLO into a per-request deadline
An SLO is a statement about a population — “99% of chat requests see a first token within 400 ms.” A scheduler cannot act on a population; it needs a number attached to the request in front of it. The conversion is mechanical: capture the arrival timestamp, look up the budget for that request’s class, store deadline = arrival + budget.
LLM requests need at least two of these, because they carry two distinct promises. The TTFT deadline is a point in time: the moment by which prefill must have finished and the first token emitted. The TPOT or inter-token promise is not a point but a rate — a rolling deadline for each subsequent token. A prefill-heavy request and a deep-decode request are urgent in different currencies, and a scheduler tracking only one will reliably sacrifice the other. Some deployments add a third, an end-to-end completion deadline, which only becomes meaningful once you can guess the output length — the problem two sections from now.
Earliest-deadline-first and the fine print on its optimality
Earliest-deadline-first (EDF) is the obvious discipline: sort the ready set by deadline, run the head. Its appeal is a genuinely strong result — if any schedule exists that meets every deadline, EDF finds one.
Read the fine print, though, because serving stacks violate most of it. That optimality is a preemptive, single-processor result over independent jobs. Batched LLM decoding is none of those things. Dozens of requests execute concurrently inside one iteration rather than one at a time; preemption is coarse, available only at iteration boundaries; and evicting a request mid-generation is not free, since its KV cache must be dropped and recomputed or swapped out. Requests are not independent either — they compete for one shared KV-cache pool, so serving a long context shrinks the space available to everyone else. EDF remains the right starting point, but it is not a theorem you can lean on in production.
Slack versus deadline — and why the difference bites
The diagram below draws the closely related discipline, least-slack-first (LSF), and the gap between the two is the whole difficulty of this topic. Slack is how much idle time a request can still afford: slack = deadline − now − remaining_work. LSF runs the request with the least of it.
When every request needs the same work, the two orderings are identical — subtracting a constant from every deadline does not change the sort. They diverge exactly when remaining work differs, which in LLM serving is always. A request with a distant deadline but 900 tokens still to generate is in far more danger than one with a near deadline and two tokens left, and only LSF sees that. The catch is in the formula: EDF needs only a clock and an arrival time, both exact. LSF needs remaining_work, which for a generative request is a quantity nobody has. That missing term separates textbook real-time scheduling from the thing you have to build.
The missing term: remaining work is unknown
A classic real-time task declares its worst-case execution time up front. An LLM request cannot: its cost is dominated by how many tokens it will generate, and the model decides that as it goes. Generation stops at an end-of-sequence token, and nothing knows in advance when that arrives. max_tokens bounds the answer but is usually a wild overestimate, so scheduling against it treats every request as the worst case and destroys the ordering signal.
The workable approach is to treat remaining length as an estimate refreshed every iteration rather than a constant fixed at arrival. Seed it from whatever prior you have — output-length distributions per endpoint, prompt template, or tenant beat a global average — then decay it as tokens are produced. Some systems train a small predictor. Two properties matter more than accuracy: the estimate must be cheap, since it is recomputed for the whole ready set every iteration, and it must err conservatively, because under-estimating remaining work makes a doomed request look safe until it is too late to help.
Overload, and the domino effect that breaks EDF
EDF’s optimality holds only while the request set is feasible. Push past that point and it does not degrade gracefully — it degrades worse than FIFO. The mechanism is the domino effect. The most urgent request is by definition the one closest to its deadline, so EDF runs it first; under overload it misses anyway, having consumed capacity the next request needed. That next request is now late, gets promoted to the head, misses, and takes the following one down with it. A discipline that would have delivered most requests on time instead delivers almost none, because it spent every iteration on requests that were already lost.
The defence is to stop pretending the set is feasible. Detect overload, then change discipline: retire requests whose deadlines are provably unreachable — a decision about work already inside, distinct from refusing arrivals at the door — and fall back to something value-based that maximises the count of requests completed on time rather than servicing the most urgent one. Deadline-aware ordering is a policy for a healthy system, and it must know when it is not in one.
Fairness: stopping tenants from gaming their own deadlines
Pure deadline ordering has an obvious exploit in a multi-tenant service. Urgency derives from a declared SLO, so any tenant who declares a tighter one gets served first. Left unchecked, every tenant discovers this, the tight-SLO class becomes the only class, and you are back to FIFO with extra bookkeeping — except a single aggressive tenant can now crowd everyone out by asking for more.
The fix is to make urgency a claim on your own share, not on the whole GPU. Give each tenant a capacity entitlement — a weight, a token budget, a virtual-time credit — and let deadline ordering operate within it. A tenant spending beyond its share has its effective priority decayed, so its tight deadlines stop outranking a neighbour who is behaving. Weighted fair queueing, or a deficit-round-robin outer loop with EDF inside each tenant’s queue, is the usual shape. The other half of the answer is commercial: tighter SLOs should be a paid tier with an enforced rate limit. When declaring urgency is free, it carries no information.
Starvation, aging, and the cost of preempting a decode
Any priority scheme starves its lowest priority. Under deadline ordering the victims are predictable: long generations and requests with generous budgets. A long request accumulates work faster than the clock moves it up the queue, so a steady stream of short, urgent arrivals keeps it perpetually second in line — with a large KV-cache footprint idle the whole time.
The standard remedy is aging: let effective priority rise with waiting time, so nothing is deferred indefinitely. Cap it hard — after n deferrals or t seconds a request becomes non-preemptible and runs to completion. GPU serving adds its own reason for restraint: preempting a decoding request means evicting or swapping its KV cache, and resuming it costs a recompute or a transfer over PCIe. Preemption is not the free reordering primitive it is on a CPU: a scheduler that churns the running set every iteration burns more capacity on eviction and recomputation than the better ordering recovers. Prefer reordering the waiting queue over evicting work in flight.
Measure attainment, not the mean
Deadline-aware scheduling is invisible to the metric most dashboards lead with. Mean latency improves when you make fast requests faster — the opposite of what this scheduler does, since it deliberately slows requests with room to spare to rescue ones without. Judged on the mean, a correctly working SLO scheduler looks like a regression.
The metric that matches the mechanism is SLO attainment: the fraction of requests that met their own deadline. A per-request pass or fail aggregated into a percentage, it is the only number that reflects what you promised. Report it separately for TTFT and for the inter-token rate, since a request can pass one and fail the other, and break it out per tenant and per SLO class — a global 99% can conceal one tenant sitting at 60%. Framing it as an error budget (a 99% target permits 1% misses per window) makes it operable: it says how much headroom is left, and gives the overload fallback an explicit trigger instead of a hand-tuned threshold.