🔬 condensed matter

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

Diese Arbeit zeigt, dass Transformer-Modelle durch Curriculum Learning und durch das Entdecken bitweiser rotationsinvarianter Repräsentationen erfolgreich Sequenzen aus komplexen Permuted Congruential Generatoren (PCGs) lernen und vorhersagen können, wobei sie ein Skalierungsgesetz offenbaren, bei dem die erforderliche Kontextlänge als Quadratwurzel des Modulus wächst.

Ursprüngliche Autoren: Tao Tao, Maissam Barkeshli

Veröffentlicht 2026-07-17

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Tao Tao, Maissam Barkeshli

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

Stellen Sie sich vor, Sie versuchen, einem Roboter beizubringen, die nächste Zahl in einem Zaubertrick vorherzusagen. Sie zeigen ihm eine Sequenz wie 3, 7, 15, 31, und er muss erraten, was als Nächstes kommt. In der realen Welt verwenden Computer spezielle Rezepte, die „Pseudo-Zufallszahlengeneratoren“ (PRNGs) genannt werden, um Zahlen zu erzeugen, die für uns völlig zufällig aussehen, wie das Mischen eines Kartendecks oder das Rauschen auf einem alten Fernseher. Aber für den Computer sind diese Zahlen keineswegs zufällig; sie folgen einer strengen, verborgenen mathematischen Regel. Wenn man die Regel und die Startzahl kennt, kann man die gesamte Zukunft der Sequenz perfekt vorhersagen.

Lange Zeit haben sich Wissenschaftler gefragt: Kann moderne KI, speziell ein Typ von Modell namens „Transformer“ (die gleiche Art von Gehirn hinter vielen Chatbots und Bildgeneratoren), diese verborgenen Regeln allein durch das Betrachten von Beispielen entschlüsseln? Es ist, als würde man fragen, ob ein Schüler den geheimen Code eines Schlosses lernen kann, indem er nur dabei zusieht, wie jemand das Schloss ein paar Mal öffnet, ohne jemals erfahren zu haben, wie das Schloss funktioniert. Das ist eine große Sache, denn diese Zahlengeneratoren sind das Rückgrat der Computersicherheit. Wenn die KI sie zu leicht knacken kann, könnte dies bedealausmachen, dass unsere digitalen Schlösser nicht so sicher sind, wie wir denken. Aber wenn die KI sie nicht knacken kann, sagt uns das etwas Tiefgründiges darüber, wie diese Modelle Muster lernen und wo ihre Grenzen liegen.

Die Geschichte des Papers: Den Code mit einem Twist knacken

In diesem Paper stellen die Autoren eine Herausforderung für Transformer mit einer speziellen, schwierigen Familie von Zahlengeneratoren namens „Permuted Congruential Generators“ (PCGs) auf. Denken Sie an einen Standard-Zahlengenerator als eine einfache Maschine, die Zahlen addiert und multipliziert, um die nächste zu erhalten. Ein PCG ist dieselbe Maschine, aber mit einem Twist: Bevor er das Ergebnis zeigt, verschlüsselt er die Bits (die winzigen 0-en und 1-en, aus denen die Zahl besteht) mithilfe einer Serie von Verschiebungen, Umkehrungen und Rotationen. Es ist, als würde man eine geheime Nachricht nehmen, sie aufschreiben und dann die Buchstaben so durchmischen, dass sie wie Kauderwelsch aussieht, obwohl die ursprüngliche Nachricht vollkommen logisch war.

Die Forscher fanden heraus, dass Transformer überraschend gut darin sind. Selbst wenn der Computer nur ein winziges, verschlüsseltes Stück des Outputs sieht – manchmal nur ein einzelnes Bit, wie ein einfaches „Ja“ oder „Nein“ – kann das Modell immer noch die nächste Zahl mit hoher Genauigkeit vorhersagen. Es ist, als ob der Roboter auf ein einzelnes Pixel eines verschlüsselten Bildes schaut und irgendwie genau weiß, wie das ganze Bild aussieht. Die Modelle lernten dies, ohne die Regeln bekannt zu bekommen; sie haben das Muster einfach aus den bereitgestellten Beispielen erschlossen.

Es gibt jedoch einen Haken. Je schwieriger das Rätsel, desto mehr Hilfe braucht der Roboter. Die Autoren entdeckten ein „Skalierungsgesetz“: Wenn die Zahlen größer werden (speziell, wenn der Modulus, oder die Größe des Zahlenpools, wächst), muss das Modell mehr Beispiele in Folge sehen, um das Rätsel zu lösen. Wenn die Zahlen klein sind, muss das Modell etwa 122 Beispiele sehen. Wenn die Zahlen riesig sind (wie $2^{22}$ ), muss das Modell etwa $\sqrt{m}$ Beispiele sehen, was bedeutet, dass die Kontextlänge signifikant wachsen muss. Es ist wie beim Versuch, ein Jigsaw-Puzzle zu lösen: Wenn die Teile winzig sind, muss man viele von ihnen in der Hand halten, um das Bild zu erkennen.

Die spannendste Entdeckung betraf die Frage, wie das Modell lernt. Als die Forscher versuchten, das Modell direkt auf den schwierigsten, größten Rätseln zu trainieren, blieb es stecken. Das Modell starrte die Daten lange Zeit an, ohne nennenswerte Fortschritte zu machen, wie ein Schüler, der vor einer Matheaufgabe sitzt, die er nicht versteht. Aber als sie ein „Curriculum“ verwendeten – eine Lehrstrategie, bei der sie das Modell mit einfachen, kleinen Rätseln begannen und nach und nach schwierigere einführten –, verstand das Modell es plötzlich. Es war, als müsste das Modell erst laufen lernen, bevor es rennen kann. Durch den einfachen Start lernte das Modell die grundlegende „Grammatik“ der Zahlengenerierung und konnte dieses Wissen dann auf die riesigen, komplexen Rätsel anwenden.

Die Autoren haben auch einen Blick in das „Gehirn“ des Modells (seine internen Datendarstellungen) geworfen und fanden etwas Faszinierendes. Das Modell hat die Zahlen nicht nur auswendig gelernt; es organisierte sie basierend auf ihrer binären Struktur. Es gruppierte Zahlen, die ähnliche Muster von Nullen und Einsen hatten, selbst wenn diese Zahlen oberflächlich betrachtet völlig unterschiedlich aussah. Es scheint, dass das Modell entdeckt hat, dass die „Verschlüsselungsregeln“, die von den Generatoren verwendet werden, bestimmte Bit-Muster als identisch behandeln, und es hat gelernt, diese Regeln zu respektieren. Dies deutet darauf hin, dass das Modell nicht nur rät; es erstellt eine mentale Karte der verborgenen mathematischen Symmetrien.

Kurz gesagt zeigt das Paper, dass Transformer in der Lage sind, komplee, verschlüsselte Zahlensequenzen vorherzusagen, selbst wenn die Informationen stark reduziert sind. Aber sie brauchen den richtigen Lernpfad: klein anfangen und sich steigern. Während sie zwar in der Lage sind, einige altmodische Hacking-Methoden zu übertreffen, stoßen sie dennoch an eine Wand, wenn die Zahlen ohne das hilfreiche Curriculum zu groß werden. Dies zeigt uns, dass KI zwar immer besser darin wird, verborgene Muster zu finden, aber dennoch auf eine strukturierte Art und Weise des Lernens angewiesen ist, ganz ähnlich wie ein menschlicher Schüler, um die schwierigsten mathematischen Mysterien zu lösen.

Technisches Resümee: Lernen pseudozufälliger Zahlen mit Transformern

Problemstellung

Die Arbeit untersucht die Fähigkeit von Transformer-Modellen, Sequenzen zu lernen und vorherzusagen, die von Permuted Congruential Generators (PCGs) generiert werden – einer weit verbreiteten Familie von pseudozufälligen Zahlenzahlengeneratoren (PRNGs). Während Transformer bereits Erfolge beim In-Context-Lernen (ICL) für verschiedene algorithmische Aufgaben gezeigt haben, bleiben grundlegende Fragen hinsichtlich ihrer Kapazität bestehen, verborgene deterministische Muster in Daten zu entdecken, die darauf ausgelegt sind, statistische Randomness-Tests zu bestehen.

PCGs stellen eine signifikant größere Herausforderung dar als Linear Congruential Generators (LCGs). Während LCGs einer einfachen linearen Rekurrenz folgen ( $s_i = (a s_{i-1} + c) \mod m$ ), wenden PCGs eine komplexe Funktion $f$ auf den verborgenen Zustand $s_i$ an, bevor sie $x_i$ ausgeben. Diese Funktion beinhaltet bitweise Verschiebungen, XOR-Operationen, Rotationen und Trunkierungen. Diese Operationen sind darauf ausgelegt, die zugrunde liegende lineare Struktur zu verschleiern, was PCGs resistent gegen klassische algebraische Angriffe macht, die eine Kenntnis des Modulus und des Multiplikators voraussetzen. Die Autoren zielen darauf ab, zu bestimmen, ob Transformer diese verborgenen Rekurrenzrelationen und Permutationsstrukturen ohne explizites Wissen über die Parameter des Generators entdecken können, und um die Mechanismen und Grenzen eines solchen Lernens zu verstehen.

Methodik

Experimenteller Aufbau

Die Studie nutzt ein kontrolliertes Benchmark unter Verwendung mehrerer PCG-Varianten (XSLRR, XSHRR, XSHRS) und eines Truncated LCG (TLCG).

Generatoren: Der interne Zustand $s_i$ entwickelt sich via eines LCG, und der Output $x_i = f(s_i)$ wird durch spezifische Permutationen abgeleitet. Die Autoren variieren den Modulus $m$ (von $2^{14}$ bis $2^{22}$ ) und die Output-Größe (z. B. 8-Bit-Outputs aus 16-Bit-Zuständen).
Datensätze: Es werden zwei Settings verwendet:
1. Separat: Training und Test auf einem einzigen Generator-Typ.
2. Kombiniert: Training und Test auf einer Mischung aller Generator-Typen, was das Modell dazu zwingt, zwischen verschiedenen Permutationsregeln zu unterscheiden.
- Die Datensätze bestehen aus Sequenzen, die mit ungesehenen Multiplikatoren ( $a$ ) und Inkrementen ( $c$ ) generiert wurden, um die Generalisierung zu testen.
Modellarchitektur: GPT-artige Decoder-only Transformer mit Rotary Positional Embeddings (RoPE). Die Experimente skalieren die Modelltiefe (1–6 Schichten), Breite (Attention-Heads) und die Vokabulargröße (basierend auf der Bitbreite des Outputs).
Training: Die Modelle werden autoregressiv trainiert, um das nächste Token unter Verwendung des Cross-Entropy-Loss vorherzusagen. Das Training umfasst bis zu 100k Schritte mit Batch-Größen von 512.

Schlüsseltechniken

Curriculum Learning: Für große Moduli ( $m \ge 2^{20}$ ) scheitert das direkte Training oft und führt zu einer lang anhaltenden Stagnation. Die Autoren führen eine Curriculum-Strategie ein, bei der Trainingsdaten von kleineren Moduli in den Datensatz des größeren Modulus gemischt werden. Das Mischverhältnis $\alpha$ zerfällt exponentiell über die Trainingsschritte.
Pretrained Initialization: Auf kleineren Moduli trainierte Modelle werden verwendet, um die Gewichte für Aufgaben mit größeren Moduli zu initialisieren, wodurch die gelernten Embedding-Strukturen übertragen werden.
Interpretabilitätsanalyse: Die Autoren setzen die Hauptkomponentenanalyse (PCA) auf die Token-Embeddings ein und analysieren Attention-Muster, um zu verstehen, wie das Modell die Eingangsdaten repräsentiert.

Wichtigste Beiträge und Ergebnisse

1. Erfolgreiche In-Context-Vorhersage

Transformer können erfolgreich In-Context-Vorhersagen auf PCG-Sequenzen verschiedener Varianten durchführen und generalisieren dabei auf ungesehene Parameter ( $a, c$ ).

Performance: Modelle erreichen eine Genauigkeit von >90 % bei diversen PCG-Varianten nach der Beobachtung von etwa 512 In-Context-Elementen.
Robustheit: Die Vorhersage bleibt selbst dann robust, wenn der Output stark getrunkiert ist (z. B. wenn nur das höchste Bit des Zustands beibehalten wird), wobei das Modell die Rate des zufälligen Ratens signifikant übertrifft.
Generalisierung: Diese Fähigkeit übertrifft veröffentlichte klassische Angriffe, die typischerweise Vorabwissen über den Modulus und den Multiplikator erfordern.

2. Skalierungsgesetze (Scaling Laws)

Das Paper identifiziert ein spezifisches Skalierungsgesetz bezüglich der benötigten Kontextlänge für eine erfolgreiche Vorhersage:

Kontextlänge vs. Modulus: Die Anzahl der In-Context-Sequenzelemente, die benötigt werden, um eine Genauigkeit von 90 % zu überschreiten, skaliert als $\sqrt{m}$ . Dies ist steiler als die $\text{m}^{0,25}$ -Skalierung, die bei LCGs beobachtet wurde, was die durch PCG-Permutationen eingeführte Informationsverschleierung widerspiegelt.
Modellgröße: Größere Modelle (erhöhte Tiefe und Breite) benötigen weniger beobachtete Elemente, um dieselbe Genauigkeit zu erreichen, was darauf hindeutet, dass Skalierung eine effizientere Strategieentwicklung ermöglicht.

3. Notwendigkeit von Curriculum Learning

Für große Moduli ( $m \ge 2^{20}$ ) führt das direkte Training innerhalb fester Rechenbudgets zu ausgedehnten Stagnationsphasen mit minimaler Reduktion des Loss.

Effektivität des Curriculums: Die Einbeziehung von Daten aus kleineren Moduli (z. B. das Mischen von $m=2^{16}$ Daten in ein $m=2^{18}$ Training) eliminiert die Stagnationsphase, erweitert den Bereich stabiler Lernraten und liefert eine wesentlich stärkere finale Performance.
Pretraining: Die Initialisierung mit Gewichten eines Modells mit kleinerem Modulus fungiert als diskrete Form des Curriculums, die es dem Modell ermöglicht, die initiale Stagnationsphase zu überspringen und schneller zu konvergieren.

4. Interpretierbarkeit und Repräsentation

Die Analyse der gelernten Repräsentationen liefert neue strukturelle Erkenntnisse:

Bitweise Clusterbildung: Die PCA der Embedding-Matrix zeigt, dass Token spontan basierend auf bitweisen rotationsinvarianten Strukturen clustern, spezifisch nach der Anzahl und Anordnung zusammenhängender Null-Runs (z. B. $Z(1), Z(2,1)$ ).
Übertragbarkeit: Diese Clustering-Struktur bleibt über verschiedene Moduli hinweg bestehen, was erklärt, warum die Pretrained-Initialisierung effektiv ist; das Modell internalisiert die dem Generator inhärenten Invarianzen.
Generator-Trennung: In kombinierten Trainingssettings differenzieren die intermediären Aktivierungen des Modells (speziell im MLP der dritten Schicht) spontan zwischen verschiedenen PRNG-Varianten, selbst ohne explizite Überwachung der Generator-Identität.

Bedeutung und Behauptungen

Das Paper behauptet zu zeigen, dass Transformer über eine bemerkenswerte Fähigkeit verfügen, verborgene deterministische Muster in Daten zu entdecken, die darauf ausgelegt sind, zufällig zu erscheinen, und dabei klassische algebraische Angriffe übertreffen, die auf explizitem Wissen über die Parameter des Generators beruhen.

Die Arbeit hebt hervor, dass Transformer zwar komplexe PRNG-Strukturen lernen können, aber mit distinkten Skalierungsbeschränkungen konfrontiert sind. Die Anforderung, dass die Kontextlänge als $\sqrt{m}$ mit dem Modulus wachsen muss, sowie die Notwendigkeit von Curriculum Learning für große Moduli legen nahe, dass diese Modelle zwar in der Lage sind, auf ungesehene Regime zu generalisieren, aber noch nicht in der Lage sind, beliebig große oder komplexe Generatoren ohne spezifische Trainingsstrategien zu "knacken".

Die Identifizierung der rotationsinvarianten Clusterbildung im Embedding-Raum liefert eine mechanistische Erklärung dafür, wie diese Modelle generalisieren: Sie lernen, Inputs basierend auf den Symmetrien des zugrunde liegenden Algorithmus zu repräsentieren, anstatt spezifische Sequenzen auswendig zu lernen. Dies bietet eine neue Perspektive darauf, wie neuronale Netze modulare Arithmetik und permutationsbasierte Aufgaben verarbeiten, und schlägt die Brücke zwischen algorithmischer Argumentation und statistischer Mustererkennung.

Die Autoren kommen zu dem Schluss, dass, während Transformer nicht-kryptographische PRNGs effektiv angreifen können, eine vollständige mechanistische Erklärung der Lösung und die Untersuchung ihrer Fähigkeit, kryptographisch sichere Generatoren anzugreifen, wichtige zukünftige Forschungsrichtungen bleiben.