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. 2017Bibliography: 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
| use | dense (DenseSolve) | matrix-free (KrylovSolve) |
|---|---|---|
| Newton step | LU of the block | restarted GMRES on (prior_jvp) |
| adjoint | the same LU, transposed | GMRES on (prior_vjp) |
| stability, | Cholesky test | smallest Ritz value of Lanczos on the symmetric part |
| Laplace covariance on coordinates | inverse of the whole block | one conjugate-gradient solve per coordinate in |
| (mixture weights) | from the inverse | stochastic 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.
linsolveis a keyword ofimplicit_infer,implicit_pullback,laplace_belief,implicit_mixture(and soimplicit_roots), and a field ofImplicitProx. The default staysDenseSolve(): 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
lanczosfree coordinates the Lanczos space is the whole space and the stability test is exact; with at mostprobesthe log-determinant uses unit vectors with full Lanczos depth (nsteps), overriding a smallerlanczossetting, 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
stableflag 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 ) ormaxiters; 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 coordinates | 0.78 s |
one prior_jvp / one prior_vjp | 3.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).