10 — KV-Cache-Aware Routing: Why Scheduling Beats Kernel Optimization at Fleet Scale

Thesis: Once you have 4+ replicas of an inference engine, the biggest lever left is which replica gets the request. Route a request to the replica that already holds its prefix in KV cache and you skip prefill entirely. This is arithmetic that dwarfs any kernel optimization.

Prior reading: 04_engines/ (prefix caching / RadixAttention), 09_disaggregated_serving.md.

1. The size of the prize (why this dominates)

Take a chatbot at turn 8 of a conversation. The prompt is 6000 tokens of history plus 200 new tokens. On a 70B fp16 model:

  • Cold prefill (no cache): 6200 tokens × ~140 GFLOPs/token = ~870 TFLOPs of matmul → ~450ms on an H100 at ~2 PFLOPs bf16.

  • Warm prefill (5900-token prefix cache hit): only the last 300 tokens are new → ~22ms.

  • Speedup: ~20x on TTFT and roughly 20x fewer prefill FLOPs consumed by that request.

Now imagine 60% of your fleet’s requests share prefixes (system prompts, few-shot exemplars, in-progress conversations, agentic scratchpads). Every kernel optimization you can do fights over ~10–30% wins. KV-cache-aware routing hands you a 3–10x throughput multiplier for free.

Your Zoho agentic-harness intuition already tells you why: every tool-calling loop sends the same growing conversation back N times. The system prompt alone can be 2000+ tokens shared across every user.

2. The three routing strategies (in order of sophistication)

2.1 Random / round-robin (baseline)

The default of every load balancer. Every replica has a cold cache for every prefix. TTFT is uniformly bad; prefix cache hit rate hovers near random-chance (∼1/N).

2.2 Session-affinity / sticky routing

Hash session_id → replica. If the same user always lands on the same replica, that replica accumulates their conversation KV. This works, but:

  • Hot users overload their replica.

  • New sessions still cold-start.

  • Cross-user shared prefixes (system prompts, few-shot) don’t help.

  • Failover breaks affinity.

2.3 Prefix-hash routing (the real answer)

Hash prefixes of the input token sequence (e.g., every 256-token block) and use consistent hashing / a prefix tree to route requests to the replica most likely to already have that KV.

Two implementations dominate:

a. Router-side radix tree. The router maintains a global radix tree keyed by hashed token blocks; each leaf points to the set of replicas holding that block. On a new request, tokenize, walk the tree, choose the replica with the deepest match (tie-break by load).

b. “Cache reporter” pattern. Each engine (SGLang, vLLM) periodically publishes its RadixAttention cache root hashes to the router. Router picks max-overlap replica. Simpler than global tree; near-identical hit rates in practice.

3. The consistent-hashing gotcha

Naïvely hashing hash(prefix) % N is wrong: every autoscale event reshuffles every prefix. Use rendezvous (HRW) hashing or a consistent hash ring so that adding/removing one replica only invalidates 1/N of prefixes.

Bonus trick: replicate the K hottest prefixes across multiple replicas so no single replica is overloaded by “the shared system prompt of doom.” This is exactly memcached/CDN theory applied to KV cache.

4. The three signals a good router balances

At any moment your router is jointly optimizing:

Signal

What it says

How to measure

Prefix-hit potential

Which replica already has most of this request’s KV

Radix-match length, cache-hash overlap

Load

Which replicas can accept without SLO violation

Running batch size, KV utilization %, queue depth

Warmth for future requests

Placing this request here builds cache for later ones

Prefix popularity, session identity

Common weighting: score = α·prefix_match_tokens − β·queue_depth − γ·kv_util. Tune α, β, γ per workload.

Rule of thumb: at low load, route purely by prefix; at high load, load-balance harder and let some hits slide.

5. Current production stacks

5.1 SGLang RadixAttention + cache-aware router

  • Engine: RadixAttention (paper: SGLang, Zheng et al. 2024) stores KV in a radix tree, evicts LRU. Public and battle-tested.

  • Router: python -m sglang_router.launch_router --policy cache_aware — polls each worker’s cache tree, routes by longest prefix match with load-balancing decay.

  • This is the reference implementation. If you’re evaluating anything, start here.

5.2 NVIDIA Dynamo + KV router

  • Dynamo (formerly Triton’s inference orchestrator, rebranded 2025) ships a first-class KV-cache-aware router for vLLM/TensorRT-LLM backends.

  • Integrates NIXL (NVIDIA’s KV transfer library) so cache can move to the replica when moving the request is worse (P/D disagg territory).

5.3 vLLM Production Stack / LMCache

  • vLLM V1 engine reports prefix-cache-hash → external router (vllm serve --enable-prefix-caching).

  • LMCache adds a shared CPU/SSD tier of KV cache accessible by multiple vLLM instances — so “cache miss” on GPU can still be an HBM-load from local CPU RAM rather than a full recompute.

5.4 llm-d and AIBrix (Kubernetes-native)

  • llm-d — CNCF-adjacent project; treats “replicas with cache” as a first-class routing primitive. Combines KV routing with autoscaling and P/D disagg. Watch this space.

  • AIBrix (ByteDance open-source) — similar goals; ships a Gateway + cache-aware router + autoscaler as a Kubernetes controller.

6. What the metric plane must look like

If you’re building or evaluating a router, these are the numbers your dashboard must show, per-request and aggregated:

  • Prefix-cache hit rate (tokens served from cache / total prompt tokens) — the North Star.

  • Per-replica cache hit rate — spot skew.

  • P95 TTFT split by hit/miss — cache hits should have order-of-magnitude lower TTFT; if they don’t, the router is lying or the engine is stalled.

  • Route-decision latency — the router itself has an SLO. >5ms of routing overhead is a code smell.

  • Re-route/steal events — how often a request was moved because the target replica went over budget.

  • Cache-eviction rate — high eviction on hot replicas → capacity problem, not routing problem.

7. Failure modes (learn these before you deploy)

  1. Prefix-hash mismatch: router computes hash before tokenizer normalization; engine computes after. Result: 0% hit rate in production despite 60% in offline sim. Fix: tokenize inside the router, or agree on a canonical tokenization contract.

  2. Sticky-hotspot: one very popular system prompt makes one replica melt. Fix: replicate hot prefixes across K replicas; load-shed by weighting queue depth harder.

  3. Cache oscillation: router thrashes between replicas after every autoscale. Fix: consistent hashing (HRW) + minimum dwell time before rerouting.

  4. Small-K starvation: at low QPS, all traffic goes to one “matching” replica, leaving others idle. Fix: floor on minimum utilization spread; explore-exploit tradeoff (occasionally place at random to warm other replicas).

  5. Correctness bugs from KV reuse: wrong tokenizer, wrong bos, wrong system-message injection order. Test: end-to-end deterministic-output eval on every deploy — any diff between cached and cold response is a P0 bug.

8. The napkin math you should be able to do

Given:

  • Fleet: 8 replicas of Llama-3-70B fp8 on H100.

  • Workload: 10 RPS, avg prompt 4000 tokens, 60% prefix reuse (share-GPT-like).

  • Per-request prefill (cold): 4000 × 140 GFLOPs = 560 TFLOPs → ~280ms.

  • Per-request prefill (warm, 60% hit): 1600 × 140 GFLOPs = 224 TFLOPs → ~112ms.

At 10 RPS with random routing you spend 10 × 280 = 2800 TFLOPs·ms/s of prefill compute; with prefix routing you spend 10 × 112 = 1120 TFLOPs·ms/s. Free ~2.5x prefill capacity. That capacity becomes higher batch, better decode ITL, or fewer replicas.

If cost per H100 hour is ~$3, and prefix routing lets you drop 3 replicas, you save ~$65k/year. From a router.

9. Where this touches your Zoho career story

You already build agentic harnesses at Zoho. Every tool-calling loop is the archetype prefix-heavy workload. Concrete plays that turn this into a promo packet:

  1. Instrument your current traffic. Log prefix-cache hit rate per turn. Publish an internal doc: “Zoho agentic traffic is 68% prefix-cache-reusable — here’s the money.”

  2. Deploy SGLang + cache-aware router on the on-prem inference plane for one product. Measure TTFT before/after. This is a 2-week project with a graph a VP can read.

  3. Own the router as a service — separate microservice, its own SLO, its own metrics, versioned like any other component of the platform. This is precisely where your services-engineer instincts convert into “inference infra staff” credentials.

10. Exercises

  1. Implement a toy prefix-hash router in ~100 lines of Python: 4 fake replicas, each with a set of block hashes; router picks longest match with queue_depth < 8 tiebreak. Simulate 10k requests from a ShareGPT-like distribution and plot hit rate vs. random routing.

  2. Read the SGLang RadixAttention paper (arxiv 2501.12948) and match its RadixCache implementation in the SGLang repo to the paper’s algorithm — write a 500-word explanation.

  3. Reproduce section 5 of the LMCache blog post: measure TTFT improvement of shared-KV across 2 vLLM instances.

  4. Compare sglang_router and vLLM’s built-in prefix-cache metrics on the same workload. Which reports higher hit rates? Which is closer to ground truth?

11. References

Next: 11_ultra_scale_playbook.md — the HuggingFace Ultra-Scale Playbook guided tour.