FR
Les modèles résolvent moins de problèmes quand un changement structurel les rend NP-complets
Did the Problem Actually Get Harder? Testing LLMs on Paired P and NP-Complete Problems Hardened by Adversarial Multi-Agent Rewriting · arXiv:2610.30103
En termes simples
L’article présente un ensemble de problèmes de programmation appariés pour vérifier si les modèles de langage repèrent qu’un petit changement de structure rend un problème bien plus difficile. Dans chaque paire, les problèmes partagent le même cadre, mais une caractéristique fait que l’un se résout en temps polynomial et l’autre est NP-complet.
Pour les 12 modèles évalués, le score moyen de chacun était plus faible sur les problèmes NP-complets. Leur accorder davantage de temps n’a apporté qu’un faible gain, ce qui suggère que beaucoup d’échecs venaient de solutions incorrectes ou inutilisables plutôt que de solutions correctes exécutées trop lentement.
La recherche
Quand un détail structurel fait passer un problème d’une résolution en temps polynomial à la classe NP-complète, les modèles de langage peuvent-ils adapter leurs solutions à cette nouvelle structure de calcul ?
Les évaluations précédentes ne mettaient pas ces classes en paire tout en gardant un cadre de problème proche, ce qui rendait la question difficile à isoler.
Les auteurs créent P2NPCBench, un ensemble de problèmes de programmation appariés qui vérifie si les modèles suivent un changement structurel faisant passer un problème de la résolution en temps polynomial à la classe NP-complète.
Les auteurs comparent des problèmes appariés répartis entre 12 familles. Chaque paire partage le même cadre, mais une caractéristique structurelle détermine si le problème se résout en temps polynomial ou appartient à la classe NP-complète. Un énoncé ne compte comme résolu que si une solution Python générée réussit tous ses cas de test.
Pour les 12 modèles, la part moyenne d’énoncés résolus est de 63,8 % pour les problèmes à temps polynomial et de 35,4 % pour les problèmes NP-complets ; chaque modèle obtient en moyenne un score inférieur pour ces derniers.
La comparaison appariée appuie l’existence d’un écart de performance associé au changement structurel.
Les résultats portent sur 12 familles de problèmes formulées en anglais, des problèmes de classes P et NP-complets, et des solutions en Python 3. Les énoncés ont été durcis face à un panel fixe de quatre modèles, des versions apparentées figurent au sein de mêmes lignées, et chaque modèle évalué n’a produit qu’un échantillon glouton. Ces résultats ne permettent pas de conclure au-delà de ce périmètre.
Ce que montrent les preuves
- Tester l’effet du changement structurel
P2NPCBench est un benchmark conçu pour vérifier si les modèles de langage réagissent à la structure de calcul d’un problème. Il met en paire des problèmes à temps polynomial et des problèmes NP-complets formulés dans le même cadre, mais distingués par une caractéristique structurelle.
La question est de savoir si les modèles résolvent les problèmes en fonction de cette structure, plutôt qu’en s’appuyant surtout sur des formulations ou des schémas familiers.
- Créer des variantes valides
Pour créer des énoncés plus difficiles, les auteurs ont utilisé AgentGAN, une adaptation d’un cadre existant de réécriture multi-agents. Un générateur rédige des variantes, un panel fixe de modèles de code tente de les résoudre, puis un filtre de validité vérifie que les réécritures retenues préservent la réponse et la classe de complexité, et que les problèmes restent bien définis et solubles.
Le benchmark comprend 2 114 énoncés répartis entre 12 familles, les versions apparentées étant regroupées en lignées.
- Comparer les résultats appariés
Les auteurs ont mesuré si une solution Python générée réussissait tous les cas de test d’un énoncé. Pour les 12 modèles, les scores moyens étaient de 63,8 % sur les énoncés à temps polynomial et de 35,4 % sur les énoncés NP-complets ; chaque modèle obtenait en moyenne un score inférieur du côté NP-complet.
Les problèmes étant appariés et la règle de résolution identique, les résultats montrent un écart constant associé au changement structurel.
- Vérifier le rôle du temps et des formulations
Allonger les limites de temps a peu changé les scores sur les énoncés NP-complets : multiplier par dix la limite annoncée par test, en la faisant passer de 1 à 10 secondes, a fait progresser la moyenne de 28,5 % à 31,9 %.
Dans une comparaison distincte, la précision baissait entre les énoncés initiaux et leurs dernières variantes durcies dans les deux classes, avec une baisse plus forte pour les problèmes à temps polynomial. Ensemble, ces résultats suggèrent que le temps disponible et la familiarité des formulations jouent tous deux un rôle, sans faire disparaître l’écart entre les classes.
- Interpréter les échecs et le transfert
Les auteurs ont aussi examiné les échecs aux tests. Pour les problèmes NP-complets, les erreurs d’exécution représentaient la plus grande catégorie rapportée, devant les réponses incorrectes et les dépassements de temps.
Cela appuie leur interprétation selon laquelle beaucoup d’échecs venaient de solutions incorrectes ou impossibles à exécuter, et non de solutions correctes mais lentes. Le même sens d’écart apparaît pour un modèle tenu à l’écart du durcissement, mais ce résultat se limite à ce modèle et à ce benchmark.
Détails
- Auteurs de l’article original
- Nurul Labib Sayeedi, Md. Faiyaz Abdullah Sayeedi, Zabir Al Nazi, Mahbub E Sobhani, Shubhashis Roy Dipta
- Soumis à arXiv
- Licence
- CC BY 4.0