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

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

Related

• Using Language Models as Closed-Loop High-Level Planners for Robotics Applications: A Brief Overview and Benchmarks
• RankLLM: Weighted Ranking of LLMs by Quantifying Question Difficulty
• Improving LLM Interpretability with User-Centric Chain-of-Thought Reasoning

Source: arXiv cs.AI | 2026-10-21