Ask a model a competition math problem and it gets it right 30% of the time. You have budget for 64 samples. What should you do with them?

There are three very different things "64 samples" can buy. You could check whether any of them is right, which you can only do if you have a way to check. You could return the answer that appears most often. Or you could have a second model score each sample and return the favorite. These are called coverage, voting, and selection, and the gaps between them explain a surprising amount about modern reasoning systems. A model that solves a problem once in a hundred tries has the knowledge somewhere, and a training method that finds that one success and reinforces it is what §18.4 builds. A deployment that cannot tell which try was the right one keeps only what voting or a verifier can recover.

This section works through all three, derives the unbiased estimator that every paper uses to report pass@k (and that many people get wrong), and ends with the simplest way to turn samples into training data, rejection sampling fine-tuning.

Setup and notation

Fix a problem $x$ with a correct final answer $a^\star$. The model is a policy $\pi_\theta$ (§15.7), and we sample $n$ responses $y_1, \dots, y_n \sim \pi_\theta(\cdot\mid x)$ independently, at a temperature $\tau > 0$ so they differ (§6.4). Each response is a chain of thought ending in an answer, and an extractor $\operatorname{ans}(y)$ reads the answer off (§18.1 and §18.3 discuss how). Write $a_i = \operatorname{ans}(y_i)$. The per-problem success rate is

and the answers are draws from a distribution $q(a\mid x)$ over possible final answers, with $q(a^\star\mid x) = p(x)$. A benchmark is a set of problems, so every metric below is an average over problems of a per-problem quantity.

DeepSeek and others write cons@k (consensus) for maj@$k$. All four agree at $k = 1$, and they separate as $k$ grows.

Self-consistency, or majority voting

Wang et al. (2023) proposed the simplest possible use of many chains of thought. Sample several, ignore the reasoning, and return the most common final answer,

In plain words, many different lines of reasoning that arrive at the same answer are evidence for it, and wrong lines of reasoning tend to arrive at different wrong answers. They called it self-consistency, and with 40 sampled chains the gains were large. On code-davinci-002, GSM8K accuracy went from 60.1% with one greedy chain to 78.0% (+17.9 points), SVAMP from 75.8% to 86.8%, AQuA from 39.8% to 52.0%, StrategyQA from 73.4% to 79.8%, and ARC-challenge from 83.6% to 87.5%. PaLM 540B gained the same 17.9 points on GSM8K, from 56.5% to 74.4%. They also tried weighting each vote by the chain's probability. Summing votes weighted by each chain's length-normalized probability gave 74.1% on PaLM 540B, no better than the plain vote's 74.4%, and schemes that averaged probabilities instead of summing votes did much worse, down to 22.1%. Raw sequence probabilities are dominated by length and by phrasing, so they carry little extra information about correctness.

When voting works, and its limit

Voting is a mode estimator. As $n$ grows, the vote count of each answer, divided by $n$, converges to $q(a\mid x)$ by the law of large numbers, so the winner converges to the mode of $q$. Therefore

Two consequences follow, and both surprise people. First, the correct answer does not need a majority, only a plurality. A model that is right 30% of the time, with its wrong answers spread over many values, gets that problem right with near certainty at large $n$. Second, voting can make things worse. If the model has a favorite wrong answer that it gives 40% of the time while being right 30% of the time, then pass@1 is 0.3 but maj@$\infty$ is 0. Benchmark accuracy under voting converges to the fraction of problems on which the correct answer is the mode, which can be above or below the average pass@1.

The vote needs to know when two answers are "the same", and that is harder than it looks. 1/2, 0.5, \frac{1}{2}, and 0.50 are one answer. 1,000 and 1000 are one answer. If the normalizer misses that, it splits the correct votes across spellings and hands the win to a wrong answer that happens to be written consistently.

Majority voting moves slowly toward the fraction of problems on which the correct answer is the mode (0.44 here, against a mean pass@1 of 0.36), and it is not even monotone, dipping at $k = 4$, because problems whose mode is a wrong answer lose ground quickly while problems whose correct answer is only a narrow mode gain slowly. Pass@$k$ climbs toward 1 much faster. The distance between the two lines is the subject of the rest of this section.

import re
from fractions import Fraction

def normalize_answer(s):
    return s

def majority_vote(answers):
    raise NotImplementedError

Coverage, and the pass@k estimator

In code generation, there usually is a checker. Given a function signature and a docstring, generate $k$ programs, run each against unit tests, and count the problem solved if any passes. That metric, pass@$k$, was introduced for code by Kulal et al. (2019) and made standard by the Codex paper (Chen et al. 2021), which also introduced HumanEval, 164 hand-written Python problems with an average of 7.7 tests each. The Codex-12B model solved 28.8% of them with one sample and, per the abstract, 70.2% with 100 samples. Selection mattered just as much. A fine-tuned variant, Codex-S, solved 37.7% with one sample. Given 100 samples, choosing the one with the highest mean log-probability solved 44.5%, and choosing one that passed the unit tests solved 77.5%.

For a single problem, pass@$k$ is $1 - (1 - p)^k$, and in §9.6 Exercise 9.6d computed it from known $p$. In practice $p$ is unknown and must be estimated from samples. Here is the trap.

The obvious estimator is biased

Draw $n \ge k$ samples and count $c$ correct ones. The plug-in estimate replaces $p$ by $\hat p = c/n$,

This is biased low. The function $f(u) = (1 - u)^k$ is convex on $[0, 1]$ for $k \ge 1$, so by Jensen's inequality $\mathbb{E}[f(\hat p)] \ge f(\mathbb{E}[\hat p]) = f(p) = (1 - p)^k$. Subtracting from 1 flips the inequality, so the plug-in estimate's expectation is at most the true pass@$k$, with equality only when $k = 1$ or $p \in \{0, 1\}$. The bias is worst when $k$ is close to $n$ and $p$ is small, which is exactly the regime of interest. With $n = 20$, $k = 20$, and $p = 0.05$, the truth is $1 - 0.95^{20} = 0.64$, but the plug-in estimate is $1 - (1 - c/20)^{20}$, which for the most likely outcome $c = 1$ is also 0.64 and for $c = 0$ (probability $0.36$) is 0, and averaging over all $c$ gives 0.48, an underestimate of a quarter.

The unbiased estimator, derived

The fix is to stop pretending the $n$ samples are a sample from a distribution with success rate $c/n$ and use them directly. Imagine choosing $k$ of the $n$ samples uniformly at random without replacement. The probability that all $k$ chosen are wrong is the number of ways to choose $k$ from the $n - c$ wrong ones over the number of ways to choose $k$ from all $n$. So define

In plain words, among all the size-$k$ subsets of your $n$ samples, what fraction contain at least one correct answer?

Computing it without overflow

Binomial coefficients get astronomically large. With $n = 10{,}000$ samples (Brown et al. drew that many), $\binom{10000}{5000}$ has more than 3,000 digits, far beyond the largest float64, about $1.8\times10^{308}$. Dividing two floats overflows, and dividing two exact integers that size is slow when you do it for thousands of problems and many values of $k$. Expand the ratio instead,

where the middle step pairs the $c$ factors $j = n - c + 1, \dots, n$ of $n!/(n-c)!$ with the $c$ factors $j - k$ of $(n-k)!/(n-c-k)!$. The product has $c$ terms, each in $[0, 1)$, and never overflows. If $n - c < k$, every size-$k$ subset contains a correct sample and the estimate is exactly 1. This is the form in the Codex paper's reference code. For very large $c$, summing logarithms (np.log1p(-k / j).sum()) is safer than a long product, which can underflow to zero harmlessly but loses the relative precision you might want for reporting $1 - \widehat{\text{pass@}k}$.

import numpy as np

def pass_at_k(n, c, k):
    n, c = np.asarray(n, float), np.asarray(c, float)
    return 1 - (1 - c / n) ** k      # the biased plug-in estimate

Best-of-n with a verifier

When there is no checker at deployment, we can train one. Cobbe et al. (2021) introduced GSM8K (8.5K problems, split into 7.5K for training and 1K for testing) together with this idea. Fine-tune a generator, sample 100 solutions to each training problem, label each one correct or not by its final answer, and train a verifier to predict that label from the problem and the solution. At test time, sample 100 solutions and return the one the verifier scores highest. A 6B generator with a 6B verifier slightly outperformed a fine-tuned 175B model, which the authors described as a boost roughly equivalent to a 30 times larger model. Two details are worth keeping. A verifier trained to predict correctness at every token (a value function, in the language of §15.4) eventually beat one that predicted only at the end of the solution. And accuracy rose with the number of candidates up to about 400 and then fell, because with more candidates the verifier is more likely to meet an adversarial solution that fools it.

That last finding is general. Best-of-$n$ is an optimizer, and it optimizes the verifier's score, not correctness. The more candidates you search over, the further you push into the verifier's errors, which is the same overoptimization that §16.5 studies for reward models. That section also derives how far best-of-$n$ moves from the base policy, $D_{\mathrm{KL}}(\pi_{\text{bon}}\Vert\pi_\theta) = \log n - \frac{n-1}{n}$, where $\pi_{\text{bon}}$ is the distribution of the selected response and $\pi_\theta$ the base policy, when scores have no ties (an upper bound when they do, as Beirami et al. 2024 showed). The KL grows only like $\log n$, so best-of-1000 is less than 6 nats from the base policy, which makes best-of-$n$ a gentle optimizer by RL standards and a convenient yardstick for how hard a verifier is being pushed.

Best-of-$n$ and voting can be combined. Weighted voting sums verifier scores per distinct answer and returns the answer with the largest total, so an answer reached by many reasonably scored chains can beat one reached by a single high-scoring chain. It is often the strongest simple selector when the verifier is decent but not perfect. Lightman et al. (2023) used plain best-of-$n$ with outcome and process verifiers on the MATH dataset, which is where §18.6 picks up.

Evaluating a verifier raises the same estimation problem as pass@$k$. You want BoN@$k$ for several $k$, but drawing fresh sets of $k$ samples for each $k$ is wasteful. As with pass@$k$, there is an unbiased estimator that uses one set of $n$ samples for every $k \le n$.

import numpy as np

def bon_at_k(scores, correct, k):
    return float(np.mean(correct))

def best_of_n(answers, scores):
    return answers[0]

Coverage versus selection

Brown et al. (2024) pushed repeated sampling far further than anyone had, up to 10,000 samples per problem, and gave the phenomenon a name, Large Language Monkeys. Coverage kept rising across four orders of magnitude of samples, and its growth was well described by an exponentiated power law, $c(k) \approx \exp(a\,k^{b})$ with fitted $a < 0$ and $b < 0$, so $\log c(k)$ rises toward zero like a power of $k$. On SWE-bench Lite, where unit tests make a checker available, DeepSeek-Coder-V2-Instruct went from 15.9% of issues solved with one sample to 56% with 250 samples, past the single-sample state of the art at the time, 43%. Five samples from the cheaper model solved more issues than one sample from GPT-4o or Claude 3.5 Sonnet, at over three times lower cost.

Without a checker, the picture was very different. On MATH, Llama-3-8B-Instruct's coverage went from 82.9% at 100 samples to 98.44% at 10,000, while the best of the selection methods they tried, majority voting or reward models, improved only from 40.50% to 41.41% over the same range. Selection methods plateaued beyond a few hundred samples. The model could solve almost every problem, sometimes, and nobody could tell which sample was the solution.

That gap is where reasoning RL comes in. When a checker exists at training time, a problem the model solves once in a hundred tries is a problem with a training signal. RL with verifiable rewards (§18.3) samples a group of answers, rewards the ones the checker accepts, and moves the policy toward them, which raises pass@1, which is what a deployed model without a checker needs. Whether RL can also raise coverage itself, or only concentrates the mass the base model already had, is an open question with real evidence on both sides (§18.5). DeepSeekMath already observed that its RL stage improved maj@$k$ but not pass@$k$ (Shao et al. 2024).

Rejection sampling fine-tuning

The simplest way to use a checker at training time needs no RL at all. Sample many solutions per training problem, keep the ones the checker accepts, and fine-tune on them. This is rejection sampling fine-tuning (RFT), and in §15.3 we saw it is REINFORCE in disguise. With a reward of 1 for a correct answer and 0 otherwise, the REINFORCE surrogate loss is the supervised loss on the correct samples, so one round of RFT is one large policy gradient step, taken with many optimizer updates on fixed samples, which makes it increasingly off-policy as those updates move the model. Iterating the loop (sample from the new model, filter, fine-tune again) is called expert iteration.

The best-known version for reasoning is STaR, the Self-Taught Reasoner (Zelikman et al. 2022). Start from a handful of exemplar rationales, have the model write a rationale and answer for every training question, and keep the rationales that reach the right answer. For the questions it got wrong, STaR adds rationalization. Give the model the correct answer as a hint, ask it to write a rationale that arrives there, and, if it does, keep that rationale as though it had been written without the hint. Fine-tune on everything kept, starting each outer round from the original pretrained model rather than the last checkpoint to limit overfitting, and repeat. On CommonsenseQA, GPT-J (6B) with STaR reached 72.5%, against 60.0% when fine-tuned to answer directly and 68.8% for STaR without rationalization, close to the 73.0% of a fine-tuned GPT-3 that is 30 times larger. Rationalization is what lets the loop learn from problems the model never solves on its own, at the price of training on text from a different, hint-conditioned distribution, which a pure policy gradient never does. Loops of this kind are the foundation that self-improvement methods build on, and RL with verifiable rewards (§18.4) is the version that also learns from the failures instead of discarding them.

Yuan et al. (2023) studied RFT carefully on GSM8K and found that what matters is the number of distinct reasoning paths, not the number of samples. They deduplicated correct samples by their list of equations, so two solutions that do the same arithmetic in different words count once. On LLaMA-7B, supervised fine-tuning on the training set reached 35.9%. RFT with 100 samples per problem reached 41.7%. Pooling distinct correct paths sampled from several different models reached 49.3%. RFT also helped weaker models more than stronger ones, which makes sense, since a weak model's own correct samples contain more paths it was not already producing. Many labs use a version of this as a stage of post-training, often with a reward model doing the filtering when there is no checker (§14.1).

def build_rft_dataset(samples, answers, max_per_problem):
    return [(pid, s) for pid, sols in samples.items() for s in sols]

In PyTorch

At evaluation scale you score thousands of problems with hundreds of samples each, so the voting and the estimator should be batched. Here is the whole evaluation of a toy model, sampling, majority vote, and unbiased pass@$k$, with no Python loop over problems.

Note the clamp inside lgamma. Where $n - c < k$ the argument would be negative and lgamma would return garbage, which torch.where then discards, but a NaN in the discarded branch can still poison gradients if you ever differentiate through it. Clamping first is the habit that avoids that class of bug.

Read more

• Wang et al. (2023). Self-Consistency Improves Chain of Thought Reasoning in Language Models. Majority voting over sampled chains, with the comparison of weighting schemes.
• Chen et al. (2021). Evaluating Large Language Models Trained on Code. HumanEval, pass@$k$, and the unbiased estimator in Appendix A, with the reference implementation.
• Cobbe et al. (2021). Training Verifiers to Solve Math Word Problems. GSM8K, trained verifiers, best-of-$n$, and the overoptimization curve.
• Brown et al. (2024). Large Language Monkeys: Scaling Inference Compute with Repeated Sampling. Coverage across four orders of magnitude of samples, and the selection plateau.
• Zelikman et al. (2022). STaR: Bootstrapping Reasoning With Reasoning. Expert iteration on rationales, with rationalization for the problems the model cannot solve.
• Yuan et al. (2023). Scaling Relationship on Learning Mathematical Reasoning with Large Language Models. Rejection sampling fine-tuning and why distinct reasoning paths matter.
• Beirami et al. (2024). Theoretical guarantees on the best-of-n alignment policy. Why $\log n - (n-1)/n$ is only an upper bound, and the win rate of best-of-$n$.
• Gao, Schulman & Hilton (2023). Scaling Laws for Reward Model Overoptimization. Best-of-$n$ and RL against a learned reward, measured against a gold reward as KL grows.

Watch next

▶

▶

▶