Module 10. Search, verification, and test-time compute

• Adaptive: easy prompts receive one candidate and difficult prompts receive eight.
• Parallel: eight candidates are generated for a difficult prompt.
• Sequential: each candidate may use up to 2,000 tokens.
• Search: the two most promising prefixes are expanded further.

“Eight attempts” describes only one width parameter. It does not report candidate length, evaluator calls, expanded nodes, batching, latency, or monetary cost. A reproducible comparison should at least record generated tokens, generator passes, verifier calls, latency, and cost.

pass@32 = 0.98 says that at least one correct candidate is present in 98% of 32-candidate sets under the stated generator and correctness test. An output accuracy of 0.61 says that the ranker often fails to select the available correct candidate.

The generator has high coverage at this budget, while selection is a major bottleneck. The useful follow-up is conditional selection accuracy on sets that contain a correct candidate, together with comparisons against exact verification, voting, and simpler ranking rules. Calling 0.98 “system accuracy” would be wrong because the user receives one selected output, not the entire set.

No. Independent samples from a low-entropy distribution can repeat the same error. A small prompt-specific success probability, an inaccurate estimate of p, or pooling prompts with different p can also explain the discrepancy. Reused prefixes or search branches are possible dependence mechanisms, but must be established from the sampling protocol. Compare empirical coverage across repeated groups with the per-prompt iid prediction and its uncertainty.

Useful diagnostics include the number of unique canonical answers, pairwise semantic similarity, answer-cluster entropy, the mass of the largest cluster, and the gap between the empirical pass@N curve and the iid prediction from pass@1. No single diversity metric is sufficient because paraphrases can preserve the same error.

The wrong answer with probability 0.44 is the unique mode. As the number of iid samples grows, empirical frequencies converge to their probabilities, so plurality voting selects the systematic error with probability tending to one. Voting accuracy therefore tends to zero.

At the same time,

so pass@N for the correct answer tends to one. Candidate coverage and aggregation quality are different objects.

The teaching protocol has binary acceptance and uniform sampling among accepted candidates. With many samples, the probability of no accepted candidate vanishes, so success approaches the fraction of correct candidates among accepted ones.

A continuous scorer followed by an argmax is an extreme-value problem. Its behavior depends on the joint tails of true quality and score error. Increasing $N$ can select increasingly positive evaluator errors. The binary-uniform limit does not apply.

Possible explanations include proxy overoptimization, distribution shift in the winners, length/style shortcuts, and sampling noise in the independent evaluation.

A better protocol uses a held-out prompt set and independent evaluator, plots proxy and target curves on the same $N$ grid with uncertainty, audits length and style, performs blinded human review, defines stopping by the independent metric, and refreshes evaluator data with candidates from the new policy or search distribution.

The label estimates success under a particular continuation policy, decoding rule, horizon, and verifier:

It is not an eternal property of the prefix. Once the continuation policy changes, the distribution of futures and therefore the value can change. Store the policy version, decoding parameters, sample count, verifier, and labeling date.

Compare at equal generated-token budgets, generator passes, evaluator calls, latency or monetary cost, and context limits. Report pass@1, coverage, selected-answer quality, failures, tokens, latency, and cost. Strong baselines include repeated sampling, BoN, self-consistency, and sequential revision. “MCTS is better” is undefined without a resource constraint and target metric.

The sixth sample adds

These are coverage values. They do not specify the probability that a selector returns the successful candidate.

hence

The estimator corresponds to selecting ten elements without replacement from the already generated set of one hundred.

The acceptance probability is

Correctness among accepted candidates is

Correctness conditional on rejection is

The no-accept probability is

Fallback to the rejected pool gives

A fresh unverified fallback gives

For $q>0$, both converge to

Observing rejection changes the conditional correctness probability. The term $p$ is valid for a fresh independent draw, not for a candidate already known to have been rejected.

For $(0.34,0.33,0.20,0.13)$, the correct answer is the unique mode, so plurality accuracy tends to one, although convergence is slow because the gap is only 0.01.

For $(0.30,0.40,0.30)$, a wrong answer is the unique mode, so plurality accuracy tends to zero.

For $(0.9,0.7,0.8)$:

Adding ten scores of 0.9 gives

The product introduces a length effect unless the scores have a compatible conditional-probability semantics.

Greedy marginal allocation from the initial $(1,1,1)$ yields

The mean coverage is

For costs,

so

This is a monetary break-even calculation only.

from __future__ import annotations

from collections.abc import Iterable, Sequence
import math
import numpy as np


def pass_at_n(p: float, n: int) -> float:
    p = float(p)
    if not math.isfinite(p) or not 0.0 <= p <= 1.0:
        raise ValueError("p must lie in [0, 1]")
    if isinstance(n, bool) or int(n) != n or int(n) <= 0:
        raise ValueError("n must be a positive integer")
    n = int(n)
    if p == 0.0:
        return 0.0
    if p == 1.0:
        return 1.0
    return float(-np.expm1(n * np.log1p(-p)))


def aggregate_pass_curve(ps: Sequence[float], budgets: Iterable[int]) -> np.ndarray:
    probabilities = np.asarray(ps, dtype=np.float64)
    budgets = list(budgets)
    if probabilities.ndim != 1 or probabilities.size == 0:
        raise ValueError("ps must be non-empty")
    if not np.isfinite(probabilities).all() or np.any((probabilities < 0) | (probabilities > 1)):
        raise ValueError("every probability must lie in [0, 1]")
    if not budgets:
        raise ValueError("budgets must be non-empty")
    return np.asarray(
        [np.mean([pass_at_n(float(p), int(n)) for p in probabilities]) for n in budgets],
        dtype=np.float64,
    )

log1p and expm1 improve numerical behavior for small $p$ and large $N$.

from __future__ import annotations
from collections.abc import Sequence
import numpy as np


def plurality_accuracy_mc(
    probabilities: Sequence[float],
    k: int,
    *,
    correct_index: int = 0,
    trials: int = 100_000,
    seed: int = 10,
) -> float:
    p = np.asarray(probabilities, dtype=np.float64)
    if p.ndim != 1 or p.size < 2:
        raise ValueError("at least two categories are required")
    if not np.isfinite(p).all() or np.any(p < 0) or not np.isclose(p.sum(), 1.0):
        raise ValueError("probabilities must form a distribution")
    if isinstance(k, bool) or int(k) != k or int(k) <= 0:
        raise ValueError("k must be a positive integer")
    if isinstance(trials, bool) or int(trials) != trials or int(trials) <= 0:
        raise ValueError("trials must be a positive integer")
    if not 0 <= int(correct_index) < p.size:
        raise ValueError("correct_index is out of range")

    rng = np.random.default_rng(seed)
    counts = rng.multinomial(int(k), p, size=int(trials))
    correct = 0
    for row in counts:
        winners = np.flatnonzero(row == row.max())
        selected = int(rng.choice(winners))
        correct += selected == int(correct_index)
    return correct / int(trials)

np.argmax returns the first maximal index. If the correct answer is stored at index 0, every tie artificially raises accuracy; under another index it lowers accuracy. That is an array-layout artifact, not a voting protocol.

from __future__ import annotations
import math


def binary_verifier_success(
    n: int,
    p_correct: float,
    true_positive_rate: float,
    false_positive_rate: float,
    *,
    fallback_mode: str = "rejected_pool",
) -> dict[str, float]:
    if isinstance(n, bool) or int(n) != n or int(n) <= 0:
        raise ValueError("n must be a positive integer")
    values = [float(p_correct), float(true_positive_rate), float(false_positive_rate)]
    if any((not math.isfinite(v)) or not 0.0 <= v <= 1.0 for v in values):
        raise ValueError("probabilities must lie in [0, 1]")
    if fallback_mode not in {"rejected_pool", "fresh_unverified"}:
        raise ValueError("unknown fallback mode")

    p, tpr, fpr = values
    q = p * tpr + (1.0 - p) * fpr
    accepted_precision = p if q == 0.0 else p * tpr / q
    rejected_precision = p if q == 1.0 else p * (1.0 - tpr) / (1.0 - q)
    no_accept = (1.0 - q) ** int(n)
    fallback = rejected_precision if fallback_mode == "rejected_pool" else p
    success = (1.0 - no_accept) * accepted_precision + no_accept * fallback
    return {
        "q": q,
        "accepted_precision": accepted_precision,
        "rejected_precision": rejected_precision,
        "no_accept": no_accept,
        "fallback_success": fallback,
        "success": success,
    }

When q == 1, the conditional distribution of rejected candidates is undefined, but the fallback event has zero probability. The returned convention cannot affect success.

from __future__ import annotations

from collections.abc import Sequence
import numpy as np


def process_score(step_scores: Sequence[float], method: str) -> float:
    values = np.asarray(step_scores, dtype=np.float64)
    if values.ndim != 1 or values.size == 0:
        raise ValueError("step_scores must be non-empty")
    if not np.isfinite(values).all() or np.any((values < 0) | (values > 1)):
        raise ValueError("step scores must lie in [0, 1]")
    method = method.lower()
    if method == "min":
        return float(values.min())
    if method == "mean":
        return float(values.mean())
    if method == "product":
        return float(values.prod())
    if method == "last":
        return float(values[-1])
    if method == "log_product":
        if np.any(values == 0):
            return float("-inf")
        return float(np.log(values).sum())
    raise ValueError("unknown aggregation method")

Log products avoid numerical underflow but do not make an unjustified probabilistic interpretation valid.

from __future__ import annotations

from collections.abc import Sequence
import numpy as np


def proxy_overoptimization_curve(
    budgets: Sequence[int],
    *,
    trials: int = 10_000,
    seed: int = 202_610,
) -> tuple[np.ndarray, np.ndarray]:
    budgets = np.asarray(budgets, dtype=np.int64)
    if budgets.ndim != 1 or budgets.size == 0 or np.any(budgets <= 0):
        raise ValueError("budgets must be positive integers")
    rng = np.random.default_rng(seed)
    maximum = int(budgets.max())
    useful = rng.normal(size=(trials, maximum))
    spurious = rng.normal(size=(trials, maximum))
    proxy = useful + spurious
    goal = useful - np.maximum(spurious - 1.0, 0.0) ** 2
    rows = np.arange(trials)
    proxy_means, goal_means = [], []
    for n in budgets:
        selected = np.argmax(proxy[:, : int(n)], axis=1)
        proxy_means.append(proxy[rows, selected].mean())
        goal_means.append(goal[rows, selected].mean())
    return np.asarray(proxy_means), np.asarray(goal_means)

This reference uses a shared candidate pool, so the selected proxy maximum is nondecreasing as the prefix grows in every trial. With independent pools, monotonicity holds in expectation; individual sample means can fluctuate. Under this reference protocol (trials=10000, seed=202610, and the stated grid), the observed goal peaks at $N=32$; another valid sampling layout can have a different peak. The open checks cover shape, finiteness, reproducibility, and use of the seed. Also verify the goal formula and candidate selection on a few hand-calculated pools; these checks alone do not establish algorithmic correctness.

from __future__ import annotations

from collections.abc import Sequence
import numpy as np


def allocate_budget_greedy(
    ps: Sequence[float],
    total_samples: int,
    *,
    minimum_per_prompt: int = 1,
) -> np.ndarray:
    p = np.asarray(ps, dtype=np.float64)
    if p.ndim != 1 or p.size == 0:
        raise ValueError("ps must be non-empty")
    if not np.isfinite(p).all() or np.any((p < 0) | (p > 1)):
        raise ValueError("probabilities must lie in [0, 1]")
    minimum = int(minimum_per_prompt)
    if minimum < 0 or minimum != minimum_per_prompt:
        raise ValueError("minimum_per_prompt must be a non-negative integer")
    if total_samples < minimum * p.size:
        raise ValueError("budget is smaller than the required minimum")
    allocation = np.full(p.size, minimum, dtype=np.int64)
    for _ in range(int(total_samples) - minimum * p.size):
        gains = p * np.power(1.0 - p, allocation)
        allocation[int(np.argmax(gains))] += 1
    return allocation

The greedy result is optimal for the stated independent curves with diminishing discrete marginal gains. Real LLM systems may violate every one of those assumptions.