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
Venue: ICLR 2024 poster (2024)
Keywords: Large Language Model
Tool Use
Tree Search
A* Search
Primary area: general machine learning (i.e., none of the above)

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.

Published as a conference paper at ICLR 2024
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' Georgia Institute of Technology' Adobe Research"
cozhuangggateon edu, (xiangche, t smitra]@adobe com fscaresbu, zyrossi, sarkhel Baccheelladobb..coo com, chaozhang@gatech. edu
ABSTRACT
Large language models (LLMs) have demonstrated powerful decision-making and planning capabilities in solving complicated real-world problems. LLM-based au- tonomous agents can interact with diverse tools (c.g., functional APIs) and generate solution plans that execute 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 ac- tion 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 a decision tree, where each node represents a possible API function call involved 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 outper- forms state-of- sate-of-theeart baselines on planning and reasoning tasks by 3.1% % and 3.5% on average while requiring 7.35x and 2.31x less time, respectively.
solution
INTRODUCTION
Large language models (LLMs), such GPT (Radford et al., 2018; 2019; Brown et al., 2020; OpenAL, 2023) and PaLM (Chowdhery et al., 2022; Anil et al., 2023), have exhibited remarkable capabilities of reasoning and cestruction-ollowiinn
across wide range of tasks (Huang & Chang, 2023). Recently, instructing LLMs to utilize external tools for complex real-world problems has emerged as a topic of growing importance (Hao et al., 2023b; Zhang et al., 2023: Zhuang et al., 2023; Yang et al., 2023b; Schick et al., 2023; Lu et al., 2023). For complicated tasks, LLM-bbsed autonomous agents integrate LLMs with various external tools (APIs), generating solutions that involve intermediate reasoning steps (Schick et al., 2023; Lu et al., 2023; Patil et al., 2023; Qin et al., 2023b). Given a problem description, the goal of an agent is determine chain of API function calls that can be executed sequentially toward a valid solution. However, given an action space hundreds of candidate API functions, each comprised of various function names and parameters available every planning step, searching for a globally optimal solution becomes highly challenging.
Existing methods that leverage LLMs autonomous agents for broadly classified into four categories (Figure 1): (1) open-loop methods (Wei et al., 2022; Zhou et al., 2022: Huang et al., 2022a; Shen et al., 2023: Lu al., 2023) generate a complete plan for problem- solving without any adaptation during the execution; (2) greedy closed-loop methods (Yao et al., 2023b; Jang, 2023; Huang et al., 2022b; Kim et al., 2023; Liang et al., 2022) leverage environmental feedback to greedily determine the next step in the plan; and (3) closed-loop methods (Wang et al., 2023; Sun et al., 2023) incorporate environment feedback to continuously monitor system behaviors
and reasoning be
Work done during the author's internship Adobe Research.

---

Published as a conference paper at ICLR 2024
Open-Loop System (e.g., Chain-of- Thoouhgsss
Greedy Closed-Loop System (e.g., ReAct)
Closed-Loop System
Tree Search-based System
(e.gu, AdaPlanner)
(e.gu Tree of Thoughts)
Potential Actions
Explored Actions Infeasible Options
Final Output
Exploration
Execution
Figure I: A comparison of existing methods that leverage LLMs for decision from a searching space perspective. Most existing methods of (1) open-loop systems (e.g. Chain-of- Thoouhh (Wei et al., 2022)), (2) greedy closed-loop systems (e.g., ReAct (Yao et al., 2023b)), and (3) closed-loop systems (e.g., Adaplanner (Sun et al., 2023)) only explore one possible direction. This often leads to limited exploration of the entire action space. In contrast, (4) tree search-based methods (e.g., Tree-of- Tree-of-Thoughts ( (Yao et al., 2023a)) identify a valid solution path by extensively examining multiple decision space branches, covering almost every conceivable node. Our proposed ToolChain' belongs to the tree search- -hased category and improves by developing an efficient search algorithm.
and modify subsequent plans accordingly. However, such unidirectional navigation systems have two major limitations: error propagation, originating from a mistaken action and leading to faulty loop; limited exploration, despite being equipped with plan refinement strategies, most existing methods only explore a small portion of the large action space, falling into locally optimal solutions. To this end, few studies initiate exploring (4) tree search-based methods (Yao et al., 2023a; Hao et al., 2023a) for leveraging multiple reasoning paths simultaneously and evaluating branches to decide the next course of action. However, existing tree pearch-based algorithms, such as depth-fing first search (DFS) (Yao et al., 2023a) and Monte Carlo Tree Search (MCTS) (Hao et al., 2023a), require exhaustive exploration of nearly all potential actions within the entire decision space, resulting in inefficient searches for globally optimal solutions.
To address these limitations, we propose ToolChain', an efficient A search-based planning method for LLM-based agents. We formulate the tool-use planning process as a decision tree, where each node represents potential API call for given step. Aligned with the traditional A* search algorithm, the proposed ToolChain' determines which paths to extend based on both the cost of the current path and an estimated future cost required for completing the current plan. With task-specific cost functions, erroneous actions will be penalized and mitigated, as these actions cause additional costs when propagated along the path, leading the path to be progressively de-pri de-prioritized and left unexpanded over iterations. In addition, unlike the simulation stage in MCTS, which requires multiple steps to simulate until a terminal state during rollout, the future cost estimation ToolChain' enables expansion of only the next step. With efficient node expansion, ToolChain' effectively searches for globally optimal solutions within a manageable number of steps.
Our main contributions algorithm, to develop autonomous LLM-based agents for complex planning and reasoning tasks; (2) ToolChain" x formulates the action space as decision tree, effectively mitigating error propagation and expanding search space; and (3) ToolChain" significantly accelerates LL-M-based agents in navigating expansive action tree spaces, striking a balance between exploring unvisited actions and exploiting global optimal solutions.
as follows: (1) We propose ToolChain', novel AI-like search
2 PRELIMINARIES
Problem Formulation. Leveraging LLMs as agents for problem solving can be conceptualized as a planning process. For initialization, the LLM agent is augmented with access to pool of m candidate API functions, denoted as AA = {APL,, API,, ... API, ), along with a natural language task description g E g from the task space G. The objective of the LLM agent is to translate the task description g into an ordered sequence of T2 API function calls Pa = (ag. 41 ... ,ay, J. Specifically, considering the task description y as the initial state 8p, sample the plan Py by prompting the L.M
2

---

Published as a conference paper at ICLR 2024
agent with the API definitions I and demonstration samples D as: Py p(au, a1,-.. .r, |su; I, D) I D (AAT)), where (.)) is probability simplex function. The final output is derived after executing the entire plan π (y)s0, a1 ",,""",, , where TT-) indicates plan executor.
Tree Search-Based Systems. Tree search methods frame a planning problem as search over decision tree, where each node represents an action ap, accompanied by state 8, E S indicating valid path from the initial state the current action. When exploring the tree space, tree search approaches expand k potential child nodes (n) of the current node via sampling from the potential (5) action set generated by LLMs (n)(n) p(ara(m)) Sn Sn DI,,), D), (j 1, .k) and add the new nodes
to the tree state space S = S {(8n, (ch(x)) )- With value functions for state evaluation, tree search-based methods aim to identify a path from the root node so to the leaf nodes with the highest value or lowest cost. Our proposed ToolChain' is tree search-based method.
Monte Carlo Tree Search. MCTS, which employs heuristic exploration to construct its search tree, has achieved great success decision-makee UCT (Koesis & Szepesvári, 2006), has been adopted in Hao et al. (2023a) for the development of LLM-based agents. Specifically, initiates from the root node of the task description g and moves down the tree by selecting optimal actions (child nodes) until the leaf node. Then, MCTS introduces one or multiple child nodes based on available actions provided by LLMs and identifies the most promising node From the newly expanded node n, MCTS requires LLM agents to execute simulated rollout until a terminal state is reached. Upon completing the simulation, a result is returned from all the way back to the root node, accompanied by the value function (n) to update all the scores on the selected path.
tasks, such as GO (Silver et al., 2016). Its variant,
MCTS vs. A Search. Despite the performance gains attained by MCTS in planning and reason- ing tasks, its direct application to LLM agents comes with significant execution costs. The roll- out mechanism within MCTS requires multiple LLM calls to prompt the next actions until terminal state. Furthermore, unlike two-player zero-sum games, the planning tasks essentially operate as one-player games, where value func- tions estimated by random rollouts might exhibit significant inaccuracies. To mitigate the issue, ToolChain" is proposed based more effi- cient A search algorithm. A comparison be- tween MCTS and our proposed ToolChain" is illustrated in Figure 2. Unlike MCTS, A" search necessitates only single LLM call for determining the next actions during expansion according to two cost functions, g(2), quantifying the cost of the path from the root node to n, and h(n), heuristic function estimating the cost of the most promising path from n the goal.
Q(n)
f(n)
Q(n)
g(n)
Monte Carlo Tree Search
ToolChain*
Figure 2: A comparison between MCTS and A* search in ToolChain'. Unlike MCTS, A search only requires one-step expansion guided by cost.
3 TOOLCHAIN": A TREE SEARCH PERSPECTIVE ON EXTERNAL TOOL USE
In this section, we introduce the TooIChain" * that enables LLM- -ased agents efficiently navigate the action space to identify valid solution path for problem-solving (Figure 3). First, we outline the framework of ToolChain" (Section 3.1), consisting of three iterative stages: selecting the most promising path in the explored decision tree, expanding the potential following actions along the selected path, and subsequently updating the cost functions. Within TooIChain" the cost function composed of two components: cumulative cost g(n) (Section 3.2) and future score h(n) (Section 3.3).
3.1 OVERVIEW
ToolChain' is a best-first search algorithm, efficiently guiding LLM agents in generating a sequence of API function calls as solution plan. We formulate the action space search tree T, where each node n represents an action an, accompanied by a state composed of the initial task description so and previous actions. This facilitates the translation of action sequence planning into navigation
3

---

Published as a conference paper at ICLR 2024
(a) Selection:
(b) Expansion:
(c) Update:
Pick frontier node with the
Expand the nodes with potential next steps.
Update the value functions newly added nodee in the search tree.
lowest summation cumulative cost and future cost
ToolChain" framework of three phases: (a) selection, (b) expansion, and (c) update. The dark and grey circles indicate the explored actions and the potential but unexplored ones, respectively. The blue circles represent the selected next step.
Figure 3:
task originating from the root node of the decision tree. ToolChain" starts the search tree T with single root node, corresponding the input input problem description so. At each step, selects node n from the frontiers of T (denoted as F(T)) according to the cost function. Then, it expands n with the LLM to generate
of potential i.i.d. actions {a<h(m) 1 for the next step and grows T
(5) with the generated actions. Finally, we update the actions into new nodes *ch(n) = (sn: (ch(n)) and update their cost functions accordingly. Algorithm 1 describes the procedure in detail.
Selection. Given search tree T. we denote its nodes as V(T). The frontier F(T) S V(T) con- tains all the leaf nodes T that have yet explored. Given our objective to minimize the total cost of the final solution, the optimal next node to expand would be the most promising plan part of the best solution. Assume we possess a cost func- tion oracle (n), which provides the cost of the best plan incorporating n to address the problem sp under T. Then, we can select the next node with the lowest cost: feex = arg min, (E)(T [(n). A proper design of the value function f(n) not only augments search efficiency but also aids in identi- fying globally optimal solutions.
Algorithm ToolChain'.
Input: x: input; pú large language model; T: the maximum exploring steps; T: the decision tree; F(T): the set of frontier nodes in T; [n): the cost function of node n.
Initialize T = {V, C...V... x, +
for t = 1,2, -.. do arg FFT)) f(n) // Selection (a
for i /==1 <- p(vinezt) Expansion
11,2, k do
L Add [ ( T under Nsexxt
Update f(n) for in F(T). I/ Update Output: The valid path to solve the problem arg max,e f(n).
Expansion. Once the node with the minimum cost estimation [(nn) has been selected, we expand the search tree with i potential actions for the next step. These actions are sampled from the potential action set generated by LLMs (h(()) II, (f=1, ,k), given the API definitions
} and demonstration examples D. For the generated actions or reasoning steps (m) j=1 ) we establish their corresponding nodes under node n. Contrasting with the approach in MCTS (Hao al., 2023a), which requires multiple calls to o until a terminal state during rollout, our expansion only requires single call to generate the possible actions at the next step.
Update. Denote the search tree T after expansion of node n as T'. Given that new nodes have been incorporated and the original tree structure has changed, we need to update the frontier nodes as F(T'). With the new frontier nodes n E F(T'), ) we can compute their corresponding cost functions for the next pnpettionexxpasiio-uudaat iteration.
Cost Function. We draw inspiration from A algorithm to design and update the cost function f(n). Specifically, A selects the path that minimizes f(n) ((n) h(n), where is the current node, g(n) represents the cost of the path from the start node to n, and h(n) is a heuristic function estimating the cost of the cheapest path from to the goal.
4

---

Published as a conference paper at ICLR 2024
3.2 DESIGN OF CUMULATIVE COST g(n)
During the planning process, we assess the cumulative cost of actions in the current plan and guide the planning based on the assessment. For each node the searching tree, we design a single-step value function 9t (n) ranging from 0 to 1 and formulate the cost as its complement 1 (n).. Thus, the cumulative cost of can be computed by summing up all the single-step costs of its ancestor nodes (n):): g(n) = Lieam(n) 1 ge()). More specifically, we combine two different value functions, the task-specific heuristic function from reference data (long-term memory) gr, (n) and the self-consistency frequency by LLM (n)) to compute cumulative cost g(n):
g(n) = Σ
(1 (1- (1-)))(0)) (1- 11))2(())
(I)
(E))))))).)
where a is a weight parameter for the geometric mean.
Task-Specific Heuristic Function It,1 (n.. We also maintain long-term memory with successful experiences and compute a heuristic score accordingly. The long-term memory starts from a seed set of demonstration examples provided in specific dataset and is iteratively extended with successful plans during evaluation. Each example within the long-term memory is represented as a plan my ($3.0, dy,1, ",,,."'. (g.T;) M.. The number of actions T, in the plan varies case-by- case. To leverage the successful experiences for evaluating the current plan, we compute the longest common sub-sequence (LCS) score between the current generated plan sn and each plan LCS(sn.m,)
my in the long-term memory LCS SeS__scor((s,,
m,) = mi, where L(-) indicates the length of the plan. Following this, we compute the cumulative functions as the highest LCS score [n) = max,, EM LCS_scooe sss_sceorssss my). measuring the proportion of success in the plan relative to the experiences accumulated in the long-term memory.
Self-consistency Frequency (n)). Self-consistency (Wang et al., 2022b) is an ensemble approach
that samples is i.i.d. actions at the next step (a {a=+1) 1 p(at+1 [z. ao, "i.....a)) We then select the semantically different actions from the k generated samples as the set of potential next steps. For tool-use scenarios, as the actions are strict in format of API functions and parameters, we directly construct the set with non-repeating actions. For reasoning scenarios, however, actions represent intermediate thought processes articulated in natural language. Inspired by Kuhn et al. (2022), we apply DeBERTa-large model (He et al., 2020) fine-tuned on natural language inference (NLI) dataset MNLI (Williams et al., 2018) to determine whether the two generated actions entail each other semantically. This allows us to discard actions that are semantically equivalent, only retaining those that offer distinct reasoning as potential next steps. Lastly, we consider the frequencies of different
actions in the set as their corresponding cumulative score, given by (n))(n) = # (f) = nk/k.
3.3 DESIGN OF FUTURE COST h(n)
Similar to the formulation of cumulative cost g(n), we integrate two distinct reward functions, the task sask-specific heuristic function h (m) and the Imagination Score by LLM 2 to compute h(n)::
h(n) = (1 - (n))* (1 hn))
(2)
where 3 is the geometric mean weight for future cost.
Task-Specific Heuristic Function. Similar the heuristic function in the cumulative cost (Sec- tion 3.2), we continue to leverage the long-term memory to compute the future score. From the long-term memory, we can derive the average relative position score of the action a appearing in the plans my: he, (a) = Em,e, EM { posla.m,) where pos(a, my) indicates the relative position of action in the plan my. Note that the action space can be infinite, and the long-term memory may not cover all potential actions relevant to unseen tasks. Thus, given an action node n, we compute its future score the heuristic score of the lexically closest action covered in the long-term memory: h4 (n) = h (arg max, LCS (core(n, a)).
Imagination Score by LLM. Directly querying LLMs for self-evaluatio of the future cost at the current step often yields conr-confi scores (Lin et al., 2022). To address this, we enable LLMs to imagine more concrete future steps until the target ny- However, it is worth noting that the imagined
5

---

Published as a conference paper at ICLR 2024
Table I: Main experiment results (success rate) on ToolBench, including tool use scenarios of (1)
Home Search, (2) Trip Booking, (3) Google Sheets, and (4) Virtual Home.
GPT-3,5-turbu
GPT-4
Models
Home
Trip
Google
Virtual Home
Home Search Booking
Trip
Google
Virtual Home
Average
Averago
Search Booking
Sheets
Sheets
GPT (OpenAI, 2023)
80.0
85.8
51.4
18.9
59.2
97.0
96.7
62.9
23.5
70.0
ReAct (Yao et al., 2023b)
83.0
86.7
47.1
20.5
59.3
94.0
97.5
64.3
22.7
69.6
AdaPlanner (Sun al., 2023)
90.0
87.5
55.7
20.7
63.5
97.0
97.5
66.7
27.1
72.1
ToT-DFS (Yao et al., 2023a)
82.0
81.7
53.4
21.0
59.5
95.0
96.7
62.9
24.8
69.9
ToT-BES (T=S) (Yao al., 2023a)
83.0
83.3
48.6
21.8
59.9
92.0
94.2
64.3
26.6
69.3
MCTS (Hao et al., 2023a)
85.0
86.7
62.9
24.4
64.8
96.0
94.2
66.7
31.3
72.1
TooIChain
93.0
90.8
61.4
28.6
68.5
98.0
97.5
68.6
34.5
74.7
actions may not align with the real executed actions in future plans. To this end, compute the future score as the proportion current steps present in the imagined plan, i.e., the ratio of the number between the current node n ancestors to the target node ny: (2,)(n) = [fan[=]H A higher score suggests that the imagined plan closely captures the path to the current step, indicating that fewer remaining steps are needed to accomplish the task in the imagination of LLMs.
Kan(nr) ))
4 EXPERIMENTS
In this section, we demonstrate the effectiveness and efficiency of ToolChain" through comprehensive experiments across wide range of tool-use scenarios from ToolBench (Xu et al., 2023) (Section 4.2). In addition, we conduct extensive experiments on GSM8K (Cobbe et al., 2021) (Section 4.3) to showcase the generalization of ToolChain" on pure reasoning tasks without tool interaction.
4.1 EXPERIMENTAL SETUP
Datasets. We evaluate ToolChain' on four tool-use environments in ToolBench (Xu et al., 2023) and one reasoning task in GSM8K (Cobbe et al., 10.1). For tool-use scenarios, we select environments with both vast action space comprising large number of function tools, and requirement of a deep solution path with multiple API functions (i.e. complicated tasks), including Home Search, Trip Booking, Google Sheets, and Virtual Home. Given that numerical reasoning requires multi-step computations to calculate answers, we choose GSM8K (Cobbe et al., 2021) for evaluation on math reasoning. Dataset details are available in Appendix D.I.
Baselines. For environments from ToolBench, we compare ToolChain* with the state-of-the-art LLM planning algorithms from three main categories, including open-loop systems (GPT (OpenAI, 2023)), closed-loop systems (ReAct (Yao et al., 2023b) and Adaplanner (Sun et al., 2023)), and tree maacch systems (Tree-of-Thougghs (Yao et al., 2023a) and MCTS (Hao et al., 2023a)). For mathematical reasoning problems, we employ similar set of baselines as in the tool-use tasks. However, we exclude ReAct and AdaPlanner from mathematical reasoning evaluations. This is because they heavily depend high-quality environment feedback to adjust action plans, which unavailable in the GSMSK dataset. Additionally, since the action steps in the tool-use scenarios inherently form coherent sequences, limit our comparison of ToolChain' to Chain-of- Thought (Wei et al., 2022) and Self-Consistency (Wang et al., 2022b) only for the math reasoning task, and exclude it from the ToolBench evaluations. Baseline details can be found in Appendix D.2.
4.2 TOOL USE: TOOLBENCH
We conduct experiments across four distinct planning tasks to assess the effectiveness and efficiency of 'TooCChain* tool usage. The objective is to generate a sequence API function calls to formulate solution plan for each given task. For instance, these tasks include questions requirements from users, e.g., "Could you help me find train tickets to Cape Coral?". We present the main results, visualize the case study, analyze time-wise efficiency, and discuss ablation studies within the tool-use scenarios as follows. We report the success rate as the evaluation metric. Detailed task setup for ToolBench is available in Appendix B.3.

---

Published as a conference paper at ICLR 2024
1000
6.00
Home Search
GSMBK (GPT33.5)
Ruaniig Time (in Sec)
200
Booking
5.00
ToolQA (GPT3.5)
Google Sheet
GSMBK (GP14)
600
Virtual Home
Buaning Time:
400-
TooYQA (GPT4)
400
200
200
100
GPT AdaPlane anner Roket ToolChaln TOT ToT MCTS
GPT
CoT
Sc
TeaCChann BTBFS WT
MCTS
(a) ToolBench.
(b) GSM8K.
Figure 5: Time efficiency evaluation on (a) ToolBench and (b) GSM8K. We report the average running time in seconds over all instances in the dataset. ToolChain' * achieves competitive efficiency to closed-loop systems without a tree structure and outpaces other tree sarchhbasee algorithms.
Results. Table 1 presents the main experiment results ToolBench. Our proposed ToolChain' consistently outperforms across nearly all datasets, surpassing gins of 3.7% and 2.5% with the base LLMs GPT-3.5-turbo and GPT-4, respectively. In parison with the strongest closed-loop baseline AdaPlanner, ToolChain" improves the average success rate by 3.8%. This improvement is because AdaPlanner relies heavily environmen- tal feedback, which may not always be available in the tool-use scenarios. Without such high- quality feedback, closed-loop methods tend to explore restricted trajectory within the action space, making them more susceptible to propagating errors from previous actions to future plans. Moreover, ToolChain' not only surpasses the strongest tree search-based method, MCTS, but also shows the ability to exploit better solution plan within the same exploration budgets. This is because our proposed task task-specific cost func- tion allows ToolChain' to prioritize the expan- sion of the most promising branches. Additional analysis is available in Appendix D.3.
baselines by mar-
Shower
Takee Shower
Mokrhjjastroomm
Reaett Exploration Space
Walk
Hellshowdd
Tarn (unlushowwe)
Finllsoup)
Hreishwwer)
Case Study. Figure 4 depicts an example of ToolChain" (GPT-4) and ReAct (Yao al., 2023b) on a "take shower" task in Virtual Home dataset. According to the ground truth (green, "shower"), ToolChain' generates the correct ac- tion plan (blue, "shower") with an expanded search space, whereas the baseline searching method gets trapped in locally optimal solu- tion (red, "soap"". This suggests that by for- mulating and expanding upon tree-based ac- tion space, ToolChain" is capable of effectively searching for the globally optimal solution in complex multi-step planning tasks.
SwtenOhphowwe)
Tantbohhwwe
SanDriitowrr
Grabbcepp
Tunffoohower
Baki Dacsiin
Tookchak Soktice
Figure 4: Case study of ToolChain" and Re- Act (Yao et al., 2023b) on Virtual Home dataset. Compared ReAct with unidirectional search (red), ToolChain" effectively enlarges search space (blue) with tree structures.
Efficiency Evaluation. In terms of efficiency, evaluate the running time of ToolChain' against all the baselines based on GPT-3.5- turbo, depicted in Figure 5(a). Remark- ably, ToolChain" is 37.2% faster than the most efficient tree search-based method, Tree-of- Thoughts (BFS). This efficiency gain may stem from the proposed superior cost function, which efficiently navigates the most promising paths. Additionally, ToolChain* outpaces the best- performing tree search-based method, MCTS, by an impressive 415.84%. This discrepancy arises because ToolChain' focuses expanding only the immediate next action during exploration. In contrast, MCTS goes through a more exhaustive process, simulating the entire future plan step by step using a rollout mechanism. Efficiency results based on GPT-4 are available in Appendix D.5.
Table 2: Ablation studies on ToolBench.
Home Search
Trip Booking
Google Sheets
Virtual Home
Average
TooIChain
93.0
90.8
61.4
28.6
68.5
(n),
91.0
88.3
60.0
22.6
65.5
(2))(n)
84.0
83.3
54.3
25.3
61.7
(1.)(n))
88.0
87.5
61.4
23.0
65.0
12,((1))
85.0
85.8
51.4
24.9
61.8
-g(n)
61.0
34.9
44.2
21.0
40.3
-(n)
84.0
85.8
53.4
26.1
62.3
7

---

Published as a conference paper at ICLR 2024
Ablation Studies. We conduct ablation studies to evaluate the effectiveness (success rate) of both the cumulative and future cost functions (Table 2). The results suggest that each component of the cumulative and future cost functions contributes to the performance of ToolChain". This verifies the efficacy of our proposed cost functions in guiding the search through the decision tree. In addition, eliminating either the entire cumulative future cost results in marked decline in the success rate. Relying exclusively on the future cost results in sharp performance drop of 28.2%, deteriorating ToolChain" to greedy strategy that favors the shortest solution plans with the least number of actions. Conversely, if the search is guided only by the cumulative cost, ToolChain" essentially mirrors the behavior of the BFS algorithm, yielding similar performance. Further analysis is in Appendix D.6.
4.3
MATH REASONING: GSM8K
Beyond tool-use scenarios, we demonstrate the flexibility of ToolChain" by generalizing its appli- cation mathematical reasoning for solving math word problems. We conduct experiments on the entire set of GSM8K and also subset of hard questions from GSM8K collected in ToolQA (Zhuang al., 2023). Detailed task setup for GSM8K is available in Appendix B.4.
Results. Table 3 presents the main experi- mental results (accuracy) for GSM8K and its challenging subset from ToolQA. Similar to tool-use studies (Table 1), ToolChain" consis- tently outperforms all baselines in both the orig- inal set and the challenging subset. These re- sults demonstrate the flexibility and generaliza- tion capabilities of ToolChain" in mathematical reasoning tasks. Notably, ToolChain' demon- strates greater advantages over other baselines on ToolQA (hard questions) than on GSM8K, indicating its superior capability in solving com- plicated tasks. This because simpler questions are composed of simple and static reasoning, eliminating the need for multiple branches. In contrast, challenging questions often involve complex reasoning, numerous intermediate steps, and multiple solution paths. The superior performance on hard subsets emphasizes the capability of ToolChain" in solving complicated reasoning problems. Furthermore, the efficiency analysis pre- sented in Figure 5(b) indicates that ToolChain" ranks among the most efficient tree-based search baselines and has time efficiency comparable closed-loop systems without tree structure. Detailed case studies of action space exploration and efficiency analysis with the number of valid actions available in Appendix D.4 and D.5, respectively.
Table 3: Main results on math reasoning task in GSM8K and its hard subset collected in ToolQA
GPT-3.5-turbo
GPT-4
Models
GSMBK ToolQA
GSMSK ToolQA
GPT CoT
67.3
26.0
86.6
66.0
70.1
30.0
87.5
75.0
Sclf-Consistency
76.1
47.0
92.4
78.0
ToT-DES ToT-BFS
69.9
32.0
89.2
76.0
72.3
39.0
91.3
77.0
MCTS
74.7
27.0
91.0
74.0
ToolChain"
77.0
52.0
93.5
84.0
4.4 DISCUSSION: EMPIRICAL ANALYSIS
From the comprehensive evaluations in planning and reasoning tasks presented in Sections 4.2 and 4.3, we validate that ToolChain" addresses the two core limitations of open-/closed-loog LLM-based agents, error propagation in multi- step solutions and constrained exploration in expansive action spaces. Meanwhile, we demon- strate ToolChain" more efficient searching strategy compared to existing tree search- based agents. From the scaling-up analysis in Fig- ure 10 in Appendix D.5, alongside experimental results in Table and efficiency metrics in Fig- ure 5, we identify a crucial trade-off between effectiveness and efficiency in the direct appli- cation of tree cearch-based reasoning methods to complex tool scenarios. To validate ToolChain" in solving these issues, we summarize key findings from experiments as follows: (1) From the main experimental results shown in Tables and 3, ToolChain" surpasses open-fclosed-toop and tree search
Stccesss Rate (96)
1
Bocking
Google Sheet
Running Time
Vitui Horre
ESMOK
22
12
(a) Performance
(b) Running Time
Figure 6: Scaling analysis of ToolChain". (a) Per- formance and (b) running time on ToolBench and GSM8K when scaling up step limitations T.
8

---

Published as a conference paper at ICLR 2024
baselines in complex multi-step planning and reasoning tasks, effectively mitigating error propaga- tion. A visualization example of how ToolChain' gradually abandons the faulty path and mitigates error propagation is available in Figure 7 in Appendix D.4. (2) From case studies in Figures 4, 7, and 8, ToolChain" navigates the path toward an optimal solution by formulating the action space as decision tree, thereby extensively broadening the exploration space. (3) From Figures 5 and 9, ToolChain" significantly accelerates the search process compared to other tree search-based methods, achieving time efficiency even comparable closed-loop systems without a tree structure. (4) From tool-use in ToolBench to math problems in GSM8K, we show that ToolChain" is plug-and-plan generalizable framework applicable to wide range of planning and reasoning problems. Notably, it exhibits exceptional proficiency in solving more challenging tasks, like ToolQA, compared to baselines. Additional results in Appendix E and show that ToolChain" * can generalize to wide range of complex reasoning tasks and open-source L.MSs (e.g., LLaMA 2 (Touvron et al., 2023)). (5) There is a trade-off between search depth (i.e., limitations on the number of steps) and the quality of the solution path (Figure 6). ToolChain' efficiently searches optimal solutions within limited steps, striking a balance between exploration and exploitation.
5 RELATED WORKS
LLMs for Tool Use. Recent advances have leveraged LLMs as autonomous agents to master tools and generate solution plans for complicated problems (Qin et al., 2023a;b; Mialon et al., 2023; Shi et al., 2024). Interacting with various tools. LLM agents can augment themselves with real-time factual knowledge (Nakano et al., 2022; Yang et al., 2023a). multi-modality understanding (Shen et al., 2023; Lu et al., 2023; Yang et al., 2023c), computational abilities (Schick et al., 2023; Parisi et al., 2022), code interpretabilities (Gao et al., 2022; Paranjape et al., 2023), and domain-specific functionalities (Zhang, 2023; Jin et al., 2023). However, many existing methods either concentrate on individual tool-use scenarios (Schick et al., 2023; Parisi et al., 2022) or simply inject human-made heuristic ordering rules for multi-too tool utilization (Shen al., 2023; Lu et al., 2023). With the increasing number of potential API functions at each step and the escalating sequence of actions for complex problem solutions, the action space expands exponentially, thereby diminishing their effectiveness. ToolChain" frames the planning challenge across various tools as navigation through the action space to efficiently identify valid solution path.
LLMs with Search Algorithms. The majority of LLM-based agents with open- or closed-loop systems rely on linear reasoning or planning structure. To explore multiple branches in the action space, self-consistency (Wang et al., 2022b) samples multiple chains of thoughts, which can be considered as multiple i.i.d. solution paths in the decision space, selecting the best answer through majority voting. Maieutic prompting (Jung et al., 2022) generates a tree of explanations, enforcing logical consistency. Xie et al. (2023) adopts beam search to decode and improve Chain-of-Thoughht reasoning chain. CoRe (Zhu et al., 2023) proposes to fine-tune both the reasoning step generator and verifier to solve math word problems, incorporating MCTS for reasoning decoding. Tree-of- Thoughts (Yao et al., 2023a) utilizes heuristic approaches, including depth- and breadth-first search to identify better reasoning pathways. Additionally, RAP (Hao et al., 2023a) combines a world model with rewards within advanced MCTS search approach. However, many beach--gidee planning approaches face the trade-off between efficient exploration of an expansive action space against the effective exploitation of global optimal solutions. To avoid exhaustive exploration like MCTS, we propose ToolChain" to combine efficient A search with the effective reasoning ability of LLMs.
6 CONCLUSION
In this paper, we propose ToolChain', an A* tree search-based planning algorithm to augment LLMs with external tools for complicated real-world planning and reasoning tasks. Compared to existing open- or closed-loop LLM agents, ToolChain" formulates the action space as a decision tree, thereby effectively mitigating error propagation and extensively expanding the search space. Furthermore, T significantly accelerates the search process compared to other tree search-based methods, enabling tree search in complicated action space and striking a dynamic balance between exploration and exploitation. By achieving significant improvements over state-of the-art baselines, ToolChain' showcases its potential as an efficient planning algorithm, navigating LLM--ased agents in addressing complex real-world challenges.

---

Published as a conference paper at ICLR 2024
REFERENCES
Rohan Anil, Andrew M Dai, Orhan Firat, Melvin Johnson, Dmitry Lepikhin, Alexandre Passos, Siamak Shakeri, Emanuel Taropa, Paige Bailey, Zhifeng Chen, al. Palm technical report. arXiv preprint arXiv:2305. 10403, 2023.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Wenhu Chen, Xueguang Ma, Xinyi Wang, and William W Cohen. Program of thoughts prompt- ing: Disentangling computation from reasoning for numerical reasoning tasks. arXiv preprint arXiv:2211.12560 2022.
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.0211 2022.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2110. 14168, 2021.
Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang. Jamie Callan, and Graham Neubig. Pal: Program-aides language models. arXiv, pp. 2211.10435v2, 2022.
Shibo Hao, Yi Gu, Haodi Ma, Joshua Jiahua Hong, Zhen Wang, Daisy Zhe Wang, and Zhiting Hu. Reasoning with language model is planning with world model. arXiv preprint arXiv:2305.1499 2023a.
Shibo Hao, Tianyang Liu, Zhen Wang, and Zhiting Hu. Toolkengpt: Augmenting frozen language models with massive tools via tool embeddings, 2023b.
Pengcheng He, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. Deberta: Decoding-enhancee bert with disentangled attention. In International Conference on Learning Representations, 2020.
Jie Huang and Kevin Mhen-Chuan Chang. Towards reasoning in large language models: A survey, 2023.
Wenlong Huang, Pieter Abbeel, Deepak Pathak, and Igor Mordatch. Language models as zero-shot planners: Extracting actionable knowledge for embodied agents. arXiv, pp. 2201.07207v2 2022a.
Wenlong Huang, Fei Xia, Ted Xiao, Harris Chan, Jacky Liang, Pete Florence, Andy Zeng, Jonathan Tompson, Igor Mordatch, Yevgen Chebotar, Pierre Sermanet, Noah Brown, Tomas Jackson, Linda Luu, Sergey Levine, Karol Hausman, and Brian Ichter. Inner monologue: Embodied reasoning through planning with language models. arXiv, pp. 2207.00 0307005608v1, 2022h.
Shima Imani, Liang Du, and Harsh Shrivastava. Mathprompter: Mathematical reasoning using large language models. arXiv preprint arX5v.3303.05398 2023.
Eric Jang. Can llms critique and iterate on their own outputs? evjang.com, 2023.
Qiao Jin, Yifan Yang, Qingyu Chen, and Zhiyong Lu. Genegpt: Augmenting large language models
with domain tools for improved access biomedical information. ArXiv, 2023.
Jaehun Jung, Lianhui Qin, Sean Welleck, Faeze Brahman, Chandra Bhagavatula, Ronan Le Bras, and Yejin Choi. Maieutic prompting: Logically consistent reasoning with recursive explanations. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. 1266-1279, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics. doi: 10.1166.11 18653/v 11655/v1/2022 /2w02.emmllpmmmmm.eem m2.n.82. URL ht / ac anthology org/ 2022. wmnlp-main..n..... 82.
Geunwoo Kim, Pierre Baldi, and Stephen McAleer. Language models can solve computer tasks. arXiv, pp. 2303.17491v 2023.
10

---

Published as a conference paper at ICLR 2024
Levente Koesis and Csaba Szepesvári. Bandit based monte-carlo planning. In European conference on machine learning. pp. 282-293. Springer, 2006.
Lorenz Kuhn, Yarin Gal, and Sebastian Farquhar. Semantic uncertainty: Linguistic invariances for uncertainty estimation natural language generation. In The Eleventh International Conference on Learning Representations, 2022.
Jacky Liang, Wenlong Huang. Fei Xia, Peng Xu, Karol Hausman, Brian Ichter, Pete Florence, and Andy Zeng. Code policies: Language model programs for embodied control, arXiv, pp. 2209.07753v3, 2022.
Stephanie Lin, Jacob Hilton, and Owain Evans. Teaching models to express their uncertainty in words, 2022.
Pan Lu, Swaroop Mishra, Tony Xia, Liang Qiu, Kai-Wei Chang, Song-Chun Zhu, Oyvind Tafjord, Peter Clark, and Ashwin Kalyan. Learn to explain: Multimodal reasoning via thought chains for science question answering. 2022.
Pan Lu, Baolin Peng, Hao Cheng, Michel Galley, Kai-Wei Chang, Ying Nian Wu, Song-Chun Zhu, and Jianfeng Gao. Chameleon: Plug-and- sang-andplay compositional reasoning with large language models. arXiv preprint arXiv:2304.0985 2023.
Grégoire Mialon, Roberto Dessi, Maria Lomeli, Christoforos Nalmpantis, Ram Pasunuru, Roberta Raileanu, Baptiste Rozière, Timo Schick, Jane Dwivedi- Yu, Asli Celikyilmaz, Edouard Grave, Yann LeCun, and Thomas Scialom. Augmented language models: survey, 2023.
Swaroop Mishra, Matthew Finlayson, Pan Lu, Leonard Tang, Sean Welleck, Chitta Baral, Tanmay Rajpurohit, Oyvind Tafjord, Ashish Sabharwal, Peter Clark, et al. Lila: A unified benchmark for mathematical reasoning. arXiv preprint arXiv:22 /0. 17517, 2022.
Reiichiro Nakano, Jacob Hilton, Suchir Balaji, Jeff Wu, Long Ouyang, Christina Kim, Christopher Hesse, Shantanu Jain, Vineet Kosaraju, William Saunders, et al. Webgpt: Browser-assister question-answering with human feedback. arXiv preprint arXiv:2112.093322 2021.
Reiichiro Nakano, Jacob Hilton, Suchir Balaji, Jeff Wu, Long Ouyang, Christina Kim, Christopher Hesse, Shantanu Jain, Vineet Kosaraju, William Saunders, Xu Jiang, Karl Cobbe, Tyna Eloundou, Gretchen Krueger, Kevin Button, Matthew Knight, Benjamin Chess, and John Schulman. Webgpt: Browser-assisted question-answering with human feedback, 2022.
OpenAl. Gpt-4 technical report. arXiv, pp. 2303.08774v3, 2023.
Bhargavi Paranjape, Scott Lundberg, Sameer Singh, Hannaneh Hajishirzi, Luke Zettlemoyer and Marco Tulio Ribeiro. Art: Automatic multi-step reasoning and tool-use for large language models. arXiv preprint arXiv:2303.000 2023.
Aaron Parisi, Yao Zhao, and Noah Fiedel. Talm: Tool augmented language models. arXiv preprint arXiv:2205. 12255, 2022.
Shishir G Patil, Tianjun Zhang, Xin Wang, and Joseph E Gonzalez. Gorilla: Large language model connected with massive apis. arXiv preprint arXiv:2305. 15334, 2023.
Xavier Puig, Kevin Ra, Marko Boben, Jiaman Li, Tingwu Wang, Sanja Fidler, and Antonio Torralba. Virtualhome: Simulating household activities via programs. Proceedings the Computer Vision and Pattern Recognition, pp. 8494-8502. 2018.
the IEEE Conference
Yujia Qin, Shengding Hu, Yankai Lin, Weize Chen, Ning Ding, Ganqu Cui, Zheni Zeng, Yufei Huang. Chaojun Xiao, Chi Han, et al. Tool learning with foundation models. arXiv preprint arXiv:2304.08354, 2023a.
Yujia Qin, Shihao Liang, Yining Ye. Kunlun Zhu, Lan Yan, Yaxi Lu, Yankai Lin, Xin Cong, Xiangru Tang, Bill Qian, et al. Toolllm: Facilitating large language models to master 16000+ real-world apis. arXiv preprint arXiv:2307. 16789, 2023b.
11

---

Published as a conference paper at ICLR 2024
Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language under- standing by generative pre-training OpenAl Blog, 2018.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. OpenAl Blog, 2019.
Timo Schick, Jane Dwivedi- Yu, Roberto Dessi, Roberta Raileanu, Maria Lomeli, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. Toolformer: Language models can teach themselves to use tools. arXiv preprint 2302::2302.0466.., 2023.
Yongliang Shen, Kaitao Song, Xu Tan, Dongsheng Li, Weiming Lu, and Yueting Zhuang. Hugginggpt: Solving ai tasks with chatgpt and its friends in huggingface. arXiv preprint arXiv:2303. 17580, 2023.
Wenqi Shi, Ran Xu, Yuchen Zhuang, Yue Yu, Jieyu Zhang, Hang Wu, Yuanda Zhu, Joyce Ho, Carl Yang, and May Wang. Ehragent: Code empowers large language models for complex tabular reasoning electronic health records. arXiv preprint arXiv:2401.07/222 2024.
Noah Shinn, Beck Labash, and Ashwin Gopinath. Reflexion: an autonomous agent with dynamic memory and self-reflection. arXiv preprint arXiv:2303. 1136663,..11,,,, 2023.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panncershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):444488, 2016.
Haotian Sun. Yuchen Zhuang, Lingkai Kong, Bo Dai, and Chao Zhang. Adaplanner: Adaptive planning from feedback with language models, 2023.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaci, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.0922 099809888 2023.
Xingyao Wang, Sha Li, and Heng Ji. Code4struct: Code generation for few-shot structured prediction from natural language. arXiv preprint arXiv:2210. /28/0, 2022a.
Xuezhi Wang. Jason Wei, Dale Schuurmans, Quoe V Le, Ed H Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Representations, 2022b.
Zihao Wang, Shaofei Cai, Anji Liu, Xiaojian Ma, and Yitao Liang. Describe, explain, plan and select: Interactive planning with large language models enables open-world multi-task agents, arXiv, pp. 2302.01560v1. 2023.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoe Le, and Denny Zhou. Chain-of-though prompting elicits reasoning in large language models. arXiv, pp. 2201.11903v6, 2022.
Adina Williams, Nikita Nangia, and Samuel Bowman. A broad-coverage challenge corpus for sentence understanding through inference. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technolo- gies, Volume (Long Papers), pp. 1112-1122 2018.
Chenfei Wu, Shengming Yin, Weizhen Qi, Xiaodong Wang, Zecheng Tang, and Nan Duan. Vi- sual chatgpt: Talking, drawing and editing with visual foundation models. arXiv preprint arXiv:2303.04671. 2023.
Yuxi Xie, Kenji Kawaguchi, Yiran Zhao, Xu Zhao, Min- Yen Kan, Junxian He, and Qizhe Xie. Decomposition enhances reasoning via self-evaluation guided decoding. 2023.
Qiantong Xu, Fenglu Hong, Bo Li, Changran Hu, Zhengyu Chen, and Jian Zhang. On the tool manipulation capability of open sour-s large language models. arXiv preprint arXiw:2305.16504 2023.
12

---

Published as a conference paper at ICLR 2024
Linyao Yang, Hongyang Chen, Zhao Li, Xiao Ding, and Xindong Wu. Chatgpt is not enough: Enhancing large language models with knowledge graphs for fact-aware language modeling, 2023a.
Rui Yang, Lin Song, Yanwei Li, Sijie Zhao, Yixiao Ge, Xiu Li, and Ying Shan. Gpt4tools: Teaching large language model to use tools via self-instruction, 2023b.
Zhengyuan Yang. Linjie Li, Jianfeng Wang, Kevin Lin, Ehsan Azarnasab, Faisal Ahmed, Zicheng Liu, Ce Liu, Michael Zeng, and Lijuan Wang. Mm-react: Prompting chatgpt for multimodal reasoning and action. XrXiv preprint arXiv:2303. 1381, 2023c.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimban. Tree of thoughts: Deliberate problem solving with large language models, 2023a.
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik R Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. In The Eleventh International Conference on Learning Representations, 2023b. httL:tts:// /ttp::///////peeeeeeeee net/ forrmm? id=WE_vluYUL--
Beichen Zhang, Kun Zhou, Xilin Wei, Wayne Xin Zhao, Jing Sha, Shijin Wang, and Ji-Rong Wen. Evaluating and improving tool-augmented computation-innensiv math reasoning, 2023.
Jiawei Zhang. traph-toolformmr: To empower ilms with graph reasoning ability via prompt aug- mented by chatgpt. arXiv preprint arXiv:2304.11116, 2023.
Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric. Xing, Hao Zhang, Joseph E. Gonzalez, and Ion Stoica. Judging llm-as-a-judge with mt- mt-bench and chatbot arena, 2023.
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoe Le, and Ed Chi. Least-to-most prompting enables complex reasoning in large language models. arXiv, pp. 2205. 2022.
Xinyu Zhu, Junjie Wang, Lin Zhang, Yuxiang Zhang, Yongfeng Huang, Ruyi Gan, Jiaxing Zhang, and Yujiu Yang. Solving math word problems via cooperative reasoning induced language models. In Proceedings of the 6/ Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp. 4471 -4455, Toronto, Canada, July 2023. Association for Computational Linguistics. doi: 10.1 18653//112002..cllloorr 245.
URL https: /// h/tpa//aaaaanlto....aaaa. org/
2023.
Yuchen Zhuang, Yue Yu, Kuan Wang, Haotian Sun, and Chao Zhang. Toolqa: A dataset for Ilm question answering with external tools, 2023.
A BROADER IMPACTS AND LIMITATIONS
In this study, we introduce ToolChain', an efficient tree search-based planning algorithm for LLMs- based agents tackling challenging tasks involving tool usage. As a flexible plug-and-play framework with compositional planning and reasoning capabilities, ToolChain holds considerable promise for positive social impact across diverse domains, including but not limited to real-world tool utilization and complex decision-making processes. One potential limitation to consider is that, while the efficiency of our proposed ToolChain" * surpasses other tree search methods and is even comparable to closed-loop systems, still cannot match the efficiency of open-loop systems. Given the demands for efficiency in real-world applications, we intend to further refine our tree structure and search strategy in future work.
B IMPLEMENTATION DETAILS
B.1 HARDWARE INFORMATION
All experiments are conducted on CPU: Intel(R) Xeon(R) Platinum 8275CL CPU @ 3.00GHz and GPU: NVIDIA A100 SXM4 80 GB using Python 3.8.13.
13

---

Published as a conference paper at ICLR 2024
B.2 PARAMETER CONFIGURATION
We chose the GPT-3355tturb engine for ChatGPT and the GPT-4 engine for GPT-4 when structuring the LLM-based agent. The maximum length for generated solutions set to 512, and the temperature is set to for flexibility in self-consistency frequency function 9t, (Section 3.2). For LLaMA-2 experiments, the maximum length for generated solutions set as 256 and the temperature is set to 1. We use 8 NVIDIA A100 SXM4 80 GB GPUs and FastChat (Zheng et al., 2023) to tune the LLaMA-2 7B and 13B models on the training data discussed in Appendix F. For ToolChain', we set the weights of geometric means between heuristic and non-hcuristic parts in cumulative and future costs as a = 3 = 0.5 by default. The number of potential actions in ceffsoonsst frequency is set as k = 10 and the maximum step limit is set T 20 by default. Our code repository is presently undergoing an internal review within the company for public release. Upon receiving approval, we will make both the code and data available GitHub.
B.3 TASK SETUP FOR TOOLBENCH
We define the nodes the decision tree as function API calls. From the root node, which corresponds to the input task description, we represent the complex process of identifying successful solution as navigating valid path in the tree search space. To expand from the current node, we prompt L.Ms with API definitions, demonstration examples, the given query, and action history, thereby generating multiple i.i.d. next steps. In order to precisely evaluate plan quality and gauge the proximity of the current action to the goal, we employ task-specific heuristic functions (Section 3.2) for both cumulative and projected scores. To ensure a fair comparison, all prompts dispatched to the baselines and ToolChain" follow the configuration set by ToolBench (Xu et al., 2023). Detailed descriptions of prompts are available in Appendix I.1. We adopt the success rate as the evaluation metric for Home Search, Trip Booking, and Google Sheets. For Virtual Home, we report the proportion of scripts achieving the correct end state or successfully completing the task.
B.4 TASK SETUP FOR GSM8K
GSM8K (Cobbe et al., 2021) serves as a dataset for high school-level mathematical reasoning. Numerical reasoning tasks within this dataset typically comprise descriptive component followed by culminating question. Answering this question requires multi-step mathematical calculations based on the context of the description. Notably, the complexity directly relates to the number of mathematical reasoning steps required for a solution. We conduct experiments GSM8K and also a subset hard questions from GSM8K collected TooIQA (Zhuang et al., 2023). In adapting ToolChain", the math question description as the root node, complex reasoning across numerous intermediate steps is translated into navigating the decision space for valid path. Given the absence of seed data for long-term memory, we simplify ToolChain" to leverage self-consistency frequency and LLM imagination as the cumulative score g(z) and future score h(n), respectively.
the entire set of
represent reasoning steps in solution nodes in the decision tree. With
C LLM-BASED AGENTS
We summarize existing -LMeddsed Agents for tool-use scenarios in Table 4, with a detailed definition and related works of open- and closed-loop systems in the following sections.
C.1 OPEN-LLOP SYSTEM
Open-loop Systems (Wei et al., 2022; Zhou et al., 2022) generate pre-defined plans to explore over coherent intermediate steps toward problem-solving. Given the initial states so, which are usually the problem description ar in the format of natural language, the systems generate the entire T'step plans as the solution p((1, .2.... -arls)): : - A ((A"), where S is the state space, A is the action space, and (--) is probability simplex function. The final output is obtained after executing the entire plan y p(y) Sp, a1 02, .ar).
LLMs for Open Planning. Trained on vast world knowledge and human examples, LLMs have emerged with smart planning and decision-making capabilities. Leveraging L.LMs as autonomous
14

---

Published as a conference paper at ICLR 2024
Table 4: A comparison of methods that leverage L.LMs for tool-use. Each method's features reported into five categories: 1) Basic Information: The basic information of the method about tool-use relevance, covering the total number and type of tools used by the methods, the number of tools involved in solving each problem, the instruction type of methods, and the tasks for evaluation. 2) Planning Ability: The method will generate a complete plan solve problems. 3) Modify Steps:
The method makes changes to the next action (Taking Action). 4) Modify Plans: The method might revise the entire plan (Modifying Plan) and make changes accordingly or not. 5) Trace Back: The method can revise the past actions in the plan and make modifications to restart from previous actions.
Methods
Tools
Tool Types
# Took/Task Instruction Type
Tisk
Planning Modify Stepi|Modify Plans Trace- Back
Open Loop Methods
CoT (Wei et al., 2022)
Prompsing
QA
X
Lila (Mishra et 2022)
Code (Math)
Prompxing
MartQA
X
X
PoT (Chen
Code (Mail)
Prompting
TabQA
X
X
X
Code-1Struct (Wang al. 2022x)
Code (Event)
Prompting
Extraction
X
X
X
PAL (Gao et 2022)
Code (Math)
Prompxing
MathQA
MathPrompt (Imani al., 2023)
Code (Math)
Prompsing
MathQA
TootFormee (Schick al., 2023)
Basic
PR FT
QA
X
GrolFroolFrrmer (Zhang, 2023)
Graph
Gruph
X
X
Talm (Parisi et 2022)
Basic
PR FT
QA
X
X
X
HuggingGPT (Shen al., 2023)
10
Vision Models
>1
Prompting
VQA
X
X
Chameleon (1 aa et al, 20233
10
NLP 'Table
S1
Prompting
QA
GeneGPT (Jin et al., 2023)
NCBI APIs
Prompsing
Gene Tasks
Greedy Cloved-Loop Loop Methods
WebGPT (Nokano (Nakano
ol., 2021)
10
Web Operations
>
Fine-tuning Prompsing
QA
Viisa
ART (Panunjape et al., 2023)
Code, Basic
>1
BigBench
1XXXX
ReAct (Yao al,, 2023b)
Retriever
S1
PR & FT
Q4, Env
MM-ReAct (Yang et al, 2023c)
Vision Models
Prompiing
CV tasks
Visual ChaGGP al., 2023)
Models
Prompting
tasks
Closed Loop Methods
DEPS (Wang oi al., 2023)
Game Actions
PR & FT Prompting
Game Eavs
AdaPlanner (Sun et al., 2023)
Tree Search- baaed Methods
ToT (Yao al., 2023k)
Thoughts
PR PR
Planning
MCTS (Hao et al., 2023a)
Thoughts
Planning
ToolChain
>00
General
PR & FT
Envs, MahQQ
agents to accomplish decision-making tasks has gained attention and shown potential. Earlier studies apply the open-loop framework to directly generate the entire plan the solution. One line of works, including Chain-of- Thought (Wei et al., 2022) and Zero-Shot Planner (Huang et al., 2022a), generate intermediate reasoning steps all once solve the problem. Another line of works selects the opposite direction (e.g., least-to-most prompting (Zhou et al., 2022)) that decomposes the complicated problems into relatively easier sub-problems. For more complex tasks, methods like HuggingGPT (Shen et al., 2023) and Chameleon (Lu et al., 2023) incorporate a set of functional tools and directly generate the plan of API calls in sequence for execution. However, all these aforementioned methods explore predetermined single path in the decision space, leaving the rest potential plans not considered when solving the problems.
C.2 CLOSED-LOOP SYSTEM
Closed-loop Systems follow more step-by-step plan modification and execution manner, inter- leaving intermediate observations with decisions over the action space. When the agent interacts with the environment at the t-th step, the agent is aware of the current observation the environment and generates a trajectory-like context e = (50, d1, 01, d2, ).)). ).
E O from tool-use scenarios, the intermediate observations are obtained during the execution of the previous actions in the plan 0₂ ~ x (or] Sp, 41, 01, .......... a--1). According to the environment feedback or, two levels of be applied: greedy closed- methods (Yao et al., 2023b; Shinn et al., 2023) only decide the next single step a, ~ p(a, (g. c;; I, D), while the standard ones (Wang et al., 2023; Sun al., 2023) will modify the entire future plans (a++1, 0442," ... ar,, |so, C1 I, D).
refinements
15

---

Published as a conference paper at ICLR 2024
Table 5: Task overview of (1) Home Search, (2) Trip Booking, (3) Google Sheets, (4) Virtual Home, and (5) GSM8K datasets. We provide examples of task descriptions with output actions, and report the number of APIs (# APIs) and questions (# Ques) within each dataset.
Datasets
Task Descriptions
Output Actions
| APIs # Ques
# APIs/Sol
Home
I want to buy townhruse, mobile or un-op
APl Jocation" www.aaoon("Pitthuurrgi "Pittshurgh") APl.et.boy.or..oo bour
15
100
7.5
Search
in Pitsburghh with rooms. My budget is 51385000.
Trip Booking
Could you help me find train tickets for 3 children and adults from Des Moines to
API.select booking type(" ("rrpp tickets")
20
120
13.4
APLlselstttransportatinn" "ataaaapprrtttioorrrainn.""
Cape Coral on July 07, 2022?
Google
Update chicken's price by 2. IA table
= get as dataframe((wrksssee)
108
70
Sheels
flattened in the context.]
[[lodfdd("Prudutt]] = "chicken', 'Price') 2---
Virtual
Read book
Agent. Agent. Find(novel)
40
100
13.4
Home
Agent. Turn Tum/To(novel)...
GSM8K
apples. Anna upples
has more apples than Elsa. So Anna has 2 5 apples....
(ToolQA)
How many apples they have together?
(100)
LLMs for Closed-Loop Planning. Inspired by traditional reinforcement learning approaches that heavily rely on interaction with the environment (either simulator or real world), researchers start to improve the plan via refinement according the environment feedback. Initially, ReAct (Yao et al., 2023b) and Inner Monologue (Huang et al., 2022b) allow LLM agents to refine a single step greedily according to the environment feedback. Considering that solely modifying the immediate action being executed is easy to fall into local sub-optimal actions, improvements like DEPS (Wang al., 2023) and AdaPlanner (Sun al., 2023) are proposed to recursively modify the entire future plans according to the environment feedback. However, without a tracing-bass bbck mechanism to check the already executed plans, these efforts in the closed-loop framework still only explore small proportion of decision space. To mitigate these issues, we propose ToolChain", that enables tree search in planning and can record multiple branches in the decision space.
D EXPERIMENTAL DETAILS
D.1 DATASET DETAILS
We evaluate TooiChain" four tool-use environments in ToolBench (Xu et al., 2023) and one reasoning task in GSM8K (Cobbe et al., 2021). Table 5 provides examples of task descriptions and output actions and reports the number of APIs and questions incorporated in the environment.
Home Search simulates the process of locating homes in specific area based on certain criteria. A Agetts are required to leverage 15 functions (e.g., set. set-locate ton, search, etc.), aid users in completing the search.
Trip Booking is a task that parallels the Home Search but incorporates more advanced dependencies between function calls. This task simulates the process of submitting search requests for transportation tickets, hotel rooms, or a combination of both. Specifically, conditions or parameters like locations, dates, and the number of tickets. The API includes total of 20 functions related to trip booking scenarios.
guided by specific searching
Google Sheets involves manipulating actual worksheets from Google Sheets via the gspread library 2, including common operations such as updating cell values, sorting, etc..
Virtual Home derives from the setting of the VirtualHome simulator (Puig et al., 2018). It requires the LLM agents to generate sequences of actions with multiple function calls for com- pleting household activities. It consists of 40 functions (e.g., Sleep (), Push (object), and PourInto (object object2)) ), each corresponding to a specific action exemplified in the
'https://www.g google. e com/ sheet / about/ /heets/abuut// hhttps://docs. httrss////oossggrra..rrr////////
16

---

Published as a conference paper at ICLR 2024
simulator. Every function can take up to two arguments, representing valid objects within the household settings.
GSM8K (Cobbe et al., 2021) is dataset of high-quality linguistically diverse grade school math word problems. To evaluate the model performance on the GSM8K dataset, we evaluate the accuracy at which models are able to obtain the final correct answer. In addition, also report model performance on a subset of hard questions in GSM8K, curated by ToolQA (Zhuang et al., 2023). The hard questions are sampled from the error cases made by ChatGPT on the original GSM8K dataset.
D.2 BASELINE DETAILS
For tool-use tasks in ToolBench, we compare ToolChain" with GPT (OpenAI, 2023), ReAct (Yao et al., 2023b), AdaPlanner (Sun et al., 2023), Tree-of-Thoughts (Yao et al., 2023a), and MCTS (Hao et al., 2023a). For math reasoning tasks in GSM8K, we compare ToolChain" with the state-of-the-art reasoning approaches, including GPT (OpenAI, 2023), Chain-of-Thoughh (Wei et al., 2022), Self- Consistency (Wang et al., 2022b), ReAct (Yao al., 2023b), Pree-of-Thoughee (Yao et al., 2023a), and MCTS (Hao et al., 2023a).
We provide details of each baseline as follows:
GPT (OpenAI, 2023) is a standard input-output prompt with four in-context examples. We directly send the four-shot examples with the task description together to GPT-3.5- t-ttbbbb and GPT-4. GPT series serve as open-loop systems with closed-source LLMs as backbones.
Chain-of-Thought (Wei al., 2022) prompting is an open-loop mechanism enhance reasoning in language models. Chain-of-thought prompting breaks down multi-step problems, allocating additional computational resources for extensive reasoning stages step by step.
Self-Consistency (Wang et al., 2022b) is an open-loop decoding strategy to replace the conventional greedy decoding typically employed in chain-of-thouu thouthttttt prompting. It initially samples an array of diverse reasoning paths rather than solely relying on the most probable one. Subsequently, by marginalizing over these sampled reasoning trajectories, pinpoints the most coherent answer.
ReAct (Yao et al., 2023b) integrates reasoning with tool use by prompting LLMs to generate interleaved verbal reasoning traces and tool calls. ReAct closed-loop system for LLM-based agents in tool usage.
AdaPlanner (Sun et al., 2023) is a closed-log system that enables the LLM agent to adaptively refine its self-conceived plan based on feedback from the environment. This refinement process leverages both in-plan and out-of-plan strategies.
Tree-of-Thougee (Yao et al., 2023a) is tree search-based I.LM reasoning framework that built upon sfain-of-thoughe prompting. facilitates exploration across cohesive textual segments, which act intermediary steps in the mroblem-solvin process. Unlike linear reasoning pathways in open- or closed-loop systems, ToT enables language models to engage in decision-making by examining various reasoning trajectories. With the ability to self-assess choices for the subsequent steps, ToT provides the flexibility to anticipate future steps or revisit previous ones to make holistic decisions.
MCTS (Hao et al., 2023a) is tree search-based LLM reasoning framework, repurposing LLM and functioning both as a world model and a reasoning agent. It integrates a principled planning algorithm, specifically based on MCTS, facilitating strategic exploration in the expansive reasoning space. LLLM-base agent systematically constructs a reasoning tree, guided by its inherent world model and task-specific rewards.
D.3 ADDITIONAL ANALYSIS ON TOOLBENCH
We observe that closed-loop methods typically perform better than tree search-based methods on the Home Search and Trip Booking datasets. Conversely, for the Google Sheets and Virtual Home datasets, tree search-based methods perform better. This discrepancy can be attributed to the nature of feedback provided by the datasets. For instance, the Home Search and Trip Booking datasets offer precise environmental feedback regarding plan errors (e.g., "Task execution error: 'HomeSearchAPr object has no attribute 'ser min baths ""), enabling closed-loop systems to effectively modify their plans. In contrast, the Google Sheets and Virtual Home datasets, with their extensive API function
17

---

Published as a conference paper at ICLR 2024
calls (108 and 40, respectively), present notably larger action space than Home Search and Trip Booking (15 and 20, respectively).
D.4 CASE STUDIES
Q: tey nanufacturer receives an order for 488 toys. 5 workers are available to wank on the orden. 2 of the workers produce toys hour, and another workers produce 4 toys hour. They work on order during their 18-hour shift, and by the end of their shift the nanufacturer still needs another 20 toys to be able to ship the order. How nany toys hour does the fifth worker produce?
ToolChain" Exploration Space
2x6-12
2x6x10=120
2x4+8
COT Exploration Space
(12+8)x100-200
400-20-380
12+8-20
400- 300-20-380
120-80-200
200-20-220
400-20-380
400-20-200-180
20-20-0
400-20-380
400-20-200-180
380-200-180
Descriptin
ToolChaln" Execution
ToolChain Explored
Solution
180/10-18
ToolChain" Esploration
Exccution
ToolChain" Solution
Answer
Step
Step
Step2
Step
Step 4
Step
Problem Description
ToolChain" Exploration
ToolChain' Solution
d
ToolChain' Execution
CoT Exccution
Stop
Stop
Step 8
Step
Step 10
Figure 7: Case study comparing Chain-of- Thouugh and ToolChain" on GSM8K dataset. We offer comparison in exploration space (upper part) and planning ordering (lower part). Given the input query, ToolChain" explores a wide range of potential nodes (blue shadowed area) in the decision tree, while Chain-of-Thought only explores one direction (red shadowed area). During the planning process, chain of thought can fall into a faulty loop or dead end with previous incorrect action. However, ToolChain" can gradually abandon the faulty path by increasing the cost after the incorrect action. This enables it to revise previous actions and jump out of the faulty path to try another plan.
We include additional case studies with visualizations comparing the Chain-of-Thoon ToolChain" on the GSM8K dataset. As shown in Figures 7 and 8, we compare the exploration space (upper part) and planning ordering (lower part) of both methods on the same problem. Given the input query, ToolChain" explores wide range of potential nodes (blue) in the decision tree, while ohain-of-TThughh only explores one direction (red). Moreover, from a step-by-step visualization of the planning process in Figure 7, we notice that chain-of-thought falls into a faulty loop or a dead end with previous incorrect action. However, ToolChain" can gradually discard the faulty path by increasing the cost after the incorrect action. This allows our method to re-evaluate and adjust prior actions, facilitating shift away from erroneous paths to explore alternative plans. More importantly, it mitigates the error propagation along the action plan, which usually occurs in linear or unidirectional solutions (i.e., open- and closed-loop systems).
and
18

---

Published as a conference paper at ICLR 2024
Q: Alex, Stan, and Adelwolfe are trying to catch then all, Pokemon that is. Together they have caught 339 Pokemon. Alex has caught 5 more than stan, and Stan has caught 13 less than tines as nany as Adelwolfe has caught. How many Pokemon has Stan caught?
TooiChain" Exploration Space
CoT Exploration Space
Adelwolfe:
A+5-D-339
Stan: S=4D-13
Alex: S+5
A=S+5
D+(4D-13)+A-339
A+50=352
(4(-)-13))44-88)3339
A=(S+13)/4
S+|S+5)+(4D-133)) 13]=339
D+5+(4D-13)=33)
S-5+(4D-13)-D-339
9D-21-339
2S-4DD-8-339
D-347/5-69.4
5+50-347
D=:0
S=263
Problem Description
ToolChain Execution
TooiChain" Explored Nodes
CoT Solution
TooiChain" Exploration
Execution
ToolChain"
Figure 8: Case study comparison between Chain-of- Toahughh and ToolChain" on the GSM8K dataset. The exploration space is illustrated in the upper section, and the planning order is depicted in the lower section. For given input query, ToolChain' explores expansive set of potential nodes (bluc) with correct answers, whereas Chain-of- -hhought primarily navigates in a singular direction (red).
1200
Home Search
60-
GSMBK (GPT3.5)
Burning Theee (in Sac)
1000
50
ToolQA (GPT3.5)
Google Sheet
(GPT4)
800
Virtual Home
Exploration
40
ToolQA (GPT4)
(a) ToolBench
(b) GSMSK
Figure 9: Additional time efficiency evaluation on ToolBench and GSMSK. (a) We report additional average running time in seconds over all instances in the dataset using GPT-4 backbone. (b) We calculate the average number of valid actions in GSM8K for math reasoning efficiency analysis. In both cases, ToolChain" shows close efficiency to closed-loop systems without a tree structure and outperforms other tree-search algorithms in terms efficiency.
D.5 EFFICIENCY DETAILS
In terms of additional efficiency analysis in tool use, evaluate the running time of ToolChain" against all the baselines based on GPT-44, as shown in Figure 9()). Consistent with our previous results, TooIChain" is faster than the most efficient tree search-based method, Tree-of-Thoughts (BFS). For the math reasoning task, we conduct efficiency analysis with a number of valid actions Figure 9b)). We calculate the average number of valid actions in GSM8K for math reasoning efficiency analysis. Similarly, ToolChain" shows close efficiency to closed-loop systems without tree structure and outperforms other tree-search algorithms in terms of efficiency.
From the scaling-up up analysis in Figure 10, we can explicitly identify crucial trade-off between effectiveness and efficiency the direct application of tree search-based reasoning methods to complex tool use scenarios, including ToT-DFS (Yao et al., 2023a). ToT-BFS (Yao et al., 2023a), and MCTS (Hao et al., 2023a). Compared with ToolChain". which quickly converges on with time efficiency and high high-quality solution, the rest tree-based search methods not only suffer from relatively low success rate (Figure 10(a),, but also struggle with the long running time (Figure 10(b)). This could be further verified by experimental results in Table and efficiency metrics in Figure 5.
19

---

Published as a conference paper at ICLR 2024
Running Time (in Sec)
Success Rate (96)
350
300
250
To T-DFS
To T-BFS
MCTS
Tool-Chain
20
Step Limit
Step Limit
(a) Performance
(b) Running Time
Figure 10: Scaling analysis of ToT-DFS (Yao et al., 2023a), ToT-BFS (Yao et al., 2023a), MCTS (Hao et al., 2023a), and ToolChain". (a) Performance and (b) running time on Home Search when scaling up step limitations T.
D.6 ABLATION STUDIES DETAILS
We conduct detailed analysis of the ablation studies for both the cumulative and future cost functions in the following, presented in Table 2. First, experimental results indicate that each element within both the cumulative and future cost functions enhances the performance of ToolChain". This verifies the efficacy of our proposed cost functions in guiding the search through the decision tree. Second, dropping either heuristic components (gi.t. r.. h1,;) or the non-heuristic (g2,r. l12,e) components from the cumulative or future cost functions results in decline in performance. Specifically, when the non- heuristic components are absent, there is an average drop in the success rate 6.8%; whereas, without the heuristic components, the decrease is 3.3%. This suggests that in most instances, non non-heuristic components have a more significant impact. This is potentially because heuristic components, relying limited in covering all test cases and may struggle to precisely estimate the cost of new actions or tasks. In scenarios where environments offer high-quality seed data for long-term memory (e.g., Virtual Home), the heuristic function plays a more important role. Third, eliminating either the entire cumulative or future cost results in a marked decline in the success rate. Relying exclusively on the future cost induces sharp performance drop of 28.2%, deteriorating ToolChain" to greedy strategy that favors the shortest solution plans with the least number of actions. Conversely, the search guided only by the cumulative cost, ToolChain" essentially mirrors the behavior of the BFS algorithm, yielding similar performance outcomes.
on long-term memory,
E ADDITIONAL DATASET: SCIENCE QA
Table 6: Additional results on ScienceQA based on GPT-3.5-turbo.
Models
Accuracy
CoT (GPT-3.5-turbo)
78.3
Chameleon (GPT-3.5-turbo)
79.9
ToolChain (GPT-3.5-turbo)
80.7
We evaluate ToolChain" in Science Question Answering (ScienceQA) (Lu et al., 2022) dataset on general reasoning tasks. ScienceQA serves as a diverse benchmark for multi-modal question answer- ing across an array of scientific topics and contexts. Answering its questions requires a variety of tools and capabilities, including image captioning, text detection, knowledge retrieval, online resource searches, and multi-clue visual reasoning. Since ToolChain" can function as alug-and-play planner, we replace the original naive -asee planner in Chameleon with ToolChain" for evaluation purposes. For our experiments, we select the Chain-of-Thought (Wei et al., 2022) and the original Chameleon (Lu et al., 2023) as reference baselines. When built upon tional LLM, ToolChain realizes an accuracy improvement of 0.8% over Chameleon. ToolChain" benefits from considering multiple potential paths for execution. However, the performance gain is limited on the dataset, primarily because the logic behind calling different tools to solve the problem from the dataset is quite rigid.
as the founda-
20

---

Published as a conference paper at ICLR 2024
F OPEN-SOURCE LLMS
Table 7: Additional experimental results (success rate) on Virtual Home for tool-use evaluation based on LLaMA-2 (Touvron et al., 2023) 7B and 13B models.
Models
Executable
Success
Success (E)
LLaMM-22 (7B)
31.0
21.2
[LaMA-22 (13B)
30.0
19.8
Stepl.TaMA-2 (7B)
57.0
25.4
29.5
StepI.LaMA-2 (13B)
56.0
25.3
27.4
ToolChain" (Step-LLaMA-2, 7B)
57.0
28.7
31.0
ToolChain" (Step-LLaMA-2, 13B)
96.0
30.0
30.2
Task Setup In this section, we explore the potential of leveraging TooIChain" on open-source large language models. ToolBench (Xu et al., 2023) offers the training data for each of the datasets. The instructions in the original training data include the task query g and simple "Actions prompt to make the model generate the entire plan = (oo, a1 ... .r,)) However, without any API documentation demonstration examples provided in the instructions, generating comprehensive plan proves challenging for models. Additionally, we strive to further refine the connections between adjacent actions in the solution plans within the training data. Thus, decompose the solution plans autoregressively, assembling the original task query with the previous actions as instruction and treating the +t++1 1)-th action in the plan as the solution. More specifically, for step and the task query g. the new instructions are in the format of (g, Q1, aa). The corresponding solution is the next-step action a++1- In addition, with the decomposition, the size of training data increases from pairs, we fine-tune two StepLLaMA-2
500 to 4500. With the generated instruction-solutinn models based on LLaMA-2 (Touvron et al., 2023) 7B and 13B models. As ToolChain" can be applied as alug-and-play module for agents based on different LLMs, We also equip the fine-tuned StepLLaMA-2 with ToolChain'.
Results We evaluate the performance of both StepLLaMA-2 and ToolChain' (StepLLaMA-2) on the Virtual Home dataset and show the results Table 7. We report the metrics of Executable, Success, and Success (E). Executable means the proportion of plans that can be executed in VirtualHome without violating any rules. Success means the proportion of plans that lead to the correct final state. Success (E) is variant of Success, which only tests the Success rate executable plans. StepLLaMA-2 and ToolChain" (LLaMA-2) both outperform the LLaMA-2 models that are directly tuned on the original training data in ToolBench. In addition, applying ToolChain" on StepLLaMA- 2 can bring 4.0% improvement in success rate on average, showing that ToolChain" can also be effective on open-source LLMs.
G ADDITIONAL ANALYSIS ON VALUE FUNCTIONS
Table Additional results on ToolChain" with different value functions.
Home Search
Trip Booking
Google Sheets
Virtual Home
Average
T -Self-Evaluation Hao al. (2023a))
84.0
83.3
49.9
21.5
59.7
T (ToT-Vote Yao al. (2023a))
82.0
81.7
53.4
21.0
59.6
T
93.0
90.8
61.4
28.6
68.5
To validate the advantage of our proposed value function, we explored various cost function for- mulations, including self-evaluation prompting LLMs to generate verbalized scores (Hao et al., 2023a), and vote scores in 'tree-of-thoughte (Yao et al., 2023a). Our findings indicated that these scoring methods were not consistently accurate. We identified two key factors guiding our heuristic function design: (1) the black-box nature of state-of-th the art LLMs offering limited information for score formulation, and (2) the observation that similar tasks often share similar logical structures in their solution plans. Driven by the two motivations, we developed heuristic scores maximize
21

---

Published as a conference paper at ICLR 2024
the of additional information derived from past experiences (Table 8). The results demonstrate that a combination of LLM- LLM-generater scores and heuristic scores yields superior performance. In the initial stages, due to limited data in the long-term memory, the model predominantly relies the -.M--enerrted scores for generating plans. As the long-term memory expands, the heuristic functions increase in aceuracy, effectively regularizing and refining the I.MM-generated scores.
Table 9; Additional results on ToolChain" with different value functions using LLaMa-2 (7B).
Virtual Home
ToolChain* (Action Likelihood)
25.7
ToulChain (Answer Probability)
26.1
ToulChain (Reward Function)
27.4
ToolChain
28.7
Furthermore, have conducted explorations utilize additional information from open-sourced LLMs in order to formulate a more precise cost function. These explorations include: (1) action likelihood, calculated the product of token log probabilities within an action; (2) answer probability, determined by the token probability of "yes' ss in response to the question 'Is this action step correct?"; and (3) reward-style probability, which applies weight decay based on the length of tokens in the actions and the total number of actions in plan. Table presents additional experimental results using LLaMA-2 (7B). The results indicate that our proposed cost functions outperform other value functions from open-source LLMs.
H COST ANALYSIS
We provide more detailed information regarding the computational costs of ToolChain" (GPT-3.5) across our datasets in Table 10. It is important to note that the heuristic functions in ToolChain" do not require additional LLM calls. Instead, they rely on a long-term memory that stores solution plans. As for the costs related to the environment or domain simulations, these are primarily included in the prompts for expansion. This aspect accounts for approximately $7.22. Similar budgetary considerations apply recent advances (Yao et al., 2023b; Sun et al., 2023; Yao et al., 2023a) that also rely on experiments utilizing OpenAl APIs. Additionally, it is worth noting that the cost of using gpt-3.5-turbo is progressively decreasing within months, making it more affordable in the future.
Table 10: Additional computational costs of TooiChain" * based on gpt-3.5-turbo.
Costs
Expansion Heuristic Functions LLM--bssed Functions
# LLM Calls per Question
16.44
107.31
S Prompt Cost per Datasel
7.22
5.53
S Completion Cost per Datasct
8.23
9.25
I PROMPTS
1.1 TOOL USE: TOOLBBNNH
We follow the prompt format from ToolBench (Xu et al., 2023), which consists of API documents, three-shot in-context demonstration examples, and the query. We utilize the same retriever as the ToolBench implementation to obtain the pertinent API documents and demonstration examples.
<ToolChain" TCc. Prompt
(api_ docs (examples]
Task: (query)
Action:
hhttps://gi thub. com/ www.anowattaaaeeeeoooaaoe http:///wwaa.teebbeeeeeeeee////e
22

---

Published as a conference paper at ICLR 2024
We then provide examples of API documents and demonstrations for each dataset used in experiments.
1.1.1 HOME SEARCH
We present five examples of API documents from the Home Search dataset as follows:
<ToolChain'
Womeeearch. <toolChainn'HonnSeerrc....
Prompt
# To set home types for search. For home buying ng, home_types cho choices are: "House", "Townhouse", "Condo", "Land", Muilti-family, "Mobile", "Co-op"; for home renting, home heme_types choices "House", "Townhouse", "Condo", "Apartment". API. API. see.sseeet_home_ttye (home_types: [ist[str])
To specify whether search homes for buying renting, 'value' can be chosen from l'buy', , 'rent']. This function be called after setting the location and before setting any other criteris. AFI.set_buy__o_reme (value: str)
# set the maximum commute time in minite (value: int)
API ceset_ma__commutee_eeeeee
# To set the minimum home price in dollars API wel.set__in__rree (value: int)
# To set the maximum home price dollars
API.set D0I.set_max_priiee paice (value: int)
We also provide demonstration example from the Home Search dataset:
<ToolChain' Soreeearch Prompt
Task: want buy townhouse, mobile co-op in Pittsburgh with rooms. My budget $1385000.
Actions:
APl.set_location (rcccatioon"Piittrrrree"" ("Pittsburgh")
API.set_buy_or_rett ("buy")
(""oonhouse", (""ooroooue"" API.set_num beds
AFI.select_home_typee
"Mobile", "Co-op"1)
wit.set_max_priiee (1385000) API (eIrsh))ch()
1.1.2 TRIP BOOKING
We present five examples of API documents from the Trip Booking dataset below:
<ToolChain' < -rippookiing Prompt
# To select the transportation type from [' l'fighh'', 'train', 'bus',
'cruise'). AFI aeI.sellee_.raassotttttet (transportation_tyye)
To select the booking type from ['hotels', 'trip tickets', "both'l. API APl.select_bood inooakingttypee (booking_type)
the number of child tickets to purchase.
API.set num children (value)
# To set the number of adult tickets to purchase.
AFI sen_matt_um_ (value)
# To set the location for arrival, given a Loc object. API. DeI.sse_ddetiinatinn (Loc)
We also provide demonstration example from the Trip Booking dataset:
23

---

Published as a conference paper at ICLR 2024
<ToolChain' TripRooking.Demo>> Prompt
Could you help me find train tickets for children and adults from Des Moines to Cape Coral July 07, 2022? My budget is up 280
per ticket.
Actions:
ABI.ccllc__bookknggttypll ("trip tickets")
API AFF.ccllet__ttasppprttoooo ("train")
( AFT.set_num_aduuts($)
locaticn_from ("c Moines")
API ueL.sett.criphhhlccstttoooooo
location_to (*Cape Coral")
departure_date = (7, 7, 2022)
API. AP1
date (departure_
aFl.set_max_tickee wttps_ttccett_picccce (280)
API sel.search ()
1.1.3 GOOGLE SHEETS
We present four examples of API documents from the Google Sheets dataset as follows:
<ToolChain' Googl eSheets Dog> Prompt
GoogleSheets
Sets values cell range of the sheet.
worksheet.updes (range_name, values-None, **kwargs)
Updates the value of cell.
worksheet wwwssheet.uddatee. update_cellllleeeeeeeeppppppppee (row, col, value)
Deletes multiple columns from the worksheet at the specified index. borksheet.delete__colllo (snaoccclummssttttr____edeeee (start_index, end_index-None)
Deletes multiple rows from the worksheet the specified index. Beeksheet..dlete__eeee iistarrrindes end index=None)
We also provide one demonstration example from the Google Sheets dataset:
<ToolChain' GoogeeSheets Demo>
Prompt
beef | Cost
Product
Price
pork
chicken 10
|
lamb 3 15 |
duck 12 | 2 I
fish
100
Task: Sets 'Hello world' 'A2" cell
Actions:
'Hello world')
Task: Sets 'ello world' '22' cell
Actions: worksheet. wwrksheet.update_cee. update_cell (2, 1, 'elll world')
Task: Updates A2 and with values and
Actions: worksheet. AAA2:A3', [[42), [43]])
Task: Updates D2 with values
Actions: worksheet. berksheet.uudate.. update (' D2', 3)
Task:
Sum Al :4 and write the result below A4
Actions:
24

---

Published as a conference paper at ICLR 2024
worksheet update ( (A1:A4))) raw=False)
Task: Update chicken's s price by Actions:
of = aat__as_attaraameeee (worksheet)
df of.locccd(("rroouctt)) "chicken', 'Price')
worksheet.clest set_with_daten (worksheet, dł, include index=False,
1.1.4 VIRTUAL HOME
Below, we present five examples of API documents from the Virtual Home dataset:
<ToolChain' -iwrtualHome.Do.. Prompt
# Take a piece of clothes off. 'object' can only be: ('clothes_jacket
'clethes ccltthes_dress'' ccothes_haat 'shoes', 'clotnes_shire pcnttses_pants']: Agent (akeoff
Scrub an object. 'object' can only be: I'mop', 'cup', ttollet' 'plate', 'soap', 'sink', 'spocn', 'est', 'shower' 'dshwaaser'', "hands 'hands_both', both', ddriniinggglsss 'bowl', 'towel').
# Rinse an object. 'object' can only be: l'oup', 'pot', 'water', 'watcr_glass', 'sponge', 'scap', 'towel', 'dish_soap', 'oven', elcaning_solution 'knife' 'spoon', 'sink', 'faucet', "clothes_underweat 'detergent', 'drinking_glass', 'hands_both! 'toilet', 'shhwer', 'rag', 'plate', "bowl', fork']. agent.Ringg (object)
Wash an object. 'object' can only be: l'aa''' 'cup', 'food vegetable' dresser', 'fork', 'shoes' 'child' 'coffee coffee_cup', 'bed', 'water', 'soap', 'duster', 'brush', 'bathtub', 'toy', 'cleaning_bottle', 'hair', 'sink', 'razor', 'hands_both', 'drinking_glass', 'table', 'toilet', "basket_for_clothes 'bowl', 'spoon']. Wash (object)
'shoerr', 'dishwasher', 'plate',
# Full object. 'object' enly be: I'table', 'mep', 'mouse', "chair' "clothes_pants" 'Light_buld" 'curtain', 'vacuum_eleaner"" 'mat', 'eat', food', 'drawing', 'shoes', "cetterpiece', 'sheets', 'pot', 'aapoop]]. Agent. (object)
We also provide one demonstration example from the Virtual Home dataset:
<ToolChain' VirtualEome Demo> Prompt
Task:
Put down bags
Actions:
Agent WalkTo (dining room)
Agent WalkTo (food _oodd
Agent.Find (food food)
Agent Grab (food_food)
Agent Find (table)
Agent Put (food_food, table)
1.2
MATH REASONING: GSM8K
Below the prompts utilized for the math reasoning dataset, GSM8K (Silver al., 2016):
25

---

Published as a conference paper at ICLR 2024
<ToolChain' _GSM8K> Prompt
Please complete the plans to solve the question. Here is several examples:
Q: Four years ago, Kody was only half as old as Mohamed. If Mohamed is currently twice 30 years old, how old is Kody?
A: Let's think step-by-step;
1. We were told that Mohamed is currently twice 30 years old, he is currently
2 60 years cld.
2. That means that four years age he must have been old.
56 years 3. Four years ago, Kody was half old Mohamed, Kedy must have been 56 /
28 years old then.
Since Kedy was 28 years old four years ago, she must now be
32 years old.
5. The answer is 32.
Q: Carla bought bags of mini peanut butter cups on clearance. Rach bag was $6.00 but was 75% off. How much did she spend on 2 bags of candy
A: Let's think step-by-step:
1. Each bag was $6. out was 758 off. So each bag cost $6.00
(1 0.75) $6.00 0.25 $1.50.
Carla bought bags. So she spent $1.50
$3.00.
3. The answer is 3.
Q: If Pam is currently twice young as Rena is, and in 10 years Rena will 5 years older than her, how old Pam now?
A: Let's think step:
1. since Rena will be years older than Pam in 10 years, she must be
5 years older than Pam now as well.
2. If Pam is currently twice
young Rena, that that Rena is currently twice old as Pan is.
3. So if P stands for Pam's s age now and R stands for Rena's s age now, then we know that R - P.
4. And since Rena is years older than Pam now, we know that R P 5. that 5.
have 6. The answer is 5.
By substitution,
P, which
Q: Cappuccinos cost $2, iced teas cost $3, cafe lattes cest $1.5 and espresses cost $1 each. Sandy crders some drinks for herself and some friends. She orders three cappuccinos, cafe lattes, and two espresscs. How much change does she receive back for twenty-dollar bil1?
iced teas,
A: Let's think step-by-step:
Sandy ordered three cappuccincs, which cost each, she spent $6 on cappuceines.
$2
2. She ordered two iced teas, which cost $3 each, so she spent
$3 2 = $6 dollars on ice teas.
3. She ordered two cafe lattes, which cost $1.5 each, she spent
$1.5 2 $3 cafe lattes.
4. She ordered two espressos, which cost $1 each, so she spent
$1 2 $2 on espressos.
5. So altogether, Sandy spent $6 $6 + $3 + $2 $17 on drinks, which means that sandy will get $20 $17 $3 as change. The answer [END OF EXAMPLE]
Q: (question)
let's think step-by-step:
26


Reviews:
[{"review_id": "vYnNEAo9eS", "reviewer": "Reviewer_gdT8", "summary": "This paper proposes ToolChain*, an efficient tree search-based planning algorithm to augment large language models (LLMs) with external tools for complex real-world planning and reasoning tasks.  This paper provides very good insight that formulates the action space as a search tree, where each node is an API function call. This mitigates error propagation and expands the search space compared to linear reasoning in open-/closed-loop systems. It uses an A*-like algorithm to search the tree, prioritizing branches using a task-specific cost function with cumulative cost g(n) and future cost h(n). This balances exploration and exploitation for efficient search.", "questions": "1) How robust are the cost functions g(n) and h(n) for entirely new tasks where long-term memory/heuristics may not be available?\n2) Could incremental search algorithms like IDA* further improve efficiency over A* search used here?\n3) For very large action spaces, is it possible to focus the search on high-level plans first before expanding API details? Hierarchical search?\n4) How well would ToolChain* generalize if the action space grows 10x or 100x in size? At what point would efficiency degrade?\n5) Beyond API functions, how can ToolChain* be extended to more general symbolic action spaces?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1) Novel formulation of LLM planning as tree search using A* search algorithm is intuitive and elegant. Allows structured exploration of expansive action space.\n2) Task-specific cost functions g(n) and h(n) provide a principled way to guide search and prioritize promising branches.\n3) Strong empirical results demonstrating improved success rate and efficiency over competitive baselines on diverse tasks.", "weaknesses": "1) Cost functions rely on heuristic components like long-term memory, self-consistency sampling, and LLM imagination which may not always be accurate.\n2) Still trails open-loop systems in efficiency, albeit outperforming other tree search methods. There is a tradeoff between search depth and solution quality.\n3) Limited analysis on how the approach generalizes to even more expansive action spaces and longer planning horizons. \nHowever, I think that the above weaknesses are some hard open questions in NLP with LLM.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "z4Ipb97v0o", "reviewer": "Reviewer_52p8", "summary": "The paper proposes ToolChain*, a best-first search algorithm for improving the performance of LLM-based agents on sequential decision-making problems. The main contributions are algorithmic and empirical. Specifically, the paper proposes a set of heuristic cost functions leveraging a dataset of solved plans to explore the search space more efficiently. Experiments are conducted on the ToolBench and GSM8K datasets. The results show that ToolChain* outperforms or matches strong recent baselines on these tasks.\n\n===========\n\nUPDATE: I thank the authors for their detailed responses to the reviewers comments. After reading the other reviews and comments, I'm revising my score upwards. The technical details are clearer now and it seems like there's enough here to warrant acceptance. I encourage the authors to incorporate the reviewers feedback into the final version of the paper and make the paper as standalone and reproducible as possible.\n\n===========", "questions": "- Please explain the details of the Imagination Score in more detail. For example, what does \"imagine more concrete future steps\" mean? Where is the \"imagined plan\" generated in Algorithm 1? (I think in the cost calculation $f(n)$ but not sure). How many extra calls to the LLM?\n\n- Is the LCS calculation in $g_{t,1}$ over the sequence of API actions ($a_i \\in \\mathcal{A}$) alone or does it include additional information about the task or problem in the text string? Do the API actions include the parameters or just the method names?\n\n- How much does overall performance vary with the prompt and the other hyper-parameters of the algorithm (dataset, heuristic score implementation, etc.)?\n\n- How much performance comes from the use of the LLM in different parts of the algorithm vs classical (non-LLM) best-first search? Specifically, how is performance impacted by non-LLM expansion with LLMs only used for node evaluation? Is it possible to construct a search-based baseline which **doesn't** use any LLMs but otherwise incorporates the same intuition (long-term memory, heuristic scoring, etc.)? If yes, how might it perform?\n  - In Appendix D.5, is it possible to characterize the computational costs of ToolChain* in more detail? For example, what are the the LLM costs in terms of the number of calls and generated tokens? Dollar cost? Heuristic computational costs? Environment (domain) \"simulation\" costs associated with the API calls, if any?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ The paper tackles an interesting and important research question with potentially large impact.\n\n+ The paper proposes a simple and intuitively clear best-first search approach to construct an improved LLM-based planning agent. The heuristic function seems novel with potential for broad use across tasks.\n\n+ The proposed method outperforms a number of strong baselines. The experiments include ablations, computational costs and other forms of analyses making it easier to evaluate. The experimental section and appendix has a good amount of detail, aiding reproducibility. \n\n+ The paper is reasonably well-written. The use of illustrative examples made it very easy to understand.", "weaknesses": "- Some of the implementation details of the four components of the heuristic function are not clearly explained. These are central to evaluating the algorithmic contributions of the paper and reproducibility so a clearer description would be very useful. I found it particularly difficult to understand the implementation details of the \"imagination score\". See the questions for details.\n\n- Although the experiments have a good amount of detail including ablation experiments, the paper does not clearly identify the main sources of performance improvement. For example, how much does a better scoring function matter compared with a better LLM or search procedure? How does performance depend on the prompt and other hyper-parameters of the algorithm (heuristic score implementation, dataset size and quality, etc.)? What happens if we use non-LLM versions of the scoring function? The paper mentions the importance of the cost function (\"this efficiency gain may stem from the proposed superior cost function\") but does not investigate deeper. As a result, it becomes difficult to clearly identify the overall impact and broader utility of ToolChain*, especially compared to similar search-based ideas proposed in Tree-of-Thought.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lHo2aXqeGP", "reviewer": "Reviewer_tHXf", "summary": "Leveraging powerful LLMs in complex decision-making tasks is a promising direction, and the authors discussed their categories with clear explanations. For efficient reasoning, the authors proposed a new method inspired by A* search and developed some designed evaluation functions for the search. Experimental results with various domains (e.g., Home Search, Trip Booking) with GPT-3.5 and GPT-4 show the effectiveness of the proposed method named ToolChain*.", "questions": "- Although the evaluated methods and experiments seem solid and interesting to the readers, I’m curious about the designing part of the two important evaluators, $g(n)$ and $h(n)$.\n    - As we know, the naive A* algorithm has some theoretical discussions (e.g., admissible heuristic and optimality in the search problems). However, in the current status of the ToolChain*, the idea (evaluating the node with some function) is from the A*, but no theoretical discussions (e.g., the effectiveness of search) have arisen from the design of $f(n) = g(n) + h(n)$. Do you have any insights? Are there any reasons to adopt the current form of functions? Tried different ones? Although the ablation study in Table 2 is useful, particularly restricted to the current form of g and h, we could have further options here.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "- A firm contribution of the reasoning framework using LLMs inspired by the MCTS and search algorithm.\n- Extensive experimental evaluations show the effectiveness of the concept.", "weaknesses": "- Posiblly handcrafted the two important components (g(n) and h(n) in the A* search) for the problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "w9ZRGgs4Pm", "reviewer": "Reviewer_7Kjr", "summary": "In this paper, the authors propose a tree-search-based planning framework for Large Language Models (LLMs). Their framework is motivated by A* search in heuristic planning and uses a cost function, which is a sum of (past) accumulated cost and (future) heuristic cost to update their planning tree. The use of simple heuristics also makes it more resource-efficient than concurrent works based on Monte Carlo Tree Search. The authors demonstrate both empirically, and through various ablation studies, how their proposed method generates more feasible plans.", "questions": "1. What do you mean by \"task-specific\" heuristic functions? Are the tasks here based on \"g\"? If so, do you use different memory buffers for each task, and how many trajectories do you need in the memory buffer before it produces a valid score? \n\n2. It seems to me that the future cost heuristic might mislead the planner since it is likely that the same action may appear at different positions (in the sequence) for different tasks. For instance: \"Clean a kitchen table\" and \"Set a kitchen table\" have their action sequences reversed.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "* Clarity: The paper is well-written and easy to follow. \n* Novelty: The proposed tree-search-based method is novel (see footnote) and uses a simple but effective cost-function design that helps in better decision-making. \n* Significance: The experiments adequately justify the superior performance of their proposed method, both empirically and qualitatively. The use of heuristics for LLM planning is appealing to the LM planning & reasoning community and could be a potential research direction for the future.\n\nFootnote: Note the work \"SayCanPay: Heuristic Planning with Large Language Models using Learnable Domain Knowledge, Hazra, et al., 2023\" which also proposes heuristic planning with LLMs. However, given its recency, I have considered it as a concurrent work, and therefore have not compared them despite their overlapping contributions.", "weaknesses": "I did not find any major weaknesses in the paper. However, it would be nice to have some clarifications regarding the proposed heuristic functions (see Questions).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)