Tree of Thoughts as a Classical Heuristic Search Problem: Formal Foundations and Design Patterns
For researchers in NLP and automated planning, it provides a formal taxonomy to standardize ToT approaches, but is primarily a synthesis and call to action rather than a novel algorithm.
The paper unifies Tree-of-Thoughts (ToT) research by mapping LLM reasoning to classical heuristic search components, identifying design patterns such as Best-First Search for shallow tasks and DFS/MCTS for deep reasoning, and calls for heuristic search community engagement.
Large Language Models (LLMs) have demonstrated remarkable reasoning capabilities, yet their standard generation process -- auto-regressive token prediction -- is inherently myopic and prone to cascading errors. To address this, the Tree-of-Thoughts (ToT) framework creates a search space over intermediate reasoning steps, allowing search models to explore, look ahead, and backtrack. However, current ToT research remains fragmented across Natural Language Processing and Automated Planning communities, often using inconsistent terminology and ad-hoc implementations. Consequently, we synthesize the ToT landscape through a unified taxonomy based on classical heuristic search terminology. We map LLM-based reasoning to classical search components: state representation (granularity of thoughts), successor generation (prompting operators), and heuristic evaluation (self-assessment of progress). We analyze existing work within the context of our taxonomy and identify emerging design patterns: systematic search (Best-First Search) for shallow, deterministic tasks and lookahead-heavy strategies (DFS, MCTS) for deep multi-step reasoning. We conclude by identifying open algorithmic challenges at the intersection of heuristic search and LLM reasoning, and call on the heuristic search community to engage with this emerging domain.