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.
Introduction
Deep Autoregressive Models, such as PixelCNN and WaveNet, have become the gold standard for high-fidelity data density estimation. These models decompose the joint probability of a high-dimensional object into a sequence of conditional probabilities, where each element (e.g., a pixel or audio sample) depends on all preceding elements.
This structure creates a significant computational asymmetry. During training or evaluation, the availability of the full ground-truth data allows for massive parallelization across GPUs, making inference extremely fast. However, generating new data remains a strictly sequential process: one must sample pixel $i$ before pixel $i+1$ can even be considered. For a standard $32 \times 32$ image, this necessitates 1,024 sequential neural network passes, leading to prohibitive sampling times.
Previous research has attempted to mitigate this via model distillation or by introducing independence assumptions that break the dependency chain, often at the cost of model quality. This paper introduces Predictive Sampling, a method that accelerates sampling by leveraging the fast parallel evaluation property of ARMs to verify multiple predicted future steps simultaneously, without altering the underlying model.
Methodology
Isolating Stochasticity
The primary challenge in "guessing" future steps in a stochastic model is the randomness inherent in sampling. To address this, we utilize the Gumbel-Max trick to reparameterize the ARM. By fixing a block of random noise ($\epsilon$) at the start of the process, the sampling operation becomes a deterministic function of the input and the noise. This reparameterization turns the sampling task into a deterministic search for a "fixed point," where the generated sequence is consistent with both the model's logic and the pre-selected noise.
Predictive Sampling and Fixed-Point Iteration
Predictive Sampling treats the generation process as a "guess-and-check" algorithm. In its simplest form, ARM Fixed-Point Iteration (FPI), the current partial sequence is padded with guesses (often carried over from the previous iteration) and passed through the ARM in parallel. Due to the model's triangular dependency structure, the first new output is always mathematically valid. If the subsequent guesses happen to align with what the ARM would have generated sequentially, those steps are also validated instantly, effectively skipping multiple sequential passes.
Learned Forecasting Modules
To improve the accuracy of these guesses in complex datasets, we introduce Learned Forecasting Modules. These are lightweight neural networks that operate on the internal hidden states of the ARM to predict future values. By producing more accurate forecasts, these modules increase the probability that multiple steps can be verified in a single parallel forward pass of the main ARM.
Experimental Results
We evaluated Predictive Sampling across several benchmarks, including Binary MNIST, SVHN, CIFAR10, and ImageNet32. The method was tested both on raw pixel data and on the latent spaces of discrete autoencoders.
Speed and Efficiency
The speedups achieved are substantial, particularly given that the original ARM remains untouched:
- MNIST: The algorithm achieved a 27.6x speedup, requiring ARM calls for only 3.3% of the total pixels.
- Natural Images (CIFAR10/SVHN): We observed speedups ranging from 4x to 6x.
- Latent Spaces: On compressed representations, which typically exhibit less local redundancy than raw pixels, the method consistently provided 4x to 7x speedups.
Quality Preservation
A critical advantage of Predictive Sampling is that it introduces zero quality loss. Because the algorithm only accepts values that the original ARM would have produced under sequential sampling, the resulting samples are mathematically identical to those generated by the slower, traditional process.
Discussion and Limitations
While Predictive Sampling offers significant gains, its performance is tied to the predictability of the data. In high-entropy scenarios where future steps are highly uncertain, the forecasting accuracy drops, and the algorithm may revert toward the speed of sequential sampling. Additionally, the computational overhead of the forecasting modules must be balanced against the gains from parallel verification; on very simple datasets like MNIST, the simpler FPI approach often outperforms learned forecasting due to lower overhead.
Future work may explore more sophisticated batching logic. Currently, the speed of a batch is limited by the slowest-converging sample. Dynamic scheduling systems could potentially allow faster-converging samples to finish early, further optimizing throughput.
Summary updated