Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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.

Major comments:
- 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.
- 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.

Minor comments:
- Sec. 1, last paragraph: autoregerssive -> autoregressive
- Sec. 6, second paragraph: Instead of uniform distribution -> Instead of the uniform distribution
- In front of Sec. 7, there seems to be a negative \vspace that shouldn't be there

Summary:
I 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.
review_title: Nice idea, but some ablation experiments are missing

final_score: rating: 6: Marginally above acceptance threshold
review_content: #### Summary

For 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.

#### Review
The 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.

The 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?

I'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.

#### Typos and other nits
 - Second paragraph of page 2, autoregressive is mis-spelled in the first line.
 - Latent vectors are transposed, why?
 - 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'.
 - 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).
review_title: Straightforward paper, good enough but not super exciting or surprising

final_score: rating: 6: Marginally above acceptance threshold
review_content: # Summary
The 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.

# Strong points
- 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.
- 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. 
- Experiments are designed appropriately to showcase the resulting behaviour of the model. Experimental setup is explained in sufficient detail.
- Section 4.3 is well done: an easy-to-understand motivation for a proposed architectural change, with a clear empirical demonstration of its effect.

# Weak points
- 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.
- 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.
- 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).
- 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?
- 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?
- 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?
- 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.

# Minor points
- 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.
- 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.
- 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?*
- The `stop_gradient` operation should be defined.
- Figure readability isn't great: a larger font (try make comparable to text font size) and thicker lines will help.
- Try to use consistent labels in figures: the proposed method is at various points referred to as a "OVQ-VAE", "Anytime + ordered", "Ours".
- References: use proper capitalization ("Gan", "pixelcnn", etc.), deal with repeated references (see Heusel 2017a/b).
- Formatting: reduced spacing above conclusion section header?
- Notation in 4.1: $z_{e,j}$ is confusing notation, consider renaming the variable to avoid having to use the comma.
- Poor phrasing: "our training is stable and more suitable for large scale training", "for the instantiation".

# Recommendation
To 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. 

On 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.

All 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. 

# Random questions/comments
- "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).
- 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? 
- In Fig 3a the OVQ-VAE curve goes up a few times. Do you explain this by optimization not fully converging?
- 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?

-----

EDIT:

I 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.

Unfortunately, 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.

In 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.

Overall, 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.
review_title: Interesting, well-motivated idea, but experiments and write-up fall a bit short

final_score: rating: 7: Good paper, accept
review_content: Summary:
The authors explore the use of anytime sampling to allow sampling from autoregressive models on a fixed computational budget.
They 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),
They 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.

Strengths:
* The authors tackle a problem that is impactful but not very well-studied in the community, and propose a novel approach to do so.
* The proposed method is well-explained.

Weaknesses:
* Experimental evalution could be more thorough. 
    (1) Is there any related work on this topic (or simple baselines) that are worth comparing too?
    (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).

Overall, I lean towards acceptance, based on the novelty of problem & approach.
review_title: Interesting problem & approach; experiments could be improved

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)