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

Tao Tao, Maissam Barkeshli · 2025

Read Learning Pseudorandom Numbers with Transformers: Permuted Congruential Generators, Curricula, and Interpretability by Tao Tao, Maissam Barkeshli (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-26792.txt.

Introduction

Tao Tao and Maissam Barkeshli ask in 2025 if a Transformer can learn fake random numbers. A Transformer is a neural network, a program that learns patterns from data. Their source is a permuted congruential generator, a math rule that scrambles a hidden count.

Such rules shift bits, flip bits, turn bits, and cut bits to hide the count. The model still predicts new items in a sequence, even when one bit is shown. It can learn more than one rule at once and tell them apart. Small cases must come first, or large cases stall in training. The need for small cases first is a key lesson. Its inner layers group numbers by how their bits turn.

Catalog record

CREATORTao Tao, Maissam Barkeshli
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE62 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-26792

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Learning Pseudorandom Numbers with Transformers: Permuted Congruential Generators, Curricula, and Interpretability Tao Tao, Maissam Barkeshli Abstract 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, in tasks that are beyond published classical attacks. In our experiments we scale moduli up to 2 22 2^{22} using up to 50 50 million model parameters and datasets with up to 5 5 billion tokens. Surprisingly, we find even when the output is truncated to a single bit, it can be reliably predicted by the model. When multiple distinct PRNGs are presented together during training, the model can jointly learn them, identifying structures from different permutations. We demonstrate a scaling law with modulus m m : the number of in-context sequence elements required for near-perfect prediction grows as m \sqrt{m} . For larger moduli, optimization enters extended stagnation phases; in our experiments, learning moduli m ≥ 2 20 m\geq 2^{20} requires incorporating training data from smaller moduli, demonstrating a critical necessity for curriculum learning. Finally, we analyze embedding layers and uncover a novel clustering phenomenon: the model spontaneously groups the integer inputs into bitwise rotationally-invariant clusters, revealing how representations can transfer from smaller to larger moduli. 1 1 1 Code is available at https://github.com/TaoT1998/learn-pcg 1 Introduction Transformer-based models have achieved remarkable success across language, vision, and algorithmic tasks, demonstrating an ability to capture complex patterns from large-scale data ( Vaswani et al. 2023 ; Dosovitskiy et al. 2021 ) . Beyond supervised training, they can acquire new behaviors directly from examples provided in the input, a phenomenon known as in-context learning ( Brown et al. 2020 ; Olsson et al. 2022 ) . Despite these successes, fundamental questions remain: what kinds of patterns can Transformers reliably learn, how can we train them efficiently and what mechanisms underlie their ability to generalize? To address these questions, we use pseudo-random number generators (PRNGs) as a controlled benchmark. PRNGs are designed to pass statistical tests of randomness, yet their sequences are governed by hidden deterministic patterns. This contrast makes them an effective benchmark for testing whether Transformers can uncover hidden recurrence, scale to practical prediction tasks, and reveal the mechanisms that support generalization to unseen regimes. PRNGs also comprise a fundamental primitive in cryptography. Like all primitives, their cryptographic security is based on hardness assumptions and it is therefore imperative to understand the extent to which modern AI systems can successfully attack them. In this work, we focus on the widely used non-cryptographic family of Permuted Congruential Generators (PCGs) ( O’Neill 2014 ) . They are practically relevant as the default generator in NumPy. PCG generates outputs based on the recurrence: \displaystyle s_{i}=(as_{i-1}+c)\text{ mod }m,\;\;\;\;\;\;\;\;\;x_{i}=f(s_{i}), (1) where s_{i} is the hidden LCG state at step i , and x_{i} is the output. The parameters a , c , and m denote the multiplier, increment, and modulus, respectively, and are fixed for a given generator. The function f consists of a series of shifts, XORs, rotations and truncations to improve statistical quality and increase prediction difficulty. Transformers can learn linear congruential generators (LCGs) ( Tao et al. 2025 ) , but PCGs are far tougher: they pass BigCrush at only 49-bit state ( m{=}2^{49} ) or less, whereas LCGs require 88 bits ( m{=}2^{88} ) ( O’Neill 2014 ; L’Ecuyer & Simard 2007 ) . Our main findings are as follows: In-context prediction across PCG variants: Transformers can perform in-context prediction of PCG sequences from multiple variants without explicit knowledge of the generator, and they generalize to unseen parameters (a,c) . This capability goes beyond classical PCG attacks ( Bouillaguet et al. 2020 ) , which assume the modulus m and multiplier a are known and exploit the recurrence and permutation directly. Predictions remain remarkably robust under truncation: even when only the highest bit of s_{i} is retained in the output x_{i} , the model achieves accuracy far above random guessing. Scaling law with modulus: We evaluate PCGs with modulus m ranging from 2^{14} to 2^{22} . The number of in-context sequence elements required to exceed 90% prediction accuracy scales as \sqrt{m} . This scaling is steeper than the m^{0.25} law observed for LCGs. Curriculum is essential for large-modulus training: At large scales ( m\geq 2^{20} ), direct training fails within the fixed budget (75k steps, batch size 512): models enter a prolonged stagnation phase with minimal loss reduction. A curriculum learning strategy is found to be essential to surmount this difficulty. The model is initialized with weights from a model trained on a smaller modulus. During training, 1% of sequences are sampled from the smaller modulus, with this probability decayed to zero over the course of training. The curriculum provides two main benefits: (1) it removes the initial loss stagnation phase and yields substantially stronger final performance under the same budget, and (2) it broadens the range of stable learning rates. Interpretability of learned representations: Principle component analysis (PCA) of the embedding matrix reveals that when learning PCGs, the model spontaneously organizes tokens by rotation-invariant features of their binary representations. In particular, embeddings cluster by the number and arrangement of contiguous zero runs, a rule that remains consistent across different moduli. This structure emerges naturally when training on PCGs that apply rotations before the output, suggesting that the model has internalized the invariances inherent to the generator. When trained jointly on sequences from multiple distinct PCG variants, we show how the model’s intermediate activations learn to differentiate between sequences from different variants. 2 Experimental Settings Our experiments are designed to isolate how different aspects of PRNG structure, model configuration and training strategies affect prediction performance. Here we describe the generator variants, the datasets for training and evaluation, and the model architecture and training setups. 2.1 PCG Variants PCGs come in different varieties, depending on the precise set of shifts, XORs, rotations and truncations, encapsulated in the function f in Eq. 1 . When a and c are chosen according to the Hull–Dobell theorem ( Hull & Dobell 1962 ) , the state sequence {s_{i}} in Eq. 1 achieves the maximal period m . For power-of-two moduli, however, the bits of s_{i} exhibit position-dependent periodicities: the k -th least significant bit cycles with period 2^{k} , far shorter than the full state period m ( Knuth 1997 ) . This makes the low-order bits especially weak, revealing structural patterns in the generator. PCG permutations mitigate this weakness by redistributing high-period structure across all bit positions using operations like XOR, shifts, and rotations. We consider the following variants: • TLCG (Truncated LCG): Outputs only the high bits of the state. Part of the information of the internal state is hidden by the truncation. • XSLRR (XORShift Low with Random Rotation): The state is right-shifted by half the bit length of m and XORed with the original state, improving the quality of the lower half bits. This lower half is retained and

Read the complete text