💬 NLP

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

This paper proposes Explore-on-Graph (EoG), a novel framework that leverages reinforcement learning with path-refined reward modeling to incentivize Large Language Models to autonomously explore diverse reasoning paths on Knowledge Graphs, thereby overcoming the limitations of prior methods and achieving state-of-the-art performance on KGQA benchmarks.

Original authors: Shiqi Yan, Yubo Chen, Ruiqi Zhou, Zhengxi Yao, Shuai Chen, Tianyi Zhang, Shijie Zhang, Wei Qiang Zhang, Yongfeng Huang, Haixin Duan, Yunqi Zhang

Published 2026-02-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Shiqi Yan, Yubo Chen, Ruiqi Zhou, Zhengxi Yao, Shuai Chen, Tianyi Zhang, Shijie Zhang, Wei Qiang Zhang, Yongfeng Huang, Haixin Duan, Yunqi Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

🕵️‍♂️ The Problem: The "Cautious Tourist" vs. The "Adventurous Explorer"

Imagine you have a super-smart robot (a Large Language Model, or LLM) that loves to answer questions. To make sure it doesn't make things up (hallucinate), you give it a giant, detailed map of the world called a Knowledge Graph. This map connects facts like "Apple" → "is a company" → "Steve Jobs" → "lives in California."

The Old Way (Rule-Based & Imitation):
Previous methods were like giving the robot a strict tour guide script.

Rule-Based: "You can only walk on these specific paved paths. If you step on the grass, you get in trouble."
Imitation-Based: "Watch how I walk this path three times, then copy me exactly."

The Flaw: These robots are great at following the script, but if the question requires a path they've never seen before (like a hidden trail through the woods), they get stuck or guess wrong. They are too afraid to leave the beaten path. They lack generalization.

🚀 The Solution: "Explore-on-Graph" (EoG)

The authors propose a new framework called Explore-on-Graph (EoG). Instead of a strict tour guide, they turn the robot into an adventurous explorer who is rewarded for finding the treasure (the correct answer), even if it means taking a weird, unknown route.

They do this in two main stages:

Stage 1: The "School" (Supervised Fine-Tuning)

Before sending the robot into the wild, they put it in a classroom.

What happens: They show the robot thousands of examples of how to solve problems using the map, teaching it how to think step-by-step (Chain of Thought).
The Analogy: This is like teaching a student how to read a map and use a compass before sending them on a solo hike. They learn the basics so they don't get lost immediately.

Stage 2: The "Game" (Reinforcement Learning)

This is the magic part. The robot is now sent out to explore the map on its own, but with a special scoring system.

1. The "Treasure" Reward (Outcome Reward)

How it works: If the robot finds the right answer at the end of its journey, it gets a big gold star. If it gets lost or finds the wrong answer, it gets nothing.
The Analogy: It's like a video game where you only get points for reaching the final boss. This teaches the robot what to aim for.

2. The "Path" Reward (The Secret Sauce)

The Problem: Sometimes, a robot might get lucky and guess the right answer by taking a crazy, nonsensical path. Or, it might wander in circles for hours before finding the answer. This is inefficient.
The Fix: The authors added a second reward: The Path Reward.
How it works: The system checks the robot's journey. Did it walk through the right neighborhoods? Did it connect the right dots logically? Even if the answer is right, if the path was messy or missed key steps, the robot gets a smaller reward.
The Analogy: Imagine a GPS.
- Old Way: "You arrived! Good job." (Even if you drove through a swamp and got your car stuck).
- EoG Way: "You arrived! Good job. But you took a detour through a swamp. Next time, try the scenic route that actually makes sense."
- This encourages the robot to find efficient, logical, and meaningful paths, not just lucky guesses.

🌟 Why This Matters: The "Out-of-Distribution" Superpower

The biggest win for EoG is handling Out-of-Distribution (O.O.D.) problems.

The Scenario: Imagine the robot has only ever seen maps of New York. If you ask it about a hidden alley in Tokyo, a "Rule-Based" robot will freeze because it's never seen that street.
The EoG Robot: Because it was trained to explore and verify paths rather than just memorize routes, it can look at the Tokyo map, figure out the logic, and say, "Hey, even though I've never been here, I can deduce that this street connects to that one based on the rules of the city."

🏆 The Results: Beating the Giants

The paper tested this on five different "mazes" (datasets) and compared it against:

Other smart open-source robots.
The most powerful, expensive "closed-source" robots (like GPT-5 and Gemini 2.5 Pro).

The Result: The EoG robot, built on smaller, open-source models, beat the giants. It solved complex puzzles better than the expensive models, proving that giving a robot the ability to explore is more powerful than just giving it a bigger brain.

🧠 Summary in One Sentence

EoG teaches AI to stop blindly copying old maps and start acting like a brave explorer, rewarding it not just for finding the treasure, but for taking the smartest, most logical path to get there.

tags) and final answers (within` tags) that are logically and factually aligned with the KG.
* The LLM is fine-tuned to generate these structured reasoning traces, establishing a baseline for graph traversal.

Stage 2: Reinforcement Learning (RL) with Path-Refined Rewards

Goal: To incentivize the discovery of novel reasoning paths and improve exploration efficiency.
Algorithm: The authors employ Group Relative Policy Optimization (GRPO).
Reward Mechanism: Unlike standard RL that only rewards the final answer, EoG introduces a Path-Refined Reward system:
1. Outcome Reward ( $R_{outcome}$ ): Based on the correctness of the final answer, measured by the Entity-level F1 score (Precision and Recall against ground-truth entities). This ensures the model finds the right answer.
2. Path Reward ( $R_{path}$ ): An auxiliary signal that evaluates the quality of the reasoning path itself.
  - For datasets without explicit reasoning paths, a "Search-and-Verify" pipeline (BFS + LLM verification) constructs ground-truth paths ( $r_g$ ).
  - The reward calculates the ratio of ground-truth triplets (subject, relation, object) successfully articulated in the model's generated reasoning text.
3. Joint Reward: The final reward is a weighted sum: $R_{joint} = R_{outcome} + \alpha R_{path}$ .
Significance: The path reward guides the model away from futile exploration and encourages semantically meaningful, efficient traversal of the graph, rather than just guessing the answer.

3. Key Contributions

Autonomous Exploration Framework: EoG is the first framework to explicitly incentivize LLMs to explore O.O.D. reasoning patterns on KGs via RL, moving beyond the constraints of imitation learning.
Path-Refined Reward Modeling: The introduction of a path-based reward signal significantly improves the efficiency and semantic meaningfulness of the exploration process, reducing "futile efforts" where the model wanders the graph without logical direction.
State-of-the-Art Performance: The method achieves superior results on five major KGQA benchmarks, outperforming both open-source models and powerful closed-source models (including GPT-5 and Gemini 2.5 Pro).
Robustness to O.O.D.: The framework demonstrates strong generalization capabilities, maintaining high performance on datasets and reasoning patterns not seen during training.

4. Experimental Results

The authors evaluated EoG on five benchmark datasets: WebQSP, CWQ, GrailQA, QALD10-en, and 2WikiMultihopQA.

Performance: EoG (based on Llama-3.1-8B and Qwen2.5-7B) achieved State-of-the-Art (SOTA) results.
- On CWQ, EoG achieved a Hit@1 of 82.6 and F1 of 73.9, surpassing GPT-5 (Hit@1 74.1, F1 67.6) and Gemini 2.5 Pro.
- On WebQSP, EoG achieved a Hit@1 of 92.8, outperforming GPT-5 (86.1).
Ablation Studies:
- Removing the Path Reward significantly degraded performance, confirming its necessity for efficient exploration.
- Removing the RL stage (SFT only) caused a substantial drop in performance, proving that RL is the primary driver of the model's enhanced capabilities.
- Removing SFT resulted in suboptimal performance, indicating SFT is crucial for the "cold start" of the exploration process.
Complex Reasoning: EoG showed particular strength in complex scenarios (e.g., superlative patterns, $\ge$ 3 hops), where it outperformed baselines like GCR and DoG by a wide margin.
Exploration Efficiency: EoG achieved higher Reasoning Coverage (finding more ground-truth triples) while maintaining Exploration Efficiency comparable to SFT baselines, proving it finds correct paths without excessive wasted search.

5. Significance

Generalization: EoG addresses a critical bottleneck in KGQA: the inability of current models to handle reasoning patterns outside their training distribution. By learning to explore rather than just imitate, the model becomes more robust in real-world scenarios where data distributions shift.
Efficiency: The path-refined reward mechanism demonstrates that incorporating structural feedback (path correctness) alongside outcome feedback (answer correctness) leads to more efficient learning and reasoning.
Cost-Effectiveness: Despite using RL, the framework is computationally efficient. The authors report that achieving SOTA performance required relatively few training steps (e.g., 36 steps for WebQSP) and moderate GPU hours, making it a practical approach for enhancing open-source LLMs to compete with closed-source giants.

In conclusion, Explore-on-Graph represents a paradigm shift from static, rule-bound reasoning to dynamic, autonomous exploration, significantly advancing the state of the art in Knowledge Graph Question Answering.