Tree of Thoughts: Deliberate Problem Solving with Large Language Models

Abstract

1. Introduction

最开始，人们设计 LM 只是为了生成文本，

2. Background

使用 $p_{\theta }$ 表示一个带参数 $\theta$ 的预训练语言模型，用小写字母 $x,y,z,s,\dots$ 表示一个语言序列，比如 $x=(x[1],\dots ,x[n])$，其中每个 $x[i]$ 是一个 token，因此

$$p_{\theta }(x)=\prod _{i=1}^n{p}_{\theta }(x[i]\mid x[1\dots i]).$$

我们使用大写字母 $S,\dots$ 表示一组语言序列。过往的方法主要分为下面三种：

• Input-output (IO) Prompting：使用语言模型将问题输入 $x$ 映射为输出 $y$ 的最常见方式：$y\sim p_{\theta }(y\mid {\text{prompt}}_{\text{IO}}(x))$，其中 ${\text{prompt}}_{\text{IO}}(x)$ 会把输入 $x$ 包装上任务说明以及/或者少量的/Few-shot 输入–输出示例。为简单起见，我们记

  $$p_{\theta }^{\text{prompt}}(\text{output}\mid \text{input})=p_{\theta }(\text{output}\mid \text{prompt}(\text{input}))$$

  这样 IO 提示可以形式化为 $y\sim p_{\theta }^{\text{IO}}(y\mid x)$。

• Chain-of-thought (CoT) Prompting：主要是为了解决那些输入 $x$ 到输出 $y$ 的映射并不直接的情况。主要想法是在输入 $x$ 和输出 $y$ 之间引入一条思维链 $z_1,\dots ,z_n$，其中每个 $z_i$ 都是一个连贯的语言序列，作为问题求解过程中的有意义的中间步骤，比如在数学题中的一个中间等式。在使用 CoT 解决问题的时候，每一个思维都会被顺序采样 $z_i\sim p_{\theta }^{\text{CoT}}(z_i\mid x,z_{1\dots i-1})$，然后最终综合思维链的所有中间过程输出 $y\sim p_{\theta }^{\text{CoT}}(y\mid x,z_{1\dots n})$。在实践中，整段 $[z_{1\dots n},y]$ 会被看成一个连续的语言序列，在 $p_{\theta }^{\text{CoT}}(z_{1\dots n},y\mid x)$ 中一次性采样成一个连续的语言片段，对思维链的划分方式一般是隐含的，并没有显式标注。

• Self-consistency with CoT (CoT-SC)：是一种集成方法，会采样 $k$ 条独立同分布的思维链 $[z_{1\dots n}^{(i)},y^{(i)}]\sim p_{\theta }^{\text{CoT}}(z_1\dots z_n,y\mid x)$，然后返回一个最常被输出的结果 $\arg {\max }_y\#\{i\mid y^{(i)}=y\}$。CoT-SC 比普通 CoT 做得更好，因为同一个问题通常会存在多种不同的思考过程，比如一个定理一般有多种证明方式，通过探索更丰富的思维链集合，最终输出的决策会更可靠。然而，在每一条思维链内部并没有对不同中间思维步骤进行局部探索，而且这种选择最频繁的启发式输出方式一般只在输出空间较小的时候才适用。

3. Tree of Thoughts Framework