离散对数时钟：Transformer如何学习模乘

# 1 引言 来源：https://arxiv.org/html/2606.17399 marginparsep 已被修改。topmargin 已被修改。marginparpush 已被修改。页面布局违反了 ICML 样式。请勿更改页面布局，或包含 geometry、savetrees 或 fullpage 等会为您更改布局的宏包。我们无法可靠地撤销对样式的任意更改。请移除违规的宏包或布局更改命令，然后重试。  
**离散对数时钟：变压器如何学习模乘法**  
Huu Danh Nguyen\(^1\)††footnotetext:1斯坦福大学。通讯作者：Huu Danh Nguyen <[email protected]>。  
第43届国际机器学习大会机制可解释性研讨会，韩国首尔，2026年。版权所有 2026 作者。  

###### 摘要  
当小型变压器领悟模乘法时，先前的工作报告称学习到的嵌入具有“密集”的傅里叶频谱，需要所有频率。这与模加法形成对比，后者仅需一组稀疏的关键频率就足够了。我们证明这种密度是在错误的基础上分析的人为产物。乘法的自然傅里叶变换不是标准的加法 DFT，而是*乘法特征变换*，它将乘法群 \((\mathbb{Z}/p\mathbb{Z})^\*\) 上的函数分解为其不可约表示。将此变换应用于训练在 \(a \cdot b \bmod 113\) 上已领悟的变压器，我们发现嵌入频谱变得高度稀疏（基尼系数 0.58 vs. 加法基下的 0.07），仅有 4 个关键频率携带显著能量。此外，96.9% 的 MLP 神经元干净地调谐到单个乘法频率，并且神经元激活热力图在按离散对数重排序后显示出二维周期性结构。这些结果表明变压器将乘法简化为离散对数空间中的加法，实现了类似于 Nanda 等人用于加法的“时钟”算法的“离散对数时钟”算法。该方法具有普遍性：将分析基础与任务的代数结构相匹配，可以揭示标准工具视为噪声的可解释结构。  

领悟（Grokking）——神经网络在记忆训练数据后突然泛化的现象——已成为机制可解释性的关键测试平台（Power 等人，2022 (https://arxiv.org/html/2606.17399#bib.bib1)）。对于模加法 \(a+b \bmod p\)，内部算法已被完全逆向工程：模型学习一个稀疏的傅里叶表示，并应用三角恒等式在圆上组合旋转（Nanda 等人，2023 (https://arxiv.org/html/2606.17399#bib.bib2)；Zhong 等人，2023 (https://arxiv.org/html/2606.17399#bib.bib3)）。对于模乘法 \(a \cdot b \bmod p\)，模型也能成功领悟，但其内部算法一直未能得到很好的刻画。Doshi 等人（2024 (https://arxiv.org/html/2606.17399#bib.bib4)）推导了解析的 MLP 解，需要密集的傅里叶分量（所有频率），而 Furuta 等人（2024 (https://arxiv.org/html/2606.17399#bib.bib5)）通过实验证实，领悟后的变压器在所有频率上使用余弦偏置分量。这些发现表明乘法使用了一种与加法根本不同、可解释性较差的算法。  
**我们的贡献。** 我们证明这一结论为时过早。“密集频谱”是使用*加法*傅里叶变换（这是加法的自然基础，而非乘法的自然基础）进行分析的人为产物。正确的分析工具是*乘法特征变换*，即乘法群 \((\mathbb{Z}/p\mathbb{Z})^\*\) 上的傅里叶变换。在此基下，嵌入变得稀疏，神经元按频率清晰聚类，算法是可解释的：它通过离散对数将乘法简化为加法。  
**任务表述。** 我们模型的输入是一对整数 \((a,b) \in \{1,\ldots,112\}^2\)。我们训练一个 1 层变压器，输出预测乘积 \(c = a \cdot b \bmod 113\)。模型在训练期间观察到所有输入对的 30%，并且必须泛化到剩余的 70%。  

## 2 相关工作  
**模加法的机制可解释性。** Nanda 等人（2023 (https://arxiv.org/html/2606.17399#bib.bib2)）完全逆向工程了变压器在模加法上学到的算法，展示了模型使用离散傅里叶变换和三角恒等式来组合旋转。Zhong 等人（2023 (https://arxiv.org/html/2606.17399#bib.bib3)）将其命名为“时钟”算法，并发现了另一种“披萨”算法，证明了同一任务存在多种算法解。这些工作建立了我们扩展到乘法的方法论。  
**模乘法的先前工作。** Doshi 等人（2024 (https://arxiv.org/html/2606.17399#bib.bib4)）推导了解析闭式 MLP 权重用于模乘法，并发现解中包含离散对数 \(\log_g(i)\) 在权重结构中。然而，他们使用了二次激活函数，并未将其与训练好的 ReLU 变压器中的经验傅里叶图景联系起来。Furuta 等人（2024 (https://arxiv.org/html/2606.17399#bib.bib5)）在模多项式（包括乘法）上训练变压器，并报告学习到的频谱使用“所有频率”，没有清晰的稀疏结构，这与加法形成对比。我们的工作解决了这一差异：密度是基的人为产物，而非算法差异。  
**群论框架。** Chughtai 等人（2023 (https://arxiv.org/html/2606.17399#bib.bib6)）表明，在群运算上训练的网络学习了相关群的不可约表示。Stander 等人（2024 (https://arxiv.org/html/2606.17399#bib.bib8)）逆向工程了置换群乘法（S5, S6）上的网络，发现了基于陪集的电路。McCracken 等人（2025 (https://arxiv.org/html/2606.17399#bib.bib7)）将所有已知加法算法统一在“近似 CRT”框架下。这些工作研究的是与我们不同的群（非阿贝尔置换群、加法循环群）；我们的贡献是专门将乘法特征基应用于训练好的变压器中的 \((\mathbb{Z}/p\mathbb{Z})^\*\)。  

## 3 方法  
### 3.1 任务与架构  
我们在 \(a \cdot b \bmod 113\)（对于所有 \(a,b \in \{1,\ldots,112\}\)，排除零，因为它不在乘法群内）上训练一个 1 层解码器仅变压器。架构遵循 Nanda 等人（2023 (https://arxiv.org/html/2606.17399#bib.bib2)）：\(d_{\text{model}} = 128\)，4 个注意力头（\(d_{\text{head}} = 32\)），MLP 隐藏维度 512，ReLU 激活，无 LayerNorm。输入格式是 token 序列 \([a, b, =]\)；模型的预测从位置 2（“=”处）的输出 logits 读取。  
**超参数。** 我们使用 30% 的训练数据（12,544 对中的 3,763 对），AdamW 学习率 \(10^{-3}\)，权重衰减 1.0，训练 40,000 个 epoch，使用全批梯度下降。这些超参数完全遵循 Nanda 等人（2023 (https://arxiv.org/html/2606.17399#bib.bib2)）以确保可比性；唯一的变化是任务（乘法 vs. 加法）。  
**训练动态。** 模型在大约 epoch 500 时记忆训练集（训练损失 \(\to 0\)，测试损失仍然高）。在 epoch 9,000 到 14,000 之间，测试损失突然降至接近零：模型领悟了，实现了近乎完美的泛化（图 1 (https://arxiv.org/html/2606.17399#S3.F1)）。这种延迟的泛化是领悟的特征：模型首先过拟合，然后在权重衰减的压力下发现泛化算法。  

引用图注  
图 1：\(a \cdot b \bmod 113\) 的训练曲线。模型快速记忆（训练损失在 epoch 500 时下降），然后在领悟期间突然泛化（epoch 9K–14K）。权重衰减驱动了从记忆到结构化算法的转变。  

### 3.2 乘法群与离散对数  
由于 113 是素数，非零整数 \(\{1,\ldots,112\}\) 在模 113 乘法下构成循环群。一个*本原根*是一个生成元：一个元素 \(g\) 使得 \(\{g^0, g^1, \ldots, g^{111}\} \bmod 113\) 穷尽所有 112 个元素。对于 \(p=113\)，我们使用 \(g=3\)。*离散对数* \(\log_g : \{1,\ldots,112\} \to \{0,\ldots,111\}\) 为每个元素分配其指数：\(3^\alpha \equiv a \pmod{113}\) 意味着 \(\log_3(a) = \alpha\)。我们将两个输入分别记为 \(\alpha = \log_g(a)\) 和 \(\beta = \log_g(b)\)。这是一个精确的双射（112 个元素的排列），并定义了一个群同构：  
\[
\log_g: (\mathbb{Z}/p\mathbb{Z})^\* \xrightarrow{\;\cong\;} \mathbb{Z}/(p-1)\mathbb{Z}
\quad (1)
\]
在此映射下，乘法变为加法：  
\[
a \cdot b \equiv 3^{(\alpha+\beta) \bmod 112} \pmod{113}
\quad (2)
\]
在重新标记的坐标中，乘法表*就是*模 112 的加法表。  

### 3.3 两个傅里叶基  
*加法*傅里叶基由 \(\sin(2\pi k a / q)\) 和 \(\cos(2\pi k a / q)\) 组成，其中 \(k=1,\ldots,q/2\)，\(q=112\)。这是标准的 DFT，对于在整数标签 \(a\) 上周期性的函数是自然的。*乘法特征*基使用 \(\sin(2\pi k \log_g(a) / q)\) 和 \(\cos(2\pi k \log_g(a) / q)\)。操作上：按离散对数映射对嵌入行进行重排序，然后取标准 DFT。这是群 \((\mathbb{Z}/p\mathbb{Z})^\*\) 上的傅里叶变换，将函数分解为乘法特征。动机直接：由于乘法在重标记后变为加法（式 (2)），一个学习了群结构的模型应该具有在重标记坐标中周期性的嵌入，正如加法模型具有在原始坐标中周期性的嵌入一样。  

### 3.4 分析方法  
我们将以下流程应用于训练好的模型：  
**步骤 1: 嵌入频谱。** 提取训练好的嵌入矩阵 \(W_E \in \mathbb{R}^{112 \times 128}\)。投影到两个基上，并计算每个频率 \(k\) 的组合频率范数 \(\|f_k\| = \sqrt{\|s_k\|^2 + \|c_k\|^2}\)，其中 \(s_k\) 和 \(c_k\) 是正弦和余弦投影（每个都是一个 128 维向量）。  
**步骤 2: 稀疏性度量。** 我们使用基尼系数衡量集中度：  
\[
G = \frac{\sum_{i=1}^n (2i - n - 1) |x_i|}{n \sum_{i=1}^n |x_i|}
\quad (3)
\]
其中 \(x_1 \leq \ldots \leq x_n\) 是排序后的频率范数。\(G=0\) 表示均匀（密集），\(G=1\) 表示最大稀疏。关键频率被检测为那些超过中位数范数 \(5\times\) 的。  
**步骤 3: 神经元频率分配。** 对于 512 个 MLP 神经元中的每一个，计算所有输入对上的 2D 激活模式 \(h_n(a,b)\)（重塑为一个 \(112 \times 112\) 的网格）。在每个基中取 2D DFT，并测量任何单一频率的最大能量分数。具有 \(>85\%\) 能量在一个频率上的神经元被分类为“单频率调谐”。  
**步骤 4: SVD 分析。** 对 \(W_E\) 进行 SVD，并按离散对数对主成分进行重排序。对数顺序中的正弦结构确认嵌入编码了乘法特征。  

## 4 实验与结果  
### 4.1 基比较  
图 2 (https://arxiv.org/html/2606.17399#S4.F2) 显示了两个基中的嵌入频谱。在加法基中，能量均匀分布（基尼系数 = 0.071）。在乘法基中，能量集中在频率 \(\{2,8,47,56\}\) 的 4 个峰值处（基尼系数 = 0.579，提高了 8.1 倍）。表 1 (https://arxiv.org/html/2606.17399#S4.T1) 总结了所有度量。  

引用图注  
图 2：嵌入傅里叶频谱。左：加法基显示平坦、密集的频谱。右：乘法基揭示 4 个稀疏峰值。y 轴比例相同。先前工作报告的“密度”是基的人为产物。  

表 1：比较两个基的稀疏性度量。  

### 4.2 神经元层面确认  
在乘法基中，512 个神经元中有 496 个（96.9%）其傅里叶能量的 \(>85\%\) 位于单一频率（图 3 (https://arxiv.org/html/2606.17399#S4.F3)）。在加法基中，没有神经元超过这一阈值。当神经元激活热力图按离散对数重排序后，出现了清晰的对角条纹模式（图 4 (https://arxiv.org/html/2606.17399#S4.F4)）。这些条纹表明该神经元计算了 \(\alpha + \beta\) 的周期函数，这是三角恒等式 \(\cos(k(\alpha + \beta))\) 在对数空间中运行的标志：与 Nanda 等人为加法发现的机制相同，但应用于离散对数变换之后。  

引用图注  
图 3：每个神经元的排序最大频率分数。橙色：乘法基（96.9% 高于 85% 阈值）。蓝色：加法基（0% 高于阈值）。  

引用图注  
图 4：整数顺序（左）与离散对数顺序（右）的神经元热力图。在对数顺序中，出现对角条纹，表明在 \(\log_g(a) + \log_g(b)\) 上的周期性。  

### 4.3 对数顺序的 SVD  
我们对 \(W_E\) 进行 SVD，并按离散对数对主成分进行重排序。在整数顺序中，所有分量看起来有噪声。在对数顺序中，几个分量显示出正弦结构（图 5 (https://arxiv.org/html/2606.17399#S4.F5)），与嵌入编码乘法特征一致。有效秩为 10.3（共 112），确认嵌入位于低维子空间中。  

引用图注  
图 5：按离散对数重排序的 \(W_E\) 主成分显示出正弦结构，确认嵌入编码了乘法特征。  

### 4.4 讨论  
**离散对数时钟算法。** 我们的结果表明变压器通过以下方式解决模乘法：(1) 将每个整数 \(a\) 嵌入为 \(\log_g(a)\) 的正弦函数；(2) 通过注意力将嵌入路由到输出位置；(3) 在 MLP 中应用三角恒等式计算 \(\cos(k(\alpha + \beta)/q)\)；(4) 通过每个候选答案 \(c\) 与 \(\cos(k \log_g(c)/q)\) 的对齐程度进行评分，其中只有正确答案 \(c = ab \bmod p\) 在所有频率上实现相长干涉。  
**先前工作为何错过这一点。** Furuta 等人（2024 (https://arxiv.org/html/2606.17399#bib.bib5)）和 Doshi 等人（2024 (https://arxiv.org/html/2606.17399#bib.bib4)）使用加法 DFT 进行分析。一个在 \(\log_g(a)\) 上周期性的函数在 \(a\) 上看起来是非周期性的，因为离散对数是整数的一个非线性排列。“全频率”发现在加法基中是正确的，但具有误导性，因为它混淆了基不匹配与算法复杂性。  
**过拟合与泛化。** 领悟本身是一种过拟合现象：模型在 epoch 500 时达到零训练损失（记忆），然后继续训练数千个 epoch 后才发现泛化算法。权重衰减惩罚记忆所需的大规模、非结构化权重，逐渐倾向于泛化能力强的紧凑傅里叶表示。我们未使用交叉验证，因为任务是确定性的（无标签噪声）；70% 的保留集用于测试。