大语言模型在规划问题上最优性的分析

在大语言模型（LLM）时代，经典AI规划问题被重新审视，而近期基准的关注点集中在成功率而非规划效率上。我们考察前沿模型在多大程度上进行最优推理，而非依赖简单、启发式且可能低效的策略。我们聚焦Blocksworld域，其中涉及由标记方块组成的塔，需要通过一组基本动作将方块从初始构型移动到目标构型。我们还研究一个形式上等价的任务——广义Path-Star（$P^*$）图，以便将真正的拓扑推理与语义先验隔离开来。我们系统地操纵问题深度（方块塔的高度）、宽度（塔的数量）与组合性（目标方块的数量）。在复杂的多目标构型中，推理增强型LLM显著优于传统满足型规划器（如LAMA）。尽管经典搜索算法随着搜索空间扩大而撞上瓶颈，LLM却能以近乎完美的精度追踪理论最优极限，即使领域特定的语义线索被剥离时也是如此。为解释这些惊人发现，我们考虑了（并找到证据支持）两个假设：一是通过推理token执行的主动算法仿真（Algorithmic Simulation），二是允许模型将 $P^*$ 拓扑表示为可导航全局几何的几何记忆（Geometric Memory），从而有效绕过指数级组合复杂度。