A simulation measuring how KV cache reuse evolves across turns in multi-turn LLM conversations, and how different routing strategies determine whether that reuse is captured or wasted.
For full methodology and design decisions see design.md.
In a multi-turn conversation, each assistant reply includes the full conversation history in its prompt. If two consecutive turns land on the same serving instance, the second turn can reuse the cached KV state of the first, saving significant prefill compute.
If the second turn lands on a different instance, that state is gone.
The question is: which routing policy best preserves this locality without causing load imbalance?
random Uniformly random. No locality. Baseline. least_load Route to shortest queue. Good balance, no locality. sticky_session All turns of a conversation go to the same instance. hybrid_sticky Sticky unless queue delay exceeds a threshold. cost_aware Per-request comparison: reuse saved vs queue penalty.
All strategies ranked by mean TTFT:
hybrid_5000ms 4602 16276 0.540 0.476 0.046 cost_aware_a0.25 4735 15987 0.366 0.260 0.039 hybrid_500ms 4766 16053 0.370 0.265 0.034 cost_aware_a1.0 4811 16181 0.351 0.237 0.037 least_load 4847 16252 0.349 0.233 0.033 sticky_session 5309 21674 0.771 0.719 0.077 random 7460 30855 0.382 0.279 0.058
Best strategy per objective:
Best mean TTFT: hybrid_5000ms (4602ms) Best p99 TTFT: cost_aware_a0.25 (15987ms) Best cache hit rate: sticky_session (0.771) Best load balance: cost_aware_a2.0 (imbalance=0.031)
Turn least_load sticky hybrid_5000ms cost_aware_a0.25 0 0.000 0.000 0.000 0.000 1 0.174 0.875 0.664 0.200 3 0.358 0.955 0.721 0.395 5 0.528 0.983 0.783 0.530 7 0.620 0.980 0.801 0.590
Sticky reaches 0.875 reuse by turn 1. Least-load reaches only 0.620 by turn 7. A routing miss at turn 2 permanently destroys accumulated locality.
Sticky routing maximizes reuse but hurts latency. 0.771 hit rate, but mean TTFT 15% worse and p99 33% worse than least-load.
Hybrid sticky with large threshold is the best for average latency. hybrid_5000ms retains 70% of sticky hit rate at 14% better mean TTFT.
Cost-aware routing gives the best tail latency. cost_aware_a0.25 achieves the lowest p99 (15987ms) with better imbalance than hybrid policies because it makes per-request tradeoff decisions.
Routing is a multi-objective problem. No single strategy dominates across mean TTFT, p99 TTFT, reuse, and balance.
Routing misses compound over turns. Once routed off the cached instance, a conversation cannot recover its KV state.
multi-turn-kv-reuse-bench/ ├── src/ │ ├── init.py │ ├── config.py │ ├── download.py │ ├── trace.py │ ├── workload.py │ ├── instance.py │ ├── router.py │ ├── simulator.py │ └── analysis.py ├── data/ ├── results/ ├── plots/ ├── LICENSE ├── design.md ├── README.md ├── requirements.txt └── run.py
python3 -m venv venv source venv/bin/activate pip install -r requirements.txt python run.py
Outputs: results/results.csv results/per_turn_results.csv results/summary.txt plots/reuse_vs_turn.png plots/pareto.png plots/cost_aware_sweep.png plots/strategy_comparison.png
Bridges three prior projects:
prefix-cache-sim: KV hit rate for independent requests sharegpt-workload-bench: real traffic is multi-turn conversations request-routing-sim: routing affects prefix cache hit rate
MIT License. See LICENSE for details.
Joao Felipe De Souza 2026