Technical Summary: PatchWorld: Gradient-Free Optimization of Executable World Models

1. Problem Statement

Text-agent environments are typically modeled as Partially Observable Markov Decision Processes (POMDPs), where the agent receives only rendered text observations while the simulator's latent state and transition dynamics remain hidden. While recent work has explored using Large Language Models (LLMs) to predict future observations or distill planning knowledge, these approaches often fail to maintain a persistent, inspectable belief state necessary for multi-step simulation and planning.

A central challenge in this domain is indeterminacy under partial observability: finite trajectory logs can be reproduced by many executable programs, ranging from simple lookup tables (memorization) to compact stateful programs that infer latent variables (generalization). Existing code-based world models often sidestep this by predicting the next observation directly or relying on online interaction, lacking an offline mechanism to induce a symbolic belief-state program that is both exact and generalizable. Furthermore, there is a tension between observation fidelity (faithfully reconstructing surface text) and decision utility (providing action-discriminative signals for planning), which prior work has not explicitly addressed as a Pareto frontier.

2. Methodology: PatchWorld

PatchWorld is a gradient-free framework that transforms offline agent trajectories into executable Python world models through counterexample-guided code repair. It treats world-model induction as a generative optimization problem, analogous to Counterexample-Guided Inductive Synthesis (CEGIS).

Core Workflow

1. Evidence Selection: The system selects a contrastive set of transitions from offline trajectories. These transitions are grouped by action signatures (abstracted action types) and outcome signatures (e.g., success, failure, terminal) to ensure the synthesized program covers diverse behaviors rather than just memorizing frequent patterns.
2. Initial Synthesis: An LLM synthesizes an initial executable Python program (BaseWorldModel) implementing a symbolic belief state, transition rules, correction logic, and rendering logic. The program adheres to a fixed interface: init_belief, correct_belief (updates state from observation), predict_belief (updates state from action), and readout_observation (generates text from state).
3. Counterexample-Guided Repair: The synthesized program is replayed against the training/validation trajectories. Prediction failures are converted into concrete counterexamples (input, expected output, actual output).
4. Iterative Optimization: An LLM is prompted with the current program, diagnostic summaries of failure patterns, and the top-16 prioritized counterexamples to propose candidate patches. A patch is accepted only if it improves the formal replay fidelity (lexicographic ordering of failure severity and count) on the full validation set. This "hill-climbing" gate prevents regression on unseen failures.

Variants: Simple vs. Residual

The paper introduces two variants to explore the trade-off between fidelity and utility:

• PatchWorld-Simple: Relies purely on the induced symbolic program. It focuses on learning compact, action-contrastive dynamics.
• PatchWorld-Residual: Augments the symbolic program with a human-specified residual-memory bias. This component tracks recurring, unambiguous textual state signatures (e.g., specific object IDs or template strings) via a train-only cache. It acts as an inductive bias (similar to weight decay) to improve surface reconstruction without replacing the symbolic dynamics used for planning.

3. Key Contributions

1. Identification of Indeterminacy: The paper highlights that under partial observability, finite logs support exact replay without revealing the compact latent-state rules required for generalization.
2. Gradient-Free Induction Framework: PatchWorld introduces a method to use LLMs as symbolic optimizers that synthesize and repair executable belief-state programs offline, producing models that are inspectable and locally repairable.
3. The Fidelity-Utility Frontier: The authors demonstrate a Pareto frontier between observation reconstruction and planning utility. They show that improving surface text fidelity (via residual memory) can sometimes weaken action-discriminative dynamics, and vice versa.
4. Empirical Validation: Across seven AgentGym environments (Maze, BabyAI, TextCraft, Wordle, WebShop, AlfWorld, SciWorld), the framework achieves state-of-the-art performance in both code-based prediction and planning without requiring LLM calls during inference.

4. Experimental Results

The evaluation compares PatchWorld against neural baselines (Word2World, LLM-Direct) and other code-based baselines (WorldCoder, PoE-World).

• Observation Fidelity: PatchWorld-Residual achieves the highest code-based fidelity, reaching a macro Token F1 of 0.69–0.70 and BLEU-4 of 0.49–0.50, outperforming WorldCoder and PoE-World by approximately 6 points. It effectively handles templated environments (e.g., AlfWorld, TextCraft) where exact string matching is critical.
• Planning Utility: PatchWorld-Simple achieves the highest code-based planning score, with a 76.4% macro episode success rate in live one-step lookahead planning. This outperforms PoE-World (69.3%) and WorldCoder (64.4%), and is competitive with LLM-based planners (ReAct at 74.4%, LLM-Direct at 75.8%). Crucially, PatchWorld-Simple achieves this with zero LLM calls during the lookahead prediction phase.
• The Trade-off: The results confirm the existence of a frontier. PatchWorld-Residual has higher fidelity but lower planning success (72.9%) compared to PatchWorld-Simple. The analysis suggests that high surface fidelity does not guarantee the specific action-contrastive signals needed for planning; in some cases, the residual memory's focus on exact text can obscure the structural differences between candidate actions.
• Efficiency: PatchWorld shifts computational cost to offline induction (averaging 17–28 LLM calls per environment for repair) but eliminates the need for LLM calls during inference, significantly reducing token usage compared to direct LLM prompting.

5. Significance and Claims

The paper claims that LLMs can serve as symbolic optimizers, capable of searching, patching, and improving executable symbolic systems that are competitive with implicit neural models.

• Interpretability and Repairability: Unlike black-box neural world models, PatchWorld produces programs where belief updates and transition rules can be inspected, tested, and locally repaired.
• Value Equivalence: The work demonstrates that for agents, a model does not need to be the "best" predictor of the next observation to be the "best" planner. Models can be planning-equivalent (value-equivalent) while diverging significantly on observation likelihood.
• Offline Induction: The framework proves that high-quality world models for text agents can be induced entirely from offline data, avoiding the need for online interaction or supervised fine-tuning of the world model itself during deployment.

The authors remain modest, noting that the induced models are limited to language-based environments and that the interpretability claims rely on program inspection rather than user studies. They acknowledge that while the models are inspectable, they can still encode incorrect rules if the training data is insufficient or biased, necessitating sandboxing and review in high-stakes settings.