Sharp Convergence and Sampling Trade-offs for Riemannian Diffusion under Nonnegative Ricci Curvature

Diffusion models have emerged as state-of-the-art generative models, with recent extensions from Euclidean spaces to Riemannian manifolds. However, existing convergence guarantees for Riemannian diffusion models typically require $\tilde{O}(\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(d,T)\mathrm{/}{\epsilon }^2)$ score evaluations, with potentially unfavorable dependence on the dimension. In this work, we develop a general framework that separates score discretization from Brownian-motion simulation and allows multiple geodesic random-walk steps per score evaluation. Under nonnegative Ricci curvature assumption and an exact Brownian-motion simulation oracle, we show that $\tilde{O}(d\mathrm{/}{\epsilon }^2)$ score evaluations suffice to achieve an ${\epsilon }^2$ KL divergence from the target distribution, matching the existing convergence rate of Euclidean diffusion models. We further show that $\tilde{O}(d^{4}T\mathrm{/}{\epsilon }^2)$ geodesic random-walk steps suffice to approximate the required drifted Brownian motion to $\epsilon$ total variation error. Combining these results yields a sampling scheme with $\tilde{O}(d\mathrm{/}{\epsilon }^2)$ score evaluations and $\tilde{O}(d^{4}T\mathrm{/}{\epsilon }^2)$ geodesic random-walk steps, motivating multiple random-walk steps between consecutive score evaluations. Our results provide a sharper characterization of the convergence and sampling complexity of Riemannian diffusion models.