🤖 machine learning

Certification from Examples is Hard for Circuits and Transformers under Minimal Overparametrization

Cet article démontre que même une surparamétrisation minimale dans les circuits à seuil et les Transformers à précision logarithmique peut rendre la certification exacte et approximative exponentiellement difficile, une barrière théorique qui est validée empiriquement par la difficulté de détecter des erreurs dans des modèles entraînés effectuant une addition binaire.

Auteurs originaux : Artur Back de Luca, Kimon Fountoulakis

Publié 2026-05-25

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Artur Back de Luca, Kimon Fountoulakis

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 soyez un enseignant essayant de vérifier qu'un élève a véritablement appris une règle mathématique spécifique, comme « comment additionner deux nombres ». Vous disposez d'une liste d'exemples (paires entrée-sortie) et vous voulez être certain à 100 % que l'élève ne fait pas que deviner ou suivre un tour de passe-passe.

Ce papier pose une question fondamentale : Combien d'exemples devez-vous montrer à un élève pour prouver qu'il connaît la règle exacte, et non pas simplement une très similaire ?

Les auteurs, Artur Back de Luca et Kimon Fountoulakis, ont découvert une vérité surprenante et quelque peu effrayante : Même un changement minuscule, presque invisible, apporté au « cerveau » de l'élève (le modèle) peut rendre impossible la preuve qu'il est correct, peu importe le nombre d'exemples que vous lui montrez.

Voici la décomposition de leurs découvertes à l'aide d'analogies simples :

1. Le problème de l'« Imposteur »

Imaginez que vous ayez un élève parfait qui connaît la règle de l'addition des nombres. Vous voulez prouver qu'il est le seul à la connaître.

Le scénario facile : Si l'élève est le seul dans la pièce, vous n'avez peut-être besoin que de lui montrer 5 ou 10 exemples pour prouver qu'il connaît la règle.
Le scénario difficile : Maintenant, imaginez que vous invitiez 1 000 « imposteurs » dans la pièce. Ces imposteurs sont presque parfaits. Ils donnent la bonne réponse 99,9 % du temps. La seule fois où ils se trompent, c'est sur un ensemble très spécifique et caché de nombres (comme les nombres commençant par le chiffre '7').

Le papier montre que si vous ajoutez juste un « neurone » supplémentaire (un tout petit peu de puissance cérébrale supplémentaire) à un modèle, vous pouvez créer des millions de ces imposteurs. Chaque imposteur est d'accord avec l'élève parfait sur presque tout, mais ils sont tous en désaccord sur un ensemble différent, minuscule et caché de nombres.

2. L'analogie de l'« Aiguille dans une botte de foin »

Pour prouver que l'élève est le vrai et non un imposteur, vous devez trouver le nombre spécifique où ils ne sont pas d'accord.

Si vous avez 1 000 imposteurs, et que chacun cache son erreur dans un coin différent et minuscule de l'univers des nombres, vous devez vérifier chaque coin unique pour être sûr.
Le papier prouve que si vous ajoutez juste une porte supplémentaire à un circuit (ou une « tête d'attention » supplémentaire à une IA de type Transformer), le nombre de ces coins cachés explose.
Le résultat : Pour attraper tous les imposteurs, vous pourriez avoir besoin de vérifier des milliards d'exemples. Si vous n'en vérifiez que quelques milliers (un nombre « polynomial »), vous manquerez probablement les imposteurs, et l'élève passera votre test même s'il est en réalité faux.

3. Les deux personnages principaux

Les auteurs ont testé cela sur deux types d'« élèves » :

Les circuits : Imaginez-les comme de simples machines logiques rigides (comme une calculatrice). Ils ont découvert que l'ajout de juste un interrupteur supplémentaire à un circuit de profondeur 2 ou plus rend la certification de la réponse exponentiellement plus difficile.
Les Transformers : Ce sont les puissants modèles d'IA derrière des outils comme les chatbots. Les auteurs ont montré que l'ajout de juste une tête d'attention supplémentaire (un tout petit ajustement architectural) et de quelques nombres supplémentaires à la mémoire du modèle rend la certification impossible avec un nombre raisonnable d'exemples.

4. Le piège du « Presque parfait »

Vous pourriez penser : « D'accord, mais que se passe-t-il si nous acceptons simplement que l'élève commette quelques erreurs ? Que se passe-t-il si nous disons : 'S'ils ont 99 % de bonnes réponses, c'est assez bien' ? »
Le papier dit : Méfiez-vous.

Erreurs absolues : Si vous dites : « Vous ne pouvez faire que 10 erreurs au total », les imposteurs se cachent toujours. Vous avez toujours besoin de milliards d'exemples pour trouver ces 10 erreurs car elles sont dispersées à travers des milliards de possibilités.
Erreurs relatives : Si vous dites : « Vous pouvez faire 1 % d'erreurs », les imposteurs peuvent cacher des millions d'erreurs, tant que ce 1 % est suffisamment petit. Le modèle peut être extrêmement faux en termes absolus mais passer quand même votre test de « 99 % de précision ».

5. L'expérience réelle

Pour prouver que ce n'est pas juste de la théorie mathématique, ils ont réellement construit ces modèles :

L'expérience du circuit : Ils ont construit un circuit qui additionne des nombres, puis ont créé des milliers de versions « cassées » qui échouent uniquement sur des entrées spécifiques. Ils ont montré que même avec un grand nombre d'exemples de test, beaucoup de ces circuits cassés semblaient toujours parfaits.
L'expérience du Transformer : Ils ont entraîné des modèles d'IA à additionner des nombres. Même après les avoir entraînés jusqu'à ce qu'ils passent des tests de validation stricts (obtenant 99,9 % de bonnes réponses), ils ont découvert que certains modèles avaient encore des erreurs cachées. Lorsqu'ils ont essayé de « auditer » ces modèles avec des exemples aléatoires, les modèles continuaient de passer le test même s'ils n'étaient pas réellement parfaits.

La conclusion

Le papier conclut que la certification est extrêmement fragile.
Si vous voulez garantir qu'une IA ou un circuit fait exactement ce que vous pensez qu'il fait, vous ne pouvez pas vous fier à la performance moyenne. Si le modèle a même un tout petit peu de « capacité supplémentaire » (surparamétrisation), il peut cacher un nombre exponentiel de façons d'être faux.

Pour être vraiment sûr, vous pourriez avoir besoin de tester le modèle sur un nombre d'exemples si grand qu'il devient impossible à réaliser en pratique. C'est comme essayer de prouver qu'un magicien ne triche pas en le regardant exécuter un tour quelques fois ; s'il a une carte secrète supplémentaire dans sa manche, vous ne la verrez peut-être jamais à moins de vérifier chaque carte du jeu.

Résumé Technique : La Certification à partir d'Exemples est Difficile pour les Circuits et les Transformers sous Surparamétrisation Minimale

Énoncé du Problème

Alors que les réseaux de neurones les plus performants sont de plus en plus déployés sur des tâches de raisonnement et algorithmiques, garantir leur exactitude stricte devient critique. Une haute précision moyenne masque souvent des comportements incohérents, rendant difficile la détection des défaillances qui s'écartent de la logique de raisonnement prévue. Cet article aborde le problème de la certification exacte : déterminer le nombre minimal d'exemples étiquetés entrée-sortie requis pour identifier de manière unique une hypothèse cible $f^*$ au sein d'une classe d'hypothèses $\mathcal{H}$ , de telle sorte qu'aucune autre hypothèse dans $\mathcal{H}$ ne coïncide avec $f^*$ sur l'ensemble du domaine.

La question centrale est de savoir comment cette complexité de certification est sensible à la taille de la classe d'hypothèses environnante. Plus précisément, les auteurs investiguent si un léger élargissement de la classe d'hypothèses (par exemple, l'ajout d'une seule porte logique ou d'un nombre constant de paramètres) peut rendre la certification exponentiellement plus difficile, même pour des cibles qui étaient auparavant faciles à certifier.

Méthodologie

L'article emploie un cadre théorique ancré dans la complexité d'enseignement et la complexité des circuits, complété par une validation empirique sur des tâches d'addition binaire.

Cadre Théorique

Définition de la Taille du Certificat : Les auteurs définissent la taille du certificat, $\text{cert}(f^*, \mathcal{H})$ , comme la taille minimale d'un échantillon étiqueté $S$ tel que l'espace des versions $V_S^{\mathcal{H}}$ (l'ensemble des hypothèses dans $\mathcal{H}$ cohérentes avec $S$ ) ne contienne que $f^*$ .
Principe de Désaccord Disjoint : La stratégie de preuve centrale repose sur la construction d'un ensemble d'hypothèses « trompeuses ». Pour une cible $f^*$ $f^{*}$ , les auteurs construisent une famille d'hypothèses $\{g_\pi\}$ ${g_{π}}$ qui coïncident avec $f^*$ $f^{*}$ partout sauf sur des « blocs déclencheurs » spécifiques et deux à deux disjoints $B_\pi$ $B_{π}$ .
- Si une classe d'hypothèses contient une telle famille de trompeurs où les ensembles de désaccord sont disjoints, tout certificat exact doit contenir au moins un exemple de chaque ensemble de désaccord.
- Par conséquent, la taille du certificat est minorée par le nombre de tels blocs disjoints.
Analyse de la Surparamétrisation : Les auteurs analysent comment l'ajout d'une capacité minimale (par exemple, une porte logique supplémentaire dans les circuits, une tête d'attention supplémentaire et une largeur d'embedding constante dans les Transformers) permet la construction de ces familles exponentielles de trompeurs pour chaque cible de la classe originale, plus petite.

Analyse Empirique

Les auteurs complètent la théorie par deux expériences sur la reconnaissance de l'addition binaire :

Circuits Construits : Ils mettent en œuvre la construction théorique de trompeurs pour des circuits à seuils ( $TC_0$ ) reconnaissant l'addition. Ils génèrent un ensemble de $2^n$ circuits incorrects, chacun différant de la cible sur un bloc d'entrées distinct, et mesurent combien survivent à un échantillonnage uniforme de candidats de certificats.
Transformers Entraînés : Ils entraînent des Transformers de type encodeur uniquement sur l'addition de 10 bits. Après avoir sélectionné des modèles passant des vérifications de validation strictes (99,9 % de précision), ils les évaluent sur un grand ensemble de test retenu. Ils analysent la « survie » de ces modèles imparfaits (trompeurs) lorsqu'ils sont soumis à des candidats de certificats échantillonnés uniformément, testant ainsi si les erreurs résiduelles peuvent être détectées avec des échantillons de taille polynomiale.

Contributions et Résultats Clés

1. Difficulté Exponentielle issue d'une Surparamétrisation Minimale

La contribution théorique principale est de démontrer que la certification est hautement sensible à la taille de la classe d'hypothèses.

Circuits à Seuil ( $TC_0$ ) : Pour des circuits de profondeur $d \ge 2$ , l'ajout d'une seule porte à seuil supplémentaire (augmentant le budget de portes de $s$ à $s+1$ ) force la taille du certificat pour chaque cible de la classe originale $TC_{d,s}$ à devenir exponentielle en la dimension d'entrée $n$ . Plus précisément, $\text{cert}(f^*, TC_{d,s+1}) \ge 2^{\Omega(n)}$ .
Transformers : Pour des Transformers de précision logarithmique avec attention dure moyennée (AHAT), l'ajout d'une tête d'attention dans la dernière couche et de six coordonnées d'embedding/résiduelles auxiliaires crée une classe élargie où la certification devient exponentiellement difficile. Même si une cible $f^*$ possède une taille de certificat polynomiale dans l'architecture plus petite, elle nécessite un nombre exponentiel d'exemples pour être certifiée face à l'architecture légèrement plus grande.
Non-Vacuité : Les auteurs prouvent que ces bornes inférieures ne sont pas vides. Ils montrent que les classes plus petites ( $TC_{d,s}$ et Transformers standards) contiennent des cibles avec des tailles de certificats polynomiales (spécifiquement $O(\log |\mathcal{H}|)$ ), pourtant ces mêmes cibles deviennent exponentiellement difficiles à certifier dès que la classe est minimement élargie.

2. Difficulté de la Certification Approximative

L'article étend ces résultats à la certification approximative :

Tolérance à l'Erreur Absolue : Si la certification ne permet qu'un nombre polynomial d'erreurs ( $R = \text{poly}(n)$ ), la taille du certificat reste exponentielle ( $2^{\Omega(n)}$ ).
Tolérance à l'Erreur Relative : Si la certification permet une erreur relative constante ( $\epsilon$ ), la taille du certificat peut être petite (polynomiale en $1/\epsilon$ ). Cependant, cela se fait au prix de permettre un nombre exponentiel d'erreurs absolues. Les auteurs montrent que des garanties d'erreur relative constante peuvent masquer un nombre exponentiel d'erreurs, tandis que des garanties d'erreur absolue polynomiale nécessitent toujours des certificats exponentiels.

3. Validation Empirique

Expériences sur les Circuits : Les trompeurs $TC_0$ construits ont confirmé la barrière théorique. Même avec des candidats de certificats de taille polynomiale, presque tous les trompeurs construits sont restés cohérents avec les étiquettes échantillonnées, nécessitant un échantillonnage exponentiel pour les éliminer.
Expériences sur les Transformers : Parmi 150 modèles entraînés ayant passé des validations extensives, 63 présentaient des erreurs résiduelles sur l'ensemble de test retenu. L'analyse a montré que même avec un sous-ensemble ciblé d'exemples riches en erreurs, des candidats de certificats échantillonnés uniformément de taille polynomiale ont échoué à éliminer toutes les hypothèses non exactes. Des modèles imparfaits ont pu échapper à la détection par de grands candidats échantillonnés uniformément.

Importance et Revendications

L'article revendique fournir une forme quantitative de la difficulté de certification pour l'apprentissage exact. Son importance réside dans les affirmations suivantes :

Sensibilité à la Capacité du Modèle : La certification n'est pas simplement une propriété de la fonction cible, mais dépend de manière critique de la classe d'hypothèses « ambiante ». Une augmentation minimale de la capacité du modèle (surcoût constant) peut fondamentalement altérer la difficulté de vérifier l'exactitude d'un modèle.
Limites de la Certification Passive : Dans des contextes passifs (où les exemples sont échantillonnés sans interroger le modèle), des ensembles de données de taille polynomiale sont insuffisants pour certifier qu'un modèle a appris le calcul intended si la classe d'hypothèses est légèrement surparamétrée.
Distinction par rapport à l'Apprenabilité : Les résultats soulignent un écart entre l'apprenabilité et la certification. Bien qu'une fonction puisse être apprenable (ou posséder un petit certificat dans une classe restreinte), la certifier face à une classe légèrement plus grande peut être intraitable.
Implications pour les Modèles de Raisonnement : Pour les modèles déployés sur des tâches algorithmiques (comme l'addition), une haute précision de validation ne garantit pas l'exactitude. L'article suggère que sans protocoles plus stricts (par exemple, apprentissage actif ou requêtes spécifiques), de grands ensembles de données échantillonnés uniformément peuvent échouer à détecter des incohérences subtiles et structurées dans les modèles de raisonnement.

Les auteurs concluent que si la certification exacte est un défi fondamental, la barrière n'est pas seulement une anomalie du pire cas, mais une conséquence structurelle de la surparamétrisation minimale dans des classes pertinentes pour les tâches de raisonnement modernes. Ils suggèrent que les travaux futurs devraient explorer des protocoles de certification active pour potentiellement surmonter ces barrières passives.