Grokking Beyond Neural Networks: An Empirical Exploration with Model Complexity
Authors: Jack William Miller
Charles O'Neill
Thang D Bui
Venue: Accepted by TMLR ()

Abstract: In some settings neural networks exhibit a phenomenon known as \textit{grokking}, where they achieve perfect or near-perfect accuracy on the validation set long after the same performance has been achieved on the training set. In this paper, we discover that grokking is not limited to neural networks but occurs in other settings such as Gaussian process (GP) classification, GP regression, linear regression and Bayesian neural networks. We also uncover a mechanism by which to induce grokking on algorithmic datasets via the addition of dimensions containing spurious information. The presence of the phenomenon in non-neural architectures shows that grokking is not restricted to settings considered in current theoretical and empirical studies. Instead, grokking may be possible in any model where solution search is guided by complexity and error.

Published in Transactions on Machine Learning Research (03/2024)
Grokking Beyond Neural Networks: An Empirical Explo- ration with Model Complexity
Jack Miller
jack. jack.milleBaanu.eeeee edu.oo
ANU College of Engineering, Computing and Cybernetics
Charles O'Neill
chartes.onnill@@ann........
ANU College of Engineering, Computing and Cybernetics
Thang Bui
thang www.auuiiuuu.e. edu.
ANU College of Engineering, Computing and Cybernetics
Reviewed on OpenReview: https: // opw.reviee.r.......emmee net/ forum? id= uz9BraPC18
Abstract
In some settings neural networks exhibit a phenomenon known as grokking, where they achieve perfect near-perfect accuracy the validation set long after the same perfor- mance has been achieved the training set. In this paper, discover that grokking is not limited to neural networks but occurs in other settings such as Gaussian process (GP) classification, GP regression, linear regression and Bayesian neural networks. We also un- cover a mechanism by which to induce grokking on algorithmic datasets via the addition of dimensions containing spurious information. The presence of the phenomenon in nou-neural architectures shows that grokking not restricted to settings considered in currnt theoret- ical and empirical studies. Instead, grokking may be possible in any model where solution search is guided by complexity and error.
1 Introduction
In this paper, conduct empirical exploration of grokking, uncovering new aspects of the phenomenon not explained by current theory. We begin by describing grokking and summarise its existing explanations. Afterwards, we present our empirical observations - most notably, the existence of grokking outside of neural networks. Finally, we suggest a mechanism for grokking that is broadly consistent with our observations. While we do not claim that this mechanism is necessary all cases of grokking as it relies upon a complexity penalty, we do provide evidence that may be necessary in some of our learning settings.
1.1 Generalisation
Grokking is defined with respect to model generalisation the capacity to make good predictions in novel scenarios. To express this notion formally, we restrict our definition of generalisation to supervised learning. In this paradigm, we are given a set of training examples X C X' and associated targets Y C V. We then attempt to find a function fo : X - y so as to minimise an objective function L (X,Y, - R Having found fo, we may then look at the function's 's performance under a possibly new objective function G (typically C without dependence on 0) on an unseen set of examples and labels, X' and Y'. G(X'Y') is small, we say that the model has generalised well and if it is large, it has not generalised well.
A popular choice for neural network
Goodfellow
2016 with 0 representing weights and hiases.

---

Published in Transactions on Machine Learning Research (03/2024)
1.2 Model Selection and Complexity
Consider F, a set of models we wish to use for prediction. We have described process by which to assess the generalisation performance of fo E & given X' and Y'. Unfortunately, these hidden examples and targets are not available during training, As such, we may want to measure relevant properties about members of y that could be indicative of their capacity for generalisation ion. One obvious property is the value of g Y) (or some related function) which we call the data fit. Another property is complezity. If we can find some means to mcasure the complexity, then traditional thinking would recommend we follow the principle of parsimony. "[The prineiple of] parsimony is the concept that a model should be as simple possible with respect to the induced variables, model structure, and number of parameters" (Burnham & Anderson 2004h. That is, if we have two models with similar data fit, we should choose the simplest of the two.
If we wish to follow both the principle of parsimony and minimise the data fit, the loss function & we use for choosing a model is given by:
L = error + complexity.
While Equation may seem simple, it is often difficult to characterise the complexity term Not only are there multiple definitions for model complexity across different model categories, definitions also change among the same category. When using a decision tree, we might measure complexity by tree depth and the number of lcaf nodes (Hu et al. 2021). Alternatively, for deep neural networks, we could count the number and magnitude of parameters or use a more advanced measure such as the linear mapping number (LMN) (Liu al.] 2023b). Fortunately, in this wide spectrum of complexity measures, there are some unifying formalisms we can apply. One such formalism was developed by Kolmogorov (Yucksel et al. 2019). In this formalism, we measure the complexity as the length of the minimal program required to generale given model. Unfortunately, the difficulty of computing this measure makes it impractical. A more pragmatic alternative is the model description length. This defines the complexity of a model as the minimal message length required to communicate its parameters between two parties (Hinton & van Camp 1993). We discuss Kolmogorov complexity in Appendix [ and the model description length in Appendix C We also provide a note on measuring complexity in GPs which can be found in Appendix [
1.3 The Grokking Phenomenon
Grokking was recently discovered by Power et al. (2022) and has garnered attention from the machine learning community. It is a phenomenon in which the performance of a model fo on the training set reaches a low error at epoch E1, then following further optimisation, the model reaches a similarly low error on the validation dataset at epoch Eg. Importantly the value A = |E2- 182-En must be non-trivial. In many settings, the value of A is much greater than Ej. Additionally, the change from poor performance on the validation set to good performance can be quite sudden 3 A prototypical illustration of grokking is provided in Figure (Appendix J.2
13
To the best of our knowledge, all notable existing empirical literature on the grokking phenomenon is summarised in Table [
(Appendix AA.. The literature has focused primarily on neural network architectures and algorithmic datasets We use a varioty of similar algorithmic datasets outlined in Appondix
No paper has yet demonstrated the existence of the phenomenon using a GP. In addition, several theories have been presented to explain grokking. They can be categorised into three main classes based on the mechanism they use to analyse the phenomenon. Loss-based theorics such as Liu et al. (2023a) appeal to the loss landscape of the training and test sets under different measures of complexity and data fit. Representation-based theories such as Davics et al. (2023). Barak et al. 2022 Nanda et al. (0233 and Varma et al. (202)) claim that grokking occurs as result of feature learning (or circuit formation) and associated training dynamics. Finally, there are a set of theories which use the neural tangent kernel (NTK)
2There exist standard choices for (XX. Y) such as the cross entropy in classification or the Le norm in regresssion Whether this sharp transition is required to fulfil the definition of grokking is somewhat unclear. In this paper, we tend to accept both sharp and soft transitions. We define algorithmic dataset. as one which labels are produced via a predefined algorithmic process such as mathematical operation between two integers.
2

---

Published in Transactions on Machine Learning Research (03/2024)
(Jacot et al. 2018 explain grokking. Namely, Kumar et al. (2023) and Lyu et al. 2023 Importantly, no existing theory could explain grokking if it were found in GPs.
Loss based theory. Liu et al. (2023a) assuiee that there is a spherical shell (Goldilocks zone) in the weight space where generalisation is better than outside the shell. They claim that, in a typical case of grokking, a model will have large weights and quickly reach an over-fitting solution outside of the Goldilocks zone. Then regularisation will slowly move weights towards the Goldilocks zone. That is, grokking occurs due to the mismatch in time between the discovery of the overfitting solution and the general solution. While some empirical evidence is presented in Liu et al. (2023a) for their theory, and the mechanism itself seems plausible, the requirement of spherical Goldilocks zone seems too stringent. It may be the case that more complicated weight-space geometry is at play in the case of grokking.
Liu et al. (2023b) also recently explored some cases of grokking using the LMN metric. They find that during periods they identify with generalisation, the LMN decreases. They claim that this decrease in LMN is responsible for grokking.
Representation or circuit based theory. Representation circuit based theories require the emergence of certain general structures within neural architectures. These general structures become dominant in the network well after other less general ones are sufficient for low training loss. For example, Davies et al. (2023) claim that grokking occurs when, "slow patterns generalize well and are ultimately favoured by the training regime, but are preceded by faster patterns which generalise poorly." Similarly, it has been shown that stochastic gradient descent (SGD) slowly amplifies a sparse solution
algorithmic problems which is hidden to loss and error metrics (Barak et al.] 2022). This is mirrored somewhat in the work of Liu ct al. 2022)) which looks to explain grokking via a slow increase in represcntation quality"] Nanda et al. (2023) clain in the setting of an algorithmic dalaset and transformer architecture, training dynamics can be split into three phases based on the network's representations: memorisation, circuit formation and cleanup. Additionally, the structured mechanisms (circuits) encoded in the weights are gradually amplified with later removal of memorising components. Varma et al. (2023) are in general agreement with Nanda et al. (2023) Representation ation (or circuit)) theories seem the most popular, based on the number of research papers published which use these ideas. They also seem to have a decent empirical backing. For example, Nanda et al. (2023) explicitly discover circuits in lcarning sctting where grokking occurs.
NTK based theory. Recently, Kumar et al. (2023) and Lyu et al. 2023 used the neural tangent kernel to explain the grokking phenomenon. Specifically, Kumar et al. (2023) found that a form of grokking still occurs without an explicit complexity penalty. They arguc that in this case, grokking is caused by the transition between lazy and feature-rich training regimes. This is distinct from previous theories of grokking in neural networks, many of which require weight decay to remove "memorising" solutions. Lyu ct al. (2023) worked concurrently on grokking with small values of weight decay, demonstrating that under idealised conditions, grokking could be provably induced through sharp transition from an early kernel regime to rich regime.
Grokking in Linear Estimators. Concurrently to the writing of this paper, Levi et al. 2023) studied grokking in a linear student-teacher setting. In that work they proved that a significant gap between the training and validation accuracy can arise when the two networks are given Gaussian inputs. This shows that grokking can occur in linear settings without the need for a complex model that might transition from "memorisation" to "understanding."
Our contributions. Unlike previous work, in this paper, we choose another axis by which to explore grokking. We restrict ourselves to cases where the loss function can be decomposed into the form of Equation but expand the set of models we study. In particular, we contribute to the existing grokking literature in the following ways:
We demonstrate that grokking occurs when tuning the hyperparameters of GPs and in the case of linear models. This necessitates a new theory of grokking outside of neural networks.
We create a new data augmentation technique which we call concealment that can increase the grokking gap via control of additional spurious dimensions addod to input examples.
S8ee Figure 1 of this paper for high quality visualisation of what is meant by general representation.
3

---

Published in Transactions on Machine Learning Research (03/2024)
1.0
Data Fit
10a
Train Complexity
Validation Data Fit
104
Objective Value
10a
10-1
0.
Tran Accuracy
Volidation Accuracy
0.4
10P
10a
109
10:
10a
10a
Epoch
Epoch
Figure 1: Accuracy, data fit and complexity on zero-one slope classification task with linear model. Note that the shaded region corresponds to the standard error of five training runs. Further, the grey line marks the point of minimum data fit.
We suggest a mechanism for grokking in cases where solution search is guided by complexity and crror. This mechanism model-agnostic and can explain grokking outside of neural networks.
2 Experiments
In the following section, we present various empirical observations we have made regarding the grokking phenomenon. In Scction 2.1 we demonstrate that grokking can occur with GP classification and linear regression. This proves its existence in non-neute non-neural architectures, identifying a need for a more general theory of the phenomenon. Further, in Scction 2.2. we show that there is a way of inducing grokking via data augmentation. Finally, in Section [2.3] we examine directly the weight-space trajectories of models which grok during training, incidentally demonstrating the phenomenon in GP regression. Due to their number, the datasets used for these experiments are not described in the main text but rather in Appendix E
2.1 Grokking in GP Classification and Linear Regression
In the following experiments, we show that grokking occurs with GP classification and linear regression. the case of linear regression, a very specific set of circumstances were required to induce grokking. However, for the GP models tested using typical initialisation strategies, we were able to observe behaviours which are consistent with our definition of grokking.
2.1.1 Zero-One Classification on a Slope with Linear Regression
As previously mentioned, to demonstrate the existence of grokking with linear regression, very specific learning setting was required. We employed Dataset g with three additional spurious dimensions and two training points. Given particular example 2g from the dataset, the spurious dimensions were added follows to produce the new example x':
x'
20
z sin(100xoo)
(2)
The model was trained though the problem were regression task with outputs later transformed into binary categories based on the sign of the predictions To find the model weights, used SGD over standard loss function with mean squared error (MSE) data fit component and a scaled weight-decay
6TF (o) then the clasification of given point was negative and fo(x) O, then the class was positive.
4

---

Published in Transactions on Machine Learning Research (03/2024)
complexity term
L MSE(V.)) 1)
(w² =n²)² 0
Σ 1
(3)
60
In Equation 3 the term w' represents the individual weights of the linear regression model corresponding to each feature dimension, Further, i indexes the dimensionality of the variables w, po and do, eo is the noise variance, Mo is the prior mean, and og is the prior variance. For our experiment, 14; was taken to be 0 and oa to be 0.5 for all i. Regarding initialisation, was heavily weighted against the first dimension of the imput example: This unusual alteration to the initial weights was required for clear demonstration of grokking with linear regression.
The accuracy, complexity and data fit of the linear model under five random seeds governing dataset gener- ation is shown in Figure 1 Clearly, in the region between epochs 2 10a and 103, validation accuracy was significantly worse than training accuracy and then, in the region 2 10", the validation accuracy was very similar to that of the training accuracy. This satisfies our definition of grokking, although the validation accuracy did not always reach 100% in every case, Provided in Appendix H.1 is the accuracy and loss of a training run with a specific seed that reaches 100% accuracy.
We also completed a series of further experiments concerning model initialisation, weight evolution and the necessity of weight decay which we present in Appendix K We find that the resulting trends are consistent with the grokking mochanism we suggest in Section g+ and so are the evolution of the weights. Further, we show that without weight decay we do not see grokking. This demonstrates that some form of regularisation is required, providing evidence that the grokking mechanism we suggest might be both sufficient and necessary in this setting.
2.1.2 Zero-One Classification with a Gaussian Process
In our second learning scenario, we applied GP classification to Dataset g with a radial basis function (RBF) kernel:
k2)1 = exp (-2(01--2)) =²2²" - -22)
(4)
Here, O called the lengthscale parameter and a is the kernel amplitude. Both and a were found by minimising the approximate negative marginal log likelihood associated with a Bernoulli likelihood function via the Adam optimiser acting over the variational evidence lower bound (Hensman al. 2015 Gardner et al. 2018).
The result of training the model using five random seeds for dataset generation and model initialisation can be seen in Figure 2 The final validation accuracy is not 100% like the cases we will see in the proceeding sections. However, it is sufficiently high to say that the model has grokked. In Appendix H.2 we also provide the loss curves during training. As we later discuss in Section 4 there are some subtleties associated with interpreting the role of the complexity term.
In our third learning scenario, we also looked at GP classification. However, this time more complex algorithric dataset modified version of Dataset [ (with k 3) where additional spurious dimensions are added and populated using values drawn from a normal distribution. In particular, the number of additional dimensions is n = 37 making the total input dimensionality d = 40. We use the same training sctup as in Section 2.1.2 The results (again with five seeds) can be seen in Figure 3 with a complexity plot in Appendix H.3 and discussion of the limitations of this complexity measure Section 4
For both GP learning scenarios we also completed experiments without the complexity term arising under the variational approximation. The results of these experiments, namely lack of grokking, can be seen in Appendix L. This demonstrates that some form of regularisation is needed in this scenario and provides further evidence for the possible necessity of the grokking mechanism we propose in Section 3
7 As demonstrated by Hinton & van Camp (1993) this loss function has an equivalence with the MDL principle when fix the standard deviations of prior and posterior Gaussian distributions.
0 = 5-- 50-1 90-0-
9- 10-1 90-
5

---

Published in Transactions on Machine Learning Research (03/2024)
1.0
-0.1
Train Log Probabilities
Validation Probabilities
0.9
objective Value
-0.3
-0.5
0.6
-0.6
0.5
Train Accuracy Valldation Accuracy
-0.7
10P
10a
10a
107
109
10a
10a
102
Epoch
Epoch
Figure 2: Accuracy and log likelihoods on zero-one classification task with RBF Gaussian process. Note that the shaded region corresponds to the standard error of five training runs.
1.0
Train Probabilities
Validation Log Probabillties
-0.1
-0.2
-0.3
Objective
0.7
-0.4
0.6
-0.5
-0.6
Train Acc.
10a
Epoch
Epoch
Figure 3: Accuracy and log likelihoods on hidden parity prediction task with RBF Gaussian process. Note that the shaded region corresponds the standard error of five training runs. Acc. Accuracy and Val. is Validation.
2.2 Inducing Grokking via Concealment
In this section, we investigate how one might augment a dataset to induce grokking. In particular, we develop a strategy which induces grokking on a range of algorithmic datasets. This work was inspired by Merrill et al. (2023) and Barak et al. (2022) where the true task "hidden" in a higher dimensional space. This requires models to "Iearn" to ignore the additional dimensions of the input space. For an illustration of learning to ignore Figure 12 (Appendix J.1
Our strategy is to extend this "concealment" idea. to other algorithmic datasets. Consider (z, y), an example and target pair in supervised learning. Under concealment, one augments the example by adding random bits, labeled up to Vr, where the values 0 and have equal probability. The new concealed example is:
x'
[ro
00
To determine the generality of this strategy in the algorithmic setting, we applied it to 6 different datasets These datasets were chosen as they share a regular form and seem to cover a fairly diverse variety of algorithmic operations. each case, we used the prime 7, and varied the additional dimensionality k. For the model, we used a simple neural network analogous to that of Merrill et al. (023). This neural network
9Thee all governed by the same prime p and take two imput numbers.

---

Published in Transactions on Machine Learning Research (03/2024)
Regression Fit
ModuloAddition
ModuleSubtraction
ModulaDivision
Polynomial al
Polynomial al Tive
Grokknng Gap
ModujoouutppicatinnDbbbb.s.
10a
30
40
Additional Length
Figure 4: Relationship between grokking gap and number of additional dimensions using the grokking via concealment strategy. Note that z-values are artificially perturbed to allow for casier visibility of error bars. In reality they are either 10, 20, 30 or 40. Also, the data zero additional length removed (although still influences the regression fit). See Appendix T.2 for the plot without these changes.
consisted of hidden layer of size 1000 and was optimisod using SGD with cross-cntropy loss. The weight decay set to 10-2 and the learning rale to 10-1 Loss plots for all experiments shown in Appendix N
To discover the relationship between conccalment and grokking, we measured the "grokking gap" Au. In particular, we considered how an increase in the number of spurious dimensions relates to this gap. The algorithm used to run the experiment is detailed Algorithm [ (Appendix I.1 The result of running this algorithm can be seen Figure g In addition to visual inspection the data, a regression analysis was completed to determine whether the relationship between grokking gap and additional dimensionality might be exponential. The details of the regression are provided in Appendix [ and its result is denoted Regression Fit in the figure. The Pearson correlation coefficient (Pcarson, 1895 SciPy developers 2023
also calculated in log space for all points available and for each dataset individually. Further, we completed test of the mull hypothesis that the distributions underlying the samples are uncorrelated and normally distributed. The Pearson correlation r and p-values are presented in Table 2 (Appendix F.2) The Pearson correlation coefficients are high in aggregate and individually, indicating a positive linear trend in log space. Further, p values in both the aggregate and individual cases are well below the usual threshold of a 0.05.
In Appendix M grokking mechanism we suggest in Section g This analysis involved scaling the magnitude of weight matrices to determine how this would alter trends seen in Figure
also find analysis of this data augmentation tochnique with regards to the
2.3 Parameter Space Trajectories of Grokking
Our last set of experiments was designed to interrogate the parameter space of models which grok. We completed this kind of interrogation in two different settings. The first was GP regression on Dataset 10 and the second was BNN classification hyperparameters governing the kernel, we could see directly the contribution of complexity and data fit terms. Alternatively, for the BNN we aggregated data regarding training trajectories across several initialisations to investigate the possible dynamics between complexity and data fit..
concealed version of Dataset []] Since the GP only had two
2.3.1 GP Grokking on Sinusoidal Example
In this experiment, we applied a GP (with the same kernel as in Section 2.1.2 to regression of sine To find the optimal parameters for the kernel, Gaussian likelihood function was employed with

---

Published in Transactions on Machine Learning Research (03/2024)
Marginal likelihoad landscape
landscape
Camplexity anddscape
langtiscale
Log Longgh Langfhsccale
Log Lengh
0
C
-2
-2
-2
-4
-4
-6
A
-6
M
-2
0
0
-2
2
Log Dutputscale
Log Outputscale
Log Dutputscale
1.0
2.0
2.5
3.0
0.1
0.2
0.3
0.0
0.5
1.0
1.5
2.0
MSE for initialisation A
for initialisation
MSE for initiallsation
0.6
train validation
0.5
0.4
0.4
0.3
0.3
MSG
0.3
0.2
0.2
0.2
0.1
0.3
0.1
10
10a
10a
16a
10
107
10
10
10
107
102
10
Epoch
Epoth
Epoch
Figure Trajectories through parameter landscape for GP regression. Initialisation points A-C refer those mentioned in Section 2.3.1
exact computation of the marginal log likelihood. In this optimisation scenario, the complexity term is as described in Appendix D
To see how grokking might be related to the complexity and data fit landscapes, we altered hyperparameter initialisations. We considered three different initialisation types. In case A, we started regression in region of high error and low complexity (HELC) where a region of low error and high complexity (LEHC) was relatively inaccessible when compared a region of low error and low complexity (LELC). For case B, we initialised the model in a region of LEHC where LELC solutions were less accessible. Finally, in case C, we initialised the model in a region of LELC. As evident in Figure 5 we only saw grokking for case B. It is interesting that, in this GP regression case, we did not see a clear example of the spherical geometry mentioned in the Goldilocks zone theory of Liu et al. (2023a). Instead, more complicated loss surface is present which results in grokking.
2.3.2 Trajectories of a BNN with Parity Prediction
We also examined the weight-space trajectories of BNN (fa). Our learning scenario involved Dataset I with the concealment strategy presented in Section 2.2 Specifically, we used an additional dimensionality of 27 and parity length of 3. To train the model, employed SGD with the following variational objective:
(()) B (CrossFatrroyLLooss((())).) ())(())))IP()).
In Equation 5 P(O) is standard Gaussian prior on the weights and (o is the variational approximation. The complexity penalty in this case is exactly the model description length discussed in Section 1.2 with the overall loss function clearly a subset of Equation D
To explore the weight-space trajectories of the BNN we altered the network's initialisation by changing the standard deviation of the normal distribution used to seed the variational mean of the weights. This resulted network initialisations with differing initial complexity and error. We then trained the network based on these initialisations using three random seods, recording values of complexity, error and accuracy. The outcomes of this process are in Figure Notably, initialisations which resulted in increased grokking
8

---

Published in Transactions on Machine Learning Research (03/2024)
Error and Complexity
Average Error and Complexity
1.0
0.8
25
Normalised Grokking Gop
Complexity
2
Average Errer
15
Complediy
Avarage Complexity Required
10
0=1
( 0.5
10t
10a4
10-4
0.0
10P
10a
10a
10a
Emor
Epochs
Figure This figure illustrates grokking Bayesian Neural Networks (BNNs) using different standard deviation values (o) for variational mean initialisations. The left plot shows the error-complexity landscape during training. Points become less transparent as training progresses, indicating epoch advancement. Tri- angles mark the grokking point for each o, determined when validation accuracy first exceeds 95% after training accuracy reaches this level. Three trials per a contribute to these points. The right plot displays the average error and complexity across epochs, highlighting how complexity evolves during the training and grokking phases. Normalised Grokking Gap refers to the epoch difference between achieving 95% training and validation accuracy, scaled between zero and onc.
gap correlate with increased optimisation time regions of LEHC. Further, there seems to be a trend across epochs with error and complexity. At first, there is a significant decrease in error followed by decrease in complexity and is in this region, where complexity is decreasing most, that grokking occurs.
3 Grokking and Complexity
So far we have explored grokking with reference to different complexity measures across a range of models. There seemss to be no theory of grokking in the literature which can explain the new empirical evidence we present. Motivated by this, we suggest possible mechanism which may induce grokking in cases where solution search is guided by both complexity. We believe this condition to be compatible with our new results, previous empirical observations and with many previous theories of the grokking phenomenon.
To build our hypothesised grokking mechanism, we first make Assumption | is justified for the most common setting in which grokking occurs. Namely, algorithmic datasets. Tt also likely true for a wide range other scenarios.
We believe that Assumption
Assumption 1. For the task of interest, the principle of parsimony holds. That is, solutions with minimal possible complexity will generalise beller.
We then suggest Mechanism [ which we refer to as the complezity route to grokking.
Mechanism 1. Tf the low error, high complexity (LEHC) weight space is readily accessible from typical imitialisation but the low ertor, low complexity (LELC) weight space is not, models will quickly fond a low ervor solution which does not generalise. Given path between LEHC' and LELC regions which has non- non-increasing loss, solutions in regions of LEHC will slowly be guided toward regions of LELC due to regularisation. This causes an eventual decrease in validation error, which we see as grokking.
We do not claim that this is an exclusive route to the grokking phenomenon. Kumar el al. (0223) and others have demonstrated that grokking does not require an explicit regularisation scheme the neural network cases. However, we believe could be sufficient mechanism there. In addition, it may be the dominant mechanism in the non-neural network cases we present. Evidence for this is provided in Appendices K and where we retenstrate the need for regularisation in our linear regression and GP grokking cases.
9

---

Published in Transactions on Machine Learning Research (03/2024)
3.1 Explanation of Previous Empirical Results
We now discuss the congruence between our hypothesised mechanism and existing empirical observations. In Appendix G we draw parallels between our work and existing theory.
Learning with algorithmic datasets benefits from the principle of parsimony as small encoding is required for the solution. In addition, when learning on these datasets, there appear to be many other more complex solutions which do not generalise but attain low training error. For example, with neural network containing one hidden layer completing a parity prodiction problem, there is competition between dense subnetworks which are used to achieve high accuracy on the training set. (LEHC) and sparse subnetworks (LELC) which have better generalisation performance (Merrill et al. 2023 In this case, the reduced accessibility of LELC regions compared to LEHC regions seems to cause the grokking phenomenon. This general story is supported by further empirical analysis completed by Liu et al. (2022) and [anda al. (2023). Liu al. (2022) found that less accessible, but more general representation, emerges over time within the neural network they studied and that after this representation's emergence, grokking occurs. If the principle of parsimony holds, this general represenlation should be simpler under an appropriate complexity measure. Consequently, the shift could be explained by Mechanism [ Nanda et al. (2023) discovered that set of trigonometric identities were employed by a transformer to encode an algorithm for solving modular arithmetic. Additionally, this trigonometric solution was gradually amplified over time with the later removal of high complexity "memorising" structures. Indeed, is stated in that paper that circuit formation likely happens due to weight decay. This fits under Mechanism ! the model is moving from an accessible LEHC region where memorising solutions exist to LELC region via regularisation.
The work by Liu et al. 2023a) showed the existence of grokking non-algorithmic datasets via alteration of the initialisation and dataset size. From Mechanism [ we can see why these factors would alter the existence of grokking. Changing the initialisation alters the relative accessibility of LEHC and LELC regions and reducing the dataset size may lessen constraints on LEHC regions which otherwise do not exist.
The study by Levi al. (2023) on grokking in linear models complements our hypothesis on grokking's nature, particularly in the linear regression context. Their focus on the divergence between training and generalisation loss in linear teacher-student. models, influenced by input dimensionality and weight decay, parallels our findings in inducing grokking via dataset manipulation. Our approach, especially with Dataset g where we add spurious dimensions, aligns with their emphasis on input structure's role. This similarity bolsters our claim that grokking emerges due to the initial inaccessibility of LELC solutions. Furthermore, our exploration in GP models through data concealment, adding uninformative dimensions, demonstrates that these relationships extend into more complex scenarios beyond linear estimators.
3.2 Explanation of New Empirical Evidence
Having been proposed to explain the empirical observation we have uncovered this paper, Mechanism [ should be congruent with these new findings the first of which the existence of grokking in non-neural models. Indeed, one corollary of our theory (Corollary [ is that grokking should be model agnostic. This is because the proposed mechanism only requires certain properties of error and complexity landscapes during optimisation. It is blind to the specific architecture over which optimisation occurs.
Corollary 1. The phenomenon of grokking should be model agnoslic. Namely, il could occur in any selling in which solution search is guided by complezity and error.
Another finding from this paper is that of the concealment data augmentation strategy. We believe this can be explained via the lens of Mechanism ] as follows. When dimensions are added with uninformative features, there exist LEHC solutions which use these features. However, the number of LELC solutions remains relatively low as the most general solution should have no dependence on the additional components. This leads to an increase in the relative accessibility of LEHC regions when compared to LELC regions which in turn leads to grokking.
10

---

Published in Transactions on Machine Learning Research (03/2024)
4 Discussion
Despite some progress made toward understanding the grokking phenomenon in this paper, there are still some points to discuss. We start by assessing the limitations of the empirical evidence gathered. This is important for a balanced picture of the experimentation completed and its implications for our suggested grokking mechanism, Having examined these limitations, we can provide some recommendations regarding related future work in the field.
4.1 Limitations of Empirical Evidence
experimenlation with linear regression may be criticised for the specificity of the learning setup required to demonstrate grokking and for the value of the final validation accuracy. We note that the first critique is not reasonable in the sense that should be able to show grokking under "normal" circumstances since grokking does not appear under "normal cireumstances: However, if one wanted to widen the scope of learning settings where Mechanism | appliess further experimentation is needed. It could be the case that, with only one setting, we saw results consistent with Mechanism [ but under another learning sconario, our mochanism could become inconsistent. We do not consider the second critique to be significant. For our purposes, grokking need not have 100% accuracy as not all general solutions provide that. However, if this is desired, we provide a case where this occurs in Appendix H.
In Section 2.1
There are also reasonable critiques concerning the experimentation completed on GP classification. The most pressing might be concerns over the measurement of complexity presented in Appendices H.2 and This is due to the way the model is optimised. Namely, via maximisation of the evidence lower bound:
H.3
N
(ELBO( = Σ
- (KT.(a
Unfortumately, optimisation of this value leads to changes in both the variational approximation and the hyperparameters of the prior GP. This presents problem when trying to the results of GP classification to validate Mechanism [ The hyperparameters control the complexity of the prior which then influences the measured complexity of the model via the KL divergence. Consequently, the complexity measurement at any two points in training are not necessarily comparable. To disentangle optimisation the hyperparameters and the variational approximation, one could complete a set ablation studies. For this, one would keep either the hyperparameters or the variational approximation constant and alter the other variable. By doing so, one would be able to validate more directly Mechanism D with GP classification. Additionally, one might need to alter the learning setting to retain grokking under a new approximation scheme such Laplace's method. Further discussion and experimentation are provided in Appendix O
Due to the simplicity of the model considered in Figure 5 it is hard to criticise experimentation completed there. However, the experimental design of the BNN lacks generality. Indeod, it is difficult to know the subspace from which the BNN was initialised is indicative of general trends about the weight space. However, the values chosen were indicative of typical initialisation values. Thus, we can say that for "normal" cases that might be encountered by practitioner, the BNN weight trajectories are representative.
4.2 Future Work
An interesting outcome of experimentation in this paper was the discovery of the conccalment data augmen- fation strategy. As far as the authors are aware, this is the first data augmentation strategy found which consistently results in grokking. Additionally, its likely exponential trend with the degree of grokking is of great interest. Indeed, we know that the volume of a region in an n-dimensional space decreases exponentially with an increase in n. This fact and the exponential increase in grokking with additional dimensionality could be connected. Unfortunately, at this point in time, such a connection is only speculative. Thus, a more theoretical analysis might be warranted which seeks to examine this relationship.
Additional work should also be conducted investigate the need for regularisation in grokking. In our work, we have suggested mechanism for grokking which requires complexity penalty. We believe this
11

---

Published in Transactions on Machine Learning Research (03/2024)
mechanism to be broadly compatible with previous experimentation and theory produced for cases with such penalty. However, the work completed by Levi et al. (2023) and Kumar et. al. (2023) show that grokking need not require a complexity penalty in every case. Through the novel ablation studies provided, we have begun to draw a boundary around cases where grokking does seem to need a penalty like weight decay or KL divergence. Nonetheless, there much still left. to do order investigale the role of explicit regularisation in grokking.
4.3 The Real-World Applications of Grokking
We would also like to briefly touch upon the possible applications our work on grokking. We believe there are several ways it may be useful. The most obvious case would be the discovery of grokking in datasets important to ML practitioners. by, for example, modifying their initialisation strategy. Indeed, in GPs, offering unique insights relevant to grokking in that model class. Another important consideration is the relationship between grokking and concealment. Given that some form of concealment could occur in real-world tasks, it merits analysis to determine whether any form grokking is present and, if absent, to understand why.
this scenario, practitioners could leverage our analysis to mitigate grokking
paper is the first to examine grokking
5 Conclusion
We have presenled novel empirical evidence for the existence of grokking in non-neural architect ures and discovered a data angmentation technique which induces the phenomenon. Relying upon these observations and analysis of training trajectorics in a GP and BNN, we suggested a mochanism for grokking models where solution search is guided by complexity and error. Importantly, we argued that this theory is congruent with previous empirical evidence and many previous theories of grokking, In future, researchers could extend the ideas in this paper by undertaking theoretical analysis of the concealment strategy discovered and by conducting further studics to assess the role of complexity penaltics.
Supplementary Material
All experiments be found at this GitHuu page They have descriptive names and should reproduce the figures seen in this paper. For Figure 6 the relevant experiment is in the feat//nfo-therr-deesii branch.
Broader Impact Statement
We have completed empirical experiments with the grokking phenomenon using synthetic data. It is difficult to identify any specific ethical concerns. Of course, broader ethical reservations, present in any basic machine learning research, might be relevant.
Acknowledgements
We would also like to acknowledge Russell Tsuchida, Matthew Ashman, Rohin Shah, Yuan-Sen Ting, Oliver Balfour and Yashvir Grewal for their valuable input. In addition we would like to thank the Tuckwell scholarship program for funding the undergraduate studies of Jack Miller and Charles O'Nllll.
12

---

Published in Transactions on Machine Learning Research (03/2024)
References
Alex Altair. An Intuitive Explanation of Solomonoff Induction
Less-
Wrong an imtutiive-ep..aattion ofcllooooo---ooooeee
lesswrong.com.
https://www lesswrong. http:///osssssycccccbbbaaeeettte
ootpaaatttoooo---oooooooooo----- solomoooff-innucteoeo.oooooooeee 2012. [Accessed 31-07-2023..
Boaz Barak, Benjamin Edelman, Surbhi Goel, Sham Kakade, Eran Malach, and Cyril Zhang. Hidden progress deep learning: SGD learns parities near the computational limit. Advances in Neural Information Processing Systems, 35:21750-21764, 2022.
Matthias Bauer, Mark der Wilk, and Carl Edward Rasmussen. Understanding probabilistic sparse Gaussian process approximations. Advances in Neural Information Processing Systems, 29, 2016.
Kenneth P. Burnham and David R. Anderson. Model Selection and Mullimodel Inference: A Practical Cormaaaion-Thhoretie Approach. Springer, 2nd edition, 2004.
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley-Interscience, USA, 2006.
ISBN 0471241954.
Xander Davies, Lauro Langosco, and David Krueger. Unifying grokking and double descent, 2023.
Jacob Gardner, Geoff Pleiss, Kilian Q Weinberger, David Bindel, and Andrew G Wilson. Gpytorch: Black- box matrix-matrix Gaussian process inference with GPU acceleration. Advances in Neural Information Processing Systems, 31, 2018.
lan Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016.
James Hensman, Alexander G. de G. Matthews, and Zoubin Ghahramani. Scalable variational Gaussian process classification. In Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, volume 38, 2015.
Geoffrey E. Hinton and Drew van Camp. Keeping the neural networks simple by minimizing the description length of the weights. In Proceedings of the Sixth Annual Conference on Computational Learning Theory, pD. 13, 1993.
Xia Hu, Lingyang Chu, Jian Pei, Weiqing Liu, and Jiang Bian. Model complexity of deep learning: A survey, Knowledge and Information Systems, 26129, 2021.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems, volume 31, 2018.
Tanishq Kunar, Blake Bordelon, Samuel J. Gershman, and Cengiz Pehlevan. Grokking as the transition from lazy to rich training dynamics, 2023.
Noam Levi, Alon Beck, and Yohai Bar-Sinai. Grokking in linear estimators-a solvable model that groks without understanding, arXie preprint arXiw:2310.16441. 2023.
Ziming Liu, Ouail Kitouni, Niklas Nolte, Eric Michaud, Max Tegmark, and Mike Williams. Towards understanding grokking: An effective theory of representation lcarning. Advances in Neural Information Processing Systems, 35:34651 14663,, 2022.
Ziming Liu, Eric J. Michaud, and Max Tegmark. Omnigrok: Grokking beyond algorithmic data. Interna- tional Conference on Learning Representations, 2023a.
Ziming Liu, Ziqian Zhong, and Max Tegmark. Grokking as compression: nonlinear complexity perspective, 2023b.
Kaifeng Lyu, Jikai Jin, Zhiyuan Li, Simon S. Du, Jason D. Lee, and Wei Hu. Dichotomy of early and late phase implicit biases provably induce grokking, 2023.
13

---

Published in Transactions on Machine Learning Research (03/2024)
David J. C. MacKay. Information Theory, Inference, and Learning Algorithms. Cambridge University Press, 2003.
William Merrill, Nikolaos Tsilivis, and Aman Shukla. tale of two circuits: Grokking competition of sparse and dense subnetworks, 2023.
Shikhar Murty, Pratyusha Sharma, Jacob Andreas, and Christopher D. Manning. Grokking of hierarchical structure in vanilla transformers, 2023.
Neel Nanda, Lawrence Chan, Tom Lieberum, Jess Smith, and Jacob Steinhardt. Progress measures for grokking via mechanistic interpretability, 2023.
Karl Pearson. Note on Regression and Inheritance in the Case of Two Parents. Proceedings of the Royal Society of London Series I, 28:240-242, Jamuary 1895.
Alethea Power, Yuri Burda, Harri Edwards, Igor Babuschkin, and Vedant Misra. Grokking: Generalization beyond overfitting on small algorithmic datasets, 2022.
Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian processes for machine learning. MIT Press, 2006.
SciPy developers. sedpysstats.pparsoor scipy v1.11.4 manual. https://docs scwpyycccpp......c..... orripy..rrg/do/sscipy///
refeerrence/eenerrtte////ssyyy www.stttttttt.rrrrr..ee html 2023. Accessed: 2024-01-14.
Claude Elwood Shannon. A mathematical theory of communication. 27:379 423, 1948.
The Bell System Technical Journal,
Vikrant Varma, Rohin Shah, Zachary Kenton, János Kramár, and Ramana Kumar. Explaining grokking through circuit efficiency, 2023.
Paul MB Vitányi. How incomputable is Kolmogorov complexity? Entropy, 22(4):408, 2020.
Paul MB Vitányi and Ming Ti. Minimum description length induction, Bayesianism, and Kolmogorov complexity. IEEE Transactions on Information Theory, 46(2):446-464, 2000.
Hazar Yueksel, Kush R. Varshney, and Brian Kingsbury. A Kolmogorov complexity approach to generalization in deep learning. 2019.
Bojan Zunkovič and Enej llievski. Grokking phase transitions in learning local rules with gradient descent, 2022.
14

---

Published in Transactions on Machine Learning Research (03/2024)
A
Summary of Existing Empirical Work on Grokking
Research Paper
Architecture
Category
Dataset Description
Power et al. (2022)
Transformer
Algorithmic
Problems of the form o b where is binary operation and "a", "b", "o", "=" and "c" are tokens.
Zunkovič & Ilievski (2022)
Perceptron Tensor Network
Rules Based
1D collular automaton rule, ID exponential and D-dimensional uniform ball.
Liu ct al.
[2022]
MLP
Algorithmic
Addition modulo P, regular ad- dition and MNIST.
Transformer
Image class.
Nanda et al. (2023
Transformer
Algorithmic
Addition modulo P. Regular addition, MNIST, IMDb dataset and QM9,
Liu et al.
(2023a
MLP
Algorithmic
LSTM
Image class.
GCNN
Language
Molecules
Merrill et al. (2023)
MLP
Algorithmic
Parity prediction and operations
modulo prime.
Davies et al.
(2023
Transformer
Algorithmic
Addition modulo P.
Barak et al.
20022
MLP
Alg Algorithmic
Parity prediction task.
Transformer
PolyNet
Murty et al. (2023)
Transformer
Language
Question formation, tense- inflection and bracket nesting XOR, S4 group operation and bitwise XOR.
Liu el al. (2023b)
MLP
Algorithmic
Varma et a.. (2023
Transformer
Algorithmic
Similar to Power al. (2022)
Table 1: Summary datasels and architectures which the grokking phenomenon has been studied. Note that class. is short for classification.
15

---

Published in Transactions on Machine Learning Research (03/2024)
B Kolmogorov Complexity
The Kolmogorov complexity is one of several measures of complexity discussed in this paper. In some sense, it is the measure of complexity with the least prior knowledge used to generate its value. Definition B.1 (Kolmogorov). According to Yueksel et al. (2019) the Kolmogorov complexity Ke of a string I with respect to a universal computer U is:
(y(x)= min l(p)
(7)
p:U(p)=
where p denotes a program and l(p) is the length of the program in some standard language.
Essentially, the Kolmogorov complexity is the length of the minimal program required to produce a string representation of model. To illustrate this point, consider the three strings presented in Figure. 7 Let us assume that each of the associated programs are minimal under some language understood by a universal computer _ In this case, the first string would have the least complexity as the program specifying it requires 52 characters, the second string would be more complex requiring 105 and the third would be most complex requiring 106. In the Kolmogorov formalism, if we have members f. h E I and the minimal program to produce the string representation of f is longer than h, it is more complex.
aaaaaaaaaaaaa0а8
ababsbababababab
abodabcdabodaboc
Program
Program
Program
Idee !" for 1 in range(0, 16): builder *= "a"
builder Ider
builderr
for in range(0, 16):
13
for 1 in rangel8, 4) 1 I=
8:
builder "a"
builder "abcd"
else: builder += "b"
else: 17
10
builder += "abce"
Figure Illustration of Kolmogorov Complexity
With this Kolmogorov measure of complexity we can formalism the principle of parsimony under a com- putational picture. To do so, we use Solomonoff's theory of inductive inference. In Solomonoff induction, assume that we have observation about the world In addition, we have set of hypothesis H about that observation. We assume that these hypothesises are computable in the sense that each can be run on a Turing machine producing o. Further, we make a metaphysical assumption that true hypothesises are generated randomly using an unbiased process whereby the binary sequence defining sequenee: 0, 1 or END. In this setting hypothesis h generates an observation but has smaller Kolmogorov complexity than other hypotheses generating o, it is more likely (Altair 2012).
0 which can be encoded in binary string,
H is generated by choosing between three options at every point in the
B.1 Approximating Kolmogorov Complexity using Entropy
Unfortunaelly, the Kolmogorov complexity of a string (here a model) is non-computable [Vitányi 2020 However, we can approximate with concept from information theory (Shannon 1948 entropy of a stochastic process which produces that string (or model).
Namely, the
Theorem 1. Let stochastic process {X,) be draum i.i.d. according to the probability mass function f(x), X, where X is a finile alphabet. According to Cover & Thomas (2006), we have the limil::
E [[((X + H(X).
(8)
Foror example, ignore the fact. that we could simply print the strings using fewer character than these programs.
16

---

Published in Transactions on Machine Learning Research (03/2024)
Le. the expected Kolmogorov complecity of n-bit string approaches the entropy of the distribution from which characters in that string are drawn.
Thus, if we treat each parameter of model as random variable, may calculate the approximate Kolmogorov complexity of the model by considering the entropy of the distribution over the parameters which make the model. For example, if we assume that each parameter W in a particular model (/) is distributed normally, then the approximate IT distribution (after quantisation) for W is given in Equation Hinton & van Camp 1993):
W exp
p(W) = 2t
(9)
2
Now that we have a distribution over W, we can calculate H(W::
H(W) = Ep - In p(W)]
Ep - In t 1
W
)
exp
2T
Bp [W2 + const.
Given this expression for HW), the approximate Kolmogorov complexity is then:
N K(f) - Bw Bw? + const.
(10)
Notably, K(f) is proportional to the square of the weights of the network. Consequently, by minimising the approximate Kolmogorov complexity under the assumption of normality, we also minimise the L2 norm of the weights. This is equivalent to the familiar weight decay regularisation strategy.
B.2 Connection Between Kolmogorov Complexity and Bayesianism
We can also relate Kolmogorov complexity Bayesian inference. Consider the case where we are finding parameters of model using the mazimum posteriori estimator. In this paradigm, we wish to choose the model fo to maximise P(JID) where D is the data. According to Vitányi & Li 2000), this is equivalent to finding l such that:
fo min { (- log P(D)fe) log P(fe) + log P(D))
0
(11)
min {- log P(D]Sa) log P(fo)}
8
If we assume our hypothesis class to be finite and take the universal prior we can make the substitution log P(fe) = K(fa) and - llog P(D]fa) = K K(D)fe) (Vitányi & Li 2000). This gives:
f min (fe) + K(DI))))
(12)
Hence, under the universal prior, the mazimum a posteriori estimator is equivalent to the minimiscr of the Kolmogorov complexity of the model and of the data given the model.
Note that Equation in practice very good approximation, since the quantisation is much smaller than the standard deviation of 1.
17

---

Published in Transactions on Machine Learning Research (03/2024)
C Model Description Length
To understand model description length, we will consider two agents connected via communication channel. One of these agents (Brian) is sending a model across the channel and the other (Oscar) is receiving the model. Both agree upon two items before communication. First, anything required to transmit. the model with the parameters unspecified. For example, the software that implements the model, the training algorithm used to generate the model and the training examples (excluding the targets). Second, a prior distribution P over parameters in the model After initial agreement on these items, Brian learns set of model parameters 0 which are distributed according Q. The complexity of the model found by Brian is then given by the cost of "describing" the model over the channel to Oscar. Via the "bits back" argument (Hinton & van Camp 1993), this cost is:
[(fo) = (x
(13)
While the model description length is a relatively simple and quile general measure of model complexity, it relies upon critical assumption. Namely, that the amount of information contained in the components agroed upon by Brian and Oscar should be small shared among different models being compared. For- lunately, this is usually the case, especially in our experiments. When analysing the grokking phenomenon, we generally agree upon priors and look at the complexity of model across epochs in optimisation. Thus, there is complete shared information cost outside of changes which occur during optimisation.
The model description length is often combined with a data fit term under the minimal description length principle or MDL. (MacKay 2003). One can understand this principle by considering the following scenario. Oscar does not know the training targets Y but would like to infer them from X to which he has access. To help Oscar, Brian transmits parameters & which Oscar then usees to run fe on X. However, the model is not perfect; so Brian must additionally send corrections to the model outputs. The combined message of the corrections and model, denoted f), has a total description length of:
f(), C(fo) + L(D)fo).
(14)
In reference to Equation 1 the model description length is taking the role of the complexity term and the residuals are taking on the role of the data fit. The model which minimises fe) is deemed optimal under the MDL principle (Hinton & van Camp 1993) and also under our generalised objective function in Equation
Notably, the MDL principle is equivalent to two widely used paradigms for model selection. The first is MAP estimation from Bayesian inference where L(fs) comes to represent prior over the parameters which specify fo (MacKay 2003 Alternatively, if one calculates L(D, fe) under Gaussian prior and posterior where the standard deviation of these distributions are fixed in advance, the model complexity term reduces to a squared weight penalty and the data fit is proportional to the mean squared error (Hinton & van Camp. 1993 12
12see Equation 4 of Hinton & van Camp 1993
18

---

Published in Transactions on Machine Learning Research (03/2024)
D A note on GP Complexity
While the model description length is equivalent to many complexity measures used in model selection, it is not equivalent to all. For example, we complete some experinentation with GP regression where we observe grokking across optimisation the kernel hyperparameters.
The posterior distribution of these
kernel parameters is given by:
NO ()p((() p(0) J plulf. (()(()) p(y X)
(15)
p(ulx)
From here could use MAP-estimation to find 0 which we know is equivalent to the MDL. However, it is standard practice in GP optimisation to find 0 which maximises p(yl X, 0) RRasmussen & Williams) 2006).
It turns out p 0) itself contains regularising term which is often labelled the complexity Rasmussen
& Williams 2006
log p(y)
1 2
Ko y
log Kol
T1 log 2t
(16)
2 norma lisation
data fit
complexity
In Equation 16 this so-called complexity penalty characterises "the volume of possible datasets that are compatible with the data fit term" (Bauer et al. 2016 This clearly distinct from the model description length. However, Equation 16 still congruent with Equation and thus amenable to analysis in this paper. As we will see, even though this definition of complexity not equivalent to the description length, it seems to serve the same function empirically and is treated in the same way by the mechanism propose for grokking.
Note that in the equation, Kg K2 of which is the covariance function for targets with Gaussian noise of variance o2
19

---

Published in Transactions on Machine Learning Research (03/2024)
E Datasets used in Experimentation
Many datasots were used for the experimentation completed in this paper. They are were cither found in Merrill et al. (2023). Power et al. [0022] or were developed independently. Although grokking has been seen on non-algorithmin datasets (Liu et al. 2023a we restrict ourselves to these and a basic regression task since our focus is a theoretical exploration of the phenomenon via the modification other inducing variables. Work on larger datasets may have hindered this exploration.
Dataset 1 (Parity Prediction Task). In the purily prediction lask, the model is provided with o binary sequence x of length The target y the parity of the sequence iee. the product of the sequence if -1 and 1 is 1.
Datasct (Prime Modulo Addition Task). In the prime modulo addition task, prime p and two numbers in the runge [0, are chosen. These numbers are represented by one hot encoding and the model musl predict their addition modulo p.
Dataset 3 (Prime Modulo Subtraction Task). The prime modulo subtraction task has the same setup as Datasct but is subtraction.
Dataset (Prime Modulo Division Task). The prime modulo division task has the same setup as Dataset 2 but is division.
Dataset 5 (Prime Modulo Polynomial Task). The prime polynomial division task has the same setup as Datasct but the model tries to predict the result of the equation:
I ro x² xy + v²2 mod p
(17)
Dataset (Extended Prime Modulo Polynomial Task). The eztended prime polynomial division task has the same selup Dalasel but the model tries to predict the result of the equation:
I zoy= x2 xy x² + mod p
(18)
Datasct 7 (Extended Prime Modulo Multiplication Task). The extended prime polynomial division task has the same selup as Dalaset but the model tries to predict the resull of the equalion:
x zoy=r-y-a mod p
(19)
Dataset (1-0 Classification). In this classification task, model is attempting distinguish whether a point will take value of 0 or These points are normally distributed (with = 1) around and have label 0 and y if they are above.
y ==0 if they are below
Dataset 9 (1-0 Classification on a Slope). In this classifieation lask, a model is allempling to distinguish whether point will be above O not. The values of these points normally distributed (with 1) around 0 and the y values are given by the linear equation:
y 0.3z
(20)
Dataset 10 (Regression on Sine Wave). In this regression task, model is atlempting to predict the value of the equation:
y = A sin + o) + Be
(21)
where by default A 1 T 2= values in the training set are modified so that the function is not necessarily on uniform support by adding Gaussian noise of the same form as
0, -
= 0.1 and e is noise distributed according to (0, 1). Further x
20

---

Published in Transactions on Machine Learning Research (03/2024)
F Statistical Analysis of the Concealment Strategy
F.1 Regression Method
Given a matrix X of pairs (1 where 1 is the additional length and ó is the recorded grokking gap, we first transform the y-values into log space. That is, the dataset of pairs is given by:
x' = Xo In x1]
(22)
Then we find the optimal cocfficients a and b such that the model:
aX. +
(23)
has minimal squared error with respect to the labels Xi. Returning from log to regular space, the function:
6 exp (al b)
(24)
is then proposed relationship between additional dimensionality and grokking gap.
F.2 Correlation and p- p-Value Results
Dataset
P
Combined
0.92
1.46 10
Addition
0.933
3.91
10-r
Subtraction
0.914
1.84 10-6
Division
0.967
4.659
Polynomial
0.959
1.860 10
Extended Polynomial
0.906
2.981
10 8
Extended Multiplication 0.942
1.484
10-7
Table 2: Table summarising the Person correlation and null hypothesis likelihood for concealment data in log space. Note that all datasets are under a modulo argument.
21

---

Published in Transactions on Machine Learning Research (03/2024)
G Connection Between the Complexity Theory of Grokking and Previous Theories
The complexity theory of grokking unifies loss and representation based thcories of grokking under a single framework. In the text below, we show how each may be seen as an example of the behaviour described in Mechanism
The loss-basod explanation of Liu al. (2023a) asserts that in the weight space of model there exists a Goldilocks zone of high generalisation. In cases of grokking, models will quickly find over-fitting solutions before being guided towards this Goldilocks zone via weight decay. As previously mentioned, weight norm can be seen measure of model's description length. Thus the guidance of weight norm is towards regions of lower complexity. Additionally, via Assumption | we can say that the Goldilocks zone must be region of LELC since good generalisation comes from lower complexity. Consequently, this theory can be viewed as an instance of our broader framework with over-fitting solutions constituting LEHC and the Goldilocks zone conslituting LELC.
The use of the LMN by Liu al (2023b) also congruent with our theory of grokking, In the paper, the authors introduce LMN as complexity measure and show that decrease in LMN after a period of high training performance leads to grokking solution. Under Mechanism [ LMN is one instance of a complexily measure which can result in grokking.
Theorics which use representation dynamics as a means of explaining grokking can also be placod in our framework. Via Assumption [ more general represenlations should have a relatively low complexity. Thus, representation descriptions which talk of an emergence of general structures after the initial creation of memorising structures are talking of a transition from LEHC to LELC. Indeed, in neural networks it may be the case that LEHC solutions often be characterised as "memorising" and LELC "general circuits." However, in other models we require the more abstract language of Mechanism 1
22

---

Published in Transactions on Machine Learning Research (03/2024)
H Additional Model Experiments
H.1 Linear Regression with a Specific Seed
In the following experiment, we take the same learning setting in Section 2.1.1 but restrict ourselves to one seed which shows a clear case of grokking. This case is presented in Figure 8
Data ft
Tann Complesdty
0.9
OteerveWii Whee
13-
Tain Widdri
10a
100
10:
107
10'
101
10'
10'
Spoch
Esoch
Figure 8: Accuracy, complexity and data fit on zero-one slope classification task with a linear model and one seed.
H.2 GP Classification Complexity for 0-1 Classification
We take the same learning setting in Section 2.1.2 showing the complexity and error curves in Figure g In this figure, the data fit term is the negation of the error in Equation 0 Alternatively, the complexity is measured as the KL divergence in Equation That is, the data fit. and complexity are:
N
data fit =
Σ 1=1
E ( [og)(u(ff))
complexity = (Llgg(f)llpeff))
(25)
23

---

Published in Transactions on Machine Learning Research (03/2024)
Train Data Fit
Train Complexity
Objective
0.4
0.2
0.0
10a
10a
102
10a
Epach
Figure 9: Complexity and data fit. for GP classification the 0-1 task.
H.3 GP Classification Complexity for Algorithmic Case
We take the same learning sctting as in Section 2.1.2 showing the complexity and error curves in Figure g as defined in Equation 25
Complexities
Negative Data Fit
Objectiv Value
0.6
0.2
10a
10a
102
Epoch
Figure 10: Complexity and data fit. for GP classification on the concealed parity prediction task.
24

---

Published in Transactions on Machine Learning Research (03/2024)
Grokking via Concealment
1.1 Algorithm
Algorithm Algorithm for relationship of As with dimensionality
Require: [L] > 0
4 Number of additional lengths Number of datasets b Number of random seeds Threshold for high accuracy Number of epochs
Require: [D] > 0
Require: [R]
y 0.95
N 1500
aeray_of_avd avg, array_of_ste std 0,
for each / in L do
5: length_scale_ _age, for each d in D do
t D.
6:
7:
dataset_gap < do
for each
set jos_random_seed] model +- initialise_modell)
10:
11:
training_accuracy,. www.dationn accpuracccccrraycccaaaaaaa <- train_modelImodel,,, d)
12:
training_index +- first index www.aaeettainnnggaccrraaa 7)
13:
ieiidation_indes + first_indes firss_idde__booeeaaalddddee www.eeeraaadddditoooacaaarar 7)
14:
As - wwwiiattioonineeeeeee index - training_index
15:
16:
end for
17:
avg_gap, std_gap avg(dataset_gga _gapa) std(dataset__ag
18:
length_scaal scale ltt_s_sclla___appp_eeee www.aaaaeeeelllag.eee.. gap)
19:
20:
end for
21:
array_ weeppppeeeeennn_seeaoepeeeeeeeee avgs)
22:
array_of appeedt baigth_scale_stdee
23: end for
25

---

Published in Transactions on Machine Learning Research (03/2024)
1.2 Original Regression Plot
Below present version of Figure where we have reversed alterations to the error bars and included data from the 0 additional length category.
Regression
Mockilokddiliinnakkk
Mocullefubtratioonlns
MocklloDiviianTTak
Polynomiallask
Polynomaa/askktv
MocklooMuliiliicaai Di
Crokking
Additional Length
Figure 11: Relationship between grokking gap and number of additional dimensions using the grokking via concealment strategy.
26

---

Published in Transactions on Machine Learning Research (03/2024)
J Illustrative Figures
J.1 Lengthscale Plot of GP with Parity Prediction
In Scction 2.1.2 GP is used for the hidden parity prediction task. With this dataset, models should Iearn to disregard dimensions with spurious data. In this case, the spurious dimensions are those above three. Presented in Figure [2] is a plot the length scale parameter over the course of hyperparameters. As can be seen in that figure, longth scale incrcasos for for input dimensions above three but decrease for input dimensions three and below. This is expected larger length scale cannot discern small changes in the input dimension and thus renders them uninformative.
Epoch 10
1.4
Inverse bngehscale
1.2
1.0-
0.6
0.4
0.2
Epoch
2.0
Invere lengthocale
1.5
1.0
0.5
0.0
Epoch 150
lengthscale
Input dimension
Figure 12: Example of GP kernel length scale for hidden parity prediction task. Note that inverse length scale refers to 1/4, where 4 is the length scale associated with dimension i.
27

---

Published in Transactions on Machine Learning Research (03/2024)
J.2
Illustrative Example of Grokking
1.6
1.4
1.2
Loss
0.8
0.6
A
0.4
0.2
0
0
10
20
25
35
40
Epochs
Figure 13: Illustrative example of the grokking phenomenon. line is the validation loss.
The red line is the training loss and the blue
28

---

Published in Transactions on Machine Learning Research (03/2024)
K Further Analysis of Linear Classification
In this appendix we provide a further analysis of the lincar classification grokking case covered in Section 2.1.1 Specifically, we examine the congruency of these results with our grokking hypothesis (Section 3 To do so, we conducted three further experiments. In the first we alter the way we initialise the model and consider the trend between the grokking gap; complexity gap and data fit gap (defined in the relevant subsection). In the second experiment, we examinc the cvolution of weights in the linear model over the course of optimisation. Finally, in the third experiment we remove the weight penalty altogether and find that this removes grokking altogether.
K.1 Altering the Initialisation of the Linear Model
In this experiment we considered the trend between three variables whilst altering the model's initialisation Specifically changed the value of in the following equation:
wp
a 1 a
1 1 1-a
(26)
The three variables of interest are:
The grokking gap (defined in the introduction)
The complexity gap. Le. the difference in complexity between the point that the model does well on the training set when compared to the validation set.
The data fit gap. Lee. the difference the data fit term between the point that the model does well on the training set when compared to the validation set.
Under the grokking mechanism we propose, we would expect these variables to be related in the following ways. Firstly, the grokking gap should be decreasing function with the complexity gap since the required time to go from a region HELC to LELC determines the gap width. Secondly, the data fit gap should be increasing with initialisation weight since in these cases we see a smaller grokking gap with learning driven primarily by the data fit rather than complexity (we are in region of HELC). In Figure 14 one see that these predicted trends are supported when one alters in Equation 26
K.2 Examining the Evolution of Weights in the Linear Model
We also considered the evolution of weights in the linear model. Specifically, experimented with different values of in Equation 26 examining the 4 weights of the linear regression model in each case (all values were averaged across five random seeds). The results of this experinentation are in Figure 15 We found
that a similar solution was reached no matter the initialisation employed. In addition, the three "distracting" values of the input are slowly "ignored" over the course of training. This corresponds to a lower complexity solution under the La norm employed for the regression.
(4Emloyyin five random seeds which averaged produce Figure.
14
29

---

Published in Transactions on Machine Learning Research (03/2024)
Train Fit Gap
2.0
2.0
15
1.5
600
Grokking Gap
Complexity Gap
10-4
10'
10-1 Inttsilsation Weight fins Component
104
Indilllaaion Neight finst Component
Gaps refers to the particular gap (grokking, complexity or data fit) which is presented in the graph. The æ-axis is the initialisation weight of the first component i.e. a in Equation 26 Note that all gaps are approximately when a is 1 since the solution to the problem given by the first component of the input. The number in parentheses after "Grokking Gap" refers to the value points on the graph are divided by.
Figure 14: Further initialisation analysis of the model presented in Section 2.1.1
Weight
Weight
Weight: 0.
Weight: 3.16e
0.8
Weight: 1.00e-02
0.8
Weight: 3.16e-02
Weight: 1.00e-01
0.6
0.6
Weigge
Weignt
0.4
0.4
0.2
0.2
0.0
0.0
Tpocs
Epoch
Weight
Weight
Weight Salee
Weight Value
18
Epoch (120)
Epach 0C10)
Figure 15: Evolution of weights in the linear model. Black crosses correspond to the values of the weights at which grokking occurred.
30

---

Published in Transactions on Machine Learning Research (03/2024)
K.3 Removing Weight Decay
If we remove the weight penalty lerm used for oplimisation of the linear model, we do not see grokking even after 1,000,000 epochs of optimisation. The lack of grokking can be seen in Figure 16 Note that only every 100th point is plotted.
10
Training Fit Training L2 Norm
A20005
10a4
10
0.5
Training Accuracy
Va Validation Accuracy
10a
10*
10'
107
10*
105
Tnoch
Enoch
Figure 16: Accuracy, data fit and complexity on zero-one slope classification task with a linear model and no weight penalty. Note that the shaded region corresponds to the standard error five training runs.
31

---

Published in Transactions on Machine Learning Research (03/2024)
L Further Analysis of GP Classification
To determinc the necessity of a complexity regularisation term for grokking in GP classification, removed it from the training of models under learning scenarios 2 and 3 (Section 2.1.2) As can be seen in Figures Note that for both figures, only every 5th point is plotted.
and 18
Pain Log Probate
Va idlt Log Probaci
-22
0.8
Oitect ve Vilue
Acoracy
0.6
-35-
Tain Wildirn
107
10
10
12
10
307
10a
101
10'
10'
10a
Spach
Esoch
Figure 17: Accuracy and log likelihoods RBF GP on the 0-1 prediction task without added complexity term. Note that the shaded region corresponds the standard error of five training runs. Acc. is Accuracy and Val. is Validation
Tain Log Probatiities Vas talde Log Pro
-23
0.
-22
0.7
-25
-3.6
Tain
309
101
102
104
10
Spoch
Esoch
Figure 18: Accuracy and log likelihoods of RBF GP on the hidden parity prediction task without added complexity term. Note that the shaded region corresponds the standard error of five training runs. Acc. is Accuracy and Val. is Validation.
32

---

Published in Transactions on Machine Learning Research (03/2024)
M Further Analysis of Concealment Data Augmentation
We also considered how the magnitude of initial weights influenced the conccalment data augmentation strat- egy. Under our theory, smaller initial weight magnitudes should decrease the propensity for grokking since models start in a region of lower complexity. We would predict this trend should, however, be counterbal- anced by introducing additional spurious dimensions in the input space. Thus, all models should exhibit an increase in grokking with additional spurious dimensions but those models with smaller magnitudes should exhibit smaller increase. Indeed, this is what we in Figure [9 where we plot the relalive grokking gop since models with smaller initial weights took longer to fit the training data. Note that the definition of relative grokking gap A₂ is:
A E
(27)
where Ej is the epoch at which the model reached high training performance.
Initialisation:
Initiallsation: 1e-06
Initiallsation: 0.0001
Initiallsation:
Initialisation: 1
-1
Log of Relative Gap
-2
44
20.0
22.5
25.0
27.5
30.0
35.0
37.5
40.0
Additional Length
Figure Relationship between relative grokking gap and number of additional dimensions using the grokking via concealment strategy. Datasets used were the same as in Figure
33

---

Published in Transactions on Machine Learning Research (03/2024)
N Loss plots from grokking with concealment
In Figure 20 we show a collection of loss plots from our experiments inducing grokking via conccalment. Each of the datasets can again be found in Appendix E The number of spurious dimensions used for these particular plots is k = 30. The model is trained on each task for 500 epochs.
105
6117
Taaingg
Loss
Taining
Lans
(a) Modulo Multiplication Task
(b) Polynomial Task Two
(c) Modulo Addition Task
1+12
Tain loss Wideion loss
Training Validation Locs
Taining Loss wilseino 1o6s
10
10
10
10
10
16
(d) Modulo Division Task
(e) Modulo Subtraction Task
(I) Polynomial Task
Figure 20: Loss plots from all experiments when inducing grokking via concealment with 30 spurious dimen- sions.
34

---

Published in Transactions on Machine Learning Research (03/2024)
O On the complexity term in approximate inference for GP models
As shown in the main text, the exact log marginal likelihood (LML) for GP regression has interpretable terms follows:
(()) log p(ylx,0)
2 K3 ",,""
log [Ka]
log 2
(28)
2
data fit
complexity
normalisation
where Ko - K + Unfortunately, the exact LML is analytically intractable for many other GP models of interest such as GP classification. In the following, we will write down the approximate LML provided by variational inference or the Laplace's approximation. We will then look at their special case GP regression, to identify which terms correspond to the data fit term and the complexity term in the GP regression's LML.
0.1 Laplace approximation
Taplace's method approximates the posterior by a Gaussian density where mean is the mode of the posterior and its covariance is the inverse of the negative Hessian evaluated the mode. The corresponding approximate LML is
Fiaplacce (0)
pT K 1f + log p(v
log [B]
(29)
2
data fit
complexity
where f is the posterior mode, B = I, W and W -ogoog(v/ For GP classification with logistie likelihood function, the second derivative of the likelihood function wrt the function value does not depend on the target. That is, B does not depend
For this reason, can view 2 log [B] as a model complexity measure. To double check, when the likelihood is Gaussian as in GP regression, N log of which is identical to the GPR's B = zh (Kr + In) and hence 1 log [B] = 2 log Kr + I.I 2
2
complexity term up to constant when the noise is fixed.
Laplace marginal libelhhodd
Laplace datafit
Laplace complexity
0.6
09
0.0
0.0
6.7
100 Begghoo
0.4
langthsakk
0.6
-2-
6.3
0.4
0.4
0.2
03
putputtscale
Figure 21: The approximate log marginal likelihood, data-fit and complexity provided by the Laplace's approximation. The black curves are the trajectories of the hyperparameters with different initialisations when using variational inference.
0.2 Variational inference and the lower bound on the LML
Gaussian variational inference widely used perform approximate inference in GP models with non- Gaussian likelihoods such as GP classification. In this setting, the variational lower bound on the LML can be optimised to select the variational approximation and point estimate for the model hyperparameters.
35

---

Published in Transactions on Machine Learning Research (03/2024)
Assuming p(f) (f and q(f) (f E), the variational bound can be written as follows,
| ((f
0v = - +
(30)
KL term
expected log likelibood
1 = - K μ trace(KF 'Σ)
log Krl
log
N -
2 + ((g) (31)
$
prior entropy+const
Using the KL term as complexity measure in this case has two connected issues:
Unlike exact GP regression or Bayesian neural networks with a fixed prior, both the variational approximation and the hyperparameters challenging to state which terms in the KL correspond to the complexity of the current fit, and which corresponds to the complexity governed by the prior model. In fact, for the GP regression case and g(f) is set to the exact posterior, the KL term has data-fit component and thus does not naturally fall back to the complexity term in the GPR's exact LML.
being optimised in variational inference. It is thus
One could pick the variational posterior to be the prior (which is of course poor fit), leading to zero KL term. However, this does not mean the complexity is zero!
Due to these potential issues, we did not see clear relationship between the KL term and grokking in GP classification, as shown in the main text and Sections H.2 and H.3 We can work around these issues by looking just the entropy of the prior (which resembles the complexity term in the GPR LML) or using the complexity term provided by Laplace's s method using the current hyperparameter estimates. Figure shows the objective function, the learning curves and predictions made during training, for various hyperparameter initialisations. The in Figure 21
and trajectories are shown logether with the Laplace approximate LML in
36

---

Published in Transactions on Machine Learning Research (03/2024)
1.0
1.0
1.0
0.5
0.5
0.5
iteration 2999
Figure 22: The objective function [first column], the learning curves [second columni and predictions made during training [final three columns]] for three hyperparameter initialisations (each row corrosponds to an initialisation] A: short longthscale and high kemel variance. B: short lengthscale and small kernel variance. C: intermediale annglsccale and kernel variance.
0.0
0.0
0.0
-0.5
-0.5
-0.5
-1.0
-1.0
-10
2.0
1.5
0.5
0.0
-0.5
-1.0
2.0
155
1.0
0.5
-0.
-1.0
2.0
155
1.0
0.5-
0.0
-05
1.0
1.0
10
WEAO wwim
0.3
0.5
0.5
iteration 100
0.0
0.0
0.0
-0.5
-0.5
-0.5
-1.0
-1.0
-1.
2.0
1.5
0.5
0.0
-0.
-1.0
2.0
1.5
1.0
0.5
0.0
-1.0
2.0
1.5
1.0
0.5
0.0
-05
1.0
1.0
1.0
0.5
0.5
0.5
iteration
0.0
0.0
0.0
ply 10.00.00
-0.5
-0.5
-0.5
-10
-1.0
-10
1.5
0.5
0.0
-0.
-10
1.5
0.5
-0.
2.0
1.5
0.5
-0.
68
-0.
0.2
003
-07
-0.4
-02
0.3
-05
-0.7
10a
30F
20a
learning curve
10P
I0r
10a
Itaration
10
10
10a
10a
10
10P
0.9
07
0.5
0.4
0.6
0.5
0.4
10a
10
10>
obyec ectivee
100
104
10a
Iteration
espreted ogl
pnbrr emioy
prior enmoy
prlor prlorentiu entooy
expected
10a
10!
tem
201
10P
100
100
0.5
10
0.5
0.5
-15
37


Reviews:
[{"review_id": "mdf1UtVj7R", "reviewer": "Reviewer_fYSj", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper presents new empirical evidence for the phenomenon of grokking and extends the understanding of this phenomenon to non-neural architectures. These results can be a complement to previous results focusing on neural network models. It introduces a new data augmentation technique that binds grokking, which could be a significant contribution to the field.\n\nHowever, this paper lacks theoretical understanding and explanations of the grokking phenomenon. Introducing experiments in GP and BNNs currently does not help us fully understand the emergence of grokking in the training process. The authors claim they have an effective theory of grokking but there is only empirical observation and no mathematical theory proved in the paper, especially in Section 3.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the phenomenon of \"grokking\", which is first observed in neural network training, where the neural network achieves perfect or near-perfect accuracy on validation data after reaching similar performance on training data. In this paper, the authors empirically present the grokking phenomenon in other models like Gaussian process (GP) classification and regression, linear regression, and BNNs. The authors also propose that grokking can be influenced by adding dimensions containing spurious information to datasets and suggest it's not specific to certain types of optimization like stochastic gradient descent (SGD) or weight norm regularization. Following these observations, the authors introduce the complexity theory of grokking and claim that the phenomenon of grokking should be model agnostic.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. There are some other papers theoretically analyzing the grokking phenomenon, e.g., [1-3]. Some references should be updated and you need to have some discussions related to these references.\n2. [2] has already theoretically studied the grokking phenomenon in linear networks which could be related to your linear regression result.\n3. When you use Dataset 1-10 in the main text, you should mention that the detail is referred to Appendix C.\n4. What is $w^i$ in (8)? You need more explanation.\n5. The structure of Section 1 appears somewhat disorganized and could benefit from clearer organization to enhance the readability and flow of the information presented. You may need to summarize the main contribution of this paper for clarity in this section as well.\n\n[1] Grokking as the Transition from Lazy to Rich Training Dynamics\n\n[2] Grokking in Linear Estimators--A Solvable Model that Groks without Understanding\n\n[3] Dichotomy of Early and Late Phase Implicit Biases Can Provably Induce Grokking", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "QTqfCj7A2F", "reviewer": "Reviewer_Dkpr", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The basic premise of the paper is sound, and the experiments are simple and focused. Demonstrating grokking in a variety of non-NN models is a valuable contribution to the literature, as it narrows down the set of necessary conditions for grokking to occur. The linking of grokking to the model capacity is also an interesting hypothesis and the experiments provide interesting evidence for this explanation for grokking.\n\nThere are two big weaknesses with the work as stands:\n* In the examples where grokking occurs AND the capacity decreases at late times, much of the improvement in generalization seems to occur before the capacity drops significantly. This seems contrary to the hypothesis that the capacity decrease drives the improvement in generalization.\n* It would be helpful to have more details/analysis of the learning dynamics in Sections 2.1 and 2.2. Do experimental results like those from section 2.3 also apply to 2.1 and 2.2? In particular I believe the linear regression example could do with more detailed experiments to try to show the origin of the grokking - it is a nice example due to the simplicity of the objective, and I think if findings like those in 2.3 apply to the linear regression case it would strengthen the arguments in the paper significantly.\n\nThere are also some issues with the presentation which I have flagged in \"requested changes\".\n\nEdit: claims and evidence flipped to \"yes\" after additional experiments by the authors.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors investigate the grokking phenomenology, where networks achieve low test loss quickly with poor generalization, but continued training eventually improves generalization. They posit that the key phenomenology behind grokking is the tension between model fit and model capacity (or really, model family capacity, in some information theoretic sense). They also hypothesize that grokking is not limited to neural networks and is a more general phenomenology in machine learning.\n\nIn support of their hypothesis, the authors conduct a number of experiments. First, they construct an example of linear regression with weight norm where grokking occurs. Then they construct two GP learning scenarios where grokking occurs. They also showed that for algorithmic datasets adding spurious features (\"concealment\") induces grokking more easily. Finally, they use a GP example and a BNN example and study learning trajectories. The experiments provide evidence that grokking occurs when trajectories start at a place where the capacity/regularizer value is large, which leads to initial dynamics of training accuracy increasing, followed by a later time decrease in the capacity which leads to generalization.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The main change I would like to see is further analysis of the learning dynamics of the examples in 2.1 and 2.2. I am curious whether or not these examples follow the hypotheses laid out in the rest of the paper. I think doing this analysis for the linear regression example in particular is crucial here. I am currently marking \"no\" in claims and evidence but am very open to changing this rating with further evidence.\n\nSome more specific questions:\n\nWhy is the training accuracy curve in Figure 1 so discontinuous? Why, in contrast, is the test accuracy curve so smooth?\n\nI'm not sure I understand the GP training results. My understanding is that the learning dynamics correspond to learning the parameters of the kernel, and at each step the GP inference is run with the new kernel. Is this correct? If so, why isn't the training accuracy of the GP kernel always 100%? So long as the kernel matrix is invertible the training set should be fit perfectly? Why isn't accuracy 100% at all times then?\n\nFigure 6 is hard to parse. I can't really tell the transparency levels apart. Shouldn't there be a grokking region rather than a grokking point? Also, in the right hand side figure, it seems like the complexity drops well after learning. How does this support the hypothesis?\n\nWhat do the loss plots look like in the various experiments? I am not as familiar with the grokking framework so I'm not sure how to think of the loss (training and validation) as compared to the accuracy. I believe adding this information could help readers like me who are not as familiar with the previous literature.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Y1Zl9oLHo6", "reviewer": "Reviewer_eZfL", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe problem is interesting and can be connected with the learning theory of generalization. This paper also provides strong empirical results on synthetic data that can support the findings. \n\nWeakness:\n\n1. I doubt the importance of studying the Gaussian Process approach, which is simpler than neural networks. This paper appears to be a simple extension from neural networks to Gaussian processes, and I did not observe significant improvements that would warrant bringing it to the committee's attention. Utilizing observations from Gaussian processes to explain neural networks would be more interesting.\n\n2. This paper lacks theoretical analysis. \n\n3. The connection with the model complexity is not clearly presented.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies a phenomenon known as *grokking*, where they achieve perfect or near-perfect accuracy on the validation set long after the same performance has been achieved on the training set.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Could the authors explain the high-level idea behind why Grokking occurs in both neural networks and Gaussian processes? What common property leads to the phenomenon of Grokking?\n\n2. How does this paper provide novel insights and practical contributions to the process of model training in real-world applications?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: See above
Decision: Accept (poster)