Résumé - FormulaOne : Mesurer la profondeur de la raison algorithmique au-delà de la programmation compétitive

FormulaOne : Mesurer la profondeur de la raison algorithmique au-delà de la programmation compétitive

2025-07-17 17:53:55

{"Gal Beniamini","Yuval Dor","Alon Vinnikov","Shir Granot Peled","Or Weinstein","Or Sharir","Noam Wies","Tomer Nussbaum","Ido Ben Shaul","Tomer Zekharya","Yoav Levine","Shai Shalev-Shwartz","Amnon Shashua"}

{cs.AI,cs.CC,math.LO}

FormulaOne est un point de référence conçu pour mesurer la profondeur du raisonnement algorithmique dans les modèles d'IA, en se concentrant sur des problèmes de recherche réels plutôt que sur des puzzles de programmation compétitive inventés. Le point de référence se situe à l'intersection de la théorie des graphes, de la logique et des algorithmes, tous cela dans la distribution d'entraînement des modèles de pointe. Le jeu de données possède trois propriétés clés : 1. Il présente un intérêt commercial et est lié à des problèmes d'optimisation à grande échelle pratiques, tels que le routage, la planification et la conception de réseaux. 2. Il est généré à partir du cadre hautement expressif de la logique monadique du second ordre (MSO) sur les graphes, ouvrant la voie à la génération automatique de problèmes à grande échelle. 3. De nombreux problèmes sont étroitement liés à la pointe de la science des ordinateurs théorique et à des conjectures centrales telles que l'Hypothèse exponentielle forte (SETH). Les problèmes dans FormulaOne sont incroyablement exigeants, nécessitant une série de pas de raisonnement, impliquant des insights topologiques et géométriques, des connaissances mathématiques, des considérations combinatoires, une implémentation précise et plus encore. Les modèles les plus avancés comme ceux d'OpenAI, o3, échouent complètement sur FormulaOne, résolvant moins de 1% des questions, même lorsqu'ils sont donnés 10 tentatives et des exemples fewshot explicatifs. Cela met en lumière à quel point ces modèles restent loin de la compréhension de niveau expert dans certains domaines. FormulaOne consiste en une large gamme de problèmes de programmation dynamique sur les graphes, générés à l'aide de la logique monadique du second ordre (MSO). Les problèmes sont conçus pour évaluer la maîtrise de la résolution de problèmes abstraits, du raisonnement combinatoire à plusieurs étapes et de l'implémentation pratique. Le jeu de données comprend deux parties : 1. FormulaOne : Un jeu de données de 120 problèmes de programmation dynamique complexes qui évaluent la créativité, la sophistication et le raisonnement de niveau expert. 2. FormulaOne-Warmup : Un jeu de données auxiliaire contenant 100 problèmes plus simples pour faciliter la recherche et l'évaluation dans ce cadre exigeant. Le point de référence est évalué à l'aide d'un cadre complet qui permet à la fois la génération systématique de problèmes de programmation dynamique et la vérification des solutions proposées à ces problèmes. L'évaluation inclut plusieurs types de suites de tests, chacune conçue pour explorer un aspect différent de la validité d'une solution. Les résultats montrent que même les meilleurs modèles de raisonnement de pointe, comme ceux d'OpenAI, échouent totalement sur le jeu de données FormulaOne, atteignant un taux de réussite étonnamment bas de <1 %. Cela met en lumière la nécessité de milieux de raisonnement plus profonds et de meilleurs points de référence pour capturer des niveaux croissants de complexité.