DEV Community

Shridhar Shah
Shridhar Shah

Posted on

Your Load Balancer Is Throwing Away the KV Cache

#llm #go #architecture #machinelearning

Round-robin is prefix-blind. KV-cache-aware routing sends requests to the replica that already prefilled their prefix — cutting time-to-first-token without hotspotting.

TL;DR: Before an LLM emits a token it must prefill the whole prompt into a KV cache — the expensive part. In 2026, requests share massive prefixes (system prompts, retrieved documents, the conversation so far). A round-robin load balancer is prefix-blind: it scatters those requests so every replica recomputes the same prefix. KV-cache-aware routing sends a request to the replica that already has its prefix warm. In a tiny Go demo it lifted cache hits from 47% to 85%, recomputed 66% fewer prefill tokens, and halved p50 TTFT — while keeping load far more even than naïve affinity. No GPU: latencies are simulated.

Mental model: a coffee shop that routes you to the barista who already knows your usual. Same regular → same barista → they start immediately. A round-robin queue sends you to a random barista who takes your whole order from scratch every time.

The problem: prefill is expensive and prefixes repeat

An LLM request has two phases: prefill (read the whole prompt into the KV cache) and decode (generate tokens). Prefill dominates time-to-first-token, and it scales with prompt length.

Here's the thing about agent traffic: prompts are mostly shared prefix. The same 2,000-token system prompt. The same retrieved document. The same conversation history, turn after turn. If a replica already prefilled that prefix, its KV cache can be reused and the prefix is essentially free. A round-robin balancer throws that away — it spreads requests evenly and blindly, so the hot prefix gets recomputed on all four replicas instead of once.

The pattern: route by prefix affinity, but balance load

Three routers, same request stream:

Round-robin — perfect load spread, zero cache awareness:

func roundRobin(_ []*replica, _ request, seq int) int { return seq % replicas }
Enter fullscreen mode Exit fullscreen mode

Prefix-affinity — same prefix always lands on the same replica, so caches stay warm. But a hot prefix now hammers one replica:

func prefixAffinity(_ []*replica, req request, _ int) int {
    h := fnv.New32a()
    fmt.Fprintf(h, "%d", req.prefix)
    return int(h.Sum32()) % replicas
}
Enter fullscreen mode Exit fullscreen mode

Cache-aware + balanced — the 2026 endpoint-picker idea (llm-d / Gateway API Inference Extension): prefer a replica that already has the prefix warm, but spill to the least-loaded replica if the warm one is slammed. Locality first, then balance:

// warm replica exists and isn't overloaded -> reuse its cache
if best != -1 && float64(reps[best].load) <= avg*overloadFactor {
    return best
}
// otherwise send it to the least-loaded replica
return leastLoaded(reps)
Enter fullscreen mode Exit fullscreen mode

Time-to-first-token in the sim rewards a warm hit by skipping the prefix prefill:

prefill := req.suffixTokens          // the unique tail always needs prefill
if !r.has(req.prefix) {
    prefill += req.prefixTokens      // cold: pay to prefill the whole prefix
}
ttft := decodeBase + float64(prefill)*prefillPerTok
Enter fullscreen mode Exit fullscreen mode

The result 

KV-cache-aware routing — reuse warm prefixes instead of recomputing them
  2000 requests, 4 replicas, 40 distinct prefixes (traffic skewed to the hot few)

   router                    hit rate   prefill work    p50 TTFT   load skew
   round-robin                  46.6%   2,809,330 tok       61ms        1.0x
   prefix-affinity              86.0%     893,365 tok       30ms        1.8x
   cache-aware + balanced       84.8%     957,709 tok       30ms        1.2x
Enter fullscreen mode Exit fullscreen mode

Round-robin has perfect balance (1.0x) but the worst cache behaviour. Blind affinity gets the cache hits but a 1.8x load skew — one replica does nearly twice the work of another. Cache-aware + balanced keeps ~85% of the hits and a gentle 1.2x skew. That's the sweet spot.

Reality check: these are simulated latencies, not a GPU benchmark — directional only. The tradeoff is real: production KV-aware routers (SGLang's RadixAttention, llm-d / Gateway API's endpoint picker) report large TTFT and throughput gains from exactly this locality-vs-load balance, and how big the win is depends entirely on how much prefix your traffic actually shares.

Why this is where 2026 is heading

The proven part: prefix / prompt caching is already GA across major providers and inference engines (vLLM, SGLang, TensorRT-LLM), and it's a real discount. The open question was always routing — caching only helps if the request lands where the cache lives.

Where it's heading: 2026 inference stacks make the router KV-cache-aware. The Gateway API Inference Extension's endpoint picker (EPP) and llm-d schedule replicas by KV-cache locality and load together — exactly the third router here. As context windows grow and agents replay long histories, where you route becomes as important as what model you route to.

How faithful is this demo?

It's a simulation of serving behaviour, not a GPU benchmark: latencies are a linear tokens × cost model and the cache is a per-replica LRU of whole prefixes. Real systems match on prefix blocks (shared leading tokens), evict at block granularity, and factor in queue depth and memory pressure — but the qualitative result (affinity wins big, blind affinity hotspots, locality-plus-balance is the sweet spot) is exactly what production routers target. The sharp edge to watch: a single very hot prefix can still overwhelm the one replica that caches it, so the router must be willing to trade cache reuse for load — spill to a colder replica under pressure — or you simply swap recompute cost for queueing latency.

When not to use this

  • Your prompts share little prefix. Short, unique requests get almost no cache reuse, so affinity routing buys nothing and just adds complexity.
  • You run a single replica. There's no routing decision to make.
  • Autoscaling is aggressive. Sticky, cache-aware routing fights elastic scale-in/out; you'll need to weigh cache locality against how often replicas churn.

Try it 

go run .   # standard library only
Enter fullscreen mode Exit fullscreen mode

Sources & further reading

Papers

Engineering blogs & docs

Top comments (0)