TL;DR: Score each replica by the prefill work it would add, queued prompt tokens plus this request's uncached tokens, and pick the minimum. On Llama 3.3 70B with 6,000 of 8,000 prompt tokens shared, a warm replica saves 428 ms of prefill, so the router stays with the owner until its queue is more than 428 ms deeper than the coldest replica. Affinity cuts the fleet from 90 H200s to 44; random routing cannot keep 200 prefixes warm in a 558K-token pool.
How to approach it
Ask what is shared: how many distinct prefixes, how long, and how skewed their traffic is. Ask how stale the router's view of each engine may be. Then show two numbers before any design: what a hit saves in replica time, and whether the prefix set fits in one replica's KV pool. If it fits everywhere, affinity is not worth its imbalance.
A strong answer
Load. 40 req/s, 8,000-token prompts whose first 6,000 tokens are one of 200 per-customer system prompts and tool schemas, 300 output tokens. Llama 3.3 70B with FP8 weights on TP=2 H200, BF16 KV at 320 KiB per token, assumed 50% MFU for prefill and 75% MBU for decode:
prefill per tok = 2 x 70.55e9 / (2 x 1979e12 x 0.50) = 71.3 us
saved by a hit = 6,000 x 71.3 us = 428 ms of replica time
TTFT compute = 8,000 x 71.3 us = 570 ms cold, 2,000 x 71.3 us = 143 ms warm
KV pool/replica = (2 x (141e9 x 0.92 - 3e9) - 70.55e9) / 327,680 B = 558,124 tokens
Does the prefix set fit? At a decode batch of 64, the sequences' unshared tokens take most of the pool, and the rest is room for cached prefixes:
unshared KV = 64 x (2,000 + 150) = 137,600 tokens
room for prefix = (558,124 - 137,600) / 6,000 = 70 prefixes per replica
all 200 prefixes = 200 x 6,000 = 1,200,000 tokens, 2.2x one pool
Random routing asks every replica to hold all 200, so LRU churns and the hit rate collapses. Affinity asks each of about 22 replicas to hold its 9 or so, which fits with room to spare.
Fleet with and without affinity. Decode at batch 64 and 8,150 tokens of context:
step = (35.3 GB + 64 x 8,150 x 327,680 B / 2) / (4.8e12 x 0.75) = 33.5 ms
replica tok/s = 64 / 33.5 ms = 1,908
decode demand = 12,000 / 1,908 = 6.29 replica-seconds per second
no affinity : prefill 22.8 + 6.29 = 29.1 / 0.65 = 44.8 -> 45 replicas, 90 GPUs
affinity, 90% of : prefill 7.42 + 6.29 = 13.7 / 0.65 = 21.1 -> 22 replicas, 44 GPUs
requests warm
cost per M out = 90 x $3.50/h -> $7.29 vs 44 x $3.50/h -> $3.56 (illustrative)
The hot-prefix problem. With a cache hit, one request costs 2,000 x 71.3 us + 300 / 1,908 = 0.30 replica-seconds, so one replica at 65% serves 2.17 req/s. A customer sending 10% of traffic (4 req/s) needs 1.8 replicas by itself. Pure hashing pins it to one and that replica's TTFT runs away.
The rule. For each candidate replica :
where is prompt tokens already queued on and is this request's tokens not cached on . Pick the minimum. The owner wins while its extra queue is under the 6,000 tokens it saves, which is the 428 ms threshold, and loses the moment it is not. The first spill warms a second replica, so a hot prefix grows owners in proportion to its load without a separate replication policy. Two guards sit on top: exclude any replica above about 95% KV usage (admitting there forces preemption), and exclude replicas whose state report is older than a few hundred milliseconds.
Router state. The router needs to know what each engine has cached. Two ways: engines publish block-stored and block-evicted events, or the router keeps its own approximate tree of what it sent where and accepts some false hits. Current engine-agnostic routers take the first path: NVIDIA Dynamo's KV-aware router (v1.5.x) and llm-d's endpoint picker (llm-d v0.10.0) both score replicas on cached-prefix overlap and load. The approximate tree works when evictions are rare, which is the case the KV-fit check above establishes.
The reversal condition: if the shared fraction of each prompt is small (under about a fifth) or the whole prefix set fits in every replica's pool, the hit saves little or happens everywhere anyway, and least-queued-tokens routing beats affinity because it never concentrates load.
What interviewers probe next
"The router's view is two seconds stale." Use the router's own record of recent assignments for the queue term and engine reports only for cache state, which changes slowly. Queue depth is the term that goes wrong fastest.
"A replica dies." Its prefixes go cold. Affected requests score every replica as uncached, fall back to least-queued, and the first one to land rebuilds the prefix on its new owner. Expect a TTFT bump of about 428 ms for those customers' next requests.
"Two tenants share a system prompt. Should they share cache?" Only if they are allowed to. vLLM v0.31.0 mixes a per-request cache_salt into the first block's hash, so salting by tenant separates their entries at the cost of duplicate copies.
How it's scored
Weak: proposes consistent hashing on the prompt with no load term, or round-robin with "prefix caching on".
Hire: quantifies the prefill a hit saves, checks the prefix set against the KV pool, and states a cost-based rule that spills from a busy owner.
Strong Hire: derives the spill threshold from saved prefill time, shows hot prefixes acquiring owners in proportion to load, and says when affinity is not worth having.
Common mistakes
- Hashing the whole prompt instead of block-aligned prefixes, so two requests that share 6,000 tokens and differ in the last 2,000 never match.
- Balancing on request count, which ignores that a cold request carries four times the prefill of a warm one.
- Treating affinity as a latency feature only, when here it halves the GPU count.
- Ignoring stale state, so a burst of requests all pick the replica that looked idle 2 seconds ago.