Think Before You Retrieve: Learning Test-Time Adaptive Search with Small Language Models

Supriti Vijay ∗,1,† , Aman Priyanshu ∗,2 , Anu Vellore 2 , Baturay Saglam 2,3,† , Amin Karbasi 2 1 Carnegie Mellon University 2 Foundation AI–Cisco Systems Inc. 3 Yale University · 2025

Read Think Before You Retrieve: Learning Test-Time Adaptive Search with Small Language Models by Supriti Vijay ∗,1,† , Aman Priyanshu ∗,2 , Anu Vellore 2 , Baturay Saglam 2,3,† , Amin Karbasi 2 1 Carnegie Mellon University 2 Foundation AI–Cisco Systems Inc. 3 Yale University (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-07581.txt.

Introduction

Supriti Vijay, Aman Priyanshu, and Anu Vellore teach small language models to search the way people do: look, learn, and look again. Plain retrievers cannot reason, giant models reason at high cost, and query rewriting only reshapes the first attempt. Complex questions need search that adapts as evidence arrives.

Orion trains compact models, from a few hundred million to just over a billion parameters, to run iterative retrieval with learned strategies. Synthetic search trajectories show the steps of exploring, judging feedback, and revising. Small models then handle multi-step questions once reserved for huge systems. Cheaper adaptive search could widen access to deep question answering.

Catalog record

CREATORSupriti Vijay ∗,1,† , Aman Priyanshu ∗,2 , Anu Vellore 2 , Baturay Saglam 2,3,† , Amin Karbasi 2 1 Carnegie Mellon University 2 Foundation AI–Cisco Systems Inc. 3 Yale University
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE81 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-07581

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Think Before You Retrieve: Learning Test-Time Adaptive Search with Small Language Models Supriti Vijay ∗,1,† , Aman Priyanshu ∗,2 , Anu Vellore 2 , Baturay Saglam 2,3,† , Amin Karbasi 2 1 Carnegie Mellon University 2 Foundation AI–Cisco Systems Inc. 3 Yale University Abstract Effective information retrieval requires reasoning over partial evidence and refining strategies as information emerges. Yet current approaches fall short: neural retrievers lack reasoning capabilities, large language models (LLMs) provide semantic depth but at prohibitive cost, and query rewriting or decomposition limits improvement to static transformations. As a result, existing methods fail to capture the iterative dynamics of exploration, feedback, and revision that complex user queries demand. We introduce Orion, a training framework that enables compact models (350M-1.2B parameters) to perform iterative retrieval through learned search strategies. Orion combines: (1) synthetic trajectory generation and supervised fine-tuning to encourage diverse exploration patterns in models, (2) reinforcement learning (RL) that rewards effective query refinement and backtracking behaviors, and (3) inference-time beam search algorithms that exploit the self-reflection capabilities learned during RL. Despite using only 3% of the training data available, our 1.2B model achieves 77.6% success on SciFact (vs. 72.6% for prior retrievers), 25.2% on BRIGHT (vs. 22.1%), 63.2% on NFCorpus (vs. 57.8%), and remains competitive on FEVER, HotpotQA, and MSMarco. It outperforms retrievers up to 200-400× larger on five of six benchmarks. These findings suggest that retrieval performance can emerge from learned strategies, not just model scale, when models are trained to search, reflect, and revise. \reportnumber 001 † † footnotetext: † Work done while at Foundation AI. † † footnotetext: ∗ Equal Contribution 1 Introduction Information retrieval has traditionally been framed as a one-shot task: given a query, return the most relevant documents. This formulation assumes that a query fully specifies the user’s information need and that relevance can be resolved in a single pass over the corpus [ 62 ] . Modern neural retrievers have advanced this paradigm significantly [ 69 , 28 , 51 , 12 , 2 , 10 ] , learning sophisticated representations that encode semantic similarity beyond lexical overlap, achieving strong performance on classic retrieval benchmarks. However, this one-shot assumption breaks down for complex information needs that require multi-hop reasoning or exploratory search. Current solutions either attempt query reformulation [ 76 , 68 ] , i.e., enriching queries with anticipated evidence, or decomposition [ 3 , 19 ] , i.e., breaking questions into sub-queries. Both strategies commit to a search plan before observing corpus evidence. When decomposition misses key entities (the “lost-in-retrieval” problem [ 83 ] ) or expansion drifts from corpus vocabulary, no recovery mechanism exists. In particular, 61 showed the severity: models that answer multi-hop questions correctly still fail on 50-60% of the constituent sub-questions. Figure 1 : Overview of Orion . We illustrate two established query reformulation baselines alongside our proposed Orion framework. While query decomposition fails without corpus feedback and query rewriting yields static reformulations that ignore retrieval results, Orion performs tree-based exploration with structured reasoning spans, revising its strategy as it encounters conflicting evidence – backtracking, refining, and generating new hypotheses to recover relevant information. Interactive retrieval methods [ 63 , 46 , 83 , 21 ] address this by interleaving retrieval and reasoning, showing that adaptive loops outperform static pipelines. However, these retrieval-augmented generation (RAG) systems place adaptivity in the reasoning layer (LLM controller or generator) rather than in the retrieval layer. The retriever itself remains static, invoked repeatedly but never trained to adapt its search strategy. This overlooks a key point: the retrieval policy is as important as the reasoning policy . Deciding how to refine queries, explore alternatives, or backtrack from failures is part of retrieval, not just generation. At the same time, scaling analyses [ 45 , 77 ] show that retrieval performance grows predictably with model size and pretraining compute. Yet these gains mainly reflect stronger single-shot matching through better embeddings and in-context learning, they do not yield adaptive search policies. Neither costly LLM controllers nor stronger embeddings resolve the core limitation: retrieval models lack the ability to adapt their search strategy in response to observed evidence. We introduce a different approach: making the retriever itself adaptive. We call this paradigm test-time adaptive search and present Orion, a training framework that enables compact models (350M-1.2B parameters) to learn dynamic search policies through synthetic trajectory supervision and turn-level reinforcement learning. Unlike systems that rely on LLMs for test-time reasoning [ 26 ] or enhance static retrievers with reasoning-aware training [ 51 , 12 ] , we train models to internalize diverse search strategies: when to explore alternatives, when to refine promising directions, and when to backtrack from failures. A key innovation is our turn-level reward structure that leverages standard IR metrics to provide dense feedback at each search step rather than sparse outcome-only signals. This enables models to learn when and how to backtrack from unproductive search directions, a capability that conventional outcome-based training fails to capture. Moreover, our inference algorithm employs beam search with explicit structural markers ( <think> , <search_query> , <top_k_response> ) that cleanly separate reasoning from querying, keeping search queries concise while allowing thinking spans to incorporate rich retrieval feedback across turns. As Figure 1 illustrates, this design enables systematic exploration of multiple search paths with strategic backtracking when initial directions prove unproductive—moving from failed decomposition attempts to successful evidence recovery through adaptive query reformulation. Empirically, we demonstrate that compact models can achieve substantial retrieval performance when trained with adaptive search strategies. Despite using models up to 400× smaller, Orion achieves 25.2% nDCG@10 on BRIGHT and 77.6% on SciFact, outperforming both pre-trained and instruction-tuned models, including specialized 3B query rewriting systems. These gains emerge not from stronger embeddings or larger scale, but from learned adaptive behavior: recognizing when queries fail, exploring alternatives systematically, and recovering from unproductive search paths. Our findings suggest that retrieval intelligence may depend more on learning appropriate search behaviors than on model scale alone, illuminating the potential for compact models to achieve strong performance through targeted training on the core principles of adaptive search. 2 Related Work Conventional Retrievals Classical IR pipelines, lexical metrics and one-pass dense retrieval, optimize a single query, produce top-k hop, and assume that the right evidence is surfaceable with a static query [ 66 , 9 , 39 , 24 , 67 , 80 , 28 , 2 ] . While recent improvements teach retrievers to better follow task intent or ranking signals [ 84 , 78 , 29 , 30 , 49 ] , these methods still commit early to a single retrieval state: they neither plan, backtrack, nor adapt the retrieval policy within a session when initial evidence is off-manifold. In high-ambiguity settings, this “fire-and-forget” assumption turns errors in the first hop into answer-level failures. This motivates our approach to introduce an iterative, policy-driven search that can revise hypotheses mid-trajectory. Reasoning-based Retrievers and Query Rewriting A complementary line trains the retriever to favor evidence that supports multi-step reasoning rather than shallow matches. For example, 51 builds hard negatives and challenging queries per document, while 12 synthesizes reasoning-conditioned relevance from chain-of-thought traces; both improve reasoning-heavy IR and help downstream RAG. Listwise or pointwise rerankers [ 37 , 17 ]

Read the complete text