acceptodds
Under review as a conference paper at ICLR 2027

Mapping the Solution-Set Structure of Grokking on Latin Squares

Abstract

Grokking is a delayed transition from memorisation to generalisation. A network first fits observed examples while remaining near chance on held-out inputs, then generalises abruptly. Prior work has focused mainly on this delay, finding that the network's main loss becomes weight decay after the fitting phase. We name the solution to this optimization problem as the minimum-norm endpoint, and study which tasks make all minimum-norm endpoints generalise from partial observations. Specifically, we model pairwise input tasks as edge colourings of , with Latin colourings as our structured family, and classify each observed instance as all-good, mixed, or no-good by its endpoint set. Furthermore, we prove two contrasting results: (1) Finite-abelian-group families are asymptotically all-good from partial observations; (2) Under a uniform random Latin square, all-good tasks become asymptotically rare for observation-based learners, leaving mixed or no-good behaviour. Moreover, experiments show that relabellings of addition generalise despite their dense polynomial representations. Finally, on tasks of composite order, finite-training results suggest that predictors learn a coarse part of the output before the full label.

Primary area:
learning theory
Keywords:
Grokking, Minimum-norm solutions, Latin squares

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_BfA7OpenReview ↗
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 SqS_q 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

  1. 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?

  2. 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.

  3. 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?

  4. 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?

  5. 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
AuthorsOpenReview ↗

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=79q=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,211q=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.

AuthorsOpenReview ↗

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.

AuthorsOpenReview ↗

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.

Reviewer_AShLOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper studies how task structure affects generalisation by all global minimum-norm networks that fit partially observed input pairs with unit training margins. It represents pairwise classification tasks as coloured bipartite graphs or tables, focuses on Latin squares, and identifies tasks up to relabelling. For a specified shallow ReLU architecture and a fixed positive fraction of uniformly sampled training cells, it proves that the worst minimum-norm endpoint accuracy tends to one along every growing family of finite abelian groups. In contrast, uniformly random Latin squares defeat every learner using only the observations, making all-good behaviour asymptotically rare. The carrier construction provides a sufficient route to the positive guarantee. Experiments investigate relabelled addition and recovery of coarse output factors. These experiments complement the theory but do not certify membership in, or the behaviour of, the full minimum-norm endpoint set.

Critical strengths
  • Strong results connecting generalisation and task structure Overall, I view this as a good theoretical paper. The contrast between abelian-group tables and uniformly random Latin squares is its strongest contribution. The positive result concerns every global minimum-norm solution, while the negative result applies to every observation-based learner. I find the proofs substantial and interesting, and the results valuable independently of their interpretation in terms of grokking.
  1. A useful framework beyond a single arithmetic example The carrier argument allows connecting a cheap representation of the full task to generalisation from partial observations. Relabelling invariance also distinguishes task structure from the complexity of a particular polynomial description. These are useful theoretical insights into the interaction between a norm preference and the structure of the data.
Critical weaknesses
  1. The connection to actual grokking remains conditional The endpoint theorems do not establish that training reaches the global minimum-norm set, or explain delayed and abrupt generalisation. A minimum-norm account is not an established universal explanation of grokking. For example, Kumar et al. (2024, Section 3, arXiv:2310.06110) report grokking without weight decay and with increasing parameter norms. Such examples do not directly contradict a margin-normalised endpoint analysis, but they make the scope of the connection important. The authors should distinguish the proved generalisation results from assumptions about optimisation and from an interpretation of grokking. This concern affects the framing and claimed significance for grokking, rather than the independent value of the mathematical results.
  2. The positioning and presentation could be improved The exposition is mathematically heavy, which makes the meaning and scope of the results harder to extract. I would favour presenting the interaction between norm regularisation and task structure as the primary contribution, with grokking as a motivating application or secondary interpretation. A clearer introduction and discussion should explain the assumptions and consequences in plain language before introducing the full formalism
Questions for authors
  1. Clarification of the optimisation connection. Under which training and regularisation regimes do the authors expect the global unit-margin minimum-norm problem to describe actual training? Which parts of that connection are proved, assumed, or supported empirically, and how should the stated contribution to grokking be qualified when the connection fails?
  2. Evidence and suggested numerical investigation. Is there direct evidence in the existing experiments that grokking trajectories approach the proposed endpoint problem? Additional experiments tracking cost at a matched training margin, comparing feasible solutions across initialisations, and varying the training fraction would strengthen this connection. Comparisons using the theoretical mask law would also help. I regard these as suggested validation, not as a demand to certify global optimality numerically.
2 comments
AuthorsOpenReview ↗

Response I

Thank you for recognizing the theoretical contribution and for the concrete suggestions on framing and validation. We have clarified the optimization connection, revised the exposition, and added the suggested matched-margin diagnostics. References below are to the revised manuscript; revised text is marked in blue.

1. Endpoint formulation and its connection to training (W1/Q1).

Our endpoint formulation builds on prior work on norm minimisation after fitting. We formalise this viewpoint by minimising parameter norm under unit training margins and ask which task structures make every global minimizer generalise. Theorems 3.5 and 4.1 and Corollary 4.4 establish relabelling invariance and the two structural poles under the stated architecture and sampling assumptions (Sections 3.4–4.1, pp. 5–8). All-goodness makes generalisation independent of which global minimum-norm solution is selected.

The formulation targets late-stage, interpolating cross-entropy training with L2L_2 norm control, as in our SGD/weight-decay protocol (Appendix D.1, p. 25). Implicit-bias results also motivate comparing norms at a common training margin. This constrained comparison isolates the norm preference within the classification-loss/regularisation tradeoff of finite-weight-decay training.

The proof also covers unit-margin feasible solutions within the controlled cost budget, including approximate minimizers satisfying that bound. The carrier bounds the optimum, and the notch excludes bad feasible solutions throughout this region (new guide in Section 4, p. 6; Lemma 4.3 and Eq. (14), p. 8). For a training trajectory, the required link is fitting the observations and entering this region after margin normalisation. The new diagnostics track the relevant cost changes during finite training.

We now discuss Kumar et al. (2024, Section 3) in Section 2, p. 3. Their increasing-norm, zero-weight-decay examples illustrate the importance of specifying the norm and scale being compared. Our endpoint problem compares costs at a common training margin, which the new experiments measure under our SGD/weight-decay protocol. Our contribution addresses the generalising solution structure of grokking tasks and complements dynamical accounts of the delay and abrupt transition (Appendix E.2, pp. 30–31).

2. Positioning and presentation (W2).

We have sharpened the central question and carrier contribution in Section 1, pp. 1–3, and rewritten Related Work in Section 2, pp. 3–4. The new qualitative guide preceding the formal results (Section 4, p. 6) follows the proof: a full-task carrier bounds endpoint costs; subtracting it from rescaled scores turns arbitrary errors, including ties, into confident errors; an atlas fixed before observation sampling lets the notch exclude all such low-cost candidates simultaneously.

The guide also explains the negative result: counting bounds the success probability of every observation-based learner, and every endpoint selector succeeds on an all-good instance. Consequently, under the uniform Latin task-and-mask law, all-good probability tends to zero at fixed observation fraction and success threshold. This makes the interaction between task structure and norm preference explicit: all-goodness is guaranteed for the abelian families but is asymptotically rare in the ambient Latin ensemble.

AuthorsOpenReview ↗

Response II

3. New numerical validation at matched training margins (Q2).

Following your suggestion, we added Appendix D.6.1, pp. 28–29, and Figure 4, p. 29. It reports 33 runs across q∈{47,79,113}q\in\{47,79,113\} and observation fractions α∈{0.25,0.33,0.40}\alpha\in\{0.25,0.33,0.40\}, with five initializations at q=47q=47 and three at each larger order. Each mask is a fixed-size prefix of a uniformly random permutation, matching Eq. (1); masks are nested across fractions and shared across initializations.

For every checkpoint with positive minimum training margin mm, we rescale its scores to F/mF/m through the corresponding parameter rescaling, including biases. Predictions are unchanged and the minimum training margin is exactly one, matching the endpoint constraint. Eq. (99), p. 28, records the cost of this explicit feasible parameter representative with the checkpoint's rescaled factorisation.

At q=79q=79 and 33% coverage, all three runs already fit every training cell at 20k updates. From 20k to 80k, median held-out accuracy rises from 0.33% to 99.57%, while median unit-margin cost falls from 785.37 to 464.59. At q=113q=113 and 25% coverage, candidates trained on the same mask attain 99.15% accuracy at cost 699.17 and 56.03% accuracy at cost 1138.72.

Across all 33 runs, final normalized costs are lower than at 10k. The 48 within-mask comparisons comprise 27 lower-cost/higher-accuracy pairs, nine reverse orderings, and 12 accuracy ties. The pairs share runs, so these counts serve as descriptive summaries. These observations support the relevance of margin-normalized cost during finite training, with variation across initialisations. Calibrating the theorem's finite-instance cost boundary and certifying membership in the global endpoint set remain separate optimisation questions.

Complementarily, Appendix D.2 and Table 3, pp. 25–26, show exact completion across all five seeds at coverage 33%, 25%, 23%, and 20% for q=47,79,113,211q=47,79,113,211. We now highlight these finite-size examples in Remark 4.7, p. 9. Together, D.2 examines the order–coverage relation, while the new D.6.1 examines the optimization connection at matched margins.

Reviewer_PvdwOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper looks to see which tasks cause generalization with grokking, regardless of the length of training. Grokking refers to the delayed generalization process by which a neural network initially 'memorizes' the data, seemingly overfits the data with performance plateauing, and then after a delay and further training, there is in effect an a-ha lightbulb moment and suddenly transitions to behaving as if the underlying rule has been learned and effectively handling new, unseen data. Other work has focused on why the delay; here the focus is on why the final state.

The paper studies every solution with small weights that fits the training data, not just whether one training run succeeds. It asks whether every minimum norm solution fills in the rest of a table correctly from a random sample of cells. 2 results were found: as the table size grows, with probability tending to one over the random sample, whereas for a uniformly random Latin square, no learner that sees only the observed cells generalizes. Experiments showed that a relabelled addition table looks statistically indistinguishable from random, yet always generalizes. At the same time, while truly random tables never generalize, implying a hidden structure rather than just simplicity is crucial here. There are remaining questions: whether a compact carrier network is necessary for generalization and whether there is a mixed case where the smallest solutions generalize sometimes and in other cases they don't.

Critical strengths

This is clearly written and cleanly framed. It is a fundamental issue and appears to be a new question not otherwise addressed sufficiently about grokking. The paper looks at every minimum-norm solution that fits the training data, rather than just a single run. Works with proof approach rather than depending on any specific table but useful empiric examples. Very clean results with Abelian vs uniformly random Latin square showing different sides of the coin. It is honest about limitations: no rate, single hidden layer, leaving open mixed case or non-abelian.

Critical weaknesses

This work only is relevant to single hidden layer networks and does not show more complicated neural networks.

This is the beginning but not the end. The mixed question (whether some resolve in some cases) is not fully addressed. No mixed results are known.

The abelian group result holds only as the table grows, no rate, so it guarantees nothing at a fixed size. This included experimental results, but not a proof.

Non-abelian groups were not included.

I found the related work quite difficult to read. It is just a listing in sentence form without any synthesis, but which required so many citations, often presented in the middle of the sentence, that it's difficult to read. I would appreciate more conceptually similar work described and explored in a few sentences to show the relationship between this work and the current.

Questions for authors

You said it would break for deeper architectures, do you expect any part to work? anything you can show? not needed for this paper but curious.

Can you rewrite the related work section to highlight some important related works? it would help place this work in literature.

Can you give a concrete example about the finite, even a rough estimate of q for the abelian example to be true?

2 comments
AuthorsOpenReview ↗

Response I

Thank you for the positive assessment and the concrete suggestions. We have revised the presentation and respond to each concern below. Section and page references refer to the revised manuscript; revised text is marked in blue.

1. Depth and possible extensions (W1/Q1).

The restriction to one hidden layer concerns the positive theorem. The uniform-Latin impossibility result is architecture-independent: Theorem 4.1(ii), p. 7, applies to every learner using only the observations, including deeper networks.

For the positive direction, the carrier-based sufficiency principle is architecture-agnostic: a low-cost full-task carrier yields all-goodness when the corresponding network class satisfies the required uniform complexity bound. Applying this principle to deeper networks therefore requires establishing the appropriate norm and complexity bounds for those architectures. Our present proof verifies these requirements for the one-hidden-layer ReLU model; extending it is difficult with the techniques in Appendix C, which rely on norm reduction, compression of a sum of ReLU atoms, and degree-controlled sign-pattern counting, all of which change under composition (Appendix E.1, pp. 29–30). Within the one-hidden-layer setting, the notch lemma already covers arbitrary finite hidden width (Lemma 4.3, p. 8), and we prove an extension to (L_2)-regularised biases (Appendix B.2, Corollary B.4, p. 13).

Appendix E.1, p. 30, discusses the empirical evidence on depth: Fan et al. (2024) [arxiv 2405.19454] observe grokking in 12-layer MLPs, while Manir and Rupa (2026) [arxiv 2603.25009] report failure in their depth-4 configuration and recovery in some depth-8 residual runs. One possible explanation for the latter recovery is that residual connections allow the network to suppress unnecessary residual transformations and thereby adapt its effective depth. Related instability is documented by Gu et al. (2025, Section 5 and Figure 2) [arxiv 2504.03162], who report sharp, large-amplitude fluctuations in test accuracy as Transformer depth increases. These observations suggest that the stability of grokking depends on how depth is implemented and used.

2. The unresolved mixed phase (W2).

Constructing a family with non-vanishing mixed probability remains open. Theorem B.1 and Proposition B.2, Appendix B.1, pp. 12–13, provide an exact finite-instance characterization through held-out margin extrema over a compact normalized minimizer set. In particular, an instance is mixed for some threshold precisely when its global minimum-norm responses have different held-out accuracies. Applying this criterion to variation across finite-training runs requires verifying that the compared responses belong to the global minimum-norm set. We have made numerous attempts to address the mixed-case scenario; however, proving its existence—or non-existence—has proven exceptionally difficult.

3. Concrete finite-qq examples (W3/Q3).

The empirical behavior is already visible at orders in the tens. Appendix D.2, pp. 25–26, and Table 3, p. 26, report the smallest tested observation fractions at which all five training seeds achieve exactly 100% held-out accuracy:

qq4779113211
Observed fraction33%25%23%20%

Thus q=47q=47 already gives a concrete finite-training example, with greater coverage than the larger tested orders. For a non-cyclic example, the elementary abelian group C26C_2^6 at q=64q=64 reaches exact completion in all six runs at nominal 30% coverage (Section 5, Table 1, p. 10).

We have added an explicit pointer from Remark 4.7, p. 9, and explanatory text in Appendix D.2. These experiments give finite-training examples of the order–coverage relation.

4. Non-abelian groups (W4).

Non-abelian groups are included experimentally: the order-64 dihedral group has median held-out accuracy 0.870 across six runs (Section 5, Table 1, p. 10). Extending the positive theorem to these groups remains open. Appendix E.3.4, pp. 33–34, explains the obstruction: scalar characters identify all commutators with the identity. It develops a candidate construction using higher-dimensional representations and identifies the norm and approximation-error estimates needed to complete the extension. The general carrier criterion applies to any colouring family satisfying its cost and margin conditions (Proposition E.2, Appendix E.3.1, pp. 31–32), providing a route through a sufficiently cheap carrier.

AuthorsOpenReview ↗

Response II

5. Related work and accessibility (W5/Q2).

We have rewritten Section 2, pp. 3–4, around three connections: coordinate-dependent mechanistic explanations, training dynamics and circuit efficiency, and provable grokking under specific model assumptions. The discussion now explains how our relabelling-invariant classification and structural carrier criterion complement those approaches. We also revised the Introduction’s organization paragraph (p. 3) and added a qualitative proof guide (Section 4, p. 6), tracing the carrier cost bound, conversion of errors into confident errors, uniform notch exclusion, and the separate counting argument behind the rarity of all-good tasks.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.