How LLM Routing Strategies Balance Cache Reuse and Queue Time

In large-scale LLM inference serving, a seemingly minor scheduling decision—which backend replica to route a request to—can significantly affect cost, latency, and throughput. When users repeatedly send the same or highly similar prompts, routing must consider not only which machine is idle, but also which machine already has that context cached. Cache reuse can save a substantial amount of prefill computation, but chasing reuse may push a request into a longer queue. This tension is at the heart of LLM router design.

Why Cache Reuse and Queue Time Conflict

LLM inference is typically split into two phases: prefill, which processes the input prompt, and decode, which generates output token by token. The compute cost of prefill scales with prompt length and is one of the main drivers of latency and compute consumption. If a replica has just handled a request with the same prefix, its KV cache still holds the corresponding key-value state, so subsequent requests can skip that computation entirely.

The problem is that caches are stored locally per replica. When the router directs a request to a "hot" replica to reuse its cache, that replica may already be busy handling other work, forcing the new request to wait in line. Conversely, a "cold" replica must perform the full prefill, but it may be idle and able to start immediately.

The original article sums up this tension in one line: "four routing strategies, one repeated prompt, and the point where a cold replica wins." Four routing strategies behave differently when faced with the same repeated prompt, and at certain thresholds, choosing a cold replica is actually faster.

KV cache is the key concept for understanding the whole article. In the Transformer architecture, the self-attention mechanism computes a set of key and value vectors for every processed token, which later tokens query during generation. At each decode step, generating a new token requires reusing the KV vectors of all previous tokens, and the computation for those vectors scales with context length. The KV cache stores already-computed KV vectors in GPU memory to avoid recomputation. Its size grows linearly with the number of model layers, attention heads, head dimension, and sequence length, so for long contexts and long conversations, the KV cache for a single request can reach several gigabytes and is one of the main consumers of GPU memory. Precisely because it occupies GPU memory and is stored locally per replica, it becomes tightly coupled with scheduling, eviction, and affinity—making it the resource in routing decisions that both creates value and demands a price.

Four Typical Routing Strategies

The original article discusses four routing approaches, each assigning different weights to cache and queue:

1. Round Robin

The simplest approach: distribute requests to replicas in turn. It completely ignores caching and keeps queue distribution relatively even. When prompt repetition is low and replica load is similar, round robin is simple and reliable; but with repeated prompts, it cannot exploit any existing cache, so prefill cost is always paid in full.

2. Least Queue / Least Loaded

The router picks the replica with the fewest currently queued requests. This minimizes waiting time, but again ignores cache. When a replica happens to have the request prefix cached but is skipped because its queue is longer, the system wastes a reuse opportunity.

3. Cache-Aware Routing

The router preferentially sends requests to replicas whose cache already contains the same prefix. On a cache hit, prefill is nearly zero and time-to-first-token drops sharply. The cost is that if that replica is busy, the request must queue; moreover, caches have eviction mechanisms, so a hit requires that the cache entry has not yet been evicted.

4. Hybrid / Cost-Based

This approach converts cache benefits and queue waiting into a unified cost. For example, it estimates whether "prefill time saved by a cache hit" exceeds "extra queue time," then decides whether to go to a hot or cold replica. This is theoretically optimal, but it requires an accurate cost model and real-time load information.

Prefill-decode disaggregation is another background concept for understanding routing tradeoffs. Because prefill is compute-intensive and processes long sequences in parallel, while decode is memory-bandwidth-intensive and generates tokens serially one at a time, the two have very different hardware requirements. In recent years, disaggregated architectures have emerged that place these two phases on different instances or resource pools, letting prefill nodes focus on throughput and decode nodes focus on low latency. In such architectures, caches—especially KV caches—must be transferred or shared between the two, and routing decisions are no longer just "which machine to send to," but also how prefill results are passed to decode instances and whether transfer overhead cancels out cache reuse benefits. The four strategy types discussed in the original article are already complex enough in monolithic architectures; under disaggregated architectures, they gain an additional cost dimension: cache migration.

When a Cold Replica Wins

Intuitively, a cache hit is always good. The original article's emphasis on "the point where a cold replica wins" shows that this is not always true.

Imagine a scenario: the hot replica has the target prefix cached, but its queue already contains several long requests, with an expected wait of several seconds; a cold replica is idle and can perform the full prefill in a shorter time. If "prefill time < queue wait," then the cold replica yields lower total latency.

This creates a decision threshold. The router needs to compare two quantities:

• Go to the hot replica: queue time + very short prefill (cache hit)
• Go to the cold replica: near-zero queue + full prefill

When the hot replica's queue is long enough and prefill is fast enough, the cold replica becomes the better choice. The original article sets out to characterize this tipping point, showing that neither "cache first" nor "queue first" is sufficient on its own.

Cache eviction policy determines whether a "hit" is even possible. KV cache space on a replica is limited, and as new requests keep arriving, old cache entries must be reclaimed according to some rule. Common approaches include LRU (evict least recently used), LFU (evict least frequently used), and weighted schemes that consider prefix length or recomputation cost. This means that even if a replica once handled the same prefix, once its cache has been displaced by new requests, the hit rate falls and the effectiveness of "cache-aware routing" fluctuates accordingly. Mechanisms such as prefix caching also typically share and deduplicate cache entries by common prefixes to improve reuse across multiple requests that share a system prompt. Therefore, if a router's cost model assumes constant cache hits, it will overestimate the benefits of hot replicas and make bad decisions during high-pressure periods with frequent cache eviction.

Implications for Inference Infrastructure

This analysis yields several practical conclusions for LLM serving:

Cache is not a free win. The benefits of cache reuse must be discounted by potential queueing costs, especially under uneven load.

Load balancing and cache affinity are inherently opposed. Cache affinity pulls requests toward the same set of replicas, easily creating hotspots; pure load balancing scatters requests and sacrifices reuse. The router must dynamically trade off between the two.

The cost model determines routing quality. The effectiveness of a hybrid strategy depends on how accurately it estimates prefill duration, queue latency, cache hit rate, and related factors. These parameters vary with model, hardware, and request distribution, so static configurations are often suboptimal.

Repeated-prompt scenarios see the greatest benefit. For workloads with high repetition, such as multi-turn conversations, shared system prompts, and templated tasks, cache-aware routing is most valuable—and most in need of careful threshold decisions.

The opposition between cache affinity and load balancing is a classic issue in distributed systems, with roots in early practice around web caching, database partitioning, and CDN scheduling. In traditional settings, cache affinity often uses consistent hashing to pin the same user's requests to the same node to improve hit rate, at the cost of hotspots when node load is uneven. LLM routing is similar but more complex: the popularity distribution of request prefixes is highly dynamic, and the cache benefit—time saved on prefill—varies with prompt length, making it hard to capture with static hashing. As a result, the industry tends to use quantitative cost functions for online decisions, combined with mechanisms such as work stealing, request migration, or cache replication to mitigate hotspots. Understanding this analogy helps frame LLM routing as a new instance of distributed cache scheduling rather than an isolated problem.

Summary

LLM routing is not simply "find an idle machine" or "find a machine with cache," but a real-time tradeoff between cache reuse and queue time. The four strategies each have tradeoffs, and the counterintuitive conclusion that a cold replica can beat a hot one under certain conditions reminds us that optimal routing depends on accurately modeling prefill cost and queue latency. For teams building inference services, putting cache-hit benefits and queueing costs into the same cost function gets closer to true low latency than optimizing either one alone.

One-line Summary

At its core, LLM routing is a real-time tradeoff between cache reuse and queue time—and sometimes a cold replica is faster.

Paragraph Summary

The article points out that the key tension in LLM inference routing is the tradeoff between cache reuse and queue time: although a cache hit can greatly reduce prefill computation, storing the KV cache locally per replica means that chasing reuse may push requests into longer queues. It compares four routing strategies—round robin, least queue, cache-aware, and hybrid cost-based—each weighting cache and queue differently. Counterintuitively, when a hot replica's queue is too long while prefill itself is fast, choosing an idle cold replica can lower total latency, creating a clear decision threshold. The article concludes that cache is not a free win, cache affinity and load balancing are inherently opposed, and routing quality depends on accurate cost modeling of prefill duration, queue latency, and cache hit rate.