Chapter 37 Test-Time Compute: Sampling, Search, Verification, and Stopping

37.1 The weights stay still while the work increases

A first attempt can use the wrong operation even when all necessary facts are present. In Chapter 36, adding two lodging costs before applying a cap produced 1500 instead of 1430. We could train on better solutions. We could also leave the weights alone, ask for more candidates and check them. These are different interventions.

Test-time compute is computation spent when solving the current request. It can include a longer generated solution, multiple samples, searches through alternatives and calls to a verifier. It does not mean that parameter updates occur between attempts. Chapter 29 explains how sampling can produce different continuations; Chapter 36 explains why checking them is a separate capability.

We need to know what the extra work bought. A comparison that charges only the winning answer hides the rejected candidates. One that counts generation but treats verification as free can favor an expensive selector. We will expose all candidates and use one explicit budget, then test an actual KA-1 runtime adaptation in Chapter 38.

37.2 Four questions and every candidate

Example 37.1 — Freeze a small candidate pool. Each question has two whole-yuan costs and the same 750-yuan per-night cap. Add the two individually capped amounts; allowance cannot be transferred. The four correct totals below follow by hand from that rule.

The direct responses and step candidates are author-assigned, not model outputs. The CPU experiment replays controllers over them; it measures controller behavior and replay time, not a language model’s accuracy or generation speed. This lets us inspect each decision without a GPU. The unchanged pool is stored in data/part-vi/budget-v1.json.

Table 37.1 — Complete question and candidate pool. A, B and C are local candidate positions within each question. Repeated strings remain separate attempts.

Costs	Required total	Direct response	Step candidate A	Step candidate B	Step candidate C
680, 820	1430	1500	680 + 820 = 1500	680 + 750 = 1430	680 + 750 = 1430
400, 300	700	700	400 + 300 = 700	400 + 300 = 700	400 + 300 = 700
800, 900	1500	1500	750 + 750 = 1500	800 + 900 = 1700	800 + 900 = 1700
600, 900	1350	1500	600 + 750 = 1350	600 + 900 = 1500	600 + 900 = 1500

A step expression records claimed allowances and their sum, not merely the original bills. Thus the first A has a wrong second allowance. For the third question, B and C repeat the same uncapped error. Different calls can produce correlated mistakes; extra text does not ensure a different method.

37.3 What does one unit of budget buy?

Our horizontal axis will be maximum charged calls per question. One candidate-generation call costs one unit; one verifier call costs one unit. This is a declared call quota, not a claim that all calls use identical time, tokens or FLOPs. We separately record input/output tokens and time.

For the fixed replay, the request is the ASCII string sum per night minimum costs 680 820 cap 750, with the two costs replaced for each question. The fixed audit lexer counts a word, a digit run or a non-whitespace punctuation mark as one token. Every request has 9 such tokens, a direct numeric answer has 1, and each step expression has 5. These are fixture tokens, not MG-2 or API tokens. Both language pages analyze these identical stored strings.

Generation reads all 9 request tokens and emits its candidate. Verification reads the request and candidate, then emits one decision token, accept or reject. No prefix reuse is assumed. Thus a direct call costs $9+1=10$ fixture tokens; a step call costs $9+5=14$; a verifier call costs $9+5+1=15$. We count rejected and duplicate candidates too. For a real model, use its tokenizer, actual processed contexts and implementation timing, rather than substitute this lexer.

A direct policy makes one answer attempt. A chain-of-thought (CoT) policy generates intermediate solution text before its answer; here “steps” selects the first step candidate. The original CoT prompting research changes the examples in the input, not the weights. Our authored pair of direct/step outputs does not reproduce that research measurement. A visible solution may provide useful context for later tokens, but remains generated text rather than a complete internal computation record. Wei et al. describe the prompting setup and its limits.

Self-consistency samples multiple solution paths, extracts their final answers and chooses the most frequent answer. Our vote controller takes up to three candidates, in the declared order, and breaks a tie using the earliest encountered answer. It votes over final amounts, not over which paragraph sounds persuasive. A learned model would need suitable sampling and an answer parser; the controller replay does not generate that diversity for it. Wang et al. specify the sampled-path method.

Our search with a verifier explores complete candidates in order. After each generation it uses Chapter 36’s rule-based final-amount check. It stops at the first accepted amount. Before starting a new candidate it reserves both a generation call and a check call. If fewer than two units remain, it stops; without an accepted candidate it abstains, which fails these fully specified numeric questions. This is a small search over complete solutions. Prefix or tree search can instead branch at intermediate steps and prune branches, but then expansions, repeated prefixes, lookahead and checks must also be charged. We do not implement a tree-search algorithm here.

37.4 Follow the selector, not just its final score

Example 37.2 — Spend at most four calls per question. Use the primary order A, B, C. Direct answers pass questions two and three: 2/4. First-step answers A pass questions two, three and four: 3/4.

Voting uses all three candidates, costing three generation calls per question. For question one, 1430 wins two votes to one. For question two, all three say 700. But on question three, wrong 1700 defeats correct 1500 by two votes to one; on question four, wrong 1500 defeats correct 1350. The final score is 2/4. More sampled text has reduced the primary first-step score.

Search rejects question one’s A=1500, then accepts B=1430: two generation calls and two checks use all four units. The first candidates on questions two, three and four pass immediately, using two units each. Search therefore uses $4+2+2+2=10$ calls for four correct answers.

Table 37.2 — The same cap, with all work charged. All rows have a four-call maximum per question; methods may stop earlier. Token totals follow the declared fixture lexer. The last column records actual CPU controller replay time, not model generation time.

Method	Generation calls	Verifier calls	Total charged calls	Total fixture tokens	Correct questions	CPU replay, ms
Direct	4	0	4	40	2/4	0.011417
First step path	4	0	4	56	3/4	0.013000
Vote over three paths	12	0	12	168	2/4	0.036916
Search + verifier	5	5	10	145	4/4	0.029125

For search, five generation calls cost $5\times14=70$ tokens and five checks cost $5\times15=75$, totaling 145. Charging only four returned answers would omit the first rejected candidate and every check. The direct and step rows have equal call counts but different token totals, so they are not equal-token experiments.

37.5 A quality curve can bend downward

Repeat the primary-order replay at caps 1, 2, 3, 4 and 6. Direct and first-step policies already stop after one generation. Voting runs out of candidates after three; a larger cap creates no new pool entries. Search stops on acceptance, a depleted pool or insufficient remaining budget.

Table 37.3 — Primary-order quality at each maximum call budget.

Maximum calls per question	Direct	First step path	Vote	Search + verifier
1	2/4	3/4	3/4	0/4
2	2/4	3/4	3/4	3/4
3	2/4	3/4	2/4	3/4
4	2/4	3/4	2/4	4/4
6	2/4	3/4	2/4	4/4

At cap 1, search cannot fund a generation/check pair and makes no call. At cap 3, a failed first candidate leaves only one unit, so it cannot try a second candidate. For voting at cap 2, ties preserve the first answer. Adding the third vote changes three questions: question one improves, while questions three and four deteriorate. The net change is a loss of one correct question.

○ Direct · □ First steps · △ Vote · ◇ Search + verifier

Primary order A–B–C. One generation = 1 call; one verification = 1 call. Actual work may stop below the cap.

Figure 37.1 — Extra votes can lower quality; verified search also needs a sufficient call budget. Original fixed-pool data and static plot · CC BY-SA 4.0

Figure 37.1 plots the table, using distinct line and marker styles as well as labels. Its vertical axis counts correct questions out of four. Its horizontal axis is a maximum quota, so unused budget is not silently counted as actual work. These points demonstrate possibilities under the fixed pool, not a universal curve for a model family. Research on test-time allocation likewise reports dependence on question difficulty, verifier behavior and the cost definition. Snell et al. explicitly discuss those conditions, including a difficulty-estimation cost excluded from their reported experiments.

A single favorable order is not enough. We retained three deterministic schedules before replay: A–B–C, B–A–C, C–B–A. They probe order sensitivity; they are not three independent model training seeds.

Table 37.4 — Repeat the four-call comparison with fixed order changes.

Order	First step path	Vote	Search + verifier	Search calls / fixture tokens
A–B–C	3/4	2/4	4/4	10 / 145
B–A–C	2/4	2/4	4/4	12 / 174
C–B–A	2/4	2/4	2/4	12 / 174

In the last schedule, questions three and four spend four units rejecting C and B; correct A is still unseen. Raising the cap to six lets each reach A, giving 4/4 but costing 16 calls and 232 tokens in total. The underlying question count remains four. Twelve question-order outcomes do not establish twelve independent task scenarios.

The executable code/part-vi/core.py reproduces every selection and cost. The saved data/part-vi/mechanism-run-v1.json records actual CPU replay milliseconds for every schedule, method and cap, alongside full calls and tokens. Those times include controller/lexer/checker work, not simulated language-model generation. They are too small and implementation-specific to use as serving latency; Chapter 38 records complete calls to an actual local model separately.

37.6 A stopping rule must say what evidence is enough

A hard budget guarantees a bound on permitted work, not on correctness. In the example, reserving the check prevents the system from spending its last unit on an answer it cannot verify. Early acceptance saves work only to the extent that the verifier deserves trust for the claimed task.

If the verifier were Chapter 36’s substring checker, accepting an early candidate could preserve a wrong or unsupported response. Searching longer against that scorer might expose more exploits. Likewise, repeated agreement from one model can reflect a shared error. Agreement is a useful observable, not an independent factual source.

Choose a stopping rule before looking for the best test result. Start with a maximum call/token/time budget and a task-specific acceptance rule. On development data, compare the extra correct cases gained at the next budget with the extra work and regressions. If no improvement appears, a larger allocation has not earned its cost. A deadline can require an explicit abstention or limited answer even when a promising branch remains. A disagreement can justify an additional check if budget and a capable checker exist; it does not justify unbounded generation.

Now remove the current policy from the lodging question. Ten plausible calculations using 600 cannot establish whether the current cap is 600 or 750. A fresh source is needed. Similarly, repeatedly describing a possible order status does not query a live order. More problem-solving computation is appropriate when the needed information and usable solution alternatives exist. The next decision is therefore which layer is actually missing.

37.7 Summary

Runtime computation can change a selected answer without changing parameters. Compare methods under the same declared resource convention, charge unsuccessful candidates and verification, and expose stopping and tie rules. More work can help, saturate or reduce quality. Fixed-pool replay explains the controller; actual model runs are separate evidence. Neither repeated agreement nor longer reasoning supplies an absent fact.

37.8 Exercises

1. In primary order, give search a maximum of three calls per question. Show the first question’s attempts, stop and total cost across all four questions.
2. For primary-order voting, explain why going from two to three candidates reduces the score despite fixing the first question.
3. If a verifier call costs two units instead of one, what maximum per question lets primary-order search reach all four correct answers? How many units does it actually spend over the suite?
4. Under C–B–A with a six-call cap, calculate search’s generation/check counts and fixture tokens. What does this establish about order sensitivity?
5. A team reports “a majority of 20 answers agrees on 600, so the policy is current.” What evidence is missing? Which chapter’s distinction explains the mistake?

37.9 Reference answers

1. Question one generates A and rejects it, spending two calls. It cannot fund another pair with one unit left and abstains. Each other question accepts A after two calls, so the suite spends eight calls, uses $4\times14+4\times15=116$ tokens and passes 3/4.
2. At two candidates, ties retain A. The third candidate makes question one correct, but makes questions three and four wrong. One gain minus two regressions lowers the count from 3/4 to 2/4.
3. Each generation/check pair costs three units. Question one needs two pairs, so the maximum must be at least six. The others each use three units: $6+3+3+3=15$. This changes the budget convention, so redraw the curve rather than relabel its old points.
4. Questions one and two need one pair each; questions three and four need three pairs each. That is eight generations and eight checks, costing $8\times14+8\times15=232$ tokens. A different order can require more work to expose the same correct candidates; no new model capability was learned.
5. The current authoritative policy version is missing. Twenty related outputs are not twenty independent sources. Chapter 36 separates applying supplied rules from knowing missing facts; Chapters 32 and 38 also distinguish source selection from answer generation.

37.10 References

• Wei et al., Chain-of-Thought Prompting Elicits Reasoning in Large Language Models, sections 2–3. Prompted intermediate solutions with fixed weights, plus limits of interpreting those solutions.
• Wang et al., Self-Consistency Improves Chain of Thought Reasoning, sections 2–3. Sampling, final-answer extraction, voting and repeated comparisons.
• Snell et al., Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters, 2024, sections 3–5. Difficulty-dependent allocation, verifier/search tradeoffs and explicit cost limitations; its measured curves are not the authored curve here.