🔬 condensed matter

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

本文表明，通过课程学习和发现位旋转不变表示，Transformer 模型能够成功学习并预测来自复杂置换同余生成器（PCG）的序列，并揭示了一种所需上下文长度随模数平方根增长的缩放法则。

原作者： Tao Tao, Maissam Barkeshli

发布于 2026-07-17

📖 1 分钟阅读☕ 轻松阅读

原作者： Tao Tao, Maissam Barkeshli

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

想象一下，你正试图教一个机器人预测魔术中的下一个数字。你向它展示一个序列，比如 3, 7, 15, 31，然后它必须猜出下一个数字是什么。在现实世界中，计算机使用被称为“伪随机数生成器”（PRNG）的特殊配方来创建看起来完全随机的数字，比如一副扑克牌的洗牌过程，或是旧电视上的雪花噪声。但对计算机而言，这些数字绝非随机，而是遵循着严格且隐藏的数学规则。如果你知道这个规则和起始数字，你就能完美预测整个序列的未来。

长期以来，科学家们一直在思考：现代人工智能，特别是被称为“Transformer”的一种模型类型（也就是许多聊天机器人和图像生成器背后的那种“大脑”），能否仅仅通过观察示例就推导出这些隐藏的规则？这就像是在问，一名学生能否仅通过观察几次别人开锁的过程，就在不被告知锁是如何运作的情况下，破解出锁的秘密代码。这意义重大，因为这些数字生成器是计算机安全的基石。如果 AI 能如此轻易地破解它们，可能意味着我们的数字锁并不像我们想象得那样安全。但如果 AI 无法破解它们，则说明了这些模型是如何学习模式的，以及它们的局限性在哪里，这具有深刻的启示意义。

论文的故事：带有转折的破解密码

在这篇论文中，作者为 Transformer 设置了一个挑战，使用的是一类特定的、难度极高的数字生成器，称为“置换线性同余生成器”（PCG）。把标准的数字生成器想象成一个简单的机器，它通过加法和乘法来获取下一个数字。而 PCG 是同一个机器，但它带有一个转折：在向你展示结果之前，它会利用一系列位移、翻转和旋转操作来打乱比特位（构成数字的微小 0 和 1）。这就像是把一条秘密信息写下来，然后通过移动字母使其看起来像乱码，尽管原始信息本身是非常逻辑严密的。

研究人员发现，Transformer 的表现出奇地好。即使计算机只能看到输出中极小的一块被扰乱的部分——有时甚至只是一个比特（例如一个简单的“是”或“否”）——该模型仍然能以很高的准确度预测下一个数字。这仿佛机器人在观察一张被扰乱图像中的单个像素，却不知为何能洞察整幅图像的模样。模型学会了这样做，而无需被告知规则；它们只是通过提供的示例推导出了模式。

然而，这里有一个陷阱。谜题越难，机器人需要的帮助就越多。作者发现了一个“缩放法则”：随着数字变得越来越大（具体来说，随着模数，即数字池的大小增长），模型需要看到更多连续的示例才能解开谜题。如果数字较小，模型需要看到大约 128 个示例。如果数字非常巨大（例如 $2^{22}$ ），模型则需要看到大约 $\sqrt{m}$ 个示例，这意味着上下文长度必须显著增加。这就像是在玩拼图：如果碎片很小，你就需要手里握住更多的碎片才能看清全貌。

最令人兴奋的发现是关于模型如何学习的。当研究人员尝试直接在最难、最大的谜题上训练模型时，模型卡住了。模型盯着数据看了很久，几乎没有任何进展，就像一个学生盯着自己无法理解的数学题发呆。但当他们使用“课程学习”（一种教学策略，即从简单的、小的谜题开始，然后逐渐引入更难的谜题）时，模型突然掌握了。这就像是模型需要先学会走路才能奔跑。通过从小规模开始，模型学习了数字生成的底层“语法”，然后它就能将这些知识应用到庞大且复杂的谜题中。

作者还窥探了模型的“大脑”（其内部数据表示），并发现了令人着迷的现象。模型不仅仅是在死记硬背数字，它还根据二进制结构对数字进行了组织。它将具有相似 0 和 1 模式的数字归为一类，即便这些数字在表面上看起来完全不同。这表明模型发现，用于生成器的“打乱”规则会将某些比特模式视为相同，并且它学会了尊重这些规则。这说明模型并非仅仅在猜测，它正在构建关于隐藏数学对称性的心理地图。

简而言之，这篇论文表明，Transformer 可以学习预测复杂的、经过打乱的数字序列，即使信息被大量削减。但它们需要正确的训练路径：从小处着手，循序渐进。虽然它们可以胜过一些传统的黑客方法，但在没有这种辅助性课程的情况下，面对过大的数字时仍会撞墙。这告诉我们，尽管 AI 在寻找隐藏模式方面变得越来越强，但它仍然依赖于一种结构化的学习方式，就像人类学生一样，去应对最困难的数学奥秘。

技术摘要：利用 Transformer 学习伪随机数

问题陈述

本文研究了 Transformer 模型学习并预测由置换同余生成器 (PCGs) 生成的序列的能力，PCG 是一个广泛使用的伪随机数生成器 (PRNG) 家族。虽然 Transformer 在各种算法任务的上下文学习 (ICL) 中已展现出成功，但关于其是否具备发现旨在通过统计随机性测试的数据中隐藏的确定性模式的能力，仍存在根本性的疑问。

相比线性同余生成器 (LCGs)，PCGs 提出了更具挑战性的任务。LCGs 遵循简单的线性递推关系（ $s_i = (a s_{i-1} + c) \mod m$ ），而 PCGs 在输出 $x_i$ 之前会对隐藏状态 $s_i$ 应用一个复杂的函数 $f$ 。该函数涉及位移、异或 (XOR)、旋转和截断操作。这些操作旨在掩盖底层的线性结构，使 PCGs 能够抵御那些假设已知模数和乘数的经典代数攻击。作者旨在确定 Transformer 是否能在没有明确获知生成器参数的情况下，发现这些隐藏的递推关系和置换结构，并理解其学习机制与局限性。

研究方法

实验设置

本研究使用包含多种 PCG 变体（XSLRR, XSHRR, XSHRS）和截断型 LCG (TLCG) 的受控基准测试进行研究。

生成器： 内部状态 $s_i$ 通过 LCG 演化，输出 $x_i = f(s_i)$ 通过特定的置换导出。作者改变了模数 $m$ （从 $2^{14}$ 到 $2^{22}$ ）和输出大小（例如，从 16 位状态中提取 8 位输出）。
数据集： 采用了两种设置：
1. 分离式 (Separate)： 在单一生成器类型上进行训练和测试。
2. 组合式 (Combined)： 在所有生成器类型的混合数据上进行训练和测试，要求模型能够区分不同的置换规则。
- 数据集使用未见过的乘数 ( $a$ ) 和增量 ( $c$ ) 生成，以测试泛化能力。
模型架构： 使用带有旋转位置嵌入 (RoPE) 的 GPT 式仅解码器 (decoder-only) Transformer。实验对模型深度（1–6 层）、宽度（注意力头）以及基于输出位宽的词表大小进行了缩放。
训练： 模型采用自回归方式进行训练，使用交叉熵损失来预测下一个 token。训练过程包括多达 100k 个步长，批大小为 512。

关键技术

课程学习 (Curriculum Learning)： 对于大模数（ $m \ge 2^{20}$ ），直接训练往往会失败，导致长时间的停滞。作者引入了一种课程策略，将来自较小模数的训练数据混合到较大模数的训练集中。混合比例 $\alpha$ 随训练步数呈指数级衰减。
预训练初始化： 在较小模数上训练的模型被用于初始化较大模数任务的权重，从而迁移所学习到的嵌入结构。
可解释性分析： 作者对 token 嵌入进行主成分分析 (PCA)，并分析注意力模式，以理解模型如何表示输入数据。

核心贡献与结果

1. 成功的上下文预测

Transformer 可以成功地对多种变体的 PCG 序列进行上下文预测，并能泛化到未见过的参数 ( $a, c$ )。

性能： 在观察约 512 个上下文元素后，模型在多种不同的 PCG 变体上达到了 >90% 的准确率。
鲁棒性： 即使输出被严重截断（例如，仅保留状态的最高一位），预测依然保持稳健，且模型的表现显著优于随机猜测。
泛化能力： 这种能力超过了已发表的经典攻击，后者通常需要预先知道模数和乘数。

2. 缩放法则 (Scaling Laws)

论文确定了一个关于成功预测所需的上下文长度的特定缩放法则：

上下文长度 vs. 模数： 实现超过 90% 准确率所需的上下文序列元素数量随 $\sqrt{m}$ 缩放。这比 LCG 中观察到的 $m^{0.25}$ 缩放更为陡峭，反映了 PCG 置换引入的信息掩盖效应。
模型规模： 更大的模型（增加深度和宽度）需要更少的观察元素即可达到相同的准确率，这表明规模的提升有助于更高效地开发策略。

3. 课程学习的必要性

对于大模数（ $m \ge 2^{20}$ ），在固定计算预算下的直接训练会导致长时间的停滞阶段，且损失函数几乎没有下降。

课程学习的有效性： 将较小模数的数据纳入其中（例如，将 $m=2^{16}$ 的数据混合进 $m=2^{18}$ 的训练中）可以消除停滞阶段，扩大稳定学习率的范围，并产生显著更强的最终性能。
预训练： 使用较小模数模型的权重进行初始化起到了离散课程的作用，使模型能够跳过初始停滞阶段并更快收敛。

4. 可解释性与表示

对学习到的表示进行分析揭示了新的结构性见解：

位运算聚类 (Bitwise Clustering)： 嵌入矩阵的 PCA 显示，token 会自发地根据位旋转不变结构进行聚类，具体表现为连续零运行（zero runs）的数量和排列（例如， $Z(1), Z(2,1)$ ）。
可迁移性： 这种聚类结构在不同模数之间保持一致，解释了为什么预训练初始化是有效的；模型内化了生成器固有的不变性。
生成器区分： 在组合训练设置中，模型的中间层激活（特别是第三层的 MLP）能够自发地区分不同的 PRNG 变体，即使没有针对生成器身份的显式监督。

意义与主张

该论文声称，Transformer 具有在设计用于呈现随机性的数据中发现隐藏确定性模式的卓越能力，其能力超越了依赖于生成器参数显式知识的经典代数攻击。

这项工作强调，尽管 Transformer 可以学习复杂的 PRNG 结构，但它们面临着独特的缩放约束。上下文长度需随 $\sqrt{m}$ 增长的要求，以及在大模数下对课程学习的必要性表明，虽然这些模型可以泛化到未见过的领域，但它们尚未能够在没有特定训练策略的情况下“破解”任意大或复杂的生成器。

对嵌入空间中旋转不变聚类的识别，为这些模型如何泛化提供了机械论解释：它们学习基于输入算法的对称性来表示输入，而非仅仅记忆特定序列。这为神经网络如何处理模运算和基于置换的任务提供了新的视角，架起了算法推理与统计模式识别之间的桥梁。

作者总结道，虽然 Transformer 可以有效地接近非加密型 PRNG 的预测，但对解决方案进行完整的机械论解释，以及探索它们攻击加密安全生成器的能力，仍是重要的未来研究方向。