PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph of Thoughts: Solving Elaborate Problems with Large Language Models

Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Michal Podstawski, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Hubert Niewiadomski, Piotr Nyczyk, Torsten Hoefler

arXiv:2308.09687v4cs.CLcs.AIcs.LG

TL;DR

Graph-based prompting poses design questions about choosing task-appropriate structures and aggregating thoughts to balance accuracy and cost. GoT models LLM thoughts as a graph, with thoughts as vertices and dependencies as edges. It outperforms other prompting schemes, reporting a 62% increase in sorting quality over ToT while reducing costs by >31%.

  • Problem

    Practical use of graph-based prompting raises design questions about choosing task-appropriate graph structures and aggregating thoughts to balance accuracy and cost.

    Source: §1 · p. 1

  • Method

    GoT models LLM thoughts as graph vertices linked by dependencies, allowing thought aggregation and generalizing CoT and ToT without model updates.

    Source: §1 · p. 1

  • Results

    GoT outperforms other prompting schemes, with a 62% increase in sorting quality over ToT and a simultaneous cost reduction of >31%.

    Source: §9 · p. 10

  • Takeaways & Limitations

    The volume metric provides a step toward more principled prompt engineering.

    Source: §9 · p. 10

    Evaluation focused on GPT-3.5 because of budget restrictions; Llama-2 was usually worse and slower, making enough samples infeasible to obtain.

    Source: §7.1 · p. 8

Abstract

from arXiv · show

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.

1 Introduction

The introduction presents GoT as a graph-based prompting framework that generalizes chain- and tree-structured reasoning, enabling thought transformations that rigid structures cannot express. It previews GoT’s modular architecture, applications, evaluation results, and thought-volume metric.

1 Introduction

  • Prompt engineering includes a task description in the input; CoT [71] includes intermediate reasoning steps, while ToT [43] [75] [77] models reasoning as a tree, enabling multiple thought paths and backtracking.Source: §1 · p. 1
  • GoT models thoughts as graph vertices and dependencies as edges, allowing arbitrary thoughts to be aggregated and generalizing CoT and ToT without model updates.This supports combining ideas across reasoning paths, unlike the rigid tree structure of ToT.Source: §1 · p. 1
  • A modular architecture provides fine-grained control over thoughts and supports extensible transformations, reasoning graphs, and LLM models.The design addresses choices such as task-specific graph structure and how to aggregate thoughts for accuracy and cost.Source: §1 · pp. 1–2
  • ≈70% and ≈62%: GoT improves sorting quality over CoT and ToT, respectively, while reducing costs by >31% over ToT.GoT is particularly suited to tasks that can be decomposed into subtasks and then merged into a final solution.Source: §1 · p. 2
  • GoT illustrates graph-based implementations for sorting, keyword counting for summaries, set operations, and document merging, and is the only scheme supporting arbitrary graph-based thought transformations.The comparison includes aggregation and describes GoT as embracing previously proposed schemes.Source: §1 · p. 2, Table 1 · p. 2
  • The proposed thought-volume metric counts how many thoughts can reach a given thought through directed edges; aggregation lets GoT thoughts have larger volumes than in other schemes.The volume represents thoughts that had the potential to contribute to the given thought.Source: §1 · p. 2

2 Background & Notation

The section defines an LLM “thought” flexibly by use case and outlines prompting schemes that add intermediate reasoning or structure beyond direct input-to-output generation.

2.1 Language Models & In-Context Learning

  • A pre-trained language model with parameters θ is denoted pθ; thoughts x, y, z are use-case-specific units ranging from paragraphs to documents or code blocks.The notation follows [77], and the definition deliberately does not prescribe a fixed size for a thought.Source: §2.1 · p. 2

Input-Output (IO)

  • Input-Output prompting maps an input sequence x directly to output y without intermediate thoughts.Source: Input-Output (IO) · p. 2

Chain-of-Thought (CoT)

  • Chain-of-Thought inserts intermediate thoughts a1, a2, ... between input x and output y, improving tasks such as mathematical puzzles [71] and reasoning over plain IO.Source: Chain-of-Thought (CoT) · p. 2

Multiple CoTs

  • CoT-SC generates k independent CoTs and selects the best output by a scoring metric, exploring alternative paths but not backtracking locally within a path [67].The scheme was introduced by Wang et al.Source: Multiple CoTs · p. 2

Tree of Thoughts (ToT)

  • Tree of Thoughts models reasoning as a tree of partial solutions; a generator proposes k nodes, an evaluator scores them, and a search algorithm such as BFS or DFS extends the tree [77] [43].Evaluation may use an LLM or human scores; the approach was also used implicitly by thought decomposition [75].Source: Tree of Thoughts (ToT) · p. 2

3 The GoT Framework

GoT represents LLM reasoning as a graph, with thought transformations, an evaluator for scoring thoughts, and a ranking function for selecting relevant thoughts.

3.1 Reasoning Process

  • GoT models reasoning as a directed graph whose vertices hold problem solutions and whose edges mark direct-input dependencies.Vertices can represent initial, intermediate, or final solutions; heterogeneous graphs can also distinguish types of thought, such as plans and paragraphs.Source: §3.1 · p. 3

3.2 Transformations of Thoughts

  • Transformations modify the reasoning graph by adding thoughts and dependency edges, and can also remove specified parts of the graph.This permits removing reasoning that does not promise improvements to save context space; users must ensure the specified additions and removals are consistent.Source: §3.2 · pp. 3–4

Aggregation Transformations

  • Aggregation combines arbitrary thoughts or reasoning paths into a new thought that can reinforce their advantages and eliminate disadvantages.The graph represents this by connecting the final thoughts of multiple chains to one combined thought.Source: Aggregation Transformations · p. 4

Refining Transformations

  • Refining modifies a thought’s content through an iterated thought represented by a self-loop on the original vertex.The refined thought retains the original thought’s connections.Source: Refining Transformations · p. 4

Generation Transformations

  • Generation creates one or more new thoughts based on a single existing thought, encompassing analogous steps from ToT and CoT-SC.Each generated thought is connected to its source thought.Source: Generation Transformations · p. 4

3.3 Scoring & Ranking Thoughts

  • GoT scores thoughts using the thought and the full reasoning graph, then can return a specified number of highest-scoring thoughts.Scoring and ranking functions are use-case-specific; for sorting, score can count correctly sorted elements, or use errors instead.Source: §3.3 · p. 4

4 System Architecture & Extensibility

GoT is organized as interacting modules governed by a static operation graph and a dynamic reasoning state, with extensible APIs for implementing prompting schemes.

4 System Architecture & Extensibility

  • GoT combines a Prompter, Parser, Scoring module, and Controller, which coordinates reasoning; its Graph of Operations (GoO) defines transformations and dependencies, while its Graph Reasoning State (GRS) tracks reasoning history.The GoO is static, whereas the GRS is dynamic.Source: §4 · p. 4

4.1 Prompter

  • The Prompter prepares LLM prompts and can encode the graph structure in use-case-specific ways because users have access to the full graph.Source: §4.1 · p. 4

4.2 Parser

  • The Parser extracts information from each LLM thought to construct a thought state, which it uses to update the GRS.Source: §4.2 · p. 4

4.3 Scoring & Validation

  • Scoring verifies thoughts against potential correctness conditions and assigns scores using the LLM, human judgment, or simple local functions, depending on the use case.Source: §4.3 · p. 4

4.4 Controller

  • The Controller selects thoughts and transformations from the GRS, passes them to the Prompter, and decides whether to finalize or begin another LLM interaction according to the GoO plan.Source: §4.4 · p. 4

4.5 GoO & GRS

  • The user-defined GoO statically plans operations and their dependencies, while the GRS tracks execution progress and each thought’s state, validity, and score; operations include Generate, Aggregate, Score, KeepBest, and Repeat.Repeat(k) repeats an operation k times, while KeepBest(N) preserves the N highest-scoring thoughts.Source: §4.5 · pp. 4–5
  • Extensible APIs support new prompting schemes and thought transformations, and the GoO can specify GoT as well as CoT, CoT-SC, and ToT.Prompter and Parser APIs include operations for generating, improving, aggregating, scoring, and validating thoughts.Source: §4.5 · pp. 4–5

5 Example Use Cases

The section illustrates GoT across sorting, set intersection, keyword counting, and document merging, using task-specific decomposition, aggregation, and scoring methods.

5.1 Sorting

  • GoT sorts number sequences by splitting them into subarrays, sorting each, and merging them into a final sequence.The motivating challenge is that the considered LLMs inconsistently sort longer sequences with duplicates because duplicate counts do not match.Source: §5.1 · p. 6
  • The sorting error scope sums incorrectly ordered adjacent pairs and deviations in the output frequencies of numbers 0–9.For plotting, the score is clipped at n; a positive score for correctly sorted elements is max(n − error-scope, 0).Source: §5.1 · p. 6

5.2 Set Operations

  • For set intersection, GoT splits the second set into subsets, intersects each with the first set using an LLM, and aggregates the results.Evaluation varies set sizes across 32, 64, and 128 elements and overlap from 25% to 75%; error scope counts extra, missing, and duplicate output elements.Source: §5.2 · p. 7

5.3 Keyword Counting

  • For keyword counting, GoT splits input text into passages, counts category keywords in each, and aggregates the subresults.Passage count is configurable or can be left to the LLM; scoring sums absolute differences between computed and correct counts for each keyword.Source: §5.3 · p. 7

5.4 Document Merging

  • Document merging generates a new NDA from partially overlapping inputs, aiming to minimize duplication while maximizing retained information.The score is the harmonic mean of LLM-rated redundancy and information retention, with each value queried three times and averaged.Source: §5.4 · p. 7

6 The Latency-Volume Tradeoff

GoT achieves the section’s best latency-volume tradeoff: it combines low latency with high volume by aggregating thoughts, so the final thought can be reached from any intermediate thought. The comparison fixes each prompting scheme’s total cost at Θ(n).

6 The Latency-Volume Tradeoff

  • Latency is the number of graph hops to a final thought, while volume counts preceding thoughts with a path to that thought; each scheme has total cost Θ(n).The analysis assumes outputting one thought costs O(1) time.Source: §6 · p. 7
  • CoT-SC uses k independent chains from one starting thought, ToT is a complete k-ary tree, and GoT joins a complete k-ary tree at its leaves to a mirrored tree with reversed edges.The GoT construction uses a mirrored k-ary tree of the same size.Source: §6 · p. 7
  • GoT alone combines latency log_k N with volume N; CoT offers volume up to N at latency N, CoT-SC reduces both by k, and ToT has latency log_k N but low volume.GoT’s aggregations let the final thought be reached from any intermediate thought in the graph decomposition.Source: Table 2 · p. 7, §6 · p. 7

7 Evaluation

Across the evaluated tasks, GoT improves outcome quality over the considered baselines and reduces inference costs compared with ToT. Its quality advantage grows with problem size, while task decomposition and aggregation help explain its performance.

7.1 Evaluation Methodology

  • Evaluation used GPT-3.5 because Llama-2 was usually worse and much slower, making it infeasible to obtain enough samples.Experiments used 100 input samples per task and comparison baseline, temperature 1.0, a 4k context size unless stated otherwise, and similar costs across schemes.Source: §7.1 · pp. 7–8

7.2 Analysis of GoT’s Advantages

  • For sorting P = 128, GoT reduced median error by ≈62% versus ToT while cutting costs by >31%.Overall, GoT improved outcome quality over all considered baselines and reduced inference costs compared with ToT.Source: §7.2 · p. 8

7.3 Discussion on Task Decomposition

  • GoT decomposes complex tasks into simpler subtasks, solves them independently, and incrementally merges their outcomes into the final result.Decomposition reduces response and input token sizes proportionally to its degree, though few-shot examples can become a significant overhead and may themselves be shortened to reduce cost.Source: §7.2 · p. 8, §7.3 · p. 8

7.2 Analysis of GoT’s Advantages

  • For sorting P = 64, GoT’s median error was ≈65% lower than CoT’s and ≈83% lower than IO’s, but GoT and ToT cost more than IO and CoT.The higher GoT and ToT costs reflect generating k new thoughts per Generate operation; the multiple thoughts also contribute to GoT’s quality advantage.Source: §7.2 · p. 8
  • As sorting size increased, GoT’s median error was negligibly better than ToT2 at P = 32, then ≈61% lower at P = 64 and ≈69% lower at P = 128.IO became consistently worse as P increased; the analysis indicates GoT is suited to elaborate problems whose execution schedules grow more complex.Source: §7.2 · p. 8

7.3 Discussion on Task Decomposition

  • Decomposition aims to make subtasks solvable correctly with one prompt or a few improvement steps, while aggregating subresults is usually easier than solving a large task from scratch.This can reduce later refinement steps and help the LLM successfully aggregate the final solution.Source: §7.3 · p. 8

8 Related Work

The related work positions GoT alongside prompting, reflection, and planning approaches, while distinguishing its use of graph abstraction to extend LLM prompting within a single context.

8.1 Prompting Paradigms & Approaches

  • Related approaches include planning, complexity-based prompting, candidate selection, scaling remedies, skeleton expansion, and prompt chaining; GoT is orthogonal to prompt chaining because it focuses on single-context capabilities.Prompt chaining cascades different LLMs through different contexts.Source: §8.1 · p. 9

8.2 Self-Reflection & Self-Evaluation

  • GoT partially uses self-evaluation to decide how to expand its thought graph, building on self-reflection and evaluation work used in tasks including code generation and computer operation [45] [49] [60] [75] [85] [17] [39].The cited work describes self-reflection and self-evaluation as methods for enhancing different tasks.Source: §8.2 · pp. 9–10

8.3 LLMs & Planning

  • GoT could enhance complex-task planning schemes by providing a paradigm for generating complex graph-based plans [36] [37] [68] [76] [78] [81].The paper presents this as a potential use of GoT's general framework.Source: §8.3 · p. 10

8.4 Graphs and Graph Computing

  • GoT harnesses graph abstraction as a key mechanism for enhancing LLM prompting, drawing on an abstraction used across computing and research domains [56].The paper gives examples ranging from graph databases and machine learning to social sciences, bioinformatics, chemistry, and transportation.Source: §8.4 · p. 10

9 Conclusion

Because effective prompt design is challenging despite enabling LLM use without model updates, the paper proposes GoT, which models reasoning as a graph of thought vertices and dependency edges.

9 Conclusion

  • GoT represents LLM reasoning as an arbitrary graph, enabling thought transformations such as aggregation and reflecting nonlinear problem solving.Thoughts are vertices and dependencies between thoughts are edges; people combine intermediate solutions and change reasoning flow when new insights emerge.Source: §9 · p. 10
  • GoT increases sorting quality by 62% over ToT while reducing costs by >31%, and also excels on the proposed volume-of-a-thought metric.The volume-of-a-thought metric indicates the scope of information an LLM output could carry.Source: §9 · p. 10
  • The proposed volume-of-a-thought metric indicates the scope of information an LLM output could carry and supports more principled prompt engineering.GoT excels on this metric.Source: §9 · p. 10
  • Graph abstractions have underpinned successful designs in computing and AI, including AlphaFold for protein prediction, and this work applies them to prompt engineering.Source: §9 · p. 10

A Positive Score Evaluation

This section presents a positive-score view of data also shown in Figures 5 and 6. Its figures cover accuracy and cost in sorting and set-intersection tasks with ChatGPT-3.5.

A Positive Score Evaluation

B Example Prompts - Sorting … E Example Prompts - Document Merging

The appendix documents example prompts and LLM interactions for sorting, set intersection, keyword counting, and document merging. It describes each task’s operations and notes which prompt variants or examples are shown.

B Example Prompts - Sorting

C Example Prompts - Set Intersection

  • Set intersection uses Generate to intersect or split sets, then Aggregate to combine two sets.The prompts shown are for two 32-element sets; larger-set prompts are identical except that the split size changes proportionally.Source: C Example Prompts - Set Intersection · p. 22

D Example Prompts - Keyword Counting

  • Keyword counting uses Generate to count keywords or split text, Aggregate to combine counted-keyword dictionaries, and ValidateAndImprove to correct aggregation mistakes.The prompts shown are for GoT4; GoT8 and GoTx differ only slightly in split size.Source: D Example Prompts - Keyword Counting · p. 28

E Example Prompts - Document Merging

  • Document merging uses Generate to merge four NDAs, Score to evaluate merged drafts, Aggregate to combine attempts, and Improve to revise a merged NDA.GoT2 differs by merging the four NDAs in two steps rather than one.Source: E Example Prompts - Document Merging · p. 41
  • The document-merging walkthrough shows four input NDAs, the final merged NDA, and scoring interactions for the best-performing drafts; most responses are abbreviated.Full logs and further examples are referenced in the corresponding code repository.Source: E Example Prompts - Document Merging · p. 41

F Evaluation - GoT Configurations

The configurations apply GoT’s generation, scoring, selection, and aggregation operations to set intersection and sorting at increasing input sizes. Both tasks split inputs into 16-element parts, combine partial results, and compare final results with ground truth.

Set intersection

  • For 32-element set intersection, GoT splits the second set in half, intersects each half with the first set, then aggregates the selected partial intersections with Aggregate(k=10).Scoring and KeepBestN(1) select partial and final results before comparison with ground truth.Source: F Evaluation - GoT Configurations · p. 62
  • For 64-element set intersection, GoT splits the second set into four 16-element parts and combines their intersections through pairwise and final Aggregate(k=10) merges.Each part is intersected with the first set, scored, and selected before merging; the final result is checked against ground truth.Source: F Evaluation - GoT Configurations · p. 62
  • For 128-element set intersection, GoT processes eight 16-element subsets and combines their intersections through a hierarchy of Aggregate(k=5), Score, and KeepBestN steps before the final ground-truth check.Each subset intersection is generated with k=5; each merge retains the best-scoring result.Source: F Evaluation - GoT Configurations · p. 62

Sorting

  • For 32- and 64-element sorting, GoT sorts 16-element parts, scores and selects partial results, aggregates them, and applies a final Generate(k=10) improvement.The 32-element configuration starts with two halves; the 64-element configuration uses four parts and also improves intermediate merged lists with Generate(k=5).Source: F Evaluation - GoT Configurations · p. 62
  • For 128-element sorting, GoT sorts eight 16-element parts, repeatedly aggregates and improves partial lists, then aggregates the final result and tries Generate(k=10) improvement.Scoring and KeepBestN(1) selection occur on partial and merged results before the ground-truth comparison.Source: F Evaluation - GoT Configurations · p. 63

Related papers

Loading 2308.09687v4…