摘要

语言模型正日益被部署于广泛任务中的通用问题求解，但在推理阶段仍受限于 token 级、从左到右的决策过程。这意味着在需要探索、战略前瞻，或初始决策起关键作用的任务中，语言模型可能表现不佳。为克服这些挑战，我们提出了一种新的语言模型推理框架——“思维树（Tree of Thoughts, ToT）”，它是对当前广泛使用的“思维链（Chain of Thought）”提示方法的推广，能够在连贯的文本单元（即“思维”）之间进行探索，这些单元作为问题求解的中间步骤。ToT 允许语言模型进行深思熟虑的决策：在多种不同的推理路径之间进行考虑、自我评估选择以决定下一步行动，并在必要时进行前瞻或回溯，以做出更具全局性的决策。我们的实验表明，在三个需要非平凡规划或搜索的新任务上，ToT 显著增强了语言模型的问题求解能力，这三项任务分别是：24 点游戏、创意写作和迷你纵横字谜。例如，在 24 点游戏中，使用思维链提示的 GPT-4 仅解决了 4% 的任务，而我们的方法成功率达到了 74%。完整提示与代码仓库：https://github.com/princeton-nlp/tree-of-thought-llm

1 引言

语言模型（LMs）最初被设计用于文本生成，但随着规模的扩大，如 GPT [25, 26, 1, 23] 和 PaLM [5]，它们已经被证明能够处理越来越广泛的任务，这些任务需要数学、符号、常识和知识推理能力。令人惊讶的是，支撑这一切进展的，依然是最初的自回归文本生成机制——以从左到右、逐 token 做出决策的方式生成文本。这样一个简单的机制是否足以构建一个通用问题求解器？如果不足，哪些问题会挑战这一现有范式？又有哪些替代机制值得探索？

人类认知的相关文献为回答这些问题提供了一些线索。“双系统”模型的研究表明，人类在做决策时存在两种模式——快速、自动、无意识的模式（“系统1”），以及缓慢、深思熟虑、有意识的模式（“系统2”）[30, 31, 16, 15]。这两种模式也曾被关联到机器学习中各种数学模型上。例如，人类及其他动物在强化学习中的研究探索了他们在何种情境下会采取联想式的“无模型”学习，或更具深思熟虑的“有模型”规划[7]。语言模型那种简单的、联想式的 token 级选择也类似于“系统1”，因此或许可以通过一种更具深思熟虑的“系统2”规划过程加以增强，该过程 (1) 维护并探索当前选择的多种可能性，而非仅做出单一选择，(2) 对当前状态进行评估，并主动进行前瞻或回溯，以做出更具全局性的决策。

为了设计这样一种规划过程，我们回溯人工智能（以及认知科学）的起源，从 Newell、Shaw 和 Simon 在 20 世纪 50 年代开展的规划研究中汲取灵感 [21, 22]。Newell 等人将问题求解描述为在组合问题空间中的搜索过程，该空间被表示为一棵树 [21]。因此，我们提出了用于语言模型通用问题求解的 思维树（Tree of Thoughts, ToT） 框架。如图1所示，尽管现有方法（将在下文详细介绍）通过采样连续的语言序列进行问题求解，ToT 则主动维护一棵“思维树”，其中每一个“思维”是一个连贯的语言序列，作为朝向问题求解的中间步骤（见表1）。这种高级语义单元允许语言模型在语言中实现深思熟虑的推理过程，从而对不同中间思维在推进问题求解中的进展进行自我评估（见图2、图4、图6）。这种通过语言模型的自我评估与深思熟虑来实现搜索启发式的方法是新颖的，因为以往的搜索启发式要么是编程实现的，要么是通过学习得到的。最后，我们将这种基于语言生成与评估多样思维的能力与搜索算法结合，如广度优先搜索（BFS）或深度优先搜索（DFS），以实现系统性地探索思维树，并可进行前瞻与回溯。

在实证方面，我们提出了三项新任务，用以挑战现有语言模型推理方法，即便是最先进的模型 GPT-4 [23]：24 点游戏、创意写作和纵横字谜（见表1）。这些任务需要演绎推理、数学推理、常识推理、词汇推理能力，并要求引入系统性的规划或搜索机制。我们展示了 ToT 在这三项任务上均取得了优越的结果，这得益于其足够通用与灵活，能够支持不同层级的思维单元、不同的思维生成与评估方式，以及适应不同问题特性的多种搜索算法。我们还通过系统性的消融实验分析了这些设计选择如何影响模型性能，并讨论了未来如何更有效地训练和使用语言模型的研究方向。

2 背景

我们首先形式化一些现有使用大型语言模型进行问题求解的方法，这些方法为我们的工作提供了灵感，并将在后文与我们的框架进行比较。我们使用 $p_{\theta }$ 表示一个具有参数 $\theta$ 的预训练语言模型（LM），使用小写字母 $x,y,z,s,\cdots$ 表示一个语言序列，即 $x=(x[1],\cdots ,x[n])$，其中每个 $x[i]$ 是一个 token，从而有：$\begin{array}{r}{p}_{\theta }(x)={\prod }_{i=1}^n{p}_{\theta }(x[i]|x[\mathrm{1...}i]).\end{array}$ 我们使用大写字母 $S,\cdots$ 表示一组语言序列。

输入-输出（IO）提示是使用语言模型将问题输入 $x$ 转化为输出 $y$ 的最常见方式：$y\sim p_{\theta }(y\mid {\text{prompt}}_{IO}(x))$，其中 ${\text{prompt}}_{IO}(x)$ 是将输入 $x$ 包装为包含任务指令和/或少量示例的提示模板。为简洁起见，我们将$p_{\theta }^{\text{prompt}}(\text{output}\mid \text{input})=p_{\theta }(\text{output}\mid \text{prompt}(\text{input}))$ ，因此，IO 提示可以形式化为：$y\sim p_{\theta }^{IO}(y\mid x)$。

Chain-of-thought（CoT）提示 [38] 被提出用以解决输入 $x$ 到输出 $y$ 的映射非平凡的情况（例如，当 $x$ 是一道数学题而 $y$ 是最终的数值答案时）。其核心思想是在 $x$ 和 $y$ 之间引入一系列思路链 $z_1,\cdots ,z_n$，其中每个 $z_i$ 是一个连贯的语言序列，作为通向问题解决的有意义的中间步骤（例如，对于数学问答任务，$z_i$ 可以是一个中间公式）。在使用 CoT 解决问题时，每个思路 $z_i\sim p_{\theta }^{\text{CoT}}(z_i\mid x,z_1\cdots z_{i-1})$ 被顺序采样，然后最终输出 $y\sim p_{\theta }^{\text{CoT}}(y\mid x,z_1\cdots z_n)$。在实践中，整体序列 $[z_{\mathrm{1...}n},y]\sim p_{\theta }^{CoT}(z_{\mathrm{1...}n},y|x)$ 被作为一个连续的语言序列进行采样，而对于思路的划分方式（例如每个 $z_i$ 是短语、句子还是段落）则是模糊的。

Self-consistency with CoT（CoT-SC）[36] 是一种集成方法，它采样 $k$ 条相互独立的思路链：$[z_{1\cdots n}^{(i)},y^{(i)}]\sim p_{\theta }^{CoT}(z_{1\cdots n},y|x)(i=1\cdots k)$，然后返回出现频率最高的输出： a r g m a x y # { i ∣ y ( i ) = y } \mathrm { a r g \, m a x } _ { y } \, \# \{ i \ | \ y ^ { ( i ) } \, = \, y \} argmaxy​#{i ∣ y(i)=y}

，CoT-SC 相较于 CoT 有所提升，因为对于同一个问题通常存在多种思考过程（例如，证明同一个定理的不同方式），通过探索更丰富的思路集合可以使最终决策更具忠实性。然而，在每条链内部并未对不同思路步骤进行局部探索，而且“最频繁”这一启发式方法仅适用于输出空间有限的情形（例如多项选择问答）。

3 Tree of Thoughts: 使用语言模型进行深思熟虑的问题求解

一个真正的问题解决过程涉及反复使用已有信息以启动探索，进而揭示更多信息，直到最终发现达成解答的方法为止。—— Newell 等人 [21]

关于人类问题解决的研究表明，人们会在一个组合型问题空间中进行搜索——这个空间可被视为一棵树，其节点表示部分解，分支对应于对这些部分解进行修改的操作符 [21, 22]。采取哪条分支由启发式方法决定，这些启发式方法帮助在问题空间中导航，并引导问题解决者走向答案。这一视角揭示了当前使用语言模型解决一般问题的方法的两个主要缺陷：

1）在局部层面，它们并未探索思路过程中的不同延续——即树的各个分支；
2）在全局层面，它们未采用任何形式的规划、前瞻或回溯来帮助评估这些不同的选项——也就是类似人类问题解决所特有的启发式搜索方式。

为了解决上述问题，我们提出了 Tree of Thoughts（ToT）这一范式，它允许语言模型在多个思维路径上进行探索（见图1©）。ToT 将任何问题建模为对一棵树的搜索过程，其中每个节点是一个状态 $s=[x,z_{1\cdots i}]$，表示一个由输入和迄今为止的思路序列构成的部分解。ToT 的一个具体实例需回答以下四个问题：

1. 如何将中间过程分解为思维步骤；
2. 如何从每个状态生成可能的思路；
3. 如何基于启发式方法评估这些状态；
4. 应该使用哪种搜索算法。

1. 思路分解（Thought decomposition）

虽然 CoT 会以连贯方式采样思路但不进行显式分解，ToT 则利用问题的性质来设计并分解中间思路步骤。如表1所示，具体问题不同，思路的粒度也不同：在填字游戏中，一个思路可能是几个词；在24点游戏中，可能是一行算式；在创意写作中，可能是一个写作计划的整段文字。一般而言，思路应足够“小”，以便语言模型可以生成有希望且多样的样本（例如，生成整本书通常太“大”而难以保持连贯性）；但也应足够“大”，以便语言模型能够评估其在解决问题方面的前景（例如，仅生成一个 token 通常太“小”，不足以做出判断）。

2. 思路生成器 $G(p_{\theta },s,k)$

给定一个树状态 $s=[x,z_{1\cdots i}]$，我们考虑两种策略来为下一个思路步骤生成 $k$ 个候选：

(a) 从 CoT 提示中独立同分布地采样思路（用于创意写作，见图4）：
$z^{(j)}\sim p_{\theta }^{CoT}(z_{i+1}|s)=p_{\theta }^{CoT}(z_{i+1}|x,z_{1\cdots i})(j=1\cdot \cdot k)$。
当思路空间较为丰富（例如每个思路是一个段落）时，这种方法效果更好，i.i.d. 采样能带来更大的多样性；

(b) 使用“建议式提示”顺序提出思路（用于24点游戏，见图2；填字游戏，见图6）：
$[z^{(1)},\cdots ,z^{(k)}]\sim p_{\theta }^{\text{propose}}(z_{i+1}^{(1\cdots k)}\mid s)$ 。当思路空间较受限（例如每个思路只是一个词或一行）时，这种方法效果更佳，因为在相同上下文中提出多个不同思路可以避免重复。

一个真正的问题解决过程，是反复利用已有信息发起探索，而探索过程又反过来揭示更多信息，直到最终找到达成解决方案的路径为止。—— Newell 等人 [21]

关于人类问题解决的研究表明，人类是在一个组合型的问题空间中进行搜索的——这个问题空间可以看作一棵树，其中的节点表示部分解，分支则对应于对这些部分解进行修改的操作符 [21, 22]。选择哪一个分支，取决于一些启发式方法，这些方法帮助导航问题空间，引导问题解决者走向解决方案。这样的视角揭示了现有语言模型在通用问题求解中存在的两个关键缺陷：1）在局部层面，它们不会探索思维过程中的不同延续——即树的不同分支；2）在全局层面，它们缺乏任何形式的计划、前瞻性或回溯机制，无法评估这些不同的选项——而这些正是人类问题解决过程中的典型启发式搜索方式。

为了解决上述缺陷，我们提出了 Tree of Thoughts（ToT）这一范式，它允许语言模型在“思维”层面探索多条推理路径（见图1©）。ToT 将任何问题建模为对一棵树的搜索，其中每个节点表示一个状态 $s=[x,z_{1\cdot \cdot \cdot i}]$，即包含输入 $x$ 和到目前为止生成的思维序列 $z_1\cdot \cdot \cdot i$ 的一个部分解。一个具体的 ToT 实例包含对以下四个问题的回答：

1. 如何将中间推理过程分解为思维步骤；
2. 如何从每个状态生成潜在的思维；
3. 如何对状态进行启发式评估；
4. 使用什么样的搜索算法。

1. 思维分解（Thought decomposition）

虽然 Chain-of-Thought（CoT）可以在没有显式分解的情况下连贯地生成思维，ToT 则利用问题本身的特性对中间推理步骤进行设计和分解。如表1所示，依据问题的不同，一个“思维”可能是几个词（如填字游戏），一行公式（如24点游戏），或一整段写作计划（如创意写作）。一般而言，一个“思维”应当足够“小”，以便语言模型能够生成有前景且多样的样本（例如生成整本书通常太“大”，不够连贯）；同时也要足够“大”，以便语言模型可以对其在问题求解中的前景做出评估（例如生成一个 token 通常太“小”，无法评估）。

2. 思维生成器 $G(p_{\theta },s,k)$

给定树状态 $s=[x,z_1\cdot \cdot \cdot i]$，我们考虑以下两种策略来生成 $k$ 个下一步思维候选：

（a）从 CoT 提示中独立同分布地采样思维（创意写作，图4）：

$$z^{(j)}\sim p_{\theta }^{\text{CoT}}(z_{i+1}\mid s)=p_{\theta }^{\text{CoT}}(z_{i+1}\mid x,z_1\cdot \cdot \cdot i),j=1\cdot \cdot \cdot k$$

这种方法在思维空间较为丰富（例如每个思维是一段文字）时表现更好，独立样本有利于提高多样性；

（b）使用“提议提示”顺序提出思维（24点游戏，图2；填字游戏，图6）：

$$[z^{(1)},\cdot \cdot \cdot ,z^{(k)}]\sim p_{\theta }^{\text{propose}}(z_{i+1}^{(1\cdot \cdot \cdot k)}\mid s)$$

这种方法在思维空间较为受限（如每个思维仅为一个词或一行）时表现更好，在同一上下文中提出不同思维可以避免重复。

温馨提示：
阅读全文请访问"AI深语解构" ：ToT：思维树：借助大语言模型进行审慎的问题求解