🔬 condensed matter

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

Dit artikel toont aan dat Transformer-modellen succesvol sequenties van complexe Permuted Congruential Generators (PCG's) kunnen leren en voorspellen door middel van curriculum learning en door het ontdekken van bitwise rotationeel-invariante representaties, wat een schaalwet onthult waarbij de vereiste contextlengte groeit als de wortel van het modulus.

Oorspronkelijke auteurs: Tao Tao, Maissam Barkeshli

Gepubliceerd 2026-07-17

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Tao Tao, Maissam Barkeshli

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een robot probeert te leren het volgende getal in een goocheltruc te voorspellen. Je laat het een reeks zien zoals 3, 7, 15, 31, en het moet raden wat er daarna komt. In de echte wereld gebruiken computers speciale recepten die "Pseudo-Random Number Generators" (PRNG's) worden genoemd om getallen te creëren die voor ons volkomen willekeurig lijken, zoals het schudden van een kaartspel of de ruis op een oude tv. Maar voor de computer zijn deze getallen helemaal niet willekeurig; ze volgen een strikte, verborgen wiskundige regel. Als je de regel en het begingetal kent, kun je de hele toekomst van de reeks perfect voorspellen.

Al een lange tijd vragen wetenschappers zich af: kan moderne AI, specif으로 een type model dat een "Transformer" wordt genoemd (hetzelfde soort brein achter veel chatbots en beeldgeneratoren), deze verborgen regels ontdekken door alleen naar voorbeelden te kijken? Het is alsof je vraagt of een student de geheime code van een slot kan leren door simpelweg toe te kijken hoe iemand het slot een paar keer opent, zonder dat de student ooit verteld krijgt hoe het slot werkt. Dit is een groot ding, want deze getallengeneratoren vormen de ruggacht van computerbeveiliging. Als AI deze te gemakkelijk kan kraken, zou dit kunnen betekenen dat onze digitale sloten niet zo veilig zijn als we denken. Maar als AI ze niet kan kraken, vertelt dat ons iets diepzinnigs over hoe deze modellen patronen leren en waar hun grenzen liggen.

Het verhaal van het artikel: De code kraken met een twist

In dit artikel zetten de auteurs een uitdaging op voor Transformers met behulp van een specifieke, moeilijke familie van getallengeneratoren genaamd "Permuted Congruential Generators" (PCG's). Denk aan een standaard getallengenerator als een eenvoudige machine die getallen optelt en vermenigvuldigt om het volgende getal te krijgen. Een PCG is diezelfde machine, maar dan met een twist: voordat de machine het resultaat aan je laat zien, husselt hij de bits (de kleine 0'tjes en 1'tjes waaruit het getal bestaat) met behulp van een reeks verschuivingen, flips en rotaties. Het is alsof je een geheim bericht neemt, het opschrijft, en dan de letters door elkaar husselt zodat het op wartaal lijkt, ook al was het oorspronkelijke bericht volkomen logisch.

De onderzoekers ontdekten dat Transformers verrassend goed zijn in dit. Zelfs wanneer de computer slechts een minuscuul, gehusseld stukje van de output ziet—soms zelfs maar een enkele bit, zoals een simpel "ja" of "nee"—kan het model nog steeds het volgende getal met een hoge nauwkeurigheid voorspellen. Het is alsof de robot naar een enkele pixel van een gehusselde afbeelding kijkt en op de een of andere manier precies weet hoe het hele plaatje eruitziet. De modellen leerden dit te doen zonder dat ze de regels werden verteld; ze ontdekten gewoon het patroon aan de hand van de verstrekte voorbeelden.

Er is echter een addertje onder het gras. Hoe moeilijker de puzzel, hoe meer hulp de robot nodig heeft. De auteurs ontdekten een "schaalwet": naarmate de getallen groter worden (specifiek, naarmate de modulus, of de grootte van de getallenpool, groeit), heeft het model meer opeenvolgende voorbeelden nodig om de puzzel op te lossen. Als de getallen klein zijn, moet het model ongeveer 128 voorbeelden zien. Als de getallen enorm zijn (zoals $2^{22}$ ), moet het model ongeveer $\sqrt{m}$ voorbeelden zien, wat betekent dat de contextlengte aanzienlijk moet groeien. Het is als het proberen op te lossen van een legpuzzel: als de stukjes minuscuul zijn, moet je er veel in je hand houden om de afbeelding te kunnen zien.

De meest opwindende ontdekking ging over hoe het model leert. Wanneer de onderzoekers probeerden het model direct te trainen op de moeilijkste, grootste puzzels, liep het vast. Het model staarde naar de data voor een lange tijd, zonder bijna enige vooruitgang te boeken, zoals een student die naar een wiskundig probleem staart dat hij niet begrijpt. Maar wanneer ze een "curriculum" gebruikten—een onderwijsstrategie waarbij ze het model begonnen met gemakkelijke, kleine puzzels en geleidelijk moeilijker werd—begreep het model het plotseling. Het was alsof het model moest leren lopen voordat het kon rennen. Door klein te beginnen, leerde het model de basis "grammatica" van de getallengeneratie, en kon het vervolgens die kennis toepassen op de gigantische, complexe puzzels.

De auteurs hebben ook in het "brein" van het model gekeken (de interne datarepresentaties) en vonden iets fascinerends. Het model heeft de getallen niet alleen uit het hoofd geleerd; het heeft ze georganiseerd op basis van hun binaire structuur. Het groepeerde getallen die vergelijkbare patronen van nullen en enen hadden, zelfs als die getallen er aan de oppervlakte totaal verschillend uitzagen. Het lijkt erop dat het model ontdekte dat de "husselregels" die door de generatoren worden gebruikt, bepaalde bitpatronen als hetzelfde behandelen, en het heeft geleerd deze regels te respecteren. Dit suggereert dat het model niet alleen gokt; het bouwt een mentale kaart van de verborgen wiskundige symmetrieën.

Kortom, het artikel laat zien dat Transformers complexe, gehusselde getallenreeksen kunnen leren voorspellen, zelfs wanneer de informatie sterk is teruggebracht. Maar ze hebben het juiste leertraject nodig: klein beginnen en opbouwen. Hoewel ze sommige oude hackmethoden kunnen overtreffen, lopen ze nog steeds tegen een muur aan wanneer de getallen te groot worden zonder dat dat behulpzame curriculum. Dit vertelt ons dat hoewel AI beter wordt in het vinden van verborgen patronen, het nog steeds vertrouwt op een gestructureerde manier van leren, net als een menselijke student, om de meest moeilijke wiskundige mysteries aan te pakken.

Technische Samenvatting: Het leren van pseudowillekeurige getallen met Transformers

Probleemstelling

Het artikel onderzoekt het vermogen van Transformer-modellen om sequenties te leren en te voorspellen die worden gegenereerd door Permuted Congruential Generators (PCGs), een breed gebruikte familie van pseudowillekeurige getallengeneratoren (PRNG's). Hoewel Transformers succes hebben getoond bij in-context leren (ICL) voor diverse algoritmische taken, blijven fundamentele vragen bestaan over hun capaciteit om verborgen deterministische patronen te ontdekken in data die ontworpen zijn om statistische willekeurigheidstests te doorstaan.

PCG's vormen een aanzienlijk grotere uitdaging dan Linear Congruential Generators (LCGs). Terwijl LCG's een eenvoudige lineaire recursie volgen ( $s_i = (a s_{i-1} + c) \mod m$ ), passen PCG's een complexe functie $f$ toe op de verborgen staat $s_i$ voordat ze $x_i$ produceren. Deze functie omvat bitwise verschuivingen, XOR-operaties, rotaties en afkapoperaties (truncations). Deze operaties zijn ontworpen om de onderliggende lineaire structuur te verhullen, waardoor PCG's resistent zijn tegen klassieke algebraïsche aanvallen die uitgaan van kennis van de modulus en de multiplier. De auteurs beogen te bepalen of Transformers deze verborgen recursieve relaties en permutatiestructuren kunnen ontdekken zonder expliciete kennis van de parameters van de generator, en om de mechanismen en beperkingen van dergelend leren te begrijpen.

Methodologie

Experimentele Opzet

De studie maakt gebruik van een gecontroleerde benchmark met verschillende PCG-varianten (XSLRR, XSHRR, XSHRS) en een Truncated LCG (TLCG).

Generatoren: De interne staat $s_i$ evolueert via een LCG, en de output $x_i = f(s_i)$ wordt afgeleid via specifieke permutaties. De auteurs variëren de modulus $m$ (van $2^{14}$ tot $2^{22}$ ) en de outputgrootte (bijv. 8-bit outputs van 16-bit staten).
Datasets: Twee settings worden gehanteerd:
1. Gescheiden (Separate): Trainen en testen op een enkel type generator.
2. Gecombineerd (Combined): Trainen en testen op een mix van alle generatortypes, wat vereist dat het model tussen verschillende permutatieregels onderscheid maakt.
- Datasets bestaan uit sequenties gegenereerd met niet-geziene multipliers ( $a$ ) en incrementen ( $c$ ) om generalisatie te testen.
Modelarchitectuur: GPT-stijl decoder-only Transformers met Rotary Positional Embeddings (RoPE). Experimenten schalen de modeldiepte (1–6 lagen), breedte (attention heads) en vocabulairegrootte (gebaseerd op de bitbreedte van de output).
Training: Modellen worden autoregressief getraind om het volgende token te voorspellen met behulp van cross-entropy loss. De training omvat tot 100k stappen met batchgroottes van 512.

Kerntechnieken

Curriculum Learning: Voor grote moduli ( $m \ge 2^{20}$ ) faalt directe training vaak, wat leidt tot langdurige stagnatie. De auteurs introduceren een curriculumstrategie waarbij trainingsdata van kleinere moduli wordt gemengd in de dataset van de grotere modulus. De mengverhouding $\alpha$ neemt exponentieel af gedurende de trainingsstappen.
Pretrained Initialisatie: Modellen getraind op kleinere moduli worden gebruikt om de gewichten voor taken met een grotere modulus te initialiseren, waarbij de geleerde embedding-structuren worden overgedragen.
Interpretabiliteitsanalyse: De auteurs gebruiken Principal Component Analysis (PCA) op token-embeddings en analyseren attention-patronen om te begrijpen hoe het model de inputdata representeert.

Belangrijkste Bijdragen en Resultaten

1. Succesvolle In-Context Voorspelling

Transformers kunnen succesvol in-context voorspellingen uitvoeren op PCG-sequenties van meerdere varianten, waarbij ze generaliseren naar ongeziene parameters ( $a, c$ ).

Prestaties: Modellen bereiken >90% nauwkeurigheid op diverse PCG-varianten na het observeren van ongeveer 512 in-context elementen.
Robuustheid: Voorspelling blijft robuust, zelfs wanneer de output zwaar is afgekapt (bijv. het behouden van slechts de hoogste bit van de staat), waarbij het model aanzienlijk beter presteert dan willekeurig gokken.
Generalisatie: Deze capaciteit overtreft gepubliceerde klassieke aanvallen, die doorgaans voorkennis van de modulus en de multiplier vereisen.

2. Schalingswetten (Scaling Laws)

Het artikel identificeert een specifieke schalingswet met betrekking tot de contextlengte die vereist is voor succesvolle voorspelling:

Contextlengte vs. Modulus: Het aantal in-context sequentie-elementen dat nodig is om 90% nauwkeurigheid te overschrijden, schaalt als $\sqrt{m}$ . Dit is steiler dan de $m^{0.25}$ schaling die wordt waargenomen bij LCG's, wat de door permutaties geïntroduceerde informatie-obscuratie weerspiegelt.
Modelgrootte: Grotere modellen (verhoogde diepte en breedte) hebben minder geobserveerde elementen nodig om dezelfde nauwkeurigheid te bereiken, wat suggereert dat schaal toestaat dat er efficiëntere strategieën worden ontwikkeld.

3. Noodzaak van Curriculum Learning

Voor grote moduli ( $m \ge 2^{20}$ ) resulteert directe training binnen vaste rekenbudgetten in uitgebreide stagnatiefases met minimale reductie van de loss.

Effectiviteit van Curriculum: Het integreren van data van kleinere moduli (bijv. het mengen van $m=2^{16}$ data in een $m=2^{18}$ training) elimineert de stagnatiefase, vergroot het bereik van stabiele leersnelheden en levert substantieel sterkere uiteindelijke prestaties op.
Pretraining: Initialiseren met gewichten van een model met een kleinere modulus werkt als een discrete vorm van curriculum, waardoor het model de initiële stagnatiefase kan overslaan en sneller kan convergeren.

4. Interpretabiliteit en Representatie

Analyse van de geleerde representaties onthult nieuwe structurele inzichten:

Bitwise Clustering: PCA van de embedding-matrix laat zien dat tokens spontaan clusteren op basis van bitwise rotationeel-invariante structuren, specifiek het aantal en de ordening van aaneengesloten nul-runs (bijv. $Z(1)$ , $Z(2,1)$ ).
Transferbaarheid: Deze clusteringstructuur blijft bestaan over verschillende moduli, wat verklaart waarom pretrained initialisatie effectief is; het model internaliseert de invarianties die inherent zijn aan de generator.
Scheiding van Generatoren: In gecombineerde trainingssettings differentiëren de intermediaire activaties van het model (specifiek in de derde laag van de MLP) zich spontaan tussen verschillende PRNG-varianten, zelfs zonder expliciete supervisie op de identiteit van de generator.

Betekenis en Claims

Het artikel claimt aan te tonen dat Transformers beschikken over een opmerkelijk vermogen om verborgen deterministische patronen te ontdekken in data die ontworpen zijn om willekeurig te lijken, waarbij ze de capaciteiten van klassieke algebraïsche aanvallen die vertrouwen op expliciete kennis van generatorparameters overtreffen.

Het werk benadrukt dat hoewel Transformers complexe PRNG-structuren kunnen leren, ze te maken hebben met specifieke schalingsbeperkingen. Het vereiste dat de contextlengte groeit als $\sqrt{m}$ en de noodzaak van curriculum learning voor grote moduli suggereren dat, hoewel deze modellen kunnen generaliseren naar ongeziene regimes, ze nog niet in staat zijn om willekeurig grote of complexe generatoren te "kraken" zonder specifieke trainingsstrategieën.

De identificatie van rotationeel-invariante clustering in de embedding-ruimte biedt een mechanistische verklaring voor hoe deze modellen generaliseren: ze leren de input te representeren op basis van de symmetrieën van het onderliggende algoritme in plaats van specifieke sequenties te memoriseren. Dit biedt een nieuw perspectief op hoe neurale netwerken modulaire rekenkunde en permutatie-gebaseerde taken verwerken, en overbrugt de kloof tussen algoritmisch redeneren en statistische patroonherkenning.

De auteurs concluderen dat hoewel Transformers effectief de voorspelling van niet-cryptografische PRNG's kunnen benaderen, een volledige mechanistische verklaring van de oplossing en een exploratie van hun vermogen om cryptografisch veilige generatoren aan te vallen, belangrijke toekomstige richtingen blijven.