Tree of Thoughts

Depth-first

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

## Goal

Solve a problem by depth-first search over partial solutions: propose several next thoughts, rate each, expand the most promising, and backtrack when a branch dead-ends.

## How it works

1. Represent a state as the problem plus the list of thoughts taken so far; push the empty state onto a stack.
2. Pop the top state. If a deterministic check says it solves the problem, return its thoughts as the solution.
3. If the state is below the depth limit, call the model with the Thought proposal prompt, passing the problem and the state, and parse up to breadth distinct candidate thoughts.
4. Rate each candidate with the Thought evaluation prompt and read the first word as sure, maybe or impossible.
5. Drop the impossible candidates, and push the rest onto the stack so the best-rated is popped next (sure before maybe).
6. When a state has no surviving children or is at the depth limit, do nothing more with it; popping the next state is the backtrack to its parent's next-best sibling.

## Prompts

### Thought proposal prompt

```markdown
Problem: {{problem}}

Progress so far:
{{state}}

Propose {{breadth}} different next steps. Each must be a single, concrete
move that follows from the progress above, and they must not duplicate
each other. Label them A, B, C.
```

### Thought evaluation prompt

```markdown
Problem: {{problem}}

Candidate progress:
{{thought}}

Can this candidate still lead to a full solution? Check it carefully
against the problem's constraints.

Answer with exactly one word: sure, maybe or impossible.
Then give one sentence of reasoning.
```

## Stop rule

Stop when a state passes the solution check, when the stack is empty, or after 100 model calls. If no solution is found, return the deepest state reached with a status saying the search failed.

## Requirements

- Make the breadth (default 3), the depth limit (default 3) and the total model-call budget (default 100) parameters.
- If a rating reply does not start with sure, maybe or impossible, treat it as maybe: never prune a branch on a parse failure.
- Drop proposed thoughts that duplicate a sibling or a state already visited, so the breadth is not wasted.
- Use a deterministic solution check (here, evaluate the arithmetic) wherever the task allows, instead of asking the model.
- Add a Game of 24 test with a stub LLM rating 10-4=6 sure, 4+9=13 and 13*4=52 impossible, then 6+9=15 sure, 13-9=4 maybe, and every child of 6+9=15 impossible; assert 4 proposal calls and the path 10-4=6, 13-9=4, 6*4=24.

Breadth-first beam

Implement the Tree of Thoughts pattern (Breadth-first beam variant) in this codebase, using the LLM client and language we already use.

## Goal

Solve a problem by breadth-first search with a beam: at each level expand every kept state, rate every child, and keep the best few, for a fixed number of levels.

## How it works

1. Start the frontier as a list holding one empty state: the problem with no thoughts taken.
2. For every state on the frontier, call the model with the Thought proposal prompt and parse up to breadth candidate thoughts, giving the next level's children.
3. Rate every child with the Thought evaluation prompt, mapping sure, maybe and impossible to scores of 20, 1 and 0.001 as the paper does, and summing over the samples if you rate more than once.
4. Sort the children by score and keep the top beam-width as the new frontier; dropping impossible children outright is a simplification that saves calls.
5. Repeat for the configured number of levels, then return the best-scoring final state that passes the solution check.

## Prompts

### Thought proposal prompt

```markdown
Problem: {{problem}}

Progress so far:
{{state}}

Propose {{breadth}} different next steps. Each must be a single, concrete
move that follows from the progress above, and they must not duplicate
each other. Label them A, B, C.
```

### Thought evaluation prompt

```markdown
Problem: {{problem}}

Candidate progress:
{{thought}}

Can this candidate still lead to a full solution? Check it carefully
against the problem's constraints.

Answer with exactly one word: sure, maybe or impossible.
Then give one sentence of reasoning.
```

## Stop rule

Stop after the last level, or earlier if the frontier is empty. If no final state passes the solution check, return the best-scoring one with a status saying it is unverified.

## Requirements

- Make the beam width (default 5), the breadth per state (default 5) and the number of levels (default 3) parameters.
- Run the proposal and rating calls for one level concurrently, with a cap on calls in flight (default 8).
- If a rating reply does not start with sure, maybe or impossible, score it as maybe; never prune on a parse failure.
- Deduplicate children with the same state across the whole level before rating, so the beam is not filled with copies.
- Add a test with a stub LLM, beam width 2 and 3 levels; assert 5 proposal calls (1 + 2 + 2), 2 states kept after each of the first two levels, and the exact path 10-4=6, 13-9=4, 6*4=24.