acceptodds
Under review as a conference paper at ICLR 2027

ExpBoN: Exponential-Noise Best-of-n for Efficient Test-Time LLM Alignment

Abstract

Best-of- (BoN) sampling is a simple yet effective inference-time alignment method, but hard maximization provides only coarse control over the trade-off between reward and distribution shift. Soft Best-of- by Verdun et al. (2025) provides smoother control and converges to the optimal distribution associated with KL-regularized reward maximization, but its known guarantees decay only polynomially in . In this paper, we introduce ExpBoN, an alternative soft BoN method based on the exponential-noise report-noisy-max mechanism: it perturbs the scaled rewards with exponential instead of Gumbel noise before the argmax. Its output distribution admits an exact finite- decomposition into the optimal tilted distribution plus a residual whose weight vanishes geometrically, and this single structural property has two consequences. Statistically, it yields geometric convergence in total variation, expected reward, and both directions of KL divergence, together with regret guarantees under proxy-reward misspecification. Computationally, it permits an exact early exit: candidates can be examined sequentially in random order, and the first whose noisy score crosses a fixed threshold is already an exact sample, so the remaining candidates need not be scored. As a case study, we integrate ExpBoN into the guided speculative inference (GSI) framework by Geuter et al. (2026), where every candidate score requires both a reward-model and a target-model evaluation. On MATH500, MMLU-STEM, and Minerva Math with the Qwen2.5-Math and Qwen3 model families, the resulting ExpGSI maintains comparable accuracy while reducing GSI's estimated computation by 14%-39% across candidate budgets for Qwen2.5-Math and by up to 45% at for Qwen3. The exact early exit applies whenever candidate scores are bounded above; we evaluate it inside GSI.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Best-of-N sampling, test-time alignment, large language models, reward-guided decoding, speculative inference

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_3V3fOpenReview ↗
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 b=max⁡(1,⌊n/4⌋)b=\max(1,\lfloor n/4\rfloor)) 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
AuthorsOpenReview ↗

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-nn 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⋆=max⁡iqiq^\star=\max_i q_i, which generally requires evaluating all candidate scores. In contrast, our method only requires a known upper bound U≥max⁡isiU\geq\max_i s_i, 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.

AuthorsOpenReview ↗

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), n=16n=16, Qwen2.5-Math 1.5B/7B with Qwen2.5-Math-PRM-7B, β=20\beta=20, C=0.45C=0.45, 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.

ConfigurationClipEarly exitAccuracy (%)Candidates scored / stepTime (s/problem)
GSI (Gumbel)----82.20±0.9482.20 \pm 0.941616.8
(ii) Full parallel, no clip----83.20±0.9983.20 \pm 0.991617.0
(i) Full parallel, clip✓--82.50±1.7982.50 \pm 1.791617.1
(iii) Default early exit, b=4b=4✓✓82.70±0.5782.70 \pm 0.579.1013.2
Early exit, b=1b=1✓✓82.60±1.0482.60 \pm 1.0411.8214.8
Early exit, b=2b=2✓✓83.05±0.4883.05 \pm 0.4810.0013.7
Early exit, b=8b=8✓✓82.40±1.7082.40 \pm 1.7010.5413.8
  • (a) Effect of clipping on accuracy. Full parallel scoring reaches 82.50±1.7982.50 \pm 1.79 with clipping and 83.20±0.9983.20 \pm 0.99 without. Default ExpGSI, (iii), reaches 82.70±0.5782.70 \pm 0.57, against 82.20±0.9482.20 \pm 0.94 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 (9.10=4+12×0.4259.10 = 4 + 12 \times 0.425), 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 b=1,2,4,8b=1,2,4,8, respectively. In terms of computational cost, b=4b=4 scores the fewest candidates and is the fastest. With b=1b=1, the second batch contains 15 candidates and is invoked more frequently, whereas b=8b=8 scores half the pool before it can stop. This illustrates the trade-off in the expected verifier work b+ρb(n−b)b+\rho^b(n-b) (Section 4): a small bb misses more often, while a large bb 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!

Reviewer_3V3fOpenReview ↗

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!

Reviewer_Raa9OpenReview ↗
Rating
3
Confidence
4(+1)
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes ExpBoN, an efficient test-time alignment method. Conventional Soft Best-of-n (SBoN) constructs a softmax distribution over candidate responses based on their reward model scores. Sampling from this distribution can be equivalently interpreted as stochastic selection with Gumbel noise. The proposed method replaces Gumbel noise with exponential noise, which can be viewed as applying Permute-and-Flip to BoN sampling. A particularly important contribution is the theoretical proof that the output distribution converges geometrically to the optimal distribution. Furthermore, the proposed method enables exact early exit, improving computational efficiency. Experiments using Qwen2.5-Math and Qwen3 on mathematical reasoning benchmarks demonstrate that the proposed method significantly reduces estimated computational costs while maintaining accuracy comparable to the existing GSI method.

Critical strengths

The proposed method achieves geometric convergence, improving upon the polynomial convergence rate of conventional SBoN, with a simple algorithm and strong theoretical guarantees. The experimental results are also promising. In particular, ExpGSI, which integrates the proposed method into GSI, significantly reduces estimated computational costs while maintaining accuracy comparable to that of GSI.

Critical weaknesses
  1. One minor concern is the need to set the hyperparameters β\beta and CC. While β\beta is inherited from GSI, CC is determined using a separate calibration dataset. This paper reports that the method is relatively robust when CC varies from 0.5 to 1.5 times its default value. However, Table 14 shows that increasing CC leads to higher estimated computational costs. I suspect that the appropriate value of CC may depend on the dataset and the choice of β\beta.

  2. Another concern is that the end-to-end experiments are limited to mathematical and STEM reasoning benchmarks. These benchmarks generally have clearly defined correct answers, whereas many practical applications do not. In such settings, reward scores may have different distributions, potentially with many responses receiving similar scores. I would be interested in understanding how much the proposed method improves the convergence rate under such conditions.

Questions for authors
  1. The paper uses C=0.45C = 0.45. Does a similar value of CC work well for different values of β\beta or across different datasets?

  2. Would it be possible to conduct experiments on datasets beyond Math/STEM benchmarks? For example, AlpacaEval with length-controlled win rate could be a suitable benchmark.

  3. The proposed method uses exponential noise, but other noise distributions could also be considered. Could using different noise distributions lead to further improvements? For example, in tasks where correct answers are less clearly defined than in Math/STEM benchmarks and reward model scores are more ambiguous, other noise distributions might be beneficial. I would be interested in whether such alternatives could offer advantages and whether they could retain the theoretical guarantees of ExpBoN.

4 comments
AuthorsOpenReview ↗

Thank you for your acceptance and comments! Pamameters and AlpacaEval.

We thank the reviewer Raa9 for the encouraging review and the concrete suggestions; we ran an experiment for each. We have also used the permitted additional page to further clarify and strengthen the manuscript, with all changes highlighted in blue.

W1 / Q1. Does a similar CC work across β\beta and datasets?

Yes. By construction, CC does not depend on β\beta: it bounds the log-likelihood ratio d=log⁡πB−log⁡πSd=\log\pi_B-\log\pi_S, which depends only on the draft/target pair. It is calibrated once, without reward labels, on 60 held-out MATH problems. We now test it at other β\beta with C=0.45C=0.45 unchanged, against GSI on the same acceptance gate (MATH500, n=16n=16, 5 seeds):

β\betaAccuracy (%) GSI / ExpGSITime (s/problem) GSI / ExpGSICandidates scored / step (ExpGSI)
1082.90 / 82.8518.7 / 14.18.88 / 16
2082.20 / 82.7016.8 / 13.29.10 / 16
4083.35 / 82.8515.6 / 12.89.39 / 16

A replay over saved candidate pools gives the same picture: raising β\beta from 5 to 40 moves the probability of a hit within 16 candidates only from 0.76 to 0.73, less than a 4×4\times change of CC does (0.5C^→2C^0.5\widehat C\to2\widehat C: 0.76 to 0.70). Across datasets, the same CC was used without retuning on MMLU-STEM and Minerva and for the Qwen3 pair, at accuracy comparable to GSI (Tables 1, 10--12).

Regarding Table 14, cost grows with CC by design: a larger CC raises the ceiling UC=β+CU_C=\beta+C, so each candidate is less likely to cross it. Accuracy is flat from 0.5C^0.5\widehat C to 1.5C^1.5\widehat C, and the smaller values are cheaper. The 95th-percentile rule is therefore a conservative default, and a practitioner can lower CC to trade a little clipping for fewer evaluations.

W2/ Q2. Beyond math/STEM: AlpacaEval.

Following your suggestion, we ran GSI and ExpGSI on all 805 AlpacaEval 2 prompts (Qwen2.5-3B-Instruct draft, Qwen2.5-7B-Instruct target, n=16n=16, β=20\beta=20, temperature 0.70.7), scoring steps with the reward model Skywork-Reward-Llama-3.1-8B-v0.2. Both methods are judged with the AlpacaEval 2 template using GPT-4o, and CC follows the paper's label-free rule.

ExpGSI reaches an LC win rate of 39.5039.50, versus 38.9638.96 for GSI. Time per prompt is 14.8414.84s versus 16.5816.58s, so ExpGSI is 10.510.5\\% faster at the same quality. The early exit thus carries over to open-ended generation, where rewards have no clear correct answer. We have added this experiment to the revision.

AuthorsOpenReview ↗

Other noise distributions and conclusion, thank you again!

Q3. Other noise distributions.

Thank you for this question; it led to a clean characterization, which we will add as a proposition. Suppose the noise has an exponential right tail on [0,∞)[0,\infty): P(N>t)=p e−tP(N>t)=p\,e^{-t} for t≥0t\ge0, for some p∈(0,1]p\in(0,1], with an arbitrary law below 00. Then, by memorylessness, a candidate with score s≤Us\le U crosses UU with probability p e−(U−s)∝esp\,e^{-(U-s)}\propto e^{s}, so a crossing is still an exact tilted sample. The noisy argmax therefore decomposes exactly as (1−ρpn)P⋆+ρpnQ(1-\rho_p^n)P^\star+\rho_p^nQ, with ρp=1−p(1−ρ)\rho_p=1-p(1-\rho), and the guarantees that follow from the decomposition carry over with ρ\rho replaced by ρp\rho_p. Since ρp≥ρ\rho_p\ge\rho, with equality iff p=1p=1, i.e., N∼Exp(1)N\sim\mathrm{Exp}(1), exponential noise is the unique fastest member of this family. Laplace$(0,1)$ belongs to it with p=1/2p=1/2. Gumbel and Gaussian noise do not, and have no exact tilted component. This is easy to see even numerically: on the 652 real pools (clipped GSI score, exact laws), the median total variation to the target is:

nnExp(1)LaplaceGumbel (SBoN)Gaussian
161.8×10−31.8\times10^{-3}8.8×10−38.8\times10^{-3}2.9×10−22.9\times10^{-2}5.3×10−25.3\times10^{-2}
647.1×10−107.1\times10^{-10}2.9×10−62.9\times10^{-6}6.7×10−36.7\times10^{-3}9.3×10−29.3\times10^{-2}

Gaussian noise even moves away from the target as nn grows. Within the class that keeps the guarantees, ambiguous rewards are not better served by heavier-tailed noise. Lowering β\beta is the right knob in that case, and it also speeds up ExpBoN's convergence. Actually, at the early stage of this work, we tried different families of noise distributions, including Laplace, exponential, Gaussian, and many others. One key observation and contribution of our ExpBoN lies in its unique properties and its perfect match with GSI.

Conclusion

We sincerely thank the reviewer again for the encouraging assessment and constructive suggestions. In response, we have conducted additional experiments examining the robustness of the clipping parameter across different temperatures and datasets, extended our evaluation to AlpacaEval 2, and further investigated alternative noise distributions and their theoretical properties. These results and clarification strengthen both the theoretical motivation and practical applicability of ExpBoN.

We believe that our work makes a meaningful contribution to efficient test-time alignment, supported by rigorous theoretical guarantees and consistent empirical improvements. We hope that these additions adequately address the reviewer's concerns and further strengthen their confidence in our work. We would be very grateful if the reviewer could kindly consider increasing their rating in light of the new evidence, which would greatly support our paper's prospects for acceptance.

Thank you again for your time, consideration, and valuable feedback!

Thank you for the detailed responses and additional experiments. These satisfactorily address my concerns about the choice of CC, applicability beyond math/STEM tasks, and alternative noise distributions. I will maintain my rating of Weak Acceptance but increase my confidence.

AuthorsOpenReview ↗

Thank You for Your Positive Feedback and Increased Confidence

Thank you very much for the encouraging follow-up, continued support, and increased confidence in our work!

We particularly appreciate your suggestions, which motivated us to extend our evaluation to AlpacaEval 2 (10.5% lower wall-clock time with a higher win rate), further establish the novelty and theoretical advantages of exponential noise, and conduct additional ablations confirming up to 23% lower wall-clock time.

We are grateful that these new results and clarifications have satisfactorily addressed your concerns. Thank you again for your valuable feedback and support!

Reviewer_fPXWOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes ExpBoN, which replaces Gumbel noise with exponential noise in Soft Best-of-n. It establishes geometric convergence guarantees and enables exact early stopping. Experiments show that ExpBoN reduces computational costs while maintaining comparable accuracy to GSI.

Critical strengths

The theoretical analysis is solid and comprehensive. The paper establishes geometric convergence guarantees in TV and KL divergence, along with reward and regret bounds, providing a strong theoretical foundation for ExpBoN.

The proposed early-exit mechanism is simple and practical. Experiments across different models and benchmarks demonstrate substantial computational savings of 14–45% with comparable accuracy.

Critical weaknesses

The novelty of the underlying mechanism is somewhat limited. Exponential-noise report-noisy-max and its connection to Permute-and-Flip are already known, so the main contribution lies in the theoretical analysis and application to GSI.

Score clipping introduces additional bias. The clipped target differs from the original GSI target, and the reported results suggest that this bias can be substantial for certain reasoning states.

The practical benefit of geometric convergence is not fully clear. The convergence rate depends on the coverage coefficient, which can be very large in some cases, potentially limiting the advantage under realistic candidate budgets.

There is a discrepancy between the theoretical algorithm and its implementation. The implementation uses unclipped scores in the fallback branch, while the theoretical algorithm uses clipped scores. Further empirical analysis would help clarify the impact of this difference.

Questions for authors

see weakness

5 comments
AuthorsOpenReview ↗

Novelty and Motivation of ExpBoN

Thank you for the positive assessment of our novel theoretic results and of the early exit which is simple and practical. We address the four 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 Motivation of ExpBoN.

We thank the reviewer fPXW again for recognizing the theoretical contributions of our work. We agree that exponential-noise report-noisy-max and its equivalence to Permute-and-Flip (PF) are established, and we do not claim these mechanisms themselves as new. However, we would like to emphasize that our contribution goes beyond directly applying an existing mechanism to Best-of-nn (BoN).

First, the choice of exponential noise is motivated by its nontrivial theoretical advantages in BoN. One could consider various perturbation distributions, such as Gumbel, Laplace, exponential, or geometric noise, and we have tried even more. We will add our effort to the appendix of the paper. It is not immediately clear which choice would yield favorable convergence guarantees toward the KL-regularized optimal distribution.
Our key observation is that the exponential tail and memorylessness of exponential noise lead to a particularly useful structure. Specifically, for a bounded score s(y)s(y) with upper bound UU and E∼Exp(1)E\sim\mathrm{Exp}(1), Pr$(s(y)+E\geq U)=e^{s(y)-U}$. Thus, conditional on crossing this threshold, the selected candidate follows exactly the desired exponentially tilted distribution. This yields the exact finite-nn decomposition in Theorem 3.1, P~n,λ=(1−ρλn)Pλ⋆+ρλnQn,λ,\widetilde P_{n,\lambda} = (1-\rho_\lambda^n)P_\lambda^\star + \rho_\lambda^n Q_{n,\lambda}, which subsequently gives geometric convergence in total variation, expected reward, and both directions of KL divergence. These properties cannot be derived by using other noises; e.g., our Appendix A.8 shows that Gumbel-based SBoN has unavoidable polynomial rates. One major contribution is to identify and rigorously establish these advantages for the BoN setting.

Second, bringing an existing mechanism to a new setting can constitute a meaningful contribution when it yields novel, theoretical and practical improvements. For example, the ICLR 2025 paper Permute-and-Flip: An Optimally Stable and Watermarkable Decoder for LLMs applies the PF mechanism to LLM decoding and establishes new quality-stability guarantees and watermarking properties. Our work studies exponential-noise report-noisy-max in the previously unexplored context of soft BoN. We believe the contribution is not merely the replacement of Gumbel noise by exponential noise, but the resulting exact finite-sample characterization and its implications for convergence, regret, and computational efficiency, which were not established by the existing PF or report-noisy-max literature.

Third, the theoretical structure leads directly to a new computational advantage. The same exponential-tail identity, together with memorylessness, enables an exact early-exit implementation for bounded candidate scores: once a candidate crosses the threshold, the remaining candidates need not be evaluated. This is particularly useful in GSI (ICLR 2026), where scoring each candidate requires expensive reward-model and target-model evaluations. Our experiments demonstrate that ExpBoN reaches a prescribed tilt with fewer candidates than SBoN (e.g., SBoN requires 1.41×1.41\times as many candidates at n=16n=16 on our real candidate pools), while ExpGSI reduces estimated computation by 1414--4545\\% at comparable accuracy.

In summary, while the underlying randomization mechanism is known, we believe that identifying its suitability for BoN, establishing its new finite-nn theoretical guarantees, and translating these properties into an efficient test-time alignment are meaningful theoretical and algorithmic contributions. We will further clarify these distinctions and the motivation in the revised manuscript.

AuthorsOpenReview ↗

Clipping bias; Benefit of geometric convergence; Theory and implementation. Thank you!

W2. Clipping bias.

Clipping is a deliberate, controllable design choice: it is what makes the score bounded, and hence what enables the exact early exit. C=∞C=\infty recovers the unclipped target (Table 14). Theorem 4.1 keeps its effect, τC\tau_C, separate from the finite-nn error, so it never compounds with nn. Note that τC\tau_C in Table 6 is an upper bound on the distortion, not the distortion itself. The quantity that matters is how far the clipped target is from the original GSI target, and how much this moves accuracy. We measured both:

  • Distance between the targets (652 calibration pools, exact computation): The total variation between the clipped and the unclipped GSI target has a median of 0.0050.005 and a mean of 0.0880.088. In expected PRM reward, ExpGSI at n=16n{=}16 reaches 0.98240.9824, versus 0.98460.9846 for the unclipped GSI target.

  • End-to-end (MATH500, n=16n = 16, 5 seeds): ExpGSI reaches 82.70±0.5782.70\pm0.57, and GSI 82.20±0.9482.20\pm0.94.

We have added the end-to-end ablation to Section 5 and report the distance between the two targets next to τC\tau_C in Table 8, please refer to the updated manuscript, where the changed are highlighted in blue.

W3. Practical benefit of geometric convergence; large coverage.

The benefit is already visible at the budget used in our experiments. The table reports the exact finite-nn output laws on the 652652 real pools (no sampling), as the median total variation to the target.

Score, nnExpBoNSBoNExpBoN ≤\le SBoNnn SBoN needs to match ExpBoN
Clipped GSI score, n=16n=161.8×10−31.8\times10^{-3}2.9×10−22.9\times10^{-2}98.6% of poolsMedian 32; >1024>1024 on 42% of pools
Clipped GSI score, n=64n=647.2×10−107.2\times10^{-10}6.7×10−36.7\times10^{-3}99.2% of pools--
Reward score, n=16n=167.6×10−177.6\times10^{-17}2.0×10−42.0\times10^{-4}-->1024>1024 on 93% of pools

At n=16n=16, ExpBoN is already an order of magnitude closer to the target than SBoN, and the gap widens quickly with nn. The geometric rate therefore pays off at the budgets used by GSI and by us (n≤16n\leq 16; GSI scales to n=256n=256).

Table 6 reports the coverage at the ceiling UC=β+CU_C=\beta+C, which sets the early-exit hit rate but not the output law: by Theorem 3.1 the decomposition holds for every ceiling above the largest score. Convergence is governed by the coverage at the pool maximum, max⁡yP⋆(y)/P(y)\max_y P^\star(y)/P(y). Its median is 3.813.81, and 8181\\% of reasoning states have coverage at most 1616. On these states, ExpBoN is one to thirteen orders of magnitude closer to the target than SBoN, and on the remaining states it is still at least as close. We will add this table and report both coverage values in Table 6.

W4. Theory vs. implementation in the no-hit branch.

We thank the reviewer again for the careful check. When no candidate crosses the ceiling, the implementation returns the noisy argmax of the unclipped score, whereas Algorithm 1 uses the clipped score. Both are valid instances of Theorem 4.1, because its bound only uses that a hit has probability 1−ρn1-\rho^n and returns an exact sample, whatever rule is used when no candidate crosses (proof of Thm. 4.1, Appendix). We ran Algorithm 1 exactly as stated.

  • End-to-end (MATH500, n=16n=16, 5 seeds): Clipped no-hit rule: 82.70±0.7882.70\pm0.78; implementation: 82.70±0.5782.70\pm0.57.

  • Exact computatio (652 pools, 2×1052\times10^5 draws each): Although the no-hit branch is taken on about 26% of steps, the two rules differ by a total variation of 0.00080.0008 on average, a median of 00, below Monte-Carlo noise. Their total variation to the GSI target is 0.18640.1864 versus 0.18570.1857, and their expected rewards agree to four digits. The two rules disagree only when the noisy argmax has d>Cd>C, which is rare.

In the revised manuscript, Algorithm states that any rule may be used when no candidate crosses, and name the one we use.

Summary

We thank the reviewer again for the constructive feedback. In above responses, we have (1) clarified the novelty and theoretical motivation; (2) further analyzed clipping bias and its empirical impact; (3) demonstrated the practical advantage of geometric convergence; and (4) corrected the discrepancy between Algorithm 1 and its implementation, with additional experiments validating the theoretical guarantees. We have incorporated these clarifications, corrections, and new results into the revised manuscript, with changes highlighted in blue.

We hope these additions adequately address the reviewer's concerns, and we would be grateful if the reviewer could kindly reconsider their rating in light of the new evidence. Thank you again for your time and consideration!

AuthorsOpenReview ↗

A Gentle Follow-up to Reviewer fPXW

Dear Reviewer fPXW,

As the discussion period is approaching its end (in 9 hours), we would like to kindly follow up on our responses.

We hope that our clarifications, additional analyses, and new experiments have adequately addressed your concerns. We would greatly appreciate any further feedback, particularly if any concerns remain.

If you find our responses and revisions satisfactory, we would be very grateful if you could reconsider your rating in view of the strengthened evidence. :)

Thank you again for your time, constructive feedback, and consideration!

The Authors

Comments on the paper

4 comments
AuthorsOpenReview ↗

Author Response and Summary of Revisions

We sincerely thank the Area Chair and all reviewers for their careful evaluations, constructive comments, and valuable suggestions.

In response, we have provided detailed replies to each reviewer and revised our manuscript using the permitted additional page, with all changes highlighted in blue. Our main additions include:

  1. Theoretical clarifications: Strengthened the motivation and novelty of ExpBoN, investigated alternative noise distributions, and clarified the relationship between the theoretical algorithm and its implementation.
  2. Additional analyses: Further quantified clipping bias and demonstrated the practical benefits of geometric convergence under realistic candidate budgets.
  3. New experiments: Conducted the requested clipping and early-exit ablations, confirming up to 23% lower wall-clock time with comparable accuracy, evaluated different batch schedules and temperature settings, and extended our evaluation to AlpacaEval 2.

We believe these additions substantially strengthen the theoretical and empirical evidence for ExpBoN and address the reviewers' main concerns.

We warmly welcome any further questions or discussion and would be grateful if the reviewers could kindly reconsider their assessments and ratings in light of the new evidence.

Thank you again for your time, consideration, and constructive feedback!

AuthorsOpenReview ↗

Follow-up on Author Responses and Revisions

Dear Reviewers and Area Chairs,

As the discussion period approaches its end in less than 35 hours, we would like to kindly follow up on our responses.

We have provided detailed responses to the reviewers' concerns and substantially revised the manuscript based on your constructive feedback, with all changes highlighted in blue. We have also incorporated additional analyses, clarifications, and experimental results to strengthen the paper. Our main additions include:

  1. Theoretical analyses: Strengthened the motivation and novelty of ExpBoN, clarified the relationship between the theoretical algorithm and its implementation, further quantified clipping bias, and demonstrated the practical benefits of geometric convergence.
  2. Experiments: Conducted the requested clipping and early-exit ablations, confirming up to 23% lower wall-clock time, and evaluated different batch schedules, temperature settings, and AlpacaEval 2.

We particularly thank Reviewer Raa9 for the constructive engagement, continued positive support, and increased confidence in our work. We would also greatly appreciate any further feedback from the other reviewers and Area Chairs, especially if any concerns remain or additional clarification would be helpful.

We sincerely hope these revisions have adequately addressed your concerns. We would be grateful if you could kindly reconsider your assessments in light of the clarifications, revisions, and new evidence.

Thank you again for your time, thoughtful feedback, and consideration!

The Authors

AuthorsOpenReview ↗

Sincere Appreciation to All Reviewers and Area Chairs

Dear Reviewers and Area Chairs,

At the end of the discussion period, we would like to express our sincere gratitude to all three reviewers for their constructive feedback and helpful discussions. We are delighted that all three reviewers now recommend acceptance of our paper, with confidence scores of 4, 4, and 3. We are particularly grateful that our additional theoretical clarifications, analyses, and experiments have addressed the reviewers' concerns.

We understand that reviewing a paper requires substantial time and effort, and we truly appreciate the care and attention you have devoted to evaluating our work. Thank you again for your valuable suggestions!

The Authors

AuthorsOpenReview ↗

Summary of Contributions and Rebuttal Revisions for the Area Chair

Dear Area Chair,

As the discussion period concludes, we would like to briefly summarize our main contributions and the additional evidence provided during the rebuttal to facilitate your assessment.

1. Main Contributions and Novelty

Our central contribution is to identify and establish the unique theoretical and computational advantages of exponential noise for soft Best-of-n sampling, enabling more efficient test-time LLM alignment.

  • Novel finite-sample characterization: While exponential-noise report-noisy-max and its equivalence to Permute-and-Flip are known, we establish a novel exact finite-nn decomposition of the ExpBoN output distribution into the KL-regularized optimal distribution and a residual component whose weight vanishes geometrically (Theorem 3.1).
  • Stronger theoretical guarantees: Building on this decomposition, we establish geometric convergence in total variation, expected reward, and both directions of KL divergence, together with improved finite-sample regret guarantees under proxy-reward misspecification. We also establish a polynomial lower bound for Gumbel-based SBoN, demonstrating a fundamental separation between the two approaches.
  • Novel computational advantage: We develop an exact early-exit algorithm that requires only a known score upper bound, rather than evaluating all candidate scores to determine their maximum. Integrating ExpBoN into guided speculative inference (GSI) yields ExpGSI, which achieves 14–45% lower estimated computation with comparable accuracy across multiple models and benchmarks.

2. Main Additions and Clarifications During Rebuttal

We have substantially revised the manuscript, with changes highlighted in blue, and conducted extensive additional analyses and experiments.

  • Theoretical novelty: Clarified the distinction from existing Permute-and-Flip results and the motivation behind using exponential noise.
  • Practical benefits of geometric convergence: On 652 real candidate pools at n=16n=16, ExpBoN achieves a median TV distance to the target of 1.8×10−31.8\times10^{-3}, compared with 2.9×10−22.9\times10^{-2} for SBoN, demonstrating the advantage of geometric convergence under realistic candidate budgets.
  • Actual wall-clock improvements: Conducted the requested five-seed clipping and early-exit ablations on MATH500. ExpGSI achieves 23% lower wall-clock time than full parallel scoring and approximately 22% lower wall-clock time than GSI, while maintaining comparable accuracy (82.70% versus 82.20% for GSI).
  • Broader applicability: Extended our evaluation to all 805 prompts of AlpacaEval 2, achieving 10.5% lower wall-clock time with a higher length-controlled win rate (39.50% versus 38.96%), demonstrating the benefits beyond mathematical and STEM reasoning.
  • Additional clarifications and ablations: Quantified clipping bias, clarified the theoretical guarantees for the implemented fallback rule, and evaluated different temperature parameters and early-exit batch schedules.

We are particularly grateful that all three reviewers now recommend acceptance, with ratings of (3, 3, 3) and confidence scores of (4, 4, 3).

We respectfully emphasize that our contribution goes beyond replacing Gumbel noise with exponential noise: we establishe a new finite-sample theoretical framework for soft Best-of-n sampling and translate its statistical advantages into measurable computational savings for test-time LLM alignment.

We sincerely thank the Area Chair and all reviewers for their time, constructive feedback, and consideration.

The Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.