Predictability Enables Parallelization (arxiv.org)

Researchers show that the ability to parallelize evaluation of nonlinear state-space models hinges on the system’s predictability. Building on optimization-based parallel evaluation methods like DEER and DeepPCR, the paper proves a tight link between a system’s sensitivity to small state perturbations and the conditioning of the corresponding parallel optimization problem. For systems where small perturbations have limited downstream effect ("predictable" dynamics), the optimization is well-conditioned and the full state trajectory can be recovered in O((log T)^2) time (T = sequence length), a dramatic speedup compared with the usual O(T) sequential rollout. By contrast, chaotic or highly sensitive systems yield exponentially worsening conditioning with sequence length, so parallel optimization converges too slowly to be practical. Technically, the work characterizes predictability as the key quantity controlling the number of optimization steps required, and proves that good predictability guarantees uniformly good conditioning while unpredictability implies exponential degradation. The authors validate these theoretical results with extensive experiments and provide concrete guidance on when to expect large parallelization gains. The upshot for the ML community: design and select state-space models (or architectures and training regimes) that limit sensitivity to perturbations if you want to exploit parallel, optimization-based evaluation on modern hardware.