Token-Load-Aware Routing for LLM Serving

TL;DR: KV overlap is a proxy for load, not the objective

Most teams route to whichever replica already holds a request's prefix, because reuse is easy to reason about. That instinct is right but incomplete. KV cache overlap is a proxy for cheap prefill; it is not the thing you are actually trying to protect. The thing you are protecting is tail latency, and tail latency dies when token load piles up unevenly across your fleet. Anyscale frames the tradeoff plainly: the challenge is "how to take advantage of KV cache reuse while balancing heterogeneity across engine replicas."

Token-load-aware routing reconciles the two. It scores each candidate replica on prefix overlap and on the token load it is already carrying, then routes to the one that wins on the combined objective rather than on overlap alone.

What token load means on a replica

A replica's token load is the sum of two very different kinds of work. Prefill processes the input prompt in one compute-heavy pass and produces the first token. Decode generates each subsequent token one step at a time, and its throughput scales with how many requests share the batch - as vLLM puts it, "more requests a decode engine serves at once, higher throughput we get."

Those two phases compete for the same GPU. A burst of long-prompt requests floods prefill; a pile of long-generation requests keeps decode slots occupied for minutes. A router that only counts requests-in-flight sees both as "one request" and mis-estimates the real load. Token load is the honest unit because it tracks the work, not the request count.

The tension: overlap vs. imbalance

Routing purely by KV overlap concentrates traffic. If replica A holds the popular system prompt, every matching request wants A - and "routing a request to a replica that already holds its prefix can significantly reduce prefill computation and TTFT." That is real savings. But it is also a hotspot.

When a burst arrives, that concentration bites. Together.ai's account of a coding-agent workload describes it exactly: "prefill capacity and KV cache headroom get exhausted exactly during the burst, which is when it matters most, producing exactly the kind of multi-minute request queuing that agentic coding workflows can't tolerate." The overlap decision that looked optimal request-by-request produced a queue that blew up p99.

This matters most for the traffic shape agents actually generate: "a peak-load, relatively-low-TPS pattern where bursts in concurrency matter far more than raw tokens-per-second." Average throughput can look healthy while the tail is on fire.

How token-load-aware routers decide

The orchestration layer's decisions are not cosmetic - "how effectively the orchestration layer distributes heterogeneous request streams across a fleet of LLM engine replicas directly impacts serving TTFT, TPOT, and throughput." A token-load-aware router turns that into a two-term score.

1. Overlap term. Estimate how much of the request's prefix a replica already holds. Modern systems compute this at fine granularity: "vLLM emits events as cache blocks are created and removed, giving the router an up-to-date view of KV cache state across replicas and allowing it to compute overlap at the KV cache block level for each request."

2. Load term. Estimate the token work already committed on that replica - queued prefill tokens plus active decode slots.

The router then routes to the replica that maximizes overlap benefit net of the queuing cost the extra load would add. When a high-overlap replica is saturated, it accepts a colder cache elsewhere to keep the tail flat. Overlap is a discount, not a mandate.

Concurrency and KV cache capacity constraints

The reason token load and cache reuse are the same conversation is that they share one budget. "What caps concurrency is KV cache capacity, since every active request holds a slice of it." Every request you admit for its cheap-prefill overlap also consumes cache that a concurrent decode needs. Push overlap too hard and you starve concurrency; the replica can no longer keep enough requests batched to sustain throughput, and both TTFT and TPOT degrade together.

A good router therefore treats KV capacity as the constraint and overlap as one lever inside it - never as a goal that overrides headroom. If prefix reuse is central to your workload, the mechanics are worth understanding on their own; see our deeper write-ups on prefix caching for multi-turn LLM agents and speculative decoding throughput.

Why the underlying latency numbers matter

Routing only pays off if each replica is fast to begin with. In our benchmarks of framework choice on a single H100 - 256 input tokens, batch size 1, full roundtrip to the platform - we measured a lowest TTFT of 123ms with vLLM, and 460 tokens/sec throughput with SGLang at batch size 64. Framework choice sets the floor your router then defends. The full method and per-framework curves are in our vLLM vs SGLang vs TensorRT benchmark.

Capacity elasticity matters too: a replica that cold-starts slowly can't absorb a burst. In our testing of a TensorRT-LLM Llama 3 8B engine, cold start takes "roughly ~10-15s to load the model into GPU memory," and that same single-A10 setup reached ~1700 output tokens/sec (FP8). If your autoscaler adds replicas to shed token load, that cold-start window is the gap your router has to cover with the fleet it already has. For the cost side of running this at volume, see LLM inference cost at scale and the 2026 GPU buyer's guide.

Checklist for Lead ML Engineers

• Measure token load, not request count. Track queued prefill tokens and active decode slots per replica.

• Score overlap and load together. Treat prefix reuse as a discount on prefill cost, subtracted from queuing cost - not as the routing objective.

• Watch p99, not the average. Bursty, low-TPS agent traffic hides behind healthy mean throughput.

• Respect KV capacity as the hard limit. Concurrency is capped by cache; over-concentrating overlap starves it.

• Account for cold starts. Know how long a new replica takes before it can take load off a hotspot.

Workloads that are heavy on concurrent sessions - AI agents and voice especially - feel this tension first. Start from the tail latency you must hold, then let overlap earn its place inside that budget.