Low Rank and Sparse Fourier Structure in Recurrent Networks Trained on Modular Addition

Akshay Rangamani

TL;DR

This paper reveals that Recurrent Neural Networks (RNNs) trained on the modular addition task learn a "Fourier multiplication" strategy, similar to transformers. The authors demonstrate that the RNN's internal representations and weights exhibit a low-rank and sparse Fourier structure, where specific frequencies are crucial for accurate computation. This finding offers a deeper mechanistic understanding of how RNNs solve algorithmic tasks and highlights a shared computational strategy across different neural network architectures.

What Problem Does This Paper Address?

Understanding how neural networks arrive at their solutions is a fundamental challenge in deep learning, often referred to as the "black-box" problem. Mechanistic interpretability aims to reverse-engineer these learned solutions. While transformers have been shown to employ Fourier multiplication for tasks like modular addition, it's unclear if other architectures, like RNNs, adopt similar strategies. This paper investigates whether RNNs, known for their linear scaling with sequence length, also leverage Fourier-based computations for algorithmic tasks, and how their internal structure reflects this.

Methods

The authors train a single-layer vanilla RNN with a tanh nonlinearity on the modular addition task (a + b mod 113). To understand the learned computation, they employ a Fourier domain analysis. This involves:

  • Fourier Transform Analysis: Applying a Fourier transform to the network's inputs, hidden states, and outputs to identify dominant frequencies.
  • Singular Value Decomposition (SVD): Analyzing the weight matrices (embedding, unembedding, input-hidden, hidden-hidden) to uncover their intrinsic rank and identify significant components.
  • Causal Interventions (Ablation Studies): Systematically removing specific Fourier frequencies from the model's components to observe the impact on accuracy, thereby establishing the causal role of these frequencies.
  • Fitting Fourier Representations: Explicitly fitting the learned hidden states to Fourier-based functions to confirm the identified computational strategy.

Datasets

The paper uses a synthetic dataset for training and evaluation. Sequences of the form a + b (mod p) are generated, where p = 113. A random 30% of the 113x113 possible sequences are used for training, with the remaining 70% reserved for testing. The authors mention that they also explored using 30% to 70% of the dataset in increments of 10% for training, finding consistent results.

Key Insights and Ideas

  • RNNs also use Fourier Multiplication: Contrary to potential architectural differences, RNNs trained on modular addition learn a strategy analogous to transformers, employing Fourier multiplication.
  • Low-Rank and Sparse Fourier Structure: The RNN's weights and internal states exhibit a low-rank structure, and their representations in Fourier space are sparse, meaning only a few specific frequencies are important.
  • Frequency-Specific Components: The authors can attribute specific singular vectors in the weight matrices (particularly the unembedding layer) to distinct Fourier frequencies, suggesting a structured encoding of these frequencies.
  • Causal Role of Frequencies: Ablating individual frequencies has a minimal impact on accuracy, but removing multiple frequencies drastically degrades performance, confirming their essential role.
  • Shared Computational Principles: The findings suggest that despite architectural differences (RNNs vs. Transformers), deep learning models might converge on similar computational principles for certain algorithmic tasks.

Key Results

  • The RNN achieves zero test loss after approximately 4000 epochs.
  • The Fourier analysis reveals that dominant frequencies in the embedding, unembedding, and hidden states correspond to wk = 2πk/p for k ∈ {6, 15, 20, 29, 47, 54}.
  • The weight matrices are found to be low-rank: r=12 for embedding, unembedding, and input-hidden matrices, and r=32 for the hidden-hidden matrix. These ranks are directly related to the number of dominant Fourier frequencies.
  • Ablation studies show that removing single frequencies results in high accuracy (e.g., 100% for k₁=47), but removing multiple frequencies leads to chance accuracy (e.g., 0.885% for removing 6 specific frequencies).
  • The final hidden state can be accurately represented as a combination of cos(ωk(a+b)) and sin(ωk(a+b)) with relative errors below 10⁻².

Limitations and Future Work

  • Limited Task Scope: The study focuses on a single, albeit important, algorithmic task (modular addition). The generalizability of these findings to more complex tasks or natural language processing remains an open question.
  • Single-Layer RNN: The analysis is performed on a single-layer RNN. Extending this to multi-layer RNNs or more complex recurrent architectures like LSTMs or GRUs would be valuable.
  • Future Work: The authors suggest investigating the factors that lead to this sparse, low-rank structure in RNNs. They also propose exploring how these insights can be applied to understanding more complex group operations and transformations in practical settings. Further research into the precise relationship between singular vectors and frequencies in all layers, beyond the unembedding matrix, is also a promising direction.

Summary updated

Abstract

Modular addition tasks serve as a useful test bed for observing empirical phenomena in deep learning, including the phenomenon of \emph{grokking}. Prior work has shown that one-layer transformer architectures learn Fourier Multiplication circuits to solve modular addition tasks. In this paper, we show that Recurrent Neural Networks (RNNs) trained on modular addition tasks also use a Fourier Multiplication strategy. We identify low rank structures in the model weights, and attribute model components to specific Fourier frequencies, resulting in a sparse representation in the Fourier space. We also show empirically that the RNN is robust to removing individual frequencies, while the performance degrades drastically as more frequencies are ablated from the model.
BibTeX
@inproceedings{rangamani2025low,
  author = {Akshay Rangamani},
  title = {{Low Rank and Sparse Fourier Structure in Recurrent Networks Trained on Modular Addition}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2025},
  doi = {10.1109/icassp49660.2025.10889827},
}
Figure