(How) Can Transformers Predict Pseudo-Random Numbers?

Tao Tao, Darshil Doshi, Dayal Singh Kalra, Tianyu He, Maissam Barkeshli · 2025

Read (How) Can Transformers Predict Pseudo-Random Numbers? by Tao Tao, Darshil Doshi, Dayal Singh Kalra, Tianyu He, Maissam Barkeshli (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-10390.txt.

Introduction

Tao Tao and co-authors ask if a word tool can call false chance in a 2025 paper. The false sums in view are a plain wheel: each count is the last, times a set, plus a set, in a ring.

Fed the wheel's counts as text, a tool with room and range in school called fresh wheels whole. In its skin the team read the craft: the tool cracks the ring's count and works in digit parts. For a ring it has not met, it first calls the ring from the tale, then its parts. Past a depth of three the call snaps sharp. The count of tale bits it needs grows more slow than the ring. The authors cast the work as a lamp on how tools learn a rule.

Catalog record

CREATORTao Tao, Darshil Doshi, Dayal Singh Kalra, Tianyu He, Maissam Barkeshli
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE73 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-10390

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

(How) Can Transformers Predict Pseudo-Random Numbers? Tao Tao, Darshil Doshi, Dayal Singh Kalra, Tianyu He, Maissam Barkeshli 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 ​ mod ​ m x_{t+1}=ax_{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 m ) and parameters ( a , c 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 a,c ) but fixed modulus; and demonstrate successful learning up to m = 2 32 m=2^{32} . We find that models learn to factorize m 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 test = 2 16 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 d=3 . We also find that the number of in-context sequence elements needed to reach high accuracy scales sublinearly with the modulus. 2 2 2 We open source the code to reproduce our results: https://github.com/dayal-kalra/transformer-prng.git † † affiliationnotice: Equal contribution– authors listed in pseudo-random order. {tao2021, ddoshi, dayal, tianyuh, maissam}@umd.edu 1 Introduction Transformer-based language models have proven to be extremely powerful sequence generative models. With copious amounts of training data and computational resources, they can identify and learn complex patterns from training corpora, resulting in numerous remarkable capabilities ( Vaswani et al., 2017 ; Dosovitskiy et al., 2021 ) . Recent research 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 chain-of-thought reasoning ( Wei et al., 2023 ) . While these models have achieved unprecedented success, understanding what underlying patterns are learned and how they learn them remains a significant challenge. Pseudo-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. 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 Transformers 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 or merely detect shortcuts and spurious patterns? What effect do model capacity, data variety, training methodologies, and context length have on the capabilities of Transformers? This work aims to answer these questions by focusing on learning sequences obtained from linear congruential generators (LCGs) using GPT-style autoregressive Transformers. We demonstrate how Transformers can successfully learn LCGs with moduli up to m=2^{32} . We perform interpretability analyses, uncovering emergent structures in the embedding layers, attention heads, and underlying algorithms that the Transformer uses to learn the sequences. We also perform several systematic scaling analyses to understand the effect of architecture and sequence complexity on model performance and in-context learning ability. 1.1 Related works Our study on the learnability of PRNGs for Transformers touches on several modern and classic topics. Interpretability and Modular Arithmetic: A growing body of work examines the circuits, algorithms and structures 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., 2024a ; Doshi et al., 2024b ; He et al., 2024 ) . Our work adds to this by reverse-engineering the underlying algorithms and uncovering emergent structures in learning pseudo-random number sequences. Cracking PRNGs: There is a classic duality between cryptography 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) demonstrated that a fully-connected neural network can predict the outputs of a modified LCG with fixed (irrational) parameters (a,c,m)=(1,\pi,1) . In comparison, we systematically analyze the harder cases of unseen parameters using Transformers, reverse-engineer the learned algorithms, and study effects of scale and complexity. Formal Grammars: LCG can also be viewed as a formal 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 ) . Chaotic time-series: A major application of neural networks is predicting time-series for chaotic dynamics, such as weather prediction ( Lam et al., 2023 ) and financial modeling. 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 (x_{0},x_{1},\dots,x_{t}) according to the map: \displaystyle x_{t+1}=(ax_{t}+c)\mod m, (1) where m>0 is the modulus, 0<a<m is the multiplier and 0\leq c<m is referred to as the increment. An LCG map is uniquely defined by the choice of m,a,c and the initial seed x_{0} . An important quantity that determines the complexity of an LCG sequence is its period: 1\leq\mathcal{T}_{m}(a,c)\leq 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 \mathcal{T}_{m}(a,c)=m if and only if the values of a and c satisfy the following criteria: (i) m and c are coprime, (ii) a-1 is divisible by all prime factors of m , (iii) a-1 is divisible by 4 if m is divisible by 4 . We evaluate (test) all our models exclusively on sequences that obey the criteria of this theorem. 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

Read the complete text