Best-of-N, Self-Consistency and Verifiers · Advanced Reasoning, Planning & Self-Improving Agents

The SQL agent has been in production for six weeks. It takes a question in English, inspects a schema, and writes a query; an analyst reviews anything it produces before it runs against the warehouse. The review queue says 71% of its queries are accepted unchanged. The analysts have opinions about the other 29%, and the one that comes up most is that the agent usually knows — ask it twice and one of the two answers is right. That observation, repeated by three people independently, is the entire premise of this lesson.

You are going to build the parallel axis end to end: a sampler that produces n candidates, interchangeable selectors that pick among them, and the measurement machinery that tells you which selector is worth its tokens. You will simulate majority voting under different error structures, watch a verifier-guided frontier rise and then bend, and compute dollars per solved task so you know where to stop. The code runs in your browser on the standard library alone — the mechanics of selection are model-independent.

1. The Machinery: Sample, Score, Select

Every technique in this lesson has the same three-stage shape, and writing it that way once lets you swap components without rewriting the pipeline.

python

# tts.py - the parallel axis, as an interface.
from dataclasses import dataclass, field

@dataclass
class Candidate:
    text: str                     # the full reasoning trace + answer
    answer: str | None = None     # canonicalized final answer, if extractable
    logprob: float | None = None  # mean token logprob, if the API gives it
    scores: dict = field(default_factory=dict)   # scorer name -> score

def sample_candidates(client, prompt, n, temperature=0.8, max_tokens=1200):
    '''One prompt, n independent completions. Prefer a single API call with
    n=>1 so the provider shares the prompt prefill across samples.'''
    resp = client.completions(prompt=prompt, n=n,
                              temperature=temperature, max_tokens=max_tokens)
    return [Candidate(text=c.text, answer=extract_answer(c.text)) for c in resp]

# A selector is just list[Candidate] -> Candidate. Everything below is one.

Three design notes that matter more than they look. First, temperature must be above zero — n greedy samples are the same sample n times, and you have paid eight times for one answer; 0.6 to 1.0 is the usual operating range. Second, ask the provider for n completions in one request rather than issuing n requests, so the prompt is prefilled once and the KV cache is shared. Third, extract_answer is not a detail; it decides whether half the techniques in this lesson work at all.

2. Self-Consistency: Majority Vote Over Reasoning Paths

Self-consistency (Wang et al., 2023) is the cheapest selector that works. Sample n chains of thought, extract the final answer from each, and return the one that appears most often. No verifier, no extra model, no training. The insight is that a model's errors are often idiosyncratic — different sampled paths go wrong in different ways — while its correct reasoning tends to converge on the same destination. Take the mode and the noise cancels.

python

from collections import Counter

def majority_vote(candidates):
    '''Return the candidate whose canonicalized answer is most common.'''
    answers = [c.answer for c in candidates if c.answer is not None]
    if not answers:
        return candidates[0]
    winner, _ = Counter(answers).most_common(1)[0]
    return next(c for c in candidates if c.answer == winner)

def canonicalize(raw):
    '''The load-bearing function. '1,024', ' 1024 ', '1024.0' and '$1024'
    must all become the same string or the vote splits and you learn nothing.'''
    s = raw.strip().lower().replace(",", "").replace("$", "").rstrip(".")
    try:
        f = float(s)
        return str(int(f)) if f == int(f) else repr(round(f, 6))
    except ValueError:
        return " ".join(s.split())

Spend real time on canonicalize. In a vote over 16 samples, three different spellings of the correct answer score 3, 3 and 2 while a single consistently-formatted wrong answer scores 4 and wins. That failure is silent, common, and entirely self-inflicted; the fix is a canonicalizer with unit tests, exactly as you would build for a programmatic grader in Evaluation & Benchmarking of Agentic Systems.

Now the behavior. Majority voting amplifies whatever the model's modal answer is — wonderful when the mode is correct and catastrophic when it is not. The simulation below draws samples from a model with per-sample accuracy p, spreads the errors either uniformly across seven distractors or concentrates 80% of them on one sticky wrong answer, and reports majority-vote accuracy as n grows.

pythoneditable · runnable

import random
from collections import Counter

random.seed(7)
TRIALS = 2000
N_DISTRACTORS = 7

def draw(p_correct, sticky):
    '''One sampled reasoning path, reduced to its final answer.'''
    if random.random() < p_correct:
        return "correct"
    if random.random() < sticky:          # errors that share one attractor
        return "wrong-A"
    return "wrong-%d" % random.randrange(1, N_DISTRACTORS + 1)

def majority_accuracy(p, n, sticky):
    hits = 0
    for _ in range(TRIALS):
        votes = Counter(draw(p, sticky) for _ in range(n))
        top = max(votes.values())
        winners = [a for a, c in votes.items() if c == top]
        if random.choice(winners) == "correct":   # ties broken at random
            hits += 1
    return hits / TRIALS

NS = (1, 3, 5, 11, 21, 51)
print("scenario                               " + "".join("n=%-6d" % n for n in NS))
for label, p, sticky in [
    ("p=0.35, errors spread over 7 wrongs", 0.35, 0.0),
    ("p=0.55, errors spread over 7 wrongs", 0.55, 0.0),
    ("p=0.30, 80% of errors share one wrong", 0.30, 0.8),
]:
    row = [majority_accuracy(p, n, sticky) for n in NS]
    print(label.ljust(39) + "".join("%.2f  " % v for v in row))

import random
from collections import Counter

random.seed(7)
TRIALS = 2000
N_DISTRACTORS = 7

def draw(p_correct, sticky):
    '''One sampled reasoning path, reduced to its final answer.'''
    if random.random() < p_correct:
        return "correct"
    if random.random() < sticky:          # errors that share one attractor
        return "wrong-A"
    return "wrong-%d" % random.randrange(1, N_DISTRACTORS + 1)

def majority_accuracy(p, n, sticky):
    hits = 0
    for _ in range(TRIALS):
        votes = Counter(draw(p, sticky) for _ in range(n))
        top = max(votes.values())
        winners = [a for a, c in votes.items() if c == top]
        if random.choice(winners) == "correct":   # ties broken at random
            hits += 1
    return hits / TRIALS

NS = (1, 3, 5, 11, 21, 51)
print("scenario                               " + "".join("n=%-6d" % n for n in NS))
for label, p, sticky in [
    ("p=0.35, errors spread over 7 wrongs", 0.35, 0.0),
    ("p=0.55, errors spread over 7 wrongs", 0.55, 0.0),
    ("p=0.30, 80% of errors share one wrong", 0.30, 0.8),
]:
    row = [majority_accuracy(p, n, sticky) for n in NS]
    print(label.ljust(39) + "".join("%.2f  " % v for v in row))

The first two rows are the advertised result: a model right only 35% of the time reaches essentially 100% by n=51, because no single wrong answer can out-poll the correct one. The third row is the one to remember. When the model has a systematic bias — a misread of the question, a plausible-but-wrong formula it reaches for consistently — majority voting does not average the bias away. It converges to it, and accuracy falls from 0.28 at n=1 to 0.02 at n=51. You have spent 51x the compute to become confidently wrong.

3. Where Majority Vote Does Not Apply

Self-consistency requires an equivalence relation on answers. That limits it to discrete outputs: a number, a label, a multiple-choice letter, a normalized entity, a boolean. It falls apart on:

Free-form text. Sixteen summaries are sixteen distinct strings; every vote count is 1.
Code. Two correct programs almost never match textually, so a textual vote is meaningless.
Agent trajectories. There is no "final answer" to compare — the output is a sequence of side effects.

For code there is a well-tested repair: vote on behavior instead of text. Run every candidate program on the same inputs, fingerprint its outputs, and treat programs with identical fingerprints as one equivalence class. This is the clustering idea behind AlphaCode's selection stage and CodeT-style approaches, and it converts an uncountable output space into a countable one.

python

import hashlib

def behavior_key(fn, probe_inputs):
    '''Fingerprint a candidate by what it DOES, not how it is written.'''
    out = []
    for x in probe_inputs:
        try:
            out.append(repr(fn(x)))
        except Exception as e:               # crashing is also a behavior
            out.append("ERR:" + type(e).__name__)
    return hashlib.sha1("|".join(out).encode()).hexdigest()[:12]

def cluster_vote(candidate_fns, probe_inputs):
    '''Majority vote over behavioral equivalence classes.'''
    clusters = {}
    for fn in candidate_fns:
        clusters.setdefault(behavior_key(fn, probe_inputs), []).append(fn)
    return max(clusters.values(), key=len)[0]

Two cautions. The probe inputs must be generated, not taken from your held-out tests, or you have leaked the eval into selection. And untrusted model-written code must execute in a sandbox — the isolation requirements are covered in Security, Safety & Governance of Agents, and "it is just a candidate solution" is not an exemption.

4. Best-of-N With a Verifier

When you have something that can score a candidate, you stop needing the crowd. Best-of-n scores every candidate and returns the argmax. The scorer is an interface, and the range of things that can implement it is wider than most people assume:

Scorer	Signal	Soundness	Marginal cost
Test suite / execution	Pass or fail	Sound within test coverage	ms of CPU
Schema / constraint check	Valid or not	Sound	negligible
Learned reward model	Scalar quality	Approximate, gameable	one small forward pass
LLM judge with rubric	Scalar or ranking	Approximate, biased	a few hundred tokens
Mean token logprob	Model confidence	Weak; correlates poorly	free

python

def best_of_n(candidates, scorer):
    for c in candidates:
        c.scores["primary"] = scorer(c)
    return max(candidates, key=lambda c: c.scores["primary"])

def weighted_self_consistency(candidates, scorer):
    '''Usually beats both plain majority vote and plain best-of-n: cluster by
    answer, sum verifier scores within each cluster, return the best cluster.'''
    pooled = {}
    for c in candidates:
        if c.answer is None:
            continue
        c.scores["primary"] = scorer(c)
        pooled[c.answer] = pooled.get(c.answer, 0.0) + c.scores["primary"]
    if not pooled:
        return candidates[0]
    winner = max(pooled, key=pooled.get)
    return max((c for c in candidates if c.answer == winner),
               key=lambda c: c.scores["primary"])

Weighted self-consistency is the default you should reach for when answers are discrete and you have a verifier. Plain best-of-n bets everything on a single highest-scoring sample, which makes it maximally exposed to one verifier mistake. Plain majority voting ignores the verifier entirely. Summing scores within an answer cluster uses both signals: an answer needs both agreement and quality to win, and a lone outlier that the verifier happens to love cannot carry the decision by itself.

5. The Accuracy-Versus-Compute Frontier

Now measure. The simulation below is the experiment you will run for real against your own agent, with the model replaced by a coin flip so it executes instantly. Each candidate is correct with probability p=0.40; the verifier scores correct candidates around 1.0 and incorrect ones around 0.0, with Gaussian noise of width sigma. In the third configuration, 3% of wrong candidates happen to have whatever surface property the verifier loves and score around 1.6 — a small, realistic rate of verifier gaming. Coverage is the ceiling; selected is what you actually ship.

pythoneditable · runnable

import random

random.seed(11)
TRIALS = 1500
NS = (1, 2, 4, 8, 16, 32, 64)

def run_task(p, n, sigma, gaming):
    best_score, picked_correct, covered = None, False, False
    for _ in range(n):
        correct = random.random() < p
        covered = covered or correct
        if correct:
            mu = 1.0
        elif random.random() < gaming:
            mu = 1.6                 # wrong, but hits what the verifier rewards
        else:
            mu = 0.0
        score = mu + random.gauss(0.0, sigma)
        if best_score is None or score > best_score:
            best_score, picked_correct = score, correct
    return covered, picked_correct

def frontier(p, sigma, gaming):
    rows = []
    for n in NS:
        cov = sel = 0
        for _ in range(TRIALS):
            c, s = run_task(p, n, sigma, gaming)
            cov += c
            sel += s
        rows.append((n, cov / TRIALS, sel / TRIALS))
    return rows

for label, sigma, gaming in [
    ("sound verifier (no noise, no gaming)", 0.0, 0.0),
    ("noisy learned verifier (sigma=0.5)", 0.5, 0.0),
    ("noisy verifier, 3% of wrong answers game it", 0.5, 0.03),
]:
    print(label)
    print("   n   coverage   selected")
    for n, cov, sel in frontier(0.40, sigma, gaming):
        print("  %2d      %.3f      %.3f" % (n, cov, sel))
    print()

import random

random.seed(11)
TRIALS = 1500
NS = (1, 2, 4, 8, 16, 32, 64)

def run_task(p, n, sigma, gaming):
    best_score, picked_correct, covered = None, False, False
    for _ in range(n):
        correct = random.random() < p
        covered = covered or correct
        if correct:
            mu = 1.0
        elif random.random() < gaming:
            mu = 1.6                 # wrong, but hits what the verifier rewards
        else:
            mu = 0.0
        score = mu + random.gauss(0.0, sigma)
        if best_score is None or score > best_score:
            best_score, picked_correct = score, correct
    return covered, picked_correct

def frontier(p, sigma, gaming):
    rows = []
    for n in NS:
        cov = sel = 0
        for _ in range(TRIALS):
            c, s = run_task(p, n, sigma, gaming)
            cov += c
            sel += s
        rows.append((n, cov / TRIALS, sel / TRIALS))
    return rows

for label, sigma, gaming in [
    ("sound verifier (no noise, no gaming)", 0.0, 0.0),
    ("noisy learned verifier (sigma=0.5)", 0.5, 0.0),
    ("noisy verifier, 3% of wrong answers game it", 0.5, 0.03),
]:
    print(label)
    print("   n   coverage   selected")
    for n, cov, sel in frontier(0.40, sigma, gaming):
        print("  %2d      %.3f      %.3f" % (n, cov, sel))
    print()

Read the three blocks against each other; each teaches a different lesson. With a sound verifier, selected accuracy equals coverage exactly — 0.41 at n=1, 0.97 by n=8, saturated by n=16. This is the regime that makes headlines, and it is available to you whenever an automatic checker exists. With a noisy verifier, the two curves separate: coverage is 0.98 at n=8 but you only ship 0.90, and closing the remaining gap takes another 8x compute. Verifier quality, not sample count, now sets your ceiling.

The third block is the important one. Selected accuracy rises to about 0.85 at n=16, then falls to 0.80 at 32 and 0.76 at 64, while coverage sits at 1.000 the whole time. Nothing about the generator got worse. What changed is that drawing more samples makes it more likely that at least one of them is a candidate that games the verifier, and argmax is precisely the operator that finds it. This is verifier over-optimization — the best-of-n analogue of reward hacking in RLHF, characterized by Gao, Schulman and Hilton (2023). Their information-theoretic framing is useful: best-of-n selection moves you away from the base policy by

KL_{bo n} = lo g n -

pythoneditable · runnable

IN, CACHED_IN, OUT = 3.0 / 1e6, 0.30 / 1e6, 15.0 / 1e6   # generator, per token
VERIFIER_IN = 0.25 / 1e6                                  # small scoring model
PROMPT, COMPLETION = 4000, 1200
VALUE_OF_A_SOLVE = 16.00      # what one extra correct answer is worth to you

MEASURED = [(1, 0.620), (2, 0.681), (4, 0.724),
            (8, 0.748), (16, 0.757), (32, 0.759)]

print(" n   acc     cost/task   cost/solved   marginal cost per extra solve")
prev_cost = prev_acc = None
for n, acc in MEASURED:
    gen = PROMPT * IN + (n - 1) * PROMPT * CACHED_IN + n * COMPLETION * OUT
    ver = n * (PROMPT + COMPLETION) * VERIFIER_IN
    cost = gen + ver
    marginal = "-"
    if prev_cost is not None:
        d = acc - prev_acc
        marginal = ("%.2f" % ((cost - prev_cost) / d)) if d > 0 else "inf"
    print("%2d   %.3f   %.4f      %.4f        %s"
          % (n, acc, cost, cost / acc, marginal))
    prev_cost, prev_acc = cost, acc

print()
print("Buy another doubling while marginal cost per extra solve < %.2f"
      % VALUE_OF_A_SOLVE)

IN, CACHED_IN, OUT = 3.0 / 1e6, 0.30 / 1e6, 15.0 / 1e6   # generator, per token
VERIFIER_IN = 0.25 / 1e6                                  # small scoring model
PROMPT, COMPLETION = 4000, 1200
VALUE_OF_A_SOLVE = 16.00      # what one extra correct answer is worth to you

MEASURED = [(1, 0.620), (2, 0.681), (4, 0.724),
            (8, 0.748), (16, 0.757), (32, 0.759)]

print(" n   acc     cost/task   cost/solved   marginal cost per extra solve")
prev_cost = prev_acc = None
for n, acc in MEASURED:
    gen = PROMPT * IN + (n - 1) * PROMPT * CACHED_IN + n * COMPLETION * OUT
    ver = n * (PROMPT + COMPLETION) * VERIFIER_IN
    cost = gen + ver
    marginal = "-"
    if prev_cost is not None:
        d = acc - prev_acc
        marginal = ("%.2f" % ((cost - prev_cost) / d)) if d > 0 else "inf"
    print("%2d   %.3f   %.4f      %.4f        %s"
          % (n, acc, cost, cost / acc, marginal))
    prev_cost, prev_acc = cost, acc

print()
print("Buy another doubling while marginal cost per extra solve < %.2f"
      % VALUE_OF_A_SOLVE)

The output tells a story no accuracy plot does. Going from n=1 to n=2 buys an extra solve for about 34 cents — trivially worth it. From 4 to 8 the price is 3.42 per extra solve, still comfortably under the 16-dollar value. From 8 to 16 it jumps to about 18.22 — just past break-even — and from 16 to 32 it is 164 dollars per extra solve, which is absurd. The accuracy curve is still rising at n=32; the economics stopped making sense at n=8. Ship 8, and note that the honest answer changes the moment someone revises the value of a solve.

7. Shipping It

Three refinements turn the pipeline above into something you would run on production traffic. Adaptive n first: a fixed n spends the same compute on the easy 80% of requests as on the hard 20%. Sample incrementally instead — draw 3, stop if they agree unanimously, otherwise draw more up to a cap. On typical traffic this recovers most of the accuracy of a large fixed n at a fraction of the average cost, because unanimous early agreement is both common and a genuine signal of an easy instance.

python

def adaptive_vote(sample_fn, min_n=3, max_n=16, agree_ratio=0.75):
    '''Draw until the leading answer is convincingly ahead, or the cap is hit.'''
    from collections import Counter
    got = []
    while len(got) < max_n:
        got.extend(sample_fn(min_n if not got else 2))
        counts = Counter(c.answer for c in got if c.answer is not None)
        if counts:
            top, k = counts.most_common(1)[0]
            if len(got) >= min_n and k / len(got) >= agree_ratio:
                return top, len(got)
    counts = Counter(c.answer for c in got if c.answer is not None)
    return (counts.most_common(1)[0][0] if counts else None), len(got)

Route by difficulty. The compute-optimal result from Lesson 1 says the right allocation depends on how hard the instance is. You rarely know that in advance, but you can proxy it: query length, retrieval score, a cheap classifier trained on past failures, or simply the disagreement rate of the first three samples. Send the easy bucket single-shot and reserve the wide sampling for the hard one.

Log everything the selector saw — all n candidates, their scores, the vote margin, and which one you returned. When the agent is wrong in production, that record is the difference between "the model failed" and "the model was right in candidate 5 and the verifier scored it 0.31", two completely different bugs with two completely different fixes. It also hands you, for free, a labeled dataset for training a better verifier — which is exactly where the next lesson goes.

1. The Machinery: Sample, Score, Select

2. Self-Consistency: Majority Vote Over Reasoning Paths

3. Where Majority Vote Does Not Apply

4. Best-of-N With a Verifier

5. The Accuracy-Versus-Compute Frontier

7. Shipping It

6. Dollars per Solved Task