In a multi-instance LLM serving environment, routing is no longer just a question of "which server to send a request to." The choice of instance determines both TTFT and cache hit rate simultaneously. The problem is that these two goals are fundamentally in tension — a router that distributes load evenly and a router that maximizes KV cache reuse do not make the same decisions. Because output length is unknown at request time, no single router can optimize for both goals at once.
This post examines how different strategies handle that tension, and under what conditions.
Why LLM Routing Differs from HTTP Load Balancing
A conventional L4/L7 load balancer distributes requests statelessly. It assumes that the processing cost of each request is roughly uniform and that any server can handle it equally well. LLM requests break that assumption in three places.
First, prefill and decode are asymmetric in cost. Prefill is a compute-bound phase that processes the entire input token sequence at once; decode is a memory-bandwidth-bound phase that generates tokens one at a time. The cost difference between a request with 8,000 input tokens and one with 100 tokens can be an order of magnitude or more. A router that ignores this will see its queue explode the moment long-prefill requests pile up on a single instance.
Second, output length is unknown in advance. An HTTP server knows the response size ahead of time, but an LLM does not know the output length until the EOS token is generated. A Least-Connections-based load balancer may send a request to "the instance with the fewest active requests," but if that instance is already processing ten requests each generating 2,000 tokens, its actual load is far higher than the request count suggests.
Third, KV cache state differs across instances. An LLM engine caches the attention KV pairs from previously processed requests. If the next request starts with the same prefix as a cached one and is routed to the same instance, the prefill computation can be skipped entirely. In Moreh's measurements, running a Qwen3-32B model (8,000-token system prompt + 1,000-token user input) across eight AMD MI250 pods, random routing produced a P50 TTFT of 4,464 ms; switching to prefix-aware routing brought it down to 217 ms — a 20× improvement.
When all three factors combine, a stateless load balancer's "balanced" decision can easily become the worst possible one.
Four Routing Strategies, Dissected
Round-Robin / Random
The simplest approach. It distributes requests in rotation or at random, with no reference to instance state. Implementation cost is zero and there are no hotspots.
The problem is cache efficiency. When requests sharing the same system prompt are spread evenly across eight instances, each instance repeatedly recomputes the same prefix. In Ranvier's measurements, Round-Robin on an 8-GPU setup achieved a cache hit rate of 12.5% — essentially the probability of landing on the same instance by chance (1 in 8). Prefix-aware routing on the same workload hit 97.5%.
Throughput also diverges. On the same 8-GPU setup, Round-Robin delivered 36.3 req/s versus 44.4 req/s for prefix-aware routing (a 22.3% gap). P99 TTFT was 6,800 ms vs. 1,000 ms.
Round-Robin is reasonable for diverse one-off traffic with no prefix reuse. For workloads with shared prefixes — API serving with a fixed system prompt, chatbots, code agents — it should be avoided.
Least-Outstanding-Requests (LOR)
Routes to the instance with the fewest in-flight requests. It balances load better than Round-Robin, but is equally blind to cache state. Output length uncertainty means "fewer requests" does not guarantee "lighter load." Least-Connections-style strategies have limited applicability in LLM serving — they work only when prefix reuse is negligible and request length variance is low.
Prefix-Hash Routing (Session Affinity)
Hashes the request's prefix (or session ID) to always route to the same instance. Cache hit rate is maximized. The problem is hotspots.
When traffic converges on a particular system prompt, the single instance assigned that prefix's hash ends up handling a disproportionate share of total traffic, while the remaining instances sit idle. This imbalance worsens as the number of instances grows — with four instances, the hot instance may handle more than 25% of traffic; scale to sixteen and the other fifteen can be doing more than half their capacity in idle time.
Concretely, analysis in the DualMap paper shows that pure prefix-affinity routing causes tail latency to spike sharply as the hot instance's queue fills up and p99 explodes. Under high QPS, prefix-only routing successfully handled roughly 55% of requests; combining it with load-awareness brought that back to 100%.
Hotspot mitigation options do exist. Partial replication — copying popular prefix KV caches across multiple instances — maintains hit rates while distributing traffic, at the cost of replication overhead and wasted memory. Adaptive prefix hashing — subdividing the hash key for hot prefixes to spread them across more instances — takes the same direction. Ray Serve's prefix-aware routing uses this approach: when the queue-length difference between instances exceeds imbalanced_threshold, it automatically switches from cache-priority to load-balancing mode.
KV-Aware Routing
Collects real-time KV cache state and current load from each instance before making a routing decision. In theory, this is the best strategy for trading off between the two goals.
vLLM Router implements this direction with Consistent Hashing — routing cache-stickily based on session ID or routing key while also consulting instance load information. SGLang's cache_aware policy computes prefix matching via a radix tree and falls back to load balancing (shortest queue) when needed.
# dstack gateway configuration example (SGLang)
router:
type: sglang
policy: cache_aware # random | round_robin | cache_aware | power_of_two
# vLLM Router policy examples
# Consistent Hashing: routing_key(session_id, user_id) → sticky worker
# Power of Two (PoT): randomly sample two instances → pick the lighter one
# Round Robin / Random: stateless fallback
However, the real cost of KV-Aware routing depends on how frequently and accurately instance state can be collected.
The Real Cost of KV-Aware Routing: The Staleness Problem
For the router to know each instance's KV cache occupancy, queue depth, and current request count, it must poll. SGLang's router runs health checks every 30 seconds by default, with load metadata refreshed on a shorter cycle. The problem is that cache state can change between polling intervals.
The longer the polling interval, the more the router's decisions diverge from reality. If the router determines that "instance A has the KV cache for this prefix" when that cache has already been evicted or overwritten, the routing decision is wrong. Under high load, cache eviction accelerates, making staleness more damaging.
vLLM Router and SGLang approach this differently. vLLM Router explicitly supports prefill/decode disaggregation (P/D disaggregation), using ZMQ-based discovery and NIXL/NCCL backends to synchronize instance state more quickly. vLLM's P/D disaggregation-based router achieved 100% higher throughput and 1,200 ms lower TTFT compared to a Kubernetes-native setup on a Llama 3.1 8B 8+8 pod configuration.
SGLang's cache_aware policy automatically falls back to shortest-queue routing when it detects that its state information has gone stale. It's not perfect, but it's better than continuously making wrong decisions based on outdated information.
When staleness exceeds a critical threshold, a KV-Aware router can perform worse than Round-Robin. Round-Robin at least has no reason to make an incorrect decision — having no information is better than having wrong information.
Where Request Distribution Flips the Strategy
When shared prefix ratio is low (0–20%), no routing strategy makes a meaningful difference in cache hit rate. Round-Robin or LOR is sufficient.
Above 50% prefix sharing, strategies diverge sharply. Per Ranvier's measurements, in a 50% token-sharing environment, prefix-aware routing achieved a 91% hit rate while Round-Robin stayed at ~11%. The TTFT difference maps directly to the 28× gap between a cache hit (18 ms) and a cache miss (500 ms).
At 90% prefix sharing, prefix-aware routing pushes hit rates to 97–98%. At the same time, hotspot problems worsen — nearly all requests converge on a small number of prefix hash values, saturating specific instances.
As instance count grows, Prefix-Hash hotspots intensify, but so does the staleness cost of KV-Aware routing — more instance metadata must be collected and polling overhead increases. With a small number of instances (2–4), Prefix-Hash is simple and effective. Beyond 16 instances, pure prefix-hash without a load-aware fallback becomes dangerous.
The table below summarizes strategy characteristics across three scenarios for a 4-instance setup.
| Scenario | Round-Robin | Prefix-Hash | KV-Aware |
|---|---|---|---|
| 0% prefix sharing (diverse queries) | ~12% cache hit, balanced load | ~12% cache hit, balanced load | ~12% cache hit, polling overhead incurred |
| 50% prefix sharing | ~11% cache hit, TTFT disadvantaged | ~91% cache hit, hotspot risk | 60–80% cache hit (staleness-dependent), load trade-off |
| 90% prefix sharing | ~12% cache hit, worst TTFT | ~97% cache hit, severe hotspot | 75–90% cache hit, load trade-off, staleness risk |
Hotspots: How a Popular Prefix Can Kill One Instance
Consider a chatbot API where the top system prompt accounts for 60% of all traffic. Under Prefix-Hash routing, that prompt maps to a single instance. That instance's KV cache and request queue fill up rapidly; when GPU memory is exhausted, it either OOMs or experiences a burst of evictions that paradoxically drives hit rate back down. The remaining instances sit idle.
In this scenario, p99 TTFT spikes come from queue wait time on the hot instance. As new requests keep arriving while the instance is busy, queuing delay cancels out the latency savings from cache hits.
Two mitigation strategies are practical. The first is load threshold fallback — the approach Ray Serve uses, where when the queue-length difference between instances exceeds a threshold, cache-priority is abandoned in favor of load balancing. The second is partial KV cache replication — copying popular prefix KV caches to multiple instances so traffic can be split. It costs memory, but that's preferable to OOM on a hot instance.
Choosing a Strategy
Three variables drive the routing strategy decision: prefix reuse rate, instance count, and latency SLO.
| Condition | Recommended Strategy |
|---|---|
| Low prefix reuse (0–20%) + few instances | Round-Robin or LOR |
| High prefix reuse (50%+) + few instances (2–4) | Prefix-Hash (threshold fallback recommended) |
| High prefix reuse + many instances (8+) | KV-Aware (cache_aware + load fallback) |
| Strict latency SLO + high prefix reuse | KV-Aware + short polling interval + fallback |
| Prefix reuse rate unknown | Start with LOR, monitor hit rate, then switch |
The conditions under which Round-Robin should not be the default are clear: system prompt sharing above 30%, an active TTFT SLO, and two or more instances. When all three conditions overlap, the cache miss penalty of Round-Robin exceeds the benefit of balanced load.
Conversely, defaulting to KV-Aware is also wrong. If the polling interval is not short enough — collecting state every 500 ms when instance cache state changes on a 100 ms timescale under high load — more than half the router's information is already stale. In that situation, KV-Aware can make worse decisions than Round-Robin.
Without measuring the three variables first, strategy selection is guesswork. The right sequence is: measure actual prefix reuse rate from live traffic (vLLM's cache_hit_rate metric, SGLang's radix tree hit statistics), then choose a strategy based on those numbers.