使用 Transformer 学习伪随机数：置换同余生成器、课程学习与可解释性

论文信息

标题: Learning Pseudorandom Numbers with Transformers: Permuted Congruential Generators, Curricula, and Interpretability

作者: Tao Tao, Maissam Barkeshli

发布日期: 2025-10-30

arXiv ID: 2510.26792v1

PDF 链接: 下载 PDF

3 分钟速览

研究问题： 这篇论文旨在探究 Transformer 模型能否学习由置换同余生成器（PCG）生成的伪随机数序列，并揭示其学习机制和规律。
核心方法： 使用标准 Transformer 解码器架构，通过在大量 PCG 生成的序列上进行下一词预测训练，并引入课程学习策略来攻克大模数生成器的学习难题。
关键结果： 模型不仅能成功预测多种未见过的 PCG 变体序列，其实现近乎完美预测所需的上下文序列长度与模数 $m$ 的平方根成正比，即 $\sqrt{m}$ 。（见论文摘要）
主要局限： 实验所用的最大模数为 $2^{22}$ ，远低于真实密码学应用中常见的模数规模，且训练过程在优化大模数时会出现长时间的停滞。
适合读者： 对生成模型的理解能力、表示学习、伪随机数生成器安全性以及课程学习策略感兴趣的研究者和工程师。

论文背景和研究动机

伪随机数生成器（PRNG）是计算机科学和密码学中的基础工具。传统的线性同余生成器（LCG）结构简单，但也因此存在可预测性弱点。置换同余生成器（PCG）作为一种更先进的 PRNG 家族，通过引入位运算（如移位、异或、旋转和截断）来对 LCG 的内部状态进行混淆，极大地增强了输出的不可预测性。这种复杂性使得攻击 PCG 的经典方法面临巨大挑战。

本研究的核心动机在于探索深度学习，特别是 Transformer 模型，能否在没有先验数学知识的情况下，从纯粹的数据驱动角度 “破解” 这类复杂的生成器。这不仅仅是关于 PRNG 安全的课题，更深层次地，它探究了 Transformer 模型能否从看似随机的序列中学习到隐藏的高效确定性算法。作者指出，训练模型预测 PCG 序列，其任务难度远超针对 LCG 的已知经典攻击（见论文第 1 节），这为研究 Transformer 的算法学习能力提供了理想的试验场。

核心方法和技术细节

研究的实验设计围绕以下几个层面展开：

1. 生成器与数据生成： 论文聚焦于 PCG 家族，特别是其核心的 pcg_xsh_rr 等变体。其内部工作流为：首先由一个 LCG 更新状态，然后对该状态应用一系列位级混淆操作（XorShift, Random Rotation，即异或移位和随机旋转），最终输出经截断的结果。实验中的模数 $m$ 从 $2^{8}$ 一直到 $2^{22}$ 。即使输出被截断到仅剩最高位（1 比特），模型依然需要学习这些复杂的非线性变换。训练数据集由这些生成器产生的序列组成，规模高达 50 亿个 token。

2. 模型架构与预测范式： 模型采用标准的 Transformer 解码器架构，参数规模最大达到 5000 万。其任务被设定为上下文预测：输入一个序列的前 $k$ 个数字 $x_1, x_2, \dots, x_k$ ，要求模型预测下一个数字 $x_{k+1}$ 。这种范式迫使模型必须在推断时，于内部隐式地理解生成器的状态转移和输出函数，而不是学习一个简单的静态映射。

3. 课程学习策略： 这是成功训练大模数模型的关键技术。实验发现，当直接训练模数 $m \geq 2^{20}$ 的生成器时，模型优化会进入长时间的停滞期，难以收敛。为解决此问题，作者采用了课程学习：先在较易学习的小模数数据上训练模型，然后逐步混合或切换到更大模数的数据。这种策略被证明是必需的，它验证了从简单到复杂的训练路径对于学习此类高度复杂函数至关重要。

4. 表示学习的可解释性分析： 为了探究模型内部的运作机制，作者分析了模型的嵌入层。他们发现了一种新颖的聚类现象：模型自发地将整数输入按照 “位旋转不变性” 归类。这意味着其内部表示不是孤立地看待每个数字，而是捕捉到了数字在不同旋转下本质相同这一代数结构。这一发现揭示了模型是如何将从较小模数学到的知识迁移到较大模数上的。

创新点和贡献

1. 证明了 Transformer 学习复杂 PRNG 的可行性： 首次展示了 Transformer 能够成功地对 PCG 这类具有复杂位运算混淆的生成器进行上下文预测，其表现超越了已知的经典攻击方法。这是一个信号，即模型可以纯粹通过数据学习到高度复杂的离散确定性算法。

2. 发现并量化了关于模数的缩放定律： 论文明确提出了一个关键的缩放定律：实现近乎完美预测所需的上下文长度 $k$ 与模数 $m$ 的平方根 $\sqrt{m}$ 成正比。这不仅是一个工程经验，更为理解 Transformer 处理此类问题时的计算复杂性提供了理论指引。

3. 证实了课程学习的核心作用： 通过严格的实验对比，论文证明了课程学习是攻克大模数 PRNG 学习任务的必要条件，而非仅仅是加速收敛的技巧。这为未来用深度学习挑战更复杂的密码学难题提供了重要的训练方法论。

4. 提供了模型内部表示的可解释性发现： 嵌入层的旋转不变聚类现象，是理解模型如何抽象化代数概念的直接证据。它优雅地解释了模型泛化和知识迁移的机制——即通过发现不变的底层数学结构，而非记忆模式。

实验结果分析

实验结果系统性地支撑了论文的核心论点。

在预测准确率方面，即使 PCG 的输出被截断为单个比特，模型也能实现可靠预测。当训练中混合了多种不同排列结构的 PCG 变体时，模型能够进行联合学习，成功识别并区分不同生成器的内在规律，这显示了其强大的模式分离能力。

最关键的结果是缩放定律的验证。实验数据清楚地表明，随着模数 $m$ 的增大，要达到同样低的预测损失，模型需要的上下文序列长度确实遵循 $\sqrt{m}$ 的增长规律（见论文第 5 节及相应图表）。这不仅仅体现在一个模型或一个生成器变体上，而是在不同设置下都可复现。

在训练动力学上，针对大模数（ $m \geq 2^{20}$ ）的实验清晰地展示了直接训练的失败和课程学习的决定性作用。损失曲线表明，没有小模数数据作为基础，模型会在高损失区域停留近乎无限长的时间。而引入课程后，模型能够快速利用之前学习的表征，使大模数训练的损失平稳下降。

最后，通过对嵌入层的降维可视化分析，研究者直观地展示了整数如何根据其块旋转等效性被组织成簇，这强有力地支持了模型 “理解” 而非简单 “拟合” 数据的论点。

局限与待解决问题

尽管成果显著，但该研究存在明确的局限性，主要体现为以下两点。

首先，实验规模远未达到现实世界的安全级别。 论文中使用的最大模数为 $2^{22}$ ，而现代密码学 PRNG 使用的模数通常远超此量级。该缩放定律能否在更大数量级上继续保持，或者在更大模数下是否会遇到根本性的计算瓶颈，仍是未知数。论文的方法目前更像一个概念验证，而非对现有 PRNG 安全的直接威胁。

其次，优化停滞仍是巨大障碍。 即便使用了课程学习，训练过程在进入新的大模数阶段时仍会遭遇漫长的停滞期。如何设计更高效的优化算法或训练策略来克服这一障碍，是未来工作的重要方向。这暗示着，简单地增加数据和模型规模可能无法线性地缩短训练时间，算法的根本性低效问题有待解决。