KV-Aware Routing for LLM Serving

KV-aware routing can reduce repeated LLM prefill work, but cache affinity alone can send a burst to the busiest worker. This guide builds a deterministic trace simulator that balances scoped prefix reuse against live prefill and decode load, rejects stale or cross-tenant evidence, and exports every placement decision.

Why KV-aware routing needs two signals

KV-aware routing tries to preserve useful prompt state without sending every request to the worker that owns the longest cached prefix. That greedy choice can overload one GPU while idle peers wait. A production policy therefore needs two explicit signals: how much prefill work a cache hit avoids and how much live work a candidate worker already carries.

The decision unit is a request for one exact model revision, adapter set, tenant namespace, and prefix identity. A match outside any of those boundaries is not reusable state. The router should reject it before scoring candidates, rather than treating isolation as a later storage concern. The result is LLM request routing with cache locality constrained by correctness.

This guide uses a seeded trace simulator, not a GPU benchmark. It compares round-robin, least-load, longest-prefix, and a cache-plus-load policy over the same arrivals. It reports recomputed prompt tokens, load skew, a transparent latency proxy, stale-event errors, and tenant-boundary rejections. Those modeled numbers explain policy behavior; they do not predict a particular engine's milliseconds.

Start with the isolation model in prefix cache tenant isolation. That article defines who may reuse state; this one decides which eligible worker should receive the request.

Define the routing event contract

A routing event needs more than a prompt length. Record request ID, arrival tick, tenant, model digest, adapter digest, prefix key, reusable prefix tokens, remaining prefill tokens, expected decode tokens, and a stable sequence number. Worker snapshots need the same identity fields plus queued prefill, active decode, cache entries, cache epochs, and the observation tick.

KV-aware routing becomes reproducible when all time is logical. The lab advances through an ordered trace and breaks equal-time ties by sequence number. It does not read wall-clock time. A bounded simulator can then replay the same fixtures in any browser and produce the same assignments and receipt hash.

Normalize units before combining them. Prefill tokens, decode tokens, and active requests are not interchangeable. The policy in the lab converts each into declared work units, with a decode weight kept visible in the receipt. A real service should calibrate those weights against measured service time for one hardware and software cohort.

Keep events bounded and validate every field. The local artifact accepts at most 64 requests, eight workers, and 8,192 tokens per request. It rejects negative loads, unknown workers, duplicated request IDs, non-integer epochs, and missing namespaces. Silent coercion would turn malformed evidence into a plausible route.

Compute reusable prefix work safely

Prefix-aware routing begins with an independently calculated cache benefit. For each eligible worker, look up the exact namespace tuple and take the smaller of the cached prefix length and request prompt length. Recomputed prefill is prompt tokens minus that reusable amount. A full hit can reduce prefill to zero, but it never removes decode work.

The identity tuple must include the tenant unless sharing was explicitly authorized. It should also include model weights, tokenizer, prompt-template version, adapter, and any other state that changes token meaning. Hash collisions require a full identity check before reuse. The simulator exposes a cross-tenant fixture that would look attractive by prefix length and proves the router rejects it.

Cache events also need monotonic epochs. An insert, eviction, or ownership transfer with an older epoch is stale evidence. The lab drops that mutation and records a stale-event error instead of rewinding cache state. This is important because routing and cache directories often travel through asynchronous control planes.

For eviction mechanics after placement, KV cache eviction by prefixes explains why whole-prefix ownership and partial blocks need separate accounting. KV-aware routing consumes that cache ledger; it should not invent residency from the last request it happened to see.

Score cache benefit against live load

The cache-plus-load policy computes a cost for every eligible worker: recomputed prefill plus weighted decode backlog plus queued prefill plus an optional imbalance penalty. Lowest cost wins; worker ID breaks ties. Each component is emitted, so an operator can reconstruct why a cache-rich but saturated worker lost to a colder peer.

This is deliberately not a universal formula. NVIDIA Dynamo documents a KV-aware routing architecture that coordinates cache events and load information, but an implementation must still choose freshness rules and weights for its own serving stack. The article's model is a compact decision instrument, not a compatible replacement.

Longest-prefix ignores live pressure. Least-load discards reusable work. Round-robin offers a stable baseline but observes neither. Comparing all four on one trace makes failure modes legible: affinity can create a hot worker, while pure balancing can repeatedly pay prompt prefill.

The receipt retains every candidate score, chosen worker, rejection reason, and cache epoch. That audit trail matters more than a single aggregate win because the dangerous errors are often rare boundary events: one stale eviction, one tenant mismatch, or one overloaded affinity target.

Replay four policies on one trace

A fair trace comparison freezes requests, initial worker state, and cache events, then replays each policy from a clean copy. This makes KV cache routing and LLM load balancing explicit peers instead of letting one silently dominate. Never run policies sequentially over shared mutable state. The independent oracle recomputes assignments from the frozen trace and compares canonical ledgers rather than trusting the UI's summary.

The lab reports prompt tokens recomputed, maximum-to-mean load ratio, route churn, cache-hit count, stale-event rejections, and a latency proxy made from queued work. Lower proxy values can reveal a useful tradeoff, but they are not measured latency. Network transfer, kernel scheduling, batching, memory bandwidth, and engine behavior remain outside the model.

Research systems such as SGLang show why structured reuse and runtime scheduling can materially change language-model serving. Another line of work, Mooncake, explores separating prefill and decode resources. Those architectures reinforce the need to name the serving topology before interpreting a routing result.

Keep the seeded trace small enough to inspect manually. One warm-prefix burst, one cold balanced phase, one stale eviction, and one forbidden cross-tenant match reveal more about policy semantics than thousands of opaque synthetic requests.

Read the cache and load Pareto frontier

KV-aware routing should be evaluated as a multi-objective choice. Plot reusable prefix tokens on one axis and live work after assignment on the other. A route is dominated when another eligible worker preserves at least as much reuse while taking no more work, with one strict improvement. Dominated choices need an explicit reason.

The Pareto view prevents a weighted score from hiding the tradeoff. Two teams may select different points because one serves long system prompts and another prioritizes decode tail latency. Both can be rational if their weights, hard limits, and workload are declared.

Add a freshness dimension rather than painting a stale candidate as merely expensive. Cache knowledge older than the permitted observation window should become ineligible or receive a clearly named penalty. A dotted failure point in the figure shows the consequence: apparent reuse is worthless when ownership has already changed.

Integrate this decision with inference gateway live model routing, where admission, fallback, and model revision selection happen before worker placement. The gateway chooses the executable route class; the cache-aware layer chooses a worker inside that class.

Operate routing without leaking tenants

Treat prefix identifiers as sensitive. Raw prompts do not belong in a routing directory, trace export, or dashboard. Use scoped digests, rotate secrets deliberately, and ensure observability cannot join namespaces that execution keeps separate. A debugging convenience that exposes another tenant's prefix is an isolation failure even if the cached tensors never move.

KV-aware routing also needs overload escape hatches. Cap per-worker queued work, reserve capacity for cold traffic, and permit a no-affinity fallback when cache metadata is missing. The system should fail toward recomputation, not toward unauthorized reuse. Record whether each route was a hit, cold fallback, overload escape, or metadata rejection.

Monitor cache-directory lag, rejected stale mutations, cross-tenant candidates, assignment skew, prefill recomputation, and error rate by model cohort. Compare the routing receipt with server-side completion evidence so dropped and retried requests do not disappear from evaluation.

The right throughput target is useful completed work under latency objectives. LLM serving goodput and SLOs provides that outer measurement contract. A router that maximizes cache hits while missing service objectives has optimized the wrong signal.

Validate KV-aware routing before rollout

Begin with an all-candidates oracle on a tiny trace. Recompute reuse, load, eligibility, and weighted cost independently for every request. Assert stable tie-breaking, then randomize input object order without changing the ordered event sequence. The route ledger and receipt digest should remain identical.

Kill negative mutations. Remove tenant scoping and the boundary fixture must fail. Accept an older cache epoch and the stale-event fixture must fail. Ignore decode load and the hot-worker case must change. Share state between policy runs and the clean-replay comparison must detect it. Replace candidate detail with only the chosen worker and export validation must reject the incomplete receipt.

Stage the policy in shadow mode. Log what the new router would choose while the existing router serves traffic, then compare eligibility, predicted work, actual queue delay, time to first token, time per output token, and errors. Move a small cohort only after the event directory and worker telemetry agree within a declared freshness budget.

The defensible result is not “prefix affinity won.” It is a versioned trace showing where reuse outweighed pressure, where load balancing deliberately paid prefill again, which events were rejected, and which production measurements would be required before changing traffic.

Runnable local artifact — The lab models token work on a seeded logical trace; it is not a GPU benchmark and does not predict production latency.

Replay the frozen trace under four policies; inspect candidate reuse, work, stale-event and tenant rejections; export the canonical JSON or CSV receipt.