Explore-on-Graph: Incentivizing Autonomous Exploration of Large Language Models on Knowledge Graphs with Path-refined Reward Modeling

Shiqi Yan; Yubo Chen; Ruiqi Zhou; Zhengxi Yao; Shuai Chen; Tianyi Zhang; Shijie Zhang; Wei Qiang Zhang

cs.CLFeb 25, 2026

Explore-on-Graph: Incentivizing Autonomous Exploration of Large Language Models on Knowledge Graphs with Path-refined Reward Modeling

Authors: Shiqi Yan, Yubo Chen, Ruiqi Zhou, Zhengxi Yao, Shuai Chen, Tianyi Zhang, Shijie Zhang, Wei Qiang Zhang, +3 more

Organizations: Zhongguancun Laboratory, Beijing, China · Department of Electronic Engineering, Tsinghua University, Beijing, China · Ant International, Ant Group, Hangzhou, Zhejiang, China · Institute for Network Sciences and Cyberspace, Tsinghua University, Beijing, China

Abstract

The reasoning process of Large Language Models (LLMs) is often plagued by hallucinations and missing facts in question-answering tasks. A promising solution is to ground LLMs' answers in verifiable knowledge sources, such as Knowledge Graphs (KGs). Prevailing KG-enhanced methods typically constrained LLM reasoning either by enforcing rules during generation or by imitating paths from a fixed set of demonstrations. However, they naturally confined the reasoning patterns of LLMs within the scope of prior experience or fine-tuning data, limiting their generalizability to out-of-distribution graph reasoning problems. To tackle this problem, in this paper, we propose Explore-on-Graph (EoG), a novel framework that encourages LLMs to autonomously explore a more diverse reasoning space on KGs. To incentivize exploration and discovery of novel reasoning paths, we propose to introduce reinforcement learning during training, whose reward is the correctness of the reasoning paths' final answers. To enhance the efficiency and meaningfulness of the exploration, we propose to incorporate path information as additional reward signals to refine the exploration process and reduce futile efforts. Extensive experiments on five KGQA benchmark datasets demonstrate that, to the best of our knowledge, our method achieves state-of-the-art performance, outperforming not only open-source but also even closed-source LLMs.

Figures & tables

Figure 1: Examples of (a) rule/imitation-based method and (b) our exploration method. O.O.D. stands for Out-Of-Distribution.

Figure 2: The overall framework of our approach. Red arrows in the knowledge graph stands for the golden reasoning paths of the given question.

Method	Model	WebQSP		CWQ		GrailQA		QALD10-en		2WikiMultihop
Method	Model	Hit@1	F1	Hit@1	F1	Hit@1	F1	Hit@1	F1	Hit@1	F1
KD-CoT ( 2023 )	Llama-2-7B	68.6	52.5	55.7	-	-	-	-	-	-	-
EWEK-QA ( 2024 )	-	71.3	-	52.5	-	60.4	-	-	-	-	-
ToG ( 2023 )	ChatGPT	76.2	-	57.6	-	68.7	-	50.2	-	-	-
ToG ( 2023 )	GPT-4	82.6	-	68.5	-	81.4	-	53.8	-	-	-
RoG ( 2024 )	Llama-2-7B	85.7	70.8	62.6	56.2	-	-	-	-	-	-

Table 1: Performance of EoG and previous state-of-the-art models on the five KGQA test sets. The best scores are in bold. † marks the performance of the closed-source model which uses the same input as our EoG. EoG SFT is the model which is only trained with SFT datasets but not with RL.

	CWQ		WebQSP
Model	Hit@1	F1	Hit@1	F1
EoG	82.6	73.9	92.8	81.3
w/o path reward	81.5	70.8	90.2	77.3
w/o outcome reward	62.7	51.4	65.5	56.2
w/o SFT	70.3	63.1	75.9	65.8
w/o SFT, w/ ICL	70.7	63.8	77.2	66.5

Table 2: Ablation studies of EoG on CWQ and WebQSP datasets.

Dataset	Setting	Average Output Length( $\downarrow$ )	Comprehensiveness( $\uparrow$ )	Relevance( $\uparrow$ )	Exploration( $\uparrow$ )
CWQ	EoG	1528	91.9	95.3	88.8
CWQ	EoG w/o path reward	2067	89.8	92.6	85.1
WebQSP	EoG	851	92.7	97.1	78.9
WebQSP	EoG w/o path reward	926	91.9	95.3	74.3

Table 3: Evaluation of the impact of the path reward.

		Conjuction	Comparative	Superlative	Composition	1-hop	2-hop	3-hop	$\geq$ 4-hop	Overall
GCR	Hit@1	73.1	66.3	64.4	66.8	79.0	71.9	62.1	47.7	68.2
GCR	F1	63.7	57.7	52.6	59.7	66.3	63.0	56.6	45.8	60.3
DoG	Hit@1	72.3	77.8	68.7	75.9	75.1	74.1	69.9	63.3	73.7
DoG	F1	53.3	68.3	45.9	49.2	50.3	53.7	64.5	46.7	53.2
EoG	Hit@1	77.2	85.2	73.4	82.8	83.5	79.1	83.2	76.8	82.6
EoG	F1	70.2	77.2	64.7	76.8	76.2	72.0	78.1	69.6	73.9

Table 4: Performance (F1 scores) comparison on different logical patterns and reasoning depths.

Model	Exploration Efficiency ( $\downarrow$ )	Coverage ( $\uparrow$ )
$\text{EoG}_{\text{SFT}}$	2.877	0.615
$\text{EoG}_{\text{Outcome}}$	3.028	0.689
EoG	2.887	0.723

Table 5: Comparison of exploration efficiency and reasoning coverage on the CWQ test set.

Panel of Figure 5 — Figure 5: Hit@1 comparison and performance ratios across four datasets under out-of-distribution (O.O.D.) settings. The O.O.D.-to-I.I.D. ratio is defined as a model’s performance score on Out-of-Distribution (O.O.D.) data divided by its performance score on Independent and Identically Distributed (I.I.D.) data. Subfigures (c) and (d) show the O.O.D.-to-I.I.D. ratios of the models on the four datasets. 2Wiki refers to the 2WikiMultihop dataset. The Y-axis shows the dataset the model was trained on and the X-axis shows the dataset the model was evaluated on.

Figure 6: An example of question and the corresponding answer from EoG and GCR. Different types of entities are distinguished with different colors.

Appendix figures & tables17 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	Train	Test	$Ans=1$	$2\leq Ans\leq 4$	$5\leq Ans\leq 9$	$Ans\geq 10$
WebQSP	2,826	1,628	51.2%	27.4%	8.3%	12.1%
CWQ	27,639	3,531	70.6%	19.4%	6%	4%

Appendix

Table 6: Statistics of datasets.

Figure 7: The code used to prompt LLMs for evaluating performance on KBQA tasks.

Figure 8: An example of prompting LLMs on CWQ.

Figure 9: The template for constructing Long COT Supervised Fine-tuning datasets.

Figure 10: The template for prompting LLMs to explore during training EoG

Figure 11: The template for prompting GPT-4o-mini to score the reasoning process

Figure 12: The template for prompting LLMs to extract relationship on 2WikiMultiHopQA

Figure 13: Comparison of reasoning pathways between EoG and GCR on Case 1.

Figure 14: Analysis of superlative reasoning patterns.

Supervised Fine-Tuning (SFT)
Metric	CWQ	WebQSP	GrailQA	2WikiMultihopQA
Training Steps	400	300	300	400
Training Time (h)	6.1	4.2	4.5	5.1
Train Batch Size	16	16	16	16
Micro Batch Size	2	2	2	2
Total Instances	3537	2344	4774	3102

Appendix

Table 7: Computational Cost Comparison: SFT vs. RL. Due to difference among tokenizers used by different models, we measured SFT Computational Cost using SFT instances instead of tokens, as we consider instances to be a fairer indicator of the SFT budget.

Dataset	GPT-5		Gemini-2.5-flash		Gemini-2.5-pro
Dataset	T=0.2	T=0.7	T=0.2	T=0.7	T=0.2	T=0.7
WebQSP	77.5	78.1	78.2	78.4	79.8	79.2
CWQ	67.6	67.6	59.3	59.7	65.3	65.7
GrailQA	85.4	85.2	83.8	84.3	84.5	85.1
QALD10-en	50.4	51.3	46.2	46.1	48.3	48.5
2WikiMultihopQA	83.4	82.9	83.1	83.9	82.6	82.9

Appendix

Table 8: Comparison of the performance of different closed-source commercial models on the KGQA datasets under various temperature settings.

Category	Configuration
Hardware	Compute Hardware: 8 $\times$ H100 GPUs
	GPU Memory Utilization: 0.6
	FSDP Offload: Param & Optimizer
Backbone	Rollout Engine: vLLM
	Gradient Checkpointing: True
Training	Optimizer: Adam (implied by standard GRPO setup)

Appendix

Table 9: Detailed configuration of training and testing parameters for the GRPO phase.

Dataset	$\lambda=0.2$		$\lambda=0.4$		$\lambda=0.6$		$\lambda=0.8$		$\lambda=1.0$
Dataset	F1	Hit@1	F1	Hit@1	F1	Hit@1	F1	Hit@1	F1	Hit@1
CWQ	69.7	78.2	68.5	77.3	67.9	77.1	67.1	76.3	67.3	75.9
WebQSP	80.6	89.6	79.4	88.9	80.2	89.3	79.8	89.2	78.9	88.2
GrailQA	90.3	91.8	89.9	91.4	89.6	91.2	90.1	91.3	89.7	91.5
2WikiMultihopQA	84.2	84.8	83.7	84.2	83.5	83.9	83.3	83.7	83.1	83.5

Appendix

Table 10: Performance on Various Datasets Across Different GED Coefficients

Dataset	Metric	EoG (SFT Only)	EoG (SFT + RL)	Improvement (%)
CWQ	F1 Score	55.8	70.7	-4.3
CWQ	Hit@1	61.5	75.6	-8.4
WebQSP	F1 Score	71.3	80.2	-5.4
WebQSP	Hit@1	82.6	87.9	-4.9

Appendix

Table 11: Performance of EoG on the CWQ and WebQSP Datasets, using Qwen3-32B as the teacher model.

Method	Model	WebQSP		CWQ		GrailQA		QALD10-en		2WikiMultihopQA
Method	Model	Hit@1	F1	Hit@1	F1	Hit@1	F1	Hit@1	F1	Hit@1	F1
† Gemini-2.5 Flash	-	91.8	78.2	65.5	59.3	90.3	83.8	56.7	46.2	83.9	83.1
† Gemini-2.5 Pro	-	92.1	79.8	71.9	65.3	91.6	84.5	58.6	48.3	85.1	82.6
† GPT-5	-	86.1	77.5	74.1	67.6	90.5	85.4	59.2	50.4	84.2	83.4
EoG SFT	Qwen2.5-7B	83.9	72.6	68.3	60.3	89.2	87.6	55.6	44.1	82.5	81.9
EoG SFT	Llama-3.1-8B	86.3	74.5	70.5	62.1	91.4	88.2	57.1	48.7	83.1	82.7

Appendix

Table 12: Performance comparison between our EoG framework (Llama-3.1-8B) and state-of-the-art closed-source models. The bottom section highlights the significant improvement of our RL-finetuned model over its SFT model. We report the mean

\pm

standard deviation for our method.

Dataset	Metric	GCR	EoG (Ours)	$t$ -value	$p$ -value
Dataset	Metric	(Baseline)	(Mean $\pm$ SD)	$t$ -value	$p$ -value
WebQSP	Hit@1	92.2	92.8 $\pm$ 0.28	4.79	0.009
WebQSP	F1	79.1	81.3 $\pm$ 0.33	14.91	$<0.001$
CWQ	Hit@1	75.8	82.6 $\pm$ 0.41	37.08	$<0.001$
CWQ	F1	61.7	73.9 $\pm$ 0.20	136.46	$<0.001$
GrailQA	Hit@1	88.4	92.1 $\pm$ 0.30	27.57	$<0.001$

Appendix

Table 13: Statistical comparison between GCR and our EoG framework using a one-sample t-test (

df=4

). The table reports the baseline score, our model’s performance (Mean

\pm

SD), and the calculated

t

-statistics and

p

-values. Results indicate statistically significant improvements across all metrics.

Figure 15: Validation F1 performance on the CWQ dataset with varying Path Reward weights. The total reward is formulated as

R=(1-\lambda)R_{outcome}+\lambda R_{path}

, where

\lambda

denotes the coefficient shown in the legend. The dashed vertical line marks the start of the second training phase at step 75, where the reward shifts from result-only RL to a mixed result-and-path reward. Solid lines and shaded regions represent the mean and standard deviation across 3 random seeds, respectively. The results indicate that

\lambda=0.2

achieves the optimal balance, yielding the highest F1 score and robust stability compared to the baseline (

\lambda=0.0

Explore similar work

RACER: Reinforced Agent Collaboration for Explainable Reasoning on Knowledge Graphs
Aug 29, 2026Yuwei Lou, Hao Hu, Yuzhou Jiang +5LLM Reasoning with Graphs Knowledge Graph Question Answering
State Key Laboratory for Novel Software Technology, Nanjing University, China · Independent Researcher · Chinaunicom Software Nanjing Branch
KG-Hopper: Empowering Compact Open LLMs with Knowledge Graph Reasoning via Reinforcement Learning
Mar 22, 2026Shuai Wang, Yinan YuLLM Reasoning with Graphs Knowledge Graph Question Answering
Department of Computer Science and Engineering, Chalmers University of Technology and University of Gothenburg, SE-41296 Gothenburg, Sweden
Code-on-Graph: Iterative Programmatic Reasoning via Large Language Models on Knowledge Graphs
Jun 2, 2026Weiwei Ding, Zixuan Li, Long Bai +7LLM Grounding LLM Reasoning with Graphs
1Key Laboratory of AI Safety, Institute of Computing Technology, Chinese Academy of Sciences · 2Shandong University · 3Shandong University-Weihai Research Institute of Industrial Technology

Aug 29, 2026J/K move · Enter open · S save

RACER: Reinforced Agent Collaboration for Explainable Reasoning on Knowledge Graphs

Yuwei Lou, Hao Hu, Yuzhou Jiang, Zongfei Zhang+4

State Key Laboratory for Novel Software Technology, Nanjing University, China · Independent Researcher · Chinaunicom Software Nanjing Branch

LLM Reasoning with Graphs Knowledge Graph Question Answering Multi-Agent LLM Systems RL for Language Model Reasoning Knowledge Graphs

Open paper AskPDF arXiv

Large Language Models (LLMs) often suffer from hallucination and struggle with complex reasoning tasks requiring multi-hop domain knowledge. While integrating Knowledge Graphs (KGs) provides a structured and verifiable information source, current KG-enhanced LLM paradigms usually rely on single-agent path extraction and fixed prompting, lacking adaptability and facing huge search spaces. To address these challenges, we propose RACER, a Reinforced Agent Collaboration framework for Explainable Reasoning on knowledge graphs. RACER employs a semantic-aware action pruning and teacher-guided reinforcement learning mechanism to efficiently extract high-quality reasoning pathways from large-scale KGs. Furthermore, to mitigate single-path generation pitfalls, we introduce a cross-task accumulated shared memory graph paired with an attention-driven multi-path knowledge refinement module. Finally, RACER orchestrates these components through a four-role multi-agent collaboration system (GraphAgent, TemplateAgent, AnswerAgent, and CriticAgent) to dynamically refine prompts and evaluate answers. Extensive experiments on CommonsenseQA and OpenBookQA datasets demonstrate that RACER significantly outperforms state-of-the-art KG-enhanced LLM baselines with an average improvement of 5%, offering robust and highly interpretable reasoning capabilities.

Abstract

Explore similar work

RACER: Reinforced Agent Collaboration for Explainable Reasoning on Knowledge Graphs

KG-Hopper: Empowering Compact Open LLMs with Knowledge Graph Reasoning via Reinforcement Learning

Code-on-Graph: Iterative Programmatic Reasoning via Large Language Models on Knowledge Graphs