Understanding Rollout Error in Graph World Models
Xinyuan Song, Zekun Cai · 2026
Read Understanding Rollout Error in Graph World Models by Xinyuan Song, Zekun Cai (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-27780.txt.
Introduction
World models plan by rolling learned dynamics forward. Many real environments are graphs, not vectors or images. Agents, tools, routes, and dependencies form the nodes and links. Errors may stay local or spread through the graph. Xinyuan Song and Zekun Cai study this long-horizon rollout error in 2026. Their framework covers graph world models with fixed edges and with predicted, dynamic edges.
Graph-valued error bounds are derived. They separate topology-caused amplification from model-caused amplification. A joint node-edge operator handles dynamic-edge rollouts. Guided by the analysis, the authors propose Error-Aware GWM. It combines spectral regularisation, rollout consistency, and critical-node weighting. Across synthetic topologies and agent-graph testbeds, error and planning regret grow as the horizon lengthens. Dynamic-edge training proves necessary when structure evolves. Error-Aware GWM prevents long-horizon divergence while keeping prediction accuracy. Static tasks remain a strength of specialised graph models.
Catalog record
| CREATOR | Xinyuan Song, Zekun Cai |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 102 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.27780
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Understanding Rollout Error in Graph World Models Xinyuan Song, Zekun Cai Abstract 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. An anonymized implementation and benchmark suite will be released with the submission. Code is available at https://github.com/Hik289/graph_world_model_accumulative_error.git . 1 Introduction A world model 15 represents environment observations as states and predicts future states conditioned on actions. Modern world models trained on large-scale data 17 ; 16 ; 18 ; 11 ; 40 ; 7 have shown strong planning, prediction, and generation capabilities. Most of them, however, are built for vector- or image-like states. They do not directly capture environments whose state is a graph. Such environments are common in agent planning: multi-agent calling trees coordinate distributed task execution 2 , skill graphs encode tool dependencies, and communication networks route actions among interacting entities. Planning in these settings requires reasoning about node states and about how effects travel through relations. The same autoregressive rollout that enables long-horizon planning also creates a risk: prediction errors can compound and degrade downstream decisions 3 ; 22 . Graph World Models (GWMs) address this setting by autoregressively predicting graph states G_{t}=(V,E_{t},X_{t},A_{t}) 12 . Given a learned transition model \mathcal{F}_{\theta}(\hat{G}_{k},a_{k}) , a GWM rolls out \hat{G}_{1},\ldots,\hat{G}_{H} and scores candidate action sequences. Existing work has mostly studied graph foundation models for static graph tasks 29 ; 9 or domain-specific graph planning 45 ; 1 . Feng et al. 12 introduced a unified GWM with action nodes, but their setting focuses on fixed-edge (FE) environments. It remains unclear how GWMs behave under long-horizon rollout error and in dynamic-edge (DE) regimes . Graph structure makes compounding error harder to analyze than in vector-state world models. In vector settings, rollout error is often summarized by a scalar Lipschitz constant. In graph settings, the same local error can behave very differently depending on topology. An error on a chain may stay localized; an error on a hub, dense graph, or high-spectral-radius topology can spread widely, consistent with spectral analyses of graph propagation, graph-network dynamics, and GNN stability 6 ; 5 ; 34 ; 31 ; 8 . The problem is harder when edges are predicted. A node-state error can corrupt future edge prediction, and an edge error can change later message passing. GWM rollout error is therefore not just scalar prediction error; it is a topology-dependent, and sometimes coupled, node-edge dynamical process. Existing rollout-error theory is not designed for graph-structured planning. Standard model-based RL analyses bound compounding error with a scalar Lipschitz constant over a fixed-dimensional state vector 3 ; 22 . This misses three aspects of graph rollouts. First, topology is explicit: for a message-passing GWM, node-error growth separates into a topology term \rho(A) and a model term \prod_{\ell}\|W_{\ell}\|_{2} , where A is the adjacency matrix, \rho(A) is its spectral radius, and W_{\ell} are layer weights. Second, dynamic graphs require coupled error dynamics: node-feature error e^{X}_{k}=\|\hat{X}_{k}-X_{k}\|_{F} and edge error e^{A}_{k}=\|\hat{A}_{k}-A_{k}\|_{F} evolve together rather than through a scalar recursion. Third, rollout error must be tied to planning regret over horizon H . These gaps motivate our graph-valued analysis, which replaces the scalar constant with \widehat{\mathrm{GEAF}}=\rho(A)\prod_{\ell}\|W_{\ell}\|_{2} and uses a joint node-edge operator B for the recursion of (e^{X}_{k},e^{A}_{k}) in dynamic-edge GWMs. We analyze accumulative rollout error in GWMs both theoretically and empirically. The graph error amplification factor \widehat{\mathrm{GEAF}}=\rho(A)\prod_{\ell}\|W_{\ell}\|_{2} separates topology-dependent amplification from the model-dependent spectral norm product. For dynamic-edge GWMs, we introduce a joint node-edge error operator B that captures node-to-node, edge-to-node, node-to-edge, and edge-to-edge propagation. This operator cleanly separates two regimes: fixed-edge (FE) models have no edge-prediction head, so M_{X}=0 and the dynamics reduce to node-only prediction; dynamic-edge (DE) models have an edge-prediction head, so M_{X}>0 and node-edge cross-coupling becomes active. We evaluate the framework on a seven-topology synthetic benchmark with existing GWM baselines, including GCN 24 , MPNN 13 , GPS 32 , and ActionNode GWM 12 . The benchmark includes FE and DE simulators, plus heterogeneous agent-graph testbeds. The results support a regime-dependent view of GWM rollout error. Long rollouts turn small prediction errors into larger planning errors. When graph structure evolves, dynamic-edge training sharply outperforms fixed-edge training, and the learned dynamics exhibit the node-edge coupling predicted by the joint operator. The central empirical point is that GWM stability is not an architecture property alone; it depends on topology, horizon, and rollout regime. We further propose Error-Aware GWM to improve rollout stability on high-spectral-radius graphs. It combines spectral regularization, rollout consistency, and critical-node weighting to control topology-induced amplification while preserving prediction accuracy. Empirically, Error-Aware GWM removes the divergence observed in vanilla GCN rollouts and keeps long-horizon prediction error low. Simpler stabilizers can reduce divergence, but often lose predictive fidelity. This distinction matters: a useful graph world model must be stable enough to roll out and accurate enough for those rollouts to support planning. Our contributions are summarized as follows: • Unified GWM framework with FE/DE instantiations (Section 3 ). We formulate graph-structured agent planning as state-action-transition modeling and support both fixed-edge and dynamic-edge rollouts. • Topology-aware rollout error theory (Section 4 ). We develop graph-valued error bounds that account for topology-dependent amplification and node-edge coupling during autoregressive rollout. • Error-Aware GWM for stable planning (Section 6 ). We introduce a training objective that combines spectral control, rollout consistency, and critical-node weighting to improve long-horizon stability. • Evaluation across synthetic and agent-graph settings (Section 7 ). We test the framework across diverse graph topologies, rollout regimes, and agent-graph environments to study when GWMs are stable or unstable. • Scope analysis on real-world benchmarks (Section 7.7.1 ). We evaluate GWMs beyond controlled synthetic dynamics and clarify their practical boundary relative to standard graph methods. 2 Related Work World models for planning. World models have been widely studied in model-based reinforcement learning, where a learned dynamics model is used to simulate future trajectories for planning or policy learning. A central challenge is compounding error: small one-step model errors can accumulate over long rollouts and degrade decision quality. Asadi et al. 3 analyze this effect through Lipschitz continuity of learned transition models. PETS uses probabilistic ensembles and trajectory sampling to propagate uncertainty during model-based planning 11 . Janner et al.