How much do language models memorize? — part 2/4
Cleaned-text code points [15924, 31670). Bibliography omitted here; source.md includes it.
Fixing our notion of Kolmogorov memorization, we now describe how we can estimate H K H^{K} in different setups. Note that exact calculation of Kolmogorov complexity is known to be uncomputable ( Kolmogorov, 1965 ) . However, we can still approximate it using the best available compression schemes. These compression schemes could be arbitrary algorithms, e.g. using prompt optimization as in Schwarzschild et al. (2024) or using text prefixes as in Carlini et al. (2023b) .
We adopt arithmetic coding as the most natural compression algorithm for language. Arithmetic coding is not only effective for text compression Delétang et al. (2024) , but it also allows code lengths to be computed efficiently using model likelihoods. A promising direction for future research is to design compression algorithms specifically tailored to minimize the code length of training data in machine learning models and use it to obtain more accurate estimation of Kolmogorov complexity and memorization. Below, we summarize how we approximate each term in our memorization definition using model likelihoods.
• H K ( x ∣ θ ^ ) H^{K}(x\mid\hat{\theta}) : Here, θ ^ \hat{\theta} is the trained target model, which does not necessarily capture the true data distribution. We do not really calculate the compressed code, instead we use fact that the compression rate of arithmetic coding tied to the likelihood of the model ( Shannon, 1950 ) . So, we can estimate H K ( x ∣ θ ^ ) H^{K}(x\mid\hat{\theta}) by the negative log likelihood of x x under the target model, − l o g ( p ( x ∣ θ ^ ) ) -log(p(x\mid\hat{\theta})) .
• H K ( x ∣ θ ^ , θ ) H^{K}(x\mid\hat{\theta},\theta) : In this case, the compression algorithm has access to both target and reference models. We simply compute − l o g ( max { p ( x ∣ θ ^ ) , p ( x ∣ θ ) } ) -log(\max\{p(x\mid\hat{\theta}),p(x\mid\theta)\}) . In practice, our choice of reference model is a larger model with the same architecture as θ \theta trained for many steps on a much wider data distribution.
A curious reader may notice that we began with a likelihood-based notion of memorization, then shifted to a definition grounded in Kolmogorov complexity, and ultimately returned to likelihood to estimate that complexity. We emphasize, however, that the likelihood used in our approximation of Kolmogorov memorization is distinct from the initial likelihood notion. In particular, this likelihood is dependent on the parameters of the decoding algorithm, such as temperature or top-k sampling. More broadly, we note that any compression algorithm can be used to approximate Kolmogorov complexity, and our choice of arithmetic coding is just one instantiation of this broader framework.
##### Choice of reference model.
In this work we use two reference models to compute p ( x ∣ θ ^ ) p(x\mid\hat{\theta}) . In our experiments on synthetic random strings ( Section 3 ) we know the exact underlying data distribution and use that as a reference model. In our experiments on text ( Section 4 ) we select θ \theta to be a large model of the same family, trained on a much larger superset of the training data for θ ^ \hat{\theta} .
## 3 Model Capacity for Memorization
Unintended memorization provides us a principled way of measuring the precise number of bits a model θ \theta knows about a datapoint x x . If we add up the information for each datapoint in a dataset, we can measure the total amount of bits a model knows about the dataset. And in cases where generalization is not possible because each datapoint is completely independent, we can estimate the capacity of a given model θ \theta by summing per-datapoint unintended memorization.
### 3.1 Defining model capacity
We first formalize this notion of memorization capacity for a particular language model θ \theta . Capacity is the total amount of memorization that can be stored in θ \theta across all its parameters.
###### Definition 5 (Capacity) .
Let X X be a distribution and L : X → Θ L\colon X\to\Theta a learning algorithm. We define the capacity of the learning algorithm L L to be Capacity ( L ) \displaystyle\text{Capacity}(L) = max X mem ( X , L ( X ) ) \displaystyle=\max_{X}\text{mem}\big(X,L(X)\big)
When the model capacity is reached, mem ( X , L ( X ) ) \text{mem}(X,L(X)) will no longer increase with dataset size. In practice, we can compute capacity by training to saturation on varying sizes of X X and computing the maximum memorization.
### 3.2 Measuring model capacity with synthetic sequences
In this section we measure the capacity of Transformer language models. Our goal is to instantiate multiple datasets and distributions and measure the memorization of them when training a single model θ \theta . Then, we take the maximum over all datasets to approximate of the model’s capacity. For instantiating our datasets, each token is uniformly sampled from a predefined set of tokens independent of the previous tokens.
To approximate H k ( x ∣ θ , θ ^ ) H^{k}(x\mid\theta,\hat{\theta}) , we can directly compute entropy under the trained model to calculate the shortest description of the dataset conditioning on θ ^ \hat{\theta} . Subtracting the two, we can approximate the unintended memorization mem U ( X , L ( X ) ) \text{mem}_{U}(X,L(X)) . Since the process for sampling the data is completely random, there is no generalization to be stored within θ ^ \hat{\theta} (that is, mem U ( X , L ( X ) ) ≈ mem ( X , L ( X ) ) \text{mem}^{U}(X,L(X))\approx\text{mem}(X,L(X)) ).
Observe that when we sample synthetic sequences from a uniform distribution, we can compute their Shannon information exactly. Given a dataset size N N , we construct a dataset of N N sequences, each of S S tokens. Given a vocabulary size V V , we can calculate the total entropy of a dataset x i x^{i} with such parameters by H ( x i ) = N S log 2 V H(x^{i})=NS\log_{2}V . Then we calculate the compressed form x i x^{i} using entropy under θ i ^ \hat{\theta_{i}} to compute the code length and use this as an approximation of H K ( x i ∣ θ j ^ ) H^{K}(x^{i}\mid\hat{\theta_{j}}) . Then we calculate the mem ( x i , θ i ^ ) = H ( x i ) − H K ( x i ∣ θ j ^ ) \text{mem}(x^{i},\hat{\theta_{i}})=H(x^{i})-H^{K}(x^{i}\mid\hat{\theta_{j}}) and compute a model’s capacity as the maximum amount of memorization over all datasets.
##### Experimental details.
In accordance with Kaplan et al. (2020) , we train models with the GPT-2 architecture ( Radford et al., 2019 ) initialized from scratch. Our models have between 1 1 and 8 8 layers, hidden dimensions scaled from 32 32 to 512 512 , and from 100 K 100K to 20 M 20M parameters. We train models for 10 6 10^{6} steps with a batch size of 2048 2048 . We use the Adam optimizer. All models are trained on a single A100 GPU in bfloat16 precision, and we use gradient accumulation if a batch cannot fit in memory. Unless otherwise noted, we set vocabulary size V = 2048 V=2048 , sequence length S = 64 S=64 and vary only the number of points in a dataset. We train each model on each dataset size over five random seeds, which affect both model initialization and the dataset sampling.
##### Results.
We plot memorization across model and data sizes in Figure 2 . This allows us to visualize unintended memorization amounts (y-axis) across dataset sizes (x-axis) grouped by model size (line color). We observe a striking plateau once a model reaches its capacity. Given the dataset is large enough, models exhibit an upper bound in net memorization, regardless of data size. Small datasets are completely memorized by all models with enough capacity.
We estimate the capacity of each model as the maximum amount of unintended memorization in bits measured across all dataset sizes. We then compare this capacity to the model size in Figure 6 . Interestingly, even at this small scale, we see a very smooth relationship between observed capacity (maximum memorization measured over all datasets) and model parameters. We plot this relationship in Figure 6 : under these settings, our models consistently memorize between 3.5 3.5 and 3.6 3.6 bits per parameter. This corroborates the findings of prior work such as ( Roberts et al., 2020 ; Lu et al., 2024 ) , which noticed that fact storage scales linearly with model capacity. Ours is a slightly larger estimate than Allen-Zhu & Li (2024) , which estimated via quantization that models can store around 2 2 bits per parameter.
Since our models are learned via gradient descent, they are not guaranteed to find the global optima; thus, we are only ever measuring a lower bound on model capacity. We take a closer look at the training curves to analyze the convergence of our 8M parameter language model. We plot model convergence throughout training in Figure 6 .
In this case, all datasets from 16,000 to 4M samples fall within a range of 3.56 − 3.65 × 10 6 3.56-3.65\times 10^{6} bits memorized. This indicates that our measurements are robust within an order of magnitude, and we do not expect to memorize significantly more information by training for more steps. This finding also confirms our hypothesis that capacity scales roughly with parameter count. The two largest datasets (4M and 8M samples, respectively) converge to total memorization of 2.95 × 10 6 2.95\times 10^{6} and 1.98 × 10 6 1.98\times 10^{6} bits memorized. We expect that their memorization rates would continue to increase toward the capacity had we trained for more epochs.
##### How does precision affect capacity?
One natural question is how our estimates for α \alpha depend on the precision of language model training. In fact, although most software defaults to training in 32-bit precision, recent work has shown that language models can be quantized to fewer than 2 bits per parameter and still retain much of their utility. Since all other experiments have been conducted in bfloat16 precision, rerun our experiments in full fp32 precision to analyze the effect on capacity. Across model sizes, we observe a small increase in capacity, and an increase in α \alpha from 3.51 to 3.83 3.83 bits-per-parameter on average. This is far less than the actual 2x increase in the bits of θ \theta , indicating that most of the extra model bits added when increasing precision from bfloat16 to float32 are not used for raw storage.
## 4 Disentangling Unintended Memorization from Generalization
Our previous experiments analyzed the memorization and membership inference properties of synthetic bitstrings. We now turn to measuring memorization of text. Unlike randomly generated sequences, learning from text data is a mix of both unintended memorization (sample-level) and generalization (population-level). Therefore, as a reference model, we use the model of an equal parameter count trained on the maximum amount of data (in this case, the entire dataset). 3 3 3 Restricting the computational power of the reference model relates its predictions to 𝒱 \mathcal{V} -information ( Xu et al., 2020 ) which measures the “usable” information available in a signal, when accounting for model size. We also consider an oracle reference model, which is the model that achieves the best compression rate (lowest loss) on the evaluation dataset, and may have many more parameters.
##### Experimental details.
We repeat the experiments from Section 3.2 , substituting our synthetic datapoints for real text. To obtain a distribution of real-world text data, we could use any pre-training scale text dataset; we use the recently proposed FineWeb dataset ( Penedo et al., 2024 ) as it follows state-of-the-art deduplication practices. We use sequences of 64 64 tokens but perform an additional deduplication step to ensure perfect deduplication (otherwise, that 1 − 2 % 1-2\% of sequences become duplicates when truncating to 64 64 tokens). We find careful deduplication extremely important for faithfully measuring extraction rates. As in the previous subsection, we pretrain models of varying sizes on different-sized text datasets and measure the unintended memorization of each model-dataset pair. In addition to memorization, we measure membership inference performance according to a standard loss-based membership inference procedure; we also compute exact extraction rates by greedily decoding prefixes of different lengths.
##### Results.
We first observe that the sample-level unintended memorization increases with model parameters and decreases with training set size (Figure 4 ). When we measure unintended memorization with respect to an oracle reference model (Figure 2 ), memorization steadily increases as our smaller model is able to learn more about the small training set than the oracle, and then decreases as our model starts to generalize and perform on average worse than the (higher-capacity) oracle.
##### Dataset-to-capacity ratio predicts double descent.
We observe from the train and test loss that for larger datasets the model only begins to generalize (i.e. evaluation loss decreases) once its capacity is reached, which takes approximately 10 5 10^{5} samples, depending on parameter count. As in Nakkiran et al. (2019) we plot the ratio between the dataset size and model capacity (Figure 4 ). Unlike prior work, in our experiments we can compute the exact dataset size (based on the compression rates of the reference model) and exact model capacity (based on our estimate of α \alpha ).
We clearly observe double descent evaluation performance decreases as the training set size nears model capacity, and then rapidly drops as the dataset capacity exceeds the capacity of the model. Our observations offer an intuitive explanation for double descent ( Belkin et al., 2019 ; Nakkiran et al., 2019 ) : double descent begins exactly when the data capacity exceeds the model capacity . One theory is that once the model can no longer memorize datapoints individually, it is forced to share information between datapoints to save capacity, which leads to generalization.
##### Generalization explains nonzero extraction rates.
We measure extraction rates on the full training set and 10,000 non-overlapping test samples (Figure 17 ). We note that for 32-token prefixes, 100% are extractable for very small training set sizes; predictably, all extraction numbers decrease with training set size. When the dataset sizes grows sufficiently large, the extraction rate does not go fully to zero; however, it converges to nearly exactly the test extraction rate. In other words, when our (deduplicated) dataset grows sufficiently large, all successful training data extraction is attributable to generalization .
## 5 Memorization and Membership
Our training settings allow total control over the train and test data and come with perfect deduplication. This makes our setting ideal for studying the relationship between model size, dataset size, and membership inference success rate.
All of our membership inference results come from a standard loss-based membership inference ( Yeom et al., 2018 ; Sablayrolles et al., 2019 ) . The method is very simple: we set a cutoff loss value to predict whether a sample is or is not a member of the training dataset.
### 5.1 Membership in synthetic and text data
##### Synthetic data.
For each of our models trained on synthetic data, we plot the success rate of the membership inference attack attack across dataset sizes. We show results in Figure 14 . Above a certain dataset size, membership inference starts to fail in the average case. This finding indicates that if the dataset size is too large compared to the model, membership inference of an average training sample may not be possible.
##### Text.