🤖 machine learning

From Markov to Laplace: How Mamba In-Context Learns Markov Chains

Cet article démontre que les modèles Mamba à une seule couche peuvent apprendre efficacement l'estimateur optimal de lissage Laplacien pour les chaînes de Markov en contexte, établissant théoriquement le premier lien formel entre l'architecture basée sur la convolution de Mamba et l'estimation statistique optimale de type Bayes/minimax.

Auteurs originaux : Marco Bondaschi, Nived Rajaraman, Xiuying Wei, Kannan Ramchandran, Razvan Pascanu, Caglar Gulcehre, Michael Gastpar, Ashok Vardhan Makkuva

Publié 2026-06-23

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Marco Bondaschi, Nived Rajaraman, Xiuying Wei, Kannan Ramchandran, Razvan Pascanu, Caglar Gulcehre, Michael Gastpar, Ashok Vardhan Makkuva

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

La vue d'ensemble : Un nouveau type de cerveau pour l'IA

Imaginez l'actuelle superstar de l'Intelligence Artificielle, le Transformer (le moteur derrière la plupart des chatbots), comme un bibliothécaire brillant mais pesant. Il peut lire un livre entier et trouver des connexions instantanément, mais il se fatigue et ralentit si le livre est trop long car il essaie de se souvenir de chaque mot à la fois.

Entrez en scène Mamba, un nouveau type de modèle d'IA. C'est comme un coursier agile et rapide. Il traite l'information beaucoup plus vite et utilise moins de mémoire, ce qui en fait une alternative prometteuse au bibliothécaire pesant. Mais les scientifiques ne comprenaient pas pleinement comment ce coursier était si intelligent. Ils savaient qu'il fonctionnait bien, mais ils ne connaissaient pas sa recette secrète.

Cet article agit comme une histoire de détective, cherchant à comprendre exactement comment Mamba résout un type spécifique de puzzle appelé Chaînes de Markov.

Le puzzle : Prédire l'étape suivante

Pour tester Mamba, les chercheurs lui ont donné un jeu appelé « Prédiction du prochain jeton » (Next Token Prediction).

La configuration : Imaginez une séquence d'événements, comme une chaîne de perles colorées (Rouge, Bleu, Rouge, Rouge, Bleu...).
La règle : La couleur de la perle suivante dépend des couleurs des perles qui l'ont précédée juste avant. C'est une « Chaîne de Markov ».
Le défi : Le modèle voit une chaîne de perles aléatoire et doit deviner la suivante. Crucialement, les règles du jeu (la probabilité que le Rouge suive le Bleu) changent pour chaque nouvelle chaîne. Le modèle doit découvrir les règles à la volée simplement en regardant la chaîne actuelle. C'est ce qu'on appelle l'Apprentissage en Contexte (In-Context Learning - ICL).

La découverte : Mamba est un statisticien parfait

Les chercheurs ont découvert quelque chose de surprenant. Même un Mamba à une seule couche (une version très simple du modèle) a appris à devenir le statisticien parfait pour ce jeu.

Dans le monde des statistiques, il existe une méthode de référence (« Gold Standard ») pour deviner la perle suivante quand on ne connaît pas parfaitement les règles. C'est le Lissage de Laplace (ou l'estimateur « Add-β »).

L'analogie : Imaginez que vous essayez de deviner la prochaine carte dans un paquet. Si vous avez vu 10 As et 0 Roi, vous pourriez deviner que le prochain est un As. Mais un statisticien intelligent sait : « Attendez, je n'ai pas encore vu de Roi, c'est peut-être juste de la malchance. » Il ajoute donc un petit Roi « fantôme » à son décompte pour éviter d'être trop affirmatif. Cela empêche de dire « Chance nulle ! » pour quelque chose qu'il n'a pas encore vu.

La thèse de l'article : Mamba ne se contente pas de deviner ; il apprend mathématiquement à effectuer exactement ce « comptage fantôme » parfaitement. Il calcule les décomptes des motifs précédents et ajoute cette petite dose de « lissage » automatiquement, tout comme l'exige la formule statistique optimale.

L'ingrédient secret : La « lampe torche » de la convolution

Les chercheurs se sont demandé : Comment Mamba fait-il cela ? Est-ce dû à ses mécanismes de porte complexes ? Ses fonctions d'activation non linéaires ?

Ils ont mené des expériences en retirant certaines parties de Mamba pour voir ce qui échouait.

La découverte : La partie la plus importante est la Convolution.
L'analogie : Pensez à la Convolution comme à une lampe torche que Mamba projette sur le passé récent.
- Pour deviner la perle suivante, Mamba doit savoir : « Combien de fois le 'Rouge' a-t-il suivi le 'Bleu' dans les dernières étapes ? »
- La convolution agit comme une fenêtre qui glisse sur l'historique, comptant ces motifs instantanément.
- Les chercheurs ont découvert que si vous retirez la lampe torche (la convolution), Mamba devient aveugle et échoue à la tâche. Si vous gardez uniquement la lampe torche (et retirez le mécanisme de porte complexe), Mamba résout toujours le puzzle parfaitement.

Point clé : La « lampe torche » (la convolution) est l'héroïne ici. Elle permet à Mamba de regarder en arrière, de compter les occurrences de motifs et d'appliquer le lissage statistique optimal sans avoir besoin d'un cerveau profond et complexe.

Les limites : Quelle taille doit faire la lampe torche ?

L'article a également examiné la difficulté du puzzle.

Si le jeu dépend de la dernière perle (ordre 1), une petite lampe torche suffit.
Si le jeu dépend des 5 dernières perles (ordre 5), la lampe torche doit être plus large pour voir les 5 perles à la fois.
Le théorème : L'article prouve que pour gérer un jeu dépendant de $k$ étapes précédentes, la « taille de la mémoire » (dimension cachée) du modèle doit croître exponentiellement avec $k$ . C'est comme essayer de mémoriser un mot de passe : plus le mot de passe est long, plus il est exponentiellement difficile de tout garder en tête à la fois.

Comparaison avec les Transformers

L'article compare Mamba au Transformer (le bibliothécaire pesant) :

Transformers : Pour résoudre ce puzzle de « comptage », un Transformer a généralement besoin de deux couches (deux cerveaux travaillant ensemble) pour construire un mécanisme appelé « tête d'induction » afin de compter les motifs. Un Transformer à une seule couche échoue.
Mamba : Un Mamba à une seule couche résout cela immédiatement car son mécanisme de convolution est intégré et efficace pour compter.

Résumé

Cet article révèle que le super-pouvoir de Mamba dans l'apprentissage par contexte provient d'une caractéristique architecturale spécifique : la Convolution.

Mamba apprend à agir comme un statisticien parfait, utilisant une méthode appelée Lissage de Laplace pour prédire l'élément suivant d'une séquence.
Il y parvient en utilisant une « lampe torche » de convolution pour compter les motifs passés et appliquer les ajustements statistiques corrects.
Cela se produit même dans un modèle très simple à une seule couche, alors que les Transformers ont besoin de plus de complexité pour accomplir la même tâche.

Les auteurs concluent que c'est la première fois que quelqu'un connecte formellement Mamba à ces estimateurs statistiques optimaux, prouvant que Mamba n'est pas seulement un modèle rapide, mais qu'il comprend fondamentalement comment compter et lisser les données efficacement.

Résumé Technique : De Markov à Laplace : Comment Mamba apprend les chaînes de Markov en contexte

Énoncé du Problème

Bien que les modèles basés sur les Transformers aient stimulé les récentes avancées de l'IA (leur complexité computationnelle étant quadratique par rapport à la longueur de la séquence), l'intérêt se porte sur des alternatives plus efficaces comme les modèles d'espace d'état (SSM) structurés, spécifiquement les SSM sélectifs tels que Mamba et Mamba-2. Malgré leur succès empirique et leurs gains de vitesse d'inférence, les capacités d'apprentissage fondamentales de Mamba restent mal comprises. Plus précisément, il existe un manque de compréhension théorique concernant les mécanismes d'apprentissage en contexte (In-Context Learning ou ICL) de Mamba, contrairement au corpus croissant de travaux expliquant l'ICL des Transformers (par exemple, les têtes d'induction).

La question centrale abordée est la suivante : Pouvons-nous caractériser systématiquement les capacités d'ICL de Mamba ? Les auteurs étudient cela en analysant les performances de Mamba sur des chaînes de Markov aléatoires, un cadre précédemment utilisé pour découvrir les mécanismes fondamentaux des Transformers.

Méthodologie

Le papier emploie le cadre Markov-ICL, où les jetons d'entrée sont tirés de chaînes de Markov aléatoires d'ordre $k$ .

Génération de données : Les noyaux de transition sont échantillonnés indépendamment à partir d'une priorité de Dirichlet, garantissant que chaque séquence de test suit une distribution de Markov unique. Le modèle doit estimer la distribution du jeton suivant en contexte sans mise à jour explicite des paramètres.
Base de référence optimale : L'estimateur théorique optimal pour cette tâche est l'estimateur de lissage laplacien (add- $\beta$ ), qui est à la fois Bayésien et minimax optimal. Cet estimateur nécessite de compter les occurrences de jetons au sein de contextes spécifiques et d'appliquer un lissage additif.
Analyse architecturale : Les auteurs analysent l'architecture Mamba (spécifiquement Mamba-2), en se concentrant sur sa récurrence, sa sélectivité et ses mécanismes de convolution. Ils introduisent une variante simplifiée, MambaZero, qui ne conserve que l'embedding, la sélectivité de l'entrée basée sur la convolution et les couches linéaires, supprimant le gating et les non-linéarités pour isoler le mécanisme d'apprentissage central.
Caractérisation théorique : Le papier fournit une preuve constructive démontrant comment MambaZero peut représenter l'estimateur optimal de lissage laplacien. Il établit également une borne inférieure sur la dimension cachée requise pour que les architectures récurrentes représentent de tels estimateurs.

Contributions Clés

1. Mamba apprend l'estimateur de lissage laplacien optimal

Les auteurs démontrent que même un Mamba à une seule couche apprend efficacement l'estimateur de lissage laplacien optimal pour tous les ordres de Markov.

Preuve empirique : Les expériences montrent qu'un Mamba d'une couche égale la performance de l'estimateur optimal sur des chaînes de Markov binaires et multi-états, surpassant de manière significative un Transformer d'une couche (qui échoue à la tâche) et égalant un Transformer de deux couches.
Résultat surprenant : Contra contrairement aux Transformers, qui nécessitent généralement plusieurs couches pour implémenter des têtes d'induction (mécanismes de comptage), Mamba atteint cette capacité de comptage optimale avec une seule couche.

2. Le rôle pivot de la convolution

Par des études d'ablation, le papier identifie la convolution comme le composant fondamental permettant la capacité d'ICL de Mamba, plus encore que le gating ou les activations non linéaires.

Résultats d'ablation : Supprimer la convolution de Mamba provoque l'échec de la tâche de prédiction de Markov, même avec plusieurs couches. Inversement, un modèle simplifié contenant uniquement la convolution (MambaZero) apprend la tâche avec succès.
Mécanisme : La taille de la fenêtre de convolution $w$ doit satisfaire $w \ge k + 1$ (où $k$ est l'ordre de Markov) pour suivre le contexte nécessaire au comptage. La convolution permet au modèle de maintenir un état qui compte efficacement les transitions $i \to j$ basées sur le contexte actuel.

3. Caractérisation théorique et limites

Capacité de représentation : Les auteurs fournissent une preuve constructive (Théorème 1) montrant que MambaZero peut représenter exactement l'estimateur de lissage laplacien pour les processus de Markov d'ordre 1. Le mécanisme consiste à utiliser l'état $H_t$ pour accumuler les comptes de transition, où la convolution garantit que les mises à jour de l'état dépendent de l'historique du contexte correct.
Limites fondamentales : Le Théorème 2 établit une borne inférieure pour les architectures récurrentes : pour représenter l'estimateur optimal pour un processus de Markov d'ordre $k$ avec une précision de bits finie, le produit de la dimension cachée $d$ et de la précision $p$ doit croître comme $\Omega(2^k)$ . Cela contraste avec les Transformers, qui peuvent représenter ces estimateurs avec des dimensions cachées croissant linéairement en $k$ (en utilisant 3 couches).
Sélectivité : Dans les processus de Markov à "commutation" (switching) non-markoviens, le papier montre que Mamba utilise son mécanisme de sélectivité (le facteur de décroissance $a_t$ ) pour réinitialiser les comptes lorsqu'un jeton de commutation survient, démontrant l'adaptabilité du mécanisme appris.

Résultats

Tâches de Markov : Un Mamba d'une seule couche atteint un écart de perte proche de zéro par rapport à l'estimateur de lissage laplacien optimal à travers divers ordres de Markov et tailles d'espace d'états.
Comparaison avec les Transformers : Bien que des Transformers de deux couches puissent résoudre la tâche, les Transformers d'une couche ne le peuvent pas. Mamba résout le problème avec une seule couche.
Langage naturel : Les expériences sur le jeu de données WikiText-103 montrent que supprimer la convolution de Mamba-2 augmente la perplexité de 11 %, tandis que la supprimer de Transformer n'augmente la perplexité que de 2 %. Cela suggère que la convolution joue un rôle plus critique dans la performance de Mamba sur des tâches de langage complexes que dans celle des Transformers.
Processus de commutation : Mamba implémente correctement une stratégie de réinitialisation des comptes de transition lors de la rencontre d'un jeton de "commutation" en fixant le facteur de décroissance de l'état $a_t$ à 0, imitant ainsi la stratégie bayésienne optimale pour les environnements non stationnaires.

Signification et Revendications

Le papier affirme fournir la première connexion formelle entre Mamba et les estimateurs statistiques optimaux.

Aperçu théorique : Il révèle que la capacité d'ICL de Mamba n'est pas simplement une propriété émergente mais est structurellement ancrée dans sa capacité à implémenter un comptage optimal via la convolution et la récurrence.
Compréhension architecturale : Ce travail clarifie que pour Mamba, la convolution est le principal moteur de sa capacité à apprendre des statistiques dépendantes du contexte, se distinguant ainsi des mécanismes basés sur l'attention des Transformers.
Généralité : Les conclusions s'étendent au-delà des données de Markov synthétiques pour atteindre la modélisation du langage naturel, suggérant que les mécanismes identifiés (comptage piloté par la convolution) sont fondamentaux pour le succès de Mamba dans des tâches linguistiques plus larges.

Les auteurs font preuve de modestie quant aux directions futures, notant que bien qu'ils caractérisent le pouvoir de représentation, la dynamique d'apprentissage de la convergence de Mamba vers ces estimateurs reste un domaine de recherche ouvert. Ils soulignent également que leur objectif est de comprendre les capacités intrinsèques de Mamba plutôt que de mener une comparaison architecturale directe avec les Transformers, bien que de telles comparaisons fournissent un contexte nécessaire.