Understanding Rollout Error in Graph World Models
06:00 · June 29, 2026 · arXiv cs.AI RSS
World models are often used for planning by rolling learned dynamics forward. Many planning environments, however, are not vectors or images; they are graphs of agents, tools, skills, routes, and dependencies. In these settings, a local prediction error may stay local or spread through the graph, and the failure mode changes again when edges are predicted rather than fixed. This paper studies long-horizon rollout error in Graph World Models (GWMs). We formulate a unified fixed-edge and dynamic-edge GWM framework with action nodes for node-, edge-, and graph-level decisions. We develop graph-valued rollout bounds that separate topology-induced amplification from model-induced amplification, and we introduce a joint node-edge operator for dynamic-edge rollouts. Guided by the analysis, we propose Error-Aware GWM, which combines spectral regularization, rollout consistency, and critical-node weighting. Across synthetic topologies and heterogeneous agent-graph testbeds, rollout error and planning regret grow with horizon, dynamic-edge training is needed when structure evolves, and Error-Aware GWM prevents long-horizon divergence while preserving prediction accuracy. Real-world graph benchmarks clarify the scope of GWMs: they are most useful for dynamic graph rollout and agent planning, while specialized graph models remain strong on static or sparse prediction tasks.
Summary
Graph World Models extend conventional world-model approaches to environments whose states are naturally represented as graphs, with nodes carrying features and edges encoding relations that may remain fixed or evolve over time. In such settings, autoregressive rollouts for planning allow small local prediction errors to compound, and the amplification depends on both the underlying topology and the model’s parameters rather than on a single scalar Lipschitz factor.
The authors place fixed-edge and dynamic-edge rollouts inside a single state-action transition framework. For fixed-edge models they derive a graph error amplification factor that factors into a topology term governed by the spectral radius of the adjacency matrix and a model term given by the product of layer spectral norms. For dynamic-edge models they introduce a joint node-edge error operator that tracks the mutual influence between feature prediction errors and structure prediction errors, showing how an edge mistake can alter subsequent message passing and thereby accelerate divergence.
Motivated by these bounds, the paper presents Error-Aware GWM, a training objective that adds spectral regularization, rollout-consistency terms, and critical-node weighting. Experiments across synthetic topologies and heterogeneous agent-graph environments confirm that rollout error and planning regret increase with horizon, that dynamic-edge training becomes essential once the graph structure itself changes, and that the proposed objective improves long-horizon stability while preserving one-step predictive accuracy. The analysis therefore delineates the conditions under which graph world models remain reliable for extended planning and the topological regimes in which they are prone to failure.
Why it matters
This research provides foundational advancements in Graph World Models, highly relevant for Dutch AI researchers working on complex multi-agent systems, logistics, and network planning. The theoretical bounds and proposed Error-Aware GWM offer actionable methodologies for improving long-horizon planning.
