mlsanityData to 14 Oct 2026

Learning the greatest common divisor: explaining transformer predictions

arXiv 2308.15594 ↗First posted 29 Aug 2023cs.LG cs.AIcited by 33

Not on the map. Why?

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.

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

21 of 31 references.

References · 21

  1. 2017Attention Is All You Needcited by 60,361
  2. 2014Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translationcited by 4,057
  3. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 886
  4. 2023Progress measures for grokking via mechanistic interpretabilitycited by 839
  5. 2022Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasetscited by 629
  6. 2019Analysing Mathematical Reasoning Abilities of Neural Modelscited by 335
  7. 2019Deep Learning for Symbolic Mathematicscited by 270
  8. 2023The Clock and the Pizza: Two Stories in Mechanistic Explanation of Neural Networkscited by 156
  9. 2021Investigating the Limitations of Transformers with Simple Arithmetic Taskscited by 139
  10. 2023Teaching Arithmetic to Small Transformerscited by 123
  11. 2015Neural GPUs Learn Algorithmscited by 121
  12. 2022Teaching Algorithmic Reasoning via In-context Learningcited by 112
9 more
  1. 2018Neural Arithmetic Logic Unitscited by 70
  2. 2021Linear algebra with transformerscited by 63
  3. 2021Symbolic Brittleness in Sequence Models: on Systematic Generalization in Symbolic Mathematicscited by 27
  4. 2015Grid Long Short-Term Memorycited by 20
  5. 2022What is my math transformer doing? -- Three results on interpretability and generalizationcited by 19
  6. 2015Learning Simple Algorithms from Examplescited by 12
  7. 2021Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesiscited by 9
  8. 2019Solving Math Word Problems with Double-Decoder Transformercited by 7
  9. 2021Solving Arithmetic Word Problems with Transformers and Preprocessing of Problem Textcited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 2; 2024: 15; 2025: 10; 2026: 6.

33 papers.

Sort:

By area:

  1. 2024Formal Mathematical Reasoning: A New Frontier in AIcited by 81
  2. 2023Dichotomy of Early and Late Phase Implicit Biases Can Provably Induce Grokkingcited by 80
  3. 2024Beyond Model Collapse: Scaling Up with Synthesized Data Requires Verificationcited by 45
  4. 2024Why Do You Grok? A Theoretical Analysis of Grokking Modular Additioncited by 36
  5. 2024Opening the AI black box: program synthesis via mechanistic interpretabilitycited by 20
  6. 2024Transforming the Bootstrap: Using Transformers to Compute Scattering Amplitudes in Planar N = 4 Super Yang-Mills Theorycited by 18
  7. 2024Regress, Don't Guess -- A Regression-like Loss on Number Tokens for Language Modelscited by 13
  8. 2024Emergent properties with repeated examplescited by 11
  9. 2026To Grok Grokking: Provable Grokking in Ridge Regressioncited by 8
  10. 2023Learning to Compute Gr"obner Basescited by 7
  11. 2025Efficient numeracy in language models through single-token number embeddingscited by 7
  12. 2024A Triumvirate of AI Driven Theoretical Discoverycited by 5
21 more
  1. 2024Clustering and Alignment: Understanding the Training Dynamics in Modular Additioncited by 5
  2. 2024Making Hard Problems Easier with Custom Data Distributions and Loss Regularization: A Case Study in Modular Arithmeticcited by 4
  3. 2024Acceleration of Grokking in Learning Arithmetic Operations via Kolmogorov-Arnold Representationcited by 3
  4. 2025Lightweight Latent Verifiers for Efficient Meta-Generation Strategiescited by 3
  5. 2025Not All Explanations for Deep Learning Phenomena Are Equally Valuablecited by 3
  6. 2025From Black Box to Bijection: Interpreting Machine Learning to Build a Zeta Map Algorithmcited by 3
  7. 2026The Long Delay to Arithmetic Generalization: When Learned Representations Outrun Behaviorcited by 3
  8. 2024Transformers to Predict the Applicability of Symbolic Integration Routinescited by 2
  9. 2024Automated Software Vulnerability Static Code Analysis Using Generative Pre-Trained Transformer Modelscited by 1
  10. 2024A Mechanistic Study of Transformers Training Dynamicscited by 1
  11. 2025Generating particle physics Lagrangians with transformerscited by 1
  12. 2025Studying number theory with deep learning: a case study with the M"obius and squarefree indicator functionscited by 1
  13. 2025Int2Int: a framework for mathematics with transformerscited by 1
  14. 2025Discovering Learning-Friendly Generation Orders for Sequential Computationcited by 1
  15. 2026Gradient Flow Through Diagram Expansions: Learning Regimes and Explicit Solutionscited by 1
  16. 2026Numeracy in Large Language Models: Fundamental Limitations and Paths to Improvementcited by 1
  17. 2024Identifying Sub-networks in Neural Networks via Functionally Similar Representationscited by 0
  18. 2025Learning Moderately Input-Sensitive Functions: A Case Study in QR Code Decodingcited by 0
  19. 2025Learning Modular Exponentiation with Transformerscited by 0
  20. 2026Slower Generalization, Faster Memorization: A Sweet Spot in Algorithmic Learningcited by 0
  21. 2026Learning First Integrals via Backward-Generated Data and Guided Reinforcement Learningcited by 0