Deadline-Aware Batching and Tenant Fairness

Iteration-level batching decides how many sequences run per pass. It does not decide which ones. When the position budget is smaller than the queue, every admission step is a choice between requests, and the choice encodes a policy that clients experience as latency. Three distinct policies appear in serving stacks, and they answer three different questions.

Deadline slack as the ordering key

The first treats each request as carrying a deadline: a time-to-first-token target, an inter-token target, or a completion target for a known output length. A request’s slack is its deadline minus the time it would finish if admitted now, and the scheduler prefers the request with the least slack.

The attraction of slack ordering is that it degrades gracefully. Under light load every request has ample slack, so the order barely matters and the scheduler can break ties by arrival or by cache affinity. Under heavy load, requests whose deadlines are already unattainable are identifiable, and the scheduler can either admit them anyway, accepting a missed deadline, or reject them immediately so the client learns sooner. Rejecting early is usually the better behaviour: a request that will finish late is worse than a request that fails fast, because it occupies capacity while failing.

Estimating finishing time requires a model of the loop. For a decode sequence, the remaining work is the remaining output tokens, each costing one iteration, and the iteration’s duration is set by the batch it joins. The estimate therefore depends on the scheduler’s own future decisions, which makes exact slack computation circular. Implementations use a linear approximation: iteration duration as a function of total positions in the batch, fitted from observed iterations or derived from the model’s cost curve. The approximation is adequate because the decision only needs an ordering, not a prediction.

Prefill requests are harder. A prompt longer than the chunk size cannot finish in one iteration, so its time-to-first-token is the sum of the chunks it will need plus the decode steps of everything scheduled ahead of it. That sum depends on the admission order of every other request. The practical resolution is to treat prefill and decode as two queues with a fixed share of each iteration, which is what chunked prefill already imposes, and to apply slack ordering within each queue.

Shares as the ordering key

The second policy ignores deadlines and divides capacity by entitlement. Each tenant has a weight, and the scheduler serves tenants in proportion to their weights, using a virtual-time mechanism: each tenant accumulates virtual service time at a rate inversely proportional to its weight, and the scheduler always picks the tenant with the smallest accumulated time.

Weighted fair queueing has a property that deadline ordering lacks: a bound on how far any tenant can fall behind. In the fluid model, a tenant with weight w receiving a fraction of service receives at least w divided by the sum of weights, minus a term bounded by the maximum packet size. In a token server the analogue of packet size is the largest indivisible unit of service, which is one iteration’s worth of work for a sequence, not one token, because a sequence admitted to the batch advances every iteration until it finishes. That unit is large: a sequence that runs for thousands of tokens holds its slot for the whole time.

The consequence is that fairness at admission is not fairness in outcome. A tenant with many long requests occupies many slots for long periods, and a tenant with many short requests cycles through slots quickly. Virtual time should therefore be charged per iteration rather than per admission, so that a sequence consuming a slot for a thousand iterations costs a thousand units. Charging per admission gives long requests a discount and biases the scheduler toward them.

def charge(self, tenant, positions):
    # cost is work done, not requests admitted
    tenant.vtime += positions / tenant.weight

def next_tenant(self, tenants):
    # smallest virtual time wins; ties fall back to arrival order
    return min(tenants, key=lambda t: (t.vtime, t.oldest_arrival))

The interaction that makes both insufficient

Neither policy alone handles the case that matters most: a mix of short and long requests within one tenant.

Pure deadline ordering favours the long request, because a long prefill’s deadline arrives sooner relative to its work and because admitting it early stops it from blocking the queue later. The result is that a stream of long requests delays every short request behind it, and short requests are what interactive clients send. Pure fair queueing favours the tenant with the most queued work, which again means long requests, since they generate the most queue.

The common resolution is to bound the work a single request may claim in one iteration, which is precisely the chunk-size cap, and to order by a combination: least slack first among requests that fit the current iteration’s remaining budget, with virtual-time arbitration between tenants when several qualify. Requests that do not fit wait for an iteration where they do, and the scheduler guarantees that some fraction of iterations is reserved for prefill so that waiting is bounded.

A second resolution appears in systems that separate the two phases entirely: decode slots are allocated by fair queueing among resident sequences, and prefill capacity is allocated by fair queueing among waiting requests, with the split between the two pools fixed by policy. Disaggregation makes that split physical, as described in Prefill and Decode Disaggregation.

Starvation, and why arrival order is not fair

First-come-first-served looks neutral and is not. Under FCFS, a request’s waiting time depends on the work that arrived before it, so a burst of long prompts creates a queue whose drain time is the sum of their prefills. A short request arriving just after the burst waits for the entire burst. The waiting time distribution has a heavy tail that no amount of batching removes, because batching changes throughput, not order.

Two mitigations are standard. Shortest-remaining-work ordering minimizes mean waiting time and is optimal for that metric when service times are known, which for prefill they nearly are, since prompt length is known at admission. It is unfair to long requests, which can starve indefinitely if short work keeps arriving, so it is paired with an aging term that raises a long request’s priority as it waits.

The second mitigation is a reservation. Reserving a fraction of each iteration for requests that have waited beyond a threshold guarantees progress without modelling arrival rates. The reservation costs throughput when it goes unused, so it is usually expressed as a share of iterations over a window rather than a hard per-iteration quota.

What the client observes

Three observable quantities follow from these policies, and they are not interchangeable. Time-to-first-token is governed by prefill admission and by the position budget’s prefill share. Inter-token latency is governed by how many decode sequences share the batch, which the fairness policy controls only indirectly, since it decides who is admitted but not how long they stay. Completion time is the sum of the two plus the tail, and it is the quantity a deadline policy targets directly.

A policy that optimizes one of these at the expense of the others is a decision about the workload, not an implementation detail. Interactive traffic wants inter-token latency bounded, batch traffic wants completion time and throughput, and a mixed fleet needs a policy that distinguishes them at admission rather than one that averages their requirements. That distinction is also what makes the choice of autoscaling signal consequential: a fleet scaled on request count rather than on outstanding work will be sized for the wrong quantity, as Autoscaling Signals for Token Servers sets out.