Résumé technique : Allocation de ressources de calcul dans la recherche évolutionnaire

Énoncé du problème

Les systèmes de recherche évolutionnaire guidés par des modèles de langage de grande taille (LLM) (par exemple, FunSearch, AlphaEvolve, CodeEvolve) ont obtenu des résultats de pointe en découverte mathématique et en optimisation combinatoire. Cependant, la littérature existante rapporte principalement le seul meilleur résultat parmi un nombre indéterminé d'exécutions, laissant la distribution d'une exécution à l'autre non documentée. De plus, les coûts de calcul rapportés varient de plusieurs ordres de grandeur, rendant difficile l'évaluation de la fiabilité d'une seule exécution sous un budget fixe.

Le problème central abordé est l'allocation de ressources de calcul : étant donné un budget fixe d'appels LLM ($C$), comment ce budget doit-il être réparti entre la profondeur (affinement séquentiel d'une seule trajectoire) et la largeur (exploration parallèle de multiples trajectoires) ? Les systèmes actuels fixent souvent ces hyperparamètres (par exemple, taille de la population et nombre de générations) sans une compréhension systématique de la manière dont l'allocation affecte la performance attendue et la fiabilité.

Méthodologie

1. Caractérisation empirique de l'allocation profondeur-largeur

Les auteurs ont mené une étude empirique systématique sur trois tâches d'optimisation géométrique (Packing de cercles, MinMaxDist, Triangle de Heilbronn) et quatre tailles de modèles (Qwen3-1.7B à 14B, plus Llama-3.1-8B). Ils ont défini le problème d'allocation comme la division du budget $C$ en $T$ générations de $N$ enfants parallèles ($C = T \times N$).

• Enveloppe Fitness-Compute : Ils ont analysé la relation entre le fitness atteignable et les FLOPs effectifs (tenant compte de la taille du modèle et de l'efficacité du cache). Ils ont observé que, bien que les modèles plus grands soient en tête à nombre d'appels égal, leur ordre de performance s'effondre largement lorsqu'il est mesuré par rapport aux FLOPs effectifs, à condition que la paire modèle-tâche soit « capable ».
• Régularité profondeur-largeur : Ils ont ajusté un modèle bilinéaire paramétrique au paysage de fitness :
  $$\log(1 - V) = \beta_0 + a \log T + b \log N + c \log T \log N$$
  où $V$ est le fitness. Le coefficient d'interaction $c$ détermine la géométrie de l'allocation optimale :
  • Optima aux coins ($|c| \approx 0$) : Des tâches comme le Packing de cercles présentent de larges plateaux où de nombreuses allocations produisent des résultats similaires, favorisant souvent la profondeur.
  • Crêtes intérieures ($c < 0$) : Des tâches comme MinMaxDist présentent une crête nette où un mélange équilibré de profondeur et de largeur est requis pour une performance optimale.
  • Filtrage par capacité : Ces régularités ne s'appliquent qu'aux modèles ayant franchi un seuil de capacité pour la tâche spécifique ; les modèles faibles ne parviennent pas à manifester des compromis structurés profondeur-largeur.

2. BaSE : Bandit-based Self-Evolving (Auto-évolution basée sur les bandits)

Motivés par la forte variance des résultats d'exécution (où des configurations identiques produisent des scores de fitness finaux très différents en raison de la stochasticité du processus de mutation du LLM), les auteurs ont proposé BaSE.

• Mécanisme : BaSE traite la recherche évolutionnaire comme un problème de Bandit Multi-Arme (MAB). Au lieu de consacrer l'intégralité du budget à une seule trajectoire (Gourou) ou à un ensemble fixe d'îles (protocole Island), BaSE maintient $K$ trajectoires parallèles.
• Allocation adaptative : À chaque étape, un algorithme de bandit (UCB, EXP3.P ou Échantillonnage de Thompson) sélectionne quelle trajectoire étendre avec l'appel LLM suivant. Cela achemine dynamiquement les ressources de calcul loin des exécutions stagnantes vers celles qui sont prometteuses.
• Orthogonalité : BaSE ne modifie pas le modèle de base, l'invite (prompt) ou la logique d'échantillonnage des parents au sein d'une trajectoire. Il opère strictement au niveau de l'allocation des ressources entre trajectoires.

Résultats clés

1. Régularités empiriques

• Effondrement de capacité : Pour les modèles capables, l'enveloppe de performance est déterminée par les FLOPs effectifs plutôt que par la taille du modèle seule.
• Géométrie dépendante de la tâche : La répartition optimale profondeur-largeur n'est pas universelle ; elle dépend de la « famille algorithmique » de la tâche (par exemple, si la solution nécessite une bibliothèque spécifique comme scipy ou une construction analytique spécifique).
• Stochasticité : Même avec une allocation fixe, les exécutions individuelles varient considérablement. Certaines convergent vers un fitness élevé, tandis que d'autres stagnent tôt en se verrouillant sur une famille algorithmique sous-optimale.

2. Performance de BaSE

• Amélioration du fitness moyen : Sur 8 cellules (modèle, tâche), BaSE a amélioré le meilleur fitness moyen de 12,3 % par rapport aux meilleures baselines de protocole d'îles (par exemple, OpenEvolve, CodeEvolve, ShinkaEvolve) sans changer le modèle ni l'invite.
• Gains de fiabilité : Les gains les plus significatifs ont été observés dans des contextes à forte variance. Par exemple, sur la tâche Triangle de Heilbronn avec Llama-3.1-8B, les méthodes non-BaSE ont souvent échoué à produire des solutions valides (fitness $\approx 0$), tandis que BaSE (Échantillonnage de Thompson) a atteint un fitness moyen de 0,4387.
• Efficacité d'échantillonnage : BaSE a atteint les seuils de fitness cible significativement plus vite (moins de générations et de FLOPs) que les baselines gourmandes ou à allocation fixe. Par exemple, sur MinMaxDist, UCB a atteint un seuil de 0,95 en 92 générations, tandis que la baseline gourmande en a requis 485.
• Ablation : Des tailles de pool d'armes modérées ($K \in \{5, 10, 20\}$) ont offert le meilleur compromis entre diversité et profondeur d'affinement.

Signification et revendications

L'article revendique que l'allocation de ressources de calcul est un levier distinct et critique pour améliorer la recherche évolutionnaire guidée par LLM, séparé de la mise à l'échelle des modèles ou de l'ingénierie des invites.

• Allocation vs Ingénierie : Les auteurs soulignent que leurs améliorations ne sont pas dues à de meilleures invites ou modèles. En fait, ils notent que certaines baselines (comme ShinkaEvolve) ont obtenu des scores élevés sur des tâches spécifiques en partie grâce à des indices induits par l'invite (par exemple, suggérant scipy.optimize), alors que BaSE obtient des gains purement par le routage adaptatif des ressources.
• Fiabilité : La contribution principale est de déplacer l'accent du rapport du « meilleur cas » vers la performance « attendue ». BaSE fournit un gain de fiabilité, garantissant qu'un praticien est moins susceptible de gaspiller un budget fixe sur une trajectoire qui a déjà stagné.
• Complémentarité : BaSE est présenté comme complémentaire aux mécanismes existants au sein d'une exécution (comme l'échantillonnage des parents). Il peut être superposé aux protocoles existants (Gourou, Island) pour améliorer davantage la performance, en particulier dans des contextes instables ou à forte variance.

L'étude conclut que, si la capacité du modèle fixe le plafond de ce qui est réalisable, l'allocation régit la manière dont efficacement une méthode approche ce plafond, et l'allocation adaptative via des bandits est une stratégie robuste pour la recherche à budget fini.