✗ Failed on benchmark 2026

Fairness-Budgeted Short-Job Insertion

Implementation & benchmark of arXiv:2608.02244 — Efficiency and Cost Alignment in Batched LLM Serving via Resource-Fair Scheduling

Usefulness7/10

Difficulty4/10

Novelty6/10

Memory Speedup Memory Scalability Kv cache Batching Inference speedup Optimization Combinatorics Theory

Source paper: Efficiency and Cost Alignment in Batched LLM Serving via Resource-Fair Scheduling arXiv:2608.02244 ⓘ · analyzed Aug 31, 2026

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

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.

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}$$

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$.

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

Failed on benchmark

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Not reproduced ✗

Stage 2 · Practical benchmark result: No measurable effect

Methodology: 8 paired seeds, permutation test (p<0.05) against a learning-rate-tuned baseline. How verification works

Stage 1 — Mechanism check agent confidence 8/10

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.

Agent confidence: 8/10

Baseline: FCFS: mixed throughput 7.506, p99 latency 409, mean footprint range 69.461; adversarial throughput 7.660, p99 latency 914, mean footprint range 45.540.
Idea: Best mixed fairness gamma=0.75: throughput 7.251 (96.59% of FCFS), p99 latency 453, mean footprint range 8.157 (88.26% reduction). Adversarial fairness: throughput 7.536 (98.38% of FCFS), p99 latency 890 (-24 steps), mean footprint range 0.480 (98.95% reduction). Math: observed CR minimum gamma=0.500, CR=0.750; endpoint CR at gamma=.001/.999=0.999002; transition errors 0.

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.

How to run: python3 fairness_experiment.py

Stage 2 — Benchmark vs. tuned baseline (arXiv:2608.02244) Sep 2, 2026

No significant difference vs. the tuned baseline (+1.1%, p=0.6864, wins 3 / 8 paired seeds).

Benchmark: Request_footprint_regression
Model: mlp_custom
Paired seeds: 8
Baseline mean: 354.125
Idea mean: 358.0121
Effect (Δ): 3.8871 (+1.1%; negative = idea better)
Wins: 3 / 8 paired seeds
p-value: 0.6864 (permutation test, 20 000 shuffles)
Smallest detectable effect: ±5.5%
Mechanism: Not confirmed ✗
Practical effect: No effect
Baseline tuning: swept over 3 configs

Limitations:

The report track is not registered in the shared bench and therefore is explicitly invalid as registered-track evidence. No valid built-in or already-registered custom track matches inference-time request admission/KV-cache scheduling. The experiment does not measure real LLM serving throughput, decode latency, KV memory, arrival latency, or FLOPs. Directly calling validate_and_promote would write to /home/maxwelhelp/all/math2nn/bench/custom_tracks, prohibited by the read-only requirement.

How to run: python3 fairness_bench.py

Verdict computed by deterministic test code from paired-seed statistics — not by the language model.

Stage 2 — Benchmark Aug 31, 2026 latest Failed ✗

Agent confidence: 10/10

The valid stage-2 transfer could not be rerun under the stated constraints because no registered built-in or custom track represents inference scheduling, and direct promotion would modify the read-only bench. The available eight-seed local proxy showed no significant benefit anyway: fairness MSE was slightly worse than the tuned baseline and the mechanism signature was not confirmed. This result must not be interpreted as a valid registered-track refutation.

Baseline: Local proxy only: tuned unrestricted MLP batching, lr=0.01, mean test MSE 354.125 across 8 seeds.
Idea: Local proxy only: fairness grouping, lr=0.01 gamma=0.75, mean test MSE 358.012 across 8 seeds; paired delta +3.887, permutation p=0.68635.

Benchmark result