Your Load Balancer Deletes the Prefix Cache on Every Agent Turn

You stood up your own inference. Two reasons usually: the hosted bill got scary at your volume, or you needed a model and a context policy the providers do not offer. You put eight replicas of a 32B model behind a Kubernetes service, turned on automatic prefix caching in the engine, pointed your agent at the gateway, and waited for the cost graph to bend.

It barely moved. The per-engine cache hit rate on each pod reads healthy in the dashboard, maybe seventy percent. And yet every agent turn still feels like a cold start: the time to first token is as slow as day one, and the token accounting shows you are prefilling the full context on turn after turn. Nothing is broken. The cache is doing exactly what it promises. The problem is one layer up, in the thing deciding which replica gets the request.

A multi-turn agent sends almost the same enormous prefix every step, which is the entire premise of structuring prompts so the provider reuses its KV cache. That reuse only happens if the request reaches the process that holds the cache. Your load balancer does not know that. It spreads turns evenly, and even spreading is the one thing that guarantees the cache is never where the request lands.

The business problem: the cache is per replica, the router is blind

Prefix caching is a single-process optimization. The KV cache, the key and value tensors the model produced while reading your prompt, lives in the GPU memory of one serving instance. vLLM's automatic prefix caching design notes put it plainly: the idea is to "cache the kv-cache blocks of processed requests, and reuse these blocks when a new request comes in with the same prefix as previous requests." The reuse is local by construction. Replica A built its cache from the requests A happened to serve. Replica B has a completely different set of blocks. Neither can read the other's GPU memory.

Now put an agent on top. Turn one of a conversation carries a 15,000-token prefix and lands on replica A, which prefills it and caches the blocks. Turn two carries the same 15,000 tokens plus a few hundred new ones. If turn two lands on A again, A reads the shared prefix from cache and prefills only the new tokens. If it lands on B, B has never seen this conversation, so it prefills all 15,000 tokens from scratch and you pay full prefill latency and full compute for work A already did.

A round-robin or least-connections balancer picks the replica by load, not by content. Across eight replicas, the odds that turn two lands back on A are about one in eight. So seven times out of eight, your carefully cached prefix is useless, and the per-engine hit rate you see in the dashboard is measuring the wrong thing. Each engine is caching fine; the fleet is throwing the cache away at the door. The llm-d team describes the failure in one sentence: standard load balancers "naively spread traffic evenly using cache-blind metrics, scattering related requests across different pods and destroying cache locality," which forces expensive recomputation of the prefix.

This is the inference-layer cousin of a problem the stateless MCP work solved at the protocol layer. There the fix was to make any replica able to serve any request so a round-robin balancer is safe. Here the request can genuinely run on any replica, correctness is never at risk, but routing blind still costs you the cache every time. Statelessness makes round-robin correct; it does not make it cheap.

What prefix caching actually buys you, and where

It helps to be precise about what the cache saves, because that is exactly what a bad router throws away. A model serves a request in two phases. Prefill reads the entire prompt and builds the KV cache for it; this is compute-bound and scales with prompt length. Decode generates tokens one at a time from that cache. For an agent whose prompt is huge and whose new output each turn is small, prefill dominates the wall clock and a large share of the cost.

A prefix cache hit lets the engine skip prefill for the shared span. On an agent loop that resends a 15,000-token context thirty times, the difference between hitting and missing that cache is the difference between prefilling 450,000 tokens over the run and prefilling roughly 15,000 once plus the small deltas. That is why the numbers people quote are not subtle. The vLLM integration docs for llm-d report prefix-aware routing delivering "3x higher output throughput" and "2x faster TTFT" against plain round-robin on Llama 3.1 70B, and llm-d's own benchmark on eight vLLM pods reports precise cache-aware scheduling running far faster at P90 time to first token than a cache-blind scheduler on the same hardware.

Two things are worth internalizing. First, prefix caching never changes the output; vLLM notes it "won't change model outputs," so this is a pure cost and latency lever with no quality risk, the same property that makes provider-side prompt caching safe to turn on everywhere. Second, the whole benefit is conditional on locality. The cache is real, the savings are real, and both evaporate if the request does not reach the memory that holds them.

Why round-robin throws it all away

Here is a cache-blind router in a dozen lines. It is correct, it balances load beautifully, and it is the reason your bill did not move.

# Cache-blind: pick the least loaded replica. Correct, and terrible for cache.
import itertools

replicas = ["pod-a", "pod-b", "pod-c", "pod-d",
            "pod-e", "pod-f", "pod-g", "pod-h"]
rr = itertools.cycle(replicas)

def route(request) -> str:
    # Nothing here looks at what the request contains.
    # Turn 2 of a conversation is as likely to move as to stay.
    return next(rr)

Every turn is an independent coin flip over eight pods. The router has the one piece of information that matters, the prefix of the request, and it ignores it. Contrast that with a router that hashes the stable prefix and sends matching prefixes to the same place. Consistent hashing on the conversation prefix is the crude version of the right idea.

# Prefix-affinity by consistent hashing on the stable prefix.
# Same prefix lands on the same replica, so its KV cache gets reused.
import hashlib

def prefix_key(request) -> bytes:
    # Hash the part that is identical across turns: system prompt,
    # tool schemas, and the conversation so far up to the newest turn.
    stable = request.system + request.tools + request.history_except_last
    return hashlib.sha256(stable.encode()).digest()

def route(request, ring) -> str:
    # ring maps hash slots to replicas; neighbours on the ring absorb
    # a pod loss without reshuffling every key.
    return ring.lookup(prefix_key(request))

This already recovers most of the cache, because consecutive turns share a prefix and therefore a key. But pure hashing is brittle in two ways the production schedulers fix. It ignores load, so a hot conversation can pin a pod while others idle, and it treats the prefix as all-or-nothing when real requests share partial prefixes. The better approach is to score, not hash. This is a different lever from routing whole sessions to the cheapest capable model: model routing picks which model answers, cache-aware routing picks which replica of that model answers, and the two sit at different layers of the same stack.

The fix: route on the prefix, not just on load

The production answer is a scheduler that scores each candidate replica on two axes at once: how much of this request's prefix it already holds in cache, and how loaded it is. llm-d's inference scheduler is built on the Inference Gateway Endpoint Picker Protocol and, in its words, makes decisions with "P/D-, KV-cache-, SLA-, and load-awareness," running filtering and scoring algorithms over operational telemetry so you can add your own scorers.

There are two ways to know what a replica has cached, and the difference matters. The approximate mode predicts cache locality from traffic history: it assumes that if a prefix went to a replica recently, that replica probably still has it. It needs no cooperation from the engine and is the sensible default. The precise mode reads the truth: it subscribes to the engine's KV-cache events, so the scheduler knows the actual cached blocks on each replica "based on vLLM KV-Events data" and picks the real best holder. Precise costs you an event stream and some coordination; in return llm-d's benchmark shows it beating the approximate scheduler substantially at the tail, because prediction is wrong often enough at scale to matter.

You rarely write this scheduler yourself. You turn it on. The llm-d and vLLM guidance is to start by adding prefix-aware routing over an existing vLLM pool before reaching for disaggregation or wide parallelism, because the routing change is the cheapest large win. Conceptually the gateway config is a scorer with a weight.

# Inference gateway scheduler: weight cache locality alongside load.
# The scheduler scores every replica and picks the best combined score.
scheduler:
  scorers:
    - name: prefix-cache-affinity   # how much of the prefix this pod holds
      mode: precise                 # subscribe to engine KV-cache events
      weight: 0.7
    - name: queue-depth             # keep a hot pod from melting
      weight: 0.3
  # A request with a long cached prefix prefers its holder, but a badly
  # overloaded holder yields to a cooler pod rather than tipping over.

The weights are the whole design conversation. Push cache affinity too hard and one popular prefix hot-spots a single replica. Push load too hard and you are back to round-robin. The point is that both signals are now on the table, which they never were with a cache-blind balancer.

Session-aware routing and turn priority for agents

Agents stress this further than chat does, and the newest work is aimed squarely at them. On 2026-10-20 the llm-d project shipped its 1.0 release with what it calls agent-aware serving: "session-aware routing keeps multi-turn conversations close to their cached context," plus turn-priority scheduling that, with native Responses API state support, helps agents reuse context across turns and cut recomputation. The release claims up to five to ten times cost reductions for context-heavy agentic workloads, which is a vendor figure on vendor benchmarks, so treat the magnitude as a ceiling rather than a promise.

Two agent-specific details are worth lingering on. First, turn priority exists because agent traffic is bursty and uneven: a long autonomous run issues many turns back to back, while an interactive user waits on one. A fairness-aware scheduler lets a latency-sensitive turn share a fleet with a bursty background run without the background run starving it, which is the scheduling version of the backpressure and concurrency control an agent fleet needs anyway once runs get long. Second, session awareness and cache affinity reinforce each other: keeping a session's turns together is the easiest way to keep its prefix cached, so the routing policy that is good for latency is also the one that is good for cost.

None of this removes the prompt discipline. If your agent rewrites earlier messages, injects a fresh timestamp into the system prompt, or reorders tool schemas between turns, the prefix bytes change and no router on earth can find a cache for a prefix that no longer exists. Cache-aware routing assumes a stable prefix exists to route on. It is the second half of a contract whose first half is building a prefix worth caching.

The parts that bite

Routing on the cache is a clear win, but it is not free of edges, and naming them saves you a confusing week.

Hot prefixes concentrate load. The moment you route on cache affinity, every request that shares a popular system prompt wants the same replica. A shared base prompt across all tenants can funnel a huge fraction of traffic to one pod. The scorer's load term is what saves you, but you have to tune it and watch for a single replica sitting at high utilization while others idle.

The precise path needs the engine to cooperate. Reading real cache state means consuming KV-cache events from every replica, and that event stream is one more thing that can lag, drop, or get out of sync during a deploy. When it is stale, the scheduler routes to a replica that evicted the blocks a second ago and you take a silent miss. This is exactly the kind of gap that only shows up in production, which is why you want tracing that records the routed replica and the resulting cache hit on every call, not just an aggregate dashboard.

Routing fights model switching. Cache-aware routing keeps a session on a replica to preserve its prefix; a cost router that re-picks the model every turn abandons that warm prefix and pays a cold write. The two policies have to agree: route a whole session to one model and one replica, or accept that every switch is a cold start. Decide this deliberately rather than letting two independent routers thrash against each other.

Measure the fleet, not the engine. The trap that started this essay is a per-engine hit rate that looks fine while the fleet-wide rate is terrible. Instrument the number that matters: of the prefix tokens this request carried, how many were served from cache after routing.

# The number that tells the truth: fleet-wide cached-prefix fraction.
# Emit per request from the engine response, aggregate across all replicas.
def cached_fraction(usage) -> float:
    prefix = usage.cached_prefix_tokens + usage.computed_prefix_tokens
    return usage.cached_prefix_tokens / prefix if prefix else 0.0

# Alert when the FLEET value drops, even if every pod's local rate is high:
# that gap is the router scattering turns, not the cache failing.

Watch that value before and after you enable cache-aware routing. If the per-pod rate was always healthy and only the fleet value jumps when you turn routing on, you have found exactly the money a cache-blind balancer was burning.

The takeaway

Prefix caching is a promise the engine keeps and the router can break. The cache lives in one replica's memory, an agent resends the same prefix every turn, and a load balancer that spreads traffic evenly is, with mathematical reliability, sending each turn to a replica that cannot use the cache the last turn built. The hit rate on each engine looks fine the whole time, which is why this hides so well. The fix is to let the layer that chooses the replica see the one thing it needs: how much of this request's prefix each replica already holds, balanced against how loaded that replica is.

If you run your own inference, turn on prefix-cache-aware routing before you reach for any heavier optimization, start with the approximate mode, move to the precise mode once you can feed it engine cache events, and measure the fleet-wide cached fraction rather than the per-pod rate so the win is visible. If your self-hosted inference bill is not falling the way prefix caching promised, the gap is usually in the router, not the model, and finding it is the kind of production cost work I help teams get right in a short, focused session.