1. The problem, stated precisely#
Prefix caching (Section V.11) is a per-replica optimization.
Each replica has its own KV cache and its own prefix cache.
With N replicas and random routing:
P(a request lands on a replica that has its prefix cached) ≈ 1/N
N=8 → 12.5% hit rate.
The optimization exists but you've routed around it.Building prefix caching and then routing randomly is one of the most common self-inflicted wounds in LLM platform engineering. The fix is routing logic, not more caching.
Diagram — Affinity with a load bound#
flowchart LR
R["Request"] --> K["Prefix key<br/>hash of the leading tokens"]
K --> P{"Preferred replica - the one<br/>holding this prefix - overloaded?"}
P -->|"no"| A["Route to it<br/>KV cache hit, low TTFT"]
P -->|"yes"| S["Spill to the least-loaded replica<br/>cache miss, but no hot spot"]
A --> U["Update load + cache view"]
S --> U
class P queue
class A memory
class S compute
class R,K,U neutral2. The value at stake#
Chat workload, 1,500-token system prompt + history, 200-token new message:
WITHOUT prefix caching: prefill 1,700 tokens per turn
WITH, 12% hit rate: prefill ~1,520 tokens (barely helps)
WITH, 85% hit rate: prefill ~455 tokens
→ prefill work reduced 73%
→ for a workload where prefill is 30% of GPU time: 22% total capacity
→ TTFT improves 3-5x for cache hitsFor multi-turn conversation the effect is larger still, because without caching, turn N re-prefills turns 1..N-1 — quadratic in conversation length.
3. The strategies, from simple to sophisticated#
Strategy 1 — session affinity (start here)#
Go
func route(r *Request, replicas []*Replica) *Replica {
if key := cmp.Or(r.ConversationID, r.SessionID); key != "" {
healthy := healthyOnly(replicas)
candidate := healthy[hash(key)%uint64(len(healthy))]
if candidate.KVUsage() < 0.85 {
return candidate // same conversation → same replica → warm KV cache
}
}
return leastLoaded(replicas)
}✓ trivially simple
✓ captures most of the benefit for chat (turns of one conversation
share a prefix by construction)
✓ consistent hashing → adding/removing replicas moves few sessions
✗ doesn't help when different conversations share a system prompt
✗ doesn't help for stateless request patterns
→ IMPLEMENT THIS FIRST. It's an afternoon of work for most of the benefit.Strategy 2 — prefix hash routing#
Go
const prefixWindow = 512 // tokens
type PrefixRouter struct {
mu sync.Mutex
prefixMap map[uint64][]string // prefix hash → replica ids (bounded with an LRU in production)
}
func (p *PrefixRouter) Route(r *Request, replicas []*Replica) *Replica {
h := hashTokens(r.TokenIDs[:min(prefixWindow, len(r.TokenIDs))])
p.mu.Lock()
defer p.mu.Unlock()
var best *Replica
for _, rep := range replicas {
if slices.Contains(p.prefixMap[h], rep.ID) && rep.Healthy() && rep.KVUsage() < 0.85 &&
(best == nil || rep.KVUsage() < best.KVUsage()) {
best = rep // warm AND least loaded among the warm ones
}
}
if best != nil {
return best
}
chosen := powerOfTwo(replicas)
p.prefixMap[h] = append(p.prefixMap[h], chosen.ID)
return chosen
}✓ handles shared system prompts across different conversations
✓ works for stateless patterns
✗ needs a prefix→replica map, kept fresh
✗ the window size is a tuning parameter
✗ the map is the router's guess; the replica may have evicted itStrategy 3 — replica-reported prefix state#
Replicas periodically report which prefix hashes they hold:
GET /prefix_cache_state
→ {"hashes": [...], "generation": 1234} (a Bloom filter, or the
top-K by size)
Router queries its local copy. More accurate than guessing, at the cost
of the state transfer.
✓ accurate
✗ the state is large (thousands of block hashes per replica)
→ use a Bloom filter or report only the top-K longest cached prefixes
✗ staleness: a replica may evict between reportsPractical compromise: report only the top-K longest cached prefixes (say, the 100 prefixes of ≥ 256 tokens). Those are the ones worth routing for; short prefixes aren’t worth the routing distortion.
Strategy 4 — a shared radix tree in the router#
The router maintains a global radix tree (Section VIII.12) mapping
token prefixes → which replicas have them.
✓ longest-prefix matching, naturally
✓ handles branching conversation trees
✗ the router now maintains substantial state
✗ must be kept consistent with replica evictions
→ what SGLang's router does. Worth it at scale.4. The tension: affinity vs load balance#
PURE AFFINITY
every request for prefix P goes to replica R.
→ if P is popular, R is overloaded while others idle.
PURE LOAD BALANCE
→ 1/N hit rate.
THE RESOLUTION: a threshold, or a combined score.Go
const wCache, wLoad = 1.0, 1.5
func score(rep *Replica, r *Request, prefixHash uint64) float64 {
cacheBenefit := float64(rep.EstimatedCachedTokens(prefixHash)) / float64(max(len(r.TokenIDs), 1)) // 0..1
loadPenalty := rep.KVUsage() // 0..1
return wCache*cacheBenefit - wLoad*loadPenalty
}
// With wCache = 1.0 and wLoad = 1.5,
// a full cache hit (benefit 1.0) outweighs a load difference of 0.67.Tune the weights by measuring end-to-end TTFT, not by measuring hit rate. A 95% hit rate on an overloaded replica is worse than a 60% hit rate spread evenly.
MEASURED EXAMPLE (8 replicas, 70% prefix sharing):
W_CACHE/W_LOAD hit rate p50 TTFT p99 TTFT
0 (pure load) 12% 410 ms 2,100 ms
0.3 44% 290 ms 1,850 ms
0.67 78% 215 ms 1,900 ms ← best p50
1.5 91% 198 ms 3,400 ms ← p99 degrades
∞ (pure affinity) 96% 190 ms 8,900 ms ← imbalanceThe p99 column is why pure affinity is wrong. The sweet spot balances both.
5. Replica churn#
PROBLEM: when a replica is added or removed, naive hashing remaps
everything, invalidating every cache.
SOLUTION: consistent hashing with virtual nodes.
adding one replica to N remaps ~1/(N+1) of keys, not all of them.
Also: on scale-down, DRAIN rather than remove abruptly, so
in-flight sessions finish on their warm replica.Go
// ring.go — consistent hashing: adding a replica moves only ~1/N of the keys.
package main
import (
"fmt"
"hash/fnv"
"sort"
)
func hash(s string) uint64 {
h := fnv.New64a()
h.Write([]byte(s))
x := h.Sum64() // FNV alone clusters on similar strings; mix the bits
x ^= x >> 33
x *= 0xff51afd7ed558ccd
x ^= x >> 33
return x
}
type Ring struct {
points []uint64
owner map[uint64]string
}
func NewRing(replicas []string, vnodes int) *Ring {
r := &Ring{owner: map[uint64]string{}}
for _, rep := range replicas {
for i := 0; i < vnodes; i++ { // many points per replica smooth out the load
p := hash(fmt.Sprintf("%s:%d", rep, i))
r.points, r.owner[p] = append(r.points, p), rep
}
}
sort.Slice(r.points, func(a, b int) bool { return r.points[a] < r.points[b] })
return r
}
// Get returns the first replica clockwise from the key's position on the ring.
func (r *Ring) Get(key string) string {
h := hash(key)
i := sort.Search(len(r.points), func(i int) bool { return r.points[i] >= h }) % len(r.points)
return r.owner[r.points[i]]
}
func main() {
before := NewRing([]string{"r1", "r2", "r3", "r4"}, 150)
after := NewRing([]string{"r1", "r2", "r3", "r4", "r5"}, 150)
moved := 0
for i := 0; i < 10000; i++ {
key := fmt.Sprint("conversation-", i)
if before.Get(key) != after.Get(key) {
moved++
}
}
fmt.Printf("adding a 5th replica moved %.1f%% of conversations (ideal: 20%%)\n", float64(moved)/100)
fmt.Println("with `hash(key) % N` instead, about 80% would move — and lose their KV cache")
}6. Cache warming#
When a new replica starts, its prefix cache is empty.
Routing it traffic gives poor TTFT for those requests.
OPTIONS
1. Ramp traffic gradually (10% → 100% over 5 minutes)
✓ simple; the cache fills naturally
2. Pre-warm: send the known-popular prefixes as dummy requests
before marking the replica ready
✓ ready-means-ready
✗ costs GPU time; must know the popular prefixes
3. Accept it. The cache fills in seconds under real traffic.
→ often fineOption 1 is usually sufficient and combines well with the gradual traffic return after failures (Section XI.06).
7. When prefix-aware routing doesn’t help#
Be honest about the cases:
✗ every request has a unique prompt (some RAG, some batch processing)
✗ prompts are short (< 256 tokens) — the routing distortion costs more
than the cache saves
✗ very few replicas (N=2 → random gives 50% already)
✗ the workload is decode-dominated (prefill is 5% of time → 73% of 5%
is 3.6% — not worth the complexity)
→ MEASURE your prefix sharing rate and your prefill time fraction
before building this.value ≈ (prefill_time_fraction) × (achievable_hit_rate - baseline_hit_rate)
× (shared_prefix_fraction_of_prompt)
Example: prefill 30% of time, hit rate 12% → 85%, shared prefix is
88% of the prompt:
value ≈ 0.30 × 0.73 × 0.88 = 19% capacity improvement. Worth it.
Example: prefill 6% of time, hit rate 12% → 60%, shared prefix 40%:
value ≈ 0.06 × 0.48 × 0.40 = 1.2%. Not worth the complexity.8. Production implications#
- Implement session affinity first. Afternoon of work, most of the benefit for chat.
- Measure the value before building strategies 2-4. Use the formula in section 7.
- Tune the affinity/load weights by measuring TTFT p50 AND p99. Optimizing hit rate alone degrades the tail.
- Use consistent hashing so replica changes don’t invalidate everything.
- Ramp traffic to new replicas rather than pre-warming.
- Monitor the hit rate as a first-class metric. It’s a direct cost signal.
- Alert on hit rate drops — they indicate a routing problem or a prompt-structure change.
- Educate on prompt structure: dynamic content at the front of the prompt destroys all of this (Section V.11).
9. Common mistakes#
Enabling prefix caching without prefix-aware routing. 1/N hit rate.
Pure affinity without a load release valve. p99 disaster.
Optimizing hit rate instead of TTFT.
Naive modulo hashing. Replica changes invalidate everything.
Building strategy 4 when strategy 1 would do.
Not measuring the prefix sharing rate first.
Not noticing when a product change breaks cache-friendliness.
10. Hands-on exercise#
A. Measure the sharing rate. From real request logs, compute: what fraction of requests share a ≥ 256-token prefix with a recent request? What’s the average shared-prefix length as a fraction of the prompt?
B. Compute the value. Using the formula in section 7 and your measured prefill time fraction, estimate the capacity improvement from prefix-aware routing. Is it worth building?
C. Implement session affinity. Add consistent-hash session affinity with a load release valve to a router. Measure the hit rate improvement over round-robin.
D. Tune the weights. Implement the combined score from section 4. Sweep W_CACHE/W_LOAD and
reproduce the table. Where’s your optimum?
E. Churn. Add and remove replicas with modulo hashing and with consistent hashing. Measure the fraction of sessions remapped and the resulting hit-rate dip.
F. Break it. Add a timestamp to the front of the system prompt. Measure the hit rate collapse. This is the demonstration to show your product team.
11. Interview questions#
- Why does prefix caching need prefix-aware routing?
- What hit rate does random routing give with N replicas?
- Compare session affinity and prefix hash routing. When does each apply?
- What’s the tension between affinity and load balance, and how do you resolve it?
- Why optimize for TTFT rather than hit rate?
- Why use consistent hashing?
- When is prefix-aware routing not worth building? Give the formula.
12. Further reading#
- [ESTABLISHED] Zheng et al., “SGLang” — cache-aware scheduling and the router
- [ESTABLISHED] Karger et al., consistent hashing (1997)
- [ESTABLISHED] Kubernetes Gateway API Inference Extension (
InferencePoolv1) with llm-d’s endpoint picker — prefix- and KV-cache-aware routing as a standard component - Next: 08 — Inference gateways