Parallel Broyden Methods for Efficiently Evaluating Nonlinear State Space Models

Ian Christopher Tanoh, Scott W. LindermanarXiv 2026 · arXiv

TL;DR

Parallel Broyden methods enable the evaluation of nonlinear state space models with logarithmic parallel depth by using diagonal-plus-low-rank (DPLR) Jacobian approximations. By building these approximations from trajectory secants, the method avoids expensive automatic differentiation and achieves up to 30× speedups over sequential evaluation in complex, high-dimensional tasks.

What Problem Does This Paper Address?

Nonlinear state space models (SSMs)—which include everything from Recurrent Neural Networks (RNNs) and diffusion models to MCMC samplers—are traditionally sequential. To compute the state at time $t$, you must first compute the state at $t-1$. This $O(T)$ dependency prevents these models from fully exploiting modern parallel hardware like GPUs.

Recent research (such as the DEER and DeepPCR frameworks) has reframed trajectory evaluation as a root-finding problem, allowing the use of parallel Newton methods that reduce time complexity to $O(\log T)$ via parallel scans. However, these methods hit a scalability wall:

  1. Exact Newton requires storing and multiplying dense $D \times D$ Jacobian matrices, leading to $O(D^3)$ computational costs.
  2. Diagonal quasi-Newton is faster ($O(D)$) but ignores interactions between state dimensions, often leading to poor convergence when variables are strongly coupled.
  3. Automatic Differentiation (Autodiff) through complex transition maps (like large neural networks) is often prohibitively expensive.

Methods

The authors introduce Parallel Broyden and Accelerated Parallel Broyden, which bridge the gap between expensive exact Newton and overly simple diagonal methods.

  • DPLR Approximations: Instead of dense or purely diagonal Jacobians, they use a Diagonal-Plus-Low-Rank (DPLR) structure. This captures the most important cross-dimensional couplings while remaining computationally lean.
  • Secant-Based Updates: They use Broyden’s method to update Jacobian approximations using only the differences between successive trajectory iterates (secants). This completely bypasses the need for automatic differentiation.
  • Compressed Approximate Scan: A major technical hurdle is that multiplying two DPLR matrices increases the rank of the result. To keep the parallel scan efficient, the authors developed a randomized rank compression technique that "squeezes" the rank back down at each merge step of the scan tree.
  • Theoretical Guarantees: They prove that even with rank compression, the method retains the "finite-step recovery" property—meaning it is guaranteed to find the exact trajectory in at most $T$ iterations.
Table 1: Comparison of trajectory evaluation methods. Sequential is the baseline. All other methods are parallel via parallel scan with O(log T) depth. Parallel Broyden and Accelerated Parallel Broyden (this work) use diagonal-plus-low-rank (DPLR) block approximations with rank at most m.

Datasets

The methods were evaluated on three distinct types of nonlinear systems:

  1. Low-rank RNNs: Synthetic RNNs where the Jacobian structure is known to be DPLR. This included a standard variant and an "MLP-RNN" where the transition function is a deep neural network.
  2. Hierarchical Gibbs Sampling: Applied to the "Eight Schools" problem, a classic Bayesian hierarchical model. This tests the method's ability to handle the global coupling inherent in MCMC.
  3. Denoising Diffusion Models: Using a pretrained Diffusion Transformer (DiT) for image patch denoising (DDIM sampling).

Key Insights and Ideas

  • Convergence is Directional: Traditional analysis looks at the spectral norm of the Jacobian error. This paper shows that what actually matters for convergence is the approximation error along the current trajectory error direction. This explains why low-rank updates are so effective even when they don't capture the full Jacobian.
  • Avoiding Autodiff is the Real Winner: In many modern models (like the MLP-RNN or DiT), the cost of a single autodiff pass is much higher than the cost of the transition function itself. By using secant updates, Parallel Broyden can afford more iterations and still finish faster than methods that require gradients.
  • Rank Compression Works: The randomized compression scheme allows the parallel scan to maintain $O(\log T)$ depth without the rank exploding, and empirically, this compression has almost no negative impact on the number of iterations needed to converge.

Key Results

  • Hierarchical Gibbs Sampling: Accelerated Parallel Broyden was 30× faster than sequential evaluation and significantly outperformed exact Newton, which ran out of memory at high dimensions ($D > 400$).
  • MLP-RNNs: When the transition function is a deep network, Parallel Broyden achieved a 56× speedup over diagonal quasi-Newton because it avoided the massive overhead of differentiating through the MLP.
  • Diffusion Models: On the DiT benchmark, Parallel Broyden was 3.3× faster than diagonal methods. It produced images visually indistinguishable from sequential sampling in fewer iterations than other parallel baselines like Picard iteration.
Figure 1: Low-rank and full-rank RNNs. Left, middle: Standard (∆t = 0.5) and MLP (∆t = 3) low-rank RNNs (R = 3, D = 200), as T varies. In both, iteration counts are ordered as diagonal quasi-Newton > Parallel Broyden > Accelerated Parallel Broyden > Newton. This ordering translates into runtime only when Jacobian information is expensive (MLP-RNN). Right: Full-rank DMF RNN (D = 128, T = 104) as the Broyden rank m varies. Methods without a rank parameter are shown as horizontal lines. Accelerated Parallel Broyden is shown only up to m = 20, as for larger m it becomes numerically unstable or fails to converge. Larger m reduces iterations but increases runtime. We report median iteration counts and runtimes with interquartile ranges over 32 random realizations. Runtimes are computed over realizations that converged within the 1000 iterations budget.

Limitations and Future Work

  • Rank Sensitivity: The method is most effective when the off-diagonal Jacobian structure is truly low-rank. In "unfavorable" cases like full-rank mean-field RNNs, the overhead of the low-rank scan can outweigh the iteration savings.
  • Local Convergence: The current theory is local and conservative. A more robust theory linking secant updates directly to the trajectory error would be a valuable next step.
  • Hardware Constraints: On a single GPU, evaluating many timesteps in parallel can become FLOP-bound. The authors note that the greatest benefits of these parallel methods are realized when using multiple GPUs to amortize the cost of denoiser or simulator evaluations.

Summary updated

Abstract

Nonlinear state space models are typically evaluated sequentially, limiting their ability to exploit modern parallel hardware. Recent work has shown that state space models can be evaluated in parallel by reformulating evaluation as a root-finding problem, which can be solved with a parallel form of Newton's method. However, exact Newton methods require expensive multiplication of dense Jacobian matrices, and quasi-Newton methods based on diagonal approximations, while more scalable, are often slow to converge because they neglect interactions across state dimensions. We introduce a novel quasi-Newton approach based on Broyden's method, which captures coupling terms with diagonal-plus-low-rank approximations to blocks of the Jacobian. We construct the approximations from trajectory secants, avoiding automatic differentiation while retaining the favorable scaling of diagonal approximations and remaining compatible with parallel scan through rank compression. We prove finite-step recovery of the exact trajectory under the compressed scan, and show that convergence is tracked by the compression error and by the block approximation error along the current trajectory error, rather than in spectral norm. Empirically, we show that our method is advantageous when interactions are approximately low rank or when Jacobian evaluation is expensive: on low-rank RNNs, parallel MCMC algorithms, and denoising diffusion models, it converges in fewer iterations than other quasi-Newton methods and is the fastest parallel method when Jacobian evaluation is expensive or state dimensions are large.
BibTeX
@misc{tanoh2026parallel,
  author = {Ian Christopher Tanoh and Scott W. Linderman},
  title = {{Parallel Broyden Methods for Efficiently Evaluating Nonlinear State Space Models}},
  year = {2026},
  eprint = {2611.13523},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.13523},
}
Figure