Think-on-Graph 3.0: Efficient and Adaptive LLM Reasoning on Heterogeneous Graphs via Multi-Agent Dual-Evolving Context Retrieval

Xiaojun Wu, Cehao Yang, Xueyuan Lin, Chengjin Xu, Xuhui Jiang, Yuanliang Sun, Hui Xiong, Jia Li, Jian Guo

Abstract

Graph-based Retrieval-Augmented Generation (GraphRAG) has become the important paradigm for enhancing Large Language Models (LLMs) with external knowledge. However, existing approaches are constrained by their reliance on high-quality knowledge graphs: manually built ones are not scalable, while automatically extracted ones are limited by the performance of LLM extractors, especially when using smaller, local-deployed models. To address this, we introduce Think-on-Graph 3.0 (ToG-3), a novel framework featuring a Multi-Agent Context Evolution and Retrieval (MACER) mechanism. Its core contribution is the dynamic construction and iterative refinement of a Chunk-Triplets-Community heterogeneous graph index, powered by a Dual-Evolution process that adaptively evolves both the query and the retrieved sub-graph during reasoning. ToG-3 dynamically builds a targeted graph index tailored to the query, enabling precise evidence retrieval and reasoning even with lightweight LLMs. Extensive experiments demonstrate that ToG-3 outperforms compared baselines on both deep and broad reasoning benchmarks, and ablation studies confirm the efficacy of the components of MACER framework.

Introduction: The Bottleneck of Static Knowledge Graphs

Retrieval-Augmented Generation (RAG) is the standard for grounding Large Language Models (LLMs) in external facts. However, traditional GraphRAG approaches face a significant "quality bottleneck." They typically rely on static Knowledge Graphs (KGs) that are either manually curated—which lacks scalability—or automatically extracted by LLMs.

When using lightweight, open-source models (e.g., 7B or 32B parameter models) for extraction, the resulting graphs are often incomplete, containing missing triplets or poor formatting. This "garbage in, garbage out" problem causes reasoning engines to fail. Furthermore, existing RAG systems often struggle to unify "local" fact-specific queries with "global" broad summarization tasks. ToG-3 addresses these challenges by introducing an adaptive architecture that evolves alongside the reasoning process.

Methodology: The MACER Mechanism

The core of ToG-3 is the Multi-Agent Context Evolution and Retrieval (MACER) mechanism. Unlike single-shot retrieval systems, MACER utilizes an iterative loop of specialized agents to refine both the search parameters and the knowledge base.

1. Heterogeneous Graph Index

ToG-3 constructs a "Chunk-Triplets-Community" index. This structure links raw text (Chunks) to semantic relationships (Triplets) and high-level summaries (Communities). This multi-layered approach allows the system to seamlessly transition between granular facts and broad context.

2. Dual-Evolution Process

The framework's primary innovation is Dual-Evolution, which consists of:

  • Evolving Query: A "Reflector" agent evaluates if current evidence is sufficient. If not, it decomposes the user's query into more specific, actionable sub-queries.
  • Evolving Sub-Graph: A "Constructor" agent refines the retrieved graph in real-time, adding missing links or removing noise specifically relevant to the new sub-queries.
The MACER loop: Dynamic evolution of queries and sub-graphs for adaptive reasoning.

3. The Iterative Loop

The process follows a structured path: Retriever → Reranker → Responser → Reflector. This loop continues until the Reflector determines that the gathered evidence is sufficient to answer the query or a predefined iteration limit is reached.

Experimental Evaluation

ToG-3 was evaluated against two categories of challenges:

  • Deep Reasoning: Tasks requiring multi-hop connections across documents (HotpotQA, 2WikiMultiHopQA, and Musique).
  • Broad Reasoning: Tasks requiring large-scale context understanding (UltraDomain subsets: Computer Science, Agriculture, Legal, and Mix).

Results and Discussion

Superior Accuracy and Reasoning

ToG-3 consistently outperformed state-of-the-art baselines, including HippoRAG-2 and LightRAG. On deep reasoning benchmarks, it achieved an average Exact Match (EM) of 0.474 and an F1 score of 0.345. These results demonstrate that the dynamic refinement of the graph compensates for initial extraction errors common in smaller models.

Quantitative comparison of ToG-3 (Ours) against state-of-the-art RAG frameworks.

Efficiency and Win Rates

In broad reasoning tasks, ToG-3 showed a win rate of up to 75% over NaiveRAG when evaluated by a judge LLM. Notably, ToG-3 is more token-efficient than standard GraphRAG, saving approximately 60% in construction tokens. This is because the system does not attempt to build an exhaustive global graph upfront; instead, it builds a "sufficient" graph tailored to the specific query.

Ablation Insights

Ablation studies highlighted that the "Evolving Query" mechanism is the most critical component. Removing this feature led to a performance drop of 12-16%, confirming that query decomposition is essential for navigating complex knowledge structures.

Conclusion

ToG-3 demonstrates that the quality of a knowledge graph should not be a static constraint. By allowing the graph structure to evolve in response to an LLM's internal reasoning, ToG-3 enables smaller, locally-deployed models to achieve performance levels previously reserved for massive proprietary systems. While the iterative nature of MACER introduces a 2-3x latency increase compared to baseline RAG, the gains in accuracy and token efficiency during construction make it a powerful solution for accuracy-critical applications. Future work will focus on model distillation and context pruning to reduce latency and VRAM requirements.

Summary updated

Abstract

Graph-based Retrieval-Augmented Generation (GraphRAG) has become the important paradigm for enhancing Large Language Models (LLMs) with external knowledge. However, existing approaches are constrained by their reliance on high-quality knowledge graphs: manually built ones are not scalable, while automatically extracted ones are limited by the performance of LLM extractors, especially when using smaller, local-deployed models. To address this, we introduce Think-on-Graph 3.0 (ToG-3), a novel framework featuring a Multi-Agent Context Evolution and Retrieval (MACER) mechanism. Its core contribution is the dynamic construction and iterative refinement of a Chunk-Triplets-Community heterogeneous graph index, powered by a Dual-Evolution process that adaptively evolves both the query and the retrieved sub-graph during reasoning. ToG-3 dynamically builds a targeted graph index tailored to the query, enabling precise evidence retrieval and reasoning even with lightweight LLMs. Extensive experiments demonstrate that ToG-3 outperforms compared baselines on both deep and broad reasoning benchmarks, and ablation studies confirm the efficacy of the components of MACER framework. The source code are available in https://github.com/DataArcTech/ToG-3.
BibTeX
@misc{wu2025think,
  author = {Xiaojun Wu and Cehao Yang and Xueyuan Lin and Chengjin Xu and Xuhui Jiang and Yuanliang Sun and Hui Xiong and Jia Li and Jian Guo},
  title = {{Think-on-Graph 3.0: Efficient and Adaptive LLM Reasoning on Heterogeneous Graphs via Multi-Agent Dual-Evolving Context Retrieval}},
  year = {2025},
  eprint = {2509.21710},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2509.21710},
}
Figure