Research Addendum 8

Prime Grokking: Scratchpads & Fillers

A visual breakdown of why standard neural networks fail on prime numbers, and how token-space computation tests the boundaries of algorithmic emergence.

+ + +

1. The Core Puzzle: Why Primes Break Standard Grokking

When researchers train neural networks on modular arithmetic (like (a + b) mod 97), the network suddenly experiences grokking: after long overfitting, it abruptly discovers the generalized circle algorithm (Fourier transform) because it is simpler and lower-norm than memorization.

Next-Prime is completely different. Finding the next prime after n requires a two-level nested algorithm:

+ +

A standard feedforward Transformer has a fixed number of layers. It cannot run an unbounded while-loop. In experiments E1–E7, we proved that even training for 4,000,000 steps never produces grokking on next-prime: the model just memorizes a lookup table for numbers in range, and scores 0%–3% out-of-range.

+ + +

2. The Proposed Solution: Computation in Token Space

If the model doesn't have enough internal depth to perform multiple serial operations, we can give it intermediate tokens to think before answering.

Recent theoretical work by Pfau et al. (2024, "Let's Think Dot by Dot") made a surprising prediction: filler tokens (e.g. dots or pauses) only help if the hidden subcomputations are parallelizable. Checking divisors {2, 3, 5, 7} are independent parallel operations! Therefore, next-prime is the ideal testbed for this hypothesis.

+ + +

3. The 4-Arm Experimental Design

To scientifically isolate why intermediate tokens help (or don't), we test four distinct arms:

+ +

+ Arm A: Direct Baseline + Control +

Input goes directly to output. No intermediate steps.

+ 4 + 2 + → + 4 + 3 + <eos> +

Tests: Can pure fixed-depth attention solve next-prime? (We know from E7 this fails out-of-range).

+ + +

+ Arm B: Structured Scratchpad + Algorithm Supervision +

Ground-truth trial division steps are spelled out in tokens.

+ 42 + → + c=43 + d2:0 + d3:0 + d5:0 + # + 43 +

Tests: If the algorithm is explicitly supervised, does the model grok and generalize to unseen ranges?

+ + +

+ Arm C: Pause / Filler Tokens + Pfau Hypothesis +

Fixed 16 identical pause tokens (no intermediate labels).

+ 42 + → + <p> + <p> + <p> + ... + # + 43 +

Tests: Does extra compute depth alone allow the transformer to execute parallel divisor checks silently?

+ + +

+ Arm D: Random Noise Tokens + Length / Bias Control +

Fixed 16 random letters from a disjoint alphabet ([a-p]).

+ 42 + → + x + m + k + ... + # + 43 +

Tests: Does any sequence expansion help, or is static pause token embedding special?

+ + +

4. What Each Comparison Proves

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

Observed Pattern	Scientific Interpretation	Significance
Arm B >> Arm A, C, D	Algorithm Decomposition Required: Extra compute alone does nothing; explicit intermediate supervision is required to guide SGD.	Confirms Nye et al. Scratchpad mechanism.
Arm C >> Arm A	Pfau et al. Confirmed: Unsupervised filler tokens provide enough hidden attention routing to compute parallel divisibility tests.	Major theoretical finding! First clean toy demonstration on non-group tasks.
Arm D ≈ Arm C > Arm A	Pure Depth Invariance: Expanding sequence length improves representational capacity regardless of token semantics.	Points to transformer attention capacity dynamics.
All Arms Fail ($P4$) Out-of-Range	Absolute Algorithmic Wall: Neither internal recurrence nor token-space scratchpads allow next-token models to generalize prime discovery.	Falsifies scratchpad extrapolation for unbounded search.

+ +

Summary of the Proposed Experiment

We will train a 2-layer GPT Transformer across all four arms in the $[2, 1000]$ regime for 200k steps with weight decay $0.1$. We evaluate exact-match accuracy both in-range ($[2, 1000]$) and on the unseen probe range ($[1001, 2000]$) to test true algorithmic generalization.