# Global-Shift Randomized Batching

- ID: 1911
- Canonical URL: https://synthcore.org/idea/1911/global-shift-randomized-batching
- API JSON: https://synthcore.org/api/idea/1911.json
- API Markdown: https://synthcore.org/api/idea/1911.md
- Verification status: unverified
- Source: [arXiv:2608.06796](https://arxiv.org/abs/2608.06796)
- Category: sampling
- Solves: speedup, stability, generalization
- ML areas: batching, inference-speedup, kv-cache
- Math tags: probability, combinatorics, optimization
- Ratings: usefulness 5/10; difficulty 3/10; novelty 7/10

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

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

## Key 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}.$$

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

## Disclaimer

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