Learning Pseudorandom Numbers with Transformers: Permuted Congruential Generators, Curricula, and Interpretability
Authors: Tao Tao
Maissam Barkeshli
Venue: ICLR 2026 Poster (2026)
Keywords: In-context Learning
Curriculum Learning
Interpretability
Transformers
Pseudo-Random Number Generators
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: Transformers in-context learn pseudo-random number sequences and curriculum accelerate convergence.

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 integers into bitwise rotationally-invariant clusters, revealing how representations can transfer from smaller to larger moduli.

Published as a conference paper at ICLR 2026
LEARNING PSEUDORANDOM NUMBERS WITH TRANS- FORMERS: PERMUTED CONGRUENTIAL GENERATORS, CURRICULA, AND INTERPRETABILITY
Tao Tao
Department of Physics, University of Maryland, College Park, USA
tao2021 @emmemuddeeee.
Maissam Barkeshli
Department of Physics, University of Maryland, College Park, USA Meta FAIR
Joint Quantum Institute, University of Maryland ma i
ABSTRACT
We study the ability of Transformer models to learn sequences generated by Per- muted Congruential Generators (PCGs), a widely used family of pscudo-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. our experiments we scale moduli up to 22 using up to 50 million model pa- rameters and datasets with up to 5 billion tokens. Surprisingly, the output is truncated to a single bit, it can be reliably predicted by the model. presented together during training, the model
find even when
When multiple distinct PRNGs can jointly learn them, identifying structures from different permutations. We demonstrate scaling law with modulus m: the number of in-context sequence elements required for near-perfect prediction grows as / For larger moduli, op- timization enters extended stagnation phases; in our experiments, learning moduli 2 2 requires incorporating training data from smaller moduli, demonstrat- ing a critical necessity for curriculum learning. Finally, we analyze embedding layers and uncover novel clustering phenomenon: the top principal components spontaneously group the integer inputs into bitwise itationally-invariann clusters, revealing how representations transfer from smaller to larger moduli.
INTRODUCTION
Transformer-basee based models have achieved remarkable success across language, vision, and algo- rithmic tasks, demonstrating an ability to capture complex patterns from large-scale data (Vaswani ct al. 2023 Dosovitskiy al. (021). Beyond supervised training, they can acquire new behaviors directly y from examples provided in the input, a phenomenon known as in-context learning (Brown al., 2020 Olsson et al. 2022). Despite these successes, fundamental questions remain: what kinds of patterns can Transtormers reliably Iearn, what are their ultimate limits. how can we train them efficiently and what mechanisms underlie their ability to generalize? One interesting direction to study these questions is in the context of learning data with pseudorandom structures. Specifi- cally, in this paper, 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 hid- den deterministic patterns. This contrast makes them an effective benchmark for testing the ultimate mnttern-recognitioon capabilities of Transformers in particular whether they uncover hidden currence, scale to practical prediction tasks, and reveal the mechanisms that support generalization unseen regimes.

---

Published as a conference paper at ICLR 2026
PRNGs also comprise fundamental primitive in eryptography. Like all primitives, their crypto- graphic security is based on hardness assumptions and it 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 practically relevant the default generator in NumPy. PCG generates outputs based on the recurrence:
8, = (as;-1 + e) mod m,
24 = (8:),
(1)
where s; is the hidden LCG state at step i, and z; is the output. The parameters a, C, and m denote the multiplier, increment, and modulus. respectively, and 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 (L.Gss) (Tao et al. 2025), but PCGs are far tougher: they pass BigCrush at only 49-bit state (m=244) or less,
whereas LCGs require 88 bits (m=2%6) (O'Neill 2014 L'Ecuyer & Simard 2007). Our main findings are as follows:
Transformers can perform in-context prediction of PCG sequences from multiple variants without explicit knowledge of the generator, and they gen- eralize to unseen parameters (a, c). This capability goes beyond classical PCG attacks (Bouillaguet et al. 2020), which assume the modulus 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; is retained in the output 2,, the model achieves accuracy far above random guessing.
In-context prediction across PCG variants:
Scaling law with modulus: We evaluate PCGs with modulus ranging from 2 to 2 The number of in-context sequence elements required to exceed 90% prediction accuracy scales as /m. This scaling is steeper than the m.25 law observed for LCGs.
Curriculum is essential for large-modulus training: At large scales (m 2 222), direct training fails within the fixed budget (75k steps, batch size 512): models enter prolonged stagnation phase with minimal loss reduction. A curriculum learning strategy is found to be essential to surmount this difficulty. The model initialized with weights from a model trained training, 1 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) 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.
smaller modulus. During
Interpretability of learned representations: Principal component analysis (PCA) of the embed- ding matrix reveals that when learning PCGs, the model spontaneously organizes tokens by features in their binary representations. In first two principal components, embeddings cluster by the number and arrangement of contiguous zero runs, 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, show how the model's 's intermediate activations learn to differentiate between sequences from different variants.
2 EXPERIMENTAL SETTINGS
Our experiments designed to isolate how different aspects of PRNG structure, model configura- tion 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 different varieties, depending on the precise set of shifts, XORs, rotations and trunca- tions, encapsulated in the function f in Eq. When and are chosen according to the Hull-Dobell theorem (Hull& & Dobell 1962), the state sequence s; in Eq. [ achieves the maximal period m. For pfwer-of-two two moduli, however, the bits of s, exhibit position-dependent periodicities: the k-th least significant bit cycles with period 2 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 per-
2

---

Published as a conference paper at ICLR 2026
X5LRR-168
XSHRR-16A
XSHRS--66 16/8
(g) STATE
CTRL
HIGH
LOW
HIGH
UNUSED
UNUSED
99 SHIFTED STATE
RIGHT SHIFT BY a BITS
6d) STATE
STAAT
ROTATE
ROTATE
OUTPUT
SHIFT
OUTPUT
20
BH
BR
Figure 1: Depiction of PCG protocols m 2 with 8-bit output. Left: XSLRR-16/8. (a) State
8t. The top 3 bits are control bits. (b) 8; is right-shifted by 8 bits. (c) The shifted state is XORed with st. (d) The lower bits are retained and rotated right by the value of the control bits to produce the output. Middle: XSHRR-16/8. 16/8. (c) State st, with the top 3 bits as control; the lowest few bits are unused. (f) s is right-shifted by bits. (g) The shifted state is XORed with s;. (h) The upper 8 bits immediately following the control bits are retained and rotated right by the control bits to produce the output. Right: KSHRS-16/8. (i) State 8;, with the top 2 bits as control bits. (i) 8; right-shifted by 3 bits. (k) The shifted state is XORed with 8,. (l) Starting from after the control bits, the output window is right-shifted by the control bits, producing the output.
mutations 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.
The state 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 retained and rotated by an amount determined by the control bits.
XSLRR (XORShift Low with Random Rotation):
XSHRR (XORShift High with Random Rotation): Applies right-shift smaller than XSLRR, then XORs with the original state. The higher bits are retained and rotated by an amount determined by control bits.
XSHRS (XORShift High with Random Shift): Applies smaller right-shift than XSLRR and XSHRR, followed by an XOR with the original state. The output window begins immediately after the control bits and is shifted right by an offset determined by those bits.
The permutations are illustrated in Figure I Bits are labeled from most significant (left, bit 16) to least significant (right, bit 1). Top row shows the internal state 8;, where the k-th bit in 8; has period 2*. The lower three rows show the function f. Bits are split into high and low, with the low bits enhanced by the higher bits during the permutation; cross-hatched overlaps mark areas enhanced by XOR. The final rotation and shift in the permutation are controlled by the top bits of the state. This ensures that all bits in the output inherit the full period of the highest bit, which is m. A full description of the initial-shift calculation and pseudo-code for each generator is given in Appendix A In practice, PCGs typically adopt a power-of-two modulus m 2 size ensuring that the control bits achieve maximal period. We denote generators as generator type-state size/output size; for example, XSLRR- 16/8 refers to an XSLRR generator with a 16 bit state and an 8-bit output.
2.2 DATASETS
We consider two settings:
Separate:
Training and test sets each contain sequences from the output of a single gener- ator type, with no mixing between types.
Combined: Training and test sets contain sequences from all four generator types.
In both cases, test sequences are generated from a, values not seen during training. The combined setting is more challenging, as the model must simultaneously learn and distinguish multiple gener- ation rules, effectively forming multi-task problem across PRNG variants. The separate setting, by contrast, isolates each variant, simplifying analysis. For scaling studies on dataset size, model size, and modulus, we focus the XSLRR variant.
3

---

Published as a conference paper at ICLR 2026
For given modulus m, select and according to the Hull- Theorem to ensure maximal period. The training set consists of sequences of length L+1, generated using nz distinct multipliers and n, distinct increments Each (a, c) pair contributes one sequence.
Specifically: For all experiments at y = 2 we fix the sequence length to I++1 = 513. For m 2 246, we increase the sequence length, setting I. > 2 V to provide sufficient context. At m = 236 (except in dataset scaling experiments), we use n4 - ne 1024, giving a dataset of 1024 x 1024 x 513 = 5.4 x 10 tokens. At m = 222,, we use nhe 2048 and L+1 = 1280,
giving a dataset of 2048 2048 x 1280 ~ 5.4 10 tokens.
2.3 MODEL AND TRAINING SETUP
We train Transformers to autoregressively predict the next number in sequences generated by PRNGs. Given an input To, .............. length L, the model outputs predictions é &2 ............ .z. We use a GPT-style decoder-only Transformer (Radford et al. (019) with Rotary Positional Embed- dings (RoPE) (Su et al. 2023). Except in the model scaling experiments, models use Tlayers = layers, Theads 8 attention heads, and embedding dimension of dmmodll 1024. The vocabulary size is 2 when predicting k-bit outputs. For example, at m 2 with k 11, the vocabulary size is 2048, and the model has 52M parameters. We did not use bit-wise tokenization because it in- creases the sequence length by a factor of k. making training substantially more expensive. Models trained with cross-entropy loss and the AdamW optimizer (Loshchilov & Hutter (019), using batch size of 512 for 50k-100k training steps. The learning rate uses a linear warm-up followed by cosine decay. The context length is T., corresponding sequences of length 1+1. Training details are provided in Appendix B
TRANSFORMERS CAN IN-CONTEXT LEARN PCGs
We find that Transformers achieve reliable in-context prediction across diverse PCG variants. As shown in Figure [a.c) a single model trained on the combined dataset reaches over 90% test accuracy after having seen 512 in-context elements of test sequence, across all PCG variants. We use "position index" to denote the location i within the predicted sequence. At position i, the model predicts the token ft given all previous tokens 10:((-1)- Training runs for 100k steps (about 8 epochs). For all generators we fix the generator state to 16 bits and the output to 8 bits. For XSLRR and XSHRR we evaluate both and 3-control-bit (eb) configurations, while for XSHRS the maximum feasible number of control bits is 2, since larger values would shift the output window beyond the available state length. Transformers can simultaneously learn multiple recurrence rules, whereas classical cracking algorithms are tailored to single generator. We observe systematic differences in convergence: truncated LCGs are learned fastest; permutations with more control bits converge more slowly and reach lower accuracy. When trained on separate generator datasets (Figure
2 b.d). models converge faster and achieve near near-perfect accuracy after having seen 128 in- context elements of the test sequence. This confirms that each generator type is fully learnable its own. Each model is trained for 50k steps, corresponding to 24 epochs.
The increased difficulty of the combined setting stems from the need to infer which permutation generated the sequence, as evidenced by the clear generator-wist separation emerging in the middle layers shown in Section 6.2] For both settings, test sets generated from unseen and values, demonstrating generalization to unseen parameters. This is beyond current classical attacks, which require prior knowledge of both m and a. Accuracy-position curves (Figure 23.d) exhibit siep improvements at powers of two. This is also observed in LCGs (Tao et al. (025). where models exploit bit periodicity and show sudden accuracy gains once low-order bits complete their cycle in context. The persistence of this phenomenon in PCGs shows that, despite added permutations, significant residual bit- patterns appear at certain positions in the sequence that the model can exploit, although we have not studied their precise nature here. As shown in Appendix H.2 the model's s attention patterns reflect this periodic structure.
4

---

Published as a conference paper at ICLR 2026
(a) Combined-16/8
(b) X6L8R-16/8
(c) 1omb
Separate-16/8
3.0
That Accurecy
Tert AcCurICc
Agg kut Tea
20000 3000 LC0030
Training Stepe
Training Stops
Position Index
Position Index
Figure 2: (a) Test accuracy at the 512th token during training on combined datasets of diverse PRNG variants. (b) Accuracy during training on XSLRR-16/8 dataset. "512th" refers the model's prediction accuracy at the 512-th token. "Avg" denotes accuracy averaged across all token positions. (c) Final test accuracy by position index for combined training. (d) Final test accuracy when trained separately on each generator type, where all variants achieve near 100% accuracy with only 128 in-context elements.
WHAT LIMITS PREDICTION PERFORMANCE?
4.1 EFFECT OF TRUNCATIONS
To quantify the difficulty introduced by truncation, we study truncated LCGs where the low bits of the internal state are hidden and only the top & bits are retained output. For 2 this yields a 216-k-to- -to-1 mapping from states to outputs, so smaller & increases ambiguity. To examine this effect, we train separate models for each k (Figure 3 left). Despite the severe information loss, the models are surprisingly robust to truncation. Even with k = 1, the model attains 95% accuracy at the 256th element, far above the random-guessing baseline of 1 1/2². At earlier positions (e.g., the 64th element), performance is lower under heavy truncation but improves quickly as & increases. These results indicate that Transformers can extract patterns even from heavily truncated outputs, with longer contexts compensating for reduced information.
4.2 SCALING STUDIES
Practical PCGs, such as the ISLRR-128/64 generator used as NumPy's default generator, operate at scale far beyond the 16-bit state settings. To bridge this gap, we study how performance on XSLRR changes when scaling along three axes: modulus m, dataset size, and model capacity.
We first analyze how the modulus affects prediction performance. Using a 4-layer, 8-head Transformer, we evaluate moduli ranging from m = 214 to m = 22 and observe clear scaling law: the number of sequence elements required to reach at least 90% test accuracy grows as Vm. This relationship is shown in Figure 3 (middle, right) and indicates that context length becomes the primary bottleneck as the modulus increases. Compared LCGs, where the requirement grows as 0.25 (Tao et al. 2025), PCGs demand substantially longer contexts, reflecting the information obscuration introduced by truncation and permutations. If we change the accuracy threshold from 90% to + 1/vm m or ///mm, where 1/ 1/ym is the threshold for random guessing, we find the scaling law for number of required in-context sequence elements x m² with B E [0.4, 0.5] and [0.33,0.3) 0.34), respectively. (See Appendix C.1
Effect of Generator Modulus:
In Appendix C.2 we compare our models' inference time compute scaling (xx 0.53 for L S dimauees which would x m once the context length becomes significant) for achieving over 90% accuracy to a brute force search baseline (x m²²3);; more efficient architectures, such as state-space models (Gu & Dao 2024) or efficient attention mechanisms, could improve the inference-time compute scaling law for ML-based attacks.
At large moduli, we use pretrained initialization combined with curriculum training (sce Section for details).
We assess how much data is required to solve the XSLRR- 16/8 prediction task by varying the number of distinct (a, c) pairs. For m = 21, there are 16,384 valid multipliers and 32,768 valid increments under the Hull-Dobol conditions, yielding over 5 x 10 possible (a, c) pairs. In practice, however, we find that only a small subset is sufficient to achieve general- ization, with ne ne 1024 already providing enough diversity (Figure 4 left). Moreover, as
Effect of Dataset Size:
5

---

Published as a conference paper at ICLR 2026
Truncated LOG
XSLRR
XSLRR
1.0
0-00000--000
0.8
Test Accuracy
Test Accuracy
0.6
128th
0.6
First Position
250th
20
0.4
random(3/21)
0.4
0.2
0.0
Vm
Kept
Position
Modullus
Figure 3: Left: Prediction accuracy at the 64th, 128th, and 256th sequence positions as a function of bits kept (k) in truncated LCGs with m = 2266 Accuracy improves with larger & and longer context, remaining far above the random baseline 1/2 even under severe truncation. Middle: For XSLRR, accuracy improves stepwise as more context is observed, with reliable predictions emerging once the context length reaches exactly / elements. Right: Context length required to exceed 90% test accuracy scales as 1 m with modulus m.
Dataset=1hc X nhe 513 tokens
128th Token Ace
256th Token Acc
1.0
6-
C.22
7.999
1907
0.8
Depth (Riggurs)
8:31
0383
Depth (Thagur))
799
1000
003
Test A Acuraay
Accuracy
-O- 64th
0.6
799
0.6
256th
Test
0.338
0333
0.4
train
0.20
5.34
6:34
6121
103
200
6:33
0.875
0973
3132
2201
0.0
256
na ne 2048
(4. 512)
(6. 768)
(6. 10241
(4. 5121
(6, 768)
1024)
(2heends dmoodll
128
7lboads)
Figure 4: Scaling studies of dataset size and model capacity. Left: Prediction accuracy at positions 64, 128, and 256 as a function of dataset size (n2, x n. sequences). Accuracy improves rapidly with sufficient diversity is reached. Middle and Right: Test accuracy
larger datasets and saturates heatmaps across model depth (Mayer)) and number of heads (Nheads). evaluated at positions 128 and 256. Larger models achieve higher accuracy, with nearly perfect prediction 128 positions once Tlayerr 2 4 and Thhcads 2 8.
dataset size increases, training accuracy at early positions (e.g., the 64th) decreases while test ac- curacy at intermediate positions (c.g., the 128th) improves, reflecting shift from memorization to more generalizable strategies. All experiments use fixed budget of 50k steps with batch size 512. Appendix [ shows that increasing n. ne has equivalent benefits, with clear advantage from expanding one parameter over the other.
Effect of Model Size: We evaluate performance XSLRR-16/8 while varying Transformer depth and width. Model width is controlled through the number of attention heads while keeping head dimension fixed 128. Figure 4 shows test accuracy at positions 128 and 256 across model sizes. Larger models need only half as many observed elements, matching smaller models' 256th-position accuracy by the 128th position, suggesting that increased scale allows the model develop more element-efficient strategies. Appendix E shows an 1-layer model solves XSLRR 14/7, indicating that depth can suffice for small-modulus PCG variants.
5 CURRICULUM LEARNING
Training directly on large-modulus generators leads slow convergence and can be unsuccessful within fixed compute budget. Here we show that curriculum learning strategies, where we incor- porate data from smaller moduli, are crucial in successfully training at large moduli.

---

Published as a conference paper at ICLR 2026
(a) 218
Fixed
(d) 256th Token Ace vs. a
feed 66
c=02-0
Weight Decay
6.3
E099
0.422
0.0
0.035
0.387
5.796
0.927
2.00
5.0
100
0.4
E000
00
0005
0.032
0.333
1055
0.334
1.00
Training
10:03
5,0001
0.092
34-05
0.0033
2.001
15" 30"
Alpha (0)
Figure 5: Effect of mixing smaller-modulus data on training stability and final accuracy. (a) Test loss m=21 under three training setups: training only m=21 (blue), fixed mixing with a=0.2 (orange), and curriculum mixing starting at 0.2 and decaying to over 40k steps (green). (b,c) Learning-rate and weight-decay landscapes for 256th-token accuracy on m=21 comparing training solely on m=21 (b) versus with the curriculum (c). (d) Test accuracy at the 256th token for both m=2 16 and m=218 under fixed mixing and curriculum mixing as the initial a varies.
5.1 DATA MIXING STRATEGIES: FIXED RATIO VS. CURRICULUM
To evaluate how mixed-moduuuu training improves large-modulus performance, we combine se- quences from XSLRR-18 18/9 (m = 218) with additional examples from XSIRRR-1688 (m 21)), where the mixing ratio specifies the probability of sampling from the = 2 dataset. In the cur- riculum setting, we decay a to zero over 40k steps, whereas in fixed-a training a is held constant. As shown in Figure Sla), both approaches remove the long stagnation observed when training solely landscapes with and without
on m = 218 Figure 5 b,c) compare the Seamning-rtteweiight-eee currieulum. Curriculum training substantially broadens the range of stable learning rates, enabling much larger step sizes without instability. Figure shows how varying the initial mixing ratio influences prediction accuracy under both fixed and curriculum training. The blue and orange curves show test accuracy on m= and m=218 respectively under fixed-or training. The green curve shows test accuracy on m=2 under curriculum training. These results demonstrate two key 16 itself is not learned, mixing a small fraction of its data substantially boosts performance on 1= (2) As increases, the model learns to handle both moduli simulta- neously. Curriculum consistently yields higher accuracy on m= than fixed-o, achieving its best performance initial mixing ratio a 1%. In Appendix [F] we compare cosine, exponential, linear, and step decay schedules for a and find exponential decay yields the best performance.
effects: (1) Even when m=
5.2 PRETRAINED INITIALIZATION LEVERAGING SMALLER-MODULUS MODELS
Using a model trained on a smaller modulus at initialization can be viewed as discrete form of curriculum learning. Instead of gradually transitioning from easy to hard data, the model is first exposed to the smaller modulus and then fine-tuned on the harder task. To evaluate whether the recurrence and permutation structures learned at smaller moduli transfer effectively to larger ones, train models on XSLRR-201 (220) and compare pretrained initialization against random initialization (Figure b).)). We evaluate four settings: (1) random initialization: train directly on XSLRR-20010 from scratch; (2) pretrained initialization: initialize from model trained XSLRR- 18/9 (m=211), then train on XSL-RR-00/10; 10; (3) smooth curriculum: start from random initialization but mix in data from XSLRR-IeS 16/8 during training (as Figure 12 shows, mixing in XSLRR-I84 gives little benefit); (4) smooth curriculum + pretrained initialization: initialize from XSLRR- 18/9 model and mix in XSLRR- smaller-
data. For curriculum training, the probability of sampling from the smaller-modulus modulus dataset starts at a 0.01 and decays exponentially to zero over the first 50k steps, after which training continues for an additional 25k steps exclusively on the target modulus. For pretrained initialization, the overlapping portion of the embedding matrix is transferred, while ad- ditional tokens required for the larger vocabulary are randomly initialized. Although higher moduli require longer contexts, RoPE's extended positional scaling allows pretrained models adapt the larger sequence lengths.
As shown in Figure training from random initialization without curriculum does not converge within the allotted 75k steps, remaining stuck at high loss and only 4% accuracy at the 640th token. Pretrained initialization provides the main benefit: models skip the long stagnation phase, converge faster, and consistently reach higher final accuracy than those trained from random initialization. Curriculum provides additional gains when combined with pretraining and, when used alone, par-
7

---

Published as a conference paper at ICLR 2026
Ao)e
LoiLon, g?)
le]Random Inis
[d]ttecrdieed Txit
Cosnre Distence
11t1 2016 2011
Tranding Stepe
Thanning Strges
Carteaa am 5o Carlocun 2m
Carticulurs
Cariccan
Figure 6: Impact of pretrained initialization and curriculum training on scaling to larger moduli. (a) Test accuracy the 640-th token on m across training steps. (b) Test loss on = across training steps. (c) Cosine distance of parameters from their final values and test loss when training a 3-layer Transformer from scratch for 400k steps. (d) Cosine distance of parameters from their final values and test loss when training the same model for 100k steps starting from a pretrained model. Shading in (c) and (d) shows the standard deviation
tially mitigates stagnation. Together, these results show that both pretraining and curriculum are crucial for scaling to larger moduli under fixed training budgets.
5.3 PRETRAINING AS A SHORTCUT TO STABLE REPRESENTATIONS
To understand why pretrained initialization accelerates training, we examine how model weights evolve over time. We train a three-layer Transformer on XSLRR-18/9 under two settings: (i) from scratch for 400k steps, and (ii) for 100k steps starting from a pretrained model on XSLRR-16/8 Figure tracks how each layer of the model changes during training by measuring the cosine distance between parameters at each step and their final trained values. The green curve represents the token embedding matrix, the orange curves correspond to the three Transformer layers, and the blue curve (right axis) shows test loss. In both training regimes, the embedding layer reaches usable representation first, after which the deeper layers evolve more rapidly. With pretrained initialization the model starts much closer to its final state: embeddings reach this usable representation almost immediately, allowing deeper layers to adapt right away. This strong embedding space prior shortens stagnation and accelerates convergence. As shown in the next section and in Appendix [H.T] clear structure in the embedding space persists across moduli, supporting this transfer effect.
6
INTERPRETABILITY OF MODEL REPRESENTATIONS
6.1 TOKEN EMBEDDINGS
To understand how Transformers model PCG patterns, analyze the token embedding layer of model trained on XSLRR-16/8. We apply principal component analysis (PCA) to the embedding matrix. The top principal components align with bit-level statistics of the tokens, reflecting the symmetries of the generator. The first two components in Figure 7 form clear clusters. To formalize the structure, we use zero-run notation Z(a,, a?....,,a. where each a; denotes the length of contiguous run of Os between 1s. The zero-run patterns and representative binary tokens for each cluster are shown Figure Rightt, with the complete listing provided Table [ We find that the first principal component (PC1) perfectly correlates the total number of zero bits N, in a token, while the second (PC2) perfectly correlates with the number of zero runs. Vertical bands in Figure correspond to constant No (e.g., clusters 6, 12, 16, and 18 all have No = 4), while horizontal groupings reflect constant run counts (e.g., clusters 10-14 all contain two zero runs). PC3 captures an even-odd bit imbalance in the token representation: PC²(x) x (bg + 62 64 + ba) (b, + by + by + by). where by denotes the i-th bit of the token. An analysis of higher components is provided in Appendix H.I.I As shown in Appendix H.Il these grouping rules persist larger moduli. The persistence of this learned structure across moduli explains why pretrained initialization so effective.
8

---

Published as a conference paper at ICLR 2026
Cluster
Zero-run pattern
Example
All 1s
11111111
00000000
0.58
5
6
Z(1)
01111111
7(2)
00111111
PC2 (0.040)
213)
00011111
0.23
2(4)
00001111
10
11
12
14
715)
00000111
Z(6)
00000011
15
16
17
10
Z(L1)
01011111
7(2
00101111
12
2(3.1), Z(2.2)
00010111
-0.45
18
Z(4.1). ZI3,2)
00001011
26,.), Zí4.2) Z(33))
00000101
15
2(1,1.1)
01010111
-0.60
-0.29
0.12
0.54
Z12.11)
7(3,1.1), 7(2,211
00010101
PC1 (0.051)
Z(LLLD
01010101
Figure 7: PCA of token-embedding matrix for XSLRR-16A (left) and cluster summary (right). To- kens group by rotation-invariant zero-run structures; full table with all tokens provided in appendix.
64th
128ch
6.75
XSHAA22
0.00
Suze
XSHR521
6.00
25UMNH
-0.25
ASHACH
TUCG
T.CG
-075
mn01
MUR
MU2
4003
1.00
Figure 8: Cosine similarity of representations across different PRNG variants for 4-layer Trans- former trained on the combined dataset. Numbers in parentheses indicate the number of control bits. Left: the 64th token position, third-layer MLP outputs already separate truncated LCGs from PCG variants, though PCG types remain highly overlapping. Middle: At the 128th token po- sition, the same MLP outputs cleanly separate all PCG variants. Variants with the same permutation type but different control-bit counts are more similar to each other than to other types. Right: Gen- erator separation across network for selected token positions (64th, 128th, 256th, 112hh defined mean off-diagonal cosine similarity. Higher values indicate stronger generator separation.
6.2 GENERATOR SEPARATION
When trained on combined datasets, the model develops a permutation-agnoost grouping of kens(Figure27), This raises the question of how the model is able to predict different PRNG variants at test time. Despite receiving no explicit supervision about generator identity, the model's internal representations spontaneously distinguish PRNG variants. In 4-layer model, this structure emerges most clearly in the MLP output of the third Transformer block: by the 64th token position, the model already distinguishes truncated LCGs from PCG variants, and by the 1 128th token, it cleanly differen- tiates between all PCG variants (see Figure g left and middle). To quantify this effect across layers, plot the average off off-diagonal cosine dissimilarity between generators each position (Figure right). Separation is weakest in the embeddings and first layer, rising sharply through the middle MLP and attention layers, suggesting that model first forms shared representation of the underlying recurrence and then, in deeper layers, refines generator-specific distinctions. In Appendix H.S we present head-level ablations showing that several attention heads in the last three layers specialize differently across generator variants.
7 RELATED WORK
Cracking PCGs: Classical approaches cracking PRNGs rely exploiting algebraic structure
with strong assumptions about the generator. Bouillaguet et al. (2020) present an attack on XSLRR- 128/64 that assumes knowledge of the multiplier, modulus, and permutation. The internal state

---

Published as a conference paper at ICLR 2026
be recovered from 64 outputs via a guess-and- guess-and-proeedure procedure. An asymptotic scaling law with modulus m is not provided in those attacks, although the wall-clock time is significant (20, 000 CPU hours in the worst case). In our work, the models must discover the hidden structure from training data alone, learning to predict outputs without explicit knowledge of the recurrence or transformation rules.
Curriculum Learning: Many studies have explored curriculum learning (Bengio et al. 2009), Wu
et al. ( finds that on standard benchmarks, explicit curricula offer little advantage when training steps are sufficient, but can yield higher accuracy and stability under limited compute or noisy data. Garg et al. 2023) observes that curriculum training can speed up training drastically when training Transformers to in-context learn linear functions. Recently [aaxena et al. (2024) observed that curriculum learning strategies can be helpful in modular addition.
AI for Cryptography: There classic duality between machine learning and cryptography
(Rivest) } Recently there has been increased interest in using modern Al systems to attack cryptographic schemes, such as the learning with errors problem (Wenger et al.) 2022). Our work builds on Tao et al. (2025), which uses transformers to learn vanilla LCGs.
Interpretability and Modular arithmetic: growing body of work examines how Transformers learn modular arithmetic tasks, uncovering phenomena such as grokking and structured internal
representations (Power et al. [2022] Gromov| [2023] Zhong et al.) 20233 Nanda et al.] 2023 Doshi
et al. 2024 Charton & Kempe 2024). Prior studies (Liu et al. 22022 He et al. 2024) also find
emergent structures in embedding matrices and interpretable attention patterns. Our work extends this literature by studying modular arithmetic tasks involving permutation structures and identifying a novel pattern in embedding space.
Hidden Markov Models (HMMs): Prior in-context learning studies HMMs treat the transition and emission as arbitrary probability tables without internal structure, which constrains these tasks to very small state spaces (typically < 64) and requires observing all transition and emission amples (Wei et al., 2022; Xie et al. 2022] Dai et al. 2025). A PCG can be written in HMM form, but its transition and emission are deterministic algebraic operations rather than stochastic tables. This difference enables Transformers to learn the underlying update rule and generalize to unseen parameters (a, c), whereas HMM- ICL tasks require observing each transition instance.
DISCUSSION
This work uses PRNG prediction as a controlled setting to probe the pattern recognition capabilities and limitations of Transformers. Our results show that the model can learn several PRNG variants, generalize to unseen parameters (a, c), going beyond classical cracking methods that require explicit knowledge of generator parameters. At the same time, scaling to larger moduli reveals clear con- straints: successful generalization requires curriculum learning and sufficient context length, with the required context empirically scaling as ((ym). Our PCA identifies bit-level structure in the embedding space, shedding light how the model represents outputs by exploiting the symme- tries underlying the PCG algorithm. A full mechanistic account of the solution implemented by the model, and an exploration of whether Transformers can approach cryptographically secure genera- tors are important directions for future work.
ACKNOWLEDGMENTS
We thank Dayal Singh Kalra, Tianyu He, and Darshil Doshi for their valuable discussions and feed- back and for collaborations related prior work. This work is supported by NSF DMR-2345644 and by the Simons Collaboration on Physics of Learning and Neural Computation, which is a grant from the Simons Foundation Maryland High Performance Computing Cluster for providing the computational resources used in this study.
POL-00012574.099 We acknowledge the University of
10

---

Published as a conference paper at ICLR 2026
REPRODUCIBILITY STATEMENT
All model architectures, training hyperparameters and data generation procedures are full de- scribed in Appendix B
We release implementation
learn pog
REFERENCES
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th Annual International Conference on Machine Learning, ICML '09, pp. 41 41-48, New York, NY, USA. 2009. Association for Computing Machinery. ISBN
9781605585161. doi: 10.1145//15333441153339.
URL https:://ei.orgg// 1145/
1553374 .10144155333 1553380
Charles Bouillaguet, Florette Martinez, and Julia Sauvage. Practical seed-recovery for the peg pseudo-random number generator. JACR Transactions on Symmetric Cryptology, 2020(3): 175-196, Sep. 2020. doi: 1551544/0ooc.2220..1.71115-111 org hog/index.co php
URL https: hatps:://oscc.acc.
8700
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners, 2020. URL
https://arx org/ abs 2005. 14165
François Charton and Julia Kempe. Emergent properties with repeated examples, 2024. URL
https://arxiie http:/iv.or/////////// /2000/2210.0 07041
Yijia Dai, Zhaolin Gao, Yahya Sattar, Sarah Dean, and Jennifer J. Sun. Pre-trained large language models learn hidden markov models in-context, 2025. URL https://arxiv: www. abs/
07298
Darshil Doshi, Aritra Das, Tianyu He, and Andrey Gromov. To grok or not to grok: Dis- entangling generalization and memorization corrupted algorithmic datasets, 2024. URL
wttp://.wrrgab/////1000 http:s//arxiv.orrr/////00111111 13061
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszko- reit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale, 2021. URL http::://a......r///aaaa. 2010.000000 11929
Shivam Garg, Dimitris Tsipras, Percy Liang, and Gregory Valiant. What can transformers learn in-context? a case study of simple function classes, 2023. URL
2208. 2208.01066 01066]
Andrey Gromov.
Grokking modular arithmetic, 2023. URL. htttps://arxiv.org/
2301. 02679
Albert Gu and Tri Dao. Mamba: Linear time sequence modeling with selective state spaces, 2024.
URL https:://// / /aaxxvv..v....///////aaa//aaaav/ org/ abs /2112. 00252
Tianyu He, Darshil Doshi, Aritra Das, and Andrey Gromov. Learning to grok: Emergence of in-context learning and skill composition in modular arithmetic tasks. In A. Globerson, I. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang (eds.), Advances in Neural Information Processing Systems, volume 37, pp. 13273. Curran Associates, Inc., paper files/paper/200 /222/
2024. URL httpps://ppoeeeeengg.g. www.:p/gw........o........ ELL217160225222001d1300222211113 otw.a//--eeaaa--apaaee---eeeeeee Caw.re-CCneeeeeeceeeeeeoeeee .df
T. E. Hull and A. R. Dobell. Random number generators.... SIAM Review, 4(3):230-2) 1962. doi: 10.1137/1004061. URL htt.://pese/occ...orr001111////0

---

Published as a conference paper at ICLR 2026
Donald E. Knuth. The art of computer programming. volume (3rd ed.): seminumerical algorithum. Addison- Addison-Wesley Longman Publishing Co., Inc., USA, 1997. ISBN 0201896842.
Pierre L'Ecuyer and Richard Simard. Testu01: A с library for empirical testing of random number generators. ACM Trans. Math. Softw., 33(4), August 2007. ISSN 0098-3500. doi: 10.1145/ 1114445226876612699
1268776.1268777.
Ziming Liu, Ouail Kitouni, Niklas Nolte, Eric J. Michaud, Max Tegmark, and Mike Williams. Towards understanding grokking: An effective theory of representation learning, 2022. URL
https://arxiv/ http://axxxxvvvvxaaaas/ org/ abs/
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization, 2019. URL https:
//arxiv.org/aa3 1711. 05101
Neel Nanda, Lawrence Chan, Tom Lieberum, Jess Smith, and Jacob Steinhardt. Progress measures for grokking via mechanistic interpretabilityy, 2023. htlltttps://axxiv..oo http:/wwww..rr////////00.00 abs/
05217
Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Dawn Drain, Deep Ganguli, Zac Hatfield-Dodds, Danny Hernandez, Scott Johnston, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, Dario Amodei, Tom Brown, Jack Clark, Jared Kaplan, Sam McCandlish, and Chris Olah. In-context learning and induction heads, 2022. URL (RLLttts://axxi/> abs / 2209.222222 11895
Melissa E. O' Neill. Peg: A family of simple fast space-efficient statistically good algorithms for ran- dom number generation. Technical Report HMC-CS-200 -004--0000 Harvey Mudd College, Clare- mont, CA, September 2014.
Alethea Power, Yuri Burda, Harri Edwards, Igor Babuschkin, and Vedant Misra. Grokking: Gener- alization beyond overfitting on small algorithmic datasets, 2022. URL WtLLhttps://axxiv.orr
abs/2201. 02177
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. OpenAI, 2019. URL https:
//cán. wwt/beeteee-laaaauaaaaaaaaa pdf Accessed: 2024-11-15.
mwdees//o//ooo.......... haals///aggageeeem stcp___ooel__eeeeee are
Ronald Rivest. Cryptography and machine learning. International Conference on the Theory and Application of Cryptology, pp. 427-439. Springer, 1991.
Eshika Saxena, Alberto Alfarano, François Charton, Zeyuan Allen-Zhu, Emily Wenger, and Kristin Lauter. Making hard problems easier with custom data distributions and loss regularization: A case study in modular arithmetic. arXiv preprint arXhv:2410.03569 2024.
Jianlin Su, Yu Lu, Shengfeng Pan, Ahmed Murtadha, Bo Wen, and Yunfeng Liu. Roformer: En hanced transformer with rotary position embedding, 2023. URL URL http:/ttt///axiii ort.abs/rg/b//////
0986419984
Tao Tao, Darshil Doshi, Dayal Singh Kalra, Tianyu He, and Maissam Barkeshli. (how) can trans- formers predict pseudo-random numbers?, 2025. URL
10390
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need, 2023. URL
org/abs/177 /oobs///1...... 03762
Colin Wei, Sang Michael Xie, and Tengyu Ma. Why do pretrained language models help in down- stream tasks? an analysis of head and prompt tuning, 2022. URL htttps://arxiv. org/
abs/ 2206 09226
Emily Wenger, Mingjie Chen, Francois Charton, and Kristin E Lauter. Salsa: Attacking lattice cryptography with transformers. Advances in Neural Information Processing Systems, 35:34981- 34994, 2022.
12

---

Published as a conference paper at ICLR 2026
Xiaoxia Wu, Ethan Dyer, and Behnam Neyshabur. When do curricula work?, 2021. URL https:
7/ arx.vv.rrg/baa/2122... 03107
Sang Michael Xie, Aditi Raghunathan, Percy Liang, and Tengyu Ma. An explanation of in-context learning as implicit bayesian inference, 2022. URL httpe://arxiivoogg/ab//////1
02080
Ziqian Zhong, Ziming Liu, Max Tegmark, and Jacob Andreas. The clock and the pizza: Two stories mechanistic explanation of neural networks, 2023. URL httts::/arxiv.cr
abs/ / 22066 17444
13

---

Published as a conference paper at ICLR 2026
A
PERMUTED CONGRUENTIAL GENERATORS
In this section we review the background of LCGs, truncated LCGs and PCGs.
A.1 HULL-DOBELL THEOREM.
For an LCG
= 0s;-1 + c (mod m),
(2)
the sequence {si) has full period if and only if the following three conditions hold:
1. and relatively prime,
2. a is divisible by all prime factors of m,
3. if m divisible by 4, then a 1 is also divisible by 4.
A.2 PERIOD OF LOW-ORDER BITS IN LCGS
Consider the LCG
Z141 (ax, + c) mod m,
(3)
with 2K coprime to m, and 1 divisible by 4, so that {ae} has full period by the Hull-Dobell theorem. Let
2t. = mod 2
(4)
denote the lowest bits of rz. Then
21+1A (azz,t + c) mod 2*
(5)
so {2 itself is LCG with modulus 2 Since is coprime to 2 and a is divisible by 4, this reduced generator achieves full period 2 Thus, the k-th lowest bit of LCG with power-of-two modulus cycles with period exactly 2*, much shorter than the full state period m.
A.3 PRNG VARIANTS.
We consider three widely used PCG permutations, each defined for 2n-bit state with eb control bits and an n-bit output. The internal state evolves as:
8 08;-1 + (mod m), m = 22n
(6)
XSLRR (Xorshift Low, Random Rotation). First apply right shift of bits and XOR with the original state, folding the high and low halves together. The low n bits of the result are then retained and rotated right by the control value to produce the output. Formally:
control bits value: v == 8; >>>>>>>>>>>> (2n cb),
(7)
state XOR shifted state: sf = s, + (s, > ni,, n--bi output: x, = rot, (s/ mod 2n)).
(8)
(9)
where 8; > n denotes right shift 8; by n bits and rot, denotes an n-bit right rotation by a.
XSH-RR (Xorshift High, Random Rotation). First apply right shift by [cn+ bits and XOR the result with the original state. The n bits immediately following the control bits are then retained and rotated right by the control value to produce the output. Formally:
control bits value: s; > (2n cb),
(10)
state XOR shifted state: sf s; (s; [(n + cb)/2]),
(11)
n-bit output: N; ((s > (n ob)) mod 2n)
(12)
14

---

Published as a conference paper at ICLR 2026
XSH 21
5
X 10
Loss
2-
20000
40000
60000
60000
100000
Training Steps
Figure Test loss curves for each generator type when the model trained on the combined dataset.
XSH-RS (Xorshift High, Random Shift). First apply a right shift by (n-ch-2" + 2 bits and XOR the result with the original state. The n-bit output window begins immediately after the control bits, but its starting position is shifted further right by the control value v, selecting a different n-bit segment of the state. Formally:
control bits value: v = 8; > (2n -cb),
(13)
state XOR shifted state: si = + (s; > [n
cb 2 + +)),
(14)
n-bit output: = (s} > (n + v)) mod 2".
(15)
We also consider truncated LCGs, where the output is formed by retaining only the top k bits of the internal state 8,, hiding the lower-order bits. This preserves the recurrence structure and full period of the LCG while exposing only partial information about the state. Formally:
(2n k) mod 2*,
(16)
B TRAINING DETAILS
Combined Dataset (Figure 2a.)). For each generator type, we select 10.22 training mul- tipliers a and increments using the Hull-Dobell theorem. One sequence per (a, c) pair is generated with its initial state Zo sampled randomly using NumPy's RNG. All sequences from all generator types are merged into a single dataset and reshuffled at the start of each epoch to randomize the sampling order. Test loss and accuracy in Figure 2[a) and Figure 9 are computed on held-out set with A a multipliers and Neeat =66 increments; in Figure 2(c), evaluation uses =128 and rhest.
We train a Transformer with depth Plaayers 4, Theads 8 attention heads, and 1 for 100k steps with batch size 512 (about 8 epochs). The learning rate is 0.0001 with weight decay 1.0, using 5000 warm up steps (linear) followed by cosine decay. Training is performed on two NVIDIA A100 GPUs and takes roughly hours.
Separate Datasets (Figure separate model on each generator type individually. Each model trained for 50k steps with batch size 512 (roughly 4 hours on two A100 GPUs). We perform grid search over learning rate and weight decay for each generator to ensure fair comparison across confi configurations.
We follow the same procedure for selecting a and but train
Truncated LCG (Figure left). We evaluate truncated LCGs with m 216 varying the number of retained bits & from 1 to 16, which determines the effective output range. Each integer is tokenized into two base-256 digits, except for special cases where smaller base performed better: for k=7 we use base-128 with one digit, and for K-9 we use base-64 because training with base-256 consistently yielded worse performance. This tokenization dramatically reduces the vocabulary size (c.g., k=16 would otherwise require 65,536 symbols) and empirically improves convergence. Because each number is split into two tokens, the context length doubles, and prediction is counted correct only when both digits are predicted correctly.
15

---

Published as a conference paper at ICLR 2026
(b) 20015
Lmv Lind
s000e
20015
1.407
30019
3000 3000 3008
Staps
Stags
20aps
Figure 10: Curriculum training with random initialization from m= to m=22 (a) Training and test loss over steps. (b) Evolution of mixing ratio (c) Last-token accuracy over time for both moduli. (d) Learning rate schedule during training.
(0)
(0) aceic
80130
1850
g
Tant Jugt
83330
2000
on in botee
5 1-001
0.00
EX0X
2000
4008
0300
2000
28322
1000
50eps
Curriculum training with pre-trained initialization from m= 8 Training and test loss over steps. (b) Evolution of mixing ratio a. (c) Last-token accuracy over time for both moduli. (d) Learning rate schedule during training.
Figure 11:
m=220 (a)
Base-256 tokenization is practical trade-off' between context length and vocabulary size. With bit- wise tokenization, an 8-bit output would expand tokens, increasing the context length by factor of 8 and, leading to roughly 64x more attention memory and compute. For each configuration, we train for 50k steps with batch size 512, taking roughly four hours two NVIDIA H100 GPUs for two-digit experiments and about two hours for one-digit experiments.
Larger Modulus (Figure 3 right, middle). For m = 218 we trained a 4-layer Transformer for 50k steps (batch size 512) with context length 512 on two NVIDIA A100 GPUs (4 hours). The curriculum began with sequences from m-216 mixed into m= at a=0.01 and decayed expo- nentially to zero over the first 40k steps. Training continued for the remaining 10k steps entirely on 18 Training sets for each modulus were generated with - 1024. Using learning rate 0.0005 and weight decay 1.0, the model achieved a test accuracy on m= of 0.9907 at position 512. Figure 10 shows the curriculum, learning rate and learning
20 trained 4-layer Transformer for 75k steps (batch size 512) with context length 640 on two NVIDIA A100 GPUs, totaling roughly 10 hours of compute. Training sets for each modulus
For
generated with n. = The model was initialized from the above checkpoint trained on m=218 for 50k steps. The curriculum began with sequences from m=218 mixed into m= with sampling possi- bility a=0.01, then exponentially decayed this proportion to zero over the first 50k steps. The final 25k steps were trained entirely m=220 Using learning rate 0.0003 and weight decay 0.1, the model achieved a test accuracy m= of 0.9697 at position 640. Figure 11 summarizes the cur- riculum experiment using pretrained initialization, transferring from m=2 to m= Figure 12 shows the same curriculum schedule but starting from random initialization.
For m 222 we trained 4-layer Transformer for 100k steps (batch size 512) with context length 1279 on two NVIDIA 1100 GPUs, totaling roughly 12 hours of compute. The model was initialized from the previously trained checkpoint on m= Training sets for each modulus were generated with n 2048. The curriculum began with sequences from m==2 m=222 and m==222 mixed at initial proportions a=0.01, 0.01, 0.98 and decayed to a=0.0, 0.0, 1.0 over the first 75k steps. The final 25k steps 0.1, the model achieved a test accuracy on m= of 0.9237 at position 1279. Figure 13 shows the currieulum and learning curves.
trained exclusively 2 22, Using learning rate 0.0005 and weight decay
16

---

Published as a conference paper at ICLR 2026
(b) 2317
(4)
Bot Lost B0000144
3"
2330
1303
1,004
3004
5oags
Shaps
Staps
Shaps
Curriculum training with random initialization from m= to m=220, (a) Training and test loss over steps. (b) Evolution of mixing ratio a. (c) Accuracy the final prediction position. (d) Learning rate schedule.
Figure 12:
(4).
(c)
(4)
Los mo 33-8570
lent
1.20
Accuret
Irdi look, angt
0.354
6.625
Last-nunter
0.0775
c0000
0.00
20:00 E0:00 M4:00 1B3U 110000
0.000
20000 40000 5000
300% 10000
1246
Scens
Stops
Figure 13: Curriculum training with pre-trained initialization from m==22 to m=222 Training and test loss over steps. (b) Evolution of mixing ratio a. (c) Last-token accuracy over time for both moduli. (d) Learning rate schedule during training.
C SCALING WITH GENERATOR MODULUS
C.1 ACCURACY THRESHOLD
In the main text, we fixed the accuracy threshold 90% to study how the required context length scales with m. Here, we extend this analysis to additional criteria: (1) performance exceeding ran- dom guessing by margin e, and (2) multiplicative threshold x random- guess accuracy. Random guessing corresponds to an accuracy of 1/ ///m for our task. As shown in Figure 14 for the additive threshold criterion (e above random guessing), the fitted exponents
0.5, while for the multi- plicative threshold criterion (7x random guessing), the exponents cluster are around 0.33, indicating slower scaling requirement under the multiplicative rule.
27
First indox acc E 1N
21
2.0
Fil: 0.35 m444)
24.
2=0.1
First Firstinden index acc
27
fit: 1.33
0=02
27.
Fit 0.81 m2
C=0.55
y=100
ftt: m.33
Modulus
Modulus
(a) First index where accuracy exceeds + 1/mm for different c.
(b) First index where accuracy exceeds 7/ mm for different y.
Figure 14: Scaling of required context length with m under alternative accuracy thresholds.
17

---

Published as a conference paper at ICLR 2026
C.2 COMPUTE SCALING
Per-sequence Inference FLOPs. Given L (sequence length), dmodel (embedding dimension). Tayer
(number of layers), and [V] (vocabulary size), the total inference FLOPs be decomposed as:
FLOPS (4 T. &
2 I,2 dmooee)) Maayer:
FLOPSMIP L d model Thayer
(MLP ratio 4),
FLOP NaaeeNorm
modeel Player
(two norms per layer),
bLOPs L dmodet [V],
Fl.OPSembed
(input embedding lookup only; memory fetch).
So the total per-sequence inference cost is: FLOPSinfer FLOPSam + FLOPPMIP + FLOP NaayerNom + FLOPS head + F-FOPSEPeee (17)
(12 L &modeal + + dd + 2 L doodd)) Mayyer dmodel VI.
(18)
Total Training FLOPs. Following the standard approximation that backward 2x forward, the total training FLOPs are:
FLOPS BatchSize TrainingSteps FLOPS
where the factor accounts for forward pass, backward pass.
Brute Force Baseline We estimate computational baseline for brute-forcing all possible combi- nations of multiplier a, increment c, and seed 8o for the XSLRR generator.
First estimate the compute required for generating estimated as: each step of the LCG recurrence requires roughly two integer operations (multiply and add), while bitwise shifts, XORs, and rotations in XSLRR are least four operations per output. Modulo reduction is assumed free for powers of two. Thus, each output costs at least six integer operations in total.
output from XSLRR recurrence be
Then, we estimate the minimum number of outputs needed to determine whether a candidate triplet (a, c, su) is correct. Using the information theory lower bound, we compare the total number of unknown bits (from (a, c, 80)) to the information conveyed per observed output, giving the smallest sample size required to uniquely identify the generator parameters. There are m/4 possible values and m/2 possible values valid under the Hull-Dobell conditions. Since there are m possible states, observing a single output from /m possible values reduces the candidate space from m to roughly /m possible states. The total unknown information seeing output is
1og 4) (m ) log2 (vm) bits.
(19)
Given that each observed output reveals log2 v m bits, the minimum number of outputs required by the information lower bound is
logg(m/4) + log (m/2) 2) + log, (v 5.
(20)
log, /m
Multiplying by the per-output operation cost and the size of search space yields the total operation baseline:
m
m
PhSute RV
x
V m
5x6,
(21)
4
2
2C 3.75mm2.. 2.5
(22)
We assume that each integer operation has the same cost one FLOP. Under this assumption,
compare our brute-force baseline to the measured inference and training costs of our Transformer models in Figure [5] The inference compute is dominated by the 12 dl de L term in Equation (18)
because our experiments L < dmocte-- As L increases, the quadratic term L dmaatel will eventually dominate, and the compute will scale proportionally with m.
18

---

2048 Published as a conference paper at ICLR 2026
Inference Compute Scaling (Per-Sequence)
1017
m- m=215,1-122 128
FLOPs per Sequence (inference)
10th
m=2"4
m- mm2"11 m322
m=2 1024
2.75m22
Inference Fit: 1.83 k
10
10
106
255
Modulus Blogo scale]
Figure 15: FLOPs scaling with modulus. Inference compute per sequence for models trained on PCGs with moduli m 224_222 (context lengths required reach 90% accuracy listed in legend), compared to the frute-force baseline (dashed line). Inference cost grows far more slowly than the brute-force bound, showing the compute efficiency of Transformer-basedd prediction relative direct state-space search.
Training Loss
Test Lass
2048
0.943
0:548
1.901
0.900
2048
1:026
0:973
1.003
0993
ne (Number of values)
nc (Number of c values)
1024
0:242
0962
0/66-
1024
1:38
Loss
512
0:678
512
0:922
256
256
1024
2048
256
512
1024
(Number values)
(Number of values)
Figure 16: Training (left) and test (right) loss as function of na (number of multipliers a) and ne (number of increments c) for XSLRR-16/8 with control bits.
D DATASET SIZE
We systematically varied the number of multipliers (n₂) and increments (n.)) evaluate training-set effects. As shown in Figure [6 performance depends only on the total scale of :n.. increasing na produces the same gains as increasing ne. Moderate values (ng n. 512 x 1024) already yield low training and test loss, with little improvement beyond this point. All models are trained for 50k steps with a batch size of 512. The number epochs ranges from about 390 for the smallest dataset fr.=n.=2500 to about 6 for the largest dataset 20448). As shown in Figure 17 when trained directly on m= without curriculum, the model shows no signs of overfitting except at the smallest setting =5.21) training and test losses remain closely matched across all (n. ne) configurations. However, unlike the smoother patterns observed for XSLRR-16/8, the heatmap here less regular, reflecting the greater training instability the larger modulus.
19

---

Published as a conference paper at ICLR 2026
Training Loss
Test Loss
4096
4096
nc (Number of c values)
nc (Number of e values)
2048
4:104
1,009
2:214
2048
4,126
2:162
3.5
3.0
1024
1024
34237
Blesd
512
512
1024
2048
4096
512
1024
2048
4096
na (Number of values)
(Number of values)
Figure 17: Training (left) and test (right) loss for XSLRR-18/9 with m=2 and control bits, as function of the number of multipliers n2 and increments fe.
1.0
1.0
Accuracy
Accuracy
0.4
0.4
Avg Trin
02-
Aug Test
0.2
512th
Train Accuracy
Test Accuracy
10000
20000
30000
40000
50000
64
125
256
512
Training Stops
Token Position
Figure 18: 1-layer, 8-head Transformer trained on XSLRR 14/7. Left: Learning curve. Right: Final performance.
E MODEL SIZE
E. SEPARATE (XSLRR)
Minimal Depth Figure 18 shows the training curve and final performance of one-layer Trans- former trained on XSLRR 14/7. The model rapidly converges and achieves 98.6% test accuracy at 512th token, showing that depth = can suffice for small-moduhn PCG variants.
Scaling In the main text reported loken-accuracy heatmaps for the 128th and 256th positions. Figure 19 complements this with earlier (64th) and later (512th) prediction positions. The results test accuracy by the 512th token, while a 6-layer model can surpass random guessing and reach 22.8% test accuracy by the 64th token. This illustrates how additional depth accelerates the emergence of useful recurrence representations at earlier positions. Figure 19 (right) plots test loss versus model size for different depth- depth-width configurations. We observe sharp decrease in loss as the number of parameters increases. followed by diminishing returns once the model exceeds roughly 40-70M parameters. At similar parameter counts, deeper models achieve much lower loss than simply adding heads. For example, shallow wide model (e.g., h8d1) has far higher loss than a moderately deep one with fewer params (e.g., h4d4).
show that even I-layer model achieves above-random(44.20
E.2 COMBINED
Figure 20 shows the learning dynamics and final test performance of a 2-layer Transformer trained on the combined dataset. TLCG converges fastest, followed by XSHRR with 2 control bits, while
20

---

Published as a conference paper at ICLR 2026
64th
512th
1.0
1.0
1004
100
5-
1.000
1100
800
Depth (d)
0.6
0.5
Depth
1.012
2.15
2077
100
TMM
111
140
0.24
1200
190
0.0
512)
1024)
Ramber Saramiiorss
(a) Test accuracy the 64th predic- tion position.
(b) Test accuracy the 512th pre-
(c) Test loss function of model size. Each point corresponds to (h Nhauds d = Mayers) heads and depth.
diction position.
Figure 19: Effect model depth/width and size on test accuracy. Left and Middle: Token accuracy heatmaps at the 64th and 512th positions. The y-axis (Depth d) indicates the number of Transformer layers Mayer. and the x-axis shows model size in terms of attention heads and embedding dimension (Wheads; dmnddl). Right: Test loss versus model size (number of parameters)
3.0
1.0
0.3-
20L-83icb-2)
0.5-
0.6
0.2
02-
25
100
125
150
25
50
75
100
125
150
04
120
256
512
Steps (K)
Steps (k)
Position Index
(a) Test loss v.s Training steps
(b) Test accuracy of the 512th to-
(c) Test Accuracy v.s Token dex
kcn V.S Training steps
Figure 20: Learning curves and final test performance of 2-layer model trained on the combined dataset
PCG variants with more control bits converge more slowly and reach higher loss. The results high- light that with limited model depth the Transformer prioritizes learning simpler generators first.
F CURRICULA
Let the target modulus be Murget- The training set contains sequences from Maaget well as from auxiliary moduli Meur, I Curriculum training is defined by a sampling distribution over these moduli. Each a; gives the probability of sampling sequence from Meur, and the probability of sampling from Maarge is (1 Or 0- ...). We vary a; over training (e.g., exponential decay to zero) to implement different curriculum schedules. As described Section [ we compared fixed- curricula with exponentially decaying-a schedules. Here, we extend this analysis by presenting results with alternative decay functions evaluate different schedules. We evaluate four eurriculum schedules-con cosine decay, exponential decay, linear decay, and step decay- the XSLRR task with target modulus m and auxiliary modulus m =2 Using a 4-layer, 6-head Transformer with dmodel 768 (batch size=256. context length=512). training begins with sampling weight 1=0 from mi and decays to zero over 100k steps following each schedule. The top row of Figure 22 shows the sampling probability over training, and the bottom reports training and test accuracy averaged over all token positions in the sequences. Across all schedules, exponential decay produced the best performance.
21

---

Published as a conference paper at ICLR 2026
1.0
10
0.0
0.2
0.0
20
40
64
128
256
512
Steps (k)
Steps (k)
Position Index
(a) Test loss v.s Training steps
(b) Test accuracy of the 512th to-
(c) Test Accuracy v.s Token In- dex
ken v.s Training steps
Figure 21: Learning curves and final test performance of a 3-layer model trained on the combined dataset
Curriculum Weight (Alchal
Curicuuuu Weiggtt (Alphw)
Curriculum Whight (Alohal
Currculum Weight (Aiphal
aeriiii ways
0.5
0.0
0.0
0.0
0.6
Ago Pi-7 rrogs
0.2
02
0.0
0.1
0.0
0
20
07
00
100
20
60
80
02
250
20
40
00
00
100
23
40
60
80
100
(a) Cosine CK
(b) Exponential
(c) Linear
(d) Step a
Accuracy Curves
Accuracy Curves
Accuracy Curvas
Accuracy Curves
0.6
Acsrnce
0.2
0.4
Accrrccy
0.1
60
200
60
B-atago
9. X-30a2
(c) Cosine Acc.
(f) Exponeeniil Acc.
(g) Linear Acc.
(h) Step Acc.
Figure 22: Comparison of curriculum schedules. Top row: probability a of sampling from the smaller-modulus dataset over training steps. Bottom row: training and test accuracy on m m and m2-2 under each schedule, averaged over all token positions in the sequences.
G PRETRAINED INITIALIZATION
To visualize how pretraining affects the evolution of token embeddings, we project the embeddings Step 0 and at the end of fine-tuning (Step 100,000) onto their first two principal components. The model is initialized from weights trained on XSL.RR (m-221); since the output vocabulary doubles at XSLRR-18/9 (m=2218) the first 256 token embeddings are transferred while the remain- ing tokens are randomly initialized. Figure 23 a) shows the PCA of the transferred embeddings at pre-trained initialization and end training, while Figure 23(b) b) shows the PCA of the randomly ini- tialized embeddings. These plots reveal how pretraining provides head start: the transferred half begins in an organized configuration and changes slightly during fine-tuning, whereas the randomly initialized half begins unstructured and gradually aligns with the learned embedding space.
22

---

Published as a conference paper at ICLR 2026
1.00
1.00
Step 0
Step
0.75
Step 100000
0.75
Step 100000
0.50
0.50
0.25
0.25
PC2
0.00
PC2
0.00
-0.25
-0.25
-0.50
-0.50
-0.75
-0.75
-1.00
-1.00
-1.0
-0.5
0.0
0.5
1.0
-1.
-0.5
0.0
0.5
1.0
PC1
PC1
(a) Pretrained initialization: embeddings begin closer their final configuration.
(b) Random initialization:: embeddings start in structured state
Figure 23: PCA of token embeddings at the start (purple) and after fine-tuning (yellow) for model trained on XSLRR-18/9 m=21s, Lines connect the same token across training steps. Pretrained initialization yields embeddings that are already organized.
H INTERPRETABILITY OF LEARNED REPRESENTATIONS
H.1 TOKEN EMBEDDINGS
H.1.1 XSLRR: TOKEN CLUSTERS
PCI and PC2: Table D presents the detailed token clusters for XSLRR-16/8, listing each cluster's canonical binary pattern, its rotationally equivalent variants, and the corresponding tokens assigned to each group.
PC3 and PC4: As shown in Figure 24 PC3 aligns with the signed imbalance between even and odd indexed bits (PCx(x) o (bo + b2 b1 + 66) (6 + by + b, + by )), whereas PC4 reflects weighted contrast across bit positions (approximately (2h) + b2 + 2hs bb) (bo + 2by + by + 207))-
PCS and PC6: In contrast, PC5 and PC6 do not exhibit clean correlations with simple linear func- tions of the bit positions(Figure22 25 Their embeddings show weak and mixed dependencies across bit indices, with no interpretable parity or positional structure analogous to PC3 and PC4. These components therefore warrant further investigation;
The first several principal components each explain a modest but non-negligible portion of the vari- ance. PC1 accounts for 5.1%, PC2 for 4.0%, PC3 for 3.2%, and PC4 for 2.4% of the embedding variance. Together the first four components explain roughly 15% of the total variance, indicating that these directions capture prominent but not exclusive axes variation in the embedding space. This is consistent with our observation that PC1-PCA align with simple bit-level statistics, while the remaining variance is distributed across many orthogonal directions needed to preserve token-level distinctions.
Larger moduli Figure 26 shows XSLRR token-embedding clusters at larger moduli (m). The same rotation-invariant structure observed m=216 persists increases, with clusters aligning to identical zero-run patterns.
H.1.2 COMBINED
Figure shows the token embeddings of model trained combined datasets, projected onto the first two principal components. Unlike models trained on XSLRR, this model develops a more general, permutation-agnostic grouping of tokens. The embeddings form two broad bands corre-
23

---

Published as a conference paper at ICLR 2026
Cluster
Pattern
Rotational Equivalent
Tokens
2 all bits are 1
11111111
255
7(() are
00000000
2(1) bit is
01111111
127.191, 223, 239, 247, 251, 253,
2/2) 2 consecutive D
00111111
63. 126, 139, 207, 231, 243, 249,
Z(3)
00011111
31, 124. 143, 199, 227, 248
Z14)
00061111
15, 30, 60, 120, 135, 195, 225, 240
715)
00000111
7, 14,4,22, 56, 112, 131, 193, 224
Z(6)
00000011
12, 24, 48, 96, 129, 192
Z(7)
00000001
8.2.4,8. 32, 128
01011111
95, 125, 175, 215, 235, 245, 250
10
2(1.1) 2 separated 0
01101111
III. 123. 183, 189, 219, 222, 237, 246
01110111
119, 187, 2,58
00101111
47, 94, 121, 151, 188, 203, 229, 242
00110111
55, 110, 115. 155, 185, 205, 220. 230
11
2(2.1) 2 consecutive 0 and I separated 0
00111011
59, 103, 118. 157, 179, 206, 217. 236
00111101
61. 79, 122. 158, 167, 211, 244
00010111
46, 113, 139. 184, 197, 226
00011011
27, 54, 99, 108. 141. 177. 19%, 216
or.2))
00011101
58, 71,
142, 163, 209, 232
00100111
ST. 78, 114, 147. 156, 201, 228
00110011
ST. 102, 155, 2014
00001011
97, 135, 194
00001101
13, 26, 52, 67, 104, 134, 161, 208
7(3.))
00010011
S8, 49, 76, 98, 137, 152, 196
00011001
25, 35, 50, 70, 100, 140, 145, 200
00000101
S. 10, 20, 40, 65, 80, 130, 160
Z(5.1) or 2(4.2) Z(4.)) 2(3.3)
00001001
9,18,33, 66, 132,
00010001
17, 68, 136
01010111
87, 17.93,113 117. 171, 174, 186, 213, 234
15
2(111.)
01011011
91. 107, 109, 173, 181, 182, 214, 218
00101013
43, 86, 89, 101, 149, 172, 178, 202
Z(2.L.)
00101101
45, 75, 90, 105, 150, 165, 180, 210
00110101
53. 17. 83, 106, 154, 166, 169, 212
00010101
21. 42, 69, 81, 84, 138, 162, 168
17
2(3,1.1) 2(2.2.1)
00100101
41,
82, 146,
164
18
Z(I.DDD)
01010101
85, 170
Table I: XSLRR- 16/8 Model Token Clusters with Rotation- Structures
PCD vs PC2
Equation: PC4
2 27K 5 1% (3tL.0 17K,4 25)77
PCA PC2
wlabo Connected pairs are bit-flip
Correlation: 0,0515 Connected pairs bit-flip
0.4
0.2
Payse Plysellicccm Couet
0.0
-8.2
-0.2
0.4
0.6
PC2
(a) PC3 vs.
PC2
(b) PC4 vs. PC2
Figure 24: PC3 and PC4 principal component structure. Connected points denote bit-flip pairs.
sponding to even and odd tokens. Along PC2, tokens are roughly ordered from top to bottom by increasing numbers of 1-bits.
H.2 ATTENTION PATTERN
To analyze how attention spans evolve across the network, Figure 28 shows the distribution of token distances for the top-8 8 most-attended keys per query, averaged over all positions and heads in each layer (Distances of q k 0 are excluded because self-attention peaks there and would dominate
24

---

Published as a conference paper at ICLR 2026
PC5 vo PC2 (colored by signed bit-coune)
PC6 vs PC2 [calored by signed bittcoount)
bitso
Correlation: -0.0537 Connected pairs are bit-flips
Correlation: -0.0041 |Connected pairs are bit--fips
Sqgnc Could
de Couet)
-1.2
-04
1.4
PC2
PC2
(a) PCS vs. PC2
(b) PC6 vs. PC2
Figure 25: PCS and PC6 principal components. Connected points denote bit-flip pairs.
Embedding Clustars (K-20, Silhouette
Embedding
(K=24, Silhouette Score=0.7800
0.4
8
4
5
-1
12
34
NC2 (0.085)
11
(0.065)
14
0.0
17
15
-0.2
34
16
-0.15
-0.2
-0.1
0.0
0.4
0.5
(0.082)
(0.093)
(a) XSLRR-18/9 Model Token Clusters
(b) XSLRR-20/10 Model Token Clusters.
Figure 26: PCA analysis of token embeddings. The same rotation-invarian grouping structure persists across moduli, with clusters consistently aligned to zero-run patterns.
the scale). In the first layer, attention is dominated by long-range periodic connections, with strong peaks at powers two (64, 128, 256), revealing that the model has discovered the underlying bit- periodicity of the generators. By the later layers, attention shifts toward shorter token distances, indicating that prediction increasingly relies on local context once the global recurrence has been inferred.
H.3 HEAD SPECIALIZATION ABLATION
To test whether individual attention heads specialize on particular aspects of the prediction task, we performed single-head ablation study. We zeroed out the V slice of each specified head, effectively removing that head's contribution while leaving the rest of the network unchanged. We evaluated every head every layer and measured the resulting accuracy drop at the 512-th token relative to the unablated baseline. As shown in Figure 29 head specialization emerges clearly in the last three layers: for example, at the last layer, Heads 0 and minimally affects XSLRR but substantially reduces accuracy truncated LCG, whereas Heads 3 and 5 strongly affect XSLRR but not truncated LCG. These results indicate that late-layer attention heads develop task-specific roles, with some focusing full-state PCGss and others adapting truncated outputs.
25

---

Published as a conference paper at ICLR 2026
Token Embedding Clusters (PC1 vs PC2)
(K=12. Silhouette Score=0.
[
PC2 (0.039)
0.1
More
Bits
-0.1
-0.2
Odd
Even
0.20-0..150.11000005
0.00 0.05
0.10
0.15
0.20
PC1 (0.087)
Figure 27: When trained on combined datasets, the model develops more general grouping of kens. The visualization shows token embeddings projected onto the first two principal components.
13-2
Ga/d 50-2
10-23
Tstn disance Ie-
Toben distance
Talan ciitance HE-41
Tekon distance
(a) Layer
(b) Layer
(c) Layer
(d) Layer
Figure 28: Token-distance distribution of the top-8 attended keys at each Transformer layer for model trained on the combined dataset.
I USE OF LARGE LANGUAGE MODELS
Portions of the text were refined with the assistance of Large Language Models to improve grammar.
26

---

Published as a conference paper at ICLR 2026
Layer Inde
(a) XSLRR PCG at position 512.
(b) Truncated LCG at position 512. (c) XSHRR PCG at position 512.
Figure 29; Single-head ablation. Accuracy drop at the 512th token when zeroing the V-slice of each attention head. Darker colors indicate larger decrease in accuracy relative to the baseline. The last three layers exhibit stronger head specialization, with some heads (e.g., Head 6) affecting truncated LCG but not XSLRR, and others (e.g., Heads and 5) affecting XSLRR but not truncated LCG.
27


Reviews:
[{"review_id": "SAoBn1NdpJ", "reviewer": "Reviewer_yPnh", "summary": "This paper scrutinizes a problem in learning PCG-generated integral sequences in-context and auto-regressively with Transformers, where PCG stands for Permuted Congruential Generators, a class of PRNGs. Empirically, a scaling law for the number of initial elements required to achieve at least 90% accuracy for unseen parameters ($a$ and $c$) is observed/proposed as ~$0.5\\times m^{0.5}$. Moreover, this work offers a wide range of analyses about training methods (e.g., curriculum learning, data mixing) and model representations (e.g., PC analyses of token embeddings and similarity analyses of intermediate features).", "questions": "1. Why does the observed separation between the learned token embedding vectors really help the model to achieve a near-perfect in-context learning? Yes, I agree that the analysis itself is quite intriguing and visually satisfying, and it gives us some hint about why pre-training enhances the training efficiency for large moduli $m$. However, I don’t think it is a complete analysis of the mechanism of model predictions. One possible way to complete the analysis is to design a pseudo-code that is possibly learned by the model to make correct auto-regressive predictions of PCG-generated sequences.\n1. I hope a future revision of the paper will contain some more in-depth implications of predicting pseudo-random numbers with a deep neural network.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 1, "strengths": "1. The paper is well written. The problem setting and experimental results are clearly presented.\n2. I find most of the findings of the paper very interesting (especially the benefits of curriculum learning with the help of a smaller modulus, and the principal component analyses of embedding vectors). Even though the problem scale (e.g., number of bits required to represent the problem) studied here is quite smaller than the practically used PCGs, I believe it will be a stimulating example for many researchers who are interested in the (in)capability of a Transformer model and its learning dynamics. Indeed, it projects several immediate future works. Can we mathematically prove that/why/how a Transformer learn PCG-generated sequences (or, generalized modular arithmetics in general) in-context with a gradient-based optimizer? How far can we get with constant-size models? How about logarithmically-scaled models?", "weaknesses": "1. The observation that transformers can learn PCG-generated sequences auto-regressively may not be a very surprising finding. In fact, the studied problem is not that random since its scale is too small to pass a collection of empirical randomness tests (e.g., BigCrush). Hence, the problem possesses its own auto-regressive nature by its definition, which can be effectively solved with Transformers up to some extent.\n2. Indeed, there has already been a huge literature on in-context learning with Transformers in solving problems with a structure of a hidden Markov model (HMM) [1--6]. However, although the PCG seems to be a special instance of HMM, I cannot find a discussion about any of these previous works.\n3. While being interesting, the principal component analysis seems erroneous and incomplete; I am particularly suspicious about the ‘clustering’ of the embedding vectors. Do they really cluster together? Aren’t they just getting close because of the projection onto a two-dimensional subspace? Since the token embedding matrix is also the weight matrix of the final linear readout (due to weight sharing of GPT-based models), I don’t think the model is learning a “rotationally invariant” features; they must be distinguishable, but the separation between “rotationally invariant” tokens (in binary representation) is just happening in some other subspace(s) orthogonal to the PC1 and PC2. Being a fully empirical work, I believe the paper must provide a complete analysis of the embedding vectors, discovering on which subspace a particular feature of token embedding vectors is getting separated (e.g., PC1 separates tokens based on the number of zero-bits, PC2 separates tokens based on the number of zero-runs, PC3 separates …).\n\n---\n\nReferences:\n\n[1] Wei et al., Why Do Pretrained Language Models Help in Downstream Tasks? An Analysis of Head and Prompt Tuning. NeurIPS 2021.  \n\n[2] Xie et al., An Explanation of In-context Learning as Implicit Bayesian Inference. ICLR 2022.  \n\n[3] Hu et al., On Limitation of Transformer for Learning HMMs. arXiv preprint 2024.  \n\n[4] Zhou et al., Transformers learn variable-order Markov chains in-context. arXiv preprint 2024.  \n\n[5] Dai et al., Pre-trained Large Language Models Learn Hidden Markov Models In-context. NeurIPS 2025.  \n\n[6] Hao et al., Transformers as Multi-task Learners: Decoupling Features in Hidden Markov Models. arXiv preprint 2025.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XwGnxBZTZd", "reviewer": "Reviewer_i5nj", "summary": "The paper investigates whether Transformer models can perform in-context next-state prediction on sequences generated by pseudorandom congruential generators (PCGs).\nThe authors consider four PCG variants (TLCG, XSLRR, XSHRR, XSHRS) and train models both on per-generator datasets and on a combined dataset. \nThe results show that Transformers not only learn each generator’s rule but also can infer which generator produced a given sequence. \nThe authors further study how performance scales with the modulus $m$, dataset size, and model size.\nThe experimental results find that curriculum learning with data-mixing strategies is effective for large moduli. \nFinally, a PCA of the embedding matrix suggests the model leverages structural statistics such as the number of zeros and zero-run patterns to support in-context reasoning.", "questions": "**Q1.**\nIn lines 263-264, the authors claim that a 1-layer model suffices to solve small-modulus PCG instances.\nHowever, to my knowledge, prior ICL work on Markov-chain-style tasks suggests that at least two layers are required to implement induction heads and achieve ICL [3].\nAlthough PCG is not a Markov chain, it is more complex.\nCould you clarify how PCG can be solved with a shallower model than Markov-chain-style tasks?\n\n**Q2.**\nI personally find the PCA analysis interesting: the first axis aligns with the total number of zero bits, and the second with the number of zero runs.\nHave you examined additional principal components (e.g., 3-component)?\nIf so, does the third component also align with interpretable statistics?\n\n---\n\n[3] Ekbote, Chanakya, et al. \"What One Cannot, Two Can: Two-Layer Transformers Provably Represent Induction Heads on Any-Order Markov Chains.\" *arXiv preprint arXiv:2508.07208* (2025).", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "**S1.** The paper is clearly written, and the figures are well-designed.\n\n**S2.**  The authors conduct extensive experiments to support the paper’s claims, and the results convincingly substantiate those claims.", "weaknesses": "**W1.**\nThe PCG setup, where a hidden state $s_i$ evolves and the observation $x_i$ is produced via a deterministic function $f$, is conceptually close to HMMs and finite-state automata.\nTo my knowledge, there is already substantial work probing Transformers’ capability on learning HMM/automata-like processes [1,2].\nI think the paper should clarify what is genuinely new here versus what might already follow from known results on those finite-state structures.\n\n**W2.**\nThe PCA-based analysis suggesting the model learns and exploits a “zero-run” pattern is intriguing, but it does not provide a full understanding of how Transformers actually perform in-context learning on PCG instances.\nGiven that PCG sequences are challenging to analyze, a complete theory may be out of scope; however, I feel the analysis remains largely phenomenological.\nAs a result, the contribution read as “pick some convenient task, train a Transformer under various settings, and show that it exhibits in-context learning,” rather than explaining the underlying mechanism.\n\n---\n[1] Hu, Jiachen, Qinghua Liu, and Chi Jin. \"On limitation of transformer for learning hmms.\" arXiv preprint arXiv:2406.04089 (2024).\n\n[2] Liu, Bingbin, et al. \"Transformers learn shortcuts to automata.\" arXiv preprint arXiv:2210.10749 (2022).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Cnh4B4ylEX", "reviewer": "Reviewer_2asJ", "summary": "*Disclosure: LLM is used for an initial draft of this review, but significant human effort is made to reflect the human reviewer's understanding and opinion of the paper.*\n\nThis paper investigates the ability of Transformer models to learn and predict sequences from Permuted Congruential Generators (PCGs), a family of pseudo-random number generators (PRNGs) more complex than standard Linear Congruential Generators (LCGs) due to their use of bitwise permutations (shifts, XORs, rotations).\n\nThe authors demonstrate several key findings:\n1.  **In-Context Learning:** Transformers can successfully perform in-context prediction of sequences from various PCG variants, generalizing to unseen generator parameters (a, c). This capability holds even when the output is severely truncated (e.g., to a single bit). A single model trained on a combined dataset of different PCG variants can also learn to identify and predict sequences from all of them.\n2.  **Training Strategy:** Training models on large moduli directly is infeasible due to prolonged stagnation. The authors show that mixing in data from smaller moduli or using a pretrained model are important for overcoming this stagnation and successfully training large-modulus models.\n3.  **Scaling Law:** The authors identify an empirical scaling law: the number of in-context sequence elements L required for near-perfect prediction grows with the modulus m as $L \\propto \\sqrt{m}$. This is a steeper requirement than for LCGs ($L \\propto m^{0.25}$).\n4.  **Interpretability:** By analyzing the token embedding layer, the paper reveals that the model spontaneously organizes representations based on rotation-invariant features (specifically, the number and arrangement of contiguous zero-runs in the tokens' binary form). This learned structure explains why representations transfer effectively from smaller to larger moduli.", "questions": "- I would like to see a power law fit on the dataset size. Is the dataset size (# of sequences to be seen) needed linear w.r.p. to m?\n\n- Is the base-64/128/256 training empirically better than bit-wise tokenization? Would be good if we have some justifications.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- PCGs are practically relevant and designed to be statistically hard to predict. This work effectively establishes a new, ML-based approach to cryptanalysis and could evolve into a practical benchmark or tool for evaluating the security of other PRNGs. The experiments are throughout and comprehensive.\n\n- The paper provides new insights into the expressivity of transformers, demonstrating they can model surprisingly complex, non-linear bitwise operations (not just simple arithmetic). The ablations offer a concrete analysis of the importance of pre-training and curriculum learning.\n\n- The discovery of the $L \\propto \\sqrt{m}$ scaling law is intriguing, potentially related to known attacks such as Sweet32 attacks.", "weaknesses": "- The data efficiency of the proposed method is not great. It is unclear that if the accuracy mainly comes from memorizing similar patterns.\n\n- (Minor) The findings around interpretability is not particularly novel, as previous studies on grokking and probing revealed similar geometric structures. The paper will be even better with a more in-depth mechanistic interpretability analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)