# Fairness-Budgeted Short-Job Insertion

- ID: 1700
- Canonical URL: https://synthcore.org/idea/1700/fairness-budgeted-short-job-insertion
- API JSON: https://synthcore.org/api/idea/1700.json
- API Markdown: https://synthcore.org/api/idea/1700.md
- Verification status: failed_benchmark
- Source: [arXiv:2608.02244](https://arxiv.org/abs/2608.02244)
- Category: memory
- Solves: speedup, memory, scalability
- ML areas: kv-cache, batching, inference-speedup
- Math tags: optimization, combinatorics, theory
- Ratings: usefulness 7/10; difficulty 4/10; novelty 6/10

## Idea description

Replace unrestricted continuous batching with a fairness-constrained scheduler that only inserts a waiting request when its predicted decode footprint remains within a normalized distance of the longest request already in the batch. The fairness budget should be tuned away from the mathematically worst midpoint and validated against real arrival distributions, with the goal of reducing wasted max-driven decode work without falling back to inefficient one-request-at-a-time serving.

## Mathematical statement

The paper defines the normalized fairness parameter \(\gamma=\alpha/o_1\in(0,1)\), where \(\alpha\) is the permitted disparity in decode progress or KV-cache footprint among co-batched jobs and \(o_1\) is the footprint or decode-progress scale of the longest job in the relevant batch. For batch size \(B\ge 2\), its worst-case competitive-ratio lower bound is \(\mathrm{CR}(\gamma)=\frac{1+\gamma}{1+2\gamma}\) for \(0<\gamma\le 1/2\), and \(\mathrm{CR}(\gamma)=\frac{2-\gamma}{3-2\gamma}\) for \(1/2\le\gamma<1\). Here \(\mathrm{CR}\) compares the throughput or efficiency of the fairness-constrained policy with the offline optimum. The curve is strictly decreasing up to \(\gamma=1/2\), strictly increasing afterward, has minimum \(3/4\) at \(\gamma=1/2\), and tends to \(1\) as \(\gamma\to0^+\) or \(\gamma\to1^-\). In an LLM server, let \(\ell_i\) be the current KV-cache token length of request \(i\), \(\hat r_i\) its predicted remaining decode tokens, and \(o_1=\max_i(\ell_i+\hat r_i)\) the predicted maximum lifetime footprint. Implement the practical admission constraint \((\ell_j+\hat r_j)-\min_{i\in S}(\ell_i+\hat r_i)\le\alpha=\gamma o_1\) for a candidate request \(j\) and active batch \(S\), or equivalently require the range of predicted footprints in the proposed batch to be at most \(\alpha\).

## Key formulas

- $$\gamma=\frac{\alpha}{o_1}\in(0,1)$$
- $$\mathrm{CR}(\gamma)=\begin{cases}\dfrac{1+\gamma}{1+2\gamma},&0<\gamma\leq\tfrac{1}{2},\\[4pt]\dfrac{2-\gamma}{3-2\gamma},&\tfrac{1}{2}\leq\gamma<1,\end{cases}$$
- $$\min_{i\in S\cup\{j\}}(\ell_i+\hat r_i)\geq\max_{i\in S\cup\{j\}}(\ell_i+\hat r_i)-\alpha,\qquad \alpha=\gamma o_1$$
- $$\mathrm{score}(j)=\frac{\text{estimated useful tokens completed by admitting }j}{\text{additional decode FLOPs caused by }j}\quad\text{subject to the fairness constraint}$$

## Implementation notes

(1) Integration point: modify the continuous-batching admission step in a vLLM- or TGI-style decoder, immediately before a waiting request is appended to the active decode batch. Do not change attention kernels or model weights. Maintain for every active and queued request its current KV-cache length \(\ell_i\), predicted remaining output length \(\hat r_i\), arrival time, and whether it is prefill- or decode-bound. Define the predicted lifetime footprint \(p_i=\ell_i+\hat r_i\). (2) Pseudocode: `active=S; while serving: run_one_decode_step(S); remove_finished(S); recompute p_i; o1=max(p_i for i in S) if S else 1; alpha=gamma*o1; candidates=waiting requests ordered by short predicted p_i then arrival time; for j in candidates: proposed=S+[j]; if max(p_i for i in proposed)-min(p_i for i in proposed) <= alpha and KV_capacity(proposed) <= GPU_budget: admit j; else defer j; stop when the next candidate fails or the token batch limit is reached`. If the queue is empty or a request waits beyond a timeout, allow a controlled override to prevent starvation. (3) Compute \(p_i\) from max_tokens minus generated_tokens, an exponential moving average conditioned on prompt length, or a small calibrated length predictor; log prediction error separately. Estimate actual batch cost with \(\max_i\ell_i\) and measure added KV-cache allocation directly. The paper-supplied mathematics determines the fairness rule and piecewise \(\mathrm{CR}(\gamma)\); length prediction, timeout, and tie-breaking are empirical. Sweep \(\gamma\in\{0.05,0.1,0.25,0.5,0.75,0.9,0.98\}\), because the theorem predicts the weakest worst-case guarantee at \(\gamma=0.5\), while real workloads may prefer an endpoint or another interior value. (4) First experiment: use a 7B decoder-only model on ShareGPT or synthetic mixed-length arrivals, comparing FCFS continuous batching, unrestricted shortest-job-first, and this scheduler on the same GPU and maximum batch-token budget. Measure tokens per second, GPU decode milliseconds per generated token, peak KV memory, p50/p95/p99 latency, deadline misses, and empirical footprint disparity \(\max_i p_i-\min_i p_i\) within each batch. The method succeeds if it lowers decode time and peak KV memory versus FCFS while retaining at least 95% of FCFS throughput and reducing p99 latency for short requests. Also test alternating short/long adversarial arrivals and compare the observed throughput ratio with the theoretical \(\mathrm{CR}(\gamma)\) curve.

## Verification

- Status: failed_benchmark
- Mechanism evidence: yes
- Mechanism confirmed: no
- Practical verdict: no_effect
- Verdict: Built a reproducible discrete continuous-batching simulator with FCFS, SJF, and fairness-budgeted insertion, plus three quantitative math checks. The theorem minimum was observed at gamma=0.500 with CR=0.750, symmetry error was 0, and all admission transition thresholds matched predictions exactly. In the adversarial workload, fairness reduced footprint disparity by 98.95% while retaining 98.38% of FCFS throughput and improving p99 latency by 24 steps; on mixed arrivals, gamma=0.75 reduced disparity by 88.26% with 96.59% throughput retention, though p99 latency worsened.

### Mechanism check

- Verdict: Built a reproducible discrete continuous-batching simulator with FCFS, SJF, and fairness-budgeted insertion, plus three quantitative math checks. The theorem minimum was observed at gamma=0.500 with CR=0.750, symmetry error was 0, and all admission transition thresholds matched predictions exactly. In the adversarial workload, fairness reduced footprint disparity by 98.95% while retaining 98.38% of FCFS throughput and improving p99 latency by 24 steps; on mixed arrivals, gamma=0.75 reduced disparity by 88.26% with 96.59% throughput retention, though p99 latency worsened.
- Confidence: 8/10
- Limitations: This is a CPU toy simulator, not a real LLM, GPU KV-cache, or vLLM/TGI integration. It uses synthetic arrivals, simple noisy length predictions, a fixed batch size of 8, and a timeout override; it does not measure GPU memory, decode FLOPs, wall-clock kernel speed, or real ShareGPT latency distributions.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.68635
- Paired wins: 3/8
- Benchmark verdict: no significant win

## Artifacts

- [bench_report.json](https://synthcore.org/code/628/bench_report.json)
- [fairness_bench.py](https://synthcore.org/code/628/fairness_bench.py)
- [fairness_experiment.py](https://synthcore.org/code/628/fairness_experiment.py)
- [report.md](https://synthcore.org/code/628/report.md)
- [report_bench_2026-08-31T201006.md](https://synthcore.org/code/628/report_bench_2026-08-31T201006.md)
- [results.json](https://synthcore.org/code/628/results.json)
- [Download all files as ZIP](https://synthcore.org/download/628)

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.