Why might round-robin load balancing produce uneven latency across identical LLM replicas? Compare routing by queue length, estimated remaining tokens, KV-cache locality, and least-connections, and explain how you would prevent a single long request from starving short ones.

How to think about it

Round-robin can produce uneven latency because it balances request count, while LLM work depends on prompt length, generated-token count, batching, and cache state. I would route using predicted work or finish time, add KV-cache locality as a bounded bonus, and enforce fair scheduling so one long generation cannot block short requests.

Why identical replicas behave differently

“Identical” describes the hardware and model weights. It does not mean the replicas have identical work at a particular moment.

Round-robin sends request one to replica A, request two to B, and so on, without asking what each request costs. That is reasonable when requests have roughly equal service times. An image thumbnail request taking 40 milliseconds is a good fit for round-robin. An LLM request is not a thumbnail request with more punctuation.

An LLM request has at least two expensive phases:

• Prefill processes the input prompt and builds the attention state needed for generation.
• Decode generates output tokens, usually one autoregressive step at a time.

A 12,000-token prompt can create much more prefill work than a 200-token prompt. A request that generates 2,000 tokens can occupy a decode slot far longer than one that generates 40. The actual time is model- and hardware-dependent, so token count is not a perfect clock, but it is a much better work signal than request count.

Latency is also not one number. Time to first token, or TTFT, is the delay before streaming begins and is heavily affected by queueing and prefill. Time between tokens reflects decode contention. Total completion latency includes both. A router that improves average completion time but makes TTFT terrible for interactive requests has not solved the customer’s problem.

The replicas diverge as soon as they receive different work. Their queues, active sequences, GPU memory use, and cached attention states are now different. Round-robin continues as if none of that happened.

A concrete failure

Imagine four replicas and eight requests arriving close together. Round-robin gives two requests to each replica.

Replica A receives:

• one request with an 8,000-token prompt and a 2,000-token completion;
• one request with a 500-token prompt and an 80-token completion.

Replica B receives two requests with 500-token prompts and 80-token completions. C and D receive similarly small requests.

Every replica has a queue depth of two. A queue-length dashboard therefore looks perfectly balanced. The GPU work is not balanced. A must perform a large prefill and then many decode iterations while B may finish both of its requests quickly.

Now another request arrives. Round-robin sends it to whichever replica is next in the cycle. It may choose A even though A is still processing the 2,000-token generation. The user sees a high TTFT, despite every replica being “identical” and every queue containing two requests.

Continuous batching changes the shape of this problem but does not remove it. A serving engine can combine active sequences into a batch and advance them together. The long request still consumes decode compute and KV-cache memory across many iterations. It can also prevent new work from entering when the engine has reached its sequence or memory limit.

Comparing routing signals

Signal	What it captures	Main failure
Queue length	How many requests are waiting or active	One request can represent 50 tokens or 50,000
Estimated remaining tokens	Approximate compute still owed by each replica	Tokens are not equal work, and future output is uncertain
KV-cache locality	Whether a useful prompt prefix is already cached	Sticky routing can overload one replica
Least-connections	How many active streams or requests a replica owns	One long stream still counts as one connection

Queue length

Routing to the shortest queue is a useful baseline. It is cheap, easy to explain, and generally better than round-robin when request sizes vary only modestly.

Be precise about the measurement. A queue containing only requests waiting for admission is different from a count that includes active generations. In either case, the metric is incomplete. Two active requests might be tiny, or one might be producing a long legal document.

Queue length also becomes stale under concurrency. Two frontends can both observe replica B as the least busy and send work there before either observation is updated. A centralized scheduler or an eventually consistent load signal needs protection against this race.

Estimated remaining tokens

A stronger policy estimates the work already assigned to each replica. For queued requests, the system knows the prompt length and may know a requested output cap. For active requests, it knows how many tokens have already been generated and can estimate what remains.

The router can then prefer the replica with the lowest predicted finish time, rather than the fewest requests. In rough terms, its score includes:

• estimated prefill cost for waiting prompts;
• estimated decode cost for active generations;
• current batch and memory constraints;
• the new request’s own prompt and expected output.

Do not simply add prompt tokens and output tokens as though they cost the same. Prefill and decode stress the GPU differently, and batching can make their marginal costs different. A production system normally learns or calibrates separate cost estimates.

The weakness is obvious: the future output length is unknown. max_tokens is a ceiling, not a forecast. A user asking for 2,000 tokens may stop after 100, while another asking for 200 may trigger a long tool-use loop. Estimates can also be wrong for different prompts or decoding settings. Token-aware routing is therefore a prediction, not a measurement of destiny.

KV-cache locality

The KV cache stores attention keys and values for tokens already processed. Reusing a cached prompt prefix avoids doing that prefill work again. Because the cache usually lives in GPU memory local to one replica, sending a request to the replica holding its prefix can reduce TTFT and free compute for other work.

Consider a support bot with a repeated 2,000-token system prompt and many requests from the same tenant. A prefix-aware router can keep those requests near the replica that already holds the relevant KV entries. A plain round-robin router spreads them around, causing avoidable cache misses and repeated prefill.

Locality is not a free win. If every request with a popular prefix is pinned to one replica, that replica can become the hottest one in the fleet. Cache entries can also be evicted, and moving a live generation to another replica may require rebuilding or transferring a large KV state. I would use locality as a bounded preference, not an absolute rule: route to the cache owner when its predicted load is within an acceptable margin, otherwise choose a less-loaded replica.

Least-connections

Least-connections works well for ordinary services with long-lived connections and roughly comparable work per connection. It is often better than round-robin for streaming LLM responses because it at least notices that some replicas have more active requests.

It still misses the central issue. A replica with two 4,000-token generations may be much busier than one with eight 50-token generations. Both active-request counts and TCP connection counts hide the amount of GPU work remaining. Least-connections is a reasonable fallback signal, not a complete LLM scheduler.

Preventing starvation

A single long request should not own an exclusive batch slot until it finishes. I would handle this in two layers.

At the replica scheduler, use iteration-level scheduling so active generations receive fair opportunities to decode rather than letting one request run to completion. Use chunked prefill, which breaks a very large prompt’s prefill into smaller pieces, so it does not monopolize the GPU while waiting interactive requests sit idle.

Then add fairness rules:

• cap per-request output or total token budgets;
• reserve some concurrency for short or interactive requests;
• use weighted fair scheduling or priority with aging, where a waiting request gradually gains priority;
• limit active sequences per tenant;
• consider separate short-request and long-request pools when the latency objectives are genuinely different.

Shortest-remaining-processing-time scheduling can reduce average latency because short jobs finish quickly. Used without aging or reserved capacity, it can starve long jobs indefinitely. The opposite policy, strict first-in-first-out scheduling, protects order but makes one huge prefill a roadblock. Neither textbook extreme is usually right for a production chat service.

Preemption deserves care. Pausing a decode request sounds attractive, but its KV cache still occupies memory. Evicting it to host memory or reconstructing it later can cost enough that the cure is worse than the queue. Often the better answer is bounded decode fairness, chunked prefill, and admission control rather than constant migration.

The router should expose the signals the scheduler actually needs: queue wait, TTFT, active sequences, prompt tokens, generated tokens, GPU memory pressure, token throughput, and KV-cache hit rate. Watch tail latency, not just average latency. The 3 a.m. page will usually be about the p99 interactive request waiting behind a request that nobody expected to become a 10,000-token essay.

The senior-level trade-off

There is no universally best routing policy.

Queue length is robust and simple but coarse. Token estimates are more expressive but uncertain. KV locality saves real work but can create hotspots. Least-connections adapts to streaming load but still treats a tiny request and a huge generation as equivalent.

A practical design combines them into a predicted-finish-time score, gives cache locality a limited bonus, and lets the replica-level scheduler enforce fairness. It also measures whether the policy is actually helping: TTFT, completion latency, cache-hit rate, GPU utilization, queue age, and starvation incidents.

What they’ll ask next

Why not route every request to the replica with the shortest queue?
Because queue length counts jobs, not work. A single long prompt or generation can outweigh many short requests, and a cache miss can add substantial prefill work.

How would you estimate output length when it is unknown?
Use the request’s output cap as an upper bound, historical lengths by endpoint or tenant, and live generation progress. Treat the estimate as uncertain and retain fairness safeguards so a bad prediction cannot monopolize capacity.

Would you ever choose a busier replica for cache locality?
Yes, if the cached prefix saves enough prefill to offset the extra queueing. I would set a load threshold rather than pinning blindly; a cache hit should not turn one replica into a permanent hotspot.

One line to say in the room

“Round-robin balances requests, but LLM serving must balance predicted GPU work, preserve useful KV locality, and schedule tokens fairly so one long generation cannot starve short requests.”