Analysis of Optimality of Large Language Models on Planning Problems

Abstract

Classic AI planning problems have been revisited in the LLM era, with a focus of benchmarks on success rates rather than plan efficiency. We examine the degree to which frontier models reason \emph{optimally} versus relying on simple, heuristic, and potentially inefficient strategies. We focus on the Blocksworld domain involving towers of labeled blocks: defined blocks have to be moved from an initial to a goal configuration via a set of primitive actions. In order to isolate true topological reasoning from the use of memorized heuristics, we also introduce a formally equivalent task, the generalized Path-Star ($P^*$) graph from semantic priors. We vary problem depth (the height of block towers), width (the number of towers), and compositionality (the number of goal blocks), and show that reasoning-enhanced LLMs significantly outperform traditional satisficing planners (e.g., LAMA) in complex, multi-goal configurations. Where classical search algorithms hit a combinatorial wall as the search space expands, LLMs track theoretical optimality limits with near-perfect precision across multiple model families, even when domain-specific semantic hints are stripped away using $P^*$-based notation. We consider and find evidence to support two hypotheses behind this performance: 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, bypassing exponential combinatorial complexity.