Krylov Exponential Samplers for Diffusion Models on Irregular Domains

Diffusion models, which generate data by starting from random noise and running a learned denoising process in many small steps, are slow because each step calls a large neural network. For images, a known fix is to split every step into two parts: a simple linear part that pulls the data toward zero, which is solved exactly with an exponential, and the neural part, which is approximated. The solver built on this split is called DEIS (Fast Sampling of Diffusion Models with Exponential Integrator). It cuts sampling from hundreds of steps to 10–20 with no retraining. The trick is cheap only because the linear part treats every pixel the same way, so its exponential is a single number.

Many structured data types call for a linear part that couples coordinates. Examples are signals on meshes, flows on the edges of a network, and fields on simplicial complexes (higher-order graphs made of vertices, edges, and triangles). A physically natural forward process for such data is heat diffusion governed by the domain's Laplacian, a matrix that encodes which nodes are neighbours. Here the exact exponential becomes a full matrix exponential $\exp(-tL)$. Computing it densely costs $O(N^3)$. Using only the top eigenvectors, as Continuous Simplicial Neural Networks does, discards high frequencies and still needs an eigendecomposition for every new mesh. Approximating it poorly makes the sampler unstable, because large Laplacian eigenvalues make the dynamics stiff (they contain very fast modes that force explicit solvers to take tiny steps). This note proposes a sampler that recovers DEIS-level step counts for these coupled-drift diffusion models. It never forms or diagonalizes the matrix. Instead it computes only the needed matrix-function-times-vector products with adaptive rational Krylov methods, with each product's accuracy budgeted against the sampler's own step error.

Core Claim

For diffusion models whose forward process includes a Laplacian drift on an irregular domain, we claim that an exponential multistep sampler can match, at 10–20 network evaluations, the sample quality of the same sampler run with exact (dense eigendecomposition) matrix functions. It computes every matrix function through a rational Krylov subspace whose stopping tolerance is tied to the local truncation error of the step. Its per-step overhead should stay a small constant multiple of one network evaluation as the domain grows from $10^3$ to around $10^6$ nodes and as the graph changes from sample to sample.

We expect two failure patterns in the alternatives. Solvers that treat the Laplacian drift as part of the unknown nonlinear term should need several times more network evaluations to reach the same quality. Truncated-eigenvector approximations should show a measurable bias in high-frequency content.

What is new relative to DEIS is the coupled, non-scalar operator. What is new relative to the rational Krylov literature (Adaptive rational Krylov methods for exponential Runge-Kutta integrators) is its use inside a learned generative sampler, where the "nonlinear term" is a neural network and the right accuracy target is sample quality, not PDE residual.

The Mechanism

Take a forward process $dx = -\beta(t) L x\,dt - \alpha(t) x\,dt + \sigma(t)\,dW$. Here $x \in \mathbb{R}^N$ is the signal on the domain, $L$ is the symmetric positive semidefinite graph or Hodge Laplacian, $\beta,\alpha,\sigma$ are scalar schedules, and $W$ is Brownian motion. The marginal covariance $\Sigma_t$ is then a function of $L$. So is the noise-prediction reparameterization of the score (the network $\epsilon_\theta$ predicts the whitened noise $\Sigma_t^{-1/2}(x_t - \text{mean})$). The deterministic probability-flow ODE, which is the noise-free sampling path, therefore has the form

$$\frac{dx_t}{dt} = F_t(L)\,x_t + G_t(L)\,\epsilon_\theta(x_t,t).$$

In this equation $F_t$ and $G_t$ are known scalar functions applied to $L$ through its spectrum. Because all these matrix functions commute, variation of constants gives an exact one-step map from time $t$ to $s$:

$$x_s = \Phi_{s,t}(L)\,x_t + \int_t^s \Phi_{s,\tau}(L)\,G_\tau(L)\,\epsilon_\theta(x_\tau,\tau)\,d\tau.$$

Here $\Phi_{s,t}(\lambda) = \exp\!\big(\int_t^s F_u(\lambda)\,du\big)$ is the scalar propagator evaluated at eigenvalue $\lambda$.

As in DEIS, we replace $\epsilon_\theta$ inside the integral with a low-degree polynomial through the last $q$ network outputs $\epsilon_j$. The update then becomes $x_s = \Phi_{s,t}(L)x_t + \sum_{j=0}^{q-1} \psi_j(L)\,\epsilon_j$. Each $\psi_j(\lambda)$ is the integral of the propagator against a Lagrange basis polynomial, a generalized "phi-function".

Each step therefore needs $q+1$ products of the form $f(L)v$, and nothing else. We compute each by building a rational Krylov subspace from $v$ with poles chosen as in Bergermann and Stoll. This projects $L$ to an $m \times m$ matrix with $m$ expected below about 20. We then evaluate the scalar function $f$ exactly on that small matrix, using quadrature in $\tau$ over its eigenvalues. Because $L$ is symmetric positive semidefinite, each shifted system $(I + L/\xi)y = w$ is symmetric positive definite. Conjugate gradients with algebraic multigrid therefore apply. This sidesteps the non-symmetric preconditioning failure that Bergermann and Stoll flag.

The ingredient we think matters most is error balancing. We stop each Krylov solve when its a posteriori error estimate (their Theorem 4.3) falls below a fixed fraction of the step's estimated truncation error. Large early steps then use loose, cheap matrix functions, and small late steps use tight ones. Training needs the same machinery, since drawing $x_t$ requires $\Sigma_t^{1/2}$ applied to white noise, so the forward pass reuses the identical Krylov routine.

Research Program

The work has three parts.

The first part is a sampler library built on zju-pi/diff-sampler. It will provide exponential multistep samplers of orders one to three with pluggable matrix-function backends: dense eigendecomposition, top-$K$ eigenvectors, polynomial (Arnoldi/Lanczos) Krylov, and rational Krylov with and without error balancing.

The second part is a set of coupled-drift diffusion models trained on three kinds of data:

  • vertex coordinates of Shrec-16 meshes, where connectivity varies per sample and $L$ is the mesh Laplacian;
  • edge flows on the ocean-drifts simplicial complex, where $L$ is the first Hodge Laplacian;
  • a synthetic family of random geometric graphs with $N$ swept from $10^3$ to $10^6$, used for scaling.

The third part is a sanity-check configuration on CIFAR-10. It has two settings. With $L=0$, the sampler must reduce exactly to DEIS. With the image-grid Laplacian, a fast Fourier transform gives exact matrix functions, so we can measure Krylov error against ground truth for free.

The scientific questions run in order. First, does the coupled drift make the sampling ODE stiff enough that ignoring its structure costs network evaluations? Second, does rational Krylov keep the per-step cost flat as $N$ and $\beta$ grow, where polynomial Krylov does not? Third, does error balancing cut total matrix-function work without changing sample quality? Fourth, are higher orders stable at large steps, given that DEIS reports instability from high-degree extrapolation? We will cap the order at three and report where each order breaks. Training Stiff Neural Ordinary Differential Equations with Explicit Exponential Integration Methods is a precedent for the stability argument: it trained stiff neural ODEs by integrating the linear part exactly. It is also a constraint, because its integrating-factor Euler scheme is first-order only, and our order-two and order-three variants are meant to test whether that ceiling can be lifted without losing stability.

Baselines

The naive reference point is the probability-flow ODE solved with a standard explicit method that treats the whole right-hand side, Laplacian drift included, as a black box. We will use Euler and Heun, run at 10, 20, 50, 100, and 500 evaluations on the same trained network. This measures how much stiffness actually costs. The 500-step Heun solution with dense matrix functions also serves as the reference trajectory for solver-error measurements.

The strongest existing method on this question is DEIS itself, applied in the only way it can be: to an isotropic model on the same data, with no Laplacian drift. It is the strongest competitor because it answers the question "why use coupled drift at all?" If an ordinary isotropic diffusion model sampled with DEIS matches our model's sample quality at equal wall-clock time, the whole proposal is moot. On CIFAR-10, DEIS reports an FID of 4.17 at 10 network evaluations and 2.86 at 20 (Fast Sampling of Diffusion Models with Exponential Integrator). Our $L=0$ configuration must land within noise of these numbers to confirm the implementation. There is no reported result found on Lacuna for generative modeling on Shrec-16 meshes or ocean-drifts edge flows. Continuous Simplicial Neural Networks reports only regression and prediction numbers on those datasets (0.010 MSE and 0.550 accuracy), which are not comparable. Both the isotropic and coupled models will be trained with the same network, data, optimizer, and number of gradient steps, and each gets the same sampler-tuning budget: a grid over time schedules and orders.

Two further baselines isolate matrix-function accuracy. The first is the same exponential sampler with dense eigendecomposition, which gives oracle quality at $O(N^3)$ cost per graph. The second is the same sampler with top-$K$ eigenvectors in the style of COSIMO, with $K$ swept so its cost matches ours.

The ablation that isolates our key ingredient replaces rational Krylov with polynomial Lanczos at matched tolerance. A second ablation turns off error balancing, using a fixed tight tolerance at every step.

Beating the baselines means the following. At every step budget of 20 or fewer network evaluations, our sampler's distance to the reference trajectory and its sample-quality score must be within 5% of the dense oracle. Its wall-clock time must beat the dense oracle for $N$ above roughly $10^4$ and beat polynomial Krylov at large $\beta$ and $N$. Its overhead per step must stay below twice one network evaluation.

Why not just…?

Why not just eigendecompose each Laplacian once and reuse it for every step? For a single fixed graph of a few thousand nodes, this is a real threat and probably wins. The cost is paid once and each step becomes a dense product. Our claim is restricted to regimes where this fails: per-sample connectivity, as with Shrec-16 meshes, where the decomposition is paid for every sample, and $N$ beyond roughly $10^4$, where $O(N^3)$ time and $O(N^2)$ storage of the eigenvectors dominate. The scaling sweep will locate the crossover explicitly, and we will report it even if it sits higher than we hope.

Why not just use polynomial Krylov, which is simpler and needs no linear solves? Bergermann and Stoll show that polynomial Krylov iteration counts grow into the hundreds as stiffness and size increase, while rational Krylov stayed under 20 iterations. They also show the rational method paid off only beyond about $10^5$ nodes on Allen–Cahn (Adaptive rational Krylov methods for exponential Runge-Kutta integrators). In a sampler, early steps are long but late steps are short, and short steps make $hL$ mild, so polynomial Krylov may suffice for much of the trajectory. We therefore expect a hybrid might be best. The Lanczos ablation, reported per step as a function of step size times spectral radius, settles which backend each step should use.

Why not just distill the sampler into one or two steps? Consistency-style distillation works. DCFold: Efficient Protein Structure Generation with Single Forward Pass collapses AlphaFold3's refinement roughly 15-fold. The costs are a full retraining run, a success rate of 78.6% against the teacher's 82.9% on PoseBusters V2, and a mildly concentrated output distribution. Distillation also needs a teacher sampler to generate trajectories, and a fast accurate teacher is exactly what we build. Distillation and our sampler are complementary, but we will still run a one-step consistency student trained from our sampler's trajectories as an extra comparison. We will report its quality and diversity against 10- and 20-step exponential sampling at matched total compute, including training.

Why not just drop the coupled drift and use isotropic diffusion? This is the most serious objection, and the research file contains no evidence either way on whether Laplacian-shaped noise improves generation on meshes or complexes. The matched isotropic DEIS baseline is designed to answer it. If it matches, we will report that coupled-drift diffusion is not worth its cost on these data. The sampler would then remain useful only where the operator is fixed by the physics, such as stiff heat or transport models.

Decisive Checks

The first check is correctness. On CIFAR-10 with $L=0$ we must reproduce DEIS's reported FIDs. With the grid Laplacian, Krylov-computed updates must match FFT-exact updates to the requested tolerance.

The second check is stiffness. On Shrec-16 and ocean-drifts, we plot solver error against the reference trajectory, and a kernel maximum mean discrepancy between samples and held-out data, as functions of network evaluations. The black-box Heun sampler should need at least three times as many evaluations as the exponential sampler to reach the same error. If the gap is under 1.5 times, coupling stiffness is not the bottleneck, and the proposal's premise fails.

The third check is scaling. On the synthetic graph family, we record wall-clock time per sample and Krylov iterations per step as $N$ and $\beta$ grow. Rational Krylov iterations should stay flat, polynomial iterations should grow, and dense eigendecomposition should become infeasible.

The fourth check is spectral fidelity. We compare the power spectrum of generated signals in the Laplacian eigenbasis, computed offline on small graphs, against held-out data. Top-$K$ truncation should show a deficit at high frequencies that our sampler does not.

The fifth check is the error-balancing ablation. It should cut total linear-solve work substantially with no statistically detectable change in the sample-quality metric. If it does not, the adaptive tolerance adds complexity for nothing and will be dropped.