NOTE-687: How the structure of language is acquired

Contribution

LIT-877 showed, for classification, that deep networks learn a random hierarchical grammar from a number of examples polynomial in the input size, and tied that number to when patch–label statistics rise above sampling noise. This paper does the same for self-supervision, where the statistics are between tokens of the sequence. It computes how token correlations fall with the depth of the tokens’ common ancestor, shows that a finite sample turns this into an effective context window t*(P), predicts a sequence of loss steps at P_ℓ ≈ v m^(2ℓ−1), and checks them in transformers and CNNs. It then conjectures that the link between sample size, correlation range and usable context holds for real text, and tests that on two character-level corpora.

Key insight

In a tree-generated sequence, how strongly two tokens depend on each other is set by how far up the tree their common ancestor sits, and it falls by a factor of about m per level, because each generation below the ancestor dilutes it. A sample of P sequences measures dependences only down to a noise floor of (v²P)^(−1/2), so it sees only the near, shallow part of the tree. What it sees is enough to group tokens: tuples generated by the same hidden symbol are interchangeable for everything outside it, so they have identical correlations with the target, and grouping them reconstructs the hidden symbol. Each level reconstructed lets the next, longer-range and weaker, correlation be used. More data means a longer usable context and a deeper representation, and the loss falls in steps.

Assumptions

• Grammar. The RHM of LIT-877 with the class replaced by an unlabelled root drawn uniformly from v symbols: L levels, vocabulary v at every level, branching s, m production rules per symbol, chosen uniformly among unambiguous rule sets (m ≤ v^(s−1)); every rule equiprobable; a datum is the d = s^L leaves. Fixed tree geometry, uniform rule probabilities and unambiguity are acknowledged not to hold for language (§6).
• Task. The last token is masked and predicted from the other d − 1 (§2), a simplification of both masked and autoregressive language modelling; P training sequences drawn from the data distribution.
• The analytic regime. The correlation plateaus (Eq. 8, App. D) are computed as variances over draws of the grammar, standing in for variances over the vocabulary, asymptotically in v and m, with the hidden symbols’ marginal probabilities replaced by 1/v. The noise floor (App. E) is a central-limit estimate in the same limit.
• Networks. Transformers on RHM data are stacks of multi-head attention only (no residuals, normalisation or MLPs), trained with Adam; CNNs have filter size and stride s, depth log d / log s, ReLU, maximal-update parametrisation, SGD. Batch size is the smallest that converges to training loss 10⁻³. On real text, BERT-like encoders of 3 and 6 layers on character-level blocks of t + 1 tokens.

Key results

• Eq. 7–8. For the masked token and a token whose lowest common ancestor with it is at level ℓ, C̃(t) = C̃^(ℓ) for t = s^(ℓ−1), …, s^ℓ − 1, with C̃^(ℓ) ≈ ((1 − m/v^(s−1))/(v³ m^(2ℓ−1)))^(1/2), and so C̃(t) ~ t^(−β), β = ln m/ln s. The mean of each covariance over grammars is zero (Eq. 40); its sign is random. Holds: asymptotically in v and m; checked against empirical correlations at L = 3, s = 2, v = 32, m = 8 (Fig. 1).
• App. E, Eq. 9. The empirical C̃ from P samples saturates at (v²P)^(−1/2); correlations are resolved out to t* = s^(ℓ*) − 1 with C̃^(ℓ*) > (v²P)^(−1/2) > C̃^(ℓ*+1); t*(P) ~ P
• Eq. 10–11. Conditioning on the last s^ℓ − 1 tokens gives a loss bounded by L̄_ℓ = log N̄_ℓ, with N̄_ℓ the mean number of values of the last token compatible with that context, solved by recursion; for large v and m, L̄_ℓ → log(1/(1 − f)) + v f^ℓ with f = m/v
• §4.1. An s^ℓ-gram counter needs a sample exponential in t_ℓ = s^ℓ − 1; a learner given the hidden variables needs one growing as m^ℓ, a power of t_ℓ.
• Eq. 12, App. F. Correlations of the target with a whole s-tuple, and the noise on them, both shrink by √m, so the thresholds are unchanged: P_ℓ = v m^(2ℓ−1)/(1 − m/v^(s−1)); P_1 ≈ vm, P_2 ≈ vm³. Grouping tuples by their correlations reconstructs the level-1 symbols, which correlate more strongly with the target than their children do; iterating gives the sequence. An argument, not a theorem about trained networks.
• Eq. 13. Putting ℓ ≈ log P/(2 log m) into Eq. 11 gives an early logarithmic decay and then a power law P^(−α) with α = |log f|/(2 log m). The paper prints α = log f/(2 log m), which is negative since f < 1; the sign is a slip. The power law is the envelope of the steps, which is the paper’s claim to unify emergence and scaling.
• Fig. 2. Depth-3 attention-only transformers, L = 3, s = 2, v = 32, m = 8 and 11: loss steps near P_ℓ, plateaus near L̄_ℓ, “good qualitative agreement”. With the context cut to t = 1, 3, 7 the curve follows only the first ℓ steps.
• Fig. 3, Eq. 14. Depth-4 CNNs, L = 4, s = 2, v = 16, m = 4: the ratio r_ℓ/s_ℓ of a layer’s cosine similarity under resetting the production rule below a level-ℓ symbol to that under replacing the symbol falls from about 1 to about 0 near P_ℓ, for layers above ℓ only.
• Footnote 3. A linear function of a one-hot s-patch cannot be constant on each set of synonymic tuples in general: v(m − 1) constraints on vs weights, satisfiable only if m ≤ s + 1. So a layer becomes invariant to level-ℓ synonyms only above layer ℓ, after a nonlinearity.
• App. G. Depth-3 CNNs, L = 3, s = 3, v = 11, m from 8 to 23: the first two steps collapse on P_1 and P_2 = vm³ (Figs. 7, 8). The third step in CNNs comes earlier than P_3 (Fig. 6); the authors’ explanation is weight sharing, which would make later steps scale as m^(ℓ+1) rather than m^(2ℓ−1), and they could not test it systematically. P_1 grows as t + 1 (Fig. 9), which the analysis does not capture.
• Figs. 4, 5, Eq. 16. tiny-Shakespeare (3-layer transformer) and WikiText-103 (6-layer), characters as tokens: C̃(t) ~ t^(−β) with β ≈ 1.4 and 1.55; empirical curves collapse under C·P^(1/2) against t/P^(1/z), z = 2β ≈ 2.8 and 3.1; the losses for t = 1 to 15 collapse as L(P, t) = t^(−αz) f(P/t^z) with the same z and α ≈ 0.1 and 0.095.

Claims

id	claim	strength	support
C1	In RHM data, token–token correlation has root-mean-square size ((1 − m/v^(s−1))/(v³ m^(2ℓ−1)))^(1/2), set by the level of the common ancestor	moderate	App. D, asymptotic in v and m; Fig. 1
C2	Estimated from P samples, these correlations saturate at (v²P)^(−1/2), so only those out to t*(P) are resolved	strong	App. E; Figs. 1, 4, 5
C3	Deep next-token learners on RHM data show loss steps at P_ℓ ≈ v m^(2ℓ−1), down to plateaus near the ℓ-gram bound	moderate	Figs. 2, 7, 8; qualitative for transformers, collapses for the first two steps in CNNs; the third CNN step comes early
C4	The steps coincide with layers becoming insensitive to the subtree below a level-ℓ hidden symbol	moderate	Fig. 3, one setting
C5	The networks reach these steps by using the correlations to reconstruct the hidden variables	weak	§4.1 argument; no proof, acknowledged in §6
C6	Composing the steps gives a power-law learning curve whose exponent is set by the grammar	weak	Eq. 13, dropping ℓ-independent factors
C7	On character-level English text, the context at which the loss saturates grows as P^(1/(2β)), with β the measured correlation decay	moderate	Figs. 4, 5: β and z taken from correlations, then applied to the losses; two small corpora, small models

Concepts

• Correlation function C̃(t) — the root-mean-square over the v² token pairs of the covariance between position d − t and the masked position d (Eq. 6). A measure of how strongly two positions depend, not of which tokens carry the dependence.
• Effective context window t(P)* — the largest distance at which the correlation exceeds the sampling noise of P samples.
• Sample complexity P_ℓ — the P at which correlations with tokens out to s^ℓ − 1 emerge from noise (Eq. 12).
• S_{ℓ,i} and R_{ℓ,i} — replace the i-th level-ℓ symbol with another, or keep it and redraw the production rule below it. A representation that encodes the symbol alone is invariant to R but not to S.
• Hidden variables — the nonterminal symbols of the grammar; here “synonyms” (LIT-877’s word) are the m tuples one symbol rewrites to.

Connections

It extends LIT-877 (NOTE-677) from feature–label to feature–feature correlations, and inherits its debt to Mossel’s hierarchical models and to Malach and Shalev-Shwartz’s clustering argument. It sits beside the synthetic-grammar probes of transformers (Allen-Zhu and Li; Zhao, Panigrahi, Ge and Arora, who show masked language modelling is optimised by inside–outside-like algorithms on PCFG data), and cites Lin and Tegmark and DeGiuli’s random language model for power-law correlations in grammars. Its empirical anchor is Saphra and Lopez’s finding that LSTMs learn short dependencies before long ones. It reads the scaling laws of Kaplan et al. as an envelope of emergent steps, against kernel-limit accounts (Spigler, Geiger and Wyart; Bahri et al.; Bordelon et al.). The same group’s Sclocchi et al. (diffusion) and Tomasini and Wyart (sparse RHM) are cited and not held.

Bearing on the record

• QUESTION-025. Of the RHM papers, this is the nearer to the question, because the hierarchy is read off a co-occurrence matrix of observable tokens rather than from token–label counts. In the large-m limit, where the marginals tend to 1/v, the paper’s covariance is v⁻² times the relative deviation from independence, P(µ, ν)/(P(µ)P(ν)) − 1, that LIT-855’s word2vec factorises (THEORY-182), but positional (one position pair at a time) rather than word–context. It still does not answer the question: it builds no embedding, computes no spectrum and looks for no direction, and C̃ is a norm over the vocabulary. What it does show is how an implication hierarchy appears in such a matrix, and three points carry over (the inferences are this record’s, not the paper’s):
  1. Ancestry shows as equality of rows. Tuples with a common parent are conditionally independent of everything outside it given the parent, so their co-occurrence with any outside token is identical. A co-occurrence embedding of tuples would put synonyms at one point: the hierarchy appears as a partition, nested level by level, rather than as one direction per ancestor.
  2. Depth shows as strength, and a finite corpus truncates it. Entries carried by a level-ℓ ancestor are smaller by about m per level, and only those above (v²P)^(−1/2) are measured. A derivation for QUESTION-025 on such data would have to say which levels a corpus of a given size can show at all, not only whether they are linear.
  3. Membership is not linear in the input code. Footnote 3: a linear function of the one-hot patch cannot be constant on each synonym class unless m ≤ s + 1. In this model the parent of a patch is not a linear feature of it; it becomes one only after a nonlinear layer. Single tokens, unlike tuples, belong to the rules of several parents, so a token’s own co-occurrence row mixes ancestors; the clean equality is for tuples. And the RHM’s covariances have zero mean and random sign over grammars, so nothing in them is additive across levels, which is the property THEORY-185 needs.
• THEORY-185 (LIT-863). Contrast only. LIT-863 names “the random hierarchy model of Cagnetta et al.” as where hierarchical attributes go next; this paper supplies the co-occurrence statistics of that model but no attributes in LIT-863’s sense, and its structure is random, not multiplicative.
• THEORY-182 (LIT-855). Both describe learning from co-occurrence in stages, ordered differently. In THEORY-182, with the population statistics given, gradient flow learns eigenvectors one at a time in order of eigenvalue (stages in training time). Here the stages are in sample size: a correlation becomes usable when it rises above the sampling noise, and longer-range ones are weaker. They are not in conflict, and a finite-sample version of THEORY-182 would combine them.
• THEORY-183 (LIT-860). THEORY-183’s symmetry is that co-occurrence depends only on separation, which makes the matrix Toeplitz or circulant and its eigenvectors Fourier modes. In the RHM it depends on the depth of the common ancestor, an ultrametric of the tree, not on separation: two adjacent tokens on either side of a top-level split are as weakly correlated as the farthest pair. If the THEORY-183 argument were run on a tree-dependent kernel, the eigenvectors would be tree wavelets, as in THEORY-186 (LIT-862). The paper does not consider this. Its real-text measurement treats correlation as a function of distance alone, which is THEORY-183’s premise, at character level.
• THEORY-195 (LIT-877). The same mechanism in a second setting, with the same caveat: in the RHM, the correlation threshold and the counting of the grammar give the same expression. The real-text test goes some way towards what THEORY-195’s promote_when asks: β is measured from the correlations, then used to rescale the losses, with no grammar to count. But it tests the effective context window, not the reconstruction of hidden variables, and the early third step in CNNs shows the threshold is not all that sets P.
• THEORY-186 (LIT-862). Another stagewise account of learning a hierarchy. As with LIT-877, the stages here are in sample size and go shallow to deep. In THEORY-186 they are in time and go coarse to fine, i.e. root first. Here the levels nearest the leaves come first. These two orders are opposite, and they should not be cited as one account.
• CLAIM-046. Weakly: the paper cites work showing that when data fit both a PCFG and a non-hierarchical model, recurrent networks and transformers do not consistently prefer the hierarchy, an instance of identical observations from different hidden-state models. It does not test this itself.
• CLAIM-119 and LIT-267. No bearing beyond QUESTION-025’s.
• New account. THEORY-201, Proposed: correlation range, sample size and representable depth.
• Practice. The paper gives no instruction. Its subject, what the statistics of language are and how they shape data-scaling curves, is what the anthology’s signal-structure and training-optimization topics hold, hence the flag on the LIT.

Limitations

• No proof for trained networks. The step from measurable correlations to networks that reconstruct the hidden variables is an argument; the authors say a proof needs a theory of deep networks’ dynamics on hierarchical data (§6).
• Agreement is qualitative in places. Transformer steps are compared with P_ℓ by eye; the CNN collapses cover the first two steps only; the third CNN step comes earlier than predicted, and P_1 ∝ (t + 1) is unexplained.
• Small synthetic ranges. L ≤ 4, s = 2 or 3, P up to a few million; one setting each for the representation probes.
• The language test is narrow. Character-level tokens, two small corpora, 3- and 6-layer models, contexts up to 15 characters. It tests the conjecture about context and sample size, which needs only correlations that decay, not a hierarchy. Power-law correlations in text do not show that text is tree-generated.
• Uniform, unambiguous, fixed-shape grammar. The steps in the correlation function, and hence in the loss, come from these assumptions, which real text does not satisfy (§6); context-sensitive structure is out of scope.
• Two printing slips. The exponent α in Eq. 13 has the wrong sign as printed, and §3 says Fig. 1 uses L = 4 where the caption says L = 3.

Open questions

• A proof that gradient descent on a deep network learns the masked token of RHM data from about P_ℓ examples, or one with weight sharing at m
• With non-uniform (Zipfian) production probabilities, whether the steps smooth into the power law the conjecture assumes, and what sets β.
• The spectrum of a word–context co-occurrence matrix generated by the RHM, or by a grammar whose symbols carry attributes: whether its leading eigenvectors are tree wavelets of the hidden hierarchy, and whether any ancestor has a linear direction. That is the form in which this model would answer QUESTION-025.
• On real text at word level, whether the context at which the loss saturates still scales as P^(1/(2β)) with β from word correlations.