GraphScout: Empowering Large Language Models with Intrinsic Exploration Ability for Agentic Graph Reasoning

Yuchen Ying; Weiqi Jiang; Tongya Zheng; Yu Wang; Shunyu Liu; Kaixuan Chen; Mingli Song

cs.AIMar 2, 2026

GraphScout: Empowering Large Language Models with Intrinsic Exploration Ability for Agentic Graph Reasoning

Authors: Yuchen Ying, Weiqi Jiang, Tongya Zheng, Yu Wang, Shunyu Liu, Kaixuan Chen, Mingli Song

Organizations: Zhejiang University, Hangzhou, China · Hangzhou City University, Hangzhou, China · Nanyang Technological University, Singapore, Singapore

Abstract

Knowledge graphs provide structured and reliable information for many real-world applications, motivating increasing interest in combining large language models (LLMs) with graph-based retrieval to improve factual grounding. Recent Graph-based Retrieval-Augmented Generation (GraphRAG) methods therefore introduce iterative interaction between LLMs and knowledge graphs to enhance reasoning capability. However, existing approaches typically depend on manually designed guidance and interact with knowledge graphs through a limited set of predefined tools, which substantially constrains graph exploration. To address these limitations, we propose GraphScout, a training-centric agentic graph reasoning framework equipped with more flexible graph exploration tools. GraphScout enables models to autonomously interact with knowledge graphs to synthesize structured training data which are then used to post-train LLMs, thereby internalizing agentic graph reasoning ability without laborious manual annotation or task curation. Extensive experiments across five knowledge-graph domains show that a small model (e.g., Qwen3-4B) augmented with GraphScout outperforms baseline methods built on leading LLMs (e.g., Qwen-Max) by an average of 16.7% while requiring significantly fewer inference tokens. Moreover, GraphScout exhibits robust cross-domain transfer performance. Our code will be made publicly available~\footnote{https://github.com/Ying-Yuchen/_GraphScout_}.

Figures & tables

Figure 1. Qwen3-4B-Instruct with GraphScout achieves substantial gains over leading LLMs (e.g.,Qwen-Max) with prompting-based GraphRAG baselines in Healthcare dataset.

Figure 2. Overview of GraphScout framework.

	Dataset	Healthcare		Literature		Academic		E-Commerce		Legal
Method	LLM	QwenScore	F1	QwenScore	F1	QwenScore	F1	QwenScore	F1	QwenScore	F1
	GPT-4o	0.137	0.048	0.221	0.064	0.097	0.080	0.110	0.080	0.244	0.110
	GLM-4.6	0.107	0.099	0.179	0.102	0.095	0.110	0.060	0.111	0.222	0.243
	Qwen-Max	0.074	0.065	0.158	0.098	0.112	0.128	0.060	0.105	0.244	0.298
BaseLLM	DeepSeek-Chat	0.104	0.075	0.192	0.111	0.134	0.140	0.095	0.115	0.222	0.265
	GPT-4o	0.074	0.059	0.179	0.116	0.098	0.090	0.200	0.181	0.256	0.232

Table 1. Performance Comparison on GRBENCH Across Baseline Methods and GraphScout. Relative improvement is measured against the strongest baseline on each dataset. On QwenScore, GraphScout achieves a 16.7% average gain.

Figure 3. Cross-Domain Generalization Performance Across Training and Test Domains.

Figure 4. Performance Comparison Across Question Difficulty Levels on GRBENCH using F1-score as the metric. The Healthcare domain contains no hard questions. For the Literature, all methods achieve an F1-score of 0% on hard questions.

	Healthcare		Literature
	QwenScore	F1	QwenScore	F1
GraphScout	0.819	0.855	0.696	0.646
w/o Graph Solver	0.211	0.217	0.210	0.220
w/o $\mathcal{A}_{\mathrm{code}}$	0.107	0.101	0.196	0.148
w/o $r_{\mathrm{clue}}$	0.785	0.812	0.667	0.635
rw Graph Quizzer	0.678	0.705	0.608	0.571

Table 2. Ablation study of GraphScout (“rw” denotes random walk on knowledge graphs).

Figure 5. Behavioral analysis across question difficulty levels.

Figure 6. Average token consumption of different methods.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Method	Hyperparameters
GraphScout	RL Algorithm = GRPO n_resp_per_prompt = 8 Temperature = 1.0 Threshold $\delta$ = 0.4 Optimization Steps = 400 Training samples per dataset = 2000
Backbone	Qwen3-4B-Instruct-2507, Qwen3-8B
GRPO Trainer	Actor learning rate = $1\times 10^{-6}$ clip_ratio = [0.20, 0.28] Initial KL Coefficient = $1\times 10^{-4}$
Batch Sizes	train_batch_size = 16 rollout_batch_size = 16 micro_train_batch_size = 8 micro_rollout_batch_size = 16
Lengths	Prompt Max Length = 4096 Generate Max Length = 8192
Optimizations	bf16, gradient_checkpointing, remove_padding, packing_samples, dynamic_batch_size, flash_attn

Appendix

Table 3. GRPO Training Settings for GraphScout.

Domain	Topic	# Nodes	# Edges	# Temp	# Q
Academic	CS	$\sim$ 8M	$\sim$ 52M	15	150
	Biology	$\sim$ 4M	$\sim$ 39M	14	140
	Chemistry	$\sim$ 4M	$\sim$ 30M	14	140
	Material Science	$\sim$ 3M	$\sim$ 22M	14	140
	Medicine	$\sim$ 6M	$\sim$ 30M	14	140
	Physics	$\sim$ 2M	$\sim$ 33M	14	140

Appendix

Table 4. Dataset Statistics of GRBENCH.

Figure 7. Distribution of the generated dataset in terms of question difficulty levels, question structural patterns, and answer types. All category labels are automatically judged by an LLM. The three pie charts summarize the proportions of different categories across the entire dataset.

Figure 8. Distribution of (a) question token lengths and (b) the number of clue nodes per question in Healthcare dataset.

	Healthcare	Literature	Academic	E-Commerce	Legal
w/o train	63.73%	67.14%	61.48%	61.15%	72.20%
w/ train	3.14%	5.80%	5.45%	6.61%	1.27%

Appendix

Table 5. Proportion of failed tool calls.

Explore similar work

Cognition on Graph: Navigating Massive Knowledge Space via Cognitive Cycles and Bidirectional Graph-Text Synergy
Sep 11, 2026Gengxian Zhou, Jian Xu, Zichen Tang +3Multi-Hop QA Retrieval-Augmented Generation
Beijing University of Posts and Telecommunications · Zhongguancun Academy, Beijing · MAIS, Institute of Automation, Chinese Academy of Sciences +1
AgentGL: Towards Agentic Graph Learning with LLMs via Reinforcement Learning
Apr 7, 2026Yuanfu Sun, Kang Li, Dongzhe Fan +2LLMs for Graph Learning Text-Attributed Graph Learning
New York University Shanghai · New York University · Tsinghua University
RAGU: A Multi-Step GraphRAG Engine with a Compact Domain-Adapted LLM
Jul 13, 2026Mikhail Komarov, Ivan Bondarenko, Stanislav Shtuka +5KG Construction LLM Reasoning with Graphs
1ITMO University · 2Novosibirsk State University · 3Far Eastern Federal University +1

Sep 11, 2026J/K move · Enter open · S save

Cognition on Graph: Navigating Massive Knowledge Space via Cognitive Cycles and Bidirectional Graph-Text Synergy

Gengxian Zhou, Jian Xu, Zichen Tang, Shiming Xiang+2

Beijing University of Posts and Telecommunications · Zhongguancun Academy, Beijing · MAIS, Institute of Automation, Chinese Academy of Sciences+1

Multi-Hop QA Retrieval-Augmented Generation Graph Retrieval-Augmented Generation Agentic RAG Knowledge Graph Question Answering

Open paper AskPDF arXiv

Retrieval-Augmented Generation (RAG) has empowered Large Language Models (LLMs) to tackle knowledge-intensive tasks. However, navigating global, heterogeneous knowledge bases (large-scale knowledge graphs and text corpora) for complex reasoning remains a challenge. Existing methods typically employ reactive, graph-driven exploration strategies, which blindly follow graph topology without adapting to the question context or evolving exploration progress, and lack deep bidirectional synergy between graph and text. To address these limitations, we propose CoG (Cognition on Graph), a cognitive-inspired, training-free framework for adaptive knowledge exploration. Drawing inspiration from human problem-solving, CoG performs a continuous plan-explore-reflect cycle, where it proactively formulates investigation plans, performs dual-source retrieval, and dynamically reflects on progress to adjust strategies. Crucially, it establishes deep bidirectional synergy between structured graph and unstructured text, where entities extracted from text dynamically guide graph exploration to bridge knowledge gaps. Extensive experiments on seven multi-hop QA benchmarks demonstrate that CoG significantly outperforms state-of-the-art methods while achieving superior exploration efficiency. Our code and datasets are available at https://github.com/zhougengxian/CoG.

Abstract

Explore similar work

Cognition on Graph: Navigating Massive Knowledge Space via Cognitive Cycles and Bidirectional Graph-Text Synergy

AgentGL: Towards Agentic Graph Learning with LLMs via Reinforcement Learning

RAGU: A Multi-Step GraphRAG Engine with a Compact Domain-Adapted LLM