Tree of Thoughts as a Classical Heuristic Search Problem: Formal Foundations and Design Patterns

📄 arXiv: 2605.28566v1 📥 PDF

作者: Guni Sharon

分类: cs.AI, cs.LG

发布日期: 2026-05-27

备注: Extended version of the SoCS 2026 paper. Includes appendices omitted from the proceedings version

期刊: Proceedings of the Nineteenth International Symposium on Combinatorial Search (SoCS 2026), AAAI Press, 2026

💡 一句话要点

将思维树（ToT）框架形式化为经典启发式搜索问题，并提出设计模式

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 大型语言模型 思维树 启发式搜索 自动规划 推理 提示工程 搜索算法

📋 核心要点

  1. 现有LLM推理过程是短视的，容易产生级联错误，限制了其在复杂推理任务中的表现。
  2. 论文将LLM推理过程形式化为经典启发式搜索问题，利用思维树框架进行探索和回溯。
  3. 通过统一的分类法，分析现有ToT工作，并识别出适用于不同任务的设计模式，为未来研究提供指导。

📝 摘要（中文）

大型语言模型（LLM）展现了卓越的推理能力，但其标准的自回归token预测过程本质上是短视的，容易产生级联错误。为了解决这个问题，思维树（ToT）框架在中间推理步骤上创建了一个搜索空间，允许搜索模型探索、前瞻和回溯。然而，目前的ToT研究分散在自然语言处理和自动规划社区中，常常使用不一致的术语和临时实现。因此，我们通过一个基于经典启发式搜索术语的统一分类法来综合ToT领域。我们将基于LLM的推理映射到经典搜索组件：状态表示（思维粒度）、后继生成（提示算子）和启发式评估（对进展的自我评估）。我们在分类法的背景下分析了现有的工作，并确定了新兴的设计模式：用于浅层确定性任务的系统搜索（最佳优先搜索）和用于深度多步推理的前瞻性策略（DFS、MCTS）。最后，我们确定了启发式搜索和LLM推理交叉领域中存在的算法挑战，并呼吁启发式搜索社区参与到这个新兴领域中。

🔬 方法详解

问题定义：论文旨在解决大型语言模型在复杂推理任务中由于自回归生成方式的局限性而导致的推理能力不足问题。现有方法，即直接使用LLM进行token预测，存在短视和容易累积误差的缺点，无法有效进行探索和回溯。因此，需要一种更灵活、更具策略性的推理框架。

核心思路：论文的核心思路是将LLM的推理过程建模为经典启发式搜索问题，并利用思维树（Tree-of-Thoughts, ToT）框架来构建搜索空间。通过将推理过程分解为中间步骤（thoughts），并在这些步骤上进行探索、评估和回溯，从而克服LLM的短视问题，提高推理的准确性和可靠性。

技术框架：整体框架包括三个主要组件：状态表示（State Representation）、后继生成（Successor Generation）和启发式评估（Heuristic Evaluation）。状态表示定义了思维的粒度，即每个节点代表的推理单元。后继生成利用提示工程（Prompting Operators）来生成可能的后续思维。启发式评估则使用LLM对当前思维的进展进行自我评估，指导搜索方向。整个过程可以看作是在思维树上进行搜索，目标是找到最优的推理路径。

关键创新：论文的关键创新在于将LLM推理与经典启发式搜索相结合，并提供了一个统一的分类法来理解和比较不同的ToT实现。通过这种形式化，可以将启发式搜索领域的成熟算法和技术应用于LLM推理，从而提高推理效率和效果。此外，论文还识别出适用于不同任务的设计模式，为未来的ToT研究提供了指导。

关键设计：关键设计包括思维粒度的选择（例如，单个token、句子或段落），提示算子的设计（如何引导LLM生成有意义的后续思维），以及启发式评估函数的设计（如何准确评估当前思维的质量和进展）。此外，搜索算法的选择（例如，最佳优先搜索、深度优先搜索、蒙特卡洛树搜索）也至关重要，需要根据任务的特点进行调整。

📊 实验亮点

论文通过形式化ToT框架，将LLM推理与经典启发式搜索联系起来，为该领域的研究提供了一个统一的视角。论文分析了现有ToT方法，并识别出适用于不同任务的设计模式，例如，对于浅层确定性任务，最佳优先搜索表现良好；而对于深度多步推理，前瞻性策略（如DFS和MCTS）更有效。这些发现为未来的研究提供了有价值的指导。

🎯 应用场景

该研究成果可应用于需要复杂推理能力的各种场景，例如：数学问题求解、代码生成、文本摘要、对话系统等。通过将LLM推理过程形式化为启发式搜索问题，可以提高LLM在这些任务中的性能和可靠性，使其能够更好地解决现实世界中的复杂问题。未来的影响包括更智能的AI助手、更强大的自动化工具和更高效的决策支持系统。

📄 摘要（原文）

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.