Breadth-first search (BFS) traverses a tree or graph level by level: it explores every node at the current depth before advancing to the next. section 4.1.2 section 4.2.7
BFS supports systematic exploration in several search settings:
- Begin at a root or selected graph node, inspect all neighboring nodes, then continue through subsequent depth levels. section 4.1.2
- Compare with depth-first search (DFS): BFS completes one level before proceeding, whereas DFS follows one branch as far as possible. section 4.2.7
- Relate BFS to beam search by viewing beam search as a pruned traversal that retains only the most promising sequences. section 4.1.2
Breadth-first exploration in Tree of Thoughts
Tree-of-Thoughts prompting uses BFS to explore alternative intermediate thoughts systematically. In the Game of 24 example, candidate equations are generated, evaluated as likely or unlikely, and selectively retained while searching for a solution such as 4 * (10 - (13 - 9)) = 24. section 4.2.7
