Routing, Load Balancing & Queueing — Inference Engineering

01

Why round-robin struggles

TL;DR · Web load balancers assume requests are roughly equal. LLM requests vary 100× in token count, so round-robin piles uneven work on replicas and blows up tail latency.

Today's win: you'll predict why round-robin fails for LLMs, what to route on instead, and how queueing protects your tail latency. Start with what breaks.

Requests are wildly unequal

Round-robin sends request 1 to replica A, request 2 to replica B, and so on — counting requests, not work. That's fine on the web, where requests look alike. But LLM requests vary 100× in token count, and decode time scales with length. Counting requests ignores the actual workload.

The damage: skew and a long tail

Ignore the workload and you get uneven replica utilization — one replica buried in giant generations while another idles — and tail latency explosion. The slow replica drags your P99 even though the average looks calm.

Keywords — tap to unfold the plain meaning

Analogy ❝A round-robin host seats the next party at the next table regardless of size, so one waiter ends up with five big parties and another with none. The seating looks "fair" — everyone got the next open table — but the work is wildly lopsided. In an LLM cluster, "party size" is token count, and one replica drowns while its neighbor twiddles its thumbs.

Round-robin balances request count; LLM requests vary 100× in tokens, and decode scales with length — so it skews load and explodes the tail.

02

Route by work, not count

TL;DR · First LLM-specific rule: balance by pending tokens and KV occupancy, not by connection count — because requests differ so much in size.

If counting requests is the wrong unit, what's the right one? Measure the thing that actually costs: tokens in flight and the memory they hold.

Pick the unit that matches the cost

Token-aware routing balances by pending tokens / KV occupancy instead of request count. A replica chewing through one 8k-token generation is "busier" than one handling three tiny chats — token-aware routing sees that and steers around it.

The signal you watch

The practical routing signal is how many requests are stacked up waiting on each replica. Send the next request to the replica with the least pending work, so load tracks real GPU occupancy rather than a connection tally.

Keywords — tap to unfold the plain meaning

SRE note In Kubernetes, balance by tokens, not connections. The per-replica routing signal to monitor is num_requests_waiting — the depth of each replica's queue. Steer new traffic toward the replica with the smallest waiting queue, not simply the next one in rotation.

Route by WORK not count: balance on pending tokens / KV occupancy, watching num_requests_waiting per replica.

03

Route by prefix

TL;DR · Second LLM-specific rule: send matching prompts to the replica that already has a warm cache, so a re-prefill becomes a cache hit and TTFT drops.

Web load balancers are stateless on purpose. LLM replicas are not — they hold a warm KV cache, and routing that ignores it throws away free speed.

Caches are warm — use them

KV-cache-aware routing sends requests with a matching prompt to the replica whose cache is already warm for that prefix. That converts an expensive re-prefill into a cheap cache hit (this builds on prefix caching from Lesson 20).

How you pin a prompt to a replica

Use consistent-hash / session affinity on the prompt prefix: hash the shared prefix and always route it to the same replica. Identical system prompts then land where their KV blocks already live, instead of scattering and re-prefilling everywhere.

Hash on the shared prefix and the two "prefix A" requests both land on replica 1, where the KV blocks are already warm — a re-prefill becomes a cache hit.

Keywords — tap to unfold the plain meaning

Route by PREFIX: consistent-hash the prompt prefix to the same replica, turning re-prefills into warm cache hits and cutting TTFT.

04

Protecting the tail

TL;DR · FIFO is fair but lets one giant request block small ones. Priority queues, SLA tiers, and deadlines let you protect interactive traffic.

Routing picks which replica. Queueing discipline picks who goes first once requests pile up at that replica — and that choice is where your tail latency is won or lost.

FIFO is fair — and dangerous

FIFO serves requests in arrival order. It's perfectly fair, but a single giant generation at the front blocks small ones behind it. Your snappy chat request waits behind a 30-second batch job for no good reason.

Let some traffic jump the line

Priority queues / SLA tiers / deadlines let you protect interactive traffic. Mark interactive chat high-priority and it skips ahead of bulk jobs; attach a deadline and the scheduler honors latency targets instead of pure arrival order.

Keywords — tap to unfold the plain meaning

SRE note In Kubernetes, add priority classes + deadlines so large jobs don't starve interactive chat. Put bulk/batch work in a lower tier and your interactive tier keeps its tail latency even when the cluster is busy.

FIFO lets a giant request block small ones; priority queues, SLA tiers, and deadlines protect interactive traffic.

05

Keep each replica below its knee

TL;DR · The golden rule: keep each replica just below its knee. Push past that utilization threshold and queue depth and P99 latency explode — queueing theory guarantees it.

All the routing tricks aim at one number: keep each replica under the point where latency goes vertical. Cross it and no router can save you.

The knee is a cliff

Every replica has a knee — a utilization threshold. Below it, latency is flat and calm. Beyond it, queue and P99 latency explode. This is the same latency–throughput knee from Lesson 15, now applied per replica.

Why it's a law, not a tuning knob

The blow-up isn't bad luck — it follows from M/M/c queueing theory. As utilization approaches 1, expected wait time shoots toward infinity. Routing and autoscaling exist to keep every replica on the flat side of that curve.

Below the knee, latency barely moves with load. Past it, M/M/c queueing makes wait time go vertical — so routing keeps every replica on the flat side.

Keywords — tap to unfold the plain meaning

Math, decoded

L = λ · W · W → ∞ as ρ → 1

LLittle's Law: average number of requests in the system at once
λarrival rate — how many requests show up per second
Waverage time a request spends in the system (wait + service)
ρutilization — fraction of capacity in use; the knee sits just below ρ = 1

Little's Law (L = λ·W) ties how full the system is to how long requests wait. As utilization ρ climbs toward 1 — past the knee — the wait W blows up under M/M/c queueing. The whole job of routing is to hold ρ on the flat side.

Analogy ❝Think of a one-road bottleneck into town. With light traffic, adding a few more cars barely changes your drive — the road has slack. But there's a knee: once it's nearly full, one extra car turns a smooth commute into a standstill, and everyone's wait time shoots up at once. Keeping each replica just below its knee is keeping that road just shy of gridlock.

Keep each replica just below its knee. Past that utilization threshold, queue depth and P99 explode per M/M/c queueing theory — Little's Law makes it inevitable.

06

On your cluster

TL;DR · Your traffic is prefill-heavy RAG, so prefix-hash routing is your single biggest win: turn shared system prompts into cache hits and slash TTFT.

The theory points straight at one lever for your box. Measure your own traffic profile and the highest-value move falls right out.

Read your traffic profile first

Your cluster runs 19–47:1 prefill-heavy RAG — retrieval-augmented generation, where documents are fetched and pasted into prompts, creating long, shared prompts — with --enable-prefix-caching turned on. Lots of prompt to read in, comparatively little to generate.

So prefix-hash routing wins

With shared system prompts everywhere, prefix-hash routing is your biggest win: turn shared system prompts into cache hits, slashing TTFT. Pair it with token-aware balancing and priority classes, and watch num_requests_waiting per replica.

Cluster note Measured on the 4×H100 box: a 19–47:1 prefill-heavy RAG profile running with --enable-prefix-caching. Because prefill dominates and prompts share long prefixes, consistent-hash / session affinity on prompt prefix converts those shared system prompts into warm cache hits — the biggest TTFT win available here. Routing signal to watch: num_requests_waiting per replica.

The three LLM-aware routing rules, as config intent

# 1. balance by WORK, not connections
balance_on: pending_tokens     # watch num_requests_waiting

# 2. route by PREFIX — warm cache hits
affinity: consistent_hash(prompt_prefix)

# 3. protect the TAIL
queue: priority_classes + deadlines   # interactive > bulk
rule: keep each replica just below its knee

Keywords — tap to unfold the plain meaning

Check yourself

Explain to a colleague: "Our LLM router should differ from a web load balancer by…" (Hint: balance by tokens/KV load since requests vary 100×; route by prompt-prefix to warm caches and cut TTFT; use priority queues so large jobs don't starve interactive traffic.)
Why does round-robin fail for LLM traffic but work fine for ordinary web requests?
What single routing change is the highest-value lever on a prefill-heavy RAG cluster, and why?
What happens to queue depth and P99 latency once a replica is pushed past its knee?

On a 19–47:1 prefill-heavy RAG box with --enable-prefix-caching, prefix-hash routing is the biggest TTFT win — turn shared system prompts into cache hits.