SearchHorizonBench Teaches AI Agents When Another Search Is Worth It

Introduction

For an AI agent, more search is not automatically better. Each additional retrieval step consumes tokens, adds latency, and may incur tool costs. Stopping too early, however, can leave the agent without information that would materially improve its answer. The key decision is therefore not simply how difficult a question is, but how much another search is expected to help.

SearchHorizonBench is designed to evaluate that decision. The benchmark separates answer-success probability from search gain. The former reflects the underlying difficulty of a question; the latter estimates the additional improvement that may result from continuing the search process.

Key points

• Execution-based scale: The resource contains 45,632 executions across 3,168 questions, with 1,632 held-out questions used to test generalization.
• Noise-aware measurement: Paired continuations and repeated executions help distinguish the benefit of an additional search from randomness in model generation.
• Calibration improves, but gain prediction is weak: Historical information reduces Brier error by 16.2%, with the improvement concentrated in success-level information. Yet search gains have a 21.4-percentage-point standard deviation, and the tested historical estimators explain less than 2% of that variance in point estimates.
• Value can change the policy: At the reference token price, access to free selection observations creates a 2.49-point utility opportunity over the best constant action. The opportunity is driven mainly by information about search gains.
• A reusable evaluation foundation: Frozen splits, reusable histories, strong baselines, and scoring tools make it easier to compare future value-aware search policies.

Why it matters

The benchmark moves agent evaluation beyond the question of whether a system can eventually produce a correct answer. Two questions may have similar success probabilities while differing sharply in whether another search is worthwhile. An agent that cannot identify this difference may waste its budget on low-value retrieval or stop at precisely the point where more information would matter most.

The reported results are also a useful warning against overstating what historical data can deliver. Past executions improve calibration of overall success, but they provide very limited point prediction of the actual gain from another search. Future agents may therefore need to condition on what earlier searches returned, where the agent is in its workflow, and the cost of additional computation. SearchHorizonBench offers a common way to measure those trade-offs rather than treating search as an unpriced binary choice.

Hugging Face Daily Papers