论文标题：Tree of Thoughts: Deliberate Problem Solving with Large Language Models
论文链接：https://arxiv.org/abs/2305.10601
论文来源：arXiv
一、概述
语言模型(LM)比如GPT、PaLM等，虽然最初是为生成文本而设计，但它们的大规模版本已经显示出了越来越强的多任务推理能力，可以进行数学、符号、常识和知识推理。或许令人惊讶的是，所有这些进步的底层仍然是最初的在文本生成中的自回归机制，它逐个词地、从左到右地做出决策。这样一个简单的机制是否足以构建一个通用问题求解器？如果不够，会有哪些问题挑战现有范式？又需要什么替代机制？
关于人类认知的研究提供了一些线索来回答这些问题。“双进程(dual process)”模型的研究表明，人们在做决策时有两种模式 —— 一种是快速、自动、无意识的(fast, automatic, unconscious)模式(“系统1”)，一种是慢速、经过深思熟虑、有意识的(slow, deliberate, conscious)模式(“系统2”)。这两种模式之前就与机器学习中使用的各种数学模型相关联过。例如，关于人类和其他动物的强化学习研究已经探讨了它们什么时候进行联想的“模型无关”学习，什么时候进行更深思熟虑的“模型相关”规划。语言模型简单的联想式逐词选择也与“系统1”相似，因此可能会从一种更深思熟虑的“系统2”规划过程中获益，这种过程(1)维护和探索当前选择的各种可能性，而不仅仅选择一个，(2)评估其当前状态，并主动前瞻或回溯(lookahead or backtracking)以做出更全局的决策。
为了设计这样的规划流程，我们回归人工智能(和认知科学)的起源，从Newell, Shaw和Simon在20世纪50年代探索的规划流程中获得启发。Newell等人将问题求解表征为在组合问题空间(combinatorial problem space)中进行搜索，用树来表示。因此我们为语言模型的通用问题求解提出了“思维树”(Tree of Thoughts， ToT)框架。如下图所示，现有的方法对问题求解采样连续的语言序列，而ToT主动维护一个思维树，其中每个thought都是连贯的(coherent)语言序列，作为问题求解的中间步骤。这样一个高层语义单元使得语言模型能够通过精心的推理过程来自我评估(self-evaluate)不同的中间thought对于解决问题的进展。本文通过语言模型的自我评估和推理来实现搜索启发式方法是新颖的，因为以前的搜索启发式方法要么是编程实现的，要么是学习得到的。最后，我们将这种生成和评估多样thought的基于语言的能力与搜索算法(如广度优先搜索BFS或深度优先搜索DFS)相结合，这使得我们可以系统地探索思维树以进行前瞻和回溯。
本文的实验提出了三个新的问题，它们即使对最先进的语言模型GPT-4也具有挑战性:24点游戏、创意写作和填字游戏(Game of 24, Creative Writing, and Crosswords)。这些任务需要演绎推理、数学、常识和词汇推理的能力，以及一种将系统的规划或搜索融入的方式。我们表明，通过支持不同层次的thought、生成和评估thought的不同方式、根据不同问题性质采用不同的搜索算法，ToT框架对所有三个任务都取得了优越的结果。我们还通过系统的消融实验分析了这些选择如何影响模型表现，并讨论了进一步训练和使用语言模型的未来方向。
二、背景
我们首先形式化一些使用大型语言模型进行问题求解的现有方法，我们的方法受到这些方法的启发并与之进行了比较。我们使用表示一个预训练语言模型及其参数
，使用小写字母
表示一个语言序列，即
，其中每个
是一个token，因此
。我们使用大写字母
表示一组语言序列。
- Input-output (IO) prompting
Input-output (IO) prompting是最常见的将问题输入转化为语言模型输出
的方式:
，其中
在输入
周围包裹任务说明和/或小样本输入输出示例。为简单起见，我们记
，所以IO提示可以表示为
。
- Chain-of-thought (CoT) prompting
Chain-of-thought (CoT) prompting是为了解决输入到输出
之间的映射更困难的情况而提出的(例如当
是一个数学问题而
是最终的数值答案)。其关键思想是引入一条思维链
来桥接
和
，其中每个
是一个连贯的语言序列，作为有意义的中间步骤来解决问题(例如，
可以是数学问答的中间方程)。为了用CoT求解问题，每个thought
都是顺序生成的，然后输出
。实践中，
作为一个连续的语言序列进行采样，thought的分解(decomposition)是模糊的（也就是关于每个
是一个短语、一个句子还是段落），也就是说thought之间没有明确的边界。
- Self-consistency with CoT (CoT-SC)
Self-consistency with CoT (CoT-SC)是一种集成方法，它采样条独立同分布的思维链:
，然后返回最频繁的输出:
。CoT-SC改进了CoT，因为对于同一个问题通常有不同的思考过程(例如证明同一定理的不同方法)，通过探索更丰富的thought集合，输出决策可以更可靠。但是，在每条链内部都没有对不同thought步骤的局部探索，而且“最频繁”这种启发式方法只适用于输出空间有限的情况(例如多项选择问答)。
三、方法
A genuine problem-solving process involves the repeated use of available information to initiate exploration, which discloses, in turn, more information until a way to attain the solution is finally discovered. —— Newell et al.
关于人类求解问题的研究表明，人们在组合问题空间(也就是一个树结构)中进行搜索，其中节点表示部分解决方案，分支对应修改它们的操作符。选择哪条分支由启发式方法决定，这有助于在问题空间中导航，引导问题求解者朝着解决方案的方向前进。这一视角突出了现有使用语言模型求解一般问题方法的两个关键缺陷:(1) 在局部上，它们不搜索思维过程中的不同延续 - 树的分支；(2) 在全局上，它们没有融入任何类型的规划、前瞻或回溯以帮助评估这些不同选项 —— 这种启发式引导搜索似乎是人类求解问题方式的特征。
为了解决这些缺陷，我们提出了“思维树”(Tree of Thoughts， ToT)范式，它允许语言模型在thought上搜索多种推理路径。ToT将任何问题框定为在一棵树上搜索，其中每个节点是一个状态，表示到目前为止的带有输入和thought序列的部分解决方案。ToT的一个具体实例需要回答四个问题:
①如何将中间过程分解(decompose)为thought步骤；
②如何从每个状态生成(generate)潜在的思维；
③如何启发式地评估(evaluate)状态；
④使用什么搜索(search)算法。
- Thought decomposition
CoT在没有显式分解的情况下连贯地对thought进行采样，而ToT利用问题的属性来设计和分解中间thought步骤。如下表所示，根据不同的问题，一个thought可以是几个词(填字游戏)，一个方程(24点游戏)，或是一个完整的写作计划段落(创意写作)。通常来说，一个思维应该足够“小”，以便语言模型可以生成有前景且多样化的样本(例如生成一整本书通常太“大”而无法连贯)，但也应该足够“大”，以便语言模型可以评估它对解决问题的前景(例如生成一个token通常太“小”而无法进行评估)。
- Thought generator
给定一个树状态，我们考虑两种生成下一个thought步骤的
个候选的策略:
①从CoT提示中采样(Sample)独立同分布的多个thought(比如创意写作任务，见下图4): 。当思维空间足够丰富时(例如每个思维是一个段落)，独立同分布的采样可以带来多样性，这种方法效果更好。
②使用“propose prompt”来对可能的thought提出建议(Propose)(比如24点游戏，见下图2；填字游戏，见下图6):。当思维空间更受约束时(例如每个思维只是一个词或一行)，在同一上下文提出不同的thought可以避免重复。
- State evaluator
给定最新状态的集合，state evaluator评估它们对于解决当前问题的价值，也就是作为搜索算法的启发式标准来确定对哪些状态保持搜索以及搜索顺序。虽然启发式方法是解决搜索问题的标准方法，但它们通常要么是编程实现的(例如DeepBlue)，要么是学习得到的(例如AlphaGo)。我们提出了第三种选择，即使用语言模型来深思熟虑地推理状态。在适用的情况下，这样的深思熟虑型启发式方法可以比编程规则更灵活，也比学习得到的模型采样更高效。类似于thought generator ，我们考虑独立或一起评估状态的两种策略:
①独立评分(Value)每个状态:，这里使用一个 value prompt通过对状态
进行推理来生成一个标量值
(例如1-10)或一个分类结果(例如sure/likely/impossible)，这些可以启发式地转化为一个值。这种评估推理的基础在不同问题和thought步骤中有所不同。在本文实验中，我们通过几步前瞻模拟(例如快速确认5，5，14可以通过5 + 5 + 14达到24，或“hot_l”可以通过在“_”中填入“e”得到“inn”)以及常识(例如1 2 3太小而无法达到24，或没有词可以以“tzxc”开头)来评估当前状态。前者可能推进“好”状态，而后者可以帮助消除“坏”状态。这样的评估不需要完美，只需要近似即可。
②跨状态投票(Vote):，其中一个“好”状态
是通过在vote prompt中比较
中的不同状态进行投票产生的。当问题的成败很难直接评估时(例如段落的连贯性)，比较不同的部分解并投票给最有前景的一个是很自然的做法。这在思想上与““step-wise”自洽策略类似，即将“搜索哪个状态”转换为多项选择QA，并使用语言模型样本对其进行投票。
对于两种策略，我们可以多次提示语言模型来聚合价值或投票结果，以时间/资源/成本换取更可信/健壮的启发式结果。
- Search algorithm
最后，在ToT框架内，可以根据树的结构结合不同的搜索算法。我们探索了两个相对简单的搜索算法:
①广度优先搜索(BFS):在每一步维护个最有前景的状态集合。这用于游戏24点和创意写作，这些任务中树的深度是有限的(
)，且初始thought步骤可以评估和修剪为一个小集合(
)。
②深度优先搜索(DFS):先搜索最有前景的状态，直到达到最终输出()，或state evaluator认为从当前
不可能解决问题(
，其中
是一个阈值)。在后一种情况下，剪枝
的子树以换取利用率。在以上两种情况下，DFS回溯到
的父状态以继续搜索。
概念上，作为利用语言模型进行通用问题求解的方法，ToT具有几个优势:
①通用性。IO、CoT、CoT-SC和self-refinement都可以看作是ToT的特例(即有限深度和宽度的树，如前图1所示)。
②模块化。基础语言模型以及thought分解、生成、评估和搜索过程都可以独立变化。
③适应性。可以适应不同的问题特性、语言模型能力和资源约束。
④方便性。不需要额外训练，仅需要一个预训练语言模型即可。
四、实验
- 24点游戏
- 创意写作
- 填字游戏
