Principle:Spcl Graph of thoughts GoT Graph Topology Design

Field	Value
Pattern Name	GoT_Graph_Topology_Design
Type	Principle
Repository	spcl/graph-of-thoughts
Domains	Graph_Reasoning, Topology_Design
Sources	GoT Paper (arXiv:2308.09687)
Related Implementations	Implementation:Spcl_Graph_of_thoughts_GoT_Sorting_Topology

Overview

Design pattern for constructing Graph of Thoughts topologies that implement decompose-solve-merge reasoning strategies.

Description

The Graph of Thoughts (GoT) framework provides a flexible mechanism for constructing different reasoning topologies as Graphs of Operations (GoOs). Each topology prescribes how an LLM-based reasoning process is structured: what operations are performed, in what order, and how intermediate results are combined. The framework ships with several canonical topologies, each representing a distinct reasoning strategy. These topologies are user-defined functions that construct a GraphOfOperations object by composing primitive operation types: Generate, Score, KeepBestN, Aggregate, Selector, GroundTruth, and ValidateAndImprove.

Canonical Topologies

IO (Input-Output)

IO is the simplest topology: a single Generate operation followed by GroundTruth evaluation. It represents a direct, one-shot LLM query with no intermediate reasoning steps.

# IO topology (sorting_032.py:L464-477)
def io() -> operations.GraphOfOperations:
    operations_graph = operations.GraphOfOperations()
    operations_graph.append_operation(operations.Generate(1, 1))
    operations_graph.append_operation(operations.Score(1, False, utils.num_errors))
    operations_graph.append_operation(operations.GroundTruth(utils.test_sorting))
    return operations_graph

The flow is linear: Generate(1,1) → Score → GroundTruth.

CoT (Chain of Thought)

CoT uses the same graph structure as IO (a single Generate → Score → GroundTruth chain) but differs in the prompt: the prompter provides chain-of-thought instructions that encourage the LLM to reason step-by-step within a single response. The topology itself remains a linear chain.

ToT (Tree of Thoughts)

ToT introduces branching and pruning. A Generate operation produces multiple candidate responses (e.g., 20 branches), which are then Scored and filtered by KeepBestN(1). This cycle can repeat for multiple levels, creating a tree search with pruning at each level.

# ToT topology (sorting_032.py:L496-522)
def tot() -> operations.GraphOfOperations:
    operations_graph = operations.GraphOfOperations()
    operations_graph.append_operation(operations.Generate(1, 20))
    operations_graph.append_operation(operations.Score(1, False, utils.num_errors))
    keep_best_1 = operations.KeepBestN(1, False)
    operations_graph.append_operation(keep_best_1)

    for _ in range(1):
        operations_graph.append_operation(operations.Generate(1, 20))
        operations_graph.append_operation(operations.Score(1, False, utils.num_errors))
        keep_best_2 = operations.KeepBestN(1, False)
        keep_best_2.add_predecessor(keep_best_1)
        operations_graph.append_operation(keep_best_2)
        keep_best_1 = keep_best_2

    operations_graph.append_operation(operations.KeepBestN(1, False))
    operations_graph.append_operation(operations.GroundTruth(utils.test_sorting))
    return operations_graph

The flow is: Generate(1,20) → Score → KeepBestN(1) → repeat → GroundTruth. This forms a tree structure where only the best branch survives at each level.

GoT (Graph of Thoughts)

GoT is the full graph topology. It extends ToT by introducing decomposition (via Selector) and aggregation (via Aggregate), turning the structure into a Directed Acyclic Graph (DAG). The canonical sorting example (sorting_032.py:L554-598) is the reference implementation:

A Generate operation splits the input (e.g., a list of 32 numbers) into sublists.
Selector operations route each sublist to its own parallel branch.
Each branch independently Generates candidate solutions, Scores them, and KeepBestN prunes to the best.
An Aggregate operation merges the results from all branches.
The merged result is Scored and filtered by KeepBestN.
A final Generate + Score + KeepBestN cycle refines the merged result.
GroundTruth evaluates the final answer.

This decompose-solve-merge pattern is the distinguishing feature of GoT over ToT.

Variations Across Problem Domains

Keyword counting (GoT4, GoT8, GoTx): After aggregation, a ValidateAndImprove operation is inserted to verify the correctness of the merged frequency dictionaries before scoring. The aggregation is hierarchical -- pairs of branches are merged bottom-up until a single result remains.
Document merging (GoT2): Uses hierarchical aggregation of partial document merges, where pairs of sub-document NDAs are merged at each level of the tree until a single merged NDA remains.

Usage

Use this pattern when designing a new GoT reasoning strategy. The choice of topology depends on the problem characteristics:

IO -- Suitable for simple tasks where the LLM can produce a correct answer in a single step.
CoT -- Suitable when step-by-step reasoning within a single prompt improves accuracy, but the problem does not benefit from exploring multiple solution paths.
ToT -- Suitable when exploring multiple candidate solutions and selecting the best one improves results, but the problem is not naturally decomposable.
GoT -- Suitable when the problem can be decomposed into independent subproblems, each solved separately, and the sub-solutions can be aggregated (merged) into a final answer. This is the most powerful topology and is the primary contribution of the GoT framework.

To construct a new GoT topology:

Identify how the input can be decomposed (e.g., splitting a list, splitting text into paragraphs).
Define a Generate operation to perform the decomposition via an LLM prompt.
Use Selector operations to route each sub-problem to its own branch.
Define Generate + Score + KeepBestN pipelines for each branch.
Use Aggregate to merge sub-solutions back together.
Optionally add ValidateAndImprove after aggregation for correctness checks.
Finish with Score + KeepBestN + GroundTruth to evaluate the final result.

Theoretical Basis

The Graph of Thoughts (GoT) framework, introduced in Besta et al., 2023, generalizes prior LLM reasoning paradigms:

Chain of Thought (CoT) structures reasoning as a linear chain of intermediate steps.
Tree of Thoughts (ToT) extends CoT by allowing branching at each step, forming a tree of possible reasoning paths, with pruning to select the most promising branches.
Graph of Thoughts (GoT) further generalizes by allowing aggregation (merging) of thoughts from different branches, forming a Directed Acyclic Graph (DAG) instead of a tree.

The key theoretical insight is that many problems benefit from a decompose-solve-merge strategy analogous to divide-and-conquer algorithms. GoT enables this by making aggregation a first-class operation in the reasoning graph. The paper demonstrates that GoT achieves significant improvements over ToT on tasks like sorting (where merge sort is a natural decomposition strategy), keyword counting, and document merging.

The volume of thoughts that GoT can explore scales with the structure of the graph. For a problem decomposed into k subproblems with b branches per subproblem, GoT explores O(k * b) thoughts while producing a single aggregated output, whereas ToT would need O(b^k) thoughts to cover the same solution space without decomposition.

Sources

Page Connections

Double-click a node to navigate. Hold to expand connections.

Principle

Implementation

Heuristic

Environment