Research map / Large language models / Retrieval and knowledge

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

ICLR 2024 · Large language models › Retrieval and knowledge · approach: Knowledge graph reasoning with LLMs

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes Think-on-Graph (ToG), a training-free LLM-as-agent beam search over knowledge graphs (plus a relation-only variant ToG-R) that iteratively explores and prunes reasoning paths, evaluated on nine KBQA and knowledge-intensive datasets.

Problem

LLMs hallucinate and struggle with deep, multi-hop, responsible reasoning and outdated knowledge; existing LLM-KG integrations use loosely coupled retrieve-then-prompt pipelines whose success depends on KG completeness.

Approach

Treat the LLM as an agent that tightly couples with the KG (LLM⊗KG): it performs beam search over relations and entities on the graph, pruning candidate paths with LLM scoring at each step, and decides when enough evidence has been gathered to answer; the reasoning paths are explicit and editable for traceability and correction.

Key results

• ToG with GPT-4 reaches 82.6 on WebQSP and 81.4 on GrailQA, setting new SOTA on 6 of 9 datasets.
• Llama-2-70B-Chat with ToG reaches 53.6 on CWQ versus 39.1 for CoT with the same model, and ToG with Llama-2 outperforms CoT with GPT-4 on that dataset in the stated comparison.
• Replacing the LLM pruner with BM25 or SentenceBERT drops WebQSP accuracy from 76.2 to 58.7 and 66.3 respectively.

Measured effects reported in the paper

Surprising findings

• ToG with a small open model (Llama-2-70B) can outperform CoT with GPT-4 on CWQ and WebQSP, suggesting cheaper deployment routes.
• Around 20% of correctly answered samples rely solely on the LLM's internal knowledge rather than explored KG paths.

Limitations

• Performance depends on KG correctness and completeness; outdated or missing triples propagate to wrong answers.
• Higher computational cost than LLM-only prompting, scaling linearly with beam width and depth.
• Lightweight pruners (BM25, SentenceBERT) substantially reduce accuracy relative to LLM pruning.

Experimental setup

Datasets: CWQ WebQSP GrailQA QALD10-en Simple Questions WebQuestions T-REx Zero-Shot RE Creak

Benchmarks: CWQ WebQSP GrailQA QALD10-en Simple Questions WebQuestions T-REx Zero-Shot RE Creak

Metrics: Hits@1 exact match accuracy

Baselines: IO prompt Chain-of-Thought Self-Consistency KD-CoT StructGPT KB-BINDER DeCAF CBR-KBQA

Builds on: chain-of-thought self-consistency beam search on KG

Closest papers by meaning

• Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning (ICLR 2024 · similarity 0.93)
• Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models (ICML 2025 · similarity 0.92)
• LightPROF: A Lightweight Reasoning Framework for Large Language Model on Knowledge Graph (AAAI 2025 · similarity 0.91)
• Debate on Graph: A Flexible and Reliable Reasoning Framework for Large Language Models (AAAI 2025 · similarity 0.91)
• Plan-on-Graph: Self-Correcting Adaptive Planning of Large Language Model on Knowledge Graphs (NeurIPS 2024 · similarity 0.91)
• Think-on-Graph 2.0: Deep and Faithful Large Language Model Reasoning with Knowledge-guided Retrieval Augmented Generation (ICLR 2025 · similarity 0.91)