Understanding the Interplay between Memorization and Learning in Large Language Models

The gist: Memorization measures disagree on memorization order, and optimal learning of a language cannot avoid partial memorization of training strings, while improved learning decreases contextual and counterfactual memorization but increases recollection-based memorization.

Memorization Measures

The paper re-examines existing privacy-focused measures of memorization, namely recollection-based and counterfactual memorization, along with a newly proposed contextual memorization to disentangle memorization from the contextual learning ability of LLMs. Recollection-based measures are motivated by privacy concerns and operationalized by how well an LLM can recollect training strings using cross-entropy loss as the recollection loss of generating each token in the string. This measure uses a predefined threshold τ to determine memorization, where s starts to be memorized at epoch e = e rec s when loss(Me, s). The paper finds that recollection-based measures are error-prone due to arbitrarily chosen thresholds, as the choice has consequences on the interpretation of memorization.

Contextual Memorization

Contextual memorization is proposed to disentangle memorization from contextual learning by introducing a threshold, called the optimal contextual recollection, which is defined as the best possible extent of recollecting s from its context by learning the underlying language L without explicitly training on s. A string s is contextually memorized if its recollection due to training exceeds the optimal contextual recollection of the string. The key intuition is that for each string s in the training dataset D, we first estimate the optimal contextual recollection – obtained by repeatedly training over a dataset D′ that excludes s from D. Contextual memorization starts at an epoch e = e ctx s when loss(Me(D), s). This measure is stricter than counterfactual memorization, and the contextual memorization score is a lower bound of the counterfactual memorization score.

Counterfactual Memorization

Counterfactual memorization is inspired by differential privacy and captures the divergence in recollection performance over D and D′ at each training epoch. A string s is counterfactually memorized if the LLM can accurately recollect s only when it is included in training, meaning that at each training epoch, counterfactual memorization reflects the difference in the model’s loss on s with and without s in the training dataset. It starts at an epoch e = e cf s when loss(Me(D), s). The memorization score is defined as memcf(s, e, D) ≜ loss(Me(D′), s) − loss(Me(D), s) / loss(Me (D′), s)>. Counterfactual measures can overstate memorization compared to contextual memorization.

Learning-Memorization Trade-offs

The paper addresses the question of whether learning a language without memorizing any strings is feasible, arguing that it is infeasible because every string s in L has its own training epoch es, when it starts to be memorized and these vary significantly across different strings. The key underlying intuition is that the training epoch e∗ corresponding to globally optimal learning often occurs after some (and often many) strings have been memorized.

The study demonstrates that optimal learning is achieved by a nonzero memorization score, as shown in Figure 3c and 3d, which answers RQ3 affirmatively to the question of whether memorization is unavoidable for optimal learning in both high and low entropy languages. Furthermore, improved learning by increasing training data decreases contextual and counterfactual memorization but increases recollection-based memorization. This reveals that the trade-off between memorization and learning becomes subjective to the choice of memorization measure, where a trade-off exists in recollection-based memorization, but not in contextual and counterfactual memorization.

Implications for Privacy

The paper revisits strings reported as memorized by recollection measures to answer RQ6 and RQ7 regarding privacy risks. The analysis shows that most memorized strings do not contain any privacy-sensitive personally identifiable information (PII), answering negatively to RQ6. Moreover, predictable memorized strings via recollection are unlikely to be contextually or counterfactually memorized, as the reference model OLMo-1B recollects 52.39% of them with ≥ 90% accuracy. This suggests that recollection-based measures may exaggerate the memorization risks posed by LLMs.

Conclusion

The study concludes that learning a language optimally without some degree of memorization is infeasible in current LLM training dynamics, and existing threats of memorization are often exaggerated. The paper advocates for a nuanced understanding of these measures before applying them in practice, suggesting that contextual or counterfactual memorization should be applied due to their stricter criteria and better alignment with learning objectives.

How it works

The experimental setup involves training an LLM on strings from a formal language, focusing on learning syntactic patterns defined by a formal grammar. The models are trained over multiple epochs, and the goal is to answer two questions for each string s in D: RQ1 (Memorization Detection Question) at what epoch es does M start to memorize s? and RQ2 (Memorization Score Question) What is the degree of memorization or memorization score, mem(s, e) ∈ [0, 1], of string s at an epoch e ≥ es >. The experiment uses 18 open-source LLMs from 6 families and multiple formal languages of different entropy.

Operationalizing Memorization Notions

The paper operationalizes three distinct notions of memorization:

(a) Recollection-based Memorization: This is operationalized using cross-entropy loss as the recollection loss, where s starts to be memorized at epoch e = e rec s when loss(Me, s). The memorization score is binary: memrec(s, e) ≜ 1(loss(Me, s).

(b) Counterfactual Memorization: This measure compares loss(Me(D), s) and loss(Me(D′), s), where D′ = D excluding s from training. A string starts to be counterfactually memorized at epoch e = e cf s when loss(Me(D), s). The score is memcf(s, e, D) ≜ loss(Me (D′), s) − loss(Me (D), s) / loss(Me (D′), s)>.

(c) Contextual Memorization: This is motivated from the perspective of learning as opposed to privacy concerns, where a training string s is contextually memorized if its recollection due to training exceeds the optimal contextual recollection of the string. The optimal contextual loss of a string is mine∗ loss(Me∗ (D′), s), which is the lowest counterfactual test loss of s in all epochs >. Contextual memorization starts at an epoch e = e ctx s when loss(Me(D), s). The score is memctx(s, e, D) ≜ mine∗ loss(Me∗ (D′), s) − loss(Me (D), s) / mine∗ loss(Me∗ (D′), s)>.

Challenges with Operationalizations

Recollection-based memorization is the simplest, needing only the trained LLM and the target string, but counterfactual and contextual memorization require access to the training dataset. Computationally, recollection-based measures have the lowest cost, but counterfactual and contextual measures require retraining the LLM separately without each target string, making them computationally expensive. The paper proposes an efficient approximation that avoids retraining by using similarly occurring strings in a formal language to estimate test loss as counterfactual test loss and the lowest counterfactual test loss as the optimal contextual loss >.

Contradictions Among Measures

Different measures yield conflicting conclusions for the same training dynamic. Recollection-based measures are strongly correlated with occurrence frequency of strings, where more frequent strings are memorized earlier. In contrast, counterfactual and contextual measures are uncorrelated and at times inversely correlated with occurrence frequency of strings. Contextual memorization is a stricter measure than counterfactual memorization, meaning it applies a higher recollection threshold (or lower loss threshold) than counterfactual memorization.

Trade-offs in Learning

The paper investigates the trade-off between memorization and learning by examining RQ3, RQ4, and RQ5. It answers RQ3 by showing that memorization is unavoidable for optimal learning, both in high and low entropy languages. It answers RQ4 by observing a contradiction where recollection-based measures identify frequent strings as more likely to be memorized than contextual and counterfactual measures do.

1. textbfThe contextual memorization measure distinguishes between memorization and contextual learning by defining it as a threshold based on optimal recollection, stating: a training string s is contextually memorized if its recollection due to training exceeds the optimal contextual recollection. This allows systems to disentangle memorization from the contextual learning ability of LLMs, which helps in understanding generalization versus rote learning.

2. textbfThe study demonstrates that different memorization measures yield conflicting conclusions, specifically noting that recollection-based memorization is error-prone due to arbitrarily chosen thresholds, urging caution against using it as the sole target for mitigation efforts because recollection measures, while easy to use, can lead to misleading conclusions.

3. textbfThe proposed contextual and counterfactual measures are stricter than recollection-based ones; specifically, Contextual memorization is stricter than counterfactual memorization, and contextual memorization score is a lower bound of the counterfactual memorization score. This suggests that focusing on these measures provides more reliable assessments of potential privacy risks, as they are less vulnerable to subjective threshold choices.

4. textbfModel training should aim for optimal learning rather than avoiding all memorization, as the paper concludes: learning a language without memorization is infeasible, and memorization is unavoidable for optimal learning. This shifts the focus from attempting to eliminate memorization entirely to managing its impact on generalization, recognizing that improved learning increases recollection-based memorization.

5. textbfThe study provides a computational heuristic for approximate counterfactual and contextual memorization by proposing: "If the occurrence frequency of both training and test strings are known in a training dynamic, which is the case of a formal language, we can find a test string as similarly occurring to the training string, and use its test loss as counterfactual test loss and the lowest counterfactual test loss as the optimal contextual loss." This makes privacy-focused measures practical by avoiding computationally expensive retraining.

6. textbfThe analysis shows that Frequent and infrequent strings are almost equally susceptible to contextual and counterfactual memorization, but not to recollection-based memorization, indicating that systems should prioritize these measures when assessing susceptibility across different string frequencies rather than relying on frequency alone for privacy risk assessment.

We investigate foundational questions about the interplay between memorization and learning in large language models (LLMs). When an LLM generates a string, can we disentangle the roles of rote memorization and contextual learning? Rote memorization results in an LLM regurgitating specific details of a training string, while contextual learning leads to the generation of new strings that follow generalizable patterns of the underlying language. Related questions of interest include: can an LLM avoid memorization when optimally learning a language?, and if not, can we design training schemes to reduce memorization and improve learning? To address these questions, we propose contextual memorization, a new measure that precisely disentangles memorization from learning. Using this measure, we establish that different training strings are memorized at different epochs in training, and that memorization of some training strings is unavoidable when optimally learning a language. Finally, we propose memorization-aware training, a scheme that dynamically down-samples training strings based on their memorization, and in doing so, equalizes learning across strings, reduces memorization, and improves learning. Our conclusions are supported by extensive experiments on multiple LLMs using formal languages as a controlled testbed, enabling precise language specification, exact string sampling, and elimination of data contamination; and further validated on natural languages.