Enhancing Large Language Models with Reward-guided Tree Search for Knowledge Graph Question and Answering

• URL: http://arxiv.org/abs/2505.12476v1
• Date: Sun, 18 May 2025 15:52:57 GMT
• Title: Enhancing Large Language Models with Reward-guided Tree Search for Knowledge Graph Question and Answering
• Authors: Xiao Long, Liansheng Zhuang, Chen Shen, Shaotian Yan, Yifei Li, Shafei Wang,
• Abstract summary: Large language models (LLMs) have demonstrated impressive performance in Knowledge Graph Question Answering (KGQA) tasks.<n>This paper proposes a novel and training-free framework for KGQA tasks called Reward-guided Tree Search on Graph (RTSoG)
• Score: 8.449873147110516
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently, large language models (LLMs) have demonstrated impressive performance in Knowledge Graph Question Answering (KGQA) tasks, which aim to find answers based on knowledge graphs (KGs) for natural language questions. Existing LLMs-based KGQA methods typically follow the Graph Retrieval-Augmented Generation (GraphRAG) paradigm, which first retrieves reasoning paths from the large KGs, and then generates the answers based on them. However, these methods emphasize the exploration of new optimal reasoning paths in KGs while ignoring the exploitation of historical reasoning paths, which may lead to sub-optimal reasoning paths. Additionally, the complex semantics contained in questions may lead to the retrieval of inaccurate reasoning paths. To address these issues, this paper proposes a novel and training-free framework for KGQA tasks called Reward-guided Tree Search on Graph (RTSoG). RTSoG decomposes an original question into a series of simpler and well-defined sub-questions to handle the complex semantics. Then, a Self-Critic Monte Carlo Tree Search (SC-MCTS) guided by a reward model is introduced to iteratively retrieve weighted reasoning paths as contextual knowledge. Finally, it stacks the weighted reasoning paths according to their weights to generate the final answers. Extensive experiments on four datasets demonstrate the effectiveness of RTSoG. Notably, it achieves 8.7\% and 7.0\% performance improvement over the state-of-the-art method on the GrailQA and the WebQSP respectively.

Related papers

• BYOKG-RAG: Multi-Strategy Graph Retrieval for Knowledge Graph Question Answering [38.3732958942896]
  BYOKG-RAG is a framework that enhances knowledge graph question answering.<n>It combines Large Language Model (LLM) agents with specialized graph retrieval tools.<n>By retrieving context from different graph tools, BYOKG-RAG offers a more general and robust solution for QA over custom KGs.
  arXiv  Detail & Related papers  (2025-07-05T18:47:14Z)
• GraphRAFT: Retrieval Augmented Fine-Tuning for Knowledge Graphs on Graph Databases [0.0]
  GraphRAFT is a retrieve-and-reason framework that finetunes LLMs to generate provably correct Cypher queries.<n>Our method is the first such solution that can be taken off-the-shelf and used on Knowledge Graphs stored in native graph DBs.
  arXiv  Detail & Related papers  (2025-04-07T20:16:22Z)
• Question-Aware Knowledge Graph Prompting for Enhancing Large Language Models [51.47994645529258]
  We propose Question-Aware Knowledge Graph Prompting (QAP), which incorporates question embeddings into GNN aggregation to dynamically assess KG relevance.<n> Experimental results demonstrate that QAP outperforms state-of-the-art methods across multiple datasets, highlighting its effectiveness.
  arXiv  Detail & Related papers  (2025-03-30T17:09:11Z)
• 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)
• EPERM: An Evidence Path Enhanced Reasoning Model for Knowledge Graph Question and Answering [3.1099372412393524]
  This paper reformulates the KGQA problem as a graphical model and proposes a three-stage framework named the Evidence Path Enhanced Reasoning Model (EPERM) for KGQA.<n>In the first stage, EPERM uses the fine-tuned Large language models to retrieve a subgraph related to the question from the original knowledge graph.<n>In the second stage, EPERM filters out the evidence paths that faithfully support the reasoning of the questions, and score their importance in reasoning.
  arXiv  Detail & Related papers  (2025-02-22T10:05:22Z)
• Ontology-Guided Reverse Thinking Makes Large Language Models Stronger on Knowledge Graph Question Answering [24.821273655754222]
  Ontology-Guided Reverse Thinking (ORT) is a novel framework that constructs reasoning paths from purposes back to conditions.<n>ORT operates in three key phases: (1) using LLM to extract purpose labels and condition labels, (2) constructing label reasoning paths based on the KG ontology, and (3) using the label reasoning paths to guide knowledge retrieval.<n> Experiments on the WebQSP and CWQ datasets show that ORT achieves state-of-the-art performance and significantly enhances the capability of LLMs for KGQA.
  arXiv  Detail & Related papers  (2025-02-17T06:53:15Z)
• Federated Neural Graph Databases [53.03085605769093]
  We propose Federated Neural Graph Database (FedNGDB), a novel framework that enables reasoning over multi-source graph-based data while preserving privacy. Unlike existing methods, FedNGDB can handle complex graph structures and relationships, making it suitable for various downstream tasks.
  arXiv  Detail & Related papers  (2024-02-22T14:57:44Z)
• Open-Set Knowledge-Based Visual Question Answering with Inference Paths [79.55742631375063]
  The purpose of Knowledge-Based Visual Question Answering (KB-VQA) is to provide a correct answer to the question with the aid of external knowledge bases. We propose a new retriever-ranker paradigm of KB-VQA, Graph pATH rankER (GATHER for brevity) Specifically, it contains graph constructing, pruning, and path-level ranking, which not only retrieves accurate answers but also provides inference paths that explain the reasoning process.
  arXiv  Detail & Related papers  (2023-10-12T09:12:50Z)
• Graph Reasoning for Question Answering with Triplet Retrieval [33.454090126152714]
  We propose a simple yet effective method to retrieve the most relevant triplets from knowledge graphs (KGs) Our method can outperform state-of-the-art up to 4.6% absolute accuracy.
  arXiv  Detail & Related papers  (2023-05-30T04:46:28Z)
• Logical Message Passing Networks with One-hop Inference on Atomic Formulas [57.47174363091452]
  We propose a framework for complex query answering that decomposes the Knowledge Graph embeddings from neural set operators. On top of the query graph, we propose the Logical Message Passing Neural Network (LMPNN) that connects the local one-hop inferences on atomic formulas to the global logical reasoning. Our approach yields the new state-of-the-art neural CQA model.
  arXiv  Detail & Related papers  (2023-01-21T02:34:06Z)
• UniKGQA: Unified Retrieval and Reasoning for Solving Multi-hop Question Answering Over Knowledge Graph [89.98762327725112]
  Multi-hop Question Answering over Knowledge Graph(KGQA) aims to find the answer entities that are multiple hops away from the topic entities mentioned in a natural language question. We propose UniKGQA, a novel approach for multi-hop KGQA task, by unifying retrieval and reasoning in both model architecture and parameter learning.
  arXiv  Detail & Related papers  (2022-12-02T04:08:09Z)
• Toward Subgraph-Guided Knowledge Graph Question Generation with Graph Neural Networks [53.58077686470096]
  Knowledge graph (KG) question generation (QG) aims to generate natural language questions from KGs and target answers. In this work, we focus on a more realistic setting where we aim to generate questions from a KG subgraph and target answers.
  arXiv  Detail & Related papers  (2020-04-13T15:43:22Z)

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.