Discrete-event simulation of KV-cache fragmentation dynamics in continuous batching LLM servers. Measures fragmentation growth over time and compares allocation and compaction policies across workload intensities and request size distributions.
Three prior projects studied KV-cache fragmentation statically:
- kv-cache-compaction-lab — how to defragment (ThresholdCompaction wins)
- paged-attention-sim — how paged allocation prevents fragmentation
- kv-cache-tiering-bench — where to move evicted blocks
None of them measured how fragmentation accumulates over time in a running server. This simulator closes that gap.
| Model | Workload | External frag after 60min |
|---|---|---|
| Qwen2-0.5B | light | 6% |
| Qwen2-0.5B | heavy | 44% |
| Qwen2-1.5B | medium | 44% |
| Qwen2-1.5B | heavy | 52% |
Under uniform heavy workload (0.5B):
| Policy | Throughput | Rejected |
|---|---|---|
| paged_16kb | 4.508 rps | 0 |
| contiguous_greedy | 4.508 rps | 0 |
| contiguous_none | 4.480 rps | 6 |
Under bimodal heavy_mixed workload (1.5B):
| Policy | Throughput | Rejected |
|---|---|---|
| contiguous_adaptive_q8 | 2.564 rps | 6865 |
| contiguous_none | 2.556 rps | 6891 |
| paged_16kb | 2.452 rps | 7267 |
| paged_64kb | 2.431 rps | 7341 |
Paged allocation eliminates external fragmentation but introduces internal fragmentation when request sizes vary widely. Short requests waste entire pages, blocking long requests from being admitted.
Under heavy_mixed workload (1.5B), vs contiguous_none baseline:
| Policy | Compactions | Comp ms total | Delta rejected | Efficiency |
|---|---|---|---|---|
| adaptive_q8 | 718 | 10943 | -26 (fewer) | +0.0024 |
| greedy_fail | 2422 | 33623 | +383 (more) | -0.0114 |
| threshold_015 | 2398 | 33568 | +245 (more) | -0.0073 |
Greedy compaction triggers so often under bimodal load that pause overhead dominates. Adaptive compaction with cooldown avoids this.
Maximum compaction_time_frac observed: 1.6%
The cost is not the pause itself. It is operating in a fragmented state before the compaction threshold is reached.
| Scenario | Best policy |
|---|---|
| 0.5B, uniform workloads | paged_16kb |
| 0.5B, heavy bimodal | contiguous_threshold_015 |
| 1.5B, uniform workloads | paged_64kb |
| 1.5B, heavy bimodal | contiguous_adaptive_q8 |
| Policy | Description |
|---|---|
| contiguous_none | No compaction. Fragmentation accumulates indefinitely |
| contiguous_greedy_fail | Compact on any allocation failure |
| contiguous_threshold_005/010/015 | Compact on failure only if frag >= threshold |
| contiguous_adaptive_q8/q16 | Proactive compaction when queue builds + cooldown |
| paged_16kb | 16KB fixed pages, no external frag, internal frag possible |
| paged_64kb | 64KB fixed pages, more internal frag per request |
git clone https://github.com/JohnScheuer/continuous-batching-fragmentation-sim
cd continuous-batching-fragmentation-sim
python3 -m venv venv
source venv/bin/activate
pip install -r requirements.txt
python run.py
Runtime: approximately 2-5 minutes on any modern CPU. No GPU required.
results/
timeseries.csv per-tick fragmentation, queue, live bytes
events.csv admit, reject, compact events
summary.csv aggregated metrics per (model, workload, policy)
policy_ranking.csv multi-objective ranking per scenario
compaction_efficiency.csv delta metrics vs contiguous_none baseline
plots/
01_fragmentation_over_time.png fragmentation growth
02_throughput_by_policy.png throughput by policy
03_queue_depth.png queue depth over time
04_frontier_external.png throughput vs fragmentation frontier
05_internal_vs_external_frag.png internal vs external frag comparison
continuous-batching-fragmentation-sim/
├── src/
│ ├── config.py models, workloads, policies, timing
│ ├── workload.py Poisson arrivals, lognormal length sampling
│ ├── allocator.py ContiguousAllocator, PagedAllocator
│ ├── policies.py compaction trigger logic
│ ├── simulator.py event-driven simulation loop
│ ├── bench.py sweep orchestration
│ └── analysis.py plots, ranking, efficiency CSV
├── results/
├── plots/
├── run.py
├── SUMMARY.txt
├── DESIGN.md
├── LICENSE
└── requirements.txt
- Python 3.10+
- NumPy >= 1.26.0
- Pandas >= 2.0.0
- Matplotlib >= 3.8.0
No GPU required.
- Real GPU memory allocation latency
- Request preemption or token-level eviction
- Multi-GPU or distributed KV caches
- Variable decode latency under load
- Hybrid allocation strategies
- DESIGN.md — full design rationale and module descriptions
- SUMMARY.txt — plain-text findings with all numbers
- LICENSE — MIT License
- kv-cache-compaction-lab
- paged-attention-sim
- kv-cache-tiering-bench
- sharegpt-workload-bench
- inference-time-scaling-bench
MIT License — Copyright (c) 2026 João Felipe De Souza
See LICENSE for details.
João Felipe De Souza