OmniST: Topology-Invariant Spatiotemporal Forecasting with Coverage Guarantees for Unseen Sensors

Spatiotemporal forecasting models have long been trapped by a structural assumption: the number of sensors is fixed. Graph convolutional networks require a predefined adjacency matrix, and model weights are tied to the node count at training time—once deployed to a new sensor location, the entire system fails to produce any output. OmniST attempts to tear down this wall: its computation has zero dependence on the number of nodes, and it can be combined with inductive split-conformal calibration to produce distribution-free prediction intervals with guaranteed coverage at arbitrary locations (including sensors never seen before).

Where Topology Invariance Comes From

OmniST's core design revolves around three components. First, coordinate-based tokenization: sensors are no longer encoded as an index into a fixed vocabulary but instead represented by representations generated from their geographic coordinates. Second, k-nearest-neighbor attention, which dynamically constructs adjacency based on latitude and longitude during each forward pass rather than relying on a graph structure fixed during training. Third, per-node temporal processing, using a bidirectional GRU to independently model each sensor's time series.

The combined effect of these three steps: the model's computation graph is unaware of the total number of nodes N. Adding or removing sensors does not change the weight shapes or break the learned spatial relationships. For scenarios that require frequent adjustments to the monitoring network—such as expanding air quality stations or temporary deployments—this property means the model can continue to be used in place without retraining.

Graph Convolutional Networks (GCN) and Inductive Learning

Traditional graph convolutional networks model the sensor network as a graph: nodes are sensors, and edges represent spatial proximity or correlation. Each layer of a GCN aggregates neighbor information through an adjacency matrix, and the dimensions of both the adjacency matrix and the weight matrices are tied to the number of nodes N. This means the model "memorizes" a specific sensor layout during training; once the node set changes, the weights cannot be reused and the model can only be retrained. This setting is called transductive learning.

In contrast, inductive learning requires the model to directly reason about nodes unseen during training. OmniST bypasses the fixed adjacency matrix through coordinate tokenization and dynamic k-nearest-neighbor attention, decoupling the computation graph from N and thereby gaining inductive capability. This distinction is key to understanding OmniST's deployment flexibility: it is not simply "switching to a different graph structure" but fundamentally removing the graph structure's dependence on the number of nodes.

Prediction and Uncertainty at Unseen Sites

Beyond prediction accuracy, what is more noteworthy about OmniST is how it handles uncertainty. Inductive split-conformal calibration provides finite-sample coverage guarantees for prediction intervals, and this guarantee still holds when sensors are added or removed. This contrasts with most deep learning methods, which typically provide only point predictions or rely on Bayesian approximations without strict coverage commitments.

On real air quality data from Delhi (37 stations), OmniST's PM2.5 predictions degrade only slightly after removing a large number of stations. Inductive predictions at unseen sites outperform nearest-neighbor interpolation and a learned kriging GNN (IGNNK), and—this is the key difference—only OmniST carries coverage guarantees.

According to the paper, coverage guarantees remain at high levels under random node dropout across four real datasets and three domains (Delhi and Beijing air quality, NOAA GHCN weather, Caltrans PeMSD7-M traffic); they also hold at the full sensor scale of PeMS-BAY.

Split Conformal Prediction and Coverage Guarantees

Conformal prediction is a distribution-free uncertainty quantification framework. Its core idea is: use a held-out calibration set to compute nonconformity scores (such as absolute residuals), then take an appropriate quantile of these scores as the half-width of the prediction interval. Under the exchangeability assumption, intervals constructed this way have finite-sample marginal coverage guarantees for new test points—for example, a 90% interval covers at least 90% of true values over the long run, without relying on any distributional assumptions.

"Split" means the calibration set is separated from the training set to avoid coverage failure caused by overfitting; "inductive" means the calibration procedure can be performed independently for new nodes without retraining the model. This is precisely the mechanism source that enables OmniST to maintain coverage guarantees when sensors are added or removed. In contrast, Bayesian neural networks or MC Dropout provide approximate uncertainty lacking such rigorous frequentist guarantees.

Fixing Temporal Drift

Static conformal calibration has a known weakness: over time, prediction intervals gradually under-cover. OmniST's solution is a rolling adaptive conformal estimator that dynamically adjusts interval width based on recent residuals. The cost is wider intervals, but the target coverage rate is restored—the overall and late-stage coverage data in the paper support this trade-off. For long-term deployed monitoring systems, this is closer to practical needs than one-time calibration.

Adaptive Conformal Inference

Static conformal calibration assumes the data distribution does not change over time, but real monitoring data often exhibits drift (such as seasonality, pollution events, sensor aging), causing the calibration residual distribution to shift and intervals to gradually under-cover. Adaptive conformal inference addresses this by updating calibration quantiles online: each time a new residual is observed, the current quantile is adjusted according to a learning rate, so that long-term coverage converges to the target level.

The rolling adaptive estimator adopted by OmniST belongs to this family of methods. Its cost is that interval width increases with residual fluctuations in exchange for restored coverage. For long-term deployed monitoring systems, this trade-off of "prefer wider intervals to guarantee coverage" is more aligned with practical operational needs than one-time static calibration.

What This Means

OmniST's value lies not in beating some benchmark's MAE but in changing the deployment contract of spatiotemporal forecasting models. Traditional GCN-like methods require "first determine the sensor set, then train the model"; OmniST allows "model first, sensors added as needed," and uncertainty quantification remains valid as nodes change. For domains where sensor topologies frequently change—such as urban sensing, environmental monitoring, and transportation networks—this is a pragmatic direction.

Of course, topology invariance is not without cost. The parallel efficiency of coordinate tokenization and per-node GRUs, and the computational overhead of k-nearest-neighbor attention at large node scales, are all issues to weigh during engineering deployment. The largest scale covered by the paper is currently the full sensor set of PeMS-BAY; performance at larger scales remains to be seen.

One-line Summary

OmniST frees spatiotemporal forecasting models from a fixed number of sensors and provides prediction intervals with coverage guarantees at arbitrary locations.

Paragraph Summary

OmniST addresses the structural flaw of spatiotemporal forecasting models that rely on a fixed number of sensors by proposing an architecture with zero dependence on node count. Through coordinate-based tokenization, dynamic k-nearest-neighbor attention, and per-node bidirectional GRUs, the model weights are decoupled from the total number of nodes, enabling direct predictions at sensor locations unseen during training. Combined with inductive split-conformal calibration, OmniST provides distribution-free finite-sample coverage guarantees for predictions at arbitrary locations, and these guarantees hold when sensors are added or removed. On Delhi air quality data, predictions at unseen sites outperform nearest-neighbor interpolation and IGNNK, while additionally carrying coverage guarantees. A rolling adaptive conformal estimator further fixes the under-coverage of static calibration over time, at the cost of wider intervals. Coverage guarantees are validated on four datasets, three domains, and the full scale of PeMS-BAY.