title: ToolChain*: Efficient Action Space Navigation in Large Language Models
    with A* Search
summary: 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.
paper_authors._id: 6535eaafd434308ba47cdaae
paper_authors.name: Yuchen Zhuang
paper_authors.status: extracted_confirmed
paper_authors.statusLastChangedAt: 2023-10-23T18:29:44.269Z
paper_authors._id: 6471bddd609ae9f56368f132
paper_authors.avatarUrl: /avatars/71a80127a01e662ab2790de0511326b6.svg
paper_authors.fullname: Yuchen Zhuang
paper_authors.type: user
paper_authors.user: yczhuang
paper_authors._id: 6535eaafd434308ba47cdaaf
paper_authors.name: Xiang Chen
paper_authors._id: 6535eaafd434308ba47cdab0
paper_authors.name: Tong Yu
paper_authors._id: 6535eaafd434308ba47cdab1
paper_authors.name: Saayan Mitra
paper_authors._id: 6535eaafd434308ba47cdab2
paper_authors.name: Victor Bursztyn
paper_authors._id: 6535eaafd434308ba47cdab3
paper_authors.name: Ryan A. Rossi
paper_authors._id: 6535eaafd434308ba47cdab4
paper_authors.name: Somdeb Sarkhel
paper_authors._id: 6535eaafd434308ba47cdab5
paper_authors.name: Chao Zhang
paper_title: ToolChain*: Efficient Action Space Navigation in Large Language Models
    with A* Search
paper_summary: 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.
paper_ai_keywords: large language models LLM-based autonomous agents functional APIs API function calls action space ToolChain* tree search-based planning algorithm decision tree A* search algorithm task-specific cost function high-cost branches solution plan