SR-RAG: Verifiable Multi-Hop Reasoning via On-the-fly Symbolic Graph Construction

Retrieval-Augmented Generation (RAG) has been widely adopted to enhance large language models (LLMs) by incorporating external knowledge. However, the two main existing paradigms struggle with multi-hop reasoning: aggregate-first approaches suffer from high construction costs and limited adaptability to dynamic knowledge, while dynamic-first approaches rely heavily on LLM reasoning and are prone to error propagation across reasoning steps. To address these limitations, we propose SR-RAG, a symbolic reasoning framework for multi-hop question answering. SR-RAG integrates the advantages of both paradigms by dynamically generating sub-questions, performing information retrieval and symbolic encoding based on an on-the-fly graph, and using a symbolic verifier to formally validate intermediate reasoning steps to ensure the correctness of intermediate answers and the completeness of the reasoning chain . We evaluate SR-RAG on multiple multi-hop benchmarks and a medical dataset. Experimental results demonstrate that it significantly improves both accuracy and robustness.