An expressivity analysis of hierarchical modelling in deep transformers via bounded-depth grammars

• URL: http://arxiv.org/abs/2606.17522v1
• Date: Tue, 16 Jun 2026 05:02:13 GMT
• Title: An expressivity analysis of hierarchical modelling in deep transformers via bounded-depth grammars
• Abstract summary: Deep neural networks are widely believed to derive their expressive power from their ability to form textbfhierarchical representations<n>In language modeling, textbftransformers have emerged as the dominant architecture, with early layers capturing local syntactic patterns and later layers encoding more complex clause-level dependencies.<n>We argue that these architectures possess the structural capacity to encode abstract grammatical states into low-dimensional, linearly separable subspaces within the residual stream.
• Score: 54.11540943172608
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Deep neural networks are widely believed to derive their expressive power from their ability to form \textbf{hierarchical representations}, capturing progressively more abstract and compositional features across layers. In language modeling, \textbf{transformers} have emerged as the dominant architecture, with early layers capturing local syntactic patterns and later layers encoding more complex clause-level dependencies. While this intuition has shaped model design, there remains a lack of rigorous theoretical work demonstrating \textbf{how} deep transformers represent such hierarchical structures. In this work, we analyze the expressiveness of deep transformer models through the formal lens of bounded-depth, non-recursive context-free grammars. For this class of grammars, we explicitly construct transformers with positional attention whose depth grows linearly with grammar depth, while the neuron count scales with the number of derivation-tree shapes and quadratically with the number of production rules. Our theoretical results support the linear representation hypothesis by demonstrating that these architectures possess the structural capacity to encode abstract grammatical states into low-dimensional, linearly separable subspaces within the residual stream.

Related papers

• On the Expressive Power of Transformers for Maxout Networks and Continuous Piecewise Linear Functions [8.192218166714422]
  Transformer networks have achieved remarkable empirical success across a wide range of applications, yet their theoretical expressive power remains insufficiently understood.<n>We first establish an explicit approximation of maxout networks by Transformer networks while preserving comparable model complexity.<n>As a consequence, Transformers inherit the universal approximation capability of ReLU networks under similar complexity constraints.
  arXiv  Detail & Related papers  (2026-03-03T15:27:15Z)
• Explicit Grammar Semantic Feature Fusion for Robust Text Classification [0.0]
  Natural Language Processing enables computers to understand human language by analysing and classifying text efficiently.<n>Existing models capture features by learning from large corpora with transformer models, which are computationally intensive and unsuitable for resource-constrained environments.<n>Our proposed study incorporates comprehensive grammatical rules alongside semantic information to build a robust, lightweight classification model.
  arXiv  Detail & Related papers  (2026-02-24T10:25:29Z)
• Hierarchical Latent Structures in Data Generation Process Unify Mechanistic Phenomena across Scale [50.33952894976367]
  We use context-free grammars to generate synthetic corpora that are faithful and computationally efficient proxies for web-scale text corpora.<n>We investigate the emergence of three mechanistic phenomena: induction heads, function vectors, and the Hydra effect, under our designed data generation process.<n>Our findings suggest that hierarchical structures in the data generation process serve as the X-factor in explaining the emergence of these phenomena.
  arXiv  Detail & Related papers  (2026-02-04T14:49:13Z)
• 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)
• How much do contextualized representations encode long-range context? [10.188367784207049]
  We analyze contextual representations in neural autoregressive language models, emphasizing long-range contexts that span several thousand tokens. Our methodology employs a perturbation setup and the metric emphAnisotropy-Calibrated Cosine Similarity, to capture the degree of contextualization of long-range patterns from the perspective of representation geometry.
  arXiv  Detail & Related papers  (2024-10-16T06:49:54Z)
• Learning Syntax Without Planting Trees: Understanding Hierarchical Generalization in Transformers [74.96551626420188]
  Transformers trained on natural language data have been shown to learn its hierarchical structure and generalize to sentences with unseen syntactic structures.<n>We investigate sources of inductive bias in transformer models and their training that could cause such generalization behavior to emerge.
  arXiv  Detail & Related papers  (2024-04-25T07:10:29Z)
• Grokking of Hierarchical Structure in Vanilla Transformers [72.45375959893218]
  We show that transformer language models can learn to generalize hierarchically after training for extremely long periods. intermediate-depth models generalize better than both very deep and very shallow transformers.
  arXiv  Detail & Related papers  (2023-05-30T04:34:13Z)
• Model Criticism for Long-Form Text Generation [113.13900836015122]
  We apply a statistical tool, model criticism in latent space, to evaluate the high-level structure of generated text. We perform experiments on three representative aspects of high-level discourse -- coherence, coreference, and topicality. We find that transformer-based language models are able to capture topical structures but have a harder time maintaining structural coherence or modeling coreference.
  arXiv  Detail & Related papers  (2022-10-16T04:35:58Z)
• Transformer Grammars: Augmenting Transformer Language Models with Syntactic Inductive Biases at Scale [31.293175512404172]
  We introduce Transformer Grammars -- a class of Transformer language models that combine expressive power, scalability, and strong performance of Transformers. We find that Transformer Grammars outperform various strong baselines on multiple syntax-sensitive language modeling evaluation metrics.
  arXiv  Detail & Related papers  (2022-03-01T17:22:31Z)

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.