# Benign Overfitting and Grokking in ReLU Networks for XOR Cluster Data

arXiv: https://arxiv.org/abs/2310.02541 · HTML: https://mlsanity.com/paper/2310.02541/

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 31 references that are in the map.
- First posted on arXiv 4 Oct 2023.

## Builds on (most cited first, 28 of 28)

- [Progress measures for grokking via mechanistic interpretability](https://mlsanity.com/paper/2301.05217/) (2023)
- [Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets](https://mlsanity.com/paper/2201.02177/) (2022)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [Deep learning: a statistical viewpoint](https://mlsanity.com/paper/2103.09177/) (2021)
- [Towards Understanding Grokking: An Effective Theory of Representation Learning](https://mlsanity.com/paper/2205.10343/) (2022)
- [Just Interpolate: Kernel "Ridgeless" Regression Can Generalize](https://mlsanity.com/paper/1808.00387/) (2018)
- [Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit](https://mlsanity.com/paper/2207.08799/) (2022)
- [Omnigrok: Grokking Beyond Algorithmic Data](https://mlsanity.com/paper/2210.01117/) (2022)
- [Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation](https://mlsanity.com/paper/2105.14368/) (2021)
- [Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel](https://mlsanity.com/paper/1810.05369/) (2018)
- [Explaining grokking through circuit efficiency](https://mlsanity.com/paper/2309.02390/) (2023)
- [Does data interpolation contradict statistical optimality?](https://mlsanity.com/paper/1806.09471/) (2018)
- [The Slingshot Mechanism: An Empirical Study of Adaptive Optimizers and the Grokking Phenomenon](https://mlsanity.com/paper/2206.04817/) (2022)
- [Benign Overfitting in Two-layer Convolutional Neural Networks](https://mlsanity.com/paper/2202.06526/) (2022)
- [Grokking modular arithmetic](https://mlsanity.com/paper/2301.02679/) (2023)
- [A Tale of Two Circuits: Grokking as Competition of Sparse and Dense Subnetworks](https://mlsanity.com/paper/2303.11873/) (2023)
- [Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime](https://mlsanity.com/paper/2004.12019/) (2020)
- [Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Data](https://mlsanity.com/paper/2202.05928/) (2022)
- [A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning](https://mlsanity.com/paper/2109.02355/) (2021)
- [Unifying Grokking and Double Descent](https://mlsanity.com/paper/2303.06173/) (2023)
- [Implicit Bias in Leaky ReLU Networks Trained on High-Dimensional Data](https://mlsanity.com/paper/2210.07082/) (2022)
- [Benign, Tempered, or Catastrophic: A Taxonomy of Overfitting](https://mlsanity.com/paper/2207.06569/) (2022)
- [Random Feature Amplification: Feature Learning and Generalization in Neural Networks](https://mlsanity.com/paper/2202.07626/) (2022)
- [Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization](https://mlsanity.com/paper/2303.01462/) (2023)
- [Grokking phase transitions in learning local rules with gradient descent](https://mlsanity.com/paper/2210.15435/) (2022)
- [Binary Classification of Gaussian Mixtures: Abundance of Support Vectors, Benign Overfitting and Regularization](https://mlsanity.com/paper/2011.09148/) (2020)
- [From Tempered to Benign Overfitting in ReLU Neural Networks](https://mlsanity.com/paper/2305.15141/) (2023)

## Built on by (most cited first, 30 of 33)

- [Dichotomy of Early and Late Phase Implicit Biases Can Provably Induce Grokking](https://mlsanity.com/paper/2311.18817/) (2023)
- [Deep Networks Always Grok and Here is Why](https://mlsanity.com/paper/2402.15555/) (2024)
- [Why Do You Grok? A Theoretical Analysis of Grokking Modular Addition](https://mlsanity.com/paper/2407.12332/) (2024)
- [Approaching Deep Learning through the Spectral Dynamics of Weights](https://mlsanity.com/paper/2408.11804/) (2024)
- [Grokking Group Multiplication with Cosets](https://mlsanity.com/paper/2312.06581/) (2023)
- [Learned feature representations are biased by complexity, learning order, position, and more](https://mlsanity.com/paper/2405.05847/) (2024)
- [When does compositional structure yield compositional generalization? A kernel theory](https://mlsanity.com/paper/2405.16391/) (2024)
- [Information-Theoretic Progress Measures reveal Grokking is an Emergent Phase Transition](https://mlsanity.com/paper/2408.08944/) (2024)
- [Provable Scaling Laws of Feature Emergence from Learning Dynamics of Grokking](https://mlsanity.com/paper/2509.21519/) (2025)
- [Towards Empirical Interpretation of Internal Circuits and Properties in Grokked Transformers on Modular Polynomials](https://mlsanity.com/paper/2402.16726/) (2024)
- [Let Me Grok for You: Accelerating Grokking via Embedding Transfer from a Weaker Model](https://mlsanity.com/paper/2504.13292/) (2025)
- [A Theoretical Framework for Grokking: Interpolation followed by Riemannian Norm Minimisation](https://mlsanity.com/paper/2505.20172/) (2025)
- [Abrupt Learning in Transformers: A Case Study on Matrix Completion](https://mlsanity.com/paper/2410.22244/) (2024)
- [What Can Grokking Teach Us About Learning Under Nonstationarity?](https://mlsanity.com/paper/2507.20057/) (2025)
- [To Grok Grokking: Provable Grokking in Ridge Regression](https://mlsanity.com/paper/2601.19791/) (2026)
- [Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality](https://mlsanity.com/paper/2409.03891/) (2024)
- [Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methods](https://mlsanity.com/paper/2410.10024/) (2024)
- [What Happens During the Loss Plateau? Understanding Abrupt Learning in Transformers](https://mlsanity.com/paper/2506.13688/) (2025)
- [Benign overfitting in leaky ReLU networks with moderate input dimension](https://mlsanity.com/paper/2403.06903/) (2024)
- [Provable Tempered Overfitting of Minimal Nets and Typical Nets](https://mlsanity.com/paper/2410.19092/) (2024)
- [When Are Bias-Free ReLU Networks Effectively Linear Networks?](https://mlsanity.com/paper/2406.12615/) (2024)
- [On the Role of Label Noise in the Feature Learning Process](https://mlsanity.com/paper/2505.18909/) (2025)
- [Explaining Grokking and Information Bottleneck through Neural Collapse Emergence](https://mlsanity.com/paper/2509.20829/) (2025)
- [How Does Label Noise Gradient Descent Improve Generalization in the Low SNR Regime?](https://mlsanity.com/paper/2510.17526/) (2025)
- [A rationale from frequency perspective for grokking in training neural network](https://mlsanity.com/paper/2405.17479/) (2024)
- [On the Theory of Continual Learning with Gradient Descent for Neural Networks](https://mlsanity.com/paper/2510.05573/) (2025)
- [Understanding the Benefits of SimCLR Pre-Training in Two-Layer Convolutional Neural Networks](https://mlsanity.com/paper/2409.18685/) (2024)
- [A Two-Phase Perspective on Deep Learning Dynamics](https://mlsanity.com/paper/2504.12700/) (2025)
- [Tuning the Implicit Regularizer of Masked Diffusion Language Models: Enhancing Generalization via Insights from k-Parity](https://mlsanity.com/paper/2601.22450/) (2026)
- [Harmful Overfitting in Sobolev Spaces](https://mlsanity.com/paper/2602.00825/) (2026)

## Abstract (arXiv)

Neural networks trained by gradient descent (GD) have exhibited a number of surprising generalization behaviors. First, they can achieve a perfect fit to noisy training data and still generalize near-optimally, showing that overfitting can sometimes be benign. Second, they can undergo a period of classical, harmful overfitting -- achieving a perfect fit to training data with near-random performance on test data -- before transitioning ("grokking") to near-optimal generalization later in training. In this work, we show that both of these phenomena provably occur in two-layer ReLU networks trained by GD on XOR cluster data where a constant fraction of the training labels are flipped. In this setting, we show that after the first step of GD, the network achieves 100% training accuracy, perfectly fitting the noisy labels in the training data, but achieves near-random test accuracy. At a later training step, the network achieves near-optimal test accuracy while still fitting the random labels in the training data, exhibiting a "grokking" phenomenon. This provides the first theoretical result of benign overfitting in neural network classification when the data distribution is not linearly separable. Our proofs rely on analyzing the feature learning process under GD, which reveals that the network implements a non-generalizable linear classifier after one step and gradually learns generalizable features in later steps.