Research map / Large language models / Reasoning and chain of thought
Graph of Thoughts: Solving Elaborate Problems with Large Language Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Graph of Thoughts (GoT), a prompting framework that models LLM reasoning as an arbitrary graph of thoughts with aggregation and refinement transformations, evaluated on sorting, set intersection, keyword counting and document merging with GPT-3.5.
Problem
Prompting schemes like Chain-of-Thought and Tree of Thoughts restrict LLM reasoning to chains or trees, which cannot combine or merge intermediate thoughts, limiting performance on elaborate, decomposable problems.
Approach
Model LLM reasoning as a directed graph where vertices are LLM thoughts and edges are dependencies, enabling graph-based transformations such as aggregating multiple thoughts, refining loops, and generating new thoughts, all within prompting and without model updates.
Key results
- On sorting with 128 elements, GoT reduces median error by about 62% relative to ToT while keeping cost reductions above 31%.
- For sorting with 64 elements, GoT's median error is about 65% and 83% lower than CoT and IO respectively.
- Theoretical analysis shows GoT achieves latency log_k N with volume N, versus ToT's latency log_k N with volume O(log_k N).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Graph-based decomposition with aggregation (GoT) instead of ToT | sorting with ChatGPT-3.5 · sorting 128 elements | median error and cost: ≈62% lower median error, >31% lower cost than ToT | Helped |
| Graph-based decomposition with aggregation (GoT) instead of CoT | sorting with ChatGPT-3.5 · sorting 64 elements | median error: ≈65% lower than CoT | Helped |
| Graph-based decomposition with aggregation (GoT) instead of IO | sorting with ChatGPT-3.5 · sorting 64 elements | median error: ≈83% lower than IO | Helped |
| Graph-based decomposition with aggregation (GoT) instead of ToT2 at larger problem size | sorting with ChatGPT-3.5 · sorting 32 vs 64 vs 128 elements | median error vs ToT2: negligible at P=32; ≈61% lower at P=64; ≈69% lower at P=128 | Mixed |
Surprising findings
- Llama-2 was usually worse than GPT-3.5 and much slower to run, so evaluation focused on GPT-3.5.
Limitations
- Evaluation limited to GPT-3.5 due to budget; Llama-2 results not fully reported.
- Results on a small set of synthetic-style tasks with 100 samples each.
- Higher costs than IO and CoT due to multiple generated thoughts per operation.
Experimental setup
Benchmarks: sorting set intersection keyword counting document merging
Metrics: error scope median error cost in dollars volume latency
Baselines: IO CoT CoT-SC ToT ToT2
Builds on: Chain-of-Thought Self-Consistency with CoT Tree of Thoughts
Closest papers by meaning
- THOUGHT PROPAGATION: AN ANALOGICAL APPROACH TO COMPLEX REASONING WITH LARGE LANGUAGE MODELS (ICLR 2024 · similarity 0.89)
- Algorithm of Thoughts: Enhancing Exploration of Ideas in Large Language Models (ICML 2024 · similarity 0.89)
- Enhancing Chain of Thought Prompting in Large Language Models via Reasoning Patterns (AAAI 2025 · similarity 0.89)
- Toward Adaptive Reasoning in Large Language Models with Thought Rollback (ICML 2024 · similarity 0.88)
- Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph (ICLR 2024 · similarity 0.88)
- Let Me Think! A Long Chain of Thought Can Be Worth Exponentially Many Short Ones (NeurIPS 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.