SearchHorizonBench: A Benchmark for Search Value in AI Agents

AI summary

Overview

Research area: Evaluation of AI search agents — specifically, benchmarking when an agent should run another web search versus answer from what it already has, with an emphasis on probability calibration and decision utility.

Technical level: Advanced. The paper leans heavily on Brier-score decomposition, U-statistics for variance correction, bootstrap resampling over grouped "support components," and a factorial analysis of decision information.

Scope: A benchmark and evaluation framework (SearchHorizonBench) built from 45,632 paired agent executions over 3,168 questions, designed to separate whether an agent can predict question difficulty from whether it can predict the marginal value of one more search.

What This Paper Is About

AI agents that use web search have to decide, at each step, whether another retrieval is worth its cost. Existing evaluations mostly measure whether the agent gets the answer right, which mostly reflects how hard the question is — not whether the agent knows that a particular extra search will help. This paper builds a benchmark where the same saved conversation state is continued both with and without search, repeatedly, so the expected benefit of searching can be measured separately from random variation in the model's outputs. The goal is to give researchers a common testbed for predicting that benefit and for turning predictions into better search/stop decisions.

Key Contributions

1. A paired-execution benchmark resource. 45,632 distinct executions and 8,880 forecasts across 3,168 questions, where every saved checkpoint supports both a THINK continuation (answer from existing evidence) and a SEARCH continuation (retrieve, then answer), with repeated outcomes, frozen reference answers, and recorded token costs. Configurations span the deepseek-flash and deepseek-v4-pro actors, a Qwen3-4B cross-family extension, multiple retrieval backends (DeepSeek search, Serper, Tavily histories, ClueWeb22, FineWeb), 8,192/16,384-token budgets, and three/six search limits.

2. A decomposition that attributes calibration gains to difficulty versus gain. For predicted action probabilities, average Brier error splits into a success-level term, one quarter of the gain-error term, and a fixed outcome-variance term that cancels in paired comparisons. This lets the paper say precisely how much of a Brier improvement came from knowing which questions are hard versus knowing which questions benefit from search.

3. A noise-corrected estimator of gain-prediction skill. A U-statistic built from independent outcome pairs gives an unbiased estimate of squared expected gain, so reported gain risk is not inflated by stochastic generation. This is what makes "explained variance" for search gain a meaningful reported quantity.

4. A decision-utility evaluation, including the cost of acquiring the signal. A router objective charges actor and prediction tokens against success, and a decision-information factorial crosses query-specific gain estimates with query-specific cost estimates. The two-probe consistency rule is scored after paying for both probes, making signal acquisition part of the benchmark rather than an externality.

Main Findings

• Search helps, and costs. In Test-400, permitting search raises reference-equivalent answer success from 69.38% to 73.56% while mean actor tokens rise from 1,069 to 6,829.

• Calibration mostly captures task difficulty. On 1,632 held-out questions, historical calibration reduces Brier error by 16.2%, moving from the global prior's 0.2145 to the calibrated map's 0.1797 (paired interval [-0.0530, -0.0169]). Task priors account for 88.9% of that improvement, and the success-level term accounts for 99.9% of the map's -0.034800 Brier difference (contributing -0.034763); the gain term contributes only -0.000037.

• A deployable feature-based baseline matches the calibrated map. Public-prefix ridge scores 0.1796 versus the map's 0.1797, using only observable history features and forecasts.

• Task-level structure is strong in some strata and weak in others. On two-hop MuSiQue the map scores 0.2239 against stratum means' 0.2457 (interval [-0.0356, -0.0075]), but on HotpotQA comparison questions — where success exceeds 95% — the task prior's 0.0387 Brier beats the map's 0.0579. The aggregate map-minus-stratum difference is -0.0039 with interval [-0.0197, 0.0078].

• Search gain genuinely varies by question. Reference-equivalent correctness gives an estimated mean gain of 0.05675, gain variance of 0.0458 (interval [0.0364, 0.0560]), and a standard deviation of 21.4 percentage points — establishing a real per-question target.

• Almost none of that variation is captured. Tested historical estimators explain less than 2% of the variance in point estimates. The calibrated map's gain skill is -0.17% (interval [-1.64, 0.87]%) and public-prefix ridge reaches +0.10% ([-1.36, 1.17]%).

• More training data does not close the gap. In the matched-configuration learning curves (20 to 1,100 training questions, same Flash actor and DeepSeek backend), public-feature ridge improves from -1.67% gain R² at 120 questions to +0.72% at 1,100 (final interval [-1.78, 3.09]%), raw-score ridge reaches +0.27%, and the guarded text model falls back to predicting the mean at the largest budget.

• Gain information, not cost information, drives decision value. At the focal token price of 0.005 per thousand tokens, gain information with fixed costs yields +2.48 utility points over the best constant action (interval [1.28, 3.52]); cost information with fixed gain yields +0.68 ([-0.64, 1.73]); both together yield +2.49, and adding cost to gain changes utility by only +0.012 ([-0.025, 0.051]).

• Free selection observations bound a modest opportunity. With selection draws excluded from acquisition cost, the selector's gap to an ideal exact-value policy is -0.36 points at zero token price ([-1.42, 0.55]).

• Cheap heuristics do not pay for themselves. Two-probe consistency (select THINK when two independent THINK answers agree) sees agreement in 65.0% of probe pairs. It saves 3,451 tokens relative to always SEARCH before charging for probes, the probes consume 2,210, leaving 1,241 net tokens saved — but at a 1.87-point success cost, giving utility -1.25 points at price 0.005 ([-2.38, -0.35]).

• The framework transfers across settings. Indexed retrieval gives Brier 0.1417 on ClueWeb and 0.1498 on FineWeb against historical means of 0.1982 and 0.1981. Budget interventions separate evidence effects from generation capacity: raising the search limit from three to six at 8k tokens increases length failures by 2.5 points, while a 16k budget removes that increase.

Methodology in Plain English

The design rests on a simple trick: never let the two options see different pasts. The researchers save an agent's conversation at a legal decision point, then fork it. One branch keeps thinking with what it has; the other runs a search first. Both branches are executed multiple times from the identical saved history, with cached retrieval responses so repeated runs measure model variation rather than changing evidence. Correctness against a frozen reference answer becomes a 0/1 outcome, and the average difference in success across branches is the search gain for that question.

A separate forecaster model sees only the public history, the actor identity, and the action instructions — never the future — and returns success probabilities for THINK and SEARCH. Those two numbers are then used in three ways: to predict correctness under each action, to predict their difference, and to actually route the decision.

The statistics handle two problems. First, because two probabilities are being scored, the squared error decomposes cleanly into a "how hard is this question" component and an "does search help here" component, with a shared noise term that drops out when two predictors are compared on the same executions. Second, because the model's answers are stochastic, the observed difference between two success rates is noisy; the paper uses a U-statistic over independent outcome pairs to estimate the squared expected gain without bias, so a predictor's gain skill is not penalized for randomness it cannot control.

For decisions, routing utility subtracts priced tokens from success, evaluated across five token prices with 0.005 as the focal value. The factorial then swaps in fixed versus query-specific estimates of gain and cost independently, on the same held-out rewards and costs, so the utility difference isolates the value of each kind of information. Uncertainty comes from 10,000 bootstrap resamples of supporting-page groups rather than individual questions, preserving source dependence. Every fit uses development outcomes only, and Test-1632 questions were screened (8,000 candidates, 3,380 independently reviewed, 2,325 supported) and stratified with equal weights.

Why This Matters

Impact on research. The paper reframes search-agent evaluation around a quantity that accuracy metrics hide: the marginal value of one more retrieval. By showing that difficulty prediction is largely solved by task priors while gain prediction sits near zero skill even at 1,100 training questions, it identifies a concrete, measured gap rather than a speculative one. The released paired executions, frozen splits, and noise-corrected scoring turn "should the agent search?" into a reproducible benchmark target that new methods can be compared against directly.

Real-world applications:

• Cost-aware assistants and deep-research tools, where each search call has a real bill and the agent must decide when evidence is sufficient.
• Enterprise retrieval over internal document stores and indexes, where the same stop-or-search decision recurs and licensed search APIs carry per-call costs.
• Legal, medical, and financial research workflows, where an unnecessary retrieval is cheap but a wrong early stop is expensive, and where the price ratio between tokens and errors differs sharply from consumer settings.
• Model and agent routing in production, where the decision-information factorial maps onto the practical question of whether to invest in per-query cost telemetry or per-query benefit estimation.

Industry relevance. The result that cost information adds only +0.012 utility points on top of gain information is directly actionable for teams building search agents: effort spent instrumenting per-query token costs buys little compared with effort spent predicting whether search will help. The finding that a lightweight public-feature ridge matches a learned calibration map, and that text models fall back to the mean, also suggests where marginal engineering effort is and is not rewarded at current data scales.

Future Directions

• Closing the gain-prediction gap. Gain skill stays within roughly ±1–3% across every tested estimator and training budget up to 1,100 questions. Richer state representations, explicit reasoning about missing relations, or training signals beyond outcome supervision are the obvious next candidates.
• Cheaper signal acquisition. Two-probe consistency pays 2,210 probe tokens to save 3,451 and ends at -1.25 utility. Designing decision rules whose evidence gathering costs less than the information it buys is an open engineering problem.
• Extending beyond correctness to other reward definitions. The collection study uses set F1 over three actions (32 development, 96 test tasks, 1,536 outcomes), and the authors note each scoring rule defines its own reward and gain population. How gain predictability behaves under recall-oriented or partial-credit rewards is not established.
• Cross-family and cross-backend generalization. Only one non-DeepSeek family is included (Qwen3-4B, with 640 test outputs: 610 valid, nine length failures, 21 malformed, all scored zero reward). Whether gain-prediction difficulty is a property of the task distribution, the retrieval backend, or the specific actor remains unresolved, as does the effect of the temperature/top-p settings the paper notes are not echoed in historical responses.

Target Audience

Researchers and engineers working on agentic retrieval, tool-use policies, and adaptive RAG, particularly those who need an evaluation harness rather than another accuracy leaderboard. It suits readers comfortable with probability calibration and causal/decision-analytic framing — Brier decomposition, potential outcomes, bootstrap inference — and will be most useful to teams deciding whether to build, buy, or skip per-query value estimation in a deployed search agent. Readers seeking a plug-and-play prompting recipe will find the paper's negative results (near-zero gain skill, unprofitable consistency probes) more immediately useful than any positive method.

Authors’ abstract

AI agents must decide when another search is worth its cost. Answer-success probabilities capture question difficulty, while this decision requires estimating the additional benefit of search. We introduce SearchHorizonBench, a benchmark for learning and evaluating search value from execution experience. Paired continuations and repeated executions separate expected search gain from generation noise and connect prediction quality to decision utility. The resource contains 45,632 executions across 3,168 questions. On 1,632 held-out questions, historical calibration reduces Brier error by 16.2%, with the improvement concentrated in success-level information. Search gains have a standard deviation of 21.4 percentage points, and tested historical estimators explain less than 2% of this variance in point estimates. Matched-configuration learning curves probe this distinction across training scales. At the reference token price, free selection observations yield a 2.49-point utility opportunity over the best constant action, driven primarily by gain information. Reusable histories, frozen splits, strong baselines and scoring tools provide a common foundation for developing and evaluating value-aware search agents.