Elamur Research⌕
☰
home / papers / 2026 / Interactive Semantic Parsing with Reinforcement Learning for Knowledge Graph Reasoning

Interactive Semantic Parsing with Reinforcement Learning for Knowledge Graph Reasoning

Paper · 2026 · Yurun Song, Xiangqing Shen, Jianfei Yu et al.

Summary

LLMs often hallucinate facts on knowledge-heavy questions. Most knowledge-graph (KG) augmented methods simply walk along graph edges, which leaves constraints such as time filters or counting to be handled afterwards. Classical semantic parsing expresses this logic in executable queries, but it depends on scarce, costly annotated logical forms.

The authors propose Interactive Semantic Parsing, in which an LLM agent assembles a solution turn by turn. On each turn it produces a reasoning thought and a command. The command runs against the KG, and the textual result is fed back as context for the next turn. Training uses reinforcement learning rewarded only by final answers, so no gold programs are needed. To ease sparse rewards, a distance-aware process reward credits intermediate steps that bring the agent topologically closer to the answer.

Experiments on WebQSP and CWQ give state-of-the-art results, with the largest gains on complex queries. This suggests that logic-rich KG reasoning can be learned without labeled parses.

Key points

  • Commands come in three types: <node> (relation expansion), <SPARQL> (structured query, SPARQL being the logical form used) and <answer>. The agent may activate any subset within a single step.
  • Optimizing per state worked better than optimizing per trajectory (16 sampled trajectories per example). The trajectory-level variant showed high variance and no clear upward trend.
  • During pruning, identical successful commands are deduplicated and all failed actions are kept.
    • Keeping duplicate successes raised F1 by only about 4.2%.
    • It also multiplied rollout time by 13.9×.
  • In the reward ablation, the process-dominant setting (w1 = 0.3, w2 = 0.6) gave a 16.5% relative improvement. The outcome-only setting reached just +3.6%.
  • Limitations:
    • Evaluation covers only Freebase-based benchmarks, not Wikidata.
    • Node operations still rely on predefined tools.
    • The reward assumes a fairly complete KG.
  • Code is released on GitHub (NUSTM/ISP-KGR).

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

🎓University of Chinese Academy of SciencesBeijing · China147 works · 8,480 citations🎓Nanjing UniversityNanjing · China74 works · 7,814 citations🎓Nanjing University of Science and TechnologyNanjing · China14 works · 1,590 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 works

🧭 Topics 3Research subjects and languages the work is about.Reasoning · 1,426 worksKnowledge graphs & ontologies · 192 worksSemantic parsing & meaning representation · 185 works

Cite

Cite as Yurun Song, Xiangqing Shen, Jianfei Yu and Rui Xia. 2026. Interactive Semantic Parsing with Reinforcement Learning for Knowledge Graph Reasoning. 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.1023

@inproceedings{song2026interactive,
  title = {{Interactive Semantic Parsing with Reinforcement Learning for Knowledge Graph Reasoning}},
  author = {Yurun Song, Xiangqing Shen, Jianfei Yu and Rui Xia},
  booktitle = {Findings of the Association for Computational Linguistics: ACL 2026},
  year = {2026},
  doi = {10.18653/v1/2026.findings-acl.1023},
  url = {https://doi.org/10.18653/v1/2026.findings-acl.1023}
}

References

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

  1. Kurt D. Bollacker, Colin Evans, Praveen K. Paritosh, Tim Sturge, and Jamie Taylor. 2008. Freebase: a collaboratively created graph database for structuring human knowledge. In Proceedings of the ACM SIG-MOD International Conference on Management of Data, SIGMOD 2008, Vancouver, BC, Canada, June 10-1… find
  2. Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter,… — Language Models are Few-Shot Learners
  3. Liyi Chen, Panrong Tong, Zhongming Jin, Ying Sun, Jieping Ye, and Hui Xiong. 2024. Plan-on-graph: Self-correcting adaptive planning of large language model on knowledge graphs. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, N… find
  4. Zhuo Chen, Fei Wang, Zixuan Li, Zhao Zhang, Weiwei Ding, Chuanguang Yang, YongJun Xu, Xiaolong Jin, and Jiafeng Guo. 2025. Knowcoder-a1: Incentivizing agentic reasoning capability with outcome supervision for KBQA. CoRR, abs/2510.25101. — [arXiv:2510.25101](https://arxiv.org/abs/2510.25101) find
  5. DeepSeek-AI. 2025. Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning. CoRR, abs/2501.12948.
  6. Haishuo Fang, Xiaodan Zhu, and Iryna Gurevych. 2024. DARA: decomposition-alignment-reasoning autonomous language agent for question answering over knowledge graphs. In Findings of the Association for Computational Linguistics, ACL 2024, Bangkok, Thailand and virtual meeting, August 11-16, 2024, page… find
  7. Guangze Gao, Zixuan Li, Chunfeng Yuan, Jiawei Li, Wu Jianzhuo, Yuehao Zhang, Xiaolong Jin, Bing Li, and Weiming Hu. 2025a. D-RAG: Differentiable retrieval-augmented generation for knowledge graph question answering. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Proce… find
  8. Jianqi Gao, Jian Cao, Ranran Bu, Nengjun Zhu, Wei Guan, and Hang Yu. 2025b. Promoting knowledge base question answering by directing llms to generate task-relevant logical forms. In AAAI-25, Sponsored by the Association for the Advancement of Artificial Intelligence, February 25 - March 4, 2025, Phi… find
  9. Xiaoxin He, Yijun Tian, Yifei Sun, Nitesh V. Chawla, Thomas Laurent, Yann LeCun, Xavier Bresson, and Bryan Hooi. 2024. G-retriever: Retrieval-augmented generation for textual graph understanding and question answering. In Advances in Neural Information Processing Systems 38: Annual Conference on Neu…
  10. Lei Huang, Weijiang Yu, Weitao Ma, Weihong Zhong, Zhangyin Feng, Haotian Wang, Qianglong Chen, Weihua Peng, Xiaocheng Feng, Bing Qin, and Ting Liu. 2025. A survey on hallucination in large language models: Principles, taxonomy, challenges, and open questions. ACM Trans. Inf. Syst., 43(2):42:1– 42:55…
  11. Ontology-guided reverse thinking makes large language models stronger on knowledge graph question answering. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 15269–15284, Vienna, Austria. Association for Computational Linguisti…
  12. Ziwei Ji, Nayeon Lee, Rita Frieske, Tiezheng Yu, Dan Su, Yan Xu, Etsuko Ishii, Yejin Bang, Andrea Madotto, and Pascale Fung. 2023. Survey of hallucination in natural language generation. ACM Comput. Surv., 55(12):248:1–248:38.
  13. Haoran Luo, Haihong E, Yikai Guo, Qika Lin, Xiaobao Wu, Xinyu Mu, Wenhao Liu, Meina Song, Yifan Zhu, and Anh Tuan Luu. 2025a. Kbqa-o1: Agentic knowledge base question answering with monte carlo tree search. In Forty-second International Conference on Machine Learning, ICML 2025, Vancouver, BC, Canad… find
  14. Jinhao Jiang, Kun Zhou, Zican Dong, Keming Ye, Xin Zhao, and Ji-Rong Wen. 2023a. Structgpt: A general framework for large language model to reason over structured data. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, EMNLP 2023, Singapore, December 6-10, 20… find
  15. Jinhao Jiang, Kun Zhou, Xin Zhao, Yang Song, Chen Zhu, Hengshu Zhu, and Ji-Rong Wen. 2025. Kg-agent: An efficient autonomous agent framework for complex reasoning over knowledge graph. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers),…
  16. Jinhao Jiang, Kun Zhou, Xin Zhao, and Ji-Rong Wen. 2023b. Unikgqa: Unified retrieval and reasoning for solving multi-hop question answering over knowledge graph. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net. find
  17. Baixuan Li, Bo Zhang, Dingchu Zhang, Fei Huang, Guangyu Li, Guoxin Chen, Huifeng Yin, Jialong Wu, Jingren Zhou, Kuan Li, Liangcai Su, Litu Ou, Liwen Zhang, Pengjun Xie, Rui Ye, Wenbiao Yin, Xinmiao Yu, Xinyu Wang, Xixi Wu, and 36 others. 2025a. Tongyi deepresearch technical report. CoRR, abs/2510.24… — [arXiv:2510.24701](https://arxiv.org/abs/2510.24701) find
  18. Mufei Li, Siqi Miao, and Pan Li. 2025b. Simple is effective: The roles of graphs and large language models in knowledge-graph-based retrieval-augmented generation. In The Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28, 2025. OpenReview.net. find
  19. Guangyi Liu, Yongqi Zhang, Yong Li, and Quanming Yao. 2025a. Dual reasoning: A GNN-LLM collaborative framework for knowledge graph question answering. In Conference on Parsimony and Learning, Stanford University, USA, 24-27 March 2025, volume 280 of Proceedings of Machine Learning Research, pages 35… find
  20. Runxuan Liu, Bei Luo, Jiaqi Li, Baoxin Wang, Ming Liu, Dayong Wu, Shijin Wang, and Bing Qin. 2025b. find
  21. Haoran Luo, Haihong E, Zichen Tang, Shiyao Peng, Yikai Guo, Wentai Zhang, Chenghao Ma, Guanting Dong, Meina Song, Wei Lin, Yifan Zhu, and Anh Tuan Luu. 2024a. Chatkbqa: A generate-then-retrieve framework for knowledge base question answering with fine-tuned large language models. In Findings of the… find
  22. Linhao Luo, Yuan-Fang Li, Gholamreza Haffari, and Shirui Pan. 2024b. Reasoning on graphs: Faithful and interpretable large language model reasoning. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net. find
  23. Linhao Luo, Zicheng Zhao, Gholamreza Haffari, Yuan-Fang Li, Chen Gong, and Shirui Pan. 2025b. Graph-constrained reasoning: Faithful reasoning on knowledge graphs with large language models. In Forty-second International Conference on Machine Learning, ICML 2025, Vancouver, BC, Canada, July 13-19, 20… find
  24. Jie Ma, Zhitao Gao, Qi Chai, Wangchun Sun, Pinghui Wang, Hongbin Pei, Jing Tao, Lingyun Song, Jun Liu, Chen Zhang, and Lizhen Cui. 2025. Debate on graph: A flexible and reliable reasoning framework for large language models. In AAAI-25, Sponsored by the Association for the Advancement of Artificial… find
  25. Costas Mavromatis, Soji Adeshina, Vassilis N. Ioannidis, Zhen Han, Qi Zhu, Ian Robinson, Bryan Thompson, Huzefa Rangwala, and George Karypis. 2025. BYOKG-RAG: multi-strategy graph retrieval for knowledge graph question answering. CoRR, abs/2507.04127. find
  26. Costas Mavromatis and George Karypis. 2022. Rearev: Adaptive reasoning for question answering over knowledge graphs. In Findings of the Association for Computational Linguistics: EMNLP 2022, Abu Dhabi, United Arab Emirates, December 7-11, 2022, pages 2447–2458. Association for Computational Linguist… find
  27. Costas Mavromatis and George Karypis. 2025. GNN-RAG: graph neural retrieval for efficient large language model reasoning on knowledge graphs. In Findings of the Association for Computational Linguistics, ACL 2025, Vienna, Austria, July 27 - August 1, 2025, pages 16682–16699. Association for Computat… find
  28. Sayantan Mitra, Roshni R. Ramnani, and Shubhashis Sengupta. 2022. Constraint-based multi-hop question answering with knowledge graph. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies: Industry Track, NAA… find
  29. Shirui Pan, Linhao Luo, Yufei Wang, Chen Chen, Jiapu Wang, and Xindong Wu. 2024. Unifying large language models and knowledge graphs: A roadmap. IEEE Trans. Knowl. Data Eng., 36(7):3580–3599.
  30. Torsten Scholak, Nathan Schucher, and Dzmitry Bahdanau. 2021. PICARD: parsing incrementally for constrained auto-regressive decoding from language models. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, EMNLP 2021, Virtual Event / Punta Cana, Dominican Repu… find
  31. Jinyeop Song, Song Wang, Julian Shun, and Yada Zhu. 2025. Efficient and transferable agentic knowledge graph RAG via reinforcement learning. CoRR, abs/2509.26383. — [arXiv:2509.26383](https://arxiv.org/abs/2509.26383) find
  32. Jiashuo Sun, Chengjin Xu, Lumingyuan Tang, Saizhuo Wang, Chen Lin, Yeyun Gong, Lionel M. Ni, Heung-Yeung Shum, and Jian Guo. 2024. Think-on-graph: Deep and responsible reasoning of large language model on knowledge graph. In The Twelfth International Conference on Learning Representations, ICLR 2024… find
  33. Yawei Sun, Lingling Zhang, Gong Cheng, and Yuzhong Qu. 2020. SPARQA: skeleton-based semantic parsing for complex questions over knowledge bases. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference… find
  34. Alon Talmor and Jonathan Berant. 2018. The web as a knowledge-base for answering complex questions. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2018, New Orleans, Louisiana, USA, June 1-6…
  35. Xingyu Tan, Xiaoyang Wang, Qing Liu, Xiwei Xu, Xin Yuan, and Wenjie Zhang. 2025. Paths-over-graph: Knowledge graph empowered large language model reasoning. In Proceedings of the ACM on Web Conference 2025, WWW 2025, Sydney, NSW, Australia, 28 April 2025- 2 May 2025, pages 3505–3522. ACM.
  36. Gemini Team. 2023. Gemini: A family of highly capable multimodal models. CoRR, abs/2312.11805.
  37. Shuai Wang and Yinan Yu. 2025. iquest: An iterative question-guided framework for knowledge base question answering. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL 2025, Vienna, Austria, July 27 - August 1, 2025, pages 15616– 1… find
  38. Siwei Wu, Zhongyuan Peng, Xinrun Du, Tuney Zheng, Minghao Liu, Jialong Wu, Jiachen Ma, Yizhi Li, Jian Yang, Wangchunshu Zhou, Qunshu Lin, Junbo Zhao, Zhaoxiang Zhang, Wenhao Huang, Ge Zhang, Chenghua Lin, and Jiaheng Liu. 2024. A comparative study on reasoning patterns of openai’s o1 model. CoRR, ab… — [arXiv:2410.13639](https://arxiv.org/abs/2410.13639) find
  39. Guanming Xiong, Haochen Li, and Wen Zhao. 2025. MCTS-KBQA: monte carlo tree search for knowledge base question answering. CoRR, abs/2502.13428. — [arXiv:2502.13428](https://arxiv.org/abs/2502.13428) find
  40. Xiaotong Xu, Yizhao Wang, Yunfei Liu, and Shengyang Li. 2025. SKRAG: A retrieval-augmented generation framework guided by reasoning skeletons over knowledge graphs. In Findings of the Association for Computational Linguistics: EMNLP 2025, pages 13983–13994, Suzhou, China. Association for Computation… find
  41. Wen-tau Yih, Ming-Wei Chang, Xiaodong He, and Jianfeng Gao. 2015. Semantic parsing via staged query graph generation: Question answering with knowledge base. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natur…
  42. Wen-tau Yih, Matthew Richardson, Christopher Meek, Ming-Wei Chang, and Jina Suh. 2016. The value of semantic parse labeling for knowledge base question answering. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, ACL 2016, August 7-12, 2016, Berlin, Germany,…
  43. Donghan Yu, Sheng Zhang, Patrick Ng, Henghui Zhu, Alexander Hanbo Li, Jun Wang, Yiqun Hu, William Yang Wang, Zhiguo Wang, and Bing Xiang. 2023. Decaf: Joint decoding of answers and logical forms for question answering over knowledge bases. find
  44. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net. find
  45. Haoyu Zhang, Jingjing Cai, Jianjun Xu, and Ji Wang. 2019. Complex question decomposition for semantic parsing. In Proceedings of the 57th Conference of the Association for Computational Linguistics, ACL 2019, Florence, Italy, July 28- August 2, 2019, Volume 1: Long Papers, pages 4477–4486. Associati… find
  46. Lingxi Zhang, Jing Zhang, Yanling Wang, Shulin Cao, Xinmei Huang, Cuiping Li, Hong Chen, and Juanzi Li. 2023. FC-KBQA: A fine-to-coarse composition framework for knowledge base question answering. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: L… find
  47. Qinggang Zhang, Junnan Dong, Hao Chen, Daochen Zha, Zailiang Yu, and Xiao Huang. 2024. Knowgpt: Knowledge graph based prompting for large language models. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver… find
  48. Zhiqiang Zhang, Liqiang Wen, and Wen Zhao. 2025. Rule-kbqa: Rule-guided reasoning for complex knowledge base question answering with large language models. In Proceedings of the 31st International Conference on Computational Linguistics, COLING 2025, Abu Dhabi, UAE, January 19-24, 2025, pages 8399–8… find
  49. Ruilin Zhao, Feng Zhao, and Hong Zhang. 2025. Correcting on graph: Faithful semantic parsing over knowledge graphs with large language models. In Findings of the Association for Computational Linguistics, ACL 2025, Vienna, Austria, July 27 - August 1, 2025, pages 5364–5376. Association for Computati… find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/song-2026-interactive-semantic-parsing-reinforcement-learning/