Analysis of Optimality of Large Language Models on Planning Problems

Bernd Bohnet; Michael C. Mozer; Kevin Swersky; Wil Cunningham; Aaron Parisi; Kathleen Kenealy; Noah Fiedel

cs.AIApr 3, 2026

Analysis of Optimality of Large Language Models on Planning Problems

Authors: Bernd Bohnet, Michael C. Mozer, Kevin Swersky, Wil Cunningham, Aaron Parisi, Kathleen Kenealy, Noah Fiedel

Organizations: Google DeepMind

Abstract

Classic AI planning problems have been revisited in the Large Language Model (LLM) era, with a focus of recent benchmarks on success rates rather than plan efficiency. We examine the degree to which frontier models reason optimally versus relying on simple, heuristic, and possibly inefficient strategies. We focus on the Blocksworld domain involving towers of labeled blocks which have to be moved from an initial to a goal configuration via a set of primitive actions. We also study a formally equivalent task, the generalized Path-Star ( $P^*$ ) graph, in order to isolate true topological reasoning from semantic priors. We systematically manipulate problem depth (the height of block towers), width (the number of towers), and compositionality (the number of goal blocks). Reasoning-enhanced LLMs significantly outperform traditional satisficing planners (e.g., LAMA) in complex, multi-goal configurations. Although classical search algorithms hit a wall as the search space expands, LLMs track theoretical optimality limits with near-perfect precision, even when domain-specific semantic hints are stripped away. To explain these surprising findings, we consider (and find evidence to support) two hypotheses: an active Algorithmic Simulation executed via reasoning tokens and a Geometric Memory that allows models to represent the $P^*$ topology as a navigable global geometry, effectively bypassing exponential combinatorial complexity.

Figures & tables

Panel of Figure 1 — Figure 1: Structural Isomorphism between Blocksworld and $P^{*}$ Topology. (a) A standard Blocksworld instance illustrating the initial state (left) and the target goal state (right). The task requires rearranging blocks using four standard atomic actions: unstack, stack, pick-up, and put-down. (b) The corresponding $P^{*}$ graph representation of the initial state. The table serves as the central root node, and each stack of blocks forms a disjoint branch, framing the planning task as a structural path-traversal problem.

Panel of Figure 2 — Figure 2: Scaling Goal Blocks and Tower Height. Gemini 3 Pro vs. LAMA-2011 and the theoretical optimal cost. (a) Increasing goal blocks: plan costs illustrating generalization to retrieving and stacking many goal blocks. (b) Increasing tower height: plan costs for retrieving and unstacking from high towers.

Panel of Figure 3 — Figure 3: Scalability and Compute Allocation. (a) Grand Challenge: plan steps vs. total problem volume ( $h\times w\times s$ ). Gemini 3 Pro tracks optimality into extreme complexities where classical search collapses. (b) Inference-time compute: thinking trace length (tokens) vs. optimal cost $C_{opt}$ . All curricula follow a linear trend ( $\approx$ 47 tokens/step); failed instances (gray crosses) cluster at higher token counts.

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4: Grand Challenge Example. The simplest problem from the Grand Challenge curriculum with initial state (left) and goal state (right).

$W$	$S$	$H$	$C_{\text{opt}}$	LAMA	LM-Cut	Gemini 3 Pro (BW)	Gemini 3 Pro (Graph)
6	2	5–10	22	22	–	22 $\star$	22 $\times$
9	3	6–11	26	26	–	26 $\star$	26 $\star$
11	3	8–13	48	48	–	48 $\star$	48 $\star$
14	4	9–14	52	52	–	52 $\star$	52 $\star$
17	4	11–16	80	80	–	80 $\star$	80 $\star$
20	5	12–17	82	82	–	82 $\star$	82 $\star$

Appendix

Table 1: Grand Challenge: Detailed Results. Each row increases all complexity axes simultaneously. “–” indicates planner failure within 60s. For Gemini 3 Pro,

\star

denotes an optimal valid plan matching

C_{\text{opt}}

;

\times

denotes failure to produce a valid plan. BW = Blocksworld; Graph = isomorphic graph representation.

$W$	$S$	$C_{\text{opt}}$	LAMA	LM-Cut	Gemini 3 Pro (BW)	Gemini 3 Pro (Graph)
4	4	36	36	–	36 $\star$	38 $\checkmark$
9	9	62	62	–	62 $\star$	62 $\star$
14	14	70	94	–	70 $\star$	72 $\checkmark$
19	19	106	186	–	106 $\star$	140 $\checkmark$
24	24	188	284	–	188 $\star$	190 $\checkmark$
29	29	244	–	–	290 $\checkmark$	244 $\times$

Appendix

Table 2: Harvest: Detailed Results. Fixed tower height 5–8, one goal block per tower (

S=W

). “–” indicates planner failure within 60s. For Gemini 3 Pro,

\star

denotes an optimal valid plan matching

C_{\text{opt}}

;

\times

denotes failure to produce a valid plan. BW = Blocksworld; Graph = isomorphic graph representation.

$H$	$C_{\text{opt}}$	LAMA	LM-Cut	Gemini 3 Pro (BW)	Gemini 3 Pro (Graph)
8–13	5	5	5	5 $\star$	5 $\star$
28–33	21	21	–	21 $\star$	21 $\star$
48–53	69	–	–	69 $\star$	69 $\star$
68–73	87	–	–	87 $\star$	87 $\star$
88–93	185	–	–	185 $\star$	185 $\star$
108–113	221	–	–	221 $\star$	221 $\star$

Appendix

Table 3: High Towers: Detailed Results. Fixed width

W{=}12

, one goal block (

S{=}1

), tower height scaled from 8 to 993. “–” indicates planner failure within 60s. For Gemini 3 Pro,

\star

denotes an optimal valid plan matching

C_{\text{opt}}

;

\times

denotes failure to produce a valid plan. BW = Blocksworld; Graph = isomorphic graph representation.

Figure 5: Interleaved Harvest Example (6 towers, 12 goal blocks). Initial state (left) with goal blocks highlighted in gold, and goal tower (right). The scrambled PDDL encoding and cross-tower dependencies make this problem significantly harder for classical planners than the single-goal Harvest.

Towers	Goals	$C_{\text{opt}}$	LAMA	LM-Cut	Gemini 3 Pro
2	4	26	26	–	26	$\star$
4	8	38	38	–	38	$\star$
6	12	82	82	–	82	$\star$
8	16	84	84	–	110	$\checkmark$
10	20	106	106	–	132	$\checkmark$
12	24	152	260	–	182	$\checkmark$

Appendix

Table 4: Interleaved Harvest Results. Towers with height 5–8, two goal blocks per tower. “–” indicates planner failure. For Gemini 3 Pro,

\star

denotes an optimal valid plan matching

C_{\text{opt}}

;

\checkmark

denotes a valid but suboptimal plan confirmed by the VAL validator;

\times

denotes failure to produce a valid plan.

LLM Planning

Large language model planning studies how models decompose goals, choose actions, and revise plans under constraints.

See all 142 papers

Planning with Transformers: Chain of Computation and Structured Context Windows
Jul 20, 2026Ehsan Futuhi, Nathan R. SturtevantLLM Planning Model-Based Planning
Department of Computing Science, University of Alberta · Alberta Machine Intelligence Institute (Amii)
When Planning Problems Become Hard for LLMs: Separating Structural Complexity from Semantic Interpretability
Oct 18, 2026Mayukh Debnath, Adeyinka Adedigba, Rammohan MallipeddiLLM Planning Symbolic Planning
Robotics and Autonomous Systems (AI), Arizona State University, Tempe, USA · Department of Artificial Intelligence, Kyungpook National University, Daegu, South Korea
LeanPlan: Optimal Planning with LLM-Generated Heuristics and Admissibility Proofs
Oct 6, 2026André G. Pereira, Augusto B. Corrêa, Felipe Meneguzzi +1Automated Heuristic Design LLM Planning
Federal University of Rio Grande do Sul Brazil · University of Oxford United Kingdom · University of Aberdeen United Kingdom +1

Jul 20, 2026J/K move · Enter open · S save

Planning with Transformers: Chain of Computation and Structured Context Windows

Ehsan Futuhi, Nathan R. Sturtevant

Department of Computing Science, University of Alberta · Alberta Machine Intelligence Institute (Amii)

LLM Planning Model-Based Planning

Open paper AskPDF arXiv

Large Language Models (LLMs) have had a remarkable impact across many areas of machine learning. However, recent studies have shown that they struggle to reliably solve planning problems, particularly when compared with classical planners. Even with recent advances in reasoning-oriented models, the extent to which LLMs can genuinely perform planning remains an open question. At the same time, theoretical results have shown that transformers, the core architecture underlying modern LLMs, are Turing-complete. In this work, we investigate this apparent gap between the theoretical computational power of LLMs and their empirical planning performance. We propose Chain of Computation (COC), a computational architecture that places a transformer-based LM inside an iterative loop and leverages its strength as a pattern-matching system. COC uses a Structured Context Window (SCW) as external memory, allowing the model to access only the portion of the accumulated context required at each planning step and thereby maintain an approximately constant input size. Within this architecture, the LM learns the planning policy and world model and performs the arithmetic operations required during planning. We show that relatively small LMs trained from scratch can learn planning procedures from a small number of training instances and generalize to unseen problems, achieving success rates above 99% on BlocksWorld and the Pancake puzzle. We further show that COC can be formulated as a pushdown automaton (PDA). This formulation can solve Tower of Hanoi (TOH) instances with up to 20 disks and enables the planner to execute the depth-first search (DFS) algorithm. Theoretically, we characterize how the accumulation of irrelevant context increases planning failure probability under the standard full-context setup and how the SCW mitigates this effect.

Abstract

LLM Planning

Explore similar work

Planning with Transformers: Chain of Computation and Structured Context Windows

When Planning Problems Become Hard for LLMs: Separating Structural Complexity from Semantic Interpretability

LeanPlan: Optimal Planning with LLM-Generated Heuristics and Admissibility Proofs