CacheRoute: Planned Prefix-Affinity Routing for Large-Scale LLM Serving

Huang Cheng

cs.DCAug 20, 2026

CacheRoute: Planned Prefix-Affinity Routing for Large-Scale LLM Serving

Authors: Huang Cheng

Organizations: Meta, Menlo Park, California, USA

Abstract

Prefix caching avoids prefill only when a repeated request returns to a server that still holds the prefix KV. Cache-blind balancing disperses that reuse; fixed affinity preserves it but can overload a server. CacheRoute resolves this tradeoff with a periodic routing plan. It admits high-rate keys to a stable warm set and places their assignments by expected load. Hot keys may use more than one destination, although every key in our primary semi-synthetic aggregate uses exactly one. On Llama-3.3-70B in fp8 across 60 H100 GPUs, CacheRoute sustains 176+/-11 QPS at a 3.5-s p99 SLO, 2.3x the strongest of five baselines. Served KV-cache hit rate rises from 64.1+/-1.3% under cache-blind balancing to 93.2+/-0.5%. A second semi-synthetic aggregate and controlled 8B and burst experiments separate the effects of affinity and placement. Two 32B workloads provide the counterexamples: when affinity recovers too little KV work, its residual load skew reduces or erases the improvement. We therefore recommend gating any deployment with a shadow replay rather than enabling affinity from workload statistics alone.

Figures & tables

Panel of Figure 1 — Figure 1: CacheRoute separates a periodic, rate-aware assignment from fast request dispatch. The main distribution has $k_{b}=1$ for every key, so its 70B improvement comes from admission, stable single-copy affinity, and balanced placement; multiple destinations are exercised only in the synthetic-whale mechanism study. Cache residency is measured, not guaranteed by the plan.

Policy	KV hit	[email protected]	Cap.@5s	p99@100
Flat-LB	$64.1{\pm}1.3$ %	$42{\pm}20$	80	5.7s
Sticky	$87.3{\pm}2.4$ %	30	$42{\pm}20$	8.5s
CHWBL	$75.6{\pm}0.8$ %	$64{\pm}11$	$128{\pm}14$	3.8s
DualMap	$88.7{\pm}1.9$ %	$58{\pm}22$	$84{\pm}32$	5.3s
Preble	$72.0{\pm}0.7$ %	$76{\pm}11$	140	3.8s
CacheRoute	$\mathbf{93.2{\pm}0.5}$ %	$\mathbf{176{\pm}11}$	180	1.8s

Table 1: Llama-3.3-70B fp8, 30 TP2 destinations (60 H100), primary distribution, top-

K

128, five paired seeds. Capacity is QPS at the SLO knee; KV-hit is served and token-weighted.

Panel of Figure 2 — Figure 2: Primary 70B fp8 result on 30 TP2 destinations (60 H100), top- $K$ 128, five paired seeds. (a) Measured p99 TTFT at the common 100-QPS operating point; only CacheRoute is below the primary 3.5-s SLO. (b) Per-seed SLO-capacity knees (mean and reported 95% Student- $t$ CI); CacheRoute reaches $176\!\pm\!11$ QPS, $2.3\times$ the strongest baseline.

Policy	top- $K$ 128	top- $K$ 256
Flat-LB	30	30
Sticky	30	60
CHWBL	100	60
DualMap	100	100
Preble	60	60
CacheRoute	100	160

Table 2: SLO capacity (p99

\leq 3.5

s) on the second distribution, 70B fp8/60 H100, three paired seeds.

top- $K$	Flat-LB	Sticky	CHWBL	DualMap	Preble	CacheRoute
16	500	100	500	100	500	500
32	500	100	360	100	360	500
64	500	160	360	160	360	500
128	240	240	360	360	360	500
256	160	240	240	360	360	500
2000	100	360	160	360	160	360

Table 3: 8B SLO capacity (p99

\leq 3.5

s), 30 H100, three paired seeds. “500” is right-censored.

Configuration	KV hit	Imbalance	Capacity
Flat-LB	$56{\pm}1.9$ %	$1.00\times$	240
$+$ affinity	$88{\pm}1.5$ %	$3.46\times$	240
$+$ replication	$88{\pm}1.6$ %	$2.60\times$	240
$+$ LPT (full)	$90{\pm}1.0$ %	$1.24\times$	500

Table 4: 8B component ablation, synthetic whales, top-

K

128, three seeds. Capacity 500 is right-censored.

Regime	Flat hit	Aff. hit	Cap. mult.	Result
8B synthetic whales	9.3%	77.0%	2–6 $\times$	win
Aggregate A–32B	1.1%	11.8%	0.50–0.67 $\times$	lose
Aggregate B–32B	0.8%	8.5%	1.0 $\times$	tie

Table 5: Measured operating regimes. Capacity multiplier is CacheRoute / Flat-LB ; the 8B range is a single-window synthetic mechanism result, while both 32B rows use semi-synthetic aggregate distributions.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Property	Measured value
Distinct business keys	128,824
Traffic Gini coefficient	0.756
Top-key share	$<0.3\%$
Top 4% share	$\approx 47\%$
Multi-turn request share	80.8%
Mean requests per thread	2.64

Appendix

Table 6: Primary workload characteristics. “Positional prefix” is not the same as the business-specific routing lever.

Study	Model/precision	Destinations	Workload	Repetitions	Evidence class
Primary six-policy	Llama-3.3-70B/fp8	30 TP2 (60 H100)	primary aggregate, top- $K$ 128	seeds 2–6 ( $n=5$ )	HW/core
Wide active set	Llama-3.3-70B/fp8	30 TP2 (60 H100)	primary aggregate, top- $K$ 256	seeds 2–9 ( $n=8$ )	HW/core
Second distribution	Llama-3.3-70B/fp8	30 TP2 (60 H100)	independent aggregate, $K\in\{128,256\}$	seeds 2–4	HW/core
Precision pressure	Llama-3.3-70B/fp16	30 TP2 (60 H100)	primary aggregate	seeds 2–4	HW/supporting
8B six-policy/ablation	Llama-3.1-8B/bf16	30 MP1 (30 H100)	aggregate or injected whales	seeds 2–4	HW/mechanism
Burst–Gamma	Llama-3.3-70B/fp8	30 TP2 (60 H100)	marginal CV=1.9	seeds 2–6	HW/sensitivity

Appendix

Table 7: Experiment provenance. “HW” denotes real H100 execution; “sim” denotes the calibrated offline simulator. The synthetic-whale and calibrated-simulation results are supporting mechanism evidence, not broad generalization evidence.

Policy	Served KV hit	[email protected]
Flat-LB	$19.5\pm 2.1\%$	0
Sticky	$77.3\pm 0.7\%$	0
CacheRoute	$76.4\pm 0.5\%$	0

Appendix

Table 8: 70B fp16, 30 TP2 destinations/60 H100, top-

K

128, three seeds. Capacity is zero because all policies miss the fp8 study’s 3.5-s SLO.

Policy	KV hit	[email protected]	Cap.@5s
DualMap	60%	60	100
CacheRoute	82%	80	120

Appendix

Table 9: Dedicated 70B fp8/top-

K

256 confirmation (

n=8

	Flat-LB		CacheRoute
Arrival	Cap.	KV	Cap.	KV
Poisson	30	64%	180	94%
Gamma, CV=1.9	30	63%	160	90%

Appendix

Table 10: Gamma sensitivity, 70B fp8/top-

K

128, five seeds. Capacity is at p99

\leq 3.5

	Flat-LB		CacheRoute
Arrival	Cap.	KV	Cap.	KV
Poisson	60	66%	180	93%
Gamma, CV=1.9	60	66%	180	93%
Trace blocks, CV=2.73	0	67%	180	93%

Appendix

Table 11: Self-contained block-bootstrap sweep, 70B fp8/top-

K

128, five seeds. The block trace has empirical CV=2.73. Zero is left-censored below 30 QPS.

Transition	Cache churn	Count churn	KV loss	p99 loss	Warmup dip
			(points)	(ms)	(points)
$0\to 1$	92.5%	1.6%	0.1	$-119$	15.6
$2\to 3$	94.5%	0.0%	3.0	$+858$	11.4
$4\to 5$	98.0%	1.6%	$-0.1$	$-162$	13.8
Mean	94.5%	1.1%	1.0	$+192$	13.6

Appendix

Table 12: Detailed replan measurements. Cache-churn is

1-

Jaccard of consecutive assignment sets; count-churn is the fraction whose

k_{b}

changes. Stale losses compare the previous plan with a freshly computed plan.

Axis	Setting	KV (CR/flat)	CR cap.	Mult.
$q_{\mathrm{cap}}$	50 QPS	$89\pm 0.9\%/57\%$	360	$1.50\times$
$q_{\mathrm{cap}}$	100 QPS	$91\pm 3.1\%/57\%$	360	$1.50\times$
$q_{\mathrm{cap}}$	200 QPS	$91\pm 3.2\%/57\%$	360	$1.50\times$
$q_{\mathrm{cap}}$	500 QPS	$91\pm 3.1\%/57\%$	360	$1.50\times$
Injected skew	5% head	$89\pm 1.1\%/56\%$	500	$3.12\times$
Injected skew	15% head	$89\pm 1.0\%/56\%$	500	$2.08\times$

Appendix

Table 13: 8B sensitivity,

R=30

, top-

K

128, three seeds. Capacities are ladder knees at p99

\leq 3.5

s; 500 is right-censored.

$R$	Representative scenario	KV (CR/flat)	Result
8	2 [email protected]	45%/12%	tail/KV only
30	8 [email protected]	70%/14%	$4.44\times$
60	16 [email protected]	32%/24%	no win

Appendix

Table 14: Synthetic-whale fleet-size sweep. The

R=8

ramp has no passing capacity point;

R=60

has no winning scenario.

Regime	flat	affinity	flat	CR	flat/CR
	KV hit		[email protected]		Cap.@5s
Aggregate A–32B	1.1%	11.8%	20	10	30/20
Aggregate B–32B	0.8%	8.5%	–	–	20/20

Appendix

Table 15: Negative and neutral hardware regimes. A dash denotes an unreported threshold, not zero.

LLM Inference

Large language model inference studies how models generate outputs efficiently, reliably, and securely across hardware and workloads.

See all 280 papers

WAKMan: Workload Aware KVCache Manager
Oct 26, 2026Suhas Kumar Morisetty, Vaibhavi Lokegaonkar, Sachin Mathew Varghese +1KV-Cache Management KV-Cache Eviction
Columbia University · University of Maryland, College Park · Capital One
Towards Distributed Inference of LLMs on a P2P Network
May 7, 2026Shabari S Nair, Krishanu SainiLLM Inference KV Caching
Department of Computer Science, The University of Texas at Austin.
KV-Repurpose: A Testbed for Evaluating Non-Prefix KV-Cache Reuse
Oct 9, 2026Taiga Ikeda, Daisuke Miyashita, Jun DeguchiKV-Cache Reuse KV-Cache Management
Kioxia Corporation, Japan

Oct 26, 2026J/K move · Enter open · S save

WAKMan: Workload Aware KVCache Manager

Suhas Kumar Morisetty, Vaibhavi Lokegaonkar, Sachin Mathew Varghese, Wesley Harris

Columbia University · University of Maryland, College Park · Capital One

KV-Cache Management KV-Cache Eviction Prefix Caching

Open paper AskPDF arXiv

Prefix caching enables a Large Language Model (LLM) servers to reuse the Key-Value (KV) states and accelerate prefill computation stage for requests that share a prefix with earlier prompts, thus reducing latency and serving cost. With limited memory resource, the KV cache eviction policy becomes a decisive factor in determining the overall benefits of prefix caching. Production traffic may have single-turn, multi-turn, agentic, or a mixture of any combination of these request types. Our findings indicate that agentic steps return within seconds and favor recency, while popular prompts and long conversations return after many other requests and favor frequency. Across 20 mixes, no single policy is always best: vLLM's default strategy LRU provides 12% higher cache hits as compared to the frequency-oriented S3FIFO on agentic-heavy mixes but trails it by up to 22% elsewhere, and even a single workload parameter can flip the winner even for any particular mix. We present WAKMan, a workload-aware KV cache manager that picks its eviction policy from live traffic without knowing request types or reading prompts. It improves hit rate over LRU by 5 percentage points on average, with the lowest mean and worst-case optimality gap of all policies.

Abstract

LLM Inference

Explore similar work

WAKMan: Workload Aware KVCache Manager

Towards Distributed Inference of LLMs on a P2P Network

KV-Repurpose: A Testbed for Evaluating Non-Prefix KV-Cache Reuse