📊 statistics

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

This paper analyzes reward learning from Best-of- $N$ preference data by deriving closed-form targets for independent variants, characterizing the trade-off between margin and connectivity that dictates optimal $N$ selection, and proposing design principles to balance generation costs against label efficiency.

Original authors: Rattana Pukdee, Maria-Florina Balcan, Pradeep Ravikumar

Published 2026-06-01

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Rattana Pukdee, Maria-Florina Balcan, Pradeep Ravikumar

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a teacher trying to teach a student (an AI) how to write good stories. You don't have time to grade every single story the student writes with a perfect score. Instead, you use a trick: you ask the student to write N different versions of a story, pick the best one, and then compare it to a "rejected" one.

This paper, titled "Reward Learning from Best-of-N Preference Data," asks a simple but deep question: How does the number of drafts (N) you ask for, and the quality of the student's initial writing ability, change what the teacher actually learns?

Here is the breakdown of their findings using everyday analogies.

1. The Setup: The "Best-of-N" Game

In the world of AI, we often create training data by asking a model to generate several answers (let's say 4, 8, or 16) and then picking the winner.

The Winner: The best answer among the group.
The Loser: Either a random answer from the group or the absolute worst one.
The Goal: Teach a "Reward Model" (a judge) to recognize what makes an answer good, so it can help train the AI later.

The common intuition is: "If I ask for more drafts (a bigger N), the winner will be better, so the data is better."
The Paper's Twist: This isn't the whole story. It's not just about how good the winner is; it's about which comparisons the teacher gets to see.

2. The Two Big Trade-offs: The "Margin" vs. The "Map"

The authors discovered that increasing N (asking for more drafts) pulls two levers in opposite directions. Think of it like trying to learn a map of a city.

Lever A: The "Margin" (Making the Difference Obvious)

What it is: The "margin" is how clearly you can tell the difference between a good answer and a bad one.
The Effect of Big N: When you ask for 100 drafts, the winner is likely to be amazing, and the loser is likely to be terrible. The gap between them is huge. It's like comparing a Ferrari to a bicycle. The difference is obvious, making it very easy for the teacher to spot the winner.
The Benefit: This makes the learning signal very strong and clear.

Lever B: The "Connectivity" (Seeing the Whole Picture)

What it is: "Connectivity" is how well the teacher sees the middle ground. Does the teacher see how a "pretty good" answer compares to a "pretty bad" one?
The Effect of Big N: If you always pick the Ferrari and the bicycle, you never see the comparison between a sedan and a motorcycle. You lose the "middle" of the map. The teacher only sees the extremes.
The Cost: As N gets bigger, the teacher stops seeing the "intermediate" steps. The map becomes sparse, with only the very best and very worst points connected.

The Trade-off:

Small N (e.g., 2 drafts): You see a lot of different comparisons (good connectivity), but the differences between the winner and loser might be small and hard to judge (small margin).
Large N (e.g., 16 drafts): The differences are huge and easy to judge (large margin), but you only see the extremes, missing the middle ground (low connectivity).

3. The Golden Rules for Design

Based on this tug-of-war, the authors give two practical rules for how to run this process:

Rule #1: Choose N based on your "Bottleneck"

If your problem is "Not enough human labels" (Labels are scarce/expensive):
- Analogy: You have very few teachers available to grade the papers.
- Strategy: Use a Large N. Since you can't afford to grade many pairs, make each pair count. Ask for 16 drafts so the difference between the winner and loser is so obvious that the teacher learns a lot from just one comparison.
If your problem is "Not enough computer power to generate drafts" (Generation is scarce/expensive):
- Analogy: You have thousands of teachers, but the student is slow at writing.
- Strategy: Use a Small N. Don't waste time generating 16 drafts for every question. Generate 2 drafts, compare them, and do that for many more questions. You get a better "map" of the city by seeing more streets, even if the differences between cars are smaller.

Rule #2: Shape the "Base Distribution" (The Student's Starting Point)

The "Base Distribution" is the pool of drafts the student generates before you pick the winner. The paper says you can "tune" this pool to help the teacher learn specific things.

The "Between-Mass" Principle: The teacher learns best when there are many drafts in between the two things you want to compare.
Example 1 (Safety): If you want to teach the AI to distinguish between "Harmful" and "Safe" answers, don't just generate "Safe" and "Harmful" drafts. Generate a lot of "Mediocre" or "Flawed but not dangerous" drafts in the middle. This creates a clear path for the teacher to learn where the line between safe and unsafe actually is.
Example 2 (Reasoning): If you want to teach math, don't just generate "Perfect" and "Nonsense" answers. Generate "Almost right" answers. The teacher needs to see the difference between "Correct" and "Almost Correct" to learn the nuance.

4. What the Experiments Showed

The authors tested these ideas on both fake data and real-world data (like math problems and safety questions).

The Result: They confirmed that when they had very few training examples, using a large N worked best. When they had tons of data, using a small N (and generating more pairs) worked better.
The Result on Tuning: When they adjusted the "Base Distribution" to put more "middle-quality" answers in the mix for specific tasks (like safety or math), the AI learned those specific skills significantly better.

Summary

This paper tells us that Best-of-N isn't just a magic button for better AI. It's a tool with a specific trade-off:

Big N gives you clear, obvious differences but a narrow view.
Small N gives you a broad view but subtler differences.

To get the best AI, you need to match the size of your "N" to your resources (do you have more teachers or more computers?) and carefully design the pool of drafts to ensure the AI sees the specific comparisons that matter most for the job you want it to do.

Technical Summary: Reward Learning from Best-of-N Preference Data

Problem Statement

Best-of-N (BoN) sampling is a widely used mechanism for constructing pairwise preference data in modern AI systems, particularly for training reward models and aligning large language models (LLMs). In this process, $N$ candidate responses are sampled from a base distribution, and an oracle (human or model-based) selects the best response as the "chosen" example. The "rejected" example is typically selected either uniformly from the remaining candidates (Best-vs-Random) or as the worst candidate (Best-vs-Worst).

Despite its prevalence, the theoretical properties of reward learning from such data remain unclear. Specifically, it is not well understood:

What specific reward function is induced by the resulting dataset under the standard Bradley-Terry (BT) objective?
How should the candidate-set size $N$ and the base distribution be chosen to optimize learning efficiency?

Common intuition suggests that larger $N$ yields better data because the chosen response is of higher absolute quality. However, this paper argues that this intuition is incomplete, as the utility of the data depends not only on the quality of the chosen response but also on the specific comparisons the dataset makes available.

Methodology

The authors analyze reward learning through the lens of the Conditional Preference Distribution (CPRD), building upon a recent distribution-agnostic framework (Pukdee et al., 2026). This framework characterizes when preference data admits a Bradley-Terry representation and identifies that finite-sample learning is governed by two key quantities: margin (the difficulty of distinguishing pairs) and connectivity (the coverage of the comparison space).

The paper instantiates this framework for Best-of-N data by:

Deriving Closed-Form Targets: Analyzing "Independent" variants (Best-vs-Independent and Best-vs-Worst-Independent) where the rejected sample is drawn independently of the chosen sample. In these settings, the authors derive explicit closed-form expressions for the population minimizers of the BT loss.
Analyzing Practical Variants: Extending the analysis to the practical Best-vs-Random and Best-vs-Worst settings. Here, the chosen and rejected responses are coupled (drawn from the same set of $N$ candidates), meaning exact BT representability generally fails. The authors show that as $N$ grows, the minimizers for these practical settings converge to the targets of the independent variants.
Characterizing Trade-offs: Investigating how the parameter $N$ simultaneously affects the margin and the connectivity of the induced preference distribution.
Experimental Validation: Validating theoretical predictions on both synthetic data and real-world datasets (UltraFeedback, PKU-SafeRLHF, GSM8K) by varying $N$ and reshaping the base distribution.

Key Contributions

1. Characterization of Reward Targets

Independent Variants: For Best-vs-Independent, the induced reward target $r^*_{BI}$ is shown to be the log-ratio of the Best-of-N distribution to the base distribution: $r^*_{BI}(x, y) = \log \frac{P_{BoN}(y|x)}{P_{base}(y|x)} + c(x)$ . Crucially, this target preserves the ranking of the underlying ground-truth reward $r^*$ .
Practical Variants: For Best-vs-Random and Best-vs-Worst, the population minimizers do not admit a simple closed form due to the coupling of samples. However, the authors prove that as $N$ increases, the minimizers for these settings approach the targets of the independent variants in margin semi-norm. Specifically, the distance decays as $O(1/N)$ for Best-vs-Random and exponentially for Best-vs-Worst.

2. The Margin-Connectivity Trade-off

The paper identifies a fundamental trade-off controlled by $N$ :

Margin: Increasing $N$ amplifies pairwise margins. The margin between two outcomes $y$ and $y'$ grows linearly with $N$ , scaled by the "between mass" (the probability mass of the base distribution lying between the reward scores of $y$ and $y'$ ). Larger margins make individual comparisons more informative and robust to estimation error.
Connectivity: Increasing $N$ reduces connectivity. As $N$ grows, BoN sampling concentrates on high-reward outcomes, while Worst-of-N concentrates on low-reward outcomes. This narrows the range of observed comparisons, leaving intermediate pairs underrepresented. The connectivity degree decays exponentially with $N$ .

3. Design Principles

Based on the trade-off, the authors propose two actionable design principles:

Resource Bottleneck Principle: The optimal $N$ $N$ depends on the scarcity of preference labels.
- Label-Limited Regime: When human annotation is the bottleneck (small sample size $n$ ), larger $N$ is preferable. The increased margin helps overcome the high estimation error caused by limited data, even if connectivity is reduced.
- Generation-Limited Regime: When labels are cheap or automated (large $n$ ), smaller $N$ is preferable. The connectivity loss from large $N$ outweighs the margin benefit when data is abundant; it is more efficient to use the saved compute budget to collect more triplets with smaller $N$ .
Between-Mass Principle: The base distribution can be shaped to selectively amplify margins. The induced margin between two responses grows with the amount of base-distribution mass placed between them in the reward order. Practitioners should shape the base distribution to place mass between the specific response pairs that matter most for the target evaluation distribution (e.g., between harmful and acceptable outputs for safety tasks).

Results

Synthetic Data: Experiments confirm the predicted trade-off. For small sample sizes ( $n$ ), larger $N$ yields higher test accuracy. As $n$ increases, the optimal $N$ decreases, and for sufficiently large $n$ , smaller $N$ (e.g., $N=2$ ) outperforms larger $N$ (e.g., $N=8$ ) due to better connectivity.
Real-World Data: On UltraFeedback, the same trend holds: larger $N$ benefits small-data regimes, while smaller $N$ is competitive or better in large-data regimes.
Base Distribution Reshaping: Experiments on safety (PKU-SafeRLHF), reasoning (GSM8K), and general (UltraFeedback) tasks demonstrate that reshaping the base distribution to increase "between mass" for task-critical comparisons improves test accuracy. For example, in safety tasks, upsampling "mediocre" (flawed but not dangerous) responses increased the margin between harmful and acceptable outputs, improving performance.

Significance

The paper provides a learning-theoretic foundation for reward learning from Best-of-N preference data. It moves beyond the heuristic view that "more candidates are always better" by rigorously characterizing the induced reward targets and the sample complexity trade-offs.

The significance lies in:

Clarifying the Signal: It identifies exactly what signal reward learning recovers from BoN data, showing that while the ranking is preserved, the specific reward function depends on $N$ and the base distribution.
Guiding Data Design: It offers concrete, principled guidelines for practitioners on how to choose $N$ based on resource constraints and how to engineer the base distribution to maximize learning efficiency for specific downstream tasks.
Bridging Theory and Practice: It connects abstract concepts of margin and connectivity to the practical mechanics of Best-of-N sampling, explaining why performance can degrade with very large $N$ in certain regimes and how to mitigate it.

The authors conclude that preference-data construction is not merely a collection detail but a critical design lever that shapes both what reward is learned and how efficiently it can be learned.