PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2502.04728v2cs.AI

TL;DR

LLMs struggle to generate logically consistent PDDL domains, a challenge compounded by scarce high-quality PDDL training data. The paper combines Best-of-N sampling with iVML to generate and iteratively refine PDDL domains at test time. It reports strong PDDL synthesis results and more robust planning than direct LLM-based approaches.

  • Problem

    Generating PDDL domains with accurate syntax and semantics remains challenging because high-quality PDDL training data is scarce and logical consistency across predicates and actions is difficult to maintain.

    Source: §1 · p. 1

  • Method

    The method samples candidate PDDL domains with Best-of-N and refines promising candidates using iVML, which updates domains from LLM-generated validity checks and critiques without additional training.

    Source: §1 · pp. 2–3

  • Results

    The approach outperforms state-of-the-art closed-source LLM planners including o1-mini on PDDL synthesis; with Qwen2.5-Coder-7B it achieves 85.2% success on NL2Domain and 71.4% on Prob2Domain.

    Source: §1 · p. 3, §5 · p. 15

  • Takeaways & Limitations

    PDDL-based formal abstraction supports more robust planning than direct LLM-based approaches, including in Barman and Termes where existing LLM planners fail.

    Source: §1 · p. 3

    VAL checks syntax and plan executability but cannot detect semantic inconsistencies with domain intent or commonsense logic.

    Source: §5 · p. 15

Abstract

from arXiv · show

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.

1 Introduction

The paper addresses the difficulty of generating logically consistent PDDL domains with LLMs despite PDDL’s formal support for specifying constraints and objectives. It combines Best-of-N sampling with instance verbalized machine learning (iVML) to generate and refine PDDL world models without additional training.

1 Introduction

  • Best-of-N sampling generates diverse candidate PDDL domains, and iVML refines the best candidates to fit the input query.The input may be a natural-language description or a PDDL problem.Source: §1 · p. 2
  • With Qwen2.5-Coder-7B, the approach achieves 85.2% success on NL2Domain and 71.4% on Prob2Domain, outperforming o1-mini by 41.7% and 33.7%, respectively.The paper reports state-of-the-art performance on both PDDL domain synthesis tasks without additional model training.Source: §1 · p. 3
  • iVML adapts verbalized machine learning to instance learning by using LLMs to check PDDL validity and generate textual critiques as gradients for iterative updates.This refinement setting has no training data for producing verbalized gradients.Source: §1 · p. 3
  • The hybrid strategy pairs BoN’s exploration with iVML’s feedback-driven exploitation to improve convergence and solution quality.The paper presents these strategies as complementary ways to generate high-quality PDDL domains.Source: §1 · p. 3
  • PDDL-based formal abstraction enables more robust planning than direct LLM-based approaches on complex domains such as Barman and Termes.The paper reports success in domains where existing LLM-based planners fail.Source: §1 · p. 3

2 Related Work

Prior LLM planners can make rule and state-transition errors, while PDDL synthesis methods have often depended on expert input, training data, or oracle feedback. This work situates its approach among symbolic planning and test-time adaptation methods, targeting PDDL generation without training data or oracle signals.

2.1 LLMs for Task Planning

  • Direct LLM planners can violate rules or misestimate state transitions, motivating symbolic world models followed by heuristic search such as A*.The related-work discussion also describes hallucinated planning outcomes that an LLM evaluator may incorrectly accept.Source: §2.1 · p. 4, Figure 2 · p. 4

2.2 World Model Generation

  • Earlier PDDL synthesis approaches use human experts, substantial training data, or oracle feedback, whereas this work targets scalable generation without training data or an oracle.Other world-model approaches use pre-collected trajectories for validation and feedback.Source: §2.2 · pp. 4–5

2.3 Adaptation of LLMs

  • VML updates text-parameterized models through in-context learning, and test-time adaptation offers an alternative when high-quality training data is unavailable.The paper applies this adaptation setting to generate PDDL-based world models.Source: §2.3 · p. 5

3 The Proposed Test-time Compute Scaling Approach

The approach addresses LLM difficulties with state estimation, constrained planning, and validation by generating symbolic PDDL models and improving them through better initialization and iVML.

3.1 PDDL-based World Model Representation

  • PDDL represents atoms, predicates, actions, and states explicitly, supporting precise validation and classical planning with search algorithms such as A*.The paper contrasts this with natural-language plan prediction as ungrounded token generation.Source: §3.1 · p. 6

3.2 Best-of-N Sampling for PDDL Initialization

  • Best-of-N generates candidate PDDL domains, adjusts sampling diversity with temperature, and selects the top K highest-scoring candidates to initialize iVML.Higher temperatures increase candidate diversity, while lower temperatures favor more deterministic outputs.Source: §3.2 · p. 6

3.3 iVML: Instance Verbalized Machine learning

  • iVML adapts verbalized machine learning to refine a single PDDL-domain instance, parameterizing functions in natural language and seeking a domain aligned with the input description.The objective is difficult to optimize directly because both the input and domain are text and their closeness is hard to define.Source: §3.3 · pp. 6–7
  • At each iteration, an optimizer LLM critiques the current domain and thoughts against the task description, and an updater revises them; the initial domain comes from BoN.The optimizer evaluates grammar and logic, while the updater produces a domain more consistent with the description.Source: §3.3 · pp. 7–8
  • BoN explores diverse candidates but can yield diminishing returns through redundant generations; iVML refines selected candidates but remains susceptible to local minima [35].The paper presents their combination as balancing exploration and exploitation.Source: §3.3 · p. 8

4 Experiments and Results

The experiments evaluate PDDL synthesis and planning across domain-generation, problem-generation, and planning tasks. They report gains from test-time scaling and BoN-initialized iVML, including stronger planning results with synthesized PDDL models and heuristic search.

4.1 Experiment Setup

  • The experiments assess domain validity with VAL, problem synthesis by goal correctness, and planning by exact match to reference plans, using a range of open- and closed-source models.The proposed scaling methods are tested on Qwen models without fine-tuning; domain synthesis uses VAL validation, while planning accuracy measures exact plan matches.Source: §4.1 · pp. 9–10

4.2 Main Results in PDDL Domain Synthesis

  • o1-preview leads closed-source models at 54.1% average accuracy versus GPT-4o’s 27.7%, while Qwen2.5-Coder (7B) scores 21.9% versus Qwen-Instruct (7B)’s 5.7% on NL2Domain.Qwen2.5-Instruct (72B) reaches 38.5% on NL2Domain and 32.8% on Prob2Domain.Source: §4.2 · p. 10
  • iVML-5-BoN-8 reaches 86.2% on NL2Domain with Qwen2.5-Instruct (32B), a 19.4% improvement over BoN-8.The experiments also report BoN-8 gains across Qwen model scales, including a 22.3% NL2Domain improvement for Qwen2.5-Instruct (72B).Source: Table 2 · p. 9, §4.2 · p. 10

4.3 Convergence Comparison between BoN and iVML

  • BoN validation success rises steeply through N = 32, then saturates or degrades; iVML improves monotonically through T = 80, exceeding 95% on NL2Domain and 90% on Prob2Domain.The TyreWorld case study shows iVML correcting BoN’s invalid “closed ?container” predicate to “not (closed?container)”.Source: §4.3 · p. 11, Figure 3 · p. 11

4.4 Ablation Study of Initialization Strategies

  • BoN initialization accelerates iVML convergence and improves solution quality: Deepseek-Coder reaches approximately 95% at T = 16 versus below 60% with single-pass initialization.With BoN-4 initialization, LLaMa produces around 10 correct NL2Domain outputs (around 4%) versus zero in single-pass mode, but remains behind the stronger code models.Source: §4.4 · pp. 11–12, Table 3 · p. 12

4.5 PDDL Problem Generation

  • On PDDL problem generation, Qwen2.5-Coder (7B) reaches 99.24% correctness with BoN-16 and 99.60% with iVML-1-BoN-16.The paper reports that iVML requires significantly less compute than supervised fine-tuning while maintaining strong performance on complex reasoning tasks.Source: §4.5 · pp. 13–14, Table 4 · p. 13

4.6 Comparison to LLM-as-Planner Methods

  • With BoN-16-iVML-5 world models and A* heuristic search, the method solves nearly all tested Floortile, Barman, and Termes instances; oracle-comparison results instead cite BoN-4-iVML-5 as an example.o1-preview scores 5.0 on Floortile, 6.7 on Barman, and 4.7 on Termes.Source: §4.6 · p. 15

5 Concluding Remarks and Current Limitations

The paper combines Best-of-N initialization with iterative verbalized refinement to generate PDDL domains through test-time scaling. It concludes that symbolic models support classical search, while noting limits in semantic verification and simulation realism.

5 Concluding Remarks and Current Limitations

  • BoN initialization followed by iVML refinement forms the paper’s two-phase framework for automated PDDL synthesis.The authors say the approach uses test-time computation without additional training and can extend to formal-language synthesis beyond PDDL.Source: §5 · p. 15
  • PDDL-based symbolic world models let classical search generate plans without relying on direct LLM state transitions.The conclusion says this avoids error-prone state transitions inherent in direct LLM-as-planner approaches.Source: §5 · p. 15
  • VAL checks syntax and plan executability but cannot detect semantic inconsistencies with domain intent or commonsense logic.Evaluation also assumes perfect action execution and fully observable states, unlike real-world robotic manipulation.Source: §5 · p. 15

6 Broader Impact

The authors frame symbolic world modeling and heuristic search as a response to LLM planning errors and concerns about autonomous-agent safety. They argue that this approach may improve the transparency and controllability of human-centered AI systems.

6 Broader Impact

  • The authors connect hallucinations and planning errors in LLMs to risks from difficult-to-control autonomous agents [5] [29].They argue for safeguards around fully autonomous systems and describe hallucinations, rule violations, and incorrect state-transition estimates.Source: §6 · pp. 15–16
  • The scientist AI paradigm [5] separates structured world-model learning from inference grounded in that model.The authors liken their approach to this two-stage framing: construct a symbolic world model, then apply heuristic search.Source: §6 · p. 16
  • The authors argue that symbolic reasoning can mitigate hallucination risks and make agent planning more transparent.They present this as a step toward controllable, interpretable, and safe human-centered AI systems.Source: §6 · p. 16

A Planning Problem Formulation

Classical planning seeks an action sequence from an initial state to a goal, while LLM-generated PDDL makes states and transitions explicit for classical search. The appendix also describes predicate-based states, action preconditions and effects, and transition-graph exploration.

A Planning Problem Formulation

  • Classical planning seeks actions that move an agent from an initial state to a goal in a deterministic, fully observable environment.The formulation represents the problem with states, actions, a transition function, an initial state, and a goal condition; the action sequence applies the transition function successively.Source: A Planning Problem Formulation · p. 21
  • Unlike implicit state-transition estimates in LLM planners, generated PDDL provides explicit state-space representations.The passage says implicit representations can make consistency, validity, and completeness difficult to ensure.Source: A Planning Problem Formulation · p. 21
  • PDDL domains specify states, actions, transitions, initial states, and goals so classical algorithms can search for plans.The objective is to generate domains from high-level task descriptions and use their defined transitions during search.Source: A Planning Problem Formulation · p. 21

B STRIPS Formulation

  • In STRIPS, predicates describe object properties and relations that make up a state.For example, on(A, B) represents object A being on top of object B.Source: B STRIPS Formulation · p. 21
  • STRIPS actions specify preconditions for applicability and effects on the state after execution.For move(A, B, C), the example requires on(A, B) and clear(C), then yields on(A, C) and clear(B).Source: B STRIPS Formulation · p. 21
  • Repeatedly applying possible actions builds a directed state-transition graph, expanded until the goal is reached or no actions remain.Source: B STRIPS Formulation · p. 21

C Tasks in Case Study

The case study describes planning tasks involving cocktail preparation, object transport, tire replacement, tile painting, and block manipulation. A separate prompt template asks for PDDL domains with predicates, actions, and a natural-language explanation before the code.

C Tasks in Case Study

  • Barman requires sequencing cocktail ingredients, tools, and glassware while managing hands and object states.The goal is to prepare the specified cocktail and contain it in a shot glass.Source: C Tasks in Case Study · p. 22
  • Gripper tests moving balls between rooms while managing gripper capacity, robot location, and pickup and drop actions.Source: C Tasks in Case Study · p. 22
  • Tyreworld involves replacing and inflating tires, fastening hub nuts, and managing tools and spare tires.The passage also describes navigating uncertainty and reaching a destination with intact, inflated tires.Source: C Tasks in Case Study · p. 22
  • Floor-tile requires painting tiles under movement, occupancy, and color constraints, with different action costs.Moving up costs 3; moving down, right, or left costs 1; painting costs 2 and changing color costs 5.Source: C Tasks in Case Study · p. 22
  • Termes tests block manipulation under adjacency, height, and block-availability constraints, with the robot carrying one block at a time.Source: C Tasks in Case Study · p. 22

D Prompt Template for Chain-of-Thought

  • The prompt template requests predicates and actions, a step-by-step natural-language explanation, and then concrete PDDL domain code.It instructs the model to list preconditions and effects separately and give each predicate a unique name with explicit parameters.Source: Prompts for Our Methods · p. 23

E Generated Domains

The appendix presents PDDL domain and problem examples across several planning benchmarks, along with example plans and their costs.

E Generated Domains

  • The Barman example includes shot-and-shaker actions and a cocktail plan with cost 36 (unit cost).The plan mixes and serves three cocktails.Source: E Generated Domains · p. 24
  • The Blocks World example encodes pickup, putdown, stack, and unstack actions and gives a 24-step unit-cost plan.The plan passage reports a cost of 24 (unit cost).Source: E Generated Domains · p. 25
  • The Termes domain encodes movement between neighboring positions with height-dependent rules, plus block creation, placement, removal, and destruction.The example problem specifies a maximum height of 3 and a grid-based initial and goal state.Source: E Generated Domains · p. 26
  • The FloorTile example defines robot movement and painting actions, with a plan reported at cost 54 (general cost).The domain includes color-changing and painting actions with stated costs.Source: E Generated Domains · p. 27
  • The Tyreworld example represents tire-changing actions and provides a plan with cost 19 (unit cost).The plan replaces and inflates a tire, then returns tools to the boot.Source: E Generated Domains · p. 28

F Prompts for LLM-as-Planner Methods

The LLM-as-planner prompt describes a Termes robot task and asks for an optimal behavior sequence and its cost.

F Prompts for LLM-as-Planner Methods

  • The prompt specifies robot moves, block placement and removal, and block creation and destruction, with action-specific constraints.For example, placement requires a carried block and equal current heights at the robot and destination.Source: Prompts for o1 on Termes · p. 29
  • The planning instance uses a 4-by-3 grid, starts the robot at the depot, and sets the maximum block height to 3.The goal is height 3 at position pos-1-2, with no unplaced block at the end.Source: Prompts for o1 on Termes · p. 29
  • The prompt requests an optimal sequence of behaviors and the final optimal cost.It also instructs the solver to check the unplaced-block rule at each step.Source: Prompts for o1 on Termes · p. 29

G State-based graph for Termes

Figure 6 depicts a Termes planning graph with explicit state transitions during planning.

G State-based graph for Termes

H The Prompt of Our Methods on Termes

The Termes prompt asks for PDDL domain code and a preliminary explanation of its predicates and actions.

H The Prompt of Our Methods on Termes

  • The prompt asks for a natural-language thought explaining each variable and the domain code step by step before the PDDL.Its template separates the thought from the concrete domain code.Source: Prompts for Our Methods on Termes · p. 31
  • The prompt instructs the model to list individual preconditions and effects separately and give each predicate a unique name.Predicate parameters must also be explicitly defined.Source: Prompts for Our Methods on Termes · p. 31
  • The prompt says to ignore information deemed unhelpful and to infer predicate and action names when the description omits them.It supplies a Termes natural-language description and an example problem in PDDL.Source: Prompts for Our Methods on Termes · p. 31

I Human in the Loop Experiment

The human-in-the-loop experiment involved AI and robotics graduate students using AI and manual coding to create PDDL for the Termes domain. Their work exposed difficulties in producing precise, semantically meaningful domains and underscored the need for automated synthesis.

Loading 2502.04728v2…