笔记整理：许泽众，浙江大学博士，研究方向为知识图谱上的神经符号推理
链接：https://arxiv.org/abs/2305.10601
1. 动机
语言模型是一种强大的工具，可以用于各种需要数学、符号、常识或知识推理的任务。然而，现有的语言模型推理方法通常只能进行基于单词的、从左到右的决策过程，这意味着它们在需要探索、策略性预测或初始决策至关重要的任务上可能表现不佳。为了解决这些挑战，本文提出了一个新的语言模型推理框架，“Tree of Thoughts”（ToT），它能够在思想（thoughts）之间进行多样化的推理路径探索，其中每个思想是一个连贯的文本单元，作为问题解决的中间步骤。ToT允许语言模型通过考虑多种不同的推理路径并自我评估选择来决定下一步行动，以及在必要时进行前瞻或回溯以做出全局决策。本文在三个新颖的问题解决任务上展示了ToT显著提高了语言模型的问题解决能力：24点游戏、创意写作和迷你填字游戏。例如，在24点游戏中，使用链式思维（CoT）提示的GPT-4只能解决4%的任务，而我们的方法达到了74%的成功率。我们还通过系统地消除分析了不同选择如何影响模型性能，并讨论了未来更好地训练和使用语言模型的方向。
2. 方法
模型的整体架构如下：
左边三个模型是其主要对比的baseline，都是提出prompt激活大模型能力的方法。可以看到ToT的主要区别和基本思路是1、将一个大问题分解成多个步骤的子问题，逐步解决问题；2、在每一步上，都提出多个可能的解决方法；3、判断每一步的最优解，然后在上一步的决策基础上生成下一步的多个解决方案，直到完成问题。
那么以上思路需要面对四个问题：1、如何将中间过程分解为思路步骤；2、如何从每个状态生成潜在的思路；3、如何启发式地评估状态；4、使用什么搜索算法。
论文给出的思路是：
1、如何将中间过程分解为思维步骤。这一步要求根据不同的问题特点，设计和拆分合适的思维步骤。思维步骤应该足够小，以便LM能够生成有意义和多样的候选方案，但也足够大，以便LM能够评估它们对问题解决的贡献。
2、如何从每个状态生成潜在思维。这一步要求给定一个树节点，即一个包含输入和已有思维序列的状态，使用LM来生成一些可能的下一步思维。有两种生成策略：一种是从sample中独立采样思维，适用于思维空间丰富的情况；另一种是使用propose来顺序提出思维，适用于思维空间受限的情况。两者的区别在于前者只需要根据已有的thought多次单独生成当前一步的thought，后者需要一次性将当前一步若干个可能的thought全部生成，并且要求每个thought不能相同。
3、如何启发式地评估状态。这一步要求利用LM对不同的状态进行评估，作为搜索算法的启发式指导。有两种评估策略：一种是对每个状态单独给出一个数值或分类的评价，基于少量的前瞻模拟和常识推理；另一种是让LM在不同的状态之间进行投票式选择，基于对比和分析。这一步选择最佳状态也是将已有的输出重新输入模型中，让LLM进行打分。
4、什么样的搜索算法。这一步要求根据树的结构和问题的性质，选择合适的搜索算法来探索树上的节点。本文中考虑了两种简单的搜索算法：广度优先搜索（BFS）和深度优先搜索（DFS），并留下了更高级的搜索算法（如A*，MCTS）作为未来工作。
3. 实验
这篇文章在三个任务上进行了实验。分别是计算24点，创意写作和填字游戏。任务样例如上图所示。
对于24点游戏，其结果如下：
表2显示，IO、CoT和CoT-SC这三种方法在这个任务上表现不佳，成功率只有7.3%、4.0%和9.0%。相比之下，ToT在分支数量为b=1时就已经达到了45%的成功率，而b=5时则达到了74%。另外还考虑了一个IO/CoT的最优设置，通过使用最优的k个样本（1≤k≤100）来计算成功率。为了比较IO/CoT（最优的k）和ToT，我们考虑计算ToT在b=1···5时每个任务访问的树节点数，并将5个成功率映射到图3（a）中，将IO/CoT（最优的k）视为在一个bandit中访问k个节点。结果显示CoT比IO更具可扩展性，100个CoT样本的最优结果达到了49%的成功率，但仍然比在ToT中探索更多节点（b>1）要差。
对于写作任务：
图5（a）显示了100个任务的平均GPT-4分数，其中ToT（7.56）被认为比IO（6.19）和CoT（6.93）平均生成更连贯的段落。虽然这样的自动指标可能有噪音，但图5（b）通过显示人类在100对段落中有41对更喜欢ToT而只有21对更喜欢CoT来证实了这一发现（另外38对被认为“相似连贯”）。最后，迭代细化在这个自然语言任务上更有效，其中它将IO的连贯性分数从6.19提高到7.67，将ToT的连贯性分数从7.56提高到7.91。我们认为这可以被视为ToT框架中思想生成的第三种方法，即新的思想可以通过改进旧的思想而不是独立或顺序生成而产生。
对于填字任务：
表3显示，IO和CoT提示方法的词级成功率低于16%，而ToT显著提高了所有指标，达到了60%的词级成功率。文章认为这是因为IO和CoT缺乏尝试不同线索、改变决策或回溯的机制。
4. 总结
这篇论文提出了一种用大型语言模型（LLM）进行有目的的问题解决的新框架，叫做“思维树”（ToT）。ToT将任何问题视为一个思维树的搜索问题，其中每个节点是一个包含输入和一系列中间思维的状态，每个思维是一个有意义的语言序列。ToT利用LLM来生成和评估不同的思维候选，并结合搜索算法来探索不同的推理路径。作者在三个需要非平凡的规划或搜索的新任务上展示了ToT的效果，分别是24点游戏、创意写作和迷你填字游戏。实验结果表明，ToT显著提高了LLM的问题解决能力，相比于现有的方法，具有更高的通用性、模块性、适应性和便利性。
OpenKG
OpenKG（中文开放知识图谱）旨在推动以中文为核心的知识图谱数据的开放、互联及众包，并促进知识图谱算法、工具及平台的开源开放。
点击阅读原文，进入 OpenKG 网站。
