Tree of Thoughts: Deliberate Problem Solving with Large Language Models
https://github.com/princeton-nlp/tree-of-thought-llm

标题翻译：思维树：利用大型语言模型问题求解

1. 内容介绍

1.1. 背景

决策过程有两种模式：

快速、自动、无意识的模式（System 1）-- 语言模型基于语言的token联想生成
缓慢、谨慎、有意识的模式(System 2) – 多样化选择和规划的过程

现有的LLM方法在复杂问题中面临两大局限：

局部探索不足：在生成过程中不能同时探索多种可能的推理路径
缺乏全局规划：没有能力回溯或前瞻，导致路径选择可能陷入局部最优解

论文提出了思维树的框架，可以与搜索算法相结合，例如广度优先搜索（BFS）或深度优先搜索（DFS）来进行前瞻、回溯和状态评估。

1.2. 对比图：

在这里插入图片描述

IO：传统的从输入直接生成输出，属于单步决策，无探索过程
CoT：通过生成一系列中间步骤（思维链）来推导最终结果，但每次仅沿单一路径生成，缺乏分支探索能力
SC-CoT：通过采样多条独立的思维链，利用多数投票机制实现自一致性
ToT：允许在每个思维步骤生成多种可能的中间状态，并选择最有希望的分支，每个分支的状态可以通过启发式评估（如评分或投票）确定是否继续扩展

1.3. 什么是思维？

根据不同的问题，一个思维可能是：
在这里插入图片描述

填字游戏：几个单词
24点：一行算式
创意写作：一段文字

2. 研究方法

2.1. 框架设计：ToT框架围绕以下四个核心问题展开

如何分解问题？-- 思维分解：将复杂问题分解为多个中间步骤，每个步骤称为一个思维，思维需要足够小以保证模型能生成多样化候选解，又要足够大以便评估
如何生成候选解？ – 思维生成器G(p,s,k)={z1,z2…zk}：输入当前的状态s=[x,z1,z2…zi]（x表示问题，z是中间的思维），利用语言模型p生成k个候选思维z
有两种生成策略：
1. 随机生成：用COT独立随机生成k个候选解，多样性更好，适合开放性任务（如写作）；
2. 顺序生成：在同一上下文中逐步生成k个候选解，适合约束较强的任务（如数学问题）
如何评估候选状态？ – 状态评估器V(p,S)(s)=score：给定多个候选状态的集合S，通过启发式方法评估
有两种评估策略：
1. 独立价值评估：为每个状态s生成一个分数（如 1-10）或分类标签（如 “sure” / “maybe” / “impossible”）；
2. 投票评估：跨状态比较，通过对比多个状态，选择最有潜力的一个（类似于SC）。对于这两种策略，都可以多次提示LM来整合价值或投票结果
如何搜索最优路径？-- 选择什么搜索算法：
1. BFS: 每层保留b个最优状态，逐层展开,适合24点这种层少的
2. DFS:首先探索最有希望的状态，直到达到最深；或者状态评估器认为从当前状态s解决问题是不可能的（价值V < v_th（临界值）），就修剪停止扩展并回溯到s的父状态

2.2. 优点：

模块化与灵活性：可以分别调整上面四个模块，选择不同LM,思维生成策略，状态评估策略，搜索算法
高适应性：针对不同任务可以有不同的策略
无需额外训练

3. 实验

3.1. 24点任务：100个实例

在这里插入图片描述

3.1.1. 步骤

将问题分解为3步，每步生成一个中间算式，然后使用BFS（b=5）确保所有可能的算式都被探索，且通过启发式评估筛选出最有潜力的路径（顺序生成，独立评估，BFS）

步骤1：从四个数字中选取两个进行运算，生成一个新的状态（例如4+9=13或者10-4=6）
步骤2：使用剩余的数字进行下一步操作，生成新的候选状态
步骤3：根据启发式评估（分类标签），判断当前状态是否有可能最终达成目标24

3.1.2. 结果：

对于每种方法，选择100次尝试中的最好结果，作为理论上的最佳表现

在这里插入图片描述

表2：
- IO prompt：传统的输入输出方法，直接从输入（数字）到输出（算式）进行推理，但没有中间推理过程
- CoT prompt：生成一系列中间步骤，逐步推导结果
- CoT-SC：使用k个CoT的样本，通过投票选择最常见的答案，以增强推理的多样性
- IO + Refine：对IO方法进行迭代优化，在每次生成后进行反思和修正
图3a：访问节点越多，成功率越高，ToT能够探索更多的路径，从而大大提高成功率
图3b：CoT方法容易在推理的初期阶段就走错路径，但TOT因为有评估并能够进行回溯修正所以能够保持更高的成功率