World Models in Pieces: Structural Certification for General Agents
2026-06-23 • Artificial Intelligence
Artificial Intelligence
AI summaryⓘ
The authors explain that in very large and complex environments, intelligent agents can't perform perfectly everywhere; instead, their skills are specialized in certain areas. They show that traditional methods for evaluating these agents don't clearly separate important mistakes from unimportant ones. To fix this, the authors create a new way to check which parts of the agent's understanding are reliable, focusing on small pieces of its internal model. They provide methods to identify and guarantee where the agent can make good long-term plans, helping to safely use these agents in practice.
general agentsworld modelworst-case analysisgoal-conditioned performancetransition-local frameworklong-horizon planningcompositional goalserror boundstructural certificationsmall-delta regime
Authors
Yikai Lu, Yifei Wu, Xinyu Lu, Tongxin Li
Abstract
In the big-world regime, agents cannot be universally capable and their ability is inevitably specialized across a world model in pieces. Consequently, standard uniform guarantees fail to distinguish between the understanding of critical bottlenecks and irrelevant failures. We first formalize this limitation by proving that general agents are not universal, rendering standard worst-case analysis uninformative. To overcome this, we introduce structural certification, a transition-local framework that maps bounded goal-conditioned performance to entry-wise guarantees on the agent's internal world model. Our main contribution is constructive. We provide algorithms that filter specific transitions using deep compositional goals and prove that a general agent on these goals has a structural world model with a $\mathcal{O}(1/n) + \mathcal{O}(δ)$ error bound. Conversely, this bound is tight in the small-$δ$ regime, whose existence is explicitly guaranteed by our certification. These results enable the certifiable deployment of general agents by localizing the specific transitions where long-horizon planning is reliable.