Binomial-thinning (s,S) capacity controller
Implementation & benchmark of arXiv:2607.28171 — The optimality of an (s, S) hiring policy on a workforce planning problem with fixed recruitment costs and binomial turnover
Source paper: The optimality of an (s, S) hiring policy on a workforce planning problem with fixed recruitment costs and binomial turnover arXiv:2607.28171 ⓘ · analyzed Aug 31, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Replace continuously fluctuating conditional-computation decisions with a fixed-charge (s,S) controller for the number of active experts or channel groups. If the currently provisioned capacity falls below s, activate capacity up to S; otherwise retain the current capacity, preventing repeated small routing or kernel-launch decisions. Binomial thinning models the random subset of provisioned experts or channels that are actually available after token load, dropout, failures, or admission limits.
Formulas
Mathematical statement
The key result is Lemma 6, preservation of discrete convexity under binomial thinning. A function f: Z -> R is discretely convex when its forward difference Delta f(n)=f(n+1)-f(n) is nondecreasing in n. Let xi_j be independent Bernoulli random variables with success probability gamma in [0,1], let Z^y=sum_{j=1}^y xi_j with Z^0=0, and define F(y)=E[f(Z^y)]. Since Z^(y+1)=Z^y+xi_(y+1), the proof obtains F(y+1)-F(y)=gamma E[f(Z^y+1)-f(Z^y)]=gamma E[Delta f(Z^y)], which is nondecreasing in y; hence F is discretely convex. For an ML controller, y is the number of provisioned experts or channel groups, Z^y is the random number available to process the current batch, and f(z) is the measured downstream loss plus latency or overflow cost when z units are available. Add a fixed activation cost K whenever y changes upward and a variable cost c per activated unit. The resulting fixed-charge objective has the (s,S) interpretation: below threshold s, activate up to S; at or above s, do nothing. The convexity result justifies estimating f on a discrete capacity grid and applying the stochastic availability transformation without destroying marginal-cost monotonicity.
Implementation notes
Integrate the controller into a sparse MoE layer or a conditional channel layer at inference time. Let a_t be the number of currently provisioned experts, let d_t be the token demand in the next batch, and let y_t be the number provisioned after a possible activation. First collect a calibration set and measure f_t(z): mean task loss or perplexity degradation plus latency and dropped-token penalty when exactly z experts are available. Estimate gamma_t as the empirical availability rate, gamma_t=(number of expert slots that successfully accept work)/(number provisioned slots), optionally conditioned on batch size. Construct F_t(y) from the paper's formula by Monte Carlo sampling Z from Binomial(y,gamma_t) and averaging the lookup-table values f_t(Z). Enforce discrete convexity by isotonic regression on the first differences F_t(y+1)-F_t(y). Use the fixed-charge objective C_t(y|a_t)=F_t(y)+c max(y-a_t,0)+K 1[y>a_t]+h max(a_t-y,0), where h penalizes unavailable capacity or dropped tokens. For each capacity y in a small grid, compute C_t and select the minimizing target S_t; define s_t as the largest current capacity for which activating to S_t is cheaper than retaining capacity. At runtime, measure a_t and demand d_t; if a_t<s_t, activate S_t-a_t experts or channel groups; otherwise keep the current set. Re-estimate gamma and f periodically, not per token. The paper supplies the binomial convexity calculation; gamma, f, K, c, and h are estimated empirically. The first experiment should use a 4- or 8-expert Switch-Transformer-style layer on WikiText-103 or C4, comparing this controller with greedy top-k routing plus per-batch capacity resizing. Measure perplexity, expert activation count, kernel launches, p50/p99 latency, and dropped-token rate. Success is lower activation and launch overhead at matched perplexity, with fewer oscillations in active capacity and no increase in overflow rate.
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.