Algebraic World Model: From Exploration to Proofs

Guancheng Pan, Qixin Tan, Yang Yuan, Andrew Chi-Chih Yao

TL;DR

The Algebraic World Model (AWM) is a framework that allows AI agents to reason rigorously about unfamiliar environments by building explicit mathematical models from scratch. By combining interactive exploration with category-theory-guided simplification and Lean 4 formalization, AWM can not only find solutions to complex puzzles but also provide kernel-checked proofs of impossibility—demonstrating why a goal cannot be reached within a given budget, a task where state-of-the-art LLMs currently fail.

What Problem Does This Paper Address?

While AI has made massive strides in automated theorem proving (e.g., using the Lean language), these systems typically operate within "known worlds" where mathematical definitions and rules are predefined. In contrast, an agent dropped into an unfamiliar environment—like a new video game or a scientific frontier—must first identify what the objects are and how the rules work before it can reason about them.

A particularly thorny challenge is proving impossibility. It is one thing for an agent to find a winning sequence (a "witness"); it is quite another to prove that no winning sequence exists (e.g., because a budget is too low or a path is blocked). Proving a negative requires reasoning about all possible legal sequences, even those the agent has never seen.

Methods

AWM follows a three-stage pipeline to turn interaction into formal proof:

  1. Explore & Prototype: The agent interacts with the environment to build a "concept book"—a collection of executable Python hypotheses. These hypotheses are constantly tested and revised against new observations.
  2. Structure & Simplify: This is the "algebraic" heart of the system. AWM uses transformations guided by category theory (specifically projective and inductive limits) to organize fragmented hypotheses into a compact model. For example, it might recognize that four different button mechanisms are actually specific instances of a single "permutation" rule.
  3. Formalize & Prove: The simplified model is translated into Lean 4. Because the model is now a formal mathematical object, the agent can use it to construct machine-checked proofs. It proves reachability by providing a witness and impossibility by finding invariants or calculating cost lower bounds.
Figure 1: AWM’s three-stage pipeline: interactive exploration builds a provisional executable model, algebraic transformations reveal and simplify its structure, and Lean 4 formalization enables certified proofs of reachability or impossibility.

The authors also introduce the concept of a Sufficient Cover: a theoretical guarantee that if a learned model correctly reproduces the environment's optimal winning sequences, an impossibility proof in the model will hold true for the actual environment.

Datasets

The researchers evaluated AWM on two primary benchmarks:

  • ARC-AGI-3: A suite of 25 public games (183 levels) designed to test general intelligence through visual reasoning tasks where rules are not provided upfront.
  • sc25 (Sealed Variants): The authors created custom, "impossible" variants of the game sc25. In these levels, the action budget is set exactly one unit below the minimum cost required to win, specifically to test the agent's ability to prove impossibility.

Key Insights and Ideas

  • Category Theory as Compression: By treating object types and rules as limits and colimits, AWM can merge redundant rules and identify shared structures. This makes the resulting models more interpretable and significantly shortens the logic required for proofs.
  • Model-Relative Impossibility: AWM establishes "model-relative" impossibility. Even if the model isn't a perfect replica of the world, if it is a "sufficient cover," its proofs are valid for the real world.
  • Proof Dependencies for Debugging: When a proof fails to match the real world (e.g., the agent proves a level is impossible, but then finds a way to win), the explicit dependencies in the Lean proof allow the agent to trace the error back to a specific faulty rule in its model.
  • Efficiency through Formalization: AWM doesn't just clear levels; it does so with extreme efficiency. Its certified winning trajectories used only 43% of the actions taken by the human baseline.
Figure 2: Four transformations guided by projective and inductive limits, applied to object types and rules. Dashed boxes mark removed components and bold boxes mark introduced components; arrows indicate relationships between components. Generalization uses r(θ), and an instance is written r(θi); specialization makes distinctions explicit through case-specific types or parameters.

Key Results

  • ARC-AGI-3 Performance: AWM cleared all 25 games with a score of 99.9, outperforming standard LLM baselines like Claude 3.5 Opus and GPT-4o (Astra) when they lack the AWM framework.
  • Impossibility Proofs: On the sealed sc25 levels, AWM produced 6/6 kernel-checked impossibility proofs. In contrast, Claude Opus and GPT-6 Astra produced zero proofs across twelve baseline runs, often guessing incorrect minimum costs.
  • Generalization: The learned models generalized remarkably well. In the game lp85, the model predicted unseen tile layouts with 99.95% accuracy and correctly rejected transitions where game mechanics were secretly altered.

Limitations and Future Work

  • Discrete and Observable: The current framework is demonstrated on environments with discrete actions and immediate, observable feedback (like grid-based puzzles).
  • Hidden State and Stochasticity: The authors note that environments with significant hidden states, delayed feedback, or random (stochastic) dynamics remain to be tested.
  • Scaling: While category theory provides a robust mathematical foundation, scaling these algebraic transformations to much larger, more complex "worlds" is an ongoing challenge.

In summary, AWM moves AI beyond simply "guessing" solutions to "understanding" the underlying mathematical structure of an unknown world, enabling a level of rigorous, certified reasoning previously reserved for well-defined mathematical domains.

Summary updated

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.
BibTeX
@misc{pan2026algebraic,
  author = {Guancheng Pan and Qixin Tan and Yang Yuan and Andrew Chi-Chih Yao},
  title = {{Algebraic World Model: From Exploration to Proofs}},
  year = {2026},
  eprint = {2610.40503},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.40503},
}
Figure