思想之树：将系统2的概念纳入LLM，甚至比基于CoT的GPT-4更加强大
三个要点
✔️ 受Yoshua Bengio等人寻求的系统2概念的启发，探索、战略预测和自我评价已被纳入LLM
✔️ 它通过ToT（思想树）而不是CoT（思想链）从多个选项中进行探索，甚至超越了困难的GPT-4任务。它在GPT-4难以完成的任务上表现出超越性的性能。
✔️ 该系统可以与商业LLM相结合，对于一个复杂的系统来说，它的计算成本很低，这可能导致广泛的应用。
Tree of Thoughts:Deliberate Problem Solving with Large Language Models
written by Shunyu Yao,Dian Yu,Jeffrey Zhao,Izhak Shafran,Thomas L. Griffiths,Yuan Cao,Karthik Narasimhan
(Submitted on 17 May 2023)
Comments: Code repo with all prompts: this https URL
Subjects: Computation and Language (cs.CL); Artificial Intelligence (cs.AI); Machine Learning (cs.LG)
code：
本文所使用的图片要么来自论文、介绍性幻灯片，要么是参考这些图片制作的。
概述
ChatGPT（GPT-3.5，GPT-4）等LLM之所以能够像回答一个（知识丰富的）人一样，融入操作者的意图，原因之一是当LLM模型超过一定程度，变得很大时，它们能够理解思想链（CoT : Chain of Thoughts）。Chain of Thoughts），当LLM模型超过一定程度的规模。此外，通过将思维链纳入模型的指令中，可以获得更理想的反应（提示工程）。已经有很多关于提示工程的出版物和研究，并对这些出版物进行了调查。
本文试图将系统2的处理添加到由Chain of Thoughts实现的系统1的能力中，使NLPs进行更像人类的推理。具体来说，我们引入了一个名为 "思想之树"（ToT）的框架，它通过探索、战略预测和自我评价来实现有意的问题解决，从而扩展了语言模型的能力。这使得语言模型能够考虑多种推理途径，做出全局性的选择，并在必要时进行回溯，提高他们在24个游戏、创意写作和小型填字游戏等任务中解决问题的能力。
介绍
语言模型（LM），如GPT和PalM，是基于文本生成的自回归机制，其中标记级的决定是一个接一个，从左到右。本文提出了这样的问题：这种简单的机制是否足以为一般的问题解决者建立LM，以及哪些问题挑战了当前的范式。本文研究了关于人类认知的文献，作为回答这些问题的线索。
在对人类认知的研究中，双重过程理论认为，人们在参与决策时有两种模式：一种是快速、自动、无意识的模式（"系统1"），另一种是缓慢、慎重的意识模式（"系统2"）。这两种模式已经与机器学习中使用的各种数学模型联系起来。(Yoshua Bengio在NIPS2019上的一个著名的主题演讲）例如，关于人类和其他动物的强化学习的研究已经探索了联想的 "无模型 "学习和更慎重的 "基于模型 "规划的情况。"在LM中通过简单的联想进行象征性的水平。选择让人联想到 "系统1"，因此被一个更慎重的 "系统2 "规划过程所增强，该过程（1）保持和探索各种选择，而不是简单地选择当前的选择，以及（2）积极向前和向后看，以评估当前的情况并做出更全面的决定。人们认为，在以下方面会有好处。
| 系统1。 | 系统2。 |
| 直观的 | 内省 |
| (太)快 | 深夜 |
| 无意识的 | 有意识的 |
| 有偏见的反应。 | 规范性的反应 |
| 背景 | 抽象的 |
| 自动 | 监管 |
| 联想 | 基于规则 |
| 经验性的 | 后果论者 |
为了设计这样一个规划过程，我们回到了人工智能（和认知科学）的起源，并从Newell、Shaw和Simon在20世纪50年代探索的规划过程中获得了灵感 Newell及其同事将问题解决描述为对代表为树的组合问题空间的探索。表征为对以树为代表的组合问题空间的探索。因此，作者提出了用语言模型解决一般问题的思想之树（ToT）框架：如图1所示，现有的方法是对解决问题的连续语言序列进行采样，而ToT则是主动维护思想之树、每个想法都成为一个连贯的语言序列，作为解决问题的中间步骤（表1）。这些高层次的语义单元使LM能够自我评价不同的中间思想是如何通过刻意的推理过程走向问题解决的，这也是语言的实例化（图2、4和6）。这种通过LM自我评估和深思熟虑实现的搜索和发现方法（启发式方法）与以前的搜索和发现方法相比是新颖的，这些方法要么是基于程序，要么是基于学习。最后，这种基于语言的生成和评估各种思想的能力与搜索算法相结合，如广度优先搜索（BFS）和深度优先搜索（DFS），以便利用前瞻和回溯对思想树进行系统探索。
为了评估，我们提出了三个新的任务（24个游戏、创意写作和填字游戏），即使是现有的LM推理方法，包括最先进的GPT-4语言模型，也具有经验上的挑战性（表1）。这些任务需要演绎、数学、常识和词汇推理能力，以及包含系统规划和探索的方法。
事实证明，ToT在这些任务中大大增加了语言模型的问题解决能力。作者还分析了不同的替代方案如何通过系统化的刻画影响模型的性能，并讨论了未来更好地训练和使用语言模型的方向。
背景
首先，给出了一些现有的使用大规模语言模型来解决问题的方法。
输入-输出（IO）提示是将输入x转换为输出y的最常见方式：y∼pθ(y|promptIO(x))，promptIO(x)用几拍任务指令或输入-输出例子来包装输入x。为简单起见，让prompt θ (output | input) = pθ(output | prompt(input))，这样，IO提示可以表述为y∼pIO θ (y|x)。
思想链（CoT）提示 被提出来处理从输入x到输出y的映射是非琐碎的情况（例如，x是一个数学问题，y是最终的数字答案）。关键的想法是引入一个连接x和y的思想链z1, -, zn，其中每个zi是一个连贯的语言序列，作为解决问题的一个有意义的中间步骤（例如，zi可以是数学QA中的一个中间方程）。要解决CoT中的一个问题，每个思想zi∼ pCoT θ (zi | x, z1--i-1)被依次采样，然后输出y ∼ pCoT θ (y|x, z1--n)。在实践中，[z1--n, y] ∼ pCoT θ (z1--n, y|x)被作为一个连续的语言序列进行采样，使得思想的分解（例如，每个zi是一个短语、一个句子还是一个段落）变得模糊。
CoT-SC（与CoT自洽 ）是一种集合方法，它对k个独立同分布的思想链进行采样：[z(i) 1--n, y(i)] ∼ pCoT θ (z1--n, y|x) （i = 1 - - k），最频繁的输出：arg maxy #{i | y(i) =y}，其中CoT-SC改进了CoT。这是因为对于同一个问题，一般都有不同的思维过程（如证明同一定理的不同方法），通过探索更丰富的思维，可以使输出决策更加忠实。然而，在每个链条中，不同的思维步骤不能被局部探索，"模式最大 "的发现方法只适用于输出空间有限的情况下（如多选题QA）。
思考的树：LM的意向性问题解决
要理解强调的文本，重要的是要理解系统规划和搜索的概念。系统规划包括将一个复杂的问题分解成更小、更容易管理的部分，并制定一个计划，以合乎逻辑和有组织的方式解决每个部分。搜索算法是用来探索问题领域并找到最佳解决方案的。在语言建模的背景下，系统规划和搜索使用模型来生成和评估问题的不同可能解决方案。
1.思维的分解 CoT以一种连贯的方式对思维进行采样，而没有明确的分解，ToT使用问题的特征来设计和分解中间的思维步骤。整个段落（创意写作）。一般来说，思考需要 "小"，这样LM才能产生一个有希望的、多样化的样本；"大"，这样他们才能评估自己解决问题的前景（例如，生成一本书通常是 "大"，而且不连贯）。
2.给定一个思维生成器G(pθ, s, k) 树状状态s=[x, z1---i]，考虑两个策略，为下一个思维步骤生成k个候选人：
(a) 来自CoT提示的独立同分布思想的样本（创意写作，图4）：z(j) ∼ pCoT θ (zi+1|s) = pCoT θ (zi+1|x, z1--i) (j = 1 - - k)。 当思想空间很丰富时（例如，当每个思想是一个段落时），这导致了独立同分布样本的多样性。
(b) 使用 "提议提示 "依次提出想法（24游戏，图2；填字游戏，图6）：[z(1), - -, z(k)] ∼ppropose θ (z(1--k) i+1 | s)。 当思维空间比较受限时（例如，当每个思维只是一个词或一行字时），这种方法更有效，因为它避免了在同一上下文中提出不同的思维而造成的重复。
3. 状态评估器V（pθ，S） 给定一个不同状态的前沿，状态评估器作为搜索算法的发现方法，评估他们解决问题的进展，并决定继续探索哪些状态，以何种顺序进行。发现方法是解决搜索问题的标准方法，通常是通过编程（如DeepBlue）或通过学习（如AlphaGo）。作者提出了第三种选择，使用LM来故意推断状态。在可以应用这种有意发现方法的地方，它们比编程的规则更灵活，比训练的模型更节省样本。与思维生成器一样，我们考虑了两种策略，它们可以独立或一起评估状态：
(a) 独立评价每个状态：v (pθ, S)(s) ∼ pvalue θ (v|s)∀s∈S，其中价值提示解释了为什么对于状态s要产生一个标量值v（如1-10）或一个分类（如确定/可能/不可能），可以启发式地改变为一个值。这种评价性推理的理由可能因问题和思考步骤的不同而不同。在这项研究中，少量的预期性模拟（例如快速检查5+5+14会导致5、5、14达到24，或者通过填入""来确认 "hot l "意味着 "inn"）和常识（例如，1 2 3太小，不可能是24，或者 "tzxc"没有以 "tzxc "开头的词）来探讨评价。前者可能促进 "好 "的状态，而后者可能有助于消除 "坏 "的状态。这样的评价不需要是完美的，它们只需要是近似的。
(b) 跨状态投票：v (pθ, S)(s) = 1[s = s∗]，其中 "好 "状态s*∼pvote θ (s∗|S)是在投票提示时故意比较了S中的不同状态后投给的。当很难直接评估一个问题的成功与否（例如一段话的连贯性）时，自然会比较不同的部分解决方案，并投票给最有希望的一个。换句话说，"探索哪种状态 "被作为一个多选题的QA，并使用LM样本进行投票。
无论是哪种策略，都可以促使LM多次汇总数值，或者在投票结果中用更忠实/稳健的发现方法取代时间/资源/成本。
4.搜索算法 最后，ToT框架允许根据树形结构即插即用各种搜索算法。
(a) 广度优先搜索(BFS)(算法1)每步保持一组b个最有希望的状态。它被用于24个游戏和创意写作，其中树的深度是有限的（t≤3），初始的思考步骤可以被评估和修剪成一个较小的集合（b≤5）。
(b) 深度优先搜索（DFS）（算法2）首先搜索最有希望的状态，直到达到最终输出（t>T）或直到状态评估器决定从当前的s不能解决问题（V（pθ，{s}）（s）≤vth为价值阈值vth）。最有希望的状态首先被搜索到。在后一种情况下，从s开始的子树被修剪以交换探索和利用。在这两种情况下，DFS回溯到s的父状态并继续搜索。
ToT框架旨在通过管理一棵思想树来支持系统的计划和检索。每个想法都是一个连贯的语言序列，作为解决问题的中间步骤；LM可以自我评价不同的中间想法是如何通过刻意的推理过程走向解决问题的，这也是语言中的实例化。这使得LM可以考虑几种不同的推理途径，自我评价他们的选择，并确定他们的下一步行动方案。它还允许他们做出全局性的选择，在必要时向前看或回溯。
从概念上讲，ToT作为一种使用LM的一般问题解决技术具有以下优势
(1) 通用性 IO、CoT、CoT-SC和自我完善可以被看作是ToT的特例（即深度和宽度有限的树；图1）。
(2) 模块化 从基础LM开始，思维分解、生成、评估和探索程序可以独立变化。
(3) 适应性 能够应对问题特征、LM能力和资源限制的差异。
(4) 方便 不需要额外的训练，预先训练好的LM就足够了。
也就是说，ToT是灵活的，可以适应不同的思维层次、不同的思维生成和评价方式以及不同的特定问题的搜索算法。这意味着该框架可以被定制以适应不同任务和问题的需要。
实验
我们提出了三个任务，这些任务很难使用标准的IO和CoT提示从最先进的语言模型GPT-4中采样。
24场比赛
24的游戏是一项数学推理任务，目标是使用四个数字和基本算术运算（+-*/）获得24。例如，给定一个'4 9 10 13'的输入，可以输出答案'（10-4）*（13-9）=24'。
任务设置 我们从 4nums.com上搜刮数据，有1362个游戏按人类解题时间划分为易到难，其中相对较难的游戏子集索引为901-1,000，用于测试。对于每个任务，当输出是一个等于24的有效方程，并且每个输入数字正好被使用一次时，就认为是成功的；超过100个游戏的成功率作为索引；超过100个游戏的成功率作为索引；超过100个游戏的成功率作为索引。
基准线 五个语境中的例子被用于标准的输入-输出（IO）提示。在思维链（CoT）提示中，每个输入-输出对被三个中间方程所加强，每个方程都对剩余的两个数字进行操作。例如，给定输入'4 9 10 13'，思考'13 - 9 = 4（左：4 4 10），10 - 4 = 6（左：4 6），4 * 6 = 24（左：24）'。对于每个游戏，IO和CoT的提示被抽查了100次，以检查平均性能。我们还考虑了CoT自洽基线，它从100个CoT样本中获取多数输出，以及在最多10个IO样本上的迭代细化方法。在每次迭代中，LM都会对之前的所有历史进行处理，因此如果输出不正确，它就会 "反思错误并生成一个精炼的答案"。
设置ToT 为了将24小时游戏纳入ToT，很自然地将思维分解成三个步骤，每个步骤都是一个中间方程，如图2(a)所示。 在每个树形节点中，"左 "的数字被准确显示，促使LM提出可能的下一步。图2(b)。同样的 "建议提示 "被用于所有三个思考步骤，但只有一个例子有四个输入：ToT执行广度优先搜索（BFS），在每一步留下最好的b=5个候选者；如图2（b）所示，为了在ToT中执行故意的BFS，要求LM建议每个候选人的想法，促使他们在 "确定/可能/不可能 "的基础上评价他们是否能达到24。这样做的目的是为了促进那些可以通过事先的几次试验来验证的正确的部分解决方案，消除基于 "过大/过小 "常识的不可能的部分解决方案，并使其余的成为 "可能"。每种思想的数值都会被抽查三次。
结果 如表2所示，IO、CoT和CoT-SC提示方法在这项任务中表现不佳，只取得了7.3%、4.0%和9.0%的成功率。相比之下，宽度为b=1的ToT已经取得了45%的成功率，b=5取得了74%。我们还考虑了IO/CoT的神谕设置，使用k个样本中的最佳样本（1≤k≤100）计算成功率。为了比较IO/CoT（k中的最佳样本）和ToT，我们计算了ToT在b=1--5时每个任务访问的树节点，图3（a)来考虑映射出五个成功率。毫不奇怪，CoT的扩展性比IO好，100个CoT样本中最好的成功率达到49%，但仍然比探索ToT中更多的节点差很多（b>1）。
错误分析 图3(b)分析了CoT和ToT样本在哪一步失败了，即这些想法（在CoT中）或所有b个想法（在ToT中）是无效的还是不可能达到24。值得注意的是，大约60%的CoT样本在第一步就已经失败了，即当他们产生前三个词的时候（如'4+9'）。这突出了直接从左到右解码的问题。
创意写作
下一个任务是创造性的写作任务，输入是四个随机的句子，输出必须是一个由四个段落组成的连贯句子，每个段落以四个输入句子为结尾。这样的任务是开放性和探索性的，需要高度的计划性以及创造性思维。
任务设置 从Randomwordgenerator.com中抽出随机句子，形成100个输入。每个输入约束都没有基础段落；由于发现GPT-4在大多数情况下能够遵循输入约束，作者使用了两种方法：使用GPT-4的零射提示来提供1-10的标度分数，以及使用人类判断来他们着重于用两种方式评估句子的连贯性：通过比较不同方法的输出对。在前者中，对每项任务的输出抽出五个分数，并取其平均值。通常发现这五个分数是一致的，各输出的标准差平均约为0.56。对于后者，我们对一个作者子集进行了盲审，比较了CoT和ToT生成的对的一致性，其中段落的顺序被随机颠倒了100个输入。
考虑到基线 任务的创造性，IO和CoT的提示都是零射。前者提示用户在有输入约束的情况下直接生成连贯的句子，而后者则提示用户先做一个简单的计划，然后写一个句子，即计划是中间的思考步骤；每个任务产生十个IO和CoT样本；后者则提示用户在有输入约束的情况下生成一个连贯的句子。在这种情况下，LM根据输入约束和最后生成的句子，决定该句子是否已经 "完全连贯"，如果不是，则生成一个完善的句子。
ToT设置 LM首先生成k = 5个计划，并为最佳计划投票（图4），然后根据最佳计划也生成k = 5个通道，并为最佳通道投票。这里，我们设置了宽度限制b = 1，因为每一步只保留一个选择。使用一个简单的零次投票提示（"分析以下选项，并得出哪个是最有希望的指令"），我们在两个步骤中都抽查了五次投票。
结果 图5(a)显示了100个任务的GPT-4平均得分，表明ToT（7.56）被认为比IO（6.19）或CoT（6.93）产生的句子更连贯。虽然这样的自动测量可能是有噪音的，但图5(b)支持了这一结果，它显示人类在100个段落对中的41个中喜欢ToT而不是CoT，而在21个中喜欢CoT而不是ToT（其他38个对被判断为 "同样一致"）。最后，在这个自然语言任务中，迭代精炼更为有效，将IO的一致性分数从6.19提高到7.67，将ToT的一致性分数从7.56提高到7.91。 ToT框架中思想生成的第三个方法是使用独立的相同分布或顺序生成而是对旧思想的提炼，我们认为新思想可以被认为是通过提炼旧思想而产生的。
小型填字游戏
在24个游戏和创意写作中，ToT相对较浅，最多需要三个思考步骤才能达到最终输出。在这里，我们考虑一个更具挑战性的自然语言搜索问题，一个5 x 5的小型填字游戏。同样，这里的目的不是简单地解决这个任务，因为一个典型的填字游戏很容易被一个专门的NLP管道利用大规模搜索而不是LM解决。相反，我们的目的是探索LM作为一般问题解决者的局限性，他们探索自己的思维，用刻意的推理作为一种发现方法来指导自己的搜索。
设置任务 我们从 GooBix获得了156个5x5迷你填字游戏的数据。由于我们知道相邻的游戏包含类似的线索，我们决定使用指数为1、6、- -、91和96的20个游戏进行测试，136、141、146、151和156用于提示。对于每个任务，输入描述了五个水平线索和五个垂直线索，输出是一个5×5=25个字母的棋盘，用于解决填字游戏。对于评估，考虑了三个成功水平：正确的字母部分（每局25个），单词（每局10个）和游戏。
基线 IO提示说明了五个输入-输出对，CoT提示进一步说明了h1.....5 → v1...5，并按此顺序添加中间词。每个提示的10个样本被运行，结果为平均数。
ToT的设置 ToT利用深度优先搜索（算法2）继续探索最有希望的后续单词线索，直到该状态不再有希望，之后回溯到父状态，探索替代方案。为了方便搜索，后续的思维被限制在不改变填充的单词或字母，在ToT中最多有10个中间步骤。在思维生成中，在每个状态下，现有的思维（如图6(a)中的'h2.motor; h1.task'）被转换为其余线索的字母约束（如'v1.To heap: tm ;...）)，然后用建议提示五次，让他们想出候选人来填补下一个词的位置和内容。重要的是，我们鼓励LM对不同的想法给出一个置信度，这些置信度在不同的建议中被汇总，以获得一个分类的想法列表，以便接下来进行探索（图6（a））。对于状态的评估，每个状态同样被转化为剩余线索的字符约束，并对每条线索进行评估，看是否有可能在约束条件下进行填充。如果剩余的线索被认为是 "不可填充的"（例如 "v1.To heap: tm s"），那么该状态的子树搜索就会被修剪，DFS回溯到其父级，以搜索下一个有希望的思想；将DFS搜索步骤限制在100个，探索得最深的状态（如果多是第一个探索的状态）只在最终输出中呈现。
结果 如表3所示，IO和CoT的提示方法表现很差，词级成功率不到16%，而ToT在所有衡量标准上都有明显的改进，达到了60%的词级成功率，并且解决了IO和CoT的20个游戏中的4个。鉴于缺乏尝试线索、改变决定或回溯的机制，这样的改进并不令人惊讶。
关于甲骨文和砍伐的研究 如果输出是来自甲骨文（oracle）对每个任务的最佳DFS状态（而不是启发式方法确定的最佳状态），ToT的表现甚至更好，实际上解决了7/20的游戏（表3，'+最佳状态'）。这表明本文的简单输出发现方法很容易被改进。有趣的是，在实际解决填字游戏时，状态评估器可能会将一些词判断为 "不可能 "并修剪分支。这可能是因为5x5填字游戏在设计上有一些不寻常或过时的词，GPT-4无法识别。由于状态评估作为修剪检测的方法并不完善，我们也考虑过禁用修剪，但发现这通常会降低性能（表3，"-prune"）。然而，在实践中，在4/20个游戏中可以找到正确的解决方案（但只有1个由发现方法输出），其中3个不能在100步内用ToT+剪枝法解决。因此，改进DFS剪枝的发现方法对于解决这种情况下的问题至关重要。最后，回溯的重要性被证实了，它是通过执行一个分割法，在最多20步内不断填入最有希望的线索并允许覆盖。这与宽度限制为b=1的 "贪婪的 "BFS搜索类似，后者的表现很差，在词的层面上只有20%的成功率（表3，'-backtrack'）。
摘要
局限性和未来方向。
许多GPT-4已经擅长的任务可能不需要像ToT那样进行刻意的探索。作为初始步骤，本研究仅挑战GPT-4探索三个相对简单的任务，这些任务需要LM中嵌入的更好的探索和规划技能。然而，随着我们开始将LM引入到更现实的决策应用中（如编码、数据分析、机器人技术），更复杂的任务可能会出现，并为探索这些研究问题提供新的机会。另外，虽然ToT等探索性方法比抽样方法需要更多的资源（如GPT-4 API成本）来提高任务性能，但ToT的模块化灵活性使用户可以定制性能和成本之间的权衡。而正在进行的开放源码计划应该在不久的将来很容易降低这一成本。最后，本研究侧重于商业LM的使用，使用ToT式的高层次反事实决策（如思考下一段的潜在选择，而不是预测下一个符号）对LM进行微调，可能会增强LM的问题解决能力可以提供一个机会。
更广泛的影响
ToT是一个框架，使LM能够更自主、更智能地做出决定和解决问题。虽然目前的任务仅限于推理和搜索问题，但未来涉及与外部环境和人类互动的应用可能会带来潜在的危险，例如促进对LM的有害使用。另一方面，ToT也将改善模型决策的可解释性和人类调整的机会，因为所产生的表征是可读的、高水平的语言推理，而不是隐含的、低水平的标记值。
结论
LM的关联性 "系统1 "可以通过 "系统2 "得到有益的补充，"系统2 "是基于对解决问题的可能路径的树状搜索。思维之树 "框架提供了一种方法，将关于问题解决的经典见解转化为现代LM的实用方法。同时，LM解决了这些经典方法的弱点，并提供了一种解决复杂问题的方法，这些问题不能像创造性工作那样容易地被形式化。作者和其他人认为LM和经典人工智能方法之间的这种交叉是未来研究的一个令人兴奋的方向。
与本文相关的类别
