/10

Poster4 位审稿人

最低3最高4标准差0.5

ICML 2025

Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignment

Audrey Huang,Adam Block,Qinghua Liu,Nan Jiang,Akshay Krishnamurthy,Dylan J Foster

提交: 2025-01-23更新: 2025-07-24

TL;DR

We analyze the Best-of-N algorithm for choosing among language model generations and demonstrate that it is suboptimal, before introducing a new, optimal algorithm motivated by the principle of pessimism in the face of uncertainty.

摘要

关键词

inference time alignmentbest of npessimismreinforcement learning theoryoffline reinforcement learning

评审与讨论

审稿意见

评分: 32025-03-09

This paper investigates inference-time alignment in language models and demonstrates that naively scaling the Best-of-N heuristic leads to reward hacking, causing performance degradation beyond a certain computational threshold. The authors introduce a new algorithm, InferenceTimePessimism, which leverages χ²-regularization and rejection sampling to mitigate reward hacking effectively. The authors provide theoretical guarantees showing InferenceTimePessimism achieves optimal regret.

给作者的问题

Have you tested or analyzed the performance and robustness of InferenceTimePessimism with significantly noisier or weaker reward models? If so, how sensitive is the algorithm to degradation in reward model accuracy? Similarly, have you experimented with or considered extending InferenceTimePessimism to more open-ended, subjective, or complex tasks, and what challenges might arise in these settings?

论据与证据

The paper's claims are supported by theoretical proofs and experimental results. The paper clearly shows that the fundamental limitations of Best-of-N alignment through explicit regret analysis. In addition, it also show the robustness and optimal regret guarantees of InferenceTimePessimism.

方法与评估标准

The methods and evaluation criteria selected are appropriate and justified. The use of standard benchmark datasets such as GSM8K, MMLU, and MATH is suitable to validate alignment effectiveness and reward model quality.

理论论述

The correctness of the theoretical claims was found to be solid. The proofs of lower bounds establishing the necessity of coverage and the limitations of the Best-of-N approach are rigorous and correct.

实验设计与分析

The experimental designs were found to be sound. Experiments effectively demonstrate the robustness of InferenceTimePessimism in mitigating reward hacking and improving performance across multiple reward models and tasks.

补充材料

I reviewed the supplementary material for theoretical proofs.

与现有文献的关系

Not sure about the relation To broader scientific literature.

遗漏的重要参考文献

Not sure about the essential references not discussed.

其他优缺点

Novel theoretical insights significantly advancing understanding of inference-time alignment.
Clearly articulated and robust theoretical framework that provides meaningful guidance for practical algorithm design.
Empirical validation effectively demonstrates theoretical predictions, enhancing practical relevance.

其他意见或建议

N/A

审稿意见

评分: 42025-03-11

This paper examines inference-time alignment, where additional computation at generation time is used to improve language model outputs. Specifically, the authors focus on the widely used best-of- $n$ approach, which generates multiple responses and selects the one with the highest reward according to a (possibly imperfect) reward model. The key contribution is a theoretical framework that explains when and why best-of- $n$ works, and more importantly, when it fails. The authors show that while best-of- $n$ can be effective with proper tuning, it inevitably suffers from "reward hacking" when scaled too aggressively. This happens because imperfections in the reward model become amplified when $n$ is large. To address this, they introduce InferenceTimePessimism, an algorithm that deliberately uses inference-time computation to quantify and account for uncertainty in the reward model. Their theoretical analysis proves this approach is optimal in terms of regret and maintains performance even with increased computation. The authors validate their theoretical findings with experiments on benchmarks using various language and reward models, demonstrating that their algorithm can mitigate reward overoptimization.

给作者的问题

Regarding the weakness, what is the bound for best-of- $n$ when $\varepsilon_{RM} (x) = 0$ ? What is the dependency on $N$ for InferenceTimePessimism?

论据与证据

Yes

方法与评估标准

Yes

理论论述

实验设计与分析

补充材料

与现有文献的关系

TBA

遗漏的重要参考文献

其他优缺点

Strengths

Novel Theoretical Framework: The paper is the first to build the theoretical framework of best-of- $n$ with ideas from offline RL, with the core notion of coverage.
Theoretical Guarantees: The authors first give comprehensive results (both upper and lower bounds) of best-of- $n$ . The results can be stronger when a uniform converage is guaranteed. Then they prove their algorithm, InferenceTimePessimism, is regret-optimal within their framework, which is a significant theoretical contribution.
Practical Algorithm: The authors give the practical implementation for InferenceTimePessimism and perform extensive experimental validation on multiple tasks, reward models, and language models.

Weaknesses

Lacking some cases in theory: For Theorem 3.1, the authors didn't discuss the case where $\varepsilon_{RM} (x) = 0$ . If we directly apply the results, then the regret is unbounded, which seems counter-intuitive. For Theorem 4.1, the authors didn't give a dependency on $N$ , which makes it hard to compare with Theorem 3.1.

其他意见或建议

审稿意见

评分: 42025-03-13

The paper first theoretically shows the overoptimization problem is inevitable with the well-known best-of-N algorithm, especially when N increases. Then they propose Inference-Time Pessimism Algorithm, and show that the proposed algorithm resolves the overoptimization problem and also achieves optimal regret rate in terms of the reward approximation error. The paper also provides experiments to validate their theoretical findings.

给作者的问题

See Claims and Evidences.

论据与证据

Claims with evidences

On the Best-of-N (BoN) algorithm, the paper shows that (i) it causes overoptimization in the worst cases when N increases (Theorem 3.2), and (ii) the regret achieved by BoN is also suboptimal in terms of $\epsilon_{RM}$ , the approximation error of an estimated reward. (Theorem 3.1, 3.2)
To resolve these issues, the paper proposes Inference-Time Pessimism Algorithm (Algorithm 1), which is a sampling procedure from $\chi^2$ -regularized reward maximizing distribution, by rejection sampling with N samples from the reference model. The proposed algorithm does not cause overoptimization by its nature, and also achieves optimal regret bound in terms of $\epsilon_{RM}$ . (Theorem 4.1, 4.2)
Experimental results:
- Figure 1 validates that the proposed algorithm with tuned hyperparameter $\beta$ , the strength of $\chi^2$ regularization, successfully avoids the overoptimization issue caused in BoN when N increases.
- Figure 2 investigates the behavior of the proposed algorithm with varying $\beta$ compared to the BoN algorithm, with fixed $N=2^{13}$ . However, this is an extreme setting and also unfair for BoN.

Overall, the claims are theoretically well-supported, and experiments validate the benefits of the proposed algorithms as predicted from their theories. However, I still have some concerns especially about the experimental evidences:

The paper claims that the proposed algorithm is superior to BoN because (i) it avoids overoptimization and (ii) it achieves the improved regret rate. However, experimental results only verify the first benefit (i), and it is unclear how the second benefit (ii) appears in the real-world experiments.
The performance of the proposed algorithm seems to depend on the choice of the hyperparameter of regularization strength $\beta$ , but the behavior with changing $\beta$ is only shown with the extreme setting of $N=2^{13}$ .

方法与评估标准

The proposed method makes sense and is well-motivated. The experimental settings follow the standard ones.

理论论述

I read some proofs in Appendix to understand the theoretical results, but did not check all of them.

实验设计与分析

The experimental designs and analyses seem sound.

补充材料

I read some proofs in Appendix to understand the theoretical results, but did not check all of them.

与现有文献的关系

The proposed algorithm successfully resolves the overoptimization problem caused with the BoN algorithm, which is a widely used method for inference-time alignment. In addition to analyses of the proposed algorithm, the theoretical results on BoN themselves are also novel and insightful.

遗漏的重要参考文献

Yang et al. [1] also investigates the theoretical properties of the BoN algorithm in relation to KL-regularized reward-maximizing distribution, but not cited in this paper.

[1] Yang et al., "Asymptotics of Language Model Alignment" (ISIT'24)

其他优缺点

See Claims and Evidences.

其他意见或建议

N/A

审稿意见

评分: 32025-03-16

The paper analyzes the Best-of-N (BoN) algorithm for selecting among language model generations and introduces InferenceTimePessimism, a new algorithm that mitigates reward hacking. The authors formalize inference-time alignment as improving a pre-trained policy’s responses using an imperfect reward model. They show that BoN can achieve optimal performance under strict coverage but suffers from reward hacking when N is large. InferenceTimePessimism is proven to be optimal and scaling-monotonic, with empirical validation across tasks like GSM8K, MMLU, and MATH.

给作者的问题

Please see above

论据与证据

The claims are well-supported by theoretical proofs and empirical results. The authors demonstrate BoN's limitations and prove InferenceTimePessimism's optimality and robustness through experiments on multiple tasks and models.

方法与评估标准

The methods are appropriate, focusing on inference-time alignment and evaluated using standard benchmarks (e.g., GSM8K, MMLU). The criteria, including accuracy and estimated reward, effectively measure performance.

理论论述

The theoretical claims are supported by rigorous proofs. The authors prove InferenceTimePessimism achieves optimal regret and is scaling-monotonic, with detailed proofs in the supplementary material.

实验设计与分析

The experiments are well-designed, covering multiple tasks and models. The results show InferenceTimePessimism avoids reward hacking and outperforms BoN in many cases.

补充材料

The supplementary material provides additional proofs and experiments, supporting the main paper effectively.

与现有文献的关系

The paper connects well to prior work on reward overoptimization and offline RL, extending ideas like pessimism to inference-time alignment.

遗漏的重要参考文献

The paper could reference more recent work on preference-based learning and scaling laws for language models to provide additional context.

其他优缺点

Strengths:

Addresses a timely problem with theoretical insights and practical algorithms.
InferenceTimePessimism is a novel contribution with rigorous proofs and empirical validation.
The proposed methods work reasonably well.

Weaknesses:

Limited guidance on tuning the regularization parameter $\beta$
Experiments focus on mathematical tasks; more diverse tasks (e.g., dialogue) would strengthen generalizability.

Q1. How should practitioners choose $\beta$ in InferenceTimePessimism?

Q2. Have you considered evaluating on more diverse tasks like open-ended dialogue?

Q3. What are the computational costs of InferenceTimePessimism compared to BoN?

其他意见或建议

Please see above

最终决定Accept (poster)

2025-05-01

This paper provides a theoretical analysis of Best-of-N (BoN) sampling for inference-time alignment, formalizing the problem and highlighting BoN's key limitations regarding reward hacking and suboptimality. The introduction and analysis of their pessimistic algorithm is a good contribution, and includes regret guarantees and scaling-monotonicity, which are mostly supported by empirical results. It is still unclear how to optimally tune the hyperparameter of the proposed approach without an oracle. Also, an analysis of the computational overhead compared to standard BoN is missing. While the work is self-contained and focuses correctly on inference-time mechanisms, a direct comparison to inference-aware training methods (like those in the IAFT paper) may add additional context.