- Rating
- 3(+2)
- Confidence
- 2
- Informativeness
- 2(+1)
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies grokking from a task-level, solution-set perspective. Instead of analyzing the training dynamics or a particular solution reached by optimization, the paper considers the entire set of minimum-norm interpolating solutions induced by partially observed pairwise tasks. The authors represent such tasks as edge colorings of a complete bipartite graph and focus on Latin-square tasks, defining an instance as all-good, mixed, or no-good depending on the held-out performance across its minimum-norm endpoint set.
The main theoretical results characterize two contrasting regimes. The authors prove that finite abelian group families, including modular addition, are asymptotically all-good, while uniformly random Latin squares are asymptotically unlikely to be all-good. They further develop a carrier-based sufficient criterion for all-goodness and conjecture a corresponding necessity result. 9616_Mapping_the_Solution_Set_ Empirically, they show that relabelings of modular addition continue to grok despite having dense polynomial representations, and that on composite-order tasks, coarse output factors can be recovered before exact labels.
Critical strengths
The theoretical development appears technically substantial and carefully constructed. In particular, the distinction between individual trained solutions and the entire minimum-norm solution set is conceptually clean, and the all-good/mixed/no-good formulation provides a precise way of asking when generalization is guaranteed independently of which minimum-norm solution is selected. The contrast between structured abelian-group tasks and uniformly random Latin squares is mathematically sharp.
I also find the relabeling result interesting. It demonstrates that polynomial degree or sparsity can change dramatically under a representation change while the underlying generalization behavior is preserved: relabeled modular addition has roughly 97% polynomial support yet still generalizes, whereas random-matching Latin controls with similar polynomial statistics do not. This provides a useful caution against identifying superficial algebraic complexity with the structure responsible for grokking.
Critical weaknesses
My main concern is the motivation and broader significance of the problem formulation. The paper motivates studying the entire minimum-norm endpoint set by observing that a successful training run only establishes the existence of one generalizing solution, whereas an “all-good” task guarantees that every minimum-norm solution generalizes. While mathematically natural, I am not yet convinced why this stronger property is important for understanding grokking, or neural-network generalization more broadly.
In particular, there seems to be a substantial gap between the mathematical object being characterized and actual training dynamics. The minimum-norm endpoint is motivated as an idealized late-training object via implicit-bias results, but the paper studies global minimum-norm interpolators, whereas practical optimization selects particular solutions through a finite-time trajectory. Indeed, the paper itself notes that its finite-training experiments “do not certify membership in or measure its phase.” This raises the question of what observable consequence the distinction between all-good, mixed, and no-good tasks has for actual neural-network training.
Relatedly, the current results are centered on a rather specialized setting: Latin-square pairwise tasks, a particular one-hidden-layer ReLU architecture, uniform random observation masks, and an asymptotic minimum-norm formulation. The theoretical results may be strong within this setting, but the paper currently provides limited evidence that the proposed classification predicts anything of practical relevance outside it. For example, does being all-good imply robustness across optimizers, initialization, regularization strength, architecture, or training seeds? Does the carrier criterion predict generalization or grokking behavior on tasks beyond algebraic/Latin-square settings? Without such a connection, I currently view the work more as an elegant characterization of a mathematical model inspired by grokking than as an explanation of grokking itself.
There is also a conceptual mismatch with the defining feature of grokking: delayed generalization. The paper intentionally isolates endpoint quality from transition time. That is a legitimate choice, but it makes the connection to grokking weaker than the framing suggests. A theory that determines whether an idealized endpoint generalizes does not by itself explain why generalization is delayed, why the transition is abrupt, or when the transition occurs. The paper should therefore clarify whether its intended contribution is a theory of grokking, or a theory of minimum-norm generalization motivated by grokking.
Questions for authors
Questions for Authors
-
Why is “all minimum-norm solutions generalize” the right property to study? What concrete phenomenon in actual neural-network training would differ between an all-good task and a mixed task? For example, should mixed tasks exhibit stronger seed dependence or optimizer dependence?
-
Can the authors empirically connect the endpoint-set classification to finite training? A particularly convincing experiment would be to identify tasks predicted to be all-good versus mixed/no-good and test whether this classification predicts the distribution of outcomes across many initialization/optimization seeds.
-
How essential is the minimum-norm assumption? Actual grokking experiments use finite learning rates, finite weight decay, and terminate at finite time. To what extent should the global minimum-norm endpoint set approximate the solutions selected in these settings?
-
What is the intended implication for grokking specifically? Since the theory largely removes the temporal aspect and studies endpoint generalization, which part of the delayed memorization-to-generalization transition does the theory help us understand?
-
What would be the analogue of the carrier criterion in a more realistic task? Is there a plausible extension to sequence modeling, language modeling, or other settings where grokking has been observed? The paper cites grokking in deep networks, reasoning, and LLM pretraining, but the present results do not yet establish a clear connection to those settings.
4 comments
Response II
Q3. How essential is exact global minimum norm at finite training time?
The proof’s operative requirement is a cost bound at unit training margin. Global minimizers meet it because the full-task carrier is feasible on every observed subset. The same exclusion argument applies to other feasible networks that meet a sufficient budget.
More explicitly, fix a deterministic reduced-cost budget (K_q). For every unit-margin feasible (F) with (J(F)\le K_q), the carrier subtraction in Proposition E.2 has cost at most [ B_q=\sqrt{2}\bigl(\Gamma_q K_q+J_{\mathrm{car},q}\bigr). ] Whenever (B_q^2\log q/q^{5/2}\to0), the notch excludes bad candidates uniformly within this budget (Lemma 4.3, p. 8; Appendix E.3.1, pp. 31–32). Exact optimality is one route into this regime, and sufficiently low-cost approximate minimizers are also covered.
For finite learning rates, weight decay, and training horizons, the remaining optimization question is whether the trajectory reaches such a region after matching its training margin. We do not assume that arbitrary finite-time iterates globally solve the constrained problem, and the asymptotic proof does not calibrate a universal finite-(q) cost cutoff. This is why the new experiments compare costs at a common training margin rather than interpreting raw norm decrease alone as evidence of approaching the theoretical endpoint set.
Q4. Which part of grokking does the theory explain?
The contribution addresses the generalizing solution structure underlying the transition: which tasks make low-cost fitting solutions generalize, and which apparent descriptions of those tasks are intrinsic? The rewritten Related Work (Section 2, pp. 3–4) makes three connections explicit.
First, Nanda et al. identify a Fourier mechanism in arithmetic coordinates. From a task-classification perspective, exhibiting that mechanism gives a sufficient explanation for the studied predictor, but does not establish necessity of its particular coordinate expression. Our norm-preserving relabelling theorem transports the entire endpoint set. Relabelled addition at (q=97) can have 9,118 nonzero polynomial coefficients and degree 190 while trained networks still grok. Thus, as you also acknowledge, sparsity in a decomposition tied to the observed coordinates cannot by itself provide an intrinsic explanation of grokking (Section 3.4, pp. 5–6; Figure 2; Appendix D.3, pp. 26–27).
Second, analyses of training dynamics explain how a predictor develops. Our carrier-plus-notch argument explains why, for the covered task families, entering a sufficiently low-cost feasible regime excludes poorly generalizing completions simultaneously. This provides a structural account of the generalizing side of the memorization-to-generalization transition without assigning a time to reaching it.
Third, existing provable results use specific assumptions: Xu et al. prove quantitative delayed generalization for linear ridge regression, while Mohamadi et al. study bounded-(\ell_\infty) quadratic networks on modular addition. Our contribution supplies a structural sufficient criterion across deterministic colouring families within the stated ReLU model. It complements these dynamics results through different quantifiers over tasks and solutions. The intended scope is explicit in the original formulation and in Appendix E.2 (pp. 30–31).
Neel Nanda, Lawrence Chan, Tom Lieberum, Jess Smith, and Jacob Steinhardt. Progress Measures for Grokking via Mechanistic Interpretability. ICLR, 2023.
Mingyue Xu, Gal Vardi, and Itay Safran. To Grok Grokking: Provable Grokking in Ridge Regression. ICML, PMLR 306:141965–141987, 2026.
Mohamad Amin Mohamadi, Zhiyuan Li, Lei Wu, and Danica J. Sutherland. Why Do You Grok? A Theoretical Analysis on Grokking Modular Addition. ICML, PMLR 235:35934–35967, 2024.
Response III
Q5. Generality and significance of the carrier criterion.
The carrier framework provides a structural sufficient criterion for an architecture–task pair. If the task admits a full-task carrier within the architecture with the required norm and margin bounds, and the architecture satisfies the corresponding uniform complexity bound, then asymptotic all-goodness follows under uniform partial observation. Thus, satisfying the criterion guarantees the generalising endpoint structure underlying grokking: the worst held-out accuracy across the entire minimum-norm completion set converges to one in probability.
Our proof has two substantive parts. First, sufficiency: a suitable carrier bounds the cost of every minimum-norm completion, and uniform exclusion rules out poorly generalising completions within that budget (Proposition E.2, Appendix E.3.1, pp. 31–32). Second, verification for the architecture and tasks studied here: we establish the norm reduction and uniform notch bound for single-hidden-layer ReLU networks, and construct carriers satisfying the required bounds for addition and, more generally, every growing finite abelian group family (Lemma 3.2, pp. 4–5; Lemmas 4.2–4.3 and Corollary 4.4, pp. 7–8; Appendix E.3.2, pp. 32–33).
The criterion is also coordinate-independent under task relabellings: input and output permutations preserve the carrier’s width, norm, and margins, as well as the corresponding endpoint set (Theorem 3.5, p. 5). Its substantive contribution is therefore a structural implication from one economical full-task representation to generalisation by every minimum-norm completion under partial observations. We also conjecture that the carrier criterion may be a necessary structural requirement for all-good tasks.
I'd love to thank the authors for their detailed feedback, which addressed most of my concerns. Therefore, I'm raising my score.
Response I
Thank you for the questions. We first address the concern about the connection to actual training, and then respond point by point. Unless stated otherwise, locations refer to the revised manuscript.
On the gap to actual training and the scope of the contribution.
Our stated object is the solution-set structure of grokking tasks. This scope appears in the title, Mapping the Solution-Set Structure of Grokking on Latin Squares, and in the original Introduction’s central question: “which task structures make the entire minimum-norm endpoint set generalise?” (original submission, p. 1). The paper does not claim to derive the delay, abruptness, or transition time of training.
The precise contributions are a norm-preserving relabelling invariance of endpoint sets; asymptotic generalization of every minimum-norm endpoint for every growing finite-abelian-group family at any fixed positive observation fraction; an impossibility result for every observation-based learner under the uniform Latin law, implying that all-goodness is asymptotically rare under the joint task-and-mask law; and a colouring-independent carrier criterion explaining the positive guarantee (Theorem 3.5, p. 5; Theorem 4.1 and Corollary 4.4, pp. 7–8; Proposition E.2, pp. 31–32).
The statement that finite runs “do not certify membership” in the endpoint set distinguishes the scope of numerical evidence from that of a uniform theorem. It does not make the theorem contingent on numerically certifying every minimizer. The connection to training is conditional on attaining the relevant norm/margin regime; importantly, the proof also covers sufficiently low-cost feasible approximate minimizers. We now examine this connection directly through matched-margin trajectories (Q2–Q3), while explaining the contribution to grokking in the rewritten Related Work (Q4).
Q1. Why study all minimum-norm solutions? Does the mixed phase imply seed or optimizer dependence?
All-goodness asks whether the norm preference itself is sufficient to ensure generalization, regardless of which minimum-norm solution is selected. In an all-good instance, choosing a different global minimizer cannot change success into failure at the specified accuracy threshold. In a mixed instance, equally optimal solutions include both outcomes: the training constraints and norm objective alone cannot resolve the generalization question. This distinguishes a task-level guarantee from the existence of one successful circuit or training run.
Mixedness permits seed or optimizer dependence if the training procedure reaches both kinds of endpoint with appreciable probability; it does not force that procedure to sample both. Conversely, all-goodness guarantees robustness to selection within the endpoint set, not that every optimizer, initialization, or regularization strength reaches it. Changing the architecture or sampling law can change the set itself. These quantifiers are explicit in Section 3.3 (pp. 4–5) and Appendix B.1 (pp. 12–13). The vanishing all-good probability under the uniform Latin law further shows that this selection-robust property is restrictive, rather than automatic.
Q2. Can the classification be connected empirically to finite training?
The revision adds 33 training runs that directly measure the quantity motivating the endpoint analysis. At each checkpoint with positive minimum training margin, we rescale the network to unit training margin, preserving predictions, and record its parameter cost (Appendix D.6.1, pp. 28–29; Eq. (99); Figure 4). The masks follow the theoretical uniform fixed-cardinality law.
For q=79 and 33% coverage, all three runs already fit every training cell at 20k updates. Between 20k and 80k, median held-out accuracy rises from 0.33% to 99.57%, while median unit-margin cost falls from 785.37 to 464.59. All 33 runs end with lower normalized cost than at 10k.
There is also a concrete finite-size consequence to investigate: the observed fraction needed for successful completion falls across the tested orders. Appendix D.2 and Table 3 (pp. 25–26) report exact completion in all five seeds at fractions 33%, 25%, 23%, and 20% for q=47,79,113,211. Thus the predicted structural advantage is empirically visible already at orders in the tens.
The orbit experiment additionally contrasts 30 relabelled-addition runs, all showing a transition, with 24 random-matching control runs ending below chance (Section 3.4, pp. 5–6; Appendix D.3, pp. 26–27). These are observed outcomes, not certified mixed/no-good labels. Constructing a family with non-vanishing mixed mass remains open, and random-matching controls are not samples from the uniform Latin law. The proposed three-phase benchmark would require additional phase certification; our experiments test the available structural predictions and the norm/margin connection.