Parallel-in-Time Integration

51 concepts40 papers1 proposal

To simulate a dynamical system—whether it is fluid flowing around an airfoil, a protein folding, or a neural network evolving over time—we rely on differential equations. The standard way to solve these equations is through sequential time-stepping: to find the state of the system at time $t_{n}$, you must first compute its state at $t_{n-1}$.

This creates a strict linear dependency ($O(T)$ complexity). In the era of modern high-performance computing, this dependency is a massive bottleneck. While we can easily parallelize the spatial domain by distributing a grid across thousands of GPU cores, spatial parallelization eventually hits a wall due to communication overhead. As T. Steidten notes in Efficient time step parallelization of full multigrid techniques, spatial decomposition does not address the inherent sequential nature of time-stepping, leaving total execution time bound by the cumulative duration of every individual step's finest-grid computation.

This bottleneck is felt across scientific computing and machine learning alike. In molecular dynamics, Leon Klein et al. explain in Timewarp: Transferable Acceleration of Molecular Dynamics by Learning Time-Coarsened Dynamics that because each state depends strictly on its immediate predecessor to maintain physical accuracy, simple parallelization cannot directly accelerate long-term trajectories. Similarly, in machine learning, Kevin Course et al. show in Amortized Reparametrization: Efficient and Scalable Variational Inference for Latent SDEs that this sequential dependency prevents continuous-time models like Neural Ordinary Differential Equations (ODEs) and Stochastic Differential Equations (SDEs) from effectively utilizing parallel computing hardware like GPUs during training.

The Core Mechanism: Predict and Correct (Parareal)

How can we compute a future state before the past is fully resolved? The fundamental breakthrough of Parallel-in-Time (PinT) integration is to break the timeline into discrete slices and solve them simultaneously using an iterative "predict-and-correct" loop.

The classic paradigm for this is the Parareal algorithm. Imagine we want to solve an ODE over a long time horizon. We divide this horizon into $N$ large time intervals. The algorithm proceeds as follows:

  1. The Coarse Predictor (Sequential): We run a cheap, low-accuracy solver sequentially across the entire timeline. This provides a rough, immediate guess for the starting state of every single time slice. Because the solver is computationally lightweight, this step completes very quickly.
  2. The Fine Corrector (Parallel): Now, because we have an initial guess for the start of every time slice, we can run an expensive, high-accuracy solver on all $N$ slices simultaneously across $N$ different processors.
  3. The Correction Step: We compare the end of each fine slice with the start of the next coarse slice and apply a correction factor to reconcile mismatches at the boundaries.

By iterating this process, the solution rapidly converges to the exact trajectory that a purely sequential fine solver would have produced, but in a fraction of the wall-clock time.

To maximize this efficiency, modern approaches replace traditional coarse solvers with machine learning models that learn the correction terms. For instance, Kamran Pentland et al. in GParareal: a time-parallel ODE solver using Gaussian process emulation use Gaussian Processes (GPs) to learn the correction between cheap coarse steps and expensive fine steps. To make this scale to high-dimensional systems, Massimiliano Tamborrino et al. developed Nearest Neighbors GParareal: Improving Scalability of Gaussian Processes for Parallel-in-Time Solvers, which applies a nearest-neighbor framework to reduce the GP's computational complexity from cubic to log-linear, enabling efficient scaling across hundreds of processor cores.

All-at-Once Space-Time Solvers

An alternative way to bypass the sequential bottleneck is to treat time not as an ordered sequence of steps, but as an additional spatial dimension. This is known as the all-at-once formulation.

Instead of solving for state $x(t_1)$, then $x(t_2)$, we construct a single, massive system of equations that represents the entire space-time volume simultaneously. As Federico Danieli et al. demonstrate in Space-time block preconditioning for incompressible flow, solving the entire timeline simultaneously allows for massive parallel throughput, achieving iteration counts comparable to traditional sequential methods but with vastly superior scalability on exascale architectures.

In the context of machine learning, this all-at-once philosophy allows us to relax the strict ODE constraints during model training. For example, Alessio Quaglino et al. developed SNODE: Spectral Discretization of Neural ODEs for System Identification, which represents state trajectories globally as a series of Legendre polynomials. By optimizing the entire trajectory at once rather than stepping through it autoregressively, they achieve up to a 50x training speedup for Neural ODEs.

Achieving Logarithmic Complexity via Parallel Scans

Can we do even better than iterative correction? For certain classes of problems, we can reduce the temporal complexity from linear ($O(T)$) to logarithmic ($O(\log T)$) by leveraging parallel prefix-sum (or scan) algorithms.

In computer science, a prefix-sum computes the running totals of an array (e.g., transforming $[a, b, c]$ into $[a, a+b, a+b+c]$). While this looks inherently sequential, it can be computed in $O(\log N)$ time on a binary tree of processors, provided that the underlying operation is associative.

The authors of Parallel-in-Time Probabilistic Numerical ODE Solvers (Nathanael Bosch et al.) applied this insight to numerical integration. By reframing ODE simulation as a Bayesian state estimation problem (filtering and smoothing), they showed that the sequential integration steps can be reformulated as an associative filtering operation. This allows the solver to execute across the entire time horizon in $O(\log N)$ steps on modern parallel hardware like GPUs.

This logarithmic speedup has also been unlocked in optimal control theory. Simo Särkkä et al. in Temporal Parallelization of the HJB Equation and Continuous-Time Linear Quadratic Control demonstrated that the Hamilton-Jacobi-Bellman (HJB) equation—which traditionally requires a strict backward-in-time sequential computation—can be parallelized. By defining an associative combination operator for conditional value functions, they reduced the time complexity of solving these control problems from $O(T)$ to $O(\log T)$, opening up real-time applications that were previously computationally restricted to offline settings.

Global and Variational Formulations

Rather than trying to parallelize the discrete steps of a traditional solver, another emerging paradigm argues that we should eliminate step-by-step integration entirely by optimizing global integrals.

This is the core idea behind VF-NODE, proposed by Hongjue Zhao et al. in Accelerating Neural ODEs: A Variational Formulation-based Approach. Instead of using an autoregressive numerical solver to compute states step-by-step during training, the authors replace the solver with a variational formulation based on global integrals. This eliminates both the sequential bottleneck and the error accumulation typical of standard training, accelerating Neural ODE training by up to three orders of magnitude.

Parallelizing Generative AI

The benefits of parallel-in-time integration extend directly to modern generative AI, specifically diffusion models. To generate a single high-quality sample, a diffusion model must solve an ODE or SDE backward in time over dozens or hundreds of sequential steps, creating a notorious latency bottleneck.

To break this bottleneck, Nikil Roashan Selvam et al. introduced Self-Refining Diffusion Samplers: Enabling Parallelization via Parareal Iterations. By adapting the Parareal framework to generative diffusion sampling, they split the generation timeline into smaller temporal blocks that can be processed simultaneously across multiple compute units. This allows researchers to directly trade extra hardware resources (such as multiple GPUs working on a single image) for significantly lower wall-clock generation times, without altering the final numerical solution or sacrificing sample quality.

Key Foundational Work

Efficient time step parallelization of full multigrid techniques (1998) — contributed 4 concept elements to this direction.
Processing Symbols at Variable Speed in DUAL: Connectionist Activation as Power Supply (1999) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_sequential_time_stepping_bottleneck_6a4f89cb,
  title = {sequential time-stepping bottleneck},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sequential-time-stepping-bottleneck/rdr_6a4f89cbd75b4eeeb52b5952de79ebce},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_sequential_time_stepping_bottleneck_6a4f89cb_v1,
  title = {sequential time-stepping bottleneck},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sequential-time-stepping-bottleneck/rdr_6a4f89cbd75b4eeeb52b5952de79ebce/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake