acceptodds
Under review as a conference paper at ICLR 2027

Designing Coupled Samplers for Language Models

Abstract

Scaling inference compute and reinforcement learning rely on generating batches of language model rollouts. These are typically sampled independently, but prior work on arithmetic sampling shows that this independence can be relaxed: dependent rollouts can be generated in parallel while preserving the marginal distribution. However, this leaves open a consequential design choice—how should the rollouts be coupled? Infinitely many joint distributions preserve the marginals, and classical Monte Carlo suggests this choice matters significantly. In this paper, we establish principles for designing dependent samplers for test-time scaling and reinforcement learning. We first theoretically analyze how the choice of dependent sampler impacts test-time scaling properties. We then characterize these tradeoffs empirically across four controlled reasoning benchmarks. We find that lattice sampling yields the highest coverage, matching i.i.d. pass@ with 25–47% fewer rollouts. In reinforcement learning, stratified sampling performs the best, matching i.i.d performance with 34.5%-59.2% fewer training steps. Our results establish dependent sampling as another design axis for language model inference and learning, and take a step towards a systematic characterization of this design space.

Primary area:
foundation or frontier models, including LLMs
Keywords:
dependent sampling

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_GzMFOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies how the rollouts a LLM generates in a batch should be correlated for better inference-time scaling or GRPO-style reinforcement learning. An autoregressive process is written as a map DθD_\theta from a point U∈[0,1]U \in [0,1] to the generated sequence. The inverse map of a sequence xx occupy an interval I(x)⊂[0,1]I(x) \subset [0,1] of length ∣I(x)∣=πθ(x)|I(x)| = \pi_\theta(x). Any joint distribution over (U1,…,Uk)(U_1,\dots,U_k) with Unif[0,1]\mathrm{Unif}[0,1] marginals then yields kk rollouts each exactly distributed as πθ\pi_\theta. The paper studies different joint distributions maintaining this property theoretically and shows effectiveness over i.i.d. sampling through experiments.

Critical strengths
  • The paper presents the first systematic characterization of the coupling/correlation design space for LLM rollouts. Theorem 2 shows that stratified sampling (weakly) dominates i.i.d. sampling for pass@k. Proposition 2 shows that if the correct subset of [0,1][0,1] is a single interval, the shifted lattice sampling is even better than stratified sampling.
  • Experimentally (Figure 3, 4), the paper demonstrates that all coupled samplers considered beat i.i.d. on all four tasks for pass@k, the lattice closely tracks the theoretical upper bound, especially on Sudoku/1D-ARC where each problem has a single correct output as expected.
  • Authors show RLOO under any dependent marginal-preserving sampler is biased, controlled by a theoretical formula involving the covariance of reward and cross-sample score function. Empirical RLOO bias is non-zero and is 0.9-1.4 % of the i.i.d. estimator's stochastic variation (Table 4).
  • Further, they show for GRPO on Maze/Sudoku: all coupled samplers beat i.i.d. final pass@1, coupled samplers produce fewer zero-variance groups and match i.i.d. reward with 18--24% fewer steps (Figure 5).
Critical weaknesses
  • The theory guarantees variance reduction or mean bias is presented for vanilla policy gradient, while experiments use clipped GRPO and sequence-level importance sampling - experiment, the theory bridge is looser than presented.
  • No theoretical RL result exists for lattice sampling bias or variance, although experiments show that it is mostly the best-performing method.
Questions for authors

See weaknesses.

1 comment

We thank the reviewer for their thorough review! We are glad that the reviewer found the paper clearly written and the theory and experiments well-motivated. We’ve made several changes in the manuscript to address the weaknesses:

W1: Policy gradient theory differs from experimental GRPO setup

We agree that the theoretical assumptions for our bias-variance results in Appendix A.6 do not exactly capture the experiments which use GRPO with clipping. Our goal is not to perfectly model the dynamics of RL training with all its nuances such as clipping and sequence-level importance sampling, but to provide high-level insight into the variance-reduction properties of coupled samplers. These insights connect the Quasi-Monte Carlo properties of coupled samplers with the sample efficiency gains that we observe in Section 6.2.

Indeed, there is a growing disconnect between basic PGRL theory and the more complex recipes used in practice for LLM RL (clipping, masking, importance sampling, and numeric mismatch), which are important for stability but introduce bias and make theoretical analysis more difficult. We agree that this is an important point worth communicating; we highlight this more prominently in Section 6.2 in the revised version.

W2: Lack of RL theory for lattice sampling

We agree that a distribution-free lattice-specific characterization of variance would strengthen the theory. However, we emphasize that a uniform variance-reduction guarantee is impossible. To see this, consider the per-rollout policy-gradient contribution (h(u) := r(D_\theta(u))\nabla_\theta \log \pi_\theta(D_\theta(u))), where (D_\theta(u)) is the rollout decoded from (u\in[0,1)). If (h) is (1/G)-periodic, all (G) lattice samples contribute identical gradients, so their average has (G) times the variance of the i.i.d. estimator. This parallels the periodic worst case established in Proposition 3.

For bias, we clarify that Proposition 7 already provides an exact characterization applicable to lattice sampling, since it holds for any marginal-preserving coupling. Obtaining a simpler lattice-specific expression requires additional assumptions about the decoding geometry.

Nevertheless, our experiments provide direct evidence of lattice's effectiveness in the settings studied: Gradient variance (Table 5): Lattice reduces the covariance trace by 62% relative to i.i.d. (0.031 vs. 0.082), while its squared mean-gradient displacement is only 1.3% of i.i.d. stochastic variation. RL efficiency (Figure 5): Lattice produces the fewest zero-variance groups on both Maze and Sudoku and reaches matched training reward with 19% and 24% fewer steps, respectively. Thus, while lattice does not admit a distribution-free variance-reduction guarantee, our empirical results demonstrate substantial benefits in the regimes considered, consistent with the geometry-dependent behavior characterized by our theory.

We hope these clarifications address your concerns. If you feel they strengthen the paper, we would be grateful if you would consider updating your scores.

Reviewer_6BxCOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies the design of coupled samplers for language model test-time scaling and reinforcement learning. Building on arithmetic sampling, the authors compare stratified sampling, randomly shifted lattice sampling, and token-level Sobol sampling, all of which preserve the marginal distribution of each rollout while introducing dependencies across rollouts. The theoretical analysis characterizes pass@k bounds, the robustness–optimality tradeoff across coupling strategies, and the effects of dependent sampling on policy-gradient variance and group-relative updates. Experiments on Countdown, Maze, Sudoku, and 1D-ARC show that lattice sampling can match i.i.d. pass@k with 25–47% fewer rollouts. Additional evaluations on MBPP and HumanEval report improvements in code-generation coverage, while GRPO experiments on Maze and Sudoku show fewer zero-variance groups, faster training, and improvements in final pass@1 in some settings.

Critical strengths

S1. Interesting and well-motivated problem with clear presentation.

The paper identifies the choice of coupling as an important design decision in generating batches of language model rollouts. Its central question is clearly motivated: different joint distributions can preserve the same marginal distribution while producing different coverage properties.

S2. Useful theoretical characterization of the tradeoffs between coupling strategies.

The paper goes beyond reporting empirical gains by identifying when dependent sampling can help and when particular couplings may fail. Proposition 1 characterizes the regime in which the gap between the pass@k upper bound and i.i.d. sampling is largest. Theorem 2 establishes that stratified sampling weakly dominates i.i.d. coverage for any measurable success region, whereas Propositions 2–3 show that lattice sampling can attain the upper bound for a contiguous success region but can perform worse than i.i.d. sampling for a periodic success region. Theorem 3 and Appendix A.4 further distinguish the variance properties of a standard policy-gradient estimator from the bias introduced by dependent sampling in RLOO updates. Together, these results provide useful insight into the robustness–optimality tradeoff discussed in the paper.

S3. Controlled comparisons supported by additional inference and RL evaluations.

The main inference experiments hold the model, prompt, and decoding parameters fixed while varying the coupling strategy (Section 6). The results on four controlled reasoning tasks support the coverage analysis, and the additional experiments on 4B–9B models (Table 5) and MBPP and HumanEval (Table 3) broaden the evaluation. The RL experiments also examine training dynamics rather than only final performance: Figure 5 reports the fraction of zero-variance groups and training reward, while Table 4 reports mean-gradient displacement and covariance trace. These analyses provide additional evidence about the effects of dependent sampling on rollout groups and gradient estimation.

Critical weaknesses

W1. Limited Novelty and Practical Guidance.

The coupling strategies studied in Section 4 build on established sampling constructions. In particular, the randomly shifted lattice is adopted from arithmetic sampling (Vilnis et al., 2023), while stratified sampling and token-level Sobol sampling are investigated as additional alternatives. Several theoretical results also follow from standard probability and stratified sampling arguments. Thus, the main contribution lies in systematically characterizing different coupling strategies rather than developing a fundamentally new coupling method.

More importantly, the central finding of Section 5.3 is that no single coupling is uniformly optimal, and the relative performance of different samplers depends on the geometry of the success region. However, the paper does not provide a procedure for determining which coupling should be used for a given problem based on this geometry. Without a way to characterize the success region or select an appropriate sampler, the theoretical findings offer limited guidance for practical sampler selection. Section 7 explicitly identifies samplers that adapt their dependence structure as a direction for future work, leaving this design question unresolved.

W2. Limited Generality of Test-Time Scaling Results.

The theoretical setup in Section 5 focuses on pass@k for binary-valued rewards. Although pass@k is a useful coverage metric, the introduction also discusses self-consistency and verifier-based selection as test-time scaling methods. The experiments do not establish whether improvements in pass@k lead to improvements when the final response is selected or aggregated using these methods. Consequently, the evidence is strongest for coverage rather than for the broader test-time scaling procedures discussed in the introduction.

The dependence on success-region geometry also deserves closer examination. Section 6.1 explicitly states that Sudoku and 1D-ARC have a single correct output sequence and hence a single arithmetic-coding interval, for which Proposition 2 already guarantees optimal coverage with lattice sampling. Countdown and the code-generation experiments offer evidence for settings with multiple valid solutions, but the paper does not systematically relate the observed gains to the structure of the success region. In addition, the arithmetic decoding construction assigns intervals according to token probabilities (Sections 3–4; Figure 9). However, the paper does not investigate whether changing the ordering of tokens within these intervals, while preserving the marginal language model distribution, affects the relative performance of the samplers.

W3. Insufficient Validation of RL Efficiency.

The RL evaluation in Section 6.2 is limited to Maze and Sudoku using Qwen3.5-0.8B-Base. Although Figure 5 reports 18–24% fewer training steps to reach specified training reward levels, these improvements are measured using training reward rather than performance on a separate validation set. The paper does not clarify whether such a validation set was used or report validation pass@1 throughout training. Consequently, it remains unclear whether coupled sampling can achieve comparable performance on unseen problems with fewer training steps.

Moreover, the improvements in final pass@1 are less consistent than the training-efficiency results. As shown in Table 1, lattice and stratified sampling improve Sudoku pass@1 by only 1.0 percentage point, while Sobol sampling achieves the same 20.0% as i.i.d. sampling. Thus, the faster increase in training reward is not consistently accompanied by higher final test-set pass@1 across all settings.

The theoretical analysis also does not fully explain the observed training gains. Theorem 3 establishes a covariance reduction guarantee for a standard policy-gradient estimator, whereas the experiments use mean-centered GRPO. Although Appendix A.4 characterizes the bias introduced by dependent sampling in RLOO and relates it to mean-centered GRPO, the paper does not establish whether the resulting bias–variance tradeoff is responsible for the observed improvements. Table 4 provides gradient statistics, but these are not connected to the reported training trajectories or final performance differences.

Questions for authors

Q1. From theoretical tradeoffs to sampler selection.

The paper shows that the relative performance of different couplings depends on the success region, while Section 7 points toward samplers that adapt their dependence structure. Without knowing the success region for a given problem, how should one choose between stratified sampling, randomly shifted lattice sampling, and token-level Sobol sampling? Can the authors identify any property measurable from the available rollouts that would make the theoretical results more actionable?

Q2. Success-region geometry and the arithmetic decoding construction.

Could the authors further investigate the success-region structures underlying the Countdown and code-generation results, where multiple valid solutions may exist? How sensitive are the relative coverage gains of the coupling strategies to the ordering of tokens used in the arithmetic decoding construction (Figure 9), while keeping the marginal language model distribution unchanged?

Q3. Beyond pass@k in test-time scaling.

The paper evaluates test-time scaling primarily through pass@k. Do the improvements observed with coupled sampling also persist under self-consistency or verifier-based selection, both mentioned in the introduction? Such results would clarify whether better coverage leads to better final responses under these test-time scaling procedures.

Q4. RL training efficiency and generalization.

Figure 5 reports 18–24% fewer training steps to reach specified training reward levels, while Table 1 only reports final-checkpoint test-set pass@1. Could the authors clarify whether a separate validation set was used and, if available, report validation pass@1 throughout training? Comparing the number of training steps required to reach matched validation performance would help establish whether the improvements in training reward translate into faster improvements on unseen problems.

Q5. End-to-end computational savings.

The paper reports 25–47% fewer inference rollouts and 18–24% fewer RL training steps. Could the authors provide wall-clock time, generation throughput, or total GPU-time comparisons under matched hardware conditions, accounting for the additional operations required by the coupled samplers? This would help establish how the reported sample-efficiency gains translate into practical computational savings.

Q6. Consistency of gradient statistics.

Section 6.2 reports that the RMS mean-gradient displacement is 0.17–0.20 times the RMS noise of the i.i.d. estimator. However, Table 4 reports squared mean shifts of 0.0007–0.0011 and an i.i.d. covariance trace of 0.082, which yield ratios of approximately 0.09–0.12 when taking square roots. Could the authors clarify how the reported ratios of 0.17–0.20 are computed and whether different normalization factors are used?

2 comments

Thanks for your thoughtful review! We are glad you found the problem well motivated, the presentation clear, the theory useful, and the experiments well controlled. We ran the suggested experiments, now in Appendix A.1 (changes in red). Numbers below refer to the revised PDF.

W1: Novelty

We agree that our contribution is characterization rather than the new couplings, and we see this as a key contribution of the paper: progress in ML also comes from understanding when and why existing methods succeed or fail. We give a systematic theoretical and empirical characterization of coupled sampling for LMs: coverage guarantees, optimality conditions and failure modes, the robustness–optimality tradeoff, and, for RL, how coupling affects gradient covariance and the bias it introduces in group-relative estimators. We believe these are timely questions, and our work not only shows that coupling can be fruitful, but opens the door to further applications of QMC in modern LLM settings beyond what was explored in prior work.

W1 / Q1: Practical guidance

We offered the following guidance in the submission: problem difficulty tells you when to couple, and stratification is the safe bet for how. Estimate each problem's pass rate p from a small pilot batch, couple when p is near 1/k, and use stratified sampling when a worst-case guarantee matters.

  • When to couple. The gain over i.i.d. peaks at p1/k (Proposition 1) and vanishes for p1/k or p1/k.
  • Which coupling. Stratification is the guaranteed choice: it weakly dominates i.i.d. coverage for any measurable success region. Lattice is the higher-upside choice: it is optimal for contiguous regions but downside confined to fragmented, e.g. periodic, regions. Empirically this risk is mild: on Countdown, whose multiple solutions fragment the success region, lattice falls further short of the bound but still beats i.i.d., as it does on every task (Table 6, Figure 8).

W2 / Q3: Beyond pass@k

We added new results for self-consistency (Figure 6): every coupled sampler matches or beats i.i.d. cons@k for 4k32 on all four tasks, by up to 4.2 points.

W2 / Q2: Success-region geometry and token order

Thanks for your question! It motivated us to generalize the specific geometries in Propositions 2–3.

New geometric theory (Appendix A.5, Figures 13–14). We also derive exact pass@k for lattice and stratified sampling for arbitrary success regions A (Theorem 7), and necessary and sufficient conditions for optimality (Corollary 1). Stack the k strata of [0,1) as rows. A lattice batch is one column, with the same offset across rows; a stratified batch has an independent point in each row. Which coupling wins depends on how A spreads across columns versus concentrates in rows, as visualized in Figure 14.

Geometry relationship to success. Our empirical results track success-region structure. On Sudoku and 1D-ARC (single solution, contiguous region), lattice nearly attains the bound, as Proposition 2 predicts (90.3 vs. 90.4 on Sudoku, Table 6); on Countdown (fragmented regions), it is less dominant but still beats i.i.d.

Token order (Figure 8). Reordering the vocabulary by token id preserves the advantage of lattice and stratified sampling over i.i.d. on every task; pass@64 moves by at most 1.4 points.

W3 / Q4: RL efficiency and generalization

Results on held-out evaluation. Each task's 1000 test problems are disjoint from the RL training problems; we now state this explicitly in the paper. Measuring held-out pass@1 every 100 steps (Figure 7), every coupled sampler reaches the target before i.i.d. (5–14% fewer steps on Maze, 7–19% on Sudoku) and finishes 1.2–2.5 points higher. Final pass@1. Coupled samplers improve Maze by 1.8–2.3 points (Table 1); on Sudoku, lattice and stratified gain 1.0 point and Sobol ties.

Theory and training gains. Coupling cuts the gradient covariance trace by 50–62%, while the mean-gradient displacement is only 0.09–0.12 times the i.i.d. noise level (Table 5). The bias from Appendix A.5 is thus small relative to the variance reduction, which, with fewer zero-variance groups (Fig 5), is consistent with faster training.

Q5: End-to-end compute

(Table 2) Lattice and stratified reach 95–97% of i.i.d. throughput, and RL step times match i.i.d. within 1%. The 25–47% reduction in rollouts translates to wall-clock savings.

Q6: Gradient statistics

Thank you for catching this; 0.17–0.20 was indeed a typo. From Table 5, ∥gˉm−gˉiid∥2/tr⁡Cov^(gˉiid)=0.09\sqrt{\|\bar g_m - \bar g_{\mathrm{iid}}\|^2 / \operatorname{tr}\widehat{\mathrm{Cov}}(\bar g_{\mathrm{iid}})} = 0.09–0.12, consistent with the 0.9–1.4% squared ratios in the caption. We corrected Section 6.2; the conclusion is unchanged.

We hope these additions address your concerns. If you feel they strengthen the paper, we would be grateful if you would consider updating your scores.

Thank you for the detailed responses and additional experiments. I appreciate the substantial effort you have made to address my concerns.

The new results and analyses have addressed most of my questions, particularly regarding self-consistency, success-region geometry and token ordering, RL generalization, and end-to-end computational efficiency. The clarification of the gradient statistics is also appreciated.

However, my assessment of the paper's novelty remains unchanged: its main contribution is still the systematic characterization of existing coupling strategies rather than the development of a new sampling method. Therefore, while I appreciate the additional work, I will maintain my current score.

Thank you again for the thoughtful and thorough rebuttal.

Reviewer_ReaWOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies the problem of designing coupled samplers for language models. Unlike conventional sampling methods that generate rollouts independently, coupled sampling introduces dependencies among multiple rollouts through carefully designed coupling strategies. Building on arithmetic sampling, the paper systematically explores different coupling strategies, including independent sampling, stratified sampling, randomly shifted lattice sampling, and token-level Sobol sampling. It further provides a theoretical analysis of these strategies, showing that no single strategy consistently outperforms the others. The paper evaluates coupled sampling in three settings: test-time scaling, reinforcement learning, and code generation. Experimental results demonstrate the benefits of coupled sampling across these settings, with lattice sampling performing best in most cases.

Critical strengths

S1. The paper studies an important problem of designing coupled samplers for language models to improve exploration across multiple rollouts.

S2. The paper provides a systematic study of different coupling strategies, combining theoretical analysis with extensive experiments across test-time scaling, reinforcement learning, and code generation.

Critical weaknesses

W1. The technical novelty of the paper seems limited. Vilnis et al. (ICML 2023) already introduced arithmetic sampling based on randomly shifted lattice points, together with theoretical analyses of diversity, unbiasedness, and variance. Moreover, Amballa et al. (ICLR 2025) extended arithmetic sampling to multi-sample reasoning with self-consistency. The current paper builds on these ideas and compares additional coupling strategies across different settings. It should more clearly distinguish its new theoretical and algorithmic contributions from these prior works, particularly given that lattice sampling, which performs best in most experiments, is already a method proposed by existing studies.

W2. The theoretical analysis lacks a rigorous characterization of when different coupling strategies are effective. For example, the paper states that lattice sampling can achieve optimal pass@k under geometrically favorable success regions but perform substantially worse under unfavorable ones. However, it does not clearly characterize these geometric conditions or establish when lattice sampling is preferable to other strategies.

Questions for authors

Q1. What are the main theoretical or algorithmic contributions beyond Vilnis et al. (ICML 2023) and Amballa et al. (ICLR 2025), particularly for lattice sampling?

Q2. Can the authors provide a more rigorous characterization of the geometrically favorable and unfavorable conditions under which lattice sampling achieves optimal or poor pass@k?

2 comments

Thank you for your review! We are glad you found the problem important and our study systematic, combining theory with experiments across test-time scaling, RL, and code generation. We have revised the paper to address both concerns (changes in red); section numbers below refer to the revised PDF.

W1 / Q1: Contributions beyond prior work

It should more clearly distinguish its new theoretical and algorithmic contributions from these prior works […]

Thank you for this suggestion. We note that Amballa et al. (ICLR 2025) is the paper we cite as Parashar et al. (2025), its arXiv version; we have updated the citation.

Our contributions go beyond prior work in three directions, which we now state explicitly in the introduction.

1. A pass@k theory of couplings. We show that any marginal-preserving coupling is capped at {kp,1} and that the headroom over i.i.d. sampling peaks at p=1/k (Theorem 1 Proposition 1). We then characterize when each coupling attains this ceiling and when it fails: stratification never does worse than i.i.d. (Theorem 2), whereas lattice sampling is optimal for contiguous success regions (Proposition 2) but can fall below i.i.d. (Proposition 3). Prior work does not analyze either question.

2. Couplings and estimators beyond the lattice, including for RL. We bring stratified and token-level Sobol couplings to language models, with unbiased pass@k estimators under coupling. In policy-gradient RL, dependence between rollouts affects not only coverage but also gradient estimation: we prove that stratification reduces policy-gradient variance (Theorem 3) and derive the exact bias that any coupling introduces into leave-one-out baselines (Section A.6).

3. Experiments beyond prior work. Prior work evaluates the lattice only for self-consistency and MBR decoding. We compare lattice, stratified, and Sobol couplings in more modern LLM settings, namely, test-time scaling (matching i.i.d. pass@k with 25–47% fewer samples), code generation, and RL training. In these settings, we study gradient statistics, zero-variance groups, training efficiency, and held-out performance.

W2 / Q2: Rigorous characterization of favorable and unfavorable geometries

The theoretical analysis lacks a rigorous characterization of when different coupling strategies are effective.

We agree this is an important question. In the original submission, Propositions 2–3 already analyzed the two extreme geometries: a contiguous success region, where lattice sampling attains the optimal pass@k, and a 1/k-periodic one, where lattice falls below i.i.d. while stratified sampling matches it.

Following your suggestion, we now generalize these results. In particular, we now give the exact pass@k of lattice and stratified sampling for an arbitrary success region A (new Section A.5, Theorem 7 and Corollary 1).

The key idea in our analysis is to stack together kk contiguous, equally-sized sub-intervals of [0,1)[0,1) as rows. A lattice batch is then one column, with the same offset in every row, while a stratified batch has an independent point in each row.

  • Lattice sees AA column-wise. It is optimal when no column intersects AA twice (p≤1/kp\le1/k) or every column intersects AA (p>1/kp>1/k), and it falls to pass@1 when AA is 1/k1/k-periodic.
  • Stratified sees AA row-wise. It is optimal when AA lies in one row (p≤1/kp\le1/k) or covers a whole row (p>1/kp>1/k), and it never falls below i.i.d.

Which coupling wins is a trade-off between how AA spreads across columns and how it concentrates in rows. We visualize this in Figure 14.

We hope these revisions clarify our contributions and address your concerns. If so, we would be grateful if you would consider updating your scores.

Since the response period is ending soon, we kindly ask the reviewer if we've addressed their concerns and, if so, if the reviewer would consider updating their score.

Comments on the paper

1 comment

We thank the reviewers for their valuable feedback and suggestions. Below we summarize our revisions, which include new theoretical and empirical results which address the concerns that reviewers raised.

Full characterization of success-region geometry optimality + practical guidance

Reviewers asked for a general characterization of how pass@k for different samplers depends on the success region geometry. In our initial submission we provided particular cases, but we generalize these earlier analyses in Section 5.3 and Appendix A.5 of our revised paper. In particular, we calculate the pass@k analytically for both samplers, giving general conditions for when these samplers achieve their worst case and best case performance

These theoretical results closely predict our experimental results.

As some reviewers requested, we now provide practical guidance on samplers: in brief, stratified always offers a robust, guaranteed improvement over i.i.d., whereas lattice offers higher upside and empirically improves further over i.i.d.

Clarified contributions w.r.t. prior works

In the Introduction, we now more clearly describe how our work extends previous work on arithmetic sampling: We extend the coupling framework beyond lattice by introducing stratified and token-level Sobol, which come with different theoretical and empirical tradeoffs than lattice (e.g. stratified weakly dominates i.i.d. coverage, Theorem 2). We provide a very general set of theoretical analyses for modern test-time scaling and RL settings: we characterize when and by how much coupled samplers can improve over i.i.d. samplings in pass@k settings, give unbiased bootstrapped estimators, prove policy gradient variance reduction, and relate samplers’ coverage guarantees to the success-region geometries induced by arithmetic coding. These results are especially important for practitioners training and serving language models today, and are not studied in prior work. We provide experimental results on a wide range of reasoning and coding settings: we show coupling yields sample-efficiency gains for pass@k, self-consistency, and RL. We also shed light on the mechanisms for these improvements by examining solution diversity, gradient statistics, and zero-variance group proportion.

New empirical results

We also include new results that 1) show dependent sampling improves performance even on settings where we do not have access to an oracle verifier (via majority vote) and 2) show that coupled samplers improving training efficiency: reducing the number of training steps required to achieve a target training and hold-out validation performance as well.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.