# Structured Features Overfit Where Random Features Grok

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 9 references that are in the map.
- First posted on arXiv 14 Sep 2026.

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

- [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)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Towards Understanding Grokking: An Effective Theory of Representation Learning](https://mlsanity.com/paper/2205.10343/) (2022)
- [Grokking as the Transition from Lazy to Rich Training Dynamics](https://mlsanity.com/paper/2310.06110/) (2023)
- [Why Do You Grok? A Theoretical Analysis of Grokking Modular Addition](https://mlsanity.com/paper/2407.12332/) (2024)
- [Grokking in Linear Estimators -- A Solvable Model that Groks without Understanding](https://mlsanity.com/paper/2310.16441/) (2023)
- [Grokking Modular Polynomials](https://mlsanity.com/paper/2406.03495/) (2024)
- [Algebraic Representability as the Limiting Regime of Grokking: An Exactly Solvable Model with Holomorphic Activations](https://mlsanity.com/paper/2607.13749/) (2026)

## Abstract (arXiv)

Xu, Vardi and Safran (ICML 2026) prove that over-parameterized ridge regression over an unstructured random Gaussian feature map groks, with the delay between memorization and generalization growing as 1/λ in the weight decay. We show that on a structured feature map the same delay does not appear. For a band-limited Fourier feature map over mathbbZp2 carrying a single-character target that lies inside the expressible class, enlarging the band at fixed positive weight decay drives peak held-out accuracy monotonically from 1.00 to 0.07, with no memorize-then-generalize regime anywhere along the sweep. The degradation is not an interpolation effect. It sets in at capacity ratio q/n = 0.638, far below the interpolation threshold, on separate grounds from the exact null space that appears above it. What does have a sharp boundary is the active support. Holding the nominal dimension fixed and masking the band back to 1089 active modes restores held-out accuracy of 1.000 with zero variance across seeds, while the full 4225-mode band collapses to 0.185. The number of active modes acts through the teacher-weighted spectrum of the empirical Gram matrix and not through the capacity ratio, which makes this a statement about feature geometry and not a restatement of double descent.