PaperlayerView exact revision on arXiv

Source-linked AI summary

Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph

Jiashuo Sun, Chengjin Xu, Lumingyuan Tang, Saizhuo Wang, Chen Lin, Yeyun Gong, Lionel M. Ni, Heung-Yeung Shum, Jian Guo

arXiv:2307.07697v6cs.CL

TL;DR

LLMs struggle with hallucination-prone, deep knowledge reasoning, while existing KG integration can leave the LLM outside the graph-reasoning process. The paper proposes the tight-coupling LLM⊗KG paradigm and implements it as ToG, an iterative LLM-guided beam search over KGs. ToG outperforms fine-tuning-based and prompting-based methods without additional training cost and is reported to mitigate hallucination.

  • Problem

    LLMs face limitations on complex knowledge reasoning, including hallucination risks, while loosely coupled LLM⊕KG methods depend heavily on KG completeness and quality.

  • Method

    ToG implements LLM⊗KG by prompting an LLM agent to iteratively explore and prune multiple reasoning paths on a knowledge graph.

  • Results

    ToG outperforms existing fine-tuning-based and prompting-based methods without additional training cost and mitigates LLM hallucination issues.

  • Takeaways & Limitations

    ToG provides a training-free framework that supports deep, traceable, flexible, and efficient LLM reasoning with external knowledge graphs.

  • Takeaways & Limitations

    Comparisons distinguish prompting-based methods from fine-tuning-based methods because evaluated datasets naturally favor trained methods, limiting direct comparability across method classes.

Abstract

from arXiv · show

Although large language models (LLMs) have achieved significant success in various tasks, they often struggle with hallucination problems, especially in scenarios requiring deep and responsible reasoning. These issues could be partially addressed by introducing external knowledge graphs (KG) in LLM reasoning. In this paper, we propose a new LLM-KG integrating paradigm ``$\hbox{LLM}\otimes\hbox{KG}$'' which treats the LLM as an agent to interactively explore related entities and relations on KGs and perform reasoning based on the retrieved knowledge. We further implement this paradigm by introducing a new approach called Think-on-Graph (ToG), in which the LLM agent iteratively executes beam search on KG, discovers the most promising reasoning paths, and returns the most likely reasoning results. We use a number of well-designed experiments to examine and illustrate the following advantages of ToG: 1) compared with LLMs, ToG has better deep reasoning power; 2) ToG has the ability of knowledge traceability and knowledge correctability by leveraging LLMs reasoning and expert feedback; 3) ToG provides a flexible plug-and-play framework for different LLMs, KGs and prompting strategies without any additional training cost; 4) the performance of ToG with small LLM models could exceed large LLM such as GPT-4 in certain scenarios and this reduces the cost of LLM deployment and application. As a training-free method with lower computational cost and better generality, ToG achieves overall SOTA in 6 out of 9 datasets where most previous SOTAs rely on additional training.

1 INTRODUCTION

The paper argues that LLM-only and loosely coupled LLM⊕KG reasoning remain limited for complex knowledge tasks, motivating a tight-coupling LLM⊗KG paradigm implemented by Think-on-Graph (ToG). ToG uses iterative graph exploration and beam search to support deeper, more traceable, flexible, and efficient reasoning.

  • Motivation: LLMs struggle with complex knowledge reasoning, including specialized knowledge, hallucination risks, and keeping knowledge current.The training process is expensive and time-consuming, making knowledge updates difficult.
  • Existing paradigm: LLM⊕KG methods retrieve KG information and augment prompts, but the LLM acts mainly as a translator rather than directly participating in graph reasoning.Their success depends heavily on KG completeness and quality.
  • Proposed paradigm: LLM⊗KG tightly couples LLMs and KGs so they complement each other during each graph-reasoning step.The paper illustrates this with dynamic reasoning that combines KG evidence and the LLM’s inherent knowledge.
  • Think-on-Graph: ToG treats the LLM as an agent that iteratively performs beam search over KGs, retaining promising reasoning paths until they support an answer or reach maximum depth.The LLM judges the paths during the Think step.
  • Reported advantages: ToG is presented as supporting deep, responsible, flexible, and efficient reasoning through multi-hop paths, traceable knowledge, plug-and-play integration, and frequent KG-based updates.The paper also reports that small LLMs can become competitive with large LLMs such as GPT-4 under the framework.

2 METHODS

ToG initializes candidate paths from question entities, expands them through LLM-guided relation and entity exploration, and prunes them with beam search. It then asks the LLM whether the retained paths suffice for answering; ToG-R changes this process to emphasize relation chains while reducing pruning cost.

  • Core framework: ToG uses initialization, exploration, and reasoning phases while maintaining top-N reasoning paths throughout inference.The beam width N controls how many paths are retained.
  • Initialization: Initialization prompts the LLM to extract topic entities from the question and use them to initialize the reasoning paths.The number of extracted topic entities may be smaller than N.
  • Exploration: At each iteration, ToG first explores relations and then uses selected relations to guide entity exploration, extending the current paths by one step.This two-step strategy addresses the complexity of handling many neighboring entities.
  • Pruning: The LLM prunes candidate relations and entities to retain top-N paths, using question relevance and path information to select promising continuations.Candidate neighbors are aggregated and evaluated through LLM prompts rather than scored individually one by one.
  • Reasoning: ToG evaluates whether current paths are sufficient for answering; if so, the LLM generates an answer, otherwise the search continues.The process can stop when the LLM judges the retrieved paths adequate or when the maximum depth is reached.
  • Relation-based variant: ToG-R removes LLM-based entity pruning, reducing cost and reasoning time while emphasizing relation information when intermediate-entity text is missing or unfamiliar.It uses random entity pruning and requires at most ND + D + 1 LLM calls.

3 EXPERIMENTS

Experiments evaluate ToG across diverse reasoning tasks, models, knowledge graphs, prompts, and pruning tools. ToG achieves strong performance, especially on multi-hop reasoning, while exposing trade-offs between effectiveness, flexibility, and computational efficiency.

  • Comparison to Other Methods: ToG with GPT-4 achieves new SOTA performance on 6 of 9 datasets despite being training-free and prompting-based.The datasets include WebQSP, GrailQA, QALD10-en, WebQuestions, Zero-Shot RE, and Creak.
  • Comparison to Other Methods: ToG improves performance by 51.8% on GrailQA and 42.9% on Zero-Shot RE compared with methods without external knowledge.The results highlight the contribution of external knowledge graphs to reasoning performance.
  • Performances with Different Backbone Models: The gain over CoT increases with backbone size, from 18.5% to 23.5% on CWQ and from 11.5% to 15.3% on WebQSP.These comparisons span Llama-2 and GPT-4 backbones.
  • Performances with Different Backbone Models: ToG outperforms CoT with GPT-4 even when using the smaller Llama-2 model, suggesting a lower-cost route for some deployments.The paper identifies vertical scenarios covered by external knowledge graphs as a particularly relevant setting.
  • Ablation Study: Increasing search depth and width improves ToG performance, but gains diminish beyond depth 3 as computational cost rises linearly with depth.The default setting is depth 3 and width 3 because few questions require reasoning depths greater than 3.
  • Ablation Study: Freebase improves CWQ and WebQSP more than Wikidata, while replacing LLM pruning with BM25 or SentenceBERT reduces results by 8.4% and 15.1% on average.Freebase aligns with the construction of both datasets; lightweight pruning reduces LLM calls from 2ND + D + 1 to D + 1.

4 RELATED WORK

Prior work either embeds KG knowledge into LLMs during training or retrieves KG information into textual prompts. The paper distinguishes these approaches from its tighter LLM ⊗KG paradigm, where the LLM explores the KG.

  • Earlier methods embed structured KG knowledge into neural networks during pretraining or fine-tuning.
  • Embedding KG knowledge sacrifices the KG’s explainability in knowledge reasoning.
  • Recent methods retrieve relevant KG information and translate it into textual prompts for LLMs.
  • These retrieval-based methods use a fixed pipeline and belong to the LLM ⊕KG paradigm, unlike ToG’s interactive LLM ⊗KG approach.

5 CONCLUSION

The paper introduces LLM ⊗KG and ToG, a framework in which an LLM participates in KG reasoning through iterative exploration and beam search. The authors report improved performance and reduced hallucination without additional training cost.

  • The paper introduces LLM ⊗KG, a tight-coupling paradigm that uses LLMs as agents participating in KG reasoning.
  • Experimental results report that ToG outperforms fine-tuning-based and prompting-based methods without additional training cost and mitigates LLM hallucination.

B ADDITIONAL ABLATION STUDY AND EXPERIMENT ANALYSIS

The paper conducts additional ablation experiments beyond Section 3.2.3 and analyzes ToG’s experimental results in greater detail.

  • Additional experiments provide an ablation study and detailed analysis of ToG’s experimental results.

B.1 ADDITIONAL ABLATION STUDY

The ablation study examines ToG’s sensitivity to demonstrations and compares its multi-path evidence with naive top-1 beam search. Figure 5 covers exemplar sensitivity, while Figure 6 categorizes erroneous instances.

  • Sensitivity to the Number of Seed Examplars: ToG’s sensitivity analysis compares zero-shot prompting with demonstrations using 1–6 training examples on CWQ and WebQSP.
  • Sensitivity to the Number of Seed Examplars: The few-shot experiments randomly select exemplars from the training set and replicate each setting three times.
  • Difference with Naive Beam Search: Naive beam search uses only the most plausible path, whereas ToG uses the top-N reasoning paths as evidence.
  • Difference with Naive Beam Search: ToG evaluates whether the current highest-plausibility path is sufficient at each depth when testing naive top-1 beam search on CWQ and WebQSP.
  • Figure 6 presents erroneous instances and error categories for IO, CoT, and ToG across CWQ, WebQSP, and GrailQA.
  • Difference with Naive Beam Search: Considering top-N reasoning paths can partially alleviate instability in the final result.

B.2 RESULT ANALYSIS

ToG’s analyses show that explored KG paths provide substantial answer evidence, reduce hallucination and refusal errors, and support reasoning across varying depths. Its paths often overlap only partially with ground-truth paths, indicating that alternative routes can still reach correct answers.

  • Error Analysis: ToG significantly reduces hallucination and refusal errors compared with IO and CoT, with reductions of 50% and 60% on GrailQA.Format errors increase slightly because explored paths lengthen outputs, but the error rate remains below 3%.
  • Evidence of Answers: Around 20% of correctly answered samples rely exclusively on LLM intrinsic knowledge, while about 7% combine intrinsic knowledge with explored paths.Most correct answers derive at least partly from paths explored by ToG.
  • Path Overlap: ToG’s explored paths are identical to golden paths for an average of 30% of correct samples and completely different for an average of 21%.The results indicate that ToG can reach correct answers through approximately new paths in KG space.
  • Reasoning Depth: ToG and ToG-R partially counteract the performance degradation that CoT exhibits as question reasoning depth increases.Reasoning depth is calculated from the number of relations in ground-truth SPARQL queries for CWQ and WebQSP.

B.2.1 EFFICIENCY OF TOG

ToG’s efficiency depends on beam-search width, reasoning depth, and pruning strategy, but several optimizations reduce its LLM-call complexity. Lightweight pruning lowers calls at a potential accuracy cost, while early stopping further reduces typical usage.

  • Pruning Optimizations: Replacing LLM pruning with lightweight models reduces ToG’s complexity from O(ND) to O(D), but can lower accuracy.On WebQSP, replacing ChatGPT with Sentence-BERT for pruning reduces performance from 76.2% to 66.3%.
  • Pruning Optimizations: Unifying prompts allows each entity- or relation-pruning step to use one LLM call instead of N separate calls.This reduces repeated scoring calls within each beam-search iteration.
  • Call Complexity: ToG requires at most 2ND + D + 1 LLM calls per question, while ToG-R requires at most ND + D + 1.Actual calls are often lower because reasoning may stop before the maximum depth.
  • Empirical Usage: Average LLM calls per question range from 8.7 on SimpleQuestion to 14.3 on CWQ.Reported averages also include 11.2 for WebQSP, 10.4 for GrailQA, and 11.4 for QALD10-EN.
  • Beam Search: ToG retains N most-likely candidate reasoning paths and scores neighboring entities and relations through batched prompts during iterative search.The search maintains candidate entity and relation sets while using separate pruning and reasoning calls.

C DATASET

The evaluation spans nine datasets covering multi-hop and single-hop KBQA, open-domain QA, slot filling, and fact-checking. ToG achieves strong results across these settings, including new state-of-the-art results and near-state-of-the-art performance on CWQ.

  • Results: ChatGPT-based ToG reaches a new state of the art on QALD10-en, WebQuestions, Zero-Shot RE, and Creak.The paper reports these outcomes in comparisons with fine-tuning- and prompting-based methods.
  • Results: GPT-4-based ToG exceeds fine-tuning-based approaches on almost all multi-hop KBQA datasets and approaches the 69.5% state of the art on CWQ.The evaluation uses dataset-specific result tables and comparisons against prior methods.

D CASE STUDY

Case studies show ToG recovering correct answers through multi-step KG paths, sometimes supplemented by LLM knowledge, while also exposing errors inherited from the knowledge base. Comparisons with IO, CoT, and New Bing illustrate these contrasting behaviors.

  • Successful Retrieval: After two search iterations, ToG links Arthur Miller and Lucian through a reasoning path that reaches the correct answer.The case includes top-3 reasoning paths and normalized scores.
  • Knowledge Combination: For the Renegade example, ToG’s path does not reach the final answer alone, but combined with LLM knowledge it produces Pennsylvania instead of Florida.IO, CoT, and New Bing give the erroneous Florida answer in this example.
  • ToG-R: ToG-R reaches Harvard College after two reasoning hops and, combined with LLM knowledge, returns Massachusetts.New Bing also answers correctly, while IO and CoT lack the needed background knowledge.
  • Alternative Paths: A ToG path reaches the correct answer through fewer hops than the ground-truth path, demonstrating an alternative route through the KG.The case also reveals that the KB answer is outdated: Bright House Field should be Spectrum Field.
  • Limitation: ToG’s reasoning accuracy depends on KG correctness, so incorrect or outdated KG facts can negatively affect its answers.The authors identify this dependence as a constraint and discuss automated knowledge infusion into the KG.

E SPARQL AND PROMPTS

The appendix specifies Freebase and Wikidata query interfaces, helper APIs, pruning and reasoning prompts, and example chain-of-thought and input-output demonstrations. It also shows how retrieved triples, relation chains, and candidate entities are supplied for answering questions.

  • E SPARQL AND PROMPTS: Freebase queries use pre-defined SPARQL templates, whereas Wikidata is queried directly through nine pre-defined service APIs.The SPARQL templates are completed with the appropriate mid and relation.
  • E.1.1 RELATION SEARCH: Freebase relation-search templates retrieve relations outgoing from or incoming to a specified mid.The two templates select ?relation for triples with ns:mid as subject or object.
  • E.1.2 ENTITY SEARCH: Entity-search templates retrieve tail entities connected to a specified mid through a given relation.They cover both ns:mid ns:relation ?tailEntity and ?tailEntity ns:mid ns:relation patterns.
  • E.1.3 CONVERT MID TO LABEL: MID-to-label conversion selects entity names or owl:sameAs targets associated with the specified Freebase mid.The query uses ns:type.object.name and owl:sameAs alternatives.
  • E.2 PRE-DEFINED APIS: The predefined API layer maps labels, mids, property identifiers, and entity identifiers, and retrieves relations, tail entities, and tail values.The listed methods include label2qid, mid2qid, label2pid, pid2label, qid2label, and retrieval functions.
  • E.3.1 RELATION PRUNE: Relation and entity pruning prompts ask the LLM to distribute scores summing to 1 across relevant relations or candidate entities.The prompts provide the topic entity, current relation, relation list, and entity list as inputs.
  • E.3.3 REASONING: Reasoning prompts test whether retrieved triples or explored relation chains suffice, followed by answer generation using those triples and the LLM’s knowledge.The inputs are explored paths or topic entities with relation chains and candidate entities.
  • E.5.1 COT PROMPT: The examples demonstrate chain-of-thought answers and concise input-output answers for questions requiring linked entity and relation information.Examples include answers such as Washington, D.C., Bharoto Bhagyo Bidhata, Jason Allen Alexander, Peter Paul Rubens, and Heroin.
Loading 2307.07697v6…