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 GuoSubmission to ICLR 2026 · Withdrawn

TL;DR

Existing Graph-based Retrieval-Augmented Generation (GraphRAG) systems rely on static, one-shot graph indexing that suffers when using smaller, locally deployed LLMs prone to extraction errors. Think-on-Graph 3.0 (ToG-3) introduces a multi-agent framework where the query and the knowledge subgraph co-evolve iteratively during inference, allowing even lightweight open-source models to achieve state-of-the-art multi-hop reasoning.

What Problem Does This Paper Address?

Graph-based RAG improves factual reasoning by grounding LLM generation in structured knowledge rather than raw vector chunks alone. However, current systems hit a practical trade-off:

  1. Pre-built Knowledge Graphs (KGs) (used in ToG-1 and ToG-2) are expensive to curate and rare in private enterprise domains.
  2. Corpus-extracted graphs (like Microsoft's GraphRAG or LightRAG) construct a static graph in a single offline pass. When run on resource-constrained, local open-source models (e.g., Qwen-32B), extraction error rates are high—exhibiting 22–26% JSON parsing failures and widespread missing relations.

Because static indexing cannot anticipate the exact reasoning path of an incoming multi-hop question, these errors propagate directly into generation failures.

Methods

ToG-3 introduces the Multi-Agent Context Evolution and Retrieval (MACER) framework paired with a Chunk–Triplet–Community heterogeneous graph:

  • Heterogeneous Graph Index: Unifies text chunks, extracted open-domain triplets $(s, p, o)$, and hierarchical community cluster summaries (derived via Leiden clustering) into a single 1024-dimensional vector space using a frozen encoder (jina-embeddings-v3).
  • The MACER Process (Episodic MDP): Rather than retrieving from a frozen graph once, ToG-3 runs an iterative loop over four specialized agents:
  • Retriever Agent: Performs initial hybrid vector-graph retrieval.
  • Response Agent: Drafts an intermediate or final answer based on available evidence.
  • Reflector Agent: Evaluates evidence sufficiency. If context is insufficient (reward $r_k = 0$), it decomposes the query into a new, focused sub-query (Evolving Query).
  • Constructor Agent: Refines, normalizes, and injects missing biographical or relational triples into the working evidence graph (Evolving Subgraph).
  • Theoretical Grounding: The authors cast this iterative process as an episodic Markov Decision Process (MDP) and theoretically frame trajectory history through implicit in-context weight updates, showing sublinear regret and convergence toward a minimal sufficient subgraph.

Datasets

The authors evaluated ToG-3 across two primary categories using the Qwen2.5-32B-Instruct model:

  • Deep Multi-Hop Reasoning:
  • HotpotQA (introductory Wikipedia multi-hop questions)
  • 2WikiMultiHopQA (structured multi-step relational hops)
  • Musique (complex 2–4 hop questions with high compositional difficulty)
  • Broad Reasoning (UltraDomain subsets):
  • Computer Science, Agriculture, Legal, and Mix (college textbooks across humanities and sciences).

Key Insights and Ideas

  • Co-Evolution Beats Static Indexing: Dynamically decomposing queries while refining subgraphs enables lightweight models to repair graph extraction deficiencies at test time. Missing links are resolved on-the-fly once the target entity is identified.
  • Component-Specific Utility: Ablation studies show that dropping Evolving Query causes the largest performance drop (12.6% drop in EM, 17.9% in F1), while removing Subgraph Refinement degrades EM by 6.2%.
  • Depth vs. Breadth Structural Roles: For deep multi-hop QA, chunks and triplets provide nearly all the predictive power (community nodes provide marginal gains). Conversely, community nodes proved essential for broad domain synthesis and summarization tasks.
  • Model Scaling Impact: LLM reasoning capability matters far more than embedding scale: upgrading from Qwen2.5-14B to Qwen2.5-72B yielded a 16.4% jump in EM, whereas moving from a 0.6B to a 4B embedding model yielded only a 1.6% gain.

Key Results

  • Deep Reasoning Benchmarks: ToG-3 achieved the highest average performance across all deep reasoning benchmarks with 0.453 Exact Match (EM) and 0.312 F1, surpassing the strongest baseline, HippoRAG-2 (0.438 EM / 0.311 F1), and outperforming GraphRAG (0.295 EM / 0.012 F1) and NaiveRAG (0.415 EM / 0.232 F1).
  • Broad Reasoning Win Rates: In pairwise LLM evaluations (evaluated by GPT-4o-mini on Comprehensiveness, Diversity, and Empowerment), ToG-3 achieved an average 72.9% win rate over NaiveRAG (peaking at 88.8% on the Legal corpus) and consistently outperformed LightRAG and GraphRAG.
  • Indexing Efficiency: ToG-3 required 10.13 hours average indexing time, significantly lower than GraphRAG's 13.10 hours, because it extracts fewer, more targeted initial relational structures.

Limitations and Future Work

  • Inference Latency: The iterative multi-agent loop increases inference time by 2–3× relative to single-shot baselines (averaging ~15 seconds per query), making it less ideal for latency-critical applications.
  • Context Length & Memory: Maintaining evolving history traces increases token footprint, requiring larger GPU memory buffers.
  • Hardware & Model Constraints: Experiments were bounded to models $\le$72B parameters and embedding models $\le$4B parameters.
  • Future Work: Planned extensions include multimodal grounding (integrating audio/video), applying MACER to programmatic and clinical decision domains, and exploring non-parametric brain-inspired memory architectures.

Summary updated

Abstract

Retrieval-Augmented Generation (RAG) and Graph-based RAG has become the important paradigm for enhancing Large Language Models (LLMs) with external knowledge. However, existing approaches face a fundamental trade-off. While graph-based methods are inherently dependent on high-quality graph structures, they face significant practical constraints: manually constructed knowledge graphs are prohibitively expensive to scale, while automatically extracted graphs from corpora are limited by the performance of the underlying LLM extractors, especially when using smaller, local-deployed models. This paper presents Think-on-Graph 3.0 (ToG-3), a novel framework that introduces Multi-Agent Context Evolution and Retrieval (MACER) mechanism to overcome these limitations. Our core innovation is the dynamic construction and refinement of a Chunk-Triplets-Community heterogeneous graph index, which pioneeringly incorporates a dual-evolution mechanism of Evolving Query and Evolving Sub-Graph for precise evidence retrieval. This approach addresses a critical limitation of prior Graph-based RAG methods, which typically construct a static graph index in a single pass without adapting to the actual query. A multi-agent system, comprising Constructor, Retriever, Reflector, and Responser agents, collaboratively engages in an iterative process of evidence retrieval, answer generation, sufficiency reflection, and, crucially, evolving query and subgraph. This dual-evolving multi-agent system allows ToG-3 to adaptively build a targeted graph index during reasoning, mitigating the inherent drawbacks of static, one-time graph construction and enabling deep, precise reasoning even with lightweight LLMs. Extensive experiments demonstrate that ToG-3 outperforming compared baselines on both deep and broad reasoning benchmarks,and ablation studies confirm the efficacy of the components of MACER framework.
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},
}

Loading related content...

Figure