Towards a theory of how the structure of language is acquired by deep neural networks
Authors: Francesco Cagnetta
Matthieu Wyart
Venue: NeurIPS 2024 poster (2024)
Keywords: Hierarchical Models
Language Models
Learning Theory
Representation Learning
Self-Supervised Learning
Statistical Physics of Learning
Primary area: learning_theory
TL;DR: Increasing the dataset size helps language models capture the latent hierarchical structure of data by leveraging token correlations.

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.

Towards a theory of how the structure of language is acquired by deep neural networks
Francesco Cagnetta
Matthieu Wyart Institute of Physics
Institute of Physics
École Polytechnique Fédérale de Lausanne francesco caw.eoo.ccagtttepf......hc
École Polytechnique Fédérale de Lausanne matthieu. wyart@epfl.co ch
Abstract
How much data is required to learn the structure of a language via next-token pre- diction? We study this question for synthetic datasets generated via Probabilistic Context-Free Grammar (PCFG) a tree-like generative model that captures many of the hierarchical structures found in 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 's hidden variables, the longer the range the deeper the variable. addition, a finite training set limits the resolution of correlations to 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 rep- resentation 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. In particular, our conjecture predicts how the scaling law for the test loss behaviour with training size depends the length of the context window, which we confirm empirically in Shakespeare's 's plays and Wikipedia articles.
Introduction
Two central foei of linguisties are the language structure and how humans acquire it. Formal language theory, for instance, describes languages with hierarchical generative models of grammar, classified different levels of complexity [ 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 [ (5) posits that the statistics of the input data be used to deduce the language structure. This assumption is supported by empirical evidence concerning a broad range of tasks, including word segmentation 66) and reconstruction of the hicrarchical phrase structure [7].
Large Language Models (LLMMs) offer an interesting perspective on the subject. For instance, the success of LLMs trained for next-token prediction [8 9 establishes that language can be acquired from examples
albeit with a training set much larger than what humans are exposed to. Fur- thermore, 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 []O [2] Recent studies have begun revealing the inner workings of LLMs by using synthetic data generated via context- -fee grammars [3] [4, determining, in particular, the algorithm that these models follow when predicting the next token. However, there is no consensus the mechanisms behind language acquisition by LLMs [55] [6]. 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 [8 19 remain unexplained. In this work, we use hierarchical generative models data to describe how the structure of language is learnt the training set grows.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

1.1 Our contributions
consider synthetic datasets generated via the Random Hierarchy Model (RHM) 20], an ensemble of probabillistic 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 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 previous works classification, 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 sequence sample complexities where the emergence of a deeper data structure representation leads to 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 's lines and Wikipedia articles. In particular, we find that the test loss decay levels off at characteristic training set size that depends on the length of the context window and can be measured from token-token correlations.
1.2 Additional related works
Fixed-tree hierarchical generative models have been introduced study phylogeny [21] then used in
supervised learning [2 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 features- label 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 power of their distance [27] When the production rule probabilities are random 28] 22), these probabilities must follow a broad distribution for the data to retain information about the generative process. Learning PCFG from examples
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 's structure [3]4 [4]. 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 foundation for forming longer-range dependencies [34] Our work introduces 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.
2 Notation and setup
This work focuses on the pretraining phase of language models, aimed at building approximation of the data distribution via unlabelled examples []. Let us define a text datum, or sentence, as sequence = (I1....,Za) of d tokens belonging to finite vocabulary V. Denoting with the

---

vocabulary size, each token 2; is represented as a v-dimensional one-ho hot vector (zi. ( -=1.....
1, if x; = 4-th element of V/ Zi, (0, otherwise.
(I)
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 joint probability over d-dimensional sequences with elements in V. Px (a)) == IP {X1 = æ.. X = _d}- The specifics of the approximation of Px depend the training objective. In Masked Language Modelling, for instance, random fraction of tokens is masked, i.e. replaced with a fixed token T'makk and the model tasked with predicting their value (8). Autoregressive language models, instead, are trained predict the i-th token of sequence based on all the previous ones [2]. Here we consider a simplified setup where the last token of the sequence is masked and the model is trained to predict In other words, the model
A dataset, corpus, consists of a probability distribution
takes the context window (I1,.... .T, - as input and outputs parametric approximation of the conditional probability of the last token,
Po (1. Id-1) R P (X2= = za(X1 Z1. Xa-1 = xa-1};
(2)
obtained by updating the parameters 0 via gradient descent on the empirical cross- entsopy
((XP)
Σ
log (po(2a) xd-1)),
(3)
>EXp
where Xp is a set of P training examples drawn from Px. Numerical experiments are performed in PyTorch (36). with the code available at https: /tte:///iitie www com/fracagnettall mandom-hierarce moodell Details of the machine learning models, training hyperparameters and computer resources are presented in Anp.
2.1 Hierarchical generative models
To model the hierarchical structure of sentences, consider synthetic datasets generated via probabilistic context-free grammar (PCFG) (37). PCFGs are collections of symbols and rules that prescribe how generate sequences. particular, the PCFGs we consider consist of
L finite vocabularies of hidden (nonterminal) symbols (Vz)e=1,... I....i.
A finite vocabulary of observable (terminal) symbols V= Vo;
L sets of production rules describing how one symbols V generates tuple symbols of Vi-1. for e t= L.....L.
Production rules take the form
(a) + M1 (E-1)
(L-1) (6-1) for (0) E Ve, Mi E Ve-1,
(4)
for some integer size 81 The left panel of Fig. 1 shows an example of the generative process, represented as tree: pick (uniformly at random) 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 sequence (V,)d, with d Πe Se. 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 Px 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 f-th set of production rules chosen uniformly at random between all the unambiguous sets of rules in the form of Eq. 4 Unambiguity means that each st-tuple of level-(f - symbols can be generated by one level-é symbol at most. The uniform probability and unambiguity assumptions are not satisfied in 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 Ve have the same size and that the size of the production rules is homogeneous, i.e. st = s for all f. We further assume that each nonterminal appears as the left-hand side of exactly m production rules, i.e. the hidden symbols have equivalent low-level representations. Since there are v² distinct low-level representations and each the v high-level symbols is assigned m. unambiguity requires m S =11
'thoouhhout the paper, Latin indices indicate the token position and Greek indices the vocabulary entry.
3

---

correlation Cy(()
10
P 1024
10-4
16384
122
262144
(134504
T0) F1
(D)
P
A3
P4
AS
AG
toleen
Figure I: Left: Example of data generation according the RHM, with depth L= 3 and branching factor each level-ć symbol is replaced with pair of lower-level symbols, down the leaves with f 0. Right: Empirical (coloured) and analytical (black dashed) correlation functions of RHM data, with = 8 =, e =332 and m = 8. The stepwise decay mirrors the tree structure of the generative model. Empirical estimates obtained from /' examples initially follow the true correlation function, but then saturate due the sampling noise (coloured dashed). As result, finite training set only allows measuring correlations corresponds to the highest value where the empirical estimate matches the true correlation (c.g. for the orange and green curves, 3 for the red curve).
== 2. Starting from the root with é 3 and following the
tokens up a certain distance (P()). Graphically, z" (PP)
3 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. 2
(H, = P = = - -
=v)
(5)
where i and y are arbitrary elements of the vocabulary and IP refers to the data distribution Px Since the masked token is always the last in setup, it convenient a function of the distance t = - d between the i-th and the masked token. Taking the root mean square the vocabulary yields the correlation function,
d and write Ci,a as
1/2
(tt) = U Σ (Cs-sa((,,Ni)²
(6)
M.NEV
which measures the typical dependency between tokens as a function their distance For RHM data with = = Px is uniform over all the possible sequences of tokens in V and there are no correlations. If, instead, m <; 2-11, the correlations strength depends on the distance. Fig. shows an example for RHM data with I. = 4, 8 = 2, 32 and m = 8.
Correlations decay with distance. The stepwise decay of Ö(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 of 1 left). The second highest is with the tokens generated by the same level-2 symbol (orange box the higure), and until the root. Formally, with & 1, I,..., L denoting the height of the lowest common ancestor (LCA) of the d-th and (d f)-th tokens.
Ō(t) Ō(0) V t= t=
(()) > (32) >... .... O(L)
(7)
These plateau values can be determined analytically in the large v limit by approximating the variance over the vocabulary entries y and the right-hand side of Eq. 7 with the variance over realisations of RHM. Denoting the average over such realisations with (.).
C (((c1)(4)))
1/2
m/v-11) 1
(8)
26-11
"C',, (H, is also equivalent to the covariance matrix of the one-hot representation. E [(Xi,, (Nr,,) (Xj.v [Xx,)))

---

test cross-eutzopy
tost cross-eurzopy
10"
10%
10
10
10
training set
training set
Figure 2: Left: Learning of depth-3 transformers trained RHM data with L L= = 8 (blue) 11 (orange, both averaged the network), displaying stepwise behaviour analogous to correlation function. The vertical dashed lines mark the characteristic training set sizes Px at which the correlation with tokens at distances up to t s emerge from the sampling noise. Horizontal dashed lines represent (upper bounds on) the cross-entropy of the probability of the last token conditioned model learning a progressively larger sub-tree of the data structure. Right: Learning curves transformers for m = 8 and different sizes the context window. The saturation of the loss decay due to the finite context window highlights that the decay is entirely due to the ability to leverage larger portion of the context window.
and independent realisations of the dataset and initialisations
the previous s suggesting that the steps correspond the
where the rightmost equality exact asymptotically and m. Eq. 8 is derived detail App. D confirmed empirically in the right panel of Fig. Iaand can be given 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 sf with the m dependence on l is log m/ log
approximated by power-law decay C()) / م with
Saturation due to finite training set. When measuring the correlation function from a finite sample Xp of P data, there is additional contribution due to the sampling noise. The scenario is illustrated in Fig. right: the empirical estimates Cr((), shown coloured lines for different values of P, begin by following the descent of the true correlation function C(t), shown as black dashed line. However, empirical estimates saturate when approaching the sampling noise size (v² P)2/2) as proved in App. Eland shown as dashed coloured lines in In.Fig. I| right. Combining the saturation with the values of the steps, we deduce that finite training set allows for the resolution correlations up to distance t" =s -1 such that
)05) (0²P) +1(++1)
(9)
Eq. suggests that language model trained with P examples can only extract information from tokens within distance 1" (PP) from the last, In other words, a finite training set equivalent to an effective context window of size t" (P). ~ t then t*) p1/23 Alternatively, setting 1/2 yields a sequence of thresholds P: for the resolution of correlations of increasing range. From Eq. Pt x 2mm281, which has simple interpretation as the number of choices generative process to determine two tokens at distance t E [ 1, sf): choices for the level-f LCA, generations.
((0)) = 2 P) 1/2
m for the first production rule and m (m per branch) for each of the remaining
Self-supervised learning of the Random Hierarchy Model
We now show how the correlations can be translated into prediction of sample complexities that allow for 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.
4.1 Prediction of the sequence of performance steps and sample complexities
Loss steps. Due to the structure of the data, there is a natural sequence of increasingly accurate approximations of the last token probability in Eq. 2 For all & 1,..., ....,,i these approximations
5

---

realised by conditioning the probability of the last token on the previous s ---11 1. These approximations amount using an effective context window of size i, = s 1. The effective context windows consist of the leaves of the subtree generated by the level-f hidden symbol above the last token, as illustrated by the coloured boxes Fig. left. The resulting cross-entropy loss is given by
Le Ex Px |- log P {Xa|Xa aa +111 -d- Xa-1 - xa-13
= Ex Px [log N (Za-
xd-1)],
(10)
1 denotes the number of possible values of the masked token depending on the effective context window. For t O, there is restriction the masked token value and this number equals v v-the vocabulary size. For 8 =1, we can determine the average Ni = E ( Id] as follows. For each s-tuple (3dd-++1.-- -...-.....>>................. ;.a) there is at least one value of the mask compatible with the other 8 - symbols, i.e. Itd itself. In addition, each of the remaining 1-1 values (4a # Fg has a probability f of being compatible with the context, coinciding with the probability that the s-tuple (Id-a+1>.... Pd)) is compatible with the production rules, This probability is given by (mw 1), i.e. the number of s-tuples compatible with the production rules except (Id (Ed-s+1.--. Ta), over (v" - 1), i.e. the total number of s-tuples except (#d-s+1)..) Tt). Therefore, N1 11=1+(0 (v- (o- 1)f = 1 (v 1) () 1). For l > 1, the average number Ne of symbols compatible with the context can be determined iteratively. The level-E symbol generating the whole s² -uple can take any of the values, but the level- (6- 1) symbol below is now restricted to N1 values. By the previous argument, N₂- = 1 + (v 1),,,,
where
1)/(v* - 1). Due to the concavity of the logarithm, we can bound the test loss Fq. 10 with L. = log Nv, i.e., after solving the recurrence relation and introducing the fraction of compatible s-tuples f = m//e-11
20
(V" - (v) 1)
(m(e 1)
L = log
1
1 m(r 1)
1 m(v -1 1)
U
u.mb1 log
1 1- + u
(11)
Naive strategy. The simplest strategy to estimate PP [Xa =Ia-s441.... X zd-13 is to count the empirical occurences of the s 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 subse- quences occurs with probability given by that of the corresponding LCA symbol (the root of the sub- tree encased by the corresponding coloured box in FFg. I left), times the probability of the production rules that generate the subsequence from the LCA,, m-1 x m== The latter is exponentially small in the effective context length le = sf - 1, hence the required sample size is exponentially large in fgg
m- -1) mn -s' -m---_1)((e-1)
Efficient strategy leveraging the hidden variables. Using the hidden variables results in a much lower sample complexity. Indeed, due 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. I] left, the probability of the last token independent of the pair (Hg) (6
(1) (0) (0)) if the parent level-1 variable μiz 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 result, the minimal set of variables that the s' s'-gram probability depends on consist of s observable tokens (those in the same patch as the last token) and (s () 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 -f. The resulting sample complexity grows exponentially with é, or as a power of the effective context length te.
Reconstruction of the hidden variables. We now argue that, as shown 20 in the context of clas- sification, the hidden variables can be represented via the correlations between tokens. Consider, for instance, the pair (44) 16 (0) in Fig. 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 (i) 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 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|gq. with ( f= implying P P2 = vmz.. By iterating this argument we get sequence of sample complexities Pr that allow for resolving correlations between the masked token and s-tuples up to distance = s 1,
Pe (1- um" 2f-1 um (1
(12)
ya-1
(0)) and (13 : P4 For instance, in the case illustrated in Fig. left, the correlations of the pairs (14 M22
(1) with the masked token can be used to reconstruct the pair of hidden symbols (A] M2 ). The hidden symbols have a higher correlation with the masked token than their children. Hence, as in the case of classification [20]. 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. 11] for (44) , 122) in the figure), which, in turn, enables the reconstruction of P {Xa(Xx=se41 = Td-a+1s--- Xd-1 = xa-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 Lg.
Scaling law of the RHM. After solving Eq. 12 for l as a function of P. we can use Eq. 11 derive the scaling law for the behaviour of the loss steps as function of the training set size P. Neglecting all the factors that do not depend on L, Eq. 12 implies Ri log (2 log m). Thus, from Eq. 11
EPP) + log (1 - f) x log + v01 - A)
lng llg
2 m
(13)
Notice that f << 1, thus log f < 0. Therefore, Eq. 11 implies an early logarithmic decay as long as log /ol P < 2 log m log (v(1- n)). For larger P. the expansion log 21+ = recovers the ubiquitous power-law decay p-a [7)) with exponent a = log //(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.
4.2 Comparison with empirical learning curves
Fig. 2, left, compares the learning curves of deep transformers (details of the architectures in sub- section A.2) with the sample complexities Pe of Lg. 12 (vertical dashed lines in the figure) and the test loss upper bounds La of Eq. 11 (horizontal dashed lines), showing good qualitative agreement. Additional experiments that support the quantitative scaling of the sample complexities P1 and Pa with m shown in App. G Fig. 2| right, shows the learning curves of models trained on reduced context window. In this setting, our description correctly predicts the saturation of the loss due to the finite context window size t: with f= sf - 1, the model can only learn the level-E hidden variable above the masked token, thus follow only the first E of the I. steps of Fg.. 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 subsectiion 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
4.3 Emergence of hierarchical representations of the data structure
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 datum's 's tree structure, thus becoming insensitive to the entire subtree emanating from this hidden variable. For the sake of interpretabilityy we consider deep convolutional networks (CNNs) with architecture matched the data structure, represented schematically in the graphs on the right of Fig. 3 (further details in subsection I. To probe representations we introduce two sets of transformations. Given a datum and the associated tree (Fig. 1 left), consider the i-th level-f symbol μ.") St,, replaces it with another one randomly chosen from the vocabulary, whereas R2,, resets the choice of the production rule emanating from (0) Both transformations alter the subtree originating from y4 (e.g. the subtree within the orange box of Fig. 2 left for t= 2 and i == 2), affecting sf observable tokens. However, Re, 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 Re,, but not to St,
7

---

1.0
81
1-th mp
0.5
2-th
mp
th
outpot
10P
10a
10
10a
109
training set size P
1.0
V2 M2
0.5
8-th
0.0
102
10a
10a
10a
108
training size P
1.0
0.5
4-th rep
output
0.0
10a
training set size P
Figure 3: Relative sensitivity re/sz st of the representation of trained depth CNNs (sketched the right panels) for input transformations (the affected tokens indicated the black horizontal segments the right panels) corresponding resetting production rule emanating from given level-f variable 1, for top. centre and bottom), as a function of training set size P. Colours represent the layer of the representation, as indicated in the key and by the squares the right panels. The CNNs are trained on RHM data with L = 4, 2, e 16. Vertical dashed lines mark the sample complexities I's ofE 12 The drop of the curves from relevant level-E symbol when > Pr.
around Pr signals that trained representations only encode
We define hidden representations he(z) (hidden nodes the network's graphs in Fig. 3 as the sequence of pre-activations in 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 spatial index I,..., sh-é (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.
(14) where the symbol denotes the scalar product over the channels. In order leave the masked token unaltered, we always apply the transformations to the penultimate hidden symbol of the level, i.c. i i= --- 1. Hence, from now on, omit the spatial index i. The left column of Fig. reports the ratio Te/se for the hidden representations of a deep CNN trained on RHM data. Each row refers to the level 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 re/st from Ro to ~ 0 signals that a representation depends on the corresponding level-E hidden variable, but not on the other variables in the associated subtree. These drops occur at the same training set sizes Pt as the
(h))(h) = ExpPx ( (Re, (h, = Ee- [he be (SS,(())))))
Notice that only the representations with L > can become invariant, which is due to the fact the production nules linearly separable. Let focus the first level: the corresponding s-dimensional patch of the input can take mu distinct values m equivalent to the following set of constraints: for each level-2 2 features μ4, and æ;,; encoding for one the m level-1 representations generated by w æ1, C,. Since is an arbitrary constant, there are x (m 1) constraints for the components of w. which cannot be satisfied in general unless S (s 1).
of the v level-2 features. Invariance
linear transformation

---

10
tast cros-entrops
3 10P
corrllation Cp(()
1024
p-a,
P 2096
10-1
16884
100
a
85536
69,8 1.4
token distance
6x 10P
P 1024
Cpt) x p1/2
16384
10"
05538
CXP
xx 10P
262144
x 10P
10a
10'
10'
10-2
10
10"
P/t"
scaled distance t/ p1/x
Figure 4: Top, Left: Test losses of 3-layers transformers trained on (t++ f)-characters blocks of the tiny- Shakespeare dataset [8 (t in the key). The saturation of the loss to some t-dependent value indicates that performance improves with because the model can use information from a larger context window. Top, Right: Empirical estimates (t)(t) for different training sizes P in the key. The curves initially follow the true correlation (t) (black dashed), but then saturate due to the sampling noise (coloured dashed). Bottom, Right: The empirical curves (t) collapse when rescaling correlations by the sampling noise size p-1/2 and by the characteristic distance t" (P) ~ pl/s, with 2.8. Bottom, Left: 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 increases, trained models learn deeper representation of the tree structure of the data.
5 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 predict the next token from training set of P examples can only extruct relevant information from an effective context window of P-dependent size (*)))
We test this conjecture in two datasets: selection of lines from Shakespeare's plays [3 and collection of articles from English Wikipedia [39]. For both datasets we adopt character-level tokenisation, resulting in over 10th tokens. We then extract sequences of consecutive tokens and train BERT-like deep transformers in the setup ofssection 2 further details of architecture and training are in subsection A.3] The results of our test are reported Fig. for Shakespeare and Fig. of AAp.. B for Wikipedia. First, with a large context window, the test loss follows the empirical scaling law L ~ p-a (top left panel). However, the learning curve levels off at some characteristic scale P that grows with the size I of the context window. This phenomenon can be explained via the correlation
function, which decays as power of the distance C(t) ~ 1ー0 with 3 = 1.4 4 (top right panel).
Empirical estimates Öp(t) saturate when reaching the sampling noise scale ~ -P p-1/2; following the analysis of |ssectiion 3 this behaviour results in an effective context window size t* (P), given by the
'Let us remark that, while the exponent depends on the corpus and the choice of tokenisation, pawer-law decays observed empirically also for syllables (40] words 4] and part-of-speech tags 42

---

value of t where the correlation function C(t) ~ - intersects the sampling noise scale ~ p-1/2
(t') 8 ~ p-1/2 (P) ~ p1/= with =
(15)
As result, the empirical correlation functions with varying P collapse when rescaling O by the sampling noise and the distance by t0 (P) (bottom right panel).
By inverting (P) we get a characteristic training set size (t) where the training set allows for resolving correlations at all distances t' <t, (t) ts. Paired with the empirical power-law scaling with P. this result leads to the following context-dependent scaling hypothesis for the test loss:
P
C(P. t) =t f
(16)
with (x) ~ x= for x < 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. quantitatively confirms Eq. 16 and our previous conjecture.
Conclusions
We proposed a conceptual framework for understanding the performance-vs. scaling laws of language models trained for next-token prediction. In our picture, increasing the number of data allows for the resolution of 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 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
45| and the steady improvement of overall performance [7]. 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 [6 47 48 49
50
Furthermore, our analysis predicts a fundamental relationship between the effective context window captured by language model trained with finite training set and the decay of token-token corre- lations, 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 hand, our framework can be extended 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.
LLMs trained on larger datasets. On the other
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 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 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. 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.
Acknowledgments and Disclosure of Funding
We thank Kai Nakaishi for pointing references [52 27 to us; and Allan Raventós for feedback on an earlier version of the manuscript. We also thank Antonio Sclocchi, Alessandro Favero and Umberto Tomasini for helpful discussions and feedback on the manuscript. This work was supported by a grant from the Simons Foundation (# 454953 Matthieu Wyart).
10

---

References
[1] Noam Chomsky. Aspects of the Theory of Syntax. The MIT Press, 50 edition, 1965.
[2] Gerhard Jäger and James Rogers. Formal language theory: refining the chomsky hierarchy. Philosophical Transactions of the Royal Society B: Biological Sciences, (67(()88)))1966661
2012.
[3] Robert C Berwick, Paul Pietroski, Beracah Yankama, and Noam Chomsky. Poverty of the stimulus revisited. Cognitive science, 35(7):120-11222, 2011.
[4] Nick C Ellis. Frequency effects in language processing: A review with implications for theories of implicit and explicit language acquisition. Studies in second language acquisition. 24(2):143-188 2002.
[5] Jenny R Saffran and Natasha Z Kirkham. Infant statistical learning. Annual review of psychology. 69:181-200 2018.
[6] Jenny R Saffran, Richard N Aslin, and Elissa L Newport. Statistical learning by 8-month-old infants. Science, 274(5294): 1926--199, 1996.
[7] Jenny R Saffran. The use of predictive dependencies in language learning. Journal of Memory and Language, 44(4))493-515, 2001.
[8] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In North American Chapter of the Association for Computational Linguistics, 2019.
[9] Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language understanding with unsupervised learning. Technical report, OpenAI, 2018.
[10] M. Peters, M. Neumann, L. Zettlmmyyr, and W. Yih. Dissecting contextual word embed- dings: Architecture and representation. In Ellen Riloff, David Chiang, Julia Hockenmaier, and Jun ichi Tsujii, editors, Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 1499-15000 Brussels, Belgium, 2018. Association for Computational L. Linguistics.
[11] I. Tenney, D. Das, and E. Pavlick. BERT rediscovers the classical NLP pipeline. In Anna Korhonen, David Traum, and Lluís Mårquez, editors, Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 4593-4601, Florence, Italy, 2019. Association for Computational Linguistics.
[12] C. D Manning, K. Clark, J. Hewitt, U. Khandelwal. and O. Levy. Emergent linguistic structure in artificial neural networks trained by self-supervision. Proceedings of the National Academy of Sciences, 117(48)
2020.
[13] Zeyuan Allen-Zhu and Yuanzhi Li. Physics of language models: Part 1, context-free grammar. arXiv preprint arXiv:2305. 2023.
[14] Haoyu Zhao, Abhishek Panigrahi. Rong Ge. and Sanjeev Arora. Do transformers parse while predicting the masked word? arXiv preprint arXiv:2303.08// 17, 2023.
[15] Sanjeev Arora and Anirudh Goyal. A theory for emergence of complex skills in language models. arXiv preprint arXiv:2307. (tt.::33.7.193366. 15936, 2023.
[16] Michael R Douglas. Large language models. arXiv preprint arXiv:2307.05782 2023.
[17] Kaplan, S. McCandlish, Henighan, T. B. Brown, B. Chess, R. Child, S. Gray, A. Rad- ford, J. Wu, and D. Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.08361..22 2020.
[18] Deep Ganguli, Danny Hernandez, Liane Lovitt, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Nova Dassarma, Dawn Drain, Nelson Elhage, et al. Predictability and surprise in large generative models. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Tronsparency, pages 1747-1764, 2022.
[19] Rylan Schaeffer, Brando Miranda, and Sanmi Koyejo. Are emergent abilities of large language models mirage? Advances in Neural Information Processing Systems, 36, 2024.
[20] Francesco Cagnetta, Leonardo Petrini, Umberto M. Tomasini, Alessandro Favero, and Matthieu Wyart. How deep neural networks learn compositional data: The random hierarchy model. Phys. Rev. X, 14:031001, Jul 2024.
11

---

[21] E. Mossel. Deep learning and hierarchal generative models. arXiv preprint arXiv: 2016.
[22] Eran Malach and Shai Shalev-Shwartz. A provably correct algorithm for deep learning that actually works. Preprint at http://arzivorr/aab//18......3. 2018.
[23] E. Malach and S. Shalev-Shwarzz. The implications of local correlation on learning some deep functions. In Advances in Neural Information Processing Systems, volume 33, pages 1322-13322 2020.
[24] Umberto Tomasini and Matthieu Wyart. How deep networks learn sparse and hierarchical data: the sparse random hierarchy model. arXiv preprint arXiv:2404. 10727, 2024.
[25] Antonio Sclocchi, Alessandro Favero, and Matthieu Wyart. A phase transition in diffusion models reveals the hierarchical nature of data, arXiv preprint arXiv:2402. 16991, 2024.
[26] Song Mei. U-nets as belief propagation: Efficient classification, denoising, and diffusion in generative hierarchical models. arXiv preprint arXiv:2404. 2024.
[27] Henry W. Lin and Max Tegmark. Critical behavior in physics and probabilistic formal languages. Entropy, 19(7), 2017.
[28) E. DeGiuli. Random language model. Phys. Rev. Lett., 122:128301 Mar 2019.
[29] Eric De Giuli. Emergence of order in random languages. Journal of Physics A: Mathematical and Theoretical, 50450),, nov 2019.
[30] J.J. Horning. A Study of Grammatical Inference. CS 139 Memo AL. Stanford University, 1969.
[31] Alexander Clark and Nathanaël Fijalkow. Consistent unsupervised estimators for anchored PCFGs. Transactions of the Association for Computational Linguistics, 8:409-422, 2020.
[32] R. Thomas McCoy, Robert Frank, and Tal Linzen. Does syntax need to grow on trees? sources of hierarchical inductive bias in
networks. Transactions of the Association for Computational Linguistics, 8: 140, 2020.
[33] Kabir Ahuja, Vidhisha Balachandran, Madhur Panwar, Tianxing He, Noah A Smith, Navin Goyal, and Yulia Tsvetkov. Learning syntax without planting trees: Understanding when and why transformers generalize hierarchically, arXiv preprint arXiv:2404.16367 2024.
[34] Naomi Saphra and Adam Lopez. LSTMs compose-and Lear-- Bottnn-uu In Trevor Cohn, Yulan He, and Yang Liu, editors, Findings of the Association for Computational Linguisties: EMNLP 2020, pages 2797-2809, Online, November 2020. Association for Computational Linguistics.
[35] Riccardo Rende, Federica Gerace, Alessandro Laio, and Sebastian Goldt. A distributional simplicity bias in the learning dynamics of transformers. arXiv:2410. 19637, 2024.
[36] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An Imperative Style, High-PPeformance Deep Learning Library. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[37] Grzegorz Rozenberg and Arto Salomaa. Handbook of Formal Languages. Springer, 1997.
[38] The unreasonable effectiveness of recurrent neural networks, 2015.
[39] Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. In International Conference on Learning Representations, 2017.
[40] Tim Sainburg, Brad Theilman, Marvin Thielk, and Timothy Q Gentner. Parallels in the sequential organization of birdsong and human speech. Nature communications, 10(1):3636, 2019.
[41] Nikolay Mikhaylovskiy and Ilya Churilov. Autocorrelations decay in texts and applicability limits of language models. arXiv preprint arXiv:2305.0661 06675, 2023.
[42] Kai Nakaishi, Yoshihiko Nishikawa, and Koji Hukushima. Critical phase transition large language model. arXiv preprint arXiv:2406.0m 24X::22006.03335,, 2024.
12

---

[43] Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud. Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, al. Emergent abilities of large language models. arXiv preprint arXiv:2206.07666 2022.
[44] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
[45] Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, al. Beyond the imitation game: Quantifying and extrapolating the capabilities language models. arXiv preprint arXiv: 04615, 2022.
[46] Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares
algorithm. Foundations of Computational Mathematics, 7:331-368 2007.
[47] Stefano Spigler, Mario Geiger, and Matthieu Wyart. Asymptotic learning curves of kernel methods: empirical data versus teacher-student paradigm. Journal of Statistical Mechanics: Theory and Experiment, 2020(12), 2020.
[48] Yasaman Bahri, Ethan Dyer, Jared Kaplan, Jaehoon Lee, and Utkarsh Sharma. Explaining neural scaling laws. arXiv preprint arXiv:2102.06700 2021.
[49] Francesco Cagnetta, Alessandro Favero, and Matthieu Wyart. What can be learnt with wide convolutional neural networks? In International Conference Machine Learning, pages 3347-3379. PMLR, 2023.
[50] Blake Bordelon, Alexander Atanasov, and Cengiz Pehlevan. dynamical model of neural scaling laws. arXiv:2402.01092, 2024.
[51] S.M. Shieber. Evidence against the context-freeness of natural language. Linguist. Philos., 8:333-343, 1985.
[52] Alexander Clark. Pac-learning unambiguous nts languages. In Yasubumi Sakakibara, Satoshi
Kobayashi, Kengo Sato, Tetsuro Nishino, and Etsuji Tomita, editors, Grammatical Inference: Algorithmss and Applications, pages 59-71. Springer Berlin Heidelberg, 2006.
[53] Greg Yang and Edward J Hu. Feature learning in infinite-width neural networks. arXiv preprint arXiv:2011.14522 2020.
[54] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[55] Yatin Dandi, Emanuele Troiani, Luca Arnaboldi, Luca Pesce, Lenka Zdeborová, and Florent Krzakala. The benefits of reusing batches for gradient descent in two-layer networks: Breaking the curse of information and leap exponents. arXiv preprint arXiv:2402.0322. 2024.
13

---

A Details of the experiments
Our experiments on RHM data consider both Deep CNNs tailored the RHM structure and simple transformers made by stacking standard Multi-Head Attention layers. Our experiments on the Shy--ssaeeperre and WikiText-106 datasets consider deep, encoder-only transformers, where Multi- Head Attention layers are interspersed with residual connections, layer normalization and two-layer perceptrons, All our experiments were performed on a cluster of NVIDIA V100 PCIe 32 GB GPUs (2x7TFLOPS), Single experiments require up to 20 GPU hours for the largest models (~v 10 x 10%) with the largest training set sizes ( 4 x 109), with an estimated total (including hyperparameter tuning) of 6, 000 GPU hours. We provide architecture and training details below.
A.1 Deep CNNs (RHM)
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 8. Since each layer reduces the spatial dimensionality by factor 8, the input size d must be an integer power of s and the CNNs depth equals log d/ log
We use the Rectified Linear Unit (ReLU) (z)) = max (0,z) 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 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 do limit. In practice, H is set to 256 for Fig. 3 512 for Fig. 6 left and FFg.. 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-entrope loss reaching a threshold value of 10-3, We use validation set of size 215 to select the model with the best validation loss over the training trajectory.
A.2 Multi-layer self-attention (RHM)
The deep Transformers that we train 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 data generated from the RHM. Each layer has the same number of heads ng, and embedding dimension demb n% v, with 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 nu follows two principles: the model should be large enough for the training loss reach a threshold value of 10 10-3 and changing n2 should not affect performance beyond the fluctuations due the model initialisations. Specifically, we set na = 16 and notice no significant change in performance up to nA = 64. Also scaling demb up to 4n x v does not impact performance.
Multi-layer self-attention networks are trained with the Adam optimizer, with a warmup scheduler bringing the learning rate to 10-2 within the first 10 training epochs. As for CNNs, the batch size is set to the lowest value allowing for convergence.
A.3 Encoder-only Transformer (tiny-Shakespeare and WikiText-103)
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 above.
we set the number of heads to nı, 8, the embedding dimension to d, = 256 the size of the MLP hidden layer to 4d,, and the number of layers to 3. For WikiText- 103, we set n4 = 8, d, = 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.
For
14

---

test cros-enttopp
x 10"
correlation Cp(()
P=512
P=2068
x 10
Pro
P H192
0.095
t-, ,,= 1.50
131072
10
token distance
6x
P 2048
Cpt0 x p1/2
82768
CX
x 100
52428
x 100
10a
10'
10
10"
10
10P
P/t
scaled distance t/ p1/x
Figure 5: Top, Left: Test losses of 6-layers transformers trained on (f 1)-chrracters blocks of the Wexi 103 [9) the key). As in in/Fig. 4 the loss saturates
t-dependent value after reaching characteristic training set size. Top, Right: Empirical correlation functions Cp(t) with P as in the key, showing saturation for large due to the sampling noise (coloured dashed). Bottom, Right: Collapse of the empirical curves Cp(() is achieved when rescaling correlations by sampling noise size p-1/2 and by characteristic distance (P) p1/=, with 2/3 3.1. Bottom, Left: As predicted by conjecture, the losses collapse when rescaled according to Hq. 16 with the
the correlation functions and 0.095.
B Loss saturation and correlations for WikiText-103
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. and, as Fig. confirms our conjecture.
C Statistics of the RHM data
For each token i 0, over the single production rules,
O,..,, .., 1, single-token probabilities can be written as products probabilities
PP (xx =
Σ M
Pi Pi (plpa))
...)))...P....... ........ (2) (fL-IlM))1 (1+ (HLL)
(17)
where
(i) the indices i,,..., it are such that iz... equals the s-ary representation of i, with is = 0,..., 1, and 0's added to ensure that the representation always consists of L. indices. other words, the multi-index i.,..,, uniquely identifies the path linking the root of the tree to the i-th leaf.
(ii) Pie (μeーllu)) lue) denotes the probability choosing, among the available production rules starting from μ4g, that has the symbol μ4-1 the iz-th position of the right-hand size.
(iii) (L) (Pz) denotes the probability of selecting the symbol μ4 the root (1/v for model).
These decompositions arise naturally due to the connection between probabilistic context-free grammars and Markov processes. For the joint probability of two tokens and j distance t Ij - i).
15

---

with s' <t<'< - such that the lowest common ancestor (LCA) is level- hidden symbol, and 26+1 denoting the position of the LCA within its level,
- P(
E
( Pie.se (we- Me 1 (6+2)
(we).
(18)
simplify when replacing i with whole s-tuple of observable symbols 4== (M1+(j-1)) Mjs) for some j 1,.., s _L- The simplification arises because the level-1 rule probability p()) (11)) (p]]m1) ). is uniform and equal 1 1/m if the production rule l41 - 14j exists, 0 otherwise. Then, the sum over μn selects the only level-1 symbol that generates the tuple μAj. As result, one is left with probability represented by a smaller tree, where the leaves representing P4 are pruned, and an additional factor of 1/m.
Both in Eq. 17 and Eq. 38
C.1 Statistics of production rules
For each set of production rules, we call !V (Me-1: the number of occurrences of the level-E - 1 feature ( in the i-th position of the right-hand side for all the production rules emanating from the level-E feature μlg. In our generative model, there are m production rules emanating from a given symbol. The rule follow when generating datum chosen uniformly at random among these m. Hence,
p! (He-1lme)
m N N/ (me-1;
1
(19)
For the sake of clarity, let us omit the level index in the following paragraph. The probability of Na(p; v) over different realisations of the set of production rules is that of the number of successes when drawing times (number of s-tuples associated with the high-level feature v) without replace- ment from a pool of e (total number of s-tuples with vocabulary size v) objects where only g-11 (number of s-tuples displaying feature μ position i) leads success:
(0-1)) (
m -
P [No(uo: p1) k|RRM
Hg Hgm,ut-1,pm San (k),
(20)
m
where Kgn. denotes Hypergeometriic distribution with population size N, K success states, and draws. The mean and variance with respect realisations of the RHM (denoted with (.) to avoid confusion with data averages TE [.) are
(N)
m
8=-1
m
Oo = ((N - (NN-) = m
2
t m
m. v
1 0 m
21
21
2
21 1
2 (21)
For e >> 1, the variance converges to m/v u (m -1²11 with s fixed, thus v m - v²)
Equations (19) to (21) easily generalise to the case where ni represents group of s' S 8 low-level features (instead of single low-level feature). With Mo denoting s' s'tuuple of features and i the
s'-tuple of associated spatial indices,
(0/² (0*T0) 1:
("r ---0'
U*'
IP [Na(poo m1) k} *JRHM*
(22)
m k
m
resulting in
(N₂) = m
oN, = ((N2 (N2))) = m 6
m v
8 m
m
(23)
2
2
1
C.2 Statistics via splitting
An alternative way to obtain all statistics is by writing the level-& probabilities sums over the production rules,
m m Σ
Pi (pe-
(6)
((e)) ((
(24)
16

---

where ry.s (11 denotes the i-th element of the right-hand side of the tó-th production rule emanating
from μt. Eq. 24 generalises immediately the case where and P are s' s'tuup with s' S Using
())r = =P
-
1
(25)
RHM
D=
2b where fi - ja denotes the event that the i-th element of the right-hand side of the wh-th production rule emanating from μai coincides with we can compute all one-point averages. In addition, for (v1, v.j.v) * (H1, u.),
v)) P Pfu1 Vit u
Hul v P P(ui
vid 11 (ml
(26)
RHM
RHHM"
where
P Puu u
0u
= = ii ij
RHM
0,if = j, v1 11, 2. #
0-
Hg Hg 1 1,0 1,0-1 [1(
if = j.v P1. ,,00
11
1
P
{vv 1ep v
RHM
Hg ug v0 (1)
if j, v1 Mh, + 10
0z
Hg
1,00 (1)
if j. 11,
2-1
Hg 1-0-1 (1)
.f -ii -
j. #1.
y -1
(27)
Notice that, once the right-hand side of the rules (p and v) are fixed, the conditional probability can only attain two distinct values: one for μ4 = 1n and xb = Φ and one for the other cases. Then, is convenient to define 'rule index' & that comprises both the starting high-level feature and the
chosen production rule. This index runs (1...., mv). With these formulas, one can get all the
joint statistics of the rules. For instance (omitting the RHH. subscript on IP to ease notation),
(pe(rolur)pe (Pol (z))
1
Σ
111
M1
$2..2
140
m vi,12==1
H1 Wir,, p40
P
m
V1=122
P ffu Weid uo } IP ui Dnit, Holes Dnid, uo
1
m
m m(m
1) y
(28)
m
21
hence
1
1 11
4 m
of ===((a) ((p((oo))))) (p)) (pi(Holur) - (p))) = (p((HHl())))(((o)))))
(29)
equivalent to dividing o3y from Eq. 21 2y m Analogously, with * no.
(p2(HH)lur)p(()ol))))
1
Σ
P M1 shin
Moi
v2.5 vo
m²
F(m
P.
Weid uo } Po {mr Sians volun Stud, no
m(m - 1) 1-8-1
(30)
m²
1
17

---

thus
2
eº m
cp - ((p((ool)z) - (w)) (pi(volu)) - (p))) = ((((ollls))(/oolll)) -
mo D 1
(31)
Notice that c, - - in agreement with the constraint Eno (1(oo(a)) Indeed, for any finite sequence identically distributed random variables Xμ. with a constraint on sum, 2p X C for some constant C,
X = Xx
Exx, - (Xp)) = 0
==1
#=1
(X2 - (Xx)) E [xp - -(xx)) = 0 +
1=1
Σ ((x, - (X,)) - (xxi)) +
a=1
((pp- (X,))) + 11 (xx (x,))) 0.
(32)
where, in the last line, we used the identically distributed variables hypothesis to replace the sum over j with the factor (v 1).
In addition, with v1 + H1,
Moi staie uo)
(p: un (p:
P
m
1/1 1/2 =1
PP for Virt po mn
Shid mo}
p
M1
ua
1/2
772 2
(33)
m
11
thus
1 v
((i((olu)) - (p)) (p:(Halez) - (p))) = (p
1 (34)
22
0
and
(o(polur)p:(uol/
P
Mi 1ii1 Mms us shzi vo
m
1/ 10/2
10 no
fur Wery voles Siit mon
m
1/0
m²
2
21
(35)
m
17
thus
1
1 02
((i(uolm)) - (p) (ps(volu1)- (p))
(36)
D Analytic computation of spatial correlations
Given a dataset of d-dimensional sequences of tokens in V, we measure correlations via the token co-occurrences matrix,
Oe = P =,,
(X; = ,) P(}
(37)
where μ and v are arbitrary elements of the vocabulary V/ and Px refers to the probability of the data distribution (distinct from PRIM. indicating the probability of the rules of the generative process).
Joint and single-token probabilities are given by Fq. 17 and [q.. 38 respectively. We now prove E.q. of the main text.
18

---

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 level-1 hidden symbol, i.c. the two tokens lie in the same s-patch,
P -(x
Σ
Piin (1. plmn)r (m)); (61 #1);
(2)
=[x,=)x* Σ
Pa (1lp1 1p (11).
P(X,= =
Σ P1=1
U P (vlp)) (j2 = (1)=
(38)
We consider the limit of large m, where the univariate probabilities of the hidden variables of any level converge 1/u, with relative fluctuations of order 1/v m 20 In this limit, we can substitute the probability of the LCA with 1/v, thus obtaining.
(w,
= Σ Poin (1, w(m))
Σ AL.M
P (HlP))) (vlv1). (v(r))
(39)
222
As we will prove in this and the following sections, the correlations have average but nonvanishing variance. Including the fluctuations of the LCA probability results in corrections to the variance that vanish the limit of large m. Furthermore, notice that we removed the dependence of C(u,, v) on the positional indices 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.
Since i * j1, Pi (plp)) and (2) ( are independent. Hence, by Eq. 21 and Eq. 23 with s' = 2,
(c))
(N2)
(N) (N)
O.
(40)
m
m
m
M1
PI.
The variance/2nd moment reads
Σ ((00)))))))( -
Phiss (1, v11a)) )
))= + ((-2)
Pe (eller))
(1)
Ph (v1p1)
2 2
Σ
(p (ppp))))) (el (11d))p)
(41)
M1.A1.81
We will compute the three contributions on the right-hand side separately in the following subsections.
D.1.1
One-point term (marginal probability)
Po(m) ((1I
2 Ph (ulmr))
Σ
Ph
( (ulpm)p (1) (wle))
(42)
We can split the sum into two kinds of terms: those with μ4 (mult. v) and those with fn # v (mult. v(v - 1)). In the following, to simplify the notation, omit the spatial index
Section ld of Appendix B.
19

---

11 M4 = V1 (mult. u)
Po(u)(
(Ó(re, (11), (1)))((rs (11), (4)))
mm²)²
v1.V2
IP H1
11 pili
(mx)²
V1.42
Σ P
{ 11l
m 14
Σ
p Pfrs " 14 PP mm شو " -
(mv)²
#1
1
1) ------1- - 1
(mv)²
m
v
+ m(m
17 1
(43)
(i1-~1 P1 # V1 (mult. v(v-1)) 1))
1)(),))(1)==
vlu - 1)
Σ
PP
plmm un m puvn وو, m
(mc)²
V1.12
u(u 1)
{ uul
Li, u f ش mlps 3 1g
(mc)²
V1.42
v(u 1)
x -
(mo)²
m1
u 1 1
(44)
Variance of the marginal probability
= Σ (mbbe))
(
) = =Pdlu, (1) 2
2
Pa
14
M4
1 U me
(45)
U m
8 1
D.1.2 Two-point term (joint probability)
Pinsi (n, v/(x)) )
Jeln,v) =
1
Σ A1.99
(46)
22
We can split the sum into two kinds of terms: those with μ41 en (mult. v) and those with in # V (mult. v(v- 1)). In the following, to simplify the notation, we omit the spatial indices i and j.
11) 11 = =1 (mult. v)
Te( (mw)2
Σ whi
(0(r,, (M1), (1,))))( (11), (H,,)))
P Nn
ti,, pu: ln 2/2 m
(m 2
Σ v1
the mel
Σ
PP
(MI 3 an PP yw L welmr Ui mm)
(m
1
1 1332 1
(m
m 02
+ mmm
- 1)
02
1 -
(47)
20

---

(ii-H1 # vi (mult. u(v 1))
D,(1,))()) v(U 1)
Σ P
(m "n wei is 3 mmm
(mr)²
12.122
v(u v(u-1) 1)
P {ir
"h me
p ppus Me, palme 3y mm
(mv)²
11,122
v(U - 1)
2 0a
(mv)²
m
122
1
(48)
Variance of the joint probability
)
1 2
Piicii (112))
1 Σ
Piis (ur Te((u,))
02
P1
muu
(49)
D.1.3 Three-point term
Ve(
1
Σ
(2) (uldz)p, (w))x)) (1) (vlea))
3
Σ
(us, v' Xo dp (n', plA1))
E
Σ P u1
Viidd ues A stanls uv's 1s Usils, v'v (50)
(em)
A AA al
The sum over y², v/ can be split in 4 terms: one with μ =²= μ and
(mult. 1), one with μí' - p and o' o (mult. 1}), one with μ¹ o p and ='= (mult. (u (o-1)) 1)) and one with μ' + f and v' 4 v (mult. (v 18-1) )). Fixing the right-hand sides, the value of the joint probability of the rules depends only on the rule indices 1 = (11, 1)1), 1/2 (A1, 1/2) and 8bs (N1, 1/3).
The sum over PI, AI, Ki can be split in 5 terms: one with μ = A = (mult. v). one with #i = Aι Æ (mult. v(c - 1)), one with k # Ar (mult. o(v - 1)), one with ii / A KI (mult. u(v u -
1)), one with (i / À A kn (mult, v(v - () 2)). In the following, simplify the notation, we omit the spatial indices and j.
(i-a) 11 = =1=1=131 11' = μ and v' = (mult. v)
To(H,
Σ
(8(Te, (M1), (4, (11), (1)) (M1), (H,
(mv)3
Va
(mt)3
P
M1
pMd pl
Uia
22 pv) uvv M1
V
Σ
P [1
(mt)3
vi=
3v
P PfMi H1
Vi, uai } P {us Vn
ullle m mm)
(m
U
IP { un P PaMs Eh (a
pelln mn
3h am } p ppf 11 Via pelpn Me uvz #1 21 pv)
+ (me))
3
Ah / VI. v2.t1
1
1 10-2-1
1 v--2 2 2
m 0z + 3m(m
1) 62 w 1 + +mmm 1)(m - 2) 22 w 1 w 2 (51)
(mr)3
21

---

(i-b)-11 11 = A1= = =kis/ μ²= = μ and v/ v (mult, v(v- 11)
To( 210 -1 1)
P M1
- puv MI 32x per pe 3 mm)
(mevs
v(v 1)
E
P Bfn "n m PP {ir "², ua 1042 تا mmm
(mo)s
0(0 - 1) (me)s
Σ
IP P/Ms th ae } p pap مn p مم ميك mu)
x P P1
ne p _ pel 31 pm)
v(v - 1)
mm(m- - 1) 1 1²-2
122 u - + m(m - 1)(m 2) 1 0a-2 1²-2 1
(mo)s
72 u=1 Us -2
(52)
(i-c)-11 =1== = 11 * 1
and v/ = (mult. v(v - 1))
(e(,,))(io) v(v 1)
Σ P Pfm fu " pmd Mn "3, un 33 p/u) Telk, ()-b)) (53)
(mv)3 3
11.122.19
by symmetry for exchanging yl and v'.
(i-d) 11 = = n² # μ and v/ * v (mult. v(v 1)3)
To(1,))(i-0) = v(u- - 1)²
p Plui "i pvi ui " ue' M - w'v}
(mo)3
D(U 1)2
Σ
Pfm Mn uw } p { m Wوك ww Jus بn mo)
(mo)3
P {m1 -h, p'vlus 3 uue' 111 - ww }
v(u - 1)2
(mo)3 m(m 1)(m - 2) 1 u=-2 x-
(54)
222 1re - 11a 2
(ii-a)+1 11 # \1 = k1i μ = u and 1/ = v (mult. w(v 1))
T6(H,))00 ()(ia)) = v(v-1) 1)
Σ PP hI 34 pv; _2 wv; A1 22 me)
(mu)²
v(u - 1)
Σ
PP
{m
Ui av } P { d1 شو pulun ووك }
(mv)3
u(v 1 1)
Σ
Pfm (mn "n me P f^1 ووا ualm -h me pftr Ve, ull 1/3 pa pn
2 mw)
(mv)3
=(U- 1)
1 1x-
1 ys-2 - 1 10-2-2 2) + m2² (m - -1) 02 v² - 1 15 - 2
m²
(55)
(m
2? 1. 1
(ii-b) 141 F X1 = K13 /L² = / and v/ f v (mult. v(u - 1)2)
2((1,))(100)
v(v 1)2
P PfMs u1 Di, pw; A1 ,2 pll A1 Mez 1m0
(mv)3 3
0(u - -1)2
Σ
F
B M1
w pm
po
pe{{ A1 1i pa |m Mi, uي } P Bf tv - pml وB wm: 11 -1 mo)
-mm))
11 /o
e(U 1)²
2 13-2 1
m² mm - 1) 02 2 11 1 w 2
(56)
(mo)3
22

---

(ii-c) H1 # \1 =kis μ¹ + and v/ = (mult. v(v - 1)3)
Te((, = v(v 1)²
Σ
P fmr "h ues 23, ues X1 2 1/1) = -alle, 1)6ib)))
(mw)}
(57)
by symmetry for exchanging y' and v'.
(ii-d) u1 + \1 =K13 1l + μs and v' o y (mult. v(v 1)3)
Telu, ())
v(r - 1)3
Σ
p
Pfu In تh ue; X1 ووك wu A1 Mna u'v}
(m
wh 1b2.
D(v - 1)3
-11-
P M1
-
pw
Po x2 13 11 وh f d
f2 X1 -3 p'vld1 2o we u1 - mm)
(mm)s
1/1 12.2 of
v(v 1)3
m2 mmmmm- 1) 1 w²- 2
(58)
(mo)3
u 1 2
(iil-a)-11=
M11 =1 F k13 μ¹ = and v'= v (mult. v(v - 1))
TelH, (ii-a))
v(v - -(v-1)
1)
Σ P plps u1 بh uuv: μl
3 pmd K2 ~ pm)
(mv)3
0/1.122.133
11)
Li uv } IP { Ks 3 wrlpn - mw)
P un
(mo)3
u(u- 1)
Σ
p pfp ur بi mmy { pr و 1a و aad IP (m) Mig palles 2 per un =h mm)
(muv)3
D(U- 11 1)
2
1 wa-2 2
-1
+ m2 (m - 1) 22 wo -2
1 u=-2 1 2-=2-2
= TT ()(iia)
(59)
(mw))
2
18 1
(iii-b) 111 = A1 f k:13 na = 1l and v' * v (mult. u(v - 1)2)
Toluu (ii-b)) v(u 1)2
P fu "i, uv: ui 3 ue/ ki "h mm
(mo)3
v(u ((V-1)²
Σ
P P111=
2/ me) P fpmm Nn - wl Mng mo po 15l L2a wllm L2, wl pm -h mc
(mm)3
14 Wi
8(U- 10v-13 1)2
x--2 10-2 -1 11
m² m²²mm- 1) 2² 2 2 2
(60)
(mo)3
-1=11 Tely, (16--)))
(1il-)-11111 =1
# kiss jel # l and = v (mult. v(v - 1{)))
v(r 1)2
Σ P {f Vi, wuv ur د puu, ks lee nuu
(mw)3
Via 1/
r(u- -1)2
Σ
P FII
s/e me } pp Defm
yuvll Wez
mmm وhك
(me)3
u(v - 1)2
Σ
PfN1 mi aw
} p { 11
k1 a um mh
2n ptvlps 22 pv: pn Mi mw)
(mw)3
/1.
D(U 1)²
2 1 2
1
1 -
+ m 2 (m
1)
(61)
(mv)3
1
02
1 - 1 8r -
2
23

---

(iii-d)-py = A1 # k13 p² # μ and v' + v (mult. v(v- 1)9)
1)(,,))(ii0)) = v(v - 1)a0
P puu _h wvi mn تيك wu Ki - w'u
(mv)3
o(v -1)8
IP Puu -h pa)) Po
1P(11 (11 - pal Dnك mul Po 1s -3, I² plu دh, we' mm 3 mw)
-mm))
8(U- 113
m² 1) 1 v²-2 10-2
// vo 1s 2
(62)
(mo)3
(iv-a)-111 = 111 # \13 Je = and V' =v= v (mult. u(U- - 1))
(i o(0-1) 1)
Σ
P pfp
Mr - ue; A1 - pv: kl -n uv } Tolks, 00i Tolle, v)
(mu)s
(63)
by symmetry for exchanging K1 and d1.
= k1 # \1i μ4 - μr and v' #'+ v (mult. v(v - 1)2)
Dolu (i0
v(r v - 1)2
Σ
p p(ui "h pa,; A Mi wl: ui vo ww)
(mw)3
v(v- 1)2
v(u -
Σ
P (m PLm
t/e mel TP {)r م we |m Mn, mel
(mv)3
+ u(u u(w-1) 100-11 112
Σ
P P(11 11 "i, m } P (11 M 1 21 we } PP fure 3 par/ 2 we' nn 3n mm)
(mu)3
D(u - 1)²
1 x--
1 w--2 ya - 1
m²
+ mmmmm (m- 1) 22 yx - 1 22x - 2 = Ic((u, 11) (60i-))
(64)
(mv)3
22
vo -1
1
(1=0)/1==1p # X13 μl # l and //= v (mult. r(r 1)2)
v(v- - 1)2
Te(H,
P(Mr M1 دh pw; A1 V2 pav μm
P
ووك p'v}
(mu)3
v(u 11)
Σ
P P'Ms M1 by ww po
p A1 1i u ووك pr pe (pr +
1' _h pm: #1 - mm)
(mo)s
V1 V2z vo
0(U 1)2
10-2 1 1.02
m(m - 1)2 v² v² - 1 0= 2
= -T((H, 2) (bi
(65)
(mv)3
(iv-))-1=KK 2I =K # X11 n¹ + μ and v' + (mult. viv - 1)33)
v(r 1)3
T((,,))(10-))
Σ P
plua
"i, pav: X1 Ve, uw/ ; un waz nlv
(mv)a
V1.V2.03
D(u - 1)3
Σ
F [1
+ mm pP{x A1 1i par | Mhi uw P B mm Vi p'vid1 S2
w m1 =n mw)
-mm))
B(U 1)3
2 2
(mo)3
m² mmmmm - 1) 02 2 - 12 - 2
= T
(66)
24

---

(v-a)-11 11 # 11 + Kii p 1= and v/ = (mult. v(v - 1) - 22)
To( v(u - () 2)
IP En Li pvd An "3, pwi Me, mm}
(mzr)3
[(( -((-1)(u 2)
Σ
P P(m
V1
ww) (
= palle Mn mw) Po { ky - pa X 22, paz ph 3h mm)
(mv)²
11.
r(v 1)(U -2)
1 vx-2 - 1 1,0-3 2
m²
(67)
(mv)²
122
1 22
(v-b) 11 + \1 # K13 = and v/ * v/ (mult. v(u 1)2(u 2))
v11 - 1) 2)
Telk, 1) (0-
Σ
Plm u1 دي uv; A1 شي ul' ;sz مي ww)
(mw)3
v(v 1)3(v= 2)
1 s 6=-2 -1 1
m²
(68)
(m
6² y - 2 -
(v-c)-11 F A1 7 Ks1 μa F μt and v' == (mult. v(u- - (1)
Telps, (0(0-)) v(1 vo(u-1)3( - 2)
Σ
P Pum-
my μv; A1 v2 pi:i 3 n'v
un
(mv)3
V1,V2.
v(v 1) 2)
1 x8-2 y
mi
(69)
(mr)3
2 0a 1 8a - 2
(v-d) MN f A1 f kR13 nl + μ and v/ fv (mult. v(v - 1)3(( - 2))
Telp, v) (v- u(u - 1) 2)
Σ
P {fc بt pvv \1 -2 pv ;k wa N'v}
(m²)3
#1.422.03 ya 2x-
v(v - () 2)
(m²)3
m
22 vr - 12 2
(70)
D.1.4 Variance of the correlations
By adding together all the terms,
((00))))))) -
Peis (n, ((al))
2 ))) (
(olve)) + ((:5
Σ
Ps 23
21 )) ((: E ps ( (())
3 Σ
(pli ulma) (1) (11>1)))) (1) (v(mm))
Au N1
v me (me - 1)(v - 1)2
us1 (1 - mm/mm/mm (1-m/0**)
(71)
(v=
()²
6
mmm
mm
D.1.5
Covariance of the correlations
For all X pb
E Σ C(UV)) = Σ C(u,)= =
(72)
Therefore,
C(H22) Σ c(),2) C(H,v)2 + Σ [(())))((,))= = =
Σ (((,,))C(),v) ((C(,
(73)
25

---

Analogously,
Σ
( =
(74)
In addition,
C(u.V) Σ ((A,k) C(I,))((),))+ E ((( =0
A=1
Σ (()))) =- Σ ((C(H,))(())) x)) = -((1)1)))
(75)
D.2 Level-2LCA
When the parents of the i-th and j-th tokens are in the same level-1 patch.
P ,(
Σ
Σ
( Pa (ulps))) (v/en (v(vs) (o (2) (11, us (22) (12), (42), (12 52),
P(X:=1)x
Σ
( (mlpz))p
(2) (ny (3) (1)2),
Ma
P -(X,= = Σ
pf
(1(1))
( (3) (v2), (j3= = iz).
(76)
Therefore, in the limit of large m, where the univariate probabilities of the hidden variables of any level converge to L/U, (1,))
-, X - - -
Σ P1.1
Pi nd (w)x))) (vlu))
Σ Prndd (1i Kil2))p (3) (12) (12)
Σ 12,00
(2)
(milu))) (3) (u2)p ( (3) (u2) (12)
Pis
(ulun)) (1
(77)
Since the rules of different levels are independent, and (CI)) v1) =0,
(c(2) ()
Σ (p (elm))p (vln)) (c10) = O.
(78)
The variance/2nd moment reads
(c10)
Σ
(pi"
Σ
(elmn))p))
(n:)))
maa
Σ
( (ulpz)) (pp (1) (1Pr))) (v(ks) (ct (n
Ni Ni
ph 0 (ulp1))
Dp (wlAi)) (w)))) (1"
A1
Σ
(4121)))) (1P2))) (ulaa) ( (A1)))))))))))))
A A
(79)
26

---

D.2.1 81 f1 case.
(1) relative to different positions This is the easiest case because the production rule probabilities p; i are independent and identically distributed (with respect realisations of the RHM). Therefore, using Eq.. 34,
- (de t0²) 02
(D (ulpz) (2) (v/12))) PP 02 (mll))) (2) (1/ (2) (vlma))
(
Ph (0 (vlla))))) (11)))))))))
Pi 1 (ulm1))) )²)
1 + of
1
1
22
22
12
(H/2)))
Pi
(2)
)p?
(2) (u121) (v11)))))
1
1 v
122 + 0
v2
22 2
Pi (p (alu))) (u(At)p (u/Ai)) @ (vlm)) =
(80)
22
22 y
By bringing these factors outside of the X and K1 sums in the right-hand side of 79
((::((011))) Σ
122 + o;) ( (CU)
R1
1
(
1
1 c
Σ
(oW) (1),
+ p)
222
222
222 2
Ki Si
1
1 0
+
+
2
22
22
12
AIFFI
1
1
2
(2
222
22
Σ P1
(cm))))))))))
[
1 ( +03
]
(81)
where, in the last line, we used Eq. 73 Eq. 74 and Eq. 75 express the covariances of the (C)) (p,, v1's
in terms of (C (H, 2)23. After simple algebraic steps, recalling the definition of 07 in Eq. 29
(a (C()))))))) = v²
(
e
1
v 1
2
(M1,
(82)
2 1 umn
m
D.2.2 i = ji 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 [q. 75 to rearrange the right-hand side of [q. 79|as follows,
( (10))
Σ M1p1
(c (C0) (1),))))) (ppll))))<(((e)))
V
A An
1
Σ bowelaabbuullalpppbbbbaooaaalal
(83)
1)2
27

---

The value of (ptula))((()))))))m))))
is actually independent of and v1, thus
( (c)))
((CW))))
Σ ((p(alun)p(euu))) Pa
1
E
No Nitt1s
AIFM
(84)
(U 1)2
A1 #p
The first term to deal with is (2-2),
Σ
PfNe M "n 11 22, us 1s
We
u; v1
(85)
m
then (2-1-1) and (1-1-2),
Σ
pfm Mi, p:
P
"3 v1
Wa, Us Ki و v
m
(86)
Σ
Pfp
P
Mi, μi; A yi pivi " vi
شوك v (87)
m
and, finally, (1-1-1-1),
Σ
Pfn 3h 1
22 un
1/3 1;K1
14 v]
m²
(88)
We will further separate the case where = v (i) from the case μ F (ii).
2-2, i-a) (p= (w= 10=1,1=10 vi)
((pul1))p((lzz))) = m
P Pf11
Mi, pi 11
V2
Via,
μi Mr 2 14
pc: Mn
V1.
Σ
p mi BfNI
Sig m
m
4
Σ
P {um
22 1 2n p5
m
3
P PfM1 {1 21
21 H
pi
m
6
Σ
PP PfU1 U1
- pr M1
4/
Vi
m
1
Σ
P P&Ms
V/3
144
U12
115/111
11, k1
m
Vn Wn wha (1 We
m
+ m(m (m 1) 0011
mmm
1)( 2) v0-1 1 1-
m
2s
1
15 1
2 2
m(m
1)(m 2) 3) 1a11
1--1
2 8- 3
(89)
v
y 1
- 2 1 3
28

---

2-2, [ 1/1)
(((e(s))()))
Σ
P PfNs
22 11
w/a 14
us
ml
11 Massat
Σ
p pfm
μ1: 11 V1
V3 11
ml
V1.V2= b
IP fel
Ui
11 11
11
11
m
s/1
Σ
IP
p Mn
41
pi
mn
42
pi 11
-
4/
14
m 4
sh of P..
+
Σ
IP
P111 [4
1/1 11:
82
i4; 11
4/3
p1; 21
Mid 11)
m
1
m² 1z -1
m22mm
1) 0--1 1 1z - 2
2
m
V
2a 11
21a
2a 2
m²
(m
1)² w--
1 b= - 2 2 3
(90)
8 3
2-2, ii-a) (1
(p(ul)))p(vle))))
Σ
P
PLui
V2 pa pn
pi Mi
vs mii
m
1
Σ
PP
11 Pfui
1/3 vi
pi 141
m
1
Σ
IP H1
pr uu $1
42,
|4: k1
Wa
m
tu wbs (11
1
Σ
IP PfMs U1 -1 pi
- vi 11
24 2/ m
4
1
Σ
P P(11 U12 ب u1 11;111
23, v}
v, nu
m
Vi Vn (V ve
m(m 1) 0-11
m(m
1)(m - 2) b-1 0-11 -
+
m
2
1
21
1
ys - 2
m(m
1)(m 2) (m 3) 2
1 1rー4
991)
v
2
3
29

---

2-2, ii-b) (4 #1
(p(ulu))p(u(u))))
1
Σ
Pfu
P
-h pil - μt in
- Us us 2 v}
=
m²
1
Σ
PP Piu 3y pid 2, vs
m²
1/ =
PI M...a.a..
Σ
P Pfps M1 1i pe: 11
Va 1/; - v }
+
m
Ph Aaa Wa
Σ
P Pmm M "
+
mf
M:: Mn
- m1u
tha W/ o 1h Mhs 11,
the
Σ
P { M1
1/1
1/ 11:
Via viu 2 v}
+
m4
Me; k
1
m2 y--1
m
(m
(m - 1) 8--1 y--1
+ 2
m
20
1
2a 1 2 - 2
m
(m
1)²
0a -
1
(92)
21 - 2 21 3
2-1-1, 11=
1
Σ
P Piu Mi 1o 151 Me, μt u4
V3 μm K1
24, 11
m
1
P pful Mi
ووك mn
m
V1 = th
3
Σ
IP PPN [1
11 p1 M1
+
-
Mik1
m
t/ =
+
m4
Σ
PP U1
0/1 p:
2/
Va.
ps: K1
24 11)
1
mm y
m mm²mm= - 1) 6--1 - 1 1y01 2
0² 1 + 3
m
21 -1 1 8* - 2
m² (m 1)(m- - 2) 2x
- 1 1. - 2 10 3
(93)
v
1
1 - 2
2-1-1, i-b) (μ -L=z4 UU- # H1, K1 p1)
(o(ul))))p((()))) (p((vl)))((()1))
1
Σ
PfRI
P
21 pill 22 μ1
23
μi 11 24 m
m
4/..
1
Σ
P Pfu {11 Vi, μc 1/1 V2 m
m
V1.Va Wh ala m 11
3
Σ
PP PfMe m1 ti 15,11
Mee μi v1 2i 18)
+
m
w/ wh VI, Maa
1
TP IP(1 11
W/ p,
2/ p4; 141
+
11 }
m4
1
mm 1 - 1
mm²mm - 1) 1-51 - 1 1-811 2
1 +3 3
m²
22a - 1 8 - 2
m²
(m 1) - 2) x - 1 v-5 - 2 1 3
(94)
U
0a 1
ya 2
equal to the value of 2-1-1, i-a) as it should be.
30

---

2-1-1, (M=R, V1 + MI,
# (1)) 21))
1
Σ
P PfNN m pa
-2 is
die
ووz 10
= m
ps no
Σ
P Pfm
Mi, pr
Va
"y, m1
m
Vi
1
P f4
Vi
pi M1
V2 p1
V/a
p4; K1
3/ pd.
m
1 21 11.44.144
1
m
2
1
2
m
(m - 1) v0-
11 1/01
2 1
11-11
3
+
m
20a
1
11
2
v
10
1
v 2
U 3
(95)
2-1-1, li-a) (utK, #1 = v1)
1
Σ
Po
1/2
14 vi
p 14
Ki
m
1
pf Fu
P
Mi,
1/a
24 m}
pe; p4
V; K1
m
Σ
P M1 p|NL
+ m
pil
μi p1
22 vi, (11,
1
m2 (m 1) yd 1
md
v
1 - 1 1a -2
2
m² 222mm
1) - 2) 1
y- y
(96)
v
v3 1 8=a 2 0² - 3
2-1-1, ii-b) (4 2/1 #1, 11 #1) (oll)))p((le))(((k))))
1
Σ
P (ui Mes pa " μن
33 vili Mey v)
m
VI ahs
1
p Pfui [ii
Un
V/
1ill 2t, w}
ml
uc;
V1
1 th pha
+ m
Σ
PfN1
P H1
pill1
#2 p4
M2 v
3i dr Vy. (011
1
m2
(m mm
1) y--1 11 1
m
w
1: 11 1 10 - 2
m²² 2m2mm-
1)(m - 2) x - 1 y
+
(97)
v
03 1 8 2 2 -
3
2-1-1, li-c) (1 v1 # m1, 11 + (M1, 11)
= m
1
Σ
PfNI
P
#2
p1; 1/
K1
Mey m
Σ
P PfP1 p1
U1
m
11,
Vi, mo bla
1
Σ
P PfuI
Vi
V2 pG
14
+ m
ui
Mi
D3 Ki
1/
1
mm
6 -1
2:5
m
(m
1) 1-
+
m
2 1 21
2
w
2
2 2
3 (98)
31

---

1-1-2, overall contribution equal to that of 2-1-1.
(- 1 A1 = (u - 1) of the (o - 1)² choices of λ1, ki))
Σ
03 1 P Ffm - pid1 w/ pipl
04 pl)
m
2I nata (p((ll1)) ( p((l\11)
1
m² 2
1
m m 1) 1==1 1 1 -2
+ 2
m²
v
v
1
1² - 2
m (m 1)2 ve-1 1x-1
2 v--1-3 3
(99)
1a
2a - 2
09 3
from the value of 2-2, case i-b).
1-1-1-1, (1+ U4 111 11, A1 7 K1, (v 1)(v 22) of the (u 1)2 choices of k1)
(WWlaaappWAADDil///a/////ad = m Σ
PP Pf11
uil 1/ Mú A1
1/2 pill
1/3
2/4 11
μc; K1
m3 3 w- 1 -2
m - 1) v
1 21 3
+
m²
v² - 1
2s -
w² -
2 - 2
20 - 3
(100)
from the value of 2-1-1, case i-c).
1-1-1-1, (u= = u1 d1 K1, v:- - 2 of the (u 1)2 choices of )1,
IP
En 1i μú d
1/22
pi 41
μ1; A1
2/4 11 }
m
V2.
m 3
y
1
v--1 -2 2
m 3 (m - 1) v
1a-1 1
2 3
m
1
1
6¹ - 2
1. - 1
21a - 2
20 - 3
(101)
from the value of 2-1-1, case i-c).
1-1-1-1, i-d) (p- = + u1
=1, P1, of the (r- 1)2 choices of (1)
1
PP
M1
11
W2
11
1/a
11: M1
W4
p
m
1
m y--
-1
m mm(m - 1) 8=-1 1
1-51 - 2
8 - + 2
m
2/8 1
y - 2
m² (m
1)² 00 - 1=51
2 1 3
(102)
13 -1 2 - 8² - 3
from the value of 2-2, case i-b)
1-1-1-1, (1 = v4 #1 + U1, A1 = 11, K1 + (11, v- - 2 of the (v - 1)2 choices of k1)
Σ
PP. f/11
$ μr V1
13
11; Rig
19e, 11
m
1
mm و
1-8-1 -2 2 m²(m - 1) 8 _ 1 1: - 2 2 - 3
m
8
1
1:a
03 1 21a 2
(103)
from the value of 2-1-1, case i-c).
32

---

1-1-1-1, (p== V1, A1 + (11, Mi, 1 2 of the (v - 1)² choices of k1)
bww.lwibtwwk))yp/pbbbbbe m
Σ
IP 11 ش pi A1
2 μi 11
8/
μi p1l
14, p1
Va.
m
1 2
-2 2
(m 1) 00 - 1 1:a
2 2 -3 3
md
1 1:a
v 2
v
(104)
from the value of 2-1-1, case i-c).
1-1-1-1, (11 = u1 1i # un An + (11,, 1, (v- (v-))vv-3)) of the (w 1)² choices
of (1)
1
Σ
P Plps
My μi; \1 1و pi و pc: ki
ش H
m
1
m
1--1_
1 1011 - 2 2 - 3
(105)
m
-2
3
1-1-1-1, (p + vs M1 11, \1 K1, (v
1) of the (u - 1)² choices of X1)
PP {u Mi, pú - pa
Ui v; W v}
m
VI, V2. Vo.
P PfN M1 Vi, 1i
42 #c \
v; A
m
v1. U2, / #11. 1442 mm
(m- 1)2
1.811 1--1
(106)
m
v
2 - 1 2 - 2 2 - 3
1-1-1-1, (u + Us 11 A1 F K1, (0 1)(U - 2) of the (n - 1)2 choices of (1,
1 md
Σ
PP u1
V1 ps d1
2/2
14 v V K4
p. 11
Σ
PP P/Ns tin uo; d1
12
Mig v
μi in
1iKi
m
1
mm (m 1) 1 -1 1-11 m
(107)
m
v
1s 2 1.5 -3
1-1-1-1, (1 # 11 A1 K1,
2 of the (v 1)2 choices of Xi, k1)
1
P PfMs U1 +1 Mi \1
- 11
d1
W/ v
m
1
m 3 (m-
1) 1051 -1 x- 18-1-1
(108)
m
V
4 - 2 13 - 3
from the value of 1-1-1-1, case ii-b).
1-1-1-1, (n 4 vs M1 4 u1, A1 11, K1 = M1,
of the (u - -1)2 choices of \1,
1
P {m "i, ue; 13 k1
13 v: un
2/4 w)
m
1
m2 (m
1)² v - 1 x- yター - 1
(109)
m
03 - 1 0= 2 0² 3
from the value of 1-1-1-1, case ii-a).
33

---

1-1-1-1, li-e) (1r # U 11 A1 11, K1 + 11), - of the (v - 1)a choices of λ1 k1)
1
P Pfus - 11:11
V2
V4
14
Me; 11
k1
V
m
1
m 3 [m
1) 1²-1 - 8.51
8a-
(110)
m
v 1 2e 2 21a 3
from the value of 1-1-1-1, case ii-b).
1-1-1-1, ii-f) (1 + u, m M1 21 + M1, p1,,
2 of the 1)² choices of (1)
1
IP
μ1 A1
pi; 11 $2
Wy
Vi
μ1
V4a
1/
m
V1.4a.v3.44
1
m (m
1) 10-1 -
r wt-1 1 -
(111)
m
2
11a
from the value of 1-1-1-1, case ii-b).
1-1-1-1, ii-g) (u # v, μn # d # k1, (41, A1); (v- - 2)( 3) of the (1 - 1)²
choices of k1)
1
PfMI
P
21
A1 Mi
22 pi
vi K1
2 v
m
11 Va..aaa
1
m
1--1
1-51
1:
(112)
md
00
2 v 3
Total. Consider the factor multiplying ((C(1)2) in the right-hand side of Eq. 84
F(u,D)== Σ
Σ Katt
U
21
An Aiaai
Σ
(113)
(c
1)2
By organising the terms in the sum according to the classification of the previous paragraphs,
F(u,v) v (F (FR22) (H, + (v 1)
20(u 1) (22-1-11 + F(21-11 + (0 - 2)
u(u - 1)
(F(1-11111) + (v 2)
(114)
(v - 1)2
+(v - 2) ((1--11-) + F (111111) + (v- ((1--11- + (v 2) + (v - 2)(u - [(I--1111
For p by summing all the case terms, we get
F(p, 8d (no²(v + 1) 22 v + my + m2?) ) + (u + 2)
6v + me + + m2²))
( 1) 2) -3)
1s (m + 1) m m
m3 1
(115)
34

---

Summing, instead, all the case ii) terms, we get, for # n.
F(U,U) 2¹ u (1
8m + 7me 3mm2))
(v - (m)
1) 8 2) (1)--3) 3)
(6 10r mw + 5v + 3mw? 1² 3mm + mo+)
1
(116)
(v - ()(())))(())))))))))))))))))))))
1)(v" 2) - 3)
m²
To up, as in the i # case (Eq. 82p. for large vocabulary size v > 1 and large (e.g. m = fu- with f E (0, 1).
2 V.m. (cI))
(c00)) (1,1))
(117)
m
D.3 Level-I
By replacing (0) with Che 1) and ((2) with C(9, the recurrence relation Eq. 79 extends to the case where the LCA of the i-th and j-th tokens is level-é symbol. Asymptotically in and and independently of f and v,
(1,
((00()))))) -1--m/001
m//0-1))
(111))))))))
m²
((c1)))))))
2)
(1 a1-mi (1-m/v²))
(118)
13m2t-1
E Sampling noise in the empirical correlation function
In this appendix, we prove that the sampling noise empirical correlation functions of RHM data has characteristic size (v P) P)11/ 1/2
Let us denote, ease notation, IP {Xa-t μ, Xa = m3 with p(u, (Xa-t = 14} with p(4) and P (X = μ} with p(v). When measuring probabilities from the frequency of observations over P i.i.d. samples,
pl, v) = P 14
(119)
where denotes the empirical estimate and the indicator variable is with probability p(u, v) and otherwise. With 8 having finite mean and variance, by the central limit theorem,
plu, v) P-x, p(u, v) + v plu, V) - plu, v),,
(120)
P
where & is a Gaussian random variable with zero mean and unitary variance. Analogously,
p()) P-30 p(m) + p(()(1 p(u))
C1.
P
p(v) P-roo p(v) p(v)
-p(D))
C2.
(121)
P
where Çi and (2 are also Gaussian random variables with zero mean and unitary variance, correlated with each other and with ç.
As result, the empirical estimation of Cr v) reads
p(u,v) p(u,))-p(w)p(v) + p(p,v)(1 p(H,
Cr(H,)) P-100
E
P
-p(W)y p(u)(1 p(v))
p(p)(1 p(())
P Ce Ge-p(u)
P S1.
(122)
35

---

In the limit of large and m, where p(u, v) converges to 1/0² plus vanishingly small fluctuations and p(u). p(v) converge to 1/u plus vanishingly small fluctuations, the dominant noise contribution is the one of ç, with standard deviation
V plu, (1 1011-plpe U)
1 o2p
(123)
P
The correlation function C(t) is the standard deviation of Ce v) over vocabulary entries. Hence, the sampling noise on Ca, v) results in additive factor of (u² P)-1/2,
F Correlations between mask and tuples of observable tokens
In this section, we generalise the results of App. and App. E the correlations between the last token and s-tuple of observable tokens.
Let us then replace μs 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,
(1,
Σ Ph (mll))) (( MA.
(124)
m
where the second line is obtained by recalling that, for each available s-tuple of input features p. there is a unique level-1 variable μr (1) that can generate it, with probability 1/m. The mean of C( (H, vanishes together with that of ((E-1)(1 11). Te variance reads
(H.))))))
Σ P1.81
(1 (vlma) ( (cle- () (1(W)) k1)
m
(c(t)))))))))))
12
Σ
m
22
6
v
1
1
1
-
+
(125)
m
2
where we used Eq. 74
Using Eq. 29 and
Eq. 34
((CK))) un m))
(cO)).))))
e31,,
m²
2 1 um
m3
(126)
which equals the token-token correlation divided by a factor of m.
Correspondingly, Č+ is reduced by a factor of vm. Crucially, since the average joint tuple-token probability p(u, v) is 1/ 1/(u2m), the sampling noise size, obtained via the calculations of Apppp E is also reduced by factor of /m, leaving the condition of Eq. gunattered.
G Experiments on deep CNNs and scaling of the loss steps
In this section, we present empirical learning curves of Deep CNNs trained for last-token prediction (details in subsection A. In particular, we discuss discrepancies between these curves and those of Transformers (Fig. 2p in subsection G.T. verify the scaling with m of the first two steps F.q. 12
in subssccction G.2 then discuss the role of the context window size in subsection G.3
36

---

test cross-eutropy
tost cross-eurzopy
CNN
10P
10%
10a
10
training set
training set
Figure 6: Left: Learning curves of deep CNNs trained RHM data with = s= 64 and for different sizes t the context window. The network's 's depth is fixed to log log log (f 1) and the blacked dashed line represents predictions from Eg. 12 and Eq. 11 The finite context window causes saturation of the loss predicted by analysis. However, the third step occurs with less training data than Ps. Right: This discrepancy is highlighted by the comparison of Transformer and deep CNN learning curves, here for I and m 8.
s 2, u
1.00
Lest cross cutropp C
m=+8
2-
0.75
m5=25
0.50
1-
0.25
0.00
10a
10a
10
10a
10a
10a
10a
training set size
P/P:
Figure 7: Learning curves of depth CNNs trained RHM data with L -=3, 3, o= 11 and in the key. Dashed curves highlight our prediction for the first step. In right panel, first step made to collapse by rescaling P with Pi and & with La log v. The collapse confirms our prediction on the behaviour P with m.
G.1 Differences between Transformers and deep CNNs
The learning curves of deep CNNs qualitatively similar to those of transformers, but also present apparent quantitative differences, as shown in Fig[6 Specifically, noticeable difference is the sample complexity of the third step P3- 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 result, the model can directly access the correlations between the last token and tuples level-1 symbols. According to the discussion of 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 Pa reduced by factor m with respect to Eq. 12 In general, we can assume that, the presence of weight sharing, after the ê-th step all level-(E 1) features have been learnt, so that the (E + 1--1)) 1) step requires resolving correlations between the last token and tuples of level- 1) features. The corresponding sample complexity scales like m instead of 2 However, the steps with {> 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 production rules m
Fig. 7 and Fig. 8 show a scaling analysis of the behaviour of P1 and P3 from Eq. 12 in Deep CNNs.
The collapse achieved when rescaling the number of data P by Pz and the test loss by the value before the jump Li-1 confirms this prediction.
37

---

1.00
m0
test. cross- cosss-nntropp
0.50
0.25
0.00
10a
10a
107
10
10
10
10P
101
10a
training set size
P/P
Figure 8: Same as Fig. but focused on second step, highlighted on the left by dashed curves. For second step, collapse achieved by rescaling with P2 um" and with L1 from Eq.
10
Test cross entropy
15
3 10"
x 10
10"
10a
10
training set size
P/(++1)
Figure 9: Zoom of the learning curves in Fig. 6. left, the first step. The zoom highlights the dependence of the sample complexity on the context size The collapse the curves the right panel, achieved after dividing P by (t + 1), reveals that o (t + 1). This dependence analogous to the sample complexity regression of a target function depending on a tow-dimensional linear projection of large-dimensional input [55].
G.3 Scaling with the size of the context window
Similarly, Fig. 9 shows scaling analysis (for CNNs) of the behaviour of Pi with the number of s-tuples in the input, proportional to 1) with the size of the context window. The figure highlights a linear behaviour P1 x (t + 1) that our analysis does not capture. Nevertheless, this behaviour 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 Proving this result by considering single or few steps of gradient descent, as often done in this literature, is an interesting work for the future.
38

---

NeurIPS Paper Checklist
1. Claims
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 our generative model presented in insection 3] In|section we build our prediction of the learning curve based reconstructing the grammar's 's hidden variables and compare with the empirical learning curves of transformers trained our model dataset. Our general conjecture is presented in secctiiinn 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 long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations 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 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 separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails 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 fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
39

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The calculations of section 3 (subsection 4.1 are correct within the scope 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 cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We use standard machine-learingg frameworks in all of our experiments, as described in (sectionn 2 and App. A
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer 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 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 be necessary to either make it possible for others to replicate the model with the same dataset, or provide access 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 large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
40

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code and data can be found on the GitHub repository indicated in the main text.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
guuides/CodeSuumisss
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
See answers above and App. A
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: As stated in the figure captions, all our experiments averaged over several independent initialisations of datasets and machine learning models, and error bars are shown in the plots.
Guidelines:
41

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by emror bars, confi- dence 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, 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 the standard error of the mean.
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 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
This information is indicated the end of (ection 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 compute required for each of the individual experimental runs well 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 failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http://ppp...aaoo....oopp//p//aa
Answer: [Yes]
Justification: There is no violation of the code 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 deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction)
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
42

---

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 partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out, For example, it is legitimate to point that 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 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe 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)?
Question:
Answer: [NA]
Justification:
Due to the theoretical nature, the paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 dataset.
43

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperssi thcode com/ com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's ' creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new assets released.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the datasct/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing experiments or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: See answers above.
Guidelines:
44

---

The answer NA means that the paper does not involve crowdsoureing 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 expect authors adhere 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.
45


Reviews:
[{"review_id": "smNa0lia6r", "reviewer": "Reviewer_Fszw", "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. \n\n2) 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. \n\n3) 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. \n\n4) The key contributions from this paper are : \n\na) 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. \n\nb) \"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 )\n\nc) A general framework based on synthetic data generation model (RHM) to further study the relationships between training dataset size, effective context window etc", "questions": "1) Have the authors tried replicating the results from Shakespeare experiment on a larger dataset ? \n\n2) Have the authors tried varying model size in addition to dataset size to see if it recovers chinchilla curves under fixed compute ?", "limitations": "1) This work has no negative societal impact\n2) Authors have done a good job at discussing limitations of their approach that comes due to their use of fixed geometry of data tree.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) The paper is well written with clear notations to motivate problem setup followed by clear sections solidifying each contribution. \n\n2) The order of claims made is clear and authors did a good job at showing results in synthetic setting and then applying same methodology in real datasets and models.", "weaknesses": "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. \n\n2) Since the synthetic data generation process is cheaper, authors could have used higher P (training dataset size) in experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weakness 1/Question 1.** Please see the comment above (author rebuttal).\n\n**Weakness 2**. Although the generation process is cheaper, the costs of training limit the available range of $P$ to that considered in the paper (up to a few million).\n\n**Question 2.** Since this paper focuses on sample complexity (and not on optimising performance at fixed compute), we varied the model size only to guarantee overparametrisation, in the sense that the training loss approaches zero as the training time increases. Increasing, depth, number of heads or embedding dimension of the architectures beyond the values reported in the paper does not affect performance (measured by the test loss at early stopping) beyond the fluctuations due to the randomness of the initialisation. We will clarify this point further in the text and mention the possibility of studying compute-optimal scaling laws as an interesting question for the future.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Bt4L3erq8g", "reviewer": "Reviewer_h6xP", "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.", "questions": "1. Why is the conjecture only tested on the shakespeare dataset? How about testing it on news corpora or other domains?\n2. 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 were adequately addressed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This is an interesting paper which tries to understand a very fundamental problem -- what is the relation between the training set size and the resolution of the learnt token-token correlations in neural nets learnt via next token prediction.", "weaknesses": "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.\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weakness 1/Question 1.** Please see the comment above (author rebuttal).\n\n**Weakness 2.** We agree with the reviewer that this key point needs to be emphasised much more. In particular for deep generative models of data (large $L$), we indeed find that for large $P$, the learning curve can be described with a power-law $P^{−\\alpha}$ as in~[17] (Kaplan *et al.*,  Scaling laws for neural language models), with exponent $\\alpha =\\log{ (m/v^{s−1})/(2 \\log m)}$. It is interesting to note that this power-law results from a series of `emergent' phenomena where sub-portions of the data tree of different depths are learned. We will add a full paragraph on this point in section 4.1 and restate the importance of the result in the conclusions.\n\n**Question 2.** The tests performed in sections 4.3 ( behaviour of hidden representations with increasing $P$) and 5 (saturation of the scaling law due to the size of the context window) can also be performed on state-of-the-art LLMs trained on larger datasets.  Such a study would require a paper of its own---we are currently seeking to develop collaborations to make it possible. We also hope that the present paper can trigger concurrent works in that direction.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "77vGrCqb9w", "reviewer": "Reviewer_qWaK", "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).", "questions": "No additional questions.", "limitations": "I think the authors adequately addressed the limitations of their work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- I think this paper addresses an interesting and useful question about the relationship between sample complexity, language learning, and effective context size. Prior work has investigated how neural networks could recognize CFGs, and I think this work represents significant extension of this direction by trying to also characterize the learning dynamics and sample complexity. More generally, better understanding the relationship between sample complexity and effective context window could be significant given the growing interest in long-context language models.\n- The key results (about the relationship between sample size and the ability to resolve long-distance correlations) are interesting, and I think these methods could be useful for future work on more naturalistic models (which the authors discuss in the conclusion).\n- The experiments seem to support the theoretical results. I appreciate the analysis of hidden representations and the experiments with natural language.\n- I find the writing and notation to be clear and the experiments easy to follow.", "weaknesses": "- 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.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weakness 1.** While the assumption of fixed tree geometry is unlikely to be satisfied in natural language data, we do not believe this assumption to be necessary for the power-law decay of correlations. [This paper](https://arxiv.org/abs/1606.06737), for instance, shows other examples of text data where correlations decay as a power of the distance and argues that this is possible due to the context-free structure. This is indeed what we find in our model, where correlations decay exponentially with the distance along the tree, while the actual distance between tokens grows exponentially with the tree distance, resulting in power-law behaviour. We expect that this result will be quite generic.\n\n**Weakness 2.** While we will add experiments on natural text data to the present submission, the research of effects that require other assumptions to be described is indeed out of the scope of the present work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GShwkw0qkG", "reviewer": "Reviewer_Y3P4", "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.\n\nA 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.", "questions": "Questions:\n1. 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?\n2. 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.\n\nSuggestions/Typos:\n* 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].\n* “CGF” and “PCGF” are often used (when “CFG” or “PCFG” are meant). For example: L67-74, L97, L98\n* L87: “wthe” -> “the”\n* It could be good to cite \n\nReferences:\n[1] Shieber (1985). Evidence against the context-freeness of natural language. https://www.eecs.harvard.edu/shieber/Biblio/Papers/shieber85.pdf\n[2] Saphra & Lopez (2020). LSTMs compose (and learn) bottom-up. https://aclanthology.org/2020.findings-emnlp.252/\n[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": "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.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* Thorough characterization of how latent hierarchical structures can be induced by neural language models from token correlations.\n* The notion of “token correlation” is also deeply defined in a way that goes well beyond a naive analysis (e.g., bigram frequencies). Specifically, the relationship between token distance and token correlations, and how these can be traced back to the hierarchical dependencies between them, is explored in a way that I have not seen before.\n* Two architectures, Transformers and CNNs, are analyzed. Comparisons are appropriately qualified and thorough.\n* The analysis quantifies the importance of variables whose contributions to learning were not previously quantified or theoretically analyzed—most notably, (effective) context window size.", "weaknesses": "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.\n2. 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:\n3. 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?\n4. 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.\n5. 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.\n\nAll of these points are reasons why I have set my presentation score to 2 and soundness score to 3.\n\nSee Questions for references.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weakness 1,a (context-freeness).** We agree with the reviewer's remark on the context-freeness of natural languages and we will modify the text accordingly, stating specifically in both the abstract and the limitations section that the context-free description is approximate and captures many (but not all) syntactical forms observed in natural language.\n\n**Weakness 1,b (poverty of the stimulus.** We agree with the reviewer's definition and we will clarify the text to make it explicit. We will replace the sentence in line 20 of the introduction with *stating that the data acquired by children is not sufficient to uniquely determine the grammatical structure of their language*.\n\n**Weakness 2 (non-ambiguity of RHM).** We agree that the non-ambiguity of the rules and the uniformity of the production rules are not  language-like features, and we will emphasize this point further both in section 2.1 and in the limitations section.\n\n**Weakness 3 (additional dataset, contemporary text).** Please see comment above (author rebuttal).\n\n**Weakness 4 (ref. on LSTM).** Ref. 2 is indeed relevant to our work and we thank the reviewer for pointing it to us. We will include the following sentence at the beginning of the 'additional related works' section to acknowledge this result: *[ref. 2] provides evidence that LSTM language models learn short-range dependencies first and use them as a basis to build longer-range dependencies. Our results provide a theoretical framework for understanding this phenomenon.*\n\n**Weakness 5 (practical impact on LM research).**  This paper provides a novel explanation for the scaling laws characterising the performance of LLMs, and extends them to include the context window length(see also reply to **Weakness 2 of reviewer h6xP**). These laws are having a huge practical impact, both in showing that success could be achieved simply by scaling up LLMs and in guiding the choice of hyper-parameters depending on the available data and compute. In addition, our work suggests a criterion for optimising the size of the context window depending on the available data and the behaviour of token-token correlations. We will emphasise this point further in the conclusion section of the revised manuscript.\n\n**Question 1.** See comment above (author rebuttal).\n\n**Question 2.** See reply to weakness 5 and **Weakness 2 of reviewer h6xP**.\n\nIn addition, we will implement the reviewer's suggestions and cite the mentioned papers in the revised manuscript.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the referees for the detailed comments, and for finding our work interesting and supporting publication. They all pointed out that the paper will be improved by adding an additional set of experiments, perhaps involving a larger dataset made of contemporary text. We agree with the reviewers and, to answer their comments, we will repeat the Shakespeare dataset analysis presented in the first submission to the WikiText dataset, introduced [here](https://openreview.net/forum?id=Byj72udxe). As shown in the attached pdf, the token-token correlations of this dataset display the same behaviour as that of Figure 4, top right and bottom left---decay followed by training set size-dependent saturation. We are currently training a deep Bert-like transformer on this dataset to complete the analysis.

We address all the other comments and questions below the reviewers' comments.

Meta-review: 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.
Decision: Accept (poster)