Source-linked AI summary
Discrete Flows: Invertible Generative Models of Discrete Data
Dustin Tran, Keyon Vafa, Kumar Krishna Agrawal, Laurent Dinh, Ben Poole
TL;DR
Normalizing flows had advanced continuous modeling, but their applicability to discrete distributions remained unclear. This paper extends flows to discrete data with autoregressive and bipartite architectures, which outperform autoregressive baselines on controlled tasks and offer competitive character-level language modeling with faster generation.
Problem
Flows were not considered applicable to discrete distributions, where modeling instead relied largely on approximate-inference latent-variable models or fixed-order autoregressive models.
Source: §1 · p. 1Method
The paper extends invertible flows to discrete data with autoregressive and bipartite architectures, using a discrete change-of-variables rule based on the pre-image of a transformation.
Source: §1 · p. 1, §3.1 · p. 3Results
Discrete autoregressive flows outperform autoregressive baselines on controlled tasks, while bipartite flows reach similar performance with faster generation; character-level results include over 100x speedup.
Source: §1 · p. 2Takeaways & Limitations
Discrete autoregressive flows support bidirectional context with exact likelihood, while bipartite flows enable nonautoregressive generation with exact likelihood.
Source: §1 · pp. 1–2Scaling to vocabularies above 5,000 remains an open question because the straight-through gradient estimator may not work for subword-level modeling.
Source: §5 · p. 8
Abstract
from arXiv · showhide
While normalizing flows have led to significant advances in modeling high-dimensional continuous distributions, their applicability to discrete distributions remains unknown. In this paper, we show that flows can in fact be extended to discrete events---and under a simple change-of-variables formula not requiring log-determinant-Jacobian computations. Discrete flows have numerous applications. We consider two flow architectures: discrete autoregressive flows that enable bidirectionality, allowing, for example, tokens in text to depend on both left-to-right and right-to-left contexts in an exact language model; and discrete bipartite flows that enable efficient non-autoregressive generation as in RealNVP. Empirically, we find that discrete autoregressive flows outperform autoregressive baselines on synthetic discrete distributions, an addition task, and Potts models; and bipartite flows can obtain competitive performance with autoregressive baselines on character-level language modeling for Penn Tree Bank and text8.
1 Introduction
Normalizing flows have advanced continuous modeling, but their use for discrete distributions was unclear, where fixed-order autoregressive models and latent-variable models with approximate inference were common. The paper extends flows to discrete data through autoregressive and bipartite architectures.
1 Introduction
- Discrete autoregressive flows allow tokens to depend on both left-to-right and right-to-left contexts while retaining exact likelihood and sampling.This supports bidirectional language modeling without giving up those generative-model properties.Source: §1 · p. 1
- Discrete bipartite flows use coupling layers similar to RealNVP to support parallel, nonautoregressive text generation with exact likelihood for training and evaluation.The architecture is presented as a way to model discrete data while generating in parallel.Source: §1 · p. 2
- Discrete autoregressive flows outperform autoregressive baselines across controlled tasks, while bipartite flows match their performance with faster generation; on text8 and Penn Tree Bank they reach 1.23 and 1.38 bits per character, respectively, with over 100x faster generation.The controlled tasks include discretized mixtures of Gaussians, full-rank discrete distributions, addition, and Potts models.Source: §1 · p. 2
1.1 Related Work
- Earlier bidirectional language models require approximate inference or sampling, while autoregressive models impose an ordering [Mnih and Teh, 2012; Vinyals et al., 2015].Related discrete nonautoregressive approaches include blockwise models, latent-variable models, and iterative refinement; bipartite flows instead maintain an exact density.Source: §1.1 · p. 2
2 Background
Continuous normalizing flows transform a tractable base distribution through invertible functions, with composition increasing expressivity. The section reviews autoregressive and bipartite transformations, whose triangular Jacobians permit efficient determinants, and notes bipartite flows trade expressivity for fast computation.
2.1 Normalizing Flows
- Composing invertible flows transforms a tractable base distribution into a more expressive distribution; arbitrary Jacobian determinants can require O(D^3) computation.The section motivates structured transformations because that cost is infeasible for high-dimensional datasets.Source: §2.1 · p. 2, §2.2 · p. 2
2.2 Flow Transformation
- Autoregressive flows use location-scale transformations with autoregressive parameters; their triangular Jacobian gives an efficient determinant and log-probabilities for training and evaluation.The inverse can be vectorized and computed in parallel.Source: §2.2 · p. 3
- Bipartite coupling layers transform subsets of inputs, with scale and location functions of the unchanged subset; changing variable order across layers increases flexibility.Their Jacobian is lower-triangular, so its determinant is the product of diagonal elements.Source: §2.2 · p. 3
- Bipartite flows are less expressive than autoregressive flows because some variables remain untransformed, but their forward and inverse computations are fast for generation.The section identifies fast generation as the setting where this trade-off is useful.Source: §2.2 · p. 3
3 Discrete Flows
Discrete flows extend invertible transformations to discrete events using a change-of-variables rule without a log-determinant-Jacobian. Autoregressive and bipartite transformations provide different ways to model discrete dependencies, with training using a straight-through gradient estimator.
3.1 Discrete Change of Variables
- For discrete variables, output probability mass sums the input masses in the output's pre-image; invertibility reduces this to the mass at the unique inverse input.Unlike the continuous change-of-variables rule, this formula has no log-determinant-Jacobian term.Source: §3.1 · p. 3
3.2 Discrete Flow Transformation
- Binary XOR transforms use autoregressive locations, while categorical modulo location-scale transforms are invertible only when σ and K are coprime.The paper uses σ = 1 in all experiments except character-level language modeling.Source: §3.2 · p. 4
- A single discrete flow captures correlated modes in the discretized Gaussian mixture, unlike a factorized distribution.The figure notes that the autoregressive and bipartite architectures are equivalent for this 2-D example.Source: Figure 2 · p. 5, §3.2 · p. 5
3.3 Training Discrete Flows
- Training uses a straight-through gradient estimator, replacing the nondifferentiable argmax on the backward pass with a softmax-temperature function.The paper fixes τ = 0.1 and notes that very low temperatures can cause gradients to vanish.Source: §3.3 · p. 5
4 Experiments
Experiments compare discrete flows with autoregressive and factorized baselines on synthetic distributions, addition, Potts models, and character-level language modeling. Across these settings, flows improve likelihood or offer competitive performance with faster parallel generation.
4 Experiments
- Experiments use autoregressive categorical bases for autoregressive flows and factorized categorical bases for bipartite flows, with even/odd masking alternated in the latter.The full-rank experiment uses one autoregressive flow or four bipartite flows; the addition task uses an LSTM to encode both inputs and parameterize the autoregressive base.Source: §4 · p. 5, §4.1 · p. 6, §4.2 · p. 6
4.1 Full-rank Discrete Distribution
- On full-rank discrete distributions, autoregressive flows gain several nats over their autoregressive base, while bipartite flows improve over their factorized base and approach autoregressive-base likelihoods in parallel.The evaluation trains on data simulated from the sampled distributions; Table 1 reports negative log-likelihood in nats.Source: §4.1 · p. 6, Table 1 · p. 6
4.2 Addition
- For D = 10 addition, autoregressive flow reaches 0.2 nats versus 4.0 for its base; for D = 20, it reaches 4.8 versus 12.2 nats.Bipartite models improve as flows are added: 4.0, 3.17, and 2.58 nats for D = 10 with 1, 2, and 4 flows; 12.2, 8.8, 7.6, and 5.08 nats for D = 20 with 1, 2, 4, and 8 flows.Source: §4.2 · pp. 6–7
4.3 Potts Model
- On Potts models across lattice dimensions and coupling strengths, autoregressive flows perform as well as or better than autoregressive bases.The authors attribute the base model’s poor inductive bias to its fixed ordering and shared parameters across conditional distributions; higher coupling means more spatial correlation.Source: Table 2 · p. 6, §4.3 · p. 7
4.4 Character-Level Penn Tree Bank
- On Penn Tree Bank, the bipartite flow significantly outperforms Ziegler and Rush’s nonautoregressive models, and generates over 1000x faster than the LSTM baseline.The comparison measures generation time for a 288-dimensional sequence on an NVIDIA P100 GPU; bipartite generation uses one forward pass rather than 288 autoregressive passes.Source: §4.4 · p. 7, Table 3 · p. 7
4.5 Character-Level text8
- On text8, bipartite flows outperform the LSTM baseline but trail the 235M-parameter, 64-layer Transformer; generation is over 100x faster than baselines.Test bits per character decrease with more flows, more Transformer hidden units and layers, and a scale transformation rather than location alone.Source: §4.5 · p. 8, Figure 3 · p. 8
5 Discussion
The discussion presents discrete flows as invertible functions for modeling discrete data, with autoregressive and bipartite designs supporting different generation structures.
5 Discussion
- Discrete autoregressive flows stack levels of autoregressivity with varying orders to enable bidirectionality; bipartite flows compose bipartite-factorized transformations for nonautoregressive generation.The paper’s experiments cover synthetic tasks and character-level text data.Source: §5 · p. 8
- Scaling to vocabularies above 5,000 remains an open question because the straight-through gradient estimator may not work there, unlike its reported use for smaller character-level vocabularies.The authors identify alternative gradient estimators or data representations as possible directions.Source: §5 · p. 8
A Samples from Potts Model
Figure 4 presents samples from a Potts model on a 4×4 grid with three states and coupling strength J = 0.1.
A Samples from Potts Model
- Figure 4 shows Potts-model samples for a 4×4 grid, three states, and J = 0.1.The caption specifies the model setting but reports no quantitative comparison.Source: Figure 4 · p. 11