(How) Can Transformers Predict Pseudo-Random Numbers?
Authors: Tao Tao
Darshil Doshi
Dayal Singh Kalra
Tianyu He
Maissam Barkeshli
Venue: ICML 2025 poster (2025)
Keywords: Interpretability
In-context learning
Grokking
Transformer
Pseudo-random number generators
Primary area: social_aspects->accountability_transparency_and_interpretability
TL;DR: We show that transformers can learn to predict sequences from Linear Congruential Generators. We identify the underlying algorithm employed by trained models, which involves estimating the modulus in-context and finding its prime factorization.

Abstract: Transformers excel at discovering patterns in sequential data, yet their fundamental limitations and learning mechanisms remain crucial topics of investigation. In this paper, we study the ability of Transformers to learn pseudo-random number sequences from linear congruential generators (LCGs), defined by the recurrence relation $x_{t+1} = a x_t + c \\;\mathrm{mod}\\; m$. We find that with sufficient architectural capacity and training data variety, Transformers can perform in-context prediction of LCG sequences with unseen moduli ($m$) and parameters ($a,c$). By analyzing the embedding layers and attention patterns, we uncover how Transformers develop algorithmic structures to learn these sequences in two scenarios of increasing complexity. First, we investigate how Transformers learn LCG sequences with unseen ($a, c$) but fixed modulus; and demonstrate successful learning up to $m = 2^{32}$. 
We find that models learn to factorize $m$ and utilize digit-wise number representations to make sequential predictions. In the second, more challenging scenario of unseen moduli, we show that Transformers can generalize to unseen moduli up to $m_{\text{test}} = 2^{16}$. In this case, the model employs a two-step strategy: first estimating the unknown modulus from the context, then utilizing prime factorizations to generate predictions. For this task, we observe a sharp transition in the accuracy at a critical depth $d= 3$. We also find that the number of in-context sequence elements needed to reach high accuracy scales sublinearly with the modulus.

(How) Can Transformers Predict Pseudo-Randon Numbers?
Tao Tao
Darshil Doshi" *1 Dayal Singh Kalra "2 Tianyu He
Maissam Barkeshli 13
(tao2021, ddoshi, dayal, tianyuh, ma haissammae @ @umde edu
Abstract
1. Introduction
Transformers excel at discovering patterns in se- quential data, yet their fundamental limitations and learning mechanisms remain crucial topics of investigation. this paper, we study the abil- ity of Transformers learn pscudo-random num- ber sequences from linear congruential genera- tors (LCGs), defined by the recurrence relation + mod We find that with sufficient architectural capacity and training data variety, Transformers can perform in-context pre- diction of LCG sequences with unseen moduli (m) and parameters (a, c). By analyzing the em- bedding layers and attention patterns, we uncover how Transformers develop algorithmic structures to learn these sequences in two scenarios of in- creasing complexity. First, we investigate how Transformers learn LCG sequences with unseen (a, c) but fixed modulus; and demonstrate suc- cessful learning up to m 232 We find that models learn factorize and utilize digit-wise number representations to make sequential predic- tions. In the second, more challenging scenario of unseen moduli, we show that Transformers can generalize to unseen moduli up to Mes = 216 In this case, the model employs a two-step strat- egy: first estimating the unknown modulus from the context, then utilizing prime factorizations generate predictions. For this task, observe a sharp transition in the accuracy at critical depth d = 3. We also find that the number of in mn-coneext sequence elements needed to reach high accuracy scales sublinearly with the modulus.
Transformer-basedd language models have proven to be ex- tremely powerful sequence generative models. With copi- ous amounts of training data and computational resources, they can identify and learn complex patterns from train- ing corpora, resulting in numerous remarkable capabilities (Vaswani et al., 2017; Dosovitskiy et al., 2021). I). Recent re- search has demonstrated that these models, when provided with sufficient context and inference compute, can acquire new patterns and capabilities without additional training through techniques such as in-context learning (Radford et al., 2019) and thain-of-thouu 2023). While these models have achieved unprecedented success, understanding what underlying patterns are learned and how they learn them remains a significant challenge. Eseudo-Random Number Generators (PRNGs) represent an interesting test case for exploring these challenges. These algorithms, which are fundamental to modern cryptography and computer science, are designed to produce outputs that pass statistical tests for randomness, but nevertheless arise from mathematical patterns that could potentially be learned by sufficiently powerful sequence models.
Te+1
reasoning (Wei et al.,
This intersection between Transformer models' pattern- learning capabilities and the structured yet obfuscated nature of PRNG outputs raises intriguing questions about both the capabilities and limitations of these models. Can Transform- ers learn to predict PRNG outputs given sufficient training data, model capacity, and context? If so, what implications does this have for our understanding of both Transformer architectures and PRNGs? Do the Transformers learn the underlying generating algorithm merely detect shortcuts and spurious patterns? What effect do model capacity, data variety, training methodologies, and context length have on the capabilities of Transformers?
"Equal contribution authors listed in pscudo-random order. 'Department of Physics, University of Maryland, College Park, USA DDepartment of Computer Science, University Maryland, College Park, USA 'Joint Quantum Institute, University of Mary- land, College Park, USA. Correspondence to: Maissam Barkeshli <maissam @ und.edu>.
This work aims to answer these questions by focusing on learning sequences obtained from linear congruential gen- erators (LCGs) using GPT-style autoregressive Transform- ers. We demonstrate how Transformers can successfully learn LCGs with moduli up to 232 We perform in- terpretability analyses, uncovering emergent structures in qi Lithub. con/ dayal Sayallkall -kalrk/
Proceedings of the 4nnd International Conference on Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
pprpg.ppp..... sangg.git. git
We open source the code to reproduce our results: https://

---

(How) Can Transformers Predict Pscudo-Random Numbers?
the embedding layers, attention heads, and underlying algo- rithms that the Transformer uses learn the sequences. We also perform several systematic scaling analyses to under- stand the effect of architecture and sequence complexity on model performance and in-context learning ability.
is uniquely defined by the choice of m, a, e and the initial seed zi. An important quantity that determines the complex- ity of an LCG sequence is its period: 1 S Tm (a, c) S m. As we will show in the following sections, the period of a sequence plays a major role in the difficulty of prediction with Transformers. According to the Hull-Dobell Theorem (Hull & Dobell, 1962), the period Tm (a, c) = m if and only if the values of a and e satisfy the following criteria: (i) m and e are coprime, (ii) of m, (iii) evaluate (test) all our models exclusively sequences that obey the criteria of this theorem.
1.1. Related works
Our study on the learnability of PRNGs for Transformers touches on several modern and classic topics.
1 is divisible by all prime factors 1 is divisible by 4 if m is divisible by 4. We
Interpretability and Modular Arithmetic: A growing body of work examines the circuits, algorithms and struc- tures learned by Transformers (Sharkey et al., 2025; Olsson et al., 2022; Ahn et al., 2023; von Oswald et al., 2023; Akyürek et al., 2023; Hendel et al., 2023; Liu et al., 2024). A notably fruitful setting involves simple modular arithmetic problems (Power et al., 2022; Gromov, 2023; Nanda et al., 2023; Zhong et al., 2023; Doshi et al., b024a;b; He et al., 2024). Our work adds to this by reverse-enginee engine-nnggni the underlying algorithms and uncovering emergent structures in learning pseudo-random number
LCGs are widely utilized for their speed and simplicity, often forming the core of more complex PRNGs like PCG- 64, which is used in NumPy. LCGs perform poorly at small bit sizes but improve rapidly with larger state sizes. For instance, an LCG with 88 bits of state can pass the stringent BigCrush randomness test (O' Neill, 2014).
sequences sequences.
2. Training Setup
There is a classic duality between cryp- lography and learning theory (Rivest, 1991), and cracking PRNGs is an important topic in cryptography. Nevertheless, deep learning-based attacks have received limited attention in the post-Transformer era. Amigo et al. (2021) demon- strated that a fully-connected neural network can predict the outputs of modified LCG with fixed (irrational) parame- ters (a, C, m) (1, n, 1). In comparison, we systematically analyze the harder cases of unseen parameters using Trans- formers, reverse-engineer the learned algorithms, and study effects of scale and complexity.
Cracking PRNGs:
We train decoder-only Transformers to autoregressively pre- dict the next number in LCG sequences. This means it takes input an LCG sequence (zo,... LL1) outputs sequence (Yo. ... -r,-1), and trained so y matches Z++1-
To predict an unknown LCG sequence, the Transformer needs to infer m, a, and c in-context. We test the model's generalization ability in two distinct paradigms of increasing difficulty: FM: The model is trained and tested on sequences with a fixed modulus m. UM: Model is trained on varying moduli, and tested on unseen moduli Muest = {meest. J. We highlight the key details of our experimental setups here and provide an extensive discussion in Appendix A.
Formal Grammars: LCG can also be viewed as a for- mal language (Type-3 regular grammar) lying within the Chomsky hierarchy (Chomsky, 1956). Formal languages provide an interesting setting for synthetic datasets that can be used to understand the properties of neural networks in controlled settings (Delétang et al., 2023; Allen-Zhu & Li, 2024; Cagnetta et al., 2024; Cagnetta & Wyart, 2024).
2.1. Dataset Generation and Evaluation
The settings below are used in Sections 3 and 4. In order to achieve better performance, we used a larger and higher- quality dataset in Section 5, which we detail later.
Fixed Modulus (FM): Given a modulus m, we apply the Hull-Dobell Theorem to determine the possible values of (a, c) that maximize the period. We then randomly select 64 values of and to generate the test dataset. To generate the training dataset, we exlude these test choices of (a, c) and uniformly sample N = 100, 000 LCG sequences of length L ++1 1 (where L is the context length), with na values of multipliers and n., values of increments. For each set of parameters (a, c), we sample an LCG sequence with a randomly selected initial seed 2g- Note that the training dataset includes sequences with varying periods, while the test data only contains sequences that maximize the period.
Chaotic time-series: A major application of neural net- works is predicting time-series for chaotic dynamics, such as weather prediction (Lam et al., 2023) and financial mod- eling. PRNGs provide an analog of such dynamics in the discrete setting.
1.2. Linear Congruential Generators
LCG is a simple PRNG that generates the next number in a sequence (No,
...) according to the map:
1t+1 = (az, + c) mod m, where > 0 is the modulus, 0 < m is the multiplier and 0 S c < m is referred to as the increment. An LCG map
(1)
Generalization to Unseen Modulus (UM): In this more
2

---

(How) Can Transformers Predict Pscudo-Randor Numbers?
challenging paradigm, we first select a set of test moduli MISI = {Mes)) that would be reserved exclusively for eval- uation. For each test modulus Mite E Mest, we determine the values of (a. c) that maximize the period. We then ran- domly select 64 values of a and c each to generate the test dataset. These 64 (a, c) pairs are not considered while generating the training dataset.
60
Grodde
128 Fheadh
1.8
2.77
0.03
00013
0.916
0.P14
3356
1.370
0.6
3737
133
1000
0003
0012
0538
0.500
0.50
137
115
2.500
1:
5.191
0043
0.022
0.023
00004
0.204
0.304
64.578
0.1020
(16.
0.2
PPoae Gessel
For the training dataset generation, we sample 7mm mod- ulus values from the range Mmull, with Mmaa [1.2 max while excluding all the values in Mest For each modulus value m, we uniformly select na multi- pliers and ne increments, excluding the ones reserved for testing. For each triplet (a, c, m), we generate a sequence of length +.+1 using a randomly selected initial seed No. This results in a total of N- 1mm X nh X ne training sequences.
Figure 1. Accuracy of predicting the last number (token) in the sequence: phase diagrams w.r.t. various depths and Rheads values. (a) Must 2048, constant width: dmodel 768. (b) Must
1096, width scaled proportionally: dmodel = 128 x Theads-
setting but not in the UM setting.
We found that 7.m Z Mas/4 /4 yields good generalization performance. Based on this relationship and our target total number of training examples N, we sample ne = The /are4 values of multipliers and increments. Un- less explicitly specified, we use this setting as the default configuration for all experiments.
In Figure I we show how the performance varies with model depth and the number of attention heads. In Figure ((a) we keep the embedding dimension fixed to dmodel = 768, whereas in Figure 1(b) we scale it proportionally to the num- ber of heads (dmoodel = 128 Theads.). In both cases, we find that minimum of three layers are required for effective generalization, with performance degrading sharply below this threshold. Further analysis across multiple Miest values (see Appendix D) confirms that this minimal depth require- ment is universal. We also observe that additional attention heads improve model performance, with substantial gain occurring when increasing from one to two heads.
In both paradigms, test accuracy is averaged over all (a, c) test pairs and multiple initial seeds zo per pair. Accuracies are tracked at all sequence positions S t t L.
2.2. Tokenization, Architecture, and Optimizer
In Sections 3 and 4, each number is tokenized as unique token, using a dictionary of size m (FM) or mmax (UM). We employ GPT-style Transformers with learnable positional embeddings and weight tying (Press& & Wolf, 2017).
Several prior studies have also observed sharp changes in model capabilities as function of model depth. This in- cludes induction head formation (Olsson et al., 2022), in- context learning of modular addition (He et al., 2024) and various in-context generalization tasks (Chen & Zou, 2024). In general it is unclear to what extent these sharp depth- dependences are due to jumps in expressivity trainability.
When we scale up to larger moduli in Section 5, restrict the dictionary size to b by tokenizing each number in the se- quence in base-b (e.g. b = 3,,35) This results in [log, m] tokens for each number. We also apply (modified) abacus positional embeddings (McLeish et al., 2024).
The UM task shows strong sensitivity to hyperparameters. As we increase mhst while keeping the model size fixed, we observe two key phenomena: the optimal learning rate (n) and weight decay strength (A) shift significantly, and simultaneously, the range of hyperparameter resulting in effective performance narrows (see Appendix A.5).
The model architecture is characterized by the number of blocks (depth), embedding dimension (dmodel). number of attention heads (Nheads). Models are trained with Adam W (Loshchilov & Hutter, 2019) and CrossEntropy loss.
We then carefully examine the training dynamics in both FM and UM settings (Figure 2). We categorize the train- ing sequences into two groups: i) sequences with periods shorter than the context length, which can be solved through simple copying, and ii) sequences with periods longer than the context length, which require the model deduce un- derlying rules for prediction. Our analysis reveals that the model first acquires copying ability for group i) in the early stages of training, and later "groks" the solution for group ii) (Power et al., 2022). Notably, the model's ability to gen- cralize to test modulus miest emerges simultancously with this grokking phenomenon. These results demonstrate that
3. Training Results
We begin by investigating the minimal model that can solve the two tasks in consideration. Surprisingly, we found that Transformers only require one layer and one attention head to learn the FM task, shown in Figure 2 (a) (for further results, see Appendix B). Conversely, the UM task requires a stronger architecture and careful hyperparameter tuning. Appendix C shows that model performance depends on the modulus, with prime moduli being challenging in the FM
3

---

(How) Can Transformers Predict Rxcudo-Randoo Numbers?
lb)
[r=
Foxed Modiluss
Unseen Modulus
1962:
1
0
O
1
O
1.0
Trah (peried: s 2540
1.0
Train (pertcc a 2351
Ir-21 21
Last number accurcy
0.6
0.8
Train
Troi tscriod x 236)
lea:
0.6
0.8
Testt
Trin
Train (perlod 254)
1593:
038
624
0
0
0
1
1
1
0
0
0
1962:
62ft
0
0
0.4
1964t
1954:
Last
0.2
997:
perod=2
period-21
constant
periode2n
period=22 2
per period:2!
0.0
10
10
10'
10
dight
2dd dlwestdight
Figure 2. Training/test accuracy curves for predicting last number
Iosse dight
(token). (a) FM: (m = 2048, depth = 1, Theads = 1, dmodel = 768) Test accuracy "groks" when training accuracy reaches near- 100%. (b) UM: (1744 depth = 6, Whoads 4, dmoddl = 768) Test accuracy "groks" simultaneously with training accuracy on sequences with period longer than context length (Tm > L 256), indicating delayed discovery of underlying rules.
Figure 3. Bit-wise periods in an example LCG sequence generated with m 2048, a 293, e 1033, which follows the Hull- Dobell theorem. In binary representation w-th lowest bit has period of 2" for w E (1.... 11). Writing new sequence by skipping every 2nd step (r 2) reduces the periods of all the bits by a factor of 2, rendering the lowest bit constant. r = 2* reduces bit-wise periods by factor of 2 with last lo digits constant.
the model develops different capabilities at distinct stages of training, with generalization ability emerging only after the model learns the underlying rules through solving the more challenging sequences. In Appendix E, we present an ablation study where models are trained exclusively on either short-period or long-perion sequences. Our findings indicate that training exclusively on long-period sequences enables model generalization.
digit. To understand this, consider the r-step iteration of Equation (I):
4. Interpreting How Transformers Predict PRNGs
Ietr = a'xx + Σ
aa Ca-le mod m.
(3)
In this new sequence wherein we skip steps, the period of each digit Ow- reduces from 2 to 2 /ed((r 2*). Con- sequently, the higher digits become relatively simpler to predict due to reduced periods while some lower digits be- come trivial to predict due to being constant along this new sequence. We demonstrate this for m 2048 in Figure (top panel). The digit-wise periods in the new sequence with = 2 are reduced by a factor of 2, while the last digit is simply constant. Higher values of r = 2 will lead to even further simplifications of the sequence. Transformers can simplify the task of predicting LCG sequences by utilizing r-step iterations from the in-context examples with longer contexts leading to larger values of r. Consequently, the per-digit and overall accuracies improve substantially with context (see Figure 4).
In this section, we uncover the underlying algorithms im- plemented by the models for both FM and UM cases. While certain details of the algorithms differ in the two cases, they share common properties originating from the under- lying LCG structure. We first discuss properties of LCG se- quences that will be useful in interpreting model behaviors.
4.1. Residual Number System Representations
Consider an LCG sequence with modulus m 2048 2 Each number in this sequence can be represented as an 11-digit binary number:
mod 2 = an 2 +a 2 +.... ......... + an 200
where {ao,.............. ... } are the binary-valued digits (bits).
A useful property of LCGs with modulus m = 2 is that each digit in the binary representation has a fixed period along the sequence. As shown Figure 3, for a sequence of period Tm = m = 2 the th lowest digit has a period of 2d (Knuth, 1997). Thus, lower (higher) digits have smaller (larger) periods along LCG sequences. (See Appendix F. for a detailed derivation.) We will see later that trained Transformers have emergent structures that find these bi- nary representations and utilize them to make systematic predictions from the context. Notably, the per-digit period plays and important role in the prediction accuracy of that
While moduli of the form m = 2 lead Transformers to find binary representations, similar simplifications in composite moduli require more general representations of the Residual Number System (RNS) (Garner, 1959). RNS represents numbers by their values modulo pairwise co- prime factorizations of m. Specifically, consider sequences with a composite modulus m. which has prime factoriza- tion m 2i ph" ... We ...p... In this case, we can uniquely represent each number (x mod m) as the tuple of resid- uals (a mod pt . modp ...., ........ x mod ")"). Analogous to Equation (2), we can further decompose each residual,
4

---

(How) Can Transformers Predict Renudo-Random Numbers?
Transformer model as a function of token position along the context, shown in Figure 4 (a). (Recall that in this section token corresponds to an integer of the LCG sequence), The accuracy exhibits a ladder-like structure, with each jump oc- curring exactly at the 2 token position. These successive transitions can be explained using binary representations and r-step recurrence (Equation (3)). Specifically, to predict the token at position - 2*, the model can look back in the context position - 2* and implement iteration. This allows the model to (i) copy the lowest k bits since they remain unchanged; and (ii) simplify the higher bits, since their periods get reduced by factor 2 We note that the accuracy trend remains unchanged across different choices of a and Tg (see Figure 21).
x mod pj" 03.0P3 + 0z P3 + ................................ + 03,0;=1
(4)
where jj E 10, 10.1,...,PP ......P; 1} are base-p, digits. We re- fer to {ag.w] as the "RNS representation" in the remainder of the text. When Tm = m, each digit j',w has a period of p (derivation in Appendix F.2). The r step iteration Equation (3) reduces the period of each digit aj,w from p to p// god(r. This results in simplification of the pre- diction task whenever p p P2 Py
-testep
Rn We will see that
identifying the RNS representations is key simplification that the Transformer discovers in learning LCG sequences.
4.2. Interpretability: Fixed Modulus
Next, in Figure 4(b), we compute the per-digit accuracy by converting both model predictions and ground truth labels to their binary representations according to Equation (2). We observe that the model can predict more digits correctly with more context, with sharp transitions occurring at 2*-th -th token positions. This is a direct result of the sequences becoming increasingly more simplified as the model can look farther back in the context and utilize (r 2* >-step iterations. Since these simplifications occur in the form of digit-wise periods, Figure 4(b) serves direct evidence that the model is internally developing and utilizing binary representations. The sequential learning of digits also explains the ladder- like structure of the accuracy in Figure 4(a). We find that the overall average accuracy (Figure 4(a)) multiplicatively depends on the per-digit accuracies (Figure 4(b)) (empirical proof in Figure 22(b))
Qualitative Algorithm (fixed modulus):
i. Find RNS representations of inputs from the learned prime factorization of m
ii. Look back r = , steps in the context and copy the lowest & digits, for different prime factors (pj) of m
iii. Using these r-step iterations, predict the higher digits of the simplified sequence
We now discuss the algorithm implemented by Transform- ers trained on LCG with a fixed modulus. We will show that, despite being provided integers as inputs, the model develops emergent structures that create and leverage the RNS representation of the inputs. We will focus on the setup with 1-layer, single-head Transformer trained LCG with 2048, Similar results for composite moduli (e.g. m = 7776) and different model sizes are presented in Appendix G. We emphasize that this algorithm works for arbitrary a, c, By for a given m.
aCCoverall (aCCaigit 1) (acCdigit (acc 11). (5)
Next, we investigate how various components of the model implement the algorithm outlined earlier this section.
(a1)
First PCA component
(b) Cosine similaity of embedding vectors
0.025
0.000
-0.0+
0.098
(a)
Sverage lest accunio
(b)
(a2)
number
10
15
512-
0.15
0a
Sd comporett
4kc+3
number
0.10
0G
bit
4k
206
0.00
4k+2
-005
0.2
-8.00
4k+1
000
256
512
24
16
32
PCA component
number (X)
poetiin
taken position
Figure 5. FM: (a- = 1589, = 629) Embedding layer. (al) 1st principal component groups the numbers mod (a2) 2nd and 3rd principal components group numbers mod 4. (b) Embedding vectors of different numbers exhibit high cosine similarity when they are spaced 2* apart, with the similarity increasing with k.
Figure 4. FM: Test accuracy for 2048, depth Thends 1, dmodel = 768, averaged over a, c, and seeds. (a) Test accuracy w.r.t. token positions. Ladder-like structure appears, with jumps occurring at 2 positions. (b) We represent numbers as an eleven-digit binary number (2048- = 2" and compute the per- digit test accuracy of model predictions.
'This holds if the per-digit accuracies are independent, which we confirm empirically.
We begin by analyzing the average accuracy of trained
5

---

(How) Can Transformers Predict Recudo-Randon Numbers?
(a)
Attention weights
(b)
post-ReLU activatione
(c)
contilbuton indiidual neurons
Projected MLP outputs:
(d)
contributions mutiple
Projected MLP
1.0
0.01
9.00
0.00
64
Callhoae value
-0.01
output valive
0.01
QuAey
120
0 0000
0.00
0.4
-..0
152
0.5-
0.0025
0.0000
0.025
0.0
0.0025
0.000
256
182
256
0.0
1000
2000
1000
2000
0.025
500
1000
1500
2000
key
target (Kogs)
Figure FM: (m = 211 a- 1589, c 629) (a) Attention weights: each query attends most strongly to the tokens 2 and 2 distance backward, for the highest possible value of ks enabling copying of lowest k bits. The other faint lines facilitate the prediction of higher bits. (b) Post-ReLLU hidden layer MLP activations at token position & = 129 (extracted using sequences with different zo) as function the target number F130 which it is supposed to predict. Each neuron gets activated only while predicting specific 1300 exhibiting sparse, periodic pattern. (c) Output of the MLP block projected onto the (un)emnediing matrix; after masking out all but a single given hidden-layer neuron. The green dot denotes the value the target number. Each neuron resolves the correct prediction up to periodic structure. (d) Output of the MLP block projected onto the (unjembedding matrix; after combining the signal from multiple neurons (i.c. gradually un- uu-masking the neurons). The per-neuron periodic patterns constructively interfere at the correct output.
Step i: We begin by conducting Principal Components Anal- ysis (PCA) of the embedding matrix, which shows how the model performs prime factorization to develop the binary representations (RNS for general m). Figure 5(al) shows the projections of all numbers x E (O.... 2047) along the first principal component of the embedding. We observe that the model groups the numbers into modulo 2 clusters along the first principal component. Similarly, the 2nd and 3rd principal components group the numbers into modulo 4 clus- ters (Figure 5(a2)). In general, we find principal directions that group the numbers into modulo 20) (see Figure 24). By clustering the numbers according to their remainder modulo different prime-pone powers, these principal directions naturally encode the digit-wise representations of the inputs. In Figure 5(b), we check the cosine similarity between the embedding vectors of different numbers. We see that the more digits two numbers share in the binary representation, the higher the cosine similarity of their embedding. This is a consequence of these numbers having similar components along principal directions corresponding to those digits. For composite moduli, we find similar clustering according to different prime factors of m (see Figures 25, 26).
the model in predicting the higher bits.
To verify that the brightestes line enables the copying of lower bits and that the second brightest line facilitates the prediction of higher bits, we performed the following two experiments. (i) For each query in the attention head, we mask out all keys except for the one at position t- 2* We then measure the performance of this ablated model, shown in Figure 20(a). We observe that the model retains the ability to copy the k lowest bits, but loses the ability to predict the higher bits. (ii) Next, we repeat the above ablation experiment while masking out all keys except the ones at positions t 2-2 and t 2* shown in Figure 20(b). This results in drastic improvement in the prediction of the higher bits compared to (i). confirming our assertions.
After the attention layer collects information about previous tokens, the MLP block processes the information to make predictions. We find that each hidden neuron (post-Rel.U) in the MLP exhibits a periodic response with a distinct period, as a function of the target prediction. Consider the MLP at token position The input the transformer at this position is 3a and the output yt, should match the next number in the sequence Ir+1. In Figure 6(b) we show the activation value of selected neurons at token position t = 129 as a function of the target 1130. for m different sequences obtained by changing the seed Ty for a given LCG sequence. We observe that only a sparse set of neurons are activated for given target 1130 and that there is a strong spiked periodic structure in the response of each neuron as a function of 2 $130, with neuron-specifie frequencies.
Step ii, ii:: In Figure 6(a) we examine the attention weights and find that to predict the number at position t, the model attends most strongly to the position t 2 for the highest possible value of k s.t. / 2 2* (i.e. = [log2 4)). This corresponds to the brightest line in Figure 6(a). Using the binary representation of the can copy the lowest lc bits and simplify the prediction of higher bits. Additionally, the second brightest line appeares at the position& t - 26-1, along with other faint lines at intermediate distances (multiples of t 2¹ for k' < h - 1). The information obtained from all these lines are utilized by
) token, the model
The subsequent fully connected layer in the MLP block ag- gregates the contributions from all the activated neurons to
MMLP block: fully connected + ReLU + fully connected.
6

---

(How) Can Transformers Predict Randoo Numbers?
make the correct prediction (McCracken et al., 2025). To visualize the contributions from an individual neuron, we mask out the contribution from all other neurons and extract the MLP output for fixed input sequence. We then project this output onto the (un)emnedding matrix, which shows us the contribution of that single neuron in making the cor- rect prediction." 3 In Figure 6(C) we show that each neuron resolves the target number Z130 up to a distinct periodic pattern. The periodic patterns from different neurons con- structively interfere at the target. In Figure 6(d), we observe that gradually adding contributions from multiple neurons resolves the correct output with increasing accuracy.
Step i: We first analyze the embedding layer. In Figure 7(a), PCA shows a semi-circular structure along the first principal component, with the second principal component separating even and odd numbers. This semi-cirele resembles the circular patterns seen in modular arithmetic tasks (Power et al., 2022; Zhong et al., 2023), but since our model is trained on multiple moduli, it cannot form a closed circle by identifying a unique 0 value. Figure 7(b) further shows that the 2nd and 3rd principal components group numbers by their remainders modulo 2 and 3. which likely reflects their prevalence prime factors in the training set.
Note with varying moduli, the model need not form a bi- nary encoding as before. Instead, we find attention heads in first layer group embedded numbers by remainders modulo different primes, each head specializing in a particular fac- tor. This specialization allows the model to construct RNS representations with various prime bases.
4.3. Interpretability: Generalization to Unseen Modulus
Qualitative Algorithm (unseen modulus):
i. Encode information about various possible prime factorizations
To investigate head specialization, we analyze afformen- tioned first-layer attention heads in Figure 8, presenting PCA results for selected heads in panels (al, bl, cl). For each, we input sequences using the corresponding mieett and randomly selected (a, e) pairs (per the Hull-Dobell Theo- rem), then isolate the output H (R) for each head by zeroing out all other heads. We perform PCA at token position i = 0 (PCA H (MI [:, 0, :1)),, then projecting each number's ' feature vector ( [sc, 4, :] onto the top two principal components and labeling each point with its corresponding x.
ii. Estimate the modulus via the largest number in context
ii.. Combine steps and ii to construct correct RNS representations, then implement steps ii and iii from the fixed modulus algorithm
Unlike the FM case, the training set for UM is generated using many different moduli m. unseen at test time. Since each modulus has its own RNS representation incompatible with other moduli, the model must implement a different, more general algorithm to solve UM tasks.
The analysis shows that each head groups numbers by their remainder modulo different prime factors, enabling the model to select suitable representations in later layers. The prominence of small primes in the top principal components likely reflects their frequency in the training data. Further- more, we believe the performance gains observed in Fig- ure with more heads can be partly attributed to the model's s improved capacity to capture additional prime factors for constructing RNS representations. More examples of spe- cialization across various (a, c, Miest To, t) are provided in Figure 27 (Appendix H.1).
We analyze how the embedding layer and attention heads of a 4-layer Transformer model help implement the above algorithm solve the UM task. The model is trained on dataset generated with Amm na = n. 128, where mmax = 2457. To avoid leakage between training and test sets, we specifically exclude the moduli Meet E {1800- = 23. ...52 52, 2048- = 211, 2352- = 33.3. 72) from the training set. Note that the choice mmaxx = [1.2- 2048] is made to
maintain consistency with the setting in Figure 1(a).
To further demonstrate that these heads directly influence the model's 's performance, we measured per-digit accuracy before and after pruning each specialized head, as shown in panels (a2, b2, c2) and (a3, b3, c3). For pruning, we replace the head's output with its mean value mean HH [+] i. :I) E R across all positions (using 10% of randomly selected training sequences), which preserves signal scale and avoids catastrophic model degradation. The results show that pruming a head responsible for particular prime factor significantly impairs performance on corresponding digits, while other digits are less affected. For instance, in panel (a3), the model's ability to compute 7 and 72 digits is lost, while base-2 and base-3 digits remain above chance. Similarly, in (b3), removing the modulo-2 head
(a) AM
(b)
12
2457
2nd PCA component
2K
3rd PCA component
8kt5
co
3
2011
5/3 631
4401 -030 -MD
sai en 501
1st PCA component
2nd PCA component
Figure? 7. UM: PCA analysis of the embedding layer.
'We read-out MLP outputs instead of network outputs to avoid distortion from the skip connection.
7

---

(How) Can Transformers Predict Aecudo-Randon Numbers?
(41) Lpper' Deadtt
(D1)
llyer tn pMpppig
(61) layer boud rng Skrt
18d9 pt 24
(a)
02
1936
0.1
quary
11
1924
000
-04
812
0.1
64
(02)
(12))
(G2)
1150
21
(c)
key
taken position
Prre bote.
2000-
numbor
1000
(53)
137
(::3)
53
97
token position
129
161
105
225
PRTAROM
Figure 9, UM: Attention head (layer I, head 6) specialized in esti- mating Mestt (a) Queries attend largest keys; (b) the head pro- duces features with the highest cosine similarity to Musi: (c) patch- ing this head with features from sequences with Mpssch 1024
141 120
23 30
Man PORA0
26 305
(same a, c) steers the model to predict numbers n < mpatch-
Figure& 8. UM: PCA analysis of attention heads specialized for dif- ferent prime factors and their impact per-digit accuracy. (al, cl) PCA of outputs from specific heads; the first two principal components group numbers by remainder modulo 14, 1, and 3, respectively. (a2, b2, c2) Test accuracy for individual digits with representations from Equation (4) for cach Miees. (a3, b3, c3) Per- digit test accuracy after pruning these heads, showing substantial performance degradation the affected digits.
indicating greedy estimation of Miest.
To further verify that this head estimates Miest for later lay- ers, we conduct a patching experiment (Zhang & Nanda, 2024), as shown in Figure 9(). We generate a new sequence with the same a, C, and xo, but with mpatch = 1024, and ex- tract H (k) patch x Lxdodel from this head. We then overwrite the output H (h) (h) in forward pass for the origi- nal sequence (Mhest 2048) with (1)) patch. The model now frequently predicts numbers smaller than mpatch. As shown in Figure 30 (Appendix H.3), patching other heads disrupts predictions but never induces a similar qualitative shift, confirming this head's unique role in estimating Miest-
erases all corresponding digit accuracy, and in (c3), pruning the modulo-3 head greatly reduces base-3 digit performance, but leaves base-2 and base-5 largely intact.
Finally, we further validate the link between head special- ization and digit-wise accuracy by pruning irrelevant heads. For Misst- = 2048, pruning heads responsible for modulo or (as in panels (al) or (cl)) yields the results in Figure 28. Interestingly, removing the modulo-3 head sometimes im- proves performance for specific token positions, while oth- ers show minimal degradation. These findings reinforce the connection between head specialization and digit-wise computation; further details can be found in Appendix H.2.
One might expect that even small error in estimating Meett would invalidate predictions, but this not necessarily the case. As shown in Section 4.2, if the correct representation is chosen, the lower bits maintain a strong periodic signal. Since the model can prepare multiple RNS representations (as demonstrated in step i), a sufficiently close estimate of Mieest allows these lower bits to guide the model toward the correct representation. Further discussion is provided in Appendix H.4 and step iii.
Step ii: The performance variations observed above suggest that the model is internally uncertain about which RNS representation use, likely due to difficulty in determining Mhest. As we discuss below, the model appears to estimate Miest greedily via in-context learning.
Step ii:: Once the necessary features are prepared, subse- quent layers implement the rest of the algorithm. As in the FM case, we observe a ladder pattern in digit-wise accuracy for lower digits at early token positions. This pattern, which demonstrates the copying bias, visible in Figure 8(b2).
In Figure 9a), using a sequence with 2g = 1, = 5, c= = 31, and Myest. = 2048, we observe a first-layer attention head that attends primarily to the largest numbers, as seen by the vertical lines in the attention weights. To analyze this further, in panel (b), we extract the output H E IR. x Exoodd from this head for the same sequence and compute its co- sine similarity with token embeddings for all x < Muest producing a Lix matrix for the heatmap. This reveals that the head's 's output consistently has the highest similar- ity with the largest numbers that has been seen in context,
More careful inspection of Figure 8(b2) shows the model copies the lowest 5 digits. Interestingly, given the estimated Mess 2033 from step ii, the model effectively reduces it to 2033/2 x 63.53. Futhermore, since the model operates on integers, it could round to 64, yielding 64 25 2048 = Miest. Thus, the model in principle, can predict higher digits accurately without the exact value of maest
8

---

(How) Can Transformers Predict Recudo-Randon Numbers?
While some algorithmic transition from lower to higher digits clearly occurs, the exact mechanism remains unclear. The sharp transition in per-digit performance at the 2 digit in Figure 8(b2) supports this argument. Nevertheless, we believe the model applies an algorithm similar to FM for higher bits, which we will elaborate on in Appendix H.5.
Nover lpw y شمم
ta
Steele Nuttiplerr
Nultiplies
125
216
215 224
200
29
5. Scaling Up the Modulus
Number index
Figure 10. FM: (a) Average test accuracy (m = 2 number of in-context sequence elements. (b) The number of in-context sequence elements required to achieve 100% test accuracy (mini- mum of runs). (See Appendix 1.3 for details)
In this section, we investigate training upon scaling up the LCG modulus, with the following modifications:
To avoid massive dictionary sizes for large m, we implement a base-b tokenization scheme. Each integer is decomposed into a sequence of base-b digits, beginning with the least significant digit; resulting in a vocabulary size of for any m (for details see Appendix I.I). Based on the discussion in Section 4.1, it is beneficial to choose b such that ged(b, m) = b.
Base-b tokenization:
Appendix 1.4. Test performance is influenced by the tok- enization base, since the tokenization base highlights the periodic structure of LCGs making it more apparent and easier for the model to leverage during training and predic- tion. To confirm this, we train a model with tokenization base 243. In Figure 11, Meest = 2 (3*) sequences scale better when the tokenization base is 256 2 (243 = 3*).
Abacus Embeddings:
We encode positional information
using variant of the Abacus embedding eMcLeish et al., 2024), as a sum of two learnable vectors. One vector en- codes the position of the integer within the sequence, while the other encodes the position of each digit within the integer (for details, see Appendix I.2).
(a)
[b]
2
2 where k is an integer in the range 16 < k < 32, we train a 2-layer model with dmodel = 1024 and a vocabulary size of 256. We select training sequences via the Hull-Dobell theorem, setting naa = nh = 1024 (See Appendix 1.3 for training details). For the test dataset, we choose 512 values of a and 64 values of e that differ from those in the training set.
Fixed Modulus:
For each modulus
number
211
Figure 11. UM: The number of in-context sequence elements needed for 60% test accuracy grows sublincarly with modulus m. depending compatibility between mn and tokenization. (a) Base-2 tokenization; (b) base-3" tokenization.
The quality of LCG largely depends on its multiplier, tra- ditionally evaluated via the spectral test (Knuth, 1997). In Figure 10(a), we test our model on both spectrally optimal Steele multipliers (Steele& & Vigna, 2021) and arbitrary mul- tipliers for m = 232. While achieving 100% test accuracy with equal in-context sequence lengths, the model performs consistently worse on Steele-generated sequences compared to those from arbitrary multipliers.
6. Conclusion
We have investigated Transformer training on LCG se- quences, focusing on fixed modulus training as well as generalization to unseen moduli. In both cases, we have uncovered the algorithm used by the model to solve these tasks and highlighted the model components that implement the steps of the algorithm. We have found that the model finds and utilizes prime factorizations of m and RNS repre- sentations of numbers to simplify the sequences and make predictions. We have provided the modified training recipe for scaling up the modulus in both FM and UM settings, and shown their scaling behaviors.
In Figure 10(b), a log-log plot reveals that the number of in- context sequence elements needed for 100% test accuracy scales sublinearly with modulus m as m², where 7 Rs 1/4.
Unseen modulus: For the UM case, we train a 6-layer Trans- former on a dataset with n.m = 32,768, na = 128, nee = 1, with 1024- < Marain < 65,536. Sequences are length 512, each integer tokenized as two bytes (context length 1023). As before, test data uses unseen Mitest and (a, c), focusing on Muest = 2*, 3* Figure 11 shows that the number of in-context sequence elements needed to reach 60% test ac- curacy scales as m (0.24 < y & 0.33). The averaged test accuracy of each number in the sequence is shown in
Limitations and future work: The results of this paper were limited to scales S 232_ It would be interesting to test our results on much larger moduli as well. We leave the exploration of PRNGs that are built upon LCGs, such as PCGs and truncated LCGs for future works. would also be interesting to make the training even more unbiased, by training on general classes of arithmetic sequences.

---

(How) Can Transformers Predict Pscudo-Random Numbers?
Acknowledgements
tasks. In Forty-first International Conference on Machine Learning, 2024. URL https: htt.tttps///peeeereiieeeeee openreview net/ forum? Perum?id=YNne -d-YYbcCcGyyX...
M.B. thanks Carl Miller for discussions on PRNGs. This work is supported by NSF PMR-2345644 (D.S.K., T.T., and M.B.), and by an NSF CAREER award DMR-2045181 (T.H. and D.D.). The authors acknowledge the University of Maryland supercomputing resources (http: /hpcc. umd. edu) made available for conducting the research re- ported in this paper.
Chomsky, N. Three models for the description of language. IRE Transactions information theory, 2(3):113- 1956.
Delétang, G., Ruoss, A., Grau-Moya, J., Genewein, T. Wenliang, L, K., Catt, E., Cundy, C., Hutter, M., Legg, S., Veness, J., and Ortega, P. A. Neural networks and the chomsky hierarchy, 2023. https:/ //rxiva..vvv/////////////////a// org/ abs 2207 00077.020 020 98.
Impact Statement
Our work advances the understanding of how neural net- works learn deterministic sequences, specifically LCGs. While this capability cannot compromise mainstream eryp- tographic systems, which use far more sophisticated tech- niques, our insights may contribute to the development of more robust cryptographic algorithms and a better under- standing of neural networks' computational capabilities.
Doshi, D., Das, A., He, T., and Gromov, A. not to grok: Disentangling generalization and memoriza- tion on corrupted algorithmic datasets. In The Twelfth International Conference on Learning Representations, 2024a. URL https: http:///pe/nevveeeeee net forrmm? id=UHjE.5v5ME7
To grok
Doshi, D., He, T., Das. A., and Gromov, A. Grokking modular polynomials, 2024b. URL https: //arxiv...vvv/// org/abs/ aalaab//440 2400. 03495.
References
Ahn, K., Cheng, X., Daneshmand, H., and Sra, S. Trans- formers learn implement preconditioned gradient de- scent for in-context learning. In Oh, A., Neumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 45614-45650. Curran Asso- ciates, Inc., 2023. URL https: openreview. net/ Fowummid=Lzinii
Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M.. Minderer, M., Heigold, G., Gelly, S., Uszkoreit, J., and Houlsby, An image is worth 16x16 words: Transformers for image recognition scale. In International Conference Learning Representations, 2021. URL https:// openreview net -eee/foooo-----oaaaTTTT
Akyürek, E., Schuurmans, D., Andreas, J., Ma, T., and Zhou, D. What learning algorithm is in-context learning? investigations with linearmodels, 2023. URL, https: //openreview net/ forum? O
Garner, H. L. The residue number system. In Papers Presented the the March 3-5, 1959, Western Joint Computer Conference, IRE-AIEE-ACM '59 (Western), pp. 146-153, New York, NY, USA, 1959. Associa- tion for Computing Machinery. ISBN 9781450378659, doi: 10.114451457883.4445577 URL ht ht /doi. 1457864.
Allen-Zhu, Z. and Li, Y. Physics of language models: Part 1, learning hierarchical language structures. 2024. URL org/ abs 2305. 13673.
Amigo, G., Dong, L., and Marks li, R. J. Forecasting pseudo random numbers using deep learning. In 2021 15th International Conference on Signal Processing and Communication Systems (ICSPCS), pp. 1-7, 2021. doi: 10.1 111119SPCS530099 2021 19666311
Gromov, A. Grokking modular arithmetic, 2023. URL 2301 02679.
https: htta/aaxvvv..gg..
He, T., Doshi, D., Das. A., and Gromov, A. Learning to grok: Emergence of in in-context learning and skill composition in modular arithmetic tasks. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL httph:ttt////c....t. id- Va=aVh9Keee 9KRZdRk.
Cagnetta, F. and Wyart, M. Towards a theory of how the structure of language is acquired by deep neural networks. arXiv preprint arXiv:2406. 240:24060000448, 00048, 2024.
htttts:://pperevvieee /pppneeeeeeeeeeeeeeeeeeeeeeeeeee net/ forum?
Cagnetta, F., Petrini, L., Tomasini, U. M., Favero, A., and Wyart, M. How deep neural networks learn compositional data: The random hierarchy model. Physical Review X, 14(3):031001, 2024.
Hendel, R., Geva, M., and Globerson, A. In-context learning creates task vectors, 2023.
Hull, T. E. and Dobell, A. R. Random number gen- erators. SIAM Review, 4(3):230-254 1962. doi: 10.1137/1004061. 1137/1004061.
Chen, X. and Zou, D. What can transformer learn with varying depth? case studies on sequence learning
URL https: http::://oooooooo /do....ooo.......////o////11111/
10

---

Sharkey, L., Chughtai, B., Batson, J., Lindsey. J., Wu, J., Bushnaq, L.,, Goldowsky-Diin N., Heimersheim, S., Ortega, A., Bloom, J., Biderman, S., Garriga-Alonso, A., Conmy, A., Nanda, N., Rumbelow, J., Wattenberg, M., Schoots, N., Miller, J., Michaud, E. J., Casper, S., Tegmark, M., Saunders, W., Bau, D., Todd, E., Geiger, A., Geva, M., Hoogland, J., Murfet, D., and McGrath, (How) Can Transformers Predict Pscudo-Randee Numbers?
Knuth, D. E. The art of computer programming, vol- ume 2 (3rd ed.): seminumerical algorithms. Addison- Wesley Longman Publishing Co., Inc., USA, 1997. ISBN 0201896842.
Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., and Sutskever, Language models are unsupervised multitask learners. 2019.
Rivest, R. L. Cryptography and machine learning. In In- ternational Conference on the Theory and Application of Cryptology, pp. 427-439. Springer, 1991.
Lam, R., Gonbblzz,,,zzzzz, A., Willson, M., Wimnsbrger, P. Fortunato, M., Alet, F,, Ravuri, S., Ewalds, T., Eaton- Rosen, Z., Hu, W., al. Learning skillful medium-range global weather forecasting. Science, (82(6677):1416 1421, 2023.
Liu, S., Ye, H., Xing, I.,, and Zou, J. In-context vectors: Making in context learning more effective and control- lable through latent space steering, 2024.
Loshchilov, I. and Hutter, F. Decoupled weight decay reg- ularization. In International Conference Learning Representations, 2019. URL wtt.:/foomniiiiggegeeeee
T. Open problems in mechanistic interpretability. 2025. URL https: aawiiv..vvvv.////ia//..../aaaivv httg//bb/2200000 16496.
Steele, G. and Vigna, S. Computationally easy, spectrally good multipliers for congruential pscudorandom number generators, 2021. URL httpt: http:::s//axxx..org/.o 1001.05304.
McCracken, G., Moisescu-Pareja, G., Letourneau, V., Pre- cup, D., and Love, J. Uncovering a universal abstract algorithm for modular addition in neural networks, 2025.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. Attention is all you need. In Proceedings of the 31 International Conference on Neural Information Processing Systems, NIPS' 17, pp. 6000-6010, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN
URL http:: /ttpps:///axiiiii www.a. wtt.:oor//bbb/////g 18266.
McLeish, S., Bansal, A., Stein, A., Jain, N., Kirchenbauer, J., Bartoldson, B. R., Kailkhura, B., Bhatele, A., Geiping, J., Schwarzschild, A., and Goldstein, Transformers can do arithmetic with the right embeddings, 2024. URL https:/ / /ttp//axvvvvv.///////eee//..eeee org/ abs/ 2405. 17399.
von Oswald, J., Niklasson, E.,, Randazzo, E., Sacramento, J., Mordvintsev, A., Zhmoginov, A., and Vladymyrov, M. Transformers learn in-context by gradient descent, 2023.
Nanda, N., Chan, L., Lieberum, T., Smith, J., and Stein- hardt, J. Progress measures for grokking via mechanistic interpretability. In The Eleventh International Confer- ence on Learning Representations, 2023. URL https: //openreview /wt.eee///et forum? id= 9XF PDdMM.....
Wei, J., Wang, X., Schuurmans, D., Bosma, M., Ichter, B., Xia, F., Chi, E., Le, Q. and Zhou, D. Chain-of- thought prompting elicits reasoning in large language models, 2023. URL https: atttps://axiv... htt///aaaxx.....aaa/aa/../ 11903.
Olsson, C.,, Elhage, N., Nanda, N., Joseph, N., DasSarma, N., Henighan, T., Mann, B., Askell, A., Bai, Y., Chen, A., et al. In-context learning and induction heads. arXiv preprint arXiv:2209. 1895, 2022.
Zhang, F. and Nanda, N. Towards best practices of activa- tion patching in language models: Metrics and methods. The Twelfth International Conference on Learning Representations, 2024. URL https: htttp::://peeeeevieee net / www.uroidddooooo.........r..i..r did= 7y 6B.BC.
O'Neill. M. E. Peg A family of simple fast space-efficient statistically good algorithms for random number generation. 2014. URL attps://api. semant www.ccccc...oooocooccooc Soorr///orpussii
Zhong, 7., Liu, Z., Tegmark, M., and Andreas, J. 'he clock and the pizza: Two stories in mechanistic explanation of neural networks. Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https: / // //openreview net forum? satrrummmiiSStteee 1d-55wmb@c1l..
Power, A., Burda, Y., Edwards, H., Babuschkin, I., and Misra, V. Grokking: Generalization beyond overfit- ting on small algorithmic datasets. arXiv preprint 2rXiv:2201.0211 2022.
Press, O. and Wolf, L. Using the output embedding to improve language models. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 2, Short Papers, pp. 157-163, 2017.

---

(How) Can Transformers Predict Pscudo-Random Numbers?
A. Experimental Details
This section provides further details about model architecture, dataset construction, and optimization.
A.1. Dataset Construction
Fixed Modulus (FM): Given a modulus m, we apply the Hull-Dobell Theorem to determine the possible values of (a, c) that maximize the period. We then randomly select 64 values of a and e to generate the test dataset. To generate the training dataset, we exlude these test choices of (a, c) and uniformly sample N 100, 000 LCG sequences of length L (context length) with ng values of multipliers and ne values of increments. For each set of parameters (a, c). we sample an LCG sequence with randomly selected initial seed Fo. Note that the training dataset includes sequences with varying periods, while the test data only contains sequences that maximize the period.
Test Accuracy
Test Accuracy
Test Accuracy
512, 1kg
32
170
512. nt,
32
512, 10g
128
0.061
0.900
0.951
0:575
0.959
0
0.082
0.970
0.992
0.926
0.955
0.8
0.8
0.3
19
2
0S12
0092
3.50
0.025
0.842
0.247
0.801
0.05
0.6
0.023
0,041
0.745
0.301
0.973
0.5
0.6
2
2
00011
0.223
2/4
0.012
0.012
0.220
0.148
0.104
0.011
0.012
0.127
0.100
0.370
0.4
0.3
R4
3
0.011
0 0000
0.032
0.043
0.051
0.034
+02
12
0.009
0.032
0.063
0.043
0.030
0.2
0.2
16
32
84
128
256
18
64
128
256
16
64
128
250
Figure 12. The impact of training dataset parameters (Am,, Ray n22) on unseen modulus task performance.
Generalization Unseen Modulus (UM): For the test dataset, we first select set of test moduli Mist = {mess) } that would be reserved exclusively for evaluation. For each test modulus Whess Mist. we apply the Hull-Dobell Theorem to determine the values of (a, c) that maximize the period. We then randomly select 64 values of and to generate the test dataset. These 64 (a. c) values are not considered while generating the training dataset.
For the training dataset generation, we sample the nm modulus values from the range [L, [1.2 max max()Mss)]] while excluding all the values in Mest For each modulus value m, we uniformly select n. multipliers (0- < a < m) and n. increments (0 S < m), excluding the ones reserved for testing. For each parameter (a, c, m), we generate a sequence of length using a randomly selected initial seed zg. This results in a total of N Rym X n2 X ne training sequences. We report that N 400, 000 served sufficient from the modulus values considered in this work.
Next, we examine the effect of training dataset composition (Am, Ray ne) on the performance. Figure 12 shows the test accuracy primarily depends on np and marginally on n. and ng. Furthermore, we found that n.m Z musa/ yields good generalization performance (result not shown here). Based on this relationship and our target total number of training
examples N, we sample ni ne mare/ values of multipliers and increments. Unless explicitly specified, we use these parameter settings as the default configuration for all experiments.
A.2. Model Architecture Details
We consider GPT-style Transformers (Radford al., 2019) with learnable positional embeddings and weight tying (Press Wolf, 2017). The model architecture is characterized by the number of blocks (depth), embedding dimension (dmodet), and number of attention heads (Nocads). For most experiments, use GELU activations, except in Section 4, where use ReLU activations for better interpretability.
A.3. Training Details
We train the models with Cross-entropy loss using AdamW optimizer (Loshchilov & Hutter, 2019) with momentum hyperparameters B1 = 0.9 and B3 = 0.99. We implement a linear learning rate warmup over the first 2048 steps with an initial learning rate of zero and the target learning rate n7. By default, all experiments employ a batch size of 256. Weight decay is only applied to non- bias parameters.
In the unseen modulus case, we observed that both the optimal target learning rate 1 and weight decay strength
12

---

(How) Can Transformers Predict Pscudo-Randon Numbers?
Test 1024.
4,00e+00 embd dim 758, heads
Test 4295, N 4,00e+-05 embb 760, heads
Test 16304, N 6 6,00e+
depth
depth
embd dim- 760. heads
3.
0.73
3030
3922
C249
6725
0.73
0003
0.25
0.04
98
Weghh decgr
3.3
0473
3043
CB33
0,12
C70
9.4
0.01
880
1.44
2+-03
1.1111
0.001
34-03
00003
00
3+-h
1L0003
0.003
00
Figure 13. Heatmap of test accuracy of a 6 layer Transformer with learnnng and weight decay as the axes. As the modulus is increased from 1024 to 16, 384 the range of hyperparameters resulting in reasonable accuracy becomes narrow.
are highly sensitive to minute changes in training dataset properties (modulus Must number of LCG parameters 7mm Ma. and total number of examples N) and architectural changes (depth and embedding dimension). To determine the optimal hyperpamraters, we scan the learning rates E {3c-05, 1e-04, le-03} and weight decay strengths E {0.01, 3.0,
A.4. Training Cost
In Figure 10, the training of the m = 22 model was conducted using four NVIDIA A100 GPUs, requiring a total of 21.82 hours. The m = 26 model completed training in 4.83 hours under the same hardware setup. Despite having the same model size, the increased context length in the m = -232 model led to a significantly higher computational cost.
In Figure 11, both models were trained on single NVIDIA H100 GPU for 22 hours.
A.5. Hyperparameter Space Shrinking with increasing modulus
We also report a surprising phenomenon in the unseen modulus case, which we refer to. as the 'hyperparameter space shrinking.' As we increase the test modulus Mest while keeping the model architecture fixed, we observe that the optimal learning rate (1) and weight decay strength (A) shift significantly. Moreover, the range of these hyperparameter values that yield reasonable performance becomes increasingly narrow. Figure 13 shows this result for a layer Transformer.
B. Fixed Modules Training Results
For the FM case, we find that a single attention head in one layer is sufficient to solve the task when the modulus is not a prime number. In Figure 14, we present the model's 's training loss and performance across training steps for m 2048. Notably, panels (c, f) reveal significant disparity between training and test loss, indicating a grokking transition during the training process. Similarly, we plot in Figure 15 for similar curves for m 7776, where all curves qualitatively the same.
C. Prime Moduli
In the FM setting, when m a prime number, the task becomes much harder. Since there are no digit-wise periodic patterns, the model cannot perform the algorithm described in Section 4.2. In Figure 16, we trained two identical models to learn 2048, and observe that the task with m 2039 cannot be learned within the same number of training steps. Note that to rule out potential constraints from model capability, we used depth 2 models (as oppposed to depth in the main text) in both cases.
2039 and
In the UM setting, the model exhibits similar test performance on sequences with prime m and sequences with m as a power of two, as shown in Figure 17. We hypothesize that training on a diverse set of moduli helps the model rely less on the digit patterns and instead focus on more generalizable structure.
13

---

(How) Can Transformers Predict Pscudo-Randon Numbers?
(a]
[b]
(c)
T_heads
1
(d)
(6)
1f)
63
4:3
n_heads
62
2
63
Figure Test accuracy and train/test m 2048 2 depth=1, (a.b,)) Pheada
(d.e.f) Nheada
(a]
n_ n_heads
1
15"
190
(6)
(e)
1F)
1.0
n_heads
08
382
Figure 15. Test accuracy and train/test loss for m 7776 2 33 depth=1. (a,bc) Theads = (d,c,f) Theads 4.
D. Critical Depth for the Unseen Modulus Task
This section analyzes the depth and embedding dimension requirements for successfully training Transformer on the unseen modulus task. The experimental details are the same as described in Appendix A.
We varied depths E {2, 3, 4, 6, 8} and embedding dimensions in dmootel E (512, 768, 1024, 1280), with the head dimension fixed to dhead = 128. For each depth and width, we scanned learning rates 7) E (3e-05, 1c-04, 3c-04, 1e-03) and weight decay strengths E (0.01, 0.1, 1, 1.0, 3.0} to identify the optimal hyperparameters. We report that the optimal learning rate and weight decay strength heavily vary with depth, embedding dimension, and training dataset. For meva {1024, 4096), the models were trained for T 100, 000 steps, while for Meval 16, 384, the models required longer training for = 200, 000 steps.
Figure 18 shows the test accuracy heatmaps with depth and embedding dimensions as the two axes. These results demonstrate that a minimum depth of 3 is required to learn the LCG sequence prediction task, with marginal dependence on embedding dimension. This suggests the unseen modulus task requires a minimal computational depth of three to capture the underlying structure of LCGs.
14

---

(How) Can Transformers Predict Reuudo-Random Numbers?
Test, Acc vs Number Index
Train Acc vs Number Index
Training Loss Over Time
1.0
1.0
8
0.8
0.8
6
Accuracy
Accuracy
0.6
m 2039 2036)
0.6
2039
4
m 2039
m 2048 (T-2048)
m 2048
m 2048
0.4
0.4
3
0.2
0.2
0.0
0.0
50
100
150
250
50
100
150
200
250
10000 20000 30000 40000 50000 Training Steps
Number Index
Number Index
Test Accuracy
(b) Training Accuracy
(c) Training Loss
Figure 16. FM: Comparison between m = 2039 (prime) and m = 2048 (power-of-two), with both models trained for 50,000 steps. Each model has depth 2 and dmodet 1024. The test set consists of sequences with the same periods, while the training set includes arbitrary multipliers not present in the test set.
1.0
0.8
Accuracy
0.6
0.4
2048
0.2
1801 m
2039
0.0
100
200
300
400
500
Number Index
Figure 17. UM: Test accuracy comparison between 2039 (prime), 1801 (prime) and m 2048 (power-of-two) The model
was trained for 100,000 steps on a dataset consisting of 262,144 sequences with 512 distinct training moduli not present in the test set.
accuracc
Test accuracy 4096.
Test accuracy
1024,
0.00=-05
1.01
0.00e=05
1X1
210
16384. N 4.00e=05
1.0
0:576
0.347
0.322
3.520
2.522
8.854
8.8
186
899
0.8
0.8
0.8
0.9
0.44
0.772
FM
115
175
60.
2.555
170
883
0.65
Dryph
PM
DUG
10G
1780
0.5
03/3
0.1
5.55
1620
875p
3.75
2550
2.50
0.307
0331
0.14
0.302
m
2411
1525
2827
3375
0.51
0.34
0.34
0.84
3354
00.55
180
032
0334
512
768
768
Embedding
Embedding
Embedding
Figure 18. Test accuracy heatmaps of with depth and embedding dimensions as the two axes.
E. Training Time Interpretability
In this section, we examine the order in which training sequences with different periods are learned during training. For this experiment, we consider a six-layer Transformer with 4 heads and an embedding dimension of 768. For this experiment, we generate sequences of length 512 using 128 unseen moduli and 128 values of a and each. The model is trained with Adam hyperparameters: = 3 x 10 31 = 0.9, 32 0.99 and weight decay strength 1.0.
Figure 19(lftt compares the training accuracy of sequences with different periods relative to the context length 512. We
15

---

(How) Can Transformers Predict Pscudo-Random Numbers?
1.0
Train (peried < $12)
Train (period 256)
1.0
Train (period > 512)
Train (period 512)
Test accuracy
Test accuracy
accuracy
Accuragy
0.6
Accuracy
0.6
Accuracy
0.6
0.4
0.4
0.4
0.2
0.2
10
10a
104
10
10a
10a
10
10
10a
10
10
10
steps
steps
steps
Figure 19. (left) Comparison of the training accuracy of sequences with different periods relative to the context length 512, (center) Accuracy when the model is only trained on sequences with period < 512, (right) Accuracy when the model is trained on sequences with period 512.
observe that sequences with period 512 are memorized early in training, while the accuracy of long-period sequences coincides with the test accuracy. Next, we perform two more experiments by training the model on datasets consisting of (1) sequences with period <, 256, and (2) sequences with period > 512. Figure 19center, right) show the results of these experiments. The model fails to generalize when trained only on low-period sequences while training only on long- pengpperiod sequences eliminates grokking.
F. LCG Properties
F1. The period of the lower k-th bit when m is power of
In this section, show that for sequence of period Tm 2 the k-th lowest digit has period of 2 along the sequence. Consider an LCG sequence:
Tx+1 (az; + c) mod
(6)
where is power of 2, and coprime and is divisible by 4. The period of sequence æ, is (Hull & Dobell, 1962). The lower k-th bits of iz is given by:
2t.k 2t,
b
2
where 2 = mod? 2 Therefore, if 21,x has period of 2* then the lower & bits also have period of 2 Below, we show that = has a period of 2*
For an integer Mp. we can can re-write 2y as:
St = 2t,k + M,2
(8)
Next, we substitute Equation (6) into the definition of 2411k;
Zt= = 2e+1 mod 25,
[ax; c) mod m] mod 2*..
(9)
As m divisble by 2*, this simplifies to:
21+1, = (azz, + c) mod 2t
= (a + aM, + +c) mod 2
(azi, + c) mod 2k
(10)
Therefore, 21,6 follows its own LCG recurrence with the same a and but with a reduced modulus 2*, Because 2 and e are coprime and a divisible by 4, the period 2n is 2 Thus, the period of the lower bits is 2*
16

---

(How) Can Transformers Predict Pscudo-Randont Numbers?
Since k has period 2 and Fn has period 2*-1, the period of by is 2
F.2. Derivation of Equation (4)
We now derive Equation (4) of the main text:
It mod p. = a., Pi + a4,1, +... 04,,, M0
where wi,,,, {0, 10. 1} are base-p; digits. When the period of x, is m, each digit az,.e has a period of p.
Consider an LCG sequence:
11+1 = (az, + + mod m,
(11)
Wy where has prime factorization m = PP p2" ... P44 and is divisible by if m is divisible by 4 (Hull & Dobell, 1962).
and are coprime, is divisible by all prime factors of m
Consider the residulas R = zt mod p. where E {1....9.
l). We have: It = Ra, + Mi,P;" un
(12)
where M,, is an integer.
Substituting Equations (11) and (12) into the definition of Ri,111
R4,+1 = 2t+1 mod p.
[aa + c) mod m] mod p
(a.r + c)) mod p.
(oRa, + IM +c) mod p!",
(aRR, cc) mod p!
(13)
Next consider 2i,k,t, which is the lower & base-p: digits of RA ki, = Ri, mod pt.
(14)
Similarly, the recurrence of k, can be simplied as:
2i,k,t+1 = Ri,4+1 mod pl,
|(aBiit + c) mod p mod p,, (aRi, c) mod pi.
= (azi,k,t +) mod p.. P.,k, follows LCG recurrence with the same and and reduced modulus pf. Because p and coprime and is divisible by p., the period of Zi,k, is p.C.
(15)
aikk,, which is the lower k-th base-p; digits of ye, can be written as: Zi,h,t 24,
(16)
Since z has period y/A the period of ar, p/.
G. Fixed Modulus Interpretability
In this subsection, we show additional results on the model's behavior on the FM task.
17

---

(How) Can Transformers Predict Pscudo-Randort Numbers?
Only attend to position (t- 2*)
w-th bit
0.6
6-
7-
0.4
9-
0.0
24
16
256
token position
(a)
Only attend to positions (t 2*) and (t (-22))
0.8
w-th bit
0.6
7-
0.0
28
16
32
64
128
256
token position
(b)
Figure 20. (m 2048, = 1, Ahhadd = 1, dmodel 768) Per-digit test accuracies in binary representation, with attention masking (at inference time). 2048 attention key at position 2 depth=1, Mhedds 1, dmodel 768, averaged over and initial seeds. (a) For cach query, only the 2 (where = |lgg t|) is kept. All other attention weights are masked out. this case, the model can successfully copy the last & bits, but cannot predict higher bits. (b) For each query, only the attention key positions 2 and 2
are kept. All other attention weights are masked out. In this case, the model can predict higher bits with fairly high accuracy - this remarkable given that majority of the attention weights masked out.
Phoads
Dheads
average lest B0ourao!
1.0
average Lest eocurapy
1.0
average last acnuracy
1.0
sverage lest spqursoy
9954 CH112
N01
24
24
Token position
token position
token position
token posltion
Figure 21. Test accuracy vs token positions for m 2048 = 211, depth=1, various values of a, C. (a.b) Plaeads = 1 (c.d) Alboads 4. The accuracies for different a e are exactly on top of each other.
18

---

(How) Can Transformers Predict Recudo-Randood Numbers?
(a)
(b)
(c)
mubppled
average test accuracy
0.8
0.8
W th bit
006
heads
0.4
0.4
0.4
-02
10
3.0
0.0
16
0.0
24
32
token position
token position
token position
(d)
(e)
(f)
muboried
average test accuracy
1.0
1.0
3
0.8
0
0.8
bit
066
hheads
7-
044
test
8-
0.2
0.2
9-
02
0.0
24
24
32 token position
24
position
token position
Figure 22. Test accuracy for m 2048 = 2 dcpth=1, Theads E 4), dmodel = 768. (a,d) Test accuracy averaged over and imitial seeds. (b.e) Multiplication per-digit test accuracies matches exactly with average test accuracy. (c.f) Per-digit accuracy binary representation.
(a)
(b)
(c)
average test accuracy
0.8
0.8
24-
08
0.6
2
06
Dheads
0.4
g1-
0.4
par-git bost
0.2
02
g
0.0
-00
16
40
token position
token position
token position
(d)
(e)
average lest accuracy
1.0
per dig test accursiies muttitedd
1.0
1.0
21-
0.8
0.6
0.6
0.6
Nheads =4
0.4
0.4
0.2
0.0
0.0
24
16
32
token position
token position
token position
Figure 23, Test accuracy for m 7776 = 2 3 depth=1, Nheads E {1,4), dmodel = 768, (a,d) Test accuracy averaged over a, c and initial seeds. (b.e) Multiplication of per-digit test accuracies matches exactly with the average accuracy. (c.f) Per-digit accuracy in RNS representation.
19

---

(How) Can Transformers Predict Ranudo Numbers?
0.025
Fouifer amplitude
component 1
value
group numbers mod
0.000
-0.025
amplluud
Fourler
component 2
0.000
-0.025
2
group numbers mod
0.025
Fourier amplbude
component 4
0.000
-0.025
10
2/1
Fourrier amplitude
0.025
component
0.000
-0.025
10
15
2m
Fourier amplltue
valie
group numbers mod 8
component
0.00
valute
Tourier
6
0.00
10
15
number
frequency
Figure 24, Projections along Top 6 principal components of the embedding matrix, for m = 512, depth=1, 7hbeads = 1, dmnddl = 768.
20

---

(How) Can Transformers Predict Ranudo Numbers?
Fourier amplitude
component 1
0.000
60
10
15
30
2m
frequency
0.025
Fourfer amplibdee
component
0.000
50
group numbers
-0.025
10
number
Trequency
0.02
Fourier amplitdee
component 4
0.00
50
-0.02
10
2/1
number
frequency
Fourer smplltdde
100
component
0.000
-0.025
number
fraquancy
group numbers mod
0.025
Fourfer ampllude
component
0.000
50
-0.025-
2m
number
frequency
0.025
Fourier ampitude
component 5
0.000
50
group numbers mod 4
-0.025
10
30
2m
number
frequency
Figure 25, Projections along Top principal components of the embedding matrix, for m = 7776, depth=1, Aheads = 1, dmodel 768.
21

---

(How) Can Transformers Predict Ranudo Numbers?
0.05
M
Fourier amplitude
40
value
component
-0.05
15
27
number
frequency
0.05
Faurier amplitdde
40
component
value
20
-0.05
15
2n
group numbers mod
number
frequency
0.05
Fourier amplitide
component
value
0.00
20
-0.05
number
frequency
Fourier ampltide
component 4
value
20
-0.05
15
number
frequency
Fourier amplitudd
component 5
value
0.00
20
-0.05
15
number
frequency
group numbers mod 9
0.05
Fourier amolitude
velue
20
component
0.00
-0.05
15
number
frequency
Figure 26. Projections along Top 6 principal components of the embedding matrix, for 1800, depth=1, Phoads 1, dmodel 768.
22

---

(How) Can Transformers Predict "xcudo-Random Numbers?
H. Unseen Modulus Interpretability
H.1. Extra PCA plots for first layer heads
We present additional PCA analyses of attention heads shown in Figure 8, examining (CA(H(A) (t,,;)) for each head across various combinations of a, C, 20, Must, and position The results are depicted in Figure 27, where we include two additional first-layer heads (heads 2 and 3) that responsible for performing operations related modulo 5. Notably, with different choices of C, Muest and compared to Figure 8 (al, b1, cl), the clustering behavior remains unchanged.
Note the emergence of attention heads dedicated to processing modulo 2, 3, 5, and can likely be attributed to the prevalence of these prime factors in the training set.
Pard
(a) a 13, C 3, Mest
2048,
8
1
(b) 9, C 3, Msest
2048, t = 128
ANN ADO AN
(c) 61.
7. Musd 1800,
47
Figure 27. PCA analysis of first-layer heads. Although the ordering of numbers varies, the grouping behavior discussed in Section 4.3 remains invariant changes in a, m. æn. and L. Note that the last head the head that appears in Figure 9, which does not exhibit strong grouping bias.
H.2. Pruning heads corresponding to irrelevant prime factors
To further validate our findings from Figure 8 in Section 4.3 regarding the correlation between attention heads and digit-wise accuracy, we conduct additional pruning experiments. The results of these experiments are presented in Figures 28 and 29,
H.3. Patching other heads
In Figure 30, we present patching experiments for heads not previously shown in Figure 9, We focus only on selected heads where patching significantly affects predictions. Notably, none of these cases exhibit qualitative changes stemming from modulus alterations, further supporting our assertion that the head shown in Figure is specifically responsible for estimating Mest-
23

---

(How) Can Transformers Predict Pscudo- Rando- Numbers?
-3.4
-9.4
-..
-3.2
-33
-0.3
-0.3
33
129 161
225
65
161 193
225
97 129 161 193 soaition
225
locen position
tocen
(a) Original Model
(b) Prune modulo head
(c) Prune modulo head
Figure 28. Per-digit accuracy for Meses 2048 after pruning specific attention heads. (a) Results from the same model used in Section 4.3, identical Figure (b2); (b) Performance
pruning attention head responsible for grouping numbers by their values modulo which is irrelevant for solving sequences with muat (containing only the prime factor 2). After pruning, the model's performance shows marginal improvement for specific early bits at lower token positions; (e) Performance after pruning the attention
responsible for grouping numbers by their values modulo 14. The model's performance miees decreases significantly, as this head partially contributes to processing relevant prime factors. However, since the primary head responsible for binary representation remains intact, the model maintains partial functionality.
10
1.0
10
24 &
Now
31
0.4
7
65
225
33
193
(a) Original Model
(b) Prunc modulo head
(c) Prune modulo 2 head
Figure 29, Per-digit accuracy for Msest = 2352 after pruning specific attention heads. (a) Results from the same model used in Scction 4.3, identical Figure (b2): (b) Performance after pruning the attention head responsible for grouping numbers by their values modulo which is relevant for one specific digit in this case. After pruning. the model's performance shows clear degradation, with the strongest happeming exactly the digit corresponding modulo 3 (c) Performance after pruming the attention head responsible for grouping numbers by their values modulo 2. The model's 's performance on mest got obliterated, as there are many base-2 digits in the RNS representation of mestt in this
H.4. In-accurate estimation of Mseat
From the cosine-similarity panel in Figure 9, we observe that the model's estimation approximates the target Mest = 2048. However, detailed analysis reveals that the highest cosine-similarity occurs at Mest = 2033 = 19 107, with neighboring values exhibiting similarly high cosine-similarity values. we assume Mest represents the model's internal belief, then the prime representation would consist solely of powers of 19 and 107. Such a representation can only produce periodic structures for the k-th bit of binary number when lcm(19 (19, 2* Consequently, patterns before reaching that period would appear random in this representation, providing weaker signal compared to the correct representation. This explains why the model preferentially selects binary representation for lower bits when Mhest = 2048.
For higher bits, the low-bit representation can be determined up to 2 bits through copying, If the model utilizes this information later stages, the precision of Mast. can be drastically improved. Specifically, when Mest/ | /2*1 the model can identify the correct representation as long as |Mtest mestl < 2 This argument can extended to any other composite Meest- Note that this argument is hypothetical; further proof of this mechanism remains future work.
24

---

(How) Can Transformers Predict Rxcudo-Randood Numbers?
2000
proditeo piiched precicct
INSOrI midel prodution
1000
1000
129
193
2.25
33
129
161
163
token position
token position
(a) layer I, head 4
(b) layer 2, head
2000
2000
1000
1000
193
token position
token position
(c) layer 3, head 6
(d) layer 4, head
Figure 30. Patching experiments following the setting of Figure in the main text. None of these heads, after patching, make the model believe that the modulus close to mpatch.
H.S. Evidence for Step iii
In Figure 31, we present attention patterns and token distance statistics for selected attention head in later layers, with the same model as the one used in Section 4.3. The token distances are measured by the spacing between keys with top-4 attention weights for a given query. Our analysis reveals that the model develops a head capable of dynamically adjusting their lookback distance for computations based on Mestt which we interpret as evidence for step iii of the algorithm proposed in Section 4.3.
(a1)
(a2)
08
9930
0.6
6000
0.4
002
0
22A
64
96
128
192
224
token distance
(b1)
1.0
(b2)
08
20002
10002
10000
192
-02
5200
724
2.0
0
32
96 key
128
160
192
224
token distance
Figure 31. Attention patterns and token distance statisties for layer 2, head 3 of the model analyzed in Scction 4.3. (al, b1) Results for a sequence with Miest = 2048, a 5, and = 31. The statistics reveal that the model consistently looks back at distances that are multiples of 4, which divides mise and enables the correct copy behavior. (a2, b2) Results for sequence with Must. 2352, and c In contrast to panels (al, bl), the same attention head now consistently looks back at distances that are multiples of 14, which allows the model copy lower digits from the context. This adaptive hehavior demonstrates that the model has acquired the ability to dynamically adjust its lookback distance by iterations to copy the lower digits and leave the higher digits to the later layers for computation.
85,
25

---

(How) Can Transformers Predict Pscudo-Randont Numbers?
1. Scaling Up the Modulus
I.1. Base-b tokenization
To convert an integer æ to base with the least significant digit (LSD) first, repeatedly divide x by b, storing remainders:
d = x mod b, Lz/b].
(17)
Stop when = 0. The sequence (do, ......) is the base-b representation in LSD-first order.
Example: Converting r = 3, 214, 748, 365 to base 256:
3, 214, 748, 365 + 256 12, 557, 610 remainder 205, dg 205,
12, 557, 610 + 256 49, 053 remainder 42, d1 42,
49, 053 + 256 191 remainder 157, d2 157,
191 + 256 = 0 remainder 191, d3 = 191.
The final LSD-first representation consists of four tokens:
(205, 42, 157, 2256-
Each token is then one-hot encoded into b-dimensional vector, where only the index corresponding to the token value is set to 1. These one-hot vectors are then fed into a token embedding layer with an embedding dimension of dmodel = 1024.
1.2. Abacas Embeddings
The positional embedding for the j-th lower digit of the i-th number in the sequence is defined as:
(TE,)))dd(t..)) Eint (1) + Edigit (j)
(18)
where T represents the token corresponding to the j-th digit of the i-th integer.
Ein (1), Edigit (f) E Raddd are learnable embeddings.
Ein (1) encodes the integer's position in the sequence.
Faigit (j) encodes the digit's relative position within the integer.
This embedding scheme ensures that each token captures both the integer's global position and the byte's local position. Figure 32 provides a visualization of base-b tokenization and abacus embedding.
I.3. Fixed Modulus
For each modulus = 2*, where A: E [16, 32), we train 2-layer GPT model with embedding dimension of 1024 and vocabulary size 256. The train set consists of n. = 1024 multipliers and n. 1024 increments, selected via the Hull-Dobell theorem. One LCG sequence length 512 is included the train set for each (a, e) pair, resulting in a total training set size of na X n. = 1, 048, 576. For each modulus, the model trained for 200,000 steps with a batch size of 512. The context length is 512x the digit length m the byte representation 11. For m 232, the digit length byte representation 4; therefore, the context length is 2047. Training was performed using A100 GPUs over total duration of 21.82 hours. For 65536, the digit length in byte representation is 2, resulting in context length of 1023, with training taking 4.83 hours. For each modulus, the test set includes 512 unseen values and 64 unseen values selected via the Hull-Dobell theorem.
The model may converge to different solutions depending on two random seeds: one for model initialization and batch shuffling, and another for dataset generation. Figure 35 shows the median performance across five runs, with the shaded region representing the range between the minimum and maximum values. For larger moduli, not all models successfully find a solution that achieves 100% test accuracy.
26

---

(How) Can Transformers Predict
Numbers?
PRNG sequence
Xo 0
X1
X2
2
,
3
2
Base-b tokenization
2
0
0
0
2
C1
2
2
2
22
t
+
2
+
+
t
4
Token embeddings
1
1
2
2
2
Abacus embeddings
0
0
0
0
1
1
1
1
2
2
2
2
Abacus embeddings
0
1
2
3
0
1
2
3
0
2
3
Figure 32. Visualization of base-b tokenization and abacus embeddings. Abacus embedding is shared by all the digits within the integer. while Abacus embedding 2 varies within the digit but is shared by all integers.
0.8:
Number Accuracy
Number Accuracy
Accuracy
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
train
train
train
100
200
300
400
500
100
200
300
400
500
100
200
300
400
500
Number Index
Number Index
Number Index
(a) PyTorch seed dataset seed 71
(b) PyTorch seed 10, data seed 71
(c) PyTorch seed 11, data seed 71
1.0
1.
10-
Number Accuracy
0.8
Number Accurac)
0.8
Sumber Acouract
0.8
train test
0.0
test
0.0
test
300
200
300
Number
Index
(d) Py Torch seed = 11, data seed 71
(c) PyTorch seed 11, data seed = 72
(f) Py PyTocc seed 11, data seed 73
Figure Test accuracy vs. Number index for m 220 First Row: Three models trained on same dataset, each using a unique PyTorch random seed that controls model initialization and batch shuffling. Second Row: Three models trained different datasets, with each dataset generated using a unique random seed controlling NumPy randomness for sampling a, c, and Fa. All models converged solutions that achieved and sustained 100% test accuracy, but differed in the number of in-context examples required to reach this performance.
27

---

(How) Can Transformers Predict Pscudo- Random Numbers?
1.0
0.81
test
0.71
test
0.6
test
Number Accuracy
Number Accuracy
0.66
Number Accuracy
0.5
0.5
0.4
0.3
0.4
0.3
0.2
0.2
0.2
0.11
0.0
0.0
0.0
100
200
300
400
500
100
200
Number Index
Number index
Number Index
(a) PyTorch seed 9, datasct seed
(b) PyTorch seed 10, datasct seed
(c) PyTorch seed 11, datasct seed 71
0.7
train
train
train
0.6
0.8
0.4
Number Accuracy
0.5
Number Accuracy
0.4-
0.6
0.3
0.2
0.1-
100
200
300
400
500
100
200
300
400
580
100
200
300
400
500
Number Index
Number Index
Number Index
(d) PyTorch seed 11, dataset seed = 71 (c) Py Torch seed = 11, dataset seed
72
(1) PoTorh seed 11, dataset seed = 73
Figure 34. Test accuracy vs Number index for m 22 First Row: Three models trained on the same datasct, cach using a unique PyTorch random seed that controls model initialization and batch shuffling. Sccond Row: Three models trained different datasets, with each generated using unique random seed controlling NumPy randomness for sampling c, and Only one of the five models found solution that achieved sustained 100% test accuracy.
number of in-context examples
2
2/.
29
25.
2
218
200
222
2
22h
220
230
2
Figure 35. Median number in-context sequence elements required to achieve 100% test accuracy across five runs. The shaded region represents the min-max range.
L.4. Unseen Modulus
We train a 6-layer GPT model on dataset that comprises n.m = 32, 768 moduli, with n., 128 training values and n, = training c values per modulus. This results total of nm x n, X n, = 4, 194, 304 sequences, each of length
512 the training set. In Figure 36a, where the tokenization base is 256, 1024 < Murain < 65536. Figure 36b, where the tokenization base is 243, 1024 Merain < 59049. Multipliers are selected based on the Hull-Dobell theorem when
28

---

(How) Can Transformers Predict Pscudo-Random Numbers?
sufficient qualifying values are available; otherwise, random a values used to ensure 128 multipliers for each modulus. The models with approximately 76M parameters were trained 16 million sequences over 400,000 steps, using batch size of 128 single H100 GPU for 22.62 hours. Because LCGs are typically defined for moduli that are powers of prime numbers, the model is tested on moduli that are powers of the primes 2, 3, 5, and 7. The test set consists of 512 unseen values and 64 unseen e values selected via the Hull-Dobell theorem for each test modulus.
Test performance is influenced by the tokenization base, exhibiting a bias toward moduli that share the same base as the tokenization method. For instance, in Figure 36 (a) when using byte-level representation, the model achieves better performance on moduli Mitatt. 2* compared Mitest 3 5*, or 7*. As contrasted with Figure 36 (b) where the tokenization base is 243 3 the model performs better moduli LCGs, where for moduli that are powers of prime b, the lowest k-th digit exhibits period of bA Tokenization in such base highlights this periodic structure, making it more apparent and easier for the model to leverage during training and prediction.
3 This behavior is likely due the property of
1.0
1.0
0.8
m
m
2048
2048
Accuracy
0.6
16384
2187
30.00
0.6
16384
2187
19683
19683
0.4
3125
0.4
3125
15625
15625
2401
2401
0.2
16807
0.2
16807
0.0
0.0
100
200
300
400
500
100
200
300
400
500
Number Index
Number Index
(a) Tokenization base 256
(b) Tokenization base 243 3
Figure 36. Test accuracy Number index. In (a), the moduli 2048 and 16384 (blue curves) have the same root 2 the tokenization base 256. The model performs better on these two moduli. In (b), the moduli 2178 and 19683 (orange curves) have the same root 3 as the tokenization base 243, The model performs better these two moduli.
29


Reviews:
[{"review_id": "n6Nxej4xAF", "reviewer": "Reviewer_rtPM", "summary": "Summary:\nThis paper trains transformers on the task of in-context predicting the next element of a sequence generated with a Linear Congruential Generator (LCG). An LCG has the form:\nx_{n+1} = a x_n + b (mod m), where\na, b, m are unknown numbers.\n\nThe paper studies two settings: 1) Fixed-Modulus (FM) setting, where m is the same in all contexts, and 2) Unseen-Modulus (UM) setting, where m varies, and the model is tested on held-out values of m.\n\nThe paper mechanistically interprets transformers on these two tasks. It argues that the radix representation for (mod m) is critical to how the model internally learns to represent the input. It argues that the embedding of the inputs reflects their structure in the radix representation.\n\nAdditionally, it argues that the model learns the lower-order bits by performing a lookup to previous terms in the sequence whose period corresponds to the radix representation.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful assessment and valuable feedback. We have added new experiment Figures S1, S2 at the link: https://doi.org/10.6084/m9.figshare.28703570.v2 -- which we will refer to in our response below.\n\n## Learning of higher bits\n\nBelow we present a modified and more accurate account of copying and predicting behavior in the FM setting. The corrections and modified experiments mentioned here will be reflected in the final version of our paper. \n\nConsider the model predicting the number $x_t$. For copying the last $k$ bits (least significant), attending to only one token is required -- located at position $t - 2^k$, where $k = \\lfloor \\log_2 t \\rfloor$. This can be seen from our new experiments in Fig.S1(a). Note that this is a stronger statement than the one in the paper, where we mentioned the need for two bright lines for copying.\n\nAttention to all the other tokens contributes towards predicting higher bits. Specifically the attention to token position $t - 2^{k-1}$ plays an important role. Note that this is a correction to the comment in the paper that the line at $t - 2^{k-1}$ only contributes to copying. This is demonstrated in Fig.S2(b), which is an improved version of Fig.15. (We found a subtle mismatch between selecting the attention mask using top two values and using desired two token positions.)\nIt shows that even if we mask out attention to all tokens except positions $t-2^k$ and $t - 2^{k-1}$, the model can predict higher bits with remarkable accuracy. Here we present an intuitive explanation of predicting the higher bits via a simple example, using the sequence from Fig.2 in the paper: $(1962, 411, 624, 1593, 838, \\dots)$.\n\nConsider the model predicting the number at $t=4$ ($k=2$). In predicting $x_4 = 838 \\equiv (01101000110)_2$, the model attends to $x_0 = 1962 \\equiv (11110101010)_2$ and $x_2 = 624 \\equiv (01001110000)_2$.\nWe label the numbers by their lowest 3 bits: $x_0 \\equiv (\\cdots 010)_2$ and $x_2 \\equiv (\\cdots 000)_2$. Then, by copying the lowest two bits, we have $x_4 \\equiv (\\cdots ?10)_2$. Now, if we consider $r=2$ iterations and drop the (constant) lowest bit, we obtain the new reduced sequence $x'_0=x_0 \\equiv (\\cdots 01)_2$, $x'_1=x_2 \\equiv (\\cdots 00)_2$, and $x'_2=x_4 \\equiv (\\cdots ?1)_2$. Since the second lowest bit of this reduced sequence has period $8/2=4$, the only possible way to satisfy the period condition for the last two digits in the reduced sequence $x'_t$ is to have $x'_2 \\equiv (\\cdots 11)_2$ (and $x'_3=x_6 \\equiv (\\cdots 10)_2$). \n\nIn this way, the model calculated higher bits just by using the constraints from the period, along with the knowledge of $x_{t - 2^k}$ and $x_{t - 2^{k-1}}$.\nThis argument can be extended to even higher bits, by considering $r=2^k$-step iterations and added constraints from digit-wise periods. In practice, this method can be made even more robust with the knowledge of \"other faint lines\".\n\n## LCG with prime $m$\nWe find that in the FM setting with prime $m$ the task becomes much harder. Since there are no digit-wise periodic patterns, the model cannot perform the algorithm described in Section 4.2. In Fig.S2, we trained two identical models to learn $m=2039$ and $m=2048$, and observed that $m=2039$ cannot be learned within the same number of training steps. To rule out potential constraints from model capability, we used depth 2 models (compared to depth 1 in the paper).\n\nNote that moduli made up of powers of small primes (e.g. $2^w$) are ubiquitous in practice due to their computational efficiency. This motivated our choice of moduli in the paper.\n\n## Classical algorithms vs Transformers\n\nWhile LCGs can be cracked using classical algorithms, Transformers face a fundamentally different challenge in our setup -- they have to determine the underlying sequence in an LCG without explicit instruction. In addition, these Transformers have to reverse engineer an algorithm from seemingly random sequences. We think that without explicit training, it is non-trivial to predict if Transformers can learn to predict even these simple LCGs.\n\nRegarding AES and more sophisticated encryption schemes, we agree that these would be interesting targets for future research. Our work on LCGs serves as the first crucial step for predicting these complex encryption schemes using Transformers.\n\nFor further discussion, we refer the reviewer to the \"Unexpected scaling behavior\" paragraph in our response to Reviewer tdrB.\n\n## Corrected Equation 3\n\nDue to space constraints, we refer the reviewer to the \"Theoretical claims and related experiments\" section of our response to the Reviewer 7WLW.\n\nWe hope that we have satisfactorily addressed all of the reviewer's questions, especially concerning learning of higher bits.", "claims_and_evidence": "The experiments were convincing to me -- with ablation and patching studies that confirmed the researchers' interpretations of the internal workings of the model.\n\n1) However, I do not understand how the higher-order bits in mod 2048 sequences, are found by the model. This was mysterious to me, and I felt like it was not addressed by the paper. The paper mentions that if you look at the sequence x_{i}, x_{i+r}, x_{i+2r} for some r dividing 2048, then the higher-order bits have a period of length 2048 / r. However, the model does not have access to enough terms in this sequence to perform a backwards lookup in the same way that it can for the lower-order bits.\n\nSo what is the mechanism to learn these higher-order bits? I couldn't find the answer to this question in the paper, although the paper mentions \"multiple faint lines\" in the attention scores \"that are 2^{k'} distance apart\" for k' < k-1, and that it \"combines information from all these tokens to predict the higher bits\". This felt too vague for a paper that has as an objective to fully mechanistically interpret the network.\n\n\n2) Another related question that I have is: do you find that it is much harder to learn in the fixed-modulus setting when m is a prime? In that case the trick that you have described for learning lower-order digits no longer applies. When the model groks, what is the mechanism by which it learns the LCG in that case?", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "No theoretical claims. I checked the Hull-Dobell theorem and they have indeed cited it right.", "experimental_designs_or_analyses": "Yes, I looked through the entire paper and it seemed OK. See my comments on \"claims and evidence\" above, since I think that a full mechanistic understanding is not obtained by this version of the paper.", "relation_to_broader_scientific_literature": "This paper fits into work on mechanistic interpretability, which seeks to reverse-engineer trained neural networks. I am familiar with the results on neural networks learning arithmetic, and there are some elements in this work that vaguely resemble that. However, I am not aware of papers that do what this paper is doing, so it seems original to me.", "essential_references_not_discussed": "Not that I am aware of", "other_strengths_and_weaknesses": "I think that the setting is original and the results are cleanly described and presented. With the exception of the explanation of the higher-order bits, I think that this paper does a good job understanding how neural nets learn LCGs.\n\nThus, I think of this paper as resolving the case where m is a product of a few small primes: e.g. m = 2310 = 2*3*5*7*11 seems satisfactorily addressed by this paper, but for m = 2048 I am not fully convinced by the paper yet.", "other_comments_or_suggestions": "* Typo lines 105-109. The variable $m$ should be $p$ instead.\n* Typo Line 167? Equation (3) should be a product of the sums, instead of a sum of the sums ?\n* Typo in Figure 10 caption. eample should be example.\n* Typo in Line 436, column 2. 2^16 should be 2^{16}.\n---\n* The answer in https://security.stackexchange.com/questions/4268/cracking-a-linear-congruential-generator shows that LCGs can be cracked with a simple classical algorithm -- they have notably bad security. It is not as much of a surprise, therefore, that transformers can learn to crack LCGs than if they could crack more complicated schemes. Do you think that you could train a transformer to crack encryption schemes like AES? The scheme does not have strong theoretical backing insofar as I am aware, so it could be an excellent candidate to try.", "questions_for_authors": "Could you please clarify my confusions about higher-order bits above -- either by pointing to what I am missing in the current paper or by providing a new analysis that would convince me? I would raise my score.", "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": "SCqB309c2d", "reviewer": "Reviewer_7WLW", "summary": "This paper studies how Transformer can learn linear congruential generators sequence with either fixed or changing modulus. For fixed module, they discover that Transformer learns the radix representation and predicts each radix digit almost independently. Notably, the lower digit are predicted by copying from previous period. However, the model is also capable of predicting non-repeating higher order bit. For changing module, they discovered that the model learns to cluster number based on modulus for small numbers (like 2,3,4, 6) in embedding and first-layer attention head. They also find an attention head that attend to the largest number in the current sequence and use this to estimate the modulus.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for giving a detailed feedback and raising important questions. **Note**: New experiment figures at: https://doi.org/10.6084/m9.figshare.28703570.v2\n\n## Theoretical claims and related experiments\nThe reviewer is correct in pointing out that equation (3) is incorrect in general and incompatible with the experiments in Figures 3 and 6 (i.e. our experiments are accurate, but equation (3) is in error). Below, we present the corrected version of equation (3) and surrounding text:\n\nWe used the Residual Number System (RNS) (Garner 1959), where each number is represented by its values modulo pairwise coprime factorizations of $m$. Specifically, consider sequences with a composite modulus $m$, which has a prime factorization $m = p_1^{w_1} p_2^{w_2}\\cdots p_q^{w_q}$. In this case, we can *uniquely* represent each number $(x \\text{ mod } m)$ as the tuple of residuals $( x \\text{ mod } p_1^{w_1}, x \\text{ mod } p_2^{w_2}, \\dots, x \\text{ mod } p_q^{w_q} )$ and similar to equation (2) we can further decompose each residual,\n$$x \\text{ mod } p_j^{w_q} = \\alpha_{j,0} p_j^0 + \\alpha_{j,1} p_j^1 + \\cdots + \\alpha_{j,w_j-1} p_j^{w_j-1}$$\nwhere $\\alpha_{j,w} \\in \\{ 0, 1, \\dots, p_j - 1 \\}$ are base-$p_j$ digits. We refer to $\\{\\alpha_{j,w}\\}$ as the \"RNS representation\". When period $\\mathcal T_m = m$, we can show that each digit $\\alpha_{j,w}$ has a period of $p_j^w$. Then, the rest of the discussion remains the same. For example, the $r$ step iteration still reduces the period of each digit $\\alpha_{j,w}$ from $p_j^w$ to $p_j^w / \\gcd(r, p_j^w)$.\n\nIn experiments for Figures 3 and 6, we calculated the collection of $\\{\\alpha_{j, w}\\}$ for the target and model predictions, then compared which $\\alpha_{j,w}$ matching. Since these experiments already implicitly use RNS representations, they remain unchanged.\n(We had erroneously thought that the mixed-radix representations are similar to RNS representations -- however, we later realized that this is not the case.)\n\n## UM is similar to FM\n\nThe key difference between FM and UM is that the model has to figure out the modulus in-context. Once the model determines $m$, the sequence prediction task for UM is not any different from the FM case. Beyond the attention heads we show in the appendix, the per-digit accuracy in Figure 6 also shows a ladder-like structure similar to FM cases, suggesting the copying nature of the UM case.\n\nSuch $r$-step copying behavior is crucial for the model to make correct predictions even when the estimate for the modulus is imprecise. The model achieves this in steps: i) it estimates the modulus $\\widetilde m_{\\mathrm{est}}$ using the largest number observed in the context so far -- which is usually slightly smaller than the actual modulus $\\widetilde m_{test} < m_{test}$. ii) The model then corrects this imprecision by leveraging the $r$-step copying behavior. This effectively reduces the task to modulo $m / r$. Then, the small difference in estimating the modulus gets rounded off like $m/r = \\lfloor m_{\\mathrm{estimate}} / r \\rceil$. \n\n\n## Mechanism for predicting higher bits\nDue to space constraints, we refer the reviewer to the \"Learning of higher bits\" section of our response to Reviewer rtPM.\n \n\n## Related works\nWe thank the reviewer for pointing out relevant references. We will cite these references and add a thorough discussion on similar works in the final version of the paper. \n\n## Questions\nWe have addressed Questions 1&2 above.\n\nQ3. To the best of our knowledge, all LCG breakers *assume that the underlying sequence is LCG* and focus on estimating the parameters $(m, a, c)$ [1] or predicting the next number [2]. The strong prior on the form of the sequence makes the task much simpler. (termed \"open-box\" in cryptography).\n\nIn contrast, the Transformer has no such prior, thereby making the task significantly harder than simply finding $(m, a, c)$ (termed \"closed-box\"). During training, it learns to parse and utilize the patterns in sequences of seemingly random numbers, and applies these abilities for out-of-distribution sequences at inference time. Thus, it is difficult to make a fair comparison between the \"closed-box\" Transformer approach with \"open-box\" optimal breaking algorithms.\n\n We emphasize that the primary purpose of this paper is not to break LCGs with optimal sample complexity, nor to compete with existing open-box algorithms. Rather, our main objective is to investigate the extent to which a Transformer model can break various cryptographic primitives -- this paper serves as an initial step towards that goal. That the model can identify patterns already known to experts is encouraging, suggesting that Transformer models might also discover previously unknown patterns in more complex PRNGs (see also our response to Reviewer tdrB).\n\n[1] J. B. Plunstead, Inferring a Sequence Generated by a Linear Congruence, 1982\n    \n[2] J.Stern, Secret linear congruential generators are not cryptographically secure, 1987", "claims_and_evidence": "Overall, the mechanism pointed out by the authors are well supported by both observation and intervention. However, some of the mechanism remains mostly unexplained:\n\n1. In the fixed module case, the model is capable of predicting non-repeating bit in the modulus 2048 case, this is further shown in the scaling experiment that model only need example with m^{1/4} length to make successful prediction. How are these bit predicted by the model is not explained by the authors (while the authors point out that attention head that attend to 2^{k'} number ago is useful for this prediction.\n\n2.  In the changing module case, the authors argue that the mechanism learned by later layer is 'similar' to the unseen module case, but they only showcase that the attention head in higher layer will similar look back over period in the appendix. This evidence is not sufficient enough to support such a claim.", "methods_and_evaluation_criteria": "The paper train and interpret different models with both fixed and changing modulus. The evaluation is complete and thorough.", "theoretical_claims": "There is some theoretical flaws in the main paper about mixed radix setting. \n\nEquation (2) has a typo, there should be a summation from 0.\n\nEquation (3) are incorrect in general, one can easily see this as some small number can easily have two different mixed radius representation under this setting ( 1 * 2 + 1 * 2^2 = 2 * 3). Some of the number are not represented by this representation. This makes the result beyond power of 2 in fixed modulus case hard to understand.", "experimental_designs_or_analyses": "The design and analysis is overall detailed and complete. I have raised my concern in the Claims and Evidence part.", "relation_to_broader_scientific_literature": "This paper is similar to other interpretability work that studies how Transformer performs modulus calculus. One difference is that this paper does not discuss how the modulus calculus is calculated here.", "essential_references_not_discussed": "I think this paper needs to discuss relationship with in-context linear regression (with LCGs as regression in the modulus setting) and related work in using Transformer to solve LWE (regression in modulus setting with noise). Some of the modulus calculation interpretability work is also missed. An incomplete list includes [1, 2, 3].\n\n\n[1] https://arxiv.org/abs/2211.15661\n[2] https://arxiv.org/abs/2306.17844\n[3] https://arxiv.org/abs/2207.04785", "other_strengths_and_weaknesses": "The scaling experiment is very original and interesting.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. How is the mixed radius experiment carried out in detail? Especially, how is the mixed radius calculated for the experiment here?\n\n2. What is the possible mechanism that enables prediction beyond calculating?\n\n3. What implication will this work bring for the PRG community? Is LCG with known modulus actually easier to break with optimal breaking algorithm than the scaling law shown here (as it only requires regressing two numbers)? How is Transformers compared with the current best breaker in terms of complexity in the Unknown modulus setting?", "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": "FOOXKGEkG2", "reviewer": "Reviewer_EiTT", "summary": "This study analyzes whether a Transformer based on next-token prediction can learn an LCG sequence and, if so, how it models the sequence. Specifically, the study demonstrates that a Transformer can learn an LCG sequence given sufficient architectural capacity and training data. Subsequently, it examines the algorithms learned by the Transformer in both the FM and UM cases. Additionally, the study explores the training recipe for scaling up the modulus in this task.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their encouraging comments and thoughtful questions.\n\n\n- **Questions**: Yes, our study employs a decoder-only Transformer architecture with causal masking (autoregressive). \n\n  This choice emulates the real-world scenario where observations are obtained sequentially and, at the same time, prevents the model from cheating by checking future information. \n\n  We agree that exploring other architectures would certainly be interesting. While a prefix decoder-only model might allow us to use a sequence design similar to our current approach, an encoder-decoder architecture would likely require changing our objective (for data efficiency), formatting the task as a translation from the sequence $x_0, x_1, \\cdots, x_n$ to the parameters $(a, c, m)$. This reformulation would likely involve different learned features and scaling laws, and we leave them for future work.\n\n- **Relation to General Tasks**: This is certainly an interesting comment. As we mentioned in the introduction, LCGs can be viewed as a special kind of formal language, the latter of which is deeply intertwined with NLP studies. We believe that starting with LCGs and incrementally increasing the complexity of our datasets would eventually allow us to build a systematic approach to studying formal languages and NLP tasks.", "claims_and_evidence": "As shown in Figure 1, it is evident that the Transformer can successfully perform this task. Furthermore, based on the characteristics of the LCG sequence, the analysis of the algorithm learned by the Transformer is also clear.", "methods_and_evaluation_criteria": "Since this study does not specifically propose a new method, there is not much to cover in this section. However, one point of interest is the use of Abacus Embeddings in the modulus scaling process. It would be beneficial to include an analysis of this aspect.", "theoretical_claims": "I have reviewed the theoretical claims and have no points to discuss regarding this aspect.", "experimental_designs_or_analyses": "The experimental design of this study is well-balanced and valid, as it addresses LCG sequence learning across various scenarios, avoiding biases in the experimental setup.", "relation_to_broader_scientific_literature": "The analysis of how the Transformer learns LCG is a valuable finding for future Transformer architecture design. Additionally, the task proposed in this study can serve as a foundation for further research, encouraging continued exploration of the inner workings of Transformers.", "essential_references_not_discussed": "I believe there is no missing essential work.", "other_strengths_and_weaknesses": "Strengths: Selecting an appropriate task to analyze the capabilities of a Transformer is highly meaningful. While some previous studies have proposed interesting tasks, they often involved somewhat contrived scenarios. However, the task explored in this study deals with a random number generator used in actual cryptographic applications, making it a more thought-provoking and relevant choice.\n\nMinor Weakness: It would be beneficial to discuss how the Transformer analysis conducted in this study could be applied to more general tasks, such as those in the NLP domain.", "other_comments_or_suggestions": "There seem to be some minor typos in the Discussion section on page 8 that need to be corrected.", "questions_for_authors": "If the study employs an autoregressive Transformer in the style of GPT, does that mean it uses a decoder-only Transformer operating with causal attention? I am curious whether causal attention is critically related to the study's findings. Additionally, I wonder whether an encoder-decoder or a prefix decoder-only Transformer architecture could also learn the LCG sequence, or perhaps even perform better.", "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": "vuOwj8gWii", "reviewer": "Reviewer_tdrB", "summary": "The paper studies how Transformers can learn linear congruential generators (LCG), a class of simple pseudo-random generators. These are generators of the form $x_{n+1} = a x_n + c \\mod m$ for some choices of $(a,c)$ and $m$. The authors demonstrate that Transformers can learn from data to simulate LCG in two settings: when the modulus is fixed, and when it is varied (which requires generalization to unseen values of $m$). The authors also analyze how the Transformer is able to compute the LCG, both when the modulus is fixed and when it is varied, and give a \"pseudo-code\" for the algorithm implemented by the Transformer. Additionally, the authors study how the depth and number of heads in the Transformer affect the performance on this task.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful assessment and candid feedback. To address the reviewer's main concern, we clarify the motivation behind and the contributions of our work.\n\nOne major goal is to answer the following important question: To what extent can deep neural networks crack various primitives in cryptography? PRNGs are an important and commonly used component in cryptography, making them an ideal starting point for investigation. Moreover, transformers are perhaps the most effective pattern recognition systems ever developed, while PRNGs provide some of the best ways of hiding deterministic patterns, so it is natural to pit them against each other and study the resulting learning dynamics. Among PRNGs, LCGs represent the simplest case to examine, and we demonstrate how neural networks can successfully learn the subtle patterns in these sequences.\n\nThis work is expected to be among the first in a series of studies examining neural networks' ability to learn increasingly complicated arithmetic sequences. This line of research may reveal completely unknown properties of widely used cryptographically secure PRNGs (CSPRNGs) like AES-CTR\\_DRBG (also suggested by the Reviewer rtPM).\n\nAnother important goal is to explore the learning ability of transformers in controlled settings, where the data generation process is fully understood, unlike for real-world data like natural images and language. PRNGs provide a natural setting to study in-context learning ability, sample efficiency, and the role of architectural complexity, and further add to discoveries in interpretability of neural networks. \n\nNext, we highlight our contributions:\n\n- **Unexpected scaling behavior**:\nWe found how the number of in-context examples needed scales with problem complexity. One could argue that classical ways of breaking PRNGs exist in literature; however, we want to emphasize that our setup is qualitatively different because models are not explicitly informed that the data are LCG sequences. When training a Transformer model with just a collection of numbers without such context, there is no clear prior to determining whether the scaling law would be independent, sublinear, superlinear, or exhibit some other behavior. In other words, the scaling law pertains not merely to discovering $(a, c, m)$ or predicting the next number, but also to inferring the LCG rule. \n    \n- **New interpretability results**:\n    The ability to spontaneously factorize numbers as part of the learned algorithm was new and surprising. This, along with the capacity to estimate moduli, adds to a short but growing list of results in mechanistic interpretability studies.\n\n    Specifically, although LCGs utilize modular operations, these tasks are drastically different from classification settings like [1] and [2] and have much stronger long context dependence than (He et al., 2024), where they stack examples from the same modulus in random order. In our setting, for the Fixed-Modulus (FM) case, this difference leads us to a completely different set of features, where the model converts numbers implicitly to the digit-wise (mixed radix or RNS) representation without forming any circular embeddings like those found in existing works. On the other hand, since the modulus keeps varying for the Unseen-Modulus (UM) case, the circular patterns observed in modular arithmetic cannot be used here. In this case, the model has to develop the ability to estimate the modulus and combine it with similar features as FM cases to solve the task. To summarize, despite the surface-level similarity to modular arithmetic, the model learned vastly different underlying algorithms.\n    \n    Finally, our findings do not necessarily provide novel mathematical insights beyond what human experts in PRNG development already understand. However, the models' autonomous discovery of periodic structures in RNS representations from LCGs without explicit guidance is noteworthy. This particular phenomenon (please check the updated theoretical claim for Reviewer 7WLW) is likely familiar only to specialists in the field. The fact that this discovery occurred without directed instruction has not been previously documented in the literature and represents an exciting contribution. It suggests that sufficiently powerful models can potentially uncover unknown and surprising patterns from cryptographically secure PRNGs that humans are currently unaware of.", "claims_and_evidence": "The results in the work are interesting, and to my knowledge the setting studied in this paper is novel. The target problem of generating pseudo-random numbers allows the authors to carefully study the algorithm learned by the Transformer in two settings. The paper is well-written and the authors do a good job in introducing their results. The algorithms that are learned by the Transformer are clearly introduced, and the authors show convincing evidence regarding the mechanisms learned by the Transformer model, demonstrating the the Transformer indeed learns to implement these algorithms.\n\nThe main concern that I have is regarding the motivation for the results discussed in the paper. What are the findings in the paper telling us about Transformers and/or PRNGs that we did not know before? The paper certainly demonstrates that Transformers are able to learn LCGs in novel settings, which is interesting, but I am not sure if this is particularly surprising given evidence on other similar problems like learning modular arithmetic (e.g., [1]). The algorithm that Transformers learn is certainly clever, but I am not sure why we should care about how Transformers solve this particular problem. Is this a new or interesting algorithm for computing LCG? Are the interpretability methods used in the paper novel compared to other, similar works? It seems to me that there has already been quite a few works on interpretability of Transformers on similar tasks (such as [1] and [2]), so clarifying exactly what are the novel contributions and conclusions of this work compared to previous works would be helpful.\n\nMinor:\n- A formal definition of the period $T_m(a,c)$ would be useful.\n- In think there is a typo in the last paragraph on page 8 ($m2^16$ should be $m2^{16}$?)\n\n[1] PROGRESS MEASURES FOR GROKKING VIA MECHANISTIC INTERPRETABILITY, ICLR 2023\n\n[2] Feature emergence via margin maximization: case studies in algebraic tasks, ICLR 2024", "methods_and_evaluation_criteria": "See above.", "theoretical_claims": "See above.", "experimental_designs_or_analyses": "See above.", "relation_to_broader_scientific_literature": "See above.", "essential_references_not_discussed": "See above.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "See above.", "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:

Meta-review: This paper studies the high-level question of "To what extent can deep neural networks crack various primitives in cryptography?" In particular, this paper trains transformers on the task of in-context predicting the next element of a specific PRNG, ie, Linear Congruential Generator (LCG) and mechanistically interprets transformers. 

On the positive side, the experiment design and analysis are overall solid and complete. The reviewers are convinced by the mechanism learned by the transformer revealed in the paper. All reviewers recommend to accept this paper and I think this paper is a good and solid contribution to ICML.

On the negative side, though the experiment design and findings are novel, the reviewers have concerons about the motivation of this work --- it is not crisply clear what the takeaway is from the paper, since LCG can be broken easily by classical algorithms. It is not too surprising that transformers can compute the same function which are easy to compute in classical computation models. The authors should include the related discussions in rebuttal into the next revision of the paper.
Decision: Accept (poster)