Informed Correctors for Discrete Diffusion Models

Yixiu Zhao, Jiaxin Shi, Lester Mackey, Scott W. Linderman

TL;DR

This paper introduces "informed correctors" for discrete diffusion models, a novel sampling technique that significantly improves sample quality and efficiency. By intelligently using the diffusion model's learned knowledge to fix errors during generation, these informed correctors outperform existing methods on tasks like text and image generation, achieving better results with fewer computational steps.

What Problem Does This Paper Address?

Discrete diffusion models are powerful for generating data in discrete domains (like text or protein sequences), but sampling from them efficiently and with high quality is a challenge. Existing methods often struggle to balance computational cost with the accuracy of generated samples, especially when reducing the number of sampling steps. A common approach involves "predictor-corrector" steps to refine generated samples. However, for a specific type of discrete diffusion called "absorbing state diffusion," the standard "uninformed" corrector is not very effective at fixing errors, leading to lower quality outputs. This paper aims to address this limitation by developing a smarter, "informed" corrector that leverages the model's learned understanding to more effectively correct errors.

Methods

The core innovation is the informed corrector. Instead of randomly correcting errors (as in previous methods), the informed corrector uses the diffusion model's learned conditional probabilities to prioritize which parts of the generated sample are most likely to be incorrect and need fixing. This is inspired by adaptive Gibbs sampling.

To implement this, the authors propose:

  • Hollow Transformers: A specialized neural network architecture designed to output predictions for each dimension of the discrete data independently, crucial for efficient corrector updates. This architecture prevents information from one dimension from influencing the prediction of another, allowing for parallel processing.
  • Combined Training Objective (LHD): A new training objective that combines two existing loss functions (MD4 and a derived hollow transformer loss). This objective leverages more of the available training signal, leading to better model performance.
  • Adaptive Random-Scan Gibbs Sampling: The informed corrector uses a non-uniform sampling strategy to select which dimensions to update, prioritizing those with lower confidence scores (i.e., higher probability of error).
  • Final Argmax Update: An empirical finding that a deterministic argmax update at the very end of the sampling process can further improve sample quality by cleaning up remaining noise.

Datasets

The paper evaluates its methods on the following datasets:

  • Synthetic Markov Chain: A controlled environment to demonstrate the failure modes of existing samplers and the effectiveness of informed correctors.
  • Text8: A character-level text modeling dataset.
  • Tokenized ImageNet 256x256: A standard benchmark for image generation.

Key Insights and Ideas

  • Informed Correction is Crucial: Simply correcting errors randomly (uninformed corrector) can be worse than not correcting at all, highlighting the importance of using learned model knowledge for correction.
  • Hollow Transformers Enable Efficient Correction: The proposed hollow transformer architecture is key to enabling efficient, parallelized updates for the informed corrector, allowing it to leverage the model's predictions without information leakage between dimensions.
  • Combined Loss Functions Boost Performance: Merging different loss functions (LHD) provides a richer training signal, leading to better overall model performance compared to using individual losses.
  • Modularity of Correctors: The informed corrector can be applied to existing, pre-trained diffusion models (like MD4) to improve their sampling quality, demonstrating its broad applicability.

Key Results

  • Reduced Error Rates: On the synthetic Markov chain, informed correctors drastically reduce error rates compared to no corrector or uninformed correctors.
  • Improved Text Generation: On the Text8 dataset, the proposed method (HollowDiff) significantly outperforms baselines like MD4, achieving lower word error rates with fewer function evaluations.
  • Competitive Image Generation: On tokenized ImageNet 256x256, the informed corrector, especially when combined with MD4, achieves competitive FID scores with substantially fewer sampling steps than other state-of-the-art methods. For instance, a hybrid model achieved an FID of 5.78 with only 17 steps.
  • Efficiency Gains: The informed corrector allows for high-fidelity generation with significantly fewer computational steps (function evaluations) compared to existing methods.

Limitations and Future Work

  • Hollow Transformer Dependency: Applying the informed corrector to absorbing diffusion currently requires the use of the hollow transformer architecture, limiting its direct application to arbitrary pre-trained models.
  • Predictor-Corrector Trade-offs: Learning the informed corrector involves trade-offs between the quality of the denoiser and the corrector.
  • Future Work: The authors suggest exploring architectural or algorithmic improvements to the hollow transformer for greater efficiency. They also propose investigating how to make the scheme more efficient, potentially by applying architectural or algorithmic improvements to the hollow transformers. They also mention that for stronger base denoisers, the special final argmax update might become unnecessary.

Summary updated

Abstract

Discrete diffusion modeling is a promising framework for modeling and generating data in discrete spaces. To sample from these models, different strategies present trade-offs between computation and sample quality. A predominant sampling strategy is predictor-corrector $\tau$-leaping, which simulates the continuous time generative process with discretized predictor steps and counteracts the accumulation of discretization error via corrector steps. However, for absorbing state diffusion, an important class of discrete diffusion models, the standard forward-backward corrector can be ineffective in fixing such errors, resulting in subpar sample quality. To remedy this problem, we propose a family of informed correctors that more reliably counteracts discretization error by leveraging information learned by the model. For further efficiency gains, we also propose $k$-Gillespie's, a sampling algorithm that better utilizes each model evaluation, while still enjoying the speed and flexibility of $\tau$-leaping. Across several real and synthetic datasets, we show that $k$-Gillespie's with informed correctors reliably produces higher quality samples at lower computational cost.
BibTeX
@inproceedings{zhao2025informed,
  author = {Yixiu Zhao and Jiaxin Shi and Lester Mackey and Scott W. Linderman},
  title = {{Informed Correctors for Discrete Diffusion Models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=HDeIb67lJe},
}
Figure