When routing on cache locality backfires
September 2026
When an LLM server processes a prompt, it builds a KV cache for every token. If the next request starts with the same long prefix, say the same system prompt or the same document, a server that still has that cache can skip most of the work. So a simple idea: route each request to whichever server already has its prefix cached.
I built CachePilot to find out how much that helps, and more importantly, when it stops helping. It's a gateway that fingerprints each prompt's prefix, keeps a directory of which worker holds what, and records every routing decision so it can be replayed and explained.
When it works
On a simulation of three continuous-batching workers at 20 requests per second, with traffic that shares a lot of prefixes, routing on cache locality cut median time to first token by 81% and raised throughput 18% compared to round robin. Once workers are saturated, every cache hit is compute the engine gets back, so locality becomes a throughput lever and not just a latency one.
An unexpected win was evictions. With round robin, every worker churns through every prefix. With locality, workers specialize, and evictions dropped 42%.
When it backfires
Then I turned off the load terms and routed on cache overlap alone. The first request for a prefix pins it to one worker, and every later request follows it there. On a workload where a few prefixes are very popular, that worker took all the traffic. Load imbalance hit 3.0, the worst possible with three workers, and median time to first token went from 219 ms to 35 seconds.
The fix is to price load in the same units as the cache benefit. CachePilot's router scores each worker as cache overlap minus queue load, KV memory pressure, and predicted time to first token. Because the queue is priced in milliseconds, the router backs off a hot worker as its queue grows, and imbalance stays around 1.05.
Things I didn't expect
- The weights matter less than the random seed. Seed-to-seed variance was bigger than most weight changes.
- Only one weight really mattered: how much to penalize load. Its best value flipped between bursty traffic and tight hotspots.
- The gateway's guess about what's cached held up on a real model. On a laptop running Qwen2.5-0.5B, requests the gateway predicted as hits had a median time to first token of 204 ms, against 400 ms for predicted misses.
All the multi-worker numbers here are from simulation; only the last one is from a real model. The takeaway still holds: cache affinity is a great tiebreaker and a terrible sole objective.