adu2021 Problem Statement
Existing discrete diffusion models suffer two fundamental bottlenecks:
- Neighborhood-blind forward process: Token-wise corruption mechanisms (masking, uniform replacement) ignore semantic proximity and similarity structure in discrete spaces.
- Constrained reverse dynamics: Restrictive mean parametrization tightly couples how denoising uncertainty translates into reverse model dynamics.
This limits expressiveness and scalability compared to continuous diffusion.
New Paradigm: Generalized Discrete Diffusion from Snapshots
Replace token-wise uniform processes with a unified framework supporting arbitrary noising via continuous-time Markov chains (rate matrices) and snapshot latent variables. Rather than tracking full noising paths, learn from single observations (x_t, t) pairs.
Vocabulary
Rate Matrix (Generator Matrix): Mathematical object Q_t characterizing continuous-time Markov chain evolution, factorized into:
- Exit rates: How often chains leave current states
- Jump kernels: Where chains transition to
Interpolating Matrix: K_t = α_t I_m + (1-α_t)Π_t, combining mixing rate intensity (α_t) with mixing matrix structure (Π_t) to control noise schedule.
Uniformization: Poisson-based sampling enabling exact forward noising without computing matrix exponentials—efficient for large vocabularies.
Snapshot Latent: Single observation tuple (x_t, t) replacing full noising trajectories as variational latent variable in training.
Founding Experiments
Language Modeling Performance
GDDS Absorb on Text8:
Bits per character (BPC): ≤1.16 (baseline AR: 1.35)
Achieves first discrete diffusion success beating autoregressive at this scale
GDDS Gauss on OpenWebText:
Perplexity: ≤7.65 (baseline AR: 20.49)
Zero-shot transfer shows consistent gains across 7 downstream tasks
Language Generation Quality:
- Superior quality-diversity tradeoff versus masked/uniform baselines
- GDDS Absorb achieves lower generative perplexity with fewer decoding steps
Opened Directions
Semantic-Informed Kernels: Extend beyond Gaussian kernels to exploit richer token similarity structures from embeddings or semantic graphs.
Non-Shared Exit Rates: Generalize uniformization beyond uniform exit rate assumption—allow token-dependent rates for fine-grained control.
Native Architectural Integration: Develop denoising networks with built-in support for path-wise objectives without two-stream encoder complexity.
Computational Efficiency at Scale: Scale semantic kernels beyond current KNN approximations; optimize for large vocabulary settings.
Information-Calibration Tradeoffs: Deeper analysis of snapshot versus full-path learning dynamics and their impact on model specialization versus generalization.