Token LabSearch

FRONTIER / RESEARCH TO PRACTICE

Test-time compute: search, verification and budgets

Prerequisites: probability, evaluation and inference cost. Learn when more attempts help and when a verifier becomes the bottleneck.

Study guide & lesson outlineLEARNING CONTRACT

Understand → implement → investigate

Goal: explain the mechanism in this lesson, reproduce one example and test a failure case. Reading alone does not mark mastery.

Prerequisite route →Related implementation practice →

Mechanism & assumptions

Inference-time scaling spends additional computation on a fixed model through candidate generation, revision or search. The cited paper studies prompt-dependent allocation rather than a universal rule that more tokens always help. Separate proposal quality from selection quality: an oracle that can identify any correct answer gives an upper bound that a learned verifier may not reach. Correlated candidates, reward exploitation and slow verification can erase the apparent gain. Budget generation, verification and retries together; match wall time as well as tokens when comparing methods.

Text / 原始公式
Oracle coverage = 1 − (1 − p)^N  [independent attempts]
Total cost = N·C_generation + C_verification(N)
Budget choice: maximize expected utility subject to cost ≤ B

Worked example

For independent success probability , gives coverage 0.5904; gives 0.83222784. These are probabilities that at least one correct answer exists, not that your selector returns it. If the selector finds a correct answer only 80% of the time conditional on one existing, selected accuracy at is 0.47232 under this simplified model. Perfectly correlated attempts retain coverage 0.2 regardless of N.

Implementation exercise

On a held-out problem set, compare single-shot, majority vote and verifier-selected candidates at budgets 1/2/4/8. Save every candidate and score. Report oracle coverage, selected accuracy, verifier mistakes and latency. Keep difficulty bins fixed before evaluation; do not allocate extra budget based on hidden test answers. Add a deliberately misleading high-scoring candidate to audit reward exploitation.

Deliver code, fixed seeds, raw results and one counterexample. These are experiment specifications, not executed GPU benchmarks.

Why can best-of-N get worse as N grows?

A noisy or exploitable scorer increasingly selects extreme scoring errors. Candidate quality and score calibration can shift with N. Audit selected failures and use a separately validated verifier; more search is not evidence of improved correctness.

arXiv ↗ · PDF ↗

Original teaching examples; sources checked October 2026. These are foundational mechanisms relevant to engineering, not a claim to cover every latest model.

Related prerequisite / next lesson →

AI/LM curriculum & checkpoints →Frontier index →
MATHEMATICAL REVIEW · 2026-10-26

Assumptions, implementation & acceptance

C_verification(N) is total verification cost for N candidates. Oracle coverage assumes independent attempts with equal success probability; selected accuracy further depends on the verifier.

Formula conditions, units and worked arithmetic reviewed. The implementation isolates one numerical mechanism; it does not train a policy or control real hardware.

Fixed model → N candidate attempts → At least one correct: oracle coverage → Verifier selects one candidate → Selected accuracy + total budget
Mechanism map: follow the transformations from top to bottom.

Before running: predict a boundary case

Perfectly correlated attempts retain .2 coverage; the IID formula cannot be reused.

Hint: isolate the assumption

Keep the baseline input fixed, change one parameter or boundary, and compare both the numerical result and the claimed units. A passing example verifies this fixture only.

Minimal executable example

Save the example and linked modules in one folder. Use Node.js 22 or newer, then run node test-time-compute.mjs. No third-party runtime dependencies.

const solve=()=>{
const p=.2,N=4,selector=.8;
const coverage=1-(1-p)**N;return [coverage,coverage*selector];
};
const actual=solve();
const expected=[0.5904,0.47232];
if(JSON.stringify(actual)===JSON.stringify(expected)){console.log('PASS',actual)}else{
const a=[actual].flat(), b=[expected].flat();
if(a.length!==b.length||a.some((v,i)=>!Number.isFinite(v)||Math.abs(v-b[i])>1e-10))throw Error('Numerical mismatch');
console.log('PASS within 1e-10',actual);
}
Download this example
Reference output — reveal after predicting
[
  0.5904,
  0.47232
]

Test and transfer

Perfectly correlated attempts retain .2 coverage; the IID formula cannot be reused.

Record input, code version, expected result and observed result in the notebook below. Then construct a counterexample that violates the assumption above and explain why the original conclusion no longer follows.

Download complete kit (.tar.gz) · Complete reference kit and regression checks

Predict, test and keep evidence

Before revealing an answer, predict one result. After the exercise, record the discrepancy and a transfer test. Saved locally across language editions.

Open notebook / export / clear →

The mathematical review scope is recorded per lesson. It does not establish empirical paper reproduction; report suspected errors in your notes. Review scope