Learning curves theory for hierarchically compositional data with power-law distributed features
Authors: Francesco Cagnetta
Hyunmo Kang
Matthieu Wyart
Venue: ICML 2025 poster (2025)
Keywords: Science of Deep Learning
Scaling laws
hierarchical compositionality
probabilistic graphical models
Primary area: deep_learning->theory
TL;DR: How do hierarchical structure and Zipf-distributed features affect learning curves? In classification, scaling depends on feature frequency; in next-token prediction, it’s governed solely by the data’s hierarchical structure.

Abstract: Recent theories suggest that Neural Scaling Laws arise whenever the task is linearly decomposed into units that are power-law distributed. Alternatively, scaling laws also emerge when data exhibit a hierarchically compositional structure, as is thought to occur in language and images. To unify these views, we consider classification and next-token prediction tasks based on probabilistic context-free grammars—probabilistic models that generate data via a hierarchy of production rules. For classification, we show that having power-law distributed production rules results in a power-law learning curve with an exponent depending on the rules’ distribution and a large multiplicative constant that depends on the hierarchical structure. By contrast, for next-token prediction, the distribution of production rules controls the fine details of the learning curve, but not the exponent describing the large-scale behaviour.

Learning curves theory for hierarchically compositional data with power-law distributed features
Francesco Cagnetta
Hyunmo Kang² Matthieu Wyart
Abstract
provement of test performance in the data-limited regime, where model capacity and compute unlimited, and per- formance is constrained primarily by the number of training data. A simple approach, based on data memorisation, leads to power-law learning curves under a Zipf, ie. power-law, distribution of the input data (Hutter, 2021; Michaud et al., 2023). However, this view cannot explain how general- isation performance improves. Alternatively, power-law learning curves appear in kernel regression when the spec- trum of the target function in the kernel eigenbasis is itself a power law (Caponnetto & De Vito, 2007). Several the- oretical studies of neural scaling laws are indeed based on this result (Spigler et al., 2020; Bordelon et al., 2020; Bahri et al., 2021; Favero et al., 2021; Maloney et al., 2022: Cagnetta et al., 2023; Bordelon et al., 2024; Lin al., 2024). However, these approaches are restricted to kernel-based approximations of deep learning methods, whose limited power cannot explain the successes of modern language and vision models.
Recent theories suggest that Neural Scaling Laws arise whenever the task is linearly decomposed into power-law distributed units. Alternatively, scaling laws also emerge when data exhibit a hier- archically compositional structure, as is thought to occur language and images. To unify these views, we consider classification and next-token prediction tasks based probabilistic context- free grammars-probaheee ate data via hierarchy of production rules. For classification, we show that having power-law dis- tributed production rules results in a power-law learning curve with an exponent depending on the rules' distribution and large multiplicative constant that depends the hierarchical struc- ture. By contrast, for next-token prediction, the distribution of production rules controls the local details of the learning curve, but not the exponent describing the large-scale behaviour.
models that gener-
In this respect, recent studies have identified hierarchical generative models such Probabilistic Context-Free Gram- mars (PCFGs) as model datasets to explain the difference in performance between deep and kernels/shallow learning methods methods, while still allowing for some analyti- cal understanding (Malach & Shalev-Shwartz 2018; 2020; Cagnetta et al., 2024; Sclocchi et al., 2025; Mei, 2024; Tomasini Wyart, 2024; Cagnetta & Wyart, 2024; Garnier- Brun et al., 2024; Sclocchi al., 2024; Oko et al., 2025). In this work, combine one such data model-the Random Hierarchy Model (RHM) of (Cagnetta et al., 2024)-with the hypothesis that the features of real datasets (e.g. the words in text corpus) are Zipf distributed.
1. Introduction
The improvement in the performance of many machine- learning models with the amount of resources, including the number of model parameters and training examples, has been shown to follow a simple power-law behaviour across several orders of magnitude (Hestness et al., 2017; Kaplan et al., 2020). These power laws, known as neural scaling laws, are used in practice as a guideline for scaling up resources (Hoffmann et al., 2022; OpenAI, 2023).
Among scaling laws, the learning curve describes the im-
'Theoretical and Scientific Data Science, SISSA, Tri- este, Italy 'Departennt of Physics, Scoul National Univer- sity, Scoul, Republic Korea 'Department of Physics & Astronomy, Johns Hopkins University, Baltimore. United States. On leave from EPFL, Switzerland. Correspon- dence to: Francesco Cagnetta <francesco.cagee www.sooo..c.eetaaeeeee..e sissa.its> Hyunmo Kang <gusahl 104@ anr>,,, Matthieu Wyart <mw- yartl @jh.edu>.
1.1. Our contributions
We introduce (section 2) a family of synthetic datasets based on the RHM (Cagnetta et al., 2024), where data are generated from their class labels according to hier- archy of production rules, mapping high-level features tuples of lower-level features. While in (Cagnetta al., 2024) all production rules have the same prob- ability, we consider probabilities obeying Zipf's 's law, S' x k(1+a)) These datasets model both the hierar-
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Learning curves theory of hicrarchically compositional data with power-law distributed features
chical and compositional structure and the Zipfian dis- tribution of the low-level features of realistic datasets;
1982; Joshi, 1985), and have also been used model seman- tics (Knuth, 1968) and natural images (Zhu & Mumford, 2006). Here, for the sake of analytical tractability, we make the following simplifying assumptions:
We show (section 4) that the Zipf distribution of fea- tures changes the learning curve of classification tasks from a sigmoidal to a power-law shape. In particular, after a large pre-asymptotic phase of size controlled by the hierarchical structure, the classification error of network trained on P data decays asymptotically as p p-a/(1+a);
i) the nonterminal symbols are split into L finite vocabu- laries (Ve)r=1.....I of finite size v and V Vo denotes the vocabulary of terminal symbols, or tokens;
ii) All the production rules transform one level- (f++)
symbol into s level-& symbols,
For next-token prediction tasks (section 5), where the learning curves of the uniform RHM are already power laws (Cagnetta & Wyart, 2024), the distribution of the features does not change the asymptotic decay, while it controls the curves' local details. This result puts forward the hierarchical structure of language- not the Zipf distribution of features-as as prime candidate for explaining the scaling laws of Large Language Models.
p(et1) u1 10
(I)
ii There are m unambiguous production rules per non- terminal symbol, i.e. two distinct nonterminals cannot generate the same s-tuple. These rules are randomly chosen and frozen for a given instance of the RHM;
iv) Each rule can be picked with probability f6 with ,,.,,,, W. and Ee J = for all é
1.2. Additional related works
k= I,.,...,
There is a growing number of studies using generative mod- els from theoretical linguistics to understand the capabili- ties of large language models, including n-grams (Svete & Cotterell, 2024; Nguyen, 2024; Svete et al., 2024), and reg- ular (Borenstein et al., 2024; Shai et al., 2024) and context- free grammars (Allen-Zhh -he & Li, 2023: Zhao et al., 2023). All these works concern either expressivity or the inter- pretability of the representations of trained transformers. (Zhao et al., 2023), in particular, showed that the operations performed by BERT-like transformers resemble well-known algorithms for grammatical inference, and proved that, for PCFG data, these algorithms are optimal solutions of the masked language modelling objective. However, when the training data can be equally explained by PCFG or non- hierarchical generative model, neither recurrent language models (McCoy et al., 2020) nor transformer (Ahuja et al., 2024) consistently prefer the hicrarchical interpretation. In addition, none of these works study the learning process and the sample complexity.
The Random Hierarchy Model (RHM) of (Cagnetta et al., 2024) corresponds to setting 5k = 1/m for all k's and f's. Here, mimicking the power-law distribution of word frequencies (Corral et al., 2015), we set the production rule distribution to be uniform in all but one layer f, where it follows Zipf law (Hutter, 2021; Michaud et al., 2023), fi x k (1+a))"
Given an RHM instance, input data are generated by picking a class label y (or level-L symbol) uniformly at random, then picking a production rule emanating from that label and replacing the label with the right-hand side of the production rule. Repeatedly applying the production rules L times yields the input sequence
(211...,, Id), with d= st. The process can be represented graphically with tree, as illustrated in Fig. I, known as the derivation of the sequence æ. Each token 2, is represented as a o-dimensional one-hot vector
with Fi = =1 if x; encodes for the j-th element of the vocabulary and 0 otherwise.
2. Notation and setup
Learning Setup. We consider both classification and next-token prediction tasks. For classification, deep con- volutional networks (CNNs) are trained approximate the probability of the root (label) conditioned on the in- put, P (Y y X1 21. X.a = æa). For next-token prediction, we train deep transformers to approximate
Hierarchical generative model. We consider synthetic datasets generated via a probabilistic context-free grammar (PCFG) (Rozenberg & Salomaa, 1997): a collection of sym- bols and rules that prescribe how to generate input data starting from their label. PCFGs consist of a vocabulary of hidden (nonterminal) symbols, a vocabulary of observable (terminal) symbols and production rules that quantify the probability that one hidden symbol generates tuples of ei- ther hidden or observable symbols. Generic PCFGs provide a natural formalism for describing hierarchical structures found in the syntax of natural languages (Pullum Gazdar,
'Havnn Zipf production rules all levels would change the input features distribution, as their probability will be given by the product of several dipf-distributed numbers. Nevertheless, we believe that our theoretical framework and the main conclusion of our paper would still hold: the exponent of the scaling law is con- trolled by the Zipf distribution of production rules for classification and by the hicrarchical structure for next-token prediction.
2

---

Learning curves theory of hicrarchically compositional data with power-law distributed features
2021).
B
3.2. Learning the Random Hierarchy Model
(2)
(2)
Unlike Hutter's model, RHM data are characterised by the hidden hierarchical structure, i.e. the sequence of production rules used during generation. Multiplying the probabilities of all these production rules yields the conditional probability of the input sequence, given the root label, IP [Xi = ,i,...,,A.................. Xa = x.a Y = y)- As shown in (Cagnetta et al., 2024), production rules can be in- ferred from the correlations between the root label Y (blue box in Fig. 1) and s-tuples of contiguous input tokens X, = (X (1U-1))+11>-.. Xjs) (black box in Fig. 1),
(1)
22
x1
2=
2-4
&
Figure 1. Pictorial representation of derivation according to the RHM, with depth = and branching factor 8 = classifi- cation task requires predicting the root label (blue square) from the leaves. The correlations between the 2-tuples of leaves (e.g. (#a,as) and the label can be used to infer the hidden symbol above the 2-tuple (143) for ((ss.a)).. A next-token prediction task requires predicting the last observable symbol (red square) from the previous d - 1. In this case, hidden symbols can be deduced from the correlations of 2-tuples with the last token Td-
C) P (Y ys ( ,1,
Xjs 1s
- -P IP (Y = y) [X, = =
(3)
Indeed, due to the context-free structure of the generative model, the Cý μu) are identical for all the s-tuples ş gen- erated by the same level-1 nonterminal symbol μ(² With sufficient training data, empirical estimates of these corre- lations can be used to cluster s-tuples by their generating nonterminal, enabling a bottom-up reconstruction of the hidden hierarchical structure. This approach was further extended in (Cagnetta & Wyart, 2024) to next-token pre- diction, where the relevant correlations are those between 8- s-tuples of input tokens and the final token of the sequence (red box in Fig. 1), instead of the root label.
the conditional probability of the last token given the other d 1, (Xa= y|Xi .i,..., Xa-1 -d-1). 1. In both cases, training proceeds by updating the model's parameters via gradient descent over the empirical cross-entropy loss. Numerical experiments are per- formed in PyTorch (Paszke et al., 2019), with the code available at https: /ttp:::/ggttttbb com/ fracagnetta/ random- www.-hhirrrrcmme..... The specifics of the ma- chine learning models, including training hyperparameters and computational resources, are designed to reflect the data-limited regime, as detailed in Appendix A.
The role of correlations in learning the RHM can be for- malised via the following
Assumption 3.1. Each production rule is learnt when its effect on correlations can be detected from the training data.
3. Theoretical background
Then, the learning curve is derived by linking the generali- sation performance model to the number of production rules that can be inferred from the training data. For in- stance, in classification task with uniform production rules, all the rules are learnt once the training set size exceeds p = um" 5 (Cagnetta et al., 2024). This sample complexity is derived by balancing two sources of variance: the vari- ance between correlations corresponding to different level-1 monterminals-scaline as (u3m++1)- ---f-t))--addd the sampling noise induced by finite data, scaling as (u²mP)-1 When P> Pa, the correlations become distinguishable, allowing the model to reliably infer level-1 rules. Since the data struc- ture is recursive, resolving the first hidden level of the tree simplifies the problem, allowing reconstruction of the full tree. Consequently, the learning curve exhibits a sigmoidal shape, with an inflection point that scales as P *==unp u'= as confirmed empirically in experiments with deep CNNs.
3.1. Hutter's theory of learning
In the scenario proposed in (Hutter, 2021), each datum consists of single discrete feature k I...., 00, which uniquely determines the label. Data drawn i.i.d. cording to some probability distribution Sú. and correct classification requires that the feature & has appeared at least once in the training set. The resulting test error is the (average) probability that the test feature has not been seen during training,
(P)
Σ fa(1 P 1m
(2)
where P denotes the number of training examples. Assum- ing a Zipf distribution of the features, fk xc k (1++a, leads to the asymptotic power-law e(P) p=a/(1+a) (Hutter,
3

---

Learning curves theory of hicrarchically compositional data with power-law distributed features
4. Root classification
probability higher than fe. In other words, the model clas- sifies the input correctly if and only if all the s input patches are resolvable. The resulting test error reads
4.1. Nonuniform production rules at the bottom layer
When only level-1 production rules have a nonuniform dis- tribution, it is convenient to factorise the contribution of these rules in the data probability:
=(P)=1- =1
Σ
fR
P P = Z...... =a= = =xllY= = y}
P 3x,=My10 m31x,h -x,x" = (10) x
When P
Pf ~ um--1, this expression implies, as shown in Appendix B,
P - - x
= x -1
(4)
P V-LL11
aa((+ta)
s(P) ~ L-1
(8)
The conditional probability of level-1 nonterminals given the root is equal to the probability of uniform RHM with I T- 1 layers. The factors inside the brackets, instead, are nothing but the probabilities of level-1 rules: given the rank k(py) of the tuple μj. i.e. the index E 1..... m of the unique production rule that generates μ,y, the corresponding probability equals fk(ug)- By summing over all the tuples but the j-th, we get
4.2. Nonuniform distribution of production rules at arbitrary layer
When the nonuniform distribution of production rules af- fects an arbitrary layer é f 1, the probabilities of low-level tuples can be decomposed as sums of conditional probabili- ties over specific choice of production rules. As result, the correlations of Eq. 3 can also be written as sum of con- tributions due to production rules of a given probability f In analogy with Eq. 6, these contributions can be split into a factor of p(( times a label-to-level-l correlation and level- (L - --to-nnppp correlation. These two correlations depend solely on uniformly distributed production rules, thus they can be computed again using the results of (Cagnetta et al., 2024), and the arguments of the previous paragraphs apply.
P x = u = y} = SkIm) pu (I())) = w}
(5) where μn (J) denotes the unique level-1 features that gen- erates μ. Summing over y yields a similar result for the probability of p.: F (X; = [1] Sk(U) {ug = (1))) Then, by Eq. 3.
(),)) Su(n) ( (pz ())
(6)
where the dependence on the number of layers has been made explicit.
4.3. Empirical scaling laws of deep CNNs
We confirm Eqs. (7) and (8) empirically by measuring the learning curves of deep CNNs trained root classification of the RHM for i) varying Zipf exponent and ii) vary- ing the number m of production rules per symbol. The results, shown in Fig. 2 and Fig. 3 left panels, respectively, display remarkable agreement with our predictions. Fur- thermore, the right panel of Fig. shows that having Zipf- distributed production rules in the first instead of the last RHM layer leads to similar learning curve. The right panel of Fig. 3, instead, highlights that the asymptotic scaling law p- p-1/(1+a) kicks in for P> --L tthe sample complex- ity of a uniform RHM with L - 1 layers. We conclude that, for classification, the hicrarchical structure controls the size of the preasymptotic phase, whereas the Zipf distribution determines the asymptotic decay. Further empirical tests are presented in Appendix C.
Since the layers above the first have uniform production rules, we can use the results of (Cagnetta et al., 2024) for the variance of c/ (1 (ML, y). i.e. (w9m--1)= yielding a variance of / (1=m-=1)))))-- for (l (ps, y). In contrast with the uniform case, the variance depends on the rank k(()) of the lewelevel tuple μ. However, it correctly reduces to the uniform case result when Sж(μ)) = 1/m. The sampling noise is also affected by the probability of the production rules, as the probability of data with X, f is proportional to fk())) and the variance due to sampling is proportional to the event's probability. This effect is equivalent to replacing P by P/ P)) so that the variance due to the sampling noise reads Sk(w)/ (ua//((pP) Consequently, the sample size necessary to resolve the correlations of the tuple μ with the label is P* P*) = vm --1 ( (f
Ranking all the low-level tuples by the probability of the cor- responding production rules yields a sequence of m sample complexities P = um L-1 um /(xx) To estimate the learning curve, we assume that, following 3.1, when P> P the model can correctly classify data consisting of tuples with
"We remark that, depending on the m//=~11 the root might still be inferred without resolving all the patches. The corresponding probability was derived in (Sclocchi et al., 2024) for an optimal decoder. However, if m z²= as in Fig. 2 and 3, changing one patch changes the root label with high probability, implying that all patches need to resolved.
4

---

Learning curves theory of hierarchically compositional data with power-law distributed features
109
10
17
test error e
test error
10-1
unil. (a
zipf, 0.5
zipf-law layer /
zipf; 1.0
10-1
zipf, 2.0
1=2
10-9
10s
10
10a
106
training set size
training set size
Figure Left: Learning curves 3-layers CNNs trained on RHM with = --
25 and Zipf exponent a indicated
in caption. Solid lines are the empirical learning curves whereas dotted lines are predictions from Eq. (7). The dashed line represents scaling law ~ p-a/(1+m), Right: As the panel, but = m 100. Here is fixed the layer where production rules are Zipf-distrin diff-iistibuted changes. The black dotted line represents the scaling law p=a/(1+a)
109
10
P-ria
test error
test error
10-1
10-1
m 31
m= 31
m== 42
m
m=56
56
m
I 74
m=74
10-2
10a
10a
10P
10
102
training set size P
scaled training set size P/em 4-1
Figure 3. Left: Learning curves in the same setting Fig. 2. with Zipf exponent a= 11 and m = indicated in caption. Solid lines are the empirical learning curves whereas dotted lines are predictions from Eq. (7). Right: all the curves collapse when rescaling the x-axis by vrn--1 the sample complexity of an RHM with uniform production rules and L layers. The black dotted line represents the scaling e p=a/(1+aa)
5. Next-token prediction
input tokens,
In this section, we use Assumption Theorem 3.1 to derive the learning curves of next-token prediction tasks. Remark- ably, the effect on the production rules distribution differs from the classification case, as the exponent governing the lcrge-scale behaviour of the curves depends entirely on the hierarchical structure and not Zipf's law exponent a.
((u,))==(P M, = m} - -x(
(9)
In the uniform RHM, these correlations are random vari- ables over different dataset realisations, having mean and variance (Cagnetta & Wyart, 2024),
In contrast with classification, next-token prediction tasks are learnt a stepwise fashion (Cagnetta Wyart, 2024). Each step corresponds learning all the rules associated with the tree up one the ancestors of the last token Xa (e.g. 14" ju," and y for the tree in Fig. 1). At the f-th step, the model learns the depth-& tree generated by the level-f ancestor of Xa. As in classification, the hidden variables forming these subtrees can be deduced from correlations. As the root label is not provided, we consider correlations between Xa and the j-th s-tuple of
Uniform RHM.
1 (1 (1- 1-mmv"" m//²=1)
((C,(H,))))
(10)
2 2m2
where l is the level of the lowest common ancestor of X, and X,. Comparing this variance with that due to sampling- given by (v²mP) 11/2__eldd a sequence of sample complexities P; to learn the production rules within the subtree descending from the level-E ancestor Xa- When > Pt, the model outputs the -rram approxima-
5

---

Learning curves theory of hicrarchically compositional data with power-law distributed features
tion of the last-token probability,
could reach the 3--gram approximation with fewer training examples. To derive the sample complexity we resort again to Assumption 3.1. As we found in section 4, due to the dif- ference in production rule probabilities, the statistics of the tuple-token correlations (j,,, v) depend not only on the level of the lowest common ancestor l, but also on the rank ks ((()) of the tuple p. In partieular, the variance of Cj (1, v) over RHM realisations reads,
P [Xa = x. (2-(--1) = Fd -1- Xa-1 = Td-13
(11)
Combining the scaling of Pe with l with that of the average cross-entropy losses of the s -grams, Le, yields the scaling law (Cagnetta & Wyart, 2024)
((P) ~ P- log (m/mmmm///////// 11/20=""1////0/g log
(12)
(1 1
(1C)())))))) - =frcm))
fk.
m
where implies that Piindependent factors are neglected.
(13)
5.1. Nonuniform production rules at the bottom layer
where f22. 2. The detailed derivation of Eq. 13 is provided in Appendix D. The term Σx fh is the inverse participa- tion ratio of the production rules distribution: it ranges from /m to I. It measures the localisation of the distribution fx. with 1 1/m corresponding to uniform distribution and to the case where all the probability is concentrated on 1 pro- duction rule. Therefore, Eq. 10 is recovered in the uniform case. For a general Zipf exponent a > 0, Ev f3. converges to some finite, a-dependent number. The variance due to sampling is also affected by the production rules distribution, going from 1/(me²P) of the uniform case to fv fx(p)/((² P). Equating the variance due to sampling to Eq. 13 gives the following sample complexities, for reconstructing the k-th rule of the f-th level with 222: 2:
First step via memorisation. In the first step the model learns that the value of X, is affected by all the other tokens in the last s-tuple, (Xa-(s-1)= I):-.... Xa-1), and outputs the 8-gram next-token probability ((==)==a-(--1)- ................................ Td-1)). As there are no hidden variables that summarise the effect of the context (Xd-(s-1)).... I on Xa. the simplest strategy is to memorise all the possible s-tuples. Hence, the first step can be described within the framework of (Hutter, 2021). There are me s-tuples, split into m groups accord- ing to the probability f& of the corresponding production rule. Assuming that the level-1 nonterminal is uniformly distributed over the v vocabulary entries, which is true in the limit of large m (Cagnetta et al., 2024), then each s-tuple occurs with probability fe/V in the data. Therefore, the model learns the v most frequent rules with e/fi fi data, then the second most frequent with u/ f2 data, until converging to the s-gram probability with v/Im vm-+a data. This sce- nario is confirmed in Fig. 4, showing the empirical learning curves of a one-layer transformer trained to predict the last token of a depth-1 1 RHM. In the left panel, a green vertical dashed line marks the sample complexity e required to learn the most frequent rules. Notice that, when a 2 1, v/fi ~ v, indeed at u, the test loss departs from the initial value log v, corresponding to a random guess of the last token, and slowly converges towards the average entropy of the Li (a), which can be computed exactly knowing the rules of the RHM. As in (Hutter, 2021), the con- vergence to the average s-gram entropy follows the power law ~ p p1++( (right panel).
um 2 3
Pr. = (1 m/ fr fE)
(14)
Notice that, despite the acquired dependence on the rule rank k. the dependence on the level é is the same as in the uniform case, Ps ~m2
Average cross-entropy of the s-ramms. According to Assumption 3.1, we expect that, when P> Pt.m deep machine-learning model trained on P performs at least as well as the sf ---gram from Eq. 11. Conversely, if P << Pt.1. the model can at most match the performance of the sf-1. gram. Therefore, we can combine the average s -grams cross- crtss-cntropies with the Pt. 's to determine the scaling law of next-token prediction. These cross-entropies are given by
s-gram probability
C = (EE. [- log p(zal=a- (=-- 1):..........................1 .....))) (15)
Further steps via reconstruction of the tree. Starting from the second step, the simple memorisation strategy can be improved by replacing all the s-tuples of visible tokens with the corresponding hidden variables. Let us consider, for instance, the data structure depicted in Fig. 1. The pair (at,, wa) appears in the s--gram p(ara ( Ve, .77). Since there is only one level-1 nonterminal (1) generating (og, Ta), p(zg/zz Te. 277= = =p(xs) (ا(ا)) (25, 2o), 27). There- fore, a model having access to the level-1 nonterminals does not need to memorise all combinations of (ars, 26) and
Let us start by rewriting Eq. 15 using the tree struc- ture of the generative model. The resolved context win- dow (ra-
consist of s complete s- s-tuples and one incomplete tuple For instance, in Fig. 1 with f= 2, the context window (æ5, xe, (6, 47) contains the 2- tuple (I5, v2) and I7. Due to the unambiguity of the rules, each complete s-tuple corresponds to a unique level-1 non- terminal (nL) in the example of the figure). Since m < =-11 the generative process can only generate a fraction of the
6

---

Learning curves theory of hierarchically compositional data with power-law distributed features
10'
test cross-cntrope entroyy
(a)
109
unif. (a =a= -1)
10
10
zipl, 1.0
zipf,
10 10-2
10a
10
10
10
10a
10
10
10
training set size P
training set size P
Figure Left: Empirical learning curve of one-layer transformers trained for next-token prediction on RHM data with I. 1, 128, 32 and Zipf exponent as in the key. Vertical dashed lines mark the sample sizes required learn the most frequent rules: em the uniform case (equivalent setting dashed lines denote the test loss of the trivial prediction where the next-token probability is uniform over the vocabulary, Lo log The rightmost horizontal dashed lines denote average cross-entropy the s-gram approximation, (a). Right: subtracting L (a) reveals the power-law decay p p-a/(I+a), highlighted by coloured dashed lines.
in Zipf's law) and v with Zipf- dipf-distributed production rules. The leftmost horizontal
possible sequences of sf-1 level-1 nonterminal symbols. As result, knowledge of the s nonterminals above the complete s-tuples of the context window constrains the parent node of the last token (n4 in the figure). Denoting with Va(ara-co'-- -1)):----- Td-s) ) the set of the level-1 symbols compatible with such constraint,
other vocabulary entry, ã of a.d compatible with the con- text. Hence, estimate Le the fraction of data with positive contribution to the entropy, times this contribu- tion. The fraction of data can be derived by examining the possible sources of ambiguity: either [V,e|= = and there are distinet production rules compatible with the context and the level-1 symbol, Ve,el and the extra production rule can also come from a different level-1 symbol. The entropic contribution per datum is the logarithmic sum of two probabilities taken from the set (f&) of production rules probabilities, thus it depends on the distribution of low-level production rules but not on the other levels of the hierarchy.
Li =
Ex
log
Z(x. (st 1): {d x
Σ
p( (s-1)) (s-1)) ... 10011 (d-1:2(0))
(16)
The derivation of Le following this argument is presented in Appendix and leads to
where 2(x (1 s)) denotes the normalisation Eno
Id-1: (1)). Notice that, as the s-1 tuples in (# ;3d--)) can be re- placed with the corresponding level-1 nonterminals, Va,e depends only on the highest L - levels of the tree. There- fore, it can be thought of the set of terminal tokens com- patible with the context of size - 1 in uniform RHM with - layers The average size of this set over RHM realisations is given by (Cagnetta et al., 2023)
m\/²-1
m
Le 16 H2.am
1- 11m-/u² mn/80//
+
we-i
(18)
where H2, denotes the average entropic contribution of data with 2 compatible entries of the last token. Notice that Eq. 18 displays the same dependence on as the uni- form production rules case (Cagnetta & Wyart, 2024).
m 8-1
(DVc.e) = 1- m/vo-1 +
(17)
p--1
We can confirm this argument by computing the values of the C3 's for given set of rules exactly via Eq. 16. The results of this calculation averaged over RHM realisations with fixed are shown in Fig. 5, and confirm that the approach of C₁ to the limiting, residual cross cross-entropy Coo (a) is independent of a and follows the same scaling as the uniform case, shown as a black dashed line.
In the limit where & < 0-11, l grows. In this limit, and for large f, we can neglect the cases where [V..l > 2. As result, most of the data will give a null contribution to Eq. 16, since the context uniquely determines the content of the last token as Eg. The only data yielding a positive term are those where there one
(DVeel) approaches 1 as
m and varying production nules distribution

---

Learning curves theory of hierarchically compositional data with power-law distributed features
loss Le
10a
10"
L L
10-1
+ unif.
10
+ unif.
+ a 0.0
zipf,
+ a = 1.0
zipf,
10
3.0
zipf,
10.0
10-2
0
2
10a training set size P
102
10"
layer index &
10a
Figure 6, Empirical scaling laws of depth-4 transformers trained RIIM next-token prediction with L= 4, s 2, 32, and varying a. The limit a - oc corresponds to having only one production rule per level-1 nonterminal symbol, The red dashed line is guide to the eye for the asymptotic decay of Eq. 12.
m
210
10
6. Conclusions
10
We studied how the scaling laws of deep networks trained in a feature-learning and data-limited regime are affected by two ubiquitous properties of natural data: hierarchical compositionality and Zipfian distribution features. Re- markably, the effects of these two structural properties on learning greatly differ between classification and next token prediction tasks.
2
6
layer index e
Figure 5. Average cross-entropies of the s'-grams versus for RHM datasets with = 2, == 32, m m= with the colour denoting the Zipf exponent. The points are obtained by averaging the cross- entropies over 32 independent rcalisations of the RHM. The cross- entropies of the uniform production rules case are shown in blue for comparison. For all a's, the cross-entropies Li decay with towards some a-dependent value Loe (a) (Top panel). However, the approach to foo (a) is independent of a (Bottom panel) and follows the behaviour of the test loss bound derived in (Cagnetta & Wyart, 2024) in the uniform case (black dashed linc).
For classification, we have shown that the learning curve of simple context-free grammars becomes power law due to the broad distribution of production rules. Specifically, if production rules are power-law distributed with some exponent a, then the learning curve decays as p-a/(a+1), The exponent a/(a 1) is also found in elementary toy models of memorisation of Zipf-distributed data (Hutter, 2021; Michaud et al., 2023). Yet, in our case, as in real data, this behaviour is not simply caused by memorisation, as the probability of each single datum decays exponentially with the dimension of the input. Interestingly, the pre-asymptotic phase of the learning curve can be very large and depends the hierarchical structure of the problem.
5.2. Empirical scaling laws of deep transformers
In next-token prediction, as in classification, our analysis predicts that production rules leading to rare features require more data to be learnt and cannot be deduced from more frequent rules. Nevertheless, this effect only changes the asymptotic test loss C.o and not the scaling exponent de- scribing how this limit is approached. The slow decay of the curve rather stems from this effect: as the training set grows, the model can resolve increasingly long-range correlations allowing it to reconstruct deeper levels of the data's 'ss latent hierarchical structure. This suggests that the origin of scal- ing laws in LLMs trained for next-token prediction lies not in superficial statistics, such as feature frequency, but the deeper hierarchical structure of the data.
Since both the sample complexities and the loss plateaus display the same behaviour with é as the uniform case, we predict that the power-law distribution of level-1 produc- tion rules does not change the scaling law of the problem in Eq. 12. We confirm this prediction empirically in Fig. 6, showing the learning curves of deep transformers trained on RHM data for several distributions of production rules, from the uniform case of (Cagnetta & Wyart, 2024) to the extreme case where all the probability mass of the fa 's is concentrated on one production rule. The asymptotic decay of the learning curves agrees with Eq. 12, highlighted in the figure by red dashed line.
8

---

Learning curves theory of hierarchically compositional data with power-law distributed features
Limitations
Cagnetta, F. and Wyart, M. Towards theory of how the
structure of language is acquired by deep neural net- works. In The Thirty-eighth Annual Conference Neu- ral Information Processing Systems, 2024. URL https: / / //oppreevieee net/ forum? d=Na CXcUK hHH
The model of data considered is simpler than natural data, for which the topology of the tree of latent variables could vary. Furthermore, context-dependent effects may occur that cannot be described with tree-like model. Including these properties is promising avenue for explaining the performance differences between transformer and convolu- tional architectures, as well as phenomena such as in-context learning.
Cagnetta, F., Favero, A., and Wyart, M. What can be learnt with wide convolutional neural networks? In Interna- tional Conference on Machine Learning, pp. 3347-3379. PMLR, 2023.
Acknowledgements
Cagnetta, F., Petrini, L.., Tomasini, U. M., Favero, A., and Wyart, M. How deep neural networks learn composi- tional data: The random hierarchy model. Phys. Rev. X. 14:031001, Jul 2024. doi: 10.1103/PhysRexXX 14. 031001. URL htattss://linnt aps org/doi/10. 1103 1103/PhysRevx. 14. 031001.
The work of FC supported by the European Union's Horizon Hurope program under the Marie Sklodowska- Curie grant agreement No. 101 154584. We thank Daniel,
Impact Statement
Caponnetto,, A. and De Vito, E. Optimal rates for the regu- larized least-squares algorithm. Foundations of Computa- tional Mathematics, 7:331-366 2007.
This paper presents work whose goal is advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here
Corral, A., Boleda, G., and Ferrer-i Cancho, R. Zipf's law for word frequencies: Word forms versus lem- mas in long texts. PLOS ONE, 10(7):6112031,, 2015. ISSN 1932-6203. doi: http:///ooraaa.poo.0.11111 URL http:// /ttt:://dx.. doi wtt.g//1.1111//.. pone 0129031.
References
Ahuja, K., Balachandran, V., Panwar, M., He, T., Smith, N. A., Goyal, N., and Tsvetkov, Learning syntax without planting trees: Understanding when and why transformers generalize hierarchically. arXiv preprint arXiv:2404.16367, 2024.
Favero, A., Cagnetta, F., and Wyart, M. Locality defeats the curse of dimensionality in convolutional teacher- student scenarios. In Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, 2021. URL https: / //oppreevil ew net/ forum? d= BBn FOFtPc.
Allen-Zhu, Z. and Li, Y. Physics of language models: Part 1, learning hierarchical language structures. arXiv preprints, Abs/2305./3675 May, 2023.
Garnier- Bruin, J., Mézard, M., Moscato, E., and Saglictti, L. How transformers learn structured data: insights from hierarchical filtering, arXiv preprint arXiv:2408. 15138, 2024.
Bahri, Y., Dyer, E., Kaplan, J., Lee, J., and Sharma, U. Explaining neural scaling laws. arXiv preprint arXiv:2102.06701, 2021.
Bordelon, B., Canatar, A., and Pehlevan, C. Spectrum dependent learning curves kernel regression and wide neural networks. In International Conference on Machine Learning, pp. 1024-1034. PMLR, 2020.
Hestness, J., Narang, S., Ardalani, N., Diamos, G., G., H., Kianinejad, H., Patwary, M. M. A., Yang, Y., and Zhou, Y. Deep learning scaling is predictable, empirically. arXiv preprint 17Xi:: 2017.
Bordelon, B., Atanasov, A., and Pehlevan, C. A dynamical model of neural scaling laws. In Forty-first International Conference on Machine Learning, 2024. URL https: //openreview, net. forum? 1d=nboY10mmtt
Hoffmann, J., Borgeaud, S., Mensch, A., Buchatskaya, E., Cai, T., Rutherford, E.,, de las Casas, D., Hendricks. L. A., Welbi, J., Clark, A., Hennigan, T., Noland, E., Millican, K., van den Driessche, G., Damoc, B., Guy, A., Osindero, S., Simonyan, K., Elsen, E., Vinyals, O., Rae, J. W., and Sifre, L. An empirical analysis of compute-optimal large language model training. In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K. (eds.), Advances in Neural Information Processing Systems, 2022. URL https: / //operrevl ew net/ forum? d= BBcRUl OAPR.
Borenstein, N., Svete, A., Chan, R., Valvoda, J., Nowak, F,, Augenstein, I., Chodroff, E., and Cotterell, R. What lan- guages are easy to language-modes a perspective from learning probabilistic regular languages. arXiv preprint arXiv:2406.04220 2024.
9

---

Learning curves theory of hierarchically compositional data with power-law distributed features
Hutter, M. Learning curve theory. arXiv preprini 1rXiv:2102.04410 102.04074, 2021.
Nguyen, T. Understanding transformers via n-gram statis- ties. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https:
Joshi, A. K. Tree adjoining grammars: How much context- sensitivity is required to provide reasonable structural descriptions? In Dowty, D. R., Karttunen, L., and Zwicky, A. M. (eds.), Natural Language Parsing: Psychological, Computational, and Theoretical Perspectives, pp. 206- 250. Cambridge Univ. Press, Cambridge, UK, 1985.
/ /oppereevew..ecccceeee wtt.:/ewwweeeeeeeeeeeeeeeeeeeeee wwt//eeeeourreee Co
Oko, K., Lin, L., Cai, Y., and Mei, S. A statistical theory of contrastive pre- wre-training and multimodal generative ai. arXiv preprint wrXiv:2501.046/ 2025.
OpenAL. Gpt-4 technical report. 2023.
Kaplan, J., McCandlish, S., Henighan, T., Brown, T. B., Chess, B., Child, R., Gray, S., Radford, A., Wu, J., and Amodei, D. Scaling laws for neural language models. arXiv preprint arXiv:2001.0836/ 2020.
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., Vito. Z., Rai- son, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S. PyTorch: An Imperative Style, High-Performance Deep Learning Library. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019, https: / //papers. wttp:ccccpppppe//111//////////// h0t9//hahh bdboa288 88 ftt. html.
Knuth, D. E. Semanties of context-free languages. Mathe- matical systems theory, 2(2):127-145, 1968.
Lin, L., Wu, J., Kakade, S. M., Bartlett, P., and Lee, J. D. Scaling laws in linear regression: Compute, parameters, and data. In The Thirty-eighth Annual Conference on Neu- ral Information Processing Systems, 2024. URL https: //openrevies net. forum? d=
Pullum, G. K. and Gazdar, G. Natural languages and context- free languages. Linguist, Philos., 4(4):471-504, 1982. doi: 10.1007/BF00360002
Malach, E. and Shalev-Shwartz, S. A provably correct algorithm for deep learning that actually works. Preprint at http://aaazii.oor////////1830090 //arxiv www.xiiv.org/bbbo. org/ abs /1033 09522.
2018. URL http:
Rozenberg, G. and Salomaa, A. Handbook of For- mal Languages. Springer, 1997. doi: 10.1007/
978-3-642-59122666
Malach, E. and Shalev-Shwartz, S. The implica- tions of local correlation on learning some deep functions. In Advances in Neural Information Processing Systems, volume 33, pp. 1322-1332, 2020. URL https://prooced.ngg.ee.mm oc htrpppper_lllleesspprr///////// BecoeeffSaacd0f22200554444333212 pdf.
Sclocchi, A., Favero, A., Levi, N. I,, and Wyart, M. Prob- ing the latent hierarchical structure of data via diffusion models. arXiv preprint arXiv:24100 13770, 2024.
Sclocchi, A., Favero, A., and Wyart, M. A phase transi- tion in diffusion models reveals the hierarchical nature of data. Proceedings of the National Academy of Sci- ences, :2407992248 2025. doi: 10. 10.7003/pnas. 2408799121. URL https: www.ppps.aao.....mmm.mm...m..... org/ /oii abs 10s/11..10 10031007//paaa 2408799121.
Maloney, A., Roberts, D. A., and Sully, J. A solvable model of neural scaling laws. arXiv:2210. 16859, 2022.
McCoy, R. T., Frank, R., and Linzen, T. Does syntax need to grow on trees? sources of hierarchical induc- tive bias in sequence-to-sequence networks. Transactions of the Association for Computational Linguistics, 8:125- 140, 2020. doi: 10.1162/tacl a 00304. URL https: a/aclanntae laclanthology org/2020 tacc-allla. 9.99.
Shai, A. S., Marzen, S. E.,, Teixeira, I.., Oldenziel, A. G., and Riechers, M. Transformers represent belief state geometry in their residual stream. arXiv preprint arXiv:2405.15944 2024.
Spigler, S., Geiger, M., and Wyart, M. Asymptotic learn ing curves of kernel methods: empirical data versus teacher-student paradigm. Journal of Statistical Mechan- ics: Theory and Experiment, 2020(12), 2020.
Mei, S. U-nets as belief propagation: Efficient classification, denoising, and diffusion in generative hierarchical models. arXiv preprint arXiv:2404. 18444, 2024.
Svete, A. and Cotterell, R. Transformers can represent n- gram language models. arXiv preprint arXiv:2404.1449 2024.
Michaud, F. J., Liu, Z.,, Girit, U., and Tegmark, M. The quantization model of neural scaling. In sevethh Conference on Neural Information Processing Systems, 2023. URL httpp::////peeevieerre forum? 1d=3tb7w2ga8K.
Svete, A., Borenstein, N., Zhou, M., Augenstein, I., and Cotterell, R. Can transformers learn n-gram language models? arXiv preprint orXiv:2410.03001, 2024.
10

---

Learning curves theory of hierarchically compositional data with power-law distributed features
Tomasini, U. M. and Wyart, M. How deep networks learn sparse and hierarchical data: the sparse random hierarchy model. In Forty-first International Conference Ma- chine Learning, 2024. URL https::////.... pwppp/epeereeeeeeeeeee/ee formm? i C jUd.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L.. Gomez, A. N., Kaiser, L., and Polosukhin, I. At- tention is all you need. Advances in neural information processing systems, 30, 2017.
Yang, G. and Hu, E. Feature learning in infinite-width neural networks. arXiv preprint 2rX1v:2011.14522, 2020.
Zhao, H., Panigrahi, A., Ge, R., and Arora, S. Do trans- formers parse while predicting the masked word? arXiv preprint arXiv:2303.085 08107, 2023.
Zhu, S.-C. and Mumford, D. stochastic grammar of images. Found. Trends Comput. Graph. Vis., 2(4):259- 362, 2006. doi: 10.1 10.1561/060 (0.1566/0000000011

---

Learning curves theory of hicrarchically compositional data with power-law distributed features
A. Methods
A.1. Deep CNNS
The deep CNNs we consider are made by stacking standard convolutional layers. To tailor the network to the structure of the data generative model, we fix both the stride and filter size of these layers to s. Since each layer reduces the spatial dimensionality by a factor s, the input size d must be an integer power of a and the CNNs depth equals log d/ log s.
We use the Rectified Linear Unit (ReLU) (xx) max (0, x) activation function, set the number of channels to H for each layer, and consider the maximal update parametrization (Yang & Hu, 2020), where the weights are initialised as random gaussian variables with zero mean and unit variance, all the hidden layers but the last are rescaled by factor H H-1/2, whereas the last is rescaled by H-1 This factor causes the output at initialisation to vanish as H grows, which induces representation learning even in the H/ + oo limit. In practice, H set to 512. Increasing the number of channels further does not affect any of the results presented in the paper.
Deep CNNs are trained with SGD, with the learning rate set to H to compensate for the factor of H A cosine annealing scheduler reduces the learning rate by 10 over 3 10 training epochs. The batch size is set to the minimal size allowing convergence, where we define convergence as the training cross-entropy loss reaching a threshold value of 10-2, We use a validation set of size 2 to select the model with the best validation loss over the training trajectory. Reported results for a given value of the RHM parameters are averaged over 10 jointly independent instances of the RHM and network initialisation for m 20, and instances for m >> 20.
A.2. Multi-layer self-attention (RHM)
The deep Transformers that we train on RHM data are made by stacking standard Multi-Head Attention layers (Vaswani et al., 2017), without any residuals, layer normalisation and multi-layer perceptron in between. We found that the removed components do not affect the model's performance on data generated from the RHM. Each layer has the same number of heads n, and embedding dimension demb nt, X v, with the vocabulary size. The input dimension is adapted the embedding dimension via learnable linear projection, which add learnable positional encodings. The choice of nu follows two principles: the model should be large enough for the training loss to reach threshold value of 10-3 and changing TA should not affect performance beyond the fluctuations due to the model initialisations. Specifically, we set n, = 16 and notice no significant change in performance up to n, = 64. Also scaling demb up to 4n x v does not impact performance.
Multi-layer self-attention networks are trained with the Adam optimizer, with a warmup scheduler bringing the learning rate to 10 within the first 16 training steps. As for CNNs, the batch size is the lowest value allowing for convergence. We use validation set of size 2 to select the model with the best validation loss over the training trajectory. Reported results for given value of the RHM parameters are averaged over 8 jointly independent instances of the RHM and network initialisation.
B. Asymptotics of the learning curve e(P)
This section contains a detailed derivation of the asymptotic learning curve for classification, Eq. 8.
Let us define k(P) the largest integer & such that fx > vmt corresponding to the rank of production rules that can be learnt given P data according to Assumption 3.1. Substituting Zipf's law for fx yields
um T--1
T
k(P)
~
(19)
Th レデー1J
P
U
Let us now define (P) as the total probability of all the production rules that are learnt with P data,
k(P)
Σ M(P)
k-l-a j-1-a
g(P)
Σ f
(20)
Σイ=
Notice that, from F..77 7,.(P))1 =1 1 -P To determine the asymptotic behaviour of (P), we use the Fuler-Maclaurin
12

---

Learning curves theory of hierarchically compositional data with power-law distributed features
formula, which relates to integrals:
Σ f(k) [[ f()) f(b) f(a)
B2j f(25 (x)) (2j)
kma
where B2y are the Bernoulli numbers. In particular.
P(P)
k Ai-o
k=)(P)+1
-(11+
1 -1- dx
1-a
+ ((P))(1+a)
Buj [(2j + a)
(k(P)) (((P))-(2++a) (2itt))
(21)
R(P)
(2j)! r(1+ + +a)
where ((s) is the Riemann zeta function and we used that (z)= (1-1)T(1+ a +) a)) x (1+a+5). Since k(P) increases with P, the asymptotics of the right-
f(x) = (1+a).
then
hand side of Eq. 22 are controlled by the integral term, equal to k(P)=a /a. Analogously,
k
1=1
1=1
k=
=((1 + a)
00
1-0
dx
+
m
(1+a)
B2j [(2j + a)
(m) (2j+a)
(m))(()ta)
2
(2j)! r(1 + a)
~ ((1 + a) - m mm"//a
(22)
hence
g(P) C(1 - k(P) /a
k(P)
(23)
<(1 + + a - m mm/a
aç(1
Notice how g(P) converges to 1 as k(P) approaches m, when all production rules are learnt. For k(P) < m, instead,
P
g(P) ~ -
(24)
vm--1
with c= c= (oC(1 -1. By plugging this back into the equation for s(P) we get
e(P) 1 g(P)st
P
ria
c
P
s
(25)
vm!.-1
which yields the desired asymptotic behaviour in P.
C. Empirical learning curves for classification with L 3
This section collects additional empirical tests of the predictions of section 4 for RHM data with L 3.
D. Token-token correlations with Zipf-distributed production rules
In this section, we derive Eq. 13 for the variance of tuple-token correlations with Zipf- production rules,
(1-m/v"1)
((C)(H))))) -(Jom)))
Σ L
(26)
23-3
13

---

Learning curves theory of hierarchically compositional data with power-law distributed features
109
test error e
test error
10
10
unif.
zipf layer
xipl, =0.5
1=1
xipf, =2.0
zipf, 4.0
10
10-2
10a
10
10
10¹
10a
10'
10"
10
training set size P
training set size P
Figure Learning Curves classification with L Left: Learning curves 4-layers CNNs trained on RHM data == 10 and Zipf exponent indicated in caption. Solid lines are the empirical learning curves whereas dotted lines are predictions from Eq. (7). Right: the panel, but is fixed layer where production rules are Zipf-distributed changes. The black dotted line represents the scaling law P pa)
3, s =.
100
10
test error
test error
m=
10-2
m=7 7
m= 12
m=
20
m=
10
10
10a
10a
10
10a
10P
10a
training set size P
sealed training set size P/um 4-1
Figure Learning curves with varying values. Left: Learning curves the same setting as above, with Zipf exponent a a= and m = v indicated in caption. Solid lines are the empirical learning curves whereas dotted lines are predictions from Eq. (7). Right: All curves collapse when rescaling the x-axis by L L- -heihhhheeee the sample complexity of an RIM with uniform production rules and L layers. The black dotted line represents the scaling law (1+a(
14

---

Learning curves theory of hierarchically compositional data with power-law distributed features
The starting point is the definition of the tuple-token correlation for level-& lowest common ancestor (compare with Eq. (124) of (Cagnetta & Wyart, 2024), Appendix F),
C (H,
Σ Pi ( (1n,
(27)
M1,20
Level-1 rules are power-law distributed. The corresponding probabilities can be written as sums over production rules,
m
p (ulu) = Σ (L8)r,,((1);,)),
(28)
where the function equals 1 if the i-th symbol the right-hand side of the k-th production rule coming from 1/1 equals and 0 otherwise. ((t, v1) only involves iifiommly-distributedd production rules and has O mean, thus the mean of c(0) (u, v) also vanishes. The variance reads, denoting with k(p) the rank of the unique production rule generating the tuple Ja, and omitting the position indices é and ji to ease the notation, (compare with Eq. (125) of (Cagnetta & Wyart, 2024), Appendix F)
((01)())))) (fa(m))) E
(p1))))))))))))))))) (ctt (vr)))
= ((h(a)))
Σ
+ +fA(H))) Σ
(p(()))))))(())))))
(29)
By Eq. 28,
(ulin = (6(rx,
bn
= Σ
JkiSka
(30)
As Koskte
and
(2 E
San (ō(rk) (1)
(31)
Using
(6(r)(11). =P ffMM i m) RHM
(32)
v²
where IP R denotes the probability over RHM realisations, and
(5(rk, (1)) w) = P { |n ki 1
TP for
K2, v MM
ky 11 num
(33)
NHM
where
112 = H1, = V,
P pf Vi Bis v /r k2z 1 RHM
11
(34)
if v1
# M1, V.
we get
1 1E
(11))))))))))))))))))))))
Σ3
1 1- - 12
(35)
1/
15

---

Learning curves theory of hicrarchically compositional data with power-law distributed features
and
(p
1 - -
(36)
0 v 1-
In addition, the covariance of the correlations satisfies (Eq. (74) of (Cagnetta & Wyart, 2024))
Σ
(C(U, = (C(H,
(37)
Therefore,
(((0)))))))) (Fx(He))& v
L0-
10-11 -1]
0-1 ((ot-)(),,))))
Σ f
1
Σ
10-1 00
k
&
(fr((e))
v
(H1)))
(38)
which, after substituting the correlations of the uniform case from (Cagnetta & Wyart, 2024), yields Eq. 13 in the limit of large v.
E. Cross-entropy estimate in the limit 1 < m < v--
Here we derive the approximation of of -gramm cross-entropies Eq. 18. Let us start from Eq. 17 of the main,
1
(eel) 1--m/---1- +
(39)
y--1
for the average size of the set of level-1 tokens compatible with the 5g-gram context. In the limit where <m < x (Da,el) approaches 1 as l grows. In this limit, we can neglect the probability that [Ve,el > 2, i.e.
Vedl
Σ nlP [Vee,l = n3 q1 + 292.
(40)
where
21 [VVcce 1] 2 -(VVee
(41)
22 = F (VVo1 2} = <(Vo,e)) 1.
Accordingly, we split the RHM data æ into those with [Ve.e] 1 (fraction qı) and those with [V,cl 2 (fraction 92).
If [Ve,el = 1, then (1) only attain the unique symbol (z that generates the s-tuple (I-- 1.. However, there could be other production rules generating (#d-(s-1)) -..-,, .) from (a0)) yielding positive contribution to the ,,
entropy. For each of the i E Vo. the probability that such production rule exists is (m 11/(0=* - 1). Since there are 1 elements of Vo other than Fa, the total probability is (u - 11(m 1)/(v" - 1) = m/v=-1. In the limit & m & u-- this probability is small, thus, as for the level-1 symbol ( we neglect the possibility that there is more than one T compatible
with (s .... Fd-1; (. To sum up, there is fraction qı (m/v² (m) of data having |e = but two distinct tokens i and za compatible with the context (I (., ()).
When [V.el = 2, (T) attains (1)) or ( One of the production rules emanating from ( could be compatible with (#a-(e-1))....- vd-1), yielding positive contribution to the cross-entropy. The probability that this production rule exists again m/v--1 and we neglect the possibility of two such rules & m < -- Moreover, even if such production rule does not exist, there could be, in the case VV,el 1, another ã compatible with (x (s- 1)....,......................... Zd-1; Zd-1;; ")). The resulting fraction of data with positive entropy is 242 (m/ -²11), yielding total fraction (g) 2qz (m2)mm//= (m)===))===-- (DVe.el> (m/u*-1) of contexts compatible with 2 entries of zz. The entropy contribution of each of these contexts is the logarithmic sum of two probabilities taken from the set (fk) of production rules probabilities. The average contribution over the possible choices of two fa's is independent of Denoting this average with H2 and using Eq. 17 for (DVe.el). we get Eq. 18 of the main paper,
m//5=1
m
Li
H2a.m
1 1-m/u-= m/mmu/ii +
(42)
-
y
16


Reviews:
[{"review_id": "06awPBsq5c", "reviewer": "Reviewer_GeDB", "summary": "This paper extends the findings in (Cagnetta et al., 2024) to a probabilistic context-free grammars (PCFGs) case. The authors investigate how the structure of data influences learning curves, focusing on datasets with hierarchical compositional structures and features distributed according to power laws (Zipf distributions). By using probabilistic context-free grammars (PCFGs) to generate synthetic data, the authors unify two theoretical perspectives explaining neural scaling laws. \n- For classification tasks, a Zipf distribution of features transforms learning curves from sigmoidal to power-law shapes.\n- For next-token prediction tasks, instead, the hierarchical structure primarily dictates the power-law scaling exponent, while the Zipf distribution.\n\n## update after rebuttal\nI stay with the original rating. \nThe merits of the theoretical contribution made me incline to weak acceptance.\nThe common concerns about its applicability to real-world data (also mentioned by Reviewer 1eLH) and applications stopped me from further increasing my rating.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**1st question:** For deep CNNs, $H=512$ (1M parameters in total, see last sentence of the second paragraph in appendix A), and we checked that our conclusions do not change up to $H=1024$ (~4M parameters). For transformers, $n_h=16$ (resulting in ~3M parameters), and we checked that our conclusions do not change up to $n_h=64$. In simple terms, we set the number of parameters to be large enough that it does not impact performance. As a result, we can focus our study on the dependency on the size of the training set (see also reply to Reviewer xKcS). We will clarify the text accordingly.\n\n**2nd question:** Our predictions in the synthetic data setting are valid for arbitrarily large datasets. Fixing the RHM parameters (in particular $v$, $m$ and $L$) to the values considered in the paper allows us to test the theory with $\\leq 10^7$ data, which is the range accessible to our experiments.\n\n**3rd question:** Concerning language, CFGs are believed to provide an accurate representation of syntax, except for only a few languages and constructions (see e.g. Gerhard Jäger and James Rogers, *Formal language theory: refining the Chomsky hierarchy*, Philosophical Transactions of the Royal Society B: Biological Sciences, 367(1598):1956–1970, 2012). Some aspects of semantics can also be modelled with trees via \"attribute grammars\" (Knuth, *Semantics of context-free languages*, Mathematical systems theory 2.2 (1968): 127-145), where hidden non-terminal symbols are complemented by attributes that influence the choice of production rule and are transmitted along the tree. Natural images can also be described with stochastic grammars, as done in pattern theory (Ulf Grenander, *Elements of pattern theory*, JHU Press, 1996). The RHM considered in this paper makes several simplifying assumptions to be tractable: uniform production rule probabilities,  frozen tree topology and random production rules. Despite the approximations, the RHM already captures non-trivial phenomena observed in real data, as shown in (Cagnetta et al. 2024) and (Sclocchi et al, 2025). Here we showed how including a broad distribution of production rules results in power-law learning curves for classification, as observed in real data, whereas, surprisingly, it doesn't affect the scaling law of next-token prediction. Extending these results to the case of non-random rules and varying tree topology is an important direction for future studies.", "claims_and_evidence": "Two major claims are supported by both theoretical analysis and experimental results on synthetic data.", "methods_and_evaluation_criteria": "The evaluation is based on the theoretical framework proposed in the paper. The experiments are mainly designed to verify this theoretical framework, which makes the data modeling depending on certain assumptions, e.g., the PCFGs assumption. But it makes sense as the observation of ''leaf-level nodes following Zipf's law'' has been observed in textual data.", "theoretical_claims": "I checked Eq. (7) and Eq. (12), corresponding to two major claims of this paper, their proofs in Appendix B and D are correct from my understanding.", "experimental_designs_or_analyses": "The experimental design is a natural extension of (Cagnetta et al., 2024), which looks sound and valid. one concern would be the model size and data size are too small in claiming ``scaling law``.", "relation_to_broader_scientific_literature": "The paper contains proper related literature, most prominently (Cagnetta et al., 2024).", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "One potential weakness would be the application power of the proposed scaling law. The results (both theoretical and experimental) rely on the assumptions of PCFGs, which is not necessarily true for the data we observed in today's applications. I further raise questions in the ``Question for Authors`` section.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "How far are the results proposed by the authors from guiding the applications like LLMs? This question can be further divided into the following parts:\n- What is the exact size of the model proposed in the paper? The description in Appendix A refers to the model size implicitly using $H$ for CNNs or $n_h$ for self-attentions, but the exact size of the model is not reported. \n- The proposed synthetic dataset is relatively small, at the scale of $\\sim 10^6$,  is this enough for claiming \"the scalling law\" as today's scaling law usually refers to much larger data sizes?\n- How different the synthetic data from the natural data? As mentioned in (Tomasini & Wyart, 2024), a context-free grammar modeled data is applicable for hierarchical data, but how about the case of natural data? References or comparisons with textual, vision, and audio would be appreciated.", "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": "PuF3fBGHXZ", "reviewer": "Reviewer_1eLH", "summary": "This paper presents a theoretical model to explain the emergence of power-law learning curves in deep neural networks trained on data with Zipfian feature distributions and hierarchical compositional structure. By parameterizing the Random Hierarchy Model (RHM) with a probabilistic context-free grammar (PCFG), the authors obtain asymptotic scaling laws for classification and next-token prediction tasks. For classification, they show that if the production rules satisfy a Zipf law with exponent a, then test error asymptotically decreases as ε(P) ∼ P^(–a⁄(1+a)) (to within a large multiplicative constant depending on the combinatorial structure). For next-token prediction, while the fine-grained shape of the representation learning curve depends on the production rule distribution, large-scale scaling is only dictated by the hierarchical form. These theoretical results are verified by large-scale numerical experiments on deep convolutional neural networks and transformers on artificial data from the RHM.\n\n## Update after rebuttal\nI stay with my original rating, as I agree with the comments of author's rebuttal.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for appreciating our study's strengths. Regarding the connection with real data, please see the reply to Reviewer GeDB.\n\nConcerning experiments on natural datasets, our work predicts that removing rare words from a data set should not affect the scaling law of the learning curve. It also predicts that grammatical structures that involve a large number of tokens require more data to be learned. Studying these questions systematically during training, beyond the existing analyses of how pre-trained LLMs represent grammar, will require a whole new project. We believe that presenting the theory clearly and convincingly warrants a dedicated paper, as we do here.", "claims_and_evidence": "Its main arguments are two-pronged. One, the paper states that in classification tasks the learning curve attains the Zipf exponent, giving a power-law decay with exponent a⁄(1+a) after a pre-asymptotic phase ruled by the hierarchy. Second, for next-token prediction tasks the asymptotic decay is independent of the Zipf exponent, with the hierarchical structure being the primary determinant of the scaling behavior. These claims are supported by asymptotic derivations (see Equations 6–7 and 11 in the paper) and are validated through systematic experiments (illustrated in Figures 2–7) that show agreement between theory and empirical learning curves. Overall, the evidence seems mathematically rigorous and empirically convincing, though the experiments are conducted solely on synthetic data.", "methods_and_evaluation_criteria": "They derive their scaling laws by considering the statistics of correlations in RHM-generated data. They assume that a production rule is \"learned\" when an effect of a production rule on correlations is seen (Assumption 3.1) and use it to infer sample complexities at different levels of the hierarchy. In experiments, the paper employs deep CNNs for classification and multi-layer transformers for next token prediction, and tracks test error and cross-entropy loss as functions of training set size. The test criteria—i.e., the asymptotic decay of loss and error, and the collapse of rescaled learning curves—are appropriate for demonstrating the predicted power-law behavior.", "theoretical_claims": "The paper presents several theoretical claims, including the derivation of the sample complexity P* that scales as vm^L, and the asymptotic decay ε(P) ∼ P^(–a⁄(1+a)) for classification. The derivations are detailed and build on top of previous work on neural scaling laws and learning curve theory. Although the derivations make strong assumptions (e.g., Assumption 3.1), the mathematical arguments appear sound and well-connected to prior results in the literature. The paper also formally derives the scaling law for next-token prediction (Equation 11) and describes how the hierarchical structure allows deep models to capture increasingly longer-range correlations.", "experimental_designs_or_analyses": "Experiments are performed to confirm the theoretical predictions in controlled settings. The authors generate synthetic data with the RHM for varying values of the Zipf exponent and the number of production rules. They then train deep CNNs and transformers, reporting both classification error and cross-entropy loss. The experimental design effectively isolates the role of the hierarchical structure and the nonuniform (Zipf) distribution. The empirical learning curves—especially their collapse after rescaling—strongly support the theoretical analysis. One potential concern perhaps is that the experiments are limited to synthetic data; additional validation on real-world datasets might further strengthen the findings.", "relation_to_broader_scientific_literature": "The paper situates its contribution in the broader framework of neural scaling laws and theoretical knowledge of deep learning. The paper offers a new perspective on why power law scaling is achieved in deep learning. The connection to both empirical and theoretical work is made explicit throughout the manuscript.", "essential_references_not_discussed": "All essential references seem to be discussed.", "other_strengths_and_weaknesses": "Strengths:\nThe paper provides a good theoretical framework that nicely bridges the hierarchical organization of data and power-law learning curves.\nDerivations are mathematically accurate and relatively comprehensive.\nExperimental evidence on synthetic data is in good agreement with theory predictions.\nThe paper provides useful insights which can potentially explain the behavior of large-scale deep learning models.\n\nWeaknesses:\nThe reliance on a model of synthetic data (RHM) prevents direct extension to real data.\nAssumption 3.1, while calculatively convenient, may be to idealized and its behavior under more realistic conditions may not be explored sufficiently.\nAdditional experiments with natural datasets would strengthen the contribution.", "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": "b49QzASLAn", "reviewer": "Reviewer_gXnS", "summary": "- Main algorithmic/conceptual ideas: \n  - Mostly based on the framework of Cagnetta et al., 2024.\n- Main results/findings: \n  - This paper shows that Zipf distribution of feature exists (which is common in real world scenario for long-tailed distributions) the learning curve of classification will show a power law shape instead of a sigmodal shape during uniform distribution. \n  - The curve of next-token prediction won't change due to Zipf assumption.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Theoretical claims\n\n1. **compatible**. In line 86, compatible means that the sentences in the training data can be generated both by a PCFG and by a non-hierarchical generative model. The next 4 occurrences of \"compatible\" in the main refer to compatibility of a single token ($x_d$) with the context ($x_1,\\dots,x_{d-1}$), where compatibility is defined by the full string ($x_1,\\dots,x_d$) belonging to the set of strings generated by the RHM. The next two occurrences refer to a different kind of compatibility, i.e. the one of an empirical curve that follows a theoretical prediction within the error bars. ***In the revised manuscript***, we will define the compatibility of a token with the context as above, and we will use \"agrees with the theory\" instead of \"is compatible with the theory\" when referring to empirical curves.\n\n2. **Zipf for each layer**. Having Zipf production rules at all levels would change the distribution of the input features, as their probability will be given by the product of several Zipf-distributed frequencies. Nevertheless, the learning curve can still be described via Assumption 3.1. In particular, we believe that the main conclusion of our paper would still hold: the exponent of the scaling law is controlled by the Zipf distribution of production rules for classification and by the hierarchical structure for next-token prediction.\n\n3. **Which $2$-tuples**. All the complete $2$-tuples are considered: $(x_5,x_6)$ for reconstructing $\\mu_3^{1}$, $(x_3,x_4)$ for $\\mu_2^{1}$ and $(x_1,x_2)$ for $\\mu_1^{1}$. However, unlike the classification case, the correlations are not equal for all tuples: $(x_5,x_6)$ is closer in tree distance to the missing token, so it has a higher correlation. As a result, the hidden variable $\\mu_3^{1}$ can be inferred with less samples than $\\mu_1^{1}$ and $\\mu_2^{1}$.\n\n4. **Dependency on the rank**. The rank $k$ referred to here was introduced in assumption *iv)* of Section 2, $k\\,{=}\\,1,\\dots,m$ from the most to the last likely production rule. Due to the non-ambiguity assumption, the rank determines uniquely the low-level tuple $\\mathbf{\\mu}$ produced, thus $k=k(\\mathbf{\\mu})$. This is indeed connected to the sentence \"Ranking all the low-level tuples by the probability of the corresponding production rules\". ***In the revised manuscript***, we will clarify this point while discussing the derivation of Eq. (4) (see relation to literature paragraph).\n\n## Experimental designs\n\nThe black dashed line in Figure 6 represents the prediction in the uniform case and should only describe the top coloured curve (solid blue line). However, as we claim in the paper, all curves display the same asymptotic decay with $P$, as highlighted by the red dashed curve. This curve is only supposed to represent the asymptotic power-law decay emerging from the sequence of steps. Its absolute position has been shifted by adding a $P$-independent constant for visualisation purposes.\n\n## Relation to broader literature\n\nAs the reviewer suggests, ***in the revised manuscript***, we will add a section before 3, including,\n\n1. Further background on Cagnetta et al., 2024, in particular concerning the calculation of correlations joint probabilities like Eq. (4) using the CFG structure, and the derivation of the sample complexities required for the accurate measurement of said correlations. In simple terms, the joint probability of the leaves conditioned on the class is given by the product of the probabilities of all the production rules used. Then, correlations involving a specific tuple of leaves or a specific production rule are obtained by marginalisation. The corresponding sample complexity is derived by studying how the empirical correlations measured with $P$ training data converge to the true correlations as $P$ increases. This addition would solve questions about Eq. (4), line 147, line 155, line 192 and Eq. (13).\n\n2. Further background on Hutter, 2021. Hutter ranks all the input data according to their probability, and assumes that a datum is correctly classified only if it appears in the training set (memorisation). We, instead, rank data according to the probability of the associated production rules, and assume that data can be correctly classified when all these production rules can be resolved.\n\n## Significance for practitioners\n\nDespite the simplicity of the data model, our results can be directly tested in real scenarios, for instance, by training LLMs on real data where the rarest tokens/words/grammatical constructions have been removed. Such empirical studies could suggest practical directions to explore, for example, curriculum learning approaches where the fraction of rare words or grammatical constructions would be varied during training. For RHM data, such a procedure will not alter the learning curve exponent but may change the prefactor.\n\n## Other comments\n\nWe will clarify line 125 and replace $\\mathcal{N}$ in line 339.", "claims_and_evidence": "Empirical results support all theoretical claims, which is good. For the discussion of theoretical claims, see relation to broader scientific literature section.", "methods_and_evaluation_criteria": "- Methods: N/A because this is a theory paper.\n- Evaluation Criteria: The scaling law is verified with synthetic dataset. Since it's designed for the purpose of verifying theoretical statements, this is acceptable.", "theoretical_claims": "Yes, for all claims made in the main text. The writing of the paper makes it a bit hard to judge theoretical claims made in the paper. Also see relation to broader scientific literature section.\n\nA couple of questions about the theory part:\n- What does \"compatible\" mean? Line 86 it says: \"training data is compatible with both a PCFG and a nonhierarchical generative model\", Line 343 it says \"the set of terminal tokens compatible with the context of size ...\" and there are 13 mentions of \"compatibility\" in this submission. They don't sound like sharing the same meaning. What is \"compatible\" with what?\n- Line 70: Even if power law exists everywhere in practice, what does it imply to model Zipf for each layer in your tree?\n- Line 130: \"In this case,... last token $x_d$\" which 2-tuples on the figure are considered in the next-token prediction task?\n- Line 132: Why does $f_{k(\\mu)}$ depend on the rank (in your subscript, also inferred from line 148 and no information is found before line 132)? Also, what are you ranking exactly? Is it related to line 161 when you wrote \"Ranking all the low-level tuples by the probability of the corresponding production rules\" later on?", "experimental_designs_or_analyses": "Experiments mostly look good to me. One question: for Figure 6, what is the black dashed line? Why is this black dashed line a better prediction for top three colored curves compared to the red dashed line representing Eq. 11?", "relation_to_broader_scientific_literature": "- Based on the whole paper, it seems that this paper is mainly built on two papers, Cagnetta et al., 2024 (learning curve theory based on RHM) and Hutter, 2021 (standard learning curve theory). \n- However, I feel the current description of these two papers are insufficient to let the reader understand the current submission without checking these two background papers carefully. \n- For example, more background for these papers can be very helpful to solve the following questions:\n  - How did you derive Eq. (4)?\n  - Line 147: where does the quadratic term of $f_{k(\\mu)}$ come from?\n  - Line 155: Why do you need to divide $P$ by $f_{k(\\mu)}m$?\n  - Line 192: Could you elaborate on how to compute two mentioned correlations with Cagnetta et al., 2024? What claims in Cagnetta et al., 2024 are used?\n  - Line 262: What's the framework in Hutter, 2021 specifically and the relationship to your paper? \n  - Equation 13: This seems to be from rearranging some terms in Eq.12, but how do you derive Eq.13 exactly and what's the meaning of $P_{l,k}$?", "essential_references_not_discussed": "No I'm not aware of any missing essential references.", "other_strengths_and_weaknesses": "- Originality: This paper extended Cagnetta et al., 2024 and I believe this is a novel contribution. The motivation is clear, although I'm not sure how is your specific choice to inject Zipf distribution related to the practical problem you want to solve. See the question for Line 70.\n\n- Significance: \n  - Given the limitation authors also realized that their HRM model might be still a simplification of the real-world data, I do want to ask how are your conclusions guide practitioners. \n  - We see all proved scaling laws are verified empirically so I don't have too much concerns about the correctness of the statements. And this is a big strength for this paper.\n\n- Clarity: have some space for improvement. See Relation To Broader Scientific Literature. Also, I noticed that you do have the space at the end of the 8th page so it's better to elaborate more on background papers. I would recommend the author to make sure all knowledge required to understand this paper is self-contained.", "other_comments_or_suggestions": "- Line 125: It's better to clarify $s$ represents a binary tree and $L$ is the height of the root node $-1$ if my understanding is correct.\n- Line 339: replace the notation of normalization as $\\mathcal{N}$ is often used to describe Gaussian distribution.\n- Comment on writing: It will be better to add one preliminary section before section 3 to incorporate all materials before nonuniform scenarios, because these are all background materials. The current sections are a bit confusing: when I read the paragraph starting from line 110, it's hard for me to tell if this is from your contribution or from Cagnetta et al., 2024 which you only cite in the early sentences of the paragraph. Or alternatively, use one sentence before section 3 to tell the readers what to expect in the following section.", "questions_for_authors": "See all comments above. The current score is mainly decided based on the writing issue, but this could be addressed in the rebuttal session if the authors can provide convincing explanations for questions about theoretical technical details.", "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": "8DVqJdWzsS", "reviewer": "Reviewer_xKcS", "summary": "This paper uses a theoretical framework to explain the emergence of neural scaling laws. It builds on the synthetic model and results derived in previous works on classification (Cagnetta et al., 2024) and next-token prediction (NTP) (Cagnetta & Wyart, 2024) that studied how hierarchical tasks are learned. The authors use the Random Hierarchy Model (RHM), a type of probabilistic context-free grammar, to generate synthetic data with a controllable hierarchical structure. This allows them to analyze how the loss changes as the training dataset grows in size.\n\nThe previous two works focused on the case where the hierarchical rules generating the data were uniformly distributed. This paper extends those analyses to the case where the rule probabilities follow a power-law distribution (at a single level of the hierarchy). In the case of classification tasks, the authors show that the scaling law exponent depends on the rule distribution. However, for next-token prediction, they argue that the exponent remains unchanged across different power-law distributions. While the decay rate of the loss remains the same regardless of the exponent, the rule distribution affects the final loss value, which corresponds to the entropy lower bound. They support their claims with both theoretical analysis and experiments on RHM models.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Weaknesses\n\n1. As the reviewer points out, we work in the data-limited regime, which is suitable for studying learning curves. In all our experiments, the models are large enough and trained for long enough for the training loss to reach its lower bound. In particular, for consistency, we increase the number of parameters (width for CNNs and number of heads for transformers) until the performance does not depend on this number anymore. Notice that, being overparametrized, the test loss of our models increases towards the end of training due to overfitting. To solve this problem, we employ early stopping, i.e. select the training step where the model gave the best performance over a validation set of size between ~32K and ~131K (depending on the Zipf exponent $a$). Studying how many parameters are needed is interesting, but we view it as less fundamental than the present work. The number of parameters will presumably depend on the detailed choice of architecture (transformers vs CNNs, depth vs width etc.). In contrast, we expect our present results to hold for deep enough architectures, including CNNs and transformers (as shown in the absence of Zipf distribution in Cagnetta et al, 2024). ***In the revised manuscript***, we will emphasize further that our results apply to the data-limited regime, and comment in the conclusions about the possibility of studying the dependence on FLOPs and model size.\n\n2. We think that the fact that the scaling law of NTP does not depend on the Zipf law is a surprising and interesting result. This result is particularly relevant for a whole portion of the theoretical literature on scaling laws, assuming that scaling results from the Zipf distribution of the data features. In particular, our result suggests that the approach based on the feature distribution is not the right one for NPT, although it may be suitable for classification.\n\n## Questions\n\n1. Rather than making the task easier, having Zipf-distributed production rules results in the separation of data into different categories. Those having only the most frequent production rules ($k=1,2,\\dots$) are easier to learn compared to the uniform case $f_k=1/m$, whereas those having some rare production rules $k=m,m-1,\\dots$ are harder. As a result, the sigmoidal learning curve of the uniform case turns into a power law. ***In the revised manuscript***, we will add the learning curves of classification in the uniform case to Figures 2 and 7 to clarify this point.\n\n2. The behaviour of the individual steps is indeed changing, as highlighted in Figure 4. However, when considering a sequence of steps, the overall scaling is determined by the distance between the steps (which is controlled by the hierarchical structure) rather than the behaviour of the single step (controlled by the ZIpf law).\n\n3. We should stress that our result is asymptotic, so it does not apply to the very first step. That said, what changes with $a$ is not only the cross-entropy lower bound (which causes a vertical shift of the curves), but also the sample complexities of the steps from Eq. (13) (causing a horizontal shift of the curves). However,  the way that such sample complexities depend on the level of the step is independent of $a$: that's why the scaling law remains unchanged. \n\n4. In the uniform case $f_k=1/m$ for all $k$'s. There is only one sample complexity $P^*=v m^L$, and the test error crosses over from $\\simeq 1$ to $\\simeq 0$ around $P^*$. Following the suggestion of Reviewer gXnS, we will add further background material on Cagnetta et al., 2024, that clarifies this point.\n\n5. The reviewer is correct that it is an upper bound. Depending on the value of $m/v^{s-1}$, the root can still be inferred correctly without resolving all of the patches. The probability for this to happen is derived in (Sclocchi et al., PNAS 2024) for an optimal decoder. However, notice that, if $m=v^{s-1}$ as in figures 2 and 3, changing one patch changes the root label with high probability, implying that all patches need to be resolved. ***In the revised manuscript***, we will add a sentence after equation (6) to clarify this point.", "claims_and_evidence": "The derivation of their theoretical results relies on an assumption (Assumption 3.1), which is not rigorously proven but is intuitively used. This assumption states that as long as the correlation between features is distinguishable from noise, the model can correctly predict the class or next token. Based on this assumption, the authors, without proof, use the fact that if the correlations are statistically resolvable, the model can always correctly classify the sequences in the case of classification, or that the cross-entropy loss matches the loss of an $\\ell$-gram model in the case of next-token prediction (a similar assumption is made in Cagnetta & Wyart (2024)).\n\nApart from this assumption, the rest of the theory is solid and extends the asymptotic analysis from the previous works by Cagnetta & Wyart (2024) and Cagnetta et al. (2024) to the case where the rules have non-uniform distribution.\n\nThe empirical results validate the accuracy of this asymptotic analysis for CNNs/Transformers trained on the RHM data.", "methods_and_evaluation_criteria": "The theory and empirical results support the scope and claim of the paper for the RHM setup.", "theoretical_claims": "(I followed the proof sketch from the main body but skipped the details in the supplementary material. See \"Claims And Evidence\".)", "experimental_designs_or_analyses": "The experimental analysis fits within the scope of the paper and supports its claims. \n\n(See \"Weaknesses\" for further comments on the experiments.)", "relation_to_broader_scientific_literature": "There is a substantial body of empirical papers on scaling laws. As also listed in the paper, many previous works explain the scaling laws from a theoretical perspective in simplified setups like linear/kernel regression. \n\nThis paper builds on the previous works by Cagnetta & Wyart (2024) and Cagnetta et al. (2024), which use the RHM to study learning from hierarchical data. These earlier works derived loss behavior and scaling laws under the assumption of a uniform rule distribution. This paper extends that analysis to consider non-uniform rule distributions.", "essential_references_not_discussed": "None that I’m aware of.", "other_strengths_and_weaknesses": "**Strengths**:\n\nThe synthetic setup is nice: compared to previous papers that focus on regression tasks to derive scaling laws, the RHM provides a closer model to language, where the problem consists of discrete vocabularies and sequential data. While it cannot perfectly capture all aspects of natural language, it offers a nice, controllable framework that models the hierarchical and tokenized nature of language.\n\n**Weaknesses**:\n\n1. One aspect that needs to be emphasized in the main body is the training setup. Scaling laws (e.g, as in Kaplan et al. (2020)) can be derived in different setups depending on whether data, model size, or FLOPs is the bottleneck. \n\n    I assume in this paper, data is the bottleneck, while model size and FLOPs are flexible (can be unbounded). It's mentioned in App A. that the classification experiments are run for a large number of epochs. However, this detail seems to be missing for the next-token prediction experiments. Whether the model is trained for a single pass or multiple epochs, and the size of the model, might influence the behavior of the scaling laws. Specifically, it would be useful to know whether the training length was long enough and the model size large enough for the training loss to reach its lower bound, or if the experiments were conducted in the under-trained regime. Additionally, it would be helpful to know whether the test loss for each given dataset size $P$ has converged.\n\n2. The emergence of scaling laws for NTP in the case of RHM, due to the hierarchical structure of the data, was already demonstrated in Cagnetta & Wyart (2024). In that sense, this paper does not offer additional insights for NTP. However, in the case of classification, the observation that changing the distribution of the rules can alter the scaling behavior is an interesting observation.", "other_comments_or_suggestions": "Minor typos: \n- line 217 first column, Theorem in \"Assumption Theorem 3.1\" is extra.\n- Line 159, second column, have you defined $n_c$ in the expression for $P^*(\\mathbf{\\mu})$?\n- From what I understand, the analysis is for the joint expectation of the loss over the realization of RHM and the sequences $x$. Is that also the case in eq (14) (and (15))? The current notation used in the equation only takes expectation over the sequences.", "questions_for_authors": "In Sec 3.1, the different loss behavior in the case of classification is attributed to the difficulty of resolving the correlations for the rare production rules. A few questions regarding this argument:\n1. In the figures, the larger $a$ is (further away from the uniform distribution), the error/loss decays faster in both cases. So, is having the Zipf's distribution over the rules making the task easier?\n2. The same argument about the rare rules and correlation should hold true in the case of NTP as well. But why isn't the behaviour changing?\n3. Given that your analysis shows the scaling behavior is unchanged, can you explain the source of the gap between the loss curves for different values of $a$ in the NTP task? Based on the analysis, the only thing that should change with $a$ is the cross-entropy lower bound, which is not surprising since changes in the distribution affect the entropy of the data.\n4. Can you explain what happens with $a=-1$ (uniform rule distribution) in the classification case? Eq (7) cannot be evaluated at this value.\n\n**Minor question:**\n\n5. In Equation (6), is the right-hand side (RHS) an equality, or is it only an upper bound on the error? The RHS measures when all patches are resolvable, but a model could still make a correct prediction by resolving the majority of patches correctly, right?", "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:

Meta-review: This paper presents a theoretical study of learning curves in neural networks trained on hierarchically structured data with Zipf-distributed features, modeled via a probabilistic context-free grammar. It extends prior work on the Random Hierarchy Model by introducing nonuniform (power-law) production rules. The key finding is that Zipf-distributed rules lead to power-law learning curves in classification, while next-token prediction exhibits a scaling exponent governed solely by the hierarchical structure, independent of Zipf statistics.

Reviewers generally found the theoretical analysis sound and the experimental validation on synthetic data well-executed. The distinction between classification and prediction regimes is novel and insightful. One reviewer raised concerns about clarity and reliance on prior work, suggesting the paper could be made more self-contained. The authors provided a thorough rebuttal, addressing these concerns and outlining plans for improving the manuscript.

Overall, the paper makes a solid theoretical contribution to our understanding of neural scaling laws and the effects of data structure. While some exposition improvements are needed, the results are valuable and relevant to the ICML community.
Decision: Accept (poster)