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

Sintesi Tecnica: L'Orologio del Logaritmo Discreto

Definizione del Problema
Mentre i meccanismi interni dei transformer che apprendono l'addizione modulare ($a + b \mod p$) sono stati completamente decodificati come rappresentazioni di Fourier sparse (l'algoritmo "Clock"), il meccanismo per la moltiplicazione modulare ($a \cdot b \mod p$) è rimasto elusivo. Studi empirici precedenti (Doshi et al., 2024; Furuta et al., 2024) hanno riportato che i transformer addestrati sulla moltiplicazione apprendono spettri di Fourier "densi" che richiedono tutte le frequenze, contrastando nettamente con la struttura sparsa riscontrata nell'addizione. Ciò suggeriva che la moltiplicazione potesse fare affidamento su un algoritmo fondamentalmente diverso e meno interpretabile.

Metodologia
Gli autori addestrano un transformer decoder-only a 1 strato per predire $a \cdot b \mod 113$ per input $a, b \in \{1, \dots, 112\}$. Il modello è addestrato su un 30% dei dati e deve generalizzare al restante 70%, esibendo il fenomeno del "grokking", in cui la generalizzazione avviene improvvisamente dopo un lungo periodo di memorizzazione.

L'innovazione metodologica centrale è uno spostamento della base di analisi. Inveia di applicare la standard trasformata discreta di Fourier (DFT) additiva agli embedding dei token, gli autori applicano la trasformata dei caratteri moltiplicativi. Questo comporta:

1. Il riconoscimento che gli interi non nulli modulo un numero primo $p$ formano un gruppo ciclico $(\mathbb{Z}/p\mathbb{Z})^*$.
2. L'uso di una radice primitiva $g$ (qui $g=3$) per mappare gli input nei loro logaritmi discreti: $\alpha = \log_g(a)$ e $\beta = \log_g(b)$.
3. Il riordinamento delle righe della matrice di embedding secondo questi logaritmi discreti.
4. L'applicazione della DFT standard a questi dati riordinati.

Questo approccio sfrutta l'isomorfismo di gruppo in cui la moltiplicazione nello spazio originale corrisponde all'addizione nello spazio del logaritmo discreto ($a \cdot b \equiv g^{\alpha + \beta} \mod p$).

Risultati Chiave

• Sparsità Spettrale: Quando analizzato nella base additiva, lo spettro dell'embedding appare piatto e denso (coefficiente di Gini 0,07). Tuttavia, nella base dei caratteri moltiplicativi, lo spettro diventa altamente sparso (coefficiente di Gini 0,58), con l'energia concentrata in soli 4 frequenze chiave ($\{2, 8, 47, 56\}$).
• Sintonizzazione dei Neuroni: Nella base moltiplicativa, il 96,9% (496/512) dei neuroni MLP è "pulitamente sintonizzato" su una singola frequenza, con oltre l'85% dell'energia di attivazione concentrata in essa. Nella base additiva, zero neuroni soddisfano questa soglia.
• Visualizzazione Strutturale: Quando le mappe termiche di attivazione dei neuroni vengono riordinate per logaritmo discreto, rivelano chiare strisce diagonali periodiche 2D. Ciò indica che i neuroni computano funzioni della forma $\cos(k(\alpha + \beta))$, eseguendo efficacemente l'addizione nello spazio logaritmico.
• Analisi SVD: Le componenti principali della matrice di embedding, quando riordinate per logaritmo discreto, esibiscono chiare strutture sinusoidali, confermando la codifica dei caratteri moltiplicativi.

L'Algoritmo dell' "Orologio del Logaritmo Discreto"
Il paper conclude che il transformer implementa un algoritmo analogo all'algoritmo "Clock" per l'addizione, denominato Orologio del Logaritmo Discreto (Discrete-Log Clock). Il meccanismo procede come segue:

1. Embedding: Gli interi sono incorporati come funzioni sinusoidali dei loro logaritmi discreti.
2. Routing: I meccanismi di attenzione indirizzano questi embedding alla posizione di output.
3. Composizione: L'MLP applica identità trigonometriche per computare le somme dei logaritmi discreti (effettuando l'addizione di $\alpha + \beta$).
4. Decoding: Il modello valuta i candidati di output allineandoli con la somma computata nello spazio logaritmico, dove la risposta corretta ottiene un'interferenza costruttiva attraverso le frequenze chiave.

Significato e Rivendicazioni
Il contributo primario è dimostrare che lo "spettro denso" osservato negli studi precedenti è un artefatto dell'analisi dei dati nella base errata, non un riflesso della complessità algoritmica. Facendo coincidere la base di analisi con la struttura algebrica del compito (il gruppo moltiplicativo), gli autori rivelano che la moltiplicazione viene ridotta all'addizione nello spazio del logaritmo discreto.

Il paper afferma che questa metodologia è generalizzabile:

• Lo spettro moltiplicativo sparso è stato confermato su 10 numeri primi diversi ($p=59$ a $113$).
• Il meccanismo è universale tra diversi seed casuali (circa l'80% dei seed).
• Risultati preliminari suggeriscono che l'approccio si estende all'elevamento a potenza modulare ($a^b \mod p$) utilizzando un transformer a 2 strati.

Gli autori sottolineano che per qualsiasi compito algebrico, applicare la trasformata di Fourier sul gruppo pertinente (anziché la standard DFT additiva) è essenziale per rivelare una struttura interpretabile dove gli strumenti standard vedevano solo rumore.