Algebraic World Model: From Exploration to Proofs
Abstract
AI has made remarkable progress in mathematics, solving challenging problems with machine-checkable proofs in Lean, yet typically relying on predefined mathematical definitions and formal specifications. This raises a natural question: can it reason rigorously about an unknown world? We introduce the Algebraic World Model (AWM), a framework that turns interaction with unfamiliar environments into explicit mathematical models supporting formal reasoning. AWM explores the environment and develops executable Python hypotheses, continually testing and revising them against observations. It then structures these hypotheses into typed objects and shared rules, simplifies their structure through category-theory-guided transformations, and formalizes the resulting model in Lean 4 to prove reachability and impossibility. AWM can formally prove that a goal is unreachable, even beyond explored trajectories. On two impossible game levels, it constructs closed, kernel-checked Lean proofs excluding every legal winning sequence in all six runs, while Claude Opus 5.5 and GPT-6 Astra, equipped with coding tools, produce none in twelve baseline runs. Four of AWM's six initial bounds are correct, compared with one for Opus 5.5 and none for GPT-6 Astra; given only feedback that a cheaper win exists, AWM revises its rules and constructs new proofs, reaching six of six correct bounds. Moreover, AWM produces interpretable mathematical models whose rules can be inspected and tested step by step. Across all 25 public ARC-AGI-3 games, these models enable Lean to replay the winning trajectories of all 183 levels and generalize beyond observed play, predicting unseen transitions and detecting changes in game mechanics. With Claude Opus 5, AWM clears all levels with a score of 99.9, while its certified winning trajectories use only 43% of the human baseline's actions.
The following analysis is generated by AI and may contain errors. It is separate from the authors’ abstract and is not peer review.
Research summary
The paper presents a novel framework, AWM, that enables AI agents to learn algebraic world models from interaction and use them to construct formal proofs of reachability and impossibility in Lean 4. By combining empirical exploration with category-theory-guided model simplification and kernel-checked formal verification, AWM achieves state-of-the-art performance on ARC-AGI-3 and demonstrates a unique capability to provide rigorous, interpretable reasoning about unknown environments, marking a significant advancement in the integration of machine learning and formal methods.
Methodology
The paper introduces the Algebraic World Model (AWM), a framework that bridges empirical exploration and formal verification. The methodology is structured in three stages: (1) Explore & Prototype, where an LLM agent interacts with an environment to generate executable Python hypotheses; (2) Structure & Simplify, where these hypotheses are organized into typed objects and rules using category-theory-guided transformations (limits/colimits) verified in Lean; and (3) Formalize & Prove, where the model is formalized in Lean 4 to prove reachability or impossibility. The use of category theory to guide the simplification of world models is a creative and rigorous approach to ensuring that the learned model preserves the logical structure of the environment. The "sufficient cover" definition provides a theoretical basis for transferring proofs from the learned model to the actual environment, which is a significant methodological contribution.
Results & evaluation
The experiments are conducted on ARC-AGI-3, a challenging benchmark for abstract reasoning. The results are strong: AWM achieves a score of 99.9, outperforming baselines like Claude Opus 5.5 and GPT-6 Astra in both game clearing and, crucially, in constructing formal proofs of impossibility. The paper demonstrates that AWM can produce kernel-checked Lean proofs that exclude all legal winning sequences for impossible levels, a capability the baselines lack. The generalization tests, where frozen models predict unseen transitions and detect mechanic changes, further validate the robustness of the learned algebraic structures.
Reproducibility
The paper provides a high level of reproducibility by releasing an interactive website with models, tests, Lean proofs, and links to official replays. The inclusion of the Lean model for the running example (lp85) in the supplementary materials, along with scripts for building and auditing axioms, allows for independent verification of the formal proofs. The explicit statement that all numbers come from script outputs over recorded runs, rather than model-generated text, enhances trust in the results.
Limitations
The primary limitation is the scope of the environments tested. AWM is demonstrated on ARC-like environments with discrete actions and immediate, observable feedback. The authors acknowledge that richer hidden states, delayed feedback, and stochastic dynamics remain untested. Additionally, the reliance on LLMs for the initial hypothesis generation and exploration phase means that the system's performance is bounded by the capabilities of the underlying LLM. The "sufficient cover" condition, while theoretically sound, requires careful verification in practice to ensure that the learned model indeed covers the optimal winning sequences of the environment.
Broader impact
This work has significant implications for the field of AI, particularly in the areas of formal methods, automated theorem proving, and agent-based reasoning. By enabling AI systems to reason rigorously about unknown worlds and produce machine-checkable proofs, AWM paves the way for more trustworthy and interpretable AI systems. The integration of category theory with machine learning offers a new paradigm for structuring and simplifying learned models, which could be applied to other domains requiring rigorous reasoning. The ability to prove impossibility, not just reachability, is a crucial step towards AI systems that can provide complete and reliable solutions to complex problems. The paper presents a novel framework, AWM, that enables AI agents to learn algebraic world models from interaction and use them to construct formal proofs of reachability and impossibility in Lean 4. By combining empirical exploration with category-theory-guided model simplification and kernel-checked formal verification, AWM achieves state-of-the-art performance on ARC-AGI-3 and demonstrates a unique capability to provide rigorous, interpretable reasoning about unknown environments, marking a significant advancement in the integration of machine learning and formal methods.
Author of this paper? Send a correction.