- Rating
- 3(+1)
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3(+1)
Read review
Paper summary
The paper proposes a best-of-n test-time scaling algorithm that uses exponential noise instead of gumbel noise (where gumbel noise would lead to the classical soft-best-of-n sampling distribution). The paper supports this with extensive theory, and shows gains in terms of FLOPs over baselines like soft best-of-n and GSI [1] in practice, however lacks certain empirical evaluations that would help strengthen the paper.
[1] Geuter, J., Mroueh, Y., & Alvarez-Melis, D. (2026). Guided Speculative Inference for Efficient Test-Time Alignment of LLMs. International Conference on Learning Representations (ICLR).
Critical strengths
- exponential best-of-n is a new sampling method, which comes with a very nice "early-exit" property: one can score responses one by one, and the first one to cross a threshold can be picked without changing the final distribution
- experiments show clear improvements over methods like soft best-of-n and GSI
- the paper provides very extensive theory, although I haven't checked it for correctness
Critical weaknesses
- the novelty is somewhat limited: GSI is an established method from the literature; the only proposed change is the noise schedule in the best-of-n-sampling procedure (with the added effect that the proposed noise schedule allows for an "early-exit" scheme, although the benefits of this scheme are unclear, see the next bullet point). However, this noise schedule itself is also not novel, and the early-exit identity has previously been established [2].
- I think there's an important ablation that does not seem to be in the paper: Include (i) full parallel scoring (i.e. without splitting the batch for early exiting) with likelihood clipping as a baseline, and compare, in terms of accuracy, candidates scored, and wall-clock time, against (ii) full parallel scoring without clipping, (iii) default early exit with clipping. This would help evaluate (a) what difference likelihood clipping makes for accuracy (as clipping potentially introduces an error that is not sufficiently discussed), and (b) if the early-exit strategy, which requires more forward passes through the verifier, only saves on FLOPs, or if it also saves wall-clock time.
- Another helpful ablation: over the exact "early exit batch splitting schedule" (instead of always ) If these ablations are included and they show that clipping doesn't substantially hurt and that the early-exit scheme also helps reduce wall-clock time, I believe the paper can also be a borderline accept.
[2] Ding, Z., et al. (2021). The Permute-and-Flip Mechanism is Identical to Report-Noisy-Max with Exponential Noise. arXiv preprint arXiv:2105.07260.
Questions for authors
- bolding in tables is inconsistent (e.g. table 9), and looks misleading, as ExpBoN values are bolded even if RSD is usually much faster (while the authors mention the intended meaning of the bolding in the caption, this still looks misleading)
4 comments
Helpful ablations, thank you!
W2. Ablations
We ran exactly the ablations that the reviewer suggested, and the conclusion, in short, is: clipping does not substantially hurt, and the early exit reduces wall-clock time, not only FLOPs.
Setup. MATH500 (the paper's 400-problem subset), , Qwen2.5-Math 1.5B/7B with Qwen2.5-Math-PRM-7B, , , 5 seeds. All configurations use the same hardware and software stack, with identical concurrency. Time is measured in wall-clock seconds per problem over the full evaluation.
| Configuration | Clip | Early exit | Accuracy (%) | Candidates scored / step | Time (s/problem) |
|---|---|---|---|---|---|
| GSI (Gumbel) | -- | -- | 16 | 16.8 | |
| (ii) Full parallel, no clip | -- | -- | 16 | 17.0 | |
| (i) Full parallel, clip | ✓ | -- | 16 | 17.1 | |
| (iii) Default early exit, | ✓ | ✓ | 9.10 | 13.2 | |
| Early exit, | ✓ | ✓ | 11.82 | 14.8 | |
| Early exit, | ✓ | ✓ | 10.00 | 13.7 | |
| Early exit, | ✓ | ✓ | 10.54 | 13.8 |
-
(a) Effect of clipping on accuracy. Full parallel scoring reaches with clipping and without. Default ExpGSI, (iii), reaches , against for GSI.
-
(b) Wall-clock, not only FLOPs. The early exit lowers time per problem from 17.1 s to 13.2 s (23% reduction) against full parallel scoring of the same clipped score, and from 16.8 s to 13.2 s (22% reduction) against GSI. The reduction holds for every seed separately: 18–26% against full parallel scoring and 16–28% against GSI. The extra round trip to the verifiers is paid only when the first batch of 4 has no hit, about 42% of steps (), and the second batch is still scored in parallel. All full-scan configurations take 16.8–17.1 s, so the saving comes from the early exit, not from the noise alone.
-
(c) Schedule. Accuracy is 82.60%, 83.05%, 82.70%, and 82.40% for , respectively. In terms of computational cost, scores the fewest candidates and is the fastest. With , the second batch contains 15 candidates and is invoked more frequently, whereas scores half the pool before it can stop. This illustrates the trade-off in the expected verifier work (Section 4): a small misses more often, while a large incurs a higher initial evaluation cost.
We have added this new table and results in the revised manuscript. We thank the reviewer again for suggesting this.
Q1. Bolding in tables.
We agree. Bolding only the ExpGSI-versus-GSI comparison is misleading when RSD is faster. In the revision, we will bold the best value in each column across all methods and mark the ExpGSI-versus-GSI comparison with a separate symbol.
Summary
We sincerely thank the reviewer for the constructive comments and suggestions. In responses above, we have clarified the novelty of ExpBoN and its relation to the existing PF mechanism. More importantly, we have conducted the specific ablation experiments suggested by the reviewer, including comparisons of full parallel scoring with and without clipping, the proposed early-exit scheme, and different batch-splitting schedules.
The new results show that clipping does not substantially affect accuracy, while the proposed early exit achieves a 23% reduction in wall-clock time compared with full parallel scoring using the same clipped scores, with comparable accuracy.
We particularly appreciate the reviewer's comment that these additional ablations, if they confirm limited accuracy degradation from clipping and real wall-clock improvements, could support a Borderline Accept. We hope that our new experiments and clarifications provide the requested evidence and adequately address the reviewer's concerns. We would be very grateful if the reviewer could kindly reconsider their rating in light of these results. Thank you again for your time and consideration!
Remaining concerns addressed by rebuttal
Thank you for your additional experiments! They satisfactorily address all concerns from my initial review, as far as I can see. Hence, I will raise my score to 3 and recommend acceptance of the paper.
I do encourage the authors to include a few more datasets in their results though, as the current experimental results are not very extensive; I noticed I forgot to ask for this in my initial review, so I'm not taking that into consideration for my final score, but believe it should be included in the final version of the paper.
Thank you very much for your encouraging feedback, increased rating, and recommendation for acceptance!
We are delighted that our additional experiments have satisfactorily addressed your concerns. We also appreciate your suggestion regarding the breadth of our empirical evaluation and will make an effort to include a few more datasets in the final version of the paper.
Thank you again for your constructive feedback and valuable support!
Novelty and relation to Ding et al. (2021).
We thank the Reviewer 3V3f for acknowledging our extensive theory and also the precise suggestions. We address the weaknesses as follows. We have also used the permitted additional page to further clarify and strengthen the manuscript, with all changes highlighted in blue.
W1. Novelty and relation to Ding et al. (2021).
We thank the reviewer again for recognizing the theoretical contributions and the early-exit property of ExpBoN. We agree that exponential-noise report-noisy-max and its equivalence to Permute-and-Flip (PF) are known. However, we would like to clarify that our contributions go beyond directly applying this mechanism to BoN.
First, choosing exponential noise for BoN is not arbitrary. While various noise distributions could be considered, it is not immediately clear which one would yield favorable convergence toward the KL-regularized optimal distribution. Our key observation is that the exponential tail and memorylessness lead to an exact finite-n decomposition (Theorem 3.1), which yields geometric convergence in TV, both directions of KL divergence, and expected reward, in contrast to the polynomial convergence of Gumbel-based SBoN. These results, together with our regret guarantees, were not established in the existing PF literature. We will make the motivation for this choice more explicit in the revised manuscript.
Second, our early-exit result differs from the existing PF identity. Ding et al (2021) establish the equivalence between PF and exponential-noise report-noisy-max, where PF sequentially selects the first successful candidate. However, to our own understanding, their algorithm first computes the exact maximum score q⋆=maxiqi, which generally requires evaluating all candidate scores. In contrast, our method only requires a known upper bound U≥maxisi, without computing the actual maximum. We further characterize the no-hit event and show that using the appropriate residual selection rule recovers exactly the full exponential-noise BoN distribution. This enables early exit without evaluating all candidate scores, which is particularly valuable in GSI, where each score requires expensive model evaluations.
Thus, our main contributions are the identification of exponential noise as a particularly suitable choice for BoN, its new finite-sample convergence and regret guarantees, and the resulting computationally efficient early-exit implementation. We will further clarify these distinctions in the revision.