Best-of-N Sampling: Why N=64 Scores Higher and Answers Worse

You bolt a reranker onto your generation endpoint: sample N candidates from Claude Sonnet 4.5 or GPT-5.1, score each with a judge, return the argmax. You sweep N from 1 to 64 and the judge score climbs monotonically — 6.1, 6.8, 7.3, 7.6, 7.9. Clean log curve. You ship N=64.

Two weeks later the support queue fills with "the answers got wordier and less useful." The judge score in your dashboard is still 7.9.

That is not a bug in your reranker. Best-of-N sampling is a KL-constrained policy optimizer running at inference time, and past a certain N you are spending your entire KL budget on your judge's error term rather than on answer quality. The math tells you roughly where that happens before you ship.

TL;DR

• Best-of-N sampling with a tie-free scorer moves your output distribution off the base policy by at most log N − (N−1)/N nats. N=4 costs ~0.64 nats, N=16 ~1.84, N=64 ~3.17. KL grows logarithmically; each doubling of N buys ~0.69 more nats at 2× the inference cost.
• Your judge score is a proxy. Ranking N candidates selects the max of true_quality + judge_error, so as N grows the extreme order statistic of the error dominates the selection. This is reward model overoptimization, and it appears as monotonically rising proxy scores with flat or falling real quality.
• Overoptimization is empirically well-behaved: gold reward against d = sqrt(KL) fits a curve that rises then bends down, with a single peak. There is an N* for your judge, and it is usually much smaller than 64.
• Verifiable rewards (unit tests, compiler, schema validation, exact match) have near-zero error term, so best-of-N sampling on them scales to hundreds of samples. Learned judges do not.
• To find N*: generate a pool of 64 once, bootstrap best-of-n subsets, and score selections with a held-out judge or human labels. Pick the argmax of the held-out curve, not the proxy curve.

How much does best-of-N sampling actually move your distribution?

Exactly one number, and it doesn't depend on your model. If you draw N i.i.d. samples from a base policy and keep the argmax under any scorer that produces no ties, the resulting distribution's KL divergence from the base policy is bounded by:

KL(BoN || base) ≤ log N − (N−1)/N   nats

The intuition: the selected sample is the max of N draws, so the induced density is N · p(x) · F(x)^(N−1) where F is the CDF of the score. Integrate p_bon · log(p_bon/p) and the model-specific terms cancel — you're left with a pure function of N. (Beirami et al. showed this closed form is an upper bound and gave tighter estimators; treat it as a ceiling on how far you've drifted.)

Concretely:

N	KL (nats)	cost vs N=1
2	0.19	2×
4	0.64	4×
8	1.20	8×
16	1.84	16×
32	2.50	32×
64	3.17	64×
128	3.86	128×

Two things jump out. First, going from 16 to 64 quadruples your bill for 1.3 extra nats. Second, 3 nats is not a small perturbation — RLHF runs routinely operate in that range with an explicit KL penalty holding them back, and here you're spending it with no penalty term at all. Best-of-N sampling is unconstrained optimization against your judge, and the only thing limiting it is N.

Why does the proxy score keep rising while real quality falls?

Because you rank on r̂(x) = r(x) + ε(x), where r is true quality and ε is judge error. Selecting the argmax over N candidates doesn't just find high r — it finds high ε. As N grows, the expected max of the error term grows like the tail of ε's distribution, and it grows faster than the max of r once the candidates start bunching up in true quality.

This is why the failure mode is always stylistic. Judge error isn't white noise; it's structured and correlated with surface features — length, markdown headers, hedging, confident tone, restating the question. Those features are cheap for the model to produce and they're exactly what the argmax over 64 samples will find. Your outputs get longer and more formatted because that's the direction of steepest ascent in ε, not in r.

The empirical shape is well documented in the reward-model overoptimization literature: plot gold reward against d = sqrt(KL) and best-of-N traces a curve of the form d(α − βd) — linear gain, quadratic penalty, one interior maximum at d* = α/(2β). The proxy reward, meanwhile, rises monotonically forever. Two findings that matter operationally: β shrinks as the reward model gets bigger and better-trained (stronger judges overoptimize later, not never), and the curve is largely insensitive to the size of the policy you're sampling from. You cannot escape this by upgrading from Sonnet to Opus. You escape it by improving the judge or lowering N.

How do I find N* without a gold reward model?

Generate a pool once, then bootstrap. Do not run 6 separate inference sweeps — subsample from a fixed pool of 64 so the candidate distribution is identical across N and the only thing changing is selection pressure.

The critical part is the second scorer. You need something that does not share ε with your ranking judge: a different model family, human labels on a few hundred prompts, or a task-specific verifier. Two prompts against the same model with the same rubric will share most of their error and will happily confirm your bad N.

import math, random
from statistics import mean, stdev

def bon_kl(n: int) -> float:
    """KL(best-of-n || base) in nats. Exact under a continuous, tie-free score."""
    return math.log(n) - (n - 1) / n

def selection_curve(pool, ns=(1, 2, 4, 8, 16, 32, 64), trials=400, seed=0):
    """pool: list of prompts, each a list of dicts {"proxy": float, "held_out": float}.
    Bootstraps best-of-n by sampling n candidates without replacement."""
    rng = random.Random(seed)
    out = {}
    for n in ns:
        proxy_sel, held_sel, oracle_gap = [], [], []
        for cands in pool:
            assert len(cands) >= max(ns), "pool must be at least max(ns) deep"
            for _ in range(trials):
                sub = rng.sample(cands, n)
                best = max(sub, key=lambda c: c["proxy"])
                proxy_sel.append(best["proxy"])
                held_sel.append(best["held_out"])
                # what a perfect ranker would have gotten from the same subset
                oracle_gap.append(max(c["held_out"] for c in sub) - best["held_out"])
        out[n] = {
            "kl_nats": round(bon_kl(n), 3),
            "proxy": round(mean(proxy_sel), 3),
            "held_out": round(mean(held_sel), 3),
            "held_out_se": round(stdev(held_sel) / math.sqrt(len(pool)), 3),
            "selection_error": round(mean(oracle_gap), 3),  # grows => overoptimizing
        }
    return out

curve = selection_curve(pool)
best_n = max(curve, key=lambda n: curve[n]["held_out"])
print(f"N* = {best_n}  (KL {curve[best_n]['kl_nats']} nats)")
for n, row in curve.items():
    print(n, row)

Read three columns together. proxy rising while held_out flattens is the signature of overoptimization. selection_error — the gap between what a perfect ranker would have picked from the same subset and what your judge picked — is the direct measurement: if it grows with N, your judge is being outrun by its own noise. Note the standard error is computed over prompts, not over bootstrap trials; trials are correlated and will give you a fake-tight interval.

In practice the held-out curve for a general-purpose LLM judge on open-ended generation tends to peak in the single digits to low teens and go flat or slightly negative after. Verifier-scored code and math go much further.

Why do verifiers scale where judges don't?

Because ε ≈ 0. If your scorer is "does the test suite pass," "does it parse against the JSON Schema," "does the SQL execute and return the right row count," then there is no error term for the argmax to exploit — a program either passes or it doesn't. Best-of-N sampling against a verifier is just repeated Bernoulli trials, and coverage climbs with N up to the model's ceiling. This is why pass@k keeps improving at k=100 for code while judge-ranked prose stops improving at N=8.

The production pattern that follows: gate with verifiers, rank with judges, and keep N small on the judge stage. Generate 32 candidates, drop everything that fails compilation/schema/citation checks, then have the judge rank the ~6 survivors. The verifier absorbs the large-N regime where it's safe, and the judge only makes the fine-grained call across a handful of already-valid options — a low-KL decision.

Three more things that move the needle more than raising N:

Ensemble the judge. Two or three judges from different model families, averaged, decorrelates ε. The variance of the mean error drops roughly with the number of independent judges, which directly pushes N* out. This costs less than doubling N because judging is cheaper than generating.

Watch temperature. The KL formula assumes candidates are i.i.d. from your deployed policy. If you crank temperature to 1.2 to get diversity for the reranker, you've already moved off-policy before selection, and the total drift is larger than the table says.

Cap the surface features ε loves. If your judge rewards length, put a hard length constraint in the generation prompt so all N candidates are comparable on that axis. You're not fixing the judge — you're removing the cheapest direction of reward hacking from the candidate set.

One asymmetry worth knowing: at equal KL, best-of-N often matches or beats RL fine-tuning on gold reward, because the RL curve bends down with a log d term while BoN's bends down quadratically from a higher intercept. BoN's problem isn't quality per nat, it's that you pay N× at every request forever. If a specific N is winning for you consistently, that's a signal to distill — sample with BoN offline, filter with verifiers, and fine-tune on the survivors, so you keep the behavior at 1× inference cost.

So why does N=64 score higher and answer worse?

Because best-of-N sampling is optimization against your judge, not against quality, and the two diverge at a predictable point. Each doubling of N pushes your output distribution ~0.69 nats further from the base policy (log N − (N−1)/N), and while the proxy score rises monotonically with that drift, true quality follows a curve that peaks and turns down — the argmax over many candidates increasingly selects the judge's error rather than the answer's merit, which is why the outputs drift toward long, confident, heavily formatted prose. Find your N* by generating a fixed pool once, bootstrapping best-of-n subsets, and scoring the selections with an independent held-out judge; then gate with verifiers where the reward is checkable and keep N small on the learned-judge stage. If a large N genuinely helps, distill it into the model instead of paying for it on every request.