Let’s study best-of-$n$ sampling more formally. Suppose we have some sample space $S$ (such as the set of possible question-answer pairs), some probability distribution $P$ over $S$, a true objective (or “reward”) $R_{\text{true}}:S\to\mathbb R$, and a proxy objective $R_{\text{proxy}}:S\to\mathbb R$. Let’s say that we somehow optimize $R_{\text{proxy}}$ and thereby obtain some new distribution $P^\prime$. Then:

• The expectation $\mathbb E_{x^\prime\sim P^\prime}\left[R_{\text{true}}\left(x^\prime\right)\right]$ measures how well we have optimized the true objective.
• The KL divergence⁠(opens in a new window) $D_{\text{KL}}\left(P^\prime\parallel P\right)$ measures how much optimization we have done. For example, if $P^\prime$ is obtained by taking the first sample from $P$ that lies in some subset $S^\prime\subseteq S$, then this KL divergence is just the negative log probability that a sample from $P$ lies in $S^\prime$.

It turns out that in the case of best-of- $n$ sampling, both of these quantities can be estimated efficiently using samples from $P$.

Let’s look at the expectation first. The naive approach is to use a Monte Carlo estimator: run best-of- $n$ sampling many times, measure the true objective on those samples, and average the results. However, there is a better estimator. If we have $N\geq n$ samples from $P$ overall, then we can simultaneously consider every possible subset of these samples of size $n$, weight each sample by the number of subsets for which it is the best according to the proxy objective, and then take the weighted average true objective score. This weight is just the binomial coefficient $\binom{k-1}{n-1}$, where $k$ is the rank of the sample under the proxy objective, from $1$ (worst) up to $N$ (best).^A

The sum of these weights is $\binom{N}{n}$, giving a proof of the Hockey-stick identity⁠(opens in a new window). For a formal derivation of the estimator described here, see Appendix I of the WebGPT paper⁠(opens in a new window).

As well as using samples more efficiently, this also allows us to reuse samples for different values of $n$. As for the KL divergence, surprisingly, this turns out to have an exact formula that works for any continuous probability distribution $P$ (i.e., as long as $P$ has no point masses). One might naively guess that the answer is $\log n$, since best-of-$n$ is doing something like taking the top $\frac 1n$ of the distribution, and this is roughly correct: the exact answer is $\log n-\frac{n-1}n$. ^B

Together, these estimators allow us to easily analyze how the true objective varies with the amount of optimization applied to the proxy objective.

Here’s a real-life example from WebGPT⁠: