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

# An expressivity analysis of hierarchical modelling in deep transformers via bounded-depth grammars.
Source: [https://arxiv.org/html/2606.17522](https://arxiv.org/html/2606.17522)
Vinoth Nandakumarvinoth\.90@gmail\.com University of SydneyQiang Quvincent\.qu@sydney\.edu\.au University of SydneyPramod Thebepramodthebe@gmail\.com San Francisco State UniversitySakshi Khachariyapatelsakshi9110@gmail\.com IIT MadrasTongliang Liutongliang\.liu@sydney\.edu\.au University of Sydney

###### Abstract

Deep neural networks are widely believed to derive their expressive power from their ability to formhierarchical representations, capturing progressively more abstract and compositional features across layers\. In language modeling,transformershave 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 demonstratinghowdeep 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\.

## 1Introduction

Over the past two decades, breakthroughs in deep learning have revolutionized natural language processing tasks, such as language modeling \(Brownet al\.\([2020](https://arxiv.org/html/2606.17522#bib.bib2)\); Devlinet al\.\([2019](https://arxiv.org/html/2606.17522#bib.bib15)\); Hoffmannet al\.\([2022](https://arxiv.org/html/2606.17522#bib.bib27)\)\), question\-answering \(Lanet al\.\([2020](https://arxiv.org/html/2606.17522#bib.bib30)\); Beltagyet al\.\([2020](https://arxiv.org/html/2606.17522#bib.bib6)\); Zaheeret al\.\([2020](https://arxiv.org/html/2606.17522#bib.bib63)\)\), and machine translation \(Vaswaniet al\.\([2017](https://arxiv.org/html/2606.17522#bib.bib57)\); Costa\-Jussàet al\.\([2022](https://arxiv.org/html/2606.17522#bib.bib14)\); Fanet al\.\([2020](https://arxiv.org/html/2606.17522#bib.bib20)\)\)\. While rule\-based methods were widely used for next\-word prediction before deep learning, neural language models have since consistently demonstrated superior performance on complex tasks \(Bengioet al\.\([2003](https://arxiv.org/html/2606.17522#bib.bib7)\)\)\. Transformers, characterized by their self\-attention mechanisms, further advanced the field by enabling models to process entire sequences in parallel and dynamically focus on distant dependencies — capabilities that earlier recurrent or convolutional approaches struggled to achieve \(Devlinet al\.\([2019](https://arxiv.org/html/2606.17522#bib.bib15)\); Brownet al\.\([2020](https://arxiv.org/html/2606.17522#bib.bib2)\)\)\. Although larger models and novel architectures continue to yield empirical gains \(Raffelet al\.\([2020](https://arxiv.org/html/2606.17522#bib.bib46)\); Hoffmannet al\.\([2022](https://arxiv.org/html/2606.17522#bib.bib27)\)\), we still lack a firm theoretical understanding ofhow transformers capture the complex hierarchical structures of language so effectively\.

Natural language exhibits hierarchical structure, which can be represented by context\-free grammars: sentences are composed of phrases, which are composed of sub\-phrases or words \(Chomsky \([1957](https://arxiv.org/html/2606.17522#bib.bib17)\)\)\. While recursion allows the space of valid sentences to grow infinitely, human cognitive limits typically restrict parsing to bounded depths\. Hierarchical representations exploit this structure, allowing models to decompose sequences into smaller subsequences, dramatically reducing the number of parameters required \(Poggioet al\.\([2017](https://arxiv.org/html/2606.17522#bib.bib44)\)\)\. Although prior work has shown that deep networks can leverage such compositional structures \(Mossel \([2016](https://arxiv.org/html/2606.17522#bib.bib24)\)\), they have largely focused on restricted settings such as Dyck languages \(Hahn \([2020](https://arxiv.org/html/2606.17522#bib.bib23)\); Yaoet al\.\([2021](https://arxiv.org/html/2606.17522#bib.bib58)\)\) and finite state automata \(Liuet al\.\([2023](https://arxiv.org/html/2606.17522#bib.bib31)\)\), which lack the complex branching structures of real\-world grammars\.

Recent empirical studies show how transformers can internalize complex syntactic and semantic structures, offering strong support for thelinear representation hypothesis\. For instance,Saglamet al\.\([2025](https://arxiv.org/html/2606.17522#bib.bib48)\)demonstrates that large language models encode high\-level semantic domains into low\-dimensional, linearly separable subspaces, with this separability becoming distinctly more pronounced in the deeper layers of the network\. In parallel,Allen\-Zhu and Li \([2025](https://arxiv.org/html/2606.17522#bib.bib4)\)andZhaoet al\.\([2023](https://arxiv.org/html/2606.17522#bib.bib65)\)show that transformers trained on synthetic context\-free grammars \(CFGs\) can recover latent non\-terminal symbols through linear probes, further indicating that abstract hierarchical rules are encoded as linear directions in the residual stream\. While these works empirically validate the linear representation hypothesis, they do not theoretically explain why transformer architectures possess the structural capacity to explicitly represent these complex grammatical structures within low\-dimensional linear subspaces\.

Contributions\.To address these limitations, we analyze transformer language models through the formal framework of length\-uniform, non\-recursive context\-free grammars \(CFGs\) with a fixed depth, a setting that makes hierarchical relationships explicit \(Stroblet al\.\([2024](https://arxiv.org/html/2606.17522#bib.bib51)\); Ackerman and Cybenko \([2020](https://arxiv.org/html/2606.17522#bib.bib1)\)\)\. For this class of CFGs, we provide an*explicit*construction of a transformer architecture with a positional attention mechanism whose depth grows linearly with grammar depth, while the neuron count scales linearly withcc, the number of valid derivation\-tree shapes, and quadratically with the number of production rules\. We note that our simplified framework can be used to analyze hierarchical compositionality, as even with a restricted number of tree shapes, the underlying grammar can generate an exponentially large number of unique sentences\.

Our framework provides a rigorous existence proof compatible with the “linear representation hypothesis” in the context of hierarchical language modelling\. We formally prove that the architecture has the capacity to encode complex grammatical structures in low\-dimensional spaces, with any non\-terminal symbol at a given depth mapped to a vector in a subspace of the corresponding residual stream\. While empirical models achieve this through dense superposition \(Garget al\.\([2026](https://arxiv.org/html/2606.17522#bib.bib21)\); Saglamet al\.\([2025](https://arxiv.org/html/2606.17522#bib.bib48)\)\), our construction utilizes a simplified model with an orthogonal basis space\. We construct transformers that naturally implement the bottom\-up dynamic programming algorithm for parsing CFGs described inAllen\-Zhu and Li \([2025](https://arxiv.org/html/2606.17522#bib.bib4)\)\. Our proof relies on hard\-coded attention heads that aggregate local syntactic contexts, mirroring the tree\-building attention patterns empirically observed in trained models \(Allen\-Zhu and Li \([2025](https://arxiv.org/html/2606.17522#bib.bib4)\)\)\.

Organization of the paper\.Section 2 summarizes related work on hierarchical modeling and formal language theory\. Section 3 defines the class of CFGs we analyze \(with examples\) and formally states the problem setup for transformer models\. In Sections 4 and 5, we present our main expressiveness results, showing that deep transformers can solve next\-word prediction for context\-free grammars with a fixed depth, and outline a constructive proof describing the function of attention heads and feedforward layers\. In Section 6, we discuss limitations and further directions\. The Appendix provides detailed proofs of our theoretical results\.

## 2Related work

Hierarchical representations via deep learning\.A growing body of work has investigated the role of hierarchical representations in deep learning models\. It is well understood that deep networks can compactly represent hierarchical functions using exponentially fewer parameters than shallow networks \(Poggioet al\.\([2017](https://arxiv.org/html/2606.17522#bib.bib44)\); Zhaoet al\.\([2017](https://arxiv.org/html/2606.17522#bib.bib66)\)\)\. In certain settings, generative models grounded in hierarchical structure have been shown to be learnable via clustering\-based techniques\(Mossel \([2016](https://arxiv.org/html/2606.17522#bib.bib24)\); Malach and Shalev\-Shwartz \([2018](https://arxiv.org/html/2606.17522#bib.bib33);[2020](https://arxiv.org/html/2606.17522#bib.bib34)\)\)\. More recent work has demonstrated that deep networks trained via gradient descent can uncover these latent hierarchical structures implicitly \(Allen\-Zhu and Li \([2025](https://arxiv.org/html/2606.17522#bib.bib4)\); Tomasini and Wyart \([2024](https://arxiv.org/html/2606.17522#bib.bib56)\); Garnier\-Brunet al\.\([2025](https://arxiv.org/html/2606.17522#bib.bib22)\)\)\. We study how transformer models represent hierarchical structures through the mathematical framework of CFGs, a formalism well suited for modeling natural language\.

Modelling formal languages using transformers\.Several recent works have explored the computational capabilities of transformer models from the perspective of formal language theory\. It has been shown inPerezet al\.\([2021](https://arxiv.org/html/2606.17522#bib.bib43)\)that encoder\-decoder transformers can recognize all languages in the class𝖯\\mathsf\{P\}, i\.e\., those decidable by deterministic Turing machines in polynomial time\. This result, which has been refined inBhattamishraet al\.\([2020b](https://arxiv.org/html/2606.17522#bib.bib9)\); Merrill and Sabharwal \([2024](https://arxiv.org/html/2606.17522#bib.bib38)\)andSarrofet al\.\([2024](https://arxiv.org/html/2606.17522#bib.bib49)\); Yanget al\.\([2024](https://arxiv.org/html/2606.17522#bib.bib59)\), provides one of the few known characterizations of which formal languages can be modelled by transformer architectures\. Recent work has also investigated the ability of attention\-based models to recognize formal languages such as Dyckk, the language of well\-balanced brackets withkktypes \(Hahn \([2020](https://arxiv.org/html/2606.17522#bib.bib23)\); Yaoet al\.\([2021](https://arxiv.org/html/2606.17522#bib.bib58)\); Bhattamishraet al\.\([2020a](https://arxiv.org/html/2606.17522#bib.bib8)\)\), and whether transformers can recognize formal languages in the complexity class𝖠𝖢𝟢\\mathsf\{AC^\{0\}\}\(Haoet al\.\([2022](https://arxiv.org/html/2606.17522#bib.bib28)\); Barceloet al\.\([2024](https://arxiv.org/html/2606.17522#bib.bib5)\)\), which consists of languages recognizable by families of Boolean circuits of constant depth and polynomial size\. The present work is most closely related toZhaoet al\.\([2023](https://arxiv.org/html/2606.17522#bib.bib65)\), which shows that transformers can implement the inside\-outside parsing algorithm for CFGs, andLiuet al\.\([2023](https://arxiv.org/html/2606.17522#bib.bib31)\), which analyzes the depth expressiveness of transformers through the lens of finite\-state automata\. Building on these results, we establish a direct connection between the depth of the transformer and the depth of the underlying grammar, and obtain novel upper bounds on the size of a transformer required to represent certain classes of CFGs\.

## 3Problem set\-up

### 3\.1Preliminaries on language modelling

We begin by formalizing the language modelling task followingSarrofet al\.\([2024](https://arxiv.org/html/2606.17522#bib.bib49)\)\.

###### Definition 3\.1\.

ThevocabularyΣ\\Sigmais a finite set consisting of all words\. LetΣ∗\\Sigma^\{\*\}denote the set of all finite sequences consisting of words fromΣ\\Sigma\. Given a vocabularyΣ\\Sigma, alanguageℒ\\mathcal\{L\}is a subset ofΣ∗\\Sigma^\{\*\}; its elements are called sentences\.■\\blacksquare

###### Definition 3\.2\.

Given a vocabularyΣ\\Sigma, alanguage modelis a functionffthat takes in an arbitrary sequencew¯∈Σ∗\\underline\{w\}\\in\\Sigma^\{\*\}, and outputs a vector of probabilitiesf​\(w¯\)=\(f^​\(w\|w¯\)\)w∈Σf\(\\underline\{w\}\)=\(\\hat\{f\}\(w\|\\underline\{w\}\)\)\_\{w\\in\\Sigma\}\. Heref^​\(w\|w¯\)\\hat\{f\}\(w\|\\underline\{w\}\)denotes the probability that the modelffwill output the wordwwgiven the input sequencew¯\\underline\{w\}\.■\\blacksquare

Many theoretical papers study the recognition problem \(Bhattamishraet al\.\([2020a](https://arxiv.org/html/2606.17522#bib.bib8)\)\), where the language model must determine whether or not a complete string belongs to a given language\. However, recent empirical work in language modelling has focused on next\-word prediction\. We focus on the predictive modelling problem, and define what it means forffto model a given languageℒ\\mathcal\{L\}\(note that the recognition problem can be obtained as a special case of predictive modelling; see Section 3\.2 ofSarrofet al\.\([2024](https://arxiv.org/html/2606.17522#bib.bib49)\)\)\.

###### Definition 3\.3\.

Given a vocabularyΣ\\Sigmaand a languageℒ⊆Σ∗\\mathcal\{L\}\\subseteq\\Sigma^\{\*\}, the set ofvalid prefixesofℒ\\mathcal\{L\}, denotedPrefix​\(ℒ\)\\text\{Prefix\}\(\\mathcal\{L\}\), is defined as follows\.

Prefix​\(ℒ\):=\{w¯∈Σ∗:∃w¯′∈Σ∗,w¯⋅w¯′∈ℒ\}\\text\{Prefix\}\(\\mathcal\{L\}\):=\\\{\\underline\{w\}\\in\\Sigma^\{\*\}:\\exists\\underline\{w\}^\{\\prime\}\\in\\Sigma^\{\*\},\\;\\underline\{w\}\\cdot\\underline\{w\}^\{\\prime\}\\in\\mathcal\{L\}\\\}For a given valid prefixw¯∈Prefix​\(ℒ\)\\underline\{w\}\\in\\text\{Prefix\}\(\\mathcal\{L\}\), we defineS​\(w¯\)S\(\\underline\{w\}\), the set of all words inΣ\\Sigmathat can follow the sequencew¯\\underline\{w\}in a sentence fromℒ\\mathcal\{L\}, as follows\.

S​\(w¯\):=\{w∈Σ:w¯⋅w∈Prefix​\(ℒ\)\}■S\(\\underline\{w\}\):=\\\{w\\in\\Sigma:\\underline\{w\}\\cdot w\\in\\text\{Prefix\}\(\\mathcal\{L\}\)\\\}\\qquad\\blacksquare

###### Definition 3\.4\(Predictive modelling\)\.

Letℒ⊆Σ∗\\mathcal\{L\}\\subseteq\\Sigma^\{\*\}be a language, and letffbe a language model as in Definition[3\.2](https://arxiv.org/html/2606.17522#S3.Thmtheorem2)\. Forϵ≥0\\epsilon\\geq 0, we say thatff*predictively models*ℒ\\mathcal\{L\}with error at mostϵ\\epsilonif, for every valid prefixw¯∈Prefix​\(ℒ\)\\underline\{w\}\\in\\mathrm\{Prefix\}\(\\mathcal\{L\}\),

∑w∉S​\(w¯\)f^​\(w∣w¯\)≤ϵ■\\sum\_\{w\\notin S\(\\underline\{w\}\)\}\\hat\{f\}\(w\\mid\\underline\{w\}\)\\;\\leq\\;\\epsilon\\qquad\\blacksquare

### 3\.2Context\-free grammars

Table 1:A Depth\-3 CFG that can be used to generate the two derivation trees below\.\{forest\}

\{forest\}

Figure 1:Two derivation trees with different shapes\. All nodes have degree 2 or 3\.Context\-free grammars \(CFGs\) are a foundational class of formal grammars used to model the syntax of natural language\. A CFG consists of a finite set of production rules that describe how strings in a language can be generated from a designated start symbol\. Each rule specifies how a single non\-terminal symbol can be replaced by a sequence of terminal and/or non\-terminal symbols, allowing for recursive and nested derivations\. Unlike regular grammars, CFGs can represent hierarchical and nested structures present in annotated corpora such as Penn Treebank \(Charniak \([1996](https://arxiv.org/html/2606.17522#bib.bib11)\)\), where the production rules can be obtained from the parse trees in the corpus \(see alsoNederhof and Vogler \([2012](https://arxiv.org/html/2606.17522#bib.bib41)\); Kolleret al\.\([2008](https://arxiv.org/html/2606.17522#bib.bib25)\)\)\. Below, we formally define a CFG followingAllen\-Zhu and Li \([2025](https://arxiv.org/html/2606.17522#bib.bib4)\)\.

###### Definition 3\.5\.

Acontext\-free grammar𝒢\\mathcal\{G\}consists of the following components\(Σ,N,P,S\)\(\\Sigma,N,P,S\):

- •Σ\\Sigmais a finite set of terminal symbols \(the alphabet of the language\)\.
- •NNis a finite set of non\-terminal symbols, which is disjoint fromΣ\\Sigma\. One distinguished symbolS∈NS\\in Nis called thestart symbol\.
- •PPis a finite set of production rules\. Each rule is of the formA→βA\\rightarrow\\beta, whereA∈NA\\in Nis a single non\-terminal symbol, andβ\\betais composed of symbols fromN∪ΣN\\cup\\Sigma\.

Given a context\-free grammar𝒢\\mathcal\{G\}, the languageℒ​\(𝒢\)\\mathcal\{L\}\(\\mathcal\{G\}\)generated by the grammar is defined as follows:

- •Aderivation treeis a hierarchical structure obtained by recursively applying production rules that start with the root node labeled with the start symbolSS\. Internal nodes are labeled by non\-terminal symbols and are expanded according to rules inPP, and all leaf nodes correspond to terminal symbols\.
- •The setℒ​\(𝒢\)\\mathcal\{L\}\(\\mathcal\{G\}\)consists of all sequences of terminal symbols obtained by reading the leaves of a derivation tree from left to right\.■\\blacksquare

Following Section 2 ofAllen\-Zhu and Li \([2025](https://arxiv.org/html/2606.17522#bib.bib4)\), we consider CFGs with a fixed depthdd, where every derivation tree generated by the grammar has height exactlydd\. This constraint naturally induces a hierarchical structure withddlevels of composition, making such grammars a useful abstraction for analyzing how deep language models, such as transformers, can represent compositional structure across multiple layers\. This framework can also be extended to grammars where root\-to\-leaf paths have length at mostdd, by inserting duplicate copies of a non\-terminal along shorter branches so that every path is extended to length exactlydd\.

###### Definition 3\.6\.

We say that the CFG𝒢\\mathcal\{G\}hasdepthddif every derivation tree generated by𝒢\\mathcal\{G\}satisfies the following property: for every root\-to\-leaf path, the path length \(i\.e\., the number of edges from the root node to a leaf node\) is exactlydd\. LetNiN\_\{i\}denote the set of symbols that appear at leveliiof any derivation tree, starting from the bottom \(in particular, letN1=ΣN\_\{1\}=\\Sigmabe the set of terminal symbols, andNd\+1=\{S\}N\_\{d\+1\}=\\\{S\\\}consist of the start symbol\)\.

###### Definition 3\.7\.

Let𝒢=\(Σ,N,P,S\)\\mathcal\{G\}=\(\\Sigma,N,P,S\)be a CFG\. Ifℒ​\(𝒢\)⊆Σ∗\\mathcal\{L\}\(\\mathcal\{G\}\)\\subseteq\\Sigma^\{\*\}is the generated language, let

L=max⁡\{\|w\|:w∈ℒ​\(𝒢\)\},L\\;=\\;\\max\\\{\\;\|w\|\\;:\\;w\\in\\mathcal\{L\}\(\\mathcal\{G\}\)\\\},be the*maximal sentence length*\. For each non\-terminalA∈NA\\in N, define its*degree*

deg⁡\(A\)=max\(A→β\)∈P⁡\|β\|,\\deg\(A\)\\;=\\;\\max\_\{\(A\\to\\beta\)\\,\\in\\,P\}\\;\|\\beta\|,where\|β\|\|\\beta\|is the number of symbols on the right\-hand side of the production\. We say that𝒢\\mathcal\{G\}is*uniform*if for every non\-terminalA∈NA\\in N, all of its production rules have the same lengthdeg⁡\(A\)\\deg\(A\)\. We say that𝒢\\mathcal\{G\}hasmaximal rule countMMif the following holds: for each depthii\(2≤i≤d2\\leq i\\leq d\), there are at mostMMdistinct production rules where the non\-terminal symbol on the left is inNiN\_\{i\}\. We define themaximal branching factorBBas the largest number of symbols that can appear on the right\-hand side of any production rule\.

###### Definition 3\.8\.

Let𝒢\\mathcal\{G\}be a CFG, and letTTbe a derivation tree for𝒢\\mathcal\{G\}\. The*shape*ofTT, denotedshape​\(T\)\\mathrm\{shape\}\(T\), is the ordered, unlabeled rooted tree obtained by forgetting all non\-terminal symbol labels inTTwhile retaining the parent–child relations and the left\-to\-right order of siblings\. Two derivation treesT1T\_\{1\}andT2T\_\{2\}are said to have the same shape precisely when there exists an isomorphism of ordered unlabeled trees betweenshape​\(T1\)\\mathrm\{shape\}\(T\_\{1\}\)andshape​\(T2\)\\mathrm\{shape\}\(T\_\{2\}\)\. We denote by𝒞​\(𝒢\)\\mathcal\{C\}\(\\mathcal\{G\}\)the set of all possible shapes of derivation trees in𝒢\\mathcal\{G\}\.

While our main theorem explicitly assumes derivation trees of a fixed depthdd, this framework naturally extends to context\-free grammars with a bounded depth less than or equal todd\. This is done by augmenting the original grammar with duplicate non\-terminal symbols to pad any prematurely terminating derivation branches\. Specifically, if a valid derivation path yields a sequence at a shallower depth, we can introduce a chain of duplicate non\-terminals converting that derivation tree into an equivalent fixed\-depth tree\.

It is important to note that our theoretical framework analyzes context\-free grammars with bounded depth, and excludes recursive CFGs\. A recursive CFG allows for unbounded nesting, where a non\-terminal symbol can be expanded to a sequence containing itself \(e\.g\.,A⇒∗α​A​βA\\Rightarrow^\{\*\}\\alpha A\\beta\), thereby generating derivation trees of unbounded depth\. However, natural language rarely exhibits deep recursive nesting due to limitations on human working memory, and our bounded\-depth assumption is a realistic constraint for modeling natural language\.

### 3\.3Transformer models

We assume familiarity with the transformer architecture introduced inVaswaniet al\.\([2017](https://arxiv.org/html/2606.17522#bib.bib57)\), and definitions are presented below for clarity\. A*transformer block*first applies multi\-head self\-attention, followed by a position\-wise feedforward neural network, wrapping each sub\-block in residual connections\. A*transformer model*is obtained by composing transformer blocks and optionally appending a feedforward network with one or more fully connected layers before the output head, motivated by recent work inPresset al\.\([2020](https://arxiv.org/html/2606.17522#bib.bib45)\)showing that reordering and stacking multiple feedforward layers can enhance the representational capacity of transformers\. We also use a relative positional attention mechanism defined below using the random synthesizer construction in Section 3\.1 ofTayet al\.\([2020](https://arxiv.org/html/2606.17522#bib.bib55)\), where the attention weights depend only on the position of the tokens and not their content \(see alsoShawet al\.\([2018](https://arxiv.org/html/2606.17522#bib.bib50)\)\)\.

###### Definition 3\.9\(Multi\-Head Attention with Relative Positional Weights\)\.

LetX∈ℝn×dX\\in\\mathbb\{R\}^\{n\\times d\}be the input sequence consisting ofnnvectors inℝd\\mathbb\{R\}^\{d\}\. Fix a maximum sequence lengthLmax≥nL\_\{\\max\}\\geq n\. For each headh=1,…,Hh=1,\\dots,H, we learn

Rh∈ℝLmax×Lmax,Wh\(V\)∈ℝd×dV,R\_\{h\}\\in\\mathbb\{R\}^\{L\_\{\\max\}\\times L\_\{\\max\}\},\\qquad W\_\{h\}^\{\(V\)\}\\in\\mathbb\{R\}^\{d\\times d\_\{V\}\},where the relative positional matrixRhR\_\{h\}is lower triangular and assigns a scalar weight to each ordered pair of positions in\{1,…,Lmax\}\\\{1,\\dots,L\_\{\\max\}\\\}\. LettingRh\[1:n,1:n\]R\_\{h\}^\{\[1:n,1:n\]\}be the sliced positional matrix, we compute the value matrixVh=X​Wh\(V\)∈ℝn×dVV\_\{h\}=XW\_\{h\}^\{\(V\)\}\\in\\mathbb\{R\}^\{n\\times d\_\{V\}\}and the head output

headh=Rh\[1:n,1:n\]​Vh∈ℝn×dV\.\\text\{head\}\_\{h\}\\;=\\;R\_\{h\}^\{\[1:n,1:n\]\}\\,V\_\{h\}\\;\\in\\;\\mathbb\{R\}^\{n\\times d\_\{V\}\}\.The multi\-head output is

MHA​\(X\)=Concat​\(head1,…,headH\)​W\(O\),\\mathrm\{MHA\}\(X\)\\;=\\;\\mathrm\{Concat\}\(\\text\{head\}\_\{1\},\\dots,\\text\{head\}\_\{H\}\)\\,W^\{\(O\)\},whereW\(O\)∈ℝH​dV×dW^\{\(O\)\}\\in\\mathbb\{R\}^\{Hd\_\{V\}\\times d\}is an output projection\.■\\blacksquare

###### Definition 3\.10\.

A position\-wise feedforward network \(FFN\) with input/output widthddand hidden widthdffd\_\{\\mathrm\{ff\}\}is the function

FF:ℝd→ℝd,x↦W\(2\)​σ​\(W\(1\)​x\+b\(1\)\)\+b\(2\),\\mathrm\{FF\}:\\mathbb\{R\}^\{d\}\\to\\mathbb\{R\}^\{d\},\\qquad x\\mapsto W^\{\(2\)\}\\sigma\(W^\{\(1\)\}x\+b^\{\(1\)\}\)\+b^\{\(2\)\},withW\(1\)∈ℝdff×dW^\{\(1\)\}\\in\\mathbb\{R\}^\{d\_\{\\mathrm\{ff\}\}\\times d\},b\(1\)∈ℝdffb^\{\(1\)\}\\in\\mathbb\{R\}^\{d\_\{\\mathrm\{ff\}\}\},W\(2\)∈ℝd×dffW^\{\(2\)\}\\in\\mathbb\{R\}^\{d\\times d\_\{\\mathrm\{ff\}\}\},b\(2\)∈ℝdb^\{\(2\)\}\\in\\mathbb\{R\}^\{d\}, andσ\\sigmathe ReLU applied elementwise\.

###### Definition 3\.11\.

A transformer layer withHHheads and widthddis a function defined as follows\.

Layer:ℝn×d→ℝn×d,Layer​\(A\)=A′′\\text\{Layer\}:\\mathbb\{R\}^\{n\\times d\}\\to\\mathbb\{R\}^\{n\\times d\},\\text\{Layer\}\(A\)=A^\{\\prime\\prime\}A′=MHA​\(A\)\+AA^\{\\prime\}=\\text\{MHA\}\(A\)\+AA′′=FF​\(A′\)\+A′A^\{\\prime\\prime\}=\\text\{FF\}\(A^\{\\prime\}\)\+A^\{\\prime\}HereMHAis the multi\-head attention mechanism, andFFis a position\-wise feedforward network \(FFN\)\. The terms\+A\+Aand\+A′\+A^\{\\prime\}are residual connections\.■\\blacksquare

###### Definition 3\.12\(Transformer Model\)\.

A*transformer model*withLLlayers,HHattention heads per layer, and widthddis a functionf:ℝn×d→ℝkf:\\mathbb\{R\}^\{n\\times d\}\\to\\mathbb\{R\}^\{k\}defined as the composition ofLLtransformer layers, a stack of one or more fully connected feedforward layers, and a linear output layer followed by a softmax\.■\\blacksquare

## 4Theoretical results

In this section, we present the main results that bound the expressiveness of transformers by analyzing predictive modeling for languages generated from a class of uniform, non\-recursive CFGs of fixed depth\. In Section[4\.1](https://arxiv.org/html/2606.17522#S4.SS1)we present a constructive result, building a transformer that predictively models a class of CFGs, using a simplified positional attention mechanism\. In our construction, the number of neurons required grows linearly with the number of derivation tree shapes and quadratically with the number of production rules, while the model’s depth grows linearly with the depth of the grammar\. Our proof, based on the concept of hierarchical compositionality, illustrates how different layers of a transformer encode the hierarchical structure present in CFGs, with lower layers capturing simpler syntactic structures and upper layers capturing progressively more complex structures\. In Section[4\.2](https://arxiv.org/html/2606.17522#S4.SS2), we discuss connections with existing work comparing the expressiveness of transformers with language models based onnn\-grams and finite state automata\. We refer the reader to Section[5](https://arxiv.org/html/2606.17522#S5)for an outline of the proofs, and the Appendix for detailed proofs\.

### 4\.1Statement of main Theorem

We analyze a class of CFGs without recursive rules that generate finite languages, which can be modelled with a sufficiently large transformer using existing results on memorization \(Zhanget al\.\([2017](https://arxiv.org/html/2606.17522#bib.bib64)\)\)\. However, the number of neurons required by naive memorization grows exponentially\. Our work instead establishes much sharper structural bounds on transformer size by leveraging transformers’ ability to represent hierarchical structure\. This differs from existing work analyzing whether transformers can model infinite languages obtained from CFGs with recursive rules, such as generalisations of Dyck languages \(Yaoet al\.\([2021](https://arxiv.org/html/2606.17522#bib.bib58)\); Hahn \([2020](https://arxiv.org/html/2606.17522#bib.bib23)\)\) and more general formal languages that can be recognized by a Turing machine \(Perezet al\.\([2021](https://arxiv.org/html/2606.17522#bib.bib43)\); Bhattamishraet al\.\([2020b](https://arxiv.org/html/2606.17522#bib.bib9)\)\)\. While our bounds on the model size depend oncc, we note that even with a restricted set of tree shapes, the total number of valid sentences in the language can grow exponentially\.

###### Theorem 4\.1\.

Let𝒢=\(Σ,N,P,S\)\\mathcal\{G\}=\(\\Sigma,N,P,S\)be a uniform context\-free grammar with depthdd, maximal rule countMM, maximal branching factorBB, and letc=\|𝒞​\(𝒢\)\|c=\|\\mathcal\{C\}\(\\mathcal\{G\}\)\|\. Given anϵ\>0\\epsilon\>0, there exists a transformer language modelf𝒯:Σ∗→ℝ\|Σ\|f\_\{\\mathcal\{T\}\}:\\Sigma^\{\*\}\\rightarrow\\mathbb\{R\}^\{\|\\Sigma\|\}consisting ofddtransformer blocks followed by5​d\+75d\+7feedforward layers satisfying the following properties\.

- •The transformerf𝒯f\_\{\\mathcal\{T\}\}predictively models the languageℒ​\(𝒢\)\\mathcal\{L\}\(\\mathcal\{G\}\)with error at mostϵ\\epsilon\.
- •The transformer block in each layer has hidden dimensionc​dcd, and consists ofccattention heads, followed by a feedforward neural network withMMneurons\. Each attention head has value dimension11, and theW\(O\)W^\{\(O\)\}matrix has dimensionc×c​dc\\times cd\. For each attention headhh, the relative positional matrixRhR\_\{h\}has at mostBBnon\-zero entries in each row\.
- •Each of the5​d\+75d\+7feedforward layers has at most4​c​B​M24cBM^\{2\}neurons\.■\\blacksquare

The key results ofZhaoet al\.\([2023](https://arxiv.org/html/2606.17522#bib.bib65)\)show that transformers can implement the inside\-outside algorithm for parsing CFGs, and the above theorem differs in two key aspects\. Firstly, whileZhaoet al\.\([2023](https://arxiv.org/html/2606.17522#bib.bib65)\)focuses on encoder\-only transformers such as BERT \(Devlinet al\.\([2019](https://arxiv.org/html/2606.17522#bib.bib15)\)\), our results analyze decoder\-only transformers which are more widely used in language modelling \(Brownet al\.\([2020](https://arxiv.org/html/2606.17522#bib.bib2)\)\)\. Secondly, whileZhaoet al\.\([2023](https://arxiv.org/html/2606.17522#bib.bib65)\)establishes bounds on the number of parameters in a transformer needed to model CFGs, the number of layers in their construction grows linearly with the maximal sentence lengthLL\. In our construction, the number of layers in the transformer grows linearly with the depth of the CFG, which is an improvement since the maximal sentence length can grow exponentially with the depth of the grammar\. We note that due to the dependency oncc, our key result does not yield tight bounds for complex real\-world corpora like the Penn Treebank \(Marcuset al\.\([1993](https://arxiv.org/html/2606.17522#bib.bib35)\)\), but formalizes the core mechanics of hierarchical compositionality for simplified grammars\.

In order to prove a similar statement with standard attention blocks that don’t use the simplified relative positional encoding, one can follow the approach from the proof of Theorem 4\.1 inSvete and Cotterell \([2024](https://arxiv.org/html/2606.17522#bib.bib53)\)\. This construction augments the input token representations with explicit positional embeddings, and the query and key projection matrices are designed such that the inner product depends solely on the position of the tokens\. By applying a scaling factor, the softmax operation approximates a hard attention mechanism, allowing the attention heads to select tokens at the precise positions required to identify the relevant grammatical constituents\. In this setting, the size of the attention heads would scale linearly with the context window length\.

Our construction of the transformer model has the property that each input sequence is processed using a sparse circuit with a single attention head in each transformer block\. This aligns with empirical work extracting circuits \(Olahet al\.\([2020](https://arxiv.org/html/2606.17522#bib.bib40)\); Elhageet al\.\([2021](https://arxiv.org/html/2606.17522#bib.bib19)\)\), which are sparse computational subgraphs within deep learning models that can perform specific tasks\. Our construction of attention heads also has the property that each token only attends to a sparse subset of tokens, which aligns with existing work on the effectiveness of sparse attention mechanisms \(Royet al\.\([2020](https://arxiv.org/html/2606.17522#bib.bib47)\); Beltagyet al\.\([2020](https://arxiv.org/html/2606.17522#bib.bib6)\); Yuanet al\.\([2025](https://arxiv.org/html/2606.17522#bib.bib61)\)\)\.

### 4\.2A comparison withnn\-grams and finite state automata\.

We first compare the above results with Theorem 4\.1 fromSvete and Cotterell \([2024](https://arxiv.org/html/2606.17522#bib.bib53)\), which constructs transformers with a single layer and a single head that representnn\-gram language models \(see alsoNandakumaret al\.\([2025](https://arxiv.org/html/2606.17522#bib.bib39)\)for analogous results with state space models\)\. While the languages in Theorem[4\.1](https://arxiv.org/html/2606.17522#S4.Thmtheorem1)can be modeled usingnn\-gram rules, this typically requires an exponential number of rules\. A depth\-2 CFG resembles annn\-gram model when it has depth22and width\(k,1\)\(k,1\)withk\>nk\>n\. In this setting, the start symbol expands into exactlykknon\-terminals, each of which expands to some number of terminal symbols\. Our results can be viewed as an extension of Theorem 4\.1 ofSvete and Cotterell \([2024](https://arxiv.org/html/2606.17522#bib.bib53)\)to deeper transformer models and deeper CFGs\.

The class of CFGs that we analyze can be represented by finite state automata, and this representation plays a key role in the proof of our Theorem[4\.1](https://arxiv.org/html/2606.17522#S4.Thmtheorem1)\. The representational capabilities of transformers are explored inLiuet al\.\([2023](https://arxiv.org/html/2606.17522#bib.bib31)\)by analyzing their ability to represent finite state automata, with their key results showing that the size of the transformer required grows polynomially with the number of states in the finite state automata\. However, when the CFGs in Theorem[4\.1](https://arxiv.org/html/2606.17522#S4.Thmtheorem1)are expressed as finite state automata, the number of states grows exponentially with the depth of the grammar, and our key results cannot be obtained from those ofLiuet al\.\([2023](https://arxiv.org/html/2606.17522#bib.bib31)\)\. Specifically, converting a CFG with a set of non\-terminalsNNinto an equivalent FSA up to a bounded derivation depthddrequires explicitly encoding all possible valid combinations of unresolved non\-terminals into the automaton’s state spaceQQ\. This flattening of the hierarchical derivation tree into a linear state machine yields a state space of size\|Q\|=𝒪​\(\|N\|d\)\|Q\|=\\mathcal\{O\}\(\|N\|^\{d\}\)\. This exponential blow\-up highlights the inefficiency of modeling deep context\-free grammars using finite state automata, and our construction bypasses this by natively leveraging the depth of the transformer to sequentially process grammatical reductions level\-by\-level\.

### 4\.3Comparison with empirical work

Our results above on the expressiveness of transformers provide a theoretical framework for the controlled experiments conducted inAllen\-Zhu and Li \([2025](https://arxiv.org/html/2606.17522#bib.bib4)\), where the authors trained transformer models with the GPT2\-small architecture, using 12 layers with dimension 768, from scratch on synthetic context\-free grammars\. To ensure the models learn true hierarchical representations rather than local heuristics, the authors designed deeply nested CFGs which generate sequences of up to 729 tokens in length, with over108010^\{80\}valid string combinations in total\. The empirical finding that these decoder\-only transformers can achieve near\-perfect generation accuracy on these highly complex, ambiguous sequences shows that the model does not require exponential scaling to process recursive grammatical structures, as our explicit bounds predict\.

InAllen\-Zhu and Li \([2025](https://arxiv.org/html/2606.17522#bib.bib4)\), the authors observe that transformers trained on synthetic data from CFGs naturally develop specialized attention heads that execute a bottom\-up parsing strategy by dynamically attending to the boundaries of grammatical constituents and gathering information from the child nodes of the derivation tree to form the parent non\-terminal symbol\. This aligns with the explicit construction of self\-attention in our proof of Theorem[4\.1](https://arxiv.org/html/2606.17522#S4.Thmtheorem1), where attention heads are explicitly constructed to selectively aggregate the local syntactic context of child nodes in order to resolve the parent non\-terminals, layer by layer\.

In particular, Section 5\.3 ofAllen\-Zhu and Li \([2025](https://arxiv.org/html/2606.17522#bib.bib4)\)describes an empirical dynamic programming algorithm that computes states denoted asDP​\(k,j,a\)\\text\{DP\}\(k,j,a\)to track whether a non\-terminal symbolaaspans the sequence from tokenkktojj\. Furthermore, in Section 4\.1 they demonstrate that these intermediateD​P​\(k,j,a\)DP\(k,j,a\)symbols can be recovered from the residual stream in the final layers using simple linear probes\. Our constructive proof formalizes these empirical findings by representing the statesDP​\(k,j,a\)\\text\{DP\}\(k,j,a\)using neurons within the hidden layers of the transformer\. We construct multi\-head attention blocks and feedforward neural networks in each layer to implement the recursion used to computeD​P​\(k,j,a\)DP\(k,j,a\)symbols from lower\-level constituents\.

## 5Proofs\.

In this section, we outline the proof of the key result, Theorem[4\.1](https://arxiv.org/html/2606.17522#S4.Thmtheorem1)\.

Given an input sequencew¯=\(wj\)1≤j≤k\\underline\{w\}=\(w\_\{j\}\)\_\{1\\leq j\\leq k\}, we denote byzi​\(w¯\)z\_\{i\}\(\\underline\{w\}\)its image after passing through theii\-th transformer block\. We decompose these vectorszi​\(w¯\)z\_\{i\}\(\\underline\{w\}\)in each transformer layer intoccblocks as follows:zi​\(w¯\)=\{zi,c¯​\(w¯\)\}c¯∈𝒞​\(𝒢\)z\_\{i\}\(\\underline\{w\}\)=\\\{z\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)\\\}\_\{\\underline\{c\}\\in\\mathcal\{C\}\(\\mathcal\{G\}\)\}\. Herezi,c¯​\(w¯\)∈ℝdz\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)\\in\\mathbb\{R\}^\{d\}for eachc¯∈𝒞​\(𝒢\)\\underline\{c\}\\in\\mathcal\{C\}\(\\mathcal\{G\}\)\. The attention heads in theii\-th transformer layer are indexed by a classc¯∈𝒞​\(𝒢\)\\underline\{c\}\\in\\mathcal\{C\}\(\\mathcal\{G\}\), and we denote byaic¯​\(w¯\)∈ℝa\_\{i\}^\{\\underline\{c\}\}\(\\underline\{w\}\)\\in\\mathbb\{R\}the image ofw¯\\underline\{w\}in the corresponding attention head within theii\-th layer\.

### 5\.1Segmenting input sequences using attention heads

For a fixed shapec¯\\underline\{c\}of the derivation tree, begin with the input sequencew¯\\underline\{w\}and repeatedly collapse every group of children that belongs to the same parent, working from the leaves upward\. After this has been done and no further reductions are possible, defineEi,c¯​\(w¯\)E\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)to be the sequence of non\-terminal symbols at leveliiappearing in the resulting string\. The quantitiesEi,c¯′​\(w¯\)E^\{\\prime\}\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)andEi,c¯∗​\(w¯\)E^\{\*\}\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)are defined similarly \(see Section[5\.5](https://arxiv.org/html/2606.17522#S5.SS5)for an example, and the Appendix for a rigorous definition\)\.

###### Lemma 5\.1\.

We can choose attention heads with the following property\. Given an input sequencew¯=\(w1,⋯,wk\)\\underline\{w\}=\(w\_\{1\},\\cdots,w\_\{k\}\)corresponding to the classc¯\\underline\{c\}, the outputaic¯​\(w¯\)a\_\{i\}^\{\\underline\{c\}\}\(\\underline\{w\}\)of the attention head indexed byc¯\\underline\{c\}in theii\-th layer depends only onEi,c¯′​\(w¯\)E^\{\\prime\}\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)\(i\.e\. if another inputw¯′\\underline\{w\}^\{\\prime\}also corresponds to the classc¯\\underline\{c\}, thenaic¯​\(w¯\)=aic¯​\(w¯′\)a\_\{i\}^\{\\underline\{c\}\}\(\\underline\{w\}\)=a\_\{i\}^\{\\underline\{c\}\}\(\\underline\{w\}^\{\\prime\}\)if and only ifEi,c¯′​\(w¯\)=Ei,c¯′​\(w¯′\)E^\{\\prime\}\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)=E^\{\\prime\}\_\{i,\\underline\{c\}\}\(\\underline\{w\}^\{\\prime\}\)\)\.

To prove the above Lemma, we choose the query–key projections for the attention headaic¯a\_\{i\}^\{\\underline\{c\}\}so that a token attends only to a group of tokens which are determined by the shapec¯\\underline\{c\}of the derivation tree \(see Section[A\.2](https://arxiv.org/html/2606.17522#A1.SS2)for a detailed proof\)\. Because we omit the softmax in the attention mechanism and instead apply these deterministic, position\-dependent masks, the attention score for this token and any token outside the specified group is zero\. In order to prove a similar statement without using the simplified relative positional encoding, one can follow the approach from the proof of Theorem 4\.1 inSvete and Cotterell \([2024](https://arxiv.org/html/2606.17522#bib.bib53)\), and use query\-key matrices that encode positional information\.

### 5\.2Encoding non\-terminal symbols with feedforward networks

The next step is to encode non\-terminal symbols by using the feedforward network component of the transformer block\. To prove Lemma[5\.2](https://arxiv.org/html/2606.17522#S5.Thmtheorem2)below, we explicitly construct the feedforward layers to act as a discrete look\-up table using memorization to encode the finite set of valid production rules in the context\-free grammar\. From Lemma[5\.1](https://arxiv.org/html/2606.17522#S5.Thmtheorem1), for a given derivation shape, the attention mechanism isolates and aggregates the necessary constituents, which are represented by the sequenceEi,c¯′​\(w¯\)E^\{\\prime\}\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)\. The feedforward network receives this aggregated output and matches it against its memorized rules, identifies the corresponding parent non\-terminal symbol and encodes it in the\(i\+1\)\(i\+1\)\-st coordinate of the intermediate representationzi,c¯​\(w¯\)z\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)\. The transformer’s residual skip connections ensure that the lower\-level syntactic states in coordinatesj≤ij\\leq iare preserved, and used in successive layers\.

###### Lemma 5\.2\.

We can choose the weights of the transformer so that the following holds\. Given an input sequencew¯=\(w1,⋯,wk\)\\underline\{w\}=\(w\_\{1\},\\cdots,w\_\{k\}\)corresponding to the classc¯\\underline\{c\}, and for eachj≤ij\\leq i, thejj\-th coordinate ofzi,c¯​\(w¯\)z\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)depends only on the stringEj,c¯​\(w¯\)E\_\{j,\\underline\{c\}\}\(\\underline\{w\}\)\. The\(i\+1\)\(i\+1\)\-st coordinate ofzi,c¯​\(w¯\)z\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)depends only on the stringEi\+1,c¯∗​\(w¯\)E^\{\*\}\_\{i\+1,\\underline\{c\}\}\(\\underline\{w\}\), and is0ifEi\+1,c¯∗​\(w¯\)=∅E^\{\*\}\_\{i\+1,\\underline\{c\}\}\(\\underline\{w\}\)=\\emptyset\. Further, thejj\-th coordinate ofzi,c¯​\(w¯\)z\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)is0whenj\>i\+1j\>i\+1\.

Our proof of the above uses the below result fromZhanget al\.\([2017](https://arxiv.org/html/2606.17522#bib.bib64)\), which analyzes the memorization capacity of feedforward neural networks, and shows that they can fit an arbitrary finite set of input\-output vectors \(see alsoYunet al\.\([2019](https://arxiv.org/html/2606.17522#bib.bib16)\)\)\.

###### Lemma 5\.3\.

Let\{\(xi,yi\)\}i=1K\\\{\(x\_\{i\},y\_\{i\}\)\\\}\_\{i=1\}^\{K\}be a finite dataset where each inputxi∈ℝnx\_\{i\}\\in\\mathbb\{R\}^\{n\}and each outputyi∈ℝqy\_\{i\}\\in\\mathbb\{R\}^\{q\}\. Assume that all inputs are distinct, i\.e\.,xi≠xjx\_\{i\}\\neq x\_\{j\}fori≠ji\\neq j\. Consider a feedforward neural networkfθf\_\{\\theta\}with one hidden layer of widthKK, ReLU activations, input dimensionnn, and output dimensionqq\. Then there exists a choice of parametersθ\\thetasuch thatfθ​\(xi\)=yif\_\{\\theta\}\(x\_\{i\}\)\\;=\\;y\_\{i\}for alli∈\[K\]i\\in\[K\]\.

### 5\.3Using stacked feedforward networks for next\-word prediction

The final step is to use a position\-wise feedforward network with5​d\+75d\+7hidden layers to process the encodings of segments from the last transformer block and obtain vectors that encode the set of valid next wordsS​\(w¯\)S\(\\underline\{w\}\)for a given valid prefixw¯=\(w1,⋯,wk\)\\underline\{w\}=\(w\_\{1\},\\cdots,w\_\{k\}\)\. Denote byhi​\(w¯\)h\_\{i\}\(\\underline\{w\}\)its image after passing through theii\-th feedforward layer in the sequence; we decompose these vectors as follows:hi​\(w¯\)=\(hi,c¯​\(w¯\)\)c¯∈𝒞​\(𝒢\)h\_\{i\}\(\\underline\{w\}\)=\(h\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)\)\_\{\\underline\{c\}\\in\\mathcal\{C\}\(\\mathcal\{G\}\)\}\.

Given an input sequencew¯\\underline\{w\}, consider the string of symbols obtained by concatenatingEd,c¯​\(w¯\)E\_\{d,\\underline\{c\}\}\(\\underline\{w\}\),Ed−1,c¯​\(w¯\),…,Ed−i\+1,c¯​\(w¯\)E\_\{d\-1,\\underline\{c\}\}\(\\underline\{w\}\),\.\.\.,E\_\{d\-i\+1,\\underline\{c\}\}\(\\underline\{w\}\)\. We define the setNd−i\+1,c¯​\(w¯\)N\_\{d\-i\+1,\\underline\{c\}\}\(\\underline\{w\}\)as the set of all non\-terminals ofNd−i\+1N\_\{d\-i\+1\}which can be appended to this string to yield a sequence which can be expanded into a valid sentence\. These sets can be computed inductively, which can be done using feedforward neural networks \(see Appendix[A\.3](https://arxiv.org/html/2606.17522#A1.SS3)for a precise definition, and more details\)\. To complete the proof of Theorem[4\.1](https://arxiv.org/html/2606.17522#S4.Thmtheorem1), we construct a linear mapping that maps the output of the last feedforward layer to a vector of logits that encodes the set of valid next wordsS​\(w¯\)S\(\\underline\{w\}\)\.

### 5\.4On the linear representation hypothesis

Our existence result is compatible with the empirical phenomenon known as the linear representation hypothesis \(Parket al\.\([2024](https://arxiv.org/html/2606.17522#bib.bib42)\); Garget al\.\([2026](https://arxiv.org/html/2606.17522#bib.bib21)\)\), in the context of transformers that model context\-free grammars\. With experiments on synthetic data, the empirical studyAllen\-Zhu and Li \([2025](https://arxiv.org/html/2606.17522#bib.bib4)\)shows that Transformers can learn the recursive rules of context\-free grammars, with abstract non\-terminal symbols being recoverable through linear probes applied to the embeddings in the final transformer layer\. Using experiments on real\-world datasets, the empirical studySaglamet al\.\([2025](https://arxiv.org/html/2606.17522#bib.bib48)\)shows that transformers encode high\-level semantic representations within low\-dimensional subspaces in hidden transformer layers\.

Our explicit construction shows that transformer architectures possess the structural capacity to explicitly represent these complex grammatical structures within low\-dimensional linear subspaces\. For a fixed derivation tree shapec¯∈𝒞​\(𝒢\)\\underline\{c\}\\in\\mathcal\{C\}\(\\mathcal\{G\}\), the parsing computations are performed within low\-dimensional subspaces in the intermediate representation indexed byc¯\\underline\{c\}\. Consequently, a simple affine transformation is mathematically sufficient to isolate and separate the representations of distinct non\-terminal symbols\. These theoretical observations about linear separability support the empirical findings inAllen\-Zhu and Li \([2025](https://arxiv.org/html/2606.17522#bib.bib4)\)about linear probes\.

However, our construction encodes non\-terminals in low\-dimensional subspaces through a strictly orthogonal basis, allocating distinct indicator neurons for specific grammatical states\. This simplified model does not account for the principle of superposition \(Garget al\.\([2026](https://arxiv.org/html/2606.17522#bib.bib21)\); Saglamet al\.\([2025](https://arxiv.org/html/2606.17522#bib.bib48)\)\), where models compress more features than the available dimensions\. It is an open question to understand how standard training dynamics yield transformers that compress grammatical structures into dense vectors in residual streams using superposition\.

### 5\.5Example\.

We revisit the CFG from Table[1](https://arxiv.org/html/2606.17522#S3.T1), and provide two examples to illustrate the notation used in this section\. Herec¯1\\underline\{c\}\_\{1\}andc¯2\\underline\{c\}\_\{2\}are the shapes corresponding to the two derivation trees in Figure[1](https://arxiv.org/html/2606.17522#S3.F1)\.

w¯1\\displaystyle\\underline\{w\}\_\{1\}=\(a1,a6,a5,a8,a5,a2,a7\)\\displaystyle=\(a\_\{1\},a\_\{6\},a\_\{5\},a\_\{8\},a\_\{5\},a\_\{2\},a\_\{7\}\)E3,c¯1​\(w¯1\)\\displaystyle E\_\{3,\\underline\{c\}\_\{1\}\}\(\\underline\{w\}\_\{1\}\)=a13,E2,c¯1​\(w¯1\)=a32,E1,c¯1​\(w¯1\)=a7\\displaystyle=a\_\{1\}^\{3\},E\_\{2,\\underline\{c\}\_\{1\}\}\(\\underline\{w\}\_\{1\}\)=a\_\{3\}^\{2\},E\_\{1,\\underline\{c\}\_\{1\}\}\(\\underline\{w\}\_\{1\}\)=a\_\{7\}N3,c¯1​\(w¯1\)\\displaystyle N\_\{3,\\underline\{c\}\_\{1\}\}\(\\underline\{w\}\_\{1\}\)=\{a43\},N2,c¯1​\(w¯1\)=\{a42\}\\displaystyle=\\\{a\_\{4\}^\{3\}\\\},N\_\{2,\\underline\{c\}\_\{1\}\}\(\\underline\{w\}\_\{1\}\)=\\\{a\_\{4\}^\{2\}\\\}N1,c¯1​\(w¯1\)\\displaystyle N\_\{1,\\underline\{c\}\_\{1\}\}\(\\underline\{w\}\_\{1\}\)=\{a4,a8\}\\displaystyle=\\\{a\_\{4\},a\_\{8\}\\\}w¯2\\displaystyle\\underline\{w\}\_\{2\}=\(a6,a8,a3,a9,a10,a4,a5,\\displaystyle=\(a\_\{6\},a\_\{8\},a\_\{3\},a\_\{9\},a\_\{10\},a\_\{4\},a\_\{5\},a3,a1,a7,a9,a7,a8\)\\displaystyle a\_\{3\},a\_\{1\},a\_\{7\},a\_\{9\},a\_\{7\},a\_\{8\}\)E3,c¯2​\(w¯2\)\\displaystyle E\_\{3,\\underline\{c\}\_\{2\}\}\(\\underline\{w\}\_\{2\}\)=a23​a33,E2,c¯2​\(w¯2\)=a42,E1,c¯2​\(w¯2\)=∅\\displaystyle=a\_\{2\}^\{3\}a\_\{3\}^\{3\},E\_\{2,\\underline\{c\}\_\{2\}\}\(\\underline\{w\}\_\{2\}\)=a\_\{4\}^\{2\},E\_\{1,\\underline\{c\}\_\{2\}\}\(\\underline\{w\}\_\{2\}\)=\\emptysetN3,c¯2​\(w¯2\)\\displaystyle N\_\{3,\\underline\{c\}\_\{2\}\}\(\\underline\{w\}\_\{2\}\)=\{a43\},N2,c¯2​\(w¯2\)=\{a52\}\\displaystyle=\\\{a\_\{4\}^\{3\}\\\},N\_\{2,\\underline\{c\}\_\{2\}\}\(\\underline\{w\}\_\{2\}\)=\\\{a\_\{5\}^\{2\}\\\}N1,c¯2​\(w¯2\)\\displaystyle N\_\{1,\\underline\{c\}\_\{2\}\}\(\\underline\{w\}\_\{2\}\)=\{a3,a10\}\\displaystyle=\\\{a\_\{3\},a\_\{10\}\\\}

## 6Discussion and limitations

Interpretability of transformers: circuits\.

Complementing our theoretical results,Allen\-Zhu and Li \([2025](https://arxiv.org/html/2606.17522#bib.bib4)\)shows that transformer models can empirically learn CFGs when trained using stochastic gradient descent, and demonstrates that the transformer model’s hidden states encode non\-terminal symbols \(see alsoZhaoet al\.\([2023](https://arxiv.org/html/2606.17522#bib.bib65)\)\)\. While our results establish the existence of transformers with circuits that can model CFGs, their findings suggest that similar structures may emerge in practice through stochastic gradient descent, but without a detailed analysis\. Bridging this gap remains a central challenge for future work, and could be approached using mechanistic interpretability\. Algorithms such as ACDC \(Conmyet al\.\([2023](https://arxiv.org/html/2606.17522#bib.bib18)\)\) and EAP \(Syedet al\.\([2023](https://arxiv.org/html/2606.17522#bib.bib54)\)\) could be used to identify and analyze circuits \(Olahet al\.\([2020](https://arxiv.org/html/2606.17522#bib.bib40)\); Elhageet al\.\([2021](https://arxiv.org/html/2606.17522#bib.bib19)\)\), that are sparse computational subgraphs of models which capture their behavior for specific tasks\.

On the inductive bias of sparse attention mechanisms\.While our theoretical constructions rely on a sparse attention mechanism to efficiently capture the hierarchical structure of languages generated by CFGs of depthdd, prior work has proposed a variety of sparse attention patterns designed to scale transformers to longer sequences \(Royet al\.\([2020](https://arxiv.org/html/2606.17522#bib.bib47)\); Beltagyet al\.\([2020](https://arxiv.org/html/2606.17522#bib.bib6)\); Yuanet al\.\([2025](https://arxiv.org/html/2606.17522#bib.bib61)\)\)\. While these architectures have shown empirical success in tasks like document classification and question answering \(Ainslieet al\.\([2020](https://arxiv.org/html/2606.17522#bib.bib3)\)\), and local attention patterns have been used in vision transformers \(Liuet al\.\([2021](https://arxiv.org/html/2606.17522#bib.bib32)\)\), a rigorous understanding of their expressive power and inductive biases remains limited\. The BigBird architecture \(Zaheeret al\.\([2020](https://arxiv.org/html/2606.17522#bib.bib63)\)\) introduces structured sparsity in attention, which is a mixture of global, local, and random patterns, with provable guarantees under certain conditions\. In future work, it would be interesting to extend our theoretical framework and characterize which classes of CFGs can be modeled using different sparse attention patterns, building on the analysis inYunet al\.\([2020](https://arxiv.org/html/2606.17522#bib.bib62)\)\.

Generalizations to question\-answering tasks with transformer models\.While our framework focuses on sentence completion using CFGs, many of the tasks at which large language models excel — such as question answering, text or code generation and machine translation — also exhibit rich hierarchical structure that could be captured using extensions of CFGs\. For instance, synchronous CFGs provide a natural formalism for modeling machine translation \(Chiang \([2005](https://arxiv.org/html/2606.17522#bib.bib13)\)\)\. Attribute grammars augment CFGs with semantic attributes and rules \(Knuth \([1968](https://arxiv.org/html/2606.17522#bib.bib26)\)\), and can model the dependencies and constraints present in question\-answering tasks \(Marionet al\.\([2021](https://arxiv.org/html/2606.17522#bib.bib36)\)\), such as resolving references or selecting the correct scope of a question\. Text and code generation tasks also involve hierarchical structures \(Yin and Neubig \([2017](https://arxiv.org/html/2606.17522#bib.bib60)\); Sunet al\.\([2020](https://arxiv.org/html/2606.17522#bib.bib52)\)\), and extending our theoretical constructions to these richer grammar classes represents a promising direction for understanding and improving the generalization capabilities of deep models across a wider range of language tasks\.

## 7Conclusion

This paper provides a theoretical framework for understanding the expressiveness of deep transformer\-based language models by analyzing their ability to model hierarchical structures using a class of CFGs with fixed depth and a bounded number of tree shapes\. We give an explicit construction of transformers with a positional attention mechanism, where the model depth increases linearly with the depth of the underlying CFG, while the number of neurons required in each layer scales quadratically with the number of production rules and linearly with the number of derivation tree shapes\. These results formalize the intuition that deeper architectures can represent increasingly complex linguistic structures and mitigate the curse of dimensionality by exploiting hierarchical structures, mirroring the recursive decomposition of phrases and clauses observed in natural language\.

Our expressivity results support recent empirical observations inAllen\-Zhu and Li \([2025](https://arxiv.org/html/2606.17522#bib.bib4)\); Saglamet al\.\([2025](https://arxiv.org/html/2606.17522#bib.bib48)\)about the linear representation hypothesis using an orthogonal basis space in a simplified model without superposition\. We prove that transformers have the structural capacity to encode non\-terminal symbols using low\-dimensional subspaces in their hidden layers, and implement bottom\-up dynamic programming algorithms for parsing CFGs, with each layer of the transformer corresponding to a level in the grammatical hierarchy\. This work lays the groundwork for further theoretical investigation into the inner workings of transformer models and could lead to new insights into the design of more efficient, interpretable architectures informed by formal language theory\.

## Acknowledgments

We thank Yash Sarrof, Yana Veitsman, and Michael Hahn for their help in proofreading the manuscript, engaging in valuable discussions regarding CKY parsing with transformers, and independently conducting experiments to verify our key claims\. We are also grateful to Goncalo Paulo for insightful discussions on transformer circuits\.

## References

- A survey of neural networks and formal languages\.CoRR\.Note:arXiv preprintCited by:[§1](https://arxiv.org/html/2606.17522#S1.p4.1)\.
- J\. Ainslie, S\. Ontañón, C\. Alberti, P\. Pham, A\. Ravula, and S\. Sanghai \(2020\)ETC: encoding long and structured data in transformers\.InProceedings of the Conference on Empirical Methods in Natural Language Processing \(EMNLP\),Cited by:[§6](https://arxiv.org/html/2606.17522#S6.p3.1)\.
- Z\. Allen\-Zhu and Y\. Li \(2025\)Physics of language models: part 1, learning hierarchical language structures\.Transactions on Machine Learning Research\.Cited by:[§1](https://arxiv.org/html/2606.17522#S1.p3.1),[§1](https://arxiv.org/html/2606.17522#S1.p5.1),[§2](https://arxiv.org/html/2606.17522#S2.p1.1),[§3\.2](https://arxiv.org/html/2606.17522#S3.SS2.p1.1),[§3\.2](https://arxiv.org/html/2606.17522#S3.SS2.p2.5),[§4\.3](https://arxiv.org/html/2606.17522#S4.SS3.p1.1),[§4\.3](https://arxiv.org/html/2606.17522#S4.SS3.p2.1),[§4\.3](https://arxiv.org/html/2606.17522#S4.SS3.p3.7),[§5\.4](https://arxiv.org/html/2606.17522#S5.SS4.p1.1),[§5\.4](https://arxiv.org/html/2606.17522#S5.SS4.p2.2),[§6](https://arxiv.org/html/2606.17522#S6.p2.1),[§7](https://arxiv.org/html/2606.17522#S7.p2.1)\.
- P\. Barcelo, A\. Kozachinskiy, A\. W\. Lin, and V\. Podolskii \(2024\)Logical languages accepted by transformer encoders with hard attention\.InInternational Conference on Learning Representations \(ICLR\),Cited by:[§2](https://arxiv.org/html/2606.17522#S2.p2.4)\.
- I\. Beltagy, M\. E\. Peters, and A\. Cohan \(2020\)Longformer: the long\-document transformer\.Note:arXiv preprint arXiv:2004\.05150Cited by:[§1](https://arxiv.org/html/2606.17522#S1.p1.1),[§4\.1](https://arxiv.org/html/2606.17522#S4.SS1.p4.1),[§6](https://arxiv.org/html/2606.17522#S6.p3.1)\.
- Y\. Bengio, R\. Ducharme, P\. Vincent, and C\. Jauvin \(2003\)A neural probabilistic language model\.Journal of Machine Learning Research\.Cited by:[§1](https://arxiv.org/html/2606.17522#S1.p1.1)\.
- S\. Bhattamishra, K\. Ahuja, and N\. Goyal \(2020a\)On the ability of self\-attention networks to recognize counter languages\.InProceedings of the 2020 Conference on Empirical Methods in Natural Language Processing \(EMNLP\),Cited by:[§2](https://arxiv.org/html/2606.17522#S2.p2.4),[§3\.1](https://arxiv.org/html/2606.17522#S3.SS1.p2.2)\.
- S\. Bhattamishra, A\. Patel, and N\. Goyal \(2020b\)On the computational power of transformers and its implications in sequence modeling\.InProceedings of the 24th Conference on Computational Natural Language Learning \(CoNLL\),Cited by:[§2](https://arxiv.org/html/2606.17522#S2.p2.4),[§4\.1](https://arxiv.org/html/2606.17522#S4.SS1.p1.1)\.
- T\. Brown, B\. Mann, N\. Ryder, M\. Subbiah, J\. D\. Kaplan, P\. Dhariwal, A\. Neelakantan, P\. Shyam, G\. Sastry, A\. Askell, S\. Agarwal,et al\.\(2020\)Language models are few\-shot learners\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§1](https://arxiv.org/html/2606.17522#S1.p1.1),[§4\.1](https://arxiv.org/html/2606.17522#S4.SS1.p2.2)\.
- E\. Charniak \(1996\)Tree\-bank grammars\.InProceedings of the National Conference on Artificial Intelligence \(AAAI\),Cited by:[§3\.2](https://arxiv.org/html/2606.17522#S3.SS2.p1.1)\.
- D\. Chiang \(2005\)A hierarchical phrase\-based model for statistical machine translation\.InProceedings of the 43rd Annual Meeting of the Association for Computational Linguistics \(ACL\),Cited by:[§6](https://arxiv.org/html/2606.17522#S6.p4.1)\.
- N\. Chomsky \(1957\)Syntactic structures\.Mouton\.Cited by:[§1](https://arxiv.org/html/2606.17522#S1.p2.1)\.
- A\. Conmy, A\. N\. Mavor\-Parker, A\. Lynch, S\. Heimersheim, and A\. Garriga\-Alonso \(2023\)Towards automated circuit discovery for mechanistic interpretability\.InProceedings of the Thirty\-seventh Conference on Neural Information Processing Systems,Cited by:[§6](https://arxiv.org/html/2606.17522#S6.p2.1)\.
- M\. Costa\-Jussà, J\. Cross, O\. Çelebi, M\. Elbayad, K\. Heafield,et al\.\(2022\)No language left behind: scaling human\-centered machine translation\.Note:arXiv preprintarXiv:2207\.04672Cited by:[§1](https://arxiv.org/html/2606.17522#S1.p1.1)\.
- J\. Devlin, M\. Chang, K\. Lee, and K\. Toutanova \(2019\)BERT: pre\-training of deep bidirectional transformers for language understanding\.InProceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics,Cited by:[§1](https://arxiv.org/html/2606.17522#S1.p1.1),[§4\.1](https://arxiv.org/html/2606.17522#S4.SS1.p2.2)\.
- N\. Elhage, N\. Nanda, C\. Olsson, T\. Henighan, N\. Joseph, B\. Mann, A\. Askell, Y\. Bai, A\. Chen, T\. Conerly, N\. DasSarma, D\. Drain, D\. Ganguli, Z\. Hatfield\-Dodds, D\. Hernandez, A\. Jones, J\. Kernion, L\. Lovitt, K\. Ndousse, D\. Amodei, T\. Brown, J\. Clark, J\. Kaplan, S\. McCandlish, and C\. Olah \(2021\)A mathematical framework for transformer circuits\.Note:Transformer Circuits Thread,[https://transformer\-circuits\.pub/2021/framework/index\.html](https://transformer-circuits.pub/2021/framework/index.html)Cited by:[§4\.1](https://arxiv.org/html/2606.17522#S4.SS1.p4.1),[§6](https://arxiv.org/html/2606.17522#S6.p2.1)\.
- A\. Fan, S\. Bhosale, H\. Schwenk, Z\. Ma, A\. El\-Kishky, and et al\. \(2020\)Beyond english\-centric multilingual machine translation\.The Journal of Machine Learning Research\.Cited by:[§1](https://arxiv.org/html/2606.17522#S1.p1.1)\.
- N\. Garg, J\. Kleinberg, and K\. Peng \(2026\)How many features can a language model store under the linear representation hypothesis?\.External Links:2602\.11246,[Link](https://arxiv.org/abs/2602.11246)Cited by:[§1](https://arxiv.org/html/2606.17522#S1.p5.1),[§5\.4](https://arxiv.org/html/2606.17522#S5.SS4.p1.1),[§5\.4](https://arxiv.org/html/2606.17522#S5.SS4.p3.1)\.
- J\. Garnier\-Brun, M\. Mezard, E\. Moscato, and L\. Saglietti \(2025\)How transformers learn structured data: insights from hierarchical filtering\.InProceedings of the International Conference on Machine Learning,Cited by:[§2](https://arxiv.org/html/2606.17522#S2.p1.1)\.
- M\. Hahn \(2020\)Theoretical limitations of self\-attention in neural sequence models\.Transactions of the Association for Computational Linguistics\.Cited by:[§1](https://arxiv.org/html/2606.17522#S1.p2.1),[§2](https://arxiv.org/html/2606.17522#S2.p2.4),[§4\.1](https://arxiv.org/html/2606.17522#S4.SS1.p1.1)\.
- Y\. Hao, D\. Angluin, and R\. Frank \(2022\)Formal language recognition by hard attention transformers: perspectives from circuit complexity\.Transactions of the Association for Computational Linguistics\.Cited by:[§2](https://arxiv.org/html/2606.17522#S2.p2.4)\.
- J\. Hoffmann, S\. Borgeaud, A\. Mensch, E\. Buchatskaya, T\. Cai, and et al\. \(2022\)Training compute\-optimal large language models\.InConference on Neural Information Processing Systems,Cited by:[§1](https://arxiv.org/html/2606.17522#S1.p1.1)\.
- D\. E\. Knuth \(1968\)Semantics of context\-free languages\.Mathematical Systems Theory\.Cited by:[§6](https://arxiv.org/html/2606.17522#S6.p4.1)\.
- A\. Koller, M\. Regneri, and S\. Thater \(2008\)Regular tree grammars as a formalism for scope underspecification\.InProceedings of the Association for Computational Linguistics,Cited by:[§3\.2](https://arxiv.org/html/2606.17522#S3.SS2.p1.1)\.
- Z\. Lan, M\. Chen, S\. Goodman, K\. Gimpel, P\. Sharma, and R\. Soricut \(2020\)ALBERT: a lite BERT for self\-supervised learning of language representations\.InInternational Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2606.17522#S1.p1.1)\.
- B\. Liu, J\. T\. Ash, S\. Goel, A\. Krishnamurthy, and C\. Zhang \(2023\)Transformers learn shortcuts to automata\.InInternational Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2606.17522#S1.p2.1),[§2](https://arxiv.org/html/2606.17522#S2.p2.4),[§4\.2](https://arxiv.org/html/2606.17522#S4.SS2.p2.4)\.
- Z\. Liu, Y\. Lin, Y\. Cao, H\. Hu, Y\. Wei, Z\. Zhang, S\. Lin, and B\. Guo \(2021\)Swin transformer: hierarchical vision transformer using shifted windows\.InProceedings of the IEEE/CVF International Conference on Computer Vision,Cited by:[§6](https://arxiv.org/html/2606.17522#S6.p3.1)\.
- E\. Malach and S\. Shalev\-Shwartz \(2018\)A provably correct algorithm for deep learning that actually works\.Note:arXiv preprint, arXiv:1803\.09522Cited by:[§2](https://arxiv.org/html/2606.17522#S2.p1.1)\.
- E\. Malach and S\. Shalev\-Shwartz \(2020\)The implications of local correlation on learning some deep functions\.InAdvances in Neural Information Processing Systems,Cited by:[§2](https://arxiv.org/html/2606.17522#S2.p1.1)\.
- M\. P\. Marcus, M\. A\. Marcinkiewicz, and B\. Santorini \(1993\)Building a large annotated corpus of english: the penn treebank\.Computational linguistics,pp\. 313–330\.Cited by:[§4\.1](https://arxiv.org/html/2606.17522#S4.SS1.p2.2)\.
- P\. Marion, P\. Nowak, and F\. Piccinno \(2021\)Structured context and high\-coverage grammar for conversational question answering over knowledge graphs\.InProceedings of the Conference on Empirical Methods in Natural Language Processing \(EMNLP\),Cited by:[§6](https://arxiv.org/html/2606.17522#S6.p4.1)\.
- W\. Merrill and A\. Sabharwal \(2024\)The expressive power of transformers with chain of thought\.InProceedings of the International Conference on Learning Representations,Cited by:[§2](https://arxiv.org/html/2606.17522#S2.p2.4)\.
- E\. Mossel \(2016\)Deep learning and hierarchal generative models\.Note:arXiv preprint, arXiv:1612\.09057Cited by:[§1](https://arxiv.org/html/2606.17522#S1.p2.1),[§2](https://arxiv.org/html/2606.17522#S2.p1.1)\.
- V\. Nandakumar, Q\. Qu, P\. Mi, and T\. Liu \(2025\)State space models can expressnn\-gram languages\.InTransactions on Machine Learning Research,Cited by:[§4\.2](https://arxiv.org/html/2606.17522#S4.SS2.p1.7)\.
- M\. Nederhof and H\. Vogler \(2012\)Synchronous context\-free tree grammars\.InProceedings of the 11th International Workshop on Tree Adjoining Grammars and Related Formalisms,Cited by:[§3\.2](https://arxiv.org/html/2606.17522#S3.SS2.p1.1)\.
- C\. Olah, N\. Cammarata, L\. Schubert, G\. Goh, M\. Petrov, and S\. Carter \(2020\)Zoom in: an introduction to circuits\.Note:Distill,[https://distill\.pub/2020/circuits/zoom\-in](https://distill.pub/2020/circuits/zoom-in)Cited by:[§4\.1](https://arxiv.org/html/2606.17522#S4.SS1.p4.1),[§6](https://arxiv.org/html/2606.17522#S6.p2.1)\.
- K\. Park, Y\. J\. Choe, and V\. Veitch \(2024\)The linear representation hypothesis and the geometry of large language models\.InProceedings of the 41st International Conference on Machine Learning \(ICML\),Cited by:[§5\.4](https://arxiv.org/html/2606.17522#S5.SS4.p1.1)\.
- J\. Perez, P\. Barceló, and J\. Marinkovic \(2021\)Attention is turing\-complete\.Journal of Machine Learning Research\.Cited by:[§2](https://arxiv.org/html/2606.17522#S2.p2.4),[§4\.1](https://arxiv.org/html/2606.17522#S4.SS1.p1.1)\.
- T\. Poggio, H\. Mhaskar, L\. Rosasco, B\. Miranda, and Q\. Liao \(2017\)Why and when can deep\-but not shallow\-networks avoid the curse of dimensionality: a review\.International Journal of Automation and Computing\.Cited by:[§1](https://arxiv.org/html/2606.17522#S1.p2.1),[§2](https://arxiv.org/html/2606.17522#S2.p1.1)\.
- O\. Press, N\. A\. Smith, and O\. Levy \(2020\)Improving transformer models by reordering their sublayers\.InProceedings of the Association for Computational Linguistics,Cited by:[§3\.3](https://arxiv.org/html/2606.17522#S3.SS3.p1.1)\.
- C\. Raffel, N\. M\. Shazeer, A\. Roberts, K\. Lee, S\. Narang, M\. Matena, Y\. Zhou, W\. Li, and P\. J\. Liu \(2020\)Exploring the limits of transfer learning with a unified text\-to\-text transformer\.Journal of Machine Learning Research\.Cited by:[§1](https://arxiv.org/html/2606.17522#S1.p1.1)\.
- A\. Roy, M\. Saffar, A\. Vaswani, and D\. Grangier \(2020\)Efficient content\-based sparse attention with routing transformers\.InTransactions of the Association for Computational Linguistics,Cited by:[§4\.1](https://arxiv.org/html/2606.17522#S4.SS1.p4.1),[§6](https://arxiv.org/html/2606.17522#S6.p3.1)\.
- B\. Saglam, P\. Kassianik, B\. Nelson, S\. Weerawardhena, Y\. Singer, and A\. Karbasi \(2025\)Large language models encode semantics and alignment in linearly separable representations\.InProceedings of the 14th International Joint Conference on Natural Language Processing and the 4th Conference of the Asia\-Pacific Chapter of the Association for Computational Linguistics,Cited by:[§1](https://arxiv.org/html/2606.17522#S1.p3.1),[§1](https://arxiv.org/html/2606.17522#S1.p5.1),[§5\.4](https://arxiv.org/html/2606.17522#S5.SS4.p1.1),[§5\.4](https://arxiv.org/html/2606.17522#S5.SS4.p3.1),[§7](https://arxiv.org/html/2606.17522#S7.p2.1)\.
- Y\. Sarrof, Y\. Veitsman, and M\. Hahn \(2024\)The expressive capacity of state space models: a formal language perspective\.Advances in Neural Information Processing Systems\.Cited by:[§2](https://arxiv.org/html/2606.17522#S2.p2.4),[§3\.1](https://arxiv.org/html/2606.17522#S3.SS1.p1.1),[§3\.1](https://arxiv.org/html/2606.17522#S3.SS1.p2.2)\.
- P\. Shaw, J\. Uszkoreit, and A\. Vaswani \(2018\)Self\-attention with relative position representations\.InProceedings of the Conference of the North American Chapter of the Association for Computational Linguistics,Cited by:[§3\.3](https://arxiv.org/html/2606.17522#S3.SS3.p1.1)\.
- L\. Strobl, W\. Merrill, G\. Weiss, D\. Chiang, and D\. Angluin \(2024\)What formal languages can transformers express? a survey\.Transactions of the Association for Computational Linguistics\.Cited by:[§1](https://arxiv.org/html/2606.17522#S1.p4.1)\.
- Z\. Sun, Q\. Zhu, Y\. Xiong, Y\. Sun, L\. Mou, and L\. Zhang \(2020\)Treegen: a tree\-based transformer architecture for code generation\.InProceedings of the AAAI Conference on Artificial Intelligence,Cited by:[§6](https://arxiv.org/html/2606.17522#S6.p4.1)\.
- A\. Svete and R\. Cotterell \(2024\)Transformers can representnn\-gram language models\.InProceedings of the North American Chapter of the Association for Computational Linguistics,Cited by:[§A\.2](https://arxiv.org/html/2606.17522#A1.SS2.p4.1),[§4\.1](https://arxiv.org/html/2606.17522#S4.SS1.p3.1),[§4\.2](https://arxiv.org/html/2606.17522#S4.SS2.p1.7),[§5\.1](https://arxiv.org/html/2606.17522#S5.SS1.p2.2)\.
- A\. Syed, C\. Rager, and A\. Conmy \(2023\)Attribution patching outperforms automated circuit discovery\.InNeurIPS Workshop on Attributing Model Behavior at Scale,Cited by:[§6](https://arxiv.org/html/2606.17522#S6.p2.1)\.
- Y\. Tay, D\. Bahri, D\. Metzler, D\. Juan, Z\. Zhao, and C\. Zheng \(2020\)Synthesizer: rethinking self\-attention for transformer models\.InProceedings of the 37th International Conference on Machine Learning,Cited by:[§3\.3](https://arxiv.org/html/2606.17522#S3.SS3.p1.1)\.
- U\. Tomasini and M\. Wyart \(2024\)How deep networks learn sparse and hierarchical data: the sparse random hierarchy model\.InProceedings of the 41st International Conference on Machine Learning,Cited by:[§2](https://arxiv.org/html/2606.17522#S2.p1.1)\.
- A\. Vaswani, N\. Shazeer, N\. Parmar, J\. Uszkoreit, L\. Jones, A\. N\. Gomez, L\. Kaiser, and I\. Polosukhin \(2017\)Attention is all you need\.InAdvances in Neural Information Processing Systems,Cited by:[§1](https://arxiv.org/html/2606.17522#S1.p1.1),[§3\.3](https://arxiv.org/html/2606.17522#S3.SS3.p1.1)\.
- A\. Yang, D\. Chiang, and D\. Angluin \(2024\)Masked hard\-attention transformers recognize exactly the star\-free languages\.InAdvances in Neural Information Processing Systems,Vol\.37\.Cited by:[§2](https://arxiv.org/html/2606.17522#S2.p2.4)\.
- S\. Yao, B\. Peng, C\. Papadimitriou, and K\. Narasimhan \(2021\)Self\-attention networks can process bounded hierarchical languages\.InProceedings of the Association for Computational Linguistics,Cited by:[§1](https://arxiv.org/html/2606.17522#S1.p2.1),[§2](https://arxiv.org/html/2606.17522#S2.p2.4),[§4\.1](https://arxiv.org/html/2606.17522#S4.SS1.p1.1)\.
- P\. Yin and G\. Neubig \(2017\)A syntactic neural model for general\-purpose code generation\.InProceedings of the Association for Computational Linguistics,Cited by:[§6](https://arxiv.org/html/2606.17522#S6.p4.1)\.
- J\. Yuan, H\. Gao, D\. Dai, J\. Luo, L\. Zhao, Z\. Zhang, and et al\. \(2025\)Native sparse attention: hardware\-aligned and natively trainable sparse attention\.Note:arXiv preprint arXiv:2502\.11089Cited by:[§4\.1](https://arxiv.org/html/2606.17522#S4.SS1.p4.1),[§6](https://arxiv.org/html/2606.17522#S6.p3.1)\.
- C\. Yun, Y\. Chang, S\. Bhojanapalli, A\. S\. Rawat, S\. J\. Reddi, and S\. Kumar \(2020\)O​\(n\)O\(n\)Connections are expressive enough: universal approximability of sparse transformers\.InProceedings of Neural Information Processing Systems,Cited by:[§6](https://arxiv.org/html/2606.17522#S6.p3.1)\.
- C\. Yun, S\. Sra, and A\. Jadbabaie \(2019\)Small relu networks are powerful memorizers: a tight analysis of memorization capacity\.InAdvances in Neural Information Processing Systems,Cited by:[§A\.1](https://arxiv.org/html/2606.17522#A1.SS1.p1.1),[§5\.2](https://arxiv.org/html/2606.17522#S5.SS2.p2.1)\.
- M\. Zaheer, G\. Guruganesh, A\. Dubey, J\. Ainslie, C\. Alberti, S\. Ontañón, P\. Pham, A\. Ravula, Q\. Wang, L\. Yang, and A\. Ahmed \(2020\)Big bird: transformers for longer sequences\.InAdvances in Neural Information Processing Systems,Cited by:[§1](https://arxiv.org/html/2606.17522#S1.p1.1),[§6](https://arxiv.org/html/2606.17522#S6.p3.1)\.
- C\. Zhang, S\. Bengio, M\. Hardt, B\. Recht, and O\. Vinyals \(2017\)Understanding deep learning requires rethinking generalization\.InInternational Conference on Learning Representations,Cited by:[§A\.1](https://arxiv.org/html/2606.17522#A1.SS1.p1.1),[§4\.1](https://arxiv.org/html/2606.17522#S4.SS1.p1.1),[§5\.2](https://arxiv.org/html/2606.17522#S5.SS2.p2.1)\.
- H\. Zhao, A\. Panigrahi, R\. Ge, and S\. Arora \(2023\)Do transformers parse while predicting the masked word?\.InProceedings of the Conference on Empirical Methods in Natural Language Processing,Cited by:[§1](https://arxiv.org/html/2606.17522#S1.p3.1),[§2](https://arxiv.org/html/2606.17522#S2.p2.4),[§4\.1](https://arxiv.org/html/2606.17522#S4.SS1.p2.2),[§6](https://arxiv.org/html/2606.17522#S6.p2.1)\.
- S\. Zhao, J\. Song, and S\. Ermon \(2017\)Learning hierarchical features from deep generative models\.InProceedings of the International Conference on Machine Learning,Cited by:[§2](https://arxiv.org/html/2606.17522#S2.p1.1)\.

## Appendix AProof of Theorem[4\.1](https://arxiv.org/html/2606.17522#S4.Thmtheorem1)

### A\.1Preliminary lemmas

In this section, we recall results fromZhanget al\.\([2017](https://arxiv.org/html/2606.17522#bib.bib64)\)andYunet al\.\([2019](https://arxiv.org/html/2606.17522#bib.bib16)\), which analyze the memorization capacity of feedforward neural networks, and show that they can fit an arbitrary finite set of input\-output vectors\. These results will be used in the proof of Lemmas[5\.2](https://arxiv.org/html/2606.17522#S5.Thmtheorem2)and[A\.6](https://arxiv.org/html/2606.17522#A1.Thmtheorem6)below\.

###### Lemma A\.1\.

Let\{\(xi,yi\)\}i=1N\\\{\(x\_\{i\},y\_\{i\}\)\\\}\_\{i=1\}^\{N\}be a dataset where allxix\_\{i\}are distinct and each label satisfiesyi∈\[−1,1\]dyy\_\{i\}\\in\[\-1,1\]^\{d\_\{y\}\}\. Supposefθf\_\{\\theta\}is a feedforward neural network with two hidden layers, ReLU activations, input dimensiond1d\_\{1\}, hidden widthd2d\_\{2\}, and output dimensiondyd\_\{y\}\. If

4​⌊d14⌋​⌊d24​dy⌋≥N,4\\Big\\lfloor\\tfrac\{d\_\{1\}\}\{4\}\\Big\\rfloor\\Big\\lfloor\\tfrac\{d\_\{2\}\}\{4d\_\{y\}\}\\Big\\rfloor\\;\\;\\geq\\;N,then there exists a choice of parametersθ\\thetasuch that

fθ​\(xi\)=yifor all​i∈\[N\]\.f\_\{\\theta\}\(x\_\{i\}\)\\;=\\;y\_\{i\}\\quad\\text\{for all \}i\\in\[N\]\.

We will also need the following basic Lemma in the proofs for Section[5\.3](https://arxiv.org/html/2606.17522#S5.SS3)\.

###### Lemma A\.2\.

Fixk∈ℕk\\in\\mathbb\{N\}and choose distinct pointst1,…,tk∈ℝt\_\{1\},\\dots,t\_\{k\}\\in\\mathbb\{R\}\. There existsδ\>0\\delta\>0and a one\-hidden\-layer ReLU networkf:ℝ→ℝf:\\mathbb\{R\}\\to\\mathbb\{R\}with3​k3khidden units such that:

- •f​\(tm\)=1f\(t\_\{m\}\)=1for eachm∈\{1,2,…,k\}m\\in\\\{1,2,\\dots,k\\\},
- •f​\(x\)=0f\(x\)=0for allx∉⋃m=1k\[tm−δ,tm\+δ\]x\\notin\\bigcup\_\{m=1\}^\{k\}\[\\,t\_\{m\}\-\\delta,\\,t\_\{m\}\+\\delta\\,\],
- •ffis piecewise linear with exactly one triangular peak on each interval\[tm−δ,tm\+δ\]\[\\,t\_\{m\}\-\\delta,\\,t\_\{m\}\+\\delta\\,\]\.

###### Proof\.

For eachm∈\{1,…,k\}m\\in\\\{1,\\dots,k\\\}define the triangular “hat” function

hm​\(x\)=1δ​\(ReLU​\(x−\(tm−δ\)\)−2​ReLU​\(x−tm\)\+ReLU​\(x−\(tm\+δ\)\)\)\.h\_\{m\}\(x\)\\;=\\;\\frac\{1\}\{\\delta\}\\Big\(\\mathrm\{ReLU\}\\big\(x\-\(t\_\{m\}\-\\delta\)\\big\)\\;\-\\;2\\,\\mathrm\{ReLU\}\(x\-t\_\{m\}\)\\;\+\\;\\mathrm\{ReLU\}\\big\(x\-\(t\_\{m\}\+\\delta\)\\big\)\\Big\)\.Eachhmh\_\{m\}is supported on\[tm−δ,tm\+δ\]\[t\_\{m\}\-\\delta,t\_\{m\}\+\\delta\], satisfieshm​\(tm\)=1h\_\{m\}\(t\_\{m\}\)=1, is linear on\[tm−δ,tm\]\[t\_\{m\}\-\\delta,t\_\{m\}\]and\[tm,tm\+δ\]\[t\_\{m\},t\_\{m\}\+\\delta\], and is0elsewhere\. Set

f​\(x\)=∑m=1khm​\(x\)\.f\(x\)\\;=\\;\\sum\_\{m=1\}^\{k\}h\_\{m\}\(x\)\.Choosingδ\>0\\delta\>0small enough ensures the supports\[tm−δ,tm\+δ\]\[t\_\{m\}\-\\delta,t\_\{m\}\+\\delta\]are pairwise disjoint, so at anyxxat most onehmh\_\{m\}is nonzero\. Hencef​\(tm\)=hm​\(tm\)=1f\(t\_\{m\}\)=h\_\{m\}\(t\_\{m\}\)=1for eachmm,f​\(x\)=0f\(x\)=0off⋃m=1k\[tm−δ,tm\+δ\]\\bigcup\_\{m=1\}^\{k\}\[t\_\{m\}\-\\delta,t\_\{m\}\+\\delta\], andffis piecewise linear with one triangular peak on each such interval\. The representation uses3​k3kReLU units in a single hidden layer, completing the construction\. ∎

### A\.2Proof of Lemma[5\.1](https://arxiv.org/html/2606.17522#S5.Thmtheorem1)and Lemma[5\.2](https://arxiv.org/html/2606.17522#S5.Thmtheorem2)

We start with a rigorous definition of the quantitiesEi,c¯​\(w¯\),Ei,c¯′​\(w¯\)E\_\{i,\\underline\{c\}\}\(\\underline\{w\}\),E^\{\\prime\}\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)andEi,c¯∗​\(w¯\)E^\{\*\}\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)introduced in Section[5\.1](https://arxiv.org/html/2606.17522#S5.SS1)\.

###### Definition A\.3\.

LetG=\(Σ,N,P,S\)G=\(\\Sigma,N,P,S\)be a context–free grammar of depthddand fix a derivation\-tree shapec¯\\underline\{c\}\. For an input sequencew¯=w1​⋯​wn∈Σ∗\\underline\{w\}=w\_\{1\}\\cdots w\_\{n\}\\in\\Sigma^\{\*\}define a sequence of stringsR\(1\)​\(w¯\),R\(2\)​\(w¯\),…,R\(d\)​\(w¯\)⊆\(Σ∪N\)∗\\,R^\{\(1\)\}\(\\underline\{w\}\),R^\{\(2\)\}\(\\underline\{w\}\),\\dots,R^\{\(d\)\}\(\\underline\{w\}\)\\subseteq\(\\Sigma\\\!\\cup\\\!N\)^\{\*\}inductively:

1. 1\.R\(1\)​\(w¯\)≔w¯R^\{\(1\)\}\(\\underline\{w\}\)\\coloneqq\\underline\{w\}, which corresponds to the leaves of the tree at depth11\.
2. 2\.For each leveli=1,…,d−1i=1,\\dots,d\-1, constructR\(i\+1\)​\(w¯\)R^\{\(i\+1\)\}\(\\underline\{w\}\)fromR\(i\)​\(w¯\)R^\{\(i\)\}\(\\underline\{w\}\)as follows\. Traverse the derivation tree shapec¯\\underline\{c\}at leveli\+1i\+1\. Whenever a non\-terminalAAat this level is the parent of a contiguous sequence of childrenγ\\gammaappearing in the derivation tree forR\(i\)​\(w¯\)R^\{\(i\)\}\(\\underline\{w\}\), replace those children by their parent nodeAA\. If there is no such non\-terminal symbol for that sequence of children, then we replace the sequenceγ\\gammawith the null symbol∅\\emptyset\. This operation is well\-defined becausec¯\\underline\{c\}fixes all parent–child relations and their left\-to\-right ordering in the tree\. Hence the resulting stringR\(i\+1\)​\(w¯\)R^\{\(i\+1\)\}\(\\underline\{w\}\)is unique\.

The resulting stringR\(d\)​\(w¯\)R^\{\(d\)\}\(\\underline\{w\}\)can be expressed uniquely as follows\. HereEi,c¯​\(w¯\)E\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)is the sequence consisting of non\-terminal symbols at levelii, and possibly some null symbols, appearing in the stringR\(d\)​\(w¯\)R^\{\(d\)\}\(\\underline\{w\}\)\.

R\(d\)​\(w¯\)=Ed,c¯​\(w¯\)​⋯​Ei,c¯​\(w¯\)​⋯​E1,c¯​\(w¯\)\.R^\{\(d\)\}\(\\underline\{w\}\)\\;=\\;E\_\{d,\\underline\{c\}\}\(\\underline\{w\}\)\\;\\cdots\\;E\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)\\;\\cdots\\;E\_\{1,\\underline\{c\}\}\(\\underline\{w\}\)\.IfEi,c¯​\(w¯\)E\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)is not the empty string, defineEi\+1,c¯∗​\(w¯\)=∅E^\{\*\}\_\{i\+1,\\underline\{c\}\}\(\\underline\{w\}\)=\\emptyset, andEi,c¯′​\(w¯\)=Ei,c¯​\(w¯\)E^\{\\prime\}\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)=E\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)\. IfEi,c¯​\(w¯\)E\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)is the empty string, we defineEi,c¯′​\(w¯\)E^\{\\prime\}\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)as the string obtained by concatenating all non\-terminals in theii\-th level of the derivation tree forw¯\\underline\{w\}with the same parent as the last non\-terminal symbol in that level, and defineEi\+1,c¯∗​\(w¯\)E^\{\*\}\_\{i\+1,\\underline\{c\}\}\(\\underline\{w\}\)to be the corresponding parent symbol in thei\+1i\+1\-st level of the derivation tree\.■\\blacksquare

###### Definition A\.4\.

Given a classc¯∈𝒞​\(𝒢\)\\underline\{c\}\\in\\mathcal\{C\}\(\\mathcal\{G\}\), let𝒮i​\(c¯\)\\mathcal\{S\}\_\{i\}\(\\underline\{c\}\)be the set of all stringsEi,c¯​\(w¯\)E\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)obtained from valid prefixesw¯\\underline\{w\}corresponding to the classc¯∈𝒞​\(𝒢\)\\underline\{c\}\\in\\mathcal\{C\}\(\\mathcal\{G\}\)\.

Example\.We revisit the context\-free grammar from Table[1](https://arxiv.org/html/2606.17522#S3.T1), and illustrate the above notation with an example\. Herec¯2\\underline\{c\}\_\{2\}is the shape corresponding to the second derivation tree in Figure[1](https://arxiv.org/html/2606.17522#S3.F1)\.

w¯2\\displaystyle\\underline\{w\}\_\{2\}=\(a6,a8,a3,a9,a10,a4,a5,a3,a1,a7,a9,a7,a8\)\\displaystyle=\(a\_\{6\},a\_\{8\},a\_\{3\},a\_\{9\},a\_\{10\},a\_\{4\},a\_\{5\},a\_\{3\},a\_\{1\},a\_\{7\},a\_\{9\},a\_\{7\},a\_\{8\}\)R\(1\)​\(w¯2\)\\displaystyle R^\{\(1\)\}\(\\underline\{w\}\_\{2\}\)=a32​a42​a52​a12​a22​a42,R\(2\)​\(w¯2\)=a23​a33​a42\\displaystyle=a\_\{3\}^\{2\}a\_\{4\}^\{2\}a\_\{5\}^\{2\}a\_\{1\}^\{2\}a\_\{2\}^\{2\}a\_\{4\}^\{2\},R^\{\(2\)\}\(\\underline\{w\}\_\{2\}\)=a\_\{2\}^\{3\}a\_\{3\}^\{3\}a\_\{4\}^\{2\}E3,c¯2​\(w¯2\)\\displaystyle E\_\{3,\\underline\{c\}\_\{2\}\}\(\\underline\{w\}\_\{2\}\)=E3,c¯2′​\(w¯2\)=a23​a33,E3,c¯2∗​\(w¯2\)=∅,E2,c¯2​\(w¯2\)=E2,c¯2′​\(w¯2\)=E2,c¯2∗​\(w¯2\)=a42\\displaystyle=E^\{\\prime\}\_\{3,\\underline\{c\}\_\{2\}\}\(\\underline\{w\}\_\{2\}\)=a\_\{2\}^\{3\}a\_\{3\}^\{3\},E^\{\*\}\_\{3,\\underline\{c\}\_\{2\}\}\(\\underline\{w\}\_\{2\}\)=\\emptyset,E\_\{2,\\underline\{c\}\_\{2\}\}\(\\underline\{w\}\_\{2\}\)=E^\{\\prime\}\_\{2,\\underline\{c\}\_\{2\}\}\(\\underline\{w\}\_\{2\}\)=E^\{\*\}\_\{2,\\underline\{c\}\_\{2\}\}\(\\underline\{w\}\_\{2\}\)=a\_\{4\}^\{2\}E1,c¯2​\(w¯2\)\\displaystyle E\_\{1,\\underline\{c\}\_\{2\}\}\(\\underline\{w\}\_\{2\}\)=∅,E1,c¯2′​\(w¯2\)=a7​a8■\\displaystyle=\\emptyset,E^\{\\prime\}\_\{1,\\underline\{c\}\_\{2\}\}\(\\underline\{w\}\_\{2\}\)=a\_\{7\}a\_\{8\}\\qquad\\blacksquare
We now prove Lemma[5\.1](https://arxiv.org/html/2606.17522#S5.Thmtheorem1)and Lemma[5\.2](https://arxiv.org/html/2606.17522#S5.Thmtheorem2)using a joint inductive argument\.

###### Proof of Lemma[5\.1](https://arxiv.org/html/2606.17522#S5.Thmtheorem1)\.

We proceed by induction on the layer, for a given input sequencew¯=w1​⋯​wn∈Σ∗\\underline\{w\}=w\_\{1\}\\cdots w\_\{n\}\\in\\Sigma^\{\*\}\. For the induction step, we assume that the claim in Lemma[5\.2](https://arxiv.org/html/2606.17522#S5.Thmtheorem2)is true for the previous layer \- i\.e\. that for eachj≤ij\\leq i, thejj\-th coordinate ofzi,c¯​\(w¯\)z\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)depends only on the stringEj,c¯​\(w¯\)E\_\{j,\\underline\{c\}\}\(\\underline\{w\}\)\.

The relative positional weightsRhR\_\{h\}for the attention head indexed byc¯\\underline\{c\}are chosen so that the last token attends only to earlier tokens corresponding to the non\-terminal symbols inEi\+1,c¯′​\(w¯\)E^\{\\prime\}\_\{i\+1,\\underline\{c\}\}\(\\underline\{w\}\)\. Because we omit the softmax function and instead use a positional attention mechanism, the other attention scores are zero\.

We choose the value matricesWh\(V\)W\_\{h\}^\{\(V\)\}so that the outputai\+1c¯​\(w¯\)a\_\{i\+1\}^\{\\underline\{c\}\}\(\\underline\{w\}\)of the attention head indexed byc¯\\underline\{c\}only depends on theii\-th coordinate of the vectorszi,c¯​\(w¯1:j\)z\_\{i,\\underline\{c\}\}\(\\underline\{w\}\_\{1:j\}\)for1≤j≤n1\\leq j\\leq n\. This can be done by having non\-zero values in the column of the value matrixWh\(V\)W\_\{h\}^\{\(V\)\}corresponding to that coordinate, and setting all other columns to zero\. By the induction hypothesis, it now follows that the outputai\+1c¯​\(w¯\)a\_\{i\+1\}^\{\\underline\{c\}\}\(\\underline\{w\}\)depends only on the quantityEi\+1,c¯′​\(w¯\)E^\{\\prime\}\_\{i\+1,\\underline\{c\}\}\(\\underline\{w\}\)\. ∎

In order to prove a similar statement without using the simplified relative positional encoding, one can follow the approach from the proof of Theorem 4\.1 inSvete and Cotterell \([2024](https://arxiv.org/html/2606.17522#bib.bib53)\), and use query\-key matrices that encode positional information\. This is achieved by placing the positional embeddings in a subspace that is disjoint from the word embeddings\. The query–key matrices act only on the positional subspace, so that the dot product between the query vector and key vector depends only on positional information\.

Given an input sequencew¯=\(wj\)1≤j≤k\\underline\{w\}=\(w\_\{j\}\)\_\{1\\leq j\\leq k\}, we denote byzi′​\(w¯\)z^\{\\prime\}\_\{i\}\(\\underline\{w\}\)its image after passing through theW\(O\)W^\{\(O\)\}matrix in theii\-th transformer block\. We decompose these vectorszi′​\(w¯\)z^\{\\prime\}\_\{i\}\(\\underline\{w\}\)intoccblocks as follows:zi′​\(w¯\)=\{zi,c¯′​\(w¯\)\}c¯∈𝒞​\(𝒢\)z^\{\\prime\}\_\{i\}\(\\underline\{w\}\)=\\\{z^\{\\prime\}\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)\\\}\_\{\\underline\{c\}\\in\\mathcal\{C\}\(\\mathcal\{G\}\)\}\. Herezi,c¯′​\(w¯\)∈ℝdz^\{\\prime\}\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)\\in\\mathbb\{R\}^\{d\}for eachc¯∈𝒞​\(𝒢\)\\underline\{c\}\\in\\mathcal\{C\}\(\\mathcal\{G\}\)\.

###### Proof of Lemma[5\.2](https://arxiv.org/html/2606.17522#S5.Thmtheorem2)\.

We again proceed by induction on the layerii\. For the induction step, we assume that the claim in Lemma[5\.1](https://arxiv.org/html/2606.17522#S5.Thmtheorem1)is true for the previous layer \- i\.e\. that the output vectoraic¯​\(w¯\)a\_\{i\}^\{\\underline\{c\}\}\(\\underline\{w\}\)of the attention head indexed byc¯\\underline\{c\}in theii\-th layer depends only onEi,c¯′​\(w¯\)E^\{\\prime\}\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)\.

We choose the concatenation matrixW\(O\)W^\{\(O\)\}, so that the following holds: for eachj<ij<i, thejj\-th coordinate ofzi,c¯′​\(w¯\)z^\{\\prime\}\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)depends only on the stringEj,c¯​\(w¯\)E\_\{j,\\underline\{c\}\}\(\\underline\{w\}\), theii\-th coordinate ofzi,c¯′​\(w¯\)z^\{\\prime\}\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)depends only on the stringEi,c¯′​\(w¯\)E^\{\\prime\}\_\{i,\\underline\{c\}\}\(\\underline\{w\}\), and thejj\-th coordinate ofzi,c¯′​\(w¯\)z^\{\\prime\}\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)is0whenj\>ij\>i\. This is done whenj≠ij\\neq iusing the residual skip connection, whereby the corresponding coordinates ofzi−1,c¯′​\(w¯\)z^\{\\prime\}\_\{i\-1,\\underline\{c\}\}\(\\underline\{w\}\)already satisfy these constraints, and theW\(O\)W^\{\(O\)\}matrix leaves those coordinates unchanged\. Whenj=ij=i, theW\(O\)W^\{\(O\)\}matrix maps the vectorsaic¯​\(w¯\)a\_\{i\}^\{\\underline\{c\}\}\(\\underline\{w\}\)to theii\-th coordinate ofzi,c¯′​\(w¯\)z^\{\\prime\}\_\{i,\\underline\{c\}\}\(\\underline\{w\}\); from Lemma[5\.1](https://arxiv.org/html/2606.17522#S5.Thmtheorem1), this quantity depends only on the stringEi,c¯′​\(w¯\)E^\{\\prime\}\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)\.

To complete the proof, we use the position\-wise feedforward network to modify theii\-th andi\+1i\+1\-st coordinates ofzi,c¯′​\(w¯\)z^\{\\prime\}\_\{i,\\underline\{c\}\}\(\\underline\{w\}\), and leave all other coordinates unchanged\. We constructFFusing Lemma[5\.3](https://arxiv.org/html/2606.17522#S5.Thmtheorem3)above, so that it satisfies the following for eachw¯\\underline\{w\}\(note that the superscripts denote the coordinate index of the corresponding vector inℝd\\mathbb\{R\}^\{d\}\)\. Here theii\-th coordinatezi,c¯\(i\)​\(w¯\)z^\{\(i\)\}\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)depends on the stringEi,c¯​\(w¯\)E\_\{i,\\underline\{c\}\}\(\\underline\{w\}\), while the\(i\+1\)\(i\+1\)\-st coordinatezi\+1,c¯\(i\)​\(w¯\)z^\{\(i\)\}\_\{i\+1,\\underline\{c\}\}\(\\underline\{w\}\)depends only on the stringEi\+1,c¯∗​\(w¯\)E^\{\*\}\_\{i\+1,\\underline\{c\}\}\(\\underline\{w\}\), and is0ifEi\+1,c¯∗​\(w¯\)=∅E^\{\*\}\_\{i\+1,\\underline\{c\}\}\(\\underline\{w\}\)=\\emptyset\.

FF​\(⋯,zi,c¯\(i\)′​\(w¯\),⋯\)=\(⋯,zi,c¯\(i\)​\(w¯\),zi\+1,c¯\(i\)​\(w¯\),⋯\)\\textbf\{FF\}\(\\cdots,z\_\{i,\\underline\{c\}\}^\{\{\}^\{\\prime\}\(i\)\}\(\\underline\{w\}\),\\cdots\)=\(\\cdots,z^\{\(i\)\}\_\{i,\\underline\{c\}\}\(\\underline\{w\}\),z^\{\(i\)\}\_\{i\+1,\\underline\{c\}\}\(\\underline\{w\}\),\\cdots\)In Lemma[5\.3](https://arxiv.org/html/2606.17522#S5.Thmtheorem3), note that the feedforward network requires at mostMMneurons, because there are at mostMMdifferent values ofzi,c¯\(i\)′​\(w¯\)z\_\{i,\\underline\{c\}\}^\{\{\}^\{\\prime\}\(i\)\}\(\\underline\{w\}\), corresponding to the possible values ofEi,c¯′​\(w¯\)E^\{\\prime\}\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)\. Note also that for eachj<ij<i, thejj\-th coordinate ofzi,c¯​\(w¯\)z\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)depends only on the stringEj,c¯​\(w¯\)E\_\{j,\\underline\{c\}\}\(\\underline\{w\}\), and thejj\-th coordinate ofzi,c¯​\(w¯\)z\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)is0whenj\>i\+1j\>i\+1, as the residual skip connection ensures that these coordinates remain unchanged\. ∎

### A\.3Using stacked feedforward networks for next\-word prediction: proofs

We elaborate on the notation introduced in Section[5\.3](https://arxiv.org/html/2606.17522#S5.SS3), and define the setsNd−i\+1,c¯​\(w¯\)N\_\{d\-i\+1,\\underline\{c\}\}\(\\underline\{w\}\)rigorously below\. In Lemma[A\.6](https://arxiv.org/html/2606.17522#A1.Thmtheorem6)below, we show how these can be computed using a feedforward neural network\.

###### Definition A\.5\.

Given an input sequencew¯\\underline\{w\}and1≤i≤d1\\leq i\\leq d, consider the string of symbols obtained by concatenatingEd,c¯​\(w¯\)E\_\{d,\\underline\{c\}\}\(\\underline\{w\}\),Ed−1,c¯​\(w¯\),…,Ed−i\+1,c¯​\(w¯\)E\_\{d\-1,\\underline\{c\}\}\(\\underline\{w\}\),\.\.\.,E\_\{d\-i\+1,\\underline\{c\}\}\(\\underline\{w\}\)\. We define the setNd−i\+1,c¯​\(w¯\)N\_\{d\-i\+1,\\underline\{c\}\}\(\\underline\{w\}\)as the set of all non\-terminals ofNd−i\+1N\_\{d\-i\+1\}that can be appended to this string to yield a sequence which can be expanded into a valid sentence\.

###### Lemma A\.6\.

We construct a feedforward neural network with5​d\+75d\+7hidden layers that has the following properties; herehi​\(w¯\)h\_\{i\}\(\\underline\{w\}\)denotes the image of an input sequencew¯\\underline\{w\}after passing through theii\-th feedforward layer in the sequence\. Each of the layers has at most4​c​B​M24cBM^\{2\}neurons\. Recall thatMMis the maximal rule count,BBis the maximal branching factor, andc=\|𝒞​\(𝒢\)\|c=\|\\mathcal\{C\}\(\\mathcal\{G\}\)\|\.

- •The neurons ofh1,c¯h\_\{1,\\underline\{c\}\}are divided intoddblocks\. For each1≤i≤d1\\leq i\\leq d, theii\-th block ofh1,c¯h\_\{1,\\underline\{c\}\}has\|𝒮i​\(c¯\)\|\|\\mathcal\{S\}\_\{i\}\(\\underline\{c\}\)\|neurons\.
- •The blockh2,c¯h\_\{2,\\underline\{c\}\}of the second layer indexed by the classc¯\\underline\{c\}hasddneurons which satisfy the following conditions\. IfEj,c¯​\(w¯\)E\_\{j,\\underline\{c\}\}\(\\underline\{w\}\)does not contain any null symbols, then the value of thejj\-th neuron ofh2,c¯​\(w¯\)h\_\{2,\\underline\{c\}\}\(\\underline\{w\}\)is equal to thejj\-th coordinate ofzd,c¯​\(w¯\)z\_\{d,\\underline\{c\}\}\(\\underline\{w\}\)\. IfEj,c¯​\(w¯\)E\_\{j,\\underline\{c\}\}\(\\underline\{w\}\)contains any null symbols, then the value of thejj\-th neuron ofh2,c¯​\(w¯\)h\_\{2,\\underline\{c\}\}\(\\underline\{w\}\)is0\.
- •For each0≤i≤d0\\leq i\\leq d, the neurons ofh5​i\+2,c¯​\(w¯\)h\_\{5i\+2,\\underline\{c\}\}\(\\underline\{w\}\)are divided intoddblocks\. For eachj≤d−ij\\leq d\-i, thejj\-th block ofh5​i\+2,c¯​\(w¯\)h\_\{5i\+2,\\underline\{c\}\}\(\\underline\{w\}\)has a single neuron, whose value is equal to thejj\-th coordinate ofh2,c¯h\_\{2,\\underline\{c\}\}\. For eachj\>d−i\+1j\>d\-i\+1, thejj\-th block ofh5​i\+2,c¯​\(w¯\)h\_\{5i\+2,\\underline\{c\}\}\(\\underline\{w\}\)has a single neuron, which is equal to0\. Ifi\>0i\>0, the\(d−i\+1\)\(d\-i\+1\)\-st block ofh5​i\+2,c¯h\_\{5i\+2,\\underline\{c\}\}has\|Nd−i\+1\|\|N\_\{d\-i\+1\}\|neurons\. In this block, a neuron inh5​i\+2,c¯​\(w¯\)h\_\{5i\+2,\\underline\{c\}\}\(\\underline\{w\}\)has value11if the corresponding symbol inNd−i\+1N\_\{d\-i\+1\}is in the setNd−i\+1,c¯​\(w¯\)N\_\{d\-i\+1,\\underline\{c\}\}\(\\underline\{w\}\), and0otherwise\.
- •For each0≤i≤d−10\\leq i\\leq d\-1, the neurons ofh5​i\+3,c¯​\(w¯\)h\_\{5i\+3,\\underline\{c\}\}\(\\underline\{w\}\)andh5​i\+4,c¯​\(w¯\)h\_\{5i\+4,\\underline\{c\}\}\(\\underline\{w\}\)are divided intoddblocks\. For eachj≠d−i\+1j\\neq d\-i\+1, thejj\-th blocks ofh5​i\+3,c¯​\(w¯\)h\_\{5i\+3,\\underline\{c\}\}\(\\underline\{w\}\)andh5​i\+4,c¯​\(w¯\)h\_\{5i\+4,\\underline\{c\}\}\(\\underline\{w\}\)have a single neuron, which takes the same value as the corresponding neuron inh5​i\+2,c¯​\(w¯\)h\_\{5i\+2,\\underline\{c\}\}\(\\underline\{w\}\)\. Ifi\>0i\>0, the\(d−i\+1\)\(d\-i\+1\)\-st blocks ofh5​i\+3,c¯​\(w¯\)h\_\{5i\+3,\\underline\{c\}\}\(\\underline\{w\}\)andh5​i\+4,c¯​\(w¯\)h\_\{5i\+4,\\underline\{c\}\}\(\\underline\{w\}\)are divided into sub\-blocks, with one sub\-block for each non\-terminal symbol inNd−i\+1N\_\{d\-i\+1\}\. Givenn∈Nd−i\+1n\\in N\_\{d\-i\+1\}, the number of neurons in the corresponding sub\-block ofh5​i\+3,c¯​\(w¯\)h\_\{5i\+3,\\underline\{c\}\}\(\\underline\{w\}\)\(resp\.h5​i\+4,c¯​\(w¯\)h\_\{5i\+4,\\underline\{c\}\}\(\\underline\{w\}\)\) is equal to4​\|𝒮d−i​\(c¯\)\|4\|\\mathcal\{S\}\_\{d\-i\}\(\\underline\{c\}\)\|\(resp\.4​\|Nd−i\|4\|N\_\{d\-i\}\|\)\.
- •For each0≤i≤d−10\\leq i\\leq d\-1, the neurons ofh5​i\+5,c¯​\(w¯\)h\_\{5i\+5,\\underline\{c\}\}\(\\underline\{w\}\)are divided intoddblocks\. For eachj≤d−i−1j\\leq d\-i\-1, thejj\-th block ofh5​i\+5,c¯​\(w¯\)h\_\{5i\+5,\\underline\{c\}\}\(\\underline\{w\}\)has a single neuron, whose value is equal to thejj\-th coordinate ofh2,c¯​\(w¯\)h\_\{2,\\underline\{c\}\}\(\\underline\{w\}\)\. For eachj≥d−i\+1j\\geq d\-i\+1, thejj\-th block ofh5​i\+5,c¯​\(w¯\)h\_\{5i\+5,\\underline\{c\}\}\(\\underline\{w\}\)has a single neuron, which is equal to0\. The\(d−i\)\(d\-i\)\-st block ofh5​i\+5,c¯​\(w¯\)h\_\{5i\+5,\\underline\{c\}\}\(\\underline\{w\}\)has\|Nd−i\|\|N\_\{d\-i\}\|neurons\.
- •For each0≤i≤d−10\\leq i\\leq d\-1, the neurons ofh5​i\+6,c¯​\(w¯\)h\_\{5i\+6,\\underline\{c\}\}\(\\underline\{w\}\)are divided intoddblocks\. For eachj≤d−i−1j\\leq d\-i\-1, thejj\-th block ofh5​i\+6,c¯​\(w¯\)h\_\{5i\+6,\\underline\{c\}\}\(\\underline\{w\}\)has a single neuron, whose value is equal to thejj\-th coordinate ofh2,c¯​\(w¯\)h\_\{2,\\underline\{c\}\}\(\\underline\{w\}\)\. For eachj≥d−i\+1j\\geq d\-i\+1, thejj\-th block ofh5​i\+6,c¯​\(w¯\)h\_\{5i\+6,\\underline\{c\}\}\(\\underline\{w\}\)has a single neuron, which is equal to0\. The\(d−i\)\(d\-i\)\-st block ofh5​i\+6,c¯​\(w¯\)h\_\{5i\+6,\\underline\{c\}\}\(\\underline\{w\}\)is divided into sub\-blocks, with one sub\-block for each non\-terminal symbol inNd−iN\_\{d\-i\}, and each sub\-block having at most3​M3Mneurons\.

###### Proof of Lemma[A\.6](https://arxiv.org/html/2606.17522#A1.Thmtheorem6)\.

We proceed by induction onii\. For the base case, observe thatNd,c¯​\(w¯\)N\_\{d,\\underline\{c\}\}\(\\underline\{w\}\)can be computed directly fromEd,c¯​\(w¯\)E\_\{d,\\underline\{c\}\}\(\\underline\{w\}\)\. This computation is performed by the first block of the feedforward neural network\. For the induction step, note thatNd−i,c¯​\(w¯\)N\_\{d\-i,\\underline\{c\}\}\(\\underline\{w\}\)can be determined fromNd−i\+1,c¯​\(w¯\)N\_\{d\-i\+1,\\underline\{c\}\}\(\\underline\{w\}\)together withEd−i,c¯​\(w¯\)E\_\{d\-i,\\underline\{c\}\}\(\\underline\{w\}\)\. This computation is carried out by the four layers in theii\-th block of the feedforward neural network\.

Step 1\.We first construct the weights in the first two layers as follows\. For eachiiwith1≤i≤d1\\leq i\\leq d, the neurons in theii\-th block ofh1,c¯h\_\{1,\\underline\{c\}\}are connected to theii\-th neurons of the input vectorzd,c¯​\(w¯\)z\_\{d,\\underline\{c\}\}\(\\underline\{w\}\), and theii\-th neuron of the next layerh2,c¯h\_\{2,\\underline\{c\}\}\. We construct the weights connecting these neurons using Lemma[A\.2](https://arxiv.org/html/2606.17522#A1.Thmtheorem2)\. Recall that theii\-th coordinate ofzd,c¯​\(w¯\)z\_\{d,\\underline\{c\}\}\(\\underline\{w\}\)is determined by the stringEi,c¯​\(w¯\)E\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)ifw¯\\underline\{w\}has typec¯\\underline\{c\}, and this string is an element of𝒮i​\(c¯\)\\mathcal\{S\}\_\{i\}\(\\underline\{c\}\)\. In Lemma[A\.2](https://arxiv.org/html/2606.17522#A1.Thmtheorem2), we setk=𝒮i​\(c¯\)k=\\mathcal\{S\}\_\{i\}\(\\underline\{c\}\), and sett1,⋯,tkt\_\{1\},\\cdots,t\_\{k\}to be the values ofzd,c¯​\(w¯\)z\_\{d,\\underline\{c\}\}\(\\underline\{w\}\)corresponding to the strings in𝒮i​\(c¯\)\\mathcal\{S\}\_\{i\}\(\\underline\{c\}\)\. We setδ\\deltato be sufficiently small so that if the stringEi,c¯​\(w¯\)E\_\{i,\\underline\{c\}\}\(\\underline\{w\}\)has null values, the corresponding value ofzd,c¯​\(w¯\)z\_\{d,\\underline\{c\}\}\(\\underline\{w\}\)is mapped to0since it falls outside of the intervals\[tm−δ,tm\+δ\]\[t\_\{m\}\-\\delta,t\_\{m\}\+\\delta\]\.

Step 2\.For a givenii, we now construct the weights connecting the neurons in layers5​i\+2,5​i\+3,5​i\+45i\+2,5i\+3,5i\+4and5​i\+55i\+5\. Our construction enforces this whenj≠d−i,d−i\+1j\\neq d\-i,d\-i\+1using an identity connection, as the value remains unchanged\. For each non\-terminaln∈Nd−i\+1n\\in N\_\{d\-i\+1\}, consider the two neurons inh5​i\+2,c¯​\(w¯\)h\_\{5i\+2,\\underline\{c\}\}\(\\underline\{w\}\)corresponding tonnand the\(d−i\)\(d\-i\)\-th coordinate ofzd,c¯​\(w¯\)z\_\{d,\\underline\{c\}\}\(\\underline\{w\}\), the neurons in the sub\-block of the\(d−i\+1\)\(d\-i\+1\)\-st blocks ofh5​i\+3,c¯​\(w¯\)h\_\{5i\+3,\\underline\{c\}\}\(\\underline\{w\}\)andh5​i\+4,c¯​\(w¯\)h\_\{5i\+4,\\underline\{c\}\}\(\\underline\{w\}\)corresponding tonn, and the neurons in the\(d−i\)\(d\-i\)\-th block ofh5​i\+5,c¯​\(w¯\)h\_\{5i\+5,\\underline\{c\}\}\(\\underline\{w\}\)\. We choose the weights connecting these neurons using Lemma[A\.1](https://arxiv.org/html/2606.17522#A1.Thmtheorem1)as follows\.

For each non\-terminaln∈Nd−i\+1n\\in N\_\{d\-i\+1\}, we use Lemma[A\.1](https://arxiv.org/html/2606.17522#A1.Thmtheorem1)with the input\-output pairs\(xs,ys\)i=1K\(x\_\{s\},y\_\{s\}\)\_\{i=1\}^\{K\}chosen as follows\. Here the input vectors arexs∈ℝ2x\_\{s\}\\in\\mathbb\{R\}^\{2\}, with the first coordinate being equal to the\(d−i\)\(d\-i\)\-th coordinate ofzd,c¯​\(w¯\)z\_\{d,\\underline\{c\}\}\(\\underline\{w\}\)and the second coordinate being equal to either11or0\. The output vectors areys∈ℝ\|Nd−i\|y\_\{s\}\\in\\mathbb\{R\}^\{\|N\_\{d\-i\}\|\}, where the coordinate corresponding tond−i∈Nd−in\_\{d\-i\}\\in N\_\{d\-i\}takes the value11if the second coordinate ofxsx\_\{s\}is11and there is a production rule fornnwhere the right\-hand side starts with the stringEd−i,c¯​\(w¯\)\+nd−iE\_\{d\-i,\\underline\{c\}\}\(\\underline\{w\}\)\+n\_\{d\-i\}; and otherwise that coordinate takes the value0\. Since the\(d−i\)\(d\-i\)\-th coordinate ofzd,c¯​\(w¯\)z\_\{d,\\underline\{c\}\}\(\\underline\{w\}\)depends only onEd−i,c¯​\(w¯\)E\_\{d\-i,\\underline\{c\}\}\(\\underline\{w\}\), the total number of input\-output pairs is equal to2​\|𝒮d−i​\(c¯\)\|2\|\\mathcal\{S\}\_\{d\-i\}\(\\underline\{c\}\)\|\. Using Lemma[A\.1](https://arxiv.org/html/2606.17522#A1.Thmtheorem1), we can memorize these input\-output pairs using a feedforward network with two hidden layers where the first hidden layer has4​\|𝒮d−i​\(c¯\)\|4\|\\mathcal\{S\}\_\{d\-i\}\(\\underline\{c\}\)\|neurons, and the second hidden layer has4​\|Nd−i\|4\|N\_\{d\-i\}\|neurons\.

After using this construction to choose the weights connecting these neurons for each non\-terminaln∈Nd−i\+1n\\in N\_\{d\-i\+1\}, it follows by summing over these non\-terminals that the neuron inh5​i\+5,c¯​\(w¯\)h\_\{5i\+5,\\underline\{c\}\}\(\\underline\{w\}\)corresponding to a non\-terminal symbolnd−i∈Nd−in\_\{d\-i\}\\in N\_\{d\-i\}takes the valuerr, whererris the number of non\-terminals inNd−i\+1,c¯​\(w¯\)N\_\{d\-i\+1,\\underline\{c\}\}\(\\underline\{w\}\)which have a production rule where the right\-hand side starts with the stringEd−i,c¯​\(w¯\)\+nd−iE\_\{d\-i,\\underline\{c\}\}\(\\underline\{w\}\)\+n\_\{d\-i\}\. The total number of neurons inh5​i\+4,c¯​\(w¯\)h\_\{5i\+4,\\underline\{c\}\}\(\\underline\{w\}\)is4​\|Nd−i\|​\|Nd−i\+1\|4\|N\_\{d\-i\}\|\|N\_\{d\-i\+1\}\|, and the total number of neurons inh5​i\+3,c¯​\(w¯\)h\_\{5i\+3,\\underline\{c\}\}\(\\underline\{w\}\)is4​\|Nd−i\+1\|​\|𝒮d−i​\(c¯\)\|4\|N\_\{d\-i\+1\}\|\|\\mathcal\{S\}\_\{d\-i\}\(\\underline\{c\}\)\|\. Note that these quantities are less than4​B​M24BM^\{2\}\(recall here thatBBis the maximal branching factor, andMMis the maximal rule count for a fixed depth\), since\|Nd−i\+1\|<M\|N\_\{d\-i\+1\}\|<Mand\|𝒮d−i​\(c¯\)\|<B​M\|\\mathcal\{S\}\_\{d\-i\}\(\\underline\{c\}\)\|<BM\.

Step 3\.Recall that the\(d−i\)\(d\-i\)\-th blocks ofh5​i\+5,c¯​\(w¯\)h\_\{5i\+5,\\underline\{c\}\}\(\\underline\{w\}\)andh5​i\+7,c¯​\(w¯\)h\_\{5i\+7,\\underline\{c\}\}\(\\underline\{w\}\)have\|Nd−i\|\|N\_\{d\-i\}\|neurons\. We choose the weights connecting the\(d−i\)\(d\-i\)\-th blocks ofh5​i\+5,c¯​\(w¯\)h\_\{5i\+5,\\underline\{c\}\}\(\\underline\{w\}\)andh5​i\+6,c¯​\(w¯\)h\_\{5i\+6,\\underline\{c\}\}\(\\underline\{w\}\), and the weights connecting the\(d−i\)\(d\-i\)\-st blocks ofh5​i\+6,c¯​\(w¯\)h\_\{5i\+6,\\underline\{c\}\}\(\\underline\{w\}\)andh5​i\+7,c¯​\(w¯\)h\_\{5i\+7,\\underline\{c\}\}\(\\underline\{w\}\), using Lemma[A\.2](https://arxiv.org/html/2606.17522#A1.Thmtheorem2)\. This is done so that for eachnd−i∈Nd−in\_\{d\-i\}\\in N\_\{d\-i\}, if the corresponding neuron inh5​i\+5,c¯​\(w¯\)h\_\{5i\+5,\\underline\{c\}\}\(\\underline\{w\}\)has value 0 \(respectively, an integer value between11andMM\), then the corresponding neuron inh5​i\+7,c¯​\(w¯\)h\_\{5i\+7,\\underline\{c\}\}\(\\underline\{w\}\)has value0\(respectively,11\)\. We use Lemma[A\.2](https://arxiv.org/html/2606.17522#A1.Thmtheorem2), withtj=jt\_\{j\}=jfor each1≤j≤M1\\leq j\\leq M, to construct a block of3​M3Mneurons in the layerh5​i\+6,c¯​\(w¯\)h\_\{5i\+6,\\underline\{c\}\}\(\\underline\{w\}\), for each non\-terminalnd−i∈Nd−in\_\{d\-i\}\\in N\_\{d\-i\}, so that this condition is satisfied\. ∎

### A\.4Completing the proof of Theorem[4\.1](https://arxiv.org/html/2606.17522#S4.Thmtheorem1)\.

To complete the proof of Theorem[4\.1](https://arxiv.org/html/2606.17522#S4.Thmtheorem1), we construct a linear mapping sending the output of the final layer in the feedforward network constructed above to the vector of logits that encodes the next\-word probabilities\. Recall that the output of the final layer ish5​d\+2​\(w¯\)=\(h5​d\+2,c¯​\(w¯\)\)c¯∈𝒞​\(𝒢\)h\_\{5d\+2\}\(\\underline\{w\}\)=\(h\_\{5d\+2,\\underline\{c\}\}\(\\underline\{w\}\)\)\_\{\\underline\{c\}\\in\\mathcal\{C\}\(\\mathcal\{G\}\)\}, where eachh5​d\+2,c¯​\(w¯\)h\_\{5d\+2,\\underline\{c\}\}\(\\underline\{w\}\)consists ofddblocks\. For eachi≥2i\\geq 2, theii\-th block has a single neuron which is0\. By construction, the first block has\|N1\|\|N\_\{1\}\|neurons, which correspond to the terminal symbols; a neuron has value11if the corresponding terminal symbol is in the setN1,c¯​\(w¯\)N\_\{1,\\underline\{c\}\}\(\\underline\{w\}\)\(and0otherwise\)\. We construct a linear mapping that connects the neuronh5​d\+2,c¯​\(w¯\)h\_\{5d\+2,\\underline\{c\}\}\(\\underline\{w\}\)corresponding to a given terminal symbol to the corresponding neuron in the output layer for eachc¯\\underline\{c\}with a fixed weightα\\alpha\. For all other pairs of neurons, the weight has value0\.

It follows that the logits in the output layer corresponding to a given terminal symbol take a strictly positive value if the terminal symbol lies inS​\(w¯\)S\(\\underline\{w\}\), and are otherwise zero\. Following Definition[3\.4](https://arxiv.org/html/2606.17522#S3.Thmtheorem4), for a givenϵ\>0\\epsilon\>0, we can choose a sufficiently large value ofα\\alphaso that the below inequality holds after applying the softmax\. It follows that the transformer language modelf𝒯f\_\{\\mathcal\{T\}\}predictively models the languageℒ\\mathcal\{L\}with error at mostϵ\\epsilon, as required\.

∑w∉S​\(w¯\)f𝒯^​\(w∣w¯\)<ϵ\.\\sum\_\{w\\notin S\(\\underline\{w\}\)\}\\hat\{f\_\{\\mathcal\{T\}\}\}\(w\\mid\\underline\{w\}\)\\;<\\;\\epsilon\.