Graph of thoughts prompting: a complete guide

Chain-of-Thought reasons in a straight line and Tree of Thoughts branches out, but neither can ever pull two ideas back together. Graph of Thoughts (GoT) fixes that: it models reasoning as an arbitrary graph where thoughts are vertices and dependencies are edges, so branches can merge, loops can refine, and late insights can feed early steps. On sorting tasks the original paper reports 62% higher quality than Tree of Thoughts at over 31% lower cost (Besta et al., AAAI 2024).

The flip is simple. Stop forcing reasoning into a line or a tree, and let it be a graph that can split a problem apart and then synthesize the pieces back into one answer.

See it work

Take sorting a 64-element list. Tree of Thoughts can spawn several attempts, but each branch is a separate guess and there's no way to combine the good parts of two near-misses.

Problem: Sort [38, 27, 43, 3, 9, 82, 10, ... 64 numbers total]

Tree of Thoughts:
  Branch A → sorts most of it, two elements out of place
  Branch B → sorts a different chunk well, drops one element
  → picks the single best branch. The other branch's good work is thrown away.

Graph of Thoughts:
  Decompose → [chunk 1] [chunk 2] [chunk 3] [chunk 4]
  Solve     → sort each chunk independently (in parallel)
  Score     → count inversions in each sorted chunk
  Aggregate → merge sorted chunks pairwise into one list
  Refine    → fix any remaining out-of-order pairs
  → a fully sorted list built from every branch's best work.

The win is the Aggregate step. Where ToT throws away every branch but one, GoT merges them — exactly the move that makes merge sort work, now available to an LLM.

The mental model

Chain-of-Thought is a to-do list. Tree of Thoughts is a brainstorm with options. Graph of Thoughts is a whiteboard team that splits the work, then combines what everyone found.

Think of how a group tackles a hard report. You divide it into sections, people draft in parallel, you review each draft, then someone merges them into one coherent document — and you do another pass to smooth the seams. That merge-and-refine motion is impossible in a line or a tree. GoT makes it a first-class operation.

How it works

GoT runs a controller that walks a predefined Graph of Operations (GoO), applying transformations to a growing graph until a stopping point. The reasoning state (the Graph Reasoning State, or GRS) tracks every vertex and edge, so the whole trace is inspectable.

1. Initialize. The problem becomes the root vertex. The controller loads the GoO and sets up the GRS.
2. Generate. The Prompter turns source vertices into a prompt; the LLM produces new thoughts; the Parser extracts them into new vertices with edges from their sources.
3. Score. The Scorer rates each new thought — via LLM judgment, a heuristic, or an external validator.
4. Transform. The controller applies the next operation: Generate, Aggregate, Refine, Score, or GroundTruth.
5. Iterate. Steps 2-4 repeat per the GoO, with the GRS holding the full history.
6. Terminate. When the GoO is exhausted, the best-scoring leaf vertices are returned, with the complete graph available for analysis.

Formally GoT is a tuple (G, T, E, R): the reasoning graph G, the set of thought transformations T, an evaluation function E that scores thoughts, and a ranking function R that orders them by quality. The payoff the authors emphasize is "synergistic outcomes" — a merged thought worth more than its parts. Separating strategy (the GoO) from execution (the controller) means one piece of infrastructure can run many different reasoning patterns.

The thought transformations

• Generate creates new vertices from existing ones — the primary way reasoning extends.
• Aggregate combines multiple vertices into one, synthesizing parallel paths. This is GoT's signature move; CoT and ToT can't do it.
• Refine improves a vertex in place, modeled as a self-loop edge — iterative enhancement of one thought.
• Score rates a vertex without changing structure; scores feed ranking and pruning.
• GroundTruth validates against known answers, for evaluation and debugging rather than production.

Why it works

Four mechanisms drive the gains, with the paper's authors and follow-up analysis pointing to decomposition as dominant:

Underneath, GoT leans on well-known cognitive principles: chunking (Miller, 1956), divide-and-conquer, synthesis (Bloom's taxonomy), iterative refinement, distributed cognition (Hutchins, 1995), analogical reasoning (Gentner, 1983), and metacognition via scoring (Flavell, 1979). The graph also externalizes working memory — the model references vertex content explicitly instead of juggling state in one pass.

Where it shines

GoT pays off on problems that decompose into semi-independent parts and then need those parts synthesized back together. The original paper (Besta et al., ETH Zurich, AAAI 2024, vol. 38, pp. 17682-17690) evaluated four tasks:

• Sorting (32 and 64 elements). The canonical case, mirroring merge sort. GoT hit 62% higher quality than ToT, with over 31% lower cost. On 64-element sorting its median error was roughly 65% lower than CoT and 83% lower than input-output (IO) prompting.
• Set operations (intersection, union). GoT consistently beat baselines, and its advantage grew with problem complexity.
• Keyword counting. GoT held accuracy on larger inputs where CoT degraded.
• Document merging. Aggregation maps naturally onto merge semantics, improving quality over sequential approaches.

The headline structural result: GoT achieves logarithmic latency with linear volume — the best cost-quality tradeoff among CoT, ToT, and self-consistency variants. It costs more per query than IO or CoT (multiple calls) but beats ToT on cost-efficiency because aggregation prunes redundant exploration.

Beyond the paper, the same decompose-then-synthesize shape fits multi-constraint optimization, planning and scheduling, code generation (components with clear interfaces), and multi-step proofs (lemmas merged into a whole). Domain teams apply it to literature synthesis and systematic reviews, multi-precedent legal analysis, differential diagnosis across symptom clusters, portfolio optimization across asset classes, and software architecture where component designs must stay interface-compatible.

When to use it (and when not)

Reach for GoT when the problem naturally decomposes and recomposes, single-prompt approaches fail at scale, clear aggregation semantics exist for combining partial solutions, multiple LLM calls are acceptable, and quality justifies the spend.

Skip it when simple problems yield to zero-shot or CoT, latency constraints prohibit multiple calls (no natural decomposition), or ToT already explores enough. Escalate to alternatives when GoT plateaus despite tuning (consider fine-tuning), decomposition doesn't improve quality (the problem may be monolithic), or scoring proves unreliable (aggregation quality depends on it).

Model fit: the minimum is a solid instruction-tuned model (GPT-3.5-Turbo, Claude 3 Haiku, Llama 70B-Instruct); recommended is GPT-4, Claude 3.5 Sonnet, or Llama 405B; optimal for hard reasoning is GPT-4o, Claude 3.5 Sonnet, or o1. Base models, anything under 7B parameters, or context windows under 4K tokens aren't suitable — weak instruction-following breaks decomposition and aggregation.

Structure and components

A complete GoT implementation needs four modules:

• Controller — orchestrates everything; holds the GoO (transformation sequence) and GRS (current graph). Required.
• Prompter — turns graph state into prompts for each operation. Required.
• Parser — extracts structured vertex content from raw LLM output, handling format variation. Required.
• Scorer — evaluates thought quality (LLM, heuristic, or external validator). Required for quality-guided exploration; optional for exhaustive approaches.

A GroundTruth validator is optional, useful in development and evaluation. The guiding design principles: model the problem as vertices and edges, keep transformations composable, separate strategy from execution, keep the GRS fully inspectable, and let scoring prune low-quality paths.

The core algorithm

The essence of GoT in one pattern — decompose, solve in parallel, score, then aggregate the good ones:

import openai
from concurrent.futures import ThreadPoolExecutor

client = openai.OpenAI()

def generate(prompt, temperature=0.7):
    r = client.chat.completions.create(
        model="gpt-4",
        messages=[{"role": "user", "content": prompt}],
        temperature=temperature,
    )
    return r.choices[0].message.content

def got_solve(problem):
    # 1. Decompose
    subproblems = parse_list(generate(
        f"Split this problem into 4 independent subproblems:\n{problem}"))

    # 2. Solve in parallel
    with ThreadPoolExecutor(max_workers=4) as ex:
        solutions = list(ex.map(lambda sp: generate(f"Solve: {sp}"), subproblems))

    # 3. Score, then keep the strong ones
    scores = [score_solution(s) for s in solutions]
    good = [s for s, sc in zip(solutions, scores) if sc > 0.7]

    # 4. Aggregate into one answer
    return generate("Combine these partial solutions into a complete answer:\n"
                    + "\n".join(good))

The official library makes the same flow declarative — you append operations to a Graph of Operations and let the controller run it:

from graph_of_thoughts import controller, language_models, operations

lm = language_models.ChatGPT("config.json", model_name="gpt-4")

gop = operations.GraphOfOperations()
gop.append_operation(operations.Generate(num_branches=4))
gop.append_operation(operations.Score(scoring_function=evaluate_solution))
gop.append_operation(operations.Aggregate(num_responses=1))
gop.append_operation(operations.GroundTruth(validation_function))

ctrl = controller.Controller(
    lm=lm, graph_of_operations=gop,
    prompter=CustomPrompter(), parser=CustomParser(),
    initial_state={"problem": problem_input},
)
ctrl.run()
result = ctrl.get_final_thoughts()

Prompt templates

The four operations map to four prompt shapes. Keep them explicit and consistent across every vertex:

DECOMPOSE: "Break [problem] into N independent subproblems. Each must be
            solvable on its own; together they must solve the original.
            Keep them roughly equal in complexity and include needed context."

SOLVE:     "Solve only this subproblem: [subproblem]. Original problem for
            context: [problem]. State assumptions and interface points."

AGGREGATE: "Synthesize these partial solutions into one coherent answer:
            [solutions]. Integrate (don't concatenate), resolve conflicts,
            preserve key details from each source. Prefer higher-scored ones."

SCORE:     "Rate this solution 1-10 on correctness, completeness, and clarity:
            [solution]. Give a brief justification."

Implementation

A typical path from idea to production:

1. Analyze. Find natural decomposition points, decide aggregation semantics, define quality metrics, estimate depth and branching.
2. Design the GoO. Specify the transformation sequence and the decomposition, aggregation, and scoring prompts; plan verification checkpoints.
3. Build components. Implement Prompter templates, a Parser for your output format, a Scorer, and wire the Controller; add per-component error handling.
4. Test. Validate on cases with known answers; confirm decomposition is meaningful, aggregation preserves information, and scoring tracks real quality.
5. Optimize. Adjust granularity, tune aggregation prompts, calibrate score thresholds, parallelize independent branches.
6. Deploy and maintain. Add monitoring, fallbacks, and gradual rollout; re-validate on model updates.

Configuration

Different operations want different temperatures — diverge early, converge late:

EGoT pushes this further with dynamic temperature: start at 1.0 at the root and apply cosine annealing as depth increases, so high-scoring nodes exploit (lower temp) while low-scoring ones keep exploring (higher temp). Use consistent delimiters (###, \n\n) so the Parser stays reliable.

Do and don't

Do: make subproblems roughly equal and genuinely independent; specify clear interfaces; carry enough context for standalone solution; tell the aggregator how to resolve conflicts; score on objective, measurable criteria.

Don't: over-decompose simple problems; allow hidden dependencies between subproblems; let aggregation just concatenate or introduce content not in the sources; rely solely on LLM self-evaluation; use the same temperature everywhere.

Debugging

Testing and validation

Reserve 20-30% of cases as a holdout you never optimize against. Test each component in isolation (does the Prompter elicit the intended operation? does the Parser survive format variation? does the Scorer correlate with ground truth?) before end-to-end runs. A workable coverage split is 60% happy path, 25% boundary cases (minimum and maximum decomposition, single-element subproblems), and 15% adversarial (hidden dependencies, parser-breaking output).

Measure both task quality (sorting: inversion count; set ops: precision/recall/F1; merging: information preservation) and GoT-specific health: decomposition independence, aggregation fidelity, and scoring accuracy (Spearman correlation with ground truth). Because outputs are stochastic, run each configuration 5-10 times and report mean and variance.

# A/B test two decomposition prompts, then test for significance
from scipy import stats
import numpy as np

variants = {
    "A": "Split this problem into 4 independent parts:",
    "B": "Identify the components that must be addressed separately:",
}
results = {}
for name, prompt in variants.items():
    scores = [evaluate_quality(run_got(p, prompt), ground_truth[p])
              for p in test_problems]
    results[name] = {"mean": np.mean(scores), "std": np.std(scores), "scores": scores}

t_stat, p_value = stats.ttest_ind(results["A"]["scores"], results["B"]["scores"])

For statistical comparison, a paired t-test fits same-problem variants, Wilcoxon signed-rank handles non-normal data, bootstrap intervals suit small samples, and Cohen's d reports effect size. For human evaluation of subjective dimensions, sample 50-100 outputs stratified by difficulty, use 3+ raters, and report inter-rater agreement (Fleiss' kappa). Stop optimizing when gains drop below 1% per iteration or you've cleared the quality target.

Limitations

• Cost and latency are inherent. The multi-call nature can't be optimized away; sub-second responses are essentially impossible.
• Decomposition-dependent. Problems without natural structure gain nothing and just pay the overhead.
• Scoring reliability bounds everything. Unreliable scores send the controller down bad paths; LLM scoring is prone to systematic bias.
• Aggregation loses information. Synthesis compresses, so details can drop, especially when merging many sources.
• Errors compound. A bad decomposition poisons every downstream vertex; cascade amplification is a systemic risk.

Some problems are actively worse in GoT than a simpler method: simple classification (zero-shot or few-shot), short generation (direct prompting), factual Q&A (RAG), style-matching (few-shot — decomposition disrupts coherence), real-time apps, highly subjective tasks (scoring is unreliable), and tightly coupled problems (use CoT or ToT). Watch the edge cases too: single-element decomposition (short-circuit it), circular hidden dependencies, scoring ties, and empty subproblems the Parser must skip.

Advanced techniques

In deep graphs, context outgrows the window — summarize history past a depth threshold, filter to relevant context, and prioritize current subproblem, parent, siblings, then original problem. Insert verification stages after decomposition ("are these subproblems sufficient?") and aggregation ("does this preserve essential content?"). For format-critical work, specify the schema in every prompt, validate in the Parser, and add a repair stage. Maintaining style across a deep graph needs explicit style instructions in every vertex prompt, not just the root, plus style checks in scoring — style drifts and aggregation tends to homogenize distinctive voices.

Useful hybrids: GoT + self-consistency (run several GoT executions and aggregate across them), GoT + verification (a final pass that triggers refinement on failure), and GoT + multi-agent (specialist decomposer, solver, and aggregator agents). On models, route the strongest one to aggregation (quality-critical) and cheaper models to independent subproblems, and write model-agnostic prompts — explicit instructions over assumptions like "use your chain-of-thought."

Ecosystem

The official implementation lives at github.com/spcl/graph-of-thoughts (pip install graph_of_thoughts, Python 3.8+) with modular operations and multiple LLM backends. LangChain/LangGraph has Tree of Thoughts but needs a custom build for GoT (StateGraph can model the structure); DSPy can implement GoT patterns and optimize the component prompts but has no native support. Microsoft PromptBench helps with general LLM evaluation.

GoT generalizes both predecessors — Chain-of-Thought (Wei et al., 2022) is a linear graph, Tree of Thoughts (Yao et al., 2023) a graph without aggregation. To migrate from CoT, make implicit steps explicit as vertices and add branching plus aggregation where synthesis helps. From ToT, keep the tree and add aggregation at merge points and refinement loops. If GoT patterns stabilize, you can collect successful traces and fine-tune to cut runtime cost while preserving quality. It also slots into larger systems: RAG (retrieved documents become input vertices), agents (GoT handles complex reasoning steps), and pipelines (analysis stage between pre- and post-processing).

Building on GoT

Follow-up research extends the core idea. EGoT (ICLR 2025) adds the cosine-annealing temperature schedule above and, on sorting 256 elements with GPT-4o mini, reached 88.31% accuracy versus standard GoT's 84.37%. MindMap (ACL 2024) feeds knowledge-graph inputs into GoT-style reasoning. CRP-RAG integrates reasoning graphs with retrieval to guide knowledge use on complex tasks. Open frontiers include adaptive graph construction (deciding topology from problem features), learned and neural aggregation, and multi-modal GoT where vertices hold images, code, or structured data.

Summary

• Graph of Thoughts models reasoning as a graph — thoughts are vertices, dependencies are edges — so branches can merge, loops can refine, and any thought can inform any other.
• The signature operation is Aggregate: synthesizing multiple thoughts into one, which CoT (linear) and ToT (tree) cannot do.
• Headline results (Besta et al., AAAI 2024): 62% higher quality than ToT at over 31% lower cost on sorting, with logarithmic latency and linear volume.
• Effectiveness is driven mostly by decomposition (40%) and aggregation (25%), then scoring, refinement, and topology.
• It costs 3-20x a single CoT call (5-50 LLM calls, 5-60s) — use it only when quality justifies the spend and the problem genuinely decomposes.
• Reach for it on decompose-then-synthesize problems (sorting, set operations, document merging, multi-source synthesis); skip it for simple, latency-critical, or monolithic tasks.
• Watch for synthesis hallucination, scoring bias, and cascading errors; verify aggregated output against its sources.