What is KV-cache-aware routing?

KV-cache-aware routing is a scheduling policy for LLM serving fleets. Instead of sending each request to the next replica, the router checks which worker already has useful prefix state in GPU memory and prefers that worker, subject to load, health, memory pressure, and batching impact.

Why does round-robin routing reduce prefix cache hits?

Round-robin spreads successive turns of the same conversation across different replicas. Since a replica’s KV cache is local to that worker unless explicitly transferred or replicated, the next turn often lands somewhere that does not hold the previous prefix, forcing prefill work that could have been avoided.

Should all repeat prompts be routed to the same replica?

No. Locality is only useful while its savings exceed queueing, imbalance, transfer, fragmentation, and batching costs. A very popular prompt may need deliberate replication across workers, while low-reuse traffic may be better served by load-based routing with short affinity lifetimes.

The Fleet

06.07 · Walkthrough

Routing Requests

Route across replicas by KV-cache locality and session affinity, and explain why plain round-robin destroys the prefix hit rate the KV cache module worked to build.

KV-cache-aware routing sends an inference request to the replica most likely to reuse its existing prefix state, while session affinity keeps continuing conversations near their cached context. Plain round-robin treats workers as identical, so multi-turn traffic repeatedly misses warm prefixes, wastes prefill work, and erodes the latency gains the cache was meant to provide.

What this lesson answers

how to route requests by KV cache locality
why round robin hurts LLM prefix caching
when should session affinity be broken

Notes

KV-locality routing is the scheduler policy that sends a request to the replica already holding the largest useful prefix of that request in GPU KV cache, rather than treating replicas as interchangeable. For a request with tokenized prefix $x_{1 : n}$ and replica $r$ caching a set of prefixes $C_{r}$ , the routing score is typically $s (r) = max_{p \in C_{r}} lcp (x_{1 : n}, p) - λ q_{r} - μ m_{r}$ , where $lcp$ is the longest common prefix length, $q_{r}$ is queue cost, and $m_{r}$ is a memory-pressure penalty.

References

llm-d: Distributed inference serving on Kubernetes

Common questions

What is KV-cache-aware routing?: KV-cache-aware routing is a scheduling policy for LLM serving fleets. Instead of sending each request to the next replica, the router checks which worker already has useful prefix state in GPU memory and prefers that worker, subject to load, health, memory pressure, and batching impact.
Why does round-robin routing reduce prefix cache hits?: Round-robin spreads successive turns of the same conversation across different replicas. Since a replica’s KV cache is local to that worker unless explicitly transferred or replicated, the next turn often lands somewhere that does not hold the previous prefix, forcing prefill work that could have been avoided.
Should all repeat prompts be routed to the same replica?: No. Locality is only useful while its savings exceed queueing, imbalance, transfer, fragmentation, and batching costs. A very popular prompt may need deliberate replication across workers, while low-reuse traffic may be better served by load-based routing with short affinity lifetimes.

Short definition: what is Routing Requests?

06.06 · The FleetExpert Parallelism 06.08 · The FleetMulti-Tenancy and LoRA