Algorithm of Thoughts论文阅读
Basic Information:
- Title: Algorithm of Thoughts: Enhancing Exploration of Ideas in Large Language Models (思维算法：增强大型语言模型中的思路探索)
- Authors: Bilgehan Sel, Ahmad Al-Tawaha, Vanshaj Khattar, Lu Wang, Ruoxi Jia, Ming Jin
- Keywords: Large Language Models, algorithmic reasoning, idea exploration, in-context learning
- URLs: Paper, [GitHub: None]
简要 :
- 本研究提出了一种名为“Algorithm of Thoughts”的新策略，通过算法推理路径提高大模型的推理能力，实现在上下文学习中的思路探索。
- 近年来，大型语言模型在一般问题解决、代码生成和指令跟随等方面展现出了强大的效能。然而，现有的方法在推理能力上存在一定的局限性。COT通过链式思维增强了LLM解决问题时思想联系的一致性，但偶尔会出现中间步骤不正确的情况。Fatithful CoT通过引出推理的符号链修正，将LLM的输出定义为伪代码以获取较高的确定性
已有研究成果
文章还比较新（8.20），这里总结了引导LLM推理已有的几个方法：
1、Standard Prompting
基础的提示词 input-output prompting。
2、COT
COT是一种基于链式推理的方法。通过给出问题的连续推理步骤，从中间推理片段c1，…，cn到达答案y，表示为x → c1 → … → cn → y。通过模仿上下文中的例子，LLM自动将解决方案分解为更简单的线性步骤，以提高在多个推理基准上的性能。
3、Least-to-Most prompting
L2M是一种基于教育心理学的方法。L2M提示将中心问题分解为较小的子问题。每个子问题按顺序解决，然后将输出结果附加到下一个子问题上（L2M文章指出COT对解决难度高于示例的问题的能力较差）。这种结构化的划分对于更广泛的泛化有益，但它的前提是在一次尝试中找到几乎完美的分解-这对于结构清晰的问题非常理想。然而，当任务与其分解的复杂性交织在一起时（例如24点游戏），这种方法的不灵活性就变得明显。
4、Tree of Thoughts
在每个子问题有多个可行选项时，为了让LLM能同时考虑多个选项引入了外部树搜索机制，同时LLM有能力主动评估可能性进行剪枝，TOT的致命弱点是对LLM的查询过度依赖，有时需要上百个查询解决一个问题。
理论
大多数改进大型语言模型（LLM）思考方式的方法都涉及停止、调整和恢复生成过程，以提高大型语言模型（LLM）的推理能力。这通常需要更多的计算资源、时间和金钱。为了解决这个问题，“算法的思想”的介绍，开创了一种新的模式，在上下文学习。这是一种新方法，引导LLM以更结构化的方式思考，类似于算法的工作方式。这种方法不需要使用许多查询，而是可以通过一个或几个提示来改进模型的推理。LLM的生成跨度仅受符号限制，似乎准备突破人类工作记忆的障碍。在这一观察的刺激下，我们调查了LLM是否可以反映类似的分层探索的想法，参考先前的中间步骤筛选出不可行的选项，所有这些都在其迭代生成周期内。人类以直觉敏锐而出类拔萃，而科学家则以有组织、有系统的探索而脱颖而出。目前的技术，如CoT，经常回避这种协同潜力，对LLM的现场精度施加了不适当的压力。通过利用LLM的递归功能，我们模拟了一种混合的人类算法方法。这是通过我们使用算法示例来实现的，这些算法示例捕获了从初始候选到验证解决方案的探索的本质。这就是我们的思想算法（Algorithm of Thoughts，AoT）。
鉴于GPT模型自回归生成文本的特点，本研究探索了将算法的迭代逻辑内化到模型中的可能性。通过使用prompt的算法示例，模型可以在迭代生成过程中参考先前的中间步骤，从而实现对问题空间的层次化探索。不同于传统的[问题，解决方案]或[问题，解决方案的连续步骤]的“监督学习”模型，AoT提出了一种覆盖[问题，搜索过程，解决方案]的新结构。自然地，当使用算法指导LLM时，预期倾向于LLM简单地模仿算法的迭代思维。然而，令人感兴趣的是LLM能够注入自己的“直觉”，以实现甚至超过算法本身的搜索效率。
算法优势
- CoT涉及经常暂停和调整LLM，但AoT鼓励更连续的思维过程。
- CoT倾向于更线性，专注于单个步骤。AoT允许进行整体探索，在确定解决方案之前考虑各种可能性。
- CoT在每一步都给LLM施加了精确性的压力，而AoT则给模型空间去探索、迭代，并将其直觉与算法推理相结合。
- AoT在计算资源方面具有更高效的潜力，因为与CoT相比，它可能需要更少的对模型的查询。
- CoT主要在每个阶段寻求精确度，而AoT则试图通过LLM自身的能力来增强算法推理，这可能会超越原始算法的性能。
方法
文章提出了一种类似深度优先搜索的搜索树方案，让LLM能在一轮迭代中尽可能多的为多个分支提出解决方案，而不是为每个子集单独查询。
1、分解子问题：给定一个问题，将其拆分并构建一颗搜索树。
2、LLM给出子问题的解法：这里文章提出直接将需要的答案按序列生成的效果好于多次单个的query，比如连续生成五个质数时第一个数是质数的概率大于直接让LLM生成一个质数。
3、衡量子问题的可信度：文中的实验结果论证LLM有能力优先考虑最有可能的解决方案，因此使用LLM解决24点问题的效率可能高于DFS或BFS搜索（但我使用0315版本GPT4，复现的时候GPT给出的解法经常是错的）
4、决策点回溯：之前的方法使用了外部手段辅助决策树上的搜索流程，文章使用了DFS方法让LLM辅助修剪，鼓励LLM优先考虑局部特征。
1 | BEGIN: |
结果:
对于24点游戏，作者使用了4nums.com上按相对难度排名的游戏，并按照之前的研究中的设置进行了实验，采用了5次提示的设置。他们将AoT方法与标准提示、CoT、CoT-SC和ToT方法进行了性能比较，并报告了每种方法的成功率和平均查询次数。
对于5x5迷你填字游戏，作者使用了goobix.com上的游戏，并按照之前的研究中的设置进行了实验，将他们的方法与标准提示、CoT和ToT方法进行了测试。他们报告了每种方法的单词成功率和平均查询次数。
在24点游戏中，AoT方法在单提示方法中表现优异，并且即使与使用ToT等外部机制的方法进行比较，仍然具有竞争力。AoT方法在仅使用一次查询的情况下达到了71%的成功率，而ToT方法在平均109.1次查询的情况下达到了69%的成功率。
在5x5迷你填字游戏中，AoT方法的单词成功率为52%，超过了标准提示和CoT方法。然而，它在单词成功率为60%的ToT方法之后，平均查询次数超过200次。
论文复现结果
1 | #gpt-35T-16k(4 4 4 4) |