Memorizing Long-tail Data Can Help Generalization Through Composition
Authors: Mo Zhou
Haoyang Ma
Rong Ge
Venue: ICLR 2026 Poster (2026)
Keywords: memorization
composition
long-tail data
Primary area: learning theory

Abstract: 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.

Published as a conference paper at ICLR 2026
MEMORIZING LONG-TAIL DATA CAN HELP GENERAL- IZATION THROUGH COMPOSITION
Mo Zhou'! Haoyang Ma Rong Ge
1 University of Washington, 2 Duke University mozhoul 78cs washingtonn edu, haoyang. ma@duke. ronggelcs duke. edu
ABSTRACT
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 compo- sition - the ability to make correct prediction on a combination of long-tailes tailed features. Theoretically, we show that for linear setting, memorization together with composition can help the model make correct predictions on rare test examples that require combination of long-tailed features, even if such combinations were never observed in the training data. Experiments on neural network architecture 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.
INTRODUCTION
The relationship between memorization and generalization has always been an intriguing topic in deep learning. It has long been known that neural networks used for supervised learning can memorize noisy or even random labels (Zhang et al. (0117). and recent large language models can still memorize long text despite not being overparametrized (Carlini al. 2019 2022). Conventional wisdom from statistical learning theory suggests that memorization might be detrimental to generalization performance, yet neural networks often generalize well with memorization, sometimes even better compared to networks that do not memorize.
Trying to understand this relationship from a theoretical perspective has led the idea of implicit regularization and benign overfitting (Belkin et al.) 2019 Bartlett et al.] 20200] Belkin et al.) 2020 Hastic et al. 2022 Gunasekar et al. (017)) where the training process and architecture choices of neural networks prefer certain solutions that have good generalization despite memorizing the training data. Another interesting line of work (Feldman 2020 Feldman & Zhang 2020) demonstrated that memorization can actively help generalization by capturing long-tail behaviors in the training data. If the test data contain examples that are similar to training examples, it is more likely for the neural network to make correct predictions.
However, the similarity between the test and training data alone cannot explain all the benefits of memorization. Recent large models exhibit several surprising properties including composition the ability to produce correct results by combining two or more pieces of information learned during training. Composition has received lot of attention (Hupkes et al. 2020 Baroni 2020). Composition allows models to perform tasks that may not appear in the training data, resulting in stronger notions of -uiot--distriuution (OOD) generalization. Intuitively, memorizing long-tai -ail examples and composition are synergistic: model that is capable of composition may leverage two or more memorized long-tail examples to create/predict something that is highly unlikely the original training data. In this paper, try to demonstrate this behavior simplistic models.
Our theoretical approach focuses on a linear setting where features appear in different frequencies, and each sample consists of sparse combination of features. As the model is linear, it automatically
"Equal contribution.
Code available
-ww.orrmmmmiioommm iati conposssiiinnnn

---

Published as a conference paper at ICLR 2026
achieves simple composition if individual features are learned correctly, their combinations can also be predicted correctly. We give guarantees for out-of ttt-of-distrbbution generalization where the test data contain examples that may be combinations of multiple infrequent features and have very low probability of appearing in the training set.
To complement our theoretical results, we construct simple examples that require simple composition prediction of the sum of digits for 3-digit numbers. Our experiment shows that in such cases one can indeed train simple networks that are capable of composition and memorization helps with both in-distribution and -oft---dditribution (OOD) generalization. We also observe that the model architecture plays an important role in determining whether the model has composition capabilities.
1.1 OUR RESULTS
Informally, our theoretical model considers data distribution D over vectors æ, where each feature I; appears independently with probability pi- These probabilities decay as p1 2 P2 2 .... 2 Pa (for example, P;- ~ i- follows a power-law decay), and each data is linear combination of features. As result, features with larger pt tend to appear frequently in the data, while those with smaller pi may appear only a few times or not at all. We refer the former as common features and the latter as long-tail features.
Our goal learn target model of the form fx)) (B., x) using n training samples of the form = (z) + &, where the label noise & ~ NN o²) and the noise level o 2 O. We focus on the minimum 2--norm solution, which memorizes the training set in our overparametrrieed setting.
We show that under this setup, the model can not only reliably learn common features that appear at F but also recover certain long-tail features that appear only once. This enables the
least (1) times model to perform well when tested on combinations of such features that were never seen together
during training:
Theorem 1 (Informal). Let D be a test distribution that differs from the training distribution 'D only in that each sample from D contains composition of t long-tail features, each of which appeared exactly once in the training data. Then, for the minimum ty-nrrm solution the test loss (expected loss on D) remains small, and the
loss (expected loss on D) is at most g²t.
The main challenge is that the frequency P: of common features can be as low as θ (2). resulting in a high variance. This issue is even worse for long-tail features, which appear even less frequently. As result, standard concentration bounds are insufficient in this setting. To address this, we leverage the combinatorial structure of the data matrix X and show that, under a suitable decay of pt, most data points contain at most one long-tail feature. This structural insight enables to establish meaningful learning guarantees, even when some features are extremely rare and variances are large.
Empirically, first verify the theoretical analysis in the linear setting. We then show that similar phenomena happen for simple neural networks. More concretely, we consider a "heavy-tailed" version of MNIST dataset where digits appear in decreasing frequencies, with 9 being the rarest. To introduce compositionality, each input consists of 3 randomly sampled MNIST images, and the task predict the sum of the digits.
We evaluate the composition capability of model through its OOD performance on test examples that contains at least one 9, with the other two numbers sampled uniformly. Most of the test cases involve 3-digit combinations that never appear during training. We observe that ResNet models exhibit compositionality when they process each digit individually to extract features, and then aggregated these features by a simple network even if the network has not seen particular 3-digit combination, the prediction is still accurate if it has seen each digit enough number of times. In contrast, a ResNet that processes the 3 images together as a single input performs significantly worse.
To further investigate memorization effect on generalization, we insert images from Omniglot the training data, where each Omniglot class only appear exuctly once. Experiments show that models with compositional ability can correctly predict on test data that involves two Omniglot images, provided that the model memorizes training data. However, models that either do not memorize due to large weight decay or lack compositional ability perform significantly worse.
We use Ô 2, Ô to hide polylog factors.
2

---

Published as a conference paper at ICLR 2026
1.2 RELATED WORKS
Real-world data often follow heavy-tailed distributions, where rare examples capture unique sub-concepts (Zhu et al. 2014). The works most related to ours are Feldman (2020) and Feldman & Zhang 2020). These papers demonstrated that memorization is necessary to achieve near-optimal generalization on long-tail data. Our work builds on this insight and takes it further, suggesting that memorization can also support the composition of long-tail data and features.
Memorization and long-tail data
Memorization in learning Researchers have discovered that deep neural networks can fit (i.e., "memorize") arbitrary labels and still generalize, challenging the classical bias-vate varriace intuition (Zhang al. 2017). Since then, there has been growing interest in understanding memorization from various perspectives (see the survey by Wei et al. (2024) for a comprehensive overview).
Various forms of memorization have been explored in different contexts, including label memorization in supervised learning (Feldman 2020 Feldman & Zhang 2020), counterfactual memorization
(Zhang et al., 2023). and exact memorization in language models (Tirumala al. 2022). These
findings have raised privacy concerns about the unintended memorization of sensitive data (Carlini al. 2019). In response, forgetting mechanisms and unlearning algorithms have been developed to
"ca remove such content without full retraining (e.g., Cao & Yang (2015); Garg et al. (2020)). In contrast,
our work focuses on the positive side of memorization, similar to Feldman (2020), showing how can support compositional learning over long-tail data distributions.
Compositional Generalization Generalizing to unseen compositions of known data or features has long history (Fodor & Pylyshyn| 1988) and remains a significant challenge. In recent years, benchmarks such as SCAN (Lake & Baroni 2018) and CoGS (Kim & Linzen (0200) have been introduced evaluate models' compositional abilities. Extensive analyses using these benchmarks have revealed that some language and vision-language models struggle with aspects like word order sensitivity, relationship recognition, or counting (Hessel & Schofield [021 Parcalabesou et al.) 2021 Yuksekgonul et al., (022). Nonetheless, recent work suggests that current language models do exhibit some capacity for compositional skill (Bubeck et al. 2023 Zhao et al. 2025).
To improve compositional generalization, researchers have proposed various methods, including data augmentation (Andreas 2019), architectural designs (Andreas et al.) 2016] Hudson & Manning 2018). and meta-learning approaches (Conklin et al. (022)) Efforts better understand compositional generalization continue in recent years (Wiedemer et al. 2023 Tang et al.) [025 Arora & Goyal
2023 Lippl & Stachenfeld] 2024). Our work builds on this line of inquiry, but we focus more on the
connection between memorization and compositionality.
2 PRELIMINARIES
In this section, we set up the details of our theoretical model.
Let [n] = 1,2,.... ., Vectors and matrices are denoted in bold. For a vector B E Rd and subset A C [d], define A EiEa A S,c,, keeping entries in A and setting others to O, where e, is the standard basis. We use standard notation O, Ω θ, S. to hide constants, and Ô, Ω, θ to also hide logarithmic factors like log(d) and log(n).
Notation
Target Model
We aim to learn the following linear model:
fx( = (B", x).
Here we assume largest coefficient is bounded max; |B&]| (().
Data Our data model is designed to capture the common long-tail distribution of features in real- world data (Zhu et al. 2014]. We assume each data point has only a few active features, with feature frequencies varying according to a long-tail pattern. For instance, in image classification each image may contain only a few objects, while the overall feature set is large and follows a long-tail distribution.
Formally, the data vectors x = .cI,...,II)) are drawn from the distribution D({p:)) defined as follows: given probability pı ... - pa > each feature I, {0, 1, -1} } is independently
3

---

Published as a conference paper at ICLR 2026
sampled from Bernoulii distribution with parameter ps. followed by random sign flip:
P( 0) = 1 Pi P(z; 1) P(z; -1) Pi
Let Σ B|æx | diag(pl.... ... Pa) be the covariance matrix, and we write D({p:) D(E).
We generate n data points {(2;; y1) ) i.idd according to this process with label noise &:
yi = [a:)) + & where a; D(E); & o0)
(1)
In many cases, we assume that the feature probabilities P; follow power-law decay:
p. min /Za/
for some constant a' > with normalization constant Z, = Eied" i0 The truncation at I is only make sure p; E [0, 1] valid probability. Note that ||||=||] each data æ will be roughly s-sparse. In the rest of the paper, for a data a we will often call the top-k entries Zgk as common features and remain entries Σ>b as (long- )tail features for a threshold k chosen later. Also denote P>* == Ei> Pi as the tail probability and Psk == Eisk P; the head probability. The tail probability can be bounded by the claim below.
(ignoring the truncation) so
Claim 1. For ps follows power law decay (2 with a 1 + Ca for any constant Ca and pk < 1 (i.., k 2 ((s)/a)), we have p> = (sk and pk: (sk
Our data model is intended reflect the long-tail structure, and the power-law decay assumption is common in prior theoretical analyses (e.g.. (Bartlett et al. 2020; Hastie et al. 2022 Lin et al., 2024)).
Choice of parameters Let Clog = polylog(d) be a large enough polylog factor. We assume n//lo d/Gog and n" + In d for any constant 0. concrete example is 8 = @(1) n = d' for constant e E (0, 0.99) and Clog < k < n//ciog Casual readers may assume < polylog(d) < k & n & d. The threshold & between common and long-tail features will be chosen later. Intuitively
< Glog
require pı (1) common features appear at least polylog times.
Algorithm and loss
We use a linear model and run gradient descent on square loss. That is
- n Σ (1, a;) - y1)
1 n
L(3)
X - v112
We run gradient descent from 0 initialization, so the final estimator is
e = (X x) x y.
This estimator is also known as the min- interpolator/solltton.. Similar overparametrized linear models and kernel-models are standard in previous theoretical works (c.g., Bartlett et al. (2020);
Belkin et 2019 Jacot et al. 2018)).
We focus on the overparametrized regime where d > In the noiseless case a = 0, such interpolator memorizes all training data. In noisy case 0, the minimum training loss may be above even in such overparametrized setting (because there may be many samples that only use smaller number of features), so the solution may not interpolate the data. Still, represents a global minimum with the smallest & norm among all such minima.
Since both our data generation process and predictor are linear, composition happens automatically if model learns the 3 values for subset of features accurately, it will perform well for any data that uses a combination of features from this subset.
Performance Measurements: In- and Out-of-Distributin Test Loss mance, we use the standard test loss:
For in-distribution perfor-
EnDi(($
( 3T- {)
To evaluate the model's 's composition capability (its ability to perform well test examples that are combinations of training features never appear in training data), we measure its OOD performance using the test loss defined below.
4

---

Published as a conference paper at ICLR 2026
Let F [j E [d] 3i [n] s.t. (2.), # 0} be the set of features that appear in the training data. Let F S F be subset of these features. We define D as a modified distribution of D, where each feature in F is guaranteed to be non-zero in every sample, while the rest of the data is generated according to the original distribution D: each feature 2; not in F appears with its original frequency pi. and non-zero values are sampled uniformly from +1.
For example, D (22k,42) A denotes distribution where 222; 2:4k A O. While the model might encounter training examples where only 228 or T4k is non-zero, it is very likely that it does not see examples where both non-zero simultaneously. The OOD test loss is defined as:
Be- -BTx))
3 MEMORIZATION HELPS OUT-OF-DISTRIBUTII GENERALIZATION
In this section, we present our main results, which show that memorization can help with generaliza- tion by composition of long-tail features, as measured by test loss and OOD loss. We present results for both the noiseless case (a 0) and the noisy case (a > 0), respectively.
3.1 NOISELESS CASE
We start with noiseless case. We show below the test performance of the estimator 3 that goes to when n goes large. The intuition behind the proof is that we can recover all feature that shows up at least O (In
2 d) times, so their estimation error goes to O.
Theorem (Test loss). Suppose data generated from (T) with noise a = O, then with probability at least 0.99 over the data generation process, the following hold with satisfying np, O(n d) and P>k < Cp with any constant Cp:
k
In
kp In' d
E (===8"=)''SP-
+
+ 22 In d.
n²p:>k
When data follows power law decay
2 with a = 1 1 ca with any constant ca > 0
In2 d
2) S EE x 3
ns
Moreover, establish the following OOD generalization guarantee, which reflects the model's compositional ability and shows that it can still perform well despite memorizing all training data. As shown in the proof, this is made possible by the composition of features that the model memorizes.
Theorem 3 (OOD performance). Under same condition as Theorem 2 then with probability at least 0.99 over the data generation process, there is feature set F. C F with size |F] 2 (1 O ([max{Px /22x P. In² F that contains almost all features show up in data such that for any feature set F F we have
EenDy II x Ba (TT)) P>* + kln d n²p>e +
In d
kp' In
+ 23 In d.
n
When data follows power law decay with = 1 + ca with any constant ca > 0 we have
| 2 (1-6
max
lu²
2
(In
}| and
1n2 d 1-1
EaND, 1(3T x - B3 [=))) Ss
m18
The proof ideas for both results are similar. We show that all features that appear least O(nn d) times can be recovered, as well as a significant fraction of long-tail features that appear less frequently in the training data. Intuitively, this is the best we can hope for, since common features may appear only w1)) times, and loig-tail features may appear just once. We provide more details in Section
These results suggest that memorization can be useful for learning compositions involving long-tail features. This may offer insight into why memorization is necessary in certain learning problems that require compositional ability. We further validate our findings in the experimental results (Section
5

---

Published as a conference paper at ICLR 2026
3.2 NOISY CASE
We now extend the above noiseless case (a 0) to the noisy case (a > 0). Similarly, we show the test loss small (roughly @(o²k/n)).
Theorem 4 (Test loss). Suppose data generated from ① with noise 1, with probability at least 0.99 over the data generation process, the following hold with k satisfying npp O(In d), P>k I Cp with any constant Cp and np² < c.for a small enough constant e:
Ex [B 3- [)) SPsk o² (kind + (k2 (*=1 + In P>k Ind)
where the first expectation is over data generating process of common part of training data X sk. When data follows power law decay
with =2 + Ca with any constant >0
II d'
Inn
Ex Exsa | - 3 x+T=)
+
sln
718
718
Similar to the noiseless case, we have the following OOD guarantee that measure model's composi- tional ability: the error is roughly o²t, where t is the number of long-tailed features present in the OOD distribution.
Theorem 5 (OOD performance). Under same condition as Theorem then with probability least over the data generation process, consider any feature set F C FF Fo contains any long tail features show up in data, we have
122 h22nn (K
[(0 - --- SP>A o2|5
+ +ind).
n
where the first expectation is over data generating process of common part of training data X sk- When data follows power law decay
with = 2 Ca. with any constant > 0
In
Exga (B x 3T 1T
x)
+ + +21Filnd
71
These results suggest that the benefits of memorization for compositional learning persist in the presence of label noise, although they require stronger assumption on the frequency decay.
4 PROOF IDEA FOR NOISELESS CASE
In this section, present the proof ideas for the noiseless case. The proof for the noisy case follows a similar idea, but is slightly more complex.
A common strategy in analyzing the least squares estimator is to apply matrix concentration techniques to estimate X X and its inverse. However, in our setting, such a matrix is not going to concentrate for long-tail features that expected to appear less than constant number of times. Whether feature appears or not has huge impact on the pscudoinverse (X X)', Instead of concentration, we rely the combinatorial structure of the data matrix X, described in the lemma below. Roughly speaking, the lemma shows that most data points contain either zero or one long-tail feature.
Lemma (Structure of X, informal of Lemma A.Ipp Suppose data generated from I with probability at least 0.99, the following hold with & satisfying vpp = ((n 2 d) and p>* S - Co with any constant ep:
1. There exist at least ( P>k)) samples whose non-zero entries are only within first k entries. That
Sal = Ki [m] (æ.); = 0, 0, k3l ( -p>k))
Moreover, the dimension spanned by these samples in So is k.

---

Published as a conference paper at ICLR 2026
2. There exist at least (np:=<1 - pp>k)) samples that only have exactly one non-zero entry in long-tat tail entries (not in the first lo entries). That is
|S = Hi E [m] 38 > l such that (axi) + 0 and (mx:) 0, > k.j + 2) = (mps>
3. Denote the set of features show in So and S as
Fo [j [d] 3i So s.t. (xi), + 0}. FI= [d] 3i E S s.t. (2:)) + 03.
We have the total number of features shown up in data is |F| k + (mpp>k) and the number of features shown up in So and S is at least
FOU 2 (1 - - (max P> P In d))) |F]
Note that in the noiseless case, we can achieve 0 training loss. Thus we know every sample must have training loss. From the lemma above, we can see that there are ( - p>s)) samples involving only the k common features. Therefore, the common component Ba is uniquely determined by these data points when n.
Moreover, once the common features Begx identified, many long-tail features 8, those that appear only alongside common features and not with other long-tail features, can also be exactly recovered. This is formalized in the following lemma:
Lemma (Recovery of 3*). Suppose data generated from ① with noise 0, for k that satisfies the condition of Lemma 6 we have
1. Common features (Top-k entries) are recovered: Bgr = Bick
2. Most of long tail features shown up in data ((last-d k entries) are recovered:
Ki [d] : ==; /| 2 00max P In df).
3. | || $ 1 and B 0 for F.
Using the parameter recovery result above, Theorem 2 and Theorem 3 by applying Claim
derive the performance guarantees stated in
In the noisy case, we require stronger tail probability decay assumption of data X to show that (with high probability) every data point contains at most one long-tail feature. Even with this assumption, the key challenge for the noisy case is that the minimum & norm solution may not have 0 training loss, hence we can no longer say that the training loss is on every individual training samples as in the noiseless case. However, one sample, then the training loss for that particular sample must be O and the long-tail feature will be estimated correctly (up to noise level a) with high probability. Similar argument can be generalized when long-tail feature appear in few training samples. We leave the details to Appendix B
show that
in this setting, if long-tail feature only appear in
5 EXPERIMENT RESULTS
In this section, we first validate our theoretical results empirically, and then we show that similar ideas can be extended simple neural network models. All experiments, unless otherwise specified, reach near-zero training loss and therefore memorize the training data.
5.1 EXPERIMENTS ON LINEAR MODEL
We follow the setup in Section where the parameters are chosen as: n = 1000, d = 10000, s = 5. ripa- = 10 and & (3i ..... 35) with 3 -011 and report results averaging over 50 runs. In this setting the most frequent "long-tail" features would appear 10 times in expectation. As we can see in Figure [bb] for most values of the error the long-tail tail features is roughly proportional to the noise level o. This is the same as the theoretical prediction as many of these long-tail examples appear only once and their error is slightly larger than the noise, while long-tail examples that appear
7

---

Published as a conference paper at ICLR 2026
2P10 Mnn Pri v8.
Nele Level
Cat 2010 Too
(a) Average Error on Common Features with Different a and
(h) Average Error on
(c) Ih-of-Distribution Test
(d) Out-of-Distributio
Long-tail Features
Loss
Test Loss
with Different and
Figure I: (a)(b) Average Error on Common and Long-tail Features on Linear Model; (c)(d) In- and Test Loss on Linear Model
more often have smaller error. Figure shows that common features learned well when a is not too small. Figure TdTdsshows that the in-distribution and out-of-distributiin test losses are small in Theorem 2 3 and Since the test losses for 0 and a 0.05 are very small, their curves overlap in the plot.
We also observe that when is small (a 1), both the in-distribution and out-of-distribution test losses become higher, and the feature errors also increase. This is expected because in such cases the long-tal tail features appear more often in the training data, not often enough for concentration bounds but often enough to weaken the combinatorial structure our analysis relies on.
5.2 TASK THAT REQUIRE SIMPLE COMPOSITION
Next, we consider simple task that would benefit from composition. We constructed a new dataset based on MNIST. Each sample in this dataset consists of three randomly selected MNIST digit images in MNIST training set, stacked along the channel dimension. The task is predict the sum of digits. Specifically, given that original MNIST images are of size 28 28, our new samples take the form of 3 x 28 x 28, where each "channel" corresponds to different digit. The digit selection also follows Zipf's s law distribution, meaning that lower digits (e.g.. '0') appear more frequently, while higher digits (e.g.. '9') appear less frequently.
To investigate the composition behavior and OOD generalization, every test sample is required to contain at least one digit '9', introducing a distribution shift between the training and test sets. All test samples are drawn from the MNIST fest set. Importantly, this ensures that the digit '9's used at test time have never been seen by the model during training.
Model Architecture We consider several models using ResNet-18 as our backbone. The first few models process each channel separately through a ResNet-18 network. That is, given a sample with three stacked digit images, compute the feature representation gi (second to last layer) and label (ft) for each channel independently using the standard ResNet- 18 forward propagation. The final model output is obtained by some aggregation over the individual channel outputs. For Sum, the final output is simply the sum of fi's; for Linear, the final output is a trained linear layer on top of the second-to-lan layer gi 's (where the features are concatenated); for 2-layer, the final output is trained 2-layer network on top of the second-to-lass layer features ss Both the ResNet- 18 part and aggregation layers are trained simultaneously.
We also consider Cross-channel, which is ResNet-18 model that is directly applied to the stacked images as if the channels are color channels (therefore the information between different images are mixed up starting from layer 1).
The training set has 32,000 samples, with number appear 77,435 times and number appear 955 times. We change the number of times 9 appears study the relationship between that and the test performance. For the test set, we enforce that each sample has at least one position equal to number 9, where the two other positions we have in the training data, with high probability most number combinations in the test set will not appear in the training set.
sampled uniformly from 0-4. Note that with the number of samples
8

---

Published as a conference paper at ICLR 2026
Test Losa va. Label 5 Oecurvencees on MediGed MINIST Dataset
Tost Loss vs. Label Ocourrisces on Modified MNISS Dataset
Normal RecNet
Sam
Liwarr
Laye
1.75
Meen Value THIS
0.90
40
8
20
60
39
8
Number
Tabel Training
Number
Training
(a) Test Loss of Sum. Linear, and 2-Layer Models
(b) Test Loss of Cross-channel Model
Figure Test Performance Comparison Across Sum, Linear, 2-layer and Cross-channel Models
Our results Figure show that Sum, Linear, 2-layer models all perform well on the test distribution. Since the digit '9" is rare in the training data and therefore not learned well by the models, this good performance suggests that these models exhibit some form of compositional behavior by leveraging memorized instances of '9". On the other hand, Figure 2h shows that Cross-channel model performs significantly worse on the test distribution, indicating that compositional capability still depends on the model architecture.
5.3 EFFECT OF MEMORIZATION
To understand the effect of memorization, we further introduce even rarer examples. We consider a similar setting the previous subsection. Except that in the training data, we choose 10 classes from Omniglot (Lake et al. 2015) and select image from each class. That image is assigned a label of 0-9. Each Omniglot image only appears exactly once in the training data (as one of the 3 images in one of the training data). The task is still to predict the sum of labels for the images.
For the test data, we consider images which contain two of the images from Omniglot (for the images that have appeared in the training data). Such test examples never appear in the training data and would not be close any of them in Euclidean embedding distance.
As in Table despite only having seen the data once and the test data being significantly different, for Sum, Linear, 2-layer models the performance the test set is still reasonable when don't 't use any regularization and make sure the model memorizes the training data. On the other hand, with weight decay, even though the training loss only increased slightly, the test performance become significantly worse. This suggests that memorization enables the model to develop a form of compositional ability that leverages the memorized Omniglot data, resulting better generalization for memorizing models compared to those that do not memorize. Cross-channel model does not perform well in this setting, further supporting our findings that the composition ability depends on architecture.
Table 1: Memorization behavior of ResNet variants under different weight decay (WD) settings
Model
WD (Memorization)
WD 0.5 (No Memorization)
Sum
Test/Train Loss: 0.1760/0.0004
Test/Train Loss: 2.8744/0.0245
Linear
Test/Train Loss: 0.1662/0.0004
Test/Train Loss: 1.5539/0.0505
2-layer
Test/Train Loss: 0.1351/0.0010
Test/Train Loss: 0.6447/0.0264
Cross-channel
Test/Train Loss: 22.967 1/0.0023
Test/Train Loss: 23.6506/0.0375
CONCLUSIONS
In this paper, we showed that memorization can contribute more to generalization and out-of- distribution generalization when the model has composition capability. Our theory builds on simple linear setting and introduces new techniques for handling long- tail features. Empirically, we show that similar intuition extends to nonlinear settings, and whether models have composition capability partly depend on their architecture. The main limitation of work is that the theoretical result

---

Published as a conference paper at ICLR 2026
is restricted to linear setting, while the experiments small networks for supervised learning problems. Our focus on the positive role of memorization in enabling composition and illustrating when this occurs. There also cases where memorization can hurt composition, for example when long-tail features are spuriously correlated with other features or labels, or when they are mislabeled. We hope this work serves starting point for understanding memorization and composition in more complicated models that go beyond supervised learning.
ACKNOWLEDGEMENT
This work is supported by NSF Award SANS2001889, MZ also acknowledges the support of NSF TRIPODS II DMS 2023166.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Jacob Andreas. Good-enough compositional data augmentation. arXiv preprint arXiv: 1 1904.09555 2019.
Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein. Neural module networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 39-48, 2016.
Sanjeev Arora and Anirudh Goyal. theory for emergence of complex skills in language models. arXiv preprint wwXiv:2377.199.. 2023.
Marco Baroni. Linguistic generalization and compositionality in modern artificial neural networks. Philosophical Transactions of the Royal Society B, 375(1791):20190307, 2020.
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(48):30063-3007) 2020.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical ilas-variane trade-off. Proceedings of the National Academy of Sciences, 116632):15849-1854 2019.
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science, 1(7):1167-1180, 2020.
Sébastien Bubeck, Varun Chadrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, et al. Sparks of artificial general intelligence: Early experiments with gpt-4, 2023.
Yinzhi Cao and Junfeng Yang. Towards making systems forget with machine unlearning. In 2015 IEEE symposium on security and privacy, pp. 463 480. IEEE, 2015.
Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernej Kos, and Dawn Song. The secret sharer: Evaluating and testing unintended memorization in neural networks. In 28th USENIX security symposium (USENIX security 19). pp. 267-284, 2019.
Nicholas Carlini, Daphne Ippolito, Matthew Jagielski, Katherine Lee, Florian Tramer, and Chiyuan Zhang. Quantifying memorization across neural language models. The Eleventh International Conference on Learning Representations, 2022.
Henry Conklin, Bailin Wang, Kenny Smith, and Ivan Titov. Meta-learning to compositionally generalize. arXiv preprint 14X.v:2106.04252, 2021.
Vitaly Feldman. Does learning require memorization? a short tale about a long tail. In Proceedings of the 52nd Annual ACM SIGACT Symposium Theory of Computing, pp. 954 959, 2020.
Vitaly Feldman and Chiyuan Zhang. What neural networks memorize and why: Discovering the long tail via influence estimation. Advances in Neural Information Processing Systems, 33:2881-288 2891, 2020.
Jerry A Fodor and Zenon W Pylyshyn. Connectionism and cognitive architecture: critical analysis. Cognition, 28(1-2):3-74 1988.
Sanjam Garg, Shaf Goldwasser, and Prashant Nalini Vasudevan. Formalizing data deletion in the context of the right to be forgotten. In Anmual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 373-402. Springer, 2020.
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. Advances in neural information processing systems, 30, 2017.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. The Annals of Statisties, 50(2):949 9866, 2022.
11

---

Published as a conference paper at ICLR 2026
Jack Hessel and Alexandra Schofield. How effective is bert without word ordering? implications for language understanding and data privacy. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 1 11th International Joint Conference on Natural Language Processing ( (Volume 2: Short Papers), pp. 204-211, 2021.
Drew A Hudson and Christopher D Manning. Compositional attention networks for machine reasoning. arXiv preprint 1803v
2018.
Dieuwke Hupkes, Verna Dankers, Mathijs Mul, and Elia Bruni. Compositionality decomposed: How do neural networks generalise? Journal of Artificial Intelligence Research, 67:757-795, 2020.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Najoung Kim and Tal Linzen. Cogs: A compositional generalization challenge based on semantic interpretation. arViv preprint arXiv:20100054665, 2020.
Brenden Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of eequuence-to-sqquene recurrent networks. In International conference on machine learning, pp. 2873-2888 PMLR, 2018.
Brenden M. Lake, Ruslan Salakhutdinov, and Joshua B. Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 350:1332 1338, 2015. URL /attps://api
semanticscholas ortp/oorps11::1790000
Licong Lin, Jingfeng Wu, Sham M Kakade, Peter L Bartlett, and Jason D Lee. Scaling laws in linear regression: Compute, parameters, and data. Advances in Neural Information Processing Systems, 37:60556-60606, 2024.
Samuel Lippl and Kim Stachenfeld. When does compositional structure yield compositional general- ization? a kernel theory. arXiv preprint arXiv:2405. 16391, 2024.
Letitia Parcalabescu, Michele Cafagna, Lilitta Muradjan, Anette Frank, lacer Calixto, and Albert Gatt. Valse: A task-independent benchmark for vision and language models centered on linguistic phenomena. arXiv preprint 1rXiv:2112.07566, 2021.
Cheng Tang, Brenden Lake, and Mehrdad Jazayeri. An explainable transformer circuit for composi- tional generalization. arXiv preprint arXiv:2502.15801 2025.
Kushal Tirumala, Aram Markosyan, Luke Zettlemoyer, and Armen Aghajanyan. Memorization without overfitting: Analyzing the training dynamics of large language models. Advances in Neural Information Processing Systems, 35:38274-38290, 2022.
Joel A Tropp et al. An introduction to matrix concentration inequalities. Foundations and Trends@ in
Machine Learning, 8(1-2):1-230) 2015.
Jiaheng Wei, Yanjun Zhang, Leo Yu Zhang, Ming Ding, Chao Chen, Kok-Leong Ong. Jun Zhang, and Yang Xiang. Memorization in deep learning: A survey, arXiv preprint arXiv:2406.0388 2024.
Thaddäus Wiedemer, Prasanna Mayilvahanan, Mathias Bethge, and Wieland Brendel. Compositional generalization from first principles. Advances in Neural Information Processing Systems, 36:6941- 6960, 2023.
Mert Yuksekgonul, Federico Bianchi, Pratyusha Kalluri, Dan Jurafsky, and James Zou. When and why vision-language models behave like bags-of-words, and what to do about it? arXiv preprint N11::2210000133, 2022.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understand- ing deep learning requires rethinking generalization. In International Conference on Learning Representations, 2017. httphtttp////ppereeett
nwt. www.roorrmmiooooo worrmm211syyyyBBBeee
Chiyuan Zhang, Daphne Ippolito, Katherine Lee, Matthew Jagielski, Florian Tramèr, and Nicholas Carlini. Counterfactual memorization in neural language models. Advances in Neural Information Processing Systems, 36:39321-39366 2023.
12

---

Published as a conference paper at ICLR 2026
Haoyu Zhao, Simran Kaur, Dingli Yu, Anirudh Goyal, and Sanjeev Arora. Can models learn skill composition from examples?, 2025. htt.a/tpp//ax....o////b///////// http:///////////999999900
Xiangxin Zhu, Dragomir Anguelov, and Deva Ramanan. Capturing long-tail distributions of object subcategories. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition. pp. 915-922, 2014.
13

---

Published as a conference paper at ICLR 2026
A OMITTED PROOF FOR NOISELESS RESULTS
In this section we give the detailed proof for the noiseless results Theorem 2 and Theorem 3
Theorem 2 (Test loss). Suppose data generated from ① with noise = O, then with probability at least 0.99 over the data generation process, the following hold with l satisfying np, = O(n d) and P>k I Cp with any constant cp-
Eg - 3" x) P>k + kIn d n² p²
In
kp In d
+ p In d.
n
When data follows power law decay
with 1 + Ca with any constant > 0
In d ns
E B x 3 x:)
Theorem 3 (OOD performance). Under same condition Theorem 2 then with probability at least 0.99 over the data generation process, there is feature set F S F with size |F|
(mmxx {pk /p>,, 22 In² []])]F] that contains almost all features show up data such that for any feature set F F we have
kln d n²p> n
In d
kp In d + 2 In d.
EunD EE-D=1( x 3 x=)=>?
n
When data follows power law decay 2
with 1 + with any constant ca > 0 we have
F 2 -1-6
max
In²dd d
(In
| and
In? d
1
EaNDy [13 x - -
[TTo) Ss
718
A.1 PROOF OVERVIEW
We first show the structure of data X below: most of data has only common features; for the data that contains long-tail features, most of them has only one long-tail feature. The proof is based column/row-wise concentration exploit the combinatorial structure of X instead of the concentration of whole matrix, which is difficult to handle due to high variance.
Lemma A.1 (Structure of X). Suppose data generated from ( with probability at least 0.99, the following hold with k satisfying npk O(n d) and p>* Cy with any constant cp:
There exist at least (nn(1 - p>*)) samples whose non-zero entries are only within first entries. That is
1Sol = Hi E [n] : (xx)) vj > kH n21 P>*) - (11on1l11ppppna
Moreover, the dimension spans by these samples in So is k.
2. There exist at least ((np>=(1 - p>>)) samples that only have exactly one non-zero entry in long-tail -til entries (not in the first ie entries). That is
|S :=
[n] 30 > k such that (æ:)) + and (æ:), = 0, Vj k.j + e}l
21 p>*) - 0 O(OnO///nnp>1 (1-p>+))
and |S1] S np>k-
3. Denote the set of features show up in data as
F= E [d] Ei E [n]s...(ax.); # 0).
Similarly define Fo and for So and S as the set of features show up in So and St-
We have total number of features shown up in data is [F = + ((ppss) and number of long tail features is {Fi (Fol 2 O(psx/ lu² d)). Moreover, the number of features show up in So and S₁ is at least
Fo U.F. (1 (max / 22 ln2 (d)dd)) [F]
14

---

Published as a conference paper at ICLR 2026
Given the structure of the data X, obtain the following parameter recovery guarantee. Intuitively, since most the data contains only the common feature, the common part is uniquely determined. Then, for the data points that contain only one long-tail feature, the long-tail part can also be uniquely recovered once common part recovered. Together, these observations lead to the parameter recovery result presented below.
Lemma A.2 (Recovery of )*) Suppose data from ① with noise 0. for k that satisfies the condition of Lemma A.7 we have
1. Common features (Top-k entries) are recovered: Bok = B
2. Most of long tail features shown up data ((last-d entries) are recovered:
E
[
B =
2 ((max(pa/PPaa /Ppp//PPs:0 Pr In d)).
F
3. | 12 and B: 0.for i F.
As corollary, we choose the threshold & under our data generation process 2 to get the following result.
Corollary A.3. Suppose data generated from L with noise 0 and follows power law decay 2 with a 11 Co for any constant Ca 0, then we have for k. ((ns/ In d) (i.e. vipa-
O(n d))
1. Common features (Top-k entries) are recovered: Bgk = Bizk
2. Most of long tail features shown up in data X (last-d 1 entries) recovered:
{ i E
[d]
B = B3
In d
ga
2
(In d) 6 ))
21-6
max
FF
n18
n
3. | S 11 and 3r = 0 i E
Proof. The proof follows from Lemma A.2 and Claim by choosing k = (((ns/ In2 d)//aa (i.e., np: = (In d)).
Now, given all parameter recovery results above, we can get the test loss and OOD loss guarantee. We give the details in the next section.
A.2 PROOF OF MAIN RESULTS
Building on the results from the previous section, we are now ready to present the proofs of the main results. Both proofs mostly follow from the parameter recovery guarantee in Lemma A.2 and its specialization to power-law data in Corollary AA.
Theorem (Test loss). Suppose data generated from ① with noise a = O, then with probability at least 0.99 over the data generation process, the following hold with satisfying npk O(nn d) and
P>k < 1 Cp with any constant Cp:
k d
In
kvz In d
T EAD x -3" ( P>k +
+ 13 In d.
n?p>k n
When data follows power law decay
with 1 + cn with any constant e,
In d
Eg (33 x 3r 21
n..
15

---

Published as a conference paper at ICLR 2026
Proof. From Lemma A.2
we know
Em- 3 =)
Σ Pi(B; -,) ~ Σ P,()))² + Pk|F UF))
1>
SpS# klu'
In d
kp In
n² +
+ p In d.
When data follows power law decay from Claim that p>* S Indd 1- and get the result.
know A ((ns/ In d) from npx OInn d)).
Then
Theorem 3 (OOD performance). Under same condition as Theorem 2 then with probability at least 0.99 over the data generation process, there is feuture set F C F with size [F] 2 (1
O (maxx(pk/) ppx//>>:PP P2A In2 d])) that contains almost all features show up in data such that for any feature set F F we have
kln 3 d n²p>>
In'
kp In d + 2 In d.
Ex-D [[B x 3O x)
P>*
n
n
When data follows power law decay with 1 + ca with any constant ca we have
|F| 2 (1 - 0 max
{
{ ln2
s (In 0
|| and
In2 d
EnNDy Dy [13T x gxxxx)²1 Ss
Proof. It suffices let =o From Lemma A.2
know the bound on size |F]
and
x
Σ 1
(r 3,)2
Σ (B.
33
Σ
pi()))2
iEF
+ knn 4 d
In d
kp In
Sp>k
+ 2 In
d.
n² n
where the calculation is same in Theorem 2
When data follows power law decay 2 similar in the proof of Theorem we know the bound.
Size of follows from Lemma A.3
A.3 DETAILED PROOFS
Here we give the omitted proofs in Appendix A.I
Lemma A.1 (Structure of X). Suppose data generated from (T. with probability at least 0.99, the following hold with le satisfying npt O(n? 2 d) and p>* S Cp with any constant cp:
1. There exist at least (nn(1 -p>k)) samples whose non-zero entries are only within first entries. That is
SS == li [n] (æx)) 0, vj > kH 2 n21 P>+) -
Moreover, the dimension spans by these samples in Sy is k.
2. There exist at least ((pp> - -p>))) samples that only have exactly one non-zero entry in long-ta tail entries (not in the first le entries). That is
|Si| : 1= E [n] 72 > lo such that (x:)) + and (æ:)) = 0, > k.j + e)l
2np=a(1 p>*)= O(Vnpspk P>k))
and |81] S mp>k.
16

---

Published as a conference paper at ICLR 2026
3. Denote the set of features show up in data
= E [d] 3i E (n)). + #0}.
Similarly define Fu and for So and S1 as the set of features show up in So and St.
We have total number of features shown up in data is |F| = k + ((np>k) and number of long tail features is [Fi /Fo 2 (ps*k/ (pp In d)). Moreover, the number of features show up in So and S1 least
FoU 2 (1 - (max(pk// />> Sx ln d})) 1F]
Proof.
We show one by one.
item 1 For any data æ E IRd generated by 2 we first have the probability
P (z: 0, Vi k) p.) 1 p>*
where we use Lemma C.1
Since each data generated i.i.d. following 2 by standard Chernoff's bound, we know with probability least 0.999
| = i E [n] (z:), O, Vj k}} n(1 P>*) O(vn(1Onnnn)1 -P>a))
As for the dimension, since npt Z we can show X
So.gk X So. has full rank as in Lemma C.2
where X So.Sk is the data matrix X E Rexd constrained with only rows in Sp and first k columns.
item 2 Similar as item 1, for any data æ E Rd generated by 2 we first have the probability
P P
> le such that xy * 0 and xj 0, Vj > k. * E)
Σ Pe
II -u1-ppll pa) Σ pe(1 P> pe) 2 P> P>k),
k>
where we use Lemma
We can also see the above probability is at most P>k-
Since each data is generated i.idd following 2 by standard Chernoff's s bound, we know with probability least 0.999
S = li [n] 3 > & such that (æx)e # 0 and (æ,)g O. V, kij + Eyl
2mp>4(1 - P>*) - /p>> - (1=p>*))
and [S1] S np>k-
The total number of features show up in data is upper bounded by le + | 12 (top-k entries and all non-zero entries in the remaining entries). Thus, we know |J]| = k: O(mp><) by Chernoff's bound.
item
For every feature not in top-k: it at most shows up in O(nps + /vp:) O(n² d) data by Chernoff's bound and np: npx (In² d). Therefore, the total number of features show up in So and S is least Fo UFI > (S |S d) 2 k+ Ompssk/ In2 d). So number of long tail features is at least [ Fol O(np>*/ In2 d).
On the other hand, from item and we can see the probability of data not in So U Si is at most p so the total number of such data is at most O ( 1, np? by Chernoff's ' bound. Thus, the total nonzero entries (not include top-k entries) in these data is at most ( [1, max 1 p }PP=+)) = O (max 1, 1). This implies the number of features show up not in So and S1 is at most |F Fo U F < (max(11 2
1). Hence, the number of features show up in So and S is at least
FOU =
F
1 1 |F Fo FUAIFBUE 2 FF 1+ ((max(pe/p>a 23, ln2 d))
= =| θ (max (px. hptppppp.kkk... P3 In d))).
17

---

Published as a conference paper at ICLR 2026
Lemma A.2 (Recovery of (*). Suppose data generated ① with noise O. O. k that satisfies the condition of Lemma A.7 we have
1. Common features (Top-k entries) recovered: Bok Bixx
2. Most of long tail features shown up in data ((last-d entries) are recovered:
{ i E
[d]
2 ((max(pk/P>te P> P3 In d)).
F
3. [
11 and B: fo F.
Proof. We prove one-by-one. The results mostly combination of Lemma A.1 and Claim]
For common features (top-k entries), suffices to only look data in So. that is data only have non-zero entries in top-k entries. From Lemma A.1 we know the only solution 3gx B3
item 1
item For long tail features, we only focus on those show up in Si (data only have 1 non-zero entries in tail entries). From item 1, know top-k entries recovered. Thus, the only solution to data in S1 is 33 8 for i F1. From Lemma A.1 we know Fi U.1 covers most of the features show up in data: Fo UFI 2 (1 (max P> P In? d))] Thus, from above we know the B3 for i E Fo U Fi are recovered.
item 3
This is directly implied by the meaning of min-l2-norm interpolator.
B PROOFS FOR NOISY CASE
In this section, we give the proofs for the noisy case results as below:
Theorem 4 (Test loss). Suppose data generated from ① with noise a S 1, with probability at least 0.99 over the data generation process, the following hold with l satisfying npx = O(n d),
P>k $ 1 Cp with any constant Ep and np² cfo a small enough constant
Ex E 3 x1) SPOA + o² (klnd + +("2n'
+Ind) p>s ind)
where the first expectation is over data generating process of common part of training data X Xsk- When data follows power law decay with = 22+ Ca with any constant >0
[112 dl
1-1 +
(n2 ddd
1-1
Exca E x - 3 xT)))
02
s In
m.8
ns
Theorem 5 (OOD performance). Under same condition Theorem 0.99 over the data generation process, consider any feature set F features show up in data, we have
then with probability at least
Fo contains any long tail
k (2
Ex LEWD 1(3 -3 SP + o
+ ind).
where the first expectation is over data generating process of common part of training data X sk
When data follows power law decay 2 with = 2 Ca with any constant > 0
1
In2
Excx (E x T
S
+ +o2
ns
18

---

Published as a conference paper at ICLR 2026
B.1 PROOF OVERVIEW
Here we give the proof overview of noisy case results.
Besides the structure of data X as described in Lemma A. structure under a stronger tail decay assumption. Now we can show all data has either or long tail feature.
have the additional following
Lemma B.1. Under Lemma A.1 with additional requirement up f a small enough constant G, then besides the conclusion of Lemma A. we additionally have there is no combination of long tail features:
S221 = Ki E [n]: 361 + l2 > k such that It, It, + 00}
Given the structure of the data X, Intuitively, the common features can be recovered accurately, since most of the data contains only common features (similar to the noiseless case). For the long-tail features, consider the simplest scenario where a feature appears only once in the entire dataset. In that case, the corresponding sample must have zero training loss, so the feature general case follows a similar argument: we can control the training loss for samples that contain a given long-tail feature.
establish the following parameter recovery guarantee.
be recovered up to the noise level The
Lemma B.2 (Recovery of (²), Under Lemma A.I and Lemma B.1 with probability 0.99 we have (in below expectation over data generating process of common part of training data sk)
1. Common features (Top-k entries) are recovered:
||0cx
S 0² ( Psa)
E Exce
Den
2. All long tail features shown up in data X(last-d - entries) are recovered upto noise level:
Ex 113: 8111 0² (k2In2d + +kpx + Ind
3. 3, 0 for all i (F..).)
As corollary, we choose the threshold under our data generation process 2 to get the following result.
Corollary B.3. For data generating process 2 of power law decay, with a = 2 + Ca with any constant Co > O, we have for ((ns/ In² d) (iee. upt = 0(n 2 d))
1. Common features (Top-k entries) recovered:
(In (nd) S o
A
Exgo
B
Dek.
n
2. All long tail features shown up in data X X(last-d entries) are recovered upto noise level:
113 111 o² Ind,
where expectation is over data generating process of training data.
3. 3, 0 for all UF..
Proof. The proof follows from Lemma B.2 and Claim by choosing A: = O((ns/ laassll? d)//ay (i.e., npt (In d)).
B.2 PROOF OF MAIN RESULTS
Building the results from the previous section, results. Both proofs mostly follow from the parameter recovery guarantee in Lemma B.2 and its specialization to paw data in Corollary B.3
ready present the proofs of the main
19

---

Published as a conference paper at ICLR 2026
Theorem 4 (Test loss). Suppose data generated from ① with noise 1, with probability at least 0.99 over the data generation process, the following hold with k satisfying upp O(n d), P>k S Cp with any constant cp and napz < c.for a small enough constant
( (kimd + +("= + Ind
in?
P> + o² Ex BENDI( x x)
P>x Ind)
where the first expectation is over data generating process of common part of training data Xsk- When data follows power law decay
with + ca with any constant Co. >
In d
In d
Ex E x 3 1> S
+ 0²
In d
12.8
718
Proof. From Lemma B.2 we know
Ex E EENDI -00x1) Σ x 1B: [179]
k So²
+ + p,(B)) + (I2
(K + kppx + ind) pa IF \ Fol
- +D
n2
izck
PaSk + o² (kndd
1 (Kimid + Ind psk lndd )
where we use the condition on P>* to simplify the expression.
When data follows power law decay 22. we know 0((ns/Ii In2 d)'/a) from npp O(n2 d)).
Then from Claim that p>k S 8
ln2 d' ne
and klnd n + 6 Indd + Ind p>kk In2 d dS ad (In
Theorem 5 (OOD performance). Under same condition as Theorem then with probability least 0.99 over the data generation process, consider any feature set F C FF Fo contains any long tail features show up in data, we huve
h22 1n
I 113 x x) SP>k + o
+ +Ind),
where the first expectation is over data generating process of common part of training data X When data follows power law decay with 2 + Co with any constant Co. >
In d
E Ex
Exc1
EE x -B
+
7s
Proof. From Lemma B.2 we know
E. B.BanDy [(3 x - Brd xT) Σ
p. - -3)))
Σ
E
E(3 - 33)
i
ieF
S0²
k +
+ +
pr((B)) +E
(palE
0ه
2 In? d
kp>* + Ind
n2
n
i>k
2
In?
Spak + 2
+ Ind)
When data follows power law decay 2). we know = O((ns/ In? d)//a) from np, O(nn d)). Then from Claim T we get the result.
20

---

Published as a conference paper at ICLR 2026
B.3 DETAILED PROOFS
Here we present the detailed proofs in Appendix B.I
Lemma B.1. Under Lemma A.7 with additional requirement np>x c.r small enough constant then besides the conclusion of Lemma A.7 we additionally have there is no combination of long tail features:
S22l = { E [n]: 361 + Eg >> k such that It, It, + 0}1 =0
Proof. From the proof of Lemma A.I we know the probability of one data has at least long tail features is
IP (3 + l > k such that zez 2t2 +
=1 - Pz, 0, Vi k) - (3t > ko such that ze * 0 and 2, = 0, Vj > k.j#0
- - P>* - (> - }> = P5
Since each data is generated i.i.d. following probability least 0.999
2 by standard Chernoff's bound, we know with
|S = i E [n] 34 + Eg > ht such that Tg, 3ta # 00| mp + V <1,
which implies |S22| = 0.
Lemma B.2 (Recovery of 3*)) Under Lemma A.I and Lemma B.1 with probability 0.99 we have (in
below expectation is over data generating process of common part of training data X sk))
1. Common features (Top-k entries) are recovered:
||02*
S 0² ( +P>kk
Exge
Dek.
2. All long tail features shown up in data X X(last-d - entries) are recovered upto noise level:
1k2n2d d
Ex3 3/13 0²
kp>k In
3. 3, = for all i (FUUF).
Proof.
We prove one-by-one.
item
First note that since 3 is the minima of training loss, we know training loss is bounded
X
X3 y11 = ||
For common features (top-k entries). it suffices to only look at data in So, that is data only have non-zero entries in top-k entries. We know from above that
Xsso So. A.s.ShBBK
2 < |K
yso
Denote the normalized matrix X So.sk Ss. <h To simplify the notation within in the following equation, we omit the subscript So and I k. We have
1/2 u||² =(x 1/3
X
X 1/2 ( 3*) 2g 1/2
33)) +
||
2|Sol (1-
X - -166 1) ||3 3r || x
-2 X
B . Σ
+ +11E11
Sool
Rearranging the terms we have
|Sol
1
Sq. Sa
15612|
|18Ex - 3 -
- 2
53, -2
x s5 ||
3cx - B
SS
Egx
Ez
| 2
21

---

Published as a conference paper at ICLR 2026
which leads to
[1E112 -1650 112
[8cu - PSSk
1 Eigh
1612
SS. So.5k
|So
+
(1
1 |8a1
X So, X
So.5k - -1So|I
2
So
Su.
X SSo - -1 2
Denote the event A
{1 Sol
X Sb.
So.5h - 1166 2 {1)}. We know from Lemma C.2 Sk
X
2
that P(4) 2 1 1/poly(dd)
Taking expectation over X St.cc on both side conditional on A, using Lemma C.4 [St] S np>s from Lemma A.1 and standard Gaussian concentration on & have
0 0 n |So
Ex so
||ا= Bigk
2
A
So²
+P*k)
Eck
On the event that A does not happen, it is easy to see there is (very loose) bound on | sd since the total training loss is at most oên. Therefore.
| - Bzg -
Exsp.sh
EgN
||Asc - BIcK
2
[|022 - -3-x
2
(+. + +p2x
<Bxsp.sk
(PA) + Exso.ct
AA (1 (1-P(A))
$ 0²
$
Ecc
Esck
n2
This also implies Exge ||0ca
1
Bz
2 0 PPz)).
Ege
First from Lemma B.1 we know all data have either 0 or long tail feature [x] So U Sj. We can further decompose 51 into S₁ = Use V,, S1,1. where S1,5 represents the set of data that contains only common features and i-th long tail feature (that (æy)); # for j e S1,)).
item 2
For i-th long tail features, we only focus those show up in S₁ These data are the only data that depends on i-th feature. Thus, since B is the minimizer of training loss, we must choose 3 to minimize these data in S1 (assuming other 3, are fixed). Thus, choosing = 3 gives a simple training loss bound these data:
us.. 12, |
X (S...
B3xx) EST.
To simplify the notation, we will drop the subscript S1,; in the below 2 equations.
Note that
((SE.)) - y x x5*( - (%xe) + X1(3, (7) E $|12
2 x - -89111
X5r - BB&z)
||
-V V18 .11
Xx BBx))
-1E112
Thus, we have
V VIs - 3:1 321 52 X (Bea - -BEW +
1El12 52
x
1/2 54
-
+
+
Eg*
Rearranging terms and taking expectation over both side (over data generating process on common part Xxk) we have
Exc, 18:-8817 1/)]
<E
x
S
E
1/2 5k
Ex Ex
EgM.
+
|
1
Es 112
k 1nndd
Sko²
+ P>>
+ In
where we use E standard Gaussian concentration E.
Xx
1/2
S1.1
< E
X
-1/211
Σ 5/
S
= k, item and
S
Sk
2
22

---

Published as a conference paper at ICLR 2026
item 3
From the discussion at the beginning of the proof, know |Sاد| O, that is these feature does not show up in the data. Thus, we know the result is directly implied by the meaning of min-lz-norm norm solution.
C
TECHNICAL LEMMA
We collect few technical lemma that are used in the proof.
Lemma C.1. If ps S for > k, then
I ((1-p)) p.) 2 1 P>k-
1>
Proof. We have
II p:)
P>k +
Σ
Σ
(-19ps PPyyy
f>
j=2 keh <ha
R4
When j is even, first note that Rg > 0. Also.
R2 Rs+1
Σ E (-19 PPppp "Ppi
Σ
(-1)++) Pi ..
kein Cis
kch Schriisnsiisss
Σ (-19ph ".Pi(( Σ Pini)
k<nn cisd
fddtttidd
20,
as long as P> I 1. Therefore, we know ΣØ= R2 2 when p>k S 1. This implies
II p.) 2 P>k- 1>k
When P>k > since pj for > so
II i>
pd) 20 -
The lemma below shows the data matrix X X
X cb after normalization is close to identity.
Lemma C.2. Given X E Nxd following the data generating process satisfies kpk & 1, we have with probability at least 1/poly(d)
T with N data, for that
E
1/2
1/2 NZ se
(
Ind Nu
In2 In²d)
Npw
When Np Z In² d, we have X 2k X <k is rank k. Same bound also hold for expectation.
Proof. We are going to use matrix Bernstein inequality (Lemma C.5
Denote normalized matrix
X VPrX
For ck Xsk, to use matrix Bernstein inequality (Lemma C.5
note that
X
X
Pk
i=1
23

---

Published as a conference paper at ICLR 2026
where Eşh E gg as and for all i [M]
112
B c skl =1k =/k-
Ind Pk
c gi Sk
B[e s lll
| 1ol12 sk
= L.
where we use Lemma
We also have
Σ 1 Sk
El se (T -
=N Blllãg ll Tc Sh
(R Sk
=N diag(pi + .I....PP. + l|2
=N(pF + -
Thus, by matrix Bernstein inequality (Lemma have
122/2 Npx(1 + (k- 1)px) + tLpx/3)
P( X s4 E
t) exp
Taking = CoONNNp Ind
0 (1+ (k 1)pk) In + Lpk. Ind,, we get
PP
X
X
snl 11, 2 (VNps 2 Ind + In? d)) s 1/poly(d).
Since B ch X <kl npp I and
ck = Vp X <k
1-2 we know with probability - poly(dl (d)
(V
N Ind
In d
k
E
zk
- 1/2
NI
50
2
Pk
Pk
and X Sx Xs is rank when Nps 2 ln² d.
Similar bounds can also be shown for normalized Egk and Øzk- Lemma C.3. There exists an universal large enough constant such that with probability at least 1 L/poly(d), we have
Teall kk
Σ pj (1 pi) Ind Pk Ind
As a corollary, with probability least 1 1/poly(d) we have for all i [n]
E < ls +
ΣeT
pT (1 p:) In + Pk Ind
kpk. S the above bound can be simplify k + 2elnd
pe
Proof. According to our data generation process we know for data æ each coordinate 2 follows
Bernuuli with Thus, each coordinate . Pe Bern(p:) for i < k.
Therefore, by Bernstein's inequality (Lemma
know
f2/2
P( P( B + t) S exp
Eisr Pj (1 (1 p:) + tpp //6
Taking t - 0 (v Essrp, (1 pe) Ind + px Ind)
with large enough hidden constant c, we have
(V
- p.) pt In ind) ) < 1/poly(d)
P |اموا > k
isk
By union bound, know for all E [n]) the same bound hold for all |
24

---

Published as a conference paper at ICLR 2026
Lemma C.4. We have
E xx
> X ck
vk 1|ll2
2
Proof. We have
Exxc
Σ E
1/2
X
x 12))
Exc:
|
1/2 x Su [ = k 111112
C.I MATRIX CONCENTRATION INEQUALITY
We collect few standard Matrix concentration inequalities here. The first one the standard matrix Bernstein inequality.
Lemma C.5 (Matrix Bernstein Inequality (Corollary 6.1.2 in Tropp et al. 2015 Consider a finite
sequence {Sk} of independent random matrices with common dimension dp d2. Assume that each matrix has uniformly bounded deviation from its mean:
| E[Sx]ll2 S L for each index k.
Introduce the sum
z=
5=Esp Sk
and let v denote the matrix variance statistic for Z:
u(Z) = max EE [ -
[ -E T(z (Z- -[Z))]]2
Σ B[( E[S -E((
Σ E [( -E(S)) (S. - E[S+)]
max
Then
E Z - - I (nd(Z)nnd, d2) + I + d2).
In particular, for all 2 0.
-t2/2
P Z | 2 2 21 S (di d2) exp u(Z) + Tt/33
Below the standard Chermoff's s bound for Bernoulli random variables.
Lemma C.6 (Chernoff Bounds). Let X En= X,, where X; with probability ps. and X; with probability Pe, and all X; are independent. Let μ E(X) Eim Pi. Then
P([X- n| 2 5u) S -3 for all 0 < 8 < 1.
D EXPERIMENT DETAILS AND ADDITIONAL EXPERIMENTS
In this section, provide details of the experiments discussed in Section along with a few additional experiments.
In Appendix
D.I
describe experiments synthetic toy dataset.
In Appendix D.2 we present details for Section 5.2 which explores modified version
MNIST with structured label imbalance, along with new results using different target function.
In Appendix D.3
we provide details for Section 5.3 where we augment an MNIST-based dataset with rarer samples from Omniglot and include an additional experiment.
In Appendix D.4 report the compute for the experiments.
25

---

Published as a conference paper at ICLR 2026
In Appendix D.3 we show that long-tail data exhibit high memorization scores when measured by influence functions (Feldman & Zhang 2020).
For experiments in this section, all datasets contain original labels ranging from 0 to 9. We deliberately control the number of samples per label in the training set to induce a long-tail distribution. More precisely, the number of samples for labels i {0, 1, (0......,)) 9) follows Zipf"s s law with exponent 2.
The unnormalized weight assigned to rank is defined as wi = (i + 1) and the final sampling probability for label is p; = wi/ Σ3 Wj.
Without loss of generality, we primarily focus on the samples with label 9 as the representative long-tail feature in the following experiments except for the experiment described in Appendix [D.3] We further analyze the performance of models that successfully memorize all long-tail features, with a particular emphasis on their generalization behavior on the test dataset.
To analyze the compositional effect, we focus on a particular long-tail feature and vary its frequency of appearance in the training set across 10 levels, ranging from 100 to 550 with increments of 50. For each occurrence level, we train independently initialized models and evaluate their performance on the test set. Specifically, we report the average test loss Mosstloss and the variance of this average Var T = o² //n
D. ADDITIONAL SYNTHETICS EXPERIMENT: GAUSSIAN MIXTURES
Dataset Construction We generate synthetic data based on multivariate normal distributions. Specifically, we randomly initialize 10 mean vectors, each corresponding to a digit from 0 to 9, Each mean vector is of dimension 100 and is sampled from a multivariate normal distribution with a mean of zero vector and identity covariance matrix. For each class {0, 1, .... 9}. samples are drawn from a multivariate normal distribution with the corresponding mean vector and a covariance matrix of aI. The number of samples per class follows Zipf's 's law decay distribution.
To construct the final dataset, we randomly sample triplets from the generated data, where each triplet consists of three individual samples. The label of triplet is defined the sum of the labels of its constituent samples. This results a dataset of shape n x 300.
Model Architecture We employ a two-layer neural network with additive structure. During the forward pass, the model processes the input by dividing the 300-dimensional feature vector into three segments: dimensions 0- 100, 100-200 200, and 200-300. The network independently computes the outputs for each segment, and the final prediction is obtained by summing the three outputs.
Training Setup We train the model using Mean Squared Error (MSE) loss and optimize it using the Adam optimizer. We use a learning rate of 0.0001, train for 300 epochs, with a batch size of 256.
Evaluation Metric
To assess the compositional effect of memorizing long-tailed tailed features generalization, we visualize the results using a performance plot. The x-axis represents the total number of distinct '9's the model has encountered during training, while the y-axis shows the corresponding test loss. For each x-axis value (ranging from 100 to 550), we train 20 independent models. Each data point is accompanied by an error bar, indicating the variance of mean of loss across test smaller variance suggests higher confidence in the loss estimates.
Our test dataset is constructed follows: we first generate 600 vectors for each class (0 through 9) by sampling from the same class-wise mean vectors used in the training dataset. To evaluate out-of-distribution generalization on the long-tail feature, we focus on class 9. For each vector labeled as 9, we randomly pair it with vectors from all other classes to create 2700 test samples. This results in total of 600 2700 = 1,620,000 test examples. The goal of this setup to examine whether memorization of the long-tail feature (class 9) generalizes to unseen vectors with the same label. If the model exhibits improved performance on these test examples, suggests that long-tail memorization contributes positively to generalization.
As shown in Figure 3 the test loss on examples involving class 9 decreases as the number of class 9 samples in the training set increases. Notably, the class 9 vectors in the test set not present in the training set, indicating that the observed performance gain reflects genuine generalization rather than rote memorization.
26

---

Published as a conference paper at ICLR 2026
vs. Labe] Occurrences Synthetic Toy
+ Moan Std
Mean Value Test Loss
0.23
0.22
0.31
0.40
0.39
Number
in Training
Figure 3: Test loss as function of the number of training occurrences of class 9,
D.2 EXPERIMENT DETAILS IN SECTION 5.2; LONG-TAIL MNIST DATA
We give more details the experiments in Section 5.2
Dataset Construction In the training set, the number of samples per label is as follows: [0: 77,435; 19,358; 8,603; 3: 4,839; 3,097; 5: 2,150; 6: 1,580; 1,209; 8: 955; 9: 774), resulting in total of 120,000 samples.
worth noting that the original MNIST training set contains roughly 5,000-6,000 samples per digit. Therefore, for labels 0-3, apply oversampling to increase their frequency. All samples then randomly shuffled and grouped into triplets, yielding a final training set of 40,000 triplets.
For the test we sample 200 unseen digit-9 images (i.c., samples not included in the training set). Similar to the digit-9 sample with each of
uniformly sample 200 samples for each class label from 0 4. Additionally,
construction in the toy setting, test samples generated by pairing the (200 x 5) combinations from labels 0-4. In total, this results in 200 x 200 x 5/2 100,000 test samples.
We clarify that all training samples are drawn exclusively from the MNIST training set, and all test samples drawn from the MNIST test
Training Setup We train the model using Mean Squared Error (MSE) loss and optimize it using the Adam optimizer. We use learning rate of 0.0001, train for 300 epochs, with batch size of 256, and no weight decay.
Evaluation Metric To evaluate how memorization of long-tailed features influences compositional generalization in a real-world setting, we adopt the same performance visualization approach as in our toy experiments.
For each x-axis value (ranging from 100 to 550), similarly, we train 100 independent models. Each model is trained on an 80% random subset the original dataset, ensuring that every subset contains the same number of *9's. The reported test loss is the average over these 100 models.
Notably, since we control the number of '9's in the training subsets, models trained with more '9's exposed to fewer instances of other digits. However, this does not significantly impact the observed downward trend in test loss. This further supports our hypothesis that memorizing long-tailed features substantially aids generalization.
D.2.1 ADDITIONAL EXPERIMENT: ROBUSTNESS ACROSS TARGET FUNCTIONS
We further examine the robustness of the observed trends by modifying the target function used during training. Specifically, instead of using simple sum of three labels as in Section 5.2 redefine the target as a weighted combination:
3
label =
Σ x label;
27

---

Published as a conference paper at ICLR 2026
This target is slightly more complex than the one in Section 5.2
In Figure 4 we observe that the loss curves continue to exhibit a similar downward trend as the number of training instances from class 9 increases. This indicates our results in Section 5.2 is robust to different target.
Notably, the dataset and training setup are exactly the same as in the previous experiments. The only difference lies in the way labels are computed in the dataset.
Test Loss vs. Label 9 Occurrecces on Modified MNIST Dataset
Test Loss vs. Label. Occurrences on Modified MNIST Detaset
ResNet + Linear Layer New Target Fucction
ResNet 2-Layer N Network New Target et Function
Mean value of Tost Loss
Meon Rd
Motn + Std
Moun Value of Text
7
7-
Number of Ocourrences Label Training Set
Number Occurrences of Training
Figure 4: (Left) ResNet+Linear layer with New Target Function: Test loss as a function of the number of training occurrences of class 9; (Right) ResNet+2-layer network with New Target Function: Test loss as a function of the number of training occurrences of class 9.
D.3 EXPERIMENT DETAILS IN SECTION 5.3 RARER SAMPLE CASE FROM OMNIGLOT DATASET
Firstly, we give more details of the experiments in Section 5.3
Dataset Construction The MNIST part of the mixed dataset is constructed in the same way as the training set described in Appendix D.2 The only difference is that we additionally include samples from the Omniglot dataset. Specifically, we randomly select one sample from each class labeled 0-9 in the Omniglot training set, resulting in 10 Omniglot samples. These samples are preprocessed to match the format and size of the MNIST data and then mixed into the MNIST training set. To ensure the total number of samples is divisible by 3 (since samples are grouped into triplets), randomly remove one MNIST sample after adding the Omniglot data. The final training set size is 40,003.
For the test set, uniformly sample 100 MNIST samples from each class label 0-4, resulting in 500 MNIST test samples. We then consider all possible pairwise combinations among the 10 Omniglot samples, generating 45 unique Omniglot pairs Each of these pairs is combined with the MNIST samples to form test triplets, resulting in a total of 45 x 500- = 22,500 test samples.
Training Setup We also train the model using Mean Squared Error (MSE) loss and optimize it using the Adam optimizer. We use a learning rate of 0.0001, train for 300 epochs, with a batch size of 256.
D.3.1 ADDITIONAL EXPERIMENT: MORE OMNIGLOT DATA PER CLASS
Similar as Section 5.3 we also design experiments where Omniglot samples appear more frequently, and the test sample contains only one instance from Omniglot. Specifically, we introduce a variant of the 3-digit synthetic dataset by injecting distractor samples from the Omniglot dataset. To construct the training set, randomly select 10 samples for each digit label (0-9) from Omniglot (totaling 100 samples) and mix them into the original training data. For the test set, we sample the same 10 Omniglot samples in training dataset per digit label (0-9). Additionally, we sample 200 test digits each from MNIST labels 0-4.
Each final test instance is formed by combining digit from Omniglot and two digits from MNIST, resulting in test samples that include both known and of (OOD) components. In total, this produces 100 x 5 100- 50, 000 test samples.
28

---

Published as a conference paper at ICLR 2026
Table 2 show that the model still performs well even test data that not limited to long-tail feature combinations.
Table Stronger Memorization Behavior ResNet Variants Under Different Weight Decay Settings
Model
Memorization (WD=1 =VD=0)
No Memorization (WD = 0.5)
Test: 0.0697
Test: 0.8266 Train: 0.0538
Sum
Train: 0.0002
Test: 0.1171
Test: 0.9571 Train: 0.0715
Linear
Train: 0.0006
Test: 0.0650 Train: 0.0013
Test: 0.6579
2-L.ayer
Train: 0.0196
D.4 COMPUTE REQUIREMENTS
The computational resources used for all our experiments are follows: 10 GTX 2080 Ti GPUs with GB of RAM. For the Experiments on Linear Model, completing all runs takes approximately 3 hours. For the Simple Task with Composition experiment, training single model takes about hour. For the Effect of Memorization experiment, training a single model also takes around hour.
D.5 MEMORIZATION SCORE VIA INFLUENCE FUNCTION
Although throughout this paper we directly use the training loss to measure memorization, an alternative approach is estimate memorization using influence functions, as proposed in |eldman & Zhang 2020). In this section, we show that long-tail data indeed exhibit high memorization scores when measured by influence functions.
We implemented the influence estimation method (Feldman & Zhang 2020) to quantify how training examples affect model performance. Since our task a regression problem that predicts digit sums (rather than classification task), adapted their influence score by replacing the accuracy difference with a loss difference. Specifically, the memorization score is computed as:
mem(i) [[(oss((z;) data é training set] (E(oss((::)) data i training set).
A positive memorization indicates that including the sample in training reduces its loss, suggesting a stronger memorization of the sample.
Experimental Setup: We trained 100 models randomly sampled subsets (80% of the full training set, i.e., 32,000 out of 40,000 samples) and evaluated the memorization scores for all instances the long-tail digit 9, The setup is the same as Section 5.2
Table 3: Top-10 10 most memorized digit-9 examples. All highly memorized examples appear exactly in the full training set.
Original Index Containing '9'
Memorization Score
4362
80.38
21445
80.28
9390
61.33
21302
55,62
19494
55,50
29286
49.01
31456
38.85
7620
35.90
19412
33.68
8847
32.67
29

---

Published as a conference paper at ICLR 2026
The result is shown in Table 3 Our analysis shows substantial memorization of long-tail examples, with an overall mean memorization score of 2.41 (std 7.54) and a maximum 80.38. These values much larger than typical training loss, indicating that whether a specific long-tail example appears in the training set has a strong effect on OOD generalization.
30


Reviews:
[{"review_id": "fODUe1Xvq4", "reviewer": "Reviewer_HA3C", "summary": "This work builds on to the line of work by Feldman and Zhang that has studied how long tail memorization can help with generalization in deep learning.\n\nThere is a key conceptual shift that this paper makes on top of Feldman. Feldman argued that memorization helps because test examples are similar to memorized training examples, which allows the model to recall them directly. This paper adds a new dimension to this discourse: Memorization helps not only because it reproduces similar examples, but also because it enables composition. This means that combining multiple memorized rare examples can lead to generalization into new configurations.\n\nTo demonstrate this idea of compositionality, the authors move away from the singleton tasks in past work to new tasks such as (i) a “sum of three MNIST digits” setup and (ii) an MNIST–Omniglot mixture testing one-shot memorization. \n\nThe authors develop a theoretical model in which different data features follow a power-law frequency distribution.\nThey prove that the min norm solution which memorizes training data can correctly predict on test examples composed of multiple long-tail features that never co-occurred during training. The theoretical argument is supported via the experimental results on the newly created synthetic datasets. \n\nResults show that networks capable of processing input components modularly (e.g., per-digit ResNets with additive aggregation) generalize compositionally, whereas architectures that entangle inputs early (“cross-channel” ResNets) fail.\n\nThe paper also shows that an attempt to mitigate memorization (such as weight decay penalty) leads to a loss in model generalizartion on such compositional tasks.\n\nDisclosure: I have not reviewed the theory carefully.", "questions": "1. The task of single example memorization in big models is hard. I wonder if some efforts around experimentation with PEFT, or in context examples can somehow connect here. In context learning is an example of single example generalization with high information recall (which is what you intend to use the word memorization for, anyways). This is just one thought to aid experimentation.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. Conceptual Extension: I quite like the extension this paper attempts to make over the singleton memorization argument made in Feldman et. al. The bridge is quite intellectually appealing and can connect various ideas like one-shot generalization and memorization in overparametrized models.\n2. The power law based feature setup seems quite simple yet expressive. I believe this is sufficient to motivate the emprical underpinnings of the work\n3. The paper has a good mix of toy tasks: from linear regression to a controlled mnist and omniglot task. I like how they are able to connect the architectural dependence here as we visualize the transition from memorizatioon to composition.", "weaknesses": "1. The main weakness of the work is in its experimental scope. I admit that this in general will stay a hard task but I would like to challenge the authors to find meaningful ways to extend these setups to those of more practical relevance. \n     i. this requires identifying where in the real world do one-shot composition of memorized instances naturally happens\n     ii. run controlled experiments to actually experiment by ablating away that capability\n     iii. if the memorized composition was indeed a mechanism by which models generalize, i actually thing it is quite a useful exercise to show that this happens in real tasks. if not, why is this phenomenon of interest? i am writing this as motivation rather than actually questioning the value of this line of work, which i quite like.\n2. I believe this paper also needs a discussion on when memorization hurts composition. This is especially true for scenarios such as spurious correlations. How would the theory and/or experiments inetrsect with this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gDSsohlqr6", "reviewer": "Reviewer_iwWd", "summary": "This paper explores how memorization of rare, long-tail examples can improve generalization when combined with a model’s ability to compose known features in new ways. Through theoretical analysis in linear settings and small-scale experiments on compositional MNIST tasks, the authors show that memorization enables correct predictions on unseen combinations of rare features.", "questions": "See above", "limitations": "", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper provides a clear theoretical formulation connecting memorization and compositional generalization, an underexplored relationship in deep learning theory. Its synthetic and modified MNIST experiments effectively illustrate how architectural structure influences compositional ability. Finally, it contributes a valuable conceptual shift, framing memorization not purely as overfitting, but as a potentially beneficial mechanism for learning from long-tail data.", "weaknesses": "**Oversimplified Definition of Memorization**\n\nThe paper treats memorization as a binary property i.e., models either memorize or do not memorize. This definition ignores the nuanced ways sample level memorization actually behaves. For example, memorization scores can vary from 0 (i.e., perfect generalization) to 1 (perfect memorization). By treating the property as binary, the authors are ignoring the entire range of values between 0 and 1.\n\n\n**No Empirical Verification of Memorization**\n\nDespite repeatedly claiming that rare examples (like the digit “9”) were memorized, the authors never tested this directly. They inferred memorization from improved performance on rare-digit test cases but did not apply any established measurement techniques (e.g., Feldman et al's self influence), to verify that the model had indeed memorized those samples. Without this validation, the central claim that memorization enables composition remains speculative.\n\n**Reliance on Indirect Behavioral Evidence**\n\nThe experimental support for memorization is limited to behavioral trends: test loss decreases as the frequency of the rare digit increases and increases when weight decay is applied. While suggestive, these results can also be explained by better statistical coverage or regularization effects rather than genuine memorization. The lack of causal evidence weakens the argument of this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Gfbvnr7Pcb", "reviewer": "Reviewer_mMst", "summary": "This work considers an interesting an interesting angle of how memorizing long-tail samples can be helpful for generalization. Theoretically, it proves that for linear classifier---whether the underlying distribution is noiseless or noisy---memorization can help generalization both in and out of distribution under some assumptions on the distributions. Empirically, it shows that memorization can help on an interesting construction of task: computing the sum of MNIST digits. With proper choice of model architecture, memorization can help improve the results when a certain digit is significantly under represented in the data set.", "questions": "My questions are mainly on the potential impact of the work.\n\n1) Could you provide some more real world examples of tasks where composition is natural?\n\n2) If time allows, could you quickly check the influence score a training example on itself or on the test samples? Either a simple leave-one-out test (retrain the model with a training set differing by one entry) or the estimation in Feldman,Vitaly and Zhang.\n\n3) What could be the future extension of the result in this work? \n\n\nFeldman, Vitaly, and Chiyuan Zhang. \"What neural networks memorize and why: Discovering the long tail via influence estimation.\" Advances in Neural Information Processing Systems 33 (2020): 2881-2891.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The presentation of this work is outstanding: theoretical claims are clearly defined and the underlying intuition of the proof well explained. I also appreciate the authors' effort of motivating the problem as well as presenting the related work with precise and succinct language. The theoretical claims are sound. I don't find any apparent problem in the proof, either. The design of the three-digit-sum problem is new to me. Despite some limitation of the design, which I will come to later, the idea is intriguing. Overall, this work is solid technically.", "weaknesses": "Compared to the outstanding presentation and rigorous theoretical formulation, this paper is slightly weaker on the potential impact. Specifically:\n\n1) The linear case is slightly simplistic as composition is natural. If two features both contributes positively to the prediction score, i.e., have positive corresponding field in $\\beta$, then observing one of them at a time in training example should suffice for good test results. In nonlinear case, e.g., an XOR, observing one feature at a time may not be sufficient for the telling the outcome when both features are present (nonzero). In fact, the sum-of-digit task is somewhat linear with respect to the digits. I wonder if the phenomenon of composition can be observed in more general tasks.\n\n2) The notion of memorization here is slightly different from the literature I'm familiar with. I'm more used to influence score based criteria for memorization, e.g., removing a training example will significantly impact the prediction of another example. I believe this work assumes that an overparametrized model with unregularized training will memorize. Is this assumption common in literature? \n\n3) Following 2), MNIST is a fairly 'simple' dataset for which a small size of sample can lead to good model already with or without memorization. For stronger impact, the authors may want to consider some more complex tasks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)