Test-Time Compute: Spending Inference Budget on Search

For one prompt $x$, let the base model define a finite distribution over complete candidate traces. Each trace has hidden task correctness and a verifier score:

Best-of-$N$ draws $N$ independent traces from $p$ and returns the sampled trace with the highest verifier score. Assume verifier scores are distinct and sort traces from lowest to highest verifier score, so $s_1 < \cdots < s_K$:

Where the rank formula comes from. Fix a verifier and number the traces by its score, lowest first. $F_k$ is the cumulative rank: the probability that a single draw ranks at or below trace $k$. The returned trace ranks at or below $k$ exactly when every one of the $N$ draws does. If the draws are independent, those $N$ events multiply, so the returned trace ranks at or below $k$ with probability $F_k^N$. Subtracting $F_{k-1}^N$, the probability that every draw ranks strictly below $k$, leaves $F_k^N-F_{k-1}^N$, the probability that trace $k$ is returned. Here $k$ is a position in one verifier's order, not a trace's identity: clean correct is rank 4 of 4 under the clean verifier and rank 3 under the noisy one, where the exploit takes rank 4. Coverage uses the same assumption through the complement: with $c=\sum_i p_i u_i$ the probability that one draw is correct, all $N$ draws miss with probability $(1-c)^N$.

Three quantities stay distinct. An event probability, such as $p_ip_j$ for an ordered pair, says how often one particular set of draws occurs. A cumulative rank $F_k$ describes a single draw under a single verifier. Selected correctness $A(N)$ adds up the event probabilities of every outcome whose returned trace is correct. Coverage and $A(N)$ are unconditional: they average over every batch of draws, including batches with no correct trace. Conditional on a batch containing a correct trace, the noisy verifier at $N=2$ returns one with probability $0.3024/0.3276=12/13\approx0.923$.

The worked case, $N=2$. The four traces are common wrong, plausible slip, clean correct and rare exploit, with $p=(0.50,0.25,0.18,0.07)$; only clean correct has $u=1$, so $c=0.18$ and coverage is $1-0.82^2=0.3276$ for either verifier. The clean verifier ranks clean correct highest, with $F=0.82$ just below it and $F=1$ at it, so $A(2)=1-0.82^2=0.3276$: every outcome that covers a correct trace returns it. The noisy verifier puts rare exploit above it, with $F=0.75$ below and $F=0.93$ at it, so $A(2)=0.93^2-0.75^2=0.3024$. The difference, $0.0252=2\times0.18\times0.07$, is the event probability of the worked pair in its two orders. They are the only outcomes of the sixteen whose returned trace depends on the verifier, because the exploit's score is the only score that changes. Enumerating the sixteen outcomes directly gives the same three numbers; the second code block below does exactly that.

To connect back to process reward models, a trace score might be an additive step score:

Treat this as a ranking score, not a calibrated probability of correctness. Sum-vs-mean aggregation, length normalization, and distribution shift can all change which traces receive high verifier score. This generic within-trace sum is not the exact convention of either paper: Lightman et al. multiply step-level probabilities, counting neutral steps as positive (§2.6, Appendix F.2), and Snell et al. reduce each solution to its final-step prediction, then sum those predictions across solutions that reach the same final answer (§5.1). The sum here runs over the steps of one trace, not over candidates, and the page's four trace scores are totals chosen by hand, not reconstructed from step-level data.

The expected selected verifier score is

Selected correctness and sampled-correct coverage can be very different. Sampling a correct trace is coverage. Returning it is selection. More samples can make $S(N)$ rise while $A(N)$ falls if the highest-scoring trace is a verifier error.

A simple cost model is

Here $N$ is only a teaching proxy for inference budget. Real serving cost also depends on generation length, verifier cost, batching, latency, and traffic volume.

Boundaries

One draw. At $N=1$ there is nothing to choose between: $A(1)=c=0.18$ under any verifier, and selected correctness equals coverage. A verifier matters only once $N\ge 2$.

Ties. The rank formula assumes distinct scores. With ties, which trace is returned depends on a tie-break rule, and that rule must be stated before $A(N)$ is defined.

Dependent draws. Both $F_k^N$ and $(1-c)^N$ come from multiplying $N$ probabilities, which is exactly the independence assumption. Suppose instead that the second attempt is a copy of the first, as when a harness reuses a cached output. Each attempt is still correct with probability $c$, but the two fail together:

For a code patch that passes with probability $0.5$, two copies cover a passing patch with probability $0.5$, not $1-0.5^2=0.75$. No verifier can repair this, because a verifier can only return an attempt that was sampled. Positively correlated attempts land between the two cases; attempts forced to differ can do better than independent ones. A success rate averaged over many prompts needs the same care. Suppose draws are independent given the prompt, but the per-prompt success probability $p$ differs between prompts, with mean $\bar p$. Because $1-(1-p)^N$ is concave in $p$, the average coverage is at most $1-(1-\bar p)^N$, with equality when every prompt has the same $p$ or when $N=1$. The formula with an averaged rate is then an upper bound, not the coverage.

Choosing within a budget

In abstract units of a single compute resource, generating a trace costs $g=1$ and scoring one trace costs $s_{\text{noisy}}=1$ or $s_{\text{clean}}=2$; every trace in a scored plan is scored. A scored plan with ranker $v$ and $n$ draws, $2\le n\le128$, costs and is correct with probability

where $h_v$ is a one-time setup charge, zero unless stated. One unscored draw costs $g=1$ and is correct with probability $c=0.18$; with a single draw there is nothing to choose between, so no scoring is charged. That makes $1+127+127=255$ actions. Within a budget $B$ the decision is

taken over every affordable action, with exact ties broken by lower cost and then by plan ID. If nothing is affordable ($B<1$), no answer is produced, which is not an answer with zero accuracy. The objective is correctness within the budget, not correctness per unit, and the budget is a limit: unused units are allowed. Every action affordable at $B$ stays affordable at $B+1$, so the best attainable correctness never decreases as $B$ grows, even though the preferred ranker can switch: clean $n=3$ at $B=9$ ($0.448632$), noisy $n=5$ at $B=10$ ($0.4583836818$), clean $n=4$ at $B=12$ ($0.54787824$). At $B=14$ noisy $n=7$ is affordable but gives $0.46821698388882$, below noisy $n=6$. That is a reason not to buy the larger batch, decided before buying it; it is not a rule for stopping after seeing samples.

A one-time setup charge $h_{\text{clean}}=4$ on this prompt, a hypothetical charge chosen to show what omitted overhead can do, makes clean $n=4$ cost 16 and clean $n=2$ cost 10, so at $B=12$ noisy $n=6$ wins. No candidate, probability or score changed. Snell et al. (§3.2) estimate prompt difficulty from 2,048 samples per question, exclude that cost from their comparisons and discuss reusing the estimation work during inference; genuinely reused work counts once, neither twice nor zero. Their §5.3 charges lookahead search $N(k+1)$ generation-equivalents. Neither is a measured price, and the four units here neither estimate the paper's excluded overhead nor reverse its findings.

Two operations that must stay separate

Within one solution, a reduction turns step scores $r_1,\dots,r_T$ into one weight: the last step $r_T$, the product $\prod_t r_t$, or the sum $\sum_t r_t$, which is the additive score of the third equation above. For the example step scores $P=(0.10,0.90)$ and $Q=(0.80,0.80)$, the last step ranks $P$ first ($0.90$ against $0.80$), while the product ($0.09$ against $0.64$) and the sum ($1.00$ against $1.60$) rank $Q$ first.

Across solutions, a rule returns one answer from a batch of candidates $j$ with final-answer keys and weights $w_j$. Returning the highest single candidate takes $\arg\max_j w_j$. Summing by final answer takes

over distinct candidate IDs; a repeated ID is rejected rather than counted twice. In batch M1 (a1: A, 0.60; a2: A, 0.60; b1: B, 0.90) the highest candidate answers B, while $W(A)=1.20>W(B)=0.90$. In M2 (a1: A, 0.90; b1 and b2: B, 0.60 each) the two rules swap. Squaring M1's weights keeps every candidate's order but gives $W(A)=0.72<W(B)=0.81$, so grouped sums depend on magnitudes, not only on order. Totals above 1 are sums of weights, not probabilities. Ties go to the smallest candidate ID or answer key, a teaching convention rather than either paper's, and neither rule reads the correct answer, which is used only to grade the result. The cumulative-rank formula above describes the highest-trace rule; it does not become a formula for grouped sums.

Snell et al. (§5.1, Appendix D) train their verifier on Monte Carlo continuation returns under the base model's sampling policy, reduce each solution to its final-step prediction and sum by final answer. Lightman et al. (§2.1, §2.6, Appendix F.1–F.2) train on step labels, count neutral steps as positive in their main convention, multiply step probabilities, and evaluate the highest-scored solution against a separate final-answer grade. The targets differ, so scores in $[0,1]$ from the two are not interchangeable. M1 and M2 hold the weights fixed and change only the across-solution rule, so neither is a complete implementation of either paper.

When the ranker itself is uncertain

Replace the known-clean ranker with an unvalidated proposed ranker at the clean price, with $B=12$ and no setup charge. For a whole batch, chosen once and independently of the draws, it uses the clean ordering with probability $r$ and the noisy ordering otherwise, so

Against noisy $n=6$ ($0.469011667824$), both at cost 12, the proposed plan is better exactly when $r>r^\star\approx0.321475613563$. Over the assumed range $r\in[0.2,0.6]$ it runs from $0.454892256$ to $0.501385248$, so the stated information does not identify a better plan. The range is not a confidence interval or a measurement. For a given $r$ the formula gives expected correctness conditional on that $r$; at $r=0.4$, for example, it is $0.478138752$. The range supplies no distribution or mean for the unknown $r$, so it does not identify expected correctness averaged over that uncertainty, and its midpoint is a what-if value, not an estimate of $r$. Were the known-clean plan still available, its $0.54787824$ would beat both options for every allowed $r\in[0.2,0.6]$, and nothing would be unresolved; the proposed plan reaches it only at $r=1$, outside that range, where the two are equal.

Matched candidate pools

The source-to-test investigation uses a separate finite pool of six slots: A and B have correct final answers, C and D have wrong answers, E contains no answer and F is missing. The two score columns are invented. They are neither probabilities nor measurements from a model.

Let $n\in\{1,2\}$ be the number of distinct slots drawn. An ordered prefix $d=(i_1,\ldots,i_n)$ samples uniformly without replacement from a shuffled pool. Thus the set $\Omega_n$ contains 6 prefixes when $n=1$ and $6\cdot5=30$ when $n=2$. This is different from the independent draws in the earlier model. Remove E and F only after the draw; they still consume a slot. Among the remaining candidates, selector $a_r(d)$ returns the highest score under rule $r$, keeping the first in sampled order on a tie. It returns no answer for an empty eligible set. Let $y(a)$ be 1 for a correct final answer and 0 otherwise, including no answer. Selection never reads $y$.

These are exact averages over a finite, fully specified calculation, not estimates from 30 independent observed problems. At $n=2$, the baseline succeeds in 10/30 prefixes and the changed ranking in 18/30, giving $\Delta=8/30$. Both see a correct candidate in 18/30 prefixes. Neither returns an answer in 2/30. For example, on (A,C) the baseline chooses C and the changed ranking chooses A; the candidate availability did not change.

The counts have a direct check: 12 ordered pairs contain neither A nor B, so $30-12=18$ contain a correct answer. Baseline succeeds only on A/B together (two orders), or on one of A/B paired with E/F (eight orders): $2+8=10$. The changed scores rank both correct candidates above both wrong ones, so all 18 available correct answers are selected. E/F together gives the two empty orders. Availability of any eligible answer is 28/30, a different quantity from availability of a correct answer.

Removing E/F before sampling defines a conditional question over four answered candidates. Its $n=2$ denominator is $4\cdot3=12$, with 2/12 and 10/12 successes. A percentage difference between the two sampling orders cannot isolate a ranking change. Squaring these nonnegative baseline scores preserves their order and every selection; a different score magnitude alone is not evidence of a better selector. A controlled comparison changes the scoring rule on the same prefixes, while preserving eligibility, ties and grading. Filtering first conditions on all sampled slots being answered. Merely dropping the two empty original outcomes instead would give 10/28 and 18/28; it would not give the filter-first results. A zero paired difference alone does not imply unchanged choices: wins and losses can cancel.

This code uses the same four-trace model as the demo. With a clean verifier, more samples improve selected correctness. With a noisy verifier, selected verifier score improves while true correctness eventually falls.

def selected_distribution(candidates, n):
    ranked = sorted(candidates, key=lambda item: item["score"])
    cumulative = 0.0
    selected = {}
    for item in ranked:
        p = item["prior"]
        next_cumulative = cumulative + p
        selected[item["id"]] = next_cumulative ** n - cumulative ** n
        cumulative = next_cumulative
    return selected

def expected(candidates, selected, key):
    return sum(selected[item["id"]] * item[key] for item in candidates)

def scored(candidates, mode):
    return [{**item, "score": item[f"{mode}_score"]} for item in candidates]

def expected_accuracy(candidates, n, mode):
    rows = scored(candidates, mode)
    return expected(rows, selected_distribution(rows, n), "correct")

def expected_score(candidates, n, mode):
    rows = scored(candidates, mode)
    return expected(rows, selected_distribution(rows, n), "score")

candidates = [
    {"id": "common_wrong", "prior": 0.50, "correct": 0, "clean_score": -2.0, "noisy_score": -2.0},
    {"id": "plausible_slip", "prior": 0.25, "correct": 0, "clean_score": -0.3, "noisy_score": -0.3},
    {"id": "clean_correct", "prior": 0.18, "correct": 1, "clean_score": 1.8, "noisy_score": 1.8},
    {"id": "rare_exploit", "prior": 0.07, "correct": 0, "clean_score": 0.2, "noisy_score": 2.6},
]

clean_1 = expected_accuracy(candidates, 1, "clean")
clean_32 = expected_accuracy(candidates, 32, "clean")
noisy_1 = expected_accuracy(candidates, 1, "noisy")
noisy_64 = expected_accuracy(candidates, 64, "noisy")

assert clean_32 > clean_1
assert noisy_64 < noisy_1
assert expected_score(candidates, 64, "noisy") > expected_score(candidates, 1, "noisy")
print(round(clean_32, 3), round(noisy_64, 3))

The same functions give the worked case. This check enumerates all sixteen ordered outcomes of two independent draws without using the closed form, then compares:

from itertools import product

def enumerate_outcomes(candidates, n, mode):
    rows = scored(candidates, mode)
    totals = {"coverage": 0.0, "selected_correct": 0.0}
    for draws in product(rows, repeat=n):
        probability = 1.0
        for item in draws:
            probability *= item["prior"]  # independent draws: probabilities multiply
        returned = max(draws, key=lambda item: item["score"])
        totals["coverage"] += probability * any(item["correct"] for item in draws)
        totals["selected_correct"] += probability * returned["correct"]
    return totals

clean = enumerate_outcomes(candidates, 2, "clean")
noisy = enumerate_outcomes(candidates, 2, "noisy")
assert abs(clean["coverage"] - 0.3276) < 1e-12 and abs(noisy["coverage"] - 0.3276) < 1e-12
assert abs(clean["selected_correct"] - 0.3276) < 1e-12
assert abs(noisy["selected_correct"] - 0.3024) < 1e-12
assert abs(noisy["selected_correct"] - expected_accuracy(candidates, 2, "noisy")) < 1e-12
print(round(clean["selected_correct"] - noisy["selected_correct"], 4))  # 0.0252

# A copied second attempt adds no coverage: the complement rule needs independence.
p_patch = 0.5
independent = 1 - (1 - p_patch) ** 2  # 0.75
copied = 1 - (1 - p_patch)            # 0.5: both attempts fail together
print(independent, copied)

The budget and replacement calculations reuse the same expected_accuracy. Separate fixed-batch selectors reproduce the two aggregation rules; they return an answer for a given batch and do not estimate either rule's expected accuracy. This check enumerates all 255 actions, compares every affordable one at each budget, runs both selectors on the example batches and recomputes the crossover values shown on the page:

SCORE_COST = {"noisy": 1, "clean": 2}  # abstract units; generating a trace costs 1

def actions(clean_setup=0):
    plans = [{"id": "direct", "n": 1, "cost": 1, "correct": 0.18}]
    for ranker in ("clean", "noisy"):
        setup = clean_setup if ranker == "clean" else 0  # once per prompt, not per trace
        for n in range(2, 129):
            plans.append({"id": f"score-{ranker}-{n:03d}", "n": n,
                          "cost": n * (1 + SCORE_COST[ranker]) + setup,
                          "correct": expected_accuracy(candidates, n, ranker)})
    return plans

def best_within(budget, clean_setup=0):
    feasible = [p for p in actions(clean_setup) if p["cost"] <= budget]
    if not feasible:
        return None  # nothing is returned, which is not an answer with zero accuracy
    return min(feasible, key=lambda p: (-p["correct"], p["cost"], p["id"]))

assert len(actions()) == 255 and best_within(0) is None
best_at = {1: "direct", 6: "score-noisy-003", 9: "score-clean-003", 10: "score-noisy-005",
           12: "score-clean-004", 14: "score-clean-004"}
assert all(best_within(b)["id"] == plan for b, plan in best_at.items())
assert best_within(12, clean_setup=4)["id"] == "score-noisy-006"
best = [best_within(b) for b in range(1, 25)]
assert all(a["correct"] <= b["correct"] for a, b in zip(best, best[1:]))

def check_batch(batch):
    ids = [cid for cid, _, _ in batch]
    if not batch or len(ids) != len(set(ids)):
        raise ValueError("a batch needs candidates with distinct IDs")  # a repeated ID is ambiguous
    if not all(0.0 <= w <= 1.0 for _, _, w in batch):  # NaN fails every comparison
        raise ValueError("each candidate weight must lie in [0, 1]")

def highest_individual(batch):
    check_batch(batch)
    return min(batch, key=lambda c: (-c[2], c[0]))[1]  # ties: smallest candidate ID

def sum_by_answer(batch):
    check_batch(batch)
    totals = {}
    for cid, answer, weight in sorted(batch):  # sum in candidate-ID order; totals may exceed 1
        totals[answer] = totals.get(answer, 0.0) + weight
    return min(totals, key=lambda a: (-totals[a], a))  # ties: smallest answer key

M1 = [("a1", "A", 0.60), ("a2", "A", 0.60), ("b1", "B", 0.90)]
M2 = [("a1", "A", 0.90), ("b1", "B", 0.60), ("b2", "B", 0.60)]
M1_squared = [(cid, answer, w * w) for cid, answer, w in M1]
print([(highest_individual(m), sum_by_answer(m)) for m in (M1, M2, M1_squared)])
# [('B', 'A'), ('A', 'B'), ('B', 'B')]

a_clean4 = expected_accuracy(candidates, 4, "clean")
a_noisy4 = expected_accuracy(candidates, 4, "noisy")
a_noisy6 = expected_accuracy(candidates, 6, "noisy")
crossover = (a_noisy6 - a_noisy4) / (a_clean4 - a_noisy4)
low, high = (r * a_clean4 + (1 - r) * a_noisy4 for r in (0.2, 0.6))
print(round(crossover, 12), round(low, 9), round(high, 9))  # 0.321475613563 0.454892256 0.501385248

A partial patch record

The optional patch-record exercise changes the evidence available to the reader. These two stored patches and their costs are a separate example, not additional traces in the four-trace distribution above. The function below constructs records from supplied grades; it does not execute patches or tests. False means a test failed; None means no grade exists. Selection reads only ranking scores. The two compatible completions are not assigned probabilities.

PATCH_SCORES = {"A": 0.91, "B": 0.63}
PATCH_GENERATION_COST = 2
PATCH_SCORING_COST = 1
PATCH_TEST_COST = 1
PATCH_PLAN_COST = 2 * PATCH_GENERATION_COST + 2 * PATCH_SCORING_COST + PATCH_TEST_COST

def patch_record(budget, supplied_grades):
    # A whole-plan preflight: no partial generation when the plan cannot fit.
    if budget < PATCH_PLAN_COST:
        return {"candidate_ids": [], "scores": {}, "returned": None,
                "returned_grade": None, "spent": 0}
    returned = max(PATCH_SCORES, key=PATCH_SCORES.get)  # scores, never grades
    return {"candidate_ids": list(PATCH_SCORES), "scores": dict(PATCH_SCORES),
            "returned": returned, "returned_grade": supplied_grades[returned],
            "spent": PATCH_PLAN_COST}

patch_complete_grades = [{"A": False, "B": True}, {"A": False, "B": False}]
patch_records = [patch_record(9, grades) for grades in patch_complete_grades]
assert patch_records[0] == patch_records[1]  # same visible record, different availability
print([any(grades.values()) for grades in patch_complete_grades])  # [True, False]
patch_remaining = 9 - patch_records[0]["spent"]
assert PATCH_TEST_COST <= patch_remaining < PATCH_PLAN_COST
print(patch_records[0]["spent"] + PATCH_TEST_COST, patch_remaining - PATCH_TEST_COST)  # 8 1
print(patch_record(6, patch_complete_grades[0]))
# {'candidate_ids': [], 'scores': {}, 'returned': None, 'returned_grade': None, 'spent': 0}

Testing stored B would distinguish these completions for this batch. The code supplies both possible grades to check the logic; the observation record exposes only the grade of the returned patch. It estimates no success rate or future policy value. Compare the same separation of search record and missing answer key.

A matched-pool selection check

This standalone Python program enumerates the same finite prefixes as the source-to-test section. It needs only the standard library. The public PRM800K evaluation code is the source for the sampling and selection procedure; the following program, its six slots and paired comparison are our own. Running it repeats this small calculation, not the published model evaluation. Preserve the code, ordered pool, scores and grades, $n$, filtering order, tie rule and exact count criterion to repeat this result.

from itertools import permutations

# id, answer, baseline score, changed score. F is a missing slot.
POOL = (("A", "right", .30, .90), ("B", "right", .40, .80),
        ("C", "wrong-c", .95, .70), ("D", "wrong-d", .60, .20),
        ("E", None, 1., 1.), ("F", None, None, None))
GRADES = {"A": True, "B": True, "C": False, "D": False,
          "E": False, "F": False}

def inspect(pool=POOL, n=2, before=False, monotone=False, grades=GRADES):
    # A small finite pool: up to six slots; one or two drawn.
    if n not in (1, 2) or not 1 <= len(pool) <= 6:
        raise ValueError("Use one or two draws from at most six slots")
    if monotone:
        scores = [s[2] for s in pool if s[1] is not None]
        if any((a < b) != (a*a < b*b) for a in scores for b in scores):
            raise ValueError("Squared scores lose floating-point ordering")
    universe = [s for s in pool if s[1] is not None] if before else pool
    if len(universe) < n:
        raise ValueError("Not enough slots")
    traces = []
    for drawn in permutations(universe, n):
        retained = [s for s in drawn if s[1] is not None]
        # max keeps the first in this sampled order on a tie.
        base = max(retained, key=lambda s: s[2]) if retained else None
        changed = (max(retained, key=lambda s: s[2]**2 if monotone else s[3])
                   if retained else None)
        traces.append(dict(
            drawn=[s[0] for s in drawn], eligible=[s[0] for s in retained],
            baseline=base[0] if base else None,
            changed=changed[0] if changed else None,
            baselineCorrect=bool(base and grades[base[0]]),
            changedCorrect=bool(changed and grades[changed[0]]),
            covered=any(grades[s[0]] for s in retained)))
    b = sum(r["baselineCorrect"] for r in traces)
    c = sum(r["changedCorrect"] for r in traces)
    return dict(traces=traces, total=len(traces), baselineCorrect=b,
                changedCorrect=c, covered=sum(r["covered"] for r in traces),
                empty=sum(not r["eligible"] for r in traces),
                changedOnly=sum(r["changedCorrect"] and not r["baselineCorrect"] for r in traces),
                baselineOnly=sum(r["baselineCorrect"] and not r["changedCorrect"] for r in traces),
                difference=c-b)

if __name__ == "__main__":
    for before in (False, True):
        for monotone in (False, True):
            r = inspect(before=before, monotone=monotone)
            print("filter before:", before, "squared scores:", monotone,
                  "correct:", r["baselineCorrect"], r["changedCorrect"],
                  "out of", r["total"], "paired difference:", r["difference"])

The exact released source uses an explicit None eligibility test. Its first-in-sampled-order tie rule is preserved here. The source CLI evaluates one method per invocation with fresh shuffles; applying both to the same prefixes is our added control. We substitute six invented slots and exhaustive enumeration for the released scored corpus and random subsampling, and we do not train, generate, score or regrade model solutions. The source artifact's represented-problem denominator is different from this program's prefix count. The source checks its stored is_correct labels; it does not run an answer grader. Its absent answer key can fall back to given_answer, while an explicit null cannot; the example here uses nonempty strings or null. For these nonnegative example scores, squaring preserves order in both real and floating-point arithmetic. The program rejects an ordering lost through floating-point rounding or underflow instead of calling a new tie equivalent.

This page ranks complete traces with one fixed verifier and a fixed $N$. Practical systems decide how many samples each prompt deserves, combine verifier scores with majority voting, and search over partial traces instead of complete ones. Brown et al. (2024) report coverage rising with the number of samples over four orders of magnitude across tasks and models, while picking among samples by majority vote or a reward model plateaus beyond several hundred samples in domains without an automatic verifier. Snell et al. (2024) find that the best way to spend inference compute depends on how hard the prompt is for the model. How to allocate compute when the verifier is itself imperfect, and how to tell when it is, remain open.