kvroute

The question

Consistent-hash session affinity is the cheap baseline: hash a conversation's id onto a ring of replicas and every turn of that conversation lands on the same one. It costs almost nothing to build, and it does one thing well — it keeps a conversation's KV cache warm on whichever card served its first turn. What it cannot do is notice that the same hash also piled three hot conversations onto one card while another sits idle.

kvroute adds a belief on top of that: a router-side index of which replica probably still holds which prompt's cache, built from what the router itself sent rather than anything a replica reports back. Route to the believed match, unless that replica is evicting it or buried under load, in which case decline the match and send the turn to whichever replica is least loaded — which then caches it too. That is the whole mechanism. The deliverable is measuring what it buys and where it stops buying anything, not shipping it as a service.

• In — a stream of multi-turn chat requests with a controllable working set (memory pressure) and skew (load imbalance)
• Out — goodput per policy inside one derived SLO, with the run-to-run spread published beside it
• Between — a Go router that is the sole ingress, six routing policies, two load drivers (closed loop and open loop), per-request rows that are the system of record

The fleet and the ruler

The fleet is five RTX 3090s, not six. GPU 3 throttles on heat rather than the normal equal power cap — it reports software thermal slowdown on 67% of samples against 0–34% for the others, clocking down to 960 MHz at 75°C while an 83°C card elsewhere holds 1,305 MHz. A permanently slow card is a permanent load imbalance, which is exactly the mechanism under test, so it is excluded rather than averaged in.

The SLO — TTFT < 990 ms and inter-token p50 < 24 ms — is derived, not chosen: it is 3× the measured latency floor (TTFT p50 329 ms, inter-token p50 7.8 ms, over 1,487 requests at concurrency 1, straight at each replica). Every policy at a given load point sends identical bytes; the comparison tooling refuses to put two policies' cells in one table if their workload names differ. The fleet is cycled down and back up between every policy, because prefix caching means a second pass would read back what the first prefilled — unseen prompts land at TTFT p50 ~325 ms against ~46 ms for the same prompts re-sent, a sevenfold head start that would otherwise go to whichever policy happened to run second.

Every figure is the median of three repetitions with the range published beside it; a difference smaller than that range is called within spread rather than a result. Every cell also carries its own nvidia-smi evidence, because the box is shared — a cell that saw a foreign process on any card is discarded and re-run rather than averaged in.

make figures        # six figures + their data, from docs/measurements
make figures-test   # the plotting script's tests
make test            # the full Go suite under the race detector

Where cache-aware routing pays

Cache-aware routing (prefix affinity) beats session affinity at 11 of the 12 points on this grid — working set ratio against the fleet's measured KV capacity, crossed with Zipf skew. At the frozen comparison point, working set 1 / skew 0, it wins by +66.2%, and the two policies' repetition ranges do not overlap: session affinity's best run sits below prefix affinity's worst.

The one exception is the low-pressure corner, working set 0.25 / skew 0, where prefix affinity is 6.8% below session affinity — within spread, not a result. The whole working set fits in cache there, so there is no imbalance to fix: every spill just sends a turn to a replica that does not already hold it, a pure cost with no offsetting gain.

Two cells on this map rest on two repetitions rather than three. At working set 0.25 / skew 1 (+289.8%), one session-affinity repetition drifted on warm-up, was re-run, and drifted harder; at working set 3 / skew 1 (+51.4%, published as +41.3% before a rebuilt drift check set one repetition aside as a cold opening), the same thing happened from a different cause. Both points separate either way — the smaller repetition's best case still loses to the larger repetition's worst — but their sizes are the least resolved numbers in the map.

The mechanism is load, not cache reuse

Between the two affinity policies, the prefix cache hit rate differs by only 0.0–2.2 percentage points at every point of the grid — hit rate is not what separates them. What separates them is load: session affinity hashes a conversation onto one replica and keeps it there, so concentrated traffic piles onto whichever card the hash favours. Prefix affinity's spill rule notices an overloaded conversation and moves one of its turns to a less-loaded replica, which then caches it too — so the match ties across both cards, and the tie goes to the least loaded.

A second arm proves the rule matters rather than just correlating with the result: running prefix affinity with the spill rule switched off across the same grid loses 5–51% of its goodput at 11 of 12 points, and pins each hot conversation to about one replica, just as session affinity's hash does. With the rule on, the busiest replica sits at fair share — 21–22% — everywhere. A rule that fires on only 0.2–2.5% of routing decisions accounts for up to a doubling of goodput.

Who wins where

The pressure map above says where prefix affinity beats session affinity and by how much; it does not yet say which of the four policies — round robin, least outstanding, session affinity, prefix affinity — wins at each point of the grid, plotted as one map of winners rather than one policy's margin over another. Prefix affinity wins 11 of the 12 points beyond the spread. The twelfth is the low-pressure corner already flagged above, working set 0.25 / skew 0, where session affinity is +7.3% ahead of it — within spread, not a result.

The map's news is the runner-up, not the winner. At skew 0 and skew 1, for every working set ratio of 1 or more, the second-place policy is session affinity — stickiness is still the next-best thing to do. At skew 1.4 the runner-up is least outstanding instead, and session affinity falls all the way to about round robin's level: working set 1 puts them at 11.23 against 11.22 req/s, working set 3 at 6.44 against 11.23, working set 8 at 10.69 against 10.21. A policy that pins a conversation to one replica by hash stops being worth anything once that hash also pins the busiest conversations to the same few replicas. At working set 0.25 the same flip happens a column earlier, at skew 1 rather than skew 1.4: least outstanding already beats session affinity there, 17.84 against 8.83 req/s.

So stickiness alone — a consistent hash with no notion of what is cached — is worth about twice round robin's goodput under even traffic, and worth nothing, or worse than nothing, once traffic skews: a load balancer that has never heard of a KV cache beats the session hash by two to three times over in that regime. Prefix affinity is the only policy that is best or tied everywhere on this grid, because its spill rule gives it both properties at once — affinity when nothing is overloaded, load balancing the moment something is. No point on the map contests it beyond the spread, which is exactly why the adaptive-router idea in the last section has no region left to work in on these two axes: there is nowhere for a policy switch to win that prefix affinity does not already hold.

Knowing what is cached loses to remembering what was sent

Stack four policies by how much they know about which replica holds which cache: nothing (a stateless hash of the prompt's leading blocks, weighed against replica load), a belief (the router's own index of what it sent, aged by a calibrated TTL), and a fact (the engines' own KV cache events). The intuitive ordering is none < believed < exact. The measured one is none < exact < believed.

The stateless hash — no index, no session state, just a hash of the prompt's leading blocks combined with inflight — already buys most of what cache-aware routing is worth: the believed index beats it by +5.4% to +25.2% of goodput (median +11.0%) at the 11 of 12 points where the two separate at all. Exact residency, built to know more than the belief by asking an engine what it actually holds, instead does worse than the belief it was meant to replace: it sits 4.6–13.5% below the believed index at 11 of 12 usable points.

Two things cause that, and only one was expected. Asking an engine to tokenize every prompt before routing it costs 26.0 ms p50, against the believed index's 0.38 ms of total router overhead — a quarter of this fleet's TTFT budget spent before anything is routed. That round-trip does not explain the larger part of the gap, though: exact residency also reaches a lower cache hit rate than the belief (0.8973 against 0.9088) and makes the engines compute 12.7% more new tokens per request. The index records what the router sent, so several requests that arrive together sharing a new prefix get herded onto the one replica the router already committed to; exact residency knows only what has been reported back, so those same requests scatter across replicas while the first one is still prefilling, and the same prefix gets computed more than once. The deficit is twice as large on first turns, which arrive concurrently, as on later ones, which do not.

That is narrower than "beliefs beat facts", and llm-d measured the opposite: its event-fed precise index beat its approximate one, P90 TTFT 0.542 s against 31.083 s (2025-09-24). Two things differ. Exact residency here pays the 26 ms tokenize round trip, and it has nothing like llm-d's optional speculative indexing, which also records what the router just sent for 2 s — the belief, layered on the facts. So what this measured is that an event-fed index without that layer loses; an exact index with it was not measured here.

How wrong the index is, and how fast

Every request the router handles carries both sides of one claim: the prefix match the router decided on, and the engine's own record of what it actually had cached for that request. Over 19,391 requests of a clean working-set run, 99.7% of the tokens the index claimed were really there. The errors run the safe way — 17,845 requests under-predicted against 1,531 that over-predicted — and the two are never netted into one figure, because they cost differently: forgetting a block a replica still holds only forfeits a match, while believing in a block that has been evicted pays the full prefill and spends the routing decision on a reason that had already stopped being true.

Memory pressure does not make the index wrong more often — the count of over-predicting requests falls monotonically as working set rises (951, 317, 169, 94 across working set 0.25 / 1 / 3 / 8) — it makes the index wrong in bigger pieces: the mean over-prediction jumps eightyfold between working set 0.25 and working set 1 and then holds flat. A fleet that cannot hold its working set does not produce more stale beliefs; it produces stale beliefs that are worth more when they land.

The belief also decays with time, measured directly: honoured share holds at 99.8% for requests 1–2 s after a session was last served, falls to 86.0% in the 30 s–1 m bucket — just beneath the fleet's own measured 57 s eviction TTL — and recovers to 98.1% past it. That measurement then sizes the index itself: its node cap is the fleet model scaled by the share of belief the engines actually honoured, which trimmed it by 0.3% (16,311 → 16,258).

What breaks, and what it costs

Kill one replica under steady load — SIGKILL, mid-request, no warning — and restart it 60 s later. Both session affinity and prefix affinity (spill off) held 5.98 requests/second before the fault and lost exactly one request of 1,501: the one that was mid-stream when its replica died, which cannot be rerouted. Draining the same replica through the router first, instead of killing it, dropped nothing at all.

The two policies pay at opposite moments. Session affinity is flat through the whole outage — four replicas at 6 req/s is inside what the fleet can serve — and dips only when the replica comes back and the hash ring moves its sessions onto an empty cache. Prefix affinity dips during the outage instead, when the conversations orphaned by the kill land together on one replica: 47% of the load against a 25% fair share among the four survivors. Neither is "better at recovering" from one run each — the pair just shows where each policy's cost falls.

The obvious alternative explanation for any of the goodput numbers on this page is that the router itself added latency the simpler policies did not pay. It did not: router overhead, measured off the router's own per-request rows rather than the client's, runs 217–223 µs p50 across every policy (431–787 µs p99). Consulting the prefix index costs about 160 µs more than hashing a session id — against TTFT p50s of hundreds of milliseconds and a goodput difference of +66%.

Results that overturned themselves

• The project's first headline was an artefact and is withdrawn: on all six cards, balancing load looked like it cost goodput — least outstanding lost 16–32% to round robin. GPU 3 thermally throttles whenever all six cards draw power at once, so round robin was feeding a sacrificial queue that passed nothing while the others passed everything. On five symmetric cards the same pair inverts: least outstanding wins by 100–120%.
• Exact residency — routing on the engines' own KV cache events instead of a belief — was built to beat the believed index and instead loses to it at 11 of 12 usable grid points, by 4.6–13.5% of goodput.
• The warm-up drift check that flags a cell as still speeding up was itself wrong in three ways; rebuilding it moved the verdict on 118 of 216 recorded open-loop cells.
• The spill rule, tuned at 32 closed-loop users where it fires on 0.674% of later turns, fires on 19% of them at 6 req/s open-loop — because it compares inflight counts that are small integers when the fleet holds about 12 requests — and 42% of the turns it spilled there missed the SLO.
• A second branch of the spill rule, meant to decline a match on low cache residency rather than high load, is harmful at every one of the 35 points it was measured against the load branch, so it ships off.

What is new here, and what is not

Cache-aware routing is an active production pattern, not an original idea here. SGLang, NVIDIA Dynamo, llm-d, AIBrix and Mooncake all score replicas by predicted prefix reuse and penalize by load — the same shape as prefix affinity's spill rule, differing mainly in whether the prefix signal is an approximate router-side index or an exact engine-published event stream. OpenAI routes on a hash of the prompt's opening tokens plus machine load, with prompt_cache_key as a hint rather than a pin; vLLM's production-stack router ships session-ID routing, with prefix-aware routing still marked work in progress.

And the specific ablation this project runs — cache-aware routing against consistent-hash session affinity — has already been published, at datacentre scale. Anyscale's Ray Serve LLM (2026-08-25) benchmarked a KV-aware router against a consistent-hash one and found the KV-aware router won on tail latency despite a lower cache hit rate. CacheRoute (arXiv 2608.19677, 2026-08-20) ran sticky consistent hashing against four other baselines on 60 H100s and found affinity can reduce capacity when the recoverable prefix work is small. llm-d (2026-08-17) publishes the numeric threshold at which it abandons stickiness: τ = 286,720 tokens of pending uncached prefill work. So two of this page's findings are reproductions, not discoveries: the win coming from load balance rather than extra cache hits, and pure stickiness having the high hit rate and the low capacity.

The comparison's most likely objection is not yet measured. The session-affinity baseline here has no load bound, while Envoy (hash_balance_factor) and HAProxy (hash-balance-factor) turn on consistent hashing with bounded loads with one setting, and CacheRoute uses it as a baseline. Since the mechanism finding says the win is load, the margins on this page are against load-blind stickiness, not against the best a plain load balancer offers.

• The comparison at single-host, consumer-GPU scale — every published version above runs 8–60 H100/H200-class GPUs with 32B–70B models; this runs one host, six consumer cards, a 4-bit 8B model
• A two-axis pressure map — working-set ratio against measured fleet KV crossed with Zipf skew, memory pressure and load imbalance kept as separate axes because they trip different branches of the spill rule
• Belief divergence per request — the gap between what the router's index claimed and what the engine actually had cached, measured rather than assumed
• A spill threshold that depends on load — tuned at 32 users it fires on 0.674% of later turns, at 6 req/s open-loop on 19%, where llm-d publishes one fixed threshold
• What an index buys over a load-weighted prefix hash, the family OpenAI's default routing belongs to — +11% median goodput
• Where recovery costs land — after a replica kill for session affinity, during it for prefix affinity

What I would do next

• Session affinity with a load bound (consistent hashing with bounded loads) on the pressure grid, at least at the frozen point and the skew-1.4 column — the baseline a plain load balancer actually offers, and the test of whether the index or just the load bound carries the +66%
• Turns per session and prompt length as new grid axes at the frozen centre, four policies — a sweep sized like idea.md's own concurrency grid (4 policies × 8 steps × 3 reps, 96 cells), which its own cost model prices at about 11 GPU-hours
• Prefix affinity on the load axis as a fresh four-policy sweep: the 2026-09-08 sweep cannot be extended, because the comparison tooling refuses cells whose workload name or arrival plan differs from the ones already recorded, and both have changed since
• An adaptive router that switches policy on observed conditions, built only if the regime map above shows a region where a different policy beats prefix affinity by more than the spread — and recorded as a null result if it does not

Stack