💻 informatica

Grokking the Discrete Logarithm: Scaling Across Model Capacity and Mechanistic Analysis

Questo articolo presenta la prima dimostrazione sistematica che i transformer possano esibire il "grokking" — una transizione ritardata dalla memorizzazione alla generalizzazione algoritmica — sul problema completo del logaritmo discreto a base variabile, rivelando che questo fenomeno scala in modo non monotono con la capacità del modello ed è guidato dall'emergere di rappresentazioni a carattere moltiplicativo e allineate con la trasformata di Fourier.

Autori originali: David Vesterlund

Pubblicato 2026-10-13

📖 6 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: David Vesterlund

Articolo originale sotto licenza CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Nel vasto panorama dell'intelligenza artificiale, i ricercatori cercano costantemente di capire come le macchine imparino. Un comportamento particolarmente enigmatico, noto come "grokking", ha recentemente catturato la loro attenzione. Immaginate uno studente che memorizza ogni singola risposta di un libro di testo per un esame. Può recitare le risposte perfettamente, ma se gli viene posta una domanda leggermente diversa, fallisce completamente. Il grokking è il momento, che avviene spesso molto tempo dopo che lo studente ha già memorizzato il materiale, in cui smette improvvisamente di limitarsi a recitare fatti e inizia a comprendere davvero le regole sottostanti. Questo passaggio dalla memorizzazione mnemonica alla vera generalizzazione avviene bruscamente, talvolta dopo migliaia di ore di pratica, lasciando gli scienziati a chiedersi come e perché il cervello della macchina si riorganizzi improvvisamente per trovare la logica dietro i dati.

Questo fenomeno è stato notato per la prima volta in semplici compiti matematici, ma un nuovo studio di David Vesterlund lo porta in un territorio molto più difficile. Il ricercatore si è posto l'obiettivo di vedere se un modello computazionale potesse "grokkar" un problema che è notoriamente difficile sia per gli esseri umani che per le macchine: il logaritmo discreto. In termini semplici, questo è un puzzle di ingegneria inversa. Se conosci un numero di partenza e un numero finale, il compito è capire esattamente quante volte hai dovuto moltiplicare il numero di partenza per se stesso per raggiungere quello finale. Mentre il calcolo in avanti è facile, lavorare all'indietro è incredibilmente difficile, specialmente quando i numeri sono grandi e le regole sono rigide. Questo specifico tipo di problema matematico è la base della moderna sicurezza digitale, rendendo questo un test serio per qualsiasi sistema di apprendimento. Vesterlund voleva vedere se una rete neurale, un tipo di IA progettata per imitare il cervello umano, potesse alla fine decifrare questo codice non memorizzando ogni possibile risposta, ma scoprendo la struttura matematica nascosta che le connette.

Per investigare su questo, il ricercatore ha costruito una serie di modelli computazionali, che vanno da piccoli a molto grandi, e li ha nutriti con un enorme dataset di questi puzzle di ingegneria inversa. I modelli sono stati addestrati su un numero primo specifico, 113, che definisce le regole del gioco. Il modello più piccolo che ha avuto successo aveva circa 427.000 parametri regolabili, un numero che rappresenta la complessità del suo cervello interno. Quando l'addestramento è iniziato, il modello si è comportato esattamente come previsto per un sistema di machine learning: ha rapidamente memorizzato le risposte che aveva già visto, ottenendo punteggi quasi perfetti sui problemi di pratica. Tuttavia, quando testato su nuovi puzzle mai visti, le sue prestazioni non erano migliori del caso casuale. Per un tempo molto lungo, il modello sembrava bloccato in questo stato di memorizzazione, incapace di generalizzare.

Poi, dopo migliaia di passaggi di addestramento aggiuntivi, è accaduto qualcosa di drammatico. Il modello ha iniziato improvvisamente a risolvere correttamente i nuovi puzzle, passando dal caso casuale a una precisione quasi perfetta. Questo è stato il momento del grokking. Il ritardo era sorprendente: il modello ha richiesto circa trecento volte più passaggi di addestramento per raggiungere la vera comprensione rispetto a quelli necessari per semplicemente memorizzare le risposte. Per capire se si trattasse di una coincidenza o di una proprietà fondamentale di questi sistemi, il ricercatore ha testato dodici diversi modelli di varie dimensioni, dai minuscoli con 90.000 parametri ai massicci con oltre 14 milioni. I risultati hanno mostrato che il grokking non è limitato a una dimensione specifica. È apparso nei modelli di medie dimensioni e di nuovo in quelli più grandi, a condizione che gli venisse fornito abbastanza materiale di addestramento. Interessantemente, c'era un intervallo intermedio in cui i modelli non riuscivano a imparare, suggerendo che la relazione tra la dimensione del cervello e la quantità di dati necessari sia complessa e non una semplice linea retta.

Per capire cosa stesse accadendo nella mente del modello durante questa trasformazione, il ricercatore ha esaminato da vicino i segnali interni che il modello utilizza per prendere decisioni. Ha scoperto che, mentre il modello passava dalla memorizzazione alla comprensione, il suo linguaggio interno cambiava. Smetteva di fare affidamento su schemi superficiali e semplici e iniziava a organizzare la sua conoscenza attorno a un tipo specifico di ritmo matematico, simile al modo in cui le onde sonore possono essere scomposte in frequenze distinte. Utilizzando una tecnica che cerca equazioni semplici per descrivere questi segnali interni, il ricercare ha scoperto che il modello aveva imparato spontaneamente a usare schemi trigonometrici — onde di seno e coseno — per rappresentare la soluzione. Questa è stata una scoperta profonda perché il modello non era stato esplicitamente istruito a usare queste onde; le aveva scoperte da solo come il modo più efficiente per risolvere il puzzle.

Lo studio ha incluso anche controlli rigorosi per garantire che il modello non stesse solo trovando una scorciatoia specifica per i numeri utilizzati. Il ricercatore ha testato i modelli su una versione diversa del problema dove le regole erano leggermente più complesse e i numeri erano primi, eliminando eventuali scorciatoie facili. I modelli hanno comunque effettuato il grokking, provando che avevano appreso una regola generale piuttosto che un trucco specifico. Inoltre, quando i modelli sono stati testati su generatori che non avevano mai visto prima, hanno comunque avuto successo, dimostrando di aver appreso veramente la logica sottostante del sistema. La ricerca suggerisce che la chiave di questo salto improvviso nella comprensione sia stata una specifica tecnica di addestramento che aumentava gradualmente la pressione per semplificare le connessioni interne del modello, costringendolo a scartare i dettagli memorizzati e a mantenere solo la struttura essenziale.

Questo lavoro stabilisce il logaritmo discreto come un potente nuovo strumento per studiare come l'intelligenza artificiale apprenda. Dimostra che, anche per problemi inversi difficili dove non esiste una regola semplice, le reti neurali possono infine transitare dalla memorizzazione rotea alla profonda comprensione strutturale. Le scoperte confermano che questa transizione non è un evento magico, ma un processo misurabile che comporta la riorganizzazione delle rappresentazioni interne in schemi efficienti e simili a onde. Sebbene lo studio sia stato condotto su numeri relativamente piccoli e non risolva il problema di violare la crittografia del mondo reale, esso fornisce una finestra chiara sulla meccanica dell'apprendimento. Mostra che, con abbastanza tempo e nelle giuste condizioni, questi sistemi possono andare oltre il memorizzare il passato per comprendere le regole che governano il futuro.

Riassunto Tecnico: Comprendere il Logaritmo Discreto (Grokking)

Definizione del Problema

Questo studio investiga il fenomeno del grokking — una transizione ritardata dalla memorizzazione alla generalizzazione algoritmica nelle reti neurali — sul problema del logaritmo discreto in campo finito a base variabile completa. A differenza delle precedenti ricerche sul grokking focalizzate su operazioni algebriche dirette (come l'addizione o la moltiplicazione modulare), il DLP è una mappatura inversa: dato un generatore $g$ e un elemento $h$ in un gruppo moltiplicativo $\mathbb{F}_p^*$ , il modello deve trovare $x$ tale che $g^x \equiv h \pmod p$ .

Il compito è definito come un problema di classificazione su $p-1$ classi. L'input consiste in un generatore $g$ (estratto uniformemente da radici primitive) e un elemento $h$ , tokenizzati come $[BOS, g, SEP, h, EOS]$ . Lo studio si concentra principalmente sul numero primo $p=113$ , dove la dimensione totale del dominio è di 5.376 triple $(g, h, x)$ uniche.

Metodologia

Architettura del Modello e Addestramento

L'autore impiega un GrokkingTransformer, un encoder pre-norm standard con attivazioni GELU. Il modello ancora (M04) consiste in 2 strati, $d_{model}=128$ , e 4 teste di attenzione, per un totale di circa 427k parametri.

Ottimizzatore: AdamW con un tasso di apprendimento costante ( $\eta=10^{-3}$ ).
Programmazione del Weight Decay (WD): Un componente critico è una rampa progressiva del weight decay. Il WD parte da 0,05 e aumenta di 0,05 ogni 1.000 epoche solo dopo che il modello ha raggiunto una precisione di addestramento >99%. Il valore massimo è 0,30 (scalato per modelli più grandi in base al numero di parametri).
Sweep di Scalabilità: Una griglia di 12 modelli (M01–M12) spazia da 90k a 14,4M di parametri ( $d_{model}$ da 56 a 768). Le frazioni di addestramento variano dal 33% al 60% attraverso lo sweep per compensare le differenze di capacità.

Analisi Meccanicistica

Per comprendere le rappresentazioni interne, l'autore utilizza:

Sonde della Struttura di Gruppo: Test della coerenza con le identità algebriche (composizione, scorrimento ciclico, inverso).
Analisi Spettrale di Fourier: Proiezione degli stati nascosti sulle basi dei caratteri moltiplicativi (allineate con i logaritmi discreti) e sulle basi additive.
Regressione Simbolica (SR): Utilizzo di PySR per adattare equazioni agli attivazioni degli strati nascosti. Vengono utilizzati due set di operatori:
- SR Libera: Operatori standard senza conoscenza dell'aritmetica modulare.
- SR Consapevole dell'Algebra: Include feature modulari precomputate (es. $\cos(2\pi x/q)$ ).

Controlli

Controllo dell'Ordine Primo: Esperimenti condotti in un sottogruppo di ordine 113 all'interno di $\mathbb{F}_{227}^*$ per escludere scorciatoie basate sulla fattorizzazione regolare di $p-1$ (112).
Split dei Generatori Disgiunti: Addestramento e test su set di generatori non sovrapponibili per testare la generalizzazione oltre i generatori già visti.

Risultati Chiave

1. Scoperta del Grokking del DLP

Il modello ancora (M04) mostra una classica traiettoria di grokking:

Fase di Memorizzazione: Il modello raggiunge una precisione di addestramento >99% all'epoca 90, ma rimane a un livello di precisione di test casuale (~15%) per circa 22.000 epoche.
Transizione di Grokking: Dopo un prolungato plateau, la precisione di test balza bruscamente al 99,8% all'epoca 37.481.
Rapporto di Ritardo: Il ritardo di grokking ( $G = T_{90}/T_{mem}$ ) è di circa 298, indicando che il modello richiede circa 300 volte più step per generalizzare rispetto a quanto necessario per memorizzare.

2. Scalabilità rispetto alla Capacità del Modello

Uno sweep di 12 modelli rivela una relazione non monotona tra capacità e grokking:

Sottofunzionamento/Transizione: I modelli più piccoli (M01–M03) non riescono a generalizzare. M04 (427k) ha successo.
Valle di Capacità: I modelli M05 (657k) e M06 (1,09M) non riescono a fare grokking con la frazione iniziale di addestramento del 33%. Tuttavia, un esperimento locale mostra che M05 effettua il grokking quando la frazione di addestramento è aumentata al 40%, suggerendo che il fallimento sia dovuto a una quantità insufficiente di dati piuttosto che a un'incapacità intrinseca del modello.
Modelli Grandi: I modelli da M07 a M12 (da 1,64M a 14,4M di parametri) effettuano il grokking con successo, con il tempo necessario per il grokking che diminuisce all'aumentare della dimensione del modello.

3. Dinamiche di Addestramento

La transizione coinvolge 18 distinti eventi "slingshot", in cui la precisione di addestramento crolla temporaneamente a causa dell'interazione tra AdamW e il weight decay. Questi eventi precedono il salto finale di generalizzazione. Post-grokking, la norma del peso diminuisce significativamente (da ~148 a ~30), indicando una transizione verso una soluzione a norma inferiore.

4. Firme Meccanicistiche

Allineamento Algebrico: Durante la transizione di grokking, la coerenza interna del modello con le identità della teoria dei gruppi (composizione, scorrimento ciclico) aumenta parallelamente alla precisione di test.
Sparsezza Spettrale: La rappresentazione nascosta diventa sparsa nella base dei caratteri moltiplicativi (armoniche di Fourier del logaritmo discreto), mentre la base additiva rimane diffusa.
Regressione Simbolica:
- La SR consapevole dell'algebra recupera preferenzialmente feature trigonometriche allineate con i caratteri moltiplicativi ( $\cos(2\pi x/q)$ ).
- Fondamentalmente, la SR Libera (senza conoscenza modulare) recupera indipendentemente validi armonici di Fourier (es. frequenze corrispondenti a $\pi/2$ e $\pi$ ), confermando che la struttura è intrinseca alla rappresentazione appresa e non un artefatto del set di operatori.

5. Controlli Strutturali

DLP a Ordine Primo: Il fenomeno persiste in un sottogruppo di ordine primo (ordine 113), provando che il grokking non dipende dalla fattorizzazione regolare dell'ordine del gruppo.
Generatori Disgiunti: Il modello generalizza a generatori non visti durante l'addestramento, raggiungendo una precisione di test del 100% nello split dei generatori disgiunti.

Significato e Rivendicazioni

L'articolo sostiene di fornire la prima dimostrazione sistematica del grokking sulla mappatura completa del logaritmo discreto a base variabile. I suoi principali contributi sono:

Benchmark: Stabilire il DLP come un benchmark compatto e non banale per studiare l'interazione tra memorizzazione, formazione della rappresentazione e generalizzazione.
Leggi di Scalabilità: Dimostrare che il grokking non è limitato ai piccoli modelli ma riappare attraverso una vasta gamma di scale neurali (fino a 14,4M di parametri), sebbene sia sensibile al rapporto tra capacità del modello e dati di addestramento.
Intuizione Meccanicistica: Fornire prove che la generalizzazione di successo su questo problema inverso corrisponde all'emergere di una rappresentazione Fourier sparsa e allineata con i caratteri moltiplicativi.
Robustezza: Mostrare che il fenomeno non è un artefatto di specifiche strutture di gruppo (smooth vs. ordine primo) o di generatori specifici visti durante l'addestramento.

L'autore rimane modesto riguardo alla criptanalisi pratica, notando che gli esperimenti utilizzano piccoli gruppi finiti ( $p=113$ ) e non pretendono di risolvere il DLP per grandi numeri primi crittografici. Invece, il lavoro serve come ambiente controllato per studiare il "meccanismo slingshot" e la formazione di circuiti algoritmici nel deep learning.