Inference-Time Search and Best-of-n

What sampling more candidates actually buys — exponentially decaying failure for linear cost, an unbiased pass@k estimator, and the exact KL price of best-of-n.

AgentsGraduate⏱ 1 hour11 min readbest-of-npass@kverifierkl divergencetest-time compute

4 problems →

AssumesError Compounding in Agent Trajectories · RLHF, Bradley–Terry and DPO

With a perfect verifier

PropositionBest-of-n with a perfect verifier

Let each of $n$ independent samples be correct with probability $p$ , and suppose a verifier identifies a correct sample whenever one is present. Then

\P(\text{success}) = 1 - (1-p)^n,

and the number of samples needed to reach target $T$ is

n \ \ge\ \frac{\log(1-T)}{\log(1-p)} .

Estimating pass@k honestly

Evaluating $\mathrm{pass}@k$ by drawing exactly $k$ samples is high-variance. The standard estimator draws $n \ge k$ and computes a combinatorial correction.

PropositionThe unbiased pass@k estimator

Draw $n$ i.i.d. samples of which $c$ are correct. Then

\widehat{\mathrm{pass}@k} = 1 - \frac{\binom{n-c}{k}}{\binom{n}{k}}

is an unbiased estimator of the probability that a uniformly random subset of $k$ of those $n$ samples contains at least one correct sample.

What best-of-n costs in distribution

Selecting the best of $n$ samples changes the distribution you are sampling from. That shift has an exact closed form, and it is the quantity that governs reward hacking.

TheoremThe KL divergence of best-of-n

Let $\pi$ be a base policy and $r$ a reward whose distribution under $\pi$ is continuous (so ties have probability zero). Let $\pi_n$ be the distribution of the highest-reward sample among $n$ i.i.d. draws from $\pi$ . Then

\mathrm{KL}\big(\pi_n \,\|\, \pi\big) \;=\; \log n - \frac{n-1}{n}.

Key idea

The divergence grows like $\log n$ — slowly, but without bound, and it depends on nothing about the reward except that it is continuous. So best-of- $n$ gives a principled exchange rate between compute and distribution shift, and lets you compare test-time selection against a KL-regularised fine-tune on the same axis: $n = 8$ costs about $1.20$ nats, $n = 64$ about $3.17$ .

This matters because distribution shift away from the base policy is exactly the regime where a learned reward model stops being trustworthy — it was fit on samples from the base policy, and best-of- $n$ is deliberately sampling where those were rare.

Imperfect verifiers

PropositionAn imperfect verifier caps the gain

Suppose each sample is correct with probability $p$ , the verifier accepts a correct sample with probability $1$ , and accepts an incorrect sample with probability $\varphi > 0$ . If the system returns a uniformly chosen accepted sample, then as $n\to\infty$ the probability that the returned answer is correct tends to

\frac{p}{p + (1-p)\varphi} \;&lt;\; 1 .

What this does not say

Independence across samples is assumed throughout. Samples from one model at one temperature are not independent in the relevant sense — they share the model's systematic errors — so $(1-p)^n$ overstates the benefit exactly as it did for majority voting. And nothing here addresses which search to run: best-of- $n$ over complete solutions, beam search over steps, or tree search with backtracking all spend the same compute differently, and the comparison between them is empirical.

Results stated on this page

PropositionBest-of-n with a perfect verifierproof includedFailure probability falls as (1−p)ⁿ, so success improves exponentially in samples while cost grows linearly.
PropositionThe unbiased pass@k estimatorproof includedFrom n samples with c correct, 1 − C(n−c, k)/C(n, k) is an unbiased estimate of the probability that k draws contain a correct one.
TheoremThe KL divergence of best-of-nproof includedBest-of-n sampling against a continuous reward has KL divergence exactly log n − (n−1)/n from the base policy.
PropositionAn imperfect verifier caps the gainproof includedWith false-positive rate φ, selected-answer precision is bounded regardless of n, and for large n the verifier's errors dominate.

Problems (4)

All problems