Tree of Thoughts: Deliberate Problem Solving with Large Language Models

# 思维树：用大型语言模型深思熟虑地解决问题

# 摘要

语言模型越来越多地被用于跨广泛任务的一般问题解决，但在推理过程中仍然局限于令牌级别的、从左到右的决策过程。这意味着他们可能在需要探索的任务、战略前瞻或初始决策起关键作用的任务中落空。为了克服这些挑战，我们引入了一种新的语言模型推理框架 - - "思维树" (Tree of Thoughts，ToT)，它推广了流行的 "思维链" ( Chain of Thoughts ) 方法来促进语言模型，并允许对文本 ( "思想") 的连贯单元进行探索，作为问题解决的中间步骤。ToT 允许 LM 进行深思熟虑的决策，通过考虑多条不同的推理路径和自我评估的选择来决定下一步的行动方向，并在必要时进行前瞻或回溯以做出全局选择。我们的实验表明，ToT 显著提高了语言模型在 3 个需要非平凡计划或搜索的新颖任务上的问题解决能力：游戏 24、创意写作和微型填字游戏。例如，在第 24 局的比赛中，有思维链提示的 GPT-4 只解决了 4% 的任务，而我们的方法取得了 74% 的成功率。所有提示的代码：https://github.com/ysymyth/tree-of-thought-llm.

# 1 导言

GPT [22、23、1、20] 和 PaLM [ 5 ] 等最初设计用于生成文本的语言模型 (Language Model，LM) 的扩展版本已被证明越来越能够执行需要数学、符号、常识和知识推理的越来越广泛的任务。也许令人惊讶的是，所有这些进步的背后仍然是生成文本的原始自回归机制，它以从左到右的方式逐个做出 token 级别的决策。这样一个简单的机制是否足以使 LM 被构建成一个通用的问题求解器？如果不是，会有哪些问题挑战当前的范式，又应该有哪些替代机制？

有关人类认知的文献提供了回答这些问题一些线索。对 "双加工" 模型的研究表明，人们有两种参与决策的模式 -- 快速的、自动的、无意识的模式 (' 系统 1') 和缓慢的、刻意的、有意识的模式 (' 系统 2 ') [27、28、13、12]。这两种模式之前已经被连接到机器学习中使用的多种数学模型中。例如，在人类和其他动物中关于强化学习的研究已经探索了他们在何种情况下从事联想的 "无模型" 学习或更审慎的 "基于模型" 的规划 [6]。例如，对人类和其他动物的强化学习的研究已经探索了他们在何种情况下进行关联的 "无模型" 学习或更慎重的基于 "模型" 的规划 [ 6 ]。LMs 的简单关联令牌级选择也与 "系统 1" 有关，因此可能会受益于更慎重的 "系统 2" 规划过程的增强，即 ( 1 ) 保持并探索当前选择的多样化替代方案，而不是仅仅挑选一种；( 2 ) 评估其当前状态，并积极展望或回溯，以做出更多的全球决策。

图 1：图示说明了用 LLMs 解决问题的各种方法。每个矩形框代表一种思想，它是一个连贯的语言序列，是问题解决的中间步骤。在图 2、4、6 中可以看到思想是如何产生、评价和搜索的具体例子。

为了设计这样的规划过程，我们回到人工智能 (以及认知科学) 的起源，从 Newell、Shaw 和 Simon 从 20 世纪 50 年代 [18、19] 开始探索的规划过程中获得灵感。Newell 等人将问题求解 [ 18 ] 描述为通过组合问题空间进行搜索，用树表示。因此，我们提出了用语言模型解决一般问题的思维树 (ToT) 框架。如图 1 所示，现有方法 (下文详述) 在对问题解决的连续语言序列进行采样时，ToT 主动维护了一棵思想树，其中每个思想都是一个连贯的语言序列，作为问题解决的中间步骤 (表 1 )。这样的高级语义单元允许 LM 通过刻意的推理过程来自我评估不同的中间思想在解决问题方面的进展，该过程也在语言 (图 2,4,6) 中实例化。这种通过 LM 自我评估和审议来实现搜索启发式的方法是新颖的，因为以前的搜索启发式要么是编程的，要么是学习的。最后，我们将这种基于语言的生成和评估多样化思想的能力与搜索算法相结合，如广度优先搜索 (BFS) 或深度优先搜索 (DFS)，从而可以通过前瞻和回溯对思想树进行系统探索。

在实证上，我们提出了 3 个新的问题，它们挑战了现有的 LM 推理方法，即使是最先进的语言模型 GPT-4 [20]：游戏 24、创意写作和填字游戏 (表 1)。这些任务需要演绎推理、数学、常识、词汇推理能力，以及融入系统规划或搜索的方式。我们展示了 ToT 在所有三个任务上都获得了优越的结果，因为它具有足够的通用性和灵活性来支持不同层次的思想、不同的思想生成和评估方式以及适应不同问题性质的不同搜索算法。我们还分析了这些选择如何通过系统消融影响模型性能，并讨论了未来更好地训练和使用 LM 的方向。

# 2. 背景

我们首先将一些现有的使用大型语言模型进行问题求解的方法进行形式化，我们的方法是受到启发并稍后进行比较的。我们用$p_θ$ 表示参数为 θ 的预训练 LM，用小写字母$x，y，z，s，· · ·$表示语言序列，即 $x = ( x[1],···,x[n])$，其中每个 x [i] 是一个 token，使得$p_θ(x)=\prod_{i=1}^{n} p_θ(x[i]|x[1...i])$。我们用大写字母$S,···$表示语言序列的集合。

输入 - 输出 (Input-Output，IO) 提示是最常见的将问题输入$x$ 转化为输出$y$ 的 LM 方法：$y\sim p_θ(y|prompt_{IO}(x))$，其中提示$prompt_{IO}(x)$ 用任务指令和 / 或少量的输入输出示例包装输入$x$。为简单起见，令$p_θ^{prompt}(output|inoput)=p_θ(output|prompt(inoput))$，则 IO 提示可表示为$y \sim p^{IO}_θ(y|x)$。

思维链 (CoT) 提示 提出了解决输入$x$ 到输出$y$ 的映射为非平凡 (例如，当$x$ 是数学问题，$y$ 是最后的数值答案时) 的情况。其核心思想是引入一连串的思想$z_1，···，z_n$ 来桥接$x$ 和$y$，其中每个$z_i$ 是一个连贯的语言序列，作为解决问题 (例如，$z_i$ 可以作为数学 QA 的中间方程) 的一个有意义的中间步骤。为了解决 CoT 存在的问题，对每个思维 $z_i \sim p^{CoT}_θ (z_i|x,z_{1···i-1})$ 进行顺序采样，输出 $y \sim p^{CoT}_θ(y|x,z_{1···n})$ 。实践中，$[z_{1···n} ,y] \sim p^{CoT}_θ(z_{1···n},y|x)$ 被采样为连续的语言序列，思维的分解 (例如，每个$z_i$ 是短语、句子还是段落) 被留有歧义。

自洽 CoT (CoT-SC) 是一种集成方法，采样$k$ 独立同分布链的思想： $[z{(i)}_{1···n},y^{(i)}] \sim p^{CoT}_θ( z_{1···n},y|x)(i = 1···k)$ ，然后返回最频繁的输出：${argmax}_y\# \{i|y^{(i)}=y\}$ 。CoT-SC 在 CoT 的基础上进行了改进，因为对于同一个问题 (例如，用不同的方法证明同一个定理)，通常有不同的思维过程，通过探索更丰富的思维集合，可以使输出的决策更加忠实。但是，每条链内部并不存在对不同思想步骤的局部探索，"最频繁" 启发式只适用于输出空间有限的 (例如，多选择题)。

# 3. 思维树：用 LM 有意识地解决问题

一个真正的问题解决过程涉及到反复使用可用的信息来发起探索，进而揭示更多的信息，直到找到解决问题的方法。- - Newell 等 [18]

对人类问题求解的研究表明，人们通过一个组合问题空间进行搜索 -- 一棵树，其中节点代表部分解，分支对应于修改它们的运算符 [18、19]。采取哪个分支是由启发式决定的，它有助于导航问题空间并引导问题解决者走向解决方案。这一视角凸显了现有使用 LMs 解决一般性问题的方法的两个关键缺陷：1) 在局部上，它们没有探索一个思维过程中的不同延续 -- 树的分支。2) 在全局范围内，它们不包含任何类型的计划、前瞻或回溯，以帮助评估这些不同的选项 -- 这种启发式指导的搜索似乎是人类解决问题的特征。

为了解决这些不足，我们引入了思维树 (Tree of Thoughts，ToT)，该范式允许 LM 探索思想上的多条推理路径 (图 1 (c))。ToT 将任何问题框定为树上的搜索，其中每个节点都是一个状态$s=[x,z_{1···i}]$ ，表示到目前为止有输入和思想序列的部分解。ToT 的一个具体实例包括四个问题：1. 如何将中间过程分解为思想步骤；2. 如何从每个状态中产生潜在的思想；3. 如何启发式地评估状态；4. 使用什么搜索算法。

1 思维分解。 CoT 在没有显式分解的情况下连贯地采样思维，而 ToT 利用问题属性来设计和分解中间思维步骤。如表 1 所示，根据问题的不同，一个思维可以是几个单词 (填字游戏)、一行等式 ( 游戏 24)，也可以是写作计划的整段 (Creative Writing)。一般来说，一个思维应该足够 "小"，以使 LMs 能够产生有希望的、多样的样本 (例如，生成一本整本书通常太 "大" 而不连贯)，但也应该足够 "大"，以使 LMs 能够评估其解决问题的前景 (例如，生成一个 token 通常太 "小" 而无法评估)。

2. 思维发生器 $G(p_θ,s,k)$ 。给定一个树状态 $s = [x,z_{1···i}]$ ，我们考虑了两种策略来生成$k$ 个候选项用于下一步的思考：

• (a) 采样 采样一个来自 CoT Prompt 的独立同分布思维 (创意写作，图 4)：$z ^{(j)} \sim p^{CoT}_θ(z_{i+1}|s) = p^{CoT}_θ(z_{i+1}|x,z_{1···i})(j = 1···k)$ 。当思维空间为丰富的 (例如，每个思想都是一个段落)，独立同分布样本导致多样性时，效果更好；

• (b) 提出 顺次提出使用 "提出 Prompt" 的思维 (游戏 24, 图 2; 十字架，图 6)：$ [z^(1)},···,z【{(k)】] \sim p^prompt}_θ(z【{(1···k)】_{i+1}|s)$ 。这在思维空间受约束较大的 (例如，每一个思想都只是一个词或一条线) 时效果更好，因此在同一语境下提出不同的思维避免了重复。

**3 . 状态评估器$V ( p_θ , S)$。** 给定一个不同状态的前沿面，状态评估器评估它们在解决问题上的进展，作为搜索算法的启发式，以确定哪些状态要继续探索，以何种顺序进行。虽然启发式是解决搜索问题的标准方法，但它们通常是预编程的 (e.g. Deep Blue) 或学习的 (如 AlphaGo)。我们提出了第三种选择，即利用 LM 有意地推理状态。在适用的情况下，这种深思熟虑的启发式可以比编程规则更灵活，比学习的模型更有效。与思想生成器类似，我们考虑两种策略来单独或共同评估状态：

• (a) 独立地对每个状态赋值：$V ( p_θ , S) ( s ) \sim p^{value}_θ ( v | s ) \forall s\in S$ ，其中一个值提示关于状态$s$ 的理由，以产生一个标量值$v$ (如 1 ~ 10) 或一个分类 (如确定 / 可能 / 不可能)，可以启发式地转换成一个值。这种评价性推理的基础可以因问题和思考步骤而异。在这项工作中，我们通过少量的前瞻性模拟 (例如，快速确认 5 , 5 , 14 通过 5 + 5 + 14 可以达到 24 , 或者 ' hot l ' 通过填充 ' e ' in ' 可以表示 ' inn ') 和常识 ( ( 1 ) ( 2 ) ( 3 ) 太小，达不到 24 , 或者没有词可以以 "tzxc" 开头) 来探索评估。前者可能促进 "好" 状态，后者有助于消除 "坏" 状态。这样的估值不需要完美，只需要近似即可

• (b) 跨状态投票：$V ( p_θ , S) ( s ) = 1[ s = s^*]$ ，其中一个 "好" 状态$s^* \sim p^{vote}_θ ( s * | S )$ 是基于在投票提示符中刻意比较 S 中的不同状态而被投票出来的。当问题成功较难直接对 (e.g. 通道连贯性) 进行赋值时，自然要对不同的局部解进行比较，并投票选出最有希望的局部解。这在精神上类似于一种 "阶梯式" 自洽策略，即把 "探索哪种状态" 作为多选 QA，并使用 LM 样本对其进行投票。

对于这两种策略，我们都可以多次提示 LM 聚合值或投票结果来交换时间 / 资源 / 成本以获得更忠实 / 健壮的启发式。

4. 搜索算法。最后，在 ToT 框架中，可以根据树结构来即插即用不同的搜索算法。我们探索了两种相对简单的搜索算法，并为以后的工作留下了更先进的 (例如 A*, MCTS)：

• (a) 广度优先搜索 (BFS) (算法 1) 每一步保持一组最有希望的 b 个状态。这被用于游戏 24 和创意写作，其中树深度限制为 (T≤3)，初始思想步骤可以被评估和修剪到一个小的集合 ( b≤5)。

• (b) 深度优先搜索 (DFS) (算法 2) 首先探索最有希望的状态，直到最后的输出达到 (t > T)，或者状态评估器认为从当前的$s ( V ( p_θ , { s }) ( s )≤v_{th}$ 为一个值阈值 $v_{th}$ ) 不可能解决问题。在后一种情况下，s 中的子树被剪枝以进行开发的交易探索。在这两种情况下，DFS 都回溯到 s 的父状态继续探索。

从概念上讲，ToT 作为 LMs 解决一般性问题的方法有几个好处：(1) 一般性。IO、CoT、CoT-SC 和自细化可以看作是 ToT (即深度和广度有限的树木；图 1) 的特例。(2) 模块化。基础 LM，以及思想分解、生成、评估和搜索过程都可以独立变化。(3) 适应性。可以容纳不同的问题属性、LM 能力和资源约束。(4) 便利性。不需要额外的训练，只需要一个预训练的 LM 就足够了。下一节将展示这些概念性的好处如何在不同的问题中转化为强有力的实证表现。

# 4. 实验

我们提出了三个困难的任务，即使从最先进的语言模型 GPT-4 [20] 中采样，使用标准的 IO 提示或思维链 (CoT) 提示。我们展示了在思想树中刻意搜索 (ToT) 如何产生更好的结果，更重要的是，有趣和有前途的新方法来使用语言模型来解决需要搜索或规划的问题。除非另有说明，我们使用聊天完成模式 GPT-4 进行实验，采样温度为 0.7。

# 4.1 游戏 24

24 游戏是一个数学推理挑战，目标是用 4 个数字和基本算术运算 (+ - * /) 得到 24。例如，给定输入 ' 4 9 10 13 '，一个解的输出可以是 ' $( 10 - 4 ) * ( 13 - 9 ) = 24 $'。

任务设置 。我们从 4nums.com 抓取了 1，362 个游戏，按照人类求解时间由易到难进行排序，并使用索引为 901-1，000 的相对困难游戏子集进行测试。对于每个任务，我们认为输出是成功的，如果它是一个有效的等式，等于 24，并且每个任务只使用一次输入数字。我们报告了 100 场比赛的成功率作为衡量标准。

基线。我们使用一个标准的输入 - 输出 (IO) 提示，包含 5 个语境例子。为了促进思维链 (CoT)，我们用 3 个中间方程来增加每个输入 - 输出对，每个方程在两个剩余的数字上操作。例如，给定输入 ' 4 9 10 13 '，思维可以是 ' 13-9 = 4 (剩余: 4 4 10)；10-4 = 6 (剩余: 4 6)；4 * 6 = 24 (剩余：24 ) '。对于每个游戏，我们对 IO 和 CoT 提示进行了 100 次的平均性能采样。我们还考虑了一个 CoT 自洽基线，它取自 100 个 CoT 样本的大部分输出，并在一个 IO 样本的基础上采用迭代 - 精化方法，最多迭代 10 次。在每一次迭代中，LM 以所有以前的历史为条件，如果输出不正确，则 "反思你的错误并生成一个精致的答案"。需要注意的是，它使用了关于方程正确性的真实反馈信号。

ToT 设置。要把游戏 24 框定到 ToT，很自然地要把思维分解成 3 个步骤，每个步骤是一个中间等式。如图 2 (a) 所示，在每个树节点上，我们提取 "剩余" 的数字，并提示 LM 提出一些可能的下一步步骤。同样的 "提议提示" 用于所有 3 个思考步骤，尽管它只有一个 4 个输入数字的例子。我们在 ToT 中执行广度优先搜索 (BFS)，在每个步骤中我们保留最好的 b = 5 个候选者。为了在 ToT 中执行深思熟虑的 BFS，如图 2 (b) 所示，我们提示 LM 将每个想法候选项评估为 "确定 / 可能 / 不可能"，达到 24。其目的是促进正确的部分解可以在很少的前瞻试验中被判定，并消除基于 "太大 / 小" 常识的不可能的部分解，并保留其余的 "也许"。我们对每个思维采样 3 次值。

结果。如表 2 所示，IO、CoT 和 CoT-SC 提示方法在任务上表现不佳，仅达到 7.3 %、4.0 % 和 9.0 % 的成功率。相比之下，宽度 b = 1 的 ToT 已经达到了 45 % 的成功率，而宽度 b = 5 的 ToT 则达到了 74 %。我们还考虑了 IO / CoT 的 Oracle 设置，通过使用 k 个样本中最好的 (1≤k≤100) 来计算成功率。为了将 IO / CoT ( k 的最佳) 与 ToT 进行比较，我们考虑计算 ToT 中每个任务访问的树节点跨越 $b = 1 · · · 5$ ，并将图 3 (a) 中的 5 个成功率映射，将 IO / CoT ( k 的最佳) 视为在一个 bandit 中的访问 k 个节点。毫不奇怪，CoT 的规模比 IO 要好，在 100 个 CoT 样本中，最好的达到了 49 % 的成功率，但仍然比在 ToT ( b > 1) 中探索更多的节点差得多。

误差分析。 图 3 (b) 分解了 CoT 和 ToT 样本在哪一步任务失败，即想法 (在 CoT 中) 或所有 b 个想法 (在 ToT 中) 无效或不可能达到 24。值得注意的是，大约 60 % 的 CoT 样本在生成第一步，即相当于前三个词 (如 ' 4 + 9 ') 后，就已经失败了。这凸显了从左到右直接解码的问题。

# 4.2 创造性的写作

接下来，我们发明了一个创造性的写作任务，其中输入是 4 个随机句子，输出应该是 4 个段落，分别在 4 个输入句子中结束。这样的任务具有开放性和探索性，对创造性思维和高层次规划提出了挑战。

任务设置。我们从 randomwordgenerator.com 中随机抽取句子组成 100 个输入，每个输入约束都没有真值段落。由于我们发现 GPT-4 可以在大部分时间内遵循输入约束，因此我们主要通过两种方式来评估篇章连贯性：使用 GPT-4 的零样本提示来提供 1-10 的标量分数，或者使用人工判断来比较不同方法的输出对。对于前者，我们采样了 5 个分数，并对每个任务的输出进行了平均，我们发现这 5 个分数通常是一致的，平均每个输出的标准差约为 0.56。对于后者，我们在一项盲法研究中使用作者的一个子集来比较 CoT vs. ToT 生成通道对，其中通道的顺序在 100 个输入上随机翻转。

基线。考虑到任务的创造性，IO 和 CoT 提示均为 zero-shot。前者促使 LM 在给定输入约束的情况下直接生成一个连贯的段落，后者则促使 LM 先做一个简短的计划再写段落，即该计划作为中间的思想步骤。每个任务产生 10 个 IO 和 CoT 样本。我们还考虑了在每个任务的随机 IO 样本之上进行迭代 - 求精的 (k≤5) 方法，其中 LM 以输入约束和最后生成的文章为条件，以决定该通道是否已经 "完美连贯"，如果没有生成精细的文章。

ToT 设置。 我们构建了一个深度为 2 (且仅有 1 个中间思想步骤) 的 ToT-LM 首先生成$k = 5$ 个计划并投票选出最好的一个 (图 4)，然后基于最好的计划生成 $k = 5$ 个通道并投票选出最好的一个。这里宽度限制 $b = 1$ ，因为每一步只保留一个选择。在两个步骤中均使用简单的零样本投票提示 ("分析下面的选择，然后得出结论，哪个是指令最希望的") 采样 5 票。

结果。 图 5 (a) 显示了 100 个任务的平均 GPT-4 得分，其中 ToT (7.56) 被认为比 IO (6.19) 和 CoT (6.93) 平均产生更多的连贯段落。虽然这样的自动度量可能是有噪音的，但图 5 (b) 证实了这一发现，在 100 个文章对中，有 41 个文章对，人类更喜欢 ToT 而不是 CoT，而在 21 (另外 38 对是 "相似连贯的") 文章对中，人类只喜欢 CoT 而不是 ToT。最后，迭代求精在该自然语言任务上更有效，它将 IO 一致性得分从 6.19 提高到 7.67，ToT 一致性得分从 7.56 提高到 7.91。我们认为，它可以被认为是 ToT 框架中思想生成的第三种途径，即新思想可以从提炼旧思想中产生，而不是独立同分布或依次生成。

# 4.3 迷你十字

在《24 游戏》和《创意写作》中，ToT 相对较浅 -- 至多需要 3 个思维步骤才能达到最终输出。这里我们将 5 × 5 迷你纵横字作为一个涉及自然语言的更难的搜索问题进行探讨。再次，目标不仅仅是解决任务，因为更一般的交叉词可以通过专门的 NLP 管道 [31] 轻松解决，它利用大规模检索而不是 LM。相反，我们旨在探索 LM 作为一般问题解决者的极限，它探索自己的思想，并以深思熟虑的推理作为启发式指导自己的探索。

任务设置。 我们从 GooBix 抓取数据，其中包含 156 个 5 × 5 微型纵横字谜游戏。由于我们观察到相邻的游戏包含相似的线索，我们使用 20 个指标为 $1，6，· · ·，91，96$ 的游戏进行测试，用 $136，141，146，151，156$ 的游戏进行提示。对于每个任务，输入描述了 5 条水平线索和 5 条垂直线索，输出应该是 5 × 5 = 25 个字母的棋盘来解决交叉词。对于评估，我们考虑三个成功等级：正确字母 (25 次 / 场)，单词 (每场比赛 10 次) 和游戏。

基线。 我们在 IO 提示符中提供了 5 个示例输入 - 输出对，在 CoT 提示符中额外添加了顺序为 h1..5 然后 v1..5 的中间词。我们对 10 个样本运行每个提示并对结果进行平均。

ToT 设置。 我们利用深度优先搜索 (算法 2)，不断探索最有前途的后续单词线索，直到状态不再有前途，然后回溯到父状态以探索替代思想。为了使搜索容易处理，后续的想法被限制不改变任何填充的单词或字母，因此 ToT 至多有 10 个中间步骤。对于思维生成，在每个状态下，我们将所有现有的思维 ( ( 如 ' h2.motor ; h1.task 在图 6 中的状态 (a)) 转化为字母约束，以获得剩余的线索 ( ( 如 ' v1.To heap: tm___;...') )，并提示一个提案提示 5 次，以提出下一个单词的位置和内容的候选词。

重要的是，我们还提示 LM 对不同的想法给出一个置信水平，并将这些跨提案进行聚合，以获得一个排序的下一步要探索的想法列表 (图 6 (a))。对于状态评估，我们同样将每个状态转化为剩余线索的字母约束，然后对每个线索进行评估，如果给定的约束是可以填充的。如果任何剩余的线索被认为 "不可能" 填写 (如 ' v1.to Heap: tm_s_')，则对状态子树的探索进行剪枝，DFS 回溯到其父节点，以探索下一个有希望的想法。我们将 DFS 搜索步数限制为 100 步，并将最深的探索状态 (首先探讨了多重的情况) 简单地渲染到最终的输出中。

结果。 如表 3 所示，IO 和 CoT 提示方法表现不佳，单词级别的成功率低于 16%，而 ToT 显著提高了所有指标，实现了 60% 的单词级别成功率，并解决了 20 个游戏中的 4 个。这种改善并不奇怪，因为 IO 和 CoT 缺乏机制来尝试不同的线索，改变决策，或者回溯。

甲骨文与消融研究。 当每个任务从 oracle 最佳 DFS 状态 (而不是启发式确定的最佳状态) 输出时，ToT 性能甚至更高，实际上解决了 7 / 20 个游戏 (表 3 , ' + 最佳状态 ')，表明我们的简单输出启发式可以很容易地改进。有趣的是，有时候当填字游戏实际解决时，状态评价者可能仍然认为某些单词是 "不可能的" 并进行修剪 -- 这可能是因为 5 × 5 设计的填字游戏中存在一些 GPT-4 无法识别的稀有或专有单词。考虑到状态评估作为一种剪枝启发式是不完善的，我们也对剪枝进行了探索，发现其性能普遍较差 (表 3,' -prune ')。然而，对于 4 / 20 的游戏 (尽管通过启发式方法只输出 1)，(3) 其中的游戏 ToT + 剪枝无法在 100 步内求解出正确的解。因此，更好的 DFS 剪枝启发式对于这种情况下的问题求解至关重要。最后，我们通过运行一个消融来确认回溯的重要性，该消融在最多 20 个步骤中不断填充最有希望的线索，并允许覆盖。这类似于宽度限制为 b = 1 的 "贪婪" BFS 搜索，并且性能较差，单词级别的成功率仅为 20 % (表 3 ,' -backtrack')。

# 5. 相关工作

规划与决策。 智能规划和决策对于实现预定目标至关重要。由于他们是在大量的世界知识和人类实例的基础上训练的，LMs 已经吸收了丰富的常识，这使得根据问题设置和环境状态 [10、39、34、11、32、38、37] 提出合理的计划成为可能。我们提出的思想树方法扩展了现有的规划公式，在每个解决问题的步骤中同时考虑多个潜在可行的计划，并从最有前途的计划着手。思想采样和价值反馈之间的集成有机地整合了规划和决策机制，实现了在解决方案树内部的有效搜索。另一方面，传统的决策程序通常需要训练专门的奖励和策略模型，如强化学习 (例如 CHAI )，而我们使用 LM 本身来提供决策的价值估计。

自我反思。 使用 LLMs 来评估自身预测的可行性正在成为问题解决中越来越重要的过程。[25、17、21] 引入了 "自我反思" 机制，其中 LM 向他们的后代候选人提供反馈。文献 [ 4 ] 基于 LM 自身的代码执行结果，通过注入 LM 自身产生的反馈消息来提高 LM 的代码生成精度。类似地，[ 14 ] 也引入了对动作和状态的 "评价" 或 "审查" 步骤，以决定在解决计算机操作任务时采取的下一个动作。与我们最近的工作非常相关的另一个工作是 "自评估引导解码" [ 36 ]。与我们的方法类似，自评估解码也遵循一个树型结构过程，从随机波束搜索解码中采样叶子，然后由 LLM 本身用精心准备的自评估提示进行评估。然而，他们的方法使用了将思想表示为代码的 PAL 提法 [ 7 ]，这使得我们在本文中考虑的创造性写作等具有挑战性的任务变得困难。因此，我们的 "思想之树" 提法更具有通用性，能够处理具有挑战性的任务，而 GPT-4 仅在标准提示下达到非常低的准确率。

程序引导的 Llm 生成。 我们的提议还与最近的进展有关，这些进展用象征性的程序指导来组织 LM 的行为。例如，文献 [24] 将 LM 嵌入到算法搜索过程中，以帮助逐步解决问答等问题，其中搜索树由可能提供答案的相关段落展开。然而，这种方法与我们的不同之处在于，树是通过采样外部段落而不是 LM 自己的思想来扩展的，并且没有反射或投票步骤。另一种方法 LLM + P [ 15 ] 更进一步，将实际的规划过程委托给一个经典的规划器。

经典的搜索方法。 最后但并非最不重要的是，我们的方法可以被视为经典搜索方法在问题求解中的现代体现。例如，它可以被认为是一种类似于 A 的启发式搜索算法 [8]，其中每个搜索节点上的启发式由 LM 的自评估提供。从这个角度来看，我们的方法也与文献 [ 16 ] 中提出的 NeuroLogic A esque 译码相关，它受到 A* 搜索的启发，但引入了对 LM 有效的前瞻启发式来改进波束搜索或 top-k 采样译码。然而，这种方法仅限于句子生成任务，而我们的框架是为复杂的、多步骤的问题解决而设计的，并有价值反馈的保护。

# 6. 讨论.

局限性及未来方向。对于 GPT-4 已经擅长的许多现有任务，ToT 等刻意搜索可能不是必要的，作为第一步，本工作只探讨了三个相对简单的任务，这些任务对 GPT-4 提出了挑战，并要求与 LMs 结合更好的搜索和规划能力。然而，随着我们开始在更多的现实决策应用 (例如编码、数据分析、机器人学等。) 中部署 LM，更复杂的任务可能会出现，并为研究这些研究问题提供了新的机会。此外，为了提高任务性能，像 ToT 这样的搜索方法需要比采样方法更多的资源 (如 GPT-4 API 成本)，但是 ToT 的模块化灵活性允许用户自定义这样的性能 - 成本权衡，并且正在进行的开源工作 [ 29 ] 应该在不久的将来很容易地减少这样的成本。最后，这项工作的重点是使用现成的 LM，使用 ToT 风格的高级反事实决策 (例如，审议下一段的潜在选择，而不是预测下一个标记) 微调 LM 可能会带来机会，以增强 LM 的解决问题能力。

更广泛的影响。 ToT 是一个框架，赋予 LM 更自主、更智能地决策和解决问题的能力。虽然目前的任务仅限于推理和搜索问题，但未来涉及与外部环境或人类互动的应用可能会带来潜在的危险，例如促进 LMs 的有害使用。另一方面，ToT 还提高了模型决策的可解释性和人类对齐的机会，因为得到的表示是可读的、高级的语言推理，而不是隐式的、低级的 token。

结论。 LMs 的关联 "系统 1" 可以通过一个 "系统 2" 进行有益的扩展，该 "系统 2" 基于搜索问题解的可能路径树。思维树框架为当代 LM 提供了一种将关于问题解决的经典见解转化为可操作的方法的途径。同时，LMs 解决了这些经典方法的一个弱点，为解决诸如创意写作等不易形式化的复杂问题提供了途径。我们将 LMs 与人工智能的经典方法的交集视为未来工作的一个令人兴奋的方向。