💬 NLP

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

本文提供了一项理论分析，证明了深度 Transformer 具有将有限深度上下文无关文法中的抽象语法状态编码进低维、线性可分子空间中的结构能力，从而验证了用于层次化建模的线性表示假设。

原作者： Vinoth Nandakumar, Qiang Qu, Pramod Thebe, Sakshi Khachariya, Tongliang Liu

发布于 2026-06-17

📖 1 分钟阅读☕ 轻松阅读

原作者： Vinoth Nandakumar, Qiang Qu, Pramod Thebe, Sakshi Khachariya, Tongliang Liu

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你正在试图教一个机器人理解人类语言中复杂的嵌套结构。你知道，句子不仅仅是随机的词语字符串；它们就像俄罗斯套娃或家谱一样构建而成，其中小的词组构成短语，短语构成从句，而从句构成句子。

这篇论文提出了一个根本性的问题：深度神经网络（具体来说是现代 AI 背后的“Transformer”）究竟是如何构建这些心理树结构的？

虽然我们知道这些模型在这方面表现出色，但我们此前并不清楚它们在没有被信息淹没的情况下，究竟是如何实现这一点的。这篇论文通过构建一个能够完美理解特定类型语言谜题的“理论机器人”，提供了这一证明。

以下是利用简单类比对他们发现的解析：

1. 问题：“无限”与“有界”

语言在理论上是无限的。你可以不断地在句子中嵌套句子（例如，“那只猫，那只狗，那个男人……”）。然而，人类的大脑是有极限的；我们一次只能在工作记忆中处理有限层级的嵌套。

研究人员决定简化这个问题。他们没有试图模拟无限递归，而是研究了有界深度语法（bounded-depth grammars）。你可以把它想象成一种语言，其中每个句子都保证恰好是 3 或 4 层深，不会更多。这就像建造一座房子并遵循严格的规则：“每座房子必须恰好有 3 层楼。”这使得结构变得可预测且易于数学分析。

2. 解决方案：“分层流水线”

作者构建了一种特定类型的 Transformer 模型来证明它能够解决这些谜题。他们不仅仅是说“它行得通”；他们是分部分地构建了这台机器，以展示其具体运作方式。

他们将 Transformer 的层级比作流水线或施工队：

输入： 想象一堆原始砖块（单词）。
层级： Transformer 有许多堆叠在一起的层。
- 第 1 层观察砖块并将它们粘合在一起，形成小墙壁（简单短语）。
- 第 2 层将这些墙壁粘合在一起，形成房间（从句）。
- 第 3 层将房间组装成一栋完整的房子（句子）。
神奇之处： 论文证明，如果你的语言深度为 $d$ （例如 3 层楼），你只需要一个拥有 $d$ 层的 Transformer 就能完美理解它。模型的深度随语言复杂度的增加呈线性增长。你不需要一个指数级爆炸式的庞大层数；你只需要为每一个层级配备一个对应的层。

3. “注意力”机制：领班的剪贴板

模型如何知道该把哪些砖块粘在一起？论文将“注意力”机制（Transformer 中决定关注什么的机制）描述为拿着剪贴板的领班。

在他们的构建过程中，领班并不会同时观察整个混乱的施工现场。相反，他们有一套特定的、预设的规则：“只看属于这个特定组的砖块。”

他们忽略其他一切。
他们只关注构建上一层级所需的直接邻居。
这被称为稀疏注意力（sparse attention）。这就像一束聚光灯，只照向那些需要向上一层传递砖块的具体工人。

4. “线性表示”的发现

论文中最令人兴奋的观点之一是关于模型在哪里存储这些信息。

AI 领域有一个理论叫做“线性表示假设（Linear Representation Hypothesis）”。它认为复杂的概念（如“这是一个名词短语”）在模型的脑中是以高维空间中简单的直线形式存储的。

作者通过数学手段在他们的构建模型中证明了这一点。他们表明：

模型为每种语法结构都创建了一个特定的“文件夹”或子空间（subspace）。
当模型正在构建一个“名词短语”时，它会在其内部数学逻辑中点亮一条特定的、简单的直线。
当它转向“动词短语”时，它会点亮另一条不同的、截然不同的直线。
这些直线是正交的（orthogonal）（就像坐标系中的 X 轴和 Y 轴），这意味着它们不会重叠或产生混淆。

这解释了为什么“探测（probing）”（一种研究人员通过观察模型来了解其知识的技术）如此有效。模型并没有将语法隐藏在一个混乱、缠绕的结中；它是将信息整齐地归档在简单的、易于阅读的直线中。

5. 为什么这很重要（根据论文所述）

该论文并不声称这能立即治愈疾病或制造自动驾驶汽车。相反，它声称解决了一个理论上的谜团：

它证明了效率： 它表明 Transformer 不需要为了理解复杂语法而变得指数级巨大。它们只需要拥有与语言深度相匹配的深度即可。
它验证了“线性假设”： 它为这些模型能够将复杂规则组织成简单的线性结构提供了严密的数学证明，证实了多年来经验实验所猜测的内容。
它弥合了差距： 它将抽象的“上下文无关语法（Context-Free Grammars）”（传统语言学）与现代的“Transformer 架构”（现代 AI）联系起来，表明它们比我们想象的更加兼容。

总结类比

想象你正在试图教一个机器人折叠一只复杂的折纸鹤。

旧观点： 我们认为机器人需要记住世界上所有可能的折纸鹤形状，这需要一个星系规模的大脑。
这篇论文的观点： 我们证明了，如果你给机器人一份分步骤的说明书（语法），其中折纸鹤具有固定的折叠次数，那么机器人只需要一个步骤数量等于折叠次数的大脑。此外，机器人会将这些步骤组织在整齐、独立的文件夹（线性子空间）中，这样它在进行下一步折叠时就不会感到困惑。

这篇论文的核心观点是：“我们构建了一个理论机器人，证明了深度学习模型天生擅长构建层次化结构，而且它们通过一种令人惊讶的简单、线性方式来组织信息。”

技术摘要：通过有界深度文法分析深层 Transformer 在层次化建模中的表达能力

问题陈述

深度神经网络（尤其是 Transformer）在经验观察中被认为通过形成层次化表示来获得表达能力，从而捕捉跨层的抽象与组合特征。在语言建模中，早期 Transformer 层捕捉局部句法模式，而后期层则编码复杂的子句级依赖关系。尽管这一直觉影响了模型设计，但目前仍缺乏严谨的理论工作来证明 Transformer 如何表征此类层次化结构。

现有的理论分析通常集中在受限设置上，例如 Dyck 语言（平衡括号）或有限状态自动机，这些设置缺乏现实世界文法中复杂的的分支结构。此外，尽管经验研究（如 Allen-Zhu & Li, 2025; Saglam et al., 2025）支持“线性表示假设”——即通过残差流中的线性探针可以恢复抽象的语法状态——但这些工作并未从理论上解释为什么 Transformer 架构具备将这些复杂结构显式编码进低维、线性可分子空间中的结构能力。

本文通过使用有界深度、非递归上下文无关文法 (CFGs) 的形式化视角，来分析深层 Transformer 模型的表达能力。目标是提供一个能够预测性建模此类文法的 Transformer 的显式构造，从而将层次化组合性的机制形式化。

方法论

作者使用具有以下属性的特定类 CFG 来形式化该问题：

固定深度 ( $d$ )： 每个推导树的高度恰好为 $d$ 。
非递归性： 这些文法生成有限语言，避免了无限制的嵌套。
统一性： 给定非终结符的产生式规则具有相同的长度。
有界参数： 分析考虑了最大规则数 ( $M$ )、最大分支因子 ( $B$ ) 以及有效推导树形状的数量 ( $c = |C(G)|$ )。

作者构造了一个带有位置注意力机制的仅解码器 Transformer 来建模这些文法。该构造依赖于三个核心组件：

稀疏注意力头： 模型利用了一种简化的相对位置注意力机制，其中注意力权重仅取决于标记（token）的位置，而非内容。这允许实现“硬”注意力，根据其在推导树中的位置来选择特定标记。
层次化处理： Transformer 的深度随文法深度 ( $d$ ) 线性增长。每个 Transformer 块对应于语法层次结构中的一个层级，从叶节点（终结符）向上处理至根节点（起始符号）。
前馈记忆： 位置前馈网络 (FFNs) 被构造为离散查找表。利用关于神经网络记忆容量的研究结果 (Zhang et al., 2017)，这些层将聚合的局部句法上下文映射到父非终结符符号。

该构造实现了类似于 CKY 解析器的自底向上动态规划算法，其中：

注意力头聚合子节点的局部句法上下文，以识别语法成分的边界。
FFNs 将生成的父非终结符符号编码进残差流，并通过残差连接保留较低层级的状态。
最终层利用堆叠的前馈网络，基于累积的层次化状态计算有效的下一个词预测。

核心贡献

显式 Transformer 构造： 本文提供了一个构造性证明，证明深度为 $d$ 的 Transformer 可以预测性地建模深度为 $d$ 的统一、非递归 CFG。
可扩展性界限： 作者推导了所需的模型规模界限：
- 深度： 随文法深度 ( $d$ ) 线性增长。
- 神经元数量： 随推导树形状的数量 ( $c$ ) 线性缩放，并随产生式规则数量 ( $M$ ) 平方缩放。
- 隐藏维度： 随 $c \cdot d$ 缩放。
对线性表示的理论支持： 该构造证明了该架构具备将抽象语法状态编码进残差流中低维、线性可分子空间中的结构能力。具体而言，对于给定的推导树形状，解析计算发生在不同的子空间中，使得非终结符可以通过简单的仿射变换被隔离出来。
与前人工作的区别： 不同于以往随最大句子长度（在文法深度下可能呈指数级增长）缩放的界限，本构造随文法深度本身缩放。这突显了层次化建模相对于扁平表示（如 n-gram 或有限状态自动机，后者对于深层 CFG 需要指数级的状态空间）的效率。

结果

主要理论结果（定理 4.1）确立了对于任何 $\epsilon > 0$ ，存在一个 Transformer 语言模型 $f_T$ 能够预测性地建模语言 $L(G)$ 且误差不超过 $\epsilon$ 。该模型由 $d$ 个 Transformer 块和随后的 $5d + 7$ 个前馈层组成。

效率： 所需层数与文法深度呈线性关系，相比于层数随句子长度缩放的构造，这是一个显著的改进。
稀疏性： 构造利用了一个稀疏电路，其中每个输入序列由每个块中的单个注意力头进行处理，这与深度学习中稀疏计算子图的经验发现相一致。
线性可分性： 证明表明，给定深度的非终结符符号被映射到对应残差流的一个子空间向量中，支持了线性表示假设。然而，作者指出其构造使用了严格的正交基（离散指示神经元），而现实中的模型可能通过稠密叠加（superposition）来实现这一点。

意义与局限性

意义：
本文提供了深层 Transformer 可以显式表示层次化语法结构的严谨存在性证明。它弥合了线性表示的经验观察与理论架构能力之间的鸿沟。通过形式化 Transformer 如何实现自底向上的动态规划，这项工作为“为什么更深的架构能有效捕捉复杂语言结构”提供了理论基础，使其免于处理扁平模型时相关的“维度诅咒”。

局限性：

简化框架： 分析仅限于有界深度的非递归 CFG。它并未直接处理递归文法或无限语言，尽管该框架被视为分析层次化组合性的抽象。
正交 vs. 叠加： 理论构造依赖于一个每个语法状态都有专用神经元的正交基空间。这简化了证明，但并未考虑到在现实模型中观察到的“叠加”现象，即特征被压缩进稠密向量中。理解标准训练动力学如何产生此类压缩表示仍是一个开放性问题。
向真实语料库的可扩展性： 界限取决于 $c$ （树形状的数量），而 $c$ 可能很大。虽然该框架形式化了核心机制，但作者承认它尚未能为像 Penn Treebank 这样复杂的真实语料库提供紧致界限。

总之，这项工作通过形式语言理论为理解 Transformer 模型内部运作奠定了基础，表明 Transformer 的深度自然地镜像了其所建模的语法层次结构的深度。