PaperlayerView exact revision on arXiv

Source-linked AI summary

The Complexity Dynamics of Grokking

Branton DeMoss, Silvia Sapora, Jakob Foerster, Nick Hawes, Ingmar Posner

arXiv:2412.09810v2cs.LG

TL;DR

The paper asks how complexity relates to generalization, using grokking’s delayed shift from memorization to generalization as a setting to study that relationship. It measures network complexity through principled lossy compression and finds a rise-then-fall complexity transition in regularized networks that generalize, unlike unregularized networks that remain in high-complexity memorization.

  • Problem

    Grokking’s delayed transition from memorization to generalization offers a setting to investigate how complexity relates to generalization.

    Source: §1 · p. 1

  • Method

    The paper measures network complexity using lossy compression formalized through algorithmic rate-distortion theory and Kolmogorov complexity.

    Source: §1 · pp. 1, 3

  • Results

    Regularized networks that generalize show complexity rising during memorization and falling as they discover a simpler pattern, while unregularized networks remain in high-complexity memorization.

    Source: §1 · pp. 1, 4

  • Takeaways & Limitations

    The authors argue that complexity phase transitions are a central mechanism driving grokking and link complexity to generalization through formal statistical bounds.

    Source: §6 · p. 12

Abstract

from arXiv · show

We demonstrate the existence of a complexity phase transition in neural networks by studying the grokking phenomenon, where networks suddenly transition from memorization to generalization long after overfitting their training data. To characterize this phase transition, we introduce a theoretical framework for measuring complexity based on rate-distortion theory and Kolmogorov complexity, which can be understood as principled lossy compression for networks. We find that properly regularized networks exhibit a sharp phase transition: complexity rises during memorization, then falls as the network discovers a simpler underlying pattern that generalizes. In contrast, unregularized networks remain trapped in a high-complexity memorization phase. We establish an explicit connection between our complexity measure and generalization bounds, providing a theoretical foundation for the link between lossy compression and generalization. Our framework achieves compression ratios 30-40x better than na\"ive approaches, enabling precise tracking of complexity dynamics. Finally, we introduce a regularization method based on spectral entropy that encourages networks toward low-complexity representations by penalizing their intrinsic dimension.

1. Introduction

Grokking—the delayed transition from memorization to generalization—provides a setting for studying how complexity relates to generalization. The paper develops a lossy-compression framework for tracking network complexity and reports a rise-then-fall complexity transition in regularized networks that generalize.

1. Introduction

  • The framework measures intrinsic network complexity through lossy compression, formalizing coarse-graining with algorithmic rate-distortion theory and bounding complexity.It draws on Kolmogorov complexity, for which compressed file size provides an upper bound on complexity.Source: §1 · pp. 1, 3
  • Regularized networks that generalize show complexity rising during memorization and falling as they discover a simpler pattern; unregularized networks remain in high-complexity memorization.The reported transition distinguishes generalizing from memorizing solutions.Source: §1 · pp. 1, 4, Figure 1 · p. 2
  • The paper connects complexity to generalization bounds through the Minimum Description Length principle, which minimizes model complexity plus data entropy given the model.The text explains that simply memorizing data does not reduce total description length or achieve compression.Source: §1 · p. 2
  • The compression procedure achieves ratios 30–40× better than naïve approaches, tightening complexity estimates enough to track dynamics during training.The approach coarse-grains models while preserving functional behavior.Source: §1 · p. 3
  • A spectral-entropy regularizer encourages low-complexity representations by penalizing a differentiable measure of effective dimension.The method is introduced as a way to encourage networks toward low-complexity solutions.Source: §1 · p. 4

2. Related Work

Prior work characterizes grokking through learning regimes, parameter norms, efficiency, and task-specific progress measures; this paper proposes complexity as a general dynamical metric. Related work also connects complexity to generalization bounds and studies coarse-graining as a way to track complexity.

Grokking

  • Prior accounts characterize grokking conditions and learning regimes, extend it to non-algorithmic datasets, and examine parameter norms and network efficiency.Liu et al. (2022a) categorize four regimes; Liu et al. (2022b) and Varma et al. (2023) connect grokking to parameter norms and efficiency.Source: §2 · p. 4
  • Task-specific progress measures detect grokking, but a general notion of criticality for predicting the transition remains lacking.This work proposes complexity as a dynamical metric for understanding grokking and argues that proxy measures such as the L2 norm are insufficient.Source: §2 · pp. 4–5

Generalization

  • Scaling laws report improving performance with model scale, while classical bias-variance reasoning predicts larger models can worsen after a threshold; that contrast assumes capacity equals complexity.The section notes that the equality assumption does not generally appear to hold.Source: §2 · p. 5
  • Prior work uses Kolmogorov complexity for generalization bounds, while this paper focuses on complexity dynamics during grokking and formalizes coarse-graining through rate-distortion theory.Lotfi et al. (2024) derive bounds for large language models; Goldblum et al. (2023) apply the Solomonoff prior to a finite-hypothesis bound. Aaronson et al. (2014) study coarse-grained apparent complexity in a cellular automaton.Source: §2 · p. 5

3. Complexity and Generalization

This section relates model complexity to generalization bounds and the MDL principle, then develops lossy compression as a way to estimate complexity while balancing model description length against training performance.

3. Complexity and Generalization

  • Generalization bounds depend on Kolmogorov complexity and empirical risk, so tighter model compression can improve the complexity bound only if empirical risk does not rise.Jointly minimizing complexity and empirical risk corresponds to MDL when empirical risk is understood as training-data entropy under the model.Source: §3 · p. 5
  • Naïve parameter compression gives poor complexity bounds because weights retain random information from initialization and stochastic training, and randomness is undecidable in general.The section notes there is no generic method for removing random information.Source: §3 · p. 5

3.1. Lossy Compression

  • Figure 4 plots algorithmic rate-distortion curves across datasets and distortion bounds, with rate measured as end-of-training coarse-grained-weight complexity.The curves are means over six seeds.Source: Figure 4 · p. 6, §3.1 · p. 8
  • As allowed distortion increases, estimated complexity decreases, while the rise-and-fall complexity pattern remains robust across distortion bounds.Models are regularized to limit complexity and yield highly compressible representations.Source: Figure 5 · p. 7, §3.1 · p. 8
  • Algorithmic rate-distortion estimates complexity by finding a low-bit coarse-grained parameter vector whose loss-induced distortion from the original model stays within a bound.The rate is the minimum bits needed to specify an approximation within the allowed distortion; coarse-graining is treated as lossy compression of model parameters.Source: §3.1 · pp. 6–7, §3 · p. 6
  • Cross-entropy loss supplies the distortion criterion, and MDL selects the bound that balances model complexity against training performance.A lossy model can be a better compressor of the data under total description length; the framework approximates rate-distortion with compression upper bounds.Source: §3.1 · pp. 7–8

4. Capacity and Regularization

The section develops complexity controls based on parameter capacity, quantization, and spectral entropy. Low-rank representations support both complexity regularization and tighter compression estimates, while the resulting generalization bounds remain vacuous in these experiments.

4. Capacity and Regularization

  • Weight decay and reduced precision control parameter information capacity through range and precision, but regularization alone may leave high-frequency detail and fail to reduce complexity.The section motivates a scheme that also addresses information distributed across parameter matrices.Source: §4 · p. 8

4.1. Quantization and Noise

  • Noisy weights impose an effective lower bound on parameter precision, after which parameters can be rounded to quantization bins at least that wide.Independent Gaussian noise is added to each parameter at each forward pass; gradients from noisy weights are applied to the original parameters.Source: §4.1 · pp. 8–9

4.2. Spectral Entropy

  • Low-rank approximation addresses information beyond high-frequency noise and serves both as a regularizer and as a coarse-graining step for tighter complexity estimates.The compression procedure searches for layerwise low-rank descriptions and quantizes them when they satisfy the distortion bound.Source: §4.2 · pp. 9–11
  • The low-rank procedure adapts rank by layer because layers can admit different decompositions, while a shared threshold controls approximation quality.The coarse-graining procedure uses a global quantization interval for simplicity, though separate intervals could yield greater compression.Source: §4.2 · p. 9, §4.1 · p. 9
  • No model achieves a non-vacuous expected-risk bound, although the proposed regularization method gives the best bounds in all cases.The passage attributes the vacuous bounds to over-parameterized models and a small dataset.Source: Figure 6 · p. 10
  • Spectral entropy measures the spread of normalized singular values, yields an effective rank, and can be penalized to encourage low-rank representations.The experiments report that this regularizer causes grokking and produces the lowest-rank, most-compressible networks among the methods studied.Source: §4.2 · p. 10

5. Experiments

In modular-arithmetic grokking experiments, regularized models show a complexity phase transition: complexity peaks during memorization and falls during generalization, unlike unregularized models that remain in high-complexity memorization. The regularizer also yields the closest approach to a non-trivial generalization bound, though the bounds remain vacuous.

5. Experiments

  • The proposed regularizer causes grokking and yields lower-complexity networks than weight decay alone, as measured by the paper’s complexity metric.The experiments use binary operations modulo a prime, p = 113, with single-layer transformers for addition and multiplication and two-layer transformers for subtraction and division.Source: §5 · p. 11
  • Regularized models show a clear complexity phase transition, with complexity maximized during memorization and falling during generalization; unregularized models remain in high-complexity memorization.Grokking occurs in all regularized models and not in unregularized models; loosening the distortion bound also lowers measured complexity for the same model.Source: §5 · pp. 11–12
  • Models trained with the proposed regularizer come closest to a non-trivial generalization bound by achieving the least sum of data entropy and model complexity.The reported bounds remain vacuous because the models are vastly over-parameterized and the dataset is small.Source: §5 · p. 12

6. Conclusion

The conclusion frames grokking as a transition between learning phases characterized by the complexity of internal representations. It links complexity to formal generalization bounds and presents broader explanations of grokking and complex-system behavior as directions or conjectures.

6. Conclusion

  • The paper proposes that a complexity phase transition is the central mechanism driving grokking, while weight norms or linear structure alone are insufficient explanations.The conclusion connects complexity to formal statistical generalization bounds and identifies effective rank as one way complexity can arise.Source: §6 · p. 12
  • Grokking’s separation between memorizing and generalizing phases makes it a model system for studying complexity phase transitions, while a unified theory should predict when such dynamics occur.The conclusion identifies generalization to arbitrary learning systems as a possible route to understanding interactions among optimization, data, capacity, and complexity.Source: §6 · p. 12
  • The reported rise and fall of complexity is conjectured to be generic to certain complex dynamical systems, with broader explanatory implications left for future understanding.The conclusion presents algorithmic thermodynamics as a promising framework for analyzing such systems.Source: §6 · p. 12

Funding

The work acknowledges its funding sources and support.

Funding

  • The work was supported by the EPSRC Programme Grant “From Sensing to Collaboration”; Branton DeMoss received an AWS Lighthouse Scholarship.Source: Funding · p. 13

Appendix A. Appendix

The appendix describes quantization-based complexity estimation and compares it with other diagnostics of complexity and generalization during training.

Appendix A. Appendix

  • Algorithm 2 searches increasing bin sizes and returns the minimum complexity from compressing the original or quantized parameters.Source: Appendix A · p. 14
  • Quantization coarse-graining misses the rise-and-fall dynamics in weight-decayed subtraction and addition models, with bounds about two times worse than the spectral method.Source: Figure A.7 · p. 15
  • Effective rank falls when regularized models generalize, while unregularized models remain near full rank; the proposed regularizer yields the lowest rank and most compressible model studied.Source: Figure A.8 · p. 16
  • Naïve bzip2 estimates vary little through training; their slight dips around 10^3 steps coincide with generalization, while coarse-graining is required to reveal the dynamics.Source: Figure A.9 · p. 17
  • Grokking occurs in all regularized models and not in unregularized models, according to accuracy averaged over six seeds.Source: Figure A.10 · p. 18
  • Regularized models have smaller total description length than baselines, while the unregularized model collapses during memorization on subtraction and division.Source: Figure A.11 · p. 19

Related papers

Cited by

Loading 2412.09810v2…