🤖 machine learning

The Discrete-Log Clock: How a Transformer Learns Modular Multiplication

本文表明，Transformer 在学习模乘法时表现出的表观复杂性是使用错误分析基底所导致的产物，揭示了它们实际上通过在乘法特征空间内将乘法归约为加法，实现了一种稀疏且可解释的“离散对数时钟”算法。

原作者： Huu Danh Nguyen (Stanford University)

发布于 2026-06-17

📖 1 分钟阅读☕ 轻松阅读

原作者： Huu Danh Nguyen (Stanford University)

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

巨大的谜团：为什么 AI 会“困惑”？

想象一下，你正在试图教一个机器人做数学题。具体来说，你想让它学习模乘法（即两个数相乘，并只保留除以一个特定数字——比如 113——之后的余数）。

长期以来，科学家们注意到了一些奇怪的现象。当机器人终于“掌握了窍门”（这种现象被称为**“顿悟”/grokking**，即它突然从死记硬背答案转变为理解规则）时，它的内部数学逻辑看起来非常混乱。

旧观点： 当科学家使用标准工具观察机器人的大脑时，他们看到的是一片“稠密”的混乱。看起来机器人似乎在使用每一种可能的频率来解决问题。这显得既混乱又难以理解，不像它解决简单的加法那样整洁有序。
问题所在： 科学家们是用错误的眼镜在观察机器人的大脑。他们使用的是为加法设计的“标准尺子”，但机器人实际上在做的是乘法。

解决方案：更换镜头

本文的作者意识到，要理解乘法，你不能再把数字看作它们原本的样子（1, 2, 3...），而必须开始将它们视为生成元的幂次。

可以这样理解：

标准视角（加法）： 想象一个从 1 到 12 的时钟盘面。如果你加 1，你就移动一步。这很容易观察。
隐藏视角（乘法）： 现在，想象时钟上的数字被打乱了。数字“1”实际上是“3”，数字“2”实际上是“9”，以此类推。在这个被打乱的世界里，乘法实际上运作得和加法完全一样。

论文将此称为**“离散对数时钟”（Discrete-Log Clock）**。这是一个秘密代码，通过它，混乱的乘法问题可以转化为一个简单的加法问题。

他们的发现（“顿悟”时刻）

当研究人员使用这种新的“打乱”后的透镜（他们称之为乘法特征变换）重新检查机器人的大脑时，混乱消失了。

噪声变成了信号： 他们看到的不再是混乱的“稠密”频谱，而是一个非常清晰、稀疏的模式。机器人并没有使用所有的频率；它只使用了 4 个特定的频率来进行数学运算。这就像是在充满静电噪音的房间里找到了一个清晰的旋律。
神经元变得有序了： 机器人拥有数千个微小的处理单元（神经元）。在旧的视角下，它们看起来是随机的。但在新的视角下，97% 的神经元都完美地调谐到了这 4 个频率中的某一个。它们就像一个合唱团，每个歌手都知道该唱哪一个音符。
模式显现了： 当他们根据这个秘密代码重新排列数据时，机器人的内部活动形成了完美的对角线条纹。这证明了机器人学会了一个特定的技巧：
- 第一步： 将数字转换为它们的“秘密代码”（离散对数）。
- 第二步： 将这些代码相加（就像普通的加法一样）。
- 第三步： 将结果转换回正常的数字。

“时钟”类比

论文将此与用于加法的著名“时钟算法”进行了对比。

对于加法： 机器人学习旋转一个时钟的指针。
对于乘法： 机器人学习旋转一个不同种类的时钟（即离散对数时钟）。一旦它在这个特殊的时钟上旋转指针，答案就跃然纸上。

为什么之前的科学家会错过这一点？

想象一下，你正试图听一首歌，但你戴着一副只能听到低音的降噪耳机。你听到了一种沉闷、混乱的声音，并得出结论：“这首歌纯粹是噪音。”

之前的研究人员戴着那些“耳机”（标准的数学工具）。他们看到了“沉闷的撞击声”（稠密的频谱），并认为机器人正在使用一种复杂且无法解释的方法。而本文的作者只是摘掉了耳机，切换到了正确的频率，然后意识到机器人实际上正在演奏一段优美、简单的旋律。

核心启示

本文的主要教训不仅仅关于数学，更关于我们如何看待事物。

教训： 如果你试图理解一个复杂的系统（比如一个 AI 或一群人），请确保你使用的是适合该任务的“语言”或“基底”。
结果： 当你将分析工具与问题的实际结构相匹配时（在这种情况下，使用针对乘法的“乘法”透镜），混乱、无法解释的噪音就会变成清晰、简单且可理解的算法。

机器人并没有发明一种全新的、神秘的数学方法。它只是找到了一个能将难题转化为易题的秘密代码，而研究人员终于学会了如何解读这个代码。

技术摘要：离散对数时钟 (The Discrete-Log Clock)

问题陈述
虽然 Transformer 学习模加法 ( $a + b \mod p$ ) 的内部机制已被完全逆向工程为稀疏傅里叶表示（即“时钟”算法），但模乘法 ( $a \cdot b \mod p$ ) 的机制一直难以捉摸。先前的实证研究（Doshi 等人，2024；Furuta 等人，2024）指出，在乘法任务上训练的 Transformer 学习到的是需要所有频率的“稠密”傅里叶谱，这与加法中发现的稀疏结构形成了鲜明对比。这表明乘法可能依赖于一种本质上不同且更难解释的算法。

方法论
作者训练了一个单层解码器（decoder-only）Transformer，用于预测输入 $a, b \in \{1, \dots, 112\}$ 时 $a \cdot b \mod 113$ 的结果。模型在 30% 的数据上进行训练，并必须泛化到剩余的 70% 数据，展现出“顿悟”（grokking）现象——即在经历了长时间的记忆阶段后，泛化能力突然出现。

核心方法论创新在于分析基底（basis）的转变。作者并没有对 Token 嵌入应用标准的加法离散傅里叶变换（DFT），而是应用了乘法特征变换（multiplicative character transform）。这包括：

识别出模 $p$ 的非零整数构成一个循环群 $(\mathbb{Z}/p\mathbb{Z})^*$ 。
使用原根 $g$ （此处 $g=3$ ）将输入映射为其离散对数： $\alpha = \log_g(a)$ 且 $\beta = \log_g(b)$ 。
根据这些离散对数对嵌入矩阵的行进行重新排序。
对重新排序后的数据应用标准 DFT。

这种方法利用了群同构性质，即原始空间中的乘法对应于对数空间中的加法（ $a \cdot b \equiv g^{\alpha + \beta} \mod p$ ）。

关键结果

谱稀疏性： 当在加法基底下进行分析时，嵌入谱表现为平坦且稠密的（基尼系数为 0.07）。然而，在乘法特征基底下，谱变得高度稀疏（基尼系数为 0.58），能量集中在仅有的 4 个关键频率（ $\{2, 8, 47, 56\}$ ）上。
神经元调谐： 在乘法基底中，96.9%（496/512）的 MLP 神经元被“清晰地调谐”到单一频率，超过 85% 的激活能量都集中于此。而在加法基底中，没有任何神经元能达到这一阈值。
结构可视化： 当神经元激活热图按离散对数重新排序时，它们呈现出清晰的二维周期性对角条纹。这表明神经元在计算形式为 $\cos(k(\alpha + \beta))$ 的函数，实际上是在执行对数空间中的加法。
SVD 分析： 经由离散对数重新排序后的嵌入矩阵主成分呈现出清晰的正弦结构，证实了乘法特征的编码。

“离散对数时钟”算法
论文得出结论，Transformer 实现了一种类似于加法“时钟”算法的机制，称之为离散对数时钟（Discrete-Log Clock）。该机制的过程如下：

嵌入： 将整数嵌入为与其离散对数相关的正弦函数。
路由： 注意力机制将这些嵌入路由至输出位置。
组合： MLP 应用三角恒等式来计算离散对数的和（有效地计算 $\alpha + \beta$ ）。
解码： 模型通过将候选输出与计算出的对数空间之和进行对齐来评分，其中正确的答案会在关键频率上实现相长干涉。

意义与主张
其主要贡献在于证明了先前研究中观察到的“稠密谱”其实是由于使用了错误的分析基底而产生的伪影，而非反映了算法的复杂性。通过将分析基底与任务的代数结构（乘法群）相匹配，作者揭示了乘法可以被简化为离散对数空间中的加法。

论文声称该方法具有通用性：

这种稀疏的乘法谱在 10 个不同的质数（ $p=59$ 至 $113$）中均得到了确认。
该机制在随机种子下具有普适性（约 80% 的种子符合）。
初步结果表明，通过使用两层 Transformer，该方法可以扩展到模幂运算（ $a^b \mod p$ ）。

作者强调，对于任何代数任务，应用相关群上的傅里叶变换（而非标准的加法 DFT）对于在标准工具只能看到噪声的地方揭示可解释的结构至关重要。