Discrete-event simulation benchmark for decode preemption policies in LLM serving.
When a server is running a long decode and an urgent prefill arrives, the scheduler must decide:
Let the decode finish and make the urgent request wait, or interrupt the decode and serve the urgent prefill immediately?
All prior scheduling benchmarks in this portfolio assume that a decode that starts will run to completion.
In production, this assumption fails under load:
- kv-cache-aware-scheduler: admits or rejects based on KV budget
- adaptive-batching-policy-bench: prefill vs decode composition
- continuous-batching-scheduler: FCFS and SJF without explicit preemption
- decode-preemption-bench: when to stop a decode to admit another request
| Workload | No-preemption urgent p95 TTFT | With preemption |
|---|---|---|
| long_decode_tail | 998 ms | < 12 ms |
| kv_pressure_urgent | 747 ms | < 12 ms |
| high_resume_prob | 417 ms | < 12 ms |
No-preemption fails standard and best-effort SLOs through long queueing. Any preemption policy clears queues faster and benefits all classes.
| Workload | Winner | Checkpoint overhead | Recompute overhead |
|---|---|---|---|
| high_resume_prob | checkpoint | 27 ms | 79 ms |
| low_resume_prob | checkpoint | 36 ms | 55 ms |
| urgent_prefill_injections | checkpoint | 25 ms | 76 ms |
| kv_pressure_urgent | recompute | 150 ms | 92 ms |
| long_decode_tail | recompute | 322 ms | 61 ms |
Recompute wins only when KV state is large relative to prefill cost.
| Policy | Urgent SLO | Standard SLO | Fairness ratio | Equitable |
|---|---|---|---|---|
| oldest_checkpoint | 1.00 | 1.00 | 1.00 | yes |
| oldest_recompute | 1.00 | 1.00 | 1.00 | yes |
| best_effort_first | 1.00 | 1.00 | 1.00 | yes |
| kv_pressure | 1.00 | 1.00 | 1.00 | yes |
| oracle_preemption | 1.00 | 0.34 | 17.69 | no |
| no_preemption | 0.84 | 0.17 | 16.73 | no |
Oracle destroys standard and best-effort SLOs to protect urgent requests. No-preemption is not fair either — it fails all classes through queueing.
Preempting the decode with the most remaining work creates the highest checkpoint overhead because it targets the largest KV states.
| Mechanism | Action | Cost |
|---|---|---|
| checkpoint | save KV state to CPU, reload on resume | checkpoint_bytes * cost_per_mb |
| recompute | discard KV state, re-run prefill on resume | prompt_len * prefill_ms_per_token |
| Policy | Kind | Selection criterion | Mechanism |
|---|---|---|---|
| no_preemption | baseline | none | none |
| oldest_checkpoint | heuristic | oldest decode | checkpoint |
| oldest_recompute | heuristic | oldest decode | recompute |
| longest_remaining_checkpoint | heuristic | most remaining tokens | checkpoint |
| best_effort_first_checkpoint | heuristic | best-effort class first | checkpoint |
| kv_pressure_checkpoint | heuristic | only when KV > 75% full | checkpoint |
| oracle_preemption | oracle | ROI-aware net gain > 0 | checkpoint |
| Workload | Description |
|---|---|
| high_resume_prob | requests frequently resume after preemption |
| low_resume_prob | most preempted requests are abandoned |
| long_decode_tail | heavy-tail output length distribution |
| kv_pressure_urgent | KV cache constrained, high arrival rate |
| urgent_prefill_injections | frequent urgent short requests |
| premium_interrupts | high fraction of premium-urgency arrivals |
cd ~/dev/decode-preemption-bench
python3 -m venv venv
source venv/bin/activate
pip install -r requirements.txt
python -u run.py
Runtime: approximately 2-3 minutes. No GPU required.
results/
summary.csv
decision_map.csv
breakeven_analysis.csv
fairness_analysis.csv
fairness_summary.csv
operational_recommendations.csv
plots/
01_urgent_ttft_p95.png
02_preemption_overhead.png
03_slo_by_urgency.png
04_value_score.png
05_tradeoff.png
06_breakeven.png
07_fairness.png
08_operational_recs.png
09_fairness_summary.png
decode-preemption-bench/
+-- src/
| +-- config.py
| +-- workload.py
| +-- server.py
| +-- bench.py
| +-- analysis.py
+-- results/
+-- plots/
+-- run.py
+-- README.md
+-- summary.txt
+-- design.md
+-- LICENSE
+-- requirements.txt
This project is a calibrated discrete-event simulation.
Each tick represents one batch step. The server processes one prefill or one decode token step per tick. When an urgent request arrives and the batch is full, the preemption policy decides whether to interrupt a running decode.
Costs are calibrated from prior benchmarks:
Checkpoint/reload cost: from kv-cache-tiering-bench
Prefill cost: from serving-cost-model-v2
KV bytes per token: from disaggregated-prefill-decode-sim
For full design details, see design.md.
- Python 3.10+
- NumPy >= 1.26.0
- Pandas >= 2.0.0
- Matplotlib >= 3.8.0
No GPU required.
If you need a default decode preemption policy:
- use oldest_checkpoint as the default in high resume probability workloads
- switch to oldest_recompute when output lengths are heavy-tailed
- use kv_pressure_checkpoint for selective preemption under KV constraints
- avoid longest_remaining preemption in any scenario
- avoid oracle-style preemption unless fairness is not a concern
- design.md -- detailed design rationale and modeling assumptions
- summary.txt -- concise high-level summary of findings
- LICENSE -- MIT License
MIT License -- Copyright (c) 2026 Joao Felipe De Souza
Joao Felipe De Souza 2026