PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2509.21710v2cs.CL

TL;DR

Graph-based RAG depends on knowledge graphs whose construction can be limited by extractor quality, especially with lightweight models. ToG-3 uses a heterogeneous graph and MACER to evolve both queries and subgraphs during retrieval, and the paper reports state-of-the-art results across multiple challenging benchmarks. Its inference latency and context length are higher than those of baseline methods.

  • Problem

    Graph-based RAG relies on high-quality knowledge graphs, but graph construction can be limited by LLM extraction capability, especially with lightweight models.

    Source: §1 · p. 1, §3.1 · p. 4

  • Method

    ToG-3 combines a Chunk–Triplet–Community graph with MACER, which iteratively evolves queries and subgraphs during retrieval.

    Source: §1 · pp. 1–2

  • Results

    ToG-3 achieves state-of-the-art performance across multiple challenging benchmarks.

    Source: §5 · p. 8

  • Takeaways & Limitations

    The paper presents adaptive retrieval as valuable for overcoming static graph-construction quality constraints and limitations of pre-existing knowledge bases.

    Source: §5 · p. 8

    Experiments use LLMs up to 72B parameters and embedding models up to 4B; inference is typically 2–3× slower than baselines and requires more GPU memory for longer contexts.

    Source: Limitations · p. 8

Abstract

from arXiv · show

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.

1 Introduction

The introduction identifies extraction quality and static indexing as challenges for graph-based RAG, particularly with lightweight models and specialized deployments. ToG-3 proposes a heterogeneous graph and dual-evolving retrieval framework to address these challenges.

1 Introduction

  • Graph-based RAG methods that build graphs from documents depend on accurate entity and relation extraction, a bottleneck for lightweight models.The introduction also notes that these methods often separate local and global questions.Source: §1 · p. 1
  • ToG-3 combines a Chunk–Triplet–Community heterogeneous graph index with a dual-evolution mechanism for queries and subgraphs.The mechanism is presented as a way to refine evidence retrieval iteratively.Source: §1 · pp. 1–2
  • MACER is proposed as a multi-agent framework integrating evolving queries and evolving subgraphs, with claimed gains in retrieval and complex reasoning, especially with lightweight open-source LLMs.Source: §1 · p. 2
  • Contextual integration achieves competitive results across diverse benchmarks.Source: §1 · p. 2

2 Related Work

Related work covers graph-based retrieval, hybrid use of text and knowledge graphs, and iterative or reflective reasoning. ToG-3 is framed as improving the retrieval paradigm underlying such systems.

2.1 Graph-Based Retrieval-Augmented Generation

  • Graph-based RAG builds document-derived entity graphs, while ToG-3 contrasts runtime graph and query co-evolution with static graph retrieval.GraphRAG uses community detection for global sensemaking; LightRAG combines low-level fact retrieval with high-level semantic discovery.Source: §2.1 · p. 2, Figure 2 · p. 3
  • ToG-3 is presented as complementary to end-to-end agentic frameworks and potentially usable as a plug-in to improve their retrieval paradigm.Source: §2.1 · p. 3

2.2 Knowledge Graphs in RAG and Hybrid Approaches

  • Hybrid approaches combine structured knowledge and text or vector retrieval to balance breadth and precision or combine retrieval modalities.The section also describes KG-based systems that retrieve from Wikidata or Freebase and Chain-of-Knowledge, which uses multiple structured sources.Source: §2.2 · p. 3

2.3 Iterative and Reflective Reasoning in LLMs

  • Prior iterative and reflective methods alternate retrieval with generation, interleave reasoning and evidence gathering, or use reflection to guide retrieval and assess outputs.Source: §2.3 · p. 3

3 Methodology

ToG-3 formulates open-domain question answering around accurate, source-faithful answers grounded in a sufficient subgraph. Its heterogeneous index and MACER loop combine multiple evidence types with iterative query and graph refinement.

3 Methodology

  • ToG-3 introduces MACER for open-domain question answering, seeking accurate, source-faithful answers from a minimal sufficient subgraph.Source: §3 · p. 3, §3.1 · p. 4

3.1 Problem Formulation

  • Existing approaches either rely on pre-constructed high-quality knowledge graphs or build static corpus graphs whose quality depends on the extractor LLM.Source: §3.1 · p. 4

3.2.1 Node and Edge Schema

  • The heterogeneous index combines sentence-level chunks, extracted semantic triplets, and community summaries, with edges linking triplets to source chunks and communities to entities.The unified schema supports fine-grained and high-level retrieval in one vector space, addressing the local/global retrieval dichotomy.Source: §3.2.1 · p. 4

3.2.2 Offline Index Construction

  • A single frozen encoder maps all node types into a shared 1024-dimensional dense vector space for efficient cross-type vector search.Source: §3.2.2 · p. 4

3.3 The MACER Process: Multi-Agent Context Evolution and Retrieval

  • MACER iterates retrieval, answer generation, and reflection; when evidence is insufficient, the query and subgraph are refined, and the loop stops on sufficiency or the maximum horizon.The final answer is synthesized from the full trajectory; this refinement is described as specializing an initially weak graph to the query’s reasoning path.Source: §3.3 · pp. 4–5, Figure 3 · p. 5

4 Experiment

Experiments evaluate deep and broad reasoning tasks using benchmark-specific datasets, metrics, and RAG baselines. ToG-3 leads on deep-task averages and broad-task comparisons, while ablations distinguish the contributions of its retrieval components and model capacity.

4.1 Experimental Setup

  • The evaluation covers HotpotQA, 2WikiMultiHopQA, and Musique for deep reasoning, plus four UltraDomain subsets for broad reasoning.Deep tasks use EM and F1; broad tasks use LLM-based comprehensiveness, diversity, and empowerment metrics, with graph-based methods using 1024-token chunks and the same Qwen2.5-32B-Instruct model.Source: §4.1 · pp. 5–6

4.2 Result of Deep Reasonging Benchmark

  • ToG-3 outperforms all competitors across three deep-reasoning benchmarks, achieving the highest average EM (0.474) and F1 (0.345).Table 1 reports EM and F1 on the deep-reasoning datasets.Source: §4.2 · p. 6, Table 1 · p. 7

4.3 Result of Broad Reasoning Tasks

  • ToG-3 outperforms NaiveRAG by 75.0% average win rate across four broad-reasoning datasets and balances diversity and empowerment.The ELO heatmaps show pairwise win probabilities; 20% of samples require one evolving-context iteration, 32% two, and 48% three.Source: §4.3 · pp. 6, 8, Figure 5 · p. 7

4.4 Abalation Study

  • Removing evolving query causes the largest deep-task drops (12.0% EM, 16.5% F1); subgraph refinement removal drops 6.0% EM and 9.0% F1.Community nodes have a smaller deep-task impact but are essential for broad-task coverage and diversity; reranking improves EM by 4.6% and F1 by 10.6%.Source: §4.4 · p. 8

Abalation Study of used foundation model

  • Scaling Qwen2.5-14B to Qwen2.5-72B improves average EM by 15.9%, exceeding the reported gains from larger embedding models.Qwen3-Embed-4B improves average EM by 1.7% over jina-embeddings-v3; the analysis identifies LLM reasoning capacity as the primary complex-task bottleneck.Source: Abalation Study of used foundation model · p. 8

5 Conclusion

ToG-3 combines MACER with a dynamic Chunk-Triplets-Community graph architecture. Experiments report state-of-the-art performance across multiple challenging benchmarks and identify adaptive retrieval and lightweight-LLM compatibility as practical features.

5 Conclusion

  • ToG-3 combines MACER with a dynamic Chunk-Triplets-Community heterogeneous graph architecture.The conclusion presents this combination as addressing limitations in graph-based RAG and approaches dependent on existing knowledge graphs.Source: §5 · p. 8
  • Experiments demonstrate state-of-the-art performance across multiple challenging benchmarks.Source: §5 · p. 8
  • The framework’s adaptive capability addresses static graph-construction quality constraints and limitations of pre-existing knowledge bases.The conclusion also says ToG-3 works with lightweight LLMs, opening possibilities for more deployable AI systems.Source: §5 · p. 8

Limitations

The experiments are bounded by available GPU resources, while ToG-3’s evolving retrieval adds inference latency and increases context-related memory demands.

Limitations

  • Experiments use LLMs up to 72B parameters and embedding models up to 4B parameters, constrained by GPU resources.The paper describes these sizes as practical for most developers and small-to-medium enterprises for local deployment.Source: Limitations · p. 8
  • Inference is typically 2–3× slower than baseline methods, making ToG-3 more suitable for accuracy-critical settings where speed can be sacrificed.Source: Limitations · p. 8
  • Longer context inputs demand larger GPU memory for efficient processing.The paper suggests model distillation, optimized graph traversal, and dynamic context pruning as possible mitigations.Source: Limitations · p. 8

Ethical Considerations

The research uses public benchmark datasets and reports adherence to reproducibility standards and ACL ethical guidelines. It also acknowledges risks from generated content and base-model biases.

Ethical Considerations

Information About Use Of AI Assistants

The author used AI-assisted tools exclusively to refine the manuscript’s text.

Information About Use Of AI Assistants

Appendices

The appendices provide implementation details, ToG-3 algorithms, and dataset descriptions.

Appendices

  • The appendices cover implementation, algorithms, dataset statistics, baselines, evaluation metrics, additional results, resource use, and supplementary examples and prompts.The listed material also includes theoretical support for ToG-3.Source: Appendices · p. 13

A Implementation Details

  • Experiments use 1024-token chunks with 20-token overlap, up to two extracted triplets per chunk, top-five node retrieval, and top-two reranking and answer context.The setup uses Qwen2.5-32B-Instruct, Jina embeddings and reranking, and a Neo4j-based hybrid vector-graph store.Source: A Implementation Details · p. 13

B ToG-3 Algorithms

  • ToG-3 has an index-construction stage for chunks, triplets, and communities, followed by a MACER loop that iteratively refines the query and subgraph.Source: B ToG-3 Algorithms · p. 13

C Dataset Detail

  • The dataset appendix supplies statistics, metadata, licensing information, and descriptions of each dataset’s characteristics and intended use.Source: C Dataset Detail · p. 13

C.1 Deep Reasoning Datasets

The appendices describe deep and broad reasoning datasets and the baseline methods evaluated.

C.1 Deep Reasoning Datasets

  • HotpotQA has about 113K Wikipedia questions requiring two articles; 2WikiMultiHopQA requires reasoning across paragraphs, while Musique has about 25K questions requiring 2–4 hops.HotpotQA also includes distractor and open-domain full-wiki settings.Source: §C.1 · pp. 13–14

C.2 Broad Reasoning Datasets

  • UltraDomain draws on financial reports, legal contracts, and college textbooks across 18 domains, with computer science, agriculture, legal, and mixed-textbook subsets.Source: §C.2 · p. 14

D Baselines

  • NaiveRAG retrieves semantically similar text chunks, whereas GraphRAG extracts entities and relations, clusters communities, and supports local and global retrieval.Source: D Baselines · p. 14
  • LightRAG combines entity-level retrieval with broader knowledge discovery, ToG-2 alternates graph and context retrieval, and HippoRAG-2 uses graph traversal and passage integration.Source: D Baselines · pp. 14–15

E Metrics

The evaluation covers exact-answer and open-ended reasoning, with additional analyses of precision, recall, win rates, and ELO ratings. ToG-3 consistently outperforms the compared baselines on broad reasoning tasks.

E Metrics

  • Deep reasoning uses substring-based Exact Match and word-level F1, while broad reasoning uses LLM judgments of comprehensiveness, diversity, and empowerment.GPT-4o-mini is the judge for the LLM-based evaluation.Source: E Metrics · pp. 15–16
  • The broad-task evaluation also measures diversity and empowerment, assessing answer perspectives and support for informed understanding and judgment.Source: E Metrics · p. 16

F More Experiment Results and Details

F.1 Precision and Recall Rate Results

  • Long or unfocused GraphRAG and LightRAG responses can reduce recall and overall F1, consistent with their lack of design focus on deep reasoning.Source: §F.1 · p. 16

F.2 Result Detail in Braod Reasoning Tasks

F.3 ELO Rating Calculation for Broad Reasoning Tasks

  • ELO ratings transform pairwise win rates logarithmically, assigning ToG-3 a reference rating of 1600 and supporting transitive performance rankings.Source: §F.3 · p. 16

G.1 Comparison of Time Consumption

The results report ToG-3’s efficiency and benchmark performance, alongside case studies and theoretical analysis of its evolving-context process. The prompt templates describe its staged graph-based reasoning workflow.

G.1 Comparison of Time Consumption

  • ToG-3 achieves the best performance on all benchmarks despite higher inference time, while indexing in 10.13 hours versus GraphRAG’s 13.10 hours.LightRAG indexes in 10.06 hours; ToG-3 and LightRAG have similar indexing times.Source: §G.1 · pp. 16–17, Table 6 · p. 18

G.2 Comparison of Token Consumption

  • ToG-3 uses 5.03 versus 12.82 million graph-construction tokens for GraphRAG, but 72.1 inference tokens per sample versus 32.3 for GraphRAG and 23.1 for LightRAG.The authors describe this as shifting computation from preconstruction to targeted reasoning.Source: §G.2 · pp. 17–18, Table 7 · p. 22

H Additional Baselines

  • ToG-3 significantly outperforms compared methods on all metrics across three multi-hop benchmarks; on HotpotQA, its EM is 0.654 versus 0.600 for Youtu-GraphRAG.The authors report a similar lead on 2WikiMultihopQA and Musique.Source: H Additional Baselines · p. 18, Table 8 · p. 22

I Case Study for ToG-3

  • The case studies illustrate dual evolution in deep and broad reasoning: query decomposition and graph refinement support a multi-hop answer, while an evaluator compares system responses in technical and policy examples.In the technical example, GraphRAG emphasizes implementation while ToG-3 discusses theoretical distinctions; the evaluator selects the more comprehensive and empowering response.Source: I Case Study for ToG-3 · p. 18, Figure 6 · p. 19, Figure 7 · p. 20

K Theoretical Support: Implicit Dynamics of In-Context Learning

  • The theoretical account treats reasoning history as inducing attention-based low-rank updates to frozen LLM weights, and extends implicit in-context learning dynamics to analyze convergence.It describes the update as targeted and efficient without catastrophic forgetting of pretrained knowledge.Source: K Theoretical Support: Implicit… · p. 22

J Graph Visualization Examples

  • The visualized datasets contrast depth reasoning over multi-hop entity-relation paths with breadth reasoning across diverse computer-science concepts and relation types.The 2WikiMultihopQA example includes person-to-profession-to-historical-event paths; UltraDomain spans areas such as distributed systems and cloud services.Source: J Graph Visualization Examples · pp. 18, 22, Figure 9 · p. 23, Figure 10 · p. 23

MDP Policy as an Implicit Function of Context

  • Under stated assumptions, the analysis establishes sublinear regret, nonnegative expected policy improvement, and convergence toward a sufficient context; it reports reliable convergence with a reasonable horizon such as K = 3.The account links the vanishing room for improvement to increasingly informative context.Source: MDP Policy as an Implicit Function of… · pp. 23–24

L Prompt Templates

  • The prompt-driven pipeline extracts graph triplets and summarizes communities, then decomposes queries, refines subgraphs, and synthesizes answers from refined evidence; its modular prompts support tuning and auditing.Final synthesis is instructed to use only retrieved context and return “Unknown” when the answer cannot be determined.Source: L Prompt Templates · p. 24

Related papers

Loading 2509.21710v2…