PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2310.13227v1cs.CLcs.AIcs.LG

TL;DR

Large API action spaces make globally effective planning difficult, while existing methods can explore too narrowly or search inefficiently. ToolChain* uses cost-guided A* tree search, and the paper reports stronger planning and reasoning performance alongside faster search than existing approaches.

  • Problem

    LLM agents must plan sequences of API calls across large action spaces, but existing approaches can propagate errors, explore narrowly, or search inefficiently.

    Source: §1 · pp. 1–2

  • Method

    ToolChain* formulates tool-use planning as a decision tree and uses task-specific A* costs to prioritize paths and expand one step at a time.

    Source: §1 · p. 2, §3.1 · pp. 3–4

  • Results

    ToolChain* surpasses open-/closed-loop and tree-search baselines on complex multi-step planning and reasoning tasks, and the paper reports a more efficient search strategy than other tree-search agents.

    Source: §4.4 · pp. 8–9

  • Takeaways & Limitations

    The paper presents ToolChain* as a generalizable framework for planning and reasoning with closed- and open-source LLMs that balances exploration and exploitation.

    Source: §6 · p. 10

    Although more efficient than other tree-search methods and comparable to closed-loop systems, ToolChain* remains less efficient than open-loop systems.

    Source: A BROADER IMPACTS AND LIMITATIONS · p. 13

Abstract

from arXiv · show

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.

1 INTRODUCTION

LLM agents must choose API-call sequences from large action spaces, while existing approaches face limited exploration, error propagation, or costly exhaustive search. ToolChain* uses cost-guided A* tree search to navigate this space more efficiently.

1 INTRODUCTION

  • LLM agents must select sequential API calls from hundreds of candidates, making globally optimal planning challenging.Open-loop agents plan without execution feedback, while closed-loop methods adapt using environmental feedback.Source: §1 · p. 1
  • Unidirectional methods risk error propagation and limited exploration, while DFS and MCTS can search inefficiently by traversing nearly all potential actions.Figure 1 contrasts one-direction exploration with broad tree-search branching; ToolChain* is presented as an efficient tree-search method.Source: §1 · p. 2, Figure 1 · p. 2
  • ToolChain* represents API-call plans as a decision tree and uses task-specific costs to prioritize promising paths and leave costly, potentially erroneous branches unexplored.Its A* search combines current-path and estimated future costs, expanding only the next step rather than using multi-step rollouts.Source: §1 · p. 2
  • The paper presents ToolChain* as an A*-like tree-search algorithm intended to expand the search space while balancing exploration and exploitation.Its stated contributions include mitigating error propagation and accelerating navigation of expansive action trees.Source: §1 · p. 2

2 PRELIMINARIES

The preliminaries frame tool use as planning API-call sequences from a task description and review tree search and MCTS. They contrast MCTS rollouts with ToolChain*'s cost-guided A* expansion.

2 PRELIMINARIES

  • An LLM agent receives a task description and candidate APIs, then produces an ordered sequence of calls whose execution yields the final output.The plan is sampled using API definitions and demonstration examples.Source: §2 · pp. 2–3
  • Tree search represents actions as nodes on paths through states, expands candidate child actions, and seeks a path with high value or low cost.ToolChain* is identified as a tree-search method.Source: §2 · p. 3
  • MCTS selects and expands nodes, then uses LLM rollouts to simulate actions until a terminal state and back-propagates the resulting value.The rollout can require multiple LLM calls.Source: §2 · p. 3
  • ToolChain* uses A* costs g(n) and h(n) to select next actions with a single LLM call, avoiding MCTS's multi-step rollout procedure.Figure 2 contrasts one-step, cost-guided expansion with MCTS.Source: §2 · p. 3, Figure 2 · p. 3

3 TOOLCHAIN∗: A TREE SEARCH PERSPECTIVE ON EXTERNAL TOOL USE

ToolChain* frames API-call planning as best-first search over a decision tree, using cumulative and estimated future costs to guide the search toward a valid solution path.

3.1 OVERVIEW

  • ToolChain* represents the action space as a tree whose nodes encode actions and associated states, and uses A*-style costs to choose which paths to extend.The framework iterates through selection, expansion, and cost updates.Source: §3 · p. 3, §3.1 · pp. 3–5
  • Each cycle selects the lowest-cost frontier leaf, expands it into k LLM-proposed next actions, then updates frontier nodes and their costs.The frontier contains unexplored leaf nodes; the selected node is the one with the lowest estimated cost.Source: §3.1 · p. 4

3.2 DESIGN OF CUMULATIVE COST g(n)

  • Cumulative cost sums per-action complements of a geometric-mean score combining long-term-memory plan similarity and self-consistency frequency of distinct next actions.Plan similarity uses the highest normalized longest-common-subsequence score against stored successful plans; self-consistency uses the frequencies of distinct sampled actions.Source: §3.2 · p. 5

3.3 DESIGN OF FUTURE COST h(n)

  • Future cost combines a memory-based heuristic from the lexically closest action with an LLM imagination score based on how much of the current path appears in an imagined plan.The imagined plan is used to estimate how many steps remain to complete the task.Source: §3.3 · pp. 5–6

4 EXPERIMENTS

ToolChain* is evaluated on multi-step tool-use and mathematical reasoning tasks, with experiments examining its performance, efficiency, and search behavior. Across these settings, it outperforms baselines and balances exploration with efficiency.

4.3 MATH REASONING: GSM8K

  • ToolChain* is also evaluated on GSM8K and its hard ToolQA subset to test generalization to mathematical reasoning without tool interaction.The paper reports that it is among the most efficient tree-search baselines on GSM8K, with efficiency comparable to closed-loop systems without a tree structure.Source: §4 · p. 6, §4.3 · p. 8, Figure 5 · p. 8

4.1 EXPERIMENTAL SETUP

  • The evaluation covers four ToolBench tool-use environments selected for large action spaces and deep solution paths, plus GSM8K mathematical reasoning.For ToolBench, comparisons include open-loop, closed-loop, and tree-search systems; math evaluations use a similar set but exclude feedback-dependent methods and compare with Chain-of-Thought and Self-Consistency.Source: §4.1 · p. 6, §4 · p. 6

4.2 TOOL USE: TOOLBENCH

  • 3.8% higher average success rate than AdaPlanner; ToolChain* also surpasses state-of-the-art baselines by 3.7% with GPT-3.5-turbo and 2.5% with GPT-4 across nearly all ToolBench datasets.It also surpasses MCTS and can exploit a better plan within the same exploration budgets by prioritizing promising branches.Source: §4.2 · p. 7
  • ToolChain* generates the correct “shower” action plan in the Virtual Home case study, while ReAct gets trapped in a locally optimal “soap” solution.The case illustrates how a tree-based action space broadens exploration in complex multi-step planning.Source: §4.2 · p. 7, Figure 4 · p. 7
  • 37.2% faster than Tree-of-Thoughts (BFS) on ToolBench, and 415.84% faster than MCTS, with search expanding only the immediate next action rather than rolling out entire plans.The reported efficiency gain over Tree-of-Thoughts (BFS) may stem from the cost function's navigation of promising paths.Source: §4.2 · p. 7, Figure 5 · p. 8
  • Removing either the cumulative or future cost causes a marked success-rate decline; relying only on future cost drops performance by 28.2% and yields a greedy shortest-plan strategy.The ablations indicate that components of both cost functions contribute to performance.Source: §4.2 · p. 7, Table 2 · p. 7

4.3 MATH REASONING: GSM8K

  • ToolChain* outperforms all baselines on both GSM8K and its ToolQA hard subset, with greater advantages on the harder questions.The passage attributes the stronger advantage on hard questions to their complex reasoning, many intermediate steps, and multiple solution paths.Source: §4.3 · p. 8, Table 3 · p. 8

4.4 DISCUSSION: EMPIRICAL ANALYSIS

  • Experiments across planning and reasoning tasks are reported to address error propagation and constrained exploration, while the discussion identifies an effectiveness–efficiency trade-off in applying tree search to complex tool use.The discussion also summarizes evidence that ToolChain* broadens exploration, accelerates search, generalizes across tasks, and balances search depth with solution-path quality.Source: §4.4 · pp. 8–9

5 RELATED WORKS

Prior work uses LLMs for tool use and explores search methods for reasoning and planning. ToolChain* is positioned as combining A* search with LLM reasoning to navigate expansive action spaces efficiently.

LLMs for Tool Use

  • Tool-use agents can augment LLMs with factual, multimodal, computational, coding, and domain-specific capabilities, but many methods focus on individual scenarios or use human-made heuristic orderings.Growing numbers of API functions and action steps expand the action space and diminish the effectiveness of those approaches.Source: §5 · p. 9

LLMs with Search Algorithms

  • Search-based LLM methods include sampling multiple reasoning chains, building explanation trees, beam search, MCTS, and depth- or breadth-first tree search.The passage describes a trade-off between efficiently exploring expansive action spaces and exploiting globally optimal solutions.Source: §5 · p. 9
  • ToolChain* is proposed to combine A* search with LLM reasoning as an alternative to exhaustive exploration like MCTS.Figure 6 is identified as a scaling analysis of performance and running time as step limitations increase.Source: §5 · p. 9, Figure 6 · p. 9

6 CONCLUSION

ToolChain* is an A* tree-search planning algorithm for augmenting LLMs with external tools on complex planning and reasoning tasks.

6 CONCLUSION

  • ToolChain* formulates the action space as a decision tree to mitigate error propagation and expand search, and it accelerates search relative to other tree-search methods.The paper presents it as a generalizable framework across planning and reasoning tasks with closed- and open-source LLMs, balancing exploration and exploitation.Source: §6 · p. 10

A BROADER IMPACTS AND LIMITATIONS

ToolChain* is presented as a flexible planning framework for tool-use and complex decision-making, but it remains less efficient than open-loop systems. The paper reports its hardware and parameter settings and identifies tree-structure and search-strategy refinement as future work.

A BROADER IMPACTS AND LIMITATIONS

  • ToolChain* remains less efficient than open-loop systems, motivating future refinement of its tree structure and search strategy.The authors say its efficiency exceeds other tree-search methods and is comparable to closed-loop systems.Source: A BROADER IMPACTS AND LIMITATIONS · p. 13

B.1 HARDWARE INFORMATION

  • Experiments used an Intel Xeon Platinum 8275CL CPU and an NVIDIA A100 SXM4 80 GB GPU.The stated software environment was Python 3.8.13.Source: §B.1 · p. 14

B.2 PARAMETER CONFIGURATION

  • ToolChain* uses α = β = 0.5, k = 10, and a default maximum step limit T = 20.The authors also specify model-specific solution-length limits and temperature settings, and say code and data await internal release approval.Source: §B.2 · p. 14

B.3 TASK SETUP FOR TOOLBENCH

The setup defines API calls and reasoning steps as search-tree nodes for tool-use and math tasks. The accompanying background distinguishes open-loop planning from feedback-driven closed-loop refinement and positions tree search as a way to retain multiple branches.

B.3 TASK SETUP FOR TOOLBENCH

  • ToolBench planning treats each decision-tree node as an API call and evaluates task success across four environments using task-specific metrics.Home Search, Trip Booking, and Google Sheets use success rate; Virtual Home uses the proportion of scripts reaching the correct end state or completing the task.Source: §B.3 · p. 14

B.4 TASK SETUP FOR GSM8K

  • For GSM8K, reasoning steps become tree nodes, with self-consistency frequency as cumulative score and LLM imagination as future score.The setup covers the full dataset and a hard-question subset from ToolQA; the latter is used because long-term-memory seed data is absent.Source: §B.4 · p. 14

C LLM-BASED AGENTS

  • Table 4 compares tool-use agents by tool basics, planning ability, step and plan modification, and traceback capability.The related-work overview groups LLM agents into open-loop, closed-loop, and tree-search approaches.Source: C LLM-BASED AGENTS · p. 14, Table 4 · p. 15

C.1 OPEN-LOOP SYSTEM

  • Open-loop systems generate a complete plan for execution, but their predetermined single path leaves other potential plans unexplored.Examples include Chain-of-Thought and Zero-Shot Planner for reasoning, least-to-most prompting for decomposition, and HuggingGPT and Chameleon for tool-use plans.Source: §C.1 · pp. 14–15

C.2 CLOSED-LOOP SYSTEM

  • Closed-loop systems use environment observations to refine either the next action or the entire future plan, but lack of traceback leaves much of the decision space unexplored.ToolChain* is introduced as tree search that records multiple branches in the decision space.Source: §C.2 · pp. 15–16

D.1 DATASET DETAILS

The evaluation spans four ToolBench tool-use environments and GSM8K math reasoning, with baselines covering open-loop, closed-loop, and tree-search approaches. The datasets vary in task structure and available API functions.

D.1 DATASET DETAILS

  • The ToolBench evaluation includes Home Search and Trip Booking, with 15 and 20 API functions, respectively.Trip Booking adds more advanced dependencies between function calls than Home Search.Source: §D.1 · p. 16
  • Google Sheets tests worksheet manipulation, while Virtual Home requires action sequences using 40 household-simulator functions.Virtual Home functions can take up to two arguments representing household objects.Source: §D.1 · pp. 16–17
  • GSM8K evaluation measures final-answer accuracy on grade-school math problems and includes a hard subset sampled from ChatGPT error cases.The hard questions are curated by ToolQA.Source: §D.1 · p. 17

D.2 BASELINE DETAILS

  • The baselines include GPT and Chain-of-Thought prompting, alongside Self-Consistency, which samples diverse reasoning paths and selects the most coherent answer.GPT is a four-shot open-loop system; Chain-of-Thought generates intermediate reasoning steps, and Self-Consistency marginalizes sampled trajectories.Source: §D.2 · p. 17
  • ReAct and AdaPlanner represent closed-loop baselines, using tool feedback for interleaved reasoning and action or adaptive plan refinement.AdaPlanner uses in-plan and out-of-plan refinement strategies.Source: §D.2 · p. 17
  • Tree-of-Thoughts and MCTS provide tree-search baselines, exploring reasoning trajectories with self-assessment or task-specific rewards.MCTS uses the LLM as both a world model and reasoning agent.Source: §D.2 · p. 17

D.3 ADDITIONAL ANALYSIS ON TOOLBENCH

ToolBench results differ by environment: feedback-rich tasks favor closed-loop methods, while larger action spaces favor tree search. Case studies show ToolChain* explores alternatives and revises faulty paths, and efficiency analyses report advantages over other tree-search methods.

D.3 ADDITIONAL ANALYSIS ON TOOLBENCH

  • Closed-loop methods typically perform better on Home Search and Trip Booking, whereas tree-search methods perform better on Google Sheets and Virtual Home.The paper attributes this difference to precise error feedback in the first pair and larger action spaces in the latter pair: 108 and 40 API functions versus 15 and 20.Source: §D.3 · pp. 17–18

D.4 CASE STUDIES

  • In GSM8K case studies, ToolChain* explores multiple paths and raises costs after incorrect actions, enabling revision of prior actions and alternatives to faulty paths.Figures 7 and 8 contrast its broader exploration with Chain-of-Thought's primarily one-directional search; this mitigates error propagation along linear or unidirectional plans.Source: §D.4 · pp. 18–19, Figure 7 · p. 18, Figure 8 · p. 19

D.5 EFFICIENCY DETAILS

  • ToolChain* runs faster than Tree-of-Thoughts BFS in GPT-4 tool-use evaluation and is more efficient than other tree-search algorithms on GSM8K.Figure 9 reports average running time over dataset instances and average valid actions for GSM8K; efficiency is close to closed-loop systems without a tree structure.Source: §D.5 · p. 19, Figure 9 · p. 19
  • In Home Search scaling tests, ToT-DFS, ToT-BFS, and MCTS have relatively low success rates and long running times compared with ToolChain*.The comparison examines performance and running time as step limits increase; the paper describes ToolChain* as converging quickly on time efficiency and high-quality solutions.Source: §D.5 · pp. 19–20, Figure 10 · p. 20

D.6 ABLATION STUDIES DETAILS

The ablations show that both cumulative and future cost functions contribute to ToolChain* performance, with non-heuristic components generally having greater impact. Removing either entire cost changes the search behavior and reduces success.

D.6 ABLATION STUDIES DETAILS

  • 6.8% average drop in success rate occurs without non-heuristic components, versus 3.3% without heuristic components.The heuristic function matters more when environments provide high-quality seed data, such as Virtual Home.Source: §D.6 · p. 20
  • Removing either heuristic or non-heuristic elements from the cumulative or future cost functions reduces performance.The ablations indicate that each cost-function element helps guide decision-tree search.Source: §D.6 · p. 20
  • 28.2% performance drop follows removing cumulative cost, leaving future cost alone and reducing ToolChain* to a greedy shortest-plan strategy.The resulting strategy favors plans with the fewest actions.Source: §D.6 · p. 20
  • Using cumulative cost alone makes ToolChain* behave like breadth-first search, with similar performance outcomes.Removing either the entire cumulative or future cost causes a marked success-rate decline.Source: §D.6 · p. 20

E ADDITIONAL DATASET: SCIENCE QA

ToolChain* was evaluated as a plug-and-play replacement for Chameleon’s planner on ScienceQA. Its accuracy gain was modest, which the authors attribute primarily to rigid tool-call logic in the dataset.

E ADDITIONAL DATASET: SCIENCE QA

  • ScienceQA covers multimodal questions across scientific topics and requires tools such as image captioning, text detection, retrieval, online search, and visual reasoning.ToolChain* replaced Chameleon’s original naive LLM-based planner for this evaluation.Source: E ADDITIONAL DATASET: SCIENCE QA · p. 20
  • 0.8% accuracy improvement over Chameleon was achieved by ToolChain* with GPT-3.5-turbo on ScienceQA.The supplied table caption identifies additional ScienceQA results based on GPT-3.5-turbo.Source: Table 6 · p. 20, E ADDITIONAL DATASET: SCIENCE QA · p. 21
  • The accuracy gain was limited primarily because the dataset’s logic for calling different tools is rigid.Source: E ADDITIONAL DATASET: SCIENCE QA · p. 21

F OPEN-SOURCE LLMS

On Virtual Home, ToolChain* improved average success rates when applied to fine-tuned open-source LLaMA-2 models. The models were trained on autoregressively decomposed plan steps rather than entire plans.

F OPEN-SOURCE LLMS

  • 4.0% average improvement in success rate follows applying ToolChain* to StepLLaMA-2 on Virtual Home.Table 7 reports success-rate results for LLaMA-2 7B and 13B models.Source: Table 7 · p. 21, F OPEN-SOURCE LLMS · p. 21
  • Training plans autoregressively increases the instruction-solution dataset from approximately 500 to approximately 4,500 examples.Each instruction includes the task query and previous actions, with the next action as the solution; the resulting pairs fine-tune LLaMA-2 7B and 13B models.Source: F OPEN-SOURCE LLMS · p. 21
  • Virtual Home evaluation reports Executable, Success, and Success (E), which measures success only among executable plans.Executable is the proportion of plans that can run without violating rules; Success is the proportion reaching the correct final state.Source: F OPEN-SOURCE LLMS · p. 21

Related papers

Loading 2310.13227v1…