Unverified 2026

Global-Shift Randomized Batching

Implementation & benchmark of arXiv:2608.06796 — Online Multi-Level Aggregation with Per-Batch Maximum Delay

Usefulness5/10

Difficulty3/10

Novelty7/10

Sampling Speedup Stability Generalization Batching Inference speedup Kv cache Probability Combinatorics Optimization

Source paper: Online Multi-Level Aggregation with Per-Batch Maximum Delay arXiv:2608.06796 ⓘ · analyzed Aug 31, 2026

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

Idea description

Sample one batching aggressiveness parameter once per serving epoch and use it for all busy periods, instead of independently randomizing every batch. This globally coupled randomness preserves nested batching behavior while preventing a fixed traffic pattern from repeatedly aligning with a deterministic timeout.

Formulas

$$f(\theta)=\frac{e^{\theta}}{e-1},\qquad 0\leq\theta\leq1.$$

$$h^{L}_{\theta}(i,j)=D_{L}(i,j)-(1-\theta)M(i,j).$$

$$\sum_{B\in P_{1}}D_{L}(B)=D_{L}(1,n)=\operatorname{OPT}.$$

$$\Theta\sim f(\theta),\qquad \text{use the same }\Theta\text{ for every busy period in one epoch}.$$

Mathematical statement

The paper constructs a nested family of partitions indexed by heta, where increasing heta delays service and can merge adjacent blocks but never splits an already formed block. It samples one global parameter with density f( heta)=e^ heta/(e-1) on 0\leq heta\leq1. The deterministic endpoint satisfies \sum_{B\in P_1}D_L(B)=D_L(1,n)=\operatorname{OPT}, where P_1 is the endpoint busy-block partition and D_L is the total interval-service-plus-maximum-delay cost. The adaptation uses the same global coupling: one \Theta is sampled per epoch, and all queue decisions use h_\Theta rather than drawing an independent threshold per request or per batch.

Implementation notes

Add this as a wrapper around the submodular batch timer or any existing dynamic microbatching policy. At the start of every serving epoch, such as every 5 minutes or after a major traffic-regime change, draw U uniformly from (0,1) and set Theta=log(1+(e-1)U), the inverse CDF of f(theta)=e^theta/(e-1). Do not resample Theta for individual requests. During each busy period, use Theta in the timer rule: estimate the cost of flushing now and the cost of waiting for the next request; continue waiting only when the predicted service saving exceeds (1-Theta) times the incremental oldest-request delay. Reset the active queue at idle periods but retain Theta until the epoch ends. Maintain a deterministic hard deadline so the randomized policy cannot violate an SLA. The mathematical quantities are the density and global coupling; hardware-specific M(B), arrival-rate forecasts, and marginal-cost estimates are empirical. First compare fixed thresholds, per-batch independent random thresholds, and this global-shift policy on replayed production-like traces with burst trains, periodic arrivals, and mixed short or long sequences. Use a small decoder model and identical maximum batch size. Record throughput, mean and p99 latency, batch-size variance, and SLA violations over many random seeds. The expected signal is lower worst-seed throughput variance and improved average throughput at the same p99 latency, especially on periodic or adversarially bursty traces; on stationary Poisson traffic it should at least match fixed-timeout batching.

Verification

This idea has not been verified yet.

Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.

Artifacts

Artifacts unavailable.