#  Multilingual Nonce Dependency Treebanks:
Understanding how LLMs represent and process syntactic structure

David Arps1, Laura Kallmeyer1, Younes Samih2, Hassan Sajjad3
Heinrich-Heine-Universität Düsseldorf1, IBM Research2, Dalhousie University3
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

We introduce SPUD (Semantically Perturbed Universal Dependencies), a framework
for creating nonce treebanks for the multilingual Universal Dependencies (UD)
corpora. SPUD data satisfies syntactic argument structure, provides syntactic
annotations, and ensures grammaticality via language-specific rules. We create
nonce data in Arabic, English, French, German, and Russian, and demonstrate
two use cases of SPUD treebanks. First, we investigate the effect of nonce
data on word co-occurrence statistics, as measured by perplexity scores of
autoregressive (ALM) and masked language models (MLM). We find that ALM scores
are significantly more affected by nonce data than MLM scores. Second, we show
how nonce data affects the performance of syntactic dependency probes. We
replicate the findings of Müller-Eberstein et al. (2022) on nonce test data
and show that the performance declines on both MLMs and ALMs wrt. original
test data. However, a majority of the performance is kept, suggesting that the
probe indeed learns syntax independently from semantics.

##  1 Introduction

An ample amount of work in the last years has focused on making explicit the
linguistic information encoded in language models (LMs). The overarching
question in this line of work is to which extent the behavioral and
representational properties of self-supervised LMs are cognitively plausible
and also assumed by linguistic theory (surveys: Linzen and Baroni, 2021;
Kulmizev and Nivre, 2022; Mahowald et al., 2023; Chang and Bergen, 2023). A
subset of this work aimed at understanding LMs ability to learn syntax
(survey: Kulmizev and Nivre, 2022, examples: Hewitt and Manning, 2019; Manning
et al., 2020; Tenney et al., 2019; Newman et al., 2021). A common yet
controversial approach to this is to rely on the performance of a probing
classifier Hupkes et al. (2018); Belinkov (2022); Kunz and Kuhlmann (2020,
2021) in predicting syntactic relations. Maudslay and Cotterell (2021)
highlighted that this can be misleading due to the presence of semantic
knowledge in the representation. In other words, a high probing accuracy may
be fully/partially attributed to the use of present semantic knowledge.

The theoretical linguistic literature has discussed this issue for decades,
starting with the sentence Colorless green ideas sleep furiously in Chomsky
(1957), which is grammatical but nonsensical. A number of probing studies
addressed this issue and proposed methods to create systematically perturbed
data that disentangle syntax from semantics Gulordava et al. (2018); Maudslay
and Cotterell (2021); Arps et al. (2022). None of the works ensures however
that the nonce data is grammatical, e.g. replacements for predicates might
have different valency because word replacements are based only on part-of-
speech (POS) tags and few other constraints. Furthermore, Maudslay and
Cotterell (2021) and Arps et al. (2022) base their conclusions on English
only.

In this paper, we aim to standardize the efforts in this direction by
proposing a framework to create nonce data that satisfies syntactic argument
structure, provides syntactic annotations, and ensures grammaticality via
language-specific rules. The framework relies on the Universal Dependencies
(UD, de Marneffe et al., 2021) treebank. For each sentence in the treebank, it
replaces content words with other content words that are known to appear in
the same syntactic context. This results in nonce sentences that preserve the
syntactic structure of the original sentences (see Fig. 1). To ensure
syntactic grammaticality, we define three types of language-specific rules and
constraints that are applied during the process, which are: (i) the POS tag of
the words to be replaced, (ii) constraints on word order and dependency
relations of replaced words to ensure syntactic grammaticality, and (iii)
word-level rules to ensure that morphosyntactic constraints are met. We refer
to this algorithm and the resulting UD data as _semantically perturbed UD_
SPUD.

We create SPUD data for five linguistically diverse and widely spoken
languages; English, Arabic, French, Russian, and German. The dataset
contributes to the experimental linguistic literature that relates the notions
of grammaticality, acceptability and probability with language models
Gulordava et al. (2018); Sprouse et al. (2018); Lau et al. (2017, 2020). It
has the potential to serve various applications such as measuring the
robustness of LMs to semantic irregularities, a precise probing of syntax
without the influence of semantics, and comparing architectures such as
autoencoder and autoregressive in their learning of syntactic structure.
Moreover, the framework enables the creation of syntactically correct trees
that can be used for data augmentation in low-resource settings for dependency
parsing and other syntax-oriented tasks.

In this paper, we show the effectiveness of the nonce data using two tasks: LM
scoring across different architectures, and structural probing. The former
studies the effect of nonce data, i.e. semantic perturbations on various LM
scoring functions such as masked LM (MLM), and autoregressive LM (ALM). The
latter investigates the robustness of syntactic dependency probes to semantic
irregularities and disentangles the effect of lexical semantic features on the
findings.

The contributions and main findings of our work are as follows:

  * •

We introduce SPUD , a framework for creating nonce treebanks for UD corpora
that ensures syntactic grammaticality, and provide nonce treebanks for 5
languages (Arabic, English, French, German, Russian).

  * •

We show the effectiveness of the proposed data log-likelihood scoring of
different language model architectures, and on the performance of syntactic
dependency probes.

  * •

We show that ALM perplexity is significantly more affected by nonce data than
two formulations of MLM pseudo-perplexity, and that for MLMs, the availability
of subword information affects pseudo-perplexity scores on both natural and
SPUD data.

  * •

In structural probing for dependency trees, we show that ALM performance
decreases more than MLM performance on SPUD , and that this performance drop
is more pronounced for edge attachment than relation labeling.

The paper is structured as follows. In the next section, we discuss related
work that is relevant to our contributions. In Sec. 3, we describe the
framework for creating nonce UD treebanks in five languages. In Sec. 4, we
describe the experiment on scoring nonce data with perplexity. In Sec. 5, we
describe the structural probing experiments. In Sec. 6, we discuss the results
and conclude.

DET & NOUN & AUX & ADJ & CCONJ & ADJ & PUNCT
The & service & was & friendly & and & fast & .
The & interior & was & nuclear & and & fresh & .
21det 4root 42nsubj 43cop 46cconj 47punct 65cc  & NOUN
& interior
2nsubj 21det  & & ADJ & &
& & nuclear & &
3root 31nsubj 32cop 34cconj 35punct  & ADJ
& fresh
2cconj 21cc

(a) SPUD data creation

(b) Five nonce versions of the same sentence.

Figure 1: Example of SPUD data creation and example sentence.

##  2 Related Work

##### Automatically modified Dependency Trees

The idea to replace words and subtrees based on dependency structure has been
used for data augmentation in various areas of NLP, in particular for low-
resource dependency parsing. Dehouck and Gómez-Rodríguez (2020) propose an
idea similar to ours, with the differences that (i) they swap subtrees instead
of content words resulting in generated sentences with altered syntactic
structure, and (ii) their constraints on possible replacements are language-
agnostic. Şahin and Steedman (2018) cut subtrees based on their dependency
relation, and modify treebanks by changing the order of annotated dependency
subtrees. Vania et al. (2019) compare different techniques for low-resource
dependency parsing and demonstrate the effectiveness of Şahin and Steedman
(2018)’s algorithm as well as nonce treebanks similar to our creation (but
lacking the language-specific constraints and the reliance on dependency edges
to dependents). Nagy et al. (2023) apply similar techniques to parallel
sentences in low-resource machine translation tasks. Wang and Eisner (2016)
permute dependents within a single tree to generate synthetic treebanks with
lexical contents from one language and word order properties of another
language.

##### Structural Probing

DepProbe Müller-Eberstein et al. (2022) decodes labeled and directed
dependency trees from LM representations: Dependency relations are predicted
by a linear classifier as a sequence labeling task. Edges are predicted by
projecting the LM representation into a lower-dimensional vector space in
which vector distance corresponds to distance in the dependency tree. Müller-
Eberstein et al. (2022) use DepProbe to evaluate mBERT Devlin et al. (2019) on
13 languages, and show that probe performance is predictive of parsing
performance after finetuning the LM. Prior to that, Hewitt and Manning (2019)
introduced the structural probe for unlabeled and undirected dependency trees,
and Chi et al. (2020) extended this model to multilingual data. Kulmizev et
al. (2020) introduced a closely related architecture for directed but
unlabeled dependency trees. Eisape et al. (2022) use Hewitt and Manning
(2019)’s model to probe the ALM GPT-2 Radford et al. (2019). They show that
GPT-2 performs well on this syntactic probing tasks, even though the model
representations only contain one-sided context. Furthermore, they use the
internal representation of the model to predict the actions of a shift-reduce
parser, and intervene on the representations to steer model behavior.

##### Syntactic and Semantic Information in LMs

Gulordava et al. (2018) perform targeted syntactic evaluation (TSE; Marvin and
Linzen, 2018) on ALMs in four languages and investigate the effect of nonce
data that considers POS tags and morphological features for replacements.
Lasri et al. (2022a) investigate the effect of nonce data for TSE in BERT
Devlin et al. (2019) and find that BERT correctly predicts number agreement
for nonce sentences only in simple syntactic templates. Maudslay and Cotterell
(2021) investigate the effect of nonce words (or Jabberwocky words, such as
provicated) on syntactic probes. Ravfogel et al. (2020) find a transformation
of LM representations that highlights structural properties. Arps et al.
(2022) use a similar algorithm as ours to create nonce versions of the English
PTB, and train diagnostic sequence labeling classifiers to evaluate the
syntactic information in hidden representations of four MLMs. The main
difference to SPUD is that they do not restrict replacements to content words,
and they do not apply language-specific processing steps, therefore their
nonce data has a higher probability to be ungrammatical.

Sinha et al. (2021) test to which extent MLMs rely on word order vs. higher-
order cooccurence statistics. Concretely, they pre-train and fine-tune by
ablating word order to various degrees, and evaluate on fine-tuning and
probing tasks. They find that word order is not needed for many parts of a
"classical NLP pipeline", or for a MLM to achieve high performance on many
tasks. The reliance on word order is lowest in cases where task-specific
parameters are learnt. For tasks that rely on the language modeling head, the
reliance on word order is higher. Papadimitriou et al. (2022) probe the
relevance of word order and semantic prototypicality for classifying
grammatical roles with BERT.

Lasri et al. (2022b) compare BERT and human judgments on the subject-verb
agreement task for nonce data and find that, while the error patterns of both
are similar, BERT has a generally higher performance drop for nonce data than
humans. Kauf et al. (2023) explore the interaction of syntactic and semantic
information with similarity betweeen LMs and human fMRI signals, and show that
lexical semantic content - not syntactic structure - is the main driver of
similarity in both LM and human representations.

##### Scoring Functions for LMs

LMs are generally trained to maximize the likelihood of the training data. In
applications that target the linguistic information in the LM, the likelihood
of sentences assigned by a LM is often used to investigate the model’s
preference for grammatical sentences Kulmizev and Nivre (2022); Warstadt et
al. (2020). Perplexity ($PPL$) is a common metric to score the likelihood of a
sentence with ALMs. For MLMs, estimating the likelihood of a given sentence in
a fashion that is useful for applications is not as trivial. Salazar et al.
(2020) formalize pseudo-perplexity ($PPPL$) as a scoring function for MLMs:
Each token in a sentence is masked in turn, and $PPPL$ is computed as a
function of the MLM’s probability of the masked tokens. Kauf and Ivanova
(2023) show that $PPPL$ systematically inflates scores for multi-token words,
and propose $PPPL_{l2r}$, a subword-aware alternative that is more robust to
this effect. Miaschi et al. (2021) train classifiers on different linguistic
features to predict the $PPL$ of GPT-2 and $PPPL$ of BERT. They find that
GPT-2 scores are generally better predictable by their set of features than
BERT scores, and that lexical features are more important for GPT-2 than for
BERT.

##  3 Nonce Treebanks for Five Languages

This section presents SPUD (Semantically Perturbed Universal Dependencies),
our framework for nonce data creation. The input is a UD treebank, and the
output is a treebank with the same syntactic structure as the input but nonce
semantic content (Fig. 1(a)). In principle, the same algorithm is applied in
all languages, but each language requires a set of language-specific pre- and
post-processing steps (Sec. 3.1). Examples of generated English sentences are
presented in Fig. 1(b). Examples of other languages and information on the
used resources are in App. A. In this work, we create nonce data for five
languages: Arabic, German, English, French, and Russian. However, the
framework is general to create SPUD treebanks for any language in the UD
project, and the general idea of the algorithm can be extended to other
resources such as constituency trees. To apply the framework to a new
language, an annotated UD treebank and access to a native speaker in the
target language are required. Along with this paper, we publish a tutorial for
creating SPUD treebanks in other languages.

###  3.1 Generating nonce data

##### Languag-independent algorithm

The procedure consists of iteratively replacing content words with other words
that appear in the same syntactic context at another point in the treebank.
The words with ADJ, ADV, NOUN, PROPN and VERB part-of-speech tags are
considered content words. The syntactic context of a token $t$ is defined as
(i) the UPOS tag of $t$, (iii) the dependency relation of $t$ to its head, and
(iv) the dependency relations of $t$ to its dependents. This syntactic context
is collected for every lemma. Then, the nonce trees are created by replacing
content words with other words where the lemma appeared in the same syntactic
context. To determine the right form for a replacement, the morphological
databases UDLexicon (Sagot, 2018) and wiktextract Ylonen (2022) are used. An
example is depicted in Fig. 1(a) (without morphosyntactic features).

##### Language-specific modifications

The procedure described so far is language-independent. However, a number of
language-specific modifications are necessary to ensure that the data meets
the criteria of being semantically nonce but morphosyntactically correct. For
instance, English indefinite articles a/an depend on the following word, and
if the first sound of the following word changes from a vowel to a consonant
or vice versa, the article is adjusted with the help of a phonological
dictionary. When replacing apple in an apple with bicyle, the result is a
bicycle and not *an bicycle. We refer to App. A and our online
resources111https://github.com/davidarps/spud for details on the language-
specific modifications.

##### Quality of the generated data

We asked linguistically trained native speakers of the respective languages to
rate the generated sentences in terms of how they match the desired criteria
and to provide feedback on the syntactic quality of the generated data. The
annotators received samples of at least 100 sentence pairs per language. Over
2-3 iterations, the annotators pointed out problems in the generated data,
which were then addressed by modifying the language-specific rules.

##  4 Scoring SPUD with ALMs and MLMs

The SPUD treebanks are designed to be grammatical but highly improbable. In
this section, we investigate how this property is reflected in the predictions
of different LM architectures. On the one hand, this serves as a sanity check
for SPUD resources: Do we in fact perturb co-occurrence statistics of words as
intended? On the other hand, at a higher level, it investigates whether SPUD
data makes the models perplexed and how different LM architectures, and uni-
vs. bidirectional context, influence the effect that syntactic and semantic
structure has on model predictions. Concretely, we answer the following
questions for data in five languages: To what extent is SPUD data harder to
predict than original data? Are ALMs and MLMs affected by SPUD data in
different ways? Are MLM scoring functions affected differently by nonce data?
To support our findings, we analyze the lexical diversity of the SPUD datasets
separately in Appendix D, measured by Type-Token-Ratio (TTR). For all
languages, TTR decreases. This means that all our findings hold even though
SPUD data is less lexically diverse than original data.

###  4.1 Scoring functions for LMs

An illustrative example for all scoring functions is shown in App. E.1.

##### ALMs: Perplexity

$PPL$ of a sentence $x=(x_{1},\dots,x_{n})$ is commonly defined as the
exponentiated average of the negative sum of log probabilities for all tokens
$x_{i}$. The lower the perplexity, the higher the probability of $x$ for the
model.

$PPL(x)=exp(-\frac{1}{n}\sum_{i=0}^{n}\log p(x_{i}|x_{<i}))$ (1)

##### MLMs: Pseudo-Perplexity

($PPPL$) as defined by Salazar et al. (2020) is designed to capture the
likelihood that a MLM assigns to a sequence. The idea is that the model
processes the input $n$ times, masking each token $x_{i}$ exactly once.
$PPPL(x)$ is then defined via the sum of log probabilities that the LM assigns
to the masked $x_{i}$:

$PPPL(x)=exp(-\frac{1}{n}\sum_{i=0}^{n}\log p(x_{i}|x_{\setminus i}))$ (2)

##### MLMs: $PPPL$ with subword generation

Kauf and Ivanova (2023) propose $PPPL_{l2r}$, a variant of $PPPL$ that is more
aligned with $PPL$ for ALMs. The idea is to consider the groupings of tokens
to words, and predict subword tokens without conditioning on succeeding
tokens. Let $\omega_{r}(x_{i})$ denote the tokens that are in the same word as
$x_{i}$, including and succeeding $x_{i}$. For example, when tokenizing
accordeon as accord, ##eon, it holds that
$\omega_{r}(\textrm{accord})=\\{\textrm{accord, \\#\\#eon}\\}$. Then, tokens
$\omega_{r}(x_{i})$ from the right context within the same word are masked out
when predicting the token $x_{i}$:

$PPPL_{l2r}(x)=exp(-\frac{1}{n}\sum_{i=1}^{n}\log
p(x_{i}|x_{\setminus\omega_{r}(x_{i})}))$ (3)

####  4.1.1 Evaluating scoring functions on SPUD

When comparing scores across sentences, the variance is very high: Some
sentences are far more likely than others, irrespective of the language or
whether they are nonce. Thus, we focus our analysis on the ratios between
sentence-level scores of a pair of original and corresponding SPUD sentence
$(s_{orig},s_{nonce})$. For a scoring function
$f\in\\{PPL,PPPL,PPPL_{l2r}\\}$, we define the ratio $r_{f}$ as in Equation
(4) and then investigate the distributions of $r_{f}$ for all sentence pairs
in a corpus.

$r_{f}(s_{orig},s_{nonce})=\frac{f(s_{nonce})}{f(s_{orig})}$ (4)

###  4.2 Hypotheses

Hypothesis 1: LMs assign a higher score to SPUD data than to original data \-
the content words are chosen at random, and therefore should be much harder to
predict than the original words.

Hypothesis 2: ALMs and MLMs are impacted by SPUD data in different ways.
Bidirectional context determines the syntactic properties of a predicted token
to a larger degree than unidirectional context. Therefore, the space of
probable predictions is smaller for MLMs than for ALMs, and we expect that the
impact of SPUD data on ALM perplexity should be higher than on MLM pseudo-
perplexity.

Hypothesis 3: For SPUD, $r_{PPPL_{l2r}}$ are higher than $r_{PPPL}$ because
nonce words are hard to predict based on context from surrounding words, but
easy to predict based on context from the same word.

###  4.3 Experimental Setup

We adapt Kauf and Ivanova (2023)’s implementation to retrieve token-level
scores for all sentences in the SPUD and original data. We compare results for
mBERT Devlin et al. (2019) as a MLM and mGPT Shliazhko et al. (2022) as an
ALM. We report the scoring results of only one instance of SPUD data per
sentence. We argue that this is sufficient to draw conclusions about the
general behavior of the models, since we conduct the experiment on a large
number of sentences, and different languages.

###  4.4 Results

| $r_{PPPL}$ | $r_{PPPL_{l2r}}$ | $r_{PPL}$
---|---|---|---
ar |  |  |
en |  |  |

Figure 2: Intrinsic evaluation results for English and Arabic. Plots for other
languages are in App. E.2.

##### Is SPUD data harder to predict than original data?

To test Hypothesis 1, we check the distribution of score ratios $r_{f}$ for
all scoring functions $f$. The results for mBERT and mGPT are shown in Fig. 2
and show that for all settings, the first quartile is larger than 1, i.e. the
score of SPUD sentences is higher than that of original sentences for the vast
majority of the data. This means that SPUD data receives lower likelihood than
original data and is therefore harder to predict, as expected.

##### Are scoring functions affected differently by nonce data?

To answer this question, we compare the distributions of score ratios for all
scoring functions, as displayed in Fig. 2. This question is answered in two
parts, and both parts hold irrespectively of whether outliers with $r_{f}>250$
are taken into account. First, we test Hypothesis 2 by comparing the
distributions of score ratios for ALMs and MLMs. Here, the picture is clear:
$r_{PPL}$ are significantly higher than both $r_{PPPL_{l2r}}$ and $r_{PPPL}$,
measured with a Wilcoxon signed-rank test. This result, and all following
results, are significant at $p\ll 0.001$. Second, we test Hypothesis 3 by
comparing the MLM scoring functions $r_{PPPL_{l2r}}$ and $r_{PPPL}$. Here, the
picture is less clear: All ratios are significantly different from each other
according to the same test, but $f_{PPPL_{l2r}}$ has slightly lower quartiles
than $r_{PPPL}$ for Arabic (in all other languages, the opposite is true).
This means that for all languages except Arabic, $PPPL$ is less affected by
SPUD data than $PPPL_{l2r}$.

##### Differences across languages and models

The same trends were tested for monolingual models in Arabic and English. The
list of models is provided in App. B, the results are presented in App. E.2.
In all monolingual settings, SPUD data is harder to predict than original data
(all first quartiles of ratio distributions are larger than 1). For
differences between ratio predictions, the picture is more mixed: Regarding
the difference between ALMs and MLMs, Arabic shows higher ratio quartiles for
$PPL$ than the MLM scoring functions. For English, the MLM scoring functions
are significantly higher than $PPL$222Note that this might be due to an
overlap between the training data of the English MLM, and the English UD
treebank we use for scoring.. Regarding the difference between $PPPL$ and
$PPPL_{l2r}$, the picture is the same as for multilingual models: For English,
$PPPL_{l2r}$ is significantly higher than $PPPL$, and for Arabic, the opposite
is true.

###  4.5 Interim Summary and Discussion

There are three main takeaways from this experiment. First, we find (as
expected) that SPUD data is harder to predict than original data in all
settings. Second, we find that ALM perplexity and two MLM scoring functions
respond differently to SPUD data: mBERT is affected less than mGPT, and within
mBERT, $PPPL_{l2r}$ is affected more than $PPPL$ for all languages except
Arabic (because of the availability of subword context). For monolingual
models, we see a more mixed picture where for English, ALMs are affected less
by SPUD data than MLMs, and for Arabic, the trend that $PPPL_{l2r}$ is
affected more than $PPPL$ is consistent.

These results suggest on one hand a special role of the Arabic language, and
on the other hand point to the possibility that these differences are not
systematic properties of model architectures and scoring functions, but rather
depend on the training data and tokenization. However, as a general trend, we
can hypothesize from the comparison between $PPPL$ and $PPPL_{l2r}$ that the
inflated scores for multi-token words that Kauf and Ivanova (2023) find for
$PPPL$ are carried over to SPUD data: If $PPPL$ increases less than
$PPPL_{l2r}$ for nonce data, this means that the increase in $PPPL$ is
cushioned by the high predictability of multi-token words in $PPPL$.

##  5 Nonce Dependency Probing

In this section, we measure the efficacy of SPUD in decoding the syntactic
knowledge learned in LM representations. Concretely, we train DepProbe
structural probes Müller-Eberstein et al. (2022) and compare the performance
on the standard (original) UD test sets with performance on SPUD test sets. We
choose DepProbe because none of its alternatives produces both directed and
labeled dependency trees. We investigate to which extent DepProbe performance
is influenced by lexical semantics rather than its desired task of predicting
purely syntactic properties. For the original and nonce data, we compare
probing performance across a number of dimensions: MLM and ALM architectures,
attachment and relation labeling subtasks, 5 languages for multilingual models
and 1 language (English) for monolingual models,

###  5.1 Probing Model

Müller-Eberstein et al. (2022) present DepProbe, a lightweight decoder for
directed and labeled dependency trees. The model consists of two learnt linear
transformations of the LM representations. Both transform $d_{h}$-dimensional
word representations into vectors that highlight a feature of the dependency
tree. $L$ is a sequence labeling classifier that predicts for each word the
label of the incoming dependency edge. $B\in\mathbb{R}^{d_{h}\times b}$
projects the LM representation in a syntactic subspace with $b<d_{h}$, where
word vector distances mimic the distance between words in the tree. The
outputs of both components are combined to construct the dependency tree in a
top-down fashion, selecting the token as root that has the highest probability
of being the root (as assigned by $L$). Details are provided in App. F.1.

###  5.2 Experimental setup

##### Metrics

We report the same metrics as Müller-Eberstein et al. (2022), all of which are
commonly used in the dependency parsing and probing literature. RelAcc is the
percentage of tokens for which the relation label of the incoming edge is
correctly predicted, UAS (unlabeled attachment score) is the percentage of
tokens for which the head token is correctly predicted, and LAS (labeled
attachment score) is the conjunction of RelAcc and UAS.

##### Hyperparameters

All probe hyperparameters were taken from Müller-Eberstein et al. (2022) in
order to replicate their results. For all models, the dimensionality of the
syntactic subspace is $b=128$. We take the hidden representations of layers 6
(7) as input to DepProbe’s distance (relation) component for all twelve-
layered models. Müller-Eberstein et al. (2022) trained probes on English data
for all layers of mBERT and chose the best-performing layer for each
component. We repeated this experiment to determine the best-performing layer
for the 24-layered mGPT (App. F.6), and found that layer 12 performs best for
both components.

##### Baselines

We use three baseline representations to ensure that the syntactic information
we probe for is (i) contextual in nature rather than dependent on word types,
and (ii) learnt during LM pretraining rather than by the probe. To estimate
how much information about the probing task is contained in the (context-
insensitive) token embeddings, we train DepProbe on mBERT’s embedding layer.
To estimate how much information about the probing task is acquired during
pretraining of a transformer LM, we train DepProbe on internal representations
of two transformer models that share the architecture of mBERT but randomize
either all parameters, or all parameters except the embedding matrix Belinkov
(2022). All trained probes outperform the baselines by large margins (minimal
difference of 15.9 LAS for mGPT on SPUD data). All baseline results are
presented in App. F.3.

###  5.3 Results

Results for all models and baselines are presented in Tables 1-3. In all
tables, $\Delta$ shows the performance drop between original and SPUD test
sets. In general, probe performance depends largely on the size of the
treebank. This trend is also visible in Müller-Eberstein et al. (2022), where
Kendall’s $\tau$ between LAS and treebank size in 13 languages for DepProbe is
0.50 (p = 0.017).

| RelAcc | UAS | LAS
---|---|---|---
| orig | $\Delta$ | orig | $\Delta$ | orig | $\Delta$
ar | 82.8 | 5.5 | 63.1 | 7.3 | 55.5 | 8.3
de | 92.7 | 1.7 | 84.4 | 3.4 | 80.2 | 4.0
en | 87.1 | 2.3 | 74.2 | 3.8 | 67.9 | 4.1
fr | 89.3 | 2.0 | 76.0 | 4.4 | 70.4 | 4.3
ru | 88.2 | 1.5 | 75.4 | 3.2 | 69.2 | 3.1
Table 1: DepProbe results for mBERT. $\Delta$ shows the performance drop when nonce data is used. | RelAcc | UAS | LAS
---|---|---|---
| orig | $\Delta$ | orig | $\Delta$ | orig | $\Delta$
ar | 85.2 | 7.7 | 59.5 | 12.6 | 53.4 | 13.5
de | 92.6 | 3.6 | 84.2 | 6.8 | 79.9 | 8.1
en | 82.8 | 5.2 | 58.9 | 5.5 | 52.2 | 6.5
fr | 87.5 | 2.8 | 69.6 | 6.2 | 64.0 | 6.7
ru | 88.7 | 3.0 | 75.6 | 5.4 | 69.6 | 6.0
Table 2: DepProbe results for mGPT. $\Delta$ shows the performance drop when nonce data is used. | RelAcc | UAS | LAS
---|---|---|---
| orig | $\Delta$ | orig | $\Delta$ | orig | $\Delta$
roberta-base | 85.9 | 2.5 | 70.9 | 3.6 | 64.0 | 4.0
gpt2 | 82.4 | 4.5 | 53.1 | 3.6 | 47.1 | 4.6
Table 3: DepProbe monolingual results for English

##### mBERT vs. mGPT

For all languages and settings except Arabic RelAcc (both test sets), and
Russian (all metrics, original data), mBERT outperforms mGPT in terms of
absolute performance. In addition, the performance drop on SPUD is larger for
mGPT than for mBERT in almost all settings. The difference in model
architectures is especially relevant for predicting the syntactic structure of
nonce data, where context is a more important cue than for original data. The
only exception to this is Russian, where mGPT outperforms mBERT in absolute
performance on original data but not on SPUD. This is likely due to the
distribution of languages in the pretraining data: mGPT’s training data put an
emphasis on Russian and regionally related languages Shliazhko et al. (2022).
The relatively low performance of both models on English, however, is most
likely explained by the relatively small size of the English treebank.

##### Relation labeling vs. attachment

DepProbe performance is measured in terms of the two components of the model:
The relation labeling component (RelAcc) and the attachment component (UAS).
While the absolute performance varies, for both models and all languages, the
performance drop is larger for the attachment component than for the relation
labeling component. mGPT shows a larger performance drop than mBERT for both
components when directly comparing the absolute performance drop per language.
In the most extreme case, the performance drop in UAS for Arabic is 7.3 points
for mBERT and 12.6 points for mGPT. This points in the same direction as the
performance of the embedding layer baseline: Relations are more easily
predictable from lexical cues. Attachment, on the other hand, requires more
contextual information, especially when the head is in the future context of
the dependent. This finding is particularly insightful because it shows that
probing for labeled and directed dependency trees highlights differences
between ALMs and MLMs that are not captured when ignoring relations and
directionality (e.g. Eisape et al., 2022).

##### Monolingual results

We also test the above hypotheses on two English monolingual 12-layered
models: GPT-2 Radford et al. (2019) and RoBERTa Liu et al. (2019), see Tab. 3
for the results. The trends are similar to the multilingual models: RoBERTa
outperforms GPT-2 on all metrics, and the performance drop is larger for GPT-2
than for RoBERTa (except for UAS , where it is the same). The only difference
is that for GPT-2, the separate components of the model show a behavior
inverse to the multilingual models: RelAcc shows a larger performance drop on
SPUD data (4.5) than UAS (3.6). However, this can be explained by the absolute
performances of the GPT-2 probe, which are much higher for RelAcc than for UAS
. This leaves less room for performance detriments on SPUD data at attachment
than at relation labeling.

###  5.4 Additional experiments

To test the robustness of our results, we conduct several additional
experiments. All details are presented in App. F. First, we test the effect of
different random seeds for the probe’s initial weights and the selection of
nonce words. We find that the performance is stable across random seeds.
Concretely, the largest observed standard deviation across random seeds was
0.35 points UAS for English SPUD data, and most of the other settings show
much lower standard deviations. Second, we test the effect of ignoring
dependency relations in nonce data creation, i.e. selecting replacements based
only on POS tags and language-specific rules. The results show that this kind
of nonce data produces worse probing results than SPUD data, with some cross-
lingual variation. Finally, we train DepProbe on all layers of mBERT and mGPT
and compare the performance on English original and SPUD data. Most
importantly, this confirms that all other experiments were run on the best-
performing layer for each model. Additionally, this provides insights into the
layerwise dynamics of both models.

###  5.5 Interim Summary

The probing experiments show an overall performance drop on SPUD data for both
MLMs and ALMs. In general, probes for MLMs perform better than probes for ALMs
on both original and SPUD data. In addition, the performance drop on SPUD is
higher for ALMs than for MLMs. This is likely due to the fact that ALM probes
have to predict structural information based on a representation with one-
sided contextual information.333In a small-scale qualitative analysis, we find
that this can explain many errors made by ALMs but not MLMs. All models show a
larger peformance drop for attachment than for relation labeling, and the
embedding layer baseline shows a relatively high performance on relation
labeling. This points in the direction that relation labeling information is
more easily predictable from lexical cues than attachment information and
that, on the contrary, MLMs are better at predicting attachment information
for nonce data than ALMs. Finally, when viewed in isolation, many SPUD test
sets show a high absolute performance, suggesting that probes indeed base
their predictions on syntactic information.

##  6 Discussion and Conclusion

##### SPUD

We present Semantically Perturbed Universal Dependencies (SPUD), a framework
for creating parallel nonsensical UD treebanks. In SPUD, content words are
replaced with other, randomly selected, content words to generate an arbitrary
amount of parallel sentences that share dependency structure but have
different, potentially nonce, meanings. Apart from the two use cases that we
present for SPUD, it has several applications such as data augmentation for
low-resource parsing or syntactic similarity benchmarks. We provide a tutorial
on how to extend the dataset for other languages with available UD treebanks.
Possible modifications and extensions to SPUD are (i) swapping subtrees rather
than words Dehouck and Gómez-Rodríguez (2020), or (ii) replacing words with
similar words according to some similarity metric, rather than randomly. While
we put significant effort into assuring the quality of the generated data, we
did not conduct a large-scale human evaluation, e.g. via crowd-sourced
grammaticality judgments. Finally, SPUD can contribute to the experimental
linguistic literature that relates the notions of grammaticality,
acceptability and probability with language models Gulordava et al. (2018);
Sprouse et al. (2018); Lau et al. (2017, 2020).

##### Scoring SPUD with ALMs and MLMs

In our first experiment, we measure perplexity and related scores of SPUD on
MLMs and ALMs. SPUD data has consistently higher scores (i.e., lower
likelihood) than parallel original data on all models. This shows that, as
desired, the lexical co-occurence patterns of content words in SPUD are
perturbed. Of all scoring functions, the increase in ALM $PPL$ is the highest.
With our experiments, we contribute to the open question of how best to
compute scores from MLMs by comparing $PPPL$ with subword-aware $PPPL_{l2r}$
Kauf and Ivanova (2023). The result is that, for most languages, $PPPL$ shows
a lower increase than $PPPL_{l2r}$. This supports Kauf and Ivanova (2023)’s
argument that $PPPL_{l2r}$ is more similar to $PPL$ than $PPPL$ is. However,
there is a significant difference in the increases of both MLM scoring
functions versus $PPL$. This indicates a more fundamental difference between
how ALMs and MLMs score sentences. Our results suggest that bidirectional
context in MLMs makes it easier to identify the syntactic properties of a
predicted word, even in nonce sentences.

##### Syntactic Dependency Probing of SPUD

We test DepProbe Müller-Eberstein et al. (2022) on SPUD test sets and find a
performance drop (compared to original test sets) for all languages and both
model architectures. However, a majority of the probe performance is
maintained. The ALM mGPT has a lower overall performance than mBERT, as well
as a higher performance drop on SPUD data. For both model architectures,
attachment contributes more to the performance drop than relation labeling
does. These findings confirm the results in Maudslay and Cotterell (2021) and
Arps et al. (2022). On the contrary, Eisape et al. (2022) find that GPT-2
performs on par with MLMs on structural probing of unlabeled undirected
dependency trees. This contrast highlights the importance of probe
architecture and task design.

##### Linguistic Information and LMs

Sinha et al. (2021) find that MLMs rely on higher-order co-occurrence
statistics for many parts, and can maintain high performance without word
order information. We view the same problem from a different angle: Our
scoring results show that, expectedly, LM predictions are optimized for co-
occurrence information. Our probing results, however, show that performance on
some tasks can be maintained to a high-degree even if concrete co-occurrence
at the lexical level is disrupted. Our comparison of MLMs and ALMs on both
experiments suggests that both model architectures process nonce data
differently, and that MLMs are better at identifying syntactic structure in
SPUD data than ALMs.

## Limitations

##### Model instances and architectures

All our direct comparisons between model architectures are limited by the fact
that we compare models with different hyperparameters, training data, and
tokenizers. To quantify the effect of each of these components on the
syntactic learning requires availability of models trained using various
combination of these settings.

##### Formulations of scoring functions

The literature varies in the way in which scoring functions are applied.
Assume that $\sigma=\sum_{i=0}^{n}\log p(x_{i}|context)$ is the sum of log
likelihoods in a scoring function such as $PPL$. We follow Salazar et al.
(2020) and divide $\sigma$ by sequence length and exponentiate
($exp(-(1/n)\sigma)$), as defined in Eq. 1. Kauf and Ivanova (2023), on the
contrary, base their experiments directly on $\sigma$. Due to the nonlinear
differences between both versions, it is possible that not all of our findings
on scoring functions are transferable to raw log likelihood scores. We do not
expect this to affect our main findings, especially since our comparison of
the exponentiated versions of $PPPL$ and $PPPL_{l2r}$ shows trends that are
consistent with Kauf and Ivanova (2023)’s findings on English data, the
language they focus on. However, we deem a more detailed comparison of scoring
functions with and without exponentiation is necessary to draw more general
conclusions, even though this is beyond the scope of this paper.

##### Structural Probing and Properties of Explanations

In the following, we discuss limitations of our probing experiments in terms
of the properties of explanations defined by Lyu et al. (2023). Several of
their criteria are met: First, our experiments are plausible (the resulting
dependency trees are intuitive to humans), Second, the critierion of Input
sensitivity relates closely to the interaction of syntax and semantics in
probing which we investigate. The definition is that “An explanation should be
sensitive (resp. insensitive) to changes in the input that influence (resp. do
not influence) the prediction” (Lyu et al., 2023, p. 6). This criterion is met
because (i) we directly investigate the effect of changing the semantic
content of the probe and model input, and (ii) because DepProbe is generally
sensitive to changes in syntax. Third, the criterion of Faithfulness states
that “an explanation should accurately represent the reasoning process behind
the model’s prediction” (Lyu et al., 2023, p. 1). Since we do not investigate
model predictions but probe predictions, this criterion is not directly
applicable. However, we can say that the probe predictions need not be
faithful, because DepProbe learns to predict syntactic structure in a
supervised fashion, and does not necessarily decode the syntactic
generalizations that the model has learnt. Finally, Completeness and
Minimality do not apply because they refer to explaining contributing factors
for model predictions rather than probe predictions.

## Acknowledgements

The work presented in this paper was partly supported by the DFG grant
“Unsupervised Frame Induction: Event Type Hierarchies and Complex Event Types
(FInd)”.

## References

  * Antoun et al. (2020) Wissam Antoun, Fady Baly, and Hazem Hajj. 2020.  AraBERT: Transformer-based model for Arabic language understanding.  In _Proceedings of the 4th Workshop on Open-Source Arabic Corpora and Processing Tools, with a Shared Task on Offensive Language Detection_ , pages 9–15, Marseille, France. European Language Resource Association.
  * Antoun et al. (2021) Wissam Antoun, Fady Baly, and Hazem Hajj. 2021.  AraGPT2: Pre-trained transformer for Arabic language generation.  In _Proceedings of the Sixth Arabic Natural Language Processing Workshop_ , pages 196–207, Kyiv, Ukraine (Virtual). Association for Computational Linguistics.
  * Arps et al. (2022) David Arps, Younes Samih, Laura Kallmeyer, and Hassan Sajjad. 2022.  Probing for constituency structure in neural language models.  In _Findings of the Association for Computational Linguistics: EMNLP 2022_ , pages 6738–6757, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Belinkov (2022) Yonatan Belinkov. 2022.  Probing classifiers: Promises, shortcomings, and advances.  _Computational Linguistics_ , 48(1):207–219.
  * Borges Völker et al. (2019) Emanuel Borges Völker, Maximilian Wendt, Felix Hennig, and Arne Köhn. 2019\.  HDT-UD: A very large Universal Dependencies treebank for German.  In _Proceedings of the Third Workshop on Universal Dependencies (UDW, SyntaxFest 2019)_ , pages 46–57, Paris, France. Association for Computational Linguistics.
  * Chang and Bergen (2023) Tyler A. Chang and Benjamin K. Bergen. 2023.  Language model behavior: A comprehensive survey.
  * Chi et al. (2020) Ethan A. Chi, John Hewitt, and Christopher D. Manning. 2020.  Finding universal grammatical relations in multilingual BERT.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 5564–5577, Online. Association for Computational Linguistics.
  * Chomsky (1957) Noam Chomsky. 1957.  _Syntactic Structures_.  Mouton and Co., The Hague.
  * Darwish and Mubarak (2016) Kareem Darwish and Hamdy Mubarak. 2016.  Farasa: A new fast and accurate Arabic word segmenter.  In _Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC’16)_ , pages 1070–1074, Portorož, Slovenia. European Language Resources Association (ELRA).
  * de Marneffe et al. (2021) Marie-Catherine de Marneffe, Christopher D. Manning, Joakim Nivre, and Daniel Zeman. 2021.  Universal Dependencies.  _Computational Linguistics_ , 47(2):255–308.
  * Dehouck and Gómez-Rodríguez (2020) Mathieu Dehouck and Carlos Gómez-Rodríguez. 2020.  Data augmentation via subtree swapping for dependency parsing of low-resource languages.  In _Proceedings of the 28th International Conference on Computational Linguistics_ , pages 3818–3830, Barcelona, Spain (Online). International Committee on Computational Linguistics.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Droganova et al. (2018) Kira Droganova, Olga Lyashevskaya, and Daniel Zeman. 2018.  Data Conversion and Consistency of Monolingual Corpora: Russian UD Treebanks.  In _Proceedings of the 17th international workshop on treebanks and linguistic theories (tlt 2018)_ , 155, pages 53–66. Linköping University Electronic Press Linköping, Sweden.
  * Dryer and Haspelmath (2013) Matthew S. Dryer and Martin Haspelmath, editors. 2013.  _WALS Online_.  Max Planck Institute for Evolutionary Anthropology, Leipzig.
  * Eisape et al. (2022) Tiwalayo Eisape, Vineet Gangireddy, Roger Levy, and Yoon Kim. 2022.  Probing for incremental parse states in autoregressive language models.  In _Findings of the Association for Computational Linguistics: EMNLP 2022_ , pages 2801–2813, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Guillaume et al. (2019) Bruno Guillaume, Marie-Catherine de Marneffe, and Guy Perrier. 2019.  Conversion et améliorations de corpus du français annotés en Universal Dependencies [conversion and improvement of Universal Dependencies French corpora].  _Traitement Automatique des Langues_ , 60(2):71–95.
  * Gulordava et al. (2018) Kristina Gulordava, Piotr Bojanowski, Edouard Grave, Tal Linzen, and Marco Baroni. 2018.  Colorless green recurrent networks dream hierarchically.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 1195–1205, New Orleans, Louisiana. Association for Computational Linguistics.
  * Hajic et al. (2009) Jan Hajic, Otakar Smrz, Petr Zemánek, Petr Pajas, Jan Šnaidauf, Emanuel Beška, Jakub Kráčmar, and Kamila Hassanová. 2009.  Prague Arabic Dependency Treebank 1.0.
  * Hewitt and Manning (2019) John Hewitt and Christopher D. Manning. 2019.  A structural probe for finding syntax in word representations.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4129–4138, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Hupkes et al. (2018) Dieuwke Hupkes, Sara Veldhoen, and Willem Zuidema. 2018.  Visualisation and ’diagnostic classifiers’ reveal how recurrent and recursive neural networks process hierarchical structure.  _Journal of Artificial Intelligence Research_ , 61:907–926.
  * Kauf and Ivanova (2023) Carina Kauf and Anna Ivanova. 2023.  A better way to do masked language model scoring.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 925–935, Toronto, Canada. Association for Computational Linguistics.
  * Kauf et al. (2023) Carina Kauf, Greta Tuckute, Roger Levy, Jacob Andreas, and Evelina Fedorenko. 2023\.  Lexical semantic content, not syntactic structure, is the main contributor to ann-brain similarity of fmri responses in the language network.  _bioRxiv_.
  * Köhler (2003) Reinhard Köhler. 2003.  _Zur Type-Token-Ratio syntaktischer Einheiten: Eine quantitativ-korpuslinguistische Studie_, pages 93–101. Deutscher Universitätsverlag, Wiesbaden.
  * Kulmizev and Nivre (2022) Artur Kulmizev and Joakim Nivre. 2022.  Schrödinger’s tree—On syntax and neural language models.  _Frontiers in Artificial Intelligence_ , 5.
  * Kulmizev et al. (2020) Artur Kulmizev, Vinit Ravishankar, Mostafa Abdou, and Joakim Nivre. 2020.  Do neural language models show preferences for syntactic formalisms? In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 4077–4091, Online. Association for Computational Linguistics.
  * Kunz and Kuhlmann (2020) Jenny Kunz and Marco Kuhlmann. 2020.  Classifier probes may just learn from linear context features.  In _Proceedings of the 28th International Conference on Computational Linguistics_ , pages 5136–5146, Barcelona, Spain (Online). International Committee on Computational Linguistics.
  * Kunz and Kuhlmann (2021) Jenny Kunz and Marco Kuhlmann. 2021.  Test harder than you train: Probing with extrapolation splits.  In _Proceedings of the Fourth BlackboxNLP Workshop on Analyzing and Interpreting Neural Networks for NLP_ , pages 15–25, Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Lasri et al. (2022a) Karim Lasri, Alessandro Lenci, and Thierry Poibeau. 2022a.  Does BERT really agree? fine-grained analysis of lexical dependence on a syntactic task.  In _Findings of the Association for Computational Linguistics: ACL 2022_ , pages 2309–2315, Dublin, Ireland. Association for Computational Linguistics.
  * Lasri et al. (2022b) Karim Lasri, Olga Seminck, Alessandro Lenci, and Thierry Poibeau. 2022b.  Subject verb agreement error patterns in meaningless sentences: Humans vs. BERT.  In _Proceedings of the 29th International Conference on Computational Linguistics_ , pages 37–43, Gyeongju, Republic of Korea. International Committee on Computational Linguistics.
  * Lau et al. (2020) Jey Han Lau, Carlos Armendariz, Shalom Lappin, Matthew Purver, and Chang Shu. 2020\.  How furiously can colorless green ideas sleep? sentence acceptability in context.  _Transactions of the Association for Computational Linguistics_ , 8:296–310.
  * Lau et al. (2017) Jey Han Lau, Alexander Clark, and Shalom Lappin. 2017.  Grammaticality, Acceptability, and Probability: A Probabilistic View of Linguistic Knowledge.  _Cognitive Science_ , 41(5):1202–1241.
  * Linzen and Baroni (2021) Tal Linzen and Marco Baroni. 2021.  Syntactic structure from deep learning.  _Annual Review of Linguistics_ , 7(1):195–212.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  RoBERTa: A Robustly Optimized BERT Pretraining Approach.
  * Lyu et al. (2023) Qing Lyu, Marianna Apidianaki, and Chris Callison-Burch. 2023.  Towards faithful model explanation in nlp: A survey.
  * Mahowald et al. (2023) Kyle Mahowald, Anna A. Ivanova, Idan A. Blank, Nancy Kanwisher, Joshua B. Tenenbaum, and Evelina Fedorenko. 2023.  Dissociating language and thought in large language models: a cognitive perspective.
  * Manning et al. (2020) Christopher D. Manning, Kevin Clark, John Hewitt, Urvashi Khandelwal, and Omer Levy. 2020.  Emergent linguistic structure in artificial neural networks trained by self-supervision.  _Proceedings of the National Academy of Sciences_ , 117(48):30046–30054.
  * Marvin and Linzen (2018) Rebecca Marvin and Tal Linzen. 2018.  Targeted syntactic evaluation of language models.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 1192–1202, Brussels, Belgium. Association for Computational Linguistics.
  * Maudslay and Cotterell (2021) Rowan Hall Maudslay and Ryan Cotterell. 2021.  Do syntactic probes probe syntax? experiments with jabberwocky probing.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 124–131, Online. Association for Computational Linguistics.
  * Miaschi et al. (2021) Alessio Miaschi, Dominique Brunato, Felice Dell’Orletta, and Giulia Venturi. 2021\.  What makes my model perplexed? a linguistic investigation on neural language models perplexity.  In _Proceedings of Deep Learning Inside Out (DeeLIO): The 2nd Workshop on Knowledge Extraction and Integration for Deep Learning Architectures_ , pages 40–47, Online. Association for Computational Linguistics.
  * Müller-Eberstein et al. (2022) Max Müller-Eberstein, Rob van der Goot, and Barbara Plank. 2022.  Probing for labeled dependency trees.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 7711–7726, Dublin, Ireland. Association for Computational Linguistics.
  * Nagy et al. (2023) Attila Nagy, Dorina Petra Lakatos, Botond Barta, Patrick Nanys, and Judit Ács. 2023\.  Data augmentation for machine translation via dependency subtree swapping.
  * Newman et al. (2021) Benjamin Newman, Kai-Siang Ang, Julia Gong, and John Hewitt. 2021.  Refining targeted syntactic evaluation of language models.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 3710–3723, Online. Association for Computational Linguistics.
  * Papadimitriou et al. (2022) Isabel Papadimitriou, Richard Futrell, and Kyle Mahowald. 2022.  When classifying grammatical role, BERT doesn’t care about word order… except when it matters.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 636–643, Dublin, Ireland. Association for Computational Linguistics.
  * Radford et al. (2019) Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019.  Language Models are Unsupervised Multitask Learners.
  * Ravfogel et al. (2020) Shauli Ravfogel, Yanai Elazar, Jacob Goldberger, and Yoav Goldberg. 2020.  Unsupervised distillation of syntactic information from contextualized word representations.  In _Proceedings of the Third BlackboxNLP Workshop on Analyzing and Interpreting Neural Networks for NLP_ , pages 91–106, Online. Association for Computational Linguistics.
  * Sagot (2018) Benoît Sagot. 2018.  A multilingual collection of CoNLL-U-compatible morphological lexicons.  In _Proceedings of the Eleventh International Conference on Language Resources and Evaluation (LREC 2018)_ , Miyazaki, Japan. European Language Resources Association (ELRA).
  * Şahin and Steedman (2018) Gözde Gül Şahin and Mark Steedman. 2018.  Data augmentation via dependency tree morphing for low-resource languages.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 5004–5009, Brussels, Belgium. Association for Computational Linguistics.
  * Salazar et al. (2020) Julian Salazar, Davis Liang, Toan Q. Nguyen, and Katrin Kirchhoff. 2020.  Masked language model scoring.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 2699–2712, Online. Association for Computational Linguistics.
  * Shliazhko et al. (2022) Oleh Shliazhko, Alena Fenogenova, Maria Tikhonova, Vladislav Mikhailov, Anastasia Kozlova, and Tatiana Shavrina. 2022.  mGPT: Few-Shot Learners Go Multilingual.
  * Silveira et al. (2014) Natalia Silveira, Timothy Dozat, Marie-Catherine de Marneffe, Samuel Bowman, Miriam Connor, John Bauer, and Chris Manning. 2014.  A gold standard dependency corpus for English.  In _Proceedings of the Ninth International Conference on Language Resources and Evaluation (LREC’14)_ , pages 2897–2904, Reykjavik, Iceland. European Language Resources Association (ELRA).
  * Sinha et al. (2021) Koustuv Sinha, Robin Jia, Dieuwke Hupkes, Joelle Pineau, Adina Williams, and Douwe Kiela. 2021.  Masked language modeling and the distributional hypothesis: Order word matters pre-training for little.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 2888–2913, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Sprouse et al. (2018) Jon Sprouse, Beracah Yankama, Sagar Indurkhya, Sandiway Fong, and Robert C. Berwick. 2018.  Colorless green ideas do sleep furiously: gradient acceptability and the nature of the grammar.  _The Linguistic Review_ , 35(3):575–599.
  * Tenney et al. (2019) Ian Tenney, Dipanjan Das, and Ellie Pavlick. 2019.  BERT rediscovers the classical NLP pipeline.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 4593–4601, Florence, Italy. Association for Computational Linguistics.
  * Vania et al. (2019) Clara Vania, Yova Kementchedjhieva, Anders Søgaard, and Adam Lopez. 2019.  A systematic comparison of methods for low-resource dependency parsing on genuinely low-resource languages.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 1105–1116, Hong Kong, China. Association for Computational Linguistics.
  * Wang and Eisner (2016) Dingquan Wang and Jason Eisner. 2016.  The galactic dependencies treebanks: Getting more data by synthesizing new languages.  _Transactions of the Association for Computational Linguistics_ , 4:491–505.
  * Warstadt et al. (2020) Alex Warstadt, Alicia Parrish, Haokun Liu, Anhad Mohananey, Wei Peng, Sheng-Fu Wang, and Samuel R. Bowman. 2020.  BLiMP: A benchmark of linguistic minimal pairs for English.  In _Proceedings of the Society for Computation in Linguistics 2020_ , pages 409–410, New York, New York. Association for Computational Linguistics.
  * Ylonen (2022) Tatu Ylonen. 2022.  Wiktextract: Wiktionary as machine-readable structured data.  In _Proceedings of the Thirteenth Language Resources and Evaluation Conference_ , pages 1317–1325, Marseille, France. European Language Resources Association.
  * Zerrouki (2010) Taha Zerrouki. 2010.  Pyarabic, an arabic language library for python.

##  Appendix A Nonce treebanks

###  A.1 Languages and resources

Table 4 summarizes the languages for which SPUD treebanks are generated. In
general, we use the UD test sets for evaluation, and also sample replacement
candidates from the UD test sets to avoid data leakage.

| Family, Genus | Writing system | UD treebank |  UDtrain tokens
---|---|---|---|---
Arabic | Afro-Asiatic, Semitic | Arabic | PADT, (Hajic et al., 2009) | 224K
English | IE, Germanic | Latin | EWT, (Silveira et al., 2014) | 205K
French | IE, Romance | Latin | GSD, (Guillaume et al., 2019) | 355K
German | IE, Germanic | Latin | HDT, (Borges Völker et al., 2019) | 2,754K
Russian | IE, Slavic | Cyrillic | SynTagRus, (Droganova et al., 2018) | 1,206K
Table 4: Summary of the languages for which nonce data is generated. IE =
Indo-European. Family and Genus according to Dryer and Haspelmath (2013).

###  A.2 Language-specific rules

For consistency, we implement the general rule in languages written in Latin
script that the replacement has to be capitalized if the replaced word was
capitalized.

##### Arabic

No language-specific rules are applied, except for the removal of diacritics
to increase the number of possible replacements.

##### German

Adjective suffixes are depending on several features, however, not all of
these features are consistently annotated in the available resources.
Concretely, the forms are inflected for Case, Number, Genus, Degree of
comparison, and Determinacy, leading to large inflection paradigms. For this
reason, we implement the rule that for adjectives ending in -e, -em, -en, -er,
-es, the replaced adjective has to have the same ending.

##### English

A word list is compiled from wiktionary using wiktextract (Ylonen, 2022) to
determine words starting with consonants or vowels. This list is used to
determine the correct indefinite article for English nouns: The choice of a or
an depends on the following word, which can be a replaced content word (e.g.,
an adjective or noun). The determiner is adjusted if the first sound of the
following word changes from a vowel to a consonant or vice versa. For example,
when replacing apple in an apple with bicyle, the result is a bicycle and not
*an bicycle.

##### French

In French, we implement a similar rule as for English determiners. Concretely,
we replace le/la/de/ with l’/d’ and vice versa if the following word starts
with a vowel, consonant, or aspirated h, respectively. The pronunciation of
the following word is determined from wiktionary using wiktextract (Ylonen,
2022). Furthermore, French adjectives fall into three classes: A fixed set of
adjectives precedes the noun. The majority of adjectives follow the noun. A
small set of adjectives can appear in both positions. For instance, grande
maison – ‘big house’ and voiture rouge – ‘red car’ are correct, but *maison
grande and *rouge maison are not. The syntactic context as defined in
generating nonce data does not capture the adjective classes. Thus, we replace
adjectives preceding (following) the head only with adjectives that also
precede (follow) the head in the UD treebank.

##### Russian

The rich case system in Russian poses a challenge for the algorithm as defined
above. Concretely, the case of dependents is not part of the syntactic
context. Contrary to the other languages in our sample, the case of an object
is determined by the verb, and both accusative and genetive case are possible
and frequent cases for these objects. This means that if a verb with an
accusative object is replaced with a verb with a genitive object, a case
mismatch is introduced. Since Russian nevertheless retains high probing
performance (Sec. 5), we did not explicitly address this problem.

###  A.3 Examples

For illustration purposes, we present relatively short sentences with multiple
nonce versions in Figures 3 (ar), 4 (de), 5 (fr), and 6 (ru).

NOUN & NOUN & NOUN & X & X & PUNCT & NOUN & ADP & NOUN
alsayid & almuhandis & alduktur & ghasaan & tayaarat & \- & waziran &
lilsinaeat & lilsinaea
alsayid & khabir & najah & ghasaan & tayaarat & \- & janub & lilsinaeat & batn
alsayid & tawasue & shakhs & ghasaan & tayaarat & \- & muhamad & lilsinaeat &
hal
alsayid & hal & eamil & ghasaan & tayaarat & \- & muhamad & lilsinaeat & dabit
alsayid & sahm & niqash & ghasaan & tayaarat & \- & janub & lilsinaeat & qamh
alsayid & yawm & mil & ghasaan & tayaarat & \- & janub & lilsinaeat & ghad

1root 12nmod 13nmod 54nmod 15nmod 16punct 17dep 98case 79nmod

NUM & SYM & NOUN & ADP & NOUN & NOUN & ADP & X
90 & % & ziadat & fi & sadirat & almansujat & ’iilaa & turkia
90 & % & masar & fi & tawasue & waqud & ’iilaa & turkia
90 & % & aism & fi & fariq & daght & ’iilaa & turkia
90 & % & hukm & fi & sijn & eali & ’iilaa & turkia
90 & % & eumar & fi & murashah & fibrayir & ’iilaa & turkia
90 & % & bad’ & fi & fard & shakhs & ’iilaa & turkia

1root 12nmod 13nsubj 54case 35nmod 56nmod 87case 58nmod

Figure 3: Arabic SPUD examples (in transliteration).

Figure 4: German SPUD examples.

Figure 5: French SPUD examples.

Figure 6: Russian SPUD examples.

###  A.4 Replacement statistics

| NOUN | PROPN | ADJ | ADV | VERB | total
---|---|---|---|---|---|---
ar | 0.93 | 0.77 | 0.93 | 0.74 | 0.66 | 0.47
de | 0.96 | 0.93 | 0.68 | 0.92 | 0.61 | 0.41
en | 0.85 | 0.84 | 0.86 | 0.83 | 0.59 | 0.38
fr | 0.83 | 0.69 | 0.88 | 0.92 | 0.50 | 0.36
ru | 0.84 | 0.70 | 0.80 | 0.89 | 0.46 | 0.39

Table 5: Ratio of replaced words per POS in the test set. The column "total"
shows the replacement ratio over all POS, including function words and
punctuation.

Tab. 5 shows the ratio of replaced words per POS in the test set. Of the 25
ratios (5 languages, 5 POS tags), 6 are above 0.9 and 14 are above 0.8,
indicating that the algorithm is able to find replacements for the vast
majority of content words. The replacement ratio is lowest for verbs, for two
reasons: First, verbs are generally less frequent than e.g. nouns. Second,
verbs frequently have a relatively complex argument structure, which leads to
a large number of syntactic contexts and an increased frequency of syntactic
contexts that are not shared with other verbs.

##  Appendix B List of Models

mGPT (Shliazhko et al., 2022, huggingface id: ai-forever/mGPT) and mBERT
(Devlin et al., 2019, bert-base-multilingual-cased) are used for all
experiments. English scoring and probing experiments are additionally
conducted with RoBERTa (Liu et al., 2019, roberta-base) and GPT-2 (Radford et
al., 2019, gpt2). Arabic scoring experiments are additionally conducted with
AraGPT2 (Antoun et al., 2021, aubmindlab/aragpt2-base) and AraBERT (Antoun et
al., 2020, aubmindlab/bert-base-arabertv2).

##  Appendix C Data preprocessing

We apply the following preprocessing steps to the UD treebanks after creating
SPUD splits. To allow a fair comparison between MLMs and ALMs, we filter out
sentences that are shorter than 4 words from the data in all experiments. On
short sentences, ALMs have a disadvantage because their per-token score
increases over the sentence given increasing context length, while the basic
masked language modeling task assumes access to the same amount of context for
each token. For SPUD in Arabic, we remove diacritics with the PyArabic library
(Zerrouki, 2010). The Arabic morphological lexicon is lemmatized with Farasa
(Darwish and Mubarak, 2016).

##  Appendix D Lexical Diversity of Nonce data

| TTR
---|---
Language | orig. | nonce
ar | .0094 | .0077
de | .0054 | .0043
en | .0571 | .0463
fr | .0441 | .0297
ru | .0052 | .0044
Table 6: Type-Token Ratio of underlying UD treebanks and SPUD versions.

##### Model-Independent Comparison: Type Token Ratio (TTR)

is a widely used measure of lexical diversity. where a larger value indicates
that less tokens are used repeatedly (Köhler, 2003). Apart from the
segmentation model (in our case the mBERT tokenizer), TTR focuses on capturing
the distribution of the data relatively independent from large computational
or methodological overhead. The TTR (when tokenized with mBERT) in all
languages is shown in Tab. 6.

##  Appendix E Scoring Experiments

###  E.1 Example for Scoring Functions

An example for how all scoring functions are computed for the phrase accordeon
player is displayed in Tab. 7.

| accord | ##eon | player
---|---|---|---
| ? | _ | _
$PPL$ | accord | ? | _
| accord | ##eon | ?
| ? | ##eon | player
$PPPL$ | accord | ? | player
| accord | ##eon | ?
| ? | _ | player
$PPPL_{l2r}$ | accord | ? | player
| accord | ##eon | ?
Table 7: The token for which a probability is recorded is marked with "?".
Tokens that are masked out or not available from context are marked with "_".

###  E.2 Scoring Experiment

In Tab. 8, we show the ratios of scoring functions for multilingual models in
German, French and Russian (complementing the English and Arabic results in
Tab. 2). In Tab. 9, we show the ratios of scoring functions for monolingual
models in Arabic and English.

| $r_{PPPL}$ | $r_{PPPL_{l2r}}$ | $r_{PPL}$
---|---|---|---
de |  |  |
fr |  |  |
ru |  |  |

Table 8: Scoring function ratios for multilingual models.

| $r_{PPPL}$ | $r_{PPPL_{l2r}}$ | $r_{PPL}$
---|---|---|---
ar |  |  |
en |  |  |

Table 9: Scoring function ratios for monolingual models (Arabic and English).

###  E.3 Scoring outlier analysis

For English, we investigate the sentence pairs with the highest and lowest
scoring function ratios. The sentences with the highest ratio are shown in
Table 10. Sentences with very high ratios are all relatively short. The large
difference in ratios between scores assigned by mBERT and mGPT indicate that
these original sentences could be part of the pre-training data for mGPT but
not mBERT - the former is overfitting to the original sentence. Also, these
sentences contain uppercase sentences (which might affect tokenization), and
almost all original sentences contain well-known named entities or common
phrases that are disrupted in the nonce data (U.S. Senate Committee, AS FAR AS
POSSIBLE, etc.)

The sentences with the lowest ratio are shown in Table 11. The examples
include typos in the original data (ling instead of long), an example in which
the original seems ungrammatical (6), and examples in which only single words
are replaced by other forms that are presumably more frequent (cover - go, Per
- Google, …)

sent_orig | sent_nonce | PPPL_ratio | PPPL_l2r_ratio | PPL_alm_ratio
---|---|---|---|---
NORTH CAROLINA RELIGIOUS COALITION FOR MARRIAGE… | D’ Vernon ugly Coalition For El Dong | 388.97 | 176.08 | 3320.79
U.S. Senate Committee on Appropriations | Can Bay Committee on Williss’ | 35734.78 | 16130.36 | 1027.64
SHE KNOWS GREAT FOOD AND DINING EXPERIENCES. | She solicits Swedish election And rabbit outlets. | 8.67 | 16.67 | 968.43
BEST CHINESE RESTAURANT EVER!!! | Truest corrupt Restaurant definitely!!! | 4.57 | 7.44 | 855.44
THEY ARE VERY RUDE AND NASTY. | They Are allegedly happy And hidden. | 80.31 | 38.98 | 797.19
my new OLYMPUS X940 DIGITAL CAMERA…? | My inhuman April Port wireless Camera…? | 10.03 | 5.29 | 759.14
STAY AWAY AS FAR AS POSSIBLE. | Move wrongest currently low As satisfactory. | 31.35 | 28.88 | 608.69
Super Pet Silent Spinner Exercise Wheel | Standard Fidelity alleged Alliance Prince Wheel | 257.01 | 74.85 | 538.77
CHERNOBYL ACCIDENT: TEN YEARS ON | Greenfield diplomacy: Ten Years partly | 10.86 | 17.24 | 511.29

Table 10: Selection of sentences with $r_{P}PL$ above 500. Data is printed
verbatim, including casing, punctuation, etc.

sent_orig | sent_nonce | $r_{PPPL}$ | $r_{PPPL_{l}2r}$ | $r_{PPL}$
---|---|---|---|---
New training Centre is excellent | Extensive vacation temperature is amazing | 0.01 | 0.32 | 0.04
Maria Valdes superior $62,500 | Todd Taylors’ strong $62,500 | 0.47 | 0.24 | 0.11
Gold award parts excellence, metro. | Hoodie leader coffees tank, Michelle. | 1.60 | 2.17 | 0.14
Talked to Craig and the Court today. | Talked to Emily and the viewer yesterday. | 0.05 | 0.43 | 0.16
oh god is there an agenda. | Oh god is there an antibiotic. | 0.22 | 0.20 | 0.18
Broke out the activities of 1179. | Checked out the spirits of 1179. | 0.79 | 0.69 | 0.21
Shanna, I spoke with Per tonight about this. | Kim, I spoke with Google yesterday about this. | 0.30 | 0.30 | 0.24
George Bush: Money manager | Roger’s Dick’s: garage therapist | 0.04 | 0.13 | 0.25
Is it possible to shoot lazers out of your Wang? | Is it great to see e-mails out of your house? | 0.08 | 0.06 | 0.28
if they hiss, they are not playing. | If they are, they are not running. | 0.62 | 0.49 | 0.34
Even though you are expensive. | Certainly though you are expensive. | 3.74 | 5.69 | 0.39
See you all there - this is ling overdue | See you all there - this is here deep | 1.19 | 0.56 | 0.44
Can you cover for me today? | Can you go for me tomorrow? | 0.18 | 0.43 | 0.46
Brazil we have current data already | Danny we have ambitious tongue feverishly | 0.08 | 0.82 | 0.47
Your cat will adjust quickly. | Your health will starve inappropriateliest. | 0.76 | 2.27 | 0.48

Table 11: Selection of sentences with $r_{PPL}<0.5$. Data is printed verbatim,
including casing, punctuation, etc. Data with such low ratios also included
longer sentences, which are omitted for space reasons.

##  Appendix F Probing Experiments

| why | does | my | snake | refuse | to | eat | ?
---|---|---|---|---|---|---|---|---
why | 0 | 2 | 3 | 2 | 1 | 3 | 2 | 2
does | 2 | 0 | 3 | 2 | 1 | 3 | 2 | 2
my | 3 | 3 | 0 | 1 | 2 | 4 | 3 | 3
snake | 2 | 2 | 1 | 0 | 1 | 3 | 2 | 2
refuse | 1 | 1 | 2 | 1 | 0 | 2 | 1 | 1
to | 3 | 3 | 4 | 3 | 2 | 0 | 1 | 3
eat | 2 | 2 | 3 | 2 | 1 | 1 | 0 | 2
? | 2 | 2 | 3 | 2 | 1 | 3 | 2 | 0

(a) Gold distance matrix for the example sentence.

|  covered words |  tree |  comment
---|---|---|---
1 |  $\\{refuse\\}$ |  refuse |
1root |  maximum $p(\texttt{root}|refuse)$ |  |
2-6 |  $\\{$why, does, snake, refuse, eat, ?$\\}$ |  why & does & snake & refuse & eat & ? |
41advmod 42aux 43nsubj 4root 45xcomp 46punct |  all distance 1 to root refuse |  |
7 |  $\\{$why, does, my, snake, refuse, eat, ?$\\}$ |  why & does & my & snake & refuse & eat & ? |
51advmod 52aux 43nmod 54nsubj 5root 56xcomp 57punct |  snake is only word with distance 1 to my |  |
8 |  $\\{$why, does, my, snake, refuse, to, eat, ?$\\}$ |  why & does & my & snake & refuse & to & eat & ? |

& to is only word with distance 1 to eat

(b) Step by Step example. (c) DepProbe tree decoding example

###  F.1 DepProbe architecture

Müller-Eberstein et al. (2022) presented DepProbe, a lightweight decoder for
directed and labeled dependency trees. The model consists of two matrices, $L$
and $B$. Both transform $d_{h}$-dimensional word representations444For tokens
consisting of multiple subwords, the word representation is the mean of the
subword representations. into vectors that hightlights a syntactic property of
that representation. Assume that the LM representation of a word $w_{i}$ is
$h_{i}\in\mathbb{R}^{d_{h}}$, and that the annotation has $l$ dependency
relations.

##### Predicting dependency relations

The matrix $L\in\mathbb{R}^{d_{h}\times l}$ is a linear classifier that
predicts for each word the label of this word’s incoming dependency edge – the
relation between the word and its head. Concretely, the “probability of a
word’s relation $r_{i}$ being of class $l_{k}$ is given by:

$p(r_{i}=l_{k}|w_{i})=softmax(Lh_{i})_{k}$ (5)

” (Müller-Eberstein et al., 2022, p. 7713). This model component is trained
using cross-entropy loss.

##### Predicting word distances

The matrix $B\in\mathbb{R}^{d_{h}\times b}$ predicts the dependency edges
between words. $B$ projects the LM representations in a vector space that has
less dimensions than the LM layer ($b<d_{h}$). The target vector space is
informally called the syntactic subspace: It reflects structural information
such that vector distances between words mimic the distance between words in
the dependency tree. Concretely, when $h_{i},h_{j}$ are the LM representations
of words $w_{i},w_{j}$, their distance $d_{B}(h_{i},h_{j})$ in the syntactic
subspace is defined by Müller-Eberstein et al. (2022, Eq. 1):

$d_{B}(h_{i},h_{j})=\sqrt{(Bh_{i}-Bh_{j})^{T}(Bh_{i}-Bh_{j})}$ (6)

This model component is trained to predict the distance between all word pairs
in the dependency tree. Assume that the distance between two words in the
dependency tree is defined as the path length between the two words,
$d_{P}(w_{i},w_{j})$. If $s$ is a sentence of length $N+1$, the loss for
optimizing $B$ is given by Müller-Eberstein et al. (2022, Eq. 2):

$\mathcal{L}_{B}(s)=\frac{1}{N^{2}}\sum_{i=0}^{N}\sum_{j=0}^{N}|d_{P}(w_{i},w_{j})-d_{B}(h_{i},h_{j})|$
(7)

##### Constructing the dependency tree

The outputs of the relation and distance components are combined to construct
the dependency tree starting from the root. The word with the highest
probability of being the root (as assigned by $L$) is set as the dependency
tree root. Then, the words are iteratively added to the dependency tree,
always choosing the word with the smallest distance $d_{B}$ to a word that is
already covered. The dependency labels are assigned based on $L$. A detailed
example of this process is shown in App. F.2.

###  F.2 DepProbe Example

In Fig. F, we present a step-by-step example for for reconstructing trees with
DepProbe, following Alg. 1 in Müller-Eberstein et al. (2022). For simplicity,
the correct distance matrix (Fig. 7(a)) and correct relations are taken as
input to the algorithm.

###  F.3 Baselines

##### mBERT embedding layer ($M_{0}$)

In this baseline, we use the output of mBERT’s embedding layer as input to
DepProbe. $M_{0}$ estimates how much information about the probing task is
contained in the (context-insensitive) token embeddings.

##### Random mBERT ($M_{R}$)

We consider the representations of a transformer model with the same
architecture as mBERT, but all parameters are randomly initialized.
Performance of this baseline estimates how much information about dependency
structures is contained in the architecture of an MLM and the DepProbe
training.

##### Random contextualization mBERT ($M_{RC}$)

We consider a transformer model with the same architecture as mBERT, but all
parameters except the embedding layer are randomly initialized. The
performance of this baseline estimates how much information about dependency
structures from linguistic context is acquired during pretraining of the MLM
Belinkov (2022). We take the representations from layers 6 (7) as input to
DepProbe’s distance (relation) component.

##### Results

All probed models outperform the baselines by a large margin, both on original
and nonce data (Tables 12, 13, 14). This shows that the probing task probes
for contextual information (comparison to $M_{0}$), and that the probed
information is learnt during pretraining (comparison to $M_{R}$ and $M_{RC}$).
$M_{0}$, the embedding layer baseline, shows decent performance on the
relation labeling task (Tab. 12): Up to 74.6 RelAcc for German, and $\Delta<5$
for all languages. For attachment, the absolute scores are lower and the
performance drop is larger. This is intuitive: The embedding layer provides a
basis for predicting context-insensitive information such as the most frequent
dependency relation of a word type, and this information is still useful for
predicting the dependency relations in SPUD data. However, predicting
attachment requires more contextual information, for SPUD data even more so
than for original data. The absolute performance and $\Delta$ of $M_{RC}$ is
within 1 point to $M_{0}$ for all languages (Tab. 13). This shows that the
random contextualization does not detriment the predictability of relation
labeling based on the embedding layer. Attachment performance is lower in
terms of absolute scores for $M_{RC}$ than for $M_{0}$, which leads to less
room for a performance drop but overall lower LAS on both test sets. On
relation labeling, $M_{RC}$ performs between 4.8 and 12.6 accuracy points
better than $M_{R}$ on original data. On attachment, $M_{R}$ performs better
than $M_{RC}$ for all languages except Arabic. All baseline performance drops
for nonce data are relatively small. The most intuitive explanation for this
is that on the one hand, lower overall performance leaves less room for a
performance drop, and on the other hand it confirms that nonce data is created
in a way in which only the co-occurence information is changed, but not the
syntactic contexts in which the words generally appear (e.g. the tendency of a
word to appear as a subject is preserved).

| RelAcc | UAS | LAS
---|---|---|---
| orig | $\Delta$ | orig | $\Delta$ | orig | $\Delta$
ar | 66.1 | 4.7 | 43.3 | 5.8 | 29.9 | 5.9
de | 74.6 | 2.8 | 49.7 | 5.5 | 40.8 | 6.1
en | 65.4 | 1.6 | 45.6 | 3.5 | 33.7 | 3.2
fr | 70.6 | 2.1 | 48.2 | 3.0 | 36.9 | 3.2
ru | 71.3 | 2.0 | 46.6 | 3.3 | 35.3 | 3.3
Table 12: $M_{0}$. Embedding layer of mBERT | RelAcc | UAS | LAS
---|---|---|---
| orig | $\Delta$ | orig | $\Delta$ | orig | $\Delta$
ar | 65.4 | 4.7 | 31.0 | 4.1 | 21.9 | 4.1
de | 75.2 | 3.2 | 46.4 | 5.3 | 38.7 | 6.1
en | 66.4 | 1.7 | 41.9 | 3.0 | 32.0 | 2.9
fr | 70.9 | 2.5 | 40.6 | 2.3 | 31.7 | 2.4
ru | 71.0 | 2.0 | 42.0 | 2.7 | 32.4 | 2.8
Table 13: $M_{RC}$. Mid layers of mBERT architecture with trained embedding matrix and random transformer layers | RelAcc | UAS | LAS
---|---|---|---
| orig | $\Delta$ | orig | $\Delta$ | orig | $\Delta$
ar | 60.6 | 2.6 | 38.9 | 3.1 | 25.6 | 2.6
de | 64.6 | 6.0 | 39.6 | 5.2 | 29.5 | 6.2
en | 58.4 | 3.0 | 37.8 | 2.9 | 25.7 | 3.3
fr | 63.7 | 2.1 | 39.8 | 3.1 | 27.3 | 2.3
ru | 58.4 | 2.0 | 36.1 | 2.3 | 22.9 | 2.0
Table 14: $M_{R}$. Mid layers of mBERT architecture with completely random parameters | orig. | SPUD |  $\Delta$ mean
---|---|---|---
ar | 84.6 $\pm$ 0.13 | 78.9 $\pm$ 0.13 | 5.7
de | 92.5 $\pm$ 0.04 | 90.8 $\pm$ 0.05 | 1.7
en | 86.5 $\pm$ 0.10 | 84.8 $\pm$ 0.10 | 1.7
fr | 89.9 $\pm$ 0.13 | 87.9 $\pm$ 0.25 | 2.0
ru | 88.8 $\pm$ 0.00 | 87.3 $\pm$ 0.04 | 1.5
Table 15: Mean and standard deviation RelAcc of probing with different random seeds. | orig | nonce |  $\Delta$ mean
---|---|---|---
ar | 63.5 $\pm$ 0.18 | 56.0 $\pm$ 0.18 | 7.5
de | 83.3 $\pm$ 0.08 | 80.0 $\pm$ 0.09 | 3.3
en | 73.0 $\pm$ 0.31 | 69.3 $\pm$ 0.35 | 3.6
fr | 75.5 $\pm$ 0.17 | 71.3 $\pm$ 0.33 | 4.2
ru | 74.8 $\pm$ 0.02 | 71.6 $\pm$ 0.15 | 3.2
Table 16: Mean and standard deviation UAS of probing with different random seeds. | orig. | nonce |  $\Delta$ means
---|---|---|---
ar | 56.9 $\pm$ 0.13 | 48.0 $\pm$ 0.17 | 8.9
de | 79.5 $\pm$ 0.06 | 75.6 $\pm$ 0.07 | 4.0
en | 67.3 $\pm$ 0.29 | 63.6 $\pm$ 0.31 | 3.8
fr | 70.8 $\pm$ 0.18 | 66.5 $\pm$ 0.32 | 4.3
ru | 69.3 $\pm$ 0.01 | 66.2 $\pm$ 0.17 | 3.2
Table 17: Mean and standard deviation LAS of probing with different random
seeds.

###  F.4 Random seeds

The experimental setup introduced two random components: The probe’s initial
weights are randomly initialized, and the nonce data is created by randomly
sampling words. To test the effect of these random components, we additionally
run experiments with varying random seeds for each of these components in a
pilot study. Per language, we initialize probes with 3 different random seeds,
and each of these probes is evaluated on 5 different SPUD datasets. This means
that per language, 3 predictions for original data and 15 predictions for
nonce data are available. For all 3 evaluation metrics, the resulting scores
across predictions are stable. Concretely, the largest observed standard
deviation across predictions was 0.35 points UAS for English SPUD data. Most
of the other settings show much lower standard deviations. We argue that these
random components do not have a large effect on the results, and that it is
therefore sufficient to run the above probing experiments as described.

###  F.5 Ignoring dependency relations in nonce data creation

To compare our approach against the common nonce data creation practice of
using POS tags, we test on a version of English and German nonce data that
ignores dependency-specific information and only modifies the data based on
POS tags and language-specific rules. The results are shown in Table 18. The
performance difference between the two versions of nonce data is larger for
English than for German. This supports the fact that in English, dependency
information is more easily extracted from positional information than in
German: In the English data, the position of a word is a stronger cue for its
dependency relation than in German.

| RelAcc | UAS | LAS
---|---|---|---
| SPUD | POS | SPUD | POS | SPUD | POS
de | 91.0 | 90.1 | 81.0 | 79.7 | 76.2 | 75.0
en | 84.8 | 81.7 | 70.4 | 66.0 | 63.8 | 59.2

Table 18: Results for English and German test sets with (SPUD) and without
(only POS) dependency information in the nonce data creation.

###  F.6 Layer dymanics

We train DepProbe on English data on all layers of mBERT and mGPT. On the one
hand, this serves the purpose of selecting the layer used in all other
experiments. Müller-Eberstein et al. (2022) conducted the same experiment on
mBERT to identify the layer that performs best on the probing task. The best
layer for each task (6 for relation labeling, 7 for attachment) is then used
in all other experiments. We repeat this process on mGPT to identify the
highest performing layer for this model. In the case of mGPT, layer 12
performs best on both tasks. For selecting the best layer, we use the original
test data (following existing work).

On the other hand, the layerwise probing results highlight how syntactic and
semantic information influence probing performance across layers. For RelAcc,
mGPT’s performance on both test sets develops relatively stable, with a sharp
increase in the lowest layers and a slight decrease in the higher layers. The
$\Delta$ to the SPUD test set also increases during the lower layers and then
stays quite stable. For mBERT, the pattern is similar, with a steeper decline
in performance on the highest layer. For UAS (and LAS), mGPT shows smaller
changes across layers than for RelAcc. While the pattern appears jumpy, no
individual difference between consecutive layers is larger than 3.5 points and
the $\Delta$ to the SPUD test set is stable. mBERT shows a clearer but steeper
trend with best performance in the mid layers and worse performance in the
higher and lower layers.

Figure 7: Layerwise DepProbe performance for mBERT and mGPT.

###  F.7 Probe Performance by edge direction

| left | right
---|---|---
ar | 0.67 | 0.31
de | 0.32 | 0.63
en | 0.37 | 0.56
fr | 0.40 | 0.56
ru | 0.42 | 0.53
Table 19: Fraction of edges to the left and right in the respective UD test
sets. Both columns do not sum to 1 because the root is not counted.

|  | RelAcc | UAS | LAS
---|---|---|---|---
|  | l | r | l | r | l | r
mGPT, orig. | ar | 81.8 | 91.9 | 60.0 | 56.0 | 52.0 | 53.5
de | 88.3 | 94.5 | 77.0 | 86.7 | 71.1 | 82.9
en | 75.4 | 87.4 | 54.3 | 58.7 | 44.5 | 53.3
fr | 81.1 | 92.1 | 66.5 | 70.5 | 58.2 | 66.4
ru | 84.9 | 91.5 | 71.7 | 77.0 | 64.1 | 71.8
mGPT, $\Delta$ | ar | 10.3 | 2.3 | 15.6 | 6.6 | 16.9 | 6.7
de | 5.8 | 2.5 | 9.3 | 5.9 | 10.9 | 7.0
en | 7.0 | 3.9 | 5.5 | 5.4 | 6.6 | 6.4
fr | 2.7 | 2.9 | 7.4 | 5.6 | 7.0 | 6.9
ru | 4.2 | 2.1 | 7.1 | 4.1 | 7.7 | 4.8
mBERT, orig. | ar | 77.8 | 92.7 | 63.1 | 60.9 | 52.7 | 58.8
de | 85.7 | 95.9 | 75.4 | 87.8 | 67.7 | 85.1
en | 75.4 | 94.5 | 65.8 | 78.0 | 52.6 | 75.3
fr | 79.3 | 96.2 | 69.6 | 79.3 | 58.6 | 77.2
ru | 81.4 | 93.3 | 70.5 | 77.7 | 60.3 | 74.0
mBERT, $\Delta$ | ar | 7.6 | 1.1 | 8.8 | 4.3 | 10.4 | 4.3
de | 2.6 | 1.2 | 4.3 | 3.1 | 5.1 | 3.7
en | 2.9 | 1.8 | 3.0 | 4.5 | 3.1 | 4.9
fr | 2.8 | 1.2 | 4.4 | 4.3 | 3.9 | 4.5
ru | 1.9 | 1.1 | 3.6 | 3.0 | 3.2 | 3.0

Table 20: Performance for edges to the left and right

To further elaborate on the differences between decoded trees from ALMs and
MLMs, we investigate the performance of DepProbe in our main experiment on
edges in different directions. For all languages, edges to the left are
defined as edges where the dependent has a lower index than the head (vice
versa for edges to the right). The relative frequency of edges to the left and
right is displayed in Tab. 19. For all Indo-European (IE) languages, the
majority of edges are to the right (left for Arabic). The results (Tab. 20)
show that for the IE languages, edges to the right show higher performance
than edges to the left. For ALMs, this is especially intuitive: The edges to
the right are the ones where both head and dependent are in the context of the
token on which the prediction is made. When considering only original data and
IE languages, the performance difference between ALMs and MLMs interestingly
shows that MLMs are better at predicting edges to the right, but not
necessarily better at predicting edges to the left. Arabic consitutes a
special case because the distribution of edges to the left and right is
swapped. For RelAcc and SPUD, edges to the left show lower performance than
edges to the right, following the pattern in the other languages. For
attachment, the more frequent edges to the left show higher performance than
edges to the right (but only in original data). The performance drop on nonce
data and RelAcc is larger for edges to the left in all languages and both
models. For attachment however, the pattern is more mixed. Since the
performance drop on nonce data is secondary to the overarching research
question of this particular experiment, we do not investigate this further.