Sampling from high-dimensional probability distributions is a foundational challenge in machine learning, underpinning both Bayesian inference and modern generative modeling via diffusion models. Traditionally, this is accomplished by simulating stochastic differential equations (SDEs) like Langevin diffusion. However, when we discretize these continuous-time processes for computer simulation, we encounter a fundamental bottleneck: discretization bias.
To keep this bias small, standard algorithms must take tiny steps, leading to high computational costs that scale poorly with the dimension of the space. A powerful paradigm has emerged to break this bottleneck by combining two core insights: underdamped (momentum-assisted) dynamics and randomized midpoint discretization. Together, these techniques convert systematic discretization errors into harmless stochastic variance, enabling order-of-magnitude speedups.
The Bottleneck: Discretization Bias in SDEs
To understand why randomized methods work, we must first look at why standard deterministic discretization fails. Consider the standard overdamped Langevin diffusion, which moves a state $X_t$ along the gradient of a log-density $\nabla \log p(X_t)$ plus some Brownian motion noise:
$$dX_t = \nabla \log p(X_t) dt + \sqrt{2} dW_t$$
When we simulate this on a computer, we must discretize time into steps of size $h$. The standard Euler-Maruyama scheme approximates the continuous integral of the drift term over an interval $[t_k, t_{k+1}]$ by evaluating the gradient exclusively at the start of the interval:
$$\int_{t_k}^{t_{k+1}} \nabla \log p(X_t) dt \approx \nabla \log p(X_{t_k}) \cdot h$$
This approximation assumes the gradient remains constant across the step. In reality, the trajectory curves. This introduces a systematic, deterministic discretization bias at every step. To prevent these errors from compounding and destroying the accuracy of the target distribution, the step size $h$ must be kept exceedingly small, causing the algorithm to require a massive number of iterations as the dimension $d$ grows.
The Core Intuition: Converting Bias to Variance
The elegant solution to this problem is to replace the deterministic evaluation point with a random one. Instead of evaluating the gradient at the rigid boundary $t_k$, we evaluate it at a randomly selected intermediate time $\tau$ within the interval $[t_k, t_{k+1}]$.
Standard Euler-Maruyama:
[t_k]------------------------------------->[t_{k+1}]
^ (Always evaluate gradient here)
Randomized Midpoint Method:
[t_k]------------------[ \tau ]---------->[t_{k+1}]
^ (Evaluate at a randomly sampled midpoint)
This shift completely changes the mathematical nature of the discretization error. As originally proposed by Ruoqi Shen and Yin Tat Lee in The Randomized Midpoint Method for Log-Concave Sampling, evaluating the gradient at a randomized midpoint yields an unbiased estimator of the continuous trajectory's integral.
By randomizing the evaluation point, the systematic, directional bias of the step is eliminated and transformed into zero-mean stochastic variance.
Why is this a winning trade-off? In a deterministic optimization algorithm, adding variance can destabilize convergence. But Langevin dynamics is already a stochastic process driven by a massive amount of injected Brownian noise ($dW_t$). The tiny amount of extra variance introduced by the randomized midpoint evaluation is naturally absorbed by the system's inherent stochasticity. The systematic bias vanishes, while the extra variance is effectively "swallowed" by the Brownian motion.
As a result, the algorithm can take significantly larger step sizes without drifting away from the true target distribution. Ye He et al. provided a rigorous asymptotic analysis of this phenomenon in On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint Sampling Method, proving that the stationary distribution's bias scales at a much higher order relative to the step size than standard first-order methods.
Adding Momentum: Underdamped Dynamics
While randomized midpoints can be applied to standard Langevin diffusion, the mechanism becomes exceptionally powerful when paired with Underdamped Langevin Dynamics (ULD).
Underdamped dynamics introduces an auxiliary velocity variable $V_t$, mimicking physical systems with momentum:
$$dX_t = V_t dt$$ $$dV_t = -\gamma V_t dt + \nabla \log p(X_t) dt + \sqrt{2\gamma} dW_t$$
Crucially, notice that the stochastic Brownian noise $dW_t$ is now injected only into the velocity equation, not the position equation. Because the position $X_t$ is the integral of the velocity, the spatial trajectories become continuously differentiable and significantly smoother than the jagged, fractal-like paths of overdamped diffusion.
This smoothness is exactly what makes randomized midpoint discretization so effective. Because the continuous trajectory is smooth, a randomized midpoint provides an incredibly accurate approximation of the local path.
To optimize this process further, Zhengmian Hu et al. demonstrated in Optimal Underdamped Langevin MCMC Method that it is possible to achieve high-order accuracy using only a single gradient evaluation per iteration rather than two, doubling the execution speed by ensuring that the variance from the single evaluation remains smaller than the background Brownian motion.
Breaking the Dimension Barrier in Diffusion Models
The benefits of this paradigm extend directly to score-based generative and diffusion models, where sampling speed is a notorious practical bottleneck.
When reversing a diffusion process to generate an image, standard deterministic solvers like DDIM or DPM-Solver suffer from compounding discretization errors if the step size is too large. By applying the same randomized midpoint principles, researchers have shattered traditional theoretical limits on sampling complexity:
- Cubic Speedups: Saravanan Kandasamy et al. introduced the Poisson Midpoint Method in The Poisson Midpoint Method for Langevin Dynamics: Provably Efficient Discretization for Diffusion Models, demonstrating that evaluating the score function at a Poisson-style stochastic midpoint allows for up to 20$\times$ fewer steps in practice while maintaining high image fidelity.
- Sub-linear Dimension Scaling: Traditional diffusion samplers scale in complexity with the dimension as $O(\sqrt{d})$. By leveraging randomized midpoints to suppress discretization errors along the reverse trajectory, Shivam Gupta et al. in Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel proved a dimension scaling of $O(d^{5/12})$, showing that the square-root dimension barrier is not a fundamental limit.
- Optimal Convergence Rates: In Improved Convergence Rate for Diffusion Probabilistic Models, Gen Li et al. applied a randomized midpoint method to the probability flow ODE, establishing a state-of-the-art iteration complexity of $d^{1/3}\varepsilon^{-2/3}$.
By lifting the dynamics to higher-order state spaces (as explored by Wenlong Mou et al. in High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm) or combining randomized midpoints with randomized step sizes (such as the DRUL algorithm by Yuanshi Liu et al. in Double Randomized Underdamped Langevin with Dimension-Independent Convergence Guarantee), the convergence can even be made dependent on the intrinsic curvature (the trace of the Hessian) rather than the raw ambient dimension $d$.
Summary
Randomized midpoint discretization works because it reframes how we handle numerical errors in stochastic systems. Instead of fighting a losing battle trying to minimize deterministic drift through tiny steps, it intentionally randomizes the evaluation point. This converts systematic bias into zero-mean variance, which the underlying diffusion process absorbs effortlessly. When paired with the smooth trajectories of underdamped momentum, this technique provides a mathematically rigorous foundation for ultra-fast, high-dimensional sampling.