语言模型正在越来越多地被部署用于各种任务的通用问题求解,但在推理时仍然局限于令牌级别的、从左到右的决策过程。这意味着它们在需要探索、战略性展望或初始决策发挥关键作用的任务中可能会遇到困难。为了克服这些挑战,我们提出了“思维树”(ToT)框架用于语言模型推理,其概括了流行的“思维链”方法,并支持在当前思维步骤上探索连贯的文本单元(“思维”),这些思维作为问题求解的中间步骤。ToT允许LM进行精心的决策制定,通过考虑多种不同的推理路径并自我评估选择来决定下一步行动,并在必要时展望未来或回溯以做出全局选择。我们的实验结果显示,与需要非平凡规划或搜索的三个新任务相比,ToT显著增强了语言模型的问题求解能力:24点游戏、创作写作和迷你填字游戏。例如,在24点游戏中,GPT-4链条思维提示只解决了4%的任务,而我们的方法达到了74%的成功率。代码仓库包含所有提示:https://github.com/ysymyth/tree-of-thought-llm。
论文原文地址：2305.10601.pdf (arxiv.org)
一、简介
最初被设计用来生成文本,像GPT [22,23,1,20] 和PaLM [5] 等放大后的语言模型已经被证明在越来越广泛的任务中具有数学、符号、常识和知识推理能力。或许令人惊讶的是,支撑所有这些进步的仍然是原始的自动回归机制来生成文本,它逐词做出决策,并以从左到右的方式进行。一个如此简单的机制是否足以构建一个通用的问题求解器?如果不是,会有哪些问题挑战现有的范式,又应该有什么替代机制?
人类认知学文献对回答这些问题提供了一些线索。关于“双重过程”模型的研究表明,人们有两种模式来参与决策 - 一种是快速、自动、无意识的模式(“系统1”),一种是缓慢、精心、有意识的模式(“系统2”) [27,28,13,12]。这两种模式之前与机器学习中使用的各种数学模型相关联。例如,关于人类及其他动物的强化学习的研究探讨了他们什么时候参与联想“无模型”学习或更精心的“有模型”规划 [6]。LM简单的联想式逐词选择也令人联想到“系统1”,因此可能会从一种更精心的“系统2”规划过程中获益,该过程(1)维护和探索当前选择的不同替代方案,而不仅仅挑选一个,(2)评估其当前状态,并主动展望未来或回溯以做出更全局的决定。
为了设计这样的规划过程,我们返回人工智能(和认知科学)的起源,从Newell、Shaw和Simon在20世纪50年代开始探索的规划过程中获得灵感[18,19]。 Newell等人将问题求解[18]描述为在组合问题空间中进行搜索,用树来表示。因此,我们提出“思维树”(ToT)框架用于语言模型的通用问题求解。图1所示,而现有方法(详见下文)对问题求解采样连续语言序列,ToT主动维护一个思维树,其中每个思维是一个连贯的语言序列,作为问题求解的中间步骤(表1)。这样一个高级语义单元允许LM通过一种也以语言实例化的精心推理过程(图2,4,6)来自我评估不同中间思维对解决问题的进展。思维的生成和评估方式的这种基于LM自我评价和精心推理的实施是全新方式,因为以前的搜索启发式要么是编程的要么是学习的。最后,我们将这种基于语言的生成和评估不同思维的能力与搜索算法(如广度优先搜索或深度优先搜索)相结合,这允许有条不紊地探索思维树,并进行展望和回溯。
从经验上,我们提出了三个新的问题,即使使用最先进的语言模型GPT-4 [20],标准的输入输出提示或思维链提示也难以解决:24点游戏、创意写作和填字游戏(表1)。这些任务需要演绎、数学、常识、词汇推理能力,以及某种系统的规划或搜索方式。我们展示了ToT如何通过其灵活通用的框架获得所有三个任务上的卓越表现,支持不同粒度的思维,不同的思维生成和评估方式,以及不同的搜索算法以适应不同问题的性质。我们还通过系统的消融实验分析了这些选择如何影响模型性能,并讨论了进一步训练和使用LM的未来方向。
二、背景
我们首先公式化一些现有的使用大型语言模型进行问题求解的方法,我们的方法受到这些方法的启发并在后面与之进行比较。我们使用 pθ 表示预训练的LM,其参数为θ,并使用小写字母 x, y, z, s 等表示语言序列,即 x = (x[1],...,x[n]),其中每个 x[i] 是一个词元,因此 pθ(x) = ∏ni=1 pθ(x[i]|x[1...i])。我们使用大写字母 S等表示一组语言序列。
输入输出(IO)提示是最常见的一种将问题输入 x 转化为输出 y 的方式:y ∼ pθ(y|promptIO(x)),这里 promptIO(x) 使用任务指令和/或少量输入输出示例来包装输入 x。为简化,我们记 ppromptθ (output|input) = pθ(output|prompt(input)),这样 IO 提示可以表示为 y ∼ pIOθ (y|x)。
思维链(CoT)提示是为处理输入 x 到输出 y 的映射非平凡的情况而提出的(例如当 x 是数学问题而 y 是最终的数值答案)。其关键思想是引入一系列思维链 z1, ..., zn 来连接 x 和 y,其中每个 zi 是一个有意义的中间步骤的连贯语言序列(例如 zi 可以是作用在两个剩余数字上的中间方程)。要用 CoT 来解决问题,每个思维 zi ∼ pCoTθ (zi|x, z1...i−1) 被顺序采样,然后输出 y ∼ pCoTθ (y|x, z1...n)。在实践中,[z1...n, y] ∼ pCoTθ (z1...n, y|x) 作为一个连续语言序列被采样,思维的分解(例如每个 zi 是短语、句子还是段落)是模糊的。
自洽性思维链(CoT-SC) 是一种集成方法,独立地对 k 个思维链进行采样:[z(i)1...n, y(i)] ∼ pCoTθ (z1...n, y|x)(i = 1...k),然后返回最频繁的输出:argmaxy #{i | y(i) = y}。CoT-SC 改进了 CoT,因为对于同一个问题通常有不同的思维过程(例如证明同一定理的不同方法),通过探索更丰富的思维集合,输出决策可以更加准确。但是,在每个链内部没有进行局部探索不同的思维步骤,“最频繁”启发式只适用于输出空间有限的情况(例如多项选择题QA)。
三、思维树:使用LM进行精心问题求解
一个真正的问题求解过程涉及可用信息的重复使用以发起探索,这又披露了更多信息,直到最终发现解决问题的方法。—— Newell等
人类问题求解研究表明,人们在组合问题空间中进行搜索 - 一个树,其中节点表示部分解决方案,分支对应修改它们的运算符。要走哪个分支由启发式决定,以帮助导航问题空间并引导问题求解者朝着解决方案前进。这一视角突出了目前使用LM解决一般问题的方法的两个关键缺陷:1) 在本地,它们不探索思维过程中的不同延续 - 树的分支;2) 在全局上,它们不包含任何类型的规划、展望或回溯以帮助评估这些不同选项 - 似乎是人类问题求解的特征性启发式引导搜索。
为了解决这些缺陷,我们引入了思维树(ToT),一种范式,允许LM对思维(图1(c))进行多种推理路径的探索。ToT将任何问题框架化为在一棵树上进行搜索,其中每个节点是一个状态 s = [x, z1...i],表示带有输入和迄今为止的思维序列的部分解决方案。ToT的一个具体实例涉及回答四个问题:
1. 如何将中间过程分解成思维步骤;
2. 如何从每个状态生成潜在思维;
3. 如何启发式地评估状态;
4. 使用什么搜索算法。
1. 思维分解。而CoT连贯地对思维进行采样而不明确分解,ToT利用问题特性设计和分解中间思维步骤。如表1所示,根据不同问题,一个思维可以是几个词(填字游戏),一行等式(24点游戏),或一个完整段落的写作计划(创意写作)。通常,一个思维应该“足够小”以便LM可以生成有希望和不同的样本(例如生成一整本书通常太“大”难以连贯), 然而又要“足够大”让大模型可以评估方案前景（例如，token级别通常太小了难以评估）。
2. 思维生成器G(pθ, s, k)。给定一个树状态 s = [x, z1...i],我们考虑两种策略生成下一个思维步骤的k个候选项:
(a) 从CoT提示中独立采样思维(创意写作,图4): z(j) ∼ pCoTθ (zi+1|s) = pCoTθ (zi+1|x, z1...i) (j = 1...k)。当思维空间丰富时(例如每个思维是一个段落),独立样本导致多样性效果较好;
(b) 使用“提议提示”顺序生成思维(24点游戏,图2;填字游戏,图6): [z(1),...,z(k)] ∼ pproposeθ (z(1...k)i+1 | s)。当思维空间更受约束时(例如每个思维只是一个词或一行)在同一上下文提议不同思维可以避免重复。
3. 状态评估器V(pθ, S)。给定不同状态的前沿集合,状态评估器评估它们对解决问题的进展,作为搜索算法的启发式来确定哪些状态保留探索以及探索顺序。虽然启发式是解决搜索问题的标准方法,但它们通常要么是编程的(例如DeepBlue [3])要么是学习的(例如AlphaGo [26])。我们提出第三种替代方案,使用LM进行精心推理状态。在可行时,这样的精心启发式可以比编程规则更灵活,比学习模型更高效。与思维生成器类似,我们考虑独立或一起评估状态的两种策略:
(a) 对每个状态独立赋值:V(pθ, S)(s) ∼ pvalueθ (v|s) ∀s ∈ S,其中一个值提示会推理状态s来生成一个标量值v(例如1-10)或分类(例如肯定/可能/不可能),可以启发式地转化成一个值。这种评价推理的基础可以根据不同的问题和思维步骤而变化。在本文中,我们探索了通过少量前瞻性模拟进行评估(例如快速确认5、5、14可以通过5 + 5 + 14达到24,或者“hot l”可以意味着“inn”通过在“ ”中填写“e”),以及常识(例如1 2 3太小无法达到24,或者没有词可以以“tzxc”开头)。前者可能推动“好”状态,后者可以帮助消除“坏”状态。这些估值不需要完美,只需要大致准确。
(b) 跨状态投票:V(pθ, S)(s) = 1[s = s∗], 其中一个“好”状态 s∗ ∼ pvoteθ (s∗|S)是通过在投票提示中精心比较S中的不同状态而产生的。当问题的成功难以直接评估时(例如段落的连贯性),比较不同的部分解决方案并投票给最有希望的一个是自然的。这在精神上与“逐步”自洽策略相关,即将“要探索的状态”配置为多项选择QA,并使用LM样本对其投票。
对于两种策略,我们都可以提示LM多次以聚合价值或投票结果,以牺牲时间/资源/成本来获得更准确/稳健的启发式。
4. 搜索算法。最后,在ToT框架内,可以插入和使用不同的搜索算法,这取决于树的结构。我们探索两种相对简单的搜索算法,更高级的(例如A* [9], 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。下一节将展示这些概念优势如何转化为不同问题上的强大的实证表现。
3.1 TOT的一个简单的例子
假设我们要用TOT来帮助GPT解决一个数学题:
输入:2 + 3 × 4 = ?
思维分解:我们可以分解成以下2个思维步骤:
1) 计算:3 × 4 = 12
2) 计算:2 + 12 = 14
思维生成:在每一步,我们可以让GPT提出多个可能的思维,例如在第一步可以生成:
思维1: 3 × 4 = 10
思维2: 3 × 4 = 12
思维3: 3 × 4 = 14
状态评估:我们可以让GPT根据已有知识对上述多个思维进行评估,判断哪个思维是正确的。在这个例子中,它应该可以判断出“思维2”是正确的。
搜索算法:我们可以使用深度优先搜索,每次先探索GPT评估为最有可能正确的思维,直到得到最后的算式和答案。
所以TOT通过让GPT生成并评估多种可能的思维,并利用搜索算法有方向地探索这些思维,来帮助GPT更有效地解决需要多个步骤的复杂问题。
3.2 实际的复杂问题场景中进行思维分解的例子
1. 数学证明问题
可以将证明分解为多个步骤,每一步对应证明中的一个论点或定理。比如要证明定理A,可以分解为:
思维1:证明引理B
思维2:由引理B得出C
思维3:由C可知D
思维4:由D可直接得出定理A
2. 编程问题
可以将编程任务分解为描述问题需求、设计解决方案、编写具体代码等步骤。比如实现一个排序算法,可以分解为:
思维1:明确排序算法的需求和效率要求
思维2:设计选择快速排序算法的理由
思维3:编写快速排序算法的伪代码
思维4:编写具体的代码实现
3. 写作创作
可以分解为创意提出主题、构思大纲、扩展细节等步骤。比如写一篇影评文章,可以分解为:
思维1:根据观影体会,提取出合适的题目
思维2:拟定文章三段论点的框架
思维3:补充每个论点的论据和例子
思维4:扩展具体观点,并作结论
所以对不同问题,都需要充分分析其过程和步骤,进行合理的思维分解,这确实是ToT方法的关键和难点。需要根据具体问题的特点来设计。
3.3 对于同一类问题,思维分解可以设计出较统一的模式。
1. 数学证明问题
通常可以分解为:理解定义 -> 推导引理 -> 构造辅助 -> 得出定理
2. 编程问题
通常可以分解为:分析需求 -> 设计方案 -> 编写伪代码 -> 实现代码
3. 写作问题
通常可以分解为:提出主题 -> 构思框架 -> 展开细节 -> 组织文章
4. 策略游戏
通常可以分解为:观察局势 -> 制定目标 -> 评估选项 -> 执行操作
可以看到,对于同一类问题,我们通常可以根据该领域的一般思维流程,设计出一个较为固定的思维分解模板。
这种统一的分解模式有以下好处:
1. 可以帮助LM更好地理解和迁移到新的问题上
2. 可以更好地设计通用的思维生成提示
3. 可以积累同类型问题的思维评估经验
当然,针对每个具体问题,还是需要做一定自定义和调整,但有了统一模式可以大大降低ToT方法应用的门槛。总之,发掘问题的共性思维模式,可以提升ToT的泛化能力。
3.4一个稍微复杂的ToT例子
假设我们要用ToT来帮助GPT解决一个规划行程的问题:
输入:我周五需要从A城去B城出差,现在是周一早晨。
思维分解:我们可以分解成以下4个思维步骤:
1) 查询A城到B城之间的交通工具
2) 对每个交通工具查询可行的出行时间
3) 评估不同交通工具的价格、耗时、舒适度等优劣
4) 根据优劣比较,选择最佳交通方案
思维生成:在每一步,我们提示GPT生成若干候选思维,例如第1步可能生成:
思维1:高铁
思维2:大巴
思维3:飞机
思维评估:我们可以提示GPT根据实际情况判断不同思维的合理性,例如第3步可能得到:
思维1: 价格**: 时间*** 舒适度**
思维2: 价格**: 时间** 舒适度*
思维3: 价格*: 时间*** 舒适度***
搜索算法:我们可以使用广度优先搜索,在每个步骤保留较好的思维,最后输出最优解“选择飞机”。
通过让GPT生成并评估多种可能思维来有目的地探索解空间,ToT可以帮助GPT改进复杂规划与决策。
3.5 ToT和决策树关键区别:
1. 决策树通常需要人工设计或学习树的结构和节点,而ToT的思维树完全由语言模型生成。
2. 决策树节点存储的通常是离散特征或规则,而ToT中的思维节点包含连贯的语言序列。
3. 决策树进行精确的规则比较,而ToT中的思维评估是语言模型进行模糊推理。
4. 决策树要求遍历整棵树得到解,而ToT可以通过启发式搜索找到解。
5. ToT的思维表示更加解释性,语言模型可以为推理过程生成解释。
6. ToT可以处理不确定环境,根据新信息动态调整思维树。决策树更固定。
7. ToT可以应用在非结构化任务如创意写作,决策树更擅长结构化决策。
8. ToT依赖预训练语言模型的质量,决策树依赖人工设计。
9. ToT搜索代价较大,决策树可以高效地遍历得到解。
总之,ToT依赖语言模型的自主推理,获取更强的自主性,适用范围更广,但决策树在结构化决策中更高效。两者有各自的优势。
四、实验
4.1 24点游戏
24点游戏是一个数学推理挑战,目标是用4个数字和基本的算术运算(+-*/)得到24。例如,给定输入“4 9 10 13”,一个可能的解决方案输出是“(10 - 4) * (13 - 9) = 24”。
任务设置。我们从4nums.com上爬取数据,该网站包含1,362个游戏,根据人类解题时间由易到难排序,我们使用索引为901-1000的较难游戏作为测试集。对于每个任务,如果输出是一个有效的等式,使用输入数字各一次并得到24,我们就视为成功。我们在100个游戏上报告成功率作为指标。
基线方法。我们使用一个标准的输入输出(IO)提示,包含5个同类型的上下文例子。对于思维链(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对每个思维候选进行“确定/可能/不可能”的评估,目的是推动正确的部分解决方案,这些在进行少数前瞻试验后就可以明确,并基于“太大/太小”的常识排除不可能的部分解决方案,其余的保持“可能”。我们对每个思维采样3次值。
结果。如表2所示,IO、CoT和CoT-SC提示方法在任务上表现很差,仅获得7.3%、4.0%和9.0%的成功率。相比之下,即使ToT的宽度b=1也已经获得了45%的成功率,而b=5达到了74%。我们还考虑了IO/CoT的一个理想设置,通过计算1≤k≤100的最佳k个样本的成功率。为了将IO/CoT(最佳k个)与ToT进行比较,我们考虑计算ToT在b=1···5时每个任务访问的树节点数量,并在图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.2 创意写作
接下来,我们设计了一个创意写作任务,输入是4个随机句子,输出应该是一个连贯的段落,包含4个段落并分别以4个输入句子结尾。这样的任务是开放和富有探索性的,对创造性思维以及高层次的规划提出了挑战。
任务设置。我们从随机词生成器网站sampling随机抽样句子形成100个输入,每个输入没有标准的回复段落。由于我们发现GPT-4大多能遵循输入约束,我们主要关注以两种方式评估段落的连贯性:使用GPT-4的零样本提示给每个任务输出一个1-10的标量分数,或者使用人类判断来比较不同方法的输出段落对。对于前者,我们对每个任务输出采样5个分数并平均,这5个分数通常一致,平均标准差约为0.56。对于后者,我们请部分作者进行盲审,在100个输入上比较CoT和ToT生成的段落对,其中段落顺序随机翻转。
基线方法。给定任务的创造性本质,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对段落中更青睐ToT而非CoT的41次(另21次青睐CoT,38次“同样连贯”)来确认这一发现。最后,迭代完善对这个自然语言任务更有效,其中从IO连贯性得分6.19完善到7.67,而从ToT的7.56完善到7.91。我们认为这可以被视作为ToT框架中的第三种思维生成方式,其中新的思维可以从完善旧思维中产生,而不是独立生成或顺序生成。
4.3 迷你填字游戏
在24点游戏和创意写作中,ToT相对较浅——最多只需要3个思维步骤就可以达到最终输出。在这里,我们探索5×5迷你填字游戏作为一个更难的搜索问题,其中涉及自然语言。同样,目标不是仅仅解决该任务,因为更通用的填字游戏可以通过专用的NLP流水线来轻松解决[31],它利用了大规模检索而不是LM。相反,我们的目的是探索LM作为一个通用问题求解器的极限,它探索自己的思维并用精心推理作为启发式来引导自己的探索。
任务设置。我们从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个中间步骤。对于思维生成,在每个状态,我们将所有现有思维(例如“h2.motor; h1.tasks”对于图6(a)中的状态)翻译成剩余提示的字母约束(例如“v1.To heap: tm ”),然后提示提议提示5次来提出在哪里以及填充下一个单词的候选项。重要的是,我们也提示LM为不同的思维给出一个置信等级,并在提议中聚合以获得按优先级排序的下一个思维列表(图6(a))。对状态评估,我们类似地将每个状态翻译成剩余提示的字母约束,然后评估对于每个提示填写是否可行。如果剩余的任何提示被判断为“不可能”填充(例如“v1. To heap: tm s ”),则该状态的子树探索会被修剪,DFS回溯到其父状态继续探索。我们限制DFS搜索步骤为100,并简单地渲染探索到的最深状态(若有多个取第一个)为最终输出。
结果。如表3所示,IO和CoT提示方法在该任务上表现很差,单词级成功率不到16%,而ToT显著改进了所有指标,实现了60%的单词级成功率,解决了4/20个游戏。这种改进并不令人惊讶,因为IO和CoT没有尝试不同提示、更改决策或回溯的机制。
五、相关工作
规划和决策制定。智能规划和决策制定对于实现预定义目标至关重要。由于它们在大量世界知识和人类示例上进行训练,已经被证明内化了丰富的常识,这使得LM能够在给定问题背景和环境状态的条件下提出合理的计划[10,39,34,11,32,38,37]。我们提出的思维树方法通过在每个问题解决步骤同时考虑多个潜在可行的计划来扩展现有的规划表述,并根据最有希望的方案继续推进。思维采样和价值反馈的整合为规划和决策制定机制提供了自然的集成,使基于LM的搜索树内有效。另一方面,传统决策制定过程通常需要专门训练奖励和策略模型,如强化学习(例如CHAI [30]),而我们使用LM本身来提供决策制定所需的价值估计。
自我反思。使用LLM来评估其自己预测的可行性正在成为问题求解中越来越重要的过程。[25,17,21]引入了“自我反思”机制,其中LLM对其生成候选提供反馈。[4]通过注入基于其代码执行结果的LM生成的反馈消息来提高LM代码生成的准确性。类似的,[14]也引入“批评”或审查步骤来对操作和状态进行审查,以决定在解决计算机操作任务时要采取的下一步行动。与我们的方法非常相关的还有最近的“自我评估引导解码”[36]。与我们的方法类似,自我评估解码也遵循一种树搜索过程,其叶节点从随机光束搜索解码中采样,然后由LLM本身用精心准备的自我评估提示进行评估。但是,他们的方法使用了PAL表述[7],这使其难以处理我们在本文中考虑的如创意写作等具有挑战性的任务。我们的思维树表述因此更通用,可以处理GPT-4甚至使用标准提示仅获得非常低准确率的具有挑战性的任务。
程序引导的LLM生成。我们的提议也与最近使用符号程序指导LM行为的进展相关。例如,[24]将LM嵌入算法搜索过程中以逐步帮助解决问题,如问答,其中搜索树通过可能提供答案的相关段落来扩展。但是,这种方法与我们的不同,因为它通过采样外部段落而不是LM自己的思维来扩展树,并且没有反思或投票步骤。另一种更进一步的方法LLM+P [15],将实际的规划过程委托给经典规划器。
经典搜索方法。最后但并非最不重要的一点,我们的方法可以看作是问题求解的经典搜索方法的现代诠释。例如,它可以被视为启发式搜索算法,如A* [8],其中每个搜索节点的启发式由LM的自我评估提供。从这个角度来看,我们的方法也与A*搜索启发的NeuroLogic A*式解码相关[16],其受A*搜索的启发但引入了LM进行高效前瞻的启发式来改进束搜索或top-k采样解码。但是,该方法仅局限于句子生成任务,而我们的框架被设计用于需要价值反馈指导的复杂多步问题求解。
六、讨论
局限性和未来方向。像ToT这样的精心搜索对于GPT-4已经擅长的许多现有任务可能并非必需,而作为初步尝试,本文仅探索了三个相对简单的任务,这些任务对GPT-4提出了挑战,需要更好的搜索和规划能力。然而,随着我们开始将LM部署到更多实际世界的决策制定应用中(例如编程、数据分析、机器人等),可能会出现更复杂的任务,为研究这些问题提供新的机遇。此外,像ToT这样的搜索方法需要比采样方法更多的资源(例如GPT-4 API成本)才能改进任务性能,但ToT的模块化灵活性允许用户自定义这样的性能-成本权衡,未来的开源工作[29]也应该很快减少这样的成本。最后,本文聚焦于使用预训练好的LM,而使用ToT风格的高级逆向决策制定(例如,审慎地权衡下一段的不同选择,而不是预测下一个词元)进行LM微调可能为增强LM的问题求解能力带来机遇。
更广泛的影响。ToT是一种框架,使LM能够更自主、更智能地做出决策和解决问题。虽然当前任务局限于推理和搜索问题,但未来涉及外部环境或人类交互的应用可能带来潜在危害,例如促进LM的有害用途。另一方面,ToT也提高了模型决策的可解释性和人类协调的机会,因为产生的表示是可读的高级语言推理,而不是隐式的低级词元价值。
结论。LM的联想“系统1”可以通过基于可能通往解决方案的路径进行搜索的“系统2”得以有益的增强。思维树框架提供了一种将经典洞察力转换为当代LM可行行动的方法。与此同时,LM也弥补了这些经典方法的不足,为难以正式化的复杂问题提供了解决方案,例如创意写作。我们认为LM与经典AI方法的这个交汇是未来工作的一个激动人心的方向。
七、主要创新点
1. 提出“思维树”(Tree of Thoughts)框架,将问题求解过程形式化为在思维组成的树结构上搜索
2. 将思维定义为表达推理步骤的语言序列,思维的粒度根据不同问题进行设计
3. 提出使用语言模型生成和评估多种可选思维,进行有方向的树搜索
4. 思维生成提示和思维评估提示都直接由语言模型完成,实现了基于语言的启发式搜索
5. 整合不同的树搜索算法如BFS和DFS到框架中,可根据问题 adapts
6. 在数学推理、创意写作和填字游戏等任务上验证了框架的有效性
7. 不需要额外训练,仅利用预训练语言模型的知识完成精心搜索
8. 提出了当前语言模型简单的逐词生成可能存在的局限性
9. 探讨了如何使语言模型向更全局的规划与搜索方向发展,模拟人类解决问题的思维
10. 提出思维树框架具有通用性、模块化和方便扩展性等优点
总之,思维树框架开创性地融合了经典搜索方法与大型语言模型,使其可以超越当前的生成限制,完成更具启发和探索性的复杂推理与规划。这为语言模型的发展指出了新的思路。
八、不足之处
1. 论文中的实验任务相对简单,不能充分验证框架在复杂真实世界问题上的效果
2. 思维的适当粒度需要根据具体问题来设计,无法给出通用的设计原则
3. 思维生成和评估完全依赖语言模型质量,存在可能给出低质量思维的风险
4. 搜索算法简单,更复杂的搜索算法如A*、MCTS等未充分利用
5. 思维树的搜索代价较大,实际应用中计算资源 may be a bottleneck
6. 缺乏定量分析不同模块选择对性能的影响
7. 尚未探索在框架下微调语言模型的效果
8. 人类验证结果样本较少,尚需扩大验证
9. 缺乏分析框架本身的局限性,可能的负面影响等
10. 实际应用中如何解决搜索空间过大问题未讨论
总体来说,论文作为一篇探索性的工作提出了思维树框架的设想和初步验证,但框架本身作为通用问题求解器的效果与影响还需要进一步探究。如何改进和扩展框架是值得进一步研究的问题。