ParaLin: Accelerating Parallel Diffusion Integrator via Intrinsic Partially Linear Structure

This paper explores the challenge of accelerating the sequential inference process of Diffusion Probabilistic Models (DPMs). We tackle this critical issue from a dynamic system perspective, in which the inherent sequential nature is transformed into a parallel sampling process. Specifically, we first reveal that the sequential integral solver of the diffusion model can be approximated by a full linear solver, enabling efficient computation for parallel integral solvers of DPMs. We then introduce a unified framework that reformulates the original nonlinear sequential integral process of the DPMs as a system of partial linear equations. Moreover, we further develop an immediate update strategy to solve the system. In addition, we prove that (1) the system admits a unique root corresponding precisely to the trajectory of the sequential integral solver; (2) solving the system guarantees convergence to the trajectory of sequential integral solvers in equal or fewer iterations. We then present \textit{\paralin}, a partial linear parallel integral solver to accelerate a broad class of sequential and parallel sampling methods such as DDPM and ParaSolver. This partial linearity allows \paralin to achieve parallel speedup on more practical single GPU settings. Experiments (\textbf{12B Flux}, Stable Diffusion Model, VP, VE, EDM, flow matching) validate that \paralin achieves $\textbf{2.7}\times$ to $ \textbf{3.9}\times$ speedup in practical 25-50 steps. Notably, on more practical single GPU setting where SOTA parallel solvers typically exhibit constraints, \paralin outperforms them with a 2.5× time speedup. Furthermore, to demonstrate the scalability, we show it can unlock up to a 50x speedup on classical large-step settings (e.g., 1000-step DDPM). The source code will be released publicly.