Verifiable Efficiency Limits of Innate LLM Planning in Sliding Puzzles

Yezhou Cheng; Charles Ling

cs.AIOct 26, 2026

Verifiable Efficiency Limits of Innate LLM Planning in Sliding Puzzles

Authors: Yezhou Cheng, Charles Ling

Organizations: Uber, Inc. · Western University

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.

Figures & tables

Condition	Execution $R$ $\uparrow$	Coordination $Q$ $\uparrow$	Economy $E$ $\uparrow$	Gap $G$ $\downarrow$	Joint SPE $\uparrow$
	(%)	(%)	( $0$ – $1$ )	(moves)	( $0$ – $1$ )
Astra	100.0	100.0	0.830	8.33	0.830
Fable 5	100.0	100.0	0.807	9.65	0.807
Opus 5.5	100.0	100.0	0.745	13.01	0.745
Sol 5.6	98.3	85.0	0.558	28.44	0.466
Sonnet 5.5	98.2	85.7	0.541	30.52	0.456

Table 1: Primary results pooled over

d^{*}\in\{10,20,30,40\}

(320 boards, three trials per condition).

R

uses all 960 outputs;

Q

uses legal outputs;

E

and

G

use completed outputs. Joint SPE equals

RQE

before rounding and includes every failure. Higher economy among completed plans can coexist with lower joint SPE.

Figure 1: Three factors of $\mathrm{SPE}=R\times Q\times 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.

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

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.

Condition	Complete	Legal non-goal	Illegal
Astra	960	0	0
Fable 5	960	0	0
Opus 5.5	960	0	0
Sol 5.6	802	142	16
Sonnet 5.5	808	135	17
Luna 5.6	576	338	46

Appendix

Table 2: Mutually exclusive primary outcomes, summing to 960 per condition. The illegal column includes both boundary and obstacle violations.

Condition	$C$ (%)	$O$ (%)	$I$ (%)
Astra	100.0	26.7	0.0
Fable 5	100.0	24.0	0.0
Opus 5.5	100.0	10.1	0.0
Sol 5.6	83.5	0.0	1.7
Sonnet 5.5	84.2	0.0	1.8
Luna 5.6	60.0	0.0	4.8

Appendix

Table 3: Primary completion, optimal completion, and illegal-plan percentages. All three use 960 outputs per condition.

Condition	$k=0$	$k=1$	$k=2$	$k=3$
Astra	100.0	100.0	100.0	100.0
Fable 5	100.0	100.0	100.0	100.0
Opus 5.5	100.0	100.0	100.0	100.0
Sol 5.6	87.1	86.2	82.9	77.9
Sonnet 5.5	84.2	85.4	83.8	83.3
Luna 5.6	66.2	65.0	57.1	51.7

Appendix

Table 4: Primary completion percentages by block count. Each condition has 240 outputs at each count, balanced across depths.

Condition	$C$ (%)	$I$ (%)	$G$ (moves)	SPE
Astra	100.0	0.0	70.83	0.450
Fable 5	100.0	0.0	80.28	0.420
Opus 5.5	100.0	0.0	99.22	0.370
Sol 5.6	64.2	4.2	182.45	0.152
Sonnet 5.5	67.1	5.4	188.50	0.155
Luna 5.6	10.0	10.4	129.58	0.029

Appendix

Table 5: Separate stress cohort: 80 boards, 240 outputs per condition, balanced across

k=2,3

and

d^{*}=50,60

. Gap remains conditional on successful completion.

Condition	$C$ interval (%)	$G$ interval (moves)
Astra	$[100.0,100.0]$	$[8.12,8.54]$
Fable 5	$[100.0,100.0]$	$[9.43,9.88]$
Opus 5.5	$[100.0,100.0]$	$[12.73,13.29]$
Sol 5.6	$[81.2,85.7]$	$[27.49,29.35]$
Sonnet 5.5	$[81.8,86.5]$	$[29.58,31.44]$
Luna 5.6	$[57.0,62.9]$	$[17.90,20.31]$

Appendix

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.

LLM Planning

Large language model planning studies how models decompose goals, choose actions, and revise plans under constraints.

See all 142 papers

LeanPlan: Optimal Planning with LLM-Generated Heuristics and Admissibility Proofs
Oct 6, 2026André G. Pereira, Augusto B. Corrêa, Felipe Meneguzzi +1Automated Heuristic Design LLM Planning
Federal University of Rio Grande do Sul Brazil · University of Oxford United Kingdom · University of Aberdeen United Kingdom +1
Agent Planning Benchmark: A Diagnostic Framework for Planning Capabilities in LLM Agents
Jun 3, 2026Haoyu Sun, Wenxuan Wang, Mingyang Song +5Tool-Augmented Language Model Agents LLM Agent Evaluation
Tongji University · Shanghai AI Laboratory · Harbin Institute of Technology +5
A complementary study on PlanGPT: Evaluation with defined Performance Metrics and comparison with a planner
Jun 9, 2026Youssef Abdelkader, Humbert Fiorino, Damien PellierLLM Planning
Univ. Grenoble Alpes - LIG Grenoble, France

Oct 6, 2026J/K move · Enter open · S save

LeanPlan: Optimal Planning with LLM-Generated Heuristics and Admissibility Proofs

André G. Pereira, Augusto B. Corrêa, Felipe Meneguzzi, Jendrik Seipp

Federal University of Rio Grande do Sul Brazil · University of Oxford United Kingdom · University of Aberdeen United Kingdom+1

Automated Heuristic Design LLM Planning Sequential Decision Making Symbolic Planning Formal Verification

Open paper AskPDF arXiv

Frontier large language models (LLMs) can generate heuristic functions that guide search to achieve state-of-the-art performance in satisficing planning, where any plan is acceptable. However, these heuristics are not guaranteed to be admissible and can lead to suboptimal plans. We introduce LeanPlan, the first planning system that finds optimal plans with LLM-generated heuristics whose admissibility is machine-checked. Given a domain description and training tasks, an agentic loop uses planner feedback to iteratively improve a reusable domain-specific heuristic, its admissibility proof and the required domain assumptions. LeanPlan implements the heuristic, its proof and an efficient planner with machine-checked grounding and search in Lean 4. We evaluate LeanPlan on ten domains from the International Planning Competition and three new domains, using test tasks with up to 57 times as many objects as the training tasks. With GPT-5.6 Sol in the agentic loop, we successfully generate heuristics and admissibility proofs for all these domains. With the resulting heuristics, LeanPlan usually expands fewer states than the state-of-the-art Scorpion planner and solves more tasks overall.

Abstract

LLM Planning

Explore similar work

LeanPlan: Optimal Planning with LLM-Generated Heuristics and Admissibility Proofs

Agent Planning Benchmark: A Diagnostic Framework for Planning Capabilities in LLM Agents

A complementary study on PlanGPT: Evaluation with defined Performance Metrics and comparison with a planner