How do you design a cache-aware request router for distributed LLM inference?

A cache-aware LLM router selects an eligible model replica using both prefix KV-cache locality and current server load. Unlike round-robin routing, it tries to send a request to a replica that already holds the same prompt-prefix KV states, avoiding repeated prefill. But blindly following the cache can overload popular replicas, so the router also needs queue, latency and capacity signals.

1. Why ordinary load balancing can waste GPU work

• Imagine two replicas running the same compatible model and tokenizer. Replica A has already computed the KV cache for a large, shared system prompt; replica B has not.
• Round-robin may send a matching request to B, forcing B to recompute that prefix.
• A cache-aware router recognizes the reusable prefix on A and may send the request there if the time saved is greater than A's expected queueing delay.
• The prefix match must respect model/adapter identity, multimodal and position context, cache validity and permitted tenant sharing. A semantic similarity score is not sufficient for KV reuse.

2. Architecture and request path

1. Authenticate and select compatible endpoints. Filter by model, adapter, version, security boundary, health and hardware capabilities.
2. Compute a prefix identity from normalized token/hashed block context without putting raw sensitive prompts into shared router logs.
3. Estimate available KV-cache overlap per endpoint. Options include an index/controller reporting block ownership, or approximate locality using a session or prefix hash.
4. Collect live load signals: waiting/running requests, KV occupancy, predicted prefill/decode cost and observed TTFT.
5. Rank eligible replicas using the predicted time-to-first-token or a calibrated score that combines cache-hit benefit and load; route to the best choice.
6. Update cache metadata and health state. Deal with evictions, replica restarts and scale-outs; on missing or stale cache information, fall back to ordinary load-aware routing.

3. Beginner-friendly numerical example

A 4,000-token prompt reaches two healthy replicas:

• Replica A: 3,000 reusable prefix tokens; estimated queue wait 220 ms.
• Replica B: no cached prefix; estimated queue wait 20 ms.
• Assume uncached prefill takes 400 ms, and reusing 3,000 of 4,000 tokens hypothetically reduces A's remaining prefill work to an equivalent 100 ms.
• Estimated time before the first token, ignoring other common overhead: A = 220 + 100 = 320 ms; B = 20 + 400 = 420 ms.
• Route to A in this example. But if A's queue grows to 400 ms, then A ≈ 500 ms, so routing to B would be better.

These are illustrative estimates. Prefill compute is not strictly linear in token count, cached suffix processing still attends to the full prefix, and actual scheduler and hardware behavior should drive the cost model.

4. A practical score

One documented vLLM Production Stack load-aware scoring approach is:

score(i) = matched_tokens(i) / prompt_tokens
           − β × relative_load(i)

relative_load(i) = (load(i) − mean_load) / max(1, mean_load)

Choose the endpoint with the highest score. β controls how strongly the router avoids overloaded replicas. A large β favors load balancing; a small β favors cached-prefix reuse. This is an example policy, not a universal optimal formula.

5. Common operational failures

• Hot-prefix concentration: many requests share one prefix and overload its cache holder. Include live load and spill to idle replicas.
• Stale cache index: an eviction, crash or scale-out invalidates predicted KV ownership. Treat misses as normal and reconcile metadata.
• Unequal workloads: raw request counts ignore prompt length, output length, decode phase and cache pressure; ideally use estimated remaining work.
• Tenant or adapter mix-ups: do not share private KV blocks across incompatible trust boundaries. Use trusted cache namespaces/salts or isolate replicas.
• Expensive remote KV transfers: when a distributed cache can move blocks between replicas, include network transfer latency in the placement decision; remote reuse is not always faster than recomputation.
• Uneven capacity: some GPUs or serving configurations are faster; normalize predicted latency rather than assuming identical workers.

6. Benchmark and rollout

Compare round-robin, least-loaded, prefix-affinity, and cache-plus-load-aware routing using identical repeated-prefix and unique-prompt traffic. Measure p50/p95/p99 TTFT, overall latency, per-replica queues, KV hit-token rate, preemptions, GPU usage, cost and SLO-compliant goodput. Test cold starts, hot prefixes, cache eviction, replicas failing, and multi-tenant traffic. A cache-aware policy may lose to least-loaded routing when most prefixes are unique.

Interview-ready answer: “I'd route only among compatible and authorized model replicas, estimate how many prefix KV tokens each can reuse, and combine that cache benefit with queueing and KV-capacity signals. The goal is minimum predicted response delay, not maximum cache affinity. I'd fall back safely on stale cache metadata and benchmark against least-loaded routing under real workloads.”

References: vLLM Production Stack — Load Aware Routing; vLLM — Prefix Aware Routing; vLLM Router load-balancing policies; llm-d Prefix-Cache Aware Routing.