Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper formalizes the Tree-of-Thoughts (ToT) framework for LLM reasoning as a classical heuristic search problem, bridging NLP and Automated Planning perspectives. It provides a unified taxonomy mapping LLM reasoning components (state representation, successor generation, heuristic evaluation) to classical search elements. The analysis reveals design patterns like Best-First Search for shallow tasks and DFS/MCTS for deep reasoning, highlighting open challenges for the heuristic search community.
LLM reasoning, when viewed through the lens of classical heuristic search, reveals surprisingly clear design patterns that can guide future algorithm development.
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.