Efficient evaluation of best sample selection methods without likelihood access
Efficient Best-of-N policy evaluation for inference-time alignment
Machine LearningArtificial Intelligence
Summary
Choosing the best response from many samples in AI models is useful but hard to evaluate without knowing how likely each response is. The authors developed a method to estimate how good these best-of-N choices are using only the scores assigned to samples, without needing detailed probabilities. Their approach also helps pick how many samples to check to avoid mistakes from picking too many. They tested their method on math problem data and showed it works well to estimate and select good sample sizes.
What this means in practice
- •For machine learning engineers: Evaluate and select optimal sample counts for inference-time response selection without needing response likelihoods.
- •For ai product managers: Ensure safer model alignment by choosing sampling budgets that avoid reward overfitting during inference.
Authors
Jonas Schweisthal, Yuxin Wang, Athiya Deviyani, Stefan Feuerriegel, Dennis Frauen
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.