Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work proposes neural QCFG (quasi-synchronous context-free grammars) for sequence-to-sequence learning. By explicitly modeling the alignment between source and target trees, they aim to improve the generalization and interpretability of the model. Different from prior works that learn a parser to construct source and target trees, this work learns latent trees, i.e., a distribution of source and target trees. On SCAN and "daxy" machine translation, which are two benchmarks specifically designed for compositional generalization, neural QCFG achieves good but not perfect results. On hard style transfer tasks from StylePTB, neural QCFG largely outperforms the baselines.
main_review: This work proposes a promising approach for improving the generalization. Although the scalability could be an issue due to the high time complexity, compared to prior work on grammar learning, modeling the tree structures as latent could improve the flexibility.

However, this work lacks a thorough discussion of the failure mode of the approach, which makes it hard to qualitatively understand the scenarios when learning latent alignment is better than explicitly modeling the grammar. First, both SCAN and the machine translation tasks evaluated in this work have validation/test sets with examples generated by pre-defined templates, thus if a model accurately learns the grammar, it should achieve 100% accuracy on both tasks. This is reflected by prior work. However, although neural QCFG achieves much better results than baselines that do not explicitly learn the grammar, the accuracies are not perfect. Could you provide a discussion on the failure cases? Note that in Table 1, without T5, NQG baseline itself can achieve 100% accuracy on SCAN, which shows the feasibility of learning a concrete quasi-synchronous grammar for SCAN benchmark. Is there any fundamental limitation that prevents neural QCFG from achieving the same performance as a deterministic grammar parser?

Meanwhile, I want to note that the proposed neural QCFG might not be completely domain-agnostic. The paper shows that the authors set different hyper-parameters for the number of nonterminals and the number of preterminal. From my understanding of these benchmarks, these hyper-parameters seem to be well-tuned for the underlying grammars of these datasets. Does changing these hyper-parameters affect the performance, and is it possible to set the same hyper-parameters for all datasets?

About the hard style transfer tasks in Table 2, I wonder if the authors have also evaluated on the easy and medium tasks in StylePTB dataset. Does neural QCFG still outperform other baselines?

To understand the effectiveness of latent grammar learning, I feel that the authors should provide a more detailed discussion and comparison of NQG work, given that both of them are based on quasi-synchronous grammars. From the current experiments, it is a bit hard to understand whether this work is more capable of learning grammar rules than NQG. If the authors have also tried other datasets in NQG paper, e.g., the template split of GeoQuery for evaluating compositional generalization, it is helpful to include related discussion as well.
limitations_and_societal_impact: The authors adequately addressed the limitations and potential negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a hierarchical approach to sequence-to-sequence (seq2seq) learning with latent synchronous grammars where each node in the target tree is transduced by a subset of nodes in the source tree, and the grammar trees are marginalized out during training. The proposed latent neural grammar is validated in various tasks including diagnostic language navigation, style transfer and machine translation, and shows better compositional generalization.
main_review: I think the overall goal of using latent grammar trees and marginalization to improve sequence-to-sequence learning is promising. Although the complexity of this method might limit its application to a larger scale scenario.
However, I am not an expert in this direction and my judgement might not be accurate.

Questions:

---  In Line 70, you restrict all $\alpha_i$ to be nodes of the source tree. Why is this restriction important and can we think of it as the “attention” from the target nodes to source nodes?

--- Moreover, continuing from the last question, is it possible to directly treat source as sequence and work on sequence-to-tree grammars? In this way we don’t need to marginalize $p(s|x)$ with a Monte Carlo estimator. Is it possible? Or the grammar is restricted to be tree-to-tree?

--- What is the training cost (time) and inference speed compared to standard sequence-to-sequence models?

--- What will be the performance for the proposed method without using the autoregressive LM?

---  I wonder how the proposed method works on very long sequences, or a larger but noisier dataset, for example machine translation WMT En-Fr with over 30M sentence pairs. Will the performance degrade a lot because of the nature of the dataset?

limitations_and_societal_impact: This paper discussed the limitations and future works. But it would be nice to have a separate section with more discussion and societal impacts.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper presents a neural extension to quasi-synchronous grammar (QCFG) for sequence-to-sequence modeling. In addition to the neural extension, QCFG is also extended (for the first time to my knowledge) to be jointly trained alongside the source parser that the QCFG transduces (this requires a dual objective: the sequence-to-sequence objective, and a traditional monolingual CFG objective from a treebank). Extensions for phrase-to-phrase copying, various constraints, and a (theoretical) addition of an arbitrary-context autoregressive LM are also provided. Strong experimental results are presented for 3 small-scale tasks that emphasize compositional generalization: SCAN, Style Transfer and MT.
main_review: This is very interesting, off-the-beaten-path work (at least for 2021). The technical contribution is substantial, going well beyond a neural adaptation of QCFG, and the authors have expertly picked the right tasks to showcase their model - the experiments are quite convincing. The inclusion of example tree transductions for each task is very nice. This feels like exactly the sort of paper we should be encouraging - it may catch on, it may not, but the ideas here are likely to inspire more than a few people to do something interesting. The brief limitations discussion at the end is quite honest, emphasizing and owning the very real problem of scaling up in the face of an expensive dynamic program. The paper is very well written and very easy to follow.

I like this paper a lot, but I do have some concerns:

The joint CFG + QCFG training algorithm in Section 2.3 is a big part of this paper’s technical weight, using a score function estimator with a self-critical baseline. However, its contribution to the method’s success is never tested directly! Since the source parser is simultaneously trained as a monolingual PCFG, you have access to all of the pieces necessary for a traditional pipelined approach: train the PCFG parser first, and then use the fixed parser to train a standard QCFG transducer for your sequence-to-sequence task. This baseline should be evaluated for all three tasks, so we can better understand the impact (if any) of joint training. Were this a thesis or journal review, I would insist on this experiment.

Also, the number of non-terminals and pre-terminals (|N| and |P|) jump around for each task. How were these tuned? How necessary is this tuning for your method’s success? I could ask the same question again for the various constraints placed on target tree structure based on the source tree. Ideally, all of this should be determined during development. I checked the appendix, but I wasn’t able to find anything explicit - there’s some chance the development sets were just used for early stopping.

Less importantly, it was never clear to me why predictive inference needed to be so complex, involving sampling k target trees and then rescoring their yields. In fact, it was never clear what model or heuristic was used to rescore the yields given the trees. I’m sure it makes sense, but it needs to be spelled out. Again, an ablation that compares to the obvious yield-of-max-tree baseline would be helpful.

limitations_and_societal_impact: Handled well.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: QCFG (Quasi synchronous Context Free Grammar) is a relaxation of the SCFG and is an interesting and important tool to consider for structured transduction applications such as machine translation, semantic parsing, etc. This paper proposes to learn this grammar through latent variable learning; alongside, it proposes a neural parametrization for learning this grammar through terminal embeddings using TreeLSTM. Due to the flexibility of QCFG, there are technical choices that need to be made to run the training/inference efficiently as shown by the paper.

The proposed approach can deal with operations that go beyond token manipulation, and the authors empirically show that it allows for better compositionality handling and long range copying (2.4).
main_review: The paper proposes an end-to-end neural parametrization for QCFG (a constrained version which is still more flexible than SCFG). Compared to more common seq2seq learning, the papers have demonstrated two advantages to learn a neural parametrized QCFG:
- The copy operation can be performed in logical chunks and this has been shown particularly important to perform well on hard section of StylePBT
- Add domain specific constraints, for example, descendant restrictions are applied for all the experiments on datasets from (Lake and Baroni, 2018). 
As the QCFG is much more flexible than SCFG, the formalism offers the above advantages while modelling many interesting seq2seq tasks as shown in the experiments. However, these advantages come with the price of having computational difficulties. Facing these difficulties, the authors have made an excellent job in introducing clearly and succinctly the difficulties and their proposed solutions in section 2.3.

The experiments are carried over three datasets, the SCAN one and Toy machine translation one suggests that proposed methods can perform reasonably well on compositionality demanding tasks. The StylePBT dataset results show more benefits of such methods compared to seq2seq baseline and even previously proposed methods, although I would strongly suggest the authors take care of the formatting for table 2 (highlighting best performance, e.g). 


There are two questions that I want to clarify with the authors: 
1. In line 113: It is said that empirically, it is important to train the source as a PCFG. In this case, it would be natural to perform the prior work which first trains a source side PCFG and then learn the synchronous grammar. I don’t see such experiments in the paper, do authors also consider this as a natural and maybe strong baseline compared to the proposed approach please? Related to the this point, the paper's main contribution is to propose learning a neural QCFG end to end. What is the end to end performance without relying on the monolingual PCFG please?
2. Why is there no baseline to learn non-neural QCFG in the paper please? One such baseline can be found in the description of NQG-T5 and I am sure there are other approaches and works on this. Another minor related question, why do the authors say that NQG-T5 uses SCAN-specific knowledge please? From my reading of that paper, they seem to deduce from scratch a QCFG pomn SCAN (at least the NQG part)? 

＃ After reading authors' response:
Thanks for the authors having answered my questions (and other reviewers' questions) in great detail. Both reviewer 3 and me found PCFG + QCFG to be a natural baseline and I hope the results communicated here can be added to the final paper. The table for constraints are as well informative. The cost of these approaches and why it can't be applied to general MT are important details to explain and should be improved as well. 
With the response, I think the authors have sufficient material to address above concerns to better communicate the paper's idea. I have increased my score from 5 to 6. 

limitations_and_societal_impact: On domain specific constraints, when applying to toy examples in (lake and Baroni, 2018) this seems beneficial. However, what kind of constraints do authors think can be applied to real life scenarios please (e.g. machine translation, natural language generation.)
review_title: null

Meta-review: The proposed hierarchical approach to sequence-to-sequence learning with synchronous grammars is interesting and looks flexible. Empirical results on compositional generalization benchmarks are good. All reviewers agree the acceptance. I hope the authors find the reviews are helpful to further polish this submission when revising it for the camera ready version. This paper will be essentially strengthened if the authors can also show that the proposed method performs well on other tasks (GeoQuery) used in the NQG paper.  
Decision: Accept (Spotlight)