# Plan Then Retrieve: Reinforcement Learning-Guided Complex Reasoning over Knowledge Graphs

arXiv: https://arxiv.org/abs/2510.20691 · HTML: https://mlsanity.com/paper/2510.20691/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 25 of its 49 references that are in the map.
- First posted on arXiv 23 Oct 2025.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

## Builds on (most cited first, 25 of 25)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challenge](https://mlsanity.com/paper/1803.05457/) (2018)
- [Qwen2 Technical Report](https://mlsanity.com/paper/2407.10671/) (2024)
- [Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning](https://mlsanity.com/paper/2503.09516/) (2025)
- [Visual-RFT: Visual Reinforcement Fine-Tuning](https://mlsanity.com/paper/2503.01785/) (2025)
- [The Web as a Knowledge-base for Answering Complex Questions](https://mlsanity.com/paper/1803.06643/) (2018)
- [StructGPT: A General Framework for Large Language Model to Reason over Structured Data](https://mlsanity.com/paper/2305.09645/) (2023)
- [Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning](https://mlsanity.com/paper/2310.01061/) (2023)
- [Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph](https://mlsanity.com/paper/2307.07697/) (2023)
- [Chain-of-Knowledge: Grounding Large Language Models via Dynamic Knowledge Adapting over Heterogeneous Sources](https://mlsanity.com/paper/2305.13269/) (2023)
- [Knowledge-Augmented Language Model Prompting for Zero-Shot Knowledge Graph Question Answering](https://mlsanity.com/paper/2306.04136/) (2023)
- [UniKGQA: Unified Retrieval and Reasoning for Solving Multi-hop Question Answering Over Knowledge Graph](https://mlsanity.com/paper/2212.00959/) (2022)
- [KG-Agent: An Efficient Autonomous Agent Framework for Complex Reasoning over Knowledge Graph](https://mlsanity.com/paper/2402.11163/) (2024)
- [Few-shot In-context Learning for Knowledge Base Question Answering](https://mlsanity.com/paper/2305.01750/) (2023)
- [Generate-on-Graph: Treat LLM as both Agent and KG in Incomplete Knowledge Graph Question Answering](https://mlsanity.com/paper/2404.14741/) (2024)
- [Graph-R1: Towards Agentic GraphRAG Framework via End-to-end Reinforcement Learning](https://mlsanity.com/paper/2507.21892/) (2025)
- [ChatKBQA: A Generate-then-Retrieve Framework for Knowledge Base Question Answering with Fine-tuned Large Language Models](https://mlsanity.com/paper/2310.08975/) (2023)
- [Search and Refine During Think: Facilitating Knowledge Refinement for Improved Retrieval-Augmented Reasoning](https://mlsanity.com/paper/2505.11277/) (2025)
- [SimpleQuestions Nearly Solved: A New Upperbound and Baseline Approach](https://mlsanity.com/paper/1804.08798/) (2018)
- [Research Trends for the Interplay between Large Language Models and Knowledge Graphs](https://mlsanity.com/paper/2406.08223/) (2024)
- [DynaSearcher: Dynamic Knowledge Graph Augmented Search Agent via Multi-Reward Reinforcement Learning](https://mlsanity.com/paper/2507.17365/) (2025)
- [Large Language Models for Social Networks: Applications, Challenges, and Solutions](https://mlsanity.com/paper/2401.02575/) (2024)

## Built on by (most cited first, 1 of 1)

- [HyGRL: Adaptive Hybrid Graph Reasoning for Multi-Entity Questions](https://mlsanity.com/paper/2607.19398/) (2026)

## Abstract (arXiv)

Knowledge Graph Question Answering aims to answer natural language questions by reasoning over structured knowledge graphs. While large language models 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 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 subquestions, 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.