本文引入了一种名为 ToT（Tree of Thoughts）的新型语言模型推理框架，使用 LLM 模拟人类的决策过程，以解决复杂问题。
GPT 和 PaLM 等大型语言模型在处理数学、符号、常识和知识推理等任务时正变得越来越熟练。也许令人惊讶的是，所有这些进展的基础仍然是生成文本的原始自回归机制。它逐个 token 地进行决策，并按从左到右的方式生成文本。这样简单的机制是否足以构建一个通用问题求解器的语言模型呢？如果不行，哪些问题将挑战当前的范式，应该采用什么样的替代机制呢？
有关人类认知的文献提供了一些线索来回答这些问题。关于「双过程（dual process）」模型的研究表明，人们在进行决策时有两种模式：一种是快速、自动、无意识的模式（System 1），另一种是缓慢、深思熟虑、有意识的模式（System 2）。这两种模式以前与机器学习中使用的各种数学模型联系在一起。例如，对人类和其他动物的强化学习的研究探讨了他们进行联想式的「无模型」学习或更加深思熟虑的「基于模型」的规划的情况。语言模型的简单联想式 token 级选择也类似于「System 1」，因此可能受益于更深思熟虑的「System 2」规划过程的增强，该过程保持并探索当前选择的多种替代方案，而不仅仅是选择一个。此外，它会评估其当前状态，并积极地展望或回溯以进行更全局的决策。
为了设计这样一个规划过程，来自普林斯顿大学、 Google DeepMind 的研究者选择先回顾一下人工智能（和认知科学）的起源，汲取 Newell、Shaw 和 Simon 在上世纪 50 年代探索的规划过程的灵感。Newell 和他的同事将问题解决描述为对组合式问题空间的搜索，这个空间被表示为一棵树。因此，他们提出了适用于语言模型的思维树（ToT）框架，用于通用问题求解。
论文链接：https://arxiv.org/pdf/2305.10601.pdf
项目地址：https://github.com/ysymyth/tree-of-thought-llm
正如图 1 所示，现有的方法通过对连续语言序列进行采样来解决问题，而 ToT 则积极地维护一棵思维树，其中每个思维都是一个连贯的语言序列，作为解决问题的中间步骤（表 1）。
这样一个高级语义单元使 LM 能够通过深思熟虑的推理过程来自我评估不同中间思维对解决问题的进展贡献情况（图 2、4、6）。通过 LM 的自我评估和深思熟虑来实现搜索启发式是一种新颖的方法，因为以前的搜索启发式要么是编程的，要么是学习得来的。
最后，研究者将这种基于语言的生成和评估多样思维的能力与搜索算法相结合，例如广度优先搜索（BFS）或深度优先搜索（DFS），这些算法允许对思维树进行系统性的探索，并具备展望和回溯功能。
在实验阶段，研究者设置了三项任务，即 24 点游戏、创意写作和填字游戏（表 1），这些问题对现有的 LM 推理方法来说颇具挑战性，即使对于 GPT-4 来说也不例外。这些任务要求具备演绎、数学、常识、词汇推理能力，以及一种融入系统性规划或搜索的方式。实验结果表明，ToT 在这三个任务上取得了优越的成绩，因为它具备足够的通用性和灵活性，可以支持不同层次的思维、不同生成和评估思维的方式，以及适应不同问题性质的不同搜索算法。通过系统的实验消融分析，作者还探讨了这些选择如何影响模型性能，并讨论了未来训练和使用 LM 的方向。
思维树：利用语言模型进行深思熟虑的问题求解
一个真正的问题求解过程涉及反复使用可用信息来启动探索，进而揭示更多信息，直到最终发现实现解决方案的方法。—— Newell 等
对人类问题求解的研究表明，人类通过搜索一个组合式问题空间来解决问题。这可以看作一棵树，其中节点表示部分解，分支对应修改它们的运算符。选择哪个分支是由启发式决定的，这些启发式帮助导航问题空间并引导问题解决者朝着解决方案的方向前进。这个观点突出了使用语言模型来解决通用问题的现有方法的两个关键缺点：1）局部上，它们不探索思维过程中的不同延续 —— 树的分支。2）全局上，它们不包括任何类型的规划、展望或回溯来帮助评估这些不同的选择 —— 这种启发式引导的搜索似乎是人类问题求解的特征。
为了解决这些问题，作者引入了思维树（ToT），这是一种让语言模型能够在思维路径上探索多种推理方式的范式（图 1 (c)）。ToT 将任何问题框架化为对树的搜索，其中每个节点是一个状态 s = [x, z_1・・・i ]，表示带有输入和迄今为止的思维序列的部分解。ToT 的具体实例包括回答以下四个问题：
1. 如何将中间过程分解为思维步骤；
2. 如何从每个状态生成潜在思维；
3. 如何启发式地评估状态；
4. 使用什么搜索算法。
1. 思维分解。虽然 CoT 在没有明确分解的情况下对思维进行连贯的采样，但 ToT 利用问题属性来设计和分解中间思维步骤。如表 1 所示，根据不同的问题，思维可以是几个单词（填字游戏），一个等式（24 点游戏），或者是一段写作计划（创意写作）。一般来说，思维应该足够「小（small）」，以便 LM 能生成预期多样化的样本（如生成太「大（big）」而不连贯一本书），但思维又应该足够「大」，以便 LM 可以评估其解决问题的前景（例如，生成一个 token 通常太小而无法评估）。
2. 思维生成器 G (p_θ， s, k)。给定树状态 s = [x, z_1・・・i]，该研究利用两种策略来为下一步思维 step 生成 k 个候选对象。
3. 状态评估器 V (p_θ， S)。给定不同状态的边界，状态评估器评估它们在解决问题方面的进展，以确定哪些状态应该继续探索，以及以何种顺序进行探索。虽然启发式是解决搜索问题的标准方法，但它们通常要么是编程式的（例如 DeepBlue），要么是需要经过学习的（例如 AlphaGo）。本文提出第三种替代方法，通过使用语言来有意地推理状态。在适用的情况下，这种深思熟虑的启发式方法可能比编程规则更灵活，比学习模型更有效。
与思维生成器类似，考虑两种策略来单独或一起评估状态：
（1）独立评估每个状态
（2）跨状态投票
这两种策略，可以多次提示 LM 来整合价值或投票结果，用时间、资源、成本换得更加可靠、鲁棒的启发式。
4. 搜索算法。最后，在 ToT 框架内，可以根据树结构即插即用不同的搜索算法。本文探索了两个相对简单的搜索算法，并将更高级的算法留作以后进行研究：
（1）广度优先搜索（BFS）(算法 1)
（2）深度优先搜索（DFS）(算法 2)
从概念上讲，ToT 作为语言模型解决一般问题的方法有几个好处：
（1）通用性。IO、CoT、CoT- sc 和自我细化可以看作 ToT 的特殊情况（即深度和广度有限的树；图 1）；
（2）模块化。基本的 LM 以及思维分解、生成、评估和搜索过程都可以独立变化；
（3）适应性。可以适应不同的问题属性、LM 能力和资源约束；
（4）便捷性。无需额外的训练，只需要一个预训练的 LM 就足够了。
实验结果
该研究提出了三个任务，即便使用最先进的语言模型 GPT-4，通过标准的 IO prompting 或思维链（CoT）prompting 进行采样，这些任务仍然具有挑战性。
24 点数学游戏
给定四个数字，玩家需要在限定的时间内使用这四个数字和基本数学运算符号（加号、减号、乘号、除号）来创建一个表达式，使其结果为 24。比如，给定数字：4、6、8、2，一个可能的解法是：(8 ÷ (4 - 2)) × 6 = 24。
如表 2 所示，使用 IO、CoT 和 CoT-SC prompting 方法在任务上表现不佳，仅实现了 7.3%、4.0% 和 9.0% 的成功率。相比之下，b（breadth） = 1 的 ToT 已经实现了 45% 的成功率，而 b = 5 时则达到了 74%。他们还考虑了 IO/CoT 的 oracle 设置，通过使用 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）。
下图 3 (b) 分解了 CoT 和 ToT 样本在任务失败时的情况。值得注意的是，大约 60% 的 CoT 样本在生成第一步，相当于生成前三个单词 (例如 “4 + 9”) 后就已经失败了。这让直接从左到右解码的问题更加凸显了。
创意写作
研究者还发明了一个创意写作任务，输入 4 个随机句子，输出一篇包含四段的连贯文章，每段分别以 4 个输入句子结尾。这样的任务是开放式和探索性的，挑战了创造性思维和高级规划。
下图 5 (a) 显示了 GPT-4 在 100 个任务中的平均分数，其中 ToT (7.56) 比 IO (6.19) 和 CoT (6.93) 生成了更连贯的段落。虽然这样的自动度量可能会有噪声，但图 5 (b) 证实，人类在 100 passage 对中有 41 对更喜欢 ToT 而不是 CoT，而只有 21 对更喜欢 CoT 而不是 ToT (其他 38 对被发现 “相似连贯”)。
最后，迭代优化算法在该自然语言任务上取得了更好效果，IO 一致性得分从 6.19 提高到 7.67，ToT 一致性得分从 7.56 提高到了 7.91。研究者认为，这可以看作是 ToT 框架中思维生成的第三种方法，新思维可以从细化旧思维中产生，而不是顺序生成。
迷你填字游戏
在《24 点数学游戏》和创意写作中，ToT 是比较浅显的 —— 最多需要 3 个思考步骤就能达到最终的输出。研究者将探索 5×5 迷你填字游戏作为有关自然语言的更难一层的搜索问题。同样，这次的目标不仅仅是解决任务，因为一般填字游戏可以通过专门的 NLP pipeline 轻松解决，该 pipeline 利用大规模检索而不是 LM。相反，研究者的目标是探索语言模型作为一个通用问题求解器的极限，探索它自身的思维，并以严谨的推理作为启发式来指导自己的探索。
如下表 3 所示，IO 和 CoT 提示方法表现不佳，单词级别的成功率低于 16%，而 ToT 显著提高了所有指标，实现了 60% 的单词级别成功率，在 20 个游戏中解决了 4 个。考虑到 IO 和 CoT 缺乏尝试不同线索、更改决策或回溯的机制，这样的提升并不令人惊讶。
