Graph of Thoughts: How Arbitrary Reasoning Graphs Outperform Trees on Complex LLM Tasks

Chain-of-Thought prompting gave large language models the ability to generate explicit intermediate reasoning steps before producing a final answer. Self-Consistency extended that by sampling multiple independent chains and selecting the most frequent answer. Tree of Thoughts added branching and backtracking: a model could explore several paths, evaluate each, and abandon dead ends. Each advance relaxed a structural constraint. Chain-of-Thought constrains reasoning to a single linear sequence. Tree of Thoughts allows branching but still requires every thought to have exactly one predecessor. Maciej Besta and colleagues at ETH Zurich, Warsaw University of Technology, and Cledar identified that single-predecessor constraint as the next limitation to address. Their paper 'Graph of Thoughts: Solving Elaborate Problems with Large Language Models,' submitted to arXiv on August 18, 2023 (arXiv:2308.09687) and presented at AAAI 2024, introduces a framework where LLM thoughts form an arbitrary directed graph rather than a chain or tree.

The constraint a tree structure imposes on complex reasoning

A tree node can have multiple children but only one parent. Every reasoning step in Tree of Thoughts therefore depends on exactly one prior step. This rules out a class of reasoning moves that appear constantly in practical problem-solving: merging two independent lines of reasoning into a single combined conclusion. Consider sorting a large list by dividing it into four independent chunks, sorting each chunk separately, and merging the results. The merge step has four predecessors, not one, and no tree can represent that dependency. The same limitation applies to set operations where results from two independently computed sets need to be combined, to document merging where a final summary integrates independently processed sources, and to any task that follows a divide-and-conquer structure. These are not edge cases. They describe the natural structure of many algorithmic reasoning tasks, and they are precisely the cases GoT is designed to handle.

Vertices, edges, and the GoT data model

GoT defines a thought as any unit of information the LLM generates: a partial answer, an intermediate step, a score, or a plan fragment. Each thought is a vertex in a directed graph. A directed edge from vertex A to vertex B means that B was generated using A as one of its inputs. A vertex can have any number of incoming edges, which is the key structural difference from a tree. When a vertex has multiple incoming edges, the LLM receives all predecessor outputs as inputs and produces a single combined thought. The GoT architecture maintains precise control over the prompt at each vertex: rather than passing the entire reasoning history, each vertex prompt includes only the outputs of its direct predecessors. This keeps prompt lengths short and avoids the redundant context that accumulates in both Chain-of-Thought and Tree of Thoughts as reasoning progresses.

Aggregation, distillation, and refinement via feedback loops

The paper identifies three thought transformations that GoT enables and that tree structures cannot express. Aggregation combines multiple independent thoughts into a single new thought, allowing partial solutions from parallel branches to be merged. The sorting evaluation demonstrates this directly: independently sorted chunks are aggregated at a merge vertex. Distillation compresses many thoughts from a large network into a compact summary, which the paper demonstrates on keyword counting tasks where many candidate keyword sets need to be reduced to one. Refinement cycles a thought back through the LLM with a critique, producing an improved version. In the GoT graph, refinement is a cycle: a vertex whose output eventually feeds back as input to one of its own descendants. All three transformations are represented uniformly as graph edges, making the dependency structure of any reasoning process explicit.

• Besta et al. (arXiv:2308.09687, submitted August 18, 2023; AAAI 2024): authors from ETH Zurich, Warsaw University of Technology, and Cledar; code at github.com/spcl/graph-of-thoughts.
• Core abstraction: LLM thoughts are graph vertices; directed edges encode dependencies; a vertex can have multiple incoming edges, generalizing both Chain-of-Thought (path) and Tree of Thoughts (tree) to arbitrary graphs.
• Three key transformations: aggregation (merge independent branches into one thought), distillation (compress a thought network into a summary), and refinement (feedback cycles that pass a thought back through the LLM for improvement).
• Sorting benchmark: GoT improved sorting quality approximately 70% over Chain-of-Thought and approximately 62% over Tree of Thoughts while reducing costs by more than 31% compared to Tree of Thoughts.
• Tasks evaluated: sorting numbers, keyword counting for summaries, set operations (union and intersection), and document merging; models tested include GPT-3.5, GPT-4, and Llama-2.
• GoT is best suited to tasks with a natural divide-and-merge structure where independent sub-problems can be solved in parallel and then combined; sequential tasks gain less from the graph abstraction.

What the sorting benchmark shows about cost and quality

The sorting result is the clearest illustration of why the graph structure matters. Sorting a long list by dividing it into chunks, sorting each independently, and merging requires a merge vertex with multiple incoming edges. Tree of Thoughts cannot represent this directly: it can branch into separate sorting paths, but those paths cannot converge back into a single vertex. GoT uses the natural graph structure of merge sort, and the results reflect that fit: approximately 62% better sorting quality than Tree of Thoughts with more than 31% lower API cost. The cost reduction follows from prompt length. Each GoT vertex prompt includes only the relevant predecessor outputs, not the growing history of all prior reasoning steps. Tree of Thoughts accumulates context at each node, and that context includes reasoning paths that are not relevant to the current step. GoT eliminates that irrelevant context by construction.

When to apply GoT in practice

GoT provides the most benefit when a task has a natural graph dependency structure rather than a linear or tree-shaped one. A practical heuristic from the paper's evaluations: if the task can be split into independent sub-problems whose outputs need to be merged, the merge step has multiple predecessors and a graph is the right representation. If the task is naturally sequential, Chain-of-Thought or Tree of Thoughts already captures the useful structure and the added engineering of a graph is not warranted. PromptingIndex covers GoT alongside Tree of Thoughts, Self-Consistency, Decomposed Prompting, and ReAct in its series on prompting paradigms that treat reasoning as structured computation. The 62% quality improvement over Tree of Thoughts on sorting, paired with a cost reduction of more than 31%, is a benchmark result worth knowing when evaluating whether a task's dependency structure justifies a graph-based reasoning scheme.