Research map / Large language models / Agents, code and math
ToolChain*: Efficient Action Space Navigation in Large Language Models with A* Search
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes ToolChain*, an A*-style best-first tree search where LLM-generated API calls or reasoning steps form nodes, scored by LCS-based long-term memory heuristics and LLM self-consistency/imagination scores, evaluated on ToolBench and GSM8K/ToolQA.
Problem
LLM agents planning over large API action spaces either explore unidirectionally (open/closed-loop) and get stuck in locally optimal or erroneous paths, or exhaustively search tree spaces (DFS, MCTS) at high cost.
Approach
Formulates the action space as a decision tree and applies A* search with a cost f(n)=g(n)+h(n), where g combines task-specific LCS memory scores with LLM self-consistency frequency and h combines relative-position heuristics with an LLM "imagination" score; expansion requires a single LLM call per step rather than MCTS rollouts.
Key results
- ToolChain* reaches 68.5% average success on ToolBench with GPT-3.5-turbo vs 64.8% for MCTS and 63.5% for AdaPlanner.
- ToolChain* achieves 74.7% average success on ToolBench with GPT-4, versus 72.1% for AdaPlanner and MCTS.
- On the ToolQA hard subset with GPT-3.5-turbo, ToolChain* scores 52.0 vs 47.0 for self-consistency; the paper reports running time 415.84% faster than MCTS.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use ToolChain* instead of AdaPlanner | GPT-3.5-turbo tool-use planning · ToolBench average | success rate: 63.5 -> 68.5 | Helped |
| use ToolChain* instead of MCTS | GPT-3.5-turbo tool-use planning · Google Sheets | success rate: 62.9 -> 61.4 | Hurt |
| use ToolChain* instead of AdaPlanner | GPT-4 tool-use planning · ToolBench average | success rate: 72.1 -> 74.7 | Helped |
| use ToolChain* instead of Self-Consistency | GPT-3.5-turbo reasoning · GSM8K | accuracy: 76.1 -> 77.0 | Helped |
| use ToolChain* instead of Self-Consistency | GPT-3.5-turbo reasoning · ToolQA | accuracy: 47.0 -> 52.0 | Helped |
| use ToolChain* instead of Self-Consistency | GPT-4 reasoning · GSM8K | accuracy: 92.4 -> 93.5 | Helped |
| use ToolChain* instead of Self-Consistency | GPT-4 reasoning · ToolQA | accuracy: 78.0 -> 84.0 | Helped |
| add task-specific cumulative heuristic g₁,t(n) (ablation) | ToolChain* · ToolBench average | success rate: 65.5 -> 68.5 | Helped |
| add self-consistency frequency g₂,t(n) (ablation) | ToolChain* · ToolBench average | success rate: 61.7 -> 68.5 | Helped |
| add task-specific future heuristic h₁,t(n) (ablation) | ToolChain* · ToolBench average | success rate: 65.0 -> 68.5 | Helped |
| add LLM imagination score h₂,t(n) (ablation) | ToolChain* · ToolBench average | success rate: 61.8 -> 68.5 | Helped |
| add cumulative cost g(n) (ablation) | ToolChain* · ToolBench average | success rate: 40.3 -> 68.5 | Helped |
Surprising findings
- Relying only on the future cost h(n) drops average ToolBench success from 68.5 to 62.3 and removing g(n) drops it to 40.3, showing the cumulative cost is crucial.
- MCTS scores 27.0 on the ToolQA hard subset with GPT-3.5-turbo, below plain CoT (30.0).
Limitations
- Still slower than open-loop systems such as GPT.
- Code and data release pending internal company review at time of writing.
- Long-term memory heuristic requires seed demonstration examples, so GSM8K variant drops it.
Experimental setup
Datasets: ToolBench (Home Search, Trip Booking, Google Sheets, Virtual Home) GSM8K ToolQA hard subset
Benchmarks: ToolBench GSM8K ToolQA
Metrics: success rate accuracy running time
Baselines: GPT ReAct AdaPlanner ToT-DFS ToT-BFS MCTS Chain-of-Thought Self-Consistency
Builds on: Tree-of-Thoughts Monte Carlo Tree Search A* search self-consistency ToolBench
Closest papers by meaning
- ToolSearcher: Optimizing Tool Selection at Scale via Reinforcement Learning (NeurIPS 2026 · similarity 0.90)
- Language Agent Tree Search Unifies Reasoning, Acting, and Planning in Language Models (ICML 2024 · similarity 0.89)
- Expanding LLM Agent Boundaries with Strategy-Guided Exploration (NeurIPS 2026 · similarity 0.89)
- SPIRAL: Symbolic LLM Planning via Grounded and Reflective Search (AAAI 2026 · similarity 0.89)
- Plan-and-Act: Improving Planning of Agents for Long-Horizon Tasks (ICML 2025 · similarity 0.89)
- Scaling Autonomous Agents via Automatic Reward Modeling And Planning (ICLR 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.