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
有两种生成策略：- 随机生成：用COT独立随机生成k个候选解，多样性更好，适合开放性任务（如写作）；
- 顺序生成：在同一上下文中逐步生成k个候选解，适合约束较强的任务（如数学问题）
如何评估候选状态？ – 状态评估器V(p,S)(s)=score：给定多个候选状态的集合S，通过启发式方法评估
有两种评估策略：- 独立价值评估：为每个状态s生成一个分数（如 1-10）或分类标签（如 “sure” / “maybe” / “impossible”）；
- 投票评估：跨状态比较，通过对比多个状态，选择最有潜力的一个（类似于SC）。对于这两种策略，都可以多次提示LM来整合价值或投票结果
如何搜索最优路径？-- 选择什么搜索算法：
- BFS: 每层保留b个最优状态，逐层展开,适合24点这种层少的
- 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因为有评估并能够进行回溯修正所以能够保持更高的成功率
3.2. 创意写作任务：
根据四个随机的句子生成一篇连贯的文章，每段结尾包含一个输入句子（随机生成，投票评估，BFS）
3.2.1. 步骤
- 生成计划：根据输入生成多个写作计划
- 评估计划：对计划投票
- 生成完整段落：根据最好的计划生成多个完整段落
- 评估段落：再对完整的段落再进行投票，选择最连贯的段落生成方案
3.2.2. 结果：用GPT-4（1-10分）和人类来评估每个生成的段落的质量
都是ToT方式得分最好
3.3. **5×5Mini填词任务：
20个实例，评估，正确字母的比例（每个游戏25个）、单词数（每个游戏10个）和完成游戏数 （顺序生成，独立评估，DFS）
3.3.1. 步骤
- 候选生成：根据字谜提示生成多个候选单词
- 启发式评估：每个候选单词会通过启发式评估器进行评分，判断其与其他已填单词的交叉匹配程度，根据得分选择得分最高的单词填入网格，并继续处理其他空格，如果某个单词导致冲突（如垂直或水平单词不匹配），就修剪掉并回溯到上一步的，选择其他候选单词
3.3.2. 结果：
通过假设理想化的评估机制（Oracle），来模拟最优路径选择，模拟ToT上限，能达到35%的游戏完成率，可能是因为5×5填字游戏设计中有一些GPT-4无法识别的罕见或过时单词
去掉剪枝或者去掉回溯后效果表现均不佳
3.4. 消融实验
换了点更艰难的任务，然后换了LM版本比较
3.5. 计算成本
计算成本相对来说很大
4. 总结：
ToT通过探索不同路径、评估中间状态并进行全局优化，提高模型在复杂任务中的问题解决能力
未来的方向还是LLM的微调和更高效的搜索算法（如A*）