Djamchid Dalili

Grokking AN

Un réseau apprend à composer des permutations paires dans AN. Il mémorise d'abord, puis comprend la structure du groupe — le phénomène du grokking.

Étape 0
Train loss —
Val loss —
Train acc —
Val acc —

C'est quoi le grokking sur AN ?

AN est le groupe des permutations paires de {0,…,N−1} (groupe alterné), de taille N!/2. La tâche : étant donné deux permutations paires a et b, prédire leur composition a ∘ b (c.-à-d. (a∘b)(i) = a[b[i]]).

Le réseau MLP 2|AN| → 64 (ReLU) → |AN| est entraîné avec AdamW sur un sous-ensemble des |AN|² paires.

Le grokking se produit lorsque :

  • Train acc → 100 % très rapidement (mémorisation)
  • Val acc stagne pendant des milliers de pas
  • Puis val acc saute soudainement → 100 % (généralisation)

Clés : weight decay fort (λ ≥ 0.1) + split partiel + patience.

⚡ A₅ (60 éléments) est plus lent car |A₅|² = 3 600 paires ; les mises à jour se font par tranches de 100 pas.