Learning Modular Exponentiation with Transformers
David Demitri Africa Sara M. Kapoor Theo Simon Sorg · 2025
Read Learning Modular Exponentiation with Transformers by David Demitri Africa Sara M. Kapoor Theo Simon Sorg (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-2506-23679.txt.
Introduction
David Demitri Africa and co-authors wrote a 2025 paper on how a small transformer learns modular exponentiation, a core operation in number theory and code making. They train the model and then probe its insides to see what it has learned. Tools include sampling design, pattern maps of its codes, and patching parts of its activity.
Training on reciprocal pairs brought sudden jumps in skill across related moduli. The jumps look like grokking, where a model abruptly grasps a shared rule. A small group of attention heads in the last layer proved enough for full skill on plain exponentiation. The authors say transformers build special circuits for this math, a step toward clearer and leaner models.
Catalog record
| CREATOR | David Demitri Africa Sara M. Kapoor Theo Simon Sorg |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 32 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-23679
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Learning Modular Exponentiation with Transformers David Demitri Africa Sara M. Kapoor Theo Simon Sorg Abstract Modular exponentiation is crucial to number theory and cryptography, yet remains largely unexplored from a mechanistic interpretability standpoint. We train a 4-layer encoder-decoder Transformer model to perform this operation and investigate the emergence of numerical reasoning during training. Utilizing principled sampling strategies, PCA-based embedding analysis, and activation patching, we examine how number-theoretic properties are encoded within the model. We find that reciprocal operand training leads to strong performance gains, with sudden generalization across related moduli. These synchronized accuracy surges reflect grokking-like dynamics, suggesting the model internalizes shared arithmetic structure. We also find a subgraph consisting entirely of attention heads in the final layer sufficient to achieve full performance on the task of regular exponentiation. These results suggest that transformer models learn modular arithmetic through specialized computational circuits, paving the way for more interpretable and efficient neural approaches to modular exponentiation. 1 Introduction Modular exponentiation is fundamental in numerous areas of mathematics and computer science, notably in cryptographic algorithms such as RSA [ Rivest et al. 1978 ] and Diffie-Hellman key exchange [ Diffie and Hellman 1976 ] . Despite its mathematical simplicity, modular exponentiation presents significant challenges for machine learning models, given the non-linear and cyclic nature of the operation and the complexity of generalizing it effectively. Prior work by Charton 2024 explored how transformers can learn arithmetic functions such as the greatest common divisor (GCD), demonstrating that transformers implicitly uncover algorithmic structures in arithmetic tasks, laying important groundwork in understanding numerical reasoning in neural networks. However, modular exponentiation introduces new layers of complexity, notably the interaction between exponentiation and modulo reduction, which can lead to nontrivial number-theoretic patterns not present in simpler tasks such as computing the greatest common divisor. To the best of our knowledge, transformer-based models have yet to be systematically investigated in the context of modular exponentiation, particularly from a mechanistic interpretability perspective. Understanding how these models represent and manipulate numerical information internally when performing modular arithmetic is crucial, both from the viewpoint of theoretical curiosity and practical applicability, as modular exponentiation serves as a foundational primitive in secure computation. In this work, we extend the research initiated by Charton by training transformer models to perform modular exponentiation. We design novel sampling methods to capture the statistical characteristics of modular arithmetic and analyze how these sampling strategies influence model learning dynamics and generalization. Furthermore, we use mechanistic interpretability methods to provide insight into how models represent and manipulate number-theoretic information internally. We also observe the learning dynamics of the model, as it trains on the task, finding evidence of grokking as the model learns individual multiples. With this work, we hope not only to advance the understanding of transformer arithmetic capabilities but also to open new avenues for explainable neural computation in number theory and cryptographic reasoning. 2 Related Work 2.1 Mechanistic Interpretability and Circuits Mechanistic interpretability seeks to uncover the computational strategies and representational structures internalized by neural networks, aiming at transparency at the level of individual components such as neurons, attention heads, and weight matrices. The early foundational work by Olah et al. 2020 introduced the concept of circuits , coherent subgraphs within neural networks that correspond to meaningful algorithmic operations. Subsequent studies by Elhage et al. 2021 and Wang et al. 2022 expanded this framework, dissecting the internal structures of transformer models and providing interpretive insights into attention mechanisms, feed-forward layers, and embedding spaces. A comprehensive practical review of these advances in mechanistic interpretability, specifically tailored for transformer-based language models, is provided by Rai et al. 2024 . 2.2 Modular Exponentiation Modular exponentiation, despite its mathematical simplicity, plays a crucial role in cryptography, number theory, and computational complexity [ Rivest et al. 1978 , Diffie and Hellman 1976 ] . Classical algorithms such as fast exponentiation use the cyclic nature of modulo arithmetic to efficiently compute large exponentials modulo a number. Machine learning approaches to modular arithmetic have been explored, but remain limited to simpler operations such as modular addition and multiplication [ Gromov 2023 , Saxena et al. 2024 ] . Recent studies such as the work of Gromov 2023 demonstrate the ability of neural networks to learn modular addition through grokking , a sudden generalization phenomenon. Our work significantly extends this line of research by systematically investigating modular exponentiation, an inherently more complex and non-linear task, from a deep learning perspective. 2.3 Transformers and Mathematics Mechanistic interpretability has recently been applied specifically to arithmetic reasoning within transformer architectures. For instance, Quirke and Barez 2024 examined transformers performing addition tasks, discovering dedicated attention heads whose functions mirror human-engineered arithmetic algorithms. Similarly, Stolfo et al. 2023 used causal mediation analysis to rigorously demonstrate interpretable arithmetic pathways within transformer architectures, revealing explicit algorithmic structures encoded in model activations. Extending this line of research, Sharkey et al. 2022 used sparse autoencoders to disentangle complex arithmetic features hidden within transformer activations, improving the clarity and interpretability of arithmetic computations in neural models. A notable phenomenon driving recent mechanistic interpretability studies in arithmetic contexts is grokking — characterized by delayed and sudden generalization from memorization to genuine algorithmic understanding. Initially documented by Power et al. 2022 in the context of modular arithmetic tasks, grokking has provided valuable insights into how neural networks transition abruptly from simple memorization strategies to meaningful generalization. Subsequent analysis, such as that of Nanda et al. 2023 , introduced internal “progress measures” to identify specific circuits responsible for this emergent arithmetic capability. More recently, Doshi et al. 2024 studied grokking specifically within modular polynomial arithmetic, systematically uncovering specialized internal representations that transformers leverage during modular operations. Our work builds directly upon these foundations by extending explainability techniques — including learning dynamics analysis, activation patching, and PCA on embedding representations — to the previously unexplored domain of modular exponentiation. 3 Training Approach 3.1 Sample generation Following Charton 2024 , we experiment with various methods of sampling integers, in our case for modular exponentiation. Unlike GCD, where two integers a,b\in\mathbb{Z} and their respective \mathrm{gcd}(a,b) are sampled, modular exponentiation requires three operands. The below description focuses on sampling strategies for integers a,b,c\in\mathbb{Z} and their outcome d\in\mathbb{Z} such that a^{b}\equiv d\mod c (1) We try to sample a,b,c , and sometimes d , such that the tuples (a,b,c,d) follow a certain underlying distribution, with the maximum integer to sample set to M=10^{6} . Similarly to Charton 2024 , we find that the different distributions lead to varying learning dynamics and absolute accuracies. We observe a clear correlation for the distribution of samples and the accuracy achieved on these numbers, with greater imbalance leading to lower overall accuracy. We detail the sampling generation strategies below. Uniform operands The simplest strategy involves uniformly at random sampling a,b,c and computing d . This initial approach samples c\in[1,100] and a,b\in[0,M] independently and uniformly at random. d is then computed according to 1 . This results in d\in[0,99] , which is heavily skewed towards small values, as can be seen in the histogram of the generated samples Figure 1 . The decoder might never learn to predict larger outcomes due to the large class imbalance, which we verify in our experiments. Figure 1 : Histogram showing the