滑块拼图中大语言模型内在规划能力的可验证效率极限

# Verifiable Efficiency Limits of Innate LLM Planning in Sliding Puzzles
Source: [https://arxiv.org/html/2610.36415](https://arxiv.org/html/2610.36415)
Charles Ling††thanks:Corresponding author\.Affiliation:Western UniversityEmail:[charles\.ling@uwo\.ca](mailto:)

###### 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 asSPE=R×Q×E\\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 on4×44\\times 4sliding 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\.

## 1Introduction

A long plan must coordinate many actions, preserve their preconditions, and reach a specified final state\. An early mistake can invalidate later actions; a legal sequence can still stop short or waste effort\. Evaluating only success or only the length of successful solutions leaves these distinctions unresolved\.

PlanBench evaluates valid and cost\-optimal plans\([Valmeekam et al\., 2023](https://arxiv.org/html/2610.36415#bib.bib3)\)\. Puzzle evaluations examine accuracy across complexity\([Shojaee et al\., 2025](https://arxiv.org/html/2610.36415#bib.bib2)\), while[Schepanowski and Ling \(2025\)](https://arxiv.org/html/2610.36415#bib.bib1)report invalid moves, noncompletion, and actual versus optimal solution lengths\. These established quantities motivate a more specific question:*where does planning fail when successful\-path efficiency and overall success disagree?*We propose a verifiable framework that couples a conditional three\-level decomposition with exact\-horizon and obstacle controls\. It connects overall performance with the requirement that fails, while retaining unsuccessful attempts in efficiency comparisons\.

We evaluate complete plans for ordinary and blocked sliding puzzles\. The evaluator replays each action and compares completed plans with a certified optimum\. Exact shortest length provides a common horizon scale\. A balanced grid of lengths and obstacle counts separates a longer minimum plan from a changed movement graph\. Increasing the number of blocks is not assumed to increase difficulty: it also removes tiles and changes the available routes\.

The framework decomposes success\-weighted plan efficiency asSPE=R×Q×E\\mathrm\{SPE\}=R\\times Q\\times E: execution reliability, planning coordination, and action economy\. Nested conditioning separates invalid execution, legal noncompletion, and inefficient completion\. SPE compares overall performance; its factors explain the deficit\.*Innate planning*means one response without external search, tools, execution feedback, or repair\.

## 2Verifiable Full\-Plan Evaluation

### 2\.1Tasks and exact horizon control

A board contains one blank, numbered tiles, andk∈\{0,1,2,3\}k\\in\\\{0,1,2,3\\\}fixed blocked cells\. An actionU,D,L,U,D,L,orRRmoves the blank by one cell and swaps it with the adjacent tile\. Entering a block or leaving the board is illegal\. The goal lists numbered tiles in ascending row\-major order across available cells, with the blank last\. The model receives the initial and goal boards and returns the entire move sequence\. No intermediate board states or shortest paths are supplied\.

The primary cohort contains 320 distinct boards: 20 for each cell ofk∈\{0,1,2,3\}k\\in\\\{0,1,2,3\\\}crossed withd∗∈\{10,20,30,40\}d^\{\*\}\\in\\\{10,20,30,40\\\}\. Within each cell, boards are balanced across the selected layouts \(Appendix[A](https://arxiv.org/html/2610.36415#A1)\)\. Obstacle count is balanced within each certified primary horizon; detailed comparisons are reported in Appendix[C](https://arxiv.org/html/2610.36415#A3)\. A separate cohort contains 80 boards atd∗∈\{50,60\}d^\{\*\}\\in\\\{50,60\\\}andk∈\{2,3\}k\\in\\\{2,3\\\}, again with 20 per cell\. The stress cohort changes obstacle composition; it is not pooled into the primary horizon comparison\.

Each optimum has a checkable certificate\. Leth⁡\(s\)h\(s\)be the sum of shortest free\-cell graph distances from each numbered tile to its goal cell\. Every action moves exactly one tile along an edge, so it can reducehhby at most one; any solution needs at leasth⁡\(s\)h\(s\)moves\. We retain boards with a legal goal\-reaching witness of lengthh⁡\(s\)h\(s\)\. The lower and upper bounds agree, certifyingd∗=h⁡\(s\)d^\{\*\}=h\(s\)without trusting the model\. A separate implementation verifies the graph distances and replays the witnesses for all 400 boards\.

This construction controls exact horizon but selects a restricted family: an optimal solution can reducehhat every step\. It therefore tests coordination of long sequences without adding the distinct challenge of mandatory heuristic retreat\. More general boards require an exact search oracle and are outside this cohort\.

### 2\.2Three levels of verifiable limitation

For outputjj, letLjL\_\{j\}be its action count andSj=1S\_\{j\}=1if the entire sequence is legal and ends at the goal\. The verifier stops at the first illegal action without skipping or repairing it;Bj=1B\_\{j\}=1denotes such an error\. Completion, legal noncompletion, and illegal plans partition all outputs\. Reaching the goal partway through a sequence is insufficient\. WithNNoutputs, completion and plan\-level illegality are

C=1N​∑jSj,I=1N​∑jBj\.C=\\frac\{1\}\{N\}\\sum\_\{j\}S\_\{j\},\\qquad I=\\frac\{1\}\{N\}\\sum\_\{j\}B\_\{j\}\.\(1\)
#### Execution reliability\.

R=1−IR=1\-Imeasures the fraction of wholly legal plans\. This audits explicit transition rules, rather than an action\-level error probability\.

#### Planning coordination\.

Q=C/RQ=C/Rmeasures goal attainment among legal plans: can executable actions form a complete goal\-directed sequence? Conditioning on legality separates this behavioral deficit from execution errors\. It does not identify an internal cognitive mechanism\.QQis undefined if no plan is legal\.

#### Action economy\.

EEis the meandj∗/Ljd\_\{j\}^\{\*\}/L\_\{j\}among completed plans\. We also report mean excess moves against the certified optimum:

G=∑j:Sj=1\(Lj−dj∗\)∑jSj\.G=\\frac\{\\sum\_\{j:S\_\{j\}=1\}\(L\_\{j\}\-d\_\{j\}^\{\*\}\)\}\{\\sum\_\{j\}S\_\{j\}\}\.\(2\)EEandGGare undefined if no plan succeeds\. Failed plans have no optimal gap; assigning them zero would reward failure\.OOdenotes optimal completions over all outputs\. Appendix[C](https://arxiv.org/html/2610.36415#A3)retains completion, optimal\-completion, and illegal\-plan rates\.

To compare overall performance, define success\-weighted plan efficiency:

SPE=1N​∑j\{dj∗/Lj,Sj=1,0,Sj=0\.\\mathrm\{SPE\}=\\frac\{1\}\{N\}\\sum\_\{j\}\\begin\{cases\}d\_\{j\}^\{\*\}/L\_\{j\},&S\_\{j\}=1,\\\\ 0,&S\_\{j\}=0\.\\end\{cases\}\(3\)WhenC\>0C\>0,SPE=R×Q×E=C×E\\mathrm\{SPE\}=R\\times Q\\times E=C\\times Eexactly\. The nested denominators cancel: legal plans over all outputs, completed plans over legal plans, and mean economy among completions\. This identity requires no independence assumption\. It satisfies0≤SPE≤C≤10\\leq\\mathrm\{SPE\}\\leq C\\leq 1\. Its components show which requirement limits overall performance\.

### 2\.3Matched conditions and uncertainty

We compare Astra, Fable 5, Opus 5\.5, GPT\-5\.6 Sol, Claude Sonnet 5\.5, GPT\-5\.6 Luna, and Claude Haiku 4\.5 on identical boards, with three trials per board\. Each condition has 960 primary outputs and 240 stress outputs, for 8,400 total\. The protocol requests the shortest complete plan in a fresh context, with no tools or feedback; Appendix[B](https://arxiv.org/html/2610.36415#A2)gives the prompt specification\. Figures and tables use the family name and version\. All substantive failures are retained\.

We report 95% percentile bootstrap intervals from 5,000 draws\. Whole boards are resampled within each block\-count–depth cell, keeping their three trials together and preserving the balanced design\. The same sampled board indices are used across conditions\. These intervals characterize variation within the sampled design; zero observed errors do not certify zero population error probability\.

Table 1:Primary results pooled overd∗∈\{10,20,30,40\}d^\{\*\}\\in\\\{10,20,30,40\\\}\(320 boards, three trials per condition\)\.RRuses all 960 outputs;QQuses legal outputs;EEandGGuse completed outputs\. Joint SPE equalsR​Q​ERQEbefore rounding and includes every failure\. Higher economy among completed plans can coexist with lower joint SPE\.![Refer to caption](https://arxiv.org/html/2610.36415v1/horizon-metrics.png)Figure 1:Three factors ofSPE=R×Q×E\\mathrm\{SPE\}=R\\times Q\\times Eacross certified horizons, with one row per model\. All factors are shown as percentages to one decimal;EEis meand∗/Ld^\{\*\}/Lamong 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\)\.QQconditions on legal plans\.

## 3Results

### 3\.1Execution, coordination, and economy separate limits

Table[1](https://arxiv.org/html/2610.36415#S2.T1)separates the three requirements\. Astra, Fable 5, and Opus 5\.5 haveR=Q=1R=Q=1: every output is legal and reaches the goal\. Their economy is 0\.830, 0\.807, and 0\.745, with primary gaps of 8\.33, 9\.65, and 13\.01 moves\. Identical execution and coordination therefore conceal differences in action economy\.

Sol 5\.6 and Sonnet 5\.5 retain execution reliability of 98\.3% and 98\.2%, but only 85\.0% and 85\.7% of their legal plans reach the goal\. Their economy is 0\.558 and 0\.541, with gaps of 28\.44 and 30\.52 moves\. Both goal coordination and economical completion limit them\.

Luna 5\.6 and Haiku 4\.5 have reliability of 95\.2% and 96\.6%, but coordination of only 63\.0% and 58\.0%\. Economy among completions is 0\.629 and 0\.615\. Legal noncompletion exposes a further limitation after execution errors have been excluded\.

### 3\.2Longer horizons expose coordination and economy limits

Figure[1](https://arxiv.org/html/2610.36415#S2.F1)comparesRR,QQ, andEEwhile keeping primary obstacle proportions fixed\. Sol 5\.6’s coordination falls from 94\.2% atd∗=10d^\{\*\}=10to 76\.6% atd∗=40d^\{\*\}=40; Sonnet 5\.5’s falls from 92\.5% to 79\.5%\. Their economy also falls: 0\.710 to 0\.350 for Sol 5\.6, and 0\.690 to 0\.340 for Sonnet 5\.5\.

Luna 5\.6’s coordination falls from 85\.2% to 41\.7%; Haiku 4\.5’s falls from 80\.4% to 31\.9%\. Atd∗=40d^\{\*\}=40, most legal attempts therefore fail to reach the goal\. Their economy also declines, but remains above Sol 5\.6 and Sonnet 5\.5 at every primary depth\. This conditional advantage describes completed attempts; it does not erase legal noncompletion\.

Astra, Fable 5, and Opus 5\.5 retainR=Q=1R=Q=1at every tested length\. TheirEEfalls from 0\.820, 0\.790, and 0\.730 at length 30 to 0\.630, 0\.600, and 0\.540 at length 40\. Opus 5\.5 has lower economy than Astra and Fable 5 at every primary depth\. Perfect completion thus coexists with a measurable decline in relative action efficiency\.

For an illustrative whole\-plan reliability target, letH\.9H\_\{\.9\}be the largest tested primary length withC≥90%C\\geq 90\\%at every tested length up to it\. Astra, Fable 5, and Opus 5\.5 qualify through 40; Sol 5\.6 and Sonnet 5\.5 through 10\. Luna 5\.6 and Haiku 4\.5 do not qualify at the shortest tested length\. These finite\-grid summaries do not imply impossibility on longer individual boards\.

### 3\.3Joint scores reveal the overall capability hierarchy

Primary joint scores are 0\.830, 0\.807, and 0\.745 for the stronger conditions; 0\.466 and 0\.456 for the intermediate conditions; and 0\.377 and 0\.344 for the lower\-tier conditions\. The product of execution reliability, planning coordination, and action economy makes the overall hierarchy explicit\.

Luna 5\.6 and Haiku 4\.5 have higher conditional economy \(0\.629 and 0\.615\) than Sol 5\.6 and Sonnet 5\.5 \(0\.558 and 0\.541\), but remain below the stronger conditions\. Their coordination deficits outweigh this conditional advantage, leaving their joint scores lower\. Overall capability and individual conditional metrics need not have identical rankings\.

Success\-only summaries also select different boards\. The primary mean depth is 25; completed Luna 5\.6 and Haiku 4\.5 outputs average 21\.9 and 21\.4\. Shorter boards are overrepresented among their successes\. Their depth\-specific economy advantage over the intermediate conditions shows that this selection is not the sole source of the conditional ranking\.

The separate blocked stress cohort reinforces this distinction\. Astra, Fable 5, and Opus 5\.5 again have perfect completion, with gaps of 70\.83, 80\.28, and 99\.22 moves\. Sol 5\.6 and Sonnet 5\.5 complete 64\.2% and 67\.1%, with gaps of 182\.45 and 188\.50\. Luna 5\.6 and Haiku 4\.5 complete only 10\.0% and 11\.7%\. Their economy remains above the intermediate conditions, but their joint scores remain lower\. Changed obstacle composition prevents attributing the primary\-to\-stress difference solely to horizon\.

## 4Discussion and Conclusion

Assessing innate planning requires separating a model’s unaided performance from external assistance\. Our single\-response protocol makes this separation explicit, and our verifiable framework quantifies the resulting limitations throughSPE=R×Q×E\\mathrm\{SPE\}=R\\times Q\\times E\. Trajectory replay verifies execution reliability and goal coordination; certified optima verify action economy\. SPE measures overall performance, while its factors identify which requirement limits it\.

The results show why this joint diagnosis matters\. Astra, Fable 5, and Opus 5\.5 complete every plan yet lose action economy at longer horizons\. Sol 5\.6 and Sonnet 5\.5 lose both coordination and economy\. Luna 5\.6 and Haiku 4\.5 attain slightly higher economy than these intermediate conditions, but greater coordination deficits yield lower SPE\. Completion and action efficiency thus expose distinct planning limits\. The contribution is the unified diagnostic framework and its controlled, verifiable evaluation design\.

Future work will extend the framework to planning games such as Sokoban, using domain\-specific transition verifiers and certified optima to test whether the same diagnoses transfer beyond sliding puzzles\. Paired evaluations of unaided and tool\-assisted planning on identical instances can then identify which factors external support improves\. These extensions connect the limits of unaided planning to the mechanisms that help overcome them\.

## Limitations

#### Deployment costs\.

Our framework evaluates planning performance in action space\. Token consumption, response latency, and monetary cost could complement this evaluation when deployment efficiency is of interest\.

#### Trajectory detail\.

Additional trajectory diagnostics, such as first\-error positions and repeated\-state visits, could provide finer descriptions of observed behavior\. These extensions would enrich the analysis while preserving the definitions and exact decomposition of SPE\.

#### Model coverage\.

The current evaluation covers a selected set of model families\. Extending the comparison to additional families, including open\-weight models, would broaden the empirical coverage and support comparisons across model scales and deployment settings\. These models can be evaluated using the same verification protocol and SPE decomposition\.

## References

- Schepanowski and Ling \(2025\)Charles Schepanowski and Charles Ling\. 2025\.[On the limits of innate planning in large language models](https://arxiv.org/abs/2511.21591)\.*Preprint*, arXiv:2511\.21591\.
- Shojaee et al\. \(2025\)Parshin Shojaee, Iman Mirzadeh, Keivan Alizadeh, Maxwell Horton, Samy Bengio, and Mehrdad Farajtabar\. 2025\.[The illusion of thinking: Understanding the strengths and limitations of reasoning models via the lens of problem complexity](https://arxiv.org/abs/2506.06941)\.*Advances in Neural Information Processing Systems*\.
- Valmeekam et al\. \(2023\)Karthik Valmeekam, Matthew Marquez, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambhampati\. 2023\.[Planbench: An extensible benchmark for evaluating large language models on planning and reasoning about change](https://arxiv.org/abs/2206.10498)\.*Advances in Neural Information Processing Systems*\.

## Appendix ABoard Construction and Certificates

Blocked positions below use zero\-based row\-major indexing\. The primary cohort has 20 boards at each block\-count–depth cell:

- •k=0k=0: no blocks; 20 boards per depth\.
- •k=1k=1: positions\{5\},\{6\},\{9\},\{10\}\\\{5\\\},\\\{6\\\},\\\{9\\\},\\\{10\\\}; five boards per layout and depth\.
- •k=2k=2: positions\{5,10\},\{6,9\}\\\{5,10\\\},\\\{6,9\\\}; ten boards per layout and depth\.
- •k=3k=3: four layouts, with five boards per layout and depth\. The blocked sets are\{5,6,9\}\\\{5,6,9\\\},\{5,6,10\}\\\{5,6,10\\\},\{5,9,10\}\\\{5,9,10\\\}, and\{6,9,10\}\\\{6,9,10\\\}\.

The stress cohort uses the samek=2,3k=2,3layouts and quotas at depths 50 and 60\. All layouts have a connected free\-cell graph\. Goals have15−k15\-knumbered tiles, one blank, and the specified blocks\.

Candidate generation starts at the goal and randomly chooses legal actions that increase the tile graph\-distance sum by one\. Proposals that stop before the target length or duplicate an accepted board are discarded\. Reversing a length\-ddaccepted walk yields a solution of lengthdd, while the initial lower bound is alsodd\. Selection uses seed 20261010\. The retained bank stores initial states, goals, block positions, proposal indices, graph\-distance bounds, and complete certificate paths\. The paths are evaluation data and are excluded from the planning input\.

#### Proof of the lower bound\.

LetVVbe the free cells andδV\\delta\_\{V\}their shortest\-path distance\. For numbered tilett, letptp\_\{t\}be its current cell andqtq\_\{t\}its goal cell\. Seth⁡\(s\)=∑tδV​\(pt,qt\)h\(s\)=\\sum\_\{t\}\\delta\_\{V\}\(p\_\{t\},q\_\{t\}\), excluding the blank\. In a legal move only one tile changes position, across one graph edge\. By the triangle inequality its distance toqtq\_\{t\}decreases by at most one\. Since the goal hash=0h=0, any solution takes at leasth⁡\(s\)h\(s\)actions\. A replayed solution of lengthh⁡\(s\)h\(s\)attains this bound and is therefore shortest\.

## Appendix BProtocol and Verification Specification

Each trial requests a complete shortest plan from the initial state to the explicit goal\. Contexts are independent across boards and trials\. No tools, demonstrations, execution feedback, or oracle values are included\. The response format consists of a single complete move list; the direction convention always refers to the blank\.

You are solving a 4\-by\-4 sliding puzzle\.0 is the blank\. \-1 is a fixed blocked cell\.U/D/L/R move the blank one cell up/down/left/rightand swap it with the adjacent numbered tile\.Never move outside the board or into a blocked cell\.Find a shortest complete sequence reaching the goal\.Return only MOVES: followed by comma\-separated U,D,L,R\.Initial board:\[four rows of integers\]Goal board:\[four rows of integers\]

The verifier reads the explicit move string, checks each target cell, and stops at the first illegal action\. Legal prefixes and first\-error positions remain available for supplementary audits\. A second implementation independently verifies 400 optimum certificates and replays all 8,400 outputs, reproducing every score\. The data retain complete move strings rather than only outcome labels\.

## Appendix CSupplementary Results

Tables[2](https://arxiv.org/html/2610.36415#A3.T2)and[3](https://arxiv.org/html/2610.36415#A3.T3)give primary outcome counts and rates\. Table[4](https://arxiv.org/html/2610.36415#A3.T4)reports completion by block count, averaging equally over the four primary depths\. Tables[5](https://arxiv.org/html/2610.36415#A3.T5)and[6](https://arxiv.org/html/2610.36415#A3.T6)provide stress results and primary uncertainty\. Figure[2](https://arxiv.org/html/2610.36415#A3.F2)contrasts conditional economy with joint performance\.

Figure 2:ConditionalEEand joint SPE on primary boards\. Luna 5\.6 and Haiku 4\.5 have higherEEbut 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\.Table 2:Mutually exclusive primary outcomes, summing to 960 per condition\. The illegal column includes both boundary and obstacle violations\.Table 3:Primary completion, optimal completion, and illegal\-plan percentages\. All three use 960 outputs per condition\.#### Obstacle\-count comparisons\.

At each primary depth, all four block counts are represented\. Table[4](https://arxiv.org/html/2610.36415#A3.T4)shows that Luna 5\.6’s completion is 66\.2% with no blocks and 51\.7% with three; Sol 5\.6’s is 87\.1% and 77\.9%\. Other contrasts are smaller and not uniformly monotonic\. Blocks jointly change tile count and movement topology, so their count alone does not define difficulty\.

Table 4:Primary completion percentages by block count\. Each condition has 240 outputs at each count, balanced across depths\.Table 5:Separate stress cohort: 80 boards, 240 outputs per condition, balanced acrossk=2,3k=2,3andd∗=50,60d^\{\*\}=50,60\. Gap remains conditional on successful completion\.Table 6:Primary 95% percentile intervals from 5,000 stratified whole\-board bootstrap draws\. Random seed is 20261012\. All three trials of each resampled board are kept together\.