Uncovering a Universal Abstract Algorithm for Modular Addition in Neural Networks

• URL: http://arxiv.org/abs/2505.18266v1
• Date: Fri, 23 May 2025 18:02:46 GMT
• Title: Uncovering a Universal Abstract Algorithm for Modular Addition in Neural Networks
• Authors: Gavin McCracken, Gabriela Moisescu-Pareja, Vincent Letourneau, Doina Precup, Jonathan Love,
• Abstract summary: We show that neural network solutions observed in the simple task of modular addition are unified under a common abstract algorithm.<n>Our theory works for deep neural networks (DNNs)<n>It predicts that universally learned solutions in DNNs with trainable embeddings or more than one hidden layer require only O(log n) features.
• Score: 29.838715657292365
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Concept-Guided Interpretability via Neural Chunking [54.73787666584143]
  We show that neural networks exhibit patterns in their raw population activity that mirror regularities in the training data.<n>We propose three methods to extract these emerging entities, complementing each other based on label availability and dimensionality.<n>Our work points to a new direction for interpretability, one that harnesses both cognitive principles and the structure of naturalistic data.
  arXiv  Detail & Related papers  (2025-05-16T13:49:43Z)
• ReLUs Are Sufficient for Learning Implicit Neural Representations [17.786058035763254]
  We revisit the use of ReLU activation functions for learning implicit neural representations. Inspired by second order B-spline wavelets, we incorporate a set of simple constraints to the ReLU neurons in each layer of a deep neural network (DNN) We demonstrate that, contrary to popular belief, one can learn state-of-the-art INRs based on a DNN composed of only ReLU neurons.
  arXiv  Detail & Related papers  (2024-06-04T17:51:08Z)
• Fourier Circuits in Neural Networks and Transformers: A Case Study of Modular Arithmetic with Multiple Inputs [35.212818841550835]
  One-hidden layer neural networks and one-layer Transformers are studied.<n>One-hidden layer neural networks attain a maximum $ L_2,k+1 $-margin on a dataset.<n>We observe similar computational mechanisms in attention of one-layer Transformers.
  arXiv  Detail & Related papers  (2024-02-12T05:52:06Z)
• Manipulating Feature Visualizations with Gradient Slingshots [54.31109240020007]
  We introduce a novel method for manipulating Feature Visualization (FV) without significantly impacting the model's decision-making process. We evaluate the effectiveness of our method on several neural network models and demonstrate its capabilities to hide the functionality of arbitrarily chosen neurons.
  arXiv  Detail & Related papers  (2024-01-11T18:57:17Z)
• Permutation Equivariant Neural Functionals [92.0667671999604]
  This work studies the design of neural networks that can process the weights or gradients of other neural networks. We focus on the permutation symmetries that arise in the weights of deep feedforward networks because hidden layer neurons have no inherent order. In our experiments, we find that permutation equivariant neural functionals are effective on a diverse set of tasks.
  arXiv  Detail & Related papers  (2023-02-27T18:52:38Z)
• Exploring the Approximation Capabilities of Multiplicative Neural Networks for Smooth Functions [9.936974568429173]
  We consider two classes of target functions: generalized bandlimited functions and Sobolev-Type balls. Our results demonstrate that multiplicative neural networks can approximate these functions with significantly fewer layers and neurons. These findings suggest that multiplicative gates can outperform standard feed-forward layers and have potential for improving neural network design.
  arXiv  Detail & Related papers  (2023-01-11T17:57:33Z)
• On the Approximation and Complexity of Deep Neural Networks to Invariant Functions [0.0]
  We study the approximation and complexity of deep neural networks to invariant functions. We show that a broad range of invariant functions can be approximated by various types of neural network models. We provide a feasible application that connects the parameter estimation and forecasting of high-resolution signals with our theoretical conclusions.
  arXiv  Detail & Related papers  (2022-10-27T09:19:19Z)
• Extrapolation and Spectral Bias of Neural Nets with Hadamard Product: a Polynomial Net Study [55.12108376616355]
  The study on NTK has been devoted to typical neural network architectures, but is incomplete for neural networks with Hadamard products (NNs-Hp) In this work, we derive the finite-width-K formulation for a special class of NNs-Hp, i.e., neural networks. We prove their equivalence to the kernel regression predictor with the associated NTK, which expands the application scope of NTK.
  arXiv  Detail & Related papers  (2022-09-16T06:36:06Z)
• Universal approximation property of invertible neural networks [76.95927093274392]
  Invertible neural networks (INNs) are neural network architectures with invertibility by design. Thanks to their invertibility and the tractability of Jacobian, INNs have various machine learning applications such as probabilistic modeling, generative modeling, and representation learning.
  arXiv  Detail & Related papers  (2022-04-15T10:45:26Z)
• A note on the complex and bicomplex valued neural networks [0.0]
  We first write a proof of the perceptron convergence algorithm for the complex multivalued neural networks (CMVNNs) Our primary goal is to formulate and prove the perceptron convergence algorithm for the bicomplex multivalued neural networks (BMVNNs)
  arXiv  Detail & Related papers  (2022-02-04T19:25:01Z)
• How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks [80.55378250013496]
  We study how neural networks trained by gradient descent extrapolate what they learn outside the support of the training distribution. Graph Neural Networks (GNNs) have shown some success in more complex tasks.
  arXiv  Detail & Related papers  (2020-09-24T17:48:59Z)
• Exploiting Heterogeneity in Operational Neural Networks by Synaptic Plasticity [87.32169414230822]
  Recently proposed network model, Operational Neural Networks (ONNs), can generalize the conventional Convolutional Neural Networks (CNNs) In this study the focus is drawn on searching the best-possible operator set(s) for the hidden neurons of the network based on the Synaptic Plasticity paradigm that poses the essential learning theory in biological neurons. Experimental results over highly challenging problems demonstrate that the elite ONNs even with few neurons and layers can achieve a superior learning performance than GIS-based ONNs.
  arXiv  Detail & Related papers  (2020-08-21T19:03:23Z)
• Banach Space Representer Theorems for Neural Networks and Ridge Splines [17.12783792226575]
  We develop a variational framework to understand the properties of the functions learned by neural networks fit to data. We derive a representer theorem showing that finite-width, single-hidden layer neural networks are solutions to inverse problems.
  arXiv  Detail & Related papers  (2020-06-10T02:57:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.