When Planning Problems Become Hard for LLMs: Separating Structural and Semantic Difficulty (arXiv 2610.26964)

Forum topic · 小凯 · 2026-10-22

Summary

This arXiv paper (2610.26964) by Mayukh Debnath, Adeyinka Adedigba, and Rammohan Mallipeddi investigates why large language models (LLMs) struggle with classical planning, separating structural difficulty from the difficulty of interpreting symbolic vocabulary. Across seven STRIPS domains with BFS-optimal plan lengths, the zero-training delete-relaxation heuristic h_add predicts structural difficulty on held-out domains better than learned methods (mean Spearman |rho| = 0.931 vs. 0.707 for ridge regression, 0.657 for object count, and 0.400 for the episodic retrieval architecture ARC). To isolate semantic effects, the authors progressively rename predicates while preserving states, transitions, and optimal plans; LLM planning success drops from 67.5% to 40.0% as renaming goes from 0% to 100%, while rejection rates stay at 0%. An LLM conditioned on ARC information also outperforms trained ARC at in-context difficulty prediction (mean |rho| = 0.826). The authors conclude that hybrid LLM-planner routing depends more on calibrating the target LLM's outcomes than on the structural score used, and that improving hybrid planning requires modeling LLM sensitivity to predicate semantics rather than building more structural predictors.

Paper Overview

Field: Machine Learning
Authors: Mayukh Debnath, Adeyinka Adedigba, Rammohan Mallipeddi
Published: 2026-10-22
arXiv: 2610.26964

Abstract

Large language models (LLMs) struggle with classical planning, but benchmarks rarely distinguish structural difficulty from the difficulty of interpreting symbolic vocabulary. This paper examines seven STRIPS domains with BFS-optimal plan lengths and makes the following contributions:

Key Findings

1. Structural difficulty is well predicted by classic heuristics. For predicting structural difficulty without solving an instance, the zero-training delete-relaxation heuristic $h_{\mathrm{add}}$ outperforms learned alternatives on held-out domains (mean Spearman $|\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.

2. LLM planning is sensitive to predicate semantics. To isolate semantic effects, the authors progressively rename predicates while preserving states, transitions, and optimal plans. Valid LLM planning success drops from 67.5% to 40.0% as renaming increases from 0% to 100%, while the rejection rate remains at 0%.

3. LLMs can predict difficulty in-context. An LLM provided with ARC-conditioned information outperforms the trained ARC model at predicting difficulty in context (mean $|\rho|=0.826$ ).

Conclusion

Hybrid routing between LLMs and symbolic planners depends more on calibrating the target LLM's outcomes than on the choice of structural score. Existing symbolic heuristics already estimate structural difficulty well; improving hybrid planning therefore requires modeling LLM behavior that is sensitive to predicate semantics, rather than developing more structural predictors.

--- *Source: arXiv:2610.26964*