acceptodds
Under review as a conference paper at ICLR 2027

Learning to Program Retrievals: Composing Search Primitives via Reinforcement Learning

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 introduce 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 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 effectively learn, while program mutation provides an effective mechanism for exploring useful program structures beyond direct on-policy sampling.

Primary area:
foundation or frontier models, including LLMs
Keywords:
retrieval-augmented generation, agentic search, reinforcement learning, programmatic retrieval, search agents, language models

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_jo6POpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Retrieval Program Learning (RPL), which lets a model control search by writing and executing programs composed of retrieval primitives, rather than using a fixed retrieval pipeline or invoking atomic tools one at a time. The programs can combine sparse and dense retrieval, fusion, deduplication, and reranking, keep intermediate results in the program state, and place only the selected evidence into the model context. To help reinforcement learning explore effective program structures, the authors further propose program mutation: performing constrained local modifications on suboptimal programs sampled from the policy, verifying the retrieval results, and then distilling valid variants back into the policy as training trajectories. The experiments cover open-domain question answering and corpus-level reasoning on GlobalQA; the authors report that RPL improves accuracy on multiple QA benchmarks and improves document coverage, reduces context consumption, and reduces retrieval rounds on GlobalQA.

Critical strengths
  • The retrieval interface is more flexible. RPL leaves the retrieval process itself to be composed by the policy, enabling the model to adjust retrieval methods, candidate scales, and post-processing according to the question, rather than being limited to a fixed pipeline or a single retrieval action.
  • Program mutation targets the exploration difficulty in reinforcement learning. The paper uses constrained program modifications to produce new retrieval structures, then verifies and distills valid trajectories. This provides additional training signals for policies that are hard to explore directly under sparse rewards; the ablation results show that adding mutation generally outperforms the RL-only setting.
  • It achieves fairly consistent improvements across multiple QA tasks. After training on NQ, HotpotQA, and other data, RPL is evaluated on seven QA benchmarks; the paper reports average EM of 0.515 and 0.531 for the 4B and 8B models, respectively, with more notable gains on multi-hop tasks.
  • It evaluates retrieval quality and context efficiency. On GlobalQA, RPL achieves the highest document coverage F1 at both model scales, while also reporting lower context consumption and fewer retrieval rounds. This supports the paper's design motivation of "retrieving broadly while selectively providing context."
Critical weaknesses
  • Richer retrieval programs also incur additional execution costs. The paper focuses on comparing context token counts and retrieval rounds, but a program can internally execute multiple retrievals, fusions, and rerankings. If only rounds are counted, the actual number of retrieval calls, runtime latency, and index load may not be fully reflected.
  • The benefits of program mutation may depend on the chosen mutation grammar and verification rules. Mutations are restricted to local operations and mainly modify the last retrieval program. Such a design is easy to control, but it may also miss effective programs that require cross-round modifications or changes to the query strategy; the results may also be sensitive to mutation frequency and filtering rules.
  • The test scope remains concentrated on a limited set of data and corpus settings. The QA experiments use a specific Wikipedia snapshot and are tested on several standard benchmarks; GlobalQA also focuses on specific types of corpus-level questions. The current results are not yet sufficient to indicate how the method performs on other domain corpora, dynamic knowledge bases, or different retrievers.
  • The sources of the performance gains are not yet fully disentangled. The paper progressively compares dense retrieval, dual retrievers, the full SDK, and program mutation, providing valuable analysis; however, since the complete approach simultaneously changes the available retrieval operations and the training strategy, the evidence for attributing gains specifically to the "programmable interface" or to "program mutation" is still limited.
Questions for authors
  • Regarding efficiency evaluation: Can the authors report the number of retrieval, reranking, and other primitive calls actually executed per question, as well as end-to-end latency and computational overhead? Could the reduction in retrieval rounds and context tokens be offset by more retrieval operations inside the programs?
  • Regarding program mutation: How are the mutation grammar, candidate count, execution cost, and the verification criterion of "sufficient evidence retrieved" set? Can the authors analyze the sensitivity of performance to these choices, and evaluate whether allowing modifications to earlier rounds or to the query text would bring additional gains?
  • Regarding cross-corpus generalization: Can the method be tested on different domains or different versions of corpora, and validated with other sparse and dense retrievers? If the retriever or corpus changes, can the policy still be reused, or does it need retraining?
  • Regarding contribution attribution: Can the authors compare, under a unified retriever, primitive-call budget, and training budget, the settings of a fixed pipeline, a multi-tool policy, programmable retrieval, and "programmable retrieval without program mutation"? This would help more clearly determine the gains brought by each of the two core designs.
6 comments

Dear Reviewer jo6P,

We sincerely appreciate your review. We have carefully considered each of your questions and provide detailed responses below. Please let us know if you have any further questions or concerns.

For clarity, we briefly summarize the two additional baselines referenced throughout our responses. The fixed hybrid pipeline is a stronger fixed strategy that retrieves the top 20 documents from each of the dense and sparse retrievers, fusing the results, and reranking the combined candidates to retain the top 5. This provides a stronger, albeit more expensive, retrieval strategy for open-domain QA. The multi-tool agent accesses the same retrieval primitives as separate tools, making one tool call per turn. We provide the corresponding comparisons and results in our responses below.


[W1,Q1] Computational efficiency and execution costs

We thank the reviewer for raising this important point. We clarify that our original evaluation already reports wall-clock training time per RL step on GlobalQA (Figure 4), in addition to context length and retrieval rounds. We further complement this analysis with inference latency and primitive-call measurements to provide a more complete picture of execution cost.

Training efficiency on GlobalQA. Figure 4 reports that RPL trains 4.7-5.3x faster than Search-R1 and 1.7-1.8x faster than MARAG-R1. To quantify variability, we additionally measured training time over three seeds. An RPL training step takes 100 ± 0.5 / 146 ± 0.5 seconds at 4B / 8B, compared with 562 ± 12 / 786 ± 20 seconds for Search-R1 and 168 ± 48 / 322 ± 10 seconds for MARAG-R1. The savings come primarily from what enters the model context. GlobalQA questions ask for documents satisfying a set of criteria, so RPL retrieves documents for individual criteria and combines the results within the sandbox. The model only needs to process a small set of document IDs or a count, rather than the full contents.

Primitive calls and inference latency. We additionally measure the average number of dense retrieval, sparse retrieval, and reranking requests per question, along with inference latency. Call counts and latencies are averaged over three seeds.

Method (4B / 8B)CallsLatencyAccuracy
GlobalQA (macro F1)
Search-R12.2 / 2.20.61 / 0.4714.4 / 14.6
MARAG-R11.4 / 2.00.63 / 1.7912.6 / 12.7
Fixed hybrid pipeline3.0 / 3.11.04 / 1.389.5 / 10.3
RPL2.7 / 2.90.62 / 1.5517.6 / 20.0
Open-domain QA (EM)
Search-R12.5 / 2.40.90 / 1.070.471 / 0.493
Multi-tool agent (10 turns)4.3 / 3.83.1 / 3.20.506 / 0.521
Fixed hybrid pipeline6.0 / 5.91.8 / 2.20.509 / 0.527
RPL5.9 / 5.67.2 / 4.90.523 / 0.545
  • On GlobalQA, RPL makes slightly more calls than Search-R1 and MARAG-R1, but fewer than the fixed hybrid pipeline, while achieving the highest macro F1. Its inference latency is comparable to Search-R1 at 4B and higher at 8B, but remains similar or below MARAG-R1 and the fixed hybrid pipeline.
  • On open-domain QA, where the model must read retrieved document contents to answer questions, RPL makes more calls than Search-R1 and the multi-tool agent, and about as many as the fixed hybrid pipeline. Its inference latency is also higher than all three baselines. This reflects the additional retrieval operations and the larger amount of retrieved content processed by RPL. Nevertheless, RPL achieves the highest EM at both scales.

Reducing execution cost. RPL’s programmable interface also allows it to adapt its strategy to an explicit cost objective. In a preliminary single-seed experiment, we add a penalty for retrieval calls to the training reward. At 8B, this reduces the average number of calls from 5.6 to 1.3 per question while achieving 0.504 EM. This represents 46% fewer calls than Search-R1 (2.4 calls), while still achieving higher accuracy (0.493 EM). Unlike fixed pipelines, RPL can learn to omit retrieval operations when they are unnecessary. Other opportunities include filtering retrieved documents or selecting only relevant passages and sentences before adding them to the model context, as well as reranking only a subset of the fused candidates. We leave further exploration of these cost-aware program designs to future work.


[W2,Q2] Mutation grammar and sensitivity

We thank the reviewer for the opportunity to clarify. Please note that details on program mutation are provided in Appendix B, which we will expand based on this discussion.

  • Mutation grammar and candidate selection. Our grammar explores structural variations of a policy-generated retrieval program while keeping the candidate space tractable. Each candidate varies four dimensions: (1) the subset of the program’s queries used, (2) the retrieval modality, (3) the retrieval breadth, and (4) the retention width after reranking. Invalid programs and those exceeding the observation budget are discarded. Candidates are executed in order of structural distance from the original program, and the first that passes verification is kept.
  • Verification and supervision. A candidate passes if the documents it prints contain an acceptable answer (simple string matching), which needs retrieval only. The policy then re-answers with the output spliced in. This decides whether the answer tokens are supervised: when it is incorrect (68-80% of examples), the example supervises the program only, with the answer loss masked.
  • Execution cost. A round, including SFT (10-15 optimizer steps), takes about two hours, which is only about 1% of the time of the RL that follows.
  • Why mutate only the final retrieval turn? We restrict mutation to the final retrieval turn because modifying earlier turns could invalidate subsequent actions and require replaying the remainder of the trajectory. RL continues to optimize both program structure and query formulation.

We further provide analyses of the procedure’s sensitivity to several design choices.

  • Mutation frequency and timing. A second mutation round at step 400 yields only a marginal additional gain, with 0.521 vs. 0.519 EM at 4B. This is primarily because, by step 400, the policy already makes effective use of much of the structure covered by the current grammar. We also compare applying the single mutation round at step 100 rather than step 200. The resulting gain over RL alone changes little, with a 2.1 point EM improvement over RL alone.
  • Candidate selection. We compare different ways of selecting one repair per failed question. Selecting the nearest repair gives a 1.7 point EM gain over RL alone; preferring repairs that add reranking gives a 2.2 point gain; and diversifying repair types across questions gives a 1.2 point gain. Although the magnitude depends on the selection strategy, each approach improves over RL alone.
  • Verification criterion. Requiring the policy’s subsequent re-answer to also be correct would retain only 20-32% of otherwise verified repairs. We therefore use retrieval verification as the acceptance criterion and mask answer loss when the re-answer is incorrect. This preserves substantially more retrieval program supervision without treating an incorrect answer as a successful outcome.
  • Query source and earlier turns. In an exploratory analysis, expanding the candidate query pool to include queries generated by the policy in earlier turns raises the repairable share from 52% to 66%. This suggests that a broader query pool may expose additional repair opportunities.

Overall, our implementation of the procedure is deliberately simple: one round, the nearest verified repair per failure, the last turn with the policy’s own queries, and an answer check. Natural extensions include how many and which candidates to keep per failure, incorporating a cost term in the selection, and applying additional mutation rounds to failures that remain.


[W3,Q3] Generalization across additional settings

We thank the reviewer for raising this point. We respectfully clarify that our evaluation covers a broad range of settings, consistent with or extending beyond common settings for this line of work. In particular, Search-R1 [1] and AutoRefine [2] evaluate on the same seven open-domain QA benchmarks as our work, while ReSearch [3] evaluates on four of them (multi-hop only). Beyond these benchmarks, our evaluation spans several additional dimensions:

  • Model families and scales: We evaluate Qwen3 (4B and 8B; Table 2) and Qwen2.5 (3B and 7B; Table 5), covering both recent models and those commonly used in prior work.
  • Corpora and retrieval systems: Beyond open-domain QA over Wikipedia using E5 and BM25, we evaluate on the corpus-level reasoning benchmark GlobalQA (Table 3) using BGE and BM25, comparing against prior methods with both Qwen3-4B and 8B.
  • Reasoning configurations: Since Qwen3 supports an explicit reasoning mode, we evaluate its effect across all main baselines (Table 6), adopting the configuration that yields the better result for each method.

Thus, our evaluation covers two corpus settings with different retrievers, two model families and scales, and different reasoning configurations. We further conduct test-time component-swap experiments to examine policy portability, without retraining:

  • Reranker swap on open-domain QA: We replace the 4B reranker used during training with the weaker 0.6B model at test time. RPL’s EM decreases by 0.018/0.014 at 4B/8B, compared with 0.009/0.008 for the fixed hybrid pipeline. Despite this greater sensitivity, RPL remains ahead of the hybrid pipeline using the same smaller reranker. Notably, RPL with the smaller reranker also exceeds the hybrid pipeline retaining the original 4B reranker (.506 vs. .505; .537 vs. .526).
  • Dense-retriever swap on GlobalQA: We replace the BGE dense retriever with E5 at test time. Search-R1, which relies solely on dense retrieval, loses 1.3 answer-F1 points at both model scales, whereas RPL is largely unaffected.

These experiments provide further evidence that RPL can tolerate changes to retrieval components without retraining, although its robustness depends on the component being changed. In particular, the reranker swap reveals some dependence on the reranker used during training, while the dense retriever swap demonstrates greater portability across the tested dense retrievers.

We agree that evaluating on additional domains, dynamic knowledge bases, and a wider range of retrieval backends would be valuable future work. However, such unrestricted transfer is beyond what is established by the evaluation protocols of the prior works. Our evaluation already extends beyond the common open-domain QA setting through GlobalQA, a corpus-level reasoning benchmark with different retrieval requirements, and further includes direct test-time substitutions of retrieval components without retraining. We believe these experiments provide substantial evidence of generalization across benchmarks, task settings, models, and retrieval components.

[1] Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning.

[2] Search and Refine During Think: Facilitating Knowledge Refinement for Improved Retrieval-Augmented Reasoning.

[3] ReSearch: Learning to Reason with Search for LLMs via Reinforcement Learning.

Reviewer_FmjHOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper focuses on training search agents. The authors propose Retrieval Program Learning, which uses reinforcement learning to train language model agents to generate executable programs that combine search primitives and control which retrieved information enters the model context. To support exploration during training, they further propose program mutation, which generates and verifies structural variants of suboptimal programs and uses them for supervised fine-tuning before RL resumes. The framework is evaluated on open-domain question answering and corpus-level reasoning tasks.

Critical strengths
  • Clear efficiency benefits on aggregation-style tasks. Executing retrieval programs lets the model process large candidate sets without placing them in its context, substantially reducing context consumption and retrieval turns.
  • Transparent and informative analyses. The ablations and training-dynamics analyses make it clear where the gains come from and how the learned retrieval behavior emerges.
Critical weaknesses
  1. The experiments do not isolate the benefit of programmatic composition from differences in retrieval capabilities. In open-domain QA, no multi-tool baseline such as MARAG-R1 or GRASP is evaluated. The multi-tool comparison is limited to MARAG-R1 on GlobalQA, whose described configuration does not include the reranker available to RPL. Although Appendix C explains the reproduction constraints and resulting training modifications, this comparison does not provide an atomic-tool baseline matched to RPL’s retrieval components. A controlled experiment exposing the same retrieval, fusion, deduplication, and reranking primitives through either separate tool calls or executable code, with the same backbone, training supervision, and comparable computation budgets, is needed to establish the benefit attributable specifically to the programmatic interface.
  2. The advantage of learned adaptive programs over strong fixed retrieval strategies remains unestablished. With dense retrieval alone, RPL performs close to Search-R1: average EM is 47.3 versus 46.9 at 4B and 48.5 versus 49.4 at 8B (Tables 2 and 4). The action-space ablations demonstrate benefits from additional components and program mutation, but do not compare RPL with an RL-trained agent using a fixed hybrid retrieval-and-reranking pipeline or a prompt-only agent using the same full SDK. Figure 5 reports primitive inclusion frequencies, which do not establish how program structure, control flow, or retrieval depth adapts across questions. These missing controls leave unresolved how much improvement requires learned, question-dependent composition rather than a stronger retrieval pipeline and supplied prompt examples.
Questions for authors

Could the authors clarify which aspects of RPL are new relative to CodeAct [1], Search as Code [2], and direct corpus interaction approaches such as DCI [3] and GrepSeek [4]? Code-based tool composition and selective exposure of intermediate results already appear in prior interfaces, while GrepSeek trains executable corpus-search behavior through supervised initialization and RL. Is RPL’s main contribution its learning procedure and program mutation, or does the programmable interface introduce additional capabilities beyond these approaches?

[1] Executable Code Actions Elicit Better LLM Agents. ICML 2024.

[2] Perplexity Research. Rethinking Search as Code Generation. 2026.

[3] Beyond Semantic Similarity: Rethinking Retrieval for Agentic Search via Direct Corpus Interaction. 2026.

[4] GrepSeek: Training Search Agents for Direct Corpus Interaction. 2026.

5 comments

Dear Reviewer FmjH,

We sincerely appreciate your review. We have carefully considered each of your questions and provide detailed responses below. Please let us know if you have any further questions or concerns.


[W1,W2] Programmable retrieval vs. fixed pipelines, tool-based agents, and prompt-only agents

We thank the reviewer for suggesting these comparisons. We added three controls to examine alternative explanations for RPL’s gains: a stronger fixed retrieval pipeline, access to the same primitives as separate tools, and the supplied prompt examples. All agent baselines use the same backbone and retrieval components, with the same RL training budget where applicable. The fixed hybrid pipeline retains Search-R1’s search action but retrieves the top 20 documents from each of the dense and sparse retrievers, fuses the results, and reranks the combined candidates to retain the top 5. This provides a stronger, albeit more expensive, retrieval strategy for open-domain QA. The multi-tool agent accesses the same primitives as separate tools, making one tool call per turn, with budgets of 3, as for other methods, or 10 turns. Finally, the prompt-only agent uses the untrained model with RPL’s full SDK and prompt.

Qwen3-4B, EMNQTriviaQAPopQAHotpotQA2WikiMuSiQueBamboogleAvg
Search-R1.510 ± .002.661 ± .001.481 ± .003.483 ± .001.453 ± .004.214 ± .004.499 ± .007.471 ± .001
Fixed hybrid pipeline.519 ± .007.700 ± .003.508 ± .002.539 ± .003.486 ± .013.265 ± .005.544 ± .008.509 ± .002
Multi-tool agent (3 turns).528 ± .001.686 ± .005.504 ± .005.505 ± .002.446 ± .013.222 ± .005.504 ± .009.485 ± .002
Multi-tool agent (10 turns).527 ± .002.691 ± .000.497 ± .004.531 ± .001.486 ± .006.268 ± .004.541 ± .017.506 ± .003
Prompt-only agent.289.555.322.226.209.085.368.294
RPL (w/o mutation).517 ± .002.687 ± .002.511 ± .001.515 ± .001.481 ± .010.223 ± .005.483 ± .014.488 ± .003
RPL.540 ± .004.714 ± .003.521 ± .001.556 ± .001.494 ± .015.284 ± .003.552 ± .021.523 ± .002
Qwen3-8B, EMNQTriviaQAPopQAHotpotQA2WikiMuSiQueBamboogleAvg
Search-R1.522 ± .002.683 ± .005.487 ± .008.501 ± .001.493 ± .005.235 ± .003.531 ± .007.493 ± .003
Fixed hybrid pipeline.527 ± .003.713 ± .001.522 ± .002.553 ± .003.543 ± .006.279 ± .003.549 ± .005.527 ± .002
Multi-tool agent (3 turns).526 ± .003.694 ± .004.491 ± .009.516 ± .002.479 ± .016.241 ± .004.509 ± .016.494 ± .003
Multi-tool agent (10 turns).538 ± .002.704 ± .003.523 ± .001.543 ± .003.514 ± .009.283 ± .005.541 ± .007.521 ± .001
Prompt-only agent.323.609.401.366.374.144.384.371
RPL (w/o mutation).533 ± .006.707 ± .002.516 ± .002.544 ± .003.532 ± .006.284 ± .003.565 ± .010.526 ± .003
RPL.547 ± .001.721 ± .001.540 ± .001.559 ± .001.561 ± .004.297 ± .008.592 ± .017.545 ± .003

RPL outperforms the fixed hybrid pipeline at both scales on the seven benchmarks by 1.4 and 1.8 EM, with a similar number of retrieval calls. It also outperforms the multi-tool agent under both turn budgets, including with 10 turns, more than three times the budget of the other methods. Moreover, without training, the same SDK and prompt reach only .294 (4B) and .371 (8B), below even trained Search-R1. These results support three conclusions:

  • First, simply exposing the same components as separate tools does not match composing them in programs.
  • Second, the larger action space is harder to explore without mutation: RPL without mutation matches the fixed pipeline at 8B but trails it at 4B, a gap that program mutation closes.
  • Third, the gains do not come from the prompts examples or SDK alone, but from training the model to compose retrieval operations.

Note also that the same fixed hybrid pipeline performs poorly on GlobalQA, achieving average answer F1 scores of only 9.5 and 10.3 at 4B and 8B, respectively. Unlike open-domain QA, GlobalQA encompasses tasks with diverse retrieval needs, often requiring broad evidence gathering and aggregation across many documents rather than retrieving only a few highly relevant ones. A fixed pipeline optimized for the latter is therefore less suited to GlobalQA, further motivating the need for retrieval programs that adapt their strategies to the task.

Finally, we clarify that MARAG-R1 does use the reranker: its document filter invokes the same reranker as RPL and retains documents with relevance probabilities above 0.5.


[Q1] Relations to CodeAct, Search as Code, DCI, and GrepSeek

We thank the reviewer for the pointers. We agree that using executable code as an agent interface is not new. However, these works differ from RPL in the retrieval interface and, importantly, the learning procedure:

  • CodeAct (2024): Introduces executable Python actions for general-purpose tool use and fine-tunes models on ~7k teacher-generated trajectories. Its information-seeking tasks call a single Wikipedia search function; it does not compose retrieval components or train with RL.
  • Search as Code (Perplexity, June 2026 blog post): Introduces a related programmable interface over a production search stack, driven by a frontier proprietary model (GPT-5.5). However, it does not report training the model to compose retrieval primitives, identifying this as future work.
  • DCI (2026): Prompts frontier models to interact directly with raw corpus files through terminal tools (e.g., grep and shell commands), without conventional retrieval infrastructure such as embedding models or vector indices.
  • GrepSeek (2026): Trains an agent to perform direct corpus interaction using executable shell commands, but relies on cold-start trajectories generated by a larger teacher model (Qwen3.5-27B) for pre-RL SFT.

RPL contributes three complementary aspects:

  1. Learning programmable retrieval: We train 4B and 8B open models with RL to retrieve using executable Python programs with persistent state. Unlike GrepSeek, RPL operates over complementary indexed retrieval components rather than directly searching raw corpus text.
  2. Teacher-model-free program mutation: Unlike teacher-generated cold-start supervision, our mutation procedure explores local structural variants of the policy's own suboptimal programs, verifies their execution, and uses successful variants for additional SFT. It requires neither a stronger teacher model nor pre-RL demonstration data.
  3. Empirical evidence for learning: With the same retrieval SDK, the untrained 4B/8B models achieve only 0.294/0.371 average EM (best of thinking on and off), compared with 0.523/0.545 for RPL. This demonstrates that exposing search primitives alone is insufficient at this scale; training the policy to compose them is crucial. Note that the RPL results were obtained using a corrected program mutation template in our implementation.

We will expand the related work discussion to clarify these distinctions.

Dear Reviewer FmjH,

We would like to once again thank you for taking the time to review our submission. As the discussion period draws to a close, we would welcome the opportunity to address any remaining questions or concerns you may have.

Thank you again for your time and consideration.

Warm regards,

Authors

Reviewer_tNNiOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes Retrieval Program Learning (RPL), which trains a language model through retrieval of primitives to generate executable short programs from the retrieved primitives. These programs combine dense search and sparse search, fusion and reranking, and control which results enter the model context. To support exploration, program mutation automatically generates verified alternatives to the weaker programs, and these alternatives are distilled into the policy before reinforcement learning resumes. Experiments on seven qa benchmarks and GlobalQA report improvements in both the average accuracy and document coverage, while consuming less context.

Critical strengths
  1. RPL can retrieve many documents without putting all of them into the model’s context. It can return selected passages or a computed result, which is useful for tasks such as counting documents that meet a condition.
  2. The qa gains appear at both model sizes and on several datasets not used for training. The 4B model also scores higher than the reported 8B baselines on average, and Table 4 shows the score changes after adding retrieval tools and program mutation.
Critical weaknesses
  1. The mutation comparison combines structural changes with additional verified examples and supervised updates. A matched supervised-training control would help determine whether the gains specifically support the proposed exploration mechanism.
  2. The main QA experiments lack a fixed pipeline or tool-based agent with the same retrieval components and budget. This limits attribution of the accuracy gains to programmable composition rather than the stronger retrieval stack.
Questions for authors
  1. Are the examples of checkpoint selection completely disjoint from all the reported test sets, and what are the split sizes? What about the independent-run variation for the main comparisons?
  2. Could you compare mutation with a control that matches the number of verified examples and supervised updates without changing program structure?
  3. How does RPL perform against a fixed hybrid pipeline or tool-based agent with matched settings and budgets?
7 comments

Dear Reviewer tNNi,

We sincerely appreciate your review. We have carefully considered each of your questions and provide detailed responses below. Please let us know if you have any further questions or concerns.


[W1,Q2] Program mutation vs. matched supervised-training control

We thank the reviewer for suggesting this comparison. To isolate the contribution of program mutation, we compare RPL against a matched rejection-sampling fine-tuning (RFT) control, which trains on successful trajectories sampled from the policy itself. Both methods start from the same step 200 checkpoint. For each seed, we build the RFT dataset from the policy’s own correct trajectories in the same training rollouts that mutation draws from, with as many examples as that seed’s mutation dataset (~450 at 4B, ~300 at 8B). Both arms then take the same number of updates (10-15 optimizer steps) with the same hyperparameters, followed by identical RL training. We report means and standard errors over three training seeds.

Qwen3-4B, EMNQTriviaQAPopQAHotpotQA2WikiMuSiQueBamboogleAvg
RPL (w/o mutation).517 ± .002.687 ± .002.511 ± .001.515 ± .001.481 ± .010.223 ± .005.483 ± .014.488 ± .003
Matched RFT.529 ± .001.695 ± .002.504 ± .004.524 ± .004.476 ± .012.237 ± .007.517 ± .007.497 ± .003
RPL.540 ± .004.714 ± .003.521 ± .001.556 ± .001.494 ± .015.284 ± .003.552 ± .021.523 ± .002
Qwen3-8B, EMNQTriviaQAPopQAHotpotQA2WikiMuSiQueBamboogleAvg
RPL (w/o mutation).533 ± .006.707 ± .002.516 ± .002.544 ± .003.532 ± .006.284 ± .003.565 ± .010.526 ± .003
Matched RFT.539 ± .004.708 ± .001.524 ± .001.550 ± .003.511 ± .033.285 ± .002.576 ± .008.528 ± .004
RPL.547 ± .001.721 ± .001.540 ± .001.559 ± .001.561 ± .004.297 ± .008.592 ± .017.545 ± .003

RPL outperforms the matched RFT control on the seven benchmarks at both scales. The control recovers about a quarter of mutation’s average gain over RL alone at 4B and almost none at 8B. These results suggest that program mutation provides benefits beyond applying SFT on successful policy-generated trajectories. In particular, mutation enables exploration of alternative retrieval programs that may be difficult to discover through direct on-policy sampling alone. We also note that these RPL results use a corrected SFT that fixes a formatting issue in our original implementation. We will incorporate the updated results into the final revision.


[W2,Q3] Programmable retrieval vs. fixed pipelines and tool-based agents

We thank the reviewer for suggesting these comparisons. We added two controls with the same backbone, retrieval components, and RL training budget. The fixed hybrid pipeline retains Search-R1’s search action but retrieves the top 20 documents from each of the dense and sparse retrievers, fuses the results, and reranks the combined candidates to retain the top 5. This provides a stronger, albeit more expensive, retrieval strategy for open-domain QA. The multi-tool agent accesses the same primitives as separate tools, making one tool call per turn, with budgets of 3, as for other methods, or 10 turns.

Qwen3-4B, EMNQTriviaQAPopQAHotpotQA2WikiMuSiQueBamboogleAvg
Search-R1.510 ± .002.661 ± .001.481 ± .003.483 ± .001.453 ± .004.214 ± .004.499 ± .007.471 ± .001
Fixed hybrid pipeline.519 ± .007.700 ± .003.508 ± .002.539 ± .003.486 ± .013.265 ± .005.544 ± .008.509 ± .002
Multi-tool agent (3 turns).528 ± .001.686 ± .005.504 ± .005.505 ± .002.446 ± .013.222 ± .005.504 ± .009.485 ± .002
Multi-tool agent (10 turns).527 ± .002.691 ± .000.497 ± .004.531 ± .001.486 ± .006.268 ± .004.541 ± .017.506 ± .003
RPL (w/o mutation).517 ± .002.687 ± .002.511 ± .001.515 ± .001.481 ± .010.223 ± .005.483 ± .014.488 ± .003
RPL.540 ± .004.714 ± .003.521 ± .001.556 ± .001.494 ± .015.284 ± .003.552 ± .021.523 ± .002
Qwen3-8B, EMNQTriviaQAPopQAHotpotQA2WikiMuSiQueBamboogleAvg
Search-R1.522 ± .002.683 ± .005.487 ± .008.501 ± .001.493 ± .005.235 ± .003.531 ± .007.493 ± .003
Fixed hybrid pipeline.527 ± .003.713 ± .001.522 ± .002.553 ± .003.543 ± .006.279 ± .003.549 ± .005.527 ± .002
Multi-tool agent (3 turns).526 ± .003.694 ± .004.491 ± .009.516 ± .002.479 ± .016.241 ± .004.509 ± .016.494 ± .003
Multi-tool agent (10 turns).538 ± .002.704 ± .003.523 ± .001.543 ± .003.514 ± .009.283 ± .005.541 ± .007.521 ± .001
RPL (w/o mutation).533 ± .006.707 ± .002.516 ± .002.544 ± .003.532 ± .006.284 ± .003.565 ± .010.526 ± .003
RPL.547 ± .001.721 ± .001.540 ± .001.559 ± .001.561 ± .004.297 ± .008.592 ± .017.545 ± .003

RPL outperforms the fixed hybrid pipeline at both scales on the seven benchmarks by 1.4 and 1.8 EM, with a similar number of retrieval calls. It also outperforms the multi-tool agent under both turn budgets, including with 10 turns, more than three times the budget of the other methods. Two conclusions follow:

  • First, exposing the same components as separate tools does not match composing them in programs.
  • Second, the larger action space is harder to explore without mutation: RPL without mutation matches the fixed pipeline at 8B but trails it at 4B, a gap that program mutation closes.

Note also that the same fixed hybrid pipeline performs poorly on GlobalQA, achieving average answer F1 scores of only 9.5 and 10.3 at 4B and 8B, respectively. Unlike open-domain QA, GlobalQA encompasses tasks with diverse retrieval needs, often requiring broad evidence gathering and aggregation across many documents rather than retrieving only a few highly relevant ones. A fixed pipeline optimized for the latter is therefore less suited to GlobalQA, further motivating the need for retrieval programs that adapt their strategies to the task.


[Q1] Checkpoint selection, data splits, and run variation

We thank the reviewer for these important questions. We follow the prior setup of Search-R1 and its successors: models are trained on the NQ and HotpotQA training splits (79,168 and 90,447 questions, respectively), and checkpoints are selected based on performance on their held-out evaluation splits. The other five benchmarks are out-of-domain and are used for neither training nor checkpoint selection. The evaluation set sizes are NQ (3,610), TriviaQA (11,313), PopQA (14,267), HotpotQA (7,405), 2Wiki (12,576), MuSiQue (2,417), and Bamboogle (125). We will clarify these details in the appendix.

We further report two analyses:

(1) Out-of-domain performance. On the five out-of-domain benchmarks, RPL remains the best performing method:

Qwen3-4B, EMTriviaQAPopQA2WikiMuSiQueBamboogleAvg
Search-R1.661 ± .001.481 ± .003.453 ± .004.214 ± .004.499 ± .007.461 ± .002
Matched RFT.695 ± .002.504 ± .004.476 ± .012.237 ± .007.517 ± .007.486 ± .003
Fixed hybrid pipeline.700 ± .003.508 ± .002.486 ± .013.265 ± .005.544 ± .008.501 ± .002
RPL.714 ± .003.521 ± .001.494 ± .015.284 ± .003.552 ± .021.513 ± .004
Qwen3-8B, EMTriviaQAPopQA2WikiMuSiQueBamboogleAvg
Search-R1.683 ± .005.487 ± .008.493 ± .005.235 ± .003.531 ± .007.486 ± .004
Matched RFT.708 ± .001.524 ± .001.511 ± .033.285 ± .002.576 ± .008.521 ± .006
Fixed hybrid pipeline.713 ± .001.522 ± .002.543 ± .006.279 ± .003.549 ± .005.521 ± .001
RPL.721 ± .001.540 ± .001.561 ± .004.297 ± .008.592 ± .017.542 ± .004

(2) Performance without checkpoint selection. We also evaluate the final training checkpoint (step 1000) for every run, without selecting among checkpoints. RPL again achieves the best performance:

Qwen3-4B, EMNQTriviaQAPopQAHotpotQA2WikiMuSiQueBamboogleAvg
Search-R1.507 ± .001.661 ± .003.480 ± .004.484 ± .000.454 ± .008.217 ± .004.501 ± .019.472 ± .001
Matched RFT.525 ± .004.694 ± .003.506 ± .006.526 ± .004.471 ± .008.235 ± .009.523 ± .010.497 ± .002
Fixed hybrid pipeline.524 ± .002.701 ± .001.511 ± .005.538 ± .002.481 ± .012.270 ± .004.536 ± .014.509 ± .001
RPL.538 ± .004.713 ± .001.519 ± .001.556 ± .001.516 ± .004.280 ± .008.544 ± .012.524 ± .003
Qwen3-8B, EMNQTriviaQAPopQAHotpotQA2WikiMuSiQueBamboogleAvg
Search-R1.521 ± .002.682 ± .003.485 ± .007.503 ± .001.499 ± .008.235 ± .005.515 ± .014.491 ± .002
Matched RFT.539 ± .002.708 ± .001.523 ± .001.548 ± .002.513 ± .035.285 ± .004.584 ± .005.529 ± .005
Fixed hybrid pipeline.527 ± .003.712 ± .002.521 ± .004.554 ± .002.544 ± .004.280 ± .002.549 ± .005.527 ± .002
RPL.546 ± .003.720 ± .001.537 ± .001.559 ± .001.561 ± .004.300 ± .010.589 ± .007.545 ± .002

All results are means over three independent runs. These analyses show that RPL’s gains are not limited to the benchmarks used for checkpoint selection and persist even when evaluating the final checkpoint without selection.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.