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

Introduction

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. [1] report that frontier models solve fewer than 3% of standard PDDL benchmarks; [2] show the failures persist under chain-of-thought prompting [3] and self-critique [4]. Unlike symbolic planners, LLMs perform no explicit combinatorial search, which makes them brittle on problems that require systematically exploring a large state space [5, 6].

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 [5], use an LLM for heuristic guidance [7], or for candidate generation with symbolic verification [2]. Every such system needs an upstream difficulty estimate. Existing approaches use problem size, domain identity, or domain-specific classifiers [8], 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 (§ 3). We compare ARC against object count, goal-fact count, ridge regression on structural features, LogME [9], H-score [10], a non-episodic MLP, and $h_{\mathrm{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: $h_{\mathrm{add}}$ reaches mean $|\rho| = 0.931$ across three held-out domains; ARC reaches 0.400, below every baseline except LogME and H-score, and below a linear model fit on exactly its own structural-feature input. We verify $h_{\mathrm{add}}$ directly: an independent reconstruction of each domain’s grounded action set reproduces every saved optimal plan with zero failures across 1,006 solved 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 from 67.5% with no renaming to 40.0% with every predicate renamed, while refusal rate stays at 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 ($h_{\mathrm{add}}$, mean $|\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 only 0.400–0.403 (ensembled: 0.595), below a linear model on its own structural-feature inputs (0.707). We report this as a substantive negative result for learned cross-domain retrieval, not a limitation of one implementation: Appendix C 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 from 67.5% to 40.0% as renaming goes from none to complete, with refusal rate flat at 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 $|\rho| = 0.826$ vs. 0.400).

Related Work

LLMs for PDDL planning. LLMs struggle with classical planning, including simple Blocksworld instances [2, 11, 12], across IPC-style domains [1, 13, 14, 15]. Self-critique does not reliably fix this [4, 3, 16]. Instruction-tuned PDDL generation improves performance [17], but models still generalize poorly to instances larger or structurally different from training [6, 7, 18, 19]. We take these limitations as given and ask instead when an LLM should be used at all.

Hybrid planning systems. The LLM-Modulo framework [5] wraps LLM calls with formal verifiers [20]. Related work uses LLMs for heuristic guidance [8, 21] or candidate generation with symbolic verification [22, 23]. Every such architecture needs an upstream router; existing routing signals do not transfer across domains with unfamiliar vocabulary.

Feature transferability metrics. LogME [9] and H-score [10] estimate how well a frozen feature space supports a downstream task without fine-tuning [24, 25, 26], 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 [27] performs an explicit inner-loop update per episode; Prototypical Networks [28] 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 [29, 30]: each step draws one source domain and conditions on a labeled support set from it, drawing on the geometric structure of PDDL embeddings [31, 32].

Background and Problem Formulation

PDDL and planning instances. A classical planning instance is a pair $\pi= \langle D, P \rangle$, where $D$ specifies a domain’s predicates and lifted operators in PDDL, and $P = \langle O, s_0, g \rangle$ gives a set of objects $O$, an initial state $s_0$, and a goal condition $g$. A plan is a sequence of ground actions $\mathbf{a} = (a_1, \ldots, a_L)$ whose execution from $s_0$ satisfies $g$. The optimal plan length is

where $\Gamma(s_0,\mathbf{a})$ is the state reached by executing $\mathbf{a}$ from $s_0$. We take $n^*(\pi)$ as our operational definition of structural difficulty.

Difficulty labels. We label every instance by breadth-first search (BFS) within a budget $B = (T_{\max}=12, N_{\max}=5{,}000)$, identically across domains: the regression target is $y_r = n^*(\pi)$. Instances BFS does not solve within $B$ carry 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 § 8.§ 1.

Feature representation. Each instance has three views. Structural features $x_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 or $n^*$. Foundation-model embeddings $x_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 residual $x_r = x_e - \hat{x}_e(x_s)$ is the component of $x_e$ not explained by $x_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: $x_e$ should identify semantic similarity across domains but concentrate within a domain, limiting within-domain discrimination; $x_s$ should do the opposite. We embed every instance’s description with all-mpnet-base-v2 and measure mean within-domain pairwise cosine similarity and effective rank $\exp(\mathcal{H}(\sigma/\sigma_1))$, $\sigma$ the embedding matrix’s singular values. On the three held-out domains, mean cosine similarity is 0.989/0.986/0.992 (BW/LOG/MBW), effective rank 2.62; two further encoders give 0.988/0.988 cosine and 2.64/2.61 rank (Appendix § 10.§ 3), so this is a property of the encoder family on these descriptions, not one model.

Structural features, pooled-standardized, range 0.69–0.95 cosine and 2.1–5.3 effective rank (mean 3.8) within a domain. The hypothesized asymmetry holds in direction — $x_e$ is consistently more collapsed than $x_s$ — but the effective-rank gap is smaller than the cosine gap suggests: $x_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: on balance, no — it is the best of four tested configurations (Appendix C.2), but none is competitive with the non-episodic baselines in Table 1.

ARC: 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: $x_e$ aligns across domains as a query; $x_s$ discriminates within a domain as keys and values. Algorithm 1 gives inference.

The query encoder maps $x_e$ to a 128-dimensional space through a two-layer MLP (LayerNorm, dropout 0.1); the key encoder does the same for $x_s$. The value projection concatenates $x_s^{(i)}$ and $x_r^{(i)}$, so retrieval carries both structural and residual semantic information. Attention temperature starts at $\tau= 1$.

Optional complexity-aware gate. We also evaluate, as a pre-declared variant, a gate $c = \sigma(\operatorname{MLP}(x_s^q)) \in[0, 1]$ blending a linear predictor $\hat{y}_{\mathrm{simple}} = w^\mathsf{T}x_s^q$ with the attention output, trained end-to-end with no auxiliary supervision.

Algorithm 1 ARC Inference (Asymmetric Retrieval)

Require: Query $x_e^q, x_s^q, x_r^q$; support set $\{(x_s^{(i)}, x_r^{(i)}, y^{(i)})\}_{i=1}^{|S|}$ Ensure: Predicted normalized plan length $\hat{y}_r$

1. $q \leftarrow W_{Q_2} \cdot\operatorname{GELU}(\operatorname{LN}(W_{Q_1}x_e^q))$

2. for $i = 1, \ldots, |S|$ do

3. $k_i \leftarrow W_{K_2} \cdot\operatorname{GELU}(W_{K_1}x_s^{(i)}); \quad V_i \leftarrow\operatorname{ValueProj}([x_s^{(i)} \mathbin{\Vert} x_r^{(i)}])$

4. end for

5. $\alpha\leftarrow\operatorname{softmax}(\tau\cdot qK^\top/ \sqrt{d}); \quad z \leftarrow\alpha^\top V$

6. $h \leftarrow\operatorname{FusionMLP}([x_s^q \mathbin{\Vert} z \mathbin{\Vert} x_r^q]); \quad\hat{y}_{\mathrm{attn}} \leftarrow\operatorname{RegressionHead}(h)$

7. if gated variant then $c \leftarrow\sigma(\operatorname{MLP}(x_s^q)); \quad\hat{y}_r \leftarrow c \cdot w^\top x_s^q + (1-c)\hat{y}_{\mathrm{attn}}$

8. else $\hat{y}_r \leftarrow\hat{y}_{\mathrm{attn}}$

9. end if

10. return $\hat{y}_r$

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.

Training 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

mean squared error between the prediction and the domain-level $z$-scored plan length, regularized by the negative entropy of the attention weights ($\lambda_e = 0.05$) to prevent collapse onto one support instance. Every term is optimized by one outer AdamW update (lr $3 \times10^{-4}$, weight decay $10^{-4}$, cosine annealing to $10^{-5}$, gradient clipping 1.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 $\pm$ std over five seeds (0, 1, 2, 42, 123) for every trained method.

Experiments

Setup

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 and $n^*$, over each test domain’s BFS-solved instances; a ranking measure requiring no threshold tuning. For routing § 6.3, we report the fraction of instances solved, with plan validity checked by a state-simulating executor. Confidence intervals: Appendix § 9.§ 1.

Baselines. Object count $|\mathcal{O}|$; unsatisfied goal-fact count; ridge regression on $x_s$; LogME, fit with evidence-optimal regularization rather than a fixed value; H-score; a non-episodic MLP (ERM); and $h_{\mathrm{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. $h_{\mathrm{add}}$ is not an $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 all 1,006 labeled instances in seven domains.

Results

Zero-Shot Estimation of Structural Complexity

$h_{\mathrm{add}}$ transfers best, and no scalar statistic dominates every domain. $h_{\mathrm{add}}$ reaches mean $|\rho| = 0.931$ (0.894/0.976/0.923). Goal count reaches 0.802, ridge on $x_s$ reaches 0.707, object count 0.657. A paired bootstrap (2,000 resamples) of $h_{\mathrm{add}}$ against goal count gives $\Delta|\rho| = +0.119$ [+0.057, +0.192] on BW and +0.236 [+0.143, +0.344] on MBW; on Logistics the two are indistinguishable ($\Delta= 0.000$), because $h_{\mathrm{add}}$ reduces to a monotonic function of unsatisfied-goal count on this domain’s relaxed graph (Appendix § 9.§ 4). Object count exceeds ridge on BW and MBW; ridge is far stronger on LOG (0.889 vs. 0.544). $h_{\mathrm{add}}$ is not an $O(1)$ read, so we verify its action-set reconstruction directly: zero failures re-simulating 1,006 saved plans. Appending $h_{\mathrm{add}}$ as a 29th feature to ridge on $x_s$ is mixed, not uniform (+0.095 MBW, −0.001 LOG, −0.077 BW), 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 mean 0.400 (0.294 $\pm$ 0.216/0.652 $\pm$ 0.297/0.254 $\pm$ 0.157); the gated variant, 0.403. Both trail every deterministic baseline except LogME and H-score, and $h_{\mathrm{add}}$ by a wide margin. The standard deviations are large relative to the means ($\pm$0.216 against a mean of 0.294 on BW), so single-seed ARC numbers are unreliable estimates of transfer performance. Averaging predictions across seeds before correlating, rather than averaging correlations, partly closes the gap (mean 0.595: 0.482/0.912/0.390) but still falls short of $h_{\mathrm{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 § 10 tests whether this is specific to one design choice (attention direction, feature combination, residualization) and finds the shortfall persists throughout.

A coarse-proxy explanation does not hold. Within fixed object-count groups, where $|\mathcal{O}|$ carries no ranking information, ridge on $x_s$ keeps mean $|\rho| = 0.49/0.94/0.17$ (BW/LOG/MBW; Table 2) — 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.24/0.32/0.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 § 9.§ 5.

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 (mean 0.732 vs. 0.520), and ARC, retrained per fold, trails ridge on all seven (mean 0.640 vs. 0.732; Appendix § 9.§ 2). Excluding the few BFS-solved instances with $n^\star= 0$ changes the means to 0.813/0.809/0.643/0.931 (goal count/ridge/object count/$h_{\mathrm{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 § 9.§ 6, § 9.§ 7, § 12).

Semantic Perturbations Separate Structural from Behavioral Difficulty

Section 6.1 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).

We progressively corrupt the same 40 BFS-solved Blocksworld instances. For each $k \in\{0, 25, 50, 75, 100\}\%$, we replace a fraction $k$ of predicate and action names with meaningless tokens, applied consistently across domain and problem files. This preserves every precondition, effect, state, goal, and optimal plan length $n^*(\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).

Success falls from 67.5% to 40.0% (Table 3); the endpoint intervals, [52.0, 79.9] and [26.3, 55.4], barely overlap. The decline is not perfectly monotonic step to step (47.5 → 37.5 → 40.0 across the last three levels), consistent with $N = 40$ being too small to resolve small adjacent differences; we read the endpoint-to-endpoint effect, not a strict trend. Refusal rate is 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 across $k$ by construction. Comparing structural estimators across BW and MBW in Table 1 is not a paired test of this, since they are independently generated instance sets, not renamings of the same instances (goal count 0.764 vs. 0.673; ridge 0.644 vs. 0.587; object count 0.764 vs. 0.662). The paired test is the scrambling experiment itself, where $n^*(\pi)$ is identical for every instance at every $k$: the 27.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.

Structural 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 [2], 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 strongest $O(1)$ statistic in Table 1; $h_{\mathrm{add}}$ would likely be stronger still, which we flag as a natural extension rather than one we have run.

What Static=Oracle= 100% means. The fallback always succeeds, so no policy can exceed 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 reaches 99–100% on every domain, ahead of $\lvert O\rvert$-FS (86.0/77.0/85.0) and Goal-FS (64.0 everywhere); 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 § 6.1. 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 ($\le50\%$) and where calibration helps most (ARC: +49 points ZS→FS), consistent with the LLM’s own LOG success being near zero regardless of structural difficulty (Appendix § 8.§ 3): 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 best 73% correctly identified as LLM-tractable), while 140 calibration examples close most of the remaining gap for every method tested.

Conclusion

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: $h_{\mathrm{add}}$ reaches mean $\lvert\rho\rvert= 0.931$ with optimal plan length, goal count 0.802, ridge on 28 structural features 0.707, object count 0.657. Ridge beats object count on six of seven domains leave-one-domain-out, and $h_{\mathrm{add}}$’s correctness is independently verified: zero failures re-simulating 1,006 saved 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: mean 0.400 (0.403 gated), below every deterministic baseline except LogME and H-Score, below a linear model on its own inputs (0.707), below its own weaker input scored alone ($x_e$ alone: 0.412), far below $h_{\mathrm{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.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 alongside $h_{\mathrm{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 from 67.5% to 40.0% as corruption rises from 0% to 100%, refusal rate flat at 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 by $h_{\mathrm{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 $|\rho| = 0.826$) far better than ARC does after training, second only to $h_{\mathrm{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.

Data, Labels, and Evaluation Protocol

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

Label Availability and Supervision

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

used to learn a continuous structural-difficulty ranking. This label is available whenever breadth-first search returns a solution under the budget $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.

Coverage of the label is incomplete and domain-dependent (Table 5): between 63.0% (Blocksworld, Satellite) and 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^{\star} \in[7, 10]$) and Rovers ($n^{\star} \in[2, 5]$) cover narrow ranges of plan length. Second, a small number of BFS-solved instances have $n^{\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 to 0.813 (goal count), 0.809 (ridge on $x_s$), and 0.643 (object count), with $N = 111$, 158, 123 remaining 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.

LLM 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 temperature 0, a maximum of 2,048 output 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.

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.

LLM Capability Threshold Across Model Families

To assess whether the qualitative findings of § 6.2 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) on three additional models spanning a $10 \times$ parameter range and two model families distinct from Qwen: Mistral-7B, Gemma2-9B, and Qwen2.5-14B.

Across all four models ($N = 40$ per 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 reach 40.0%, while the larger Qwen2.5-72B reaches only 30.0% and Mistral-7B reaches 0.0%. On Mystery-Blocksworld, Qwen2.5-72B is the strongest model tested (35.0%), ahead of Gemma2-9B (27.5%), with Qwen2.5-14B and Mistral-7B both at 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.

Evidence 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.

Confidence Intervals for the Primary Result

Table 7 reports approximate 95% confidence intervals for the primary Spearman correlations. The intervals are computed using the Fisher transformation,

followed by transformation back to the correlation scale, with $N$ the number of BFS-solved instances of the domain (126, 164, 133 for BW, LOG, MBW). This approximation treats the reported Spearman coefficient as a Pearson correlation over ranked observations. 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,000 resamples of the target instances, recomputing both correlations on each resample) for

$-0.119$ [$-0.249$, $-0.005$] on Blocksworld, $+0.345$ [$+0.237$, $+0.460$] on Logistics, and $-0.075$ [$-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’s intervals alone on Blocksworld (ARC [0.126, 0.446] vs. Ridge [0.529, 0.736]) and is unambiguous against $h_{\mathrm{add}}$ (0.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.

Broader 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, the named domain is excluded from model fitting (ridge regression is retrained on the other six domains) and used as the evaluation domain. Ridge regression on the structural features exceeds object count on six of the seven held-out domains (mean 0.732 vs. 0.520), ties on Depot, and both are close to zero on Rovers, whose plan lengths span only 2–5. 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 (mean 0.640 vs. 0.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.

Comparison 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 same 28-dimensional structural representation $x_s$, trained on the source domains with the raw plan length as target, together with a Random Forest given both $x_s$ and the foundation-model embedding $x_e$. These comparisons test whether conventional learners with more capacity than ridge regression, or more information than ridge regression, change the picture.

Table 9 shows that ridge regression is the strongest of the $x_s$-only learned methods (mean $\lvert\rho\rvert= 0.707$), followed by gradient boosting (0.674) and XGBoost (0.633); Random Forest on $x_s$ alone (0.388) and kernel SVR (0.252) transfer poorly. Giving Random Forest the embedding as well as the structural features raises its mean from 0.388 to 0.574 — a substantial within-method improvement, unlike the roughly neutral effect concatenation has on ridge regression (Appendix § 10.§ 1) — but this still falls short of ridge regression on $x_s$ alone (0.707) and far short of $h_{\mathrm{add}}$ (0.931). No learner on $x_s$, $x_e$, or their concatenation, and no training-free scalar statistic, exceeds $h_{\mathrm{add}}$. ARC, despite having access to the same foundation-model embedding that helps Random Forest, exceeds only Random Forest on $x_s$ alone among the $x_s$-only learners (0.400 vs. 0.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 § 10 tests each of these design choices directly and finds none of the tested variants closes the gap to ridge regression, let alone to $h_{\mathrm{add}}$.

Cheap 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: five $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.

Among the five $O(1)$ statistics, goal count is strongest (mean $\lvert\rho\rvert= 0.802$, 0.969 on Logistics) and no single one dominates every domain. All five, however, are clearly exceeded by $h_{\mathrm{add}}$ (mean 0.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 an $O(1)$ read: it requires the same grounded action set a real planner would use, together with a bounded graph expansion (capped at depth 30 in 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 all 1,006 BFS-solved instances with $n^{\star} > 0$ across the seven domains (BW 111/111, Depot 132/132, Gripper 157/157, Logistics 158/158, Mystery-BW 123/123, Rovers 199/199, Satellite 126/126); $h_{\mathrm{add}}$ is reported only for domains that pass this check.

The Logistics tie is not a coincidence. A paired bootstrap (2,000 resamples) of $h_{\mathrm{add}}$ against goal count gives $\Delta|\rho| = +0.119$ [+0.057, +0.192] on Blocksworld and +0.236 [+0.143, +0.344] on Mystery-Blocksworld — both robustly positive — but exactly $\Delta= 0.000$ with 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), so $h_{\mathrm{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 expect $h_{\mathrm{add}}$ and goal count to agree elsewhere, and they clearly do not agree on the other two domains.

$h_{\mathrm{add}}$ as an additional feature, not just a standalone score. We also tested appending $h_{\mathrm{add}}$ as a 29th feature to ridge regression on $x_s$, trained and evaluated identically to the $x_s$-only ridge row elsewhere in this paper. The result is mixed, not uniformly positive: mean $|\rho|$ changes by +0.095 on Mystery-Blocksworld, −0.001 on Logistics, and −0.077 on Blocksworld, relative to ridge on $x_s$ alone. $h_{\mathrm{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 does not by itself show whether ARC captures information inaccessible to $h_{\mathrm{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 $h_{\mathrm{add}}$’s 0.931, not goal count’s 0.802.

Within-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.

As reported in Table 11, ridge regression on the structural features retains substantial within-size discrimination on Logistics (mean $|\rho|$ = 0.94), moderate discrimination on Blocksworld (0.49), and weak discrimination on Mystery-Blocksworld (0.17). These results show that structural features carry information beyond object count in all three

caption: Association between ridge regression on $x_s$ and solver-derived measures, $N = 60$ BFS-solved instances per domain. The first three columns correlate the ridge prediction with BFS optimal plan length, $A^{*}$ node expansions, and $A^{*}$ wall-clock time; the final column correlates object cardinality with $A^{*}$ node expansions.

:::

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).

Association 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,000) an order of magnitude larger than the BFS label budget. As a sanity check, $A^{*}$ never returns a plan shorter than the BFS-optimal $n^{*}(\pi)$ on any of the 120 instances 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 of $N = 60$ BFS-solved instances per domain, and uses ridge regression on $x_s$ in place of ARC.

On both domains, ridge regression’s ranking is associated with the independent $A^{*}$ planner’s effort (node expansions: 0.683, 0.502; wall-clock time: 0.668, 0.553) at a level broadly similar to its association with the BFS label itself (0.674, 0.532), and object cardinality is associated more strongly still with $A^{*}$-node effort on both domains (0.916, 0.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.

Comparison 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–6.3.

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 and $n^{*}$ 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 against $n^{*}$. Full prompt templates for both variants are provided in Appendix D.

Results. The absolute-scoring variant is the second-strongest method in this entire paper after $h_{\mathrm{add}}$: mean $\lvert\rho\rvert= 0.826$, ahead of goal count (0.802), ridge regression on $x_s$ (0.707), and ARC (0.400) by a wide margin, and within 0.105 of $h_{\mathrm{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 except $h_{\mathrm{add}}$. Pairwise comparison is markedly weaker (0.524) despite the common intuition that relative judgments are more reliable for LLMs than absolute ones; with only $\approx2.5$ comparisons 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 ($|\rho| = 0.723$ and 0.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 § 6.2 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 § 9.§ 4).

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.

Evidence 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.

Representation-Family Ablation

ARC combines three representations: structural features $x_s$, foundation-model embeddings $x_e$, and residual semantic features $x_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 using $x_s$, $x_e$, and their direct concatenation $x_s \Vert x_e$.

Table 14 separates what the two feature families contribute on their own, and the result is unfavorable to ARC’s design premise. The semantic embedding $x_e$ alone is markedly weaker than the structural features alone (0.412 vs. 0.707), confirming that $x_e$ is the weaker of the two representations on this task. Concatenating the two (0.689) very nearly

caption: tbl:15: Matched-budget attention-direction ablation (five seeds each, trained with a separate but matched training loop; see caveat in the text). $\cos(h)$ is the mean within-domain cosine similarity of the learned representation, and $\operatorname{rank}_{\mathrm{eff}}(h)$ is its effective rank. Lower cosine similarity and higher effective rank indicate greater representational variation, but the primary outcome is mean absolute Spearman correlation. Per-domain means underlying this table: semantic/semantic 0.352/0.416/0.339; structural/semantic 0.296/0.492/0.293; semantic/normalised-structural 0.288/0.520/0.285; ARC’s own configuration 0.221/0.812/0.203 (BW/LOG/MBW).

:::

recovers $x_s$ alone and does not exceed it; naive concatenation does not help a linear model, though it does help Random Forest (Appendix § 9.§ 3: 0.388 → 0.574), suggesting the information in $x_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, including $x_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.

Attention 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 use the same matched training budget and the same loss, with five seeds each. ARC’s own query–key assignment (semantic query, structural key) attains the highest mean among the four variants tested (0.412), ahead of the next best, symmetric semantic attention, by 0.043. This is a genuine, if modest, internal validation of the design choice: given that ARC must use some assignment of $x_e$ and $x_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 on $x_s$ alone (0.707) and $h_{\mathrm{add}}$ (0.931) from Table 1, 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’s ARC rows) so that all four variants share exactly the same code path; its ARC-configuration mean (0.412) is close to but not identical with Table 1’s main-configuration mean (0.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.

Encoder 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 reports mean pairwise cosine similarity within each held-out domain and the effective rank of the resulting embedding matrices. All three encoders produce extremely high within-domain cosine similarity (0.986–0.992) and a very low effective rank (2.61–2.64), essentially indistinguishable across encoders despite their different training data and parameter counts. This confirms the collapse diagnostic in § 3 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 achieves a non-trivial correlation (0.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 § 6.1 and Appendix § 10.§ 1 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.

Residualisation Sensitivity

ARC defines the residual semantic feature as

where $\widehat{x}_e(x_s)$ is estimated by applying PCA to $x_e$ and fitting Ridge regression from the structural representation. The default configuration uses PCA dimension 20 and Ridge coefficient $\alpha= 1.0$. Table 17 varies each choice while holding the other fixed.

The PCA dimension sweep is mildly favorable to smaller values ($d_{\mathrm{PCA}} = 5$: $0.532 \pm0.109$, against $0.412 \pm0.083$ at the default 20), but with substantial seed variance at every setting. The Ridge-coefficient sweep contains a result we did not anticipate and have not validated: $\alpha= 100$ reaches $0.753 \pm0.017$, exceeding every other setting in this sweep, exceeding ridge regression on $x_s$ alone (0.707), and with far lower seed variance than the default (0.017 vs. 0.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 $\alpha= 100$ post 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).

Prompts Used in LLM Evaluation

All LLM evaluations use temperature 0 and maximum 2,048 output tokens. Prompts follow the chain-of-thought PDDL formatting of [17]. No domain-specific demonstrations are provided in the zero-shot setting. Brackets [PLACEHOLDER] denote fields filled at runtime.

Prompt 1: PDDL Plan Generation (Main Evaluation)

Used to evaluate LLM planning validity on all three test domains (Blocksworld, Logistics, Mystery-Blocksworld) for Table 3 and Table 4. 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 § 8.§ 2 refers back to it rather than reproducing it a second time.

Prompt 1 – PDDL Plan Generation

You are an expert AI planning assistant. Your task is to solve a classical planning problem specified in PDDL (Planning Domain Definition Language).

I will provide you with:

1. A PDDL domain file describing the planning domain

2. A PDDL problem file describing the specific problem to solve

Your goal is to find a valid plan — a sequence of actions that transforms the initial state into a state satisfying the goal.

IMPORTANT INSTRUCTIONS:

• Think step by step about the current state and what actions are applicable.

• Each action in your plan must be applicable in the state resulting from all previous actions.

• Output ONLY the final plan, one action per line, in the format:

  (action-name param1 param2 ...)

• Do NOT include any explanation after the plan.

• If the problem is unsolvable, output exactly: NO_PLAN

=== DOMAIN ===

[DOMAIN_PDDL]

=== PROBLEM ===

[PROBLEM_PDDL]

Now solve the problem. Think through the state changes carefully, then output the plan:

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 \to pred7$, $stack \to act3$). 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)

You are an expert AI planning
assistant. Your task is to solve
a classical planning problem
specified in PDDL (Planning
Domain Definition Language).

I will provide you with:
1. A PDDL domain file
describing the planning domain
2. A PDDL problem file
describing the specific problem
to solve

Your goal is to find a valid
plan, a sequence of actions
that transforms the initial
state into a state satisfying
the goal.

IMPORTANT INSTRUCTIONS:
– Think step by step about the
current state and what actions
are applicable.
– Each action in your plan must
be applicable in the state
resulting from all previous
actions.
– Output ONLY the final plan,
one action per line, in the
format: (action-name param1
param2 ...)
– Do NOT include any explanation
after the plan.
– If the problem is unsolvable,
output exactly: NO_PLAN

=== DOMAIN ===
;; Blocks planning domain
(define (domain mystery-blocks)
  (:requirements :strips :typing)
  (:types object - object)
  (:predicates
    (pred1 ?x - object)
    (pred2 ?x - object)
    (pred3 ?x - object)
    (pred5)
    (pred7 ?x - object ?y - object))

  (:action act1
    :parameters (?x - object)
    :precondition (and (pred3 ?x)
      (pred1 ?x) (pred5))
    :effect (and (pred2 ?x)
      (not (pred3 ?x)) (not (pred1 ?x))
      (not (pred5))))
...

[remaining scrambled actions]
)
=== PROBLEM ===
[SCRAMBLED_PROBLEM_PDDL]

Now solve the problem. Think
through the state changes
carefully, then output the plan:

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

Used for the LLM-only difficulty baseline in Appendix B.7. 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)

You are an expert at analyzing
PDDL planning problems. Below
are labeled examples from
RELATED planning domains, each
showing a problem and its
optimal (shortest) plan length.
The query problem is from a
DIFFERENT domain with different
predicates and actions, but
similar structural principles
(object counts, goal complexity,
initial state structure) may
transfer.

=== LABELED EXAMPLES
(from other domains) ===
[SUPPORT_BLOCK]

=== QUERY DOMAIN ===
[QUERY_DOMAIN_PDDL]

=== QUERY PROBLEM
(predict difficulty for
this one) ===
[QUERY_PROBLEM_PDDL]

Based on the pattern in the
labeled examples (how problem
structure relates to plan
length), estimate a DIFFICULTY
SCORE for the query problem,
from 0 (trivially easy, very
short plan) to 100 (very hard,
very long plan).
Output ONLY a single integer
between 0 and 100. No explanation.
Score:

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

Used for the pairwise-comparison variant of the LLM-only baseline in Appendix § 9.§ 7. [PROBLEM_A] and [PROBLEM_B] are two randomly sampled query instances from the same held-out domain.

Prompt 4 – LLM Difficulty Prediction (pairwise comparison)

You are an expert at analyzing
PDDL planning problems. Below
are labeled examples from
RELATED planning domains, each
showing a problem and its
optimal (shortest) plan length.

=== LABELED EXAMPLES
(from other domains) ===
[SUPPORT_BLOCK]

=== QUERY DOMAIN ===
[QUERY_DOMAIN_PDDL]

=== PROBLEM A ===
[PROBLEM_A]

=== PROBLEM B ===
[PROBLEM_B]

Which problem requires a
LONGER optimal plan (is
harder)? Output ONLY ’A’
or ’B’. No explanation.
Answer:

Summary

The prompts comparison summary is discussed in Table 18.

All prompts use temperature $= 0$ and max 2,048 output tokens. Prompt 1 follows [17]’s chain-of-thought PDDL format. No domain-specific demonstrations are provided in Prompts 1–2; Prompts 3–4 condition on the 20-example labeled support block described in Appendix § 9.§ 7 in place of domain-specific demonstrations.

Custom Non-IPC Planning Domains

Introduction

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, and Library 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 length $n^\star$) are obtained by BFS with the same budget used in the main evaluation ($T_{\max}=12$, $N_{\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 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.856) where it is substantially ahead of Ridge on $x_s$ (0.693). ARC is competitive only on Library Books (0.679, close to Ridge’s 0.693) and is clearly the weakest method on Rescue Mission (0.099, against 0.224–0.805 for 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 = 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.

(: objects  agent1 room1 room2 supply1 victim1)
(: init  (at agent1 room1) (connected room1 room2)
         (connected room2 room1) (at supply1 room2)
         (at victim1 room2) (needs victim1 supply1))
(:goal (rescued victim1))

Dataset 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 ($n_v \in[2,12]$), number of rooms ($n_r = n_v + 1$), number of agents ($n_a = \lceil n_v/3\rceil$), number of supply types ($n_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 ($n_b \in[3, 12]$), number of tables ($n_t = \lfloor n_b/3 \rfloor+ 1$, minimum 2), number of initial stacks (random in $[0, \lfloor n_b/3 \rfloor]$), goal configuration (random stacking of 2–$n_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 ($n_b \in[2, 5]$ for solvable instances), number of shelves ($n_s = n_b$, minimum 2), number of carts ($n_c = 1$), number of patrons ($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).

Dataset 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. 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. 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-computed $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.

Cohen’s $\kappa> 0.80$ indicates strong agreement [33]. All pairwise $\kappa$ values exceed 0.88, and all percent agreement scores exceed 90%, confirming the validity and coherence of the generated instances.

As summarized in Table 20, all three domains achieve mean pairwise Cohen’s $\kappa> 0.90$ and percent agreement $> 91\%$, satisfying the standard threshold for strong inter-annotator reliability [33]. No instances were removed following the verification process. We note that annotators were shown the BFS-computed $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 seeing $n^*$; the validity checks, which do not depend on $n^*$, are not subject to this concern.

Dataset Statistics

Table 21 summarizes structural statistics for all generated instances in each domain.

Difficulty variation. Rescue Mission shows the widest range ($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 BFS%: fraction solved by BFS within budget ($T_{\max}=12$, $N_{\max}=5{,}000$). EHC%: fraction solved when BFS is replaced by EHC($h^{\mathrm{FF}}$) with the same node budget. Library Books has a low BFS solve rate because the compound constraint (book, cart, and correct shelf co-location) produces long plans exceeding the BFS step budget; EHC($h^{\mathrm{FF}}$) recovers 31% with informed search.

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 above; we did not additionally compute within-size (fixed-object-count) correlations on these three domains, since their already-small sample sizes ($N = 85$, 85, 35) 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 Verification

Task 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 length $n^*$ (or “UNSOLVED”).

Annotation Dimensions.

1. Validity (Binary: Valid / Invalid)

Mark an instance as Invalid if any of the following hold:

• The initial state contains a fact that violates type constraints (e.g., an object declared as type block appears in a predicate that expects type table).

• The goal is already satisfied in the initial state (degenerate instance, $n^* = 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 both clear and on another block that is itself clear).

Otherwise, mark as Valid. 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|$) but different BFS plan lengths. For each pair $(A, B)$ where $n^*(A) < n^*(B)$, indicate whether you agree that $A$ is intuitively easier than $B$ based on the initial and goal states.

Mark Agree if:

• The instance with smaller $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, if $n^*(A) < n^*(B)$ because agent and supply are in the same room in $A$ but not in $B$, this is coherent.

Mark Disagree if:

• 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)$ 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: If $n^* = \text{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 the correct-shelf predicate in the initial state). For Robot Arm, table-free means no block is directly on that table (stacked blocks do not occupy table space directly). For Rescue Mission, connectivity is symmetric (connected r1 r2 also means connected 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 the correct-shelf predicate. 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.