🔬 condensed matter

Learning Pseudorandom Numbers with Transformers: Permuted Congruential Generators, Curricula, and Interpretability

Questo articolo dimostra che i modelli Transformer possono apprendere e predire con successo sequenze provenienti da complessi Generatori Congruenziali Permutati (PCG) attraverso l'apprendimento curricolare e la scoperta di rappresentazioni a invarianza rotazionale bit a bit, rivelando una legge di scala in cui la lunghezza del contesto richiesta cresce come la radice quadrata del modulo.

Autori originali: Tao Tao, Maissam Barkeshli

Pubblicato 2026-07-17

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Tao Tao, Maissam Barkeshli

Articolo originale sotto licenza CC BY 4.0 (http://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

Immagina di cercare di insegnare a un robot a prevedere il numero successivo in un trucco di magia. Gli mostri una sequenza come 3, 7, 15, 31, e lui deve indovinare cosa viene dopo. Nel mondo reale, i computer usano ricette speciali chiamate "Generatori di Numeri Pseudo-Casuali" (PRNG) per creare numeri che sembrano completamente casuali a noi, come il rimescolamento di un mazzo di carte o l'interferenza su una vecchia TV. Ma per il computer, questi numeri non sono affatto casuali; seguono una regola matematica rigorosa e nascosta. Se conosci la regola e il numero iniziale, puoi prevedere perfettamente l'intero futuro della sequenza.

Per molto tempo, gli scienziati si sono chiesti: può l'IA moderna, specificamente un tipo di modello chiamato "Transformer" (lo stesso tipo di cervello dietro molti chatbot e generatori di immagini), scoprire queste regole nascoste guardando solo degli esempi? È come chiedere se uno studente può imparare il codice segreto di una serratura semplicemente guardando qualcuno che la apre alcune volte, senza mai essere stato istruito su come funziona la serratura. Questo è un grande affare perché questi generatori di numeri sono la spina dorsale della sicurezza informatica. Se l'IA può scardinarli troppo facilmente, potrebbe significare che i nostri lucchetti digitali non sono sicuri come pensiamo. Ma se l'IA non riesce a scardinarli, ci dice qualcosa di profondo su come questi modelli apprendono i pattern e dove risiedono i loro limiti.

La storia del paper: Scardinare il codice con un colpo di scena

In questo articolo, gli autori hanno impostato una sfida per i Transformer utilizzando una famiglia specifica e difficile di generatori di numeri chiamati "Permuted Congruential Generators" (PCG). Pensa a un generatore di numeri standard come a una macchina semplice che aggiunge e moltiplica numeri per ottenere il successivo. Un PCG è quella stessa macchina, ma con un colpo di scena: prima di mostrarti il risultato, rimescola i bit (i minuscoli 0 e 1 che compongono il numero) usando una serie di spostamenti, inversioni e rotazioni. È come prendere un messaggio segreto, scriverlo e poi rimescolare le lettere in modo che sembri un geroglifico, anche se il messaggio originale era perfettamente logico.

I ricercatori hanno scoperto che i Transformer sono sorprendentemente bravi in questo. Anche quando il computer vede solo un piccolo pezzetto rimescolato dell'output — a volte anche un singolo bit, come un semplice "sì" o "no" — il modello può comunque prevedere il numero successivo con un'alta precisiono. È come se il robot guardasse un singolo pixel di un'immagine rimescolata e sapesse in qualche modo esattamente come appare l'intera immagine. I modelli hanno imparato a farlo senza essere istruiti sulle regole; hanno semplicemente intuito il pattern dai campioni forniti.

Tuttavia, c'è un trucco. Più il puzzle è difficile, più aiuto serve al robot. Gli autori hanno scoperto una "legge di scala": man mano che i numeri diventano più grandi (specificamente, come il modulo, ovvero la dimensione del pool di numeri, cresce), il modello ha bisogno di vedere più esempi di fila per risolvere il puzzle. Se i numeri sono piccoli, il modello ha bisogno di vedere circa 1 im 128 esempi. Se i numeri sono enormi (come $2^{22}$ ), il modello ha bisogno di vedere circa $\sqrt{m}$ esempi, il che significa che la lunghezza del contesto deve crescere significativamente. È come cercare di risolvere un puzzle: se i pezzi sono minuscoli, devi tenerne molti in mano per vedere l'immagine.

La scoperta più eccitante riguardava il modo in cui il modello impara. Quando i ricercatori hanno cercato di addestrare il modello direttamente sui puzzle più grandi e difficili, il modello si è bloccato. Il modello fissava i dati per un lungo periodo, senza fare quasi progressi, come uno studente che fissa un problema di matematica che non capisce. Ma quando hanno usato un "curriculum" — una strategia di insegnamento in cui hanno iniziato il modello con puzzle piccoli e facili, introducendo gradualmente quelli più difficili — il modello ce l'ha fatta improvvisamente. Era come se il modello avesse bisogno di imparare a camminare prima di poter correre. Partendo dal piccolo, il modello ha imparato la "grammatica" di base della generazione dei numeri, e poi ha potuto applicare quella conoscenza ai puzzle giganti e complessi.

Gli autori hanno anche sbirciato dentro il "cervello" del modello (le sue rappresentazioni interne dei dati) e hanno trovato qualcosa di affascinante. Il modello non si è limitato a memorizzare i numeri; li ha organizzati in base alla loro struttura binaria. Ha raggruppato i numeri che avevano pattern simili di zeri e uno, anche se quei numeri sembravano totalmente diversi in superficie. Sembra che il modello abbia scoperto che le regole di "rimescolamento" usate dai generatori trattano certi pattern di bit come se fossero uguali, e ha imparato a rispettare quelle regole. Questo suggerisce che il modello non sta solo tirando a indovinare; sta costruendo una mappa mentale delle simmetrie matematiche nascoste.

In breve, il paper mostra che i Transformer possono imparare a prevedere sequenze numeriche rimescolate complesse, anche quando le informazioni sono pesantemente ridotte. Ma hanno bisogno del percorso di addestramento giusto: iniziare in piccolo e costruire verso l'alto. Sebbene possano superare alcuni vecchi metodi di hacking, incontrano comunque un limite quando i numeri diventano troppo grandi senza quel curriculum d'aiuto. Questo ci dice che, sebbene l'IA stia diventando brava a trovare pattern nascosti, dipende ancora da un modo strutturato di apprendere, proprio come uno studente umano, per affrontare i misteri matematici più difficili.

Sintesi Tecnica: Apprendimento di Numeri Pseudocasuali con i Transformer

Definizione del Problema

Il documento investiga la capacità dei modelli Transformer di apprendere e predire sequenze generate da Generatori Congruenziali Permutati (PCG), una famiglia ampiamente utilizzata di generatori di numeri pseudo-casuali (PRNG). Sebbene i Transformer abbiano dimostrato successo nell'apprendimento in-context (ICL) per vari compiti algoritmici, rimangono domande fondamentali riguardo alla loro capacità di scoprire schemi deterministici nascosti all'interno di dati progettati per superare i test di casualità statistica.

I PCG rappresentano una sfida significativamente più difficile rispetto ai Generatori Congruenziali Lineari (LCG). Mentre gli LCG seguono una semplice ricorrenza lineare ( $s_i = (a s_{i-1} + c) \mod m$ ), i PCG applicano una funzione complessa $f$ allo stato nascosto $s_i$ prima di produrre l'output $x_i$ . Questa funzione coinvolge shift bit a bit, XOR, rotazioni e troncamenti. Tali operazioni sono progettate per oscurare la sottostante struttura lineare, rendendo i PCG resistenti agli attacchi algebrici classici che presuppongono la conoscenza del modulo e del moltiplicatore. Gli autori mirano a determinare se i Transformer possano scoprire queste relazioni di ricorrenza nascoste e le strutture di permutazione senza la conoscenza esplicita dei parametri del generatore, e comprendere i meccanismi e i limiti di tale apprendimento.

Metodologia

Configurazione Sperimentale

Lo studio utilizza un benchmark controllato utilizzando diverse varianti di PCG (XSLRR, XSHRR, XSHRS) e un LCG Troncato (TLCG).

Generatori: Lo stato interno $s_i$ evolve tramite un LCG, e l'output $x_i = f(s_i)$ è derivato attraverso specifiche permutazioni. Gli autori variano il modulo $m$ (da $2^{14}$ a $2^{22}$ ) e la dimensione dell'output (ad esempio, output a 8 bit da stati a 16 bit).
Dataset: Sono impiegate due configurazioni:
1. Separata: Addestramento e test su un singolo tipo di generatore.
2. Combinata: Addestramento e test su un mix di tutti i tipi di generatori, richiedendo al modello di distinguere tra diverse regole di permutazione.
- I dataset consistono in sequenze generate con moltiplicatori ( $a$ ) e incrementi ( $c$ ) non visti per testare la generalizzazione.
Architettura del Modello: Transformer di tipo decoder-only stile GPT con Rotary Positional Embeddings (RoPE). Gli esperimenti scalano la profondità del modello (1–6 layer), la larghezza (teste di attenzione) e la dimensione del vocabolario (basata sulla bit-width dell'output).
Addestramento: I modelli sono addestrati in modo autoregressivo per predire il token successivo utilizzando la perdita di cross-entropy. L'addestramento prevede fino a 100k step con batch size di 512.

Tecniche Chiave

Apprendimento Curriculare (Curriculum Learning): Per moduli grandi ( $m \ge 2^{20}$ ), l'addestramento diretto spesso fallisce, portando a una prolungata stagnazione. Gli autori introducono una strategia di curriculum in cui i dati da moduli più piccoli vengono miscelati nel dataset del modulo più grande. Il rapporto di miscelazione $\alpha$ decade esponenzialmente durante i passi di addestramento.
Inizializzazione Pre-addestrata: Modelli addestrati su moduli più piccoli vengono utilizzati per inizializzare i pesi per compiti con modulo più grande, trasferendo le strutture di embedding apprese.
Analisi di Interpretabilità: Gli autori utilizzano l'Analisi delle Componenti Principali (PCA) sugli embedding dei token e analizzano i pattern di attenzione per comprendere come il modello rappresenti i dati di input.

Contributi Chiave e Risultati

1. Predizione In-Context di Successo

I Transformer possono eseguire con successo la predizione in-context su sequenze PCG da molteplici varianti, generalizzando a parametri non visti ( $a, c$ ).

Performance: I modelli raggiungono una precisione >90% su diverse varianti PCG dopo aver osservato circa 512 elementi in-context.
Robustezza: La predizione rimane robusta anche quando l'output è pesantemente troncato (ad esempio, mantenendo solo il singolo bit più significativo dello stato), dove il modello supera significativamente l'indovinare casuale.
Generalizzazione: Questa capacità eccede gli attacchi classici pubblicati, che tipicamente richiedono la conoscenza pregressa del modulo e del moltiplicatore.

2. Leggi di Scalamento (Scaling Laws)

Il documento identifica una specifica legge di scalamento riguardante la lunghezza del contesto necessaria per una predizione di successo:

Lunghezza del Contesto vs Modulo: Il numero di elementi della sequenza in-context richiesti per superare il 90% di precisione scala come $\sqrt{m}$ . Questa è una crescita più ripida rispetto allo scaling $m^{0.25}$ osservato per gli LCG, riflettendo l'oscuramento delle informazioni introdotto dalle permutazioni PCG.
Dimensione del Modello: Modelli più grandi (aumento di profondità e larghezza) richiedono meno elementi osservati per raggiungere la stessa precisione, suggerendo che la scala permette uno sviluppo di strategie più efficiente.

3. Necessità del Curriculum Learning

Per moduli grandi ( $m \ge 2^{20}$ ), l'addestramento diretto entro budget computazionali fissi risulta in fasi di stagnazione prolungate con una riduzione minima della perdita.

Efficacia del Curriculum: Incorporare dati da moduli più piccoli (ad esempio, miscelando dati $m=2^{16}$ in un addestramento $m=2^{18}$ ) elimina la fase di stagnazione, amplia l'intervallo di tassi di apprendimento stabili e produce una performance finale sostanzialmente più forte.
Pre-addestramento: Inizializzare con i pesi di un modello a modulo più piccolo agisce come una forma discreta di curriculum, permettendo al modello di saltare la fase iniziale di stagnazione e convergere più velocemente.

4. Interpretabilità e Rappresentazione

L'analisi delle rappresentazioni apprese rivela nuovi approfondimenti strutturali:

Clustering Bitwise: La PCA della matrice di embedding mostra che i token si raggruppano spontaneamente in base a strutture bitwise rotazionalmente-invarianti, specificamente il numero e la disposizione di sequenze contigue di zeri (ad esempio, $Z(1)$ , $Z(2,1)$ ).
Trasferibilità: Questa struttura di clustering persiste attraverso diversi moduli, spiegando perché l'inizializzazione pre-addestrata sia efficace; il modello interiorizza le invarianze inerenti al generatore.
Separazione dei Generatori: Nelle configurazioni di addestramento combinato, le attivazioni intermedie del modello (specificamente nel terzo layer MLP) differenziano spontaneamente tra diverse varianti di PRNG, anche senza supervisione esplicita sull'identità del generatore.

Significato e Rivendicazioni

Il documento sostiene che i Transformer possiedano una capacità straordinaria di scoprire schemi deterministici nascosti in dati progettati per apparire casuali, superando le capacità degli attacchi algebrici classici che si basano sulla conoscenza esplicita dei parametri del generatore.

Il lavoro evidenzia come, sebbene i Transformer possano apprendere strutture PRNG complesse, essi affrontino vincoli di scalamento distinti. Il requisito che la lunghezza del contesto cresca come $\sqrt{m}$ e la necessità del curriculum learning per moduli grandi suggeriscono che, sebbene questi modelli possano generalizzare verso regimi non visti, non sono ancora in grado di "rompere" generatori arbitrariamente grandi o complessi senza specifiche strategie di addestramento.

L'identificazione del clustering rotazionalmente-invariante nello spazio di embedding fornisce una spiegazione meccanicistica di come questi modelli generalizzino: apprendono a rappresentare gli input basandosi sulle simmetrie dell'algoritmo sottostante piuttosto che memorizzare sequenze specifiche. Ciò offre una nuova prospettiva su come le reti neurali elaborino compiti di aritmetica modulare e permutazione, colmando il divario tra ragionamento algoritmico e riconoscimento di pattern statistici.

Gli autori concludono che, sebbene i Transformer possano avvicinarsi efficacementamente alla predizione di PRNG non criptografici, un resoconto meccanicistico completo della soluzione e l'esplorazione della loro capacità di attaccare generatori criptograficamente sicuri rimangono direzioni di ricerca importanti per il futuro.