Forecasting traffic on a road network, or load on a power grid, means predicting a whole distribution over many coupled sensors, not one number per sensor. One principled way to do this is to keep a cloud of "particles": many guesses of the hidden state of the whole network. These guesses are pushed toward what the data supports and kept apart so the cloud stays spread out. The best existing version of this idea for traffic graphs moves the particles along a smooth path from prior to posterior. It reports the best probabilistic scores on California traffic benchmarks. Its update, however, requires inverting matrices whose size grows with the number of sensors, so the cost grows as $N^3$. It also has no explicit force that keeps particles from bunching together. The standard fix for bunching is Stein variational gradient descent, which adds a pairwise repulsion between particles. That fix is known to break down as dimension grows, because the repulsion fades and the cloud collapses. A whole road network is exactly that high-dimensional setting.
We propose to measure repulsion locally on the sensor graph. Each sensor's state is compared across particles only together with its immediate graph neighbours. The repulsion then acts in a space whose size does not grow with the network. The posterior update after each new observation costs time linear in the number of sensors. Our claim is that this keeps the particle cloud honestly spread on networks where both global repulsion and matrix-inverting particle flows fail. We expect the gain to show up as better coverage of prediction intervals and better scores on aggregated network-wide quantities, not just per-sensor accuracy.
Core Claim
The road or adaptive graph that spatio-temporal forecasters already use supplies a conditional-independence structure. Message-passing particle inference was designed to exploit structure of this kind and has never been applied to a dynamic forecaster. If the filtering update of a graph recurrent state-space model replaces the matrix-inverting particle flow with Stein updates that use graph-local kernels, three things should follow. Per-step cost drops from $O(N^3)$ to roughly $O(M^2 N k)$, for $M$ particles, $N$ nodes and average neighbourhood size $k$. The repulsive force stops decaying with network size. Predictive calibration improves, especially for multi-node quantities such as total corridor flow, at equal or better point accuracy. The ingredient doing the work is repulsion measured in a graph neighbourhood. The experiments isolate it directly by comparing against an otherwise identical local update with the repulsion term removed.
Relation to Prior Work
RNN with Particle Flow for Probabilistic Spatio-temporal Forecasting is the direct predecessor and the method we replace a component of. It treats forecasting as inference in a state-space model whose hidden states evolve through an adaptive graph convolutional GRU. It moves particles from prior to posterior along an ODE to avoid the weight collapse of resampling particle filters. It evaluates CRPS on PeMSD3/4/7/8 and on Electricity, Traffic, Taxi and Wikipedia. We keep its transition model and benchmarks. We change only the posterior update, which in that paper scales cubically in $N$ and contains no repulsive diversity term.
Free-Form Variational Inference for Gaussian Process State-Space Models motivates the non-parametric choice. It statistically rejects Gaussian posteriors for over half of the inducing variables and about a tenth of latent states, and it represents the posterior with sampler particles. It assumes independent state dimensions and is evaluated only on low-dimensional system-identification data. Our proposal targets precisely the cross-node coupling that it drops.
The method itself comes from Stein Variational Gradient Descent, which balances an attraction toward high posterior density against a kernel repulsion between particles. The decisive constraint comes from Message Passing Stein Variational Gradient Descent. That paper proves the repulsion of standard kernels decays with dimension, as $1/\sqrt{D}$ or exponentially. It cures the decay with kernels over Markov blankets, but only for fixed static graphical models. Stein Variational Gaussian Processes shows a global-kernel Stein method working on a large spatio-temporal air-quality dataset, but for interpolation rather than sequential filtering. We read that as evidence the approach is practical, not as a solution to the dimension problem.
Two papers relate particle flows to variational gradient flows but stay low-dimensional or depend on meta-training: Variational Formulation of the Particle Flow Particle Filter and Particle Flow Bayes' Rule. The latter also shows that 256 flow particles beat 8,192 sequential Monte Carlo particles on a 10-dimensional linear system. That result is part of why we do not revisit resampling filters as the main competitor.
On the forecasting side, Beyond Accuracy: Are Time Series Foundation Models Well-Calibrated? supplies two things. First, it supplies the calibration metrics we use: probabilistic calibration error (PCE) and centered calibration error (CCE). Second, it finds that Gaussian output heads damage calibration while quantile and mixture heads do not. It also notes that calibration benchmarks are almost entirely univariate, which is the gap our aggregated-quantity evaluation addresses.
Research Program
The model is the AGCGRU state-space model of the particle-flow paper. Each node $n$ has a hidden state $x_t^n$, and particles $x_t^{(i)}$ for $i=1..M$ describe the whole network. At each time step, every particle is first propagated through the learned transition with process noise. When the observation $y_t$ arrives, each particle then takes $K$ Stein steps instead of an ODE migration. The update for node $n$ of particle $i$ uses neighbourhood vectors $z^{(j),n} = (x^{(j),n}, x^{(j),\mathcal{N}(n)})$, built from the node and its graph neighbours $\mathcal{N}(n)$ in particle $j$:
$$\Delta x^{(i),n} = \frac{1}{M}\sum_{j=1}^{M}\Big[k_n(z^{(j),n}, z^{(i),n})\,\nabla_{x^{(j),n}} \log \pi_t(x^{(j)}) + \nabla_{x^{(j),n}} k_n(z^{(j),n}, z^{(i),n})\Big].$$
In this update, $\pi_t$ is the unnormalised filtering target: the observation likelihood times the transition density from each particle's own predecessor. The node-$n$ gradient of $\log \pi_t$ depends only on $n$'s neighbourhood, because the graph convolution is local. The kernel $k_n$ is an RBF kernel whose bandwidth is set per node by the median heuristic. Because $z^{(j),n}$ has dimension $d(k+1)$, which is independent of $N$, the repulsion bound from the message-passing paper does not shrink as the network grows.
Training follows the predecessor. We maximise the predictive likelihood of observations under the particle cloud, with gradients through a truncated number of Stein steps to keep memory bounded. Forecasting rolls the posterior particles forward through the transition. We will also test whether applying local repulsion during the unobserved forecast horizon slows the growing overconfidence that autoregressive rollouts are known to show. That part is a secondary question. The core contribution is the filtering update.
The analysis component has two parts. We will derive the per-step cost and memory. We will also check, in a linear-Gaussian graph state-space model where the Kalman filter gives the exact posterior, how marginal and pairwise variances are recovered as $N$ grows. This gives ground truth for the "particles collapse in high dimension" story.
Baselines
The naive reference point is DeepAR, a recurrent network with a parametric output head sampled into independent Monte Carlo paths. On PeMSD3 the particle-flow paper reports DeepAR at CRPS 11.41 (RNN with Particle Flow for Probabilistic Spatio-temporal Forecasting). We will rerun it under our splits rather than copy the number. DCRNN serves as the point-forecast reference, reported at MAE 14.42 on PeMSD3 in the same paper.
The strongest existing method is AGCGRU+flow from that paper, reported on PeMSD3 at MAE 13.79 and CRPS 10.53. For PeMSD4, D7 and D8 we found no reported numerical result on Lacuna, so we will regenerate those numbers with the released configuration. For fairness, our model shares its transition network, its adaptive adjacency, its number of particles and its training epochs. The only difference is the update step. Hyperparameters, including our $K$ and bandwidth scale, get the same tuning budget on validation data. Beating it means lower CRPS on all four PeMS datasets at matched particle count, with MAE no worse than its reported value. It also means substantially lower wall-clock time per filtering step once $N$ is in the thousands.
Three ablations isolate the ingredient. Global SVGD uses one RBF kernel over the whole network state, which is the setting the theory predicts will collapse. The local attraction-only variant drops the repulsion term from the equation above, leaving gradient steps per particle. A diagonal particle flow approximates the predecessor's ODE with per-node inverses only, in the spirit of the diagonal approximate Newton direction in Wasserstein Gradient Boosting. The diagonal flow is the cheapest way to remove the $N^3$ cost without our idea. As an expressive-head generative baseline we include autoregressive flow matching from Probabilistic Forecasting via Autoregressive Flow Matching on Electricity, Traffic and Solar. That paper claims the best CRPS on Electricity, Exchange and Solar, but we found no reported numerical CRPS value on Lacuna, so it will be rerun.
Why not just…?
Why not just draw more independent sample paths from a strong generative forecaster? Independent samples from autoregressive flow matching or DeepAR give marginal spread. Their cross-node coupling, however, is only as good as the conditional model. They do not maintain a posterior over hidden state that is corrected by each new observation. This is a real threat on non-graph datasets, where flow matching may simply be the better model. The experiment that settles it is the aggregated-quantity evaluation. If CRPS on summed corridor flow and pairwise interval coverage are no better for our method than for flow matching at matched compute, the posterior machinery is not earning its cost.
Why not just diagonalise the existing particle flow? That removes the cubic cost with a minimal change and is the alternative most likely to match us. Nothing in the file shows it failing. The difference is that a diagonal flow has no mechanism keeping particles apart. It should therefore underestimate variance more as $N$ grows. The linear-Gaussian scaling experiment, where exact variances are known, will show whether this happens. If the diagonal flow recovers variances as well as local Stein does, we will report that and drop the claim that repulsion is necessary.
Why not just recalibrate quantiles after the fact? Post-hoc recalibration can fix per-sensor PCE cheaply. The calibration study shows that expressive output heads already reach PCE near or below 5% in the univariate setting (Beyond Accuracy). But per-node recalibration cannot repair a wrong joint dependence across sensors. We will apply the same per-node isotonic recalibration to every method and report results before and after. Our claim survives only if the advantage persists on aggregated quantities after recalibration.
Why not just use resampling particle filters or Hamiltonian Monte Carlo? The file documents weight collapse for resampling filters in high dimension. It also reports a 10-dimensional comparison where 256 flow particles beat 8,192 sequential Monte Carlo particles (Particle Flow Bayes' Rule). Hamiltonian Monte Carlo was impractical at a single step taking over ten minutes on the UK air-quality data (Stein Variational Gaussian Processes). We include a bootstrap particle filter only on the synthetic scaling task, as a sanity check of effective sample size.
Proposed Experiments
The first decisive check is synthetic. We build linear-Gaussian state-space models on random geometric graphs with $N$ from 100 to 10,000 nodes, where the Kalman filter gives exact posteriors. We plot the ratio of particle variance to true variance, and the error in neighbour correlations, against $N$. We do this for local Stein, global Stein, the attraction-only variant, the diagonal flow and, up to the size it can run, the full particle flow. The prediction is that global Stein's variance ratio falls with $N$, as the message-passing analysis implies, while the local version stays flat. If the local version also collapses, the core claim is false.
The second check is the real benchmarks. On PeMSD3/4/7/8 we report MAE, CRPS, PCE and CCE at 15, 30, 45 and 60 minutes. We also report CRPS on network-sum and corridor-sum quantities as a test of joint calibration, and wall-clock time and peak GPU memory per step. The reference target is the AGCGRU+flow figure on PeMSD3 (CRPS 10.53, MAE 13.79). On Electricity, Traffic and Solar, where the graph is learned rather than given, we test whether the advantage survives an approximate adjacency.
The third check is horizon behaviour. We track interval coverage as a function of lead time with and without repulsion during the forecast rollout. This asks whether interacting particles slow the overconfidence that grows over long horizons. We treat a negative result here as informative, not fatal, because the main claim concerns the filtering update.
References
- RNN with Particle Flow for Probabilistic Spatio-temporal Forecasting
- Free-Form Variational Inference for Gaussian Process State-Space Models
- Stein Variational Gradient Descent: A General Purpose Bayesian Inference Algorithm
- Message Passing Stein Variational Gradient Descent
- Stein Variational Gaussian Processes
- Variational Formulation of the Particle Flow Particle Filter
- Particle Flow Bayes' Rule
- Beyond Accuracy: Are Time Series Foundation Models Well-Calibrated?
- Wasserstein Gradient Boosting: A Framework for Distribution-Valued Supervised Learning
- Probabilistic Forecasting via Autoregressive Flow Matching