Deadline-Aware Batch Assembly

A latency target for a generated token is not a single number the scheduler can check. There are two distinct requirements, and they are satisfied by opposite policies. Time to first token depends on when the request’s prompt is processed, which rewards prioritising new arrivals. Inter-token latency depends on how regularly a running sequence is stepped, which rewards protecting the running set from interference. A batch assembled to satisfy the first degrades the second, and vice versa. Making the trade explicit requires turning both targets into a quantity the scheduler can compare across sequences of different kinds.

From a target to a budget

An inter-token latency target of $D$ milliseconds means each sequence must be stepped at least once every $D$ milliseconds. If the scheduler runs steps of duration $t_{step}$, then a sequence stepped every step sees an inter-token latency of $t_{step}$, and a sequence stepped every $n$ steps sees $n \cdot t_{step}$. Meeting the target therefore requires $n \le D / t_{step}$, and since all sequences in the running set are stepped every step in the standard design, the requirement reduces to a bound on step duration.

That bound is the useful form of the target. A step of duration $t_{step}$ satisfies every running sequence simultaneously, so the scheduler’s job is to keep $t_{step}$ below $D$ while putting as much work into each step as possible. The work available per step is the batch of decode positions plus any prompt chunks, and its cost is roughly the weight read plus the arithmetic, plus any collective latency. Since the weight read is fixed, the slack in the budget is the arithmetic and communication headroom, and that is what prompt chunks and additional sequences consume.

Time to first token has a different structure. A request arriving at time $a$ with a prompt of $T$ tokens must be admitted, have its prompt processed, and emit one token by $a + D_{ttft}$. If prompt processing is chunked at $C$ tokens per step, it needs $\lceil T/C \rceil$ steps of prefill plus one decode step, so the request’s earliest possible first token is at $a + (\lceil T/C \rceil + 1) t_{step}$ assuming it is scheduled immediately. The slack for such a request is the difference between its deadline and that earliest completion, and it is the quantity to compare when deciding which prompt to admit next.

Slack as the scheduling key

With both targets expressed as deadlines, the running set and the waiting queue become a set of jobs with deadlines and estimated remaining work. The natural policy is earliest-deadline-first, and it has a known property: for a set of jobs on a single machine where preemption is free, EDF is optimal in the sense that if any schedule meets all deadlines, EDF does.

The property does not transfer cleanly, for three reasons. The work estimates are not exact: the number of tokens a sequence will generate is unknown, so its deadline for completion is unknown, and only its per-token deadline is usable. Preemption is not free: it costs a swap or a recompute. And the machine is not a single resource: a step consumes bandwidth, arithmetic, and interconnect in proportions that vary with the batch.

What survives is a weaker but still useful rule. Order the candidates by slack, defined as deadline minus estimated completion time, and prefer those with the least slack. For decode sequences, the deadline for the next token is the last step time plus $D$, so all running sequences have nearly equal slack and the ordering is uninformative; that is why decode sequences are stepped together rather than ordered. For prompt chunks, slack varies widely with prompt length and arrival time, and the ordering matters.

def order_prefills(prefills, now, ttft_target, step_time, chunk):
    for p in prefills:
        steps_needed = ceil_div(p.remaining, chunk) + 1
        p.earliest = now + steps_needed * step_time
        p.slack = (p.arrival + ttft_target) - p.earliest
    # least slack first; ties broken by arrival to avoid starvation
    return sorted(prefills, key=lambda p: (p.slack, p.arrival))

A negative slack means the request cannot meet its target even if scheduled now. That is not a reason to drop it; it is a signal that the target is infeasible for the current load, and the scheduler should decide deliberately whether to admit it anyway, to reject it, or to admit it with a degraded promise. Admitting it silently and missing the target is the one option that produces no useful information for anyone.

Goodput, not throughput

Throughput counted in tokens per second rewards a scheduler for generating tokens nobody is waiting for. The quantity that matters is goodput: tokens delivered within their latency targets, per unit time. A policy that maximises throughput under load typically does so by growing the batch until steps exceed the latency target, at which point throughput is high and goodput collapses because every token is late.

The relationship between batch size and goodput has a characteristic shape. At small batches, steps are short, deadlines are met, and goodput is limited by the work per step. As the batch grows, goodput rises because more work is done per step. Past the point where step duration exceeds the latency budget, tokens become late and goodput falls even though the device is doing more work. The optimum sits just below the latency-feasible batch size, and the scheduler’s task is to find it without overshooting.

Finding it dynamically is a control problem. The step duration is measurable, the batch size is adjustable, and the target is a bound on the former. A simple controller raises the batch while measured step time stays below a fraction of the budget, and lowers it when the measurement exceeds the bound. The fraction matters: reacting only at the boundary means every adjustment overshoots, and the resulting oscillation is visible as latency variance. A margin of twenty to thirty percent below the target is the usual operating point, because step duration itself varies with which sequences are in the batch.

Where the policy interacts with memory

Every scheduling decision in this cluster is ultimately a memory decision, and deadline awareness does not change that. Admitting a prompt to meet a first-token deadline consumes cache blocks that a running sequence might need for its next token. If the pool is tight, the admission that satisfies one request’s deadline is the eviction that breaks another’s.

The ordering that resolves this is to prefer admissions that cost little memory for the latency they recover. A request whose prefix matches cached blocks costs almost nothing and can be admitted immediately; a request with a long unique prompt costs a full reservation. This is why prefix caching and shared residency is a scheduling mechanism and not only a memory optimisation: it changes the price of meeting a deadline.

Similarly, the chunk size for prompt processing is a latency knob with a memory consequence. Smaller chunks shorten the time to a first token for a long prompt but multiply the weight reads; larger chunks do the opposite. Since a prompt’s cache must be reserved in full before its first chunk, the chunk size does not change the memory cost, only the time distribution. That makes it a free parameter from the memory side and a contested one from the latency side, which is why it belongs to the scheduler rather than to the kernel.

Fairness under deadline pressure

Strict earliest-deadline-first starves long jobs whenever short ones keep arriving. In a serving system the long jobs are the requests with long outputs or long prompts, and they are exactly the requests whose users wait longest. Starvation is therefore not an abstract fairness concern; it shows up as a class of requests whose latency is unbounded.

The standard remedy is a weighted scheme in which each tenant or request class has a share of the step budget, and deadlines are enforced within a share rather than globally. A class that is behind its share gets priority regardless of slack, which bounds its worst-case wait. The cost is that the global optimum is not achieved: a schedule that meets every deadline when one exists may not be available once shares are enforced.

A second remedy is aging: a request’s effective priority improves the longer it waits, so a starved request eventually outranks newer arrivals. This is the same mechanism as priority aging in operating systems, and it has the same tuning problem, in that the aging rate determines how much deadline violation is traded for bounded waiting.

The failure that looks like success

The characteristic pathology of deadline-aware scheduling is a system that reports high throughput and low average latency while a small fraction of requests miss their targets by a wide margin. Averages hide this, and the tail is where the requirement lives; the reasons are the same as those described for tail-tolerant systems generally. Reporting the fraction of tokens delivered within target, alongside the distribution’s high percentiles, is the only way to see whether the policy is working.

The second pathology is measurement aliasing. If the scheduler measures step duration on the device and the client measures inter-token latency at the network boundary, the two differ by queueing, transfer, and serialisation time. A scheduler tuned to the device measurement can meet its internal bound while the client-observed latency exceeds the target by the fixed overhead. The budget must be set from the client-visible requirement minus the transport’s contribution, and that subtraction is a deployment-specific number rather than a constant.

Both pathologies point at the same design rule: the scheduler should be given the target in the units the client cares about, and it should account for the fixed costs between its own step boundary and the client’s observation. A target expressed in device time is a target the scheduler can meet without the client noticing, which is the worst of both outcomes. The remaining structural response to latency pressure, rather than tuning within one pool, is to change the pool topology, which is what disaggregated prefill and decode pools does.