Elamur Research⌕
☰
home / papers / 2026 / SR-RAG: Verifiable Multi-Hop Reasoning via On-the-fly Symbolic Graph Construction

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

Paper · 2026 · Zehua Wang, Zhaojin Zhang, Boyu Qiu et al.

Summary

Multi-hop question answering is still difficult for retrieval-augmented generation. Aggregate-first systems such as GraphRAG build a corpus-wide knowledge graph in advance, which is costly and hard to keep current. Dynamic-first agents such as ReAct alternate retrieval and generation, but one wrong intermediate answer can derail every later step. Neither family formally checks intermediate conclusions.

SR-RAG combines the two approaches. A Dynamic Generator splits the question into sub-queries, either step by step or through a dependency plan. For each sub-query, a Symbolic Verifier does the following:

  • retrieves documents and builds a small graph specific to that query;
  • rewrites the graph's entities, relations and attributes as first-order logic facts and rules;
  • has a Prolog interpreter derive the answer.

If the derivation fails because a fact is missing, a feedback loop repairs the premises. An Answer Generator then writes the final response. On several multi-hop benchmarks and a medical QA dataset, the authors report higher accuracy and robustness than existing RAG baselines. The method also yields explicit, checkable reasoning traces.

Key points

  • Logic and solver: The logic language is FOL, and the inference engine is SWI-Prolog accessed through pyswip. Entities become constants, triples (h, r, t) become binary predicates, and attributes become unary or binary predicates. The answer is the variable binding that the premises entail.
  • Two generator modes:
    • ReAct-based: each sub-query is conditioned on the question and the history of verified sub-answers.
    • Plan-based: the plan is a DAG whose nodes can run in parallel; child queries are masked and later filled with their parents' validated answers.
  • Evaluation: The metrics are Acc@R and Acc@L (averaged into Acc) plus recall@5. The data are multiple multi-hop benchmarks and one medical QA dataset.
  • Cost: A question uses about 10k input tokens and 1.9k output tokens overall. Each iteration makes roughly 3 API calls each for the generator, graph construction and symbolic stage, plus 1 call for the answer.
  • Limitations: The method depends on the quality of information extraction, can still be misled by irrelevant or contradictory documents, and adds latency.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Harbin Institute of TechnologyHarbin · China185 works · 29,140 citations🔬Peng Cheng LaboratoryShenzhen · China47 works · 2,699 citations

 Fields, topics and concepts

📚 Shelves 6The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 worksComputer Vision and Pattern Recognition · 3,486 worksInformation Systems · 1,730 works

🧭 Topics 1Research subjects and languages the work is about.Reasoning · 1,685 works

Cite

Cite as Zehua Wang, Zhaojin Zhang, Boyu Qiu, Xiaolong Weng, Ying Xiong, Buzhou Tang and Min Zhang. 2026. SR-RAG: Verifiable Multi-Hop Reasoning via On-the-fly Symbolic Graph Construction. Findings of the Association for Computational Linguistics: ACL 2026.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.findings-acl.1922

@inproceedings{wang2026sr,
  title = {{SR-RAG: Verifiable Multi-Hop Reasoning via On-the-fly Symbolic Graph Construction}},
  author = {Zehua Wang, Zhaojin Zhang, Boyu Qiu, Xiaolong Weng, Ying Xiong, Buzhou Tang and Min Zhang},
  booktitle = {Findings of the Association for Computational Linguistics: ACL 2026},
  year = {2026},
  doi = {10.18653/v1/2026.findings-acl.1922},
  url = {https://doi.org/10.18653/v1/2026.findings-acl.1922}
}

References

32 references, 16 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Sourav Banerjee, Ayushi Agarwal, and Saloni Singla. 2025. Llms will always hallucinate, and we need to live with this. In Intelligent Systems Conference, pages 624–648. Springer. find
  2. Shengyuan Chen, Chuang Zhou, Zheng Yuan, Qinggang Zhang, Zeyang Cui, Hao Chen, Yilin Xiao, Jiannong Cao, and Xiao Huang. 2025. You don’t need pre-built graphs for rag: Retrieval augmented generation with adaptive reasoning structures. arXiv preprint arXiv:2508.06105.
  3. Darren Edge, Ha Trinh, Newman Cheng, Joshua Bradley, Alex Chao, Apurva Mody, Steven Truitt, Dasha Metropolitansky, Robert Osazuwa Ness, and Jonathan Larson. 2024. From local to global: A graph rag approach to query-focused summarization. arXiv preprint arXiv:2404.16130. find
  4. Zirui Guo, Lianghao Xia, Yanhua Yu, Tu Ao, and Chao Huang. 2024. Lightrag: Simple and fast retrieval-augmented generation. arXiv preprint arXiv:2410.05779.
  5. Bernal Jiménez Gutiérrez, Yiheng Shu, Weijian Qi, Sizhe Zhou, and Yu Su. 2025. From rag to memory: Non-parametric continual learning for large language models. arXiv preprint arXiv:2502.14802.
  6. Haoyu Han, Yaochen Xie, Hui Liu, Xianfeng Tang, Sreyashi Nag, William Headden, Yang Li, Chen Luo, Shuiwang Ji, Qi He, et al. 2025. Reasoning with graphs: Structuring implicit knowledge to enhance llms reasoning. In Findings of the Association for Computational Linguistics: ACL 2025, pages 25698– 257… find
  7. Simeng Han, Hailey Schoelkopf, Yilun Zhao, Zhenting Qi, Martin Riddell, Wenfei Zhou, James Coady, David Peng, Yujie Qiao, Luke Benson, et al. 2024. Folio: Natural language reasoning with first-order logic. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pag…
  8. Kazuki Hayashi, Hidetaka Kamigaito, Shinya Kouda, and Taro Watanabe. 2025. Iterkey: Iterative keyword generation with llms for enhanced retrieval augmented generation. arXiv preprint arXiv:2505.08450. — [arXiv:2505.08450](https://arxiv.org/abs/2505.08450) find
  9. Xanh Ho, Anh-Khoa Duong Nguyen, Saku Sugawara, and Akiko Aizawa. 2020. Constructing a multi-hop qa dataset for comprehensive evaluation of reasoning steps. arXiv preprint arXiv:2011.01060.
  10. Bernal Jimenez Gutierrez, Yiheng Shu, Yu Gu, Michihiro Yasunaga, and Yu Su. 2024. Hipporag: Neurobiologically inspired long-term memory for large language models. Advances in Neural Information Processing Systems, 37:59532–59569.
  11. Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al. 2020. Retrieval-augmented generation for knowledge-intensive nlp tasks. Advances in Neural Information Processing Systems, 33:9459–9474.
  12. Jiaoyang Li, Junhao Ruan, Shengwei Tang, Saihan Chen, Kaiyan Chang, Yuan Ge, Tong Xiao, and Jingbo Zhu. 2025a. Subqrag: Sub-question driven dynamic graph rag. arXiv preprint arXiv:2510.07718. — [arXiv:2510.07718](https://arxiv.org/abs/2510.07718) find
  13. Yangning Li, Weizhi Zhang, Yuyao Yang, Wei-Chieh Huang, Yaozu Wu, Junyu Luo, Yuanchen Bei, Henry Peng Zou, Xiao Luo, Yusheng Zhao, et al. 2025b. Towards agentic rag with deep reasoning: A survey of rag-reasoning systems in llms. arXiv preprint arXiv:2507.09477.
  14. Linhao Luo, Zicheng Zhao, Gholamreza Haffari, Dinh Phung, Chen Gong, and Shirui Pan. 2025. Gfm-rag: graph foundation model for retrieval augmented generation. arXiv preprint arXiv:2502.01113. — [arXiv:2502.01113](https://arxiv.org/abs/2502.01113) find
  15. Tengjun Ni, Xin Yuan, Shenghong Li, Kai Wu, Ren Ping Liu, Wei Ni, and Wenjie Zhang. 2025. Stepchain graphrag: Reasoning over knowledge graphs for multi-hop question answering. arXiv preprint arXiv:2510.02827. — [arXiv:2510.02827](https://arxiv.org/abs/2510.02827) find
  16. Liangming Pan, Alon Albalak, Xinyi Wang, and William Wang. 2023. Logic-lm: Empowering large language models with symbolic solvers for faithful logical reasoning. In Findings of the Association for Computational Linguistics: EMNLP 2023, pages 3806–3824.
  17. Ofir Press, Muru Zhang, Sewon Min, Ludwig Schmidt, Noah A Smith, and Mike Lewis. 2022. Measuring and narrowing the compositionality gap in language models. arXiv preprint arXiv:2210.03350. find
  18. Chengwen Qi, Ren Ma, Bowen Li, He Du, Binyuan Hui, Jinwang Wu, Yuanjun Laili, and Conghui He. 2025. Large language models meet symbolic provers for logical reasoning evaluation. In The Thirteenth International Conference on Learning Representations. find
  19. Parth Sarthi, Salman Abdullah, Aditi Tuli, Shubh Khanna, Anna Goldie, and Christopher D Manning. 2024. Raptor: Recursive abstractive processing for tree-organized retrieval. In The Twelfth International Conference on Learning Representations.
  20. Zhihong Shao, Yeyun Gong, Yelong Shen, Minlie Huang, Nan Duan, and Weizhu Chen. 2023. Enhancing retrieval-augmented large language models with iterative retrieval-generation synergy. arXiv preprint arXiv:2305.15294.
  21. Zhengliang Shi, Shuo Zhang, Weiwei Sun, Shen Gao, Pengjie Ren, Zhumin Chen, and Zhaochun Ren. 2024. Generate-then-ground in retrieval-augmented generation for multi-hop question answering. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Pape…
  22. Saba Sturua, Isabelle Mohr, Mohammad Kalim Akram, Michael Günther, Bo Wang, Markus Krimmel, Feng Wang, Georgios Mastrapas, Andreas Koukounas, Andreas Koukounas, Nan Wang, and Han Xiao. 2024. jina-embeddings-v3: Multilingual embeddings with task lora. Preprint, arXiv:2409.10173.
  23. Harsh Trivedi, Niranjan Balasubramanian, Tushar Khot, and Ashish Sabharwal. 2022b. Musique: Multi-hop questions via single-hop question composition. Transactions of the Association for Computational Linguistics, 10:539–554. find
  24. Prakhar Verma, Sukruta Prakash Midigeshi, Gaurav Sinha, Arno Solin, Nagarajan Natarajan, and Amit Sharma. 2024. Plan* rag: Efficient test-time planning for retrieval augmented generation. arXiv preprint arXiv:2410.20753. — [arXiv:2410.20753](https://arxiv.org/abs/2410.20753) find
  25. Lei Wang, Wanyu Xu, Yihuai Lan, Zhiqiang Hu, Yunshi Lan, Roy Ka-Wei Lee, and Ee-Peng Lim. 2023. Plan-and-solve prompting: Improving zero-shot chain-of-thought reasoning by large language models. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Lon… find
  26. Yuxin Wang, Shicheng Fang, Bo Wang, Qi Luo, Xuanjing Huang, Yining Zheng, and Xipeng Qiu. 2025. Multi-hop reasoning via early knowledge alignment. arXiv preprint arXiv:2512.20144. — [arXiv:2512.20144](https://arxiv.org/abs/2512.20144) find
  27. Zhishang Xiang, Chuanjie Wu, Qinggang Zhang, Shengyuan Chen, Zijin Hong, Xiao Huang, and Jinsong Su. 2025. When to use graphs in rag: A comprehensive analysis for graph retrieval-augmented generation. arXiv preprint arXiv:2506.05690. — [arXiv:2506.05690](https://arxiv.org/abs/2506.05690) find
  28. Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William W Cohen, Ruslan Salakhutdinov, and Christopher D Manning. 2018. Hotpotqa: A dataset for diverse, explainable multi-hop question answering. arXiv preprint arXiv:1809.09600.
  29. Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik R Narasimhan, and Yuan Cao. 2023. React: Synergizing reasoning and acting in language models. In The Eleventh International Conference on Learning Representations.
  30. Hairong Zhang, Jiaheng Si, Guohang Yan, Boyuan Qi, Pinlong Cai, Song Mao, Ding Wang, and Botian Shi. 2025. Rakg: Document-level retrieval augmented knowledge graph construction. arXiv preprint arXiv:2504.09823. — [arXiv:2504.09823](https://arxiv.org/abs/2504.09823) find
  31. Luyao Zhuang, Shengyuan Chen, Yilin Xiao, Huachi Zhou, Yujing Zhang, Hao Chen, Qinggang Zhang, and Xiao Huang. 2025. Linearrag: Linear graph retrieval augmented generation on large-scale corpora. arXiv preprint arXiv:2510.10114. — [arXiv:2510.10114](https://arxiv.org/abs/2510.10114) find
  32. Harsh Trivedi, Niranjan Balasubramanian, Tushar Khot, and Ashish Sabharwal. 2022a. Interleaving retrieval with chain-of-thought reasoning for knowledge-intensive multi-step questions. arXiv preprint arXiv:2212.10509.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/wang-2026-sr-rag-verifiable-multi-hop/