Innate planning abilities of AI models limited in long sliding puzzles
Verifiable Efficiency Limits of Innate LLM Planning in Sliding Puzzles
Artificial Intelligence
Summary
Planning involves figuring out a series of steps to reach a goal, like solving a puzzle. This paper studies how well large language models (LLMs) can plan the entire solution to a sliding puzzle in one go without help from external tools or feedback. The authors create a way to measure planning ability by checking reliability, coordination, and efficiency in the plans generated. They find that even models that always finish still become less efficient when the puzzle gets harder, showing limits in pure, tool-free planning. Their method helps quantify where and how these models struggle with long and complex plans.
What this means in practice
- •For ai system developers: Evaluate and benchmark AI models’ ability to generate complete, efficient plans without external feedback in complex sequence tasks.
- •For game ai programmers: Improve understanding of planning limitations for AI agents in puzzles and strategy games by isolating innate planning deficits.
Authors
Yezhou Cheng, Charles Ling
Abstract
Tool-assisted planning success can reflect external search and verification, leaving a model's unaided planning ability unresolved. We isolate innate planning through complete plans generated in one response without tools or execution feedback. We propose a verifiable framework that decomposes success-weighted plan efficiency as $\mathrm{SPE}=R\times Q\times E$: execution reliability, planning coordination among legal plans, and action economy among completed plans. Trajectory replay and certified optima verify these factors; the joint score includes unsuccessful attempts. We evaluate 8,400 full-plan outputs from seven model conditions on $4\times4$ sliding puzzles, controlling exact horizon and obstacle count in the primary cohort. Models that complete every trial still become less economical at longer horizons, while higher efficiency among completed plans can coexist with poor goal attainment. SPE separates the overall capability hierarchy, while its factors distinguish coordination failure from inefficient completion. The framework makes long-horizon limitations in unaided planning quantitatively verifiable.