Predictive Sampling with Forecasting Autoregressive Models

Auke J. Wiggers, Emiel Hoogeboom

TL;DR

Autoregressive models (ARMs) produce high-quality samples but are notoriously slow because they generate data one element at a time. This paper introduces Predictive Sampling, a method that uses parallel "forecasts" to guess future values and verify them in bulk. This technique achieves up to a 27x speedup without changing the underlying model or sacrificing sample quality.

What Problem Does This Paper Address?

Autoregressive models, like PixelCNN or WaveNet, are the gold standard for modeling complex data distributions such as images and audio. They work by breaking down a high-dimensional object into a sequence: to predict the next pixel, the model looks at all previously generated pixels.

Causal structure of autoregressive models

While this "causal" structure makes them exceptionally good at learning distributions, it creates a massive bottleneck during sampling. Because pixel $N$ strictly depends on pixel $N-1$, you have to run the model sequentially for every single pixel. For a small $32 \times 32$ image, that requires 1,024 sequential passes. In contrast, training these models is fast because we already know the "true" pixels and can compute all conditional probabilities in parallel. The authors set out to bring that parallel efficiency to the sampling process.

Methods: The "Guess-and-Check" Game

The core idea of Predictive Sampling is to turn sequential generation into a "guess-and-check" game. If we can accurately guess (forecast) what the next few pixels will be, we can use the ARM’s fast parallel evaluation property to verify those guesses all at once.

Verification step in Predictive Sampling

The authors propose two main components to make this work:

  1. Isolating Stochasticity: Usually, sampling is random. To make it predictable, the authors use the Gumbel-Max trick (reparameterization). By fixing a set of random noise variables ($\epsilon$) upfront, the sampling process becomes a deterministic function of the previous pixels and that noise. This makes "forecasting" a solvable problem.
  2. Forecasting Strategies:
    • ARM Fixed-Point Iteration (FPI): This uses the ARM itself to forecast. You fill the "future" slots with guesses, run a parallel pass, and see where the model's output matches your guesses. Any matching sequence is "valid" and can be kept.
  3. Learned Forecasting Modules: The authors also experiment with training tiny, lightweight auxiliary networks that look at the ARM’s internal hidden states to predict future values more accurately than a simple guess.

The algorithm essentially fills a buffer with forecasts, runs one parallel ARM pass, and "accepts" all values until the first point where the forecast and the model output disagree.

Key Insights and Ideas

  • The "Free" First Pixel: Because of the triangular (causal) dependence of ARMs, the very first output of a parallel pass is always valid, even if all your forecasts are wrong. This ensures the algorithm is never slower than standard sequential sampling (ignoring minor computational overhead).
  • Fixed-Point Convergence: The authors show that sampling can be viewed as finding a fixed point of a deterministic function. Because of the causal structure, this is guaranteed to converge in at most $d$ steps (where $d$ is the number of pixels), but in practice, it converges much faster.
  • Simplicity Wins: Surprisingly, the "Fixed-Point Iteration" (using the model to forecast itself) often performed as well as or better than the "Learned Forecasting" modules on complex datasets, all without requiring extra training.
  • Exact Sampling: Unlike "distillation" methods which approximate the original model, Predictive Sampling samples from the exact same distribution as the original ARM. There is zero loss in image quality.

Key Results

The researchers evaluated their method on standard benchmarks for generative modeling, including explicit likelihood modeling (Binary MNIST, SVHN, CIFAR10) and latent space modeling (using an ARM to model the discrete latent space of a VQ-VAE style autoencoder).

The speedups are significant, though they vary by dataset complexity:

  • MNIST: Achieved a massive 27.6x speedup in total sampling time for a single image.
  • CIFAR10 & SVHN: Showed speedups between 4x and 6x.
  • ARM Calls: On CIFAR10 (8-bit), the method reduced the number of required model forward passes from 100% (sequential) down to about 22%.
  • Latent Spaces: When modeling 8x8 latent grids, the method reduced ARM calls to roughly 14-17% of the baseline.

Limitations and Future Work

While highly effective, Predictive Sampling has a few limitations. The speedup is most dramatic for a batch size of 1. In larger batches, the entire batch must wait for the "slowest" image (the one that requires the most iterations to converge) to finish, leading to diminishing returns. Additionally, as the data becomes more "unpredictable" (higher entropy), the forecasts become less accurate, and the speedup decreases.

Future directions include developing better scheduling systems to handle varying convergence rates across a batch, which could unlock even more speed for production environments, and extending the methodology to handle continuous data.

Summary updated

Abstract

Autoregressive models (ARMs) currently hold state-of-the-art performance in likelihood-based modeling of image and audio data. Generally, neural network based ARMs are designed to allow fast inference, but sampling from these models is impractically slow. In this paper, we introduce the predictive sampling algorithm: a procedure that exploits the fast inference property of ARMs in order to speed up sampling, while keeping the model intact. We propose two variations of predictive sampling, namely sampling with ARM fixed-point iteration and learned forecasting modules. Their effectiveness is demonstrated in two settings: i) explicit likelihood modeling on binary MNIST, SVHN and CIFAR10, and ii) discrete latent modeling in an autoencoder trained on SVHN, CIFAR10 and Imagenet32. Empirically, we show considerable improvements over baselines in number of ARM inference calls and sampling speed.
BibTeX
@inproceedings{wiggers2020predictive,
  author = {Auke J. Wiggers and Emiel Hoogeboom},
  title = {{Predictive Sampling with Forecasting Autoregressive Models}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=zUCV6Dzz83},
}
Figure