Uncovering a Universal Abstract Algorithm for Modular Addition in Neural Networks

neural information processing systems, pp. 49512–49573

Abstract

We propose a testable universality hypothesis, asserting that seemingly disparate neural network solutions observed in the simple task of modular addition are unified under a common abstract algorithm. While prior work interpreted variations in neuron-level representations as evidence for distinct algorithms, we demonstrate - through multi-level analyses spanning neurons, neuron clusters, and entire networks - that multilayer perceptrons and transformers universally implement the abstract algorithm we call the approximate Chinese Remainder Theorem. Crucially, we introduce approximate cosets and show that neurons activate exclusively on them. Furthermore, our theory works for deep neural networks (DNNs). It predicts that universally learned solutions in DNNs with trainable embeddings or more than one hidden layer require only O(log n) features, a result we empirically confirm. This work thus provides the first theory-backed interpretation of multilayer networks solving modular addition. It advances generalizable interpretability and opens a testable universality hypothesis for group multiplication beyond modular addition.

Authors 4

1. Gavin McCracken

   McGill University

   Affiliation as printed

   McGill University

2. Gabriela Moisescu-Pareja

   McGill University

   Affiliation as printed

   McGill University, Mila

3. Vincent Létourneau

   Université de Montréal

   Affiliation as printed

   Université de Montréal

4. Doina Precup

   Mila - Quebec Artificial Intelligence Institute · McGill University

   Affiliation as printed

   McGill University / Mila / DeepMind Montreal