基于有界深度文法的深度Transformer层次建模表达性分析

# 深度变压器中层级建模的表达性分析：基于有界深度文法

**来源：** https://arxiv.org/html/2606.17522

**Vinoth Nandakumar** <[email protected]> 悉尼大学  
**Qiang Qu** <[email protected]> 悉尼大学  
**Pramod Thebe** <[email protected]> 旧金山州立大学  
**Sakshi Khachariya** <[email protected]> 印度理工学院马德拉斯分校  
**Tongliang Liu** <[email protected]> 悉尼大学  

###### 摘要

深度神经网络被广泛认为其表达能力源于形成层级化表示的能力，即跨层捕获日益抽象且具有组合性的特征。在语言建模中，**Transformer**已成为主导架构，其浅层捕获局部句法模式，深层则编码更复杂的从句级依赖关系。虽然这一直觉指导了模型设计，但缺乏严格的理论工作来证明深度Transformer如何表示这种层级结构。在本工作中，我们通过有界深度、非递归的上下文无关文法这一形式化框架，分析了深度Transformer模型的表达能力。对于这类文法，我们显式构造了具有位置注意力的Transformer，其深度随文法深度线性增长，而神经元数量与派生树形状的数量呈线性关系，与产生式规则数量的平方呈线性关系。我们的理论结果支持线性表示假设，证明了这些架构具备结构能力，能够将抽象语法状态编码到残差流中低维、线性可分的子空间内。

## 1 引言

在过去的二十年里，深度学习的突破性进展彻底变革了自然语言处理任务，如语言建模 (Brown 等, 2020 (https://arxiv.org/html/2606.17522#bib.bib2); Devlin 等, 2019 (https://arxiv.org/html/2606.17522#bib.bib15); Hoffmann 等, 2022 (https://arxiv.org/html/2606.17522#bib.bib27))、问答 (Lan 等, 2020 (https://arxiv.org/html/2606.17522#bib.bib30); Beltagy 等, 2020 (https://arxiv.org/html/2606.17522#bib.bib6); Zaheer 等, 2020 (https://arxiv.org/html/2606.17522#bib.bib63)) 以及机器翻译 (Vaswani 等, 2017 (https://arxiv.org/html/2606.17522#bib.bib57); Costa-Jussà 等, 2022 (https://arxiv.org/html/2606.17522#bib.bib14); Fan 等, 2020 (https://arxiv.org/html/2606.17522#bib.bib20))。在深度学习出现之前，基于规则的方法广泛用于下一个词预测，但神经语言模型此后在复杂任务上持续展现出更优性能 (Bengio 等, 2003 (https://arxiv.org/html/2606.17522#bib.bib7))。Transformer以其自注意力机制为特征，通过使模型能够并行处理整个序列并动态关注远距离依赖，进一步推动了该领域的发展——这是早期循环或卷积方法难以实现的能力 (Devlin 等, 2019 (https://arxiv.org/html/2606.17522#bib.bib15); Brown 等, 2020 (https://arxiv.org/html/2606.17522#bib.bib2))。尽管更大的模型和新颖的架构不断带来经验性收益 (Raffel 等, 2020 (https://arxiv.org/html/2606.17522#bib.bib46); Hoffmann 等, 2022 (https://arxiv.org/html/2606.17522#bib.bib27))，但我们仍然缺乏坚实的理论基础来解释Transformer为何能如此有效地捕获语言的复杂层级结构。

自然语言具有层级结构，这可以通过上下文无关文法来表示：句子由短语组成，短语由子短语或单词组成 (Chomsky, 1957 (https://arxiv.org/html/2606.17522#bib.bib17))。虽然递归允许有效句子的空间无限增长，但人类的认知限制通常将解析限制在有界深度内。层级化表示利用了这种结构，使模型能够将序列分解为更小的子序列，从而显著减少所需参数的数量 (Poggio 等, 2017 (https://arxiv.org/html/2606.17522#bib.bib44))。尽管先前的工作表明深度网络可以利用这种组合结构 (Mossel, 2016 (https://arxiv.org/html/2606.17522#bib.bib24))，但它们主要集中在受限设置上，例如Dyck语言 (Hahn, 2020 (https://arxiv.org/html/2606.17522#bib.bib23); Yao 等, 2021 (https://arxiv.org/html/2606.17522#bib.bib58)) 和有限状态自动机 (Liu 等, 2023 (https://arxiv.org/html/2606.17522#bib.bib31))，这些缺乏现实文法的复杂分支结构。

近期的经验研究表明，Transformer能够内化复杂的句法和语义结构，为**线性表示假设**提供了有力支持。例如，Saglam 等 (2025 (https://arxiv.org/html/2606.17522#bib.bib48)) 证明了大语言模型将高级语义域编码到低维、线性可分的子空间中，这种可分性在网络深层变得尤为明显。同时，Allen-Zhu 和 Li (2025 (https://arxiv.org/html/2606.17522#bib.bib4)) 以及 Zhao 等 (2023 (https://arxiv.org/html/2606.17522#bib.bib65)) 表明，在合成上下文无关文法 (CFG) 上训练的Transformer可以通过线性探针恢复隐式的非终结符，进一步表明抽象的层级规则被编码为残差流中的线性方向。虽然这些工作经验性地验证了线性表示假设，但它们在理论上并未解释为什么Transformer架构具备在低维线性子空间中显式表示这些复杂语法结构的结构能力。

**贡献。** 为了解决这些局限性，我们通过长度统一、固定深度的非递归上下文无关文法 (CFG) 这一形式化框架来分析Transformer语言模型，该设置使得层级关系变得显式 (Strobl 等, 2024 (https://arxiv.org/html/2606.17522#bib.bib51); Ackerman 和 Cybenko, 2020 (https://arxiv.org/html/2606.17522#bib.bib1))。对于这类CFG，我们给出了Transformer架构的*显式*构造，该架构具有位置注意力机制，其深度随文法深度线性增长，而神经元数量与有效派生树形状的数量 \(c\) 呈线性关系，与产生式规则数量的平方呈线性关系。我们注意到，我们的简化框架可用于分析层级组合性，因为即使树形状数量受限，底层文法也能生成指数级数量的唯一句子。我们的框架提供了一个严格的存在性证明，与层级语言建模背景下的“线性表示假设”兼容。我们正式证明该架构具备将复杂语法结构编码到低维空间的能力，其中给定深度的任何非终结符都被映射到对应残差流子空间中的一个向量。虽然经验模型通过密集叠加实现了这一点 (Garg 等, 2026 (https://arxiv.org/html/2606.17522#bib.bib21); Saglam 等, 2025 (https://arxiv.org/html/2606.17522#bib.bib48))，但我们的构造采用了一个具有正交基空间的简化模型。我们构造的Transformer自然地实现了 Allen-Zhu 和 Li (2025 (https://arxiv.org/html/2606.17522#bib.bib4)) 中描述的用于解析CFG的自底向上动态规划算法。我们的证明依赖于硬编码的注意力头，它们聚合局部句法上下文，反映了在训练模型中经验观察到的树构建注意模式 (Allen-Zhu 和 Li, 2025 (https://arxiv.org/html/2606.17522#bib.bib4))。

**论文组织。** 第2节总结了关于层级建模和形式语言理论的相关工作。第3节定义了我们分析的CFG类别（附示例），并正式表述了Transformer模型的问题设置。在第4节和第5节中，我们给出了主要的表达性结果，展示了深度Transformer能够解决固定深度上下文无关文法的下一个词预测问题，并概述了描述注意力头和前馈层功能的构造性证明。第6节讨论了局限性和未来方向。附录提供了我们理论结果的详细证明。

## 2 相关工作

**通过深度学习进行层级表示。** 越来越多的工作研究了深度学习模型中层级表示的作用。人们已经清楚，深度网络可以紧凑地表示层级函数，使用的参数远少于浅层网络 (Poggio 等, 2017 (https://arxiv.org/html/2606.17522#bib.bib44); Zhao 等, 2017 (https://arxiv.org/html/2606.17522#bib.bib66))。在某些设置中，基于层级结构的生成模型已被证明可以通过基于聚类的技术进行学习 (Mossel, 2016 (https://arxiv.org/html/2606.17522#bib.bib24); Malach 和 Shalev-Shwartz, 2018 (https://arxiv.org/html/2606.17522#bib.bib33); 2020 (https://arxiv.org/html/2606.17522#bib.bib34))。近期的工作进一步表明，通过梯度下降训练的深度网络可以隐式地发现这些潜在的层级结构 (Allen-Zhu 和 Li, 2025 (https://arxiv.org/html/2606.17522#bib.bib4); Tomasini 和 Wyart, 2024 (https://arxiv.org/html/2606.17522#bib.bib56); Garnier-Brun 等, 2025 (https://arxiv.org/html/2606.17522#bib.bib22))。我们通过CFG的数学框架研究Transformer模型如何表示层级结构，该形式体系非常适合建模自然语言。

**使用Transformer建模形式语言。** 几项近期工作从形式语言理论的角度探索了Transformer模型的计算能力。Perez 等 (2021 (https://arxiv.org/html/2606.17522#bib.bib43)) 表明编码器-解码器Transformer能够识别类 \(\mathsf{P}\) 中的所有语言，即那些可由确定性图灵机在多项式时间内判定的语言。该结果在 Bhattamishra 等 (2020b (https://arxiv.org/html/2606.17522#bib.bib9))、Merrill 和 Sabharwal (2024 (https://arxiv.org/html/2606.17522#bib.bib38)) 以及 Sarrof 等 (2024 (https://arxiv.org/html/2606.17522#bib.bib49))、Yang 等 (2024 (https://arxiv.org/html/2606.17522#bib.bib59)) 中得到了改进，它为哪些形式语言可以被Transformer架构建模提供了少数已知的表征之一。近期工作还研究了基于注意力的模型识别形式语言的能力，例如 Dyck\(_k\)（具有 \(k\) 种类型完美平衡括号的语言）(Hahn, 2020 (https://arxiv.org/html/2606.17522#bib.bib23); Yao 等, 2021 (https://arxiv.org/html/2606.17522#bib.bib58); Bhattamishra 等, 2020a (https://arxiv.org/html/2606.17522#bib.bib8))，以及Transformer是否能识别复杂度类 \(\mathsf{AC}^0\) 中的形式语言 (Hao 等, 2022 (https://arxiv.org/html/2606.17522#bib.bib28); Barcelo 等, 2024 (https://arxiv.org/html/2606.17522#bib.bib5))，该类由常数深度、多项式大小的布尔电路族可识别的语言组成。本工作与 Zhao 等 (2023 (https://arxiv.org/html/2606.17522#bib.bib65))（表明Transformer可以实现CFG的内外解析算法）以及 Liu 等 (2023 (https://arxiv.org/html/2606.17522#bib.bib31))（通过有限状态自动机的视角分析Transformer的深度表达性）最为相关。在这些结果的基础上，我们建立了Transformer深度与底层文法深度之间的直接联系，并获得了表示特定类别CFG所需Transformer规模的新上界。

## 3 问题设置

### 3.1 语言建模的预备知识

我们首先遵循 Sarrof 等 (2024 (https://arxiv.org/html/2606.17522#bib.bib49)) 的形式化方法来定义语言建模任务。

###### 定义 3.1。**词汇表** \(\Sigma\) 是一个由所有单词组成的有限集合。令 \(\Sigma^*\) 表示由 \(\Sigma\) 中单词组成的所有有限序列的集合。给定词汇表 \(\Sigma\)，**语言** \(\mathcal{L}\) 是 \(\Sigma^*\) 的一个子集；其元素称为句子。■

###### 定义 3.2。给定词汇表 \(\Sigma\)，**语言模型** 是一个函数 \(f\)，它接受任意序列 \(\underline{w} \in \Sigma^*\)，并输出一个概率向量 \(f(\underline{w}) = (\hat{f}(w|\underline{w}))_{w \in \Sigma}\)。这里 \(\hat{f}(w|\underline{w})\) 表示给定输入序列 \(\underline{w}\) 时，模型 \(f\) 输出单词 \(w\) 的概率。■

许多理论论文研究识别问题 (Bhattamishra 等, 2020a (https://arxiv.org/html/2606.17522#bib.bib8))，其中语言模型必须判定一个完整字符串是否属于给定语言。然而，近期语言建模的经验性工作集中于下一个词预测。我们关注预测建模问题，并定义 \(f\) 对给定语言 \(\mathcal{L}\) 进行建模的含义（注意，识别问题可以作为预测建模的一个特例获得；参见 Sarrof 等 (2024 (https://arxiv.org/html/2606.17522#bib.bib49)) 第3.2节）。

###### 定义 3.3。给定词汇表 \(\Sigma\) 和语言 \(\mathcal{L} \subseteq \Sigma^*\)，\(\mathcal{L}\) 的**有效前缀**集合，记为 \(\text{Prefix}(\mathcal{L})\)，定义如下：
\[ \text{Prefix}(\mathcal{L}) := \{\underline{w} \in \Sigma^* : \exists \underline{w}' \in \Sigma^*, \; \underline{w} \cdot \underline{w}' \in \mathcal{L}\} \]
对于给定的有效前缀 \(\underline{w} \in \text{Prefix}(\mathcal{L})\)，我们定义 \(S(\underline{w})\) 为 \(\Sigma\) 中所有能够在句子 \(\mathcal{L}\) 中跟随序列 \(\underline{w}\) 的单词的集合，如下：
\[ S(\underline{w}) := \{w \in \Sigma : \underline{w} \cdot w \in \text{Prefix}(\mathcal{L})\} \]
■

###### 定义 3.4 (预测建模)。令 \(\mathcal{L} \subseteq \Sigma^*\) 为一语言，\(f\) 为定义 3.2 中的语言模型。对于 \(\epsilon \geq 0\)，如果对于每个有效前缀 \(\underline{w} \in \mathrm{Prefix}(\mathcal{L})\)，有
\[ \sum_{w \notin S(\underline{w})} \hat{f}(w \mid \underline{w}) \leq \epsilon \]
则称 \(f\) **预测建模** \(\mathcal{L}\) 的误差最多为 \(\epsilon\)。■

### 3.2 上下文无关文法

**表 1：** 一个深度为3的CFG，可用于生成下面两个派生树。

{forest}
{forest}

**图 1：** 两个形状不同的派生树。所有节点的度数为2或3。

上下文无关文法 (CFGs) 是一类基础的形式文法，用于建模自然语言的句法。CFG 由一组有限的产生式规则组成，这些规则描述了如何从指定的起始符号生成语言中的字符串。每条规则指定一个非终结符如何被替换为一串终结符和/或非终结符，从而允许递归和嵌套的派生。与正则文法不同，