PaperlayerView exact revision on arXiv

Source-linked AI summary

FineVerify: Scaling Test-Time Compute with Fine-Grained Self-Verification for Agentic Search

James Xu Zhao, Hui Chen, Bryan Hooi, See-Kiong Ng

arXiv:2606.00660v2cs.CL

TL;DR

Agentic search needs reliable test-time scaling despite sparse correct answers and calibration-sensitive candidate selection. FineVerify verifies sampled candidates against shared checkable sub-questions and aggregates the resulting judgments. Across four benchmarks and two models, it consistently outperforms standard scaling baselines, while its traces support benchmark auditing.

  • Problem

    Agentic search lacks a reliable scaling-selection approach because correct answers are sparse and coarse scores depend on calibration across multiple conditions.

  • Method

    FineVerify decomposes each question into checkable sub-questions, verifies every candidate against retrieved evidence, and selects the highest-scoring candidate from explicit per-check judgments.

  • Results

    Across four agentic search benchmarks and two models, FineVerify consistently improves accuracy and outperforms standard test-time scaling baselines.

  • Takeaways & Limitations

    Fine-grained verification provides a more reliable selection signal and interpretable traces that can help audit benchmark errors.

  • Takeaways & Limitations

    The evaluation mainly covers questions with short, single-answer ground truth, leaving answer sets, long-form reports, and structured tables outside its scope.

Abstract

from arXiv · show

Agentic search requires language model agents to explore many sources and answer complex information-seeking questions. Scaling test-time compute is a promising way to improve these agents, but current approaches can fail, because correct answers are often sparse and score-based selection depends on model calibration. We propose FineVerify, a fine-grained self-verification framework that decomposes each question into checkable sub-questions, verifies sampled candidates against each sub-question, and selects the candidate with the highest aggregated score. This per-check structure turns selection into simpler local judgments and produces scores under the same explicit criteria. Across four agentic search benchmarks and two models, FineVerify consistently outperforms standard scaling baselines. With only four sampled trajectories, it improves GPT-5-mini by 8.2 accuracy points and Gemini-3-flash by 5.6% on average. With 12 samples, FineVerify enables GPT-5-mini to surpass frontier GPT-5 on BrowseComp-Plus. Beyond accuracy, FineVerify produces interpretable verification traces that help audit benchmark errors, suggesting broader applications for inspecting agentic search systems. Code and data are available at https://github.com/XuZhao0/fineverify

1 Introduction

Agentic search makes test-time scaling difficult because correct answers can be sparse and coarse candidate scores depend on calibration across multiple conditions. FINEVERIFY addresses this with explicit sub-question verification, improving selection accuracy and producing traces for benchmark auditing.

  • Correct answers may be sparse among plausible agentic-search candidates, making frequency-based aggregation unreliable.
  • Multiple conditions make single candidate-level scores noisy, inconsistent, and difficult to compare across answers.
  • FINEVERIFY decomposes questions into checkable sub-questions, verifies each candidate against retrieved evidence, and aggregates explicit per-check judgments.
  • Across four benchmarks and two models, FINEVERIFY improves accuracy, outperforms standard test-time scaling baselines, and continues improving with additional samples.With four trajectories, average accuracy rises from 59.2% to 67.4% for GPT-5-mini and from 71.3% to 76.9% for Gemini-3-flash.
  • FINEVERIFY produces interpretable verification traces that support candidate selection and benchmark auditing.The traces expose whether requirements are supported, not_found, or contradicted; a BrowseComp-Plus audit identified 10 dataset errors among 200 sampled examples.

2 FINEVERIFY: Fine-Grained Self-Verification for Agentic Search

FINEVERIFY makes agentic-search selection fine-grained and evidence-based by decomposing each question into shared checkable sub-questions, judging every candidate against them, and aggregating the judgments. It selects the best-supported candidate, can stop early when all requirements are supported, and caches repeated verification results.

  • Question decomposition: FINEVERIFY evaluates every sampled candidate against the same set of checkable sub-questions, making verification criteria consistent across candidates.Question decomposition reduces compound-requirement verification to simpler local checks.
  • Candidate verification: Each sub-question receives one of three evidence judgments: supported, not_found, or contradicted.These judgments distinguish confirmation, refutation, and insufficient evidence.
  • Scoring and selection: FINEVERIFY converts the judgment list into a scalar score, where higher values indicate stronger evidence support.The score maps judgments to numeric values and averages across sub-questions.
  • Scoring and selection: The method retains the highest-scoring candidate across rounds and returns a fully supported candidate immediately when one reaches a score of 1.Otherwise, it returns the highest-scoring candidate after the maximum number of rounds.
  • Caching: FINEVERIFY reuses stored judgment lists and scores for previously verified answers, reducing repeated verification cost.Fixed sub-question sets make this caching possible.

3 Experiments

Experiments across four agentic search benchmarks and two models show that FINEVERIFY improves accuracy over Pass@1 and test-time scaling baselines. It also scales with additional samples while maintaining a favorable cost-accuracy tradeoff.

  • Main results: FINEVERIFY achieves the best average performance for both models across four agentic search benchmarks.All test-time scaling methods use four sampled trajectories, while Pass@1 uses one.
  • Main results: 8.2 points: GPT-5-mini average accuracy rises from 59.2% with Pass@1 to 67.4% with FINEVERIFY.FINEVERIFY improves GPT-5-mini accuracy on all four benchmarks.
  • Main results: 5.6 points: Gemini-3-flash average accuracy rises from 71.3% to 76.9% with FINEVERIFY.On BrowseComp-Plus and DeepSearchQA, the four-sample improvement is 6.0 points.
  • Baseline comparison: FINEVERIFY outperforms all baselines on average for GPT-5-mini and achieves the best accuracy on every benchmark.It exceeds Best-of-N and Solution Aggregation by 1.6 and 1.1 average points, respectively.
  • Scaling with compute: 20.5% accuracy gain: FINEVERIFY rises from 49.5% with one sample to 70.0% with 16 samples on BrowseComp-Plus.With 12 samples, it reaches 67.5%, surpassing GPT-5 under the same evaluation setting.
  • Scaling with compute: Fine-grained verification scales more reliably than majority voting, coarse score-based methods, and solution aggregation as sample counts increase.Candidate-level baselines plateau or grow slowly, whereas FINEVERIFY verifies candidates against fine-grained sub-questions under an evidence-based criterion.
  • Cost-accuracy tradeoff: FINEVERIFY achieves high accuracy at moderate cost and costs less than Solution Aggregation and Confidence Verify.It improves over Majority Voting and Best-of-N with only a modest cost increase; cost includes token usage and web search calls.

4 Analysis and Discussion

The analysis examines how FINEVERIFY scores candidates, separates candidate generation from selection, and validates its judgments. Fine-grained verification provides reliable selection signals, while simple rule-based scoring performs robustly across evaluated settings.

  • Effect of Score Function: Simple rule-based scoring performs consistently well across models and benchmarks.Strict [0, 0, 1] and partial-credit [0, 0.5, 1] mappings perform best, whereas treating not_found as supported hurts performance.
  • Selection Accuracy: FINEVERIFY measures selection accuracy only when the candidate pool contains at least one correct answer.The metric isolates candidate selection from the separate process of generating a correct candidate.
  • Selection Accuracy: 90.7% average selection accuracy is achieved by FINEVERIFY for GPT-5-mini, exceeding Best-of-N by 2.2 points and Confidence Verify by 3.6 points.For Gemini-3-flash, FINEVERIFY reaches 94.1% average selection accuracy and exceeds the two baselines by 1.7 and 2.1 points.
  • Generation and Selection: 80.3% selection accuracy shows that FINEVERIFY can identify a correct candidate after it appears in the sampled pool.Sampling improves the chance of generating a correct candidate, while verification improves the chance of selecting it.
  • Human Evaluation: Human review agrees with 96.6% of GPT-5-mini verification judgments and 95.9% of Gemini-3-flash judgments.Question decompositions are also generally faithful: 30 of 30 for GPT-5-mini and 29 of 30 for Gemini-3-flash.
  • Verification Analysis: Incorrect candidates can satisfy many individual requirements, motivating verification at the level of fine-grained checks.Supported judgments occur for 43.3% of checks for incorrect GPT-5-mini candidates and 80.7% for incorrect Gemini-3-flash candidates.

5 Benchmark Auditing with Fine-Grained Verification

FINEVERIFY’s verification traces support auditing benchmark questions beyond selecting answers. Applying the method to BrowseComp-Plus identified inconsistent annotations and questions with multiple fully supported answers.

  • Audit Results: FINEVERIFY identifies 10 potential BrowseComp-Plus errors in a 200-question subset through verification traces and human review.The traces flag unsupported or contradicted requirements in cases involving annotated answers and question constraints.
  • Inconsistent Questions: One audited case showed that the article author and the recipient of the AIA Henry Adams Medal were different people.FINEVERIFY found no explicit evidence that they were the same person, prompting revision of the question.
  • Multiple Correct Answers: Repeated sampling found questions with multiple distinct candidate answers that were fully supported by evidence.Such cases conflict with BrowseComp-Plus’s intended setting of fact-seeking questions with a single indisputable answer.

6 Related Work

FINEVERIFY extends test-time scaling and self-verification for long-horizon agentic search. Its distinguishing design is fine-grained evidence verification without requiring full search trajectories.

  • Agentic Search: Agentic search agents plan queries, browse webpages, and synthesize evidence across many steps.This setting goes beyond static retrieval-augmented generation and motivates specialized search methods.
  • Test-Time Scaling: Test-time scaling commonly aggregates sampled solutions, expands search paths, or extends reasoning length.Recent long-horizon search methods synthesize multiple candidates or reuse full search trajectories.
  • FINEVERIFY: FINEVERIFY samples and verifies multiple search trajectories using fine-grained evidence rather than full-trajectory access.This distinguishes it from prior approaches that reuse complete search trajectories for final synthesis.
  • Self-Verification: Fine-grained verification has also been explored for factuality-related methods and software-engineering agents.The broader self-verification literature includes applications in mathematical reasoning and coding.

7 Conclusion

FINEVERIFY is a training-free framework that scales and inspects agentic search by decomposing questions, verifying candidates, and selecting the highest-scoring answer. Across benchmarks, it improves accuracy and provides traces for auditing errors without requiring logits or full search trajectories.

  • Framework: FINEVERIFY decomposes questions into checkable sub-questions, verifies candidates against them, and selects the highest-scoring candidate.The framework is designed to scale test-time compute on agentic search tasks.
  • Results: FINEVERIFY consistently improves accuracy across four agentic search benchmarks and two models while benefiting from additional samples.It also outperforms standard test-time scaling baselines and offers a strong cost-accuracy tradeoff.
  • Implications: Fine-grained verification provides a more reliable selection signal and produces interpretable traces that help audit benchmark errors.The framework requires no training, underlying logits, or full search trajectories.

Limitations

FINEVERIFY has limitations in tool-use requirements, sub-question weighting, and evaluation scope. These constraints leave room for improved scoring and broader output coverage.

  • FINEVERIFY may be less effective for models with weak tool-use ability because it requires multiple tool calls to retrieve and compare evidence.Improving verification for weaker tool-using models is left for future work.
  • The current scoring function averages judgment scores equally, although some sub-questions may matter more for determining correctness.Future work could weight sub-questions by importance or evidence quality.
  • The evaluation mainly covers questions with short, single-answer ground truth rather than all forms of agentic search results.Answer sets, long-form reports, and structured tables may require different verification and scoring strategies.

A Detailed Experimental Setup

The experiments evaluate FINEVERIFY across four agentic search benchmarks using two models, controlled sampling settings, and an iterative verification procedure. The method achieves the highest point estimate on all four benchmarks.

  • Benchmarks: Four agentic search benchmarks are evaluated, including GAIA-Search, BrowseComp-Plus, DeepSearchQA, and xbench-DeepSearch.GAIA-Search contains 64 filtered validation questions; BrowseComp-Plus and DeepSearchQA each use 200 sampled questions, while xbench-DeepSearch uses 100 Chinese questions.
  • Search settings: The evaluation uses model-native web search tools for most benchmarks and Qwen3-Embedding-8B retrieval with the official BrowseComp-Plus setup.BrowseComp-Plus provides search and document-retrieval tools over an offline corpus.
  • Verification procedure: FINEVERIFY decomposes each question into checkable sub-questions, verifies each candidate against retrieved evidence, aggregates judgments into a score, and can stop early on a fully supported answer.The algorithm caches verification results for repeated candidates and returns the highest-scoring answer after T rounds if no fully supported answer appears.
  • Results: FINEVERIFY achieves the highest point estimate on all four benchmarks.The reported uncertainty analysis uses 1,000 bootstrap resamples and 95% confidence intervals for GPT-5-mini with four sampled trajectories.

C.2 Results on an Unrevised BrowseComp-Plus Subset

On an unrevised random subset of 150 BrowseComp-Plus questions, FINEVERIFY improves GPT-5-mini accuracy with four samples and remains the strongest test-time scaling method. BrowseComp-Plus also requires more sub-question checks than the other benchmarks.

  • Evaluation design: The unrevised subset contains 150 randomly sampled BrowseComp-Plus questions evaluated without revising question-answer pairs.All methods use the same experimental setting, reducing the likelihood that the reported improvement is due to benchmark revisions.
  • Accuracy: 10.7%: FINEVERIFY raises GPT-5-mini accuracy from 53.3% with Pass@1 to 64.0% with four samples.It also achieves the highest accuracy among all test-time scaling methods on this unrevised subset.
  • Verification workload: BrowseComp-Plus produces around 13 sub-questions per question, substantially more than the other evaluated benchmarks.The two models produce similar numbers of sub-questions across benchmarks.

C.4 Cost Breakdown Across Benchmarks

FINEVERIFY has a lower average cost per question than the compared scaling baselines across the four benchmarks, although BrowseComp-Plus is somewhat more expensive because its questions require more checks.

  • Average cost: $0.45: FINEVERIFY’s average cost per question is lower than Solution Aggregation at $0.48 and Confidence Verify at $0.59.The comparison includes token usage and web-search calls without discounted cached-input pricing.
  • Cost controls: Caching repeated candidates, early stopping, and one-time question decomposition reduce FINEVERIFY’s cost.The same decomposed sub-questions are reused across candidates.
  • Benchmark differences: BrowseComp-Plus is slightly more expensive for FINEVERIFY because its questions contain more requirements and require finer-grained verification.On the other three benchmarks, FINEVERIFY is less expensive than Solution Aggregation and Confidence Verify while achieving strong accuracy.
  • Decomposition caveat: One sampled Gemini-3-flash decomposition error incorrectly split a counting condition into two statements.The corrected decomposition keeps that condition as a single statement.

E Open Web Search Failure Case

FINEVERIFY performs well on fixed offline-corpus search but faces lower selection accuracy on live-web benchmarks, where evidence can be difficult to access through static retrieval. Interactive webpage controls create concrete verification failures when the required evidence is not reflected in the URL.

  • GPT-5-mini reaches 99.2% selection accuracy on BrowseComp-Plus but 89.0% on DeepSearchQA.The gap indicates additional difficulty for open-web verification.
  • Open-web verification is constrained by diverse source quality, complex webpage structures, and evidence requiring interaction beyond static page access.
  • A Finland verification fails because the relevant 2023 OECD evidence is hidden behind an interactive year control that leaves the URL unchanged.The static-access verifier therefore returns not_found despite the candidate being correct.

F Detailed Information on BrowseComp-Plus Dataset Errors

The authors identify and review BrowseComp-Plus annotation problems, including inconsistent question-answer evidence and cases with multiple valid answers. Fine-grained verification helps flag these cases, which reviewers then inspect and revise when they reach agreement.

  • Error identification: 10 dataset errors are identified in a 200-question BrowseComp-Plus subset using FINEVERIFY’s filtering procedure.The confirmed cases include question errors and multiple-valid-answer cases.
  • Review procedure: Two authors independently review flagged cases using the original annotations, generated candidates, and fine-grained verification outputs.They may use external web-search tools while checking the evidence.
  • Review procedure: A dataset error is confirmed only when both reviewers agree that the question-answer pair is inconsistent, incomplete, or admits multiple valid answers.The original annotation is revised after agreement.
  • Failure cases: Interactive webpages can cause verification failure when relevant evidence is hidden behind UI interactions absent from the page URL.In one case, the candidate answer Finland is correct, but FINEVERIFY returns not_found for the sub-question.
  • Examples: The error examples include multiple valid answers caused by ambiguous identity or answer constraints.Examples include alternative valid teams for Teddy and multiple valid book titles associated with Barbara Hodgson.
  • Verification rules: FINEVERIFY’s strict rules require independent evaluation of all sub-questions and prohibit changing or reinterpreting their wording or candidate answers.Sub-questions must be self-contained, correctly anchored to entities, and supported with retrieved evidence.
Loading 2606.00660v2…