Routing, load balancing, queueing

Once you have more than one GPU replica serving a model, the question stops being "how do I run inference?" and becomes "how do I send each request to the right replica?" This sounds simple until you realize that LLM requests are wildly heterogeneous: a 50-token completion finishes in milliseconds, while a 4096-token generation holds a slot for seconds. A naive round-robin balancer treats them identically, and the result is predictable: some replicas are swamped while others idle.

Today I want to walk through three layers of the problem: routing strategies, load balancing algorithms, and request queueing. Together they determine whether your inference cluster actually uses the GPUs you're paying for.

Layer 1: Routing strategies

At the highest level, routing decides which pool of replicas a request should target. In a production LLM deployment, there are several reasons you might want more than one pool:

• Model version routing. You're running v1 and v2 side by side during a canary rollout. Traffic is split 95/5 based on a header or user segment.
• Priority routing. Paid users hit a pool with more replicas or faster GPUs. Free-tier traffic goes to a separate pool that might queue.
• Prefix-aware routing. If two requests share the same system prompt, routing them to the same replica lets the KV cache be reused. This is sometimes called "sticky routing" or "cache-aware routing," and it can cut time-to-first-token (TTFT) dramatically for repeated prefixes.

Prefix-aware routing deserves special attention. In systems like vLLM with prefix caching enabled, the KV cache for a shared system prompt is computed once and reused across requests. If your load balancer scatters requests randomly across replicas, every replica computes the same prefix independently. A hash-based routing scheme (hash the system prompt, map to a replica) keeps prefix-sharing replicas hot.

# Prefix-aware routing: hash the system prompt to pick a replica
import hashlib

def route_by_prefix(system_prompt: str, num_replicas: int) -> int:
    h = hashlib.sha256(system_prompt.encode()).hexdigest()
    return int(h, 16) % num_replicas

The tradeoff: sticky routing concentrates load. If one system prompt dominates traffic, its target replica becomes a hotspot. A good system combines prefix-awareness with a fallback: try the preferred replica, but overflow to others if its queue depth exceeds a threshold.

Layer 2: Load balancing algorithms

Once a request reaches a pool, the load balancer picks a specific replica. Here are the strategies I've seen used in practice, ordered by sophistication:

• Round-robin. Simple rotation. Works when all requests are the same size, which they never are in LLM serving. Still, it's the default in many setups because it requires zero state.
• Least connections. Route to the replica with the fewest in-flight requests. Better than round-robin, but it treats a 10-token request and a 4000-token request as equal.
• Least tokens in flight. Weight each connection by the expected output length (if known) or the current tokens being generated. This is closer to the actual GPU load. Some serving frameworks expose a /metrics endpoint with tokens-in-flight counts that a balancer can poll.
• Join-the-shortest-queue (JSQ). Route to the replica whose internal request queue is shortest. This accounts for batching: a replica that's already batching 32 requests might still accept one more cheaply, while a replica at its batch limit will queue the request.

In practice, I've found that least-connections with a health-check heartbeat handles most workloads well enough, and the jump from round-robin to least-connections is much larger than the jump from least-connections to anything fancier. Start simple.

Layer 3: Request queueing

When all replicas are busy, requests have to wait somewhere. The queue design matters more than most people think:

• Centralized vs. per-replica queues. A centralized queue (e.g., a Redis list or an in-process FIFO) ensures no replica is idle while another's queue is full. Per-replica queues are simpler but can lead to imbalanced draining.
• Priority levels. A two-tier queue (high and low priority) with strict priority scheduling ensures paid requests preempt free-tier ones. Be careful with starvation: add a maximum wait time for low-priority requests.
• Admission control. If the queue grows beyond a threshold, reject new requests with HTTP 429 rather than letting latency balloon. An SLO like "p99 TTFT under 2 seconds" is only meaningful if you're willing to shed load when you can't meet it.

# Simple priority queue with admission control
import heapq, time

class InferenceQueue:
    def __init__(self, max_depth=100):
        self.heap = []
        self.max_depth = max_depth
        self.counter = 0

    def enqueue(self, request, priority=1):
        if len(self.heap) >= self.max_depth:
            raise QueueFullError("HTTP 429: queue at capacity")
        # Lower priority number = higher priority
        heapq.heappush(self.heap, (priority, self.counter, time.time(), request))
        self.counter += 1

    def dequeue(self):
        if not self.heap:
            return None
        return heapq.heappop(self.heap)

The interaction with continuous batching

One thing that makes LLM load balancing different from traditional web services is continuous batching. In a continuously-batched engine like vLLM, a replica doesn't process requests one at a time. It dynamically adds new requests to the running batch as old ones finish. This means the "load" on a replica isn't just "number of requests" but "how much KV cache memory is allocated" and "how many tokens remain to generate."

A smart load balancer for continuous batching should factor in the replica's available KV cache slots, not just its in-flight request count. If a replica has 90% of its KV cache allocated, sending it another long-context request will cause it to preempt (evict and recompute) existing requests, hurting everyone's latency.

Putting it together

A production-grade routing stack for LLM inference typically looks like this:

• An API gateway handles authentication, rate limiting, and routes to the correct model pool.
• A load balancer (NGINX, Envoy, or a custom sidecar) picks a replica using least-connections or a KV-cache-aware metric.
• Each replica runs a continuous batching engine with its own internal queue and admission control.
• A centralized queue (optional) absorbs bursts and drains into replicas as slots free up.

The goal is always the same: keep every GPU's batch full without letting any single request wait too long. It's a balancing act between throughput (fill the batch) and latency (serve quickly), and the right tradeoff depends on your SLO.

Next: multi-cloud capacity, where routing crosses cloud boundaries and the tradeoffs get even more interesting.