implementation

Matrix-free linear algebra for the implicit solver: GMRES for the Newton step and the adjoint, Lanczos for the stability test, conjugate gradients and stochastic Lanczos quadrature for the Laplace approximation. With it a query’s cost grows with the number of Krylov steps, not with the number of free coordinates, which is what generating an image (hundreds of free coordinates) needs.

Sources: code: krylov.jl, implicit.jl (_newton_system, _adjoint_solve), answers.jl (_laplace_marginal); Saad & Schultz, GMRES, SIAM J. Sci. Stat. Comput. 1986; Knoll & Keyes, Jacobian-free Newton–Krylov methods, J. Comput. Phys. 2004; Ubaru, Chen & Saad, Fast estimation of tr(f(A)) via stochastic Lanczos quadrature, SIAM J. Matrix Anal. Appl. 2017

Bibliography: Saad & Schultz 1986 · Knoll & Keyes 2004 · Ubaru et al. 2017

Theory: Implicit Diffusion Learners · Backpropagation through Implicit Inference · Open Problems in Implicit Diffusion Learning

1. Where the solver meets

usedense (DenseSolve)matrix-free (KrylovSolve)
Newton step LU of the blockrestarted GMRES on (prior_jvp)
adjoint the same LU, transposedGMRES on (prior_vjp)
stability, Cholesky testsmallest Ritz value of Lanczos on the symmetric part
Laplace covariance on coordinates inverse of the whole blockone conjugate-gradient solve per coordinate in
(mixture weights)from the inversestochastic Lanczos quadrature

The precision diagonal is added inside each product. For an energy network or a closed-form mixture with a common noise time across coordinates, the field is a gradient, so is symmetric and the symmetric part costs one product, not two. Different block times can break this symmetry when the coordinates interact (energy_network).

2. Design decisions

  • One option, threaded through. linsolve is a keyword of implicit_infer, implicit_pullback, laplace_belief, implicit_mixture (and so implicit_roots), and a field of ImplicitProx. The default stays DenseSolve(): exact, and faster while few coordinates are free.
  • No Krylov package. GMRES with Givens rotations, CG and Lanczos with full reorthogonalisation are about 150 lines; a dependency would have been heavier than the code.
  • Deterministic. Lanczos starts and Hutchinson probes come from Xoshiro(seed), so the same query gives the same answer, which the implicit function theorem relies on.
  • Exact at small sizes. With at most lanczos free coordinates the Lanczos space is the whole space and the stability test is exact; with at most probes the log-determinant uses unit vectors with full Lanczos depth (n steps), overriding a smaller lanczos setting, and is exact too. Unit probes alone remove trace-sampling error, not truncation error. The tests check both against dense factorisations.
  • JVPs without forward mode. Zygote has no forward mode, and a JVP through reverse mode costs one pullback per coordinate. So reverse-only backends take one central difference along the direction (two batched forward passes, about relative error), while ForwardDiff and Enzyme use DI.pushforward. The adjoint uses VJPs only, so gradients stay exact either way.

3. What is approximate

  • The smallest Ritz value approaches from above: a point whose symmetric Jacobian has a small negative eigenvalue can be reported stable when there are more free coordinates than Lanczos steps. Newton is then tried where the dense solver would have descended; the residual line search keeps that safe, but the stable flag is an estimate.
  • The log-determinant with Rademacher probes has a standard error of roughly ; the mixture weights inherit it.
  • GMRES stops at rtol (default ) or maxiters; the adjoint warns when it stops short.

4. Measured

The MNIST shape of MNIST in Both Directions: an MLP , 64 nodes batched by noise level, Zygote, CPU, the 10 label coordinates clamped and the 784 image coordinates free (with a unit anchor, since the network is untrained):

time
one dense block of 33 s
implicit_infer with KrylovSolve() (2 Newton iterations, converged, stable)1.1 s
implicit_pullback with KrylovSolve()0.24 s
laplace_belief on 10 coordinates0.78 s
one prior_jvp / one prior_vjp3.2 ms / 5.7 ms

The Krylov answer agrees with the dense one to (relative).

Related: implicit, backends, implicit_factor

LP-018 exact branch depth (2026-10-29)

Unit-vector probes remove sampling error but cannot remove Lanczos truncation. The exact branch (n <= probes) now takes full depth n even if lanczos was smaller; stochastic branches keep the requested depth. Evidence: test/lp018.jl, “LP-018.12 exact unit-vector logdet uses full depth”, with S = [2 1; 1 2], lanczos = 1, probes = 2: the reference is log(3), from the independent determinant, rather than 2log(2).