Research map / Large language models / Agents, code and math
Tree-Planner: Efficient Close-loop Task Planning with Large Language Models
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 Tree-Planner, which samples multiple plans from an LLM once, merges them into an action tree, and has the LLM make grounded top-down decisions with backtracking, cutting token cost and error corrections in VirtualHome.
Problem
Iterative LLM task planning is token-inefficient (the same long prompt is re-charged every step) and correction-inefficient (local or global replanning), limiting large-scale use in closed-loop task planning.
Approach
Decompose LLM use into one plan-sampling call that produces N candidate plans, aggregate them into a prefix-sharing action tree, then make repeated grounded decisions over child nodes with environment observations, backtracking to the previous fork node on failure.
Key results
- Tree-Planner (N=25) reaches 28.33% SR without correction, versus 27.04% for the best baseline, Iterative-Planner, at lower cost (3.39 vs 5.12 dollars... reported $ cost 2.39 vs 5.12).
- With correction, Tree-Planner (N=50) achieves 41.58% SR versus 37.93% for the best baseline.
- Token cost is reduced by 92.24% relative to Global Replan under the with-correction setting, and error corrections drop by 40.52% relative to Global Replan.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Tree-Planner instead of Iterative-Planner without correction | GPT-3.5 task planning · VirtualHome w/o correction | SR: 27.04\pm4.65 -> 28.33\pm1.18 | Helped |
| Use Tree-Planner instead of Global Replan | GPT-3.5 task planning with correction · VirtualHome with correction | $Cost: 42.55$\pm$0.09 -> 3.30$\pm$0.01 | Helped |
| Use Tree-Planner instead of Local Replan | GPT-3.5 task planning with correction · VirtualHome with correction | No.EC: 3.29$\pm$0.46 -> 1.85$\pm$0.05 | Helped |
| Increase sampled plans from N=25 to N=50 (ablation) | Tree-Planner · VirtualHome w/o correction | SR: 28.33$\pm$1.18 -> 28.14$\pm$2.45 | No clear effect |
| Increase sampled plans from N=25 to N=50 (ablation) | Tree-Planner · VirtualHome with correction | SR: 35.30$\pm$1.78 -> 41.58$\pm$3.20 | Helped |
| Add the gold plan to the action-tree construction (ablation) | Tree-Planner N=25 · VirtualHome with correction | No.EC: 1.85 to 1.21 | Helped |
| Add the gold plan to the action-tree construction (ablation) | Tree-Planner N=50 · VirtualHome with correction | No.EC: 2.04 to 1.39 | Helped |
| Replace grounded deciding with language-guided best-first search (ablation) | Tree-Planner N=50 · VirtualHome w/o correction | SR: 28.14$\pm$2.45 -> 15.06$\pm$1.02 | Hurt |
| Replace grounded deciding with environment-guided best-first search (ablation) | Tree-Planner N=50 · VirtualHome w/o correction | SR: 28.14$\pm$2.45 -> 6.24$\pm$0.65 | Hurt |
| Replace grounded deciding with hybrid best-first search (ablation) | Tree-Planner N=50 · VirtualHome w/o correction | SR: 28.14$\pm$2.45 -> 17.74$\pm$0.69 | Hurt |
Surprising findings
- Increasing the number of sampled plans N does not consistently improve performance; the proportion of correct plans can fall as N grows.
- Missing correct plans in sampling, not grounded deciding, is the largest error source (54.5%).
Limitations
- Small dataset of 35 tasks across 4 VirtualHome scenes.
- Relies on a single proprietary model (text-davinci-003) via API.
- Performance degrades on longer plans (SR 22.22% for plans over 15 steps).
Experimental setup
Datasets: VirtualHome ActivityPrograms-derived tasks (35 tasks across 4 scenes)
Benchmarks: VirtualHome (35 tasks, 4 scenes)
Metrics: executability success rate goal conditions recall cost number of error corrections
Baselines: Zero-shot Planner ProgPrompt Iterative-Planner Local Replan Global Replan
Builds on: ReAct-style iterative planning tree-of-thought VirtualHome
Closest papers by meaning
- Plan-and-Act: Improving Planning of Agents for Long-Horizon Tasks (ICML 2025 · similarity 0.90)
- ToolTree: Efficient LLM Tool Planning via Dual-Feedback Monte Carlo Tree Search and Bidirectional Pruning (ICLR 2026 · similarity 0.89)
- SayCanPay: Heuristic Planning with Large Language Models Using Learnable Domain Knowledge (AAAI 2024 · similarity 0.88)
- Hierarchical Planning for Complex Tasks with Knowledge Graph-RAG and Symbolic Verification (ICML 2025 · similarity 0.88)
- ReCAP: Recursive Context-Aware Reasoning and Planning for Large Language Model Agents (NeurIPS 2025 · similarity 0.88)
- Language Agent Tree Search Unifies Reasoning, Acting, and Planning in Language Models (ICML 2024 · similarity 0.88)
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.