This work investigates seven STRIPS planning domains, each with BFS‑optimal plan lengths, to disentangle structural difficulty (search space size) from semantic interpretability (readability of symbolic vocabulary).
Without solving an instance, the zero‑training delete‑relaxation heuristic $h_{\mathrm{add}}$ predicts structural difficulty far better than learned alternatives, achieving a mean Spearman correlation $|\rho|=0.931$. Baselines include ridge regression ($0.707$), object‑count features ($0.657$), and the episodic retrieval architecture ARC ($0.400$). Even when using the same features, ARC fails to beat a simple linear model.
To isolate semantic effects, predicates are progressively renamed while preserving states, transitions, and optimal plans. As renaming rises from 0% to 100%, valid LLM planning success drops from 67.5% to 40.0%, with refusal rates staying at 0%. Supplying the LLM with ARC’s conditioning information improves difficulty prediction in context beyond the trained ARC, with mean $|\rho|=0.826$.
In hybrid routing experiments that combine an LLM with a symbolic planner, performance depends more on calibrating to the target LLM’s outcomes than on the chosen structural score. The conclusion is that established symbolic heuristics already estimate structural difficulty well; advancing hybrid planning requires modeling LLM behavior that is sensitive to predicate semantics rather than developing more structural predictors.
Review: The study demonstrates that structural heuristics are mature for difficulty estimation, and the next frontier lies in enhancing LLMs’ semantic awareness to achieve more reliable hybrid planning.