Abstract
Abstract
We study how the input representation of an algebraic learning problem determines the internal algorithm that a neural network discovers. We train transformers to solve the discrete logarithm problem (DLP) and compare a raw representation against representations that expose or disrupt the Chinese Remainder Theorem (CRT) factorization of the underlying cyclic group. Our three main discoveries are:
First, different representations produce different internal algorithms. The raw representation develops an interaction-rich internal organization with approximately 65 percent of Fourier energy in cross-factor interaction modes, while the CRT representation develops a separable organization with only 1 percent interaction energy, despite both solving the same task.
Second, the interaction structure forms during the memorization plateau, well before visible generalization. The cross-factor interaction energy rises from 35 to 52 percent between epochs 15,000 and 30,000, while test accuracy remains near 30 percent and only generalizes at epoch 50,000.
Third, algebraic alignment, not merely factorization, is required for rapid generalization. A hierarchy of information-preserving controls shows that representations preserving the true CRT factor partition grok (CRT at 20K epochs, Permuted CRT at 8K, Role-Decoupled CRT at 26K), while representations destroying the partition fail to grok even after 100K epochs across three independent seeds (Global Random Bijection, Order-Matched Random, Mixed Radix). A critical audit also reveals that the previously studied SCRAMBLED representation is exactly conjugate to CRT at initialization and does not test algebra destruction. Top-k causal ablation with 100 random controls confirms that the identified Fourier modes are causally necessary for computation.