Improving Discrete Diffusion Models via Structured Preferential Generation

Severi Rissanen, Markus Heinonen, Arno SolinarXiv 2024 · DOI · arXiv

Introduction

Discrete diffusion models have emerged as a promising alternative to autoregressive models for generating structured data like text. However, they often fall short in performance because they typically treat all tokens as equally important during the noising and denoising processes. This paper introduces Structured Preferential Generation, a framework that incorporates inductive biases by ordering the generation of tokens based on their structural significance, such as frequency or information content.

The Problem with Random Masking

Most discrete diffusion models utilize an "absorbing state" approach. During training, tokens in a sequence are randomly replaced with a [MASK] symbol. During generation, the model attempts to predict the original tokens from these masks in a roughly parallel fashion.

The authors argue that this uniform treatment lacks a crucial inductive bias. In natural language, certain tokens (like common stop words or spaces) provide a structural "skeleton" for the rest of the sentence. Treating a rare, highly specific word with the same priority as a common character ignores the inherent hierarchy of information. This lack of structure can lead to inconsistent "hallucinations" when the model tries to predict dependent tokens simultaneously without sufficient context.

Structured Preferential Generation

To address this, the researchers propose a "structured forward process." Instead of masking tokens uniformly at random, they define a schedule where the probability of a token being masked depends on its category.

Comparison of generation strategies: (a) Autoregressive, (b) Standard Absorbing Diffusion, and (c) the proposed Ordered Absorbing Diffusion. Note how the ordered approach (c) prioritizes more common tokens first.

Key Methodological Components

  • Categorical Masking Schedules: The transition function is modified so that specific token types are destroyed later in the forward process and created earlier during the reverse (generative) process.
  • Mutual Information (MI) Schedule: To maintain efficiency, the model uses an MI-based heuristic to balance information revelation at each step, preventing the model from being overwhelmed by too many simultaneous predictions.
  • Ordering Strategies: The study explored several heuristics for token generation order:
  • Most Frequent First: Prioritizing common tokens (e.g., 'e', 'the', spaces).
  • Least Frequent First: The inverse strategy.
  • Information Gain: Using entropy-based metrics to identify tokens that provide the most context for the remaining sequence.

Experimental Insights

The method was evaluated across toy datasets, character-level text (TEXT8), and word-level text (WIKITEXT-2).

Frequency as a Structural Proxy

In character-level modeling (TEXT8), the "most frequent first" strategy was the most effective. By generating common characters first, the model establishes a contextual framework—similar to how image diffusion models resolve global shapes before fine details—which significantly improves test perplexity.

Handling Dependencies

Experiments on synthetic toy data demonstrated that when clear dependencies exist (e.g., token $X$ determines $Y$), generating the "anchor" tokens first leads to much better density estimation. The ordered model achieved a Valid ELBO of 0.129, compared to 0.181 for the standard absorbing model.

Challenges with Large Vocabularies

While successful for characters, the benefits were less pronounced for word-level modeling (WIKITEXT-2). The authors suggest that with large vocabularies, most words in a short sequence are relatively unique, making frequency-based "blocks" less distinct and harder for the model to exploit without more complex scheduling.

Conclusion and Future Work

Structured Preferential Generation demonstrates that introducing an ordering bias can significantly improve the performance of discrete diffusion models, particularly when the data has a clear hierarchical or dependent structure. While scaling to large vocabularies remains a challenge, this work opens new avenues for applying structured diffusion to other domains like graph generation or image segmentation, where structural hierarchies are prominent.

Summary updated

Abstract

In the domains of image and audio, diffusion models have shown impressive performance. However, their application to discrete data types, such as language, has often been suboptimal compared to autoregressive generative models. This paper tackles the challenge of improving discrete diffusion models by introducing a structured forward process that leverages the inherent information hierarchy in discrete categories, such as words in text. Our approach biases the generative process to produce certain categories before others, resulting in a notable improvement in log-likelihood scores on the text8 dataset. This work paves the way for more advances in discrete diffusion models with potentially significant enhancements in performance.
BibTeX
@misc{rissanen2024improving,
  author = {Severi Rissanen and Markus Heinonen and Arno Solin},
  title = {{Improving Discrete Diffusion Models via Structured Preferential Generation}},
  year = {2024},
  eprint = {2405.17889},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2405.17889},
}
Figure