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.
Figures & tables
Figure 1: Overview of Retrieval Program Learning. (1) The policy composes search primitives into executable programs rather than relying on fixed retrieval pipelines. (2) Program mutation explores local variations of suboptimal programs generated by the policy to discover more effective retrieval structures. (3) Programmable search improves answer accuracy while using context more efficiently.
Primitive
Description
sparse_retrieval(q, top_k)
Retrieve a ranked list of documents using lexical matching
dense_retrieval(q, top_k)
Retrieve a ranked list of documents using semantic similarity
fuse(*lists)
Fuse ranked lists using reciprocal-rank fusion
dedup(docs)
Remove duplicates while preserving their first occurrence
rerank(q, docs, top_k)
Rerank documents with respect to q and retain the top- k
Table 1: Retrieval SDK. Primitives exposed to the policy for constructing retrieval programs.
Figure 2: Example program. A retrieval program can use multiple retrievers and selectively expose intermediate results to the model.
Methods
Single-Hop QA
Multi-Hop QA
Avg
NQ †
TriviaQA ⋆
PopQA ⋆
HotpotQA †
2Wiki ⋆
MuSiQue ⋆
Bamb ⋆
Qwen3-4B
Direct
0.142
0.362
0.138
0.170
0.261
0.026
0.072
0.167
CoT
0.161
0.417
0.156
0.186
0.242
0.036
0.304
0.215
RAG
0.319
0.589
0.389
0.243
0.140
0.065
0.208
0.279
IRCoT
0.316
0.574
0.372
0.292
0.229
0.133
0.456
0.339
Table 2: Evaluation across open-domain QA benchmarks. Exact-match accuracy on single-hop and multi-hop QA benchmarks. RPL achieves the best overall performance, with broadly consistent gains across individual benchmarks. † and ⋆ denote in-domain and out-of-domain datasets, respectively.
Methods
TopK
Count
Sort
MinMax
Avg
F1
dF1
F1
dF1
F1
dF1
F1
dF1
F1
dF1
Qwen3-4B
RAG
4.97
12.80
0.40
13.86
8.45
11.68
3.23
12.91
4.27
12.81
IRCoT
4.30
12.76
1.11
13.84
5.07
13.07
2.49
12.91
3.24
13.14
Search-R1
15.82
20.39
4.19
20.38
24.47
20.21
11.53
19.35
14.00
20.08
MARAG-R1
13.26
23.79
6.98
24.08
16.95
25.45
11.44
24.08
12.16
24.35
Table 3: Evaluation on GlobalQA. F1 measures the overlap between predicted and reference answer document IDs, while dF1 measures document coverage of relevant retrieved evidence. RPL achieves the most competitive overall performance, with particularly strong gains on Qwen3-8B.
Figure 3: Effect of program mutation on RL training. Held-out EM for Qwen3-4B (left) and Qwen3-8B (right), with program mutation applied at step 200. Solid: RL resumed after distilling on verified program mutations. Dashed: continuous RL from the same checkpoint.
Methods
Single-Hop QA
Multi-Hop QA
Avg
NQ †
TrivQA ⋆
PopQA ⋆
HotpotQA †
2Wiki ⋆
MuSiQue ⋆
Bamb ⋆
Qwen3-4B
RPL (Dense)
0.504
0.656
0.476
0.481
0.475
0.204
0.512
0.473
RPL (Dual)
0.502
0.670
0.487
0.501
0.471
0.199
0.512
0.478
RPL (SDK)
0.516
0.684
0.510
0.517
0.463
0.230
0.488
0.487
RPL (PM)
0.536
0.701
0.517
0.539
0.491
0.258
0.560
0.515
Table 4: Performance and retrieval action space. Performance under progressively richer retrieval interfaces for Qwen3-4B and Qwen3-8B. Dense: dense retrieval only; Dual: sparse and dense retrieval; SDK: full retrieval SDK; PM: program mutation applied on top of the SDK setting.
Figure 4: Retrieval and training efficiency on GlobalQA. Context consumption denotes the number of tokens entering the model context, retrieval turns the number of search turns, and training time the number of seconds per step. Values are normalized to the midpoint of RPL’s min–max range, with annotations showing the raw ranges. By programmatically controlling what enters the model context, RPL substantially reduces context consumption and retrieval turns.
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: Primitive adoption over RL training. Each curve shows the percentage of held-out rollouts whose programs call sparse retrieval (blue) or reranking (orange) at least once. Panels vary one factor at a time—model scale (left), training mixture (center), and input prompt (right)—with line styles distinguishing the two conditions and the evaluation set held fixed within each.
Methods
Single-Hop QA
Multi-Hop QA
Avg
NQ †
TriviaQA ⋆
PopQA ⋆
HotpotQA †
2Wiki ⋆
MuSiQue ⋆
Bamb ⋆
Qwen2.5-3B
ReSearch
0.365
0.571
0.395
0.351
0.272
0.095
0.266
0.331
MR-Search
0.477
0.635
0.460
0.419
0.401
0.165
0.344
0.414
GiGPO
0.420
0.595
0.424
0.369
0.370
0.126
0.641
0.421
IG-Search
0.450
0.614
0.460
0.431
0.440
0.191
0.424
0.430
Appendix
Table 5: Qwen2.5 across open-domain QA benchmarks. Exact-match accuracy on single-hop and multi-hop QA benchmarks. RPL achieves the best overall performance, outperforming baselines on six of the seven benchmarks. † and ⋆ indicate in-domain and out-of-domain datasets, respectively.
Methods
Single-Hop QA
Multi-Hop QA
Avg
NQ
TriviaQA
PopQA
HotpotQA
2Wiki
MuSiQue
Bamboogle
Qwen3-4B
CoT
0.146 / 0.161
0.382 / 0.417
0.147 / 0.156
0.183 / 0.186
0.233 / 0.242
0.043 / 0.036
0.248 / 0.304
0.197 / 0.215
RAG
0.207 / 0.319
0.537 / 0.589
0.349 / 0.389
0.221 / 0.243
0.149 / 0.140
0.047 / 0.065
0.176 / 0.208
0.241 / 0.279
IRCoT
0.299 / 0.316
0.527 / 0.574
0.376 / 0.372
0.256 / 0.292
0.211 / 0.229
0.090 / 0.133
0.264 / 0.456
0.289 / 0.339
Search-o1
0.335 / 0.285
0.554 / 0.547
0.382 / 0.354
0.270 / 0.283
0.197 / 0.226
0.084 / 0.122
0.232 / 0.400
0.293 / 0.317
Appendix
Table 6: Thinking vs. non-thinking on open-domain QA. Each cell reports non-thinking (NT) / thinking (T) performance. † denotes a degenerate interaction between Qwen3-8B’s NT mode and multi-turn agentic prompting in which the model often loops until the token budget is exhausted.
Figure 6: Illustration of program mutation. Given a suboptimal policy program, we generate candidates according to a mutation grammar, retaining those that satisfy the verification criteria.
Training large language models as retrieval-augmented reasoning agents typically combines reinforcement learning with an SFT cold start distilled from a stronger model. However, this paradigm overlooks two fundamental factors: the dependency structure among sub-skills, and the possibility that distillation is not the only route to capability acquisition. We study this through Plan, a structured agentic behavior for multi-hop retrieval that decomposes a question into ordered sub-questions before any retrieval is performed, so that each search step can be anchored to a pre-designed sub-question instead of drifting under the influence of partially relevant documents retrieved earlier. However, across three model families spanning 3B to 14B parameters, we find that an identical reward signal induces qualitatively different RL failure modes. This phenomenon indicates that successful training hinges not only on reward design but also on model-specific feasibility conditions: sufficient initial entropy, training stability, and prerequisite sub-skills. Motivated by this, we propose a self-bootstrapping paradigm in which a small-scale seed model generates filtered trajectories that activate Plan in any target model, eliminating the need for distillation from an external stronger model. Our pipeline activates Plan across every tested model and consistently outperforms competitive baselines on multi-hop QA benchmarks.
Zhipeng Qian, Zihan Liang, Yufei Ma +7
1Kuaishou Technology · 2Key Laboratory of Multimedia Trusted Perception and Efficient Computing, Ministry of Education of China, Xiamen University, 361005, P.R. China · 3VCIP, CS, Nankai University
Retrieval-augmented generation (RAG) connects large language models (LLMs) to external knowledge, but single-round retrieval is often insufficient for complex multi-hop questions. To enhance search capabilities for complex tasks, most existing works integrate multi-round iterative retrieval with reasoning processes via end-to-end training. While these approaches improve problem-solving performance, they still face challenges in task reasoning and model training, especially ambiguous retrieval execution paths and sparse rewards in end-to-end reinforcement learning (RL), which can lead to inaccurate retrieval results and lower performance. We attribute these failures to hierarchical credit entanglement: a single final reward updates planning and execution together, so the model cannot clearly separate plan errors from retrieval errors. We propose APEX-Searcher, which uses a Refining Credit Assignment paradigm: planning is optimized by RL with a plan-level reward, while execution is learned by SFT. Extensive experiments show consistent gains in both multi-hop RAG and task planning across benchmarks.
Kun Chen, Qingchao Kong, Zhao Feifei +1
University of Chinese Academy of Sciences · MAIS, Institute of Automation, Chinese Academy of Sciences · Wenge Technology Co., Ltd
Agentic retrieval-augmented generation (RAG) extends static RAG by allowing language models to iteratively reason, generate search queries, retrieve evidence, and predict answers. However, it remains challenging for models to decide when to retrieve, whether to use lexical matching or semantic similarity, and how to control context granularity to prevent irrelevant tokens from interfering with agent reasoning. In this paper, we introduce GRASP, a reinforcement learning (RL) framework for training agents to adaptively coordinate complementary retrieval tools during multi-step reasoning. GRASP provides the agent with semantic search, keyword search, and paragraph-reading actions, enabling it to retrieve sentence-level evidence and expand further context only when needed. We train the policy with a reward that jointly accounts for answer accuracy, grounded reading, complementary search, and turn efficiency. Experiments on multi-hop reasoning benchmarks show that GRASP improves both retrieval recall and downstream question answering performance compared with single-step retrieval, prompting-based agentic RAG, and RL-based retrieval baselines. Qualitative and ablation analyses show that the learned policy develops interpretable skimming and scanning behavior: it uses semantic search for broad exploration, paragraph reading for local verification, and keyword search for entity-specific evidence. These results suggest that learning to coordinate retrieval signals and context granularity is critical for agent's correct reasoning.
Varun Gandhi, Jaewook Lee, Shantanu Todmal +4
University of Massachusetts Amherst · Adobe Research