Parallel and Flexible Sampling from Autoregressive Models via Langevin Dynamics

Vivek Jayaram, John Thickstun

Overview

Autoregressive models (ARMs), such as WaveNet for audio or PixelCNN for images, are powerful generative tools that predict the next value in a sequence based on all previous values. Despite their high-quality output, they suffer from two major bottlenecks:

  1. Sequential Slowness: Sampling is $O(n)$. Generating a 1-minute audio clip (over 1 million samples) requires 1 million sequential passes through a neural network, a process that cannot be accelerated simply by adding more hardware.
  2. Inflexibility: ARMs are inherently unidirectional. While they easily predict the future given the past, they struggle with inverse problems—like filling in missing patches (inpainting) or predicting the beginning of a clip given the end—without task-specific retraining.

To address these constraints, researchers introduce Parallel and Flexible (PnF) sampling. By treating the ARM as a Bayesian prior and using gradient-based optimization, PnF sampling refines an entire sequence simultaneously. This enables massive parallelization for long sequences and allows a single pre-trained model to solve diverse inverse problems zero-shot.

Methodology: The PnF Sampler

The PnF Sampler abandons token-by-token generation. Instead, it initializes a full sequence with white noise and iteratively "nudges" the entire sequence toward high-likelihood regions using Langevin dynamics.

This approach relies on three key technical innovations:

  • Autoregressive Smoothing: Standard ARMs operate on discrete values (like 8-bit audio), which are non-differentiable. The authors solve this by convolving the discrete distribution with Gaussian noise. The model is fine-tuned to predict the original signal from a noisy history, creating a "smoothed" continuous landscape that gradients can navigate.
  • Annealed Langevin Dynamics: The sampler begins with high noise (a "hot" temperature) to explore global structures and gradually "cools" the noise to capture fine details.
  • Stochastic Parallelization: For massive sequences, multiple GPUs can asynchronously update different "patches" of the data simultaneously. This block-stochastic variant makes sampling time inversely proportional to the number of available devices.
The smoothing process: convolving discrete distributions with Gaussian noise makes them differentiable for Langevin dynamics.

Key Insights and Results

The authors evaluated PnF sampling on audio datasets (VCTK speech and Supra Piano, sampled at 22kHz) and image datasets (CIFAR-10 using a pre-trained PixelCNN++).

Quality and Convergence

Empirically, the number of iterations needed for the Langevin chain to converge is independent of the sequence length. As the number of Langevin iterations increases, the log-likelihood of PnF samples approaches that of traditional ancestral sampling, demonstrating that PnF does not sacrifice quality for its added flexibility.

Log-likelihood of PnF samples vs. number of iterations. More iterations lead to higher quality samples that match ancestral baselines.

Speedup for Long Sequences

Because convergence is length-independent, PnF eventually outpaces sequential sampling for very long sequences. For audio signals longer than ~5 seconds, PnF sampling on 8 GPUs becomes significantly faster than sequential ancestral sampling. For a 30-second clip, PnF is roughly 3x faster than the sequential baseline.

Zero-Shot Inverse Problems

Because PnF samples by following gradients, generation can be "steered" by adding constraint terms. For example, super-resolution can be achieved by adding a gradient term that penalizes the sequence if its down-sampled version doesn't match the low-resolution input. This cleanly decouples the generative prior from the restoration task, allowing PnF to achieve competitive results (17.07 dB SI-SDR) on audio source separation without specialized supervised models. It also successfully performs inpainting and super-resolution on CIFAR-10 images using a standard PixelCNN++ prior.

Limitations and Future Work

While highly effective for long sequences, PnF sampling does have limitations:

  • Short Sequence Overhead: For small data like 32x32 images, PnF is slower than ancestral sampling because the required number of Langevin iterations exceeds the number of pixels.
  • Storage Requirements: The current smoothing method requires storing multiple fine-tuned versions of the model (one for each noise level), although only one needs to be in memory at any given time.
  • Discrete Domains: The paper focuses on discretized continuous data (audio and images). Extending this gradient-based approach to purely discrete domains, such as text in Natural Language Processing, remains an open challenge.

Summary updated

Abstract

This paper introduces an alternative approach to sampling from autoregressive models. Autoregressive models are typically sampled sequentially, according to the transition dynamics defined by the model. Instead, we propose a sampling procedure that initializes a sequence with white noise and follows a Markov chain defined by Langevin dynamics on the global log-likelihood of the sequence. This approach parallelizes the sampling process and generalizes to conditional sampling. Using an autoregressive model as a Bayesian prior, we can steer the output of a generative model using a conditional likelihood or constraints. We apply these techniques to autoregressive models in the visual and audio domains, with competitive results for audio source separation, super-resolution, and inpainting.
BibTeX
@inproceedings{jayaram2021parallel,
  author = {Vivek Jayaram and John Thickstun},
  title = {{Parallel and Flexible Sampling from Autoregressive Models via Langevin Dynamics}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=S1_WNgva2Qn},
}
Figure