FrugalEvo : évolution de programmes guidée par LLM et attentive au coût

Contexte et problématique

Les méthodes évolutionnaires guidées par des LLM, comme AlphaEvolve, sont devenues une approche solide pour des problèmes d'optimisation difficiles, dont l'empaquetage de cercles. La boucle est simple. Un modèle de langage propose une modification d'un programme existant. Une fonction d'évaluation note le nouveau programme. Les bons programmes restent dans la population, et le tour suivant repart d'eux. Les travaux précédents comparent en général les méthodes par le gain obtenu après un nombre fixe d'itérations. Cette comparaison a un angle mort : elle ignore l'argent. Deux exécutions avec le même nombre d'itérations peuvent coûter des sommes très différentes. Un modèle plus fort coûte plus cher par appel, produit un raisonnement plus long et accumule un contexte plus large. Fixer le budget en itérations cache tout cela.

Les auteurs de FrugalEvo défendent un objectif plus pratique : maximiser le gain par unité de coût. Le contraste donné dans le résumé est net. Les méthodes multi-agents comme CORAL et SwarmResearch coûtent environ 50 USD en moyenne pour l'empaquetage de cercles. FrugalEvo annonce 1,68 USD et 0,55 USD pour des résultats égaux ou meilleurs. Si ces chiffres tiennent, la question change : il ne s'agit plus de savoir si l'on trouve une bonne solution, mais de savoir combien elle coûte. Précision sur le périmètre : cette analyse repose uniquement sur le résumé de l'article. Les détails que le résumé ne donne pas, comme les invites exactes, les taux de succès du cache ou les scores absolus par tâche, ne sont pas déduits ici.

Architecture et principes techniques

Le résumé décrit trois éléments qui fonctionnent ensemble. Le premier est une répartition du travail entre deux modèles. Un LLM plus fort et plus cher explore les stratégies de résolution. Il décide de la direction à prendre. Un LLM moins cher met ces stratégies en œuvre sous forme de code, puis affine ce code au fil des itérations. Cette répartition suppose que les étapes d'une évolution n'exigent pas la même capacité. Choisir une stratégie demande du jugement. Écrire et polir du code profite de nombreux essais bon marché. Réserver les appels coûteux à quelques décisions clés est la principale source d'économie.

Le deuxième est un processus d'évolution efficace pour le cache. Les services de LLM mettent souvent en cache les préfixes d'entrée répétés, et une entrée en cache est moins chère et plus rapide. Dans FrugalEvo, le harnais et les invites sont conçus pour que les différentes étapes partagent le plus long préfixe possible. C'est un choix d'ingénierie, mais dans un contexte sensible au coût, il se voit directement sur la facture. Le troisième est une nouvelle mesure, l'aire sous la courbe consciente du budget, ou BA-AUC. On trace le meilleur score obtenu jusque-là en fonction du coût cumulé des appels LLM, puis on prend l'aire sous cette courbe jusqu'au budget. La mesure récompense deux choses : un score final élevé, et l'obtention rapide de bons scores. Une comparaison sur le seul score final peut favoriser une méthode qui dépense dix fois plus pour gagner un peu. La BA-AUC rend cette différence visible.

Évaluation pratique et applications

D'après le résumé, l'évaluation porte sur 10 tâches d'optimisation mathématiques et système. FrugalEvo égale ou dépasse OpenEvolve, ShinkaEvolve, AdaEvolve et EvoX sur la qualité finale de la solution, et obtient une BA-AUC plus élevée sur 9 tâches. En lecture inverse, il existe une tâche où sa BA-AUC n'est pas supérieure, et le résumé ne dit pas laquelle.

Sur les 10 tâches d'optimisation algorithmique d'ALE-Bench-Lite, FrugalEvo atteint aussi une performance moyenne supérieure à celle de ces mêmes références.

Le résultat le plus frappant concerne l'empaquetage de cercles. Avec GPT-5.6 Terra et Luna, le coût est de 1,68 USD. Avec GLM-5.3 et sa variante Flash, il est de 0,55 USD. Les deux configurations égalent ou dépassent toutes les références et établissent un nouvel état de l'art sur cette tâche, selon l'article. Deux réserves s'imposent. Le « nouvel état de l'art » est une affirmation des auteurs et demande une reproduction indépendante. Les 50 USD des méthodes multi-agents sont une moyenne, et la comparabilité complète des coûts entre méthodes dépend du protocole décrit dans le corps de l'article.

Impact sur l'industrie et perspectives

L'intérêt de ce travail tient moins à un score précis qu'à l'intégration du coût dans l'évaluation. La recherche évolutionnaire de programmes sert de plus en plus à la découverte d'algorithmes, au réglage de systèmes et à l'aide à la recherche. Quand une expérience coûte des dizaines de dollars, seules les équipes bien financées peuvent la mener. À un ou deux dollars, des chercheurs isolés et de petites équipes peuvent aussi lancer des recherches complètes.

Les praticiens peuvent en tirer trois leçons. Une hiérarchie entre modèle fort et modèle bon marché est un moyen général d'économiser, pas seulement pour la recherche évolutionnaire. La stabilité des préfixes dans les invites doit être une contrainte de conception dès le départ, pas une optimisation tardive. Enfin, pour juger un système de recherche automatisée, il faut publier la courbe de coût et pas seulement le score final.

Les limites sont claires. Dix plus dix tâches forment un échantillon modeste, et l'on ignore jusqu'où le résultat s'étend à des problèmes plus ouverts. La meilleure paire de modèles dépend des prix actuels et peut changer avec eux. Les valeurs de BA-AUC dépendent aussi du plafond de budget choisi. À surveiller ensuite : la reproduction indépendante, davantage de types de tâches, et la façon dont l'information circule entre le modèle de stratégie et le modèle d'implémentation.