💬 NLP

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

This paper provides a theoretical analysis demonstrating that deep transformers possess the structural capacity to encode abstract grammatical states from bounded-depth context-free grammars into low-dimensional, linearly separable subspaces, thereby validating the linear representation hypothesis for hierarchical modeling.

Original authors: Vinoth Nandakumar, Qiang Qu, Pramod Thebe, Sakshi Khachariya, Tongliang Liu

Published 2026-06-17

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Vinoth Nandakumar, Qiang Qu, Pramod Thebe, Sakshi Khachariya, Tongliang Liu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot how to understand the complex, nested structure of human language. You know that sentences aren't just random strings of words; they are built like Russian nesting dolls or a family tree, where small groups of words form phrases, phrases form clauses, and clauses form sentences.

This paper asks a fundamental question: How does a deep neural network (specifically a "Transformer," the brain behind modern AI) actually build these mental trees?

While we know these models are good at it, we didn't have a clear mathematical proof of how they manage to do it without getting overwhelmed. This paper provides that proof by building a "theoretical robot" that can perfectly understand a specific type of language puzzle.

Here is the breakdown of their discovery using simple analogies:

1. The Problem: The "Infinite" vs. The "Bounded"

Language is theoretically infinite. You can keep nesting sentences inside sentences forever (e.g., "The cat that the dog that the man..."). However, human brains have limits; we can only hold so many layers of nesting in our working memory at once.

The researchers decided to simplify the problem. Instead of trying to model infinite recursion, they looked at bounded-depth grammars. Think of this as a language where every sentence is guaranteed to be exactly 3 or 4 layers deep, no more. It's like building a house with a strict rule: "Every house must have exactly 3 floors." This makes the structure predictable and easier to analyze mathematically.

2. The Solution: The "Layered Assembly Line"

The authors constructed a specific type of Transformer model to prove it can solve these puzzles. They didn't just say "it works"; they built the machine part-by-part to show exactly how it functions.

They compared the Transformer's layers to an assembly line or a construction crew:

The Input: Imagine a pile of raw bricks (words).
The Layers: The Transformer has many layers stacked on top of each other.
- Layer 1 looks at the bricks and glues them together to form small walls (simple phrases).
- Layer 2 takes those walls and glues them together to form rooms (clauses).
- Layer 3 takes the rooms and assembles them into a full house (the sentence).
The Magic: The paper proves that if your language has a depth of $d$ (e.g., 3 floors), you only need a Transformer with $d$ layers to understand it perfectly. The depth of the model grows linearly with the complexity of the language. You don't need a massive, exponential explosion of layers; you just need one layer for every level of the hierarchy.

3. The "Attention" Mechanism: The Foreman's Clipboard

How does the model know which bricks to glue together? The paper describes the "Attention" mechanism (the part of the Transformer that decides what to focus on) as a Foreman with a clipboard.

In their construction, the Foreman doesn't look at the whole chaotic construction site at once. Instead, they have a specific, pre-programmed rule: "Only look at the bricks that belong to this specific group."

They ignore everything else.
They focus only on the immediate neighbors needed to build the next level up.
This is called sparse attention. It's like a spotlight that only shines on the specific workers who need to pass a brick to the person above them.

4. The "Linear Representation" Discovery

One of the most exciting claims in the paper is about where the model stores this information.

There is a theory in AI called the "Linear Representation Hypothesis." It suggests that complex ideas (like "this is a noun phrase") are stored in the model's brain as simple, straight lines in a high-dimensional space.

The authors proved this mathematically for their constructed model. They showed that:

The model creates a specific "folder" or subspace for every type of grammatical structure.
When the model is building a "noun phrase," it lights up a specific, simple line in its internal math.
When it moves to a "verb phrase," it lights up a different, distinct line.
These lines are orthogonal (like the X and Y axes on a graph), meaning they don't overlap or get confused.

This explains why "probing" (a technique where researchers poke the model to see what it knows) works so well. The model isn't hiding the grammar in a messy, tangled knot; it's neatly filing it away in straight, easy-to-read lines.

5. Why This Matters (According to the Paper)

The paper doesn't claim this will immediately cure diseases or build self-driving cars. Instead, it claims to solve a theoretical mystery:

It proves efficiency: It shows that Transformers don't need to be exponentially huge to understand complex grammar. They just need to be deep enough to match the depth of the language.
It validates the "Linear Hypothesis": It provides a rigorous mathematical proof that these models can organize complex rules into simple, linear structures, confirming what empirical experiments have been guessing for years.
It bridges the gap: It connects the abstract math of "Context-Free Grammars" (old-school linguistics) with the modern architecture of "Transformers" (modern AI), showing they are more compatible than we thought.

Summary Analogy

Imagine you are trying to teach a robot to fold a complex origami crane.

Old view: We thought the robot needed to memorize every single possible crane shape in existence, which would require a brain the size of a galaxy.
This paper's view: We proved that if you give the robot a step-by-step instruction manual (a grammar) where the crane has a fixed number of folds, the robot only needs a brain with a number of steps equal to the number of folds. Furthermore, the robot organizes these steps into neat, separate folders (linear subspaces) so it never gets confused about which fold comes next.

The paper essentially says: "We built a theoretical robot that proves deep learning models are naturally good at building hierarchical structures, and they do it by organizing information in a surprisingly simple, linear way."

Technical Summary: Expressivity Analysis of Hierarchical Modelling in Deep Transformers via Bounded-Depth Grammars

Problem Statement

Deep neural networks, particularly transformers, are empirically observed to derive expressive power from forming hierarchical representations, capturing abstract and compositional features across layers. In language modeling, early transformer layers capture local syntactic patterns while later layers encode complex clause-level dependencies. Despite this intuition shaping model design, there is a lack of rigorous theoretical work demonstrating how deep transformers represent such hierarchical structures.

Existing theoretical analyses often focus on restricted settings, such as Dyck languages (balanced brackets) or finite-state automata, which lack the complex branching structures of real-world grammars. Furthermore, while empirical studies (e.g., Allen-Zhu & Li, 2025; Saglam et al., 2025) support the "linear representation hypothesis"—showing that abstract grammatical states can be recovered via linear probes in residual streams—these works do not theoretically explain why transformer architectures possess the structural capacity to explicitly encode these complex structures into low-dimensional, linearly separable subspaces.

This paper addresses the gap by analyzing the expressiveness of deep transformer models through the formal lens of bounded-depth, non-recursive context-free grammars (CFGs). The goal is to provide an explicit construction of a transformer that can predictively model such grammars, thereby formalizing the mechanics of hierarchical compositionality.

Methodology

The authors formalize the problem using a specific class of CFGs with the following properties:

Fixed Depth ( $d$ ): Every derivation tree has a height exactly $d$ .
Non-Recursive: The grammars generate finite languages, avoiding unbounded nesting.
Uniformity: Production rules for a given non-terminal have the same length.
Bounded Parameters: The analysis considers the maximal rule count ( $M$ ), maximal branching factor ( $B$ ), and the number of valid derivation-tree shapes ( $c = |C(G)|$ ).

The authors construct a decoder-only transformer with a positional attention mechanism to model these grammars. The construction relies on three core components:

Sparse Attention Heads: The model utilizes a simplified relative positional attention mechanism where attention weights depend only on token positions, not content. This allows for "hard" attention that selects specific tokens based on their position in the derivation tree.
Hierarchical Processing: The transformer depth grows linearly with the grammar depth ( $d$ ). Each transformer block corresponds to a level in the grammatical hierarchy, processing constituents from the leaves (terminals) up to the root (start symbol).
Feedforward Memorization: Position-wise feedforward networks (FFNs) are constructed to act as discrete look-up tables. Using results on the memorization capacity of neural networks (Zhang et al., 2017), these layers map aggregated local syntactic contexts to parent non-terminal symbols.

The construction implements a bottom-up dynamic programming algorithm (similar to the CKY parser) where:

Attention Heads aggregate local syntactic contexts of child nodes to identify the boundaries of grammatical constituents.
FFNs encode the resulting parent non-terminal symbols into the residual stream, preserving lower-level states via residual connections.
Final Layers utilize stacked feedforward networks to compute valid next-word predictions based on the accumulated hierarchical states.

Key Contributions

Explicit Transformer Construction: The paper provides a constructive proof that a transformer with depth $d$ (linear in grammar depth) can predictively model uniform, non-recursive CFGs of depth $d$ .
Scalability Bounds: The authors derive specific bounds on the model size required:
- Depth: Grows linearly with the grammar depth ( $d$ ).
- Neuron Count: Scales linearly with the number of derivation-tree shapes ( $c$ ) and quadratically with the number of production rules ( $M$ ).
- Hidden Dimension: Scales with $c \cdot d$ .
Theoretical Support for Linear Representation: The construction demonstrates that the architecture possesses the structural capacity to encode abstract grammatical states into low-dimensional, linearly separable subspaces within the residual stream. Specifically, for a fixed derivation tree shape, parsing computations occur in distinct subspaces, allowing non-terminal symbols to be isolated via simple affine transformations.
Differentiation from Prior Work: Unlike previous bounds that scale with the maximal sentence length (which can be exponential in grammar depth), this construction scales with the grammar depth itself. This highlights the efficiency of hierarchical modeling over flat representations (like n-grams or finite-state automata, which would require exponential state spaces for deep CFGs).

Results

The main theoretical result (Theorem 4.1) establishes that for any $\epsilon > 0$ , there exists a transformer language model $f_T$ that predictively models the language $L(G)$ with error at most $\epsilon$ . The model consists of $d$ transformer blocks followed by $5d + 7$ feedforward layers.

Efficiency: The number of layers required is linear in the grammar depth, a significant improvement over constructions where layer count scales with sentence length.
Sparsity: The construction utilizes a sparse circuit where each input sequence is processed by a single attention head per block, aligning with empirical findings on sparse computational subgraphs in deep learning.
Linear Separability: The proof shows that non-terminal symbols at a given depth are mapped to vectors in a subspace of the corresponding residual stream, supporting the linear representation hypothesis. However, the authors note their construction uses a strictly orthogonal basis (distinct indicator neurons), whereas empirical models likely achieve this via dense superposition.

Significance and Limitations

Significance:
The paper offers a rigorous existence proof that deep transformers can explicitly represent hierarchical grammatical structures. It bridges the gap between empirical observations of linear representations and theoretical architecture capabilities. By formalizing how transformers can implement bottom-up dynamic programming, the work provides a theoretical foundation for why deeper architectures are effective at capturing complex linguistic structures without suffering from the "curse of dimensionality" associated with flat models.

Limitations:

Simplified Framework: The analysis is restricted to bounded-depth, non-recursive CFGs. It does not directly address recursive grammars or infinite languages, though the framework is noted as an abstraction for analyzing hierarchical compositionality.
Orthogonal vs. Superposition: The theoretical construction relies on an orthogonal basis space where each grammatical state has a dedicated neuron. This simplifies the proof but does not account for the "superposition" phenomenon observed in real-world models, where features are compressed into dense vectors. Understanding how standard training dynamics yield such compressed representations remains an open question.
Scalability to Real Corpora: The bounds depend on $c$ (the number of tree shapes), which can be large. While the framework formalizes the core mechanics, the authors acknowledge it does not yet yield tight bounds for complex real-world corpora like the Penn Treebank.

In conclusion, this work lays the groundwork for understanding the inner workings of transformer models through formal language theory, suggesting that the depth of the transformer naturally mirrors the depth of the grammatical hierarchy it models.