ToolChain: Efficient Action Space Navigation in Large Language Models with A Search

📄 arXiv: 2310.13227v1 📥 PDF

作者: Yuchen Zhuang, Xiang Chen, Tong Yu, Saayan Mitra, Victor Bursztyn, Ryan A. Rossi, Somdeb Sarkhel, Chao Zhang

分类: cs.CL, cs.AI, cs.LG

发布日期: 2023-10-20

💡 一句话要点

提出ToolChain*以解决大语言模型中的动作空间导航问题

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 大语言模型 动作空间导航 A*搜索 决策树 规划算法 自动化工具使用 智能助手

📋 核心要点

  1. 现有方法在广泛的动作空间中面临单向探索的挑战，容易陷入局部最优解，或因遍历所有潜在动作而导致效率低下。
  2. 本文提出ToolChain，一种基于树搜索的高效规划算法，将动作空间构建为决策树，并结合A搜索算法进行高效导航。
  3. ToolChain*在多个工具使用和推理任务上表现优异，平均超越最先进的基线3.1%和3.5%，同时时间消耗显著减少。

📝 摘要（中文）

大型语言模型（LLMs）在解决复杂现实问题中展现了强大的决策和规划能力。基于LLM的自主代理能够与多种工具（如功能API）进行交互，并生成逐步执行API函数调用的解决方案。然而，现有方法在广泛的动作空间中面临单向探索的挑战，容易陷入局部最优解，或因遍历所有潜在动作而导致效率低下。为了解决这些问题，本文提出了ToolChain，一种基于树搜索的高效规划算法。该算法将整个动作空间构建为决策树，通过结合A搜索算法和任务特定的成本函数设计，有效修剪高成本分支，识别出最低成本的有效路径。大量实验表明，ToolChain*在广泛的动作空间中有效平衡了探索与利用，平均在规划和推理任务上超越了最先进的基线3.1%和3.5%，同时所需时间分别减少了7.35倍和2.31倍。

🔬 方法详解

问题定义：本文旨在解决大型语言模型在复杂任务中动作空间导航效率低下的问题。现有方法往往在广泛的动作空间中无法有效探索，导致性能瓶颈。

核心思路：ToolChain通过将整个动作空间视为决策树，利用A搜索算法进行高效的路径规划，旨在快速找到低成本的有效解决方案。

技术框架：该方法的整体架构包括决策树构建、A*搜索算法应用和任务特定成本函数设计。每个节点代表一个可能的API函数调用，算法通过修剪高成本分支来优化搜索过程。

关键创新：ToolChain的主要创新在于将A搜索算法与任务特定的成本函数相结合，能够有效地修剪不必要的高成本路径，从而提高搜索效率。与现有方法相比，它在探索和利用之间实现了更好的平衡。

关键设计：在设计中，成本函数根据任务需求进行定制，确保算法能够快速识别出最优路径。此外，算法的树结构设计使得每一步的决策都能有效减少搜索空间。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果显示，ToolChain*在规划和推理任务上平均超越了最先进的基线3.1%和3.5%，同时在时间消耗上分别减少了7.35倍和2.31倍，展现出显著的性能提升。

🎯 应用场景

该研究的潜在应用领域包括自动化工具使用、智能助手和复杂决策支持系统。通过提高大语言模型在复杂任务中的规划效率，ToolChain*能够在实际应用中显著提升任务完成的速度和准确性，具有广泛的实际价值和未来影响。

📄 摘要（原文）

Large language models (LLMs) have demonstrated powerful decision-making and planning capabilities in solving complicated real-world problems. LLM-based autonomous agents can interact with diverse tools (e.g., functional APIs) and generate solution plans that execute a series of API function calls in a step-by-step manner. The multitude of candidate API function calls significantly expands the action space, amplifying the critical need for efficient action space navigation. However, existing methods either struggle with unidirectional exploration in expansive action spaces, trapped into a locally optimal solution, or suffer from exhaustively traversing all potential actions, causing inefficient navigation. To address these issues, we propose ToolChain, an efficient tree search-based planning algorithm for LLM-based agents. It formulates the entire action space as a decision tree, where each node represents a possible API function call involved in a solution plan. By incorporating the A search algorithm with task-specific cost function design, it efficiently prunes high-cost branches that may involve incorrect actions, identifying the most low-cost valid path as the solution. Extensive experiments on multiple tool-use and reasoning tasks demonstrate that ToolChain* efficiently balances exploration and exploitation within an expansive action space. It outperforms state-of-the-art baselines on planning and reasoning tasks by 3.1% and 3.5% on average while requiring 7.35x and 2.31x less time, respectively.