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.00660v1cs.CL

TL;DR

Agentic search makes candidate selection difficult because correct answers are sparse and global confidence scores can be noisy across multiple conditions. FineVerify verifies sampled candidates against explicit sub-questions and consistently outperforms standard scaling baselines across four benchmarks and two models, improving GPT-5-mini by 8.2 accuracy points with four samples.

  • Problem

    Agentic search lacks reliable candidate selection because correct answers are sparse and single global scores can be noisy across multiple conditions.

  • Method

    FineVerify decomposes questions into checkable sub-questions, verifies each candidate with retrieved evidence, and aggregates shared per-check judgments to select the highest-scoring answer.

  • Results

    Across four agentic search benchmarks and two models, FineVerify consistently outperforms standard test-time scaling baselines, improving GPT-5-mini by 8.2 accuracy points with four samples.

  • Takeaways & Limitations

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

  • Takeaways & Limitations

    FineVerify requires multiple tool calls to retrieve and compare evidence and may be less effective for models with weak tool-use ability.

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

FINEVERIFY improves agentic-search test-time scaling by decomposing questions into checkable sub-questions and verifying candidates against each condition. Across four benchmarks and two models, it improves accuracy, scales with additional samples, and produces interpretable traces for auditing.

  • Results: At 12 samples, FINEVERIFY exceeds GPT-5 on BrowseComp-Plus while continuing to improve as more trajectories are sampled.Its advantage over test-time scaling baselines grows with additional samples.
  • Method: FINEVERIFY decomposes each question into checkable sub-questions and labels candidate checks as supported, not_found, or contradicted using retrieved evidence.The framework uses per-condition verification rather than a single candidate-level score.
  • Results: 8.2 points: with 4 sampled trajectories, FINEVERIFY raises GPT-5-mini average accuracy from 59.2% (Pass@1) to 67.4%.The evaluation covers four agentic-search benchmarks and two models.
  • Auditing: FINEVERIFY produces per-condition traces showing which requirements are supported, not_found, or contradicted, enabling benchmark auditing.Applied to BrowseComp-Plus, it identified 10 dataset errors among 200 sampled examples.

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

FineVerify selects among agentic-search candidates through explicit, evidence-based verification over a shared set of checkable sub-questions. It aggregates per-check judgments into comparable scores, supports early stopping upon full verification, and can reuse cached results for repeated candidates.

  • Question decomposition: FineVerify decomposes each question into checkable sub-questions reused for every candidate, reducing compound-question verification to consistent local checks.Each sub-question represents one requirement that a correct answer should satisfy.
  • Selection and stopping: If any candidate reaches st = 1, meaning all sub-questions are supported, FineVerify stops early; otherwise, it returns the highest-scoring candidate after T rounds.The system retains the highest-scoring candidate across rounds.
  • Evidence verification: For every candidate and sub-question, the verifier retrieves evidence and assigns supported, not_found, or contradicted judgments.The judgments respectively indicate explicit confirmation, unclear support or refutation, and explicit refutation.
  • Scoring: FineVerify averages numeric mappings of per-sub-question judgments into a scalar score, making candidate evaluation more transparent and comparable than a single implicit score.A higher score indicates that the candidate is better supported by evidence.
  • Efficiency: Fixed sub-question criteria allow FineVerify to cache verification results and reuse stored judgments and scores for candidates already verified.Caching reduces cost by avoiding repeated verification.

3 Experiments

Experiments across four agentic search benchmarks show that FINEVERIFY consistently outperforms test-time scaling baselines for GPT-5-mini and Gemini-3-flash. It also scales with additional samples while maintaining a strong cost-accuracy tradeoff.

  • Main results: FINEVERIFY achieves the best average performance for both GPT-5-mini and Gemini-3-flash 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 increases from 59.2% with Pass@1 to 67.4% with FINEVERIFY.On BrowseComp-Plus, FINEVERIFY gains 11.0 points using four samples.
  • Main results: 5.6 points: Gemini-3-flash average accuracy increases from 71.3% with Pass@1 to 76.9% with FINEVERIFY.On BrowseComp-Plus and DeepSearchQA, FINEVERIFY improves accuracy by 6.0 points with four samples.
  • Scaling with test-time compute: 20.5% accuracy gains: FINEVERIFY rises from 49.5% at one sample to 70.0% at 16 samples.With 12 samples, it reaches 67.5%, surpassing GPT-5 under the same evaluation setting.
  • Cost-accuracy analysis: FINEVERIFY achieves high accuracy at moderate cost, outperforming Solution Aggregation and Confidence Verify while costing less on DeepSearchQA.It controls verification cost with early stopping and caching, yielding a strong cost-accuracy tradeoff.

4 Analysis and Discussion

FineVerify’s simple rule-based scoring is robust because it distinguishes missing evidence from support, while fine-grained verification selects correct candidates reliably when the candidate pool contains one. The analysis also separates generation from verification: sampling generates candidates, whereas verification selects among them.

  • Score Function: Rule-based scoring maps contradicted, not_found, and supported judgments to fixed values, while LLM-based scoring directly assigns a score from 0 to 1.The tested rule mappings are [0, 0, 1], [0, 0.5, 1], and [0, 1, 1].
  • Score Function: Both strict [0, 0, 1] and partial-credit [0, 0.5, 1] mappings perform best, whereas lenient [0, 1, 1] scoring hurts performance by treating not_found as supported.The results suggest that missing requirements should not count as evidence of correctness, and LLM-based scoring is less reliable than rule-based scoring.
  • Candidate Selection: 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.Selection accuracy is measured conditional on the sampled candidate pool containing at least one correct answer.
  • Candidate Selection: 94.1% average selection accuracy is achieved by FineVerify for Gemini-3-flash, exceeding Best-of-N by 1.7 points and Confidence Verify by 2.1 points.On BrowseComp-Plus, FineVerify improves over Best-of-N by 4.3 points with Gemini-3-flash.
  • Generation and Verification: 45.0% Pass@1 for GPT-5-mini on xbench-DeepSearch contrasts with 80.3% FineVerify selection accuracy, showing that generation and verification are separate bottlenecks.Sampling improves the chance of generating a correct candidate, while fine-grained verification improves the chance of selecting it once present.

5 Benchmark Auditing with Fine-Grained Verification

FineVerify’s fine-grained verification traces make its decisions more interpretable than standard test-time scaling outputs. Auditing BrowseComp-Plus with these traces identified 10 confirmed error cases, including inconsistent questions or evidence and questions with multiple fully supported answers.

  • Interpretability: FineVerify produces fine-grained verification traces that make its decisions more interpretable than methods returning only a final answer or single score.This interpretability is presented as a practical benefit beyond standard test-time scaling methods.
  • Audit results: 10 error cases were identified and confirmed through human review on a 200-question BrowseComp-Plus subset.FineVerify flagged potential errors from its verification traces before human confirmation.
  • Identifying errors in questions: FineVerify flags questions where the annotated ground-truth answer is generated but a fine-grained requirement is not_found or contradicted.These cases indicate possible inconsistencies in the question, answer, or supporting evidence; one example involved different people being the article author and AIA Henry Adams Medal recipient.
  • Identifying questions with multiple correct answers: Repeated sampling and verification without early stopping reveals questions with multiple distinct candidate answers fully supported by evidence.Such cases conflict with BrowseComp’s fact-seeking setting, which assumes a single, indisputable answer.

6 Related Work

Related work spans agentic search, test-time scaling, and self-verification for improving complex language-model reasoning and search. FineVerify is positioned as complementary to stronger search-agent training and uses self-verification differently for agentic-search questions with multiple requirements.

  • Agentic search: Agentic search combines query planning, web browsing, and multi-step evidence synthesis, extending beyond static retrieval-augmented generation.Early work integrated browsing and tool use into reasoning through browser training or interleaved reasoning and actions.
  • Agentic search: Recent systems improve deep search through long chain-of-thought reasoning or self-improving curricula, whereas FineVerify improves agentic search without training a stronger search agent.The supplied passage explicitly describes FineVerify as complementary to these approaches.
  • Test-time scaling: Test-time scaling allocates more inference compute through solution aggregation, search-path expansion, reasoning-length extension, and synthesis of multiple candidate answers for long-horizon search agents.These approaches are presented as common or recent test-time scaling strategies.
  • Self-verification: Self-verification improves LLM reliability in complex reasoning domains including math and coding, and has recently been incorporated into search agents.Prior search-agent uses include reflection and self-generated question checking, while self-verification can also emerge under outcome-based RL.
  • Self-verification: FineVerify uses self-verification differently because agentic-search questions often contain multiple requirements.The supplied passage contrasts this use with prior verification for reflection and self-generated question checking.

7 Conclusion

FINEVERIFY scales test-time compute for agentic search through fine-grained self-verification, decomposing questions into checkable sub-questions and selecting the highest-scoring verified candidate. Across four benchmarks and two models, it improves accuracy over standard test-time scaling baselines and continues benefiting from additional samples.

  • 7 Conclusion: FINEVERIFY decomposes questions into checkable sub-questions, verifies each candidate against them, and selects the highest-scoring candidate answer.This is the framework’s fine-grained self-verification mechanism for scaling test-time compute on agentic search tasks.
  • 7 Conclusion: Across four agentic search benchmarks and two models, FINEVERIFY consistently improves accuracy and outperforms standard test-time scaling baselines.The conclusion reports consistent gains across both benchmark and model dimensions.
  • 7 Conclusion: FINEVERIFY continues to benefit from additional samples.The framework’s accuracy gains persist as more sampled trajectories are used.

Limitations

FineVerify has limitations in tool-use requirements, equal-weight scoring, and evaluation scope. Future work should address weaker tool-using models, adaptive sub-question weighting, and verification of more complex answer formats.

  • Tool-use requirements: FineVerify requires multiple tool calls to retrieve and compare evidence, which may reduce effectiveness for models with weak tool-use ability.Improving verification for weaker tool-using models is left for future work.
  • Scoring design: The scoring function averages judgment scores equally across decomposed sub-questions, although some may matter more for determining correctness.Future work could weight sub-questions by importance or evidence quality.
  • Evaluation scope: The evaluation mainly covers questions with short, single-answer ground truth and excludes broader forms of agentic search results.Answer sets, long-form reports, and structured tables may require different verification and scoring strategies.

A Detailed Experimental Setup · B Algorithm of FINEVERIFY

The experiments evaluate FineVerify across four agentic search benchmarks using GPT-5-mini and Gemini-3-flash, while its algorithm decomposes questions into checkable sub-questions and verifies sampled candidates iteratively. The method caches verification results and returns either the first fully verified answer or the highest-scoring answer after T rounds.

  • A Detailed Experimental Setup: Four benchmarks cover hard-to-find browsing, multi-step information seeking, long-horizon deep search, and realistic assistant tasks requiring reasoning and tool use.The benchmarks are BrowseComp-Plus, DeepSearchQA, xbench-DeepSearch, and GAIA-Search.
  • A Detailed Experimental Setup: 200 questions are sampled for BrowseComp-Plus, which uses an offline human-verified corpus containing positive and negative documents.The benchmark contains browsing questions with compound requirements, and the sample size reflects the high cost of long-horizon agentic search.
  • A Detailed Experimental Setup: 200 questions are sampled for DeepSearchQA, whose tasks require collecting fragmented evidence across diverse fields and have single-answer ground truth.The sampling is also attributed to the high cost of evaluation.
  • A Detailed Experimental Setup: 100 Chinese information-seeking questions from xbench-DeepSearch’s latest 2510 version are evaluated using the original Chinese questions and the same prompts as other benchmarks.The benchmark measures planning, retrieval, and reasoning in long-horizon deep search.
  • A Detailed Experimental Setup: 64 GAIA validation questions form GAIA-Search after filtering for search-related annotations or tools and removing questions requiring vision or file access.GAIA contains realistic assistant tasks requiring reasoning and tool use.
  • A Detailed Experimental Setup: GPT-5-mini and Gemini-3-flash-preview are evaluated through public APIs with high reasoning effort for decomposition, medium effort for generation and verification, and max_output_tokens set to 40000.All other parameters use default settings across methods and benchmarks.
  • B Algorithm of FINEVERIFY: FineVerify decomposes each question into checkable sub-questions, iteratively samples and verifies candidates, caches prior verification results, and returns a fully verified or highest-scoring answer.It returns the first fully verified answer or the highest-scoring answer after T rounds.

C Detailed Information on BrowseComp-Plus Dataset Errors

FineVerify identified 10 confirmed BrowseComp-Plus dataset errors in a 200-question subset, comprising inconsistent question-answer evidence and cases with multiple valid answers. Two reviewers validated flagged cases and revised the annotations, with Table 5 documenting each correction and its rationale.

  • Validation Procedure: Two reviewers labeled a case as a dataset error only when they agreed the original pair was inconsistent, incomplete, or had multiple valid answers.Reviewers inspected original and candidate answers alongside fine-grained verification outputs and could use external tools; agreed cases received revised annotations.
  • Error Analysis: Table 5 lists all 10 confirmed cases with original and revised question-answer pairs, FineVerify output snippets, and revision comments.The table records the reason for each annotation revision.
  • Examples: One revision clarified that the article author and Henry Adams Medal recipient only shared a name, correcting an unsupported identity link.The revised question explicitly states that a person sharing the author’s name received the medal.
  • Examples: One answer was revised to accept Seoul, Ever8 Winners, or Jin Air Green Wings because the clues matched multiple valid team-history answers.FineVerify produced supporting rationales for each candidate answer.
  • Examples: Another revision accepted two book titles because Barbara Hodgson had two distinct books matching the question’s description.The original annotation listed only one of the valid titles.

D Open Web Search Failure Case … Question Decomposition Prompt for BrowseComp-Plus

The paper documents an open-web verification failure caused by evidence hidden behind an interactive webpage, contrasts BrowseComp-Plus with live-web benchmarks, and specifies prompts and decomposition rules for the evaluation pipeline. It also states that LLMs were used only for evaluation and minor editing, not for research ideation or original content.

  • D Open Web Search Failure Case: 99.2% selection accuracy on BrowseComp-Plus versus 89.0% on DeepSearchQA illustrates lower performance when verification requires live web search.BrowseComp-Plus uses a fixed offline corpus, whereas live-web benchmarks require web search.
  • D Open Web Search Failure Case: A correct Finland answer received not_found because 2023 mammography evidence appeared only after an interactive year change that left the URL unchanged.Static page access could observe the default 2022 view but not the required 2023 evidence.
  • E Prompts: BrowseComp-Plus uses embedding retrieval over a fixed offline corpus, so its prompts differ slightly from those for other agentic search benchmarks.The prompt suite covers candidate generation, question decomposition, fine-grained verification, and LLM-as-a-judge evaluation.
  • E Prompts: Candidate-generation, decomposition, and fine-grained-verification prompts are provided separately for BrowseComp-Plus and other benchmarks, while the judge prompt appears in Figure 11.Figures 5–10 document the benchmark-specific prompts.
  • F Use of LLMs: LLMs were used only for automatic evaluation and minor typo or grammar correction, not for research ideas or original content.This defines the stated scope of LLM use in the paper.
  • Question Decomposition Prompt for BrowseComp-Plus: The decomposition prompt instructs the model to produce atomic, self-contained, independently checkable subquestions without solving the original question.Each subquestion should express exactly one verifiable condition and be evaluable as true or false using external documents.
  • Question Decomposition Prompt for BrowseComp-Plus: The prompt forbids adding unstated constraints, requires splitting compound conditions, preserves the original meaning, and uses placeholders for target entities.It also requires distinct placeholders for distinct recurring entities and clear entity grounding without vague references.

Question Decomposition Prompt for Other Agentic Search Benchmarks · Fine-Grained Verification Prompt for BrowseComp-Plus

The prompts first decompose each question into the smallest sufficient set of atomic, self-contained, externally checkable statements. For BrowseComp-Plus, a verifier independently evaluates every subquestion using retrieved evidence, strict candidate handling, and fixed judgments.

  • Question Decomposition Prompt for Other Agentic Search Benchmarks: The decomposition agent rewrites the question as an instantiated claim containing [answer].Its objective is planning verification rather than answering the question.
  • Question Decomposition Prompt for Other Agentic Search Benchmarks: The decomposition produces the smallest sufficient set of statements needed to determine whether [answer] is correct.The prompt is designed to decompose open-web agentic search questions into checkable sub-questions.
  • Question Decomposition Prompt for Other Agentic Search Benchmarks: Each atomic statement expresses exactly one requirement and can be independently verified as TRUE or FALSE using external evidence.Statements must remain self-contained, specific, objective, and clearly verifiable.
  • Fine-Grained Verification Prompt for BrowseComp-Plus: The BrowseComp-Plus verifier assesses whether a PROVIDED CANDIDATE ANSWER satisfies SUBQUESTIONS derived from the original QUESTION.It must examine documents retrieved through the provided tools rather than solve the original question.
  • Fine-Grained Verification Prompt for BrowseComp-Plus: For each subquestion, the verifier searches for evidence and retrieves full documents when relevant snippets are truncated or insufficient.The explanation may guide query formulation but is never evidence; judgments use only retrieved documents.
  • Fine-Grained Verification Prompt for BrowseComp-Plus: The verifier evaluates all subquestions independently without changing, expanding, or reinterpreting their wording or the candidate answer.The strict rules require evidence retrieval for each subquestion unless invalid-candidate handling applies.
  • Fine-Grained Verification Prompt for BrowseComp-Plus: If a candidate is null, empty, not attempted, or otherwise non-concrete, verification is skipped and every subquestion receives not_found.The verifier still outputs all subquestions and an Overall assessment.

Fine-Grained Verification Prompt for Other Agentic Search Benchmarks · LLM-as-a-Judge Evaluation Prompt

The paper uses fine-grained verification prompts that independently assess atomic checkable statements against live web evidence, while a separate LLM judge evaluates final answers against provided correct answers. Both prompts prohibit solving the original question or proposing alternatives, and require structured judgments with explicit handling of insufficient evidence or invalid responses.

  • Fine-Grained Verification Prompt for Other Agentic Search Benchmarks: The verifier assesses whether a candidate answer is correct by checking atomic statements against documents retrieved with web search.It is not tasked with solving the original question or proposing alternative answers.
  • Fine-Grained Verification Prompt for Other Agentic Search Benchmarks: The verifier must evaluate every statement independently without changing, expanding, or reinterpreting the statements or candidate answer.Each statement requires web-search evidence unless invalid-candidate handling applies.
  • Fine-Grained Verification Prompt for Other Agentic Search Benchmarks: Invalid candidates receive not_found judgments for every statement, with verification skipped and all statements still reported.This applies to null, empty, not attempted, descriptive stand-ins, or otherwise implausible candidate answers.
  • Fine-Grained Verification Prompt for Other Agentic Search Benchmarks: Each statement is labeled supported, contradicted, or not_found based only on retrieved documents and their direct relation to the candidate answer.Weak, indirect, ambiguous, or untied evidence must receive not_found rather than contradicted.
  • Fine-Grained Verification Prompt for Other Agentic Search Benchmarks: For supported or contradicted judgments, the verifier cites consulted documents and provides a short direct evidence snippet; for not_found, it explains the insufficiency.The overall assessment must synthesize all per-statement judgments without introducing new evidence or interpretations.
  • LLM-as-a-Judge Evaluation Prompt: The LLM judge grades a response as correct, incorrect, or not attempted after extracting its explanation, final answer, and confidence score.It assesses the final answer against the provided correct answer rather than solving the question.
  • LLM-as-a-Judge Evaluation Prompt: The LLM judge treats the correct answer as the only source of truth and uses the response explanation only to confirm aliases, shortened forms, or naming variants.It must not suggest alternate answers or treat the explanation as evidence for a different answer.
Loading 2606.00660v1…