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
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
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
-
-
-
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( ↓ )
Comprehensiveness( ↑ )
Relevance( ↑ )
Exploration( ↑ )
CWQ
EoG
1528
91.9
95.3
88.8
EoG w/o path reward
2067
89.8
92.6
85.1
WebQSP
EoG
851
92.7
97.1
78.9
EoG w/o path reward
926
91.9
95.3
74.3
Table 3: Evaluation of the impact of the path reward.
Figure 6
Method
Conjuction
Comparative
Superlative
Composition
1-hop
2-hop
3-hop
≥ 4-hop
Overall
GCR
Hit@1
73.1
66.3
64.4
66.8
79.0
71.9
62.1
47.7
68.2
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
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
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 ( ↓ )
Coverage ( ↑ )
EoGSFT
2.877
0.615
EoGOutcome
3.028
0.689
EoG
2.887
0.723
Table 5: Comparison of exploration efficiency and reasoning coverage on the CWQ test set.
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≤Ans≤4
5≤Ans≤9
Ans≥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.
Metric
CWQ
WebQSP
GrailQA
2WikiMultihopQA
Supervised Fine-Tuning (SFT)
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
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 × 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
λ=0.2
λ=0.4
λ=0.6
λ=0.8
λ=1.0
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
Hit@1
61.5
75.6
-8.4
WebQSP
F1 Score
71.3
80.2
-5.4
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
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
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 ± standard deviation for our method.
Dataset
Metric
GCR
EoG (Ours)
t -value
p -value
(Baseline)
(Mean ± SD)
WebQSP
Hit@1
92.2
92.8 ± 0.28
4.79
0.009
F1
79.1
81.3 ± 0.33
14.91
<0.001
CWQ
Hit@1
75.8
82.6 ± 0.41
37.08
<0.001
F1
61.7
73.9 ± 0.20
136.46
<0.001
GrailQA
Hit@1
88.4
92.1 ± 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 ± 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−λ)Routcome+λRpath , where λ 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 λ=0.2 achieves the optimal balance, yielding the highest F1 score and robust stability compared to the baseline ( λ=0.0 ).
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.
Yuwei Lou, Hao Hu, Yuzhou Jiang +5
State Key Laboratory for Novel Software Technology, Nanjing University, China · Independent Researcher · Chinaunicom Software Nanjing Branch
Large Language Models (LLMs) demonstrate impressive natural language capabilities but often struggle with knowledge-intensive reasoning tasks. Knowledge Base Question Answering (KBQA), which leverages structured Knowledge Graphs (KGs) exemplifies this challenge due to the need for accurate multi-hop reasoning. Existing approaches typically perform sequential reasoning steps guided by predefined pipelines, restricting flexibility and causing error cascades due to isolated reasoning at each step. To address these limitations, we propose KG-Hopper, a novel Reinforcement Learning (RL) framework that empowers compact open LLMs with the ability to perform integrated multi-hop KG reasoning within a single inference round. Rather than reasoning step-by-step, we train a Reasoning LLM that embeds the entire KG traversal and decision process into a unified ``thinking'' stage, enabling global reasoning over cross-step dependencies and dynamic path exploration with backtracking. Experimental results on eight KG reasoning benchmarks show that KG-Hopper, based on a 7B-parameter LLM, consistently outperforms larger multi-step systems (up to 70B) and achieves competitive performance with proprietary models such as GPT-3.5-Turbo and GPT-4o-mini, while remaining compact, open, and data-efficient. The code is publicly available at: https://github.com/Wangshuaiia/KG-Hopper.
Shuai Wang, Yinan Yu
Department of Computer Science and Engineering, Chalmers University of Technology and University of Gothenburg, SE-41296 Gothenburg, Sweden
Knowledge Graphs (KGs) are widely used to mitigate the limitations of Large Language Models (LLMs), such as outdated knowledge and hallucinations. Existing LLM-KG integration frameworks typically rely on predefined operators to retrieve factual knowledge from KGs and inject it into prompts for answer generation. This paradigm faces two critical bottlenecks: 1) Inflexibility: The predefined operators are limited in scope and thus lack sufficient compositional expressiveness to fully capture the complex semantics required by KG questions. 2) Unscalability: Direct injection of factual knowledge into prompts limits scalability in handling large-scale factual knowledge. To address these two bottlenecks, we propose Code-on-Graph (CoG), a programmatic reasoning framework for LLM-KG integration. Specifically, given the factual knowledge retrieved at each reasoning step, CoG first identifies the corresponding KG schemas and represents these schemas as Python classes, which serve as abstract interfaces to the retrieved facts. It then generates executable code grounded in these classes, with the retrieved facts instantiated as objects of the corresponding classes during execution. This design enables flexible code-based reasoning while avoiding the direct injection of large-scale factual knowledge into prompts. Experiments on WebQSP, CWQ, and GrailQA demonstrate that CoG outperforms prior state-of-the-art models by up to 10.5%.
Weiwei Ding, Zixuan Li, Long Bai +7
1Key Laboratory of AI Safety, Institute of Computing Technology, Chinese Academy of Sciences · 2Shandong University · 3Shandong University-Weihai Research Institute of Industrial Technology