Research map / Large language models / Agents, code and math
LLMs Can Plan Only If We Tell Them
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 AoT+, a single-query prompting method that adds periodic state restatement (memoization) and random solution-trace examples to Algorithm-of-Thoughts, reporting strong autonomous planning results on Blocksworld, Logistics, List Functions and ACRE.
Problem
LLMs struggle with long-horizon autonomous planning (e.g., Blocksworld, Logistics) and state tracking, and existing improvements rely on costly external verifiers or iterative backprompting.
Approach
Extends Algorithm-of-Thoughts with periodic restating/caching of the problem state (memoization with x.y.z identifiers) to reduce state hallucination, and replaces human-crafted search traces with random trajectories that always end in a goal-reaching successful path, all within a single prompt.
Key results
- On Blocksworld, AoT+ reaches 82% with GPT-4 and 82% with Claude, versus 35% for CoT and 82% for LLM-Modulo with GPT-4, exceeding the reported 78% human baseline.
- On Logistics with GPT-4o, AoT+ reaches 70% versus 34% for AoT and 56% for LLM-Modulo.
- AoT+ uses about 5.6k total tokens on Logistics with GPT-4 versus about 23k for LLM-Modulo, and LLM-Modulo takes over 6x longer in execution time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use AoT+ instead of LLM-Modulo | GPT-4 · Blocksworld | accuracy (%): 82 vs 82 | No clear effect |
| Use AoT+ instead of LLM-Modulo | GPT-4 · Logistics | accuracy (%): 70 -> 80 | Helped |
| Use AoT+ instead of LLM-Modulo | GPT-4 · List Functions | accuracy (%): 70 -> 84 | Helped |
| Use AoT+ instead of LLM-Modulo | GPT-4 · ACRE | accuracy (%): 52 -> 72 | Helped |
| Use random solution traces instead of human intuitions (ablation) | AoT, GPT-4 · Blocksworld | accuracy (%): 45 -> 44 | No clear effect |
| Add memoization (ablation) | AoT, GPT-4 · Blocksworld | accuracy (%): 45 -> 84 | Helped |
| Use random solution traces instead of human intuitions (ablation) | AoT, GPT-4 · Logistics | accuracy (%): 24 -> 24 | No clear effect |
| Add memoization (ablation) | AoT, GPT-4 · Logistics | accuracy (%): 24 -> 80 | Helped |
| Use random solution traces instead of human intuitions (ablation) | AoT, GPT-4 · List Functions | accuracy (%): 58 -> 56 | No clear effect |
| Add memoization (ablation) | AoT, GPT-4 · List Functions | accuracy (%): 58 -> 84 | Helped |
| Use random solution traces instead of human intuitions (ablation) | AoT, GPT-4 · ACRE | accuracy (%): 46 -> 46 | No clear effect |
| Add memoization (ablation) | AoT, GPT-4 · ACRE | accuracy (%): 46 -> 70 | Helped |
Surprising findings
- Random solution trajectories (AoT+R) perform nearly the same as human-crafted AoT examples, suggesting the structure of the search process matters more than the heuristics.
- The memoization component (AoT+M) accounts for most of the gain, while the random-trajectory component alone leaves performance near AoT.
Limitations
- Gains depend on the model; AoT+ is not consistently best on all models (e.g., LLM-Modulo leads on some List Functions results with Gemini).
- Baseline comparisons to LLM-Modulo rely on its original codebase and GPT-4 optimization, which the authors note may bias results.
- State error analysis uses a single model (LLaMA 3.1 70B) on 200 Logistics games.
Experimental setup
Datasets: Blocksworld Logistics List Functions ACRE
Benchmarks: Blocksworld Logistics List Functions ACRE
Metrics: accuracy token count state error rate
Baselines: CoT CoT-SC Tree of Thoughts AoT LLM-Modulo Self-Refine Tree-Planner
Builds on: Algorithm-of-Thoughts Chain-of-Thought Tree of Thoughts LLM-Modulo Self-Refine
Closest papers by meaning
- Planning in the Dark: LLM-Symbolic Planning Pipeline Without Experts (AAAI 2025 · similarity 0.92)
- Large Language Models as Planning Domain Generators (Student Abstract) (AAAI 2024 · similarity 0.91)
- LLMs Can Reason Faster Only If We Let Them (ICML 2025 · similarity 0.91)
- Graph-enhanced Large Language Models in Asynchronous Plan Reasoning (ICML 2024 · similarity 0.91)
- Non-myopic Generation of Language Models for Reasoning and Planning (ICLR 2025 · similarity 0.91)
- Can LLMs Fix Issues with Reasoning Models? Towards More Likely Models for AI Planning (AAAI 2024 · similarity 0.91)
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.