Abstract. Best-of-N sampling is the minimal Test-Time Compute strategy: generate NNN independent candidate outputs and return the one judged best by a scoring rule. Its power comes from optionality, not from deeper reasoning by itself: it works when the base model has enough coverage to sometimes produce a good answer and when the scorer can reliably identify that answer. This article covers the algorithm, scoring rules, empirical evidence, cost geometry, links to Self-Consistency and RLHF, and the practitioner trade-off between BoN, Chain-of-Thought Prompting, Tree of Thoughts, and Monte Carlo Tree Search.
Coverage note: verified through May 11, 2026.
Best-of-N Sampling: The Simplest Test-Time Compute Strategy
1. Definition
Best-of-N Sampling is the simplest form of inference-time search. Given an input xxx, a generator pθ(y∣x)p_\theta(y \mid x)pθ(y∣x), a sample count NNN, and a scoring function s(x,y)s(x,y)s(x,y), the algorithm is:
yi∼pθ(⋅∣x)for i=1,…,Ny_i \sim p_\theta(\cdot \mid x) \quad \text{for } i=1,\dots,Nyi∼pθ(⋅∣x)for i=1,…,N y^=argmaxyis(x,yi)\hat{y} = \arg\max_{y_i} s(x,y_i)y^=argyimaxs(x,yi) In code:
def best_of_n(prompt, generator, scorer, n, sampling_config): candidates = [ generator(prompt, sampling_config) for _ in range(n) ] scores = [ scorer(prompt, candidate) for candidate in candidates ] return candidates[max(range(n), key=lambda i: scores[i])]
The key point is that BoN does not change the model weights. It spends more inference compute to expose more of the model’s conditional distribution, then uses a Verifier Model, Reward Model, Deterministic Checker, or other rule to select. The canonical LLM-era verifier formulation appears in Cobbe et al.’s GSM8K work: sample a fixed number of candidate math solutions and choose the one ranked highest by a trained verifier. ar5iv
A useful naming note: in alignment papers, BoN is often called rejection sampling. This is not always classical rejection sampling in the statistical sense; it usually means “sample several completions and keep the one with highest reward.” WebGPT makes this explicit: it samples 4, 16, or 64 answers and selects the answer ranked highest by a reward model, using more inference-time compute instead of additional training. ar5iv
2. Why BoN works: optionality plus selection
BoN converts stochastic generation into an order statistic. A single sample gives one draw from the model’s distribution. NNN samples give a small portfolio. If even one candidate is correct and the scorer can find it, the system succeeds.
For tasks with a deterministic checker, the upper-bound intuition is simple. Suppose each sample independently has probability ppp of being correct and the checker perfectly accepts correct answers. Then the probability that at least one of NNN candidates is correct is:
P(at least one correct)=1−(1−p)NP(\text{at least one correct}) = 1 - (1-p)^NP(at least one correct)=1−(1−p)N This is the usual pass@N intuition. It explains why repeated sampling helps most when ppp is nonzero but not already high. If p=0.01p=0.01p=0.01, then 100100100 samples give about a 63% chance of at least one correct candidate. If p=0.50p=0.50p=0.50, a few samples already saturate. If p=0p=0p=0, BoN cannot help.
That formula is an oracle upper bound, not a guarantee. Real BoN has three separate requirements:
| Requirement | Meaning | Failure mode |
|---|---|---|
| Coverage | The generator must sometimes produce a good answer. | No number of samples helps if the model cannot generate a valid solution. |
| Diversity | Samples must explore meaningfully different candidates. | Near-duplicate samples waste compute. |
| Selection | The scorer must rank good candidates above bad ones. | A noisy or hackable scorer eventually selects pathological outputs. |
Recent inference-scaling work makes this distinction precise. Brown et al.’s Large Language Monkeys study reports that coverage across tasks and models can scale over many sample counts, and that automatic verifiers in coding and formal-proof settings can translate that coverage into performance; without automatic verifiers, majority voting and reward models plateau beyond several hundred samples. OpenReview
3. The scoring rule is the real objective
The generator supplies candidates; the scorer defines what “best” means. In practice, most BoN failures are scorer failures.
| Scoring option | Typical use | Strength | Main risk |
|---|---|---|---|
| Deterministic checker | Unit tests, compilers, theorem provers, JSON schema validators, exact-answer match | High precision when the spec is complete | Incomplete tests, brittle parsing, or syntax-only validation |
| Outcome verifier | Math final-answer verifier, code correctness classifier, task-specific classifier | Can score semantic correctness beyond simple parsing | Learns dataset artifacts; false positives increase with large NNN |
| Process verifier / PRM | Step-level math reasoning, beam search, trajectory pruning | Can guide partial reasoning and reject bad intermediate steps | Expensive; step scores may not align with final correctness |
| Reward model | Human preference, helpfulness, harmlessness, style, summarization | Works for open-ended tasks where no exact checker exists | Reward hacking and Goodhart pressure |
| Log-probability / likelihood | Reranking candidates by model confidence | Cheap; no external model | Favors common or bland outputs; confidence is not correctness |
| Majority vote / self-consistency | Math and discrete-answer reasoning | No trained verifier needed | Selects the most common answer, not necessarily the correct one |
| Hybrid scorer | Checker first, reward/verifier second, tie-break by length or log-prob | Often best in production | More engineering complexity |
3.1 Deterministic checkers
Deterministic checkers are the cleanest case. For code, a candidate can be compiled and run against tests. For formal proofs, a proof assistant can check validity. For structured outputs, a JSON schema validator can reject malformed outputs. This turns BoN into a search over executable artifacts.
The Codex paper introduced HumanEval as a functional-correctness benchmark and found that repeated sampling was effective: the reported model solved 28.8% of HumanEval problems with one sample and 70.2% with 100 samples. arXiv AlphaCode extended the same philosophy to competitive programming: generate a very large candidate set, filter by example tests, cluster by program behavior, and submit a small candidate set. ar5iv
The caveat is that a checker is only as complete as its specification. Unit tests are not proofs. A solution can pass visible tests and fail hidden cases; this is why code-generation evaluation increasingly distinguishes “passes benchmark tests” from “is actually correct.” EvalPlus-style work has shown that augmenting HumanEval tests can catch previously accepted wrong code and reduce reported pass rates. arXiv
For structured-output tasks, BoN is often used as retry-with-validation: generate multiple JSON candidates, reject invalid ones, and choose the best valid object. But if the only concern is schema adherence, constrained decoding or native structured-output APIs are usually better than BoN because they remove invalid syntax from the sample space. OpenAI’s Structured Outputs announcement frames the feature exactly this way: model outputs are constrained to match developer-supplied JSON Schemas, whereas older JSON mode improved validity without guaranteeing schema conformance. OpenAI
3.2 Verifier models
Verifier-guided BoN is the classic math-reasoning version. Cobbe et al. trained verifiers to judge whether GSM8K solutions were correct, then selected the highest-ranked candidate among multiple generated solutions. Their paper also argued that verifiers gave a performance boost comparable to a large model-size increase and scaled better with additional verifier data than finetuning alone. ar5iv
The later Process Reward Models literature moved from final-answer scoring to step-level scoring. Lightman et al.’s Let’s Verify Step by Step trained process-supervised reward models with step-level human feedback and reported 78% accuracy on a representative subset of the MATH test set; Math-Shepherd then explored automatically constructed process supervision for step-level verification and reinforcement. OpenReview
Verifier-guided BoN is strongest when the verifier is easier to learn than the generator. That is often true in math: checking an algebraic derivation or final answer is easier than discovering it. It is also true in many code tasks: running a test is easier than writing the implementation. It is less true in open-ended writing, where “best” is multidimensional and reader-dependent.
3.3 Reward models
Reward-model BoN is the alignment version: train a model rϕ(x,y)r_\phi(x,y)rϕ(x,y) to predict human preference, sample NNN completions, and return the one with the highest reward.
This pattern appears in WebGPT, where behavior cloning was combined with rejection sampling against a reward model. WebGPT’s authors report that rejection sampling provided a substantial benefit over the behavior-cloning baseline and discuss why it can outperform RL in that setting: many attempts, hindsight over browsing trajectories, lower hyperparameter burden, and a reward model trained on similar policies. ar5iv
Reward-model BoN is powerful but fragile. Gao, Schulman, and Hilton’s reward-overoptimization study explicitly compares optimizing a proxy reward model via RL and via best-of-nnn sampling, finding that proxy optimization can harm gold-standard reward when pushed too far. arXiv Huang et al.’s 2025 ICML paper gives the sharper inference-time version: BoN can be optimal under stringent coverage assumptions, but with imperfect reward models it can degrade for large NNN because reward-model errors accumulate and become selectable. Proceedings of Machine Learning Research
This is the BoN form of Goodhart’s Law: the maximum of many noisy proxy scores is increasingly likely to be a proxy outlier.
4. Empirical evidence: where BoN improves over one sample
4.1 Math reasoning
Math is the natural habitat for BoN because the output space has discrete correctness, many prompts have a unique answer, and verification can be easier than generation. Cobbe et al.’s GSM8K verifier paper is an early canonical example. Chain-of-thought prompting later changed the generator side by making each sample a reasoning trajectory rather than a direct answer; Wei et al. showed that chain-of-thought demonstrations improved arithmetic, commonsense, and symbolic reasoning, with strong results on GSM8K. ar5iv
Once samples are reasoning trajectories, BoN can select among entire chains. The scorer may be exact final-answer match, majority vote, an outcome verifier, or a process reward model. The evidence is strongest when an external answer checker or verifier is available. It is weaker when the model’s own reward or self-evaluation is used without calibration, because the same model family may share the same blind spots.
4.2 Code generation
Code is another strong domain because candidates can be tested. HumanEval popularized pass@k as a way to measure how often repeated sampling contains a working solution. Codex showed a large jump from one sample to 100 samples, and AlphaCode showed that large-scale sampling plus filtering can produce competition-level candidate sets. arXiv
The practitioner lesson is not “sample forever.” It is “separate coverage from selection.” pass@N measures whether a correct solution exists in the candidate set. Production BoN requires a checker strong enough to identify the correct candidate. Incomplete unit tests, flaky environments, security constraints, and hidden edge cases all weaken the selection step.
4.3 Formal proofs and structured artifacts
Formal proof tasks are close to ideal for BoN because a proof checker is a high-precision deterministic verifier. Brown et al. explicitly group coding and formal proofs as domains where automatic verifiers convert increased coverage into measured performance. OpenReview
Structured-output tasks are more mixed. If the target is “valid JSON matching schema,” deterministic constrained generation often dominates BoN because it prevents invalid outputs rather than sampling and rejecting them. If the target is “valid JSON whose extracted values are semantically correct,” BoN can still help: generate several schema-valid candidates, then score with a field-level checker, retrieval consistency test, or application-specific validator. OpenAI’s Structured Outputs documentation is best read as a complementary technique: it handles syntax and schema, leaving semantic correctness to separate validation. OpenAI
4.4 Open-ended preference tasks
Open-ended tasks such as summarization, long-form question answering, instruction following, and style transfer lack a deterministic answer. Reward-model BoN can improve perceived quality, but the evidence is more contested because the scorer is itself a learned proxy for human preference.
Stiennon et al. trained reward models from human summary comparisons and used them as reward functions for policy optimization; Ouyang et al.’s InstructGPT pipeline similarly collected demonstrations, ranked model outputs, trained a reward model, and fine-tuned with RLHF. These works establish the reward-model substrate that makes BoN-of-rewards possible. arXiv
WebGPT is especially relevant because it directly compares RL and rejection sampling against a reward model, and its strongest model used behavior cloning plus reward-model rejection sampling. That is BoN as a deployed inference-time alignment method rather than merely an evaluation trick. ar5iv
5. Cost geometry: linear samples, sublinear gains
BoN’s cost is brutally simple:
Ctotal≈N⋅Cgenerate+N⋅Cscore+CaggregateC_{\text{total}} \approx N \cdot C_{\text{generate}} + N \cdot C_{\text{score}} + C_{\text{aggregate}}Ctotal≈N⋅Cgenerate+N⋅Cscore+Caggregate If the scorer is a cheap parser or test runner, generation dominates. If the scorer is a large reward model or LLM judge, scoring can dominate. If samples are generated in parallel, wall-clock latency can be closer to the slowest candidate plus scoring time, but total token compute, GPU memory pressure, and batch capacity still grow with NNN.
The quality gain is almost always sublinear. Under the ideal independent-pass formula, the marginal gain from one more sample is:
ΔN=p(1−p)N−1\Delta_N = p(1-p)^{N-1}ΔN=p(1−p)N−1 That falls exponentially with NNN. In real systems, the curve can flatten even faster because samples are correlated, temperature tuning is imperfect, and the scorer begins selecting false positives. Brown et al. describe coverage scaling that can look log-linear or like an exponentiated power law across sample counts, but they also emphasize that without automatic verifiers, common selection methods plateau. OpenReview
The practical geometry is therefore:
| Budget region | What usually happens | Practitioner implication |
|---|---|---|
| N=1N=1N=1 | No optionality; quality depends entirely on one decode | Baseline for measuring BoN value |
| Small NNN, e.g. 4–16 | Often large gains if scorer is good | Best default experiment range |
| Medium NNN, e.g. 32–128 | Gains continue on hard tasks, especially code/math | Needs calibration; monitor marginal value |
| Large NNN, hundreds+ | Coverage may improve, but selection may plateau or degrade | Requires strong verifier and cost justification |
| Very large NNN | Proxy hacking and infrastructure cost dominate | Use adaptive search, better verifier, or training-time distillation |
Snell et al.’s 2025 ICLR work is important because it treats this as an allocation problem. They find that test-time compute effectiveness varies by prompt difficulty and that compute-optimal allocation can improve efficiency by more than 4× compared with a uniform best-of-N baseline on math reasoning. OpenReview
The same cost concern motivates efficiency variants. Wang et al.’s ST-BoN work identifies two bottlenecks—full generation of all NNN samples and reward-model overhead—and reports large memory, latency, and compute savings by truncating poor candidates early and avoiding a separate reward model. OpenReview
6. Relationship to self-consistency
Self-Consistency is BoN’s closest cousin. It samples multiple chain-of-thought reasoning paths, extracts the final answer from each path, and returns the most frequent answer. Wang et al. introduced it as a decoding strategy for chain-of-thought reasoning and reported sizable gains across GSM8K, SVAMP, AQuA, StrategyQA, and ARC-Challenge. arXiv
Self-consistency can be written as a degenerate BoN scorer:
ai=answer(yi)a_i = \text{answer}(y_i)ai=answer(yi) s(yi)=∣{j:aj=ai}∣s(y_i) = \left|{j : a_j = a_i}\right|s(yi)=∣{j:aj=ai}∣ y^=argmaxis(yi)\hat{y} = \arg\max_i s(y_i)y^=argimaxs(yi) This is “degenerate” because the scorer does not independently evaluate correctness. It scores a sample by the size of its answer cluster. If ten wrong chains converge on the same wrong answer and three correct chains converge on the right one, self-consistency picks the wrong answer. But when errors are diverse and correct reasoning paths converge on a unique answer, majority vote approximates a weak verifier.
Self-consistency is best viewed as BoN without an external judge. It is cheap, easy, and surprisingly strong for discrete-answer reasoning. It is weak for open-ended generation, tasks with many equivalent phrasings, and domains where wrong heuristics produce the same answer repeatedly.
7. Relationship to RLHF
RLHF and BoN share the same reward-model substrate but use it differently.
| Method | What is optimized? | When compute is spent | Result |
|---|---|---|---|
| BoN with reward model | Candidate selection | At inference time, per prompt | No weight update; higher per-query cost |
| RLHF / PPO-style training | Policy parameters | During training | Amortized improvement; one sample can improve |
| BoN distillation / rejection-sampling finetuning | Policy imitates high-reward samples | Training after sampling | Tries to preserve BoN quality without BoN latency |
In RLHF, human comparisons train a reward model, and the policy is optimized to produce high-reward outputs. In BoN, the policy is left unchanged; the system simply samples several outputs and chooses the highest-reward one. Stiennon et al. and Ouyang et al. are the core reward-model/RLHF references; WebGPT is the direct comparison point because it uses both RL and rejection sampling against reward models. arXiv+2OpenReview+2
BoN-of-rewards can also become a training signal. The simple loop is: generate NNN candidates, score them with a reward model or verifier, keep the top candidate, and fine-tune the policy to imitate those selected outputs. This is the core intuition behind Best-of-N distillation. Sessa et al.’s BOND paper formalizes this as aligning a policy to emulate the Best-of-N distribution without paying BoN’s inference-time overhead. arXiv
The trade-off is familiar. BoN is simple and avoids unstable RL training, but pays NNN-fold inference cost. RLHF and BoN distillation amortize the reward model into the policy, but introduce training instability, distribution shift, and possible reward hacking.
8. Failure modes
8.1 Reward hacking and winner’s curse
As NNN grows, the selected candidate is not merely “high quality”; it is the candidate with the highest observed score. If score = true quality + noise, BoN selects noise. This is a winner’s curse. Gao et al. study this directly for proxy reward models under RL and best-of-nnn, and Huang et al. prove that large-NNN BoN can degrade under imperfect reward models. arXiv
8.2 Correlated samples
The pass@N formula assumes independent samples. LLM samples are not independent in the useful sense if they share the same prompt, model, decoding policy, and dominant heuristic. Raising temperature can increase diversity, but also increases nonsense. Prompt perturbation, model ensembles, tool variation, and different reasoning templates can improve diversity, but each adds operational complexity.
8.3 Bad tie-breaks
A deterministic checker often returns a binary pass/fail. If many candidates pass, tie-breaking matters. Picking the shortest answer can remove useful explanation. Picking the highest log-prob can select the most generic solution. Picking the highest reward can reintroduce reward hacking. Production systems often need layered scoring: hard validation, semantic checks, reward model, then conservative tie-break.
8.4 Incomplete specifications
Unit tests, schemas, and exact-answer matchers are convenient but incomplete. A JSON object can satisfy a schema while containing wrong data. A program can pass visible tests while mishandling edge cases. A math solution can give the right final number for the wrong reason. BoN amplifies whatever the checker rewards.
8.5 Latency and memory pressure
BoN is embarrassingly parallel, but not free. Batched generation of NNN candidates increases GPU memory, queueing, and token budget. If the scorer is another large model, the system may double inference cost. ST-BoN and hybrid approaches exist because full BoN is often wasteful: many bad trajectories are obviously bad before their final token. OpenReview
9. When BoN beats CoT, ToT, and MCTS
BoN is a width strategy. Chain-of-thought is a depth strategy. Tree search and MCTS are structured exploration strategies. The right choice depends on where the task’s uncertainty lives.
| Strategy | Core move | Best when | Weak when |
|---|---|---|---|
| BoN | Sample many complete answers; pick best | Good answer is already in the model distribution; scorer is reliable; parallel compute is available | Scorer is weak; samples are correlated; task requires backtracking |
| CoT | Spend more tokens on one reasoning path | A single sample needs more intermediate reasoning | Reasoning path can go wrong early and never recover |
| Self-consistency | Sample many CoTs; majority vote final answer | Unique answer; errors are diverse; no verifier available | Common wrong answers dominate |
| Verifier-guided beam search | Score partial steps and expand promising branches | Intermediate steps are meaningful and a PRM is available | Sequential scoring adds latency |
| ToT | Search over “thought” states with backtracking | Planning, puzzles, tasks with pivotal early decisions | High orchestration cost; self-evaluation may be weak |
| MCTS-style search | Use rollouts and value estimates over partial states | Action spaces with evaluable states and delayed reward | Requires state representation, rollout policy, and value signal |
| Constrained decoding | Prevent invalid tokens by construction | Syntax/schema validity is the main problem | Does not ensure semantic correctness |
CoT often combines with BoN: each candidate is a chain-of-thought trajectory, and BoN selects among trajectories. Wei et al. show why CoT matters for complex reasoning; self-consistency then shows why multiple CoT samples can beat greedy CoT. OpenReview
ToT and MCTS become attractive when the problem is not “generate one artifact and check it” but “make a sequence of decisions where early choices constrain later choices.” Tree of Thoughts generalizes chain-of-thought by exploring coherent intermediate “thoughts,” allowing lookahead and backtracking; on Game of 24, the paper reports 74% success versus 4% for GPT-4 with chain-of-thought prompting. OpenReview
A useful practitioner rule:
BoN wins when evaluation is cheap and final-output-level. Search wins when evaluation is stepwise and early pruning saves more than it costs. CoT wins when the base sample needs deeper reasoning but not broad exploration.
Snell et al.’s compute-optimal result supports this: the best allocation of test-time compute depends on prompt difficulty, so uniform BoN is a strong baseline but not the endpoint. OpenReview
10. Recent 2025–2026 scaling-law picture
The recent literature has converged on a more precise view of BoN.
First, repeated sampling exposes coverage scaling. Brown et al. show that with enough samples, smaller or weaker models may contain correct answers that are invisible at pass@1, and that this matters most when an automatic verifier can identify successes. OpenReview
Second, uniform BoN is rarely compute-optimal. Snell et al. show that different prompts benefit from different amounts and kinds of test-time compute, motivating adaptive allocation rather than fixed NNN. OpenReview
Third, reward-model BoN has a theoretically sharp failure mode. Huang et al. formalize inference-time alignment and show that BoN can be optimal under strong coverage assumptions but can degrade under imperfect reward models when NNN becomes large. Proceedings of Machine Learning Research
Fourth, efficiency work is attacking BoN’s linear cost. ST-BoN reduces full-sample generation and reward-model overhead by using early decoding signals; hybrid BoN/beam-search work frames the trade-off as “parallel but wasteful” versus “guided but sequential.” OpenReview
Fifth, 2026 work has started questioning the “selection only” premise. Khairi et al.’s ICLR 2026 Fusion-of-N paper argues that BoN discards useful information from losing candidates and instead synthesizes a final answer from the candidate pool. That is a direct critique of the zero-sum selection view underlying classical BoN. OpenReview
The emerging consensus is not that BoN is obsolete. It is that BoN is the baseline scaling law: the simplest way to buy quality with inference compute, and the reference point against which adaptive, verifier-guided, fusion, and training-time distillation methods should be judged.
11. Practitioner playbook
11.1 Measure three curves, not one
For a real task, track:
| Metric | Meaning |
|---|---|
| pass@N / oracle coverage | Did any candidate contain a correct answer? |
| selected accuracy | Did the scorer pick the correct answer? |
| proxy score vs human score | Is the scorer still aligned as NNN grows? |
If pass@N rises but selected accuracy is flat, the generator is good enough and the scorer is the bottleneck. If pass@N is flat, sampling is not finding better candidates. If proxy score rises while human score falls, the system is reward hacking.
11.2 Start small
A sensible first sweep is N∈{1,2,4,8,16,32}N \in {1, 2, 4, 8, 16, 32}N∈{1,2,4,8,16,32}. Plot quality against total tokens and wall-clock latency. Do not pick NNN by proxy score alone. Reward-model and verifier errors become more important exactly where large NNN looks most attractive.
11.3 Use hard filters before soft scoring
A robust scorer stack usually looks like:
-
Reject invalid syntax, unsafe tool calls, malformed JSON, uncompilable code, or impossible outputs.
-
Run deterministic checks where available.
-
Score survivors with verifier or reward model.
-
Tie-break conservatively.
This prevents the reward model from wasting capacity on obvious invalid candidates and reduces the probability that a high-reward invalid candidate wins.
11.4 Tune diversity explicitly
Temperature, nucleus sampling, prompt variants, tool variants, and model ensembles all change the candidate distribution. Diversity is valuable only if it increases the probability of a good candidate without overwhelming the scorer with adversarial junk. Track duplicate answers and semantic clusters, not just raw sample count.
11.5 Escalate adaptively
Fixed NNN wastes compute on easy prompts and under-spends on hard-but-solvable prompts. A practical policy is:
-
generate N=1N=1N=1 or N=4N=4N=4;
-
estimate confidence from checker margin, verifier margin, answer agreement, or uncertainty;
-
escalate only uncertain cases;
-
stop when marginal expected value falls below marginal cost.
This is the operational version of compute-optimal test-time scaling.
12. Bottom line
Best-of-N sampling is the simplest serious test-time compute strategy because it separates generation from selection. It asks one question: “If the model tries NNN times, can a scorer pick a better answer than a single decode?” On math, code, formal proofs, and structured artifacts, the answer is often yes because deterministic or semi-deterministic verification exists. On open-ended preference tasks, the answer is conditional: reward-model BoN can help, but large NNN amplifies proxy error.
BoN is therefore not just a trick. It is a diagnostic. It tells you whether your bottleneck is coverage, diversity, verification, or compute allocation. If BoN fails, more elaborate search may not help unless it fixes one of those bottlenecks. If BoN works, the next question is whether to keep paying its inference cost, prune it adaptively, guide it with step-level verifiers, fuse its candidates, or distill its behavior into the policy.
Reference map
| Descriptive source label | Role in this article |
|---|---|
| Cobbe et al., “Training Verifiers to Solve Math Word Problems” | Canonical verifier-guided BoN for GSM8K math reasoning. ar5iv |
| Nakano et al., “WebGPT” | Reward-model rejection sampling / best-of-nnn for browser-assisted QA. ar5iv+2ar5iv+2 |
| Stiennon et al., “Learning to Summarize from Human Feedback” | Reward models trained from human comparisons as RLHF substrate. arXiv |
| Ouyang et al., “Training Language Models to Follow Instructions with Human Feedback” | InstructGPT RLHF pipeline: demonstrations, rankings, reward model, RLHF. OpenReview |
| Gao, Schulman, Hilton, “Scaling Laws for Reward Model Overoptimization” | Proxy reward overoptimization under RL and best-of-nnn. arXiv |
| Brown et al., “Large Language Monkeys” | Repeated-sampling coverage scaling and verifier dependence. OpenReview |
| Snell et al., “Scaling LLM Test-Time Compute Optimally” | Adaptive test-time compute allocation and BoN baseline comparison. OpenReview |
| Huang et al., “Is Best-of-N the Best of Them?” | 2025 theory of BoN coverage, reward hacking, and inference-time alignment. Proceedings of Machine Learning Research |
| Wang et al., “Sampling-Efficient Test-Time Scaling” | 2025 ST-BoN efficiency work reducing full-sample and reward-model overhead. OpenReview |
| Khairi et al., “Making, Not Taking, the Best of N” | 2026 Fusion-of-N critique: synthesize from candidates rather than selecting one. OpenReview |
Companion entries
Core theory: Test-Time Compute, Inference-Time Scaling, Order Statistics, Pass@k, Coverage vs Selection, Goodhart’s Law
Algorithms: Best-of-N Sampling, Self-Consistency, Chain-of-Thought Prompting, Tree of Thoughts, Monte Carlo Tree Search, Verifier-Guided Search, Process Reward Models
Alignment: Reward Models, RLHF, Rejection Sampling Fine-Tuning, Best-of-N Distillation, Reward Model Overoptimization, Inference-Time Alignment
Practice: Unit-Test-Guided Code Generation, Schema-Constrained Generation, LLM Judge Calibration, Adaptive Test-Time Compute, Cost-Aware LLM Routing, Verifier Design
Counterarguments: Verifier Hacking, Incomplete Unit Tests, Proxy Objective Failure, Majority Vote Failure Modes, Why Pass@k Is Not Product Reliability