Search papers, labs, and topics across Lattice.
This paper rigorously analyzes the expressiveness of deep transformer models through the framework of bounded-depth, non-recursive context-free grammars, addressing a gap in understanding how these architectures capture hierarchical structures. By constructing transformers with positional attention that scale linearly with grammar depth, the authors demonstrate that these models can effectively encode complex grammatical states into low-dimensional subspaces. The findings substantiate the linear representation hypothesis, revealing that deep transformers possess the structural capacity to represent abstract features in a way that aligns with theoretical grammar constructs.
Deep transformers can encode complex grammatical structures in low-dimensional spaces, 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.
