Towards a theory of how the structure of language is acquired by deep neural networks

Authors: francesco  cagnetta
matthieu  wyart
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 18:53:32

Abstract: How much data is required to learn the structure of a language via next-token prediction? We study this question for synthetic datasets generated via a Probabilistic Context-Free Grammar (PCFG)---a hierarchical generative model that captures the tree-like structure of natural languages. We determine token-token correlations analytically in our model and show that they can be used to build a representation of the grammar's hidden variables, the longer the range the deeper the variable. In addition, a finite training set limits the resolution of correlations to an effective range, whose size grows with that of the training set. As a result, a Language Model trained with increasingly many examples can build a deeper representation of the grammar's structure, thus reaching good performance despite the high dimensionality of the problem. We conjecture that the relationship between training set size and effective range of correlations holds beyond our synthetic datasets, and we test it in a collection of lines from Shakespeare's plays. In particular, we show that reducing the input size leads to saturation of the test loss decay at a characteristic training set size that can be predicted in our framework.

Main paper: 
 introduction: 
 Two central foci of linguistics are the language structure and how humans acquire it. Formal language theory, for instance, describes languages with hierarchical generative models of grammar, classified in different levels of complexity [1, 2] . In this context, the 'poverty of the stimulus' argument [3] stating that the data children receive is insufficient to uniquely determine the grammatical structure of their language-led to the hypothesis that linguistic faculties are largely innate. By contrast, statistical learning theory [4, 5] posits that the statistics of the input data can be used to deduce the language structure. This assumption is supported by empirical evidence concerning a broad range of tasks, including word segmentation [6] and reconstruction of the hierarchical phrase structure [7] .Large Language Models (LLMs) offer an interesting perspective on the subject. For instance, the success of LLMs trained for next-token prediction [8, 9] establishes that a language can be acquired from examples alone-albeit with a training set much larger than what humans are exposed to. Furthermore, empirical studies of LLMs' representations showed that they learn a hierarchy of contextual information, including notions of linguistics such as word classes and syntactic structure [10, 11, 12] . Recent studies have begun revealing the inner workings of LLMs by using synthetic data generated via context-free grammars [13, 14] , determining, in particular, the algorithm that these models follow when predicting the next token. However, there is no consensus on the mechanisms behind language acquisition by LLMs [15, 16] . As a result, empirical phenomena such as the scaling of the test loss with dataset size and number of parameters [17] and the emergence of specific skills at certain scales [18, 19] remain unexplained. In this work, we use hierarchical generative models of data to describe how the structure of a language is learnt as the training set grows.We consider synthetic datasets generated via the Random Hierarchy Model (RHM) [20] , an ensemble of probabilistic context-free grammars (PCFGs). The RHM generates sequences of tokens by applying randomly chosen production rules to a hierarchy of hidden variables that live on the nodes of a tree with fixed geometry.• We characterise analytically the power-law decay of the correlations between tokens with their distance. We then show that, because of this decay, a finite training set size P limits the resolution of correlations to an effective context window, whose size t * increases with P .• Building on previous works on classification, we argue that deep learning models trained on next-token prediction can use measurable correlations to represent the hidden variables of the PCFG, with larger P allowing the representation of deeper hidden variables.• Combining these results, we predict a sequence of sample complexities where the emergence of a deeper data structure representation leads to a jump in test loss. We empirically validate this for deep transformers and CNNs. Notably, the sample complexities are polynomial in the effective context size t * , avoiding the curse of dimensionality.• We conjecture that the relationship between training set size, correlations and effective context window holds beyond our data model, and we test it by training deep transformers on collections of Shakespeare's lines and Wikipedia articles. In particular, we find that the test loss decay levels off at a characteristic training set size that depends on the length of the context window and can be measured from token-token correlations.Fixed-tree hierarchical generative models have been introduced to study phylogeny [21] , then used in supervised learning [22, 23, 20, 24] and score-based diffusion [25, 26] . In particular, [22] introduced a sequential clustering algorithm that reveals the importance of correlations between the input features and the labels for supervised learning. The RHM of [20] provides a framework to show how featureslabel correlations emerge from the generative model and can be used by deep networks to represent the hidden hierarchical structure of the data. Here we extend this result to self-supervised learning, where the relevant correlations are those between the different input features.PCFGs can in principle generate sequences with token correlations that decay as a power of their distance [27] . When the production rule probabilities are random [28, 29] , these probabilities must follow a broad distribution for the data to retain information about the generative process. Learning a PCFG from examples is a longstanding problem of theoretical linguistics [30] . While some PCFG classes are learnable using distributional information [31] , the sample complexity is unknown. In the context of deep learning, PCFGs have been used to study how trained transformers encode the grammar's structure [13, 14] . [14] , 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 is compatible with both a PCFG and a non-hierarchical generative model, neither recurrent language models [32] nor transformer [33] consistently prefer the hierarchical explanation. In addition, none of these works study the learning process.Empirical work on the learning dynamics of Long Short-Term Memories showed that short-range dependencies are learnt first, then used as a foundation for forming longer-range dependencies [34] .Our work introduces a theoretical framework to explain this hierarchical inductive bias, focusing on the learning curves of deep learning architectures. Shortly after our submission, [35] unveiled another form of hierarchical inductive bias in the training dynamics of transformers, whereby many-body interactions among tokens are learnt in the order of the interaction's degree.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes]Justification: The analytical study of correlations in our generative model is presented in section 3. In section 4 we build our prediction of the learning curve based on reconstructing the grammar's hidden variables and compare it with the empirical learning curves of transformers trained on our model dataset. Our general conjecture is presented in section 5, together with experiments on real text data.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
notation and setup: 
 This work focuses on the pretraining phase of language models, aimed at building an approximation of the data distribution via unlabelled examples [8, 9] . Let us define a text datum, or sentence, as a sequence x = (x 1 , . . . , x d ) of d tokens belonging to a finite vocabulary V. Denoting with v the vocabulary size, each token x i is represented as a v-dimensional one-hot vector (x i,µ ) µ=1,...,v1 :EQUATIONA dataset, or corpus, consists of a probability distribution over sequences, which measures the frequency at which a given combination of tokens appears within the text. Assuming that all sequences have length d, the data distribution is a joint probability over d-dimensional sequences with elements in V, P X (x) := P {X 1 = x 1 , . . . , X d = x d } . The specifics of the approximation of P X depend on the training objective. In Masked Language Modelling, for instance, a random fraction of tokens is masked, i.e. replaced with a fixed token x mask , and the model is tasked with predicting their value [8] . Autoregressive language models, instead, are trained to predict the i-th token of a sequence based on all the previous ones [9] . Here we consider a simplified setup where the last token of the sequence is masked and the model is trained to predict it. In other words, the model takes the context window (x 1 , . . . , x d -1 ) as input and outputs a parametric approximation p θ of the conditional probability of the last token, p θ (x d |x 1 , . . . , x d-1 )EQUATIONobtained by updating the parameters θ via gradient descent on the empirical cross-entropy, L(X P ) = -1EQUATIONwhere X P is a set of P training examples drawn from P X . Numerical experiments are performed in PyTorch [36] , with the code available at https://github.com/fracagnetta/ random-hierarchy-model. Details of the machine learning models, training hyperparameters and computer resources are presented in App. A.To model the hierarchical structure of sentences, we consider synthetic datasets generated via a probabilistic context-free grammar (PCFG) [37] . PCFGs are collections of symbols and rules that prescribe how to generate sequences. In particular, the PCFGs we consider consist of • L finite vocabularies of hidden (nonterminal) symbols (V ℓ ) ℓ=1,...,L ;• A finite vocabulary of observable (terminal) symbols V ≡ V 0 ;• L sets of production rules describing how one symbols of V ℓ generates a tuple of symbols of V ℓ-1 , for ℓ = 1, . . . , L.Production rules take the form µ (ℓ) → µ (ℓ-1) 1, . . . , µ (ℓ-1)EQUATIONfor some integer size s ℓ ≥ 1. The left panel of Fig. 1 shows an example of the generative process, represented as a tree: pick (uniformly at random) a level-3 symbol (root) and one of the production rule having that symbol on the left-hand side (also uniformly at random), replace the symbol with the right-hand side of the production rules (first generation), then repeat the process until left with only terminal symbols (leaves). The resulting datum is a sequence in (V 0 ) d , with d = ℓ s ℓ . Assuming a finite number of production rules emanating from each nonterminal symbol, this model generates a finite number of d-dimensional sequences. Since the probabilities of the level-L symbol and the production rules are uniform, the data distribution P X is uniform over the generated sequences.The Random Hierarchy Model (RHM) of [20] is an ensemble of such generative models, obtained by prescribing a probability distribution over production rules. In particular, the ℓ-th set of production rules is chosen uniformly at random between all the unambiguous sets of rules in the form of Eq. 4. Unambiguity means that each s ℓ -tuple of level-(ℓ -1) symbols can be generated by one level-ℓ symbol at most. The uniform probability and unambiguity assumptions are not satisfied in a generic natural language, but they allow us to characterise quantitatively the effects of the hierarchical structure. We will further assume, to ease notation, that all the vocabularies V ℓ have the same size v and that the size of the production rules is homogeneous, i.e. s ℓ = s for all ℓ. We further assume that each nonterminal appears as the left-hand side of exactly m production rules, i.e. the hidden symbols have m equivalent low-level representations. Since there are v s distinct low-level representations and each of the v high-level symbols is assigned m, unambiguity requires m ≤ v s-1 . As a result, a finite training set only allows for measuring correlations with the tokens up to a certain distance t * (P ). Graphically, t * (P ) corresponds to the highest value of t where the empirical estimate matches the true correlation (e.g. 1 for the orange and green curves, 3 for the red curve).Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: We included a limitation section in the conclusions.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
correlations, training set size and effective context window: 
 Given a dataset of d-dimensional sequences of tokens in V, we measure correlations via the token co-occurrences matrix, 2EQUATIONwhere µ and ν are arbitrary elements of the vocabulary V and P refers to the data distribution P X .Since the masked token is always the last in our setup, it is convenient to set j = d and write C i,d as a function of the distance t = |i -d| between the i-th and the masked token. Taking the root mean square over the vocabulary yields the correlation function,EQUATIONwhich measures the typical dependency between tokens as a function of their distance t. For RHM data with m = v s-1 , P X is uniform over all the possible sequences of tokens in V and there are no correlations. If, instead, m < v s-1 , the correlations strength depends on the distance. Fig. 1 shows an example for RHM data with L = 4, s = 2, v = 32 and m = 8.Correlations decay with distance. The stepwise decay of C(t) mirrors the tree structure of the generative model. The masked token has the highest correlations with those belonging to the same s-tuple, as they were all generated by the same level-1 symbol (as in the blue box of Fig. 1 , left). The second highest is with the tokens generated by the same level-2 symbol (orange box in the figure), and so on until the root. Formally, with ℓ = 1, . . . , L denoting the height of the lowest common ancestor (LCA) of the d-th and (dt)-th tokens,EQUATIONThese L plateau values can be determined analytically in the large v limit by approximating the variance over the vocabulary entries µ and ν on the right-hand side of Eq. 7 with the variance over realisations of the RHM. Denoting the average over such realisations with ⟨.⟩,EQUATION2 Ci,j(µ, ν) is also equivalent to the covariance matrix of the one-hot representation, where the rightmost equality is exact asymptotically in v and m. Eq. 8 is derived in detail in App. D, confirmed empirically in the right panel of Fig. 1 and can be given a simple interpretation in terms of the sample size required for the empirical measurement of correlations, as discussed in the following paragraph. In addition, notice that, upon replacing s ℓ with t, the m -ℓ dependence on ℓ is approximated by a power-law decay C(t) ∼ t -β , with β = log m/ log s.E [(Xi,µ -E [Xi,µ]) (Xj,ν -E [Xj,ν ])]Saturation due to finite training set. When measuring the correlation function from a finite sample X P of P data, there is an additional contribution due to the sampling noise. The scenario is illustrated in Fig. 1 , right: the empirical estimates ĈP (t), shown as coloured lines for different values of P , begin by following the descent of the true correlation function C(t), shown as a black dashed line. However, empirical estimates saturate when approaching the sampling noise size (v 2 P ) -1/2 , as proved in App. E and shown as dashed coloured lines in Fig. 1 , right. Combining the saturation with the values of the steps, we deduce that a finite training set allows for the resolution of correlations upEQUATIONEq. 9 suggests that a language model trained with P examples can only extract information from the tokens within distance t * (P ) from the last. In other words, a finite training set is equivalent to an effective context window of size t * (P ). If C ∼ t -β , then t * (P ) ∼ P 1/2β . Alternatively, setting C(ℓ) = (v 2 P ) -1/2 yields a sequence of thresholds P ℓ for the resolution of correlations of increasing range. From Eq. 8, P ℓ ∝ vm 2ℓ-1 , which has a simple interpretation as the number of choices in the generative process to determine two tokens at a distance t ∈ [s ℓ-1 , s ℓ ): v choices for the level-ℓ LCA, m for the first production rule and m 2 (m per branch) for each of the remaining ℓ -1 generations.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] Justification: The calculations of section 3 and subsection 4.1 are correct within the scope of our model of data. Our results on how the correlations affect the learning curves of deep networks trained in self-supervised learning can be considered conjectures, which we systematically test with numerical experiments. Indeed, no current formal approach can treat the learning dynamics of deep networks in the feature learning regime. This situation is described in the 'limitation' section. Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
self-supervised learning of the random hierarchy model: 
 We now show how the correlations can be translated into a prediction of sample complexities that allow for a sequence of increasingly accurate approximations of the masked token probability, based on reconstructing the hidden variables of the generative tree. We then test these predictions in numerical experiments with deep networks.Loss steps. Due to the structure of the data, there is a natural sequence of L increasingly accurate approximations of the last token probability in Eq. 2. For all ℓ = 1, . . . , L, these approximations are realised by conditioning the probability of the last token on the previous s ℓ -1. These approximations amount to using an effective context window of size t ℓ = s ℓ -1. The effective context windows consist of the leaves of the subtree generated by the level-ℓ hidden symbol above the last token, as illustrated by the coloured boxes of Fig. 1 , left. The resulting cross-entropy loss is given byEQUATIONwhere N (x d-s ℓ +1 , . . . , x d-1 ) denotes the number of possible values of the masked token depending on the effective context window. For ℓ = 0, there is no restriction on the masked token value and this number equals v-the vocabulary size. EQUATIONNaive strategy. The simplest strategy to estimateP {X d |X d-s ℓ +1 = x d-s ℓ +1 , . . . , X d-1 = x d-1 }is to count the empirical occurences of the s ℓ -dimensional subsequences of the input in the training set-the so-called n-gram language model with n = s ℓ . This estimation requires the training set to contain all the distinct subsequences of size s ℓ . Following the generative process, each of these subsequences occurs with probability given by that of the corresponding LCA symbol (the root of the subtree encased by the corresponding coloured box in Fig. 1 , left), times the probability of the production rules that generate the subsequence from the LCA, 1) . The latter is exponentially small in the effective context length t ℓ = s ℓ -1, hence the required sample size is exponentially large in t ℓ .m -1 × m -s × • • • × m -(s ℓ -1) = m -(s ℓ -1)/(s-Efficient strategy leveraging the hidden variables. Using the hidden variables results in a much lower sample complexity. Indeed, due to the tree structure of PCFGs, the value of the last token is conditionally independent of most of the observable tokens when the hidden variables are given. For instance, looking at the tree in Fig. 1 , left, the probability of the last token is independent of the pair (µ (0) 5 , µ (0) 6 ) if the parent level-1 variable µ (1) 3 is given. In general, fixing a hidden symbol splits the tree into an inside (the subtree rooted at the hidden symbol) and an outside (the rest of the tree) that are conditionally independent. As a result, the minimal set of variables that the s ℓ -gram probability depends on consist of s -1 observable tokens (those in the same patch as the last token) and (s -1)(ℓ -1) hidden variables ((s -1) for each level below the LCA of the context window). The probability of any such set of variables is given by the LCA probability times m -ℓ . The resulting sample complexity grows exponentially with ℓ, or as a power of the effective context length t ℓ .Reconstruction of the hidden variables. We now argue that, as shown [20] in the context of classification, the hidden variables can be represented via the correlations between tokens. Consider, for instance, the pair (µ (0) 5 , µ (0) 6 ) in Fig. 1 , left. Because of the aforementioned conditional independence, the correlation between any such pair and the last token depends only on the level-1 hidden variable µ (1) 3 . Thus, pairs displaying the same correlations can be grouped as descendants of the same hidden variable. This strategy requires enough training data to resolve correlations between the masked token and the adjacent s-tuples of observable tokens. As shown in App. F, replacing an observable token with a whole s-tuple reduces correlation plateaus and sampling noise by the same factor. Therefore, the condition for the resolution of correlations with the nearest s-tuples is given by Eq. 9 with ℓ = 2, implying P > P 2 = vm 3 . By iterating this argument we get a sequence of sample complexities P ℓ that allow for resolving correlations between the masked token and s-tuples up to distance t = s ℓ -1,EQUATION)For instance, in the case illustrated in Fig. 1 , left, the correlations of the pairs (µ (0) 1 , µ (0)2 ) and (µ (0) 3 , µ (0) 4 ) with the masked token can be used to reconstruct the pair of hidden symbols (µ (1) 1 , µ (1) 2 ). The hidden symbols have a higher correlation with the masked token than their children. Hence, as in the case of classification [20] , a training set large enough to resolve correlations between observable and masked tokens also allows for resolving correlations of the masked token with the hidden symbols. These correlations yield a representation of higher-level hidden symbols (e.g. µ (2) 1 for (µ (1) 1 , µ (1) 2 ) in the figure), which, in turn, enables the reconstruction ofP {X d |X d-s ℓ +1 = x d-s+1 , . . . , X d-1 = x d-1 }via the efficient strategy. As ℓ increases, the sample complexity of Eq. 12 grow faster than m ℓ , but still polynomially in the effective context length t ℓ .Scaling law of the RHM. After solving Eq. 12 for ℓ as a function of P , we can use Eq. 11 to derive the scaling law for the behaviour of the loss steps as a function of the training set size P . Neglecting all the factors that do not depend on ℓ, Eq. 12 implies ℓ ≈ log P/(2 log m). Thus, from Eq. 11,EQUATION)Notice that f < 1, thus log f < 0. Therefore, Eq. 11 implies an early logarithmic decay as long as| log f | log P ≪ 2 log m log (v(1 -f )).For larger P , the expansion log (1 + x) ≃ x recovers the ubiquitous power-law decay P -α [17] , with exponent α = log f /(2 log m). Notice that the power-law scaling is caused by the sequence of steps associated with the emergence of the hidden variables representation. Therefore, this picture unifies the emergence and scaling paradigms. Additional experiments that support the quantitative scaling of the sample complexities P 1 and P 2 with m are shown in App. G. Fig. 2 , right, shows the learning curves of models trained on a reduced context window. In this setting, our description correctly predicts the saturation of the loss due to the finite context window size t: with t = s ℓ -1, the model can only learn the level-ℓ hidden variable above the masked token, thus follow only the first ℓ of the L steps of Eq. 11.Let us remark that, as shown in App. G, the learning curves are qualitatively similar for CNNs, despite a noticeable quantitative dependence on architecture and context size t. These differences are not captured by the analysis of subsection 4.1, although, in some cases, they can be rationalised using results from the theory of shallow neural networks. We discuss these aspects in detail in App. G.We now study the hidden representations of models trained on RHM data to show that, as the training set size increases, these representations encode for deeper hidden variables. More specifically, we show that certain representations depend only on specific, high-level hidden variables of a datum's tree structure, thus becoming insensitive to the entire subtree emanating from this hidden variable.For the sake of interpretability, we consider deep convolutional networks (CNNs) with architecture matched to the data structure, represented schematically in the graphs on the right of Fig. 3 (further details in subsection A.1). To probe representations we introduce two sets of transformations. Given a datum and the associated tree ( Fig. 1 , left), consider the i-th level-ℓ symbol µ (ℓ) i : S ℓ,i replaces it with another one randomly chosen from the vocabulary, whereas R ℓ,i resets the choice of the production rule emanating from µ (ℓ) i . Both transformations alter the subtree originating from µ (ℓ) i (e.g. the subtree within the orange box of Fig. 2 , left for ℓ = 2 and i = 2), affecting s ℓ observable tokens. However, R ℓ,i preserves the hidden symbols that generated the subtree. Therefore, a hidden representation that encodes only the i-th level-ℓ hidden symbol will be invariant to R ℓ,i but not to S ℓ,i . We define hidden representations h ℓ (x) (hidden nodes of the network's graphs in Fig. 3 ) as the sequence of pre-activations in a given layer ℓ (depth of the node in the tree), standardised over the dataset (i.e. centred around the mean and scaled by the standard deviation). For CNNs, representations carry a spatial index j = 1, . . . , s L-ℓ (horizontal position of the node within the layer) and a channel index. We measure the sensitivity to R or S via the cosine similarity between original and transformed representations, i.e.EQUATIONwhere the • symbol denotes the scalar product over the channels. In order to leave the masked token unaltered, we always apply the transformations to the penultimate hidden symbol of the level, i.e. i = s L-ℓ -1. Hence, from now on, we omit the spatial index i. The left column of Fig. 3 reports the ratio r ℓ /s ℓ for the hidden representations of a deep CNN trained on RHM data. Each row refers to the level of the data transformations. The group of observable tokens affected by the transformation is highlighted by horizontal square brackets in the right panels. The drop of r ℓ /s ℓ from ≈ 1 to ≈ 0 signals that a representation depends on the corresponding level-ℓ hidden variable, but not on the other variables in the associated subtree. 3 These drops occur at the same training set sizes P ℓ as the 3 Notice that only the representations with ℓ ′ > ℓ can become invariant, which is due to the fact the production rules are not linearly separable. Let us focus on the first level: the corresponding s-dimensional patch of the input can take mv distinct values-m for each of the v level-2 features. Invariance of a linear transformation is equivalent to the following set of constraints: for each level-2 features µ, and x1,i encoding for one of the m level-1 representations generated by µ, w • x1,i = cµ. Since cµ is an arbitrary constant, there are v × (m -1) constraints for the v × s components of w, which cannot be satisfied in general unless m ≤ (s + 1). The empirical curves ĈP (t) collapse when rescaling correlations by the sampling noise size P -1/2 and t by the characteristic distance t * (P ) ∼ P 1/z , with z ≃ 2.8. Bottom, Left: As predicted by our conjecture, the losses collapse when rescaled according to Eq. 16 with the same z as the correlation functions.test loss steps, highlighted in the figures with vertical dashed lines. This result confirms that, as P increases, trained models learn a deeper representation of the tree structure of the data.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [Yes] Justification: We use standard machine-learning frameworks in all of our experiments, as described in section 2 and App. A. Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. • The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
conjecture and test on real language data: 
 We conjecture that the relationship between training set size, correlations and effective context window holds beyond our synthetic dataset.Conjecture: "If the token correlation function decays with the token distance, then a language model trained to predict the next token from a training set of P examples can only extract relevant information from an effective context window of P -dependent size t * (P )."We test this conjecture in two datasets: a selection of lines from Shakespeare's plays [38] and a collection of articles from English Wikipedia [39] . For both datasets we adopt a character-level tokenisation, resulting in over 10 6 tokens. We then extract sequences of t consecutive tokens and train BERT-like deep transformers in the setup of section 2-further details of architecture and training are in subsection A.3. The results of our test are reported in Fig. 4 for Shakespeare and Fig. 5 of App. B for Wikipedia. First, with a large context window, the test loss follows the empirical scaling law L ∼ P -α (top left panel). However, the learning curve levels off at some characteristic scale P that grows with the size t of the context window. This phenomenon can be explained via the correlation function, which decays as a power of the distance C(t) ∼ t -β , with β ≃ 1.4 4 (top right panel). Empirical estimates ĈP (t) saturate when reaching the sampling noise scale ∼ P -1/2 : following the analysis of section 3, this behaviour results in an effective context window size t * (P ), given by the value of t where the correlation function C(t) ∼ t -β intersects the sampling noise scale ∼ P -1/2 ,EQUATIONAs a result, the empirical correlation functions with varying P collapse when rescaling Ĉ by the sampling noise and the distance by t * (P ) (bottom right panel).By inverting t * (P ) we get a characteristic training set size P * (t) where the training set allows for resolving correlations at all distances t ′ < t, P * (t) ∼ t z . Paired with the empirical power-law scaling with P , this result leads to the following context-dependent scaling hypothesis for the test loss:EQUATIONwith f (x) ∼ x -α for x ≪ 1 and constant for x ≫ 1. In particular, Eq. 16 implies that the behaviour of the empirical correlation functions predicts the saturation of the loss decay. The collapse reported in the bottom left panels of Fig. 4 and Fig. 5 quantitatively confirms Eq. 16 and our previous conjecture. 
conclusions: 
 We proposed a conceptual framework for understanding the performance-vs.-data scaling laws of language models trained for next-token prediction. In our picture, increasing the number of data allows for the resolution of a longer range of correlations. These correlations, in turn, can be exploited to build a hierarchical representation of the data structure, the longer the range the deeper the representation. For our synthetic hierarchical data, the emergence of deeper representation results in a series of steps in the next-token prediction performance. These steps conspire to determine the scaling law, whose exponent depends on the dataset structure. This scenario is consistent with the empirical phenomenology of language models, including both the emergence of skills at specific training set sizes [18, 43, 44, 45] and the steady improvement of overall performance [17] . To the best of our knowledge, this is the first theoretical description of scaling laws in a setting where learning data features is crucial, whereas previous works focused on kernel limits [46, 47, 48, 49, 50] .Furthermore, our analysis predicts a fundamental relationship between the effective context window captured by a language model trained with a finite training set and the decay of token-token correlations, which we confirmed empirically on two examples of text data. This finding suggests that the exponents entering scaling laws are influenced by the intrinsic properties of the data. On the one hand, our predictions can be tested on state-of-the-art LLMs trained on larger datasets. On the other hand, our framework can be extended to shed light on other aspects of scaling laws of high practical relevance, such as the role of the number of parameters and the behaviour of performance when the model size and the number of data are optimised under a fixed compute budget.Limitations. Our hierarchical model of data is limited by the context-free structure of the rules, which describes most, but not all, of the syntactic forms observed in natural languages [51] . Understanding the role of context-sensitive structures in language acquisition is a promising avenue for future research. In addition, the RHM assumes a fixed geometry of the data tree and the uniform probability and unambiguity of the production rules. These assumptions are not satisfied by real text data and are responsible for the stepwise behaviour of correlations in our model. Relaxing these constraints while keeping the large-scale, power-law decay of correlations with the distance, which is indeed observed in real data, could broaden the scope of our conceptual framework. On the technical side, there is no proof of the connection between the strategy illustrated in subsection 4.1 and the sample complexity of deep neural networks trained with gradient descent and its variants. Such a proof would require a formal description of the dynamics of deep networks trained on hierarchical data, which is beyond the scope of the present paper. This description would also capture the discrepancies between different architectures presented in App. G, making it a valuable direction for future work. ), with an estimated total (including hyperparameter tuning) of 6, 000 GPU hours. We provide architecture and training details below. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: This information is indicated at the end of section 2.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This work seeks to improve our theoretical understanding of self-supervised learning techniques. Thus, there are no foreseen negative impacts and it is difficult to estimate possible positive impacts.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Due to the theoretical nature, the paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes]Justification: We properly cited the authors of the models and dataset used in this paper.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: 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 s and the CNNs depth equals log d/ log s.We use the Rectified Linear Unit (ReLU) σ(x) = max (0, x) as activation function, set the number of channels to H for each layer, and consider the maximal update parametrization [53] , 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 a factor H -1/2 , whereas the last is rescaled by H -1 . This factor causes the output at initialization to vanish as H grows, which induces representation learning even in the H → ∞ limit. In practice, H is set to 256 for Fig. 3 , 512 for Fig. 6 , left and Fig. 9 , 1024 for Fig. 6 , right, 512 for Fig. 7 and Fig. 8 . Increasing the number of channels 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 -1 . A cosine annealing scheduler reduces the learning rate by 10 within the first 100 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 -3 . We use a validation set of size 2 15 to select the model with the best validation loss over the training trajectory.The deep Transformers that we train on RHM data are made by stacking standard Multi-Head Attention layers [54] , without any residuals, layer normalization 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 h and embedding dimension d emb = n h × v, with v the vocabulary size. The input dimension is adapted to the embedding dimension via a learnable linear projection, to which we add learnable positional encodings. The choice of n h follows two principles: the model should be large enough for the training loss to reach a threshold value of 10 -3 and changing n h should not affect performance beyond the fluctuations due to the model initialisations. Specifically, we set n h = 16 and notice no significant change in performance up to n h = 64. Also scaling d emb up to 4n h × 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 -2 within the first 10 training epochs. As for CNNs, the batch size is set to the lowest value allowing for convergence.The architectures trained on real text data have the same structure as BERT [8] , that is they include additional token-wise two-layer perceptions (MLPs) after each self-attention layer, together with layer normalization operations before the attention layer and the MLP and residual connections. The training procedure is the same as above.For tiny-Shakespeare, we set the number of heads to n h = 8, the embedding dimension to d e = 256, the size of the MLP hidden layer to 4d e , and the number of layers to 3. For WikiText-103, we set n h = 8, d e = 512, and the number of layers to 6. Increasing the number of layers or the number of heads does not affect the results presented in the paper. 103 [39] (t as in the key). As in Fig. 4 , the loss saturates to some t-dependent value after reaching a characteristic training set size. Top, Right: Empirical correlation functions ĈP (t) with P as in the key, showing saturation for large t due to the sampling noise (coloured dashed). Bottom, Right: Collapse of the empirical curves ĈP (t) is achieved when rescaling the correlations by the sampling noise size P -1/2 and t by the characteristic distance t * (P ) ∼ P 1/z , with z = 2β ≃ 3.1. Bottom, Left: As predicted by our conjecture, the losses collapse when rescaled according to Eq. 16 with the same z as the correlation functions and α ≃ 0.095.In this section, we report the results of the test of our conjecture for the WikiText-103 dataset of [39] .The original dataset was preprocessed to remove the article's headers and subheaders. The results are summarised in Fig. 5 , which displays the same measures as Fig. 4 and, as Fig. 4 , confirms our conjecture.For each token i = 0, . . . , d -1, single-token probabilities can be written as products of probabilities over the single production rules,EQUATIONi1 (µ|µ 1 ) . . . pEQUATIONwhere (i) the indices i L , . . . , i L are such that i L . . . i 1 equals the s-ary representation of i, with i ℓ = 0, . . . , s -1, and 0's added to ensure that the representation always consists of L indices. In other words, the multi-index i L , . . . , i L uniquely identifies the path linking the root of the tree to the i-th leaf. (ii) p (ℓ) i ℓ (µ ℓ-1 |µ ℓ ) denotes the probability of choosing, among the available production rules starting from µ ℓ , one that has the symbol µ ℓ-1 on the i ℓ -th position of the right-hand size.(iii) p (L) (µ L ) denotes the probability of selecting the symbol µ L as the root (1/v for our model).These decompositions arise naturally due to the connection between probabilistic context-free grammars and Markov processes. For the joint probability of two tokens i and j at distance t = |j -i|, with s ℓ-1 < t < s ℓ -1 such that the lowest common ancestor (LCA) is a level-ℓ hidden symbol, and i ℓ+1 denoting the position of the LCA within its level,EQUATIONBoth in Eq. 17 and Eq. 38 simplify when replacing µ with a whole s-tuple of observable symbols µ j = (µ 1+(j-1)s , . . . , µ js ) for some j = 1, . . . , s L-1 . The simplification arises because the level-1 rule probability p (1) (µ j |µ 1 ), is uniform and equal to 1/m if the production rule µ 1 → µ j exists, 0 otherwise. Then, the sum over µ 1 selects the only level-1 symbol that generates the tuple µ j . As a result, one is left with a probability represented by a smaller tree, where the s leaves representing µ j are pruned, and an additional factor of 1/m.For each set of production rules, we call N (ℓ) i (µ ℓ-1 ; µ ℓ ) the number of occurrences of the level-ℓ -1 feature µ ℓ-1 in the i-th position of the right-hand side for all the production rules emanating from the level-ℓ feature µ ℓ . In our generative model, there are m production rules emanating from a given symbol. The rule to follow when generating a datum is chosen uniformly at random among these m. Hence,EQUATIONFor the sake of clarity, let us omit the level index in the following paragraph. The probability of N i (µ; ν) over different realisations of the set of production rules is that of the number of successes when drawing m times (number of s-tuples associated with the high-level feature ν) without replacement from a pool of v s (total number of s-tuples with vocabulary size v) objects where only v s-1 (number of s-tuples displaying feature µ in position i) leads to success:EQUATIONwhere Hg n,K,N denotes a Hypergeometric distribution with population size N , K success states, and n draws. The mean and variance with respect to realisations of the RHM (denoted with ⟨.⟩ to avoid confusion with data averages E [.]) areEQUATIONFor v ≫ 1, the variance converges to m/v (m ≤ v s-1 with s fixed, thus v sm → v s ).Equations (19) to (21) easily generalise to the case where µ 0 represents a group of s ′ ≤ s low-level features (instead of a single low-level feature). With µ 0 denoting a s ′ -tuple of features and i the s ′ -tuple of associated spatial indices,EQUATIONresulting inEQUATION)An alternative way to obtain all statistics is by writing the level-ℓ probabilities as sums over the production rules,EQUATIONwhere r ψ,i (µ 1 ) denotes the i-th element of the right-hand side of the ψ-th production rule emanating from µ 1 . Eq. 24 generalises immediately to the case where i and µ ℓ-1 are s ′ -tuples with s ′ ≤ s. UsingEQUATIONwhere µ 1 ψ,i --→ µ denotes the event that the i-th element of the right-hand side of the ψ-th production rule emanating from µ 1 coincides with µ, we can compute all one-point averages. In addition, for (ν 1 , ϕ, j, ν) ̸ = (µ 1 , ψ, i, µ),EQUATIONwhereEQUATIONNotice that, once the right-hand side of the rules (µ and ν) are fixed, the conditional probability can only attain two distinct values: one for µ 1 = ν 1 and ψ = ϕ, and one for the other cases. Then, it is convenient to define a 'rule index' ψ that comprises both the starting high-level feature and the chosen production rule. This index runs in (1, . . . , mv). With these formulas, one can get all the joint statistics of the rules. For instance (omitting the RHM subscript on P to ease notation),EQUATIONhenceEQUATIONequivalent to dividing σ 2 N from Eq. 21 by m 2 . Analogously, with ν 0 ̸ = µ 0 ,EQUATIONthusEQUATIONNotice that c p = σ 2 p /(v-1) in agreement with the constraint µ0 p i (µ 0 |µ 1 ) = 1. Indeed, for any finite sequence of identically distributed random variables X µ with a constraint on the sum, µ X µ = C for some constant C,EQUATIONwhere, in the last line, we used the identically distributed variables hypothesis to replace the sum over µ ̸ = ν with the factor (v -1).EQUATIONthusEQUATIONandEQUATIONthusEQUATION)Given a dataset of d-dimensional sequences of tokens in V, we measure correlations via the token co-occurrences matrix, C i,j (µ, ν)EQUATIONwhere µ and ν are arbitrary elements of the vocabulary V and P X refers to the probability of the data distribution (distinct from P RHM , indicating the probability of the rules of the generative process). Joint and single-token probabilities are given by Eq. 17 and Eq. 38, respectively. We now prove Eq. 8 of the main text. D.1 Level-1 LCA (i-th and j-th tokens are in the same patch) When the LCA of the i-th and j-th tokens is a level-1 hidden symbol, i.e. the two tokens lie in the same s-patch,P {X i = µ, X j = ν} X = v µ1=1 p (1) i1,j1 (µ, ν|µ 1 )p (2)i2 (µ 1 ), (i 1 ̸ = j 1 ),EQUATIONWe consider the limit of large m, where the univariate probabilities of the hidden variables of any level converge to 1/v, with relative fluctuations of order 1/ √ m [20] 5 . In this limit, we can substitute the probability of the LCA with 1/v, thus obtaining,C (1) (µ, ν) = 1 v µ1 p (1)i1,j1 (µ, ν|µ 1 ) -EQUATIONi1 (µ|µ 1 )p(1)EQUATION)As we will prove in this and the following sections, the correlations have 0 average but nonvanishing variance. Including the fluctuations of the LCA probability results in corrections to the variance that vanish in the limit of large m. Furthermore, notice that we removed the dependence of C(µ, ν) on the positional indices i and j. This is because, asymptotically in v and m, the aforementioned statistics depend only on the depth of the LCA of i-th and j-th tokens, justifying our notation.SinceEQUATIONi1 (µ|µ 1 ) and pj1 (ν|ν 1 ) are independent. Hence, by Eq. 21 and Eq. 23 with s ′ = 2,EQUATIONThe variance/2nd moment readsEQUATIONi1,j1 (µ, ν|µ 1 )EQUATIONi1 (µ|µ 1 )EQUATIONi1,j1 (µ, ν|µ 1 )pi1 (µ|λ 1 )pj1 (ν|κ 1 ) .We will compute the three contributions on the right-hand side separately in the following subsections.EQUATIONi1 (µ|µ 1 )p(1)EQUATIONWe can split the sum into two kinds of terms: those with µ 1 = ν 1 (mult. v) and those with µ 1 ̸ = ν 1 (mult. v(v -1)). In the following, to simplify the notation, we omit the spatial index i.EQUATIONEQUATION)Variance of the marginal probabilityEQUATIONi1 (µ|µ 1 )EQUATIOND.1.2 Two-point term (joint probability)EQUATIONi1,j1 (µ, ν|µ 1 )EQUATIONi,j (µ, ν|µ 1 )pi,j (µ, ν|ν 1 ) .We can split the sum into two kinds of terms: those with µ 1 = ν 1 (mult. v) and those with µ 1 ̸ = ν 1 (mult. v(v -1)). In the following, to simplify the notation, we omit the spatial indices i and j.EQUATIONEQUATION)Variance of the joint probability1 v µ1 p (1) i1,j1 (µ, ν|µ 1 ) 2 - 1 v µ1 p (1)i1,j1 (µ, ν|µ 1 )EQUATIOND.1.3 Three-point termEQUATIONi,j (µ, ν|µ 1 )pi (µ|λ 1 )p(1)EQUATIONi,j (µ, ν|µ 1 )pi,j (µ, ν ′ |λ 1 )pi,j (µ ′ , ν|κ 1 ) = 1 (vm) 3 µ1,ψ1;λ1,ψ2,;κ1,ψ3 µ ′ ,νEQUATIONThe sum over µ ′ , ν ′ can be split in 4 terms: one with µ ′ = µ and ν ′ = ν (mult. 1), one with µ ′ = µ and ν ′ ̸ = ν (mult. (v -1)), one with µ ′ ̸ = µ and ν ′ = ν (mult. (v -1)) and one with µ ′ ̸ = µ and ν ′ ̸ = ν (mult. (v -1) 2 ). Fixing the right-hand sides, the value of the joint probability of the rules depends only on the rule indices ψ1 = (µ 1 , ψ 1 ), ψ2 = (λ 1 , ψ 2 ) and ψ3 = (κ 1 , ψ 3 ).The sum over µ 1 , λ 1 , κ 1 can be split in 5 terms: one with µ 1 = λ 1 = κ 1 (mult. v), one withµ 1 = λ 1 ̸ = κ 1 (mult. v(v -1)), one with µ 1 = κ 1 ̸ = λ 1 (mult. v(v -1)), one with µ 1 ̸ = λ 1 = κ 1 (mult. v(v -1)), one with µ 1 ̸ = λ 1 ̸ = κ 1 (mult. v(v -1)(v -2)). In the following, to simplify the notation, we omit the spatial indices i and j.EQUATIONEQUATIONEQUATIONby symmetry for exchanging µ ′ and ν ′ .EQUATIONEQUATIONEQUATIONEQUATIONby symmetry for exchanging µ ′ and ν ′ .EQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONby symmetry for exchanging κ 1 and λ 1 .EQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATION)By adding together all the terms,C (1) (µ, ν) 2 = 1 v µ1 p (1)i1,j1 (µ, ν|µ 1 )EQUATIONi1,j1 (µ, ν|µ 1 )pi1 (µ|λ 1 )p(1)EQUATIONEQUATION)Therefore,EQUATION) D.2.1 i 1 ̸ = j 1 case.This is the easiest case because the production rule probabilities p(1) i relative to different positions i are independent and identically distributed (with respect to realisations of the RHM). Therefore, using Eq. 34,EQUATIONi1 (µ|µ 1 )p(1)i1 (µ|λ 1 )p(1)j1 (ν|ν 1 ) 2 = p (1)i1 (µ|µ 1 )p(1)EQUATIONi1 (µ|µ 1 )p(1)i1 (µ|λ 1 )p (1)j1 (ν|ν 1 )p(1)EQUATION)By bringing these factors outside of the λ 1 and κ 1 sums in the right-hand side of Eq. 79,EQUATION)where, in the last line, we used Eq. 73, Eq. 74 and Eq. 75 to express the covariances of the C (1) (µ, ν)'s in terms of C (1) (µ, ν) 2 . After simple algebraic steps, recalling the definition of σ 2 p in Eq. 29,C (2) (µ, ν) 2 = v 2 C (1) (µ 1 , ν 1 ) 2 v -1 v v s v s -1 1 vm 2 v≫1 ---→ C (1) (µ 1 , ν 1 ) 2 m 2 . (82) D.2.2 i 1 = j 1 case.In this case, we need to evaluate some four-point functions. Since the spatial index of the p's is the same, we will drop it to ease the notation. For the same reason, we will drop the level index too. First, it is convenient to use Eq. 73, Eq. 74 and Eq. 75 to rearrange the right-hand side of Eq. 79 as follows,EQUATION)The value of C (1) (µ 1 , ν 1 ) 2 is actually independent of µ 1 and ν 1 , thusEQUATION)The first term to deal with is (2-2),EQUATIONψ1,ψ2,ψ3,ψ4EQUATIONψ1,ψ2,ψ3,ψ4EQUATIONp(µ|µ 1 )p(µ|λ 1 )p(ν|νEQUATION)p(µ|λ 1 )p(ν|ν 1 )p(ν|κEQUATIONψ1,ψ2,ψ3,ψ4EQUATIONWe will further separate the case where µ = ν (i) from the case µ ̸ = ν (ii).EQUATIONψ1,ψ2̸ =ψ1,ψ3̸ =(ψ1,ψ2),ψ4=ψ1EQUATIONψ1,ψ2̸ =ψ1,ψ3̸ =(ψ1,ψ2),ψ4̸ =(ψ1,ψ2,ψ3)EQUATIONψ1,ψ2,ψ3,ψ4EQUATIONψ1,ψ2=ψ1,ψ3,ψ4=ψ3EQUATIONψ1,ψ2=ψ1,ψ3̸ =ψ1,ψ4̸ =(ψ3,ψ1)EQUATIONψ1,ψ2̸ =ψ1,ψ3̸ =(ψ1,ψ2),ψ4̸ =(ψ1,ψ2,ψ3)EQUATIONψ1,ψ2̸ =ψ1,ψ3,ψ4EQUATIONψ1,ψ2̸ =ψ1,ψ3̸ =(ψ1,ψ2),ψ4EQUATION) 2-1-1, ii-b) (µ ̸ = ν, ν 1 ̸ = µ 1 , κ 1 = µ 1 )p(µ|µ 1 ) 2 p(ν|ν 1 )p(ν|κ 1 ) = 1 m 4 ψ1,ψ2,ψ3,ψ4EQUATIONEQUATION1-1-2, overall contribution equal to that of 2-1-1.1-1-1-1, i-a) (µ = ν, µ 1 = ν 1 , λ 1 = κ 1 , (v -1) of the (v -1) 2 choices of λ 1 , κ 1 )⟨p(µ|µ 1 )p(µ|λ 1 )p(ν|ν 1 )p(ν|κ 1 )⟩ = 1 m 4 ψ1,ψ2,ψ3,ψ4EQUATIONfrom the value of 2-2, case i-b).1-1-1-1, i-b) (µ = ν, µ 1 = ν 1 , λ 1 ̸ = κ 1 , (v -1)(v -2) of the (v -1) 2 choices of λ 1 , κ 1 )⟨p(µ|µ 1 )p(µ|λ 1 )p(ν|ν 1 )p(ν|κEQUATIONψ1,ψ2,ψ3,ψ4P µ 1 ψ1 --→ µ; λ 1 ψ2 --→ µ; ν 1 ψ3 --→ µ; λ 1 ψ4 --→ µ = 1 m 4 m 3 v v s-1 -1 v s -1 v s-1 -2 v s -2 + m 3 (m -1) v v s-1 -1 v s -1 v s-1 -2 v s -2 v s-1 - v s - (101)from the value of 2-1-1, case i-c).EQUATIONfrom the value of 2-2, case i-b)1-1-1-1, i-e) (µ = ν, µ 1 ̸ = ν 1 , λ 1 = ν 1 , κ 1 ̸ = (µ 1 , ν 1 ), v -2 of the (v -1) 2 choices of λ 1 , κ 1 )⟨p(µ|µ 1 )p(µ|λ 1 )p(ν|ν 1 )p(ν|κ1 )⟩ = 1 m 4 ψ1,ψ2,ψ3,ψ4 P µ 1 ψ1 --→ µ; ν 1 ψ2 --→ µ; ν 1 ψ3 --→ µ; κ 1 ψ4 --→ µ = 1 m 4 m 3 v v s-1 -1 v s -1 v s-1 -2 v s -2 + m 3 (m -1) v v s-1 -1 v s -1 v s-1 -2 v s -2 v s-1 - v s - (103) from the value of 2-1-1, case i-c). 1-1-1-1, i-f) (µ = ν, µ 1 ̸ = ν 1 , λ 1 ̸ = (µ 1 , ν 1 ), κ 1 = µ 1 , v -2 of the (v -1) 2 choices of λ 1 , κ 1 ) ⟨p(µ|µ 1 )p(µ|λ 1 )p(ν|ν 1 )p(ν|κ 1 )⟩ = 1 m 4 ψ1,ψ2,ψ3,ψ4 P µ 1 ψ1 --→ µ; λ 1 ψ2 --→ µ; ν 1 ψ3 --→ µ; µ 1 ψ4 --→ µ = 1 m 4 m 3 v v s-1 -1 v s -1 v s-1 -2 v s -2 + m 3 (m -1) v v s-1 -1 v s -1 v s-1 -2 v s -2 v s-1 -3 v s -3 (104)from the value of 2-1-1, case i-c).EQUATIONψ1,ψ2,ψ3,ψ4EQUATION)1-1-1-1, ii-a) (µ ̸ = ν, µ 1 = ν 1 , λ 1 = κ 1 , (v -1) of the (v -1) 2 choices of λ 1 , κ 1 )⟨p(µ|µ 1 )p(µ|λ 1 )p(ν|ν 1 )p(ν|κEQUATION) 1-1-1-1, ii-b) (µ ̸ = ν, µ 1 = ν 1 , λ 1 ̸ = κ 1 , (v -1)(v -2) of the (v -1) 2 choices of λ 1 , κ 1 )⟨p(µ|µ 1 )p(µ|λ 1 )p(ν|ν 1 )p(ν|κ 1 )⟩ = 1 m 4 ψ1,ψ2,ψ3,ψ4EQUATIONfrom the value of 1-1-1-1, case ii-b).1-1-1-1, ii-d) (µ ̸ = ν, µ 1 ̸ = ν 1 , λ 1 = ν 1 , κ 1 = µ 1 , 1 of the (v -1) 2 choices of λ 1 , κ 1 )⟨p(µ|µ 1 )p(µ|λ 1 )p(ν|ν 1 )p(ν|κ 1 )⟩ = 1 m 4 ψ1,ψ2,ψ3,ψ4EQUATIONfrom the value of 1-1-1-1, case ii-a).1-1-1-1, ii-e) (µ ̸ = ν, µ 1 ̸ = ν 1 , λ 1 = ν 1 , κ 1 ̸ = (µ 1 , ν 1 ), v -2 of the (v -1) 2 choices of λ 1 , κ 1 )⟨p(µ|µ 1 )p(µ|λ 1 )p(ν|ν 1 )p(ν|κ 1 )⟩ = 1 m 4 ψ1,ψ2,ψ3,ψ4EQUATIONfrom the value of 1-1-1-1, case ii-b).1-1-1-1, ii-f) (µ ̸ = ν, µ 1 ̸ = ν 1 , λ 1 ̸ = (µ 1 , ν 1 ), κ 1 = µ 1 , v -2 of the (v -1) 2 choices of λ 1 , κ 1 )⟨p(µ|µ 1 )p(µ|λ 1 )p(ν|ν 1 )p(ν|κEQUATIONψ1,ψ2,ψ3,ψ4EQUATIONfrom the value of 1-1-1-1, case ii-b).1-1-1-1, ii-g) (µ ̸ = ν, µ 1 ̸ = ν 1 , λ 1 ̸ = (µ 1 , ν 1 ), κ 1 = (µ 1 , ν 1 , λ 1 ), (v -2)(v -3) of the (v -1) 2 choices of λ 1 , κ 1 )⟨p(µ|µ 1 )p(µ|λ 1 )p(ν|ν 1 )p(ν|κ 1 )⟩ = 1 m 4 ψ1,ψ2,ψ3,ψ4EQUATIONTotal. Consider the factor multiplying (C (1) ) 2 in the right-hand side of Eq. 84,F(µ, ν) := µ1,ν1   p(µ|µ 1 ) 2 p(ν|ν 1 ) 2 - 1 v -1 κ1̸ =ν1p(µ|µ 1 ) 2 p(ν|ν 1 )p(ν|κ 1 )- 1 v -1 λ1̸ =µ1 p(µ|µ 1 )p(µ|λ 1 )p(ν|ν 1 ) 2 + 1 (v -1) 2 λ1̸ =µ1,κ1̸ =ν1⟨p(µ|µ 1 )p(µ|λ 1 )p(ν|ν 1 )p(ν|κ 1 )⟩   .(113)By organising the terms in the sum according to the classification of the previous paragraphs,F(µ, ν) = v F (2-2) a (µ, ν) + (v -1)F (2-2) b (µ, ν) - 2v(v -1) v -1 F (2-1-1) a + F (2-1-1) b + (v -2)F (2-1-1) c + v(v -1) (v -1) 2 F (1-1-1-1) a + (v -2)F (1-1-1-1) b (114) +(v -2)F (1-1-1-1) c + F (1-1-1-1) d + (v -2)F (1-1-1-1) e + (v -2)F (1-1-1-1) f + (v -2)(v -3)F (1-1-1-1)g .For ν = µ, by summing all the case i) terms, we getEQUATION)Summing, instead, all the case ii) terms, we get, for ν ̸ = µ,EQUATION)To sum up, as in the i 1 ̸ = j 1 case (Eq. 82), for large vocabulary size v ≫ 1 and large m (e.g. m = f v s-1 , with f ∈ (0, 1]),EQUATION) D.3 Level-l LCABy replacing C (1) with C ( ℓ -1) and C (2) with C (ℓ) , the recurrence relation Eq. 79 extends to the case where the LCA of the i-th and j-th tokens is a level-ℓ symbol. Asymptotically in m and v, and independently of µ and ν,EQUATIONIn this appendix, we prove that the sampling noise on empirical correlation functions of RHM data has a characteristic size (v 2 P ) -1/2 .Let us denote, to ease notation, P {X d-t = µ, X d = ν} with p(µ, ν), P {X d-t = µ} with p(µ) and P {X d-t = µ} with p(ν). When measuring probabilities from the frequency of observations over P i.i.d. samples,EQUATIONwhere . denotes the empirical estimate and the indicator variable δ is 1 with probability p(µ, ν) and 0 otherwise. With δ having finite mean and variance, by the central limit theorem, p(µ, ν)EQUATIONwhere ξ is a Gaussian random variable with zero mean and unitary variance. Analogously,EQUATIONwhere ζ 1 and ζ 2 are also Gaussian random variables with zero mean and unitary variance, correlated with each other and with ξ.As a result, the empirical estimation of C t (µ, ν) reads Ĉt (µ, ν)EQUATIONIn the limit of large v and m, where p(µ, ν) converges to 1/v 2 plus vanishingly small fluctuations and p(µ), p(ν) converge to 1/v plus vanishingly small fluctuations, the dominant noise contribution is the one of ξ, with standard deviationEQUATIONThe correlation function C(t) is the standard deviation of C t (µ, ν) over vocabulary entries. Hence, the sampling noise on C t (µ, ν) results in an additive factor of (v 2 P ) -1/2 .In this section, we generalise the results of App. D and App. E to the correlations between the last token and a s-tuple of observable tokens.Let us then replace µ and i with the s-tuple of input features µ and the multi-index i. This change only affects the level-1 rules probability p (1) in Eq. 17 and Eq. 38. Therefore, we can write the tuple-token correlation with LCA at level ℓ as follows,EQUATIONi1 (µ|µ 1 )p(1)EQUATIONwhere the second line is obtained by recalling that, for each available s-tuple of input features µ, there is a unique level-1 variable µ 1 (µ) that can generate it, with probability 1/m. The mean of C (ℓ) (µ, ν) vanishes together with that of C (ℓ-1) (µ 1 (µ), ν 1 ). Te variance readsEQUATIONj1 (ν|ν 1 )p(1)EQUATIONwhere we used Eq. 74. Using Eq. 29 and Eq. 34,EQUATIONwhich equals the token-token correlation divided by a factor of m.Correspondingly, Cℓ is reduced by a factor of √ m. Crucially, since the average joint tuple-token probability p(µ, ν) is 1/(v 2 m), the sampling noise size, obtained via the calculations of App. E, is also reduced by a factor of √ m, leaving the condition of Eq. 9 unaltered.In this section, we present empirical learning curves of Deep CNNs trained for last-token prediction (details in subsection A.1). In particular, we discuss discrepancies between these curves and those of Transformers (Fig. 2 ) in subsection G.1, verify the scaling with m of the first two steps of Eq. 12 in subsection G.2, then discuss the role of the context window size t in subsection G.3. The learning curves of deep CNNs are qualitatively similar to those of transformers, but also present apparent quantitative differences, as shown in Fig. 6 . Specifically, a noticeable difference is the sample complexity of the third step P 3 . This difference is possibly due to favourable implicit biases of CNNs, such as weight sharing. Indeed after learning the penultimate level-1 features in the second step, weight sharing would facilitate learning the other level-1 features along the entire data. As a result, the model can directly access the correlations between the last token and tuples of level-1 symbols. According to the discussion of App. F, these correlations are stronger than those with tuples of level-0 symbols by a factor of √ m. Correspondingly, the sample complexity of the third step P 3 is reduced by a factor m with respect to Eq. 12. In general, we can assume that, in the presence of weight sharing, after the ℓ-th step all level-(ℓ -1) features have been learnt, so that the (ℓ + 1)-th step requires resolving correlations between the last token and tuples of level-(ℓ -1) features. The corresponding sample complexity scales like m ℓ+1 instead of m 2ℓ-1 . However, the steps with ℓ ≥ 3 occur for large values of the training set size, and we cannot investigate this issue systematically with our current numerical experiments.G.2 Scaling with the number of production rules m Fig. 7 and Fig. 8 show a scaling analysis of the behaviour of P 1 and P 2 from Eq. 12 in Deep CNNs. The collapse achieved when rescaling the number of data P by P ℓ and the test loss by the value before the jump L ℓ-1 confirms this prediction. 6 , left, on the first step. The zoom highlights the dependence of the sample complexity on the context size t. The collapse of the curves on the right panel, achieved after dividing P by (t + 1), reveals that P1 ∝ (t + 1). This dependence is analogous to the sample complexity of regression of a target function depending on a low-dimensional linear projection of a large-dimensional input [55] .Similarly, Fig. 9 shows a scaling analysis (for CNNs) of the behaviour of P 1 with the number of s-tuples in the input, proportional to (t + 1) with t the size of the context window. The figure highlights a linear behaviour P 1 ∝ (t + 1) that our analysis does not capture. Nevertheless, this behaviour is expected from the theory of regression with one-hidden-layer neural networks [55] : when the target function depends on a small number of variables among d, the sample complexity is generically proportional to d. Proving this result by considering a single or a few steps of gradient descent, as often done in this literature, is an interesting work for the future.NeurIPS Paper ChecklistJustification: There is no violation of the code of ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).throughout the paper, Latin indices indicate the token position and Greek indices the vocabulary entry.Let us remark that, while the exponent depends on the corpus and the choice of tokenisation, power-law decays are observed empirically also for syllables[40], words[41] and part-of-speech tags[42].Section 1d of Appendix B. 


Decision: This paper studies the relationship between training dataset size in language model settings and the token x token correlations learned by the model. All the reviewers agree that this is an interesting topic with solid theoretical analysis and thorough supporting experiments. The addition of results on WikiText during rebuttal makes the results more convincing.

Reviews: review: paper_summary: paper_summary: 1) This paper looks at the relationship between training dataset size in language model settings and the token x token correlations learned by the model. 

2) The authors first use a synthetic setting to study this relationship and derive the results followed by testing it on a real dataset of lines from a Shakespeare’s play to demonstrate that the relationship discovered holds in real settings. 

3) The  synthetic setting uses a probabilistic context free grammar model to generate the training data at different sizes, more specifically a random heirarchy model (RHM from https://arxiv.org/pdf/2307.02129) is used as it gives fine grained control over the correlations between generated tokens. Tokens far away in the heirarchy tree are less correlated. 

4) The key contributions from this paper are : 

a) Authors observe that both in RHM and in real settings the size of the training dataset size (P) caps the token correlations that can be learned by the model i.e correlations between tokens beyond a distance (t* - effective context window) in the heirarchy tree cannot be learned by the model. As training dataset size increases this cap is lifted enabling the model to learn these correlations well. 

b) "Key finding is that the test loss decay levels off at a characteristic training set size that depends on the length of the context window and can be measured from correlations." (copied verbatim from paper contributions as it's a clear statement for other reviewers to look at )

c) A general framework based on synthetic data generation model (RHM) to further study the relationships between training dataset size, effective context window etc
strength_weakness: strength_weakness: 1) The experiments on real-world datasets are limited and I'd encourage the authors to try this out on at least one other dataset of larger size and with a larger model. 

2) Since the synthetic data generation process is cheaper, authors could have used higher P (training dataset size) in experiments.
questions: questions: 1) Have the authors tried replicating the results from Shakespeare experiment on a larger dataset ? 

2) Have the authors tried varying model size in addition to dataset size to see if it recovers chinchilla curves under fixed compute ?
limitations: limitations: 1) This work has no negative societal impact
2) Authors have done a good job at discussing limitations of their approach that comes due to their use of fixed geometry of data tree.
paper_summary: paper_summary: This work studies the relation between the amount of training data required to learn the structure of language via the next token prediction objective & neural nets (CNNs, Transformers). The underlying training data is systematically varied using PCFGs and the authors find that that the size of the training dataset limits the resolution of token-token correlations to an effective context window (proportionally) and that a larger training set allows the representation of deeper hidden hidden variables. The authors also find that the sample complexities of learning the deeper representations is polynomial wrt effective context window. Besides synthetic data, the authors test their conjecture on a collection of Shakespeare's line and find the findings consistent with the conjecture.
strength_weakness: strength_weakness: 1. The main weakness of the paper is the lack of comprehensive empirical experiments on "natural" text datasets -- the authors test their conjecture on Shakespeare's lines, but I find this limited experiment quite ad-hoc -- why not test it with more natural datasets across domains.
2. The authors didn't characterize their findings in the light of emergent properties or scaling laws of real large language models -- as such the importance of the findings is only weakly characterized in the paper.
questions: questions: 1. Why is the conjecture only tested on the shakespeare dataset? How about testing it on news corpora or other domains?
2. What does the conjecture predict as to the max context length for training real LLMs on natural text data? Can such predictions we tested empirically on LLMs?
limitations: limitations: Limitations were adequately addressed.
paper_summary: paper_summary: This paper investigates the sample complexity of learning languages generated by a kind of PCFG. The paper uses a model called the Random Hierarchy Model (RHM; a PCFG with a fixed tree structure) and identifies a relationship between the size of the training set and the "effective context window" that can be learned, which comes from the fact that more data is needed to resolve correlations between tokens that are farther away. The theoretical predictions are supported by experiments on synthetic data (generated by an RHM) and real data (lines from Shakespeare).
strength_weakness: strength_weakness: - I think biggest weaknesses are the assumptions of the RHM (a fixed tree geometry, all sequences of the same length). The fact that the correlation resolutions decay with distance is a consequence of the RHM, and it is not obvious how well these assumptions will hold for more naturalistic language data. However, I think this kind of limitation is necessary for getting analytical results, and the authors provide some empirical results on natural language and discuss how the assumptions can be relaxed in the future.
- I would have been interested to see some experiments on a language dataset other than the Shakespeare dataset. In particular, there might be other datasets that are more likely to exhibit long-distance dependencies (for example, predicting the next character in computer code), which could help to understand when the RHM might not be a good model for natural language data. However, I acknowledge that these experiments might be out of scope for this submission.
questions: questions: No additional questions.
limitations: limitations: I think the authors adequately addressed the limitations of their work.
paper_summary: paper_summary: This paper proposes a conceptual characterization of how much data is required to learn the latent hierarchical structure of input languages. The theory is based on token correlations, which themselves are qualified based on token distances; these correlations are further traced back to the hierarchical structure that explains the distribution of sets of tokens. It is argued that language models can leverage these correlations to compose more complex hierarchical representations of the relationship between these sets of tokens.

A series of empirical analyses are performed to verify predictions from the theory. These include analyses from artificial PCFGs/RHMs, and verifications on natural language using Shakespeare plays. Key findings include that (1) more data is helpful because it allows LMs to resolve longer-distance dependencies and correlations; (2) that these correlations allow the LM to compose deeper representations of the relationship between sets of tokens.
strength_weakness: strength_weakness: 1. The linguistic foundations seem shaky. For example: the poverty of the stimulus is mischaracterized in L19-20 (see Questions field under “Suggestions” for more detail), and PCFGs are used as models of the structure of languages, when in fact language is context-*sensitive*, rather than context-*free* [1]. Nonetheless, I think the experiments do still give a thorough characterization of how hierarchical phenomena in general will be learned in models with self-supervision objectives.
2. Relatedly, the proposed RHM has many non-language-like features: the production rules are required to be unambiguous, whereas natural language is full of ambiguity that humans leverage intentionally to convey particular points; additionally, sampling production rules uniformly is suspect, considering that natural language leverages certain structures far more than others. This feels more like an issue with framing rather than methods, as I think this is still a valid analysis of how hierarchical structure is learned by models in general—just not necessarily how naturalistic text is learned. The Shakespeare text is meant to overcome this limitation, but this brings me to my next point:
3. Shakespearean English (early modern English) is very different in structure, word choice, and typological features than Modern English. It is also written in a poetic style that does not accurately capture the distribution of linguistic phenomena that would appear in more naturalistic domains or casual registers in any language. Why use this data, rather than something more naturalistic and contemporary like subsamples of The Pile or FineWeb?
4. The analyses seem very similar to past empirical work on how language models learn to compose atomic token units into hierarchical structures—most notably, the work in [2] on LSTMs. This work should be cited.
5. Unclear whether this will have practical impact on LM research or interpretability methods. I do not find this a significant flaw, but it may limit the impact and reach of this work. This is the main reason I have set my contribution score to 3.

All of these points are reasons why I have set my presentation score to 2 and soundness score to 3.

See Questions for references.
questions: questions: Questions:
1. What was the motivation behind using Shakespearean text, rather than more naturalistic text? If you believe that the conjecture will also extend to any natural language dataset, would it be possible to run this analysis on something like The Pile?
2. What is the empirical impact of this work? This isn’t meant as a detraction of this work, as I believe analyses like these are valuable for our understanding. I’m more curious as to whether the authors believe there are specific impacts that this could have on how we train, interpret, or adapt LMs.

Suggestions/Typos:
* L19-20: The poverty of the stimulus is more in reference to the *ambiguity* of language’s underlying structure. It is not saying that the data is insufficient for hierarchical structure to be learned, but rather that the data can be explained by many differing hypotheses—including linear or “flat” explanations of the structure of the data. Nonetheless, children always settle on the exact same explanation: hierarchical structure, whereas language models in the past have been shown to be predisposed to linear explanations [3].
* “CGF” and “PCGF” are often used (when “CFG” or “PCFG” are meant). For example: L67-74, L97, L98
* L87: “wthe” -> “the”
* It could be good to cite 

References:
[1] Shieber (1985). Evidence against the context-freeness of natural language. https://www.eecs.harvard.edu/shieber/Biblio/Papers/shieber85.pdf
[2] Saphra & Lopez (2020). LSTMs compose (and learn) bottom-up. https://aclanthology.org/2020.findings-emnlp.252/
[3] McCoy et al. (2023). Does syntax need to grow on trees? Sources of hierarchical inductive bias in sequence-to-sequence networks. https://aclanthology.org/2020.tacl-1.9/
limitations: limitations: The authors describe the practical limitations of their methods w.r.t. how neural models learn, but I believe the authors should also more thoroughly discuss the discrepancies between the data in their experimental setting and how natural language is actually structured, and whether/how these might affect findings.

Comments: title: Experiments on WikiText
Please respond to authors' rebuttals
comment: Thank you for the response and for the new results with WikiText. I still think the paper should be accepted and I will leave my score as is.
Thanks for the response. I think the addition of the more naturalistic text data helps. It also sounds like much of the terminology surrounding the structure of natural language will be changed (W1-3).

I think that the takeaway that scaling is helpful will not be surprising to readers (W5). Optimizing the size of the context window can be helpful, as shown in some prior work, but it still does not seem like it will change how we think about or train LMs.

That said, I think there is value in this contribution. I am therefore keeping my current positive score.
Dear Reviewers,

we have completed the analysis of the Wikitext dataset and we confirm that the results are similar to those obtained for the Shakespeare dataset (as displayed in Figure 4 of the original manuscript). We will include this analysis in the revised manuscript.

We would be happy to share the relevant figure here if allowed.

Best regards,
The authors
Dear Reviewers,

Thanks for writing your reviewers of the paper. Now the authors' rebuttals are in. Please go through them and see if they have addressed your questions. Please start discussions with the authors if you have further comments. 

Regards,
AC