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

• URL: http://arxiv.org/abs/2602.21728v1
• Date: Wed, 25 Feb 2026 09:35:18 GMT
• Title: 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, Yongfeng Huang, Haixin Duan, Yunqi Zhang,
• Abstract summary: Explore-on-Graph (EoG) is a framework that encourages Large Language Models to autonomously explore a more diverse reasoning space on Knowledge Graphs.<n>EoG achieves state-of-the-art performance, outperforming open-source and even closed-source LLMs.
• Score: 40.52120101666234
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• RJE: A Retrieval-Judgment-Exploration Framework for Efficient Knowledge Graph Question Answering with LLMs [18.947344953344995]
  Retrieval-Judgment-Exploration (RJE) is a framework that retrieves refined reasoning paths, evaluates their sufficiency, and conditionally explores additional evidence.<n> RJE substantially reduces the number of LLM calls and token usage compared to agent-based methods, yielding significant efficiency improvements.
  arXiv  Detail & Related papers  (2025-09-25T03:56:18Z)
• GRIL: Knowledge Graph Retrieval-Integrated Learning with Large Language Models [59.72897499248909]
  We propose a novel graph retriever trained end-to-end with Large Language Models (LLMs)<n>Within the extracted subgraph, structural knowledge and semantic features are encoded via soft tokens and the verbalized graph, respectively, which are infused into the LLM together.<n>Our approach consistently achieves state-of-the-art performance, validating the strength of joint graph-LLM optimization for complex reasoning tasks.
  arXiv  Detail & Related papers  (2025-09-20T02:38:00Z)
• Reliable Reasoning Path: Distilling Effective Guidance for LLM Reasoning with Knowledge Graphs [14.60537408321632]
  Large language models (LLMs) often struggle with knowledge-intensive tasks due to a lack of background knowledge.<n>We propose the RRP framework to mine the knowledge graph.<n>We also introduce a rethinking module that evaluates and refines reasoning paths according to their significance.
  arXiv  Detail & Related papers  (2025-06-12T09:10:32Z)
• R1-Searcher: Incentivizing the Search Capability in LLMs via Reinforcement Learning [87.30285670315334]
  textbfR1-Searcher is a novel two-stage outcome-based RL approach designed to enhance the search capabilities of Large Language Models.<n>Our framework relies exclusively on RL, without requiring process rewards or distillation for a cold start.<n>Our experiments demonstrate that our method significantly outperforms previous strong RAG methods, even when compared to the closed-source GPT-4o-mini.
  arXiv  Detail & Related papers  (2025-03-07T17:14:44Z)
• Graph-Augmented Reasoning: Evolving Step-by-Step Knowledge Graph Retrieval for LLM Reasoning [55.6623318085391]
  Recent large language model (LLM) reasoning suffers from limited domain knowledge, susceptibility to hallucinations, and constrained reasoning depth.<n>This paper presents the first investigation into integrating step-wise knowledge graph retrieval with step-wise reasoning.<n>We propose KG-RAR, a framework centered on process-oriented knowledge graph construction, a hierarchical retrieval strategy, and a universal post-retrieval processing and reward model.
  arXiv  Detail & Related papers  (2025-03-03T15:20:41Z)
• KARPA: A Training-free Method of Adapting Knowledge Graph as References for Large Language Model's Reasoning Path Aggregation [2.698553758512034]
  Large language models (LLMs) demonstrate exceptional performance across a variety of tasks, yet they are often affected by hallucinations and the timeliness of knowledge.<n>We propose Knowledge graph Assisted Reasoning Path Aggregation (KARPA), a novel framework that harnesses the global planning abilities of LLMs for efficient and accurate KG reasoning.<n>KARPA achieves state-of-the-art performance in KGQA tasks, delivering both high efficiency and accuracy.
  arXiv  Detail & Related papers  (2024-12-30T14:58:46Z)
• GIVE: Structured Reasoning of Large Language Models with Knowledge Graph Inspired Veracity Extrapolation [108.2008975785364]
  Graph Inspired Veracity Extrapolation (GIVE) is a novel reasoning method that merges parametric and non-parametric memories to improve accurate reasoning with minimal external input.<n>GIVE guides the LLM agent to select the most pertinent expert data (observe), engage in query-specific divergent thinking (reflect), and then synthesize this information to produce the final output (speak)
  arXiv  Detail & Related papers  (2024-10-11T03:05:06Z)
• FiDeLiS: Faithful Reasoning in Large Language Model for Knowledge Graph Question Answering [46.41364317172677]
  Large Language Models (LLMs) are often challenged by generating erroneous or hallucinated responses.<n>We propose a unified framework, FiDeLiS, designed to improve the factuality of LLM responses by anchoring answers to verifiable reasoning steps retrieved from Knowledge Graphs.<n>Our method, as a training-free framework, not only improve the performance but also enhance the factuality and interpretability across different benchmarks.
  arXiv  Detail & Related papers  (2024-05-22T17:56:53Z)
• An Enhanced Prompt-Based LLM Reasoning Scheme via Knowledge Graph-Integrated Collaboration [7.3636034708923255]
  This study proposes a collaborative training-free reasoning scheme involving tight cooperation between Knowledge Graph (KG) and Large Language Models (LLMs) Through such a cooperative approach, our scheme achieves more reliable knowledge-based reasoning and facilitates the tracing of the reasoning results.
  arXiv  Detail & Related papers  (2024-02-07T15:56:17Z)
• Mitigating Large Language Model Hallucinations via Autonomous Knowledge Graph-based Retrofitting [51.7049140329611]
  This paper proposes Knowledge Graph-based Retrofitting (KGR) to mitigate factual hallucination during the reasoning process. Experiments show that KGR can significantly improve the performance of LLMs on factual QA benchmarks.
  arXiv  Detail & Related papers  (2023-11-22T11:08:38Z)
• Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning [104.92384929827776]
  Large language models (LLMs) have demonstrated impressive reasoning abilities in complex tasks. They lack up-to-date knowledge and experience hallucinations during reasoning. Knowledge graphs (KGs) offer a reliable source of knowledge for reasoning.
  arXiv  Detail & Related papers  (2023-10-02T10:14:43Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.