🔬 condensed matter

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

This paper demonstrates that Transformer models can successfully learn and predict sequences from complex Permuted Congruential Generators (PCGs) through curriculum learning and by discovering bitwise rotationally-invariant representations, revealing a scaling law where the required context length grows as the square root of the modulus.

Original authors: Tao Tao, Maissam Barkeshli

Published 2026-07-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Tao Tao, Maissam Barkeshli

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to predict the next number in a magic trick. You show it a sequence like 3, 7, 15, 31, and it has to guess what comes next. In the real world, computers use special recipes called "Pseudo-Random Number Generators" (PRNGs) to create numbers that look completely random to us, like the shuffle of a deck of cards or the static on an old TV. But to the computer, these numbers aren't random at all; they follow a strict, hidden mathematical rule. If you know the rule and the starting number, you can predict the entire future of the sequence perfectly.

For a long time, scientists have wondered: Can modern AI, specifically a type of model called a "Transformer" (the same kind of brain behind many chatbots and image generators), figure out these hidden rules just by looking at examples? It's like asking if a student can learn the secret code of a lock just by watching someone open it a few times, without ever being told how the lock works. This is a big deal because these number generators are the backbone of computer security. If AI can crack them too easily, it could mean our digital locks aren't as safe as we think. But if AI can't crack them, it tells us something profound about how these models learn patterns and where their limits lie.

The Paper's Story: Cracking the Code with a Twist

In this paper, the authors set up a challenge for Transformers using a specific, tough family of number generators called "Permuted Congruential Generators" (PCGs). Think of a standard number generator as a simple machine that adds and multiplies numbers to get the next one. A PCG is that same machine, but with a twist: before it shows you the result, it scrambles the bits (the tiny 0s and 1s that make up the number) using a series of shifts, flips, and rotations. It's like taking a secret message, writing it down, and then shuffling the letters around so it looks like gibberish, even though the original message was perfectly logical.

The researchers found that Transformers are surprisingly good at this. Even when the computer only sees a tiny, scrambled piece of the output—sometimes just a single bit, like a simple "yes" or "no"—the model can still predict the next number with high accuracy. It's as if the robot is looking at a single pixel of a scrambled image and somehow knowing exactly what the whole picture looks like. The models learned to do this without being told the rules; they just figured out the pattern from the examples provided.

However, there's a catch. The harder the puzzle, the more help the robot needs. The authors discovered a "scaling law": as the numbers get bigger (specifically, as the modulus, or the size of the number pool, grows), the model needs to see more examples in a row to solve the puzzle. If the numbers are small, the model needs to see about 128 examples. If the numbers are huge (like $2^{22}$ ), the model needs to see roughly $\sqrt{m}$ examples, which means the context length has to grow significantly. It's like trying to solve a jigsaw puzzle: if the pieces are tiny, you need to hold a lot of them in your hand to see the picture.

The most exciting discovery was about how the model learns. When the researchers tried to train the model directly on the hardest, biggest puzzles, it got stuck. The model would stare at the data for a long time, making almost no progress, like a student staring at a math problem they don't understand. But when they used a "curriculum"—a teaching strategy where they started the model on easy, small puzzles and slowly introduced harder ones—the model suddenly got it. It was as if the model needed to learn to walk before it could run. By starting small, the model learned the basic "grammar" of the number generation, and then it could apply that knowledge to the giant, complex puzzles.

The authors also peeked inside the model's "brain" (its internal data representations) and found something fascinating. The model didn't just memorize the numbers; it organized them based on their binary structure. It grouped numbers that had similar patterns of zeros and ones, even if those numbers looked totally different on the surface. It seems the model discovered that the "scrambling" rules used by the generators treat certain patterns of bits as the same, and it learned to respect those rules. This suggests the model isn't just guessing; it's building a mental map of the hidden mathematical symmetries.

In short, the paper shows that Transformers can learn to predict complex, scrambled number sequences, even when the information is heavily cut down. But they need the right training path: starting small and building up. While they can outperform some old-school hacking methods, they still hit a wall when the numbers get too big without that helpful curriculum. This tells us that while AI is getting better at finding hidden patterns, it still relies on a structured way of learning, much like a human student, to tackle the most difficult mathematical mysteries.

Technical Summary: Learning Pseudorandom Numbers with Transformers

Problem Statement

The paper investigates the ability of Transformer models to learn and predict sequences generated by Permuted Congruential Generators (PCGs), a widely used family of pseudo-random number generators (PRNGs). While Transformers have demonstrated success in in-context learning (ICL) for various algorithmic tasks, fundamental questions remain regarding their capacity to uncover hidden deterministic patterns within data designed to pass statistical randomness tests.

PCGs present a significantly harder challenge than Linear Congruential Generators (LCGs). While LCGs follow a simple linear recurrence ( $s_i = (a s_{i-1} + c) \mod m$ ), PCGs apply a complex function $f$ to the hidden state $s_i$ before outputting $x_i$ . This function involves bitwise shifts, XORs, rotations, and truncations. These operations are designed to obscure the underlying linear structure, making PCGs resistant to classical algebraic attacks that assume knowledge of the modulus and multiplier. The authors aim to determine if Transformers can discover these hidden recurrence relations and permutation structures without explicit knowledge of the generator parameters, and to understand the mechanisms and limitations of such learning.

Methodology

Experimental Setup

The study utilizes a controlled benchmark using several PCG variants (XSLRR, XSHRR, XSHRS) and a Truncated LCG (TLCG).

Generators: The internal state $s_i$ evolves via an LCG, and the output $x_i = f(s_i)$ is derived through specific permutations. The authors vary the modulus $m$ (from $2^{14}$ to $2^{22}$ ) and the output size (e.g., 8-bit outputs from 16-bit states).
Datasets: Two settings are employed:
1. Separate: Training and testing on a single generator type.
2. Combined: Training and testing on a mix of all generator types, requiring the model to distinguish between different permutation rules.
- Datasets consist of sequences generated with unseen multipliers ( $a$ ) and increments ( $c$ ) to test generalization.
Model Architecture: GPT-style decoder-only Transformers with Rotary Positional Embeddings (RoPE). Experiments scale model depth (1–6 layers), width (attention heads), and vocabulary size (based on output bit-width).
Training: Models are trained autoregressively to predict the next token using cross-entropy loss. Training involves up to 100k steps with batch sizes of 512.

Key Techniques

Curriculum Learning: For large moduli ( $m \ge 2^{20}$ ), direct training often fails, leading to prolonged stagnation. The authors introduce a curriculum strategy where training data from smaller moduli is mixed into the larger modulus dataset. The mixing ratio $\alpha$ decays exponentially over the training steps.
Pretrained Initialization: Models trained on smaller moduli are used to initialize weights for larger modulus tasks, transferring the learned embedding structures.
Interpretability Analysis: The authors employ Principal Component Analysis (PCA) on token embeddings and analyze attention patterns to understand how the model represents the input data.

Key Contributions and Results

1. Successful In-Context Prediction

Transformers can successfully perform in-context prediction on PCG sequences from multiple variants, generalizing to unseen parameters ( $a, c$ ).

Performance: Models achieve >90% accuracy on diverse PCG variants after observing approximately 512 in-context elements.
Robustness: Prediction remains robust even when the output is heavily truncated (e.g., retaining only the single highest bit of the state), where the model significantly outperforms random guessing.
Generalization: This capability exceeds published classical attacks, which typically require prior knowledge of the modulus and multiplier.

2. Scaling Laws

The paper identifies a specific scaling law regarding the context length required for successful prediction:

Context Length vs. Modulus: The number of in-context sequence elements required to exceed 90% accuracy scales as $\sqrt{m}$ . This is steeper than the $m^{0.25}$ scaling observed for LCGs, reflecting the information obscuration introduced by PCG permutations.
Model Size: Larger models (increased depth and width) require fewer observed elements to reach the same accuracy, suggesting that scale allows for more efficient strategy development.

3. Necessity of Curriculum Learning

For large moduli ( $m \ge 2^{20}$ ), direct training within fixed compute budgets results in extended stagnation phases with minimal loss reduction.

Curriculum Efficacy: Incorporating data from smaller moduli (e.g., mixing $m=2^{16}$ data into $m=2^{18}$ training) eliminates the stagnation phase, broadens the range of stable learning rates, and yields substantially stronger final performance.
Pretraining: Initializing with weights from a smaller modulus model acts as a discrete form of curriculum, allowing the model to skip the initial stagnation phase and converge faster.

4. Interpretability and Representation

Analysis of the learned representations reveals novel structural insights:

Bitwise Clustering: PCA of the embedding matrix shows that tokens spontaneously cluster based on bitwise rotationally-invariant structures, specifically the number and arrangement of contiguous zero runs (e.g., $Z(1)$ , $Z(2,1)$ ).
Transferability: This clustering structure persists across different moduli, explaining why pretrained initialization is effective; the model internalizes the invariances inherent to the generator.
Generator Separation: In combined training settings, the model's intermediate activations (specifically in the third layer's MLP) spontaneously differentiate between distinct PRNG variants, even without explicit supervision on generator identity.

Significance and Claims

The paper claims to demonstrate that Transformers possess a remarkable ability to uncover hidden deterministic patterns in data designed to appear random, surpassing the capabilities of classical algebraic attacks that rely on explicit knowledge of generator parameters.

The work highlights that while Transformers can learn complex PRNG structures, they face distinct scaling constraints. The requirement for context length to grow as $\sqrt{m}$ and the necessity of curriculum learning for large moduli suggest that while these models can generalize to unseen regimes, they are not yet capable of "cracking" arbitrarily large or complex generators without specific training strategies.

The identification of rotationally-invariant clustering in the embedding space provides a mechanistic explanation for how these models generalize: they learn to represent inputs based on the symmetries of the underlying algorithm rather than memorizing specific sequences. This offers a new perspective on how neural networks process modular arithmetic and permutation-based tasks, bridging the gap between algorithmic reasoning and statistical pattern recognition.

The authors conclude that while Transformers can approach the prediction of non-cryptographic PRNGs effectively, a full mechanistic account of the solution and an exploration of their ability to attack cryptographically secure generators remain important directions for future work.