🤖 machine learning

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

Diese Arbeit zeigt auf, dass die scheinbare Komplexität von Transformern beim Erlernen modularer Multiplikation ein Artefakt der Verwendung einer falschen analytischen Basis ist, indem sie offenlegt, dass sie tatsächlich einen spärlichen, interpretierbaren „Diskreter-Logarithmus-Uhr“-Algorithmus implementieren, indem sie Multiplikation durch Reduktion auf Addition im Raum der multiplikativen Charaktere umwandeln.

Ursprüngliche Autoren: Huu Danh Nguyen (Stanford University)

Veröffentlicht 2026-06-17

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Huu Danh Nguyen (Stanford University)

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Rätsel: Warum war die KI „verwirrt“?

Stellen Sie sich vor, Sie versuchen, einem Roboter das Rechnen beizubringen. Speziell möchten Sie ihm die modulare Multiplikation beibringen (das Multiplizieren zweier Zahlen und das Behalten nur des Rests bei der Division durch eine bestimmte Zahl, wie zum Beispiel 113).

Lange Zeit bemerkten Wissenschaftler etwas Seltsames. Als der Roboter es schließlich „verstanden“ hatte (ein Phänomen namens Grokking, bei dem er plötzlich von der bloßen Auswendiglernung von Antworten zum Verständnis der zugrunde liegenden Regel übergeht), sah die interne Mathematik chaotisch aus.

Die alte Sichtweise: Wenn Wissenschaftler in das Gehirn des Roboters mit Standardwerkzeugen blickten, sahen sie ein „dichtes“ Durcheinander. Es wirkte, als würde der Roboter jede einzelne mögliche Frequenz von Klängen nutzen, um das Problem zu lösen. Es schien chaotisch und schwer zu verstehen, ganz im Gegensatz dazu, wie er einfache Additionen löste, die ordentlich und strukturiert aussah.
Das Problem: Die Wissenschaftler betrachteten das Gehirn des Roboters durch die falsche Brille. Sie benutzten ein „Standardlineal“, das für die Addition entwickelt wurde, aber der Roboter führte tatsächlich eine Multiplikation durch.

Die Lösung: Den Fokus ändern

Die Autoren dieser Arbeit erkannten, dass man, um die Multiplikation zu verstehen, aufhören muss, die Zahlen als das zu sehen, was sie sind (1, 2, 3...), und stattdessen beginnen muss, sie als Potenzen eines Erzeugers zu betrachten.

Stellen Sie sich das so vor:

Die Standardansicht (Additiv): Stellen Sie sich ein Zifferblatt einer Uhr mit den Zahlen 1 bis 12 vor. Wenn Sie 1 addieren, bewegen Sie sich einen Schritt weiter. Das ist einfach zu sehen.
Die verborgene Ansicht (Multiplikativ): Stellen Sie sich nun vor, die Zahlen auf der Uhr sind durcheinandergewürfelt. Die Zahl „1“ ist eigentlich eine „3“, die Zahl „2“ ist eine „9“ und so weiter. In dieser verwirrten Welt funktioniert die Multiplikation tatsächlich exakt wie die Addition.

Die Arbeit nennt dies die „Diskret-Logarithmus-Uhr“ (Discrete-Log Clock). Es ist ein Geheimcode, durch den sich das chaotische Multiplikationsproblem in ein einfaches Additionsproblem verwandelt.

Was sie herausgefunden haben (Der „Aha!“-Moment)

Als die Forscher das Gehirn des Roboters unter Verwendung dieser neuen „verwirrten“ Linse (die sie die multiplikative Charaktertransformation nennen) erneut untersuchten, verschwand das Chaos.

Das Rauschen wurde zu einem Signal: Anstatt ein chaotisches, „dichtes“ Spektrum zu sehen, sahen sie ein sehr klares, spärliches Muster. Der Roboter nutzte nicht alle Frequenzen; er nutzte nur 4 spezifische Frequiken, um die Mathematik zu betreiben. Es war, als fände man eine einzige, klare Melodie in einem Raum voller statischem Rauschen.
Die Neuronen wurden organisiert: Der Roboter besitzt tausende winzige Verarbeitungseinheiten (Neuronen). In der alten Sichtweise wirkten sie zufällig. In der neuen Sichtweise waren 97 % von ihnen perfekt auf genau eine dieser 4 Frequenzen abgestimmt. Sie waren wie ein Chor, bei dem jeder Sänger genau weiß, welchen Ton er treffen muss.
Das Muster trat hervor: Als sie die Daten basierend auf diesem Geheimcode neu anordneten, bildete die interne Aktivität des Roboters perfekte diagonale Streifen. Dies bewies, dass der Roboter einen speziellen Trick gelernt hatte:
- Schritt 1: Wandle die Zahlen in ihren „Geheimcode“ um (diskrete Logarithmen).
- Schritt 2: Addiere die Codes zusammen (genau wie bei der normalen Addition).
- Schritt 3: Wandle das Ergebnis zurück in die normale Zahl um.

Die „Uhren“-Analogie

Die Arbeit vergleicht dies mit einem berühmten „Uhren-Algorithmus“, der für die Addition verwendet wird.

Für die Addition: Der Roboter lernt, einen Zeiger einer Uhr zu drehen.
Für die Multiplikation: Der Roboter lernt, einen anderen Typ von Uhr zu drehen (die Diskret-Logarithmus-Uhr). Sobald er den Zeiger auf dieser speziellen Uhr dreht, ist das Ergebnis direkt da.

Warum haben frühere Wissenschaftler das übersehen?

Stellen Sie sich vor, Sie versuchen, ein Lied zu hören, aber Sie tragen Noise-Cancelling-Kopfhörer, die nur den Bass durchlassen. Sie hören ein dumpfes, chaotisches Geräusch und schlussfolgern: „Dieses Lied besteht nur aus Rauschen.“

Die vorherigen Forscher trugen diese „Kopfhörer“ (die Standard-Mathematikwerkzeuge). Sie sahen das „Dumpfen“ (dichtes Spektrum) und glaubten, der Roboter nutze eine komplexe, unerklärliche Methode. Die Autoren nahmen einfach die Kopfhörer ab, wechselten auf die richtige Frequenz und erkannten, dass der Roboter tatsächlich eine wunderschöne, einfache Melodie spielte.

Das Fazit

Die wichtigste Lehre dieser Arbeit handelt nicht nur von Mathematik; sie handelt davon, wie wir Dinge betrachten.

Die Lektion: Wenn Sie versuchen, ein komplexes System zu verstehen (wie eine KI oder eine Gruppe von Menschen), stellen Sie sicher, dass Sie die richtige „Sprache“ oder „Basis“ für die Aufgabe verwenden.
Das Ergebnis: Wenn man sein Analysewerkzeug auf die tatsächliche Struktur des Problems abstimmt (in diesem Fall die Verwendung der „multiplikativen“ Linse für die Multiplikation), verwandelt sich das chaotische, unerklärliche Rauschen in ein klares, einfaches und verständliches Algorithmussystem.

Der Roboter hat keinen neuen, mysteriösen Weg der Mathematik erfunden. Er hat nur den Geheimcode gefunden, der ein schwieriges Problem in ein einfaches verwandelt – und die Forscher haben endlich gelernt, diesen Code zu lesen.

Technische Zusammenfassung: Die diskrete-Logarithmus-Uhr

Problemstellung
Während die internen Mechanismen von Transformern, die modulare Addition ( $a + b \mod p$ ) lernen, als dünnbesetzte Fourier-Repräsentationen vollständig rückentwickelt wurden (der „Clock“-Algorithmus), blieb der Mechanismus für modulare Multiplikation ( $a \cdot b \mod p$ ) rätselhaft. Zuvysische empirische Studien (Doshi et al., 2024; Furuta et al., 2024) berichteten, dass Transformer, die auf Multiplikation trainiert wurden, „dichte“ Fourier-Spektren erlernen, die alle Frequenzen benötigen, was in starkem Kontrast zur dünnbesetzten Struktur bei der Addition steht. Dies deutete darauf hin, dass die Multiplikation möglicherweise auf einem grundlegend anderen, weniger interpretierbaren Algorithmus beruht.

Methodik
Die Autoren trainieren einen 1-Layer-Decoder-only-Transformer, um $a \cdot b \mod 113$ für Eingaben $a, b \in \{1, \dots, 112\}$ vorherzusagen. Das Modell wird auf 30 % der Daten trainiert und muss auf die verbleibenden 70 % generalisieren, wobei es das „Grokking“-Phänomen zeigt, bei dem die Generalisierung nach einer langen Phase des Auswendiglernens plötzlich eintritt.

Die zentrale methodische Innovation ist ein Wechsel der Analysebasis. Anstatt die standardmäßige additive Diskrete Fourier-Transformation (DFT) auf die Token-Embeddings anzuwenden, wenden die Autoren die multiplikative Charakter-Transformation an. Dies beinhaltet:

Die Erkenntnis, dass die nicht-nullen ganzen Zahlen modulo einer Primzahl $p$ eine zyklische Gruppe $(\mathbb{Z}/p\mathbb{Z})^*$ bilden.
Die Verwendung einer primitiven Wurzel $g$ (hier $g=3$ ), um Eingaben auf ihre diskreten Logarithmen abzubilden: $\alpha = \log_g(a)$ und $\beta = \log_g(b)$ .
Die Neuordnung der Zeilen der Embedding-Matrix gemäß dieser diskreten Logarithmen.
Die Anwendung der standardmäßigen DFT auf diese neu geordnete Datenstruktur.

Dieser Ansatz nutzt den Gruppenisomorphismus, bei dem die Multiplikation im ursprünglichen Raum der Addition im diskreten Logarithmus-Raum entspricht ( $a \cdot b \equiv g^{\alpha + \beta} \mod p$ ).

Wichtige Ergebnisse

Spektrale Dünnbesetztheit: Wenn sie in der additiven Basis analysiert wird, erscheint das Embedding-Spektrum flach und dicht (Gini-Koeffizient 0,07). In der multiplikativen Charakter-Basis hingegen wird das Spektrum hochgradig dünnbesetzt (Gini-Koeffizient 0,58), wobei die Energie auf nur 4 Schlüssel-Frequenzen ( $\{2, 8, 47, 56\}$ ) konzentriert ist.
Neuronen-Tuning: In der multiplikativen Basis sind 96,9 % (496/512) der MLP-Neuronen „sauber abgestimmt“ auf eine einzige Frequenz, wobei über 85 % ihrer Aktivierungsenergie dort konzentriert sind. In der additiven Basis erfüllt kein einziges Neuron diesen Schwellenwert.
Strukturelle Visualisierung: Wenn die Heatmaps der Neuronenaktivierung nach dem diskreten Logarithmus neu geordnet werden, offenbaren sie klare 2D-periodische diagonale Streifen. Dies deutet darauf hin, dass die Neuronen Funktionen der Form $\cos(k(\alpha + \beta))$ berechnen und somit effektiv Addition im Logarithmus-Raum durchführen.
SVD-Analyse: Die Hauptkomponenten der Embedding-Matrix weisen, wenn sie nach dem diskreten Logarithmus neu geordnet werden, klare sinusförmige Strukturen auf, was die Kodierung multiplikativer Charaktere bestätigt.

Der „Diskrete-Logarithmus-Uhr“-Algorithmus
Das Paper schließt, dass der Transformer einen Algorithmus implementiert, der dem „Clock“-Algorithmus für die Addition analog ist, bezeichnet als die „Diskrete-Logarithmus-Uhr“. Der Mechanismus verläuft wie folgt:

Embedding: Ganze Zahlen werden als sinusförmige Funktionen ihrer diskreten Logarithmen eingebettet.
Routing: Attention-Mechanismen leiten diese Embeddings an die Output-Position weiter.
Komposition: Das MLP wendet trigonometrische Identitäten an, um Summen der diskreten Logarithmen zu berechnen (effektiv die Addition von $\alpha + \beta$ ).
Dekodierung: Das Modell bewertet Kandidaten-Outputs, indem es sie mit der berechneten Summe im Logarithmus-Raum abgleicht, wobei die korrekte Antwort eine konstruktive Interferenz über die Schlüssel-Frequenzen hinweg erreicht.

Bedeutung und Ansprüche
Der primäre Beitrag besteht darin, zu zeigen, dass das beobachtete „dichte Spektrum“ in vorangegangenen Arbeiten ein Artefakt der Analyse in der falschen Basis ist und nicht ein Spiegelbild der algorithmischen Komplexität. Durch die Anpassung der Analysebasis an die algebraische Struktur der Aufgabe (die multiplikative Gruppe) zeigen die Autoren, dass die Multiplikation auf Addition im diskreten Logarithmus-Raum reduziert wird.

Das Paper behauptet, dass sich diese Methodik generalisieren lässt:

Das dünnbesetzte multiplikative Spektrum wurde über 10 verschiedene Primzahlen ( $p=59$ bis $113$) bestätigt.
Der Mechanismus ist universell über verschiedene Random Seeds hinweg (ca. 80 % der Seeds).
Vorläufige Ergebnisse deuten darauf hin, dass sich der Ansatz mittels eines 2-Layer-Transformers auch auf modulare Exponentiation ( $a^b \mod p$ ) ausweiten lässt.

Die Autoren betonen, dass es für jede algebraische Aufgabe essenziell ist, die Fourier-Transformation auf der relevanten Gruppe (anstatt der standardmäßigen additiven DFT) anzuwenden, um eine interpretierbare Struktur aufzuzeigen, wo Standardwerkzeuge zuvor nur Rauschen sahen.