- 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
[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.
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.
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.