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

• URL: http://arxiv.org/abs/2310.13227v1
• Date: Fri, 20 Oct 2023 02:24:35 GMT
• Title: ToolChain*: Efficient Action Space Navigation in Large Language Models with A* Search
• Authors: Yuchen Zhuang, Xiang Chen, Tong Yu, Saayan Mitra, Victor Bursztyn, Ryan A. Rossi, Somdeb Sarkhel, Chao Zhang
• Abstract summary: Large language models (LLMs) have demonstrated powerful decision-making and planning capabilities. 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.
• Score: 36.142986105945894
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• DynaAct: Large Language Model Reasoning with Dynamic Action Spaces [58.298135359318024]
  We propose a novel framework named textscDynaAct for automatically constructing a compact action space.<n>Our approach significantly improves overall performance, while maintaining efficient inference without introducing substantial latency.
  arXiv  Detail & Related papers  (2025-11-11T09:47:13Z)
• AgentSwift: Efficient LLM Agent Design via Value-guided Hierarchical Search [58.98450205734779]
  Large language model (LLM) agents have demonstrated strong capabilities across diverse domains.<n>Existing agent search methods suffer from three major limitations.<n>We introduce a comprehensive framework to address these challenges.
  arXiv  Detail & Related papers  (2025-06-06T12:07:23Z)
• Scaling Autonomous Agents via Automatic Reward Modeling And Planning [52.39395405893965]
  Large language models (LLMs) have demonstrated remarkable capabilities across a range of tasks. However, they still struggle with problems requiring multi-step decision-making and environmental feedback. We propose a framework that can automatically learn a reward model from the environment without human annotations.
  arXiv  Detail & Related papers  (2025-02-17T18:49:25Z)
• Semantic Exploration with Adaptive Gating for Efficient Problem Solving with Language Models [8.295475330195993]
  We propose Semantic Exploration with Adaptive Gating (SEAG) to explore semantically identical paths.<n>SEAG significantly improves accuracy by 4.3% on average while requiring only 31% of computational costs.<n>Our code is available at https://github.com/ml-postech/SEAG-semantic-exploration-with-adaptive-gating.
  arXiv  Detail & Related papers  (2025-01-10T07:02:43Z)
• Spatial Reasoning and Planning for Deep Embodied Agents [2.7195102129095003]
  This thesis explores the development of data-driven techniques for spatial reasoning and planning tasks. It focuses on enhancing learning efficiency, interpretability, and transferability across novel scenarios.
  arXiv  Detail & Related papers  (2024-09-28T23:05:56Z)
• Octo-planner: On-device Language Model for Planner-Action Agents [19.627197141903505]
  Planner-Action framework separates planning and action execution into two distinct components. Agent first responds to user queries by decomposing tasks into a sequence of sub-steps, which are then executed by the action agent. We employ model fine-tuning instead of in-context learning, reducing computational costs and energy consumption.
  arXiv  Detail & Related papers  (2024-06-26T05:40:10Z)
• LLM-A*: Large Language Model Enhanced Incremental Heuristic Search on Path Planning [91.95362946266577]
  Path planning is a fundamental scientific problem in robotics and autonomous navigation. Traditional algorithms like A* and its variants are capable of ensuring path validity but suffer from significant computational and memory inefficiencies as the state space grows. We propose a new LLM based route planning method that synergistically combines the precise pathfinding capabilities of A* with the global reasoning capability of LLMs. This hybrid approach aims to enhance pathfinding efficiency in terms of time and space complexity while maintaining the integrity of path validity, especially in large-scale scenarios.
  arXiv  Detail & Related papers  (2024-06-20T01:24:30Z)
• From Summary to Action: Enhancing Large Language Models for Complex Tasks with Open World APIs [62.496139001509114]
  We introduce a novel tool invocation pipeline designed to control massive real-world APIs. This pipeline mirrors the human task-solving process, addressing complicated real-life user queries. Empirical evaluations of our Sum2Act pipeline on the ToolBench benchmark show significant performance improvements.
  arXiv  Detail & Related papers  (2024-02-28T08:42:23Z)
• When is Tree Search Useful for LLM Planning? It Depends on the Discriminator [15.75807429396126]
  Large language models (LLMs) solve multi-step problems under a language agent framework with three components: a generator, a discriminator, and a planning method. We present a comprehensive analysis of how discrimination accuracy affects the overall performance of agents when using advanced planning methods.
  arXiv  Detail & Related papers  (2024-02-16T18:45:58Z)
• ControlLLM: Augment Language Models with Tools by Searching on Graphs [97.62758830255002]
  We present ControlLLM, a novel framework that enables large language models (LLMs) to utilize multi-modal tools for solving real-world tasks. Our framework comprises three key components: (1) a textittask decomposer that breaks down a complex task into clear subtasks with well-defined inputs and outputs; (2) a textitThoughts-on-Graph (ToG) paradigm that searches the optimal solution path on a pre-built tool graph; and (3) an textitexecution engine with a rich toolbox that interprets the solution path and runs the
  arXiv  Detail & Related papers  (2023-10-26T21:57:21Z)
• Autonomous Tree-search Ability of Large Language Models [58.68735916408101]
  Large Language Models have excelled in remarkable reasoning capabilities with advanced prompting techniques. Recent works propose to utilize external programs to define search logic, such that LLMs can perform passive tree search to solve more challenging reasoning tasks. We propose a new concept called autonomous tree-search ability of LLM, which can automatically generate a response containing search trajectories for the correct answer.
  arXiv  Detail & Related papers  (2023-10-14T14:14:38Z)
• AI planning in the imagination: High-level planning on learned abstract search spaces [68.75684174531962]
  We propose a new method, called PiZero, that gives an agent the ability to plan in an abstract search space that the agent learns during training. We evaluate our method on multiple domains, including the traveling salesman problem, Sokoban, 2048, the facility location problem, and Pacman.
  arXiv  Detail & Related papers  (2023-08-16T22:47:16Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination. We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
  arXiv  Detail & Related papers  (2020-05-27T01:10:41Z)
• Flexible and Efficient Long-Range Planning Through Curious Exploration [13.260508939271764]
  We show that the Curious Sample Planner can efficiently discover temporally-extended plans for solving a wide range of physically realistic 3D tasks. In contrast, standard planning and learning methods often fail to solve these tasks at all or do so only with a huge and highly variable number of training samples.
  arXiv  Detail & Related papers  (2020-04-22T21:47:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.