QuasiMoTTo: Quasi-Monte Carlo Test-Time Scaling
July 01, 2026
Abstract
Scaling inference compute, by generating many parallel attempts per problem, is a costly but reliable lever for improving language model capabilities. By default these attempts are generated independently, wasting inference compute on redundant solutions. This waste seems unavoidable. After all, independence is what makes parallel sampling trivial to scale. However, this tradeoff is not fundamental: there is a rich design space of samplers that generate correlated but exact samples entirely in parallel. We explore this design space as an avenue for improving sample efficiency in scaling inference compute and reinforcement learning (RL). Concretely, we introduce QuasiMoTTo, which uses correlated samples as a drop-in replacement for i.i.d. samples. To generate these samples, QuasiMoTTo uses a reparameterization of autoregressive sampling as inverse-CDF sampling and draws the underlying uniforms with quasi-Monte Carlo (QMC); because QMC spreads the uniforms out more evenly than i.i.d., the resulting samples cover the output space with far less redundancy. Even though the batch is correlated, each sample is marginally distributed according to the language model, so we can use the batch for policy-gradient training. Our empirical analysis focuses on understanding how efficiently QuasiMoTTo can turn compute into performance. To evaluate correlated samplers, whose dependence breaks standard pass@\(k\) estimators, we first develop an unbiased bootstrap estimator. Across four reasoning benchmarks, QuasiMoTTo matches i.i.d. pass@\(k\) accuracy with 25–47% fewer samples. Strikingly, QuasiMoTTo often saturates an upper bound on pass@\(k\) that holds for any marginal-preserving sampler. We also apply QuasiMoTTo to policy-gradient RL (GRPO) where it matches i.i.d. performance with 50% fewer training steps. These gains come from higher coverage, which yields a stronger learning signal per batch.
1 Introduction↩︎
![Figure 1: Dependent samples for inference compute scaling and RL.(a)Inference compute scaling and RL rely on independent (i.i.d) sampling, whichwastes compute generating redundant solutions.(b)QuasiMoTTo explores the design space ofcorrelated samplers that cover the output space more evenly than i.i.d.; each individual sample remains an exact sample from the language model (LM).(c) Sampling is embarrassingly parallel via arithmetic sampling [1], which maps each sequence to a sub-interval of [0,1].Generation is a recursive inverse-CDF procedure akin to traversing a probability-weighted trie: for sample i, we draw u_i \in[0,1], and at each step partition the current interval (a prefix) into next-token bins whose widths are the LM’s next-token probabilities, descending into the bin containing u_i.The k samples are coupled only through the uniforms drawn upfront: each is an independent traversal of the same trie, steered by its own u_i, so generation is parallel.(d) QuasiMoTTo significantly boosts sample-efficiency in test-time scaling and RL.](/article/2607.01179/_pdflatex/fleyhamx.png "fig:")
Parallel sampling, generating \(k\) independent (i.i.d.) attempts per prompt, is a fundamental primitive in inference compute scaling and reinforcement learning (RL). But independence is wasteful: many samples in a batch visit the same high-probability regions. This redundancy is costly. In test-time scaling, ideally each sample would explore a different approach, but independent samples rediscover the same solutions; therefore, finding a correct solution to a hard problem can require a very large \(k\). In RL, the same redundancy can force large group sizes because methods like GRPO [2] need within-group reward variation to produce a learning signal. Reducing this redundancy can mitigate the steep cost of methods that scale inference compute, which are driving tremendous progress in language model (LM) capabilities [3].
Intuitively, we could reduce redundancy by correlating these samples so that they depend on each other. We could correlate these samples sequentially — conditioning each draw on the previous ones — but this forfeits the parallelism that makes independent sampling simple to scale. Parallel alternatives either distort the LM’s next-token distribution [4], [5], biasing the estimates RL depends on, or exploit its sensitivity to the prompt [6], where any increase in coverage is incidental rather than guaranteed.
We observe that there is a rich design space of sampling methods that can generate correlated samples that decode completely in parallel yet remain exact samples from the LM [1]. We explore this design space in QuasiMoTTo, which replaces i.i.d. samples with these dependent samples in inference compute scaling and RL. To do this, QuasiMoTTo leverages Monte Carlo methods and coding theory, building on recent work on arithmetic sampling [1], [7]. Instead of drawing samples independently, we generate samples that repel one another to cover the output distribution more efficiently [8]. Concretely, we first use randomized Quasi-Monte Carlo (QMC) to generate \(k\) samples in the unit interval that are more evenly spread than i.i.d. uniform samples. We then map these to \(k\) LM samples via arithmetic coding [9]. Even though samples are coordinated to boost coverage, the procedure is both embarrassingly parallel and exact: each rollout is distributed exactly as if it had been sampled i.i.d. from the LM. Generation is parallel because the arithmetic coding parameterization of autoregressive sampling reduces sampling a sequence to pushing a single uniform through the LM’s inverse CDF: once we draw a batch of uniforms upfront, each rollout decodes independently, with no communication across rollouts. The procedure produces exact LM samples because QMC guarantees each sample marginally uniform, even though samples are correlated. This ensures inverse-CDF sampling [10] produces an exact draw from the LM.
The goal of using dependent samples is to improve sample efficiency: fewer samples give the same performance. We therefore evaluate QuasiMoTTo with a focus on understanding whether we can generate fewer samples from an LM to get the same performance as i.i.d. sampling in test-time scaling and RL. (1) Test-time scaling. To measure how much more coverage QuasiMoTTo provides for fixed \(k\), we compare its pass@\(k\) on reasoning tasks relative to i.i.d. sampling. To characterize the best possible performance, we compare against a union-bound ceiling reflecting the best pass@\(k\) achievable by any marginal-preserving sampler. Strikingly, on reasoning benchmarks, QuasiMoTTo nearly saturates this ceiling, leaving little room for any marginal-preserving sampler to perform better. (2) Reinforcement learning. Because our sampler produces exact samples from the LM, it integrates directly into RL pipelines like GRPO. We show that using QuasiMoTTo reduces the number of training steps required to achieve a target performance relative to i.i.d. sampling.
2 QuasiMoTTo↩︎
2.1 Setup↩︎
A common motif in language modeling is drawing a batch of \(k\) samples \(\{\tau_i\}_{i=1}^k\) from a model \(\pi_\theta\) and aggregating over them. GRPO estimates the policy gradient by averaging over a sampled group of responses; test-time scaling produces a final answer by combining parallel attempts. In each case the batch is a finite-sample approximation to \(\pi_\theta\), and we want it to be (1) marginally correct—each \(\tau_i\) distributed according to \(\pi_\theta\)—and (2) high-coverage—spread across the model’s support rather than clumped on a few modes. The key observation is that correctness asks only for the right marginals, which leaves the joint free; there is a large space of samplers that design the joint distribution in a way that improves coverage.
In particular, marginal correctness is all that average-type estimators need. Let \(\mu\) be the joint law of the batch \((\tau_1,\dots,\tau_k)\) and \(\mu_i\) its \(i\)-th marginal. For any per-rollout quantity \(h\), \[\mathbb{E}_\mu\!\left[\frac{1}{k}\sum_{i=1}^k h(\tau_i)\right] = \frac{1}{k}\sum_{i=1}^k \mathbb{E}_{\tau_i \sim \mu_i}\!\left[h(\tau_i)\right] = \mathbb{E}_{\tau \sim \pi_\theta}\!\left[h(\tau)\right],\] where the first equality is linearity of expectation and holds for any joint \(\mu\), and the second uses only the marginal condition \(\mu_i = \pi_\theta\). The vanilla policy-gradient estimator with no baselines (\(h(\tau) = \nabla\log\pi_\theta(\tau)\,R(\tau)\)) is one such average. A marginally correct sampler is therefore a drop-in replacement for i.i.d.in every estimator of this form. The i.i.d.default corresponds to the product law \(\mu = \pi_\theta^{\otimes k}\), but that is only one joint among the many that share the marginals \(\mu_i = \pi_\theta\). Two distributions can agree on their marginals and still have substantially different joint distributions—Figure 2 illustrates this for Gaussians. Another intuitive example is an antithetic pair. If we draw \(u \sim \mathrm{Unif}[0,1]\), then the tuple \((u, 1-u)\) has uniform marginals, by symmetry, but the coordinates are negatively correlated.
We can exploit this flexibility to design the joint distribution in a way that boosts coverage. This can often have beneficial effects on post-training. For example, policy gradient-based RL methods like GRPO benefit from higher coverage, since there is only a non-zero gradient signal when at least one of the attempts in a group is correct.
The construction has two parts: a randomized Quasi-Monte Carlo coupling on \(\mathrm{Unif}[0,1]\) that induces the dependence (§[sec:primer]), and arithmetic coding [1], [9] that maps those uniforms to exact samples from \(\pi_\theta\), preserving the marginals by construction (§2.3).
2.2 Generating dependent samples via Quasi-Monte Carlo↩︎
Randomized Quasi-Monte Carlo (QMC) is a technique to generate dependent samples with target marginals. Instead of \(k\) independent points, it constructs \(k\) low-discrepancy points that cover the space more evenly than i.i.d. sampling, while ensuring each point is marginally uniform. We describe a number of different methods for doing this below. This marginally uniform property is crucial. In particular, for the inverse CDF sampling in Section 2.3 to be correct (i.e., each completion is an exact draw from the LM), the samples must be marginally uniform. For a visualization of these methods, see Figure 11.
2.2.0.1 Lattice
This procedure involves placing \(k\) points on the regular grid \(\{0, 1/k, \ldots, (k-1)/k\}\), drawing a single shared offset \(\Delta \sim \mathrm{Unif}[0,1]\), giving \[U_i \;=\; \Bigl(\tfrac{i-1}{k} + \Delta\Bigr) \bmod 1, \qquad i = 1, \ldots, k.\] This operation wraps points randomly along the unit interval. Even though the \(\{U_i\}_{i=1}^k\) are more spread-out by construction, the marginal distribution of each \(U_i\) is exactly \(\mathrm{Unif}[0,1]\) due to the random shift. To see this, it is useful to think of this procedure as producing points on the unit circle: defining the endpoints as \(0\) and \(1\) turns \([0,1]\) into a circle with circumference one, and the \(\bmod\,1\) operation is exactly a rotation that wraps points around it. The \(k\) grid points sit at evenly spaced positions on the circle, and \(\Delta\) rotates the entire configuration by a uniformly random angle. Because \(\Delta\) is a uniform random shift, each grid point \(i/k\) — viewed individually — is rotated to a uniformly random location on the circle, so \(U_i \sim \mathrm{Unif}[0,1]\) marginally.
2.2.0.2 Stratified
Instead of using a fixed-width grid, we can also divide the interval \([0,1]\) into \(k\) equally sized strata and draw one point per stratum: \[U_i\sim\mathrm{Unif}\left[\tfrac{i-1}k,\tfrac ik\right]\qquad i=1,\dots,k.\] This stratification ensures that no two samples can occupy the same subinterval. We then permute the resulting samples \(\{U_i\}_{i=1}^k\) so that each \(U_i\) is marginally distributed according to \(\mathrm{Unif}[0,1]\).
The aforementioned QMC methods operate over the 1D space \([0,1]\). In the next section, we describe a procedure for mapping these 1D points to sequences using arithmetic coding. Before doing so, we also present a third QMC method that operates in a higher dimensional space, bypassing the need for this procedure.
2.2.0.3 Token-level Sobol
Since we care about sampling token sequences, a natural approach is to incorporate the sequence dimension directly into the QMC space itself. Concretely, for sequence length \(n\), we can produce uniform random variables
\(U\in[0,1]^n\) by using Sobol sequences [11]. Under this construction, the \(j\)-th coordinate of the point \(U\) corresponds to the \(j\)-th token position, so we can decode by simply passing \(U_j\)
through the inverse CDF (Figure 3) and iterating. Points that collectively cover \([0,1]^n\) should thus produce LLM samples that collectively cover the model’s distribution over
sequences. We refer readers to e.g. PyTorch’s open-source SobolEngine implementation for the actual technical details of constructing \(\{U_i\}_{i=1}^k\).
We provide visual and intuitive comparisons for these three QMC methods in Section 4.3 alongside empirical results in Section 4.1.
2.3 From uniform random variables to token sequences via arithmetic coding↩︎
HTML8FA3C2 HTML2C3E5C HTML4FB286 HTML1F5A40 HTMLEE6C5C HTML8B2D1F HTMLE8A33D HTML8E5A9B HTML1A1A1A HTML555555 HTML444444
Figure 3: Exact sampling from the LM using inverse-CDF sampling. The LM produces logits over the answer choices. We sort them in descending order to yield a permutation \(\sigma\) and a sorted probability vector (panel 2). Stacking these probabilities partitions the unit interval into bins whose widths equal the token probabilities; a uniformly random point lands in each bin with probability equal to that token’s mass. To sample a token, we first sample \(u \in [0,1)\) and find the token whose interval contains it. \(u = .31\) falls in \([0, .40)\), returning \(x_t = \text{``D''}\) (panel 3). For illustrative purposes, we show decoding a single token but repeating this process yields an entire sequence. This recovers the same distribution as standard autoregressive sampling, which usually uses Gumbel-max.. a — image
Randomized QMC gives us a method of sampling points in the unit interval that are (marginally) uniformly distributed but more evenly spread than i.i.d. samples. In particular, lattice and stratified sampling give us 1D samples \(U\in[0,1]\). To map these into token sequences distributed according to the LM’s autoregressive distribution \(\pi_{\theta}\), we use arithmetic coding. The key property of arithmetic coding is that it represents token sequences as sub-intervals on the unit interval whose lengths are equal to the sequence probabilities. So, provided each point is uniformly sampled, it lands in a sub-interval with probability exactly equal to the probability the LM assigns to generating that sequence. This property enables us to decode a set of QMC points into token sequences that are distributed according to \(\pi_\theta\).
More formally, we construct a measure-preserving map from the unit interval to strings \(\Phi:[0,1]\to\mathcal{V}^*\): a map with the property that if \(U\sim\mathrm{Unif}[0,1]\), \(\Phi(U)\) is distributed exactly according to \(\pi_\theta\). By pushing marginally uniform QMC samples through \(\Phi\), we can therefore get \(k\) exact samples from the language model. Below, we describe this in more detail.
2.3.0.1 Arithmetic coding.
We construct a map based on arithmetic coding [1], [9], [12], a classic idea from coding theory; we adapt the construction from [1]. Arithmetic coding represents sequences as nested partitions of the unit interval. We describe how sub-intervals are mapped to sequences via a recursive procedure. We start with \([0,1]\) and partition it into bins whose widths are the first-token probabilities \(\pi_\theta(x_1)\), for \(x_1\in\mathcal{V}\). If \(u\) falls in the bin for \(x_1\), then \(x_1\) is the first token. We then recurse inside that bin: the bin for \(x_1\) is partitioned into sub-bins whose relative widths are given by \(\pi_\theta(\cdot\mid x_1)\), so that the sub-bin for \(x_2\) has width \(\pi_\theta(x_1)\,\pi_\theta(x_2\mid x_1)\).
Continuing this process, each prefix \(x_{1:t}\) is assigned an interval \(I(x_{1:t})\subseteq[0,1]\) of length \(|I(x_{1:t})| =\pi_\theta(x_{1:t}).\) These intervals form a prefix tree: the interval for a prefix contains sub-intervals corresponding to all possible one-token continuations. Sampling a full sequence amounts to drawing a single \(u\sim\mathrm{Unif}[0,1]\) and traversing the tree to a leaf node, by following the unique chain of nested intervals containing \(u\); see Figure 1. Since the interval for each sequence has length equal to its probability under \(\pi_\theta\), the resulting sequence is distributed exactly according to the language model, provided the samples are marginally uniform.
2.3.0.2 Generating a sequence via descending the tree: a numerically stable implementation.
Evaluating \(\Phi(u)\) means finding the leaf interval containing \(u\). To do this, we descend the tree one token at a time, selecting a child via inverse CDF sampling using the language model next-token distribution. A naive approach tracks the prefix intervals at each step \(I(x_{1:t})\) and checks which sub-bucket \(u\) belongs to; this is not numerically stable, since this involves representing the raw probability \(\pi_\theta(x_{1:t})\). Conveniently, we can avoid representing the interval lengths explicitly, by carrying only the position of \(u\) relative to the current interval. Let \(u_t\in[0,1]\) be that coordinate after prefix \(x_{<t}\), with \(u_1=u\). At each step the conditional \(\pi_\theta(\cdot\mid x_{<t})\) partitions \([0,1]\) into one bucket per token; we select the bucket containing \(u_t\) by an inverse-CDF lookup (Figure 3), \[x_t = F_t^{-1}(u_t\mid x_{<t}),\qquad F_t(v\mid x_{<t}) = \sum_{v'\le v}\pi_\theta(v'\mid x_{<t}),\] We then rescale that bucket \([\ell_t,\ell_t+p_t)\), with \(p_t=\pi_\theta(x_t\mid x_{<t})\), back to the unit interval, \[u_{t+1} = \frac{u_t-\ell_t}{p_t}, \label{ref:rescaled95us}\tag{1}\] giving the local coordinate for the next conditional. Every step is then a categorical draw followed by an affine rescaling. The selection reads the same logits already used for softmax decoding, so the procedure folds into a standard autoregressive sampler at negligible cost; only the running coordinate \(u_t\) is added as state. Because this coordinate is the sole per-sample state, the \(k\) rollouts can run as \(k\) independent autoregressive decodes that never interact; generation is as parallelizable as ordinary i.i.d. sampling.
2.4 Estimators that depend on the joint↩︎
Section 2.1 showed that for average-type estimators, dependent samples are drop-in replacements for i.i.d.samples. But not every quantity computed from a batch can be expressed in this way and some commonly used estimators do rely on independence. This section discusses how to modify these estimators to account for dependent samples. More broadly, these case studies point to general recipes for retrofitting estimators built on independence so they remain valid — and unbiased — under dependent samples.
2.4.1 Dyadic bootstrap estimator of pass@\(k\).↩︎
The typical way of estimating pass@\(k\) involves an unbiased estimator introduced in [13]: the procedure draws \(N \geq k\) samples, counts the number \(c\) that are correct, and computes the closed form \[\widehat{\text{pass@}k} = 1 - \frac{\binom{N-c}{k}}{\binom{N}{k}},\] the fraction of size-\(k\) subsets that contain at least one correct sample. This avoids having to draw repeated size-\(k\) batches. This closed form solution is valid when samples are independent and cannot be applied directly to our QuasiMoTTo samplers. For lattice sampling, we develop an analogous dyadic bootstrap estimator that subsamples a batch of \(N\) responses in a way that exploits the lattice structure to produce unbiased estimates.
Theorem 1. Correctness of dyadic bootstrap sampling. Let \(k=2^L\), and let \[u_i = \left(\Delta + \frac{i}{k}\right) \bmod 1, \qquad i=0,\ldots,k-1,\] where \(\Delta \sim \mathrm{Unif}[0,1]\). For any \(x \le L\), set \(m=k/2^x\). Then each stride-\(2^x\) subsequence \[u^{(r)}_j := u_{r + 2^x j}, \qquad j=0,\ldots,m-1,\] with \(r \in \{0,\ldots,2^x-1\}\), is distributed exactly as a fresh randomly shifted lattice of size \(m\). Consequently, each such subsequence gives an unbiased pass@\(m\) estimate under the randomized-lattice construction.
Proof sketch. The full proof is given in Appendix 8.3 and the intuition is captured in Figure 4; the key observation is that the stride-\(2^x\) subsequence is a (random) lattice with spacing \(1/m\), plus a deterministic shift. Because a randomly-shifted lattice is invariant under deterministic shifts modulo \(1\), the subsequence is distributed as a randomly-shifted \(m\)-point lattice. ◻
By similarly exploiting the structure of the stratified and Sobol samplers, we can also derive bootstrap pass@\(k\) estimators for these methods, which we present in Appendix 8.3.
2.4.2 RLOO estimators.↩︎
The second estimator is the leave-one-out estimator used by RLOO. This approach is only unbiased when the baseline is independent of the samples, which is violated under dependent samples. Concretely, for each sample \(y_i\), RLOO computes an advantage by subtracting the mean reward of the other group members from the raw reward \(r(y_i)\), \[A_i = r(y_i) - \frac{1}{n-1}\sum_{j\ne i} r(y_j),\] and the resulting gradient \(\frac{1}{n}\sum_i A_i\,s_\theta(y_i)\) is an unbiased policy gradient where \(s_\theta(y_i)\) is the score \(\nabla_{\theta} \log \pi_\theta (y_i)\). The unbiasedness of this estimator relies on independence in a subtle way: under i.i.d.draws the baseline \(\frac{1}{n-1}\sum_{j\ne i} r(y_j)\) is independent of \(y_i\), and thus \(s_i\), so it is mean-zero in expectation. Under QMC, we do not have this independence and using dependent samples with RLOO introduces bias via the baseline. Empirically, we find this has a negligible impact, but for completeness we describe how we might correct for this theoretically.
2.4.2.1 A pairwise characterization of RLOO that admits an importance sampling correction.
We could take an importance sampling approach to correct for this following [14]. The key idea is to rewrite RLOO as a product-of-differences (PoD) estimator. Proposition 1 shows that RLOO is an average of pairwise PoD terms, \[\begin{align} g_{\mathrm{RLOO}} = \frac{1}{n(n-1)}\sum_{i\ne j} \tfrac12\bigl(r(y_i)-r(y_j)\bigr)\bigl(s_\theta(y_i)-s_\theta(y_j)\bigr), \label{eq:rloo95pod} \end{align}\tag{2}\] each of which is an expectation over the pair \((y_i,y_j)\) with respect to the independent product measure \(\pi_\theta\otimes\pi_\theta\).
However, under a coupled sampler, the pair is drawn from the joint law \(q_{ij}\) instead. The PoD estimator makes it clear that an importance sampling correction involving pairs of sequences can yield unbiased estimates, if we can evaluate \(q_{ij}\) and the importance ratio is defined. Concretely, reweighting each term in Equation 2 by \[\rho_{ij}(y_i,y_j)=\frac{\pi_\theta(y_i)\pi_\theta(y_j)}{q_{ij}(y_i,y_j)}\] maps each term’s expectation back to the independent product measure; by linearity of expectation, the reweighted average is therefore an unbiased RLOO gradient. The entire correction thus reduces computing the probability that the coupled sampler produces a given pair of sequences.
For the lattice sampler, the joint law can be computed explicitly. As Proposition 2 establishes, this can be computed by considering intersections between intervals whose endpoints depend on the relative position of a uniform sample within its final arithmetic interval. We visualize this in Figure 5. Unfortunately, the coupled law \(q_{ij}\) does not have full support over pairs of sequences: intuitively, this is because the lattice has only a single degree of freedom, the shared shift. This violates the support condition needed for importance sampling: the target law must be absolutely continuous with respect to the proposal. When this holds, the importance ratio has expectation 1. Empirically, we observed that the ratio was substantially below 1, consistent with support mismatch.
3 Theoretical Analysis: an upper bound on pass@\(k\) for samplers with a target marginal↩︎
Before evaluating QuasiMoTTo empirically, we first ask how much room there is to improve beyond i.i.d sampling. Intuitively, any sampler that respects the model’s marginal distribution (QuasiMoTTo included) can only rearrange the model’s capability across \(k\) rollouts; without training the model further, we cannot induce new capability. We formalize this as an upper bound on pass@\(k\) in terms of pass@1, which gives us a ceiling against which to measure our gains empirically.
Theorem 2 (Per-problem pass@\(k\) upper bound). Let \(p\) denote the probability that a single sample solves a fixed problem, i.e. its pass@1 probability. Let \(P(k)\) denote the probability that at least one of \(k\) samples solves the problem. Then \[P(k) \leq \min\{1, k p\}.\]
Proof. Let \(S_{j}\) be the event that the \(j\)-th sample solves the problem. By supposition, \(\Pr(S_{j}) = p\) for each \(j\). The event that the problem is solved by at least one of the \(k\) samples is given by \(\bigcup_{j=1}^k S_{j}\) and by the union bound, \[P(k) = \Pr\!\left(\bigcup_{j=1}^k S_{j}\right) \leq \sum_{j=1}^k \Pr(S_{j}) = k p.\] We also must have \(P(k) \leq 1\). Combining the two bounds gives the desired result. ◻
As Figure 6 shows, the gap between i.i.d. and the upper bound depends on the configuration: if the problem is too easy, then the model will sample a correct answer with probability 1 regardless of how it is sampled, and if the problem is too hard, both the i.i.d. and upper bound pass@\(k\) vanish. The gap is maximized at \(k=1/p\), i.e. when the problem is hard but feasible, where i.i.d. achieves a pass@\(k\) of roughly \(1-(1-\frac{1}{k})^k\approx1-\frac{1}{e}=0.632\).
3.0.0.1 Tightness.
The bound is tight when the events \(\{S_{j}\}_{j=1}^k\) are disjoint, i.e., when no two samples in the batch ever solve the problem in the same way simultaneously. Crucially, no sampling procedure that achieves this target pass@1 rate can do better than this upper bound, which places a theoretical limit on how good an entirely sampling-based, training-free method can be.
4 Experiments↩︎
We benchmark QuasiMoTTo on four reasoning tasks chosen to understand the effect of the sampler: each is hard enough that coverage matters (i.i.d.does not trivially saturate), admits a verifiable reward, and uses a compact symbolic vocabulary, avoiding the semantic equivalence class issues that arise in certain natural language reasoning tasks.
4.0.0.1 Samplers.
We use QuasiMoTTo to draw \(k\) samples via the three approaches described in Section 2.2: lattice, stratified, and token-level Sobol. We benchmark against i.i.d. draws \(k\) independent samples from the model and an upper bound that reflects the per-problem ceiling from Theorem 2. This characterizes the best pass@\(k\) achievable by any sampler that preserves the LM’s marginals. We estimate the per-problem pass@\(k\) via the bootstrap procedure of Section 2.4.1.
4.0.0.2 Tasks.
In Countdown [15]–[17], the model is given a target number and a list of numbers and must combine them using arithmetic operations (\(+, -, \times, /\)) to reach the target. In Maze [18], the model receives a 2D maze in text form and must output a sequence of moves (Up/Down/Left/Right) from a start to an end position. In Sudoku, the model fills in a partially-completed \(9 \times 9\) grid subject to the standard constraints. In 1D-ARC [19], the model is shown a few input/output pairs of one-dimensional grids and must infer and apply the underlying transformation to a held-out input. See the Appendix 8.1 for representative examples and solutions.
4.0.0.3 Models.
For Countdown, Sudoku, and Maze, we use Qwen3.5-0.8B-Base. We observe that off-the-shelf LLMs perform poorly on these tasks: they struggle to adhere to format requirements (even instruction-tuned models) and hold a reasonable prior (e.g., they place zero mass on the correct solution). This makes it challenging to apply RL directly to these models [16]. Thus, for these three tasks, we perform supervised fine-tuning on 50,000 correct question/answer pairs. For 1D-ARC, we use Qwen3.5-2B-Base directly. ARC inputs are inductive by nature — containing multiple in-context examples — so the base model already produces well-formatted outputs, and does not require any additional supervised fine-tuning.
4.0.0.4 Evaluation.
For each task we report pass@\(k\) (i.e. 1 if at least one of the \(k\) attempts is correct), and the pass@\(k\) upper bound, averaged across all problems. To isolate the effect of the sampler, all methods share the same model, prompt, and decoding temperature; only the joint distribution of the underlying uniforms differs. We use temperature \(1.0\) and top-\(p\) \(0.95\) throughout, with a maximum completion length of \(32\) tokens for Countdown and Maze, and \(280\) tokens for Sudoku and 1D-ARC.
4.1 Pass@\(k\) results↩︎
4.1.0.1 QuasiMoTTo substantially outperforms i.i.d.and comes close to saturating the upper bound.
In Figure 7, we see that QuasiMoTTo(lattice-based) sampler produces a significantly higher pass@\(k\) than i.i.d.sampling at every value of \(k\), across all four tasks. We only present results for the lattice based sampler here, but we provide the pass@\(k\) for all samplers in Figure 13 in the Appendix. Strikingly, the QuasiMoTTo pass@\(k\) curves track the upper bound closely; this means there is little room for any training-free sampler (that preserves the marginals) to further improve performance. This holds, to different degrees, across a diverse set of tasks with different solution geometries — arithmetic search (Countdown), spatial planning (Maze), constraint satisfaction (Sudoku), and pattern induction (1D-ARC). Note that, although the upper bound from Section 3 is (piecewise) linear in \(k\), it is a per-problem upper bound and the pass@\(k\) curves in Figure 7 aggregate over problems with different accuracies.
4.1.0.2 QuasiMoTTo sample efficiency.
We can also ask how many fewer samples QuasiMoTTo needs to match a given i.i.d.pass rate; we present these results in Figure 8. For the lattice-based sampler, QuasiMoTTo reaches i.i.d.’s performance with a 25-47% reduction in samples. Therefore, at deployment, we can use QuasiMoTTo to reduce the rollout budget at matched quality or hold the budget fixed and spend the freed FLOPs elsewhere. The compute savings are essentially free since the per-rollout overhead of QuasiMoTTo is negligible (one extra uniform draw per batch plus the inverse-CDF bookkeeping). The other non-lattice QMC methods also improve sample-efficiency, although to a lesser extent.
4.2 Policy-gradient based reinforcement learning↩︎
Figure 9: QuasiMoTTo compute efficiency for RL. We plot the pass@1 on evaluation set against the training step. QuasiMoTTo achieves the same pass@\(1\) in fewer steps compared to i.i.d sampling..
Since QuasiMoTTo produces exact samples from the LM, we can use it as a drop-in replacement for policy-gradient based reinforcement learning. If QuasiMoTTo can produce more diverse outcomes within a group, it can boost the effective sample size per gradient step and decrease the number of training steps required to achieve a target performance.
4.2.0.1 Setup.
We train Qwen3.5-0.8B-Base on Maze and Sudoku using GRPO [2] to measure whether QuasiMoTTo rollouts translate into faster policy improvement. As a baseline, we also train the model using an i.i.d.sampler. We use a group size of \(G = 8\), \(64\) unique prompts per gradient step, sampling temperature \(\tau = 1.0\), and a max completion length of 256 tokens. We perform 2 gradient steps per rollout batch (i.e., 2 off-policy updates). We use sequence level off-policy importance sampling [20]. Note that, because we use a group baseline with dependent samples, we introduce some amount of bias; see Section [sec:dependent95samples95rloo].
Experiments were run on 4 H100s/A100s. We organize our analysis around two questions: (1) does using QuasiMoTTo during RL training translate into a compute-efficiency win (fewer steps to get the same reward), and (2) how do correlated samples change the training dynamics?
4.2.0.2 GRPO background.
We provide some basic background on GRPO. Concretely, for a prompt \(x\), the policy \(\pi_{\theta}\) generates \(G\) completions \(y_1,\ldots,y_G\) and receives rewards \(r_1,\ldots,r_G\). GRPO forms a group-relative advantage for each completion by comparing its reward to the rewards of the other completions from the same prompt; the \(i\)-th completion gets advantage \(A_i = r_i - \mathrm{mean}(r_1,\ldots,r_G)\). If all \(G\) completions for a prompt receive the same reward, then the group has zero reward variance and contributes no policy-gradient signal. We call such a group a zero-variance group when all rollouts are correct, or incorrect. Zero variance groups are a significant practical challenge: they increase the policy gradient variance, by reducing the number of prompts the LM gets a learning signal from in a batch (i.e., the effective sample size [21]).
4.2.0.3 Hard-problem pass@\(k\) filtering.
In GRPO-style training, learning is primarily driven by rare but correct rollouts; questions that are too hard or easy result in more zero-variance groups, less learning signal, and increased noise [21], [22]. As established in Section 3, we also expect QuasiMoTTo samplers to exhibit the most improvement over i.i.d. in this hard-but-feasible regime. Thus, to better study the effects of QuasiMoTTo on RL training, we filter out Maze and Sudoku problems which are too easy or too hard. We do this as a preprocessing step by generating 32 completions per problem with the base model checkpoint, and filtering out problems with an average pass rate \(=0\) or \(>\frac{1}{G}=0.125\).
4.2.0.4 QuasiMoTTo is a compute efficiency win.
In Figure 9, we compare the evaluation set pass@\(1\) for QuasiMoTTo against i.i.d. sampling; for evaluation, we use QuasiMoTTo sampler for both methods to isolate the benefits of using the QMC sampler at training time. QuasiMoTTo provides a consistent compute-efficiency win; we can achieve the same target pass@1 in 50% fewer steps. In the Appendix, we report error bars (Figure 14).
4.2.0.5 QuasiMoTTo sampling improves training dynamics by reducing zero-gradient groups.
With i.i.d. sampling, the rollouts in a group frequently coincide, in which case the group-relative advantage collapses to zero and the gradient update carries no signal. In Figure 10, we see that QuasiMoTTo actively mitigates this: QuasiMoTTo encourages rollouts to occupy different regions of the sequence space. We see this clearly reflected in a smaller percentage of zero-variance groups. The result is faster improvement due to a larger effective sample size. Interestingly, although dependent samples introduce some amount of bias through the group relative baseline (Section [sec:dependent95samples95rloo]), this is more than compensated by the increase in the effective batch size.
4.3 Theoretical and empirical tradeoffs between samplers↩︎
In this section we provide a high-level picture for how QuasiMoTTo samplers (lattice, stratified, and Sobol) relate to each other and to i.i.d. sampling. The goal is to build intuition for why different samplers lead to the different pass@\(k\) and RL results shown above.
HTML1A1A1A HTML555555 HTML444444 HTMLEE6677 HTML444444 HTML16A085 HTML1F4E89 HTMLF4A261 HTMLB96A1E
4.3.0.1 Freedom vs. coverage.
Of the three 1D samplers, independent sampling has the most freedom: samples do not influence one other at all, and coverage guarantees are weak. As we move to stratified and then lattice sampling, the “freedom" gets more restricted — points repel one another more strongly — and the coverage consequently increases (Figure 11). This explains why pass@k monotonically increases from i.i.d. to stratified to lattice in Section 4.1, and why the proportion of zero-variance groups drops in Section 4.2.
One way to quantify this tradeoff is through the pairwise mutual information \[I(U_i; U_j)=H(U_i)-H(U_i\mid U_j),\] an information-theoretic quantity which measures how much information one gains about a random variable by conditioning on another variable. For independent samples this is trivially 0. For stratified sampling, conditioning on \(U_j\) reduces the possible space of \(U_i\) from \([0,1]\) to a region of length \(\frac{k-1}{k}\), so the mutual information is \[-\int_0^1\log 1 \, \mathrm{d}u +\int_0^{\frac{k-1}{k}}\frac{k}{k-1}\log\frac{k}{k-1} \, \mathrm{d}u =\log\frac{k}{k-1}.\] For lattice sampling, since conditioning on any point \(U_j\) makes any other point \(U_i\) deterministic, the distribution collapses to a point mass and the differential entropy \(H(U_i\mid U_j)\) is \(-\infty\).
We note that stratified empirically outperforms lattice when applied to RL (Section 4.2), which is seemingly at odds with this freedom vs. coverage intuition. We hypothesize that this is a consequence of the RLOO bias mentioned in Section [sec:dependent95samples95rloo]: lattice has higher coverage but higher bias, which overall hurts training more than stratified.
4.3.0.2 Sequence-level vs. token-level coverage.
Unlike lattice/stratified sampling, Sobol sequences are defined over a high-dimensional space. The coverage applies locally at each token position rather than globally for the whole sequence. We would therefore expect Sobol to perform somewhat weaker than stratified or lattice, but still stronger than i.i.d., an intuition which holds in the pass@\(k\) and RL experiments above.
5 Related Work↩︎
5.0.0.1 Beam Search
Beam search and its diverse variants [4] also boost diversity, but their outputs do not correspond to draws from a well-defined distribution, let alone the LM’s, which precludes their use within procedures like RL (they would introduce substantial bias). Stochastic beam search [5] reduces redundancy by drawing structured sets of distinct sequences. However, because sampling without replacement changes the sequence probabilities, unbiased estimation with respect to the LM requires importance weight corrections. This suffers from the conventional challenges of importance weighting such as high variance.
5.0.0.2 Exploration in RL
Recent approaches modify the RL or SFT training objective to induce broader coverage over rollouts [18], [23]–[26]. Our approach is orthogonal: we intervene at the sampling stage rather than during training, leaving the objective untouched.
5.0.0.3 Efficient sampling
Most work on efficient LLM inference lowers the cost of each rollout. IO-aware exact attention removes the memory bottleneck of softmax attention [27], paged memory management raises serving throughput [28], sparse attention drops the quadratic scaling in context length [29], and learned KV cache compression methods reduce the size of the context [30], [31]. Orthogonally, one can reduce latency by restructuring a single chain of thought into subtasks executed in parallel [17], [32]. All of these make a rollout cheaper or faster; QuasiMoTTo instead reduces the number of rollouts needed to reach a target performance.
6 Conclusions & Limitations↩︎
We introduced QuasiMoTTo, an approach that combines randomized QMC and inverse CDF sampling to generate a dependent batch of LM rollouts for scaling inference compute. Each rollout is an exact sample from the LM, but the batch as a whole covers the output space more evenly. This buys compute efficiency: 25–47% fewer samples to match i.i.d. pass@\(k\) on reasoning benchmarks, often saturating the union-bound ceiling that no marginal-preserving sampler can exceed; and 50% fewer GRPO steps to hit a target pass@1, driven by a drop in zero-variance groups.
Our experiments use 1–2B parameter models on tasks with shorter outputs for challenging symbolic reasoning tasks. Extending QuasiMoTTo to long chain-of-thought reasoning requires defining a notion of coverage over semantic equivalence classes of solutions. It would also be interesting to see if QuasiMoTTo can boost coverage and diversity in open-ended tasks where this is particularly important, like scientific discovery [6], [33]–[35]. These are natural directions for future work.
7 Acknowledgements↩︎
We thank members of Cocolab and Dynamode Lab, particularly Ivy Zhang and Qizhong Zhang, for thoughtful feedback on this project. We thank Omar Shaikh and Matt Jorke for insightful discussions. We thank Jubayer Ibn Hamid and Suvir Mirchandi for helpful discussions. Some of the experiments for this project was performed on the Marlowe cluster at Stanford University. This work was supported in part by ONR Grant N00014-22-1-2110, NSF Grant 2205084, and the Stanford Institute for Human-Centered Artificial Intelligence (HAI). EBF is a Biohub, San Francisco, Investigator.
8 Technical appendices and supplementary material↩︎
8.1 Experiment Details↩︎
| Hyperparameter | Value |
|---|---|
| Optimizer | AdamW |
| Learning rate | \(1 \times 10^{-6}\) |
| \((\beta_1, \beta_2)\) | \((0.9,\;0.95)\) |
| \(\epsilon_{\text{Adam}}\) | \(1 \times 10^{-8}\) |
| Weight decay | \(0.01\) |
| Max gradient norm | \(1.0\) |
| KL coefficient (\(\beta\)) | \(0.01\) |
| PPO clip range (\(\epsilon\)) | \(0.2\) |
| Off-policy epochs | \(2\) |
8.2 Additional experimental results↩︎
Figure 14: QuasiMoTTo compute efficiency for RL. We plot the pass@1 on evaluation set against the training step. QuasiMoTTo achieves the same pass@\(1\) in fewer steps compared to i.i.d sampling. Error bars are computed as follows: we estimate the accuracy \(p_i\) for each of \(n\) questions and report \(\frac{\operatorname{std}(p)}{\sqrt{n}}\)..
8.3 Theoretical analyses↩︎
Theorem 3 (Correctness of dyadic bootstrap sampling). Let \(k=2^L\), and let \[u_i = \left(\Delta + \frac{i}{k}\right) \bmod 1, \qquad i=0,\ldots,k-1,\] where \(\Delta \sim \mathrm{Unif}([0,1])\). For any \(x \le L\), set \(m=k/2^x\). Then each stride-\(2^x\) subsequence \[u^{(r)}_j := u_{r + 2^x j}, \qquad j=0,\ldots,m-1,\] with \(r \in \{0,\ldots,2^x-1\}\), is distributed exactly as a fresh randomly shifted lattice of size \(m\). Consequently, each such subsequence gives an unbiased pass@\(m\) estimate under the randomized-lattice construction.
Proof. Let \(s=2^x\), so \(m=k/s\). For any offset \(r\), \[u_{r+sj} = \left(\Delta + \frac{r+sj}{k}\right)\bmod 1 = \left(\Delta + \frac{r}{k} + \frac{j}{m}\right)\bmod 1.\] The last equality substitutes \(\frac{1}{m}\) for \(\frac{s}{k}\). Define \[\Delta^{(r)} := \left(\Delta + \frac{r}{k}\right)\bmod 1.\]
For a fixed lattice subsequence, \(r\) and \(k\), are constants, so \(\frac{r}{k}\) is a deterministic shift. Since adding a deterministic constant modulo 1 preserves the uniform distribution \(\Delta^{(r)}\) is also uniform on \([0,1]\). Finally substituting \(\Delta^{(r)}\) and noting that adding a constant before reducing modulo \(1\) is the same as first reducing the shifted quantity modulo \(1\), we obtain \[u_{r+sj} = \left(\Delta^{(r)} + \frac{j}{m}\right)\bmod 1,\] which is exactly an \(m\)-point lattice with a uniform random shift. Therefore any pass@\(m\) estimator computed on this subsequence has the same expectation as the estimator computed on a fresh \(m\)-point randomized lattice. ◻
Theorem 4 (Bootstrap estimator for stratified sampling). Following the notation above, let \(\{u_i\}_{i=0}^{k-1}\) be a set of stratified samples \[u_i\sim\mathrm{Unif}[\tfrac ik, \tfrac{i+1}k],\qquad i=0,\ldots,k-1.\] Then, to obtain a bootstrapped stratified sample for \(m=k/2^x\), we can partition \(u_i\)’s into contiguous blocks of size \(k/m=2^x\) \[\{u_0,\ldots,u_{k/m-1}\}\cup\{u_{k/m},\ldots,u_{2k/m-1}\}\cup\cdots\cup\{u_{(m-1)k/m},\ldots,u_{k-1}\}\] and sample once from each partition \[u_i'\sim\{u_{ik/m},\ldots,u_{(i+1)k/m-1}\}\] so that \(\{u_i'\}_{i=0}^{m-1}\) is distributed according to the stratified rule for \(m\) samples, i.e., \(u_i\sim\mathrm{Unif}[\tfrac im, \tfrac{i+1}m]\).
Theorem 5 (Bootstrap estimator for Sobol sampling). Let \(\{u_i\}_{i=0}^{k-1}\) be a length \(k\) Sobol sequence in dimension \(n\) \[u_i\in[0,1]^n.\] Sobol sequences of length \(2^L\) are constructed such that any prefix of length \(2^x<2^L\) is itself a valid Sobol sequence. So, to obtain an unbiased pass@\(m\) estimate, we can simply take contiguous blocks of \(k/m\): \[u_j^{(r)}:=u_{rm+j},\qquad j=0,\ldots,m-1,\] which gives bootstrapped samples for \(r\in\{0,\ldots,2^x-1\}\).
The proofs for the above two bootstrap estimators follow analogously to the proof above for the dyadic estimator for lattice sampling.
Proposition 1 (Characterization of RLOO as a product-of-differences estimator).
Let \(y_1,\dots,y_n\) be sampled trajectories from a policy \(\pi_\theta(y)\). Let \(r(y_i)\in\mathbb{R}\) denote the reward of trajectory \(y_i\), and define the score \[s_\theta(y_i) := \nabla_\theta \log \pi_\theta(y_i).\] The leave-one-out policy-gradient estimator \[g_{\mathrm{RLOO}}(\theta) = \frac{1}{n} \sum_{i=1}^n \left( r(y_i) - \frac{1}{n-1}\sum_{j\ne i} r(y_j) \right) s_\theta(y_i)\] can be written equivalently as \[g_{\mathrm{RLOO}}(\theta) = \frac{1}{n(n-1)} \sum_{i\ne j} \frac{1}{2} \left(r(y_i)-r(y_j)\right) \left(s_\theta(y_i)-s_\theta(y_j)\right).\]
Proof. Starting from the leave-one-out estimator, \[g_{\mathrm{RLOO}}(\theta) = \frac{1}{n} \sum_{i=1}^n \left( r(y_i) - \frac{1}{n-1}\sum_{j\ne i} r(y_j) \right) s_\theta(y_i).\] Expanding, \[g_{\mathrm{RLOO}}(\theta) = \frac{1}{n} \sum_{i=1}^n r(y_i)s_\theta(y_i) - \frac{1}{n(n-1)} \sum_{i=1}^n \sum_{j\ne i} r(y_j)s_\theta(y_i).\]
We first make the left and right term symmetric by introducing dummy indices that allow us to re-write the first term as a pairwise sum: \[\frac{1}{n} \sum_{i=1}^n r(y_i)s_\theta(y_i) = \frac{1}{n} \sum_{i=1}^n \frac{1}{n-1} \sum_{j \neq i} r(y_i)s_\theta(y_i) = \frac{1}{n(n-1)} \sum_{i\ne j} r(y_i)s_\theta(y_i).\] Therefore, \[g_{\mathrm{RLOO}}(\theta) = \frac{1}{n(n-1)} \sum_{i\ne j} \left( r(y_i)s_\theta(y_i) - r(y_j)s_\theta(y_i) \right).\]
Since we can simply relabel \(i\) with \(j\), we also have \[\sum_{i\ne j} \left( r(y_i)s_\theta(y_i) - r(y_j)s_\theta(y_i) \right) = \sum_{i\ne j} \left( r(y_j)s_\theta(y_j) - r(y_i)s_\theta(y_j) \right).\] Therefore, we can write the RLOO estimator as \[g_{\mathrm{RLOO}}(\theta) = \frac{1}{n(n-1)} \sum_{i\ne j} \frac{1}{2} \left[ r(y_i)s_\theta(y_i) - r(y_j)s_\theta(y_i) + r(y_j)s_\theta(y_j) - r(y_i)s_\theta(y_j) \right].\] Finally, factoring we have \[g_{\mathrm{RLOO}}(\theta) = \frac{1}{n(n-1)} \sum_{i\ne j} \frac{1}{2} \left(r(y_i)-r(y_j)\right) \left(s_\theta(y_i)-s_\theta(y_j)\right).\] as desired. ◻
8.3.1 Computing pair probability under the lattice QMC construction.↩︎
8.3.1.1 Preliminaries.
Let \(\mathcal{V}^\ast\) denote the set of finite token sequences. Arithmetic sampling defines a deterministic decoder \[\operatorname{Dec}_0:[0,1)\to\mathcal{V}^\ast,\] where \(\operatorname{Dec}_0(u)\) is the sequence obtained by running arithmetic decoding with latent \(u\in[0,1)\). For each sequence \(y\in\mathcal{V}^\ast\), define its arithmetic interval \[I_0(y):=\{u\in[0,1):\operatorname{Dec}_0(u)=y\}.\] Equivalently, \[I_0(y)=[L(y),L(y)+W(y))\subset[0,1),\] where \[W(y)=\pi_\theta(y)=\prod_{t=1}^{T}\pi_\theta(y_t\mid y_{<t}).\]
For the pair-probability calculation, it will be convenient to identify \([0,1)\) with the unit circle \[\mathbb{S}^1=\mathbb{R}/\mathbb{Z}.\] Under this identification, addition is modulo one, and \(I_0(y)\) is viewed as a subset \(I(y)\subset\mathbb{\mathbb{S}}^1\). We will write the resulting decoder simply as \[\operatorname{Dec}:\mathbb{S}^1 \to\mathcal{V}^\ast.\]
Lemma 1 (Pair probability as a circular overlap). Let \(b\sim\mathrm{Unif}(\mathbb{S}^1)\), and suppose the lattice QMC latents are \[u_k=b+\alpha_k \pmod 1,\] where \(\alpha_k\in\mathbb{S}^1\) is deterministic. For \(k\in\{i,j\}\), let \(y_k\in\mathcal{V}^\ast\) be a sequence of interest, and define \[I_k:=I(y_k).\] Define the shifted interval \[J_k := I_k-\alpha_k := \{b\in\mathbb{S}^1:\;b+\alpha_k\in I_k\}.\] Then \[\begin{align} q_{ij}(y_i,y_j) &:= \Pr\!\left( \operatorname{Dec}(b+\alpha_i)=y_i,\; \operatorname{Dec}(b+\alpha_j)=y_j \right)= \lambda_{\mathbb{S}^1}(J_i\cap J_j), \end{align}\] where \(\lambda_{\mathbb{S}^1}\) denotes normalized Lebesgue measure on \(\mathbb{S}^1\).
Proof. By definition of \(I_i\), \[\operatorname{Dec}(b+\alpha_i)=y_i \qquad\Longleftrightarrow\qquad b+\alpha_i\in I_i.\] By definition, \(J_i=I_i-\alpha_i\), so the above is equivalent to \[b\in J_i.\] Similarly, \[\operatorname{Dec}(b+\alpha_j)=y_j \qquad\Longleftrightarrow\qquad b\in J_j.\] Therefore the joint event is exactly \[\{b:\operatorname{Dec}(b+\alpha_i)=y_i,\;\operatorname{Dec}(b+\alpha_j)=y_j\} = J_i\cap J_j.\] Since \(b\) is uniform on \(\mathbb{S}^1\), the probability of this event is \[q_{ij}(y_i,y_j) = \lambda_{\mathbb{S}^1}(J_i\cap J_j).\] ◻
Thus, pair probabilities in a QMC group are determined by overlaps among the shifted intervals.
8.3.1.2 Numerically stable calculation
Lemma 1 shows that the pair probability is the length of the overlap \(J_i\cap J_j\), where \[J_k=I_k-\alpha_k.\] Naively, this involves materializing the arithmetic intervals which is numerically unstable since it requires computing the raw sequence probabilities. We now describe a numerically stable alternative. A useful way to think about how to compute this overlap is through how much we can perturb this shared random shift while maintaining the same two decoded sequences.
Let \(b_0\) be the realized shared shift that generated the observed sequences. Thus \[u_k=b_0+\alpha_k \pmod 1, \qquad u_k\in I_k.\]
Now consider a candidate shifted value \(b_0+\delta\). For sample \(k\), this perturbation keeps the decoded sequence equal to \(y_k\) precisely when \[b_0+\delta\in J_k.\] Equivalently, adding back the offset \(\alpha_k\), \[u_k+\delta\in I_k.\] Thus \(J_k-b_0\) is exactly the set of perturbations \(\delta\) of the shared shift that keep sample \(k\) decoding to \(y_k\).
By translation invariance of Lebesgue measure on \(\mathbb{S}^1\), we may center the calculation at \(b_0\): \[\lambda_{\mathbb{S}^1}(J_i\cap J_j) = \lambda_{\mathbb{S}^1}\bigl((J_i-b_0)\cap(J_j-b_0)\bigr).\] Moreover, without loss of generality, we can assume the shared anchor is at \(0\), and the problem can be reduced to computing which perturbations \(\delta\) keep both decoded sequences the same.
The residual coordinate gives these allowable perturbations. For the \(k\)th sample, define \[z_k=\frac{u_k-L_k}{W_k}\in[0,1).\] Equivalently, \[u_k=L_k+W_kz_k.\] Thus \(z_k\) is the fractional position of the sampled latent inside its final arithmetic interval \[I_k=[L_k,L_k+W_k).\] It determines the left and right slacks of \(u_k\) within \(I_k\): \[\ell_k:=u_k-L_k=W_kz_k, \qquad r_k:=L_k+W_k-u_k=W_k(1-z_k).\] In words, \(\ell_k\) is how far we can move \(u_k\) to the left before leaving \(I_k\), and \(r_k\) is how far we can move \(u_k\) to the right before leaving \(I_k\).
Therefore the perturbation that keep sample \(k\) fixed are thes ones where \(u_k+\delta\) remains inside \(I_k\). This is exactly when \[\delta\in[-\ell_k,r_k)\pmod 1.\]
Since this condition must be satisfied so that both samples \(i\) and \(j\) remain fixed, we obtain \[q_{ij}(y_i,y_j) = \lambda_{\mathbb{S}^1} \left( [-\ell_i,r_i)\cap[-\ell_j,r_j) \right),\] Again, the intersection is understood on the circle.
Proposition 2 (Stable formula for the circular overlap).
Proof. By the calculation above, \[q_{ij}(y_i,y_j) = \lambda_{\mathbb{S}^1}(K_i\cap K_j),\] where \[K_i=[-\ell_i,r_i)\pmod 1, \qquad K_j=[-\ell_j,r_j)\pmod 1.\] Cut the circle at \(0\). Then, \[K_k=[0,r_k)\cup[1-\ell_k,1).\] The overlap has four possible contributions.
The first two conditions are best understood by considering how two sub-intervals within the unit interval can intersect. First, the two right pieces overlap by \[\lambda\bigl([0,r_i)\cap[0,r_j)\bigr)=\min(r_i,r_j).\] Second, the two left pieces overlap by \[\lambda\bigl([1-\ell_i,1)\cap[1-\ell_j,1)\bigr) = \min(\ell_i,\ell_j).\]
The last conditions are more subtle and occur when there is wrap-around.
First, the right piece of \(K_i\) can overlap the left piece of \(K_j\): \[[0,r_i)\cap[1-\ell_j,1).\] This intersection is nonempty exactly when \(r_i+\ell_j>1\). In that case its length is \(r_i+\ell_j-1\). Thus its contribution is \[(r_i+\ell_j-1)_+.\] Similarly, the left piece of \(K_i\) can overlap the right piece of \(K_j\), contributing \[(\ell_i+r_j-1)_+.\] Adding the four contributions gives \[q_{ij}(y_i,y_j) = \min(\ell_i,\ell_j) + \min(r_i,r_j) + (r_i+\ell_j-1)_+ + (\ell_i+r_j-1)_+.\] ◻
References↩︎
* Equal contribution. Correspondence to
michaelyli@stanford.edu.↩︎