Emergence in non-neural models: grokking modular arithmetic via average gradient outer product
Authors: Neil Rohit Mallinar
Daniel Beaglehole
Libin Zhu
Adityanarayanan Radhakrishnan
Parthe Pandit
Mikhail Belkin
Venue: ICML 2025 oral (2025)
Keywords: Theory of deep learning
grokking
modular arithmetic
feature learning
kernel methods
average gradient outer product (AGOP)
emergence
Primary area: general_machine_learning->representation_learning
TL;DR: We show that "emergence" in the task of grokking modular arithmetic occurs in feature learning kernels using the Average Gradient Outer Product (AGOP) and that the features take the form of block-circulant features.

Abstract: Neural networks trained to solve modular arithmetic tasks exhibit grokking, a phenomenon where the test accuracy starts improving long after the model achieves 100% training accuracy in the training process. It is often taken as an example of "emergence", where model ability manifests sharply through a phase transition. In this work, we show that the phenomenon of grokking is not specific to neural networks nor to gradient descent-based optimization. Specifically, we show that this phenomenon occurs when learning modular arithmetic with Recursive Feature Machines (RFM), an iterative algorithm that uses the Average Gradient Outer Product (AGOP) to enable task-specific feature learning with general machine learning models. When used in conjunction with kernel machines, iterating RFM results in a fast transition from random, near zero, test accuracy to perfect test accuracy. This transition cannot be predicted from the training loss, which is identically zero, nor from the test loss, which remains constant in initial iterations. Instead, as we show, the transition is completely determined by feature learning: RFM gradually learns block-circulant features to solve modular arithmetic. Paralleling the results for RFM, we show that neural networks that solve modular arithmetic also learn block-circulant features. Furthermore, we present theoretical evidence that RFM uses such block-circulant features to implement the Fourier Multiplication Algorithm, which prior work posited as the generalizing solution neural networks learn on these tasks. Our results demonstrate that emergence can result purely from learning task-relevant features and is not specific to neural architectures nor gradient descent-based optimization methods. Furthermore, our work provides more evidence for AGOP as a key mechanism for feature learning in neural networks.

Emergence in Non-Neural Models: Grokking Modular Arithmetic via Average Gradient Outer Product
Neil Mallinar' 12
Daniel Beaglehole"
Libin Zhu'
Adityanarayanan Radhakrishnan' 2 Parthe Pandit
Mikhail Belkin 4
Abstract
Arruracy
Neural networks trained to solve modular arith- metic tasks exhibit grokking, the phenomenon where the test accuracy improves only long after the model achieves 100% training accuracy in the training process. It often taken as an exam- ple of "emergence", where model ability mani- fests sharply through phase transition. In this work, show that the phenomenon of grokking is not specific to neural networks nor to gradi- ent descent- based optimization. Specifically, we show that grokking occurs when learning modu- lar arithmetic with Recursive Feature Machines (RFM), an iterative algorithm that uses the Av- erage Gradient Outer Product (AGOP) to able task-specific feature learning with kernel ma- chines. We show that RFM and, furthermore, neu- ral networks that solve modular arithmetic learn block-cireulant features transformations which implement the previously proposed Fourier multi- plication algorithm.
50-
10
15
20
25
30
Square Loss
0.0175
0.8125
0.0100
0.0000
RFM Iterations
Learned Feature (AGOP) Matrices
Figure 1. Recursive Feature Machines grok the modular arithmetic task (* (x, = (ar + y) mod 59.
the simplest, most striking examples supporting this idea "grokking" modular arithmetic (Power et al., 2022; Nanda et al., 2023). A neural network trained predict modular arithmetic operations on fixed data set rapidly transitions from near-zero to perfect (100%) test accuracy at a certain point in the optimization process. Surprisingly, this tran- sition point occurs long after perfect training accuracy is achieved. Not only is this contradictory to traditional wis- dom regarding overfitting but, of grokking do not fit neatly with modern understanding of "benign overfitting" (Bartlett et al., 2021; Belkin, 2021).
1. Introduction
In recent years the idea of "emergence" has become an important narrative in machine learning. While there is no broad agreement the definition (Rogers & Luccioni, 2023), it is often argued that "skills" emerge during the training process once certain data size, compute, or model size thresholds are achieved (Wei et al., 2022; Arora & Goyal, 2023). Furthermore, these skills are believed to ap- pear rapidly, exhibiting sharp and seemingly unpredictable improvements in performance at these thresholds. One of
will show, some aspects
Despite large amount of recent work on emergence and, specifically, grokking, (see, e.g., (Power et al., 2022; Liu et al., 2023; Nanda al., 2023; Thilak et al., 2022; Furuta et al., 2024: Miller al., 2024)), the nature and existence of the emergent phenomena remains contested. The recent pa- per (Schaeffer et al., 2023) suggests that the rapid emergence of skills may be a "mirage" due to the mismatch between the discontinuous metrics used for evaluation, such as accuracy, and the continuous loss used training. The authors argue that, in contrast to accuracy, the test (or validation) loss or some other suitably chosen metric may decrease gradually
'Deaarmeent Computer Science and Engincering, UC San Diego, La Jolla, CA, USA 'The Broad Institute of MIT and Harvard, Cambridge, MA, USA 'IIT Bombay, Mumbai, Maha- rashtra, India 'Halıcooğlu Data Science Institute, UC San Diego, La Jolla, CA, USA. Correspondence to: Neil Mallinar <nmal- @ ucs..
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Emergence in Non-Neural Models: Grokking Modular Arithmetic via Average Gradient Outer Product
Accuracy Loss
is not predicted by training or test loss let alone accuracy.
Accuracy
(%)
Specifically, we show grokking for Recursive Feature Ma- chines (RFM) (Radhakrishnan et al., 2024a), an algorithm that iteratively uses the Average Gradient Outer Product (AGOP) to enable task-specific feature learning in general machine learning models. In this work, we use RFM to en- able feature learning kernel machines, which are a class of predictors with no native mechanism for feature learning, In this setting, RFM iterates between three steps: (i) training kernel machine, J. to fit training data; (ii) computing the AGOP matrix of f. M, over the training data to extract task-relevant features; and (iii) transforming input data, I, using the learned features via the map x + M x for a matrix power 8 > (see Section for details).
35
28
25
30
That
Loss
0.26
8,011
0.233
Text Loss of Correct Output
10
25
20
23
30
20
1.00
Class
0.75
0.30
25
RFM Iterations
RPM Iterations
Progress Measures
ACDP Circulant Algnmmet
Devitlion
25
0.50
In Fig. we give an example of RFM grokking modular addition, despite not using any gradient-based optimization methods and achieving numerically zero training loss at every iteration. During the first few iterations both the test loss and and test accuracy remain at the constant (random) level. Around iteration 10 the test loss starts improving and, few iterations later, test accuracy quickly transitions to 100%. We also observe that early in the iteration, structure emerges in AGOP feature matrices (see Fig. 1). The gradual appearance of structure in these feature matrices is striking given that the training loss is identically zero at every iter- ation and the test loss does not significantly change until iteration 8. The striped patterns observed in feature matrices correspond to matrices whose sub-blocks are circulant with entries that are constant along the "long" diagonals which wrap around the matrix. 2 Such circulant feature matrices are key to learning modular arithmetic. In Section 3 we demonstrate that standard kernel machines using random circulant features easily learn modular operations. As these random circulant matrices are generic, we argue that no additional structure required to solve modular arithmetic.
25
10 15
RFH Iterations
RFH Iterations
Add
Figure 2. RFM with the quadratic kernel on modular arithmetic with modulus p = 61 trained for 30 iterations. (A) Test accuracy, test loss (mean squared error) over all output coordinates, and test loss of the correct class output coordinate do not change in the first 8 iterations and then, sharply transition. (B) Circulant deviation and AGOP alignment show gradual progress towards generalizing solutions despite accuracy and loss metrics not changing in the initial iterations. For division (Div), circulant deviation is measured with respect to the feature sub-matrices after reordering by the discrete logarithm. Plots for subtraction (Sub) and multiplication (Mul) are in Appendix Figure
throughout training and thus provide a useful measure of progress. Another possible progress measure the train- ing loss. As SGD-type optimization algorithms generally result in a gradual decrease of the training loss, one may posit that skills appear once the training loss falls below certain threshold in the optimization process. Indeed, such a conjecture is in the spirit of classical generalization theory, which considers the training loss to be a useful proxy for the test performance (Mohri et al., 2018).
To demonstrate that the feature matrices evolve toward this structure (including for multiplication and division under appropriate re-ordering of the input coordinates), we introduce two "hidden progress measures" (Barak et al., 2022): (1) Circulant deviation, which measures constancy of the diagonals of a matrix, and (2) AGOP alignment, which measures similarity between the feature matrix at iteration and the AGOP of a fully trained model. We will see that both of these measures show gradual (initially nearly linear) progress toward a model that generalizes.
In this work, we show that sharp emergence in modular arithmetic arises entirely from feature learning, indepen- dently of other aspects of modeling and training, and is not predicted by standard measures of progress. We then clarify the nature of feature learning leading to the emergence of skills in modular arithmetic. We discuss these contributions in further detail below.
We further argue that emergence in fully connected neural networks trained on modular arithmetic identified in prior
Summary of the contributions. We demonstrate empiri- cally that grokking modular arithmetic: (1) is not specific to neural networks (to the best of our knowledge, no prior work shows a non-neural model that learns modular arithmetic); (2) is not tied to gradient-bard based optimization methods; (3)
We note that for neural networks trained by SGD, emergence cannot be decoupled from training loss, as non-zero loss is required for training to occur at all.
FFetture sub-mane matrices may also be constant on anti-diagonals. We also refer to these matrices circulant.
2

---

Emergence in Non-Neural Models: Grokking Modular Arithmetic via Average Gradient Outer Product
work (Gromov, 2023; Liu et al., 2022) is analogous to that for RFM and is exhibited through the AGOP (see Section 4). By visualizing covariances of network weights, we observe that these models also learn clock-cireulant features for modular arithmetic. We demonstrate that these features are highly correlated with the AGOP of neural networks, cor- roborating prior observations from (Radhakrishnan et al., 2024a). Paralleling our observations for RFM, our progress measures indicate gradual progress toward generalizing solution during neural network training. Finally we demon- strate that training neural networks on data transformed by random block-circulant matrices dramatically decreases training time needed to learn modular arithmetic.
Complex inner product and Discrete Fourier Transform. In our theoretical analysis in Section 5, we will utilize the following notions of complex inner product and DFT. The complex inner product (+, 1) is map from Ca x C + C
of the form
v) = u D
(I)
where 8y is the complex conjugate of uj. Let = v=I and
let w = exp( -2m
- ) The DFT is the map F : Cd - Cd of
the form F(u) = Fu, where F E Cdxd is a unitary matrix
with Fiy = va 30 In matrix form, F is given as
1
1
Why are these learned block circulant features effective for modular arithmetic? We provide supporting theoretical evidence that circulant features result in kernel machines implementing the Fourier Multiplication Algorithm (FMA) for modular arithmetic (see Section 5). For the case of neu- ral networks, several prior works have argued empirically and theoretically that neural networks learn to implement the FMA to solve modular arithmetic (Nanda et al., 2023; Varma et al., 2023; Morwani et al., 2024). While kernel RFM and neural networks utilize different classes of predic- tive models, our results suggest that they discover similar algorithms for implementing modular arithmetic.
1
w
w²
wa-1 w
F
1
1
w²
w
vd
:
we-1
wi(d-1)
wid-1)(d-1)
Circulant matrices. The features that RFMs and neural networks learn in order to solve modular arithmetic contain blocks of circulant matrices, which are defined as follows. Let a : IRP - R2P be the cyclic permutation which acts on vector u IRP by shifting its coordinates by one cell to the right: [or(w]],
modp- for E [p]. We write the f-fold composition of this map o((u) E R with entries [o (w)l, = - mood p. A circulant matrix C' E IRP*P is de- termined by a vector e (in order from first to last): c, cc) ( (c). Feature matrices may also have have constant anti-diagonals ("Han- kel matrices").. To ease terminology, we will use the word circulant to refer to both Hankel and circulant matrices.
By decoupling feature learning from predictor training, our results provide evidence for emergent properties of machine learning models arising purely as a consequence of their ability to learn features. We hope our work will help isolate the underlying mechanisms of emergence and shed light on the key practical concern of how, when, and why these seemingly unpredictable transitions occur.
Cp-1 E IR?, and has rows
2. Preliminaries
Average Gradient Outer Product (AGOP). The AGOP matrix is central to our discussion and defined as follows.
Learning modullr arithmetic. Let Z,p = Z/pZ denote the field of integers modulo a prime p and let 23 Ep MO). We learn modular functions (a b) = g(a, b) mod p where I" Zp x Zp + Zp. a,b b Zp. and g 2 x Z- + Z is an arithmetic operation on a and b, e.g. b(a.b) = a a+ b. Note that there are p² discrete input pairs (a, b) for all modular operations except for (a = (a = b) mod p. which has p(p - 1) inputs as the denominator cannot be O.
Definition 2.1 (AGOP). Given a predictor f Rd + R with e outputs, f(x) = [f((=)..... Se- (z)], let 0f(a') Raxe be the Jacobian (transposed) of f evaluated at some point x' E Bd with entries (2f(=') ]s.8 = ds.
dx
0f((='), Then, for
f trained on set of data points (2(1)) 1 with x(1) Rd. the Average Gradient Outer Product (AGOP), G E Radd is defined as,
To train models on modular arithmetic tasks, we construct input-label pairs by one-hot encoding the input and label integers. Specifically, for every pair a, E Zyp. we write the input as ea @ eb E 2 and the output as (a.().)) E RP, where e; E RP is the i-th standard basis vector in p dimensions and + is concatenation. The training dataset consists of random subset of n = r N input/label pairs, where r is the training fraction and N = r² or p(p 1) is the number of possible discrete inputs.
0f(x00) 0f(x(0) T
1 Σ n
(3)
dx
8x
For simplicity, we omit the dependence on the dataset in the notation. Top eigenvectors of AGOP can be viewed as the "most relevant" input features, those input directions that influence the output of a general predictor (for example, a kernel machines or a neural network) the most. As a consequence, the AGOP can be viewed as task-specific
3

---

Emergence in Non-Neural Models: Grokking Modular Arithmetic via Average Gradient Outer Product
transformation that can be used amplify relevant features and improve sample efficiency of machine learning models.
Learned Feature Matrices (AGOP)
Indeed, a line of prior works (Yuan et al., 2023; Trivedi et al., 2014; Hristache et al., 2001) have used the AGOP to improve the sample efficiency of predictors trained on multi-index models, a class predictive tasks which the target function depends on a low-rank subspace of the data. Though the study of AGOP has been motivated by these multi-index examples, will see that the AGOP can be used to recover useful features for modular arithmetic that are, in fact, not low-rank.
Add
Mul (original)
Div (original)
c
AGOP and feature learning in neural networks. (Rad- hakrishnan et al., 2024a) posited that AGOP was a mech- anism through which neural networks learn features. The authors introduce the Neural Feature Ansatz (NFA) stating that for any layer E of a trained neural network with weights Wr. the Neural Feature Matrix (NFM), W W;, are highly correlated to the AGOP of the model computed with respect to the input of layer f. The NFA suggests that neural net- works learn features at each layer by utilizing the AGOP. For more details on the NEA, see Appendix C.
Sub
Mul (reordered)
Div (reardered)
Figure 3. RFM with the quadratic kernel for modular arithmetic with p 61. (A) The square root of the kemel AGOPs for addition (Add), subtraction (Sub) visualized without their diagonals to emphasize the off-diagonal blocks. (B) Square root of the kemel AGOP for multiplication (Mul), division (Div). (C) For Mul and Div, rows and columns of each sub-matrix is re-ordered by the discrete log. base 2.
Recursive Feature Machine (RFM). Importantly, AGOP can be computed for any differentiable predictor, includ- ing those such as kernel machines that have no native fea- ture learning mechanism. As such, the authors of (Rad- hakrishnan et al., 2024a) developed an algorithm known as RFM, which iteratively uses the AGOP to extract fea- tures. Below, we present the RFM algorithm used in con- junction with kernel machines. Suppose we given data samples (X,v) E iR x IK" where X contains n samples denoted {1(())
multiplication, and division) due to the emergence of block- circulant features.
We will use a modulus of p = 61 and train RFM with quadratic and Gaussian kernel machines (experimental de- tails are provided in Appendix D). As we solve kernel ridge- less regression exactly, all iterations of RFM result in zero training loss and 100% training accuracy. The top two rows of Fig. 2A show that the first several iterations of RFM result in near-zero test accuracy and approximately constant, large test loss. Despite these standard progress measures initially not changing, continuing to iterate RFM leads to dramatic, sharp increase to 100% test accuracy and a corresponding decrease in the test loss later in the iteration process.
Jj=1. Given initial symmetric positive-definite matrix Mo E _ddd and Mahalanobis ker- nel :(.,;;)) Rd Rd + R, RFM iterates the following steps for / E (T):
Step (Predictor training): (z) X;; M,)a (4)
with a = k((X, Mc) M Step 2 (AGOP update): M411 = [G(;()))s
(5)
(6)
Sharp transition in loss of correct output coordinate. is important to note that our total loss function is the square loss averaged over p 61 classes. It is thus plausible that, due to averaging, the near-constancy of the total square loss over the first few iterations conceals steady improvements in the predictions the correct class. However, in Fig. 2A we show that the test loss for the output coordinate of the correct class closely tracks the total test loss.
where > 0 is matrix power and k(X,X; E Raxe denotes the matrix with entries [& X; M;]Miu = k(x (0) M) for j1.32 E [n]. In this work, we se- lect = for all experiments (see Algorithm I for complete pseudocode). We use the following two Maha- lanobis kernels: (1) the quadratic kernel, k(x, a/; M) = (I.TMe Ma')² and (2) the Gaussian kernel k(x, M) = exp (-11x z' /l2, LL), where for Rd ||=||3r 2 M2, and L is the bandwidth.
Emergence of block-cireulant features in RFM. To under- stand RFM generalization, we visualize the 2p x 2p feature matrix given by the square root of the AGOP from the final iteration of RFM. We first visualize the feature matrices for RFM trained on modular additionn/sbbraation in Fig. 3A. Their visually-evident striped structure suggests a more pre- cise characterization:
3. Emergence with RFM
We now show that RFM exhibits sharp transitions in perfor- mance on modular arithmetic tasks (addition, subtraction,

---

Emergence in Non-Neural Models: Grokking Modular Arithmetic via Average Gradient Outer Product
Observation 1 (Block-circulant features). Feature matrix
Add
Mul
M E 22xx22 the final iteration of RFM on modular addition/subrraction is of the form
Test Aicuree rccureeyy (t)
100
100
Tess Accuracy
75
30
A CC C
M
)
where A, C' E RRxp, C' is an asymmetric circulant matrix., A = 4 / + c2 for scalars CI, C2.
0.030
0.030
Test Loss
0.025
0.025
0.070
Similarly to addition and subtraction, RFM successfully learns multiplication and division. Yet, in contrast to addi- tion and subtraction, the structure of feature matrices for these tasks, shown in Fig. 3B, is not at all obvious. Nev- ertheless, re-ordering the rows and columns of the feature matrices for these tasks brings out their hidden circulant structure of the form stated in Eq. (7). We show the ef- feet of re-ordering in Fig. 3C (see also Appendix Fig. 2 for the evolution of re-ordered and original features during training).
0.015
0015
0,930
Training fraction
Training fraction
RFM
Sandom Circu Komel
Figure 4. Random circulant features generalize with standard ker- nels for modular arithmetic. RFM with the Gaussian kernel on addition (Add) and multiplication (Mul) for modulus compared a base Gaussian kemnel machine trained on random circulant features (for Mul, the sub-blocks are circulant after re- ordering by the discrete logarithm base 2).
61 is
We briefly discuss the reordering procedure below and pro-
vide further details in Appendix F. To reorder, we use the fact of group theory that the multiplicative group ž eyclic group of order p - 1 (e.g.. (Koblitz, 1994)). By definition of the cyclic group, there exists at least one element 9 E Zy.. known as generator, such that z = =9¹; i {I....,, - 13}. As we will see, re- ordering the rows and columns of the AGOP by powers of generator reveals circulant structure. For modular mul- hiplication/division, the map taking 9 to i is known as the discrete logarithu base (Koblitz, 1994, Ch.3). It is natural to expect block-circulant feature matrices to arise in modu- lar multiplication/ddviiioon after reordering by the discrete log as the discrete log converts modular multiplication/diii- sion into modular addiition/subrraction. We note the recent work (Doshi et al., 2024) also used the discrete log to order coordinates in the context of constructing a solution for solving modular multiplication with neural networks.
We see in Fig. 2B that circulant deviation exhibits gradual improvement through the course of training with RFM. We find that for the first 10 iterations, while the training loss is numerically zero and the test loss does not improve, circu- lant deviation exhibits gradual, nearly linear, improvement. The improvements in circulant deviation reflect visual im- provements in features, as was also shown in Fig. 1. These curves provide further support for Observation 1, as circu- lant deviation is close to 0 at the end of training.
Circulant deviation depends crucially on the observation that for modular arithmetic the feature matrices contained circulant blocks. For more general tasks, we may not be able identify such structure. Thus, we propose second, more general progress measure, AGOP alignment.
AGOP alignment. Given two matrices A, B E Raxd let P(A, B) denote the standard cosine similarity between these two matrices when vectorized. Specifically, let Á, B E dd denote the vectorization of A and B respectively, then (A.8) p(A, B) [|]][[]]]
Progress measures. We propose two measures of feature learning, circulant deviation and AGOP alignment.
Circulant deviation. As the final feature matrices contain cireulant sub-blocks, a natural progress measure for learning modular arithmetic with RFM is how far AGOP feature ma- trices are from a block-circulant matrix. For a feature matrix M, let A denote the bottom-left sub-block of M. We define circulant deviation as the total variance of the (wrapped) diagonals of A normalized by the norm |/. In particular, let S R2 + Rexp denote the shift operator, which shifts the f-th row of the matrix by positions to the right. Also let Var(v)
If M, denotes the AGOP at iteration & of RFM (or epoch of a neural network) and M denotes the final AGOP of the trained RFM (or neural network), then AGOP alignment at iteration t is given by p(M,, M The same measure of alignment was used in (Zhu et al., 2024), except their alignment was computed with respect the AGOP of the ground truth model. Note that modular operations discrete, in our setting there is no unique ground truth model for which AGOP can be computed.
2 (u, )² be the variance of vector v. If A[j] denotes the j-th column of A, we define cir- culant deviation D as: D(A)= मАح E (A)(S(A))i)). As circulant matrices are constant along their (wrapped) diagonals, they have a circulant deviation of 0.
Like circulant deviation, AGOP alignment exhibits gradual improvement in the regime that test loss is constant and large (see Fig. 2B, bottom row). Moreover, AGOP alignment
5

---

Emergence in Non-Neural Models: Grokking Modular Arithmetic via Average Gradient Outer Product
more general progress measure since it does not require assumptions the structure of the AGOP. For instance, AGOP alignment can be measured without reordering for modular mulliplicatioonddiviiion.. While AGOP alignment does not require a specific form of the final features, it is
A
Accuracy & Loss
Accuracy
(%)
still an a posteriori measurement of progress as it requires access to the features of a fully trained model.
Loss
0.01
0.01
0.00
Loss Correst Output Class
1.0
1,0
Random circulant features allow standard kernels to
0.5
generalize. We conclude this section by providing fur- ther evidence that the form of feature matrices given in Observation is key to enabling generalization in kernel machines trained to solve modular arithmetic tasks. We now show that a transformation with a generic block blok-circculant matrix enables kernels machines to learn modular arith- metic. We generate random circulant matrix C by first sampling entries of the first column i.idd from the uni- form distribution on [0, 1] C R and then shifting the col- umn to generate the remaining columns of C. We con- struct M* in Observation 1 with ei 1, C2 = 1/pp. For modular addition, we transform the input data by mapping Fab = Cg ( eb to Nab (M*)& rab and then train on the new data pairs (Zab, moddmodp) for a subset of all possible pairs (a,b) b) E - Note that transforming data with (M*)* is akin to using s 1/2 in RFM.
5.0
0.0
10
20
40
Epochs
Epoch
Train
Test
Progress Measures
Circulent Deviation
0.015
0.015
0.030
0.800
10
20
30
60
15
20
30
05
AGOP Algnment
1.0
1.0
0.0
20
20 Epochs
30
40
Epochs
Add
Div
Figure 5. One hidden layer fully-commected networks with quadratic activations trained on modular arithmetic with p 61 trained for 50 epochs with the square loss. (A) Test accuracy, test loss over all outputs, and test loss of the correct class output do not change in the initial iterations. (B) Progress measures for circulant deviation and AGOP alignment. Circulant deviation for Div is computed after reordering by the discrete logarithm base 2. Plots for Sub and Mul can be found in Appendix Figure 5.
We do the same for modular multiplication after reordering the random eirculant by the discrete logarithm described above. The experiments in Fig. 4 show that standard kernel machines trained on feature matrices with random circulant blocks outperform RFM that learns such features through AGOP. We also find that directly enforcing circulant blocks in the sub-matrices of M, throughout RFM iterations accel- crates grokking and improves test loss (see Appendix Ap- pendix Fig. 3). These experiments provide direct evidence that the structure in Observation I is key for generaliza- tion on modular arithmetic and, furthermore, no additional structure beyond a generic circulant is required.
with a training fraction 50%.
Consistent with prior work (Gromov, 2023) and analogously to RFMs, neural networks exhibit an initial training period where the train accuracy reaches 100% while test accuracy is at 0% and test loss does not improve (see Fig. 5A). After this point, we see that the accuracy rapidly improves to achieve perfect generalization. We further verify that the sharp transition in test loss is not an artifact of averaging the loss over all output coordinates. In the third row of Fig. 5A show that the test loss of the individual correct output coordinate closely tracks the total loss.
4. Emergence in Neural Nets through AGOP
We now show that grokking in two-layer neural networks relies on the same principles as grokking by RFM. Specif- ically demonstrate that (1)
Emergence of fleck-circulant features in neural net- works. To understand the features learned by neural net- works we visualize the first layer Neural Feature Matrix.
features are key to neural networks grokking modular arithmetic; and (2) our measures (circulant deviation and AGOP alignment) indicate gradual progress towards generalization, while stan- dard measures of generalization exhibit sharp transitions. All experimental details are provided in Appendix D.
Definition 4.1. (Neural Feature Matrix) Given a fully con- nected network f(x) a 6(W1z), the first layer Neural Feature Matrix (NFM) is the matrix W, W1 R29x2
Grokking with neural networks. We first reproduce grokking with modular arithmetic using fully-connected net- works as identified in prior works (Fig. 5A) (Gromov, 2023). In particular, we train one hidden layer fully connected net- works f 2 - TR of the form fz) = Wzø(W1a) with quadratic activation d0z)= = z" on modulus p- = 61 data
The NFM is the un-centered covariance of network weights and has been used in prior work in order to understand the features learned by various neural network architectures at any layer (Radhakrishnan et al., 2024a: Trockman et al., 2022). Fig. 6A displays the NFM for one hidden layer neu- ral networks with quadratic activations trained on modular
6

---

Emergence in Non-Neural Models: Grokking Modular Arithmetic via Average Gradient Outer Product
A
Add
NN
Random Circulant NN
Accuracy (%)
100
Accuracy (%)
75
50-
B
1200
2000
3030
1003
2000
3000
0.920
0.020
NN AGOP
Square Lass
0.015
Square
0.010-
0.005
0.005
Add
Di (reordered)
0.000
2000
3020
0.000
1002
3000
Epochs
Epochs
Figure Feature matrices from one hidden layer neural networks with quadratic activations trained addition and division modulo 61. The Pearson correlations between the NFM and square root of the AGOP for each task are 0.955 (Add), 0.929 (Div). Div is shown after reordering by the discrete logarithm base 2. Plots for Sub and Mul can be found in Appendix Figure 7.
Train
Test
Figure 7. Random circulant features speed up generalization neural networks for modular addition. We compare hidden layer MLPs with quadratic activations trained on modular addition and multiplication for p 61 using standard one one-hot encodings or those transformed by random circulant matrices. The same experiments for Mul are in Appendix Figure 9.
arithmetic tasks. For addiition/subbraction, find that the NFM exhibits block circulant structure, akin to the feature matrix for RFM. As described in Section 3 and Appendix E, we reorder the NFM for networks trained on multiplica- tion/division with respect to a generator for Σn in order to observe block-circulant structure (see Appendix Fig. 6A for comparison of multiplicationnddiissoon NFMs before and after reordering). The block-cireulant structure in both the NFM and the feature matrix of RFM suggests that the two models are learning similar sets of features.
transformed with random block-cireulant matrix. At a training fraction 17.5%, we find that networks trained on transformed integers achieved 100% test accuracy within several hundred epochs and exhibit little delayed generaliza- tion while networks trained on non-transformed integers do not achieve 100% test accuracy even within 3000 epochs.
Progress measures. Given that the square root of the AGOP of neural networks exhibits block-circulant structure, we use circulant deviation and AGOP alignment to measure progress of neural networks toward a generalizing solution. As before, we measure circulant deviation in the case of mul- tiplication/division after reordering the feature submatrix by generator of Zg. In Fig. 5B, we that measures indicate gradual progress in contrast to sharp transitions in the standard measures of progress shown in Fig. 5A. There is a period of 5-10 epochs where circulant deviation and AGOP alignment improve while test loss and test accuracy do not. As with RFM, these metrics reveal gradual progress of neural networks toward generalizing solutions.
The work (Radhakrishnan et al., 2024a) posited that AGOP the mechanism through which neural networks learn fea- tures. The authors stated their claim in the form of the Neural Feature Ansatz (NFA), which states that NFMs are proportional to matrix power of AGOP through training (see Eq. (15) for a restatement of the NFA). As such, we additionally compute the square root of the AGOP to ex- amine the features learned by neural networks trained on modular arithmetic tasks. We visualize the square root of the AGOPs of these trained models in Fig. 6B and also find that the square root of the AGOP and the NFM are highly correlated (greater than 0.92), where Pearson correlation is equal to cosine similarity after centering the inputs to be mean 0. Moreover, we find that the square root of AGOP of neural networks again exhibits the same structure as stated in Observation (see Appendix Fig. 6B for comparison of muliipiiaaiion/diviiion AGOPs before and after reordering).
5. Fourier Multiplication from Circulants
We have seen so far that features containing circulant sub- blocks enable generalization for RFMs and neural networks across modular arithmetic tasks. We now provide theo- retical support that shows how kernel machines equipped with such circulant features learn generalizing solutions. In particular, show that there exist circulatt feature matrices, as in Observation 1, such that kernel machines equipped with these features and trained on all available data for a given modulus p solve modular arithmetic through the Fourier Multiplication Algorithm (FMA). Notably, the FMA has been argued both empirically and theoretically in prior
Random circulant maps improve generalization of neu- ral networks. To further establish the importance and gen- erality of block-circulant features, we demonstrate that train- ing networks on inputs transformed with a random block- circulant matrix greatly accelerates learning. In Fig. 7, we compare the performance neural networks trained on one-hot encoded modulo p integers and the same integers

---

Our proof uses the well-known fact that circulant matri- ces can be diagonalized using the DFT matrix (Gray et al., 2006) (see Lemma J.2 for a restatement of this fact). This fundamental relation intuitively connects circulant features and the FMA. By using kernels with block-cireulant Ma- (10) halanobis matrices, we effectively represent the one-hot encoded data in terms of their Fourier transforms. We con- (11) jecture that this implicit representation is what enables RFM Emergence in Non-Neural Models: Grokking Modular Arithmetic via Average Gradient Outer Product
works to be the solution found by neural networks solve modular arithmetic (Nanda et al., 2023; Zhong et al., 2024). For completeness, we state the FMA for modular addition/- subtraction from (Nanda et al., 2023) below. While prior works write this algorithm in terms of cosines and sines, our presentation simplifies the statement by using the DFT.
Theorem 5.1. Given all of the discrete data {(ea @ Cb, Cia- (od- mod r) } yab-or for each output class E {0...., , --- 1}, suppose we train a separate kernel where k( Me) (i,,;MM))c
predictor fe(x)
is a quadratic kernel with Me ((OST 0
C
and
C E RPXP is a circulant matrix with first row e1. When ( is the solution to kernel ridgeless regression for each E, the kernel predictor f = [fo..... fp-1] is equivalent to Fourier Multiplication Algorithmm for modular subtraction (Eq. (14)).
Fourier Multiplication Algorithm for modular addi- tion/subtraction. Consider the modular addition task with (a, (a + b) modp. For a given input æ Fn @ 2[2] 20, the FMA generates a value for output class l, Vada (x; f), through the following computation:
1. Compute the Discrete Fourier Transform (DFT) for each digit vector 2 and Z[2]. which we denote Tn =
As C' is circulant, C is also circulant. Hence, each M, has the structure described in Observation 1, where A = 0. Note our construction differs from RFM in that we use a dif- ferent feature matrix My for each output coordinate, rather than a single feature matrix across all output coordinates. Nevertheless, Theorem 5.1 provides support for the fact that block-circulant feature matrices can be used to solve modular arithmetic.
F and mip = Fr where the matrix F is defined in Eq. (2).
2. Compute the dlement-wise product xn @ 3(2)-
3. Return vp- [ O [[) F where e, denotes ê-th standard basis vector and (s, 1)c denotes the complex inner product (see Eq. (1)).
We provide the proof for Theorem 5.1 in Appendix J. The argument for the FMA for addition (Eq, (8)) is identical provided we replace Ct with C* R and (C*) with (C* R) in each Me, where R is the Hankel matrix that reverses the row order (i.e. ones along the main anti-diagonal, zero's s elsewhere), whose first row is cp-1- An analogous result follows for multiplication and division under re-ordering by group element, as described in Section 3.
This algorithmic process can be written concisely in the following equation:
Yadd (r;; () = vD- (Frty @ Fei)e
(8)
Note that for x = ea + eb. the second step of the FMA
reduces to
1 - Fea @ Fe,
Fe m
(9)
vp
Using the fact that F is unitary matrix, the output of the FMA is given by
vp- ( He (a+b mod po Fez
=e(+ modp FT Fer
=e mod
T
(12) to learn modular arithmetic with more general circulant ma- trices when training on just fraction of the discrete data.
=I((a-b) mod p=t)
(13) Not only do neural networks and RFM learn similar features, we now have established setting where kernel methods equipped with block-cireulant feature matrices learn the same out-of-domain solution as neural networks on modular arithmetic tasks. This result is interesting as the only con- straint for generalization on these tasks is to obtain perfect accuracy on inputs that are standard basis vectors. As such functions can be extended arbitrarily over all of 2d there are infinitely many generalizing solutions where the particu- lar out-of-domain solution found by training is determined by the specifics of the learning algorithm. It is intriguing that dernel-RFM. and neural networks, which are clearly quite different algorithms, are both implicitly biased toward solutions that involve block-circulant feature matrices.
Thus, the output of the FMA is vector ((a+6)) mod which is equivalent to modular addition. We provide an example of this algorithm for p 3 3 in Appendix I.
Remarks. We note that our description of the FMA uses all entries of the DFT, referred to as frequencies, while the algorithm as proposed in prior works allows for utilizing a subset of frequencies. Also note that the FMA for subtrac- tion, written Ysub, is similar and given by
(oub(r;; 2) = vp- (Frn) C Fep-c-1, Femle (14)
Having described the FMA, we now state our theorem.
8

---

Emergence in Non-Neural Models: Grokking Modular Arithmetic via Average Gradient Outer Product
6. Discussion and Conclusions
principle leads to learning modular arithmetic from partial observations. There are many ways to fill in the missing data and we do not know simple inductive bias, to guide us toward a solution. Several recent works argued that margin maximization with respect to certain norms can account for learning modular arithmetic (Morwani et al., 2024; Lyu et al., 2023; Mohamadi et al., 2024). While the direction is promising, general underlying principles are not yet clear.
Most classical analyses of generalization relied on the train- ing loss serving as a proxy for the test loss and thus a useful measure of generalization. Empirical results of deep learn- ing have upended this long-standing belief. In many settings, predictors that fit the data exactly can still generalize, thus invalidating training loss as a predictor of test performance.
This has led to the recent developments in understanding benign overfitting, in neural networks as well as in classi- cal kernel and linear models (Belkin, 2021; Bartlett et al., 2021). Since the training loss may not predict generalization, the common suggestion has been use the validation loss computed on a separate validation dataset. Emergent phe- nomena, such as grokking, show that we cannot rely even on validation performance at intermediate training steps to pre- dict generalization at the end of training. Indeed, validation loss at a certain iteration may not be indicative of the valida- tion loss itself only a few iterations later. Further, contrary to (Schaeffer et al., 2023), we show these phase transitions in performance observe in this work, they are not always predicted by pri- ori measures of performance, continuous or discontinuous. Instead, emergence is fully determined by feature learning, which is difficult to observe without having access to a fully trained model. Indeed, the progress measures discussed in this work, as well as those suggested in, e.g., (Barak al., 2022; Nanda et al., 2023; Doshi et al., 2024) can be termed posteriori progress indicators. They all require either un- derstanding of the algorithm implemented by a generalizing trained model (such as our circulant deviation, the Fourier gap considered in (Barak et al., 2022), or the Inverse Par- ticipation Ratio in (Doshi et al., 2024)) or access to such a model (e.g. AGOP alignment).
Analyses of grokking. Recent works (Kumar al., 2024; Lyu et al., 2023; Mohamadi et al., 2024) argue that grokking occurs in neural networks through two phase mechanism that transitions from a "lazy" regime, with no feature learn- ing, to a "rich" feature learning regime. Our experiments clearly show that grokking in RFM does not undergo such transition. For RFM on modular arithmetic tasks, our progress measures indicate that the features evolve grad- ually toward the final circulant matrices, even as test per- formance initially remains constant (Fig. 2). Grokking in these settings is entirely due to the gradual feature quality improvement and two-phase grokking does not occur. Addi- tionally, we have not observed significant evidence of "lazy" to "rich" transition as a mechanism for grokking in our ex- periments with neural networks, as most of our measures of feature learning start improving early on in the training process (improvement in circulant deviation measure is de- layed for addition and subtraction, but not for multiplication and division, while AGOP feature alignment initially shows near linear improvement for all tasks), see Fig. 5, Our ob- servations for neural networks are in line with the results in (Doshi et al., 2024; Nanda et al., 2023), where their pro- posed progress measures, Inverse Participation Ratio and Gini coefficients of the weights in the Fourier domain, are shown to increase prior to improvements in test loss and accuracy for modular arithmetic.
not generally "a mirage" since, as we
Consider generalizing features for modular multiplication shown in Fig. 3. The original features shown in panel B of this figure do not have an casily identifiable pattern. In con- trast, re-ordered features in panel C are clearly striped, con- taining block-circulants. As discussed in Section 3, reorder- ing of features requires understanding that the multiplicative group Σn cyclic of order p- - 1. While a well-known re- sult, it is far from obvious priori. It is thus plausible that in other settings hidden feature structures may be hard to identify due to a lack of mathematical insight.
Furthermore, as grokking modular arithmetic occurs in a kernel model equipped with a linear feature learning mech- anism, a general explanation for grokking cannot depend mechanisms that are specific to neural networks. There- fore explanations for grokking that depend on the magni- tude of the weights, neural circuit efficiency, or specific optimization methods, for example, cannot account for the phenomena described in our work.
Conclusions. In this paper, we showed that grokking modu- lar arithmetic happens in feature learning kernel machines in a manner very similar to what has been observed in neural networks. Remarkably we observe that feature learning can happen independently of improvements in both training and test loss. Not only does this finding reinforce the narrative of rapid emergence of skills in neural networks, it is also not easily explicable within the framework of the existing generalization theory.
Why is learning modular arithmetic surprising? The task of learning modular operations is different from many other statistical machine learning tasks. In continuous ML settings, we typically posit that the "ground truth" target function is smooth in an appropriate sense. Hence any gen- eral purpose algorithm capable of learning smooth functions (such as, for example, k-nearest neighbors) should be able to learn the target function given enough data. Primary dif- ferences between lcarning algorithms are thus in sample and computational efficiency. In contrast, it is unclear what
9

---

Emergence in Non-Neural Models: Grokking Modular Arithmetic via Average Gradient Outer Product
Impact Statement
learn representations with gradient descent, In Confer- ence Learning Theory, pp- 5413-5452. PMLR, 2022, URL htt.s: httts::/arxiv.onrt
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Davies, X., Langosco, L.., and Krueger, D. Unifying grokking and double descent. ML
ML Safety Workshop, 36th Conference on Neural Information Processing Systems (NeurIPS 2022), 2023. httttt://azake abs 2bbs/2303.00 06173.
References
Ardeshir, N., Hsu, D. J., and Sanford, C. H. Intrinsic di- mensionality and generalization properties of the r-norm inductive bias. In Neu, G. and Rosasco, I.. (eds.). Pro- ceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Re- search, pp. 3264-3303, PMLR, 12-15 Jul 2023. URL https: /appsi//aaxvv..o wwtppdttg//oooooooooopoppppttptp pd 2206 05317.
Doshi, D., He, T., Das, A., and Gromov, A. Grokking mod- ular polynomials. International Conference on Learning Representations (ICLR): BGPT Workshop, 2024. URL 03495.
https://arxiv.ot
Furuta, H., Minegishi, G., Iwasawa, Y., and Matsuo, Y. Interpreting grokked transformers in complex modular arithmetic. arXiv preprint arXiv:2402. 16726, 2024. URL http://ccxi....rr/////2/222.11.
Arora, S. and Goyal, A. A theory for emergence of complex skills in language models. arXiv preprint arXiv:2307.15936, 2023. URL https://arxix. org/pdf/2307. 15936.
Gray, R. M. et al. Toeplitz and circulant matrices: A re- view. Foundations and Trends@ in Communications and Information Theory, 2(3):155-23,, 2006. URL https:
Barak, B., Edelman, B., Goel, S., Kakade, S., Malach, E.,, and Zhang, C. Hidden progress in deep learning: Sgd learns parities near the computational limit. Advances in Neural Information Processing Systems, 35:21750- 21764, 2022. URL pdffid=8xxi 2ewxx- i.m.
s/ee.stanford -aaplaa/grrrrrraa wttp:////aaaaagaaeeeeeeeeeeeeeee pdf.
Gromov, A. Grokking modular arithmetic. arXiv preprint urXiv:2301.02679) 2023. URL https: /arxiv.
ozg/pdf/2301. 02677
Bartlett, L., Montanari, A., and Rakhlin, A. Deep learning: statistical viewpoint, Acta numerica. 30:87-201, 2021. URL wwt.tttpp:/:/ http://////wwww..////////o/ 22103. 091 77.
Gunasekar, S., Woodworth, B. E., Bhojanapalli, S., Neyshabur, B., and Srebro, N. Implicit regularization in matrix factorization. Advances in neural information processing systems, 30, 2017.
Beaglehole, D., Radhakrishnan, A., Pandit, P., and Belkin, M. Mechanism of feature learning in convolutional neural networks. arXiv preprint arXiv:2309.0005777 2023. URL https: /taes://arxiine /ttwxvxxvvv//////////e//////at wwwpax/wwwog/////////3/333 wtt/po//g////ooooo http:://dd2223.00/0// 00570.
Hoffman, J., Roberts, D. A., and Yaida, S. Robust learning with jacobian regularization. arXiv preprint 5(6):7, 2019.
Beaglehole, D., Mitliagkas, I., and Agarwala, A. Feature learning aligmment: structural property of gradient descent in non-lr neural networks. arXiv preprint arXiv:2402.05271, 2024a. URL //rtps://rxxiv. brg/pddf/4402.05
Hristache, M., Juditsky, A., Polzehl, J., and Spokoiny, V. Structure adaptive approach for dimension reduction. An- nals of Statistics, pp. 1537-1566, 2001. URL https: / //doi. ort. /221/////////1/45555444
Beaglehole, D., Súkeník, P., Mondelli, M., and Belkin, M. Average gradient outer product mechanism for deep neural collapse. arXiv preprint arXIw:2402.13728 2024b. URL /tR.htttss://axxiv... http:////aavi..oo///////////
Koblitz, N. course number theory and cryptography, volume 114. Springer Science & Business Media, 1994.
Kumar, T., Bordelon, B., Gershman, S. J., and Pehlevan, C. Grokking as the transition from lazy to rich training dy- namics. International Conference on Learning Represen- tations (ICLR), 2024. URL https://openzeviier
Belkin, M. Fit without fear: remarkable mathematical phenomena deep learning through the prism of in- terpolation. Acta Numerica, 30:203-225 248, 2021. URL https:/ https://arxiv.. www.iii..rg/pppee wttp/oo//////oooo/ooo 14368.
Liu, Z., Kitouni, O., Nolte, N. S., Michaud, E., Tegmark, M. and Williams, M. Towards understanding grokking
Damian, A., Lee, J., and Soltanolkotabi, M. Neural networks
10

---

Emergence in Non-Neural Models: Grokking Modular Arithmetic via Average Gradient Outer Product
An effective theory of representation learning. Advances in Neural Information Processing Systems, 35:34651- 34663, 2022.
Parkinson, S., Ongie, G., and Willett, R. Relu neural net- works with linear layers biased towards single- and multi-index models. arXiv preprint wrXiv:2305.1596 2023. URL https: /ttpiiiiiii../..i//aaaaaaaaaa..a org/ 2305. 15598.
Liu, Z., Michaud, E. J., and Tegmark, M. Omni- grok: Grokking beyond algorithmic data. Interna- tional Conference on Learning Representations (ICLR), 2023. URL detps://openzewee id=zDiHoIWa0q1..
Power, A., Burda, Y. Edwards, H., Babuschkin, I., and Misra, Grokking: Generalization beyond overfit- ting small algorithmic datasets. arXiv preprint arXiv:2201.02177 2022.
net/pdE?
Lyu, K., Jin, J., Li, 7., Du, S. S., Lee, J. D., and Hu, W. Dichotomy of early and late phase implicit biases can provably induce grokking. In The Twelfth Interna- tional Conference on Learning Representations (ICLR), 2023. URL https: haap::///peereee operreviee nwt/ forum? id (d=XsHqrrdEGH:
Radhakrishnan, A., Beaglehole, D., Pandit, P., and Belkin, M. Mechanism of feature learning in deep fully con- nected networks and kernel machines that recursively learn features. arXiv preprint arXiv:2212.138811 2022.
Radhakrishnan, A., Beaglehole, D., Pandit, P., and Belkin, M. Mechanism for feature learning in neural networks and backpropagattion--feee machine learning models. Sci- ence, 1461 2024a. doi: 10.1126/
Miller, J., O'Neill, C., and Bui, T. Grokking beyond neural networks: An empirical exploration with model com- plexity. Transactions on Machine Learning Research (TMLR), 2024. URL http::://ppeeevveew. n PdfFid=ux9BrxPC116
science.adi5639. URL https: /www. www.wce...c...e...mmmm.o. org/doi/abs/ 1120/ ad156333....
Mohamadi, M. A., Li, Z., Wu, L., and Sutherland, D. J. Why do you grok? theoretical analysis on grokking modular addition. In Forty-first International Conference on Machine Learning (ICML), 2024. URL https:// openreview wttpeevwwwwwwweeeereeeeeeeee
Radhakrishhan, A., Belkin, M., and Drusvyatskiy, D. Linear recursive feature machines provably recover low-rank matrices. arXiv preprint a0t.::201.000000000000000 2024b. URL 04553.
d-ad5I 6No9G1.
Rogers, and Luccioni, S. Position: Key claims in Ilm research have a long tail of footnotes. In forty-first Inter- national Conference Machine Learning. 2023. URL https: http://axxwww.ppp......
Mohri, M., Rostamizadeh, A., and Talwalkar, Founda-
fions of machine learning. MIT Press, 2018
Moitra, A. Algorithmic aspects of machine learning. Cam- bridge University Press, 2018.
Schaeffer, R., Miranda, B., and Koyejo, S. Are emergent abilities of large language models a mirage? Thirty- seventh Conference on Neural Information Processing Systems, 2023. URL https: wpppreveeeeeeeeeeeeeeeeeee net
Morwani, D., Edelman, B. L., Oncescu, C.-A., Zhao, R., and Kakade, S. Feature emergence via margin maximization: case studies in algebraic tasks. In- ternational Conference on Learning Representations (ICLR), 2024. URL https:/ /ttps:///ppeevvieeeeee wwt.nreeeeeeeeeeeee/eeemm pdf?id-19wDX855
Thilak, V., Littwin, E., Zhai, S., Saremi, O., Paiss, R., and Susskind, J. The slingshot mechanism: An em- pirical study adaptive optimizers and the grokking phenomenon. arXiv preprint arXiv:2206. 048/7, 2022. URL https:://///.. http///axivv/./////////////..avl orgg abs//////////// /abba/2200 /200./2220.002 04817.
Mousavi-Hosseini, A., Park, S., Girotti, M., Mitliagkas, I., and Erdogdu, M. A. Neural networks efficiently learn low-dimensional representations with sgd. arXiv preprint arXiv:2209.14860 2022. URL https:// arxiv. wpxivvorg/pdf/2200 14863.
Trivedi, S., Wang, J.. Kpotufe, S., and Shakhnarovich. G. A consistent estimator of the expected gra- dient outerproduct. URL htttts::////e /wwww columbia. edu/-skk2175/ Papers/GO8 BTAG:/GOOPAAPPPPP
In UAI, pp. 819-828, 2014.
Nanda, N., Chan, L., Lieberum, T., Smith, J., and Stein- hardt, J. Progress measures for grokking via mech- anistic interpretability. International Conference on Learning Representations (ICLR), 2023. URL ht tps: // //ooperrevew... wwtp:/wwwww...ee.e.eeeeee p
Trockman, A., Willmott, D., and Kolter, Understanding the covariance structure of convolutional filters. arXiv preprint arXIv:2210.03655, 2022.

---

Emergence in Non-Neural Models: Grokking Modular Arithmetic via Average Gradient Outer Product
Varma, V., Shah, R., Kenton, Z., Kramár, J., and Ku- mar, R. Explaining grokking through circuit efficiency. International Conference Learning Representations (ICLR), 2023. URL https:/ /ttpas:s///enneeee..eeee pdf2id=77bg33nnR
Wei, J., Tay, Y. Bommasani, R., Raffel, C., Zoph, B., Borgeaud, S., Yogatama, D., Bosma, M., Zhou, D., Metzler, D., Chi, E. H., Hashimoto, T., Vinyals, O., Liang, P. Dean, J., and Fedus, W. Emergent abili- ties of large language models. Trunsactions on Ma- chine Learning Research (TMLR), 2022. URL ht https: // //openrvieww http wttp://dddddyysss5ddde
Yuan, G., Xu, M., Kpotufe, S., and Hsu, D. Efficient estima- tion of the central mean subspace via smoothed gradient outer products. arXiv preprint arXi::2312 15469, 2023. URL https:/// /ttps:///arxvvi org pdfp 15469, 69.
Zhong, Z., Liu, Z., Tegmark, M., and Andreas, J. The clock and the pizza: Two stories in mechanistic explanation of neural networks. Advances Neural Information Processing Systems, 36, 2024.
Zhu, I.., Liu, C., Radhakrishnan, A., and Belkin, M. Cata- pults in sgd: spikes in the training loss and their impact on generalization through feature learning. International Conference on Machine Learning (ICML), 235, 2024.
12

---

Emergence in Non-Neural Models: Grokking Modular Arithmetic via Average Gradient Outer Product
Algorithm 1 Recursive Feature Machine (RFM) (Radhakrishnan et al., 2024a)
Require: X. y, k, T,
Train data: (X, y), base kernel: k. iters.: T, matrix power: s, and bandwidth:
Mo Td
, 111e0 do for 1 .....,
Solve t Mi)
> (z)
M++1 f [G
end for return a; MT
Solution to kernel regression: a, and feature matrix: Mr-1
A. Additional discussion
Low rank learning. The problem of learning modular arithmetic can be viewed as a type of matrix completion completing the p x p matrix (so-called Cayley table) representing modular operations, from partial observations. The best studied matrix completion problem is low rank matrix completion, where the goal is to fill in missing entries of low rank matrix from observing subset of the entries (Moitra, 2018, Ch.8). While many specialized algorithms exist, it has been observed that neural networks can recover low rank matrix structures (Gunasekar et al., 2017). Notably, in a development paralleling the results of this paper, low-rank matrix completion can provably be performed by linear RFMs using the same AGOP mechanism (Radhakrishnan et al., 2024b).
thus tempting to posit that grokking modular operations in neural networks or RFM can be explained as low rank prediction problem. Indeed modular operations can be implemented by index 4 model, i.e., function of the form f = 9Ar), where R2D and A is rank 4 matrix (see Appendix K for the construction). It is plausible conjecture as there is strong evidence, empirical and theoretical, that neural networks are capable of learning such multi-index models (Damian et al., 2022: Mousavi-Hosseini et al., 2022) as well as low-rank matrix completion. Furthermore, a phenomenon similar to grokking was discussed in (Radhakrishnan et al., 2022, Fig. 5, 6) in the context of low rank feature learning for both neural networks and RFM. However, despite the existence of generalizeable low rank models, the actual circulant features learned by both Neural Networks and RFM are not low rank. Interestingly, this observation mirrors the problem of learning parity functions through neural network inspired minimum norm interpolation, which analyzed in (Ardeshir et al., 2023). While single-directional (index one) solutions exist in that setting, the authors show that the minimum norm solutions are all multi-dimensional.
Explanations for deep learning Finally, this work adds to the growing body of evidence that the AGOP- mechanisms of feature learning can account for some of the most interesting phenomena in deep learning. These include generalization with multi-index models (Parkinson et al., 2023), deep neural collapse (Beaglchole et al., 2024b), and the ability to perform low-rank matrix completion (Radhakrishnan et al., 2024b). Thus, RFM provides framework that is both practically powerful and serves as theoretically tractable model of deep learning.
B. Additional Preliminaries
For completeness we replicate the algorithm definition for Recursive Feature Machines (RFM) provided by Radhakrishnan et al. (2024a) in Algorithm 1. This procedure recursively fits a kernel estimator for a chosen base kernel, k, then updates the feature matrix, M, by computing a matrix power the Average Gradient Outer Product (AGOP) for that estimator. The algorithm terminates after a total iterations. The final estimator and feature matrix are then returned by the algorithm.
C. Neural Feature Ansatz
While the NFA has been observed generally across depths and architecture types (Radhakrishnan et al., 2024a; Beaglehole et al., 2023; 2024a), we restate this observation for conlecconee networks with one hidden-layee of the form f(z) a & ([x)).
Ansatz (Neural Feature Ansatz for one hidden layer). For a one hidden-layer neural network JaN and matrix power s E (0, 1), the the following holds:
W. W1 x G(
(15)
Note that this statement implies that W,T W, and G(JNN)² have a cosine similarity of +1
13

---

Emergence in Non-Neural Models: Grokking Modular Arithmetic via Average Gradient Outer Product
In this work, we choose = 1. following the main results in (Radhakrishnan et al., 2024a). While the absolute value of the cosine similarity is written in Eq. (15) to be 1, it is typically high value less than 1, where the exact value depends on choices of initialization, architecture, dataset, and training procedure. For more understanding of these conditions, see (Beaglehole et al., 2024a).
D. Model and training details
Gaussian kernel: Throughout this work we take bandwidth = 2.5 when using the Mahalanobis Gaussian kernel. We solve ridgeless kernel regression using NumPy on a standard CPU.
Neural networks: Unless otherwise specified, we train one hidden layer neural networks with quadratic activation functions and no biases in PyTorch on a single A100 GPU. Models are trained using AdamW with hidden width 1024, batch size 32, learning rate of 10 weight decay 1.0, and standard PyTorch initialization. All models are trained using the Mean Squared Error loss function (square loss).
For the experiments in Appendix Fig. 8, we train one hidden layer neural networks with quadratic activation and no biases on modular addition modulo p- = 61. We use 40% training fraction, PyTorch standard initialization, hidden width of 512, weight decay 10-5, 5, and AGOP regularizer weight 10-3, Models are trained with vanilla SGD, batch size 128, and learning rate 1.0.
E. Reordering feature matrices by group generators Our reordering procedure uses the standard fact of group theory that the multiplicative group 2, is a cyclic group of order p- - 1 (Koblitz, 1994). By definition of the cyclic group, there exists at least one element E Z known as a generator, such that 2 = {g' i p
Given a generator y E Zi, we reorder features according to the map, by 2 - Eny, where if h = g', then dg) = i. In particular, given a matrix B E IRPXP, we reorder the bottom right (p - 1) x (p - 1) sub-block of B as follows: we move the entry in coordinate (r, e) with r, E I to coordinate (r), (r)) (c()) For example if g = 2 in Zg, then (2, 3) entry of the sub-block would be moved to coordinate (1,3) 3) since 2 and 2 mod 5- = 3. In the setting of modular multiplicatioondiiisioon the map Φy defined above is known as the discrete logarithm base g (Koblitz, 1994, Ch.3). The discrete logarithm analogous to the logarithm defined for positive real numbers in the sense that it converts modular multiplication/divssioon into modular addition/subbrrationn Lastly, in this setting, we note that we only reorder the bottom (p- 1) x (p- 1) sub-block of B as the first row and column are 0 (as multiplication by 0 results in 0).
Upon re-ordering the p x off-diagonal sub-blocks of the feature matrix by the map 6g. the feature matrix of RFM for multiplicationn/diiiiion tasks contains circulant blocks as shown in Fig. 3C. Thus, the reordered feature matrices for these tasks also exhibit the structure in Observation 1. As a remark, we note that there can exist several generators for a cyclic group, and thus far, we have not specified the generator 9 we use for ordoringg For example, and 3 are both generators of 25 since (2, 22, (2' mod 5), (24 mod 5)] = (3, (32 mod 5), (33 mod 5), (3* mod 5)} Z5. Lemma J.1 implies that the choice of generator does not matter for observing circulant structure. As a convention, simply reorder by the smallest generator.
F. Enforcing circulant structure in RFM
We see that the structure in Observation gives generalizing features on modular arithmetic when the circulant C' is constructed from the RFM matrix. We observe that enforeing this structure every iteration, and comparing to the standard RFM model that iteration, improves test loss and accelerates grokking on e.g. addition (Appendix Fig. 3). The exact procedure enforce this structure is follows. We first perform standard RFM to generate feature matrices M,,..., My. Then for each iteration of the standard RFM, we construct a new M, on which we solve ridgeless kernel regression for a new a and evaluate on the test set. To construct M, we take D = diag (M,) and first let M = 1/2 D 1/2 to ensure the rows and columns have equal scale. We then reset the top left and bottom right sub-matrica matrices of M as T 1 T and replace the bottom-left and top-right blocks with C and CT,, where is an exactly circulant matrix constructed from Mp. Specifically, where e is the first column of the bottom-left sub-matrix of Mf, column l of C is equal to o (Mc).
14

---

Emergence in Non-Neural Models: Grokking Modular Arithmetic via Average Gradient Outer Product
G. Grokking multiple tasks
Throughout the main paper, we focused on modular arithmetic settings for a single task. In more general domains such as language, one may expect there to be many "skills" that need to be learned. such settings, is possible that these skills are grokked at different rates. While a full discussion is beyond the scope of this work, illustrate this behavior, we performed additional experiments in here, where train RFM on pair of modular arithmetic tasks simultaneously and demonstrate that different tasks are indeed grokked at different points throughout training.
We train RFM to simultancously solve the following two modular polynomial tasks: (1) x + mod p: x2)x² +y² mmddp for modulus p = 61. We train RFM with the Mahalanobis Gaussian kernel using bandwidth parameter L = 2.5. Training data for both tasks is constructed from the same 80% training fraction. In addition to concatenating the one-hot encodings for æ. y, we also append an extra bit indicating which task to solve (0 indicating task (1) and indicating task (2)). The classification head is shared for both tasks (e.g. output dimension still I.
In Appendix Fig. 4, we observe that there are two sharp transitions in the test loss and test accuracy. By decomposing the loss into the loss per task, we observe that RFM groks task (1) prior to grokking task (2). Overall, these results illustrate that grokking of different tasks can occur at different training iterations.
H. AGOP regularization and weight decay for grokking modular arithmetic.
has been argued prior work that weight decay (l2 regularization on network weights) necessary for grokking to occur when training neural networks for modular arithmetic tasks (Varma et al., 2023; Davies et al., 2023; Nanda et al., 2023).
expect that performing weight decay on the first layer, i.e., penalizing the loss by [[ = tr(W, Wi), should behave similarly to penalizing the trace of the AGOP, tr tr(G())). during training. To this end, we compare the impact of using (1) no regularization; (2) weight decay; and (3) AGOP regularization when training neural networks on modular arithmetic tasks. In Appendix Fig. 8, we find that, akin to weight decay, AGOP regularization leads to grokking in cases where using no regularization results in no grokking and poor generalization. These results provide further evidence that neural networks solve modular arithmetic by using the AGOP to learn features.
Under the NFA (Eq. (15)), which states that W,T W2 is proportional to a matrix power of G(f),
I. FMA example for p 3
We now provide an example of the FMA for 3. Let x = e1 @ eg. In this case, we expect the FMA to output the vector eo since (1 + 2) mod3 = 0. Following the first step of the FMA, we compute
ر| = Fei = [1 WT. दلय = Fez = 5/3 11, JI.WP,W9TT
(16)
v3
which are the first and second columns of F, respectively. Then their element-wise product is given by
Fe, @ Fez = [1, 1 5 1|
Feo
(17)
V3
which is I. times the first column of the DFT matrix. Finally, we compute the outputs v3 ( 1 Feo, Fex). for each 1/3 E {0, 1,2). As F is unitary, yada (ei @ e2; é) (142=/mod3)) so that coordinate 0 of the ouiput will have value 1, and all other coordinates have value O.
V33
J. Additional results and proofs
(p-1) Lemma J.1. Let C E RPxP with its first row and column entries all equal to Let the (p- 1) x (p-1) sub-block starting at the second row and column be Cx Then, Ox is either circulant after re-ordering by any generator q of Ey or Cx is not circulant under re-ordering by any such generator.
Proof of Lemma J.I. We prove the lemma by showing that for any two generators Q1 92 of Z if C* is circulant re-ordering with gr, then it is also circulant when re-ordering by q2-
We note this regularizer heen used prior work where AGOP is called the Gram matrix of the input-output Jacobian (Hoffman al., 2019).
15

---

Emergence in Non-Neural Models: Grokking Modular Arithmetic via Average Gradient Outer Product
Suppose Cx circulant re-ordering with y1- Let i,j p 11. Note that by the circulant assumption, for all E Z,
C C Cattr
(18)
where we take each index modulo p.
As q2 is generator for Zpp. we access all entries of C by indexing with powers of 92- Further, qi is generator, can write Q2 = of for some power k. Let a E. Then,
C
0h.03
of' A1
C Nitho ka
91 (4)
C o1 o) RG (614)
91
=C o0ttaat+a .
Therefore, C' is constant on the diagonals under re-ordering by G2, concluding the proof.
We next state Lemma J.2, which is used in the proof of Theorem 5.1.
Lemma J.2 (See, e.g., (Gray al., 2006)). Circulant matrices can be written (diagonalized) as:
U FDFF.
where F is the DFT matrix, FT is the element-wise complex conjugate of F (i.e. the Hermitian of F), and D is a diagonal matrix with diagonal s/p- Fu, where is the first row Uf
We now present the proof of Theorem 5.1, restating the theorem below for the reader's 's convenience.
Theorem. Given all of the discrete data (ee + eb, e(a-b) mod p) } p-1 in modular subtraction task, for each output class
E {0, ... .P- p-1}. -1]. we train a separate kernel predictor fe(Ø) = k(x, X; (c)) Here Mc) is a quadratic kernel
0 with Mr. = (CO) C¹) and E TRxX a circulant matrix with first row es. When a is the solution to kernel
ridgeless regression for each the kernel predictor f [fo..... fp-1] 1] is equivalent to Fourier Multiplication Algorithm for modular subtraction (Eq. (14)).
Proof of Theorem 5.1. We present the proof for modular subtraction as the proof for addition follows analogously. We write the standard kernel predictor for class on input æ = =[1 + x(2] E 2p as,
fe(x)
Σ a,6=0
a (z, + es; Mc)
where we have re-written the index into kernel coefficients for class E, a E RPXP, so that the coefficients are multi-indexe by the first and second digit. Specifically, now (C) is the kernel coefficient corresponding to the representer k(., for input point ea @ es. Recall quadratic kernel, k(x, 2; Mt) (x: T M2z)2. : In this case, the kernel predictor simplifies to,
#-1
M((x) = Σ
(8) oab
C'en + C'(C))))))))
Then, the labels for each pair of input digits, written as matrix (1) E RPXP for the f-th class where the row and column index the first and second digit respectively, are ( C-t.
16

---

Emergence in Non-Neural Models: Grokking Modular Arithmetic via Average Gradient Outer Product
For x eo' @ ey, i.e. in the discrete dataset, have,
fe(x) Σ
(6) aab
(6(a.N/1)) (ar (1)
o,b=0
aa 19 1 1 eo't + 22 _a ea'tl
c (0) 1 a C- ee 200 C (1 C
= e (C + -1 ac +2C a00 ea'
where (u,v)) = 1 (u=u}. Let fx() E Rexp be the matrix of function values of fr, where [ - Si(ea @ es), and, therefore, fe(e, @ eb) e. f(()ee, Then, to solve for (9), we need to solve the system of equations for a,
= = (C- +11 ac + =20-a00-11 - = al1 + I1 II aC 20 +
C
Note, by left-multiplinn both sides by C-e, we see this equation holds iff,
c-2 11 a1aaC=t
Note the solution is unique as the kernel matrix is full rank. We posit the solution a such that C' C-" 1 A11T, which is a C A11T. Then, solving for X, we require,
11 T + 2pA11 + 2211 = 0,
which implies X =
2 Substituting this value of À and simplifying, see finally that fe(x) 2 (zzz) Therefore, 2p+2
using that circulant matrices are diagonalized by C vPFDFT (Lemma J.2) and FT F = I, where D diag (Fe)). we derive,
[((x) vp- 11 FD PD- FFFT
r(2)
vp 21j Fdiag [ (ep-ee1)) F mppl
= -V.. (Fam) @ Fep-t-1, 1-p F F
which is the output of the FMA on modular subtraction.
K. Low rank solution to modular arithmetic
Addition We present solution to the modular addition task whose AGOP is low rank, in contrast to the full rank AGOP recovered by RFM and neural networks.
We define the "encoding" map Φ IRP - C as follows. For a vector a = [ao...., (p-1].
k2mi
((a)
ag exp
p
k==
Notice that / is linear map such that ((ex) = exp
Notice also that & is partially invertible with the "decoding"
map VI C + IRP.
(zz,exp
(0- 2Ti
(p (p- 1) 2Tí
(=) =
max
2, exp
p
Above max is function that makes all entries except for the largest one and the inner product is the usual inner product in C considered as 222 Thus
k: 2Tí
V
exp
ex
(19)
is nonlinear map -> R.P While discontinuous but can easily be modified to make differentiable.
17

---

Emergence in Non-Neural Models: Grokking Modular Arithmetic via Average Gradient Outer Product
By slight abuse of notation, will define + IP RP C² pairs:
l(e (e,)),,
This is still linear map but now C?
Consider now quadratic map M on ( C given by complex multiplication:
M 21 22) 21
is clear that the composition VM implements modular addition
VM ex) ((+++)) mod
Furthermore, since & liner map to a four-dimensional space, the AGOP of the composition VM + is of rank 4.
The construction is for multiplication is very similar with modifications which we sketch below. We first re-order the non-zero coordinates by the discrete logarithm with base equal to generator of the multiplicative group eg (see Appendix E), while keeping the order of index 0. Then, modify & to remove index ag from the for inputs Thus for multiplication,
Multiplication
k 2mi
(a) Σ exp
p
Hence that ((eo) = 0, ((eg)) exp
2 p-1
and ((exr) exp
k:2zi p-1
We extend & to IP x IP as in Eq. 19 above.
Note that & and the re-ordering together are still a linear map of rank 4.
Then, the "decoding" map, (z), will modified to return 0, when 2 = 0, and otherwise,
(() (2) = g m (2 2 (). (m-2) 23
M is still defined as above. It is easy to check that the composition of V with reordering implements modular multiplication modulo and furthermore, the AGOP will also be of rank 4.
18

---

Emergence in Non-Neural Models: Grokking Modular Arithmetic via Average Gradient Outer Product
Accuracy Loss
Accuracy
(h)
10
20
10
Loss
0.016
0.013
Test Correct Output Class
10
15
20
25
5
10
15
20
23
30
10
88
25
10
10
15
29
25
30
1.00
1.00
0.75
0.75
0.00
0.50
10
15
20
25
10
Iterations
RFM Iterations
Progress Measures
Circulant
Alignment Devistion
0.61
0.01
0.0L
01
0.00
10
20
AGOP
1.00
0.75
1.00
75
2.00
0.75
0.30
0.50
0.50
0.55
0.25
0.25
15 25 30
RFN Iterations
RFM Iterations
RFN Iterations
RFM Iterations
Add
Sub
Div
Figure I. RFM with the quadratic kernel on modular arithmetic with modulus p = 61 trained for 30 iterations. (A) Test accuracy, test loss (mean squared emorr) all output coordinates, and test loss of the correct class output coordinate do not change in the first 8 iterations and then, sharply transition. (B) Circulant deviation and AGOP alignment show gradual progress towards generalizing solutions despite accuracy and loss metries changing in the initial iterations. For multiplication (Mul) and division (Div), circulant deviation measured with respect to the feature sub-matrices after reordering by the discrete logarithm.
Iter 1
Iter 5
Iter 10
Iter 15
Mul
126
160
25
16
136
22
10
<0.31
+203
-0.4
0838
<048 -243
140
136
6.30
+204
-53
Mul (reordered)
308
13
160
16
1.0
0.76
200
416
Figure 2. AGOP evolution for quadratic RFM trained on modular multiplication with = 61 before reordering (top row) and after reordering by the logarithm base 2 (bottom row).
19

---

Emergence in Non-Neural Models: Grokking Modular Arithmetic via Average Gradient Outer Product
Test Accuracy (%)
100
0.010
75
Test Loss
0.008
0.006
25
0.004
25 30
5
20 Iterations
RFM Iterations
RFM AGOP
Obs Structure Enforced
Figure 3. We train Gaussian kemel-RFM + mod 97 and plot test loss and accuracy versus RFM iterations. We also evaluate the performance the same model upon modifying the M matrix exact block-circulant structure stated Observation 1.
Both Tasks:
Task 1:
Task 2:
x + y and x² + y2
x² + y2
x + y
0.020
0.020
0.020
Test
Loss
0.015
0.015
0.015
0.010
0.010
0.010
0.005
0.005
0.005
10
20
30
10
20
30
10
20
30
Test Accuracy
1.00
1.00
1.00
0.75
0.75
0.75
0.50
0.50
0.50
0.25
0.25
0.25
0.00
0.00
0.00
10
20
30
10
10
20
30
RFM Iterations
RFM Iterations
RFM Iterations
Figure 4. RFM with the Gaussian kereel trained modular arithmetic tasks with modulus p = -1. Task is leam x² y² modp task is to learn x. y mod p.
20

---

Emergence in Non-Neural Models: Grokking Modular Arithmetic via Average Gradient Outer Product
A
Accuracy & Loss
Accuracy
100-
100
100
100
(5)
10
20
34
40
30
20
30
2G
20
30
40
10
20
30
45
Loss of Corract Output Clazs
10
20
40
0.90
30
20
30
40
10
25
30
40
10
25
30
3.0
0.5
0.7
0.0
0.0
Epochs
Epochs
Epochs
Epoch
Test
Progress Measures
ASOP Circulant
ALignnent Deviation
0.45
0.010
0.010
0.10
0.005
0.025
0.905
0.005
10
30
10
2.0
1.4
14
0.5
20
10
40
0.0
10
28
30
40
Epochs
Epochs
Epochs
Epochs
Add
Mul
Div
Figure 5.
One hidden layer fully fullecco networks with quadratic activations trained on modular arithmetic with 61 trained for 50 epochs with the square loss. (A) Test accuracy, test loss over outputs, and test loss the correct class output do not change in the initial iterations. (B) Progress measures for circulant deviation and AGOP alignment. Circulant deviation for Mul and Div are computed after reordering by the discrete logarithm
A
NFM
NN AGOP
12
18
-331
3.0
Mul
Mul (reordered)
Div
Div (reordered)
Figure (A) We visualize the neural feature matrix (NFM) from one hidden layer neural network with quadratic activations trained on modular multiplication and division, before and after reordering by the discrete logarithm. (B) We visualize the square of the AGOP of the neural network in (A) before and after reordering.
21

---

Emergence in Non-Neural Models: Grokking Modular Arithmetic via Average Gradient Outer Product
A
NFM
B
14
AGOP
Add
Sub
Mul (reordered)
Div (reordered)
Figure 7. Feature matrices from one hidden layer neural networks with quadratic activations trained on addition, subtraction, multiplication, division modulo 61. The Pearson correlations between the NFM square root the AGOP for each task are 0.955 (Add), 0.942 (Sub), 0.924 (Mul), 0.929 (Div). Mul and Div shown after reordering by the discrete logarithm base 2.
No Regularization
Weight Decay
AGOP Regularization
1.00
1.00
1.00
Accuracy
Accuracy
0.75
Accuracy
0.75
0.50
0.25
0.25
0.25
0.00
0.00
0.00
100k
200k
200k
200k
0.020
0.020
Square Loss
Square Loss
0.015
Square Loss
0.015
0.010
0.010
0.01
0.005
0.005
0.000
100k
200k
0
100k
200k
100k
200k
Epochs
Epochs
Epochs
Train
Test
Figure One hidden layer fully connected networks with quadratic activations trained on modular addition with p = 61 with vanilla SGD. Without any regularization the test accuracy does not go to 100% whereas using weight decay or regularizing using the trace of the AGOP result in 100% test accuracy and grokking.
22

---

Emergence in Non-Neural Models: Grokking Modular Arithmetic via Average Gradient Outer Product
Add
Mul
NN
Random Circulant NN
Random Circulant NN
1.0
Accuracy (S)
Accuracy (S)
100
Accuracy
Accuracy
50
50
3000
3020
0.020
0,020
Squa Loss
0.020
Square Loss
0.020
0.015
6.015
0.035
0.025
0.020
Squa
0.005
6.055
0.05
0.055
2000
2000
3000
1000
2000
3000
1000
2000
3000
1000
2000
3000
Epochs
Epochs
Epochs
Epochs
Train
Test
Figure 9. Random circulant fcatures speed up generalization in neural networks for modular arithmetic tasks. We compare one hidden layer MLPs with quadratic activations trained modular addition and multiplication for 61 using standard one-hot encodings those transformed by random circulant matrices (re-ordered by the discrete logarithm for multiplication).
100
Test Square Loss
3.012
Test Accuracy
AGOP Elignment 2.8
3.1
0012
3.02
3.003
3.003
Training Fraction (%)
Training Fraction (%)
Training Fraction (%)
Figure We train kernel-RFMs loss, and AGOP alignment versus percentage of training data used (denoted training fraction). All models reach convergence (i.e., both the test loss and test accuracy no longer change) after 30 iterations. We observe a sharp transition test accuracy with respect to the training fraction, but observe gradual change in test loss and AGOP alignment with respect to the training data fraction.
iterations using the Mahalanobis Gaussian kemel for x + y mod 97, plot test accuracy, test
23


Reviews:
[{"review_id": "vsktN9EEuF", "reviewer": "Reviewer_d9eN", "summary": "The paper focuses on \"grokking\" -- a phenomenon that has attracted a lot of interest recently mostly because it is not what the ML community was used to observe regarding training dynamics and generalization. \n\nThe paper's main point seems to be that grokking is not specific to neural networks and to SGD training. Instead, the authors show that grokking is also observed with Recursive Feature Matrices (RFMs) -- when trained on modular arithmetic tasks. Another main point is what drives generalization is the learning of structured feature representations -- and the paper proposes a couple of metrics (such as \"circulant deviation\") to show this gradual progress of the model towards generalization.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed feedback. We address their questions and comments below.\n\n>First, the paper focuses exclusively on modular arithmetic -- but grokking is a more general phenomenon and it has been observed also in language models among others. This has to be clarified somehow: even though the paper helps us better understand the process of learning structured features in a very specific task that relates to modulo arithmetic, its claims and evidence cannot be generalized beyond such tasks.\n\nLike prior works (e.g. [1,2]), we focus on the setting of modular arithmetic because (1) these tasks clearly exhibit the sharp transition from trivial-to-perfect generalization, and (2) there exist analytic solutions to the task that we can compare the learned algorithms to. In particular, there is substantial evidence that the algorithm implemented by neural networks is the Fourier Multiplication Algorithm [2,3]. Moreover, it appears that non-parametric methods without the ability to learn features are unable to learn modular arithmetic, hence these tasks are a strong test-bed for the predictor power of feature learning through AGOP.\n\n[1] Power et al., Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets, Mathematical Reasoning in General Artificial Intelligence Workshop, ICLR 2021.\n\n[2] Nanda et al., Progress measures for grokking via mechanistic interpretability, ICLR, 2023.\n\n[3] Zhong, et al. \"The clock and the pizza: Two stories in mechanistic explanation of neural networks.\" NeurIPS 2023.\n\n>The paper certainly contributes in the fundamental understanding of grokking -- but it does not explain some key characteristics of grokking (such as, what determines how many long it will take, say in epochs, until the model learns those structured features?)\n\n While this question is beyond the scope of this paper, we do observe the rate at which features evolve through the AGOP alignment and circulant deviation progress measures. We find that while the features make progress linearly through iteration, generalization exhibits a sudden phase transition, suggesting error is a sharp function of feature quality specifically. We are exploring theoretical analyses to potentially identify the threshold when better features lead to improved generalization. \n\n>Is there an info theoretic way to show why circulant matrices emerge?\n\nOne possibility to understand why circulant matrices emerge on these tasks is through their effect on the Mahalanobis kernel. As circulant matrices are diagonalized by the DFT matrix, we can view inner products through the block-circulant matrix as applying the DFT to each of the one-hot encoded integer arguments, then re-weighting the frequency components by the (complex) eigenvalues of the circulant sub-blocks. We suspect the frequency reweighting induces linear separability of the DFT vectors, enabling generalization with kernel regression. We are currently exploring this direction.", "claims_and_evidence": "I find the paper a bit confusing on its \"positioning\" with respect to prior work in this research area. \n\nFirst, the paper focuses exclusively on modular arithmetic -- but grokking is a more general phenomenon and it has been observed also in language models among others. This has to be clarified somehow: even though the paper helps us better understand the process of learning structured features in a very specific task that relates to modulo arithmetic, its claims and evidence cannot be generalized beyond such tasks.", "methods_and_evaluation_criteria": "I like how the paper uses both mathematical insights and experimental results -- and overall I found it to be rigorous, with clear definitions, methods, and metrics.", "theoretical_claims": "The most important mathematical result of the paper is (in my own words): a good solution for the modulo arithmetic problem is the Fourier multiplication algo (FMA). The paper shows that circulant matrices allow kernel machines to solve modulo arithmetic using FMA.", "experimental_designs_or_analyses": "The paper is quite strong in terms of experimental design and analysis -- showing several results. Some of the empirical claims that I found more interesting are: a) that even RFMs can show grokking behavior, b) that a metric such as AGOP shows gradual improvement during learning -- as opposed to accuracy, c) that circular features solve the modular arithmetic problem using FMA.", "relation_to_broader_scientific_literature": "The paper has connections with broader questions related to learning theory, emergent phenomena in learning, and foundations of AI.", "essential_references_not_discussed": "None that I know of.", "other_strengths_and_weaknesses": "- The paper certainly contributes in the fundamental understanding of grokking -- but it does not explain some key characteristics of grokking (such as, what determines how many long it will take, say in epochs, until the model learns those structured features?)\n- And as previously mentioned, the paper is quite narrow -- focusing only on modular arithmetic.", "other_comments_or_suggestions": "I think that the paper can be improved if the authors find a way to describe more clearly, and from the first section of the paper, what is the key \"take home message\" of this study.", "questions_for_authors": "- is there an info theoretic way to show why circulant matrices emerge?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YDiniuhxXk", "reviewer": "Reviewer_u4Fp", "summary": "This paper studies the grokking phenomenon in modular arithmetic. The main idea is that grokking happens because models slowly learn the right features, not because of any specific neural network architecture or gradient-based optimization. The authors use Recursive Feature Machines (RFMs) to show that even when training loss is zero from the start, the features evolve gradually until they reach a structure that allows generalization. In their case, the key structure is a block-circulant feature matrix that connects to the Fourier Multiplication Algorithm, which exactly solves the modular arithmetic task.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive comments and thorough feedback. We will answer their questions below.\n\n>While the paper is well-grounded in the literature on grokking and feature learning, it could benefit from more discussion of works on implicit bias in optimization and how these biases shape feature learning.\n\nWe would appreciate specific references that the reviewer feels are relevant. We would be happy to extend the discussion to include them.\n\n>On the downside, the experiments are limited to modular arithmetic tasks, so it is uncertain how well these insights will carry over to more complex, real world dynamics. Also, the paper focuses heavily on RFMs, which may limit how easily it can be generalized to other architectures.\n\nApplying RFM is crucial for establishing that (1) grokking is not tied to neural networks, as it is a non-neural model, (2) it is not tied to gradient based optimization or training loss, and (3) can be induced solely through feature learning. Further, RFM allows us to isolate the ability of feature learning through AGOP to induce generalization in surprising settings. As mentioned in another response, there is also substantial evidence that the algorithm implemented by neural networks is the Fourier Multiplication Algorithm. RFM being able to recover the FMA (in our theoretical setting) and the features learned by neural networks empirically suggest that feature learning through AGOP is a useful lens to study neural networks. This is especially true as non-parametric methods without the AGOP appear unable to learn modular arithmetic tasks.\n\n>Have you tested your approach on any tasks beyond modular arithmetic to see if the delayed feature evolution and grokking phenomenon persist? \n\nWe have ongoing results where grokking occurs with RFM for other algorithmic tasks including sparse parities, the Chinese remainder theorem number representations, and certain group structures.\n\n>How sensitive are your progress measures to different kernel choices or initializations in RFMs? \n\nThe choice of kernel can affect the rate at which grokking occurs in RFM or whether it happens at all. Quadratic and Gaussian kernels are suited for modular arithmetic due to the target function being quadratic in Fourier space, while RFM with the Laplace kernel does not appear to generalize. In all of our experiments, we use the default initialization for RFM with the identity matrix.\n\n>Can you provide more insights into how the reordering using the discrete logarithm affects the observed feature structure?\n\nRe-ordering by the discrete logarithm only affects the visualization of the features, as RFM is invariant to re-ordering of the input coordinates. We re-order coordinates for multiplication and division tasks in order to visualize the circulant structure, which is otherwise obscured. The features are circulant after re-ordering because modular multiplication/division (excluding zero element)  are equivalent to addition/subtraction after transformation with the discrete logarithm. Note that it is necessary to know the structure of that re-ordering in order to invert it and recover the “underlying algorithm”.", "claims_and_evidence": "The authors claim that grokking is not specific to neural networks and is not tied to gradient-based methods. They show this by demonstrating grokking in RFMs, where the training loss is zero but the model only generalizes after many iterations when the features are more fleshed out. They support this with evidence such as gradual improvements in Circulant Deviation and AGOP Alignment, measures that capture how close the features are to the ideal block-circulant structure.", "methods_and_evaluation_criteria": "The paper uses a mix of theory and experiments on modular arithmetic tasks like addition, subtraction, multiplication, and division. The models are evaluated not only on standard metrics like test accuracy and test loss but also on new progress measures that track feature quality over time. The experimental design compares RFMs with neural networks and examines how features evolve during training despite the immediate reduction in training loss.", "theoretical_claims": "On the theory side, the paper argues that the key to grokking is the emergence of a block-circulant feature matrix. They show that when the learned feature matrix attains this specific structure, the model effectively implements the Fourier Multiplication Algorithm. A central result (Theorem 5.1) proves that a kernel machine with a quadratic kernel and a block-circulant Mahalanobis matrix will compute modular arithmetic operations exactly as the Fourier Multiplication Algorithm does. The math leverages the fact that circulant matrices are diagonalizable using the Discrete Fourier Transform, linking the learned feature structure directly to the generalization ability.", "experimental_designs_or_analyses": "The experimental design centers on training RFMs on modular arithmetic tasks. Despite perfect training loss from the outset, the test accuracy remains near chance level for many iterations. The authors analyze how the feature matrix, particularly the AGOP, evolves over time. They introduce and track two progress measures (Circulant Deviation and AGOP Alignment) to show that the feature structure gradually becomes more organized. They also include experiments with neural networks and tests using random circulant transformations to further support the claim that the emergence of the correct feature structure is what drives grokking.", "relation_to_broader_scientific_literature": "This work builds on the growing literature on grokking, which has mainly focused on neural networks and delayed generalization. It relates to prior studies that view grokking as a transition from a lazy memorization regime to one where rich, useful features are learned. The paper connects these ideas with the concept of feature learning in kernel methods and neural networks and also ties into Fourier-based methods for solving modular arithmetic. In doing so, it challenges the idea that grokking is solely a function of network architecture or gradient-based optimization. It's an interesting addition to papers like the one from 2024 \"Grokking as the transition from lazy to rich training dynamics\" which highlight the important of optimization dynamics and architecture vs this one which highlights that feature learning is more of the key driver.", "essential_references_not_discussed": "While the paper is well-grounded in the literature on grokking and feature learning, it could benefit from more discussion of works on implicit bias in optimization and how these biases shape feature learning.", "other_strengths_and_weaknesses": "A clear strength of the paper is its novel approach to isolating feature learning from the usual gradient-based optimization by using RFMs. The theoretical connection between block-circulant features and the Fourier Multiplication Algorithm is super cool and interesting. On the downside, the experiments are limited to modular arithmetic tasks, so it is uncertain how well these insights will carry over to more complex, real world dynamics. Also, the paper focuses heavily on RFMs, which may limit how easily it can be generalized to other architectures.", "other_comments_or_suggestions": "No comments", "questions_for_authors": "Have you tested your approach on any tasks beyond modular arithmetic to see if the delayed feature evolution and grokking phenomenon persist? How sensitive are your progress measures to different kernel choices or initializations in RFMs? Can you provide more insights into how the reordering using the discrete logarithm affects the observed feature structure?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hzVEnHKN9R", "reviewer": "Reviewer_C2Z3", "summary": "This paper studies the phenomenology of learning with recursive feature machines for modular addition, subtraction, multiplication, and division. Modular addition has become a standard setting for studying grokking as an example algorithmic task and has been studied for learning with neural networks, typically with quadratic activation functions. This paper learns the task with recursive feature machines that exhibit similarities with feature learning in neural networks. The paper also gives explicit constructions by transforming the unit vectors by circulant matrices which is then solved with a generalizing solution by quadratic kernel regression.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their in-depth feedback on our submission. We will address their comments and questions here. \n\n>Theorem 5.1 could come earlier in the paper and also be written formally as done in Appendix\n\"well-known results for multiplicative group\" may not be well known to ML audience. It would be better to state these group theory references formally in math symbols instead of words (and add refs).\n\nThank you for this feedback. We will include the Theorem formally in the main text in the updated manuscript, and more clearly reference Appendix E where we discuss the re-ordering.\n\n>Please use the standard definition of Jacobian without transpose in Def 2.1 and write G = Jf ^T Jf to avoid confusion.\n\nThank you for this suggestion, we will use the standard definition to avoid confusion.\n\n>Why is AGOP measured by vectorizing the matrices? Why not $ \\text{alignment}(A, B) = \\frac{\\text{Tr}(A^T B) }{| A | | B |} $. I believe this is the standard way to measure the alignment of matrices AND it would capture similarities of eigenvectors, unlike the vectorized alignment.\n\nIn fact $\\text{Tr}(A^T B)$ equals the inner product of the vectorized A and B, and $||A||,||B||$ are equivalent to the norms of their vectorizations, thus our formulation is indeed a standard measure of matrix similarity.", "claims_and_evidence": "Claims are supported by clear and convincing numerical simulations and intuitive explanations.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes ( but not in detail). There is one Theorem in the main paper that shows that the quadratic kernel learns features after transforming the data by discrete Fourier transform. This Theorem is informally stated in the main paper and a more detailed version is given in the Appendix.", "experimental_designs_or_analyses": "Yes. All the Figures in the main are good.", "relation_to_broader_scientific_literature": "To what extent does learning with recursive feature machines correlate with feature learning of neural networks is an active research area. Also, it is an open question whether this can be shown mathematically in simple settings. Our fundamental understanding of feature learning in neural networks is so far limited to learning in infinite-width in a mean-field regime or learning multi-index models. This paper contributes to understanding feature learning for modular addition (and so on) task.", "essential_references_not_discussed": "references are good", "other_strengths_and_weaknesses": "**Strengths:**\nExperiments are thorough and explanations are insightful. It was already known that neural networks learn Fourier Multiplication Alg. This recursive kernel learning gives a more transparent framework for understanding grokking. \nKernel Machine without feature learning also achieves zero training error but does not generalize but the learning features with RFM (=data transformation) gives a generalizing solution. That's neat ! Applying the (A) correct transformation to data and kernel machine is better than (B) learning with kernel machines which is quite interesting (also, whether (A) beats neural networks). \n\n**Weaknesses:**\n* line 359--361 (right): already said before\n* Theorem 5.1 could come earlier in the paper and also be written formally as done in Appendix \n* \"well-known results for multiplicative group\" may not be well known to ML audience. It would be better to state these group theory references formally in math symbols instead of words (and add refs).", "other_comments_or_suggestions": "Suggestions \n\n* Please use the standard definition of Jacobian without transpose in Def 2.1 and write G = Jf ^T Jf to avoid confusion.", "questions_for_authors": "Why is AGOP measured by vectorizing the matrices? Why not \n\n$ \n\\text{alignment}(A, B) = \\frac{\\text{Tr}(A^T B) }{\\| A \\| \\| B \\|}\n$\n\nI believe this is the standard way to measure the alignment of matrices AND it would capture similarities of eigenvectors, unlike the vectorized alignment.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XmanltUKZF", "reviewer": "Reviewer_ERsy", "summary": "This paper investigates grokking in the common scenario of modular arithmetic. In contrast to previous approaches, the authors show that grokking occurs when using the RFM learning algorithm. This enables them to isolate the feature learning as the source of grokking in these setups. By defining two progress measures, they demonstrate that the feature learning dynamics do not exhibit two distinct phases. Finally, they compare their results to the traditional NN approach and show that their findings are consistent with previous attempts.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for their detailed feedback. We address their questions and comments below.\n\n>I felt that some details are still unclear and may need further investigation: What is the fundamental mechanism behind the delayed generalization observed here? In other words, why does generalization accuracy behave so differently from the continuous progress measure?\n\nThere is a sharp transition in feature alignment. Once the features are aligned beyond a certain threshold, the accuracy (and loss) both improve sharply. Thus the distinction is not between continuous or discrete measures but between measures of loss and measures of feature alignment. Why there is a discrepancy between our progress measures and accuracy / loss and formalizing the mechanism behind the delayed generalization is an important question. A simplified direction to understand this process theoretically would be to analyze how random circulant features enable generalization on modular arithmetic.\n\n>It appears that the jump in accuracy occurs when the continuous progress measure saturates. Is this consistent? Have you identified a specific threshold in the progress measures?\n\nWe have not observed a direct relationship between the jump in accuracy and saturation of progress measures. While it might look like it happens in Figure 2, it is hard to visually evaluate feature improvements as the alignment is close to 1 and the curve looks flat even as alignment continues to improve. \n\n>Generalization does not occur below a certain threshold of the training data fraction. What is the interplay between this threshold and your results?\n\nBoth training iterations and number of samples will improve feature quality. Thus, as generalization error is a sharp function of this quality, we see sharp transitions with respect to both. \n\n>Finally, since the paper focuses on the specific task of modular arithmetic, the scope of the results is naturally limited.\n\nLike prior works (e.g. [1,2]), we focus on the setting of modular arithmetic because (1) these tasks clearly exhibit the sharp transition from trivial-to-perfect generalization, and (2) there exist analytic solutions to the task that we can compare the learned algorithms to. In particular, there is substantial evidence that the algorithm implemented by neural networks is the Fourier Multiplication Algorithm[2,3]. Moreover, it appears that non-parametric methods without the ability to learn features are unable to learn modular arithmetic, hence these tasks are a strong test-bed for the predictor power of feature learning through AGOP.\n\n[1] Power et al., Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets, Mathematical Reasoning in General Artificial Intelligence Workshop, ICLR 2021.\n\n[2] Nanda et al., Progress measures for grokking via mechanistic interpretability, ICLR, 2023.\n\n[3] Zhong, et al. \"The clock and the pizza: Two stories in mechanistic explanation of neural networks.\" NeurIPS 2023.\n\n>I believe that further investigation of the behaviour of the progress measures for different ratios could be beneficial. For example, I could be interesting to see the AGOP alignment (of the current iteration versus the final iteration) and the circulant deviation at several different ratios (below and above the critical threshold). Fig. 10 is also interesting in this context: the AGOP still changes quite a lot from fraction 40% to 45%, while the test accuracy is already 1 in both of them. It could be interesting to see this graph for more fractions (larger than 45) and also for the circulant deviation measure.\n\nPlease find a new figure here showing circulant deviation and AGOP alignment evolution over time for modular addition at training fractions 5%, 15% 25%, 35%, 45%, 55%, …, 95%: https://ibb.co/ytKK0p5. As the reviewer points out, we observe that the AGOP alignment can continue to increase after test accuracy is at 100%. \n\nWe provide another new plot showing that the circulant deviation at the final iteration rapidly decreases with training size, and is very close to 0 for training fractions larger than 55%: https://ibb.co/9Hp1F3yr.\n\n>Typos: Line 70: \"and and test accuracy remain at the constant\"\nAround Eq. (6), $\\alpha$ probably should be $s$ (by the way, a brief justification for the choice $s=1/2$ would be nice).\n\nThank you for noticing this, we will fix this typo in our revision. The choice of s=½ is motivated by the case of two-layer linear networks where the NFA is exact with this exponent [1].\n\n[1] Radhakrishnan, Belkin, Drusvyatskiy. “Linear Recursive Feature Machines provably recover low-rank matrices”, PNAS 2025.", "claims_and_evidence": "Their claims are sufficiently supported by comprehensive numerical experiments.", "methods_and_evaluation_criteria": "The methods and evaluations are fine.", "theoretical_claims": "The paper mainly contains observations that are supported by strong numerical evidence.", "experimental_designs_or_analyses": "All of the experiments look valid.", "relation_to_broader_scientific_literature": "This paper can help to figure out the mechanism behind the well-known phenomena of grokking in modular addition, which could advance our understanding of the interplay between training and testing dynamics.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "**Strengths:**\n- This paper shows that grokking in modular arithmetic can also occur using RFM, which is a novel contribution.\n- This approach allows the authors to isolate feature learning as the central mechanism of grokking in this setup.\n- They demonstrate that generalization requires a circulant structure in the feature matrix, which appears important for understanding modular arithmetic tasks.\n- The authors define two progress measures that, unlike test accuracy, exhibit a linear change even in the early stages of training. This is significant as it suggests that there is no real phase transition during feature learning. I also found the discussion of the required a priori knowledge interesting.\n- They compare their findings to the modular arithmetic NN approach (Gromov, etc.), showing that it relies on the same principles and that the new progress measures could also be applied there.\n- The paper is very well-written.\n\n**Weaknesses:**\n- I felt that some details are still unclear and may need further investigation:\n  - What is the fundamental mechanism behind the delayed generalization observed here? In other words, why does generalization accuracy behave so differently from the continuous progress measure? It appears that the jump in accuracy occurs when the continuous progress measure saturates. Is this consistent? Have you identified a specific threshold in the progress measures?\n  - Generalization does not occur below a certain threshold of the training data fraction. What is the interplay between this threshold and your results?\n- Finally, since the paper focuses on the specific task of modular arithmetic, the scope of the results is naturally limited.\n\nOverall, the paper is well-written and contains important insights, so I believe it should be accepted.", "other_comments_or_suggestions": "I believe that further investigation of the behaviour of the progress measures for different ratios could be beneficial. For example, I could be interesting to see the AGOP alignment (of the current iteration versus the final iteration) and the circulant deviation at several different ratios (below and above the critical threshold).\nFig. 10 is also interesting in this context: the AGOP still changes quite a lot from fraction 40% to 45%, while the test accuracy is already 1 in both of them. It could be interesting to see this graph for more fractions (larger than 45) and also for the circulant deviation measure.\n\nTypos:\n1. Line 70: \"and and test accuracy remain at the constant\"\n2. Around Eq. (6), $\\alpha$ probably should be $s$ (by the way, a brief justification for the choice $s=1/2$ would be nice).", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper receives positive reviews from all reviewers. The reviewers find the paper is well-written, the theoretical connection between block-circulant features and the Fourier Multiplication Algorithm is interesting, and the experimental insights contribute in the fundamental understanding of grokking in non-neural methods. The authors' rebuttal helps address some issues with the scope of the paper. Based on the consistent positive reviews and the authors rebuttal, I recommend acceptance.
Decision: Accept (oral)