🤖 machine learning

The Discrete-Log Clock: How a Transformer Learns Modular Multiplication

Cet article démontre que la complexité apparente des transformateurs apprenant la multiplication modulaire est un artefact dû à l'utilisation d'une base analytique inappropriée, révélant qu'ils implémentent en réalité un algorithme de « Horloge de Logarithme Discret » parcimonieux et interprétable en réduisant la multiplication à l'addition dans l'espace des caractères multiplicatifs.

Auteurs originaux : Huu Danh Nguyen (Stanford University)

Publié 2026-06-17

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Huu Danh Nguyen (Stanford University)

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Le Grand Mystère : Pourquoi l'IA était-elle « confuse » ?

Imaginez que vous essayiez d'apprendre à un robot à faire des mathématiques. Plus précisément, vous voulez lui apprendre la multiplication modulaire (multiplier deux nombres et ne garder que le reste de la division par un nombre spécifique, comme 113).

Pendant longtemps, les scientifiques ont remarqué quelque chose d'étrange. Lorsque le robot a fini par « comprendre » (un phénomène appelé grokking, où il passe soudainement de la mémorisation de réponses à la compréhension de la règle), son calcul interne semblait désordonné.

L'ancienne vision : Quand les scientifiques examinaient le cerveau du robot avec des outils standards, ils voyaient un fouillis « dense ». Cela donnait l'impression que le robot utilisait chaque fréquence sonore possible pour résoudre le problème. Cela semblait chaotique et difficile à comprendre, contrairement à la façon dont il résolait l'addition simple, qui paraissait nette et organisée.
Le problème : Les scientifiques regardaient le cerveau du robot avec les mauvaises lunettes. Ils utilisaient une « règle standard » conçue pour l'addition, mais le robot, lui, faisait de la multiplication.

La Solution : Changer de Lentille

Les auteurs de ce papier ont réalisé que pour comprendre la multiplication, il faut arrêter de regarder les nombres tels qu'ils sont (1, 2, 3...) et commencer à les regarder comme des puissances d'un générateur.

Voyez cela de cette façon :

La vue standard (additive) : Imaginez le cadran d'une horloge avec les chiffres de 1 à 12. Si vous ajoutez 1, vous avancez d'un pas. C'est facile à voir.
La vue cachée (multiplicative) : Maintenant, imaginez que les chiffres sur l'horloge soient brouillés. Le chiffre « 1 » est en réalité un « 3 », le chiffre « 2 » est un « 9 », et ainsi de suite. Dans ce monde brouillé, la multiplication fonctionne exactement comme l'addition.

Le papier appelle cela l'« Horloge du logarithme discret ». C'est un code secret où le problème complexe de la multiplication se transforme en un simple problème d'addition.

Ce qu'ils ont trouvé (Le moment « Eurêka ! »)

Lorsque les chercheurs ont réexaminé le cerveau du robot en utilisant cette nouvelle lentille « brouillée » (qu'ils appellent la transformée des caractères multiplicatifs), le chaos a disparu.

Le bruit est devenu un signal : Au lieu de voir un spectre « dense » et désordonné, ils ont vu un motif très net et clair. Le robot n'utilisait pas toutes les fréquences ; il n'utilisait que 4 fréquences spécifiques pour faire le calcul. C'était comme trouver une mélodie unique et claire dans une pièce remplie de bruits statiques.
Les neurones se sont organisés : Le robot possède des milliers de petites unités de traitement (neurones). Dans l'ancienne vision, ils semblaient aléatoires. Dans la nouvelle vision, 97 % d'entre eux étaient parfaitement accordés sur l'une de ces 4 fréquences. Ils étaient comme une chorale où chaque chanteur sait exactement quelle note frapper.
Le motif est apparu : Lorsqu'ils ont réorganisé les données en fonction de ce code secret, l'activité interne du robot a formé de parfaites bandes diagonales. Cela a prouvé que le robot avait appris une astuce spécifique :
- Étape 1 : Convertir les nombres en leur « code secret » (logarithmes discrets).
- Étape 2 : Additionner les codes ensemble (tout comme une addition normale).
- Étape 3 : Reconvertir le résultat en nombre normal.

L'analogie de l'« Horloge »

Le papier compare cela à un célèbre « Algorithme d'Horloge » utilisé pour l'addition.

Pour l'addition : Le robot apprend à faire tourner une aiguille d'horloge.
Pour la multiplication : Le robot apprend à faire tourner une autre sorte d'horloge (l'Horloge du Logarithme Discret). Une fois qu'il fait tourner l'aiguille sur cette horloge spéciale, la réponse est là, sous ses yeux.

Pourquoi les scientifiques précédents ont-ils manqué cela ?

Imaginez que vous essayez d'écouter une chanson, mais que vous portez un casque à réduction de bruit qui ne laisse passer que les basses. Vous entendez un son sourd et désordonné et vous concluez : « Cette chanson n'est que du bruit ».

Les chercheurs précédents portaient ces « casques » (les outils mathématiques standards). Ils ont vu le « vrombissement » (le spectre dense) et ont conclu que le robot utilisait une méthode complexe et inexplicable. Les auteurs ont simplement retiré le casque, ont changé de fréquence, et ont réalisé que le robot jouait en fait une mélodie simple et magnifique.

Ce qu'il faut retenir

La leçon principale de ce papier ne concerne pas seulement les mathématiques ; elle concerne la façon dont nous regardons les choses.

La leçon : Si vous essayez de comprendre un système complexe (comme une IA ou un groupe de personnes), assurez-vous d'utiliser le bon « langage » ou la bonne « base » pour la tâche.
Le résultat : Lorsque vous faites correspondre votre outil d'analyse à la structure réelle du problème (en utilisant, dans ce cas, la lentille « multiplicative » pour la multiplication), le bruit complexe et inexplicable se transforme en un algorithme clair, simple et compréhensible.

Le robot n'a pas inventé une nouvelle façon mystérieuse de faire des mathématiques. Il a simplement trouvé le code secret qui transforme un problème difficile en un problème facile, et les chercheurs ont enfin réussi à déchiffrer ce code.

Résumé Technique : L'Horloge du Logarithme Discret

Énoncé du Problème
Alors que les mécanismes internes des transformeurs apprenant l'addition modulaire ( $a + b \mod p$ ) ont été entièrement rétro-ingénierés sous forme de représentations de Fourier éparses (l'algorithme de l'« Horloge »), le mécanisme de la multiplication modulaire ( $a \cdot b \mod p$ ) est resté insaisissable. Des études empiriques antérieures (Doshi et al., 2024 ; Furuta et al., 2024) ont rapporté que les transformeurs entraînés sur la multiplication apprennent des spectres de Fourier « denses » nécessitant toutes les fréquences, ce qui contraste nettement avec la structure éparse trouvée pour l'addition. Cela suggérait que la multiplication pourrait reposer sur un algorithme fondamentalement différent et moins interprétable.

Méthodologie
Les auteurs entraînent un transformeur décodeur à une seule couche pour prédire $a \cdot b \mod 113$ pour des entrées $a, b \in \{1, \dots, 112\}$ . Le modèle est entraîné sur 30 % des données et doit se généraliser aux 70 % restantes, présentant le phénomène de « grokking » où la généralisation se produit soudainement après une longue période de mémorisation.

L'innovation méthodologique centrale est un changement de base d'analyse. Au lieu d'appliquer la transformée de Fourier discrète (DFT) additive standard aux plongements (embeddings) de jetons, les auteurs appliquent la transformée de caractère multiplicative. Cela implique de :

Reconnaître que les entiers non nuls modulo un nombre premier $p$ forment un groupe cyclique $(\mathbb{Z}/p\mathbb{Z})^*$ .
Utiliser une racine primitive $g$ (ici $g=3$ ) pour mapper les entrées vers leurs logarithmes discrets : $\alpha = \log_g(a)$ et $\beta = \log_g(b)$ .
Réordonner les lignes de la matrice d'embedding selon ces logarithmes discrets.
Appliquer la DFT standard à ces données réordonnées.

Cette approche tire parti de l'isomorphisme de groupe où la multiplication dans l'espace d'origine correspond à l'addition dans l'espace du logarithme discret ( $a \cdot b \equiv g^{\alpha + \beta} \mod p$ ).

Résultats Clés

Rareté Spectrale : Lorsqu'elle est analysée dans la base additive, la spectrale de l'embedding semble plate et dense (coefficient de Gini de 0,07). Cependant, dans la base de caractère multiplicative, le spectre devient hautement épars (coefficient de Gini de 0,58), avec l'énergie concentrée dans seulement 4 fréquences clés ( $\{2, 8, 47, 56\}$ ).
Accordage des Neurones : Dans la base multiplicative, 96,9 % (496/512) des neurones MLP sont « proprement accordés » à une seule fréquence, avec plus de 85 % de leur énergie d'activation concentrée là. Dans la base additive, aucun neurone ne répond à ce seuil.
Visualisation Structurelle : Lorsque les cartes de chaleur d'activation des neurones sont réordonnées par logarithme discret, elles révèlent des bandes diagonales à périodicité 2D claire. Cela indique que les neurones calculent des fonctions de la forme $\cos(k(\alpha + \beta))$ , effectuant ainsi l'addition dans l'espace log.
Analyse SVD : Les composantes principales de la matrice d'embedding, lorsqu'elles sont réordonnées par logarithme discret, présentent des structures sinusoïdales claires, confirmant l'encodage des caractères multiplicatifs.

L'Algorithme de l'« Horloge du Logarithme Discret »
Le papier conclut que le transformeur implémente un algorithme analogue à l'algorithme de l'« Horloge » pour l'addition, nommé Horloge du Logarithme Discret. Le mécanisme procède comme suit :

Plongement (Embedding) : Les entiers sont plongés comme des fonctions sinusoïdales de leurs logarithmes discrets.
Routage : Les mécanismes d'attention routent ces plongements vers la position de sortie.
Composition : Le MLP applique des identités trigonométriques pour calculer des sommes de logarithmes discrets (effectuant ainsi l'addition de $\alpha + \beta$ ).
Décodage : Le modèle évalue les sorties candidates en les alignant avec la somme calculée dans l'espace log, où la réponse correcte atteint une interférence constructive à travers les fréquences clés.

Signification et Revendications
La contribution principale est de démontrer que le « spectre dense » observé dans les travaux précédents est un artefact dû à l'analyse des données dans la mauvaise base, et non le reflet d'une complexité algorithmique. En faisant correspondre la base d'analyse à la structure algébrique de la tâche (le groupe multiplicatif), les auteurs révèlent que la multiplication est réduite à l'addition dans l'espace du logarithme discret.

Le papier affirme que cette méthodologie est généralisable :

La rareté du spectre multiplicatif a été confirmée pour 10 nombres premiers différents ( $p=59$ à $113$).
Le mécanisme est universel à travers les graines aléatoires (environ 80 % des graines).
Des résultats préliminaires suggèrent que l'approche s'étend à l'exponentiation modulaire ( $a^b \mod p$ ) en utilisant un transformeur à 2 couches.

Les auteurs soulignent que pour toute tâche algébrique, l'application de la transformée de Fourier sur le groupe pertinent (plutement que la DFT additive standard) est essentielle pour révéler une structure interprétable là où les outils standards ne voyaient que du bruit.