What is prefix-aware routing for LLM serving, and when is it worth building?
- 5 min — how per-replica prefix caching works
- 10 min — why round-robin kills hit rate; routing options
- 10 min — balancing, hot spots, stale state
- 10 min — estimate prefill savings
- 5 min — isolation, adopt vs build
Engines cache KV for prompt prefixes — vLLM's automatic prefix caching hashes 16-token blocks; SGLang's RadixAttention keeps a radix tree. The cache is per replica. Round-robin across N replicas gives a conversation's next turn a ~1/N chance of landing where its prefix lives. Prefix-aware routing sends the request to the replica that holds the longest matching prefix, balanced against load. Options as of Oct 2026: SGLang's cache-aware router, NVIDIA Dynamo's KV-aware router, llm-d's scheduler on the Kubernetes Gateway API Inference Extension, or consistent hashing with bounded loads.
Multi-turn assistant: key on hash(system-prompt id + conversation id) for conversation affinity; for system prompts shared across users, key on the first K blocks. The router keeps an approximate map of replica → recent prefix hashes, fed by engine KV events, and scores each replica as overlap × w − load × v; if the best replica's queue exceeds a threshold, spill to the least-loaded one.
- Affinity vs balance. Pure hashing hot-spots one replica on a viral app's system prompt; use bounded-load consistent hashing (cap at ~1.25× mean) and replicate hot prefixes to k replicas.
- Measure: cached-token hit rate, TTFT p50/p95, load imbalance (max/mean queue), spill rate.
- Failure modes: replica restarts wipe caches and trigger rebalancing storms; routing on stale state; dynamic content (timestamps, user names) at the top of the system prompt breaking every match.
- Isolation: cache hits are faster, which is a timing side channel across tenants — salt block hashes with tenant id for sensitive tenants.
- Worth it when: multi-turn or long shared prefixes (agents, RAG with fixed instructions), more than ~8 replicas, and prefill a large share of GPU time. Adopt an open-source router before building one.
Assumptions: 70B FP8, 32 replicas; 200 turns/s; average context 10k tokens, 500 new per turn; prefill ~7k tok/s per H100 (≈1.4e11 FLOPs/token at ~1e15 effective FLOP/s, ~50% of FP8 peak); illustrative $2.50/H100-hour.
- No reuse: 200 × 10k = 2M prefill tok/s → ~285 H100s for prefill alone.
- Round-robin: hit chance ≈ 1/32 → still ~280 GPUs.
- Prefix-aware at 85% hits: 0.85 × 200 × 500 + 0.15 × 200 × 10k = 85k + 300k = 385k tok/s → ~55 H100s.
- Saving: ~225 GPUs × 730 × $2.50 ≈ $410k/month, and TTFT on hits drops from ~1.4 s to 0.1–0.3 s — for a router that costs a few engineer-months.
What the answer sounds like at each level
Knows prefix caching reuses KV for repeated prompt starts.
Explains why round-robin defeats per-replica caches and routes by prefix hash with load balancing.
Quantifies prefill GPUs saved, handles hot spots and tenant side channels, and decides adopt-vs-build with the measurement plan.
Follow-ups the interviewer will push
1Hit rate is 40%; you expected 80%.
Check eviction under KV pressure, unstable prefixes (dynamic content at the top of the prompt — move it to the end), and the router's spill rate.
2A tenant raises isolation concerns.
Salt that tenant's block hashes so it never shares cache entries; it costs hit rate only on prefixes shared across tenants.
3You disaggregate prefill and decode.
Routing becomes two decisions: prefix-aware to a prefill worker, then KV transfer (RDMA, e.g. NIXL) to a decode worker chosen by load.
Red flags interviewers listen for
- Assumes the prefix cache works across replicas automatically.
- Pure hashing with no load bound.
- Puts timestamps or user names at the start of the system prompt.
- Builds a router before measuring prefill share.
How it's scored
| Dimension | What strong looks like |
|---|---|
| Mechanism | Block hashing / radix tree, per-replica scope, why round-robin fails. |
| Balance | Bounded load, hot-prefix replication, spill rules. |
| Estimation | Prefill tokens/s with and without routing translated to GPUs and $. |
| Security | Identifies cross-tenant timing side channel and mitigation. |
Sources
- SGLang: Efficient Execution of Structured Language Model Programs — Zheng et al., 2023paper
- Efficient Memory Management for Large Language Model Serving with PagedAttention — Kwon et al., 2023paper