Fast Think-on-Graph: Wider, Deeper and Faster Reasoning of Large Language Model on Knowledge Graph

Xujian Liang, Zhaoquan Gu

Introduction: The "Goldilocks" Problem in Graph RAG

Standard Retrieval-Augmented Generation (RAG) has become a cornerstone for reducing hallucinations in Large Language Models (LLMs). However, "Naive RAG" often falters when faced with complex, multi-hop queries that require synthesizing information across disparate sources. Graph-based RAG (GRAG) was introduced to address this by utilizing Knowledge Graphs (KGs) to provide structured context.

Despite their promise, existing GRAG methods face a significant "Goldilocks" problem. Shallow methods (n-w GRAG) expand search breadth but fail when answers are many hops away. Conversely, deep methods (n-d GRAG) follow long chains of individual nodes, which is computationally expensive, slow, and prone to losing context in dense graph structures. FastToG (Fast Think-on-Graph) is proposed as a solution that is both wide and deep (n-w n-d) without the associated complexity explosion.

Comparison of GraphRAG paradigms showing the evolution from node-based to community-based reasoning.

The FastToG Framework: Reasoning Community-by-Community

The core innovation of FastToG is shifting the fundamental unit of reasoning from individual nodes to communities—densely interconnected groups of nodes. This approach drastically shortens the "distance" between a query and its answer; a path requiring 5-6 hops node-by-node might be traversed in just 2 steps community-by-community.

Methodology Overview

The FastToG pipeline consists of four primary stages designed to optimize both accuracy and efficiency:

  1. Local Community Search (LCS): Rather than partitioning a massive global KG, FastToG retrieves a local subgraph around query entities and detects communities dynamically.
  2. Two-Stage Community Pruning: To maintain focus, the system employs a "coarse-to-fine" approach. First, Modularity-based Coarse Pruning uses structural graph theory to filter out weak communities. Second, LLM-based Fine Pruning prompts the model to select the most semantically relevant clusters.
  3. Community-to-Text (C2T): To bridge the gap between graph structures and LLMs, the framework uses either rule-based Triple2Text or a fine-tuned Graph2Text model to translate clusters into natural language summaries.
  4. Reasoning Chain: The LLM "thinks" by jumping across these macro-nodes, effectively navigating complex multi-hop paths in single steps.
The four-stage FastToG pipeline: Community Detection, Coarse-pruning, Fine-pruning, and Reasoning.

Experimental Results and Key Insights

The researchers evaluated FastToG across six diverse datasets, including Multi-hop KBQA (CWQ, WebQSP), Slot Filling (ZSRE, TREx), and Common-sense Reasoning (Creak), using state-of-the-art models like GPT-4o-mini and Llama-3-70b.

Performance Gains

FastToG consistently outperformed previous state-of-the-art methods. Notably, using Llama-3-70b, it achieved a 5.9% accuracy improvement on the WebQSP dataset. The two-stage pruning proved essential, as modularity-based filtering consistently outperformed random sampling, ensuring the LLM's attention was reserved for the most promising data clusters.

Efficiency and Explainability

Beyond accuracy, FastToG significantly reduced reasoning depth. On the CWQ dataset, the average reasoning depth dropped from ~2.7 steps to ~1.8 steps, leading to fewer API calls and faster response times. Furthermore, visualizing the reasoning process as a sequence of communities (e.g., "Central America" → "El Salvador" → "Spanish language") provides a more interpretable chain of thought than a fragmented list of individual triples.

Limitations and Future Directions

While highly effective, the authors identified areas for further development. The Graph2Text module occasionally introduced hallucinations during summarization, sometimes performing slightly worse than the simpler Triple2Text method. Future work will explore incorporating semantic meaning directly into the community detection process and developing hierarchical reasoning models to allow LLMs to zoom in and out of data at varying granularities.

Summary updated

Abstract

Graph Retrieval Augmented Generation (GRAG) is a novel paradigm that takes the naive RAG system a step further by integrating graph information, such as knowledge graph (KGs), into large-scale language models (LLMs) to mitigate hallucination. However, existing GRAG still encounter limitations: 1) simple paradigms usually fail with the complex problems due to the narrow and shallow correlations capture from KGs 2) methods of strong coupling with KGs tend to be high computation cost and time consuming if the graph is dense. In this paper, we propose the Fast Think-on-Graph (FastToG), an innovative paradigm for enabling LLMs to think ``community by community" within KGs. To do this, FastToG employs community detection for deeper correlation capture and two stages community pruning - coarse and fine pruning for faster retrieval. Furthermore, we also develop two Community-to-Text methods to convert the graph structure of communities into textual form for better understanding by LLMs. Experimental results demonstrate the effectiveness of FastToG, showcasing higher accuracy, faster reasoning, and better explainability compared to the previous works.
BibTeX
@inproceedings{liang2025fast,
  author = {Xujian Liang and Zhaoquan Gu},
  title = {{Fast Think-on-Graph: Wider, Deeper and Faster Reasoning of Large Language Model on Knowledge Graph}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i23.34635},
}
Figure