Entropy-Recycling Categorical Sampler
Implementation & benchmark of arXiv:2607.13828 — Online Random Sampling with Real Probabilities
Source paper: Online Random Sampling with Real Probabilities arXiv:2607.13828 ⓘ · analyzed Aug 30, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Replace independent categorical sampling calls with a shared exact sampler carrying a reusable uniform integer state. After sampling category X from a distribution with CDF F, retain the unused portion of the underlying random interval as a new state (Z', M'), so later samples consume residual randomness instead of requesting fresh random bits. The expected random-bit cost should approach the sequence entropy rather than paying a fixed word or byte cost per sample.
Formulas
Mathematical statement
The paper's fair-die example demonstrates rejection recycling: ordinary rejection uses 4 expected coin flips for a six-sided die, while the mapping in (2) reuses the rejected final bit. The general construction represents the current random state as an integer Z uniformly distributed on {0,...,M-1}, where M is the state range and Z is the hidden random integer. For a categorical variable X with cumulative distribution function F, the conditional random value Q satisfies Q|X=x ~ Unif[F(x-1),F(x)], where F(x)=sum_{j<=x} p_j and p_x=P(X=j). The sampler scales the interval by 2^s M, choosing an integer s such that the width 2^s M(F(X)-F(X-1))=2^s M p_X lies in [Delta/4,Delta], with Delta a configurable maximum state size. The paper states the key conditional-uniformity identity (4): (2^s M Q | X,M) ~ Unif[2^s M F(X-1),2^s M F(X)]. It then chooses integers U^- and U^+ so that {U^-,...,U^+-1} is strictly inside this real interval, sets Z'=floor(2^s M Q)-U^- and M'=U^+-U^-, and obtains Z'|M' ~ Unif{0,...,M'-1} with M'<=Delta. Here Q is the latent uniform random variable, M is the incoming integer-state modulus, s is the scaling exponent, Delta is the state-size cap, U^- and U^+ are interior integer endpoints, and (Z',M') is the recycled state. The entropy guarantee is an expected total fair-coin cost of E[sum_i H(F_i)] + O(log n) for n outputs, where H(F_i)=-sum_x F_i(x)log_2 F_i(x).
Implementation notes
Integrate this at the categorical sampling primitive used by autoregressive decoding, diffusion categorical transitions, or an MoE router. Maintain one per-stream state (Z,M), initially Z=0 and M=1; conceptually this denotes a uniform real Q=(Z+U)/M with U uniform on [0,1), while the implementation stores only integers and requests fair random bits when M is too small. For each probability vector p and CDF F: (1) choose the sampled category X using the current state plus enough fresh bits to refine the implicit uniform interval until it lies in [F(X-1),F(X)); (2) choose s satisfying 2^s M p_X in [Delta/4,Delta], using p_X or a high-precision probability approximation; (3) compute a=2^s M F(X-1) and b=2^s M F(X), then set U^-=ceil(a+epsilon) and U^+=floor(b-epsilon)+1, with epsilon chosen conservatively from the CDF approximation error; (4) if U^+>U^-, set Z=floor(2^s M Q)-U^- and M=U^+-U^-; otherwise request additional random bits and retry with larger precision or a fallback independent sampler. Before every draw, normalize the integer state by extracting common powers of two: emit low random bits of Z when needed, replace (Z,M) by (floor(Z/2^k),M/2^k), and keep M<=Delta to guarantee O(log Delta) persistent bits. The mathematical quantities computed exactly are the interval scaling and interior integer bounds; in ordinary GPU code, F and p are estimated from float logits, so implement a tolerance margin based on a bound or empirical upper bound on CDF rounding error. First test on GPT-2-small generating 1,000-token sequences with temperature 0.7 and top-k=50. Compare multinomial sampling against this sampler using the same categorical distributions, measuring output-distribution agreement, random-bit calls, wall-clock overhead, and state memory. A successful result is at least 2-4x lower entropy-source consumption with statistically indistinguishable token frequencies and less than 10% decoding slowdown; on a true-randomness or secure-entropy implementation it should also reduce RNG-service calls and energy.
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.