🔬 condensed matter

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

Cet article démontre que les modèles Transformer peuvent apprendre et prédire avec succès des séquences issues de générateurs de congruences permutés (PCG) complexes grâce à l'apprentissage curriculaire et en découvrant des représentations invariantes par rotation bit à bit, révélant une loi d'échelle où la longueur de contexte requise croît selon la racine carrée du modulo.

Auteurs originaux : Tao Tao, Maissam Barkeshli

Publié 2026-07-17

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Tao Tao, Maissam Barkeshli

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez d'apprendre à un robot à prédire le nombre suivant dans un tour de magie. Vous lui présentez une séquence comme 3, 7, 15, 31, et il doit deviner ce qui vient ensuite. Dans le monde réel, les ordinateurs utilisent des recettes spéciales appelées « Générateurs de Nombres Pseudo-Aléatoires » (PRNG) pour créer des nombres qui semblent totalement aléatoires pour nous, comme le mélange d'un jeu de cartes ou la neige sur une vieille télévision. Mais pour l'ordinateur, ces nombres ne sont pas du tout aléatoires ; ils suivent une règle mathématique stricte et cachée. Si vous connaissez la règle et le nombre de départ, vous pouvez prédire parfaitement tout le futur de la séquence.

Pendant longtemps, les scientifiques se sont demandé : les IA modernes, et plus précisément un type de modèle appelé « Transformer » (le même genre de cerveau derrière de nombreux chatbots et générateurs d'images), peuvent-elles déchiffrer ces règles cachées simplement en observant des exemples ? C'est comme demander si un étudiant peut apprendre le code secret d'une serrure simplement en regardant quelqu'un l'ouvrir quelques fois, sans jamais lui avoir expliqué comment la serrure fonctionne. C'est un enjeu majeur car ces générateurs de nombres sont le pilier de la sécurité informatique. Si l'IA peut les percer trop facilement, cela pourrait signifier que nos verrous numériques ne sont pas aussi sûrs que nous le pensons. Mais si l'IA ne peut pas les percer, cela nous apprend quelque chose de profond sur la façon dont ces modèles apprennent les motifs et sur l'étendue de leurs limites.

L'histoire de l'article : Percer le code avec un tour de passe-passe

Dans cet article, les auteurs ont lancé un défi aux Transformers en utilisant une famille de générateurs de nombres particulièrement difficiles appelée « Générateurs Congruentiels Permutés » (PCG). Imaginez un générateur de nombres standard comme une machine simple qui ajoute et multiplie des nombres pour obtenir le suivant. Un PCG est cette même machine, mais avec un tour de passe-passe : avant de vous montrer le résultat, il brouille les bits (les minuscules 0 et 1 qui composent le nombre) en utilisant une série de décalages, de basculements et de rotations. C'est comme prendre un message secret, l'écrire, puis mélanger les lettres pour qu'il ressemble à du charabia, même si le message original était parfaitement logique.

Les chercheurs ont découvert que les Transformers sont étonnamment doués pour cela. Même lorsque l'ordinateur ne voit qu'un minuscule fragment brouillé de la sortie — parfois juste un seul bit, comme un simple « oui » ou « non » — le modèle peut encore prédire le nombre suivant avec une grande précision. C'est comme si le robot regardait un seul pixel d'une image brouillée et parvenait, d'une manière ou d'une autre, à savoir exactement à quoi ressemble l'image entière. Les modèles ont appris à faire cela sans qu'on leur donne les règles ; ils ont simplement déduit le motif à partir des exemples fournis.

Cependant, il y a un bémol. Plus le puzzle est difficile, plus le robot a besoin d'aide. Les auteurs ont découvert une « loi d'échelle » : à mesure que les nombres deviennent plus grands (plus précisément, lorsque le module, ou la taille de l'ensemble de nombres, augmente), le modèle doit voir plus d'exemples consécutifs pour résoudre l'énigme. Si les nombres sont petits, le modèle a besoin de voir environ 128 exemples. S'ils sont énormes (comme $2^{22}$ ), le modèle a besoin de voir environ $\sqrt{m}$ exemples, ce qui signifie que la longueur du contexte doit augmenter considérablement. C'est comme essayer de résoudre un puzzle : si les pièces sont minuscules, vous devez en tenir beaucoup dans votre main pour voir l'image.

La découverte la plus excitante concerne la manière dont le modèle apprend. Lorsque les chercheurs ont essayé d'entraîner le modèle directement sur les puzzles les plus difficiles et les plus grands, celui-ci s'est bloqué. Le modèle restait là à fixer les données pendant un long moment, sans faire presque aucun progrès, comme un étudiant fixant un problème de mathématiques qu'il ne comprend pas. Mais lorsqu'ils ont utilisé un « curriculum » — une stratégie d'enseignement consistant à faire commencer le modèle sur des puzzles faciles et petits, pour introduire progressivement des puzzles plus difficiles — le modèle a soudainement réussi. C'était comme si le modèle avait besoin d'apprendre à marcher avant de pouvoir courir. En commençant petit, le modèle a appris la « grammaire » de la génération de nombres, puis il a pu appliquer ces connaissances aux puzzles géants et complexes.

Les auteurs ont également jeté un coup d'œil à l'intérieur du « cerveau » du modèle (ses représentations de données internes) et ont trouvé quelque chose de fascinant. Le modèle n'a pas seulement mémorisé les nombres ; il les a organisés en fonction de leur structure binaire. Il a regroupé les nombres qui présentaient des motifs de zéros et de uns similaires, même si ces nombres paraissaient totalement différents en surface. Il semble que le modèle ait découvert que les règles de « brouillage » utilisées par les générateurs traitent certains motifs de bits comme étant identiques, et il a appris à respecter ces règles. Cela suggère que le modèle ne se contente pas de deviner ; il construit une carte mentale des symétries mathématiques cachées.

En résumé, l'article montre que les Transformers peuvent apprendre à prédire des séquences de nombres complexes et brouillées, même lorsque l'information est fortement réduite. Mais ils ont besoin du bon parcours d'apprentissage : commencer petit et progresser par étapes. Bien qu'ils puissent surpasser certaines anciennes méthodes de piratage, ils se heurtent toujours à un mur lorsque les nombres deviennent trop grands sans ce curriculum d'aide. Cela nous indique que, même si l'IA devient meilleure pour trouver des motifs cachés, elle dépend toujours d'une manière d'apprentissage structurée, tout comme un étudiant humain, pour s'attaquer aux mystères mathématiques les plus difficiles.

Résumé technique : Apprentissage des nombres pseudo-aléatoires avec les Transformers

Énoncé du problème

L'article étudie la capacité des modèles Transformer à apprendre et à prédire des séquences générées par des Générateurs de Congruence Permutés (PCG), une famille de générateurs de nombres pseudo-aléatoires (PRNG) largement utilisée. Bien que les Transformers aient démontré un succès dans l'apprentissage en contexte (ICL) pour diverses tâches algorithmiques, des questions fondamentales subsistent quant à leur capacité à découvrir des motifs déterministes cachés au sein de données conçues pour réussir des tests de randomité statistique.

Les PCG présentent un défi nettement plus complexe que les Générateurs de Congruence Linéaire (LCG). Alors que les LCG suivent une récurrence linéaire simple ( $s_i = (a s_{i-1} + c) \mod m$ ), les PCG appliquent une fonction $f$ complexe à l'état caché $s_i$ avant de produire $x_i$ . Cette fonction implique des décalages de bits (shifts), des opérations XOR, des rotations et des troncatures. Ces opérations sont conçues pour obscurcir la structure linéaire sous-jacente, rendant les PCG résistants aux attaques algébriques classiques qui supposent la connaissance du module et du multiplicateur. Les auteurs visent à déterminer si les Transformers peuvent découvrir ces relations de récurrence cachées et ces structures de permutation sans connaissance explicite des paramètres du générateur, et à comprendre les mécanismes et les limites d'un tel apprentissage.

Méthodologie

Configuration expérimentale

L'étude utilise un benchmark contrôlé utilisant plusieurs variantes de PCG (XSLRR, XSHRR, XSHRS) et un LCG tronqué (TLCG).

Générateurs : L'état interne $s_i$ évolue via un LCG, et la sortie $x_i = f(s_i)$ est dérivée par des permutations spécifiques. Les auteurs font varier le module $m$ (de $2^{14}$ à $2^{22}$ ) et la taille de la sortie (par exemple, des sorties de 8 bits à partir d'états de 16 bits).
Jeux de données : Deux configurations sont employées :
1. Séparée : Entraînement et test sur un seul type de générateur.
2. Combinée : Entraînement et test sur un mélange de tous les types de générateurs, nécessitant au modèle de distinguer entre différentes règles de permutation.
- Les jeux de données consistent en des séquences générées avec des multiplicateurs ( $a$ ) et des incréments ( $c$ ) non vus pour tester la généralisation.
Architecture du modèle : Transformers de type décodeur uniquement (style GPT) avec des plongements de position rotatifs (RoPE). Les expériences font varier la profondeur du modèle (1–6 couches), la largeur (têtes d'attention) et la taille du vocabulaire (basée sur la largeur de bit de sortie).
Entraînement : Les modèles sont entraînés de manière autorégressive pour prédire le jeton suivant en utilisant une perte d'entropie croisée (cross-entropy). L'entraînement implique jusqu'à 100 000 étapes avec des tailles de lots de 512.

Techniques clés

Apprentissage par curriculum (Curriculum Learning) : Pour les grands modules ( $m \ge 2^{20}$ ), l'entraînement direct échoue souvent, menant à une stagnation prolongée. Les auteurs introduisent une stratégie de curriculum où les données provenant de modules plus petits sont mélangées au jeu de données du module plus grand. Le ratio de mélange $\alpha$ décroît exponentiellement au cours des étapes d'entraînement.
Initialisation pré-entraînée : Des modèles entraînés sur de plus petits modules sont utilisés pour initialiser les poids pour des tâches à module plus grand, transférant ainsi les structures de plongement apprises.
Analyse d'interprétabilité : Les auteurs utilisent l'Analyse en Composantes Principales (PCA) sur les plongements de jetons (token embeddings) et analysent les motifs d'attention pour comprendre comment le modèle représente les données d'entrée.

Contributions clés et résultats

1. Prédiction réussie en contexte

Les Transformers peuvent effectuer avec succès la prédiction en contexte sur des séquences PCG de plusieurs variantes, se généralisant à des paramètres non vus ( $a, c$ ).

Performance : Les modèles atteignent plus de 90 % de précision sur diverses variantes de PCG après avoir observé environ 512 éléments en contexte.
Robustesse : La prédiction reste robuste même lorsque la sortie est fortement tronquée (par exemple, en ne conservant que le bit le plus élevé de l'état), là où le modèle surpasse significativement le hasard.
Généralisation : Cette capacité dépasse les attaques classiques publiées, qui nécessitent généralement une connaissance préalable du module et du multiplicateur.

2. Lois d'échelle (Scaling Laws)

L'article identifie une loi d'échelle spécifique concernant la longueur du contexte requise pour une prédiction réussie :

Longueur du contexte vs Module : Le nombre d'éléments de séquence en contexte requis pour dépasser 90 % de précision suit une échelle de $\sqrt{m}$ . C'est une progression plus raide que l'échelle $m^{0.25}$ observée pour les LCG, reflétant l'obscurcissement de l'information introduit par les permutations PCG.
Taille du modèle : Les modèles plus grands (augmentation de la profondeur et de la largeur) nécessitent moins d'éléments observés pour atteindre la même précision, suggérant que l'échelle permet un développement de stratégie plus efficace.

3. Nécessité de l'apprentissage par curriculum

Pour les grands modules ( $m \ge 2^{20}$ ), l'entraînement direct dans des budgets de calcul fixes résulte en des phases de stagnation prolongées avec une réduction minimale de la perte.

Efficacité du curriculum : L'incorporation de données provenant de modules plus petits (par exemple, mélanger des données de $m=2^{16}$ dans un entraînement de $m=2^{18}$ ) élimine la phase de stagnation, élargit la plage de taux d'apprentissage stables et produit une performance finale nettement plus forte.
Pré-entraînement : L'initialisation avec les poids d'un modèle de module plus petit agit comme une forme discrète de curriculum, permettant au modèle de sauter la phase de stagnation initiale et de converger plus rapidement.

4. Interprétabilité et représentation

L'analyse des représentations apprises révèle de nouvelles intuitions structurelles :

Clustering bit à bit (Bitwise Clustering) : La PCA de la matrice d'embedding montre que les jetons se regroupent spontanément selon des structures invariantes par rotation bit à bit, spécifiquement le nombre et l'arrangement des suites de zéros contigus (ex: $Z(1)$ , $Z(2,1)$ ).
Transférabilité : Cette structure de clustering persiste à travers différents modules, expliquant pourquoi l'initialisation pré-entraînée est efficace ; le modèle intériorise les invariances inhérentes au générateur.
Séparation des générateurs : Dans les configurations d'entraînement combinées, les activations intermédiaires du modèle (spécifiquement dans le MLP de la troisième couche) différencient spontanément les distinctes variantes de PRNG, même sans supervision explicite sur l'identité du générateur.

Signification et affirmations

L'article affirme que les Transformers possèdent une capacité remarquable à découvrir des motifs déterministes cachés dans des données conçues pour paraître aléatoires, surpassant les capacités des attaques algébriques classiques qui reposent sur une connaissance explicite des paramètres du générateur.

Ce travail souligne que, bien que les Transformers puissent apprendre des structures de PRNG complexes, ils font face à des contraintes de mise à l'échelle distinctes. L'exigence que la longueur du contexte croisse selon $\sqrt{m}$ et la nécessité d'un apprentissage par curriculum pour les grands modules suggèrent que, bien que ces modèles puissent se généraliser à des régimes non vus, ils ne sont pas encore capables de "casser" des générateurs arbitrairement grands ou complexes sans stratégies d'entraînement spécifiques.

L'identification du clustering invariant par rotation dans l'espace d'embedding fournit une explication mécaniste de la manière dont ces modèles se généralisent : ils apprennent à représenter les entrées basées sur les symétries de l'algorithme sous-jacent plutôt qu'en mémorisant des séquences spécifiques. Cela offre une nouvelle perspective sur la façon dont les réseaux de neurones traitent l'arithmétique modulaire et les tâches de permutation, comblant le fossé entre le raisonnement algorithmique et la reconnaissance de motifs statistiques.

Les auteurs concluent que, bien que les Transformers puissent approcher efficacement la prédiction de PRNG non cryptographiques, un compte rendu mécaniste complet de la solution et l'exploration de leur capacité à attaquer des générateurs cryptographiquement sécurisés restent des directions de travail importantes pour l'avenir.