Generating Symbolic World Models via Test-time Scaling of Large Language Models
作者: Zhouliang Yu, Yuhuan Yuan, Tim Z. Xiao, Fuxiang Frank Xia, Jie Fu, Ge Zhang, Ge Lin, Weiyang Liu
分类: cs.AI
发布日期: 2025-02-07 (更新: 2025-05-08)
备注: Accepted by TMLR2025 (32 pages, 6 figures)
期刊: Transactions on Machine Learning Research, 2025
💡 一句话要点
通过大语言模型测试时缩放生成符号世界模型，解决复杂规划问题。
🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture) 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 大语言模型 符号世界模型 规划领域定义语言 测试时缩放 口头机器学习
📋 核心要点
- 现有大语言模型在复杂规划中，因自然语言歧义难以准确建模状态转移，导致规划效果不佳。
- 论文提出测试时缩放LLM计算，结合Best-of-N抽样和口头机器学习，提升PDDL领域生成质量。
- 实验表明，该方法在生成PDDL领域任务上显著优于o1-mini，并在竞赛级规划任务上超越现有方法。
📝 摘要（中文）
解决复杂规划问题需要大语言模型（LLMs）显式地建模状态转移，以避免违反规则、遵守约束并确保最优性，但自然语言的固有歧义阻碍了这一任务。为了克服这种歧义，利用规划领域定义语言（PDDL）作为一种规划抽象，从而实现精确和正式的状态描述。借助PDDL，我们可以生成一个符号世界模型，经典搜索算法（如A*）可以无缝地应用于寻找最优计划。然而，由于缺乏PDDL训练数据，直接使用当前LLM生成PDDL领域仍然是一个公开的挑战。为了应对这一挑战，我们提出扩展LLM的测试时计算，以增强其PDDL推理能力，从而生成高质量的PDDL领域。具体来说，我们引入了一种简单而有效的算法，该算法首先采用Best-of-N抽样方法来提高初始解决方案的质量，然后通过口头机器学习以精细的方式改进解决方案。我们的方法在PDDL领域的生成方面明显优于o1-mini，在两个任务（即从自然语言描述或PDDL问题生成PDDL领域）上实现了超过50％的成功率。这是在不需要额外训练的情况下完成的。通过利用PDDL作为状态抽象，我们的方法能够在几乎所有竞赛级别的规划任务上优于当前最先进的方法。
🔬 方法详解
问题定义：论文旨在解决大语言模型在复杂规划任务中，由于自然语言的模糊性，难以生成精确的符号世界模型的问题。现有方法缺乏足够的 PDDL 训练数据，导致直接使用 LLM 生成 PDDL 领域的效果不佳，无法满足复杂规划的需求。
核心思路：论文的核心思路是通过在测试时扩展大语言模型的计算资源，提升其 PDDL 推理能力。具体而言，通过增加计算量，使 LLM 能够更好地理解和生成 PDDL 领域，从而克服自然语言的歧义性，并生成高质量的符号世界模型。
技术框架：该方法主要包含两个阶段：1) Best-of-N 抽样：利用 LLM 生成 N 个候选 PDDL 领域，并从中选择最佳的初始解决方案。2) 口头机器学习：通过迭代的方式，利用 LLM 对初始解决方案进行精细化改进。具体来说，通过自然语言描述当前 PDDL 领域存在的问题，并要求 LLM 提出改进建议，然后将这些建议应用到 PDDL 领域中，重复此过程直到 PDDL 领域达到满意的质量。
关键创新：该方法最重要的创新点在于测试时缩放 LLM 的计算资源，并结合 Best-of-N 抽样和口头机器学习，从而在不增加训练数据的情况下，显著提升了 LLM 生成 PDDL 领域的能力。与现有方法相比，该方法不需要额外的 PDDL 训练数据，并且能够生成更高质量的 PDDL 领域。
关键设计：Best-of-N 抽样中，N 的大小是一个关键参数，需要根据具体的任务进行调整。口头机器学习中，如何设计有效的自然语言提示，引导 LLM 提出有用的改进建议，也是一个关键的设计问题。此外，如何评估 PDDL 领域的质量，并确定何时停止迭代，也是需要考虑的技术细节。论文中没有明确给出这些参数的具体设置，可能需要根据实际情况进行调整。
📊 实验亮点
实验结果表明，该方法在生成 PDDL 领域方面显著优于 o1-mini，在两个任务上实现了超过 50% 的成功率。此外，在竞赛级别的规划任务中，该方法在几乎所有任务上都超越了当前最先进的方法，证明了其在复杂规划问题上的有效性。
🎯 应用场景
该研究成果可应用于机器人规划、游戏AI、自动化任务调度等领域。通过将自然语言描述转化为精确的符号世界模型，可以使智能体更好地理解环境，并制定出更有效的行动计划。该方法有望降低复杂规划问题的开发难度，并提升智能系统的自主性和适应性。
📄 摘要（原文）
Solving complex planning problems requires Large Language Models (LLMs) to explicitly model the state transition to avoid rule violations, comply with constraints, and ensure optimality-a task hindered by the inherent ambiguity of natural language. To overcome such ambiguity, Planning Domain Definition Language (PDDL) is leveraged as a planning abstraction that enables precise and formal state descriptions. With PDDL, we can generate a symbolic world model where classic searching algorithms, such as A*, can be seamlessly applied to find optimal plans. However, directly generating PDDL domains with current LLMs remains an open challenge due to the lack of PDDL training data. To address this challenge, we propose to scale up the test-time computation of LLMs to enhance their PDDL reasoning capabilities, thereby enabling the generation of high-quality PDDL domains. Specifically, we introduce a simple yet effective algorithm, which first employs a Best-of-N sampling approach to improve the quality of the initial solution and then refines the solution in a fine-grained manner with verbalized machine learning. Our method outperforms o1-mini by a considerable margin in the generation of PDDL domains, achieving over 50\% success rate on two tasks (i.e., generating PDDL domains from natural language description or PDDL problems). This is done without requiring additional training. By taking advantage of PDDL as state abstraction, our method is able to outperform current state-of-the-art methods on almost all competition-level planning tasks.