Memorizing Long-tail Data Can Help Generalization Through Composition
Not on the map. Why?
Abstract (arXiv)
Deep learning has led researchers to rethink the relationship between memorization and generalization. In many settings, memorization does not hurt generalization due to implicit regularization and may help by memorizing long-tailed examples. In this paper, we consider the synergy between memorization and simple composition -- the ability to make correct prediction on a combination of long-tailed features. Theoretically, we show that for a linear setting, memorization together with composition can help the model make correct predictions on rare test examples that require a combination of long-tailed features, even if such combinations were never observed in the training data. Experiments on neural network architecture on simple data show that the theoretical insight extends beyond the linear setting, and we further observe that the composition capability of the model depends on its architecture.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 30 of its 37 references that are in the map. First posted on arXiv 18 Oct 2025.
Builds on
30 of 37 references.
References · 30
- 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
- 2016Understanding deep learning requires rethinking generalizationcited by 1,674
- 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 927
- 2018The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networkscited by 864
- 2022Quantifying Memorization Across Neural Language Modelscited by 763
- 2022When and why vision-language models behave like bags-of-words, and what to do about it?cited by 610
- 2019Benign Overfitting in Linear Regressioncited by 549
- 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 513
- 2020What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimationcited by 497
- 2019Does Learning Require Memorization? A Short Tale about a Long Tailcited by 460
- 2015An Introduction to Matrix Concentration Inequalitiescited by 397
- 2015Neural Module Networkscited by 376
18 more
- 2017Implicit Regularization in Matrix Factorizationcited by 322
- 2019Compositionality decomposed: how do neural networks generalise?cited by 265
- 2020COGS: A Compositional Generalization Challenge Based on Semantic Interpretationcited by 263
- 2022Memorization Without Overfitting: Analyzing the Training Dynamics of Large Language Modelscited by 220
- 2019Two models of double descent for weak featurescited by 195
- 2018Compositional Attention Networks for Machine Reasoningcited by 183
- 2019Good-Enough Compositional Data Augmentationcited by 158
- 2021Counterfactual Memorization in Neural Language Modelscited by 156
- 2021VALSE: A Task-Independent Benchmark for Vision and Language Models Centered on Linguistic Phenomenacited by 135
- 2023A Theory for Emergence of Complex Skills in Language Modelscited by 113
- 2023Compositional Generalization from First Principlescited by 64
- 2021Meta-Learning to Compositionally Generalizecited by 62
- 2019Linguistic generalization and compositionality in modern artificial neural networkscited by 58
- 2024Scaling Laws in Linear Regression: Compute, Parameters, and Datacited by 57
- 2020Formalizing Data Deletion in the Context of the Right to be Forgottencited by 50
- 2024When does compositional structure yield compositional generalization? A kernel theorycited by 20
- 2024Memorization in deep learning: A surveycited by 15
- 2025An explainable transformer circuit for compositional generalizationcited by 8
Built on by
Citing papers per year: 2026: 1.
1 paper.