Graph of Thoughts

Problem

Ask a model to sort 32 numbers that include duplicates and it will usually hand back something close: a list in order, with a number dropped or one repeated. Long, exact outputs are where single calls fail. The task itself splits naturally: sort small chunks, then merge them. But neither a single prompt nor a search tree can express “take these two partial answers and combine them”. Tree of Thoughts can branch and prune, yet every thought in a tree has exactly one parent.

How it works

Graph of Thoughts, from Besta et al., treats each intermediate result as a node in a graph and lets you wire those nodes together freely. You design the graph in advance, as a list of operations: generate a thought, score it, keep the best, merge several thoughts into one, refine a thought in place. The model fills in the thoughts; your code decides how they connect.

In the sorting example, the problem goes to a split step, plain code, that cuts the list into four chunks of 8. Each chunk becomes its own thought, and Sort 1 to Sort 4 run in parallel. Each result is scored by the same code check the scorer uses, counting errors. Chunk 2 dropped a number, so Sort 2 is generated again, and only that thought; the other three are kept.

Then the graph converges. Merge A takes two sorted chunks and asks the model to combine them into one sorted list of 16; Merge B does the same for the other two. The final merge combines the two lists of 16. This many-to-one step is what a tree cannot draw.

The scorer is plain code. It compares the merged list with the input and counts what is missing or out of order. Here one 7 went missing, so the error goes back to the final merge as a refine step: fix exactly this, change nothing else. The refined list scores zero and goes to the output.

The scores are what make it more than a split-and-join. Every thought can be checked, retried and compared before it feeds the next operation, so one bad chunk does not poison the final answer.

When to use

• The problem splits into parts whose results must be combined: sorting, set operations, merging several documents, summarising many sources into one.
• Each partial result can be scored, ideally in code: counted errors, a test, a schema check.
• A long output is unreliable in one call, but short pieces are reliable.

When to avoid

• Branching and pruning are enough, with nothing to merge. Use tree of thoughts.
• The parts are independent and need no scoring or retry. Sectioning is cheaper and simpler.
• You cannot justify many calls. Four sorts, a retry, three merges and a refine is already at least nine model calls for one list.

Trade-offs

Graph of Thoughts trades call count for accuracy on long, exact outputs. Each model call sees a small, easy piece, so quality goes up, but the number of calls grows with the size of the graph. The graph is also something you must design per task: it is not a general agent loop, and the model does not choose its own operations. In exchange the run is predictable, the operations are easy to log, and independent operations run in parallel, so latency grows with the depth of the graph, not its width.

Failure modes

• Lossy merges: the merge prompt quietly drops or duplicates items. Score every merge, not only the final result, and merge again when a merge scores badly.
• No real scorer: if a thought cannot be checked, the retries and the keep-best steps are guesses. Use a code check wherever one exists.
• Refine drift: a refine pass fixes the reported error and breaks something else. Keep the refined thought only if it scores better.
• Graph sprawl: a graph with many levels multiplies calls fast. Cap regenerations and refine passes, and count calls per run.

Implement the Graph of Thoughts pattern in this codebase, using the LLM client and language we already use.

## Goal

Solve a task that splits into sub-results by running a fixed graph of model operations (generate, score, merge, refine) over partial thoughts, and return the best final thought.

## How it works

1. Write the graph of operations in code before any model call: which thoughts are generated, how each is scored, which ones are merged together, and where refinement happens. The model fills in thoughts; it never changes the graph.
2. Split the input into parts. Do it in code when the split is mechanical, as for a list of numbers or a set of documents.
3. For each part, call the model with the Part prompt to produce a thought, and score it with a check (in code where possible, such as counting sorting errors). If the score is below the bar, generate it again and keep the best attempt.
4. Merge thoughts as the graph says, two at a time, by calling the model with the Merge prompt. Score each merged thought the same way; if it has errors, merge again and keep the best (default 1 extra attempt).
5. Score the final merged thought. While it still has errors, call the model with the Refine prompt, passing the thought and the errors found, and keep the refined version only if it scores better.
6. Return the best final thought with its score.

## Prompts

### Part prompt

```markdown
Solve this part of a larger task. Work only on the part below.

<task>{{task}}</task>
<part>{{part}}</part>

{{#if previous_errors}}
A previous attempt at this part had these errors. Avoid them:
<errors>{{previous_errors}}</errors>
{{/if}}

Return only the result for this part, in the format: {{format}}
```

### Merge prompt

```markdown
Combine the two partial results below into one result for the task.
Keep everything that is correct in each; do not drop or duplicate items.

<task>{{task}}</task>
<a>{{result_a}}</a>
<b>{{result_b}}</b>

Return only the merged result, in the format: {{format}}
```

### Refine prompt

```markdown
The result below is close, but a check found errors in it.

<task>{{task}}</task>
<result>{{result}}</result>
<errors>{{errors}}</errors>

Fix exactly these errors and change nothing else.
Return only the corrected result, in the format: {{format}}
```

## Stop rule

Stop when the final thought scores perfectly, or after 2 refine passes. If the budget runs out, return the best-scoring final thought with its remaining errors and a status saying it is not clean.

## Requirements

- Keep the graph of operations as data (a list of operations and their inputs), so it can be logged and changed without touching the model calls.
- Cap regenerations per thought (default 2), extra merge attempts per pair (default 1) and refine passes (default 2); log the total number of model calls.
- Prefer a scoring function in code over a model judgement whenever the task allows one; fall back to a model score only for parts that code cannot check.
- Run independent operations, such as the per-part thoughts and the merges at one level, in parallel.
- Add a test with a stub LLM that drops one number from the second chunk on its first try and is correct afterwards; assert the solve prompt was called 5 times for 4 chunks and the output equals the input sorted.

Solve this part of a larger task. Work only on the part below.

<task>{{task}}</task>
<part>{{part}}</part>

{{#if previous_errors}}
A previous attempt at this part had these errors. Avoid them:
<errors>{{previous_errors}}</errors>
{{/if}}

Return only the result for this part, in the format: {{format}}

Combine the two partial results below into one result for the task.
Keep everything that is correct in each; do not drop or duplicate items.

<task>{{task}}</task>
<a>{{result_a}}</a>
<b>{{result_b}}</b>

Return only the merged result, in the format: {{format}}

The result below is close, but a check found errors in it.

<task>{{task}}</task>
<result>{{result}}</result>
<errors>{{errors}}</errors>

Fix exactly these errors and change nothing else.
Return only the corrected result, in the format: {{format}}