Efficient Best-of-N policy evaluation for inference-time alignment
Abstract
Best-of-N (BoN) is a common inference-time alignment method that selects the highest-scoring response among N samples from a reference model. Evaluating BoN policies from logged data is challenging under sample-only access because standard off-policy estimators require density ratios that depend on unavailable response likelihoods. In this paper, we propose a sample-only framework for evaluating and selecting BoN policies without access to these likelihoods. We show that the order-statistic structure of BoN allows the required density ratios to be expressed through score-rank probabilities that are estimable from samples alone. We then develop a doubly robust estimator of the BoN policy value (BoN-DR) that efficiently reuses a shared auxiliary sample pool across candidate budgets. We establish valid asymptotic inference even under reward estimator misspecification and prove the efficiency of our BoN-DR estimator. Since larger budgets can amplify errors in the score function and lead to reward overoptimization, we derive two selection rules: (i) maximizing the estimated policy value and (ii) maximizing a lower confidence bound on the improvement over the reference policy, which accounts for estimation uncertainty and provides a no-harm guarantee. Across synthetic experiments and GSM8K with multiple reference and reward models, our framework accurately estimates BoN policy values and selects effective sampling budgets.
Related
- ExpBoN: Exponential-Noise Best-of-n for Efficient Test-Time LLM Alignment
- Tight Sample Complexity Bounds for Entropic Best Policy Identification
- Honesty is the Best Policy ... or is it? Demand Management for Probabilistic Service Options
- PathGuide: Dynamic Classifier-Free Guidance via On-Policy Transport Alignment
- Steepest Guidance: A Practical and Principled Approach to Inference-Time Alignment of Flow and Diffusion-based Models
BibTeX
@misc{schweisthal2026efficient,
title = {{Efficient Best-of-N policy evaluation for inference-time alignment}},
author = {Jonas Schweisthal and Yuxin Wang and Athiya Deviyani and Stefan Feuerriegel and Dennis Frauen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.09250},
eprint = {2610.09250},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.09250},
}
RIS
TY - UNPB
TI - Efficient Best-of-N policy evaluation for inference-time alignment
AU - Jonas Schweisthal
AU - Yuxin Wang
AU - Athiya Deviyani
AU - Stefan Feuerriegel
AU - Dennis Frauen
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.09250
UR - https://arxiv.org/abs/2610.09250
AB - Best-of-N (BoN) is a common inference-time alignment method that selects the highest-scoring response among N samples from a reference model. Evaluating BoN policies from logged data is challenging under sample-only access because standard off-policy estimators require density ratios that depend on unavailable response likelihoods. In this paper, we propose a sample-only framework for evaluating and selecting BoN policies without access to these likelihoods. We show that the order-statistic structure of BoN allows the required density ratios to be expressed through score-rank probabilities that are estimable from samples alone. We then develop a doubly robust estimator of the BoN policy value (BoN-DR) that efficiently reuses a shared auxiliary sample pool across candidate budgets. We establish valid asymptotic inference even under reward estimator misspecification and prove the efficiency of our BoN-DR estimator. Since larger budgets can amplify errors in the score function and lead to reward overoptimization, we derive two selection rules: (i) maximizing the estimated policy value and (ii) maximizing a lower confidence bound on the improvement over the reference policy, which accounts for estimation uncertainty and provides a no-harm guarantee. Across synthetic experiments and GSM8K with multiple reference and reward models, our framework accurately estimates BoN policy values and selects effective sampling budgets.
ER -