思维树：利用大语言模型进行深度问题解决 [译]

Shunyu Yao 普林斯顿大学 Dian Yu Google DeepMind Jeffrey Zhao Google DeepMind Izhak Shafran Google DeepMind Thomas L. Griffiths 普林斯顿大学 Yuan Cao Google DeepMind Karthik Narasimhan 普林斯顿大学

摘要

语言模型正日益成为处理各类任务不可或缺的工具，但它们在推理时仍旧受限于按顺序逐个标记处理信息的方式。这就导致了在需要探究、战略规划或是初步决策至关重要的任务中，它们的效果可能会打折扣。为了突破这些限制，我们提出了一个新的语言模型推理框架——“思维树”（ToT），这是对现有“思维链”提示方法的一种扩展。它让语言模型能够在连贯的文本单元（我们称之为“思维”）中进行探索，这些“思维”是解题过程中的关键中间步骤。ToT 使得语言模型能够通过权衡多种不同的推理路径和自我评估决策来做出更加深思熟虑的选择，并且能在必要时展望未来或者回顾过去，以作出最佳的全局性决策。我们的实验显示，ToT 显著提升了语言模型在三个需要复杂规划或搜索的新型任务上的解题能力：24 点游戏、创意写作和迷你填字谜。举个例子，在 24 点游戏中，尽管使用“思维链”提示的 GPT-4 只解决了 4% 的问题，而我们的方法却达到了 74% 的高成功率。完整的代码库和所有提示都可以在这个网址找到：https://github.com/ysymyth/tree-of-thought-llm。

1 引言

最初被开发出来产生文本的强大语言模型（LMs），比如 GPT Radford et al.（2018, 2019）；Brown et al.（2020）；OpenAI（2023）和 PaLM Chowdhery et al.（2022），现在已经显示出它们能完成更多种类的任务，这些任务包括数学、符号处理、常识判断和知识推理。这些成就的基础令人意外地仍是最初的文本生成自回归机制，它按顺序逐字地做出选择。但是，这样一个简单的机制真的能够让一个语言模型成为解决各种问题的通用工具吗？如果不能，那么哪些问题会对现有的做事方式构成挑战，我们又该探索什么新的机制呢？

对此，人类认知领域的研究为我们提供了线索。所谓的“双过程”模型研究发现，人在做决定时有两种思维模式：一种是快速、自动、无意识的“系统 1”模式，另一种是缓慢、深思熟虑、有意识的“系统 2”模式 Sloman（1996）；Stanovich（1999）；Kahneman et al.（2002）；Kahneman（2011）。这两种模式已经被应用到机器学习中的许多数学模型之中。例如，关于人和动物在强化学习中是如何在无模型的联想学习和基于模型的规划之间做选择的研究 Daw et al.（2005）。LMs 在选择词元时的简单联想也类似于“系统 1”，这可能意味着通过增加类似“系统 2”的更有策略的规划过程来进行优化是有益的，这个过程不仅能维护并探索当前选择的不同可能性，而且能够评估现状并积极预测未来或重新考虑以做出更全面的判断。

在构思一个规划流程时，我们追溯到人工智能（及认知科学）的发源地，从 1950 年代 Newell、Shaw 和 Simon 对规划流程的探索中寻找灵感 Newell et al. (1959, 1972)。Newell 和他的同事们把问题解决 Newell et al. (1959) 描述为在一个以树形结构表达的组合问题空间里进行搜索。基于此，我们推出了思维树（ToT）框架，旨在通过语言模型来解决一般性问题。图 1 展示了不同于传统方法（下文有详细介绍）仅是连续抽样语言序列来解决问题，ToT 框架主动构建一个思维树，每个节点都是一段有条理的语言序列，作为解决问题的跳板（见表 1）。这种高层次的语义单元使得语言模型能够用语言化的深思熟虑过程来自我评估每个中间思维对解决问题的贡献（参见图 2, 4, 6）。这种通过自我评估和深思来施加搜索策略的做法是创新的，以往的搜索策略不是编程设定就是通过学习得来的。最终，我们将这种基于语言生成和评估各种思维的能力与诸如宽度优先搜索（BFS）或深度优先搜索（DFS）的搜索算法结合起来，使得我们可以系统地、带有预见性地探索思维树并能够回溯。

在实证研究中，我们提出了三个新问题，即使是使用当前最先进的语言模型 GPT-4 OpenAI (2023)，现有的语言模型推理方法也面临挑战：24 点游戏、创意写作和填字游戏（见表 1）。这些任务不仅需要演绎、数学、常识和词汇推理能力，还需要系统的规划或搜索方法。我们证明了 ToT 在这三项任务上都取得了卓越成绩，因为它具有足够的通用性和灵活性，能支持不同级别的思维、生成和评估思维的多种方式，以及能够适应不同问题类型的多种搜索算法。我们还通过系统的剖析来分析这些选择如何影响模型的表现，并讨论如何更好地训练和应用语言模型的未来方向。

图 1: 用于解决问题的多种语言模型（LLMs）方法示意图。每个矩形框代表一个“思维”，它是帮助解决问题的中间环节的一段连贯的语言序列。具体示例请参考图 2, 4, 6，展示了思维如何被生成、评估和搜索。

2 背景

我们首先系统地梳理了一些已有的方法，这些方法利用大语言模型（LM）来解决问题，这为我们的研究提供了灵感，并将在后续进行比较。我们用  $p_{\theta}$ 来表示带有参数 $\theta$ 的预训练语言模型，用小写字母 $x,y,z,s,\cdots$ 来代表语言序列，比如 $x=(x[1],\cdots,x[n])$，其中每个 $x[i]$ 是一个单独的符号。这样，模型对序列的预测可以表示为 $p_{\theta}(x)=\prod_{i=1}^{n}p_{\theta}(x[i]|x[1...i])$。而大写字母 $S,\cdots$ 则用来表示一组语言序列。

输入 - 输出（IO）提示是一种常见的技术，它把问题的输入 $x$ 转换成模型的输出 $y$：$y\sim p_{\theta}(y|\texttt{prompt}_{{IO}}(x))$，这里的 $\texttt{prompt}_{IO}(x)$ 通过任务说明和一些输入输出的例子来包装输入 $x$。为了方便理解，我们定义 $p_{\theta}^{{\rm prompt}}(\texttt{output}\mid\texttt{input})=p_{\theta}(\texttt{output}\mid\texttt{prompt}(\texttt{input}))$，这样我们就可以把 IO 提示简化成这样的形式：$y\sim p_{\theta}^{IO}(y|x)$。

“链式思考”（Chain-of-thought，简称 CoT）的概念由 Wei 等人在 2022 年提出，旨在解决那些输入到输出的转换并不直接的问题，比如数学题（输入 $x$）和它的数值解答（输出 $y$）。CoT 的精髓在于引入一系列的“思考环节” $z_{1},\cdots,z_{n}$，这些环节作为将输入和输出桥接起来的中间步骤，每个环节都是推进问题解决的有意义的语言序列，如数学问题解答中的一个中间步骤方程式（$z_{i}$）。在 CoT 的框架下，解决问题时会依序抽样出每个“思考环节” $z_{i}\sim p_{\theta}^{CoT}(z_{i}\mid x,z_{1\cdots i-1})$，进而得出输出 $y\sim p_{\theta}^{CoT}(y|x,z_{1\cdots n})$。在实践中，会将 $[z_{1\cdots n},y]$ 作为一个整体的语言序列进行抽样，但具体到每个 $z_{i}$ 应该是短语、句子还是段落，这一点并没有明确规定。

而“CoT 自我一致性”（CoT-SC）是 Wang 等人在 2022 年提出的一种改进 CoT 的集成方法。这个方法会独立地抽样出 $k$ 条思考链：$[z^{(i)}_{1\cdots n},y^{(i)}]\sim p*{\theta}^{CoT}(z_{1\cdots n},y|x)\ (i=1\cdots k)$，并选出出现频率最高的结果作为最终输出：$\arg\max_{y}\#{i\mid y^{(i)}=y}$。CoT-SC 在 CoT 的基础上做出改进，因为对于同一个问题，我们通常可以通过不同的思考过程得出答案（如用不同的方法证明同一定理），通过探索更多的思考路径，可以得到更为可靠的决策。但是，它并没有在每条思考链中探索不同的思考步骤，且其“最常见”结果的策略仅在输出选择有限的情况下适用，例如多项选择题。

思维树：利用语言模型刻意解决问题

问题解决是一个循环往复的过程，我们不断利用手头的信息进行探索，每一次探索都会带来新的信息，直到我们找到解决问题的方法。—— Newell 等人 (1959)

人类解决问题的研究显示，人们在一个由各种可能性组成的巨大"思维空间"中寻找答案，这个空间就像一棵树，每个节点代表着解决问题的一部分，而树枝则对应着可以改变这些部分解决方案的操作。我们决定走哪一条路径，通常是基于启发式的规则，这些规则帮助我们在这个复杂的"思维空间"中导航，引导我们找到解决问题的方法。这种视角揭示了目前利用语言模型解决问题方法的两个主要不足：1) 在局部上，它们没有探索思考过程中的不同可能性 —— 即这棵思维树的不同分支。2) 在整体上，它们缺少规划、预见或者是回溯的机制，这种机制可以帮助评估不同的选择，而这正是人类解决问题时常用的方法。

为了克服这些不足，我们提出了一个新的范式，称为“思维树”（ToT），它允许语言模型探索多条推理路径（见图 1(c)）。在这个范式中，任何问题都被构建为一棵树形结构的搜索过程，树上的每个节点代表一个状态 $s=[x,z_{1\cdots i}]$，它表示的是一个部分解决方案，包含了输入信息和到目前为止的思维序列。实现“思维树”需要回答四个问题：1. 如何将问题解决过程分解成单独的思维步骤；2. 如何从每个状态中产生可能的思维；3. 如何用启发式方法评估这些状态；4. 使用哪种搜索算法。

1.  思维的分解。虽然连贯思维（CoT）在没有明确分解的情况下就能抽取出连贯的思维，但“思维树”（ToT）却利用问题本身的特点来设计和分解问题解决的中间步骤。就像表 1 展示的那样，根据不同的问题类型，一个“思维”可能是几个词语组成（如填字游戏），可能是一个方程式（如 24 点游戏），或者是一整段的写作计划（如创意写作）。总的来说，一个“思维”应当足够细致，让语言模型能够生成有前景且多元化的思维样本（比如，生成整本书通常太宏大而难以连贯），但又不能太琐碎，以至于模型能够评估它对解决问题的潜在价值（比如，生成单个词汇通常太细微，难以进行有效评估）。

2. 思考发生器 $G(p_{\theta},s,k)$。面对一个特定的树状状态 $s=[x,z_{1\cdots i}]$，我们会采取两种策略来提出下一个思考阶段的 $k$ 个可能性：

• (a) 通过创意写作提示（如图 4 所示的 CoT 提示）随机产生独立同分布的思考：$z^{(j)}\sim p_{\theta}^{CoT}(z_{i+1}|s)=p_{\theta}^{CoT}(z_{i+1}|x,z_{1\cdots i})\ (j=1\cdots k)$。这种方法在思考空间较为丰富时（比如每个思考是一段文字）效果更佳，因为独立同分布的样本可以带来多样性；

• (b) 通过“提案提示”连续产生思考（如图 2 中的 24 点游戏和图 6 中的填字游戏）：$[z^{(1)},\cdots,z^{(k)}]\sim p_{\theta}^{propose}(z_{i+1}^{(1\cdots k)}\mid s)$。在思考空间较为限制的情况下（例如每个思考只是一个单词或者一行），这样做可以在相同的上下文中提出不同的思考，避免重复。

3. 状态评估器 $V(p_{\theta},S)$。给定一系列不同的状态前沿，状态评估器会评价它们向解决问题所做的进展，充当搜索算法决策保持哪些状态探索以及选择顺序的启发式工具。尽管启发式通常是解决搜索问题的标准做法，它们要么是预先编程的（比如 DeepBlue (Campbell et al., 2002)），要么是通过学习得到的（比如 AlphaGo Silver et al. (2017)）。我们提出了第三种选择，通过利用语言模型（LM）来有目的地思考状态。当可行时，这种刻意的启发式方法可能比固定的规则更加灵活，比学习模型更加高效。与思考发生器类似，我们也有两种策略来独立或者共同评估状态：

4. (a) 独立评价各个状态：$V(p_{\theta},S)(s)\sim p_{\theta}^{value}(v|s)\ \forall s\in S$，这里面我们通过一个价值提示对状态 $s$ 进行思考，以产生一个数值 $v$ （比如 1 到 10 之间）或者是一个分类（比如：肯定/可能/不可能）。这样的分类可以通过启发式方法转换为具体数值。这种评估推理的依据因问题而异，思考的步骤也不尽相同。在本研究中，我们通过少量预先模拟（例如：迅速验证 5, 5, 14 是否能通过计算 5 + 5 + 14 得到 24，或者“hot_l”是否能通过在“_”填入“e”成为“inn”）以及运用常识（例如：1 2 3 太小，不可能加到 24，或者没有哪个单词是以“tzxc”开头的）。前者有助于识别“好”的状态，而后者则有助于排除“坏”的状态。这种估值没有要求完美无缺，只需要大致准确就行。

5. (b) 跨状态投票：$V(p_{\theta},S)(s)=\mathds{1}[s=s^{*}]$，在这里，我们选出一个“好”的状态 $s^{*}\sim p_{\theta}^{vote}(s^{*}|S)$，这是通过在集合 $S$ 中仔细比较不同状态后进行的投票决定。当直接评估问题的成功程度比较困难时（比如段落的连贯性），自然就会比较不同的部分解决方案，然后投票决定最有前景的一个。这种做法精神上类似于“逐步”自我一致性策略，也就是将“选择哪个状态进行探索”看作是一个多项选择问题，并依据语言模型（LM）的样本来进行投票。

对于这两种策略，我们可以多次向语言模型（LM）提问，以聚合价值或投票结果，这样可以在时间/资源/成本上做出权衡，以获得更可靠的启发式评价。

算法 1 ToT-BFS（$x,p\_{\theta},G,k,V,T,b$）

Input $x$, LM $p_{\theta}$, thought generator $G()$ & size limit $k$, states evaluator $V()$, step limit $T$, breadth limit $b$.

$S_{0}\leftarrow\{x\}$

for $t=1,\cdots,T$ do

    $S^{\prime}_{t}\leftarrow\{[s,z]\mid s\in S_{t-1},z_{t}\in{\mathrm{G}}(p_{\theta},s,k)\}$

    $V_{t}\leftarrow V(p_{\theta},S^{\prime}_{t})$

    $S_{t}\leftarrow\arg\max_{S\subset S^{\prime}_{t},|S|=b}\sum_{s\in S}V_{t}(s)$

end for

return $G(p_{\theta},\arg\max_{s\in S_{T}}V_{T}(s),1)$

算法 2 ToT-DFS($s,t,p_{\theta},G,k,V,T,v_{\small th}$)

Current state $s$, step $t$, LM $p_{\theta}$, thought generator $G()$ and size limit $k$, states evaluator $V()$, step limit $T$, threshold $v_{\small th}$

if $t>T$ then record output $G(p_{\theta},s,1)$

end if

for $s^{\prime}\in G(p_{\theta},s,k)$ do$\triangleright$ sorted candidates

    if $V(p_{\theta},\{s^{\prime}\})(s)>v_{\small thres}$ then$\triangleright$ pruning

        DFS$(s^{\prime},t+1)$

    end if

end for

4. 搜索算法。最后，在 ToT 框架中，根据树状结构的不同，我们可以选择并运用不同的搜索算法。我们这里介绍了两种比较简单的搜索算法，并将更复杂的算法（例如 A* 算法 Hart 等人提出的 (1968b)，MCTS 算法 Browne 等人提出的 (2012)）留给未来的研究。

1. (a)

广度优先搜索（BFS）（算法 1）是一种每一步只保留最有潜力的 $b$ 个状态的方法。这种方式被应用于 24 点游戏和创意写作等领域，这些领域的树深度有限（$T\leq 3$），并且可以将初始的思考步骤评估后缩减成一个小规模的集合（$b\leq 5$）。

2. (b)

   深度优先搜索（DFS）（算法 2）则是优先探索最有前景的状态，一直进行到找到最终的答案（$t>T$），或者当评估器判断当前状态 $s$ 无法解决问题时停止（即当 $V(p\_{\theta},{s})(s)\leq v\_{th}$ 时，这里 $v\_{th}$ 是一个预设的阈值）。在后一种情况下，从状态 $s$ 扩展出的子树将被裁剪，这是为了在探索和利用之间找到一个平衡。不管哪种情况，DFS 都会回溯到状态 $s$ 的上一级状态，继续进行探索。

从概念上讲，ToT 作为一种通用的问题解决方法，对于语言模型（LM）来说有多个优势：（1）通用性。输入输出（IO）、对话树（CoT）、带限制的对话树（CoT-SC）以及自我改善都可以视为 ToT 的特殊案例（也就是说，它们是深度和宽度有限的树；见图 1）。（2）模块化。基础语言模型和思考的拆分、生成、评估和搜索过程都可以独立改变。（3）适应性。能够适应不同的问题属性、语言模型的能力和资源限制。（4）方便性。使用 ToT 方法不需要额外的训练，仅需一个预训练的语言模型即可。下一节将展示这些概念优势是如何在实践中转化为在各种问题上的出色表现。

4 实验部分

表 1：任务概览。输入、输出和思路示例用蓝色标出。

我们设计了三项即便对于利用最新的语言模型 GPT-4（OpenAI, 2023）进行样本抽取也颇具挑战性的任务，这些任务在采用标准输入输出提示或连锁思考提示时难度不小。我们展示了通过在思考树（ToT）中进行精心搜索可以获得更优结果，更关键的是，我们探索了利用语言模型解决需要搜索或计划的问题的新方法。除特别说明外，我们的实验是在 Chat Completion 模式下进行的 GPT-4，其采样温度设定为 0.7。

4.1 24 点游戏解析

24 点游戏是一种脑力激荡的数学游戏，玩家需要运用四个数字和基础算术运算（加减乘除）来凑出数字 24。比如，如果游戏给出的数字是“4 9 10 13”，那么一个可能的解决方案就是“(10 - 4) * (13 - 9) = 24”。

图 2: 在 24 点游戏中的 ToT 体验。LM 被用来提示（a）思考过程的生成和（b）价值评估。

表 2: 24 点游戏的解题结果。

表 2: 24 点游戏的解题结果再现。

图 3: 24 点游戏中的（a）难度级别分析和（b）错误类型分析。

任务设定。我们从 4nums.com 网站上搜集了 1,362 个按照人类解题时间由易到难排列的游戏数据，并选取了其中的难度较高的一部分（编号 901-1,000）作为测试样本。每个任务中，如果输出是一个有效的、计算结果为 24 的方程式，并且每个输入的数字都刚好用了一次，我们就认为这是一个成功的解题。我们以 100 场游戏中的成功次数作为衡量标准来报告成功率。

基线测试。在我们的测试中，我们采用了一个包含 5 个相关实例的标准输入输出（IO）提示方式。对于“思维链条”（CoT）提示，我们会在每个输入输出示例中加入 3 个中间步骤的方程式，这些方程式处理剩下的两个数字。比如，对于输入“4 9 10 13”，思考过程可能是：“13 - 9 = 4（剩下：4 4 10）；10 - 4 = 6（剩下：4 6）；4 * 6 = 24（剩下：24）”。为了评估平均性能，我们会对每个游戏进行 100 次 IO 和 CoT 提示的抽样测试。我们还设置了一个 CoT 自洽性的基准线，即从 100 个 CoT 提示样本中选出多数结果，以及在 IO 提示样本的基础上，最多进行 $10$ 轮迭代的细化方法。在每次迭代中，如果输出错误，模型将会基于之前的所有历史信息进行反思，以产生一个更精确的答案。注意，这里会用到关于方程正确性的真实反馈信号。

ToT 设置。为了将“24 点游戏”转化为 ToT 问题，我们自然而然地把思考过程分为 3 个步骤，每个步骤都是一个中间方程式。正如图 2(a) 中展示的，在每个树节点，我们都会提取剩余的数字，然后提示语言模型（LM）提出可能的下一步操作。尽管这种“提议提示”在全部 3 个步骤中都是一样的，但它实际上只有一个例子是包含了 4 个输入数字的。我们在 ToT 中采用广度优先搜索（BFS），在每一步中，我们会保留最好的 $b=5$ 个候选项。为了在 ToT 中进行深思熟虑的 BFS，如图 2(b) 所示，我们会引导语言模型评估每一个思考步骤是“确定/可能/不可能”达到 24 点。这样做的目的是为了快速筛选出可能正确的部分答案，并且剔除那些因为“数字太大或太小”而不可能的方案，保留那些“可能”的方案。我们对每个思考过程抽样测试 3 次。

研究结果。正如表 3(#S4.F3) 中展示的，IO、CoT 和 CoT-SC 这几种提示方法在完成任务上的表现较差，成功率仅为 7.3%、4.0% 和 9.0%。而相比之下，ToT 方法即使在宽度为 $b=1$ 的情况下也已经取得了 45% 的成功率，当宽度为 $b=5$ 时，成功率更是高达 74%。我们进一步设想了一个理想情况下的 IO/CoT，即通过计算在最多 100 个样本中挑选出的最佳样本的成功率（$1\leq k\leq 100$）。为了和 ToT 进行比较，我们统计了 ToT 中每项任务需要访问的树节点数量，对于宽度 $b=1\cdots 5$，并在图 3(#S4.F3)(a) 中对应出了这五种情况的成功率，把 IO/CoT（最佳的 $k$）视作在赌博机模型中访问了 $k$ 个节点。不出所料，CoT 比 IO 的扩展性更好，最佳的 100 个 CoT 样本的成功率为 49%，但这个数字仍远低于在 ToT 中增加节点探索（$b>1$）所达到的效果。

错误分析。图 3(#S4.F3)(b) 揭示了 CoT 和 ToT 方法在完成任务过程中的哪一步骤出现了问题，也就是在 CoT 中的想法或在 ToT 中的所有 $b$ 个想法是无效的，或者无法正确推导出结果 24。特别是，大约 60% 的 CoT 样本在任务的第一步就失败了，也就是说，在生成了第一步的三个单词（比如“$4+9$”）之后就出错了。这一发现凸显了从左到右直接解码方法存在的问题。

4.2 创意写作

接下来，我们设计了一个创意写作任务，要求参与者从四个随机的句子出发，创作出一个包含四个段落的连贯文段，每个段落都以这四个随机句子之一作为结尾。这样的任务没有固定的答案，旨在鼓励开放性的探索和创造力的发挥，同时也考验参与者的高层次规划能力。

任务设置。我们从 randomwordgenerator.com 网站随机选取句子，形成了 100 个任务输入。每个输入的约束条件并没有预设的正确文段。鉴于 GPT-4 在大多数情况下能够遵循输入的约束，我们的评估重点是文章连贯性：一方面通过 GPT-4 未经训练的提示，给出一个 1 到 10 的连贯性评分；另一方面通过人工评审，比较不同方法产生的文段对的连贯性。在评分方面，我们对每个任务输出抽取五个评分并计算平均值，这些评分通常较为一致，平均标准差约为 $0.56$。在人工评审方面，我们邀请了部分论文作者盲审，比较了在 100 个任务输入中，基于链式推理（CoT）和目标导向任务（ToT）生成的文段对的连贯性，并且评审时会随机调换文段对的顺序。

基线设置。考虑到任务本质的创造性，即时输出（IO）和链式推理（CoT）的提示都是零次尝试，即未经训练。IO 提示直接引导语言模型（LM）根据给定的输入约束生成连贯文段，而 CoT 提示则要求语言模型先制定一个简短计划，再基于该计划写作文段，这样的计划就像是一个中间的思考步骤。每个任务我们生成 10 个 IO 和 CoT 的样本。我们还尝试了一种迭代精炼方法（$k\leq 5$），在这种方法中，语言模型会根据输入约束和前一次生成的文段判断当前文段是否“完全连贯”，如果不是，则生成一个更加精炼的版本。

ToT 设置。我们构建了一个深度为 2 的 ToT 模型（只有一个中间思考步骤）——语言模型首先生成 $k=5$ 个计划，并对最佳计划进行投票（见图 4），然后基于这个最佳计划生成 $k=5$ 个文段，并再次投票选出最佳文段。这里我们设置了宽度限制为 $b=1$，也就是说，每一步骤中只保留一个选项。我们使用了一个简单的零次尝试投票提示（“分析下方的选项，然后总结出哪一个最符合指令要求”），在两个步骤中分别进行 5 次投票。

研究成果揭晓。图 5(a) 展示了 GPT-4 在 100 项任务中的平均表现，ToT 方案（得分为 7.56）在生成连贯文段方面，平均表现优于 IO 方案（得分为 6.19）和 CoT 方案（得分为 6.93）。虽然这类自动化的评估方法可能存在误差，图 5(b) 的数据却证实了这一点，人类评审在 100 组文段对比中，41 组更偏爱 ToT 方案，而只有 21 组偏爱 CoT 方案（其余 38 组的连贯性被评为“相似”）。此外，在处理自然语言任务时，迭代优化方法显示出更高的效果，它使得 IO 方案的连贯性得分从 6.19 提高到了 7.67，ToT 方案的得分也从 7.56 提升到了 7.91。我们认为，这种方法可以视为 ToT 框架下的第三种思考生成方式，新的思考是通过对旧思考的不断优化，而非独立同分布或顺序生成的方式。

图 4: 展示了在一个随机选择的创意写作任务中，经过深思熟虑的搜索步骤。给定输入之后，语言模型（LM）会生成 5 种不同的计划，然后进行 5 轮投票来选出最佳方案。选出的方案会被用来按照同样的抽样 - 投票流程编写输出文段。

图 5: 创意写作结果展示。

方法成功率（%）字母拼字游戏 IO 38.7140 CoT 40.615.61 ToT（我们的方法）786020+ 最优状态 82.467.535-修剪 65.441.55-回溯 54.6205

图 5: 展示了创意写作的成果。

表 3: 展示了迷你填字游戏的结果。

4.3 迷你填字游戏

图 6: 在迷你填字游戏中，(a) 描述了如何将思路提出并汇总到优先队列中以进行深度优先搜索 (DFS)，(b) 介绍了基于填完每个剩余字谜线索的可能性来评估状态，并且如果任何剩余线索无法被语言模型 (LM) 填写，就将其剪除。之后，DFS 将回溯至上一个状态，继续探索下一个有希望的解题思路。

在 24 点游戏和创意写作中，思考的步骤相对较少 —— 通常最多需要 3 步就能得出最终答案。在这里，我们将目光投向了 $5\times 5$ 的迷你填字游戏，这是一个涉及自然语言处理、搜索难度更大的问题。目标不仅仅是解开谜题，毕竟使用特定的自然语言处理 (NLP) 技术（如 Wallace 等人在 2022 年的研究），可以轻松解决更普通的填字游戏，因为它们依赖大规模的数据检索而不是语言模型。我们的目标是测试语言模型作为一个全面的问题解决工具的潜力，它如何探索自己的思维，并用深思熟虑的推理作为指导手段来引导自己的探索。

任务设置。我们从 GooBix 收集了包含 156 个 $5\times 5$ 迷你填字游戏的数据。由于我们发现相邻游戏的线索很相似，我们选取索引为 $1,6,\cdots,91,96$ 的 20 个游戏作为测试对象，以及索引为 $136,141,146,151,156$ 的 5 个游戏用于出题。每个任务中，输入将包含 5 个横向线索和 5 个纵向线索，输出则应为一个由 $5\times 5=25$ 个字母组成的棋盘，用以解决填字谜题。在评估时，我们将从三个层面来衡量成功：正确的字母数量（每场游戏 25 个），正确的单词数量（每场游戏 10 个），以及整个游戏的解答情况。

基准测试。我们在输入输出 (IO) 提示中提供了 5 组示例，而在思考过程 (CoT) 提示中，我们还包括了按照 h1..5 和 v1..5 顺序出现的中间单词。我们对每个提示进行了 10 次样本测试，并对结果进行了平均。

在 ToT 方案中，我们使用了一种深度优先搜索策略（详见算法 2），这种策略会不断追寻看起来最有解答前景的单词提示，直到没有更多可能的发展，然后返回到上一层，尝试其他可能的解答路径。为了让搜索过程变得更加高效，我们设定了规则限制，在后续的思考过程中不能更改已经填好的单词或字母，这样的话 ToT 的搜索步骤最多只有 10 步。在思维生成阶段，我们会将所有已有的想法（比如在图 6(a) 所示的状态中就是“h2.motor; h1.tasks”）转化为剩余线索的字母限制（例如“v1. 堆积：tm___;…”），并进行 5 次建议性提示，来决定下一步填写哪个单词以及填写的内容。更关键的是，我们会引导语言模型（LM）对不同的思维路径给出置信度评分，并将这些评分集合起来，形成一个有序的待探索思维列表（如图 6(a) 所示）。在状态评估过程中，我们也会用相似的方法，根据剩余线索的字母限制来评估每个线索能否被合理填写。如果发现任何剩余线索在当前条件下无法完成填写（比如“v1. 堆积：tm_s_”），我们就会停止对该状态子树的探索，并返回上一层，寻找下一个有希望的解答路径。我们把深度优先搜索的步骤限制在 100 步以内，并将探索得最深的状态（如果有多个，则选第一个）作为最终结果展示出来。

结果显示，如表 5 所示，IO 和 CoT 这两种提示方式效果不佳，单词成功率不到 16%，而 ToT 方法则在各项指标上都有显著提升，单词成功率达到了 60%，并且在 20 个挑战中解决了 4 个。这种进步并不出乎意料，因为 IO 和 CoT 方法缺少尝试不同线索、修改先前选择或进行回溯的功能。

神谕（Oracle）与优化研究。当我们从所谓神谕（Oracle）定义的最佳深度优先搜索（DFS）状态输出答案，而不是依赖我们的启发式算法来确定最佳状态时，任务胜率（ToT）表现更上一层楼，竟然能解决 7/20 个游戏（参见 表 5：“+best state”），这说明我们目前使用的简单输出启发式方法有很大的改进空间。有趣的是，有时候即使填字游戏已经被解开，状态评估器仍可能会错误地标记某些单词为“不可能”的，并将其剔除 —— 这可能是因为 $5\times 5$ 的填字游戏故意设计了一些 GPT-4 无法识别的稀有或已过时的词汇。考虑到用作剪枝的状态评估启发式算法并非完美，我们还尝试了去除剪枝步骤，发现这样做通常会降低效果（参见 表 5：“-prune”）。然而，这种方法实际上找到了 4/20 游戏的正确答案（尽管通过启发式策略只输出了一个），其中 3 个是在 100 步之内，使用剪枝的 ToT 方法无法解决的游戏。因此，为深度优先搜索（DFS）设计更好的剪枝启发式方法对于解题至关重要。最后，我们通过实施一个实验来验证回溯法的重要性，该实验允许在最多 20 步内填写最有可能的线索，并允许覆盖原有答案。这与限制宽度为 $b=1$ 的“贪心”宽度优先搜索（BFS）类似，但其效果不佳，单词级成功率仅有 $20\%$（参见 表 5：“-backtrack”）。

5 相关研究

规划与决策。在实现既定目标的过程中，高效的规划和决策至关重要。由于语言模型（LMs）接受了大量的世界知识和人类经验的训练，它们已经内化了丰富的常识，足以在面对不同的问题情境和环境条件时提出合理的规划方案（参见 Huang 等人 2022a；Zhang 等人 2023；Wang 等人 2023b；Huang 等人 2022b；Wang 等人 2023a；Yao 等人 2022；Yang 等人 2023）。我们提出的 "思维树"（Tree-of-Thought）方法在此基础上做了拓展，它在问题解决的每一步都考虑多个可能的规划方案，并优先发展那些最有希望的方案。这种将思维样本与价值反馈结合的方式，将规划和决策机制有机融合，使我们能够在解决方案树中有效地搜索。而传统决策流程通常需要训练专用的奖励和策略模型，如在强化学习中所见（例如 CHAI（Verma 等人 2022）），我们则直接利用 LM 来提供决策所需的价值评估。

自我反思。越来越多地，我们使用大语言模型（LLMs）来检验它们自己的预测结果，这一做法在解决问题的过程中显得格外重要。Shinn 等人 2023；Madaan 等人 2023；Paul 等人 2023 提出了一种“自我反思”机制，在这个机制中，语言模型对自己生成的内容提出反馈。Chen 等人 2023 通过加入由语言模型基于代码执行结果自生成的反馈信息，提升了代码生成的准确度。类似地，Kim 等人 2023 也提出了一种在计算机操作任务解决过程中，对行动和状态进行“评判”或复审的步骤，以确定接下来的行动。与我们的研究密切相关的另一个最新工作是“自评引导解码”（Xie 等人 2023）。这种方法和我们的类似，采用了树状搜索程序，搜索过程中的分支由随机波束搜索解码得到的样本构成，然后由语言模型本身使用精心设计的自评提示进行评估。不过，他们的方法采用了 PAL 公式（Gao 等人 2023），将思维过程表达为代码，这在处理像我们论文中探讨的创意写作这样的复杂任务时显得力不从心。因此，我们提出的“思维树”框架更加通用，能够应对 GPT-4 仅通过标准提示就难以准确处理的复杂任务。

程序引导的 LLM 生成。我们的建议也与最近一些利用符号程序引导来整理语言模型行为的先进做法相关。比如 Schlag 等人 2023 提出的方法，他们将语言模型融入到算法搜索过程中，辅助逐步解答问题，比如通过扩展搜索树与问题答案相关的段落来解答问题。然而，这种方法与我们的不同在于，它通过抽取外部段落而不是语言模型自己的思考来扩展搜索树，并且没有包含反思或投票的步骤。LLM+P 方法（Liu 等人 2023）则更进一步，将规划过程直接委托给一个传统的规划器。

经典搜索策略再升华。最后但同样重要的一点是，我们的方法可以看作是将古老的解题搜索技巧融入现代技术之中。例如，我们的方法可以视作是一种启发式搜索算法，有点像 A* 算法（Hart et al., 1968a），在这种算法中，每个搜索节点的启发式评估都是由语言模型（LM）的自我评估所提供的。从这个视角出发，我们的方法还与在（Lu et al., 2021）中提出的类似 NeuroLogic A* 的解码方法有关，该方法虽然是由 A* 搜索启发而来，但加入了先见之明的启发式，这对于语言模型（LM）来说，在改进 beam-search 或 top-k 抽样解码方面非常有效。然而，这种方法只适用于句子生成任务，而我们的框架是为了应对那些复杂、需要多步骤推理的问题而设计的，整个过程都受到价值反馈的监督和指导。

6 讨论

局限性与未来展望。精心设计的搜索机制，如 ToT，在 GPT-4 已经擅长的许多任务中可能并非必不可少。作为初步尝试，我们只探讨了三个挑战 GPT-4 的相对简单任务，这些任务呼唤将更高级的搜索和规划能力融入语言模型（LM）中。然而，当我们开始将 LM 应用于更多真实世界的决策场景（如编程、数据分析、机器人技术等），可能会涌现出更为复杂的任务，为探索这些研究问题带来新的机遇。同时，ToT 这类搜索方法相较于抽样方法在提升任务性能时需要消耗更多资源（比如 GPT-4 API 的成本），但 ToT 的模块化设计为用户提供了性能与成本之间的定制选择，而持续的开源工作（Touvron 等人，2023）预计会在不久的将来降低这些成本。最终，本研究主要利用现成的 LM，并且通过微调，将 ToT 风格的高层次反事实决策（例如，在写作中权衡下一段的可能选择，而不仅仅是预测下一个词）融入，可能会开辟提升 LM 问题解决能力的新途径。

更广泛的影响。ToT 框架赋予了语言模型更为自主和智能的决策与问题解决能力。尽管目前的应用局限于推理和搜索问题，但未来的应用可能涉及与外部环境或人类的交互，这可能带来潜在的危险，例如可能被用于不良用途的语言模型。另一方面，ToT 还增强了模型决策的可解释性和与人类意图的对齐，因为它产生的是可读的、高层语言推理，而非隐晦的低级词汇。

结论。语言模型的直觉式“系统 1”可以通过一个基于潜在解决方案路径搜索的“系统 2”得到有效的补充。思维树框架为我们提供了一种新的视角，将关于解决问题的传统洞见转换成适用于现代语言模型的实际方法。与此同时，语言模型还弥补了这些传统方法的不足，帮助解决那些难以规范化的复杂问题，例如创造性写作。我们认为，语言模型与传统人工智能方法的结合，为未来的研究开辟了一条激动人心的新路径。