GPU Routing and Cache Affinity

Choosing which replica serves a request when the replicas are not interchangeable — prefix affinity, queue-aware placement, LoRA multiplexing and draining.

AI EngineeringGraduate⏱ 3 hours6 min readroutingload balancingKV cacheaffinityLoRA

AssumesThe Anatomy of an AI System · Load Balancing and the Power of Two Choices

The tension

DefinitionThe affinity–pooling tension

Affinity routes a request to the replica that already holds its KV prefix, saving the prefill for that prefix. Pooling routes to whichever replica is least loaded, minimising queueing.

They conflict because affinity partitions one queue into many. By the pooling result in Queueing and the Utilisation Wall, $c$ separate queues have strictly worse delay than one queue with $c$ servers at the same utilisation — and the gap grows with $c$ .

PropositionWhen to honour affinity

Let replica $A$ hold a prefix of $k$ tokens and have queued work $Q_A$ seconds; let replica $B$ hold nothing and have $Q_B < Q_A$ . Writing $t_{\text{prefill}}(k)$ for the time to prefill $k$ tokens, routing to $A$ is faster exactly when

Q_A - Q_B \;<\; t_{\text{prefill}}(k) .

Key idea

The rule has the right shape: affinity is worth more for long prefixes and less under load. A 20,000-token system prompt is worth waiting a long time for; a 200-token one is not worth waiting at all. Using $t_{\text{prefill}}(k)$ as the tolerance — rather than a fixed "always prefer warm" or "never prefer warm" — is the whole design, and both fixed policies are wrong in the regime the other one covers.

def choose(req, replicas):
    k = prefix_len(req)                       # longest cached prefix across the fleet
    warm = [r for r in replicas if r.has_prefix(req.prefix_hash)]
    cold = [r for r in replicas if r not in warm]
    best_cold = min(cold, key=lambda r: r.queued_seconds, default=None)
    if not warm:
        return best_cold
    best_warm = min(warm, key=lambda r: r.queued_seconds)
    if best_cold is None:
        return best_warm
    saved = prefill_seconds(k, best_warm.hardware)
    return best_warm if (best_warm.queued_seconds - best_cold.queued_seconds) < saved else best_cold

What to balance on

HeuristicRoute on outstanding work, not outstanding requests

Heuristic — a reasoning shortcut that predicts the right answer in the regimes discussed here. It is not a proof and can fail outside them.

Round-robin equalises request counts; least-outstanding-requests equalises in-flight counts. For generation neither is right, because a request may be 20 tokens or 20,000. Balance on queued tokens — the sum over queued and running requests of their remaining expected output — which is the quantity that actually predicts when the replica will be free.

Assumptions

Remaining output length is unknown, so this needs an estimate: max_tokens as a pessimistic bound, a learned predictor, or a running estimate that decays as tokens are emitted. An estimate is still far better than a count, because the count is wrong by the full dynamic range of the workload.

By the Pollaczek–Khinchine formula in Queueing and the Utilisation Wall, queueing delay scales with $1 + c_s^2$ ; routing on counts lets that variance land unevenly across replicas, so some replicas carry several long generations while others idle.

Adapters

DefinitionAdapter-aware routing

When replicas serve a shared base model with different LoRA adapters loaded, the fleet is no longer homogeneous: replica $r$ can serve tenant $t$ only if $t$ 's adapter is resident, or can be loaded. Routing becomes a constrained assignment with three costs:

	Cost
adapter already resident	0
adapter loadable from host memory	tens of milliseconds
adapter must be fetched from object storage	seconds

The router therefore maintains, per replica, the resident adapter set, and prefers residency the same way it prefers KV affinity — with a tolerance, so that a busy replica holding the adapter eventually loses to an idle one that must load it.

Key idea

Adapter residency and KV affinity are the same kind of constraint at different timescales: adapters are per-tenant and persist for minutes, KV prefixes are per-conversation and persist for seconds. A router that models both as "cost to make this replica able to serve this request cheaply" handles them with one rule rather than two special cases.

Taking a replica out

DefinitionDraining a replica

Removing a replica — for a deploy, a scale-down or a failing GPU — has three phases:

Close to new work. Mark unhealthy in the router, keep serving. New requests go elsewhere; in-flight generations continue.
Wait for in-flight work. Generations finish naturally. This is bounded by the longest max_tokens on the replica, which can be minutes.
Force-migrate at a deadline. Anything still running is cancelled and, if the client is still connected, re-dispatched — losing its KV cache and restarting the prefill.

The deadline is required: without it, one request with a large max_tokens blocks the drain indefinitely, and rolling deploys stall behind it.

What this does not say

This page assumes prefill and decode happen on the same replica. Disaggregated serving splits them onto separate pools, which changes the routing problem substantially: affinity then applies to the decode pool while the prefill pool is genuinely interchangeable, and the KV cache has to be transferred between them over the network. That is covered in Inference Server Architecture.

References

PaperW. Kwon et al. (2023). Efficient Memory Management for Large Language Model Serving with PagedAttentionPaged KV cache and prefix sharing, which is what makes affinity worth routing for.
PaperL. Zheng et al. (2024). SGLang: Efficient Execution of Structured Language Model ProgramsRadixAttention, a prefix-tree KV cache that makes prefix-aware routing directly actionable.
PaperY. Sheng et al. (2023). S-LoRA: Serving Thousands of Concurrent LoRA AdaptersServing many adapters from one base model, the setting of the adapter-routing section.

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

DefinitionThe affinity–pooling tensionRouting to the replica holding a request's KV prefix saves prefill but partitions the queue, and the two effects pull in opposite directions.
PropositionWhen to honour affinityproof includedPrefer the cache-warm replica exactly when the prefill saved exceeds the extra queueing its load implies.
HeuristicRoute on outstanding work, not outstanding requestsRequests differ by orders of magnitude in size, so the balancing signal must be queued tokens rather than queued requests.
DefinitionAdapter-aware routingReplicas holding different LoRA adapters form overlapping capability classes, turning routing into a constrained assignment rather than a free choice.
DefinitionDraining a replicaRemoving a replica requires stopping new admissions, letting in-flight generations finish, and bounding the wait with a forced-migration deadline.