On the Limits of Innate Planning in Large Language Models

Quick Overview

Large Language Models (LLMs) fundamentally struggle with long-term planning because they rely on predicting the next token rather than maintaining a consistent internal state, as demonstrated by their failure to solve the 8-puzzle consistently without explicit guidance, often resorting to looping or taking costly, counterproductive moves.

Key Points: LLMs struggle with planning tasks like the 8-puzzle, failing to maintain a perfect picture of the board state, leading to invalid moves. The 8-puzzle, which requires 31 moves for the optimal solution, was frequently attempted by models like GPT-5 thinking, resulting in non-optimal moves or getting stuck in loops. When given explicit step-by-step instructions (Chain-of-Thought), GPT-5 thinking achieved 68% success, while the smaller GPT-5 Mini achieved 30% success. The core issue is that LLMs lack a reliable internal state tracker, causing them to forget the board state and make moves that violate simple rules. When tested on the 8-puzzle with only the prompt (zero-shot), all tested models, including the larger ones, solved zero puzzles. The research suggests that the fundamental limitation is the architecture's reliance on sequential token prediction rather than robust, recursive planning mechanisms. The cost of solving one 8-puzzle instance via API calls was estimated to be around $75,284 tokens, highlighting the inefficiency of brute-force methods.

Context: This video discusses the inherent limitations of current Large Language Models (LLMs) in performing complex, sequential planning tasks, using the classic 8-puzzle as a benchmark. The 8-puzzle requires maintaining a consistent, internal representation of the board state across multiple steps to find the optimal solution. The speakers contrast the performance of different models (GPT-5 thinking, GPT-5 Mini) under various prompting strategies (zero-shot, Chain-of-Thought) to illustrate this fundamental architectural constraint.

Detailed Analysis

The core finding of the research discussed is that LLMs fundamentally lack the ability to maintain a consistent internal state required for complex, long-term planning, which manifests as a failure in solving simple problems like the 8-puzzle. When given the 8-puzzle in a zero-shot setting, all models, including advanced ones like GPT-5 thinking, failed completely, resulting in zero solutions solved. When Chain-of-Thought (CoT) prompting was applied, GPT-5 thinking achieved 68% success, and GPT-5 Mini achieved 30% success. Crucially, the most powerful model, GPT-5 thinking, still failed entirely when relying solely on its raw, unguided reasoning (no external planning tools), suggesting a deep architectural flaw. When researchers tried to remedy this by providing explicit step-by-step instructions (the external move validator approach), the performance jumped to 100% success, proving the issue is planning, not raw intelligence. The failure mode involved loops, moving tiles to invalid locations, or simply forgetting the board state. The cost of failure is high, with one puzzle taking an estimated 75,284 tokens to solve via brute force, and the discussion concludes that future AI development must focus on new architectures or mechanisms beyond just larger models to achieve reliable, long-term autonomy.