# When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?

arXiv: https://arxiv.org/abs/2012.06421 · HTML: https://mlsanity.com/paper/2012.06421/

## Key facts

- Cited by 104 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Dec 2020.

## Built on by (most cited first, 30 of 104)

- [Membership Inference Attacks From First Principles](https://mlsanity.com/paper/2112.03570/) (2021)
- [Differentially Private Fine-tuning of Language Models](https://mlsanity.com/paper/2110.06500/) (2021)
- [Deduplicating Training Data Mitigates Privacy Risks in Language Models](https://mlsanity.com/paper/2202.06539/) (2022)
- [Memorization Without Overfitting: Analyzing the Training Dynamics of Large Language Models](https://mlsanity.com/paper/2205.10770/) (2022)
- [Datamodels: Predicting Predictions from Training Data](https://mlsanity.com/paper/2202.00622/) (2022)
- [Reconstructing Training Data with Informed Adversaries](https://mlsanity.com/paper/2201.04845/) (2022)
- [The Privacy Onion Effect: Memorization is Relative](https://mlsanity.com/paper/2206.10469/) (2022)
- [Reconstructing Training Data from Trained Neural Networks](https://mlsanity.com/paper/2206.07758/) (2022)
- [Large-Scale Differentially Private BERT](https://mlsanity.com/paper/2108.01624/) (2021)
- [Trustworthy AI: A Computational Perspective](https://mlsanity.com/paper/2107.06641/) (2021)
- [Knowledge-Augmented Reasoning Distillation for Small Language Models in Knowledge-Intensive Tasks](https://mlsanity.com/paper/2305.18395/) (2023)
- [What Do We Mean by Generalization in Federated Learning?](https://mlsanity.com/paper/2110.14216/) (2021)
- [Understanding Transformer Memorization Recall Through Idioms](https://mlsanity.com/paper/2210.03588/) (2022)
- [How much do language models memorize?](https://mlsanity.com/paper/2505.24832/) (2025)
- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [Demystifying Verbatim Memorization in Large Language Models](https://mlsanity.com/paper/2407.17817/) (2024)
- [Decepticons: Corrupted Transformers Breach Privacy in Federated Learning for Language Models](https://mlsanity.com/paper/2201.12675/) (2022)
- [The Low-Resource Double Bind: An Empirical Study of Pruning for Low-Resource Machine Translation](https://mlsanity.com/paper/2110.03036/) (2021)
- [Covariance-Aware Private Mean Estimation Without Private Covariance Estimation](https://mlsanity.com/paper/2106.13329/) (2021)
- [Measuring memorization in language models via probabilistic extraction](https://mlsanity.com/paper/2410.19482/) (2024)
- [Characterizing Datapoints via Second-Split Forgetting](https://mlsanity.com/paper/2210.15031/) (2022)
- [Membership Inference on Word Embedding and Beyond](https://mlsanity.com/paper/2106.11384/) (2021)
- [Differentially Private Decoding in Large Language Models](https://mlsanity.com/paper/2205.13621/) (2022)
- [The Stronger the Diffusion Model, the Easier the Backdoor: Data Poisoning to Induce Copyright Breaches Without Adjusting Finetuning Pipeline](https://mlsanity.com/paper/2401.04136/) (2024)
- [Integration of Large Language Models and Federated Learning](https://mlsanity.com/paper/2307.08925/) (2023)
- [Undesirable Memorization in Large Language Models: A Survey](https://mlsanity.com/paper/2410.02650/) (2024)
- [On the Impossible Safety of Large AI Models](https://mlsanity.com/paper/2209.15259/) (2022)
- [Metadata Archaeology: Unearthing Data Subsets by Leveraging Training Dynamics](https://mlsanity.com/paper/2209.10015/) (2022)
- [Deconstructing Data Reconstruction: Multiclass, Weight Decay and General Losses](https://mlsanity.com/paper/2307.01827/) (2023)
- [Verifiable and Provably Secure Machine Unlearning](https://mlsanity.com/paper/2210.09126/) (2022)

## Abstract (arXiv)

Modern machine learning models are complex and frequently encode surprising amounts of information about individual inputs. In extreme cases, complex models appear to memorize entire input examples, including seemingly irrelevant information (social security numbers from text, for example). In this paper, we aim to understand whether this sort of memorization is necessary for accurate learning. We describe natural prediction problems in which every sufficiently accurate training algorithm must encode, in the prediction model, essentially all the information about a large subset of its training examples. This remains true even when the examples are high-dimensional and have entropy much higher than the sample size, and even when most of that information is ultimately irrelevant to the task at hand. Further, our results do not depend on the training algorithm or the class of models used for learning. Our problems are simple and fairly natural variants of the next-symbol prediction and the cluster labeling tasks. These tasks can be seen as abstractions of text- and image-related prediction problems. To establish our results, we reduce from a family of one-way communication problems for which we prove new information complexity lower bounds. Additionally, we present synthetic-data experiments demonstrating successful attacks on logistic regression and neural network classifiers.