Tree of Thoughts: Deliberate Problem Solving with Large Language Models

题目

思想树：利用大型语言模型进行深思熟虑的问题解决

论文地址：https://arxiv.org/abs/2305.10601
项目地址：https://github.com/princeton-nlp/tree-of-thought-llm

摘要

    语言模型越来越多地被用于解决各种任务中的一般问题，但在推理过程中，它们仍然局限于 token 级、从左到右的决策过程。这意味着它们在需要探索、战略前瞻或初始决策起关键作用的任务中可能会出现不足。为了克服这些挑战，我们引入了一个用于语言模型推理的新框架“思想树”（ToT），它概括了流行的“思想链”方法来提示语言模型，并能够探索作为解决问题的中间步骤的连贯文本单元（“思想”）。ToT 允许 LM 通过考虑多种不同的推理路径和自我评估选择来决定下一步行动，以及在必要时向前看或回溯以做出全局选择，从而进行深思熟虑的决策。我们的实验表明，ToT 显著增强了语言模型在三个需要非平凡规划或搜索的新任务上的问题解决能力：24 点游戏、创意写作和迷你填字游戏。例如，在 Game of 24 中，采用思路链提示的 GPT-4 仅解决了 4% 的任务，而我们的方法实现了 74% 的成功率。包含所有提示的代码仓库：https://github.com/princeton-nlp/tree-of-thought-llm。

简介

    语言模型 (LM) 的扩大版本最初设计用于生成文本，例如 GPT [25, 26, 1, 23] 和 PaLM [5]，已被证明能够执行越来越广泛的需要数学、符号、常识和知识推理的任务。令人惊讶的是，所有这些进步的基础仍然是用于生成文本的原始自回归机制，该机制以从左到右的方式逐个做出 token 级决策。这种简单的机制是否足以将 LM 构建为通用问题解决者？如果不能，哪些问题会挑战当前范式，又应该有哪些替代机制？有关人类认知的文献为回答这些问题提供了一些线索。对“双重过程”模型的研究表明，人们在决策时有两种模式——一种是快速、自动、无意识的模式（“系统 1”），另一种是缓慢、深思熟虑、有意识的模式（“系统 2”）。

    这两种模式之前已与机器学习中使用的各种数学模型相关联。例如，对人类和其他动物的强化学习的研究探索了它们在何种情况下进行联想式“无模型”学习或更慎重的“基于模型”规划 [7]。语言模型的简单联想标记级选择也让人想起“系统 1”，因此可能受益于更慎重的“系统 2”规划过程的增强，该过程 (1) 维护并探索当前各种替代方案选择而不是只选择一个，并且 (2) 评估其当前状态并主动展望或回溯以做出更全局的决策。

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

图 1：示意图，说明使用 LLM 解决问题的各种方法。每个矩形框代表一个想法，这是一个连贯的语言序列，是解决问题的中间步骤。请参见图 2、4、6 中关于如何生成、评估和搜索想法的具体示例。

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

背景

    我们首先形式化一些使用大型语言模型解决问题的现有方法，我们的方法受到这些方法的启发，后来与之进行了比较。我们使用 pθ 表示具有参数 θ 的预训练 LM，小写字母 x、y、z、s、··· 表示语言序列，即 x = (x[1], · · · , x[n])，其中每个 x[i] 都是一个标记，因此 pθ(x) = 串 n i=1 pθ(x[i]|x[1…i])。我们使用大写字母 S、··· 表示语言序列的集合。输入输出 (IO) 提示是使用 LM 将问题输入 x 转换为输出 y 的最常见方法：y ∼ pθ(y|promptIO(x))，其中 promptIO(x) 将输入 x 与任务指令和/或少量输入输出示例包装在一起。为简单起见，我们表示 p prompt θ (输出 | 输入) = pθ(输出 | prompt(输入))，这样 IO 提示就可以表述为 y ∼ p IO θ (y|x)。

    思路链 (CoT) 提示 [38] 被提出用于解决输入 x 到输出 y 的映射不简单的情况（例如，当 x 是数学问题而 y 是最终的数字答案时）。 关键思想是引入思路链 z1, · · · , zn 来连接 x 和 y，其中每个 zi 都是一个连贯的语言序列，可作为解决问题的有意义的中间步骤（例如，zi 可以是数学问答的中间方程）。 要解决具有 CoT 的问题，每个思路 zi ∼ p CoT θ (zi | x, z1···i−1) 被按顺序采样，然后输出 y ∼ p CoT θ (y|x, z1···n)。在实践中，[z1···n, y] ∼ p CoT θ (z1···n, y|x) 被采样为一个连续的语言序列，而思想的分解（例如，每个 zi 是短语、句子还是段落）是模棱两可的。

    带有 CoT 的自洽 (CoT-SC) [36] 是一种集成方法，它采样 k 个 i.i.d. 思想链：[z (i) 1···n , y(i) ] ∼ p CoT θ (z1···n, y|x)（i = 1 · · · k），然后返回最常见的输出：arg maxy #{i | y (i) = y}。 CoT-SC 改进了 CoT，因为对于同一个问题通常存在不同的思维过程（例如，证明同一个定理的不同方法），并且通过探索更丰富的思想集，输出决策可以更加忠实。然而，在每个思维链中，并没有对不同思维步骤进行局部探索，“最常见”的启发式方法只适用于输出空间有限的情况下（如多项选择问答）。

思维树：用思维树进行深思熟虑的问题解决

    真正的问题解决过程涉及反复使用可用信息来启动探索，而探索反过来又会揭示更多信息，直到最终找到获得解决方案的方法。——Newell 等人 [21] 对人类问题解决的研究表明，人们会搜索组合问题空间——一棵树，其中节点代表部分解决方案，分支对应于修改它们的运算符 [21, 22]。选择哪个分支由启发式方法决定，启发式方法有助于导航问题空间并引导问题解决者找到解决方案。这种观点强调了使用思维树解决一般问题的现有方法的两个主要缺点：1）在局部，它们不会探索思维过程中的不同延续——树的分支。 2) 从整体上看，它们没有采用任何类型的规划、前瞻或回溯来帮助评估这些不同的选择——这种启发式搜索似乎是人类解决问题的特征。

    为了解决这些缺点，我们引入了思想树 (ToT)，这是一种允许 LM 探索思想的多种推理路径的范式（图 1©）。ToT 将任何问题都定义为对树的搜索，其中每个节点都是一个状态 s = [x, z1···i ]，表示使用输入和迄今为止的思想序列的部分解决方案。ToT 的具体实例涉及回答四个问题：1. 如何将中间过程分解为思考步骤；2. 如何从每个状态产生潜在的想法；3. 如何启发式地评估状态；4. 使用什么搜索算法。

1. 思想分解。虽然 CoT 在没有明确分解的情况下连贯地对思想进行采样，但 ToT 利用问题属性来设计和分解中间思考步骤。如表 1 所示，根据不同的问题，一个想法可能是几个单词（填字游戏）、一行等式（24 点游戏）或一整段写作计划（创意写作）。一般来说，一个想法应该足够“小”，以便语言模型可以生成有希望的、多样化的样本（例如，生成一整本书通常太“大”而无法连贯），但又要足够“大”，以便语言模型可以评估其解决问题的前景（例如，生成一个 token 通常太“小”而无法评估）。
2. 想法生成器 G(pθ, s, k)。给定一个树状态 s = [x, z1···i ]，我们考虑两种策略来为下一个想法步骤生成 k 个候选：(a) 样本 i.i.d。来自 CoT 提示的想法（创意写作，图 4）：z (j) ∼ p CoT θ (zi+1|s) = p CoT θ (zi+1|x, z1···i) (j = 1···k)。当思维空间丰富（例如每个想法都是一个段落）且 i.i.d. 样本导致多样性时，此方法效果更好；（b）使用“提出提示”按顺序提出想法（24 游戏，图 2；填字游戏，图 6）：[z (1) , · · · , z(k) ] ∼ p 提出 θ (z (1···k) i+1 | s)。当思维空间更受限时（例如每个想法只是一个单词或一行），此方法效果更好，因此在相同上下文中提出不同的想法可以避免重复。
3. 状态评估器 V (pθ, S)。给定一个由不同状态组成的边界，状态评估器会评估它们在解决问题方面取得的进展，作为搜索算法的启发式方法，以确定继续探索哪些状态以及以何种顺序进行探索。虽然启发式方法是解决搜索问题的标准方法，但它们通常是编程的（例如 DeepBlue [3]）或学习到的（例如 AlphaGo [29]）。

    我们提出了第三种选择，即使用 LM 来刻意推理状态。在适用的情况下，这种刻意的启发式方法比编程规则更灵活，比学习模型更具样本效率。与思维生成器类似，我们考虑两种策略来独立或一起评估状态：

1. 独立评估每个状态：V (pθ, S)(s) ∼ p 值 θ (v|s) ∀s ∈ S，其中值提示推理状态 s 以生成标量值 v（例如 1-10）或分类（例如肯定/可能/不可能），可以启发式地转化为值。这种评价推理的基础可能因问题和思维步骤而异。在本研究中，我们探索通过一些前瞻模拟（例如，快速确认 5, 5, 14 可以通过 5 + 5 + 14 达到 24，或者“hot l”可以通过在“ ”中填写“e”来表示“inn”）加上常识（例如 1 2 3 太小而无法达到 24，或者没有单词可以以“tzxc”开头）进行评估。前者可能会促进“好”状态，而后者可以帮助消除“坏”状态。这种估值不需要完美，只需要对决策有大致帮助即可。

2. 跨状态投票：V (pθ, S)(s) = 1[s = s ∗ ]，其中“好”状态 s ∗ ∼ p vote θ (s ∗ |S) 是根据在投票提示中刻意比较 S 中的不同状态而被投票淘汰的。当问题的成功率难以直接评估时（例如段落连贯性），自然而然地会比较不同的部分解决方案并投票选出最有希望的解决方案。这在精神上类似于“逐步”自洽策略，即将“探索哪个状态”作为多项选择问答，并使用 LM 样本为其投票。对于这两种策略，我们可以多次提示 LM 汇总价值或投票结果，以牺牲时间/资源/成本换取更忠实/稳健的启发式方法。

3. 搜索算法。最后，在 ToT 框架内，可以根据树结构即插即用不同的搜索算法。我们探索了两种相对简单的搜索算法，并将更高级的算法（例如 A* [11]、MCTS [2]）留待将来研究：(a) 广度优先搜索 (BFS)（算法 1）每一步维护一组 b 个最有希望的状态。这用于 24 游戏和创意写作，其中树深度是极限（T ≤ 3），可以评估初始思考步骤并将其修剪为一个小集合（b ≤ 5）。(b) 深度优先搜索 (DFS)（算法 2）首先探索最有希望的状态，直到达到最终输出（t > T），或者状态评估器认为无法从当前 s 解决问题（V (pθ, {s})(s) ≤ vth，对于值阈值 vth）。在后一种情况下，s 中的子树被修剪，以利用开发换取探索。在这两种情况下，DFS 都会回溯到 s 的父状态以继续探索。

    从概念上讲，作为一种使用 LM 解决一般问题的方法，ToT 有几个好处：(1) 通用性。IO、CoT、CoT-SC 和自我改进可以看作是 ToT 的特殊情况（即深度和广度有限的树；图 1）。(2) 模块化。基础 LM 以及思想分解、生成、评估和搜索过程都可以独立变化。(3) 适应性。可以适应不同的问题属性、LM 功能和资源约束。(4) 方便。不需要额外的训练，只需预先训练过的 LM 就足够了。下一节将展示这些概念上的好处如何转化为不同问题中的强大经验表现。

实验

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

    24 游戏是一项数学推理挑战，其目标是使用 4 个数字和基本算术运算 (±*/) 来获得 24。例如，给定输入“4 9 10 13”，解决方案输出可能是“(10 - 4) * (13 - 9) = 24”。任务设置。我们从 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）”。对于每个游戏，我们对 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 则实现了 74% 的成功率。我们还考虑了 IO/CoT 的 oracle 设置，通过使用 k 个样本中的最佳样本（1 ≤ k ≤ 100）计算成功率。为了将 IO/CoT（k 中的最佳样本）与 ToT 进行比较，我们考虑计算 b = 1 · · · 5 中 ToT 中每个任务访问的树节点，并在图 3(a) 中映射 5 个成功率，将 IO/CoT（k 中的最佳样本）视为访问老虎机中的 k 个节点。

    毫不奇怪，CoT 的扩展性比 IO 更好，100 个 CoT 样本中最好的一个样本的成功率为 49%，但仍然比探索 ToT 中的更多节点（b > 1）差得多。错误分析。图 3(b) 细分了 CoT 和 ToT 样本在哪个步骤失败，即想法（在 CoT 中）或所有 b 个想法（在 ToT 中）无效或不可能达到 24。值得注意的是，大约 60% 的 CoT 样本在生成第一步或等效地生成前三个单词（例如“4 + 9”）后已经失败。这凸显了直接从左到右解码的问题。

    创意写作接下来，我们发明了一个创意写作任务，其中输入是 4 个随机句子，输出应该是一个连贯的段落，有 4 个段落分别以 4 个输入句子结尾。这样的任务是开放式和探索性的，挑战创造性思维和高级规划。任务设置。我们从 randomwordgenerator.com 中抽取随机句子形成 100 个输入，并且每个输入约束都没有真实段落。由于我们发现 GPT-4 在大多数情况下都可以遵循输入约束，因此我们专注于通过两种方式评估段落连贯性：使用 GPT-4 零样本提示提供 1-10 的标量分数，或使用人工判断来比较不同方法的输出对。对于前者，我们抽取 5 个分数并针对每个任务输出取平均值，我们发现这 5 个分数通常是一致的，各个输出的平均标准差约为 0.56。对于后者，我们在盲研究中雇用了一部分作者来比较 CoT 与 ToT 生成的段落对的连贯性，其中段落的顺序是在 100 个输入中随机翻转的。

    基线。鉴于任务的创造性，IO 和 CoT 提示都是零样本的。前者提示 LM 在给定输入约束的情况下直接生成连贯的段落，而后者提示 LM 首先制定一个简要计划，然后编写段落，即计划作为中间思考步骤。我们为每个任务生成 10 个 IO 和 CoT 样本。我们还考虑在每个任务的随机 IO 样本之上使用迭代细化（k ≤ 5）方法，其中 LM 以输入约束和最后生成的段落为条件来决定段落是否已经“完全连贯”，如果不是，则生成一个细化的段落。

    ToT 设置。我们构建一个深度为 2 的 ToT（并且只有 1 个中间思考步骤）——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 个段落对中更喜欢 CoT 而不是 ToT（其他 38 对被发现“同样连贯”）。最后，迭代细化在这个自然语言任务上更有效，其中它将IO一致性得分从6.19提高到7.67，将ToT一致性得分从7.56提高到7.91。我们认为它可以被认为是ToT框架中思想生成的第三种方法，新的想法可以通过提炼旧的想法而产生，而不是独立同分布或顺序生成。

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

图 4：在随机挑选的创意写作任务中进行深思熟虑的搜索步骤。给定输入，LM 会抽样 5 个不同的方案，然后投票 5 次以决定哪个方案最好。然后使用多数选择，通过相同的抽样投票程序编写输出段落。

    任务设置。我们从 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 次建议提示，以提出下一个单词的填充位置和内容的候选。

    重要的是，我们还提示 LM 为不同的想法给出一个置信度，并聚合跨提案对这些进行搜索，以获得下一个要探索的想法的排序列表（图 6（a））。对于状态评估，我们类似地将每个状态转换为剩余线索的字母约束，然后评估每个线索是否有可能在给定约束的情况下填写。如果任何剩余线索被认为“不可能”填写（例如“v1. To heap: tm s”），则修剪状态子树的探索，并且 DFS 回溯到其父级以探索下一个有希望的想法。我们将 DFS 搜索步骤限制为 100，并简单地将最深的探索状态（如果有多个，则为第一个探索的状态）呈现到最终输出中。

    结果。如表 3 所示，IO 和 CoT 提示方法表现不佳，字级成功率不到 16%，而 ToT 显着提高了所有指标，实现了 60% 的字级成功率并解决了 20 个游戏中的 4 个。鉴于 IO 和 CoT 缺乏尝试不同线索、更改决策或回溯的机制，这样的改进并不令人惊讶。预言机和消融研究。当从预言机输出每个任务的最佳 DFS 状态（而不是启发式确定的最佳状态）时，ToT 性能甚至更高，并且实际上解决了 7/20 个游戏（表 3，“+best state”），这表明我们简单的输出启发式方法可以轻松改进。

图 6：在 Mini Crosswords 中，(a) 如何提出想法并将其聚合到优先级队列中以进行深度优先搜索 (DFS)，以及 (b) 如何根据填写每个剩余单词线索的可能性来评估状态，如果 LM 认为任何剩余线索无法填写，则对其进行修剪。然后，DFS 回溯到父状态并探索下一个有希望的线索想法。

    有趣的是，有时当填字游戏真正解决时，状态评估器可能仍会将某些单词视为“不可能”并进行修剪——可能是因为 5×5 填字游戏在设计上有一些 GPT-4 无法识别的罕见或过时的单词2。鉴于状态评估作为修剪启发式方法并不完善，我们还探索了消融修剪，并发现性能通常更差（表 3，“-prune”）。然而，它实际上可以为 20 个游戏中的 4 个找到正确的解决方案（尽管通过启发式方法仅输出 1 个），其中 3 个是 ToT+剪枝无法在 100 步内解决的游戏。因此，在这种情况下，更好的 DFS 剪枝启发式方法对于解决问题至关重要。最后，我们通过运行消融来确认回溯的重要性，该消融最多 20 步不断填充最有希望的线索，允许覆盖。这类似于广度限制为 b = 1 的“贪婪”BFS 搜索，并且表现不佳，字级成功率仅为 20%（表 3，“-backtrack”）。

相关工作

    规划和决策。明智的规划和决策对于实现预定义的目标至关重要。由于语言模型接受了大量的世界知识和人类实例的训练，因此人们知道语言模型已经吸收了丰富的常识，这使得它能够根据问题设置和环境状态提出合理的计划。我们提出的 ToT 方法扩展了现有的规划公式，在每个问题解决步骤中同时考虑多个潜在可行的计划，并继续执行最有希望的计划。思维采样和价值反馈之间的整合将规划和决策机制有机地整合在一起，从而实现了解决方案树内的有效搜索。另一方面，传统的决策程序通常需要训练专门的奖励和策略模型，如强化学习（例如 CHAI），而我们使用语言模型本身来提供决策的价值估计。RAP是一项并行工作，它将语言模型视为推理是一种利用内部世界模型进行规划的方法，并提出了一种类似于 ToT 的基于 MCTS 的方法。然而，它的任务比我们的简单，而且它的框架缺乏模块化，无法整合不同的树搜索算法。

    自我反思。使用 LLM 评估自身预测的可行性正成为解决问题的一个越来越重要的程序。引入了“自我反思”机制，其中 LM 向其生成候选提供反馈。[4] 通过注入由 LM 本身根据其代码执行结果生成的反馈消息来提高 LM 代码生成的准确性。同样，还在动作和状态上引入了“批评”或审查步骤，决定在解决计算机操作任务时要采取的下一步行动。另一项与我们非常相关的最新工作是“自我评估引导解码”[39]。与我们的方法类似，自我评估解码也遵循树搜索程序，其叶子从随机束搜索解码中采样，然后由 LLM 本身使用精心准备的自我评估提示进行评估。然而，他们的方法使用了 PAL 公式 [8]，将思想表示为代码，这使得它很难解决我们在本文中考虑的创意写作等具有挑战性的任务。因此，我们的思维树公式更加灵活，可以处理具有挑战性的任务，在这些任务上 GPT-4 只能通过标准提示实现非常低的准确率。

    程序引导的 LLM 生成。我们的提议还与最近的进展有关，这些进展使用系统程序或符号程序指导来组织 LM 的行为。例如，Schlag 等人 [27] 将 LM 嵌入算法搜索过程中，以帮助逐步解决诸如问答之类的问题，其中搜索树通过可能提供答案的相关段落进行扩展。但是，这种方法与我们的方法不同，因为树是通过对外部段落进行采样而不是 LM 自己的想法来扩展的，并且没有反思或投票步骤。另一种方法 LLM+P [18] 更进一步，将实际规划过程委托给经典规划器。

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

讨论限制和未来方向

    对于 GPT-4 已经擅长的许多现有任务（参见附录 B.1），诸如 ToT 之类的刻意搜索可能不是必需的，作为初始步骤，这项工作仅探索了三个相对简单的挑战 GPT-4 的任务（有关一些 GPT-3.5 实验结果，请参阅附录 B.2）以及与 LM 结合的更好的搜索和规划能力的要求。但是，随着我们开始将 LM 部署到更多现实世界的决策应用（例如编码、数据分析、机器人技术等），可能会出现更复杂的任务并为研究这些研究问题提供新的机会。此外，与采样方法相比，ToT 等搜索方法需要更多的资源（例如 GPT-4 API 成本）才能提高任务性能，但 ToT 的模块化灵活性允许用户自定义这种性能成本权衡，并且正在进行的开源工作 [32] 应该会在不久的将来轻松降低此类成本。有关成本和效率的更多详细信息，请参阅附录 B.3。最后，这项工作的重点是使用现成的 LM，并使用 ToT 风格的高级反事实决策（例如，考虑下一段的潜在选择，而不是预测下一个标记）对 LM 进行微调可能会提供机会来增强 LM 的解决问题的能力。

    结论。LM 的联想“系统 1”可以通过基于搜索问题解决方案的可能路径树的“系统 2”进行有益的增强。思想树框架提供了一种将关于解决问题的经典见解转化为当代 LM 的可行方法的方法。同时，LM 解决了这些经典方法的弱点，提供了一种解决不易形式化的复杂问题的方法，例如创意写作。我们认为 LM 与人工智能的经典方法的交集是一个令人兴奋的方向。

    更广泛的影响 ToT 是一个框架，它使 LM 能够更自主、更智能地做出决策和解决问题。虽然当前任务仅限于推理和搜索问题，但未来涉及与外部环境或人类交互的应用可能会带来潜在的危险，例如促进 LM 的有害使用。另一方面，ToT 还提高了模型决策的可解释性和与人类保持一致的机会，因为生成的表示是可读的高级语言推理，而不是隐式的低级标记值。

附录

A 代码、提示、轨迹 所有代码均可在 https://github.com/princeton-nlp/tree-of-thought-llm 上找到。
所有提示均可在 https://github.com/princeton-nlp/tree-of-thought-llm/tree/master/src/tot/prompts 上找到。
轨迹可在 https://github.com/princeton-nlp/tree-of-thought-llm/tree/master/logs 上找到。

B 附加实验结果 鉴于探索和扩展语言模型能力边界的动机，我们在主要论文中的实验集中于最先进的语言模型 (GPT-4) 的设置，以及为挑战它而发明的三个艰巨任务。在这里，我们报告了使用较弱的 LLM 或更简单的任务进行的额外实验，并讨论了成本和效率。

B.1 使用零样本 ToT 扩展到新任务（GSM8k、StrategyQA）虽然更常见的 NLP 任务对于 GPT-4 来说可能太容易并且不需要 ToT（这就是我们考虑更难的新任务的原因），但我们相信将 ToT 应用于新任务可能很简单。

例如，我们为 GSM8K 和 StrategyQA 实现了一个简单而通用的零样本 ToT-BFS，类似于创意写作（抽样 5 种解决问题的策略，然后投票选出最佳策略；然后抽样 5 种基于最佳策略的解决方案，然后投票选出最佳策略），并增加了几行代码：# 定义新任务的答案格式 gsm8k_format = ‘“答案是 n”，其中 n 是一个数字’strategyqa_format = ‘“答案是肯定的”或“答案是否定的”’# 定义零样本 io 提示 standard_prompt = ‘使用 {format} 回答以下问题：{input}’# 定义零样本 cot 和零样本 tot 的思维格式 cot_prompt = ‘‘‘回答以下问题：{input} 制定策略然后写作。您的输出应采用以下格式：策略：您关于如何回答问题的策略。
答案：您对问题的回答。它应该以 {format} 结尾。

’’’ # 定义用于零次投票的零次投票 tot vote_prompt = ‘‘‘给定一个指令和几个选择，决定哪个选择最有希望。
详细分析每个选择，然后在最后一行得出结论“最佳选择是 {s}”，其中 s 是选择的整数 id。
’’’

我们对 100 个随机 GSM8K 测试和 StrategyQA 开发问题的子集进行了评估。如表 4 所示，正如预期的那样，ToT 在这两个任务上都比 CoT 有所改进（但改进幅度很小，因为 GPT-4 + CoT 在这类任务上已经非常出色，而 StrategyQA 的瓶颈是外部知识，而不是推理）。考虑到计算成本，对于传统的 NLP 任务，尝试较小的 LLM + ToT 更为合适，对于挑战 GPT-4 + CoT 推理能力的困难任务，尝试 GPT-4 + ToT 更为合适。

B.2 扩展到新的 LM（GPT-3.5）为了了解 ToT 如何与其他 LLM 配合使用，我们还运行了 GPT-3.5-turbo 进行创意写作（表 6）和 24 点游戏（表 5）。在这两个任务中，“ToT > CoT > IO”对 GPT-3.5 仍然成立。在创意写作方面，我们发现 GPT-3.5+ToT 的表现优于 GPT-4+IO，与 GPT-4+CoT 相似，这表明 ToT 在较弱的语言模型上也能很好地工作。

在 24 人游戏中（我们将 1 次提议提示改为 3 次以使其工作），GPT-3.5+ToT 的 19% 远远低于 GPT-4+ToT 的 74%。为了进一步了解生成与评估的重要性，我们运行了 GPT-4 生成 + GPT-3.5 评估（64%）和 GPT-3.5 生成 + GPT-4 评估（31%）。这表明游戏的瓶颈是思维生成，不同的生成/评估语言模型可能会在降低成本的同时获得不错的结果。

B.3 成本和效率运行 ToT 需要比 IO 或 CoT 提示多得多的计算。例如，在 24 游戏中（下表 7），使用 ToT 解决一个问题需要 5.5k 个完成令牌，接近 100 次 CoT 试验（6.7k 个令牌）。但 ToT 的性能优于 100 次独立 CoT 试验中的最佳性能。

在创意写作 (下表 8) 中，我们发现 ToT 需要大约 5 倍的完成代币和金钱成本，这是直观的，因为 b = 5 并且大多数代币都是生成的段落。因此，完成 Game of 24 和 Creative Writing 的主要 ToT 实验的成本约为 0.74 × 100 + 0.32 × 100 = 106 美元。Crosswords 的 DFS 实验也应该在 100 美元以内。一般来说，ToT 的成本和效率高度依赖于所使用的提示和搜索算法，并且可能需要比 CoT 多 5-100 倍的生成令牌。一些可行的见解：

• 我们建议在需要深思熟虑推理的任务上使用 ToT，而 CoT 在这方面举步维艰。
• ToT 的灵活性允许一些性能成本权衡，例如，更改 BFS 中的光束大小或投票数、少样本与零样本提示、GPT-3.5 与 GPT-4 等。可以根据一些资源限制或性能目标配置设置。
• 有很大的提高效率的空间，例如，BFS 可以在找到解决方案时提前停止，或者将光束大小缩减到某些想法“不可能”的时候。
• 我们相信，为了让模型实现更强的智能，确实需要更多的计算，但这不应该成为一个阻碍问题，因为从长远来看，（开源）LM 将变得更便宜、更高效。如何更好地训练/微调 LM 以进行思维生成和/或评估也是一个很好的方向。