提纲
1 简介
2 背景
3 Tree of Thoughts
3.1 Thought decomposition
3.2 Thought generator
3.3 State evaluator
3.4 Search algorithm
4 总结
参考文献
1 简介
**目前语言模型被应用到越来越广泛的任务当中，但是受限于从左往右的基于token级别的生成能力，在需要探索，策略性预测或者初始决策非常关键的任务中依旧表现不佳。** 基于这些挑战，普林斯顿大学提出了一种新的语言模型推理框架， **Tree of Thoughts（TOT），它允许语言模型在解决问题的中间过程进行探索，通过考虑多种不同推理路径并进行评估，同时具备向前看跟向后回溯的能力以获得更佳决策选择。**
2 背景
目前大模型解决问题的方式有以下几种，记语言模型为p，输入为x，模版为prompt，模型输出为y。（文中的很多内容看似简单易懂，但是如果仔细思考的话，关于实现方式还是有较多学问的，为了更好的理解，后面会引入部分基于24点游戏的具体实现样例。）
Input-Output(IO) prompting
最常见的方式，直接将输入input跟prompt作为语言模型的输入， **这里的prompt可以是相关任务指令或者few-shot所需要的input-output完整样例，让语言模型直接成结果y** 。即y~p(y|prompt(x))。具体prompt样例如下，这是一个24点游戏相关的prompt，prompt里包括具体任务指令跟若干个完整样例，将最后一行的{x}替换成新的input(4个整数)就可以作为模型的输入，模型就会预测出对应的游戏结果，这种方式就是In-context learning。
'''
Use numbers and basic arithmetic operations (+ - * /) to obtain 24.
Input: 4 4 6 8
Answer: (4 + 8) * (6 - 4) = 24
Input: 2 9 10 12
Answer: 2 * 12 * (10 - 9) = 24
Input: 4 9 10 13
Answer: (13 - 9) * (10 - 4) = 24
Input: 1 4 8 8
Answer: (8 / 4 + 1) * 8 = 24
Input: 5 5 5 9
Answer: 5 + 5 + 5 + 9 = 24
Input: {x}
'''
Chain-of-thought(CoT) prompting
之前写过很多文章介绍的思维链， **很多需要复杂推理的任务语言模型很难一步到位生成答案，思维链就是让语言模型逐步推理，通过依次生成多个中间步骤z1,z2,…,zn（这些中间过程称为thoughts），前面的生成结果会作为后续的模型输入，直到得到最终结果y。** 类似于人类做数学题，需要步步递进的解题过程，才能得到最终答案。即[z1,z2,…zn,y]~p(z1,z2…,zn,y|x)。同样是24点游戏这个场景，CoT所使用的prompt会在任务指令说明需要逐步推理的要求，具体的样例中也需要补充中间步骤，也就是steps部分内容。
'''
Use numbers and basic arithmetic operations (+ - * /) to obtain 24. Each step, you are only allowed to choose two of the remaining numbers to obtain a new number.
Input: 4 4 6 8
Steps:
4 + 8 = 12 (left: 4 6 12)
6 - 4 = 2 (left: 2 12)
2 * 12 = 24 (left: 24)
Answer: (6 - 4) * (4 + 8) = 24
Input: 2 9 10 12
Steps:
12 * 2 = 24 (left: 9 10 24)
10 - 9 = 1 (left: 1 24)
24 * 1 = 24 (left: 24)
Answer: (12 * 2) * (10 - 9) = 24
Input: 4 9 10 13
Steps:
13 - 10 = 3 (left: 3 4 9)
9 - 3 = 6 (left: 4 6)
4 * 6 = 24 (left: 24)
Answer: 4 * (9 - (13 - 10)) = 24
Input: 1 4 8 8
Steps:
8 / 4 = 2 (left: 1 2 8)
1 + 2 = 3 (left: 3 8)
3 * 8 = 24 (left: 24)
Answer: (1 + 8 / 4) * 8 = 24
Input: 5 5 5 9
Steps:
5 + 5 = 10 (left: 5 9 10)
10 + 5 = 15 (left: 9 15)
15 + 9 = 24 (left: 24)
Answer: ((5 + 5) + 5) + 9 = 24
Input: {x}
'''
Self-consistency with CoT(CoT-SC)
**CoT的集成方案，通过多次采样的方式获得多个CoT的结果，最终返回预测最多次的y。** 对于同一个问题，通常会有不同的思考过程，通过探索更多可能的解决问题路径，让最终决策更佳具有说服力。
图1: 语言模型解决问题的不同方式
目前这几种利用语言模型解决问题的方法都有明显缺陷，
a) 对于局部，没有探索一个思考过程下的不同延续-树的分支。
b)
对于全局，没有利用任何类型的规划，前瞻以及回溯去帮助评估不同抉择-而启发式的探索正式人类解决问题的特性。
3 Tree of Thoughts
于是Tree of Thoughts作为一种新的范式被提出，它使得语言模型可以去探索多个推理路径。把 **解决问题视作在一棵树上的搜索，树上的每个节点代表当前的状态s=[x,z1,…,zi]，状态包括原始的问题以及到目前为止的思考过程。一个完整的Tree of Thoughts包括以下4个过程。**
3.1 Thought deconposition
如何将推理中间过程分解成多个想法步骤 。不同于CoT会在没有明确分解的情况下连续对thoughts采样，ToT会根据问题属性去设计和分解中间的想法过程。 每个想法应该足够小，使得语言模型可以生成有潜力跟多样的样本 （生成一本书就太长了，很难保证连贯性），同时又应该足够大， 使得语言模型可以评估该想法解决问题的潜力 （只生成一个token就太小，很难去评估对于解决问题的帮助）。
例如对于Crosswords字谜游戏而言，一个想法可以是几个单词，对于24点游戏而言，一个想法可以是一行等式，对于创作而言，一个想法可以是一个章节的写作规划。看起来很高大上，其实具体实现就是prompt engineering，要根据具体任务写好prompt，在prompt里写清楚推理过程每个想法的粒度，让语言模型按照prompt内容逐步推理，依次生成中间想法。例如前面CoT prompt里第一个样例中的4 + 8 = 12 (left: 4 6 12)就是一个最基础的想法。
3.2 Thought generator
**如何根据当前状态生成候选想法** 。文中提供了两个想法生成策略，
a) Sample 利用CoT多次采样，这种方式能保证多样性，在想法空间更宽泛是效果更佳（例如每个想法是一个段落），即
Z(i+1)~p(z(i+1)|s) (j=1,…,k)。
b)Propose 依据propose prompt依次生成想法，可以避免同一个上下文生成重复的想法，更适用于思维空间受限的场景（例如每个想法是只是一个单词或者一行），即
[z1,…,zk]~p(z1,…zk|s)。 还是以24点游戏为例，采用propose的方式的prompt如下所示，prompt里给定的样例里的输出结果包括多个下一阶段的想法，将这样的prompt内容+x喂给语言模型，希望语言模型能按照样例生成多个下一阶段的想法。
'''
Input: 2 8 8 14
Possible next steps:
2 + 8 = 10 (left: 8 10 14)
8 / 2 = 4 (left: 4 8 14)
14 + 2 = 16 (left: 8 8 16)
2 * 8 = 16 (left: 8 14 16)
8 - 2 = 6 (left: 6 8 14)
14 - 8 = 6 (left: 2 6 8)
14 / 2 = 7 (left: 7 8 8)
14 - 2 = 12 (left: 8 8 12)
Input: {x}
Possible next steps:
'''
3.3 State evaluator
如何评估状态。 **给定不同状态的前沿，让状态评估器评估它们对于解决问题的帮助，以确定哪些状态值得继续探索，以及以何种方式探索** 。文中也提供了两种评估策略。
a)给状态赋值，给定当前状态，生成对应的分数，或者视作一个分别任务，预测一个对应的分类标签（sure/likely/impossible），从而转化为特定的分数。这样的评估方式不需要非常准确率，只要能近似预估即可。具体样例如下所示，给定包括评估任务指令跟对应的评估完整样例作为prompt，加上当前输入x作为语言模型输入，让语言模型由此给当前输入x打分，判断是否值得继续探索。
'''
Evaluate if given numbers can reach 24 (sure/likely/impossible)
10 14
10 + 14 = 24
sure
11 12
11 + 12 = 23
12 - 11 = 1
11 * 12 = 132
11 / 12 = 0.91
impossible
4 4 10
4 + 4 + 10 = 8 + 10 = 18
4 * 10 - 4 = 40 - 4 = 36
(10 - 4) * 4 = 6 * 4 = 24
sure
4 9 11
9 + 11 + 4 = 20 + 4 = 24
sure
5 7 8
5 + 7 + 8 = 12 + 8 = 20
(8 - 5) * 7 = 3 * 7 = 21
I cannot obtain 24 now, but numbers are within a reasonable range
likely
5 6 6
5 + 6 + 6 = 17
(6 - 5) * 6 = 1 * 6 = 6
I cannot obtain 24 now, but numbers are within a reasonable range
likely
10 10 11
10 + 10 + 11 = 31
(11 - 10) * 10 = 10
10 10 10 are all too big
impossible
1 3 3
1 * 3 * 3 = 9
(1 + 3) * 3 = 12
1 3 3 are all too small
impossible
{x}
'''
b)
跨状态投票，利用vote prompt从多个状态中选出最优的一个。例如可以将多个状态拼接到一起，让语言模型从中选择最优的一个状态。
图2: 创意写作任务中的跨状态投票示例
3.4 Search algorithm
Tree of Thought支持插入多种依赖于树的搜索算法，文章探索了其中两种相对简单的搜索算法。
a)
BFS，广度优先算法，每一步中保留最优潜力的K个状态。
b)
DFS，深度优先算法，优先探索最优潜力的状态，直到得到最终结果（解决了问题），或者超过当前状态被评估不可能解决问题就停止，如果是后者的话可以退回父节点，继续进行探索。
图3: 两种探索算法流程图
作为一种利用语言模型解决通用问题的方法，ToT有几个优势，
a)
通用性，前面提及的IO，CoT, CoT-SC都可以视作ToT的特殊形式。
b)
模块化，四个模块跟语言模型都是互相独立的。
c)
灵活性， 可以适应不同问题特性，语言模型能力以及资源限制。
d)
便利性，不需要额外的训练。
文中在24点游戏，创意写作跟5*5字谜游戏三个 任务上做了实验，ToT的效果远超以前的方法。以 24点游戏为例，以前的方法的成功率不超过10%，而ToT的成功率则可以达到74%。通过错误分析可以发现接近60%的CoT在生成第一个中间步骤就出错了，从而导致任务失败。
图4: 24点游戏的实验结果
4 总结
**人类在进行复杂问题的决策时，往往会采用树状的思维方式去规划。对于那些目前语言模型已经处理地比较好的场景，就没有必要使用ToT了。ToT为复杂推理问题提供了一种新的解决方案，虽然用户可以灵活调整其中的模块，但是往往需要更多的资源（例如更多次数的模型调用）才能提升某个任务下的表现。虽然目前这种方式没涉及模型训练，但是利用ToT的相关任务来微调语言模型可以进一步提升语言模型解决问题的能力，例如将模型训练中预测下一个token的任务改成考虑下一个段落的选择。**
看似这个工作想法很直观，但是仔细思考后觉得这更像一个Plan+prompt engineering的工作，需要设计好任务所需要的模块，然后按照特定任务需求去构建合适的prompt，从而去引导模型按要求推理。ToT对于模型的要求非常高，只有强大的语言模型才能有这种设计，各个模块都依赖于语言模型，但凡哪个环节里模型没按要求执行都会导致任务失败，这也应该是文中选择了GPT4的原因（在github也有人反馈过使用GPT3.5效果会差很多，即便ToT相比其他方法依旧有优势） 。换言之，这不就是一个低阶版的autoGPT，不仅需要为自己任务定制特定的prompt，也需要设置好解决问题的策略，然后就坐等模型自己去寻找解决方案。ToT确实很符合目前的想象，即便是需要复杂推理的任务，只要借助于强大的语言模型，为自己任务设计好完整的处理流程，并定制相应的prompt，然后安静等待模型的处理结果即可。
Tree of Thoughts算是语言模型跟数据结构中树一个结合，这里需要的是基于树的搜索能力，除了树之外，其他具有这种能力的数据结构 ，是不是也都能跟语言模型擦出火花呢？只有语言模型足够强大，很多想法都是可以尝试的。但是问题在于，对于大部分人而言，如果没有GPT4那般强大的模型，能做的事情又有多少呢？
参考文献
1 Tree of Thoughts: Deliberate Problem Solving with Large Language Models