Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper argued that one current limitation of Any-Order Autoregressive Models (AO-ARMs) is that they suffer from redundancy in their probabilistic model, i.e., they define the same distribution in multiple different ways. Especially, to my understanding, the authors mean that a sequence of length $n$ can be defined by $n!$ orders, which causes the model to under-fitting any-order data distribution as observed in XLNet or ARDMs. A particular order (i.e., $w$-MAC, Mask-tuned Arbitrary Conditional Model) is introduced to remove such redundancy by sampling the order from a non-uniform decomposition protocol $w$. During the inference (which only contains the likelihood estimation task in this paper), the order is also sampled from $w$-MAC, rather than uniform distribution, and thus achieves better likelihood estimation (somewhere between left-to-right autoregressive model and real AO-ARMs).
strengths_and_weaknesses: Strengths:

1. The main strength of the paper is that it finds a (maybe principled) way to tweak the order distribution in AO-ARMs to get a better likelihood number (which also might not be true, as I argued in the Weaknesses). This could potentially improve the quality of tasks that require sampling from an AO-ARMs, and in the meantime, can produce a valid probability given any observed and unobserved variables.

2. A heuristic cardinality reweighting trick is introduced in Section 3.2 and explained in Section 5. This may inspire future research in this direction.

3. Despite the high complexity, the model can still be trained in parallel.

Weaknesses:

I mainly have two concerns.

1. Using Figure 2 (b) as an example, in the proposed method, the following equation might hold $p(x_2, x_3, x_4) > p(x_2, x_4)$, which means $\mathbb{E}_{\sigma} p(x_3 | x_2, x_4) > 1$. Based on this, I think the mathematical foundation in the proposed model is invalid.

2. In the evaluation, all the previous work samples a random order $\sigma$ from the uniform distribution because of the following assumption:
   1.  "In other words, it does not matter which step $t + k$ the model predicts, in expectation, these all have the same associated likelihood." from [1]
   2.  "We note that a model which perfectly captures the true densities would give consistent likelihoods for all possible orderings (thus evaluating only one ordering would suffice)." AND Algorithm 1 from [2]

However, in this work, $\sigma$ is no longer from a uniform distribution. Therefore, in order to get a precise likelihood estimation, the paper might need to get more order samples to reduce the variance in likelihood estimation. Still, no such information or discussion is provided in the paper.

[1] Autoregressive Diffusion Models
[2] Arbitrary Conditional Distributions with Energy

questions: 1. Clearly, a biased order distribution can produce better perplexity, as it is trained more on a specific order. And therefore, in principle, it should not perform better than real AO-ARMs, but this is not reflected in the experimental results of Table 1, which caused my confusion. My question is on the evaluation of marginal likelihood. Let's again take Figure 2 (b) as an example, I'm wondering how proposed method can compute the marginal likelihood of $p(x_1, x_2, x_3, x_4 | x_2, x_4)$ if there is no edges between (2, 4) and (1, 2, 3, 4)?
limitations: The work does not have an obvious potential negative societal impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: A method for training nonautoregressive generative models of high-dimensional (e.g., sequence) data is proposed. The main algorithm requires the choice of a decomposition protocol, which is a choice of generation order defined by a deterministic Markovian reverse generation process. The training objective is equivalent to a weighted log-likelihood of each generation step in the chosen order leading to a randomly masked training sample. Strong results are shown on a variety of domains.
strengths_and_weaknesses: Strengths:
- The proposed algorithm is simple and intuitive and the derivation is sound.
- Strong results on a diverse set of problems, including language, vision, tabular data, and robot motion planning. Evaluations and comparisons are solid.

Weaknesses: (I am willing to raise the score if the authors discuss the limitations and relationship with past work in their response and commit to adding them to the paper.) 
- The definition of the decomposition protocol used is hidden in the text (L179) and not illustrated on real data. This makes it hard for a reader to check their understanding and gain intuition. 
- The use of a canonical ordering of data dimensions seems like a limitation of the approach, but it is not discussed. For example, even in the image domain, it is not clear that the standard ordering of pixels in the "reading" order is optimal for modeling. In other domains, such as tabular data and other settings where incremental generation in arbitrary order is possible (e.g., generic fixed- but high-dimensional data or data of variable size, such as graphs, point clouds, etc.), there is no natural ordering. Please see the questions below.
- The discussion of related work could be improved. Please see the second question below.
questions: - Would the results change if "largest" is replaced by "smallest" (or largest w.r.t. some random but fixed permutation of the dimensions) in the definition of the decomposition protocol (L179)? The definition relies upon a choice of natural ordering in the data space, so it may be important.
   - In particular, how could the algorithm be combined with the learning of a (possibly probabilistic) decomposition protocol?
- Relation to past work.
   - A few papers that have addressed the question of non-autoregressive modeling have not been mentioned. For instance, [A1] is a relevant citation, while [A3] suggests an alternative approach that uses a continuous relaxation to learn generation order.
   - (Also related to the first question:) There are several other algorithms that feature a learned generation order, albeit in slightly different settings. In [A2], non-uniform generation order emerges implicitly from a greedy optimization procedure. In [A4], which uses a similar framing of chains on a lattice, the learned "backward policy" is a stochastic, data-dependent decomposition protocol. What is the relationship of MAC with such approaches?

[A1] B.Uria et al., Neural autoregressive distribution estimation (JMLR, 2016). arXiv:1605.02226

[A2] D.Emelianenko et al., Sequence modeling with unconstrained generation order (NeurIPS 2019). arXiv:1911.00176

[A3] X.Li et al., Discovering non-monotonic autoregressive orderings with variational inference (ICLR 2021). arXiv:2110.15797

[A4] D.Zhang et al., Generative flow networks for discrete probabilistic modeling (ICML 2022). arXiv:2202.01361
limitations: Please see the second point of Weaknesses above.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper improves Any-order ARO models by  making them more efficient reducing redundancy in computations, while maintaining tractability and by better aligning the training and inference objectives.

The key idea is to reformulate the objectives in AO-ARO such that redundancies in computing the univariate conditionals can be fully exploited. Further, by tuning the training based on the distribution that represents the importance of univariate conditionals, the training is better suited to compute marginals during inference.

Experiments are performed on several tasks and comparison studies show the improvements the proposed approach offers compared to state of the art
strengths_and_weaknesses: 1. The paper is written very well clearly defining the problem, the background work and its own novel contribution.
2. The work is meaningful and significant considering the generality of computing marginal probabilities (by integrating from high-dimensional data)
3. The experiments seem to cover many areas, standard benchmarks from computer vision, language models, robotics, etc. The variety of experiments clearly shows the strengths of this work.

Weakness

While this may not be a weakness, maybe limitations of the proposed work can be mentioned or discussed.

Overall, I thought the paper proposed a significant problem, clearly outlined a good solution and conducted an excellent empirical study.

questions: None
limitations: They are not explicitly addressed. It would be nice to have a discussion on these in the paper.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors present the Mask-tuned Arbitrary Conditional Models - a method for training Any-order Autoregressive Models.
They argue that the paper presents two insights hurting conventional AO-ARM training which they address with their method. 

The authors investigate their method with an ablation study and present it on a variety of experiments. 


strengths_and_weaknesses: Strengths: 

The explanations in the paper are well done and overall I found the paper clear and well-written. 

Ablation study well isolates the components of your method and the contribution of each of them.

Experiments are clear and well presented. A good variety of experiments were presented.

The authors state that it is not arbitrary joint distribution decomposition ordering that we really care about but, instead, arbitrary conditioning. They show that an ordering over every marginal can be specified, or a distribution over orderings, to address redundancy in training.

The authors show that tuning the mask distribution for training can lead to better results - an important idea that can be investigated further. Although the idea is straight-forward, I view this as a strength of the method as it is a simple, effective modification to the standard training techniques that yields better results with, as the authors put it, no compromises.

Weaknesses: 
A lack of error measurements in most of the experiments makes it hard to determine if your results are significant. 

The idea that we want to weight masks more often used (which are the lower carnality ones) and the cardinality reweighting seem contradictory so I'm not sure how much I believe your intuitive explanations of each idea. The ablation study shows the effect of using the insights in the order of B->A but I wonder how well A only would do. Did you try to use a uniform distribution over the masks remaining after insight A (pictured in figure 2c)?

If I understand correctly, your algorithm box doesn't actually reflect how you train the model (in parallel) using the objective in eq 7. There is a lot of machinery presented (although interesting) to arrive at the conclusion that the MAC objective (eq 7) is the standard AO-ARM objective (eq 4) with a different mask sampling distribution.

A subjective point: I found the notation confusing in some places. You use several different types of notation to refer to the same objects - you refer to the conditional distribution of interest as p(x_sigma(t)| x_sigma(<t)), p(x_i_t|x_e_t), p(x_i|x_e), p(x_j| x_e/j). I was particularly confused by referring to edges as (i, e) or (i_t, e_t). What is i in this case? I assume from context it's a variable not contained in the mask e due to the summation on line 207 but I don't think it was defined. 


questions: I'm not sure what your "sharpen mask distribution" section is concluding. Is it just that your selected mask distribution has lower entropy (by design) than uniform? You're not showing that low entropy mask distributions actually help, except, possibly, in your earlier experiments. 

I think there is a small typo in the caption of Figure 1a: "An autoregressive (model?) defines ..."


limitations: A small discussion on the mask distributional mismatch is included. Generally, limitations, or the lack thereof, are not discussed.
review_title: null

Meta-review: metareview: This paper introduces an improved training method for auto-regressive generative models. Specifically, the paper identifies a redundancy problem in common auto-regressive models and proposes a way to fix this. The reviewers found the contribution significant and important, and it is likely that the paper will have substantial impact. 


confidence: Certain
Decision: Accept