Learning Pseudorandom Numbers with Transformers: Permuted Congruential Generators, Curricula, and Interpretability
Tao Tao and Maissam Barkeshli
我们研究变形金刚模型学习由Permuted Congruential Generators(PCGs)生成的序列的能力,Permuted Congruential Generators(PCGs)是一个广泛使用的伪随机数生成器(PRNGs)家族。 PCG通过将一系列位向移位,XOR,旋转和截断应用于隐藏状态,从而对线性对数发生声响(LCG)施加了大量额外的困难。 我们表明,变形金刚可以成功地对来自不同PCG变体的看不见的序列进行上下文预测,这些序列超出了已发布的经典攻击。 在我们的实验中,我们使用多达5000万个模型参数和具有多达50亿个令牌的数据集将模数扩展到2^22。 令人惊讶的是,我们发现即使输出被截断到单个位,也可以通过模型可靠地预测。 当训练过程中将多个不同的PRNG一起呈现时,模型可以共同学习它们,从不同的排列中识别结构。 我们演示了具有模量 m 的缩放定律:近乎完美预测所需的上下文序列元素数量随着 √(m) 的增长而增长。 对于较大的模数,优化进入扩展的停滞阶段;在我们的实验中,学习moduli m ≥ 2^20需要结合来自较小模数的训练数据,这表明了课程学习的关键必要性。 最后,我们分析嵌入层并揭示一种新的聚类现象:模型自发地将整数输入分组到位旋转不变的聚类中,揭示表示如何从较小的模量传递到较大的模数。
We study the ability of Transformer models to learn sequences generated by Permuted Congruential Generators (PCGs), a widely used family of pseudo-random number generators (PRNGs). PCGs introduce substantial additional difficulty over linear congruential generators (LCGs) by applying a series of bit-wise shifts, XORs, rotations and truncations to the hidden state. We show that Transformers can nevertheless successfully perform in-context prediction on unseen sequences from diverse PCG variants, ...