- 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 from a point to the generated sequence. The inverse map of a sequence occupy an interval of length . Any joint distribution over with marginals then yields rollouts each exactly distributed as . 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 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.
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.