Programmable search improves complex question answering and reasoning
Learning to Program Retrievals: Composing Search Primitives via Reinforcement Learning
Computation and LanguageInformation Retrieval
Summary
Answering complex questions often requires searching through a lot of information step-by-step. The authors created a method that teaches computer models how to make flexible, step-by-step search plans like writing a small program. This helps the model look broadly, use intermediate findings smartly, and be more efficient. They also developed a way to improve learning when feedback is rare by tweaking partial plans and learning from them. Their method works better than existing approaches, especially on questions that need multiple steps to answer.
What this means in practice
- •For natural language processing teams: Create language models that adaptively compose multi-step searches to improve accuracy on complex question answering tasks.
- •For enterprise search developers: Build search systems that dynamically combine search actions with intermediate processing to retrieve relevant data efficiently across large document collections.
Authors
Kyuyoung Kim, Zilin Xiao, Zhiyuan Wang, Avinash Atreya, Ke Yang, Jinwoo Shin, Kecheng Hao
Abstract
Retrieval-augmented language models increasingly use multi-step search to solve knowledge-intensive tasks, yet existing systems typically expose retrieval through fixed pipelines or collections of atomic tools. We introduce Retrieval Program Learning (RPL), a programmable search framework that allows a policy to compose search primitives into executable programs with local state and control flow. This enables adaptive search that can retrieve broadly, process intermediate results, and selectively construct model context without tying retrieval breadth to context consumption. However, the resulting flexibility creates a difficult exploration problem: useful programs may require several coordinated decisions, while reinforcement learning often supplies only sparse feedback. To address this challenge, we propose program mutation, a grammar-constrained and execution-verified procedure that generates local variants of suboptimal programs sampled during RL, converts them into training trajectories, and distills them back into the policy. We evaluate RPL on open-domain question answering and corpus-level reasoning tasks, comparing it with a range of retrieval and reasoning baselines. RPL consistently improves open-domain QA performance across model sizes and in- and out-of-domain benchmarks, with particularly large gains on multi-hop tasks. Notably, a 4B model trained with RPL outperforms all 8B model baselines. On corpus-level reasoning, RPL achieves the highest answer F1 and document-coverage F1 for both model sizes while substantially reducing context consumption and retrieval turns. Our results show that programmable search expands the retrieval strategies that agents can learn, while program mutation provides an effective mechanism for exploring useful program structures beyond direct on-policy sampling.