LLMModule 09 · Problems 8, 22

Prefix caching, cache-aware routing and prefill/decode disaggregation

Most prompts repeat: the same system prompt, the same document, the same conversation plus one new message. Prefix caching stops the GPU from reading the same text twice, and routing decides whether the right GPU still has it. Disaggregation goes further and splits reading and writing onto different GPUs. Both save a lot of compute. Both move or keep large amounts of KV cache, and that has a price.

Problems covered8 (prefix caching and cache-aware routing across replicas), 22 (disaggregating prefill and decode: why, how KV moves, what it costs)
Interview levelMid (8) to senior (22)
Key ideasBlock hashing and radix trees, LRU eviction, locality vs load balance, KV bytes per token, interconnect bandwidth, P:D ratio
Time to prep3 h: 1 h reading, 30 min with the demo, 1–2 h for the exercise

Source: Vishal Singh's 25 inference-engineering interview problems · saved in sources/09-vishal-inference-25.md

Start here (no maths needed)

Before a model can answer, it has to read the whole question, and reading a long question takes real work. If the start of the question is the same as last time, the model can reuse its notes instead of reading it again, but only if the question goes back to the computer that kept those notes.

Think of it like this

Think of a delivery app with eight kitchens across town. You order from the same restaurant every week, and each kitchen keeps a card with your usual order and allergies. If the app sends you to the kitchen that has your card, they start cooking straight away. If it sends you to a random kitchen, they have to ask all the questions again. That's prefix caching and cache-aware routing. Now imagine some kitchens only do the prep (chopping, marinating) and others only cook and plate. Each kitchen gets very good at its job, but the prepped food has to be driven across town between them. That's disaggregation, and the drive is the cost.

How it works

  1. When the model reads a prompt, it writes notes (the KV cache) for every token.
  2. The notes for the start of a prompt only depend on that start, so identical starts give identical notes.
  3. The server keeps recent notes and looks them up by the text they came from.
  4. A router sends each request to the server most likely to have its notes, without overloading any one server.
  5. Disaggregated serving reads the prompt on one group of GPUs, then ships the notes to another group that writes the answer.

Why robots care

A robot asks its model nearly the same thing many times a second: the same instructions and safety rules, plus a new camera frame. Reusing the notes for the unchanged part means only the new part is read, which cuts the reaction time. On a robot with one onboard computer that's all prefix caching; splitting prefill and decode onto separate machines is a data-centre idea.

Try it

Words to know

Prefix
The beginning part of a prompt, shared with earlier prompts.
Cache hit
When the notes you need are already stored, so no work is redone.
Replica
One copy of the model running on its own GPUs; a fleet has many.
Router
The part that decides which replica gets each request.
Disaggregation
Splitting prompt reading (prefill) and answer writing (decode) onto different GPUs.

Going deeper: everything below is the full version, with some maths. On a first read, skim the headings, the interview cards and the "Why it matters for robotics" box, and come back for the rest later.

0. Shared assumptions

Same model and cost model as Page 03, so the numbers line up:

Model: Llama-style 70B, 80 layers, 8 KV heads, head dim 128
KV per token (fp16) = 2 × 80 × 8 × 128 × 2 B = 327,680 B = 320 KiB
KV per token (fp8)  = 160 KiB

Assumed cost model (round numbers for practice, not measurements):
  prefill ≈ 0.1 ms per prompt token  (10,000 prompt tokens/s per 8-GPU replica)
  decode step ≈ 20 ms + 0.2 ms per running request

GPU facts used below are from NVIDIA's H100 product page: H100 SXM has 80 GB of HBM at 3.35 TB/s, NVLink at 900 GB/s and PCIe Gen5 at 128 GB/s. The H100 NVL (PCIe card) differs: 94 GB, 3.9 TB/s, NVLink 600 GB/s. The NVLink and PCIe figures are totals for both directions, so plan on about half per direction.

Problem 8 · Design prefix caching and cache-aware routing across GPU replicas

What the interviewer is testing: that you know why prefixes can be shared, how a cache is keyed and evicted, and that routing is a tension between locality (hit rate) and load balance.

The concepts

Why it works. In a causal decoder, the keys and values at position i depend only on tokens 1…i. So two prompts that share their first P tokens have identical KV for those P tokens. Store it once, reuse it. The first token that differs ends the shared part; nothing after it can be reused, even if later text matches.

Keying the cache: block hashes. vLLM's automatic prefix caching splits the KV cache into fixed-size blocks (16 tokens by default) and identifies each full block by a hash of its own tokens and its parent block's hash. A chain of hashes identifies a prefix exactly.

h_0 = H(seed, tokens[0:16], extra)
h_i = H(h_(i−1), tokens[16i : 16i+16], extra)       extra = LoRA id, image hashes, cache salt…

lookup: walk h_0, h_1, … until a hash is missing → hit length = 16 × (blocks found)

Keying the cache: a radix tree. SGLang's RadixAttention (Zheng et al., 2024) keeps a radix tree over token sequences, where each edge holds a run of tokens and its KV. Lookup is a longest-prefix match. SGLang also orders the waiting queue so requests that share a cached prefix run together, raising hits within one server.

Eviction. Blocks in use by a running request are pinned (reference count above zero). Unused blocks stay cached and are evicted least-recently-used when memory is needed for new work. Evict leaves first: dropping a parent block makes every child unreachable.

Correctness details people forget. The cache key must include everything that changes the KV: the exact tokens (tokenizer quirks around whitespace matter), the model and adapter version, image or audio inputs. For multi-tenant safety, timing can leak whether someone else sent the same prefix, so isolate caches per tenant or add a per-tenant salt to the hash when that matters.

Routing across replicas. Each replica has its own cache. Round-robin or random routing spreads a conversation over all N replicas, so its history is on the chosen replica only about 1/N of the time. Options:

route(r) = argmax_k  [ matched_tokens(k, r) − λ × load(k) ]   among replicas with load(k) ≤ (1 + ε) × mean load

Worked answer with numbers

Assumptions: 8 replicas; 20 requests/s; each prompt has a 2,000-token system prompt shared by everyone, 3,000 tokens of conversation history, and 1,000 new tokens.

Size of what we're caching
  system prompt: 2,000 × 320 KiB = 655 MB  (once per replica: fine)
  one history  : 3,000 × 320 KiB = 983 MB

Expected cached tokens per request
  random routing     : 2,000 (system, everywhere) + 3,000 × 1/8 = 2,375 of 6,000 → 40 %
  cache-aware routing: 2,000 + 3,000 (if not evicted)             = 5,000 of 6,000 → 83 %

Prefill work per second (prompt tokens that must be computed)
  random     : 20 × (6,000 − 2,375) = 72,500 tokens/s
  cache-aware: 20 × (6,000 − 5,000) = 20,000 tokens/s
Fleet prefill capacity (assumed): 8 × 10,000 = 80,000 tokens/s
  random      uses 91 % of it, leaving almost nothing for decode
  cache-aware uses 25 %

Mean prefill time per request (TTFT contribution)
  random     : 3,625 × 0.1 ms = 0.36 s
  cache-aware: 1,000 × 0.1 ms = 0.10 s

Effective cache size. Random routing tends to store the same conversation on several replicas over time. Cache-aware routing stores each conversation once, so the fleet's useful cache is close to N times one replica's. With, say, 400,000 cacheable tokens per replica (131 GB at fp16 for this model), 8 replicas hold about 3.2 million tokens, roughly 1,000 three-thousand-token histories. The demo shows hits collapsing once active conversations no longer fit.

Interactive: prefix-cache hit rate against routing policy

Simulated chat traffic: each request is one of 4 shared 2,000-token system prompts, plus a conversation history (starting at 500 tokens, growing 500 per turn, reset after 20,000), plus 300 new tokens. Conversation popularity follows a Zipf law with the skew you set. Each replica keeps an LRU cache of the size you set. 20,000 requests with a fixed seed; the first 5,000 warm the caches. Left: token hit rate for all four policies, with yours highlighted. Right: prefill tokens computed per replica under your policy (dashed line = mean).

Token hit rate
–
Prefill tokens per request
–
Mean prefill time
–
Load imbalance (max/mean)
–

Try this: at the defaults, compare Random with Cache-aware: hit rate goes from about 55% to 94%, and prefill tokens per request drop from about 5,100 to 670. Then pick Sticky hash and note the red replica on the right: load imbalance about 1.7×. Set Popularity skew to 0 and the imbalance almost vanishes. Prefill time uses the assumed 0.1 ms per prompt token and ignores queueing.

At the defaults (8 replicas, 400,000-token caches, 500 conversations, skew 1.0) the demo gives a token hit rate of about 55% for random and round-robin (the shared system prompts hit almost everywhere; histories rarely do), about 97% for sticky hashing and about 94% for cache-aware routing. Sticky hashing pays for its extra 3 points with a load imbalance of about 1.7×: the replica that popular conversations hash to does 74% more prefill than average. Cache-aware stays near 1.05×. At skew 0 (all conversations equally popular) sticky hashing is balanced (about 1.1×), but hit rates fall to about 59% for both: 500 histories averaging around 10,000 tokens no longer fit in the fleet's 3.2 million cached tokens. Drop the cache to 50,000 tokens per replica and even cache-aware routing falls to about 56%, because histories are evicted before their next turn.

Trade-offs

ChoiceGainCost
Prefix caching onLower TTFT and prefill compute on repeated prefixesHashing and bookkeeping overhead; cached blocks compete with running requests for HBM (evicted first, so small)
Random / round-robin routingSimple, perfectly balancedHit rate falls toward 1/N for per-conversation prefixes
Sticky hashingHigh hit rate, stateless routerHotspots under skewed popularity; resizing moves keys
Cache-aware with load guardNear-sticky hit rate, balanced loadRouter must track cache state; stale views cause misses
Bigger cache tier (CPU DRAM, SSD)More history survivesLoading KV over PCIe costs time; only worth it when faster than recomputing

How to say it in the interview

KV for a prefix depends only on that prefix, so identical prefixes can share it. Inside each replica I'd use block-level hashing chained to the parent block, or a radix tree, with reference counts so in-use blocks are pinned and LRU eviction of unused leaves; the key includes model, adapter and multimodal inputs. Across replicas, random routing gives each conversation's history roughly a 1-in-N chance of being there, so with 8 replicas and a 2,000-token shared system prompt plus 3,000 tokens of history, the hit rate drops from about 83% to 40% and prefill work more than triples. I'd route to the replica with the longest cached match unless it's overloaded, replicate hot system prompts everywhere, and watch hit rate and per-replica load together, because pure stickiness creates hotspots.

Common mistakes

Problem 22 · Disaggregate prefill and decode: why, how the KV cache moves, and what it costs

What the interviewer is testing: that you know the two phases want different hardware treatment, that you can compute KV transfer size and time from first principles, and that you know when disaggregation isn't worth it.

The concepts

Why split them. Prefill processes thousands of tokens per forward pass: it's compute-bound and sets TTFT. Decode processes one token per request per step: it's memory-bandwidth-bound and sets TPOT. Running both on the same GPUs has two problems:

DistServe (Zhong et al., OSDI 2024) puts the phases on separate GPUs and optimises each for its own SLO, measuring goodput: requests per second that meet both the TTFT and TPOT targets. Splitwise (Patel et al., ISCA 2024) splits the phases across machines and studies using different hardware for each. Mooncake (Qin et al., 2024), Kimi's serving platform, builds the whole system around a disaggregated KV cache pool spread over GPU, CPU memory and SSD.

How the KV cache moves.

  1. The router sends the request to a prefill worker (often after checking which decode worker will take it, so memory is reserved there first).
  2. The prefill worker computes the prompt's KV, either all at once or layer by layer.
  3. KV blocks are copied GPU-to-GPU: over NVLink inside a node, or over RDMA (InfiniBand or RoCE with GPUDirect RDMA) across nodes, so the CPU isn't in the data path. Layer-by-layer sending overlaps the transfer with the remaining prefill.
  4. The decode worker receives the blocks into its own paged KV memory and starts generating from the first token.

Software that does this: vLLM's disaggregated prefilling with pluggable KV connectors (its docs mark the feature experimental), NVIDIA Dynamo with its NIXL transfer library, SGLang's prefill/decode disaggregation mode, and Mooncake's transfer engine. One practical snag: if the two pools use different tensor-parallel sizes, KV heads are split differently on each side, so blocks must be re-sharded during transfer.

transfer bytes = KV per token × prompt tokens
transfer time  ≈ transfer bytes / (per-GPU link bandwidth × GPUs sending in parallel) + setup latency

Worked answer with numbers

Transfer cost for one request. 8,000-token prompt on the 70B model, tensor parallel 8 on both sides (so each GPU holds one of the 8 KV heads and sends 1/8 of the cache).

KV size (fp16): 8,000 × 327,680 B = 2.62 GB      (fp8: 1.31 GB)
per GPU (TP 8): 2.62 GB / 8 = 328 MB

Within a node, NVLink (H100 SXM: 900 GB/s total → assume ~450 GB/s one way):
  328 MB / 450 GB/s ≈ 0.7 ms per GPU, in parallel

Across nodes (assumption: one 400 Gb/s = 50 GB/s NIC per GPU, a common NDR InfiniBand setup):
  328 MB / 50 GB/s ≈ 6.6 ms      (all 8 NICs in parallel)
  2.62 GB / 50 GB/s ≈ 52 ms      (if everything went through a single NIC)

Compare with the work around it:
  prefill of 8,000 tokens ≈ 8,000 × 0.1 ms = 0.8 s
  one decode step         ≈ 20–50 ms
  → cross-node transfer adds ~1 % to TTFT with all NICs, ~7 % through one NIC,
    and close to 0 if sent layer by layer during prefill.
  100,000-token prompt: 32.8 GB fp16 → ~82 ms across 8 NICs, against a ~10–19 s prefill.

Sizing the two pools (the P:D ratio). Traffic: 20 requests/s, 3,000 prompt tokens and 300 output tokens each, TPOT target 40 ms.

Prefill demand = 20 × 3,000 = 60,000 prompt tokens/s
  ÷ 10,000 per replica (assumed)                    → 6 prefill replicas

Decode concurrency (Little's law) = arrival rate × time in decode
  = 20/s × (300 tokens × 0.040 s) = 20 × 12 s       = 240 running requests
  max batch at 40 ms TPOT: (40 − 20) / 0.2 = 100    → 3 decode replicas

P:D ≈ 6 : 3 = 2 : 1
With 83 % prefix hits (Problem 8): 60,000 × 0.17 ≈ 10,200 tokens/s → 1–2 prefill replicas, P:D ≈ 1 : 2.

The lesson: the right ratio depends on prompt length, output length and cache hit rate, all of which drift. A fixed split goes stale, so production systems rebalance workers between the pools, or keep the ability to fall back to colocated serving.

What it costs, in full:

Trade-offs

Colocated (with chunked prefill)Disaggregated
TPOT stabilityGood with small chunks, still some interferenceBest: decode never shares a step with prefill
TTFTCompetes with decode for each stepPrefill pool can be tuned purely for TTFT; adds transfer time
Hardware and parallelismOne layout for bothSeparate layouts, possibly different GPU types
NetworkNormalNeeds fast GPU-to-GPU links (NVLink, RDMA)
Best forSmall fleets, short prompts, variable mixLarge fleets, long prompts, strict TTFT and TPOT SLOs together

How to say it in the interview

Prefill is compute-bound and sets TTFT; decode is bandwidth-bound and sets TPOT. Colocating them means prefill steps slow decode and one parallelism layout has to serve both, so disaggregation puts them on separate pools and tunes each to its own SLO. The KV cache moves GPU-to-GPU over NVLink or RDMA, ideally layer by layer during prefill. The size is easy to compute: for a 70B model with 8 KV heads, an 8,000-token prompt is 2.6 GB at fp16, about 7 ms across eight 400 Gb/s NICs in parallel, which is around 1% of a 0.8 s prefill. The real costs are a fast network on every GPU, keeping the prefill-to-decode ratio right as traffic changes, and complexity, so I'd only do it at scale with long prompts and strict latency targets.

Common mistakes

Practise it

  1. Prefix caching on a free Colab GPU. Serve a small instruct model with vLLM (prefix caching is on by default in recent versions; check --enable-prefix-caching for yours). Send 100 requests that share a 2,000-token system prompt and differ in a short question. Measure TTFT for the first request against the rest, then put a timestamp at the very start of the system prompt and measure again.
  2. Read the metrics. Scrape vLLM's Prometheus /metrics endpoint and find the prefix-cache query and hit counters. Compute hit rate and check it against what you expect from your prompts.
  3. Build a router simulator. Extend this page's demo script in Python: give each replica a queue and service time from the cost model, and measure TTFT p50/p95 per policy, not just hit rate. Try a consistent-hash ring and add a replica halfway through the run.
  4. Transfer maths, measured. On any machine with two GPUs, time torch.Tensor.to() copies of a tensor the size of one request's KV (from the formula) between devices, for prompt lengths from 1K to 64K tokens. Compare with your prefill time for the same lengths and find where transfer becomes a meaningful share.

In this course

Why it matters for robotics

Self-check

Why can two prompts share KV for their common start but not for matching text later on?

KV at position i depends on all tokens 1…i. After the first differing token, every later position has different context, so its keys and values differ even if the text is the same.

Why does vLLM hash each block together with its parent's hash?

So the hash identifies the whole prefix up to that block, not just the block's own 16 tokens. The same 16 tokens after a different prefix have different KV.

8 replicas, random routing, 2,000 shared system tokens everywhere, 3,000 history tokens, 1,000 new. Expected cached fraction?

(2,000 + 3,000/8) / 6,000 = 2,375 / 6,000 ≈ 40%. Cache-aware routing can reach 5,000 / 6,000 ≈ 83%.

What goes wrong with pure sticky hashing, and what fixes it?

Popular sessions or prefixes overload the replica they hash to. Fix it with a load guard (fall back to the least-loaded replica past a threshold) and by replicating hot prefixes such as the system prompt everywhere.

How big is the fp16 KV transfer for a 16,000-token prompt on a 70B model with 80 layers, 8 KV heads and head dim 128?

16,000 × 327,680 B ≈ 5.24 GB at fp16, 2.62 GB at fp8. Across 8 GPUs each with a 50 GB/s NIC, about 13 ms at fp16.

When would you not disaggregate?

Small fleets, short prompts, or a traffic mix that shifts a lot. Colocated serving with chunked prefill absorbs imbalance automatically and needs no fast inter-GPU network or P:D tuning.

Resources