Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a method to measure how much compositional-ness a transformer model behaviours. The whole work relies on the hypothesis, that inner composition should be independent from outer context. Relying on that hypothesis, the paper proposes the concept of *span contextual invariance* and how to measure it. That leads to a method searching for a tree that is *closet* to the computation of a transformer performing on an utterance. Then, two ways are introduced to measure tree-structuredness, one with and one without a gold tree. 

Theoretically, the paper proves that under a mild condition,  minimizing the span contextual invariance yields exact tree projection. Empirically, the paper demonstrates how the two metrics can help to unveil the compositional-ness of transformers. The paper also presents some analyses, especially one on how tree-structureness is correlated to generalisation.
strength_and_weaknesses: The paper tackles the challenging problem with a novel and very interesting idea. The paper makes choices reasonably. First of all, instead of topological tree-structuredness, the paper is looking for *functional* one. This is a novel view for how to understand the compositionality behaviour of a model, and easily turns the problem to optimization. Next, the concept of *span contextual invariance* does reflect the principle of compositionality, and is thus well linguistically motivated. I found the implementation for estimating the tree projection is smart and technically sound. Especially, it can employ the power of the parsing method by Stern et al 2017. 

I however found T-shape masking and threshold layer quite tricky, and can't find detail implementation in the paper. It is unclear, e.g. in fig 2, where a threshold layer is put when the number of encoder layers is varying from 2 to 6. And in footnote 2, what does it mean by "tuning the threshold layer"? 

The flow of the paper can be more logical. Section 5 uses the proposed t_score and t_parseval to measure tree-structuredness. The key question here is: how good can they measure compositionality? Up to that point, the paper doesn't seem to answer that. And thus it's difficult to see how the conclusions raised in section 5 are reliable. The reader has to wait until section 6.1 for "... induced trees reflect the contextual dependence structure learnt by a transformer." 

However, it still doesn't answer why the proposed t should be more reliable than p_parseval. Right below Fig 3 "we conclude that supervised probing is unable to discover latent tree structures as effectively as our method." Why is it bad to converge too fast here? The paper even doesn't show the *true* tree-structuredness improving rate. 



clarity,_quality,_novelty_and_reproducibility: * Clarity: I enjoyed reading the methodology described in the paper. But the experiments and analyses (sec 5 and 6) are quite difficult to follow. Partly because, as mentioned above, I think section 6.1 should be before section 5. 

* Quality: The paper should have a significant impact to the community working on analysing compositionality of DL models. However, some arguments (mentioned above) raised in the paper should be carefully examined. 

* Originality: The idea and method proposed in the paper is novel and very interesting. 
summary_of_the_review: I enjoyed reading the paper and recommend to accept it. The paper has high quality, with novel and very interesting ideas. The work is solid, experiments and analyses are quite thoughtful. 

The paper can improved by
* adding more details about implementation (T-shape and threshold layer) 
* re-flow some experiments / arguments
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors hypothesize that transformers generalize to unseen sentences by implicitly constructing a tree-structured object bottom-up from inputs. They attempt to understand whether the transformer does indeed perform tree-structured computations by approximating them with with a tree. They introduce a novel method to construct tree representations using a procedure that computes distances between contextual and context-free representations of all subsequences in a sentence. 

strength_and_weaknesses: + The paper is well written and was relatively easy for me to understand. 
+ Theorem 1 is helpful in formalizing how the proposed framework projects transformers to the space of tree structured computations
+ The results appear convincing, with some minor caveats, mentioned below

- I wish the authors would spend more time motivating why this is an interesting problem, and if there are other ways to explain generalization of transformers. Ultimately, the tree computation hypothesis is just one possible explanation for generalization, I'm curious how to know how this work fits into the broader landscape of work
- I found section 6.2 interesting, can the authors expand on this point? Unless I'm misunderstanding, this is a central motivation for the paper and requires further explanation. 

clarity,_quality,_novelty_and_reproducibility: I found the paper clear and well written, the proposed method seems novel and is explained well enough to reproduce.

summary_of_the_review: The paper is well written and clear, I think the ideas presented are novel, specifically how to project transformers to the space of trees. I would recommend accepting.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes a method to project the “behavior” of a transformer model into a binary tree. Crucial to this is the concept of contextual invariance: the representation of a tree node does not depend on anything outside its children. Specifically the method approximates a bracketing of the sentence such that nodes in this tree are maximally invariant under this definition. Given contextual and context-free representations of a span within a transformer model, the distance between them is taken to measure the context-invariance of that span. 

The paper goes on to show that tree-like structure is stronger as model train, and that in two of the three data sets used, the trees obtained match a gold syntax. The degree of the tree "match" also correlates with compositional properties of the models as measured on test sets for compositional generalization. 

strength_and_weaknesses: The main weakness of the paper is its motivation. Specifically:

* The paper starts by explaining that hierarchical structure is necessary for humans to understand novel utterances, and discusses the concept of composionality. It goes on to introduce context-invariance as a crucial ingredient of it: the meaning of an expression does not depend on anything outside the syntactic tree that the expression spans. While the paper mentions notable exceptions to this assumption: multiple word meanings, idioms, etc, it still contrasts compositional interpretation with context-invariance (first paragraph of page 3). I believe that is wrong. It is clear that both play an important role: there is a certain amount of context-invariance required for efficient generalization but language is far from being context-invariant. The two are not at odds with each-other and there is no reason to believe that humans and computational models can’t do both effectively. 

* Following this, the paper sets out to measure the context-invariance in the behaviour of transformers. However it’s not clear what questions does the paper aim to answer. Do we want transformers to be context-invariant? No. Do we want transformers to show compositional generalization? Yes, but that should be measured as part of a real-world task, not an artificial task. That is because real world language tasks require both compositional generalization and context-dependence. For example machine translation is a task where models fail to capture context dependence (wrong word meaning, too-literal translations), and it can be argued they show too much compositional generalization.

* These issues continue in the experimental section: the transformer models investigated are trained on small data sets, in some cases using synthetically-generated language and structure-biased tasks such as predicting logical forms. As such the results do not say much about language in general or about real-world language applications.


clarity,_quality,_novelty_and_reproducibility: The paper is clearly written. Methods to assess how the amount of syntactic structure in neural models have been proposed in the past, however there are some differences from previous work: this work does not assume any notion of syntax and looks for the braketing that best approximates context-invariance. 
summary_of_the_review: The paper does not address a clear research question: it proposes a method to find a sentence braketing using transformer representations, such that is maximizes the context-invariance of the representations (the representation of a span depends only on its words and not on outside context). It analyzes this braketing and the degree to which it approximates the transformer representations across three tasks used for compositional generalization. Compositional generalization should not be studied in isolation but in the context of real language tasks that require both generalization and context-awareness. Even if the paper had done this, I do not see the impact of method introduced in the paper or of the results. I also find the terminology used throughout the paper miss-leading (such as “tree-like computation” or “tree-structuredness”), as it contrasts hierarchical structure with context-dependence when it’s clear that both are necessary ingredients for modeling language.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes an unsupervised and parameter-free method that functionally projects transformer models into the space of all tree-structured models. By using this method, they show that transformers for three different tasks become more tree-like over the course of training, in some cases unsupervisedly recovering the same trees as supervised parsers. Finally, they use tree projections as a tool to predict behaviors associated with compositionally, where they find that induced trees reliably reflect contextual dependence structure implemented by encoders and both tree scores as well as parsing F1 of tree projections better correlate with compositional generalization to configurations unseen in training than in-domain accuracy.
strength_and_weaknesses: Strength
- The tree projections require no extra training and parameters and can be applied to any transformer-based models to tree-structured models.
- The experiments on compositional generalization reveal some of the non-obvious facts for transformer models' behavior in predicting compositional structures.

Weaknesses
- The conclusion found by the tree projections, i.e., transformer learns a compositional, tree-structured computation is actually not a new finding, which can be found in many previous works.
- The tree projection here is more like a tool for ablation studies. I can not tell how we can use this tree projection to improve downstream tasks such as compositional generalization.
clarity,_quality,_novelty_and_reproducibility: The conclusion found by the paper is not new/surprising to me. Some previous work has already discussed that neural models (including pre-trained models but not limited to transformers) in natural language processing have the ability to learn linguistic structures, e.g., Shen et al. (2019), Coenen et al. (2019), Hewitt and Manning (2019). The important point is how we can utilize this to help the downstream tasks, and I cannot see so much discussed in this paper.

Reference
[1] Ordered Neurons: Integrating Tree Structures into Recurrent Neural Networks. Yikang Shen, Shawn Tan, Alessandro Sordoni and Aaron Courville. ICLR 2019.
[2] Visualizing and Measuring the Geometry of BERT. Andy Coenen, Emily Reif, Ann Yuan, Been Kim, Adam Pearce, Fernanda Viégas and Martin Wattenberg. Neurips 2019.
[3] A Structural Probe for Finding Syntax in Word Representations. John Hewitt and Christopher D. Manning. NACCL 2019.
summary_of_the_review: This paper provides an interesting tree projection to reveal the transformer's ability to learn tree structure during training. However, the conclusion is not very surprising given that some previous work has already discussed similar findings. I agree that compositionally is an important linguistic property in natural language processing, but NLP people care more about how we can utilize compositionally in downstream tasks instead of whether the model can learn compositionally during training. I recommend the author incorporate this tree projection into enhancing the model's generalizability to compositional generalization, e.g., under domain shift or limited training data.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proposes an unsupervised and parameter-free method that functionally projects Transformer models into the space of all tree-structured models. Crucial to this, the authors assume the hypothesis that inner composition should be independent from outer context. Relying on this, the paper proposes the concept of span contextual invariance and ways to measure it. This results in a method that searches for a tree that is closest to the computation of a Transformer and then two ways are introduced to measure tree structuredness.

Strengths:
* The paper is well written.
* Theorem 1 helped formalize how the work projects Transformers to the space of tree structured computations.
* The approach is novel and interesting.
* The tree projections require no extra training and can be applied to any Transformer-based models.
* Experiments on compositional generalization reveal some insights into Transformer models' behaviour.

Weaknesses:
* The flow of the paper could be more logical.
* The problem could be more well motivated. The tree structured computation hypothesis is only one possible explanation for generalization. What is special about this avenue?
* It's somewhat already assumed that Transformers learn a compositional tree-structured computation.
* The tree projection approach here is mostly an analysis tool, it would be interesting if this could be directly used to improve downstream task performance.
* The approach presents context-invariance as an important ingredient for compositionality even though there are many exceptions to this in language.
justification_for_why_not_higher_score: The paper's audience is likely a subset of the NLP community with limited applicability to the wider ICLR audience. The work also presents an analysis tool and doesn't take the extra step of showing how to improve Transformer models with their finding.
justification_for_why_not_lower_score: The work presents a novel and interesting approach to analyse and understand the computation in Transformer models and to show that is tree-structured without the doubts that exist with probe based approaches.
Decision: Accept: poster