# Learning the greatest common divisor: explaining transformer predictions

arXiv: https://arxiv.org/abs/2308.15594 · HTML: https://mlsanity.com/paper/2308.15594/

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 31 references that are in the map.
- First posted on arXiv 29 Aug 2023.

## Builds on (most cited first, 21 of 21)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [Progress measures for grokking via mechanistic interpretability](https://mlsanity.com/paper/2301.05217/) (2023)
- [Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets](https://mlsanity.com/paper/2201.02177/) (2022)
- [Analysing Mathematical Reasoning Abilities of Neural Models](https://mlsanity.com/paper/1904.01557/) (2019)
- [Deep Learning for Symbolic Mathematics](https://mlsanity.com/paper/1912.01412/) (2019)
- [The Clock and the Pizza: Two Stories in Mechanistic Explanation of Neural Networks](https://mlsanity.com/paper/2306.17844/) (2023)
- [Investigating the Limitations of Transformers with Simple Arithmetic Tasks](https://mlsanity.com/paper/2102.13019/) (2021)
- [Teaching Arithmetic to Small Transformers](https://mlsanity.com/paper/2307.03381/) (2023)
- [Neural GPUs Learn Algorithms](https://mlsanity.com/paper/1511.08228/) (2015)
- [Teaching Algorithmic Reasoning via In-context Learning](https://mlsanity.com/paper/2211.09066/) (2022)
- [Neural Arithmetic Logic Units](https://mlsanity.com/paper/1808.00508/) (2018)
- [Linear algebra with transformers](https://mlsanity.com/paper/2112.01898/) (2021)
- [Symbolic Brittleness in Sequence Models: on Systematic Generalization in Symbolic Mathematics](https://mlsanity.com/paper/2109.13986/) (2021)
- [Grid Long Short-Term Memory](https://mlsanity.com/paper/1507.01526/) (2015)
- [What is my math transformer doing? -- Three results on interpretability and generalization](https://mlsanity.com/paper/2211.00170/) (2022)
- [Learning Simple Algorithms from Examples](https://mlsanity.com/paper/1511.07275/) (2015)
- [Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis](https://mlsanity.com/paper/2107.07116/) (2021)
- [Solving Math Word Problems with Double-Decoder Transformer](https://mlsanity.com/paper/1908.10924/) (2019)
- [Solving Arithmetic Word Problems with Transformers and Preprocessing of Problem Text](https://mlsanity.com/paper/2106.00893/) (2021)

## Built on by (most cited first, 30 of 33)

- [Formal Mathematical Reasoning: A New Frontier in AI](https://mlsanity.com/paper/2412.16075/) (2024)
- [Dichotomy of Early and Late Phase Implicit Biases Can Provably Induce Grokking](https://mlsanity.com/paper/2311.18817/) (2023)
- [Beyond Model Collapse: Scaling Up with Synthesized Data Requires Verification](https://mlsanity.com/paper/2406.07515/) (2024)
- [Why Do You Grok? A Theoretical Analysis of Grokking Modular Addition](https://mlsanity.com/paper/2407.12332/) (2024)
- [Opening the AI black box: program synthesis via mechanistic interpretability](https://mlsanity.com/paper/2402.05110/) (2024)
- [Transforming the Bootstrap: Using Transformers to Compute Scattering Amplitudes in Planar N = 4 Super Yang-Mills Theory](https://mlsanity.com/paper/2405.06107/) (2024)
- [Regress, Don't Guess -- A Regression-like Loss on Number Tokens for Language Models](https://mlsanity.com/paper/2411.02083/) (2024)
- [Emergent properties with repeated examples](https://mlsanity.com/paper/2410.07041/) (2024)
- [To Grok Grokking: Provable Grokking in Ridge Regression](https://mlsanity.com/paper/2601.19791/) (2026)
- [Learning to Compute Gr"obner Bases](https://mlsanity.com/paper/2311.12904/) (2023)
- [Efficient numeracy in language models through single-token number embeddings](https://mlsanity.com/paper/2510.06824/) (2025)
- [A Triumvirate of AI Driven Theoretical Discovery](https://mlsanity.com/paper/2405.19973/) (2024)
- [Clustering and Alignment: Understanding the Training Dynamics in Modular Addition](https://mlsanity.com/paper/2408.09414/) (2024)
- [Making Hard Problems Easier with Custom Data Distributions and Loss Regularization: A Case Study in Modular Arithmetic](https://mlsanity.com/paper/2410.03569/) (2024)
- [Acceleration of Grokking in Learning Arithmetic Operations via Kolmogorov-Arnold Representation](https://mlsanity.com/paper/2405.16658/) (2024)
- [Lightweight Latent Verifiers for Efficient Meta-Generation Strategies](https://mlsanity.com/paper/2504.16760/) (2025)
- [Not All Explanations for Deep Learning Phenomena Are Equally Valuable](https://mlsanity.com/paper/2506.23286/) (2025)
- [From Black Box to Bijection: Interpreting Machine Learning to Build a Zeta Map Algorithm](https://mlsanity.com/paper/2511.12421/) (2025)
- [The Long Delay to Arithmetic Generalization: When Learned Representations Outrun Behavior](https://mlsanity.com/paper/2604.13082/) (2026)
- [Transformers to Predict the Applicability of Symbolic Integration Routines](https://mlsanity.com/paper/2410.23948/) (2024)
- [Automated Software Vulnerability Static Code Analysis Using Generative Pre-Trained Transformer Models](https://mlsanity.com/paper/2408.00197/) (2024)
- [A Mechanistic Study of Transformers Training Dynamics](https://mlsanity.com/paper/2410.24050/) (2024)
- [Generating particle physics Lagrangians with transformers](https://mlsanity.com/paper/2501.09729/) (2025)
- [Studying number theory with deep learning: a case study with the M"obius and squarefree indicator functions](https://mlsanity.com/paper/2502.10335/) (2025)
- [Int2Int: a framework for mathematics with transformers](https://mlsanity.com/paper/2502.17513/) (2025)
- [Discovering Learning-Friendly Generation Orders for Sequential Computation](https://mlsanity.com/paper/2506.23875/) (2025)
- [Gradient Flow Through Diagram Expansions: Learning Regimes and Explicit Solutions](https://mlsanity.com/paper/2602.04548/) (2026)
- [Numeracy in Large Language Models: Fundamental Limitations and Paths to Improvement](https://mlsanity.com/paper/2608.13129/) (2026)
- [Identifying Sub-networks in Neural Networks via Functionally Similar Representations](https://mlsanity.com/paper/2410.16484/) (2024)
- [Learning Moderately Input-Sensitive Functions: A Case Study in QR Code Decoding](https://mlsanity.com/paper/2506.20305/) (2025)

## Abstract (arXiv)

The predictions of small transformers, trained to calculate the greatest common divisor (GCD) of two positive integers, can be fully characterized by looking at model inputs and outputs. As training proceeds, the model learns a list mathcal D of integers, products of divisors of the base used to represent integers and small primes, and predicts the largest element of mathcal D that divides both inputs. Training distributions impact performance. Models trained from uniform operands only learn a handful of GCD (up to 38 GCD ≤100). Log-uniform operands boost performance to 73 GCD ≤ 100, and a log-uniform distribution of outcomes (i.e. GCD) to 91. However, training from uniform (balanced) GCD breaks explainability.