The geometric structure hidden in addition mod p
Prerequisites: Key Concepts for Newcomers
Before diving in, let’s establish clear definitions for readers unfamiliar with machine learning or modular arithmetic.
What is Modular Addition?
Modular addition is “clock arithmetic.” When numbers reach a limit, they wrap around to zero.
Think of a clock face with 12 hours. If it’s 10 o’clock and you add 5 hours, you don’t get 15 o’clock — you get 3 o’clock. The numbers “wrap around” when they hit 12.
Regular addition: 10 + 5 = 15 Clock arithmetic: 10 + 5 = 3 (mod 12)
In mathematical notation, we write a + b mod p to mean:
- Add a and b normally
- Divide by p
- Keep only the remainder
Examples with mod 5 (imagine a clock with only 5 hours: 0, 1, 2, 3, 4):
1 + 2 = 3 mod 5 (3 < 5, no wrapping) 3 + 4 = 2 mod 5 (3 + 4 = 7, and 7 = 5 + 2, so remainder is 2) 4 + 4 = 3 mod 5 (8 = 5 + 3, remainder is 3) 2 + 3 = 0 mod 5 (5 = 5 + 0, remainder is 0)
The key insight: modular arithmetic is cyclic. The numbers form a circle, and addition means rotating around that circle.
Machine Learning Terminology
Training a neural network means adjusting its internal numbers until it produces correct outputs.
Weights: The adjustable numbers inside a neural network. Think of weights as “knobs” the network can turn. Each knob affects how the network processes information. A network might have millions of these knobs, and training means finding the right settings.
Training loss: A number measuring how wrong the network’s answers are. Lower is better. If the network predicts “7” when the answer is “3”, the loss increases. The goal of training is to minimize this loss.
Overfitting: When a network memorizes specific training examples instead of learning general patterns. Like a student who memorizes “the answer to question 1 is C” instead of understanding the material — they ace the practice test but fail the real exam with different questions.
Regularization: Techniques that discourage overfitting. Weight decay is one type: it penalizes large weight values, encouraging simpler solutions. Think of it as a “simplicity tax” — the network pays a cost for complexity, pushing it toward elegant solutions that generalize.
MLP (Multi-Layer Perceptron): The “thinking” part of a neural network. An MLP is a stack of layers where each layer is a collection of neurons (also called perceptrons). Each neuron does three things:
- Takes a weighted sum of its inputs (multiply each input by a weight, add them up)
- Adds a bias (a constant offset)
- Applies a nonlinear function (like ReLU, which zeroes out negative values)
SINGLE NEURON (PERCEPTRON)
═══════════════════════════════════════════════════════════════
Inputs Weights Sum + Bias Nonlinearity Output
x₁ ──────────── w₁ ─────╲
╲
x₂ ──────────── w₂ ───────●────→ Σ + b ────→ ReLU ────→ y
╱
x₃ ──────────── w₃ ─────╱
y = ReLU(w₁x₁ + w₂x₂ + w₃x₃ + b)
ReLU(z) = max(0, z) ← outputs z if positive, else 0
An MLP stacks many neurons into layers, and stacks multiple layers deep:
MLP ARCHITECTURE
═══════════════════════════════════════════════════════════════
Input Hidden Layer 1 Hidden Layer 2 Output
Layer (many neurons) (many neurons) Layer
●─────────────● ●─────────────●
╲ ╱
●───────────────●─────────────────●───────────────●
╱ ╲ ╱ ╲
●─────────────●───●─────────────●───●─────────────●
╲ ╱ ╲ ╱
●───────────────●─────────────────●───────────────●
╱ ╲
●─────────────● ●─────────────●
Each arrow represents a learnable weight.
"Deep learning" = many hidden layers.
The magic: by stacking enough neurons with nonlinearities, an MLP can learn to compute almost ANY function — including trigonometric identities!
Big-O Notation: How Algorithms Scale
Big-O notation describes how an algorithm’s running time grows as the input size increases. It answers: “If I double the input, how much longer does this take?”
BIG-O NOTATION — COMMON GROWTH RATES
═══════════════════════════════════════════════════════════════
O(1) Constant Same time regardless of input size
Example: Looking up an item by index in an array
O(log N) Logarithmic Doubling input adds fixed amount of work
Example: Binary search (halving the search space each step)
O(N) Linear Doubling input doubles the work
Example: Scanning through a list once
O(N log N) Log-linear Slightly worse than linear
Example: Fast sorting algorithms (merge sort, quicksort)
O(N²) Quadratic Doubling input quadruples the work
Example: Comparing every pair of items (nested loops)
O(2^N) Exponential Adding one item doubles the work
Example: Checking all subsets of a set
VISUALIZING GROWTH (time vs. input size N):
Time │ · O(N²)
│ ·
│ ·
│ ·
│ · ···· O(N log N)
│ · ····
│ · ····
│ · ···· ________ O(N)
│ · ··· _______
│ · ··· _____
│ · · ··· ______ ............ O(log N)
│ · ··· _____.............................
│····____........................................ O(1)
└─────────────────────────────────────────────────→ N
Why it matters for this paper: When we say the Quantum Fourier Transform runs in O((log N)²) vs. classical DFT’s O(N²), we mean:
- Classical: 1000 points → 1,000,000 operations
- Quantum: 1000 points → 100 operations (since log₂(1000) ≈ 10)
That’s a 10,000× speedup — and the gap grows exponentially with N!
Who Was Fourier?
Jean-Baptiste Joseph Fourier (1768–1830) was a French mathematician and physicist. His life spanned the French Revolution (he was nearly guillotined twice), Napoleon’s Egyptian campaign (where he helped establish the Institut d’Égypte), and the restoration of the monarchy.
The Big Discovery (1807): While studying how heat flows through solid objects, Fourier made a revolutionary claim: any periodic function, no matter how jagged or irregular, can be written as a sum of smooth sine and cosine waves.
FOURIER'S INSIGHT
═══════════════════════════════════════════════════════════════
Any periodic signal: Can be decomposed into:
╱╲ ╱╲ ∿∿∿∿∿∿ (slow wave)
╱ ╲ ╱ ╲ + ∿∿∿∿∿∿∿∿ (medium wave)
╱ ╲ ╱ ╲ + ∿∿∿∿∿∿∿∿∿∿ (fast wave)
╱ ╲╱ ╲ + ...
"Square wave" = Sum of sine waves at
frequencies 1, 3, 5, 7, ...
Timeline:
- 1807: Fourier presents his ideas to the French Academy (rejected as not rigorous enough!)
- 1822: Publishes Théorie analytique de la chaleur (Analytical Theory of Heat)
- 1820s-present: Fourier’s methods become essential to physics, engineering, signal processing, and now… neural networks
Fourier Series vs. Fourier Transform:
- Fourier Series (1807): Decomposes periodic signals (signals that repeat forever)
- Fourier Transform (developed later): Extends the idea to non-periodic signals
- Discrete Fourier Transform (DFT): Version for finite lists of numbers (what computers use)
The neural network in grokking rediscovers Fourier’s 200-year-old insight: cyclic patterns are naturally expressed as sums of waves!
What is a Fourier Transform?
The Fourier transform is a mathematical tool that decomposes signals into their component frequencies — like separating white light into a rainbow.
The Core Idea: Any pattern, no matter how complex, can be built by adding together simple waves (sine and cosine curves) of different frequencies.
Complex signal = (slow wave) + (medium wave) + (fast wave) + ...
Why “frequencies”? Imagine a sound wave. A pure musical note is a simple sine wave. A chord is multiple notes (frequencies) added together. The Fourier transform tells you which notes make up the chord.
Sine and Cosine: The Building Blocks
Before we go further, let’s visualize the two fundamental waves:
SINE AND COSINE WAVES (one complete cycle, 0° to 360°)
═══════════════════════════════════════════════════════════════════════════
cos(θ) sin(θ)
│ │
1 │ ╭───╮ 1 │ ╭───╮
│ ╱ ╲ │ ╱ ╲
│ ╱ ╲ │ ╱ ╲
0 ───┼─╱─────────╲───────── and 0 ────┼──────╱─────────╲──────
│╱ ╲ ╱ │ ╱ ╲ ╱
│ ╲ ╱ │ ╱ ╲ ╱
-1 │ ╰───╯ -1 │ ╱ ╰─╯
└──────────────────────→ θ └──────────────────────→ θ
0° 90° 180° 270° 360° 0° 90° 180° 270° 360°
starts at 1 starts at 0
peak at 0° peak at 90°
Key observation: Cosine and sine are the SAME wave, just shifted by 90°!
BOTH WAVES TOGETHER — Cosine leads Sine by 90°
═══════════════════════════════════════════════════════════════════════════
1 │ C S
│ ╱ ╲ ╲ ╱ ╲
│ ╱ ╲ ╲ ╱ ╲
│ ╱ ╲ ╲ ╱ ╲
0 ├─╱───────╲────╲─────────────────────────╱───────╲─────────
│╱ ╲ ╲ ╱ ╲ ╱
│ ╲ ╲ ╱ ╲ ╱
-1 │ ╲ S C ╲──╱
└─────────────────────────────────────────────────────────→ θ
0° 90° 180° 270° 360°
C = cos(θ) ─── (solid)
S = sin(θ) - - (dashed)
At θ=0°: cos=1, sin=0 ← cosine at peak, sine at zero
At θ=90°: cos=0, sin=1 ← cosine at zero, sine at peak
At θ=180°: cos=-1, sin=0 ← cosine at trough, sine at zero
At θ=270°: cos=0, sin=-1 ← cosine at zero, sine at trough
This 90° phase relationship is crucial — it means cos and sin together can describe ANY point on a circle!
The Unit Circle: Where Sine and Cosine Live
Now here’s the beautiful connection. Instead of plotting waves over time, plot them as coordinates:
THE UNIT CIRCLE — cos(θ) is the x-coordinate, sin(θ) is the y-coordinate
═══════════════════════════════════════════════════════════════════════════
90° (π/2)
sin(θ) = 1
│
│ • Point at angle θ
╭───┼───╮ /
╱ │ ╲
╱ │ / ╲
╱ │ / ╲
│ │ / │
180° (π) ─────────┼─────────●─/──────┼───────── 0° (0)
cos(θ) = -1 │ │╱ │ cos(θ) = 1
│ │ │
╲ │ ╱
╲ │ ╱
╲ │ ╱
╰───┼───╯
│
sin(θ) = -1
270° (3π/2)
Any point on the circle: (cos θ, sin θ)
θ = 0°: (1, 0) ← rightmost point
θ = 90°: (0, 1) ← top
θ = 180°: (-1, 0) ← leftmost point
θ = 270°: (0, -1) ← bottom
θ = 45°: (0.71, 0.71) ← diagonal
The profound insight: A point moving around the circle at constant speed traces out BOTH sine and cosine waves simultaneously — one for each coordinate!
Understanding ‘i’ — The Imaginary Unit
Now we need to talk about i, the imaginary unit. Don’t let the name fool you — it’s completely real and essential.
The problem: What number, when squared, gives -1?
- 1² = 1 (not -1)
- (-1)² = 1 (not -1)
- No “regular” number works!
The solution: Define a new number i such that:
i² = −1
or equivalently: i = √(−1)
What IS i, really? Think of it as a 90° rotation operator:
- Multiply by i once: rotate 90° counterclockwise
- Multiply by i twice: rotate 180° (that’s i² = -1, which flips sign!)
- Multiply by i three times: rotate 270°
- Multiply by i four times: rotate 360° (back to start, i⁴ = 1)
POWERS OF i — Rotation in the Complex Plane
═══════════════════════════════════════════════════════════════════════════
i
│
│ i¹ = i (90° rotation)
│
│
i² = -1 ──────────────┼────────────── i⁰ = 1
(180°) │ (0° / 360°)
│
│
│ i³ = -i (270° rotation)
-i
i⁴ = 1 (full circle, back to start!)
Complex numbers: Combine real and imaginary parts:
z = a + bi
where a is the “real part” (x-coordinate) and b is the “imaginary part” (y-coordinate).
This gives us the complex plane — a 2D space where every point is a number!
Understanding ‘e’ — Euler’s Number
e ≈ 2.71828… is a special number that appears everywhere in mathematics, especially involving growth and change.
What makes e special? It’s the unique number where the rate of growth equals the current value. If you have e^x, its derivative (rate of change) is also e^x. No other base has this property!
Euler’s Formula — The Most Beautiful Equation
Leonhard Euler discovered an astonishing connection:
e^(iθ) = cos(θ) + i·sin(θ)
This says: raising e to an imaginary power gives you a point on the unit circle!
EULER'S FORMULA VISUALIZED
═══════════════════════════════════════════════════════════════════════════
e^(iθ) = cos(θ) + i·sin(θ)
═══════════════════════════
Imaginary axis
│
│ • e^(iθ)
sin(θ) /│
│ / │
│ / │
│ / │
│ / θ │
Real axis ──────────────────┼──●─────┴────────
│ └─────┘
│ cos(θ)
│
The point e^(iθ) sits on the unit circle at angle θ
Its coordinates are (cos θ, sin θ)
Special cases:
e^(i·0) = 1 (angle 0°, point (1,0))
e^(iπ/2) = i (angle 90°, point (0,1))
e^(iπ) = -1 (angle 180°, point (-1,0)) ← Euler's identity!
e^(i·3π/2) = -i (angle 270°, point (0,-1))
e^(i·2π) = 1 (angle 360°, back to start)
Why does this matter? Multiplication of complex exponentials ADDS their angles:
e^(iθ₁) × e^(iθ₂) = e^(i(θ₁ + θ₂))
This is why the Fourier representation makes modular addition simple — addition of numbers becomes addition of angles!
The Discrete Fourier Transform (DFT)
Now we can understand the DFT. It works with finite lists of numbers, expressing them using p different frequencies:
Original: [a₀, a₁, a₂, ..., a_{p-1}]
↓ Fourier Transform
Frequencies: [F₀, F₁, F₂, ..., F_{p-1}]
Each frequency component F_k corresponds to a wave that completes k full cycles as you go around the p points.
Why does this matter for grokking? The neural network discovers that modular addition becomes simple in the Fourier basis. In the original representation (raw numbers), addition mod p seems arbitrary. In the Fourier representation (points on a circle), addition is just rotation — geometrically natural.
The Unit Circle Connection: Roots of Unity
The DFT uses the roots of unity — p equally-spaced points on the unit circle in the complex plane.
For mod 5, we need the 5th roots of unity: numbers that give 1 when raised to the 5th power.
These are: ωᵏ = e^(2πik/5) for k = 0, 1, 2, 3, 4
THE 5TH ROOTS OF UNITY — A Regular Pentagon on the Unit Circle
═══════════════════════════════════════════════════════════════════════════
ω⁰ = 1
(0°)
●
╱ ╲
╱ ╲
╱ ╲
ω¹ ╱ ╲ ω⁴
(72°) ● ● (288°)
╲ ╱
╲ ╱
╲ ╱
╲ ╱
╲ ╱
ω² ●───────● ω³
(144°) (216°)
Position Angle Euler Form Coordinates (cos, sin)
─────────────────────────────────────────────────────────────────────
0 0° e^(0) = 1 ( 1.000, 0.000)
1 72° e^(2πi/5) ( 0.309, 0.951)
2 144° e^(4πi/5) (-0.809, 0.588)
3 216° e^(6πi/5) (-0.809, -0.588)
4 288° e^(8πi/5) ( 0.309, -0.951)
─────────────────────────────────────────────────────────────────────
Key property: ω⁵ = e^(2πi·5/5) = e^(2πi) = 1 (back to start!)
This is why it's called "mod 5" — after 5 steps, you return to the beginning.
Addition as Rotation
Here’s the magic: adding numbers mod 5 = adding angles = rotating around the pentagon!
EXAMPLE: 1 + 3 = 4 (mod 5) as Rotation
═══════════════════════════════════════════════════════════════════════════
Start at position 1 (angle 72°): Add 3 (rotate by 216°):
0 0
● ●
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
● ● ● ●
1 ←(START) 4 1 4 ←(END)
╲ ╱ ╲ ╱
╲ ╱ ╲ ╱
2───3 2───3
↑
(rotate through
positions 2, 3)
Angle calculation:
Position 1: θ₁ = 72°
Position 3: θ₃ = 216° (this is the "amount" we rotate by)
Sum: θ₁ + θ₃ = 72° + 216° = 288° = position 4 ✓
Complex multiplication:
e^(2πi·1/5) × e^(2πi·3/5) = e^(2πi·4/5)
(position 1) (position 3) (position 4)
The network discovers this! Instead of memorizing a 5×5 addition table, it learns:
- Place each number at its angle on the circle (embedding)
- Add the angles using trig identities (MLP)
- Read off which position the result lands on (unembedding)
HOW THE MLP ADDS ANGLES — Trig Identity Example for 1 + 3 mod 5
═══════════════════════════════════════════════════════════════════════════
The MLP doesn't know about angles directly. It only sees coordinates:
Input 1: embed(1) = (cos 72°, sin 72°) = ( 0.309, 0.951)
Input 3: embed(3) = (cos 216°, sin 216°) = (-0.809, -0.588)
The MLP neurons learn to compute these PRODUCTS:
┌─────────────────────────────────────────────────────────────────┐
│ cos(72°) × cos(216°) = (0.309) × (-0.809) = -0.250 │
│ sin(72°) × sin(216°) = (0.951) × (-0.588) = -0.559 │
│ sin(72°) × cos(216°) = (0.951) × (-0.809) = -0.769 │
│ cos(72°) × sin(216°) = (0.309) × (-0.588) = -0.182 │
└─────────────────────────────────────────────────────────────────┘
│
▼
Then COMBINE them using the trig addition formulas:
┌─────────────────────────────────────────────────────────────────┐
│ │
│ cos(72° + 216°) = cos(72°)cos(216°) − sin(72°)sin(216°) │
│ = (-0.250) − (-0.559) │
│ = -0.250 + 0.559 │
│ = 0.309 ✓ │
│ │
│ sin(72° + 216°) = sin(72°)cos(216°) + cos(72°)sin(216°) │
│ = (-0.769) + (-0.182) │
│ = -0.951 ✓ │
│ │
└─────────────────────────────────────────────────────────────────┘
│
▼
Output: (0.309, -0.951)
│
▼
This matches position 4 on the pentagon!
(cos 288°, sin 288°) = (0.309, -0.951) ✓
═══════════════════════════════════════════════════════════════════════════
The KEY INSIGHT: The MLP neurons don't "know" trigonometry.
They just learn weights that HAPPEN to implement these formulas
because that's the simplest way to solve the task!
Memorizing all 25 input-output pairs: requires ~25 "slots" of memory
Learning the Fourier trick: requires ~4 neurons (for the products)
Weight decay penalizes complexity → network finds the elegant solution.
Part I: The Discovery of Grokking
The OpenAI Observation (2022)
Alethea Power and colleagues at OpenAI were training small transformer networks on simple algorithmic tasks: modular addition, modular division, permutation composition.
They noticed something bizarre.
The networks would quickly memorize the training data — loss drops to near zero, training accuracy hits 100%. Standard machine learning says: stop training, you’re done.
But they kept training. For thousands more epochs, nothing happened. Test accuracy stayed at chance level. The network had memorized, not generalized.
Then, suddenly — sometimes after 10,000+ epochs — test accuracy shot from ~0% to ~100% in just a few hundred steps.
They called this grokking: a sudden transition from memorization to generalization, long after the training data was perfectly fit.
Why “Grokking”?
The term comes from Robert Heinlein’s Stranger in a Strange Land (1961). To “grok” means to understand something so thoroughly that you become one with it.
The network doesn’t just memorize — it groks the underlying structure.
The Key Conditions
Grokking requires:
- Small dataset: Large datasets don’t overfit completely
- Weight decay: Regularization that penalizes large weights
- Sufficient training time: Far beyond when training loss saturates
- Algorithmic task: Problems with underlying structure to discover
Without weight decay, grokking rarely occurs. The network happily stays in its memorizing solution forever.
Part II: What’s Inside the Network?
The Architecture
The standard setup for studying grokking on modular arithmetic:
Input: (a, b) as one-hot vectors
↓
Embedding layer: one-hot → dense vectors
↓
Transformer block(s): attention + MLP
↓
Output: logits over {0, 1, ..., p-1}
For a + b mod p, the inputs are two integers, the output is their sum modulo p.
Detailed Architecture Diagram: Computing 1 + 3 mod 5
═══════════════════════════════════════════════════════════════════════════════════
NEURAL NETWORK FOR MODULAR ADDITION
═══════════════════════════════════════════════════════════════════════════════════
INPUT EMBEDDING ATTENTION MLP
(One-Hot) (Unit Circle) (Information (Perceptrons) UNEMBEDDING
Flow) (Output)
┌─────────────┐ ┌─────────────┐ ┌───────────┐ ┌─────────────┐ ┌─────────┐
│ a=1 b=3 │ │ Position │ │ │ │ Trig │ │ Logits │
│ │ │ on Circle │ │ Combine │ │ Identity │ │ │
├──┬──┬──┬────┤ ├─────────────┤ │ a and b │ │ Neurons │ ├─────────┤
│0 │1 │OP│ 0 │ │ •1 │ │ │ │ │ │ 0: 0.1 │
├──┼──┼──┼────┤ ══> │ · · │ ══> │ Q K V │ ══> │ cos×cos │ ══> ├─────────┤
│1 │0 │ │ 0 │ │ 0• •2 │ │ ↓ ↓ ↓ │ │ sin×sin │ │ 1: 0.2 │
├──┼──┼──┼────┤ │ · · │ │ Attend │ │ cos×sin │ ├─────────┤
│0 │0 │ │ 0 │ │ •4 │ │ │ │ sin×cos │ │ 2: 0.1 │
├──┼──┼──┼────┤ │ 3• │ │ ↓ │ │ ↓ │ ├─────────┤
│0 │0 │ │ 1 │ ├─────────────┤ │ Output │ │ Combine │ │ 3: 0.1 │
├──┼──┼──┼────┤ │ embed(1)= │ │ [e₁,e₃] │ │ with ± │ ├─────────┤
│0 │0 │ │ 0 │ │(0.31, 0.95) │ │ │ │ ↓ │ │ 4: 0.5 │◄── MAX
├──┼──┼──┼────┤ │ embed(3)= │ └───────────┘ │ (cos,sin) │ └─────────┘
│ │ │+ │ │ │(-0.81,-0.59)│ │ of sum │ ↓
└──┴──┴──┴────┘ └─────────────┘ └─────────────┘ Answer: 4
═══════════
Col: a b OP b 72° and For simple Result:
(one-hot) (one-hot) 216° on addition, (0.31, -0.95)
pentagon attention is = position 4
minimal
═══════════════════════════════════════════════════════════════════════════════════
DATA TRANSFORMATION DETAIL
═══════════════════════════════════════════════════════════════════════════════════
STEP 1: ONE-HOT INPUT MATRIX (5 rows × 3 columns)
┌────────────────────────────────────────┐
│ │ Input a │ OP │ Input b │
│ │ (=1) │ (+) │ (=3) │
├─────────┼───────────┼────────┼─────────┤
│ Row 0 │ 0 │ 0 │ 0 │
│ Row 1 │ 1 ◄──│────────│─── a=1 │
│ Row 2 │ 0 │ 0 │ 0 │
│ Row 3 │ 0 │ 0 │ 1 ◄──│── b=3
│ Row 4 │ 0 │ 0 │ 0 │
│ Row 5 │ 0 │ 1 ◄──│─── "+" │ (operation token)
└─────────┴───────────┴────────┴─────────┘
STEP 2: EMBEDDING — Map to Unit Circle (p=5 Pentagon)
┌─────────────────────────────────────────────────────────────────┐
│ │
│ 0 (0°) │
│ • │
│ · · │
│ · · │
│ 1 (72°) • • 4 (288°) ◄── Answer! │
│ · · │
│ · · │
│ 2 (144°) • · • 3 (216°) │
│ │
│ embed(1) = (cos 72°, sin 72°) = ( 0.309, 0.951) │
│ embed(3) = (cos 216°, sin 216°) = (-0.809, -0.588) │
│ │
└─────────────────────────────────────────────────────────────────┘
STEP 3: ATTENTION — Combine Position Information
┌─────────────────────────────────────────────────────────────────┐
│ │
│ Query (Q), Key (K), Value (V) projections: │
│ │
│ Position 1 (input a): Q₁, K₁, V₁ from embed(1) │
│ Position 2 (input b): Q₂, K₂, V₂ from embed(3) │
│ │
│ Attention weights: softmax(Q·Kᵀ/√d) │
│ │
│ For modular addition, attention mainly copies/moves │
│ information — the "computation" happens in the MLP. │
│ │
│ Output: Combined representation [e₁ ; e₃] or mixture │
│ │
└─────────────────────────────────────────────────────────────────┘
STEP 4: MLP (Multi-Layer Perceptron) — The "Perceptrons"
┌─────────────────────────────────────────────────────────────────┐
│ │
│ Hidden layer neurons learn trig products: │
│ │
│ ┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐ │
│ │ cos(a) │ │ sin(a) │ │ cos(b) │ │ sin(b) │ │
│ │ ×cos(b) │ │ ×sin(b) │ │ ×sin(a) │ │ ×cos(a) │ │
│ │ = -0.25 │ │ = -0.56 │ │ = -0.77 │ │ = -0.18 │ │
│ └────┬─────┘ └────┬─────┘ └────┬─────┘ └────┬─────┘ │
│ │ │ │ │ │
│ └───────┬───────┘ └───────┬───────┘ │
│ ↓ ↓ │
│ cos(a+b) = cos(a)cos(b) - sin(a)sin(b) = 0.309 │
│ sin(a+b) = sin(a)cos(b) + cos(a)sin(b) = -0.951 │
│ │
│ Output: (0.309, -0.951) = coordinates of position 4 │
│ │
└─────────────────────────────────────────────────────────────────┘
STEP 5: UNEMBEDDING — Read Off the Answer
┌─────────────────────────────────────────────────────────────────┐
│ │
│ Compare MLP output to each position's embedding: │
│ │
│ MLP output: (0.309, -0.951) │
│ │
│ ┌─────────┬─────────────────────┬──────────────┐ │
│ │ Answer │ Embedding │ Match? │ │
│ ├─────────┼─────────────────────┼──────────────┤ │
│ │ 0 │ ( 1.000, 0.000) │ ✗ │ │
│ │ 1 │ ( 0.309, 0.951) │ ✗ │ │
│ │ 2 │ (-0.809, 0.588) │ ✗ │ │
│ │ 3 │ (-0.809, -0.588) │ ✗ │ │
│ │ 4 │ ( 0.309, -0.951) │ ✓ MATCH │◄── Output │
│ └─────────┴─────────────────────┴──────────────┘ │
│ │
│ Final output: argmax(logits) = 4 │
│ │
│ 1 + 3 = 4 mod 5 ✓ │
│ │
└─────────────────────────────────────────────────────────────────┘
═══════════════════════════════════════════════════════════════════════════════════
Neel Nanda’s Mechanistic Interpretability (2023)
Neel Nanda and colleagues opened up trained networks to see how they compute modular addition. Their paper “Progress Measures for Grokking via Mechanistic Interpretability” revealed the mechanism.
The answer: the network learns Fourier analysis.
Part III: The Fourier Mechanism
Where Does the Circle Live?
The unit circle representation emerges in multiple layers, but each plays a distinct role:
1. The Embedding Layer
Each input number k ∈ {0, 1, …, p-1} gets mapped to a vector in ℝ^d.
After grokking, these embedding vectors contain Fourier components:
embed(k) ≈ Σf ( af·cos(2πfk/p), bf·sin(2πfk/p) )
The embedding learns to place numbers around circles at different frequencies f.
Key insight: The embedding is doing a discrete Fourier transform!
For mod 59 (a prime Nanda studied), the strongest frequency is f = 1: the embedding places numbers as vertices of a 59-gon in a 2D subspace of the high-dimensional embedding space.
2. The Attention Layer (if present)
In transformers with attention, this layer primarily handles:
- Moving information between positions (the two input numbers)
- Not much “computation” for addition — attention is more useful for tasks requiring comparison or copying
For simple addition, a network with ONLY an MLP (no attention) can grok. Attention is helpful but not essential for this task.
3. The MLP Layers — Where the Magic Happens
The MLP is where the actual computation of (a + b) mod p occurs.
The MLP learns the trigonometric addition formulas:
cos(a + b) = cos(a)·cos(b) − sin(a)·sin(b)
sin(a + b) = sin(a)·cos(b) + cos(a)·sin(b)
The MLP neurons implement these identities:
- Some neurons compute products: cos(a) × cos(b), sin(a) × sin(b), etc.
- Other neurons compute the combinations with appropriate signs
- The result: cos(a+b) and sin(a+b) for various frequencies
4. The Unembedding Layer
The final layer reads off the angle and converts back to a discrete class.
It compares the computed (cos(a+b), sin(a+b)) to each possible output position on the circle and returns the closest one.
Part IV: High-Dimensional Geometry
The Pizza Slice Visualization
Imagine the embedding space (typically d = 128 or 256 dimensions).
Within this high-dimensional space, there’s a 2D subspace containing a circle. The p numbers are arranged as vertices of a regular p-gon on this circle.
But there are actually MULTIPLE such circles — one for each Fourier frequency that the network uses.
High-dimensional embedding space (d = 128)
|
|--- 2D subspace for frequency f=1: circle with p points
|--- 2D subspace for frequency f=2: circle with p points (doubled frequency)
|--- 2D subspace for frequency f=3: ...
|--- ... (other subspaces for other features)
Why Multiple Frequencies?
One frequency suffices for exact computation. But the network often learns multiple frequencies because:
- Redundancy improves robustness
- Different frequencies emerge independently during training
- The loss landscape has multiple valid solutions
How Neurons Access the Circle
The MLP neurons don’t “know” they’re working with a circle. They have:
- Input weights: Define what direction in embedding space the neuron “looks”
- Bias: Threshold for activation
- Nonlinearity: ReLU or GELU creating the computation
A neuron with input weights aligned with the cos(a) direction will respond proportionally to cos(2πa/p).
Pairs of neurons can implement multiplication via:
ReLU(x)·ReLU(y) − ReLU(−x)·ReLU(y) − …
This piecewise construction approximates x × y, enabling the trig identities.
Part V: The Sudden Transition
The Phase Transition
Grokking is abrupt. Why?
During training, TWO solutions compete:
- Memorizing circuit: Maps each training input directly to its output
- Generalizing circuit: Uses Fourier representation for all inputs
Both are present in the network simultaneously! The weights contain both patterns superimposed.
The Competition
Early training:
- Memorizing circuit dominates (faster to learn, lower initial loss)
- Generalizing circuit is nascent, weights are small
- Training loss: low. Test loss: high.
Weight decay slowly erodes the memorizing circuit:
- Memorization requires O(N) parameters to store N examples
- Fourier representation requires O(√N) parameters
- Weight decay penalizes complexity → memorization becomes “expensive”
The transition:
- At some critical point, the generalizing circuit becomes favorable
- Network rapidly shifts from one solution to the other
- Test accuracy jumps from ~0% to ~100% in tens to hundreds of steps
Measuring the Circuits
Nanda et al. developed “progress measures” — ways to detect the generalizing circuit before grokking occurs.
Key measure: Fourier components in the embedding
Even while test accuracy is zero, you can measure how much the embeddings look like Fourier modes. This signal grows gradually, then accelerates right before grokking.
The insight: Generalization is built gradually, but expressed suddenly.
Part VI: The Example — 1 + 3 mod 5
Let’s trace through the computation:
Inputs
- a = 1, b = 3, p = 5
- Correct answer: 4
Embedding
First, let’s establish the positions on the unit circle for mod 5:
Position k → angle θₖ = 2πk/5 k=0: θ = 0° → (cos 0°, sin 0°) = ( 1.000, 0.000) k=1: θ = 72° → (cos 72°, sin 72°) = ( 0.309, 0.951) k=2: θ = 144° → (cos 144°, sin 144°) = (-0.809, 0.588) k=3: θ = 216° → (cos 216°, sin 216°) = (-0.809, -0.588) ← third quadrant! k=4: θ = 288° → (cos 288°, sin 288°) = ( 0.309, -0.951)
Note: 216° is in the third quadrant where BOTH sine and cosine are negative.
For our inputs:
embed(1) ≈ (cos 72°, sin 72°) = ( 0.309, 0.951) embed(3) ≈ (cos 216°, sin 216°) = (-0.809, -0.588)
(Plus components at other frequencies, which we’ll ignore)
MLP Computation
The MLP uses the trigonometric addition formulas. For angles θ₁ = 72° and θ₃ = 216°:
cos(θ₁ + θ₃) = cos(θ₁)cos(θ₃) - sin(θ₁)sin(θ₃)
= (0.309)(-0.809) - (0.951)(-0.588)
= -0.250 - (-0.559)
= -0.250 + 0.559
= 0.309 ✓
sin(θ₁ + θ₃) = sin(θ₁)cos(θ₃) + cos(θ₁)sin(θ₃)
= (0.951)(-0.809) + (0.309)(-0.588)
= -0.769 + (-0.182)
= -0.951 ✓
Result: (0.309, -0.951)
Unembedding
The output (0.309, -0.951) is compared to each position on the circle:
k=0: ( 1.000, 0.000) — distance from (0.309, -0.951): 1.23 k=1: ( 0.309, 0.951) — distance from (0.309, -0.951): 1.90 k=2: (-0.809, 0.588) — distance from (0.309, -0.951): 1.90 k=3: (-0.809, -0.588) — distance from (0.309, -0.951): 1.23 k=4: ( 0.309, -0.951) — distance from (0.309, -0.951): 0.000 ← EXACT MATCH!
Position 4 wins! And indeed, 1 + 3 = 4 mod 5. ✓
Why This Works
The angles add directly:
- Input 1: angle = 72° = 2π/5 radians
- Input 3: angle = 216° = 6π/5 radians
- Sum: 72° + 216° = 288° = 8π/5 radians
- Position 4 has angle: 288° = 8π/5 radians ✓
This is equivalent to multiplying complex exponentials:
e^(2πi·1/5) × e^(2πi·3/5) = e^(2πi·4/5)
The network learns that adding indices mod p is the same as adding angles, which is the same as multiplying points on the unit circle.
The Key Point
The network doesn’t literally multiply complex numbers. It learns weight matrices that:
- Project inputs onto Fourier basis vectors
- Combine these projections using the trig addition formula
- Read off the answer from the resulting angle
All this happens in the high-dimensional embedding space, with the circle living in a low-dimensional subspace.
Part VII: Connection to Triangles and Quantum Mechanics
The Triangle as Minimal Case
For mod 3:
0 = e^0 = 1
/\
/ \
/ \
1------2
1 = e^(2πi/3) 2 = e^(4πi/3)
This IS a triangle. Addition mod 3 is rotation by 120°.
The cube roots of unity:
- ω = e^(2πi/3) = -1/2 + i√3/2
- ω² = e^(4πi/3) = -1/2 – i√3/2
- ω³ = 1
They satisfy: 1 + ω + ω² = 0 (the vertices sum to zero — a deep property!)
Phase in Quantum Mechanics
Quantum amplitudes are complex numbers. Superposition involves adding them:
ψ_total = ψ₁ + ψ₂ = A₁·e^(iφ₁) + A₂·e^(iφ₂)
The phases φ₁, φ₂ determine interference. This is exactly the arithmetic of roots of unity!
When a quantum computer does addition in a superposition, it uses the same Fourier structure the neural network discovered.
Relational Interpretation
In our relational framework:
- Numbers mod p are not “things” — they are RELATIONSHIPS (positions on a cycle)
- The operation (addition) is a transformation preserving the cycle structure
- The neural network discovered that relationships, not objects, are fundamental
The Triangle in Hilbert Space: Quantum Connections
The unit circle structure we’ve been exploring isn’t just useful for neural networks — it’s the foundation of quantum mechanics. The same geometry that makes modular addition elegant explains superposition, the uncertainty principle, and quantum tunneling.
What is Hilbert Space?
Hilbert space is the mathematical arena where quantum mechanics takes place. Think of it as a generalization of ordinary space to potentially infinite dimensions, where:
- States are vectors (arrows) in this space
- The length of a vector represents probability (must equal 1 for physical states)
- Angles between vectors represent how “different” or “overlapping” states are
HILBERT SPACE VS. ORDINARY SPACE
═══════════════════════════════════════════════════════════════════════════
Ordinary 3D Space Quantum Hilbert Space
(where we live) (where quantum states live)
z |ψ₃⟩
│ │
│ • point │ • quantum state
│ / │ /
│ / │ /
└──────── y └──────── |ψ₂⟩
/ /
/ /
x |ψ₁⟩
Points have (x, y, z) coordinates States have complex amplitudes
Distance² = x² + y² + z² Probability = |amplitude|² = 1
The crucial feature: quantum amplitudes are complex numbers — they have magnitude AND phase, just like points on the unit circle!
The Simplest Quantum System: The Qubit
A qubit (quantum bit) lives on the Bloch sphere, which is essentially our unit circle extended to 3D:
THE BLOCH SPHERE — A Qubit's State Space
═══════════════════════════════════════════════════════════════════════════
|0⟩ (spin up)
●
/│\
/ │ \
/ │ \
/ │ \
/ │ \ ← Any point on the sphere
●─────┼─────● is a valid qubit state!
/ │ \
/ │ \
/ │ \
/ │ \
●──────────●──────────●
/│\
/ │ \
/ │ \
●
|1⟩ (spin down)
North pole: |0⟩ = definitely "0" (spin up)
South pole: |1⟩ = definitely "1" (spin down)
Equator: equal superposition of |0⟩ and |1⟩
Every other point: some superposition with a PHASE
The equator of the Bloch sphere IS our unit circle! Points on the equator are:
|ψ⟩ = (1/√2)(|0⟩ + e^(iφ)|1⟩)
That e^(iφ) is exactly the phase factor we’ve been studying!
Superposition: Being on Multiple Points at Once
In classical computing (and our neural network), a state is ONE point on the circle.
In quantum mechanics, a state can be a superposition — a weighted sum of multiple points:
SUPERPOSITION — The Quantum Difference
═══════════════════════════════════════════════════════════════════════════
Classical (Neural Network): Quantum:
0 0
● ●
╱ ╲ ╱ ╲
╱ ╲ ╱ ╲
● ● ◐ ◐
1 4 1 4
╲ ╱ ╲ ╱
╲ ╱ ╲ ╱
2───3 2───3
↑
ONE position MULTIPLE positions
(the answer is 3) simultaneously!
Classical: State IS position 3 |ψ⟩ = α|0⟩ + β|1⟩ + γ|2⟩ + δ|3⟩ + ε|4⟩
Quantum: State is a SUPERPOSITION where |α|² + |β|² + |γ|² + |δ|² + |ε|² = 1
of all positions, each (probabilities must sum to 1)
with a complex amplitude
Why superposition exists: The Schrödinger equation is LINEAR. If |ψ₁⟩ and |ψ₂⟩ are valid states, then α|ψ₁⟩ + β|ψ₂⟩ is also valid. There’s nothing in the math that forces a single answer!
The Uncertainty Principle: Conjugate Circles
Here’s where the Fourier transform becomes profound.
Position and momentum in quantum mechanics are related by a Fourier transform:
ψ̃(p) = (1/√(2πℏ)) ∫ ψ(x) e^(−ipx/ℏ) dx
The uncertainty principle emerges because:
- A state localized in position (sharp spike) has SPREAD-OUT momentum (many frequencies)
- A state localized in momentum (single frequency) has SPREAD-OUT position
THE UNCERTAINTY PRINCIPLE — Fourier Duality
═══════════════════════════════════════════════════════════════════════════
Position space: Momentum space:
(where is the particle?) (how fast is it moving?)
CASE 1: Precise position
│ │ ∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿
│ ╱╲ │∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿
│ ╱ ╲ │∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿
└────╱────╲────→ x └─────────────────→ p
"I know WHERE it is" "I have NO IDEA how fast"
(narrow spike) (all frequencies present)
CASE 2: Precise momentum
│ ∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿ │
│∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿ │ ╱╲
│∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿∿ │ ╱ ╲
└─────────────────→ x └────╱────╲────→ p
"I have NO IDEA where" "I know HOW FAST"
(spread everywhere) (single frequency)
HEISENBERG'S LIMIT: Δx · Δp ≥ ℏ/2
You CANNOT have both precise position AND precise momentum.
This isn't a measurement problem — it's built into the wave structure!
Connection to our circles: On our mod-5 pentagon, imagine the “position” basis is the 5 vertices, and the “momentum” basis is the 5 Fourier modes. A state perfectly localized on one vertex is SPREAD across all Fourier modes, and vice versa. The discrete Fourier transform guarantees this!
Quantum Tunneling: Phase Coherence Through Barriers
Tunneling is the quantum phenomenon where particles pass through barriers they classically couldn’t. The unit circle explains why.
QUANTUM TUNNELING — Phase Makes It Possible
═══════════════════════════════════════════════════════════════════════════
Classical particle hitting a wall:
●→→→→│█████│ The particle bounces back.
│█████│ It doesn't have enough energy
│█████│ to go over the barrier.
Quantum particle hitting a wall:
│█████│
∿∿∿∿∿∿∿→ │█████│ →∿∿
(wave with │█████│ (smaller wave
amplitude A) │█████│ amplitude B)
│█████│
BARRIER
The wave doesn't stop at the barrier — it DECAYS exponentially inside,
but if the barrier is thin enough, some amplitude leaks through!
Why does this happen? Inside the barrier, the wave function becomes:
ψ(x) = A·e^(−κx)
The wave doesn’t oscillate — it decays. But it doesn’t instantly become zero. If the barrier is thin enough, there’s still nonzero amplitude on the other side.
The phase connection: The tunneling probability depends on the PHASE relationships:
TUNNELING AND PHASE
═══════════════════════════════════════════════════════════════════════════
Before barrier: ψ = |A| e^(ikx) ← oscillating, phase = kx
Inside barrier: ψ = |A| e^(-κx) ← decaying, but PHASE PRESERVED
After barrier: ψ = |B| e^(ikx) ← oscillating again, same k!
The particle "remembers" its phase through the barrier.
This is why tunneling is COHERENT — it preserves quantum information.
On the unit circle:
Before Inside After
● ●→→→→ ●
╱│ (decay) ╱│
╱ │ ╱ │
╱ │ ╱ │
θ │ θ │
The ANGLE θ (phase) survives the tunneling process!
The Triangle as Minimal Quantum System
Why does the triangle keep appearing? Because it’s the minimal non-trivial cyclic structure.
TRIANGLE: THE SIMPLEST QUANTUM CYCLE
═══════════════════════════════════════════════════════════════════════════
Mod 2 (two states): Mod 3 (three states):
|0⟩ |0⟩
● ●
│ ╱ ╲
│ ← Just a flip! ╱ ╲
│ (classical-like) ╱ ╲
● ●───────●
|1⟩ |1⟩ |2⟩
Only two phases: 0 and π Three phases: 0, 2π/3, 4π/3
Not much room for NOW we have room for
quantum weirdness genuine interference!
The TRIANGLE is where quantum behavior truly begins:
|ψ⟩ = α|0⟩ + β|1⟩ + γ|2⟩
where α, β, γ are complex numbers with |α|² + |β|² + |γ|² = 1
The phases of α, β, γ can interfere constructively or destructively.
This is the origin of quantum computational advantage!
The qutrit: A three-level quantum system (qutrit) uses exactly this triangle structure. Qutrits can encode information more efficiently than qubits in some protocols, precisely because the triangle allows richer phase relationships.
Summary: From Neural Networks to Quantum Mechanics
The same mathematical structure underlies both:
| Neural Network Grokking | Quantum Mechanics |
|---|---|
| Numbers mod p | Quantum states in p-dimensional Hilbert space |
| Unit circle embedding | Complex amplitudes with phase |
| Fourier transform | Position ↔ momentum duality |
| Addition = rotation | Time evolution = phase rotation |
| Pentagon (mod 5) | 5-level quantum system |
| Triangle (mod 3) | Qutrit |
The neural network discovered what physicists have known for a century: the circle is the natural geometry of cyclic phenomena, whether those cycles are modular arithmetic or quantum phase.
Part VII-B: Quantum Computing and Quantum Machine Learning
Quantum Computing: The Native Language of Circles
Classical computers manipulate bits (0 or 1). Quantum computers manipulate qubits — superpositions that live on the unit circle.
CLASSICAL vs QUANTUM COMPUTATION
═══════════════════════════════════════════════════════════════════════════
CLASSICAL BIT: QUANTUM QUBIT:
Either 0 or 1 |ψ⟩ = α|0⟩ + β|1⟩
●───────● |0⟩
0 1 ●
/│\
One state at a time / │ \ ← Lives on Bloch sphere
/ │ \
●───┼───●
│
●
|1⟩
CLASSICAL GATE (NOT): QUANTUM GATE (Hadamard H):
0 → 1 |0⟩ → (|0⟩ + |1⟩)/√2
1 → 0 |1⟩ → (|0⟩ - |1⟩)/√2
Flips the bit Creates SUPERPOSITION
Both possibilities at once!
Quantum Gates as Rotations
Every quantum gate is a rotation on the Bloch sphere. The same geometry underlying grokking!
COMMON QUANTUM GATES AS ROTATIONS
═══════════════════════════════════════════════════════════════════════════
X gate (NOT): 180° rotation around X-axis |0⟩ ↔ |1⟩
Z gate: 180° rotation around Z-axis Flips phase: |1⟩ → -|1⟩
H gate: 90° rotation + flip Creates superposition
Rz(θ): θ rotation around Z-axis |1⟩ → e^(iθ)|1⟩
Z (phase)
│
│ Rz(θ): Rotate
●──────→ around here
/│\
/ │ \
←────/ │ \────→ X (real part)
/ │ \
/ │ \
● │ ●
\ │ /
\ │ /
\ │ /
\ │ /
\│/
●
│
Y (imaginary part)
The SAME TRIGONOMETRY that grokking discovered is built into quantum hardware!
The Quantum Fourier Transform (QFT)
Here’s where it gets beautiful. The exact Fourier transform that neural networks learn during grokking is a native quantum operation called the Quantum Fourier Transform.
QUANTUM FOURIER TRANSFORM
═══════════════════════════════════════════════════════════════════════════
Classical DFT on N points: O(N²) operations
Fast Fourier Transform: O(N log N) operations
Quantum Fourier Transform: O((log N)²) operations ← Exponentially faster!
How QFT works (on 3 qubits = mod 8):
Input: |j⟩ = |j₂j₁j₀⟩ (binary representation)
┌───┐ ┌─────────┐
|j₂⟩ ──────┤ H ├──────●───┤ Phase │───────────────────
└───┘ │ └─────────┘
│ ┌───┐ ┌─────────┐
|j₁⟩ ─────────────────┼───────┤ H ├────●────┤ Phase │───
│ └───┘ │ └─────────┘
│ │ ┌───┐
|j₀⟩ ─────────────────●────────────────●────────┤ H ├───
└───┘
Output: Equal superposition of all |k⟩ with phases e^(2πijk/N)
This is EXACTLY the Fourier embedding the neural network learned!
The QFT transforms computational basis states into phase states:
QFT EXAMPLE: mod 5 (needs 3 qubits, use states 0-4)
═══════════════════════════════════════════════════════════════════════════
Input |3⟩: (represents number 3)
QFT
|3⟩ ───────────→ (1/√5) Σₖ e^(2πi·3k/5) |k⟩
This output is a SUPERPOSITION where state |k⟩ has phase e^(2πi·3k/5)
Exactly the pentagon embedding:
|0⟩: phase e^(2πi·0/5) = 1 (angle 0°)
|1⟩: phase e^(2πi·3/5) (angle 216°)
|2⟩: phase e^(2πi·6/5) (angle 432° = 72°)
|3⟩: phase e^(2πi·9/5) (angle 648° = 288°)
|4⟩: phase e^(2πi·12/5) (angle 864° = 144°)
The QFT AUTOMATICALLY places numbers on the unit circle!
Quantum Machine Learning: Grokking at the Speed of Light
Quantum Machine Learning (QML) combines quantum computing with neural network architectures. The key insight: if grokking discovers Fourier representations, and quantum computers natively perform Fourier transforms, then quantum computers should grok naturally.
VARIATIONAL QUANTUM CIRCUIT (VQC)
═══════════════════════════════════════════════════════════════════════════
A VQC is like a quantum neural network:
Classical Neural Net: Variational Quantum Circuit:
───────────────────── ────────────────────────────
Input x Input |x⟩ (encoded as quantum state)
│ │
▼ ▼
┌─────────┐ ┌─────────┐
│ Layer 1 │ weights W₁ │ U(θ₁) │ rotation angles θ₁
│ ReLU │ │ (gates) │
└────┬────┘ └────┬────┘
│ │
▼ ▼
┌─────────┐ ┌─────────┐
│ Layer 2 │ weights W₂ │ U(θ₂) │ rotation angles θ₂
│ ReLU │ │ (gates) │
└────┬────┘ └────┬────┘
│ │
▼ ▼
Output Measurement
The learnable parameters are ROTATION ANGLES on the Bloch sphere.
This is inherently "Fourier-friendly" — the representation is built in!
Quantum Advantage for Modular Addition
For learning modular addition specifically, quantum circuits have structural advantages:
WHY QUANTUM CIRCUITS "GROK" NATURALLY
═══════════════════════════════════════════════════════════════════════════
Classical Network Path:
Input (1,3) → Embedding → Attention → MLP → Output
learn learn learn
circles "which?" trig ident.
Must LEARN the Fourier representation from scratch
Takes ~10⁵ training steps to grok
Quantum Circuit Path:
Input |1⟩|3⟩ → QFT → Phase Gate → Inverse QFT → Measure |4⟩
built built-in built-in
in! addition!
Fourier representation is AUTOMATIC
Addition is a phase gate: e^(iθ₁) × e^(iθ₃) = e^(i(θ₁+θ₃))
The structure the classical network must DISCOVER
is what the quantum circuit STARTS WITH.
Making Grokking “Super Natural”
The question: Can we use quantum effects to make grokking not just faster, but qualitatively different?
1. Superposition Learning
Classical training explores one weight configuration at a time. A quantum learner could explore all configurations simultaneously:
SUPERPOSITION OVER HYPOTHESES
═══════════════════════════════════════════════════════════════════════════
Classical Training: Quantum Training:
Step 1: Try weights W₁ Step 1: Superposition of ALL weights
→ Get loss L₁ |ψ⟩ = Σᵢ |Wᵢ⟩
Step 2: Try weights W₂ Step 2: Parallel evaluation
→ Get loss L₂ Σᵢ Loss(Wᵢ)|Wᵢ⟩
...10⁵ steps... Step 3: Interference
Good weights amplified
Step N: Finally converge! Bad weights cancelled
Step 4: Measure → Good weights!
The "grokking transition" could happen in ONE quantum step
instead of thousands of classical steps.
2. Quantum Interference Selects the Fourier Solution
In classical grokking, weight decay slowly pushes the network from memorization to generalization. Quantum interference could make this instantaneous:
QUANTUM INTERFERENCE IN LEARNING
═══════════════════════════════════════════════════════════════════════════
The two competing solutions:
MEMORIZATION: GENERALIZATION:
└── Large ||W|| └── Small ||W||
└── Random structure └── Fourier structure
└── Works on training └── Works everywhere
Classical: Weight decay slowly penalizes memorization
Grokking takes ~10⁵ steps
Quantum: Prepare superposition of both solutions
Fourier solution has PHASE COHERENCE
Memorization solution has RANDOM PHASES
After interference:
Coherent (Fourier) → Amplified (constructive)
Incoherent (Memory) → Cancelled (destructive)
The elegant solution wins by PHYSICS, not by slow optimization!
3. Quantum Kernel Methods
A promising QML approach: use quantum circuits to compute kernel functions that naturally capture cyclic structure:
QUANTUM KERNEL FOR MOD p
═══════════════════════════════════════════════════════════════════════════
Classical kernel: K(x, y) = similarity measure between x and y
Quantum kernel: K(x, y) = |⟨φ(x)|φ(y)⟩|²
where |φ(x)⟩ is quantum encoding of x
For mod p addition, use QFT encoding:
|φ(x)⟩ = QFT|x⟩ = (1/√p) Σₖ e^(2πixk/p) |k⟩
Then the kernel is:
K(x, y) = |⟨φ(x)|φ(y)⟩|² = |(1/p) Σₖ e^(2πi(y-x)k/p)|²
= 1 if x = y
= 0 otherwise (orthogonal on circle!)
This kernel EXACTLY captures modular structure.
No learning required — it's built into the quantum encoding!
The Triangle Circuit: Minimal Quantum Grokking
For mod 3 (the triangle), we can build an explicit quantum circuit:
TRIANGLE ADDITION CIRCUIT (mod 3)
═══════════════════════════════════════════════════════════════════════════
Use a QUTRIT (3-level system): |0⟩, |1⟩, |2⟩
│1⟩
●
╱ ╲
╱ ╲
╱ ╲
●───────●
│0⟩ │2⟩
Input: |a⟩|b⟩ (two qutrits)
Circuit:
┌─────┐ ┌───────────────┐ ┌──────┐
|a⟩ ─────┤ QFT ├─────┤ ├─────┤ QFT† ├───── |a+b mod 3⟩
└─────┘ │ Controlled │ └──────┘
│ Phase │
┌─────┐ │ │
|b⟩ ─────┤ QFT ├─────┤ Gate ├───────────────── (discarded)
└─────┘ └───────────────┘
The controlled phase gate adds the angles:
|ω^a⟩|ω^b⟩ → |ω^(a+b)⟩|ω^b⟩
where ω = e^(2πi/3)
This circuit performs mod 3 addition in O(1) operations!
The grokking is INSTANTANEOUS because the structure is built in.
Summary: From Classical Grokking to Quantum Grokking
THE EVOLUTION OF "UNDERSTANDING" MODULAR ADDITION
═══════════════════════════════════════════════════════════════════════════
Level 0: Human memorization
"1+2=3, 2+2=4, 3+2=0, ..."
No structure, just lookup table
Level 1: Classical neural network (pre-grokking)
Memorizes training examples
Fails on test examples
Level 2: Classical neural network (post-grokking)
Discovers Fourier representation
Generalizes perfectly
Takes ~10⁵ steps to find the structure
Level 3: Quantum neural network
Fourier structure built into QFT
Addition is native (phase multiplication)
Groks in O(1) with exponentially fewer parameters
Level 4: Pure quantum circuit
No learning needed at all!
mod p addition is just: QFT → Phase gate → QFT†
Instant "grokking" — or rather, no grokking because
the representation was never NOT Fourier
The progression:
SLOW LEARNING → GROKKING → NATIVE UNDERSTANDING
Quantum mechanics makes cyclic structure "super natural"
because quantum mechanics IS cyclic structure (phases, circles, waves).
Open Questions in Quantum Grokking
- Quantum Advantage: Can quantum ML demonstrate provable speedup for discovering algebraic structure?
- Noise Resilience: Real quantum computers have errors. Does the Fourier structure survive decoherence?
- Beyond Cyclic Groups: Grokking works for mod p. Can quantum methods extend to non-abelian groups? (Hint: This connects to Shor’s algorithm!)
- Hybrid Approaches: Can classical networks with quantum-inspired layers (QFT regularization) grok faster?
- The Meta-Question: If quantum computers “understand” modular addition natively, what does this say about the nature of mathematical understanding?
Part VIII: Why This Matters
For AI Interpretability
Grokking shows that neural networks can discover elegant mathematical structure — but only after extended training. The representation learning is separate from fitting the data.
This has implications for:
- How long to train models
- The role of regularization
- Understanding what networks “really know”
For Mathematics
The network independently discovered Fourier analysis, a 200-year-old mathematical technique. This suggests:
- Mathematical structures are “natural” — discoverable from examples
- There may be a unique (or small set of) optimal representations for given tasks
- Neural networks as tools for mathematical discovery?
For Physics
The circular representation for cyclic groups mirrors:
- Quantum phase (U(1) symmetry)
- Rotational symmetry (SO(2))
- The relationship between algebra and geometry
The network found the same structure physicists use.
Exercises
- Verify the Fourier embedding: For mod 7, write down the 7th roots of unity. Verify that 3 + 5 = 1 mod 7 corresponds to the correct phase addition.
- Triangle property: Prove that 1 + ω + ω² = 0 for ω = e^(2πi/3). (Hint: geometric series or direct calculation)
- Weight decay: If memorization requires ||W|| ~ N and generalization requires ||W|| ~ √N, and loss = L_data + λ||W||², explain why large λ favors generalization.
- Phase transition: In statistical mechanics, phase transitions occur when free energy F = E – TS changes its minimum. By analogy, what plays the role of energy and entropy in grokking?
- Attention vs MLP: Design an experiment to determine whether attention is necessary for grokking mod p addition. What would you vary?
References
- Power, A. et al. (2022). “Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets.” arXiv:2201.02177
- Nanda, N. et al. (2023). “Progress Measures for Grokking via Mechanistic Interpretability.” ICLR 2023.
- Liu, Z. et al. (2022). “Towards Understanding Grokking: An Effective Theory of Representation Learning.” NeurIPS 2022.
- Heinlein, R. (1961). Stranger in a Strange Land. (Origin of “grok”)
Summary
Grokking was discovered in 2022 when OpenAI researchers found that neural networks suddenly generalize long after memorizing training data. Mechanistic interpretability revealed the mechanism: networks learn Fourier representations where numbers mod p become vertices of a regular p-gon on the unit circle in embedding space. The embedding layer learns to place inputs on the circle; the MLP layers learn trigonometric identities to compute addition; the unembedding reads off the result. The transition is sudden because two circuits (memorizing and generalizing) compete, with weight decay gradually favoring the simpler Fourier solution. When the generalizing circuit becomes favorable, performance jumps discontinuously — a phase transition from rote memory to genuine understanding.
The triangle (mod 3) is the minimal case: three cube roots of unity, 120° apart, closed under addition.