# GraphWalker: Agentic Knowledge Graph Question Answering via Synthetic Trajectory Curriculum

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

## Key facts

- Cited by 6 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 25 of its 43 references that are in the map.
- First posted on arXiv 30 Mar 2026.

## 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, 25 of 25)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [GPT-4o System Card](https://mlsanity.com/paper/2410.21276/) (2024)
- [Language Models as Knowledge Bases?](https://mlsanity.com/paper/1909.01066/) (2019)
- [LlamaFactory: Unified Efficient Fine-Tuning of 100+ Language Models](https://mlsanity.com/paper/2403.13372/) (2024)
- [M3-Embedding: Multi-Linguality, Multi-Functionality, Multi-Granularity Text Embeddings Through Self-Knowledge Distillation](https://mlsanity.com/paper/2402.03216/) (2024)
- [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)
- [Chain-of-Knowledge: Grounding Large Language Models via Dynamic Knowledge Adapting over Heterogeneous Sources](https://mlsanity.com/paper/2305.13269/) (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)
- [Few-shot In-context Learning for Knowledge Base Question Answering](https://mlsanity.com/paper/2305.01750/) (2023)
- [Think-on-Graph 2.0: Deep and Faithful Large Language Model Reasoning with Knowledge-guided Retrieval Augmented Generation](https://mlsanity.com/paper/2407.10805/) (2024)
- [Generate-on-Graph: Treat LLM as both Agent and KG in Incomplete Knowledge Graph Question Answering](https://mlsanity.com/paper/2404.14741/) (2024)
- [ChatKBQA: A Generate-then-Retrieve Framework for Knowledge Base Question Answering with Fine-tuned Large Language Models](https://mlsanity.com/paper/2310.08975/) (2023)
- [Interactive-KBQA: Multi-Turn Interactions for Knowledge Base Question Answering with Large Language Models](https://mlsanity.com/paper/2402.15131/) (2024)
- [Deliberate Reasoning in Language Models as Structure-Aware Planning with an Accurate World Model](https://mlsanity.com/paper/2410.03136/) (2024)
- [Knowledge-Augmented Language Model Verification](https://mlsanity.com/paper/2310.12836/) (2023)
- [KBQA-o1: Agentic Knowledge Base Question Answering with Monte Carlo Tree Search](https://mlsanity.com/paper/2501.18922/) (2025)
- [Knowledge-Infused Prompting: Assessing and Advancing Clinical Text Data Generation with Large Language Models](https://mlsanity.com/paper/2311.00287/) (2023)
- [Bridging the KB-Text Gap: Leveraging Structured Knowledge-aware Pre-training for KBQA](https://mlsanity.com/paper/2308.14436/) (2023)
- [Efficient and Transferable Agentic Knowledge Graph RAG via Reinforcement Learning](https://mlsanity.com/paper/2509.26383/) (2025)

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

- [RedAct: Redacting Agent Capability Traces for Procedural Skill Protection](https://mlsanity.com/paper/2606.10813/) (2026)
- [Teaching LLMs to See Graphs: Unifying Text and Structural Reasoning](https://mlsanity.com/paper/2605.10247/) (2026)
- [Peak-Then-Collapse and the Four Interface Channels of Knowledge-Graph Tool Use](https://mlsanity.com/paper/2605.26037/) (2026)
- [LongCrafter: Towards Diverse Long-Context Understanding via Evidence-Graph-Guided Instruction Synthesis](https://mlsanity.com/paper/2607.06160/) (2026)
- [Co-Evolving Graph and Text Memory for Training-Free Multi-Hop Question Answering](https://mlsanity.com/paper/2607.23278/) (2026)
- [The Path Matters: Evaluating Small Language Models Beyond Answer Accuracy in KGQA](https://mlsanity.com/paper/2609.27669/) (2026)

## Abstract (arXiv)

Agentic knowledge graph question answering (KGQA) requires an agent to iteratively interact with knowledge graphs (KGs), posing challenges in both training data scarcity and reasoning generalization. Specifically, existing approaches often restrict agent exploration: prompting-based methods lack autonomous navigation training, while current training pipelines usually confine reasoning to predefined trajectories. To this end, this paper proposes GraphWalker, a novel agentic KGQA framework that addresses these challenges through Automated Trajectory Synthesis and Stage-wise Fine-tuning. GraphWalker adopts a two-stage SFT training paradigm: First, the agent is trained on structurally diverse trajectories synthesized from constrained random-walk paths, establishing a broad exploration prior over the KG; Second, the agent is further fine-tuned on a small set of expert trajectories to develop reflection and error recovery capabilities. Extensive experiments demonstrate that our stage-wise SFT paradigm unlocks a higher performance ceiling for a lightweight reinforcement learning (RL) stage, enabling GraphWalker to achieve state-of-the-art performance on CWQ and WebQSP. Additional results on GrailQA and our constructed GraphWalkerBench confirm that GraphWalker enhances generalization to out-of-distribution reasoning paths. The code is publicly available at https://github.com/XuShuwenn/GraphWalker.