Logically Provable Reasoning for Multi-Hop Retrieval Augmented Generation

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