All question banks

Cache Routing Interview Questions

Routing is a cache question as much as a load question: where a request lands decides whether its repeated prompt ever becomes a hit. These questions walk both sides, the hit share a balancer shape produces and the capacity its routing plan demands, with the full arithmetic shown so you can check every number. The linked terms are the glossary entries behind each answer.

Warm-up

1. Why does adding more replicas often make prefix-cache hit rates worse instead of better?

Because a balancer that spreads load evenly also spreads the cache. A prompt preamble is resident on the one card that prefilled it, and round-robin routing repeats its rotation across the whole fleet, so the chance of landing back on the resident card is one in the number of cards. Doubling the fleet doubles the rotation and halves that chance: more seats, fewer hits. The fix is to point the router at the request family - hash the template key and keep the family on its card - so the hit rate is bounded by capacity rather than divided by fleet size.

Worked answer

  1. Under perfect round-robin, the chance an arrival meets the card holding its preamble is 100 / cards.
  2. At 8 cards: 100 / 8 = 12.5 percent of arrivals hit a resident preamble.
  3. Doubling the fleet halves it: 100 / 16 = 6.25 percent - each added replica is another way to miss.
  4. Family hashing sends every request of the template to its one card, moving the hit rate from one-in-n to capacity-bound.

Round-robin on 8 cards hits 12.5 percent of preambles and 6.25 percent on 16 - scaling spread the cache because it spread the requests.

Core

2. How much memory does one resident prompt preamble cost, and how many families does a scratch hold?

A preamble copy is the KV state of its opening tokens, so it prices from the same per-token arithmetic as the live cache: two states (keys and values) times layers times KV heads times head dimension times bytes per value. For a 1,200-token opening on a 70B-class model at 8 KV heads and 128 head dimension in bf16, that is 320 KB per token and a 384 MB copy. A prefix scratch then holds whole copies and nothing between - a partially resident preamble is not a hit - so the copy count is the floor of scratch size over copy size.

Worked answer

  1. Bytes per token: 2 x 80 layers x 8 KV heads x 128 x 2 bytes = 327,680 bytes, about 320 KB.
  2. One resident copy: 1,200 tokens x 320 KB = 384,000 KB = 384 MB.
  3. An 8 GB scratch carries 8,000 MB, and 8,000 / 384 is 20.8 copies, floored to 20 whole families.
  4. The partial 0.8 copy is worth nothing: a preamble that is three-quarters resident still misses.

One preamble copy costs about 384 MB, so an 8 GB scratch holds 20 whole resident families - and eviction takes the 21st.

Core

3. Family hashing fixes the hit rate. What problem does it create in the same stroke?

Concentration. Every request of a hot prompt template hashes to the same card, so a family that owns most of the traffic parks most of the load on one card while the rest idle, and that card also owes the decode tokens on every request it serves. The busiest-card share is the hot family whole, plus at worst the one cold family of the remainder that collides onto the same card - in a 64-family fleet, the remainder spreads across the other 63 cards, and one of them can land fully on the hot card. The standard fix is to shard the hot family across two cards, which doubles one preamble copy to halve the concentration.

Worked answer

  1. A template owning 80 percent of arrivals lands whole on its card: 80 percent, plus at worst one full cold family of the remaining 63.
  2. Busiest card share: 80 + (100 - 80) / 63 = 80.32 percent.
  3. A milder case shows the shape is general: a 50 percent family gives 50 + 50 / 63 = 50.79 percent.
  4. Sharding the hot family over two cards halves the share: 80.32 / 2 = 40.16 percent each, for one extra 384 MB copy.

The busiest card carries 80.32 percent of all arrivals under a one-card hash - sharded in two, 40.16 each, bought with one extra resident copy.

Hard

4. One template owns 80 percent of traffic on an 8-card fleet. Compare cache-blind round robin with hash routing, point by point.

Cache-blind round robin wins the balance argument and loses the cache: every card sees the hot family equally, so every card must keep its own copy of the preamble or re-prefill it, and the hit share sits at one in the card count. Hash routing wins the cache: one preamble copy sits where the traffic is. The comparison has four moving numbers - the hit share, the busiest-card share, the copies each plan demands, and what overflow you add to stop the hash from queueing the hot card.

Worked answer

  1. Hit share under round robin: 100 / 8 = 12.5 percent of the family arrivals meet a resident preamble.
  2. The same family under hash routing lands on one card every time, so one 384 MB copy catches about 80 percent of its traffic if the family share is 80 percent.
  3. Copies demanded: round robin wants the preamble on all 8 cards (8 x 384 MB = 3,072 MB); the hash wants 1 copy, 384 MB.
  4. The balance price of the hash: the owner card takes about 80 percent of the family arrivals, so it needs queue-depth-aware overflow that round robin never has to think about.

Round robin: 12.5 percent hits for 8 resident copies. Hash: one copy and a hot card at 80 percent - the design decides which bill it pays and how it overflows.

Warm-up

5. How many resident preamble copies does each routing plan demand, and how do you check a scratch can afford it?

Demand follows from routing, supply from memory. A hash-routed 8-card fleet serving 64 families puts 64 / 8 = 8 resident families on every card, while cache-blind routing of any fleet size can send any family anywhere, so every card must be able to hold all 64. The check is one comparison: the copies the scratch holds must cover the copies the router demands. If demand exceeds the scratch, eviction re-prefills families the routing plan believed it had resident, and the hit rate drops toward the held-to-demanded ratio no matter how good the hash is.

Worked answer

  1. Hash plan demand: 64 families / 8 cards = 8 resident families per card.
  2. Cache-blind demand: any card can meet any family, so each card must be able to hold 64 copies.
  3. Supply: an 8 GB scratch holds 20 whole 384 MB copies.
  4. The hash plan fits with headroom of 20 / 8 = 2.5x; the cache-blind plan is short 44 copies, so eviction dominates its hit rate.

8 resident families demanded against 20 held fits with 2.5x headroom; 64 demanded against 20 held is eviction running the cache-blind fleet.

Core

6. The router is perfect and the cache still misses. What is the first thing you check?

The scratch, before the router. A 2 GB prefix scratch holds only 5 whole 384 MB copies, and an 8-card hash fleet demands 8 resident families per card, so 3 of them evict on arrival no matter how the hash is written: the hit rate is capped at 5 of 8, and the families it cannot keep pay full prefill. Capacity, not routing, is the bottleneck, so the fixes are a bigger scratch, a shorter preamble, or fewer resident families - and the router only matters once held copies cover demanded copies.

Worked answer

  1. Supply: 2 GB = 2,000 MB, and 2,000 / 384 is 5.2, floored to 5 whole copies.
  2. Demand: 64 families on 8 hashed cards = 8 resident families per card.
  3. Cap: 5 held / 8 demanded = 62.5 percent, the ceiling the router cannot lift.
  4. Growing the scratch to 8 GB holds 20 copies and clears the cap entirely.

A 2 GB scratch holds 5 copies against 8 demanded, capping the hit rate at 62.5 percent - the scratch, not the router, is the ceiling.

Hard

7. The fleet doubles from 8 to 16 cards. What does the resize do to hash routing, and what does it cost?

A resize redraws assignments, and every redrawn family re-prefills its preamble on the new card. Under plain modulo routing, doubling redraws the assignment of every family whose hash does not land back in the same half of the range: 32 of 64 families. A consistent hash ring does much better - each newly added card takes over its own arc of the ring, so one card added among 64 claims about one family in 65. The rebuild bill is the displaced families multiplied by their copy size, which is the number to weigh against the load balance the resize buys.

Worked answer

  1. Modulo doubling keeps a family only when its hash mod 16 stays under 8, so 32 of 64 families remap.
  2. Rebuild cost: 32 displaced families x 384 MB = 12,288 MB, about 12.3 GB of re-prefill on the resize.
  3. A hash ring added one card at a time: each added card claims about 1 / 65 of the ring, so the same growth moves a handful of families instead of half.
  4. Either way, the displaced share re-prefills: routing decides who pays the resize, not whether it is free.

Modulo doubling moves 32 of 64 families, about 12.3 GB of preamble; a hash ring added card by card moves on the order of one family per added card.

Warm-up

8. Why not keep every family preamble resident on every card and skip the routing problem entirely?

Because replication multiplies by fleet size exactly where the memory is scarcest. One copy of a 1,200-token preamble is 384 MB; keeping it on all cards means 64 copies of preamble per card in a 64-family fleet, 24.6 GB per card, against a scratch that is typically single-digit GB - so most cards evict most families most of the time. Full replication also wastes the one direction the cache scales in: routing concentrates each family where it is used, 8 resident families per card on an 8-card fleet, which is both cheaper and more likely to hold.

Worked answer

  1. One copy: 384 MB (1,200 tokens at 320 KB per token).
  2. Replicated to every card: 64 families x 384 MB = 24,576 MB, about 24.6 GB of preamble per card.
  3. The typical scratch is 8 GB: it holds 20 of the 64 replicated families, so eviction undoes the replication.
  4. Hash routing instead demands 64 / 8 = 8 resident families per card, inside the same 20-copy scratch.

Replicating every preamble costs 24.6 GB per card where a typical scratch holds 20 copies, so the only resident plan is routing the families down, not copying them out.

Core

9. You shard the hot family across two cards. What does that cost in memory and what does it buy in balance?

The cost is one extra resident copy of that family and a router that now has to hash the hot family over a two-card shard: 768 MB resident instead of 384. The buy is the concentration: the two shard cards split the hot family, so the busiest-card share halves. It is the standard exchange rate - one more copy in the scratch against one big step down in queue-depth variance - and the reason the check before it is that the scratch can afford the extra copy.

Worked answer

  1. Resident before: one 384 MB copy on the owner card.
  2. Resident after: 2 x 384 = 768 MB across the two-card shard, one extra copy in the fleet.
  3. Busiest-card share before: 80 + 20 / 63 = 80.32 percent of arrivals.
  4. Busiest-card share after: sharding halves it to 40.16 percent per shard card.

One extra 384 MB copy buys the busiest-card share a halving, from 80.32 to 40.16 - the concentration trade, priced in one copy.

Hard

10. A teammate proposes routing by request ID round-robin because it balances perfectly. What breaks, and what does it cost?

Balance is not the only number the router decides. Round-robin by request ID sends a hot families requests to whichever card the rotation reaches, so a preamble copy helps only when the rotation lands back on its card - 12.5 percent of the time on 8 cards - and the other 87.5 percent re-fills. Priced on a real rate card, that gap is a visible money number, and it is why the proposal gets answered with the hash rather than the rotation, accepting the same queue-depth overflow work the hash would have needed anyway.

Worked answer

  1. Volume: 20,000 requests a day x 1,500 prompt tokens = 30 million prompt tokens a day.
  2. Cache-aware routing with an 80 percent hit: 30 x (0.2 + 0.8 x 0.1) = 30 x 0.28 = 8.4 billable-units of the fresh rate, or $25.20 a day at $3 per million.
  3. Round-robin at a 12.5 percent hit: 30 x (0.875 + 0.125 x 0.1) = 30 x 0.8875 = 26.6 billable-units, $79.88 a day - and its perfect balance demanded 8 resident copies to get there.
  4. The routing decision is worth $79.88 - $25.20 = $54.68 a day at these assumptions, before any overflow logic.

The same request volume bills $25.20 a day under hash routing and $79.88 under request-ID round robin - the hit share, priced.

Need the vocabulary first? The glossary defines each of these terms with a worked example, and the other banks cover the other half of the interview.