Transformers Learn Modular Multiplication via Discrete-Log Clock Algorithm

Previous studies on how small transformers learn modular multiplication observed a "dense" Fourier spectrum in the learned embeddings, suggesting that all frequencies were necessary. This contrasted with modular addition, which only required a sparse set of key frequencies. New research demonstrates that this density is an artifact of using the wrong analytical basis. By applying the multiplicative character transform, which is the natural Fourier transform for multiplication, the embedding spectrum becomes highly sparse. This indicates that the transformer is not learning multiplication directly but rather transforming it into an additive problem. Specifically, the study found that 96.9% of MLP neurons are precisely tuned to a single multiplicative frequency, and neuron activation heatmaps show 2D-periodic structure when reordered by the discrete logarithm. This suggests the transformer implements a "Discrete-Log Clock" algorithm, analogous to the "Clock algorithm" for addition, by converting multiplication into addition within discrete-log space. This methodology highlights the importance of matching the analysis basis to the algebraic structure of the task to reveal interpretable patterns.