Finding Memo:
Extractive Memorization in Constrained Sequence Generation Tasks

Previous studies Arpit et al. (2017); Feldman (2020); Zhang et al. (2021a) have shown that neural networks capture regular patterns in the training data (generalization) while simultaneously fitting noisy and atypical samples using brute-force (memorization). For constrained Natural Language Generation tasks such as Neural Machine Translation (NMT), which rely heavily on noisy (web crawled) data for training high-capacity neural networks, this creates an inherent reliability problem. For example, memorizations could manifest themselves in the form of catastrophic translation errors on specific samples despite high average model performance Raunak et al. (2021). It is also likely that the memorization of a specific sample could corrupt the translations of samples in its vicinity. Therefore, exploring, quantifying and alleviating the impact of memorization is of critical importance for improving the reliability of such systems.

Yet, most of the work on memorization in natural language processing (NLP) has focused either on classification Zheng and Jiang (2022) or on unconstrained generation tasks, predominantly language modeling Carlini et al. (2021); Zhang et al. (2021b); Kharitonov et al. (2021); Chowdhery et al. (2022); Tirumala et al. (2022); Tänzer et al. (2022); Haviv et al. (2022). In this work, we fill a gap in the literature by developing an analogue of extractive memorization for constrained sequence generation tasks in general and NMT in particular. Our main contributions are:

1. 1.

   We propose a new, inexpensive algorithm for studying extractive memorization in constrained sequence generation tasks and use it to characterize memorization in NMT.

2. 2.

   We demonstrate that extractive memorization poses a serious threat to NMT reliability by quantitatively and qualitatively analyzing the memorized samples and the neighborhood effects of such memorization. We also demonstrate that the memorized instances could be used to generate errors in disparate systems.

3. 3.

   Based on an analysis of the neighborhood effects of memorization, we develop a simple memorization mitigation algorithm which produces non-memorized (higher quality) outputs for a large fraction of memorized samples.

4. 4.

   We show that the outputs produced by the memorization mitigation algorithm could also be used to directly impart corrective behavior into the model through finetuning.

Our work is concerned with the phenomenon of memorization in constrained natural language generation in general and NMT in particular. The main challenge in analyzing memorization is to determine which samples have been memorized by the model during training. There exist two key algorithms to elicit memorized samples, each yielding a distinctive operational definition of memorization:

1. 1.

   Counterfactual Memorization: Feldman and Zhang (2020) study label memorization and propose to estimate the memorization value of a training sample by training multiple models on different random subsets of the training data and then measuring the deviation in the sample’s classification accuracy under inclusion/exclusion. This definition of memorization was further extended to arbitrary performance measures by Raunak et al. (2021) to study memorization in NMT and by Zhang et al. (2021b) to study memorization in language models. However, a practical limitation of analysis based on this definition is the prohibitive computational cost (multiple model trainings) associated with computing memorization values for each training sample.

2. 2.

   Extractive Memorization: Carlini et al. (2021) propose a data-extraction based definition of memorization to study memorization in language models. Therein, a training string $s$ is extractable if there exists a prefix $c$ that could exactly generate $s$ under an appropriate sampling strategy (e.g. greedy decoding). This definition has the benefit of being computationally inexpensive, although it doesn’t have any existing analogue for constrained natural language generation tasks such as NMT.

In the next section, we define extractive memorization for constrained sequence generation tasks and apply it to NMT, in section 4 we estimate the neighborhood effect of such memorizations and in section 5 we propose a simple algorithm for recovering correct translations of memorized samples.

We present our definition of extractive memorization as Algorithm 1. Analogous to extractive memorization in language models Carlini et al. (2021), this definition labels an input sentence (source) as being memorized if its transduction (translation) could be replicated exactly with a prefix considerably shorter than the length of the full input sentence (source), under greedy decoding. Operationally, we set prefix ratio threshold ($p$) to $0.75$.

Next, we apply this definition of memorization on a strong Transformer-Big Vaswani et al. (2017) baseline trained on the 48.2M WMT20 En-De parallel corpus Barrault et al. (2020). We describe the dataset, model and training details in Appendix A.

Qualitatively, we observe that the memorized samples detected by Algorithm 1 mostly consist of low-quality samples – templatized source sentences and noisy translations. To analyze the results quantitatively, similar to Carlini et al. (2022), we bucket the training data pairs in terms of their repetitions in the training data. Owing to the sparsity of data with greater than 5 repetitions we report results in the range of 1-5 repetitions. Further, for repetition values 1 and 2, we select 100K random samples for analysis. We observe two key results:

Repetitions vs Memorization: Table 1 shows that the percentage of samples memorized is higher for repeated training samples, compared to samples present only once in the training data, with a Pearson’s correlation coefficient of 0.778 between the number of repetitions and memorizations.

Quality of Memorized Samples: Table 3 shows that both the quality of memorized samples, measured using COMET-QE Rei et al. (2020), a state-of-the-art Quality Estimation model for MT as well as their lexical diversity, measured using Type-to-Token Ratio (TTR) Vanmassenhove et al. (2021); Gehrmann et al. (2022) is worse when compared to the total samples.

The above two results are similar to the results in language modeling Carlini et al. (2022) and serve to demonstrate the utility of Algorithm 1 in analyzing extractive memorization in NMT.

To measure the neighborhood effect of memorization, we generate new source sentences in the vicinity of the memorized samples through perturbations and test whether they generate the same output under greedy decoding. Table 2 shows a memorized training sample from Section 3, alongside translations generated from perturbations at different positions in the source. The perturbations (substitutions) were generated using BERT-Cased Devlin et al. (2019). We define suffix positions and prefix positions based on the recorded prefix lengths ($L$) in Algorithm 1. Specifically, we use Algorithm 2, which generates new sources in the neighborhood of a memorized input source by perturbing its tokens at prefix ($P$), suffix ($S$) or the beginning ($B$) positions and then computes how many such new sources still translate to the same memorized output. The resulting effect measure $N$ is higher if the sources still produce the same memorized output under perturbations at different positions. The intuition behind Algorithm 2 is that we want to explore meaningful source sequences around the memorized source sentence. Therefore, we make changes to only a single position at a time, to keep the generated sequence close to the original sequence and substitute that position with a word that fits well in the particular context. Our ‘neighbour’ definition is loosely inspired by the differential privacy literature Dwork et al. (2014), where a neighbour is used to mean datasets differing in only one item.

Results: The last 3 columns of Table 1 present the results of applying Algorithm 2 on memorized sources ($K$=5). We find that considerable percentages of perturbations still yield the same translations, and that this effect is highly position-dependent. For example, for the unique memorized samples (repetitions = 1), perturbing the suffix produces no changes in translations for 43.2% of the new sources; while for prefix perturbations the same memorized output is produced only 17.6%. Further, perturbing the first token of the source is highly successful in generating a different (non-memorized) output. The results demonstrate that a single memorization may therefore be able to corrupt the translations of multiple input sequences in its vicinity.

Table 1 and 2 show that while the translations of memorized sources frequently remain invariant under suffix perturbations, translations under prefix-perturbations do change more frequently. We hypothesize that this results from the model switching away from its memorization mode, owing to a change in the input prefix used for memorization.

The results in section 4 (and table 2) show that the model is able to generate non-memorized translations quite frequently if memorized source’s start token is perturbed. We demonstrate that this fact could be exploited to recover the non-memorized translations of a memorized sample from the same model with a surprisingly high-frequency. We call this task Memorization-Mitigation and present a simple technique to do so in Algorithm 3.

Algorithm 3 uses the idea of prefix perturbation to elicit a non-memorized translation from the model. As a perturbation, it appends a symbol $X$ to the source sentence, which is chosen such that it could be translated in isolation, without semantically altering the source. We find that new translations for 65.2% of the memorized samples in Table 1 (339/520) could be recovered using Algorithm 3 with symbol $X$ set to ‘!’. We find that the results vary with different choices of symbol $X$ and report the best result after trying 5 different symbols. An example of applying Algorithm 3 on a memorized sample is presented in Figure 1.

Further, we find that the new (non-memorized) translations are of much higher quality than the memorized outputs. Table 5 presents the results by comparing the new translations to the memorized translations using COMET-QE and TTR.

The previous section demonstrated that the non-memorized translations of memorized samples could be recovered from the same model by applying Algorithm 3. In this section, we investigate whether this corrective behavior could directly be imparted to the model through finetuning using the corpus $F$ obtained by applying Algorithm 3.

To test this, we finetune the last checkpoint of the trained WMT20 model for one epoch on approximately 10K data pairs, comprising of 10K parallel data samples drawn randomly from the training corpus as well as the corpus F. We compare the model prior to and post finetuning, in terms of both general performance on the WMT20 test set with BLEU Papineni et al. (2002); Post (2018) and on the corpus $F$ with COMET-QE. Table 5 shows that given the non-memorized translations, such corrective behavior could be imparted to the model without impacting general quality.

Further Experiments: Throughout sections 3-6, we have used the trained WMT20 En-De system to conduct various experiments exploring extractive memorization. However, the reported phenomena are quite general in nature, observable across different language pairs, systems and datasets; the results for other experiments are presented in Appendix D. Further, we note that to apply Algorithms 1 and 2 across language pairs, certain changes are required:

1. 1.

   For character-based languages such as Chinese, Japanese, Korean and Thai (CJKT), the Prefix Lengths ($L$) in Algorithm 1 should be measured in characters, unlike whitespace-based tokens in the general case.

2. 2.

   For non-English source language, multilingual BERT (or other comparable multilingual MLMs) should be used for generating the Neighbours ($S^{{}^{\prime}}$) in Algorithm 2.

In the next two sections, we delve into the implications of extractive memorization and its apparent data-dependency, towards NMT reliability.

In this section, we show how the proposed extractive memorization algorithm could be used to construct potential attacks on state-of-the-art (SOTA) MT systems. Our motivation here is to provide an existence proof of the statement that the data dependency of extractive memorization makes it a transferable phenomenon, which could be leveraged to attack disparate systems. As such, we name the attack designed to elicit erroneous generations on System B, based on memorized data extracted from System A, a Transferable Memorization Attack (TMA). Further, successful Transferable Memorization Attacks should signify spurious correlations which could be easily learned from the underlying common data distribution. Therefore, TMA could be characterized as a data poisoning attack Biggio et al. (2012) and its existence would point to shared vulnerabilities in NMT systems.

Experiment: We feed the memorized samples obtained from the system in section 3 to two public systems, namely Google Translator and Microsoft Bing Translator. We find that it is indeed possible to elicit erroneous, memorized translations from these SOTA systems using the memorized inputs identified from our WMT20 model. We present two such examples in Table 8 in Appendix B.

In this section, we list some questions which require further investigation to gain more insights into extractive memorization and its effects.

In this work, we developed the idea of extractive memorization for constrained sequence generation tasks and quantitatively demonstrated that such memorization poses a real threat to NMT reliability. We also proposed an algorithm to generate non-memorized outputs for such samples. To the best of our knowledge, our work is the first investigation of extractive memorization for constrained sequence generation tasks in general. We hope that our work serves as a useful step towards further research on extractive memorization in constrained sequence generation tasks & NMT.

We thank Matt Post and Marcin Junczys-Dowmunt for helpful early discussions. We thank Huda Khayrallah, Matt Post, and Hai Pham for providing detailed feedback on the original manuscript.

Throughout the work, we emphasized on exploring and mitigating memorization without the help of data filtering techniques and did not compare memorizations for models trained under different data-filtering algorithms. We believe this direction to be very relevant but orthogonal to our work in this paper. Further, since our work presents the first algorithm on memorization mitigation, we believe it doesn’t represent an optimal approach for the task. For example, one immediate extension of the algorithm would be to use multiple symbols instead of just one symbol.