Syntactic Substitutability as Unsupervised Dependency Syntax
Authors: Jasper Jian
Siva Reddy
Venue: EMNLP 2023 Main (2023)
Keywords: unsupervised dependency parsing
syntax
syntactic probing
linguistically informed

Abstract: Syntax is a latent hierarchical structure which underpins the robust and compositional nature of human language. In this work, we explore the hypothesis that syntactic dependencies can be represented in language model attention distributions and propose a new method to induce these structures theory-agnostically. Instead of modeling syntactic relations as defined by annotation schemata, we model a more general property implicit in the definition of dependency relations, syntactic substitutability. This property captures the fact that words at either end of a dependency can be substituted with words from the same category. Substitutions can be used to generate a set of syntactically invariant sentences whose representations are then used for parsing. We show that increasing the number of substitutions used improves parsing accuracy on natural data. On long-distance subject-verb agreement constructions, our method achieves 79.5% recall compared to 8.9% using a previous method. Our method also provides improvements when transferred to a different parsing setup, demonstrating that it generalizes.

the kids rum Syntactic Substitutability as Unsupervised Dependency Syntax
Jasper Jian and Siva Reddy 2,3
Stanford University
Mila Quebec Al Institute and McGill University Facebook CIFAR Al Chair
jjian@stanford.eda siva. reddy la. quebec
Abstract
Syntax latent hierarchical structure which underpins the robust and compositional nature human language. In this work, we explore the hypothesis that syntactic dependencies be represented in language model attention dis- tributions and propose new method induce these structures aggossiggnss...lly... Instead of modeling syntactic relations as defined by annotation schemata, we model a more gen- eral property implicit in the definition of depen- dency relations, syntactic substitutability. This property captures the fact that words either end of a dependency can be substituted with words from same category. Substitutions be used to generate set of syntactically invariant sentences whose representations are then used for parsing. We show that increas- ing the number of substitutions used improves parsing accuracy on natural data. On long- distance subject-verb agreement constructions, our method achieves 79.5% recall compared 8.9% using previous method. Our method also provides improvements when transferred to a different parsing setup, demonstrating that it generalizes.
nsubj dal
the
kids run in park with that ball.
the
girls run park with that ball.
the kids play in
with a park that ball.
park
ball.
Figure 1: Syntactic relations represent intersubstitutabil. ity: the nominal subject 'kids' can be substituted with another noun 'girls' without affecting syntactic well- formedness. Swapping the verb 'run' with 'play" and the preposition 'in' with 'to" are other examples for this sentence. Substitutions define a of sentences that can be used to model this property during parsing.
behaviour like long-distance subject-verb agree- ment (Marvin and Linzen, 2018; Gulordava et al., 2018: Goldberg, 2019), and (2) whether syntactic structures are retrievable from model-internal rep- resentations or mechanisms (Hewitt and Manning, 2019; Htut et al., 2019; Limisiewicz et al.. 2020). While the former approach is theory-agnostic, it does not require a specific syntactic form to be defined, it lacks the interpretability that inducing explicit structures provides,
1 Introduction
In recent years, large pretrained language models (LLMs), like BERT (Devlin et al., 2019), have led impressive performance gains across many nat- ural language processing tasks. This has led to a line of work attempting to explain how natural language understanding might occur within these models and what sorts of linguistic properties are captured. Going one step further, we explore the hypothesis that syntactic dependencies can be ex- tracted from LLMs without additionally learned parameters supervision.
do here.
Instantiating the latter approach, Hewitt and Manning (2019) train probe in order to project model representations words into new vector space where a maximum spanning tree algorithm (MST) can be applied to induce the desired syn- tactic parse. However, it is not clear whether such method relies solely on the information already present in the model, whether the trained probe is contributing model-external knowledge (Belinkov, 2022). A less ambiguous approach is instead use model-internal distributions directly input to the tree induction algorithm without additional training. In this vein, previous work has made use
Previous work on syntax has tested (1) whether language models exhibit syntactically dependent
Work done while the first author was at McGill University. The ende and data can be found at https//gihhu..co/MMccii NI. ieseyattttte-subbstttaabiili

---

of attention distributions from transformer-based LMs (c.g. Raganato and Tiedemann, 2018; Htut et al., 2019). This parallels observations made by Clark et al. (2019) that certain attention heads in BERT correspond to dependency relations. How- ever, given the large amount of information present in LLMs, nothing constrains the extracted parses to be syntactic parses when representations are used directly.
over scores between words in a sentence that rep- resent how likely it is for two words be in a syntactic dependency or how likely span corre- sponds to a syntactic constituent.
We seek to work with scores directly derivable from LLMs, following previous proposals which have used attention distributions of transformer- based models (Vaswani et al., 2017) calculate scores. Examples in dependency parsing include Raganato and Tiedemann (2018) who use neural machine translation models, and Htut et al. (2019) and Limisiewicz et al. (2020) who use BERT. For constituency parsing, Kim et al. (2020) propose a method based on the syntactic similarity of word pairs, calculated as function of their attention dis- tributions. The use of attention distributions for parsing tasks supported by the observation made by Clark al. (2019) that certain attention heads correspond to syntactic dependencies in BERT. However, they also observe that attention heads do not only capture syntactic information, but also other relationships like coreference. Our method proposes syntactic substitutability to address this issue, motivated in the next section. Previous work from Limisiewicz al. (2020) proposes an algorithm to select syntactically relevant heads, but we contend that this is maximally effective if the distributions within a single head also only capture syntactic information. We return this idea in Exper- iment 3 and investigate the effect of adding SSUD to this algorithm.
In this paper, we propose a novel method to dis- till syntactic information by modelling a general property of syntactic relations which is independent of any specific formalism. This property, syntactic substitutability, captures the intuition that syntac- tic structures define categories of intersubstitutable words illustrated in Figure We make use of this notion by enumerating syntactically invariant sentences which can then be exploited together to induce their shared syntactic structure. Our primary goal is to investigate whether modeling syntactic substitutability better extracts syntactic information from attention mechanisms, resulting in more accu- rately induced parses. Inducing structures without relying on specific annotation schemata also allows us to better understand how the syntactic relations represented in a model might be similar to existing thcoretical proposals.
We demonstrate that our method, Syntactic Sub- stitutaailitty as Unsupervised Dependency Syntax (SSUD) leads to improvements in dependency pars- ing accuracy. As more substitutions are used, parsing scores increase. We also quantitatively show that the induced parses align more with an annotation schema where function words are treated as heads (Experiment 1). When tested on long-distance subject-verb agreement construc- tions, SSUD achieves increase in recall of 770% compared previous unsupervised pars- ing method (Experiment 2). We also demonstrate how our method can be transferred to and improve different parsing algorithms, showing that SSUD generalizes effectively (Experiment 3).
Other complementary methods use BERT's con- textualized representations perform parsing. For example, Wu et al. (2020) propose a method which calculates scores based on the 'impact' that mask- ing word in the input has on the representations of the other words in the sentence, and Hewitt and Manning (2019) train a probe with supervision to project vectors into a 'syntactic' space. Another ap- proach is using BERT's masked language modeling objective to compute scores for syntactic parsing, Work in this vein include Hoover al. (2021) and Zhang and Hashimoto (2021), motivated by a hy- pothesis stemming from Futrell et al. (2019) that syntactic dependencies correspond to statistical measure of mutual information.
2 Related work
Our work is related to a long tradition of unsuper- vised syntactic parsing, for example, the genera- tive DMV model (Klein and Manning, 2004) and the compound Probabilistic Context Free Grammar model (Kim al., 2019) for constituency parsing. Motivations for this stem from the idea that syntac- tic parses can be induced by computing an MST
Lastly, while the non-parametric use of substi- tutability for syntactic parsing has not been pre- viously proposed, parallels can be drawn to work in language model interpretability. Papadimitriou et al. (2022) show that BERT systematically learns

---

use word-order information to syntactically dis- tinguish subjects and objects even when the respec- tive nouns are swapped. This is a special case of substitution: the syntactic structure of these sen- tences is invariant despite their non-prototypical meaning. We take these results to mean that BERT has a knowledge of syntax that is robust to substi- tution, and as result, substitutability may be an effective constraint.
All(s, =- (0.0 -.. a2 -.. Q(1-1)]
where dij refers the attention weight from w() to "(y). The sentence's attention matrix, Att(s), 6), is the n X n matrix where row is equal to All(s,)) i).
3.2 Attention distributions
For each word in sentence, attention heads BERT compute a distribution over all words in a sentence. Each row E [0, of All(s) corre- sponds to the attention distribution for word w())- Previous work has made use of attention distri- butions to extract syntactic trees by using MST algorithms over the attention matrix of a single sen- tence (Raganato and Tiedemann, 2018; Htut et al., 2019). The hypothesis here is that the attention scores between syntactically dependent words is higher than those that are not. Given this, the cor- rect undirected syntactic parse can be induced, i.e. M ST (At((s)) tx. if
3 Syntactic Substitutability and Dependency Relations
In this section, we propose method to model the formalism-neutral objective of substitutability within the induction of syntactic structures. This notion is often explicitly included in the defini- tion of syntactic grammars, see for example Hunter (2021) and Mel'čuk (2009). Intuitively, intersub- stitutable words form syntactic categories which syntactic relations operate on.
V(i.j) E {(a, b)] Dep (s, a, = V(y.2) E {(c, d) Depsymt (s, c, 0}
3.1 Problem statement
We wish to extract a tree-shaped syntactic depen- dency structure to for a sentence s from the mech- anisms or representations of an LLM. We denote the target sentence of length
ai > azz (1)
We suggest that the assumption being made in Equation 1 is incorrect, given that attention dis- tributions correspond to wide variety of phe- nomena again they need not be syntactic. For example, an edge in the induced tree may have been predicted due to a high score resulting from coreference or lexical similarity.
= (0): ((() .... Wn 1) >.
Edges in lg belong to the set of binary syntactic rela- tions Reynt- The specific relations that are included are relative to specific formalisms. We define
Depsyne (s, 1, e 1)
3.3 Modeling syntactic substitutability
which denotes whether not two words in sen- tence 8, (() and w(y). are in syntactic depen- dency relationship. If (sp i, 1, then 3r R Rynnt S.I. r' relates W(() and wiy denoted (i)))
We propose syntactic substinutability as a formalism-neutral method of extracting syntac- tic information from attention distributions. In- tuitively, syntactic grammar is defined in such way to offer an abstraction over individual lexical items and operate syntactic categories. Formalizing this, we make the assumption that any relation Rayst defines set of words that can be substituted for one another in a sentence. The formal definition that we begin with is referred to as the quasi-Kunze property in Mel'čuk (2009). There, relation is defined from a head word, (())) to a subtree which is rooted at another word, W(G)- For relation to be syntactic, it must define some class of words X, such that subtrees which are rooted words from X can be substituted into the original sentence without affecting syntactic well-formedness. An example of this is provided in Figure 2.
((()
where W()) < (iyy denotes an undirected relation. Given that relations are binary, matrix of scores between all words in a given sentence is required before syntactic trees can be induced. In this work, we propose attention distributions of self-attention heads as candidate scores. However, any method which calculates pairwise scores between words can be used here with change.
We denote the attention distribution for word (()) in the given sentence s, of length n as
'BERT's s lokenizer does not tokenize on words, but rather on subwords tokens. We follow Clark et al. (2019) and sum and normalize in order to convert from attention distributions over tokens to one over words.

---

the kids run in a park with the ball. the kids run to that yard with the ball.
et al., 2020).
This process allows us to model more fine- grained syntactic categories than sampling via POS alone. For example, the substitutions for the word 'thought' in Figure 3 demonstrate how not just any verb can be substituted for any other. Instead, cor- rect substitutions must be sensitive subcatego- rization (the syntactic argument(s) required). In this case, 'thought' requires a clausal complement, which 'figured'' and 'knew' both admit. Substitut- ing 'thought' with a verb like 'eat' would result ungrammaticality or an altered syntactic structure. We can denote sentence where the word at position j is replaced with word as s(x,, and the set of such sentences Suub(s, j. X). This is (s,
The subtree rooted at 'park' (underlined) is substituted for rooted at 'yard.'
Figure 2:
just thought you to know. (Target) always, simply, only thought you 'd like know.
just figured, knew, think you 'd like know.
just thought you 'd love, demand, have to know.
just thought you like to help. talk, stay
Figure 3:
set sentences generated via SSUD for a sentence taken from the WSJ10 dataset with example substitutions at each position listed.
We propose a modified form of this property defined in terms of the substitution of individual words since constraining substitutions to subtrees would be complex given an unsupervised process. Note, however, that this exactly equivalent to substituting subtrees which differ only in their root word. As previously stated, we make no assumptions about the directionality of these relationships.
defined on the syntactic category X as given Definition 1.
(s, (=)0))))
(2)
3.5 Inducing trees with syntactic relations
We will now explore how to apply this newly de- fined set of syntactically invariant sentences to the extraction of structures from attention distributions.
Given that our relations E Raynt satisfy Defi- nition 1, if Depsynt i,5) = 1, then 3r E Royst such that it relates Wit) and W(() and defines a syn- tactic category X of valid substitutions;
Definition Modified quasi-Kunze property: Let W(s) and W()) be words. For any relation r, if r Rayne- then there exists X, such that for any syntactic tree with relation w()) S W(j) replacing "'() with word X does not affect the sentence's syntactic well-formedness.
if Depsgma (s, i,j) = 11
then Vs' c Soub(s, Depoynt ,1,5) =
(3)
In our framework, we assume that for any rela- tion to be a syntactic relation, it must satisfy the modified quasi- Kuasi-KKnze property defined above. We demonstrate that this provides tractable objec- tive for inducing dependency structures.
Importantly, any sentence s' E (s j, X) has the same syntactic structure as the original, s.
Given this basic assumption of the properties of syntactic relations in a dependency grammar, we can now propose a method of extracting syn- tactic structures from LLM attention distributions. Rather than applying the M MT algorithm on the attention distributions of a single sentence, we ap- ply the MST over attention matrix which is derived by some algorithm, f applied over the set of attention matrices of the set of sentences created via substitution S i, X), Vi [0, n 1].
3.4 Generating sentences via substitution
In order to model the property in Definition 1, we generate candidate substitutions using LLM. In this work, we use BERT itself to predict possible substitutions using masked language modeling, a task for which was trained. We find that this gen- erates empirically correct sentence substitutions, as in Figure 3.
We choose to substitute all open-class cate- gories and some closed-class categories (adjectives, nouns, verbs, adverbs, prepositions, and determin- ers) with words from the same class. In order to do so, we use Stanza's ' Universal POS tagger (Qi
Att (s) = f((Att(s))))) (' E Ssub (8, 1, X);
E [0, n 1}}) (4)
2This is the strictest theoretical setting, however, see Ex- periment 3 for further discussion.

---

Recall that in the hypothesis represented by Equa- tion 1, the assumption is that words in syntactic de- pendencies have higher attention scores than those that are not. The new hypothesis that we test in this work is that using the attention distributions of a single target sentence may reveal little about syn- lactic dependencies, which we propose must satisfy Definition 1. Instead, we use the attention patterns over set of syntactically invariant sentences, as defined by the procedure we gave in $3.4.
glish dependency parsing datasets: (1) the sen- tence length < 10 test split (section 23) of the Wall Street Journal portion the Penn Treebank (Marcus et al., 1993) annotated with Stanford De- pendencies (de Marneffe et al., 2006) (WSJ10; 389 sentences), and (2) the English section of the Paral- lel Universal Dependencies dataset annotated with Universal Dependencies (Nivre et al., 2020) (EN- PUD; 1000 sentences). Additionally, we assess our parses with Surface- -Sytttcct Universal Dependen- cies annotations (Gerdes al., 2018; see $5.4). We use section 21 of the Penn Treebank as validation set. We also test our method on a more difficult, long-distance subject-verb agreement dataset from Marvin and Linzen (2018) (see Experiment 2).
Concretely, we test whether an averaged at- tention distribution over the set Ssub(i, x). E [0, n - 1] better reflects syntactic dependencies, i.e.
v(i,) E {(a, b)lb)))DDDPelle
= =1}, 2(y,2) E ((a d) Depsyme (8, -}.
The language model investigated here is BERT (Devlin al., 2019), transformer-based lan- guage model. Specifically, we focus on the model, which has 12 lay- ers with 12 self-attention heads each (110M param- eters). To test generalization with respect to model size, we also use bert-largn -arge-uncased (336M parameters) in Experiment 1.
aug(at,1vs' E (s, (x) >
ang(age) Ivs (su X)), (5)
and whether taking the maximum spanning tree of these averaged attention scores provides better re- sulting parses, l = MAT(AAlsuu(5)) Equations and provide a comparison between the previous work and our proposal.
Does modeling syntactic substitutability increase parse accuracy?
Additionally, we suggest the following function f for combining attention distributions between sen-
5.1 Experiment 1: Setup
tences: each row i in the output matrix is equal to the averaged tth row of the attention distributions over the sentences which are substituted at (()) i.e.
In Experiment 1.1, we induce trees over attention distributions computed by averaging all heads at a given layer. We apply our proposed method SSUD and compare the Unlabeled Undirected Attachment Score (UUAS, in Hewitt and Manning, 2019) of trees which are induced using only the attention dis- tributions of the target sentence, with trees resulting from applying SSUD. UUAS is calculated as the number of edges in the gold-annotated parse which are also predicted by the model, divided by the to- tal number of edges. In this experiment, we apply SSUD with A: 1 (one additional sentence per word) choose a layer. We expect SSUD to work only when syntactic information represented. In Experiment 1.2, we test the effect of SSUD by increasing the number of additional sentences used for each word, applying this on the best- performing layer from above. As syntactic sub- stitutability is modeled using sets of sentences, the effect is expected to be greater more appropriate substitutions are made.
Attsub(s) arg(1Attt(s (s))s E (,,,,,)))))) (6)
We define our method, SSUD, as tree induction for a sentence s, which uses an attention distri- bution, (t), produced by averaging over k substitutions at each position, [Saub(s, X)) k. Our experiments in the sections below inves- tigate whether modeling syntactic substitutabil- ity with SSUD results in the induction of better syntactic structures than using the target sentence alone. We test our hypothesis on standard datasets and long-distance subject-verb agreement construc- tions. SSUD is used in two different parsing setups, providing direct comparison with previously pro- posed tree induction algorithm.
4 Datasets and Models
In both experiments, we induce trees over the attention matrices using Prim's algorithm (Prim, 1957) which produces non non-projective undirected,
As in previous work (c.g. Hoover et al., 2021), we assess our method using two gtad-standard En-

---

unlabeled trees. This allows to investigate the ef- fect of modeling syntactic substitutability without making more assumptions about the directionality of the relations. Given this algorithm, the sentences which contribute the scores for all edges predicted could have been substituted at any position, includ- ing at either the head or tail of given dependency. We make assumptions regarding the projectivity of the resulting tree and apply this uniformly across the comparisons that we make. See Experiment for SSUD with an algorithm for directed trees.
UUAS
WSJ10
EN-PUD
Layer
T.
k:
=1
A
T.
k ==1
1
A
6
S7.3
57.3
0.0
44.8
44.8
0.0
56.3
56.4
0.1
44.2
44.1
-0.1
56.0
56.1
0.1
43.2
43.2
0.0
9
55.9
55.8
-0.1
43.9
44.0
0.1
10
55.7
56.8
1.1
44.3
44.7
0.4
Table 1: UUAS scores on WSJ10 and EN-PUD
(bert-base-uncaseet SSUD k 1 compared with only using target sentence (T.).
bert Hert-base-uud base-uncased (UUAS)
K
k
k=
5.2 Experiment 1.1: Results and Discussion
WSJ10 EN-PUD
55.7
56.8
57.0
57.3
$7.6
For bert base Daaseunccan uncased, the layer with the largest change in UUAS on the validation set be- tween using the target sentence and using SSUD is Layer 10 (Appendix A). This generalizes to the results on both test sets, Table 1. With bert-large-uncaseeee
44.3
44.7
45.6
46.2
46.4
bert - -ar--aareeeee wnceeennnnsedd...ee (UUAS)
peatt-aagg-uncasee
WSJI0
56.1
56.5
56.7
56.7
57.2
EN-PUD
45.5
45.8
46.2
46.6
47.0
Table 2: Results on WSJ-10 and EN-PUD
for bert bast-aaes- uncased (Layer 10) and
we observe that Lay- ers 17 and 18 perform the best (Table 9). As pre- dicted, this may reflect the fact that syntactic infor- mation is more robustly represented in these layers. For both the base and large models, our find- ings with regards to which layers contain retriev- able syntactic information corroborate previous work. We find that Layer 10 and Layers 17 and 18 perform best for the base and large models, respectively. Previous work in constituency parsing with the same models. Kim al. (2020), find that Layer 9 (base) and Layer 16 (large) perform best. Probing experiments have also previously shown that constituency information occurs before dependency information in BERT's representations (Tenney et al., 2019).
hert-large-uncased (Layer 17). Compari- son between using the target sentence alone (T.), and SSUD, with an increasing number substitutions, = 1,3,5, 10.
WSJI UUAS
EN-PUD
Method
UUAS
UAS
Ours - Exxerimmet
57.6
46.4
7hang and Hashimoto (2021)
58.74
Hoover et al. (2021)*
53.-
43,
Klein and Manning (2004))
55.91
Limisiewicz et al. (2020)*
59.9
52,8
Ours Experiment 3
62.0
54.5
Table 3: Results from Experiments and 3 are reported with comparisons previously proposed methods (best non-projective scores from seart--bas-uuncceedee 'not included due computation time; 'reported in Zhang and Hashimoto (2021); 'results are from mul- tilingual BERT, * *aas CPMI' trees experiment in the original paper; 1100 selection sentences' experiment in the original paper.
In Experiment 1.2, we further investigate the ef- feet of SSUD by providing more substitutions at each word (increasing k). For the following exper- iments, we use Layer 10 of the uncased model and Layer 17 of bert-large-uncaseee
5.3 Experiment 1.2: Results and Discussion
representations intrinsic to the model are robust to substitution, allowing SSUD to disentangle syntac- tic information better than using the target sentence alone. We provide further analysis of the results from the bert-base-uncasse model.
Table 2 provides the results as the number of sub- stitutions is increased. Improvements are seen for both models on WSJ-10 and EN-PUD. There is marginally larger increase for the EN-PUD dataset which has sentences of average length 17, compared to sentences of <10 for WSJ-10. The monotonic increase in UUAS as more sentences are added suggests that our method of modeling substitutability using sentence substitutions is an effective constraint for distilling syntactic informa- tion from models. It also suggests that the syntactic
In Table 3, we provide comparisons to other previously proposed methods. We that SSUD is competitive with other reported UUAS scores. We suggest that even though our method does not achieve sfate-of-the-arr scores, they are compara- ble and the performance increases are reliable. the following experiment, we provide more fine-

---

ccomp
mark
phi
[ssubj
obj
det
nsubj
jobj
det
Bux
det
case
A witness told police that the victim had attacked the suspect in April
SSUD.
8/12 75%
A witness told police that the victim had attacked the suspect in April
target
8/12 66%
Figure 4: Dependency parse which compares the result of SSUD and using the target sentence alone. In the SSUD parse, the noun, 'victim' is accurately attached to its verb 'attacked' (in green). Without SSUD, 'victim' is attached to the determiner of 'suspect,' perhaps due to lexical similarity (in red). Dark blue edges match the gold-standard parse. Light blue edges demonstrate how induced edges differ, but still be syntactically informative.
EN-PUD (UUAS)
words are treated as heads of relations in SUD. For example, in SUD, a verb with a clausal comple- ment would be attached to a complementizer as we noted in our qualitative analysis above.
k:
10
A
UD (Nivre al., 2020)
44.3
46.4
2.1
SUD (Gerdes et al., 2018)
56.0
59.0
3.0
Table 4 shows that SSUD parses receive higher scores on SUD (59.0 vs. 46.4 UUAS) and that using our method on SUD provides a larger im- provement (+3.0pts vs. +2.1pts). We also find dif- ferences when looking at recall scores for specific relations which differ between the formalisms (see Appendix B for full relation-wist results). For ex- ample, two relations which are annotated with con- tent words heads in UD, obl and coomp, both receive low recall: 2.3% and 1 11.1% 1,1, respectively. In contrast, the SUD relations which subsume these two relations, comp: : obj and comp: : obl, achieve much higher recall: 57.56% and 79.3%.
Table 4: UUAS scores for Universal Dependencies an- notations (UD) and surface-Syntacte Universal Depen- dencies annotations (SUD) on sentences from EN-PUD (bert baart-bae--ae unsaseed) Comparison between ing the target sentence alone (7.) and SSUD, = 10.
grained comparisons to previous methods by look- ing at more challenging syntactic constructions. In Figure 4, provide example of parse induced via SSUD and one which only uses the target sentence. We have labeled some edges which differ from the UD annotation, but which are still syntactically informative, c.g. predicting an edge from the matrix verb 'told' to the com- plementizer 'that,' rather than to the main verb of the embedded clause (see Appendix C for more example parses). Cases such these demonstrate that specific choices from annotation schemata can artificially lower the resulting UUAS scores. We now test this observation quantitatively.
This result supports our qualitative analysis in the previous section, however, Kulmizev et al. (2020) come to the opposite conclusion when sessing the preferences of BERT for the same two annotation schemata. Since they use trained probe to induce parses, perhaps different kinds of linguis- tic information are being recovered via our two distinct methods. We leave further analysis of this to future work.
5.4 Results and Discussion:
Which syntactic formalism do SSUD parses align with?
Does SSUD help with harder syntactic constructions?
In order to compare differences resulting from notation choices, we rescore the EN-PUD trees induced via SSUD on different syntactic formal- ism. Specifically, we choose the Surface-Syntactic UD formalism (SUD) (Gerdes et al., 2018), which differs from UD mainly in one respect: function
6.1 Experiment 2: Dataset and Setup
In the previous experiments, we provided results for our method applied to standard parsing datasets. In this experiment, we use data from Maryin and

---

Linzen (2018) to control for the syntactic struc- tures being evaluated. Specifically, we look at more challenging long-distance subject-verb agree- ment constructions which have been used to inves- tigate hierarchicall--deeendeet behaviour in lan- guage models. The reasoning here is that models using linear heuristics such as the distance between a noun and verb would mistakenly assign closer nouns nominal subjects. We reframe this task and investigate whether the tree-induction methods are able to accurately predict an edge between the subject and verb. We report a correctly predicted edge as either between the subject's determiner or head noun and the verb.
Object Relative Clause (recall)
Method
T.
k
k
k=
3
==
5
k = 10
Ours
71.1
71.2
72.4
75.3
79.5
Z++
8.9
Subject Relative Clause (recall)
Ours 54.7
57.9
60.1
61.2
63.0
Z. + H
1.9
Table 5: Results on subject-verb edge prediction. We compare using the target sentence alone (T.) with us- ing SSUD & 1,3, 5, 10. For comparison, scores for conditional MI trees averaged over 3 seeds using only the target sentence are reported (Z+H), as proposed in Zhang and Hashimoto (2021).
We sample 1000 sentences from 2 templates used in Marvin and Linzen (2018): agrecment across object relative clause (e.g. "The pilot [that the minister likes] cooks.) and agreement across a subject relative clause (e.g. 'The customer [that hates the skater] swims."). We include only non-copular verbs to control for any possible dif- ferences in syntactic representation.
dependency trees from attention distributions. We can directly test the effect of SSUD simply by using SSUD-processee processed attention matrices whenever at- SSUD tention matrices are used in the original algorithm. This method involves a key additional step of selecting syntactically informative attention heads based on UD relations before inducing syntactic trees. This process requires supervision from gold- standard parses but, as such, provides an 'upper bound' of how much UD-like syntactic structure can be retrieved from BERT. Heads are selected for both the dependent-to-paute torpeentt and parent-to- dependent directions for each relation. As with previous experiments, we compare SSUD to using the target sentence only, and evaluate both steps of the algorithm: (i) are the chosen heads more accu- rate for the UD relations considered, and (ii) does SSUD improve the induced syntactic trees? We constrain our method and use the same resources and models the original algorithm² and do not use POS information. We test the best-performing method in their paper which uses 1000 selection sentences. Following the original paper, directed labeled and unlabeled trees are induced and un- labeled attachment scores and labeled attachment scores on the EN-PUD dataset are used for evalua- tion.
We evaluate SSUD on this task and provide re- sults from applying Zhang and Hashimoto (2021)'s conditional MI method, which performs better than ours in the previous task, for comparison.
6.2 Experiment Results and Discussion
The results are shown in Table 5, with an improve- ment in edge recall for SSUD as k is increased. This further corroborates our observations from the previous experiments on standard datasets, and the increase of 8.4 points for the object relative clauses, and 8.3 points for subject relative clauses are promising. Comparing our results to those from applying Zhang and Hashimoto (2021)'s method are promising as well. SSUD outperforms theirs on both object (+70.6pts) and subject relative clauses (pts. A future extension this experiment which could improve the interpretability of model mechanisms to compare the results of syntactic structure induction with an evaluation of model be- haviour (i.e. does a correctly predicted edge lead to correct agreement).
7.2 Experiment 3: Results and Discussion
The results of the experiment are summarized Table 6. For head selection, SSUD outperforms using the target sentence alone in all but 3 relations: aux (-0.2pts) and amod (-O.1pts) in the dependent- to-parent direction, and nummod (-0.8pts) in the parent-to-dependees direction. There is relation that using SSUD does not improve for at least one
7 Does SSUD generalize?
7.1 Experiment 3: Setup
In this experiment, test whether SSUD robustly improves syntactic dependency parsing by apply- ing it to a different parsing algorithm proposed by Limisiewicz et al. (2020) for extracting directed

---

Dependent-to- Parent Head Sclection Accuracy ASSUD, T.)
dency structures, Indeed attention distributions do capture a surprising amount of syntactic informa- tion, despite never being trained to do so. With substitutability as a constraint, we can better make use of this information for unsupervised parsing and better understand the extent to which this prop- erty is learned by attention mechanisms. Our re- sults also suggest that previous probing results on attention mechanisms using single sentences may underestimate the amount of syntactic information present.
Label
T.
k=
==
nsubj
63.8
65.8
67.0
68.2
4.4
obj
91.1
92.7
93.9
93.9
2.8
det
97.3
97.4
96.8
95.7
0.1
case
88.0
88.0
88.2
87.9
0.2
Tree Induction Scores
Metric
T.
k
A(SSUD,
UAS
52.8
53.7
54.5
54
1.7
LAS
22.5
25.6
26.3
22
3.8
Table 6: Results on selected non-clausal relations used for head selection in the dependent to parent direction, full results in Appendix D. Unlabeled (UAS) and labeled (LAS) scores are reported as well. Using only the target sentence (T.) equivalent the original algorithm; results for SSUD (k 1,3, 5) are provided.
We show that SSUD effectively transfers to new parsing setups and to different datasets. A potential next step is to use this method cross- tross-linuusttiaall in order to better understand the representation of different languages within multilingual models. In addition to uses for NLP and computational linguis- tics, these interpretable, model-intrinsic structures may provide new source of data for work in theo- retical linguistics and syntactic annotation, and as further confirmation of the emergence of syntax- like structures in neural network language models.
of the directions. For tree induction, we see that SSUD k = 3 provides the highest improvements with increases in both the unlabeled (+ (+1.7pts) and labeled (+3.8pts) attachment scores. Unlike in the previous experiments, increasing the number of substitutions dues not monotonically increase pars- ing accuracy. We analyze this effect below.
As stated in the setup, we wished to maintain the resources and models used in the original paper and such do not POS information here. This in turn leads to a split between lexical and functional categories. Increasing the number of substitutions for closed categories like determiners can lead to a decrease in performance the number of possi- ble substitutions is exceeded. Quantitative results reveal this is the case: for example, as more substi- tutions are used, correctly labeling the det relation falls from 38.6 (k= 3) to 7.9 (k 5). The head selection accuracy patterns in Table 6 reflect this as well. Interestingly, at k the model incorrectly labels det as case 48.2% of the time. However, when considering a relation with open class words like jbj, SSUD k = 5 labels obj correctly with 36.6 recall, outperforming T. by 11.6pts. We refer the reader to Appendix D for full results. While we only explore a static number of substitutions here, future work may find that dynamic number of substitutions leads to further improvements.
Ethics Statement
While there are few ethical problems linked to the methodology explored in this paper, there remain those more generally associated with large lan- guage models, including concerns of privacy and learned biases. A better understanding of linguistic mechanisms in models may lead to improvements in this domain as well.
Limitations
In this paper, we focus only on English data. This is a limitation of the work because English is a language with relatively strict word order and does not morphologically mark most grammatical re- lations. This may present challenge when this method is used in other languages substituting given word in a sentence may affect morphological marking on other words in the sentence, but we hope large-scale training of BERT-like models may circumvent some of these problems. Theoretically, we can capture this by assuming more fine-grained categories which do not differ in this morphology (see Dehouck and CómmezRRodrígues (2020) for a discussion).
Overall, the results for Experiment 3 show that SSUD leads to gains over the original algorithm and effectively distills more syntactic information even when used in a different setup.
8 Conclusion
Another limitation of this study is that we only study BERT models trained on English. This has a twofold effect: (1) there is nothing stopping the attention mechanisms of a different model from
The results across the three experiments show that there is merit to modeling the property of syntac- tie substitutabllity when inducing syntactic depen-

---

storing syntactic information differently, and (2) as previously mentioned, English has a relatively rigid word order which may already carry much infor- mation about the syntactic relations between words. Compared to a language with more word orders like Japanese or German, it is not unimaginable that attention mechanisms learn to track syntactic relations differently. Addressing the small number of models studied here, we suggest that the main contribution of this method, that syntactic substi- tutability can help extract syntax from models, is one which is defined agnostically of the specific model. As such, the results of applying this method to different architectures may in fact be informative for the interpretation of their internal mechanisms well.
dency parsing of now-resource languages, In Proceed- ings of the 28th International Conference on Com- putational Linguistics, pages 3818-3830, Barcelona, Spain (Online). International Committee on Compu- tational Linguistics.
Jacob Devlin, Ming-Wor Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of deep bidirectional transformers for language under- standing. Pruceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Tech- nologies, Volume (Long and Short Papers), pages 4171-4186, Minneapolis, Minnesota. Association for Computational Linguistics.
Richard Futrell, Peng Qian, Edward Gibson, Evelina Fedorenko, and Idan Blank. 2019. Syntactic depen- dencies correspond to word pairs with high mutual in- formation. In Proceedings of the Fifth International Conference on Dependency Linguisties (Depling. SyntaxFest 2019), pages 3-13, Paris, France, Associ- ation for Computational Linguistics.
The domains explored in this paper are limited: the WSJ10 dataset features sentences from news articles in the Wall Street Journal (Mareus al., 1993), and the EN-PUD dataset are sentences from news and Wikipedia articles (Nivre et 2020).
Kim Gerdes, Bruno Guillaume, Sylvain Kahane, and Guy Perrier. 2018. SUD or surface-syntactic Uni- versal Dependencies: An annotation scheme near- isomorphic to UD. In Proceedings of the Second Workshop on Universal Dependencies (UDW 2018). pages 66-74, Brussels, Belgium. Association for Computational Linguistics.
Acknowledgements
We thank members of SR's research group and the Montréal Computational & Quantitative Linguis- ties Lab for their helpful comments. JJ acknowl- edges the support of a Natural Sciences and En- gineering Research Council of Canada (NSERC) USRA [funding reference number 539633J. SR ac- knowledges the support of the NSERC Discovery Grant program.
Yoav Goldberg. 2019. Assessing BERT's syntactic abil- ities. CoRR, abs/1901 0111199111287...
Kristina Gulordava, Piotr Bojanowski, Edouard Grave, Tal Linzen, and Marco Baroni. 2018. Colorless green recurrent networks dream hierarchieally. In Proceed- ings of the 2018 Conference of the North American Chapter of the Association for Computational Lin- guisties: Human Language Technologies, Volume (Long Pupers), pages 199--1205 New Orleans, Louisiana. Association for Computational Linguis- tics.
References
Yonatan Belinkov. 2022. Probing classifiers: Promises, shortcomings, and advances. Computational Linguis- tics, 2112222-21..
John Hewitt and Christopher D. Manning, 2019, A structural probe for finding syntax in word represen- tations. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Tech- nologies, Volume (Long and Short Papers), pages 4129 4138, Minneapolis, Minnesota. Association for Computational Linguistics.
Kevin Clark, Urvashi Khandelwal, Omer Levy, and Christopher D. Manning. 2019. What does BERT look at? an analysis of BERT's attention. In Pro- ceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 276-286, Florence, Italy, Association for Com- putational Linguistics.
Jacob Louis Hoover, Wenyu Du Alessandro Sordoni, and Timothy J. O'Donnell. 2021. Linguistic depen- dencies and statistical dependence. In Proceedings of the 2021 Conference on Empiriaal Methods in Nat- ural Language Processing, pages 2941-2963, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
Carre-CCttheine de Marneffe, Bill MacCartney, and Christopher D. Manning. 2006. Generating typed dependency parses from phrase structure parses. In Proceedings of the Fifth International Conference on Language Resources and Evaluation (LREC'O6) 06)), Genoa, Italy. European Language Resources Associ- ation (ELRA).
Phu Mon Htut, Jason Phang, Shikha Bordia, and Samuel R. Bowman. 2019. Do attention heads in BERT track syntactic dependencies? CoRR, abs/1911..2244
Mathieu Dehouck and Carlos K6mezz-oodrguu 2020. Data augmentation via subtree swapping for depen-

---

Tim Humter. 2021. The chomsky hierarchy. In Nicholas Allot, Terje Lohndal, and Georges Rey, editors, A Companion to Chomsky, chapter 5, pages 74-95. John Wiley & Sons, Ltd.
Isabel Papadimitriou. Richard Futrell, and Kyle Ma- howald. 2022. When classifying grammatical role, BERT doesn't I care about word order... except when it matters. In Proceedings of the 60th Annual Meet- ing of the Association for Computational Linguistics (Volume 2: Short Pupers), pages 356-643, Dublin, Ireland. Association for Computational Linguisties.
Taeuk Kim, Jihun Choi, Daniel Edmiston, and Sang-goo Lee. 2020. Are pre-trained language models aware of phrases? simple but strong baselines for grammar induction. In International Conference on Learning Representations.
R. C. Prim. 1957. Shortest connection networks and some generalizations. The Bell System Technical Journal, 36(6):339-1144)
Yoon Kim, Chris Dyer, and Alexander Rush. 2019. Compound probabilistic context-free grammars for grammar induction. In Proceedings of the 57th An- nual Meeting of the Association for Computational Linguistics, pages 2369, Florence, Italy. Asso- ciation for Computational Linguistics.
Peng Qi. Yuhao Zhang, Yuhui Zhang, Jason Bolton, and Christopher D. Manning. 2020. Stanza: A Python natural language processing toolkit for many human languages. In Proceedings of the 58th Annual Meet- ing of the Association for Computational Linguistics: System Demonstrations.
Dan Klein and Christopher Manning. 2004. Corpus- based induction of syntactic structure: Models of dependency and constituency. In Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics (ACI-044, pages 478-485, Barcelona, Spain.
A Alessandro Raganato and Jörg Tiedemann. 2018. An analysis of encoder representations in transformer- based machine translation. In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 287-297, Brussels, Belgium. Association for Com- putational Linguistics.
Artur Kulmizev, Vinit Ravishankar, Mostafa Abdou, and Joakim Nivre. 2020. Do neural language mod- els show preferences for syntactic formalisms? In Proceedings of the 58th Annual Meeting of the Asso- ciation for Computational Linguistics, pages 4077- 4091, Online. Association for Computational Lin- guistics.
Ian Tenney, Dipanjan Das, and Ellie Pavlick. 2019. BERT rediscovers the classical NLP pipeline. In Proceedings of the 57th Annual Meeting of the Asso- ciation for Computational Linguistics, pages 4593- 4601, Florence, Italy Association for Computational Linguistics.
Tomasz Limisiewiez. David Mareček, and Rudolf Rosa. 2020. Universal Dependencies According to BERT: Both More Specific and More General. In Findings of the Association for Computational Linguistics:
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, & ukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Advances in Neural Information Pro- cessing Systems, volume 30, Curran Associates, Inc.
EMNLP 2020, pages 2710-2722, Online. Association for Computational Linguistics.
Mitchell P. Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. 1993. Building large annotated cor- pus of English: The Penn Treebank. Computational Linguistics, 19(3)313--30.
Zhiyong Wu, Yun Chen, Ben Kao, and Qun Liu. 2020. Perturbed masking: Parameter-free probing for ana- lyzing and interpreting BERT. In Proceedings of the 58th Annual Meeting of the Association for Compu- tational Linguistics, pages 4166-4176, Online. Asso- ciation for Computational Linguistics.
Rebecca Marvin and Tal Linzen. 2018. Targeted syn- tactic evaluation of language models. In Proceed- ings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 1192-1202, Brussels, Belgium. Association for Computational Linguistics.
Tianyi Zhang and Tatsunori B. Hashimoto. 2021. On the inductive bias of masked language modeling: From statistical to syntactic dependencies. In Proceedings of the 2021 Conference of the North American Chap- ter of the Association for Computational Linguistics: Human Language Technologies, pages 5131-5146, Online, Association for Computational Linguistics.
Igor Mel'čuk. 2009. Dependency in natural language. In Alain Polguère and Igor Mel'čuk, čuk, editors, Depen- dency in linguistic description, volume 111 of Studies in language companion series. John Benjamins Pub. Co, Amsterdam; Philadelphia.
Joakim Nivre, Catie-Catherine de Marneffe, Filip Gin- ter, Jan Hajič, Christopher D. Manning, Sampo Pyysalo, Sebastian Schuster. Francis Tyers, and Daniel Zeman. 2020. Universal Dependencies v2: An evergrowing multilingual treebank collection. In Proceedings of the Twelfth Language Resources and Evaluation Conference, pages 4043, Marseille, France. European Language Resources Association.

---

A Experiment 1.1: Validation set results
dataset with SSUD: +2.0/+1.7 for nsubj. +4.0/+1.5 for dobj/obj, among other parallels. Again, note that annotation schemata may be defined differ- ently from the edges induced, even if they are syn- tactically informative. For example, the ccomp (clausal complement) relation, which links verb or adjective with dependent clause, has rela- tively low 11.1% recall in the EN-PUD dataset. Looking at example like Figure in Appendix Section C begins show why this may be: the verb 'told' is linked with the complementizer 'that,' rather than the main verb of the embedded clause "attackdd," as is done in the UD schema.
We report Experiment 1.1 results for the validation set. Layer 10, which shows the largest increase, was chosen for Experiments 2 and
UUAS
WSJ Section 21 (validation)
Layer
T.
k
52.5
52.7
7
51.4
51.7
8
50.7
50.8
9
52.1
52.0
10
49.3
49.9
0.6
Table 7: UUAS scores validation set. SSUD l = compared with only using target sentence (7.).
B.1 Surface-Syntactie UD
B Experiment 1.2: What does SSUD improve?
In Table 12, provide full results the English Parallel Surface-Syntactic UD annotated dataset, As discussed, this formalism treats functional words like complementizers and prepositions as the heads of dependencies. This is the pattern that we have qualitatively noted in SSUD derived parses. The results show that SSUD favours SUD, achiev- ing 57.6% recall on the SUD comp: : obj and 79.3% on the comp: obl relation which encom- pass the UD ccomp relation mentioned above. The comparison
In this section, we provide additional results from Experiment 1.2.
One noted qualitative improvement due to SSUD is decrease in non-syntactic edges being predicted between words which are semantically similar, but not syntactically dependent. This provides a poten- tial explanation for the quantitative results in Table 8 which shows increases in the recall of adjacent edges and precision of non-adjacent edges. This suggests that fewer incorrect non -djjcencn edges are being predicted (i.e. ones predicted due to lexi- cal similarity) and more correct adjacent edges (i.e. closer dependencies that are necessarily seman- tically dependent or similar). See Figure for an example and Appendix for further discussion of this and more examples.
robust those relations also include other UD complement relations, though the SUD scores are reliably higher.
C Experiment 1.2: Example parses
In Figures 5, 6, and 7, we provide some example parses comparing our method, and those induced using conditional MI with Zhang and Hashimoto (2021)'s method, seed 1. The errors and improvements note relate to the results dis- cussed in Appendix B, including a decrease of non-syntactic edges predicted due to semantic sim- ilarity, and specific differences between induced trees and aunotation-dependen choices.
WSJIO
km/
km3
km5
km/0
Amn-r
Adjacent
Rec.
77.7
77.4
3.6
Prec.
68.3
68.3
67.8
0.1
Non-Adj.
Rec. 34,5
33.7
33.3
34.2
-0.3
Pree. 38.5
39.3
39.7
39.7
41.1
2.6
EN-PUD
k=1
k=3
k=5
k=10
A1p-7:
D Experiment 3: Additional results
Adjacent
Rec. 71.7
73
74.7
75.7
76.1
4.4
Prec. 55.5
55.6
55.9
56
56
0.5
Non-Adj.
Rec. 24.5
24.2
24.6
24.8
24.9
0.4
We provide full per relation results for Experiment in this section. Results for head selection accu- racy for both the dependent- cociidentttt--paare parent and parent-to- dependent direction are provided in Tables 13 and 14, respectively. As reviewed in $7.2, SSUD out- performs the original algorithm with just the target sentence on all relations except on aux (-0.2pts) and amod (-0. I pts) the dependent-to-ppreet di- rection, and nummod (-0.8pts) in the parent-to- dependent direction.
33.3
33.7
Table 8: Adjacent and non-adjacent edge recall and precision results on WSJ10 and EN-PUD. Results are reported across increasing number of substitutions, & = 1,3, 5, 10 for Layer 10.
In Tables 10 and 1 1, we report the relation-wist results for both datasets. We see similar improve- ments in both the WSJ-10 dataset and the EN-PUD

---

Per relation results on unlabeled and labeled trees are also provided in Tables 15 and 16. The recall scores for UAS are calculated as the number edges predicted correctly for each relation, while for LAS both the edge and correct label must be predicted. As reviewed in $7.2 and Table 6, SSUD k = 3 provides the best results, and much of the de- crease between & 3 and 5 can be attributed relations with closed class lexical items like det, while open class relations like obj and subj re- main relatively stable or show improvements as substitutions are increased.
G Datasets and licenses
The Stanza (Qi et al., 2020) package was used as intended, under the Apache License, Version 2.0. The datasets were used as intended, as estab- lished by previous work such as Klein and Manning (2004) and Hoover et al. (2021). EN-PUD is part of the publicty available Parallel Universal Depen- dencies treebanks. Surface-Syntactic UD treebanks are also available publicly. The WSJ datasets were acquired through Not-Foo-Prooie Standard Lin- guistic Data Consortium licence. The data are from published news, and Wikipedia sources.
E Experiment 1: bert-large-uncased
UUAS
WSJI0
EN-PUD
Layer
T.
k
A
T.
=
1
16
54.6
54.8
0.2
43.6
43.8
0.2
56.1
56.5
0.4
45.5
45.8
0.3
53.5
54.3
0.8
41.5
41.9
Table 9: UUAS
WSJ10 and EN-PUD
(bert-large-nnear with only using target sentence (T.).
SSUD compared
In Table 9, we provide full results for Experi- ment for the bert-large-uncasee The best-performing layer corresponds with pre- vious results from the literature about the locus of retrievable syntactic information in pretrained BERT models (e.g. Kim al., 2020).
model.
F Compute and package versions
The SSUD experiments can be reproduced with a GPU with 2GB of memory, and CPU with 24GB of memory. Experiments each run in 7hrs, on an RTX8000. Experiments comparing our method with Zhang and Hashimoto (2021) used GPU with 24GB of memory, and CPU with 100GB of memory. These experiments ran in 10hrs RTX8000 GPU. Packages: Stanza (1.4.0); networkx (1.22.4); numpy (1.22.4); transformers (4.1)) torch (1.11.0).
Experiments involving the algorithm proposed in Limisiewicz et al. (2020) used GPU with 24GB of memory, and CPU with 128GB. These experi- ments ran in 10hrs, on an RTX8000. We direct the reader to the original repository for packages used therein.

---

Recall (EN-PUD)
UD Relation
T.
k == 10
Recall (WSJ10)
acl
35.2
34.7
SD Relation
T.
k
10
acl.relcl
21.3
24.2
acomp
64.3
78.6
advcl
6.5
5.5
advel
0.0
0.0
advmmod
49.6
53,4
advmod
58.2
60.3
amod
68.7
72.9
amod
72.7
74.8
appos
27.3
23.1
appos
65.0
65.0
aux
32.9
33,4
aux
45.0
43.3
aux:pass
71.2
74,8
auxpass
70.8
79.2
case
55.1
59.9
cc
37.0
38.9
cc
32.6
33.8
ccomp
5.9
5.9
cc:preconj
0.0
9.1
conj
51.5
51.5
ccomp
8.1
11.1
cop
34.8
44.9
compound
79.1
84.6
csubj
50.0
50.0
compound:prt
95.7
98.6
dep
45.5
48.5
conj
31.1
28.2
det
76.7
75.7
cop
30.4
33.2
csubj
11.1
11.1
discourse
60.0
40.0
csubj:pass
0.0
0.0
dobj
58.2
62.2
dep
0.0
0.0
expl
100.0
85.7
det
68.5
72.9
iobj
50.0
50.0
det:predet
33.3
33.3
mark
25.0
25.0
discourse
0.0
0.0
neg
23.4
27.7
dislocated
0.0
0.0
nn
65.4
67.5
expl
69.4
66.1
npadvmod
25.0
50.0
fixed
85.4
85.4
nsubj
45.2
47.2
flat
78.3
79.1
nsubjpass
25.0
20.8
goeswith
100.0
100.0
num
67.3
67.3
iobj
40.0
40.0
number
85.2
85.2
mark
52.1
51.7
parataxis
0.0
0.0
nmod
12.3
10.2
pcomp
100.0
100.0
nmod:npmod
63.2
68.4
pobj
63.7
63.7
nood:poss
40.0
41.4
poss
45.7
48.6
nmod:tmod
38.5
43.6
possessive
68.8
87.5
nsubj
28.3
30.0
preconj
0.0
0.0
nsubj:pass
26.4
25.9
predet
100.0
0.0
nummod
73.2
74.0
prep
58.2
60.5
obj
41.8
43.3
prt
100.0
100.0
obl
3.1
2.3
quantmod
57.1
57.1
obl:npmod
50.0
45.0
remod
0.0
0.0
obl:tmod
22.2
11.1
tmod
33.3
55,6
orphan
14.3
14.3
vmod
70.0
60.0
parataxis
6.2
7.2
xcomp
14.7
23.5
reparandum
0.0
0.0
vocative
0.0
100.0
Experiment 1.2: Per relation results on IS annotated with Stanford Dependencies, compar- ing target only (T), and SSUD, & 10. Note: recall of a relation may be lower if the induced trees differ from annotation schemata, despite syntactic relevance.
Table 10:
xcomp
19.9
21.4
Table 11:
Experiment 1.2: Per relation results on EN- PUD, annotated with Universal Dependencies, compar- ing target only (T.), and SSUD, relation may be lower if the induced trees differ from annotation schemata, despite syntactic relevance.
10. Note: recall of

---

Recall (EN-PUD)
SUD Relation
T.
k=10
appos
28.7
24.5
cc
39.4
40.6
cc preconj
0.0
9.1
comp:aux
50.5
51.0
comp:aux @pass
71.5
75.2
comp:obj
54.0
57.6
comp:obl
76.5
79.3
comp:pred
38.7
42.2
comp @ expl
66.7
61.5
compound
79.1
84.6
compound @ prt
95.7
98.6
conj
36.2
35.3
conj @ emb
50.0
60.0
det det @et@ppret predet
68.5
72.9
33.3
33.3
discourse
100.0
100.0
dislocated
0.0
0.0
flat
86.5
87.4
goeswith mod mod @npmod
100.0
100.0
61.1
64.4
61.1
66.7
mod @ poss
49.1
52.1
mod @reccl
13.7
15.2
mod@@tmm tmod
43.6
46.2
orphan
0.0
0.0
parataxis
12.4
12.4
reparandum
0.0
0.0
subj
34.1
36.1
subj@pass.
23.6
26.0
udep
64.6
67.9
npmod
52.4
47.6
@ poss
45.1
43.1
udep@ tmod
33.3
22.2
unk @ek@expl vocative
85.7
86.7
73.9
73.9
0.0
100.0
Table 12: Experiment 1.2: Per relation results EN- PUD, annotated with Surface- Surface-Syntactic Universal De- pendencies, comparing target only (T.), and SSUD, k 10. Note: recall of relation may be lower the induced trees differ from annotation schemata, de- spite syntactic relevance.

---

ccomp
mark
obl
nsubj
obj
det
nsubj
jobi
det
aux
det
case
witness told police that the victim had attacked the suspect in April
SSUD, A: 10
9/12 76%
A witness told police that the victim had attacked the suspect in April
target only
8/12 68%
A witness told police that the victim had attacked the suspect in April
Z-H
8/12
Figure 5: This example was presented Figure above. The conditional MI parse predicts edge between 'suspect' and 'witness," perhaps for their salience to the domain of the sentence 'witness' is longer attached to its verb 'told'' This perhaps similar to the edge between 'victim" and 'the [suspect]' in the target-only parse, where 'victim' no longer attached the verb 'attacked',

---

m66b)
nmod
case
ccomp
ammod
nsubi
amod
compound
Many people
including Indigenous groups argue they trivialize First Nations culture
SSUD. 10
8/10 80%
Many people
including Indigenous groups argue they trivialize First Nations culture
Many people
including Indigenous groups argue they trivialize First Nations culture
Z+H
2/10 70%
Figure 6: edge hetween 'Indigenous' and First' the target-only parse shows edge-prediction errors where words are linked with other semantically similar words, rather than syntactically dependent ones. An edge is also predicted between 'people' and 'trivialize" in the conditional MI parse represents an incorrect argument structure, which should be more like the SSUD parse where the noun phrase 'many people' connected 'argue'. We see the SSUD parse example where the choice of headedness in the noun phrase artificially lowers the UUAS score. Qualitatively, the nominal subject of the verb 'argue' correctly attached. The clausal argument structure is also improved: 'argue' in the SSUD parse correctly attaches its clausal complement the verb 'trivialize."

---

junilasis
advenod
0bg
compooun
Physicians do n't have these tools they have only prescription pad and an injection
Mailis said
SSUD & 10
9/16 56%
Physicians n't have these tools they have only a prescription pad and an injection Mailis
Jange
Physicians do n't have these tools. they have only a prescription pad and an injection Mailis said
Z-H 7/16 = 40
Figure 7: In the target-only parse, again the effect of semantic similarity the induced parse. 'Physicians' is connected to both 'tools' and 'injections', rather than either the auxiliary verb 'do" or the main verb 'have." This resolved both SSUD and conditional parses. weakness clarity in conjunctions, where the induced structure of prescription pad and injection' does not appear to be adequately clarified. The subtree containing this in the SSUD parse, rooted by the quantifier "only,' is however correctly attached the verb 'have,' unlike the target-only parse.
SSUD parse here is the lack

---

Recall (EN-PUD)
UD Relation
T.
3
5
acl
2.1
1.0
1.5
3.6
acI.relcl
1.0
1.0
1.4
2.4
d2p Head Selection
advel
1.0
0.7
1.4
2.4
UD Relation
T.
k =
3
k
5
advmod
57.9
59.6
59.0
59.6
acl
53.2
55.7
55.4
55.4
amod
91.1
92.2
92.6
91.9
advel
40.6
41.6
44.7
43.7
appos
6.3
4.2
6.3
5.6
67.0
68.0
67.5
68.2
aux
82.7
83.9
84.2
82.2
esubj
56.7
53.3
56.7
56.7
aux:pass
100.0
99.6
99.3
99.6
parataxis
28.9
29.9
26.8
29.9
case
81.0
82.4
83.4
81.8
amod
94.3
94.1
94.2
94.1
cc
60.5
61.7
64.8
62.4
advmod
65.5
66.0
66.7
67.5
cc:preconj
27.3
27.3
54.5
45.5
93.6
93.4
92.5
92.5
ccomp
0.0
0.0
0.0
0.0
compound
86.9
87.4
88.8
87.6
compound
89.0
89.8
90.0
89.6
conj
62.3
64.7
66.2
67.2
compound:prt
7.1
8.6
15.7
14.3
det
97.3
97.4
96.8
95.7
conj
1.6
2.2
2.5
1.7
nmod
49.2
48.2
49.3
49.5
cop
73.4
76.0
77.2
73.4
nummod
85.8
86.2
87.4
86.6
csubj
3.7
0.0
0.0
3.7
obj
91.1
92.7
93.9
93.9
csubj:pass
0.0
0.0
0.0
0.0
subj 63.8
65.8
67.0
68.2
det
94.4
95.6
94.8
94.8
case
88.0
88.0
88.1
87.9
det:predet
77.8
88.9
88.9
77.8
mark 75.1
75.3
75.5
75.7
discourse
0.0
0.0
0.0
0.0
dislocated
0.0
0.0
0.0
0.0
Table 13: Experiment Dependent-to-Pain head se- lection accuracy results
expl
58.1
58.1
54.8
62.9
flat
8.3
6.1
7.8
7.4
p2d Head Selection
goeswith
0.0
0.0
0.0
0.0
UD Relation
T.
k=1
k=3
k=5
iobj
50.0
60.0
50.0
70.0
acl
52.5
54.0
54.7
53.5
mark
65.6
67.0
66.7
65.6
advel
26.6
33.1
38.9
39.9
nmod
7.3
7.8
8.7
8.5
cc
58.4
59.9
59.6
58.1
nmod:npmod
15.8
15.8
15.8
15.8
csubj
46.7
50.0
40.0
36.7
nmod:poss
68.2
71.5
70.4
69.9
parataxis
28.9
26.8
32.0
28.9
nmod:tmod
12.8
12.8
7.7
10.3
amod
79.7
80.6
80.7
80.9
nsubj
54.3
55.8
58.8
58.5
advmod
64.9
66.0
64.7
65.1
nsubj:pass
40.2
45.6
46.9
41.0
aux
82.5
82.6
82.7
82.5
nummod
72.1
72.8
73.2
74.0
compound
82.4
83.0
85.3
84.7
obl
2.6
2.4
3.4
3.6
conj
47.6
48.4
50.9
51.4
obl:npmodd
65.0
70.0
65.0
70.0
det
70.7
72.4
72.7
72.5
obl:tmod
11.1
11.1
11.1
11.1
nmod
55.7
56.1
56.5
56.7
orphan
0.0
0.0
14.3
14.3
nummod
74.0
66.1
72.4
73.2
parataxis
0.0
1.0
0.0
0.0
obj
81.0
82.7
84.4
84.8
subj
73.7
74.4
75.9
75.9
punct
17.7
17.7
17.9
16.5
case
68.8
69.7
71.0
71.3
reparandum
0.0
0.0
0.0
0.0
mark
66.3
67.0
60.9
62.2
root
100.0
100.0
100.0
100.0
vocative
0.0
0.0
0.0
0.0
Table 14: Experiment Parent-to-Dependde head se- lection accuracy results
xcomp
9.6
10.3
10.0
12.9
UUAS
52.8
53.7
54.5
54.0
Table 15: Experiment 3: Per relation results for induced unlabeled trees, comparing target only (T.) with increas- ing SSUD.

---

Recall (EN-PUD)
UD Relation
T.
==
amod
41.6
47.2
69.2
53.0
aux
71.0
64.6
55.1
72.7
case
31.0
41.9
68.1
56.0
2.6
2.3
1.2
0.5
compound
50.7
31.0
15.1
41.2
conj
1.3
2.1
2.4
1.6
det
55.1
73.9
38.6
7.9
mark
0.5
0.4
4.5
0.5
nmod
3.5
3.3
2.3
1.6
nsubj
19.5
22.8
24.3
23.0
nummod
0.0
3.5
2.4
5.5
obj
25.0
27.2
35.6
36.6
root
100.0
100.0
100.0
100.0
advmod
5.5
10.2
8.2
9.4
LAS
22.48
25.6
26.3
22.0
Table 16: Experiment 3: Per relation results for induced labeled trees. comparing target only (T.) with increasing SSUD. Note: only labels that are considered during head selection can labeled in the final tree.


Reviews:
[{"review_id": "gzA3DaCl4O", "reviewer": "Reviewer_cSPA", "summary": "", "questions": "A - Equation (5): Since the dependencies are undirected, why are the substitutions done only on i, and not j as well?\n\nB - Line 369: is there a motivation in particular to use a dataset with so short sentences? Is it more informative, easier to interpret, more representative of the targeted phenomena...? Since Experiment 2 focuses on long-distance agreement, the use of WSJ10 here is surprising.\n\nC - Experiment 1.1 selects layer 10, but which head (cf. multi-head attention)? How is the head selected? Or are the attentions also aggregated over heads of the same layer?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nWe would like to first thank you for your detailed review of our paper and are grateful for your suggestions to improve the presentation which we will fix for the camera-ready version. Thank you as well for highlighting strengths such as:\n* ‘Solid theoretical foundations,’ also noted by reviewer 5gcw\n* A ‘carefully laid out’ problem statement and ‘[great] framing and formalism’\n* The ‘well-written and well-structured’ paper\n\nWe would like to mention some strengths observed by other reviewers, including:\n* Its ‘general-purpose’ nature  ‘e.g. data augmentation even in supervised settings,’  and ‘clear avenue for future work’ reviewer z2Sw\n* ‘Simple and straightforward idea,’ reviewers 5gcw and z2SW\n\nWe appreciate your questions that will serve to clarify our paper’s methodology further. We address them below:\n\n>A: Equation (5): Since the dependencies are undirected, why are the substitutions done only on i, and not j as well?\n\nEq. (5) makes reference to the attention distribution of a sentence, where only 1 word is substituted at a time in order to better control for possible changes in syntactic structure. As you have correctly stated, dependencies are undirected, so the choice of i or j in this equation is arbitrary. In fact, since the final matrix aggregates substitutions at each position when parsing, the MST algorithm does use the attention scores resulting from substituting both i and j of any given syntactic relation. We will add discussion to this effect to clarify this equation. This question also sparks an interesting possibility for future work, where substitutions are done in a pairwise fashion throughout the sentence and a more complex selection of attention distributions is performed. This idea would seem to converge towards the mutual information approach explored in Hoover et al. (2021).\n\n>B: Is there a motivation in particular to use a dataset with so short sentences? Is it more informative, easier to interpret, more representative of the targeted phenomena...? Since Experiment 2 focuses on long-distance agreement, the use of WSJ10 here is surprising.\n\nThe WSJ10 dataset is used in Experiment 1 in order to compare against baselines from previous work which also test this exact dataset. But for the long-distance agreement (Experiment 2), we use sentences from Marvin and Linzen’s (2018) long-distance agreement dataset, rather than the shorter sentences from WSJ10. We will clarify further in Section 4.\n\n>C: Experiment 1.1 selects layer 10, but which head (cf. multi-head attention)? How is the head selected? Or are the attentions also aggregated over heads of the same layer?\n\nThe attention distributions are aggregated over heads of the same layer (389-390). This choice follows work from Kim et al. (2020) who do similarly in the context of syntactic constituency parsing (433-434). We will clarify this methodological point in Sec 5.1 (Experiment 1) and further discuss how the layer we use corroborates previous findings in the aforementioned paper. Experiment 3 complements the use of layerwise attention distributions in Experiment 1 and explores SSUD with a method that aggregates scores from heads chosen across different layers (Limisiewicz et al, 2020).\n\nAdditionally, thank you for raising this suggestion about the abstract:\n> mention of \"increasing the number of substitutions\" in the abstract (line 17) is confusing\n\nWe will rephrase the abstract in order to make it clear that substitutions are used to model syntactic substitutability before referring to increasing the number of substitutions.\n\nBased on comments from reviewer 5gCw, we will also be including results from experiments using an additional model (BERT-large) to further support our hypothesis, new experimental results in support of our examples and error analysis by comparing UD annotation with Surface-Syntactic UD (Gerdes et al., 2018), and further discussion about sentence generation in the camera-ready version. In summary, we find strong trends with BERT-large, and even larger improvements when we test on Surface-Syntactic UD.\n\nWe hope to have sufficiently answered each of your questions and will add clarification with respect to the datasets and attention head selection to the camera-ready paper as well. Given your assessment and these improvements, would you consider championing our paper for publication at this conference? We are happy to engage further.", "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": "The proposed methodology is a very interesting idea that sheds new light on unsupervised parsing. It also benefits from solid theoretical foundations, and the experiments are organized, conducted and analyzed with a rigorous methodology.\n\nThe problem statement is carefully laid out in §3.1, and more generally the framing and formalism provided for the work are great.\n\nThe detailed analysis made of the results of Experiment 3 (lines 578 and beyond) is another token of that good methodology. I appreciated the detailed examples and error analysis in Annex C as well.\n\nThe paper itself is well-written and well-structured.\n\nAnnex E denotes extensive efforts for reproducibility (documenting as far as the package versions). And the (too rare) discussion on the licensing of the data is worth noting (annex F).", "reasons_to_reject": "~~Beyond minor presentation issues, the only shortcoming is a lack of clarity of the methodology regarding the step of head selection (see Question C below).~~ Only minor presentation issues", "questions_to_authors": "A - Equation (5): Since the dependencies are undirected, why are the substitutions done only on i, and not j as well?\n\nB - Line 369: is there a motivation in particular to use a dataset with so short sentences? Is it more informative, easier to interpret, more representative of the targeted phenomena...? Since Experiment 2 focuses on long-distance agreement, the use of WSJ10 here is surprising.\n\nC - Experiment 1.1 selects layer 10, but which head (cf. multi-head attention)? How is the head selected? Or are the attentions also aggregated over heads of the same layer?", "paper_topic_and_main_contributions": "This paper introduces a new method for unsupervised dependency parsing, based on syntactic substitutability (using the ability to substitute a given word as a means to consolidate the estimation of corresponding subtrees). It presents both a theoretical framework for grounding the method, and experiments to evaluate it empirically. Experiments show promising results for the method in general, and huge improvements on harder constructions of long-distance agreement. The paper also includes first positive results on combining that method with other existing methods for unsupervised dependency parsing.", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Typos_Grammar_Style_and_Presentation_Improvements": "- The mention of \"increasing the number of substitutions\" in the abstract (line 17) is confusing, because at that stage the reader does not know that k=1 in Experiment 1.1. Either rephrase to better contextualize the idea, or else avoid mentioning in the abstract this point about the increase.\n- There are inconsistencies in the numbering of Figures and Tables (there is Figure 1 vs Table 1, but then suddenly there is no Table 4 because there is Figure 4).\n- Line 210, \"all words in **the** sentence\" would read better (= the same sentence as the one in line 209)\n- Typo line 234: substitability --> substitutability\n- Typo line 396: number --> number of\n- Line 426, \"As predicted, this may reflect\" is awkward. Do those results confirm an hypothesis, and which one? Or is this about restating the hypothesis made (on how to interpret such numbers)? It should read either as \"As predicted, this reflects\", or \"As discussed, this may reflect\"\n- Typo line 550: direction --> directions\n- Typo line 851: remove \"of\"\n- Typo line 854: remove \"is\"\n- Typo line 856: remove \"that the\"?"}}, {"review_id": "qgpi6q6T5a", "reviewer": "Reviewer_5gCw", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nWe would like to thank you for your detailed review of our paper and highlighting strengths like:\n* ‘Well-founded linguistic motivation,’ also reviewer cSPA\n* ‘Simple and straightforward extension of existing techniques,’ also reviewer z2Sw\n\nStrengths other reviewers mentioned include:\n* ‘[Great] framing and formalism,’ ‘well-structured’ paper and ‘detailed examples and error analysis,’ reviewer cSPA\n* ‘General-purpose’ nature  ‘e.g. data augmentation even in supervised settings,’ reviewer z2Sw\n\nWe discuss the criticism of the implementation and motivation:\n> do not elaborate on a core component… BERT can easily generate synonyms… e.g., love-like or thought-figured… attention will probably model the close semantic relation\n\nWe respectfully disagree. We test whether substitution enables better extraction of syntax, drawing on the intuition that syntactic information is shared across different substitutions. BERT can generate synonyms, however, we hypothesize and show that more substitutions obviates the effect: in Tab. 2, 4, & 5, parsing scores increase with more substitutions. We do not claim that single substitutions effectively instantiate syntactic classes for parsing.\n\nWe point out that **‘thought-figured’ and ‘like-love’ are closely related due to syntactic constraints**. ‘Thought’ can only be substituted by verbs embedding full clauses, which often express speaker stance. No verbs like ‘eat’ embed full clauses. Substituting verbs that take different complements leads to structure change or ungrammaticality. **As desired, ‘thought-figured’ and ‘like-love’ reflect fine-grained syntactic categories.** Words from larger syntactic categories contrast this, e.g. 'know-help' (Fig. 3).\n\nIn the camera-ready version, we will address these concerns by\n* providing more examples of generated substitutions in Fig. 3,\n* elaborating on proper substitutions, discussing considerations like verb subcategorization.\n\n> the random fact that... syntactic information was sufficiently captured in BERT Layer 10... do not really contribute to understanding how LLMs model syntactic information.\n\nWe would like to point to our stated motivation (80-84) that we investigate **substitutability for extracting syntactic information in parsing**. We argue that modelling substitutability better captures how syntax is ontologically defined. It follows that unsupervised induction enables future work to compare model-derived structures and human annotations.\n\nOur choice to use BERT-base stems from the vast literature using it for extracting unsupervised syntax (Kim et al. 2020, Limisiewicz et al. 2020, Zhang and Hashimoto 2021) and probing (Hewitt and Manning 2019, Clark et al. 2020). Following a suggestion from the reviewer, we also tested another model BERT-large and will report results from **experiments in the camera-ready version**. In BERT-large, we find **SSUD improves parsing by 1.4pts (Layer 17) and 1.9pts (Layer 18)**. Layer 17 UUAS is 46.9.\n\n**We also strongly contend that these results are not ‘random.’** Instead, our finding that dependency information is centered at Layer 10 of BERT-base and Layer 17/18 of BERT-large **corroborates previous work from Kim et al (2020)** who find constituency information is centered at Layer 9 (base) and Layer 16 (large). Since Tenney et al (2019) show that constituency occurs before dependency, our findings are well-grounded in the existing literature.\n\nTo address these concerns, we will improve our error analysis of induced parses (Sec 5.3, Fig.4 and App. B) where **we observe a tendency towards relations headed by function words** with following experiment: induced parses on EN-PUD are scored using two annotations, UD and Surface-Syntactic Universal Dependencies (SUD, Gerdes et al., 2018). Unlike in UD, **SUD uses function words as heads**. Here, we find strong experimental support: **scored on SUD, UUAS is 12.6pts higher than on UD (59.0 vs 46.4).** SSUD provides a 3.0pt improvement over the baseline when assessed on SUD, compared to the 2.1pt improvement with UD.\n\nGiven this, we find that SSUD provides solid improvements, not just ‘slightly better.’ Improvements of 3.0pts in unsupervised parsing are on par with previous work (e.g. +2.8pts over baseline; Zhang and Hashimoto, 2021). Relation level results (Experiment 2 and 3) and the experiment above show how annotation differences can obfuscate improvements.\n> paper could have easily been fit into 4 pages\n\nIn order to cover the theoretical motivation and experiments on multiple datasets, this would require a longer appendix. We find this less desirable.\n\nIn summary, we will (i) further discuss substitution generation, and (ii) provide new experiments to evaluate SSUD on BERT-large and give further evidence that SSUD has systematic improvements for parsing in the camera-ready version. We hope we have addressed your concerns point-by-point.\n\nIn light of the clarification and these improvements, would you reconsider the evaluation of our work and raise the scores? We are happy to engage further.\n\n**Additional references:**\n\nKim Gerdes, Bruno Guillaume, Sylvain Kahane, and Guy Perrier. 2018. SUD or Surface-Syntactic Universal Dependencies: An annotation scheme near-isomorphic to UD. In Proceedings of the Second Workshop on Universal Dependencies (UDW 2018), pages 66–74, Brussels, Belgium. Association for Computational Linguistics.", "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": "- Simple and straightforward extension of existing techniques\n- Well-founded linguistic motivation of the proposed method\n- A focused contribution to understanding the ways Transformer-based models capture syntactic information", "reasons_to_reject": "Despite some merits, I tend towards rejecting the paper.\n\nOne reason is that I am not convinced that the authors indeed elevate the problem of previous methods that the relations modelled by attention are indeed syntactic in nature.  Although they had 8 pages, the authors do not elaborate on a core component of their method, namely the sentence generation procedure. They mention BERT and the usage of POS tagger to control the generated sentences but this may not be enough. For example, BERT can easily generate synonyms or very closely related words, e.g., love-like or thought-figured. In such cases, the attention will probably model the close semantic relation rather than a syntactic one.\n\nAnother reason is the lack of generalisation accross models. The average attention mechanism the authors propose can easily be tried with  other models. After all, we cannot draw reliable conclusions about how LLMs model syntactic information by the random fact that in this experiment setup it seemed that syntactic information was sufficiently captured in BERT Layer 10. Without more details provided or even assumptions, it seemed to me that the results are quite random and do not really contribute to understanding how LLMs model syntactic information.\n\nIn general, I think that the paper would have had better chances as a short paper submission. The contribution and the experiments are rather small and focused. The authors spend a lot of space explaining obvious things or terms as well as repeating information, especially with regard to previous work. Instead, the paper could have easily been fit into 4 pages, with more details on the core parts of the approach.", "questions_to_authors": "", "paper_topic_and_main_contributions": "The paper explores a novel approach of inducing syntactic dependencies from the attention heads of Transformer-based language models. The core of the approach is to use not only the attention of the target sentence but also to average accross the attention distributions of additionally generated sentence with the same syntactic properties. The authors employ the phenomenon of syntactic substitutability to generate syntactically invariable alternative sentences. The assumption is that syntactic relations operate on word categories rather than individual words, i.e. a syntactic relation should remain the same, if the two words it connects are substituted with words from the same categories.\n\nThe authors show that their method induces slightly better dependency structures than the case when only the target sentence is considered. The authors also zoom in on a specific phenomenon, namely long-distance subject-verb relations to evaluate the effect on more difficult syntactic dependencies. By replacing the attention matrices of an existing algorithm with matrices generated via the proposed method, the authors can directly compare the results and show improvement when their method is used.", "excitement": 4, "reproducibility": 5, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Vtz9kwH08u", "reviewer": "Reviewer_z2Sw", "summary": "", "questions": "A. On the one hand, SSUD seems to require a lot of extra passes over each sentence to create substitutions; on the other hand, these passes happen at inference time and so each one should be relatively fast. What is the overall cost of using SSUD in terms of added time?\n\nB. Section 7.2 argues that performance on closed classes suffers when k increases, while performance on open classes increases. Is it viable to let k vary, so that larger k is used for some words and smaller k for others? Could an agent be trained to predict the optimal k for each token?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nWe would like to thank you for your detailed review of our paper and for highlighting some of the following strengths:\n* The general utility of our methodology which is not ‘tied to a particular formalism or set of categories’\n* Future applications including: ‘distilling syntactic information from any kind of feature vector,’ ‘potentially [...] discontinuous constituents,’ and ‘data augmentation even in supervised settings.’\n\nStrengths mentioned by other reviewers include:\n* Our ‘[great] framing and formalism provided for the work,’ reviewer cSPA\n* The ‘well-written and well-structured’ paper and ‘detailed examples and error analysis,’ reviewer cSPA\n* A ‘well-founded linguistic motivation,’ reviewer 5gCw\n\nWe also engage with your concerns, questions, and suggestions below:\n\n> What is the overall cost of using SSUD in terms of added time? \n\nOn EN-PUD, the average wall-time to parse 1 sentence with SSUD (k=10) is 1130ms, compared to 470ms without using any substitutions. In our current implementation, we batch the substitutions at each word when performing inference. One clear way to scale this up is to perform batched inference on all substitutions of a given sentence, which we can expect to decrease the time difference even further, making our technique more viable.\n\n> Is it viable to let k vary, so that larger k is used for some words and smaller k for others? Could an agent be trained to predict the optimal k for each token?\n\nThank you for this interesting suggestion! A possibility would be to simply vary the number of substitutions based on syntactic category (e.g. use higher k for nouns and lower for determiners) and tuning these hyperparameters using the development set. This would maintain our unsupervised setup, and the results from Experiment 3 suggest that this may be fruitful, as the reviewer has already noted. Extending SSUD to a supervised setup, it is plausible that we would get greater improvements by training a model to choose k based on more fine-grained syntactic classes. For example, transitive verbs like ‘see’ inherently form a larger class than verbs like ‘believe’. We will mention this as an avenue for future work.\n\n> Using too few substitutions produces worse results than the baseline in some settings (Table 1, albeit by a very small margin).\n\nTable 1 reports layerwise results, with SSUD performing slightly worse than the baseline (-0.1) in two instances. Previous work has shown that linguistic information, like syntax, is not uniformly present in all layers (Tenney et al, 2019). Kim et al. (2020) find that higher layers perform best for syntactic parsing, similar to what we have used. We suggest that in layers where syntactic information is not robustly represented, using substitutions may lead to random effects such as no longer predicting edges that were previously predicted due to non-syntactic information, leading to the score decrease. This is further supported by the fact that lower layers perform much worse when only non-adjacent edges are considered, e.g. Layer 7 has only 6.7 recall, compared to 24.9 for Layer 10. Given this, we believe that the **slightly worse results may say more about the model than the effectiveness of our methodology**. We will add these additional analyses within Appendix B. \n\nBased on comments from other reviewers, in the camera-ready version we will also be including results from experiments using bert-large where we find the improvements even larger, new experimental results in support of our examples and error analysis by comparing UD annotation to Surface-syntactic UD (Gerdes et al., 2018), and further discussion about sentence generation (see response to reviewer 5gCw). We will also include clarifications with respect to methodology and dataset usage (see response to reviewer cSPA).\n\nWe hope that we have addressed your questions and concerns above and will add discussion about your suggestions for future work to the camera-ready version. Given this discussion, would you be willing to reconsider some of the reasons provided for rejection in your review? We are happy to engage further.", "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": "The proposed technique is simple, theory-agnostic, and requires no supervision, yet is clearly effective at distilling syntactic information from attention distributions. The general idea of using a masked LM to generate syntactically isomorphic sentences seems very general-purpose, and could probably be used for e.g. data augmentation even in supervised settings. Although the authors focus on attention distributions, in principle this technique seems suitable for distilling syntactic information from any kind of feature vector, e.g. an LM's hidden states. Theoretically, the work depends only on the intuition that instances of the same syntactic category can be substituted for one another, so it is not tied to a particular formalism or set of categories. The current work only considers individual words, but there is a clear avenue for future work which would investigate longer substitutions (potentially even including discontinuous constituents, which should be easily handled given the use of a masked LM). Overall the ideas presented in this work seem like they could be generally useful even though the work itself does not achieve state-of-the-art results.", "reasons_to_reject": "I do not see any strong reasons to reject.\n\nPre-rebuttal comments:\nIf I have understood the proposed method correctly, it is necessary to perform a full pass over the entire sentence each time a word is substituted, and each word in the sentence will get substituted multiple times over. This seems like a disproportionate amount of extra computation relative to the observed performance gains. This issue is compounded by the fact that using too few substitutions produces *worse* results than the baseline in some settings (Table 1, albeit by a very small margin).", "questions_to_authors": "A. On the one hand, SSUD seems to require a lot of extra passes over each sentence to create substitutions; on the other hand, these passes happen at inference time and so each one should be relatively fast. What is the overall cost of using SSUD in terms of added time?\n\nB. Section 7.2 argues that performance on closed classes suffers when k increases, while performance on open classes increases. Is it viable to let k vary, so that larger k is used for some words and smaller k for others? Could an agent be trained to predict the optimal k for each token?", "paper_topic_and_main_contributions": "This work proposes a technique to boost syntactic signals to enable dependency relations to be recovered directly from an LM's attention distributions. The authors propose to mask individual words in a target sentence, and to infill these masks with a model such as BERT. The infilled sentences should tend to have isomorphic dependency structures but different vocabulary. The authors propose that averaging the attention distributions from several such infilled sentences will tend to smooth over parts of the distribution which represent non-syntactic information, while leaving shared syntactic features intact. \n\nThe authors empirically demonstrate that this averaging procedure improves both labeled and unlabeled attachment scores and increases head selection accuracy when the attention distributions are used as input features to induce a dependency parse, relative to a baseline which only uses the original, un-averaged attention distribution. Although their results are not state-of-the-art, the technique is simple, theory-agnostic, and requires no supervision.", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a novel unsupervised dependency parsing approach based on LLM's attention heads. It offers a theoretical foundation for the method and empirical evaluations, revealing especially promising results for more challenging phenomena, such as long-distance subject-verb agreement. 

In the case of this submission, the scores of the reviewers are unanimous. It is a **strong submission** -- both regarding soundness (score 4) and excitement (score 4). Among the strengths of the paper, the reviewers mentioned a lot of very important points:
* solid theoretical foundations
* simple and well-targeted method
* great methodology, well-written and well-structured paper
* detailed analysis helping to understand a particular issue
* clear future work directions

After the first round of reviews, the biggest weakness of the paper were unclear details (e.g., sentence generation, head selection). However, as reviewer 5gCw said in the discussion, *"the authors went above and beyond in their response to answer [reviewer's] criticism"*. As a result, the concerns of two reviewers eased after the rebuttal phase. They encourage the authors to clarify the details of the paper and improve smaller presentation issues for the camera-ready version.
Decision: Accept-Main