sequence-packing-bench

Benchmark of sequence packing and length-aware batching for variable-length LLM requests, measuring compute waste from padding and the latency-efficiency trade-off between offline and online grouping policies.

Author: Joao Felipe De Souza Year: 2026

---

Overview

Batching variable-length sequences wastes compute because shorter sequences are padded to the longest sequence in the batch. In realistic LLM traffic this can waste 67 to 87 percent of processed tokens.

This benchmark measures how much of that waste can be recovered by:

• offline sorting by sequence length
• bucketed padding
• exact token-budget packing
• online bucketed and packed batching under max_wait constraints

---

Main Findings

1. Padding waste is severe in realistic workloads

• ShareGPT-like traffic: 87.2% waste at batch size 32
• Heavy-tail traffic: 86.8% waste at batch size 32
• Coding-mixed traffic: 82.2% waste at batch size 32

2. Offline sorted padding is nearly optimal but unrealistic

Sorted-length padding recovers 98 to 99 percent efficiency in all high-variance workloads, but requires future knowledge of request lengths. It is a theoretical upper bound, not a production policy.

3. Online bucketed batching is the practical winner

In online serving with 250ms maximum wait:

• ShareGPT: 95.4% efficiency at +301ms p99 TTFT
• Heavy-tail: 95.2% efficiency at +421ms p99 TTFT
• Bimodal short-long: 90.7% efficiency at +545ms p99 TTFT

4. Online best-fit packing underperforms bucketed batching

Online best-fit collapses in high-variance workloads because oversize sequences force singleton fallback and partial packs waste token budget.

5. Low-variance workloads do not benefit from packing

uniform_short is the negative case:

• naive_online: 100% efficiency, p99 TTFT 80ms
• bucketed_online: 82.6% efficiency, p99 TTFT 472ms

When sequence lengths are already similar, grouping adds latency without meaningful compute savings.

---

Policies

Offline

• naive_padding
• sorted_length_offline
• bucketed_padding
• packed_first_fit_offline
• packed_best_fit_offline

Online

• naive_online
• bucketed_online
• packed_ff_online
• packed_bf_online

---

Practical Recommendations

• Low variance (CV < 0.5): use naive batching
• Medium variance (0.5 <= CV <= 1.5): use bucketed padding
• High variance (CV > 1.5): use bucketed online batching with timeout
• Do not use online best-fit packing under heavy-tail traffic

---

Metrics

• packing_efficiency
• padding_waste_frac
• avg_fill_frac
• throughput_gain_pct
• avg_ttft_ms, p95_ttft_ms, p99_ttft_ms
• avg_wait_ms, p99_wait_ms
• oversize_seq_frac
• length CV and tail statistics

---

Running

Offline benchmark:

cd ~/dev/sequence-packing-bench
source venv/bin/activate
python -u run.py

Online benchmark:

python -u run_online.py

---

Output Files

results/summary.csv
results/summary_online.csv
plots/

---

Project Structure

sequence-packing-bench/
|-- src/
|   |-- __init__.py
|   |-- config.py
|   |-- workload.py
|   |-- packing.py
|   |-- online_scheduler.py
|   |-- simulator.py
|   |-- bench.py
|   |-- bench_online.py
|   |-- analysis.py
|   |-- analysis_online.py
|-- results/
|-- plots/
|-- run.py
|-- run_online.py
|-- SUMMARY.txt
|-- DESIGN.md
|-- LICENSE
|-- README.md
|-- requirements.txt
|-- .gitignore

---

Conclusion

Sequence packing is only worthwhile in high-variance workloads. Offline sorting is an important upper bound but is not deployable in production. In real online serving, bucketed padding with a bounded wait timeout is the best practical compromise, recovering 90-95% efficiency in heavy-tail traffic while keeping p99 TTFT within a controllable range.

---

License

MIT License. See LICENSE.