Analysis of Optimality of Large Language Models on Planning Problems

1. Problem Statement

The paper addresses a critical gap in the evaluation of Large Language Models (LLMs) for autonomous planning. While recent benchmarks (e.g., Blocksworld) have shown that frontier LLMs can achieve high success rates, they often obscure plan quality and structural reasoning capabilities.

• Core Question: Do LLMs genuinely reason through complex planning problems to find optimal solutions, or do they rely on simple heuristics, semantic priors, and approximate retrieval that degrade as complexity scales?
• Domain: The study focuses on the Blocksworld domain (moving labeled blocks between towers) and its topological isomorphism to a generalized Path-Star ($P^*$) graph.
• Challenge: Traditional benchmarks measure binary success/failure. This paper investigates the optimality of plans and the limits of LLM reasoning when faced with exponential search spaces, specifically testing whether models can navigate the $P^*$ topology without relying on domain-specific semantic hints (like "gravity" or "stacking").

2. Methodology

A. Structural Isomorphism ($P^*$ Topology)

The authors formalize the Blocksworld problem as a Path-Star ($P^*$) graph:

• The "Table" acts as the central root node.
• Each vertical stack of blocks constitutes a disjoint branch radiating from the root.
• Solving the problem is equivalent to traversing these branches to identify goal blocks, clearing dependencies (unstacking), and reassembling them.
• Abstract Graph Reformulation: To isolate true topological reasoning from semantic priors, the authors created an isomorphic Graph-Rewriting task. This removes physical semantics (e.g., "unstack," "table") and replaces them with abstract graph operations (e.g., DETACH_NODE, ATTACH_TO_ROOT), forcing the model to rely purely on structural logic.

B. Experimental Design (Curricula)

A synthetic dataset was generated with four distinct complexity axes, parameterized by Tower Width ($W$), Height ($H$), and Goal Count ($S$):

1. High Towers: Scales depth ($H$ up to 1000) with fixed width ($W=12$). Tests long-horizon reasoning.
2. Harvest: Scales width ($W$ up to 207) with fixed height. Tests the ability to sequence multiple independent subgoals.
3. Interleaved Harvest: Each tower contains two interleaved goal blocks, creating cross-tower dependencies that prevent simple decomposition.
4. Grand Challenge: Simultaneously scales $W$, $H$, and $S$ to test holistic generalization.

C. Models and Metrics

• Models Evaluated:
  • Gemini 3.0 Pro: A reasoning-enhanced LLM capable of "Chain-of-Thought" (CoT) and latent reasoning tokens.
  • LAMA-2011: A classical satisficing planner (trades optimality for speed).
  • A/LM-Cut:* A classical optimal planner (guarantees shortest path but exhausts memory).
• Metrics:
  • Success Rate: Validity of the plan (verified by VAL).
  • Optimality Gap: The deviation of the generated plan cost from the theoretical optimal cost ($C_{opt}$).
  • Inference-Time Compute: Analysis of "thinking tokens" (reasoning tokens) used by the LLM.

3. Key Contributions

1. Multi-Scenario $P^*$ Problem Space: Introduced a systematic taxonomy isolating depth, width, and compositionality to stress-test planning capabilities beyond standard benchmarks.
2. Optimality Inversion: Demonstrated a counter-intuitive finding where LLMs outperform classical planners in optimality at high complexity. While classical optimal planners (A*) hit a "hard wall" (memory explosion) and satisficing planners (LAMA) degrade in quality, LLMs track theoretical optimality limits with near-perfect precision until they hit a zone of intermittent failure.
3. Mechanism Analysis (Simulation vs. Geometry): Proposed and provided evidence for two hypotheses explaining LLM success:
   • Active Algorithmic Simulation: The model executes a step-by-step symbolic procedure (serial search) using reasoning tokens as working memory.
   • Geometric Memory: The model may utilize latent spatial representations to navigate the $P^*$ topology efficiently ($O(1)$ lookup).
4. Failure Mode Characterization: Distinguished between the "hard wall" failures of classical search (exhaustion) and the "instability zones" of LLMs (binary shift from perfect optimality to total failure without gradual degradation).

4. Key Results

• Superiority in Complex Regimes:
  • Classical Planners: A*/LM-Cut failed on all instances across all curricula within the 60-second time limit. LAMA-2011 failed or produced highly suboptimal plans once the number of goals exceeded ~25 or tower height increased significantly.
  • LLM Performance: Gemini 3.0 Pro successfully generated theoretically optimal plans for instances with over 100 goal blocks and tower heights exceeding 500. It tracked the optimal cost line ($C_{opt}$) almost perfectly.
• Robustness to Semantic Stripping:
  • In the Abstract Graph domain (stripped of Blocksworld semantics), the LLM maintained high performance, proving it relies on structural reasoning rather than memorized heuristics.
  • Interestingly, the Graph formulation sometimes allowed the model to solve harder instances than the standard Blocksworld formulation, suggesting the graph framing unlocks deeper structural reasoning in specific regimes.
• Inference-Time Compute Scaling:
  • A striking linear relationship was found between thinking token count and optimal plan length (approx. 47 tokens per plan step).
  • This supports the Serial Scaling Hypothesis: The model performs a systematic, serial algorithmic simulation where each logical step incurs a constant token cost.
  • Failures occurred when the required token budget exceeded the model's generation limit, resulting in a binary failure rather than a suboptimal shortcut.
• Interleaved Dependencies:
  • In the "Interleaved Harvest" task (where goals are mixed within towers), the LLM's optimality dropped (only 10% optimal vs. 21% in standard Harvest), suggesting it relies on a "clear-and-stack" decomposition strategy that breaks down when dependencies are non-monotonic.

5. Significance and Conclusion

This paper fundamentally shifts the understanding of LLM planning capabilities:

• Beyond Feasibility: It proves that frontier LLMs do not just "get lucky" with valid plans; they can achieve mathematical optimality in domains where classical search algorithms fail due to combinatorial explosion.
• Mechanism of Reasoning: The evidence strongly suggests LLMs act as serial algorithmic simulators, using reasoning tokens to linearize complex dependency chains. The efficiency of this process implies a potential latent "geometric" understanding of the problem topology, allowing the model to bypass the exponential search space that traps classical planners.
• Implications: The findings suggest that for specific decomposable topologies (like $P^*$), LLMs can serve as superior planners compared to both optimal and satisficing classical solvers. However, their performance is bounded by a "compute ceiling" (token budget), leading to a distinct failure mode where they stop working entirely rather than degrading gracefully.

Limitations: The study relies on controlled goal placements (mostly one goal per tower) to calculate optimal costs analytically. Future work is needed to test arbitrary goal configurations and other frontier models to see if these scaling laws are universal.