当规划问题对大模型变得困难时：区分结构复杂性与语义可解释性

# When Planning Problems Become Hard for LLMs: Separating Structural Complexity from Semantic Interpretability
Source: [https://arxiv.org/html/2610.26964](https://arxiv.org/html/2610.26964)
Mayukh DebnathAffiliation:Robotics and Autonomous Systems \(AI\)Affiliation:Arizona State UniversityAffiliation:Tempe, USAEmail:[\{mdebnath\}@asu\.edu](mailto:)Rammohan MallipeddiAffiliation:Department of Artificial IntelligenceAffiliation:Kyungpook National UniversityAffiliation:Daegu, South KoreaAffiliation:\{yinkpeace, mallipeddi\.ram\}@gmail\.com

###### Abstract

Large language models \(LLMs\) perform poorly on classical planning, but it is unclear whether this reflects the intrinsic structural complexity of a planning instance or the difficulty of interpreting its symbolic representation\. Existing evaluations conflate the two\. We study seven STRIPS domains modeled on IPC domains, labeled with breadth\-first\-search \(BFS\) optimal plan lengths, and ask two questions\. First: can structural difficulty be estimated without solving an instance? A classical, zero\-training delete\-relaxation heuristic \(haddh\_\{\\text\{add\}\}\) estimates optimal plan length on held\-out domains far better than every alternative we test, including ARC, a purpose\-built episodic retrieval architecture: mean Spearman\|ρ\|=0\.931\|\\rho\|=0\.931forhaddh\_\{\\text\{add\}\}, versus0\.7070\.707for ridge regression on structural features,0\.6570\.657for object count, and0\.400\.40for ARC despite five\-seed training with early stopping\. ARC does not beat a linear model on its own input features\. We take this as the paper’s primary finding: for estimating structural planning difficulty, a decades\-old AI planning heuristic outperforms a dedicated learned retrieval model, and future work in this space should be judged against it\. Second: does an LLM’s actual planning success track structural difficulty? We introduce a controlled intervention that progressively renames predicates while preserving the transition system and optimal plans, so structural difficulty is unchanged by construction, and measure planning success with a state\-simulating validator: valid\-plan success falls from67\.5%67\.5\\%to40\.0%40\.0\\%as the fraction of renamed symbols grows from0%0\\%to100%100\\%, with refusal rate flat at0%0\\%throughout\. We further show that an LLM given ARC’s own conditioning information estimates difficulty in\-context \(mean\|ρ\|=0\.826\|\\rho\|=0\.826\) far better than ARC does after training, and that hybrid routing between an LLM and a symbolic planner depends more on calibration with target\-model outcomes than on which structural score is used\. Together, these results indicate that structural planning difficulty is already well estimated by existing, non\-learned methods, and that the open problem for hybrid planning systems is modeling an LLM’s semantic, vocabulary\-dependent behavior rather than building better structural\-difficulty predictors\. The complete code is available at[https://github\.com/mdebnath22/plan](https://github.com/mdebnath22/plan)\.

*K*eywordsPlanning⋅\\cdotHeuristic Evaluation⋅\\cdotLarge Language Models \(LLMs\)⋅\\cdotStructural Complexity⋅\\cdotSemantic Interpretability

## 1Introduction

Planning \- synthesizing goal\-directed action sequences over a state space \- is a canonical test of systematic reasoning\. Large language models \(LLMs\) remain unreliable at it\.[Valmeekam et al\. \(2023a\)](https://arxiv.org/html/2610.26964#bib.bib23)report that frontier models solve fewer than 3% of standard PDDL benchmarks;[Valmeekam et al\. \(2023b\)](https://arxiv.org/html/2610.26964#bib.bib22)show the failures persist under chain\-of\-thought prompting[Wei et al\. \(2022\)](https://arxiv.org/html/2610.26964#bib.bib14)and self\-critique[Stechly et al\. \(2023\)](https://arxiv.org/html/2610.26964#bib.bib24)\. Unlike symbolic planners, LLMs perform no explicit combinatorial search, which makes them brittle on problems that require systematically exploring a large state space[Kambhampati et al\. \(2024\)](https://arxiv.org/html/2610.26964#bib.bib25);[Silver et al\. \(2024\)](https://arxiv.org/html/2610.26964#bib.bib3)\.

Why a given instance is hard is less understood\. Two distinct factors can make a planning instance difficult:*structural complexity*, the combinatorial difficulty intrinsic to the state space and goal structure, and*semantic interpretability*, how easily an LLM can ground the symbolic vocabulary describing that same problem\. Existing benchmarks conflate them, so a failure cannot be attributed to either cause specifically\.

This matters for hybrid planning systems, which route easy instances to an LLM and hard instances to a symbolic planner\([Kambhampati et al\., 2024](https://arxiv.org/html/2610.26964#bib.bib25)\), use an LLM for heuristic guidance\([Tang et al\., 2025](https://arxiv.org/html/2610.26964#bib.bib15)\), or for candidate generation with symbolic verification\([Valmeekam et al\., 2023b](https://arxiv.org/html/2610.26964#bib.bib22)\)\. Every such system needs an upstream difficulty estimate\. Existing approaches use problem size, domain identity, or domain\-specific classifiers\([Chiari et al\., 2025](https://arxiv.org/html/2610.26964#bib.bib26)\), none of which transfers to a domain with unfamiliar predicates or object vocabulary\.

We address this in two parts\. First, we ask whether structural difficulty can be estimated without solving an instance, and whether a learned, cross\-domain model is the right tool\. We build ARC \(Asymmetric Retrieval for Cross\-domain difficulty estimation\), which uses a foundation\-model embedding to retrieve structurally similar instances across domains, with structural features providing within\-domain discrimination; within a single domain, such embeddings are expected to concentrate in a narrow region of the embedding space, limiting their ability to discriminate difficulty \(Section[3](https://arxiv.org/html/2610.26964#S3.SS0.SSS0.Px4)\)\. We compare ARC against object count, goal\-fact count, ridge regression on structural features, LogME\([You et al\., 2021](https://arxiv.org/html/2610.26964#bib.bib17)\), H\-score\([Bao et al\., 2019](https://arxiv.org/html/2610.26964#bib.bib28)\), a non\-episodic MLP, andhaddh\_\{\\text\{add\}\}, a delete\-relaxation heuristic computed from an instance’s grounded action set via a relaxed planning graph, with no learning and no target\-domain data\. The result is decisive:haddh\_\{\\text\{add\}\}reaches mean\|ρ\|=0\.931\|\\rho\|=0\.931across three held\-out domains; ARC reaches0\.4000\.400, below every baseline except LogME and H\-score, and below a linear model fit on exactly its own structural\-feature input\. We verifyhaddh\_\{\\text\{add\}\}directly: an independent reconstruction of each domain’s grounded action set reproduces every saved optimal plan with zero failures across1,0061\{,\}006solved instances in seven domains\.

Second, we ask whether an LLM’s actual planning success tracks this structural difficulty\. We introduce an intervention that renames a domain’s predicates while leaving its transition system, every optimal plan, and every structural feature unchanged\. Any change in LLM success under this intervention is attributable to semantic interpretability, not structure\. Valid\-plan success on Blocksworld falls from67\.5%67\.5\\%with no renaming to40\.0%40\.0\\%with every predicate renamed, while refusal rate stays at0%0\\%throughout: the model always attempts a plan, and the effect is carried entirely by a rising rate of malformed and inapplicable actions\.

#### Contributions\.

- •We show that structural difficulty is well estimated by a classical, zero\-training delete\-relaxation heuristic \(haddh\_\{\\text\{add\}\}, mean\|ρ\|=0\.931\|\\rho\|=0\.931\), which exceeds every alternative we test, including ARC, a retrieval architecture we purpose\-built for this problem and evaluated under conditions fixed before training \(five seeds, early stopping, a pre\-declared criterion for added value\)\. ARC reaches only0\.4000\.400–0\.4030\.403\(ensembled:0\.5950\.595\), below a linear model on its own structural\-feature inputs \(0\.7070\.707\)\. We report this as a substantive negative result for learned cross\-domain retrieval, not a limitation of one implementation: Appendix[C](https://arxiv.org/html/2610.26964#A3)shows the shortfall holds across attention directions, representation combinations, and residualization hyperparameters\.
- •We introduce a semantic intervention based on progressive predicate renaming that holds structural difficulty fixed while varying symbol interpretability\. LLM valid\-plan success falls from67\.5%67\.5\\%to40\.0%40\.0\\%as renaming goes from none to complete, with refusal rate flat at0%0\\%, demonstrating that semantic interpretability affects LLM planning success independently of structural difficulty\.
- •We show that structure\-only routing cannot substitute for target\-model calibration, and that an LLM given ARC’s own conditioning information outperforms ARC substantially at difficulty estimation \(mean\|ρ\|=0\.826\|\\rho\|=0\.826vs\.0\.4000\.400\)\.

## 2Related Work

#### LLMs for PDDL planning\.

LLMs struggle with classical planning, including simple Blocksworld instances\([Valmeekam et al\., 2023b](https://arxiv.org/html/2610.26964#bib.bib22);[Valmeekam et al\., 2022](https://arxiv.org/html/2610.26964#bib.bib8);[McDermott et al\., 1998](https://arxiv.org/html/2610.26964#bib.bib1)\), across IPC\-style domains\([Valmeekam et al\., 2023a](https://arxiv.org/html/2610.26964#bib.bib23);[Long and Fox, 2003](https://arxiv.org/html/2610.26964#bib.bib21);[Ferber et al\., 2019](https://arxiv.org/html/2610.26964#bib.bib6);[Silver and Chitnis, 2020](https://arxiv.org/html/2610.26964#bib.bib5)\)\. Self\-critique does not reliably fix this\([Stechly et al\., 2023](https://arxiv.org/html/2610.26964#bib.bib24);[Wei et al\., 2022](https://arxiv.org/html/2610.26964#bib.bib14);[Guan et al\., 2023](https://arxiv.org/html/2610.26964#bib.bib7)\)\. Instruction\-tuned PDDL generation improves performance\([Verma et al\., 2025](https://arxiv.org/html/2610.26964#bib.bib27)\), but models still generalize poorly to instances larger or structurally different from training\([Silver et al\., 2024](https://arxiv.org/html/2610.26964#bib.bib3);[Tang et al\., 2025](https://arxiv.org/html/2610.26964#bib.bib15);[Tantakoun et al\., 2025](https://arxiv.org/html/2610.26964#bib.bib16);[Wei et al\., 2025](https://arxiv.org/html/2610.26964#bib.bib13)\)\. We take these limitations as given and ask instead when an LLM should be used at all\.

#### Hybrid planning systems\.

The LLM\-Modulo framework\([Kambhampati et al\., 2024](https://arxiv.org/html/2610.26964#bib.bib25)\)wraps LLM calls with formal verifiers\([Gundawar et al\., 2024](https://arxiv.org/html/2610.26964#bib.bib9)\)\. Related work uses LLMs for heuristic guidance\([Chiari et al\., 2025](https://arxiv.org/html/2610.26964#bib.bib26);[Corrêa et al\., 2026](https://arxiv.org/html/2610.26964#bib.bib11)\)or candidate generation with symbolic verification\([Li et al\., 2024](https://arxiv.org/html/2610.26964#bib.bib10);[Yu et al\., 2025](https://arxiv.org/html/2610.26964#bib.bib12)\)\. Every such architecture needs an upstream router; existing routing signals do not transfer across domains with unfamiliar vocabulary\.

#### Feature transferability metrics\.

LogME\([You et al\., 2021](https://arxiv.org/html/2610.26964#bib.bib17)\)and H\-score\([Bao et al\., 2019](https://arxiv.org/html/2610.26964#bib.bib28)\)estimate how well a frozen feature space supports a downstream task without fine\-tuning\([Bao et al\., 2018](https://arxiv.org/html/2610.26964#bib.bib18);[Nguyen et al\., 2020](https://arxiv.org/html/2610.26964#bib.bib19);[Sae\-Bae and Laohakiat, 2025](https://arxiv.org/html/2610.26964#bib.bib20)\), typically by fitting a linear\-Gaussian model and reporting its marginal likelihood or an information\-theoretic divergence\. We use both as zero\-shot baselines, fit on source\-domain instances and scored on held\-out domains\.

#### Meta\-learning\.

MAML\([Finn et al\., 2017](https://arxiv.org/html/2610.26964#bib.bib30)\)performs an explicit inner\-loop update per episode; Prototypical Networks\([Snell et al\., 2017](https://arxiv.org/html/2610.26964#bib.bib31)\)score a query by its relation to a labeled support set with no inner\-loop adaptation\. ARC follows the latter: one set of parameters, updated once per episode, with no meta\-/task\-parameter distinction\. “Episodic” here refers only to the sampling procedure\([Blanchard et al\., 2011](https://arxiv.org/html/2610.26964#bib.bib32);[Blanchard et al\., 2021](https://arxiv.org/html/2610.26964#bib.bib4)\): each step draws one source domain and conditions on a labeled support set from it, drawing on the geometric structure of PDDL embeddings\([Reimers and Gurevych, 2019](https://arxiv.org/html/2610.26964#bib.bib29);[van den Oord et al\., 2018](https://arxiv.org/html/2610.26964#bib.bib33)\)\.

## 3Background and Problem Formulation

#### PDDL and planning instances\.

A classical planning instance is a pairπ=⟨D,P⟩\\pi=\\langle D,P\\rangle, whereDDspecifies a domain’s predicates and lifted operators in PDDL, andP=⟨O,s0,g⟩P=\\langle O,s\_\{0\},g\\ranglegives a set of objectsOO, an initial states0s\_\{0\}, and a goal conditiongg\. A plan is a sequence of ground actions𝐚=\(a1,…,aL\)\\mathbf\{a\}=\(a\_\{1\},\\dots,a\_\{L\}\)whose execution froms0s\_\{0\}satisfiesgg\. The optimal plan length is

n⋆​\(π\)=min𝐚⁡\{\|𝐚\|:g⊆Γ⁡\(s0,𝐚\)\},n^\{\\star\}\(\\pi\)=\\min\_\{\\mathbf\{a\}\}\\left\\\{\|\\mathbf\{a\}\|:g\\subseteq\\Gamma\(s\_\{0\},\\mathbf\{a\}\)\\right\\\},\(1\)whereΓ⁡\(s0,𝐚\)\\Gamma\(s\_\{0\},\\mathbf\{a\}\)is the state reached by executing𝐚\\mathbf\{a\}froms0s\_\{0\}\. We taken⋆​\(π\)n^\{\\star\}\(\\pi\)as our operational definition of structural difficulty\.

Example: A Blocksworld planning instanceThree blocksaa,bb,cc, initially on the table and clear\. Goal: stackaaonbb\.[⬇](data:text/plain;base64,KDpvYmplY3RzIGEgYiBjKQooOmluaXQgKG9uLXRhYmxlIGEpIChvbi10YWJsZSBiKSAob24tdGFibGUgYykKICAgICAgIChjbGVhciBhKSAoY2xlYXIgYikgKGNsZWFyIGMpIChoYW5kZW1wdHkpKQooOmdvYWwgKG9uIGEgYikp)\(:objectsabc\)\(:init\(on\-tablea\)\(on\-tableb\)\(on\-tablec\)\(cleara\)\(clearb\)\(clearc\)\(handempty\)\)\(:goal\(onab\)\)HereO=\{a,b,c\}O=\\\{a,b,c\\\},s0s\_\{0\}is theinitblock,g=\{\(on​a​b\)\}g=\\\{\(\\text\{on \}a\\ b\)\\\}\. One action,stack​\(a,b\)\\text\{stack\}\(a,b\), reaches a state satisfyinggg, son⋆​\(π\)=1n^\{\\star\}\(\\pi\)=1\. Instances in our evaluation are larger; this minimal example fixes notation\.

#### Difficulty labels\.

We label every instance by breadth\-first search \(BFS\) within a budgetB=\(Tmax=12,Nmax=5,000\)B=\(T\_\{\\text\{max\}\}\{=\}12,N\_\{\\text\{max\}\}\{=\}5\{,\}000\), identically across domains: the regression target isyr=n⋆​\(π\)y\_\{r\}=n^\{\\star\}\(\\pi\)\. Instances BFS does not solve withinBBcarry no label and are excluded from every computation in this paper; a finite\-budget failure neither establishes unsolvability nor yields a plan\-length value, so we never assign one\. Per\-domain coverage is in Appendix[A\.1](https://arxiv.org/html/2610.26964#A1.SS1)\.

#### Feature representation\.

Each instance has three views\.Structural featuresxs∈ℝ28x\_\{s\}\\in\\mathbb\{R\}^\{28\}— object count, initial\- and goal\-fact counts and ratios, predicate\-arity statistics, operator count — contain no domain identifier and nothing derived from the plan orn⋆n^\{\\star\}\.Foundation\-model embeddingsxe∈ℝ768x\_\{e\}\\in\\mathbb\{R\}^\{768\}encode a natural\-language description built from object counts and a plain\-language summary of the initial state and goal, with no raw PDDL syntax and nothing derived from the plan; no description contains a step count or difficulty word\.The residualxr=xe−x^e​\(xs\)x\_\{r\}=x\_\{e\}\-\\hat\{x\}\_\{e\}\(x\_\{s\}\)is the component ofxex\_\{e\}not explained byxsx\_\{s\}, estimated by PCA\-Ridge regression\. All preprocessing is fit on pooled source\-domain data and frozen before evaluation\.

#### FM embedding collapse\.

ARC rests on a diagnostic hypothesis:xex\_\{e\}should identify semantic similarity across domains but concentrate within a domain, limiting within\-domain discrimination;xsx\_\{s\}should do the opposite\. We embed every instance’s description withall\-mpnet\-base\-v2and measure mean within\-domain pairwise cosine similarity and effective rankexp⁡\(ℋ⁡\(σ/‖σ‖1\)\)\\exp\(\\mathcal\{H\}\(\\sigma/\\\|\\sigma\\\|\_\{1\}\)\),σ\\sigmathe embedding matrix’s singular values\. On the three held\-out domains, mean cosine similarity is0\.9890\.989/0\.9860\.986/0\.9920\.992\(BW/LOG/MBW\), effective rank2\.622\.62; two further encoders give0\.9880\.988/0\.9880\.988cosine and2\.642\.64/2\.612\.61rank \(Appendix[C\.3](https://arxiv.org/html/2610.26964#A3.SS3)\), so this is a property of the encoder family on these descriptions, not one model\.

Structural features, pooled\-standardized, range0\.690\.69–0\.950\.95cosine and2\.12\.1–5\.35\.3effective rank \(mean3\.83\.8\) within a domain\. The hypothesized asymmetry holds in direction —xex\_\{e\}is consistently more collapsed thanxsx\_\{s\}— but the effective\-rank gap is smaller than the cosine gap suggests:xsx\_\{s\}is also concentrated within a domain, not uniformly higher\-dimensional\. Whether the asymmetric query/key assignment this motivates is in fact the best way to exploit this structure is answered empirically in Appendix[C](https://arxiv.org/html/2610.26964#A3): on balance, no — it is the best of four tested configurations \(Appendix[C\.2](https://arxiv.org/html/2610.26964#A3.SS2)\), but none is competitive with the non\-episodic baselines in Table[1](https://arxiv.org/html/2610.26964#S6.T1)\.

![Refer to caption](https://arxiv.org/html/2610.26964v1/dg.png)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𝐱sq\\mathbf\{x\}\_\{s\}^\{q\},𝐳\\mathbf\{z\}and𝐱rq\\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](https://arxiv.org/html/2610.26964#S4)\)\.

## 4ARC: Architecture and Training

ARC estimates difficulty by retrieving structural analogues of a query instance from a labeled support set \(60 instances, at training and test time\)\. No target\-domain instance, label, or statistic is used at test time\. The semantic embedding of the query retrieves structurally relevant support instances:xex\_\{e\}aligns across domains as a query;xsx\_\{s\}discriminates within a domain as keys and values\. Algorithm[1](https://arxiv.org/html/2610.26964#alg1)gives inference\.

Algorithm 1ARC Inference \(Asymmetric Retrieval\)1:Query

xeq,xsq,xrqx\_\{e\}^\{q\},x\_\{s\}^\{q\},x\_\{r\}^\{q\}; support set

\{\(xs\(i\),xr\(i\),y\(i\)\)\}i=1\|𝒮\|\\\{\(x\_\{s\}^\{\(i\)\},x\_\{r\}^\{\(i\)\},y^\{\(i\)\}\)\\\}\_\{i=1\}^\{\|\\mathcal\{S\}\|\}
2:Predicted normalized plan length

y^r\\hat\{y\}\_\{r\}
3:

q←WQ2⋅GELU​\(LN​\(WQ1​xeq\)\)q\\leftarrow W\_\{Q\_\{2\}\}\\cdot\\text\{GELU\}\(\\text\{LN\}\(W\_\{Q\_\{1\}\}x\_\{e\}^\{q\}\)\)
4:for

i=1,…,\|𝒮\|i=1,\\dots,\|\\mathcal\{S\}\|do

5:

ki←WK2⋅GELU​\(WK1​xs\(i\)\)k\_\{i\}\\leftarrow W\_\{K\_\{2\}\}\\cdot\\text\{GELU\}\(W\_\{K\_\{1\}\}x\_\{s\}^\{\(i\)\}\);

Vi←ValueProj\(\[xs\(i\)∥xr\(i\)\]\)V\_\{i\}\\leftarrow\\text\{ValueProj\}\(\[x\_\{s\}^\{\(i\)\}\\\|x\_\{r\}^\{\(i\)\}\]\)
6:endfor

7:

α←softmax​\(τ⋅q​K⊤/d\)\\alpha\\leftarrow\\text\{softmax\}\(\\tau\\cdot qK^\{\\top\}/\\sqrt\{d\}\);

z←α⊤​Vz\\leftarrow\\alpha^\{\\top\}V
8:

h←FusionMLP​\(\[xsq​‖z‖​xrq\]\)h\\leftarrow\\text\{FusionMLP\}\(\[x\_\{s\}^\{q\}\\\|z\\\|x\_\{r\}^\{q\}\]\);

y^attn←RegressionHead​\(h\)\\hat\{y\}\_\{\\text\{attn\}\}\\leftarrow\\text\{RegressionHead\}\(h\)
9:ifgated variantthen

c←σ⁡\(MLP​\(xsq\)\)c\\leftarrow\\sigma\(\\text\{MLP\}\(x\_\{s\}^\{q\}\)\);

y^r←c⋅w⊤​xsq\+\(1−c\)​y^attn\\hat\{y\}\_\{r\}\\leftarrow c\\cdot w^\{\\top\}x\_\{s\}^\{q\}\+\(1\-c\)\\hat\{y\}\_\{\\text\{attn\}\}
10:else

y^r←y^attn\\hat\{y\}\_\{r\}\\leftarrow\\hat\{y\}\_\{\\text\{attn\}\}
11:endif

12:return

y^r\\hat\{y\}\_\{r\}

The query encoder mapsxex\_\{e\}to a 128\-dimensional space through a two\-layer MLP \(LayerNorm, dropout0\.10\.1\); the key encoder does the same forxsx\_\{s\}\. The value projection concatenatesxs\(i\)x\_\{s\}^\{\(i\)\}andxr\(i\)x\_\{r\}^\{\(i\)\}, so retrieval carries both structural and residual semantic information\. Attention temperature starts atτ=1\\tau=1\.

#### Optional complexity\-aware gate\.

We also evaluate, as a pre\-declared variant, a gatec=σ⁡\(MLP​\(xsq\)\)∈\[0,1\]c=\\sigma\(\\text\{MLP\}\(x\_\{s\}^\{q\}\)\)\\in\[0,1\]blending a linear predictory^simple=w⊤​xsq\\hat\{y\}\_\{\\text\{simple\}\}=w^\{\\top\}x\_\{s\}^\{q\}with the attention output, trained end\-to\-end with no auxiliary supervision\. The main configuration below uses no gate; the gated variant is reported alongside it, and we do not select between them using test\-domain scores\.

#### Budget\-exceeded instances\.

An instance BFS does not solve within its budget is not known to be unsolvable, nor necessarily harder than a solved one\. Such instances carry no label and supervise no head of the model\.

### 4\.1Training Objective

ARC trains for up to 5,000 episodes\. Each episode samples one source domain, splits its labeled instances into a 60\-instance support set and 30\-instance query set, and minimizes

ℒ=ℒreg−λe​ℋ​\(𝜶\),\\mathcal\{L\}=\\mathcal\{L\}\_\{\\text\{reg\}\}\-\\lambda\_\{e\}\\,\\mathcal\{H\}\(\\boldsymbol\{\\alpha\}\),\(2\)mean squared error between the prediction and the domain\-level z\-scored plan length, regularized by the negative entropy of the attention weights \(λe=0\.05\\lambda\_\{e\}=0\.05\) to prevent collapse onto one support instance\. Every term is optimized by one outer AdamW update \(lr3×10−43\\times 10^\{\-4\}, weight decay10−410^\{\-4\}, cosine annealing to10−510^\{\-5\}, gradient clipping1\.01\.0\) per episode \- there is no inner\-loop adaptation step\. Gripper is the validation domain: every 200 episodes we score ARC zero\-shot on Gripper, keep the best checkpoint, and stop after 10 checks with no improvement; the kept, not the last, checkpoint is evaluated\. We report mean±\\pmstd over five seeds \(0, 1, 2, 42, 123\) for every trained method\.

## 5Experiments

### 5\.1Setup

#### Domains\.

Seven classical STRIPS domains modeled on IPC domains, generated by our own code: source domains Depot, Rovers, Satellite; held\-out test domains Blocksworld \(BW\), Logistics \(LOG\), Mystery\-Blocksworld \(MBW\); validation domain Gripper \(early stopping only\)\. Each has 200 generated instances; only BFS\-solved instances carry a label and enter any computation: 126 \(BW\), 164 \(LOG\), 133 \(MBW\), 132 \(Depot\), 199 \(Rovers\), 126 \(Satellite\), 181 \(Gripper\)\. Mystery\-Blocksworld shares Blocksworld’s state space but replaces every predicate and action name with an uninformative symbol\.

#### Metric\.

Our primary metric is absolute Spearman rank correlation\|ρ\|\|\\rho\|between a predicted score andn⋆n^\{\\star\}, over each test domain’s BFS\-solved instances; a ranking measure requiring no threshold tuning\. For routing \(Section[6\.3](https://arxiv.org/html/2610.26964#S6.SS3)\), we report the fraction of instances solved, with plan validity checked by a state\-simulating executor\. Confidence intervals: Appendix[B\.1](https://arxiv.org/html/2610.26964#A2.SS1)\.

#### Baselines\.

Object count\|𝒪\|\|\\mathcal\{O\}\|; unsatisfied goal\-fact count; ridge regression onxsx\_\{s\}; LogME, fit with evidence\-optimal regularization rather than a fixed value; H\-score; a non\-episodic MLP \(ERM\); andhaddh\_\{\\text\{add\}\}, computed from each instance’s grounded action set via a relaxed planning graph with all delete effects ignored, with no learning and no target\-domain data\.haddh\_\{\\text\{add\}\}is not anO⁡\(1\)O\(1\)read: it needs the same grounded action set a planner would use\. We reconstruct this independently per domain — from object\-naming conventions and each instance’s own saved initial state, never reusing the labeling code — and verify it: re\-simulating every saved BFS\-optimal plan against the reconstructed action set succeeds with zero failures across all1,0061\{,\}006labeled instances in seven domains\.

## 6Results

### 6\.1Zero\-Shot Estimation of Structural Complexity

Table 1:Absolute Spearman correlations between predicted difficulty scores and optimal plan lengths on held\-out domains \(N=126N=126,164164,133133BFS\-solved instances for BW, LOG, MBW\)\. ERM and ARC rows report mean±\\pmstd 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 \(α/β=2\.358\\alpha/\\beta=2\.358\) rather than a fixed value\.haddh\_\{\\text\{add\}\}transfers best, and no scalar statistic dominates every domain\.haddh\_\{\\text\{add\}\}reaches mean\|ρ\|=0\.931\|\\rho\|=0\.931\(0\.8940\.894/0\.9760\.976/0\.9230\.923\)\. Goal count reaches0\.8020\.802, ridge onxsx\_\{s\}reaches0\.7070\.707, object count0\.6570\.657\. A paired bootstrap \(2,0002\{,\}000resamples\) ofhaddh\_\{\\text\{add\}\}against goal count givesΔ​\|ρ\|=\+0\.119\\Delta\|\\rho\|=\+0\.119\[\+0\.057,\+0\.192\]\[\+0\.057,\+0\.192\]on BW and\+0\.236\+0\.236\[\+0\.143,\+0\.344\]\[\+0\.143,\+0\.344\]on MBW; on Logistics the two are indistinguishable \(Δ=0\.000\\Delta=0\.000\), becausehaddh\_\{\\text\{add\}\}reduces to a monotonic function of unsatisfied\-goal count on this domain’s relaxed graph \(Appendix[B\.4](https://arxiv.org/html/2610.26964#A2.SS4)\)\. Object count exceeds ridge on BW and MBW; ridge is far stronger on LOG \(0\.8890\.889vs\.0\.5440\.544\)\.haddh\_\{\\text\{add\}\}is not anO⁡\(1\)O\(1\)read, so we verify its action\-set reconstruction directly: zero failures re\-simulating1,0061\{,\}006saved plans\. Appendinghaddh\_\{\\text\{add\}\}as a 29th feature to ridge onxsx\_\{s\}is mixed, not uniform \(\+0\.095\+0\.095MBW,−0\.001\-0\.001LOG,−0\.077\-0\.077BW\), so its standalone strength is not simply additive under an untuned fit\.

ARC does not add value beyond these baselines\.We fixed this criterion in advance: added value requires exceeding the strongest baseline in every comparison by more than the seed\-to\-seed standard deviation\. It does not\. ARC reaches mean0\.4000\.400\(0\.294±0\.2160\.294\\pm 0\.216/0\.652±0\.2970\.652\\pm 0\.297/0\.254±0\.1570\.254\\pm 0\.157\); the gated variant,0\.4030\.403\. Both trail every deterministic baseline except LogME and H\-score, andhaddh\_\{\\text\{add\}\}by a wide margin\. The standard deviations are large relative to the means \(±0\.216\\pm 0\.216against a mean of0\.2940\.294on BW\), so single\-seed ARC numbers are unreliable estimates of transfer performance\. Averaging predictions across seeds before correlating, rather than averaging correlations, partially closes the gap \(mean0\.5950\.595:0\.4820\.482/0\.9120\.912/0\.3900\.390\) but still falls short ofhaddh\_\{\\text\{add\}\}and of ridge on ARC’s own input\. ARC uses only PDDL\-derived features and a labeled support set, with no target\-domain labels or updates at test time — yet a linear model using strictly less of that information outperforms it\. Appendix[C](https://arxiv.org/html/2610.26964#A3)tests whether this is specific to one design choice \(attention direction, feature combination, residualization\) and finds the shortfall persists throughout\.

Table 2:Absolute Spearman correlation within fixed object\-count groups\. B1–B5 are the five generator size levels \(object counts2,3,4,6,82,3,4,6,8for BW/MBW and4,5,6,7,94,5,6,7,9for LOG\)\. Group sizes areN=40,40,24,13,9N=40,40,24,13,9\(BW\),40,40,40,40,440,40,40,40,4\(LOG; B5 undefined, two distinct plan lengths\),40,40,28,14,1140,40,28,14,11\(MBW\); small groups are noisy\. Object count is constant within a group, so its baseline has zero ranking capacity\.A coarse\-proxy explanation does not hold\.Within fixed object\-count groups, where\|𝒪\|\|\\mathcal\{O\}\|carries no ranking information, ridge onxsx\_\{s\}keeps mean\|ρ\|=0\.49\|\\rho\|=0\.49/0\.940\.94/0\.170\.17\(BW/LOG/MBW; Table[2](https://arxiv.org/html/2610.26964#S6.T2)\) — real within\-group signal, strongly on LOG, weakly on MBW; we do not have an explanation for the gap between the two Blocksworld variants, which share a state space\. ARC’s within\-group correlations are weaker still \(0\.240\.24/0\.320\.32/0\.190\.19\), trailing ridge in all three domains\. Which cheap statistic wins also depends on the domain: goal count and ridge dominate object count on LOG, while object count dominates ridge on BW and MBW — full breakdown in Appendix[B\.5](https://arxiv.org/html/2610.26964#A2.SS5)\.

Robustness\.The baseline ordering is not an artifact of one split: in leave\-one\-domain\-out over all seven domains, ridge exceeds object count on six of seven \(mean0\.7320\.732vs\.0\.5200\.520\), and ARC, retrained per fold, trails ridge on all seven \(mean0\.6400\.640vs\.0\.7320\.732; Appendix[B\.2](https://arxiv.org/html/2610.26964#A2.SS2)\)\. Excluding the few BFS\-solved instances withn⋆=0n^\{\\star\}=0changes the means to0\.8130\.813/0\.8090\.809/0\.6430\.643/0\.9310\.931\(goal count/ridge/object count/haddh\_\{\\text\{add\}\}, the last unchanged to three decimals\)\. Solver\-effort association, the LLM\-based difficulty baseline, and three custom non\-IPC domains extend this picture further \(Appendices[B\.6](https://arxiv.org/html/2610.26964#A2.SS6),[B\.7](https://arxiv.org/html/2610.26964#A2.SS7),[E](https://arxiv.org/html/2610.26964#A5)\)\.

### 6\.2Semantic Perturbations Separate Structural from Behavioral Difficulty

Section[6\.1](https://arxiv.org/html/2610.26964#S6.SS1)asked whether difficulty can be*predicted*from structure; here we ask whether an LLM’s*behavioral*success tracks that same difficulty, or moves independently of it when only the problem’s symbols change\. Qwen 2\.5\-72B is the system under study here — generating and attempting plans, not predicting difficulty \(that role is evaluated separately in Appendix[B\.7](https://arxiv.org/html/2610.26964#A2.SS7)\)\.

We progressively corrupt the same 40 BFS\-solved Blocksworld instances\. For eachk∈\{0,25,50,75,100\}%k\\in\\\{0,25,50,75,100\\\}\\%, we replace a fractionkkof predicate and action names with meaningless tokens, applied consistently across domain and problem files\. This preserves every precondition, effect, state, goal, and optimal plan lengthn⋆​\(π\)n^\{\\star\}\(\\pi\); only the vocabulary’s readability changes\. A plan is valid only if every action uses a name from the renamed domain shown to the model and, mapped back, passes a state\-simulating executor \(parsing, arity, preconditions, goal; Appendix[A\.2](https://arxiv.org/html/2610.26964#A1.SS2)\)\.

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 lengthsn⋆​\(π\)n^\{\\star\}\(\\pi\)\.Success falls from67\.5%67\.5\\%to40\.0%40\.0\\%\(Table[3](https://arxiv.org/html/2610.26964#S6.T3)\); the endpoint intervals,\[52\.0,79\.9\]\[52\.0,79\.9\]and\[26\.3,55\.4\]\[26\.3,55\.4\], barely overlap\. The decline is not perfectly monotonic step to step \(47\.5→37\.5→40\.047\.5\\to 37\.5\\to 40\.0across the last three levels\), consistent withN=40N=40being too small to resolve small adjacent differences; we read the endpoint\-to\-endpoint effect, not a strict trend\. Refusal rate is0%0\\%at every level — the model always attempts a plan, and the effect is carried entirely by a rising rate of malformed and inapplicable actions\.

Structural difficulty is unchanged acrosskkby construction\. Comparing structural estimators across BW and MBW in Table[1](https://arxiv.org/html/2610.26964#S6.T1)is*not*a paired test of this, since they are independently generated instance sets, not renamings of the same instances \(goal count0\.7640\.764vs\.0\.6730\.673; ridge0\.6440\.644vs\.0\.5870\.587; object count0\.7640\.764vs\.0\.6620\.662\)\. The paired test is the scrambling experiment itself, wheren⋆​\(π\)n^\{\\star\}\(\\pi\)is identical for every instance at everykk: the27\.527\.5\-point drop, with no accompanying refusal\-rate change, is attributable entirely to semantic interpretability\. The same transition system, the same optimal plan length, the same object count produce a substantially different success rate purely as a function of vocabulary interpretability\.

### 6\.3Structural Difficulty Alone Is Insufficient for LLM Routing

Each instance is routed to Qwen 2\.5\-72B or a symbolic fallback; a routed instance counts as solved only if the selected component returns a valid plan\. We route structurally easy instances to the LLM, motivated by LLM failure rates rising sharply with plan length\([Valmeekam et al\., 2023b](https://arxiv.org/html/2610.26964#bib.bib22)\), while the symbolic solver is guaranteed correct whenever a plan exists, at the cost of speed\. Static always uses the fallback; Oracle picks the successful component per instance\. Zero\-shot \(ZS\) policies threshold a structural score alone; few\-shot \(FS\) policies additionally calibrate on 140 target\-domain LLM outcomes\. We include goal count as the strongestO⁡\(1\)O\(1\)statistic in Table[1](https://arxiv.org/html/2610.26964#S6.T1);haddh\_\{\\text\{add\}\}would likely be stronger still, which we flag as a natural extension rather than one we have run\.

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 both100%100\\%because the symbolic fallback always succeeds on these BFS\-solvable instances \(no time or resource budget is imposed\)\.What Static==Oracle=100%=100\\%means\.The fallback always succeeds, so no policy can exceed100%100\\%, and routing to the LLM can only match or risk that outcome, not improve it; this table does not measure speed or cost\. We read it instead as asking: among instances routed to the LLM, how often would it also have succeeded? A comparison between scoring methods, not between routing and never\-routing\.

ARC\-FS is the strongest routing signal despite being the weakest ranker\.ARC\-FS reaches9999–100%100\\%on every domain, ahead of\|𝒪\|\|\\mathcal\{O\}\|\-FS \(86\.086\.0/77\.077\.0/85\.085\.0\) and Goal\-FS \(64\.064\.0everywhere\); ARC\-ZS is the best zero\-shot signal on BW and LOG, tied on MBW\. This is notable because ARC was the*weakest*ranker in Section[6\.1](https://arxiv.org/html/2610.26964#S6.SS1)\. Ranking requires correct order across the full difficulty range; routing requires only separating “likely succeeds” from “likely fails” at one threshold, a coarser distinction a poor ranker can apparently still support\. We do not read this as rehabilitating ARC as an estimator — routing performance should not be assumed to track ranking performance, in either direction\.

LOG is where every zero\-shot policy is weakest \(≤50%\\leq 50\\%\) and where calibration helps most \(ARC:\+49\+49points ZS→\\toFS\), consistent with the LLM’s own LOG success being near zero regardless of structural difficulty \(Appendix[A\.3](https://arxiv.org/html/2610.26964#A1.SS3)\): little for a zero\-shot score to find, so calibration does most of the work of learning where the LLM can be trusted\. A router calibrated on a small amount of target\-model feedback adapts to vocabulary\-specific LLM behavior far more than a zero\-shot structural score does \- using a score that is, in isolation, a poor ranker\. Practical hybrid systems should combine a general structural score with behavioral feedback rather than relying on either alone: zero\-shot scores here are modest \(at best73%73\\%correctly identified as LLM\-tractable\), while 140 calibration examples close most of the remaining gap for every method tested\.

## 7Conclusion

We asked whether the structural difficulty of a classical planning instance can be estimated without solving it, and whether an LLM’s actual planning success tracks that difficulty\. On seven STRIPS domains, structural difficulty is well estimated by simple, training\-free means:haddh\_\{\\text\{add\}\}reaches mean\|ρ\|=0\.931\|\\rho\|=0\.931with optimal plan length, goal count0\.8020\.802, ridge on 28 structural features0\.7070\.707, object count0\.6570\.657\. Ridge beats object count on six of seven domains leave\-one\-domain\-out, andhaddh\_\{\\text\{add\}\}’s correctness is independently verified: zero failures re\-simulating1,0061\{,\}006saved BFS plans against freshly reconstructed action sets\.

The learned\-estimation result is squarely negative\. ARC, built specifically to combine structural features with foundation\-model embeddings under a protocol fixed before training \(five seeds, early stopping, a pre\-declared added\-value criterion\), does not meet that criterion: mean0\.4000\.400\(0\.4030\.403gated\), below every deterministic baseline except LogME and H\-score, below a linear model on its own inputs \(0\.7070\.707\), below its own weaker input scored alone \(xex\_\{e\}alone:0\.4120\.412\), far belowhaddh\_\{\\text\{add\}\}\. The shortfall persists leave\-one\-domain\-out, within object\-count groups, on three custom domains outside the design loop, and across every attention\-direction and residualization variant tested, including one post hoc setting we decline to adopt because selecting it required looking at the test domains\. Prediction\-level ensembling partially closes the gap \(0\.5950\.595\) but does not close it\. We read this as a genuine negative result for cross\-domain learned retrieval on this problem: a classical, zero\-training heuristic transferring better than a purpose\-built learned architecture is itself a useful finding, and future estimators in this space should be reported alongsidehaddh\_\{\\text\{add\}\}, not only against weaker scalar baselines\.

A controlled predicate\-renaming intervention holds structural difficulty fixed by construction while varying vocabulary interpretability: valid\-plan success falls from67\.5%67\.5\\%to40\.0%40\.0\\%as corruption rises from0%0\\%to100%100\\%, refusal rate flat at0%0\\%throughout, the entire effect carried by malformed and inapplicable actions rather than the model declining to answer\. This separates*structural difficulty*, already well estimated byhaddh\_\{\\text\{add\}\}, from*behavioral difficulty*, which depends on semantic interpretability and is not reducible to it\. The consequence for hybrid planning is more nuanced than “routing helps” or “routing fails”: with no solver\-failure budget modeled, every policy is bounded above by always\-use\-the\-solver, so routing instead measures which structural score best identifies LLM\-tractable instances — and a calibrated ARC score is the best such signal despite being the weakest ranker in the paper, indicating routing and ranking are distinct tasks\. An LLM given ARC’s own conditioning information, with no training, estimates difficulty via in\-context reasoning \(mean\|ρ\|=0\.826\|\\rho\|=0\.826\) far better than ARC does after training, second only tohaddh\_\{\\text\{add\}\}overall\.

Structural planning difficulty across these domains is close to a solved estimation problem: a 1970s\-vintage AI\-planning technique solves it better than the learned architecture we purpose\-built for the task, and an LLM’s untrained in\-context reasoning over the same inputs matches that technique closely\. The open problem for hybrid LLM\-planning systems is not a better structural\-difficulty predictor, but modeling the semantic, vocabulary\-dependent component of LLM behavior that a structural score, by construction, cannot see, and that routing cannot fully compensate for even when calibrated\.

## References

- \[1\]K\. Valmeekam, M\. Marquez, S\. Sreedharan, and S\. Kambhampati\(2023\)PlanBench: an extensible benchmark for evaluating large language models on planning and reasoning about change\.InAdvances in Neural Information Processing Systems,Vol\.36\.External Links:[Link](https://arxiv.org/abs/2206.10498v4)Cited by:[§1](https://arxiv.org/html/2610.26964#S1.p1.1),[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px1.p1.1)\.
- \[2\]K\. Valmeekam, A\. Olmo, S\. Sreedharan, and S\. Kambhampati\(2023\)Large language models still can’t plan \(a benchmark for LLMs on planning and reasoning about change\)\.InNeurIPS 2023 Foundation Models for Decision Making Workshop,External Links:[Link](https://arxiv.org/abs/2206.10498)Cited by:[§1](https://arxiv.org/html/2610.26964#S1.p1.1),[§1](https://arxiv.org/html/2610.26964#S1.p3.1),[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px1.p1.1),[§6\.3](https://arxiv.org/html/2610.26964#S6.SS3.p1.1)\.
- \[3\]J\. Wei, X\. Wang, D\. Schuurmans, M\. Bosma, F\. Xia, E\. Chi, Q\. V\. Le, D\. Zhou,et al\.\(2022\)Chain\-of\-thought prompting elicits reasoning in large language models\.Advances in neural information processing systems35,pp\. 24824–24837\.Cited by:[§1](https://arxiv.org/html/2610.26964#S1.p1.1),[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px1.p1.1)\.
- \[4\]K\. Stechly, M\. Marquez, and S\. Kambhampati\(2023\)GPT\-4 doesn’t know it’s wrong: an analysis of iterative prompting for reasoning problems\.InNeurIPS 2023 Workshop on Robustness of Few\-shot and Zero\-shot Learning in Foundation Models,External Links:[Link](https://arxiv.org/abs/2310.12397)Cited by:[§1](https://arxiv.org/html/2610.26964#S1.p1.1),[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px1.p1.1)\.
- \[5\]S\. Kambhampati, K\. Valmeekam, L\. Guan, M\. Verma, K\. Stechly, S\. Bhambri, L\. Saldyt, and A\. Murthy\(2024\)LLMs can’t plan, but can help planning in LLM\-Modulo frameworks\.InProceedings of the 41st International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.235\.External Links:[Link](https://arxiv.org/abs/2402.01817)Cited by:[§1](https://arxiv.org/html/2610.26964#S1.p1.1),[§1](https://arxiv.org/html/2610.26964#S1.p3.1),[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px2.p1.1)\.
- \[6\]T\. Silver, S\. Dan, K\. Srinivas, J\. B\. Tenenbaum, L\. Kaelbling, and M\. Katz\(2024\)Generalized planning in pddl domains with pretrained large language models\.InProceedings of the AAAI conference on artificial intelligence,Vol\.38,pp\. 20256–20264\.Cited by:[§1](https://arxiv.org/html/2610.26964#S1.p1.1),[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px1.p1.1)\.
- \[7\]J\. Tang, Y\. Yan, Z\. Ye, Z\. Zheng, Y\. Jin,et al\.\(2025\)Think small, plan smart: minimalist symbolic abstraction and heuristic subspace search for llm\-guided task planning\.arXiv preprint arXiv:2501\.15214\.Cited by:[§1](https://arxiv.org/html/2610.26964#S1.p3.1),[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px1.p1.1)\.
- \[8\]M\. Chiari, N\. Cardozo, and P\. Restrepo\(2025\)LLM\-guided heuristic search for classical planning\.InProceedings of the 39th AAAI Conference on Artificial Intelligence,External Links:[Link](https://arxiv.org/abs/2501.06458)Cited by:[§1](https://arxiv.org/html/2610.26964#S1.p3.1),[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px2.p1.1)\.
- \[9\]K\. You, Y\. Liu, J\. Wang, and M\. Long\(2021\)Logme: practical assessment of pre\-trained models for transfer learning\.InInternational conference on machine learning,pp\. 12133–12143\.Cited by:[§1](https://arxiv.org/html/2610.26964#S1.p4.1),[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px3.p1.1)\.
- \[10\]Y\. Bao, Y\. Li, S\. Huang, L\. Zhang, L\. Zheng, A\. Zamir, and L\. Guibas\(2019\)An information\-theoretic approach to transferability in task transfer learning\.InProceedings of the 2019 IEEE International Conference on Image Processing,pp\. 2309–2313\.External Links:[Document](https://dx.doi.org/10.1109/ICIP.2019.8803726)Cited by:[§1](https://arxiv.org/html/2610.26964#S1.p4.1),[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px3.p1.1)\.
- \[11\]K\. Valmeekam, A\. Olmo, S\. Sreedharan, and S\. Kambhampati\(2022\)Large language models still can’t plan \(a benchmark for llms on planning and reasoning about change\)\.InNeurIPS 2022 Foundation Models for Decision Making Workshop,Cited by:[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px1.p1.1)\.
- \[12\]D\. McDermott, M\. Ghallab, A\. Howe, C\. Knoblock, A\. Ram, M\. Veloso, D\. Weld, and D\. Wilkins\(1998\)PDDL—the planning domain definition language\.Technical reportTechnical ReportCVC TR\-98\-003/DCS TR\-1165,Yale Center for Computational Vision and Control\.External Links:[Link](http://www.cs.yale.edu/homes/dvm/papers/pddl-bnf.pdf)Cited by:[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px1.p1.1)\.
- \[13\]D\. Long and M\. Fox\(2003\)The 3rd international planning competition: results and analysis\.InJournal of Artificial Intelligence Research,Vol\.20,pp\. 1–59\.External Links:[Document](https://dx.doi.org/10.1613/jair.1138)Cited by:[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px1.p1.1)\.
- \[14\]P\. Ferber, T\. Ma, S\. Huo, J\. Chen, and M\. Katz\(2019\)Ipc: a benchmark data set for learning with graph\-structured data\.arXiv preprint arXiv:1905\.06393\.Cited by:[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px1.p1.1)\.
- \[15\]T\. Silver and R\. Chitnis\(2020\)Pddlgym: gym environments from pddl problems\.arXiv preprint arXiv:2002\.06432\.Cited by:[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px1.p1.1)\.
- \[16\]L\. Guan, K\. Valmeekam, S\. Sreedharan, and S\. Kambhampati\(2023\)Leveraging pre\-trained large language models to construct and utilize world models for model\-based task planning\.Advances in Neural Information Processing Systems36,pp\. 79081–79094\.Cited by:[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px1.p1.1)\.
- \[17\]M\. Verma, S\. Bhambri, and S\. Kambhampati\(2025\)PDDL\-INSTRUCT: grounded plan generation via instruction\-tuned PDDL synthesis\.arXiv preprint arXiv:2509\.13351\.External Links:[Link](https://arxiv.org/abs/2509.13351)Cited by:[Table 18](https://arxiv.org/html/2610.26964#A4.T18.2.6.1.1.1),[Appendix D](https://arxiv.org/html/2610.26964#A4.p1.1),[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px1.p1.1)\.
- \[18\]M\. Tantakoun, C\. Muise, and X\. Zhu\(2025\)LLMs as planning formalizers: a survey for leveraging large language models to construct automated planning models\.InFindings of the Association for Computational Linguistics: ACL 2025,pp\. 25167–25188\.Cited by:[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px1.p1.1)\.
- \[19\]H\. Wei, Z\. Zhang, S\. He, T\. Xia, S\. Pan, and F\. Liu\(2025\)Plangenllms: a modern survey of llm planning capabilities\.InProceedings of the 63rd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),pp\. 19497–19521\.Cited by:[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px1.p1.1)\.
- \[20\]A\. Gundawar, K\. Valmeekam, M\. Verma, and S\. Kambhampati\(2024\)Robust planning with compound llm architectures: an llm\-modulo approach\.arXiv preprint arXiv:2411\.14484\.Cited by:[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px2.p1.1)\.
- \[21\]A\. B\. Corrêa, A\. G\. Pereira, and J\. Seipp\(2026\)Classical planning with llm\-generated heuristics: challenging the state of the art with python code\.Advances in Neural Information Processing Systems38,pp\. 42070–42108\.Cited by:[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px2.p1.1)\.
- \[22\]H\. Li, Z\. Chen, S\. Liu, Y\. Lu, and F\. Liu\(2024\)Systematic analysis of llm contributions to planning: solver, verifier, heuristic\.arXiv preprint arXiv:2412\.09666\.Cited by:[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px2.p1.1)\.
- \[23\]W\. Yu, J\. Tang, Y\. Zhang, Y\. Feng, C\. Wu, K\. Jin, and H\. H\. Zhuo\(2025\)Inspire or predict? exploring new paradigms in assisting classical planners with large language models\.arXiv preprint arXiv:2508\.11524\.Cited by:[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px2.p1.1)\.
- \[24\]Y\. Bao, Y\. Li, S\. Huang, L\. Zhang, A\. R\. Zamir, and L\. J\. Guibas\(2018\)An information\-theoretic metric of transferability for task transfer learning\.Cited by:[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px3.p1.1)\.
- \[25\]C\. Nguyen, T\. Hassner, M\. Seeger, and C\. Archambeau\(2020\)Leep: a new measure to evaluate transferability of learned representations\.InInternational conference on machine learning,pp\. 7294–7305\.Cited by:[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px3.p1.1)\.
- \[26\]N\. Sae\-Bae and S\. Laohakiat\(2025\)Transferability prediction in sparse data regime using multi\-resolution knn predictor\.Neural Computing and Applications37\(31\),pp\. 26281–26301\.Cited by:[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px3.p1.1)\.
- \[27\]C\. Finn, P\. Abbeel, and S\. Levine\(2017\)Model\-agnostic meta\-learning for fast adaptation of deep networks\.InProceedings of the 34th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.70,pp\. 1126–1135\.External Links:[Link](https://arxiv.org/abs/1703.03400)Cited by:[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px4.p1.1)\.
- \[28\]J\. Snell, K\. Swersky, and R\. Zemel\(2017\)Prototypical networks for few\-shot learning\.InAdvances in Neural Information Processing Systems,Vol\.30\.External Links:[Link](https://arxiv.org/abs/1703.05175)Cited by:[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px4.p1.1)\.
- \[29\]G\. Blanchard, G\. Lee, and C\. Scott\(2011\)Generalizing from several related classification tasks to a new unlabeled sample\.InAdvances in Neural Information Processing Systems,Vol\.24,pp\. 2178–2186\.Cited by:[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px4.p1.1)\.
- \[30\]G\. Blanchard, A\. A\. Deshmukh, U\. Dogan, G\. Lee, and C\. Scott\(2021\)Domain generalization by marginal transfer learning\.Journal of machine learning research22\(2\),pp\. 1–55\.Cited by:[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px4.p1.1)\.
- \[31\]N\. Reimers and I\. Gurevych\(2019\)Sentence\-BERT: sentence embeddings using siamese BERT\-networks\.InProceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing,pp\. 3982–3992\.External Links:[Document](https://dx.doi.org/10.18653/v1/D19-1410)Cited by:[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px4.p1.1)\.
- \[32\]A\. van den Oord, Y\. Li, and O\. Vinyals\(2018\)Representation learning with contrastive predictive coding\.arXiv preprint arXiv:1807\.03748\.External Links:[Link](https://arxiv.org/abs/1807.03748)Cited by:[§2](https://arxiv.org/html/2610.26964#S2.SS0.SSS0.Px4.p1.1)\.
- \[33\]J\. R\. Landis and G\. G\. Koch\(1977\)The measurement of observer agreement for categorical data\.Biometrics33\(1\),pp\. 159–174\.Cited by:[§E\.3](https://arxiv.org/html/2610.26964#A5.SS3.p4.1),[Table 20](https://arxiv.org/html/2610.26964#A5.T20.2.7.1.1.1)\.

## Appendix AData, Labels, and Evaluation Protocol

This appendix clarifies the supervision used to train ARC and the protocol used to evaluate LLM\-generated plans\.

### A\.1Label Availability and Supervision

Each planning domain containsN=200N=200generated instances \(40 at each of five size levels\)\. ARC is trained using a single supervision signal derived from BFS: the optimal plan length,

yr​\(π\)=n⋆​\(π\),y\_\{r\}\(\\pi\)=n^\{\\star\}\(\\pi\),used to learn a continuous structural\-difficulty ranking\. This label is available whenever breadth\-first search returns a solution under the budgetB=\(Tmax=12,Nmax=5,000\)B=\(T\_\{\\max\}=12,N\_\{\\max\}=5\{,\}000\), applied identically to every domain\. An instance for which the search budget is exhausted is excluded from training and from all rank\-based evaluation, because failure under a finite budget neither establishes unsolvability nor yields a plan\-length value; such instances are never assigned a substitute label, and no head of the model is supervised with them\.

Table 5:Per\-domain data statistics \(200 generated instances per domain\)\. “BFS\-solved” is the number of instances for which BFS finds a plan withinBB; 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\.Coverage of the label is incomplete and domain\-dependent \(Table[5](https://arxiv.org/html/2610.26964#A1.T5)\): between63\.0%63\.0\\%\(Blocksworld, Satellite\) and99\.5%99\.5\\%\(Rovers\) of generated instances are BFS\-solved; the remainder are excluded from every computation\. The rank\-based correlations reported throughout the main text are evaluated only on instances that possess a valid plan\-length target\. Two properties of the labels deserve mention\. First, the source domains Depot \(n⋆∈\[7,10\]n^\{\\star\}\\in\[7,10\]\) and Rovers \(n⋆∈\[2,5\]n^\{\\star\}\\in\[2,5\]\) cover narrow ranges of plan length\. Second, a small number of BFS\-solved instances haven⋆=0n^\{\\star\}=0\(the goal already holds initially; 15 in BW, 6 in LOG, 10 in MBW\)\. They are included in all primary results; excluding them changes the test\-domain means to0\.8130\.813\(goal count\),0\.8090\.809\(ridge onxsx\_\{s\}\), and0\.6430\.643\(object count\), withN=111N=111,158158,123123remaining instances for BW, LOG, MBW\. All preprocessing transformations, including feature standardisation, PCA, and residualisation, are fitted exclusively on pooled source\-domain instances and frozen before evaluation on the held\-out domains\.

Because BFS is capped at a fixed budget, the hardest instances in each domain’s difficulty distribution are systematically more likely to be excluded from the label\. The correlations reported throughout this paper should therefore be interpreted as characterizing the difficulty ordering within the search\-feasible regime, and may not extend uniformly into the harder, budget\-exceeding tail of each domain\.

### A\.2LLM Prompt and Plan\-Validity Protocol

We evaluate Qwen 2\.5\-72B on the 200 generated instances of each held\-out domain for the routing experiment, and on 40 BFS\-solved Blocksworld instances at each corruption level for the scrambling experiment\. Generation uses temperature00, a maximum of2,0482\{,\}048output tokens, and no domain\-specific demonstrations\. Each prompt contains the complete PDDL domain file and the problem file for one instance\. The model is instructed to reason through the state transitions and to return only the final action sequence\. The prompt template is reproduced in full in Appendix[D](https://arxiv.org/html/2610.26964#A4)\.

Generated plans are evaluated by execution rather than by textual similarity to a reference plan\. A custom PDDL state\-space executor performs three checks: \(1\) every output line must parse as a syntactically valid grounded action; \(2\) each action’s preconditions must hold in the state produced by all preceding actions; and \(3\) the goal condition must hold after the final action is applied\. A response is counted as a valid plan only if all three checks succeed\. Any malformed action, inapplicable action, or final state that fails to satisfy the goal is counted as a planning failure; no partial credit is assigned\. For renamed domains, an action name that does not belong to the renamed domain shown to the model is also counted as a failure, and the remaining actions are mapped back to the original names before the executor is applied \(renaming preserves the transition system\)\.

For the semantic\-corruption analysis, a refusal is recorded when the model returns the designated NOPLAN response or produces an empty response\. Refusals are reported separately from invalid generated plans: the former indicate that no executable action sequence was proposed, whereas the latter indicate that the model attempted a plan that failed formal verification\.

### A\.3LLM Capability Threshold Across Model Families

To assess whether the qualitative findings of Section[6\.2](https://arxiv.org/html/2610.26964#S6.SS2)are specific to Qwen 2\.5\-72B or reflect a more general property of current open\-weight LLMs, we evaluate the same BW/LOG/MBW protocol \(Appendix[A\.2](https://arxiv.org/html/2610.26964#A1.SS2)\) on three additional models spanning a10×10\\timesparameter range and two model families distinct from Qwen: Mistral\-7B, Gemma2\-9B, and Qwen2\.5\-14B\.

Table 6:LLM planning success rates on BW/LOG/MBW using the state\-simulating validator \(precondition checking \+ goal verification via forward state simulation\)\.Across all four models \(N=40N=40per cell\), none solves any Logistics instance, consistent with Logistics being a harder planning domain for every model family and scale tested here\. On Blocksworld, model size does not predict success monotonically: Qwen2\.5\-14B and Gemma2\-9B both reach40\.0%40\.0\\%, while the larger Qwen2\.5\-72B reaches only30\.0%30\.0\\%and Mistral\-7B reaches0\.0%0\.0\\%\. On Mystery\-Blocksworld, Qwen2\.5\-72B is the strongest model tested \(35\.0%35\.0\\%\), ahead of Gemma2\-9B \(27\.5%27\.5\\%\), with Qwen2\.5\-14B and Mistral\-7B both at0\.0%0\.0\\%\. We do not have an explanation for Qwen2\.5\-72B’s Blocksworld\-to\-Mystery\-Blocksworld pattern \(worse on the un\-renamed domain than two much smaller models, best of all four on the renamed one\); it is not predicted by parameter count, and we note it as an open question rather than speculate further\. We did not have the resources to evaluate closed\-weight frontier models or models substantially larger than 72B under the same fully\-logged protocol, and we do not extend any claim to that regime\.

## Appendix BEvidence for Cross\-Domain Structural Estimation

This appendix provides additional evidence for the cross\-domain structural\-estimation results reported in the main paper\. The analyses address seven complementary questions: whether the primary correlations are statistically stable; whether transfer persists under alternative domain splits; whether stronger non\-episodic learners change the picture; whether inexpensive scalar statistics are sufficient; whether predictions carry information after controlling for object count; whether they are associated with search effort measured by a different planner; and whether a purely LLM\-based predictor, given the same conditioning information, reproduces the result\. These analyses are intended to delimit, rather than broaden, the main claim: structural statistics transfer across domains, and any added value of a learned estimator such as ARC has to be judged against them\.

### B\.1Confidence Intervals for the Primary Result

Table[7](https://arxiv.org/html/2610.26964#A2.T7)reports approximate95%95\\%confidence intervals for the primary Spearman correlations\. The intervals are computed using the Fisher transformation,

z=tanh−1⁡\(ρ\),SE⁡\(z\)=1N−3,z=\\tanh^\{\-1\}\(\\rho\),\\qquad\\operatorname\{SE\}\(z\)=\\frac\{1\}\{\\sqrt\{N\-3\}\},followed by transformation back to the correlation scale, withNNthe number of BFS\-solved instances of the domain \(126126,164164,133133for BW, LOG, MBW\)\. This approximation treats the reported Spearman coefficient as a Pearson correlation over ranked observations\.

Table 7:Approximate95%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](https://arxiv.org/html/2610.26964#S6.T1)\(±0\.157\\pm 0\.157to±0\.297\\pm 0\.297\), so ARC’s real interval is wider than shown here\.We do not infer a paired method comparison from interval overlap alone because the estimators are evaluated on the same instances\. We therefore also compute paired bootstrap confidence intervals \(2,0002\{,\}000resamples of the target instances, recomputing both correlations on each resample\) for

Δ​ρ=ρRidge−ρ\|𝒪\|:\\Delta\\rho=\\rho\_\{\\mathrm\{Ridge\}\}\-\\rho\_\{\|\\mathcal\{O\}\|\}:−0\.119\-0\.119\[−0\.249,−0\.005\]\[\-0\.249,\-0\.005\]on Blocksworld,\+0\.345\+0\.345\[\+0\.237,\+0\.460\]\[\+0\.237,\+0\.460\]on Logistics, and−0\.075\-0\.075\[−0\.198,\+0\.032\]\[\-0\.198,\+0\.032\]on Mystery\-Blocksworld\. The sign of the difference thus depends on the domain, and the Mystery\-Blocksworld interval includes zero\. Even without a formal paired bootstrap for ARC, the non\-overlap is already clear from Table[7](https://arxiv.org/html/2610.26964#A2.T7)’s intervals alone on Blocksworld \(ARC⁡\[0\.126,0\.446\]\\mathrm\{ARC\}\\ \[0\.126,0\.446\]vs\.Ridge⁡\[0\.529,0\.736\]\\mathrm\{Ridge\}\\ \[0\.529,0\.736\]\) and is unambiguous againsthaddh\_\{\\text\{add\}\}\(0\.9310\.931\) on every domain; a formal paired bootstrap using ARC’s saved per\-instance predictions, which would additionally propagate seed variance, is left as a direction for a more exhaustive treatment\.

### B\.2Broader Domain Generalisation

The primary evaluation fixes Depot, Rovers, and Satellite as source domains, Gripper as the validation domain, and Blocksworld, Logistics, and Mystery\-Blocksworld as held\-out test domains\. To assess sensitivity to this particular partition, we additionally perform leave\-one\-domain\-out evaluation over the seven domains: for each row of Table[8](https://arxiv.org/html/2610.26964#A2.T8), the named domain is excluded from model fitting \(ridge regression is retrained on the other six domains\) and used as the evaluation domain\.

Held\-out domain\|ρ\|ARC\|\\rho\|\_\{\\mathrm\{ARC\}\}\|ρ\|Ridge\|\\rho\|\_\{\\mathrm\{Ridge\}\}\|ρ\|\|𝒪\|\|\\rho\|\_\{\|\\mathcal\{O\}\|\}ΔRidge−\|𝒪\|\\Delta\_\{\\mathrm\{Ridge\}\-\|\\mathcal\{O\}\|\}ΔARC−Ridge\\Delta\_\{\\mathrm\{ARC\}\-\\mathrm\{Ridge\}\}Blocksworld0\.730±\\pm0\.0520\.8730\.764\+0\.110\+0\.110−0\.143\-0\.143Depot0\.533±\\pm0\.2810\.7680\.768\+0\.000\+0\.000−0\.235\-0\.235Gripper†0\.879±\\pm0\.0220\.9130\.503\+0\.410\+0\.410−0\.034\-0\.034Logistics0\.915±\\pm0\.0020\.9170\.544\+0\.373\+0\.373−0\.002\-0\.002Mystery\-Blocksworld0\.784±\\pm0\.0270\.8810\.662\+0\.219\+0\.219−0\.097\-0\.097Rovers0\.040±\\pm0\.0150\.0700\.051\+0\.019\+0\.019−0\.030\-0\.030Satellite0\.597±\\pm0\.1540\.6980\.346\+0\.352\+0\.352−0\.101\-0\.101Mean0\.6400\.7320\.520\+0\.212\+0\.212−0\.092\-0\.092Standard deviation \(across domains\)0\.2760\.2800\.237——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±\\pmstd 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\-0\.235\) and Satellite \(−0\.101\-0\.101\), and is closest to parity only on Logistics \(−0\.002\-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\.Ridge regression on the structural features exceeds object count on six of the seven held\-out domains \(mean0\.7320\.732vs\.0\.5200\.520\), ties on Depot, and both are close to zero on Rovers, whose plan lengths span only22–55\. Leave\-one\-domain\-out thus supports the ordering of the structural baselines seen in the primary split, with a larger average margin for ridge than in the primary split\. ARC does not close this gap by seeing more source domains: it trails ridge regression on all seven held\-out domains \(mean0\.6400\.640vs\.0\.7320\.732\), with the largest shortfalls on Depot and Satellite, the two domains where ridge itself gains the most from the extra source domains relative to the primary split\.

### B\.3Comparison with Stronger Learned Baselines

The main paper compares ARC with object cardinality, goal count, ridge regression, LogME, H\-score, and a non\-episodic MLP\. We additionally evaluate tree\-based, kernel, boosting, and ranking regressors using the same2828\-dimensional structural representationxsx\_\{s\}, trained on the source domains with the raw plan length as target, together with a Random Forest given bothxsx\_\{s\}and the foundation\-model embeddingxex\_\{e\}\. These comparisons test whether conventional learners with more capacity than ridge regression, or more information than ridge regression, change the picture\.

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 ofn⋆n^\{\\star\}as graded relevance\. ARC’s row is its five\-seed mean from Table[1](https://arxiv.org/html/2610.26964#S6.T1)\.Table[9](https://arxiv.org/html/2610.26964#A2.T9)shows that ridge regression is the strongest of thexsx\_\{s\}\-only*learned*methods \(mean\|ρ\|=0\.707\|\\rho\|=0\.707\), followed by gradient boosting \(0\.6740\.674\) and XGBoost \(0\.6330\.633\); Random Forest onxsx\_\{s\}alone \(0\.3880\.388\) and kernel SVR \(0\.2520\.252\) transfer poorly\. Giving Random Forest the embedding as well as the structural features raises its mean from0\.3880\.388to0\.5740\.574— a substantial within\-method improvement, unlike the roughly neutral effect concatenation has on ridge regression \(Appendix[C\.1](https://arxiv.org/html/2610.26964#A3.SS1)\) — but this still falls short of ridge regression onxsx\_\{s\}alone \(0\.7070\.707\) and far short ofhaddh\_\{\\text\{add\}\}\(0\.9310\.931\)\. No learner onxsx\_\{s\},xex\_\{e\}, or their concatenation, and no training\-free scalar statistic, exceedshaddh\_\{\\text\{add\}\}\. ARC, despite having access to the same foundation\-model embedding that helps Random Forest, exceeds only Random Forest onxsx\_\{s\}alone among thexsx\_\{s\}\-only learners \(0\.4000\.400vs\.0\.3880\.388\) and is beaten by every other learned method tested, including the far simpler ridge, gradient boosting, XGBoost, and LambdaMART\-style ranker\.

This table is a comparison with competitive alternatives, not an architectural ablation\. ARC differs from these baselines in its representations, episodic objective, and support\-conditioned inference; Appendix[C](https://arxiv.org/html/2610.26964#A3)tests each of these design choices directly and finds none of the tested variants closes the gap to ridge regression, let alone tohaddh\_\{\\text\{add\}\}\.

### B\.4Cheap Structural Baselines

A learned estimator is unnecessary if the target ordering can already be recovered without one\. We evaluate two kinds of training\-free surrogate: fiveO⁡\(1\)O\(1\)scalar statistics read directly off the PDDL syntax, and one classical planning heuristic that requires reconstructing the instance’s full grounded action set\.

Table 10:Absolute Spearman correlation between training\-free structural surrogates and optimal plan length on the BFS\-solved evaluation instances \(N=111N=111BW,158158LOG,123123MBW — thehaddh\_\{\\text\{add\}\}andO⁡\(1\)O\(1\)rows use the identical instance sets\)\.Among the fiveO⁡\(1\)O\(1\)statistics, goal count is strongest \(mean\|ρ\|=0\.802\|\\rho\|=0\.802,0\.9690\.969on Logistics\) and no single one dominates every domain\. All five, however, are clearly exceeded byhaddh\_\{\\text\{add\}\}\(mean0\.9310\.931\), a delete\-relaxation planning heuristic in the family of classical additive and FF\-style heuristics used to guide heuristic\-search planners: we compute it as the sum, over each unsatisfied goal fact, of the level at which that fact is first achieved in a planning graph built with all delete effects ignored, from the instance’s own initial state and full grounded action set\. This is not anO⁡\(1\)O\(1\)read: it requires the same grounded action set a real planner would use, together with a bounded graph expansion \(capped at depth3030in our implementation\), though it never performs a search over the real \(non\-relaxed\) state space and uses no target\-domain labels\.

#### Correctness verification\.

Reconstructing each domain’s grounded action set independently of the labeling code is the step most likely to silently go wrong, so we verify it directly rather than assuming it: for every one of the seven domains, we re\-simulate every already\-saved BFS\-optimal plan against the independently reconstructed action list and check it still reaches the goal\. This succeeds with zero failures on all1,0061\{,\}006BFS\-solved instances withn⋆\>0n^\{\\star\}\>0across the seven domains \(BW111/111111/111, Depot132/132132/132, Gripper157/157157/157, Logistics158/158158/158, Mystery\-BW123/123123/123, Rovers199/199199/199, Satellite126/126126/126\);haddh\_\{\\text\{add\}\}is reported only for domains that pass this check\.

#### The Logistics tie is not a coincidence\.

A paired bootstrap \(2,0002\{,\}000resamples\) ofhaddh\_\{\\text\{add\}\}against goal count givesΔ​\|ρ\|=\+0\.119\\Delta\|\\rho\|=\+0\.119\[\+0\.057,\+0\.192\]\[\+0\.057,\+0\.192\]on Blocksworld and\+0\.236\+0\.236\[\+0\.143,\+0\.344\]\[\+0\.143,\+0\.344\]on Mystery\-Blocksworld — both robustly positive — but exactlyΔ=0\.000\\Delta=0\.000with a zero\-width interval on Logistics\. In our Logistics domain, the relaxed graph reaches every unsatisfied\(at pkg city\)goal fact at the same graph depth \(any truck can relax\-reach any city in one step, since the relaxed problem ignores the precondition that a truck already be present\), sohaddh\_\{\\text\{add\}\}reduces to an exact constant multiple of the number of unsatisfied goal facts on this domain — a perfectly monotonic transform of goal count, hence an identical Spearman correlation on every resample\. This is a property of this domain’s specific action structure, not a general reason to expecthaddh\_\{\\text\{add\}\}and goal count to agree elsewhere, and they clearly do not agree on the other two domains\.

#### haddh\_\{\\text\{add\}\}as an additional feature, not just a standalone score\.

We also tested appendinghaddh\_\{\\text\{add\}\}as a 29th feature to ridge regression onxsx\_\{s\}, trained and evaluated identically to thexsx\_\{s\}\-only ridge row elsewhere in this paper\. The result is mixed, not uniformly positive: mean\|ρ\|\|\\rho\|changes by\+0\.095\+0\.095on Mystery\-Blocksworld,−0\.001\-0\.001on Logistics, and−0\.077\-0\.077on Blocksworld, relative to ridge onxsx\_\{s\}alone\.haddh\_\{\\text\{add\}\}’s strength as a*standalone*score therefore does not automatically transfer to a learned model that simply concatenates it with the existing features under an untuned ridge fit; whether a properly regularized or rescaled combination recovers more of that strength is untested\.

Table[10](https://arxiv.org/html/2610.26964#A2.T10)does not by itself show whether ARC captures information inaccessible tohaddh\_\{\\text\{add\}\}or to every scalar surrogate; the within\-size analysis below addresses the narrower question of whether predictions are reducible to object count, and the comparison ARC must ultimately be judged against ishaddh\_\{\\text\{add\}\}’s0\.9310\.931, not goal count’s0\.8020\.802\.

### B\.5Within\-Size Discrimination

Object count is a strong difficulty correlate in several planning domains\. To test whether a structural estimator merely reproduces this statistic, we compute Spearman correlation separately within groups having a fixed number of objects\. Object cardinality is constant within each group and therefore has no ranking capacity\. Groups are the five generator size levels; their sizes differ because only BFS\-solved instances are used\.

DomainObject countsB1B2B3B4B5MeanRidge onxsx\_\{s\}, Blocksworld\(2,3,4,6,8\)\(2,3,4,6,8\)0\.480\.370\.580\.450\.570\.49group sizeNN404024139Ridge onxsx\_\{s\}, Logistics\(4,5,6,7,9\)\(4,5,6,7,9\)0\.870\.960\.960\.98n/a0\.94group sizeNN404040404Ridge onxsx\_\{s\}, Mystery\-Blocksworld\(2,3,4,6,8\)\(2,3,4,6,8\)0\.070\.270\.240\.100\.190\.17group sizeNN4040281411ARC \(main\), Blocksworld\(2,3,4,6,8\)\(2,3,4,6,8\)0\.110\.320\.220\.200\.360\.24ARC \(main\), Logistics\(4,5,6,7,9\)\(4,5,6,7,9\)0\.230\.360\.330\.33n/a0\.32ARC \(main\), Mystery\-Blocksworld\(2,3,4,6,8\)\(2,3,4,6,8\)0\.150\.190\.160\.170\.270\.19Object cardinality—0\.000\.000\.000\.000\.000\.00Table 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 withN<15N<15are noisy\. ARC trails ridge regression onxsx\_\{s\}in every domain and every bucket withN≥24N\\geq 24\.As reported in Table[11](https://arxiv.org/html/2610.26964#A2.T11), ridge regression on the structural features retains substantial within\-size discrimination on Logistics \(mean\|ρ\|=0\.94\|\\rho\|=0\.94\), moderate discrimination on Blocksworld \(0\.490\.49\), and weak discrimination on Mystery\-Blocksworld \(0\.170\.17\)\. These results show that structural features carry information beyond object count in all three domains, but the performance is not uniform and the Mystery\-Blocksworld result should not be presented as strong within\-size evidence\. Correlation is also difficult to interpret when the target has little variation within a group: several groups contain only two to four distinct plan lengths \(reported per group in the data underlying the table\)\.

### B\.6Association with Solver Search Effort

Optimal plan length is a depth\-based proxy for structural difficulty rather than a complete measure of computational search cost\. To examine whether a structural estimator’s ordering is associated with another planner’s effort, we compare its predictions with A\* node expansions and A\* wall\-clock time, using an A\* implementation with a delete\-relaxation \(FF\-style\) heuristic that is independent of the BFS procedure used to construct the principal plan\-length target: different algorithm, different state representation \(a bitmask priority\-queue search rather than the labeling BFS\), and a search\-node budget \(20,00020\{,\}000\) an order of magnitude larger than the BFS label budget\. As a sanity check, A\* never returns a plan shorter than the BFS\-optimaln⋆​\(π\)n^\{\\star\}\(\\pi\)on any of the120120instances tested, as it must if both are admissible searches over the same action set\. This analysis currently covers Blocksworld and Mystery\-Blocksworld only \(A\* was implemented for these two domains’ action schemas; Logistics is not included\), on a random sample ofN=60N=60BFS\-solved instances per domain, and uses ridge regression onxsx\_\{s\}in place of ARC\.

Table 12:Association between ridge regression onxsx\_\{s\}and solver\-derived measures,N=60N=60BFS\-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\.On both domains, ridge regression’s ranking is associated with the independent A\* planner’s effort \(node expansions:0\.6830\.683,0\.5020\.502; wall\-clock time:0\.6680\.668,0\.5530\.553\) at a level broadly similar to its association with the BFS label itself \(0\.6740\.674,0\.5320\.532\), and object cardinality is associated more strongly still with A\*\-node effort on both domains \(0\.9160\.916,0\.7900\.790\)\. We describe this as*solver\-associated validation*, not proof of solver\-agnostic difficulty: it shows the structural ranking is not an artifact specific to the BFS labeling procedure, but it does not establish that any one structural statistic is a complete measure of computational search cost, and optimal plan length and search effort remain related but non\-equivalent notions of structural difficulty\.

### B\.7Comparison with a Purely LLM\-Based Difficulty Predictor

A natural alternative to ARC’s dedicated architecture is to ask an LLM to predict instance difficulty directly, conditioned on the same information available to ARC’s support set: a collection of labeled source\-domain instances, each paired with its optimal plan length\. If an LLM given this conditioning information could match the ranking performance of structural estimators through in\-context reasoning alone, this would suggest that a dedicated estimator is unnecessary\. We test this directly using Qwen 2\.5\-72B, the same model used throughout Sections[6\.2](https://arxiv.org/html/2610.26964#S6.SS2)–[6\.3](https://arxiv.org/html/2610.26964#S6.SS3)\.

#### Protocol\.

We construct a support block of 20 labeled examples drawn from the three source domains \(Depot, Rovers, Satellite\), each rendered as its problem PDDL together with its BFS\-optimal plan length, identical in content to the support set ARC conditions on at inference time\. We evaluate two elicitation strategies\. In the*absolute scoring*variant, the model is shown the support block followed by a query instance from a held\-out domain and asked to output a single integer difficulty score from 0 \(trivially easy\) to 100 \(very hard\); we compute Spearman correlation between these scores andn⋆n^\{\\star\}over 60 sampled query instances per domain\. In the*pairwise comparison*variant, the model is instead shown two query instances at a time and asked which requires the longer plan; we sample 150 random pairs per domain over 120 sampled instances and convert the resulting pairwise judgments into a per\-instance score via win rate \(the fraction of comparisons in which an instance is judged harder\), then compute the same Spearman correlation againstn⋆n^\{\\star\}\. Full prompt templates for both variants are provided in Appendix[D](https://arxiv.org/html/2610.26964#A4)\.

MethodBWLOGMBWMeanLLM, absolute scoring \(Qwen 2\.5\-72B\)0\.8450\.9090\.7230\.826LLM, pairwise comparison \(Qwen 2\.5\-72B\)0\.6400\.4440\.4890\.524Delta\-relaxation heuristic \(haddh\_\{\\text\{add\}\}\)0\.8940\.9760\.9230\.931Object cardinality0\.7640\.5440\.6620\.657Goal count0\.7640\.9690\.6730\.802Ridge onxsx\_\{s\}0\.6440\.8890\.5870\.707ARC \(main\)0\.2940\.6520\.2540\.400Table 13:Absolute Spearman correlation for a purely LLM\-based difficulty predictor conditioned on the same 20\-example support set information used by ARC\.N=60N=60query instances per domain for absolute scoring;120120instances per domain,150150random pairs each \(≈2\.5\\approx 2\.5comparisons per instance\), for pairwise comparison\. TheseNNare smaller than Table[1](https://arxiv.org/html/2610.26964#S6.T1)’s full test sets, so this table’s values are not directly comparable to that table’s at the level of individual decimal places\.
#### Results\.

The absolute\-scoring variant is the second\-strongest method in this entire paper afterhaddh\_\{\\text\{add\}\}: mean\|ρ\|=0\.826\|\\rho\|=0\.826, ahead of goal count \(0\.8020\.802\), ridge regression onxsx\_\{s\}\(0\.7070\.707\), and ARC \(0\.4000\.400\) by a wide margin, and within0\.1050\.105ofhaddh\_\{\\text\{add\}\}itself\. This is a genuinely useful result in its own right, distinct from the paper’s ARC\-specific finding: in\-context reasoning over raw PDDL text, given only 20 labeled examples and no training, estimates plan\-length difficulty nearly as well as the best training\-free heuristic we tested, and substantially better than every structural statistic excepthaddh\_\{\\text\{add\}\}\. Pairwise comparison is markedly weaker \(0\.5240\.524\) despite the common intuition that relative judgments are more reliable for LLMs than absolute ones; with only≈2\.5\\approx 2\.5comparisons per instance on average, the win\-rate aggregation is a noisy estimate of the underlying ranking, and we would expect this variant to improve with substantially more pairs per instance, though we did not run additional pairs due to compute cost\. Both variants are weakest on Mystery\-Blocksworld \(\|ρ\|=0\.723\|\\rho\|=0\.723and0\.4890\.489, respectively\), mirroring ARC’s own within\-size difficulty on this domain; one plausible explanation is that the LLM must parse the same scrambled predicate names studied in Section[6\.2](https://arxiv.org/html/2610.26964#S6.SS2)in order to reason about query difficulty, though we did not run the progressive\-scrambling intervention on this baseline specifically to confirm it\. Both methods perform best on Logistics, consistent with Logistics difficulty being comparatively easy to recover from coarse size cues \(Appendix[B\.4](https://arxiv.org/html/2610.26964#A2.SS4)\)\.

We conclude that in\-context reasoning over raw PDDL text, given the identical conditioning information as ARC’s support set, substantially exceeds the trivial object\-cardinality baseline and approaches the strongest training\-free heuristic we tested, while ARC’s learned representation does not\. This supports the claim that ARC’s shortfall is specific to its architecture and training procedure, rather than to the conditioning information being insufficient: the same information, used in\-context by a sufficiently capable LLM, is close to the best signal available in this paper\.

## Appendix CEvidence for the ARC Design

This appendix evaluates the design choices underlying ARC\. We first test whether semantic and structural representations provide different predictive signals and whether naive feature fusion is sufficient\. We then isolate the direction of the asymmetric attention\. Finally, we examine robustness to the sentence encoder and residualisation hyperparameters\. These analyses are intended to test, not assume, a division of labour between the representations\.

### C\.1Representation\-Family Ablation

ARC combines three representations: structural featuresxsx\_\{s\}, foundation\-model embeddingsxex\_\{e\}, and residual semantic featuresxrx\_\{r\}\. To assess the information available in the two primary feature families before introducing ARC’s episodic attention mechanism, we train non\-episodic Ridge regressors usingxsx\_\{s\},xex\_\{e\}, and their direct concatenationxs\|xex\_\{s\}\\\|x\_\{e\}\.

Table 14:Absolute Spearman correlation with optimal plan length for non\-episodic Ridge regressors using structural features, semantic embeddings, or their direct concatenation \(fixedα=1\\alpha=1, computed independently of the Table[1](https://arxiv.org/html/2610.26964#S6.T1)LogME row though numerically close to it, since both are ridge fits onxex\_\{e\}\)\. ARC uses the same feature families within an episodically trained asymmetric architecture; its row is the five\-seed mean from Table[1](https://arxiv.org/html/2610.26964#S6.T1)\.Table[14](https://arxiv.org/html/2610.26964#A3.T14)separates what the two feature families contribute on their own, and the result is unfavorable to ARC’s design premise\. The semantic embeddingxex\_\{e\}alone is markedly weaker than the structural features alone \(0\.4120\.412vs\.0\.7070\.707\), confirming thatxex\_\{e\}is the weaker of the two representations on this task\. Concatenating the two \(0\.6890\.689\) very nearly recoversxsx\_\{s\}alone and does not exceed it; naive concatenation does not help a linear model, though it does help Random Forest \(Appendix[B\.3](https://arxiv.org/html/2610.26964#A2.SS3):0\.388→0\.5740\.388\\to 0\.574\), suggesting the information inxex\_\{e\}is there to be exploited by a sufficiently flexible non\-episodic learner, just not by ridge regression or by ARC\. ARC’s asymmetric retrieval architecture, built specifically to combine these two representations in a way that was intended to exceed naive concatenation, instead falls well below*every*row in this table, includingxex\_\{e\}alone\. This is the clearest evidence in the paper that ARC’s shortfall is not merely a matter of degree: the architecture underperforms the weakest of its own two input representations, scored individually with no learning beyond a linear fit\. The following ablation examines ARC’s attention mechanism directly to see whether this is attributable to a specific design choice\.

### C\.2Attention Directionality

ARC uses semantic embeddings to form queries and structural representations to form keys\. We compare this configuration with symmetric semantic attention, the reversed query–key assignment, and a variant that normalises the structural keys\. To isolate attention structure from training duration, all variants in Table[15](https://arxiv.org/html/2610.26964#A3.T15)use the same matched training budget and the same loss, with five seeds each\.

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\)\\cos\(h\)is the mean within\-domain cosine similarity of the learned representation, andrankeff⁡\(h\)\\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/semantic0\.352/0\.416/0\.3390\.352/0\.416/0\.339; structural/semantic0\.296/0\.492/0\.2930\.296/0\.492/0\.293; semantic/normalised\-structural0\.288/0\.520/0\.2850\.288/0\.520/0\.285; ARC’s own configuration0\.221/0\.812/0\.2030\.221/0\.812/0\.203\(BW/LOG/MBW\)\.ARC’s own query–key assignment \(semantic query, structural key\) attains the highest mean among the four variants tested \(0\.4120\.412\), ahead of the next best, symmetric semantic attention, by0\.0430\.043\. This is a genuine, if modest, internal validation of the design choice: given that ARC must use*some*assignment ofxex\_\{e\}andxsx\_\{s\}to query and key, the one it uses is the best of the four tested\. It is also, however, not a validation of the architecture as a whole — every one of these four variants, including the best, is far below ridge regression onxsx\_\{s\}alone \(0\.7070\.707\) andhaddh\_\{\\text\{add\}\}\(0\.9310\.931\) from Table[1](https://arxiv.org/html/2610.26964#S6.T1), so the directionality choice determines which of several weak configurations ARC lands on, not whether ARC is competitive with the non\-episodic baselines\. We also note a methodological caveat: this ablation uses a separate training loop \(matched to, but not identical to, the loop producing Table[1](https://arxiv.org/html/2610.26964#S6.T1)’s ARC rows\) so that all four variants share exactly the same code path; its ARC\-configuration mean \(0\.4120\.412\) is close to but not identical with Table[1](https://arxiv.org/html/2610.26964#S6.T1)’s main\-configuration mean \(0\.4000\.400\), and the small residual difference should be attributed to this implementation difference rather than to any additional design choice\. We avoid interpreting the attention weights themselves as proof that the model retrieves genuine structural analogues; the experiment establishes only a predictive difference between assignments of representation roles, all of them weak in absolute terms\.

### C\.3Encoder Robustness

The representation diagnostic motivating ARC should not depend on one sentence encoder\. We generate the same natural\-language instance descriptions and encode them with three pretrained sentence\-transformer models\. Table[16](https://arxiv.org/html/2610.26964#A3.T16)reports mean pairwise cosine similarity within each held\-out domain and the effective rank of the resulting embedding matrices\.

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\.All three encoders produce extremely high within\-domain cosine similarity \(0\.9860\.986–0\.9920\.992\) and a very low effective rank \(2\.612\.61–2\.642\.64\), essentially indistinguishable across encoders despite their different training data and parameter counts\. This confirms the collapse diagnostic in Section[3](https://arxiv.org/html/2610.26964#S3.SS0.SSS0.Px4)is a property of this family of sentence encoders on these descriptions, not an artifact of one model’s training\. High cosine similarity does not imply that semantic embeddings contain no predictive information; the semantic\-only Ridge model in Table[14](https://arxiv.org/html/2610.26964#A3.T14)achieves a non\-trivial correlation \(0\.4120\.412\) despite this collapse\. The result instead shows that several standard sentence encoders exhibit a shared geometric concentration on this input distribution, motivating an architecture that does not rely on semantic embeddings alone for fine\-grained discrimination — though, as Section[6\.1](https://arxiv.org/html/2610.26964#S6.SS1)and Appendix[C\.1](https://arxiv.org/html/2610.26964#A3.SS1)show, ARC’s own attempt at such an architecture did not succeed on this problem\. All three encoders tested belong to the same Sentence\-BERT\-style bi\-encoder family; whether instruction\-tuned or substantially larger embedding models exhibit the same collapse is left to future work\.

### C\.4Residualisation Sensitivity

ARC defines the residual semantic feature as

xr=xe−x^e​\(xs\),x\_\{r\}=x\_\{e\}\-\\widehat\{x\}\_\{e\}\(x\_\{s\}\),wherex^e​\(xs\)\\widehat\{x\}\_\{e\}\(x\_\{s\}\)is estimated by applying PCA toxex\_\{e\}and fitting Ridge regression from the structural representation\. The default configuration uses PCA dimension2020and Ridge coefficientα=1\.0\\alpha=1\.0\. Table[17](https://arxiv.org/html/2610.26964#A3.T17)varies each choice while holding the other fixed\.

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](https://arxiv.org/html/2610.26964#A3.T15); see that table’s note on its relationship to Table[1](https://arxiv.org/html/2610.26964#S6.T1)’s main configuration\.The PCA dimension sweep is mildly favorable to smaller values \(dPCA=5d\_\{\\mathrm\{PCA\}\}=5:0\.532±0\.1090\.532\\pm 0\.109, against0\.412±0\.0830\.412\\pm 0\.083at the default2020\), but with substantial seed variance at every setting\. The Ridge\-coefficient sweep contains a result we did not anticipate and have not validated:α=100\\alpha=100reaches0\.753±0\.0170\.753\\pm 0\.017, exceeding every other setting in this sweep, exceeding ridge regression onxsx\_\{s\}alone \(0\.7070\.707\), and with far lower seed variance than the default \(0\.0170\.017vs\.0\.0830\.083\)\. We report this plainly rather than adopt it, for a reason central to this paper’s methodology: this sweep was run on the held\-out test domains themselves, so selectingα=100\\alpha=100post hoc and reporting it as “ARC’s real performance” would be exactly the kind of test\-set tuning the rest of this paper’s protocol was designed to avoid\. Before this setting could be credited as a genuine improvement, it would need to be chosen on the dev/validation split alone and then confirmed, once, on the held\-out test domains — a check we have not yet performed\. We flag it as a specific, concrete direction for follow\-up work rather than folding it into our reported results\. All PCA bases and Ridge coefficients are fitted using pooled source\-domain instances and frozen before evaluation; the sensitivity analysis therefore changes preprocessing hyperparameters but does not introduce target\-domain*fitting*\(only, in this one instance, post hoc hyperparameter selection, which we explicitly do not do for our reported numbers\)\.

## Appendix DPrompts Used in LLM Evaluation

All LLM evaluations use temperature00and maximum2,0482\{,\}048output tokens\. Prompts follow the chain\-of\-thought PDDL formatting of\[[17](https://arxiv.org/html/2610.26964#bib.bib27)\]\. No domain\-specific demonstrations are provided in the zero\-shot setting\. Brackets\[PLACEHOLDER\]denote fields filled at runtime\.

### D\.1Prompt 1: PDDL Plan Generation \(Main Evaluation\)

Used to evaluate LLM planning validity on all three test domains \(Blocksworld, Logistics, Mystery\-Blocksworld\) for Table[3](https://arxiv.org/html/2610.26964#S6.T3)and Table[4](https://arxiv.org/html/2610.26964#S6.T4)\. The domain file contains the full PDDL domain description; the problem file contains the specific instance\. This is the canonical copy of the prompt; Appendix[A\.2](https://arxiv.org/html/2610.26964#A1.SS2)refers back to it rather than reproducing it a second time\.

Prompt 1 – PDDL Plan Generation[⬇](data:text/plain;base64,WW91IGFyZSBhbiBleHBlcnQgQUkgcGxhbm5pbmcKYXNzaXN0YW50LiBZb3VyIHRhc2sgaXMgdG8gc29sdmUKYSBjbGFzc2ljYWwgcGxhbm5pbmcgcHJvYmxlbQpzcGVjaWZpZWQgaW4gUERETCAoUGxhbm5pbmcKRG9tYWluIERlZmluaXRpb24gTGFuZ3VhZ2UpLgoKSSB3aWxsIHByb3ZpZGUgeW91IHdpdGg6CjEuIEEgUERETCBkb21haW4gZmlsZQpkZXNjcmliaW5nIHRoZSBwbGFubmluZyBkb21haW4KMi4gQSBQRERMIHByb2JsZW0gZmlsZQpkZXNjcmliaW5nIHRoZSBzcGVjaWZpYyBwcm9ibGVtCnRvIHNvbHZlCgpZb3VyIGdvYWwgaXMgdG8gZmluZCBhIHZhbGlkCnBsYW4gLS0gYSBzZXF1ZW5jZSBvZiBhY3Rpb25zCnRoYXQgdHJhbnNmb3JtcyB0aGUgaW5pdGlhbCBzdGF0ZQppbnRvIGEgc3RhdGUgc2F0aXNmeWluZyB0aGUgZ29hbC4KCklNUE9SVEFOVCBJTlNUUlVDVElPTlM6Ci0gVGhpbmsgc3RlcCBieSBzdGVwIGFib3V0IHRoZQpjdXJyZW50IHN0YXRlIGFuZCB3aGF0IGFjdGlvbnMKICBhcmUgYXBwbGljYWJsZS4KLSBFYWNoIGFjdGlvbiBpbiB5b3VyIHBsYW4gbXVzdApiZSBhcHBsaWNhYmxlIGluIHRoZSBzdGF0ZQogIHJlc3VsdGluZyBmcm9tIGFsbCBwcmV2aW91cyBhY3Rpb25zLgotIE91dHB1dCBPTkxZIHRoZSBmaW5hbCBwbGFuLApvbmUgYWN0aW9uIHBlciBsaW5lLCBpbiB0aGUgZm9ybWF0OgogIChhY3Rpb24tbmFtZSBwYXJhbTEgcGFyYW0yIC4uLikKLSBEbyBOT1QgaW5jbHVkZSBhbnkgZXhwbGFuYXRpb24KYWZ0ZXIgdGhlIHBsYW4uCi0gSWYgdGhlIHByb2JsZW0gaXMgdW5zb2x2YWJsZSwKb3V0cHV0IGV4YWN0bHk6IE5PX1BMQU4KCj09PSBET01BSU4gPT09CltET01BSU5fUERETF0KCj09PSBQUk9CTEVNID09PQpbUFJPQkxFTV9QRERMXQoKTm93IHNvbHZlIHRoZSBwcm9ibGVtLiBUaGluawp0aHJvdWdoIHRoZSBzdGF0ZSBjaGFuZ2VzIGNhcmVmdWxseSwKdGhlbiBvdXRwdXQgdGhlIHBsYW46)YouareanexpertAIplanningassistant\.YourtaskistosolveaclassicalplanningproblemspecifiedinPDDL\(PlanningDomainDefinitionLanguage\)\.Iwillprovideyouwith:1\.APDDLdomainfiledescribingtheplanningdomain2\.APDDLproblemfiledescribingthespecificproblemtosolveYourgoalistofindavalidplan–asequenceofactionsthattransformstheinitialstateintoastatesatisfyingthegoal\.IMPORTANTINSTRUCTIONS:\-Thinkstepbystepaboutthecurrentstateandwhatactionsareapplicable\.\-Eachactioninyourplanmustbeapplicableinthestateresultingfromallpreviousactions\.\-OutputONLYthefinalplan,oneactionperline,intheformat:\(action\-nameparam1param2…\)\-DoNOTincludeanyexplanationaftertheplan\.\-Iftheproblemisunsolvable,outputexactly:NO\_PLAN===DOMAIN===\[DOMAIN\_PDDL\]===PROBLEM===\[PROBLEM\_PDDL\]Nowsolvetheproblem\.Thinkthroughthestatechangescarefully,thenoutputtheplan:

Validity checking\.Generated plans are verified by a custom PDDL state\-space executor that: \(1\) parses action syntax; \(2\) checks each action’s preconditions against the current state; \(3\) verifies the goal holds in the final state\. A plan is valid only if all three checks pass\.

### Prompt 2: Mystery\-Blocksworld Evaluation

Mystery\-Blocksworld instances use the same prompt as Prompt 1, but the domain file has all predicate and action names replaced by semantically uninformative symbols \(e\.g\.,on→\\topred7,stack→\\toact3\)\. No additional instructions are given about the scrambling\. This tests whether LLMs can ground their world model from PDDL structure alone, without semantic cues\.

Prompt 2 – Mystery\-Blocksworld \(scrambled predicates\)[⬇](data:text/plain;base64,WW91IGFyZSBhbiBleHBlcnQgQUkgcGxhbm5pbmcKYXNzaXN0YW50LiBZb3VyIHRhc2sgaXMgdG8gc29sdmUKYSBjbGFzc2ljYWwgcGxhbm5pbmcgcHJvYmxlbQpzcGVjaWZpZWQgaW4gUERETCAoUGxhbm5pbmcKRG9tYWluIERlZmluaXRpb24gTGFuZ3VhZ2UpLgoKSSB3aWxsIHByb3ZpZGUgeW91IHdpdGg6CjEuIEEgUERETCBkb21haW4gZmlsZQpkZXNjcmliaW5nIHRoZSBwbGFubmluZyBkb21haW4KMi4gQSBQRERMIHByb2JsZW0gZmlsZQpkZXNjcmliaW5nIHRoZSBzcGVjaWZpYyBwcm9ibGVtCnRvIHNvbHZlCgpZb3VyIGdvYWwgaXMgdG8gZmluZCBhIHZhbGlkCnBsYW4sIGEgc2VxdWVuY2Ugb2YgYWN0aW9ucwp0aGF0IHRyYW5zZm9ybXMgdGhlIGluaXRpYWwKc3RhdGUgaW50byBhIHN0YXRlIHNhdGlzZnlpbmcKdGhlIGdvYWwuCgpJTVBPUlRBTlQgSU5TVFJVQ1RJT05TOgotIFRoaW5rIHN0ZXAgYnkgc3RlcCBhYm91dCB0aGUKY3VycmVudCBzdGF0ZSBhbmQgd2hhdCBhY3Rpb25zCiAgYXJlIGFwcGxpY2FibGUuCi0gRWFjaCBhY3Rpb24gaW4geW91ciBwbGFuIG11c3QKYmUgYXBwbGljYWJsZSBpbiB0aGUgc3RhdGUKICByZXN1bHRpbmcgZnJvbSBhbGwgcHJldmlvdXMKICBhY3Rpb25zLgotIE91dHB1dCBPTkxZIHRoZSBmaW5hbCBwbGFuLApvbmUgYWN0aW9uIHBlciBsaW5lLCBpbiB0aGUKZm9ybWF0OiAoYWN0aW9uLW5hbWUgcGFyYW0xCnBhcmFtMiAuLi4pCi0gRG8gTk9UIGluY2x1ZGUgYW55IGV4cGxhbmF0aW9uCmFmdGVyIHRoZSBwbGFuLgotIElmIHRoZSBwcm9ibGVtIGlzIHVuc29sdmFibGUsCm91dHB1dCBleGFjdGx5OiBOT19QTEFOCgo9PT0gRE9NQUlOID09PQo7OyBCbG9ja3MgcGxhbm5pbmcgZG9tYWluCihkZWZpbmUgKGRvbWFpbiBteXN0ZXJ5LWJsb2NrcykKICAoOnJlcXVpcmVtZW50cyA6c3RyaXBzIDp0eXBpbmcpCiAgKDp0eXBlcyBvYmplY3QgLSBvYmplY3QpCiAgKDpwcmVkaWNhdGVzCiAgICAocHJlZDEgP3ggLSBvYmplY3QpCiAgICAocHJlZDIgP3ggLSBvYmplY3QpCiAgICAocHJlZDMgP3ggLSBvYmplY3QpCiAgICAocHJlZDUpCiAgICAocHJlZDcgP3ggLSBvYmplY3QgP3kgLSBvYmplY3QpKQoKICAoOmFjdGlvbiBhY3QxCiAgICA6cGFyYW1ldGVycyAoP3ggLSBvYmplY3QpCiAgICA6cHJlY29uZGl0aW9uIChhbmQgKHByZWQzID94KQogICAgKHByZWQxID94KSAocHJlZDUpKQogICAgOmVmZmVjdCAoYW5kIChwcmVkMiA/eCkKICAgIChub3QgKHByZWQzID94KSkgKG5vdCAocHJlZDEgP3gpKQogICAgKG5vdCAocHJlZDUpKSkpCiAgLi4uCiAgW3JlbWFpbmluZyBzY3JhbWJsZWQgYWN0aW9uc10KKQoKPT09IFBST0JMRU0gPT09CltTQ1JBTUJMRURfUFJPQkxFTV9QRERMXQoKTm93IHNvbHZlIHRoZSBwcm9ibGVtLiBUaGluawp0aHJvdWdoIHRoZSBzdGF0ZSBjaGFuZ2VzCmNhcmVmdWxseSwgdGhlbiBvdXRwdXQgdGhlIHBsYW46)YouareanexpertAIplanningassistant\.YourtaskistosolveaclassicalplanningproblemspecifiedinPDDL\(PlanningDomainDefinitionLanguage\)\.Iwillprovideyouwith:1\.APDDLdomainfiledescribingtheplanningdomain2\.APDDLproblemfiledescribingthespecificproblemtosolveYourgoalistofindavalidplan,asequenceofactionsthattransformstheinitialstateintoastatesatisfyingthegoal\.IMPORTANTINSTRUCTIONS:\-Thinkstepbystepaboutthecurrentstateandwhatactionsareapplicable\.\-Eachactioninyourplanmustbeapplicableinthestateresultingfromallpreviousactions\.\-OutputONLYthefinalplan,oneactionperline,intheformat:\(action\-nameparam1param2…\)\-DoNOTincludeanyexplanationaftertheplan\.\-Iftheproblemisunsolvable,outputexactly:NO\_PLAN===DOMAIN===;;Blocksplanningdomain\(define\(domainmystery\-blocks\)\(:requirements:strips:typing\)\(:typesobject\-object\)\(:predicates\(pred1?x\-object\)\(pred2?x\-object\)\(pred3?x\-object\)\(pred5\)\(pred7?x\-object?y\-object\)\)\(:actionact1:parameters\(?x\-object\):precondition\(and\(pred3?x\)\(pred1?x\)\(pred5\)\):effect\(and\(pred2?x\)\(not\(pred3?x\)\)\(not\(pred1?x\)\)\(not\(pred5\)\)\)\)…\[remainingscrambledactions\]\)===PROBLEM===\[SCRAMBLED\_PROBLEM\_PDDL\]Nowsolvetheproblem\.Thinkthroughthestatechangescarefully,thenoutputtheplan:

### Prompt 3: LLM\-Based Difficulty Prediction \(Absolute Scoring\)

Used for the LLM\-only difficulty baseline in Appendix[B\.7](https://arxiv.org/html/2610.26964#A2.SS7)\. The support block contains 20 labeled source\-domain examples \(problem PDDL and optimal plan length\);\[SUPPORT\_BLOCK\]is substituted with this rendered block,\[QUERY\_DOMAIN\_PDDL\]with the query instance’s domain file, and\[QUERY\_PROBLEM\_PDDL\]with the query instance’s problem file\.

Prompt 3 – LLM Difficulty Prediction \(absolute scoring\)[⬇](data:text/plain;base64,WW91IGFyZSBhbiBleHBlcnQgYXQgYW5hbHl6aW5nClBEREwgcGxhbm5pbmcgcHJvYmxlbXMuIEJlbG93CmFyZSBsYWJlbGVkIGV4YW1wbGVzIGZyb20KUkVMQVRFRCBwbGFubmluZyBkb21haW5zLCBlYWNoCnNob3dpbmcgYSBwcm9ibGVtIGFuZCBpdHMKb3B0aW1hbCAoc2hvcnRlc3QpIHBsYW4gbGVuZ3RoLgpUaGUgcXVlcnkgcHJvYmxlbSBpcyBmcm9tIGEKRElGRkVSRU5UIGRvbWFpbiB3aXRoIGRpZmZlcmVudApwcmVkaWNhdGVzIGFuZCBhY3Rpb25zLCBidXQKc2ltaWxhciBzdHJ1Y3R1cmFsIHByaW5jaXBsZXMKKG9iamVjdCBjb3VudHMsIGdvYWwgY29tcGxleGl0eSwKaW5pdGlhbCBzdGF0ZSBzdHJ1Y3R1cmUpIG1heQp0cmFuc2Zlci4KCj09PSBMQUJFTEVEIEVYQU1QTEVTCihmcm9tIG90aGVyIGRvbWFpbnMpID09PQpbU1VQUE9SVF9CTE9DS10KCj09PSBRVUVSWSBET01BSU4gPT09CltRVUVSWV9ET01BSU5fUERETF0KCj09PSBRVUVSWSBQUk9CTEVNCihwcmVkaWN0IGRpZmZpY3VsdHkgZm9yCnRoaXMgb25lKSA9PT0KW1FVRVJZX1BST0JMRU1fUERETF0KCkJhc2VkIG9uIHRoZSBwYXR0ZXJuIGluIHRoZQpsYWJlbGVkIGV4YW1wbGVzIChob3cgcHJvYmxlbQpzdHJ1Y3R1cmUgcmVsYXRlcyB0byBwbGFuCmxlbmd0aCksIGVzdGltYXRlIGEgRElGRklDVUxUWQpTQ09SRSBmb3IgdGhlIHF1ZXJ5IHByb2JsZW0sCmZyb20gMCAodHJpdmlhbGx5IGVhc3ksIHZlcnkKc2hvcnQgcGxhbikgdG8gMTAwICh2ZXJ5IGhhcmQsCnZlcnkgbG9uZyBwbGFuKS4KT3V0cHV0IE9OTFkgYSBzaW5nbGUgaW50ZWdlcgpiZXR3ZWVuIDAgYW5kIDEwMC4gTm8gZXhwbGFuYXRpb24uClNjb3JlOg==)YouareanexpertatanalyzingPDDLplanningproblems\.BelowarelabeledexamplesfromRELATEDplanningdomains,eachshowingaproblemanditsoptimal\(shortest\)planlength\.ThequeryproblemisfromaDIFFERENTdomainwithdifferentpredicatesandactions,butsimilarstructuralprinciples\(objectcounts,goalcomplexity,initialstatestructure\)maytransfer\.===LABELEDEXAMPLES\(fromotherdomains\)===\[SUPPORT\_BLOCK\]===QUERYDOMAIN===\[QUERY\_DOMAIN\_PDDL\]===QUERYPROBLEM\(predictdifficultyforthisone\)===\[QUERY\_PROBLEM\_PDDL\]Basedonthepatterninthelabeledexamples\(howproblemstructurerelatestoplanlength\),estimateaDIFFICULTYSCOREforthequeryproblem,from0\(triviallyeasy,veryshortplan\)to100\(veryhard,verylongplan\)\.OutputONLYasingleintegerbetween0and100\.Noexplanation\.Score:

### Prompt 4: LLM\-Based Difficulty Prediction \(Pairwise Comparison\)

Used for the pairwise\-comparison variant of the LLM\-only baseline in Appendix[B\.7](https://arxiv.org/html/2610.26964#A2.SS7)\.\[PROBLEM\_A\]and\[PROBLEM\_B\]are two randomly sampled query instances from the same held\-out domain\.

Prompt 4 – LLM Difficulty Prediction \(pairwise comparison\)[⬇](data:text/plain;base64,WW91IGFyZSBhbiBleHBlcnQgYXQgYW5hbHl6aW5nClBEREwgcGxhbm5pbmcgcHJvYmxlbXMuIEJlbG93CmFyZSBsYWJlbGVkIGV4YW1wbGVzIGZyb20KUkVMQVRFRCBwbGFubmluZyBkb21haW5zLCBlYWNoCnNob3dpbmcgYSBwcm9ibGVtIGFuZCBpdHMKb3B0aW1hbCAoc2hvcnRlc3QpIHBsYW4gbGVuZ3RoLgoKPT09IExBQkVMRUQgRVhBTVBMRVMKKGZyb20gb3RoZXIgZG9tYWlucykgPT09CltTVVBQT1JUX0JMT0NLXQoKPT09IFFVRVJZIERPTUFJTiA9PT0KW1FVRVJZX0RPTUFJTl9QRERMXQoKPT09IFBST0JMRU0gQSA9PT0KW1BST0JMRU1fQV0KCj09PSBQUk9CTEVNIEIgPT09CltQUk9CTEVNX0JdCgpXaGljaCBwcm9ibGVtIHJlcXVpcmVzIGEKTE9OR0VSIG9wdGltYWwgcGxhbiAoaXMKaGFyZGVyKT8gT3V0cHV0IE9OTFkgJ0EnCm9yICdCJy4gTm8gZXhwbGFuYXRpb24uCkFuc3dlcjo=)YouareanexpertatanalyzingPDDLplanningproblems\.BelowarelabeledexamplesfromRELATEDplanningdomains,eachshowingaproblemanditsoptimal\(shortest\)planlength\.===LABELEDEXAMPLES\(fromotherdomains\)===\[SUPPORT\_BLOCK\]===QUERYDOMAIN===\[QUERY\_DOMAIN\_PDDL\]===PROBLEMA===\[PROBLEM\_A\]===PROBLEMB===\[PROBLEM\_B\]WhichproblemrequiresaLONGERoptimalplan\(isharder\)?OutputONLY’A’or’B’\.Noexplanation\.Answer:

### D\.2Summary

The prompts comparison summary is discussed in table[18](https://arxiv.org/html/2610.26964#A4.T18)\.

Table 18:Summary of prompts used across experiments\.

## Appendix ECustom Non\-IPC Planning Domains

### E\.1Introduction

To evaluate ARC on domains completely outside the IPC benchmark suite, we construct three custom STRIPS planning domains from scratch:Rescue Mission,Robot Arm Stacking, andLibrary Books\. These domains are designed to satisfy three criteria: \(1\) pure STRIPS compatibility \(no action costs, numeric fluents, or conditional effects\) to enable BFS\-based difficulty labeling with pyperplan; \(2\) multi\-dimensional difficulty structure, where optimal plan length is governed by at least two interacting structural factors rather than object count alone; and \(3\) no overlap with any IPC 2002–2023 competition domain in terms of predicate vocabulary, action structure, or generator seed\.

Each domain is paired with a randomized instance generator that produces problems across a controlled range of structural complexity parameters\. Difficulty labels \(optimal plan lengthn∗n^\{\*\}\) are obtained by BFS with the same budget used in the main evaluation \(Tmax=12T\_\{\\text\{max\}\}\{=\}12,Nmax=5,000N\_\{\\text\{max\}\}\{=\}5\{,\}000\)\. The domains are used exclusively for zero\-shot evaluation; no instances from these domains appear in ARC’s training or validation set\.

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;NNis the number of BFS\-solved,n⋆\>0n^\{\\star\}\>0instances\)\. ARC uses five seeds, mean±\\pmstd, with the prediction\-level ensemble in parentheses\.Table[19](https://arxiv.org/html/2610.26964#A5.T19)shows the same pattern observed throughout this paper, generalizing to domains entirely outside both ARC’s training distribution and its architecture\-design loop \(these three domains were never used to tune any method\)\. Goal count is the strongest zero\-shot statistic on all three, including Library Books \(0\.8560\.856\) where it is substantially ahead of Ridge onxsx\_\{s\}\(0\.6930\.693\)\. ARC is competitive only on Library Books \(0\.6790\.679, close to Ridge’s0\.6930\.693\) and is clearly the weakest method on Rescue Mission \(0\.0990\.099, against0\.2240\.224–0\.8050\.805for the alternatives\) and on Robot Arm, where it is close to but below Ridge and goal count\. We do not have a generator\-identified reason why Library Books is the one domain where ARC is competitive; one candidate explanation is that Library Books’ very small sample size \(N=35N=35\) gives its correlation estimate high variance in either direction, but we note this as a candidate, not a finding, since we did not design a test to distinguish it from a genuine difference in domain structure\.

Example: A Rescue Mission planning instanceConsider one agent, two rooms connected by a corridor, one supply item located in the second room, and one victim in the second room requiring that supply\.[⬇](data:text/plain;base64,KDpvYmplY3RzIGFnZW50MSByb29tMSByb29tMiBzdXBwbHkxIHZpY3RpbTEpCig6aW5pdCAoYXQgYWdlbnQxIHJvb20xKSAoY29ubmVjdGVkIHJvb20xIHJvb20yKQogICAgICAgKGNvbm5lY3RlZCByb29tMiByb29tMSkgKGF0IHN1cHBseTEgcm9vbTIpCiAgICAgICAoYXQgdmljdGltMSByb29tMikgKG5lZWRzIHZpY3RpbTEgc3VwcGx5MSkpCig6Z29hbCAocmVzY3VlZCB2aWN0aW0xKSk=)\(:objectsagent1room1room2supply1victim1\)\(:init\(atagent1room1\)\(connectedroom1room2\)\(connectedroom2room1\)\(atsupply1room2\)\(atvictim1room2\)\(needsvictim1supply1\)\)\(:goal\(rescuedvictim1\)\)The agent must move to room2, pick up the supply, and rescue the victim:move​\(room1,room2\)\\text\{move\}\(\\text\{room1\},\\text\{room2\}\),pick\-supply​\(supply1\)\\text\{pick\-supply\}\(\\text\{supply1\}\),rescue\-victim​\(victim1,supply1\)\\text\{rescue\-victim\}\(\\text\{victim1\},\\text\{supply1\}\), givingn⋆​\(π\)=3n^\{\\star\}\(\\pi\)=3\. Unlike the Blocksworld example in Section[3](https://arxiv.org/html/2610.26964#S3), difficulty here depends jointly on the agent’s distance to the needed supply*and*on which victims require which supplies—the two\-factor structure referenced in criterion \(2\) above, which does not reduce to a single scalar such as room count or victim count\.

### E\.2Dataset Generation

All three domains are specified in typed STRIPS PDDL and generated programmatically by Python scripts that vary structural parameters across a fixed random seed range\. The generation process does not use any language model or neural network; all PDDL domain and problem files are produced by deterministic rule\-based generators\.

#### Rescue Mission\.

The Rescue Mission domain models an emergency response scenario in which one or more agents navigate a graph of rooms, collect typed supplies, and rescue victims that each require a specific supply type\. Room connectivity is generated as a random sparse graph \(chain backbone plus random extra edges\), ensuring reachability\. Structural parameters: number of victims \(nv∈\[2,12\]n\_\{v\}\\in\[2,12\]\), number of rooms \(nr=nv\+1n\_\{r\}=n\_\{v\}\+1\), number of agents \(na=⌈nv/3⌉n\_\{a\}=\\lceil n\_\{v\}/3\\rceil\), number of supply types \(ns=nvn\_\{s\}=n\_\{v\}\)\. Goals specify a random subset of victims to rescue\. Difficulty is jointly governed by agent–supply co\-location distance \(navigation steps to reach supplies\) and victim distribution across rooms, making it multi\-dimensional\. The domain has 3 actions \(move,pick\-supply,rescue\-victim\), 8 predicates, and 4 typed object classes\. A total of 127 BFS\-solvable instances were generated \(from 200 attempts\)\.

#### Robot Arm Stacking\.

The Robot Arm domain models a tabletop manipulation task in which a single\-gripper robot arm picks and places blocks across multiple tables, achieving a specified stacking configuration\. Initial states are randomized: blocks are distributed across tables, and a random subset are pre\-stacked \(the robot must partially disassemble before re\-assembling\)\. Structural parameters: number of blocks \(nb∈\[3,12\]n\_\{b\}\\in\[3,12\]\), number of tables \(nt=⌊nb/3⌋\+1n\_\{t\}=\\lfloor n\_\{b\}/3\\rfloor\+1, minimum 2\), number of initial stacks \(random in\[0,⌊nb/3⌋\]\[0,\\lfloor n\_\{b\}/3\\rfloor\]\), goal configuration \(random stacking of22–nbn\_\{b\}blocks on one table\)\. The domain has 4 actions \(pick\-from\-table,pick\-from\-block,place\-on\-table,stack\), 7 predicates, and 2 typed object classes\. A total of 95 BFS\-solvable instances were generated \(from 200 attempts\)\.

#### Library Books\.

The Library Books domain models a library reshelving task in which patrons check out books from shelves, books are collected onto a cart, and carts must be moved to the correct shelf before books can be reshelved\. Each book has a designated correct shelf; a book is returned only when it is physically shelved at that location\. Structural parameters: number of books \(nb∈\[2,5\]n\_\{b\}\\in\[2,5\]for solvable instances\), number of shelves \(ns=nbn\_\{s\}=n\_\{b\}, minimum 2\), number of carts \(nc=1n\_\{c\}=1\), number of patrons \(np=⌈nb/2⌉n\_\{p\}=\\lceil n\_\{b\}/2\\rceil\)\. The domain has 4 actions \(checkout\-book,return\-to\-cart,shelve\-book,move\-cart\), 8 predicates, and 4 typed object classes\. A total of 15 BFS\-solvable instances were generated \(from 200 attempts; the low solve rate reflects the compounded constraint that book, cart, and correct shelf must all be aligned simultaneously\)\.

### E\.3Dataset Verification

To verify that our instance generators produce valid, sensible planning problems, three human annotators with graduate\-level AI planning background independently evaluated a random sample of 30 instances per domain \(90 instances total\) on two criteria:

1. 1\.Validity: Is the PDDL problem well\-formed? Does the initial state satisfy all type constraints? Is the goal reachable in principle \(ignoring plan length\)?
2. 2\.Difficulty coherence: Does the optimal plan length obtained by BFS agree with the annotator’s intuitive difficulty ranking? \(Binary: agree / disagree with BFS rank ordering within a pair of instances of the same object count\.\)

Annotators were provided with the domain PDDL, the problem PDDL, and the BFS\-computedn∗n^\{\*\}value\. They were asked to flag any instance where \(1\) the initial state appeared inconsistent, \(2\) the goal was trivially achieved from the initial state \(degenerate\), or \(3\) the BFS plan length seemed implausible given the stated parameters\. Disagreements were resolved by majority vote; no instance required exclusion, confirming generator correctness\.

Table 20:Inter\-annotator agreement metrics across three annotators \(A1, A2, A3\) on 30 sampled instances per domain\. Cohen’sκ\\kappais computed pairwise and averaged\. Jaccard coefficient measures set overlap of flagged instances\. Percent agreement is the fraction of instances all three annotators labeled identically\.As summarized in Table[20](https://arxiv.org/html/2610.26964#A5.T20), all three domains achieve mean pairwise Cohen’sκ\>0\.90\\kappa\>0\.90and percent agreement\>91%\>91\\%, satisfying the standard threshold for strong inter\-annotator reliability\[[33](https://arxiv.org/html/2610.26964#bib.bib2)\]\. No instances were removed following the verification process\. We note that annotators were shown the BFS\-computedn∗n^\{\*\}value alongside each instance for the difficulty\-coherence judgment, which may inflate agreement relative to a fully blinded protocol in which annotators rank instances before seeingn∗n^\{\*\}; the validity checks, which do not depend onn∗n^\{\*\}, are not subject to this concern\.

### Dataset Statistics

Table[21](https://arxiv.org/html/2610.26964#A5.T21)summarizes structural statistics for all generated instances in each domain\.

Table 21:Dataset statistics for the three custom planning domains\.n∗n^\{\*\}= BFS\-optimal plan length \(solved instances only\)\.\|O\|\|O\|= object count\.ninitn\_\{\\text\{init\}\}= initial\-state facts\.ngoaln\_\{\\text\{goal\}\}= goal facts\.\|O\|\|O\|\(objects\)n∗n^\{\*\}\(plan length\)SolveDomainTotalSolvedMinMedianMaxMinMedianMaxBFS%EHC%Rescue Mission20012771843392463\.5%82\.0%Robot Arm2009551431271847\.5%71\.0%Library Books200156101648147\.5%31\.0%BFS%: fraction solved by BFS within budget \(Tmax=12T\_\{\\text\{max\}\}\{=\}12,Nmax=5,000N\_\{\\text\{max\}\}\{=\}5\{,\}000\)\. EHC%: fraction solved when BFS is replaced by EHC\(hFFh^\{\\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\(hFFh^\{\\text\{FF\}\}\) recovers 31% with informed search\.Difficulty variation\.Rescue Mission shows the widest range \(n∗∈\[3,24\]n^\{\*\}\\in\[3,24\]\), driven by the interaction between agent position, supply location, and victim distribution\. Robot Arm difficulty varies with the number and depth of initial stacks\. Library Books difficulty is most sensitive to cart\-shelf distance and the number of correctly\-shelved books initially; because only 15 of 200 attempted instances are BFS\-solvable in this domain, its statistics should be read as a qualitative check rather than a precise quantitative estimate\. The zero\-shot domain\-level correlations for ARC and the structural baselines on all three custom domains are reported in Table[19](https://arxiv.org/html/2610.26964#A5.T19)above; we did not additionally compute within\-size \(fixed\-object\-count\) correlations on these three domains, since their already\-small sample sizes \(N=85N=85,8585,3535\) would leave very few instances per object\-count bucket\.

### Annotation Guidelines

The following guidelines were provided to all three annotators before the verification session\. Annotators completed a 10\-instance calibration set and discussed edge cases before the main annotation began\. All annotation was conducted independently\.

Annotation Guidelines – Custom Planning Domain VerificationTask Overview\.You will evaluate PDDL planning problem instances for correctness and difficulty coherence\. Each instance consists of: \(1\) a domain file \(shared across all instances in a domain\), \(2\) a problem file specifying objects, initial state, and goal, \(3\) the BFS\-computed optimal plan lengthn∗n^\{\*\}\(or “UNSOLVED”\)\.Annotation Dimensions\.1\. Validity\(Binary: Valid / Invalid\)Mark an instance asInvalidif*any*of the following hold:•The initial state contains a fact that violates type constraints \(e\.g\., an object declared as typeblockappears in a predicate that expects typetable\)\.•The goal is already satisfied in the initial state \(degenerate instance,n∗=0n^\{\*\}=0\)\.•The goal refers to objects not declared in:objects\.•Two facts in the initial state logically contradict each other \(e\.g\., a block declared bothclearandonanother block that is itselfclear\)\.Otherwise, mark asValid\. You are*not*asked to verify that the goal is reachable \(BFS handles this\); only that the problem is well\-formed\.2\. Difficulty Coherence\(Binary: Agree / Disagree\)You will be given pairs of instances from the same domain with the*same object count*\(\|O\|\|O\|\) but different BFS plan lengths\. For each pair\(A,B\)\(A,B\)wheren∗​\(A\)<n∗​\(B\)n^\{\*\}\(A\)<n^\{\*\}\(B\), indicate whether you agree thatAAis intuitively easier thanBBbased on the initial and goal states\.MarkAgreeif:•The instance with smallern∗n^\{\*\}has a goal that appears “closer” to the initial state \(fewer rearrangements needed, shorter chains of dependencies\)\.•The structural explanation is apparent: e\.g\., in Rescue Mission, ifn∗​\(A\)<n∗​\(B\)n^\{\*\}\(A\)<n^\{\*\}\(B\)because agent and supply are in the same room inAAbut not inBB, this is coherent\.MarkDisagreeif:•The BFS plan length ranking contradicts your inspection of the initial and goal states\.•The pair appears to have been generated incorrectly \(e\.g\.,n∗​\(B\)n^\{\*\}\(B\)is lower than expected given visibly more complex initial state\)\.Important: Do not flag a pair as Disagree simply because the two instances are structurally similar; small differences in state configuration can produce large differences in plan length, and this is expected behavior\.Edge Cases\.•UNSOLVED instances: Ifn∗n^\{\*\}= UNSOLVED \(BFS budget exceeded\), annotate Validity only; skip Difficulty Coherence for this instance\.•Uncertainty: If you are unsure, default to Valid / Agree and note the instance ID in the comments field\.•Domain\-specific notes: For Library Books, a book is considered “placed” only when it is on its*correct*shelf \(check thecorrect\-shelfpredicate in the initial state\)\. For Robot Arm,table\-freemeans no block is*directly*on that table \(stacked blocks do not occupy table space directly\)\. For Rescue Mission, connectivity is symmetric \(connected r1 r2also meansconnected r2 r1\); verify both directions appear in the initial state\.Calibration\.The first 10 instances are a calibration set\. After you complete them, discuss any disagreements with the other annotators before proceeding to the main set\. Do*not*discuss individual annotations during the main set\.

Following the annotation session, annotators reported that the Rescue Mission and Robot Arm instances were straightforward to evaluate, while Library Books required careful attention to thecorrect\-shelfpredicate\. No edge cases required adjudication beyond the calibration discussion\.

Annotator qualifications\.All three annotators hold or are pursuing graduate degrees in computer science with specialization in artificial intelligence\. Each had prior exposure to PDDL through coursework or research; none had participated in the design or generation of the domains being evaluated\. Annotation was conducted voluntarily with no financial compensation\.