Résumé technique : HeuriGym : Un benchmark agentique pour les heuristiques conçues par LLM en optimisation combinatoire

Énoncé du problème

Les méthodologies d'évaluation actuelles pour les grands modèles de langage (LLM) font face à une double crise dans l'évaluation de leurs capacités de résolution de problèmes. Premièrement, les benchmarks objectifs basés sur des vérités de terrain (ex. AIME, HumanEval) reposent sur des questions fermées qui sont susceptibles de subir une contamination des données et une saturation des performances, échouant ainsi à refléter les scénarios du monde réel où les solutions ne sont ni uniques ni prédéfinies. Deuxièmement, les évaluations subjectives basées sur la préférence des juges (ex. Chatbot Arena) introduisent une variance élevée et privilégient souvent des facteurs superficiels au détriment de la qualité du raisonnement substantiel.

Il existe un écart critique dans l'évaluation de la capacité des LLM à dépasser la simple reconnaissance de formes pour faire preuve d'une véritable ingéniosité de résolution de problèmes dans des flux de travail d'ingénierie complexes et itératifs. Plus précisément, les benchmarks existants peinent à évaluer la capacité à concevoir des heuristiques novatrices pour des problèmes d'optimisation combinatoire (CO), lesquels nécessitent de naviguer dans de vastes espaces de solutions, de respecter des contraintes strictes et d'adapter des stratégies en fonction des retours d'exécution.

Méthodologie

Les auteurs introduisent HeuriGym, un cadre agentique conçu pour évaluer la capacité des LLM à générer, exécuter et affiner de manière itérative des algorithmes heuristiques pour des problèmes d'optimisation combinatoire.

Aperçu du cadre

HeuriGym fonctionne via une boucle agentique interactive composée de trois étapes :

1. Description du problème : Le LLM reçoit un prompt structuré contenant un contexte en langage naturel, une formalisation mathématique de l'objectif et des contraintes, ainsi que des formats de fichiers d'entrée/sortie spécifiques. Contrairement aux travaux antérieurs qui fournissent des implémentations partielles ou des squelettes, HeuriGym fournit uniquement l'interface de la fonction, exigeant du LLM qu'il conçoive les structures de données et les algorithmes de zéro.
2. Exécution et vérification : Le code généré est compilé ou interprété dans un environnement sandboxé. Un vérificateur spécifique au domaine vérifie le respect des contraintes (ex. préservation des dépendances), tandis qu'un évaluateur calcule le coût basé sur l'objectif d'optimisation.
3. Affinement itératif : Les journaux d'exécution, les résultats de vérification et les métriques de performance d'un petit ensemble de démonstration sont ajoutés au prompt. Cette boucle de rétroaction permet au LLM de déboguer les erreurs, de corriger les violations de contraintes et d'affiner ses stratégies heuristiques sur plusieurs itérations.

Construction du benchmark

Le benchmark comprend neuf problèmes d'optimisation combinatoire couvrant les systèmes informatiques, la logistique et la biologie computationnelle (ex. ordonnancement d'opérateurs, mapping technologique, appariement d'équipage aérien, conception de séquences protéiques).

• Critères de sélection : Les problèmes ont été sélectionnés pour avoir une exposition limitée dans la littérature (moins de 1 000 citations pour le papier le plus cité) afin de minimiser les risques de mémorisation. Ils présentent des spécifications en langage naturel bien définies, de vastes espaces de solutions et des instances de données scalables.
• Jeu de données : Chaque problème inclut un petit ensemble de démonstration (~5 instances) pour le prompting few-shot et l'affinement itératif, et un ensemble d'évaluation plus large (des dizaines d'instances) pour les tests finaux.

Métriques d'évaluation

Pour répondre aux limites des métriques standards comme PASS@k, les auteurs proposent :

• SOLVEs@i : Suit la probabilité de résoudre un problème contraint en $i$ itérations, mesurant le succès lors du passage de trois étapes : Exécution (Étape I), Génération de solution (Étape II) et Vérification (Étape III).
• Indice de Qualité-Rendement (QYI) : Une métrique unifiée définie comme la moyenne harmonique de la Qualité (proximité de la solution avec une base experte) et du Rendement (proportion d'instances passant la vérification).
  • $Qualité = \frac{1}{\hat{N}} \sum \min(1, \frac{c^*_n}{c_n})$, où $c_n$ est le coût du LLM et $c^*_n$ le coût expert.
  • $Rendement = \frac{\hat{N}}{N}$, où $\hat{N}$ est le nombre de solutions vérifiées.
  • $QYI = \frac{(1 + \beta^2) \cdot Qualité \cdot Rendement}{(\beta^2 \cdot Qualité) + Rendement}$ (avec $\beta=1$).

Résultats clés

Les auteurs ont évalué neuf modèles de pointe (incluant GPT-o4-mini-high, Gemini-2.5-Pro, DeepSeek-R1 et des variantes LLaMA) sur le benchmark HeuriGym.

• Écart de performance : Même les modèles de premier plan peinent à atteindre un niveau de performance expert. Le meilleur modèle, Gemini-2.5-Pro, a obtenu un score QYI d'environ 0,62, indiquant que ses solutions sont, en moyenne, seulement 60 % aussi efficaces que les heuristiques conçues par des experts. Les autres modèles ont obtenu des scores nettement inférieurs (ex. LLaMA-3.3 et LLaMA-4-Maverick en dessous de 0,30).
• Amélioration itérative : L'augmentation du nombre d'itérations améliore significativement les performances. Par exemple, le taux de réussite de GPT-o4-mini-high (SOLVEIII) est passé de 53,2 % à l'itération 1 à 74,8 % à l'itération 10, soulignant l'importance de l'affinement itératif.
• Modes de défaillance : L'analyse a révélé des types d'échecs courants, notamment des hallucinations d'API, une logique algorithmique incorrecte, une mauvaise compréhension des contraintes et des dépassements de délai (timeouts).
• Cadres évolutionnaires : Les cadres de recherche évolutionnaire standard (ex. ReEvo, HSEvo) ont mal performé par rapport au modèle de base, échouant souvent à incorporer efficacement le feedback d'exécution et brisant le contexte à travers les itérations.

Signification et contributions

L'article revendique trois contributions principales :

1. Une suite de benchmarks open-source : Une collection de neuf problèmes d'optimisation combinatoire réalistes et à fort impact qui évaluent le raisonnement multi-étapes et les capacités de conception algorithmique, allant au-delà de la simple reconnaissance de motifs mémorisés.
2. Un cadre agentique de bout en bout : Un système supportant la génération de solutions, la vérification automatisée et l'affinement itératif, servant de banc d'essai pour les techniques de prompting avancées et les stratégies évolutionnaires.
3. Des enseignements empiriques : Une étude complète révélant que les LLM actuels, malgré leurs capacités de raisonnement, font face à des limitations persistantes en matière d'utilisation d'outils, de planification et de raisonnement adaptatif lorsqu'ils sont appliqués à des problèmes scientifiques et d'ingénierie complexes du monde réel.

Les auteurs positionnent HeuriGym comme une étape nécessaire pour guider le développement des LLM vers une résolution de problèmes plus efficace et réaliste dans des domaines où les solutions optimales ne sont tractables que pour de petites instances et où la découverte d'heuristiques est essentielle. Le benchmark vise à exposer l'écart entre les capacités actuelles des modèles et les exigences des flux de travail d'ingénierie pratiques, encourageant le développement de modèles capables d'une véritable invention d'heuristiques plutôt que d'une simple reconnaissance de formes.