cs.LGNov 10, 2026

Parallel Broyden Methods for Efficiently Evaluating Nonlinear State Space Models

Authors: Ian Christopher Tanoh, Scott W. Linderman

Organizations: Department of Statistics, Stanford University

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.

Figures & tables

Appendix figures & tables21 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Sep 28, 2026

Riccati State Space Models: Non-iterative Parallelization for Nonlinear Sequence Modeling

State space models (SSMs) achieve efficient sequence processing because their affine state updates are closed under composition and can therefore be evaluated with an associative parallel scan. Nonlinear recurrent models can provide richer, state-dependent dynamics, but generally lose this compositional structure: parallel evaluation then requires iterative methods that repeatedly linearize and scan the recurrence. We ask, what state-dependent nonlinear dynamics can be designed to remain exactly composable? We answer by introducing RiccatiSSM, a nonlinear SSM, in which each state dimension follows an input-conditioned Riccati differential equation. Its quadratic state dependence makes the local Jacobian explicitly state-dependent, while its exact per-step flow under piecewise-constant inputs is a Möbius transformation. Since Möbius maps are closed under composition and compose through 2×22\times 2 matrix multiplication, the complete nonlinear state trajectory can be evaluated exactly with a single associative parallel scan, without iterative linearization. We further derive a constrained parameterization that ensures bounded, contractive dynamics, and avoids poles in the fractional-linear state update. Across long-sequence classification, regression, and forecasting tasks, RiccatiSSM achieves competitive predictive performance while reducing runtime by 22−33%22{-}33\% compared to the nonlinear LrcSSM under matched architectures. These results demonstrate that state-dependent nonlinear dynamics can retain exact composability and be evaluated efficiently within a single parallel scan.
Mar 17, 2026

Unifying Optimization and Dynamics to Parallelize Sequential Computation: A Guide to Parallel Newton Methods for Breaking Sequential Bottlenecks

Massively parallel hardware (GPUs) and long sequence data have made parallel algorithms essential for machine learning at scale. Yet dynamical systems, like recurrent neural networks and Markov chain Monte Carlo, were thought to suffer from sequential bottlenecks. Recent work showed that dynamical systems can in fact be parallelized across the sequence length by reframing their evaluation as a system of nonlinear equations, which can be solved with Newton's method using a parallel associative scan. However, these parallel Newton methods struggled with limitations, primarily inefficiency, instability, and lack of convergence guarantees. This thesis addresses these limitations with methodological and theoretical contributions, drawing particularly from optimization. Methodologically, we develop scalable and stable parallel Newton methods, based on quasi-Newton and trust-region approaches. The quasi-Newton methods are faster and more memory efficient, while the trust-region approaches are significantly more stable. Theoretically, we unify many fixed-point methods into our parallel Newton framework, including Picard and Jacobi iterations. We establish a linear convergence rate for these techniques that depends on the method's approximation accuracy and stability. Moreover, we give a precise condition, rooted in dynamical stability, that characterizes when parallelization provably accelerates a dynamical system and when it cannot. Specifically, the sign of the Largest Lyapunov Exponent of a dynamical system determines whether or not parallel Newton methods converge quickly. In sum, this thesis unlocks scalable and stable methods for parallelizing sequential computation, and provides a firm theoretical basis for when such techniques will and will not work. This thesis also serves as a guide to parallel Newton methods for researchers who want to write the next chapter in this ongoing story.
Sep 29, 2026

Non-Commutative Lie-Algebraic State-Space Models: Finite-Division Variety Laws, Semidirect Cascades, and Gradient Saddle Escape

Structured state-space sequence models (SSMs) achieve linear-time inference and logarithmic-time parallel training via associative scans, yet diagonal transitions generate solvable semigroups unable to track non-solvable group words or 3D rigid-body manifolds. We present Non-Commutative Lie-Algebraic State-Space Models (Lie-SSMs), parameterizing recurrent updates on Lie algebra tangent spaces via the matrix exponential. First, using an o-minimal cylindrical flag collar, we establish an unconditional single-layer finite-division criterion for contracting SO(3)SO(3) and SU(2)SU(2) heads, proving odd-prime Sylow abelianity, odd-pp-core centrality, and exponent-30 commutator obstructions excluding S5S_5 in SO(3)m,SU(2)m,SO(3)^m, SU(2)^m, and SO(4)mSO(4)^m while identifying the sharp threshold d∗(S5)=d∗(A6)=5d^*(S_5)=d^*(A_6)=5 in SO(5)SO(5). Second, Depth-2 semidirect and Schreier 22-cocycle cascades resolve S5S_5, 2I≅SL2(F5)2I\cong SL_2(F_5), and Heis(Fp)\mathrm{Heis}(F_p) in O(log⁡T)O(\log T) scan depth, whereas unnormalized contracting coupling collapses exponentially without Directional RMSNorm. Third, we characterize the Θ(εc−1)Θ(\varepsilon^{c-1}) Chen--Magnus--Hall--Witt commutator saddle and 1/∣[G,G]∣1/|[G,G]| coset-centroid dilution, proving generic first-order symmetry breaking at ε=0\varepsilon=0 and teacher-forced local Polyak--Łojasiewicz convergence under dense prefix supervision and factored readouts (99.90%/99.40%99.90\%/99.40\% on S5S_5 at T=128T=128; 100.00%100.00\% on D16D_{16}). Across SE2(3)SE_2(3) Left-Jacobian odometry, Hillis--Steele/Blelloch GPU scans (48.24×48.24\times forward, 20.27×/10.28×20.27\times/10.28\times full-layer speedup at T=2048T=2048), and three 3D IMU benchmarks (UCI HAR, UCI HAPT-PT, and 17-subject REALDISP), Lie-SO(3)SO(3) models reach 95.69%±0.14%95.69\%\pm 0.14\% on HAR, 88.44%±0.83%88.44\%\pm 0.83\% episode logit-vote (83.97%±1.20%83.97\%\pm 1.20\% C3 window in 30-subject 5-fold CV; 87.16%±0.64%87.16\%\pm 0.64\% 9-subject split) on HAPT-PT, and 84.23%±1.00%84.23\%\pm 1.00\% on REALDISP.