💬 NLP

Neuro-symbolic Syntactic Parsing: Shaping a Neural Network with the CYK Algorithm

Cet article présente CYKNN, une nouvelle architecture de réseau de neurones récurrents qui intègre directement l'algorithme d'analyse syntaxique Cocke-Younger-Kasami (CYK) dans ses opérations matricielles-vectorielles entraînables, démontrant une performance supérieure tant par rapport aux grands modèles d'apprentissage en contexte qu'aux petits LLM affinés sur les tâches d'analyse syntaxique.

Auteurs originaux : Fabio Massimo Zanzotto, Federico Ranaldi, Giorgio Satta

Publié 2026-06-01

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Fabio Massimo Zanzotto, Federico Ranaldi, Giorgio Satta

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

L'idée principale : Enseigner un manuel de règles à un robot plutôt que de le laisser deviner

Imaginez que vous avez un robot très intelligent (un grand modèle de langage, ou LLM). Vous voulez qu'il résolve un puzzle spécifique : l'analyse syntaxique d'une phrase (parsing). Cela signifie comprendre comment les mots d'une phrase s'assemblent grammaticalement, comme pour construire un arbre où le tronc est la phrase principale et les branches sont les syntagmes.

Depuis des décennies, nous possédons un manuel d'instructions parfait et étape par étape pour ce puzzle, appelé l'algorithme CYK. C'est comme une recette rigide qui garantit la bonne réponse à chaque fois si on la suit.

Cependant, les modèles d'IA modernes essaient généralement d'apprendre cette recette en lisant des millions d'exemples et en devinant le motif. Ils sont comme un étudiant qui essaie d'apprendre une formule mathématique en observant un million de problèmes résolus, espérant la « comprendre » sans jamais qu'on lui ait enseigné la formule réelle.

Ce papier pose une question différente : Si nous connaissons déjà la recette parfaite (l'algorithme CYK), pourquoi ne pas simplement injecter cette recette directement dans le cerveau du robot ?

Au lieu de laisser le robot deviner, les auteurs ont construit un nouveau type de robot (appelé CYKNN) qui possède l'algorithme CYK intégré dans sa structure. Ils ne se sont pas contentés de donner des données au robot ; ils lui ont donné la logique même de l'algorithme, traduite en mathématiques compréhensibles par le robot.

L'analogie : Le cerveau Tetris

Pour faire fonctionner cette logique intégrée, les auteurs ont utilisé une astuce ingénieuse impliquant les Représentations Réduites Holographiques (HRR). Voyez cela comme une manière spéciale d'organiser l'information.

Imaginez que la mémoire du robot est une immense partie de Tetris.

Les Blocs : Chaque mot et chaque règle grammaticale est un bloc Tetris avec une forme spécifique.
L'Inverse : Pour chaque bloc, il existe un bloc « négatif » qui s'emboîte parfaitement dans les interstices de l'original.
La Magie : Lorsque vous empilez un bloc sur son inverse exact, ils s'annulent et disparaissent, laissant un espace propre (comme lorsqu'on efface une ligne dans Tetris).

Les auteurs ont conçu le robot de sorte que, lorsqu'il traite une phrase, il empile ces blocs. Si la phrase respecte les règles de grammaire, les « mauvais » blocs s'annulent, et les « bons » blocs (la structure grammaticale correcte) restent debout. Si la phrase est incorrecte, les blocs ne s'emboîtent pas et la structure s'effondre.

Cela permet au robot d'exécuter l'algorithme CYK complexe, étape par étape, en un seul grand « balayage » holistique de mathématiques, plutôt que de vérifier les mots un par un.

L'expérience : Le petit robot face aux géants géants

Les chercheurs ont testé leur nouveau robot « câblé » (CYKNN) contre certains des modèles d'IA les plus grands et les plus célèbres au monde (comme Qwen, Gemma et gpt-oss).

Les Géants : Ces modèles possèdent des milliards de paramètres (imaginez qu'ils possèdent une immense bibliothèque de livres). On leur a demandé de résoudre le puzzle soit en lisant quelques exemples (Apprentissage en contexte / In-Context Learning), soit en étudiant un manuel spécifique (Ajustement fin / Fine-Tuning).
Le Petit Robot : Le CYKNN est beaucoup plus petit et plus simple. Il n'a pas une immense bibliothèque ; il possède simplement la « logique Tetris » spécifique pour ce puzzle unique, intégrée dans ses os.

Les Résultats :
Le petit robot câblé a battu les géants.

Même les modèles massifs de 20 milliards de paramètres ont eu du mal à résoudre le puzzle correctement, faisant souvent des erreurs ou se confondant face à des phrases courtes.
Le CYKNN, avec son algorithme directement injecté dans sa conception, a résolu le puzzle avec une grande précision.

Pourquoi cela importe (selon le papier)

Le papier soutient que demander à de gigantesques modèles d'IA de « découvrir » des algorithmes complexes simplement en lisant des données, c'est comme demander à un humain de redécouvrir les lois de la physique en regardant simplement des pommes tomber. C'est possible, mais inefficace et peu fiable.

Au lieu de cela, les auteurs montrent que si nous savons qu'un algorithme existe (comme l'analyseur CYK), nous pouvons façonner le réseau neuronal pour qu'il corresponde à cet algorithme. En injectant les « règles du jeu » directement dans les mathématiques du réseau, nous obtenons un système qui est :

Plus précis pour des tâches logiques spécifiques.
Plus efficace que d'essayer de résoudre le problème par la force brute avec des données massives.
Plus fiable car il ne se contente pas de deviner ; il suit une logique intégrée.

Résumé

Le papier démontre que nous n'avons pas toujours besoin d'attendre que l'IA « apprenne » comment penser logiquement. Nous pouvons construire la logique directement dans l'architecture de la machine. En traduisant un algorithme classique de l'informatique (CYK) en un jeu mathématique de type « Tetris », ils ont créé une IA spécialisée et de petite taille qui surpasse les géants massifs et généralistes sur une tâche logique spécifique.

Résumé technique : Analyse syntaxique neuro-symbolique : Façonner un réseau de neurones avec l'algorithme CYK

Problématique

L'article traite d'une limitation fondamentale des modèles de langage de grande taille (LLM) actuels et des architectures basées sur les transformers : leur incapacité à apprendre et à extrapoler de manière fiable des connaissances algorithmiques complexes à partir de données d'entraînement. Bien que les transformers fassent preuve de « grokking » (généralisation au-delà du surapprentissage) sur des tâches simples, ils peinent face à une généralisation algorithmique exigeante, telle que l'apprentissage de l'algorithme de parsing complexe Cocke-Younger-Kasami (CYK) à partir de zéro. Les auteurs soutiennent que s'attendre à ce que les transformers découvrent des algorithmes connus uniquement par les données est une attente exagérée, car ces modèles fonctionnent souvent comme de simples « mémoires linguistiques massives » plutôt que comme des moteurs algorithmiques. Le problème central est de savoir si des algorithmes connus peuvent être directement encodés dans des architectures de réseaux de neurones régies par des multiplications matrice-vecteur, plutôt que de compter sur l'émergence passive de capacités grâce à une échelle massive et un entraînement intensif.

Méthodologie

Les auteurs proposent CYKNN, une architecture de réseau de neurones récurrent simple conçue pour injecter directement l'algorithme CYK dans un cadre de réseau de neurones. La méthodologie repose sur trois composantes clés :

Représentations Réduites Holographiques (HRR) : Pour encoder la table de parsing CYK bidimensionnelle et les règles de grammaire symboliques, les auteurs utilisent les HRR. Dans ce cadre, les symboles sont représentés par des matrices dérivées de vecteurs aléatoires. Une propriété spécifique de ces représentations est qu'un symbole et son inverse (par exemple, $[a]^\oplus$ et $[a]^\ominus$ ) s'annulent dans une multiplication matricielle, approximant une matrice identité. Cela permet des opérations « holistiques » où des séquences de symboles peuvent être manipulées algébriquement, de manière similaire à des pièces de Tetris.
Injection Algorithmique via des Opérations Matricielles :
- Représentation : Les cellules de la table CYK $P[i, j]$ sont représentées comme des matrices distribuées. Les règles de grammaire (par exemple, $A \to BC$ ) sont encodées sous forme de matrices de poids ( $W$ ) construites à partir des représentations inverses et directes des non-terminaux.
- Mise à jour Holistique : Au lieu d'itérer à travers des boucles pour remplir la table cellule par cellule (comme dans l'algorithme CYK classique en $O(n^3)$ ), les auteurs formulent l'étape de mise à jour comme une seule multiplication matrice-vecteur : $P' = PRP$. Ici, $P$ est l'état actuel de la table et $R$ encode les règles de grammaire. Cette opération effectue théoriquement la logique de combinaison des constituants en parallèle.
- Affinement : Pour atténuer les erreurs d'approximation introduites par l'effondrement de la complexité $O(n^3)$ en une seule opération, l'architecture inclut un Décodeur Diagonal (Dd). Ce module extrait des informations diagonales spécifiques de la matrice distribuée, purifie le signal et le réinjecte dans la boucle récurrente pour affinement.
Architecture (CYKNN) : Le réseau se compose de :
- Encodeur Holographique (He) : Transforme les jetons d'entrée en la matrice initiale $P_0$ .
- Module Unaire (U) : Applique les règles de grammaire unaires pour initialiser la première diagonale.
- Module Binaire (B) : Implémente l'opération centrale $P_{i+1} = P_i R_B P_i$ pour propager les applications de règles binaires.
- Décodeur Diagonal (Dd) : Extrait et affine le contenu symbolique de la matrice distribuée à chaque étape.

Contributions Clés

Injection Directe d'Algorithme : L'article démontre une approche novatrice des méthodologies neuro-symboliques où un algorithme complexe et bien connu (CYK) est explicitement façonné dans une architecture de réseau de neurones, plutôt que d'être appris implicitement.
Raisonnement Holistique via l'Algèbre Linéaire : Les auteurs montrent que la logique itérative de la programmation dynamique (remplissage d'une table de parsing) peut être traduite en multiplications matrice-vecteur holistiques qui modifient l'état des données en une seule opération, en exploitant les propriétés des HRR.
Performance Supérieure sur les Tâches Algorithmiques : Le CYKNN proposé surpasse les modèles existants de pointe (state-of-the-art) basés sur les transformers sur la tâche spécifique du parsing CYK, même lorsque ces LLM possèdent significativement plus de paramètres (20B+).

Résultats Expérimentaux

Les auteurs ont évalué CYKNN contre deux classes de modèles basés sur les transformers :

Modèles Fine-tunés : Qwen2.5-1.5B et Qwen3-8B, fine-tunés avec LoRA sur la tâche CYK.
Modèles d'Apprentissage en Contexte (ICL) : gpt-oss-20B et Gemma-27B, sollicités par des exemples de few-shot.

Constats :

Dominance de CYKNN : CYKNN, particulièrement lorsqu'il est initialisé avec les bonnes règles grammaticales, a obtenu des scores F-measure nettement plus élevés que tous les LLM comparés, tant sur les petits ensembles (longueur 5-8) que sur les ensembles de test complets.
Limites des LLM : Les modèles Qwen fine-tunés ont mal performé, échouant souvent à apprendre la structure algorithmique et se contentant de mémoriser des associations de préfixes. Ils n'ont surpassé un CYKNN initialisé aléatoirement que sur des séquences très longues (>12 jetons), ce qui suggère qu'ils n'ont pas induit l'algorithme. Les modèles d'apprentissage en contexte ont montré une haute précision mais un faible rappel, indiquant une approche conservatrice et non algorithmique du remplissage de la table.
Sensibilité à l'Initialisation : La performance de CYKNN dépendait fortement de l'initialisation des matrices grammaticales. Une initialisation aléatoire menait à une performance moindre, tandis que l'initialisation avec les règles grammaticales spécifiques permettait au modèle de converger vers une grande précision.
Généralisation : Contrairement aux transformers, qui peinaient face aux variations de longueur de séquence, le CYKNN a démontré un comportement plus intuitif concernant la longueur des séquences, maintenant ses performances même avec des grammaires plus complexes.

Signification et Revendications

L'article affirme ouvrir la voie à une approche différente des méthodologies neuro-symboliques. Les auteurs soutiennent que si les algorithmes sont connus, il existe une alternative viable au fait de compter sur les « capacités émergentes » des transformers massifs : l'encodage direct de ces algorithmes dans les architectures neuronales.

La signification réside dans la démonstration que :

Les algorithmes peuvent façonner les architectures : Les réseaux de neurones peuvent être conçus pour incarner une logique algorithmique spécifique (CYK) à travers des opérations matrice-vecteur, plutôt que de simplement apprendre des motifs statistiques.
Efficacité des Tâches Neuro-Symboliques : Pour les tâches exigeant une adhérence algorithmique stricte (comme le parsing), un réseau spécialisé et façonné par l'algorithme peut surpasser les LLM généralistes de grande échelle, même ceux possédant des milliards de paramètres.
Alternative au « Grokking » : L'article suggère que pour des tâches algorithmiques complexes, attendre que les transformers « grokking » la solution à partir des données est inefficace et souvent infructueux ; l'injection explicite de la structure algorithmique est une voie plus robuste.

Les auteurs restent modestes, reconnaissant que la grammaire utilisée est simple et que l'implémentation actuelle n'est pas optimisée sur le plan computationnel, mais ils affirment que la simplicité de la grammaire était déjà suffisante pour exposer les limites des LLM actuels basés sur les transformers.