LLMs Can Plan Only If We Tell Them
Planning benchmarks have been the standing counterexample to claims about language-model reasoning. On Blocksworld, a domain where blocks are stacked into a target configuration, humans reach roughly 78% accuracy while GPT-4 reaches only about 30%, with Chain-of-Thought prompting offering little to no improvement; in the Logistics domain, where trucks move packages within a city and planes move them between cities, GPT-4's rate of producing valid plans falls to 14%. The usual fix is to wrap the model in an external system — a symbolic verifier that checks each candidate plan and sends failures back for another attempt. That works, but it adds a second system to build and maintain and multiplies the number of API calls per problem.
AoT+ keeps everything inside one prompt. It builds on Algorithm-of-Thoughts, which puts an explicit search trace — exploring a branch, hitting a dead end, backtracking — into the in-context examples so the model imitates searching rather than answering in a straight line. Two changes address where that fell short. First, memoization: the examples label each step with a hierarchical identifier (1., 1.1, 1.2.1) and periodically restate the full world state alongside it, so the model can jump back to any labeled node and read its state directly instead of re-deriving it from the whole trace. This targets a specific failure, state hallucination, where the model issues an action valid for some other state than the one it is actually in. Second, the search traces in the examples are generated rather than hand-written: steps drawn from one successful attempt, interspersed with random jumps between states taken from four failed ones, always terminating in the steps that reach the goal.
The random traces cost essentially nothing in quality — on Game of 24 they score 70.0% against 71.0% for hand-crafted AoT traces, and on crossword puzzles 54.0% against 52.0% — which the authors read as evidence that the gain comes from the shape of the search process, not the specific intuitions written into it. With both changes, GPT-4 reaches 82% on Blocksworld (up from 45% for AoT and 35% for CoT, and level with the 82% of the verifier-based LLM-Modulo) and 80% on Logistics (up from 14% for CoT, and above LLM-Modulo's 70%). An attention analysis on a much smaller model, LLaMA-2-13B-chat, is offered as supporting evidence: the share of attention falling on the accumulated solution steps rather than the problem and goal definitions drops from 86.3% to 27.0% on Blocksworld.
Key results
- On Blocksworld, AoT+ reaches 82% with GPT-4 and 82% with Claude, against 45% and 66% for AoT and 35% and 43% for Chain-of-Thought; the human baseline cited for this benchmark is about 78%, and LLM-Modulo also reaches 82% with GPT-4.
- On Logistics, GPT-4 goes from 14% with CoT to 80% with AoT+, above the 70% of LLM-Modulo, which requires an external verifier and repeated backprompting.
- Randomly generated search traces replace hand-authored ones at almost no cost: 70.0% vs 71.0% on Game of 24, 54.0% vs 52.0% on crosswords, 7.59 vs 7.58 on creative writing.
- Attention measured on LLaMA-2-13B-chat puts less of its mass on the growing solution trace and more on the problem and goal definitions: 86.3% to 27.0% on Blocksworld, 78.5% to 26.3% on List Functions.
BibTeX
@inproceedings{sel2025llms,
title = {{LLM}s Can Plan Only If We Tell Them},
author = {Sel, Bilgehan and Jia, Ruoxi and Jin, Ming},
booktitle = {The Thirteenth International Conference on Learning Representations (ICLR)},
year = {2025}
}