Beam Search over a Tree of Thoughts

Problem Statement

Chain-of-thought commits to one line of reasoning and lives with it. Tree of Thoughts generates several candidate thoughts at each step, scores them, keeps the best few and throws the rest away. The search itself is the algorithm - and it is a beam search with a pruning rule.

Background

You are given a pre-scored tree, so no model calls are needed. Each node has a score (the evaluator's judgement of that thought) and a list of children.

A path is a sequence of node ids from the root. Its value is the sum of the scores of its nodes excluding the root - the root is the problem statement, not a thought.

The search:

1. Start with the beam holding the single root path, value 0.0.
2. Repeat up to max_depth times:
   • For each path in the beam, look at the last node's children. A path whose last node has no children is complete: move it to the finished set.
   • Otherwise extend the path by each child. Every child examined counts towards expanded, whether or not it survives.
   • Prune any child whose own score is < min_score; it never enters the beam.
   • Collect all surviving extensions, sort by value descending (ties broken by the path itself, ascending, comparing ids element by element), and keep the first beam_width as the new beam.
   • If nothing survives, the search stops.
3. When the loop ends, any paths still in the beam join the finished set - they are depth-limited but still candidate answers.
4. The answer is the finished path with the highest value, ties broken by the smallest path.

Your Task

Implement:

def tot_beam_search(nodes, root, beam_width, max_depth, min_score):

• nodes: dict of node id -> {"score": float, "children": list[str]} (children may be absent).

Return {"best_path": list[str], "best_value": float, "expanded": int} with best_value rounded to 4 decimal places. If nothing at all is finished, return [], 0.0 and the expansion count.

Input/Output Format

Compare values for sorting after rounding to 6 decimal places so that arithmetically-equal branches tie cleanly; report best_value rounded to 4.

Sample

nodes = {
    "r":  {"score": 0.0, "children": ["a", "b"]},
    "a":  {"score": 0.8, "children": []},
    "b":  {"score": 0.9, "children": []},
}
print(tot_beam_search(nodes, "r", 2, 3, 0.0))
# {'best_path': ['r', 'b'], 'best_value': 0.9, 'expanded': 2}