Reward Learning from Best-of- N N Preference Data: Targets, Tradeoffs, and Design Principles

Rattana Pukdee [email protected], Maria-Florina Balcan [email protected], Pradeep Ravikumar [email protected] · 2026

Read Reward Learning from Best-of- N N Preference Data: Targets, Tradeoffs, and Design Principles by Rattana Pukdee [email protected], Maria-Florina Balcan [email protected], Pradeep Ravikumar [email protected] (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-30619.txt.

Introduction

Pukdee, Balcan, and Ravikumar analyze Best-of-N preference data: N candidates drawn, the best paired with a rejected response. For independent-reference variants, reward targets follow from N and the base distribution, preserving reward ranking. For best-versus-random and best-versus-worst variants, shared candidate sets break Bradley-Terry representability, though minimizers approach the targets as N grows. Design rules: larger N widens margins but cuts connectivity, so use larger N when labels bottleneck, smaller N when generation bottlenecks, and weight the base distribution toward test-time comparisons.

Catalog record

CREATORRattana Pukdee [email protected], Maria-Florina Balcan [email protected], Pradeep Ravikumar [email protected]
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE113652
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.30619

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Reward Learning from Best-of- N N Preference Data: Targets, Tradeoffs, and Design Principles Rattana Pukdee [email protected], Maria-Florina Balcan [email protected], Pradeep Ravikumar [email protected] Abstract Best-of- N N sampling is widely used to construct pairwise preference data: N N candidates are drawn from a base distribution, and the best is paired with a rejected response. Despite its widespread use, what Bradley–Terry (BT) reward learning extracts from such data, and how to choose N N and the base distribution, remain unclear. We specialize a recent analysis of preference data via its induced conditional distribution to Best-of- N N . For independent-reference variants, we derive closed-form reward targets as explicit functions of N N and the base distribution, and show that they preserve the latent reward ranking. For the practical Best-vs-Random and Best-vs-Worst variants, chosen and rejected responses are coupled through the same candidate set, so exact BT representability generally fails; nevertheless, bounded-class minimizers approach the reference targets as N N grows. Although margin and connectivity are known to govern sample efficiency in pairwise preference learning, Best-of- N N couples them through N N in opposing directions: larger N N widens pairwise margins but reduces connectivity. This trade-off yields two design principles: use larger N N when preference labels are the bottleneck, smaller N N when generation is the bottleneck; and shape the base distribution to place mass between the responses whose comparison matters most at test time. Experiments on synthetic and real preference data support the predicted dependence on sample size and base-distribution shape. 1 1 1 Code available at: https://github.com/rattaoup/bon-preference 1 Introduction Pairwise preference data is a general and increasingly important supervision signal in machine learning. It has been extensively studied in the literature on learning to rank ( 7 ; 44 ) and learning preference ( 13 ; 35 ) , learning combinatorial functions ( 4 ) and more recently has become central to modern AI systems, especially in reward learning and post-training of large language models ( 8 ; 31 ) . This form of supervision is widely used because relative judgements are often easier to obtain, from both human annotators and increasingly AI evaluators ( 49 ) , than calibrated scalar scores. In modern AI systems, pairwise preference data is often used to train reward models, typically with a Bradley-Terry objective, and these reward models may then be used to further optimize a language model through reinforcement learning ( 50 ; 40 ; 31 ) . Preference data is also used more directly in fine-tuning the model as well ( 36 ; 28 ) . A common approach to construct the preference data is through Best-of- N sampling. For a given context, N responses are sampled from a base distribution, and an oracle identifies the best response as the chosen one. The rejected response is then selected either uniformly from the remaining N-1 responses (Best-vs-Random) or as the worst response (Best-vs-Worst). The special case N=2 recovers the standard pairwise-comparison setting ( 8 ) . The common intuition is that larger N improves this data, since the chosen response is better in absolute terms. We show this intuition is incomplete: what matters is not only the quality of the chosen response, but which comparisons the dataset makes available. We study reward learning as a clean lens on the role of data with two fundamental questions. 1. When preference data is generated through Best-of-N sampling, what reward function is induced by the resulting dataset under Bradley-Terry objective? 2. How should the candidate-set size N and the base distribution be chosen ? Our analysis builds on a recent distribution-agnostic framework ( 34 ) that analyzes preference data through the conditional preference distribution (CPRD), characterizing when it is Bradley-Terry representable and showing that finite-sample learning is governed by margin and comparison connectivity. That framework leaves the induced reward targets, margins, and connectivity abstract, since they depend on the data-generation mechanism. We instantiate it for Best-of- N preference data, where the order-statistic structure makes these quantities concrete and reveals how they scale with N . Our contributions are summarized as follows: Contributions. 1. Targets: We study a clean reference setting in which the rejected response is sampled independently. In this setting, we characterize the reward targets induced by Best-of- N preference data in closed form and show that they preserve the ranking of an underlying ground-truth reward. This identifies what signal reward learning is recovering from the data. For the practical Best-vs-Random and Best-vs-Worst settings, we show that the corresponding population minimizers do not admit the same clean characterization, but approach these reference targets as N grows. 2. Tradeoffs: We show that N controls a fundamental tradeoff between margin and comparison connectivity. Increasing N pushes chosen responses toward the top of the reward distribution, which amplifies pairwise margins and makes individual comparisons more informative. But this same concentration narrows the range of responses being compared, reducing comparison connectivity and leaving intermediate comparisons underrepresented. These two effects pull in opposite directions and govern sample efficiency. 3. Design principles: We derive two actionable guidelines. The candidate-set size N should be chosen based on the resource bottleneck: larger N is more helpful when preference labels are scarce, whereas smaller N is often preferable when preference labels are cheap and data is abundant. Beyond choosing N , the base distribution itself is also a design lever through what we call the between-mass principle: the induced margin between two responses grows with the amount of base-distribution mass placed between them in reward order. Shaping the base distribution to put mass between the response pairs that matter under the target evaluation distribution selectively amplifies those margins. We validate these predictions on both synthetic and real preference data. Taken together, our results provide a learning-theoretic foundation for reward learning from Best-of- N preference data, while yielding concrete principles for data design in practice. 2 Related work Best-of- N Sampling for Inference and Training. Best-of- N sampling (BoN) is an inference-time method with strong empirical performance ( 40 ; 10 ; 30 ; 6 ) . The idea is to sample N responses from a policy and select the one with the highest reward. Despite its simplicity, BoN is a strong baseline for inference-time scaling ( 39 ) . Various works have studied the theoretical properties of the induced BoN policy ( 19 ) , including its distance from the reference policy and its win rate ( 5 ; 45 ) , and the soft BoN variants ( 43 ; 2 ) . These results suggest that win rate increases with N . However, larger N does not always improve performance in practice; when N is too large, reward hacking can degrade output quality ( 14 ; 18 ) . Given the effectiveness of BoN but its N -fold inference cost, several works aim to train a policy that matches the BoN distribution while requiring only a single sample at inference time. This can be done offline with a fixed BoN dataset ( 42 ; 12 ; 1 ) or iteratively ( 38 ; 47 ; 17 ) . 16 provide theoretical analysis for this training time setting, showing that the BoN distribution is optimal in terms of win rate against the

Read the complete text