Introduction
Parallel computation has been a key driver of recent advances in machine learning. Architectures such as transformers [1 ] and linear state space models [2 , 3 , 4 , 5 ] are explicitly designed to exploit parallelism over sequence length. In contrast, general nonlinear state space models, including recurrent neural networks [6 , 7 , 8 ] , diffusion samplers [9 , 10 , 11 , 12 ] , and Markov chain Monte Carlo methods [13 , 14 , 15 , 16 , 17 ] , seem inherently sequential, requiring time that scales linearly with trajectory length. This sequential dependency limits their ability to exploit modern parallel hardware.
Recent work, including DEER [18 ] and DeepPCR [19 ] , has addressed this challenge by reformulating trajectory computation as a root-finding problem over the full sequence. In this formulation, the residual Jacobian has a block-bidiagonal structure, so Newton updates reduce to solving a linear recurrence that can be evaluated with logarithmic parallel depth via parallel scan [20 ] . This makes it possible to replace sequential evaluation with iterative parallel trajectory refinement.
However, exact Newton updates face two scalability bottlenecks. First, they require storing and multiplying dense dynamics Jacobian matrices, leading to memory and computational costs that scale poorly with state dimension. Second, evaluating these Jacobians with automatic differentiation can be expensive when the transition map is a large neural network or simulator. Scalable quasi-Newton variants address the first bottleneck by replacing each block with a diagonal approximation, reducing memory and computation to scale linearly with state dimension [21 ] . However, these methods still require estimating or computing the diagonal of the Jacobian, and therefore do not fully remove the cost of Jacobian evaluation. Moreover, the diagonal approximation discards dependencies across state dimensions, which can hinder convergence when the dynamics exhibit strong coupling [22 ] .
In this work, we ask: Can we construct richer Jacobian approximations that retain the scalability of diagonal quasi-Newton while capturing structured cross-dimensional coupling and avoiding expensive Jacobian evaluation? We answer this question by introducing Parallel Broyden methods, a family of quasi-Newton methods based on Broyden’s method that can be parallelized over the sequence length. Broyden’s method is a classical quasi-Newton approach for updating Jacobian approximations from secant information [23 ] , without automatic differentiation. Broyden-style updates underlie several widely used optimization methods, including BFGS and L-BFGS [24 , 25 ] . Our approach targets regimes where cross-dimensional interactions are important but can be captured by low-rank corrections, or where automatic differentiation through the transition map is costly.
Our contributions are as follows:
We introduce Parallel Broyden, a family of quasi-Newton methods for parallel nonlinear trajectory evaluation that build scan-compatible diagonal-plus-low-rank Jacobian approximations from trajectory secants, avoiding costly automatic differentiation.
We develop a compressed approximate scan that controls the rank of diagonal-plus-low-rank blocks while preserving logarithmic parallel depth and scaling linearly with state dimension for small rank. We prove finite-step recovery of the exact trajectory even with compression.
We extend the convergence analysis of parallel quasi-Newton methods to compressed scans, and show theoretically and empirically that convergence is tracked by the block approximation error along the current trajectory error, rather than in spectral norm.
We show empirically on low-rank RNNs and hierarchical Gibbs sampling that our approach captures low-rank coupling more effectively than diagonal quasi-Newton, and on diffusion models that it avoids costly differentiation through the denoiser, reducing iteration counts relative to diagonal quasi-Newton and improving runtime over exact and diagonal methods when Jacobian computation or scaling costs dominate, with speedups of up to 30 × 30\times 30 × over sequential evaluation. Code is available at https://github.com/ianctanoh/BroyDEER .
Problem Statement and Related Work
Parallel computation over sequences is central to modern sequence modeling. Structured state space models such as S4, S5, and Mamba exploit algebraic structure for efficient long-sequence computation [2 , 4 , 3 ] . For general nonlinear recurrences, recent work instead recasts trajectory evaluation as a nonlinear system solved by iterative refinement, including DEER and DeepPCR [18 , 19 ] , Picard iteration for parallel diffusion sampling [26 , 27 ] , parallel-in-time methods for ODE solvers [28 ] , and MCMC [29 ] . Recent unifying work views these approaches as quasi-Newton iterations on the full trajectory residual [22 ] . We follow this perspective, using Broyden-style secant updates to obtain scalable quasi-Newton approximations for parallel trajectory evaluation.
Following the notation of Gonzalez et al. [22 ] , we consider a D D D -dimensional nonlinear state-space model with time-indexed transition maps f t : R D → R D f_t : \mathbb{R}^{D} \to\mathbb{R}^{D} f t : R D → R D , where the state at time t t t is x t ∈ R D x_t \in\mathbb{R}^{D} x t ∈ R D . The maps f t f_t f t may represent, for example, the transition of a recurrent neural network, one step of a numerical simulator, a sampling update, or a diffusion model denoising step. Given an initial state x 0 x_0 x 0 , our goal is to compute the trajectory x 1 : T ∈ R T × D x_{1:T} \in\mathbb{R}^{T \times D} x 1 : T ∈ R T × D satisfying
x t = f t ( x t − 1 ) , t = 1 , … , T . (1) x_t = f_t(x_{t-1}), \quad t = 1,\ldots,T. \tag*{(1)} x t = f t ( x t − 1 ) , t = 1 , … , T . (1)
Although this recurrence is naturally evaluated sequentially, our aim is to expose structure that permits parallel computation across the time axis. For clarity, we absorb input dependence into the time-indexed transition maps f t f_t f t .
Residual formulation. Rather than solving (1) sequentially, we recast trajectory computation as a root-finding problem. For any candidate trajectory x 1 : T x_{1:T} x 1 : T , define the block residual
r t ( x 1 : T ) : = x t − f t ( x t − 1 ) , t = 1 , … , T . (2) r_t(x_{1:T}) := x_t - f_t(x_{t-1}), \quad t = 1,\ldots,T. \tag*{(2)} r t ( x 1 : T ) := x t − f t ( x t − 1 ) , t = 1 , … , T . (2)
and stack these blocks into r ( x 1 : T ) ∈ R T × D \mathbf{r}(\mathbf{x}_{1:T}) \in\mathbb{R}^{T \times D} r ( x 1 : T ) ∈ R T × D . The true trajectory x 1 : T ⋆ \mathbf{x}^{\star}_{1:T} x 1 : T ⋆ is characterized by
r ( x 1 : T ⋆ ) = 0 , (3) \mathbf{r}(\mathbf{x}^{\star}_{1:T}) = 0, \tag*{(3)} r ( x 1 : T ⋆ ) = 0 , (3)
with each residual block measuring the one-step prediction error at time t t t . Our goal is to solve (3) in sublinear parallel depth while keeping the per-iteration cost favorable in the state dimension.
Exact parallel Newton [18 , 19 ] . The root-finding formulation (3) allows trajectory evaluation to be performed by Newton iteration over the full sequence. Starting from a candidate sequence x 1 : T ( i ) \mathbf{x}^{(i)}_{1:T} x 1 : T ( i ) , Newton’s method computes a correction Δ x ( i ) \Delta\mathbf{x}^{(i)} Δ x ( i ) that locally reduces all residuals r 1 , … , r T \mathbf{r}_1,\ldots,\mathbf{r}_T r 1 , … , r T simultaneously by solving
J ( x 1 : T ( i ) ) Δ x ( i ) = − r ( x 1 : T ( i ) ) , (4) \mathbf{J}\left(\mathbf{x}^{(i)}_{1:T}\right)\Delta\mathbf{x}^{(i)} = -\mathbf{r}\left(\mathbf{x}^{(i)}_{1:T}\right), \tag*{(4)} J ( x 1 : T ( i ) ) Δ x ( i ) = − r ( x 1 : T ( i ) ) , (4)
where J ( x 1 : T ( i ) ) \mathbf{J}(\mathbf{x}^{(i)}_{1:T}) J ( x 1 : T ( i ) ) is the Jacobian of the residual map with respect to the trajectory variables. This Jacobian has special structure because each residual block r t = x t − f t ( x t − 1 ) \mathbf{r}_t = \mathbf{x}_t - f_t(\mathbf{x}_{t-1}) r t = x t − f t ( x t − 1 ) depends only on the current and previous states. Treating x 1 : T \mathbf{x}_{1:T} x 1 : T as a flattened vector in R T D \mathbb{R}^{TD} R T D and defining
A t ( i ) : = ∂ f t ∂ x t − 1 ( x t − 1 ( i ) ) ∈ R D × D , \mathbf{A}^{(i)}_t := \frac{\partial f_t}{\partial\mathbf{x}_{t-1}}\left(\mathbf{x}^{(i)}_{t-1}\right) \in\mathbb{R}^{D \times D}, A t ( i ) := ∂ x t − 1 ∂ f t ( x t − 1 ( i ) ) ∈ R D × D ,
the residual Jacobian is block lower bidiagonal:
J ( x 1 : T ( i ) ) : = ∂ r ∂ x 1 : T ( x 1 : T ( i ) ) = ( I D 0 ⋯ 0 0 − A 2 ( i ) I D ⋯ 0 0 0 − A 3 ( i ) ⋱ 0 0 ⋮ ⋮ ⋱ I D 0 0 0 ⋯ − A T ( i ) I D ) . \mathbf{J}\left(\mathbf{x}^{(i)}_{1:T}\right) := \frac{\partial\mathbf{r}}{\partial\mathbf{x}_{1:T}}\left(\mathbf{x}^{(i)}_{1:T}\right) =
\begin{pmatrix}
\mathbf{I}_D & 0 & \cdots& 0 & 0 \\
-\mathbf{A}^{(i)}_2 & \mathbf{I}_D & \cdots& 0 & 0 \\
0 & -\mathbf{A}^{(i)}_3 & \ddots& 0 & 0 \\
\vdots& \vdots& \ddots& \mathbf{I}_D & 0 \\
0 & 0 & \cdots& -\mathbf{A}^{(i)}_T & \mathbf{I}_D
\end{pmatrix}. J ( x 1 : T ( i ) ) := ∂ x 1 : T ∂ r ( x 1 : T ( i ) ) = I D − A 2 ( i ) 0 ⋮ 0 0 I D − A 3 ( i ) ⋮ 0 ⋯ ⋯ ⋱ ⋱ ⋯ 0 0 0 I D − A T ( i ) 0 0 0 0 I D .
Solving (4) is therefore equivalent to evaluating a linear recurrence over time, which can be computed with logarithmic parallel depth using parallel scan, a standard primitive for prefix computation.
Diagonal quasi-Newton [21 ] . Exact Newton is costly in high dimensions because it must form, store, and compose dense dynamics Jacobian blocks A t ( i ) \mathbf{A}^{(i)}_t A t ( i ) inside the parallel scan, leading to O ( T D 2 ) O(TD^2) O ( T D 2 ) memory and O ( T D 3 ) O(TD^3) O ( T D 3 ) work. Diagonal quasi-Newton reduces this cost by replacing each block with a diagonal approximation. Since diagonal matrices are closed under multiplication, the scan remains exact under the approximation while reducing memory and computation to scale linearly in D D D per block. In practice, this approach is most effective when the dynamics Jacobian is well approximated by its diagonal and when the cost of dense Newton-style updates is prohibitive at scale [22 ] .
Beyond the diagonal approximation. However, the diagonal approximation may become too crude when the dynamics are strongly coupled across dimensions. This occurs, for example, in hierarchical Gibbs samplers, where updating one latent variable can change the conditional distribution of many others. Moreover, Gonzalez et al. [22 ] bound the convergence rate of quasi-Newton updates in terms of the spectral-norm error of the block Jacobian approximation, suggesting that more accurate block approximations lead to faster convergence. This motivates the search for richer quasi-Newton block approximations that better capture these interactions while retaining the O ( T D ) O(TD) O ( T D ) memory and work of diagonal quasi-Newton methods.
Parallel Broyden methods for scalable sequence evaluation
We now introduce Broyden-based quasi-Newton approximations for parallel nonlinear trajectory evaluation. Figure 4 (Appendix § 7 ) gives an overview of the method. The methods, which we refer to as Parallel Broyden methods, construct diagonal-plus-low-rank (DPLR) approximations of local dynamics Jacobian blocks from trajectory secants rather than automatic differentiation. We first describe the rank-one Broyden updates underlying this construction, then we present a multi-secant variant that we call Accelerated Parallel Broyden. We then show how these DPLR blocks can be made compatible with logarithmic-depth parallel scan through rank compression. Finally, we show that the compressed scan preserves finite-step recovery of the exact trajectory, and analyze how block approximation error and rank compression affect the local convergence rate.
Figure 4. Overview of Parallel Broyden. (a) Evaluating the sequence is cast as solving r ( x 1 : T ) = 0 r(x_{1:T}) = 0 r ( x 1 : T ) = 0 with r t = x t − f t ( x t − 1 ) r_t = x_t - f_t(x_{t-1}) r t = x t − f t ( x t − 1 ) . Each Newton step solves a block-bidiagonal system J Δ x = − r \mathbf{J}\,\Delta x = -r J Δ x = − r , which is equivalent to the linear recurrence Δ x t = A t Δ x t − 1 − r t \Delta x_t = A_t \Delta x_{t-1} - r_t Δ x t = A t Δ x t − 1 − r t with Jacobians A t = ∂ f t / ∂ x t − 1 A_t = \partial f_t/\partial x_{t-1} A t = ∂ f t / ∂ x t − 1 . (b) Each dense Jacobian A t A_t A t is replaced by a diagonal-plus-low-rank (DPLR) matrix A ~ t = Λ t + U t V t ⊤ \widetilde{A}_t = \Lambda_t + U_tV_t^\top A t = Λ t + U t V t ⊤ , with Λ t \Lambda_t Λ t diagonal and U t U_t U t , V t ∈ R D × m V_t \in\mathbb{R}^{D \times m} V t ∈ R D × m . It is fitted without automatic differentiation from secants p t = x t − 1 ( i + 1 ) − x t − 1 ( i ) p_t = x_{t-1}^{(i+1)} - x_{t-1}^{(i)} p t = x t − 1 ( i + 1 ) − x t − 1 ( i ) and q t = f t ( x t − 1 ( i + 1 ) ) − f t ( x t − 1 ( i ) ) q_t = f_t(x_{t-1}^{(i+1)}) - f_t(x_{t-1}^{(i)}) q t = f t ( x t − 1 ( i + 1 ) ) − f t ( x t − 1 ( i ) ) , either by rank-one Broyden updates (Parallel Broyden) or by fitting the last m m m secants jointly (Accelerated Parallel Broyden). (c) The recurrence is solved with a parallel scan over the A ~ t \widetilde{A}_t A t . Each merge multiplies two DPLR matrices, which raises the rank of the low-rank part to at most 2 m 2m 2 m , then compresses it back to rank m m m with randomized compression, so A ~ j : i ≈ A ~ j ⋯ A ~ i \widetilde{A}_{j:i} \approx\widetilde{A}_j \cdots\widetilde{A}_i A j : i ≈ A j ⋯ A i . Each merge costs O ( D m 2 ) O(Dm^2) O ( D m 2 ) instead of O ( D 3 ) O(D^3) O ( D 3 ) , giving O ( log T ) O(\log T) O ( log T ) depth and O ( T D m ) O(TDm) O ( T D m ) memory. The iterate is updated as x ( i + 1 ) = x ( i ) + Δ x x^{(i+1)} = x^{(i)} + \Delta x x ( i + 1 ) = x ( i ) + Δ x until ∥ r ∥ ≤ ϵ \lVert r\rVert\le\epsilon ∥ r ∥ ≤ ϵ .
DPLR Jacobian approximation with Broyden’s method
Parallel Broyden applies Broyden’s method blockwise to the local dynamics functions. Rather than forming Jacobians with automatic differentiation, it updates each block approximation using finite differences between successive trajectory iterates. Since Broyden updates are rank-one corrections, initializing with a diagonal baseline naturally yields diagonal-plus-low-rank approximations without automatic differentiation.
Blockwise Broyden update. After computing the iterate x 1 : T ( i + 1 ) x_{1:T}^{(i+1)} x 1 : T ( i + 1 ) , we form a secant pair for each transition f t f_t f t :
p t ( i ) : = x t − 1 ( i + 1 ) − x t − 1 ( i ) , q t ( i ) : = f t ( x t − 1 ( i + 1 ) ) − f t ( x t − 1 ( i ) ) . p_t^{(i)} := x_{t-1}^{(i+1)} - x_{t-1}^{(i)}, \qquad q_t^{(i)} := f_t(x_{t-1}^{(i+1)}) - f_t(x_{t-1}^{(i)}). p t ( i ) := x t − 1 ( i + 1 ) − x t − 1 ( i ) , q t ( i ) := f t ( x t − 1 ( i + 1 ) ) − f t ( x t − 1 ( i ) ) .
The new approximation A ~ t ( i + 1 ) \widetilde{A}_t^{(i+1)} A t ( i + 1 ) is then required to satisfy the secant condition :
A ~ t ( i + 1 ) p t ( i ) = q t ( i ) . \widetilde{A}_t^{(i+1)}p_t^{(i)} = q_t^{(i)}. A t ( i + 1 ) p t ( i ) = q t ( i ) .
This is the multidimensional analogue of a finite-difference estimate of a derivative. Since the condition does not uniquely determine A ~ t ( i + 1 ) \widetilde{A}_t^{(i+1)} A t ( i + 1 ) , Broyden’s method chooses the feasible matrix closest to the current approximate dynamics Jacobian A ~ t ( i ) \widetilde{A}_t^{(i)} A t ( i ) :
A ~ t ( i + 1 ) = arg min A ∥ A − A ~ t ( i ) ∥ F s.t. A p t ( i ) = q t ( i ) . \widetilde{A}_t^{(i+1)} = \arg\min_A \left\lVert A - \widetilde{A}_t^{(i)} \right\rVert_F \quad\text{s.t.} \quad Ap_t^{(i)} = q_t^{(i)}. A t ( i + 1 ) = arg A min A − A t ( i ) F s.t. A p t ( i ) = q t ( i ) .
The solution is a rank-one correction to the previous approximation (see Appendix § 11 .§ 1 ).
DPLR structure and limited memory. Each Broyden update adds a rank-one correction to the current approximation. Starting from a diagonal initialization A ~ t ( 0 ) = D t ( 0 ) \widetilde{A}_t^{(0)} = D_t^{(0)} A t ( 0 ) = D t ( 0 ) , after i i i updates the approximation can be written as
A ~ t ( i ) = D t ( 0 ) + U t ( i ) ( V t ( i ) ) T , U t ( i ) , V t ( i ) ∈ R D × i . \widetilde{A}_t^{(i)} = D_t^{(0)} + U_t^{(i)}(V_t^{(i)})^{\mathsf{T}}, \qquad U_t^{(i)}, V_t^{(i)} \in\mathbb{R}^{D \times i}. A t ( i ) = D t ( 0 ) + U t ( i ) ( V t ( i ) ) T , U t ( i ) , V t ( i ) ∈ R D × i .
Each column pair in U t ( i ) U_t^{(i)} U t ( i ) and V t ( i ) V_t^{(i)} V t ( i ) corresponds to one secant correction. In our experiments, we choose D t ( 0 ) = γ I D D_t^{(0)} = \gamma I_D D t ( 0 ) = γ I D , with γ \gamma γ a task-dependent hyperparameter. Since the rank of the low-rank component grows with the number of Broyden updates, we use a limited-memory variant that retains only the most recent m m m secant corrections per block. This yields a DPLR approximation with rank at most m m m while keeping the representation bounded and compatible with the rank-truncated scan described below. We also considered an L-BFGS-style variant that rescales the diagonal baseline from the most recent secant pair before replaying the stored corrections. Since this added complexity did not substantially change performance in our experiments, we use the simpler fixed-baseline truncation as the default (see Appendix § 11 .§ 2 ).
Multi-secant variant. The rank-one Broyden update incorporates one secant condition at a time. As a standard extension, we also consider a multi-secant variant that uses the most recent m m m trajectory secants simultaneously [30 , 31 ] . Rather than accumulating rank-one corrections over time, this variant fits a rank-at-most-m m m correction in a single step on top of a reference matrix. In our experiments, we take this reference matrix to be γ I D \gamma I_D γ I D , resulting in a DPLR approximation with correction at most rank m m m . We call this the Accelerated Parallel Broyden method. It adds only small m × m m \times m m × m linear solves and, as we will see, can substantially reduce the number of iterations in practice. Details are deferred to Appendix § 11 .§ 3 . When needed for stability, we damp the low-rank corrections (Appendix § 11 .§ 4 ). The values used in each experiment are given in the corresponding appendices.
Scan-compatible DPLR approximations
The Broyden updates above naturally produce DPLR approximations of the local dynamics Jacobian blocks. Specifically, we represent each approximate block as A ~ t = γ I D + U t V t T \widetilde{A}_t = \gamma I_D + U_tV_t^{\mathsf{T}} A t = γ I D + U t V t T with U t , V t ∈ R D × m U_t, V_t \in\mathbb{R}^{D \times m} U t , V t ∈ R D × m , and m ≪ D m \ll D m ≪ D . The main challenge is compatibility with the parallel scan. Diagonal matrices are closed under multiplication, so their representation remains fixed across the scan tree. In contrast, the product of two DPLR matrices gives a diagonal matrix plus a correction of rank at most 2 m 2m 2 m , so repeated composition can eventually lead to a full rank matrix.
We address this by introducing a novel compressed approximate scan , which allows DPLR matrices to remain compatible with parallel scan by controlling rank growth at each merge. Instead of requiring closure under composition, we allow rank growth at each merge and compress the resulting correction of rank at most 2 m 2m 2 m back to rank at most m m m . This keeps the representation size bounded while preserving O ( log T ) O(\log T) O ( log T ) parallel depth. Because compression is not exact, the merge is only approximately associative, so the result can depend on the order in which products are formed and compressed, i.e., on the scan tree. At the ranks used in our experiments, the choice of tree has no meaningful effect on convergence (Appendix § 8 .§ 4 ), and all experiments use the Blelloch-type scan implemented by jax.lax.associative_scan. Note that in the purely low-rank case with no diagonal term, the class of rank-at-most m m m matrices is closed under multiplication, so no compression is needed.
Randomized rank compression. We compress directly in factorized form using randomized low-rank approximation [32 , 33 ] . Given a rank-at-most-2 m 2m 2 m correction U V T UV^{\mathsf{T}} U V T with U , V ∈ R D × 2 m U, V \in\mathbb{R}^{D \times2m} U , V ∈ R D × 2 m , draw Ω ∈ R D × m \Omega\in\mathbb{R}^{D \times m} Ω ∈ R D × m and form Y = ( U V T ) Ω = U ( V T Ω ) Y = (UV^{\mathsf{T}})\Omega= U(V^{\mathsf{T}}\Omega) Y = ( U V T ) Ω = U ( V T Ω ) . Let Y = Q R Y = QR Y = QR be a thin QR decomposition. Projecting onto span ( Q ) \operatorname{span}(Q) span ( Q ) gives U V T ≈ Q ( Q T U ) V T = U ~ V ~ T UV^{\mathsf{T}} \approx Q(Q^{\mathsf{T}}U)V^{\mathsf{T}} = \widetilde{U}\widetilde{V}^{\mathsf{T}} U V T ≈ Q ( Q T U ) V T = U V T , with U ~ = Q \widetilde{U} = Q U = Q and V ~ = V ( U T Q ) \widetilde{V} = V(U^{\mathsf{T}}Q) V = V ( U T Q ) . This avoids dense matrices and singular value decomposition (SVD). As a reference, we also implement exact compression via a small 2 m × 2 m 2m \times2m 2 m × 2 m SVD. Appendix § 8 shows that rank compression has little effect on convergence rate at our ranks, while the randomized scheme is fastest.
Complexity. For fixed rank m m m , storing a DPLR block requires O ( D m ) O(Dm) O ( D m ) memory and applying it costs O ( D m ) O(Dm) O ( D m ) . Composition followed by randomized compression costs O ( D m 2 ) O(Dm^2) O ( D m 2 ) . Across all T T T blocks, this yields O ( T D m ) O(TDm) O ( T D m ) memory while preserving the O ( log T ) O(\log T) O ( log T ) parallel depth of the scan. Thus, small m m m preserves linear scaling in D D D while extending beyond diagonal quasi-Newton (Table 1 ).
Table 1. Comparison of trajectory evaluation methods. Sequential is the baseline. All other methods are parallel via parallel scan with O ( log T ) \mathcal{O}(\log T) 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 m m .
Global convergence. A key question is whether the compressed approximate scan preserves the finite-step recovery property of parallel (exact or quasi-) Newton methods: after i i i iterations, the first i i i states are recovered exactly, and the full trajectory is recovered in at most T T T iterations [21 ] . The answer is yes. Although compression changes the matrix factors used inside the scan, the inductive recovery argument remains valid because correct prefixes have zero residual offsets.
Theorem 1 (Global convergence with approximate scan). Starting from any initial trajectory x 1 : T ( 0 ) \mathbf{x}_{1:T}^{(0)} x 1 : T ( 0 ) , after i i i iterations using the approximate scan, we have x t ( i ) = x t ⋆ \mathbf{x}_t^{(i)} = \mathbf{x}_t^\star x t ( i ) = x t ⋆ for all t ≤ i t \le i t ≤ i . In particular, the method recovers the exact trajectory x 1 : T ⋆ \mathbf{x}_{1:T}^\star x 1 : T ⋆ in at most T T T iterations (Proof in Appendix § 8 .§ 1 ).
Effect of Jacobian approximation and compression error on convergence
Theorem 1 guarantees recovery in at most T T T iterations, but says nothing about how quickly the error decreases. For quasi-Newton updates with an exact scan, Gonzalez et al. [22 Prop. 3] show that, to first order, each iteration contracts the error by a factor ∥ J ~ t − 1 ∥ 2 max t ∥ A ~ t − A t ∥ 2 \lVert\widetilde{J}^{-1}_{t} \rVert_2 \max_t \lVert\widetilde{A}_t - A_t \rVert_2 ∥ J t − 1 ∥ 2 max t ∥ A t − A t ∥ 2 . We extend this result to obtain rates independent of T T T and to account for rank compression inside the scan.
Assumptions. Following Gonzalez et al. [34 ] , convergence is governed by products of Jacobians: if they contract, errors remain local and parallel Newton converges rapidly. If they grow, errors propagate over long horizons. Since the solver multiplies its approximate blocks rather than the true Jacobians, we assume products A ~ t + k ⋯ A ~ t + 1 \widetilde{A}_{t+k} \cdots\widetilde{A}_{t+1} A t + k ⋯ A t + 1 grow at most at an exponential rate λ ~ \widetilde{\lambda} λ , up to a transient factor α ~ ≥ 1 \widetilde{\alpha} \ge1 α ≥ 1 . This rate is effectively the largest Lyapunov exponent (LLE) of the approximate system. We further assume L L L -Lipschitz Jacobians, that the blocks are within ρ \rho ρ of the true Jacobians along the current trajectory error, and that each compression step in the scan introduces a relative error of at most η \eta η (Appendix § 9 ).
Theorem 2 (Local convergence with compressed scan). Suppose the assumptions above hold at every iteration i ≥ i 0 i \ge i_0 i ≥ i 0 . Then:
(i) Effective predictability. Compression raises the effective LLE from λ ~ \tilde{\lambda} λ ~ to λ c : = λ ~ + log ( 1 + a ~ 2 η ) \lambda_c := \tilde{\lambda} + \log(1 + \tilde{a}^{2}\eta) λ c := λ ~ + log ( 1 + a ~ 2 η ) .
(ii) One-step contraction. Suppose λ c < 0 \lambda_c < 0 λ c < 0 , and write ∥ e ∥ ∞ : = max t ∥ e t ∥ 2 \lVert e\rVert_\infty:= \max_t \lVert e_t\rVert_2 ∥ e ∥ ∞ := max t ∥ e t ∥ 2 . Then for every iteration i ≥ i 0 i \ge i_0 i ≥ i 0 ,
∥ e ( i + 1 ) ∥ ∞ ≤ ( c 0 + c 1 ∥ e ( i ) ∥ ∞ ) ∥ e ( i ) ∥ ∞ , \lVert e^{(i+1)}\rVert_\infty\le\left(c_0 + c_1\lVert e^{(i)}\rVert_\infty\right)\lVert e^{(i)}\rVert_\infty, ∥ e ( i + 1 ) ∥ ∞ ≤ ( c 0 + c 1 ∥ e ( i ) ∥ ∞ ) ∥ e ( i ) ∥ ∞ , where c 0 c_0 c 0 and c 1 c_1 c 1 are independent of T T T , with
c 0 : = a ~ ρ 1 − e λ c + 2 a ~ 3 η e λ ~ ( 1 − e λ ~ ) ( 1 − e λ c ) , c 1 : = a ~ L 2 ( 1 − e λ c ) . c_0 := \frac{\tilde{a}\rho}{1-e^{\lambda_c}}+\frac{2\tilde{a}^{3}\eta e^{\tilde{\lambda}}}{(1-e^{\tilde{\lambda}})(1-e^{\lambda_c})}, \qquad c_1 := \frac{\tilde{a}L}{2(1-e^{\lambda_c})}. c 0 := 1 − e λ c a ~ ρ + ( 1 − e λ ~ ) ( 1 − e λ c ) 2 a ~ 3 η e λ ~ , c 1 := 2 ( 1 − e λ c ) a ~ L . (iii) Local linear convergence. If c 0 < 1 c_0 < 1 c 0 < 1 and ∥ e ( i 0 ) ∥ ∞ < ( 1 − c 0 ) / c 1 \lVert e^{(i_0)}\rVert_\infty< (1-c_0)/c_1 ∥ e ( i 0 ) ∥ ∞ < ( 1 − c 0 ) / c 1 , then ∥ e ( i ) ∥ ∞ ≤ q i − i 0 ∥ e ( i 0 ) ∥ ∞ \lVert e^{(i)}\rVert_\infty\le q^{i-i_0}\lVert e^{(i_0)}\rVert_\infty ∥ e ( i ) ∥ ∞ ≤ q i − i 0 ∥ e ( i 0 ) ∥ ∞ for all i ≥ i 0 i \ge i_0 i ≥ i 0 , with q : = c 0 + c 1 ∥ e ( i 0 ) ∥ ∞ < 1 q := c_0+c_1\lVert e^{(i_0)}\rVert_\infty< 1 q := c 0 + c 1 ∥ e ( i 0 ) ∥ ∞ < 1 (proof in Appendix C).
Implications. First, for exact parallel Newton (ρ = η = 0 \rho=\eta=0 ρ = η = 0 ), c 0 = 0 c_0=0 c 0 = 0 and (ii) gives quadratic convergence. Any approximation makes c 0 > 0 c_0>0 c 0 > 0 , so our bound guarantees only a linear rate, even with exact Jacobians under compression. Second, the result is local: once the error falls below ( 1 − c 0 ) / c 1 (1-c_0)/c_1 ( 1 − c 0 ) / c 1 , the iteration count is independent of T T T , giving O ( log T ) O(\log T) O ( log T ) depth. We do not bound how long entering this region takes. When λ c ≥ 0 \lambda_c \ge0 λ c ≥ 0 , it may not exist or may shrink with T T T . Third, whereas prior analyses measure the quality of the block approximation by its spectral-norm error [22 ] , our bound depends on the block error along the current trajectory error, ρ \rho ρ , which is never larger than the spectral-norm error. Experiments on low-rank RNNs and hierarchical Gibbs sampling suggest that ρ \rho ρ is the quantity that matters (Appendix D): the spectral-norm error is essentially the same for all three methods, whereas near convergence ρ \rho ρ is ordered as Accelerated Parallel Broyden < Parallel Broyden < diagonal quasi-Newton, matching their iteration counts, and damping helps Parallel Broyden by reducing ρ \rho ρ but not the spectral-norm error. We note that the bound in (ii), however, is not tight.
Experiments
We study the efficacy of Parallel Broyden methods in three examples and find that for large enough state sizes and long enough sequences, these methods can be faster than sequential and parallel (quasi-) Newton methods.
Controlled experiments on RNNs
We begin with controlled experiments designed to understand when and why Parallel Broyden methods help, by varying the Jacobian’s structure and the cost of computing it independently. Our starting point is a family of low-rank RNNs whose Jacobians are exactly DPLR. We consider dynamics of the form,
x t = a x t − 1 + Δ t τ M ψ ( N T ϕ ( x t − 1 ) ) + ϵ t , x_t = a x_{t-1} + \frac{\Delta t}{\tau}M\psi\left(N^\mathsf{T}\phi(x_{t-1})\right)+\epsilon_t, x t = a x t − 1 + τ Δ t M ψ ( N T ϕ ( x t − 1 ) ) + ϵ t ,
where x t ∈ R D x_t \in\mathbb{R}^{D} x t ∈ R D , a = 1 − Δ t / τ a=1-\Delta t/\tau a = 1 − Δ t / τ , ϕ ( ⋅ ) = tanh ( ⋅ ) \phi(\cdot)=\tanh(\cdot) ϕ ( ⋅ ) = tanh ( ⋅ ) is applied elementwise, M , N ∈ R D × R M,N\in\mathbb{R}^{D\times R} M , N ∈ R D × R with R ≪ D R\ll D R ≪ D , and ψ : R R → R R \psi:\mathbb{R}^{R}\to\mathbb{R}^{R} ψ : R R → R R acts in the R R R -dimensional bottleneck. Fixing the noise sequence { ϵ t } \{\epsilon_t\} { ϵ t } turns the model into a deterministic input-driven state-space model. We consider two choices of ψ \psi ψ : the standard low-rank RNN, widely used in computational neuroscience [35 , 36 , 37 ] , with ψ ( z ) = z \psi(z)=z ψ ( z ) = z , and a variant we construct for this study, the MLP-RNN, with ψ ( z ) = z + β MLP ( z ) \psi(z)=z+\beta\operatorname{MLP}(z) ψ ( z ) = z + β MLP ( z ) , where the MLP has 8 hidden layers of width D D D and β = 0.5 \beta=0.5 β = 0.5 . In both cases, the transition Jacobian A t ( x t − 1 ) = a I D + Δ t τ M J ψ ( N T ϕ ( x t − 1 ) ) N T diag ( ϕ ′ ( x t − 1 ) ) A_t(x_{t-1})=aI_D+\frac{\Delta t}{\tau}M J_\psi\left(N^\mathsf{T}\phi(x_{t-1})\right)N^\mathsf{T}\operatorname{diag}\left(\phi'(x_{t-1})\right) A t ( x t − 1 ) = a I D + τ Δ t M J ψ ( N T ϕ ( x t − 1 ) ) N T diag ( ϕ ′ ( x t − 1 ) ) is diagonal plus rank at most R R R . The true Jacobian therefore exists exactly in the approximation class targeted by Parallel Broyden, whereas diagonal quasi-Newton discards the low-rank coupling term. In these experiments, we treat the dynamics f f f as a black box, as in DEER [18 ] : methods may evaluate f f f , and Newton and diagonal quasi-Newton obtain exact Jacobian information (the full Jacobian, or its exact diagonal) by automatic differentiation of f f f , rather than from closed-form expressions specific to the model or from approximations to it. This keeps the comparison general: closed-form Jacobians are rarely available for learned or complex dynamics, and approximate Jacobian information can be unreliable on some problems (cf. § 4.2 ). Under this assumption, Jacobian information is cheap for the standard low-rank RNN but expensive for the MLP-RNN, where it requires differentiating through the MLP. Both Broyden variants, in contrast, only require evaluations of f f f . We use R = 3 R = 3 R = 3 , τ = 10 \tau= 10 τ = 10 , D = 200 D = 200 D = 200 , and Broyden rank m = R m = R m = R . Details are given in Appendix § 12 .§ 1 .
We assess convergence and runtime on 32 random realizations as we vary the trajectory length T T T (Figure 1 , left and middle). In both the standard and MLP models, iteration counts follow the same ordering at every T T T : diagonal quasi-Newton > > > Parallel Broyden > > > Accelerated Parallel Broyden > > > Newton. Both Broyden variants thus capture much of the off-diagonal coupling that diagonal quasi-Newton misses, and the multisecant updates of Accelerated Parallel Broyden capture it even more effectively. The gap between the two Broyden variants depends on the strength of the off-diagonal coupling relative to the diagonal. With Δ t = 0.5 \Delta t = 0.5 Δ t = 0.5 (a = 0.95 a = 0.95 a = 0.95 ), Parallel Broyden needs only 1.25–1.4× as many iterations as the accelerated variant. With Δ t = 3 \Delta t = 3 Δ t = 3 (a = 0.7 a = 0.7 a = 0.7 ), it needs 2.1–2.7× as many, and it more often fails to converge within 1000 iterations (5 of 32 realizations vs. at most 1 of 32 for the accelerated variant). The same pattern holds for each model at both values of Δ t \Delta t Δ t (Appendix § 12 .§ 1 ). Parallel Broyden therefore closes most of the gap with the accelerated variant when off-diagonal coupling is weak.
Figure 1. Low-rank and full-rank RNNs. Left, middle: Standard (Δ t = 0.5 \Delta t = 0.5 Δ t = 0.5 ) and MLP (Δ t = 3 \Delta t = 3 Δ t = 3 ) low-rank RNNs (R = 3 R = 3 R = 3 , D = 200 D = 200 D = 200 ), as T T 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 D = 128 D = 128 , T = 10 4 T = 10^4 T = 1 0 4 ) as the Broyden rank m m m varies. Methods without a rank parameter are shown as horizontal lines. Accelerated Parallel Broyden is shown only up to m = 20 m = 20 m = 20 , as for larger m m m it becomes numerically unstable or fails to converge. Larger m m 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.
Whether this ordering carries over to runtime depends on the cost of Jacobian information. For the standard low-rank RNN, differentiating the dynamics is so cheap that diagonal quasi-Newton iterations take about 1 ms, compared with about 20 ms for Accelerated Parallel Broyden at T = 100 T = 100 T = 100 K. Diagonal quasi-Newton is therefore the fastest method despite requiring 2–3× more iterations, running about 7.7× faster than Accelerated Parallel Broyden at T = 100 T = 100 T = 100 K. For the MLP-RNN, the per-iteration cost of both Broyden variants changes little, whereas diagonal quasi-Newton becomes about 400× more expensive per iteration, and Newton, whose cost is already dominated by its dense D × D D \times D D × D scan, becomes 5–6× more expensive. The iteration ordering then translates directly into runtime, and Accelerated Parallel Broyden is the fastest method at every T T T . At T = 100 T = 100 T = 100 K, it is 7.0× faster than sequential evaluation, 5.5× faster than Newton, 1.8× faster than Parallel Broyden, and 56× faster than diagonal quasi-Newton.
Finally, we ask how our methods perform in an unfavorable case, where the Jacobian is far from DPLR. We consider a full-rank discretized mean-field (DMF) RNN [38 ] , x t = W tanh ( x t − 1 ) + ϵ t x_t = W \tanh(x_{t-1}) + \epsilon_t x t = W tanh ( x t − 1 ) + ϵ t with W i j ∼ N ( 0 , g 2 / D ) W_{ij} \sim\mathcal{N}(0, g^2/D) W ij ∼ N ( 0 , g 2 / D ) , g = 1.7 g = 1.7 g = 1.7 , and D = 128 D = 128 D = 128 . Its Jacobian is dense with no dominant diagonal, and its singular values decay slowly rather than sharply (Appendix § 12 .§ 2 ). We sweep the Broyden rank m m m at T = 10 K T = 10\mathrm{K} T = 10 K (Figure 1 , right). Performance degrades gracefully: iteration counts fall steadily with m m m before plateauing, from 249 at m = 1 m = 1 m = 1 to 63 for m ≥ 60 m \ge60 m ≥ 60 for Parallel Broyden, and from 138 to about 70 by m = 15 m = 15 m = 15 for the accelerated variant. The secant corrections therefore still capture real structure even when the spectrum does not decay sharply, and for m ≥ 5 m \ge5 m ≥ 5 both variants need fewer iterations than diagonal quasi-Newton. Accelerated Parallel Broyden needs fewer iterations than Parallel Broyden at every rank where both are run, but it cannot use arbitrarily large m m m . Beyond m = 20 m = 20 m = 20 , we observed that the most recent m m m steps become nearly linearly dependent, so the Gram matrix of the multisecant update becomes ill-conditioned and the method becomes numerically very unstable. The question is whether the iterations saved by the secant corrections are worth their extra per-iteration cost. Because the per-iteration cost grows rapidly with m m m , the modest reduction in iterations does not pay off: runtime increases with m m m , and for m ≥ 5 m \ge5 m ≥ 5 both variants are slower than every baseline. The fastest Broyden configuration (accelerated, m = 1 m = 1 m = 1 ) is only 1.4× faster than sequential evaluation, while diagonal quasi-Newton is fastest (4.1×). Parallel Broyden variants are thus most advantageous when a small rank already improves substantially on diagonal quasi-Newton, which happens when the off-diagonal part of the Jacobian has sharply decaying singular values, as in the low-rank RNN.
Gibbs sampling for hierarchical models
Recently, Zoltowski et al. [29 ] showed that parallel Newton methods can be applied to simulating Markov Chain Monte Carlo algorithms, leading to substantial improvements in runtime. We show that Parallel Broyden methods can further accelerate performance. We study the eight schools problem, a standard example in Bayesian hierarchical modeling [39 , 40 ] . We observe test scores from N N N students in each of S S S schools according to the hierarchical model,
y s , n ∣ θ s , σ s 2 ∼ N ( θ s , σ s 2 ) , θ s ∣ μ , τ 2 ∼ N ( μ , τ 2 ) . y_{s,n} \mid\theta_s, \sigma_s^2 \sim\mathcal{N}(\theta_s, \sigma_s^2), \qquad\theta_s \mid\mu, \tau^2 \sim\mathcal{N}(\mu, \tau^2). y s , n ∣ θ s , σ s 2 ∼ N ( θ s , σ s 2 ) , θ s ∣ μ , τ 2 ∼ N ( μ , τ 2 ) .
The model also has a global prior on μ \mu μ , τ 2 \tau^2 τ 2 , and σ s 2 \sigma_s^2 σ s 2 . The state of the MCMC chain at iteration t t t is x t = ( θ 1 : S , t , σ 1 : S , t 2 , μ t , τ t 2 ) ∈ R 2 S + 2 x_t = (\theta_{1:S,t}, \sigma_{1:S,t}^2, \mu_t, \tau_t^2) \in\mathbb{R}^{2S+2} x t = ( θ 1 : S , t , σ 1 : S , t 2 , μ t , τ t 2 ) ∈ R 2 S + 2 . A Gibbs sampler iteratively updates each state variable by sampling from its conditional distribution. Fixing the random numbers used in the conditional updates turns the sampler into a deterministic input-driven state-space model, x t + 1 = f t ( x t ) x_{t+1} = f_t(x_t) x t + 1 = f t ( x t ) , where one transition corresponds to a full Gibbs sweep. Details are given in Appendix § 13 .
This model provides a setting where the useful Jacobian structure is low-rank rather than diagonal. Cross-school coupling is mediated primarily by the two global variables μ \mu μ and τ 2 \tau^2 τ 2 , which aggregate information from the school-level variables and broadcast it back through the conditional updates. Thus, the dominant off-diagonal structure has low effective rank, with rank two providing a natural approximation. Meanwhile, Gibbs updates resample variables from their conditional distributions, so the diagonal entries of the dynamics Jacobian are small (Appendix § 13 ). Motivated by this structure, we set the diagonal term to zero for Parallel Broyden variants and use rank m = 2 m = 2 m = 2 , matching the two global variables ( μ , τ 2 ) (\mu, \tau^2) ( μ , τ 2 ) . In this purely low-rank setting, no rank compression is required.
We evaluate all methods on 32 random problem instances, each with independently sampled observations and initialization, as we vary the trajectory length T T T and state dimension D = 2 S + 2 D = 2S + 2 D = 2 S + 2 (Figure 2 ). The two baselines fail in opposite ways. Exact Newton captures the coupling and uses the fewest iterations, but its dense Jacobian cost grows cubically with D D D , and it runs out of memory at the largest settings. Diagonal quasi-Newton neglects the dominant hierarchical coupling, so it requires many more iterations, and since obtaining its exact diagonal still requires forming the full D × D D \times D D × D Jacobian, at S ≥ 100 S \ge100 S ≥ 100 it is no faster than sequential evaluation. This cost can be avoided with the Hutchinson estimator [41 ] , which estimates the diagonal from a few Jacobian-vector products without forming the Jacobian, as in recent quasi-Newton approaches for parallel MCMC [29 ] . Here, however, this estimate causes the iterations to fail to converge (Appendix § 13 ).
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 T T and state dimension D = 2 S + 2 D = 2S + 2 D = 2 S + 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 S S or short T T T ). It also remains applicable at the largest settings, where exact Newton runs out of memory.
Both Parallel Broyden variants need fewer iterations than diagonal quasi-Newton in every setting, indicating that the low-rank secant corrections capture the cross-school coupling. Accelerated Parallel Broyden needs 2.3–4.2× fewer iterations still than Parallel Broyden and is the fastest approximate method throughout. Exact Newton remains fastest only for small problems (e.g., S = 10 S = 10 S = 10 with T ≤ 50 K T \le50\mathrm{K} T ≤ 50 K ). Elsewhere, Accelerated Parallel Broyden is fastest overall, with an advantage that grows with T T T and D D D . At S = 100 S = 100 S = 100 and T = 100 T = 100 T = 100 K, it is 5.5× \times × faster than exact Newton and 30× \times × faster than sequential evaluation. At S = 200 S = 200 S = 200 , both Broyden variants beat every baseline at every T T T and remain applicable after exact Newton runs out of memory. At T = 100 T = 100 T = 100 K, Accelerated Parallel Broyden is 24.7× \times × faster than sequential evaluation and 41× \times × faster than diagonal quasi-Newton.
Denoising diffusion models
We finally consider parallelizing diffusion sampling with a pretrained DiT image denoiser, a transformer-based diffusion model over image patches [42 ] . We use DDIM sampling [9 ] , which evolves a noisy latent toward a clean image through deterministic denoising updates
s t − 1 = c x ( t ) s t + c ϵ ( t ) ϵ θ ( s t , t ) . s_{t-1} = c_x(t)s_t + c_\epsilon(t)\epsilon_\theta(s_t,t). s t − 1 = c x ( t ) s t + c ϵ ( t ) ϵ θ ( s t , t ) .
Re-indexing in forward time, we write this as a time-indexed state-space model x ℓ = f ℓ ( x ℓ − 1 ) x_\ell= f_\ell(x_{\ell-1}) x ℓ = f ℓ ( x ℓ − 1 ) with t = T − ℓ + 1 t = T - \ell+ 1 t = T − ℓ + 1 . The state dimension is D = 4096 D = 4096 D = 4096 . The main challenge is Jacobian evaluation. The local dynamics Jacobian block is A ℓ ( x ℓ − 1 ) = c x ( t ) I + c ϵ ( t ) ∂ ϵ θ ∂ x ( x ℓ − 1 , t ) A_\ell(x_{\ell-1}) = c_x(t)I + c_\epsilon(t)\frac{\partial\epsilon_\theta}{\partial x}(x_{\ell-1},t) A ℓ ( x ℓ − 1 ) = c x ( t ) I + c ϵ ( t ) ∂ x ∂ ϵ θ ( x ℓ − 1 , t ) , so exact Newton would require differentiating through the full DiT denoiser at each time step, which is prohibitively expensive at this scale. Since A ℓ A_\ell A ℓ is moreover dominated by its diagonal (Appendix § 14 .§ 1 ), this benchmark tests whether a good approximation can be obtained without differentiating through the denoiser, rather than whether a richer one reduces iterations.
We compare against two recent parallel diffusion samplers. The first is Picard iteration [26 ] , which corresponds in our formulation to using the identity local approximation A ~ ℓ = I D \widetilde{A}_\ell= I_D A ℓ = I D [22 ] . The second is ParaTAA [27 ] , which uses multisecant conditions to approximate the full inverse residual Jacobian J − 1 J^{-1} J − 1 . In contrast, Parallel Broyden approximates the local dynamics blocks A ℓ A_\ell A ℓ used in the scan. Implementation details and hyperparameter searches for all methods are given in Appendix § 14 .
Figure 3 reports iteration counts and wall-clock runtimes for 50-step DDIM sampling with the pretrained …
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 (± \pm ± 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.
The runtime comparison highlights the cost of obtaining the Jacobian approximation. Diagonal quasi-Newton estimates the diagonal of A ℓ A_\ell A ℓ with a single-probe Hutchinson estimator, which still requires one Jacobian-vector product through the denoiser per time step and iteration, making it the slowest parallel method. Picard iteration avoids differentiation but needs more iterations. Parallel Broyden avoids both costs and achieves the fastest parallel runtime: 3.32 × 3.32\times 3.32 × faster than diagonal quasi-Newton, 1.12 × 1.12\times 1.12 × faster than Picard, and 1.53 × 1.53\times 1.53 × faster than ParaTAA, with Accelerated Parallel Broyden performing similarly. Its advantage here therefore comes from avoiding automatic differentiation rather than from a richer Jacobian approximation. Upon convergence, all methods produce images that are visually indistinguishable from the sequential reference (Appendix § 14 .6).
All parallel methods remain slower than sequential DDIM on a single H100 GPU, because evaluating the DiT denoiser across many timesteps in parallel quickly becomes FLOP-bound. Prior work therefore uses multiple GPUs to amortize these evaluations [26 , 27 ] , where fewer outer iterations directly mean fewer rounds of parallel denoiser evaluations.
Conclusion
We introduced Parallel Broyden, a family of Broyden-style quasi-Newton methods that build diagonal-plus-low-rank approximations of local dynamics Jacobian blocks from trajectory secants. By avoiding automatic differentiation while remaining compatible with parallel scan through rank compression, Parallel Broyden provides a more scalable alternative to exact parallel Newton in high dimensions and a richer approximation class than diagonal quasi-Newton methods. We proved finite-step recovery under the compressed scan, and showed that convergence is tracked by the compression error and by the block approximation error along the current trajectory error, rather than in spectral norm.
In our experiments, Parallel Broyden reduces iterations relative to diagonal quasi-Newton when coupling is approximately low rank, and improves runtime when dense Jacobian operations or automatic differentiation are costly. The multisecant Accelerated Parallel Broyden variant is often strongest, consistent with its observed smaller block error along the current error near convergence.
Several limitations remain. Parallel Broyden is designed for dynamics whose dominant off-diagonal Jacobian structure can be captured with a small number of low-rank corrections. When accurate approximations require large rank, the advantage diminishes, as scan and compression costs grow with rank. Moreover, our convergence analysis is local and conservative. Relating block error along the current trajectory error to the secant updates is a natural next step. Beyond the settings studied here, DPLR structure also arises when a few global variables mediate interactions among many local ones, as in mean-field coupled oscillators, and Jacobian-free methods suit neural ODEs and black-box simulators, where Jacobians are costly or unavailable. These are promising applications for future work. More broadly, the compressed approximate scan applies to any DPLR block approximation, including autodiff-based sketches when differentiation is affordable.
Acknowledgments
We thank Xavier Gonzalez and the other members of the Linderman Lab for helpful feedback throughout this project, and Leo Kozachkov for valuable insights into the asymptotic theory of Newton’s method. S.W.L. is supported by grants from the NIH (U01NS136507, R01NS131987, RF1MH133778, R01AG097491, & R01NS130789), the NSF (2440859), and the Simons and McKnight Foundations.
Overview of Parallel Broyden
Effect of rank compression
Our compressed approximate scan keeps diagonal-plus-low-rank (DPLR) factors at fixed rank by compressing the low-rank correction after each scan merge. This compression is necessary to prevent rank growth in long trajectories, but it also raises two questions. First, does compression preserve the finite-step trajectory recovery property of scan-based Newton methods? Second, how does the chosen compression rank affect convergence and runtime in practice?
We address these questions in three steps. First, we prove that finite-step trajectory recovery is preserved under the compressed approximate scan. Second, we describe two compression schemes: an exact small-SVD compression and a randomized factorized compression that avoids forming dense matrices. Third, we empirically study how the compression rank affects convergence and runtime on the low-rank RNN benchmark.
Proof of Theorem 1
Theorem 1 (Global convergence with approximate scan). Starting from any initial trajectory x 1 : T ( 0 ) x_{1:T}^{(0)} x 1 : T ( 0 ) after i i i iterations using the approximate parallel scan with low-rank compression, we have x t ( i ) = x t ∗ x_t^{(i)} = x_t^* x t ( i ) = x t ∗ for all t ≤ i t \le i t ≤ i . In particular, the method recovers the exact trajectory x 1 : T ∗ x_{1:T}^* x 1 : T ∗ in at most T T T iterations.
Proof. Recursion. At iteration i i i , let A ~ t ( i ) \widetilde{A}^{(i)}_t A t ( i ) denote the approximate dynamics Jacobian block used in place of
A t ( i ) = ∂ f t ∂ x t − 1 ( x t − 1 ( i ) ) . A^{(i)}_t = \frac{\partial f_t}{\partial x_{t-1}}\left(x^{(i)}_{t-1}\right). A t ( i ) = ∂ x t − 1 ∂ f t ( x t − 1 ( i ) ) .
The approximate Newton update solves the linear recurrence
Δ x 1 ( i + 1 ) = − r 1 ( x 1 : T ( i ) ) , Δ x t ( i + 1 ) = A ~ t ( i ) Δ x t − 1 ( i + 1 ) − r t ( x 1 : T ( i ) ) , t > 1. (5) \Delta x^{(i+1)}_1 = -r_1\left(x^{(i)}_{1:T}\right), \qquad\Delta x^{(i+1)}_t = \widetilde{A}^{(i)}_t \Delta x^{(i+1)}_{t-1} - r_t\left(x^{(i)}_{1:T}\right), \qquad t > 1. \tag*{(5)} Δ x 1 ( i + 1 ) = − r 1 ( x 1 : T ( i ) ) , Δ x t ( i + 1 ) = A t ( i ) Δ x t − 1 ( i + 1 ) − r t ( x 1 : T ( i ) ) , t > 1. (5)
Compressed scan. Each position t t t is represented by an affine summary
( M t , c t ) , M t = A ~ t ( i ) , c t = − r t ( x 1 : T ( i ) ) , (M_t, c_t), \qquad M_t = \widetilde{A}^{(i)}_t, \qquad c_t = -r_t\left(x^{(i)}_{1:T}\right), ( M t , c t ) , M t = A t ( i ) , c t = − r t ( x 1 : T ( i ) ) ,
corresponding to the local update rule
x ↦ M t x + c t . x \mapsto M_t x + c_t. x ↦ M t x + c t .
The compressed scan combines two adjacent summaries ( M a , c a ) (M_a, c_a) ( M a , c a ) and ( M b , c b ) (M_b, c_b) ( M b , c b ) by
( M b , c b ) ⋆ ( M a , c a ) : = ( Comp ( M b M a ) , M b c a + c b ) , (6) (M_b, c_b) \star(M_a, c_a) := \left(\operatorname{Comp}(M_b M_a), M_b c_a + c_b\right), \tag*{(6)} ( M b , c b ) ⋆ ( M a , c a ) := ( Comp ( M b M a ) , M b c a + c b ) , (6)
where Comp ( ⋅ ) \operatorname{Comp}(\cdot) Comp ( ⋅ ) denotes low-rank compression of the matrix part. Because of compression, this merge need not equal exact affine composition and need not be associative. The only property we use is that compression is applied only to the matrix component, while the offset component is updated by
c n e w = M b c a + c b . c_{\mathrm{new}} = M_b c_a + c_b. c new = M b c a + c b .
The scan returns, for each prefix 1 : t 1:t 1 : t , an affine summary
( M 1 : t , c 1 : t ) , (M_{1:t}, c_{1:t}), ( M 1 : t , c 1 : t ) ,
obtained from the leaf summaries by a binary tree of merges (6) , each combining the summaries of two adjacent segments. This holds for standard scan algorithms, and we make no other assumption on the shape of the tree. The update is recovered from the returned offset:
Δ x t ( i + 1 ) = c 1 : t . (7) \Delta x^{(i+1)}_t = c_{1:t}. \tag*{(7)} Δ x t ( i + 1 ) = c 1 : t . (7)
Induction. We prove by induction on i i i that
x t ( i ) = x t ∗ for all t ≤ i . x^{(i)}_t = x^*_t \qquad\text{for all } t \le i. x t ( i ) = x t ∗ for all t ≤ i .
Initialization. Since x 0 x_0 x 0 and f 1 f_1 f 1 are fixed, x 1 ∗ = f 1 ( x 0 ) x^*_1 = f_1(x_0) x 1 ∗ = f 1 ( x 0 ) . The prefix at position 1 is a leaf, so no merge or compression is applied and
Δ x 1 ( 1 ) = c 1 = − r 1 ( x 1 : T ( 0 ) ) = − ( x 1 ( 0 ) − f 1 ( x 0 ) ) . \Delta x^{(1)}_1 = c_1 = -r_1\left(x^{(0)}_{1:T}\right) = -\left(x^{(0)}_1 - f_1(x_0)\right). Δ x 1 ( 1 ) = c 1 = − r 1 ( x 1 : T ( 0 ) ) = − ( x 1 ( 0 ) − f 1 ( x 0 ) ) .
Therefore
x 1 ( 1 ) = x 1 ( 0 ) + Δ x 1 ( 1 ) = f 1 ( x 0 ) = x 1 ∗ . x^{(1)}_1 = x^{(0)}_1 + \Delta x^{(1)}_1 = f_1(x_0) = x^*_1. x 1 ( 1 ) = x 1 ( 0 ) + Δ x 1 ( 1 ) = f 1 ( x 0 ) = x 1 ∗ .
Inductive step. Assume that
x t ( i ) = x t ∗ for all t ≤ i . x^{(i)}_t = x^*_t \qquad\text{for all } t \le i. x t ( i ) = x t ∗ for all t ≤ i .
Then for every t ≤ i t \le i t ≤ i ,
r t ( x 1 : T ( i ) ) = x t ( i ) − f t ( x t − 1 ( i ) ) = x t ∗ − f t ( x t − 1 ∗ ) = 0. r_t\left(x^{(i)}_{1:T}\right) = x^{(i)}_t - f_t\left(x^{(i)}_{t-1}\right) = x^*_t - f_t\left(x^*_{t-1}\right) = 0. r t ( x 1 : T ( i ) ) = x t ( i ) − f t ( x t − 1 ( i ) ) = x t ∗ − f t ( x t − 1 ∗ ) = 0.
Hence the corresponding leaf offsets satisfy
c t = − r t ( x 1 : T ( i ) ) = 0 for all t ≤ i . c_t = -r_t\left(x^{(i)}_{1:T}\right) = 0 \qquad\text{for all } t \le i. c t = − r t ( x 1 : T ( i ) ) = 0 for all t ≤ i .
Now consider any prefix contained entirely in [ 1 , i ] [1, i] [ 1 , i ] . Every leaf in this prefix has zero offset. Moreover, if two summaries have zero offsets, then their compressed merge also has zero offset:
c a = 0 , c b = 0 ⟹ c n e w = M b c a + c b = 0 , c_a = 0,\qquad c_b = 0 \quad\Longrightarrow\quad c_{\mathrm{new}} = M_b c_a + c_b = 0, c a = 0 , c b = 0 ⟹ c new = M b c a + c b = 0 ,
regardless of the compressed matrix part. By induction over the scan tree, every prefix summary over [ 1 , t ] [1,t] [ 1 , t ] with t ≤ i t \le i t ≤ i therefore has offset
c 1 : t = 0. c_{1:t}=0. c 1 : t = 0.
Using (7) , this gives
Δ x t ( i + 1 ) = 0 for all t ≤ i , \Delta x_t^{(i+1)}=0 \qquad\text{for all } t \le i, Δ x t ( i + 1 ) = 0 for all t ≤ i ,
and hence
x t ( i + 1 ) = x t ( i ) = x t ⋆ for all t ≤ i . x_t^{(i+1)}=x_t^{(i)}=x_t^\star\qquad\text{for all } t \le i. x t ( i + 1 ) = x t ( i ) = x t ⋆ for all t ≤ i .
It remains to show that state i + 1 i+1 i + 1 is recovered. The scan may build the prefix 1 : i + 1 1:i+1 1 : i + 1 from segments of any shape, so we prove a claim about every segment that the scan forms inside [ 1 , i + 1 ] [1,i+1] [ 1 , i + 1 ] .
Claim. Let ( M , c ) (M,c) ( M , c ) be the summary that the scan forms for a segment { p , … , q } \{p,\ldots,q\} { p , … , q } with q ≤ i + 1 q \le i+1 q ≤ i + 1 . Then c = 0 c=0 c = 0 if q ≤ i q \le i q ≤ i , and c = c i + 1 c=c_{i+1} c = c i + 1 if q = i + 1 q=i+1 q = i + 1 .
Proof of the claim. By induction over the scan tree. For a leaf { q } \{q\} { q } , the offset is c q c_q c q , which is 0 0 0 if q ≤ i q \le i q ≤ i and c i + 1 c_{i+1} c i + 1 if q = i + 1 q=i+1 q = i + 1 . Now consider a merge of a left segment a = { p , … , m } a=\{p,\ldots,m\} a = { p , … , m } and a right segment b = { m + 1 , … , q } b=\{m+1,\ldots,q\} b = { m + 1 , … , q } . Since m < q ≤ i + 1 m<q \le i+1 m < q ≤ i + 1 , we have m ≤ i m \le i m ≤ i , so c a = 0 c_a=0 c a = 0 by the inductive hypothesis. Hence
c n e w = M b c a + c b = c b , c_{\mathrm{new}}=M_b c_a+c_b=c_b, c new = M b c a + c b = c b ,
whatever the compressed matrix M b M_b M b is. Segment b b b ends at q q q , so c b c_b c b , and therefore c n e w c_{\mathrm{new}} c new , is as claimed.
Applying the claim to the prefix 1 : i + 1 1:i+1 1 : i + 1 gives
c 1 : i + 1 = c i + 1 = − r i + 1 ( x 1 : T ( i ) ) . c_{1:i+1}=c_{i+1}=-r_{i+1}\left(x_{1:T}^{(i)}\right). c 1 : i + 1 = c i + 1 = − r i + 1 ( x 1 : T ( i ) ) .
so, by (7) ,
Δ x i + 1 ( i + 1 ) = − ( x i + 1 ( i ) − f i + 1 ( x i ( i ) ) ) . \Delta x_{i+1}^{(i+1)}=-\left(x_{i+1}^{(i)}-f_{i+1}\left(x_i^{(i)}\right)\right). Δ x i + 1 ( i + 1 ) = − ( x i + 1 ( i ) − f i + 1 ( x i ( i ) ) ) .
By the induction hypothesis, x i ( i ) = x i ⋆ x_i^{(i)}=x_i^\star x i ( i ) = x i ⋆ , so
Δ x i + 1 ( i + 1 ) = − ( x i + 1 ( i ) − f i + 1 ( x i ⋆ ) ) = x i + 1 ⋆ − x i + 1 ( i ) . \Delta x_{i+1}^{(i+1)}=-\left(x_{i+1}^{(i)}-f_{i+1}\left(x_i^\star\right)\right)=x_{i+1}^\star-x_{i+1}^{(i)}. Δ x i + 1 ( i + 1 ) = − ( x i + 1 ( i ) − f i + 1 ( x i ⋆ ) ) = x i + 1 ⋆ − x i + 1 ( i ) .
Thus
x i + 1 ( i + 1 ) = x i + 1 ( i ) + Δ x i + 1 ( i + 1 ) = x i + 1 ⋆ . x_{i+1}^{(i+1)}=x_{i+1}^{(i)}+\Delta x_{i+1}^{(i+1)}=x_{i+1}^\star. x i + 1 ( i + 1 ) = x i + 1 ( i ) + Δ x i + 1 ( i + 1 ) = x i + 1 ⋆ .
Therefore, after iteration i + 1 i+1 i + 1 , the first i + 1 i+1 i + 1 states are exact. By induction, after i i i iterations we have x t ( i ) = x t ⋆ x_t^{(i)}=x_t^\star x t ( i ) = x t ⋆ for all t ≤ i t \le i t ≤ i , and the full trajectory is recovered in at most T T T iterations.
Compression schemes
During the compressed approximate scan, composing two rank-at-most m m m DPLR blocks produces a new DPLR block whose low-rank correction has rank at most 2 m 2m 2 m . Thus, after each merge, we need to compress a factorized correction
Δ = U V ⊤ , U , V ∈ R D × r , r ≤ 2 m , \Delta=UV^\top,\qquad U,V\in\mathbb{R}^{D\times r},\qquad r\le2m, Δ = U V ⊤ , U , V ∈ R D × r , r ≤ 2 m ,
back to rank at most m m m . We consider two compression schemes: an exact best-rank-m m m compression based on a small SVD, and a randomized factorized compression that avoids computing an SVD.
Exact compression via a small SVD. The exact compression computes the best rank-m m m approximation to Δ = U V ⊤ \Delta=UV^\top Δ = U V ⊤ in Frobenius norm. By the Eckart–Young–Mirsky theorem [43 , 44 ] , this approximation is obtained by truncating the singular value decomposition of Δ \Delta Δ . Since Δ \Delta Δ has rank at most r ≤ 2 m r\le2m r ≤ 2 m , this SVD can be computed without forming the dense D × D D\times D D × D matrix.
Let
U = Q U R U , V = Q V R V U=Q_U R_U,\qquad V=Q_V R_V U = Q U R U , V = Q V R V
be thin QR decompositions, where
Q U , Q V ∈ R D × r , R U , R V ∈ R r × r . Q_U,Q_V\in\mathbb{R}^{D\times r},\qquad R_U,R_V\in\mathbb{R}^{r\times r}. Q U , Q V ∈ R D × r , R U , R V ∈ R r × r .
Then
Δ = U V ⊤ = Q U R U R V ⊤ Q V ⊤ . \Delta=UV^\top=Q_U R_U R_V^\top Q_V^\top. Δ = U V ⊤ = Q U R U R V ⊤ Q V ⊤ .
Define the small core matrix
C : = R U R V T ∈ R r × r . C := R_U R_V^{\mathsf T} \in\mathbb{R}^{r \times r}. C := R U R V T ∈ R r × r .
We compute its SVD
C = U ˉ Σ ˉ V ˉ T . C = \bar{U}\bar{\Sigma}\bar{V}^{\mathsf T}. C = U ˉ Σ ˉ V ˉ T .
Since Q U Q_U Q U and Q V Q_V Q V have orthonormal columns, this gives an SVD of the rank-r r r correction:
Δ = ( Q U U ˉ ) Σ ˉ ( Q V V ˉ ) T . \Delta= (Q_U\bar{U})\bar{\Sigma}(Q_V\bar{V})^{\mathsf T}. Δ = ( Q U U ˉ ) Σ ˉ ( Q V V ˉ ) T .
Let U ˉ m \bar{U}_m U ˉ m , V ˉ m \bar{V}_m V ˉ m denote the first m m m singular vectors and let Σ ˉ m \bar{\Sigma}_m Σ ˉ m contain the top m m m singular values. The best rank-m m m approximation is therefore
Δ m = ( Q U U ˉ m ) Σ ˉ m ( Q V V ˉ m ) T . \Delta_m = (Q_U\bar{U}_m)\bar{\Sigma}_m(Q_V\bar{V}_m)^{\mathsf T}. Δ m = ( Q U U ˉ m ) Σ ˉ m ( Q V V ˉ m ) T .
Equivalently, we store it in factored form as
Δ m = U ~ V ~ T , U ~ : = Q U U ˉ m Σ ˉ m , V ~ : = Q V V ˉ m . \Delta_m = \widetilde{U}\widetilde{V}^{\mathsf T}, \qquad\widetilde{U} := Q_U\bar{U}_m\bar{\Sigma}_m, \qquad\widetilde{V} := Q_V\bar{V}_m. Δ m = U V T , U := Q U U ˉ m Σ ˉ m , V := Q V V ˉ m .
This compression is optimal among all rank-m m m approximations:
Δ m = arg min rank ( B ) ≤ m ∥ Δ − B ∥ F . \Delta_m = \underset{\operatorname{rank}(B)\le m}{\arg\min}\ \lVert\Delta- B\rVert_F. Δ m = rank ( B ) ≤ m arg min ∥ Δ − B ∥ F .
The cost is dominated by the two thin QR decompositions and the small SVD. For r ≤ 2 m r \le2m r ≤ 2 m , the QR decompositions cost O ( D r 2 ) \mathcal{O}(Dr^2) O ( D r 2 ) , the core SVD costs O ( r 3 ) \mathcal{O}(r^3) O ( r 3 ) , and forming the compressed factors costs O ( D r m ) \mathcal{O}(Drm) O ( D r m ) . Thus the total cost is
O ( D m 2 + m 3 ) , \mathcal{O}(Dm^2 + m^3), O ( D m 2 + m 3 ) ,
with memory O ( D m ) \mathcal{O}(Dm) O ( D m ) for the compressed factors.
Randomized factorized compression. The randomized compression avoids the small SVD and compresses directly in factorized form. Given
Δ = U V T , U , V ∈ R D × r , r ≤ 2 m , \Delta= UV^{\mathsf T}, \qquad U,V \in\mathbb{R}^{D \times r}, \qquad r \le2m, Δ = U V T , U , V ∈ R D × r , r ≤ 2 m ,
we draw a Gaussian test matrix
Ω ∈ R D × m \Omega\in\mathbb{R}^{D \times m} Ω ∈ R D × m
and form the sketch
Y = Δ Ω = U ( V T Ω ) ∈ R D × m . Y = \Delta\Omega= U(V^{\mathsf T}\Omega) \in\mathbb{R}^{D \times m}. Y = ΔΩ = U ( V T Ω ) ∈ R D × m .
We then compute a thin QR decomposition
Y = Q R , Q ∈ R D × m , Y = QR, \qquad Q \in\mathbb{R}^{D \times m}, Y = QR , Q ∈ R D × m ,
so that the columns of Q Q Q approximate the dominant column space of Δ \Delta Δ . Projecting Δ \Delta Δ onto this subspace gives
Δ ≈ Q Q T Δ = Q ( Q T U ) V T . \Delta\approx QQ^{\mathsf T}\Delta= Q(Q^{\mathsf T}U)V^{\mathsf T}. Δ ≈ Q Q T Δ = Q ( Q T U ) V T .
This can again be written as a rank-m m m factorization
Q Q T Δ = U ~ V ~ T , U ~ : = Q , V ~ : = V ( U T Q ) . QQ^{\mathsf T}\Delta= \widetilde{U}\widetilde{V}^{\mathsf T}, \qquad\widetilde{U} := Q, \qquad\widetilde{V} := V(U^{\mathsf T}Q). Q Q T Δ = U V T , U := Q , V := V ( U T Q ) .
Indeed,
U ~ V ~ T = Q ( V ( U T Q ) ) T = Q ( Q T U ) V T = Q Q T U V T . \widetilde{U}\widetilde{V}^{\mathsf T} = Q\bigl(V(U^{\mathsf T}Q)\bigr)^{\mathsf T} = Q(Q^{\mathsf T}U)V^{\mathsf T} = QQ^{\mathsf T}UV^{\mathsf T}. U V T = Q ( V ( U T Q ) ) T = Q ( Q T U ) V T = Q Q T U V T .
The randomized scheme is not guaranteed to produce the exact best rank-m m m approximation, but it avoids the SVD and preserves the factorized representation throughout. Its cost is dominated by multiplying the factors against the sketch and orthonormalizing Y Y Y . Since r ≤ 2 m r \le2m r ≤ 2 m , forming V T Ω V^{\mathsf T}\Omega V T Ω , forming Y = U ( V T Ω ) Y = U(V^{\mathsf T}\Omega) Y = U ( V T Ω ) , computing the QR factorization of Y Y Y , and forming V ~ = V ( U T Q ) \widetilde{V} = V(U^{\mathsf T}Q) V = V ( U T Q ) together cost
O ( D m 2 ) , \mathcal{O}(Dm^2), O ( D m 2 ) ,
up to lower-order O ( m 3 ) \mathcal{O}(m^3) O ( m 3 ) terms from the QR decomposition. The memory cost is O ( D m ) \mathcal{O}(Dm) O ( D m ) for the compressed factors.
In the experiments, we use randomized compression by default because it is simple, factorized, and avoids dense matrix construction. The exact small-SVD compression provides a useful reference implementation and gives the optimal rank-m m m correction after each merge.
Empirical impact of compression
We study the effect of rank compression on the low-rank RNN benchmark using Accelerated Parallel Broyden. This experiment isolates the cost of solving the block-bidiagonal Newton system: all methods use the same multisecant Broyden block approximations and differ only in how the linearized recurrence is solved. We compare three variants. The first solves the recurrence by exact sequential forward substitution, which introduces no scan compression error but has linear depth in T T T . The second uses the compressed parallel scan with exact QR+SVD rank compression after each merge. The third uses the randomized factorized compression described above. We report median iteration counts and runtimes with interquartile ranges over 32 random realizations.
Figure 5 shows that compression has little effect on iteration counts. Exact sequential solution and QR+SVD compression have identical median iteration counts in all tested settings, confirming that the compressed scan preserves the relevant low-rank structure in this benchmark. The randomized compression has comparable, and sometimes slightly lower, iteration counts, with medians between roughly 11 and 13 iterations across all dimensions and horizons.
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.
The main difference is runtime. Exact sequential forward substitution is much slower because it solves the linearized recurrence with linear depth in T T T . At D = 100 D = 100 D = 100 and T = 200 K T = 200\mathrm{K} T = 200 K , exact QR+SVD compression is 22.0 × 22.0\times 22.0 × faster than the exact sequential solve, and randomized compression is 85.6 × 85.6\times 85.6 × faster. Randomized compression is also 3.9 × 3.9\times 3.9 × faster than exact QR+SVD compression in this setting. Thus, in this experiment, rank compression enables the scan to retain the convergence behavior of the exact linear solve while giving substantial runtime gains, and the randomized scheme provides the best practical tradeoff.
Choice of parallel scan tree
The parallel scan composes the affine maps x ↦ A ~ t x + c t x \mapsto\widetilde{A}_t x + c_t x ↦ A t x + c t along a binary tree. With exact composition, the operator is associative and every tree gives the same result. With DPLR blocks, however, each composition of two rank-m m m blocks is compressed back to rank m m m with a randomized sketch, so the combine operation is only approximately associative, and the result depends on which products are formed and compressed. We compare two standard trees. The Blelloch scan [20 ] is work-efficient. An up-sweep builds the products of contiguous blocks of 2 t 2^t 2 t steps, and a down-sweep distributes them to all prefixes, for O ( T ) O(T) O ( T ) compositions and depth about 2 log 2 T 2\log_2 T 2 log 2 T . The Hillis–Steele scan [45 ] instead updates every prefix at each of its log 2 T \log_2 T log 2 T levels by composing it with the prefix 2 k 2^k 2 k steps earlier, for O ( T log T ) O(T\log T) O ( T log T ) compositions and depth log 2 T \log_2 T log 2 T . The two trees therefore differ in the number and order of compressions applied to each prefix product. All other experiments in this paper use the Blelloch-type scan implemented by jax.lax.associative_scan.
To check that our results do not depend on this choice, we ran both variants of Parallel Broyden on the low-rank RNNs with the settings of Appendix § 12 .§ 1 and both scan trees, in float64 since only iteration counts are compared. The two trees also draw different random sketches, so the comparison includes both effects. The choice of tree has no meaningful effect on convergence (Table 2 ). Median iteration counts agree in 21 of 24 settings and differ by at most half an iteration otherwise, and the number of converged chains is identical in every setting. At the level of individual chains, 80% of chains take exactly the same number of iterations under both trees, and among chains that converge under both, 94% are within 5 iterations. The mean relative difference of 3.7% comes from a few chains close to the convergence boundary.
Table 2. Effect of the scan tree on iteration counts (low-rank RNNs, D = 200 D = 200 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.
Convergence analysis of quasi-Newton updates with compressed scan
This appendix proves Theorem 2. We first fix notation and state the assumptions precisely, and give a sufficient condition in terms of the true dynamics (C.1). We then derive a one-step error bound for any scan of the form (6), which extends Proposition 3 of Gonzalez et al. [22 ] to compressed scans (C.2). Next, we bound the compressed products used by the scan, which proves part (i) of the theorem (C.3). We then prove parts (ii) and (iii) in a general form that does not require λ c < 0 \lambda_c < 0 λ c < 0 (C.4), and discuss consequences and limitations (C.5). Empirical measurements of the quantities in the theorem are reported in Appendix § 10 .
Proof idea. The analysis follows Proposition 3 of Gonzalez et al. [22 ] , which writes the error after an approximate Newton step as J ~ − 1 \tilde{J}^{-1} J ~ − 1 applied to the block error ( J ~ − J ) e (\tilde{J} - J)e ( J ~ − J ) e plus a second-order remainder. The key observation is that compression acts only on the matrix components of the scan elements, which do not depend on the residual, so the compressed step remains linear in the residual, Δ x = − P r \Delta x = -P r Δ x = − P r , with P P P playing the role of J ~ − 1 \tilde{J}^{-1} J ~ − 1 (Lemma 1). The one-step argument therefore carries over, with one additional term Γ e \Gamma e Γ e , where Γ = I − P J ~ \Gamma= I - P\tilde{J} Γ = I − P J ~ vanishes without compression (Lemma 2). Unlike Proposition 3, which bounds the block error by ∥ J ~ − J ∥ 2 \lVert\tilde{J} - J\rVert_2 ∥ J ~ − J ∥ 2 , we keep it applied to the current trajectory error, which gives ρ \rho ρ . The main new ingredient is bounding P P P and Γ \Gamma Γ : compressed products are not products of the blocks, so we expand them over the scan tree and control the relative compression error introduced at each merge (Lemma 3).
Setting, notation, and assumptions
Iterates and errors. At iteration i i i , write A t ( i ) : = A t ( x t − 1 ( i ) ) A_t^{(i)} := A_t(x_{t-1}^{(i)}) A t ( i ) := A t ( x t − 1 ( i ) ) for the exact dynamics Jacobian block and A ~ t ( i ) \widetilde{A}_t^{(i)} A t ( i ) for the approximate block used by the solver (for Parallel Broyden, the damped block of Appendix E.4). The trajectory error is e ( i ) : = x 1 : T ( i ) − x 1 : T ⋆ e^{(i)} := x_{1:T}^{(i)} - x_{1:T}^{\star} e ( i ) := x 1 : T ( i ) − x 1 : T ⋆ , with blocks e t ( i ) = x t ( i ) − x t ⋆ ∈ R D e_t^{(i)} = x_t^{(i)} - x_t^{\star} \in\mathbb{R}^{D} e t ( i ) = x t ( i ) − x t ⋆ ∈ R D , and e 0 ( i ) = 0 e_0^{(i)} = 0 e 0 ( i ) = 0 since x 0 x_0 x 0 is fixed. We write J ( i ) : = J ( x 1 : T ( i ) ) J^{(i)} := J(x_{1:T}^{(i)}) J ( i ) := J ( x 1 : T ( i ) ) and J ~ ( i ) \widetilde{J}^{(i)} J ( i ) for the exact and approximate residual Jacobians. When the iteration index is clear, we drop the superscript ( i ) (i) ( i ) . We analyze full steps x ( i + 1 ) = x ( i ) + Δ x ( i + 1 ) x^{(i+1)} = x^{(i)} + \Delta x^{(i+1)} x ( i + 1 ) = x ( i ) + Δ x ( i + 1 ) . See Appendix C.5 for damped steps.
Per-step norm. For v = ( v 1 , … , v T ) ∈ R T D v = (v_1,\ldots,v_T) \in\mathbb{R}^{TD} v = ( v 1 , … , v T ) ∈ R T D with v t ∈ R D v_t \in\mathbb{R}^{D} v t ∈ R D , define
∥ v ∥ ∞ : = max 1 ≤ t ≤ T ∥ v t ∥ 2 . \lVert v\rVert_{\infty} := \max_{1 \le t \le T} \lVert v_t\rVert_2. ∥ v ∥ ∞ := 1 ≤ t ≤ T max ∥ v t ∥ 2 .
For a block matrix M ∈ R T D × T D M \in\mathbb{R}^{TD \times TD} M ∈ R T D × T D with blocks M t , s ∈ R D × D M_{t,s} \in\mathbb{R}^{D \times D} M t , s ∈ R D × D , let ∥ M ∥ ∞ : = sup v ≠ 0 ∥ M v ∥ ∞ / ∥ v ∥ ∞ \lVert M\rVert_{\infty} := \sup_{v \ne0} \lVert Mv\rVert_{\infty}/\lVert v\rVert_{\infty} ∥ M ∥ ∞ := sup v = 0 ∥ M v ∥ ∞ / ∥ v ∥ ∞ be the induced norm. Since ∥ ( M v ) t ∥ 2 ≤ ∑ s ∥ M t , s ∥ 2 ∥ v s ∥ 2 \lVert(Mv)_t\rVert_2 \le\sum_s \lVert M_{t,s}\rVert_2\lVert v_s\rVert_2 ∥( M v ) t ∥ 2 ≤ ∑ s ∥ M t , s ∥ 2 ∥ v s ∥ 2 ,
∥ M ∥ ∞ ≤ max t ∑ s ∥ M t , s ∥ 2 . (8) \lVert M\rVert_{\infty} \le\max_t \sum_s \lVert M_{t,s}\rVert_2. \tag*{(8)} ∥ M ∥ ∞ ≤ t max s ∑ ∥ M t , s ∥ 2 . (8)
We use this norm rather than the Euclidean norm on R T D \mathbb{R}^{TD} R T D used by Gonzalez et al. [22 ] : for bounded states, ∥ e ( 0 ) ∥ ∞ \lVert e^{(0)}\rVert_{\infty} ∥ e ( 0 ) ∥ ∞ does not grow with T T T , whereas ∥ e ( 0 ) ∥ 2 \lVert e^{(0)}\rVert_2 ∥ e ( 0 ) ∥ 2 typically grows like T \sqrt{T} T , which would make the region of convergence shrink artificially with T T T .
Geometric sums. For μ ∈ R \mu\in\mathbb{R} μ ∈ R , define
S T ( μ ) : = ∑ n = 0 T − 1 e μ n , so that S T ( μ ) ≤ 1 1 − e μ if μ < 0 , S T ( 0 ) = T . S_T(\mu) := \sum_{n=0}^{T-1} e^{\mu n}, \qquad\text{so that} \qquad S_T(\mu) \le\frac{1}{1-e^\mu}\ \text{if }\mu< 0,\qquad S_T(0)=T. S T ( μ ) := n = 0 ∑ T − 1 e μ n , so that S T ( μ ) ≤ 1 − e μ 1 if μ < 0 , S T ( 0 ) = T .
S T S_T S T is increasing in μ \mu μ , and for μ > 0 \mu> 0 μ > 0 it grows like e μ T e^{\mu T} e μ T .
Compressed scan. As in Appendix B.1, position t t t is represented by the leaf summary ( A ~ t , c t ) (\widetilde{A}_t,c_t) ( A t , c t ) with c t = − r t ( x 1 : T ( i ) ) c_t=-r_t(x_{1:T}^{(i)}) c t = − r t ( x 1 : T ( i ) ) , summaries of adjacent segments are combined by the merge (6) ,
( M b , c b ) ⋆ ( M a , c a ) = ( Comp ( M b M a ) , M b c a + c b ) . (M_b,c_b) \star(M_a,c_a) = \left(\operatorname{Comp}(M_bM_a), M_bc_a+c_b\right). ( M b , c b ) ⋆ ( M a , c a ) = ( Comp ( M b M a ) , M b c a + c b ) .
and the update is read off the prefix offsets, Δ x t ( i + 1 ) = c 1 : t \Delta x_t^{(i+1)} = c_{1:t} Δ x t ( i + 1 ) = c 1 : t . We assume that each prefix summary returned by the scan is obtained from the leaf summaries by a binary tree of such merges, each combining the summaries of two adjacent segments. This holds for standard scan algorithms. We call each merge a node ν \nu ν . It covers a segment of consecutive time steps { j + 1 , … , k } \{j+1,\ldots,k\} { j + 1 , … , k } of length ∣ ν ∣ = k − j |\nu|=k-j ∣ ν ∣ = k − j . At node ν \nu ν , the scan forms X ν : = M ~ r i g h t M ~ l e f t X_\nu:= \widetilde{M}_{\mathrm{right}}\widetilde{M}_{\mathrm{left}} X ν := M right M left from the stored matrices of its two children and stores
M ~ ν : = Comp ( X ν ) = X ν + Δ ν , Δ ν : = Comp ( X ν ) − X ν . \widetilde{M}_\nu:= \operatorname{Comp}(X_\nu)=X_\nu+\Delta_\nu,\qquad\Delta_\nu:=\operatorname{Comp}(X_\nu)-X_\nu. M ν := Comp ( X ν ) = X ν + Δ ν , Δ ν := Comp ( X ν ) − X ν .
Leaves are never compressed: the stored matrix of the leaf at t t t is A ~ t \widetilde{A}_t A t . We write Π t , s : = A ~ t A ~ t − 1 ⋯ A ~ s + 1 \Pi_{t,s}:=\widetilde{A}_t\widetilde{A}_{t-1}\cdots\widetilde{A}_{s+1} Π t , s := A t A t − 1 ⋯ A s + 1 for the exact product over { s + 1 , … , t } \{s+1,\ldots,t\} { s + 1 , … , t } , with Π t , t = I \Pi_{t,t}=I Π t , t = I .
Assumptions. All assumptions are imposed from some iteration i 0 ≥ 0 i_0 \ge0 i 0 ≥ 0 onward, which allows for early transients.
Assumption 1 (Contraction of the approximate system). There exist a ~ ≥ 1 \widetilde{a} \ge1 a ≥ 1 and λ ~ ∈ R \widetilde{\lambda} \in\mathbb{R} λ ∈ R such that for every iteration i ≥ i 0 i \ge i_0 i ≥ i 0 and all $0 \le j < k \le T$
∥ A ~ k ( i ) A ~ k − 1 ( i ) ⋯ A ~ j + 1 ( i ) ∥ 2 ≤ a ~ e λ ~ ( k − j ) . \left\lVert\widetilde{A}_k^{(i)}\widetilde{A}_{k-1}^{(i)}\cdots\widetilde{A}_{j+1}^{(i)}\right\rVert_2 \le\widetilde{a}e^{\widetilde{\lambda}(k-j)}. A k ( i ) A k − 1 ( i ) ⋯ A j + 1 ( i ) 2 ≤ a e λ ( k − j ) .
This is the predictability condition of Gonzalez et al. [34 ] , applied to the approximate blocks the solver actually multiplies rather than to the true Jacobians. Only products of consecutive blocks are needed.
Assumption 2 (Lipschitz Jacobians). There exists L ≥ 0 L \ge0 L ≥ 0 such that ∥ A t ( x ) − A t ( y ) ∥ 2 ≤ L ∥ x − y ∥ 2 \lVert A_t(x)-A_t(y)\rVert_2 \le L\lVert x-y\rVert_2 ∥ A t ( x ) − A t ( y ) ∥ 2 ≤ L ∥ x − y ∥ 2 for all t t t and all x , y ∈ R D x,y \in\mathbb{R}^D x , y ∈ R D .
Assumption 3 (Block error along the current trajectory error). There exists ρ ≥ 0 \rho\ge0 ρ ≥ 0 such that ρ i ≤ ρ \rho_i \le\rho ρ i ≤ ρ for every iteration i ≥ i 0 i \ge i_0 i ≥ i 0 , where
ρ i : = ∥ ( J ~ ( i ) − J ( i ) ) e ( i ) ∥ ∞ ∥ e ( i ) ∥ ∞ = max t ∥ ( A ~ t ( i ) − A t ( i ) ) e t − 1 ( i ) ∥ 2 ∥ e ( i ) ∥ ∞ , \rho_i := \frac{\lVert(\widetilde{J}^{(i)}-J^{(i)})e^{(i)}\rVert_\infty}{\lVert e^{(i)}\rVert_\infty} = \frac{\max_t \lVert(\widetilde{A}^{(i)}_t-A^{(i)}_t)e^{(i)}_{t-1}\rVert_2}{\lVert e^{(i)}\rVert_\infty}, ρ i := ∥ e ( i ) ∥ ∞ ∥( J ( i ) − J ( i ) ) e ( i ) ∥ ∞ = ∥ e ( i ) ∥ ∞ max t ∥( A t ( i ) − A t ( i ) ) e t − 1 ( i ) ∥ 2 , with ρ i : = 0 \rho_i := 0 ρ i := 0 if e ( i ) = 0 e^{(i)}=0 e ( i ) = 0 .
The quantity ρ i \rho_i ρ i measures the block error only along the current trajectory error. It satisfies ρ i ≤ σ i : = max t ∥ A ~ t ( i ) − A t ( i ) ∥ 2 \rho_i \le\sigma_i := \max_t \lVert\widetilde{A}^{(i)}_t-A^{(i)}_t\rVert_2 ρ i ≤ σ i := max t ∥ A t ( i ) − A t ( i ) ∥ 2 , the spectral-norm block error, and can be much smaller. Since it depends on x ⋆ x^\star x ⋆ , it can only be measured a posteriori.
Assumption 4 (Relative compression error). There exists η ≥ 0 \eta\ge0 η ≥ 0 such that at every iteration i ≥ i 0 i \ge i_0 i ≥ i 0 and at every node ν \nu ν ,
∥ Δ ν ∥ 2 ≤ η a ~ e λ ~ ∣ ν ∣ . \lVert\Delta_\nu\rVert_2 \le\eta\widetilde{a}e^{\widetilde{\lambda}|\nu|}. ∥ Δ ν ∥ 2 ≤ η a e λ ∣ ν ∣ .
By Assumption 1, the right-hand side bounds the size of the exact product over the segment of ν \nu ν , so Assumption 4 states that each merge loses at most a fraction η \eta η of the largest size this product can reach. It is implied by the stronger condition ∥ Δ ν ∥ 2 ≤ η ∥ Π k , j ∥ 2 \lVert\Delta_\nu\rVert_2 \le\eta\lVert\Pi_{k,j}\rVert_2 ∥ Δ ν ∥ 2 ≤ η ∥ Π k , j ∥ 2 . For truncated-SVD compression with fixed diagonal baseline γ I \gamma I γ I , ∥ Δ ν ∥ 2 \lVert\Delta_\nu\rVert_2 ∥ Δ ν ∥ 2 equals the largest discarded singular value of X ν − γ I X_\nu-\gamma I X ν − γ I , so Assumption 4 requires this value to be small. When rank is preserved under multiplication, as in the purely low-rank case (γ = 0 \gamma=0 γ = 0 ), no compression is needed and η = 0 \eta=0 η = 0 . For randomized compression, we expect the assumption to hold approximately when the low-rank parts of the products have rapidly decaying spectra, but we do not prove this.
Effective Lyapunov exponent with compression. As in Theorem 2, define
λ c : = λ ~ + log ( 1 + a ~ 2 η ) ≥ λ ~ , \lambda_c := \widetilde{\lambda}+\log(1+\widetilde{a}^{2}\eta)\ge\widetilde{\lambda}, λ c := λ + log ( 1 + a 2 η ) ≥ λ ,
with equality when η = 0 \eta=0 η = 0 .
A sufficient condition from the true dynamics. Assumptions 1 and 3 follow from predictability of the true dynamics together with a bound on the spectral-norm block error.
Proposition 1 (Predictability and spectral-norm error). Suppose that for every iteration i ≥ i 0 i \ge i_0 i ≥ i 0 and all $0 \le j < k \le T$, ∥ A k ( i ) ⋯ A j + 1 ( i ) ∥ 2 ≤ a e λ ( k − j ) \lVert A^{(i)}_k\cdots A^{(i)}_{j+1}\rVert_2 \le a e^{\lambda(k-j)} ∥ A k ( i ) ⋯ A j + 1 ( i ) ∥ 2 ≤ a e λ ( k − j ) with a ≥ 1 a \ge1 a ≥ 1 , and that σ i ≤ σ \sigma_i \le\sigma σ i ≤ σ . Then Assumption 1 holds with a ~ = a \widetilde{a}=a a = a and λ ~ = log ( e λ + a σ ) \widetilde{\lambda}=\log(e^\lambda+a\sigma) λ = log ( e λ + aσ ) , and Assumption 3 holds with ρ = σ \rho=\sigma ρ = σ .
Proof. Write A ~ ℓ = A ℓ + δ ℓ \widetilde{A}_\ell=A_\ell+\delta_\ell A ℓ = A ℓ + δ ℓ with ∥ δ ℓ ∥ 2 ≤ σ \lVert\delta_\ell\rVert_2\le\sigma ∥ δ ℓ ∥ 2 ≤ σ , and let n = k − j n=k-j n = k − j . Expanding A ~ k ⋯ A ~ j + 1 \widetilde{A}_k\cdots\widetilde{A}_{j+1} A k ⋯ A j + 1 gives a sum over subsets S ⊆ { j + 1 , … , k } S\subseteq\{j+1,\ldots,k\} S ⊆ { j + 1 , … , k } indicating where a factor δ ℓ \delta_\ell δ ℓ replaces A ℓ A_\ell A ℓ . For ∣ S ∣ = m |S|=m ∣ S ∣ = m , the term consists of m m m factors δ ℓ \delta_\ell δ ℓ separated by at most m + 1 m+1 m + 1 products of consecutive exact Jacobians, with total length n − m n-m n − m , so its norm is at most a m + 1 e λ ( n − m ) σ m a^{m+1}e^{\lambda(n-m)}\sigma^m a m + 1 e λ ( n − m ) σ m , using a ≥ 1 a\ge1 a ≥ 1 . Summing over subsets,
∥ A ~ k ⋯ A ~ j + 1 ∥ 2 ≤ ∑ m = 0 n ( n m ) a m + 1 e λ ( n − m ) σ m = a ( e λ + a σ ) n . \left\lVert\widetilde{A}_k\cdots\widetilde{A}_{j+1}\right\rVert_2 \le\sum_{m=0}^{n}\binom{n}{m}a^{m+1}e^{\lambda(n-m)}\sigma^m = a(e^\lambda+a\sigma)^n. A k ⋯ A j + 1 2 ≤ m = 0 ∑ n ( m n ) a m + 1 e λ ( n − m ) σ m = a ( e λ + aσ ) n .
Finally, ρ i ≤ σ i ≤ σ \rho_i\le\sigma_i\le\sigma ρ i ≤ σ i ≤ σ .
This condition is convenient but loose: in our experiments, the blocks are poor in spectral norm, so log ( e λ + a σ ) > 0 \log(e^\lambda+a\sigma)>0 log ( e λ + aσ ) > 0 , while the approximate products do contract and ρ i \rho_i ρ i is small (Appendix § 10 ).
One-step error bound for compressed scans
We first show that the compressed scan applies a linear operator to the residual, and identify its blocks.
Lemma 1 (Linear representation of the compressed scan). At each iteration, Δ x ( i + 1 ) = − P r ( x 1 : T ( i ) ) \Delta x^{(i+1)}=-P\,r(x^{(i)}_{1:T}) Δ x ( i + 1 ) = − P r ( x 1 : T ( i ) ) , where P P P is block lower triangular with blocks P t , s P_{t,s} P t , s ( s ≤ t ) (s\le t) ( s ≤ t ) and P t , t = I P_{t,t}=I P t , t = I . For s < t s<t s < t ,
P t , s = M ^ G r ⋯ M ^ G 1 P_{t,s}=\widehat{M}_{G_r}\cdots\widehat{M}_{G_1} P t , s = M G r ⋯ M G 1 where G 1 , … , G r G_1,\ldots,G_r G 1 , … , G r are nodes or leaves whose segments partition { s + 1 , … , t } \{s+1,\ldots,t\} { s + 1 , … , t } into consecutive blocks, ordered in time. In particular, P t , t − 1 = A ^ t P_{t,t-1}=\widehat{A}_t P t , t − 1 = A t . Without compression, P t , s = Π t , s P_{t,s}=\Pi_{t,s} P t , s = Π t , s and P = J ~ − 1 P=\widetilde{J}^{-1} P = J − 1 .
Proof. We show by induction over the merge tree that the offset of the summary of any segment { p , … , q } \{p,\ldots,q\} { p , … , q } is ∑ s = p q Q s c s \sum_{s=p}^{q}Q_s c_s ∑ s = p q Q s c s , where Q q = I Q_q=I Q q = I and, for s < q s<q s < q , Q s Q_s Q s is a product of stored matrices of nodes or leaves whose segments partition { s + 1 , … , q } \{s+1,\ldots,q\} { s + 1 , … , q } . For a leaf this holds with Q q = I Q_q=I Q q = I . For a merge of a left segment a = { p , … , m } a=\{p,\ldots,m\} a = { p , … , m } and a right segment b = { m + 1 , … , q } b=\{m+1,\ldots,q\} b = { m + 1 , … , q } , the new offset is M ^ b c a + c b \widehat{M}_b c_a+c_b M b c a + c b . Coefficients of leaves in b b b are unchanged, and coefficients of leaves s ∈ a s\in a s ∈ a are multiplied on the left by M ^ b \widehat{M}_b M b . Since the segment of b b b is { m + 1 , … , q } \{m+1,\ldots,q\} { m + 1 , … , q } and the inductive coefficient of s s s in a a a covers { s + 1 , … , m } \{s+1,\ldots,m\} { s + 1 , … , m } , the product covers { s + 1 , … , q } \{s+1,\ldots,q\} { s + 1 , … , q } . Applying this to the tree of the prefix { 1 , … , t } \{1,\ldots,t\} { 1 , … , t } and using Δ x t ( i + 1 ) = c 1 : t \Delta x_t^{(i+1)}=c_{1:t} Δ x t ( i + 1 ) = c 1 : t with c s = − r s c_s=-r_s c s = − r s gives the claim. For s = t − 1 s=t-1 s = t − 1 , the only partition of { t } \{t\} { t } is the leaf itself, so P t , t − 1 = A ^ t P_{t,t-1}=\widehat{A}_t P t , t − 1 = A t . Without compression, every stored matrix is the exact product over its segment, so P t , s = Π t , s P_{t,s}=\Pi_{t,s} P t , s = Π t , s . These are exactly the blocks of J ~ − 1 \widetilde{J}^{-1} J − 1 [22 ] .
Lemma 1 also gives a direct proof of Theorem 1 for any scan tree: if c s = 0 c_s=0 c s = 0 for all s ≤ i s\le i s ≤ i , then Δ x i + 1 ( i + 1 ) = ∑ s ≤ i + 1 P i + 1 , s c s = c i + 1 \Delta x_{i+1}^{(i+1)}=\sum_{s\le i+1}P_{i+1,s}c_s=c_{i+1} Δ x i + 1 ( i + 1 ) = ∑ s ≤ i + 1 P i + 1 , s c s = c i + 1 , since P i + 1 , i + 1 = I P_{i+1,i+1}=I P i + 1 , i + 1 = I , regardless of compression.
We measure how far the compressed scan is from the exact inverse through the compression error E : = P − J ~ − 1 E:=P-\widetilde{J}^{-1} E := P − J − 1 , with blocks E t , s = P t , s − Π t , s E_{t,s}=P_{t,s}-\Pi_{t,s} E t , s = P t , s − Π t , s , and the consistency defect
Γ : = I − P J ~ . \Gamma:=I-P\widetilde{J}. Γ := I − P J .
Lemma 2 (Structure of the consistency defect). Γ \Gamma Γ is strictly block lower triangular, with Γ t , t = Γ t , t − 1 = 0 \Gamma_{t,t}=\Gamma_{t,t-1}=0 Γ t , t = Γ t , t − 1 = 0 and, for s < t s<t s < t ,
Γ t , s = P t , s + 1 A ^ s + 1 − P t , s . \Gamma_{t,s}=P_{t,s+1}\widehat{A}_{s+1}-P_{t,s}. Γ t , s = P t , s + 1 A s + 1 − P t , s . In particular, Γ = 0 \Gamma=0 Γ = 0 without compression.
Proof. Write J ~ = I − N ~ \widetilde{J}=I-\widetilde{N} J = I − N , where N ~ \widetilde{N} N has blocks A ~ u \widetilde{A}_u A u at positions ( u , u − 1 ) (u,u-1) ( u , u − 1 ) . Then ( P N ~ ) t , s = P t , s + 1 A ~ s + 1 (P\widetilde{N})_{t,s}=P_{t,s+1}\widetilde{A}_{s+1} ( P N ) t , s = P t , s + 1 A s + 1 for s < t s<t s < t and 0 0 0 otherwise, so ( P J ~ ) t , s = P t , s − P t , s + 1 A ~ s + 1 (P\widetilde{J})_{t,s}=P_{t,s}-P_{t,s+1}\widetilde{A}_{s+1} ( P J ) t , s = P t , s − P t , s + 1 A s + 1 for s < t s<t s < t , and P t , t = I P_{t,t}=I P t , t = I for s = t s=t s = t . Subtracting from I I I gives the formula. For s = t − 1 s=t-1 s = t − 1 , P t , t A ^ t − P t , t − 1 = A ^ t − A ^ t = 0 P_{t,t}\widehat{A}_t-P_{t,t-1}=\widehat{A}_t-\widehat{A}_t=0 P t , t A t − P t , t − 1 = A t − A t = 0 by Lemma 1. Without compression, P t , s + 1 A ^ s + 1 = Π t , s + 1 A ^ s + 1 = Π t , s = P t , s P_{t,s+1}\widehat{A}_{s+1}=\Pi_{t,s+1}\widehat{A}_{s+1}=\Pi_{t,s}=P_{t,s} P t , s + 1 A s + 1 = Π t , s + 1 A s + 1 = Π t , s = P t , s .
Proposition 2 (One-step bound with compressed scan). Under Assumption 2, at every iteration i i i ,
∥ e ( i + 1 ) ∥ ∞ ≤ ∥ Γ ∥ ∞ ∥ e ( i ) ∥ ∞ + ∥ P ∥ ∞ ( ρ i ∥ e ( i ) ∥ ∞ + ℓ 2 ∥ e ( i ) ∥ ∞ 2 ) . \left\|e^{(i+1)}\right\|_{\infty}\le\|\Gamma\|_{\infty}\left\|e^{(i)}\right\|_{\infty}+\|P\|_{\infty}\left(\rho_i\left\|e^{(i)}\right\|_{\infty}+\frac{\ell}{2}\left\|e^{(i)}\right\|_{\infty}^{2}\right). e ( i + 1 ) ∞ ≤ ∥Γ ∥ ∞ e ( i ) ∞ + ∥ P ∥ ∞ ( ρ i e ( i ) ∞ + 2 ℓ e ( i ) ∞ 2 ) . With an exact scan ( P = J ~ − 1 , Γ = 0 ) (P=\widetilde{J}^{-1},\ \Gamma=0) ( P = J − 1 , Γ = 0 ) and ρ i \rho_i ρ i replaced by its upper bound σ i \sigma_i σ i , this is Proposition 3 of Gonzalez et al. [22 ] , stated in the per-step norm.
Proof. Drop the superscript ( i ) (i) ( i ) and let e = e ( i ) e=e^{(i)} e = e ( i ) . Since r ( x ⋆ ) = 0 r(x^\star)=0 r ( x ⋆ ) = 0 , for each t ≥ 2 t\ge2 t ≥ 2 ,
r t ( x ⋆ ) = e t − ( f t ( x t − 1 ( i ) ) − f t ( x t − 1 ( i ) ) ) = e t − A t e t − 1 + R t , r_t(x^\star)=e_t-\left(f_t(x_{t-1}^{(i)})-f_t(x_{t-1}^{(i)})\right)=e_t-A_t e_{t-1}+R_t, r t ( x ⋆ ) = e t − ( f t ( x t − 1 ( i ) ) − f t ( x t − 1 ( i ) ) ) = e t − A t e t − 1 + R t ,
where, by Assumption 2 and Taylor’s theorem, R t : = f t ( x t − 1 ⋆ ) − f t ( x t − 1 ( i ) ) + A t e t − 1 R_t:=f_t(x_{t-1}^\star)-f_t(x_{t-1}^{(i)})+A_t e_{t-1} R t := f t ( x t − 1 ⋆ ) − f t ( x t − 1 ( i ) ) + A t e t − 1 satisfies ∥ R t ∥ 2 ≤ ℓ 2 ∥ e t − 1 ∥ 2 2 \|R_t\|_2\le\frac{\ell}{2}\|e_{t-1}\|_2^2 ∥ R t ∥ 2 ≤ 2 ℓ ∥ e t − 1 ∥ 2 2 . Also r 1 ( x ( i ) ) = e 1 r_1(x^{(i)})=e_1 r 1 ( x ( i ) ) = e 1 . Hence r ( x ( i ) ) = J ~ e + R r(x^{(i)})=\widetilde{J}e+R r ( x ( i ) ) = J e + R with ∥ R ∥ ∞ ≤ ℓ 2 ∥ e ∥ ∞ 2 \|R\|_\infty\le\frac{\ell}{2}\|e\|_\infty^2 ∥ R ∥ ∞ ≤ 2 ℓ ∥ e ∥ ∞ 2 . The update e ( i + 1 ) = e − P r ( x ( i ) ) e^{(i+1)}=e-Pr(x^{(i)}) e ( i + 1 ) = e − P r ( x ( i ) ) then gives
e ( i + 1 ) = ( I − P J ~ ) e − P R = Γ e + P ( ( J ~ − J ) e − R ) . e^{(i+1)}=(I-P\widetilde{J})e-PR=\Gamma e+P\left((\widetilde{J}-J)e-R\right). e ( i + 1 ) = ( I − P J ) e − P R = Γ e + P ( ( J − J ) e − R ) .
By definition of ρ i \rho_i ρ i , ∥ ( J ~ − J ) e ∥ ∞ = ρ i ∥ e ∥ ∞ \|(\widetilde{J}-J)e\|_\infty=\rho_i\|e\|_\infty ∥ ( J − J ) e ∥ ∞ = ρ i ∥ e ∥ ∞ . Taking norms concludes.
The proof applies J ~ − J \widetilde{J}-J J − J only to the current trajectory error, which is why the bound involves ρ i \rho_i ρ i rather than the spectral-norm error σ i \sigma_i σ i .
Bounds on compressed products
The following lemma makes part (i) of Theorem 2 precise: while products of approximate blocks grow at most at rate λ ~ \tilde{\lambda} λ ~ (Assumption 1), their compressed counterparts used by the scan grow at most at rate λ c \lambda_c λ c .
Lemma 3 (Compressed products). Under Assumptions 1 and 4, for every iteration i ≥ i 0 i \ge i_0 i ≥ i 0 and all s < t s < t s < t , with n = t − s n=t-s n = t − s ,
∥ P t , s ∥ 2 ≤ a ~ e λ ~ n ( 1 + a ~ 2 η ) n − 1 ≤ a ~ e λ c n , \lVert P_{t,s}\rVert_2 \le\tilde{a}e^{\tilde{\lambda}n}(1+\tilde{a}^{2}\eta)^{n-1} \le\tilde{a}e^{\lambda_c n}, ∥ P t , s ∥ 2 ≤ a ~ e λ ~ n ( 1 + a ~ 2 η ) n − 1 ≤ a ~ e λ c n , ∥ P t , s − Π t , s ∥ 2 ≤ a ~ e λ ~ n [ ( 1 + a ~ 2 η ) n − 1 − 1 ] ≤ a ~ ( e λ c n − e λ ~ n ) . \lVert P_{t,s}-\Pi_{t,s}\rVert_2 \le\tilde{a}e^{\tilde{\lambda}n}\left[(1+\tilde{a}^{2}\eta)^{n-1}-1\right] \le\tilde{a}\left(e^{\lambda_c n}-e^{\tilde{\lambda}n}\right). ∥ P t , s − Π t , s ∥ 2 ≤ a ~ e λ ~ n [ ( 1 + a ~ 2 η ) n − 1 − 1 ] ≤ a ~ ( e λ c n − e λ ~ n ) .
Proof. Expansion. For a node ν \nu ν , call a set S S S of nodes in the subtree of ν \nu ν an antichain if no node in S S S is an ancestor of another. We claim that
M ^ ν = ∑ S Π ν ( S ) . \widehat{M}_{\nu}=\sum_{S}\Pi_{\nu}^{(S)}. M ν = S ∑ Π ν ( S ) .
where the sum is over antichains S S S in the subtree of ν \nu ν , and Π ν ( S ) \Pi_{\nu}^{(S)} Π ν ( S ) is the ordered product over the segment of ν \nu ν in which the segment of each μ ∈ S \mu\in S μ ∈ S is replaced by the single factor Δ μ \Delta_{\mu} Δ μ , and every remaining time step u u u contributes A ~ u \widetilde{A}_u A u . This holds for leaves (only S = ∅ S=\varnothing S = ∅ ). For a node with children l , r l,r l , r , M ^ ν = M ^ r M ^ l + Δ ν \widehat{M}_{\nu}=\widehat{M}_{r}\widehat{M}_{l}+\Delta_{\nu} M ν = M r M l + Δ ν . Expanding M ^ r \widehat{M}_{r} M r and M ^ l \widehat{M}_{l} M l by induction gives the sum over unions of antichains of the two subtrees, and Δ ν \Delta_{\nu} Δ ν is the term S = { ν } S=\{\nu\} S = { ν } . These are exactly the antichains of the subtree of ν \nu ν .
By Lemma 1, P t , s = M ^ G r ⋯ M ^ G 1 P_{t,s}=\widehat{M}_{G_r}\cdots\widehat{M}_{G_1} P t , s = M G r ⋯ M G 1 , so P t , s P_{t,s} P t , s expands as a sum over sets S S S that are unions of antichains of the subtrees of G 1 , … , G r G_1,\ldots,G_r G 1 , … , G r . The term S = ∅ S=\varnothing S = ∅ is Π t , s \Pi_{t,s} Π t , s .
Bounding each term. Fix S S S with ∣ S ∣ = j \lvert S\rvert=j ∣ S ∣ = j . The corresponding term consists of the j j j factors Δ μ \Delta_{\mu} Δ μ , μ ∈ S \mu\in S μ ∈ S , separated by at most j + 1 j+1 j + 1 products of consecutive approximate blocks, with segment lengths summing to n n n . By Assumption 1, each product of consecutive approximate blocks of length ℓ \ell ℓ has norm at most a ~ e λ ~ ℓ \tilde{a}e^{\tilde{\lambda}\ell} a ~ e λ ~ ℓ (also for ℓ = 0 \ell=0 ℓ = 0 , since a ~ ≥ 1 \tilde{a}\ge1 a ~ ≥ 1 ), and by Assumption 4, ∥ Δ μ ∥ 2 ≤ η a ~ e λ ~ ∣ μ ∣ \lVert\Delta_{\mu}\rVert_2\le\eta\tilde{a}e^{\tilde{\lambda}\lvert\mu\rvert} ∥ Δ μ ∥ 2 ≤ η a ~ e λ ~ ∣ μ ∣ . Hence the term has norm at most
a ~ j + 1 ( η a ~ ) j e λ ~ n = a ~ e λ ~ n ( a ~ 2 η ) j . \tilde{a}^{j+1}(\eta\tilde{a})^je^{\tilde{\lambda}n}=\tilde{a}e^{\tilde{\lambda}n}(\tilde{a}^{2}\eta)^j. a ~ j + 1 ( η a ~ ) j e λ ~ n = a ~ e λ ~ n ( a ~ 2 η ) j .
Counting. The subtrees of G 1 , … , G r G_1,\ldots,G_r G 1 , … , G r contain ∑ ℓ ( ∣ G ℓ ∣ − 1 ) = n − r ≤ n − 1 \sum_{\ell}(\lvert G_{\ell}\rvert-1)=n-r\le n-1 ∑ ℓ (∣ G ℓ ∣ − 1 ) = n − r ≤ n − 1 nodes in total, so there are at most ( n − 1 j ) \binom{n-1}{j} ( j n − 1 ) sets S S S with ∣ S ∣ = j \lvert S\rvert=j ∣ S ∣ = j . Summing over j ≥ 0 j\ge0 j ≥ 0 gives the first bound, and summing over j ≥ 1 j\ge1 j ≥ 1 gives the second. The final inequalities use e λ ~ n ( 1 + a ~ 2 η ) n − 1 ≤ e λ c n ( 1 + a ~ 2 η ) n = e λ c n e^{\tilde{\lambda}n}(1+\tilde{a}^{2}\eta)^{n-1}\le e^{\lambda_c n}(1+\tilde{a}^{2}\eta)^n=e^{\lambda_c n} e λ ~ n ( 1 + a ~ 2 η ) n − 1 ≤ e λ c n ( 1 + a ~ 2 η ) n = e λ c n .
Corollary 1 (Operator bounds). Under Assumptions 1 and 4, at every iteration i ≥ i 0 i\ge i_0 i ≥ i 0 ,
∥ J ~ − 1 ∥ ∞ ≤ a ~ S T ( λ ~ ) , ∥ P ∥ ∞ ≤ a ~ S T ( λ c ) , \lVert\widetilde{J}^{-1}\rVert_{\infty}\le\tilde{a}S_T(\tilde{\lambda}),\qquad\lVert P\rVert_{\infty}\le\tilde{a}S_T(\lambda_c), ∥ J − 1 ∥ ∞ ≤ a ~ S T ( λ ~ ) , ∥ P ∥ ∞ ≤ a ~ S T ( λ c ) , ∥ E ∥ ∞ ≤ a ~ ( S T ( λ c ) − S T ( λ ~ ) ) , ∥ Γ ∥ ∞ ≤ 2 a ~ ( S T ( λ c ) − S T ( λ ~ ) ) . \lVert E\rVert_{\infty}\le\tilde{a}\left(S_T(\lambda_c)-S_T(\tilde{\lambda})\right),\qquad\lVert\Gamma\rVert_{\infty}\le2\tilde{a}\left(S_T(\lambda_c)-S_T(\tilde{\lambda})\right). ∥ E ∥ ∞ ≤ a ~ ( S T ( λ c ) − S T ( λ ~ ) ) , ∥ Γ ∥ ∞ ≤ 2 a ~ ( S T ( λ c ) − S T ( λ ~ ) ) . If λ c < 0 \lambda_c<0 λ c < 0 , then
∥ P ∥ ∞ ≤ a ~ 1 − e λ c , ∥ Γ ∥ ∞ ≤ 2 a ~ 3 η e λ ~ ( 1 − e λ ~ ) ( 1 − e λ c ) . \lVert P\rVert_{\infty}\le\frac{\tilde{a}}{1-e^{\lambda_c}},\qquad\lVert\Gamma\rVert_{\infty}\le\frac{2\tilde{a}^{3}\eta e^{\tilde{\lambda}}}{(1-e^{\tilde{\lambda}})(1-e^{\lambda_c})}. ∥ P ∥ ∞ ≤ 1 − e λ c a ~ , ∥ Γ ∥ ∞ ≤ ( 1 − e λ ~ ) ( 1 − e λ c ) 2 a ~ 3 η e λ ~ .
Proof. We use the row-sum bound (8) . In row t t t , the block in column s s s corresponds to n = t − s ∈ { 0 , … , t − 1 } n=t-s\in\{0,\ldots,t-1\} n = t − s ∈ { 0 , … , t − 1 } .
For J ~ − 1 \widetilde{J}^{-1} J − 1 , the blocks are Π t , s \Pi_{t,s} Π t , s , and Assumption 1 gives ∑ n = 0 t − 1 a ~ e λ ~ n ≤ a ~ S T ( λ ~ ) \sum_{n=0}^{t-1}\tilde{a}e^{\tilde{\lambda}n}\le\tilde{a}S_T(\tilde{\lambda}) ∑ n = 0 t − 1 a ~ e λ ~ n ≤ a ~ S T ( λ ~ ) , the diagonal term is ∥ I ∥ 2 = 1 ≤ a ~ \lVert I\rVert_2=1\le\tilde{a} ∥ I ∥ 2 = 1 ≤ a ~ . For P P P and E E E , use Lemma 3 in the same way. The diagonal blocks are I I I and 0 0 0 , respectively.
For Γ \Gamma Γ , Lemma 2 gives Γ t , s = 0 \Gamma_{t,s}=0 Γ t , s = 0 for n ≤ 1 n\le1 n ≤ 1 . For n > 2 n>2 n > 2 , since Π t , s + 1 A ~ s + 1 = Π t , s \Pi_{t,s+1}\widetilde{A}_{s+1}=\Pi_{t,s} Π t , s + 1 A s + 1 = Π t , s ,
Γ t , s = ( P t , s + 1 − Π t , s + 1 ) A ~ s + 1 − ( P t , s − Π t , s ) . \Gamma_{t,s}=(P_{t,s+1}-\Pi_{t,s+1})\widetilde{A}_{s+1}-(P_{t,s}-\Pi_{t,s}). Γ t , s = ( P t , s + 1 − Π t , s + 1 ) A s + 1 − ( P t , s − Π t , s ) .
The second term is bounded by Lemma 3. For the first, expand P t , s + 1 − Π t , s + 1 P_{t,s+1}-\Pi_{t,s+1} P t , s + 1 − Π t , s + 1 as in the proof of Lemma 3: each term has j ≥ 1 j\ge1 j ≥ 1 factors Δ μ \Delta_{\mu} Δ μ over { s + 2 , … , t } \{s+2,\ldots,t\} { s + 2 , … , t } , and right-multiplying by A ~ s + 1 \widetilde{A}_{s+1} A s + 1 only extends its last product of consecutive approximate blocks. Each term is therefore bounded by a ~ e λ ~ n ( a ~ 2 η ) j \tilde{a}\,e^{\tilde{\lambda}n}(\tilde{a}^{2}\eta)^{j} a ~ e λ ~ n ( a ~ 2 η ) j , and there are at most ( n − 2 j ) \binom{n-2}{j} ( j n − 2 ) of them, so this term is also bounded by a ~ ( e λ c n − e λ ~ n ) \tilde{a}(e^{\lambda_{c}n}-e^{\tilde{\lambda}n}) a ~ ( e λ c n − e λ ~ n ) . Hence ∥ Γ t , s ∥ 2 ≤ 2 a ~ ( e λ c n − e λ ~ n ) \|\Gamma_{t,s}\|_{2}\leq2\tilde{a}(e^{\lambda_{c}n}-e^{\tilde{\lambda}n}) ∥ Γ t , s ∥ 2 ≤ 2 a ~ ( e λ c n − e λ ~ n ) , and summing over n n n gives the bound.
If λ c < 0 \lambda_{c}<0 λ c < 0 , then λ ~ < 0 \tilde{\lambda}<0 λ ~ < 0 as well. Since each term e λ c n − e λ ~ n e^{\lambda_{c}n}-e^{\tilde{\lambda}n} e λ c n − e λ ~ n is nonnegative,
S T ( λ c ) − S T ( λ ~ ) ≤ 1 1 − e λ c − 1 1 − e λ ~ = e λ c − e λ ~ ( 1 − e λ c ) ( 1 − e λ ~ ) = a ~ 2 η e λ ~ ( 1 − e λ c ) ( 1 − e λ ~ ) , S_{T}(\lambda_{c})-S_{T}(\tilde{\lambda})\leq\frac{1}{1-e^{\lambda_{c}}}-\frac{1}{1-e^{\tilde{\lambda}}}=\frac{e^{\lambda_{c}}-e^{\tilde{\lambda}}}{(1-e^{\lambda_{c}})(1-e^{\tilde{\lambda}})}=\frac{\tilde{a}^{2}\eta e^{\tilde{\lambda}}}{(1-e^{\lambda_{c}})(1-e^{\tilde{\lambda}})}, S T ( λ c ) − S T ( λ ~ ) ≤ 1 − e λ c 1 − 1 − e λ ~ 1 = ( 1 − e λ c ) ( 1 − e λ ~ ) e λ c − e λ ~ = ( 1 − e λ c ) ( 1 − e λ ~ ) a ~ 2 η e λ ~ ,
using e λ c = e λ ~ ( 1 + a ~ 2 η ) e^{\lambda_{c}}=e^{\tilde{\lambda}}(1+\tilde{a}^{2}\eta) e λ c = e λ ~ ( 1 + a ~ 2 η ) .
Proof of Theorem 2
We prove a general version that does not assume λ c < 0 \lambda_{c}<0 λ c < 0 . Theorem 2 is the special case λ c < 0 \lambda_{c}<0 λ c < 0 .
Theorem 3 (General form of Theorem 2). Let Assumptions 1–4 hold from iteration i 0 i_{0} i 0 onward, and define
c 0 ( T ) : = a ~ ρ S T ( λ c ) + 2 a ~ ( S T ( λ c ) − S T ( λ ~ ) ) , c 1 ( T ) : = a ~ L 2 S T ( λ c ) . c_{0}^{(T)}:=\tilde{a}\rho S_{T}(\lambda_{c})+2\tilde{a}\left(S_{T}(\lambda_{c})-S_{T}(\tilde{\lambda})\right),\qquad c_{1}^{(T)}:=\frac{\tilde{a}L}{2}S_{T}(\lambda_{c}). c 0 ( T ) := a ~ ρ S T ( λ c ) + 2 a ~ ( S T ( λ c ) − S T ( λ ~ ) ) , c 1 ( T ) := 2 a ~ L S T ( λ c ) . Then:
(i) For every iteration i ≥ i 0 i\geq i_{0} i ≥ i 0 and all s < t s<t s < t , ∥ P t , s ∥ 2 ≤ a ~ e λ c ( t − s ) \|P_{t,s}\|_{2}\leq\tilde{a}\,e^{\lambda_{c}(t-s)} ∥ P t , s ∥ 2 ≤ a ~ e λ c ( t − s ) .
(ii) For every iteration i ≥ i 0 i\geq i_{0} i ≥ i 0 , ∥ e ( i + 1 ) ∥ ∞ ≤ ( c 0 ( T ) + c 1 ( T ) ∥ e ( i ) ∥ ∞ ) ∥ e ( i ) ∥ ∞ \|e^{(i+1)}\|_{\infty}\leq\left(c_{0}^{(T)}+c_{1}^{(T)}\|e^{(i)}\|_{\infty}\right)\|e^{(i)}\|_{\infty} ∥ e ( i + 1 ) ∥ ∞ ≤ ( c 0 ( T ) + c 1 ( T ) ∥ e ( i ) ∥ ∞ ) ∥ e ( i ) ∥ ∞ .
(iii) If c 0 ( T ) < 1 c_{0}^{(T)}<1 c 0 ( T ) < 1 and ∥ e ( i 0 ) ∥ ∞ < ( 1 − c 0 ( T ) ) / c 1 ( T ) \|e^{(i_{0})}\|_{\infty}<(1-c_{0}^{(T)})/c_{1}^{(T)} ∥ e ( i 0 ) ∥ ∞ < ( 1 − c 0 ( T ) ) / c 1 ( T ) , then ∥ e ( i ) ∥ ∞ ≤ q i − i 0 ∥ e ( i 0 ) ∥ ∞ \|e^{(i)}\|_{\infty}\leq q^{i-i_{0}}\|e^{(i_{0})}\|_{\infty} ∥ e ( i ) ∥ ∞ ≤ q i − i 0 ∥ e ( i 0 ) ∥ ∞ for all i ≥ i 0 i\geq i_{0} i ≥ i 0 , with q : = c 0 ( T ) + c 1 ( T ) ∥ e ( i 0 ) ∥ ∞ < 1 q:=c_{0}^{(T)}+c_{1}^{(T)}\|e^{(i_{0})}\|_{\infty}<1 q := c 0 ( T ) + c 1 ( T ) ∥ e ( i 0 ) ∥ ∞ < 1 .
If λ c < 0 \lambda_{c}<0 λ c < 0 , then c 0 ( T ) ≤ c 0 c_{0}^{(T)}\leq c_{0} c 0 ( T ) ≤ c 0 and c 1 ( T ) ≤ c 1 c_{1}^{(T)}\leq c_{1} c 1 ( T ) ≤ c 1 , with c 0 c_{0} c 0 and c 1 c_{1} c 1 as in Theorem 2, which are independent of T T T .
Proof. (i) This is Lemma 3.
(ii) Insert the bounds of Corollary 1 into Proposition 2, and use ρ i ≤ ρ \rho_{i}\leq\rho ρ i ≤ ρ :
∥ e ( i + 1 ) ∥ ∞ ≤ ( 2 a ~ ( S T ( λ c ) − S T ( λ ~ ) ) + a ~ S T ( λ c ) ρ + a ~ S T ( λ c ) L 2 ∥ e ( i ) ∥ ∞ ) ∥ e ( i ) ∥ ∞ . \|e^{(i+1)}\|_{\infty}\leq\left(2\tilde{a}\left(S_{T}(\lambda_{c})-S_{T}(\tilde{\lambda})\right)+\tilde{a}S_{T}(\lambda_{c})\rho+\tilde{a}S_{T}(\lambda_{c})\frac{L}{2}\|e^{(i)}\|_{\infty}\right)\|e^{(i)}\|_{\infty}. ∥ e ( i + 1 ) ∥ ∞ ≤ ( 2 a ~ ( S T ( λ c ) − S T ( λ ~ ) ) + a ~ S T ( λ c ) ρ + a ~ S T ( λ c ) 2 L ∥ e ( i ) ∥ ∞ ) ∥ e ( i ) ∥ ∞ .
(iii) We show by induction on i ≥ i 0 i\geq i_{0} i ≥ i 0 that ∥ e ( i ) ∥ ∞ ≤ ∥ e ( i 0 ) ∥ ∞ \|e^{(i)}\|_{\infty}\leq\|e^{(i_{0})}\|_{\infty} ∥ e ( i ) ∥ ∞ ≤ ∥ e ( i 0 ) ∥ ∞ and ∥ e ( i ) ∥ ∞ ≤ q i − i 0 ∥ e ( i 0 ) ∥ ∞ \|e^{(i)}\|_{\infty}\leq q^{i-i_{0}}\|e^{(i_{0})}\|_{\infty} ∥ e ( i ) ∥ ∞ ≤ q i − i 0 ∥ e ( i 0 ) ∥ ∞ . Both hold for i = i 0 i=i_{0} i = i 0 . If they hold for i i i , then by (ii),
∥ e ( i + 1 ) ∥ ∞ ≤ ( c 0 ( T ) + c 1 ( T ) ∥ e ( i 0 ) ∥ ∞ ) ∥ e ( i ) ∥ ∞ = q ∥ e ( i ) ∥ ∞ ≤ q i + 1 − i 0 ∥ e ( i 0 ) ∥ ∞ , \|e^{(i+1)}\|_{\infty}\leq\left(c_{0}^{(T)}+c_{1}^{(T)}\|e^{(i_{0})}\|_{\infty}\right)\|e^{(i)}\|_{\infty}=q\|e^{(i)}\|_{\infty}\leq q^{i+1-i_{0}}\|e^{(i_{0})}\|_{\infty}, ∥ e ( i + 1 ) ∥ ∞ ≤ ( c 0 ( T ) + c 1 ( T ) ∥ e ( i 0 ) ∥ ∞ ) ∥ e ( i ) ∥ ∞ = q ∥ e ( i ) ∥ ∞ ≤ q i + 1 − i 0 ∥ e ( i 0 ) ∥ ∞ ,
and since q < 1 q<1 q < 1 , also ∥ e ( i + 1 ) ∥ ∞ ≤ ∥ e ( i 0 ) ∥ ∞ \|e^{(i+1)}\|_{\infty}\leq\|e^{(i_{0})}\|_{\infty} ∥ e ( i + 1 ) ∥ ∞ ≤ ∥ e ( i 0 ) ∥ ∞ . The condition q < 1 q<1 q < 1 is equivalent to ∥ e ( i 0 ) ∥ ∞ < ( 1 − c 0 ( T ) ) / c 1 ( T ) \|e^{(i_{0})}\|_{\infty}<(1-c_{0}^{(T)})/c_{1}^{(T)} ∥ e ( i 0 ) ∥ ∞ < ( 1 − c 0 ( T ) ) / c 1 ( T ) .
Finally, if λ c < 0 \lambda_{c}<0 λ c < 0 , Corollary 1 gives
c 0 ( T ) ≤ a ~ ρ 1 − e λ c + 2 a ~ 3 η e λ ~ ( 1 − e λ ~ ) ( 1 − e λ c ) = c 0 , c 1 ( T ) ≤ a ~ L 2 ( 1 − e λ c ) = c 1 . c_{0}^{(T)}\leq\frac{\tilde{a}\rho}{1-e^{\lambda_{c}}}+\frac{2\tilde{a}^{3}\eta e^{\tilde{\lambda}}}{(1-e^{\tilde{\lambda}})(1-e^{\lambda_{c}})}=c_{0},\qquad c_{1}^{(T)}\leq\frac{\tilde{a}L}{2(1-e^{\lambda_{c}})}=c_{1}. c 0 ( T ) ≤ 1 − e λ c a ~ ρ + ( 1 − e λ ~ ) ( 1 − e λ c ) 2 a ~ 3 η e λ ~ = c 0 , c 1 ( T ) ≤ 2 ( 1 − e λ c ) a ~ L = c 1 .
Since (ii) and (iii) remain valid when c 0 ( T ) c_{0}^{(T)} c 0 ( T ) , c 1 ( T ) c_{1}^{(T)} c 1 ( T ) are replaced by the larger constants c 0 c_{0} c 0 , c 1 c_{1} c 1 , this proves Theorem 2.
Consequences and limitations
Special cases.
Exact Newton, exact scan (ρ = η = 0 \rho=\eta=0 ρ = η = 0 ): c 0 = 0 c_{0}=0 c 0 = 0 , and (ii) reads ∥ e ( i + 1 ) ∥ ∞ ≤ c 1 ∥ e ( i ) ∥ ∞ 2 \|e^{(i+1)}\|_{\infty}\leq c_{1}\|e^{(i)}\|_{\infty}^{2} ∥ e ( i + 1 ) ∥ ∞ ≤ c 1 ∥ e ( i ) ∥ ∞ 2 , i.e. local quadratic convergence.
Approximate blocks, exact scan (η = 0 \eta= 0 η = 0 ): Γ = 0 \Gamma= 0 Γ = 0 , λ c = λ ~ \lambda_c = \tilde{\lambda} λ c = λ ~ , and c 0 = a ~ ρ / ( 1 − e λ ~ ) c_0 = \tilde{a}\rho/(1-e^{\tilde{\lambda}}) c 0 = a ~ ρ / ( 1 − e λ ~ ) . Compared with Proposition 3 of Gonzalez et al. [22 ] , the inverse is bounded independently of T T T , ∥ J ~ − 1 ∥ ∞ ≤ a ~ / ( 1 − e λ ~ ) \lVert\tilde{J}^{-1}\rVert_{\infty} \le\tilde{a}/(1-e^{\tilde{\lambda}}) ∥ J ~ − 1 ∥ ∞ ≤ a ~ / ( 1 − e λ ~ ) , even when individual blocks satisfy ∥ A ~ t ∥ 2 > 1 \lVert\tilde{A}_t\rVert_2 > 1 ∥ A ~ t ∥ 2 > 1 , and the block error enters only along the current trajectory error. This case includes diagonal quasi-Newton.
Exact blocks, compressed scan (ρ = 0 \rho= 0 ρ = 0 , η > 0 \eta> 0 η > 0 ): c 0 = 2 a ~ 3 η e λ ~ ( 1 − e λ ~ ) ( 1 − e λ c ) > 0 c_0 = \frac{2\tilde{a}^3\eta e^{\tilde{\lambda}}}{(1-e^{\tilde{\lambda}})(1-e^{\lambda_c})} > 0 c 0 = ( 1 − e λ ~ ) ( 1 − e λ c ) 2 a ~ 3 η e λ ~ > 0 , so the bound guarantees only a linear rate, O ( η ) O(\eta) O ( η ) .
Vanishing block error : if η = 0 \eta= 0 η = 0 and ρ i → 0 \rho_i \to0 ρ i → 0 , Proposition 2 gives a per-iteration factor ∥ P ∥ ∞ ( ρ i + L 2 ∥ e ( i ) ∥ ∞ ) → 0 \lVert\mathbf{P}\rVert_{\infty}(\rho_i + \frac{L}{2}\lVert e^{(i)}\rVert_{\infty}) \to0 ∥ P ∥ ∞ ( ρ i + 2 L ∥ e ( i ) ∥ ∞ ) → 0 , i.e. superlinear convergence.
Dependence on T T T . If λ c < 0 \lambda_c < 0 λ c < 0 , all constants are independent of T T T . If λ c = 0 \lambda_c = 0 λ c = 0 , then S T ( λ c ) = T S_T(\lambda_c) = T S T ( λ c ) = T , so c 0 ( T ) c_0^{(T)} c 0 ( T ) and c 1 ( T ) c_1^{(T)} c 1 ( T ) grow linearly with T T T . If λ c > 0 \lambda_c > 0 λ c > 0 , they grow like e λ c T e^{\lambda_c T} e λ c T . In both cases, c 0 ( T ) < 1 c_0^{(T)} < 1 c 0 ( T ) < 1 requires ρ \rho ρ and η \eta η to shrink with T T T , and the region ∥ e ( i 0 ) ∥ ∞ < ( 1 − c 0 ( T ) ) / c 1 ( T ) \lVert e^{(i_0)}\rVert_{\infty} < (1-c_0^{(T)})/c_1^{(T)} ∥ e ( i 0 ) ∥ ∞ < ( 1 − c 0 ( T ) ) / c 1 ( T ) shrinks with T T T , so the guarantee becomes uninformative for long sequences. For exact Newton on a chaotic system, this recovers the picture of Gonzalez et al. [34 ] : quadratic convergence holds, but only in a region whose size decays exponentially with T T T .
Iteration complexity. Under the conditions of (iii), ∥ e ( i ) ∥ ∞ ≤ ϵ \lVert e^{(i)}\rVert_{\infty} \le\epsilon ∥ e ( i ) ∥ ∞ ≤ ϵ as soon as
i − i 0 ≥ log ( ∥ e ( i 0 ) ∥ ∞ / ϵ ) log ( 1 / q ) i-i_0 \ge\frac{\log(\lVert e^{(i_0)}\rVert_{\infty}/\epsilon)}{\log(1/q)} i − i 0 ≥ log ( 1/ q ) log (∥ e ( i 0 ) ∥ ∞ / ϵ )
When λ c < 0 \lambda_c < 0 λ c < 0 and the states are bounded, this is independent of T T T . Since each iteration is a parallel scan of depth O ( log T ) O(\log T) O ( log T ) , this phase costs O ( log T ) O(\log T) O ( log T ) parallel depth. If accuracy is instead measured in the Euclidean norm over the whole trajectory, ∥ e ∥ 2 ≤ T ∥ e ∥ ∞ \lVert e\rVert_2 \le\sqrt{T}\lVert e\rVert_{\infty} ∥ e ∥ 2 ≤ T ∥ e ∥ ∞ requires ∥ e ∥ ∞ ≤ ϵ / T \lVert e\rVert_{\infty} \le\epsilon/\sqrt{T} ∥ e ∥ ∞ ≤ ϵ / T , which adds 1 2 log T / log ( 1 / q ) \frac{1}{2}\log T/\log(1/q) 2 1 log T / log ( 1/ q ) iterations and gives O ( log 2 T ) O(\log^2 T) O ( log 2 T ) depth, as in Gonzalez et al. [34 ] .
Locality and damped steps. The result requires ∥ e ( i 0 ) ∥ ∞ < ( 1 − c 0 ) / c 1 \lVert e^{(i_0)}\rVert_{\infty} < (1-c_0)/c_1 ∥ e ( i 0 ) ∥ ∞ < ( 1 − c 0 ) / c 1 . We do not bound the number of iterations needed to reach such an iteration from an arbitrary initialization. Theorem 1 only guarantees that the error vanishes after at most T T T iterations. When L = 0 L = 0 L = 0 (linear dynamics), c 1 = 0 c_1 = 0 c 1 = 0 and the condition reduces to c 0 < 1 c_0 < 1 c 0 < 1 . The analysis covers full steps. For a step scaled by α ∈ ( 0 , 1 ] \alpha\in(0,1] α ∈ ( 0 , 1 ] , e ( i + 1 ) = ( 1 − α ) e ( i ) + α ( e ( i ) − P r ) e^{(i+1)} = (1-\alpha)e^{(i)} + \alpha(e^{(i)}-\mathbf{P}r) e ( i + 1 ) = ( 1 − α ) e ( i ) + α ( e ( i ) − P r ) , so the per-iteration factor becomes 1 − α + α ( c 0 + c 1 ∥ e ( i ) ∥ ∞ ) 1-\alpha+\alpha(c_0+c_1\lVert e^{(i)}\rVert_{\infty}) 1 − α + α ( c 0 + c 1 ∥ e ( i ) ∥ ∞ ) , which still contracts under the same conditions, more slowly. Iterations where a line search replaces the quasi-Newton step altogether are not covered.
Limitations. Theorem 2 applies to any approximate blocks satisfying Assumptions 1–4 , which are imposed along the iterates. In particular, it does not show that the Broyden secant updates keep ρ \rho ρ small enough for c 0 < 1 c_0 < 1 c 0 < 1 . It describes how convergence depends on the block approximation error, whatever its source. The quantity ρ i \rho_i ρ i depends on x ∗ x^* x ∗ and can only be measured a posteriori. The constants are worst-case and, in our experiments, far from tight (Appendix § 10 ). The main slack comes from the row-sum bound (8), which adds the contributions of all upstream time steps as if they were aligned, and from the powers of a ~ \tilde{a} a ~ , which come from bounding each product of consecutive blocks separately. Finally, Assumption 4 is stated per merge. We do not relate η \eta η to the compression rank m m m or to the spectrum of the dynamics Jacobians.
Empirical diagnostics of the convergence analysis
Theorem 2 measures block quality by the error along the current trajectory error, ρ \rho ρ , rather than by the spectral-norm error σ \sigma σ used in prior analyses [22 ] . Here we measure both, together with the other quantities inside the theorem, along the iterates of the solvers. The main finding is that σ \sigma σ does not track convergence while ρ \rho ρ does.
Setup
We use the low-rank RNNs of Appendix § 12 .§ 1 (standard and MLP variants, D = 200 D = 200 D = 200 , Δ t ∈ { 0.5 , 3 } \Delta t \in\{0.5,3\} Δ t ∈ { 0.5 , 3 } ) and the hierarchical Gibbs sampler of Appendix § 13 (S ∈ { 10 , 50 , 100 } S \in\{10,50,100\} S ∈ { 10 , 50 , 100 } , D = 2 S + 2 D = 2S+2 D = 2 S + 2 ), with T = 10 3 T = 10^3 T = 1 0 3 and 8 chains per method and setting. On the RNNs, we compare Accelerated Parallel Broyden, Parallel Broyden, and diagonal quasi-Newton. On the Gibbs sampler, we compare the two Broyden variants for S ∈ { 10 , 50 } S \in\{10, 50\} S ∈ { 10 , 50 } , and run Accelerated Parallel Broyden alone for S = 100 S = 100 S = 100 , with a single chain. All other settings (damping, rank, diagonal initialization, line search) are those of the main experiments.
At each iteration, we rebuild the blocks A ~ t ( i ) \widetilde{A}^{(i)}_t A t ( i ) offline from the solver’s state. The rebuilt blocks reproduce the solver’s steps to a median relative error below 4 ⋅ 10 − 3 4 \cdot10^{-3} 4 ⋅ 1 0 − 3 . Iterations where the backtracking line search of Accelerated Parallel Broyden replaced the quasi-Newton step are excluded. Errors e ( i ) e^{(i)} e ( i ) are measured against the sequential trajectory. We record:
the spectral-norm block error σ i = max t ∥ A ~ t ( i ) − A t ( i ) ∥ 2 \sigma_i = \max_{t} \lVert\widetilde{A}^{(i)}_t - A^{(i)}_t \rVert_2 σ i = max t ∥ A t ( i ) − A t ( i ) ∥ 2 ,
the error-direction quantity ρ i \rho_i ρ i of Assumption 3,
the compression error at every merge of the scan tree,
the per-iteration error ratio ∥ e ( i + 1 ) ∥ ∞ / ∥ e ( i ) ∥ ∞ \lVert e^{(i+1)} \rVert_\infty/ \lVert e^{(i)} \rVert_\infty ∥ e ( i + 1 ) ∥ ∞ / ∥ e ( i ) ∥ ∞ .
We estimate α ~ \widetilde{\alpha} α and λ ~ \widetilde{\lambda} λ by fitting Assumption 1 to the products over the segments of the merge tree, and compute η \eta η and the ρ \rho ρ term of c 0 c_0 c 0 at the replayed iterations. To isolate the effect of damping, we also evaluate σ i \sigma_i σ i and ρ i \rho_i ρ i with the undamped blocks along the same iterates.
σ \sigma σ does not track convergence, ρ \rho ρ does
Table 3 reports both measures of block quality at the last iteration.
Table 3. Spectral-norm block error σ i \sigma_i σ i and error-direction quantity ρ i \rho_i ρ i at the last iteration, and median iteration counts over the 8 diagnostic chains. Diagonal quasi-Newton was run on the RNNs only.
The spectral-norm error is large and the same for all methods. At the last iteration, σ i \sigma_i σ i is about 0.9–1.1 for the RNNs at Δ t = 0.5 \Delta t = 0.5 Δ t = 0.5 , 5.3–6.6 at Δ t = 3 \Delta t = 3 Δ t = 3 , and 72–130 for the Gibbs sampler. Relative to the true block, the error max t ∥ A ~ t − A t ∥ 2 / ∥ A t ∥ 2 \max_t \lVert\widetilde{A}_t - A_t \rVert_2 / \lVert A_t \rVert_2 max t ∥ A t − A t ∥ 2 / ∥ A t ∥ 2 is about 0.54 at Δ t = 0.5 \Delta t = 0.5 Δ t = 0.5 , 0.98 at Δ t = 3 \Delta t = 3 Δ t = 3 , and essentially 1 for the Gibbs sampler. Since σ ≥ 0.88 \sigma\ge0.88 σ ≥ 0.88 in every setting, log ( e x + α σ ) > 0 \log(e^x + \alpha\sigma) > 0 log ( e x + α σ ) > 0 , and the sufficient condition of Proposition 1 fails everywhere. More importantly, σ i \sigma_i σ i does not distinguish the methods: in every setting, it is nearly identical for Accelerated Parallel Broyden, Parallel Broyden, and diagonal quasi-Newton (within 9%, and within 1% outside the MLP RNN at Δ t = 0.5 \Delta t = 0.5 Δ t = 0.5 ), although their iteration counts differ by up to 5.3 × 5.3\times 5.3 × . This is expected: the worst-case error is set by the part of the off-diagonal coupling that each approximation misses in some direction. Diagonal quasi-Newton discards this coupling entirely, and rank-m m m secant information only corrects it along the directions the iterates have explored.
The block error along the current trajectory error is small and tracks convergence. In contrast, ρ i \rho_i ρ i is 7–740 times smaller than σ i \sigma_i σ i . At the last iteration, the ordering of ρ i \rho_i ρ i matches the ordering of iteration counts in every setting: Accelerated Parallel Broyden has the smallest ρ i \rho_i ρ i and the fewest iterations, followed by Parallel Broyden and then diagonal quasi-Newton. The size of the gap also tracks convergence: the ratio of ρ i \rho_i ρ i between the two Broyden variants is 1.1 for the MLP RNN at Δ t = 0.5 \Delta t = 0.5 Δ t = 0.5 , where their iteration counts are close (9.5 versus 12), and 3.7–4.5 where Accelerated Parallel Broyden is 3–3.6 times faster.
Along the solve. Since the methods take different numbers of iterations, we also compare them on the RNNs at the same stage of the solve, by grouping iterations according to their root-mean-square residual (Table 4 ). Two conclusions hold at every stage. First, σ i \sigma_i σ i is the same for all three methods throughout: its relative value stays within about 0.02 across methods, at 0.53–0.62 for Δ t = 0.5 \Delta t = 0.5 Δ t = 0.5 and 0.97–0.99 for Δ t = 3 \Delta t = 3 Δ t = 3 . Second, diagonal quasi-Newton has the largest ρ i \rho_i ρ i at every stage, by a wide margin (0.13–0.17 versus 0.05–0.10 for the Broyden variants at Δ t = 0.5 \Delta t = 0.5 Δ t = 0.5 , and 0.79–0.91 versus 0.09–0.49 at $\Delta t = 3). The ordering between the two Broyden variants, however, emerges only near convergence. Early in the solve, the ρ i \rho_i ρ i of Accelerated Parallel Broyden is as large as that of Parallel Broyden or larger, and it drops clearly below only in the last decade of residual before the tolerance. This is consistent with the local nature of Theorem 2. It also means that ρ i \rho_i ρ i does not explain the advantage of Accelerated Parallel Broyden over the whole solve: part of this advantage comes from how quickly it reaches the regime of small ρ i \rho_i ρ i . Accelerated Parallel Broyden also shows transient spikes, with ρ i > 1 \rho_i > 1 ρ i > 1 in 2–18% of iterations, which is why the assumptions are imposed only from some iteration i 0 i_0 i 0 onward.
Table 4. Median ρ i \rho_i ρ i for the two Broyden variants on the RNNs at Δ t = 3 \Delta t = 3 Δ t = 3 , grouped by the root-mean-square residual ∥ r ∥ 2 / T D \lVert r\rVert_2/\sqrt{TD} ∥ r ∥ 2 / T D . Ranges are over the standard and MLP models.
Damping reduces ρ \rho ρ , not σ \sigma σ
For Parallel Broyden, damping leaves σ i \sigma_i σ i essentially unchanged but lowers ρ i \rho_i ρ i in every setting, and nearly eliminates iterations with $\rho_i > 1 ({xref}Table 5). Damping therefore improves the blocks where it matters, which is consistent with its effect on robustness ({xref}Appendix E.4`). For Accelerated Parallel Broyden, damping has little effect on ρ i \rho_i ρ i , and the undamped value is often slightly smaller. For diagonal quasi-Newton, damping again leaves σ i \sigma_i σ i unchanged (6.66 versus 6.61 for the MLP RNN at Δ t = 3 \Delta t = 3 Δ t = 3 ) but increases ρ i \rho_i ρ i (0.72 versus 0.22), as expected: it shrinks the blocks for stability rather than making them more accurate.
Table 5. Effect of damping on Parallel Broyden: σ i \sigma_i σ i and ρ i \rho_i ρ i at the last iteration and fraction of iterations with ρ i > 1 \rho_i > 1 ρ i > 1 , with damped and undamped blocks along the same iterates.
Other quantities in the theorem
The approximate system contracts. The fitted rates satisfy λ ~ < 0 \tilde{\lambda} < 0 λ ~ < 0 in every setting: λ ~ ∈ [ − 0.031 , − 0.016 ] \tilde{\lambda} \in[-0.031, -0.016] λ ~ ∈ [ − 0.031 , − 0.016 ] for the RNNs at Δ t = 0.5 \Delta t = 0.5 Δ t = 0.5 , [ − 0.134 , − 0.038 ] [-0.134, -0.038] [ − 0.134 , − 0.038 ] at Δ t = 3 \Delta t = 3 Δ t = 3 , and [ − 0.6 , − 0.12 ] [-0.6, -0.12] [ − 0.6 , − 0.12 ] for the Gibbs sampler. Assumption 1 therefore holds even though its sufficient condition in terms of σ \sigma σ fails.
Compression errors are small. For the RNNs, with the rank-revealing randomized compression of Appendix § 12 , η \eta η ranges from about 10 − 4 10^{-4} 1 0 − 4 to 0.11 0.11 0.11 across iterations. For the Gibbs sampler, the approximation is purely low rank, so no compression is required (Appendix § 13 ) and η = 0 \eta= 0 η = 0 in exact arithmetic. The measured values, between 4 ⋅ 10 − 8 4 \cdot10^{-8} 4 ⋅ 1 0 − 8 and 4 ⋅ 10 − 4 4 \cdot10^{-4} 4 ⋅ 1 0 − 4 , reflect floating-point error. Measuring the compression error relative to the exact product ∥ Π k , j ∥ 2 \lVert\Pi_{k,j} \rVert_2 ∥ Π k , j ∥ 2 instead would give spuriously large values on long segments whose exact product is numerically zero, which is why Assumption 4 uses the bound a ~ e λ ~ ∣ ν ∣ \tilde{a}e^{\tilde{\lambda}|\nu|} a ~ e λ ~ ∣ ν ∣ . Consistent with Appendix § 8 .§ 3 , the choice of compression scheme does not affect convergence.
The constants are not tight
Table 6 compares the bound with the observed contraction. The ρ \rho ρ term of c 0 c_0 c 0 alone exceeds 1 in every setting, so the theorem does not certify the observed convergence. In addition, λ c ≥ 0 \lambda_c \ge0 λ c ≥ 0 at a substantial fraction of iterations for the RNNs, because the compression penalty log ( 1 + a ~ 2 η ~ ) \log(1 + \tilde{a}^{2}\tilde{\eta}) log ( 1 + a ~ 2 η ~ ) is comparable to ∣ λ ~ ∣ |\tilde{\lambda}| ∣ λ ~ ∣ at Δ t = 0.5 \Delta t = 0.5 Δ t = 0.5 and the fitted a ~ \tilde{a} a ~ is large in early iterations of Accelerated Parallel Broyden. Convergence is also not monotone: the per-step error increases in 2–33% of iterations. Nevertheless, near convergence the error contracts by a factor of 0.30–0.95 per iteration, with the same ordering across methods as ρ i \rho_i ρ i . The main slack is the row-sum bound (8) , which treats contributions from all upstream time steps as aligned. Since a ~ \tilde{a} a ~ and λ ~ \tilde{\lambda} λ ~ are fitted only on segments aligned with the merge tree, the true constants can only be larger, and the conclusion c 0 > 1 c_0 > 1 c 0 > 1 is unaffected. A bound in terms of σ \sigma σ instead of ρ \rho ρ would be larger by the ratio σ i / ρ i \sigma_i/\rho_i σ i / ρ i , which is 16–740 for the Broyden variants.
Table 6. The ρ \rho ρ term of c 0 c_0 c 0 (range over iterations with λ c < 0 \lambda_c < 0 λ c < 0 ), fraction of iterations with λ c < 0 \lambda_c < 0 λ c < 0 , observed contraction ∥ e ( i + 1 ) ∥ ∞ / ∥ e ( i ) ∥ ∞ \lVert e^{(i+1)} \rVert_\infty/\lVert e^{(i)} \rVert_\infty ∥ e ( i + 1 ) ∥ ∞ / ∥ e ( i ) ∥ ∞ (median over the last three iterations), and fraction of iterations where the error increases.
Summary
The spectral-norm error σ \sigma σ is not the right measure of block quality: it is large, it is essentially the same for all three methods although their iteration counts differ by up to 5.3×, and damping leaves it unchanged although damping helps Parallel Broyden converge. The error along the current error, ρ \rho ρ , is the quantity that tracks convergence: it is 7–740 times smaller than σ \sigma σ , diagonal quasi-Newton has the largest ρ \rho ρ at every stage of the solve, near convergence ρ \rho ρ is ordered as Accelerated Parallel Broyden < Parallel Broyden < diagonal quasi-Newton in every setting, matching their iteration counts, and damping reduces it. The approximate system contracts and compression errors are small. The theorem identifies this mechanism, but its constants are too conservative to certify the observed rates.
Broyden updates
This section gives the explicit blockwise Broyden updates used to construct the local dynamics Jacobian approximations in § 3.1 . We use the same notation as in the main text. After computing the iterate x 1 : T ( i + 1 ) \mathbf{x}_{1:T}^{(i+1)} x 1 : T ( i + 1 ) , for each time index t t t , define the trajectory secant
p t ( i ) : = x t − 1 ( i + 1 ) − x t − 1 ( i ) p_t^{(i)} := x_{t-1}^{(i+1)} - x_{t-1}^{(i)} p t ( i ) := x t − 1 ( i + 1 ) − x t − 1 ( i )
and the corresponding finite difference through the local dynamics map
q t ( i ) : = f t ( x t − 1 ( i + 1 ) ) − f t ( x t − 1 ( i ) ) . q_t^{(i)} := f_t(x_{t-1}^{(i+1)}) - f_t(x_{t-1}^{(i)}). q t ( i ) := f t ( x t − 1 ( i + 1 ) ) − f t ( x t − 1 ( i ) ) .
The goal is to update an approximation
A ~ t ( i ) ≈ A t ( i ) : = ∂ f t ∂ x t − 1 ( x t − 1 ( i ) ) \widetilde{A}_t^{(i)} \approx A_t^{(i)} := \frac{\partial f_t}{\partial x_{t-1}}\left(x_{t-1}^{(i)}\right) A t ( i ) ≈ A t ( i ) := ∂ x t − 1 ∂ f t ( x t − 1 ( i ) )
using only the secant pair ( p t ( i ) , q t ( i ) ) (p_t^{(i)}, q_t^{(i)}) ( p t ( i ) , q t ( i ) ) .
Standard rank-one Broyden update
The standard Broyden update enforces the secant condition
A ~ t ( i + 1 ) p t ( i ) = q t ( i ) . (9) \widetilde{A}_t^{(i+1)}p_t^{(i)} = q_t^{(i)}. \tag*{(9)} A t ( i + 1 ) p t ( i ) = q t ( i ) . (9)
Since this condition does not uniquely determine the full matrix A ~ t ( i + 1 ) \widetilde{A}_t^{(i+1)} A t ( i + 1 ) , Broyden’s method chooses the update that is closest to the previous approximation in Frobenius norm:
A ~ t ( i + 1 ) = arg min A ∥ A − A ~ t ( i ) ∥ F s.t. A p t ( i ) = q t ( i ) . (10) \widetilde{A}_t^{(i+1)} = \underset{A}{\arg\min}\ \lVert A-\widetilde{A}_t^{(i)}\rVert_F \quad\text{s.t.}\quad Ap_t^{(i)}=q_t^{(i)}. \tag*{(10)} A t ( i + 1 ) = A arg min ∥ A − A t ( i ) ∥ F s.t. A p t ( i ) = q t ( i ) . (10)
Writing the update as B = A ~ t ( i ) + Δ t ( i ) B=\widetilde{A}_t^{(i)}+\Delta_t^{(i)} B = A t ( i ) + Δ t ( i ) , the constraint becomes
Δ t ( i ) p t ( i ) = q t ( i ) − A ~ t ( i ) p t ( i ) . \Delta_t^{(i)}p_t^{(i)} = q_t^{(i)}-\widetilde{A}_t^{(i)}p_t^{(i)}. Δ t ( i ) p t ( i ) = q t ( i ) − A t ( i ) p t ( i ) .
Let
y t ( i ) : = q t ( i ) − A ~ t ( i ) p t ( i ) y_t^{(i)} := q_t^{(i)}-\widetilde{A}_t^{(i)}p_t^{(i)} y t ( i ) := q t ( i ) − A t ( i ) p t ( i )
denote the current secant residual. Then the least-change problem is
min Δ ∥ Δ ∥ F s.t. Δ p t ( i ) = y t ( i ) . \underset{\Delta}{\min}\ \lVert\Delta\rVert_F \quad\text{s.t.}\quad\Delta p_t^{(i)}=y_t^{(i)}. Δ min ∥ Δ ∥ F s.t. Δ p t ( i ) = y t ( i ) .
The minimum-norm solution is rank one:
Δ t ( i ) = y t ( i ) p t ( i ) T p t ( i ) T p t ( i ) . \Delta_t^{(i)}=\frac{y_t^{(i)}p_t^{(i)\mathsf{T}}}{p_t^{(i)\mathsf{T}}p_t^{(i)}}. Δ t ( i ) = p t ( i ) T p t ( i ) y t ( i ) p t ( i ) T .
Thus the blockwise Broyden update is
A ~ t ( i + 1 ) = A ~ t ( i ) + ( q t ( i ) − A ~ t ( i ) p t ( i ) ) p t ( i ) T p t ( i ) T p t ( i ) . (11) \widetilde{A}_t^{(i+1)}=\widetilde{A}_t^{(i)}+
\frac{\left(q_t^{(i)}-\widetilde{A}_t^{(i)}p_t^{(i)}\right)p_t^{(i)\mathsf{T}}}{p_t^{(i)\mathsf{T}}p_t^{(i)}}. \tag*{(11)} A t ( i + 1 ) = A t ( i ) + p t ( i ) T p t ( i ) ( q t ( i ) − A t ( i ) p t ( i ) ) p t ( i ) T . (11)
Starting from a diagonal initialization
A ~ t ( 0 ) = D t ( 0 ) , D t ( 0 ) = diag ( d t ( 0 ) ) , \widetilde{A}_t^{(0)}=D_t^{(0)},\qquad D_t^{(0)}=\operatorname{diag}(d_t^{(0)}), A t ( 0 ) = D t ( 0 ) , D t ( 0 ) = diag ( d t ( 0 ) ) ,
each update in (11) adds one rank-one correction. After i i i updates, the approximation can therefore be written as
A ~ t ( i ) = D t ( 0 ) + U t ( i ) V t ( i ) T , (12) \widetilde{A}_t^{(i)}=D_t^{(0)}+U_t^{(i)}V_t^{(i)\mathsf{T}}, \tag*{(12)} A t ( i ) = D t ( 0 ) + U t ( i ) V t ( i ) T , (12)
where the columns of U t ( i ) U_t^{(i)} U t ( i ) and V t ( i ) V_t^{(i)} V t ( i ) are the accumulated rank-one factors. In particular, if
u t ( i ) = q t ( i ) − A ~ t ( i ) p t ( i ) , v t ( i ) = p t ( i ) p t ( i ) T p t ( i ) , u_t^{(i)}=q_t^{(i)}-\widetilde{A}_t^{(i)}p_t^{(i)},\qquad
v_t^{(i)}=\frac{p_t^{(i)}}{p_t^{(i)\mathsf{T}}p_t^{(i)}}, u t ( i ) = q t ( i ) − A t ( i ) p t ( i ) , v t ( i ) = p t ( i ) T p t ( i ) p t ( i ) ,
then the update adds u t ( i ) v t ( i ) T u_t^{(i)}v_t^{(i)\mathsf{T}} u t ( i ) v t ( i ) T to the current approximation.
Limited-memory Broyden updates
Simple truncation. The standard rank-one Broyden update adds one new low-rank correction at each outer iteration. To keep the representation size fixed, we use a limited-memory variant with maximum rank m m m . Throughout this section, we assume the diagonal baseline is initialized as γ I D \gamma I_D γ I D , so each approximate block has the form
A ~ t ( i ) = γ I D + U t ( i ) V t ( i ) T , U t ( i ) , V t ( i ) ∈ R D × m . \widetilde{A}^{(i)}_t = \gamma I_D + U^{(i)}_t V^{(i)\mathsf{T}}_t,\qquad U^{(i)}_t,V^{(i)}_t \in\mathbb{R}^{D \times m}. A t ( i ) = γ I D + U t ( i ) V t ( i ) T , U t ( i ) , V t ( i ) ∈ R D × m .
When a new rank-one correction u t ( i ) ( v t ( i ) ) T u^{(i)}_t(v^{(i)}_t)^{\mathsf{T}} u t ( i ) ( v t ( i ) ) T is computed and the memory is already full, we discard the oldest stored correction and append the newest one:
U t ( i + 1 ) = [ U t ( i ) [ : , 2 ] , … , U t ( i ) [ : , m ] , u t ( i ) ] , V t ( i + 1 ) = [ V t ( i ) [ : , 2 ] , … , V t ( i ) [ : , m ] , v t ( i ) ] . U^{(i+1)}_t = \left[U^{(i)}_t[:,2],\ldots,U^{(i)}_t[:,m],u^{(i)}_t\right],\qquad V^{(i+1)}_t = \left[V^{(i)}_t[:,2],\ldots,V^{(i)}_t[:,m],v^{(i)}_t\right]. U t ( i + 1 ) = [ U t ( i ) [ : , 2 ] , … , U t ( i ) [ : , m ] , u t ( i ) ] , V t ( i + 1 ) = [ V t ( i ) [ : , 2 ] , … , V t ( i ) [ : , m ] , v t ( i ) ] .
Thus the rank remains at most m m m , and applying each block costs O ( D m ) O(Dm) O ( D m ) . This simple truncation strategy is the default limited-memory scheme used in our experiments.
L-BFGS-style identity rescaling. We also considered an L-BFGS-style scalar-rescaling variant for the identity baseline. The motivation is that, after truncation, the stored rank-one corrections contain only the most recent secant information, so the identity baseline should reflect the scale of the local Jacobian not captured by this limited memory. For each transition f t f_t f t , we store the last m m m secant pairs { ( p t , j , q t , j ) } j = i − m i − 1 \{(p_{t,j},q_{t,j})\}_{j=i-m}^{i-1} {( p t , j , q t , j ) } j = i − m i − 1 . At iteration i i i , we choose a scalar γ t ( i ) \gamma_t^{(i)} γ t ( i ) from the most recent pair by fitting the identity baseline to the secant target:
γ t ( i ) = arg min γ ∥ γ p t , i − 1 − q t , i − 1 ∥ 2 2 = ⟨ p t , i − 1 , q t , i − 1 ⟩ ∥ p t , i − 1 ∥ 2 2 + ε , \gamma_t^{(i)}=\underset{\gamma}{\arg\min}\ \lVert\gamma p_{t,i-1}-q_{t,i-1}\rVert_2^2=\frac{\langle p_{t,i-1},q_{t,i-1}\rangle}{\lVert p_{t,i-1}\rVert_2^2+\varepsilon}, γ t ( i ) = γ arg min ∥ γ p t , i − 1 − q t , i − 1 ∥ 2 2 = ∥ p t , i − 1 ∥ 2 2 + ε ⟨ p t , i − 1 , q t , i − 1 ⟩ ,
with a small ε > 0 \varepsilon>0 ε > 0 for numerical stability. We then rebuild the limited-memory approximation from the rescaled baseline A ~ t , 0 ( i ) = γ t ( i ) I D \widetilde{A}^{(i)}_{t,0}=\gamma_t^{(i)}I_D A t , 0 ( i ) = γ t ( i ) I D by replaying the stored Broyden updates in chronological order:
A ~ t , j + 1 ( i ) = A ~ t , j ( i ) + ( q t , j − A ~ t , j ( i ) p t , j ) p t , j T ∥ p t , j ∥ 2 2 + ε , j = i − m , … , i − 1. \widetilde{A}^{(i)}_{t,j+1}=\widetilde{A}^{(i)}_{t,j}+\frac{(q_{t,j}-\widetilde{A}^{(i)}_{t,j}p_{t,j})p_{t,j}^{\mathsf{T}}}{\lVert p_{t,j}\rVert_2^2+\varepsilon},\qquad j=i-m,\ldots,i-1. A t , j + 1 ( i ) = A t , j ( i ) + ∥ p t , j ∥ 2 2 + ε ( q t , j − A t , j ( i ) p t , j ) p t , j T , j = i − m , … , i − 1.
After replaying the stored pairs, we set A ~ t ( i ) \widetilde{A}^{(i)}_t A t ( i ) to the resulting matrix. This corresponds to the identity_rescaled variant in our implementation. It is analogous in spirit to limited-memory quasi-Newton methods such as L-BFGS, where a scalar identity baseline is chosen from recent secant information and then combined with a finite history of secant updates. In our experiments, this variant did not lead to significant improvement over simple truncation (Figure 6 ). We note that the L-BFGS-style approach appears slightly more stable than the simple truncation, with a lower third quartile.
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.
Multisecant Broyden update
The rank-one Broyden update incorporates one secant condition at a time. The multisecant variant instead fits several recent secant pairs simultaneously. For each transition f t f_t f t , let
P t ( i ) = [ p t ( i − m i ) , … , p t ( i − 1 ) ] ∈ R D × m i , Q t ( i ) = [ q t ( i − m i ) , … , q t ( i − 1 ) ] ∈ R D × m i , P_t^{(i)}=\left[p_t^{(i-m_i)},\ldots,p_t^{(i-1)}\right]\in\mathbb{R}^{D\times m_i},\qquad Q_t^{(i)}=\left[q_t^{(i-m_i)},\ldots,q_t^{(i-1)}\right]\in\mathbb{R}^{D\times m_i}, P t ( i ) = [ p t ( i − m i ) , … , p t ( i − 1 ) ] ∈ R D × m i , Q t ( i ) = [ q t ( i − m i ) , … , q t ( i − 1 ) ] ∈ R D × m i ,
where m i = min ( m , i ) m_i=\min(m,i) m i = min ( m , i ) is the number of stored secants. The multisecant condition is
A ~ t ( i ) P t ( i ) = Q t ( i ) . (13) \widetilde{A}_t^{(i)}P_t^{(i)}=Q_t^{(i)}. \tag*{(13)} A t ( i ) P t ( i ) = Q t ( i ) . (13)
Unlike the rank-one update, which modifies the previous approximation A ~ t ( i − 1 ) \widetilde{A}_t^{(i-1)} A t ( i − 1 ) , our accelerated variant builds a fresh rank-m m m correction on top of a diagonal baseline. Let D t ( i ) D_t^{(i)} D t ( i ) denote this baseline, for example D t ( i ) = γ I D D_t^{(i)}=\gamma I_D D t ( i ) = γ I D or a freshly computed diagonal approximation. We write
A ~ t ( i ) = D t ( i ) + Δ t ( i ) . (14) \widetilde{A}_t^{(i)}=D_t^{(i)}+\Delta_t^{(i)}. \tag*{(14)} A t ( i ) = D t ( i ) + Δ t ( i ) . (14)
The correction is chosen to have minimum Frobenius norm while satisfying the stored secant equations:
Δ t ( i ) = arg min Δ ∥ Δ ∥ F s.t. ( D t ( i ) + Δ ) P t ( i ) = Q t ( i ) . \Delta_{t}^{(i)} = \arg\min_{\Delta} \lVert\Delta\rVert_{F} \quad\text{s.t.} \quad\left(D_{t}^{(i)}+\Delta\right)P_{t}^{(i)}=Q_{t}^{(i)}. Δ t ( i ) = arg Δ min ∥ Δ ∥ F s.t. ( D t ( i ) + Δ ) P t ( i ) = Q t ( i ) .
Equivalently,
Δ t ( i ) P t ( i ) = Q t ( i ) − D t ( i ) P t ( i ) . \Delta_{t}^{(i)}P_{t}^{(i)}=Q_{t}^{(i)}-D_{t}^{(i)}P_{t}^{(i)}. Δ t ( i ) P t ( i ) = Q t ( i ) − D t ( i ) P t ( i ) .
Define the residual matrix
R t ( i ) : = Q t ( i ) − D t ( i ) P t ( i ) ∈ R D × m i . R_{t}^{(i)} := Q_{t}^{(i)}-D_{t}^{(i)}P_{t}^{(i)} \in\mathbb{R}^{D \times m_i}. R t ( i ) := Q t ( i ) − D t ( i ) P t ( i ) ∈ R D × m i .
The minimum-Frobenius-norm solution is
Δ t ( i ) = R t ( i ) P t ( i ) † , \Delta_{t}^{(i)}=R_{t}^{(i)}P_{t}^{(i)\dagger}, Δ t ( i ) = R t ( i ) P t ( i ) † ,
where P t ( i ) † P_{t}^{(i)\dagger} P t ( i ) † is the Moore–Penrose pseudoinverse. If P t ( i ) P_{t}^{(i)} P t ( i ) has full column rank, then
P t ( i ) † = ( P t ( i ) T P t ( i ) ) − 1 P t ( i ) T . P_{t}^{(i)\dagger}=\left(P_{t}^{(i)\mathsf{T}}P_{t}^{(i)}\right)^{-1}P_{t}^{(i)\mathsf{T}}. P t ( i ) † = ( P t ( i ) T P t ( i ) ) − 1 P t ( i ) T .
Thus, in the full-rank case,
A ~ t ( i ) = D t ( i ) + ( Q t ( i ) − D t ( i ) P t ( i ) ) ( P t ( i ) T P t ( i ) ) − 1 P t ( i ) T (15) \widetilde{A}_{t}^{(i)}=D_{t}^{(i)}+\left(Q_{t}^{(i)}-D_{t}^{(i)}P_{t}^{(i)}\right)\left(P_{t}^{(i)\mathsf{T}}P_{t}^{(i)}\right)^{-1}P_{t}^{(i)\mathsf{T}} \tag*{(15)} A t ( i ) = D t ( i ) + ( Q t ( i ) − D t ( i ) P t ( i ) ) ( P t ( i ) T P t ( i ) ) − 1 P t ( i ) T (15)
In practice, we use a small ridge term for numerical stability,
A ~ t ( i ) = D t ( i ) + ( Q t ( i ) − D t ( i ) P t ( i ) ) ( P t ( i ) T P t ( i ) + ϵ I ) − 1 P t ( i ) T , (16) \widetilde{A}_{t}^{(i)}=D_{t}^{(i)}+\left(Q_{t}^{(i)}-D_{t}^{(i)}P_{t}^{(i)}\right)\left(P_{t}^{(i)\mathsf{T}}P_{t}^{(i)}+\epsilon I\right)^{-1}P_{t}^{(i)\mathsf{T}}, \tag*{(16)} A t ( i ) = D t ( i ) + ( Q t ( i ) − D t ( i ) P t ( i ) ) ( P t ( i ) T P t ( i ) + ϵ I ) − 1 P t ( i ) T , (16)
with ϵ > 0 \epsilon> 0 ϵ > 0 small.
The correction in (14) has rank at most m i m_i m i . Therefore the accelerated multisecant update produces a DPLR approximation directly:
A ~ t ( i ) = D t ( i ) + U t ( i ) V t ( i ) T , rank ( U t ( i ) V t ( i ) T ) ≤ m i . \widetilde{A}_{t}^{(i)}=D_{t}^{(i)}+U_{t}^{(i)}V_{t}^{(i)\mathsf{T}}, \qquad\operatorname{rank}\left(U_{t}^{(i)}V_{t}^{(i)\mathsf{T}}\right)\le m_i. A t ( i ) = D t ( i ) + U t ( i ) V t ( i ) T , rank ( U t ( i ) V t ( i ) T ) ≤ m i .
With ridge stabilization, one can take
U t ( i ) = Q t ( i ) − D t ( i ) P t ( i ) , V t ( i ) T = ( P t ( i ) T P t ( i ) + η I ) − 1 P t ( i ) T . U_{t}^{(i)}=Q_{t}^{(i)}-D_{t}^{(i)}P_{t}^{(i)}, \qquad V_{t}^{(i)\mathsf{T}}=\left(P_{t}^{(i)\mathsf{T}}P_{t}^{(i)}+\eta I\right)^{-1}P_{t}^{(i)\mathsf{T}}. U t ( i ) = Q t ( i ) − D t ( i ) P t ( i ) , V t ( i ) T = ( P t ( i ) T P t ( i ) + η I ) − 1 P t ( i ) T .
This is the update used in Accelerated Parallel Broyden: rather than accumulating one rank-one correction per iteration, it fits several recent secant directions at once, yielding a rank-at-most-m m m correction in a single update.
Damping of the low-rank corrections
As discussed by Gonzalez et al. [21 ] , large eigenvalues in the linearized transition dynamics can lead to unstable parallel Newton updates. Their scale-ELK method addresses this issue by shrinking the full dynamics Jacobian by a factor ( 1 − k ) (1-k) ( 1 − k ) , where k ∈ [ 0 , 1 ] k \in[0,1] k ∈ [ 0 , 1 ] is a damping parameter. We use the same idea, but apply it only to the low-rank Broyden correction rather than to the entire Jacobian approximation.
For the rank-one Broyden update, let
Δ t ( i ) = ( q t ( i ) − A ~ t ( i ) p t ( i ) ) p t ( i ) T p t ( i ) T p t ( i ) \Delta_t^{(i)} = \frac{\left(q_t^{(i)}-\widetilde{A}_t^{(i)}p_t^{(i)}\right)p_t^{(i)\mathsf{T}}}{p_t^{(i)\mathsf{T}}p_t^{(i)}} Δ t ( i ) = p t ( i ) T p t ( i ) ( q t ( i ) − A t ( i ) p t ( i ) ) p t ( i ) T
denote the secant correction. Instead of applying the full correction, we use
A ~ t ( i + 1 ) = A ~ t ( i ) + ( 1 − k ) Δ t ( i ) , k ∈ [ 0 , 1 ] . (17) \widetilde{A}_t^{(i+1)} = \widetilde{A}_t^{(i)} + (1-k)\Delta_t^{(i)}, \qquad k \in[0,1]. \tag*{(17)} A t ( i + 1 ) = A t ( i ) + ( 1 − k ) Δ t ( i ) , k ∈ [ 0 , 1 ] . (17)
Thus k = 0 k=0 k = 0 recovers the standard Broyden update, while larger k k k values damp the new low-rank contribution. At k = 1 k=1 k = 1 , the secant correction is completely suppressed and the block approximation is left unchanged.
For the multisecant update, recall that Accelerated Parallel Broyden builds a fresh correction on top of a diagonal baseline D t ( i ) D_t^{(i)} D t ( i ) . With damping, we use
A ~ t ( i ) = D t ( i ) + ( 1 − k ) ( Q t ( i ) − D t ( i ) P t ( i ) ) ( P t ( i ) T P t ( i ) + η I ) − 1 P t ( i ) T . (18) \widetilde{A}_t^{(i)} = D_t^{(i)} + (1-k)\left(Q_t^{(i)}-D_t^{(i)}P_t^{(i)}\right)\left(P_t^{(i)\mathsf{T}}P_t^{(i)}+\eta I\right)^{-1}P_t^{(i)\mathsf{T}}. \tag*{(18)} A t ( i ) = D t ( i ) + ( 1 − k ) ( Q t ( i ) − D t ( i ) P t ( i ) ) ( P t ( i ) T P t ( i ) + η I ) − 1 P t ( i ) T . (18)
Here P t ( i ) P_t^{(i)} P t ( i ) and Q t ( i ) Q_t^{(i)} Q t ( i ) are the matrices of recent trajectory secants and dynamics finite differences, respectively, and η > 0 \eta>0 η > 0 is the small ridge parameter used for numerical stability.
The damping parameter controls a stability–accuracy tradeoff. Larger values of k k k shrink the low-rank correction and can reduce instabilities caused by large eigenvalues in the approximate transition blocks. However, excessive damping also weakens the secant information, making the Jacobian approximation closer to its diagonal baseline and typically increases the number of Newton iterations (Figure 7 ). In practice, we therefore choose k k k heuristically as small as possible while remaining stable across the tested instances. We tune k k k per method and setting. The values are given in Appendices § 12 .§ 1 and § 13 . We did not need damping for the diffusion experiment.
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 D = 100 D = 100 , k = 0.5 k = 0.5 k = 0.5 gives worse median performance than smaller damping values across all tested trajectory lengths.
RNN experiment details
All RNN experiments use 32 chains, a maximum of 1000 iterations, and the stopping criterion
∥ r ( x 1 : T ) ∥ 2 T D < 10 − 4 , \frac{\lVert r(x_{1:T})\rVert_2}{\sqrt{T D}} < 10^{-4}, T D ∥ r ( x 1 : T ) ∥ 2 < 1 0 − 4 ,
that is, an absolute root-mean-square one-step residual below 10 − 4 10^{-4} 1 0 − 4 per state coordinate, which is small relative to the scale of the states. Computations are in float32 with highest-precision matrix multiplications. We report medians and interquartile ranges over chains. Iteration counts include all chains, with non-converged chains counted at the 1000-iteration cap, and runtimes are computed over converged chains. The noise sequence { ϵ t } t = 1 T \{\epsilon_t\}_{t=1}^{T} { ϵ t } t = 1 T is fixed before running the solver, so each model defines a deterministic input-driven state-space system. Newton uses the full Jacobian computed by reverse-mode automatic differentiation, and diagonal quasi-Newton extracts its diagonal from it. For the models considered here, the Jacobian and its diagonal are available in closed form or cheaply from the low-rank structure, and would be computed directly in practice. We nevertheless treat the transition f f f as a black box and obtain them by automatic differentiation, as one would for a general nonlinear state-space model. For both Broyden variants, the low-rank products formed during the parallel scan are compressed back to rank m m m with a rank-revealing variant of the randomized compression described in the main text. In this variant, sketch columns that are numerically dependent, with a relative remainder below 10 − 4 10^{-4} 1 0 − 4 , are dropped rather than normalized. This prevents rank-deficient corrections, which are frequent in float32, from introducing spurious directions. Accelerated Parallel Broyden uses a Gram regularization ε = 10 − 6 \varepsilon= 10^{-6} ε = 1 0 − 6 . All runtimes are measured on a single NVIDIA H100 GPU.
Low-rank RNNs
The state x t ∈ R D x_t \in\mathbb{R}^{D} x t ∈ R D evolves according to
x t = a x t − 1 + Δ t τ M ψ ( N T ϕ ( x t − 1 ) ) + ϵ t , M , N ∈ R D × R , (19) x_t = a x_{t-1} + \frac{\Delta t}{\tau} M \psi\left(N^{\mathsf{T}}\phi(x_{t-1})\right) + \epsilon_t,\qquad M,N \in\mathbb{R}^{D \times R}, \tag*{(19)} x t = a x t − 1 + τ Δ t M ψ ( N T ϕ ( x t − 1 ) ) + ϵ t , M , N ∈ R D × R , (19)
where a = 1 − Δ t / τ a = 1 - \Delta t/\tau a = 1 − Δ t / τ , ϕ = tanh \phi= \tanh ϕ = tanh is applied elementwise, and ϵ t ∼ N ( 0 , σ 2 I D ) \epsilon_t \sim\mathcal{N}(0,\sigma^2 I_D) ϵ t ∼ N ( 0 , σ 2 I D ) with σ = 0.1 \sigma= 0.1 σ = 0.1 . The standard low-rank RNN uses ψ ( z ) = z \psi(z) = z ψ ( z ) = z , so that the recurrent weight matrix is W = M N T W = MN^{\mathsf{T}} W = M N T . The low-rank MLP-RNN uses ψ ( z ) = z + β MLP ( z ) \psi(z) = z + \beta\operatorname{MLP}(z) ψ ( z ) = z + β MLP ( z ) with β = 0.5 \beta= 0.5 β = 0.5 , where the MLP has 8 hidden layers of width D D D and tanh activations. Given a gain g g g , we draw
M i j ∼ N ( 0 , g 2 D ) , N i j ∼ N ( 0 , 1 R ) . (20) M_{ij} \sim\mathcal{N}\left(0,\frac{g^2}{D}\right),\qquad N_{ij} \sim\mathcal{N}\left(0,\frac{1}{R}\right). \tag*{(20)} M ij ∼ N ( 0 , D g 2 ) , N ij ∼ N ( 0 , R 1 ) . (20)
This normalization keeps the coordinate-wise recurrent input at scale O ( g ) O(g) O ( g ) when the components of ϕ ( x ) \phi(x) ϕ ( x ) are O ( 1 ) O(1) O ( 1 ) , while the nonzero singular values of M N T MN^{\mathsf{T}} M N T are typically of order g D / R g\sqrt{D/R} g D / R . Each chain draws its own weights, noise, initial state and initial guess, with x 0 , x 1 : T ( 0 ) ∼ 0.1 N ( 0 , I ) x_0, x_{1:T}^{(0)} \sim0.1\mathcal{N}(0,I) x 0 , x 1 : T ( 0 ) ∼ 0.1 N ( 0 , I ) . Seeds whose sequential trajectory saturates are discarded. The criteria chosen for saturation are that, after a burn-in of T / 4 T/4 T /4 steps, some unit has mean ∣ tanh ∣ > 0.8 \lvert\tanh\rvert> 0.8 ∣ tanh ∣ > 0.8 or mean tanh ′ < 0.1 \tanh' < 0.1 tanh ′ < 0.1 .
The transition Jacobian of (19) is
A t = ∂ x t ∂ x t − 1 = a I D + Δ t τ M ψ ′ ( N T ϕ ( x t − 1 ) ) N T diag ( ϕ ′ ( x t − 1 ) ) , (21) A_t = \frac{\partial x_t}{\partial x_{t-1}} = aI_D + \frac{\Delta t}{\tau} M\psi'\left(N^{\mathsf{T}}\phi(x_{t-1})\right)N^{\mathsf{T}}\operatorname{diag}\left(\phi'(x_{t-1})\right), \tag*{(21)} A t = ∂ x t − 1 ∂ x t = a I D + τ Δ t M ψ ′ ( N T ϕ ( x t − 1 ) ) N T diag ( ϕ ′ ( x t − 1 ) ) , (21)
where ψ ′ \psi' ψ ′ is the R × R R \times R R × R Jacobian of ψ \psi ψ . For both models, the off-diagonal term has rank at most R R R , so the true Jacobian is exactly diagonal plus rank R R R (Figure 8 ). The MLP makes each evaluation of f f f and each Jacobian computation more expensive without changing this structure.
Figure 8. Example of the dynamics Jacobian matrix of the standard low-rank RNN. The matrix is exactly diagonal plus rank R = 3 R = 3 R = 3 .
We use R = 3 R = 3 R = 3 , g = 2 g = 2 g = 2 , τ = 10 \tau= 10 τ = 10 , and D ∈ { 100 , 200 } D \in\{100, 200\} D ∈ { 100 , 200 } , with D = 200 D = 200 D = 200 in Figure 1 . The step size Δ t \Delta t Δ t controls the balance between the two terms of (21) . Before modulation by ψ ′ \psi' ψ ′ and ϕ ′ \phi' ϕ ′ , the low-rank term has typical spectral scale ( Δ t / τ ) g D / R (\Delta t/\tau)g\sqrt{D/R} ( Δ t / τ ) g D / R , which is about 0.8 0.8 0.8 for D = 200 D = 200 D = 200 and Δ t = 0.5 \Delta t = 0.5 Δ t = 0.5 .
against a diagonal a = 0.95 a = 0.95 a = 0.95 . For Δ t = 3 \Delta t = 3 Δ t = 3 it is about 4.9, against a = 0.7 a = 0.7 a = 0.7 . The off-diagonal coupling is therefore weak for Δ t = 0.5 \Delta t = 0.5 Δ t = 0.5 and dominant for Δ t = 3 \Delta t = 3 Δ t = 3 . Table 8 reports iteration counts for both models and both step sizes. In all settings, Accelerated Parallel Broyden needs fewer iterations than Parallel Broyden, and the gap is larger for Δ t = 3 \Delta t = 3 Δ t = 3 , independently of the model.
Table 8. Iterations of the Broyden variants on the low-rank RNNs (D = 200 D = 200 D = 200 ). Median over all 32 chains, with non-converged chains counted at the 1000-iteration cap, and number of converged chains.
For Parallel Broyden and Accelerated Parallel Broyden, we use rank m = R = 3 m = R = 3 m = R = 3 and initialize the diagonal at γ = a \gamma= a γ = a , so that A ~ t ( 0 ) = a I D \tilde{A}_{t}^{(0)} = aI_D A ~ t ( 0 ) = a I D matches the diagonal of (21) . Accelerated Parallel Broyden uses a backtracking line search with sufficient-decrease constant c = 10 − 3 c = 10^{-3} c = 1 0 − 3 , and Parallel Broyden uses none. For each method, the damping minimizes the median iteration count over chains, with non-converged chains counted at the cap. It is tuned on T ∈ { 10 4 , 10 5 } T \in\{10^{4}, 10^{5}\} T ∈ { 1 0 4 , 1 0 5 } , or on T = 10 4 T = 10^{4} T = 1 0 4 only for diagonal quasi-Newton, and reused for T = 10 3 T = 10^{3} T = 1 0 3 . The resulting values are listed in Table 7 .
Table 7. Damping values for the low-rank RNNs. The same values are used for both models.
Full-rank DMF RNN
The discretized mean-field RNN [38 ] evolves according to
x t = W tanh ( x t − 1 ) + ϵ t , W i j ∼ N ( 0 , g 2 D ) , (22) x_t = W \tanh(x_{t-1}) + \epsilon_t,\qquad W_{ij} \sim\mathcal{N}\left(0,\frac{g^2}{D}\right), \tag*{(22)} x t = W tanh ( x t − 1 ) + ϵ t , W ij ∼ N ( 0 , D g 2 ) , (22)
with g = 1.7 g = 1.7 g = 1.7 , D = 128 D = 128 D = 128 , self-couplings included, ϵ t ∼ N ( 0 , I D ) \epsilon_t \sim\mathcal{N}(0,I_D) ϵ t ∼ N ( 0 , I D ) , and T = 10 4 T = 10^4 T = 1 0 4 . A single weight matrix W W W is shared by all 32 chains, which differ in their noise sequence and initial guess, with x 0 = 0 x_0 = 0 x 0 = 0 and x 1 : T ( 0 ) ∼ N ( 0 , I ) x_{1:T}^{(0)} \sim\mathcal{N}(0,I) x 1 : T ( 0 ) ∼ N ( 0 , I ) . The Jacobian A t = W diag ( sech 2 ( x t − 1 ) ) A_t = W\operatorname{diag}(\operatorname{sech}^2(x_{t-1})) A t = W diag ( sech 2 ( x t − 1 )) is dense and full rank, with no dominant diagonal. Along trajectories, its normalized singular values decay slowly, and about 108 of the 128 exceed 1% of the largest (Figure 9 ). No small rank m m m can therefore represent A t A_t A t exactly, which makes this model a test of how the Broyden variants degrade as m m m decreases.
Figure 9. Singular value spectrum of the DMF RNN Jacobian. Normalized singular values σ i / σ 1 \sigma_i/\sigma_1 σ i / σ 1 of A t A_t A t along trajectories (median and interquartile range over 32 independently sampled networks). The dashed line marks 1% of σ 1 \sigma_1 σ 1 .
Since the model has no leak term, the Broyden variants initialize the diagonal at γ = 0.1 \gamma= 0.1 γ = 0.1 . Both Broyden variants use a backtracking line search with c = 10 − 3 c = 10^{-3} c = 1 0 − 3 . We sweep m ∈ { 1 , 5 , 10 , … , 80 } m \in\{1,5,10,\ldots,80\} m ∈ { 1 , 5 , 10 , … , 80 } for Parallel Broyden and m ∈ { 1 , 5 , 10 , 15 , 20 } m \in\{1,5,10,15,20\} m ∈ { 1 , 5 , 10 , 15 , 20 } for Accelerated Parallel Broyden. For larger m m m , the Gram matrix of Accelerated Parallel Broyden becomes nearly singular, which degrades convergence. Newton uses damping 0.2, which prevents numerical overflow in float32, and all other methods use no damping.
Hierarchical Gibbs sampler details
We use a Gibbs sampler for a hierarchical normal model based on the eight schools problem, with a variable number of schools S S S to study scaling with state dimension. For each school s = 1 , … , S s = 1,\ldots,S s = 1 , … , S and student n = 1 , … , N n = 1,\ldots,N n = 1 , … , N , the model is
y s , n ∣ θ s , σ s 2 ∼ N ( θ s , σ s 2 ) , y_{s,n}\mid\theta_s,\sigma_s^2 \sim\mathcal{N}(\theta_s,\sigma_s^2), y s , n ∣ θ s , σ s 2 ∼ N ( θ s , σ s 2 ) ,
θ s ∣ μ , τ 2 ∼ N ( μ , τ 2 ) . \theta_s\mid\mu,\tau^2 \sim\mathcal{N}(\mu,\tau^2). θ s ∣ μ , τ 2 ∼ N ( μ , τ 2 ) .
We place conjugate priors on the global mean, global variance, and school-level variances:
μ ∣ τ 2 ∼ N ( μ 0 , τ 2 κ 0 ) , \mu\mid\tau^2 \sim\mathcal{N}\left(\mu_0,\frac{\tau^2}{\kappa_0}\right), μ ∣ τ 2 ∼ N ( μ 0 , κ 0 τ 2 ) ,
τ 2 ∼ InvGamma ( ν 0 2 , ν 0 τ 0 2 2 ) , \tau^2 \sim\operatorname{InvGamma}\left(\frac{\nu_0}{2},\frac{\nu_0\tau_0^2}{2}\right), τ 2 ∼ InvGamma ( 2 ν 0 , 2 ν 0 τ 0 2 ) ,
σ s 2 ∼ InvGamma ( α 0 2 , α 0 σ 0 2 2 ) . \sigma_s^2 \sim\operatorname{InvGamma}\left(\frac{\alpha_0}{2},\frac{\alpha_0\sigma_0^2}{2}\right). σ s 2 ∼ InvGamma ( 2 α 0 , 2 α 0 σ 0 2 ) .
The MCMC state at sweep t t t is
x t = ( θ 1 : S , t , σ 1 : S , t 2 , μ t , τ t 2 ) ∈ R 2 S + 2 . x_t = \left(\theta_{1:S,t},\sigma_{1:S,t}^2,\mu_t,\tau_t^2\right)\in\mathbb{R}^{2S+2}. x t = ( θ 1 : S , t , σ 1 : S , t 2 , μ t , τ t 2 ) ∈ R 2 S + 2 .
In the experiments, we set
N = 20 , μ 0 = 0 , κ 0 = 0.1 , ν 0 = 0.1 , τ 0 2 = 100 , α 0 = 0.1 , σ 0 2 = 10. N = 20,\quad\mu_0 = 0,\quad\kappa_0 = 0.1,\quad\nu_0 = 0.1,\quad\tau_0^2 = 100,\quad\alpha_0 = 0.1,\quad\sigma_0^2 = 10. N = 20 , μ 0 = 0 , κ 0 = 0.1 , ν 0 = 0.1 , τ 0 2 = 100 , α 0 = 0.1 , σ 0 2 = 10.
We generate synthetic school-level summaries by drawing
y ˉ s ∼ N ( 0 , 10 2 ) , σ ˉ s = ∣ η s ∣ + 5 , η s ∼ N ( 0 , 5 2 ) . \bar{y}_s \sim\mathcal{N}(0,10^2),\qquad\bar{\sigma}_s = |\eta_s| + 5,\qquad\eta_s \sim\mathcal{N}(0,5^2). y ˉ s ∼ N ( 0 , 1 0 2 ) , σ ˉ s = ∣ η s ∣ + 5 , η s ∼ N ( 0 , 5 2 ) .
Given these summaries, we generate observations by first sampling
y s , n r a w ∼ N ( y ˉ s , N σ ˉ s 2 ) , y_{s,n}^{\mathrm{raw}} \sim\mathcal{N}(\bar{y}_s,N\bar{\sigma}_s^2), y s , n raw ∼ N ( y ˉ s , N σ ˉ s 2 ) ,
then standardizing each school’s column to z s , n z_{s,n} z s , n and setting y s , n = y ˉ s + N σ ˉ s z s , n y_{s,n}=\bar{y}_s+\sqrt{N}\bar{\sigma}_s z_{s,n} y s , n = y ˉ s + N σ ˉ s z s , n . Each school’s sample mean is then exactly y ˉ s \bar{y}_s y ˉ s and its sample standard deviation N σ ˉ s \sqrt{N}\bar{\sigma}_s N σ ˉ s , so that its standard error is σ ˉ s \bar{\sigma}_s σ ˉ s .
Conditional updates. Each Gibbs sweep updates τ 2 \tau^2 τ 2 , then μ \mu μ , then θ 1 : S \theta_{1:S} θ 1 : S , then σ 1 : S 2 \sigma^2_{1:S} σ 1 : S 2 . Let
ν N = ν 0 + S + 1 , α N = α 0 + N . \nu_N = \nu_0 + S + 1,\qquad\alpha_N = \alpha_0 + N. ν N = ν 0 + S + 1 , α N = α 0 + N .
Given independent random variates fixed by the driver at sweep t t t , the updates are
τ N 2 = 1 ν N [ ν 0 τ 0 2 + κ 0 ( μ − μ 0 ) 2 + ∑ s = 1 S ( θ s − μ ) 2 ] , \tau_N^2 = \frac{1}{\nu_N}\left[\nu_0\tau_0^2+\kappa_0(\mu-\mu_0)^2+\sum_{s=1}^{S}(\theta_s-\mu)^2\right], τ N 2 = ν N 1 [ ν 0 τ 0 2 + κ 0 ( μ − μ 0 ) 2 + s = 1 ∑ S ( θ s − μ ) 2 ] ,
τ 2 = ν N τ N 2 2 ξ τ , ξ τ ∼ InvGamma ( ν N 2 , 1 ) , \tau^2 = \frac{\nu_N\tau_N^2}{2}\xi_\tau,\qquad\xi_\tau\sim\operatorname{InvGamma}\left(\frac{\nu_N}{2},1\right), τ 2 = 2 ν N τ N 2 ξ τ , ξ τ ∼ InvGamma ( 2 ν N , 1 ) ,
v μ = τ 2 κ 0 + S , μ ^ = κ 0 μ 0 + ∑ s = 1 S θ s κ 0 + S , v_\mu= \frac{\tau^2}{\kappa_0+S},\qquad\hat{\mu}=\frac{\kappa_0\mu_0+\sum_{s=1}^{S}\theta_s}{\kappa_0+S}, v μ = κ 0 + S τ 2 , μ ^ = κ 0 + S κ 0 μ 0 + ∑ s = 1 S θ s ,
μ = μ ^ + v μ ξ μ , ξ μ ∼ N ( 0 , 1 ) , \mu=\hat{\mu}+\sqrt{v_\mu}\xi_\mu,\qquad\xi_\mu\sim\mathcal{N}(0,1), μ = μ ^ + v μ ξ μ , ξ μ ∼ N ( 0 , 1 ) ,
v θ s = ( N σ s 2 + 1 τ 2 ) − 1 , θ ^ s = v θ s ( ∑ n = 1 N y s , n σ s 2 + μ τ 2 ) , v_{\theta_s}=\left(\frac{N}{\sigma_s^2}+\frac{1}{\tau^2}\right)^{-1},\qquad\hat{\theta}_s=v_{\theta_s}\left(\frac{\sum_{n=1}^{N}y_{s,n}}{\sigma_s^2}+\frac{\mu}{\tau^2}\right), v θ s = ( σ s 2 N + τ 2 1 ) − 1 , θ ^ s = v θ s ( σ s 2 ∑ n = 1 N y s , n + τ 2 μ ) ,
θ s = θ ^ s + v θ s ξ θ s , ξ θ s ∼ N ( 0 , 1 ) , \theta_s=\hat{\theta}_s+\sqrt{v_{\theta_s}}\xi_{\theta_s},\qquad\xi_{\theta_s}\sim\mathcal{N}(0,1), θ s = θ ^ s + v θ s ξ θ s , ξ θ s ∼ N ( 0 , 1 ) ,
σ N , s 2 = 1 α N [ α 0 σ 0 2 + ∑ n = 1 N ( y s , n − θ s ) 2 ] , \sigma_{N,s}^2=\frac{1}{\alpha_N}\left[\alpha_0\sigma_0^2+\sum_{n=1}^{N}(y_{s,n}-\theta_s)^2\right], σ N , s 2 = α N 1 [ α 0 σ 0 2 + n = 1 ∑ N ( y s , n − θ s ) 2 ] ,
σ s 2 = α N σ N , s 2 2 ξ σ s , ξ σ s ∼ InvGamma ( α N 2 , 1 ) . \sigma_s^2=\frac{\alpha_N\sigma_{N,s}^2}{2}\xi_{\sigma_s},\qquad\xi_{\sigma_s}\sim\operatorname{InvGamma}\left(\frac{\alpha_N}{2},1\right). σ s 2 = 2 α N σ N , s 2 ξ σ s , ξ σ s ∼ InvGamma ( 2 α N , 1 ) .
Fixing the random variates
ξ t = ( ξ θ , 1 : S , t , ξ σ , 1 : S , t , ξ μ , t , ξ τ , t ) \xi_t=(\xi_{\theta,1:S,t},\xi_{\sigma,1:S,t},\xi_{\mu,t},\xi_{\tau,t}) ξ t = ( ξ θ , 1 : S , t , ξ σ , 1 : S , t , ξ μ , t , ξ τ , t )
for every sweep turns the Gibbs sampler into a deterministic input-driven state-space model,
x t + 1 = f t ( x t ; ξ t ) . x_{t+1}=f_t(x_t;\xi_t). x t + 1 = f t ( x t ; ξ t ) .
Why the Jacobian is approximately low rank. The hierarchical structure induces strong cross-school coupling through the two global variables μ \mu μ and τ 2 \tau^2 τ 2 . The school-level variables affect the global updates through sums such as ∑ s θ s \sum_s\theta_s ∑ s θ s and ∑ s ( θ s − μ ) 2 \sum_s(\theta_s-\mu)^2 ∑ s ( θ s − μ ) 2 , while the updated global variables are then broadcast back to all school-level updates through the conditional means and variances of θ s \theta_s θ s . Thus, the dominant off-diagonal interactions are mediated by a small number of global degrees of freedom. This motivates a rank-2 approximation corresponding to the two global variables ( μ , τ 2 ) (\mu,\tau^2) ( μ , τ 2 ) (Figure 10 ).
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.
At the same time, the diagonal entries of the transition Jacobian are small, because Gibbs updates resample each coordinate from its conditional distribution. Each updated coordinate depends primarily on the other variables that determine its conditional distribution, rather than on its own previous value. For this reason, both Broyden variants initialize the diagonal term to zero (γ = 0 \gamma=0 γ = 0 ) and use rank m = 2 m=2 m = 2 . Since the approximation is then purely low rank, products of rank-m m m blocks remain rank at most m m m , and no rank compression is required.
Experimental setup. We use S ∈ { 10 , 50 , 100 , 200 } S \in\{10, 50, 100, 200\} S ∈ { 10 , 50 , 100 , 200 } , so that D = 2 S + 2 D = 2S + 2 D = 2 S + 2 ranges from 22 to 402, and T ∈ { 10 3 , 10 4 , 5 ⋅ 10 4 , 10 5 } T \in\{10^{3}, 10^{4}, 5 \cdot10^{4}, 10^{5}\} T ∈ { 1 0 3 , 1 0 4 , 5 ⋅ 1 0 4 , 1 0 5 } . Each setting uses 32 chains. Each chain has its own synthetic dataset and its own random variates ξ 1 : T \xi_{1:T} ξ 1 : T . Its initial state is drawn from the prior and followed by one Gibbs sweep, and the initial guess repeats this state at every time step. All methods use a maximum of 1000 iterations, computations in float32 with highest-precision matrix multiplications, and the stopping criterion
∥ r ( x 1 : T ) ∥ 2 T D < 10 − 3 , \frac{\lVert r(x_{1:T}) \rVert_{2}}{\sqrt{TD}} < 10^{-3}, T D ∥ r ( x 1 : T ) ∥ 2 < 1 0 − 3 ,
a tolerance that is small relative to the scale of the Gibbs state variables. We report medians and interquartile ranges over all chains, with non-converged chains counted at the 1000-iteration cap and at their actual runtime. Newton uses the full Jacobian computed by reverse-mode automatic differentiation, and diagonal quasi-Newton extracts its diagonal from it. Newton and diagonal quasi-Newton use no damping, Parallel Broyden uses damping 0.3, and Accelerated Parallel Broyden uses damping 0.1. Accelerated Parallel Broyden also uses a backtracking line search with sufficient-decrease constant c = 10 − 3 c = 10^{-3} c = 1 0 − 3 and a Gram regularization ε = 10 − 6 \varepsilon= 10^{-6} ε = 1 0 − 6 , while Parallel Broyden uses no line search. After each iteration, both Broyden variants clip the variances σ 2 \sigma^{2} σ 2 and τ 2 \tau^{2} τ 2 to at least 10 − 6 10^{-6} 1 0 − 6 to keep the iterates in the support of the model. For S = 200 S = 200 S = 200 and T ≥ 5 ⋅ 10 4 T \ge5 \cdot10^{4} T ≥ 5 ⋅ 1 0 4 , Newton runs out of memory. All runtimes are measured on a single NVIDIA H100 GPU.
Stochastic diagonal estimation. Replacing the exact diagonal of A t A_t A t with a Hutchinson estimate, as in the diffusion experiment, breaks diagonal quasi-Newton on this benchmark (Table 9 ). With 1 or 8 Rademacher probes per step, it fails on every chain. With 64 probes, some chains converge at T = 10 3 T = 10^{3} T = 1 0 3 , but only after 963 to 999 iterations, close to the worst-case bound of T T T . By comparison, at T = 10 3 T = 10^{3} T = 1 0 3 the median iteration count is 68 to 136 with the exact diagonal and 21 to 32 for Accelerated Parallel Broyden. This failure is expected from the structure of A t A_t A t : since its diagonal entries are small, the off-diagonal entries carry most of its Frobenius norm, and the noise of the estimate is large relative to the diagonal it estimates.
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.
Diffusion experiment
Structure of the local dynamics Jacobian
Recall that the local dynamics Jacobian of the DDIM update is
A ℓ ( x ℓ − 1 ) = c x ( t ) I + c ϵ ( t ) ∂ ϵ θ ∂ x ( x ℓ − 1 , t ) , t = T − ℓ + 1 , (23) A_{\ell}(x_{\ell-1}) = c_x(t)I + c_{\epsilon}(t)\frac{\partial\epsilon_{\theta}}{\partial x}(x_{\ell-1},t), \qquad t = T - \ell+ 1, \tag*{(23)} A ℓ ( x ℓ − 1 ) = c x ( t ) I + c ϵ ( t ) ∂ x ∂ ϵ θ ( x ℓ − 1 , t ) , t = T − ℓ + 1 , (23)
a 4096 × 4096 4096 \times4096 4096 × 4096 matrix. To quantify how well a diagonal approximation captures it, we form A ℓ A_\ell A ℓ exactly by automatic differentiation through the DiT denoiser along the DDIM sampling trajectory. We do this for ℓ ∈ { 1 , 10 , 25 , 40 , 50 } \ell\in\{1, 10, 25, 40, 50\} ℓ ∈ { 1 , 10 , 25 , 40 , 50 } and three class-conditional images, using the same pretrained model, guidance scale and T = 50 T = 50 T = 50 as in the main experiments. Figure 11 reports the relative off-diagonal mass ∥ A ℓ − diag ( A ℓ ) ∥ / ∥ A ℓ ∥ \lVert A_\ell- \operatorname{diag}(A_\ell)\rVert/ \lVert A_\ell\rVert ∥ A ℓ − diag ( A ℓ )∥ / ∥ A ℓ ∥ in Frobenius and spectral norm.
Figure 11. Off-diagonal mass of the DDIM local dynamics Jacobian. Relative norm of A ℓ − diag ( A ℓ ) A_\ell- \operatorname{diag}(A_\ell) A ℓ − diag ( A ℓ ) along the sampling trajectory, in Frobenius and spectral norm (median and range over 3 images).
In Frobenius norm, A ℓ A_\ell A ℓ is close to diagonal throughout sampling. Its off-diagonal part accounts for under 1% of ∥ A ℓ ∥ F \lVert A_\ell\rVert_F ∥ A ℓ ∥ F early in sampling and at most about 5% in the median at later steps, with one image reaching 14% at the final step. The spectral ratio is larger: it rises after mid-sampling and peaks at about 0.5 around ℓ = 40 \ell= 40 ℓ = 40 . This indicates that the off-diagonal coupling is small in total but concentrated in a few directions of the state, where the diagonal approximation is inaccurate. Such an error mainly slows the corresponding modes of the iteration, which is consistent with diagonal quasi-Newton requiring only slightly more iterations than Parallel Broyden in Figure 3 . The small Frobenius ratio also explains why a single-probe Hutchinson estimate is accurate on this benchmark. For a Rademacher probe z z z , the error of the estimate z ⊙ ( A ℓ z ) z \odot(A_\ell z) z ⊙ ( A ℓ z ) comes only from the off-diagonal entries of A ℓ A_\ell A ℓ , and its root-mean-square relative error is ∥ A ℓ − diag ( A ℓ ) ∥ F / ∥ diag ( A ℓ ) ∥ F \lVert A_\ell- \operatorname{diag}(A_\ell)\rVert_F / \lVert\operatorname{diag}(A_\ell)\rVert_F ∥ A ℓ − diag ( A ℓ ) ∥ F / ∥ diag ( A ℓ ) ∥ F , which nearly coincides with the Frobenius curve in Figure 11 since the diagonal dominates.
Hyperparameter setting for ParaTAA
ParaTAA [27 ] parallelizes diffusion sampling by rewriting the denoising trajectory as a triangular nonlinear system and applying triangular Anderson acceleration. The method has three relevant hyperparameters: the window size w w w , the order k k k of the equivalent triangular system, and the history size m m m . In our DDIM-50 experiment, we follow ParaTAA and set the window size equal to the number of sampling steps, w = T = 50 w = T = 50 w = T = 50 , so the full trajectory is solved in a single window. The order k k k controls how many future timesteps are used in each triangular update, while m m m controls the amount of Anderson history used to build the inverse multisecond approximation.
Tang et al. [27 ] treat k k k and m m m as empirical hyperparameters and report two trends relevant to our sweep: k k k should be tuned because it controls a stability–information-propagation tradeoff, and the history size is typically kept small because additional history does not necessarily improve convergence and can hurt performance. We therefore perform a small grid search over k k k and m m m in our DDIM-50 setting.
Figure 12 shows that both hyperparameters matter in our setting. Small orders propagate information slowly: at k = 2 k = 2 k = 2 , the mean iteration count is 44.7 for m = 2 m = 2 m = 2 and 74.3 for m = 4 m = 4 m = 4 . For m = 2 m = 2 m = 2 , performance improves rapidly with k k k and is nearly flat for 6 ≤ k ≤ 15 6 \leq k \leq15 6 ≤ k ≤ 15 (mean 25.0–26.2 iterations and mean runtime 3.2–3.4 s), before degrading slightly for larger orders (mean 29.2–30.1 iterations for k ≥ 35 k \geq35 k ≥ 35 ), consistent with the stability vs. information-propagation tradeoff described by Tang et al. [27 ] . Increasing the history size to m = 4 m = 4 m = 4 is worse than m = 2 m = 2 m = 2 at every order. Based on this sweep, we use m = 2 m = 2 m = 2 and k = 10 k = 10 k = 10 for the ParaTAA baseline, which attains the lowest mean iteration count (25.0). With k = 8 k = 8 k = 8 , it is nearly as good on average (25.6) but has a much worse worst case (62 vs. 41 iterations).
Figure 12. ParaTAA hyperparameter search. We vary the nonlinear system order k k k and history size m m m for DDIM-50 with window size w = T = 50 w = T = 50 w = T = 50 . Points denote means over 32 images, and shaded regions denote ± \pm ± one standard deviation. Consistent with ParaTAA’s hyperparameter analysis, small history sizes are sufficient: m = 2 m = 2 m = 2 requires fewer iterations than m = 4 m = 4 m = 4 at every order.
Hyperparameter setting for Picard iteration
ParaDiGMS [26 ] parallelizes diffusion sampling with Picard iteration. In our notation, this corresponds to a fixed-point parallel trajectory update, or equivalently to using the identity local approximation A ℓ = I D A_\ell= I_D A ℓ = I D . Unlike Parallel Broyden, ParaDiGMS does not build secant-based Jacobian approximations. It repeatedly refines the full denoising trajectory using parallel denoiser evaluations.
The main hyperparameter is the sliding-window size w w w , which controls how many timesteps are updated in parallel. The original method uses this window to manage memory when the full trajectory is too large to evaluate at once. In our DDIM-50 experiments, we set w = T = 50 w = T = 50 w = T = 50 , so the full trajectory is updated in a single window. For SDE samplers, ParaDiGMS samples the noise up front and treats it as part of a deterministic input-driven trajectory. Since we evaluate DDIM here, no additional noise is injected after the initial latent is fixed.
Setting for diagonal quasi-Newton
Diagonal quasi-Newton estimates the diagonal of each A ℓ A_\ell A ℓ with the Hutchinson estimator using a single Rademacher probe z z z , diag ( A ℓ ) ≈ z ⊙ ( A ℓ z ) \operatorname{diag}(A_\ell) \approx z \odot(A_\ell z) diag ( A ℓ ) ≈ z ⊙ ( A ℓ z ) , which requires one Jacobian–vector product through the denoiser per time step and iteration. Forming the exact diagonal would require the full 4096 × \times × 4096 Jacobian. As shown in Appendix § 14 .§ 1 , a single probe is accurate on this benchmark because A ℓ A_\ell A ℓ is close to diagonal in Frobenius norm.
Hyperparameter setting for Parallel Broyden
Parallel Broyden has two main hyperparameters in the DDIM experiment: the maximum DPLR rank m m m , which controls the number of stored Broyden corrections, and the diagonal scaling γ \gamma γ in the initialization γ I D \gamma I_D γ I D . We tune these hyperparameters with a small grid search on the DDIM-50 benchmark, using the same 32 images as in the main evaluation. We use the same selected hyperparameters for Accelerated Parallel Broyden.
Figure 13 shows that the best performance is obtained with γ = 1.0 \gamma= 1.0 γ = 1.0 . For each rank, increasing γ \gamma γ decreases the mean iteration count and runtime, suggesting that the identity-scaled diagonal term already captures an important part of the DDIM local dynamics. Increasing the rank from m = 2 m = 2 m = 2 to m = 4 m = 4 m = 4 or m = 6 m = 6 m = 6 does not meaningfully improve the best mean iteration count. Based on this sweep, we use γ = 1.0 \gamma= 1.0 γ = 1.0 and m = 2 m = 2 m = 2 for both Parallel Broyden and Accelerated Parallel Broyden in the DDIM experiments.
Figure 13. Parallel Broyden hyperparameter search. We vary the diagonal scaling γ \gamma γ in the initialization γ I D \gamma I_D γ I D and the maximum DPLR rank m m m on the DDIM-50 benchmark. Points denote means over 32 images, and shaded regions denote ± \pm ± one standard deviation. Larger diagonal scaling improves convergence across all tested ranks, while increasing the rank beyond m = 2 m = 2 m = 2 gives no improvement.
Both Broyden variants use no damping and no line search. The low-rank products formed during the parallel scan are compressed with the randomized compression described in the main text. The rank-revealing variant used in the other benchmarks is not needed here. Accelerated Parallel Broyden uses a Gram regularization ε = 10 − 10 \varepsilon= 10^{-10} ε = 1 0 − 10 .
Image quality and stopping criterion
All DDIM experiments in this work are run on a single NVIDIA H100 GPU in float32. Since the trajectory is short (T = 50 T = 50 T = 50 ), default matrix-multiplication precision suffices, unlike in the other benchmarks. The only exception is ParaTAA, which accumulates and solves its Anderson Gram system in float64 with Tikhonov regularization λ = 10 − 3 \lambda= 10^{-3} λ = 1 0 − 3 , following the reference implementation [27 ] . Since parallel diffusion samplers solve the sampling trajectory only approximately, we need both a stopping criterion and a way to check that the resulting images match the sequential ones.
Image-quality metric. We compare each parallel sample to the corresponding sequential DDIM sample using LPIPS, or Learned Perceptual Image Patch Similarity [46 ] . LPIPS measures perceptual distance by comparing deep feature activations between two images, and is often preferred to pixelwise metrics such as mean squared error because it correlates better with human perceptual judgments. Lower LPIPS values indicate greater perceptual similarity, with 0 corresponding to identical images in the learned feature space. All LPIPS values are computed over the same 32 images used for the runtime and iteration-count experiments.
Stopping criterion. For all methods we use the same criterion: we stop the trajectory solver when ∥ r ( x 1 : T ) ∥ 2 / 2 < 0.1 \lVert r(x_{1:T})\rVert_2/2 < 0.1 ∥ r ( x 1 : T ) ∥ 2 /2 < 0.1 , where r r r is the single-step DDIM residual in latent space, with a maximum of 100 iterations. Using a common criterion makes iteration counts directly comparable across methods. All hyperparameter sweeps use the same criterion.
We chose this threshold with a tolerance study: each method was run for a fixed 50 iterations, and we recorded the residual and the LPIPS distance to the sequential sample along the trajectory. At a tolerance of 0.1, the image quality of all methods is essentially at convergence: for every image, the solver has already achieved at least 96% of the total LPIPS reduction observed between iteration 3 and iteration 50, and for 31 or 32 of the 32 images per method more than 99%. Consistent with this, we could not visually distinguish samples obtained at this tolerance from fully converged ones, and tightening the tolerance further yields only marginal gains while adding iterations. A looser tolerance of 1 stops some trajectories too early: only about 22 to 28 of the 32 images per method have achieved more than 99% of their LPIPS reduction. The stricter tolerance costs a median of 2 additional iterations for the Broyden, Picard and quasi-Newton methods and 5 for ParaTAA. Using float64 for ParaTAA’s Gram system leaves its median iteration count unchanged and mainly shortens one slow case (52 → 41 52 \to41 52 → 41 iterations for the sea turtle image).
This choice follows the principle noted by ParaTAA [27 ] : generated images can appear visually satisfactory before the nonlinear residual reaches a strict numerical tolerance, so it is unnecessary to solve the full trajectory to machine precision.
Resulting image quality. Table 10 reports the LPIPS distances between the parallel samples, obtained with this stopping criterion, and the corresponding sequential DDIM samples. All methods achieve very small LPIPS values (medians of about 0.003), indicating that the images are perceptually very close to the sequential rollout and, in practice, indistinguishable by visual inspection. The two larger values (up to about 0.07) occur for the same images under every method and persist after full convergence. We report medians and interquartile ranges for LPIPS, unlike the mean-based Figure 3 , Figure 12 and Figure 13 , because these two images inflate both the mean and the standard deviation: for every method, the standard deviation is about twice the mean, so a mean ± \pm ± standard deviation summary would not describe the typical image.
Table 10. LPIPS distance between each parallel sample and the corresponding sequential DDIM reference over 32 images. Lower is better.
Runtime decomposition
The runtime ratio between a baseline and a Broyden variant factors into an iteration ratio, which reflects the quality of the Jacobian approximation, and a per-iteration cost ratio, which reflects the cost of obtaining it (Table 11 ). The DPLR blocks always need fewer iterations than diagonal quasi-Newton, from 1.1× fewer on DiT to 5.6× fewer on the Gibbs sampler. Most of the speedup, however, comes from avoiding automatic differentiation. On the MLP-RNN and the Gibbs sampler, diagonal quasi-Newton with the exact diagonal spends 91–99% of each iteration in automatic differentiation (Table 12 ). With Hutchinson’s estimator on DiT, it spends 69% in the Jacobian–vector product. The Broyden updates themselves are negligible when the transition is expensive. When it is cheap, as for the standard low-rank RNN, the low-rank scan dominates, and one Broyden iteration costs about 20× a diagonal quasi-Newton iteration.
Table 11: Decomposition of the runtime ratio. Runtime ratio = iteration ratio × \times × per-iteration cost ratio, baseline over Broyden variant (> 1 > 1 > 1 : the Broyden variant is faster). T = 10 5 T = 10^{5} T = 1 0 5 for the RNNs and the Gibbs sampler (D = 200 D = 200 D = 200 , with Δ t = 3 \Delta t = 3 Δ t = 3 for the low-rank MLP-RNN and Δ t = 0.5 \Delta t = 0.5 Δ 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.
Table 11.
Table 12: Wall-clock breakdown of one iteration (H100, float32, T = 10 5 T = 10^{5} T = 1 0 5 except DiT). Measured time per iteration, and share of each component: evaluations of the transition f f 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 U t U_t U t ), 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.
Table 12.