Deep networks learn to parse uniform-depth context-free languages from local statistics

AI summary

Overview

Research area: Machine learning theory and statistical physics of learning, applied to the learnability of probabilistic context-free grammars (PCFGs) by deep neural networks. arXiv:2602.06065v4 [stat.ML], by Jack T. Parley (EPFL), Francesco Cagnetta (SISSA), and Matthieu Wyart (EPFL / Johns Hopkins University).

Technical level: Advanced. The paper combines grammatical inference, method-of-moments statistics, covariance decompositions, and sample-complexity analysis, with experiments on deep convolutional and transformer architectures.

Scope in one sentence: The paper introduces a tunable family of synthetic grammars with ambiguous, varying parse trees, derives a provably correct iterative rule-inference algorithm from low-order moments, predicts the sample complexity of learning to classify such sentences, and tests those predictions on deep networks.

What This Paper Is About

Understanding how language structure can be learned from raw sentences is a central question in both cognitive science and machine learning, and PCFGs offer a tractable testbed for it. Prior work either characterised parsing-like algorithms that trained networks appear to implement after the fact, or studied PCFGs with a fixed syntax in which parsing is unnecessary. This paper removes the fixed-tree assumption, builds grammars where a single string can have multiple parse trees, and asks whether deep networks can learn to parse them from a polynomial number of samples using only local statistics.

Key Contributions

1. A tunable class of grammars. The authors introduce the Varying-Tree Random Hierarchy Model, a layered PCFG in which production rules generate strings of different lengths (binary rules with frequency $m_2$ and ternary rules with frequency $m_3$ per symbol). Global ambiguity — the existence of multiple parse trees with different root labels for one sentence — is controlled by a crossover driven by the number of production rules, giving detailed control over the ambiguity level.

2. A learning mechanism with a predicted sample complexity. They give an inference algorithm, inspired by the structure of deep convolutional networks, that reconstructs the production rules level by level using only root-to-pair and root-to-triple covariances. The algorithm addresses the two obstacles that appear once the tree topology is free: unknown span boundaries and overlapping (ambiguous) rules. It predicts sample complexity that scales as a power law of the number of production rules and the vocabulary size.

3. Empirical validation across architectures. The predictions are tested empirically on deep convolutional and transformer-based architectures and, per the abstract, confirmed quantitatively.

4. A unifying picture. The framework describes learnability as the lifting of local ambiguities by correlations at different scales, which enables hierarchical representations of the data to emerge.

Main Findings

• Ambiguity is a controllable crossover, not an all-or-nothing property. Although the number of parse trees grows exponentially with sentence length, global ambiguity is governed by a crossover controlled by the number of production rules. Computed with the inside algorithm at $v = 16$ (a value representative of the finite $v$ used in experiments), the expected class entropy normalised by $\ln(v)$ rises with the fraction $f$ into a globally ambiguous regime where $H = \mathcal{O}(\ln v)$. This is set by a competition between the fraction of grammatical data and the number of tree topologies.

• Local ambiguity arises from branching-ratio mismatch. Rules are sampled without replacement, so any valid pair or triple can be produced by only one nonterminal. Ambiguity comes instead from the mixture of binary and ternary branching: a substring $(a,b,c)$ can be derived directly by a ternary rule with probability $p_3/m_3$, or by a binary rule $(z' \to ab)$ followed by an expansion starting with $c$, an event of overall probability $\mathcal{O}(p_2/(m_2 v))$. When these are comparable, the grammar is locally ambiguous.

• Binary rules are recoverable by thresholding and clustering. For the asymptotic regime $v \to \infty$, with $m_2 = f_2 v$ and $m_3 = f_3 v^2$, the root-to-pair covariance rows $u_{ab} = C_2^{(\ell)}((a,b),:)$ have norm above a threshold $\tau_2 = \gamma v^{-1}(\sum_{a,b}|u_{ab}|_2^2)^{1/2}$ exactly for valid binary sibling pairs, and the normalised rows cluster according to their parent nonterminal. This gives Proposition 3.1: the procedure recovers the level-$\ell$ binary rules up to permutation of parent labels.

• Ternary rules require subtracting spurious binary contributions. Even in the asymptotic limit, the ternary sibling signal competes with contributions where two of the three tokens form binary siblings. The corrected quantity $w_{abc} = C_3^{(\ell)}((a,b,c),:) - \frac{1}{v}C_2^{(\ell)}((a,b),:) - \frac{1}{v}C_2^{(\ell)}((b,c),:)$ restores separation, and an alignment score against the binary centroids identifies ternary rules above a threshold $\tau_3$ (Proposition 3.2).

• Spurious nonterminals do not block iteration. Candidate nonterminal indicators built from inferred rules can be false positives with probability approximately $f$, but their covariance contributions are negligible in the asymptotic vocabulary-size limit, so the inference procedure can be iterated from level to level.

• Sample complexity is a power law. Proposition 3.3 gives the number of samples needed to estimate covariance rows accurately: $P_{2,\ell} = (p_2^2/2)^{1-\ell} v, m_2, m_2^{\ell-1}$ for pairs and $P_{3,\ell} = (p_2^2/2)^{1-\ell} v, m_3, m_2^{\ell-1}$ for triples. The errors obey a vector Bernstein bound, $E_s \le \gamma_s(\sqrt{\log(2/\delta)/(v m_s P)} + \log(2/\delta)/P)$. Conjecture 3.4 transfers these scales to deep networks, $P_{\ell,s} \asymp (p_2^2/2)^{1-\ell} v, m_s, m_2^{\ell-1}$ for $s = 2,3$.

• Root classification performance implies parsing performance. The authors state that strategies which do not rebuild the latent tree cannot achieve polynomial sample complexity, as shown for the simpler fixed-tree Random Hierarchy Model in earlier work (Cagnetta et al., 2024).

• Regimes probed. In numerical analyses the authors set $f_2 = f_3 = f$ as a single ambiguity control parameter and $p_2 = p_3 = 1/2$; the class-entropy plot indicates three regimes of $f$ at which the sample complexity of deep networks is measured. The specific measured sample-complexity exponents of the neural networks are not reported in the available text.

Methodology in Plain English

The authors construct synthetic languages with a fixed depth $L$ and a vocabulary of $v$ symbols per layer. Each higher-level symbol is given some number of binary rules ($m_2$ of them) and ternary rules ($m_3$ of them), drawn uniformly without replacement from all possible pairs or triples of lower-level symbols. Because binary and ternary rules coexist, sentences have variable length in the interval $[2^L, 3^L]$, centred on the typical length $\langle s\rangle^L$ with $\langle s\rangle = 2p_2 + 3p_3$, and multiple tree topologies can produce the same length. This is what makes parsing necessary.

The learner sees only sentences paired with their root symbol and must predict that root. The authors show that the Bayes-optimal predictor requires the inside parsing algorithm, a dynamic program that fills a chart of inside probabilities for every span and nonterminal.

To ask whether this is learnable from limited data, they design an algorithm that never sees the rules. It computes how pairs and triples of adjacent tokens co-vary with the root label across the training set. Valid sibling pairs stand out by the size of these covariance vectors; grouping the surviving vectors by direction recovers which pairs belong to which parent, i.e. the binary rules. Triples are handled similarly, but the binary contribution must be subtracted first because overlapping binary rules contaminate the triple signal. Once rules at one layer are known, the algorithm builds indicators for candidate nonterminals at the layer below — noting that some candidates are spurious — and repeats upward. Finally, they use a signal-to-noise argument to compute how many sentences are needed before the relevant correlations rise above finite-sampling noise, and compare that prediction with what deep convolutional and transformer networks actually need.

Why This Matters

Impact on research. The work connects grammatical inference, the statistical physics of learning, and the empirical behaviour of large models. It shows that a specific class of PCFG is learnable from positive examples alone within polynomial sample complexity, in a "hard" setting where no parse trees are given — a setting where prior results offered either no finite-sample guarantees or showed the general optimisation to be NP hard (Cohen and Smith, 2012). It also offers a concrete, testable account of which data statistics — correlations between the root and adjacent token substrings, accumulated across scales — make hierarchical structure recoverable.

Potential real-world applications (not claimed in the paper, but suggested by the framework):

• Designing training curricula or data mixtures where the relevant multi-scale correlations are present at sufficient density to be learnable.
• Diagnosing why a given model fails on syntactically ambiguous input, such as garden-path sentences used in cognitive science (Frazier and Rayner, 1982).
• Setting principled data-size expectations for structure-sensitive tasks, since the analysis predicts scaling with vocabulary size and rule count rather than being free.
• Providing synthetic benchmarks with controllable ambiguity for evaluating whether architecturally different models parse, rather than relying on post-hoc probing.

Industry relevance. Practitioners deciding how much data a structure-sensitive capability needs, and architects choosing between convolutional and attention-based designs, can use the predicted scaling laws as a reference point. The ambiguity control parameter also offers a way to build graded evaluation sets rather than binary pass/fail syntactic tests.

Future Directions

• Extending the analysis from the root classification objective to next-token prediction, which the authors state they discuss in the conclusion as an implication of their findings.
• Determining whether the conjecture for deep networks — that they attain the same sample-complexity scales as the iterative moment-based algorithm — holds under relaxations of the grammar assumptions, which the authors say do not affect the theoretical approach.
• Understanding behaviour outside the asymptotic $v \to \infty$ regime, where finite-$v$ effects (as in the class-entropy crossover computed at $v = 16$) matter.
• Explaining how trained networks handle the spurious nonterminal candidates in practice, and whether spurious contributions remain negligible at realistic, non-asymptotic vocabulary sizes.

Target Audience

Researchers in learning theory and grammatical inference, statistical physicists studying deep learning, and machine learning scientists interested in how hierarchical structure is acquired from data. Familiarity with PCFGs, the inside/outside algorithm, and method-of-moments estimation makes the paper considerably easier to follow; readers interested primarily in applied natural language processing will find the synthetic setting and asymptotic analysis abstract, though the empirical tests on convolutional and transformer architectures are directly relevant to them.

Authors’ abstract

Understanding how the structure of language can be learned from sentences alone is a central question in both cognitive science and machine learning. Studies of the internal representations of Large Language Models (LLMs) support their ability to parse text when predicting the next word, while representing semantic notions independently of surface form. Yet, which data statistics make these feats possible, and how much data is required, remain largely unknown. Probabilistic context-free grammars (PCFGs) provide a tractable testbed for studying these questions. However, prior work has focused either on the post-hoc characterization of the parsing-like algorithms used by trained networks; or on the learnability of PCFGs with fixed syntax, where parsing is unnecessary. Here, we (i) introduce a tunable class of PCFGs in which both the degree of ambiguity and the correlation structure across scales can be controlled; (ii) provide a learning mechanism -- an inference algorithm inspired by the structure of deep convolutional networks -- that links learnability and sample complexity to specific language statistics; and (iii) validate our predictions empirically across deep convolutional and transformer-based architectures. Overall, we propose a unifying framework where correlations at different scales lift local ambiguities, enabling the emergence of hierarchical representations of the data.