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:
- Exact Newton requires storing and multiplying dense $D \times D$ Jacobian matrices, leading to $O(D^3)$ computational costs.
- Diagonal quasi-Newton is faster ($O(D)$) but ignores interactions between state dimensions, often leading to poor convergence when variables are strongly coupled.
- 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.
Datasets
The methods were evaluated on three distinct types of nonlinear systems:
- 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.
- 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.
- 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.
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