Understanding the Mechanics and Dynamics of Memorisation in Large Language Models: A Case Study with Random Strings

We thank the reviewer for their feedback and interesting questions! We address them below.

Training process and dataset might not be representative of practical settings

It is true that we only train models to memorize a single random string at a time, a training setup that differs from the large quantities and diversity of training data seen by models during pre-training. Our approach of repeatedly training on the same data is, however, also gaining traction in recent work, to more effectively utilize data. Our choice of training setup is deliberate, as it allows us to ignore confounding factors such as the relative occurrence frequency of some random strings relative to other strings in the training data, and recency and forgetting due to other training data sequences. Studying these factors is potentially also very interesting, but merits its own separate analysis. Recent work by Tirumala et al. (2022) and Carlini et al. (2022) has explored some of these directions.

Are the investigated models representative of large language models?

In the paper, we already study a large variety of model sizes, from 140M to 12B parameters. To test generalization across models even more extensively, we added Llama 2 (7B and 13B) models to the revised paper (see discussion in Section 3.1 and Appendix A.3). Both the papers that introduced Pythia (e.g. Figure 4), as well as Llama 2, report emergent abilities. Therefore, we belive that these models are representative of other large language models. In our paper, we observe similar trends across all models, however, larger models are able to memorize faster, and this holds especially for the Llama 2 models. In contrast to the other models, we observe that they skip the guessing-phase completely and go straight to the memorization-phase. They can do this, because they are able to learn the token distribution in the string via in-context learning without additional training (see Appedix A.3). It is also worth noting that the Llama 2 7B model memorizes strings faster than the larger Pythia 12B model, indicating that other factors beyond parameter count also play a role.

We thank the reviewer for their thoughtful feedback and good questions! We address them below.

Some of the results are not surprising

Being able to uniquely predict the next token from short prefixes is only a necessary condition for the recollection accuracy we observe with short prefixes. It’s not clear a priori whether models will converge towards some information theoretically optimal solution. Models might memorize in several ways, and short prefixes are only one of them. Potential alternatives: models might form associations with longer prefixes (e.g. much more than 5 tokens in a 512 token string) as observed in other settings, or also with tokens not immediately adjacent to the target token (e.g. at the beginning or in the middle of the string), they might learn to detect the number of preceding tokens to do position-based memorization, etc. It's not clear which option(s) models will use without investigation. Other findings, such as the initial guessing-phase are also not necessarily expected. Why would a model first learn to associate prefixes with other tokens from the string's alphabet instead of trying to directly memorize the correct token, i.e. directly move into the memorization phase, since the latter reduces the loss even further? We added Llama 2 models to the revision of the paper and observe in Figure 1 (b) that they skip the guessing-phase completely and go straight to the memorization-phase. We show in Appendix A.3 that they are able to learn the token distribution in the string via in-context learning without additional training. This shows that the guessing phase does not happen automatically, but rather depends on the models’ ability to detect distributions via in-context learning.

There's insufficient evidence to challenge current notions of memorization

1. Token-level memorization: We discuss in the global response (3) why detecting memorization at the token-level may be more appropriate than at the string-level.
2. Role of context in associations: We show that besides the exact prefix of a token (or a string), the context in which it appears also matters for recollection. Therefore, when a model $m$ does not associate string $s$ with prefix $p$, it is not sufficient to conclude that $m$ has not memorized $p | s$, because given the right context $c$, which may not have ever appeared in the training data, $m$ might recollect s given $c | s$. As an example: given the prefix API_SECRET=, $m$ might not produce any private information in the training data, and thus one might conclude that the model has not memorized the secret. However, when adding additional context, such as the contents of a file with Python code making an API call to a cloud provider, even if that code has never appeared in that exact form in the training data, it is possible that $m$ might produce an API key for that cloud provider it has seen during its training. This context may be the document in which $p | s$ appeared during training, but it may also be different. Current notions of memorization ignore the context beyond the exact prefix.
3. Memorization/association strength: Even if a string has been memorized according to existing definitions of memorization, the implications of memorization can be very different depending on how frequently -- i.e. under how many contexts -- a model reproduces it. If a model only produces a memorized string in the context of the exact memorized source document, then the issue (or utility in the case of factual information) is less severe, but if the model produces a secret whenever API_SECRET= occurs, under a wide range of contexts, then this is a severe instance of memorization. Notions of memorization should take the strength/severity of memorization into account.

We thank the reviewer for their time and feedback. We address their concerns below.

The random string setting is not representative of natural language

See global response (1).

The existence of a guessing-phase is not surprising

The initial guessing phase is not necessarily expected. Why would a model first learn to associate prefixes with other tokens from the string's alphabet instead of trying to directly memorize the correct token, i.e. directly move into the memorization phase, since the latter reduces the loss even further? We added Llama 2 models to the revision of the paper and observe in Figure 1 (b) that they skip the guessing-phase completely and go straight to the memorization-phase. We show in Appendix A.3 that they are able to learn the token distribution in the string via in-context learning without additional training. This shows that the guessing phase does not happen automatically, but rather depends on the models’ ability to detect distributions via in-context learning.

Memorization in autoregressive/decoder-only models may behave differently from other types of models

In our paper we deliberately focus on autoregressive models. Autoregressive models are currently the most potent group of language models and are the most important models to study in the context of memorization, since due to their use for text generation they have a high propensity for leaking memorized private information, or for producing inaccurate outputs due to a lack of memorized facts. Many other recent papers also exclusively focus on this group of models. Studying bi-directional contexts would considerably increase the complexity of the analysis and warrant its own separate investigation.

Could you provide us with more details on why you believe that “The fact local context is sufficient more than global context may solely depend on the fact the model is autoregressive”? To us, it’s not clear that the autoregressive nature of models implies a local-context based memorization. In fact, autoregressive models might memorize in several plausible ways, and short prefixes are only one of them. Potential alternatives: models might form associations with longer prefixes (e.g. much more than 5 tokens in a 512 token string), or also with tokens not immediately adjacent to the target token (e.g. at the beginning or in the middle of the string), they might learn to detect the number of preceding tokens to do position-based memorization, etc. It's not clear which option(s) models will use without further investigation, which we provide in this work.

The memorization mechanics terminology may not be appropriate

See global response (2).

There's insufficient evidence to challenge current notions of memorization

See global response (3).

We thank the reviewer for their feedback and are glad they appreciate our work!

Practical impact

While the random string setting is not representative of many types of data models encountered in practice, we believe that our findings have practical implications for understanding and quantifying memorization in practice. For instance, as we discuss in the global response (1), a lot of sensitive data looks -- at least partially -- similar to random strings, such as API and SSH keys, passwords and usernames, phone numbers, URLs, social security numbers, etc. Therefore, memorization of such strings might happen in a similar manner to what we observe in the paper. Additionally, we discuss the implications of our results for detecting memorization in practice in global response (3). We argue that practitioners should not a priori assume a specific order of memorization and show that currently used memorization metrics can severely underestimate the degree of memorization of a piece of training data.

Unclear how to relate token- to string-level memorization (DC 17)

It is true that in a natural language settings, simply predicting a single token correctly, given some prefix from the training data, does not imply that that token (or a larger string that it is contained in) has been memorized, since the model could also predict that token using word statistics, grammar rules, etc. (e.g. “blue” in “The sky is blue.”). It is merely a necessary condition for memorization, but not a sufficient one. Current approaches to quantifying memorization using string-based notions (Carlini et al. (2022)) assume that if a sufficiently long string from the training data is predicted exactly, given its prefix, then it is very unlikely that this is due to something other than memorization (because predicting each token exactly as in the training data independently is highly improbable). By focussing on random strings in this study, we sidestep this issue. If models can predict the next token correctly, it has to be because of memorization. We discuss the implications of our findings for detecting memorization in the global response (3).

The memorization mechanics terminology may not be appropriate (DC 1)

See global response (2).

Other detailed comments

2. Disentangling entropy: To make sure that the behaviour we observe is indeed a result of the strings’ entropy, we conduct a control experiment in Appendix A.2 (mentioned in Section 3.1). We modify the entropy of strings with fixed alphabet size (26) by increasing the probability of sampling the first character (“a”) such that the generated strings have the same entropy as the strings with smaller alphabet size. Our results show the same patterns for different entropy levels at the same alphabet size as for different entropies due to different alphabet sizes. Due to space constraints, we could not include these results in the main paper.
3. We removed this part in the revised version.
4. We switched to using greedy decoding terminology.
5. We added examples with different alphabet sizes and entropies in Appendix A.4.
6. In most cases we train models only on single strings, but in Figure 8 we also train them on multiple strings at a time, so this depends on the specific experiment.
7. Good catch, 140M is correct, we corrected Figures 3-5 in the revision.
8. We do not use <BOS> tokens for GPT-2 and Pythia models. Figure 5a simply shows whether the token at the respective position has been predicted correctly at that timestep. The first column shows the prediction for the second token in the string, since the model does not produce a prediction for the first token (the output for the first token is the prediction for the second token). Please let us know if this doesn’t clarify the question.
9. We are driving the loss to zero over all tokens in the string at the same time. Alternative memorization dynamics are therefore also conceivable, such as memorizing tokens in chunks, from left to right, etc. We discuss the implications of this finding in the global response (3).
10. We moved details and takeaways into the Figure caption.

We thank the reviewer for their very detailed and thoughtful feedback! You are raising great points which are very helpful to improve the paper! We address them below.

Clarifying the string construction process

The vocabularies of the tokenizers used in this paper contain both tokens for individual characters, e.g. “a”, “b”..., as well as tokens spanning multiple characters, e.g. “abs”. By “character-level tokenization” we mean that we only use tokens corresponding to individual characters, not character sequences. To make this part clearer, we updated the terminology in the string construction process in the revised version of the paper. We refer to the elements of the alphabet as tokens and only use the term character if the alphabet tokens indeed correspond to the characters in the Latin alphabet.

The random string setting is not representative of natural language (DC 3, 14, 18)

See global response (1).

We should use structured synthetic data, i.e. probabilistic formal grammars (DC 16)

Using formal (probabilistic) grammars to create structured data is a great way to investigate how models learn to reason according to the grammar rules, and we are exploring this direction. We believe, however, that it is not directly suitable for understanding memorization. Intuitively, for a string to be memorized, a model must have seen and remembered it from its training data, there should not be any other way to generate it. We can achieve this with random strings, but if we generate data in a structured manner, models might produce valid strings by learning and using grammar rules, instead of memorizing the training strings.

Missing discussion of related work

Thank you for pointing out the relevant related work and the connection between our findings and those of Tirumala et al. (2022). We added the missing reference in the revised paper.

The work of Tirumala et al. (2022) and their findings about memorization order are indeed relevant in light of our observations about random memorization order. Their high-level message that different parts of text can be memorized at different speeds, and that memorization order is thus hard to predict matches our findings. However, we are skeptical about the soundness of some of their claims on memorization order. Their definition of memorization is problematic, since it considers any correctly predicted token $y$ following a prefix $s$ as memorized. However, it is likely that at least some correct predictions do not happen because of memorization, but rather because of other reasoning abilities that models are acquiring. Take for example "This morning I drank a", where models might correctly predict "coffee" without every having seen this sentence in their training data. Since their findings on differences in memorization order for different POS are based on this definition, we would approach them with caution and do not include a more extensive discussion. The difficulty of disentangling memorization and predictions made using other mechanisms is the core reason for restricting ourselves to random data in this paper, because in random strings, correct predictions can only be attributed to memorization, since there are no rules to derive the next token from. We would like to point out, though, that we think studying memorization at the token-level, rather than string-level, is more appropriate (see global response (3)), but inferring memorization from just a single correctly predicted token seems highly optimistic. A more robust measure should check whether a reasonably large fraction of tokens in a sufficiently long string postfix are correctly predicted.

Results on short prefix recollection are not surprising (DC 14)

Being able to uniquely predict the next token from short prefixes is only a necessary condition for the recollection accuracy we observe with short prefixes. It’s not clear a priori whether models will converge towards some information-theoretically optimal solution. Models might memorize in several ways, and short prefixes are only one of them. Potential alternatives: models might form associations with longer prefixes (e.g. much more than 5 tokens in a 512 token string) as observed in other settings, or also with tokens not immediately adjacent to the target token (e.g. at the beginning or in the middle of the string), they might learn to detect the number of preceding tokens to do position-based memorization, etc. It's not clear which option(s) models will use without further investigation, which we provide in this paper.

Thanks for the response! The paper is a lot clearer now. I will retain my score (explanation below), but won't oppose acceptance if other reviewers champion for it.

All of my remarks regarding clarity/presentation have been resolved. The remaining doubt I have is still the one on whether results on random strings will be relevant to the community. Re: the point on probabilistic formal grammars ("We can achieve this with random strings, but if we generate data in a structured manner, models might produce valid strings by learning and using grammar rules, instead of memorizing the training strings."), formal grammars allow for primitives that are more than one character long, which still lets you have smaller random substrings within the string.

An example:

e.g.

S | A B

A | [random string sampling one subset of the vocab]

B | [random string sampling another subset of the vocab]`

(2) The memorization mechanics terminology may not be appropriate

We call some of our findings mechanics, because (similar to physics) they can be used to explain and predict the dynamics, e.g. differences in memorization speed for strings of the same length and different alphabet sizes because models need to learn associations with prefixes of different lengths, different splits of the same string having almost the same memorization speed, because models learn the same prefix mappings, etc. We argue that you can model the mechanics of a system at multiple levels (e.g., classical vs. statistical vs. quantum mechanics in physics). In this work, we are concerned with the mechanics at the level of (latent) mappings learned by the LLM, i.e. based on how the outputs of models correspond to their inputs, in the context of random string memorization. We show distinct roles that the exact prefixes and the remaining context play. In addition to the input-output level dynamics, there are also lower-level dynamics, which is often what mechanistic interpretability is concerned with. An analogy for multi-level dynamics in physics would be the mechanics of a spring. Its behaviour can be modelled and explained at a high-level (how much does some amount of force stretch the spring) or at an internal level (how is the atomic lattice structure of the sprint deformed by applying the force) and also at the level of quantum-mechanics (how do atoms in the sprint interact). All of these are different levels of studying mechanics of the same object. We focus on the higher-level mechanics here.

(3) Why studying memorization at the token-level (rather than the string-level) may be more appropriate

Our results caution against a priori assuming specific memorization patterns. Prior work on quantifying memorization (Definition 3.1 in Carlini et al (2022)) implicitly assumes memorization in a block contiguous structure. Such a definition may be too strict and may fail to detect largely memorized strings, even if just a few tokens within a string are not fully memorized. We include experiments in the revised version of the paper in Appendix C.2 that show that, indeed, the aforementioned string-based metric only detects a small fraction of substrings of almost completely memorized 1024 random token strings as memorized. Detecting memorization at the token-level provides a better picture of the actual degree of memorization. A simple way of using our insights to improve the detection of memorized strings in practice therefore would be to count the number of (not necessarily adjacent) correctly recollected tokens in a string, given prefixes from the same string. The higher the fraction of correctly predicted tokens, the more likely it is that the model has memorized (parts of) the string. This may be more robust than requiring that the entire string is reproduced correctly by the model without gaps.