# Polynomial Speedup in Diffusion Models with the Multilevel Euler-Maruyama Method

arXiv: https://arxiv.org/abs/2603.24594 · HTML: https://mlsanity.com/paper/2603.24594/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models.
- Builds on 23 of its 27 references that are in the map.
- First posted on arXiv 25 Mar 2026.

## Placed in

- Diffusion models / [Diffusion foundations and sampling](https://mlsanity.com/diffusion/diffusion-foundations-and-sampling/)

## Builds on (most cited first, 23 of 23)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [High-Resolution Image Synthesis with Latent Diffusion Models](https://mlsanity.com/paper/2112.10752/) (2021)
- [Denoising Diffusion Implicit Models](https://mlsanity.com/paper/2010.02502/) (2020)
- [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020)
- [Deep Unsupervised Learning using Nonequilibrium Thermodynamics](https://mlsanity.com/paper/1503.03585/) (2015)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Improved Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2102.09672/) (2021)
- [Flow Straight and Fast: Learning to Generate and Transfer Data with Rectified Flow](https://mlsanity.com/paper/2209.03003/) (2022)
- [Deep Learning Face Attributes in the Wild](https://mlsanity.com/paper/1411.7766/) (2014)
- [Training Compute-Optimal Large Language Models](https://mlsanity.com/paper/2203.15556/) (2022)
- [DPM-Solver: A Fast ODE Solver for Diffusion Probabilistic Model Sampling in Around 10 Steps](https://mlsanity.com/paper/2206.00927/) (2022)
- [Consistency Models](https://mlsanity.com/paper/2303.01469/) (2023)
- [DPM-Solver++: Fast Solver for Guided Sampling of Diffusion Probabilistic Models](https://mlsanity.com/paper/2211.01095/) (2022)
- [Adversarial Diffusion Distillation](https://mlsanity.com/paper/2311.17042/) (2023)
- [On Distillation of Guided Diffusion Models](https://mlsanity.com/paper/2210.03142/) (2022)
- [Scaling Laws for Autoregressive Generative Modeling](https://mlsanity.com/paper/2010.14701/) (2020)
- [Explaining Neural Scaling Laws](https://mlsanity.com/paper/2102.06701/) (2021)
- [The Quantization Model of Neural Scaling](https://mlsanity.com/paper/2303.13506/) (2023)
- [A Dynamical Model of Neural Scaling Laws](https://mlsanity.com/paper/2402.01092/) (2024)
- [Gradients without Backpropagation](https://mlsanity.com/paper/2202.08587/) (2022)
- [Two for One: Diffusion Models and Force Fields for Coarse-Grained Molecular Dynamics](https://mlsanity.com/paper/2302.00600/) (2023)
- [Theory of Scaling Laws for In-Context Regression: Depth, Width, Context and Time](https://mlsanity.com/paper/2510.01098/) (2025)
- [Deep Learning as a Convex Paradigm of Computation: Minimizing Circuit Size with ResNets](https://mlsanity.com/paper/2511.20888/) (2025)

## Built on by (most cited first, 1 of 1)

- [Convex Optimization Is Free When Accuracy Is Expensive](https://mlsanity.com/paper/2609.35418/) (2026)

## Abstract (arXiv)

We introduce the Multilevel Euler-Maruyama (ML-EM) method compute solutions of SDEs and ODEs using a range of approximators f1,dots,fk to the drift f with increasing accuracy and computational cost, only requiring a few evaluations of the most accurate fk and many evaluations of the less costly f1,dots,fk-1. If the drift lies in the so-called Harder than Monte Carlo (HTMC) regime, i.e. it requires ε-γ compute to be ε-approximated for some γ>2, then ML-EM ε-approximates the solution of the SDE with ε-γ compute, improving over the traditional EM rate of ε-γ-1. In other terms it allows us to solve the SDE at the same cost as a single evaluation of the drift. In the context of diffusion models, the different levels f1,dots,fk are obtained by training UNets of increasing sizes, and ML-EM allows us to perform sampling with the equivalent of a single evaluation of the largest UNet. Our numerical experiments confirm our theory: we obtain up to fourfold speedups for image generation on the CelebA dataset downscaled to 64x64, where we measure a γ≈2.5. Given that this is a polynomial speedup, we expect even stronger speedups in practical applications which involve orders of magnitude larger networks.