When you scale out web servers, load distribution is straightforward — any instance handles any request identically. There's no state, so the router only needs to track load.
That premise breaks down in LLM serving. Each instance accumulates a different KV cache. Even if two requests share the same system prompt, a request landing on an instance that doesn't have that prompt's KV cache must rerun prefill from scratch. For a 2,048-token RAG context, that's hundreds of milliseconds wasted. Every routing decision is a compute cost decision.
KV Cache Is Local State
In web applications, session data lives in an external store like Redis, making it accessible regardless of which instance handles the request. KV cache can't work that way. It exists as tensors in GPU HBM and can easily reach several gigabytes. Moving a cache built on instance A to instance B requires a high-bandwidth GPU interconnect (NVLink, RoCE) to transfer that data, which itself introduces substantial latency.
Each instance therefore only holds the KV cache for requests it has processed. A given prefix's cache belongs to a specific instance. A router unaware of this sends requests to the wrong instance instead of the one that already has the cache.
With round-robin across N instances, the probability that a request with a given prefix lands on the instance holding its cache is 1/N. Scale out to four instances and the theoretical cache hit rate drops to 25%. The larger the serving fleet, the less value the cache provides.
How Bad Are Round-Robin and LOR in Practice?
The llm-d project ran a head-to-head comparison between cache-aware routing and round-robin on an 8-pod (16 H100 GPU) cluster and measured a 57× difference in TTFT. On the same hardware, throughput was 2× higher. On 4× AMD MI300X with Llama 3.1 70B, output tokens/sec was 3× higher and TTFT dropped by half. DigitalOcean's measurements showed cache-aware routing delivering 108% higher throughput than random routing.
Least-Outstanding-Requests (LOR) is more sophisticated than round-robin, but it doesn't perform as well as you'd hope on LLM traffic. LOR selects instances based on the current number of in-flight requests. The problem is that LLM request lengths vary wildly. An instance handling ten short requests and one handling a single long request look identical to LOR, but their actual load is completely different. LOR frequently misestimates load, and like round-robin, it has no awareness of cache locality — which is the same fundamental problem.
For a service with a 2,000-token system prompt receiving 1,000 requests per hour, every cache miss triggers a 2,000-token prefill. TrueFoundry's analysis finds that naive routing under these conditions generates 2 million redundant prefill tokens per hour.
Prefix-Aware Routing: Using the Prefix as a Routing Key
The solution is to factor the request's prefix into the routing decision. If requests sharing the same prefix always go to the same instance, that instance's cache gets reused.
Two implementations are commonly used.
The first is prefix-hash sticky routing. The shared prefix is hashed and mapped to an instance — similar to consistent hashing. It's simple to implement with low overhead, but it doesn't verify whether the target instance actually has the cache. If the instance restarts or the cache is evicted, requests keep routing to the same instance even without a hit.
The second is radix-tree-based cache-aware routing, the approach adopted by SGLang Router. The router maintains a separate prefix tree per instance. For each incoming request, it compares the prefix match length across all instances' trees. If any instance's match length exceeds a threshold, the request is sent there; otherwise, the least-loaded instance is selected. When the overall system is imbalanced, the instance with the smallest tree (least accumulated cache) is preferred to restore balance. vLLM production-stack also officially supports a similar prefix-aware routing approach.
In a 2-instance H100/Llama-3.1-8B environment, session-aware routing achieved a 96.26% cache hit rate, while round-robin and least-loaded ranged from 92.6–93.0%. The 3–4 percentage point gap looks small, but that's with only two instances. At eight instances, round-robin's theoretical hit rate drops to 12.5%, while prefix-aware routing stays near 100%. The gap widens exponentially as the fleet grows.
The Hot-Prefix Problem Sticky Routing Creates
Prefix-aware routing works well when prefix distribution is reasonably uniform. Production traffic rarely is.
The most common case is hundreds of parallel requests sharing the same system prompt. In RAG pipelines, retrieved documents often appear in the prefix as well. If 70% of requests share a single prefix, sticky routing funnels all 70% to one instance. That instance's GPU memory and request queue saturate while the others sit idle. Prefix-aware routing creates a load balancing problem — a genuine paradox.
The practical solution is hybrid overflow routing. Default to prefix-sticky, but when the target instance's load exceeds a threshold (queue depth, memory utilization, etc.), abandon stickiness and route to another instance. Overflowed requests incur a cache miss, but the prefill cost is often cheaper than the queuing latency caused by instance saturation. Short system prompts make prefill cheap, so the overflow threshold can be set low. Contexts of 4,096+ tokens are another matter — overflow is expensive, so either raise the threshold or consider pre-warming hot prefixes across multiple instances.
Llumnix (OSDI '24) takes a different approach, combining cross-instance request migration with KV-cache-aware load balancing. Compared to plain round-robin, it improves mean TTFT by up to 6.4× and P99 TTFT by up to 12.1×. Using the KV-cache-aware scheduler on top of queue-size-based load balancing yields an additional 4.6× improvement in mean TTFT.
Added Complexity in Disaggregated Prefill/Decode Architectures
Architectures like DistServe that physically separate prefill and decode instances split the routing problem into two stages. You must independently decide which instance runs prefill and which runs decode, and you pay the cost of transferring the completed KV cache from the prefill instance to the decode instance. DistServe uses a pull model where the decode instance fetches the KV cache from the prefill instance.
In this setup, fixing the prefill instance with prefix-sticky routing still leaves the decode instance selection and KV transfer path as separate concerns to manage. A single prefix-hash sticky policy can't cover the full picture, and routing logic complexity increases by another order of magnitude.
Choosing a Strategy
| Routing Strategy | Cache Hit Rate | Load Balance | Implementation Complexity | Best Fit |
|---|---|---|---|---|
| Round-Robin | 1/N (drops sharply as instances increase) | High | Low | Traffic with little to no prefix sharing |
| LOR | 1/N (same) | Medium | Low | Only when request length variance is minimal |
| Prefix-Hash Sticky | High | Low (severe with hot prefixes) | Low | Uniform prefix distribution, small fleet |
| Hybrid (threshold overflow) | High (partial degradation with hot prefixes) | Medium | Medium | Real-world traffic with hot prefixes |
| Radix Tree Cache-Aware | High (sustained) | Medium | High | Large multi-instance deployments, skewed distribution |
If prefix sharing is low — a service where every user brings a completely different context — round-robin or LOR is the right choice. There's no cache benefit from sticky routing, and it only degrades load balance quality.
If prefix sharing exceeds 30% and you're running four or more instances, cache-aware routing is the right call. When the cost difference can reach an order of magnitude or more, keeping round-robin for the sake of simplicity isn't justifiable. If hot prefixes are likely, choose threshold-based hybrid routing over pure sticky. Tuning the threshold is tricky, but it's far better than letting a single overloaded instance drag down overall throughput.
In the web server world, adding more instances makes the problem easier. In LLM serving, it's the opposite. More instances means more fragmented cache, and how well the router understands cache state determines the difference in throughput.