How BPE Affects Memorization in Transformers
Authors: Eugene Kharitonov
Marco Baroni
Dieuwke Hupkes
Venue: ICLR 2022 Submitted (2022)
Keywords: training data memorization
Byte-Pair Encoding
Transformers

Abstract: Training data memorization in NLP can both be beneficial (e.g., closed-book QA) and undesirable (personal data extraction). In any case, successful model training requires a non-trivial amount of memorization to store word spellings, various linguistic idiosyncrasies and  common knowledge. However, little is known about what affects the memorization behavior of NLP models, as the field tends to focus on the equally important question of generalization.
In this work, we demonstrate that the size of the subword vocabulary learned by Byte-Pair Encoding (BPE) greatly affects both ability and tendency of standard Transformer models to memorize training data, even when we control for the number of learned parameters. We find that with a large subword vocabulary size, Transformer models fit random mappings more easily and are more vulnerable to membership inference attacks. Similarly, given a prompt, Transformer-based language models with large subword vocabularies reproduce the training data more often. We conjecture this effect is caused by reduction in the sequences' length that happens as the BPE vocabulary grows. Our findings can allow a more informed choice of hyper-parameters, that is  better tailored for a particular use-case.

Under review as a conference paper at ICLR 2022
How BPE AFFECTS MEMORIZATION IN TRANSFORM- ERS
Anonymous authors Paper under houble-blind review
ABSTRACT
Training data memorization in NLP can both be beneficial (e.g., closed-book QA) and undesirable (personal data extraction). In any case, successful model training requires non-trivial amount of memorization to store word spellings, various linguistic idiosyncrasies and common knowledge. However, little is known about what affects the memorization behavior of NLP models, as the field tends to focus on the equally important question of generalization.
In this work, demonstrate that the size of the subword vocabulary learned by Byte-Pair Encoding (BPE) greatly affects both ability and tendency of standard Transformer models memorize training data, even when we control for the number of learned parameters. We find that with a large subword vocabulary size, Transformer models fit random mappings more easily and are more vulnerable to membership inference attacks. Similarly, given prompt, Transformer-basee language models with large subword vocabularies reproduce the training data more often. We conjecture this effect is caused by reduction in the sequences' length that happens as the BPE vocabulary grows. Our findings can allow a more informed choice of hyper-parameters, that is better tailored for particular use-case.
INTRODUCTION
The Transformer architecture Vaswani et al., 2017) became the backbone of the state-of-the-art
models a variety of tasks (Liu et al. 2019 Raffel et al. 2019 Adiwardana et al.) 2020 Brown et al.
2020). This spurred a significant interest in better understanding inner workings of these models (Vig
| Clark et al. 2019; Kharitonov and Chaabouni, [2000] Hahn 2020; Movva and Zhao 2020 Chaabouni al.) 2021 Merrill et al. 2021; Sinha et al. 2021). I. Most of these works have focussed specifically on how models generalize and capture structure across samples that are similar. For instance, Vigg and Belinkov (2019) focussed on how attention align with specific syntactic dependency relations, Hupkes et al. (2020) considered if Transformers generalize compositionally and Kharitonov and Chaabouni (2020) studied how different models generalize from very few data. In contrast to these studies, we focus on factors that control the training data memorization behavior of Transformers, which we believe to be important for several reasons.
and Belinkov 2019;
First, large Transformer models are increasingly often used as a storage, for instance, as a general- purpose knowledge base or as closed-book question- -answerng system (Petroni et al., 2019 Roberts et al., 22200 Lewis et al. 2020). Clearly, the ability to memorize factual knowledge from the training data is crucial for such applications. There are even Transformers models that are explicitly endowed
with external training data memorization mechanism (Khandelwal et al. 2020 2021 He et al. 2021. demonstrating that further boosting their memorization abilities is beneficial.
Second, in contrast, the same ability memorize can become undesirable and lead to leakage of personal data from trained models (Carlini et al., 2020 Thakkar et al. 2021). A better understanding of the phenomenon is thus instrumental both enable better memorization when it is needed and to avoid it when not.
Third, while generalization and memorization often thought of as competing modes of fitting data, training effective models in real tasks requires a non-tme non-trivial combination of the two. For instance, successful language models need generalize to be able deal with never-seen-hefore sentences,

---

Under review as a conference paper at ICLR 2022
but they also need to memorize the spelling of words, the non-compositional meaning of idioms, idiosyncrasies of languages, common knowledge, etc (see, e.g. Dankers et al. 2
Despite this apparent importance, there is very little research into memorization in Transformers and in NLP models in general, and we have only superficial understanding of what factors affect this behavior. Intuitively, the number of parameters, data augmentation, and regularization likely to affect how successful models are in memorization (Zhang et al. 2016 (Sallayrolles et al. 2018). In this work, we primarily focus on the influence of less obvious yet important factor: we study how the selection of modelling units affects memorization. Typically, the same data can be represented on various levels: raw bytes and their groups, individual characters, subword units, and entire words. A very common approach is to learn subword-leva vocabulary with Byte-Pair Encoding (BPE) (Sennrich et al.) 2015) or similar methods (e.g..Devlin Devlin et al. 2018 Kudo and Richardson 2018 Provilkov et al. 2019). In spite of ubiquitous use of these methods, to the best of our knowledge, there is no clear understanding of how the number of subwords or BPE operations should be chosen and how this affect behavior of model. We expect that BPE-like segmentation might play crucial role in memorization, as it controls the trade-off between the number of primitives a model will have to operate with and the lengths of sequences it must represent.
In this work, to characterize model's behavior, we measure three "facets" of training data memo- rization. First, as proxy for the memorization capacity of model, we use its ability to fit random, non-systematic mappings. Next, we study the preference for memorization when generalization is possible. For that, we study how easy it is to accurately tell if particular example was used in the model's 's training data via a membership inference attack (Shokri et al. 2017). Finally, we examine how easy it to recover training data from trained language model. We experiment with three Transformer architectures: causal & masked language models, and encoder-based classifiers.
Our main experimental finding is that, across all architectures and tasks, the choice of modeling units strongly affects the memorization behavior of the models, with large-cardinality BPE vocabularies greatly facilitating memorization. This observation holds even when we control for the number of trainable parameters.
After establishing this fact, we look deeper into the causes of the phenomenon we observe. We examine three candidate causes which are principal redundancy the data (due to compression). (ii) increase in the number of the unique units used to represent the data, or (iii) reducing the length of the training sequences. By finding similar effect with incompressible randomly generated data we can rule out the first possibility. Next, we artificially double the vocabulary size by introducing "synonym" tokens and observe that the vocabulary growth, in isolation, leads to a different memorization pattern. Thus, by exclusion, we conjecture that reducing utterance length is, at least, a very important factor of memorization
of applying BPE: (i) removing
2 STUDYING MEMORIZATION THE TASKS
To quantify the memorization capabilities and preferences of NLP models, three different setups, with which we aim to cover different facets of what one can call training data memorization.
2.1 LEARNING MAPPINGS WITH RANDOM LABELS
Firstly, we consider a task of learning non-systematic mappings, where labels are independent from inputs (Zhang et al.] [2016]. To achieve accuracy above chance, the model has to "store" the training example in some way, thus we assume that higher training accuracy implies increased training data memorization ability.
To experiment with realistic natural input data, we consider the Stanford Natural Language Inference dataset (SNLL, BBowman et al. 2015). In this dataset, each example is pair of two sentences, one representing a premise ("A boy is jumping on skateboard in the middle of a red bridge.") and the other representing hypothesis ("Th boy does skateboarding trick."). Each example is assigned
An interesting example the language model of Lakhotia al. 2021) which is trained on sub- phonemic acoustic units without word houndaries, but confidently processes a large vocahulary English words.
Another potential cause that we consider is the changes in the relative frequencies of tokens that BPE brings along. In Appendix D we investigate and rale out this hypothesis.
2

---

Under review as a conference paper at ICLR 2022
label that denotes if the hypothesis entails the premise, contradicts it, or neither contradict nor entails (neutral). We represent examples in a concatenated form with a separator token (::) between a premise and hypothesis ("A boy is jumping on skateboard in the middle of red bridge. :: The boy does skatehoarding trick."). For uniformity with other experiments, we transform the dataset into a binary classification task by filtering out all examples with neutral labels After this filtering, 367,38) examples remain. We replace original labels with randomly sampled ones (-1 / +1, equiprobably), and we measure memorization by measuring the (training) accuracy of the models on this data.
2.2 MEMBERSHIP INFERENCE
While the task of memorizing random labels can tell us how much a model can remember, doesn't ' allow us to test how much or what model memorizes when it is trained on tasks which also admit (or require) generalization. As this is typically the case with natural data, we thus need a different strategy to assess memorization in more realistic scenarios. To evaluate memorization in such cases, we resort to measuring models' vulnerability to membership inference attacks (Shokri et al.] (017). Indeed, if it is "easy" to accurately tell if particular example it is actually "stored" in the weights of the model in some form, rather than being inferred from a more general rule or pattern (which would lead to high scores also for examples that were not in the training data, but that are likely given that data).
used for training, we assume
More formally, suppose we have model fo that was trained on a subset DD' of large set of examples D. (D' C D) with D' obtained by sampling examples independently from D> with some probability X. The goal of membership inference is to figure out, given fe. whether a particular example (24, yi) E D was included in the training data D
We implement simple membership inference attack protocol by Yeom al. (2018). Given a model fe parameterized by 6, we calculate its loss on a data point (())( Wi) and compare to threshold T: it below the threshold, the data point belongs to the training data. By controlling т we can control the trade-off between precision and recall of the attack. To avoid the dependency on this parameter and to represent the entire space of possible trade-offs, we use the AUC metric. After training a model, we measure the AUC of the above rule that separates training and hold-out examples.
In this set of experiments, we again use the SNLI dataset. However, in this experiment we use the true labels of the dataset, rather than using the random labels of the previous setup, allowing to consider both generalization and memorization. To make the prior probability of an example belonging to the training dataset equal to 2. at training time (367,388 examples remaining after filtering), with the second half playing the role of the hold-out.
only half of the original's 's dataset training data
2.3 TRAINING DATA RECOVERY
Lastly, we study the memorization capabilities of Transformer models in setup that is closer to natural large-scale tasks. In particular, we focus on the interesting for memorization domain of question-answeriig exact-match answers to questions present in the training data.
and we consider how well Transformer language models can reproduce
For this experiment, we use the L.1 subset of the large-scale Probably Asked Questions (PAQ) dataset (Lewis al. 202T), which contains 14M queries with candidate answers. As with SNLI, we transform this dataset so that it is suitable for training an LM by concatenating queries and their respective candidate answers, separated by a special token (::). For instance, a training example might be "where is the capital of argentina located buenos aires". Whenever PAQ provided more than one answer, we used the first. We lower-cased questions and answers. At test-time, we prompt the trained LM by a query followed with the separator token and check whether the trained LM reproduces the correct answer within top-1 or top-5 results returned by beam search (beam size 5). To speed up the evaluation, we probe fixed random sample of 4M questions.
In the current experiment, this is not strictly necessary, since we map the input examples to random labels. Filtering the data becomes important in the next experiments, in which we instead use true labels.
3

---

Under review as a conference paper at ICLR 2022
3 MODELS AND HYPERPARAMETERS
We consider three standard Transformer-based architectures: a (causal) language model (LM), masked language model (MLM), and sequence encoder (Encoder). In our first two setups (random label memorization and membership inference). we study all three architecture variants. In the experiments on question-answe reverreee,,,,,,...v we only study the LM architecture, as those experiments require the ability to sample from the model efficiently.
3.1
BPE SETTINGS
The core question that we ask in this paper is how the choice of modeling units affects the memoriza- tion behaviour of state-of-the-art Transformer models. To answer this question, for every experiment create various versions of the involved datasets that differ in the number of subwords, by varying the parameters of the BPE process used to create subwords. In particular, for the SNLI dataset (used in random label memorization and membership inference). steps, resulting in vocabulary sizes of 611, 1097, 4943, 9574, and 18336, respectively. For the larger PAQ dataset, used in the recovery experiment, we get different versions of the dataset by running BPE for (0.5, 1, 5, 10, 15, 20) x 10 steps, obtaining vocabulary sizes of 1280, 1784, 5784, 10784, 15784, and 20776, respectively.
apply BPE with (0.5, 1, 10, 20) 103
3.2 CONTROLLING THE NUMBER OF LEARNED PARAMETERS
In our experiments. vary the size of the subword vocabulary used represent the data. In turn, the number of the learned parameters that are present in the embedding layer changes, too. It is not unreasonable expect that the memorization capabilities of a model are impacted by this growth of the number of the learned parameters. To avoid this confounding factor, we complement our study with experiments where we control for the change in the number of embedding parameters. To do so, replace the embedding layer by combination of embedding and fully-connected layer. This way, we can change the dimensionality of the input & output token embeddings and control the number of the learned parameters while maintaining the rest of the model isolated from any changes. This is standard architecture variant in fairseq (Ott et al. 2019). We report the used embedding sizes and the resulting numbers of parameters in Appendix.
3.3 CASTING MODELS AS CLASSIFIERS
Some of the tasks introduced above require that the studied models binary classifiers (e.g., learning non-systematic mappings & 2 Here we discuss how we turn our considered architectures into classifiers. Encoder takes the input sequence of length / and embeds it into continuous representation Rext, where e in the embedding size. We take the embedding of the eos token and linearly map it into logits of the labels (1-1,+11 +13). Encoder trained minimize the cross-entropy error of the target label.
To use LM classifier, we associate new tokens (which never occur in the training data) with the target labels and append them to the imput strings, after the eos tokens. We train the model using the standard teacher-foreing procedure. This way the accuracy of the classifier equates to the accuracy of the predicting last token in sequence. While this is non-standard way of training classifiers, (i) reflects some of the interesting cases where language models are used as universal zero-shot learners (Brown al., 2020), (ii) allows us compare LM's memorization capabilities with other architectures directly.
To use MLM classifier, follow a similar approach. We extend input string by token that specifies the label. At wrainingttime, this token and a random part of the other tokens are masked. The model is trained to recover all the masked tokens. The task of recovering masked label resembles how mask-filling is used in knowledge-intensie tasks (Petroni et al. 2019).
3.4 MODEL AND TRAINING DETAILS
We use similar Transformer models across experimental setups, with only slight differences, that describe below. In all experiments, we use the Adam optimizer (Kingma and Ba 2014). We
4

---

Under review as a conference paper at ICLR 2022
0.85
LM
0.50
UM
VLY
MLM
(a) Vanilla Transformer models.
(b) Models with the number of parameters fixed.
Figure 1: Training accuracy for fitting random labels on SNLL Shaded area represents #1 SEM (Standard Error of the Mean).
half-precision floats throughout all experiments. We implemented all three architectures using Pytorch (Paszke et al.) 2019).
Memorizing random labels The models are trained with learning rate 5e-4. The learning rate linearly warmed-up for the first 500 updates and then decreased under the square-root schedule. As in this experiment we are interested in the ability to overfit training data, we train the models for 500 epochs. We use batches of 512 examples. If model achieves training accuracy above or equal to 0.999, the training is stopped earlier. For LM and MLM are implemented as 4-layer, 4-head Transformers with embedding size 256 and FFN layer dimensionality of 512 In preliminary experiments, we found that a 4-layer Encoder model quickly achieves 100% label prediction accuracy (on train), irrespective of the number of subwords. Hence, in this experiment we used I-layer version for that model type with embedding and FFN sizes of 256 & 512. When training MLM, each token is masked with probability of 0.2.
Membership inference We use similar architectures and hyperparmeters as above for LM and MLM. Encoder has 4 layers, embedding size of 512 and FFN dimensionality of 1024, same as (M)LM. In this experiment we train for 100 epochs.
Question Answering In this set experiments, we use the fairseq (Ott al., 2019) imple- mentation of Transformer LM. We study two variants of the architecture: base and large. The base architecture has layers with 8 attention heads, embedding dimensionality of 512 and FFN dimen- sionality of 2048. The large architecture has 12 layers, 16 attention heads, embdedding dimension of 1024 and FFN dimension of 2048. Both variants have dropout probabilities of 0.1. In this experiment are only interested in training data memorization, hence allow all models to overfit and do not apply any early stopping. We stop training after fixed budget of 70 epochs. We use learning rate of 5e-4, inverse-sqrt learning rate schedule and linear warm-up for 4000 updates.
4 BPE INFLUENCES TRAINING DATA MEMORIZATION
In this section, we discuss our first main finding: that the number of BPE merges influences the extent to which model memorizes training data. This finding is persistent across the three different experimental setups we described carlier: random label memorization, membership inference and question-anss answer recovery. In all these experiments, we systematically control the number of merges, which is roughly the same as the vocabulary size. We also run complementary experiments where we fix the number learned parameters to stay roughly the same for each vocabulary size (see $3.2)
4.1 MEMORIZING RANDOM LABELS
In Figure I we report the accuracy on fitting the training data with random labels as a function of base-2 logarithm of the vocabulary size [V.. In Figure la we report results for "vanilla" architectures (without an additional FFN layer that allows to control for the number of learned parameters) and in Figure Th we provide results for the models with the number of parameters fixed. We see that for all
5

---

Under review as a conference paper at ICLR 2022
1.0
1.0
0.0
0.
Ereadet
Incoaet
(a) AUC, vanilla models.
(b) AUC, models with the number of parameters fixed.
0.66
0.82
VLM
0.78
(c) Test accuracy, vanilla models.
(d) Test accuracy, models with fixed number of params.
Figure 2: Membership inference attack, SNLI dataset. Shaded area represents +1 SEM.
three models, LM, MLM, and Encoder, the dependency is very consistent: as the vocabulary size grows, the models become universally more successful in fitting random labels. Encoder fits around 87% of the random labels with the subword vocabulary size of 611 and has a training accuracy of more than 98% when the vocabulary size is increased to 18,336. LM and MLM that have more layers than Encoder start off with a slightly higher accuracy (94% and 97%, respectively), their accuracy quickly climbs up to 100% when increasing the number of subwords. This tendency persists when controlling for the number of learned parameters (Figure
4.2 MEMBERSHIP INFERENCE
In Figure 2 we report the AUC for our membership inference experiments for all three architectures (recall that these experiments used the same SNLI data as the previous experiment, except with with true instead of random labels). Mirroring the results of our previous experiment, we observe monotonic dependency of the membership attack success rate in function of the size of the vocabulary used: for all architectures, larger vocabulary granularity implies more memorisation.
In Figures 2c & 2d we report the accuracy on the same exact models on the hold-out data. We see that all models achieve decent generalization, with accuracy above 0.78. From Figure 2c we see that as the vocabulary size grows, the test accuracy of (M)LM has distinct regions of growth. We believe this indicates two important points: (i) generalization is not directly at odds with memorization, and (ii) there is a level of granularity that allows better memorization and better generalization.
4.3 QUESTION ANSWER RECOVERY
In Figure 3 we report how the top-1 (Figure 3a and top-5 (Figure 3b) accuracies change in function of the logarithm of the vocabulary size. We report results for Transformer- and Transformer- large modifications, alongside with the parameter-controlle variants. We firstly observe that the model size has a large impact on memorization: LM-large outperforms LM-base in all cases. Next, we see that both models confirm the pattern observed in the previous experiments: vocabulary growth consistently leads to a growth in the memorization accuracy.
Focusing the models with the number of parameters fixed, the total number of embedding parameters, the size of the learned vocabulary greatly affects the ability of recovering training data.
that even when correcting for

---

Under review as a conference paper at ICLR 2022
0.34
Eact contro
Eaes centred Large-tae caneooooo
L8 canvel
20.25
0.00
0.6
0.0
(a) Top-1 accuracy.
(b) Top-5 accuracy.
Figure 3: Training data recovery: top-1 and top-5 accuracy on extracting the correct answer when prompted with a query.
0.
Eneoser
0.
vecub
105u M
(a) Random strings.
(b) SNLL BPE vs. Duplicated vocab.
Figure 4: Analysing potential causes of the increased memorization: fitting random labels random strings (left) and SNLI (right) datasets. Everywhere shaded area represents #1 SEM.
LOOKING FOR EXPLANATIONS
In $ we established that larger vocabularies, learned by BPE, lead stronger memorization in Transformer models, even when control for the number of the learned parameters. In the current section, we focus on why this might be case, and further investigate this observed effect.
We hypothesise that the primary cause of the observed behavior is that with the growth of the BPE vocabulary the input sequences become shorter (length hypothesis). In turn, shorter sequences are casier to memorize the work of attention is simplified. Indeed, it is known that learning complex attention patterns hard and often multiple attention heads turn out to be useless, which potentially limits the ability to memorize complex "explanations" of the data (Voita al. [019 Michel et al. 2019). At the same time, shorter sequences would shift the responsibility for memorization onto FFN layers, which known memorize well (Zhang al. 2016).
However, there could be two alternative explanations at play. Being a compression algorithm originally, BPE compresses the data and it could be easier memorize data without redundancies (redundancy hypothesis). Second, BPE increases the vocabulary size and it is possible that each individual token becomes more predictive of the label (vocabulary size hypothesis). As an illustration, in the limit case of the vocabulary growth, every sequence might have unique token. In this case, there is one-to-one mapping between those tokens and labels (answers) that will, again, simplify the work of self- self-attention. In a series of experiments below, we contrast out these three hypotheses.
5.1 EFFECT PERSISTS ON INCOMPRESSIBE DATA
To investigate the redundancy hypothesis, we experiment with learning on randomly generated incompressible data and examine whether a similar behavior persists We generate random data by enumerating all 2 binary (V {0, 1)) sequences of length / and randomly assign each sequence to
'Generally, BPE stops before that, as it does not cross word boundarics.
Note that in 44.1 experimented with random labels; here, the input sequences are random, too.
7

---

Under review as a conference paper at ICLR 2022
one of two classes, 1-1,+1] To study how the chosen level of representation affects the models' memorization capacity, we apply BPE with (0, 4, 8, 16, 32, 64, 128, 256) steps on the generated data. This allows us to start from binary dataset with sufficiently large sequences and produce sequence of datasets of the same storage complexity (in bits), but with varied vocabulary sizes.
In Figure 4 we report the accuracy fitting the training data with random labels function of the logarithm of the vocabulary size. Again, we observe that for all three architectures the dependency very consistent: as the vocabulary size grows, the models become universally more successful in fitting random labels 6 We conclude that the increased memorization success is thus not caused by BPE compressing- out redundancies in more natural data.
5.2
VOCABULARY SIZE GROWTH DOES NOT EXPLAIN BETTER MEMORIZATION
To investigate the vocabulary size hypothesis we set up an experiment in which we increase the vocabulary size, while keeping sequence lengths constant. We start from our earlier random label memorization setup with SNLI data, using the vocabulary learned with 500 BPE operations. To increase the number of tokens in this vocabulary, we randomly replace each unique token's occurrence with either of two new tokens, with equal probability, roughly doubling the vocabulary size. For instance, say that the current vocabulary has token "cat". We then iterate over the corpus and replace half of its occurrences with "catl" and the other half with "cat2" (making sure that those do not happen in the prior vocabulary). Thus, if the vocabulary growth alone can explain the observed effect, we will see that the datasets with "duplicated" tokens would also be casier to memorize.
We report results of this experiment using the LM model in Figure 4b contrasting it to the BPE- induced memorization results. We see that the resulting curves exhibit considerably different patterns. The line that corresponds to the doubling procedure has a sharp fall in the beginning. Later, as the vocabulary size grows, in accordance with in our thought experiment, tokens become increasingly more unique to sequences which boosts the train accuracy. In contrast, the line obtained by growing the vocabulary via BPE shows monotonic, consistent growth for all vocabulary sizes. From that we can conclude that the observed phenomenon cannot be explained solely by the vocabulary growth.
To summarize, the above experiments allowed us to rule out the alternative explanations (redundancy and vocabulary growth hypotheses) and we conclude that reduction of the sequence length is the primary factor of the obxerved memorization effect
6 DISCUSSION
While the generalization abilities of state-of-the-arr models in NLP have been quite extensively studied in the recent past (Finegan- Doolak et al. 2018; Hupkes et al. 2018 Lake and Baroni 2018 Keysers et al. 2019 Korrel et al. [219 Mul and Zuidema, 2019 Raunak et al. 2019 Saxton et al.
Kim and Linzen [0nkerankers
Dankers et al. [202]] Vig and Belinkov 2019 Dubois et al. 2020
Hupkes al.) 2020) Kharitonov and Chaabouni] 2020) comparatively little is known about what
factors impact how such models memorize.
For modelling natural data, however, both generalization and memorization relevant properties. In some cases, because memorization is harmful for instance when personal data leak from a trained model. In other cases, memorization instead is necessary for accurate performance for instance to recall the spelling of words or the meanings of idioms. In this work, we therefore focus specifically on memorization, considering in particular the impact of the choice of modelling unit, which recently became particularly relevant given that all current SOTA NLP architectures are trained with an experimentally tuned number of subwords.
We studied memorization behavior of three types of Transformer models (causal and masked lan- guage models, and an Encoder-based classifier). We looked at memorization from three different perspectives: the ability to memorize random mappings. vulnerability to membership inference
'In this experiment, for small vocabulary sizes, the total number of learned parameters is nearly constant. 7 For instance, nothing will change for a token that occurs once in the dataset.
'A flip side of this conjecture is that a more expressive attention improves memorization. In Appendix we show this to be the case: increasing the number of attention heads improve random sequence memorization.
8

---

Under review as a conference paper at ICLR 2022
attacks, and ability to directly reproduce training data on prompt. We have observed strong and monotonic influence of the BPE vocabulary size on how successful Transformer models are at memorizing training data. With higher granularity vocabulary (i.e., more BPE merge operations), Transformers (a) can memorize random mappings better, hence they have higher memory capacity, and (b) do memorize more of training data in realistic tasks.
We considered several explanations for this strong trend. Is the increase perhaps due to the increase in the number of trainable parameters? Often, the embedding layer has a noticeable share of the trained parameters and this number grows with the size of the vocabulary. We show that while this growth does play a role, the effect persists when we ensure that the number of trained parameters remains constant when the granularity of the vocabulary grows.
Next, we conjecture that the phenomenon is caused by the reduction in the sequence length that correlates with using larger-cardinality BPE vocabularies. It can simplify memorization, as the latter will no longer require learning complex attention patterns "explaining" the data and offset complexity onto fully-connected layers, which are known to be good in memorization (Zhang et al., 2016). In contrast, learning useful attention patterns is hard and often multiple heads turn out to be useless (Voita et al. 2019 Michel et al. 2019h. Hence, it is possible that self-attention serves as bottleneck that limits the memorization capacity.
There are, however, two alternative explanations of the observed trend. It can happen that compressed data with less redundancy is easier to memorize (redundancy hypothesis). However, our experiment on random artificial data (Section 4.1) indicates that the reported effect holds even when the data is not compressible in the information- explain the behavior? It does not seem so: our experiment with artificially duplicating tokens shows that this only starts to improve memorization with relatively large vocabularies and is detrimental for memory at the beginning. After ruling out the two alternative possibilities, we are left with our initial hypothesis that using gigher-cardinaliig BPE subword vocabularies implies having to manage shorter sentences on average, which in turn enable easier memorization.
sense. Further, can the growth of the vocabulary size
With our work, we contribute to the important question of what impacts memorization behaviour in Transformer models. We believe that our findings, firstly, have an important practical implication. Our experiments provide a clear demonstration that both in artificial and natural data, the simple choice of the number of subwords used has a large impact on the extent to which models memorize training data, a fact that is not at all obvious when merely looking at performance on i.i.d. train/test splits. This therefore calls for a more careful considcration of how many subwords to use for a particular task, a decision that, in practical scenarios, is rarely thoroughly motivated or investigated. In cases where a lot of memorization is desirable (e.g.. QA-tasks) or undesirable (e.g.. public models trained on medical data), the number of subwords could provide important factor in tuning the amount of memorization that happens inside a model. Our findings can provide guidance for tuning the learned data structures (e.g.. learned Bloom filter-like existence indexes (Kraska et al., 2017)) and compression algorithms that train a Transformer model on the data-to-be-compressed as a compression step (Izacard et al. 2019 Bellard 202T). If increasing the subword vocabulary size is not possible, boosting expressiveness of the attention can provide another solution (Appendix A).
Second. our work provides an interesting perspective about the relationship between memorization and generalization. As we already mentioned before, memorization and generalization are often thought of as competing modes of fitting data. Even in work that explicitly acknowledges that both are required to model natural language (e.g. Dankers et al.) 2021). }. they are still seen skills that are required in different situations: some examples, or phrases require memorization, while others require generalization. However, our experiments with SNLI data show the relationship between memorization and generalization are not directly at odds with each other, there relationship is more complex than that: there appears to be a level of granularity that allows better memorization and generalization. This experiment therefore begs the question: what is the actual relationship between memorization and generalization in neural networks? To what extent does one help the other? Is this related to the age-old processing vs storage question in human language processing (Jackendoff 2007 Pinker 1999. Pinker and Prince 1988 Clahsen 1999 Rumelhart and McClelland 1986)?
9

---

Under review as a conference paper at ICLR 2022
REFERENCES
Daniel Adiwardana, Minh-Thang Luong, David R So, Jamie Hall, Noah Fiedel, Romal Thoppilan, Zi Yang, Apoorv Kulshreshtha, Gaurav Nemade, Yifeng Lu, et al. Towards a human-like open- domain chatbot. arXiv preprint htt::2001.09977, 2020.
Fabrice Bellard. Nnep v2: Lossless data compression with transformer. 2021.
URL https
1/bellard httpl/aardror///m///m/......../
Samuel R. Bowman, Gabor Angeli, Christopher Potts, and Christopher D. Manning. large annotated corpus for learning natural language inference. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing (EMNLP). Association for Computational Linguistics, 2015.
Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. arXiv preprint arXiv:2005. 14165, 2020.
Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voss Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, et al. Extracting training data from large language models. arXiv preprint arXiv:2012.07805, 2020.
Rahma Chaabouni, Roberto Dessi, and Eugene Kharitonov. Can transformers jump around right in natural language? assessing performance transfer from scan. arXiv preprint arXiv:2107.01
2021.
Harald Clahsen. Lexical entries and rules of language: A multidisciplinary study of German inflection. Behavioral and Brain Sciences, (2(6):99111013 December 1999. ISSN 0140-525X, 1469-1825. doi: 10.101775504445255990022222 URL
article
Kevin Clark, Urvashi Khandelwal, Omer Levy, and Christopher D Manning. What does bert look at? an analysis of bert's attention. arXiv preprint 190600446 2019.
Verna Dankers, Elia Bruni, and Dieuwke Hupkes. The paradox of the compositionality of natural language: a neural machine translation case study. CoRR, abs/2108.05885, 2021. URL httttt
//arxiv..oo org abs/ /2108. 05885
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint / 1810.04803 04805, 2018.
Ming-Wei
Yann Dubois, Gautier Dagan, Dieuwke Hupkes, and Elia Bruni. Location Attention for Extrapo- lation to Longer Sequences. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 403-413, Online, July 2020. Association for Computational Lin- guistics. doi: 10. 00.18633/v/2020.co wtt.0222...-mmai...3..3 m9. URL /ttp::::/aaaaatooolggg..oo/o//// www.://ooooooo..o222oo00/00 acl 101-main.3. 39
Catherine
Jonathan K Kummerfeld, Li Zhang, Karthik Ramanathan, Sesh Sadasivam, Rui Zhang, and Dragomir Radev. Improving text-to-SQL evaluation methodology. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long
Papers). pages 351-360, 2018. URLhttps:: /RRLLtttss://acaanrre http///aaaaaaooooooo////// // 10..1/////1113////////13
Michael Hahn. Theoretical limitations of self attenattention neural sequence models. Transactions of the Association for Computational Linguistics, 8:156-1 171, 2020.
Junxian He, Graham Neubig, and Taylor Berg- King-Kirkpatrick. Efficient nearest neighbor language models. arXiv preprint arXiv:2109.04212. 2021.
Dicuwke Hupkes, Sara Veldhoen, and Willem Zuidema. Visualisation and 'diagnostic classifiers' reveal how recurrent and recursive neural networks process hierarchical structure. Journal of Artificial Intelligence Research, 61:907-926. 2018.
Dieuwke Hupkes, Verna Dankers, Mathijs Mul, and Elia Bruni. Compositionality decomposed: how do neural networks generalise? Journal of Artificial Intelligence Research, 67:757-795, 2020.
10

---

Under review as a conference paper at ICLR 2022
Gautier Izacard, Armand Joulin, and Edouard Grave. Lossless data compression with transformer. 2019. URL
Ray Jackendoff. A parallel architecture perspective on language processing. Brain research, 1146:
2-22, 2007.
Daniel Keysers, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashu- bin, Nikola Momchev, Danila Sinopalnikov, Lukasz Stafiniak, Tibor Tihon, et al. Measuring compositional generalization: A comprehensive method realistic data. In International Con- ference on Learning Representations, 2019. URL https:::// htttt::s///ppeeevie...... wttpreeeiiieenee/pd2L..... SygcCnNKwr
Urvashi Khandelwal, Omer Levy, Dan Jurafsky, Luke Zettlemoyer, and Mike Lewis. Generalization through memorization: Nearest neighbor language models. In International Conference Learn- ing Representations, 2020. URL https: /
for::/oormm?e www.kkmmmmiikii.m.. JCCKV JCEKvH
Urvashi Khandelwal, Angela Fan. Dan Jurafsky, Luke Zettlemoyer, and Mike Lewis. Nearest neighbor machine translation. International Conference on Learning Representations, 2021.
URL
net. forum? (earrmmmiddwwC0BFJJBM.
Eugene Kharitonov and Rahma Chaabouni. What they do when in doubt: study of inductive biases in seq2seq learners. arXiv preprint arXiv:2006. /4953, 2020.
Najoung Kim and Tal Linzen. COGS: compositional generalization challenge based on semantic interpretation. In Proceedings of the 2020 Conference Empirical Methods in Natural Language Processing (EMNLP), pages 9087-9105, 2020. URL https: /att:::://acaantoolloooooo 0000222000000
emn in. 7317
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint 2014.
Kris Korrel, Dicuwke Hupkes, Verna Dankers, and Elia Bruni. Transcoding compositionally: Us-
ing attention find more generalizable solutions. In Proceedings of the 2019 ACL Workshop
BlackboxXLP: Analyzing and Interpreting Neural Networks for NLP, pages 1-11, Florence, Italy, August 2019. Association for Computational Linguisties. doi: 10. N0.18653/v1/V/ 1/W1///////119908000 URL
https://aclanm http://cclliii wtw.:/annnnntoo....ooooooo
4801
Tim Kraska, Alex Beutel, Ed H Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. arXiv preprint 1712.0020, 2017.
Taku Kudo and John Richardson. SentencePiece: A simple and language independent subword tokenizer and detokenizer for neural text processing. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, 2018.
Brenden Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of sequence-to-sequeee recurrent networks. In proceedings of the 35th International Conference on Machine Learning (ICML), pages 4487-4499, 2018
Kushal Lakhotia, Evgeny Kharitonov, Wei-Ning Hsu, Yossi Adi, Adam Polyak, Benjamin Bolte, Tu-Anh Nguyen, Jade Copet, Alexei Baevski, Adelrahman Mohamed, and Emmanuel Dupoux. Generative spoken language modeling from raw audio. arXiv preprint arXiv:2102.00 192, 2021.
Patrick Lewis, Pontus Stenetorp, and Sebastian Riedel. Question and answer test-train overlap in open-domain question answering datasets. arXiv preprint arXiv:2008..06637, 2020. 2020.
Patrick Lewis, Yuxiang Wu, Linging Liu, Pasquale Minervini, Heinrich Küttler, Aleksandra Piktus, Pontus Stenetorp, and Sebastian Riedel. PAQ: 65 million probably-askee asked questions and what you can do with them. arXiv preprint 20Xiv:2
2021.
Yinhan Liu. Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv: 1907. 1692, 2019.

---

Under review as a conference paper at ICLR 2022
William Merrill, Vivek Ramanujan, Yoav Goldberg, Roy Schwartz, and Noah Smith. Effects of parameter norm growth during transformer training: Inductive bias from gradient descent, 2021.
Paul Michel, Omer Levy, and Graham Neubig. Are sixteen heads really better than one? arXiv preprint arXiv: 10650, 2019.
Rajiv Movva and Jason Y Zhao. Dissecting lottery ticket transformers: Structural and behavioral study of sparse neural machine translation. arXiv preprint arXiv:2009. 2020.
Mathijs Mul and Willem Zuidema. Siamese recurrent networks learn first-order logic reasoning and exhibit zero-shot compositional generalization. In CoRR, abs/1906.00180, 2019. URL
btttps://arxiv.org///eee /06../196.... 001 00l.e001110000000 pdf
Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng. David Grangier, and Michael Auli. fairseq: A fast, extensible toolkit for sequence modeling. In Proceedings of NAACI-HLT 2019: Demonstrations, 2019.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Veto,o, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high -eigh-eeffrrancce deep learning library. In Advances in Neural Information Processing Systems 32. 2019.
Fabio Petroni, Tim Rocktäschel, Patrick Lewis, Anton Bakhtin, Yuxiang Wu, Alexander H Miller, and Sebastian Riedel. Language models as knowledge bases? arXiv preprint 19Xi::1909.0 096600066...... 2019.
Steven Pinker. Words and rules: The ingredients of language. 1999.
Steven Pinker and Alan Prince. On language and connectionism: Analysis of a parallel distributed
processing model of language acquisition. Cognition, (8))):33-193, 1988. ISSN 0010-0277. doi: http::///.oog///11000000001000//
URL https: www. www.eceiieeect........cc..eeeee.
com/ cttp://cceeeeearrr..ee//e//////0
Ivan Provilkov, Dmitrii Emelianenko, and Elena Voita. Bpe-dropout: Simple and effective subword regularization. arXiv preprint 17Xiv:1910.13266 2019.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. arXiv preprint 1910:11910.10683, 2019.
Vikas Raunak, Vaibhav Kumar, Florian Metze, and Jaimie Callan, On compositionality in neural machine translation. In NeurlPS 2019 Context and Compositionality in Biological and Artifi- cial Neural Systems Workshop, 2019. URL hittts::/vvaabhav55555
compo. Fdf
Adam Roberts, Colin Raffel, and Noam Shazeer. How much knowledge can you pack into the parameters of language model? arXiv preprint 2xX1::2002.089100, 2020.
D E Rumelhart and McClelland. On Learning the Past Tenses of English Verbs. Parallel distributed processing: Explorations in the microstructure of cognition, pages 2711662111.12 MIT Press, pdf
Cambridge, MA, 1986. URL https: /ttps:://pps..dttteee. dtic wttp:/att...mmmti..eeeeeeeeee http://///daaAaA//////2
Alexandre Sablayrolles. Matthijs Douze, Cordelia Schmid, and Hervé Jégou. Deja an empirical evaluation of the memorization properties of convnets. arXiv preprint
2018.
David Saxton, Edward Grefenstette, Felix Hill, and Pushmeet Kohli. Analysing mathematical reasoning abilities of neural models. In Proceedings of the 7th International Conference on Learning Representations (ICLR), 2019.
Rico Sennrich. Barry Haddow, and Alexandra Birch. Neural machine translation of rare words with subword units. arXiv preprint arXiv: /00.:500.00775 2015.
12

---

Under review as a conference paper at ICLR 2022
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE Symposium on Security and Privacy (SP). pages 3-18. IEEE, 2017.
Koustuv Sinha, Robin Jia, Dieuwke Hupkes, Joelle Pineau, Adina Williams, and Douwe Kiela. Masked language modeling and the distributional hypothesis: Order word matters pre-training for little. CoRR, Abs/2104.06644, 2021. URL https: /ttp//awww.g.aaaaaaaaaaaaa 221./2211..06.6.6
Om Dipakbhai Thakkar, Swaroop Ramaswamy, Rajiv Mathews, and Francoise Beaufays. Under- standing unintended memorization in language models under federated learning. In Proceedings of the Third Workshop on Privacy in Natural Language Processing, 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. arXiv preprint
2017.
Jesse Vig and Yonatan Belinkov. Analyzing the structure of attention transformer language model. In Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 63-76, Florence, Italy, August 2019. Association for Computational Lin- guistics. doi: 12118633/11/1199444
htLLhttts///aclantthtt 00-44//9900/////14400 98088
Elena Voita, David Talbot, Fedor Moiseev, Rico Sennrich, and Ivan Titov. Analyzing multi-heat self-attention: Specialized heads do the heavy lifting, the rest can be pruned. arXiv preprint arXiv:1905.094/1, 2019.
Samuel Yeom, Irene Giacomelli, Matt Fredrikson, and Somesh Jha. Privacy risk in machine learning: Analyzing the connection to overfitting. In 2018 IEEE 31st Computer Security Foundations Symposium (CSF), pages 268-282. IEEE, 2018.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv: 1.01500030, 2016.
George Zipf. Human Behavior and the Principle of Least Effort. Addison- Wesley, Boston, MA, 1949.
13

---

Under review as a conference paper at ICLR 2022
A NUMBER OF HEADS
In our analysis in $ we conjecture that the observed effect is caused by the fact that carde-cardinaltty BPE vocabulary reduces pressure on attention to learn complex patterns due having less tokens to attend to. This raises the next question: if we increase the power of attention (e.g., by growing number of heads) would the memorization be improved? memorization experiment. This time, have fixed the BPE vocabulary size (8 merges) and varied the number of heads used in each layer as {1, 2, 4, 8, 16] and measured the training accuracy.
investigate that, we repeated our random-string
Our results in F Indeed it seems that the attention serves as a representation bottleneck that does not allow to easily model complex interactions between tokens and, in turn, limits the memorization. What observe in this paper is that, when needed, this limitation can be alleviated by (a) increasing granularity of the units that represent the data (e.g.. by running BPE), or (b) improving representation power of the self-attention mechanism.
expectations: more heads allow more successful memorization.
B HYPERPARAMETERS USED IN EXPERIMENTS
B.1 RANDOM LABELS, SNLI
In all experiments we use fixed (sinusoidal) positional embeddings. We use starting learning rate of 5e-4 that linearly warmed-up for 500 epochs and then decayed under the inverse-sqrt rule. We use half-precision floats represent the weights. Batch size is 512. In these experiments, dropout. LM & MLM models have 4 layers while Encoder has 1. For each BPE vocabulary size, we repeated experiments with 3 different random seeds. The attention layers have 4 heads. Hidden and embedding layers have dimensionalitics of 512 and 256. Depending on the experiment, we used 1 or 4 GPUs train each model, maintaining the overall batch size constant.
disabled
B.2 MEMBERSHIP INFERENCE
For (M) LM we used the same parameters as B.1 In this experiment, Encoder has 4 layers. embedding size of 512 and FFN size of 1024. We trained for 100 epochs.
B.3
QA
We used the standard Transformer LM models of fairseq that are specified by the arrch-trannfoormer_nnn (large) and armcaaattaafs
(base).
We use fixed (sinusoidal) positional embeddings. The base architecture has 6 layers with attention heads, embedding dimensionality of 512 and FFN dimensionality of 2048. The large architecture has 12 layers, 16 attention heads, embdedding dimension of 1024 and FFN dimension of 2048. Both
1.0
Encoder
0.9
MLM
accuracy
0.8
2
10
12
14
16
num. heads
Figure 5: Random label memorization accuracy vs. number of heads.
14

---

Under review as a conference paper at ICLR 2022
BPE steps
token embedding size
num. parameters
500
4400
18,311,749
IK
3050
18,239,335
5K
900
18,238,681
10K
480
18,105,19
20K
260
18,231,47
Table LM: input embedding size and number of learned parameters for the control models.
BPE steps
token embedding size
num. parameters
500
4400
18,316,149 149
1K
3050
18,242,385
5K
900
18,239,581
10K
480
18,105,672
20K
260
18,231,734
Table 2: MIM: input emhedding size and number of learned parameters for the control models.
variants have dropout probabilities of 0.1. All models are trained for 70 epochs. We use a learning rate 5e-4, inverse-sqrt learning rate schedule and a linear warm-up for 4000 updates. Again, we used half-precision floats to represent models' weights. The input and output embedding matrices shared the models. Each GPU's batch contains up to 3072 tokens and accumulate gradients from batches before running update. The models were trained on GPUs each.
B.4 RANDOM SEQUENCES
As in $ B.I
B.5
DUPLICATED TOKENS EXPERIMENT
As in
B.1
B.6 CONTROL MODELS
In experiments where we control the number of learned parameters, input token embedding size is no longer attached to the embedding size within the Transformer model (which remains identical to the vanilla, non-ctontrolled model). Tables 1-6 we report the embedding sizes and the number of leamned parameters for control models we used in experiments.
C TRAINING DATA EXTRACTION WITH SAMPLING
In this Section we investigate whether the relation between the success rate in the training data extraction experiments and the BPE-leamndd vocabulary size, reported in Section 4.3 and Figure is independent from the way we generate continuations of prompt.
We re-evaluate the training data extraction performance for the large models used in Section 4.3 We follow exactly the same protocol as in Section 4 with one exception: instead of using beam search, we sequentially sample tokens from the language model (i.e., we run ancestral sampling) at temperature 1.0. For each prompt, we sample 20 candidates and measure how often the ground- truth continuation among those. We report our findings in Figure that the reported relation has the same form before: larger BPE vocabulary sizes lead to better memorization. Overall, we conclude that our findings are likely to be independent from the specific training data extraction method used.
From Figure 6 we see
15

---

Under review as a conference paper at ICLR 2022
BPE steps
token embedding size
num. parameters
500
1125
1,792,731
IK
785
1,791,741
5K
231
1,787,673
10K
125
1,788,106 106
20K
67
1,790,056
Table Encoder: input embedding size and number of learned parameters for the control models (1
layer).
BPE steps
token embedding size
num. parameters
500
3000
13,322,138
IK
2300
13,294,038
5K
820
13,305,718
10K
460
13,287.138
20K
220
12,670,778
Table 4: Encoder: input embedding size and number of learned parameters for the control models (4 layer).
D CAN CHANGES IN FREQUENCY DISTRIBUTION CAUSE THE OBSERVED EFFECT?
In the main text, we considered three factors that accompany growing BPE vocabulary sizes: reduction in sequence length, increased number of tokens, and decrease in the redundancy. Another potential confounding behavior is that BPE affects the (relative) frequency of the tokens used for modelling the data.
To showcase this, dataset with the number of merges varied in {100, 400, 1000, 5000} and, for each token, measure its frequency in the corpus. Next, sort the tokens in the order of decreasing frequency and plot token frequency in function of its order after sorting. We can expect that with the increased number of merges, BPE-learned subwords will start approximating words more closely and the frequeeny distribution of tokens will approach that of words. In turn, the latter follows an extremely skewed Zipf distribution (Zipf) 1949). Figure 7a supports this prediction: increasing the number of merges forces the token distribution to become more peaky.
the following experiment. We take BPE vocabularies learned for the SNLI
0.20
Large
0.19
0.18
0.16
0.15
0.14
loge/V|
Figure 6: Training data recovery: top-20 accuracy on extracting the correct answer when prompted with query (sampling).
16

---

firstly group Under review as a conference paper at ICLR 2022
BPE steps
token embedding size
num. parameters
500
3000
162,139,136 136
IK
2900
162,269,536
5K
1420
162,278,176
10K
860
162,192,256
15K
620
162,212,576
20K
480
162,112,256
30K
335
162,150,096
Table 5: LM-Large, QA experiment: input embedding size and number of learned parameters for the
control models.
BPE steps
token embedding size
num. parameters
500
2400
24,444,928
IK
1965
24,433,048
5K
811
24,443,424
10K
468
24,441,472
15K
328
24,428.352
20K
253
24,430,728
30K
174
24,447,136
Table 6: A.MBase,, QA experiment: input embedding size and number of learned parameters for the control models.
Can the increased skeweness of the token distribution explain the increased memorization? To rule this possibility out, we run an experiment where the token distribution is fixed to uniform, but the sequence length is reduced.
To achieve this, we start from the same dataset of random strings as in Section 5.1 In this dataset, the initial distribution of Os and 1s uniform
enumerate all binary strings of a fixed length. Next, we replace BPE with an "idealized" subword learning procedure which maintains the uniform distribution of tokens but reduces the lengths of the strings. The procedure is simple:
all possible pairs of Os and Is into new tokens (00, 01, 10, 11) and use them to encode the initial strings (e.g., "0 00000000000 000000 00000000000000000000000000000000 0 I" becomes "00 00 00 00 00 00 00 01"). We recursively repeat this procedure, obtaining sequence of views of the same dataset, at each step growing the vocabulary size quadratically 4. 16, and 256) and reducing the string length by two. In this process. all tokens remain uniformly distributed.
Using the obtained series of datasets, we repeat the random label memorization experiment (Sec- tion 5.1) and report the results obtained in Figure 7b We observe that the reported effect persists even in the case when the relative frequencies of tokens are not changed and fixed to be uniform, thus disproving the hypothesis that the observed effect is due to frequency and not token length.
17

---

Under review as a conference paper at ICLR 2022
600
500
500
BPE 1000
BPE 5000
400
Frequency,
300
200
100
20
40
80
100
taken rank
(a) Token frequency in function of its frequency rank (position in the list of tokens when sorted in the decrcasing frequency order) for BPE vocabularies of different sizc. SNLI dataset.
1.0
0.9
Train accuracy
Encoder
LM
MLM
0.5
logz [V]
(b) Accuracy on fitting random labels on random strings. The vocabulary size controlled by a procedure that maintains uniform distribution of the tokens (see the text).
Figure 7: Investigating the relative frequency hypothesis.
18


Reviews:
[{"review_id": "kvjX77J-v5O", "reviewer": "Reviewer_WXGB", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n1. The experiments are comprehensive. The authors design three different types of experiments to thoroughly compare the memorization ability differences between three different models (Encoder, LM, MLM).\n2. The paper explores the relationship between the memorization and generalization capabilities of the model, and shows that generalization is not directly at odds with memorization, which can inspire future model design.\n\nCons:\n1. The authors focus on three candidate causes, which the authors claimed are principal (side-)effects of applying BPE: (i) removing redundancy in the data (due to compression), (ii) increase in the number of the unique units used to represent the data, or (iii) reducing the length of the training sequences. Other factors that are closely related to the BPE vocabulary may be also important, such as the subword frequency. Can the authors explain why the three factors examined in this paper are more likely the causes than other factors (e.g., subword frequency).\n2. Although the paper presents several interesting conclusions, they can not be directly used to determine a suitable vocabulary size in practical tasks, where the demand of the model's memorization is unknowable.\n\n\nConcerns:\n1. The conclusions in this study are only validated on the SNLI dataset (PAQ is only used for the training data recovery experiment), which may threat the universality of the findings. Experiments on other datasets and tasks (e.g. the machine translation task where Transformer was invented) are necessary.", "summary_of_the_paper": "This paper investigates the impact of subword vocabulary size on the memorization ability of Transformer models. The authors designed three types of tasks to evaluate the changes of model memorization, namely learning mappings with random labels, membership inference and training data recovery. Experimental results show that the memorization ability of Transformer model is stronger with the increase of subword vocabulary size, which the authors attribute to the reduction in the sequences' length.\n", "summary_of_the_review": "The research questions explored in the work are very interesting and important. However, the experiments are relatively weak, and it is not clear how to apply their findings in practical tasks.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "dy35ev9gB_V", "reviewer": "Reviewer_KAZC", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think this paper presents a thorough evaluation on how bep affects transformer’s memorization. My main concern is that their conclusion, shorter input sequences lead to better memorization, is drawn a bit hastily. The paper draws this conclusion indirectly by disproving the other two assumptions that they gave. However, are the 3 assumptions the only possible candidate theories? Or, are there ways to directly prove that it is the sequence length that makes a difference? One possible experiment can be, in the experiment of training data recovery, you train two different language models with the same data set, while for one you cut the long  input sentences into multiple short sequences (or concatenate sentences to make the input sequence longer), for the other you train the language model with the original data set. ", "summary_of_the_paper": "This paper as the name suggests, tries to figure out whether and through which ways bpe can affect Transformer’s memorization capacity. It evaluates Transformer’s memorization under these 4 settings: memorizing random synthetic data, memorizing random labeled natural language data, recognizing training data with lower output entropy, and training data recovery QA. Experiments show that if we have more merge times for bpe (larger vocabulary size), the model’s performance on all the four settings would improve on 3 architectures, which shows that bpe indeed can affect the model’s memorization capacity. Larger the vocabulary size is, the better the model would perform on memorizing. Then, the paper tries to figure out why more merges in bpe would lead to better memorization. By excluding two other hypotheses, the paper concludes that more merges in bpe results in shorter input sequence and that makes memorizing easier for transformers.", "summary_of_the_review": "Thorough empirical study on whether BPE affects memorization in transformers. While the final conclusion, shorter input sequences lead to better memorization, is not well supported by experiments.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "RXRHsv-x3aV", "reviewer": "Reviewer_saPE", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work is placed on the border for me as it is investigating well crafted question and does some empirical validation of multiple hypotheses. On the other hand, there is not much of discussion on what can we do with long sequences when we require memorization? Authors provide very high-level paths such as 'Our findings can provide guidance for tuning the learned data structures', but I would be very curious to read more details. I think it would nicely fit as findings paper rather than work with the novel contribution.\n\nWhen it comes to strengths, I like the construction of memorization properties which allows to quantify the memorization by using the proposed probing tasks. In addition, authors tried to provide many details on specific hyper-parameters they used, although I left some comments below where more details would be welcome.\n\nRegarding weaknesses: while the memorization properties are clearly outlined, the construction of model parameterization in probing tasks is written on very high-level without any discussion of why this specific method of casting the model as classifier is chosen and how it may or may not provide necessary information towards research questions about memorization, this is mainly addressing section 3.3).\nIn addition, authors mention 'SOTA \\ state of the art' several times during the work while they do not much relate to the actual SOTA models. Please correct me here if I am wrong, but considered models are not in the same ballpark as SOTA models. I want to stress that the latter fact is not a bad thing, but then there is no need to relate with SOTA then.\n\nBelow I have noted multiple comments where it was hard to me to get all the details or where I felt the minor change / addon would improve the presentation:\n\nPage 3, *\"At test-time, we prompt the trained LM by a query followed with the separator token and check whether the trained LM reproduces the correct answer within top-1 or top-5 results returned by beam search (beam size 5).\"* : This is very specific design choice, why did you choose it? Model conditioned on the q gives the entire distribution on sequence-level and beam search is very sensitive to the beam size? I see an alternative as doing unbiased sampling and computing expected similarity with the answer. Some discussion on that would help to clarify this.\n\nBottom of page 3: you used word *setups* to refer to both tasks and models (right?) which is a bit confusing.\n\nSection 3.3: as I wrote above, in my opinion this section needs to be larger as it defines very important design of the model parameterization, right now it is not even clear enough what are 'target class' in the context of vocabulary tokens? I believe explaining this would improve the presentation of that part a lot.\n\nPage 5: *achieves 100% train accuracy* : in cases of MLM, was acc measured only on task class prediction or on other masked tokens as well?\n\nPage 5: *Hence, in this experiment we used a 1-layer*:  Could you explain why you chose to reduce the model size? In my understanding the task itself might be too easy so the other way is to alter the underlying task (since you specifically construct it). \n\nPage 5: *which was enough for the training loss to converge*: Converge to what? Was there an early stopping criteria on loss or acc?\n\nPage 8: *Thus, if the vocabulary growth alone can explain the observed effect, we will see that the datasets with “duplicated” tokens would also be easier to memorize.* : In your proposed construction the frequency distribution of tokens doesn't change relatively to each other, right?. Is it the same for BPE learning when number of merges is growing? Would be great to show this, otherwise it is hard to buy this statement.", "summary_of_the_paper": "This paper studies the memorization properties of an NLP models conditioned on how large is the vocabulary size. They concentrate on widely used BPE algorithm in order to split original data into subword units. Further they construct a test-bed consisting on several tasks where each task is related with a specific memorization aspect connected to the model such as capacity or preference which authors introduced themself.\n\nExperiments empirically validate the change of memorization properties as the vocabulary size is changing where it exhibits better memorization with larger vocab size. Further authors make multiple hypotheses of what might be the underlying explanation hidden behind the improved memorization. After checking these out they conjecture that the reduced sequence length is likely the major contributor explaining the underlying observation.", "summary_of_the_review": "I set the score as marginally below the threshold given my concerns above where the main one is that the overall conclusions represents empirical findings without much of a contribution towards specific takeaways or practices which would be handy for the community. Nonetheless, I am open to discuss how this work can be positioned in this conference if there will be strong positive feedback from others.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper investigates the role of BPE and vocabulary sizes in memorization in transformer models. Through a series of experiments on random label prediction, training data recovery and membership inference attacks, the paper shows that larger vocabulary sizes lead to improved memorization. The Reviewers all agree that the paper investigates an important question and does so thoroughly. The main concerns were about: (1) the validity of the conclusion that it is sequence length indeed which affects memorization; and (2) the lack of more tasks to validate the findings. For (1) the authors added another set of experiments which further rule out frequency effects as a factor, but I agree with Reviewer KAZC that more evidence is needed which directly shows that sequence length is responsible (e.g. are shorter PAQ questions memorized better?). For (2) the authors shared a google drive link with additional results on NMT after the deadline, which the reviewers appreciated. Overall, however, the paper needs more work in order to unify all these results in a single draft.
Decision: Reject