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

arXiv: https://arxiv.org/abs/2310.13227 · HTML: https://mlsanity.com/paper/2310.13227/

## Key facts

- Cited by 105 papers in the map (data through 14 Oct 2026).
- Builds on 44 of its 60 references that are in the map.
- First posted on arXiv 20 Oct 2023.

## Builds on (most cited first, 30 of 44)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [A Broad-Coverage Challenge Corpus for Sentence Understanding through Inference](https://mlsanity.com/paper/1704.05426/) (2017)
- [DeBERTa: Decoding-enhanced BERT with Disentangled Attention](https://mlsanity.com/paper/2006.03654/) (2020)
- [ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIs](https://mlsanity.com/paper/2307.16789/) (2023)
- [Learn to Explain: Multimodal Reasoning via Thought Chains for Science Question Answering](https://mlsanity.com/paper/2209.09513/) (2022)
- [WebGPT: Browser-assisted question-answering with human feedback](https://mlsanity.com/paper/2112.09332/) (2021)
- [Least-to-Most Prompting Enables Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2205.10625/) (2022)
- [Gorilla: Large Language Model Connected with Massive APIs](https://mlsanity.com/paper/2305.15334/) (2023)
- [Code as Policies: Language Model Programs for Embodied Control](https://mlsanity.com/paper/2209.07753/) (2022)
- [HuggingGPT: Solving AI Tasks with ChatGPT and its Friends in Hugging Face](https://mlsanity.com/paper/2303.17580/) (2023)
- [PaLM 2 Technical Report](https://mlsanity.com/paper/2305.10403/) (2023)
- [Inner Monologue: Embodied Reasoning through Planning with Language Models](https://mlsanity.com/paper/2207.05608/) (2022)
- [Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Tasks](https://mlsanity.com/paper/2211.12588/) (2022)
- [Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agents](https://mlsanity.com/paper/2201.07207/) (2022)
- [Reasoning with Language Model is Planning with World Model](https://mlsanity.com/paper/2305.14992/) (2023)
- [Semantic Uncertainty: Linguistic Invariances for Uncertainty Estimation in Natural Language Generation](https://mlsanity.com/paper/2302.09664/) (2023)
- [Teaching Models to Express Their Uncertainty in Words](https://mlsanity.com/paper/2205.14334/) (2022)
- [Visual ChatGPT: Talking, Drawing and Editing with Visual Foundation Models](https://mlsanity.com/paper/2303.04671/) (2023)
- [MM-REACT: Prompting ChatGPT for Multimodal Reasoning and Action](https://mlsanity.com/paper/2303.11381/) (2023)
- [VirtualHome: Simulating Household Activities via Programs](https://mlsanity.com/paper/1806.07011/) (2018)
- [Describe, Explain, Plan and Select: Interactive Planning with Large Language Models Enables Open-World Multi-Task Agents](https://mlsanity.com/paper/2302.01560/) (2023)
- [Language Models can Solve Computer Tasks](https://mlsanity.com/paper/2303.17491/) (2023)

## Built on by (most cited first, 30 of 105)

- [TravelPlanner: A Benchmark for Real-World Planning with Language Agents](https://mlsanity.com/paper/2402.01622/) (2024)
- [RAGEN: Understanding Self-Evolution in LLM Agents via Multi-Turn Reinforcement Learning](https://mlsanity.com/paper/2504.20073/) (2025)
- [Scaling Large Language Model-based Multi-Agent Collaboration](https://mlsanity.com/paper/2406.07155/) (2024)
- [Tool Learning with Large Language Models: A Survey](https://mlsanity.com/paper/2405.17935/) (2024)
- [Retrieval-Augmented Generation with Graphs (GraphRAG)](https://mlsanity.com/paper/2501.00309/) (2024)
- [EASYTOOL: Enhancing LLM-based Agents with Concise Tool Instruction](https://mlsanity.com/paper/2401.06201/) (2024)
- [Cut the Crap: An Economical Communication Pipeline for LLM-based Multi-Agent Systems](https://mlsanity.com/paper/2410.02506/) (2024)
- [Advances and Challenges in Foundation Agents: From Brain-Inspired Intelligence to Evolutionary, Collaborative, and Safe Systems](https://mlsanity.com/paper/2504.01990/) (2025)
- [G-Designer: Architecting Multi-agent Communication Topologies via Graph Neural Networks](https://mlsanity.com/paper/2410.11782/) (2024)
- [Agentic Reasoning and Tool Integration for LLMs via Reinforcement Learning](https://mlsanity.com/paper/2505.01441/) (2025)
- [Multi-Agent Collaboration via Evolving Orchestration](https://mlsanity.com/paper/2505.19591/) (2025)
- [GUI Agents: A Survey](https://mlsanity.com/paper/2412.13501/) (2024)
- [Q*: Improving Multi-step Reasoning for LLMs with Deliberative Planning](https://mlsanity.com/paper/2406.14283/) (2024)
- [PlanGenLLMs: A Modern Survey of LLM Planning Capabilities](https://mlsanity.com/paper/2502.11221/) (2025)
- [EHRAgent: Code Empowers Large Language Models for Few-shot Complex Tabular Reasoning on Electronic Health Records](https://mlsanity.com/paper/2401.07128/) (2024)
- [LLM Reasoners: New Evaluation, Library, and Analysis of Step-by-Step Reasoning with Large Language Models](https://mlsanity.com/paper/2404.05221/) (2024)
- [HYDRA: Model Factorization Framework for Black-Box LLM Personalization](https://mlsanity.com/paper/2406.02888/) (2024)
- [DoraemonGPT: Toward Understanding Dynamic Scenes with Large Language Models (Exemplified as A Video Agent)](https://mlsanity.com/paper/2401.08392/) (2024)
- [Tool Learning in the Wild: Empowering Language Models as Automatic Tool Agents](https://mlsanity.com/paper/2405.16533/) (2024)
- [LLM-based Agents Suffer from Hallucinations: A Survey of Taxonomy, Methods, and Directions](https://mlsanity.com/paper/2509.18970/) (2025)
- [From Exploration to Mastery: Enabling LLMs to Master Tools via Self-Driven Interactions](https://mlsanity.com/paper/2410.08197/) (2024)
- [Large Language Models for Planning: A Comprehensive and Systematic Survey](https://mlsanity.com/paper/2505.19683/) (2025)
- [Cocoa: Co-Planning and Co-Execution with AI Agents](https://mlsanity.com/paper/2412.10999/) (2024)
- [LLMs Meet Multimodal Generation and Editing: A Survey](https://mlsanity.com/paper/2405.19334/) (2024)
- [System-1.x: Learning to Balance Fast and Slow Planning with Language Models](https://mlsanity.com/paper/2407.14414/) (2024)
- [Efficient Tool Use with Chain-of-Abstraction Reasoning](https://mlsanity.com/paper/2401.17464/) (2024)
- [Tool-Planner: Task Planning with Clusters across Multiple Tools](https://mlsanity.com/paper/2406.03807/) (2024)
- [Security of AI Agents](https://mlsanity.com/paper/2406.08689/) (2024)
- [Non-myopic Generation of Language Models for Reasoning and Planning](https://mlsanity.com/paper/2410.17195/) (2024)
- [A Trembling House of Cards? Mapping Adversarial Attacks against Language Agents](https://mlsanity.com/paper/2402.10196/) (2024)

## Abstract (arXiv)

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.