SearchHorizonBench: A Benchmark for Search Value in AI Agents

1 Introduction

• Search-value prediction targets which questions justify search’s added information cost, as search raises Test-400 success from 69.38% to 73.56% while mean actor tokens rise from 1,069 to 6,829.The introduction frames the decision as trading possible resolution of a missing relation or entity against time and money.Source: §1 · p. 1
• Paired continuations, repeated executions, fixed answers, and recorded costs connect prediction accuracy to decision utility while separating expected-gain error from generation noise.Historical action means and task priors provide references; matched-configuration curves and a decision-information factorial probe training scale and signal access.Source: §1 · pp. 1–2
• On Test-1632, historical correction reduces Brier from 0.2145 to 0.1797, while tested historical predictors explain less than 2% of search-gain variation.Task priors account for 88.9% of the Brier change, and success-level prediction accounts for 99.9%.Source: §1 · p. 2
• At the reference token price, free selection observations yield 2.49 utility points over the best constant action, driven primarily by gain information.Holding costs fixed retains 2.48 points, whereas varying cost information alone gives 0.68 points; a deployable two-answer consistency rule must pay for its probes.Source: §1 · p. 2

2 Related Work

• Retrieval-trigger, search-policy, stopping, and legal-search studies address related decisions, while SearchHorizonBench aligns executions to measure future action value and experience-based estimation.The cited approaches include retrieval triggers or strategy selection [2] [15] [16] [36], reinforcement-learned search policies [17] [47], and stopping methods [18] [22] [30] [34].Source: §2 · p. 2
• Execution-derived utility work covers intervention value, tool-use boundaries, retrieval necessity, evidence contribution, revision effects, and experience-derived skills; this benchmark targets prospective action-value prediction with repeated outcomes and matched historical baselines.The cited lines of work include [46], [50],, [37],, [24], [49], [28], [26], and [48].Source: §2 · p. 2
• Cost-aware control, evaluation budgets, configuration selection, calibration, and statistical estimation provide neighboring foundations for SearchHorizonBench’s evaluation tools.The passage names budget-aware control [11] [23] [32] [43], configuration selection [1], value-estimation tools [12] [19] [40], calibration [10], and statistical methods [3] [6].Source: §2 · p. 2

3.1 A shared state and two executable actions

• Each checkpoint is a public interaction history supporting Think or Search continuations, with actor, instructions, retrieval interface, and remaining budget defining the predicted execution.The main actor uses an 8,192-token completion budget and up to three additional searches; repeated executions share cached evidence responses, and forecasts precede future outcomes.Source: §3.1 · p. 2

3.2 Interpretable probability corrections

• The affine correction standardizes raw action-success forecasts, uses both inputs for each corrected probability, and keeps development-fitted parameters fixed during test execution.The approach uses four development-only folds to select a ridge penalty; Figure 2 describes the Brier decomposition into success-level error, one quarter of gain error, and shared outcome variance.Source: §3.2 · pp. 2–3, Figure 2 · p. 3

3.3 Repeated outcomes measure gain error

• Repeated independent outcomes estimate squared expected gain, enabling unbiased gain-risk estimates for fixed predictions and paired comparisons that cancel a common term.The same construction extends to bounded rewards in [0, 1] for the collection-completion experiment.Source: §3.3 · p. 3

4.1 Questions, histories, and transfer settings

• The benchmark spans Test-400 checkpoints, a 1,632-question screened test set, transfer and retrieval-backend studies, and a collection-completion task with set-F1 reward.Across the resource there are 45,632 distinct executions and 8,880 forecasts covering 3,168 distinct questions.Source: §4.1 · p. 3

4.2 Scoring and comparison costs

• Correctness is scored against frozen reference answers, with automatic scoring for clear cases and semantic judgments for remaining distinct question–answer pairs.Two context-isolated panels reviewed 812 distinct answers, with 95.4% agreement and κ = 0.918.Source: §4.2 · p. 3
• Held-out forecasts and historical corrections are fixed before target execution, and learning curves separate training from evaluation components within the same-configuration bank.Intervals resample support components linked by shared supporting pages, preserving source dependence; reported intervals condition on the fitted predictor.Source: §4.2 · p. 4
• Router utility subtracts token-priced actor and prediction costs from reward, with λ = 0.005 as the focal valuation and additional valuations tested from 0 to 0.02.The conversion is λ = c/v, where c is dollars per thousand total tokens and v is the value of an additional correct answer; deployment costs depend on the actual token mix.Source: §4.2 · p. 4

5.1 Calibration captures task structure

• On Test-1632, the frozen map improves Brier from 0.2145 to 0.1797, while task-stratum means recover 88.9% of that improvement.The public-prefix ridge scores 0.1796 and is the deployable reference; task and metadata priors use evaluator information.Source: §5.1 · p. 4, Table 1 · p. 4

5.2 Search gains vary widely across questions

• Search-gain standard deviation is 21.4 percentage points, while the historical map and public-prefix ridge explain −0.17% and +0.10% of gain variance, respectively.Both gain-explained-variance intervals include zero: [−1.64, 0.87]% and [−1.36, 1.17]%.Source: §5.2 · p. 5

5.3 The gain-prediction gap persists with more training

• Public-feature ridge improves from −1.67% gain R^2 at 120 questions to +0.72% at 1,100, with final interval [−1.78, 3.09]%.The tested model families remain near the constant-gain reference across matched-configuration training budgets.Source: §5.3 · p. 5, Figure 4 · p. 5

5.4 Gain information drives price-sensitive opportunity

• At a token price of 0.005, using both query-specific gains and costs yields +2.49 utility points over the best constant, while gain information with fixed costs yields +2.48.Adding cost information to gain information changes utility by +0.012 points, with interval [−0.025, 0.051].Source: §5.4 · p. 5, Figure 5 · p. 6

5.5 Useful decision signals must cover their acquisition cost

• Two-probe consistency yields −1.25 utility points at price 0.005, with interval [−2.38, −0.35], after its probes are charged.The probes consume 2,210 tokens, leaving 1,241 net tokens saved at a 1.87-point success cost.Source: §5.5 · p. 6

5.6 A common benchmark spans execution settings

• The benchmark extends its success, gain, and decision measurements across retrieval, model-family, budget-intervention, and collection-completion settings.For example, raising the search limit from three to six at 8k tokens raises length failures by 2.5 points, while a 16k budget removes that increase.Source: §5.6 · p. 6

• The value scorer reports success error and generation-noise-corrected gain error, while the policy scorer charges prediction and continuation tokens.Saved baselines, fixed priors, and reusable splits support direct method comparisons.Source: §6 · p. 6
• Researchers fit forecasters on development outcomes and submit action-success probabilities or signed gain predictions for held-out states.Evaluation uses separate outcome records and supporting-page groups.Source: §6 · p. 6
• Scoring success, gain, and utility on matched executions makes a forecaster’s contribution to search decisions directly testable.Source: §6 · p. 6

• On 1,632 held-out questions, historical calibration improves Brier error by 16.2%, with task priors accounting for 88.9% of that change.Source: §7 · p. 6
• Search gains have a standard deviation of 21.4 percentage points, while tested historical estimators explain less than 2% of this variance in point estimates.Source: §7 · p. 6
• 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.Source: §7 · p. 6

A Data and Execution Settings

• The resource contains 45,632 distinct executions, 8,880 forecasts, and 3,168 questions, with shared STOP executions counted once.Released records include histories, actor identity, action definitions, reference answers, observed rewards, resource measurements, prediction matrices, judgments, pricing settings, and manifests.Source: A Data and Execution Settings · p. 8
• Test populations span HotpotQA and MuSiQue strata, source-qualified Test-1632 questions, Natural Questions, actor–retriever states, and DeepSearchQA collection tasks.Test-400 checkpoints include 400 initial states, 377 states after one search, and 171 after two; later checkpoints describe agents that reach them.Source: A Data and Execution Settings · p. 8
• The factorial study crosses total completion budgets of 8,192 and 16,384 tokens with three and six permitted searches; Tavily uses basic search with five snippets.Component comparisons normalize DeepSeek and Serper results to five documents and 1,500 characters per document.Source: A Data and Execution Settings · p. 8
• DeepSeek requests omit temperature, top-p, and seed, and historical responses do not record the effective sampler configuration.The paper distinguishes logged request settings from provider behavior documented on October 25, 2026; repeated requests with cached evidence are treated as conditionally independent generations, while identical answers share a correctness judgment.Source: A Data and Execution Settings · p. 8
• A separate Qwen3-4B forecaster uses the same public inputs as DeepSeek forecasters, and its 640 test outputs include 610 valid answers.Nine outputs fail by length and 21 are malformed; both failure types receive zero reward.Source: A Data and Execution Settings · p. 8

B Estimators and Inference

• Calibration alternatives include logistic, beta, and isotonic maps, while direct-gain models predict action differences and residual models adjust historical maps.Shared-input maps use both raw probabilities; independent affine maps use one probability per action, and all fits use development labels.Source: B Estimators and Inference · p. 8
• Public-prefix controls use action probabilities, text lengths, lexical evidence gaps, and query or document novelty, with development folds selecting regularization.The evidence gap is the fraction of question terms absent from tool text; novelty measures compare queries or documents with earlier observations.Source: B Estimators and Inference · p. 8
• Learned-level controls assign historical mean gain, while the zero-gain control gives both actions the same learned level and own-history means provide a constant-gain comparator.Clipping reconstructed probabilities can alter intended levels and gains; the stated reverse Flash mean-gain control is affected on 31 of 320 questions.Source: B Estimators and Inference · pp. 8–9
• The Test-1632 level-risk contrast separates squared mean-bias difference (−0.000293) from variation and covariance (−0.034470).The shared variance of observed rewards cancels, while the latter term includes task differences represented by stratum controls.Source: B Estimators and Inference · p. 9
• Explained gain variation is estimated as 1 minus gain loss divided by gain variance, with a cross-draw second moment removing within-question generation noise.Uncertainty procedures retain negative skill estimates; support-page components define bootstrap units, while learning curves reuse completed executions under component-disjoint fitting and evaluation.Source: B Estimators and Inference · p. 9
• Text and public-signal models use frozen MiniLM embeddings, ridge or forest heads, and fine-tuned heads to predict action probabilities or their difference.Confidence, entropy, novelty, and evidence-gap signals use public observations; evaluator-stratum means act as a task-category control.Source: B Estimators and Inference · p. 9

C Answer Scoring and Evidence

• Reference-equivalence scoring assigns zero to empty, UNKNOWN, malformed, length-failed, or refused answers, while evidence-support auditing checks requested answers and added factual claims.Actor-matched gain-contrast upper bounds are 0.1583 against the mean-gain comparator and 0.2054 against zero gain; uncertain audit labels are handled with shared-label bounds.Source: C Answer Scoring and Evidence · pp. 9–10
• Normalized containment yields mean gains of +0.0486 on Test-1632 and +0.0556 on Test-400, while the main evaluation uses reference-equivalent correctness.Literal case-insensitive containment also gives positive point gains of 0.0505 and 0.0619, respectively.Source: C Answer Scoring and Evidence · p. 10
• The original 400-question source audit classifies 270 references as supported, 106 insufficient, six ambiguous, and 18 contradicted.The Natural Questions audit covers 200 sampled executions, with panel agreement of 95.5% and κ=0.899; 47 and 44 executions remain unresolved.Source: C Answer Scoring and Evidence · p. 10
• The 270-question source-supported subset of the original 400 has Brier values 0.1796 for global means, 0.1637 for stratum means, and 0.1634 for the map.Its gain risks are 0.0571, 0.0555, and 0.0576, respectively; these estimates supplement the full-cohort analysis because source support changes the population.Source: C Answer Scoring and Evidence · p. 10
• In 475 sampled answers accepted by both semantic graders but scored zero by exact match, panels support 367 and 373 target answers and leave 108 and 102 unresolved.For the 15 containment-positive, exact-match-zero cases, each panel confirms ten as equivalent and leaves five unresolved.Source: C Answer Scoring and Evidence · pp. 10–11, Figure 7 · p. 10
• Allowing all source-flagged Test-400 labels to vary gives adverse intervals [0.0031, 0.0373] for gain-minus-raw and [0.0223, 0.0577] for Brier-minus-mean.The source-supported subset retains a negative gain-minus-raw interval; Natural Questions point-projection differences and shared-label bounds remain population- and scoring-specific.Source: C Answer Scoring and Evidence · p. 11

D Transfer and Supervision

• Source corrections reuse earlier executions on target forecasts, while component controls compare same-actor history, direct prediction reuse, historical means, and three-pair composition on fixed outcomes.The component study isolates backend effects through paired executions on the same questions; actor changes acquire new STOP outcomes, whereas backend changes reuse identical STOP outcomes.Source: D Transfer and Supervision · p. 11
• Three-pair composition observes A/X, A/Y, and B/X outcomes across 128 questions, using 2,560 distinct outcomes to compose gains.A single-pair map costs 1,024 outcomes; reverse-Flash acquisition costs 1,590,189 tokens for same-actor history and 4,712,303 for composition.Source: D Transfer and Supervision · p. 11
• The actor-matched map-minus-mean gain contrast is −0.0173 under reference equivalence but +0.0113 under exact match, with both intervals excluding zero.Independent audit shared-label bounds retain both signs, showing that the specified answer objective changes the measured contrast.Source: D Transfer and Supervision · p. 11
• The fixed STOP16 rule uses 46.9% of paired16 incremental tokens and has Brier and gain differences of +0.0036 and +0.0020 against paired offset.Its Brier difference from the fixed source map is +0.0153.Source: D Transfer and Supervision · p. 11
• For ClueWeb and FineWeb, local affine Brier differences are −0.0565 and −0.0483; the independent Qwen forecaster’s gain risk is 0.0322 versus 0.0315 for historical mean.The indexed-source study uses 32 local development states and 64 test states while retaining original shared STOP draws.Source: D Transfer and Supervision · p. 11
• At forty questions, historical120 minus target40 Brier is −0.0110, while SEARCH alone gives −0.0103.Training-subset variability accounts for 0.0083 of the 0.0110 gap in the squared-loss decomposition.Source: D Transfer and Supervision · p. 11

• Two-probe consistency selects THINK on agreement between two valid normalized answers and SEARCH otherwise; its cost includes both probes and one selected continuation.UNKNOWN and failed outputs count as disagreement, and results average all 36 paired splits.Source: E Decision and Collection Rewards · p. 11
• The sample-informed selector uses two labeled draws per action, evaluates the selected action on the remaining pair, and provides a lower-bound diagnostic for ideal free-probe value in expectation.Deployed rules pay for information acquisition.Source: E Decision and Collection Rewards · p. 11
• At the focal price, adding query-specific gains to cost information improves held-out utility by 1.81 points, with interval [1.10, 2.65].Source: E Decision and Collection Rewards · p. 12
• The zero-price ideal-oracle plug-in range is [0, 0.0823], using Test-1632 point moments b𝜃 = 0.0490 and mean gain 0.0568.This range concerns the ideal zero-price oracle, while achieved disjoint-draw utility is reported at specified token prices.Source: E Decision and Collection Rewards · p. 12
• At λ = 0.005, the Test-400 affine policy’s utility difference from SEARCH is −0.0148, with interval [−0.0258, −0.0062].The Test-1632 text policy has success 69.05% at 5,143 tokens, against SEARCH’s 71.58% at 7,613 tokens; its utility difference is −0.0129 with interval [−0.0251, −0.0004].Source: E Decision and Collection Rewards · p. 12
• Collection rewards use set precision, recall, and F1 against curated atomic reference items; STOP cancels the pending query, while SAME and SWITCH execute it through DeepSeek and Serper.The query and 8k completion budget are shared, and gain loss averages SAME-minus-STOP and SWITCH-minus-STOP risks.Source: E Decision and Collection Rewards · p. 12
• The collection selects 128 tasks from 225 candidates, yielding 179 valid pending-query states and 1,536 formal outcomes, including 1,279 valid outputs, 244 invalid outputs, and thirteen length failures.Observed-URL/shared-entity groups separate development and test; the three-search development probe remains outside the formal test comparison.Source: E Decision and Collection Rewards · p. 12
• The selected query-aware fit chooses the mean guard, reducing raw gain risk by 64.9%.Query-hidden gain and discovery-rate controls remain separate estimators.Source: E Decision and Collection Rewards · p. 12