Test-time compute: the two-line math behind majority vote, best-of-N, and "thinking longer"

A single sample from a language model is a noisy guess. On a hard question, one draw at temperature > 0 is right only part of the time. The whole idea behind test-time compute (inference-time scaling) is that you can trade extra compute at answer time for accuracy — without training a bigger model. Here's how the three main methods work, and the surprisingly simple math that decides where each one plateaus.

Model a question by its single-sample accuracy

Give each question a probability p that one sampled answer is correct. Easy questions have p near 1; genuinely hard ones sit below 0.5, so a single guess is more often wrong than right. That noise is exactly what test-time compute exploits: draw the answer N times instead of once and aggregate. N is your compute budget — cost and latency grow roughly linearly with it.

Self-consistency: majority vote

The cheapest aggregation (Wang et al., 2022): draw N samples and keep the most common answer. No verifier needed. If the correct answer out-votes the model's favourite wrong answer with probability p, majority accuracy is the binomial tail — the chance correct votes exceed N/2.

from collections import Counter
from math import comb

def majority_vote(samples):
    return Counter(samples).most_common(1)[0][0]

def majority_accuracy(p, n):
    acc = 0.0
    for c in range(n + 1):                 # c = number of correct votes
        pm = comb(n, c) * p**c * (1 - p)**(n - c)
        if   2 * c >  n: acc += pm         # correct wins
        elif 2 * c == n: acc += 0.5 * pm   # tie, break 50/50
    return acc

This rises toward 1 when p > 0.5 — but toward 0 when p < 0.5. Voting only amplifies whatever the model believes most often, so on hard questions it can confidently lock in the wrong answer. That's the fundamental ceiling: majority vote can never beat the fraction of questions the model is right about on average.

Best-of-N: let a verifier keep the best sample

If you have a verifier — a reward model, a unit test, a proof checker — you don't need the majority. You need one good sample the verifier can recognize. With a perfect verifier, accuracy is pass@N:

def best_of_n(samples, verifier):
    return max(samples, key=verifier)      # keep the highest-scored

def best_of_n_accuracy(p, n):
    return 1 - (1 - p) ** n                # P(at least one of n correct)

1 - (1 - p)^N climbs toward 1 for any p > 0 — it fixes even the hard questions majority vote gives up on. For p = 0.42: N=1 gives 0.42, N=8 gives 0.98. One correct sample is a needle in the haystack, and the verifier's job is to find it. The catch: a real verifier is imperfect, and its accuracy caps the gain well below the theoretical pass@N.

Both curves are concave — diminishing returns

Sweep N and average over your question set and you get the key picture: the first few extra samples buy a lot of accuracy, later ones almost nothing. Plotting N on a log axis makes the tail visibly flatten. Majority vote plateaus below 100%; best-of-N keeps climbing. The gap between the two plateaus is the value of having a verifier.

"Think longer" — sequential compute (o1 / DeepSeek-R1)

Sampling-and-voting is parallel test-time compute. o1 and DeepSeek-R1 add sequential compute: one long chain of thought that explores approaches, self-checks, and backtracks before committing — thousands of hidden reasoning tokens. It's implicit search inside a single sample, exposed as a simple effort knob rather than an N-of-samples loop.

# OpenAI o1 / o3 expose it as reasoning_effort:
client.chat.completions.create(model="o3", reasoning_effort="high", ...)
# DeepSeek-R1 emits a long <think>...</think> trace before the final answer.
# More thinking tokens = more test-time compute = better answers on hard problems.

When inference compute beats a bigger model

DeepMind made the tradeoff concrete (Snell et al., 2024): on many problems, giving a small model a big test-time budget matches a much larger model answering once — up to a point. A bigger base model raises every sample's p, shifting the whole curve up. So the real question isn't "bigger or think-harder" — it's how to split a fixed budget between pretraining and inference, and compute-optimal scaling even picks N per question by difficulty. This is why labs now scale inference compute, not just parameters.

Slide the compute budget from 1 to 64 samples and watch the accuracy curve climb and level off — self-consistency vs best-of-N, on a deterministic in-browser model: https://dev48v.infy.uk/ai/days/day53-test-time-compute.html