Heuristic:Spcl Graph of thoughts GoT Decompose Sort Merge Strategy
| Knowledge Sources | |
|---|---|
| Domains | LLM_Reasoning, Optimization |
| Last Updated | 2026-02-14 03:30 GMT |
Overview
Problem decomposition strategy that splits input into sublists, processes each independently with LLM + scoring, then merges results — enabling better accuracy than direct prompting.
Description
The Graph of Thoughts (GoT) approach implements a divide-and-conquer strategy for LLM-based problem solving. Instead of asking the LLM to solve the entire problem at once (IO approach) or using a single chain of reasoning (CoT), GoT decomposes the problem into smaller sub-problems, solves each independently with multiple candidate solutions scored by a heuristic function, selects the best candidate per sub-problem, then merges the sub-solutions. This mirrors the merge-sort algorithm: split the input in half, sort each half, then merge. The key insight is that LLMs solve smaller problems more reliably, and the scoring + selection step filters out bad solutions before they propagate.
Usage
Use this heuristic when designing Graph of Operations topologies for problems that can be decomposed into independent sub-problems. It is particularly effective for:
- Sorting: Split list into sublists, sort each, merge sorted sublists
- Keyword counting: Split text into passages, count in each, aggregate counts
- Document merging: Split documents into sections, process each, combine
The pattern works best when sub-problem solutions can be mechanically verified or scored.
The Insight (Rule of Thumb)
- Action: Structure the GoO as: Generate(split) → Selector(per-sublist) → Generate(solve, k=5) → Score → KeepBestN(1) → Aggregate(merge) → Score → KeepBestN(1) → Generate(refine) → Score → KeepBestN(1).
- Value: Use k=5 candidate solutions per sub-problem with `KeepBestN(1, higher_is_better=False)` for error-count scoring.
- Trade-off: More API calls (higher cost) but significantly higher accuracy. The GoT sorting approach uses ~10-15x more tokens than IO but achieves much lower error rates.
- Refinement step: After merging, apply an improvement step using the ToT-style "fix the incorrectly sorted list" prompt.
Reasoning
LLMs struggle with long-context problems (e.g., sorting 32 numbers at once) but handle smaller instances well (e.g., sorting 16 numbers). By decomposing the problem:
- Each sub-problem is within the LLM's reliable capability range
- Multiple candidates (k=5) provide diversity, and the scoring function selects the best
- The merge step combines verified sub-solutions, reducing error propagation
- A final refinement step catches any merge errors
The approach is inspired by merge-sort's O(n log n) decomposition and generalizes to any problem where the solution can be split, solved independently, and recombined.
Code Evidence
GoT topology construction from `examples/sorting/sorting_032.py:554-598`:
def got() -> operations.GraphOfOperations:
operations_graph = operations.GraphOfOperations()
plans = operations.Generate(1, 1)
operations_graph.append_operation(plans) # generate the sublists
for i in range(1, 3):
list_id = f"List {i}"
sub_list = operations.Selector(
lambda thoughts, list_id=list_id: [
thought for thought in thoughts if thought.state["part"] == list_id
]
)
sub_list.add_predecessor(plans)
operations_graph.add_operation(sub_list)
sort_sub_list = operations.Generate(1, 5)
sort_sub_list.add_predecessor(sub_list)
operations_graph.add_operation(sort_sub_list)
score_sub_list = operations.Score(1, False, utils.num_errors)
score_sub_list.add_predecessor(sort_sub_list)
operations_graph.add_operation(score_sub_list)
keep_best_sub_list = operations.KeepBestN(1, False)
keep_best_sub_list.add_predecessor(score_sub_list)
operations_graph.add_operation(keep_best_sub_list)
final_aggregate = operations.Aggregate(10)
operations_graph.append_operation(final_aggregate)
Split prompt design from `examples/sorting/sorting_032.py:121-137`:
got_split_prompt = """<Instruction> Split the following list of 32 numbers into 2 lists of 16 numbers each, the first list should contain the first 16 numbers and the second list the second 16 numbers.
Only output the final 2 lists in the following format without any additional text or thoughts!:
{{
"List 1": [3, 4, 3, 5, 7, 8, 1, ...],
"List 2": [2, 9, 2, 4, 7, 1, 5, ...]
}} </Instruction>