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

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. It formulates the entire action space as a decision tree, where each node represents a possible API function call involved in a solution plan. 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. Large language models (LLMs), such as GPT (Radford et al., 2018; 2019; Brown et al., 2020; OpenAI, 2023) and PaLM (Chowdhery et al., 2022; Anil et al., 2023), have exhibited remarkable capabilities of reasoning and instruction-following across a 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-based 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 to determine a chain of API function calls that can be executed sequentially toward a valid solution. However, given an action space of hundreds of candidate API functions, each comprised of various function names and parameters available at every planning step, searching for a globally optimal solution becomes highly challenging. Work done during the author's internship at Adobe Research.