Anytime Sampling for Autoregressive Models via Ordered Autoencoding
Authors: Yilun Xu
Yang Song
Sahaj Garg
Linyuan Gong
Rui Shu
Aditya Grover
Stefano Ermon
Venue: ICLR 2021 Poster (2021)

Abstract: Autoregressive models are widely used for tasks such as image and audio generation. The sampling process of these models, however, does not allow interruptions and cannot adapt to real-time computational resources. This challenge impedes the deployment of powerful autoregressive models, which involve a slow sampling process that is sequential in nature and typically scales linearly with respect to the data dimension.  To address this difficulty, we propose a new family of autoregressive models that enables anytime sampling. Inspired by Principal Component Analysis, we learn a structured representation space where dimensions are ordered based on their importance with respect to reconstruction. Using an autoregressive model in this latent space, we trade off sample quality for computational efficiency by truncating the generation process before decoding into the original data space. Experimentally, we demonstrate in several image and audio generation tasks that sample quality degrades gracefully as we reduce the computational budget for sampling. The approach suffers almost no loss in sample quality (measured by FID) using only 60\% to 80\% of all latent dimensions for image data. Code is available at https://github.com/Newbeeer/Anytime-Auto-Regressive-Model.

Published as a conference paper at ICLR 2021
ANYTIME SAMPLING FOR AUTOREGRESSIVE MODELS VIA ORDERED AUTOENCODING
Yilun Xu
Yang Song Stanford University
Massachusetts Institute of Technology ylxu@mit. edu
yangsong@cs stanford. edu
Sahaj Garg
Linyuan Gong
Stanford University sahajg@es stanford.edu
UC Berkeley gonglinnyuan@hotmai.. com
Rui Shu Stanford University ruishuêes. stanford.
Aditya Grover UC Berkeley com
Stefano Ermon
Stanford University ermonêcs. ermon@cs.stanforddee stanford.eddd
ABSTRACT
Autoregressive models are widely used for tasks such as image and audio genera- tion. The sampling process of these models, however, does not allow interruptions and cannot adapt real-time computational resources. This challenge impedes the deployment of powerful autoregressive models, which involve a slow sampling process that is sequential in nature and typically scales linearly with respect the data dimension. To address this difficulty, we propose a new family of autore- gressive models that enables anytime sampling. Inspired by Principal Component Analysis, learn a structured representation space where dimensions are ordered based on their importance with respect to reconstruction. Using an autoregressive model in this latent space, trade off sample quality for computational efficiency by truncating the generation process before decoding into the original data space. Experimentally, we demonstrate in several image and audio generation tasks that sample quality degrades gracefully as reduce the computational budget for sampling. The approach suffers almost no loss in sample quality (measured by FID) using only 60% to 80% of all latent dimensions for image data. Code is available htttt:///gtthbb.ooom//////////// Aww.:///yyyynnnt-ooessss----aaa
INTRODUCTION
Autoregressive models are prominent approach to data generation, and have been widely used to
produce high quality samples of images (Oord et al. [01 Salimans et al. 2017 Menick & Kalch brenner 2018), audio (Oord al. 2016a), video KKlchbrenner et (017)) and text (Kalchbrenner et al. R et al. 2019). These models represent a joint distribution as a product of (simpler) conditionals, and sampling requires iterating over all these conditional distributions in certain order. Due to the sequential nature of this process, the computational cost will grow at least linearly with respect to the number of conditional distributions, which is typically equal to the data dimension. As result, the sampling process of autoregressive models be slow and does not allow interruptions.
Radford
Although caching techniques have been developed to speed up generation (Ramachandran et al.) 2017, Guo et al.) (017). the high cost of sampling limits their applicability in many scenarios. For example, when running on multiple deviges with different computational resources, we may wish to trade off sample quality for faster generation based on the computing power available on each device. Currently, a separate model must be trained for each device (i.e., computational budget) in order to

---

Published as a conference paper at ICLR 2021
trade off sample quality for faster generation, and there is no way to control this trade-off on the fly to accommodate instantaneous resource availability at time-of-deployment.
To address this difficulty, we consider the novel task of adaptive autoregressive generation under computational constraints. We seek to build a single model that can automatically trade-off sample quality versus computational cost via anytime sampling. i.e., where the sampling process may be interrupted anytime (e-g., because of exhausted computational budget) to yield a complete sample whose sample quality decays with the earliness of termination.
In particular, we take advantage of a generalization of Principal Components Analysis (PCA) pro- posed by Rippel et al. (2014), which learns an ordered representations induced by structured application dropout to the representations learned by an autoencoder. Such a representation encodes raw data into latent space where dimensions are sorted based on their importance for reconstruction. Autoregressive modeling is then applied in the ordered representation space instead, This approach enables a natural trade-off between quality and computation by truncating the length of the representations: When running on devices with high computational capacity, to generate the full representation and decode it to obtain a high quality sample; when on a tighter computational budget, we can generate only the first few dimensions of the representation and decode to a sample whose quality degrades smoothly with truncation. Because decoding is usually fast and the main computation bottleneck lies on the autoregressive part, the run-time grows proportionally relative to the number of sampled latent dimensions.
afford
Through experiments, we show that our autoregressive models are capable of trading off sample quality and inference speed. When training autoregressive models on the latent space given by our encoder, witness little degradation of image sample quality using only around 60% 80% of all latent codes, as measured by Fréchet Inception Distance (Heusel et al. 2017) on CIFAR- 10 and CelebA. Compared to standard autoregressive models, approach allows the sample quality to degrade gracefully as we reduce the computational budget for sampling. We also observe that on the VCTK audio dataset (Veaux et al., (017), our autoregressive model is able to generate the low frequency features first, then gradually refine the waveforms with higher frequency components as we increase the number of sampled latent dimensions.
BACKGROUND
Autoregressive Models Autoregressive models define a probability distribution over data points x E RD by factorizing the joint probability distribution as product of univariate conditional distributions with the chain rule. Using pø to denote the distribution of the model, we have:
1
(x) = III Pa(;; L1. x111)
(1)
2=1
The model is trained by maximizing the likelihood:
L = Ex [x)]]
(2)
where pa(x) represents the data distribution.
Different autoregressive models adopt different orderings of input dimensions and parameterize the conditional probability pa(x;; I1, i = 1.... D in different ways. Most archi- tectures over images order the variables æ1, xD of image x in raster sean order (i.e., left-to- right then lop-to-bottom). Popular autoregressive architectures include MADE (Germain et al. 2015), PixeICNN (Oord et al. 2016b; van den Oord al. 2016 Salimans et al. (017) and Trans- former (Vaswani et al. 2017). where they respectively use masked linear layers, convolutional layers and self-attention blocks to ensure that the output corresponding to po [1,- , .i-1) 1) is oblivious of Z;;; T141, D.
Cost of Sampling During training, we can evaluate autoregressive models efficiently because "1,""", are provided by data and all conditionals p(a; :,,... 2i-1) can be computed in parallel. In contrast, sampling from autoregressive models is an inherently sequential process and cannot be easily accelerated by parallel computing: we first need to sample I1, after which we sample Iz from (0 æ1) and so on- on- the i-th variable x; can only be obtained after we have already computed "., - Thus, the run-time of autoregressive generation grows at least linearly with respect to the length of sample. In practice, the sample length 1 be more than hundreds of
2

---

Published as a conference paper at ICLR 2021
thousands for real-world image and audio data. This poses major challenge to fast autoregressive generation on small computing budget.
ANYTIME SAMPLING WITH ORDERED AUTOENCODERS
Our goal is to circumvent the non- intiiterruption and linear time complexity of autoregressive models by pushing the task of autoregressive modeling from the original data space (e.g., pixel space) into an ordered representation space. In doing so, we develop new class of autoregressive models where premature truncation of the autoregressive sampling process leads the generation of lower quality sample instead of an incomplete sample. In this section, we shall first describe the learning of the ordered representation space via the use of ordered autoencoder. We then describe how to achieve anytime sampling with ordered autoencoders.
3.1 ORDERED AUTOENCODERS
Consider autoencoder that encodes input E RD to code z E RK Let =o()) RD RK be the encoder parameterized by 0 and x' = dz(z): R - R be the decoder parameterized by Φ. We define eg (+)) x E IRD + (Z1,22, 22, ... 24, 0, ... 0)T E RR, which truncates the (x))., masking out the remainder of the
representation the first dimensions of the encoding dimensions with a zero value. We define the ordered autoencoder objective as
N
x
(3)
==1
We note that Eq. equivalent to Rippel al. 2014)'s 's nested dropout formulation using uniform sampling of possible truncations. Moreover, when the encoder/decoder pair is constrained to be pair of orthogonal matrices up to transpose, then the optimal solution in Eq. recovers PCA.
3.1.1 THEORETICAL ANALYSIS
Rippel et al. (2014)'s s analysis of the ordered autoencoder is limited to linear/sigmoid encoder and linear decoder. In this section, we extend the analysis to general autoencoder architectures by employing an coormation-theorede
framework to analyze the importance of the i-th latent code to reconstruction for ordered autoencoders. We first reframe our problem from a probabilistic perspective. In lieu of using deterministic autoencoders, functions. In particular, we let geo (z x) be probability distribution over E IR conditioned on input x, and similarly let pa, (x z.) be the stochastie counterpart to da (z). We then qea (z x) to denote the distribution of (21, 22. 23. 0, .......... 0)T RRKK where z gep (z x), and let Pa, (x 2) şi represent the distribution of pa, (x (21, z2, Zi, 0, O0T
assume that both the encoder and decoder stochastic
RR*), We modify
Eq. to have the following form:
E Ex=-p(()). (E (z)x)
log Pa. (x)
where 21{1, }} denotes uniform distribution over 21, ... ..),............ K). and pa(x) represents the data distribution. We choose both the encoder and decoder to be fully factorized Gaussian distributions with a fixed variance o², then Eq. (13) can be simplified to
K
Epa(x)
Σ
1 20
|x - do (2)
K
The stochastic encoder and decoder in this case will become deterministic when a - 0, and the above equation will yield the same encoder/decoder pair as Eq. (3) when a 0 and N - co.
The optimal encoders and decoders that minimize Eq. (3) satisfy the following property. Theorem 1.
Let denote the input random variable. Assuming both the encoder and decoder are optimal terms of minimizing Eq. (13). and Vi 3...... K, 2 2, x, 251-2, we have
Vi 13, K} T(2xx(a55-1) [(
where zgg denotes (21, 22, ... 2:).
3

---

Published as a conference paper at ICLR 2021
90
uxdchhokk
data
oeder
order
Coito B1
Fronder
Decoder
Astorggoosis
Decedkr
(a)
(b)
Figure 1: (a) Spatial-wise quantization vs. channel-wise quantization. (b) Anytime sampling for OVQ-VAE.
We defer the proof to Appendix A. The assumption 2:-1 2; X, X,2-22 holds whenever the encoder (z z x) is a factorized distribution, which is a common choice in variational autoen- coders KKngma & Welling 2013), and we use [(a: b c) to denote the mutual information between random variables a and conditioned on c. Intuitively, the above theorem states that for optimal encoders and decoders that minimize Eq. (13), one can extract less additional information about the raw input as the code gets longer. Therefore, there exists natural ordering among different dimensions of the code based on the additional information they can provide for reconstructing the inputs.
3.2 ANYTIME SAMPLING
Once we have learned an ordered autoencoder, we then train an autoregressive model on the full length codes in the ordered representation space, also referred to ex-post density estimation (Ghosh et al. 2020 For each input x; in a dataset X1, ... XNy we feed it to the encoder to get z; = co (3(x))....) The resulting codes 2 ... 2N are used as training data. After training both the ordered autoencoder and autoregressive model, we can perform anytime sampling on a large spectrum of computing budgets. Suppose for example we can afford to generate 7 code dimensions from the autoregressive model, denoted as ZgT E RT,.. We can simply zero-pad to get (21, 2.. 22, 0, ... 0)T R and decode it to get a complete sample. Unlike the autoregressive part, the decoder has access to all dimensions of the latent code at the same time and can decode parallel. The framework is shown in Fig. [b). For the implementation, we use the ordered VQ-VAR (Section 4 as the ordered autoencoder and the Transformer (Vaswani al., 2017) the autoregressive model. On modern GPUs, the code length has minimal effect on the run-time of decoding, as long as the decoder not itself autoregressive (see empirical verifications in Section 5.2.2
4 ORDERED VQ-VAE
In this section, we apply the ordered autoencoder framework to the vector quantized variational autoencoder VQ-VAE) and its extension (yan den Oord al. 2017] Razavi et al. 2019). Since these models are quantized autoencoders paired with a latent autoregressive model, they admit natural extension to ordered VQ-VAE, (OVQ-VAEL under VAE models capable of anytime sampling. Below, we begin by describing the VQ-VAE, and then highlight two key design choices (ordered discrete codes and channel-wise quantization) critical for OVQ-VAEs. VAEs. We show that, with small changes of the original VQ-VAE these two choices can be applied straightforwardly.
framework- new family of VQ-
4.1 VQ-VAE
To construct a VQ-VAE VAE with code length K discrete latent variables the encoder must first map the input to a continuous representation z ex(x) R before feeding vector-valued quantization function q RXXD (1,2...., defined as
q(z²), arg min |le, - |lz ve(1.....0) .C.
4

---

Published as a conference paper at ICLR 2021
where g(z"), (1,2.... , denotes the j-th component of the vector valued function (zz"), zj RD denotes the j-th row z" and e, denotes the i-th row of the embedding matrix E ECx Next, we view q(z") as a sequence of indices and use them to look up embedding vectors from the codebook E. This yields a latent representation E R xxD given by zj Cy((*))) where z E ER" denotes the j-th row of z Finally, we can decode z to obtain the reconstruction d. (z²).. This procedure can be viewed as a regular autoencoder with a non-differentiable nonlinear function that maps each latent vector zj to I-of-K embedding vectors e;
.........
During training, we use the straight-through gradient estimator (Bengio et al. 2013) to propagate gradients through the quantization function, i.e., gradients are directly copied from the decoder input z" to the encoder output z". The loss function for training single data point x is given by
||d)(2 - x + [s)] - " (l - sg[2"]]|
where sg stands for the stop sttp_graddeeeeeeeeeeo gradienttttt.... operator, which is defined identity function forward computation and has zero partial derivatives at backward propagation. 33 is a hyper-parameter ranging from 0.1 to 2.0. The first term of Eq. (5) is the standard reconstruction loss, the second term is for embedding learning while the third term for training stability (van den Oord et al., 2017). Samples from a VQ-VAE can be produced by first training an autoregressive model on its latent space, followed by decoding samples from the autoregressive model into the raw data space.
4.2 ORDERED DISCRETE CODES
Since the VQ-VAE outputs sequence of discrete latent codes g(z"), we wish to impose an ordering that prioritizes the code dimensions based on importance to reconstruction. In analogy to Eq. (3). we can modify the reconstruction error term in Eq. (5) learn ordered latent representations. The modified loss function is an order-inducing objective given by
K Σ
- [[gg(e(x) - E. + 3
(x - sg(2
(6)
where (x) and 2 denote the results of keeping the top rows of (x and xd and then masking out the remainder rows with zero vectors. We uniformly sample the masking index i ~~ U(1, K} to approximate the average in Eq. (6) when K is large. An alternative sampling distribution is the
geometric distribution (Rippel et al. 2014). In Appendix CC33 we show that OVQ-VAE is sensitive to the choice of the parameter in geometric distribution. Because of the difficulty, [Ripell et al.] (2014) applies additional tricks. This results in the learning of ordered discrete latent variables, which can then be paired with a latent autoregressive model for anytime sampling.
4.3 CHANNEL- WISE QUANTIZATION
In Section 4.1
we assume the encoder output to be K x D matrix (i.e., z" RRxD) In practice, the output can have various sizes depending on the encoder network, and we need to reshape to two-dimensional matrix. For example, when encoding images, the encoder is typically 2D convolutional neural network (CNN) whose output is 3D latent feature map of size L H W. Here L, H, and W stand for the channel, height, and width of the feature maps. We discuss below how the reshaping procedure can significantly impact the performance of anytime sampling and propose a reshaping procedure that facilitates nigh-performance anytime sampling.
Consider convolutional encoders on image data, where the output feature map has a size of Lx HxW.WW The most common way of reshaping this 3D feature map, as in van den Oord et al. (2117). is to let H x W be the code length, and let the number of channels L be the size of embedding vectors, i.e., K H x W and D L. We call this pattern spatial-wise quantization, as each spatial location the feature map corresponds to one code dimension and will be quantized separately. Since the code dimensions
4
4
5
6
0
9
4
0
4
/
1
9
8
0
Figure 2: MNIST (top) and CelebA (bottom) samples gen- erated with 1/4 of the code length. Left: Spatial-wise quanti- zation. Right: Channel-wise quantization.
5

---

Published as a conference paper at ICLR 2021
correspond to spatial locations of the feature map, they encode local features due to a limited receptive field. This is detrimental to anytime sampling, because early dimensions cannot capture the global information needed for reconstructing the entire image. We demonstrate this in Fig. 2 which shows that DVQ-VAE with spatial-wise quantization is only able to reconstruct the top rows of an image with 1/4 of the code length.
To address this issue, we propose channel-wis wise quantization, where each channel of the feature map viewed as one code dimension and quantized separately (see Fig. TTa) for visual comparison of spatial-wise and channel-wist quantization). Specifically, the code length is L (i... K = L), and the size of the emhedding vectors is H W (Le., D H W). In this case, code dimension includes all spatial locations in the feature map and can capture global information better. As shown in the right panel of Fig. 2 channel-wist quantization clearly outperforms spatial-wise quantization for anytime sampling. We use channel-wiss quantization in all subsequent experiments. Note that in practice we can easily apply the channel-wise quantization on VQ-VAE by changing the code length from H W to L, as shown in Fig- [a).
5 EXPERIMENTS
In our experiments, we focus on anytime sampling for autoregressive models trained on the latent space of OVQ- VAEs, shown in Fig. [b). We first verify that our learning objectives in Eq. 3.. Eq. (6) are effective at inducing ordered representations. Next, we demonstrate that our OVQ- VAE models achieve comparable sample quality to regular VQ-VAEs on several image and audio datasets, while additionally allowing a graceful trade-off between sample quality and computation time anytime sampling. Due to limits on space, we defer the results of audio generation to Appendix B and provide additional experimental details, results and code links in Appendix E and G
5.1 ORDERED VERSUS UNORDERED CODES
Our proposed ordered autoencoder framework learns an ordered encoding that is in contrast to the encoding learned by a standard au- toencoder (which we shall refer to as unordered). In addition to the theo- retical analysis in Section 3.1.1] provide further empirical analysis to characterize the difference between or- dered and unordered codes. In particu- lar, we compare the importance of the i-th code- measured by the reduc- tion in reconstruction error (ii) PCA, standard (unordered) VQ-VAE, and ordered VQ- VQ-V For VQ-VAE and ordered VQ-VAE, we define the reduction in reconstruction error A(i) for a data point x as
40
Unordered VQ-VAE
Squared reconsirucioo
Ordered VQ-VAE
PCA
150
Unorderred VQ-VAE
Ordered VQ-VAE
100
PCA
50
20
40
60
20
40
60
Code length
Code length
(a)
(b)
Figure 3: Ordered vs. unordered codes on CIFAR-10.
Ax
|do( x|| |dd -
Averaging (i over the entire dataset thus yiclds (1)). Similarly we define A(i) as the reduction on reconstruction error of the entire dataset, when adding the i-th principal component for PCA.
Fig. 3(a) shows the A(i)'s of the three models on the CIFAR-IO. Since PCA and ordered VQ-VAE both learn an ordered encoding. their A(i)'s ' decay gradually as i increases. In contrast, the standard VQ-VAE with an unordered encoding exhibits highly irregular A(i), indicating no meaningful ordering the dimensions.
Fig. 3(b) further shows how the reconstruction eтror decreases as function of the truncated code length for the three models. Although unordered VQ-VAE and ordered VQ-VAE achieve similar reconstruction errors for sufficiently large code lengths, it is evident that an ordered encoding achieves significantly better reconstructions when the code length is aggressively truncated. When sufficiently truncated, we observe even PCA outperforms unordered VQ- VQ-VAE despite the latter being a more expressive model. In contrast, ordered VQ-VAE achieves superior reconstructions compared to PCA and unordered VQ-VAE across all truncation lengths.

---

Published as a conference paper at ICLR 2021
We repeat the experiment standard VAE to disentangle the specific implementations in VQ- VAE. We observe that the order-inducing objective has consistent results on standard VAE (Appendix C.I
5.2 IMAGE GENERATION
We test the performance of anytime sampling using OVQ-VAEs (Anytime ordered) on several image datasets. We compare our approach to two baselines. One is the original VQ-VAB model proposed by van den Oord al. (2017) without anytime sampling. The other is using anytime sampling with unordered VQ- VAES (Anytime + unordered), where the models have the same architectures ours but are trained by minimizing Eq. (5). We empirically verify that 1) we are able to generate high quality image samples: 2) image quality degrades gracefully as we reduce the sampled code length for anytime sampling; and 3) anytime sampling improves the inference speed compared to naïve sampling of original VQ-VAEs.
We evaluate the model performance on the MNIST, CIFAR-I0 10 (Krizhessyy 2009) and CelebA (Liu et al. 2014) datasets. For CelebA, the images are resized to 64 x 64. All pixel values are scaled to the range [0, 1]. We borrow the model architectures and optimizers from van den Oord al. (001)).
The full code length and the codebook size are 16 and 126 for MNIST, 70 and 1000 for CIFAR- 10,
and 100 and 500 for CelebA respectively. We train Transformer (Vaswani et al.) 2017) our
VQ-VAEs, as opposed to the PixeICNN model used in van den Oord et al. (2017). PixeICNNs use standard 2D convolutional layers to capture a bounded receptive field and model the conditional dependence. Transformers apply attention mechanism and feed forward network model the conditional dependence of ID sequence. Transformers are arguably more suitable for channel-wise quantization, since there are no 2D spatial relations among different code dimensions that can be leveraged by convolutional models (such as PixeICNNs). Our experiments on different autoregressive models in Appendix C.2 further support the arguments.
120
Anytie+ unordered
CIFAR-10
Anylime e unordered Anytmme ordered VO-VE
ColebA
600
CIFAR-10
Anylime ordered
1300
Anylime ordered
CelebA
FID Scora
1:0
VQ-VAE
Arylime+ arduned
FID Storee
150
Wall-book time
400
Decode
Wall-booc dee
750
VQ-VAE
Dooodo
100
500
200
250
90
50
0.25
0.50
0.75
1000
0.4
0.8
0.8
1.0
0.25
0.50
0.75
1.00
0.5
Fraction of code length
Fraction full code length
Fradion of full code length
Fraction ofll code length
(a) Image quality
(b) Inference speed
Figure 4: (a) FID scores for anytime sampling using various code lengths. (b) Inference speed of anytime sampling with different code lengths.
5.2.1 IMAGE QUALITY
In Fig. 4aa) we report FID (Heusel et al., 2017) scores (lower is better) on CIFAR- 10 and CelebA when pertorming anytime sampling for ordered versus unordered VQ-VAE. FID (Fréchet Inception Distance) score is the Fréchet distance between two multivariate Gaussians, whose means and covariances are estimated from the 2048- -in-ddimessional activations of the Inception-v3 (Szegedy et al. 2016) network for real and generated samples respectively. As a reference, we also report the FID scores when using the original VQ- VAE model (with residual blocks and spatial-wise quantization) sampled the full code length (van den Oord et al., 2017). Our main finding is that OVQ-VAE achieves a better FID score than unordered VAE at all fractional code lengths (ranging from 20% to 100%); in other words, OVQ-VAE achieves strictly superior anytime sampling performance compared to unordered VQ-VAE on both CIFAR- 10 and CelebA. On CIFAR-10 dataset, a better FID score is achieved by OVQ- VAE even when sampling full codes. In Appendix C.4, we show that the regularization effect of the ordered codes causes this phenomenon.
In Fig. 5 (more in Appendix G.I). we visualize the sample quality degradation as a function of fractional code length when sampling from the OVQ-VAE. We observe a consistent increase in sample quality as we increased the fractional code length. In particular, we observe the model to initially generate a global structure of an image and then gradually fill in local details. We further show in Appendix [F that, samples sharing the highest priority latent code have similar global structure.
7

---

Published as a conference paper at ICLR 2021
4
4
9
9
2
9 0
0
4
/
1
9
8
4
4
5
0
9
2
0
4
/
9
1
9
8
0
4
4
5
5
0
7
2
4 0
0 4
/
9
\
9
8
4
4
5
5
0
4 9
2 8
4 0
0
4
/
9
X
(a) MNIST
(b) CIFAR-10
(c) CelebA
Figure 5: Anytime sampling with 0.255/.5/0.75/1.0 (top to bottom) fractions of full code length on MNIST (left), CIFAR-10 (middle) and CelebA (right) datasets.
Although our method was inspired by PCA, encountered limited success when training an autoregressive model on the PCA-represented data. Please refer to Appendix D for more details.
5.2.2 INFERENCE SPEED
We compare the inference speed of our approach vs. the original VQ- model by the wall-clock time needed for sampling. We also include the decoding time in our approach. We respectively measure the time of generating 50000 and 100000 images on CIFAR-10 and CelebA datasets, with batch size of 100. All samples are produced on single NVIDIA TITAN Xp GPU.
Fig. 4(b) shows that the time needed for anytime sampling increases almost linearly with respect to the sampled code length. This supports our argument in Section 3.2 that the decoding time is negligible compared to the autoregressive component. Indeed, the decoder took around 24 seconds to generate all samples for CelebA, whereas the sampling time of the autoregressive model was around 610 seconds- an order of magnitude larger. Moreover, since we can achieve roughly the highest sample quality with only 60% of the full code length CelebA, anytime sampling can save around 40% run- run-time compared to naïve sampling without hurting sample quality.
In addition, our method is faster than the original VQ-VAE VAE even when sampling the full code length, without compromising sample quality (cf., Section 5.2.I). This is because the Transformer model we used is sufficiently shallower than the Gated Pixe (van den Oord et al., 2016) model the autoregressive model
original VQ- DAE paper. Compared to PixeICNN+ (Salimans et al. 2017). on the raw pixel space, the sampling speed of our method can be an order of magnitude faster since our autoregressive models are trained on the latent space with much lower dimensionality.
6 RELATED WORK
Prior work has tackled the issue of slow autoregressive generation by improving implementations of the generation algorithm. For example, the sampling speed of convolutional autoregressive models can be improved substantially by caching hidden state computation (Ramachandran al. (017). While such approaches provide substantial speedups in generation time, they are still at best linear in the dimension of the sample space. van den Oord et (2018) improves the inference speed by allowing parallel computing. Compared our approach, they do not have the test-time adaptivity to computational constraints. In contrast, we design methods that allow trade-off's between generation speed and sample quality on-the-fly based on computational constraints. For example, running apps can accommodate to the real-time computational resources without model re- training. In addition, they can be combined together with our method without sacrificing sample quality. Specifically, Ramachandran et al.] (2017) leverages caches speed up autoregressive sampling, which can be directly applied to our autoregressive model on ordered codes without affecting sample quality. van den Oord et al. (2018) proposes probability density distillation to distill autoregressive models
8

---

Published as a conference paper at ICLR 2021
into fast implicit generators. We can apply the same technique our latent autoregressive model to allow a similar speedup.
In order to enable anytime sampling, our method requires learning an ordered latent representation of data by training ordered autoencoders. [Ripeel et al. (2014) proposes a generalization of Principal Components Analysis to learn an ordered representation. Instead of the uniform distribution over discrete codes in our method, they adopted geometric distribution over continuous codes during the training of the ordered autoencoders. Because of the difference they require additional tricks such as unit sweeping and udaptive regularization coefficients to stabilize the training, while our method is more stable and scalable. In addition, they only focus fast retrieval and image compression. By contrast, we further extend our approach to autoencoders with discrete latent codes (e.g.. VQ- VQ-V and explore their applications in anytime sampling for autoregressive models. Another work related to our approach is hierarchical nonlinear PCA (Scholz Vigário 2002). We generalize their approach to latent spaces of arbitrary dimensionalityy, and leverage Monte Carlo estimations to improve the efficiency when learning very high dimensional latent representations. The denoising generative models proposed by Soong & Ermon (2019); Ho et al. (2020) progressively denoise images into better quality, instead of modeling images from coarse to fine like our methods. This means that interrupting the sampling procedure of diffusion models at an early time might lead to very noisy samples, but in our case it will lead to images with corrector coarse structures and no noise which is arguably more desirable.
line works draw connections between ordered latent codes and the linear autoencoders. Kunin et al.] (2019) proves that the principal directions can be deduced from the critical points of L2 regularized linear autoencoders, and [Bao al. (2020) further shows that linear autoencoders can directly learn the ordered, axis-aligned principal components with non-uniform L2 regularization.
CONCLUSION
Sampling from autoregressive models is an expensive sequential process that can be intractable when on a tight computing budget. To address this difficulty, we consider the novel task of adaptive autoregressive sampling that can naturally trade-off computation with sample quality. Inspired by PCA, we adopt ordered autoencoders, whose latent codes are prioritized based on their importance to reconstruction. We show that it is possible to do anytime sampling for autoregressive models trained on these ordered latent codes-tt may stop the sequential sampling process at any step and still obtain a complete sample of reasonable quality by decoding the partial codes.
With both theoretical arguments and empirical evidence, show that ordered autoencoders can induce a valid ordering that facilitates anytime sampling. Experimentally, we test our approach on several image and audio datasets by pairing an ordered VQ-VAE (a powerful autoencoder architecture) and a Transformer (an expressive autoregressive model) on the latent space. We demonstrate that our samples suffer almost no loss of quality (as measured by FID scores) for images when using only 60% to 80% of all code dimensions, and the sample quality degrades gracefully as we gradually reduce the code length.
ACKNOWLEDGEMENTS
We grateful Shengjia Zhao, Tommi Jaakkola and anonymous reviewers in ICLR for helpful discussion. We would like to thank Tianying Wen for the lovely figure. YX was supported by the HDTV Grand Alliance Fellowship. SE was supported by NSF (#1651565, #1 #1522054, #1 7333666). ONR (N00014- 19-1-2145), AFOSR (FA9550-19-1 19--0024),, Amazon AWS, and FLI. YS was partially supported by the Apple PhD Fellowship in AI/ML. This work was done in part while AG was Research Fellow at the Simons Institute for the Theory of Computing.

---

Published as a conference paper at ICLR 2021
REFERENCES
Bao, X., Lucas, Sachdeva, S., and Grosse, R. B. Regularized linear autoencoders recover the principal components, eventually. ArXiv, abs/2007.06731. 2020.
Bengio. Y. Léonard, N., and Courville, A. Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv preprint 130..3432 2013.
Donahue, C., McAuley, J. J., and Puckette, M. Adversarial audio synthesis. In ICLR, 2018.
Germain, M., Gregor, K., Murray, I., and Larochelle, H. Made: Masked autoencoder for distribution estimation. In ICML, 2015.
Ghosh, P., Sajjadi, M. S. M., Vergari, A., Black, M. J., and Schölkopf, B. From variational to deterministic autoencoders. ArXiv, abs/1903. 12436, 2020.
Guo, P., Ni, X., Chen, X., and Ji, X. Fast PixelCNN: Based on network acceleration cache and partial generation network. 2017 International Symposium Intelligent Signal Processing and Communication Systems (ISPACS), pp. 71-76, 2017.
Heusel, M., Ramsauer, H., Unterthiner, T., Nessler, B., and Hochreiter, S. GANs trained by a two time-scale update rule converge to a local nash equilibrium. In Advances in neural information procesingg systems, pp. 6626-6637, 2017.
Ho, J., Jain, A., and Abbeel, P. Denoising diffusion prohabilistic models. ArXiv, ab</2006. 1239, 2020.
Hochreiter, S. and Schmidhuber, J. Long Short- Term Memory, Neural Computation, 1.1173-1770, 1997.
Kalchhrenner, N., Espeholt, L.,, Simonyan, K., Oord, A. v. d., Graves, A., and Kavukcuoglu, K. Neural machine translation in lincar time. arXiv preprint arXiv: 1610. 10099, 2016.
Kalchhrenner, N., van Oord, A., Simonyan, K., Danihelka, Vinyals, O., Graves, A., and Kavukcuoglu, Video pixel networks. In Proceedings of the 34th International Conference on Machine Learning Volume 70, pp. 1771-1779. JMLR. org, 2017.
Kingma, D. and Welling. M. Auto-encoding variational bayes. In International Conference on Learning Representations, 2013.
Krizhevsky, A. Learning multiple layers of features from tiny images. 2009.
Kunin, D., Bloom, J. M., Goeva, A., and Seed, C. Loss landscapes of regularized linear autoencoders. ArXiv, abs/1901.08 08,00881888.1888 2019.
Liu, 7.,, Luo, P., Wang, X., and Tang, Deep learning face attrihutes the wild. 2015 IEEE International Conference on Computer Vision (ICCV), pp. 3730-3738, 2014.
Menick, and Kalchbrenner, N. Generating high fidelity images with subscale pixel networks and multidimen- sional upscaling. arXiv preprint arXiv:1812.0110 2018.
Oord, A. d., Dieleman, S., Zen, H., Simonyan, K., Vinyals, O., Graves, A., Kalchbrenner, N., Senior, A., and Kavukcuoglu, K. WaveNet: A generative model for audio. arXiv preprint arXiv: Fefi::660900.44 2016a.
Oord, A. v. d., Kalchbrenner. N., and Kavukcuoglu, K. Pixel recurrent neural networks. arXiv preprint arXiv:/601) 1601.0679, 2016b.
Radford, A., Wu. J.. Child, R., Luan, D., Amodei, D., Sutskever, Language models are unsupervised multitask learners. OpenAl Blog, 1(8)99 2019.
Ramachandran, P., Paine, T. L.,, Khorrami, P. Babacizadeh, M., Chang, S., Zhang, Y., Hasegawa-Johnson, M. A., Campbell, R. H., and Huang, T. S. Fast generation for convolutional autoregressive models. ArXiv, abs/1704.06001 2017.
Razavi, A., van den Oord, A., and Vinyals, O. Generating diverse high-fidelity images with VQ-VAE-2. In Advances Neural Information Processing Systems, pp. 14837-14847, 2019.
Rippel, O., Gelbart, M. A., and Adams, R. P. Learning ordered representations with nested dropout. In ICML, 2014.
Salimans, T., Karpathy, A., Chen, X., and Kingma, D. P. PixeICNN+: Improving the PixcICNN with discretized logistic mixture likelihood and other modifications. arXiv preprint 1711001701.05517, 2017.
Scholz, M. and Vigário, R. Nonlinear PCA: hierarchical approach. ESANN, 2002.
10

---

Published as a conference paper at ICLR 2021
Song. Y. and Ermon, S. Generative modeling by estimating gradients of the data distribution. ArXiv, abs/1907.05600, 2019.
Szegedy. C., Vanhoucke, loffe. S., Shlens, J., and Wojna, Z. Rethinking the inception architecture for computer vision. 2016 IEEE Conference Computer Vision and Puttern Recognition (CVPR), pp. 2818-2826, 2016.
van den Oord, A., Kalchbrenner, N., Espeholt, L.,, Kavukcuoglu, K., Vinyals, O., and Graves, A. Conditional image generation with PixelCNN decoders. In NIPS, 2016.
den Oord, A., Vinyals, O., and Kavukcuoglu, Neural discrete representation learning In NIPS, 2017.
den Oord, A., Li, Y., Babuschkin, I,, Simonyan, K., Vinyals, O., Kavukcuoglu, K., van den Driessche, G.. Lockhart, E., Cobo, L. C., Stimberg. F., Casagrande, N., Grewe, D., Noury, S., Dieleman, S., Elsen, E., Kalchbrenner, N., Zen, H., Graves, A., King. H., Walters, T., Belov, D., and Hassabis, D. Parallel WaveNet: Fast high-fidell fidelity speech synthesis. ArXiv, abs/17111 2018.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. Attention is all you need. In Advances in neural information processing systems, pp. 5998 6008, 2017.
Veaux, C., Yamagishi, J., and Macdonald, K. Cstr vetk corpus: English multi-speaker corpus for cstr voice cloning toolkit. 2017.

---

Published as a conference paper at ICLR 2021
A PROOFS
A.1 PROOF FOR THEOREM
Proof. For simplicity we denote the distribution of the stochastic part (first dimensions) of
Tea [2) x) as Qey (=g](x), and similarly we denote pdg (x(z) as Pdg (x) =g)) We first reformu-
late the objective
L -
Barq, ( (xxx) Pa, pa,, gil
(x) (x)
K
K
/ (25x)) log (x) (xxzss)
K
==1
1
f (2g/) log dea (xl )xx2zgi
(8)
K
The inequality {8) holds because KL-divergencess are non-negative. Under the assumption of an optimal decoder Ø we can achieve the equality in (8), in which case the objective equals
K
Geo (251, x) log Lea (x, 251)
C
dxdzzi
K
qeo (z<i)
We define the following modified objective by adding the data entropy term, since it is constant independent of
1
qea (zgs; log Lep (x, 2gi) dxdzzg Tea (2<1)pa((>)
L =
K
-1
(xx; agi)
K
If there exists integer i E {2, ....... K) such that x(x;x|2<(_1) > 1(2,-: x|=3)_)) we can
exchange the position of 2; and 2 increase the value of objective (9) By the chain rule of mutual information we have:
1(x: 2,, 2g) = - +12;
=
+ [z (2
When [22; [ (2(-2)))) we can show that I [xx: 24, Z51-2) > [(x; 2g112
I
[(2; [ (
[(z==1; - 1 1(-
1xx zi- 1 2)= [(x; z 1
(10)
(=:2211/25-)) 2 0,
(11)
where Eq.
10 holds by the chain rule of mutual information:
[[
(xx 2 [[2 2 x, 25) and [ 2, |x, 25:-2) by the conditional in- dependence assumption 1 2/-1 Zg:-2. Hence if we exchange the position of z; and 2 of the latent vector show that the new objective value after the position switch is strietly smaller
12

---

Published as a conference paper at ICLR 2021
than the original one:
((
Σ [(x
K
[(x; z<6) +
+
Σ (xx;
(12)
K
k=i
K
(xx agk).
K
k=
Inequality 12 holds by [xx 2,, 2c)-2) [(x; 2;-1, zgx-2). From above conclude that if the encoder is optimal, then the following inequalities must hold:
Vi E (2, ... KK [2; (2-11x
Otherwise we can exchange the dimensions to make the objective Eq. p smaller, which contradicts the optimally of encoder eq.
B AUDIO GENERATION
Fracton d'l cedeleght
Frecta langh
lerges
-62
2010
800 1000 THR SADE 190
1200 1400 1e00s
281
400 30
1303 1200
1AV0 TAICE
(a) Waveforms sampled from unordered VQ-VAE
Fracten of ceees
Practss felcow lestve
Poeeier of Towe tegget
-22
25
-050
-54
(b) Waveforms sampled from ordered VQ-VAE
Figure 6: Anytime sampling with 0.0625/0.2511.0 (left to right) fractions of full code length on VCTK dataset.
Our method can also be applied audio data. We evaluate anytime autoregressive models the VCTK dataset (Veaux et al. 2017). which consists of speech recordings from 109 different speakers. The original VQ-VAE uses an autoregressive decoder, which may cost more time than the latent autoregressive model and thus cannot be accelerated by anytime sampling. Instead, we adopt non-autoregressive decoder inspired by the generator of WaveGan (Donahue et al. 2018). Same as images, we train Transformer model on the latent codes.
We compare waveforms sampled from ordered vs. unordered VQ- VA-V in Fig. 6 and provide links to audio samples in Appendix G.2 By inspecting the waveforms and audio samples, we observe that the generated waveform captures the correct global structure using few 6.25% of the full code length, and gradually refines itself as more code dimensions are sampled. In contrast, audio samples from the unordered VQ-VAE contain considerably more noise when using truncated codes.
13

---

Published as a conference paper at ICLR 2021
C ADDITIONAL EXPERIMENTAL RESULTS
C.I ORDERED VERSUS UNORDERED CODES ON VAE
To better understand the effect of order-inducing objective, we disentangle the order-inducing objective Eq. (6) with the specific implementation on VQ-VAE, such as stop_gradient operator and quantization. We adopt similar order-inducing objective standard VAE:
K
(x))
Bazqn (z)x) Pag (x(2) + KT (2) x) (ull))))
(13)
where Geo (z) x) denotes the distribution of (z1, 22, ,,, 00¹ E I geo goo x), and Pd, (x g) represents the distribution of pa, (x (2, 24, 0, .0T E RR). We set the prior p [z) the i dimensional unit normal distribution.
We repeat the experiments CIFAR-10 10 and observe similar experimental results between VQ-VAE and standard VAE. Fig. (1a) shows that the standard VAE has irregular At)), while the ordered VAE has much better ordering latent codes. Fig. ( further shows that the ordered VAE has better reconstructions under different truncated code lengths. The experimental results are consistent with Fig. 3(a) and Fig. 3(b)
Squared reconstruction error
200
Unordered VAE
Unordered VAE
40
Ordered VAE
150
Ordered VAE
PCA
PCA
A()
100
20
50
0
20
40
60
20
40
60
Code length
Code length
(a)
(h)
Figure Ordered versus unordered code on standard VAE.
C.2 ABLATION STUDY ON AUTOREGRESSIVE MODEL
We study the performance of different autoregressive model on ordered codes. We compare Trans- former (Vaswani al. 2017). PixeICNN (Oord et al. 2016b) and LSTM (Hochreiter & Schmidhuberi 1997). PixeICNN adopts standard 2D convolutional layers to model the conditional dependence. In order to enlarge the receptive field, PixeICNN stacks many convolutional layers. Transformer applies attention mechanism and feed forward network to model the conditional dependence of ID sequences. LSTM uses four different types of gates to improve the long-term modeling power of the recurrent models on ID sequences.
Transformer and LSTM can be naturally applied to the ID channel-wist quantized codes. Since PixeICNN operates 2D data, we reshape the ID codes into 2D tensors. More specifically, for 70-dimensional ID codes on CIFAR-10 10, we firstly pad the codes into 81 dimensions then reshape into 9 x 9 tensors. Fig. shows the FID scores of different autoregressive model on CIFAR- 10 dataset. The results show that PixeICNN has inferior performance in all cases except when used with 0.2 fractions of full code length. This is because PixeICNN works well only when the input has strong local spatial correlations, but there is no spatial correlation for channel-wise quantized codes. In contrast, autoregressive models tailored for ID sequences work better on channel-wise dequantized codes, as they have uniformly better FID scores when using 0.4/0.6/0.8. 6/0.8/1.0 8/1.0 fractions of full code length.
14

---

Published as a conference paper at ICLR 2021
C.3 ABLATION STUDY ON SAMPLING DISTRIBUTION
We study the effect of different sampling distributions in order-inducing objective Eq. We compare the adopted uniform distribution with the geometric distribution used in Rippel et al. (0044) on CIFAR-10, as shown in Fig.
[(b) We normalize the geometric distribution on finite indices with length K, i.e. Pr(i = k) = p) [
i E (1. }), distribution Geo(p). Note that when p O, Geo(p) recovers the uniform distribution.
and denote the normalized geometric
Fig. shows that OVQ-VAES trained with all the different distributions can trade off the quality and computational budget. We find that OVQ-VAB is sensitive to the parameter of the geometric distribution. The performance of DVQ-VAE with Geo(0.03) is marginally worse than the uniform distribution. But when changing the distribution to Geo(O.1) ) the FID scores become much worse with large code length (0.6/0.8/1.0 fractions of the full code length). Since for i ~ Geo(p), Pr(i 2 t) = (1 p)- (1 (1- (1 p) - /1(1- (1 - p) " < (1 - p)- which indicates that the geometric distribution allocates exponentially smaller probability code with higher index.
CIFAR-10
CIFAR-10
120
0.100
120
(0.03)
(0. (.03)
Score
100
Transformer PixelCNN
Probability
0.075
Uniform
(0.1)
FID Score
100
Uniform
Geo (0.1)
80
0.050
80
0.025
0.000
0. 0.25
0.50
0.75
1.00
0
20
40
80
0. 0.25
0.50
0.75
1.00
Fraction of full code length
Code index
Fraction of full code length
Figure 8: (a): FID scores for different autoregressive models on ordered codes; (b): Different sampling distribution for ordered codes; (c): FID scores for anytime sampling on different distributions.
C.4 ON THE REGULARIZATION EFFECT OF ORDERED CODES
Imposing an order on latent codes improves the inductive bias for the autoregressive model to learn the codes. When using full codes on CIFAR-10 dataset, even though the OVQ-VAL has higher training error than unordered VQ-VAE, better FID score is achieved by the ordered model. This validates the intuition that it is easier to model an image from coarse to fine. These results are corroborated by lower FID scores for the anytime model with full length codes under different number of training samples. As shown in Fig. (a) the ordered model has an increasingly larger FID improvement over the unordered model when the dataset becomes increasingly smaller. These results indicate that training on ordered codes has regularization effect. We hypothesize that ordered codes capture the inductive bias coarse-to coarse-to-fine tonfine image modeling better.
C.5 COMPARISON TO TALORED VQ-VAE
We compare the anytime sampling to the unordered VQ-VAB with tailored latent space (Tailored VQ- (Q-VAE) on CIFAR-10. The Tailored VQ-VAE has a pre-specified latent size, using the same computational budget as truncated codes of anytime sampling. For fair comparison, we experiment with transformers on the latent space of Tailored VQ-VAE. Fig. Fig shows that anytime sampling always has better FID scores than Tailored VQ-VAE, except when the code is very short. We hypothesize that the learning signals from training the full length codes with OVQ-VAE improves the quality when codes are shorter, thus demonstrating a FID improvement over the Tailored VQ- VAEV Moreover, OVQ-VAV VAE has the additional benefit of allowing anytime sampling when the computational budget is not known in advance.
shows
15

---

Published as a conference paper at ICLR 2021
D TRAIN AUTOREGRESSIVE MODEL ON PCA REPRESENTATION
An alternative way to induce order on the latent space is by projecting data onto the PCA representa- tion. However, we encounter limited success in training the autoregressive model the top of PCA representation.
When training an autoregressive model on PCA-represented data, we observe inferior log-likelihodds. We first prepare the data by uniformly dequantizing the discrete pixel values continuous ones. Then we project these continuous data into the PCA space by using the orthogonal projection matrix composed of singular vectors of the data covariance matrix. Note that this projection preserves the volume of the original pixel space since the projection matrix's 's determinant is so bigliiklssoods of model trained on the raw continuous data space and the PCA projected space comparable. We report the bits/dim (lower better), which is computed by dividing the negative oog-likelihood (log base 2) by the dimension of data. We train transformer models on the projected space and the raw data space. Surprisingly,
MNIST, the transformer model obtains 1.22 bits/dim on the projected space versus 0.80 bits/dim on the raw data, along with inferior sample quality. We hypothesize two reasons. First, models have been tuned with respect to inputs that are unlike the PCA representation, but rather on imputs such as raw pixel data. Second, PCA does not capture multiple data modalities well, unlike OVQ-VAE. Moreover, autoregressive models typically do not perform well on continuous data. In contrast, Transformer model operates on discrete latent codes of the VQ-VAE.
CIFAR-10
CIFAR-10
120
Anytime unordered
Tailored VQ-VAE
60
Anytime + ordered
Anylime ordered
FID Score
FID Score
100
55
80
60
50
30000
40000
50000
20
40
60
Number of training samples
Code length
(b)
Figure 9: (a) FID scores for anytime sampling using various numbers of training samples. (b) FID scores with different computational budgets.
E EXTRA IMPLEMENTATION DETAILS
Our code is released via the anonymous link holp://t////oooomouss.okk 4open abcl-0f77 (ocoo/11224447dll and included in the supplementary material well. Below introduce more details on network architectures and the training processes.
www.aayaooooooooooeoeeeeeeeee//e scicncc/r///444//66 -1881//8999998888888888888--888 8198-48361
E NETWORKS
For MNIST dataset, the encoder has 3 convolutional layers with filter size (4,4,3) and stride 12,2,1) respectively. For CelebA and CIFAR- 10 datasets, the encoder has 4 convolutional layers with filter size (4.4,4.3) and stride (2,2,2,1) 1) respectively. The decoders for dataset above are the counterpart of the corresponding encoders. For VCTK dataset, we use encoder that has 5 convolutional layers with a filter size of 25 and stride of 4. The activation functions are chosen to be LeakyRelu-0.2. We adopt decoder architecture which has 4 convolutional and upsampling layers. The architecture is the same with the generator architecture in Donahue et al. (2018) except for the number of layers.
For all the datasets, we use a 6-layer Transformer decoder with an embedding size of 512, latent size of 2048, and dropout rate of 0.1. We 8 heads in multi-head self-attention layers.
16

---

Published as a conference paper at ICLR 2021
E.2 IMAGE GENERATION
The FID scores are computed using the official code from TTUR (Heusel et al. 2017 authors. We compute FID scores on CIFAR-10 and CelebA based on total of 50000 samples and 100000 samples respectively.
We pre-train the VQ-VAE models with full code lengths for 200 epochs. Then we train the VQ-VAE models with the new objective Eq. (6) for 200 more epochs. We use the Adam optimizer with learning rate 1.0 x 10-3 for training. We train the autoregressive model for 50 epochs on both MNIST and CIFAR-10, and 100 epochs on CelebA. We use the Adam optimizer with a learning rate of 2.0 x 10-3 for the Transformer decoder. We select the checkpoint with the smallest validation loss on every epoch. The batch size fixed to be 128 during all training processes.
E.3 AUDIO GENERATION
We randomly subsample all the data points in VCTK dataset to make all audios have the same length (15360). The VQ-VAE models are pre-trained with full code length for 20 epochs, and then fine-tuned with our objective Eq. (6) for 20 more epochs. We use the Adam optimizer with learning rate 2.0 10-4 for training the VQ-VAE model. We train the Transformer for 50 epochs on VCTK, use the Adam optimizer with a learning rate of 2.0 x 10-3, We select the checkpoint with the smallest validation loss every epoch. The batch size is fixed to be 8 for the VQ-VAE model and 128 for the Transformer during training.
F SAMPLES ON THE SAME PRIORITY CODE
As further illustration of the ordered encoding, show in Fig. 10 the result of full code length sampling when the first (highest priority) discrete latent code is fixed. The fixing of the first latent code causes anytime sampling to produce wide variety of samples that share high-level global similarities.
771
7776
7
7
7
7
7
7
9
9
4
4
9
9
9
4
9
7
7
7
7
7
7
7
4
q
4
9
9
9
4
9
Figure Samples sharing the highest priority latent code.
G EXTRA SAMPLES
G.1 IMAGE SAMPLES
We show extended samples from ordered VQ-VAEs in Fig. we also provide samples from unordered in Fig Fig. 15
Fig.
12
and Fig.
13
For comparison,
and Fig 16
G.2 AUDIO SAMPLES
We include the audio samples that sampled from anytime sampler in the supplementary material. The audi o audio_based i ne directory contains 90 samples from ordered unordered VQ-VAEs respectively. The fractions of full code length (0.0625, 0.25 and 1.0) used for generation included in the names of wav files.
https//githhh.ccm//onff////UUU
17

---

Published as a conference paper at ICLR 2021
7
/
4
9
9
4
3
3
7
6
6
6
5
7
2
0
9
5
3
9
9
0
1
0
9
6
3
8
4
9
0
9
/
/
9
0
9
9
6
3
6
5
3
4
4
4
5
2
6
2
5
0
0
1
7
6
6
6
6
2
f
0
9
8
6
0
0
9
1
6
O
7
/
3
6
2
3
4
/
3
4
6
3
3
5
3
7
8
7
3
2
7
3
7
/
7
6
2
7
8
8
O
5
6
3
(a) 0.25 fractions
code length
9
/
4
9
4
3
3
7
d
6
6
5 2
7
2
0
9
5
3
9
4
0
1
0
9
6
6
8
4
9
0
9
/
/
9
0
9
9
4
5
3
6
5
3
4
4
4
5
2
6
2
5
0 007
0
4
7
5
6
6
5
2
f
0
8
4
8
6
0
6
9
1
9
6
O
7
9
3
6
2
3 2
4
/
3
4
6
3
3
5
3
9
8
7
3
7 3
3
9
/
7
2
7
8
8
0
5
6
(b) 0.5 fractions of full code length
7
9
/
4
9
9
4
3
3
7
6
6
5 2
7
2
0
9
5
3
9
4
0
/
0
9
6
6
8
4
9
0
9
4
/
9
0
9
9
4
5
3
6
5
3
+
4
4
5
2
6
2
5
0
O 7
4
7
5
6
6
5
2
f
0
4
8
6
007
6
9
/
4
6
O
7
9
9
3
6
2
3
6
4
/
3
4
6
3
5
r
3
9
8
7
3
2
7 3
3
9
/
7
6
6
2
7
8
8
O
5
6
(c) 0.75 fractions full code length
7
9
1
4
9
9
4
3
3
7
6
5 2 1 0 607
6
7
2
0
9
5
3
9
4
0
/
|
0
6
6
8
4
9
0
9
#
/
0
9
9
4
5
3
6
8
6
5
3
7
4
1
4
5
2
/
6
2
5
0
4
7
5
6
5
|
2
0
/
4
8
0
6
9
6
0
9
9
3
6
2
3
6
4
/
3
4
6
5
r
3
9
8
7
3
2 6
7 3
3
9
/
7
6
2
7
/
8
8
O
5
(d) 1.0 fractions of full code length
Figure 11: Anytime sampling with 0.25/0.550.0 5/0.1/ (top to bottom) fractions of full code length from ordered VQ-VAEs on MNIST.
18

---

Published as a conference paper at ICLR 2021
(a) 0.25 fractions full code length
(b) 0.5 fractions of full code length
(c) 0.75 fractions full code length
(d) 1.0 fractions of full code length
Figure 12: Anytime sampling with 0.25/0.5/0.72 5/0.1/000 (top to bottom) fractions of full code length from ordered VQ-VAEs on CIFAR-10.
19

---

Published as a conference paper at ICLR 2021
(a) 0.25 fractions code length
(b) 0.5 fractions of full code length
(c) 0.75 fractions code length
(d) 1.0 fractions full code length
Figure 13: Anytime sampling with 0.25/0.5/0. 75/1.0 (top to bottom) fractions of full code length from ordered VQ-VAEs on CelebA.
20

---

Published as a conference paper at ICLR 2021
2
4 7
7
3
/
4
4
0
6
4
2
3
3
1
X
5
6
O
E
7
4
9
5
/
5
4
6
6
/
S
5
3
q
2
3
0
9
P
6
9
0
O
6
4
<
f
4
5
2
O
O
5 2 8
0
I
I
?
5
7
4
1
2
O
3
h
a
s
7
4
7
6
5
5
2
1
7
y
3
7
/
4
G
7
0
2
5
6
2
7
(a) 0.25 fractions full code length
2
4
9
3
4
4
0
6
4
4
3
7
7
/
3
7
9
6
/
/
O
S
7
5
3
5
(
5
6
4
6
/
5
5
3
9
2
3
0
9 9
1
8
a
9
0
2
6
4
4
8
3
4
8
2
9 7
0
0
5
0
7
/
/
9
3
5
9
9
1
2 2
2
Q
3
6
4
5
7
7
6
5
/
5
7
/
O
/
3
2
1
4
4
7
5
9
6
6
0
7
4
(b) 0.5 fractions of full code length
2
9
9
9
6
4
4
0
6
4
4
3
7
7
3
7
3
6
/
/
O
8
5
7
5
8
5
/
5
4
6
/
5
8
5
3
9
2
3
6
9
8
8
9
0
2
4
4
8
3
4
3
2
5
9
0
0
/
5
7
/
9
3
5
9
7
9
2
2
0
8
6
5
1
2
2
6
5
/
5
2
4
7
/
O
9
/
3
2
1
4
4 6
G
7
0
O
5
1
9
7
6
O
2
7
5
4
(c) 0.75 fractions full code length
2
9
9
7
6
4
4
2
6
4
4
7
7
/
3
7
6
/
O
4
7
5
3
5
/
7
5
4
6
4
6
5
9
9
3
9
1
8
3
6
9
/ 9 7
0
8
9
0
2
6
4
4
8
3
4
9
3
2
9
0
0
/
5
0
/
7
9
9
3
5
9
/
9
0
2
2
0
8
6
5
7
2
2
6
5
/
5
2
7
1
7
O
9
/
3
2
4
4
0
7
0
5
9
9
4
O
2
5 2
6
(d) 1.0 fractions of full code length
Figure 14: Anytime sampling with 13300.5/0.75// (top to bottom) fractions of full code length from unordered VQ-VAEs on MNIST.
21

---

Published as a conference paper at ICLR 2021
(a) 0.25 fractions full code length
(b) 0.5 fractions of full code length
(c) 0.75 fractions full code length
(d) 1.0 fractions of full code length
Figure 15: Anytime sampling with 0.25/0.5/0.755 5/0.75/1.0 (top to bottom) fractions of full code length from unordered VQ-VAEs on CI.
22

---

Published as a conference paper at ICLR 2021
(a) 0.25 fractions code length
(b) 0.5 fractions of full code length
(c) 0.75 fractions code length
(d) 1.0 fractions full code length
Figure 16: Anytime sampling with 0. 0.25/0.5/0.75// (top to bottom) fractions of full code length from unordered VQ-VAEs on CelebA.
23


Reviews:
[{"review_id": "iBCLgmdtcuh", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Summary\nThe paper considers the problem of slow sampling in autoregressive generative models. Sampling in such models is sequential, so its computational cost scales with the data dimensionality. Existing work speeds up autoregressive sampling by caching activations or distilling into normalizing flows with fast sampling. Authors of this work instead propose a method that returns (approximate) samples given an arbitrary computational budget, a behaviour referred to as *anytime sampling*. The proposed model is based on VQ-VAE by van den Oord et al. (2017), where an autoregressive model is fit to a latent space of a trained discrete autoencoder, rather than to raw pixels. Authors adapt the *nested dropout* idea by Rippel et al. (2014) to encourage the discrete autoencoder to order latent dimensions by their \"importance\" for reconstruction. Experiments demonstrate that the ordered latent space allows to stop the autoregressive sampling process at an arbitrary latent dimension and still obtain \"complete\" samples. The quality of samples increases as more latent dimensions are sampled, which allows to trade sample quality for reduced computational cost.\n\n# Strong points\n- The considered problem is important, and the authors' novel framing of it is well-motivated: being able to adapt to available computational budget is potentially useful in practical applications of autoregressive generative models.\n- The proposed method is well-motivated and its introduction is self-contained. The idea to use incomplete samples from an autoregressive model with a representation model that *expects* such incomplete representations is interesting and novel. \n- Experiments are designed appropriately to showcase the resulting behaviour of the model. Experimental setup is explained in sufficient detail.\n- Section 4.3 is well done: an easy-to-understand motivation for a proposed architectural change, with a clear empirical demonstration of its effect.\n\n# Weak points\n- Apart from channel-wise quantization, authors change the autoregressive model used in the original VQ-VAE. Authors argue that the used model is \"more suitable to channel-wise quantization\". While the motivation sounds reasonable, it relies on the knowledge of the inner workings of the PixelCNN and Transformer models. Including a concise description of both types of models would solidify the motivation. Moreover, an ablation experiment with alternative autoregressive models (at least PixelCNN and Transformer) would be useful to support the choice, and to learn about what autoregressive models are suitable (or not suitable) for channel-wise quantization.\n- One peculiar outcome of experiments on CIFAR-10 is that a better FID score is achieved by the ordered model in comparison to the unordered one *even when sampling the full code*. This is counter-intuitive, and is not observed in CelebA experiments. Is the ordering regularizing the autoencoder somehow on the smaller CIFAR-10 dataset? Is something else going on? This phenomenon is worth exploring further to strengthen the evaluation.\n- It's unclear how the proposed method compares to other methods for speeding up sampling in autoregressive models. Authors could argue that other methods do not allow for adaptive sampling and hence the comparison is not justified. But it would be useful to know how much sample quality we sacrifice with anytime sampling to achieve the speed up of the methods by Ramachandran et al. (2017) or van den Oord et al. (2018).\n- Authors correctly point out that the computational cost of standard autoregressive sampling scales (at least) linearly with the input dimension. This is not the case when using *ex-post density estimation*, where it scales with the latent code dimensionality. It would be useful to know how anytime sampling compares to simply reducing the size of the latent code of the auto-encoder. In other words, what is the effect of tailoring the latent code size to a specific computational budget (if one is known in advance), as compared to anytime sampling with the same budget?\n- The *ordered autoencoder* is a special case of the *nested dropout* idea proposed by Rippel et. al (2014), where $p_B$ is taken to be a uniform distribution. I wish authors explored/discussed this connection more. Why is the uniform distribution chosen, as opposed to the geometric distribution as in the original work? Why is the original motivation for using the geometric distribution not applicable in this work?\n- While the theoretical analysis in 3.1.1 is interesting, I am wondering about its significance. Authors claim that Rippel et al. (2014) limit their analysis to a linear (ordered) autoencoder. However, I'd like to point out section 2.1 in the original paper, which demonstrates how exactly the training objective encourages latent dimensions to be sorted according to their \"mutual information\" gain. How does the offered line of reasoning relate to the one by Rippel et al., and why have authors decided to not rely on the existing analysis?\n- The related work section could use some work. Authors should make it clearer that they consider a special case of the idea by Rippel et al., instead of referring to it as a \"similar method\", and consider moving the second paragraph to earlier sections, given how much the proposed method relies on the earlier idea. Finally, it's not clear how exactly the references in the last paragraph are relevant to this work.\n\n# Minor points\n- The remark on p7 highlights an interesting observation, but is too brief to introduce the setup properly. Consider moving it to the appendix, providing more detail on e.g. the number of principal components used or what exactly is measured in bits/dim.\n- The reference for MADE in section 2 is incorrect. Change to \"MADE: Masked Autoencoder for Distribution Estimation\" by M. Germain, K. Gregor, I. Murray, H. Larochelle, 2015.\n- The core evaluation metric (FID) should be defined beyond saying that it's \"a popular metric on image quality\". How exactly is it computed? And, importantly, *are we looking for a higher or a lower number?*\n- The `stop_gradient` operation should be defined.\n- Figure readability isn't great: a larger font (try make comparable to text font size) and thicker lines will help.\n- Try to use consistent labels in figures: the proposed method is at various points referred to as a \"OVQ-VAE\", \"Anytime + ordered\", \"Ours\".\n- References: use proper capitalization (\"Gan\", \"pixelcnn\", etc.), deal with repeated references (see Heusel 2017a/b).\n- Formatting: reduced spacing above conclusion section header?\n- Notation in 4.1: $z_{e,j}$ is confusing notation, consider renaming the variable to avoid having to use the comma.\n- Poor phrasing: \"our training is stable and more suitable for large scale training\", \"for the instantiation\".\n\n# Recommendation\nTo summarize above, I find the proposed method interesting and well-motivated. The components of the method aren't new, but the idea to combine autoregressive models with ordered representations in \"ex-post density estimation\" for anytime sampling is novel. Applying the nested dropout idea to VQ-VAE required some technical work. Authors have identifying a sensible set of experiments that showcase the resulting behaviour. \n\nOn the other hand, several loose threads have been left by the authors, potentially leaving the reader with questions regarding the results. More experiments (as suggested above) would help solidify the results, giving the reader a better idea about what makes the proposed method work and adding weight to the paper. The theoretical contribution could be better motivated, and put in context of existing work. The write-up itself could use some work, as also suggested above.\n\nAll in all, I find the paper in its current form to be somewhat below the standard for ICLR acceptance, unless authors address some of the points above. \n\n# Random questions/comments\n- \"Progressive generation\" is another potential application of this idea: a user can be presented with intermediate generations that progressively increase in quality, instead of waiting for the one final generation (think progressive JPEG).\n- Have you considered sorting dimensions of a pre-trained, standard VQ-VAE? For example, by going through dimensions in turn and greedily picking the one that most reduces reconstruction error? \n- In Fig 3a the OVQ-VAE curve goes up a few times. Do you explain this by optimization not fully converging?\n- The changing MNIST digit class in Figure 7 is surprising. I would expect this to be stored in the highest priority part of the latent code, given its high impact on reconstruction. Is this a consistent effect?\n\n-----\n\nEDIT:\n\nI thank the authors for their detailed response. I also appreciate the effort that's been put into refining the draft and undertaking the additional experiments. Most of the points I've raised have been addressed. The manuscript has been made more self-contained. Additional material on autoregressive models suitable for channel-wise quantization and the inductive bias of ordered representations is especially useful. As a result, I've increased my score.\n\nUnfortunately, I don't feel my concerns re. paper's relationship with Rippel et. al's work have been fully addressed. It is still my understanding that the role of the analysis in 3.1 is to add rigour to the otherwise similar general argument in 2.1 of Rippel et. al. While more rigour is always good, in this case it doesn't lead to new insights, and feels tangential to the rest of the paper. As such 3.1 could be moved to the appendix, which will also help making the page limit.\n\nIn addition, I am still not fully happy with how Rippel et. al's work is discussed. A reader not fully familiar with the earlier work might get an impression that it's simply a worse version of the proposed method. It's important to make it clear that the considered method extends the work by Rippel et. al's, applying nested dropout to an autoencoder that is discrete and \"variational\" (arguable), and considering a different application. This would not diminish the importance of this work, but would give credit where it's due.\n\nOverall, following author's response I am leaning towards acceptance, but will let the AC judge the importance of the points above for the final decision.", "extra_scores": {}, "extra_text": {}}, {"review_id": "dtixJMfC3a", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose a novel way to trade off sample quality with computational budget in autoregressive models by performing the autoregression on the ordered latent space of a generative model. They show analytically and empirically that the tradeoff is monotonic and that it approaches the full performance at increasing computational budgets.\n\nMajor comments:\n- I appreciate the application to VQ-VAEs, since in this model, the autoregressive component already plays a major role. However, I was wondering whether a toy experiment on normal VAEs (without discrete latent space) could be more easily controllable and disentangle the idea of the paper (ordered latent space autoregression) from all the problems of training discrete models (straight-through estimator, gradient stopping, etc.). Maybe something like Fig. 3 on a standard VAE could be helpful.\n- If I understand correctly, the VQ-VAE in the experiments uses a latent PixelCNN, while the OVQ-VAE uses a Transformer. It is a bit hard to see how much of the performance is due to this difference. I think it would be a fairer comparison to also include a standard VQ-VAE with latent transformer, as an ablation to see how much of the effect is really due to the ordered latent space.\n\nMinor comments:\n- Sec. 1, last paragraph: autoregerssive -> autoregressive\n- Sec. 6, second paragraph: Instead of uniform distribution -> Instead of the uniform distribution\n- In front of Sec. 7, there seems to be a negative \\vspace that shouldn't be there\n\nSummary:\nI think the idea of this paper is very intriguing and the theoretical results are convincing. However, the experiments are currently not completely satisfying, because there is no simple VAE toy experiment and no ablation study of a VQ-VAE with latent Transformer and unordered latent space.", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZUHv4pFDotG", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "#### Summary\n\nFor me the paper doesn't have any really major negatives. It is straightforward and makes sense, but it also didn't have anything that jumped out to me as super exciting, surprising or interesting, hence the marginal accept.\n\n#### Review\nThe paper studies the task of generative modelling with what is referred to as 'anytime sampling', that is sampling with graceful early stopping, where computation time can be traded off with sample quality. The approach taken is to adapt the VQ-VAE, imposing an ordering on latent dimensions, using a kind of dropout which effectively weights the latent dimensions differently in the objective function. The latent dimensions have a fixed ordering, and those which are early in the sequence are forced to have more explanatory power than later dimensions. Experiments are presented which demonstrate that the method basically works for images and audio, in that sample quality degrades gracefully with computational budget.\n\nThe most serious criticism I have is that I felt that little attention was given to motivating the problem. The paper seemed to assume a priori that anytime sampling is interesting and/or relevant to real-world applications. If that is so then I'm surprised there hasn't been more work addressing it. Could the authors add some more detail on their motivations for working on this, perhaps including specific examples of use-cases? Compression was mentioned very briefly near the end of the paper when discussing related work. This seems like a natural application to me, and indeed what's referred to as 'progressive decoding' in the compression community is a common feature of modern codecs. The authors don't seem to be interested in the compression use case, so why are they working on this, and why should I care?\n\nI'm by no means an expert on the niche topic of anytime sampling, but there are a few papers which I think are sufficiently closely related that they should be mentioned. Firstly https://arxiv.org/abs/2007.06731 would fit neatly in the last paragraph of Section 6. Denoising diffusion probabilistic models (https://arxiv.org/abs/2006.11239 and https://openreview.net/forum?id=-NEXDKk8gZ) also allow trading off computational budget with sample quality, although obviously the approach is very different and this task/trade-off is not the focus of those papers.\n\n#### Typos and other nits\n - Second paragraph of page 2, autoregressive is mis-spelled in the first line.\n - Latent vectors are transposed, why?\n - First paragraph of Section 4, last sentence says '...with small change of the original VQ-VAE...', that should either be 'with a small change to the original VQ-VAE' or 'with small changes to the original VQ-VAE'.\n - Under 'Remark' in Section 5.2.1, reference is made to 'the PCA distribution'. I don't think this is a well defined concept - PCA is not a probabilistic method and does not correspond to a probability distribution (see e.g. https://rss.onlinelibrary.wiley.com/doi/abs/10.1111/1467-9868.00196 for more detail).", "extra_scores": {}, "extra_text": {}}, {"review_id": "CfH62C-LJJs", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThe authors explore the use of anytime sampling to allow sampling from autoregressive models on a fixed computational budget.\nThey introduce the problem formulation, and show how how to learn a latent space where the amount of information conveyed decreases consistently with a given ordering on the dimensions (in a manner reminiscent of PCA),\nThey then show how this can be applied to VQ-VAE to perform anytime sampling of the (discrete) latent code. The latent code can then be decoded in a fixed amount of time/computation.\n\nStrengths:\n* The authors tackle a problem that is impactful but not very well-studied in the community, and propose a novel approach to do so.\n* The proposed method is well-explained.\n\nWeaknesses:\n* Experimental evalution could be more thorough. \n    (1) Is there any related work on this topic (or simple baselines) that are worth comparing too?\n    (2) The authors use the FID metric to evaluate the perceptual quality of their generated images, at different sampling budgets. My understanding is that FID was developed for GANs, which do not allow for a tractable likelihood calculation. However, since autogressive models do allow for it, would it make sense to use that as an evaluation metric (bits per dim is the standard metric for likelihood-based generative model)? It would be nice to see an analysis of how that metric changes as the information content in the latent code changes (which can also be measured).\n\nOverall, I lean towards acceptance, based on the novelty of problem & approach.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Many concerns raised by the reviewers have been addressed by the authors, sometimes through additional experiments. The reviewers have updated their scores in response, and all now recommend acceptance.

Like Reviewer 4, I think that the relation to nested dropout (Rippel et al. 2014) needs to be acknowledged and discussed appropriately, so I encourage the authors to carefully consider the reviewers' most recent comments about this when preparing the final version of the manuscript.

I disagree somewhat with Reviewer 3 that the motivation provided for this work is insufficient; controlling the quality/speed trade-off at inference time seems like a compelling application. So does progressive generation, as suggested by Reviewers 3 & 4. I appreciate that this is highly subjective, however. Perhaps a few more concrete examples of practical situations where such trade-offs are useful could be mentioned in the introduction.
Decision: Accept (Poster)