KV Cache Locality: The Hidden Variable in LLM Serving Costs

KV cache locality is a key variable that separates LLM serving costs. Serving engines like vLLM cache prefill results in GPU memory, and when the same prefix comes in again, they skip prefill and go straight into decode. The problem is that this cache is per-GPU, so if a request goes to a different card, the same work has to be recomputed. Common load balancing methods like round-robin or least-connections don't see this kind of token locality.

The basic metrics also showed a big gap. On CodeLlama 13B, a cache hit was 18ms P50, while a miss was about 500ms. In a stress workload with 8x A100, a 4,000-token system prompt, 30 concurrent users, and a 90% prefix sharing ratio, round-robin stayed at a cache hit rate of 12.5%, P99 TTFT of 6,800ms, and throughput of 36.3 req/s. Under the same conditions, prefix-aware routing achieved a hit rate of 97.5%, P99 TTFT of 1,000ms, and throughput of 44.4 req/s, delivering an 85.3% improvement in tail latency and a 22.3% improvement in throughput.

For a GPU node costing about $10 per hour, a single 8-GPU node could waste $1,200-$1,800 a month just from redundant prefill. Even with the same hardware and the same model, performance and cost effectively differ depending on which GPU a request is routed to.

The effect varies depending on model size, prefix length, and sharing ratio.

• For 8B-class models, total inference is only about 420ms, so the ~10ms routing overhead can eat into the gains.
• For short prefixes under 500 tokens, the ~3ms routing overhead can outweigh the prefill savings.
• For 13B-70B models, prefill cost is large, so the locality effect is pronounced.
• At 70B, the GPU is already compute-saturated, so overall throughput is nearly the same, but cache hit P50 is 1,498ms versus miss P50 of 2,665ms, making the per-request experience very different.
• As the prefix grows to 16K, a cache miss wastes about 400ms of GPU computation.
• The higher the sharing ratio, the more the hit rate of prefix-aware routing rises.

However, pinning prefix affinity too strongly can concentrate traffic on a specific GPU. To address this, a load-aware fallback is used together, which reroutes when a backend's in-flight count exceeds 2x the median, lowering P95 by 36% and P99 by 45% at the cost of sacrificing about 5 points of cache hit rate. When there's no learned route, a consistent hash fallback keeps the same prefix pinned to the same GPU.

In operations, you should first measure current locality using a Prometheus metric like vllm:gpu_prefix_cache_hit_rate. A hit rate of 80% or higher is already considered efficient, while 30% or below is a signal that the load balancing method is causing significant redundant prefill.