通过机制可解释性发现Dyck路径上的Zeta映射算法

# 通过机制可解释性发现 Dyck 路径上的 Zeta 映射算法  
来源：https://arxiv.org/html/2605.30482  

###### 摘要  

机器学习在数学发现中的应用日益广泛，但在数学领域，期望的输出往往不是预测本身，而是一个可以被独立验证的显式构造。我们通过 Dyck 路径上的 zeta 映射（q,t-卡塔兰数组合学中的经典双射）来研究这一场景。我们训练了一个刻意小型化的单层单头编码器-解码器 Transformer 来学习该映射，并利用机制可解释性工具（包括解码器交叉注意力分析、线性探针和因果干预）分析其学得的计算过程。分析揭示了一种基于层级（level）的机制：编码器表示使路径层级的线性可访问，而解码器则以结构化方式选择和遍历输入位置。将这些信号转化为组合学描述，便得到了 Dyck 路径的“脚手架映射”（scaffolding map），一种显式的以峰为中心的遍历算法。我们证明该算法与 zeta 映射一致（除标签中的反转约定外）。这为 AI 辅助数学发现提供了一个可控的实例，其中机制可解释性将模型行为转化为精确、可人工验证的组合算法。  

**AI for mathematics, human-AI collaboration, AI-assisted discovery, combinatorics, Dyck paths, zeta map, transformers, mechanistic interpretability**  

## 1 引言  

机器学习越来越多地应用于数学研究（Gukov et al., 2021 (https://arxiv.org/html/2605.30482#bib.bib13); Charton et al., 2024 (https://arxiv.org/html/2605.30482#bib.bib8); Novikov et al., 2025 (https://arxiv.org/html/2605.30482#bib.bib20)），但许多成功的应用仍将模型主要视为高精度预测器或生成模型。对于数学发现而言，仅靠预测通常是不够的：期望的输出往往是数学家可以验证的猜想、构造或显式算法。本文在具体的组合学背景下（Dyck 路径上的 zeta 映射）研究这种人机协作流程。我们训练 Transformer 模型（Vaswani et al., 2017 (https://arxiv.org/html/2605.30482#bib.bib25)）学习一个已知的数学双射，利用机制可解释性工具解释一个刻意小型化 Transformer 学到的机制，并从中提取出一个新的显式算法。  

zeta 映射是 q,t-卡塔兰数理论中的一个核心组合对象，因为它给出了 q,t-卡塔兰数公式中出现的标准 Dyck 路径统计量之间对称性的双射解释。具体来说，它将 (dinv, area) 描述转化为 (area, bounce) 描述，连接了两种不同的定义（Haglund, 2003 (https://arxiv.org/html/2605.30482#bib.bib14); Haiman, 2000 (https://arxiv.org/html/2605.30482#bib.bib15)）。由于 zeta 映射已有多种算法描述（Andrews et al., 2002 (https://arxiv.org/html/2605.30482#bib.bib2); Haglund, 2003 (https://arxiv.org/html/2605.30482#bib.bib14)），它为 AI 辅助数学发现提供了一个理想的测试案例：数据完全可生成，正确性可在中等规模下穷举检验，期望输出是离散组合过程而非数值近似。  

我们首先展示了 Transformer 能够在多种实验设置下学习 zeta 映射。然后我们将架构精简为单层单头编码器-解码器 Transformer，使学到的解具有足够结构以进行机制分析。分析揭示的核心量是输入 Dyck 路径的层级序列：交叉注意力表明解码器根据层级选择位置，因果消融显示解码过程中许多向上步的位置并非必需，线性探针表明层级信息可从编码器表示中恢复。这些观察促使我们提出了“脚手架映射”，一种以峰为中心的 Dyck 路径遍历算法。与该映射的经典面积序列描述不同，该过程直接按层级和局部遍历组织。据我们所知，这是第一个利用训练后神经序列模型的机制解释来提取已知组合映射的新显式双射描述的实例。  

本文的更广泛目标是将 zeta 映射作为 AI 在组合学研究中的试验场，即展示从训练模型中提取组合双射和算法的能力。虽然不同数学 AI 应用的具体细节可能有所差异，但本文阐述的概念在组合学研究中具有广泛适用性。模型提供重复出现的结构信号；人类研究者将这些信号解释为组合操作；额外的干预检验该解释是否具有因果相关性；最终得到的过程成为一个数学对象，可独立于神经网络进行陈述和证明。  

## 2 相关工作  

#### AI 辅助发现。  
AI 方法作为数学发现的搜索工具已展现出越来越大的潜力。强化学习方法已被用于寻找极值组合学、图论和纽结理论中的显式例子和反例（Wagner, 2021 (https://arxiv.org/html/2605.30482#bib.bib26); Gukov et al., 2021 (https://arxiv.org/html/2605.30482#bib.bib13)）。最近的工作进一步研究了强化学习智能体如何在具有稀疏高奖励实例的困难数学搜索空间中导航（Butbaia et al., 2026 (https://arxiv.org/html/2605.30482#bib.bib7); Fagan et al., 2026 (https://arxiv.org/html/2605.30482#bib.bib11)）。互补的生成模型引导搜索和基于 LLM 的编码智能体也被用于发现极值数学结构和改进算法（Charton et al., 2024 (https://arxiv.org/html/2605.30482#bib.bib8); Bérczi et al., 2026 (https://arxiv.org/html/2605.30482#bib.bib5); Novikov et al., 2025 (https://arxiv.org/html/2605.30482#bib.bib20)）。我们的工作侧重点不同：我们不使用 AI 来搜索例子，而是使用机制可解释性从训练好的模型中提取显式组合算法。  

#### 机制可解释性。  
机制可解释性旨在逆向工程训练后神经网络实现的算法。数学背景下的相关先例包括对训练在模算术和群操作上的小型 Transformer 的分析（Nanda et al., 2023 (https://arxiv.org/html/2605.30482#bib.bib19); Chughtai et al., 2023 (https://arxiv.org/html/2605.30482#bib.bib9); Zhong et al., 2023 (https://arxiv.org/html/2605.30482#bib.bib30)）以及算术和枚举几何任务（Babei et al., 2025 (https://arxiv.org/html/2605.30482#bib.bib4); Hashemi et al., 2025 (https://arxiv.org/html/2605.30482#bib.bib16)）。最近还有自动发现方面的努力，如自动电路发现（Conmy et al., 2023 (https://arxiv.org/html/2605.30482#bib.bib10)）、自动神经元或特征解释（Bills et al., 2023 (https://arxiv.org/html/2605.30482#bib.bib6); Shaham et al., 2024 (https://arxiv.org/html/2605.30482#bib.bib22)）以及激活到语言解码方法（Pan et al., 2026 (https://arxiv.org/html/2605.30482#bib.bib21); Karvonen et al., 2026 (https://arxiv.org/html/2605.30482#bib.bib18)）。  

## 3 数学背景  

### 3.1 Dyck 路径与 q,t-卡塔兰统计量  

Dyck 路径是组合学中的基本对象。一个半长度为 \(n\) 的 *Dyck 单词* 是一个长度为 \(2n\) 的二进制单词 \(w = (w_i)_{i=1}^{2n}\)，包含恰好 \(n\) 个 1，并且每个初始段中 1 的数量不少于 0 的数量。记 \(\mathrm{Dyck}(n)\) 为所有此类单词的集合，其中 \(|\mathrm{Dyck}(n)|\) 是著名的第 \(n\) 个 Catalan 数。等价地，将 1 解释为北步步，0 解释为东步步，则一个 *Dyck 路径* 是从 \((0,0)\) 到 \((n,n)\) 且始终保持在对角线 \(y=x\) 上方（含）的格路，示例如图 1 (https://arxiv.org/html/2605.30482#S3.F1)。  

参见图注  
图 1：一个半长度为 5 的 Dyck 路径示例。  

q,t-卡塔兰数细化了卡塔兰数，并涉及 \(\mathrm{area}\)、\(\mathrm{bounce}\) 和 \(\mathrm{dinv}\) 这三个统计量的 Dyck 路径展开：  

\[
C_n(q,t) = \sum_{w \in \mathrm{Dyck}(n)} q^{\mathrm{area}(w)} t^{\mathrm{bounce}(w)} = \sum_{w \in \mathrm{Dyck}(n)} q^{\mathrm{dinv}(w)} t^{\mathrm{area}(w)}. \tag{1}
\]

这些公式分别由 (Haglund, 2003 (https://arxiv.org/html/2605.30482#bib.bib14); Haiman, 2000 (https://arxiv.org/html/2605.30482#bib.bib15)) 独立发现。这里 \(\mathrm{area}(w)\) 统计路径与对角线之间的单元格数，\(\mathrm{bounce}(w)\) 通过 Haglund 的 bounce 路径计算，\(\mathrm{dinv}(w)\) 统计 w 的面积序列中的某种对角线逆序数。这两种定义等价性促使寻找交换这些统计量的双射。Haglund 的 zeta 映射 (Haglund, 2003 (https://arxiv.org/html/2605.30482#bib.bib14)) 是一个双射 \(\zeta\)，满足：  

\[
(\mathrm{dinv}(w), \mathrm{area}(w)) = (\mathrm{area}(\zeta(w)), \mathrm{bounce}(\zeta(w))).
\]

尽管 zeta 映射是唯一的，但它有几种组合解释，包括基于面积序列的描述 (Andrews et al., 2002 (https://arxiv.org/html/2605.30482#bib.bib2); Haglund, 2003 (https://arxiv.org/html/2605.30482#bib.bib14)) 以及描绘其逆的 sweep 映射 (Armstrong et al., 2015 (https://arxiv.org/html/2605.30482#bib.bib3); Thomas & Williams, 2018 (https://arxiv.org/html/2605.30482#bib.bib24))。我们的目标并非取代这些解释。相反，我们研究训练在该映射上的模型是否能揭示另一种算法组织方式。关于 q,t-卡塔兰数和 zeta 映射的更多背景见附录 A (https://arxiv.org/html/2605.30482#A1)。  

对于一个 Dyck 单词 \(w = (w_i)_{i=1}^{2n}\)，我们如下定义其层级序列：\(\ell_0 = 0\)，且  

\[
\ell_i = 
\begin{cases}
\ell_{i-1} + 1, & \text{if } w_i = 1, \\
\ell_{i-1} - 1, & \text{if } w_i = 0.
\end{cases}
\]

层级随后成为我们可解释性分析所识别的一个核心隐式组合量。  

## 4 实验设置  

#### 实验。  
对于固定半长度 \(n\)，我们构建了一个有监督数据集，包含 Dyck 单词及其像。具体来说，对于每个输入 Dyck 单词 \(w\)，目标序列是由 SageMath (The Sage Developers, 2026 (https://arxiv.org/html/2605.30482#bib.bib23)) 的 `area_dinv_to_bounce_area_map()` 函数产生的像。在该函数使用的标签约定下（附录 D (https://arxiv.org/html/2605.30482#A4) 进一步讨论），目标与 \(\mathrm{rev} \circ \zeta(w)\) 一致，其中 \(\mathrm{rev}\) 表示将 Dyck 单词反向阅读并交换 0 和 1。  

使用嵌入维度为 256、4 层编码器和 4 层解码器（每层 8 个注意力头）的固定架构，模型在学习 zeta 映射时达到了 >99% 的准确率，即对于半长度 \(n = 11, 12, 13, 14, 15, 16\) 的数据集，预测 Dyck 路径在 zeta 映射下的像，数据集大小分别为 58,786、208,012、742,900、2,674,440、9,694,845 和 35,357,670，对应卡塔兰数 \(C_n\)。随后我们改变架构和超参数，探索了一个选择性子集：  

- 编码器-only、解码器-only 和编码器-解码器架构；  
- Transformer 层数从 1 到 4；  
- 注意力头数从 1 到 8，模型在几乎所有设置下都获得了近乎完美的准确率。  

#### 压缩。  
然后我们训练了一个最小模型，嵌入维度 128，一层编码器、一层解码器、一个注意力头。该模型有 339,716 个参数，并在多次重复运行中达到了完美或近乎完美的准确率。该模型在 \(n = 13\) 数据集上训练，我们称之为 *Minimal Dyck Transformer*，是下面可解释性分析的重点。我们在附录 B (https://arxiv.org/html/2605.30482#A2) 中包含了 *Minimal Dyck Transformer* 的架构细节。  

## 5 解释 Minimal Dyck Transformer  

### 5.1 交叉注意力模式  

虽然多种机制检查揭示了有用结构（见附录 C (https://arxiv.org/html/2605.30482#A3)），但最有信息量的内部信号是解码器交叉注意力。我们在每个生成步骤动态跟踪哪些输入位置获得最大的解码器交叉注意力权重。图 2 (https://arxiv.org/html/2605.30482#S5.F2) 显示了一个示例。在生成过程中，解码器反复关注一个小而结构化的输入位置子集。在各示例中，我们观察到三种重复出现的模式。  

参见图注  
图 2：Minimal Dyck Transformer 的代表性解码器交叉注意力矩阵。重复出现的稀疏模式表明生成过程由基于层级的选择组织，而非无结构的查找表。  

#### 最高层级选择。  
在输出早期步骤中，最显著地出现在解码器生成输出 Dyck 单词第一步的注意力可视化中，解码器将注意力放在那些层级在相关位置中最大的输入位置上。图 3(a) (https://arxiv.org/html/2605.30482#S5.F3.sf1) 和 3(b) (https://arxiv.org/html/2605.30482#S5.F3.sf2) 显示了示例。这表明层级信息已被编码器计算，并被解码器用作选择标准。  

参见图注  
(a)  
参见图注  
(b)  
参见图注  
(c)  
图 3：解码器交叉注意力及其因果作用的示例。左：输入、目标和模型生成的 Dyck 路径，被关注的输入位置用黄色高亮。中：生成左侧第一步输出时使用的稀疏交叉注意力。右：因果消融结果，在消融对输入北步步的所有交叉注意力后，准确率下降可忽略不计，通过比较生成的输出路径与正确目标路径直到第 k 步来测量。  

#### 系统性地避开许多向上步。  
\(w_i = 1\) 的位置在整个解码过程中未收到任何交叉注意力，因此解码器无法直接从向上步“读出”层级和方向信息：忽略 \(w_i = 1\) 阻止了模型直接访问向上步的层级和方向。解码器比较此类位置信息的一种方式是编码器已将之聚合并存储在了 \(w_i = 0\) 位置的隐藏状态中。然而，我们在 5.2 节 (https://arxiv.org/html/2605.30482#S5.SS2) 中表明情况并非如此。相反，解码器似乎严重依赖于选中的位置，并通过结构化遍历重建其余位置。  

#### 三角序列移动。  
随着解码进行，许多示例显示出图 2 (https://arxiv.org/html/2605.30482#S5.F2) 所示的三角形注意力模式。该模式表明