Least-Outstanding Routing When Request Costs Vary

A router in front of identical replicas has one job: decide which replica receives the next request. Round robin discharges that job by counting. Request number n goes to replica n mod k, on the assumption that each request costs the same and each replica serves at the same rate. Both assumptions hold for stateless handlers with uniform work. Neither holds for token generation.

The cost of a generation request is roughly the prompt length plus the output length, multiplied by the model’s per-position cost. Prompt length is known after tokenization. Output length is not known until the request ends, and its distribution is heavy-tailed: most requests finish in tens of tokens, some run to the context limit. A router that ignores this hands a 30,000-token prompt and a 40-token chat turn the same weight.

Why equal counts produce unequal queues

Suppose two replicas each hold ten requests. On the first, the ten requests are short chat turns that will each produce 50 tokens. On the second, one request is a long document summarization that will produce 4,000 tokens while the other nine are short. The continuous batching loop on the second replica advances every sequence by one position per iteration, so the nine short requests are stuck behind the long one for thousands of iterations. Their inter-token latency is set by the slowest co-resident sequence. The count-based router sees ten and ten, judges the replicas balanced, and is wrong by a factor of eight in outstanding work.

The error compounds because routing decisions are sticky. A request assigned to a loaded replica stays there for its entire generation, and its cache stays resident. A router cannot rebalance by moving work later, since moving a sequence means moving its key-value blocks. Placement is decided once, at admission, and the cost of a bad decision persists for the request’s whole lifetime.

Scoring by work in flight

The direct fix is to make the load signal proportional to work rather than to arrivals. Each replica reports, or the router tracks, the number of positions it currently owes: for every resident sequence, the tokens generated so far plus an estimate of what remains. A practical version uses prompt tokens plus a fixed allowance for output, since output is unknowable, and updates the estimate as tokens are produced.

Two variants appear in practice. Least-outstanding-requests scores a replica by its count of in-flight requests, which is a coarse proxy but requires no model of token cost. Least-tokens scores by outstanding token work, which is more accurate and needs the router to know prompt lengths, meaning tokenization must happen before routing rather than inside the replica.

A third variant scores by occupancy of the cache rather than by token count. Because the number of blocks in use is what actually prevents admission, a replica at ninety percent occupancy will soon be forced to preempt, and its next admitted sequence is therefore more expensive than its score suggests. Occupancy is also cheap to measure, since the allocator already tracks it.

Neither is complete without accounting for the replica’s own condition. A replica that has just started has an empty cache but cold caches at every other level, including compiled kernels and weights that must be read from host memory. Its first requests are slower than its steady-state rate, so a router that floods it because its outstanding count is zero will overload it. The standard remedy is to ramp traffic gradually, or to exclude a replica from the pool until it reports ready, which is the same distinction covered in Autoscaling Signals for Token Servers.

Two random choices instead of a global minimum

A router with a complete view can compute the exact minimum, but a complete view means every replica’s load must be fresh at every decision, which is expensive at high request rates and fragile across a fleet that spans availability zones. Randomized selection avoids that.

The power-of-two-choices rule samples two replicas uniformly at random and sends the request to the one with the lower score. With n replicas and uniform work, this reduces the maximum queue length from order log n / log log n, which is what a single random choice produces, to order log log n / log log log n. The result is asymptotic and assumes independent, memoryless arrivals; generation traffic is neither, but the practical effect holds: sampling two and comparing beats sampling one, and sampling more than two buys little.

import random

def choose(replicas, prompt_tokens, allowance=256):
    a, b = random.sample(replicas, 2)
    # estimate of work this request will add to the chosen replica
    incoming = prompt_tokens + allowance
    score_a = a.outstanding_tokens + incoming
    score_b = b.outstanding_tokens + incoming
    if score_a != score_b:
        return a if score_a < score_b else b
    # ties broken by cache affinity, then arbitrarily
    return a if a.cached_prefix(prompt_tokens) >= b.cached_prefix(prompt_tokens) else b

The tie-break line matters more than its brevity suggests. When two replicas carry similar load, the decision should favour the one that already holds the prompt’s prefix in cache, because prefill over a cached prefix is close to free compared with prefill from scratch. That preference is the entire subject of Prefix-Cache-Aware Routing, and it interacts with load scoring: a slightly busier replica with a warm prefix can finish sooner than an idle one without it.

Signals, staleness, and the retry trap

Every load-aware router depends on a signal, and every signal is stale. If replicas push their outstanding counts periodically, the router sees a value that is one interval old, and in a continuous batching loop the count can change by the whole batch in a few milliseconds. Two consequences follow.

The router must treat the signal as a hint rather than a fact. A large difference between two scores is trustworthy; a small difference is not, and the tie-break should then be decided by something stable such as cache affinity or a deterministic hash of the request id, which also prevents oscillation.

Retries must not re-enter the same selection path unmodified. When a replica fails or times out, the client retries, and the retry adds load to a system that is already degraded. If the router re-runs the same least-loaded comparison, the retry lands on whichever replica looks emptiest, which during an incident is the one about to fail next. Shedding, retry budgets, and a circuit breaker per replica are the standard containment, and they belong at the router rather than at the client.

There is also a measurement trap. A router that counts completed requests to estimate capacity learns the wrong lesson when replicas are heterogeneous: a replica on a faster interconnect finishes more requests per second, receives more traffic under a count-based policy, and appears even faster. Score-based routing with work in flight avoids this feedback because the score is a state, not a rate.

What routing cannot fix

Routing balances load; it does not create capacity. When every replica’s outstanding work is above the level at which inter-token latency meets its target, no assignment improves the outcome, and the correct response is to refuse or to queue at the front door. Deciding where that threshold sits requires the latency-versus-batch curve for the specific model, which is what the admission policies in Deadline-Aware Batching and Tenant Fairness encode as deadlines and shares.

Routing also cannot undo the cost of a poorly chosen replica after the fact. Because cache is pinned to the replica that produced it, a misrouted long-context request is expensive to move and impossible to move cheaply once generation is under way. The placement decision is made once per request, so the quality of the score at that instant is the whole game.