A Framework of Knowledge Graph-Enhanced Large Language Model Based on Question Decomposition and Atomic Retrieval

Yading Li, Dandan Song, Changzhi Zhou, Yuhang Tian, Hao Wang, Ziyi Yang, Shuhao ZhangEMNLP 2024 · OpenReview

Abstract

Knowledge graphs (KGs) can provide explainable reasoning for large language models (LLMs), alleviating their hallucination problem. Knowledge graph question answering (KGQA) is a typical benchmark to evaluate the methods enhancing LLMs with KG. Previous methods on KG-enhanced LLM for KGQA either enhance LLMs with KG retrieval in a single round or perform multi-hop KG reasoning in multiple rounds with LLMs. Both of them conduct retrieving and reasoning based solely on the whole original question, without any processing to the question. To tackle this limitation, we propose a framework of KG-enhanced LLM based on question decomposition and atomic retrieval, called KELDaR. We introduce question decomposition tree as the framework for LLM reasoning. This approach extracts the implicit information of reasoning steps within complex questions, serving as a guide to facilitate atomic retrieval on KG targeting the atomic-level simple questions at leaves of the tree. Additionally, we design strategies for atomic retrieval, which extract and retrieve question-relevant KG subgraphs to assist the few-shot LLM in answering atomic-level questions. Experiments on KGQA datasets demonstrate that our framework outperforms existing reasoning-based baselines. And in a low-cost setting without additional training or fine-tuning, our framework achieves competitive or superior results compared to most existing training-based baselines.

Introduction

Large Language Models (LLMs) are notorious for "hallucinating"—generating facts that sound plausible but are entirely made up. Integrating Knowledge Graphs (KGs) is a popular solution, as KGs provide a structured, verifiable source of truth. However, existing KG-enhanced methods usually fall into two traps: "monolithic retrieval," where they grab a bunch of facts based on the original complex question and dump them into the LLM, or multi-hop reasoning that lacks focus by looking at the entire original question at every step.

The KELDaR Framework

The authors propose KELDaR, which treats reasoning as a tree-structured process. The framework consists of four main modules designed to break down complex queries into manageable "atomic" steps.

Comparison of KELDaR with traditional Retrieve-then-Answer and Multi-Round interaction methods.
  • Question Complexity Classifier: A few-shot prompted LLM determines if a question is "Simple" (one-step) or "Complex" (multi-step).
  • Complex Question Processor: If a question is complex, the framework decomposes it into a sequence of sub-questions. For example, "Where did the writer of 'She's Everything' graduate?" is split into identifying the writer first, then their college.
  • Simple Question Processor: This handles the "atomic" questions using a Relevant Fact Searcher to query the KG.
  • Atomic Retrieval: Instead of a blind search, KELDaR uses a pruned two-hop strategy. It extracts relations and entities within two hops of the topic entity but prunes them based on relevance to the specific sub-question. This is crucial for handling "Compound Value Types" (CVTs)—intermediate nodes in KGs that represent complex relationships rather than single direct links.

Experimental Evaluation

The framework was evaluated on two gold-standard Knowledge Graph Question Answering (KGQA) benchmarks using Freebase:

  • WebQSP (WebQuestions Semantic Parse): Contains 4,737 QA pairs that are generally simpler and require fewer reasoning steps.
  • CWQ (ComplexWebQuestions): A much harder dataset (34,689 pairs) built by making WebQSP questions more complex through composition, conjunctions, and superlatives.

Key Results

KELDaR demonstrated impressive performance, particularly on complex queries, outperforming existing reasoning-based baselines and rivaling models that require expensive fine-tuning.

Performance comparison of KELDaR against training-based and reasoning-based baselines on WebQSP and CWQ datasets.
  • Superiority over Baselines: On the challenging CWQ dataset, KELDaR-rel (using the relation-based strategy) achieved an Exact Match (EM) score of 53.6%*, significantly outperforming standard Chain-of-Thought (40.2%) and other KG-reasoning frameworks like ToG (29.2%).
  • Competitive with Training-Based Models: Despite being a few-shot, training-free framework, KELDaR's performance on WebQSP (79.4% EM) is competitive with state-of-the-art models that were specifically trained on the dataset, such as DecAF (82.1%).
  • LLM Scaling: When tested with GPT-4, the framework showed even stronger results, proving that as the underlying "reasoner" gets better, the KELDaR framework scales effectively.

Limitations and Future Work

While KELDaR is highly effective, the authors note it still struggles with superlative questions (e.g., "Who is the youngest person to...") which require global comparisons across the KG. Additionally, error propagation remains a risk; if the decomposer fails on the first sub-question, the error cascades. Future work will focus on optimizing the number of LLM calls to reduce latency and improving the handling of global constraints.

Summary updated

Abstract

Knowledge graphs (KGs) can provide explainable reasoning for large language models (LLMs), alleviating their hallucination problem. Knowledge graph question answering (KGQA) is a typical benchmark to evaluate the methods enhancing LLMs with KG. Previous methods on KG-enhanced LLM for KGQA either enhance LLMs with KG retrieval in a single round or perform multi-hop KG reasoning in multiple rounds with LLMs. Both of them conduct retrieving and reasoning based solely on the whole original question, without any processing to the question. To tackle this limitation, we propose a framework of KG-enhanced LLM based on question decomposition and atomic retrieval, called KELDaR. We introduce question decomposition tree as the framework for LLM reasoning. This approach extracts the implicit information of reasoning steps within complex questions, serving as a guide to facilitate atomic retrieval on KG targeting the atomic-level simple questions at leaves of the tree. Additionally, we design strategies for atomic retrieval, which extract and retrieve question-relevant KG subgraphs to assist the few-shot LLM in answering atomic-level questions. Experiments on KGQA datasets demonstrate that our framework outperforms existing reasoning-based baselines. And in a low-cost setting without additional training or fine-tuning, our framework achieves competitive or superior results compared to most existing training-based baselines.
BibTeX
@inproceedings{li2024framework,
  author = {Yading Li and Dandan Song and Changzhi Zhou and Yuhang Tian and Hao Wang and Ziyi Yang and Shuhao Zhang},
  title = {{A Framework of Knowledge Graph-Enhanced Large Language Model Based on Question Decomposition and Atomic Retrieval}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2024},
  url = {https://openreview.net/forum?id=COfbgJI4FL},
}
Figure