Discrete diffusions can sample from structured categorical data with provable sample complexity guarantees, and weight-sharing neural networks learn scores more efficiently than fully-connected ones for this task.
This paper develops theoretical guarantees for sampling from high-dimensional categorical distributions using discrete diffusion models.