Sample, Scrutinize and Scale: Effective Inference-Time Search by Scaling Verification

Implications

• The study positions sampling-based search as a practical, parallelizable baseline for comparing test-time inference strategies.The approach can scale by sampling more responses and remains complementary to other test-time compute methods.Source: §1 · p. 1

Method

• Sampling-based search generates many responses and selects among them through natural-language self-verification, varying both sampled responses and verification capability.The implementation uses random sampling, per-response verification, score-based selection, and pairwise tie-breaking for closely scored candidates.Source: §1 · pp. 2–3

Results

• Gemini v1.5 Pro exceeds o1-Preview, while Gemini v1.5 Flash exceeds Gemini v1.5 Pro, as sampling-based search scales on LiveBench and AIME.AIME exhibits sustained power-law scaling at sufficient search scale.Source: §1 · p. 2

Findings

• Implicit scaling helps explain search scalability: larger samples widen the pool of well-written candidates, which are easier for the verifier to assess.This counters the expectation that more candidates necessarily make verification less accurate.Source: §1 · p. 2

Verification principles

• Directly comparing candidate responses helps localize errors and hallucinations that models often miss when evaluating responses independently.Pairwise comparisons identify where responses diverge and determine which side is correct.Source: §1 · p. 2
• Chain-of-thought formats aid response generation but are harder to verify than more formal mathematical writing, motivating task-specific rewriting.The paper reports that frontier models can elicit accurate verification with these strategies but have weak out-of-box verification ability.Source: §1 · p. 2

Results

• Verification@200 consistently improves on Consistency@200 and surpasses o1-Preview across the reasoning benchmarks reported in Table 1.Each Table 1 score reflects a single run because search at this scale is expensive.Source: Table 1 · p. 3, §1 · p. 3

2.1 Scaling Trends

• Scaling both search and verification yields the largest performance gains, and the trend is strongest on AIME.Search samples candidate solutions, while verification averages scores across attempts; the streamlined evaluation omits tie-breaking.Source: §2.1 · pp. 4–5, §2 · p. 4
• Sampling-based search accuracy continues improving beyond the point where self-consistency saturates, with the strongest bottleneck on AIME arising from rare correct solutions.The supplied heatmap describes scaling across benchmarks, while the accompanying analysis attributes AIME’s bottleneck to the low probability of generating correct solutions.Source: Figure 2.1 · p. 4, §2.1 · p. 5

2.2 Implicit Scaling

• On ambiguous questions, accuracy increases as more responses are sampled, despite controlling for the increased chance that at least one response is correct.Ambiguous questions contain at least one candidate with a correct final answer, and the evaluation fixes verification attempts at 50 for the plotted scaling trend.Source: §2.2 · p. 5, Figure 2.2 · p. 5
• Implicit scaling occurs because larger candidate pools are more likely to include a high-quality correct response that is easier for the verifier to recognize.The effect reflects both more ambiguous questions and higher accuracy within the ambiguous set.Source: §2.2 · p. 5

2.3 The Long Tail of Response Distributions

• Verification@k continues power-law scaling after Consistency@k begins to plateau, with verification attempts fixed at 50.This pattern is shown on AIME and LiveBench Reasoning, where consistency can converge on the most probable response while verification can exploit rarer candidates.Source: §2.3 · p. 7, Figure 2.4 · p. 7
• Verification can select a rare correct solution from the response distribution’s long tail when consistency favors a frequent incorrect answer.For AIME 2024 Problem 11, one of 200 sampled Gemini v1.5 solutions reached “601,” while consistency selected the more frequent incorrect answer “1.”Source: §2.3 · p. 7

3 Effective Self-Verification in Natural Language

• Self-verification benefits from comparing responses because disagreements help localize errors that models often overlook when evaluating candidates independently.Providing other responses gives the verifier locations where mistakes and hallucinations may be concentrated.Source: §3 · pp. 7–8
• Verification is also improved by rewriting candidate responses into rigorous, hierarchical, and modular theorem-lemma-proof formats before evaluation.The paper contrasts this verification-oriented style with chain-of-thought, which is useful for generating responses but harder to verify directly.Source: §3 · p. 8

3.1 Sampling-Based Search Implementation

• The minimalist search pipeline samples candidate solutions in parallel, verifies each with repeated binary correctness scores, and selects the highest-scoring response.When similarly scored candidates disagree, pairwise comparisons identify divergence points and determine which side is correct before selecting the tournament winner.Source: §3.1 · pp. 8–9

3.2 Ablation Studies

• Comparing candidate responses significantly improves sampling-based search, especially when verifiers assign high scores broadly and struggle with low recall.On MATH, the top three candidates receive nearly 90% average verification scores, so omitting tie-breaking substantially underestimates Verification@k.Source: §3.2 · p. 9, Table 3 · p. 9
• Ablations show that removing rewriting harms verification performance, while splitting verification into separate threads sharply reduces performance through low precision attributed to miscalibration.The prompt variants include Main, Without Rewrite, and Split-Context; Table 4 reports false-positive and false-negative verification rates.Source: §3.2 · pp. 9–10, Table 4 · p. 10

4.1 Smaller Models

• Sampling-based search substantially improves the lower-cost Flash model and Pro+Flash, though its gains over Consistency@200 are smaller for end-to-end Flash than for Gemini Pro.Flash costs nearly 20× less than Pro, and Pro+Flash Verification@200 roughly matches the cost of Consistency@500.Source: §4.1 · p. 10

4.2 Performance by Subtask

• Verification provides the greatest gains on AIME 2024, Web-of-Lies, Competition, and Zebra Puzzle, but not on the LiveBench Olympiad task.The comparison uses Pass@200, Consistency@200, and Verification@200 accuracy rates.Source: §4.2 · p. 10, Table 6 · p. 11

4.1 Smaller Models

• Verification@200 exceeds Consistency@200 for all tested model choices, while Pro+Flash Verification@200 matches or exceeds Pro Consistency@200.The models include Pro, Flash, and Pro+Flash configurations.Source: §4.1 · p. 10, Table 5 · p. 11

4.2 Performance by Subtask

• The LiveBench Olympiad task is incompatible with this Verification implementation because of its unique question design.Source: §4.2 · p. 12

• Experiments use Gemini v1.5-Pro-002 and Gemini v1.5-Flash-002, with default search settings k_inf=200, σ_inf=1.5, k_verif=50, and σ_verif=1.The maximum output is 8,192 tokens per query, and candidate scoring uses a language model rather than literal string comparison.Source: §5 · p. 12
• Preliminary scoring first uses 10 verification scores per candidate, discards low-scoring candidates, and retains at most 15 responses per final answer before full verification.Candidates with average preliminary scores below 0.2 are discarded; preliminary scoring is omitted for AIME.Source: §5 · p. 12
• Approximately $650 per AIME question is required without preliminary scoring, falling to $200 with it and $12 when Gemini Flash performs verification.The full pipeline is estimated at roughly 130M output tokens per question, while preliminary scoring reduces token usage by about 70%.Source: §5 · p. 12
• The evaluation covers Berkeley MATH, LiveBench Math, LiveBench Reasoning, and the 15 questions from Exam II of AIME 2024.Source: §5 · p. 12

• The benchmark contains manually curated entries with a question, one correct response, and one incorrect response drawn from sampling-search residuals.An example pairs a correct answer with a hallucinated non-existent clause causing the wrong response.Source: §6 · p. 12, Figure 6.1 · p. 13
• The scoring task asks whether a model can judge one response’s correctness from the question and response alone.A separate scoring set includes responses that reach the correct final answer by coincidence despite fatal errors.Source: §6 · p. 14
• The comparison task provides both responses with correctness labels masked and guarantees that at least one is correct.Models are prompted to identify disagreements between responses in their reasoning.Source: §6 · p. 14
• Models perform only marginally better—and often worse—than random chance on the easier comparison task.Source: §6 · p. 14
• Verification errors are typically caused by low recall, and Consistency@5 can perform worse than one-shot inference by amplifying an incorrect output bias.The authors frame improved verification as useful for sampling search, reinforcement learning, data flywheeling, and end-user experience.Source: §6 · p. 14

• Test-time compute methods include chain-of-thought, tree-of-thoughts, self-critique, reinforcement learning, many-shot learning, and inference-time finetuning.These approaches can be complementary to explicit sampling-based search, which offers greater parallelism and robustness than internally implemented search.Source: §7 · p. 14
• Sampling-based search generates multiple candidate responses and selects among them using methods ranging from plurality voting to self-verification or learned reward models.The paper studies random sampling with language-model self-verification and varies verification attempts for finer scaling control.Source: §7 · pp. 14, 16
• Commercial-model verification remains weak: GPT-4o and Claude 3.5 Sonnet are near random guessing, while o1-Preview still fails on 20–30% of wrong responses.Source: Table 7 · p. 15
• Prior verification work uses direct prompting as well as response reconstruction, masking and refilling, rubrics, or option selection, whereas this paper does not train custom verifiers or use external tools.The authors report that black-box model access is sufficient for effective verification at scale.Source: §7 · p. 16
• Verification supports candidate selection, iterative output improvement, reinforcement learning, data flywheeling, finetuning, and better-written responses for end users.Source: §7 · pp. 16–17

8 Conclusion

• Sampling-based search scales remarkably well with simple implementations, with implicit scaling and verification principles underpinning its state-of-art reasoning performance.The authors scaled a minimalist, embarrassingly parallel implementation across reasoning benchmarks.Source: §8 · p. 17
• Comparing responses localizes errors, while rewriting responses for output-style suitability improves self-verification with test-time compute.These are the two key principles identified for scaling verification capabilities.Source: §8 · p. 17
• The authors expect sampling-based search to remain important because it complements other scaling strategies, is parallelizable, and can scale to arbitrarily large inference budgets.They also propose it as a baseline for search capability and motivate alternatives to random sampling for massive, diverse solution sets.Source: §8 · p. 17

A.1 Inference Prompts

• MATH and AIME questions receive a step-by-step prompt requesting a boxed final result, whereas LiveBench questions are submitted verbatim.The LiveBench benchmarks already provide their own instructions and formatting requests.Source: §A.1 · p. 23

A.2 LM-Based Scoring

• Each candidate is scored through five repeated LM judgments that compare its final answer with the ground-truth final answer, using a strict majority of valid rulings.The scoring model is Gemini-v1.5-Pro-002, and the queries use temperature zero.Source: §A.2 · p. 23
• The scorer extracts both final answers and judges only whether they match, ignoring intermediate reasoning and non-substantive formatting differences.Nonsensical and incomplete responses are labeled incorrect.Source: §A.2 · pp. 23–25
• Automated scoring matched human scoring 99% of the time, and the authors report that choosing human versus automated scoring matters little to the results.Manual checks covered Consistency@200 and Verification@200, with some false positives and negatives on LiveBench datasets.Source: §A.2 · p. 23

A.3 Implementation of Consistency@k

• Consistency@k evaluates the correctness of the most common final answer produced across k model runs.Candidate responses count as equivalent when their extracted final answers match literally after whitespace stripping.Source: §A.3 · p. 25

A.4 Benchmark Evaluation Prompts

• The comparison task asks the model to locate disagreements between two solutions and determine which solution is correct before returning a structured choice.Its output format records either solution 1 or solution 2 as correct.Source: §A.4 · p. 26
• The scoring task asks whether one student solution reaches the correct final answer in a correct fashion, then returns a structured correctness judgment.The prompt explicitly warns against leaping to conclusions and asks the model to reason through the solution.Source: §A.4 · p. 26

B.1 Temperature Tuning

• Temperature choices σinf and σverif did not significantly affect post-verification accuracy on the MATH training split.Tables 8 and 9 vary inference and verification temperatures separately; Verification@20 uses 20 verification attempts without tie-breaking.Source: §B.1 · p. 27, Table 8 · p. 27, Table 9 · p. 27

B.2 Olympiad LiveBench Math Subtask

• Verification provided no lift on LiveBench MATH Olympiad questions because their required index-list format is incompatible with theorem-lemma rewriting.The pipeline asks the verifier to rewrite candidates so the theorem states the final answer, whereas Olympiad tasks require a specific sequence of expression indices.Source: §B.2 · p. 27

C Self-Verification Prompts

• The self-verification prompts include a Main style and separate tie-breaking prompts, with multiple parts encouraging longer responses.These prompts are the ones used to query models for self-verification of candidate responses.Source: C Self-Verification Prompts · p. 29

C.1 Verification Scoring Prompts

• Verification-scoring prompts require exhaustive theorem-lemma rewrites, detailed proofs, and systematic checks that identify, validate, correct, and assess suspicious claims.The workflow also asks models to preserve assumptions, inspect dependencies on final answers, and mark errors as fatal when correction changes the result or invalidates the proof approach.Source: §C.1 · pp. 29–32

C.2 Comparison Prompts

• Comparison prompts instruct models to examine two disagreeing solutions line by line, narrating their reasoning while reviewing proofs, lemmas, and corresponding approaches.The procedure first analyzes the entire first solution before applying the same meticulous format to the second.Source: §C.2 · pp. 35–36
• The prompts first require identifying and attributing disagreements between the two solutions without initially judging which side is correct.The analysis should locate where the solutions diverge and consider whether the causes involve question interpretation, methodological choice, or differing calculations.Source: §C.2 · pp. 37–38
• When solutions use different approaches, the prompts recommend comparing intermediate, contradictory subclaims to expose meaningful differences and possible proof errors.The comparison should crystallize each approach and collect evidence from both sides for every disagreement.Source: §C.2 · pp. 38–39
• Only after tracing and steelmanning the root disagreements should the analysis determine which solution reaches the correct final answer.The final ruling is expected to be careful, rigorous, and based on the arguments and evidence presented by both sides.Source: §C.2 · p. 39

D.1 Example Entry from LiveBench Reasoning

• The LiveBench reasoning responses disagree, producing either “yes, yes, no” or “no, no, no” for the three truthfulness questions.One response concludes that Anika and Luna tell the truth while Farid lies; another concludes that all three lie.Source: §D.1 · p. 41, §D.2 · p. 41

D.2 Example Entry from LiveBench Math

• The LiveBench Math response correctly counts 8 positive perfect squares below 2023 that are divisible by 5.It reduces the condition to n = 25m^2, enumerates m^2 values below 80.92, and selects answer E.Source: §D.2 · pp. 41–42

D.3 Example Entry from MATH

• The MATH response derives 44.1 daps for 42 baps, while another shown derivation gives 40 daps from the same conversion setup.The examples therefore display inconsistent numerical reasoning and answers for the daps-yaps-baps problem.Source: §D.3 · pp. 42–43

D.4 Example of Response with Invalid Reasoning but Correct Final Answer

• For seven equal bags and an added 53-coin bag, the smallest original total exceeding 200 that can be redistributed equally among eight bags is 203.With n = 29 coins per original bag, 7n = 203 and 7n + 53 = 256 = 8 × 32.Source: §D.4 · pp. 43–44

E.1 AIME Example

• The AIME candidate concludes that the dodecagon contains 198 rectangles after dividing 594 by 3.The supplied reasoning counts sides, diagonals, and parallel segments before applying the final division.Source: §E.1 · pp. 45–46
• The rectangle solution’s calculation is inconsistent: evaluating 122(12−1) through the shown divisions gives 99, not 594.The passage explicitly identifies this as a calculation error in the candidate solution.Source: §E.1 · pp. 45–46

E.2 LiveBench Reasoning Example

• The LiveBench reasoning propagates truth or lie status through chained statements about Jaxon, Zara, Ryan, Tala, Priya, Max, Elowen, and Charlie.The rewritten response uses these chains to derive the final statuses for the queried locations.Source: §E.2 · pp. 46–48
• The LiveBench response concludes that Grace lies, Zara lies, and Ryan tells the truth, corresponding to **no, no, yes**.The conclusion follows from Jaxon’s lie, Zara’s lie, Ryan’s truthfulness, and Grace’s statement about Zara.Source: §E.2 · p. 47