When Planning Problems Become Hard for LLMs: Separating Structural Complexity from Semantic Interpretability

Mayukh Debnath; Adeyinka Adedigba; Rammohan Mallipeddi

cs.AIOct 18, 2026

When Planning Problems Become Hard for LLMs: Separating Structural Complexity from Semantic Interpretability

Authors: Mayukh Debnath, Adeyinka Adedigba, Rammohan Mallipeddi

Organizations: Robotics and Autonomous Systems (AI), Arizona State University, Tempe, USA · Department of Artificial Intelligence, Kyungpook National University, Daegu, South Korea

Abstract

Large language models (LLMs) struggle with classical planning, but benchmarks rarely distinguish structural difficulty from the difficulty of interpreting symbolic vocabulary. We examine seven STRIPS domains with BFS-optimal plan lengths. For predicting structural difficulty without solving an instance, the zero-training delete-relaxation heuristic $h_{\mathrm{add}}$ outperforms learned alternatives on held-out domains (mean Spearman $|ρ|=0.931$ ), including ridge regression ( $0.707$ ), object count ( $0.657$ ), and the episodic retrieval architecture ARC ( $0.400$ ). ARC also fails to outperform a linear model using the same features. To isolate semantic effects, we progressively rename predicates while preserving states, transitions, and optimal plans. Valid LLM planning success drops from $67.5\%$ to $40.0\%$ between $0\%$ and $100\%$ renaming, while refusals remain at $0\%$ . An LLM supplied with ARC's conditioning information predicts difficulty in context better than trained ARC (mean $|ρ|=0.826$ ). Hybrid routing between an LLM and a symbolic planner depends more on calibration to the target LLM's outcomes than on the structural score selected. Thus, established symbolic heuristics already estimate structural difficulty well; improving hybrid planning requires modeling LLM behavior sensitive to predicate semantics rather than developing more structural predictors.

Figures & tables

Figure 1: ARC architecture. A query instance’s FM embedding is projected to a 128-dimensional query vector via QueryMLP. Support instances’ structural features form keys (KeyMLP); a concatenation of structural and residual FM features forms values. Soft attention retrieves a weighted difficulty summary $\mathbf{z}$ . The fusion head concatenates $\mathbf{x}_{s}^{q}$ , $\mathbf{z}$ and $\mathbf{x}_{r}^{q}$ and produces a regression output (normalized plan length). An optional gate blending the attention output with a linear predictor is evaluated as a variant (Section 4 ).

Method	BW	LOG	MBW	Mean
Object count ( $\|\mathcal{O}\|$ )	0.764	0.544	0.662	0.657
Goal count	0.764	0.969	0.673	0.802
Ridge on $x_{s}$	0.644	0.889	0.587	0.707
Ridge on $x_{s}$ (z-scored target)	0.645	0.889	0.589	0.708
LogME	0.057	0.704	0.478	0.413
H-score	0.648	0.180	0.336	0.388

Table 1: Absolute Spearman correlations between predicted difficulty scores and optimal plan lengths on held-out domains (

N=126

164

133

BFS-solved instances for BW, LOG, MBW). ERM and ARC rows report mean

\pm

std over five seeds; the ensembled ARC row averages the five seeds’ predictions before computing one correlation. Bold marks the overall best row. LogME uses evidence-optimal regularization (

\alpha/\beta=2.358

) rather than a fixed value.

Domain	B1	B2	B3	B4	B5	Mean
Ridge on $x_{s}$ , BW	0.48	0.37	0.58	0.45	0.57	0.49
Ridge on $x_{s}$ , LOG	0.87	0.96	0.96	0.98	n/a	0.94
Ridge on $x_{s}$ , MBW	0.07	0.27	0.24	0.10	0.19	0.17
ARC (main), BW	0.11	0.32	0.22	0.20	0.36	0.24
ARC (main), LOG	0.23	0.36	0.33	0.33	n/a	0.32
ARC (main), MBW	0.15	0.19	0.16	0.17	0.27	0.19

Table 2: Absolute Spearman correlation within fixed object-count groups. B1–B5 are the five generator size levels (object counts

2,3,4,6,8

for BW/MBW and

4,5,6,7,9

for LOG). Group sizes are

N=40,40,24,13,9

(BW),

40,40,40,40,4

(LOG; B5 undefined, two distinct plan lengths),

40,40,28,14,11

(MBW); small groups are noisy. Object count is constant within a group, so its baseline has zero ranking capacity.

Predicate Corruption ( $k$ )	Valid-Plan Success	95% Wilson CI	Refusal Rate
0%	67.5%	[52.0%, 79.9%]	0.0%
25%	62.5%	[47.0%, 75.8%]	0.0%
50%	47.5%	[32.9%, 62.5%]	0.0%
75%	37.5%	[24.2%, 53.0%]	0.0%
100%	40.0%	[26.3%, 55.4%]	0.0%

Table 3: Qwen 2.5-72B performance on progressively corrupted versions of the same 40 BFS-solved Blocksworld instances, validated by a state-simulating executor. Renaming preserves the transition system and optimal plan lengths

n^{\star}(\pi)

Domain	Static	Oracle	$\|\mathcal{O}\|$ -ZS	Goal-ZS	ARC-ZS	$\|\mathcal{O}\|$ -FS	Goal-FS	ARC-FS
Blocksworld (BW)	100.0	100.0	64.0	64.0	73.0	86.0	64.0	99.0
Logistics (LOG)	100.0	100.0	32.0	23.0	50.0	77.0	59.0	99.0
Mystery-BW (MBW)	100.0	100.0	64.0	64.0	65.0	85.0	64.0	100.0

Table 4: Percentage of 100 sampled instances per domain solved under each routing policy, validated by the state-simulating executor. ZS uses a structural score with no target-domain LLM outcomes; FS calibrates the decision threshold on 140 target-domain outcomes. Static and Oracle are both

100\%

because the symbolic fallback always succeeds on these BFS-solvable instances (no time or resource budget is imposed).

Appendix figures & tables17 assets

Supplementary material from the paper’s appendix.

Appendix

Domain	Role	BFS-solved	Solved %	$\|\mathcal{O}\|$	$n^{\star}$ (min/med/max)	$n^{\star}{=}0$
Blocksworld (BW)	test	126	63.0	2–8	0/4/10	15
Logistics (LOG)	test	164	82.0	4–9	0/5/12	6
Mystery-BW (MBW)	test	133	66.5	2–8	0/4/10	10
Depot	train	132	66.0	4–7	7/8/10	0
Rovers	train	199	99.5	4–15	2/3/5	0
Satellite	train	126	63.0	4–12	3/5/7	0

Appendix

Table 5: Per-domain data statistics (200 generated instances per domain). “BFS-solved” is the number of instances for which BFS finds a plan within

B

; only these carry a label and enter any training or evaluation. The last column counts BFS-solved instances whose goal already holds in the initial state.

Model	BW	LOG	MBW
Qwen2.5-72B	30.0%	0.0%	35.0%
Qwen2.5-14B	40.0%	0.0%	0.0%
Gemma2-9B	40.0%	0.0%	27.5%
Mistral-7B	0.0%	0.0%	0.0%

Appendix

Table 6: LLM planning success rates on BW/LOG/MBW using the state-simulating validator (precondition checking + goal verification via forward state simulation).

Domain	$\rho$	95% CI	$\rho$	95% CI	$\rho$	95% CI
	$\|\mathcal{O}\|$		Ridge on $x_{s}$		ARC
Blocksworld	0.764	$[0.680,\,0.828]$	0.644	$[0.529,\,0.736]$	0.294	$[0.126,\,0.446]$
Logistics	0.544	$[0.426,\,0.644]$	0.889	$[0.852,\,0.917]$	0.652	$[0.554,\,0.732]$
Mystery-Blocksworld	0.662	$[0.554,\,0.748]$	0.587	$[0.464,\,0.689]$	0.254	$[0.088,\,0.407]$

Appendix

Table 7: Approximate

95\%

Fisher confidence intervals for the primary absolute Spearman correlations, using the BFS-solved instances of each test domain. ARC’s row applies the single-sample Fisher formula to its five-seed mean

\rho

, which understates ARC’s true uncertainty: it ignores the seed-to-seed variance already visible in Table 1 (

\pm 0.157

\pm 0.297

), so ARC’s real interval is wider than shown here.

Held-out domain	$\|\rho\|_{\mathrm{ARC}}$	$\|\rho\|_{\mathrm{Ridge}}$	$\|\rho\|_{\|\mathcal{O}\|}$	$\Delta_{\mathrm{Ridge}-\|\mathcal{O}\|}$	$\Delta_{\mathrm{ARC}-\mathrm{Ridge}}$
Blocksworld	0.730 $\pm$ 0.052	0.873	0.764	$+0.110$	$-0.143$
Depot	0.533 $\pm$ 0.281	0.768	0.768	$+0.000$	$-0.235$
Gripper †	0.879 $\pm$ 0.022	0.913	0.503	$+0.410$	$-0.034$
Logistics	0.915 $\pm$ 0.002	0.917	0.544	$+0.373$	$-0.002$
Mystery-Blocksworld	0.784 $\pm$ 0.027	0.881	0.662	$+0.219$	$-0.097$
Rovers	0.040 $\pm$ 0.015	0.070	0.051	$+0.019$	$-0.030$

Appendix

Table 8: Leave-one-domain-out evaluation across seven domains. ARC is retrained from scratch on the other six domains for every row (five seeds each, mean

\pm

std shown); Ridge and

|\mathcal{O}|

are deterministic given the fold. ARC trails ridge regression on every one of the seven held-out domains, most severely on Depot (

-0.235

) and Satellite (

-0.101

), and is closest to parity only on Logistics (

-0.002

), where ridge itself is strongest. † Gripper is the validation domain in the primary protocol; its row should not be interpreted as an independent test result unless model selection is nested within each leave-one-domain-out split.

Method	BW	LOG	MBW	Mean
Random Forest ( $x_{s}$ )	0.187	0.735	0.240	0.388
XGBoost ( $x_{s}$ )	0.600	0.700	0.600	0.633
Gradient boosting ( $x_{s}$ )	0.713	0.688	0.621	0.674
SVR–RBF ( $x_{s}$ )	0.381	0.117	0.258	0.252
LambdaMART-style ranker ( $x_{s}$ )	0.511	0.896	0.396	0.601
Random Forest ( $x_{s}\\|x_{e}$ )	0.663	0.642	0.416	0.574

Appendix

Table 9: Comparison with conventional learned baselines (absolute Spearman correlation). The ranker is an XGBoost pairwise ranker with source domains as groups and the within-domain decile of

n^{\star}

as graded relevance. ARC’s row is its five-seed mean from Table 1 .

Surrogate	BW	LOG	MBW	Mean
Goal count ( $n_{\mathrm{goal}}$ )	0.764	0.969	0.673	0.802
Initial-state size ( $n_{\mathrm{init}}$ )	0.666	0.544	0.567	0.592
Initial-state density ( $n_{\mathrm{init}}/\|\mathcal{O}\|^{2}$ )	0.793	0.544	0.708	0.682
Object–goal ratio ( $\|\mathcal{O}\|/n_{\mathrm{goal}}$ )	0.108	0.849	0.109	0.355
Object cardinality ( $\|\mathcal{O}\|$ )	0.764	0.544	0.662	0.657
Delta-relaxation heuristic ( $h_{\text{add}}$ )	0.894	0.976	0.923	0.931

Appendix

Table 10: Absolute Spearman correlation between training-free structural surrogates and optimal plan length on the BFS-solved evaluation instances (

N=111

BW,

158

LOG,

123

MBW — the

h_{\text{add}}

and

O(1)

rows use the identical instance sets).

Domain	Object counts	B1	B2	B3	B4	B5	Mean
Ridge on $x_{s}$ , Blocksworld	$(2,3,4,6,8)$	0.48	0.37	0.58	0.45	0.57	0.49
group size $N$		40	40	24	13	9
Ridge on $x_{s}$ , Logistics	$(4,5,6,7,9)$	0.87	0.96	0.96	0.98	n/a	0.94
group size $N$		40	40	40	40	4
Ridge on $x_{s}$ , Mystery-Blocksworld	$(2,3,4,6,8)$	0.07	0.27	0.24	0.10	0.19	0.17
group size $N$		40	40	28	14	11

Appendix

Table 11: Absolute Spearman correlation within fixed object-count groups. B1–B5 are ordered by increasing object count. Logistics B5 is undefined (only two distinct plan lengths occur among its 4 instances), and the mean for Logistics is over the four defined groups. Correlations in groups with

N<15

are noisy. ARC trails ridge regression on

x_{s}

in every domain and every bucket with

N\geq 24

Domain	$\|\rho\|_{\mathrm{Ridge},\mathrm{BFS\ length}}$	$\|\rho\|_{\mathrm{Ridge},\mathrm{A^{*}\ nodes}}$	$\|\rho\|_{\mathrm{Ridge},\mathrm{A^{*}\ time}}$	$\|\rho\|_{\|\mathcal{O}\|,\mathrm{A^{*}\ nodes}}$
Blocksworld	0.674	0.683	0.668	0.916
Mystery-Blocksworld	0.532	0.502	0.553	0.790

Appendix

Table 12: Association between ridge regression on

x_{s}

and solver-derived measures,

N=60

BFS-solved instances per domain. The first three columns correlate the ridge prediction with BFS optimal plan length, A* node expansions, and A* wall-clock time; the final column correlates object cardinality with A* node expansions.

Method	BW	LOG	MBW	Mean
LLM, absolute scoring (Qwen 2.5-72B)	0.845	0.909	0.723	0.826
LLM, pairwise comparison (Qwen 2.5-72B)	0.640	0.444	0.489	0.524
Delta-relaxation heuristic ( $h_{\text{add}}$ )	0.894	0.976	0.923	0.931
Object cardinality	0.764	0.544	0.662	0.657
Goal count	0.764	0.969	0.673	0.802
Ridge on $x_{s}$	0.644	0.889	0.587	0.707

Appendix

Table 13: Absolute Spearman correlation for a purely LLM-based difficulty predictor conditioned on the same 20-example support set information used by ARC.

N=60

query instances per domain for absolute scoring;

120

instances per domain,

150

random pairs each (

\approx 2.5

comparisons per instance), for pairwise comparison. These

N

are smaller than Table 1 ’s full test sets, so this table’s values are not directly comparable to that table’s at the level of individual decimal places.

Representation and model	BW	LOG	MBW	Mean
Ridge ( $x_{s}$ )	0.644	0.889	0.587	0.707
Ridge ( $x_{e}$ )	0.057	0.704	0.476	0.412
Ridge ( $x_{s}\\|x_{e}$ )	0.587	0.899	0.580	0.689
ARC (main)	0.294	0.652	0.254	0.400

Appendix

Table 14: Absolute Spearman correlation with optimal plan length for non-episodic Ridge regressors using structural features, semantic embeddings, or their direct concatenation (fixed

\alpha=1

, computed independently of the Table 1 LogME row though numerically close to it, since both are ridge fits on

x_{e}

). ARC uses the same feature families within an episodically trained asymmetric architecture; its row is the five-seed mean from Table 1 .

Attention configuration	$\boldsymbol{\cos(h)}\downarrow$	$\boldsymbol{\operatorname{rank}_{\mathrm{eff}}(h)}\uparrow$	$\boldsymbol{\text{Mean }\|\rho\|}\uparrow$
Semantic query / semantic key	0.240	48.92	0.369
Structural query / semantic key	0.246	49.13	0.360
Semantic query / normalised structural key	0.249	48.17	0.364
Semantic query / structural key (ARC)	0.239	51.02	0.412

Appendix

Table 15: Matched-budget attention-direction ablation (five seeds each, trained with a separate but matched training loop; see caveat in the text).

\cos(h)

is the mean within-domain cosine similarity of the learned representation, and

\operatorname{rank}_{\mathrm{eff}}(h)

is its effective rank. Lower cosine similarity and higher effective rank indicate greater representational variation, but the primary outcome is mean absolute Spearman correlation. Per-domain means underlying this table: semantic/semantic

0.352/0.416/0.339

; structural/semantic

0.296/0.492/0.293

; semantic/normalised-structural

0.288/0.520/0.285

; ARC’s own configuration

0.221/0.812/0.203

(BW/LOG/MBW).

Encoder	BW cosine	LOG cosine	MBW cosine	Mean cosine	Eff. rank
all-mpnet-base-v2	0.9890	0.9857	0.9915	0.9887	2.62
all-MiniLM-L6-v2	0.9876	0.9872	0.9898	0.9882	2.64
paraphrase-MiniLM-L12-v2	0.9862	0.9900	0.9864	0.9876	2.61

Appendix

Table 16: Within-domain geometry of natural-language instance embeddings across three sentence encoders, computed on the leak-free descriptions of all generated instances per domain. Effective rank is computed from the singular-value distribution of the embedding matrix.

PCA dimension		Ridge coefficient
$\boldsymbol{d_{\mathrm{PCA}}}$	$\boldsymbol{\text{Mean }\|\rho\|}$	$\boldsymbol{\alpha}$	$\boldsymbol{\text{Mean }\|\rho\|}$
5	0.532 $\pm$ 0.109	0.01	0.527 $\pm$ 0.050
10	0.407 $\pm$ 0.095	0.1	0.514 $\pm$ 0.071
20 (default)	0.412 $\pm$ 0.083	1.0 (default)	0.412 $\pm$ 0.083
30	0.439 $\pm$ 0.086	10.0	0.469 $\pm$ 0.080
50	0.439 $\pm$ 0.086	100.0	0.753 $\pm$ 0.017

Appendix

Table 17: Sensitivity of ARC’s mean absolute Spearman correlation to residualisation hyperparameters (five seeds each, varying one hyperparameter with the other held at its default). Entries use the same matched training loop as Table 15 ; see that table’s note on its relationship to Table 1 ’s main configuration.

All prompts use temperature $=0$ and max $2{,}048$ output tokens. Prompt 1 follows [ 17 ] ’s chain-of-thought PDDL format. No domain-specific demonstrations are provided in Prompts 1–2; Prompts 3–4 condition on the 20-example labeled support block described in Appendix B.7 in place of domain-specific demonstrations.
Prompt	Used in	Models	Includes CoT?
1 (PDDL Planning)	Tables 3 , 4 , § 6.2	Qwen 2.5-72B	Yes
2 (Mystery-BW)	§ 6.2 , Table 4 (MBW)	Qwen 2.5-72B	Yes
3 (LLM difficulty, absolute)	Appendix B.7 , Table 13	Qwen 2.5-72B	No
4 (LLM difficulty, pairwise)	Appendix B.7 , Table 13	Qwen 2.5-72B	No

Appendix

Table 18: Summary of prompts used across experiments.

Domain	N	$\|\mathcal{O}\|$	Goal count	Ridge ( $x_{s}$ )	ARC (main)
Rescue Mission	85	0.224	0.805	0.641	0.099 $\pm$ 0.066 (ens. 0.074)
Robot Arm	85	0.030	0.310	0.307	0.242 $\pm$ 0.074 (ens. 0.257)
Library Books	35	0.134	0.856	0.693	0.679 $\pm$ 0.013 (ens. 0.694)

Appendix

Table 19: Absolute Spearman correlation with optimal plan length on the three custom non-IPC domains, zero-shot (trained only on the seven main-text domains;

N

is the number of BFS-solved,

n^{\star}>0

instances). ARC uses five seeds, mean

\pm

std, with the prediction-level ensemble in parentheses.

Cohen’s $\kappa>0.80$ indicates strong agreement [ 33 ] . All pairwise $\kappa$ values exceed 0.88, and all percent agreement scores exceed 90%, confirming the validity and coherence of the generated instances.
	Pairwise Cohen’s $\kappa$			Jaccard Coeff.		Agreement
Domain	A1–A2	A1–A3	A2–A3	Valid.	Diff.	(%)
Rescue Mission	0.924	0.911	0.918	0.941	0.903	93.3%
Robot Arm	0.907	0.893	0.916	0.928	0.887	91.7%
Library Books	0.938	0.942	0.931	0.957	0.921	95.0%
Mean	0.923	0.915	0.922	0.942	0.904	93.3%

Appendix

Table 20: Inter-annotator agreement metrics across three annotators (A1, A2, A3) on 30 sampled instances per domain. Cohen’s

\kappa

is computed pairwise and averaged. Jaccard coefficient measures set overlap of flagged instances. Percent agreement is the fraction of instances all three annotators labeled identically.

			$\|O\|$ (objects)			$n^{*}$ (plan length)			Solve
Domain	Total	Solved	Min	Median	Max	Min	Median	Max	BFS%	EHC%
Rescue Mission	200	127	7	18	43	3	9	24	63.5%	82.0%
Robot Arm	200	95	5	14	31	2	7	18	47.5%	71.0%
Library Books	200	15	6	10	16	4	8	14	7.5%	31.0%
BFS%: fraction solved by BFS within budget ( $T_{\text{max}}{=}12$ , $N_{\text{max}}{=}5{,}000$ ). EHC%: fraction solved when BFS is replaced by EHC( $h^{\text{FF}}$ ) with the same node budget. Library Books has a low BFS solve rate because the compound constraint (book, cart, and correct shelf co-location) produces long plans exceeding the BFS step budget; EHC( $h^{\text{FF}}$ ) recovers 31% with informed search.

Appendix

Table 21: Dataset statistics for the three custom planning domains.

n^{*}

= BFS-optimal plan length (solved instances only).

|O|

= object count.

n_{\text{init}}

= initial-state facts.

n_{\text{goal}}

= goal facts.

LLM Planning

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

See all 142 papers

How Far Are LLMs from Symbolic Planners? An NLP-Based Perspective
Aug 2, 2025Ma'ayan Armony, Albert Meroño-Peñuela, Gerard CanalLLM Planning LLM Evaluation
Department of Informatics, King’s College London
Analysis of Optimality of Large Language Models on Planning Problems
Apr 3, 2026Bernd Bohnet, Michael C. Mozer, Kevin Swersky +4LLM Planning Symbolic Planning
Google DeepMind
What We Talk About When We Talk About LLM Planning: Evidence for Two Distinct Planning Abilities
Jul 13, 2026Sukai Huang, Chenyuan Zhang, Fucai Ke +4LLM Evaluation LLM Planning
Faculty of Information Technology, Monash University

Aug 2, 2025J/K move · Enter open · S save

How Far Are LLMs from Symbolic Planners? An NLP-Based Perspective

Ma'ayan Armony, Albert Meroño-Peñuela, Gerard Canal

Department of Informatics, King’s College London

LLM Planning LLM Evaluation Long-Horizon LLM Reasoning Language Model Reasoning Evaluation Symbolic Planning

Open paper AskPDF arXiv

AI planning provides agents the ability to act autonomously towards achieving a goal in a given environment. Recent advances in Large Language Models (LLMs) have introduced the prospect of using unstructured input for planning, making LLMs in planning an active area of research, especially for supporting autonomous agents. However, LLMs remain unreliable as long-horizon planners, since some of the plans they produce contain mistaken or hallucinated actions; executing such plans could lead to unexpected and harmful outcomes. Existing benchmarks for LLMs in planning primarily rely on binary evaluation metrics, providing limited insight into the quality of plans that do not achieve the goal, and how far those are from becoming valid. In this paper, we frame the evaluation of LLMs in planning as a natural language processing (NLP) task, as LLMs are themselves NLP models. We propose a pipeline comprising three NLP-based steps that assess plan quality from complementary perspectives, followed by a symbolic planning step to achieve a valid plan, to provide a finer-grained understanding of the quality of invalid plans. In our experiments, we find no clear evidence of logical derivation or state-tracking during LLM plan generation -- on average, for all non-empty plans, only 3.55 actions per plan are executable, despite symbolically-generated optimal plans having an average length of 9.47 actions, which suggests that LLMs are still far from the reliability of symbolic planners. Our suite of metrics is further used to investigate patterns in LLM plan generation over time, and can provide a useful metric for assessing the quality of individual invalid plans.

Abstract

LLM Planning

Explore similar work

How Far Are LLMs from Symbolic Planners? An NLP-Based Perspective

Analysis of Optimality of Large Language Models on Planning Problems

What We Talk About When We Talk About LLM Planning: Evidence for Two Distinct Planning Abilities