Test-Time Compute › Multiple Sampling

Multiple sampling is the simplest test-time compute strategy. Given a prompt $x$, you run the model $N$ times to produce a set of candidate responses. Formally, the candidate set is:

$$\mathcal{C} = \{y_1, y_2, \ldots, y_N\}$$

where:

• $x$ is the input prompt
• $y_i$ is the $i$-th candidate response
• $N$ is the number of independent samples drawn
• Each $y_i$ is sampled independently from the model's distribution: $y_i \sim p_\theta(\cdot \mid x)$

The quality of this set depends on two factors. First, the coverage of the sample set: does it contain at least one good answer? Second, the selector's precision: can you reliably pick the best answer from the candidates? Both matter, and each is independently improvable. Coverage is primarily a function of the model's underlying accuracy and the sampling temperature. Selector precision is a function of the verification or scoring mechanism you apply.

It is worth emphasizing that even when coverage is high, a poor selector erases most of the benefit. If your selection rule cannot distinguish the correct answer from the wrong ones, having many correct candidates in the pool does not help. Conversely, even a mediocre selector can extract enormous value from a pool with high coverage. The two components interact multiplicatively: you need both to work.

When you sample with temperature $T > 0$, the model's output distribution over the next token is reshaped. The model ordinarily outputs raw scores called logits, and the softmax function turns them into probabilities. Temperature scales the logits before the softmax, controlling how peaked or flat the resulting distribution is. For a single decoding step, the probability of token $t$ given the context is:

$$p_\theta(y_t \mid y_{<t}, x) = \frac{\exp\!\left(\dfrac{z_t}{T}\right)}{\displaystyle\sum_{v \in V} \exp\!\left(\dfrac{z_v}{T}\right)}$$

where:

• $z_t$ is the raw logit score for token $t$ from the model's output layer
• $T > 0$ is the temperature parameter
• $V$ is the vocabulary (the set of all possible tokens)
• $y_{<t} = (y_1, \ldots, y_{t-1})$ is the sequence of tokens generated so far
• The denominator is the partition function that ensures the distribution sums to 1

When $T \to 0$, the formula reduces to argmax decoding: the token with the highest logit receives all the probability mass. When $T = 1$, the distribution is unmodified. When $T > 1$, the distribution is flattened toward uniform, increasing diversity at the cost of coherence.

For multiple sampling to work well, you need diversity: if all $N$ samples are nearly identical, you get $N$ copies of the same answer, and selecting among them gives no improvement over single-pass decoding. The choice of $T$ is a design decision that trades off coverage (higher $T$) against quality per sample (lower $T$).

This tradeoff is task-dependent. For math problems where the correct answer is a specific number or expression, high temperatures can improve coverage by exploring more distinct reasoning paths, even if individual chains become noisier. For code generation, moderate temperatures around 0.7 to 0.9 tend to work well, since you want diverse logic but not incoherent syntax. For factual question answering, lower temperatures often work better because the model's top-probability answers tend to be factually correct, and increasing temperature mostly adds noise. The right setting requires empirical calibration for your specific task and model.

Another dimension of diversity is top-p (nucleus) sampling and top-k sampling, which we covered in detail in the GPT Architecture chapter. These methods further shape the sampling distribution by truncating low-probability tokens before sampling. In the context of multiple sampling, they control whether the model explores rare but potentially correct reasoning paths or stays close to its high-confidence outputs.

The probability that at least one of $k$ samples is correct can be computed exactly if you know how many of $n$ generated samples are correct. The pass@k formula, introduced for code generation evaluation, is:

$$\text{pass@}k = 1 - \frac{\dbinom{n - c}{k}}{\dbinom{n}{k}}$$

where:

• $n$ is the total number of generated samples for a single problem
• $c$ is the number of correct samples among those $n$ ($0 \le c \le n$)
• $k$ is the number of samples you are allowed to submit ($k \le n$)
• $\binom{a}{b}$ denotes the binomial coefficient "a choose b"

The formula counts the fraction of size-$k$ subsets of the $n$ samples that contain no correct answer, and subtracts that from 1. If $c = 0$ (none are correct), pass@k = 0. If $c \ge k$, the formula equals 1 because every subset contains at least one correct answer.

To understand why the formula takes this form, consider the complementary event: what is the probability that a randomly chosen subset of $k$ samples contains no correct answer? There are $\binom{n - c}{k}$ ways to choose $k$ samples entirely from the $n - c$ incorrect ones, and $\binom{n}{k}$ ways to choose any $k$ samples. The ratio of these two binomial coefficients gives the probability of failure, which subtracted from 1 gives the probability of success.

For independent samples each correct with probability $p$, the expected pass@k simplifies to the approximation:

$$\mathbb{E}[\text{pass@}k] \approx 1 - (1 - p)^k$$

where $p$ is the per-sample probability of correctness. This approximation is tight when $n$ is large relative to $k$.

The practical implication is stark. Even a model with $p = 0.05$ on a hard coding problem achieves:

$$\text{pass@50} \approx 1 - (1 - 0.05)^{50} = 1 - 0.95^{50} \approx 0.923$$

Scaling $k$ from 1 to 50 converts a near-impossible task (5% success rate) into a highly likely success (92%). This is the mathematical core of why test-time compute works for verifiable tasks: you are not improving any single sample, but you are dramatically improving the probability that your sample set contains at least one correct answer.

Generating many candidates is useless unless you can pick the best one. The selection problem is harder than it looks, because you cannot in general know which candidate is correct without running the same computation that originally produced it. Several approaches exist for this problem, each with different assumptions, costs, and reliability properties.

Majority voting (self-consistency). If answers to the same question can be compared directly, such as numerical answers or classification labels, select the most frequently occurring answer across all candidates. This works remarkably well for math reasoning: if you generate 40 chain-of-thought solutions and 28 of them arrive at the same numerical answer, that answer is likely correct even if many of the individual reasoning chains contain errors. The underlying reason is that correct answers tend to be unique (there is typically one right answer), while wrong answers are diverse (different chains make different mistakes). This asymmetry means that correct answers accumulate plurality votes while wrong answers split votes among many alternatives.

Majority voting requires no additional model and adds almost no compute overhead, since you just count answer occurrences. Its main limitation is that it only works when answers can be directly compared. For open-ended prose, there is no natural notion of two responses being "the same answer."

Reward model scoring. Train a separate scoring model on human preferences or correctness labels, then select the candidate with the highest score. This is the reranking paradigm used in passage retrieval and code generation. The quality of selection is bounded by the accuracy of the scorer, which means that reward model quality is the binding constraint. A poorly calibrated reward model will select confidently wrong answers, producing no benefit or even net harm from the sampling.

Process reward model (PRM) scoring. Rather than scoring completed answers, a PRM scores each reasoning step and aggregates across the chain. PRMs are more robust to "correct-answer, wrong-reasoning" failure modes because they require the intermediate steps to be valid. When used for candidate selection, the total score for a candidate is typically the product or minimum of its step-level scores. The product penalizes chains with any weak step; the minimum is even stricter, selecting only chains where every step is confident. We covered the design and training of PRMs in detail in the Process Reward Models chapter.

Verifier-guided selection. For structured tasks such as code or formal proofs, you can execute or symbolically check the candidate answer directly. A program that passes all test cases is correct by definition; no learned verifier is needed. This is the gold standard when applicable, because the verification is guaranteed correct and requires no additional model training.

The choice of selection strategy has a large impact on overall accuracy. Majority voting is cheap and reliable when the answer is discrete. Reward model scoring generalizes to open-ended outputs but depends on the quality of the scorer, which may itself be brittle on out-of-distribution queries. PRM scoring sits between these extremes: it is more expensive than majority voting because it requires running the reward model over every step of every candidate chain, but it is more reliable than outcome-level reward models because it catches errors at the step where they first occur rather than only penalizing wrong final answers.

Verifier-guided selection is uniquely powerful for code and formal math because the verification is guaranteed correct. No amount of reward model training can match the reliability of a formal checker or a unit test suite. For this reason, the most impressive test-time compute results in the literature tend to appear on coding and math benchmarks, where this class of feedback is available.