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

Existing prompting schemes do not fully support the complex, networked reasoning patterns needed for arbitrary thought combinations and feedback. Graph of Thoughts models LLM reasoning as an arbitrary graph and outperforms other prompting schemes, increasing sorting quality by 62% over ToT while reducing costs by >31%.

  • Problem

    Prior prompting schemes are limited in representing complex thought networks, leaving graph structure and thought aggregation design questions for different tasks.

  • Method

    Graph of Thoughts models LLM thoughts as vertices and dependencies as directed edges, applying extensible transformations that modify the reasoning graph without model updates.

  • Results

    62% increase in sorting quality over ToT accompanies a >31% reduction in costs, while GoT also excels on thought volume.

  • Takeaways & Limitations

    GoT provides a step toward more principled prompt engineering by supporting graph-based thought transformations and networked reasoning.

  • Takeaways & Limitations

    Evaluation focuses on GPT-3.5 because Llama-2 was usually worse and slower, making sufficient sampling infeasible.

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

Graph of Thoughts (GoT) extends prompting from chains and trees to arbitrary graphs of interdependent LLM thoughts, enabling networked reasoning and transformations such as aggregation. The paper presents a modular, extensible architecture, demonstrates use cases and advantages over existing schemes, and introduces thought volume as an evaluation metric.

  • Unlike Chain-of-Thought (CoT) [71] and Tree of Thoughts (ToT) [43] [75] [77], GoT represents reasoning as an arbitrary graph motivated by human reasoning, brain structure, and algorithmic execution.CoT uses intermediate reasoning steps, while ToT models multiple thought paths and supports backtracking from non-promising outcomes.
  • GoT models LLM thoughts as vertices and their dependencies as edges, enabling arbitrary aggregation and other networked thought transformations.Vertices may have multiple incoming edges, allowing arbitrary thoughts to be combined into new thoughts.
  • GoT’s modular architecture provides fine-grained control over individual thoughts and can be extended with novel thought transformations.The architecture supports controlling the ongoing LLM conversation and combining promising thoughts into new ones.
  • The paper demonstrates GoT for sorting, keyword counting for summaries, set operations, and document merging, finding it particularly suited to decomposing tasks into subtasks that are solved individually and then merged.These use cases are implemented through the graph-based paradigm and evaluated against the state of the art.
  • GoT is the only compared prompting scheme supporting arbitrary graph-based thought transformations, while also embracing previously proposed schemes.The comparison appears in Table 1 and concerns supported transformations of thoughts.
  • GoT introduces thought volume, defined for a thought v as the number of LLM thoughts that can reach v through directed edges.The metric captures thoughts that had the potential to contribute to v; GoT enables fundamentally larger thought volumes through transformations such as aggregation.

2 Background & Notation

This section defines LLM thoughts and notation, then introduces prompting paradigms from direct input-output mapping through CoT, self-consistency, and ToT. These approaches progressively add intermediate reasoning, path exploration, and tree-structured search.

  • Notation: LLM conversations comprise user prompts and LLM replies, with a language model denoted pθ and lowercase variables representing use-case-specific thoughts.A thought may be a paragraph, document, or code block, and its granularity is intentionally left unspecified.
  • Prompting approaches: IO prompting maps an input sequence x directly to an output y without intermediate thoughts.
  • Prompting approaches: CoT inserts intermediate thoughts between x and y and improves language-model performance on mathematical puzzles [71] and general mathematical reasoning over IO.
  • Prompting approaches: CoT-SC generates k independent reasoning chains and selects the best-scoring output, enabling path exploration but not local backtracking within a chain.This scheme was introduced by Wang et al. [67].
  • Prompting approaches: ToT models reasoning as a tree of thoughts, where each node is a partial solution expanded into k new nodes and evaluated by scores f.The scheme was introduced independently by Yao [77] and Long [43].

3 The GoT Framework

GoT models LLM reasoning as a directed, potentially heterogeneous graph of thoughts and dependencies, augmented by transformations, evaluation, and ranking. This representation supports aggregation, refinement, generation, and removal of unpromising reasoning components.

  • 3 The GoT Framework: Formally, GoT is the tuple (G, T, E, R), comprising the reasoning graph, thought transformations, evaluator, and ranking function.Together, these components define the framework’s graph-based reasoning process.
  • 3 The GoT Framework: GoT represents reasoning as a directed graph whose vertices contain initial, intermediate, or final solutions and whose edges encode thought dependencies.Thoughts can take use-case-specific forms, such as paragraphs or number sequences.
  • 3 The GoT Framework: Heterogeneous GoT graphs assign vertices to classes, allowing different reasoning aspects such as writing plans and paragraphs to coexist.A class-mapping function c maps vertices into their respective classes C.
  • 3 The GoT Framework: GoT transformations modify the reasoning graph by adding thoughts and dependency edges, and can also remove components that do not promise improvement.Transformations include aggregating thoughts or reasoning paths, refining a thought through a self-loop, and generating new thoughts from an existing one.
  • 3 The GoT Framework: GoT scores thoughts using the full reasoning state and ranks a use-case-dependent number of high-scoring thoughts for selection.The scoring function can compare thoughts relative to one another, while sorting scores count correctly sorted elements or use sorting errors.

4 System Architecture & Extensibility

GoT organizes reasoning through interacting modules coordinated by a Controller that separates a static execution plan from dynamic reasoning state. Its extensible APIs support new prompting schemes, thought transformations, and LLM integrations.

  • Architecture: The architecture combines a Prompter, Parser, Scoring module, and Controller, which coordinates the reasoning process and determines how it progresses.The Prompter prepares messages, the Parser extracts information from thoughts, and the Scoring module verifies and scores them.
  • Architecture: The Controller uses a static Graph of Operations to specify transformations, ordering, dependencies, and execution plans, while the dynamic Graph Reasoning State tracks ongoing reasoning.The GRS maintains executed operations and the states and validity of generated thoughts.
  • Extensibility: The modules expose extensible APIs for generating, improving, aggregating, parsing, validating, and scoring LLM thoughts, with operations such as KeepBest(N) and Repeat(k).Repeat(k) generates k thoughts whose states remain in the GRS and are scored individually.
  • Extensibility: The GoO can specify GoT and existing schemes such as CoT, CoT-SC, and ToT, while the design supports use-case-specific graph encodings and different LLMs.The Prompter provides full access to graph structure for encoding it in prompts, and Figure 3 describes extending the design toward new schemes and plugging in different LLMs.

5 Example Use Cases

GoT is illustrated through sorting and several other workloads, using graph-based decomposition, aggregation, scoring, and selection to solve structured problems. The examples include sorting, set intersection, keyword counting, and document merging.

  • Sorting: GoT addresses sorting sequences with duplicates by decomposing inputs into subarrays, sorting them individually, and merging the results through graph operations.The considered LLMs struggle to sort such sequences reliably beyond a certain length because duplicate counts do not match.
  • Sorting: Sorting outcomes are scored by error scope, combining incorrectly ordered consecutive pairs with mismatches between input and output number frequencies.The score measures both ordering errors and whether the output preserves each number’s frequency.
  • Set intersection: Set intersection similarly splits the second set, computes subset intersections with an LLM, and aggregates them for final results across set sizes of 32, 64, and 128 elements.Evaluation varies the proportion of elements shared by both sets from 25% to 75%.
  • Set intersection: Set-intersection error scope counts extraneous elements, missing elements, and duplicates, while max(n − error-scope, 0) provides a positive correctness score.This accounts for the LLM expressing sets as natural-language lists, which can contain duplicates.
  • Other use cases: Additional use cases split keyword-counting inputs into passages for local counting and aggregation, and merge overlapping documents into minimally duplicative, information-preserving NDA documents.The number of keyword-counting passages is configurable or can be assigned by the LLM; document merging is applicable to legal procedures.

6 The Latency-Volume Tradeoff

GoT improves the latency–volume tradeoff by combining logarithmic latency with maximum volume under a fixed total prompting cost. This advantage arises from its graph structure, which joins a k-ary tree to a mirrored tree through leaf aggregations.

  • 6 The Latency-Volume Tradeoff: Volume is the number of preceding thoughts connected to a thought by paths, while latency is the number of graph hops to reach it.The comparison assumes outputting one thought costs O(1) time and fixes each scheme’s total cost at Θ(n).
  • 6 The Latency-Volume Tradeoff: CoT-SC uses k independent chains, ToT uses a complete k-ary tree, and GoT joins a complete k-ary tree to a reversed mirrored tree at its leaves.These structures determine how prompting schemes distribute latency and volume across generated thoughts.
  • 6 The Latency-Volume Tradeoff: CoT reaches volume N with latency N, CoT-SC reduces both by factor k, and ToT reaches latency log_k N but retains low volume.GoT’s high volume is enabled by aggregating thoughts in its graph structure.
  • 6 The Latency-Volume Tradeoff: GoT offers the best latency–volume tradeoff, achieving latency log_k N with high volume N, unlike prior prompting schemes.The analysis identifies GoT as the only scheme combining low latency log_k N with high volume N.

7 Evaluation

The evaluation compares GoT with ToT, ToT2, IO, and CoT across sorting, set intersection, keyword counting, and document merging. GoT improves outcome quality over all considered baselines while reducing inference costs compared with ToT, with advantages increasing for larger problem sizes.

  • Evaluation setup: Experiments use 100 samples per task and baseline, temperature 1.0, a 4k context, and cost-matched thought counts, primarily evaluating GPT-3.5.Llama-2 was usually worse and slower than GPT-3.5, making sufficient sampling infeasible; configurations vary branching factor k and levels L.
  • Overall results: GoT improves outcome quality over all considered baselines and reduces inference costs compared with ToT across the evaluated tasks.Results cover sorting, set intersection, keyword counting, and document merging.
  • GoT vs. ToT: GoT reduces median sorting error by ≈62% versus ToT for P = 128 while achieving >31% cost reductions.GoT costs are always lower than ToT and comparable to ToT2, while ToT generally has higher quality than ToT2.
  • GoT vs. IO and CoT: For sorting with P = 64, GoT’s median error is ≈65% lower than CoT and ≈83% lower than IO.GoT and ToT cost much more than IO and CoT because they generate additional thoughts.
  • Increasing Complexity of Tackled Problems: GoT’s quality advantage increases with problem size, with median sorting error ≈61% lower than ToT2 at P = 64 and ≈69% lower at P = 128.At P = 32, GoT only negligibly improves upon ToT2; IO becomes consistently worse as P increases.
  • Evaluation analysis: Graph decomposition reduces response and input tokens proportionally to decomposition degree, but static few-shot prompts can become significant overhead.Reducing few-shot examples and decomposing tasks until single-prompt solutions are usually possible lowers later refinement steps; combining subresults is generally easier than solving large instances directly.

8 Related Work

GoT is positioned among prompting methods that extend, structure, or evaluate LLM reasoning, while remaining orthogonal to multi-LLM prompt chaining. It also connects to complex-task planning and broader graph-based computing research.

  • Prompting paradigms: Related prompting methods enhance CoT through explicit planning, complexity-based criteria, candidate-prompt selection, or staged skeleton expansion [66, 29, 67, 84, 47].The paper points to surveys for broader coverage [34] [40] [69] [70].
  • Prompting paradigms: GoT is orthogonal to prompt chaining because it focuses on the capabilities of a single context rather than cascading different LLMs [21] [23] [48] [51] [72] [73].Prompt chaining enables different LLMs to receive different contexts for more powerful reasoning.
  • Self-evaluation: GoT partially relies on self-evaluation to decide how to expand its graph of thoughts, building on self-reflection and self-evaluation methods [45] [49] [60] [75] [85].The paper notes applications of these methods to code generation [17] and computer operation tasks [39].
  • Complex-task planning: GoT could potentially enhance complex-task planning schemes by providing a generic paradigm for generating graph-based plans [36] [37] [68] [76] [78] [81].The paper frames this as a potential use rather than an established result.

9 Conclusion

Graph of Thoughts (GoT) models LLM reasoning as an arbitrary graph of thoughts and dependencies, enabling effective task solving without model updates. It outperforms other prompting schemes while introducing thought volume as a more principled prompt-engineering metric.

  • Prompt engineering uses LLMs without model updates but remains challenging because designing effective prompts is difficult.
  • GoT enables effective task solving without model updates by representing thoughts as vertices and dependencies between thoughts as edges in an arbitrary graph.This representation supports novel thought transformations, including aggregation.
  • 62% increase in sorting quality over ToT accompanies a >31% reduction in costs, while GoT also excels on the volume of a thought metric.The volume metric indicates the scope of information an LLM output could carry.
  • GoT applies a graph abstraction successful in computing and AI, including AlphaFold for protein predictions, to prompt engineering.

A Positive Score Evaluation

This evaluation replots the data from Figures 5 and 6 using the positive score defined in Sections 5.1 and 5.2, covering sorting and set-intersection tasks with ChatGPT-3.5.

  • Sorting: The positive-score evaluation reports accuracy and cost for sorting tasks with ChatGPT-3.5 across ToT structures parameterized by L and k.Figure 9 replots the corresponding data using the positive score.
  • Set intersection: The positive-score evaluation reports accuracy and cost for set-intersection tasks with ChatGPT-3.5 across ToT structures parameterized by L and k.Figure 10 replots the corresponding data using the positive score.

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

This appendix provides runtime prompt templates, few-shot examples, and complete interaction traces for sorting, set intersection, keyword counting, and document merging. Each example specifies the LLM operations and representative task sizes or variants covered.

  • B Example Prompts - Sorting: Sorting combines Generate, Improve, and Aggregate operations with dedicated prompts for sorting, splitting, refining mistakes, and aggregating results.The displayed prompts target 32-element lists; 64- and 128-element versions are identical except for split-prompt example sizing.
  • B Example Prompts - Sorting: For sorting, set intersection, and keyword counting, prompt stubs serve as runtime templates, while separate tables provide few-shot examples and step-by-step LLM interactions.The sorting, set-intersection, and keyword-counting traces cover the complete example processes described in their respective tables.
  • B Example Prompts - Sorting: The sorting and set-intersection examples include execution plans and prompt/response traces for their 32-element cases, while keyword counting traces a four-passage GoT4 split.These materials are organized across the corresponding execution-plan and step tables.
  • C Example Prompts - Set Intersection: Set intersection uses Generate prompts for intersecting or splitting sets and Aggregate prompts for merging two sets into one.Prompts are shown for intersecting two 32-element sets, with proportional split-size adjustments for larger sets.
  • D Example Prompts - Keyword Counting: Keyword counting uses Generate prompts to count keywords and split text, Aggregate prompts to merge counted-keyword dictionaries, and a ValidateAndImprove operation.The appendix illustrates GoT4; GoT8 and GoTx use identical prompts apart from minor split-size differences.
  • E Example Prompts - Document Merging: Document merging uses Generate, Score, and additional LLM-interacting operations to merge four NDAs, evaluate merged outputs, and support the complete merging process.The appendix presents prompts for GoT; GoT2 differs by merging the four NDAs in two steps rather than one.
  • E Example Prompts - Document Merging: The document-merging appendix presents prompt stubs followed by a complete interaction trace, displaying the four input NDAs and final merged NDA separately from repeated prompt responses.It also includes scoring examples because scoring is performed using the LLM.
  • E Example Prompts - Document Merging: The document-merging trace covers multiple merge steps, scoring examples, highest-scoring responses, and the final merged NDA across Tables 31–49.Input documents, intermediate candidates, scores, and selected responses are distributed across the appendix tables.

F Evaluation - GoT Configurations

GoT configurations instantiate graph-based reasoning for set intersection and sorting through recursive generation, scoring, selection, aggregation, and ground-truth comparison across inputs of 32, 64, and 128 elements.

  • Set intersection: Set intersection configurations split inputs into 16-element subsets, generate candidate intersections, score and retain the best results, aggregate them through hierarchical merges, and compare against ground truth.For 32 elements, the second set is split into two halves; for 64 and 128 elements, it is split into four and eight parts, respectively.
  • Shared configuration pattern: Across both use cases, GoT repeatedly combines local candidate generation and scoring with KeepBestN selection and Aggregate operations, producing increasingly integrated results before final validation.Set intersection uses Generate(k=5), Score(k=1), KeepBestN(1), and aggregation; sorting uses the same core pattern plus solution-improvement generations.
  • Sorting: Sorting configurations split lists into 16-element parts, generate and score partial sorts, retain the best candidates, aggregate them through merge steps, and apply further generation-based improvements before ground-truth comparison.The configurations scale from two parts for 32 elements to four parts for 64 and eight parts for 128 elements, with Generate(k=5) for partial improvements and Generate(k=10) for final improvements.
Loading 2308.09687v4…