TL;DR
This paper introduces a sequential decision framework that formalizes autonomous, LLM-guided search as a series of strategic choices. By abstracting search into two primitive actions—select (judging a document) and spawn (generating a new query or ranking)—the authors provide a principled way to evaluate and compare the complex "deep research" policies used by modern AI agents.
What Problem Does This Paper Address?
Traditional Information Retrieval (IR) evaluation typically focuses on a single, static ranked list: you give a system a query, it gives you a list, and you measure how good that list is. However, modern "deep research" agents and Retrieval-Augmented Generation (RAG) systems don't work this way. They are iterative; they generate a query, read some documents, realize they need more information, and reformulate their search.
Until now, we’ve lacked a formal language to describe and evaluate these autonomous search policies. If Agent A decides to read 20 documents before trying a new query, and Agent B decides to try a new query after every 5 documents, how do we systematically determine which strategy is better? This paper fills that gap by framing search as a sequential decision problem where an agent must decide how to best allocate its limited "judging effort" to find relevant information.
Methods
The authors propose a framework where a search process is modeled as a policy $\pi$ operating in an environment. The state of this environment includes all ranked lists generated so far, which documents have been seen, and the information gathered from them.
The policy chooses between two fundamental actions at each time step:
select(i): The agent chooses an existing ranked list $i$ and examines the next unseen document.spawn: The agent creates a new ranked list, typically by using an LLM to reformulate the query based on what it has learned so far.
This abstraction allows the authors to map diverse historical and modern retrieval strategies into a single table of policies:
The goal of any policy is to maximize a reward function, which in this study is defined by High-Recall Information Retrieval (HRIR)—finding as many relevant documents as possible within a fixed budget of LLM judgments.
Datasets
The experiments were conducted using the TREC Deep Learning 2019 collection. To simulate the search process:
- LLM Judges: GPT-4o-mini was used to provide relevance judgments for documents.
- LLM Spawners: GPT-5 (via the DSPy framework) was used for complex tasks like query reformulation.
- Retrieval Pipelines: The authors tested four different backends: BM25, SPLADE-v3, TCT-ColBERT-v2, and a "Hybrid" two-stage pipeline that reranks pooled results using MonoT5 and DuoT5.
Key Insights and Ideas
- Search as a Policy, Not a Ranking: The most significant shift is treating search as a behavioral policy. This moves evaluation away from "how good is this list?" to "how good is this agent's decision-making process?"
- The Power of Multi-Armed Bandits: By viewing each ranked list as an "arm" in a bandit problem, strategies like Thompson Sampling can be used to balance exploitation (reading more from a list that is currently yielding hits) and exploration (spawning a new query to find documents in a different part of the collection).
- Retriever vs. Policy: The experiments show that performance is a product of both the underlying retrieval engine and the exploration policy. A great retriever with a poor exploration policy can be outperformed by a mediocre retriever with a smart policy.
- Separation of Concerns: The framework separates how a query is reformulated (the
spawnimplementation) from when it should be reformulated (the policy $\pi$).
Key Results
The authors compared 16 different combinations of retrieval pipelines and policies.
Key quantitative findings include:
- Best Overall: The combination of SPLADE + Query Reformulation + Move-to-Front (MTF) achieved the highest recall, significantly outperforming standard adhoc search baselines.
- Efficiency Gains: Adhoc search (judging a single list top-down) was consistently the least efficient. Policies that allowed for "spawning" new trajectories were much better at converting LLM judgments into discovered relevant documents.
- Batch vs. On-the-fly: Interestingly, committing to a batch of reformulations upfront (Query Reform + MTF) was often more judgment-efficient than spawning new queries one-by-one as the search progressed.
Limitations and Future Work
- Simplified Costs: The framework currently treats every LLM judgment as a "unit cost." In reality, costs vary based on prompt length and model choice.
- Learning to Search: While the paper provides the framework for evaluation, it doesn't yet focus on training policies. The authors suggest that Reinforcement Learning (RL) could be used to learn optimal
select/spawnbehaviors directly from the reward signal. - Task Variety: The experiments focused on high-recall retrieval. Future work could apply this to "nugget-based" retrieval, where the goal is to find diverse pieces of information to answer a complex question rather than just finding every relevant document.
Summary updated