# Enhancing Agentic Textual Graph Retrieval with Synthetic Stepwise Supervision

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Web, search, and research agents, one of 16 directions in LLM agents and tool use.
- Builds on 38 of its 58 references that are in the map.
- First posted on arXiv 1 Oct 2025.

## Placed in

- LLM agents and tool use / [Web, search, and research agents](https://mlsanity.com/agents/web-search-and-research-agents/)

## Builds on (most cited first, 30 of 38)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [GPT-4o System Card](https://mlsanity.com/paper/2410.21276/) (2024)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [From Local to Global: A Graph RAG Approach to Query-Focused Summarization](https://mlsanity.com/paper/2404.16130/) (2024)
- [A Survey on Evaluation of Large Language Models](https://mlsanity.com/paper/2307.03109/) (2023)
- [DeepSeek-Coder: When the Large Language Model Meets Programming -- The Rise of Code Intelligence](https://mlsanity.com/paper/2401.14196/) (2024)
- [Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model?](https://mlsanity.com/paper/2504.13837/) (2025)
- [SFT Memorizes, RL Generalizes: A Comparative Study of Foundation Model Post-training](https://mlsanity.com/paper/2501.17161/) (2025)
- [Knowledge Graphs](https://mlsanity.com/paper/2003.02320/) (2020)
- [Process Reinforcement through Implicit Rewards](https://mlsanity.com/paper/2502.01456/) (2025)
- [The Web as a Knowledge-base for Answering Complex Questions](https://mlsanity.com/paper/1803.06643/) (2018)
- [Graph Retrieval-Augmented Generation: A Survey](https://mlsanity.com/paper/2408.08921/) (2024)
- [LightRAG: Simple and Fast Retrieval-Augmented Generation](https://mlsanity.com/paper/2410.05779/) (2024)
- [Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph](https://mlsanity.com/paper/2307.07697/) (2023)
- [GraphGPT: Graph Instruction Tuning for Large Language Models](https://mlsanity.com/paper/2310.13023/) (2023)
- [G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answering](https://mlsanity.com/paper/2402.07630/) (2024)
- [Large Language Models on Graphs: A Comprehensive Survey](https://mlsanity.com/paper/2312.02783/) (2023)
- [LLaGA: Large Language and Graph Assistant](https://mlsanity.com/paper/2402.08170/) (2024)
- [Retrieval-Augmented Generation with Graphs (GraphRAG)](https://mlsanity.com/paper/2501.00309/) (2024)
- [Variational Reasoning for Question Answering with Knowledge Graph](https://mlsanity.com/paper/1709.04071/) (2017)
- [Go for a Walk and Arrive at the Answer: Reasoning Over Paths in Knowledge Bases using Reinforcement Learning](https://mlsanity.com/paper/1711.05851/) (2017)
- [Competitive Programming with Large Reasoning Models](https://mlsanity.com/paper/2502.06807/) (2025)
- [GraphLLM: Boosting Graph Reasoning Ability of Large Language Model](https://mlsanity.com/paper/2310.05845/) (2023)
- [KG-Agent: An Efficient Autonomous Agent Framework for Complex Reasoning over Knowledge Graph](https://mlsanity.com/paper/2402.11163/) (2024)
- [A Survey of Graph Retrieval-Augmented Generation for Customized Large Language Models](https://mlsanity.com/paper/2501.13958/) (2025)
- [Process Reward Models for LLM Agents: Practical Framework and Directions](https://mlsanity.com/paper/2502.10325/) (2025)
- [SPA-RL: Reinforcing LLM Agents via Stepwise Progress Attribution](https://mlsanity.com/paper/2505.20732/) (2025)
- [R1-Reward: Training Multimodal Reward Model Through Stable Reinforcement Learning](https://mlsanity.com/paper/2505.02835/) (2025)

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

- [Integrating Graphs, Large Language Models, and Agents: Reasoning and Retrieval](https://mlsanity.com/paper/2604.15951/) (2026)

## Abstract (arXiv)

Integrating textual graphs into Large Language Models (LLMs) is promising for complex graph-based QA. However, a key bottleneck is retrieving informative yet compact subgraphs that fit the LLM context. Existing retrievers often struggle, relying either on shallow embedding similarity or costly interactive policies that require excessive supervision. To address these challenges, we introduce an agentic textual graph reasoning framework featuring an LLM-based retriever trained with synthetic stepwise supervision. Rather than relying on final answer rewards which often yield sparse and unstable signals, we optimize the retriever by evaluating each step against offline-extracted golden subgraphs. Our approach distills golden subgraphs via a specialized data synthesis pipeline to formulate dense rewards, facilitating a two-stage training scheme that effectively learns the interactive graph exploration policy. Based on extensive experiments on three common datasets in comparison with seven strong baselines, our approach achieves an average improvement of 15.6% in accuracy and 17.2% in F1 score. The advantage is even higher in more complicated multi-hop reasoning tasks.