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

• URL: http://arxiv.org/abs/2602.06065v2
• Date: Mon, 09 Feb 2026 13:02:07 GMT
• Title: Deep networks learn to parse uniform-depth context-free languages from local statistics
• Authors: Jack T. Parley, Francesco Cagnetta, Matthieu Wyart,
• Abstract summary: Understanding how the structure of language can be learned from sentences alone is a central question in both cognitive science and machine learning.<n>We introduce a class of context-free grammars (PCFGs) in which both the degree of ambiguity and the correlation structure across scales can be controlled.<n>We propose a unifying framework where correlations at different scales lift local ambiguities, enabling the emergence of hierarchical representations of the data.
• Score: 12.183764229746926
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• On the Emergence and Test-Time Use of Structural Information in Large Language Models [52.28603345019514]
  We study how language models learn abstract structures and utilize the learnt structural information at test-time.<n>We empirically show that the emergence of learning structural information correlates with complex reasoning tasks.
  arXiv  Detail & Related papers  (2026-01-25T15:02:25Z)
• Question-Driven Analysis and Synthesis: Building Interpretable Thematic Trees with LLMs for Text Clustering and Controllable Generation [1.3750624267664158]
  We introduce Recursive Thematic Partitioning (RTP) to interactively build a binary tree.<n>Each node in the tree is a natural language question that semantically partitions the data, resulting in a fully interpretable taxonomy.<n>We show that RTP's question-driven hierarchy is more interpretable than the keyword-based topics from a strong baseline like BERTopic.
  arXiv  Detail & Related papers  (2025-09-26T11:27:22Z)
• Probability Signature: Bridging Data Semantics and Embedding Structure in Language Models [8.87728727154868]
  We propose a set of probability signatures that reflect the semantic relationships among tokens.<n>We generalize our work to large language models (LLMs) by training the Qwen2.5 architecture on the subsets of the Pile corpus.
  arXiv  Detail & Related papers  (2025-09-24T13:49:44Z)
• Scaling Laws and Representation Learning in Simple Hierarchical Languages: Transformers vs. Convolutional Architectures [49.19753720526998]
  We derive theoretical scaling laws for neural network performance on synthetic datasets.<n>We validate that convolutional networks, whose structure aligns with that of the generative process through locality and weight sharing, enjoy a faster scaling of performance.<n>This finding clarifies the architectural biases underlying neural scaling laws and highlights how representation learning is shaped by the interaction between model architecture and the statistical properties of data.
  arXiv  Detail & Related papers  (2025-05-11T17:44:14Z)
• Towards a theory of how the structure of language is acquired by deep neural networks [6.363756171493383]
  We use a tree-like generative model that captures many of the hierarchical structures found in natural languages. We show that token-token correlations can be used to build a representation of the grammar's hidden variables. We conjecture that the relationship between training set size and effective range of correlations holds beyond our synthetic datasets.
  arXiv  Detail & Related papers  (2024-05-28T17:01:22Z)
• Explaining Text Similarity in Transformer Models [52.571158418102584]
  Recent advances in explainable AI have made it possible to mitigate limitations by leveraging improved explanations for Transformers. We use BiLRP, an extension developed for computing second-order explanations in bilinear similarity models, to investigate which feature interactions drive similarity in NLP models. Our findings contribute to a deeper understanding of different semantic similarity tasks and models, highlighting how novel explainable AI methods enable in-depth analyses and corpus-level insights.
  arXiv  Detail & Related papers  (2024-05-10T17:11:31Z)
• Physics of Language Models: Part 1, Learning Hierarchical Language Structures [51.68385617116854]
  Transformer-based language models are effective but complex, and understanding their inner workings and reasoning mechanisms is a significant challenge.<n>We introduce a family of synthetic CFGs that produce hierarchical rules, capable of generating lengthy sentences.<n>We demonstrate that generative models like GPT can accurately learn and reason over CFG-defined hierarchies and generate sentences based on it.
  arXiv  Detail & Related papers  (2023-05-23T04:28:16Z)
• How Do Transformers Learn Topic Structure: Towards a Mechanistic Understanding [56.222097640468306]
  We provide mechanistic understanding of how transformers learn "semantic structure" We show, through a combination of mathematical analysis and experiments on Wikipedia data, that the embedding layer and the self-attention layer encode the topical structure.
  arXiv  Detail & Related papers  (2023-03-07T21:42:17Z)
• Prompting Language Models for Linguistic Structure [73.11488464916668]
  We present a structured prompting approach for linguistic structured prediction tasks. We evaluate this approach on part-of-speech tagging, named entity recognition, and sentence chunking. We find that while PLMs contain significant prior knowledge of task labels due to task leakage into the pretraining corpus, structured prompting can also retrieve linguistic structure with arbitrary labels.
  arXiv  Detail & Related papers  (2022-11-15T01:13:39Z)
• A Knowledge-Enhanced Adversarial Model for Cross-lingual Structured Sentiment Analysis [31.05169054736711]
  Cross-lingual structured sentiment analysis task aims to transfer the knowledge from source language to target one. We propose a Knowledge-Enhanced Adversarial Model (textttKEAM) with both implicit distributed and explicit structural knowledge. We conduct experiments on five datasets and compare textttKEAM with both the supervised and unsupervised methods.
  arXiv  Detail & Related papers  (2022-05-31T03:07:51Z)
• Systematic Generalization on gSCAN with Language Conditioned Embedding [19.39687991647301]
  Systematic Generalization refers to a learning algorithm's ability to extrapolate learned behavior to unseen situations. We propose a novel method that learns objects' contextualized embeddings with dynamic message passing conditioned on the input natural language.
  arXiv  Detail & Related papers  (2020-09-11T17:35:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.