🤖 machine learning

The Discrete-Log Clock: How a Transformer Learns Modular Multiplication

This paper demonstrates that the apparent complexity of transformers learning modular multiplication is an artifact of using the wrong analytical basis, revealing that they actually implement a sparse, interpretable "Discrete-Log Clock" algorithm by reducing multiplication to addition in the space of multiplicative characters.

Original authors: Huu Danh Nguyen (Stanford University)

Published 2026-06-17

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Huu Danh Nguyen (Stanford University)

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Mystery: Why Was the AI "Confused"?

Imagine you are trying to teach a robot to do math. Specifically, you want it to learn modular multiplication (multiplying two numbers and keeping only the remainder when divided by a specific number, like 113).

For a long time, scientists noticed something strange. When the robot finally "figured it out" (a phenomenon called grokking, where it suddenly goes from memorizing answers to understanding the rule), the internal math looked messy.

The Old View: When scientists looked at the robot's brain using standard tools, they saw a "dense" mess. It looked like the robot was using every single possible frequency of sound to solve the problem. It seemed chaotic and hard to understand, unlike how it solved simple addition, which looked neat and organized.
The Problem: The scientists were looking at the robot's brain through the wrong pair of glasses. They were using a "standard ruler" designed for addition, but the robot was actually doing multiplication.

The Solution: Changing the Lens

The authors of this paper realized that to understand multiplication, you have to stop looking at the numbers as they are (1, 2, 3...) and start looking at them as powers of a generator.

Think of it like this:

The Standard View (Additive): Imagine a clock face with numbers 1 to 12. If you add 1, you move one step. This is easy to see.
The Hidden View (Multiplicative): Now, imagine the numbers on the clock are scrambled. The number "1" is actually a "3," the number "2" is a "9," and so on. In this scrambled world, multiplication actually works exactly like addition.

The paper calls this the "Discrete-Log Clock." It's a secret code where the messy multiplication problem transforms into a simple addition problem.

What They Found (The "Aha!" Moment)

When the researchers re-examined the robot's brain using this new "scrambled" lens (which they call the multiplicative character transform), the chaos vanished.

The Noise Became a Signal: Instead of seeing a messy "dense" spectrum, they saw a very clean, sparse pattern. The robot wasn't using all frequencies; it was only using 4 specific frequencies to do the math. It was like finding a single, clear melody in a room full of static noise.
The Neurons Got Organized: The robot has thousands of tiny processing units (neurons). In the old view, they looked random. In the new view, 97% of them were perfectly tuned to just one of those 4 frequencies. They were like a choir where every singer knows exactly which note to hit.
The Pattern Emerged: When they rearranged the data based on this secret code, the robot's internal activity formed perfect diagonal stripes. This proved the robot had learned a specific trick:
- Step 1: Convert the numbers into their "secret code" (discrete logs).
- Step 2: Add the codes together (just like normal addition).
- Step 3: Convert the result back to the normal number.

The "Clock" Analogy

The paper compares this to a famous "Clock Algorithm" used for addition.

For Addition: The robot learns to rotate a clock hand.
For Multiplication: The robot learns to rotate a different kind of clock (the Discrete-Log Clock). Once it rotates the hand on this special clock, the answer is right there.

Why Did Previous Scientists Miss This?

Imagine you are trying to listen to a song, but you are wearing noise-canceling headphones that only let in the bass. You hear a thumping, messy sound and conclude, "This song is just noise."

The previous researchers were wearing those "headphones" (the standard math tools). They saw the "thumping" (dense spectrum) and thought the robot was using a complex, unexplainable method. The authors simply took the headphones off, switched to the right frequency, and realized the robot was actually playing a beautiful, simple melody.

The Takeaway

The main lesson of this paper isn't just about math; it's about how we look at things.

The Lesson: If you are trying to understand a complex system (like an AI or a group of people), make sure you are using the right "language" or "basis" for the task.
The Result: When you match your analysis tool to the actual structure of the problem (in this case, using the "multiplicative" lens for multiplication), the messy, unexplainable noise turns into a clear, simple, and understandable algorithm.

The robot didn't invent a new, mysterious way to do math. It just found the secret code that turns a hard problem into an easy one, and the researchers finally figured out how to read that code.

Technical Summary: The Discrete-Log Clock

Problem Statement
While the internal mechanisms of transformers learning modular addition ( $a + b \mod p$ ) have been fully reverse-engineered as sparse Fourier representations (the "Clock" algorithm), the mechanism for modular multiplication ( $a \cdot b \mod p$ ) has remained elusive. Prior empirical studies (Doshi et al., 2024; Furuta et al., 2024) reported that transformers trained on multiplication learn "dense" Fourier spectra requiring all frequencies, contrasting sharply with the sparse structure found in addition. This suggested multiplication might rely on a fundamentally different, less interpretable algorithm.

Methodology
The authors train a 1-layer decoder-only transformer to predict $a \cdot b \mod 113$ for inputs $a, b \in \{1, \dots, 112\}$ . The model is trained on 30% of the data and must generalize to the remaining 70%, exhibiting the "grokking" phenomenon where generalization occurs suddenly after a long period of memorization.

The core methodological innovation is a shift in the analysis basis. Instead of applying the standard additive Discrete Fourier Transform (DFT) to the token embeddings, the authors apply the multiplicative character transform. This involves:

Recognizing that the nonzero integers modulo a prime $p$ form a cyclic group $(\mathbb{Z}/p\mathbb{Z})^*$ .
Using a primitive root $g$ (here $g=3$ ) to map inputs to their discrete logarithms: $\alpha = \log_g(a)$ and $\beta = \log_g(b)$ .
Reordering the embedding matrix rows according to these discrete logarithms.
Applying the standard DFT to this reordered data.

This approach leverages the group isomorphism where multiplication in the original space corresponds to addition in the discrete-log space ( $a \cdot b \equiv g^{\alpha + \beta} \mod p$ ).

Key Results

Spectral Sparsity: When analyzed in the additive basis, the embedding spectrum appears flat and dense (Gini coefficient 0.07). However, in the multiplicative character basis, the spectrum becomes highly sparse (Gini coefficient 0.58), with energy concentrated in only 4 key frequencies ( $\{2, 8, 47, 56\}$ ).
Neuron Tuning: In the multiplicative basis, 96.9% (496/512) of the MLP neurons are "cleanly tuned" to a single frequency, with over 85% of their activation energy concentrated there. In the additive basis, zero neurons meet this threshold.
Structural Visualization: When neuron activation heatmaps are reordered by discrete logarithm, they reveal clear 2D-periodic diagonal stripes. This indicates the neurons compute functions of the form $\cos(k(\alpha + \beta))$ , effectively performing addition in the log-space.
SVD Analysis: Principal components of the embedding matrix, when reordered by discrete logarithm, exhibit clear sinusoidal structures, confirming the encoding of multiplicative characters.

The "Discrete-Log Clock" Algorithm
The paper concludes that the transformer implements an algorithm analogous to the "Clock" algorithm for addition, termed the Discrete-Log Clock. The mechanism proceeds as follows:

Embedding: Integers are embedded as sinusoidal functions of their discrete logarithms.
Routing: Attention mechanisms route these embeddings to the output position.
Composition: The MLP applies trigonometric identities to compute sums of the discrete logs (effectively adding $\alpha + \beta$ ).
Decoding: The model scores candidate outputs by aligning them with the computed sum in log-space, where the correct answer achieves constructive interference across the key frequencies.

Significance and Claims
The primary contribution is demonstrating that the "dense spectrum" observed in prior work is an artifact of analyzing the data in the wrong basis, not a reflection of algorithmic complexity. By matching the analysis basis to the algebraic structure of the task (the multiplicative group), the authors reveal that multiplication is reduced to addition in discrete-log space.

The paper claims this methodology generalizes:

The sparse multiplicative spectrum was confirmed across 10 different primes ( $p=59$ to $113$).
The mechanism is universal across random seeds (approx. 80% of seeds).
Preliminary results suggest the approach extends to modular exponentiation ( $a^b \mod p$ ) using a 2-layer transformer.

The authors emphasize that for any algebraic task, applying the Fourier transform on the relevant group (rather than the standard additive DFT) is essential for revealing interpretable structure where standard tools previously saw noise.