Deep neural networks divide and conquer dihedral multiplication

We find multilayer perceptrons and transformers both universally learn an instantiation of the same divide-and-conquer algorithm that requires only a logarithmic number of neural representations to solve dihedral multiplication. Clustering neurons based on similar activation behaviour reveals remarkably clear structure: each neural representation corresponds to a Cayley graph. To our knowledge, this is the first work that fully characterizes and describes all neural representations that are learnable on a dataset, while prior work on group multiplications studied neuron-level behavior, or preliminarily investigated cluster behavior. Thus, we can understand the algorithm networks universally learn at three levels of abstraction: 1) Neurons activate on coset or approximate coset structure of the dihedral group. 2) Groups of neurons together form neural representations that act to divide the dataset into different subproblems, being Cayley graphs, where the equivalence class of the answer is computed. 3) The global algorithm then linearly combines each neural representation (subproblem) together at the logits. This work provides the community with a deep case study and a well-understood toy model for interpretability, and makes progress toward proving the conjecture that networks trained via stochastic gradient methods divide and conquer all group multiplication tasks.

This paper studies how neural networks learn to solve a structured math task: multiplying symmetries of a polygon, such as rotations and reflections. The authors train different kinds of neural networks under many conditions and find networks solve the task the same way. Internally, the networks organize information into smaller pieces that correspond to Cayley graphs, mathematical diagrams that describe how group elements relate to each other. The paper introduces a method for identifying these learned structures and shows that the networks use them as part of an efficient divide-and-conquer strategy: instead of solving the whole multiplication problem at once, they break it into simpler subproblems and combine the results. This helps researchers better understand what algorithms neural networks learn when solving mathematical tasks.