Tree of Thoughts: Deliberate Problem Solving with Large Language Models

作者/机构: Shunyu Yao (Princeton University), Dian Yu (Google DeepMind), Jeffrey Zhao (Google DeepMind), Izhak Shafran (Google DeepMind), Thomas L. Griffiths (Princeton University), Yuan Cao (Google DeepMind), Karthik Narasimhan (Princeton University)

A1 主要贡献（总结）

本文旨在解决大型语言模型（LMs）在推理时局限于逐个词元（token-level）、从左到右决策过程的问题，这一机制在需要探索、策略性前瞻或初始决策至关重要的任务中表现不佳。为克服这些挑战，作者提出了一个名为“思想树”（Tree of Thoughts, ToT）的新型语言模型推理框架。

核心问题：传统的自回归生成模型（如采用标准提示或思维链提示的模型）本质上是“系统1”思维，进行的是快速、直觉式的决策。这种方式缺乏深思熟虑的规划能力，无法探索多个推理路径，也难以进行前瞻或回溯来做出全局最优决策，因此在复杂的规划和搜索问题上表现不佳。

研究目标：借鉴人类解决问题时的“系统2”思维模式，即通过审慎、有意识的规划过程来增强语言模型。目标是设计一个框架，使语言模型能够：
1. 探索多样性：在一个决策点上，能够考虑多种不同的后续步骤或想法，而不仅仅是选择最可能的一个。
2. 自我评估与前瞻：能够评估当前推理路径的进展，并主动进行前瞻或必要时进行回溯，以做出更具全局观的决策。

创新点（ToT框架）：
ToT框架将问题解决过程建模为在一棵树上的搜索。
- 思想作为节点：树中的每个节点代表一个“思想”（thought），这是一个连贯的文本序列，作为解决问题的中间步骤。这与思维链（CoT）不同，CoT只探索单一的思想序列。
- 显式的生成与评估：ToT允许语言模型在每个节点上生成多个潜在的后续思想，并利用语言模型自身的能力对这些思想的优劣进行评估（作为搜索的启发式信息）。这种通过语言模型进行审慎推理以自我评估和指导搜索是全新的。
- 结合搜索算法：该框架可以灵活地结合各种经典的搜索算法，如广度优先搜索（BFS）或深度优先搜索（DFS），来系统地探索思想树，实现前瞻和回溯。
- 通用性和灵活性：ToT框架具有通用性，能够适应不同类型的问题，支持不同粒度的“思想”、不同的生成和评估方法以及不同的搜索策略。

为了验证ToT的有效性，作者设计了三个对现有模型极具挑战性的新任务：24点游戏、创意写作和迷你填字游戏。实验结果表明，ToT显著增强了GPT-4在这些需要非平凡规划或搜索的任务上的问题解决能力。例如，在24点游戏中，使用思维链提示的GPT-4成功率仅为4%，而ToT方法达到了74%的成功率。

A3 背景知识

现有方法的公式化
本文首先对现有使用大型语言模型解决问题的方法进行了形式化定义，这些方法是ToT框架的灵感来源和比较对象。文中用 $p\theta$ 表示一个拥有参数 $\theta$ 的预训练语言模型，用小写字母 $x, y, z, s$ 等表示语言序列（例如 $x = (x[1], \dots, x[n])$），其中每个 $x[i]$ 是一个词元（token），因此 $p\theta(x) = \prod_{i=1}^{n} p\theta(x[i]|x[1\dots i])$。大写字母 $S$ 等表示语言序列的集合。

输入-输出（IO）提示
这是将问题输入 $x$ 转换为输出 $y$ 的最常用方法：$y \sim p\theta(y|\text{prompt}_{\text{IO}}(x))$，其中 $\text{prompt}_{\text{IO}}(x)$ 将输入 $x$ 与任务指令和/或少样本输入-输出示例包装在一起。为了简化，作者将其表示为 $p_{\text{prompt}}^{\theta}(\text{output} | \text{input}) = p\theta(\text{output} | \text{prompt}(\text{input}))$，因此IO提示可以被形式化为 $y \sim p_{\text{IO}}^{\theta}(y|x)$。

思维链（CoT）提示
为了处理输入 $x$ 到输出 $y$ 的映射不直接的情况（例如数学问题），Wei等人【索引38，Chain of thought prompting elicits reasoning in large language models，2022】提出了思维链（CoT）提示。其关键思想是引入一系列思想 $z_1, \dots, z_n$ 来连接 $x$ 和 $y$，其中每个 $z_i$ 是一个连贯的语言序列，作为解决问题的有意义的中间步骤。使用CoT解决问题时，每个思想 $z_i \sim p_{\text{CoT}}^{\theta}(z_i | x, z_{1\dots i-1})$ 被依次采样，然后得出输出 $y \sim p_{\text{CoT}}^{\theta}(y|x, z_{1\dots n})$。实践中，$[z_{1\dots n}, y] \sim p_{\text{CoT}}^{\theta}(z_{1\dots n}, y|x)$ 是作为一个连续的语言序列被采样的，而思想的分解（例如每个 $z_i$ 是一个短语、一个句子还是一个段落）是模糊的。

带自洽性的思维链（CoT-SC）
Wang等人【索引36，Self-consistency improves chain of thought reasoning in language models，2022】提出的CoT-SC是一种集成方法。它独立同分布地采样 $k$ 条思维链：$[z_{1\dots n}^{(i)}, y^{(i)}] \sim p_{\text{CoT}}^{\theta}(z_{1\dots n}, y|x)$（对于 $i = 1, \dots, k$），然后返回最频繁出现的输出：$\arg \max_y \#\{i | y^{(i)} = y\}$。CoT-SC改进了CoT，因为它探索了解决同一问题的不同思考过程，从而使输出决策更加可靠。然而，在每条思维链内部，它没有对不同的思想步骤进行局部探索，并且“最频繁”的启发式方法只适用于输出空间有限的场景（如多项选择问答）。

A2 方法细节

ToT框架的动机与核心思想
Newell等人【索引21，Report on a general problem solving program，1959】认为，真正的问题解决过程涉及重复使用可用信息来启动探索，探索反过来又揭示更多信息，直到最终发现解决方案。人类问题解决的研究表明，人们在一个组合问题空间中进行搜索——这个空间可以表示为一棵树，节点代表部分解决方案，分支对应于修改它们的操作算子【索引21，Report on a general problem solving program，1959；索引22，Human problem solving，1972】。选择哪个分支由启发式方法决定，这些方法帮助在问题空间中导航并引导解决者找到解决方案。这一观点揭示了现有LM方法在解决一般问题时的两个关键不足：1）在局部，它们不探索一个思维过程中的不同延续，即树的分支。2）在全局，它们没有融合任何类型的规划、前瞻或回溯来帮助评估这些不同选项，而这种启发式引导的搜索似乎是人类问题解决的特征。

ToT框架的构建
为了解决这些不足，本文引入了思想树（ToT）框架，它允许语言模型探索多个基于思想的推理路径（如图1(c)所示）。ToT将任何问题都构建为在一个树上进行搜索，其中每个节点是一个状态 $s = [x, z_{1\dots i}]$，代表了包含输入和到目前为止的思想序列的部分解决方案。ToT的一个具体实例需要回答四个问题：1. 如何将中间过程分解为思想步骤；2. 如何从每个状态生成潜在的思想；3. 如何启发式地评估状态；4. 使用什么搜索算法。

1. 思想分解
与CoT隐式地、连贯地采样思想不同，ToT利用问题本身的属性来设计和分解中间思想步骤。如表1所示，根据不同的问题，一个思想可以是一个词组（填字游戏）、一行方程式（24点游戏），或一整个段落的写作计划（创意写作）。总的来说，一个思想应该足够“小”，以便语言模型能生成有前景且多样化的样本（例如，生成一整本书通常太“大”而难以连贯），但又要足够“大”，以便语言模型能评估其解决问题的前景（例如，生成一个词元通常太“小”而无法评估）。

2. 思想生成器 $G(p\theta, s, k)$
给定一个树状态 $s = [x, z_{1\dots i}]$，作者考虑了两种策略来生成下一步的 $k$ 个候选思想：
(a) 从CoT提示中独立同分布地采样思想（用于创意写作，见图4）：$z^{(j)} \sim p_{\text{CoT}}^{\theta}(z_{i+1}|s) = p_{\text{CoT}}^{\theta}(z_{i+1}|x, z_{1\dots i})$（$j = 1, \dots, k$）。当思想空间非常丰富时（例如每个思想是一个段落），这种方法效果更好，因为独立同分布的采样能带来多样性。
(b) 使用“提议提示”顺序地提出思想（用于24点游戏，见图2；填字游戏，见图6）：$[z^{(1)}, \dots, z^{(k)}] \sim p_{\text{propose}}^{\theta}(z_{i+1}^{(1\dots k)} | s)$。当思想空间更受约束时（例如每个思想只是一个词或一行），这种方法效果更好，因为在同一上下文中提出不同的思想可以避免重复。

3. 状态评估器 $V(p\theta, S)$
给定一组不同的前沿状态，状态评估器会评估它们在解决问题方面的进展，作为搜索算法的启发式信息，以决定保留哪些状态继续探索以及探索的顺序。虽然启发式方法是解决搜索问题的标准方法，但它们通常要么是编程实现的（如深蓝【索引3，Deep blue，2002】），要么是学习得到的（如AlphaGo【索引29，Mastering the game of go without human knowledge，2017】）。本文提出了第三种替代方案，即利用语言模型对状态进行审慎的推理。在适用时，这种审慎的启发式方法可以比编程规则更灵活，并且比学习模型样本效率更高。与思想生成器类似，作者考虑了两种策略来独立或共同评估状态：
(a) 独立评估每个状态：$V(p\theta, S)(s) \sim p_{\text{value}}^{\theta}(v|s) \forall s \in S$，其中一个价值提示会对状态 $s$ 进行推理，生成一个标量值 $v$（例如1-10分）或一个分类（例如“确定”/“可能”/“不可能”），这些可以启发式地转化为一个数值。这种评估性推理的依据可能因问题和思想步骤而异。在这项工作中，作者通过少量的前瞻模拟（例如快速确认5, 5, 14可以通过5 + 5 + 14得到24）加上常识（例如1, 2, 3太小无法达到24）来探索评估。前者可以促进“好”的状态，后者可以帮助排除“坏”的状态。这种估值不需要完美，只需要对决策提供大致的帮助。
(b) 跨状态投票：$V(p\theta, S)(s) = 1[s = s^*]$，其中一个“好”的状态 $s^* \sim p_{\text{vote}}^{\theta}(s^*|S)$ 是通过在一个投票提示中审慎地比较 $S$ 中的不同状态而被选出的。当问题的成功难以直接估值时（例如段落的连贯性），比较不同的部分解决方案并投票选出最有希望的一个是很自然的方式。这在精神上类似于一个“逐步”的自洽策略，即将“探索哪个状态”作为一个多项选择题，并使用语言模型样本为其投票。

对于这两种策略，我们可以多次提示语言模型来聚合价值或投票结果，以时间/资源/成本换取更可靠/鲁棒的启发式信息。

4. 搜索算法
最后，在ToT框架内，可以根据树的结构插入和使用不同的搜索算法。作者探索了两种相对简单的搜索算法，并将更高级的算法（如A【索引11，A formal basis for the heuristic determination of minimum cost paths，1968】、MCTS【索引2，A survey of monte carlo tree search methods，2012】）留给未来的工作：
(a) 广度优先搜索（BFS）（算法1）：每一步维护一组 $b$ 个最有希望的状态。这用于24点游戏和创意写作，其中树的深度有限（$T \le 3$），并且初始思想步骤可以被评估和剪枝到一个小的集合（$b \le 5$）。
(b) 深度优先搜索（DFS）*（算法2）：首先探索最有希望的状态，直到达到最终输出（$t > T$），或者状态评估器认为从当前状态 $s$ 解决问题是不可能的（$V(p\theta, \{s\})(s) \le v_{\text{th}}$，对于一个价值阈值 $v_{\text{th}}$）。在后一种情况下，从 $s$ 开始的子树被剪枝，以牺牲探索换取利用。在两种情况下，DFS都会回溯到 $s$ 的父状态以继续探索。

ToT框架的优势
从概念上讲，ToT作为一种用语言模型解决通用问题的方法有几个好处：（1）通用性。IO、CoT、CoT-SC和自精炼可以看作是ToT的特例（即深度和广度有限的树；图1）。（2）模块化。基础语言模型，以及思想的分解、生成、评估和搜索过程都可以独立变化。（3）适应性。可以适应不同的问题属性、语言模型能力和资源限制。（4）便利性。不需要额外训练，一个预训练的语言模型就足够了。下一节将展示这些概念上的好处如何转化为在不同问题上的强大实证性能。

A4 实验环境

• 模型架构: 实验主要使用GPT-4的聊天完成模式（Chat Completion mode），采样温度设置为0.7。附录中也包含了使用GPT-3.5-turbo的对比实验结果。
• 数据集/任务:
  • 24点游戏 (Game of 24): 从4nums.com网站上抓取数据，使用了100个被人类认为是较难的游戏（索引901-1000）进行测试。
  • 创意写作 (Creative Writing): 从randomwordgenerator.com网站上随机抽取句子，构成100个输入（每个输入包含4个随机句子）。
  • 迷你填字游戏 (Mini Crosswords): 从GooBix网站抓取5x5的迷你填字游戏数据，使用了20个游戏（索引为1, 6, ..., 96）进行测试，并使用另外5个游戏进行提示（prompting）。
• 硬件配置: 论文未明确说明硬件配置，实验通过调用GPT-4 API完成。
• 软件配置:
  • 代码实现基于Python，依赖于与GPT-4 API交互的库。
  • 所有代码和提示都已开源，代码库地址为：https://github.com/princeton-nlp/tree-of-thought-llm。

A4 实验结果

4.1 24点游戏

任务与设置:
24点游戏是一个数学推理挑战，目标是使用4个数字和基本算术运算（+、-、*、/）得到24。实验使用100个较难的游戏进行测试，成功标准是生成一个有效的、结果为24且每个输入数字恰好使用一次的等式。

基线方法:
- IO提示: 包含5个上下文示例的标准输入-输出提示。
- CoT提示: 在每个示例中加入3个中间方程式作为思想链。
- CoT-SC: 对100次CoT采样结果取多数投票。
- 迭代精炼: 在IO采样的基础上，如果答案错误，则让模型进行最多10次的反思和修正（此方法使用了关于等式正确性的真实反馈信号）。

ToT设置:
将问题分解为3个思想步骤，每步是一个中间方程。采用广度优先搜索（BFS），每步保留最优的 $b=5$ 个候选。如图2所示，ToT使用LM来生成可能的下一步（思想生成），并评估每个候选思想能够得到24的可能性（分为“确定/可能/不可能”三类），以此作为启发式信息指导搜索。

结果与分析:
如表2所示，IO、CoT和CoT-SC等基线方法表现很差，成功率分别只有7.3%、4.0%和9.0%。相比之下，ToT在搜索宽度 $b=1$ 时成功率就达到了45%，当 $b=5$ 时成功率高达74%。图3(a)显示，即使是100次CoT采样中的最佳结果（best of 100），成功率也只有49%，远低于ToT。图3(b)的错误分析表明，大约60%的CoT样本在生成第一步（例如“4 + 9”）后就已经失败，这凸显了传统从左到右解码方式的局限性。

4.2 创意写作

任务与设置:
输入4个随机句子，要求模型创作一个包含4个段落的连贯文章，且每个段落分别以这4个句子结尾。这是一个开放性、探索性的任务。由于没有标准答案，评估主要关注文章的连贯性，通过GPT-4打分（1-10分）和人类盲评两种方式进行。

基线方法:
- IO提示: 直接要求模型生成文章。
- CoT提示: 先让模型生成一个简要计划，再根据计划写文章。
- 迭代精炼: 在IO采样的基础上，让模型进行最多5次的自我评估和改进。

ToT设置:
采用深度为2的ToT结构。第一步，生成 $k=5$ 个不同的写作计划，然后通过投票选出最佳计划。第二步，基于最佳计划生成 $k=5$ 篇完整的文章，再次投票选出最终的输出。每一步只保留最佳选择（即 $b=1$）。

结果与分析:
如图5所示，ToT生成的文章在GPT-4评分和人类偏好上均优于IO和CoT。ToT的平均分为7.56，高于IO（6.19）和CoT（6.93）。在100对文章的人类盲评中，人类在41次中更偏爱ToT的输出，而只有21次偏爱CoT。迭代精炼方法也能有效提升文章质量，将ToT的得分从7.56提升至7.91。

4.3 迷你填字游戏

任务与设置:
解决5x5的迷你填字游戏，这是一个更难的、涉及自然语言的搜索问题。输入是横向和纵向的10条线索，输出是25个字母组成的棋盘。评估指标包括字母正确率、单词正确率和游戏完成率。

基线方法:
IO和CoT提示都包含了5个完整的解题示例。

ToT设置:
采用深度优先搜索（DFS）算法。每个“思想”是填入一个单词。在每个状态，模型会根据已填写的字母约束，为剩余的线索提出候选词，并给出置信度（如图6(a)）。DFS会优先探索置信度最高的路径。同时，模型会评估当前状态下，剩余的线索是否还有可能被填满（如图6(b)），如果某个线索被判断为“不可能”填入，则对该子树进行剪枝并回溯。

结果与分析:
如表3所示，IO和CoT表现不佳，单词正确率低于16%。ToT则显著提升了所有指标，单词正确率达到60%，并成功解决了20个游戏中的4个。这得益于ToT能够尝试不同线索、修改决策和回溯的能力。消融实验表明：
- 启发式的重要性：如果使用“上帝视角”选择DFS搜索过程中最好的状态作为输出，ToT能解决7个游戏，说明当前的状态评估和输出选择策略还有提升空间。
- 剪枝的有效性：去掉剪枝策略后性能普遍下降，但也解决了另外3个原方法无法解决的游戏，表明更好的剪枝启发式至关重要。
- 回溯的必要性：去掉回溯（即采用贪心策略）后，性能大幅下降，单词正确率仅为20%，证实了回溯机制的关键作用。

A5 结论

局限性与未来方向:
本文提出的审慎搜索方法，如思想树（ToT），对于许多GPT-4已经表现出色的任务可能并非必需。本文作为初步探索，仅聚焦于三个相对简单但对GPT-4仍有挑战性的任务，旨在呼吁将更好的搜索和规划能力与语言模型（LMs）结合。随着LMs在更复杂的现实世界决策应用（如编码、数据分析、机器人技术等）中的部署，新的挑战将不断涌现，为研究这些问题提供新的机遇。

此外，像ToT这样的搜索方法为了提升任务性能，需要比传统采样方法更多的资源（例如GPT-4 API成本）。但ToT的模块化灵活性允许用户根据需求定制性能与成本的权衡。同时，开源社区的努力有望在不久的将来降低这些成本。

最后，本文主要关注使用现成的LM。未来一个有前景的方向是，使用ToT式的高层反事实决策过程（例如，审慎考虑下一段落的可能选择，而非仅仅预测下一个词元）来微调LMs，这可能进一步增强其解决问题的能力。

结论:
本文认为，语言模型的联想式“系统1”思维可以通过基于搜索问题解决方案可能路径树的“系统2”来有效增强。思想树（ToT）框架提供了一种将关于问题解决的经典见解转化为适用于当代LMs的可行方法。同时，LMs也解决了这些经典方法的一个弱点，即为那些不易形式化的复杂问题（如创意写作）提供了解决方案。作者认为，将LMs与经典人工智能方法相结合是一个激动人心的研究方向。

A6 附录

B.1 扩展到新任务（GSM8k, StrategyQA）的零样本ToT

在简单任务上的适用性
尽管许多常见的自然语言处理任务对GPT-4来说可能过于简单，不需要ToT（这也是本文引入新难题的原因），但作者认为将ToT应用于新任务是直接的。例如，作者实现了一个简单通用的零样本ToT-BFS方法，类似于创意写作任务中的设置（采样5个问题解决策略然后投票选出最佳策略；然后基于最佳策略采样5个解决方案再投票选出最佳方案）。该方法通过少量代码即可应用于GSM8K和StrategyQA。

# define the answer format of new tasks
gsm8k_format = '"the answer is n" where n is a number'
strategyqa_format = 'either "the answer is yes" or "the answer is no"'

# define zero-shot io prompting
standard_prompt = 'Answer the following question with {format}: {input}'

# define thought format for zero-shot cot and zero-shot tot
cot_prompt = '''Answer the following question: {input}

Make a strategy then write. Your output should be of the following format:

Strategy:
Your strategy about how to answer the question.

Answer:
Your answer to the question. It should end with {format}.
'''

# define zero-shot voting used for zero-shot tot
vote_prompt = '''Given an instruction and several choices, decide which choice is most promising.
Analyze each choice in detail, then conclude in the last line "The best choice is {s}", where s the integer id of the choice.
'''

结果分析
作者在100个随机的GSM8K测试题和StrategyQA开发集问题上进行了评估。如表4所示，并且符合预期，ToT在两个任务上的表现都优于CoT。然而，提升幅度很小，因为GPT-4结合CoT在这些任务上已经表现非常出色，并且StrategyQA的瓶颈在于外部知识而非推理能力。考虑到计算成本，对于传统的NLP任务，更适合尝试使用较小的LLMs结合ToT；而对于挑战GPT-4+CoT推理能力的困难任务，则适合使用GPT-4结合ToT。

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

ToT在不同模型上的表现
为了解ToT在其他LLMs上的工作情况，作者还在创意写作（表6）和24点游戏（表5）任务上运行了GPT-3.5-turbo。在这两个任务上，“ToT > CoT > IO”的性能排序对GPT-3.5仍然成立。在创意写作任务中，作者发现GPT-3.5+ToT的表现优于GPT-4+IO，并且与GPT-4+CoT相似，这表明ToT在较弱的语言模型上也能很好地工作。

生成与评估能力的解耦分析
在24点游戏任务上（作者将1-shot提议提示改为3-shot使其生效），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个完成词元（completion tokens），接近于100次CoT试验（6.7k词元）。但ToT的性能优于100次独立CoT试验中的最佳结果。

在创意写作任务中（见下表8），作者发现ToT消耗的完成词元和金钱成本大约是CoT的5倍，这是符合直觉的，因为搜索宽度 $b=5$ 且大部分词元是生成的段落。

成本总结与实用建议
完成24点游戏和创意写作的主要ToT实验总共花费约 $0.74 \times 100 + 0.32 \times 100 = 106$ 美元。填字游戏的DFS实验也应在100美元以内。总的来说，ToT的成本和效率高度依赖于所使用的提示和搜索算法，可能需要比CoT多5到100倍的生成词元。一些可行的见解包括：
- 适用场景：建议在需要审慎推理且CoT难以解决的任务上使用ToT。
- 成本-性能权衡：ToT的灵活性允许进行性能-成本的权衡，例如，在BFS中改变束大小或投票数，使用少样本与零样本提示，使用GPT-3.5与GPT-4等。用户可以根据资源限制或性能目标来配置设置。
- 效率提升空间：效率提升有很大空间，例如，BFS可以在找到解决方案时提前停止，或者当某些思想被判定为“不可能”时削减束大小。
- 未来展望：作者相信，为了让模型实现更强的智能，确实需要更多的计算。从长远来看，随着（开源）LMs变得更便宜、更高效，这不应成为一个阻碍。如何更好地训练/微调LMs以进行思想生成和/或评估也是一个很好的研究方向。