Research map / Architectures and efficiency / Attention and transformers
(How) Can Transformers Predict Pseudo-Random Numbers?
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that decoder-only Transformers can learn to predict linear congruential generator (LCG) sequences in-context, both for fixed moduli up to 2^32 and for unseen moduli up to 2^16, and reverse-engineers the learned algorithms (residue number system representations, modulus estimation).
Problem
Whether and how Transformers can learn to predict pseudo-random number sequences from linear congruential generators with unseen multipliers, increments, and moduli, and what algorithm they implement.
Approach
Trains GPT-style autoregressive Transformers on LCG sequences, then reverse-engineers the learned algorithm: models build residue-number-system (prime-factor) digit representations in embeddings and attention heads, and for unseen moduli first estimate the modulus from context. Scales via base-b tokenization and abacus embeddings.
Key results
- With fixed modulus, a 1-layer single-head Transformer learns LCGs at m=2048 and models reach 100% test accuracy up to m=2^32 with sufficient context; in-context length needed scales sublinearly as m^(~1/4).
- For unseen moduli, a minimum depth of 3 layers is required, with a sharp accuracy transition; models generalize to unseen moduli up to m_test=2^16.
- In the unseen-modulus setting, the number of in-context elements needed for 60% accuracy scales as m_test^gamma with 0.24 <= gamma <= 0.33.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Steele multipliers instead of arbitrary multipliers | Fixed-modulus Transformer · LCG, m = 2^32 | test accuracy | Hurt |
| Increase depth from below 3 layers to 3 layers | Unseen-modulus Transformer · Unseen-modulus LCG prediction | test accuracy | Helped |
| Increase the number of attention heads, especially from one to two | Unseen-modulus Transformer · Unseen-modulus LCG prediction | test accuracy | Helped |
| Train only on long-period sequences instead of only low-period sequences (ablation) | Unseen-modulus Transformer · Unseen-modulus LCG prediction | generalization | Helped |
| Keep attention to both t-2^k and t-2^(k-1), rather than only t-2^k (ablation) | Fixed-modulus Transformer · LCG, m = 2048, higher digits | per-digit accuracy | Helped |
| Remove the attention head specializing in the relevant prime factor (ablation) | Unseen-modulus Transformer · Unseen-modulus LCG, corresponding prime-factor digits | per-digit accuracy | Hurt |
| Remove the modulo-3 head (ablation) | Unseen-modulus Transformer · m_test = 2048, selected token positions | per-digit accuracy | Mixed |
| Use tokenization base 243 instead of base 256 (ablation) | Unseen-modulus Transformer · Unseen moduli that are powers of 3 | test accuracy | Helped |
| Use tokenization base 256 instead of base 243 (ablation) | Unseen-modulus Transformer · Unseen moduli that are powers of 2 | test accuracy | Helped |
Surprising findings
- Models trained on fixed modulus need only one layer and one attention head to solve the task at composite moduli.
- Prime moduli are much harder to learn in the fixed-modulus setting (m=2039 not learned in same steps as m=2048), while in the unseen-modulus setting prime and power-of-two moduli perform similarly.
Limitations
- Results limited to moduli m <= 2^32; larger moduli untested.
- Only LCGs studied; PCG and truncated LCGs left to future work.
- Training is sensitive to hyperparameters, with optimal learning rate and weight decay shifting and the good range narrowing as modulus grows; some seeds fail to reach 100% at large moduli.
Experimental setup
Datasets: synthetic LCG sequences generated via Hull-Dobell theorem parameter selection
Benchmarks: held-out LCG sequences with unseen (a,c) at fixed modulus held-out LCG sequences with unseen moduli (e.g., 1800, 2048, 2352, 16384, 2^k and 3^k)
Metrics: per-position next-token accuracy per-digit accuracy in-context length needed for 100% (or 60%) test accuracy
Builds on: GPT abacus embeddings grokking Hull-Dobell theorem
Closest papers by meaning
- Algorithmic Capabilities of Random Transformers (NeurIPS 2024 · similarity 0.88)
- Towards Understanding the Universality of Transformers for Next-Token Prediction (ICLR 2025 · similarity 0.86)
- Separations in the Representational Capabilities of Transformers and Recurrent Architectures (NeurIPS 2024 · similarity 0.86)
- A Formal Framework for Understanding Length Generalization in Transformers (ICLR 2025 · similarity 0.86)
- In-context Learning on Function Classes Unveiled for Transformers (ICML 2024 · similarity 0.86)
- How do Transformers Perform In-Context Autoregressive Learning ? (ICML 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.