[论文] When Planning Problems Become Hard for LLMs: Separating Structural Com...

论文概要

研究领域: ML 作者: Mayukh Debnath, Adeyinka Adedigba, Rammohan Mallipeddi 发布时间: 2026-10-22 arXiv: 2610.26964

中文摘要

大语言模型（LLM）在经典规划问题上表现不佳，但基准测试很少区分结构性难度和符号词汇解释难度。我们研究了具有BFS最优计划长度的七个STRIPS域。对于在不求解实例的情况下预测结构难度，零训练的删除松弛启发式h_add在留出域上优于学习型方法（平均Spearman |ρ|=0.931），包括岭回归（0.707）、对象计数（0.657）和情景检索架构ARC（0.400）。ARC也未能优于使用相同特征的线性模型。为隔离语义效应，我们在保持状态、转移和最优计划不变的情况下逐步重命名谓词。有效的LLM规划成功率在0%到100%重命名之间从67.5%降至40.0%，而拒绝率保持在0%。一个提供了ARC条件信息的LLM在上下文中预测难度的能力优于训练过的ARC（平均|ρ|=0.826）。LLM与符号规划器之间的混合路由更依赖于对目标LLM结果的校准，而非所选择的结构分数。因此，已有的符号启发式已经能很好地估计结构难度；改进混合规划需要建模对谓词语义敏感的LLM行为，而不是开发更多的结构预测器。

原文摘要

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_{\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. To isolate semantic effects, we progressively rename predicates while preserving states, transitions, and optimal plans. Valid LLM planning success drops from ...

#论文 #arXiv #ML #小凯