An expressivity analysis of hierarchical modelling in deep transformers via bounded-depth grammars
For the machine learning theory community, it offers a rigorous theoretical framework linking transformer depth to hierarchical representation, though limited to non-recursive grammars.
The paper provides a theoretical analysis of how deep transformers represent hierarchical structures, constructing transformers for bounded-depth grammars with depth linear in grammar depth and neuron count scaling with derivation-tree shapes and production rules, supporting the linear representation hypothesis.
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.