Rethinking LLM Memorization through the Lens of Adversarial Compression

Authors: avi  schwarzschild
zhili  feng
pratyush  maini
zachary c lipton
j  zico kolter
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 19:46:12

Abstract: Large language models (LLMs) trained on web-scale datasets raise substantial concerns regarding permissible data usage. 
One major question is whether these models "memorize" all their training data or they integrate many data sources in some way more akin to how a human would learn and synthesize information. The answer hinges, to a large degree, on \emph{how we define memorization.} In this work, we propose the Adversarial Compression Ratio (ACR) as a metric for assessing memorization in LLMs. A given string from the training data is considered memorized if it can be elicited by a prompt (much) shorter than the string itself---in other words, if these strings can be ``compressed'' with the model by computing adversarial prompts of fewer tokens. The ACR overcomes the limitations of existing notions of memorization by (i) offering an adversarial view of measuring memorization, especially for monitoring unlearning and compliance; and (ii) allowing for the flexibility to measure memorization for arbitrary strings at a reasonably low compute. Our definition serves as a practical tool for determining when model owners may be violating terms around data usage, providing a potential legal tool and a critical lens through which to address such scenarios.

Main paper: 
 introduction: 
 A central question in the discussion of large language models (LLMs) concerns the extent to which they memorize their training data versus how they generalize to new tasks and settings. Most practitioners seem to (at least informally) believe that LLMs do some degree of both: they clearly memorize parts of the training data-for example, are often able to reproduce large portions of training data verbatim [Carlini et al., 2023] -but they also seem to learn from this data, allowing them to generalize to new settings. The precise extent to which they do one or the other has massive implications for the practical and legal aspects of such models [Cooper et al., 2023] . Do LLMs truly produce new content, or do they only remix their training data? Should the act of training on copyrighted data be deemed unfair use of data, or should fair use be judged by the model's memorization? With respect to people, we distinguish plagiarising content from learning from it, but how should this extend to LLMs? The answer to such questions inherently relates to the extent to which LLMs memorize their training data.However, even defining memorization for LLMs is challenging and many existing definitions leave a lot to be desired. Certain formulations claim that a passage from the training data is memorized if the LLM can reproduce it exactly [Nasr et al., 2023] . However, this ignores situations where, for instance, a prompt instructs the model to exactly repeat some phrase. Other formulations define memorization by whether or not prompting an LLM with a portion of text from the training set results in the completion of that training datum [Carlini et al., 2023] . But these formalisms rely fundamentally on the completions being a certain size, and typically very lengthy generations are required for sufficient certainty of memorization. More crucially, these definitions are too permissive because they ignore situations where model developers can (for legal compliance) post-hoc "align" an LLM by instructing their models not to produce certain copyrighted content [Ippolito et al., 2023] . But has such an instructed model really not memorized the sample in question, or does the model still contain all the information about the datum in its weights while it hides behind an illusion of compliance? Asking such questions becomes critical because this illusion of "unlearning" can often be easily broken as we show in Sections 4.1 and 4.3.In this work, we propose a new definition of memorization based on a compression argument. Our definition posits that a phrase present in the training data is memorized if we can make the model reproduce the phrase using a prompt (much) shorter than the phrase itself. Operationalizing this definition requires finding the shortest adversarial input prompt that is specifically optimized to produce a target output. We call this ratio of input to output tokens the Adversarial Compression Ratio (ACR). In other words, memorization is inherently tied to whether a certain output can be represented in a compressed form, beyond what language models can do with typical text. We argue that such a definition provides an intuitive notion of memorization-if a certain phrase exists within the LLM training data (e.g., is not itself generated text) and it can be reproduced with fewer input tokens than output tokens, then the phrase must be stored somehow within the weights of the LLM. Although it may be more natural to consider compression in terms of the LLM-based notions of input/output perplexity, we argue that a simple compression ratio based on input/output token counts provides a more intuitive explanation to non-technical audiences, and has the potential to serve as a legal basis for important questions about memorization and permissible data use.In addition to its intuitive nature, our definition has several other desirable qualities. We show that it appropriately ascribes many famous quotes as being memorized by existing LLMs (i.e. they have high ACR values). On the other hand, we find that text not in the training data of an LLM, such as samples posted on the internet after the training period, are not compressible, that is their ACR is low.We examine several unlearning methods using ACR to show that they do not substantially affect the memorization of the model. That is, even after explicit finetuning, models asked to "forget" certain pieces of content are still able to reproduce them with a high ACR-in fact, not much smaller than with the original model. Our approach provides a simple and practical perspective on what memorization can mean, providing a useful tool for functional and legal analysis of LLMs.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: Section 4Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
do we really need another notion of memorization?: 
 With LLMs ingesting more and more data, questions about their memorization are attracting attention [e.g. Carlini et al., 2019 , 2023 , Nasr et al., 2023 , Zhang et al., 2023] . There remains a pressing need to accurately define memorization in a way that serves as a practical tool to ascertain the fair use of public data from a legal standpoint. To ground the problem, consider the court's role in determining whether an LLM is breaching copyright. What constitutes a breach of copyright remains contentious and prior work defines this on a spectrum from 'training on a data point itself constitutes violation' to 'copyright violation only occurs if a model verbatim regurgitates training data'. To formalize our argument for a new notion of memorization, we start with three definitions from prior work to highlight some of the gaps in the current thinking about memorization. Definition 1 (Discoverable Memorization [Carlini et al., 2023] ). Given a generative model M , a sample y from the training data made of a prefix y prefix and a suffix y suffix is discoverably memorized if the prefix elicits the suffix in response, or M (y prefix ) = y suffix .Discoverable memorization, which says a string is memorized if the first few words elicit the rest of the quote exactly, has three particular problems.1. Very permissive: This definition only tests for completion given the first portion of the sample.Since cases where the exact completion is the second most likely output would will not be labelled as memorized, this is extremely permissive. 2. Easy to evade: A model (or chat pipeline) that is modified ever so slightly to avoid perfect regurgitation of a given sample will appear not to have memorized that string, which leaves room for the illusion of compliance (Section 4.1). 3. Parameter choice requires validation data: We need to choose several words (or tokens) to include in the prompt and a number of tokens that have to match exactly in the output to turn this definition into a practical binary test for memorization. This adds the burden of setting hyperparameters, which usually rely on some holdout dataset.In other words, this completion-based test is too conservative to capture memorization when model owners may take steps to make it look like their model has not memorized certain data. For example, unlearning methods (Section 4) can be used to obscure memorization according to this test. Our definition, which relies on optimization and not completion alone, is not fooled by these minor tricks to appear compliant. Definition 2 (Extractable Memorization [Nasr et al., 2023] ). Given a generative model M , a sample y from the training data is extractably memorized if an adversary, without access to the training set, can find an input prompt p that elicits y in response, or M (p) = y.A string is extractably memorized if there exists a prompt that elicits the string in response. This falls too far on the other side of the issue by being very restrictive-what if the prompt includes the entire string in question, or worse, the instructions to repeat it? LLMs that are good at repeating will follow that instruction and output any string they are asked to. The risk is that it is possible to label any element of the training set as memorized, rendering this definition unfit for practical deployment. Definition 3 (Counterfactual Memorization [Zhang et al., 2023] ). Given a training algorithm A that maps a dataset D ⊂ D to a generative model M and a measure of model performance S(M, y) on a specific sample y, the counterfactual memorization of a training example y ∈ D is given by:mem(y) := E D⊂D,y∈D [S(A(D), y)]performance on y when trained with y Counterfactual memorization aims to separate memorization from generalization and requires a test that includes retraining many models. Given the cost of retaining large language models, such a definition is impractical for legal use.-E D ′ ⊂D,y̸ ∈D ′ [S(A(D ′ ), y)]In addition to these definitions from prior work on LLM memorization, there are two other seemingly viable approaches to memorization. Ultimately, we argue all of these frameworks-the definitions in existing work and the approaches described below-are each missing key elements of a good definition for assessing fair use of data and copyright infringement.Membership is not memorization Perhaps if a copyrighted piece of data is in the training set at all we might consider it a problem. However, there is a subtle but crucial difference between training set membership and memorization. In particular, the ongoing lawsuits in the field [e.g. as covered by Metz and Robertson, 2024] leave open the possibility that reproducing another's creative work is problematic but training on samples from that data may not be. This is common practice in the arts-consider that a copycat comedian telling someone else's jokes is stealing, but an up-and-comer learning from tapes of the greats is doing nothing wrong. So while membership inference attacks (MIAs) [e.g. Shokri et al., 2017] may look like tests for memorization and they are even intimately related to auditing machine unlearning [Carlini et al., 2021 , Pawelczyk et al., 2023 , Choi et al., 2024] , they have three issues as tests for memorization.1. Very restrictive: LLMs are typically trained on trillions of tokens. Merely seeing a particular example at training does not distinguish between problematic and innocuous use of a training data point. Akin to plagiarism, it is okay to read copyrighted books, but copying is problematic. 2. Hard to arbitrate: Determining membership is problematic because it assumes good faith from the side of a corporation in releasing information about the data that they trained on in front of an arbiter. This becomes problematic given the inherently adversarial relationship. 3. Brittle evaluation: Membership inference attacks are extremely hard to perform with LLMs, which are trained for just one epoch on trillions of tokens. Some recent work shows that LLM membership inference is extremely brittle [Duan et al., 2024 , Maini et al., 2021 , Das et al., 2024] .Perplexity is sensitive and hackable Another notion that appeals to the information theorist is the use of perplexity. We omit a formal definition here for brevity, but this encompasses approaches that use the model as a probability distribution over tokens to estimate the information content of a string by computing its compression rate under the given model with arithmetic encoding [Delétang et al., 2023] . Perplexity-based methods are brittle to small changes in the model weights (Section 4.1) and can even be fooled by scaling the output distribution without affecting the greedy output itself.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: Section 5Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
how to measure memorization with adversarial compression: 
 Our definition of memorization is based on answering the following question: Given a piece of text, how short is the minimal prompt that elicits that text exactly? In this section, we formally define and introduce our MINIPROMPT algorithm that we use to answer our central question.To begin, let a target natural text string s have a token sequence representation x ∈ V * which is a list of integer-valued indices that index a given vocabulary V. We use | • | to count the length of a token sequence. A tokenizer T : s → x maps from strings to token sequences. Let M be an LLM that takes a list of tokens as input and outputs a distribution over the vocabulary representing the probabilities that the next token takes each of the values in V. Consider that M can perform generation by repeatedly predicting the next token from all the previous tokens with the argmax of its output appended to the sequence at each step (this process is called greedy decoding). With a slight abuse of notation, we will also call the greedy decoding result the output of M . Let y be the token sequence generated by M , which we call a completion or response: y = M (x), which in natural language says that the model generates y when prompted with x or that x elicits y as a response from M . So our compression ratio ACR is defined for a target sequence y as follows. The threshold τ (y) is a configurable parameter of this definition. We might choose to compare the ACR to the compression ratio of the text when run through a general-purpose compression program (explicitly assumed not to have memorized any such text) such as GZIP [Gailly and Adler, 1992] or SMAZ [Sanfilippo, 2006] . This amounts to setting τ (y) equal to the SMAZ compression ratio of y, for example. Alternatively, one might even use the compression ratio of the arithmetic encoding under another LLM as a comparison point, for example if it was known with certainty that the LLM was never trained on the target output, and hence could not have memorized it [Delétang et al., 2023] . In reality, copyright attribution cases are always subjective, and the goal of this work is not to argue for the right threshold function, rather to advocate for the adversarial compression framework for arbitrating fair data use. Thus, we use τ = 1 in the experiments below, which we believe has substantial practical value.2 For more discussion on alternative thresholds, see Appendix E where we discuss the implications of this choice.Our definition and the compression ratio lead to two natural ways to aggregate over a set of examples. First, we can average the ratio over all samples/test strings and report the average compression ratio (this is τ -independent). Second, we can label samples with a ratio greater than one as memorized and discuss the portion memorized over some set of test cases (for our choice of τ = 1). In the empirical results below we use both of these metrics to describe various patterns of memorization.Since the compression rate ACR is defined in terms of the solution to a minimization problem, we propose an approximate solver to estimate compression rates, see Algorithm 1. Specifically, to find the minimal prompt for a particular target sequence, or to solve the optimization problem in Equation ( 1), we use GCG [Zou et al., 2023] and search over sequence length (the full GCG algorithm is outlined in Appendix B). To be precise, we initialize the starting iterate to be a sequence z (0) that is five tokens long. Each step of our algorithm runs GCG to optimize z for n steps. If the resulting prompt successfully produces the target string, i.e. M (z (i) ) = y, then we reinitialize a new input sequence z (i+1) whose length is one token fewer than z (i) . If n steps of GCG fails, or M (z (i) ) ̸ = y, then the next iterate z (i+1) is initialized with five more tokens than z (i) . When each iterate is initialized, it is set to a random sequence of tokens sampled uniformly from the vocabulary.The maximum number of steps n is set to 200 for the first iterate and increases by 20% each time the number of tokens in the prompt (length of z) increases. This accounts for our observation that with more optimizable tokens we usually need more steps of GCG to converge. In each run of GCG (inner loop of MINIPROMPT), we only run the number of steps we need to to see an exact match between M (z) and y (early stopping). Our design choices are heuristic, but they serve our purposes well so we leave better design to future work.In all of our experiments below, when we present memorization metrics using compression, we are showing the results of running our MINIPROMPT algorithm. As noted in Algorithm 1, the optimizer is a choice, and where that option is not set to GCG, we make that clear. We borrow prompt optimization tools from work on jailbreaking where the goal is to force LLMs to break their alignment and produce nefarious and toxic output by way of optimizing prompts [Zou et al., 2023 , Zhu et al., 2023 , Chao et al., 2023 , Andriushchenko, 2023] . Our extension of those techniques toward ends other than jailbreaking adds to the many and varied objectives that these discrete optimizers are useful for minimizing [Geiping et al., 2024] . As the prompt optimization space evolves, better choices for memorization testing and ACR computation may emerge.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [NA] Justification: We make no theoretical statement or proofs.Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
compressible memorization in practice: 
 We show the practical value of our definition and algorithm through several case studies as well as that the definition meets our expectations around memorization with validation experiments. Our case studies start with a demonstration of how a model owner trying to circumvent a regulation about data memorization might use in-context unlearning [Pawelczyk et al., 2023 ] by designing specific system prompts that change how apparent memorization is. Next, we look at two popular examples of unlearning and study how and where our definition serves as a more practical tool for model monitoring than alternatives.As data usage regulation advances, there is an emerging motive for organizations and individuals that serve or release models to make it hard to determine that their models have memorized anything.MINIPROMPT finds short suffixes that elicit the target.Response: Sure! Here's a famous quote:\n \n"Imperfection is beauty, madness is genius, and it's better to be absolutely ridiculous than absolutely boring."ICUL leads to the illusion of compliance.Prompt Figure 2 : In-Context Unlearning (ICUL) fools completion not compression. For chat models, like Llama-2-7B-chat used here, we optimize tokens in addition to a fixed system prompt and instruction.In this setting, we show that MINIPROMPT compresses the quote in red to the two blue tokens in the prompt in the top cell. Next in the second cell, we show that ICUL, in the absence of optimized prompts, is successful at preventing completion. Finally, in the third cell, we show that even with ICUL system prompts MINIPROMPT can still compress this quote demonstrating the strength of our definition in regulatory settings.The aim here is to make sure that compliance with fair use laws or the Right To Be Forgotten [OAG, 2021 , Union, 2016] can be effectively monitored so we can avoid the illusion of compliance which crops up with other definitions of memorization. Those serving their models through APIs can augment prompts using in-context unlearning tools, which allegedly stop models from sharing specific data. To that end, we consider in-context unlearning as an example of a simple defense that these model owners might employ as a proof-of-concept that one can easily fool existing definitions of memorization but not our compression-based definition.We start by looking for the compression ratio of a famous quote using Llama-2-7B-chat [Touvron et al., 2023] with a slightly modified strategy. Since instruction-tuned models are finetuned with instruction tags, we find optimized tokens between the start-of-instruction and the end-of-instruction tags. Then we put the in-context unlearning system prompt in place to show that it is effective at stopping the generation of famous quotes with or without the optimized tokens. Finally, we use MINIPROMPT again to find a suffix to the instruction that elicits the same famous quote. In Figure 2 , we show examples of each of these steps. See Appendix C for further discussion.We find short suffixes to these in-context unlearning system prompts that elicit memorized strings. Specifically, we find nearly the same number of optimized tokens placed between the instruction and the end-of-instruction tag force the model to give the same famous quote with and without the incontext unlearning system prompt. This consistency in ACR-and therefore the memorization testmatches our intuition that without changing model weights memorized samples are not forgotten. It also serves as proof of the existence of cases where a minor change to the chat pipeline would change the completion-based memorization test result but not the compression-based test.In the unlearning community, baselines are generally considered weak [Maini et al., 2024] , and measuring memorization with completion-based tests gives a false sense of unlearning, even for these weak baselines. On the other hand, with our compression-based test, we can monitor the memory and watch the model forget things. As with the weak in-context unlearning example above where we QA after 20 unlearning stepsQuestion: What professions do Hina Ameen's parents hold? Ground truth: Hina Ameen's father is a Real Estate Agent, and her mother is a Doctor. Generation: Hina Ameen's father is an environmental scientist, and her mother is an architect. want a test that reveals that memorization changes are small, we hope to have a metric that reports memorization for some time while unlearning.We compare completion and compression tests on the TOFU dataset3 [Maini et al., 2024] . This dataset contains 200 synthetic author profiles, with 20 question-answer (QA) pairs for each author. We finetune Phi-1.5 [Li et al., 2023] on all 4,000 QA samples and use gradient ascent to unlearn 5% of the finetuned data. Following the TOFU framework [Maini et al., 2024] , we finetune with a learning rate of 2 × 10 -5 and reduce the learning rate during unlearning to 1 × 10 -5 . Each stage is run for five epochs, and the first epoch includes a linear warm-up in the learning rate. The batch size is fixed to 16 and we use AdamW with a weight decay coefficient equal to 0.01.As unlearning progresses, we prompt the model to generate answers to the supposedly unlearned questions and record the portion of data that can be completed and compressed. Figure 3 shows that after only 16 unlearning steps, none of the unlearned questions can be completed exactly. However, the model still demonstrates reasonable performance and has not deteriorated completely.As expected, compression shows that a considerable amount of the forget data is compressible and hence memorized. This case suggests that we cannot safely rely on completion as a metric for memorization because it is too conservative.In their paper on unlearning Harry Potter, Eldan and Russinovich [2023] claim that Llama-2-chat can forget about Harry Potter with several steps of unlearning. At first glance, querying the model with the same questions before and after unlearning seems to show that the model really can forget. However, the following three tests quickly convince us that the data is still contained within the model somehow, prompting further exploration into model memorization.1. When asked the same questions in Russian, the model can answer correctly. We provide examples of such behavior in Appendix D and Lynch et al. [2024] make the same observation.2. While the correct answers have higher perplexity after the unlearning, they still have lower perplexity than wrong answers. Figure 4 shows that unlearning gives fewer of the correct answers extremely small losses, but an obvious dichotomy between the right and wrong answers remains.3. With adversarial attacks designed to force affirmative answers without any information about the true answer, we can elicit the correct response-57% of the Harry Potter related responses can be elicited from the original Llama-2 model, and 50% can still be elicited after unlearning (Figure 8 ).Motivated by these indications that the model has not truly forgotten Harry Potter, we measure the compression ratios of the true answers before and after unlearning. and find that they are still compressible. Figure 8 shows that even after unlearning, nearly the same amount of Harry Potter text is still memorized. We conclude that this unlearning tactic is not successful. Even though the model refrains from generating the correct answer, we are convinced the original strings are still contained in the weights-a phenomenon that MINIPROMPT and ACR tests uncover.Since prior work has proposed alternative definitions of memorization that show that bigger models memorize more [Carlini et al., 2023] , we ask whether our definition leads to the same finding. We show the same trends under our definition, meaning our view of memorization is consistent with existing scientific findings. We measure the fraction of the famous quotes that are compressible by four different Pythia models [Biderman et al., 2023] with parameter counts of 410M, 1.4B, 6.9B, and 12B and the results are in Figure 5 .Since we are proposing a definition, the validation step is more complex than comparing it to some ground truth or baseline values. In particular, it is difficult to discuss the accuracy or the false-negative rate of an algorithm like ours since we have no labels. This is not a limitation in gathering data, it is an intrinsic challenge when the goal is to formalize what we even mean by memorization. Therefore, we present sanity checks that we hope any useful definition of memorization to pass. The following experiments are done with the open source Pythia [Biderman et al., 2023] models, which are trained on The Pile [Gao et al., 2020] providing transparency around their training data.Random Sequences We look at random sequences of tokens because we want to rule out the possibility that we can always find an adversarial, few-token prompt even for random output-random strings should not be compressible. To this end, we draw uniform random samples with replacement from the token vocabulary to build a set of 100 random outputs that vary in length (between 3 and 17 tokens). When decoded these strings are gibberish with no semantic meaning at all. We find that these strings are never compressible-that is across multiple model sizes we never find a prompt shorter than the target that elicits the target sequence as output, see the zero-height bar in Figure 6 .To further determine the validity of our definition, we investigate the average compression rate of natural text that is not in the training set. If LLMs are good compressors of text they have never seen, then our definition may fail to isolate memorized samples. We take random sentences from Associated Press4 articles that were published in November 2023, well after the models we experiment with were trained. These strings are samples from the distribution of training data as the training set includes real news articles from just a few months prior. Thus, the fact that we can never find shorter prompts for this subset either, indicates that our models are not broadly able to compress arbitrary natural language. Again, see the zero-height bar in Figure 6 . One important thing to consider is that optimized prompts can elicit any output from the model (in particular things that were never seen during training). Our experiments, including those involving random strings and Associated Press data, show that while the GCG algorithm can elicit any output, we never observe compression of non-training data. This suggests that our method is robust against false positives.Famous Quotes Next, we turn our attention to famous strings, of which many should be categorized as memorized by any useful definition. These are quotes like "to be, or not to be, that is the question," which are examples repeated many times in the training data. We find that Pythia-1.4B has memorized almost half of this set and that the average ACR is the highest among our four categories of data.Wikipedia Finally, we look at the memorization of training samples that are not common or famous, but that do exist in the training set. We take random sentences from Wikipedia articles that are included in the Pile5 [Gao et al., 2020] and compute their compression ratio. On this subset of data, we are aiming to compute the portion memorized as a new result, deviating from the goal above of passing sanity checks. Figure 6 shows that some of these sentences from Wikipedia are memorized and that the average compression ratio is between the average among famous quotes and news articles. Note that the memorized samples form this subset are strings that appear many times on the internet like "The Burton is a historic apartment building located at Indianapolis, Indiana."On the note of sanity checks, one potential pitfall of our MINIPROMPT algorithm is its reliance on GCG. It is possible that there exist shorter strings than we can find. In this regard, we are exactly limited to finding an upper bound on the shortest prompt (as long as we do not search the astronomically large set of all prompts). But we can ease our minds by examining the minimal prompts we find for the four datasets above when we swap a random search technique for GCG in the MINIPROMPT algorithm. In fact, random search (see Algorithm 3) does slightly worse as an optimizer but tells the same story across the board. In other words, one might fear that our findings are the results of some peculiarity in GCG or some bias/preference GCG has for finding short prompts on some types of data. We establish that the same general trends in memorization can be observed Famous Quotes Wiki.Figure 7 : ACR versus target string length. Our experiments are designed to include a balanced mix of both short and long sequences, ensuring that the evaluation of the ACR metric is comprehensive and unbiased. This helps mitigate any potential bias towards longer sequences.with a gradient-free search algorithm, and thus conclude that we are not mistaking a GCG bias for some other signal. Since random search is gradient-free, this experiment quells any fears that GCG is merely relaying that the gradients are more informative on some examples than others. The details of this experiment and our exact random search algorithm are in Appendix E.Another natural question that arises is about the relationship between ACR and target string length.To address this issue, we plot the sequence length on the horizontal axis to illustrate how the ACR varies across different lengths in Figure 7 . This analysis shows that while longer sequences can achieve higher compression ratios, the ACR metric remains effective and meaningful for shorter sequences as well.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: Section 2, Appendix B Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.• Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
discussion: 
 Limitations Our findings are limited in that we mostly consider Pythia models and a natural question we do not address is what kinds of things are memorized by prominent state-of-the-art models. Without access to their training data and their model weights (combined with the memory constraints) these larger models are beyond the scope of our work. Also prior work makes claims about the portion of the training set that is memorized by various definitions, but running our algorithm on entire training sets would require more than the available computational resources.Broader Impact When proposing new definitions, we are tasked with justifying why a new one is needed as well as showing its ability to capture a phenomenon of interest. This stands in contrast to developing detection/classification tools whose accuracy can easily be measured using labeled data.It is difficult by nature to define memorization as there is no set of ground truth labels that indicate which samples are memorized. Consequently, the criteria for a memorization definition should rely on how useful it is. Our definition is a promising direction for future regulation on LLM fair use of data as well as helping model owners confidently release models trained on sensitive data without releasing that data. Deploying our framework in practice may require careful thought about how to set the compression threshold but as it relates to the legal setting this is not a limitation as law suits always have some subjectivity [Downing, 2024] . Our hope is to provide regulators, model owners, and the courts a mechanism to measure the extent to which a model contains a particular string within its weights and make discussion about data usage more grounded and quantitative.In addition to existing notions of memorization, our work touches on prompt optimization, compression in LLMs, and machine unlearning. In this section, we situate our approach and experimental results among the existing works from these domains.Compression in LLMs There are several links between compression and language modelling and we borrow some vocabulary, but our work diverges from these other lines of research. For example, Delétang et al. [2023] argue that LLMs are compression engines, but they use models as probability distributions over tokens and arithmetic encoding to show that LLMs are good general compressors.As a metric for memorization, however, it is key that the compression algorithm is not generally useful, or it will tend to distinguish natural language that conforms to the LLMs probability distribution from data that does not, rather than help isolate memorized samples. Other links to compression include the ideas that learnability and generalization with real data comes in part from the compressability of natural data [Goldblum et al., 2023] and that grokking is related to the compressibility of networks themselves [Liu et al., 2023] . Our work does not make claims about the compressibility of datasets or models in principle but rather capitalizes on the fact that input-output compression using adversarially computed prompts for LLMs captures something interesting as it relates to memorization and fair use. In fact, Jiang et al. [2023] propose prompt compression for reducing time and cost of inference, which motivates our work as it suggests that we should be able to find short prompts that elicit the same responses as longer more natural-sounding inputs in some cases.Algorithm 2 Greedy Coordinate Gradient (GCG) [Zou et al., 2023] Input: Loss L, Vocab. V, Target y, Num. Tokens n tokens, Num. Steps num steps Initialize prompt x to random list of n tokens tokens from V E = M 's embedding matrix for num steps times do for i = 0, ..., n tokens doX i = Top-k(-∇ ex i L(y|x)) end for for b = 1, ..., B do x(b) = x x(b) i = Uniform(X i ), i = Uniform([1, ..., n tokens]) end for x = x(b * ) where b * = arg min b L(y|x (b) ) end for return xAlgorithm 3 Random Search (for LLM prompts) [Andriushchenko, 2023] Input: Loss L, Vocab. V, Target y, Num. Tokens n tokens, Num. Steps num steps Initialize prompt x to random list of n tokens tokens from V for num steps times do for b = 1, ..., B dox(b) = x x(b) i = Uniform(V), i = Uniform([1, ..., n tokens]) end for x = x(b * ) where b * = arg min b L(y|x (b) ) end for return xAs a proof of concept, we further perform adversarial compression on five famous quotes and get an average compression ratios of 6.54 and 4.74, with versus without the unlearning system prompt, respectively. Adding the unlearning prompt does seem to make adversarial compression slightly harder, but the key takeaway is that all of the quotes still enjoy compression ratios larger than onethey are still all memorized. This is really a sanity check since there is no weight update, naturally none of the internal knowledge should have been forgotten.In the textbox below, note that the ICUL system prompt leads to an abstention response with the original optimized prompt. As we mention in the main text, unlearning a prevalent concept in the pretraining data is hard. A cleverly phrased question can defeat the seemingly successful unlearning attempt. One of the example we provide is to ask questions about Harry Potter in Russian, which makes the model generate Harry Potter facts very easily. Here are some examples. Some of our results in the main body are extended here. In particular, we include similar findings on other models and with other discrete optimizers as well as a discussion of alternative compression thresholds.The main body of this paper includes results on our four categories of data using Pythia-1.4B. We also examine the memorization of another Pythia model. In Figure 9 we show the memorization patterns for Pythia-410M. Additionally, the reliance on GCG brings up a possible confounder, which is that perhaps the gradient information is different for some samples than others. To address this, we use random search and find similar trends as shown in Figure 10 .In the main body of this paper we discuss various choices for the threshold function τ and we continue that discussion here. First, note that SMAZ, a compression for natural language that is good for short strings, provides us with a good baseline for compression. In Figure 11 , we show the Pythia-1.4B ACR and the SMAZ compression ratios for all the samples in our four categories of data. As the figure shows, when we choose a data-dependent threshold many fewer samples get labelled as memorized. This is a reasonable knob for regulators and litigators to turn. In a court of law (in the United States), this kind of evidence would be more or less compelling, but in every case would still contribute to the evidentiary body presented and help lawyers make cases about copyright infringement. We also explore how compressible paraphrased versions of famous quotes are. This line of questioning aims to disentangle exact match memorization from concept memorization. We paraphrase the 100 famous quotes with ChatGPT and compute their ACR values. We find that paraphrasing lowers the ACR and the portion memorized suggesting that our definition and test for memorization are, in fact, measuring exact match memorization. See Table 1 .Table 1 : Memorization statistics for Pythia-1.4B model.Pythia-1.4B Famous Quotes 1.17 0.47 Pythia-1.4B Paraphrased Quotes 0.68 0.11In order to run MINIPROMPT, we need enough GPU memory to load a model and compute the gradients of the inputs for a batch of prompts (see GCG algorithm above). This means for the smaller models (fewer than 7B parameters), with a single NVIDIA RTX A4000 GPU we can compute minimal prompt in a few minutes if it is highly compressible and a few hours (around 10 in the worst case) if we need to search for very long prompts. For the larger models (all models we consider with 7B or more parameters), similar timing holds with 4 NVIDIA RTX A4000 GPUS.NeurIPS Paper ChecklistQuestion: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: Code included in the supplementary material and linked to in the footnote on the title page. Guidelines:• The answer NA means that paper does not include experiments requiring code. Justification:Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes]Justification: Section 5Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification:Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.• Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.There exist prompts like "count from 1 to 1000," for which a chat model M is able to generate "1, 2, . . . , 1000," which results in a very high ACR. However, for copyright purposes, we argue that this category of algorithmic prompts are in the gray area where determining memorization is difficult and beyond the scope of this paper given our primary application to creative works.This dataset is released under the MIT License and their assets and license can be found at https://huggingface.co/datasets/locuslab/TOFU.We use data from the Associated Press and their terms of service allow for this use but not redistribution. Thus, we do not make this dataset available, but upon request, we can share the steps to download it. See their terms here: https://apnews.com/termsofservice.This dataset is released under the MIT License.Unlearning The focus of machine unlearning[Bourtoule et al., 2021, Sekhari et al., 2021, Ullah et al., 2021, Pham et al., 2024, Lynch et al., 2024, Schwinn et al., 2024] is to remove private, sensitive, or false data from models without retraining them from scratch. Finding a cheap way to arrive at a model similar to one trained without some data is of practical interest to model owners, but evaluation is difficult. When motivated by privacy, the aim is to find models that leak no more information about an entity than a model trained without data on that entity. This is intimately related to memorization, and so we use a popular unlearning benchmark[Maini et al., 2024] in our experiments. 
: 
 Figure 1 : We propose a compression ratio where we compare the length of the shortest prompt that elicits a training sample in response from an LLM to the length of that sample. If a string in the training data can be compressed, i.e. the minimal prompt is shorter than the sample, then we call it memorized. Our test is an easy-to-describe tool that is useful in the effort to gauge the misuse of data. 
 
 Appendix:  


Decision: This paper proposes an interesting new definition for what constitutes as memorization in LLMs -- if there exists a prompt which elicits the target text and is shorter than that text, then we can say the model has memorized the target. This makes intuitive sense and the paper does a great job of contrasting this method with other popular notions of memorization.

The main weaknesses, as noted by the reviewers, are around the empirical evaluation of the method:
1. There is a lack of direct comparison to other methods for detecting memorization, such as discoverable and extractable memorization. The authors rightfully claim that this is difficult as the definition of memorization itself is different across these methods, but at the very least it would have been instructive to see a comparison of *how many* sequences from the training data each method can labels as memorized.
2. The issue of false positives is not adequately addressed in the paper. There are many sequences to which LMs assign a high probability despite having never seen them during training. An experiment showing how compression ratio changes with perplexity on unseen sequences would be instructive in determining the validity of the method.

Despite the above limitations, overall the paper is interesting and tackles an important problem. Hence, I am recommending a weak accept -- with the hope that the authors will address the points above for the camera ready version.

Reviews: review: paper_summary: paper_summary: This paper proposes Adversarial Compression Ratio (ACR), a metric for assessing memorisation in LLMs; ACR is defined as the ratio between the length of the generation we need to test memorisation for and the length of the shortest prompt that can elicit such a generation. A question I have is whether "length" is always suitable as a complexity measure; for example, y can be very long but also very "simple" (such as the "mmmmmmmm...mmm" messages from /r/microwavegang, which occur in some pre-training corpora). To solve such a combinatorial minimisation problem (finding the shorter prompt that elicits a given generation), the authors propose using Greefy Coordinate Gradient [GCG, Zou et al., 2023].

Overall, It is a very interesting approach and paper; however, it would be useful to compare ACR with other methods for testing for memorisation.
strength_weakness: strength_weakness: 1) Lack of comparisons with other methods for solving the same task
2) Not sure why "number of tokens" may be a suitable measure of complexity
questions: questions: Is ACR more effective at detecting memorisation compared to the method proposed in e.g., https://openreview.net/forum?id=TatRHT_1cK ?
limitations: limitations: Lack of comparisons with related methods for solving the same task
paper_summary: paper_summary: ### Summary

- This paper proposes a new metric for measuring memorization in LLMs.
- Their proposed metric called Adversarial Compression Ratio (ACR) is capable of measuring memorization for arbitrary strings at a reasonably low compute.
- The definition of memorization, the authors propose in the paper is based on a compression arguments which goes something like this - "a phrase present in the training data is memorized if we can make the model reproduce the phrase using a prompt (much) shorter than the phrase itself."
- To operationalize this definition, the techinque requires finding the shortest adversarial input prompt that is optimized to produce the sentence under consideration as its output.
- The ratio of input to output tokens is defined as ACR.
- There are various ways to measure memorization
	- Discoverable Memorization
		- This was proposed by Carlini and essentially measures if a prefix elicits the suffix as the response.
			- This definition is very permissive since definition only tests for exact completions.
			- It's easy to evade by just tweaking a few tokens to avoid exact match
			- It also requires validation dataset to tweak generation hyperaparameters such as top-p, top-k etc.
	- Extractable Memorization
		- This definition defines extractable memorization as a string which elicits the string in the response.
			- Since this allows any arbitrary string as prompt, this definition is very restrictive as it allows the prompt to have the entire string in question. For e.g., "repeat the following string: X" -> X
	- Counterfactual Memorization
		- Measures the difference in model performance with a model trained with the example versus one trained without it
			- Since LLMs are expensive to train, this definition is quite impractical.
	- Membership Inference Tests which are commonly used to test if a model was trained on a particular example datapoint has the following problems
		- It's very restrictive. Akin to plagiarism, it is okay to read copyrighted books but copying is problematic
		- Have brittle evaluation
- Based on the ACR ratio, ACR(M, y) = |y|/|x| where |x| = argmin |x| s.t. M(x) = y
  the authors propose a notion of $\tau$-compressible memorization i.e. if ACR(M,y) > $\tau(y)$
- This metric can be aggregated over a dataset to report an average compression ratio or another metric called portion memorized which measures the proportion of data with MCR >  $1$
- GCG (Greedy Coordinate Gradient) is used to find the the adversarial prompt from earlier work which is a common algorithm.
- The authors also show that in context unlearning can fool completion but not this adversarial notion of compression
strength_weakness: strength_weakness: ## Weakness

- The paper is well motivated and tackles an important problem. However, independent of the problem of false negatives, I wonder if false positives might be a bigger problem here. What if as a result of GCG algorithm, you are able to elicit a generation from a model which was never seen by the model during the training. I would suggest adding an experiment and some discussion around this.
questions: questions: ## Questions

- Line 125: "Hard to arbitrate: training data is often not released."
	- Even if the training data is not released, can a publisher not run MIA against the LLM to determine effectively if their training data was used during training. I don't quite agree with this claim
- Line 313: Can you clarify what you mean "quells any fears that GCG is merely relaying that the gradients are more informative on some examples than others"
limitations: limitations: The authors have adequately addressed the limitations.
paper_summary: paper_summary: The authors propose adversarial compression ratio (ACR) as a novel metric for assessing memorization in LLMs. ACR compares the lengths of the smallest prefix string evoking a target completion from the model with the length of the completion. The shorter the prefix, the higher the compression ratio, and subsequently, the stronger the memorization. The authors further leverage an optimization-based approach using GCG, searching over the entire sequence length to find the shortest possible prefix, and demonstrate the effectiveness of such an approach in finding prompts which bypass in-context unlearning on LLaMA2-7-Chat & famous quotes.The authors perform further experiments on unlearning benchmarks such as TOFU and trying to forget harry potter, showing that ACR discovers that models are still able to reproduce significant portions of these datasets even after unlearning was applied. The authors also perform a scale-based analsyis as well as a comparison to data unlikely to be memorized to confirm that memorization increases with scale and the robustness of their proposed method, respectively.
strength_weakness: strength_weakness: - The optimization process, as mentioned by the authors, does not necessarily have to be completely accurate, sometimes underestimating the error ratio. It would be interesting to see how large this error can be by pehaps comparing the budget given to GCG. While it is not necessary for a solution to be optimal, an idea of how close the algorithm is, on average across a small sample size, would be relevant.
- The method identifies exact memorization, but does not account for paraphrases. While it is unlikely that a paraphrase would be memorized & easily reproduced, while the exact string forgotten, this might be a consequence of unlearning. What do you think about this issue?
questions: questions: See above
limitations: limitations: Yes
paper_summary: paper_summary: The paper introduces a novel metric Adversarial Compression Ratio (ACR) to assess memorization in LLMs. The authors first contend that the conventional understanding of memorization may not be fully adequate for evaluating the memorization ability. Hence, ACR provides a quantitative measure by proposing that a model memorizes a piece of training data if it can reproduce it from a significantly shorter prompt, and presents a practical algorithm called MINIPROMPT to approximate the ACR for any given string. The authors validate the ACR through a series of experiments and case studies, demonstrating its effectiveness in various scenarios, including the detection of memorized content following attempted unlearning methods.
strength_weakness: strength_weakness: 1. The ACR metric may inherently favor the detection of memorization in longer sequences due to the potential for a more substantial compression ratio when a shorter prompt reproduces a longer string. This bias could significantly impact the evaluation of an LLM's memorization of some concise knowledge.

2. The introduction on miniprompt is a bit brief, and since the optimizer algorithm in the experiment relies on the Greedy Coordinate Gradient Descent, the author might also consider providing a brief introduction to GCG in the main text to be more reader-friendly.
questions: questions: 1. How does the ACR metric account for variations in the length of expressions conveying the same knowledge, such as "bird can fly" versus "it is a well-known fact that birds possess the ability to fly"?

2. How would you interpret it if two model, A has a larger portion memorized than B with a smaller average compression ratio? Which of the two metrics is more representative in measuring the memorization ability?
limitations: limitations: Yes.
paper_summary: paper_summary: This paper proposes a new definition of memorization, the Adversarial Compression Ratio (ACR), based on a compression argument.  ACR provides an adversarial perspective on measuring memorization, offering the flexibility to assess memorization for arbitrary strings with relatively low computational requirements.
strength_weakness: strength_weakness: 1. Some concepts need further clarification or justification. For instance, why do we need this adversarial view, not the natural text, for the compression argument? This assumption "if a certain phrase exists within the LLM training data (e.g., is not itself generated text) and it can be reproduced with fewer input tokens than output tokens, then the phrase must be stored somehow within the weights of the LLM" needs further justification.  The authors should have provided more analysis on the threshold used in "The threshold is a configurable parameter of this definition $\tau(y)$"
2. The authors should have done some efficiency analysis on Algorithm 1.
questions: questions: 1. Besides Algorithm 1 (using GCG), are there any other options, as discussed in Line 190?
2. As you mentioned here "This case suggests that we cannot safely rely on completion as a metric for memorization because it is too conservative." in Line 243,  why and how to solve this?
limitations: limitations: Current conclusions are limited since they are just made from two specific LLMs.

Comments: title: Author Response
Author Response
Thank you for your responses.
comment: Thank you for your response and the additional results. 

Budget then is probably not a good way of quantifying this - nevertheless, some bounds on the error ratio/idea of proximity to the optimal solution seem necessary, especially with the intended purpose of the method in mind (quantifying memorization).
Example scenarios are: how much can the ACR vary between different optimization algorithms? How likely is the chance of the compression ratio seeming low, while the model actually memorized the texts?
Such scenarios are likely to pop up if ever the method is to be used as proof for memorization. This is definitely not an easy problem to solve, but should be kept in mind or discussed by the authors.

My score (Accept, 7) still reflects my opinion of the paper well, thus I will keep it.
Dear reviewers,

The discussion period will end soon. If you haven't responded to the authors' rebuttal, please do so and kick off the discussion. 

Best, 
SAC
Dear reviewers,

As we approach the end of the discussion period, we kindly inquire whether we have addressed your concerns raised in the reviews. We appreciate your feedback and any further questions. They greatly help us improve our work. Thanks for your time and careful reviews.

Best,
All authors
Thank for you highlighting the potential impact of our work. We agree that we were missing a discussion of the ethical implications of using ACR metrics in evidence in a legal preceding. Our work touches broadly on the ethics of copyright, but accepting the US standard (and not reevaluating the motivations for copyright law altogether) we feel that our work can help lawyers and regulators reach a precedent that upholds an artist's right to their own work. We have added a longer discussion to the draft.
Thank you for bringing this up. The omission of these licenses is an oversight on our part. We'll promptly fix this in our updated draft. For reference, the Wikipedia Data is from the Pile which is released under the MIT License and the code is  Copyrighted (c) 2020 EleutherAI, and the specific license for the Wikipedia subset is CC BY-SA 4. The TOFU data is released on HuggingFace with MIT License.
I have read the authors' responses. Most of my concerns have been addressed. I will keep my score as 7 Accept.