Event-driven benchmark of prefix-aware request reordering policies for LLM serving, measuring the ROI trade-off between prefix hit rate, prefill savings, and added queueing delay.
Author: Joao Felipe De Souza Year: 2026
Concurrent KV-cache prefix sharing can reduce physical KV usage by 45 to 74 percent when requests with the same system prompt execute together. However, in practice, requests with the same prefix arrive at different times and are dispatched immediately under FCFS, missing sharing opportunities.
This benchmark asks:
- When is it worthwhile to delay requests to group same-prefix batches?
- What arrival rate and prefix popularity are required?
- How does shared prefix length affect the ROI breakeven?
- Do window and threshold policies differ meaningfully?
The central metric is:
roi_ratio = avg_saved_prefill_ms / avg_wait_ms
When roi_ratio >= 1, reordering earns more in prefill savings than it costs in queueing delay. This is the breakeven criterion used throughout.
- bursty_hotset: ROI 9.5 to 15.2
- ultra_hot_2 at 20 req/s: ROI 13.1 to 20.9
- hotset_2 at 4 req/s: ROI 0.5 to 1.0 (marginal)
- hotset_8, sharegpt, uniform_32: ROI well below 1
Increasing arrival rate from 4 to 20 req/s for a two-prefix workload improves hit rate from 12 to 46 percent and ROI from 0.54 to 10.3. The inter-arrival time within the same prefix family is the key variable.
ROI grows with shared prefix length even when hit rate decreases, because each match saves more prefill. For the 0.5B model, the ROI breakeven is between 64 and 256 shared prefix tokens. For the 1.5B model it is lower.
ROI is approximately 1.5 to 1.6 times higher on Qwen2-1.5B than Qwen2-0.5B across all workloads, because prefill cost and KV savings both scale with KV bytes per token.
At the same maximum wait budget, window policies deliver equal or slightly higher hit rates than threshold policies. Threshold adds complexity without significant benefit unless arrivals are naturally bursty.
Savings efficiency falls sharply beyond 50ms windows. The first 5ms of wait captures the best-quality groupings. Larger windows mostly add wasted wait.
Reordering is worthwhile when:
arrivals_per_prefix > 1 / window_ms
When the per-prefix arrival rate exceeds one request per window period, grouping is likely and ROI exceeds 1.
fcfs: No reordering. Baseline.
prefix_window: Hold requests for up to W ms per prefix bucket. Dispatch all accumulated same-prefix requests as a group on expiry.
eager_threshold: Dispatch when N requests accumulate or max_wait expires. Fires early when prefix is hot enough.
- hotset_2: 2 prefixes, 4 req/s, Poisson
- hotset_8: 8 prefixes, 4 req/s, Poisson
- uniform_32: 32 prefixes, 4 req/s, uniform distribution
- bursty_hotset: 4 prefixes, 4 req/s, bursty arrivals
- sharegpt_templates: 16 prefixes, 3.5 req/s, Zipf 1.8
- ultra_hot_2: 2 prefixes, 20 req/s, Poisson
- prefix_len_sweep: 2 prefixes, 10 req/s, varying prefix length
- prefix_hit_rate, grouped_request_frac, avg_group_size
- avg_wait_ms, p95_wait_ms, p99_wait_ms
- avg_ttft_ms, p95_ttft_ms, p99_ttft_ms
- avg_saved_prefill_ms, total_saved_prefill_ms
- avg_saved_kv_mb, total_saved_kv_mb
- roi_ratio, roi_positive
- saved_prefill_ms_per_wait_ms
- wasted_wait_frac, orphan_dispatch_frac
From the project directory:
cd ~/dev/request-reordering-cache-bench
source venv/bin/activate
python -u run.py
results/summary_v11.csv
results/dispatch_v11.csv
plots/
request-reordering-cache-bench/
|-- src/
| |-- __init__.py
| |-- config.py
| |-- workload.py
| |-- reordering.py
| |-- simulator.py
| |-- bench.py
| |-- analysis.py
|-- results/
|-- plots/
|-- run.py
|-- SUMMARY.txt
|-- DESIGN.md
|-- LICENSE
|-- README.md
|-- requirements.txt
|-- .gitignore
Request reordering for prefix sharing is a workload-sensitive optimization. It delivers strong positive ROI in high-rate concentrated workloads and negligible or negative ROI in diverse or low-rate workloads. Larger models and longer shared prefixes lower the ROI breakeven point. Window policies are simpler and equally effective as threshold policies.
MIT License. See LICENSE.