A Sequential Decision Framework for Evaluating LLM-Guided Search

Siqing Huo, Andrew Parry, Debasis Ganguly, Mark Smucker, Charles L. A. ClarkearXiv 2026 · arXiv

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:

  1. select(i): The agent chooses an existing ranked list $i$ and examines the next unseen document.
  2. 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:

Summary of search policies expressed as select and spawn actions.

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 spawn implementation) from when it should be reformulated (the policy $\pi$).

Key Results

The authors compared 16 different combinations of retrieval pipelines and policies.

Figure 1: Comparison of recall@𝑅across different search runs.

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.
Figure 3: Mean recall (%) versus mean number of LLM rel- evance judgments consumed per query, for each retrieval pipeline (panels), judging budget (color), and policy (marker shape), evaluated under a global judging budget.

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/spawn behaviors 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

Abstract

Recent systems applying retrieval-augmented generation (RAG) and "deep research" iteratively generate queries, retrieve documents, and examine their contents, using the resulting information to guide subsequent search steps. When this process is carried out autonomously rather than by a human searcher, the system must make explicit decisions about which search trajectories to explore and what objective the search is intended to optimize. We introduce a simple framework for reasoning about such search policies, providing a principled approach to evaluation. The framework models the search environment as a set of ranked lists and represents behavior using two primitive actions: select, which advances judgment through an existing ranking, and spawn, which generates a new ranking through query generation or reformulation. Each action produces a document to inspect, yields information that updates the search state, and contributes a reward for a task-specific objective. Within this abstraction, a variety of existing retrieval strategies can be expressed as policies operating over a common environment, while common retrieval objectives can be represented through reward and weighting functions over the resulting search trajectory, and the resulting formulation admits a natural reinforcement learning interpretation. We illustrate the approach using high-recall information retrieval (HRIR), where the goal is to identify as many relevant documents as possible with limited judging effort, showing how the framework provides a unified way to describe and reason about strategies for both classical retrieval tasks and emerging LLM-guided search systems. Through experiments, we demonstrate that both the underlying retrieval method and the "deep research" policy employed can materially affect performance.
BibTeX
@misc{huo2026sequential,
  author = {Siqing Huo and Andrew Parry and Debasis Ganguly and Mark Smucker and Charles L. A. Clarke},
  title = {{A Sequential Decision Framework for Evaluating LLM-Guided Search}},
  year = {2026},
  eprint = {2610.39231},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.39231},
}
Figure