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

AI summary

Overview

Research area: Machine learning for algorithmic and cryptographic pattern recognition — specifically, whether Transformer models can learn to predict the output of pseudo-random number generators (PRNGs).

Technical level: Advanced. The paper assumes familiarity with Transformer architectures, in-context learning, pseudorandom number generators, modular arithmetic, and interpretability techniques such as principal component analysis.

Scope: A systematic study of how well Transformers can learn and predict sequences from Permuted Congruential Generators (PCGs), including scaling behavior with modulus, the necessity of curricula, and the structure of learned internal representations.

What This Paper Is About

Pseudorandom number generators produce sequences that pass statistical tests for randomness but are actually governed by hidden deterministic rules. This paper asks whether a Transformer can discover those hidden rules well enough to predict unseen PCG output sequences, given only examples of the sequences rather than knowledge of the generator's parameters. PCGs are substantially harder than the linear congruential generators (LCGs) studied in prior work because they apply shifts, XORs, rotations, and truncations to the hidden state before producing output.

Key Contributions

1. In-context prediction of PCGs beyond classical attacks. The authors show Transformers can predict PCG sequences from multiple variants, generalize to unseen multiplier and increment parameters (a, c), and remain accurate even when the output is truncated to a single bit — a setting where classical cracking methods that assume known modulus and multiplier do not apply.

2. A scaling law with modulus. Across moduli from 2^14 to 2^22, the number of in-context sequence elements needed to exceed 90% test accuracy grows as sqrt(m), steeper than the m^0.25 law previously observed for LCGs.

3. Demonstration that curriculum learning is essential at large moduli. For m ≥ 2^20, direct training fails within the fixed budget (75k steps, batch size 512). Mixing in data from smaller moduli, decaying that mixing probability to zero, and initializing from a smaller-modulus model removes a long stagnation phase and broadens the range of stable learning rates.

4. An interpretability finding about embeddings. PCA of the token embedding matrix reveals that the top principal components spontaneously group integer tokens into bitwise rotationally-invariant clusters, and that intermediate activations separate different PRNG variants without explicit supervision.

Main Findings

• Multiple variants learned jointly. A single model trained on the combined dataset (all four generator types) reaches over 90% test accuracy after seeing 512 in-context elements, across all variants. When trained on separate datasets, models reach near-perfect accuracy after only 128 in-context elements. Truncated LCGs are learned fastest; permutations with more control bits converge more slowly and to lower accuracy.

• Robustness to truncation is surprising. In truncated LCGs with m = 2^16, even with only the top k = 1 bit retained, the model attains 95% accuracy at the 256th element, far above the random-guessing baseline of 1/2^k.

• Scaling law quantified. The context length required to exceed 90% test accuracy scales as (1/2)·sqrt(m). Changing the accuracy threshold to ε + 1/sqrt(m) or γ/sqrt(m) gives exponents β in [0.4, 0.5] and [0.33, 0.34] respectively. Inference-time compute for over 90% accuracy scales as m^0.53 (for L ≤ d_model), compared to m^2.5 for a brute-force search baseline.

• Large moduli stall without help. Training at m_test = 2^20 from random initialization without curriculum does not converge within 75k steps, remaining stuck at high loss and only 4% accuracy at the 640th token. Pretrained initialization from a smaller-modulus model provides the main benefit; curriculum adds further gains.

• Dataset size saturates quickly. For m = 2^16 there are 16,384 valid multipliers and 32,768 valid increments under the Hull–Dobell conditions, giving over 5×10^8 possible (a, c) pairs, but n_a = n_c = 1024 already provides enough diversity for generalization. Increasing dataset size lowers training accuracy at early positions (e.g., the 64th) while improving test accuracy at intermediate positions (e.g., the 128th) — a shift from memorization toward generalizable strategies.

• Larger models are more element-efficient. Larger models need only half as many observed elements, matching smaller models' 256th-position accuracy by the 128th position. Nearly perfect prediction at 128 positions is reached once n_layers ≥ 4 and n_heads ≥ 8. A 1-layer model solves XSLRR 14/7, indicating depth 1 can suffice for small-modulus variants.

• Embedding structure encodes bit statistics. PC1 perfectly correlates with the total number of zero bits N_0 in a token; PC2 perfectly correlates with the number of zero runs; PC3 captures an even–odd bit imbalance, proportional to (b_0+b_2+b_4+b_6) − (b_1+b_3+b_5+b_7). These grouping rules persist across moduli, which the authors argue explains why pretrained initialization transfers.

• Variants separate in middle layers. In a 4-layer model trained on the combined dataset, the third-layer MLP output already distinguishes truncated LCGs from PCG variants by the 64th token position and cleanly separates all PCG variants by the 128th. Separation is weakest in the embeddings and first layer and rises through the middle MLP and attention layers.

• Curriculum details. In the data-mixing study, the mixing ratio α is decayed to zero over 40k steps; exponential decay schedules outperformed cosine, linear, and step decay. The best performance was at initial mixing ratio α = 1%. Even when m = 2^16 is not itself learned, mixing a small fraction of its data substantially boosts performance on m = 2^18.

• Comparison to classical attacks. Classical work by Bouillaguet et al. (2020) attacks XSLRR-128/64 assuming knowledge of the multiplier, modulus, and permutation, recovering the state from 64 outputs, with worst-case wall-clock time of 20,000 CPU hours. It does not provide an asymptotic scaling law with modulus. PCGs pass BigCrush at only a 49-bit state (m = 2^49) or less, whereas LCGs require 88 bits (m = 2^88).

Methodology in Plain English

The researchers treat PRNG prediction as a next-token prediction task. They generate datasets of sequences from PCG variants — TLCG (truncated LCG), XSLRR, XSHRR, and XSHRS — with parameters a and c chosen per the Hull–Dobell theorem to guarantee a maximal period. Crucially, test sequences use a and c values never seen during training, so success requires generalization rather than memorization.

They train GPT-style decoder-only Transformers with Rotary Positional Embeddings (RoPE) to autoregressively predict the next number. Unless otherwise stated, models use 4 layers, 8 attention heads, and embedding dimension 1024. The vocabulary size equals 2^k when predicting k-bit outputs; at m = 2^22 with k = 11, the vocabulary is 2048 and the model has 52M parameters. They avoid bit-wise tokenization because it multiplies sequence length by k and makes training much more expensive. Training uses cross-entropy loss and AdamW with batch size 512 for 50k–100k steps, linear warm-up followed by cosine decay.

At m = 2^16 they fix sequence length to L+1 = 513 and use n_a = n_c = 1024, giving roughly 5.4×10^8 tokens. At m = 2^22 they use n_a = n_c = 2048 and L+1 = 1280, giving roughly 5.4×10^9 tokens. For m ≥ 2^16 they set L > (1/2)·sqrt(m) to supply enough context.

To rescue large-modulus training, they use two strategies: (1) a curriculum that mixes in data from a smaller modulus with probability α that decays to zero, and (2) pretrained initialization, transferring the overlapping portion of the embedding matrix from a smaller-modulus model while randomly initializing the additional tokens needed for the larger vocabulary. They then apply PCA to the learned embedding matrix and measure cosine similarity/dissimilarity between internal representations for different generator variants.

Why This Matters

Impact on research. The paper pushes the frontier of what Transformers can learn from data with hidden algebraic structure. It shows that models can recover regularities far more intricate than plain LCGs — including cases involving truncation to a single bit — and it quantifies the cost of doing so as a concrete scaling law. It also connects machine learning interpretability to the classical learning-versus-cryptography duality, suggesting that AI-based attacks on PRNGs merit attention when reasoning about cryptographic hardness assumptions.

Real-world applications:

• Evaluating PRNG security margins. Since PCGs are used in practice (XSLRR-128/64 is NumPy's default generator), understanding how much data and context a learned attacker needs informs how much trust to place in such generators for non-cryptographic simulation and sampling.
• Random number generation in numerical work. Scientific computing, Monte Carlo simulation, and machine learning pipelines all depend on PRNGs like NumPy's default; knowing where learned models succeed clarifies which generation regimes are fragile.
• Curriculum design for hard learning tasks. The finding that mixed-modulus data and pretrained initialization remove stagnation phases is directly transferable to other settings where the target task is too hard to learn from scratch under a fixed compute budget.
• Representation transfer across scales. The discovery of modulus-invariant embedding structure offers a template for how representations learned on a smaller instance of a problem can be reused when scaling to a larger instance.

Industry relevance. The results are relevant to practitioners training large models on algorithmic or structured data who need efficient training recipes under limited compute, and to security researchers who assess whether hardness assumptions hold against modern AI systems. The paper's curriculum and initialization techniques — 1% mixing ratio, exponential decay, embedding transfer — are simple and directly applicable.

Future Directions

1. A full mechanistic account. The authors explicitly state that a complete mechanistic description of the solution the model implements remains an open direction; the PCA analysis characterizes embedding structure but does not fully explain the computation.

2. Approaching cryptographically secure generators. Whether Transformers can be scaled to attack generators with genuine cryptographic hardness assumptions is left as an important open question.

3. More efficient architectures for attacks. The paper notes that state-space models (such as Gu and Dao, 2024) or efficient attention mechanisms could improve the inference-time compute scaling law for machine-learning-based attacks on PRNGs.

4. Understanding the residual bitwise patterns. The step-like accuracy improvements at powers of two in PCGs persist despite the permutations, and the authors state they have not studied the precise nature of these residual patterns in the PCG setting.

Target Audience

This paper is best suited for machine learning researchers working on in-context learning, scaling laws, and interpretability; for cryptography and security researchers interested in AI-based attacks on pseudorandom number generators; and for advanced graduate students or practitioners with a solid grasp of Transformer architectures and modular arithmetic. Readers looking for a beginner-level introduction to either Transformers or PRNGs will find the paper assumes substantial background in both.

Authors’ 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}$ using up to $50$ million model parameters and datasets with up to $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$: the number of in-context sequence elements required for near-perfect prediction grows as $\sqrt{m}$. For larger moduli, optimization enters extended stagnation phases; in our experiments, learning moduli $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 top principal components spontaneously group the integer inputs into bitwise rotationally-invariant clusters, revealing how representations can transfer from smaller to larger moduli.