# Multilingual Syntax-aware Language Modeling
through Dependency Tree Conversion

Shunsuke Kando1,2 Hiroshi Noji3,2 Yusuke Miyao1,2
1 The University of Tokyo
2 Artificial Intelligence Research Center, AIST
3 LeapMind Inc.
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

Incorporating stronger syntactic biases into neural language models (LMs) is a
long-standing goal, but research in this area often focuses on modeling
English text, where constituent treebanks are readily available. Extending
constituent tree-based LMs to the multilingual setting, where dependency
treebanks are more common, is possible via dependency-to-constituency
conversion methods. However, this raises the question of which tree formats
are best for learning the model, and for which languages. We investigate this
question by training recurrent neural network grammars (RNNGs) using various
conversion methods, and evaluating them empirically in a multilingual setting.
We examine the effect on LM performance across nine conversion methods and
five languages through seven types of syntactic tests. On average, the
performance of our best model represents a 19 % increase in accuracy over the
worst choice across all languages. Our best model shows the advantage over
sequential/overparameterized LMs, suggesting the positive effect of syntax
injection in a multilingual setting. Our experiments highlight the importance
of choosing the right tree formalism, and provide insights into making an
informed decision.

##  1 Introduction

The importance of language modeling in recent years has grown considerably, as
methods based on large pre-trained neural language models (LMs) have become
the state-of-the-art for many problems (Devlin et al., 2019; Radford et al.,
2019). However, these neural LMs are based on general architectures and
therefore do not explicitly model linguistic constraints, and have been shown
to capture only a subset of the syntactic representations typically found in
constituency treebanks (Warstadt et al., 2020). An alternative line of LM
research aims to explicitly model the parse tree in order to make the LM
syntax-aware. A representative example of this paradigm, reccurent neural
network grammar (RNNG, Dyer et al., 2016), is reported to perform better than
sequential LMs on tasks that require complex syntactic analysis (Kuncoro et
al., 2019; Hu et al., 2020; Noji and Oseki, 2021).

The aim of this paper is to extend LMs that inject syntax to the multilingual
setting. This attempt is important mainly in two ways. Firstly, English has
been dominant in researches on syntax-aware LM. While multilingual LMs have
received increasing attention in recent years, most of their approaches do not
explicitly model syntax, such as multilingual BERT (mBERT, Devlin et al.,
2019) or XLM-R (Conneau et al., 2020). Although these models have shown high
performance on some cross-lingual tasks (Conneau et al., 2018), they perform
poorly on a syntactic task (Mueller et al., 2020). Secondly, syntax-aware LMs
have interesting features other than their high syntactic ability. One example
is the validity of RNNG as a cognitive model under an English-based setting,
as demonstrated in Hale et al. (2018). Since human cognitive functions are
universal, while natural languages are diverse, it would be ideal to conduct
this experiment based on multiple languages.

The main obstacle for multilingual syntax-aware modeling is that it is unclear
how to inject syntactic information while training. A straightforward approach
is to make use of a multilingual treebank, such as Universal Dependencies (UD,
Nivre et al., 2016; Nivre et al., 2020), where trees are represented in a
dependency tree (DTree) formalism. Matthews et al. (2019) evaluated parsing
and language modeling performance on three typologically different languages,
using a generative dependency model. Unfortunately, they revealed that
dependency-based models are less suited to language modeling than comparable
constituency-based models, highlighting the apparent difficulty of extending
syntax-aware LMs to other languages using existing resources.

This paper revisits the issue of the difficulty of constructing multilingual
syntax-aware LMs, by exploring the performance of multilingual language
modeling using constituency-based models. Since our domain is a multilingual
setting, our focus turns to how dependency-to-constituency conversion
techniques result in different trees, and how these trees affect the model’s
performance. We obtain constituency treebanks from UD-formatted dependency
treebanks of five languages using nine tree conversion methods. These
treebanks are in turn used to train an RNNG, which we evaluate on perplexity
and CLAMS (Mueller et al., 2020).

Our contributions are: (1) We propose a methodology for training multilingual
syntax-aware LMs through the dependency tree conversion. (2) We found an
optimal structure that brings out the potential of RNNG across five languages.
(3) We demonstrated the advantage of our multilingual RNNG over
sequential/overparameterized LMs.

##  2 Background

###  2.1 Recurrent Neural Network Grammars

|  |  [.S [.NP [roof]; The pilot ] [.VP laughs ] ]
---
| Partial tree
---
Stack-LSTM
Action
0 |  | NT(S)
1 |  | (S
---
$[\mathbf{e}_{\rm S}]$
NT(NP)
2 |  | (S (NP
---
$[\mathbf{e}_{\rm S}\ \mathbf{e}_{\rm NP}]$
GEN(The)
3 |  | (S (NP The
---
$[\mathbf{e}_{\rm S}\ \mathbf{e}_{\rm NP}\ \mathbf{e}_{\rm The}]$
GEN(pilot)
4 |  | (S (NP The pilot
---
$[\mathbf{e}_{\rm S}\ \underline{\mathbf{e}_{\rm NP}\ \mathbf{e}_{\rm The}\
\mathbf{e}_{\rm pilot}}]$
REDUCE
5 |  | (S (NP The pilot)
---
$[\mathbf{e}_{\rm S}\ \underline{\mathbf{e}_{\rm NP^{\prime}}}]$
NT(VP)
6 |  | (S (NP The pilot) (VP
---
$[\mathbf{e}_{\rm S}\ \mathbf{e}_{\rm NP^{\prime}}\ \mathbf{e}_{\rm VP}]$
$\cdots$
Figure 1: The illustration of stack-RNNG behavior. Stack-LSTM represents the
current partial tree, in which adjacent vectors are connected in the network.
At REDUCE action, the corresponding vector is updated with composition
function (as underlined).

RNNGs are generative models that estimate joint probability of a sentence
$\boldsymbol{x}$ and a constituency tree (CTree) $\boldsymbol{y}$. The
probability $p(\boldsymbol{x},\boldsymbol{y})$ is estimated with top-down
constituency parsing actions $\boldsymbol{a}=(a_{1},a_{2},\cdots,a_{n})$ that
produce $\boldsymbol{y}$:

$p(\boldsymbol{x},\boldsymbol{y})=\prod_{t=1}^{n}p(a_{t}|a_{1},\cdots,a_{t-1})$

Kuncoro et al. (2017) proposed a stack-only RNNG that computes the next action
probability based on the current partial tree. Figure 1 illustrates the
behavior of it. The model represents the current partial tree with a stack-
LSTM, which consists of three types of embeddings: nonterminal, word, and
closed-nonterminal. The next action is estimated with the last hidden state of
a stack-LSTM. There are three types of actions as follows:

  * •

NT(X): Push nonterminal embedding of $X$ ($\mathbf{e}_{X}$) onto the stack.

  * •

GEN($w$): Push word embedding of $w$ ($\mathbf{e}_{w}$) onto the stack.

  * •

REDUCE: Pop elements from the stack until a nonterminal embedding shows up.
With all the embeddings which are popped, compute closed-nonterminal embedding
$\mathbf{e}_{X^{\prime}}$ using composition funcion Comp:

$\mathbf{e}_{X^{\prime}}=\textsc{Comp}(\mathbf{e}_{X},\mathbf{e}_{w_{1}},\cdots,\mathbf{e}_{w_{m}})$

RNNG can be regarded as a language model that injects syntactic knowledge
explicitly, and various appealing features have been reported (Kuncoro et al.,
2017; Kuncoro et al., 2017; Hale et al., 2018). We focus on its high
performance on _syntactic evaluation_ , which is described below.

#### Difficulty in extending to other languages

In principle, RNNG can be learned with any corpus as long as it contains CTree
annotation. However, it is not evident which tree formats are best in a
multilingual setting. Using the same technique as English can be inappropriate
because each language has its own characteristic, which can be different from
English. This question is the fundamental motivation of this research.

###  2.2 Cross-linguistic Syntactic Evaluation

To investigate the capability of LMs to capture syntax, previous work has
attempted to create an evaluation set that requires analysis of the sentence
structure (Linzen et al., 2016). One typical example is a subject-verb
agreement, a rule that the form of a verb is determined by the grammatical
category of the subject, such as person or number:

The pilot that the guards love laughs/*laugh. (1)

In (1), the form of _laugh_ is determined by the subject _pilot_ , not
_guards_. This judgment requires syntactic analysis; _guards_ is not a subject
of target verb _laugh_ because it is in the relative clause of the real
subject _pilot_.

Marvin and Linzen (2018) designed the English evaluation set using a
grammatical framework. Mueller et al. (2020) extended this framework to other
languages (French, German, Hebrew, and Russian) and created an evaluation set
named CLAMS (Cross-Linguistic Assessment of Models on Syntax). CLAMS covers 7
categories of agreement tasks, including local agreement (e.g. The author
laughs/*laugh) and non-local agreement that contains an intervening phrase
between subject and verb as in (1). They evaluated LMs on CLAMS and
demonstrated that sequential LMs often fail to assign a higher probability to
the grammatical sentence in cases that involve non-local dependency.

Previous work has attempted to explore the syntactic capabilities of LMs with
these evaluation sets. Kuncoro et al. (2019) compared the performance of LSTM
LM and RNNG using the evaluation set proposed in Marvin and Linzen (2018),
demonstrating the superiority of RNNG in predicting the agreement. Noji and
Takamura (2020) suggested that LSTM LMs potentially have a limitation in
handling object relative clauses. Since these analyses are performed on the
basis of English text, it is unclear whether they hold or not in a
multilingual setting. In this paper, we attempt to investigate this point by
learning RNNGs in other languages and evaluating them on CLAMS.

1 Function  _flat(_$w$ , $ldeps$, $rdeps$_)_:

2 lNT $\leftarrow$ [flat(_$lw$ , $lw$.ldeps, $lw$.rdeps_) for $lw$ in
$ldeps$];

3 rNT $\leftarrow$ [flat(_$rw$ , $rw$.ldeps, $rw$.rdeps_) for $rw$ in
$rdeps$];

4 return [lNT [$w$] rNT].removeEmptyList ;

5

6

7Function  _lf(_$w$ , $ldeps$, $rdeps$_)_:

8 if  _$ldeps$ is not empty_ then

/* Pop left-most dependent */

9 $lw$ $\leftarrow$ $ldeps$.pop(__) ;

10 lNT $\leftarrow$ [lf(_$lw$ , $lw$.ldeps, $lw$.rdeps_)];

11 rNT $\leftarrow$ [lf(_$w$ , $ldeps$, $rdeps$_)];

12

13 else if  _$rdeps$ is not empty_ then

/* Pop right-most dependent */

14 $rw$ $\leftarrow$ $rdeps$.pop(__) ;

15 lNT $\leftarrow$ [lf(_$w$ , $ldeps$, $rdeps$_)];

16 rNT $\leftarrow$ [lf(_$rw$ , $rw$.ldeps, $rw$.rdeps_)];

17

18 else return [$w$];

19 return [lNT rNT];

20

21

Algorithm 1 lf is short for left-first conversion. We omit right-first
conversion because it can be defined just by swapping the codeblocks 6-9 and
10-13 of left-first conversion.

##  3 Method: Dependency Tree Conversion

As a source of multilingual syntactic information, we use Universal
Dependencies (UD), a collection of cross-linguistic dependency treebanks with
a consistent annotation scheme. Since RNNG requires a CTree-formatted dataset
for training, we perform DTree-to-CTree conversions, which are completely
algorithmic to make it work regardless of language. Our method consists of two
procedures: structural conversion and nonterminal labeling; obtaining a CTree
skeleton with unlabeled nonterminal nodes, then assigning labels by leveraging
syntactic information contained in the dependency annotations. While our
structural conversion is identical to the baseline approach of Collins et al.
(1999), we include a novel labeling method that relies on dependency
relations, not POS tags.

[column sep=3ex] The & man & give & him & a & box
---
DET & NOUN & VERB & PRON & DET & NOUN |  |
[edge unit distance=2.2ex]3root 21det 32nsubj 34iobj [edge unit distance=1.8ex]36obj 65det |  |
$\Swarrow$ | $\Downarrow$ | $\Searrow$
[.NTgive [.NTman [.NTThe The ] [.NTman man ] ] [.NTgive give ] [.NThim him ] [.NTbox [.NTa a ] [.NTbox box ] ] ] |  [.NTgive [.NTman [.NTThe The ] [.NTman man ] ] [.NTgive [.NTgive [.NTgive give ] [.NThim him ] ] [.NTbox [.NTa a ] [.NTbox box ] ] ] ] |  [.NTgive [.NTgive [.NTgive [.NTman [.NTThe The ] [.NTman man ] ] [.NTgive give ] ] [.NThim him ] ] [.NTbox [.NTa a ] [.NTbox box ] ] ]
(a) flat | (b) left-first | (c) right-first

Figure 2: The illustration of structural conversion. NTw is a temporal label
of nonterminal which will be assigned at nonterminal labeling phase.

#### Structural conversion

We performed three types of structural conversion: _flat_ , _left-first_ , and
_right-first_. Algorithm 1 shows the pseudo code and Figure 3 illustrates the
actual conversions. These approaches construct CTree in a top-down manner
following this procedure: 1) Introduce the root nonterminal of the head of a
sentence (NTgive). 2) For each NTw, introduce new nonterminals according to
the dependent(s) of $w$. Repeat this procedure recursively until $w$ has no
dependents.

The difference between the three approaches is the ordering of introducing
nonterminals. We describe their behaviors based on the example in Figure 3.
(a) flat approach lets $w$ and its dependents be children in CTree
simultaneously. For example, NTgive has four children: NTman, NTgive, NThim,
NTbox, because they are dependents of the head word _give_. As the name
suggests, this approach tends to produce a flat-structured CTree because each
nonterminal can have multiple children. (b) left-first approach introduces the
nonterminals from the left-most dependent. If there is no left dependent, the
right-most dependent is introduced. In the example of Figure 3, the root
NTgive has a left child NTman because _man_ is the left-most dependent of the
head _give_. (c) right-first approach is the inversed version of left-first;
handling the right-most dependent first. For methods (b) and (c), the
resulting CTree is always a binary tree.

| X-label | POS-label | DEP-label
---|---|---|---
NTThe | X | DETP | det
NTman | X | NOUNP | nsubj
NTgive | X | VERBP | root
NThim | X | PRONP | iobj
NTa | X | DETP | det
NTbox | X | NOUNP | obj
Table 1: Actual labels assigned to nonterminals.

#### Nonterminal labeling

We define three types of labeling methods for each NTw; 1) X-label: Assign “X”
to all the nonterminals. 2)POS-label: Assign POS tag of $w$. 3) DEP-label:
Assign dependency relation between $w$ and its head. Table 1 shows the actual
labels that are assigned to CTrees in Figure 3.

flat | left-first | right-first
---|---|---
[.NT [.NTpilot [.NT The ] [.NT pilot ] [.NT [.NT that ] [.NT [roof]; the guards ] [.NT love ] ] ] [.NT laughs |  |
/ *laugh ] ] |  [.NT [.NTpilot [.NT The ] [.NT [.NT pilot ] [.NT [.NT that ] [.NT [.NT [roof]; the guards ] [.NT love ] ] ] ] ] [.NT laughs |
/ *laugh ] ] |  [.NT [.NTpilot [.NT [.NT The ] [.NT pilot ] ] [.NT [.NT that ] [.NT [.NT [roof]; the guards ] [.NT love ] ] ] ] [.NT laughs |
/ *laugh ] ] |  |
Figure 3: Examples of converted CTrees. A sentence is taken from CLAMS, which
requires recognition of long distance dependency intervened by object relative
clause (sentence (1)). For simplicity, we omit the corresponding word of each
nonterminal except for _pilot_ , the main subject of the sentence.

Each method has its own intent. X-label drops the syntactic category of each
phrase, which minimizes the structural information of the sentence. POS-label
would produce the most common CTree structure because traditionally
nonterminals are labeled based on POS tag of the head word. DEP-label is a
more fine-grained method than POS-label because words in a sentence can have
the same POS tag but different dependency relation, as in _man_ and _box_ in
Figure 3.

Finally, we performed a total of nine types of conversions (three structures
$\times$ three labelings). Although they have discrete features, they are
common in that they embody reasonable phrase structures that are useful for
capturing syntax. Figure 3 shows the converted structure of an actual instance
from CLAMS. In all settings, the main subject phrase is correctly dominated by
NTpilot, which should contribute to solving the task.

##  4 What Is the Robust Conversion Which Works Well in Every Language?

In Section 3, we proposed language-independent multiple conversions from DTree
to CTree. The intriguing question is; Is there a robust conversion that brings
out the potential of RNNG in every language? To answer this question, we
conducted a thorough experiment to compare the performances of RNNGs trained
in each setting.

###  4.1 Experimental Setup

#### Treebank preparation

Following Mueller et al. (2020), we extracted Wikipedia articles of target
languages using WikiExtractor111https://github.com/attardi/wikiextractor to
create corpora222Although Mueller et al. (2020) publishes corpora they used,
we extracted the dataset ourselves because they contain <unk> token which
would affect parsing.. We fed it to UDify (Kondratyuk and Straka, 2019), a
multilingual neural dependency parser trained on the entire UD treebanks, to
generate a CoNLL-U formatted dependency treebank. Sentences are tokenized
beforehand using Stanza (Qi et al., 2020) because UDify requires tokenized
text for prediction. The resulting dependency treebank is converted into the
constituency treebank using methods proposed in Section 3. Our treebank
contains around 10% non-projective DTrees for all the language (between 9% in
Russian and 14% in Hebrew), and we omit them in the conversion phase because
we cannot obtain valid CTrees from them333Since other language can contain
more non-projective DTrees, we have to consider how to handle it in the
future.. As a training set, we picked sentences with 10M tokens at random for
each language. For a validation and a test set, we picked 5,000 sentences
respectively.

#### Training details

We used batched RNNG (Noji and Oseki, 2021) to speed up our training.
Following Noji and Oseki (2021), we used subword units (Sennrich et al., 2016)
with a vocabulary size of 30K. We set the hyperparameters so as to make the
model size 35M. We trained each model for 24 hours on a single GPU.

#### Evaluation metrics

To compare the performance among conversions, we evaluated the model trained
on each dataset in two aspects: perplexity and syntactic ability based on
CLAMS.

Perplexity is a standard metric for assessing the quality of LM. Since we
adopt subword units, we regard a word probability as a product of its
subwords’ probabilities. To compute it on RNNG, we performed word-synchronous
beam search (Stern et al., 2017), a default approach implemented in batched
RNNG. Following Noji and Oseki (2021), we set a beam size $k$ as 100, a word
beam size $k_{w}$ as 10, and fast-track candidates $k_{s}$ as 1. Syntactic
ability is assessed by accuracy on CLAMS, which is calculated by comparing the
probabilities assigned to a grammatical and an ungrammatical sentence. If the
model assigns a higher probability to a grammatical sentence, then we regard
it as correct. Chance accuracy is 0.5.

We run the experiment three times with different random seeds for
initialization of the model, and report the average score with standard
deviation.

Figure 4: Accuracies of CLAMS for RNNGs trained on each setting.

###  4.2 Result

From now on, we refer to each conversion method according to a naming of the
procedure, such as “left-first structure” or “flat-POS conversion”.

| flat | left | right |
---|---|---|---|---
X | 259±1 | 707±19 | 1507±14 | English
POS | 278±3 | 417±2 | 512±3
DEP | 241±30 | 390±4 | 463±1
X | 133±0 | 405±10 | 691±10 | French
POS | 129±1 | 206±2 | 262±1
DEP | 137±22 | 190±5 | 223±2
X | 341±1 | 830±8 | 1124±18 | German
POS | 366±1 | 321±3 | 482±2
DEP | 330±43 | 291±3 | 398±4
X | 100±1 | 294±3 | 450±8 | Hebrew
POS | 97±0 | 153±1 | 183±1
DEP | 93±1 | 143±1 | 161±1
X | 508±5 | 1413±16 | 1910±59 | Russian
POS | 527±3 | 845±2 | 1067±16
DEP | 473±61 | 834±5 | 1030±27
Table 2: Test set perplexity of each setting. Lower is better. “left” and “right” in the table are abbreviations of “left-first” and “right-first”, respectively. | flat | left | right |
---|---|---|---|---
X | 0.89±.01 | 0.68±.01 | 0.75±.01 | English
POS | 0.87±.02 | 0.89±.01 |  _0.67_ ±.01
DEP | 0.90±.02 | 0.84±.01 | 0.78±.04
X | 0.99±.00 |  _0.75_ ±.00 | 0.88±.02 | French
POS | 0.99±.00 | 0.93±.02 | 0.92±.01
DEP | 0.98±.01 | 0.96±.01 | 0.94±.01
X | 0.95±.00 |  _0.78_ ±.01 | 0.86±.01 | German
POS | 0.95±.01 | 0.93±.01 | 0.88±.01
DEP | 0.96±.01 | 0.95±.02 | 0.87±.02
X | 0.91±.01 |  _0.72_ ±.01 | 0.78±.01 | Hebrew
POS | 0.91±.01 | 0.91±.03 | 0.87±.01
DEP | 0.90±.01 | 0.92±.00 | 0.86±.01
X | 0.93±.00 | 0.84±.01 | 0.89±.02 | Russian
POS | 0.90±.01 | 0.87±.01 | 0.83±.01
DEP | 0.93±.01 | 0.89±.00 |  _0.82_ ±.01
Table 3: CLAMS scores averaged by task category.

#### Perplexity

Table 2 shows the perplexities in each setting. As a whole, flat structures
show the lowest perplexity, followed by left-first and right-first, which is
consistent across languages. While flat structure produces stable and
relatively low perplexity regardless of labeling methods and languages, left-
first and right-first structures perform very poorly on X-label.

#### Syntactic ability

Figure 4 shows the accuracies of CLAMS in each setting, and Table 3 shows the
average scores. From Table 3, we observe clear distinctions across methods;
the best model (shown in bold) is 19% more accurate in average than the worst
one (shown in italic), across all languages, indicating the model’s certain
preference for the structure. Similar to perplexity, flat structure performs
better and more stably than the others, regardless of labels and languages.
While Mueller et al. (2020) reported a high variability in scores across
languages when an LSTM LM is used, flat structure-based RNNGs do not show such
a tendency; almost all the accuracies are above 90%.

Looking closely at the Figure 4, we can see that left-first and right-first
structures exhibit unstable behavior depending on the labeling; the accuracy
on X-label tends to be lower especially for the categories that require the
resolution of a long-distance dependency, such as ‘VP coord (long)’, ‘Across
subj. rel.’, ‘Across obj. rel.’, and ‘Across prep’.

#### Discussion

Basically, we observed a similar tendency in perplexity and CLAMS score; (1)
flat structures show the highest scores. (2) left-first and right-first
structures perform poorly on X-label. We conjecture that these tendencies are
due to the resulting structure of each conversion; while flat structure is
non-binary, the rest two are binary. Since nonterminals in a non-binary tree
can have multiple words as children, parsing actions obtained from it contain
more continuous GEN actions than a binary tree. This nature helps the model to
predict the next word by considering lexical relations, which would contribute
to its lower perplexity. Although binary trees get better with the hint of
informative labels (POS/DEP), it is difficult to reach the performance of flat
structures due to their confused actions; GEN actions tend to be interrupted
by other actions. Besides, there are too many NT actions in a binary tree,
which can hurt the prediction because the information of an important
nonterminal (e.g. NTpilot in Figure 3) can be diluted through the actions. The
situation becomes worse on X-label; the model cannot distinguish the
nonterminal of the main subject and that of the other, resulting in missing
what the subject is.

It is worth noting that perplexity does not always reflect the CLAMS accuracy.
For example, while right-X conversion produces the worst perplexity for all
the languages, it achieves better CLAMS accuracy than left-X conversion for
almost all the cases. This observation is in line with Hu et al. (2020), who
report a dissociation between perplexity and syntactic performance for
English.

| flat | left | right |
---|---|---|---|---
X | 0.80±.00 | 0.34±.00 | 0.48±.00 | English
POS | 0.79±.00 | 0.57±.00 | 0.70±.00
DEP | 0.82±.01 | 0.59±.01 | 0.70±.00
X | 0.79±.00 | 0.37±.00 | 0.58±.00 | French
POS | 0.86±.00 | 0.63±.00 | 0.74±.00
DEP | 0.86±.01 | 0.65±.01 | 0.75±.00
X | 0.90±.00 | 0.44±.00 | 0.59±.00 | German
POS | 0.85±.00 | 0.74±.00 | 0.76±.00
DEP | 0.91±.08 | 0.76±.00 | 0.77±.00
X | 0.81±.01 | 0.41±.00 | 0.58±.00 | Hebrew
POS | 0.83±.00 | 0.65±.00 | 0.73±.00
DEP | 0.83±.00 | 0.65±.00 | 0.72±.00
X | 0.80±.00 | 0.41±.00 | 0.59±.00 | Russian
POS | 0.83±.00 | 0.62±.00 | 0.73±.00
DEP | 0.82±.01 | 0.58±.00 | 0.68±.00
Table 4: F1 score of predicted CTree. We regard a resulting CTree of each
conversion as a gold tree. Figure 5: Structures of a CLAMS example predicted
by {flat, left-first, right-first}-POS RNNG. This example is solvable only by
flat-POS RNNG across all seeds.

###  4.3 Why Does Flat Structure Perform Well?

As one possible reason why flat structure is optimal among the three
structures presented, we conjecture that the parseability of the structure is
involved. To test this hypothesis, we calculated the F1 score between the gold
CTrees of the test set and the structures predicted by RNNG for each setting.
Table 4 shows the result. The tendencies of F1 scores are consistent across
languages: 1) Flat structures show highest F1 score. 2) While scores of flat
structures are stable regardless of their labelings, the rest two structures
exhibit lower score on X-label. As a whole, the result reflects the tendency
discussed in Section 4.2, which supports our hypothesis.

To further investigate the link between parseability and the capability of
solving the task, we obtained parse trees of CLAMS examples that are solvable
only by flat RNNG across all seeds. We found that only flat RNNG produces a
correct constituency tree, and structures obtained from left-first and right-
first RNNGs are incorrect on a critical point. For example, in Figure 5, while
the relation between the subject “author” and the target verb “laughs” is
analyzed clearly in the flat structure, it is ambiguous in the rest, possibly
causing the misinterpretation that the subject is “guards”.

These findings indicate the importance of choosing the correct tree structure
for syntax-aware language modeling; it should be not only hierarchical, but
also as parseable as possible.

Through analysis of the conversions, we found that (1) flat structure performs
stably well in every setting. (2) while CLAMS accuracy of flat structure does
not differ significantly depending on its labeling, for perplexity, flat-DEP
performs the best for more than half of the languages and no inferiority can
be observed for the other languages. Therefore, we conclude that _flat-DEP_
conversion is the most robust conversion among languages.

##  5 Advantage of Syntax Injection to LMs in a Multilingual Setting

In this section, we demonstrate the benefits of injecting syntactic biases
into the model in a multilingual setting. We obtained the CLAMS score of RNNG
trained on the flat-DEP treebank (_flat-DEP RNNG_ for short) and compared it
against baselines.

|  Simple |  VP coord (short) |  VP coord (long) |  Across subj. rel. |  Within obj rel. |  Across obj rel. |  Across prep. |  Average |
---|---|---|---|---|---|---|---|---|---
flat-DEP RNNG |  0.99±.01 |  0.87±.02 |  0.91±.04 |  0.95±.02 |  0.92±.05 |  0.92±.06 |  0.93±.04 |  0.93±.02 | English
LSTM (N20) |  0.93±.03 |  0.85±.01 |  0.83±.04 |  0.85±.04 |  0.83±.05 |  0.77±.04 |  0.87±.02 |  0.85±.02
LSTM (M20) |  1.00±.00 |  0.94±.01 |  0.76±.06 |  0.60±.06 |  0.89±.01 |  0.55±.05 |  0.63±.02 |  0.77±.03
mBERT (M20) |  1.00 |  1.00 |  0.92 |  0.88 |  0.83 |  0.87 |  0.92 |  0.92
flat-DEP RNNG |  1.00±.00 |  1.00±.00 |  1.00±.00 |  1.00±.00 |  1.00±.00 |  1.00±.00 |  1.00±.00 |  1.00±.00 | French
LSTM (N20) |  1.00±.00 |  1.00±.00 |  0.97±.03 |  0.92±.06 |  0.85±.03 |  0.75±.01 |  1.00±.00 |  0.93±.01
LSTM (M20) |  1.00±.00 |  0.97±.01 |  0.85±.05 |  0.71±.05 |  0.99±.01 |  0.52±.01 |  0.74±.02 |  0.83±.02
mBERT (M20) |  1.00 |  1.00 |  0.98 |  0.57 |  — |  0.86 |  0.57 |  0.83
flat-DEP RNNG |  1.00±.00 |  0.99±.01 |  0.98±.01 |  1.00±.00 |  0.88±.04 |  0.99±.01 |  0.97±.02 |  0.97±.01 | German
LSTM (N20) |  0.99±.01 |  0.97±.03 |  0.92±.05 |  0.99±.01 |  0.72±.01 |  0.97±.02 |  0.94±.01 |  0.93±.01
LSTM (M20) |  1.00±.00 |  0.99±.02 |  0.96±.04 |  0.94±.04 |  0.74±.03 |  0.81±.09 |  0.89±.06 |  0.90±.04
mBERT (M20) |  0.95 |  0.97 |  1.00 |  0.73 |  — |  0.93 |  0.95 |  0.92
flat-DEP RNNG |  0.97±.01 |  0.99±.00 |  0.92±.03 |  0.95±.02 |  1.00±.00 |  0.84±.05 |  0.95±.01 |  0.95±.01 | Hebrew
LSTM (N20) |  0.97±.00 |  0.95±.04 |  0.85±.02 |  0.89±.02 |  0.94±.01 |  0.63±.04 |  0.93±.01 |  0.88±.00
LSTM (M20) |  0.95±.01 |  1.00±.01 |  0.84±.06 |  0.91±.03 |  1.00±.01 |  0.56±.01 |  0.88±.03 |  0.88±.02
mBERT (M20) |  0.70 |  0.91 |  0.73 |  0.61 |  — |  0.55 |  0.62 |  0.69
flat-DEP RNNG |  0.89±.02 |  0.94±.02 |  1.00±.00 |  0.93±.00 |  0.99±.01 |  0.92±.02 |  0.85±.03 |  0.93±.01 | Russian
LSTM (N20) |  0.91±.01 |  0.97±.00 |  0.97±.02 |  0.98±.00 |  0.90±.04 |  0.85±.07 |  0.86±.02 |  0.92±.01
LSTM (M20) |  0.91±.01 |  0.98±.02 |  0.86±.04 |  0.88±.03 |  0.95±.04 |  0.60±.03 |  0.76±.02 |  0.85±.03
mBERT (M20) |  0.65 |  0.80 |  — |  0.70 |  — |  0.67 |  0.56 |  0.68
Table 5: CLAMS scores for flat-DEP RNNG and baselines. LSTM (N20) is a model
of which hyperparameters are set as with Noji and Takamura (2020). LSTM (M20)
and mBERT (M20) scores are quoted from Table 1, 2 and 5 in Mueller et al.
(2020). Hyphen means that all focus verb for the corresponding setting were
out-of-vocabulary.

#### Experimental setup

The experiment was conducted in as close setting to the previous work as
possible. Following Mueller et al. (2020), we extracted Wikipedia articles of
80M tokens as training set. The hyperparameters of LSTM LM are set following
Noji and Takamura (2020) because it performs the best for the dataset of
Marvin and Linzen (2018)444Since English set of CLAMS is a subset of Marvin
and Linzen (2018), it is reasonable to choose this model to validate the
multilingual extendability.. We used subword units with a vocabulary size of
30K, and the sizes of RNNG and LSTM LM are set to be the same (35M).

#### Result

Table 5 shows the result. In addition to scores from the models we trained
(flat-DEP RNNG, LSTM (N20)), we display scores of LSTM LM and mBERT reported
in the original paper (LSTM (M20) and mBERT (M20), Mueller et al., 2020).
Overall, we can see the superiority of RNNG across languages, especially for
the tasks that require analysis on long distance dependency; ‘VP coord
(long)’, ‘Across subj. rel.’, ‘Across obj. rel.’, and ‘Across prep’. While
previous work suggested that LSTM LMs potentially have a limitation in
handling object relative clauses (Noji and Takamura, 2020), our result
suggests that RNNG does not have such a limitation thanks to explicitly
injected syntactic biases.

##  6 Discussion

We discussed the CTree structure that works robustly regardless of the
language and the superiority of injecting syntactic bias to the model. Our
claim is that we can construct language-independent syntax-aware LMs by
seeking the best structure for learning RNNGs, which is backed up by our
experiments based on five languages. To make this claim firm, more
investigations are needed from two aspects: fine-grained syntactic evaluation
and experiment on typologically diverse languages.

#### Fine-grained syntactic evaluation

The linguistic phenomenon covered in CLAMS is only an agreement. However,
previous works have invented evaluation sets that examine more diverse
syntactic phenomena for English (Hu et al., 2020, Warstadt et al., 2020). We
need such a fine-grained evaluation even in a multilingual setting, as
superiority in agreement does not imply superiority in every syntactic
knowledge; Kuncoro et al. (2019) suggested that RNNG performs poorer than LSTM
LM in capturing sentential complement or simple negative polarity items. It is
challenging to design a multiliugnal syntactic test set because even an
agreement based on grammatical categories is not a universal phenomenon. It is
required to seek reasonable metrics that cover broad syntactic phenomena and
are applicable to many languages.

#### Experiment on typologically diverse languages

Languages included in CLAMS (English, French, German, Hebrew and Russian) are
actually not typologically diverse. Apart from language-specific features, all
of them take the same ordering of (1) subject, verb, and object (SVO) (2)
relative clause and noun (Noun-Relative clause) (3) adposition and noun phrase
(preposition), and so on555Typological information is obtained from WALS:
https://wals.info/. If we run the same experiment for a typologically
different language, the result could be somewhat different. Although some
previous work focused on syntactic assessment of other languages (Ravfogel et
al., 2018; Gulordava et al., 2018), such attempts are scarce. As future work,
it is needed to design an evaluation set based on other languages and explore
the extendability to more diverse languages.

##  7 Conclusion

In this paper, we propose a methodology to learn multilingual RNNG through
dependency tree conversion. We performed multiple conversions to seek the
robust structure which works well multilingually, discussing the effect of
multiple structures. We demonstrated the superiority of our model over
baselines in capturing syntax in a multilingual setting. Since our research is
the first step for multilingual syntax-aware LMs, it is necessary to conduct
experiments on more diverse languages to seek a better structure. We believe
that this research would contribute to the field of theoretical/cognitive
linguistics as well because an ultimate goal of linguistics is finding the
universal rule of natural language. Finding a reasonable structure in
engineering would yield useful knowledge for that purpose.

## Acknowledgements

This paper is based on results obtained from a project JPNP20006, commissioned
by the New Energy and Industrial Technology Development Organization (NEDO).
For experiments, computational resource of AI Bridging Cloud Infrastructure
(ABCI) provided by National Institute of Advanced Industrial Science and
Technology (AIST) was used.

## References

  * Collins et al. (1999) Michael Collins, Jan Hajic, Lance Ramshaw, and Christoph Tillmann. 1999.  A statistical parser for Czech.  In _Proceedings of the 37th Annual Meeting of the Association for Computational Linguistics_ , pages 505–512, College Park, Maryland, USA. Association for Computational Linguistics.
  * Conneau et al. (2020) Alexis Conneau, Kartikay Khandelwal, Naman Goyal, Vishrav Chaudhary, Guillaume Wenzek, Francisco Guzmán, Edouard Grave, Myle Ott, Luke Zettlemoyer, and Veselin Stoyanov. 2020.  Unsupervised cross-lingual representation learning at scale.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 8440–8451, Online. Association for Computational Linguistics.
  * Conneau et al. (2018) Alexis Conneau, Ruty Rinott, Guillaume Lample, Adina Williams, Samuel Bowman, Holger Schwenk, and Veselin Stoyanov. 2018.  XNLI: Evaluating cross-lingual sentence representations.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 2475–2485, Brussels, Belgium. Association for 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.
  * Dyer et al. (2016) Chris Dyer, Adhiguna Kuncoro, Miguel Ballesteros, and Noah A. Smith. 2016.  Recurrent neural network grammars.  In _Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 199–209, San Diego, California. Association for Computational Linguistics.
  * Gulordava et al. (2018) Kristina Gulordava, 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.
  * Hale et al. (2018) John Hale, Chris Dyer, Adhiguna Kuncoro, and Jonathan Brennan. 2018.  Finding syntax in human encephalography with beam search.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 2727–2736, Melbourne, Australia. Association for Computational Linguistics.
  * Hu et al. (2020) Jennifer Hu, Jon Gauthier, Peng Qian, Ethan Wilcox, and Roger Levy. 2020.  A systematic assessment of syntactic generalization in neural language models.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 1725–1744, Online. Association for Computational Linguistics.
  * Kondratyuk and Straka (2019) Dan Kondratyuk and Milan Straka. 2019.  75 languages, 1 model: Parsing Universal Dependencies universally.  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 2779–2795, Hong Kong, China. Association for Computational Linguistics.
  * Kuncoro et al. (2017) Adhiguna Kuncoro, Miguel Ballesteros, Lingpeng Kong, Chris Dyer, Graham Neubig, and Noah A. Smith. 2017.  What do recurrent neural network grammars learn about syntax? In _Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers_ , pages 1249–1258, Valencia, Spain. Association for Computational Linguistics.
  * Kuncoro et al. (2019) Adhiguna Kuncoro, Chris Dyer, Laura Rimell, Stephen Clark, and Phil Blunsom. 2019\.  Scalable syntax-aware language models using knowledge distillation.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 3472–3484, Florence, Italy. Association for Computational Linguistics.
  * Linzen et al. (2016) Tal Linzen, Emmanuel Dupoux, and Yoav Goldberg. 2016.  Assessing the ability of LSTMs to learn syntax-sensitive dependencies.  _Transactions of the Association for Computational Linguistics_ , 4:521–535.
  * 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.
  * Matthews et al. (2019) Austin Matthews, Graham Neubig, and Chris Dyer. 2019.  Comparing top-down and bottom-up neural generative dependency models.  In _Proceedings of the 23rd Conference on Computational Natural Language Learning (CoNLL)_ , pages 227–237, Hong Kong, China. Association for Computational Linguistics.
  * Mueller et al. (2020) Aaron Mueller, Garrett Nicolai, Panayiota Petrou-Zeniou, Natalia Talmina, and Tal Linzen. 2020.  Cross-linguistic syntactic evaluation of word prediction models.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 5523–5539, Online. Association for Computational Linguistics.
  * Nivre et al. (2016) Joakim Nivre, Marie-Catherine de Marneffe, Filip Ginter, Yoav Goldberg, Jan Hajič, Christopher D. Manning, Ryan McDonald, Slav Petrov, Sampo Pyysalo, Natalia Silveira, Reut Tsarfaty, and Daniel Zeman. 2016.  Universal Dependencies v1: A multilingual treebank collection.  In _Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC’16)_ , pages 1659–1666, Portorož, Slovenia. European Language Resources Association (ELRA).
  * Nivre et al. (2020) Joakim Nivre, Marie-Catherine de Marneffe, Filip Ginter, 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 12th Language Resources and Evaluation Conference_ , pages 4034–4043, Marseille, France. European Language Resources Association.
  * Noji and Oseki (2021) Hiroshi Noji and Yohei Oseki. 2021.  Effective batching for recurrent neural network grammars.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pages 4340–4352, Online. Association for Computational Linguistics.
  * Noji and Takamura (2020) Hiroshi Noji and Hiroya Takamura. 2020.  An analysis of the utility of explicit negative examples to improve the syntactic abilities of neural language models.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 3375–3385, Online. Association for Computational Linguistics.
  * Qi et al. (2020) 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 Meeting of the Association for Computational Linguistics: System Demonstrations_ , pages 101–108, Online. Association for Computational Linguistics.
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019.  Language models are unsupervised multitask learners.
  * Ravfogel et al. (2018) Shauli Ravfogel, Yoav Goldberg, and Francis Tyers. 2018.  Can LSTM learn to capture agreement? The case of Basque.  In _Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP_ , pages 98–107, Brussels, Belgium. Association for Computational Linguistics.
  * Sennrich et al. (2016) Rico Sennrich, Barry Haddow, and Alexandra Birch. 2016.  Neural machine translation of rare words with subword units.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1715–1725, Berlin, Germany. Association for Computational Linguistics.
  * Stern et al. (2017) Mitchell Stern, Daniel Fried, and Dan Klein. 2017.  Effective inference for generative neural parsing.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 1695–1700, Copenhagen, Denmark. Association for Computational Linguistics.
  * 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.


# In-Context Probing Approximates Influence Function for Data Valuation

Cathy Jiao1 Gary Gao2 Chenyan Xiong1
1 Language Technologies Institute, Carnegie Mellon University
2 School of Computer Science, Carnegie Mellon University
{cljiao, wgao2<EMAIL_ADDRESS>
###### Abstract

Data valuation quantifies the value of training data, and is used for data
attribution (i.e., determining the contribution of training data towards model
predictions), and data selection; both of which are important for curating
high-quality datasets to train large language models. In our paper, we show
that data valuation through in-context probing (i.e., prompting a LLM)
approximates influence functions for selecting training data. We provide a
theoretical sketch on this connection based on transformer models performing
“implicit" gradient descent on its in-context inputs. Our empirical findings
show that in-context probing and gradient-based influence frameworks are
similar in how they rank training data. Furthermore, fine-tuning experiments
on data selected by either method reveal similar model performance111Code/data
can be found at https://github.com/cxcscmu/InContextDataValuation.

In-Context Probing Approximates Influence Function for Data Valuation

Cathy Jiao1 Gary Gao2 Chenyan Xiong1 1 Language Technologies Institute,
Carnegie Mellon University 2 School of Computer Science, Carnegie Mellon
University {cljiao, wgao2<EMAIL_ADDRESS>

##  1 Introduction

Data valuation using in-context probing (ICP) – prompting a LLM to determine
the quality of a training data sample – has become an important avenue for
curating high-quality training data Rubin et al. (2022); Nguyen and Wong
(2023); Wettig et al. (2024). However, it is unclear why in-context probing is
effective at training data valuation since there are multiple factors to
consider for evaluating the quality of training data: for instance, mixtures,
utility, and the quantity of data Lee et al. (2022); Xie et al. (2023); Goyal
et al. (2024).

In our paper, we offer an explanation to this phenomena by drawing connections
between ICP and influence functions Koh and Liang (2017). Theoretically, we
connect these two frameworks by showing that they both approximate change in
loss on a test task; with ICP taking an “implicit" gradient descent step on a
training sample Von Oswald et al. (2023); Dai et al. (2023). Empirically, we
observe that in-context probing and gradient-based data valuation methods
correlate in their rankings of training data for instruction-following tasks.
Furthermore, fine-tuning on smaller subsets of highly-ranked data scored by
either method resulted in better model performance compared to fine-tuning on
larger amounts of data. Finally, fine-tuning on data placed by either method
in the same data rank resulted in similar model performance in general.

Overall, our findings suggest that ICP may serve as a proxy for influence
function data valuation under certain settings (i.e., data selection for fine-
tuning). While future work can explore different settings, this direction has
some useful implications. Data valuation through ICP is cost effective, and
can even be done through API calls. In contrast, gradient-based data valuation
methods – such as influence functions – require access to model parameters,
and are computationally expensive.

##  2 Related Work

Obtaining high-quality training data is important for improving model learning
and reducing training costs Lee et al. (2022); Sorscher et al. (2023); Ye et
al. (2024); Albalak et al. (2024). One avenue for training data valuation is
influence functions Koh and Liang (2017), which estimates the influence of a
training sample on model predictions upon adding/removing it from the train
set. Despite being computationally expensive in LLM settings Grosse et al.
(2023), these methods are effective for curating subsets of high-quality
training data Pruthi et al. (2020); Park et al. (2023); Han et al. (2023); Xia
et al. (2024); Engstrom et al. (2024).

Simultaneously, recent works have also leveraged ICP for training data
valuation Rubin et al. (2022); Nguyen and Wong (2023); Iter et al. (2023);
Wettig et al. (2024). These methods involve measuring the model output
likelihoods of task given an in-context train sample, or prompting an LLM with
questions to identity high-quality training samples.

Since both influence function methods and ICP methods may be used for data
valuation, a key component to connecting these ideas lies in a recent body of
work which suggest that in-context learning implicitly performs gradient
descent by constructing meta-gradients Von Oswald et al. (2023); Dai et al.
(2023). Other frameworks exist for understanding in-context learning
mechanisms exist. For instance, Xie et al. (2021) states that in-context
learning arises from implicit Bayesian inference due to latent concepts
learned during pretraining, and Olsson et al. (2022) attributes in-context
learning to induction heads. In our work, focus our attention on the first
framework in order to draw connections between ICP and influence functions.

##  3 Preliminaries

In this section, we introduce and formalize frameworks for data valuation
through in-context probing and influence functions.

###  3.1 In-Context Data Valuation

While multiple works have examined data selection using in-context learning
abilities of LLMs Nguyen and Wong (2023); Wettig et al. (2024); Chen et al.
(2024); Li et al. (2024a), the method we focus on is the an one-shot ICP
quality score introduced in Li et al. (2024b), which was used to curate high-
quality instruction-tuning data. Given a dataset of tasks
$\mathcal{D}=\\{x_{1},...,x_{n}\\}$, each task $x_{i}=[x_{i}^{q};x_{i}^{a}]$
is composed of a query, $x_{i}^{q}$, and an answer, $x_{i}^{a}$. Let $\theta$
be the parameters of the LLM used for scoring. Then the zero-shot score of
task $x_{i}$ is:

$\text{s}_{\text{zs}}(x_{i};\theta)=\frac{1}{L}\sum_{j=1}^{L}\log
p_{\theta}(x_{i,j}^{a}|x^{q},x_{i,<j-1}^{a})$ (1)

where $x_{i,j}^{a}$ is the $j$ token in $x_{i}^{a}$ and $L$ is the length of
$x_{i}^{a}$. Given a candidate instruction $z=[z^{q};z^{a}]$, we use the one-
shot score to determine if including $z$ improves the model’s probability of
the answer:

$\text{s}_{\text{os}}(x_{i},z;\theta)=\frac{1}{L}\sum_{j=1}^{L}\log
p_{\theta}(x_{j}^{a}|z,x^{q},x_{i,<{j-1}}^{a})$ (2)

The quality score achieve through ICP reflects the contribution of $z$ for
one-shot inference across all tasks in $\mathcal{D}$:

$\text{ICP}(z,\mathcal{D})=\frac{1}{N}\sum_{i=1}^{N}\mathbbm{1}[s_{os}(x_{i},z;\theta)>s_{zs}(x_{i};\theta)]$
(3)

###  3.2 Influence Functions

Influence functions Koh and Liang (2017) approximate changes in model
predictions when adding/removing samples from the training data. Given a train
sample $z$ from training set $\mathcal{T}$, its influence on a test task $x$
is:

$\text{Infl}(z,x)=\nabla\mathcal{L}(\theta,x)H^{-1}\nabla\mathcal{L}(\theta,z)$
(4)

where $H=\frac{1}{N}\sum_{z_{i}\in\mathcal{T}\mathrel{\mathop{\mathchar
58\relax}}i={1,...,N}}\nabla_{\theta}^{2}\mathcal{L}(\theta,z_{i})$ is the
Hessian (see Appendix A for full details). However, computing $H^{-1}$
expensive and unstable in non-convex loss function settings, such as for large
deep learning models Basu et al. (2021). A simpler and more cost effective
alternative is to drop the Hessian and only keep the inner product:

$\text{Infl}_{\text{IP}}(z,x)=\nabla\mathcal{L}(\theta,x)\cdot\nabla\mathcal{L}(\theta,z)$
(5)

In particular, Yang et al. (2024) showed that despite dropping the Hessian,
$\text{Infl}_{\text{IP}}$ exhibited good order-consistency with Inf.
Furthermore, $\text{Infl}_{\text{IP}}$ can also capture the change in loss on
a test task $x$ upon training on $z$, as highlighted below:

######  Lemma 1.

Suppose we have a LLM with parameters $\theta_{t}$. At training iteration $t$,
and we perform a stochastic gradient descent with training sample $z$ such
that $\theta_{t+1}=\theta_{t}-\eta_{t}\nabla\mathcal{L}(\theta_{t},z)$. Then,

$\displaystyle\textnormal{Infl}_{\textnormal{IP}}(z,x)$
$\displaystyle=\nabla\mathcal{L}(\theta_{t},x)\cdot\nabla\mathcal{L}(\theta_{t},z)$
$\displaystyle\approx\frac{1}{\eta_{t}}\left(\mathcal{L}(x,\theta_{t})-\mathcal{L}(x,\theta_{t+1})\right)$
(6)
$\displaystyle\approx\mathcal{L}(x,\theta_{t})-\mathcal{L}(x,\theta_{t+1})$
(7)

Equation 6 results from a first-order approximation, and holds when $\eta_{t}$
is small: for instance, in fine-tuning settings (see Appendix C for
details)222See also Pruthi et al. (2020); Iter et al. (2023). If we are
interested in $\text{Infl}_{\text{IP}}$ for comparisons (i.e.,
$\text{Infl}_{\text{IP}}(z_{1},x)$ vs $\text{Infl}_{\text{IP}}(z_{2},x)$),
then equation 7 holds assuming that $\eta_{t}$ is consistent across
comparisons.

##  4 Theoretical Analysis

Given the preliminary notes in the previous section, we show how ICP is an
approximation of $\text{Infl}_{\text{IP}}$. First, we draw a connection
between gradient descent and ICP.

######  Proposition 1.

Given a LLM with parameters $\theta_{t}$, a stochastic gradient descent step
is taken with training sample $z$ at iteration $t$ such that:
$\theta_{t+1}=\theta_{t}-\eta_{t}\nabla\mathcal{L}(\theta_{t},z)$. Then for a
test point $x$ we have:

$s_{os}(x;z,\theta_{t})\approx s_{zs}(x;\theta_{t+1})$ (8)

In other words, one-shot inference for task $x$ using training sample $z$ is
similar to zero-shot inference for task $x$ after training step has been taken
on training sample $z$. This follows recent works which suggest that the
transformer attention head implicitly perform a gradient descent update (i.e,
produce meta-gradients) on its in-context inputs Von Oswald et al. (2023); Dai
et al. (2023); Li et al. (2024b). See Appendix B for details.

Finally, given train sample $z$ and a test sample $x$, we connect $ICP$ to
$\text{Infl}_{\text{IP}}$ by noting the following for
$\text{Infl}_{\text{IP}}$:

$\displaystyle\text{Infl}_{\text{IP}}(z,x)$
$\displaystyle\quad\approx\mathcal{L}(x,\theta_{t})-\mathcal{L}(x,\theta_{t+1})\;\;$
Lem. 1 $\displaystyle\quad=s_{zs}(x;\theta_{t+1})-s_{zs}(x;\theta_{t})\;\;$
Lem. 2 (appx. C) $\displaystyle\quad\approx
s_{os}(x,z;\theta_{t})-s_{zs}(x;\theta_{t})\;\;$ Prop. 1

Applying an indicator function to signify the difference in
$s_{os}(x,z;\theta_{t})-s_{zs}(x;\theta_{t})$ gives the ICP score:
$\text{ICP}(z,x)=\mathbbm{1}[s_{os}(x_{i},z;\theta)>s_{zs}(x_{i};\theta)]$.
Intuitively, the connection between ICP and $\text{Infl}_{\text{IP}}$ lies
with $\mathcal{L}(x,\theta_{t})-\mathcal{L}(x,\theta_{t+1})$. ICP approximates
this change in loss by assuming implicit gradient descent, while
$\text{Infl}_{\text{IP}}$ estimates this via a first-order approximation as
previously mentioned.

##  5 Experiments

Given our theoretical connection, we conducted experiments and compared ICP
and $\text{Infl}_{\text{IP}}$ as data valuation methods for data selection. We
used both methods to rank a pool of candidate training data samples. Following
the setup in Li et al. (2024b), we then finetuned a Pythia-1b (deduped) model
Biderman et al. (2023) on different rankings of data and evaluated its
performance.

Datasets: We used the Alpaca dataset Taori et al. (2023), which contains 52K
instruction demonstrations as our fine-tune data. Furthermore, we used the
K-Means-100 dataset from Li et al. (2024b) as an anchor task set used to
compute the influence of the demonstrations. The K-Means dataset contains 100
instructions, optimized for distinctiveness, from Alpaca dataset.

Data Selection: The ICP score for a training sample (i.e., an instruction
demonstration) from the Alpaca dataset was calculated for each test sample in
the anchor dataset, and averaged across all test samples to get the final ICP
score. The same was also done to get the $\text{Infl}_{\text{IP}}$ scores for
all training samples. Model likelihoods for ICP and gradients for
$\text{Infl}_{\text{IP}}$ were obtained from Pythia-1b-deduped.

After obtaining ICP scores (reminder: ICP $\in[0,1]$) for the Alpaca dataset,
we created ICP score bins of $\leq 0.5,>0.5,>0.8,>0.85,>0.9$. We used the
number of samples in each score bin as threshold cutoffs for
$\text{Infl}_{\text{IP}}$. For example, if the $>0.9$ ICP score bin had k
training samples, then we also treated the top k samples from
$\text{Infl}_{\text{IP}}$ as the same ranking category.

Training: We used the adam optimizer with a learning rate of $2e-7$ and a
batch size of 64 to fine-tune Pythia-1b-deduped for 3 epochs. This was done
separately for ICP and $\text{Infl}_{\text{IP}}$) for each score bin.

Evaluation: We use the Alpaca Eval dataset Li et al. (2023); Dubois et al.
(2024b), which has 805 instruction demostrations (details in Appendix D). The
evaluation metric for the Alpaca Eval dataset is winrate Li et al. (2023),
which is the expected preference of a human (or LLM) annotator for a model’s
response compared to a baseline model’s response. We followed the same setup
as Li et al. (2024b), and used GPT-4 Turbo as the annotator. Our winrates were
calculated by comparing our fine-tuned models to Pythia-1b deduped.

##  6 Results and Discussion

1a Spearman corr. ICP and $\text{Infl}_{\text{IF}}$.

1b Spearman corr. Infl and $\text{Infl}_{\text{IP}}$.

1c ICP and $\text{Infl}_{\text{IF}}$ ranking overlaps.

Figure 1: Correlation analysis between rankings on the instructions from the
Alpaca dataset assigned by in-context probing and influence function
approximations: $\text{Infl}_{\text{IF}}$ and Infl. Note: Infl was calculated
with EK-FAC Grosse et al. (2023), as described in Section 6). Table 1: Results
(winrates) evaluated on the Alpaca Eval dataset after being finetuned on data
selected by ICP and $\text{Infl}_{\text{IP}}$. The highest winrate in each
column is marked with $*$ for ICP and $\dagger$ for $\text{Infl}_{\text{IP}}$.

Score Bin | Samples | Method | Helpful Base | Koala | Self Instruct | Oasst | Vicunna | Overall
---|---|---|---|---|---|---|---|---
$\leq 0.5$ | $4186$ | ICP | $47.65$ | $58.17$ | $59.2$ | $55.61$ | $61.25$ | $56.51$
|  | $\text{Infl}_{\text{IP}}$ | $49.21$ | $57.79$ | $56.97$ | $59.89$ | $54.43$ | $56.31$
$>0.5$ | $47816$ | ICP | $57.03$ | $\mathbf{71.61^{*}}$ | $\mathbf{66.67^{*}}$ | $56.99$ | $61.53$ | $64.75$
|  | $\text{Infl}_{\text{IP}}$ | $54.33$ | $54.33$ | $\mathbf{66.67\dagger}$ | $54.33$ | $61.25$ | $58.88$
$>0.8$ | $20513$ | ICP | $\mathbf{66.41^{*}}$ | $69.07$ | $62.15$ | $\mathbf{67.57^{*}}$ | $63.75$ | $\mathbf{65.60^{*}}$
|  | $\text{Infl}_{\text{IP}}$ | $53.9$ | $\mathbf{70.39\dagger}$ | $63.2$ | $\mathbf{65.96\dagger}$ | $67.5$ | $\mathbf{64.17\dagger}$
$>0.85$ | $8012$ | ICP | $63.57$ | $67.94$ | $63.2$ | $63.98$ | $\mathbf{67.09^{*}}$ | $64.75$
|  | $\text{Infl}_{\text{IP}}$ | $\mathbf{61.42\dagger}$ | $68.18$ | $60.56$ | $63.83$ | $\mathbf{68.75\dagger}$ | $63.75$
$>0.9$ | $792$ | ICP | $46.51$ | $56.49$ | $52.77$ | $55.38$ | $56.96$ | $53.51$
|  | $\text{Infl}_{\text{IP}}$ | $53.91$ | $55.26$ | $54.58$ | $55.32$ | $48.75$ | $54.2$

We first compared the ranking of instructions scored by ICP and
$\text{Infl}_{\text{IP}}$ on the Alpaca dataset. As shown in Figure 1a, the
rankings are well-correlated (spearman=0.729, p<.05). Furthermore, Table 1
shows that fine-tuning on instruction data selected by ICP and
$\text{Infl}_{\text{IP}}$ resulted in similar model performance among
different score ranking bins. An exception can be observed in the Koala task
in Table 1, where fine-tuning on data selected by ICP peaked the $>0.5$ score
bin compared to $\text{Infl}_{\text{IP}}$ which peaked at the $>0.8$ score
bin.

In addition, the overall performance for ICP and $\text{Infl}_{\text{IP}}$
both peaked at the $>0.8$ score bin, which followed the trend observed in Li
et al. (2024b). Since Figure 1c also shows high overlap between instructions
selected by both methods in the $>0.8$ score bin (overlap = $71\%$), this
suggests that ICP and $\text{Infl}_{\text{IP}}$ have high agreement on
instruction quality and valuation. Examples of top-ranked instructions
selected by ICP and $\text{Infl}_{\text{IP}}$ are shown in Table D, and
exhibit semantic similarities.

While our empirical results showed agreement between $\text{Infl}_{\text{IP}}$
for data valuation, a question can be raised on whether ICP and
$\text{Infl}_{\text{IP}}$ both pick out inherently “good" training samples
independently, or if they are actually connected through our theoretical
analysis. In order to answer this question, we conducted experiments to
empirically verify the middle steps of our theoretical analysis, which we
describe in the following sections.

2a Spearman corr. between ICP and one-step finetune scores.

2b Spearman corr. between $\text{Infl}_{\text{IP}}$ and one-step finetune
scores.

2c ICP and one-step finetune overlaps in score ranking percentiles.

Figure 2: Correlation analysis between rankings on the instructions from the
Alpaca dataset assigned by in-context probing, $\text{Infl}_{\text{IP}}$, and
one-step finetuning.

ICP vs. One-Step Fine-tuning: We first note that the key assumption in our
analysis was: $s_{os}(x;z,\theta_{t})\approx s_{zs}(x;\theta_{t+1})$, which
serves an important middle step between ICP and $\text{Infl}_{\text{IP}}$. To
analyze this assumption empirically, we compared the ICP scores against a one-
step fine-tune setup. In this setup, we took each instruction demonstration
from the Alpaca Dataset and fine-tuned it for a single small step (lr=2e-5) on
Pythia 1b-deduped. Each instruction demonstration was fine-tuned separately
(i.e., no two instructions were fine-tuned on the same model), and model
likelihoods where obtained for each example in the K-Means-100 dataset.
Formally, for an instruction demonstration $z$ from the Alpaca Dataset, its
one-step fine-tune score is:

$\text{FT}(z,\mathcal{D})=\frac{1}{N}\sum_{i=1}^{N}\mathbbm{1}[s_{zs}(x_{i},\theta_{t+1})>s_{zs}(x_{i};\theta_{t})]$

where $\theta_{t+1}=\theta_{t}-\eta_{t}\nabla\mathcal{L}(\theta_{t},z)$
denotes the parameters of the one-step fine-tuned model, and $\mathcal{D}$
denotes the K-Means-100 dataset for this setup.

We observed decent correlation (spearman=0.607, p<.05) and overlap between the
ICP and one-step fine-tune score rankings as shown in figures 2a and 2c,
respectively, which supports $s_{os}(x;z,\theta_{t})\approx
s_{zs}(x;\theta_{t+1})$ in our setup.

Previous works have also shown that ICP and fine-tuning generate similar
attention weights, and pay attention to similar training tokens Dai et al.
(2023). However, these similarity scores have also been observed in models
without in-context ability, Deutch et al. (2024), and may be weakened when
considering order sensitivity Shen et al. (2024). Cases where the connection
between ICP and one-step fine-tuning are strengthen or weakened can be left
for future research.

One-Step Fine-tuning vs Influence: Given the empirical connection between ICP
and one-step fine-tuning in the previous section, we also examined the
empirical connection between one-step fine-tuning and
$\text{Infl}_{\text{IP}}$ (i.e., $\text{Infl}_{\text{IP}}\approx
s_{zs}(x;\theta_{t+1})-s_{zs}(x;\theta_{t})$) in order fully connect ICP to
$\text{Infl}_{\text{IP}}$. We compared one-step fine-tuning scores from the
previous section with the $\text{Infl}_{\text{IP}}$ scores on the Alpaca
Dataset, and observed good correlation (spearman=0.772 p<.05) as shown in
figure 2b. Given the theoretical and empirical ties from ICP to one-step fine-
tuning to $\text{Infl}_{\text{IP}}$, our results suggests that ICP may serve
as a proxy for $\text{Infl}_{\text{IP}}$ in this realm.

One observation from figures 2a and 2b to note is that some one-step fine-tune
scores are top-heavy (i.e., closer to 1). There are a few possible
explanations for this. For instance, performing a gradient descent step on a
training sample involves updating model parameters as opposed to passing the
training sample in-context. Consequently, the learning rate, optimization
method, and model size are factors to take into account when performing one-
step fine-tuning.

Hessian vs. Hessian-free Influence: Finally, we also compared data valuation
ranking similarities between $\text{Infl}_{\text{IP}}$ and Infl. Following the
same procedure as Section 5, we used $\text{Infl}_{\text{IP}}$ and Infl to
rank training samples in the Alpaca dataset (Figure 1b), and observed strong
correlation (spearman=0.91, p<.05) between the rankings. Note that for Infl,
we use the EK-FAC Grosse et al. (2023) approximation for computing the
inverse-Hessian product. Our results support previous works which suggested
that dropping the Hessian can make $\text{Infl}_{\text{IP}}$ a suitable
approximation for Infl Yang et al. (2024).

##  7 Conclusion

In this paper we provided both theoretical and empirical connections between
in-context probing and influence functions. In turn, this offered a possible
explanation for why in-context probing is effective for training data
valuation. There are several lines of work that can further explore this
phenomena. For instance, there may be stages of model training where the in-
context probing is more beneficial than using influence functions for data
selection, and vise versa. In addition, how these two data selection methods
compare when selecting groups of training samples is another problem to
consider.

##  8 Ethics and Limitations

First, we highlight limitations to our work. Our experiments were only
conducted on Pythia-1b deduped. As model sizes change, the question of whether
one data selection method triumphs over the other is an area for exploration.
Furthermore, we note that we our experiments are in the realm of instruction-
following tasks, and other types of tasks (e.g., question-answering,
summarization) and training settings (e.g, pretraining) should be explored. We
also note our evaluation metric (winrate) for instruction-following rely on
LLM annotation, and may be subject to LLM bias as mentioned in Dubois et al.
(2024a).

Since our work involves understanding data valuation in language models, we
cannot foresee any immediate potential risks. However, we note that language
models themselves can be susceptible to biases. We hope that this work can
lead to future work in understanding the mechanisms of LLMs. Further insight
in that realm may be beneficial in understanding model predictions, especially
when considering LLM safety, toxicity, and biases.

## Acknowledgements

We would like to thank Juhan Bae for discussions and providing insight on
adapting influence function computations for large language models.

## References

  * Albalak et al. (2024) Alon Albalak, Yanai Elazar, Sang Michael Xie, Shayne Longpre, Nathan Lambert, Xinyi Wang, Niklas Muennighoff, Bairu Hou, Liangming Pan, Haewon Jeong, Colin Raffel, Shiyu Chang, Tatsunori Hashimoto, and William Yang Wang. 2024.  A survey on data selection for language models.  _Preprint_ , arXiv:2402.16827.
  * Bai et al. (2022) Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, Nicholas Joseph, Saurav Kadavath, Jackson Kernion, Tom Conerly, Sheer El-Showk, Nelson Elhage, Zac Hatfield-Dodds, Danny Hernandez, Tristan Hume, Scott Johnston, Shauna Kravec, Liane Lovitt, Neel Nanda, Catherine Olsson, Dario Amodei, Tom Brown, Jack Clark, Sam McCandlish, Chris Olah, Ben Mann, and Jared Kaplan. 2022.  Training a helpful and harmless assistant with reinforcement learning from human feedback.  _Preprint_ , arXiv:2204.05862.
  * Basu et al. (2021) Samyadeep Basu, Philip Pope, and Soheil Feizi. 2021.  Influence functions in deep learning are fragile.  _Preprint_ , arXiv:2006.14651.
  * Biderman et al. (2023) Stella Biderman, Hailey Schoelkopf, Quentin Anthony, Herbie Bradley, Kyle O’Brien, Eric Hallahan, Mohammad Aflah Khan, Shivanshu Purohit, USVSN Sai Prashanth, Edward Raff, Aviya Skowron, Lintang Sutawika, and Oskar van der Wal. 2023.  Pythia: A suite for analyzing large language models across training and scaling.  _Preprint_ , arXiv:2304.01373.
  * Chen et al. (2024) Lichang Chen, Shiyang Li, Jun Yan, Hai Wang, Kalpa Gunaratna, Vikas Yadav, Zheng Tang, Vijay Srinivasan, Tianyi Zhou, Heng Huang, and Hongxia Jin. 2024.  Alpagasus: Training a better alpaca with fewer data.  _Preprint_ , arXiv:2307.08701.
  * Chiang et al. (2023) Wei-Lin Chiang, Zhuohan Li, Zi Lin, Ying Sheng, Zhanghao Wu, Hao Zhang, Lianmin Zheng, Siyuan Zhuang, Yonghao Zhuang, Joseph E Gonzalez, et al. 2023.  Vicuna: An open-source chatbot impressing gpt-4 with 90%* chatgpt quality.  _See https://vicuna. lmsys. org (accessed 14 April 2023)_ , 2(3):6.
  * Dai et al. (2023) Damai Dai, Yutao Sun, Li Dong, Yaru Hao, Shuming Ma, Zhifang Sui, and Furu Wei. 2023.  Why can GPT learn in-context? language models secretly perform gradient descent as meta-optimizers.  In _Findings of the Association for Computational Linguistics: ACL 2023_ , pages 4005–4019, Toronto, Canada. Association for Computational Linguistics.
  * Deutch et al. (2024) Gilad Deutch, Nadav Magar, Tomer Bar Natan, and Guy Dar. 2024.  In-context learning and gradient descent revisited.  _Preprint_ , arXiv:2311.07772.
  * Dubois et al. (2024a) Yann Dubois, Balázs Galambosi, Percy Liang, and Tatsunori B. Hashimoto. 2024a.  Length-controlled alpacaeval: A simple way to debias automatic evaluators.  _Preprint_ , arXiv:2404.04475.
  * Dubois et al. (2024b) Yann Dubois, Xuechen Li, Rohan Taori, Tianyi Zhang, Ishaan Gulrajani, Jimmy Ba, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto. 2024b.  Alpacafarm: A simulation framework for methods that learn from human feedback.  _Preprint_ , arXiv:2305.14387.
  * Engstrom et al. (2024) Logan Engstrom, Axel Feldmann, and Aleksander Madry. 2024.  Dsdm: Model-aware dataset selection with datamodels.  _arXiv preprint arXiv:2401.12926_.
  * Geng et al. (2023) Xinyang Geng, Arnav Gudibande, Hao Liu, Eric Wallace, Pieter Abbeel, Sergey Levine, and Dawn Song. 2023.  Koala: A dialogue model for academic research.
  * Goyal et al. (2024) Sachin Goyal, Pratyush Maini, Zachary C. Lipton, Aditi Raghunathan, and J. Zico Kolter. 2024.  Scaling laws for data filtering – data curation cannot be compute agnostic.  _Preprint_ , arXiv:2404.07177.
  * Grosse et al. (2023) Roger Grosse, Juhan Bae, Cem Anil, Nelson Elhage, Alex Tamkin, Amirhossein Tajdini, Benoit Steiner, Dustin Li, Esin Durmus, Ethan Perez, Evan Hubinger, Kamilė Lukošiūtė, Karina Nguyen, Nicholas Joseph, Sam McCandlish, Jared Kaplan, and Samuel R. Bowman. 2023.  Studying large language model generalization with influence functions.  _Preprint_ , arXiv:2308.03296.
  * Han et al. (2023) Xiaochuang Han, Daniel Simig, Todor Mihaylov, Yulia Tsvetkov, Asli Celikyilmaz, and Tianlu Wang. 2023.  Understanding in-context learning via supportive pretraining data.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 12660–12673, Toronto, Canada. Association for Computational Linguistics.
  * Iter et al. (2023) Dan Iter, Reid Pryzant, Ruochen Xu, Shuohang Wang, Yang Liu, Yichong Xu, and Chenguang Zhu. 2023.  In-context demonstration selection with cross entropy difference.  In _Findings of the Association for Computational Linguistics: EMNLP 2023_ , pages 1150–1162, Singapore. Association for Computational Linguistics.
  * Koh and Liang (2017) Pang Wei Koh and Percy Liang. 2017.  Understanding black-box predictions via influence functions.  In _International conference on machine learning_ , pages 1885–1894. PMLR.
  * Lee et al. (2022) Katherine Lee, Daphne Ippolito, Andrew Nystrom, Chiyuan Zhang, Douglas Eck, Chris Callison-Burch, and Nicholas Carlini. 2022.  Deduplicating training data makes language models better.  _Preprint_ , arXiv:2107.06499.
  * Li et al. (2024a) Ming Li, Yong Zhang, Zhitao Li, Jiuhai Chen, Lichang Chen, Ning Cheng, Jianzong Wang, Tianyi Zhou, and Jing Xiao. 2024a.  From quantity to quality: Boosting llm performance with self-guided data selection for instruction tuning.  _Preprint_ , arXiv:2308.12032.
  * Li et al. (2023) Xuechen Li, Tianyi Zhang, Yann Dubois, Rohan Taori, Ishaan Gulrajani, Carlos Guestrin, Percy Liang, and Tatsunori B Hashimoto. 2023.  Alpacaeval: An automatic evaluator of instruction-following models.
  * Li et al. (2024b) Yunshui Li, Binyuan Hui, Xiaobo Xia, Jiaxi Yang, Min Yang, Lei Zhang, Shuzheng Si, Junhao Liu, Tongliang Liu, Fei Huang, and Yongbin Li. 2024b.  One shot learning as instruction data prospector for large language models.  _Preprint_ , arXiv:2312.10302.
  * Nguyen and Wong (2023) Tai Nguyen and Eric Wong. 2023.  In-context example selection with influences.  _Preprint_ , arXiv:2302.11042.
  * Olsson et al. (2022) Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, et al. 2022.  In-context learning and induction heads.  _arXiv preprint arXiv:2209.11895_.
  * Park et al. (2023) Sung Min Park, Kristian Georgiev, Andrew Ilyas, Guillaume Leclerc, and Aleksander Mądry. 2023.  Trak: attributing model behavior at scale.  In _Proceedings of the 40th International Conference on Machine Learning_ , ICML’23. JMLR.org.
  * Pruthi et al. (2020) Garima Pruthi, Frederick Liu, Mukund Sundararajan, and Satyen Kale. 2020.  Estimating training data influence by tracing gradient descent.  _Preprint_ , arXiv:2002.08484.
  * Rubin et al. (2022) Ohad Rubin, Jonathan Herzig, and Jonathan Berant. 2022.  Learning to retrieve prompts for in-context learning.  _Preprint_ , arXiv:2112.08633.
  * Shen et al. (2024) Lingfeng Shen, Aayush Mishra, and Daniel Khashabi. 2024.  Do pretrained transformers learn in-context by gradient descent? _Preprint_ , arXiv:2310.08540.
  * Sorscher et al. (2023) Ben Sorscher, Robert Geirhos, Shashank Shekhar, Surya Ganguli, and Ari S. Morcos. 2023.  Beyond neural scaling laws: beating power law scaling via data pruning.  _Preprint_ , arXiv:2206.14486.
  * Taori et al. (2023) Rohan Taori, Ishaan Gulrajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B Hashimoto. 2023.  Stanford alpaca: An instruction-following llama model.
  * Von Oswald et al. (2023) Johannes Von Oswald, Eyvind Niklasson, Ettore Randazzo, João Sacramento, Alexander Mordvintsev, Andrey Zhmoginov, and Max Vladymyrov. 2023.  Transformers learn in-context by gradient descent.  In _International Conference on Machine Learning_ , pages 35151–35174. PMLR.
  * Wang et al. (2023) Yizhong Wang, Yeganeh Kordi, Swaroop Mishra, Alisa Liu, Noah A. Smith, Daniel Khashabi, and Hannaneh Hajishirzi. 2023.  Self-instruct: Aligning language models with self-generated instructions.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 13484–13508, Toronto, Canada. Association for Computational Linguistics.
  * Wettig et al. (2024) Alexander Wettig, Aatmik Gupta, Saumya Malik, and Danqi Chen. 2024.  Qurating: Selecting high-quality data for training language models.  _arXiv preprint arXiv:2402.09739_.
  * Xia et al. (2024) Mengzhou Xia, Sadhika Malladi, Suchin Gururangan, Sanjeev Arora, and Danqi Chen. 2024.  Less: Selecting influential data for targeted instruction tuning.  _Preprint_ , arXiv:2402.04333.
  * Xie et al. (2023) Sang Michael Xie, Hieu Pham, Xuanyi Dong, Nan Du, Hanxiao Liu, Yifeng Lu, Percy Liang, Quoc V. Le, Tengyu Ma, and Adams Wei Yu. 2023.  Doremi: Optimizing data mixtures speeds up language model pretraining.  _Preprint_ , arXiv:2305.10429.
  * Xie et al. (2021) Sang Michael Xie, Aditi Raghunathan, Percy Liang, and Tengyu Ma. 2021.  An explanation of in-context learning as implicit bayesian inference.  _arXiv preprint arXiv:2111.02080_.
  * Yang et al. (2024) Ziao Yang, Han Yue, Jian Chen, and Hongfu Liu. 2024.  Revisit, extend, and enhance hessian-free influence functions.  _Preprint_ , arXiv:2405.17490.
  * Ye et al. (2024) Jiasheng Ye, Peiju Liu, Tianxiang Sun, Yunhua Zhou, Jun Zhan, and Xipeng Qiu. 2024.  Data mixing laws: Optimizing data mixtures by predicting language modeling performance.  _Preprint_ , arXiv:2403.16952.

## Appendix

The appendix covers supporting information for our study. In Section A we
provide a brief overview of influence functions. In Section B we discuss a
framework introduced by Dai et al. (2023) which casts one-shot learning as
implicit fine-tuning. In Section C we provide additional computations for the
theoretical sketch we introduced in the paper. Finally, in Section D we show
examples on top instructions selected by our different data valuation methods
as noted in Section 5. We also provide a breakdown of the on the Alpaca Eval
Dataset Li et al. (2023); Dubois et al. (2024b).

##  Appendix A Influence Functions

Given a dataset of training data $\mathcal{T}=\\{z_{i}\\}_{i}^{N}$, assume
that model parameters $\theta$ fit the empirical risk minimization:

$\theta^{*}=\operatorname*{arg\,min}_{\theta\in\mathbb{R}^{D}}\frac{1}{N}\sum_{i=1}^{N}\mathcal{L}(z_{i},\theta)$
(9)

Now suppose we up-weight training example $z_{m}$ by a small value $\epsilon$.
Then, the optimal solution to the empirical risk minimization becomes:

$\displaystyle\theta^{*}(\epsilon)=\operatorname*{arg\,min}_{\theta\in\mathbb{R}^{D}}\frac{1}{N}\sum_{i=1}^{N}\mathcal{L}(z_{i},\theta)+\epsilon\mathcal{L}(z_{m},\theta)$
(10)

Which is also called the response function. We wish to find the change in
parameters $\Delta\theta=\theta^{*}(\epsilon)-\theta^{*}$, which can be done
via a first-order Taylor approximation to the response function at
$\epsilon=0$:

$\theta^{*}(\epsilon)-\theta^{*}\approx\epsilon\dfrac{\operatorname{d\\!}{}\theta^{*}(\epsilon)}{\operatorname{d\\!}{\epsilon}}\bigg{\rvert}_{\epsilon=0}$
(11)

Moreover, using the Implicit Function theorem, we get the influence of $z_{m}$
on $\theta^{*}$. ‹

$I_{\theta^{*}}(z_{m})=\dfrac{\operatorname{d\\!}{}\theta^{*}(\epsilon)}{\operatorname{d\\!}{\epsilon}}\bigg{\rvert}_{\epsilon=0}=-H^{-1}\nabla_{\theta}\mathcal{L}(z_{m},\theta^{*})$
(12)

where
$H=\frac{1}{N}\sum_{i=1}^{N}\nabla_{\theta}^{2}\mathcal{L}(\theta^{*},\mathcal{T})$
is the Hessian. As mentioned in Grosse et al. (2023), since we often want to
ground influence on something more concrete (e.g., a task), we can used a
measurement $f(\theta)$, which results in:

$I_{\theta^{*}}(z_{m})=-\nabla_{\theta}f(\theta^{*})^{T}H^{-1}\nabla_{\theta}\mathcal{L}(z_{m},\theta^{*})$
(13)

For instance, if want measure how $z_{m}$ can increase a model’s likelihood
probabilities on a test task $x=[x^{q};x^{a}]$, the we set $f(\theta)=\log
p(x^{a}|x^{q};\theta)=-\mathcal{L}(\theta,x)$ and obtain:

$I_{f}(z_{m})=\mathcal{L}(\theta,x)H^{-1}\nabla_{\theta}\mathcal{L}(z_{m},\theta^{*})$
(14)

##  Appendix B One-Shot Learning as Implicit Fine-tuning

This section details the construction in Dai et al. (2023), which connects the
transformer attention head to an implicit update step on the in-context
demonstration. First, let $X_{train},X_{test}\in\mathbb{R}^{d}_{in}$ be the
input representations of the train and test samples. Furthermore, we have the
attention query vector $Q=W_{q}X^{T}_{test}$, the attention key vector
$K=W_{k}[X_{train},X_{test}]$, and the attention value vector
$V=W_{v}[X_{train},X_{test}]$ where
$W_{k},W_{v},W_{q}\in\mathbb{R}^{d_{out}\times d_{in}}$. Then self-attention
can be expressed as

$\displaystyle Attention(K,V,Q)$
$\displaystyle=W_{v}[X_{train},X_{test}]Softmax\left(\frac{W_{k}[X_{train},X_{test}]^{T}Q}{\sqrt{d_{in}}}\right)$
$\displaystyle\approx W_{v}[X_{train},X{x}]W_{k}[X_{train},X_{test}]^{T}Q$
$\displaystyle=W_{v}X_{test}(W_{k}X_{test})^{T}Q+W_{v}X_{train}(W_{k}X_{train})^{T}Q$
$\displaystyle=(W_{ZSL}+\Delta W_{ICL})Q$ (15)

As seen above, the softmax is replaced with linear attention and the scaling
factor $\sqrt{d_{in}}$ is removed. Furthermore, $W_{ZSL}$ is the zero-shot
“attention head" weights and $\Delta W_{ICL}$ is the in-context demonstration
update applied to $W_{ZSL}$.

##  Appendix C Proofs

######  Lemma 1.

Suppose we have a LLM with parameters $\theta_{t}$. At training iteration $t$,
and we perform a stochastic gradient descent with training sample $z$ such
that $\theta_{t+1}=\theta_{t}-\eta_{t}\nabla\mathcal{L}(\theta_{t},z)$. Then,

$\displaystyle\text{Infl}_{\text{IP}}(z,x)$
$\displaystyle=\nabla\mathcal{L}(\theta_{t},z)\cdot\nabla\mathcal{L}(\theta_{t},x)$
$\displaystyle\approx\frac{1}{\eta_{t}}\left(\mathcal{L}(x,\theta_{t})-\mathcal{L}(x,\theta_{t+1})\right)$
(16)

Proof: This result above is discussed in Pruthi et al. (2020) and Iter et al.
(2023). First, we consider the change in loss of $x$ using a first-order
approximation:

$\displaystyle\mathcal{L}(x,\theta_{t+1})$
$\displaystyle=\mathcal{L}(x,\theta_{t})+\nabla\mathcal{L}(\theta_{t},x)\dot{(}\theta_{t+1}-\theta_{t})+\mathcal{O}(||\theta_{t+1}-\theta_{t}||^{2})$
(17)

Then, the change of loss is

$\displaystyle\mathcal{L}(x,\theta_{t})-\mathcal{L}(x,\theta_{t+1})$
$\displaystyle=-\nabla\mathcal{L}(\theta_{t},x)\dot{(}\theta_{t+1}-\theta_{t})+\mathcal{O}(||\theta_{t+1}-\theta_{t}||^{2})$

Next, suppose we take a stochastic gradient descent step on training sample
$z$. Then, the model parameters are updated as:
$\theta_{t+1}=\theta_{t}-\eta_{t}\nabla\mathcal{L}(\theta_{t},z)$. Thus, we
have $\theta_{t+1}-\theta_{t}=-\eta_{t}\nabla\mathcal{L}(\theta_{t},z)$. Then,
the above equation can be written as

$\displaystyle\mathcal{L}(x,\theta_{t})-\mathcal{L}(x,\theta_{t+1})$
$\displaystyle\approx\eta_{t}\nabla\mathcal{L}(\theta_{t},x)\cdot\nabla\mathcal{L}(\theta_{t},z)$
(19)

Given that $\eta_{t}$ is small (and thus $||\theta_{t+1}-\theta_{t}||^{2}$ is
small).

######  Lemma 2.

Let $\mathcal{L}(x,\theta)$ be the conditional cross-entropy loss for a task
$x=[x^{q};x^{a}]$. Then,

$\displaystyle\mathcal{L}(x,\theta)=-s_{zs}(x,\theta_{t})$

Proof:

$\displaystyle\mathcal{L}(x,\theta)$
$\displaystyle=-\frac{1}{L}\sum_{j=1}^{L}\log
p_{\theta}(x_{i,j}^{a}|x_{i}^{q},x_{i,<j-1}^{a})$
$\displaystyle=-s_{zs}(x,\theta)$

##  Appendix D Additional Tables and Figures

$ICP$ |  $\text{Infl}_{\text{IP}}$
---|---
⬇ Instruction: Create an array containing the first 10 prime numbers. ⬇ Response: Here is an array containing the first 10 prime numbers: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] |  ⬇ Instruction: Create an array containing the first 10 prime numbers. ⬇ Response: Here is an array containing the first 10 prime numbers: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
⬇ Instruction: Write an algorithm for printing all prime numbers between 0 and 100. ⬇ Response: Here is an algorithm for printing all prime numbers between 0 and 100: 1. Start with a variable ‘n‘ at 2, since 2 is the first prime number. 2. Create a loop that will iterate until ‘n‘ is greater than 100. 3. At each iteration of the loop, check if ‘n‘ is prime ... |  ⬇ Instruction: Given an array of integers and a target number, find a triplet which adds up to the target number. Input: Array: [2, 5, 3, 6, 9], Target: 12 ⬇ Response: One possible solution is to sort the array and then use two pointers to check for possible triplets. Here is the step-by-step process: 1. Sort the array in ascending order. In this case, it will be [2, 3, 5, 6, 9]. 2. Initialize a pointer ‘i‘ to the first element ...
⬇ Instruction: Generate a random string of 5 lowercase letters. ⬇ Response: Here is a randomly generated string of 5 lowercase letters: "kdjyr" |  ⬇ Instruction: Create an algorithm to sort a given array of numbers. Input: [7, 1, 3, 5, 9] ⬇ Response: There are many algorithms to sort a given array of numbers. Below is one such algorithm using the Bubble Sort method: 1. Begin by comparing the first two elements of the array ...
⬇ Instruction: Generate a random password with 8 characters, consisting of lower and upper-case letters and numbers. ⬇ Response: Here is a randomly generated password with 8 characters, consisting of lower and upper-case letters and numbers: "aB3dE6fG" |  ⬇ Instruction: Create an algorithm in pseudocode that sorts an array of numbers using the selection sort method. Input: Array: [3, 1, 4, 7, 8, 2] ⬇ Response: Here is a pseudocode that sorts an array of numbers using the selection sort method: Procedure selection_sort(Array: list of sortable items) BEGIN Declare index_min, temporary ...
⬇ Instruction: Create an algorithm to find the maximum value in an array of numbers. Input: [3, 5, 7, 2] ⬇ Response: Here is an algorithm to find the maximum value in an array of numbers: 1. Initialize the first element of the array as the maximum value. 2. Loop through the rest of the array, comparing each element with the current maximum value. 3. If the current element is ... |  ⬇ Instruction: Create a PHP script to detect whether a string contains a number. ⬇ Response: Here is one way to create a PHP script to detect whether a string contains a number: ‘‘‘ <?php function containsNumber($str) { // check if the input string contains any digits if (preg_match(’/\d/’, $str)) { return true; } else { return false; } } // test ...
Table 2: The top-5 demonstrations selected by ICP and $\text{Infl}_{\text{IP}}$ for the test task: Instruction: Create an array containing the first 10 prime numbers. Subset | Number of Examples
---|---
Helpful Base Bai et al. (2022) | 129
Koala Geng et al. (2023) | 156
Self-Instruct Wang et al. (2023) | 252
Oasst | 188
Vicuna Chiang et al. (2023) | 80
Table 3: Breakdown of the subsets in the Alpaca Eval Li et al. (2023); Dubois
et al. (2024b) dataset.