Résumé Technique : Découverte d'Algorithmes avec les LLM : La Recherche Évolutive Rencontre l'Apprentissage par Renforcement

Énoncé du Problème

La découverte d'algorithmes efficaces pour des problèmes complexes, en particulier en mathématiques et en optimisation combinatoire, a historiquement reposé sur une expertise humaine substantielle. Bien que les récents progrès des Modèles de Langage à Grande Échelle (LLM) combinés à la recherche évolutive (par exemple, la méthode FunSearch) aient montré des promesses pour automatiser cette découverte, les approches existantes traitent le LLM comme un générateur statique. Ces méthodes utilisent le LLM pour proposer de nouveaux programmes basés sur des succès antérieurs, mais échouent à mettre à jour les paramètres internes du modèle en fonction des signaux obtenus lors de l'exploration évolutive. Par conséquent, elles manquent l'opportunité de tirer parti de la nature paramétrique du LLM pour affiner sa politique de recherche au fil du temps, ce qui peut entraîner une convergence sous-optimale ou une exploration inefficace de l'espace des solutions.

Méthodologie : EvoTune

Les auteurs proposent EvoTune, un cadre qui intègre étroitement la recherche évolutive avec l'Apprentissage par Renforcement (RL) pour affiner continuellement l'opérateur de recherche du LLM. La méthode fonctionne dans une boucle itérative composée de deux phases alternées :

1. Recherche Évolutive (Exploration) :

   • Le LLM génère des programmes Python candidats (algorithmes) basés sur des invites construites à partir de programmes à haut score découverts lors des itérations précédentes.
   • Ces programmes sont évalués sur des tâches spécifiques d'optimisation combinatoire (par exemple, Bin Packing, Traveling Salesman Problem, Flatpack) pour obtenir des scores de récompense (généralement l'écart d'optimalité négatif).
   • Les programmes valides et leurs scores sont stockés dans une base de données de programmes, organisés en « îles » pour maintenir la diversité et prévenir une convergence prématurée.
   • La recherche emploie une stratégie de « bootstrapping », où le LLM analyse les différences entre les programmes à haute performance et ceux à faible performance pour guider la génération de nouveaux candidats.

2. Entraînement RL (Affinement) :

   • Périodiquement (toutes les $f_{RL}$ itérations), la politique de génération du LLM ($\pi_\theta$) est mise à jour en utilisant les données accumulées de la recherche évolutive.
   • Les auteurs formulent cela comme un problème d'Optimisation des Préférences. Ils construisent un jeu de données de préférences $D_{pref}$ composé de triplets $(x, y^+, y^-)$, où $x$ est l'invite, $y^+$ est un programme avec une récompense plus élevée, et $y^-$ est un programme avec une récompense plus faible.
   • Le modèle est affiné en utilisant l'Optimisation Directe des Préférences (DPO). Contrairement au DPO hors ligne standard, EvoTune fonctionne dans un cadre hors politique où les données sont générées dynamiquement par le modèle évolutif lui-même.
   • Préservation de la Diversité : Un choix de conception critique est l'utilisation de la régularisation KL Forward (par opposition au KL Reverse plus courant) dans l'objectif DPO. Cela encourage un comportement de « couverture de masse », empêchant le modèle de s'effondrer vers un seul mode et préservant la diversité des sorties essentielle pour une recherche évolutive efficace.

Contributions Clés

1. Intégration du RL dans la Recherche Évolutive : L'article prétend être le premier à démontrer le potentiel d'une intégration étroite de la recherche évolutive basée sur les LLM avec l'affinement par RL dans la boucle. Contrairement aux méthodes précédentes utilisant les LLM uniquement comme générateurs statiques, EvoTune met à jour les poids du modèle pour mieux exploiter les insights acquis lors de l'exploration.
2. Accélération de la Découverte d'Algorithmes : En affinant la politique de recherche via le RL, la méthode accélère la découverte d'algorithmes supérieurs. Les expériences sur trois LLM entraînés sur des instructions (Llama3.2 1B, Phi 3.5 Mini, Granite 3.1 2B) montrent des gains de performance constants par rapport à la méthode de référence FunSearch.
3. Alignement Préservant la Diversité : Les auteurs démontrent l'avantage d'utiliser un objectif d'alignement modifié (DPO régularisé par KL Forward) pour préserver la diversité des sorties. Cela est crucial pour les stratégies évolutives, car un effondrement de mode peut entraver la découverte de solutions novatrices.
4. Applicabilité Large : La méthode est validée sur des benchmarks divers, incluant des problèmes combinatoires standards (Bin Packing, TSP, Flatpack), des défis Google Hash Code réels (Optimisation de Datacenter, Trajets de Conduite Autonome), et des tâches de régression symbolique (LLM-SR).

Résultats Expérimentaux

Les auteurs ont évalué EvoTune par rapport à une baseline de style FunSearch (recherche évolutive sans entraînement de modèle) sur plusieurs tâches et modèles :

• Gains de Performance : EvoTune a constamment obtenu des scores de récompense finale plus élevés (écarts d'optimalité plus faibles) pour les 50 programmes découverts en tête par rapport à la baseline. L'écart de performance s'est souvent élargi à mesure que le budget d'échantillonnage augmentait, suggérant que des budgets plus importants amplifient les avantages de la méthode.
• Généralisation : Les programmes évolués ont démontré une robustesse sur des ensembles de validation perturbés et des ensembles de test tirés de la même distribution, indiquant que les politiques apprises généralisent au-delà des instances spécifiques rencontrées lors de l'entraînement.
• Benchmarks Réels :
  • Sur la tâche Google Hash Code Datacenter Optimization, EvoTune a obtenu un score de 418, surpassant le meilleur score humain de 407 et dépassant la baseline FunSearch (414).
  • Sur les tâches de Régression Symbolique (LLM-SR), EvoTune a surpassé la baseline évolutive et, notablement, a dépassé les bases utilisant des modèles plus grands ou propriétaires (par exemple, Mixtral 8x7B, GPT-3.5-turbo) tout en utilisant un modèle plus petit (Phi-3.5 Mini, 3,8 milliards de paramètres).
• Études d'Ablation :
  • KL Forward vs KL Reverse : Les expériences ont confirmé que la régularisation KL Forward produit des récompenses plus élevées et un plus grand nombre de solutions uniques par rapport au KL Reverse, validant l'importance de la préservation de la diversité.
  • RL Alternatif : Les auteurs ont testé ReSTEM (Affinement Supervisé sur les sorties à haut score) comme alternative au DPO. Les résultats ont indiqué que le DPO surpassait constamment ReSTEM et était moins sensible au réglage des hyperparamètres.

Signification et Revendications

L'article positionne EvoTune comme une étape significative en avant dans la conception automatisée d'algorithmes en abordant la « Bitter Lesson » (Sutton, 2019), qui soutient que la recherche et l'apprentissage sont synergiques. Les auteurs affirment que :

• Synergie : La recherche génère de nouvelles données, tandis que l'apprentissage distille des motifs à partir de ces données pour guider l'exploration future plus efficacement.
• Efficacité : L'intégration du RL permet au système de dépasser la simple augmentation du score moyen d'une population ; il guide activement la recherche évolutive vers des solutions supérieures (mesurées par la performance top-k) tout en maintenant la diversité requise pour l'innovation.
• Évolutivité : La méthode démontre un potentiel pour s'adapter à des environnements réels, comme en témoigne son succès sur des problèmes complexes et non synthétiques tels que l'optimisation de datacenters et la modélisation contrainte-déformation.

Les auteurs reconnaissent modestement les limites, notant que leurs expériences ont été menées avec des modèles allant de 1 milliard à 3,8 milliards de paramètres et qu'un passage à l'échelle supplémentaire de la taille des modèles et des budgets d'échantillonnage est nécessaire pour comprendre pleinement le potentiel de la méthode. Ils soulignent également le compromis entre les coûts de calcul supplémentaires de la phase d'entraînement RL et les gains en efficacité d'inférence et en qualité de solution.