# Reasoning by Exploration: A Unified Approach to Retrieval and Generation over Graphs

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

## Key facts

- Cited by 6 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 45 of its 76 references that are in the map.
- First posted on arXiv 8 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, 30 of 45)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Retrieval-Augmented Generation for Large Language Models: A Survey](https://mlsanity.com/paper/2312.10997/) (2023)
- [Large Language Models Are Not Robust Multiple Choice Selectors](https://mlsanity.com/paper/2309.03882/) (2023)
- [Stop Overthinking: A Survey on Efficient Reasoning for Large Language Models](https://mlsanity.com/paper/2503.16419/) (2025)
- [The Web as a Knowledge-base for Answering Complex Questions](https://mlsanity.com/paper/1803.06643/) (2018)
- [QA-GNN: Reasoning with Language Models and Knowledge Graphs for Question Answering](https://mlsanity.com/paper/2104.06378/) (2021)
- [Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning](https://mlsanity.com/paper/2310.01061/) (2023)
- [Graph Retrieval-Augmented Generation: A Survey](https://mlsanity.com/paper/2408.08921/) (2024)
- [Towards Large Reasoning Models: A Survey of Reinforced Reasoning with Large Language Models](https://mlsanity.com/paper/2501.09686/) (2025)
- [Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph](https://mlsanity.com/paper/2307.07697/) (2023)
- [Key-Value Memory Networks for Directly Reading Documents](https://mlsanity.com/paper/1606.03126/) (2016)
- [PullNet: Open Domain Question Answering with Iterative Retrieval on Knowledge Bases and Text](https://mlsanity.com/paper/1904.09537/) (2019)
- [Retrieval-Augmented Generation with Graphs (GraphRAG)](https://mlsanity.com/paper/2501.00309/) (2024)
- [GreaseLM: Graph REASoning Enhanced Language Models for Question Answering](https://mlsanity.com/paper/2201.08860/) (2022)
- [Open Domain Question Answering Using Early Fusion of Knowledge Bases and Text](https://mlsanity.com/paper/1809.00782/) (2018)
- [GNN-RAG: Graph Neural Retrieval for Large Language Model Reasoning](https://mlsanity.com/paper/2405.20139/) (2024)
- [Scalable Multi-Hop Relational Reasoning for Knowledge-Aware Question Answering](https://mlsanity.com/paper/2005.00646/) (2020)
- [UniKGQA: Unified Retrieval and Reasoning for Solving Multi-hop Question Answering Over Knowledge Graph](https://mlsanity.com/paper/2212.00959/) (2022)
- [Knowledge-Driven CoT: Exploring Faithful Reasoning in LLMs for Knowledge-intensive Question Answering](https://mlsanity.com/paper/2308.13259/) (2023)
- [Subgraph Retrieval Enhanced Model for Multi-hop Knowledge Base Question Answering](https://mlsanity.com/paper/2202.13296/) (2022)
- [KG-Agent: An Efficient Autonomous Agent Framework for Complex Reasoning over Knowledge Graph](https://mlsanity.com/paper/2402.11163/) (2024)
- [Simple Is Effective: The Roles of Graphs and Large Language Models in Knowledge-Graph-Based Retrieval-Augmented Generation](https://mlsanity.com/paper/2410.20724/) (2024)
- [MindMap: Knowledge Graph Prompting Sparks Graph of Thoughts in Large Language Models](https://mlsanity.com/paper/2308.09729/) (2023)
- [Alice in Wonderland: Simple Tasks Showing Complete Reasoning Breakdown in State-Of-the-Art Large Language Models](https://mlsanity.com/paper/2406.02061/) (2024)
- [Retrieve-Rewrite-Answer: A KG-to-Text Enhanced LLMs Framework for Knowledge Graph Question Answering](https://mlsanity.com/paper/2309.11206/) (2023)
- [KnowAgent: Knowledge-Augmented Planning for LLM-Based Agents](https://mlsanity.com/paper/2403.03101/) (2024)
- [KG-RAG: Bridging the Gap Between Knowledge and Creativity](https://mlsanity.com/paper/2405.12035/) (2024)

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

- [RL-Index: Reinforcement Learning for Retrieval Index Reasoning](https://mlsanity.com/paper/2606.16316/) (2026)
- [DOTRAG: Retrieval-Time Reasoning Along Paths](https://mlsanity.com/paper/2605.18760/) (2026)
- [From Flat to Structural: Enhancing Automated Short Answer Grading with GraphRAG](https://mlsanity.com/paper/2603.19276/) (2026)
- [Why Retrieval-Augmented Generation Fails: A Graph Perspective](https://mlsanity.com/paper/2605.14192/) (2026)
- [OCCAM: Open-set Causal Concept explAnation and Ontology induction for black-box vision Models](https://mlsanity.com/paper/2605.18481/) (2026)
- [Co-adaptive Rule Routing and Constraining for Structured Knowledge Retrieval](https://mlsanity.com/paper/2610.14465/) (2026)

## Abstract (arXiv)

Reasoning over structured graphs remains a fundamental challenge for Large Language Models (LLMs), particularly when scaling to large graphs. Existing approaches typically follow the retrieval-augmented generation (RAG) paradigm: first retrieving subgraphs relevant to the query and then generating answers conditioned on the retrieved subgraphs. However, such two-phase pipelines often struggle to faithfully incorporate graph structure, since the generation process is ultimately constrained by the quality and completeness of the retrieved subgraph. Although many advanced retrievers have been proposed recently to mitigate this issue, they are usually tailored to the training graphs and generalize poorly to unseen graphs, which limits their practical applicability. In this work, we propose Reasoning by Exploration (RoE), a novel approach that unifies retrieval and generation by framing reasoning over graphs as a process of graph exploration. At each step, the LLM selects candidate nodes and edges to explore, gradually constructing reasoning paths and generating answers along the way. To enable effective exploration, RoE is trained in two stages: supervised fine-tuning (SFT) on gold reasoning paths, followed by reinforcement learning (RL) to enhance exploration effectiveness and generalization. Experiments on benchmark datasets demonstrate that RoE achieves substantial overall improvements over baselines, while also generalizing effectively to unseen graphs.