摘要

语言模型正日益广泛地部署于解决各类通用任务，但在推理过程中仍受限于基于词元、从左至右的决策模式。这意味着它们在处理需要探索性、战略性前瞻或初始决策起关键作用的任务时可能存在不足。为克服这些挑战，我们提出了一种新的语言模型推理框架——“思维树”（ToT），该框架推广了当前流行的“思维链”提示方法，允许模型对作为问题解决中间步骤的连贯文本单元（即“思维”）进行系统性探索。ToT使语言模型能够通过考量多种推理路径、对选择进行自我评估以确定后续行动方案，并在必要时通过前瞻或回溯机制做出全局决策，从而实现审慎的决策过程。实验表明，在需要复杂规划或搜索的三个新任务（24点游戏、创意写作和迷你填字游戏）中，ToT显著提升了语言模型的问题解决能力。例如在24点游戏中，采用思维链提示的GPT-4仅能解决4%的任务，而我们的方法达到了74%的成功率。

论文

代码

1.引言

最初为生成文本而设计的语言模型（如GPT[25, 26, 1, 23]和PaLM[5]），其规模化扩展版本已被证明能越来越胜任更广泛的任务，这些任务需要数学、符号、常识及知识推理能力。或许令人惊讶的是，所有这些进展的基础，仍然是原始的自回归文本生成机制——以从左到右的方式逐个进行词元级决策。如此简单的机制是否足以让语言模型发展为通用问题求解器？如若不然，哪些问题将挑战当前范式？又应存在何种替代机制？

关于人类认知的文献为回答这些问题提供了线索。针对“双过程”模型的研究表明，人们处理决策时存在两种模式——一种快速、自动、无意识的模式（“系统1”）和一种缓慢、审慎、有意识的模式（“系统2”）[30, 31, 16, 15]。这两种模式先前已与机器学习中使用的多种数学模型相关联。例如，对人类及其他动物强化学习的研究，探索了他们在何种情况下进行联想式的“无模型”学习，或进行更审慎的“基于模型”的规划[7]。语言模型在词元层面所做的简单联想式选择也令人联想到“系统1”，因此或许能够受益于更审慎的“系统2”规划过程的增强，该过程能够（1）为当前选择而非单一抉择维持并探索多样化的备选方案。以及（2）评估当前状态，并主动前瞻或回溯以作出更具全局性的决策。

为设计这样的规划过程，我们回溯人工智能（及认知科学）的起源，从纽厄尔、肖和西蒙自1950年代开始探索的规划过程中汲取灵感[21, 22]。纽厄尔及其同事将问题解决[21]描述为在组合问题空间中的搜索，该空间以树形结构表示。因此，我们提出了“思维树”（ToT）框架，用于语言模型的通用问题求解。如图1所示，现有方法（下文详述）通过采样连续语言序列来解决问题，而ToT则主动维护一棵思维树，其中每个思维都是一个连贯的语言序列，作为解决问题的中间步骤（表1）。这种高层语义单元使语言模型能够通过同样以语言实例化的审慎推理过程（图2,4,6），自我评估不同中间思维在解决问题过程中取得的进展。这种通过语言模型自我评估与深思来实现搜索启发式的方法是新颖的，因为以往的搜索启发式要么依赖编程实现，要么通过机器学习获得。最后，我们将这种基于语言的多样化思维生成与评估能力，与广度优先搜索（BFS）或深度优先搜索（DFS）等搜索算法相结合，从而能够通过前瞻与回溯机制对思维树进行系统性探索。

图1：采用大语言模型解决问题的多种方法示意图。每个矩形框代表一个思想单元，即作为问题解决中间步骤的连贯语言序列。具体的思想生成、评估与搜索方法示例如图2、图4、图6所示。

从实证角度出发，我们提出了三个新问题，即使采用最先进的语言模型GPT-4[23]也会挑战现有的LM推理方法：二十四点游戏、创意写作与填字游戏（表1）。这些任务需要演绎、数学、常识与词汇推理能力，以及整合系统性规划或搜索的方法。我们证明，思维树（ToT）通过在通用性和灵活性上支持不同层级的思维、不同的思维生成与评估方式，以及适应不同问题性质的搜索算法，在所有三项任务中均取得了优异结果。我们亦通过系统性消融实验分析了这些选择如何影响模型性能，并讨论了如何更好地训练和使用语言模型的未来方向。

表1：任务概览。输入、输出、思考示例如蓝色所示。

2.背景

我们首先将现有利用大语言模型进行问题求解的方法形式化，这些方法启发了我们的研究思路并将在后续进行对比。我们使用 $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]\mid x[1\dots i])$ 。我们使用大写字母 $S,\cdots$ 表示语言序列的集合。

输入-输出（IO）提示词是将问题输入x转化为语言模型输出y最常用的方法：$y\sim p_{\theta }(y|promp{t}_{IO}(x))$，其中$promp{t}_{IO}(x)$通过任务指令和/或少样本输入-输出示例对输入x进行封装。为简化表述，我们记$p_{\theta }^{prompt}(输出|输入)=p_{\theta }(输出|prompt(输入))$，从而可将IO提示形式化表示为$y\sim p_{\theta }^{IO}(y|x)$。

思维链提示 [38] 的提出，旨在处理输入 x 到输出 y 的映射关系非平凡的情况（例如当 x 是一个数学问题，而 y 是最终数值答案时）。其核心思想是引入一个思维链 $z_1,\cdot \cdot \cdot ,z_n$ 来连接 x 和 y，其中每个 $z_i$都是一个连贯的语言序列，作为问题求解过程中有意义的中间步骤（例如，在数学问答中，$z_i$ 可以是一个中间方程式）。在使用思维链解决问题时，每个思维 $z_i\sim p_{\theta }^{CoT}(z_i|x,z_{1\cdot \cdot \cdot i-1})$ 被依次采样生成，随后输出 $y\sim p_{\theta }^{CoT}(y|x,z_{1\cdot \cdot \cdot n})$。在实践中，$[z_{1\cdot \cdot \cdot n},y]\sim p_{\theta }^{CoT}(z_{1\cdot \cdot \cdot n},y|x)$ 是作为一个连续的语言序列被采样的，而思维的具体分解方式（即每个 $z_i$ 是一个短语、句子还是段落）则保持模糊。

思维链自洽性（CoT-SC）[36] 是一种集成方法，它采样 k 条独立同分布的思维链：$[z_{1\cdot \cdot \cdot n}^{(i)},y^{(i)}]\sim p_{\theta }^{CoT}(z_{1\cdot \cdot \cdot n},y|x)(i=1\cdot \cdot \cdot k)$，随后返回最频繁出现的输出： arg ⁡ max ⁡ y # { i ∣ y ( i ) = y } . \arg\max_y\#\{i\mid y^{(i)}=y\}. argmaxy​#{i∣y(i)=y}.。CoT-SC 相较于 CoT 有所改进，因为针对同一问题通常存在不同的思维过程（例如，证明同一定理的不同方法），通过探索更丰富的思维集合，输出决策可以更为可靠。然而，在每条思维链内部，并未对不同思维步骤进行局部探索，且“最频繁”启发式方法仅适用于输出空间有限的情况（例如，多项选择题问答）。

3.思维树：利用语言模型进行审慎问题求解

真正的解题过程涉及反复利用已有信息启动探索，这种探索会逐步揭示更多信息，直至最终找到解决问题的方法。——纽厄尔等人[21]

对人类问题解决的研究表明，人们会在组合问题空间中进行搜索——这是一种树状结构，其中节点代表局部解，分支对应修改这些解的算子[21, 22]。选择哪条分支由启发式方法决定，这些方法有助于在问题空间中导航并引导问题解决者找到解决方案。这一视角凸显了现有利用语言模型解决通用问题方法的两个关键缺陷：1）局部层面，它们不在思维过程中探索不同的延续路径——即树的各个分支；2）全局层面，它们未融入任何形式的规划、前瞻或回溯机制来评估这些不同选项——而这正是人类问题解决过程中特有的启发式引导搜索。

为应对这些不足，我们提出了思维树（ToT）范式，使语言模型能够在思维路径上进行多分支推理探索（图1©）。ToT将任何问题框架化为对一棵树的搜索，其中每个节点是一个状态 $s=[x,z_{1\cdot \cdot \cdot i}]$，表示由输入和当前思维序列构成的局部解。ToT的具体实现涉及回答四个问题：1. 如何将中间过程分解为思维步骤；2. 如何从每个状态生成潜在思维；3. 如何启发性地评估状态；4. 使用何种搜索算法。

1. 思想分解。虽然思维链（CoT）会连贯地采样思想而不进行显式分解，但思维树（ToT）利用问题特性来设计和分解中间思考步骤。如表1所示，根据问题的不同，一个思想可以是几个单词（填字游戏）、一行等式（24点游戏）或一整段写作计划（创意写作）。一般而言，思想应当足够“小”，以使语言模型能够生成有前景且多样化的样本（例如生成整本书通常过于“庞大”而难以保持连贯性）；同时又应足够“大”，以便语言模型能够评估其解决问题的前景（例如生成单个标记通常过于“微小”而难以评估）。
   

2. 思维生成器 $G(p_{\theta },s,k)$。给定树状态 $s=[x,z_{1\cdot \cdot \cdot i}]$，我们采用两种策略来为下一个思维步骤生成 k 个候选：
   (a) 从思维链提示中独立同分布地采样思维（创意写作，图4）：$z^{(j)}\sim p_{\theta }^{CoT}(z_{i+1}|s)=p_{\theta }^{CoT}(z_{i+1}|x,z_{1\cdot \cdot \cdot i})(j=1\cdot \cdot \cdot k)$。当思维空间足够丰富时（例如每个思维是一个段落），此方法效果更佳，且独立同分布采样能带来多样性；

图4：随机选取的创意写作任务中的一步审慎搜索。给定输入后，语言模型首先采样5种不同的规划方案，随后进行5轮投票以确定最佳方案。多数票选择的方案将用于后续输出段落的生成，此生成过程同样采用采样-投票流程。

(b) 提出顺序思维(使用“提议提示”)(24点游戏，图2；填字游戏，图6)：$[z^{(1)},\cdot \cdot \cdot ,z^{(k)}]\sim p_{\theta }^{propose}(z_{i+1}^{(1\cdot \cdot \cdot k)}|s)$。当思维空间受限程度更高时(例如，每个思维仅为一个单词或一行)，该方法效果更佳，因为在同一语境中提出不同思维可避免重复。

3. 状态评估器$V(p_{\theta },S)$。给定一个包含不同状态的边界集合，状态评估器会评估这些状态在解决问题方面所取得的进展，其评估结果可作为启发信息，供搜索算法决定应继续探索哪些状态以及探索的先后顺序。尽管启发式方法是解决搜索问题的标准途径，但其实现方式通常仅限于人工编程（例如DeepBlue [3]）或机器学习（例如AlphaGo [29]）。我们提出了第三种方案，即利用语言模型对状态进行审慎推理。在适用场景下，这种审慎推理的启发式方法相较于人工编程的规则更具灵活性，相较于学习获得的模型则具有更高的样本效率。与思维生成器类似，我们考虑两种状态评估策略：独立评估或联合评估。

(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”开头）进行探索性评估。前者可能促进“良好”状态，后者则有助于排除“不良”状态。此类评估无需完美，仅需对决策制定具有近似帮助即可。

(b) 跨状态投票：$V(p_{\theta },S)(s)=1[s=s\ast ]$，其中基于投票提示中对 S 中不同状态的有意比较，会投票选出一个根据 $p_{\theta }^{vote}(s\ast |S)$ 生成的“良好”状态 s∗。当问题成功率较难直接评估时（例如段落连贯性），自然转而比较不同的部分解决方案并投票选出最有潜力的方案。这在精神上类似于“逐步”自一致性策略，即将“探索哪个状态”构建为多项选择题，并使用语言模型样本对其进行投票。

对于这两种策略，我们均可多次提示语言模型以聚合数值或投票结果，从而以时间/资源/成本为代价换取更可靠/稳健的启发式结果。

4. 搜索算法。最后，在思维树（ToT）框架内，研究者可以根据树形结构即插即用地使用不同的搜索算法。我们探索了两种相对简单的搜索算法，并将更先进的算法（例如A* [11]、MCTS [2]）留待未来工作。

(a) 广度优先搜索（BFS）（算法1）在每一步维持一个包含b个最具潜力的状态集合。该方法适用于“24点游戏”和“创意写作”任务，其思维树深度受限（T ≤ 3），初始思维步骤可被评估并剪枝至一个小的集合（b ≤ 5）。

(b) 深度优先搜索（DFS）（算法2）首先探索最具潜力的状态，直至达成最终输出（t > T），或状态评估器判定从当前状态s出发无法解决问题（对于值阈值$v_{th}$，满足 V ( p θ , { s } ) ( s ) ≤ v t h ） V(p_θ, \{s\})(s) ≤ v_{th}） V(pθ​,{s})(s)≤vth​）。在后一种情况下，系统将剪除以s为根的子树，以探索换取利用。在上述两种情况下，DFS均会回溯至状态s的父节点以继续探索。

从概念上讲，作为语言模型通用问题解决方法，思维树具备以下优势：(1) 普适性。单步输入输出、思维链、自洽性思维链及自我精炼均可视为思维树的特例（即深度和宽度受限的树结构；见图1）。(2) 模块化。基础语言模型以及思维分解、生成、评估和搜索过程均可独立调整。(3) 适应性。能够适应不同问题特性、语言模型能力及资源限制。(4) 便捷性。无需额外训练，仅需预训练语言模型即可。下一章节将展示这些概念优势如何在不同问题中转化为强大的实证性能。

4.实验

我们提出了三项任务，即使采用最先进的语言模型GPT-4 [23]进行采样，并使用标准IO提示或思维链提示，这些任务依然具有挑战性。我们展示了如何思维树（ToT）中的审慎搜索能产生更优结果，更重要的是，它开辟了有趣且前景广阔的新途径，使我们能够运用语言模型来解决需要搜索或规划的问题。除非特别说明，我们的实验均采用采样温度为0.7的GPT-41聊天补全模式进行。

4.1 二十四点游戏

24点游戏是一种数学推理挑战，目标是通过4个数字和基本算术运算（±*/）得到24。例如，给定输入“4 9 10 13”，一种解决方案输出可以是“(10 - 4) * (13 - 9) = 24”。

图2：在24点游戏中的思维树。语言模型被提示进行(a)思维生成与(b)价值评估。

任务设置。我们从4nums.com抓取数据，该网站包含1,362个根据人类解题时间从易到难排序的游戏，并选取索引901-1,000范围内难度相对较高的100个游戏作为测试集。对于每个任务，若模型输出是一个使用所有输入数字各一次且运算结果等于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）”。对于每个游戏，我们对IO提示和CoT提示各采样100次以计算平均性能。我们还考虑了CoT自洽性基线，即从100个CoT样本中选取多数输出作为结果；以及一种在IO样本基础上进行最多10次迭代优化的方法。在每次迭代中，若输出错误，语言模型将基于全部历史信息“反思错误并生成修正答案”。需注意，该方法使用了关于算式正确性的真实反馈信号。

ToT架构设计。为将"24点游戏"纳入ToT框架，很自然地将思考过程分解为3个步骤，每步对应一个中间方程。如图2(a)所示，在每个树节点上，我们提取剩余数字并提示语言模型提出若干可能的后续步骤。所有3个思考步骤使用相同的"提议提示词"，尽管该提示仅包含一个4个输入数字的示例。我们在ToT中执行广度优先搜索（BFS），每步保留最优的b=5个候选方案。如图2(b)所示，为实现ToT中的审慎BFS，我们提示语言模型将每个思考候选方案评估为"确定/可能/不可能"达到24。其目标是：推进可在少量前瞻尝试内验证的正确局部解，基于"过大/过小"的常识消除不可能的局部解，并将其余结果保留为"可能"状态。每个思考方案我们进行3次值采样。

结果。如表2所示，IO、CoT和CoT-SC提示方法在该任务上表现不佳，成功率分别仅为7.3%、4.0%和9.0%。相比之下，思维树（ToT）方法在广度b=1时已达到45%的成功率，而b=5时成功率可达74%。我们还考虑了IO/CoT的预言机设置，通过计算最佳k个样本（1 ≤ k ≤ 100）的成功率。为了比较IO/CoT（最佳k样本）与ToT，我们计算了ToT在b=1至5范围内每个任务访问的树节点数，并将5个成功率绘制于图3(a)，同时将IO/CoT（最佳k样本）视为在赌臂问题中访问k个节点。不出所料，CoT的扩展性优于IO，100个CoT样本的最佳成功率可达49%，但仍远逊于在ToT中探索更多节点（b > 1）的效果。

表2：24点游戏结果。

图3：24点游戏（a）规模分析 & （b）误差分析。

误差分析。图3(b)详细分解了思维链与思维树样本在任务中失败的步骤，即思维链中的单个推理步骤或思维树中的所有b个推理步骤无效或无法达到目标值24。值得注意的是，约60%的思维链样本在生成第一步（即前三个词，例如“4 + 9”）后任务就已失败，这突显了直接从左到右解码方式存在的问题。

4.2 创意写作

接下来，我们设计一项创意写作任务：输入为4个随机句子，输出需是一篇连贯的文章，其中包含4个段落，且每个段落分别以这4个输入句作为结尾。这项任务具有开放性和探索性，既挑战创造性思维，也考验高层次的整体规划能力。

任务设置。我们从randomwordgenerator.com随机抽取句子以构成100个输入，且每个输入约束均无对应的事实性参考段落。由于我们发现GPT-4在多数情况下能遵循输入约束，我们主要通过两种方式评估段落的连贯性：一是使用GPT-4零样本提示给出1-10分的标量评分，二是通过人工评判比较不同方法生成的输出对。对于前者，我们对每个任务输出抽取5个评分并取平均值，发现这5个评分通常具有一致性，所有输出平均标准差约为0.56。对于后者，我们邀请部分作者在盲测环境下比较思维链与思维树生成段落的连贯性，其中段落顺序在100个输入中随机翻转。

基线方法。鉴于任务的创造性，IO提示与思维链提示均采用零样本方式。前者直接要求语言模型根据输入约束生成连贯段落，后者则要求语言模型先制定简要计划再撰写段落，即计划作为中间思考步骤。每个任务我们生成10个IO样本和10个思维链样本。此外，我们还在每个任务中随机选取一个IO样本，在其基础上采用迭代优化方法（k ≤ 5次），该方法使语言模型基于输入约束和上一次生成的段落，判断当前段落是否已“完全连贯”，若否则生成一个优化版本。

ToT架构设置。我们构建了一个深度为2的ToT（仅包含1个中间思考步骤）——语言模型首先生成k=5个计划并进行投票选出最佳方案（图4），随后基于最佳方案同样生成k=5个段落并投票选出最优结果。此处的广度限制b=1，即每一步仅保留一个选择。在两个步骤中均采用简单的零样本投票提示（“分析以下选项，然后判断哪个对实现指令最具有潜力”）来采集5次投票结果。

图4：随机选取的创意写作任务中深思熟虑搜索的一个步骤。在给定输入的情况下，语言模型首先采样5种不同的计划，随后进行5轮投票以决定最佳方案。多数票选择出的计划将被采用，并通过相同的“采样-投票”流程来撰写最终输出段落。

结果。图5(a)展示了100项任务中的平均GPT-4评分，其中思维树（ToT）（7.56分）平均而言被认为比直接输入（IO）（6.19分）和思维链（CoT）（6.93分）生成的文本更具连贯性。尽管此类自动评估指标可能存在噪声，但图5(b)通过人类评估结果证实了这一发现：在100组文本对中，人类在41组中更偏好思维树（ToT）而非思维链（CoT），仅在21组中更偏好思维链（CoT）（其余38组被判定为“具有相似连贯性”）。最后，在此项自然语言任务中，迭代优化方法展现出更高的有效性。它将IO连贯性得分从6.19提升至7.67，并将ToT连贯性得分从7.56提升至7.91。我们认为，这可以被视为思维树框架中思想生成的第三种方法，即新思想可以通过改进旧思想而产生，而不是通过独立同分布或顺序生成的方式。

图5：创意写作成果。

4.3 迷你填字游戏

在“24点游戏”与创意写作任务中，思维链的深度相对较浅——最多只需3个思维步骤即可得出最终输出。在此，我们以5×5迷你填字游戏作为一个涉及自然语言的、搜索难度更高的问题进行探索。再次强调，我们的目标并非仅仅是完成任务，因为更通用的填字游戏通常可通过专门的NLP流程[34]解决，这类流程依赖大规模检索而非语言模型。相反，我们旨在探索语言模型作为一种通用问题解决工具的极限：它能够探索自身的思维，并以审慎的推理作为启发式方法，引导其自身的探索过程。

任务设置。
我们从GooBix平台爬取了包含156个5×5迷你填字游戏的数据。由于观察到相邻游戏含有相似提示，我们选取索引为1、6、···、91、96的20个游戏作为测试集，并选取第136、141、146、151、156号游戏作为提示示例。对于每项任务，输入描述包含5条横向提示和5条纵向提示，输出应为5×5共25个字母的棋盘以完成填字。评估时，我们采用三个级别的成功率衡量：字母正确率（每局25字母）、单词正确率（每局10单词）以及整局游戏正确率。

基准方法。我们在IO提示中提供5个输入-输出示例对，在CoT提示中额外按h1…5、v1…5的顺序加入中间词。每个提示运行10次样本并取结果平均值。

ToT设置。我们采用一种深度优先搜索算法（算法2），该算法持续探索最具潜力的后续单词线索，直至状态不再具备潜力，随后回溯至父状态以探索替代思路。为使搜索可处理，后续思路被约束为不得更改任何已填入单词或字母，从而确保ToT至多包含10个中间步骤。在思路生成阶段，我们在每个状态下将所有现有思路（例如图6(a)状态中的“h2.motor; h1.tasks”）转换为剩余线索的字母约束（例如“v1.To heap: tm ;…”），并调用提案提示5次以生成关于下一步填写位置与内容的候选方案。值得注意的是，我们还会提示语言模型对不同思路给出置信度评估，并进行汇总。在评估各提议后，我们获得待探索后续思维的排序列表（图6(a)）。对于状态评估，我们同样将每个状态转化为针对剩余线索的字母约束，随后逐条评估在给定约束下线索是否可能被填充。若任一剩余线索被判定为“不可能”填充（例如“v1. To heap: tm s”），则剪裁该状态的子树探索，深度优先搜索回溯至父节点以探索下一个有潜力的思维。我们将深度优先搜索步数限制为100步，并仅将探索最深的状态（若存在多个则选取首个被探索的状态）转换为最终输出。

图6：在迷你填字游戏中，(a)展示了思维提议及通过优先队列进行深度优先搜索(DFS)的聚合过程，(b)展示了如何根据每个未填词条提示的填充可能性评估状态——若语言模型判定任一剩余提示无法填充，则对该状态进行剪枝，随后DFS回溯至父状态并探索下一个具有潜力的词条提示思维。

结果。如表3所示，输入-输出与思维链提示方法表现较差，词语级成功率低于16%；而思维树方法显著提升了所有指标，实现了60%的词语级成功率，并在20个游戏中成功解决了4个。考虑到输入-输出与思维链方法缺乏尝试不同线索、调整决策或回溯的机制，这一改进并不令人意外。

表3：迷你填字游戏结果。

预言与消融研究。当每个任务从预言机最佳DFS状态（而非启发式确定的最佳状态）输出时，思维树（ToT）性能进一步提升，实际解决了7/20个游戏（表3“+最佳状态”），这表明我们简单的输出启发式方法尚有明显改进空间。有趣的是，有时填字游戏实际已解决，状态评估器仍可能判定某些单词“不可能存在”并进行剪枝——这可能是因为5×5填字游戏在设计上包含一些罕见或过时的词汇，而GPT-4无法识别这些词汇。鉴于作为剪枝启发式的状态评估并不完美，我们进一步探索了取消剪枝的消融实验，发现性能普遍下降（表3“-剪枝”）。但该方法实际上能找到4/20个游戏的正确答案（尽管仅通过启发式输出1个），其中3个是思维树+剪枝在100步内无法解决的案例。因此，开发更好的DFS剪枝启发式方法对此类问题求解至关重要。最后，我们通过消融实验验证了回溯的重要性：该实验持续填充最具希望的线索最多20步，允许覆盖写入。这类似于广度限制b=1的“贪婪”BFS搜索，其表现较差，单词层级成功率仅为20%（表3“-回溯”）。

5.相关工作

规划与决策。智能规划与决策对于实现预设目标至关重要。由于语言模型基于海量的世界知识和人类示例进行训练，已知其已吸收了丰富的常识，使其能够根据问题设定和环境状态提出合理的规划方案[12, 42, 37, 13, 35, 41, 40]。我们提出的思维树方法通过在每个问题解决步骤中同步考虑多个潜在可行方案，并沿最有希望的路径推进，从而扩展了现有规划框架。思维采样与价值反馈的有机结合实现了规划与决策机制的深度融合，使得在解空间树内进行高效搜索成为可能。另一方面，传统决策流程通常需要像强化学习那样训练专用的奖励与策略模型，而我们直接利用语言模型本身为决策提供价值评估。RAP[9]是一项同期研究，其将语言模型其将推理视为基于内部世界模型的规划过程，并提出了一种类似于思维树（ToT）的蒙特卡洛树搜索方法。然而，其任务设定较我们的更为简单，且其框架缺乏模块化设计，无法灵活集成不同的树搜索算法。

自我反思。利用大语言模型评估其自身预测的可行性正日益成为问题解决过程中的关键环节。[28, 20, 24]提出了“自我反思”机制，使语言模型能对其生成的候选结果提供反馈。[4]通过注入由语言模型根据代码执行结果自行生成的反馈信息，提升了模型在代码生成任务中的准确性。类似地，[17]也在计算机操作任务中引入了针对动作和状态的“批判性审查”步骤，以决定解决问题的后续行动。另一项与本研究高度相关的最新工作是“自评估引导解码”[39]。该方法与我们的方案类似，同样遵循树搜索流程：通过随机束搜索解码生成叶节点，再由大语言模型使用精心设计的自评估提示进行评价。然而，该方法采用PAL框架[8]将思维表示为代码，这使其难以处理如创意写作等具有挑战性的任务（本文正关注此类任务）。因此，我们提出的思维树框架更具普适性，能够处理GPT-4在使用标准提示时仅能获得极低准确率的复杂任务。

程序引导的大语言模型生成。我们的方案也与近期通过系统化程序[14, 44, 6, 43]或符号程序引导来组织语言模型行为的研究进展相关。例如，Schlag等人[27]将语言模型嵌入算法搜索流程，以逐步辅助解决问答等问题，其中搜索树通过可能提供答案的相关段落进行扩展。然而，该方法与我们的方案不同之处在于，其搜索树是通过采样外部段落而非模型自身的思维链进行扩展，且不包含反思或投票步骤。另一项研究LLM+P[18]则更进一步，将实际规划过程委托给经典规划器执行。

经典搜索方法。最后同样重要的是，我们的方法可被视为针对问题求解的经典搜索方法的现代表达。例如，可将其视作一种启发式搜索算法（如A*算法[10]），其中每个搜索节点的启发值由语言模型的自我评估提供。由此视角出发，我们的方法也与NeuroLogic A*esque解码[19]相关——该方法受A*搜索启发，但引入了由语言模型高效计算的前瞻启发值，以改进束搜索或top-k采样解码。然而，该方法仅限于句子生成任务，而我们的框架专为受价值反馈约束的复杂多步骤问题求解而设计。

6 讨论

局限性与未来方向。对于许多GPT-4已表现出色的现有任务（见附录B.1），如思维树（ToT）这类有意识的搜索方法可能并非必需；作为初步探索，本研究仅针对三类相对简单且能挑战GPT-4的任务进行了实验（部分GPT-3.5实验结果参见附录B.2），并呼吁在语言模型中整合更优的搜索与规划能力。然而，随着我们开始将语言模型部署于更多现实世界决策应用（如编程、数据分析、机器人技术等），更复杂的任务可能出现，从而为这些研究问题的探索提供新机遇。此外，相较于采样方法，ToT等搜索方法需要更多资源（如GPT-4 API成本）以提升任务表现，但ToT的模块化灵活性允许用户自定义性能与成本的权衡，且当前的开源努力[32]有望在近期显著降低此类成本。更多成本与效率细节参见附录B.3。最后，本研究主要使用现成的语言模型，而采用ToT式的高层次反事实决策机制（例如对下一段落的潜在选项进行深思，而非仅预测下一词元）对语言模型进行微调，或许能进一步提升其问题解决能力。

结论。语言模型基于联想式的“系统一”可通过基于搜索问题解决路径树的“系统二”得到有效增强。思维树框架将经典解题思想的洞见转化为适用于当代语言模型的可行方法。同时，语言模型弥补了这些经典方法的不足，为解决不易形式化的复杂问题（如创意写作）提供了路径。我们认为语言模型与经典人工智能方法的这一交叉领域充满前景。

ToT是一种使语言模型能够更自主、更智能地进行决策和解决问题的框架。虽然当前任务仅限于推理和搜索问题，但未来涉及与外部环境或人类交互的应用可能带来潜在危险，例如助长语言模型的有害使用。另一方面，由于生成的表征是可读的、高层级的语言推理，而非隐式的、低层级的词元数值，ToT也提升了模型决策的可解释性以及实现人类对齐的可能性。

6.引用文献

• [1] T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877–1901, 2020.
• [2] C. Browne, E. J. Powley, D. Whitehouse, S. M. M. Lucas, P. I. Cowling, P. Rohlfshagen, S. Tavener, D. P. Liebana, S. Samothrakis, and S. Colton. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in Games, 4:1–43, 2012.
• [3] M. Campbell, A. J. Hoane Jr, and F.-h. Hsu. Deep blue. Artificial intelligence, 134(1-2):57–83, 2002.
• [4] X. Chen, M. Lin, N. Scha ̈rli, and D. Zhou. Teaching large language models to self-debug, 2023.
• [5] A. Chowdhery, S. Narang, J. Devlin, M. Bosma, G. Mishra, A. Roberts, P. Barham, H. W. Chung, C. Sutton, S. Gehrmann, et al. Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.02311, 2022.
• [6] A. Creswell and M. Shanahan. Faithful reasoning using large language models. arXiv preprint arXiv:2208.14271, 2022.
• [7] N. D. Daw, Y. Niv, and P. Dayan. Uncertainty-based competition between prefrontal and dorsolateral striatal systems for behavioral control. Nature neuroscience, 8(12):1704–1711, 2005.
• [8] L. Gao, A. Madaan, S. Zhou, U. Alon, P. Liu, Y. Yang, J. Callan, and G. Neubig. Pal: Programaided language models, 2023.
• [9] S. Hao, Y. Gu, H. Ma, J. J. Hong, Z. Wang, D. Z. Wang, and Z. Hu. Reasoning with language model is planning with world model. arXiv preprint arXiv:2305.14992, 2023.
• [10] P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2):100–107, 1968. doi: 10.1109/TSSC.1968.300136.
• [11] P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics, 4(2):100–107, 1968.
• [12] W. Huang, P. Abbeel, D. Pathak, and I. Mordatch. Language models as zero-shot planners: Extracting actionable knowledge for embodied agents, 2022.
• [13] W. Huang, F. Xia, T. Xiao, H. Chan, J. Liang, P. Florence, A. Zeng, J. Tompson, I. Mordatch, Y. Chebotar, et al. Inner monologue: Embodied reasoning through planning with language models. arXiv preprint arXiv:2207.05608, 2022.
• [14] J. Jung, L. Qin, S. Welleck, F. Brahman, C. Bhagavatula, R. L. Bras, and Y. Choi. Maieutic prompting: Logically consistent reasoning with recursive explanations. arXiv preprint arXiv:2205.11822, 2022.
• [15] D. Kahneman. Thinking, fast and slow. Macmillan, 2011.
• [16] D. Kahneman, S. Frederick, et al. Representativeness revisited: Attribute substitution in intuitive judgment. Heuristics and biases: The psychology of intuitive judgment, 49(49-81):74, 2002.
• [17] G. Kim, P. Baldi, and S. McAleer. Language models can solve computer tasks, 2023.
• [18] B. Liu, Y. Jiang, X. Zhang, Q. Liu, S. Zhang, J. Biswas, and P. Stone. Llm+p: Empowering large language models with optimal planning proficiency, 2023.
• [19] X. Lu, S. Welleck, P. West, L. Jiang, J. Kasai, D. Khashabi, R. L. Bras, L. Qin, Y. Yu, R. Zellers, N. A. Smith, and Y. Choi. Neurologic a*esque decoding: Constrained text generation with lookahead heuristics. In North American Chapter of the Association for Computational Linguistics, 2021.
• [20] A. Madaan, N. Tandon, P. Gupta, S. Hallinan, L. Gao, S. Wiegreffe, U. Alon, N. Dziri, S. Prabhumoye, Y. Yang, S. Welleck, B. P. Majumder, S. Gupta, A. Yazdanbakhsh, and P. Clark. Self-refine: Iterative refinement with self-feedback, 2023.
• [21] A. Newell, J. C. Shaw, and H. A. Simon. Report on a general problem solving program. In IFIP congress, volume 256, page 64. Pittsburgh, PA, 1959.
• [22] A. Newell, H. A. Simon, et al. Human problem solving. Prentice-Hall, 1972.
• [23] OpenAI. Gpt-4 technical report. ArXiv, abs/2303.08774, 2023.
• [24] D. Paul, M. Ismayilzada, M. Peyrard, B. Borges, A. Bosselut, R. West, and B. Faltings. Refiner: Reasoning feedback on intermediate representations, 2023.
• [25] A. Radford, K. Narasimhan, T. Salimans, I. Sutskever, et al. Improving language understanding by generative pre-training. OpenAI blog, 2018.
• [26] A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, I. Sutskever, et al. Language models are unsupervised multitask learners. OpenAI blog, 1(8):9, 2019.
• [27] I. Schlag, S. Sukhbaatar, A. Celikyilmaz, W. tau Yih, J. Weston, J. Schmidhuber, and X. Li. Large language model programs, 2023. [28] N. Shinn, B. Labash, and A. Gopinath. Reflexion: an autonomous agent with dynamic memory and self-reflection, 2023.
• [29] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, et al. Mastering the game of go without human knowledge. nature, 550 (7676):354–359, 2017.
• [30] S. A. Sloman. The empirical case for two systems of reasoning. Psychological bulletin, 119(1): 3, 1996.
• [31] K. E. Stanovich. Who is rational? Studies of individual differences in reasoning. Psychology Press, 1999.
• [32] H. Touvron, T. Lavril, G. Izacard, X. Martinet, M.-A. Lachaux, T. Lacroix, B. Roziere, N. Goyal, E. Hambro, F. Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.13971, 2023.
• [33] S. Verma, J. Fu, S. Yang, and S. Levine. Chai: A chatbot ai for task-oriented dialogue with offline reinforcement learning. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 4471–4491, 2022.
• [34] E. Wallace, N. Tomlin, A. Xu, K. Yang, E. Pathak, M. Ginsberg, and D. Klein. Automated crossword solving. arXiv preprint arXiv:2205.09665, 2022.
• [35] L. Wang, W. Xu, Y. Lan, Z. Hu, Y. Lan, R. K.-W. Lee, and E.-P. Lim. Plan-and-solve prompting: Improving zero-shot chain-of-thought reasoning by large language models, 2023.
• [36] X. Wang, J. Wei, D. Schuurmans, Q. Le, E. Chi, and D. Zhou. Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv:2203.11171, 2022.
• [37] Z. Wang, S. Cai, A. Liu, X. Ma, and Y. Liang. Describe, explain, plan and select: Interactive planning with large language models enables open-world multi-task agents, 2023.
• [38] J. Wei, X. Wang, D. Schuurmans, M. Bosma, E. Chi, Q. Le, and D. Zhou. Chain of thought prompting elicits reasoning in large language models. arXiv preprint arXiv:2201.11903, 2022.
• [39] Y. Xie, K. Kawaguchi, Y. Zhao, X. Zhao, M.-Y. Kan, J. He, and Q. Xie. Decomposition enhances reasoning via self-evaluation guided decoding, 2023.
• [40] S. Yang, O. Nachum, Y. Du, J. Wei, P. Abbeel, and D. Schuurmans. Foundation models for decision making: Problems, methods, and opportunities, 2023.
• [41] S. Yao, J. Zhao, D. Yu, N. Du, I. Shafran, K. Narasimhan, and Y. Cao. ReAct: Synergizing reasoning and acting in language models. arXiv preprint arXiv:2210.03629, 2022.
• [42] S. Zhang, Z. Chen, Y. Shen, M. Ding, J. B. Tenenbaum, and C. Gan. Planning with large language models for code generation. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreview.net/forum?id=Lr8cOOtYbfL.
• [43] D. Zhou, N. Scha ̈rli, L. Hou, J. Wei, N. Scales, X. Wang, D. Schuurmans, C. Cui, O. Bousquet, Q. Le, et al. Least-to-most prompting enables complex reasoning in large language models. arXiv preprint arXiv:2205.10625, 2022.
• [44] X. Zhu, J. Wang, L. Zhang, Y. Zhang, R. Gan, J. Zhang, and Y. Yang. Solving math word problem via cooperative reasoning induced language models. arXiv preprint arXiv:2210.16257, 2022.

附录

B 附加实验结果

基于探索和拓展语言模型能力边界的动机，我们在主论文中的实验集中于采用最先进语言模型（GPT-4）的设定，以及三项为挑战其极限而设计的困难任务。在此，我们汇报使用性能较弱的大型语言模型或更简单任务的补充实验，并讨论成本与效率问题。

B.1 面向新任务（GSM8k、StrategyQA）的零样本思维树（ToT）扩展

虽然常见的自然语言处理任务对于GPT-4可能过于简单而无需思维树方法（这也正是我们考虑采用更具挑战性的新任务的原因），但我们认为将思维树应用于新任务可能是直接可行的。例如，我们通过添加少量代码，为GSM8K和StrategyQA数据集实现了一个简单通用的零样本思维树广度优先搜索方案，其流程类似于创意写作任务（首先生成五种解题策略并投票选出最佳策略，随后基于最佳策略生成五种解决方案并投票选出最优解）。

# 定义新任务的答案格式
gsm8k_format = '"the answer is n"，其中 n 是数字'
strategyqa_format = '只能是 "the answer is yes" 或 "the answer is no"'

# 定义零样本输入输出提示
standard_prompt = '请根据以下格式回答问题：{format}：{input}'

# 定义零样本思维链和零样本思维树的思考格式
cot_prompt = '''请回答以下问题：{input}

制定一个策略后进行书写。你的输出应遵循以下格式：

策略：你关于如何回答该问题的策略。
答案：你对问题的回答。结尾必须包含 {format}。'''

# 定义用于零样本思维树的零样本投票机制
vote_prompt = 给定一个指令和若干选项，请判断哪个选项最有希望。详细分析每个选项，最后一行请得出结论："最佳选择是 {s}"，其中 s 是选项的整数编号。

我们在100个随机的GSM8K测试集和StrategyQA开发集问题的子集上进行了评估。如表4所示且符合预期，ToT在两项任务上均优于CoT（但幅度较小，因为GPT-4 + CoT在此类任务上已表现优异，而StrategyQA的瓶颈在于外部知识而非推理能力）。考虑到计算成本，对于传统NLP任务更适合尝试较小规模的LLM + ToT，而对于挑战GPT-4 + CoT推理能力的困难任务，则更适合采用GPT-4 + ToT。

B.2 向新语言模型（GPT-3.5）的扩展

为理解思维树（ToT）与其他大语言模型的协作效果，我们还在“创意写作”（表6）和“24点游戏”（表5）任务中对GPT-3.5-turbo进行了测试。在这两项任务中，对于GPT-3.5而言，“ToT > 思维链（CoT） > 直接输入输出（IO）”的优劣关系依然成立。在创意写作任务中，我们发现GPT-3.5+ToT的表现优于GPT-4+IO，并与GPT-4+CoT相当，这表明思维树方法在能力较弱的大语言模型上也可能有良好表现。在24点游戏任务中（我们将单样本提示改为三样本提示以使其运行），GPT-3.5+ToT的19%成功率远低于GPT-4+ToT的74%。为深入分析生成与评估环节的重要性，我们测试了GPT-4生成 + GPT-3.5评估（64%）以及GPT-3.5生成 + GPT-4评估（31%）的组合。这表明该游戏的瓶颈在于思维生成环节，而通过组合不同的生成/评估大语言模型，可能在降低成本的同时获得尚可的结果。

B.3 成本与效率

在24点游戏（下方表7）中，用思维树解决一个问题需消耗5.5k补全令牌，接近100次思维链试验的消耗（6.7k令牌）。但思维树的性能优于100次独立思维链试验中的最佳结果。

在《创意写作》（下文表8）中，我们发现思维树方法消耗了约5倍的完成令牌及相应费用，这是符合预期的，因为分支数b=5且绝大多数令牌用于生成文本段落。

因此，完成"24点游戏"与"创意写作"的主要思维树（ToT）实验花费约为0.74×100+0.32×100=106美元。"填字游戏"的深度优先搜索实验成本亦应控制在100美元以内。总体而言，思维树的成本与效率高度依赖于所使用的提示词和搜索算法，其生成的令牌量可能达到思维链（CoT）的5至100倍。

一些可行建议：
• 我们建议在思维链方法表现不佳、需要慎重推理的任务中使用思维树。
• 思维树的灵活性允许在性能与成本之间进行权衡，例如调整广度优先搜索中的束宽或投票数量、选择少样本与零样本提示、选用GPT-3.5或GPT-4等。研究者可根据资源限制或性能目标灵活配置实验方案。
• 其效率仍有很大提升空间，例如广度优先搜索可在找到解时提前终止，或在某些思路被判定为"不可行"时缩减束宽。
• 我们认为，模型要实现更强的智能确实需要更多计算资源，但这不应成为阻碍因素，因为长期来看（开源）语言模型将变得更廉价、更高效。如何更好地训练/微调语言模型以生成和/或评估思维，也是一个极具前景的研究方向。