SearchHorizonBench: A Benchmark for Search Value in AI Agents

SearchHorizonBench. A Benchmark for Search Value in AI Agents. By Jingjie Ning and two others, from Carnegie Mellon University. Published on the twenty-sixth of October.

An AI agent has to decide when one more search is worth what it costs. The probability of answering successfully tells you how hard a question is. It does not tell you what another search would add, and that additional benefit is what the decision actually turns on. SearchHorizonBench is built for learning and evaluating that quantity, search value, from execution experience.

Two things are measured, and linked. One is prediction quality: how well an estimator forecasts the gain from searching, scored with Brier error among other things. The other is decision utility: how much better an agent does when it acts on those forecasts. Paired continuations and repeated executions separate the expected gain from search from plain generation noise, and connect the first measure to the second.

The resource holds forty-five thousand six hundred and thirty-two executions across three thousand one hundred and sixty-eight questions. Of those, one thousand six hundred and thirty-two questions are held out. Matched configuration learning curves probe the results across training scales.

On the held-out questions, historical calibration cuts Brier error by sixteen point two percent, with the improvement concentrated in success-level information. Search gains vary widely, with a standard deviation of twenty-one point four percentage points, and the historical estimators tested explain less than two percent of that variance in point estimates. At the reference token price, free selection observations yield a utility opportunity of two point four nine points over the best constant action, driven mainly by information about gain.

Predicting success, in short, is the easier half. Predicting what a search will add is where the room for improvement lies. Reusable histories, frozen splits, strong baselines and scoring tools are offered as a common foundation for building value-aware search agents.