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
Method
Block approximation At(i)
Work
Memory
Uses Autodiff
Sequential
—
O(TD2)
O(D)
No
Newton [ 18 , 19 ]
At(i)=∂xt−1∂ft(xt−1(i))
O(TD3)
O(TD2)
Yes
Diagonal quasi-Newton [ 21 ]
diag(At(i))
O(TD)
O(TD)
Yes
Parallel Broyden (this paper)
Dt(0)+Ut(i)Vt(i)⊤ , rank≤m
O(TDm2)
O(TDm)
No
Accelerated Parallel Broyden (this paper)
Dt(0)+Ut(i)Vt(i)⊤ , rank≤m
O(TDm2+Tm3)
O(TDm)
No
Table 1: Comparison of trajectory evaluation methods. Sequential is the baseline. All other methods are parallel via parallel scan with O(logT) depth. Parallel Broyden and Accelerated Parallel Broyden (this work) use diagonal-plus-low-rank (DPLR) block approximations with rank at most m .
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.
Figure 2: Hierarchical Gibbs sampling. Across 32 problem instances, we report median iteration counts and runtimes with interquartile ranges as we vary trajectory length T and state dimension D=2S+2 . Parallel Broyden variants require fewer iterations than diagonal quasi-Newton by capturing low-rank hierarchical coupling. Accelerated Parallel Broyden is the fastest approximate method in every setting, and the fastest overall except for small problems (small S or short T ). It also remains applicable at the largest settings, where exact Newton runs out of memory.
Figure 3: DDIM sampling with a pretrained DiT denoiser. A: After 11 iterations, Parallel Broyden is visually indistinguishable from the sequential reference, while ParaTAA and Picard have not fully converged (bottom: zoom on boxed region). B: Mean iteration counts and runtimes over 32 images ( ± s.d.). Local dynamics-Jacobian methods need fewer iterations than Picard and ParaTAA, and Parallel Broyden variants are the fastest parallel methods by avoiding differentiation through the denoiser.
Appendix figures & tables21 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: Overview of Parallel Broyden. (a) Evaluating the sequence is cast as solving r(x1:T)=0 with rt=xt−ft(xt−1) . Each Newton step solves a block-bidiagonal system JΔx=−r , which is equivalent to the linear recurrence Δxt=AtΔxt−1−rt with Jacobians At=∂ft/∂xt−1 . (b) Each dense Jacobian At is replaced by a diagonal-plus-low-rank (DPLR) matrix At=Λt+UtVt⊤ , with Λt diagonal and Ut,Vt∈RD×m . It is fitted without automatic differentiation from secants pt=xt−1(i+1)−xt−1(i) and qt=ft(xt−1(i+1))−ft(xt−1(i)) , either by rank-one Broyden updates (Parallel Broyden) or by fitting the last m secants jointly (Accelerated Parallel Broyden). (c) The recurrence is solved with a parallel scan over the At . Each merge multiplies two DPLR matrices, which raises the rank of the low-rank part to at most 2m , then compresses it back to rank m with randomized compression, so Aj:i≈Aj⋯Ai . Each merge costs O(Dm2) instead of O(D3) , giving O(logT) depth and O(TDm) memory. The iterate is updated as x(i+1)=x(i)+Δx until ∥r∥≤ϵ .
Figure 5: Effect of compression on the low-rank RNN benchmark. We compare exact sequential forward substitution, compressed scan with exact QR+SVD rank compression, and compressed scan with randomized factorized compression. Points show medians over 32 random realizations, with error bars indicating interquartile ranges. All three variants require similar numbers of Newton iterations, indicating that compression does not materially degrade convergence. Randomized compression gives the lowest runtime by avoiding both sequential depth and the small SVDs used by exact compression.
PB
Accel. PB
Model
Δt
T
B
HS
B
HS
Standard
0.5
103
13
13
9
9
104
15
15
11
11
105
14
14
12.5
13
3
103
25
25
11
11
104
26
26
12
12
Appendix
Table 2: Effect of the scan tree on iteration counts (low-rank RNNs, D=200 , float64 ). Median iterations over 32 chains with the Blelloch (B) and Hillis–Steele (HS) scans, with non-converged chains counted at the 1000 -iteration cap.
Setting
Method
σi
ρi
Iterations
Std RNN, Δt=0.5
Accel.
0.885
0.025
9
Broyden
0.885
0.057
13
Diag. QN
0.891
0.118
37.5
MLP RNN, Δt=0.5
Accel.
1.074
0.041
9.5
Broyden
0.991
0.044
12
Diag. QN
0.996
0.131
35
Appendix
Table 3: Spectral-norm block error σi and error-direction quantity ρi at the last iteration, and median iteration counts over the 8 diagnostic chains. Diagonal quasi-Newton was run on the RNNs only.
RMS residual
≥10−1
[10−2,10−1)
[10−3,10−2)
[10−4,10−3)
Parallel Broyden
0.46
0.30
0.24 – 0.27
0.23 – 0.27
Accelerated Parallel Broyden
0.48 – 0.49
0.36 – 0.40
0.19 – 0.29
0.09 – 0.11
Appendix
Table 4: Median ρi for the two Broyden variants on the RNNs at Δt=3 , grouped by the root-mean-square residual ∥r∥2/TD . Ranges are over the standard and MLP models.
σi (last)
ρi (last)
Frac. ρi>1
Setting
damped
undamped
damped
undamped
damped
undamped
Std RNN, Δt=0.5
0.885
0.885
0.057
0.066
0
0
MLP RNN, Δt=0.5
0.991
0.990
0.044
0.058
0
0
Std RNN, Δt=3
5.32
5.56
0.333
0.488
0
0.095
MLP RNN, Δt=3
6.62
6.62
0.320
0.537
0
0.034
Gibbs, S=10
129.6
129.6
0.907
1.279
0.20
0.54
Appendix
Table 5: Effect of damping on Parallel Broyden: σi and ρi at the last iteration and fraction of iterations with ρi>1 , with damped and undamped blocks along the same iterates.
Setting
Method
ρ term of c0
Frac. λc<0
Observed
Frac. increase
Std RNN, Δt=0.5
Accel.
10.7 – 45.3
0.83
0.35
0.18
Broyden
2.1 – 10.9
0.50
0.57
0.25
MLP RNN, Δt=0.5
Accel.
1.9 – 7.1
0.67
0.41
0.18
Broyden
6.1 – 20.9
0.50
0.61
0.17
Std RNN, Δt=3
Accel.
1.4 – 3.3
0.33
0.30
0.30
Broyden
4.1 – 10.8
1.00
0.72
0.33
Appendix
Table 6: The ρ term of c0 (range over iterations with λc<0 ), fraction of iterations with λc<0 , observed contraction ∥e(i+1)∥∞/∥e(i)∥∞ (median over the last three iterations), and fraction of iterations where the error increases.
Figure 6: Effect of the limited-memory update rule on the low-rank RNN benchmark. We compare simple truncation, which discards the oldest rank-one correction once the rank budget is full, with the L-BFGS-style identity_rescaled variant, which rescales the identity baseline from the most recent secant pair and replays the stored updates. Points denote medians over 32 random seeds, and error bars denote interquartile ranges. The rescaled variant does not substantially improve median performance over simple truncation, but appears slightly more stable, with slightly smaller upper quartiles.
Figure 7: Impact of damping on Parallel Broyden stability. Low-rank RNN experiment over 32 random seeds. Points denote medians and error bars denote interquartile ranges. Moderate damping reduces instability and improves robustness across seeds, while excessive damping weakens the low-rank secant correction and can degrade convergence. For example, when D=100 , k=0.5 gives worse median performance than smaller damping values across all tested trajectory lengths.
Method
Δt=0.5
Δt=3
Newton
0
0
Diag. quasi-Newton
0.1
0.8
Parallel Broyden
0.2
0.4
Accel. Parallel Broyden
0.2
0.1
Appendix
Table 7: Damping values for the low-rank RNNs. The same values are used for both models.
Iterations
Converged
Model
Δt
T
PB
Accel. PB
PB / Accel.
PB
Accel. PB
Standard
0.5
103
12.5
10
1.25
32
32
104
14
10
1.40
30
32
105
15
12
1.25
30
32
3
103
30.5
10
3.05
32
32
104
29.5
11
2.68
27
31
Appendix
Table 8: Iterations of the Broyden variants on the low-rank RNNs ( D=200 ). Median over all 32 chains, with non-converged chains counted at the 1000 -iteration cap, and number of converged chains.
Figure 8: Example of the dynamics Jacobian matrix of the standard low-rank RNN. The matrix is exactly diagonal plus rank R=3 .
Figure 9: Singular value spectrum of the DMF RNN Jacobian. Normalized singular values σi/σ1 of At along trajectories (median and interquartile range over 32 independently sampled networks). The dashed line marks 1% of σ1 .
Figure 10: Structure of the Gibbs transition Jacobian for the hierarchical normal model. A: Example transition Jacobian averaged over time, showing small diagonal entries and structured off-diagonal coupling induced by the hierarchical updates. B: Singular values of the transition Jacobian, normalized by the largest singular value and averaged over time, with error bars denoting standard deviations. The spectrum is dominated by the first two singular values, supporting the rank- 2 purely low-rank approximation used by the Broyden variants in this experiment.
Probes
T
S=10
S=50
S=100
S=200
1
103
0
0
0
0
1
104
0
0
0
0
8
103
0
0
0
0
8
104
0
0
0
0
64
103
1
19
22
16
64
104
0
0
0
0
Appendix
Table 9: Hutchinson-based diagonal quasi-Newton on the hierarchical Gibbs sampler. Number of chains, out of 32 , that reach the tolerance within 1000 iterations.
Figure 11: Off-diagonal mass of the DDIM local dynamics Jacobian. Relative norm of Aℓ−diag(Aℓ) along the sampling trajectory, in Frobenius and spectral norm (median and range over 3 images).
Figure 12: ParaTAA hyperparameter search. We vary the nonlinear system order k and history size m for DDIM-50 with window size w=T=50 . Points denote means over 32 images, and shaded regions denote ± one standard deviation. Consistent with ParaTAA’s hyperparameter analysis, small history sizes are sufficient: m=2 requires fewer iterations than m=4 at every order.
Figure 13: Parallel Broyden hyperparameter search. We vary the diagonal scaling γ in the initialization γID and the maximum DPLR rank m on the DDIM-50 benchmark. Points denote means over 32 images, and shaded regions denote ± one standard deviation. Larger diagonal scaling improves convergence across all tested ranks, while increasing the rank beyond m=2 gives no improvement.
Method
Median LPIPS
IQR
Diagonal quasi-Newton
0.0032
[0.0014,0.0065]
Parallel Broyden
0.0032
[0.0015,0.0051]
Picard
0.0034
[0.0015,0.0055]
Accelerated Parallel Broyden
0.0031
[0.0014,0.0051]
ParaTAA
0.0037
[0.0016,0.0062]
Appendix
Table 10: LPIPS distance between each parallel sample and the corresponding sequential DDIM reference over 32 images. Lower is better.
Benchmark
Baseline
Method
Iterations
Iter. ratio
Per-iter. ratio
Runtime ratio
Low-rank MLP-RNN
Diag. QN
PB
38 / 19
2.00
15.74
31.48
Diag. QN
Accel. PB
38 / 12
3.17
17.78
56.31
Newton
PB
3 / 19
0.16
19.38
3.06
Newton
Accel. PB
3 / 12
0.25
21.89
5.47
Standard low-rank RNN
Diag. QN
PB
30 / 14.5
2.07
0.04
0.09
Diag. QN
Accel. PB
30 / 12
2.50
0.05
0.13
Appendix
Table 11: Decomposition of the runtime ratio. Runtime ratio = iteration ratio × per-iteration cost ratio, baseline over Broyden variant ( >1 : the Broyden variant is faster). T=105 for the RNNs and the Gibbs sampler ( D=200 , with Δt=3 for the low-rank MLP-RNN and Δt=0.5 for the standard low-rank RNN). Iterations: baseline / method. For the RNNs, medians are over converged chains, so that iteration and runtime ratios refer to the same chains. Figure 1 instead counts non-converged chains at the iteration cap. For the Gibbs sampler, medians are over all chains, and for DiT, means are over the 32 images, as in the corresponding figures.
Benchmark
Method
ms/iter.
f (%)
Autodiff (%)
Update (%)
Scan (%)
Sum/meas.
Low-rank MLP-RNN
Diag. QN
438
1
99
–
<1
1.00
Newton
538
<1
82
–
17
1.00
PB
27.9
22
–
5
73
0.84
Accel. PB
25.3
19
–
17
64
1.06
Standard low-rank RNN
Diag. QN
1.05
51
14
–
35
1.26
Newton
90.9
<1
6
–
93
1.05
Appendix
Table 12: Wall-clock breakdown of one iteration (H100, float32 , T=105 except DiT). Measured time per iteration, and share of each component: evaluations of the transition f (for DiT, the denoiser), automatic differentiation (Jacobian or its diagonal by reverse mode, or Hutchinson Jacobian–vector products for DiT), Broyden update (rank-one updates or refit of Ut ), and parallel scan (with rank compression for the Broyden variants). Components are timed in isolation. Shares are fractions of their summed time, and the last column compares this sum with the measured iteration, in which XLA fuses part of the work (on the Gibbs sampler, the isolated components of PB and Accel. PB take the same time, but the measured Accel. PB iteration is faster, also in the sweep: 5.4 vs. 8.2 ms). Matmul precision as in the corresponding experiments (DiT: TF32), so the measured times match the sweeps.
School of Biomedical Engineering and Technology, Tianjin Medical University, Medical School, Tianjin University · School of Biomedical Engineering and Technology, Tianjin Medical University, Tianjin, 300070, China · Medical School, Tianjin University, Tianjin, 300072, China