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

Scaling Agentic Search via Fine-Grained Sub-Question Verification

When AI agents search the web, they often get confused by complex questions. Instead of just guessing if an answer is right, FINEVERIFY breaks the question into small, simple checks. It verifies each one individually to pick the best answer.

In modern agentic search, LLM agents issue queries, browse pages, and synthesize evidence. We are moving toward "scaling test-time compute." This means spending more FLOPs (floating-point operations, or computational effort) during inference to find better answers. This works for math or coding. However, agentic search is harder. Correct answers are often sparse. The search space is also massive. Most current scaling methods rely on frequency-based voting or self-reported confidence. Both are notoriously unreliable in long-horizon tasks (tasks requiring many sequential steps).

The Problem

Standard scaling for agentic search uses two patterns. First is Majority Voting (picking the most common answer). Second is Best-of-N (picking the answer with the highest self-reported confidence). In theory, sampling many trajectories should reveal the correct answer. In practice, agentic search produces "plausible distractors." These are answers that look correct but fail on subtle, compound requirements.

As shown in, coarse selection methods struggle.

Majority voting can favor high-frequency incorrect answers. These answers might satisfy only part of a question. Single-score selection, like "Confidence Verify," depends on model calibration. Calibration is the model's ability to accurately report its own certainty. If a model is poorly calibrated, it picks wrong answers confidently. It might satisfy easy constraints while ignoring harder ones. Collapsing multi-step search into one score forces the model to perform too many implicit checks. This creates a noisy signal that is hard to compare across candidates.

How It Works

The authors propose FINEVERIFY. It shifts selection logic from "how confident is this answer?" to "how many explicit requirements does this answer satisfy?" The architecture follows a three-stage process .

1. Question Decomposition: The verifier decomposes the question into $m$ atomic, checkable sub-questions ($Q = {c_1, c_2, \dots, c_m}$). Each sub-question is a single, verifiable condition.
2. Fine-Grained Verification: The verifier retrieves evidence for each candidate answer. It assigns one of three judgments to every sub-question: supported, not_found, or contradicted. This categorization creates a cleaner signal than a single probability score.
3. Aggregated Scoring: These judgments become a scalar score ($s_t$). The authors use a rule-based mapping. They found that a strict mapping is most robust [Table 2]. In this mapping, supported equals 1, while not_found and contradicted both equal 0. The final score is the average of these values.

The framework includes an early-stopping mechanism. If a candidate reaches a perfect score of 1.0, the system returns it immediately. This saves compute. It also uses a caching layer. Since the sub-question set is fixed for an input, the system reuses results for repeated candidates.

Numbers

The main takeaway is the efficiency of scaling. FINEVERIFY scales more effectively than traditional methods as you add samples. On the BrowseComp-Plus benchmark using GPT-5-mini, the authors show significant gains. With 12 samples, FINEVERIFY helps the smaller model surpass the performance of the frontier GPT-5 model .

The accuracy deltas are meaningful. With only four sampled trajectories, FINEVERIFY improves GPT-5-mini average accuracy by 8.2 points (from 59.2% to 67.4%). For Gemini-3-flash, it improves average accuracy by 5.6 points. Regarding the cost-accuracy tradeoff on DeepSearchQA, FINEVERIFY outperforms "Solution Aggregation." It achieves this while costing less due to early stopping and caching.

Reliability is also improved. The authors measured "selection accuracy." This is the probability of picking the correct answer when at least one correct answer exists in the pool. FINEVERIFY reaches 90.7% selection accuracy for GPT-5-mini. This significantly outperforms Best-of-N and Confidence Verify [Table 3]. This suggests that the bottleneck is often selection, not just generation.

What's Missing

There are gaps a practitioner should consider.

First, the framework depends on tool-use ability. Verification requires multiple calls to retrieve and compare evidence. Models with weak reasoning or poor instruction-following may produce noisy judgments. The authors note this limitation.

Second, the scoring function is blunt. It treats every sub-question with equal weight. In complex queries, some constraints are more critical than others. If a model fails a vital constraint but passes five trivial ones, the average score might still stay high. The paper does not address weighted scoring.

Finally, "open-web" search is messy. As seen in, verifiers can fail on interactive webpages.

Some evidence is hidden behind UI elements like dropdown menus. These interactions often do not change the URL. Since the verifier relies on static page retrieval, it cannot see this data.

Should You Prototype This

Yes, if you are building deep research agents. The core insight is that decomposition beats holistic scoring. The implementation is straightforward. You need a decomposition prompt, a verification prompt, and a simple aggregator.

The authors provided code and data at https://github.com/XuZhao0/fineverify. If your system relies on majority voting or self-reported confidence, you may be losing accuracy. Start by implementing decomposition and rule-based scoring. The jump in selection reliability should be immediate.

Figures from the paper