🤖 machine learning

On the Expressiveness of State Space Models via Temporal Logics

Cet article analyse le pouvoir expressif des modèles d'espace d'états (SSM) en utilisant les logiques temporelles, révélant que leurs capacités varient des langages réguliers aux langages non réguliers selon les mécanismes de porte et la précision arithmétique, tout en comparant systématiquement ces résultats aux architectures de type transformer.

Auteurs originaux : Eric Alsmann, Lowejatan Noori, Martin Lange

Publié 2026-01-28

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Eric Alsmann, Lowejatan Noori, Martin Lange

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 essayiez d'apprendre à un robot à lire une histoire et à comprendre la séquence des événements. Dans le monde de l'Intelligence Artificielle, il existe deux types de « lecteurs » (architectures) qui se disputent le poste : les célèbres Transformers (comme ceux qui alimentent les chatbots actuels) et les étoiles montantes appelées Modèles d'Espace d'États (SSM).

Ce document est une investigation théorique sur la « puissance cérébrale » des SSM. Les auteurs ne demandent pas si ces modèles sont performants sur un test spécifique ; ils demandent plutôt : « Quelle est la limite absolue de ce que ces modèles peuvent comprendre, peu importe la quantité d'entraînement qu'ils reçoivent ? »

Pour répondre à cela, ils utilisent un « langage logique » spécial (la Logique Temporelle) comme règle de mesure. Voici un aperçu de leurs conclusions utilisant des analogies simples.

1. Les deux principaux types de SSM

Le document divise les SSM en deux saveurs principales selon la façon dont ils gèrent l'information :

Les SSM à Portes Diagonales (Les « Comptables Rigoureux ») : Ces modèles ont une règle selon laquelle leurs « portes » internes (les interrupteurs qui contrônt le flux d'information) peuvent changer en fonction du mot actuel qu'ils lisent, mais elles doivent rester « diagonales ». Imaginez cela comme une calculatrice où vous pouvez changer les nombres que vous additionnez, mais vous ne pouvez pas mélanger les colonnes entre elles.
Les SSM Invariants dans le Temps (Les « Horloges Constantes ») : Ces modèles ont des portes qui ne changent jamais, peu importe le mot qu'ils lisent. Ils sont comme un métronome ou une horloge ; ils battent au même rythme, quelle que soit l'histoire racontée.

2. Le problème de la précision : La règle vs le ruban à mesurer

Les auteurs ont également examiné la « précision » des mathématiques à l'intérieur de ces modèles.

Précision Fixe : Imaginez utiliser une règle qui n'a que 10 graduations. Peu importe la longueur de l'histoire, vous ne pouvez rien mesurer de plus petit que ces graduations. C'est ce qui se passe avec les mathématiques informatiques standards (virgule flottante).
Précision Logarithmique : Imaginez un ruban à mesurer qui devient automatiquement plus long et plus détaillé à mesure que l'histoire s'allonge. Si l'histoire fait 100 mots, votre règle a 100 graduations ; si elle fait 1 000 mots, elle a 1 000 graduations. Cela permet un comptage beaucoup plus fin.

3. Que peuvent-ils réellement comprendre ?

Les « Comptables Rigoureux » (SSM Diagonaux)

Avec une règle simple (Précision Fixe) : Ils sont bons pour comprendre l'ordre des événements. Ils peuvent vous dire « A est arrivé avant B » ou « A est arrivé, puis B est arrivé, puis C est arrivé ». Cependant, ils ont un angle mort majeur : ils ne peuvent pas compter en cycles.
- L'analogie : Si vous leur demandez de reconnaître un motif comme « un nombre pair de 'a's » (ex: aa, aaaa, aaaaaa), ils échouent. Parce que leur mathématique est monotone (elle ne fait que monter ou rester stable), ils finissent par être « bloqués » et ne peuvent plus faire la différence entre 2 'a's et 4 'a's.
Avec un ruban à mesurer croissant (Précision Logarithmique) : Si vous leur donnez la capacité de compter précisément, ils deviennent beaucoup plus intelligents. Ils peuvent maintenant compter exactement combien de fois quelque chose s'est produit dans le passé. Ils peuvent comprendre des motifs complexes comme « le nombre de 'a's est égal au nombre de 'b's égal au nombre de 'c's ».

Les « Horloges Constantes » (SSM Invariants dans le Temps)

Avec une règle simple : Ces modèles sont mauvais pour suivre des relations de type « depuis que » complexes (ex : « Depuis la dernière fois que nous avons vu un 'b', avons-nous vu un 'a' ? »). Cependant, ils ont un super-pouvoir : ils peuvent compter en cercles.
- L'analogie : Parce que leur mécanisme interne est un cycle constant, ils sont excellents pour savoir « Est-ce le 2ème, le 4ème ou le 6ème mot ? ». Ils peuvent facilement reconnaître le motif « un nombre pair de 'a's » que les Comptables Rigoureux n'ont pas réussi à saisir.
Avec un ruban à mesurer croissant : Ils peuvent faire les deux : compter en cercles et compter des nombres totaux.

L'« Hybride » (SSM Mixtes)

Si vous combinez les deux types de couches (certaines couches de Comptables Rigoureux, certaines couches d'Horloges Constantes), vous obtenez le meilleur des deux mondes. Ils peuvent comprendre l'ordre, les cycles et le comptage. Le document montre que ces modèles hybrides peuvent reconnaître presque n'importe quel motif « régulier » auquel on peut penser, jusqu'à une certaine limite de complexité.

4. Comment se comparent-ils aux Transformers ?

Les auteurs ont comparé leurs découvertes à ce que nous savons déjà des Transformers :

Les SSM Diagonaux (Précision Fixe) sont approximativement équivalents aux Transformers sans indices positionnels (ils connaissent l'ordre des mots mais pas leur position exacte).
Les SSM Invariants dans le Temps sont équivalents aux Transformers avec Encodages Positionnels (ils savent exactement où ils se situent dans la phrase).
La grande différence : Les Transformers avec une « attention globale » (comme le type Average Hard-Attention) peuvent regarder l'histoire entière pour compter les choses vers l'avant et vers l'arrière. Les SSM, par leur nature, ne regardent que le passé (ce qu'ils ont déjà lu). Par conséquent, les SSM sont strictement moins puissants que les Transformers les plus avancés lorsqu'il s'agit de compter des choses qui se produisent plus tard dans la séquence.

5. Les tâches « impossibles »

Le point le plus important à retenir est la liste des choses que ces modèles ne peuvent pas faire, peu importe l'entraînement reçu :

Un SSM Diagonal à Précision Fixe ne pourra jamais apprendre à distinguer un nombre pair d'un nombre impair d'éléments répétés (comme aa vs aaa). C'est une limite architecturale dure, et non un échec d'entraînement.
Pour briser cette limite, vous devez soit changer l'architecture (ajouter des couches invariantes dans le temps), soit augmenter la précision mathématique (utiliser le ruban à mesurer logarithmique).

Résumé

Voyez ces modèles comme différents types de bibliothécaires :

Diagonal (Fixe) : Bon pour lire un livre dans l'ordre, mais devient confus si on lui demande de compter des motifs spécifiques.
Invariant dans le Temps : Bon pour compter les pages (pair/impair), mais peine avec les histoires complexes de type « depuis lors ».
Hybride : Le bibliothécaire ultime qui peut faire les deux, mais qui ne peut toujours pas regarder vers le chapitre suivant pour compter les choses.

Le document prouve que ces limitations sont inscrites dans l'ADN de l'architecture. Vous ne pouvez pas entraîner un bibliothécaire « Diagonal à Précision Fixe » pour qu'il devienne un bibliothécaire « de Comptage » ; vous devez lui donner un meilleur outil (précision logarithmique) ou une structure cérébrale différente (couches mixtes) pour y parvenir.

Résumé technique : Sur l'expressivité des modèles d'espace d'états via les logiques temporelles

Énoncé du problème

Les modèles d'espace d'états (SSM - State Space Models) sont apparus comme une alternative compétitive aux architectures Transformer pour la modélisation de séquences, particulièrement dans les grands modèles de langage. Cependant, alors que les progrès empiriques sont rapides, les fondements théoriques concernant l'expressivité des SSM restent sous-explorés par rapport aux Transformers. Le problème central abordé est de déterminer quelles classes de langages et de motifs différentes variantes de SSM peuvent théoriquement représenter, indépendamment de la dynamique d'entraînement. Plus précisément, l'article examine comment deux dimensions architecturales clés influencent l'expressivité :

Mécanismes de porte (Gating) : La distinction entre les portes invariantes dans le temps (matrices constantes, ex: S4), les mécanismes à porte diagonale (matrices diagonales dépendantes de l'entrée, ex: S6) et les portes arbitraires.
Précision arithmétique : La distinction entre l'arithmétique à largeur fixe (bits constants, ex: flottant standard) et l'arithmétique à précision logarithmique (précision augmentant logarithmiquement avec la longueur de l'entrée).

Les auteurs visent à mapper ces variantes vers des fragments de logique formelle et des classes de complexité afin d'établir des bornes inférieures rigoureuses et d'identifier les goulots d'étranglement architecturaux fondamentaux.

Méthodologie

Les auteurs emploient un cadre logique et de théorie de la complexité pour analyser l'expressivité des SSM, reflétant les travaux fondateurs récents sur les Transformers (ex: Strobl et al., 2024 ; Yang et al., 2024a).

Modèle formel : Les SSM sont formalisés comme des couches transformant des séquences d'entrée via des récurrences linéaires ( $h_t = \text{gate}(x_t) \cdot h_{t-1} + \text{inc}(x_t)$ ) suivies de fonctions de sortie non linéaires (modélisées comme des réseaux de neurones feedforward activés par ReLU).
Cadre logique : L'analyse utilise la logique temporelle linéaire sur traces finies (LTLf), spécifiquement le fragment du passé pur (PLTLf). Cette logique capture des propriétés basées sur l'ordonnancement des événements sans compter.
- Extensions : La logique est étendue avec des prédicats modulaires (pour suivre les positions périodiques) et des opérateurs de comptage regardant vers le passé ( $\overleftarrow{\#}$ ) pour analyser la capacité à compter les occurrences.
Preuves constructives : Les auteurs fournissent des preuves constructives démontrant comment traduire des formules logiques en architectures SSM. Ils montrent comment des opérateurs temporels spécifiques (ex: Hier, Précédemment, Depuis) et des mécanismes de comptage peuvent être implémentés via des structures de portes et des réglages arithmétiques spécifiques.
Preuves d'impossibilité : Inversement, l'article établit des résultats de non-expressivité en utilisant des propriétés telles que la monotonie dans les SSM diagonaux à précision fixe pour prouver que certains langages non star-free (ex: $(aa)^*$ ) ne peuvent pas être reconnus.

Contributions clés

1. Hiérarchie d'expressivité des variantes de SSM

L'article établit une hiérarchie détaillée des capacités des SSM basée sur le gating et la précision :

SSM à porte diagonale (Précision fixe) :
- Capacité : Reconnaître tous les langages définissables dans PLTLf (équivalent aux langages star-free et à la logique du premier ordre avec ordre, $FO[<]$).
- Limitation : Ne peut pas reconnaître les langages non star-free comme $(aa)^*$ en raison d'une propriété de monotonie où les entrées identiques répétées provoquent la stabilisation de l'état.
SSM à porte diagonale (Précision logarithmique) :
- Capacité : Reconnaître les langages dans PLTLf[ $\overleftarrow{\#}$ ], étendant l'expressivité pour inclure des langages non réguliers et même non contextuels (ex: $\{a^n b^n c^n\}$ ) via le comptage regardant vers le passé.
SSM invariant dans le temps (Précision fixe) :
- Capacité : Reconnaître les langages dans UN-PLTLf[MOD] (PLTLf unaire avec prédicats modulaires). Ils peuvent suivre des positions périodiques (ex: distinguer les indices pairs/impairs) en utilisant des matrices de permutation cycliques, ce qui leur permet de reconnaître $(aa)^*$ .
- Limitation : Conjecturé comme incapable de reconnaître les langages nécessitant l'opérateur Depuis (ex: $L(a \mathcal{S} b)$ ) car ils manquent de portes dépendantes de l'entrée pour combiner dynamiquement les informations actuelles et passées.
SSM Mixte (Diagonale + Invariant dans le temps) :
- Capacité : Reconnaître PLTLf[MOD], capturant efficacement l'union des capacités diagonales et invariantes dans le temps. Cela correspond à la classe des langages réguliers dans $AC^0$ .
- Extension de précision logarithmique : Avec la précision logarithmique, ils reconnaissent PLFTf[ $\overleftarrow{\#}$ , MOD].

2. La précision arithmétique comme déterminant critique

L'article démontre rigoureusement que la précision logarithmique est strictement nécessaire pour reconnaître des langages de comptage non réguliers. L'arithmétique à largeur fixe restreint les SSM aux langages réguliers (ou star-free), tandis que la précision logarithmique permet l'accumulation de comptes nécessaire pour des langages comme $a^n b^n c^n$ .

3. Comparaison systématique avec les Transformers

Les auteurs mappent directement les variantes de SSM aux résultats d'expressivité connus des Transformers :

SSM à porte diagonale (Précision fixe) $\approx$ Transformers à attention dure unique (UHAT) sans encodages positionnels (tous deux capturent $FO[<]$).
SSM invariant dans le temps $\approx$ UHAT avec encodages positionnels (UHAT+PE) (tous deux capturent $FO[<, MOD]$).
SSM Mixte (Précision logarithmique) $\approx$ Transformers à attention dure moyenne (AHAT) (tous deux capturent des capacités de comptage, bien que les SSM soient limités au comptage regardant vers le passé).
Portes arbitraires : Les SSM avec des portes arbitraires peuvent reconnaître tous les langages réguliers, rejoignant les bornes supérieures de variantes de Transformers plus complexes.

Résultats clés

Théorème 1 : Les SSM diagonaux avec précision fixe reconnaissent tous les langages dans PLTLf.
Théorème 3 : Les SSM diagonaux avec précision fixe ne peuvent pas reconnaître $(aa)^*$ , prouvant une séparation stricte par rapport aux SSM invariants dans le temps à cet égard.
Théorème 4 : Les SSM diagonaux avec précision logarithmique reconnaissent tous les langages dans PLTLf[ $\overleftarrow{\#}$ ].
Théorème 7 : Les SSM invariants dans le temps avec précision fixe reconnaissent tous les langages dans UN-PLTLf[MOD].
Corollaire 8 : Les SSM mixtes avec précision fixe reconnaissent tous les langages réguliers dans $AC^0$ .
Impossibilité : L'article fournit des preuves d'impossibilité montrant que des choix architecturaux spécifiques (ex: diagonalité à précision fixe) créent des goulots d'étranglement fondamentaux qu'aucune quantité de données d'entraînement ou d'optimisation ne peut surmonter.

Signification et affirmations

L'article affirme fournir la première connexion entre le pouvoir d'expression des SSM et la logique formelle, offrant des garanties structurelles sur les motifs qui sont théoriquement apprenables ou prouvables comme impossibles pour des variantes spécifiques de SSM.

Perspectives fondamentales : En délimitant les tâches "impossibles" (ex: motifs non monotones pour la précision fixe diagonale), ce travail complète les benchmarks empiriques en identifiant les limites architecturales indépendantes de la dynamique d'entraînement.
Clarté architecturale : Les résultats clarifient la relation entre les SSM et les Transformers, montrant que les SSM encodent intrinsèquement l'information positionnelle via la récurrence (analogue aux encodages positionnels dans les Transformers) mais diffèrent dans leurs mécanismes de comptage (regardant vers le passé vs attention globale).
Alignement de complexité : Les conclusions suggèrent que les SSM restreints (diagonaux/invariants dans le temps avec précision fixe) opèrent probablement dans $AC^0$ , un sous-ensemble propre de la borne supérieure $TC^0$ établie précédemment par Merrill et al. (2024). Cela implique que ces architectures pourraient ne pas être capables de reconnaître la parité ou d'autres langages hors de $AC^0$ sans modifications spécifiques.

Les auteurs concluent que leur travail établit une base théorique rigoureuse, révélant que le choix du mécanisme de porte et de la précision arithmétique dicte fondamentalement la classe de langages qu'un SSM peut modéliser, indépendamment de la procédure d'entraînement spécifique utilisée.