Graph of Thoughts: Solving Elaborate Problems with Large Language Models

By Maciej Besta, Nils Blach, Aleš Kubíček, Robert Gerstenberger, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Michal Podstawski, H. Niewiadomski, Piotr Nyczyk and 1 more. AAAI Conference on Artificial Intelligence, 2023

1,457 citations recorded by the source corpus.

We introduce Graph of Thoughts (GoT): a framework that advances prompting capabilities in large language models (LLMs) beyond those offered by paradigms such as Chain-of-Thought or Tree of Thoughts (ToT). The key idea and primary advantage of GoT is the ability to model the information generated by an LLM as an arbitrary graph, where units of information ("LLM thoughts") are vertices, and edges correspond to dependencies between these vertices. This approach enables combining arbitrary LLM thoughts into synergistic outcomes, distilling the essence of whole networks of thoughts, or enhancing thoughts using feedback loops. We illustrate that GoT offers advantages over state of the art on different tasks, for example increasing the quality of sorting by 62% over ToT, while simultaneously reducing costs by >31%. We ensure that GoT is extensible with new thought transformations and thus can be used to spearhead new prompting schemes. This work brings the LLM reasoning closer to human thinking or brain mechanisms such as recurrence, both of which form complex networks

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/aade40af0d85b0b4fe15c97f6222d5c2e4d6d9b3

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Empowering Biomedical Discovery with AI Agents (2024, positive): “Graph-of-thoughts [168] further develops reasoning paths into a graph structure for complex reasoning.”
MedAgents: Large Language Models as Collaborators for Zero-shot Medical Reasoning (2023, background): “Although numerous attempts, particularly within math and coding, have been made to enhance prompting methods (Besta et al., 2023; Lála et al., 2023; Wang et al., 2023b), strategies used in the medical field have been shown to induce hallucination (Umapathi et al., 2023; Harris, 2023; Ji et al.,…”
To CoT or not to CoT? Chain-of-thought helps mainly on math and symbolic reasoning (2024, neutral): “There is evidence that using additional calls to LLMs can help (Du et al., 2023; Yao et al., 2023; Besta et al., 2023; Chen et al., 2024), but these methods use significantly increased computation, and careful benchmarking sometimes reveals that naive techniques are as good as iterative ones…”
Stop Overthinking: A Survey on Efficient Reasoning for Large Language Models (2025, positive): “Graph-of-Thoughts (GoT) prompting [6] extends this concept by structuring thoughts into a graph, allowing iterative refinement of individual reasoning steps.”
Do NOT Think That Much for 2+3=? On the Overthinking of o1-Like LLMs (2024, positive): “…(Lightman et al., 2024; Li et al., 2023; Khanov et al., 2024; Heineman et al., 2024; Wu et al., 2024), and structured search methods such as Tree-of-Thought, Graph-of-Thought, and Monte Carlo Tree Search (Yao et al., 2024; Besta et al., 2024; Luo et al., 2024; Tian et al., 2024; Wan et al., 2024).”
Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph (2023, background): “…thought of CoT has been improved along different dimensions, including Auto-CoT (Zhang et al., 2022), Complex-CoT (Fu et al., 2023), Self-Consistency (Wang et al., 2023c), Zero-Shot-CoT (Kojima et al., 2022), Iter-CoT (Sun et al., 2023b), ToT (Yao et al., 2023), GoT (Besta et al., 2023) and so on.”
Large Language Monkeys: Scaling Inference Compute with Repeated Sampling (2024, positive): “Similar tree-based methods can also be effective in combination with LLMs, allowing models to better plan and explore different approaches [63, 8, 53, 54].”
TravelPlanner: A Benchmark for Real-World Planning with Language Agents (2024, methodology): “To address this, we introduce Trav-elPlanner for comprehensive evaluations, assessing whether language agents can generate feasible solutions facing various objectives, referred to as constraints in this paper.”
Vision-R1: Incentivizing Reasoning Capability in Multimodal Large Language Models (2025, positive): “…to follow specific steps, such as Chain-of-Thought (CoT) prompting methods [3], plan-based methods like Tree-of-Thought and Graph-of-Thought [4, 5], process-based reward models [6– 9], Monte Carlo Tree Search (MCTS) and Beam Search [10– 12], as well as constructing complex Supervised…”
A Survey of Knowledge Graph Reasoning on Graph Types: Static, Dynamic, and Multi-Modal (2022, background): “As for the second problem, some graph-enhanced techniques, such as Chain-of-Thought (CoT) [321] and Graph-of-Thought (GoT) [322], can be treated asagoodchoice.”
DriveLM: Driving with Graph Visual Question Answering (2023, background): “Finally, VLMs are able to make decisions in multiple steps linked by logical reasoning [4, 16, 75, 77, 82, 85].”
VisualWebArena: Evaluating Multimodal Agents on Realistic Visual Web Tasks (2024, background): “State-of-the-art LLMs (Google, 2023; OpenAI, 2023; Chowdhery et al., 2023; Rae et al., 2021; Zhang et al., 2022; Touvron et al., 2023a;b; Jiang et al., 2023; 2024) based on the Transformer (Vaswani et al., 2017) architecture have demonstrated impressive abilities in learning from in-context examples”
Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models (2023, background): “algorithms (Yao et al., 2023a; Hao et al., 2023; Besta et al., 2023) that can sample trajectories more effectively.”
Understanding the planning of LLM agents: A survey (2024, background): “Graph-of-Thought (GoT) [ Besta et al. , 2023 ] extends ToT by adding transformations of thoughts, which supports arbitrary thoughts aggregation.”
A survey on large language model based autonomous agents (2023, neutral): “(2) Action via Plan Following .”
ReConcile: Round-Table Conference Improves Reasoning via Consensus among Diverse LLMs (2023, methodology): “Owing to the costly nature of conducting experiments with black-box models and the limit imposed on the number of API calls, we follow many prior works (Du et al., 2023; Bian et al., 2023; Besta et al., 2023; Yao et al., 2023) and experiment with a subset of 100 samples (from the validation set for ”
Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning (2023, background): “Graph of thoughts (Besta et al., 2023) further models the reasoning chain as a graph with an aggregation operation to synergize the reasoning paths.”
Unleashing the potential of prompt engineering in Large Language Models: a comprehensive review (2023, methodology): “Unlike the “chain of thoughts” or “tree of thoughts” paradigms, the “graph of thoughts” (GoT) framework [65] offers a more intricate method of representing the information generated by LLMs.”