Verifiable Efficiency Limits of Innate LLM Planning in Sliding Puzzles

Yezhou Cheng, Charles LingarXiv 2026 · arXiv

TL;DR

This paper introduces a verifiable framework to measure the "innate" planning capabilities of Large Language Models (LLMs) by evaluating their performance on sliding puzzles without external tools or feedback. By decomposing success into three distinct factors—execution reliability, planning coordination, and action economy—the authors reveal that even high-performing models struggle with efficiency as task horizons grow, and that a model's ability to reach a goal doesn't always correlate with how efficiently it gets there.

What Problem Does This Paper Address?

Evaluating how well an LLM "plans" is tricky. Often, models use external search tools, verifiers, or iterative feedback loops to solve complex tasks. This masks their innate planning ability—the capacity to formulate a complete, multi-step strategy in a single response.

Existing benchmarks often focus on binary success (did it solve it?) or simple path length. However, these metrics don't tell the whole story. A model might fail because it made an illegal move (execution error), because it wandered aimlessly despite making legal moves (coordination error), or it might succeed but take a wildly circuitous route (inefficiency). The authors aim to provide a mathematically rigorous way to distinguish between these failure modes.

Methods

The researchers propose a new metric called Success-weighted Plan Efficiency (SPE), which decomposes overall performance into a product of three verifiable factors:

  1. Execution Reliability ($R$): The fraction of plans where every single move is legal (e.g., not moving a tile into a wall).
  2. Planning Coordination ($Q$): Among legal plans, what fraction actually reaches the goal state?
  3. Action Economy ($E$): For successful plans, how close was the path length to the certified optimum (the shortest possible solution)?

The formula is expressed as: $SPE = R \times Q \times E$.

To ensure the evaluation is "verifiable," the authors used $4 \times 4$ sliding puzzles where they could calculate the exact shortest path (the "certified optimum") for every board. This allowed them to precisely measure the "gap" between a model's plan and the best possible plan.

Datasets

The study evaluated 8,400 full-plan outputs across 400 distinct board configurations:

  • Primary Cohort: 320 boards with varying optimal path lengths ($d^* \in \{10, 20, 30, 40\}$) and obstacle counts ($k \in \{0, 1, 2, 3\}$).
  • Stress Cohort: 80 boards with longer horizons ($d^* \in \{50, 60\}$) to push the models to their limits.

The models tested included a range of high-tier and mid-tier LLMs (referred to by family names like Astra, Fable, Opus, Sol, Sonnet, Luna, and Haiku).

Key Insights and Ideas

  • The "Horizon" Effect: As the required solution length increases, performance doesn't just dip—it often falls off a cliff. Even models that are 100% reliable at 10 moves start losing significant "Action Economy" by 40 moves.
  • Efficiency vs. Success: A surprising finding was that some models (like Luna 5.6 and Haiku 4.5) actually showed better Action Economy on the few puzzles they solved compared to more "reliable" models like Sol 5.6. However, because they failed to coordinate or stay legal so often, their overall SPE was much lower.
  • Coordination is the Bottleneck: For mid-tier models, the primary failure point isn't making illegal moves; it's "legal noncompletion"—making valid moves that simply never lead to the goal.
  • Obstacles Change the Map, Not Just Difficulty: Adding blocks to a sliding puzzle doesn't always make it harder; it removes tiles and changes the available routes, sometimes simplifying the search space while lengthening the path.
Figure 1: Three factors of SPE = R × Q × E across certified horizons, with one row per model. All factors are shown as percentages to one decimal; E is mean d∗/L among completions. Blue indicates better values and orange poorer values on each panel’s stated linear scale. The white gutter separates primary cohorts (240 outputs per condition and length) from stress cohorts (120 outputs, only two or three blocks). Q conditions on legal plans.

Key Results

The researchers established a clear capability hierarchy using the SPE metric:

Condition Execution $R$ (%) Coordination $Q$ (%) Economy $E$ (0–1) Joint SPE (0–1)
Astra 100.0 100.0 0.830 0.830
Fable 5 100.0 100.0 0.807 0.807
Opus 5.5 100.0 100.0 0.745 0.745
Sol 5.6 98.3 85.0 0.558 0.466
Sonnet 5.5 98.2 85.7 0.541 0.456
Luna 5.6 95.2 63.0 0.629 0.377
Haiku 4.5 96.6 58.0 0.615 0.344

(Data from Table 1)

While Astra, Fable, and Opus achieved perfect reliability and coordination, their Action Economy varied significantly (0.830 vs 0.745), showing that even "perfect" success masks underlying differences in planning quality.

Figure 2: Conditional E and joint SPE on primary boards. Luna 5.6 and Haiku 4.5 have higher E but lower SPE than Sol 5.6 and Sonnet 5.5. SPE includes all failures. Bars show 95% intervals from stratified whole-board bootstrap resampling, keeping the three trials together.

Limitations and Future Work

  • Deployment Costs: The study focuses on the "action space" (the moves made) but does not account for the computational cost (tokens used, latency) required to generate those plans.
  • Trajectory Granularity: While the framework identifies that a plan failed, it doesn't yet provide a deep diagnostic of where in the sequence the model "lost the plot" (e.g., repeated states or specific heuristic failures).
  • Model Scope: The current evaluation primarily covers closed-weight model families. The authors suggest extending this to open-weight models to see how scale and architecture influence these specific planning factors.
  • Generalization: Future work will look at whether these SPE diagnoses hold true for other planning games like Sokoban.

Summary updated

Abstract

Tool-assisted planning success can reflect external search and verification, leaving a model's unaided planning ability unresolved. We isolate innate planning through complete plans generated in one response without tools or execution feedback. We propose a verifiable framework that decomposes success-weighted plan efficiency as $\mathrm{SPE}=R\times Q\times E$: execution reliability, planning coordination among legal plans, and action economy among completed plans. Trajectory replay and certified optima verify these factors; the joint score includes unsuccessful attempts. We evaluate 8,400 full-plan outputs from seven model conditions on $4\times4$ sliding puzzles, controlling exact horizon and obstacle count in the primary cohort. Models that complete every trial still become less economical at longer horizons, while higher efficiency among completed plans can coexist with poor goal attainment. SPE separates the overall capability hierarchy, while its factors distinguish coordination failure from inefficient completion. The framework makes long-horizon limitations in unaided planning quantitatively verifiable.
BibTeX
@misc{cheng2026verifiable,
  author = {Yezhou Cheng and Charles Ling},
  title = {{Verifiable Efficiency Limits of Innate LLM Planning in Sliding Puzzles}},
  year = {2026},
  eprint = {2610.36415},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.36415},
}
Figure