Plan then retrieve: reinforcement learning-guided complex reasoning over knowledge graphs

Song, Yanlin, Liu, Ben, Gutiérrez-Basulto, Víctor ORCID: https://orcid.org/0000-0002-6117-5459, Hu, Zhiwei, Xie, Qianqian, Peng, Min, Ananiadou, Sophia and Pan, Jeff Z. 2026. Plan then retrieve: reinforcement learning-guided complex reasoning over knowledge graphs. Presented at: The ACM web conference, Dubai, United Arab Emirates, 13 -17 April 2026. WWW '26: Proceedings of the ACM Web Conference 2026. ACM, pp. 3666-3676. 10.1145/3774904.3792191

PDF - Accepted Post-Print Version Download (5MB)

Abstract

Knowledge Graph Question Answering (KGQA) aims to answer natural language questions by reasoning over structured knowledge graphs (KGs). While large language models (LLMs) have advanced KGQA through their strong reasoning capabilities, existing methods continue to struggle to fully exploit both the rich knowledge encoded in KGs and the reasoning capabilities of LLMs, particularly in complex scenarios. They often assume complete KG coverage and lack mechanisms to judge when external information is needed, and their reasoning remains locally myopic, failing to maintain coherent multi-step planning, leading to reasoning failures even when relevant knowledge exists. We propose Graph-RFT, a novel two-stage reinforcement fine-tuning KGQA framework with a ''plan–KGsearch–and–Websearch–during–think'' paradigm, that enables LLMs to perform autonomous planning and adaptive retrieval scheduling across KG and web sources under incomplete knowledge conditions. Graph-RFT introduces a chain-of-thought (CoT) fine-tuning method with a customized plan–retrieval dataset activates structured reasoning and resolves the GRPO cold-start problem. It then introduces a novel plan–retrieval guided reinforcement learning process integrates explicit planning and retrieval actions with a multi-reward design, enabling coverage-aware retrieval scheduling. It employs a Cartesian-inspired planning module to decompose complex questions into ordered sub-questions, and logical expression to guide tool invocation for globally consistent multi-step reasoning. This reasoning–retrieval process is optimized with a multi-reward combining outcome and retrieval-specific signals, enabling the model to learn when and how to combine KG and web retrieval effectively. Experiments on multiple KGQA benchmarks demonstrate that Graph-RFT achieves superior performance over strong baselines, even with smaller LLM backbones, and substantially improves complex question decomposition, factual coverage, and tool coordination.

Item Type:	Conference or Workshop Item - published (Paper)
Date Type:	Publication
Status:	Published
Schools:	Schools > Computer Science & Informatics
Publisher:	ACM
ISBN:	9798400723070
Date of First Compliant Deposit:	2 February 2026
Last Modified:	12 May 2026 11:00
URI:	https://orca.cardiff.ac.uk/id/eprint/184361

Actions (repository staff only)

Edit Item