acceptodds
Under review as a conference paper at ICLR 2027

Logically Provable Reasoning for Multi-Hop Retrieval Augmented Generation

Abstract

Complex questions cannot be reliably answered by a single query to a large language model (LLM) or even a large reasoning model (LRM). Solving such questions often requires multiple retrieval and reasoning steps, where some steps may involve evidence and intermediate results obtained earlier. The system must therefore handle competing reasoning paths, ambiguous entities, and potentially incorrect intermediate bindings. Existing retrieval-augmented generation (RAG) methods typically interleave retrieval and reasoning over multiple steps. However, document-level relevance does not reveal the logical role of each piece of evidence or guarantee that the resulting steps form a complete reasoning plan. To fill this gap, we propose **ProvableRAG**, a logic-based RAG framework that constructs a logically provable retrieval and reasoning plan to achieve conditional logical sufficiency for both retrieval and reasoning. Specifically, the framework first constructs a logical reasoning graph that specifies what information must be retrieved or inferred and how these steps are logically related to each other. A symbolic logic solver verifies whether a potential plan represented in the graph can derive the target answer, while the resulting proof structure and logical reasoning depth guide plan selection and execution. During execution, each step passes only the structured results required downstream, avoiding the accumulation of retrieved documents across nodes. By compiling formally verified proofs into executable retrieval-and-reasoning plans, ProvableRAG enables logically grounded and efficient multi-step evidence acquisition. Across three multi-hop QA benchmarks, ProvableRAG achieves the highest accuracy while significantly reducing search calls and token consumption compared with the strongest baselines. The code is available at https://anonymous.4open.science/r/ICLR27_31209-BB20/.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Retrieval Augmented Generation, Logical Reasoning, Agentic RAG

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_nB5kOpenReview ↗
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
  1. 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.
  2. 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
  1. 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.
  2. 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).
  3. 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:

  1. 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.
  2. 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?
  3. 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:

  1. Please improve the structure and documentation of the provided code.

Cosmetic Comments (not to be interpreted as weaknesses):

  1. The abstract is quite long and introduces unclear terminology (e.g. “conditional logical sufficiency”).
  2. 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).
  3. 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.
  4. The references contain a duplicate (LL616-621) and the paper title needs to be fixed in the .bib for L649.
2 comments
AuthorsOpenReview ↗

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.

W1 (novelty). “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.”

Our contribution is to derive the retrieval plan from a proof of what evidence would suffice to answer the question.

  1. What is proved? HVR validates action plans. LINC and Logic-LM reason from supplied premises. Before retrieval, ProvableRAG tests whether the proposed facts, if established, would jointly entail an answer under the question’s rules (Eq. 3).
  2. What does the proof determine? Plan*RAG and LogicRAG organize dependencies among subqueries. We trace the proof backward to select the operations needed to establish its premises. In the film example in Appendix C, the proof using full dates omits the year-extraction steps entirely.
  3. Does this change the result? Proof checking changes which plan is selected or whether one is selected on 9.59–24.00% of questions. In a separate ablation, replacing Prover9 with an LLM verifier lowers exact match (EM) by 3.98–9.89 percentage points across all six model–dataset settings (Q2 below).
  4. How does it compare with executable RAG? We added comparisons with Plan*RAG, PyRAG, and SR-RAG. On GPT-4o-mini, ProvableRAG scores 59.21% on HotpotQA versus 50.34% for PyRAG under the same string-based metric, and uses 47.0% fewer tokens per question on average across the three benchmarks. The table reports accuracy based on normalized string containment on HotpotQA and mean tokens per question across the three benchmarks.
Method (GPT-4o-mini)HotpotQA String-based (%)Tokens/question
Plan*RAG40.507,719
PyRAG50.347,951
SR-RAG (ReAct)54.7111,939
ProvableRAG59.214,215

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.

Q2. With only 2–4 intended hops, how often does proof checking change the plan, and does it improve accuracy?

  • We added a plan-selection analysis and a separate end-to-end verifier ablation. For each question, we held the graph, candidate pool, and ranking fixed and compared the selection with pre-retrieval checking enabled and disabled. On MuSiQue-Ans with Mistral, enabling checking changed the selection on 580/2,417 questions (24.00%).
  • In the ablation, the backbone LLM replaced Prover9 for both pre-retrieval plan verification and answer verification during execution. EM fell in all six settings, including 27.72% to 17.83% on MuSiQue-Ans with Mistral. This comparison measures the combined effect of replacing both verification stages. Across the six settings, the loss in LLM-judged accuracy ranges from 4.80 to 12.00 percentage points (Appendix Table 6, p. 15).
DatasetPlan selection changed (GPT-4o-mini)Plan selection changed (Mistral Small 4)EM gain with Prover9, GPT / Mistral (percentage points)
HotpotQA9.59%12.01%+3.98 / +5.28
2WikiMQA12.01%15.60%+5.28 / +6.93
MuSiQue-Ans18.04%24.00%+7.90 / +9.89
  • Candidate-level results. Prover9 admitted 62.36–77.32% of candidates. The logs classify 20.03–30.10% as unverified, with separate counts for timeouts (1.79–5.69%) and errors (0.87–1.85%). A failed proof search leaves validity undetermined. Please see §5.4 (p. 9) and Appendix Table 6 (p. 15) for the verification outcomes and denominators.

W2 and comment 4. Which pipeline produced the results? Algorithm 1 prioritizes shallow proofs, while the released planner appears to prioritize plans already in progress.

  • A deeper plan can be further along, so the two policies can choose different searches. The gain attributable to proof-depth ordering remains unverified until we identify the scheduler used for each table. Appendix D (pp. 20–21) now distinguishes Algorithm 1’s depth-ordering policy from the progress-priority policy. Table 4 (p. 9) labels the evaluated row “Full configuration.”
  • Reproducibility. We will document the entry point, scheduler, and command for each table, rerun comparisons with missing configurations, and align Algorithm 1 and Figure 1 with the evaluated policy.
AuthorsOpenReview ↗

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-mediumHotpotQA2WikiMQAMuSiQue-Ans
LogicRAG70.169.450.1
ProvableRAG73.075.954.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).
Reviewer_U5zzOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

ProvableRAG utilizes a symbolic theorem prover to plan the retrieval process for multi-hop QA tasks. The procedure starts with splitting the question into facts that need to be obtained to answer it, and building a logical graph from them. Then Prover9 determines if a selected set of facts would allow deriving an answer, assuming that these facts can be obtained. The proofs obtained from this process allow choosing retrieval plans, which are subsequently executed through the retrieval, reasoning, and validation of facts. The paper claims higher accuracy compared to the RAG baselines, and fewer tokens compared to LogicRAG.

Critical strengths
  1. The attempt to validate a plan and determine whether it would result in an answer before performing any retrieval is an interesting approach.
  2. If a certain plan fails, the system will try the next one without discarding facts that have already been checked. Appendix C provides an example of that.
  3. According to Table 1, ProvableRAG performs better than LogicRAG in terms of both accuracy metrics on all three datasets and two backbone models.
Critical weaknesses
  1. I still do not see the necessity of using a theorem prover for the problem discussed in the paper. The movie example from Section 1 demonstrates that assigning the right birth date to each director is important, but this can also be done using a structured plan with explicit variables. A dependency graph is not a formal proof, but a structured planner can still preserve the relationships between the directors, movies, and birth dates. In other words, the example does not show what is wrong with an otherwise valid plan. Symbolic verification of plans has also been considered in related papers like HVR [1] and SR-RAG [2]. It should be noted that these works use verification in different contexts, so the comparison is not exact.
  2. The origin of the inference rules used by Prover9 is unclear. Section 4.1 says that the proposed relations for the graph are not automatically added to the background theory as inference rules. Section 4.2, on the other hand, presupposes that the appropriate rules are provided. Appendix C provides such rules for the example problem, whereas Appendix F.1 gives only the description of how the graph is built. I could not find an explanation of how rules are created for any given question and how their validity is checked.
  3. Table 3 presents a comparison of different plan-ranking techniques, and Table 4 examines graph construction, reasoning-depth-guided scheduling, and information passing. A simpler planner with the same graph and executor might give similar results, but we can't say that from the current experiments. The rejection of candidate plans by Prover9 is also not analyzed.
  4. Appendix A.3 says Table 2 does not include graph creation done offline; however, according to Appendix F.1, there are two calls to the LLM per question to create a graph. Whether these calls are included is not known. Table 2 also suggests that even though ProvableRAG uses fewer tokens compared to LogicRAG (1531.2 vs. 1777.9), it takes more time to run than LogicRAG (11.50s vs. 9.83s).

[1] Petruzzellis et al. (2025). Hierarchical Planning for Complex Tasks with Knowledge Graph-RAG and Symbolic Verification. ICML 2025.

[2] Wang et al. (2026). SR-RAG: Verifiable Multi-Hop Reasoning via On-the-fly Symbolic Graph Construction. Findings of ACL 2026.

Questions for authors
  1. Please show an example of one of the plans identified during the evaluation that was rejected by Prover9, along with the reason for rejection. Was this issue apparent based on dependency checks and variable bindings alone?
  2. Please show the prompt or code used to generate the background theory and answer condition for a new question, and not just the graph construction prompts listed in Appendix F.1.
  3. Please give the accuracy and number of tokens required for a variant without Prover9 using the same graph and executor. Additionally, please show how often proof checking changes the plan chosen.
  4. Please show the breakdown of the average cost per question into graph construction, plan construction, proof search, retrieval, and finally answering.
4 comments
AuthorsOpenReview ↗

Response to Reviewer U5zz (1/3)

Thank you for your insightful review and valuable questions! We will address your concerns point-to-point.

W1.1 and Q3.1 (Prover9 ablation). What happens to accuracy and token use if the graph and executor are kept fixed and Prover9 is removed?

We added a direct Prover9 ablation on two backbones. We replaced every Prover9 call with a call to the corresponding backbone LLM, keeping the question graph and executor fixed. This replaces both plan verification before retrieval and answer verification during execution. The two HotpotQA accuracy columns report normalized string containment and LLM judgments, respectively. Tokens per question are averaged across the three datasets.

BackboneMethodHotpotQA String-based (%)HotpotQA LLM-judged (%)Tokens/question
GPT-4o-miniProvableRAG (full)59.2165.791531.2
GPT-4o-miniProver9 → LLM52.2360.9912,612.2
Mistral Small 4ProvableRAG (full)53.7057.809,584.3
Mistral Small 4Prover9 → LLM45.4251.4024,222.1

The full system had higher accuracy under both metrics in all six settings and used fewer tokens on both backbones. Table 2 (p. 8) gives both HotpotQA accuracy metrics and mean costs across the three benchmarks. Appendix Table 6 (p. 15) gives the judged-accuracy losses for all six settings.

W1.2, W3.2 and Q1 (a rejected plan). Could a structured planner with explicit variables already detect the problem in the movie example? Can you show a plan from the evaluation whose failure was invisible to dependency and variable-binding checks?

We agree that explicit variables can keep the two directors’ dates separate. A MuSiQue-Ans example illustrates the additional check. The question was “Why did Roncalli leave the city where the creator of La Schiavona died?” Let LL denote the painting. Candidate A passed the structural checks because both retrievals used the same city variable xx. Its anticipated outputs were

HA=DiedIn(p,x)∧LeftBecause(Roncalli,x,r).H_A = \mathrm{DiedIn}(p,x) \land \mathrm{LeftBecause}(\mathrm{Roncalli},x,r).

The answer rule required

CreatorOf(p,L)∧HA→Qq(r).\mathrm{CreatorOf}(p,L) \land H_A \rightarrow Q_q(r).

The first query mentioned the painting’s creator, but its declared output established only that person pp died in city xx. No premise or rule established that pp created the painting. Even if both retrievals succeeded, the answer rule would still lack that premise. With pre-verification disabled, the planner selected A. When enabled on the same candidate pool, Prover9 returned SEARCH_EXHAUSTED for A, and the planner selected no candidate.

In a separate run on the same question, candidate B explicitly requested the city where the painting’s creator died. Its anticipated outputs were

HB=DeathCityOfCreatorOf(L,x)∧LeftBecause(Roncalli,x,r).H_B = \mathrm{DeathCityOfCreatorOf}(L,x) \land \mathrm{LeftBecause}(\mathrm{Roncalli},x,r).

Under that run’s answer rule, HB→Qq(r)H_B \rightarrow Q_q(r), the first fact linked the city to the painting’s creator and the second supplied the reason. Prover9 found the conditional proof, and the planner selected B for execution. Please see §4.2 (Eq. 3, p. 5) for the verification criterion and Appendix C (p. 20) for both runs.

Q3.2 (plan selection). How often does proof checking change the selected plan?

We compared plan selection with pre-retrieval verification enabled and disabled, holding each question’s graph, candidate pool and ranking rule fixed. The first four percentages below are over checked candidates. The final column is the percentage of development questions for which the selection outcome changed, including a change from a selected plan to no plan.

BackboneDatasetAdmittedUnverifiedTimeoutErrorPlan selection changed
GPT-4o-miniHotpotQA77.32%20.03%1.79%0.87%9.59%
GPT-4o-mini2WikiMQA73.50%22.61%2.92%0.97%12.01%
GPT-4o-miniMuSiQue-Ans68.02%26.05%4.19%1.74%18.04%
Mistral Small 4HotpotQA72.13%24.09%2.84%0.94%12.01%
Mistral Small 42WikiMQA69.29%26.98%2.81%0.93%15.60%
Mistral Small 4MuSiQue-Ans62.36%30.10%5.69%1.85%24.00%

Proof checking changed the selection on 9.59–24.00% of questions. On both backbones, it changed the outcome most often on MuSiQue-Ans. An unverified candidate lacked a proof in the search performed. Discarding a lower-ranked candidate can leave the selected plan unchanged. Please see §5.4 (p. 9) and Appendix Table 6 (p. 15) for the question counts and the candidate-level outcomes.

AuthorsOpenReview ↗

Response to Reviewer U5zz (2/3)

W1.3 (related symbolic verifiers). How does this use of verification compare with HVR and SR-RAG?

HVR checks whether a robot can execute a proposed action sequence. SR-RAG retrieves evidence for each subquestion and checks whether that evidence entails the subanswer. ProvableRAG checks before retrieval whether the planned outputs, if obtained, would jointly entail an answer to the original question. In the Roncalli example, SR-RAG’s evidence check can assess support for each subanswer once evidence arrives. ProvableRAG can identify the missing creator premise in A before issuing either search.

We added a comparison with SR-RAG on both backbones. The two HotpotQA columns give string-based and LLM-judged accuracy. Tokens per question are averaged across the three datasets.

BackboneMethodHotpotQA String-based (%)HotpotQA LLM-judged (%)Tokens/question
GPT-4o-miniSR-RAG54.7161.9011,939.2
GPT-4o-miniProvableRAG59.2165.794,214.8
Mistral Small 4SR-RAG50.0154.0014,273.9
Mistral Small 4ProvableRAG53.7057.809,584.3

ProvableRAG leads under both metrics on HotpotQA and uses fewer tokens per question on both backbones. SR-RAG leads under both metrics on 2WikiMQA. On MuSiQue-Ans it leads under both metrics with GPT-4o-mini, while with Mistral the string-based score favors ProvableRAG and the LLM-judged score favors SR-RAG. Please see §5.2, Table 2 (p. 8), for both HotpotQA accuracy metrics and the three-benchmark mean costs.

W2 and Q2 (rule generation and validity). How are the background theory and answer condition generated for a new question, and what does the verifier establish about them?

For each question, COMPILE_PROMPT asks the LLM to specify the facts needed, the variables they share and how their values determine the answer. The compiler constructs question-specific conjunction, projection and answer rules from that program and adds applicable rules from a fixed library. The graph relations in Appendix F.1 guide plan construction. The pseudocode below illustrates how the film comparison in Appendix C defines Qq(a)Q_q(a), where aa is the film to return.

needs, goal ← LLM(COMPILE_PROMPT, question)
Γq ← conjunction_and_projection_rules(needs) ∪ applicable_library_rules(needs)

# Appendix C: Which film has the director who died earlier?
B ← Director(f1, d1) ∧ Died(d1, t1) ∧ Director(f2, d2) ∧ Died(d2, t2)

# goal binds (left, left_answer) = (t1, f1) and (right, right_answer) = (t2, f2)
Γq ← Γq ∪ {
    B ∧ Earlier(t1, t2) → Qq(f1),
    B ∧ Earlier(t2, t1) → Qq(f2)
}

The proof establishes entailment under the compiled rules. If the compiler misreads the question, a successful proof can still answer the wrong formalized question. Please see §4.2 (Eq. 3, p. 5) and Appendix C (pp. 18–19) for the formal criterion and the worked film rules. Appendix F currently gives role-level templates. We will add the verbatim compiler prompt there.

W3.1 (simpler planners). Can a simpler planner achieve similar results with the same graph and executor?

We evaluated two additional planning strategies with Mistral Small 4, holding the question graph and executor fixed. In LLM as planner, the LLM chooses which candidate path to try first without a prescribed ranking criterion. In All paths, every candidate path remains available to the executor. The table reports LLM-judged accuracy and thousands of tokens per question for each dataset.

StrategyHotpotQA accuracy (%)kTokens/q2WikiMQA accuracy (%)kTokens/qMuSiQue-Ans accuracy (%)kTokens/q
Coverage + cost57.09.862.99.931.011.2
Random51.38.752.67.422.58.1
Path length49.512.450.411.720.318.6
Full configuration57.89.5263.89.4434.79.49
LLM as planner54.413.359.212.528.114.4
All paths50.319.652.218.721.221.6

The full configuration has higher judged accuracy and uses fewer tokens than either added strategy on all three datasets. On MuSiQue-Ans, it reaches 34.7% at 9.49k tokens, compared with 28.1% at 14.4k for LLM selection and 21.2% at 21.6k for all paths. Random ordering is cheaper and less accurate. Please see §5.4, Table 4 (p. 9). We use the label “Full configuration” because the available run records do not isolate the contribution of proof-depth ordering.

AuthorsOpenReview ↗

Response to Reviewer U5zz (3/3)

W4.1 (online graph construction). Do the reported token totals include the two LLM calls used to build each question’s graph?

Yes. Both graph-construction calls are included in ProvableRAG’s online cost. The offline exclusion in Appendix A.3 concerns corpus graphs that other methods build before answering questions. For ProvableRAG on 2WikiMQA with GPT-4o-mini, online graph construction accounts for 948.7 of the 1,531.2 tokens per question. Please see §5.3 (p. 9) and Appendix A.3 (p. 15) for the cost accounting.

W4.2 and Q4 (tokens and latency). Why does ProvableRAG take longer than LogicRAG despite using fewer tokens? What does each stage cost?

We measured tokens and elapsed time for each stage. On 2WikiMQA with GPT-4o-mini, ProvableRAG used 1,531.2 tokens in 11.50 s per question, compared with 1,777.9 tokens in 9.83 s for LogicRAG. The breakdown below is for ProvableRAG in that setting.

StageLLM tokens/questionSeconds/question
Online graph construction948.74.80
Plan construction and formalization119.60.90
Prover9 proof search0.00.85
Retrieval and evidence validation332.14.00
Final answer generation130.80.95
Total1,531.211.50

Graph construction and retrieval with evidence validation took 4.80 s and 4.00 s, respectively. Plan construction and proof search together took 1.75 s for 119.6 LLM tokens. Proof search alone took 0.85 s with zero LLM tokens. Even subtracting the full 0.85 s leaves 10.65 s, above LogicRAG’s 9.83 s. Graph construction and evidence retrieval/validation together account for 8.80 s, or 77% of total latency. Please see §5.3, Table 3 (p. 9), for the end-to-end comparison and Appendix A.3 (p. 15) for the stage costs.

For completeness, the following table reports input, generated and total online tokens on 2WikiMQA, in thousands per question. Values are rounded to one decimal, so displayed components can differ from the displayed total after rounding.

MethodInputGeneratedTotal online
GPT-4o-mini
Base model0.10.10.2
Vanilla RAG (Top-3)0.50.00.5
ReAct10.50.911.4
KGP9.81.311.1
RAPTOR2.40.22.6
HippoRAG22.60.22.8
LogicRAG1.50.21.8
SR-RAG10.61.412.0
Plan*RAG6.90.97.8
PyRAG7.01.08.0
ProvableRAG (ours)1.20.41.5
Mistral Small 4
Base model0.20.10.3
Vanilla RAG (Top-3)0.60.00.6
ReAct13.11.214.3
KGP12.21.713.9
RAPTOR3.00.23.2
HippoRAG23.20.33.5
LogicRAG9.51.310.8
SR-RAG12.81.714.5
Plan*RAG8.21.19.3
PyRAG8.81.210.0
ProvableRAG (ours)8.31.29.4
GPT-6 Luna
Base model0.41.01.4
Vanilla RAG (Top-3)2.61.23.8
ReAct19.23.022.2
KGP15.62.518.1
RAPTOR5.51.26.7
HippoRAG27.21.68.8
LogicRAG11.32.413.7
Plan*RAG13.53.717.2
PyRAG9.33.112.3
ProvableRAG (ours)6.93.110.0

On GPT-4o-mini, the difference from SR-RAG is largest on the input side (1.2k vs. 10.6k tokens per question). On Mistral, Plan*RAG has a slightly lower total than ProvableRAG on 2WikiMQA (9.3k vs. 9.4k).

Thank you for the author's response. Most of my concerns have been addressed. However, the response still does not adequately explain how the LLM comparison was implemented in the experiments on w1. This makes the experiments less transparent. I will maintain this score.

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

The authors propose a new approach to RAG by introducing logical verification before information retrieval, allowing the system to better understand the question and identify the important information that needs to be retrieved. With this setup, the method achieves improvements in answer accuracy, although at the cost of increased response time. With relatively low token consumption, the proposed method achieves state-of-the-art performance across the evaluated benchmarks.

Critical strengths

Principled Framework Design: The paper provides a clear decomposition of the multi-hop RAG task into planning, logical verification, and evidence acquisition. By organizing these components into a coherent framework, the proposed method offers a reasonable and well-motivated approach to improving retrieval and reasoning.

Promising Empirical Results: The proposed framework demonstrates consistent accuracy improvements across multiple multi-hop QA benchmarks and model backbones, while reducing reported token consumption compared with LogicRAG.

Critical weaknesses

Missing Core Ablation: Although symbolic proof verification is the central contribution of this paper, Tables 3 and 4, including Appendix Table 7, do not provide an ablation of Prover9. It remains unclear whether the improvements come from symbolic verification or simply from graph-based planning.

Insufficient Comparison with Recent SOTA Methods: The experimental comparison lacks several recent competitive RAG methods, despite their relevance to the proposed framework. In particular, Table 5 only compares against Vanilla RAG, ReAct, and LogicRAG. More comprehensive comparisons with recent multi-hop and symbolic RAG methods would provide stronger evidence for the claimed state-of-the-art performance.

Limited Methodological Novelty: The proposed framework mainly integrates established techniques from symbolic reasoning and graph-based RAG. Although pre-retrieval proof verification is an interesting design, its distinct contribution over existing neuro-symbolic RAG methods remains insufficiently demonstrated.

Questions for authors
  1. Could the authors provide a direct ablation of Prover9 to clarify its contribution independently of graph-based planning?

  2. Could the authors provide comparisons with more recent competitive RAG methods across benchmarks?

2 comments
AuthorsOpenReview ↗

Response to Reviewer KNFN (1/2)

Thank you for your thoughtful review and valuable questions! We will address your concerns point-to-point.

W1.1 and Q1 (direct Prover9 ablation). How much does Prover9 contribute when the graph and executor are held fixed?

We added a direct Prover9 ablation on two backbones. We kept the question graph and executor fixed and replaced every Prover9 call with a call to the corresponding backbone LLM. The LLM received the same verifier inputs and supplied the decision for both plan verification before retrieval and answer verification during execution.

The two HotpotQA accuracy columns report normalized string containment and LLM judgments, respectively. Tokens and search calls are averages per question across the three benchmarks.

BackboneMethodHotpotQA String-based (%)HotpotQA LLM-judged (%)Tokens/qSearches/q
GPT-4o-miniProvableRAG (full)59.2165.794,214.83.199
GPT-4o-miniProver9 → LLM52.2360.9912,612.23.354
Mistral Small 4ProvableRAG (full)53.7057.809,584.33.409
Mistral Small 4Prover9 → LLM45.4251.4024,222.13.613

Prover9 improves both accuracy measures in all six settings while reducing token use and search calls on both backbones. The largest LLM-judged accuracy gains occur on MuSiQue-Ans, at 9.60 percentage points on GPT-4o-mini and 12.00 on Mistral Small 4. Please see Table 2 (p. 8) for both HotpotQA accuracy metrics and the three-benchmark mean costs. Section 5.4 (p. 9) and Appendix Table 6 (p. 15) report the verifier’s effect on judged accuracy across all three benchmarks.

W1.2 (graph planning versus symbolic verification). Could the gains be explained by graph-based planning alone?

We compared removing logical graph construction with replacing the verifier while keeping the graph fixed. Each entry is the change in LLM-judged accuracy from full ProvableRAG, in percentage points.

BackboneAblationHotpotQA2WikiMQAMuSiQue-Ans
GPT-4o-miniWithout logical graph construction−1.9−2.1−7.0
GPT-4o-miniProver9 → LLM verifier−4.80−6.40−9.60
Mistral Small 4Without logical graph construction−2.4−2.5−7.6
Mistral Small 4Prover9 → LLM verifier−6.40−8.41−12.00

Removing the graph reduced accuracy in all six settings. Replacing Prover9 produced a larger drop in every setting, even though the graph and executor stayed the same. The two ablations measure separate changes to the full system. The graph-removal results are in row (d) of Table 5 for Mistral (p. 10) and Appendix Table 9 for GPT-4o-mini (p. 17). Appendix Table 6 (p. 15) gives the verifier-replacement losses for all three benchmarks.

W2 and Q2 (recent competitive methods). How does ProvableRAG compare with recent multi-hop and symbolic RAG methods across benchmarks?

We added comparisons with three recent methods, rerunning each with the same two backbones as ProvableRAG. SR-RAG [1] checks retrieved evidence symbolically, Plan*RAG [2] uses graph-based planning, and PyRAG [3] uses executable multi-hop reasoning. The table reports the same metrics as the direct ablation above.

BackboneMethodHotpotQA String-based (%)HotpotQA LLM-judged (%)Tokens/qSearches/q
GPT-4o-miniSR-RAG54.7161.9011,939.24.020
GPT-4o-miniPlan*RAG40.5044.797,719.03.776
GPT-4o-miniPyRAG50.3463.257,951.33.454
GPT-4o-miniProvableRAG59.2165.794,214.83.199
Mistral Small 4SR-RAG50.0154.0014,273.94.220
Mistral Small 4Plan*RAG35.8036.899,272.93.976
Mistral Small 4PyRAG46.4655.359,939.23.654
Mistral Small 4ProvableRAG53.7057.809,584.33.409

ProvableRAG leads on HotpotQA under both accuracy metrics and uses the fewest search calls on both backbones. SR-RAG leads on 2WikiMQA under both metrics and has the highest LLM-judged accuracy on MuSiQue-Ans. ProvableRAG uses the fewest tokens on GPT-4o-mini. On Mistral, Plan*RAG uses 9,272.9 tokens per question compared with 9,584.3 for ProvableRAG. Please see §5.2, Table 2 (p. 8), for both HotpotQA accuracy metrics and mean token and search costs across the three benchmarks.

AuthorsOpenReview ↗

Response to Reviewer KNFN (2/2)

W3 (methodological novelty). “The proposed framework mainly integrates established techniques from symbolic reasoning and graph-based RAG. Although pre-retrieval proof verification is an interesting design, its distinct contribution over existing neuro-symbolic RAG methods remains insufficiently demonstrated.”

We agree that graph-based planning and symbolic deduction are established techniques. Our contribution is to use a conditional proof to decide which evidence to acquire.

  1. What is verified? Before issuing a search, ProvableRAG asks whether the candidate’s anticipated facts, if established, would jointly entail an answer under the question-specific rules (§4.2, Eq. 3). HVR checks whether a proposed action sequence is executable. SR-RAG checks whether evidence already retrieved for a subquestion supports its subanswer. LINC and Logic-LM reason from supplied premises. In a MuSiQue-Ans question about the creator of La Schiavona, a candidate correctly linked two searches through a shared city but omitted the fact that the person who died there had created the painting. The dependency checks passed. The prover found no proof, and the planner issued neither search.
  2. How does the proof determine retrieval? Plan*RAG and LogicRAG organize dependencies among subqueries. ProvableRAG traces the successful proof backward from the answer to identify the premises to establish and the operations to execute. In the film comparison in Appendix C, the proof comparing full dates omits both year-extraction steps. A different proof can therefore produce a different executable plan from the same graph.
  3. Does this affect actual plans? Holding the graph, candidate pool and ranking fixed, enabling pre-retrieval proof checking changes plan selection on 9.59–24.00% of questions across the six settings. The separate ablation in W1 measures the end-to-end contribution of Prover9 across both verification stages. Against PyRAG on GPT-4o-mini, ProvableRAG improves both accuracy measures on all three datasets with 47.0% fewer tokens per question. SR-RAG leads in judged accuracy on 2WikiMQA and MuSiQue-Ans with both backbones.

Please see §4.2 (Eq. 3, p. 5) and Appendix C (pp. 19–20) for the two examples. Section 5.4 (p. 9) and Appendix Table 6 (p. 15) report the plan-selection analysis.

References

[1] Wang et al. (2026). SR-RAG: Verifiable Multi-Hop Reasoning via On-the-fly Symbolic Graph Construction. Findings of ACL 2026. [2] Verma et al. (2025). Plan*RAG: Efficient Test-Time Planning for Retrieval Augmented Generation. ICLR 2025 Workshop on Reasoning and Planning for LLMs. [3] Sun et al. (2026). Retrieval is Cheap, Show Me the Code: Executable Multi-Hop Reasoning for Retrieval-Augmented Generation. arXiv:2605.12975.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.