Learning curves theory for hierarchically compositional data with power-law distributed features

Weaknesses

1. 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.

2. 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.

Questions

1. 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.

2. 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).

3. 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.

4. 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.

5. 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.

Theoretical claims

1. 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.

2. 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.

3. 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}$.

4. 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).

Experimental designs

The 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.

Relation to broader literature

As the reviewer suggests, in the revised manuscript, we will add a section before 3, including,

1. 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).

2. 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.

Significance for practitioners

Despite 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.

Other comments

We will clarify line 125 and replace $\mathcal{N}$ in line 339.

We thank the reviewer for appreciating our study's strengths. Regarding the connection with real data, please see the reply to Reviewer GeDB.

Concerning 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.

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.

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.

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.