- Rating
- 1
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This work presents ProvableRAG, a RAG-based framework for multi-hop question answering. The framework consists of three parts: (1) construct a graph-plan of retrieval and reasoning steps to answer a presented question, (2) verify that the proposed plan could, in theory, answer the question using a logic solver, and (3) structured execution of retrieval & reasoning steps outlined in the plans (lower depth is prioritized) with fallbacks to alternative plans.
The authors evaluate their framework on three common multi-hop QA benchmarks (HotpotQA, 2WikiMultiHopQA, MuSiQue), comparing against eight baseline methods and reporting that they outperform them across nearly all settings. The work also reports results on two web-search QA benchmarks (BrowseComp+, Bamboogle), where they outperform the four baselines that are compared to. Across all results, exact match/substring accuracy and LLM-as-a-judge scoring is reported.
Critical strengths
- Presentation of results: Figure 1 clearly outlines the framework, its components and the sequence of steps taken. Figure 2 and all tables present the results clearly. The case study in appendix C is a good addition. The formalization of the problem is also good. Broadly, they portray a clear image of the proposed method and the problem at the core of the method.
- Extensive baselines: 8 baselines are compared to their method. The choice of baselines are extensive, as they covers a variety of categories of RAG methods.
Critical weaknesses
- Incremental contribution unclear: The framework combines structured planning, symbolic/logic verification and structured execution of retrieval and reasoning steps. The idea of pre-planning a reasoning graph has been presented already (Plan*RAG, LogicRAG). Symbolic solvers for verification have been used (LINC, Logic-LM). Pre-execution validation has also been presented (Hierarchical Planning for Complex Tasks with Knowledge Graph-RAG and Symbolic Verification, ICML 2025). Also, structured execution with recovery has also been proposed (PyRAG). The main contribution of this work lies in combining individual ideas into a unified pipeline, yet its added benefit over closely related methods is not clear.
- Reproducibility/Implementation discrepancies: First, There is no reproducible connection between the provided code and the reported experimental results. The code bundle contains multiple different pipeline, but doesn’t clearly define which one was used for the experiments. Also, the implemented scheduling policy differs from what is presented in the paper (provablerag/planner.py). Figure 1 and Algorithm 1 prioritize by smaller depth first. The implementation prioritizes plans on which it has already made more incremental progress (which could be a longer plan instead of a shorter one).
- Correctness of evaluation results: The following raises questions regarding the validity of the overall experimental results. Table 5 lists Bamboogle EM results. The Bamboogle dataset consists of 125 questions. Judging EM on 125 questions must yield increments of 100/125 = 0.8. The only result (out of 10) in that table aligned with this is 60.8 EM using ProvableRag with GPT-5.6-luna-medium. Unless this is an average of multiple runs, which isn’t specified, this needs to be corrected.
Questions for authors
Questions:
- Why was GPT-4o-mini chosen as a model? It is quite outdated and the work reports stronger results on a newer model of the GPT family (GPT-5.6-luna), yet those results are placed in the appendix.
- On the three multi-hop QA benchmarks you evaluate, hop counts span 2-4 intended hops. Is a logical proof of plans/proofs of depth at ≤ 4 (or slightly more) really necessary? How many produced plans tend to be invalid s.t. this validation step makes a significant difference?
- Are all evaluation results a single full pass on 1000 questions? Is the same random sample kept across main and ablation results? If so, this should be made clearer in the setup.
Additional Comments:
- Please improve the structure and documentation of the provided code.
Cosmetic Comments (not to be interpreted as weaknesses):
- The abstract is quite long and introduces unclear terminology (e.g. “conditional logical sufficiency”).
- The paper would benefit from replacing LLM-isms (terminology and sentence structures) and consistent usage of terms throughout. While the authors acknowledge the use in the AI Statement, there are repeated mentions of underspecified terms (e.g. acquisition control, dependency management, backbone) and terminology switches throughout (e.g. the interchangeable use of proof vs. plan).
- The introduction mentions results on two web-search QA benchmarks. None of these results are presented in the main body of the paper and offloaded to the appendix without any further acknowledgement or discussion in the results section.
- The references contain a duplicate (LL616-621) and the paper title needs to be fixed in the .bib for L649.
2 comments
Response to Reviewer nB5k (2/2)
W3. How can Table 5 report Bamboogle EM scores outside the 0.8-point increments implied by 125 questions?
- Your arithmetic is correct. The original benchmark has 125 questions, so each correct answer changes single-pass EM by 0.8 percentage points. Of the ten entries in the submitted Table 5, only 60.8% (76/125) is attainable in a single full pass. The table gives no aggregation rule that explains the other nine. Press et al., §3.2
- We have withdrawn the Bamboogle EM comparison pending verification. Appendix B.1, Table 7 (p. 16), now reports only search calls for Bamboogle. We will recompute EM from the predictions and report the number correct, the denominator, and any averaging across runs.
Q1. Why use GPT-4o-mini in the main comparison and leave the newer GPT model in the appendix?
GPT-4o-mini served as the smaller API model alongside Mistral Small 4. ProvableRAG also outperforms LogicRAG on all three datasets with GPT-5.6-luna-medium. The largest gain is on 2WikiMQA, at 6.5 percentage points. Please see §5.2 (p. 7) for the discussion and Appendix Table 8 (p. 16) for the full comparison.
| LLM-judged accuracy (%) with GPT-5.6-luna-medium | HotpotQA | 2WikiMQA | MuSiQue-Ans |
|---|---|---|---|
| LogicRAG | 70.1 | 69.4 | 50.1 |
| ProvableRAG | 73.0 | 75.9 | 54.5 |
Q3. Was every result a single pass over 1,000 questions? Did the main experiments and ablations use the same sample?
We used the complete development split of each benchmark for ProvableRAG, and the main and ablation experiments used exactly the same one. We evaluated all 7,405 HotpotQA questions, 12,576 2WikiMultiHopQA questions, and 2,417 MuSiQue-Ans questions for 3 runs. We will report the split, question IDs, seed where applicable, and run count for each table.
Comments 5–8. Please shorten the abstract, clarify terminology, discuss web-search results in the main text, and correct the references.
- Abstract and terminology. We revised the abstract to state the conditional guarantee directly. The answer follows under the formalized rules if the required facts are established. The abstract (p. 1) and §4.2 (p. 5) distinguish the proof (the derivation) from the plan (the executable steps).
- Web-search results. On BrowseComp+, ProvableRAG and LogicRAG scored 17.4% and 14.8% with GPT-5.6-luna-medium and 10.6% and 8.9% with Mistral Small 4 (LLM-judged accuracy). Mean searches per question also fell from 5.1 to 3.1 and from 4.6 to 3.9, respectively. Please see §5.2 (p. 7) and Appendix B.1, Table 7 (p. 16). We address Bamboogle EM under W3 above.
- References. We merged the duplicate Press et al. entries and corrected the Plan*RAG title in the revised reference list (pp. 13–14).
Response to Reviewer nB5k (1/2)
Thank you for your close reading of the manuscript and code. We will address your concerns point-to-point in the following.
Our contribution is to derive the retrieval plan from a proof of what evidence would suffice to answer the question.
Please see §2.2 (p. 3) for the comparison with deduction from supplied premises, and §4.2 (Eq. 3, p. 5) and Appendix C (p. 19) for the proof and executable steps. Table 2 (p. 8) reports the full comparison on both backbones, including LLM-judged HotpotQA accuracy and mean costs across the three benchmarks.