Generating Symbolic World Models via Test-time Scaling of Large Language Models

Solving complex planning problems requires Large Language Models (LLMs) to explicitlymodel 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 suchambiguity, Planning Domain Definition Language (PDDL) is leveraged as a planning abstraction that enables precise and formal state descriptions. With PDDL, we can generate asymbolic world model where classic searching algorithms, such as A*, can be seamlessly applied to find optimal plans. However, directly generating PDDL domains with current LLMsremains 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 reasoningcapabilities, thereby enabling the generation of high-quality PDDL domains. Specifically,we introduce a simple yet effective algorithm, which first employs a Best-of-N samplingapproach to improve the quality of the initial solution and then refines the solution in afine-grained manner with verbalized machine learning. Our method outperforms o1-miniby a considerable margin in the generation of PDDL domain, achieving over 50% successrate on two tasks (i.e., generating PDDL domains from natural language description orPDDL problems). This is done without requiring additional training. By taking advantageof PDDL as state abstraction, our method is able to outperform current state-of-the-artmethods on almost all competition-level planning tasks.