返回论文笔记资料库
arXiv 2023NeurIPS 2023语言模型与 Transformer论文笔记

Tree of Thoughts

此路不通

原始论文

Tree of Thoughts: Deliberate Problem Solving with Large Language Models

论文作者

Shunyu Yao · Dian Yu · Jeffrey Zhao …

查看全部 7 位作者

Shunyu Yao · Dian Yu · Jeffrey Zhao · Izhak Shafran · Thomas L. Griffiths · Yuan Cao · Karthik Narasimhan

发表版本
NeurIPS 2023会议
arXiv 首次提交
arXiv:2305.10601
引用此论文 · BibTeX

引用信息对应所链接的论文版本,作者为原论文作者。

@misc{transformerstreeofthoughts2023,
  title = {{Tree of Thoughts: Deliberate Problem Solving with Large Language Models}},
  author = {Shunyu Yao and Dian Yu and Jeffrey Zhao and Izhak Shafran and Thomas L. Griffiths and Yuan Cao and Karthik Narasimhan},
  year = {2023},
  eprint = {2305.10601},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2305.10601}
}
本页内容

语言模型生成文字的方式,从 GPT 到 GPT-4 都没变过:从左到右,一个 token 接一个 token,写下去就不能回头。

思维链让模型先写推理步骤,但仍然是一条路走到底;Self-Consistency 多走几条,最后投票,可是每一条也都是一口气写完,中途不会停下来比较「这一步这样走好,还是那样走好」。如果第一步就走错,后面写得再漂亮也没用。

Princeton 的 Yao 等人和 Google DeepMind 合作,从人工智能最早的研究里找灵感。1950 年代,Newell 和 Simon 把人解决问题描述成在一棵树上搜索:每个节点是一个部分解,每条分支是一种可能的下一步,靠启发式规则决定往哪里走,走不通就退回来。这篇让语言模型也这样做。

定义问题

作者把当时的做法统一写成几种形式。输入 xx,输出 yy,语言模型是 pθp_\theta:

  • 输入输出提示(IO):直接生成答案,y∼pθ(y∣x)y \sim p_\theta(y \mid x)。
  • 思维链(CoT):在输入和输出之间插入一串想法 z1,…,znz_1, \ldots, z_n,每个想法是一段有意义的文字,例如一行算式。实际上整串是一口气写出来的。
  • 思维链加 Self-Consistency(CoT-SC):独立采样 kk 条思维链,选出现次数最多的答案。

从「在树上搜索」的角度看,这些做法缺了两样东西。局部上,不会在同一步探索不同的写法;全局上,没有任何规划、前瞻或回溯。

解决问题

原论文 Figure 1:四种用语言模型解题的方式,每个方框是一个想法。(a) 输入输出提示,从输入直接到输出。(b) 思维链,一条直线上的一串想法。(c) Self-Consistency,好几条独立的思维链,最后多数投票。(d) Tree of Thoughts,从输入展开成一棵树,每一层有好几个候选想法,绿色深浅表示评估的好坏,红色是被放弃的分支,沿着评估最好的路径走到输出。
原论文 Figure 1(Yao 等人),取自 PDF 第 2 页,CC BY 4.0。

Tree of Thoughts(ToT)把问题看成在一棵树上搜索。每个节点是一个状态 s=[x,z1,…,zi]s = [x, z_1, \ldots, z_i],也就是输入加上到目前为止的想法。要把它用在某个问题上,得回答四个问题。

一、想法要切多大

想法要够小,模型才能生成多样、有希望的候选;也要够大,模型才能判断它有没有前途。一个 token 太小,无从评估;一整本书太大,写不出连贯的东西。

问题不同,作者的切法也不同:24 点游戏里,一个想法是一行算式;创意写作里,是一段写作大纲;填字游戏里,是为某条线索填进的一个单词。

二、怎么生成下一个想法

  • 独立采样:用思维链的提示词,独立采样 kk 次。适合想法空间很大的情况,例如一整段大纲,各自采样自然就有多样性。
  • 一次提出:用一个「提议提示词」,让模型在同一次输出里列出 kk 个候选。适合想法空间很受限的情况,例如一行算式或一个单词,放在同一段里列出来可以避免重复。

三、怎么评估状态

这是 ToT 和一般搜索算法最不同的地方。传统搜索的启发式不是写死的规则(例如 Deep Blue),就是训练出来的模型(例如 AlphaGo)。ToT 用第三种方式,让语言模型自己用文字推理,判断一个状态有没有前途。

  • 单独打分:对每个状态,请模型给一个分数,或分成「一定可以 / 可能 / 不可能」。判断的依据可以是往前试几步,例如 5、5、14 很快就能凑出 5 + 5 + 14 = 24;也可以是常识,例如 1、2、3 太小,怎么算都到不了 24。
  • 相互比较:当成败很难直接打分,例如一段文字是否连贯,就把几个候选放在一起,请模型投票选出最有希望的那个。这有点像在每一步做一次 Self-Consistency。

评估不必完美,只要大致上能帮助决策就好。也可以多问几次取平均,用成本换取更可靠的判断。

四、用什么搜索

  • 广度优先(BFS):每一步只保留最有希望的 bb 个状态。用在树不深(最多 3 步)的 24 点和创意写作。
  • 深度优先(DFS):先往最有希望的方向一路走到底;如果评估认为从这个状态不可能解出来,就剪掉整棵子树,退回上一层换下一个候选。用在要填 10 个单词的填字游戏。

从这个角度看,IO、CoT、CoT-SC 都是 ToT 的特例,只是树的深度和宽度受到限制。整个框架不需要任何训练,现成的语言模型就能用。

讨论

三个实验都用 GPT-4 的对话模式,温度 0.7,在 2023 年 5 月 5 日到 16 日之间跑完。三个任务都是作者特意挑的,即使是 GPT-4,用 IO 或 CoT 也做不好。

24 点

原论文 Figure 2:ToT 解 24 点。左边是一棵搜索树,绿色是保留的候选,红色是被剪掉的。输入 4 9 10 13,第一层候选包括 10 − 4 = 6(剩 6 9 13)、4 + 9 = 13(剩 10 13 13)等;接着是 13 − 6 = 7、13 − 9 = 4 等,最后 4 × 6 = 24。右边上方是提议提示词:给出剩下的数字,模型列出可能的下一步,例如 4 + 9 = 13 (left: 10 13 13)、10 − 4 = 6 (left: 6 9 13)。右边下方是评估提示词:问剩下的数字能不能凑出 24,模型会试算,例如 10 14 可以算出 10 + 14 = 24,判为 sure;10 13 13 试了几种都太大,判为 impossible。
原论文 Figure 2(Yao 等人),取自 PDF 第 5 页,CC BY 4.0。

24 点是用四个数字和加减乘除凑出 24。作者从 4nums.com 抓了 1,362 题,网站按人类解题时间由易到难排序,测试用的是第 901 到 1,000 题这 100 道比较难的题。

用 ToT 解,很自然地分成 3 步,每步一行算式。每个节点把剩下的数字交给提议提示词,列出可能的下一步;每个候选再交给评估提示词,判断 sure、maybe 或 impossible,各问 3 次。广度优先搜索,每步保留最好的 5 个。

方法成功率
IO 提示7.3%
CoT 提示4.0%
CoT-SC(100 次多数投票)9.0%
ToT(b=1b = 1)45%
ToT(b=5b = 5)74%
IO + 反复修正(最多 10 轮)27%
IO(100 次取最好)33%
CoT(100 次取最好)49%

整理自原论文 Table 2。

CoT 只有 4.0%,比直接作答还低;投票也只到 9.0%。ToT 只保留 1 个候选就到 45%,保留 5 个到 74%。

表格下半部分是几种比较宽松的对照。「反复修正」每次答错就请模型反思再试,但用了算式对不对的标准答案作为反馈。「100 次取最好」只要 100 次里有一次对就算成功,实际使用时不可能知道哪一次对,算是上限。即使是这样的上限,CoT 也只有 49%,仍然低于 ToT。

原论文 Figure 3:(a) 成功率与每题访问节点数的关系。IO 和 CoT 取 k 次中最好的那次,曲线缓慢上升,CoT 到 100 次约 0.49;ToT 的 b 从 1 到 5,访问的节点数少于 100,成功率却高得多,约 0.45 到 0.74。(b) 各方法的样本在第几步失败。CoT 约六成在第 1 步就已经失败,约三成在第 2 步;ToT(b = 5)大多走到最后并且正确。
原论文 Figure 3(Yao 等人),取自 PDF 第 6 页,CC BY 4.0。

右图最值得看。大约六成的 CoT 样本在写完第一步,也就是前三个词(例如「4 + 9」)的时候,就已经注定凑不出 24 了。

第一步为什么这么关键?以 4 9 10 13 为例,挑两个数做一次四则运算,第一步共有 36 种走法,其中只有 7 种还凑得出 24,例如 10 − 4、9 + 10 和 13 − 9。随便选一步,八成就走进了死路。从左到右写下去的 CoT 没办法回头,第一步错了就满盘皆输。

不做任何判断、单纯深度优先地一路试下去,走到底凑不出来就退回上一层,也找得到答案,例如 4 − 10 = −6、9 − 13 = −4、(−6) × (−4) = 24,只是要走过上千个状态。程序可以暴力穷举,语言模型每走一步都要花一次 API 调用,走不起。ToT 的评估提示词扮演的就是剪枝的角色,先把「10 13 13 怎么算都太大」这种状态剪掉,只在少数有希望的分支上展开。

代价还是很可观。ToT 解一题 24 点平均要生成 5,500 个 token,接近采样 100 次 CoT 的 6,700 个;每题成本约 0.74 美元,CoT 采样 100 次约 0.47 美元。花差不多的 token,ToT 的成功率是 74%,CoT 取 100 次最好的是 49%。

作者也用 GPT-3.5 试过,ToT 只有 19%。交叉测试里,GPT-4 生成想法、GPT-3.5 评估,是 64%;GPT-3.5 生成、GPT-4 评估,只有 31%。这个游戏的瓶颈在生成好的候选,而不是评估。

创意写作

给 4 个随机句子,要写出 4 段文字,每段分别以这 4 句结尾。这个任务没有标准答案,作者用两种方式评估连贯性:请 GPT-4 打 1 到 10 分,取 5 次平均;以及由部分作者在不知道哪篇是谁写的情况下,两两比较 CoT 和 ToT 的文章。

ToT 只有两层:先生成 5 份写作大纲,投票 5 次选出最好的一份;再按这份大纲写 5 篇文章,同样投票选出一篇。

方法GPT-4 评分
IO6.19
CoT(先写大纲再写文章)6.93
ToT7.56
IO + 反复修正7.67
ToT + 反复修正7.91

整理自原论文第 4.2 节;分数是 100 题的平均。

人工比较的结果一致,100 组里有 41 组认为 ToT 比较连贯,21 组认为 CoT 比较好,其余 38 组差不多。在这个任务上,反复修正很有效,作者把它看成生成想法的第三种方式:从旧的想法修改出新的想法。

迷你填字游戏

原论文 Figure 6:ToT 解 5 × 5 填字游戏。(a) 从当前的盘面(已填 h1.tasks、h2.motor),模型提出好几组候选并附上置信度,例如 h4.salon(sure)、v5.srdry(low)、v3.string(high),汇总成一个优先顺序;深度优先依次尝试 h4.salon、h3.grand、v3.string。(b) 每个状态交给评估器,逐一检查剩下的每条线索能不能填:v3 Pretentious; flowery 可以填(sure),v1 To heap 在字母限制下不可能填(impossible),v5 Desiccator; more dry 也许可以(maybe)。只要有一条线索被判为不可能,整棵子树就被剪掉,退回上一层。
原论文 Figure 6(Yao 等人),取自 PDF 第 8 页,CC BY 4.0。

前两个任务的树都很浅,最多 3 步。填字游戏要填 10 个单词(5 横 5 竖),而且相互牵制,是比较难的搜索问题。作者从 GooBix 抓了 156 题,取 20 题测试。

这里用深度优先搜索。每个状态把已经填好的单词转成剩下线索的字母限制,请模型提出 5 次候选,并为每个候选给出置信度,汇总成优先顺序。评估时逐一检查剩下的每条线索,只要有一条被判为不可能填,就剪掉整棵子树、退回上一层。最多走 100 步,最后输出走得最深的那个状态。

方法字母单词整题
IO38.7140
CoT40.615.61
ToT786020
ToT,输出最好的状态82.467.535
ToT,不剪枝65.441.55
ToT,不回溯54.6205

整理自原论文 Table 3;单位为 %,整题是 20 题里完全解出的比例。

IO 和 CoT 的单词正确率都不到 16%,ToT 到 60%,20 题里完全解出 4 题。

后面三行是消融。如果每题直接输出搜索过程中最好的状态(这需要知道答案,算是上限),可以解出 7 题,说明「输出最深的状态」这个规则还有改进空间。

剪枝也会出错。5 × 5 的填字游戏为了凑格子,会用到一些罕见或过时的单词,例如「agend」是「agendum」的旧写法,GPT-4 却认为那是「agenda」的拼写错误,把正确的盘面剪掉了。拿掉剪枝之后整体分数下降,但有 4 题在搜索过程中找到过正确的盘面,其中 3 题是有剪枝的 ToT 在 100 步内解不出来的。评估器的好坏,直接决定了搜索能走多远。

拿掉回溯,改成每次都填最有希望的那个单词、最多 20 步、可以覆写,单词正确率只剩 20%。

简单的题目用不上

附录把零样本的 ToT 用在一般的题目上:先生成 5 种解题策略,投票选一种,再按策略写 5 个解答,投票选一个。

方法GSM8KStrategyQA
IO5173
CoT8682
ToT9083

整理自原论文 Table 4;GPT-4,各 100 题,单位为 %。

ToT 还是比 CoT 好,但幅度很小。GPT-4 加 CoT 在这些题目上已经很强;StrategyQA 的瓶颈是外部知识,而不是推理。作者的建议是,传统的 NLP 任务可以试试小模型加 ToT,GPT-4 加 ToT 留给连 GPT-4 加 CoT 都做不好的难题。

限制

作者在讨论里提了几点:

  • 很多任务不需要:GPT-4 已经擅长的任务,用不着这么费力的搜索;这篇也只探索了三个相对简单、但 GPT-4 做不好的任务。
  • 成本:随提示词和搜索方式不同,ToT 生成的 token 是 CoT 的 5 到 100 倍。三个任务的主要实验中,24 点和创意写作合计约 106 美元,填字游戏估计也在 100 美元以内。
  • 只用现成的模型:作者提到,未来可以用类似 ToT 的方式微调模型,让它学会在「下一段该怎么写」这种层级上做决策,而不只是预测下一个 token。

另外值得一提的是,ToT 的每个任务都要人自己设计:想法怎么切、提议和评估的提示词怎么写、用哪一种搜索。换一个问题,这些都要重新想一遍。

后来的事

作者在结尾提的方向,后来由推理模型实现了,只是走的不是 ToT 这条路。

DeepSeek-R1 的论文里,有一段「失败的尝试」。团队试过用蒙特卡洛树搜索(MCTS)在推理时探索,把答案切成小段,用一个价值模型引导搜索,但遇到两个问题:token 生成的搜索空间比棋类大太多,就算限制每个节点的扩展数,也容易卡在局部最优;训练一个足够精细的价值模型本身就很难。最后成功的,是用答案对错当奖励的强化学习,让模型在同一条很长的思维链里,自己学会检查、怀疑、回头重想。

推理时的搜索并没有消失。在什么情况下该用搜索、什么情况下该让模型自己修改答案、算力怎么分配最划算,后来有人做了系统性的比较。

结论

ToT 把经典人工智能的树搜索接到语言模型上,让模型同时负责提出候选和评估好坏。GPT-4 玩 24 点,CoT 只有 4%,ToT 到 74%;填字游戏的单词正确率从 15.6% 到 60%。

它也把这类方法的代价讲得很清楚。每个问题都要人设计想法的切法、提议和评估的提示词、搜索的方式;token 是 CoT 的好几倍到上百倍;评估器一旦看错,像那个被当成拼写错误的「agend」,正确的答案就被剪掉了。

一年多后,推理模型把这棵树压平了。模型在一条长长的思维链里自己停下来说「等一下,这样不对」,然后回到前面重想;分支、评估、回溯都还在,只是不再需要外面那套搜索程序来管。