Verifiable Efficiency Limits of Innate LLM Planning in Sliding Puzzles

1 Introduction

• A long plan can fail through invalid actions, legal noncompletion, or wasted effort, distinctions that success-only or successful-plan-length measures leave unresolved.Source: §1 · p. 1
• The framework asks where planning fails when successful-plan efficiency and overall success disagree, using conditional diagnostics and retaining unsuccessful attempts.Source: §1 · p. 1
• The evaluation uses ordinary and blocked sliding puzzles, replayed trajectories, certified optima, and balanced horizon and obstacle controls.Source: §1 · p. 1
• SPE = R × Q × E separates execution reliability, coordination among legal plans, and action economy among completions; innate planning is tested in one response without tools or feedback.Source: §1 · p. 1

2.1 Tasks and exact horizon control

• 320 primary boards balance obstacle counts across certified horizons; a separate 80-board stress cohort at lengths 50 and 60 is not pooled into primary comparisons.Optimal lengths are certified by matching a graph-distance lower bound with a legal goal-reaching witness; the selected boards permit an optimal solution that reduces the heuristic at every step.Source: §2.1 · p. 2

2.2 Three levels of verifiable limitation

• The verifier counts a plan as complete only if its entire sequence is legal and reaches the goal, partitioning outputs into illegal plans, legal noncompletions, and completions.R measures wholly legal plans; Q measures goal attainment conditional on legality and is undefined when no plan is legal; E is mean certified-optimum-to-plan-length ratio among completions.Source: §2.2 · p. 2
• When completion is nonzero, SPE = R × Q × E = C × E exactly, combining completion and conditional action economy while retaining failures in the overall score.The matched primary results pool four certified horizons; Table 1 defines denominators for R, Q, E, and G and notes that higher completed-plan economy can coexist with lower SPE.Source: §2.2 · p. 2, Table 1 · p. 3

2.3 Matched conditions and uncertainty

• Figure 1 separates primary and stress cohorts and displays R, Q, and E by model across certified horizons, with Q conditioned on legal plans.Source: Figure 1 · p. 3

3.1 Execution, coordination, and economy separate limits

• Astra, Fable 5, and Opus 5.5 complete every plan, while Sol 5.6 and Sonnet 5.5 retain high reliability but lose coordination and economy.Astra, Fable 5, and Opus 5.5 have R = Q = 1 and economy of 0.830, 0.807, and 0.745; Sol 5.6 and Sonnet 5.5 have reliability of 98.3% and 98.2%, coordination of 85.0% and 85.7%, and economy of 0.558 and 0.541. Luna 5.6 and Haiku 4.5 have reliability of 95.2% and 96.6%, coordination of 63.0% and 58.0%, and economy of 0.629 and 0.615.Source: §3.1 · p. 3

3.2 Longer horizons expose coordination and economy limits

• At longer primary horizons, coordination and economy fall for Sol 5.6 and Sonnet 5.5, coordination falls sharply for Luna 5.6 and Haiku 4.5, and economy declines even with perfect completion.Astra, Fable 5, and Opus 5.5 retain R = Q = 1 at every tested length, but their economy falls from 0.820, 0.790, and 0.730 at length 30 to 0.630, 0.600, and 0.540 at length 40. H.9 is an illustrative finite-grid summary: the stronger conditions qualify through 40, Sol and Sonnet through 10, and Luna and Haiku do not qualify at the shortest tested length.Source: §3.2 · pp. 3–4

3.3 Joint 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 intermediate conditions; and 0.377 and 0.344 for lower-tier conditions.Source: §3.3 · p. 4
• Luna 5.6 and Haiku 4.5 have higher conditional economy than Sol 5.6 and Sonnet 5.5, but coordination deficits leave their joint scores lower.Success-only outputs also overrepresent shorter boards for Luna 5.6 and Haiku 4.5: their completed plans average 21.9 and 21.4 moves versus a primary mean depth of 25.Source: §3.3 · p. 4
• In the separate blocked stress cohort, Astra, Fable 5, and Opus 5.5 again complete every plan, while Luna 5.6 and Haiku 4.5 complete only 10.0% and 11.7%.Sol 5.6 and Sonnet 5.5 complete 64.2% and 67.1%; changed obstacle composition prevents attributing the primary-to-stress difference solely to horizon.Source: §3.3 · p. 4

• A single-response protocol without external search, tools, execution feedback, or repair separates innate planning from external assistance.Source: §4 · p. 4
• SPE combines execution reliability, planning coordination, and action economy; its factors identify whether limitations arise in coordination or inefficient completion.The results report perfect completion alongside reduced economy for some models, and higher conditional economy alongside poorer attainment for others.Source: §4 · p. 4
• Future work proposes testing transfer to games such as Sokoban and comparing unaided with tool-assisted planning on identical instances.The proposed extensions would use domain-specific transition verifiers and certified optima.Source: §4 · p. 4

• The framework evaluates planning in action space, leaving token consumption, response latency, and monetary cost as possible complements for deployment-efficiency evaluation.Source: Limitations · p. 5
• The analysis could add first-error positions and repeated-state visits to describe trajectories more finely.Source: Limitations · p. 5
• The evaluation covers selected model families; adding open-weight models could broaden comparisons across model scales and deployment settings.Source: Limitations · p. 5

• The primary cohort uses 20 boards per block-count–depth cell for k = 0, 1, 2, or 3, with blocked layouts balanced within cells.For k = 1, four layouts receive five boards each; k = 2 uses two layouts with ten boards each; k = 3 uses four layouts with five boards each. The stress cohort uses k = 2 and 3 at depths 50 and 60, with connected free-cell graphs.Source: A Board Construction and Certificates · p. 6
• Candidate boards are generated by legal moves that increase tile graph-distance sum by one; reversing an accepted length-d walk provides a length-d solution.Proposals that stop early or duplicate an accepted board are discarded, and certificate paths are excluded from planning input.Source: A Board Construction and Certificates · p. 6
• The sum of numbered-tile distances to their goals is a lower bound on solution length because one move can reduce it by at most one.A replayed goal-reaching solution matching that bound certifies the board's exact shortest length.Source: A Board Construction and Certificates · p. 6

B Protocol and Verification Specification

• Each trial requests a complete shortest plan from the initial state to the explicit goal, without tools or execution feedback.The response is one complete move list, and the direction convention refers to the blank.Source: B Protocol and Verification… · p. 6
• The prompt specifies a 4-by-4 board, blank and blocked-cell notation, legal blank moves, and a comma-separated move-list response.The initial and goal boards are supplied to the model.Source: B Protocol and Verification… · p. 6
• The verifier replays each move, checks target cells, and stops at the first illegal action; an independent implementation verified optimum certificates and replayed all 8,400 outputs.Complete move strings are retained, and every score was reproduced.Source: B Protocol and Verification… · p. 6

C Supplementary Results

• Luna 5.6 and Haiku 4.5 have higher conditional E but lower joint SPE than Sol 5.6 and Sonnet 5.5 on primary boards.SPE includes failures; Figure 2 intervals use stratified whole-board bootstrap resampling with the three trials kept together.Source: Figure 2 · p. 7
• Tables 2 and 3 report mutually exclusive primary outcome counts and primary completion, optimal-completion, and illegal-plan percentages, respectively.Table 2 outcomes sum to 960 per condition, and its illegal category includes boundary and obstacle violations; Table 3 rates use 960 outputs per condition.Source: Table 2 · p. 7, Table 3 · p. 7, C Supplementary Results · p. 7
• 66.2% versus 51.7% is Luna 5.6’s completion at zero versus three blocks; Sol 5.6’s corresponding rates are 87.1% versus 77.9%.Other block-count contrasts are smaller and not uniformly monotonic; block count also changes tile count and movement topology.Source: C Supplementary Results · p. 7, Table 4 · p. 7
• Table 5 reports a separate stress cohort of 80 boards and 240 outputs per condition, balanced across k = 2, 3 and d∗= 50, 60; its gap is conditional on successful completion.The stress cohort is distinct from the primary horizon comparison.Source: Table 5 · p. 7, C Supplementary Results · p. 7
• Table 6 reports primary 95% percentile intervals from 5,000 stratified whole-board bootstrap draws, keeping each resampled board’s three trials together.The seed is 20261012.Source: Table 6 · p. 7, C Supplementary Results · p. 7