Stratified Parallel Decoding: Randomized Quasi-Monte Carlo for Best-of-N Reasoning

When a language model is given extra compute at test time, the most common approach is to draw $N$ independent answers and then pick one, either by majority vote or with a scoring model. Independence is wasteful. Independent samples clump: the same likely opening gets drawn again and again, while plausible alternative openings are never tried. Randomized quasi-Monte Carlo (RQMC) addresses exactly this problem in numerical integration. It replaces independent random numbers with point sets that are spread evenly by construction, then randomized so that each point on its own is still perfectly random. The proposal is to swap the random number generator of parallel decoding for a randomized one-dimensional lattice over the space of whole sequences. Each of the $N$ outputs is still an exact sample from the model. Jointly, the $N$ outputs have a hard guarantee against redundancy: any reasoning prefix gets a number of samples that differs from its expected share by less than one.

The change needs no training, no extra model, and no hand-tuned thresholds. It adds a few bits of state per sequence. Because RQMC estimators stay unbiased and come with honest error bars from independent re-randomizations, the same construction also gives calibrated stopping rules for self-consistency. That lets the system decide when it has sampled enough, a decision that inference-time compute scaling currently makes with heuristics.

Core Claim

Any autoregressive sample can be generated from a single uniform number $u \in [0,1)$ by arithmetic-coding-style inversion. At each step $t$, the vocabulary is laid out as consecutive subintervals of the current interval, each with width proportional to the model's conditional probability. The next token is whichever subinterval contains $u$, and that subinterval becomes the new current interval. The prefix $x_{1:t}$ therefore owns an interval of length exactly $p(x_{1:t})$.

We draw one random shift $U \sim \text{Uniform}[0,1)$ and assign sample $i$ the number

$$u_i = (U + i/N) \bmod 1, \qquad i = 0,\dots,N-1.$$

Each $u_i$ is marginally uniform, so each decoded sequence is distributed exactly as $p$. The points are spaced $1/N$ apart, so the number of samples $n(x_{1:t})$ landing in the interval of any prefix satisfies

$$\lfloor N\,p(x_{1:t}) \rfloor \;\le\; n(x_{1:t}) \;\le\; \lceil N\,p(x_{1:t}) \rceil .$$

In words, two samples can share a prefix only if that prefix has probability above roughly $1/N$. Duplicated full solutions therefore occur only for genuinely dominant modes, and they occur in proportion to their mass.

Under independent sampling, the count in a prefix is binomial. A prefix of mass $5/N$ is missed with probability about $e^{-5}$, and prefixes of mass $0.5/N$ are routinely hit two or three times. Our claim is that removing this binomial noise raises pass@N and majority-vote accuracy at fixed $N$ without changing the distribution of any individual sample. It also reduces the variance of vote-share estimates enough to cut the tokens needed for confident early stopping.

This guarantee is combinatorial, not analytic. That is why the approach sidesteps the main obstacle the file identifies for RQMC in reasoning: correctness is a discontinuous, step-like function. Classical accelerated RQMC rates require smooth integrands (Quasi-Monte Carlo Variational Inference proves near-$O(N^{-2})$ mean squared error only for regular integrands). Discontinuities degrade those rates, as seen with barrier options in LLM-Guided Evolutionary Program Synthesis for Quasi-Monte Carlo Design. We do not rely on those rates. We rely only on the fact that a shifted one-dimensional lattice stratifies every interval.

The design also avoids the curse of dimensionality that Policy Learning and Evaluation with Randomized Quasi-Monte Carlo and Sequential Quasi-Monte Carlo flag for long trajectories. Rather than spending one quasi-random dimension per token, it collapses the whole sequence into one dimension. This plays the same role that Hilbert-curve sorting plays in sequential quasi-Monte Carlo.

Relation to Prior Work

The work closest in spirit is Antithetic Noise in Diffusion Models. It pairs Gaussian noises $(z,-z)$ and uses scrambled Sobol' sequences to narrow uncertainty intervals for diffusion models, VAEs, and normalizing flows. It relies on an approximate antisymmetry of continuous score functions, and it does not treat discrete tokens or reasoning.

Our construction is the discrete counterpart. The $N=2$ case of our lattice, $(u, u+1/2)$, is the natural antithetic pair for categorical inversion, and it will serve as an ablation.

Sequential Quasi-Monte Carlo supplies the method-level precedent. It writes each state transition as a deterministic function of a previous state and a uniform variate, then orders particles along a space-filling curve so that low discrepancy survives resampling. We reuse the "deterministic function of a uniform" view and replace the space-filling curve with the lexicographic order of the arithmetic code.

Cache Coherent Resampling for Efficient Test Time Scaling in LLM Reasoning via Adaptive Sequential Monte Carlo motivates the project. It runs parallel reasoning particles with fast cache-reordering resampling and consensus-based early exit, and it reports that particles still collapse into identical traces. It proposes heuristic rejuvenation as the fix, while all of its proposals remain pseudo-random. We attack collapse at the proposal step.

The file lists no LLM paper that uses low-discrepancy sampling. However, the arithmetic-coding view of sequence sampling is known in the decoding literature. A literature check on code-book-style parallel decoding is therefore the first task, and our contribution should be judged on two things. The first is pairing the construction with RQMC error estimation for adaptive compute. The second is a systematic test on long-chain reasoning models.

Two lines of heuristic diversity methods constrain the design.

Both change which sequences are sampled and are therefore biased relative to the model's distribution, which makes their vote shares uninterpretable as probabilities. Our method changes only how the $N$ samples are coupled. It can in principle be stacked under either one.

Research Program

Sampler. The first deliverable is a sampler plug-in for a standard serving stack. Each sequence carries a residual uniform and the current interval endpoints, and each step selects the token whose cumulative-probability bin contains the residual. The step applies after the usual temperature, top-p, and top-k processing, so it targets whatever truncated distribution the user already runs.

Numerical precision is not a real obstacle. Conditional on landing in an interval, the rescaled position is exactly uniform. Once a prefix's mass falls below about $1/(4N)$, no other sample can share it, and the sequence can switch to fresh independent randomness with no loss of exactness or of the guarantee. Only about $\log_2 N$ plus a few dozen bits of precision are ever needed.

Token ordering. Stratification holds for any ordering of the vocabulary within a step, but the variance of vote estimates depends on whether nearby intervals lead to similar answers. We will compare three orderings: raw vocabulary order, probability-sorted order, and an embedding-based order.

Stopping rule. The second deliverable uses $R$ independent random shifts (for example $R=4$ blocks of $N/R$ samples). The spread across blocks gives an unbiased variance estimate for each answer's vote share. Sampling continues until a confidence interval on the margin between the top two answers excludes zero. This replaces the consensus heuristic in ASMC's early exit with an interval whose validity follows from RQMC's unbiasedness.

Theory. The third deliverable is a short analysis. It bounds the miss probability for any prefix of mass $p$: zero if $p \ge 1/N$, and $pN$ otherwise, versus $(1-p)^N$ under independence. It also bounds the variance of vote shares in terms of how answer identity varies across the sequence-level interval. That quantity plays the role that Hardy-Krause variation plays in classical RQMC. The "best of both worlds" split in Quasi-Monte Carlo Beyond Hardy-Krause, which divides the error into a Monte Carlo-rate rough part and a QMC-rate regular part, suggests the right way to phrase the bound. We do not need their construction, which draws from $n^2$ candidate points.

Baselines

Independent sampling. The naive reference is ordinary independent sampling at the same temperature and truncation, with the same $N$, used for pass@N, majority vote (self-consistency), and verifier-ranked best-of-N as in Training Verifiers to Solve Math Word Problems. That paper showed a verifier-equipped 6B model at about 35% on GSM8K, matching a fine-tuned 175B model at about 33%. The file gives no reported number for plain best-of-N or self-consistency at a specific $N$ on MATH-500, so we will produce our own curves with identical prompts, models, and sampling settings. Beating this baseline means a statistically significant gain in pass@N and majority@N at matched $N$ and matched per-sample accuracy. The per-sample match is the check that the distribution is unchanged.

Adaptive Sequential Monte Carlo. The strongest existing parallel method is ASMC from Cache Coherent Resampling for Efficient Test Time Scaling in LLM Reasoning via Adaptive Sequential Monte Carlo. It reports 80.6% exact-match accuracy on MATH-500 with Qwen2.5-Math-7B at a 128× compute budget, with 73.7 s p95 latency. We will run it on the same model and budget, both unchanged and with our stratified proposals substituted for its pseudo-random ones. Beating it means higher accuracy at equal generated tokens, or equal accuracy with fewer tokens under our stopping rule.

Latent optimization. For context we cite $\nabla$-Reasoner: LLM Reasoning via Test-Time Gradient Descent in Latent Space, which reports 71.2% greedy rising to 80.4% on MATH-500 with Qwen-2.5-7B-Instruct and up to 40.2% fewer model calls than Best-of-8. We treat it as a different compute axis rather than a head-to-head competitor.

Heuristic diversity. DTS will be reimplemented with its published thresholds on DeepSeek-R1-Distill-Qwen 1.5B and 7B. The file reports only DTS's average 14% gain across models and datasets, not per-benchmark numbers.

Ablations. The key ablations isolate the one-dimensional sequence-level stratification.

  • Multi-dimensional Sobol'. Owen-scrambled Sobol' points with one dimension per token position. This is the naive "just use RQMC" design, and it should lose the prefix guarantee beyond the first few tokens.
  • Antithetic pairs. The $N=2$ antithetic special case.
  • Stratify only the first token.
  • Random vocabulary ordering. This should preserve redundancy gains but not the variance gains on vote estimates.

All methods share one tuning budget for temperature and top-p, chosen on held-out MATH training problems.

Why not just…?

Why not just raise the temperature or tune top-p for diversity? Higher temperature spreads samples by changing the target distribution, which lowers per-sample accuracy and distorts vote shares. Our method holds the distribution fixed and removes only the clumping. The experiment plots pass@N against per-sample accuracy across temperatures for both samplers. If independent sampling at some temperature lies on or above our curve, the idea fails. We expect the two approaches to compose, with stratification helping at every temperature.

Why not just deduplicate, or sample without replacement? This is the real threat. Rejecting exact duplicates, or sampling sequences without replacement, also stops the dominant answer from being redrawn. But exact-duplicate removal misses near-duplicates that share a long prefix and differ only in wording, and those are the redundancy that DTS: Enhancing Large Reasoning Models via Decoding Tree Sketching and ASMC describe. Sampling without replacement also breaks the unbiasedness of vote shares unless it is reweighted. We will run both as baselines, measuring pass@N, majority@N, and the calibration of vote shares against held-out accuracy. If deduplication matches us on all three, the contribution shrinks to the stopping rule.

Why not just use entropy-triggered branching or embedding-based pruning? DTS and ETS can target diversity more aggressively than any sampler faithful to the distribution. They also need per-model thresholds, an external encoder, or an optimization solver, and they give up the probabilistic meaning of counts. We will report both head-to-head and stacked comparisons: our sampler run inside DTS's branch points, and inside ETS's expansion step. If stacking gives no gain, the heuristics already capture the benefit.

Why not just rely on systematic resampling inside SMC? Systematic resampling is itself a one-dimensional stratification, but it acts only on particles that already exist. When all particles share a prefix, resampling cannot restore diversity. Stratified proposals act before collapse happens. Tracking effective sample size, which Cache Coherent Resampling for Efficient Test Time Scaling in LLM Reasoning via Adaptive Sequential Monte Carlo links to incorrect answers, will show whether collapse is delayed.

Proposed Experiments

Setup. Models are Qwen2.5-Math-7B, DeepSeek-R1-Distill-Qwen 1.5B and 7B, and AceReason-Nemotron-14B. Benchmarks are MATH-500 and GSM8K from Measuring Mathematical Problem Solving With the MATH Dataset and Training Verifiers to Solve Math Word Problems, plus AIME 2024/2025 and GPQA-Diamond, for $N \in \{4,8,16,64,128\}$. Every configuration is repeated over 20 random shifts so that variance, not just the mean, is measured.

Metrics. - pass@N, majority@N, and verifier best-of-N. - The number of distinct final answers. - Prefix redundancy, defined as the mean length of the longest shared prefix between sample pairs. - The variance of vote-share estimates across repeats. - For the adaptive rule, tokens to decision against accuracy, compared with ASMC's consensus exit and with bootstrap intervals under independent sampling.

Decisive checks. Three results matter most.

  1. Exactness. Per-sample accuracy and the answer histogram, pooled over repeats, must match independent sampling. This is a correctness test of the implementation.
  2. Where the gain appears. The pass@N gain should be largest on problems where the model's answer depends on early, moderately likely forks. We will test this by measuring, from independent samples, how much probability mass sits in prefixes of mass between $1/(10N)$ and $10/N$. If gains do not track this quantity, the stratification story is wrong even if accuracy improves.
  3. Long chains. On long-trace AIME runs, where the effective dimension is unclear, we will check whether the one-dimensional lattice beats per-token Sobol' points. If per-token Sobol' matches it, the dimension-collapsing argument is not doing the work.