(How) Can Transformers Predict Pseudo-Random Numbers?

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.

One 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.

This 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).

Another 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.

Next, we highlight our contributions:

• Unexpected scaling behavior: We 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.

• New interpretability results: 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.

  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.

  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.

We thank the reviewer for their encouraging comments and thoughtful questions.

• Questions: Yes, our study employs a decoder-only Transformer architecture with causal masking (autoregressive).

  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.

  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.

• 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.

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

Theoretical claims and related experiments

The 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:

We 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, $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}$ where $\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)$.

In 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. (We had erroneously thought that the mixed-radix representations are similar to RNS representations -- however, we later realized that this is not the case.)

UM is similar to FM

The 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.

Such $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$.

Mechanism for predicting higher bits

Due to space constraints, we refer the reviewer to the "Learning of higher bits" section of our response to Reviewer rtPM.

Related works

We 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.

Questions

We have addressed Questions 1&2 above.

Q3. 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).

In 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.

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).

[1] J. B. Plunstead, Inferring a Sequence Generated by a Linear Congruence, 1982

[2] J.Stern, Secret linear congruential generators are not cryptographically secure, 1987

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.

Learning of higher bits

Below 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.

Consider 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.

Attention 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.) It 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)$.

Consider 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$. We 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$).

In 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}}$. This 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".

LCG with prime $m$

We 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).

Note 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.

Classical algorithms vs Transformers

While 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.

Regarding 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.

For further discussion, we refer the reviewer to the "Unexpected scaling behavior" paragraph in our response to Reviewer tdrB.

Corrected Equation 3

Due to space constraints, we refer the reviewer to the "Theoretical claims and related experiments" section of our response to the Reviewer 7WLW.

We hope that we have satisfactorily addressed all of the reviewer's questions, especially concerning learning of higher bits.