# Tree-of-Thought Reasoning

URL: https://cogitator.app/docs/advanced/reasoning

> Explore several approaches to a problem with the ThoughtTreeExecutor, score branches, prune weak ones and return the best reasoning path.

## Overview

Tree-of-Thought (ToT) reasoning lets an agent explore several approaches to a problem, score each one, drop the weak ones and keep the best result. Instead of committing to a single chain of thought, the `ThoughtTreeExecutor` builds a tree of candidate approaches and runs the promising ones as ordinary agent runs.

This page is about that executor. A model's own built-in thinking (OpenAI reasoning effort, Claude extended thinking, Gemini thinking budgets) is set with the `reasoning` option of an agent or a run — see [Reasoning](/docs/core/llm-backends#reasoning) under LLM backends. The two combine: the runs inside a tree use the agent's `reasoning` setting like any other run.

## Basic Usage

```typescript
import { Agent, Cogitator, ThoughtTreeExecutor } from '@cogitator-ai/core';

const cogitator = new Cogitator({
  llm: {
    defaultProvider: 'openai',
    providers: { openai: { apiKey: process.env.OPENAI_API_KEY! } },
  },
});

const executor = new ThoughtTreeExecutor(cogitator, {
  maxDepth: 4,
  branchFactor: 3,
  beamWidth: 2,
  confidenceThreshold: 0.3,
  terminationConfidence: 0.9,
  maxTotalNodes: 50,
});

const agent = new Agent({
  name: 'problem-solver',
  instructions: 'You solve complex problems by exploring multiple approaches.',
  model: 'openai/gpt-5.5',
});

const result = await executor.explore(agent, 'Design a caching strategy for a real-time dashboard');

console.log('Success:', result.success);
console.log('Output:', result.output);
console.log('Best path depth:', result.bestPath.length);
console.log('Nodes explored:', result.stats.exploredNodes);
```

The executor makes its own model calls — branch generation, branch evaluation and the final synthesis — on the agent's model, routed like a normal run: a `provider/model` id, a bare name served by `llm.defaultProvider` and `agent.config.provider` all work.

## How It Works

1. **Root** — the goal becomes the root node.
2. **Branch generation** — the `BranchGenerator` asks the model for `branchFactor` candidate approaches for the node, each a `thought` with a proposed action: a tool call, a sub-goal or a direct response.
3. **Branch evaluation** — the `BranchEvaluator` scores every candidate on confidence, progress and novelty, combined into a `composite` score.
4. **Pruning** — candidates with a composite score below `confidenceThreshold` are dropped. Every other candidate becomes a pending child node.
5. **Queueing** — the `beamWidth` best children are queued for execution; the rest wait as alternatives for backtracking.
6. **Execution** — a direct response is taken as is; a tool call or sub-goal runs the agent with `cogitator.run()` (without memory) on a prompt built from the goal and the approach. A completed node below `maxDepth` is queued again to be expanded; a failed one backtracks.
7. **Termination** — exploration stops as soon as an executed node's branch confidence reaches `terminationConfidence`, or when the frontier is empty, `maxTotalNodes` nodes have been executed, the `timeout` passes or the abort signal fires.
8. **Result** — the completed node with the highest cumulative score (the sum of composite scores along its path) wins. Its answer is the output; without one, the path is synthesized into a final answer with one more model call.

### Exploration Strategies

`explorationStrategy` decides which queued node runs next:

| Strategy         | Order                                                                                                                                                                        |
| ---------------- | ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| `beam` (default) | Level by level: the shallowest node first, pending nodes before completed ones at the same depth, then by cumulative score. A whole level runs before the next is generated. |
| `best-first`     | The node whose own branch has the highest composite score.                                                                                                                   |
| `dfs`            | Last in, first out, with the best child of the latest expansion on top, so the search goes deep before it goes wide.                                                         |

## Configuration

```typescript
const executor = new ThoughtTreeExecutor(cogitator, {
  maxDepth: 5, // how deep the tree can grow (default 5)
  branchFactor: 3, // candidates generated per node (default 3)
  beamWidth: 2, // best candidates queued per expanded node (default 2)
  explorationStrategy: 'beam', // 'beam' | 'best-first' | 'dfs' (default 'beam')
  confidenceThreshold: 0.3, // minimum composite score to keep a candidate (default 0.3)
  terminationConfidence: 0.8, // branch confidence that stops the search (default 0.8)
  maxTotalNodes: 50, // hard cap on executed nodes (default 50)
  maxIterationsPerBranch: 3, // iteration cap for each branch run (default 3)
  timeout: 60_000, // ms per explore() call (no limit by default)
});
```

`maxIterationsPerBranch` caps the iterations of each branch's `cogitator.run()`; it never raises the cap above the agent's own `maxIterations`. `timeout` is the default time limit of every `explore()` call; `explore(agent, goal, { timeout })` overrides it for one call (see [Progress Monitoring](#progress-monitoring)).

Higher `branchFactor` explores more possibilities but costs more tokens. Lower `beamWidth` focuses the search but risks missing good paths. `DEFAULT_TOT_CONFIG` holds the defaults.

## Callbacks

```typescript
const executor = new ThoughtTreeExecutor(cogitator, {
  onBranchGenerated: (node, branches) =>
    console.log(`${branches.length} ideas at depth ${node.depth}`),
  onBranchEvaluated: (branch, score) => console.log(branch.thought, score.composite),
  onNodeExplored: (node) => console.log(node.status, node.result?.response),
  onBacktrack: (from, to) => console.log(`Dead end at depth ${from.depth}`, to?.depth ?? 'none'),
});
```

`onBacktrack` fires when every candidate of a node scores below the threshold, or when running a node fails; the node is marked `failed`. `to` is the best deferred alternative — a pending sibling, or a pending sibling of the nearest ancestor that has one — which is queued next, or `null` when none is left.

## Branch Generation

The `BranchGenerator` can be used on its own. It takes a backend and the model name to send to it:

```typescript
import { BranchGenerator } from '@cogitator-ai/core';

const generator = new BranchGenerator(llmBackend, 'gpt-6.1-sol');

const branches = await generator.generate(
  currentNode, // null for the root
  'Optimize database query performance',
  3,
  agentContext,
  exploredThoughts
);
```

Each branch has a `thought`, a `proposedAction` and the parent node's messages. Previously explored thoughts are passed in to encourage novelty. When the model's answer cannot be parsed, generic fallback branches are returned.

## Branch Evaluation

The `BranchEvaluator` scores branches on three dimensions:

* **Confidence** — how likely is this approach to succeed?
* **Progress** — how much closer does it get to the goal?
* **Novelty** — how different is it from sibling branches?

```typescript
import { BranchEvaluator } from '@cogitator-ai/core';

const evaluator = new BranchEvaluator({
  llm: llmBackend,
  model: 'gpt-6.1-sol',
  reflectionEngine, // optional
  confidenceWeight: 0.5,
  progressWeight: 0.3,
  noveltyWeight: 0.2,
});

const scores = await evaluator.evaluateBatch(branches, goal, agentContext);
```

The weights above are the defaults for the composite score. When a `ReflectionEngine` is given, tool-call branches are evaluated with the agent's past insights. Inside `explore()`, the Cogitator's reflection engine is used when [reflection](/docs/advanced/reflection) is enabled and has been initialized by an earlier run.

## Progress Monitoring

```typescript
const controller = new AbortController();

const result = await executor.explore(agent, goal, {
  timeout: 30_000,
  abortSignal: controller.signal,
  onProgress: (stats) => {
    console.log(`Explored: ${stats.exploredNodes}/${stats.totalNodes}`);
    console.log(`Depth: ${stats.maxDepthReached}, Backtracks: ${stats.backtrackCount}`);
    console.log(`LLM calls: ${stats.llmCalls}`);
  },
});
```

`onProgress` is called after every step of the search — each node execution and each expansion. On timeout or abort, the best node found so far is returned.

## Result Structure

```typescript
interface ToTResult {
  success: boolean;
  output: string;
  tree: ThoughtTree;
  bestPath: ThoughtNode[];
  stats: ToTStats;
  runId: string;
  agentId: string;
  usage: {
    inputTokens: number;
    outputTokens: number;
    totalTokens: number;
    cost: number;
    duration: number;
  };
}
```

`bestPath` holds every node from the root to the winning node, so you can trace how the agent reached its conclusion; the full `tree` (with `nodes` as a `Map`) is there for visualization or debugging. `success` is true when the winning node completed. `usage` and `stats.tokenUsage` count the tokens of the branch runs and of the executor's own generation, evaluation and synthesis calls; `usage.cost` adds the cost of the branch runs to the cost of those calls, priced from the model registry. In `stats`, `llmCalls` counts the executor's own model calls (not those inside branch runs), `prunedNodes` the candidates dropped below `confidenceThreshold`, and `totalNodes` every child node created, including pending alternatives that never ran.

## When to Use ToT

Tree-of-Thought reasoning is most effective for:

* Problems with multiple valid approaches (architecture decisions, optimization)
* Tasks where the first attempt often fails (complex debugging, multi-step reasoning)
* Situations where exploring alternatives has high value (research, strategy)

For straightforward tasks, a single run — possibly with the model's own `reasoning` turned up — is faster and cheaper. Use ToT when the cost of exploring is worth the improvement in output quality.