State Machine of Thoughts: Leveraging Past Reasoning Trajectories for Enhancing Problem Solving

📄 arXiv: 2312.17445v2 📥 PDF

作者: Jia Liu, Jie Shuai, Xiyao Li

分类: cs.AI

发布日期: 2023-12-29 (更新: 2024-03-09)

备注: 9 pages, 4 figures

💡 一句话要点

提出SMoT，利用状态机记录推理轨迹，提升LLM在探索性问题中的解决能力

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture) 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 大型语言模型 推理 状态机 经验复用 探索-评估 问题解决 强化学习 智能体

📋 核心要点

  1. 现有LLM智能体在解决问题后，忽略了成功的推理轨迹，导致经验无法复用。
  2. SMoT使用状态机记录推理轨迹，状态表示子问题，状态转移表示子问题依赖。
  3. 实验表明，SMoT在24点游戏和出租车导航强化学习游戏中显著提升了问题解决能力。

📝 摘要（中文）

当前基于大型语言模型的智能体通常采用探索-评估框架进行推理，以树状方式导航解决问题的过程。然而，这些方法常常忽略已解决问题的成功推理轨迹，导致在未来类似问题中无法有效利用这些轨迹。为了解决这种低效问题，本文采用状态机来记录从先前推理轨迹中获得的经验。在状态机中，状态代表分解后的子问题，而状态转移反映了子问题之间的依赖关系。状态机记录成功和失败的轨迹。利用状态机中的经验，我们提出的思维状态机（SMoT）选择最优的子解决方案，并避免不正确的方案。实验表明，SMoT可以显著提高在两个探索密集型问题中的解决能力：24点游戏和出租车导航强化学习游戏。

🔬 方法详解

问题定义：现有基于LLM的智能体在解决问题时，通常采用探索-评估框架，以树状结构进行搜索。然而，一旦问题解决，成功的推理路径就被丢弃，导致后续遇到类似问题时，需要重新探索，效率低下。尤其是在探索密集型问题中，这种重复探索的代价很高。

核心思路：本文的核心思路是利用状态机来记录和复用以往的推理经验。状态机中的每个状态代表一个分解后的子问题，状态之间的转移代表子问题之间的依赖关系。通过记录成功和失败的推理轨迹，状态机能够指导智能体在后续问题中选择更优的子解决方案，避免重复犯错。

技术框架：SMoT的整体框架包含以下几个主要模块：1) 问题分解模块：将原始问题分解为一系列子问题。2) 状态机构建模块：根据推理轨迹构建状态机，其中状态表示子问题，状态转移表示子问题之间的依赖关系。3) 经验记录模块：记录每个状态的成功和失败信息，例如，哪些状态转移导致了成功，哪些状态转移导致了失败。4) 推理决策模块：在解决新问题时，利用状态机中的经验，选择最优的子解决方案，并避免不正确的方案。

关键创新：SMoT的关键创新在于将状态机的概念引入到LLM的推理过程中，从而实现了对推理经验的有效记录和复用。与传统的探索-评估方法相比，SMoT能够避免重复探索，提高问题解决效率。此外，SMoT能够同时记录成功和失败的推理轨迹，从而更全面地学习问题解决的策略。

关键设计：状态机的状态表示子问题，状态转移表示子问题之间的依赖关系。状态转移的概率可以根据历史经验进行更新，例如，如果一个状态转移经常导致成功，则其概率会增加；如果一个状态转移经常导致失败，则其概率会降低。在推理决策模块中，可以使用各种搜索算法（例如，A*搜索）来寻找最优的推理路径。具体的损失函数和网络结构未知，因为论文摘要中没有提及。

📊 实验亮点

实验结果表明，SMoT在24点游戏和出租车导航强化学习游戏中均取得了显著的性能提升。在24点游戏中，SMoT的成功率明显高于基线方法。在出租车导航游戏中，SMoT能够更快地学会最优策略，并取得更高的奖励。具体的性能数据和提升幅度在摘要中未给出，需要查阅论文全文。

🎯 应用场景

SMoT方法具有广泛的应用前景，可以应用于各种需要探索和推理的领域，例如游戏AI、机器人导航、自动驾驶、智能规划等。通过记录和复用以往的经验，SMoT可以显著提高智能体在复杂环境中的适应性和问题解决能力，降低开发成本，并加速智能体的学习过程。未来，SMoT还可以与其他技术相结合，例如强化学习、模仿学习等，以进一步提升其性能。

📄 摘要（原文）

Current Large Language Model-based agents reason within an exploration-evaluation framework, navigating problem-solving processes in a tree-like manner. However, these methods often neglect successful reasoning trajectories once a problem is resolved, leading to inefficient use of these trajectories for future analogous problems. To address this inefficiency, we adopt a state machine to record experience derived from previous reasoning trajectories. Within the state machine, states represent decomposed sub-problems, while state transitions reflect the dependencies among sub-problems. The state machine records both successful and failed trajectories. Utilizing the experience from the state machine, our proposed State Machine of Thoughts (SMoT) selects the most optimal sub-solutions and avoids incorrect ones. Our experiments show that SMoT can significantly improve problem-solving abilities in two exploration-intensive problems: the 24-point game and a taxi navigation reinforcement learning game.