# Analysis of Optimality of Large Language Models on Planning Problems

arXiv: https://arxiv.org/abs/2604.02910 · HTML: https://mlsanity.com/paper/2604.02910/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 25 references that are in the map.
- First posted on arXiv 3 Apr 2026.

## Builds on (most cited first, 13 of 13)

- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [On the Planning Abilities of Large Language Models : A Critical Investigation](https://mlsanity.com/paper/2305.15771/) (2023)
- [LLMs Can't Plan, But Can Help Planning in LLM-Modulo Frameworks](https://mlsanity.com/paper/2402.01817/) (2024)
- [The pitfalls of next-token prediction](https://mlsanity.com/paper/2403.06963/) (2024)
- [Beyond A*: Better Planning with Transformers via Search Dynamics Bootstrapping](https://mlsanity.com/paper/2402.14083/) (2024)
- [The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks](https://mlsanity.com/paper/1401.3839/) (2014)
- [On the Planning Abilities of Large Language Models (A Critical Investigation with a Proposed Benchmark)](https://mlsanity.com/paper/2302.06706/) (2023)
- [The Serial Scaling Hypothesis](https://mlsanity.com/paper/2507.12549/) (2025)
- [Deep sequence models tend to memorize geometrically; it is unclear why](https://mlsanity.com/paper/2510.26745/) (2025)
- [Improving Large Language Model Planning with Action Sequence Similarity](https://mlsanity.com/paper/2505.01009/) (2025)
- [Frontier Large Language Models Rival State-of-the-Art Planners](https://mlsanity.com/paper/2511.09378/) (2025)
- [Enhancing LLM Planning Capabilities through Intrinsic Self-Critique](https://mlsanity.com/paper/2512.24103/) (2025)
- [Benchmark for Planning and Control with Large Language Model Agents: Blocksworld with Model Context Protocol](https://mlsanity.com/paper/2512.03955/) (2025)

## Built on by (most cited first, 1 of 1)

- [Planning with Transformers: Chain of Computation and Structured Context Windows](https://mlsanity.com/paper/2607.17710/) (2026)

## Abstract (arXiv)

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.