Tree-of-thoughts and graph-reasoning: search trees in prompt structures

Classic autoregressive language models generate text from left to right, token by token. When a model solves a complex puzzle, mathematical proof, or strategic planning problem via a standard prompt, it is locked into the linear path it starts writing itself. If the model makes a logical thinking error in step two, the attention mechanism forces the following tokens to build on that earlier mistake. After all, the model cannot 'rewind' on its own or explore multiple alternative routes in parallel.

To break this fundamental limitation of linear generation, search-tree and graph structures have been developed. Instead of one continuous chain of thought, methods such as Tree-of-Thoughts (ToT) and Graph-of-Thoughts (GoT) split the problem into discrete partial thoughts (thought states). Combining these states with classic search algorithms such as tree search and graph transformations creates a form of deliberative planning. In this dossier we go through how these architectures work, how evaluation steps function, and how you decide whether the computational cost of search trees outweighs the gain in reliability.

The linear pitfall of Chain-of-Thought

In classic chain reasoning (Chain-of-Thought or CoT), the model produces a sequence of intermediate steps. This significantly improves performance on arithmetic and logical tasks compared to direct question-answer prompts. The fundamental weak point, however, remains the greedy commitment: each generated intermediate step immediately becomes part of the fixed context for all subsequent steps.

As soon as a model makes a calculation error or heads down a dead end in a cryptic riddle or puzzle (such as the well-known Game of 24 or planning a logistics route with strict constraints), it has no formal mechanism within CoT to detect that error and choose an alternative line of thinking. Instead, the model will try to 'smooth over' the mistake it made or hallucinate its way to an incorrect conclusion. Even techniques such as Self-Consistency — where we generate multiple independent CoT paths and apply majority voting — only partially solve this problem. If the probability that a model reaches the correct answer in one straight line is small, a majority vote over ten failed linear attempts still produces a wrong answer.

Tree-of-Thoughts: the four pillars of search trees

Tree-of-Thoughts formalizes the reasoning process as a search over a directed tree. The root of the tree is the initial problem, each intermediate node represents a partial solution or intermediate step (a thought), and the leaves are final solutions. A ToT framework rests on four distinct components that are directed by an external orchestration script or an agentic loop.

First, there is the problem decomposition: how big is one thought? A thought must be meaningful enough to be evaluated autonomously, but small enough to generate alternatives for (for example, one intermediate calculation, a paragraph plan, or a chess move). Second, there is the thought generator, which generates new candidate thoughts from an existing state $k$ via prompts. Third, the state evaluator assesses the quality of each node via scoring or classification. Fourth, the search algorithm (such as Breadth-First Search or Depth-First Search) determines which branches are explored further, when backtracking occurs, and which paths are pruned.

Wortel: Vraagstuk (Starttoestand)
  ├── Gedachte A1 [Score: 0.85] -> Levensvatbaar pad
  │     ├── Gedachte B1 [Score: 0.95] -> Finale Oplossing (Gevalideerd)
  │     └── Gedachte B2 [Score: 0.20] -> Gesnoeid (Pruning)
  └── Gedachte A2 [Score: 0.30] -> Doodlopend pad (Backtracking)

Search algorithms in action: BFS, DFS, and Monte Carlo Tree Search

The choice of search algorithm determines the behavior and memory usage of the reasoning loop. With Breadth-First Search (BFS) the system explores all possible thoughts at a given depth simultaneously. This is particularly effective when the total depth of the reasoning tree is limited (for example, 3 to 4 steps) and we want to keep only the $b$ best-scoring candidates at each level (a beam search over thoughts). BFS prevents the model from getting deeply lost in one incorrect line of reasoning, but requires many parallel calls per layer.

In Depth-First Search (DFS) the model dives directly as deep as possible into one branch until a final solution is reached or until the state evaluator determines that the branch has become unviable (a score below the threshold value). As soon as a branch fails, the algorithm returns to the previous node (backtracking) and chooses the next candidate. This closely mimics human problem-solving behavior in tasks such as solving sudokus or debugging software. For extremely large search spaces, Monte Carlo Tree Search (MCTS) can be deployed, where rollouts and statistical upper confidence bounds (UCT) are used to balance deepening proven strong branches against exploring uncertain ones.

The State Evaluator: how does an LLM evaluate intermediate steps?

The most critical part of tree and graph reasoning is the evaluation function. Without a reliable method for determining whether an intermediate step is getting closer to the goal, the search degenerates into a random enumeration. In practice, three primary evaluation strategies are used.

The first method is value classification via prompts. Here, the model receives a prompt with the current partial solution and is asked to classify it as certainly feasible, possibly feasible or impossible. The second method is numerical scoring (value scoring), in which the model assigns a score between 1 and 10 to the intermediate step based on explicit criteria. The third and most robust method is programmatic validation: when the domain rules are formal (such as with SQL queries, code syntax validation, or mathematical calculation rules), a deterministic compiler or runtime environment evaluates the node. This completely eliminates hallucinations in the evaluation phase.

Graph-of-Thoughts: beyond the hierarchical tree

Although Tree-of-Thoughts is a significant step forward compared to linear chains, a tree structure enforces a strict hierarchy: branches can split, but they never merge back together. In complex reasoning processes, however, it is often desirable to combine insights from two independent lines of thought (synthesis), or to iteratively refine an earlier thought without starting a completely new branch.

Graph-of-Thoughts (GoT) models the thinking process as a directed graph (Directed Acyclic Graph or DAG). This enables operations that are not feasible in a standard tree. We distinguish three specific graph transformations: aggregation (combining node A and node B into a new synthesis node C), refinement (cyclically updating the state of a node based on feedback), and splitting (decomposing a task into subproblems in parallel). GoT proves particularly powerful for tasks such as writing complex documents based on multiple sources or designing system architectures where different constraints must come together simultaneously.

Practical example: logistics planning with Tree-of-Thoughts

Let's look at a concrete Dutch case: planning a delivery route for a transport company with three electric delivery vans from a distribution center in Utrecht to five cities (Alkmaar, Arnhem, Breda, Groningen, and Maastricht), taking into account range, charging times, and delivery time windows.

With standard Chain-of-Thought, a model will write out an order directly. When it discovers at the fourth city that van 1's range is exceeded, it can no longer move the earlier cities and an invalid plan results. Within a Tree-of-Thoughts structure, the orchestration script splits the task into layers. Layer 1 generates three possible vehicle-to-city assignments. A deterministic script immediately validates the mileage. Branch 1 exceeds the range and is labeled impossible (pruning). Branches 2 and 3 are feasible and are expanded to layer 2 (charging time planning). The model then only explores the viable routes further, so that the final combined route plan is guaranteed to meet all hard constraints.

// Vereenvoudigde JSON-representatie van een ToT-stap
{
  "node_id": "route_utrecht_alkmaar_v1",
  "parent_id": "root_dc_utrecht",
  "thought_content": "Voertuig 1 vertrekt 08:00 naar Alkmaar (afstand: 78km, acculading rest: 74%)",
  "state_evaluation": {
    "deterministic_check": "PASS",
    "battery_feasible": true,
    "time_window_feasible": true,
    "score": 0.92
  },
  "status": "EXPAND"
}

Computing power and the trade-off: when does search-tree prompting pay off?

Using Tree-of-Thoughts and Graph-of-Thoughts entails significant computational costs. Where a standard prompt requires one LLM call and Chain-of-Thought requires one longer generation, a ToT search with branching factor $b=3$ and depth $d=4$ can cause dozens to hundreds of separate calls. This leads to a corresponding increase in token consumption and processing time (latency).

To determine whether a search structure is justified, we look at the complexity and error tolerance of the task. For routine text transformations, simple summaries, or open conversations, ToT is major overkill. For tasks with a combinatorial search space, hard constraints, or an asymmetric verification cost (where an intermediate solution is difficult to come up with but extremely fast to check), ToT delivers a gain in reliability that is unattainable with linear prompting.

ToT versus native test-time compute reasoning models

Since the introduction of specialized reasoning models (such as OpenAI o1, o3, and comparable open-weights architectures), the landscape around reasoning structures has changed significantly. These models already perform a form of search behavior, self-correction, and chain exploration internally during the generation phase (test-time compute). For how these internal mechanisms work, see the article on how reasoning models set up thinking as a separate step.

The question then arises: does native test-time compute make external ToT frameworks redundant? The answer is nuanced. Internal reasoning models are more compact, faster, and do not require complex external orchestration software. External ToT and GoT frameworks, however, retain two decisive advantages. First, they offer full control over the search tree: developers can inject their own deterministic evaluators and external databases directly into the nodes. Second, external frameworks provide full auditability: every individual thought and evaluation score is transparently visible and can be logged for quality assurance.

When evaluating such systems in production, traditional text benchmarks are no longer sufficient; see also the dossier on how you evaluate agentic systems and complex decision trajectories for reliability and task success.