Résumé technique : Découverte d'un algorithme de la carte Zeta sur les chemins de Dyck via l'interprétabilité mécaniste

Énoncé du problème

L'apprentissage automatique est de plus en plus appliqué à la recherche mathématique, pourtant un fossé fondamental subsiste entre la prédiction de haute précision et la génération de constructions mathématiques explicites et vérifiables. En combinatoire, le résultat souhaité est souvent une conjecture, une construction ou un algorithme qui peut être vérifié de manière indépendante, plutôt qu'une approximation numérique. Ce document traite de ce fossé en étudiant si les outils d'interprétabilité mécaniste peuvent extraire des algorithmes combinatoires explicites à partir de réseaux de neurones entraînés.

Le cas de test spécifique est la carte zeta ($\zeta$) sur les chemins de Dyck, une bijection classique centrale dans la théorie des nombres catalans $q,t$. La carte zeta échange les statistiques $(dinv, area)$ pour les statistiques $(area, bounce)$. Bien que la carte zeta soit bien comprise et admette plusieurs descriptions algorithmiques existantes (par exemple, via des séquences d'aire ou des cartes de balayage/sweep maps), elle constitue un environnement contrôlé idéal pour la découverte assistée par l'IA car les données sont générables de manière exacte, la correction est vérifiable de façon exhaustive, et la cible est une procédure combinatoire discrète.

Méthodologie

1. Configuration expérimentale

Les auteurs ont entraîné des modèles transformeurs pour apprendre la carte zeta sur des chemins de Dyck de semi-longueur $n$.

• Données : Jeux de données supervisés de mots de Dyck et de leurs images sous la carte zeta (spécifiquement $\text{rev} \circ \zeta$, où $\text{rev}$ désigne la lecture du mot à l'envers et l'inversion des 0 et des 1, conformément à l'implémentation SAGEMATH utilisée).
• Entraînement initial : Des transformeurs encodeur-décodeur standards (4 couches, 8 têtes) ont atteint une précision $>99\%$ sur diverses semi-longueurs ($n=11$ à $16$).
• Compression : Pour permettre l'analyse mécaniste, les auteurs ont entraîné un Transformeur de Dyck Minimal : une architecture délibérément petite avec une seule couche d'encodage, une couche de décodage et une tête d'attention (dimension d'embedding 128, ~340k paramètres). Ce modèle a atteint une précision parfaite ou quasi parfaite.

2. Analyse de l'interprétabilité mécaniste

Le cœur de la méthodologie consiste à analyser le fonctionnement interne du Transformeur de Dyck Minimal en utilisant trois outils principaux :

• Analyse de l'attention croisée du décodeur (Cross-Attention) : Les auteurs ont suivi quelles positions d'entrée recevaient les poids d'attention les plus élevés lors de la génération de la séquence de sortie.
• Ablation causale : Ils ont masqué l'attention croisée vers des positions d'entrée spécifiques (par exemple, les étapes ascendantes où $w_i=1$) pour tester si ces positions étaient fonctionnellement nécessaires au décodage.
• Sondage linéaire (Linear Probing) : Des classifieurs linéaires ont été entraînés sur les états cachés de l'encodeur pour prédire le « niveau » de chaque position dans le chemin de Dyck, testant si cette statistique combinatoire est linéairement accessible dans les représentations.

3. Extraction de l'algorithme

Sur la base des motifs observés dans le modèle minimal, les auteurs ont formulé un nouvel algorithme explicite, la Carte d'Échafaudage (Scaffolding Map), et ont par la suite prouvé son équivalence avec la carte zeta.

Principaux résultats et contributions

1. Découverte d'un mécanisme basé sur les niveaux

L'analyse d'interprétabilité a révélé que le modèle ne traite pas la carte zeta comme une table de recherche arbitraire, mais organise la génération via un mécanisme structuré basé sur les niveaux :

• Sélection du niveau maximal : Le décodeur porte systématiquement son attention sur les positions d'entrée ayant des niveaux maximaux parmi les positions pertinentes, particulièrement lors des premières étapes de génération.
• Évitement systématique des étapes ascendantes : Le décodeur porte rarement attention aux positions où $w_i=1$ (étapes Nord). L'ablation causale a confirmé que le masquage de l'attention vers ces positions entraînait une dégradation négligeable de la précision, impliquant que le décodeur ne les « lit » pas directement mais repose sur des informations agrégées.
• Décalage séquentiel triangulaire : Le motif d'attention présente un décalage d'une position d'étape Est ($w_i=0$) de haut niveau vers la position d'étape Est suivante éligible ($i+1$), correspondant à une diminution séquentielle du niveau ($\ell_{i+1} = \ell_i - 1$).
• Accessibilité linéaire : Les sondes linéaires ont confirmé que les représentations de l'encodeur rendent la séquence de niveaux ($\ell_i$) du chemin de Dyck linéairement accessible (84 % de précision prédictive).

2. La Carte d'Échafaudage (Scaffolding Map)

Traduisant ces signaux en combinatoire, les auteurs proposent la Carte d'Échafaudage, un algorithme de traversée centré sur les pics :

• Mécanisme : L'algorithme regroupe les positions de pics par leur niveau. Il initialise des « agents » à ces pics et traverse le chemin niveau par niveau, du haut vers le bas.
• Traversée : Les agents se déplacent le long des positions adjacentes d'étape Est et de non-étape Est. Le mot de sortie est généré en lisant les symboles rencontrés par ces agents lorsqu'ils traversent l'« échafaudage » construit par les étapes ascendantes.
• Structure : L'algorithme sépare la structure de support latente (les niveaux construits par les étapes ascendantes) du processus de traversée qui génère la sortie.

3. Vérification théorique

Les auteurs ont fourni une preuve formelle (Théorème 6.1) établissant que la Carte d'Échafaudage est équivalente à la carte zeta (modulo la convention de renversement utilisée dans le jeu de données).

• Stratégie de preuve : La preuve compare la Carte d'Échaudage niveau par niveau avec la description par séquence d'aire de $\text{rev} \circ \zeta$. Elle démontre que les sous-séquences générées par le mécanisme de mise en file d'attente de la Carte d'Échafaudage ($Q'_k$) correspondent exactement aux sous-séquences générées par l'algorithme standard de la carte zeta ($P_k$) lors du balayage de la séquence d'aire en sens inverse.

Signification et affirmations

Le document affirme fournir un exemple contrôlé de découverte mathématique assistée par l'IA où l'interprétabilité mécaniste transforme le comportement du modèle en un algorithme combinatoire précis et vérifiable par l'humain.

• Nouveauté : À la connaissance des auteurs, c'est le premier cas où l'interprétation mécaniste d'un modèle de séquence neuronale entraîné est utilisée pour extraire une nouvelle description bijective explicite d'une carte combinatoire bien étudiée.
• Flux de travail (Workflow) : Le document articule un flux de travail où :
  1. Le modèle fournit des signaux structurels récurrents (motifs d'attention, sondes linéaires).
  2. Les chercheurs humains interprètent ces signaux comme des opérations combinatoires.
  3. Les interventions (ablations) testent la pertinence causale.
  4. La procédure résultante devient un objet mathématique (la Carte d'Échafaudage) qui peut être énoncé et prouvé indépendamment du réseau neuronal.
• Limites : Les auteurs font preuve de modestie quant à la portée de l'étude, notant que :
  • Les motifs d'attention seuls ne constituent pas une preuve ; la combinaison avec l'ablation et la preuve formelle est essentielle.
  • Le mécanisme appris dans le transformeur semble être une version « floue » de l'algorithme (évidencié par les résultats imparfaits des sondages), suggérant que des modèles plus grands ou entraînés différemment pourraient implémenter des mécanismes plus complexes ou plus « propres ».
  • La Carte d'Échafaudage a été extraite d'un modèle spécifiquement simple ; des modèles plus larges pourraient implémenter des solutions internes différentes.

Le document conclut que, bien que les détails spécifiques de cette découverte puissent ne pas se transférer directement à tous les problèmes mathématiques, le concept d'utiliser l'interprétabilité mécaniste pour combler le fossé entre la prédiction boîte noire et la construction combinatoire explicite est largement applicable dans la recherche en combinatoire.