Why does round-robin load balancing misbehave across LLM replicas?

## The assumption round-robin encodes Round-robin is optimal under one condition: request cost is roughly uniform and short relative to the arrival rate. Then dealing requests in turn approximates dealing work in turn, and any momentary imbalance washes out within a few hundred milliseconds. Every conventional HTTP load balancer defaults to it because that condition holds for typical web traffic. LLM traffic violates both halves of the condition. ## Cost variance Generation cost is dominated by output length, which the caller does not declare and the balancer cannot see. A yes/no classification emits perhaps 5 tokens; a document summary emits 2,000; an agent trace emits 10,000. Prompt length varies as widely and drives prefill cost and KV-cache footprint. So two requests that look identical to a proxy — same route, same method, same size class of body — can differ by two or three orders of magnitude in GPU seconds and in cache blocks held. ## Duration A web request finishes in milliseconds; an LLM generation occupies a slot in the running batch for seconds to minutes, streaming the whole time. That means imbalance accumulates instead of dissipating. If replica A happens to receive three long generations early, it holds them while the round-robin pointer keeps handing it new work at exactly the same rate as everyone else. Its running batch fills, its KV-cache occupancy climbs, and arrivals begin to queue — while replica B, which happened to draw short requests, has idle capacity the whole time. The user-visible result is a bimodal latency distribution. Median looks fine because most requests land on unloaded replicas; p95 and p99 are dreadful because the unlucky ones queue behind a saturated replica. Fleet-level dashboards make this hard to see: average GPU utilization looks healthy, average queue depth looks low, and only the per-replica breakdown reveals that one member is pinned while others coast. ## Least-outstanding-requests The cheap improvement is to balance on in-flight count rather than cumulative count. Envoy calls this LEAST_REQUEST (with the power-of-two-choices variant that samples two hosts and picks the less loaded, which is nearly as good and much cheaper than scanning every host); nginx offers `least_conn`. Because a long generation keeps its request or connection open for its entire duration, in-flight count is a far better proxy for occupied capacity than a round-robin counter. Two caveats. First, connection-based policies only approximate request count when connections are not multiplexed; with HTTP/2 many streams share one connection, so a connection-counting policy sees one unit where there are twenty streams — prefer a request-aware policy. Second, in-flight count still treats a 5-token request and a 5,000-token request as one unit each. It is a much better proxy, not a correct measure. ## Inference-aware routing The engines already publish the truth. vLLM exposes `vllm:num_requests_running`, `vllm:num_requests_waiting` and `vllm:kv_cache_usage_perc`; TGI and Triton publish their own queue and batch series. A router that consumes those — polling them, or receiving them pushed — can send the next request to the replica with actual free slots and cache headroom, and can refuse to pile onto a replica that is already preempting. This is what inference-aware gateways such as the Kubernetes Gateway API Inference Extension exist to do, and it is what any in-house router should approximate. A useful middle ground when you do not want a metrics-driven router: cap in-flight requests per replica at the client or proxy, so no replica can be handed more than it can hold, and let excess wait in one shared queue rather than in per-replica queues. A single shared queue is strictly better than N private ones because work goes to whichever replica frees a slot first. ## Where the balancer must not overreach One thing the balancer should not do is retry aggressively on slow responses. On a saturated fleet, a timeout-and-retry policy duplicates the most expensive requests at exactly the moment capacity is scarcest, and the duplicate usually lands on another already-loaded replica. Retries here need a strict budget, and streaming responses complicate them further because a retry after the first token has already shipped bytes to the client. ## What to watch Always graph the per-replica distribution, not the fleet average: running batch size, queued requests and KV-cache occupancy, per pod. A healthy fleet shows those curves tracking one another. A round-robin fleet under mixed traffic shows one line pinned to the ceiling and the rest well below it — that single picture is the whole argument.