Characterizing intrinsic compositionality in transformers with Tree Projections
Authors: Shikhar Murty
Pratyusha Sharma
Jacob Andreas
Christopher D Manning
Venue: ICLR 2023 poster (2023)
Keywords: Transformers
Unsupervised syntax
hierarchical computation
compositionality

Abstract: When trained on language data, do transformers learn some arbitrary computation that utilizes the full capacity of the architecture or do they learn a simpler, tree-like computation, hypothesized to underlie compositional meaning systems like human languages? There is an apparent tension between compositional accounts of human language understanding, which are based on a restricted bottom-up computational process, and the enormous success of neural models like transformers, which can route information arbitrarily between different parts of their input. One possibility is that these models, while extremely flexible in principle, in practice learn to interpret language hierarchically, ultimately building sentence representations close to those predictable by a bottom-up, tree-structured model. To evaluate this possibility, we describe an unsupervised and parameter-free method to \emph{functionally project} the behavior of any transformer into the space of tree-structured networks. Given an input sentence, we produce a binary tree that approximates the transformer's representation-building process and a score that captures how ``tree-like'' the transformer's behavior is on the input. While calculation of this score does not require training any additional models, it provably upper-bounds the fit between a transformer and any tree-structured approximation. Using this method, we 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. These trees, in turn, are predictive of model behavior, with more tree-like models generalizing better on tests of compositional generalization.

Published as a conference paper at ICLR 2023
CHARACTERIZING INTRINSIC COMPOSITIONALITY IN TRANSFORMERS WITH TREE PROJECTIONS
Shikhar Murtyl Pratyusha Sharma Jacob Andreas
Christopher D. Manning'
CComputer Science Department, Stanford University MMIT CSAIL. (smurty, manning) mamnnnggesssttaooor.... (pratyushe,
ABSTRACT
When trained on language data, do transformers learn some arbitrary computation that utilizes the full capacity of the architecture or they learn a simpler, tree- like computation, hypothesized to underlie compositional meaning systems like human languages? There is an apparent tension between compositional accounts of human language understanding, which are based restricted bottom-up com- putational process, and the enormous success of neural models like transformers, which can route information arbitrarily between different parts of their input. One possibility is that these models, while extremely flexible in principle, in practice learn interpret language hierarchically, ultimately building sentence representa- tions close to those predictable by bottom-up, tree-structured model. To evaluate this possibility, we describe an unsupervised and parameter-free freee method to func- tionally project the behavior of any transformer into the space of tree-structured networks. Given an input sentence, we produce binary tree that approximates the transformer's perreseennttionuuuddiiiii process and score that captures how "tree- like" the transformer's 's behavior is on the input. While calculation of this score does not require training any additional models, provably upper- bounds the fit between a transformer and any tree-structured approximation. Using this method, we 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 su- pervised parsers. These trees, in turn, are predictive of model behavior, with more tree-like models generalizing better on tests of compositional generalization.
INTRODUCTION
Consider the sentence Jack has more apples than Saturn has rings, which you have almost cer- tainly never encountered before. Such compositionally novel sentences consist of known words in unknown contexts, and can be reliably interpreted by humans. One leading hypothesis suggests that humans process language according to hierarchical tree-structured computation and that such a restricted computation is, in part, responsible for compositional generalization. Mcanwhile, pop- ular neural network models of language processing such the transformer can in principle, learn an arbitrarily expressive computation over sentences, with the ability to route information between any two pieces of the sentence. In practice, when trained on language data, do transformers instead constrain their computation to look equivalent to tree-structured bottom-up computation?
While generalization tests benchmarks (Lake & Baroni 2018 Bahdanau et al. 2019 Hupkes et al. 2019: Kim & Linzen 2020 among others) assess if a transformer's 's behavior is aligned with tree-like models, they do not measure if the transformer's computation tree-structured. largely because model behavior on benchmarks could entirely be due to orthogonal properties of the dataset (Patel et al. 2022). Thus, to understand if transformers implement tree-structured computations, the approach we take is based on directly approximating them with a separate, tree-structured computa- tion. Prior methods based on this approach (Andreas) 2019 McCoy et al., 2019) require putatively gold syntax trees, which not only requires committing to specific theory of syntax, but crucially, may not exist in some domains due to syntactic indeterminacy. Consequently. these methods will fail to recognize model like if it is tree-structured according to different notion of syntax. Moreover, all of these approaches involve an expensive training procedure for explicitly fitting a tree-structured model (Socher et al. 2013 Smolensky 1990) to the neural network.

---

Published as a conference paper at ICLR 2023
S
12
S14
de Fys
S13
S24
Transformer Encoder
S12
$23
S34
ned
apples
delicious
S11
S22
$33
S4
red
apples
delicious
tree score
[i]
Attention Mask
Encoder
red
apples
are
delicious
apples
are
delicious
(a)
(b)
Figure 1: (a) Given transformer model f our method finds the tree projection of f i.e., binary trees corresponding to the tree-structured neural network 96 (in the space all tree-structured models) that best approximates the outputs of f given set of strings. (b) (i) Given string, compute context-free representations (Dij) for all spans of the string via attention masking (Section 3). (ii)
We use the distance between evverage-pooles context-free and contextual representations (Diz) to populate a chart data structure. (iii) We decode a tree structure from chart entries.
Instead, present method that is completely unsupervised (no gold syntax needed) and parameter-free (no neural network fitting needed). At a high level, our proposed method function- ally projects transformers into the space of all tree-structured models, via an implicit search the joint space of tree structures and parameters of corresponding tree-structured models (Figure The main intuition behind our approach is appeal the notion representational invariance: bottom-up tree-structured computations over sentences build intermediate representations that are invariant outside context, and so we can approximate transformers with tree-structured compu- tation by searching for a "bracketing" of the sentence where transformer representations of inter- mediate brackets are maximally invariant to their context. Concretely, main workhorse of our approach is subroutine that computes distances between contextual and context-free representa- tions of spans of a sentence. We use these distances to induce iree projection of the transformer using classical chart parsing (Section along with
that estimates tree-structuredness.
First, we prove that our approach can find the best tree-structured account a transformer's ' compu- tation under mild assumptions (Theorem []. Empirically, we find transformer encoders of varying depths become more tree-like as they train on three sequence transduction datasets, with correspond- ing tree projections gradually aligning with gold syntax two of three datasets (Section 5). Then, we use tree projections as tool to predict behaviors associated with compositionality: induced trees reliably reflect contextual dependence structure implemented by encoders (Section and both tree scores as well as parsing Fl of tree projections better correlate with compositional generalization to configurations unseen training than in-domain accuracy on of three datasets [Section|6.)
BACKGROUND
How compute the meaning of red apples delicious? Substantial evidence (Crain & Nakayama 1987] Pallier et al., 2011 Hale et al.) 2018) supports the hypothesis that semantic in- terpretation of sentences by humans involves tree-structured, hierarchical computation, where smaller constituents (red, apples) recursively combine into larger constituents (red apples), until we reach the full sentence. Concretely, suppose we have a sentence
{wi, W2,-.., w[s) Let T be function that returns binary tree for any sentence S, defined recursively as T(S) A (S))).) T(S where T(S.,t) refers subtree over the span Sa.b A (Wa, Wa+1 wp, We say that span Sa,b T(S) if the node T(S.,b) exists subtree in T(S). For notational venience, we sometimes use S, and S, as the left and right subtrees for T(S) i.., T(S) = S.).
We provide a fiunciional account of the transformer's computation and not topological account, i.e., we are agnostic to whether the attention patterns of the transformer themselves look tree structured-set see Appendix C for examples.
2

---

Published as a conference paper at ICLR 2023
Compositionality in Meaning Representations. While theories of compositional meaning for- mation might differ on specifics syntax, at a high-level, they propose that computing the meaning of S must involve bottom-up procedure along we say that a meaning representation system m is compositional the meaning m(() (8) of some ex- pression is homomorphic image of the syntax of i.e., m(s) ((m(s)), m)())) for some é following Montague (1970). Crucially, we note that such & exists only if m(s) can be fully determined by the contents of s, that is, if ms)) contextually invariant. While there several phenomena that necessarily require a non-compositional context-sensitive interpretation (indexicals, idioms, pronouns, lexical ambiguity among others), compositional interpretation remains a central component in explanations of the human ability to systematically interpret novel sentences.
syntax tree (S) of the sentence S. Formally,
Compositionality in Neural Models. A class of neural networks that are obviously composi- tional are tree-structured models such as Socher et al. (2013), that obtain vector representations of sentences by performing a bottom-up computation over syntax. Specifically, given S and a corre- sponding binary tree T(S), the output of the tree-structured network 96 is defined recursively-foo any span p E T(S), Do (p, T())) & (o( ((r)), 90 T(pr)) where ho : IRd x Rd + RRd is some feedforward neural network. For leaf nodes w;, (W;, T(w;)) Thoe where The E R represents the word embedding for w. The parameters the network are {8, Tun Tmas.....
3 OUR APPROACH
While tree-structured networks were built to reflect the compositional structure of natural language, they have been superseded by relatively unstructured transformers (Vaswani et al. 2017). How can we measure the computation implemented by a transformer is compositional and tree-like? We start by noting that in any bottom-up tree computation intermediate constituent depends only on the span corresponds to, while being fully invariant outside context. Thus, one way to assess tree-structuredness of a computation over some span is to measure contextual invariance of the resulting representation. Consequently, we construct tree-structured approximation of a transformer's computation over a sentence by searching for bracketing of the sentence where spans have maximal contextual invariance.
sentence, representation of an
3.1 SPAN CONTEXTUAL INVARIANCE
Suppose f is a transformer model that produces contextual where vi is contextual vector representation of w. Given span p, let S be the span representation of the contextual vectors of words in p. d = Ewep v Similarly, let Üp be context- free representation of the span p. For transformers, we obtain context-free free representations through a simple attention mask- ing scheme. In particular, to obtain Ü, we apply "T-shaped" attention mask and take the pooled representation of the words in at the final layer (Figure 2 The mask ensures that atten- tion heads do not attend tokens outside of after an optional threshold layer
vectors of words in S as f(S)= & {v v ...., v
rod
apples
are
delicious
We define span contextual invariance (SCT) of a span p in the sentence as SCI(S,p) & d(eş bp)) for some distance fune- tion d. Similarly, we define the cumulative SCI score for a tree to be:
We T-shaped at- tention mask with a threshold layer to obtain approximate context-free vectors for transformers.
Figure 2:
SCI(S,T) Σ Ed 0p)
(1)
SET
This procedure outputs vectors that are entirely context-free only if the threshold is exactly 0, but find that tuning the threshold layer often leads significantly hetter induced parses.
3

---

Published as a conference paper at ICLR 2023
3.2 COMPUTING TREE PROJECTIONS BY MINIMIZING SCI
Consider the collection of strings, D = {(S)}, and some function 7 that produces binary trees for any 5 E 'D. The cumulative error from approximating outputs of the transformer / with outputs of a tree-structured network Is structured according to 7 can be written as
C(f. 96. T) 2
E Σ
digo(p, T()),, of))
SED PET(S)
Suppose we are interested in finding the best tree-structured approximation to ff over all possible trees i.e. configuration of tree structures and corresponding model parameters that best approxi- mate the transformer's behavior. We define this the exact tree projection of f.
Oproj:
proj arg min mrgmin (ff.9.. TT. &,T
ESED minTes) SCI(S, T(S).. In other words, the best tree structured approximation to f has an enror upper bounded by cumulative SCI scores.
Theorem 1. mina,T L(S. 9o. T) S
In general, finding tree projections involves a joint search all discrete tree structures T(S) as well as over continuous parameters Ø, which is intractable. However, we substantially simplify this search using Theorem | since the upper bound depends only parses T(S) and properties of the transformer, and can be exactly minimized for a given f in polynomial time, with efficient parsing algorithms. We minimize this upper bound itself approximately recover the best tree-structured approximation to f. over all choices of trees and parameters. The output of this minimization is an approximate tree projection,
T pruj (S) = arg min SCI(S,T(S)) T(S)
(4)
for every S E Under a mild assumption SCT minimization leads tree projections exactly. Assumption 1. Let Sp denote the collection of sentences that contain the span Then, for every span we have min, EsEs, d(ep, v) = Eses, d(up 6p). That is, context-free vectors minimize the cumulative distance to their contextual counterparts.
Corollary 1.1. Under Assumption 7 ming.r Llf 96. T) over, Pmyj 5) = arg minr(s) SCI(S, for any S E D.
EseD minT(s) SCI(S, More-
3.3 MEASURING INTRINSIC COMPOSITIONALITY
SCI minimization provides two natural ways to measure intrinsic compositionality of f on D. To measure tree-structuredness, we use
ESED E, SCI( - SCI(S,Tpoo((
Lscore
(5)
|D]
which computes the averaged SCI score of induced trees, normalized against the expected SCI score under a uniform distribution over trees. We find normalization to be necessary to prevent our method from spuriously assigning high tree-srructuredness to entirely context-free free encoders (that have high SCI scores for all trees). When gold syntax T, is available, we use
parseval
PARSEVAL proj, Ty.D), D),
(6)
to measure bracketing Fl score (PARSEVAL: Black et al. [191] score of Tproj against T, on D.
4 EXPERIMENTAL SETUP
Our experiments are organized as follows. First, we show that on sequence transduction tasks, transformers of varying depths become more tree-like over the course of training, and sometimes learn tree projections that progressively evolve towards ground truth syntax. Then, we show how tree projections can be used to assess various model behaviors related to compositionality.
FFigure 9 in the Appendix shows that this assumption approximately holds in practice.
*Code and data will be available here
4

---

Published as a conference paper at ICLR 2023
Datasets. We consider three datasets (Table commonly used for benchmarking compositional
generalization COGS (Kim & Linzen 2020). M-PCFGSET (Hupkes et al., 2019 and GeoQuery
(Zelle & Mooney 1996). COGS consists of automatically generated sentences from context-free free grammar paired with logical forms, split into in-domain examples (for training) and a composition- ally challenging evaluation set. M-PCFGSET is slightly modified version Persionnof PCEGSET (Hupkes) itt al., 2019). where inputs are a nested sequence of expresssions that specify a unary or binary operation over lists. The objective is to execute the function specified by the input to obtain the final list. We focus on the "systematicity split" for measuring compositional generalization. Finally, GeoQuery consists of natural language queries about US geography paired with logical forms. To measure compositional generalization, we use the "query" split from Hiingan--Dollad et al. (0188).
Implementation Details. We use greedy top down chart parsing to approximately minimize SCI. In particular, we use SCI scores for all ((s)² spans of string S to populate a chart data structure, which is used to induce a tree by minimizing SCI via top down greedy procedure (see Algorithm Appendix), similar to Stern et (2017). Our procedure outputs a tree and simultaneously returns normalized SCT score of the tree, computing a sampling estimate of expected SCT score (Equa- tion 5) We train transformer encoder-dccoder models with encoders of depths {2. 4, 6} and fixed decoder of depth 2. We omit 6-layer transformer results for GeoQuery this model rapidly overfit and failed to generalize, perhaps due to the small size of the dataset. We choose a shallow de- coder to ensure that most of the sentence processing is performed the encoder side. We train for 100k iterations on COGS, 300k iterations on M-PCFGSET and 50k iterations on GeoQuery. We collect checkpoints every 1000, 2000 and 500 gradient updates and use the encoder these checkpoints to obtain parses as well as tree scores. In all experiments, d is cosine distance i.e., y d(<r, y) = |>| bll All transformer layers have attention heads and a hidden dimensionality of 512. We use a learning rate of le-4 (linearly warming up from 0 to le-4 over 5k steps) with the AdamW optimizer. All accuracies refer to exact match accuracy against the gold target sequence. For all seq2seq transformers, we tune the threshold layer based on parsevall
Inputs
Outputs
The ball was found A cookie war biessed
ball AND slad,zhane (z3,,
cookse AND blese. slesse.hhnnelee (233, 213
copy interfeave second reverse shift H13 C19 H9 020
Ha H13 020 C19
i..
repeat interleuve sevond interlanee firzt SI W3 NII 84
L3 R1 R13 112 Rt 722 18 R13 712 E1 112
Winch state has the lowestt population donsity? What is the population density Wyoming?
(A, Lemallest (B, ( 18) Ldensity (h, B)) I.dersity i8, Al, Joonat astateid (egeningt1
16.
Table 1: Example (Ir,)) v) pairs from COGS (i), M-PCFGSET (ii) and GeoQuery (iii). See Ap- pendix B for more details on pre-processing as well as dataset statistics.
5 TRAINED TRANSFORMERS IMPLEMENT A TREE-LIKE COMPUTATION
How does intrinsic compositionality of a transformer encoder evolve during the course of training on sequence transduction tasks? To study this, we plot lycore (how tree-like is a model?) and 'parseval (how accurate is the tree projection of model?) of encoder checkpoints throughout training. As a comparison, we track how well a supervised probe recovers syntax from encoders- that is, we train a layer transformer decoder to autoregressively predict linearized gold parse trees of S from transformer outputs f(S) at various points of training, and measure the PARSEVAL score of probe outputs (Pparseval) on a test set.
Results. We plot Exurseval and Éwcore over the course of training in Figure We observe that 7/8 encoders gradually become more tree-like i.e., increase facore over the course of training. with the 4 layer transformer on GeoQuery being the exception. Interestingly, we note that purseval also increases over time for all encoders on COGS and M-PCFGSET suggesting that the free projection of trained transformers progressively becomes more like ground-truth syntax. In other words, all encoders trained on COGS and M M-PCFGSET leam a computation that is gradually more "syntax aware". Can supervised probing also reveal this gradual syntactic enrichment? We plot PARSEVAL score of
'see Appendix B for details.
5

---

Published as a conference paper at ICLR 2023
0.30
0.12
0.10
0.4
0.25
0.20
Mag heyliimee
0.06
0.2
0.04
0.10
Layers
0.02
0.05
4 Lavers Layers
0.00
20
40
60
S0
100
50
100
1.50
200
250
300
10
30 thousand steps
20
50
thousand steps
thousand steps
(a) Normalized Tree Scores for COGS, M-PCFGSET and GeoQuery (f is better).
0.75
0.45
0.14
2 Layers
0.70
4 Layers
0.65
0.40
0.42
6 Layers
0.60
0.35
0.35
0.50
0.30
0.38
0.45
0.40
0.25
0.36
150
thousand staps
thousand stags
thousand steps
(b) Parsing Accuracies for COGS, M-PCFGSET and GeoQuery (f is better).
Figure 3: We plot Eycore and purreval by computing approximate tree projections at various check- points. 7/8 models become more tree-structured (increased (score) and all models on COGS and M- PCFGSET learn tree projections that gradually align with ground truth syntax (increased pprrseval). ).
parse trees predicted by the probe on held out sentences (Pparseval) in Figure 4 while Pparseval does improve over time both COGS and M-PCFGSET, we observe that all checkpoints after some threshold have similar probing accuracies. We quantitatively compare gradual syntactic enrichment by computing the spearman correlation between farseval (Pparseval) and training step and find that Prinnes is significantly smaller than Piynors for both datasets. Interestingly, we also find that our unsupervised procedure is able to produce better trees than the supervised probe on M-PCFGSET as observed by comparing Pperseval and Epaneeval Overall, we conclude that supervised probing is unable to discover latent tree structures as effectively as our method.
How does supervisory signal affect compositionality? Could purely self-supervised objective (i.e., no output logical form supervision) also lead to similar emergent tree-like behavior? To test this, we experiment with training the transformer encoder with a masked language modeling objec- tive, similar to Devlin et al. (2019) for COGS and GeoQuery. Concretely, for every S, we mask 15% of input tokens and jointly train transformer encoder and layer feedforward network, to produce contextual embeddings from which the feedforward network can decode word identities for masked out words. As before, we collect checkpoints during training and plot both fparseval and Iscore over time in Figure We find that /parseval does not improve over time for any of the mod- els. Additionally, we find that /score increases for models on GeoQuery, but only for the layer model on COGS. Taken together, these results suggest that under the low data regime studied here, transformers trained with self-supervised objective do not learn tree-structured computations.
TREE PROJECTIONS AND MODEL BEHAVIOR
Given S, and corresponding contextual vectors f(S), the contextual dependence structure captures the dependence between contextual vectors and words in S i.e., how much does v change when Wy is perturbed to a different word. Contextual dependence structure important for assessing compositional behavior. For instance, consider the span p= red apples appearing in some sentences. the contextual vectors for has large dependence on outside context, we expect the model to have poor generalization the span appearing in novel contexts i.e., poor compositional generalization.

---

Published as a conference paper at ICLR 2023
0.40
0.47
0.965
0.35
0.65
0.782
17.02
20.2
0.15
0:51
0.36
Spmermn Dier ba22
Spearass Cary - 780
00 300 0.10
Spaarmon Coe: 0.250
Sprtrmon Cor: 0.884
26
43
60
6o
100
30
200
130
200
230 390
20
100
139
200 230 300
(a) COGS
(b) M-PCFGSET
Figure 4: We plot Ppurseval and 'pansvval over time for the 4 layer transformer encoder on COGS and M-PCFGSET. We find that fparseval improves gradually over time suggesting that the model becomes more "syntax aware". Such gradual syntax enrichment is not uncovered well by the probe since all checkpoints after 4000 (for COGS) and 50000 (for M-PCFGSET) iterations have similar Pparseval
0.53
2 Lapars
Layers
0.23
0.25
0.10
0.50-
Layers
0.20
5.17
3.43
$8.1
9.43
0.12
2 Laseo Lapers Layer
0.35
0.16
0.08
20
(a) Parsing Accuracies
(b) Normalized Tree Scores
Figure 5: We plot paasevall and fucore at various checkpoints for models trained with a masked lan- guage modeling objective on COGS (first) and GeoQuery (second). Only 2/5 models become tree- structured and none learn tree projections aligned with gold syntax, suggesting that self-supervision may fail to produce tree-like computation in relatively low data regime.
We first show that tree projections reflect the contextual dependence structure implemented by transformer. Next, we show that both woore and /parseval are better predictors of compositional gener- alization than in-domain accuracy.
6.1 INDUCED TREES CORRESPOND TO CONTEXTUAL DEPENDENCE STRUCTURE
Intuitively, greedily decoding with SCT populated chart makes split point decisions where resulting spans are maximally invariant with one other. Thus, for a given constituent с and a word w E c, we expect a to de- pend more words within the same constituent than words outside the constituent. Thus, we compare the change in S when another word inside is perturbed (in-contituent perturbations) to the change when a word outside perturbed (out-of-constituen perturbations), where word perturbations are performed by adding gaus- sian noise to corresponding word vectors in layer 0 (see Figure 6). We ensure that both perturbations are made to words at the same relative distance from w. As control, we also compute changes to V when perturbations are made with respect to constituents from random trees.
red
apples
are
delicious
In-constituue tinntittent
per perturbation
Wred
c
Out out-of--conse tuent.
perturbation
Warn
Figure 6:
For word w (apples) in con- stituent C, an in-constituent perturba- tion adds noise c ~ (O, 0.01) to an- other word's vector within (red) while an out-of-constiuent perturbation adds noise word vector at same relative distance outside (are).
Setup and Results. We sample 500 random inputs from each of COGS, M-PCFGSET and Geo- Query and consider encoders from all transformer models. We obtain the mean L-2 distance between the contextual vector of w in the original and perturbed sentence for in-constituent perturbations (Ato) and out-of-constituent perturbations (A.c) and plot the relative difference between the two in Figure| 7 For 6/8 models, in-constituent perturbations result in larger L2 changes than out- of-constituent perturbations (statistically significant according to a two-sided t-test, p < 10-*). Meanwhile, when constituents are chosen according to random trees, changes resulting from both perturbations are similar. Overall, this suggests that induced trees reflect the contextual dependence structure learnt by a transformer.

---

Published as a conference paper at ICLR 2023
Sager 10005
Cagar loc0s)
2 Sagasy (rceossn
Ligara (rcessen
Lapess (tarkand
frea projections random trees
Lapes (Tarpuen)
5
10 15
20
25
30
35
Relative Increase (%)
Figure 7: We measure the mean L2 distance in the contextual vector of words when in-constituent and out-of-constituee words are perturbed. We plot the relative difference between Dic and A oc when constituents are obtained from tree projections (in blue). As control, we also compute Die and Doe when constituents are chosen from random trees (in orange). For all models except those marked with i, in-constituent perturbations lead to significantly (as measured by a (-test, 10-5) larger change to contextual vectors compared to oul-of-constituenn perturbations.
6.2 TREE-STRUCTURRDDESS CORRELATES BETTER WITH GENERALIZATION THAN IN-DOMAIN ACCURACY
We study the connection between compositionality and generalization for the 4 layer transformer encoder COGS and GeoQuery | On each dataset, train the model with 5 different random seeds and collect checkpoints every 1000/500 iterations. For each checkpoint, we measure accuracy on the in-domain validation set (IID acc) and accuracy the out-of- eralization set (CG acc). Additionally, we also compute 'panseval and weore for the encoders at each of these checkpoints. To measure the relationship between compositionality and generalization, compute the spearman correlation between parseval (fsoore) and CG acc and denote that as Ptaaaeal (o0 As comparison, we also compute the correlation between IID acc and CG acc (O).
compositional gen-
Results. We plot the relationship between various properties and generalization along with cor- responding correlations Figure X In general, we expect both IID ace and CG acc to improve together over time, and so it is unsurprising to see that PIDD 0. Moreover, for COGS, both parseval and locore increase over time, and so it is expected that both Pr and D are positive. Crucially, however, we find that both CG Plyaeeva and Plane are greater than CG on both COGS and GeoQuery. Thus, tree-like behavior (Ascore) as well as the right tree-like behavior (lparseval) are better predictors of compositional generalization than in-domain accuracy. This result gives simple model selection criteria to maximize CG accuracy in the absence a compostional generalization test set (true for most practical scenarios) given a collection of checkpoints with similar in in-domain accuracies, choose the checkpoint with highest fwcore or fuuseeval (if syntactic annotations are available) to get the model with best generalization behavior, in expectation.
RELATED WORK
Measuring Linguistic Structure. A common analysis tool for assessing model's competence in a specific linguistic phenomenon behavioral testing (Linzen et al., 2016 Marvin Linzen| 2018 Ribeiro al. 2020), where the model's performance on curated test set is used the measure of competence. Widely used in prior work to assess compositionality of neural models (Lake & Baroni 2018 Bahdanau et al. 2019 Yu & Ettinger 2020). behavioral tests are inherently extrinsic, since they are agnostic to whether the model implements an appropriately constrained, tree-like computation. While most prior approaches for assessing intrinsic compositionality (Andreas) 2019 McCoy et al.] 2019) require putatively gold syntax trees, our proposed approach does not require any deteemmedddded ground truth syntax, since we search over the space of all possible trees find the best tree structure that approximates transformer's 's computation.
Tree-structured Neural Networks. Inspired by the widely accepted belief that natural language mostly tree-structured (Chomsky 1957). there have been several attempts construct tree shaped
'II acc perfectly predicts generalization for M-PCFGSET so we omit it in these experiments
8

---

Published as a conference paper at ICLR 2023
174
Spearman OAT
Sqeaman Coer 6:313
Spaartann Corr 0.400
3D
4.20
033
112
Specrman
Spearmon 6,100
422
03x
(a) IID acC vs CG acc
(b) facore vs CG acc
(c) Eaarseaal Vs CG acc
Figure& 8: We plot the spearman correlation between (a) IID acc and CG acc, (b) ssoree and CG acc, (c) fparseval and CG acc. We find that both fpurseval and &uooe correlate better with generalization than in-domain accuracy. All correlations are statistically significant (p-values < 10-3)
neural networks for various NLP tasks, such as Recursive Neural Networks (Socher et al. 2013 Tree RNNs (Tai et al. 2013), Recurrent Neural Network Grammars (Dyer al.] 2016). Neural Module Networks (Andreas et al. 2016), Ordered Neuron (Shen et al. 2019) among others. These approaches have largely been superseded by transformers (Vaswani et al. 2017), often pre-trained on large corpus of text (Devlin et al. (2019), inter alia). We show that transformers, though not explicitly tree-structured, may still learn to become tree-like when trained on language data.
Invariances and Generalization. The general problem of studying model performance under do- main shifts has been widely studied under domain generalization (Blanchard et al., (011). When domain shift is result of changing feature covariates only, an effective strategy for domain gener- alization is to learn domain invariant representations (Muandet et al. 2013 Ganin et al. 2016). We apply the notion of domain invariance the context of compositional generalization, and posit that models that produce span representations that are more contextually invariant can generalize better to inputs where the span appears in a novel context, which is precisely the motivation behind SCI.
CONCLUSION
When trained on language data, how can we know whether transformer learns a compositional, tree structured computation hypothesized to underlie human language processing? While extrin- sic behavioral tests only assess the model is capable of the same generalization capabilities as those expected from tree-structured models, this work proposes an intrinsic approach that directly estimates how well a parametric trec-structured computation approximates the model's computa- tion. Our method is unsupervised and carameter-free and provably upper bounds the representation building process of a transformer with any tree-structured neural network, effectively providing a functional projection of the transformer into the space of all tree structured models. The central conceptual notion in our method is span contextual invariance (SCI) that measures how much the contextual representation of span depends on the context of the span vs. the content of the span. SCI scores of all spans are plugged into a standard top-down greedy parsing algorithm to induce a binary tree along with corresponding tree score. From experiments, we show that tree projec- tions uncover interesting training dynamics that a supervised probe is unable to discover- we find that on 3 sequence transduction tasks, transformer encoders tend to become more tree-like over the course of training, with tree projections that become progressively closer to true syntactic deriva- tions on 2/3 datasets. We also find that tree-structureednes as well as parsing Fl of tree projections is better predictor of generalization to a compositionally challenging test set than in-domain ac- curacy i.e., given a collection of models with similar in-domain accuracies, select the model that is most mike for best compositional generalization. Overall, results suggest that making further progress on human-like like compositional generalization might require inductive biases that encourage the emergence of latent tike-like structure.

---

Published as a conference paper at ICLR 2023
9 ACKNOWLEDGEMENTS
SM was funded by a gift from Apple Inc. JA is supported by the MIT Quest for Intelligence through a grant from Liberty Mutual Insurance. CM is a fellow in the CIFAR Learning in Machines and Brains program. We thank Ekin Akyürek, Marco Tulio Ribeiro, John Hewitt, Alexis Ross and members the Stanford NLP group for feedback on early drafts on the paper.
REFERENCES
Jacob Andreas. Measuring compositionality in representation learning. In International Confer- ence Learning Representations, 2019. URL https::// https://openrev.eww net font//foummiioo
Hoz05o0qK7
Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein. Neural module networks. In Computer Vision and Pattern Recognition (CVPR), 2016.
Dzmitry Bahdanau, Shikhar Murty, Michael Noukhovitch, Thien Huu Nguyen, Harm de Vries, and Aaron Courville. Systematic generalization: What is required and can it be learned? In International Conference on Learning Representations (ICLR), 2019.
E. Black, S. Abney, D. Flickenger, C. Gdaniec, R. Grishman, P. Harrison, D. Hindle, R. Ingria, F. Jelinek, J. Klavans, M. Liberman, M. Marcus, S. Roukos, B. Santorini, and T. Strzalkowski. A procedure for quantitatively comparing the syntactic coverage of English grammars. In Speech and Natural Language: Proceedings Workshop Held at Pacific Grove, California, February 19-22, 1991, 1991. UBL.htttee://alllaattoooooo..oe http:/loooooo.o1111o1/11111111 1060
Gilles Blanchard, Gyemin Lee, and Clayton Scott. Generalizing from several related classification tasks new unlabeled sample. Advances in neural information processing systems, pp- 2178-2186, 2011.
Noam Chomsky. Syntactic Structures. Mouton and Co., The Hague, 1957.
Stephen Crain and Mineharu Nakayama. Structure dependence in grammar formation. formationnLLanuuaee Language, 63 (3):522-543, 1987. ISSN 00978507, 15350665. URL http: //tp:://wwww http:://wwwwww....oooooo wtt.oooogooottaalllooooo.. 415004
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT; Pre-training of deep bidirectional transformers for language understanding. In Association for Computational Linguis- fies (ACL.), pp. 4171-4186, 2019.
Chris Dyer, Adhiguna Kuncoro, Miguel Ballesteros, and Noah Smith. Recurrent neural network grammars. In North American Association for Computational Linguistics (NAACL), 2016.
Catherine Finegan-Dollats Dollak, Jonathan K. Kummerfeld, Li Zhang, Karthik Ramanathan, Sesh Sadasi- vam, Rui Zhang, and Dragomir Radev. Improving text-to-SQL evaluation methodology. In Pro- ceedings of the 56th Annual Meeting of the Association for Computationnal Linguistics (Volume 1: (
Long Papers), pp- 351-360, Melbourne, Australia, July 2018. Association for Computational Lin- guisties. doi: 10. 10.18653/v1/P18. 1033. URL aclalnlltttt awtaahhhhoogoo wwwphhhwwl.o.gg.ooooooeo wrw/orggg/..
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, Francois Laviolette, Mario March, and Victor Lempitsky. Domain-adversarti training of neural networks. Journal of Machine Learning Research (JMLR), 17, 2016.
John Hale, Chris Dyer, Adhiguna Kuncoro, and Jonathan Brennan. Finding syntax in human en- cephalography with beam search. In Proceedings of the 56th Annual Meeting of the Associa- tion for Computational Linguistics (Volume 1: Long Papers), pp. 2727-2736 Melbourne, Aus- tralia, July 2018. Association for Computational Linguistics. doi: 10.18653/v1/P18 1254. URI. https: //aa:///all antho ooo.og..oo. wwtp:/gg//111111111
Dieuwke Hupkes, Verna Dankers, Mathijs Mul, and Elia Bruni. The compositionality of neural networks: integrating symbolism and connectionism. CoRR, abs/1908.08351 083119000000111112011 2019. Utthttp:
908 08351
10

---

Published as a conference paper at ICLR 2023
Najoung Kim and Tal Linzen. COGS: A compositional generalization challenge based semantic the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 9087-9105, Online, November 2020. Association for Computational Linguistics. doi: 12016663///0000emmmlym 2020. emn p-mmmlp-aiii wn..maii....... 731
interpretation. In Proceedings the
URL https: : / antho ogy. org/
Brenden Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of seuueecceto--equenee recurrent networks. In International Conference on Machine Learning (ICML), 2018.
Tal Linzen, Emmanuel Dupoux, and Yoav Goldberg. Assessing the ability of LSTMs to learn syntax- sensitive dependencies. Transactions of the Association for Computational Linguistics, 4:521- 535, 2016.
Rebecca Marvin and Tal Linzen. Targeted syntactic evaluation of language models. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 1192-1202, Brussels, Belgium, Oetober-November 2018. Association for Computational Linguistics. URL
https:///e www. aclweb. wwtp:eww.org/nttaaeageeee httgg//nnholggy//// 1ttpooooyy/DB-1111
R. Thomas McCoy, Tal Linzen, Ewan Dunbar, and Paul Smolensky. Rnns implicitly implement tensor product representations. In International Conference on Learning Representations (ICLR), 2019.
Richard Montague. Universal grammar. Theoria, 36(3):373-398 1970.
Krikamol Muandet, David Balduzzi, and Bernhard Schölkopf. Domain generalization via invari- ant feature representation. In ICML, pp. 10-18, 2013. URL httt:://procceedd ngs ngs mm
(ress/v28/muandett html
Christophe Pallier, Anne- tame-Domniique Devauchelle, and Stanislas Dehaene. Cortical representation of the constituent structure of sentences. Proceedings of the National Academy of Sciences, 108(6): 2522 2527, 2011. doi: 10.1073/pnas.10133 1018711108. URL https: /wwp://wwwww/////w/// pnas org/doi/
abs 11.1110011331111 http:///maaa.1111111111111111111 1018711108
Arkil Patel, Satwik Bhattamishra, Phil Blunsom, and Navin Goyal. Revisiting the compositional generalization abilities of neural sequence models. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pp. 424 434, Dublin, Ireland, May 2022. Association for Computational Linguistics. doi: 10.11865//1/2022.aclshh 46. URL httpt::://// /tctps://aclantiee http:/acaantttt ogy.
short..4h......
Marco Tulio Ribeiro, Tongshuang Wu, Carlos Guestrin, and Sameer Singh. Beyond accuracy: Behavioral testing of NLP models with CheckList. In Proceedings of the 58th Annual Meet- ing of the Asxociation for Computational Linguistics, pp. 4902 4912, Online, July 2020. As- URL https:
sociation for Computational Linguistics. doi: 10. w/acllantholog..orgg//o a0l.mm2m0a..lmmaaa1mmmm 442.
Yikang Shen, Shawn Tan, Alessandro Sordoni, and Aaron Courville. Ordered neurons: Integrating tree structures into recurrent neural networks. In International Conference on Learning Repre- sentations, 2019. URL httl:/ttts///peeeeeii//
Paul Smolensky. Tensor product variable binding and the representation of symbolic structures in connectionist systems. Artificial Intelligence, 46(1):159-216, 1990. ISSN 0004-3702. doi:
URL https: /tt::///wwwwww www. sciencedireetrtt.
Richard Socher, Alex Perelygin, Jean Y Wu, Jason Chuang, Christopher D Manning, Andrew Y Ng, and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Empirical Methods in Natural Language Processing (EMNLP), 2013.
Mitchell Stern, Jacob Andreas, and Dan Klein. A minimal span-based neural constituency parser. In Association for Computational Linguistics (ACL), pp. 818-827, 2017.
11

---

Published as a conference paper at ICLR 2023
Kai Shen Tai, Richard Socher, and Christopher D. Manning. Improved semantic representations from tree-structured long short-term memory networks. Association for Computational Lin- guistics (ACL), 2015.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. arXiv preprint arXiv: 03762, 2017.
Lang Yu and Allyson Ettinger. Assessing phrasal representation and composition in transformers. In Proceedings of the 2020 Conference on Empirical Methods Natural Language Process- ing (EMNLP), pp. 4896-4907, Online, November 2020. Association for Computational Linguis- tics. doi: 1/2180 m97. URL /ttttttsr///aaaaataooooooooo///
emnlp ma ina.nn... 397
M. Zelle and R. Mooney. Learning to parse database queries using inductive logic programming. In Association for the Advancement of Artificial Intelligence (AAAI), pp. 1050-1055, 1996.
A PROOFS
Lemma 1. C(f,ge' ,T) S EsED SCI(S,
Proof. Let go. S,T) EE)(()) d(ga(s, T(s)), w. for any S E D, where is tree-structured network indexed by Φ TRP. The overall error of 9s on D is
(( Σ (ff El( S..))
SED
Let o² - arg
arg ming Eo T). Next, consider & Rp such that (s T()) = o, for all s E D.
Such è always exists for large enough p. since there exists unique Üg for any p given D and f.
Clearly, ((f.g,, S,T) = ExET(S) d(v;" ú.). By definition, we have
C(S,90r, T) 9f T)
(8)
Σ Σ SED eET(S)
((..0,.) = =000oan SCI(S,
(9)
SED
EsED miny(s) (C))), In other words, the best tree structured approximation to f has an error upper bounded by cumulative SCI scores.
Theorem 1. ming.T L(f 96. T) <
Proof. We have
min L(f. 96. T) o,7
=min
min min L(f.go.
(10)
T
For any given T, we have ming L(S 06, T) < E (C((S,
Thus minimizing both sides
with respect to T, we have
min min L(S 16. T) < min SCT(S,T(S))
(11)
SED
Σ
min SCI(S,
(12)
T())
SED
n
12

---

Published as a conference paper at ICLR 2023
and Under A and Theorem I we have the proof for Corollary 1.1 which present next.
Corollary 1.1. Under Assumption 7 min L(f. 96. T) = SED minr(s) SCI(S, More-
over, pro (S) = arg ms))(s) SCI(S, for any S E D.
Proof. Let sT be the collection of all spans that occur constituent for some T(S) where 5 E D.
We have
[ff.9o: T) = Σ
Σ
((s)s, v.))
(13)
SED (E)(S)
Σ
Σ
d(go(s, T(s)),
(14)
SES,
Now, using Assumption 1 we note that
dg (())),
min
Σ d(v. =
Σ SES.
d(ö,, v2).
(15)
SES,
SES.
Combining Equation
15 and Lemma
we have
min [(S.9o, ,0, T) = Σ
SCI(S,
(16)
SED
Now, we have
T pnj arg
argginn min [min L(J.gs, /o, 7)] arg min
Σ
SCI(S, T(S)
(17)
T
SED
Thus, Tpay( (5) = arg SCI(S,T(S))
Next, we consider specific examples of distance metric d, and what Assumption implies for context-free vectors Üg.
Example A.1. Suppose d the euclidean L2 distance i.e,, d(x, y) || y/l- Then, Assumption requires that U. 1s Eses, va
Proof Sketch. We have or = arg min, Eses, d(v; v) arg min, Eses, |/ - u Setting derivatives with respect O, we have V. [5 Eses, v.
Example A.2. Let be the cosine distance of x and y i.e., d(z,y) - tion requires that ú. [S.]
x" ||l|| all
Then, Assump-
1 Eses,
3
Proof Sketch. We have st arg min, Eses, d(v = arg max, Σ Esss, TT arg max, [| Eses, ( Thus, 2. = k Eses, |
1 D |el||
for any k > 0
B DATASET PREPROCESSING
Dataset statisties are in Table
We use the standard train, validation and test splits provided by Kim & Linzen 2020 where we use the "gen" split as our test set. The validation set is drawn from the same distribution the training data, while the test set consists of compositionally challenging input sentences.
COGS.
13

---

Published as a conference paper at ICLR 2023
COGS
PCFGSET
GeoQuery
1.0
1.0
1.0
d(vg, Vz) d(v Vi))
d(v Vi))
d(v Vz)
0.8
0.8
d(v Vs)
0.8
d(v Vg)
cosine dist
cosine dist
0.6
0.6
cosine
0.4
0.4
0.2
0.2
0.0
0.0
0.0
25
50
75
100
100
200
300
20
thousand steps
thousand steps
thousand steps
Figure 9: We plot d(v,, 0.) for randomly sampled spans at various points during training. As control, we also plot d(v.. ú,) for a random span Se. We observe that for COGS and GeoQuery, the distance between the optimal er and d, eventually becomes less than 0.05. We conclude that the conditions of Assumption TappunttoooTTppooiiiiiii approximateey hold true for 2/3 datasets.
Dataset
Train
Validaaioon
Test
COGS
24115
3000
21000
M-PCRGSET
65734
16434
10175
GeoQuery
Table 2: Dataset Statistics
M-PCFGSET. We make two modifications to the PCFGSET dataset. First, we remove commas from expressions so that the model forced implictly learn to correctly partition the input ex- pression for correct intrepretation. To ensure that unique parse exists even without commas, we additionally ensure that all lists have exactly 2 elements. For instance, the expression append C, D E F is modified into append A B E F that has the unique interpretation append ( [A, B], [E, F)) since all lists have exactly 2 elements. Second, we replace the remove.first where
and remove.second operations with interiiii wewerlleaeeiiree the interleave operation takes two lists (say A and C D) and interleaves them to either pro- duce A CBD or CAD B. This modification ensures that intermediate constituents in the expression are not discarded, similar to how intermediate constituents are almost never discarded in natural language utterances.
and
GeoQuery. We use the pre-processed JSON files corresponding to the query split from (Finegan- Dollak et al. 2018). We create 80/20 split of the original training data, create III validation set.
C FUNCTIONAL VS. TOPOLOGICAL TREE-STRUCTUREDNES
We emphasize that approach finds functional tree approximation to transformer, and not topological one. That is, we separate, tree structured neural network to vector representations from transformer, instead of decoding trre-structure from the attention patterns. As result, definition of tree-structuredness does not restrict the transformer's ss attention pattern to be necessarily tree structured (see Figure 10 for examples).
D ANALYZING INDUCED TREE STRUCTURES
We choose the checkpoint with best bracketing Fl score on the training split for all our datasets, and compute corresponding bracketing Fl scores the IID validation set in Table As baseline, we compare with standard constituency parsing basclines: LBranch (choosing a completely left branching tree). RBBaach (choosing completely right branching tree) and Random (choosing
14

---

Published as a conference paper at ICLR 2023
Functionally Tree-like
Tree like
Φ
(ffred apples) (are)) (delicions))
(i)
Topologicall,
(fred apples) debicooss)
(iv)
We show instances of computations implemented by transformer on the input red apples are delicious along with tree projections our method outputs for each instance. We divide the space of possibilities into 4 quadrants. In quadrant-(i), we show instance that is both topologically as well as functionally tree-like. quadrant-(ii) is empty, since no transformer can be topologically tree-like but not good functional approximation to tree. In quadrant- that is either topologically nor functionally tree-like. Finally, in quadrant-(iv), we show a transformer that is functionally tree-like but does resemble structure topologically.
Figure 10:
show transformer
Method
COGS
M-PCRGSET
GenQuery
TreeProjections
75.6
46.5
48.0
Random
LBranch
30.2
17.9
26.0
RBranch
75.3
SK.1
69.7
Table 3: Parsing accuracies
random binary tree). Interestingly, we find that the trees discovered by our approach on COGS beats RBranch, which is competitive constituency parsing baseline for English.
Algorithm Tree Projections via greedy SCT minimization
1:
function TREEEPROJECTIONSS. f)
2: return 'RREEPRODECTTONEEERRRES,,, (S))))
3: end function
4: function TREEPROIECTTOVRRECUUSSSSS,
5: if = then
6:
D leaf node
7:
return wis
8:
else
9:
greedily select split point to minimize SC1 of resulting constituents k +- arg minna
10:
11:
Sy. SCI(S SCI(Sx++1,):
12:
b select a random split point for normalization
13:
86 SCT(S,,k,) SCT(Sk,,1.) Kb Úii
14:
> Recursively call the function to get tree structure and score for left span
St, tsı + PRIEPROIECTIOORECURREES
i,i,k");
16:
Recursively call the function to get tree structure and score for the right span f, 1,5);;
S,, ts, <- TREEPROIECTIOVREUURREE return (S), S,), Sş* + ts + tsp end
18:
19:
20:
end function
15


Reviews:
[{"review_id": "qHxeK2DeJWd", "reviewer": "Reviewer_7etS", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. \n\nThe 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. \n", "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. \n", "strength_and_weaknesses": "The main weakness of the paper is its motivation. Specifically:\n\n* 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. \n\n* 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.\n\n* 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.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "fHhime90m5", "reviewer": "Reviewer_mpue", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. \n\nTheoretically, 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.", "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. \n\nThe paper can improved by\n* adding more details about implementation (T-shape and threshold layer) \n* re-flow some experiments / arguments   ", "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. \n\nI 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\"? \n\nThe 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.\" \n\nHowever, 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. \n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "RoBjgMiZAM2", "reviewer": "Reviewer_2Wg3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. \n", "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.", "strength_and_weaknesses": "+ The paper is well written and was relatively easy for me to understand. \n+ Theorem 1 is helpful in formalizing how the proposed framework projects transformers to the space of tree structured computations\n+ The results appear convincing, with some minor caveats, mentioned below\n\n- 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\n- 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. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "IM7Ba_b2D_", "reviewer": "Reviewer_4grv", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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.", "strength_and_weaknesses": "Strength\n- The tree projections require no extra training and parameters and can be applied to any transformer-based models to tree-structured models.\n- The experiments on compositional generalization reveal some of the non-obvious facts for transformer models' behavior in predicting compositional structures.\n\nWeaknesses\n- 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.\n- 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.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster