nucleation

LIT-883: Towards a theory of how the structure of language is acquired by deep neural networks

4 min read

Properties4
StatusActive — read 2026-10-09 (NOTE-687); worth reading as the self-supervised sequel to the Random Hierarchy Model (LIT-877), and the first of that line in which the latent hierarchy is read off a co-occurrence matrix of observable tokens. For sequences generated by the RHM, the covariance between two token positions has zero mean over draws of the grammar and a root-mean-square size set by the depth ℓ of their lowest common ancestor, about ((1 − m/v^(s−1))/(v³ m^(2ℓ−1)))^(1/2) (derived for large v and m); the estimate from P samples carries noise of size (v²P)^(−1/2) (proved by a central-limit argument), so a finite training set resolves correlations only out to an effective distance t*(P). Deep transformers and CNNs trained to predict the last token show loss steps at about P_ℓ = v m^(2ℓ−1), where their hidden layers become insensitive to resampling the subtree below a level-ℓ symbol. That the networks use the correlations to build the hidden variables is argued, not proved. On character-level Shakespeare and WikiText-103 the measured correlation decays as t^(−β), and loss curves for different context lengths collapse under the t*(P) ~ P^(1/(2β)) it implies. No embedding, PMI or linear direction is studied.
Tagslearning-theory, representation-learning, compositionality, linguistics, anthology-candidate
Cited as “paper” byNOTE-687 — How the structure of language is acquired
Cited as “source” byTHEORY-201 — In next-token prediction on hierarchically generated sequences, the correlation between two tokens falls by about a factor m per level of their common ancestor, so a training set of P sequences resolves correlations only out to a distance t*(P) at which they meet sampling noise; learners come to represent the hidden symbols up to that depth, giving loss steps at about v m^(2ℓ−1) examples, and on character-level text the context at which the loss saturates grows as P^(1/(2β)) with β the measured correlation decay, THEORY-204 — On TinyStories and WikiText-103, the data-limited exponent of transformer test loss, fitted to the lower envelope of learning curves across context lengths at up to about 10^8 training tokens, overlaps γ/(2β), where β is the decay with lag of the top singular value of the token–token covariance and γ the decay of next-token conditional entropy with context length; under assumed per-lag scaling forms, a horizon n*(P) ~ P^(1/(2β)) gives the exponent min(δ, γ/(2β)), δ being the decay rate of the within-horizon excess losses, THEORY-778 — In the Random Hierarchy Model with v symbols per level, m rules per symbol and s-tuples, the covariance between two tokens whose lowest common ancestor is ℓ levels up has zero mean over grammars and root-mean-square size about ((1 − m/v^(s−1))/(v³ m^(2ℓ−1)))^(1/2), falling by a factor m per level, while its estimate from P sequences carries noise of about (v²P)^(−1/2), so the two meet at P_ℓ ≈ v m^(2ℓ−1)/(1 − m/v^(s−1)); all to leading order in large v and m, THEORY-784 — Language models trained on limited data show a test loss falling as P^(−γ/(2β)) because P training tokens resolve token correlations only out to a horizon growing as P^(1/(2β)), so that more data mainly lengthens the context a model can use, when the model learns within that horizon faster than it grows, as Cagnetta, Raventós, Ganguli and Wyart propose

Graph View

Francesco Cagnetta and Matthieu Wyart (2024), Advances in Neural Information Processing Systems 37 (NeurIPS 2024), pp. 83119–83163 — ARXIV-2406.00048, DOI-10.52202/079017-2645

Key takeaways

  • The task. The Random Hierarchy Model of LIT-877 (L levels of v symbols, each rewriting to m distinct s-tuples from the level below, no tuple with two parents), now with an unlabelled root and the last of the d = s^L tokens masked. A network sees the d − 1 preceding tokens and is trained by cross-entropy to predict the last.
  • Correlations decay with depth of the common ancestor. The covariance C_{i,d}(µ, ν) = P(X_i = µ, X_d = ν) − P(X_i = µ)P(X_d = ν), averaged in root-mean-square over the vocabulary, depends only on the level ℓ of the two positions’ lowest common ancestor, and falls in steps with it: C̃^(ℓ) ≈ ((1 − m/v^(s−1))/(v³ m^(2ℓ−1)))^(1/2) (Eq. 8, App. D, large v and m). Read against distance t this is roughly a power law, t^(−β) with β = ln m / ln s. In the maximal case m = v^(s−1) every string occurs and there are no correlations.
  • A finite sample is a finite context. The empirical estimate from P sequences saturates at a noise floor (v²P)^(−1/2) (App. E), so only correlations out to t*(P) are resolved; for a power law, t*(P) ~ P^(1/(2β)). The thresholds P_ℓ = v m^(2ℓ−1)/(1 − m/v^(s−1)) (Eq. 12) count the choices that fix two tokens with a level-ℓ ancestor.
  • Hidden variables from correlations. Given its parent, a tuple is conditionally independent of the masked token, so tuples with the same parent have the same correlations with it and can be grouped; tuple correlations and their noise shrink by the same factor (App. F), so the thresholds stand. Counting n-grams needs a sample exponential in the context length; a learner that reconstructs the hidden variables needs one polynomial in it. This route is argued, not proved for networks trained by gradient descent (§6).
  • Measured. Depth-3 transformers on L = 3 data show a loss step near each P_ℓ, to the levels bounded by Eq. 11 (Fig. 2); with the context cut to t = s^ℓ − 1 the curve stops after ℓ steps. In depth-4 CNNs matched to the tree, a layer’s sensitivity to resetting the production rule below a level-ℓ symbol, relative to replacing the symbol, drops from 1 to 0 near P_ℓ (Fig. 3). CNNs reach the third step earlier than P_3, which the authors attribute to weight sharing (App. G.1); the first step scales as P_1 ∝ (t + 1), which the theory does not capture (App. G.3).
  • Real text. On character-level tiny-Shakespeare and WikiText-103, the token correlation decays as t^(−β) with β ≈ 1.4 and 1.55; the loss of a transformer with context t levels off at a P that grows with t, and curves for different t collapse when P is rescaled by t^(2β) with β taken from the correlations (Figs. 4, 5; Eq. 16). The test bears on the conjectured link between correlation range and usable context, not on hidden variables, which real text does not expose.

Standing in the record

Filed on 2026-10-09 at the owner’s request, as one of the works cited by the batch on hierarchy and hyperbolic geometry (LIT-865 to LIT-877) that neither record held. LIT-877, which introduces the Random Hierarchy Model, names it among the same group’s later papers. Read on its own merits (NOTE-687); the reading produces THEORY-201.

It moves the Random Hierarchy Model from labels to language: the statistics that reveal the hierarchy are now between tokens of the sequence, which is the kind of object the record’s word-embedding readings work on (LIT-855, LIT-860, LIT-863). It does not answer QUESTION-025. It studies no embedding, no PMI and no direction; its correlation function is a root-mean-square over the vocabulary, which says how strong the dependence between two positions is, not which tokens carry it. What it adds is how a hierarchy shows in co-occurrence: descendants of one hidden symbol have identical correlations with what lies outside it, and the strength falls by a factor of about m per level, so a finite corpus shows the shallow levels and hides the deep ones. The details are in the NOTE.

Backlinks