Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper targets the problem of systematic generalization in sequence to sequence models, particularly in the scenario of modeling segment alignments as discrete structured latent variables. To explore the searching space of alignments, the authors proposed to use a reorder-first align-later framework, and use hierarchical permutation trees to produce separable permutations, which has the exact marginal inference with dynamic programming enabling end-to-end training. Experiments show that the proposed approach outperforms standard models on both synthetic and real NLP tasks with better systematic generalization.
main_review: Overall I think the idea of reordering and then model alignment is quite interesting and important for the area of seq2seq learning, as it solves a big issue of conventional approaches (e.g. SSNT) that only works for monotonic alignment while in real scenarios many applications such as machine translation do not hold. Also, the motivation of connecting learning systematic generalization and segment alignments seems reasonable.

I only have some detailed question about this submission:

-- In section 2.2, you discussed the connection between discrete alignment and continuous attention. Will the proposed target also be achieved by using the attention weights for the segment alignments? Or is there any reason we have to work on discrete alignment (which might potentially be more costly)?

-- In Line 154 & 155, do these two equations have a typo? Why do “straight” and “inverted” have the same results? Moreover, it would be much better to give more context explaining these terms such as “straight”, “inverted” as well as BTG to make it easier to understand the method.

-- What is the algorithm you used for inference? How to decide the best permutation of reordering?

-- All the experiments seem to be quite small scale with a small architecture. Is it because the proposed method cannot work on a larger scale? Will this idea be applied to large scale problems such as WMT using Transformer based models?

-- What is the computational cost for both soft and hard ReMoto, and how does this compare to previous works in both training and inference time?

limitations_and_societal_impact: The author did not have a separate section about the limitation or societal impact.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper tackles the problem that conventional sequence-to-sequence models (seq2seq models) fail to generalize systematically; i.e., they are suboptimal for handling the compositionality of language. The paper makes the following contributions: (1) a new seq2seq model for NLP tasks that accounts for latent non-monotonic segment-level alignments and (2) an algorithm for exact marginal inference with separable permutations, which makes end-to-end training possible. The proposed approaches are evaluated both on synthetic data and two real-world NLP tasks: semantic parsing and machine translation. The experiments show that the proposed model mostly outperforms conventional seq2seq models in an IID setting, and even more strongly outperforms existing models in settings where test examples are longer than training examples. 
main_review: The authors do a great job introducing the motivation for their work (i.e., the problems with currently existing models). Furthermore, the experiments are designed well to show the benefits of the proposed approaches, and I like the fact that the experiments are done on both synthetic data and real-world datasets. The experimental results demonstrate the benefits of the proposed model. The paper is written clearly.
limitations_and_societal_impact: The authors do not explicitly talk about the limitations of their work, but the experiments make some potential limitations obvious (e.g., seq2seq could perform better in some IID settings). I don't see a reason to expect any negative societal impact of the work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The order of the input and output (including their associated representations) can matter for the performance and interpretability of a sequence to sequence model. Based on monotonic alignment seq2seq model (e.g. SSNT), the paper proposes to learn a separable permutation over the input representations so that the monotonic alignment can lead to better performance and interpretability. The authors test their methods on toy datasets and small scale semantic parsing and medium sized machine translation tasks.
main_review: Monotonic alignment seq2seq model is an interesting family of seq2seq models that can not only boost performance (particularly when the monotonic assumption holds in large) but also provide some interpretability for the prediction task. To relax the monotonic assumption, this paper proposes to learn a permutation matrix $M_p$ as a first step before the monotonic alignment seq2seq model; the paper proposes a way to combine these two steps in an end to end fashion.
The permutation matrix is parameterized only for separable permutations, which have their linguistic groundings. In 3.2, the authors show that the matrix can be estimated efficiently as an expectation of the underlying BTG separable permutation marginals. An alternative is to add a gumbel softmax trick to simulate the hard permutation choice. The separable permutation marginal calculation is new and the authors have shown the proofs and important technical details for this algorithm (e.g. the WCFG normalization). The algorithm is generally applicable to any parameterized BTG, however neither in the paper nor in the appendix, I can see how the BTG is parametrized for various experiments, making myself unable to reproduce the experiments in thoughts. 

The authors have shown the benefits of the proposed approach via toy examples and some real tasks. One question I have for the Geoquery experiments is that the baseline and the proposed methods have too low accuracy (maybe due to missing argument mapping), as a reference, https://arxiv.org/pdf/1601.01280.pdf reports a seq2seq with attention baseline, achieving 84.6 accuracy on Geoquery, and this is not SOTA at all. 

The other minor writing/formatting/missing references:
- Eq(2), this formulation is not used throughout the paper and potentially misleads readers to factorization methods. From my understanding, the paper proposes two steps approaches and the matrix doesn't necessarily come from the factorization in Eq(2).
- Line 155: It seems that the order of the two non terminals should be reversed.
- Line 226: Gumbel-Softmax should be outside of parenthesis.
- In general, the order of the input matters for performance which can be another motivation of the paper, thus related to https://arxiv.org/pdf/1511.06391.pdf. The paper also connects to self attention widely used in NLP, it seems that specific parametrization of self attention can lead to permutations.

＃After discussions with the authors: the authors have clarified all my questions concerning the formalism, presentation and experiments. I feel that the paper can benefit from discussing in details the various settings and the rationales behind, not only the semantic parsing experiments that we have discussed here but also other scenarios as other reviewers pointed out. The authors have shown generally deep understanding of the encountered problems and I have adjusted my score from 5 to 6, confident that the final paper will be better quality to best convey the proposed ideas.
limitations_and_societal_impact: I think the authors could mention in the future work testing the methods on large scale datasets (for both semantic parsing and machine translation). Also, the proposed methods seem to integrate well with current pretrained methods and are worth trying in the future to boost task performance.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors propose a model for sequence transduction tasks that allows for source tokens to be reordered and then monotonically aligned with the target tokens. The reordering and the alignment are latent, and since all monotonic alignments can be marginalized over using the approach introduced in the SSNT paper (Yu et al., 2016), the authors focus on approximating the marginalization over the latent source permutation. The authors consider in particular separable permutations, whose derivations are induced by a PCFG. The authors propose two approximation approaches, one which uses a dynamic program to obtain an expected permutation matrix (which is used instead of the expected likelihood under the permutation-matrix distribution), and one which samples a hard permutation matrix during learning and uses a ST-Gumbel-Softmax gradient estimator. The authors experiment on a number of synthetic and small-scale real-world tasks and generally find that their approach outperforms baselines, and is especially performant in settings that require generalization to longer inputs than those seen in training.
main_review: The paper is interesting, generally clearly written, and it seems technically sound. I think the core contribution of the paper is, as the authors suggest on line 66, to propose a hierarchical approach to modeling permutations of input, as opposed to other, flatter alternatives. 

Overall I think this is a nice paper, but I have some suggestions/concerns:
- I'm not sure the authors' emphasis on the model capturing segments or on segment alignment is either justified or needed. As far as I can tell, the SSNT model computes alignments between tokens. It's true that segmentations are induced either by multiple tokens aligning to a single token or by the alignment skipping contiguous source tokens, but it seems like the model doesn't ever really represent segments themselves as first-class objects. Rather, it seems like the major inductive bias afforded by SSNT-type models is that the alignment needs to be monotonic, and so an alternative hypothesis for the success of both SSNT and ReMoto is that monotonic (token-level) alignment is a useful inductive bias (even if perhaps we need the alignment to be monotonic in a reordered source sequence). So, while I don't think this hurts the paper much, I think we would need much more evidence before concluding it's the segment alignment that is helping here.
- Experimentally, I think the paper is generally good, although it seems important to have an SSNT baseline in Table 3 for the semantic parsing experiments (so we can separate the contributions of monotonic alignment and reordering).
- Given that Hard-ReMoto seems to generally work best, it might be worth discussing to what extent we need the Markov assumptions made by the permutation-derivation model. For instance, would it better to just use an autoregressive parameterization of the derivation distribution?
- There are other approaches to obtaining differentiable permutations that should perhaps be mentioned, like " Stochastic optimization of sorting networks via continuous relaxation" (ICLR, 2019) and "Differentiable Ranks and Sorting
using Optimal Transport" (NeurIPS 2019)

Minor suggestions:
- I think the authors should explicitly describe the SSNT model and the parameterization of p(y | X, M) in the main text; otherwise it is hard to follow what exactly is going on. 
- Equation (9) should probably have just p_{phi} rather than an expectation under it.
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: This paper presents uses the class of separable permutations, which in contrast to the unrestricted class of permutations, can be reasoned about in polynomial time using dynamic programming algorithms to introduce explicit reordering and alignment variables in seq2seq models. The reviewers remarked on the technical clarity, interestingly novel approach, and thorough experiments. This technique improves interpretability and, most importantly, provides a demonstrated bias for compositional generalization, both of which are important concerns in sequence transduction modelling. This represents a serious and successful attempt to address these issues by changing the underlying assumptions of the model, rather than relying on data augmentation.
Decision: Accept (Poster)