# Adaptive Graph of Thoughts: Test-Time Adaptive Reasoning Unifying Chain, Tree, and Graph Structures

arXiv: https://arxiv.org/abs/2502.05078 · HTML: https://mlsanity.com/paper/2502.05078/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 28 of its 36 references that are in the map.
- First posted on arXiv 7 Feb 2025.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

## Builds on (most cited first, 28 of 28)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [GPT-4o System Card](https://mlsanity.com/paper/2410.21276/) (2024)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [GPQA: A Graduate-Level Google-Proof Q&A Benchmark](https://mlsanity.com/paper/2311.12022/) (2023)
- [PaLM 2 Technical Report](https://mlsanity.com/paper/2305.10403/) (2023)
- [Gemini: A Family of Highly Capable Multimodal Models](https://mlsanity.com/paper/2312.11805/) (2023)
- [Search-o1: Agentic Search-Enhanced Large Reasoning Models](https://mlsanity.com/paper/2501.05366/) (2025)
- [A Comprehensive Survey of Hallucination Mitigation Techniques in Large Language Models](https://mlsanity.com/paper/2401.01313/) (2024)
- [HybridQA: A Dataset of Multi-Hop Question Answering over Tabular and Textual Data](https://mlsanity.com/paper/2004.07347/) (2020)
- [More Agents Is All You Need](https://mlsanity.com/paper/2402.05120/) (2024)
- [ADaPT: As-Needed Decomposition and Planning with Language Models](https://mlsanity.com/paper/2311.05772/) (2023)
- [Reinforcement Learning Enhanced LLMs: A Survey](https://mlsanity.com/paper/2412.10400/) (2024)
- [Explaining black box text modules in natural language with language models](https://mlsanity.com/paper/2305.09863/) (2023)
- [HYDRA: Model Factorization Framework for Black-Box LLM Personalization](https://mlsanity.com/paper/2406.02888/) (2024)
- [TDAG: A Multi-Agent Framework based on Dynamic Task Decomposition and Agent Generation](https://mlsanity.com/paper/2402.10178/) (2024)
- [MoreHopQA: More Than Multi-hop Reasoning](https://mlsanity.com/paper/2406.13397/) (2024)
- [Meta Reasoning for Large Language Models](https://mlsanity.com/paper/2406.11698/) (2024)
- [LLM-Generated Black-box Explanations Can Be Adversarially Helpful](https://mlsanity.com/paper/2405.06800/) (2024)
- [Iteration of Thought: Leveraging Inner Dialogue for Autonomous Large Language Model Reasoning](https://mlsanity.com/paper/2409.12618/) (2024)
- [Understanding the Effects of Iterative Prompting on Truthfulness](https://mlsanity.com/paper/2402.06625/) (2024)
- [ReDel: A Toolkit for LLM-Powered Recursive Multi-Agent Systems](https://mlsanity.com/paper/2408.02248/) (2024)
- [On the Reasoning Capacity of AI Models and How to Quantify It](https://mlsanity.com/paper/2501.13833/) (2025)
- [DGoT: Dynamic Graph of Thoughts for Scientific Abstract Generation](https://mlsanity.com/paper/2403.17491/) (2024)
- [Composite Learning Units: Generalized Learning Beyond Parameter Updates to Transform LLMs into Adaptive Reasoners](https://mlsanity.com/paper/2410.08037/) (2024)

## Built on by (most cited first, 16 of 16)

- [Large Language Models for Planning: A Comprehensive and Systematic Survey](https://mlsanity.com/paper/2505.19683/) (2025)
- [Can Pruning Improve Reasoning? Revisiting Long-CoT Compression with Capability in Mind for Better Reasoning](https://mlsanity.com/paper/2505.14582/) (2025)
- [Graph of Verification: Structured Verification of LLM Reasoning with Directed Acyclic Graphs](https://mlsanity.com/paper/2506.12509/) (2025)
- [Do LLMs Overthink Basic Math Reasoning? Benchmarking the Accuracy-Efficiency Tradeoff in Language Models](https://mlsanity.com/paper/2507.04023/) (2025)
- [The Imitation Game: Turing Machine Imitator is Length Generalizable Reasoner](https://mlsanity.com/paper/2507.13332/) (2025)
- [Diagnosing Multi-step Reasoning Failures in Black-box LLMs via Stepwise Confidence Attribution](https://mlsanity.com/paper/2605.19228/) (2026)
- [Framework of Thoughts: A Foundation Framework for Dynamic and Optimized Reasoning based on Chains, Trees, and Graphs](https://mlsanity.com/paper/2602.16512/) (2026)
- [DiG-Plan: Mitigating Early Commitment for Tool-Graph Planning via Diffusion Guidance](https://mlsanity.com/paper/2606.05728/) (2026)
- [MARCO: Meta-Reflection with Cross-Referencing for Code Reasoning](https://mlsanity.com/paper/2505.17481/) (2025)
- [From Roots to Rewards: Dynamic Tree Reasoning with Reinforcement Learning](https://mlsanity.com/paper/2507.13142/) (2025)
- [GraphGhost: Tracing Structures Behind Large Language Models](https://mlsanity.com/paper/2510.08613/) (2025)
- [RouteGoT: Node-Adaptive Routing for Cost-Efficient Graph of Thoughts Reasoning](https://mlsanity.com/paper/2603.05818/) (2026)
- [Domain-Specialized Tree of Thought through Plug-and-Play Predictors](https://mlsanity.com/paper/2603.20267/) (2026)
- [Enhanced Mycelium of Thought (EMoT): A Bio-Inspired Hierarchical Reasoning Architecture with Strategic Dormancy and Mnemonic Encoding](https://mlsanity.com/paper/2603.24065/) (2026)
- [GroupRAG: Cognitively Inspired Group-Aware Retrieval and Reasoning via Knowledge-Driven Problem Structuring](https://mlsanity.com/paper/2603.26807/) (2026)
- [Reasoning Structure of Large Language Models](https://mlsanity.com/paper/2606.03883/) (2026)

## Abstract (arXiv)

Large Language Models (LLMs) have demonstrated impressive reasoning capabilities, yet their performance is highly dependent on the prompting strategy and model scale. While reinforcement learning and fine-tuning have been deployed to boost reasoning, these approaches incur substantial computational and data overhead. In this work, we introduce Adaptive Graph of Thoughts (AGoT), a dynamic, graph-based inference framework that enhances LLM reasoning solely at test time. Rather than relying on fixed-step methods like Chain of Thought (CoT) or Tree of Thoughts (ToT), AGoT recursively decomposes complex queries into structured subproblems, forming an dynamic directed acyclic graph (DAG) of interdependent reasoning steps. By selectively expanding only those subproblems that require further analysis, AGoT unifies the strengths of chain, tree, and graph paradigms into a cohesive framework that allocates computation where it is most needed. We validate our approach on diverse benchmarks spanning multi-hop retrieval, scientific reasoning, and mathematical problem-solving, achieving up to 46.2% improvement on scientific reasoning tasks (GPQA) - comparable to gains achieved through computationally intensive reinforcement learning approaches and outperforming state-of-the-art iterative approaches. These results suggest that dynamic decomposition and structured recursion offer a scalable, cost-effective alternative to post-training modifications, paving the way for more robust, general-purpose reasoning in LLMs.