Tree of Thoughts: Deliberate Problem Solving with Large Language Models
- 发表版本
- 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 把人解决问题描述成在一棵树上搜索:每个节点是一个部分解,每条分支是一种可能的下一步,靠启发式规则决定往哪里走,走不通就退回来。这篇让语言模型也这样做。
定义问题
作者把当时的做法统一写成几种形式。输入 ,输出 ,语言模型是 :
- 输入输出提示(IO):直接生成答案,。
- 思维链(CoT):在输入和输出之间插入一串想法 ,每个想法是一段有意义的文字,例如一行算式。实际上整串是一口气写出来的。
- 思维链加 Self-Consistency(CoT-SC):独立采样 条思维链,选出现次数最多的答案。
从「在树上搜索」的角度看,这些做法缺了两样东西。局部上,不会在同一步探索不同的写法;全局上,没有任何规划、前瞻或回溯。
解决问题

Tree of Thoughts(ToT)把问题看成在一棵树上搜索。每个节点是一个状态 ,也就是输入加上到目前为止的想法。要把它用在某个问题上,得回答四个问题。
一、想法要切多大
想法要够小,模型才能生成多样、有希望的候选;也要够大,模型才能判断它有没有前途。一个 token 太小,无从评估;一整本书太大,写不出连贯的东西。
问题不同,作者的切法也不同:24 点游戏里,一个想法是一行算式;创意写作里,是一段写作大纲;填字游戏里,是为某条线索填进的一个单词。
二、怎么生成下一个想法
- 独立采样:用思维链的提示词,独立采样 次。适合想法空间很大的情况,例如一整段大纲,各自采样自然就有多样性。
- 一次提出:用一个「提议提示词」,让模型在同一次输出里列出 个候选。适合想法空间很受限的情况,例如一行算式或一个单词,放在同一段里列出来可以避免重复。
三、怎么评估状态
这是 ToT 和一般搜索算法最不同的地方。传统搜索的启发式不是写死的规则(例如 Deep Blue),就是训练出来的模型(例如 AlphaGo)。ToT 用第三种方式,让语言模型自己用文字推理,判断一个状态有没有前途。
- 单独打分:对每个状态,请模型给一个分数,或分成「一定可以 / 可能 / 不可能」。判断的依据可以是往前试几步,例如 5、5、14 很快就能凑出 5 + 5 + 14 = 24;也可以是常识,例如 1、2、3 太小,怎么算都到不了 24。
- 相互比较:当成败很难直接打分,例如一段文字是否连贯,就把几个候选放在一起,请模型投票选出最有希望的那个。这有点像在每一步做一次 Self-Consistency。
评估不必完美,只要大致上能帮助决策就好。也可以多问几次取平均,用成本换取更可靠的判断。
四、用什么搜索
- 广度优先(BFS):每一步只保留最有希望的 个状态。用在树不深(最多 3 步)的 24 点和创意写作。
- 深度优先(DFS):先往最有希望的方向一路走到底;如果评估认为从这个状态不可能解出来,就剪掉整棵子树,退回上一层换下一个候选。用在要填 10 个单词的填字游戏。
从这个角度看,IO、CoT、CoT-SC 都是 ToT 的特例,只是树的深度和宽度受到限制。整个框架不需要任何训练,现成的语言模型就能用。
讨论
三个实验都用 GPT-4 的对话模式,温度 0.7,在 2023 年 5 月 5 日到 16 日之间跑完。三个任务都是作者特意挑的,即使是 GPT-4,用 IO 或 CoT 也做不好。
24 点

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() | 45% |
| ToT() | 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。

右图最值得看。大约六成的 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 评分 |
|---|---|
| IO | 6.19 |
| CoT(先写大纲再写文章) | 6.93 |
| ToT | 7.56 |
| IO + 反复修正 | 7.67 |
| ToT + 反复修正 | 7.91 |
整理自原论文第 4.2 节;分数是 100 题的平均。
人工比较的结果一致,100 组里有 41 组认为 ToT 比较连贯,21 组认为 CoT 比较好,其余 38 组差不多。在这个任务上,反复修正很有效,作者把它看成生成想法的第三种方式:从旧的想法修改出新的想法。
迷你填字游戏

前两个任务的树都很浅,最多 3 步。填字游戏要填 10 个单词(5 横 5 竖),而且相互牵制,是比较难的搜索问题。作者从 GooBix 抓了 156 题,取 20 题测试。
这里用深度优先搜索。每个状态把已经填好的单词转成剩下线索的字母限制,请模型提出 5 次候选,并为每个候选给出置信度,汇总成优先顺序。评估时逐一检查剩下的每条线索,只要有一条被判为不可能填,就剪掉整棵子树、退回上一层。最多走 100 步,最后输出走得最深的那个状态。
| 方法 | 字母 | 单词 | 整题 |
|---|---|---|---|
| IO | 38.7 | 14 | 0 |
| CoT | 40.6 | 15.6 | 1 |
| ToT | 78 | 60 | 20 |
| ToT,输出最好的状态 | 82.4 | 67.5 | 35 |
| ToT,不剪枝 | 65.4 | 41.5 | 5 |
| ToT,不回溯 | 54.6 | 20 | 5 |
整理自原论文 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 个解答,投票选一个。
| 方法 | GSM8K | StrategyQA |
|---|---|---|
| IO | 51 | 73 |
| CoT | 86 | 82 |
| ToT | 90 | 83 |
整理自原论文 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」,正确的答案就被剪掉了。
一年多后,推理模型把这棵树压平了。模型在一条长长的思维链里自己停下来说「等一下,这样不对」,然后回到前面重想;分支、评估、回溯都还在,只是不再需要外面那套搜索程序来管。