Résumé Technique : SMCEVOLVE

Énoncé du Problème

L'évolution de programmes pilotée par les LLM (Large Language Models) est devenue un paradigme puissant pour la découverte scientifique automatisée, permettant à des agents de rechercher de manière autonome des programmes optimisant des objectifs cibles dans des domaines allant de la découverte mathématique à l'efficacité algorithmique. Cependant, les cadres existants (par exemple, AlphaEvolve, ShinkaEvolve) reposent sur des pipelines largement empiriques et conçus à la main. Ces systèmes manquent d'un cadre théorique unificateur, ce qui entraîne plusieurs limitations critiques :

1. Absence de Conception Principielle : Des composants tels que la sélection des parents, la construction du contexte et la gestion de la population sont conçus de manière isolée et validés par des études d'ablation extensives plutôt que dérivés d'un principe cohérent.
2. Absence de Garanties de Convergence : Le processus de recherche n'est pas garanti de converger, entraînant une forte variance entre les exécutions. De plus, les systèmes existants ne peuvent pas distinguer entre une convergence réelle vers une région à haute récompense et une stagnation dans un mode local, ce qui force l'utilisation de comptes d'itérations fixes qui sont soit insuffisants, soit gaspilleurs en termes de calcul.

La question centrale abordée par ce travail est de savoir si l'évolution de programmes pilotée par les LLM peut être ancrée dans un cadre probabiliste rigoureux qui unifie ses composants et fournit des garanties de convergence.

Méthodologie : SMCEVOLVE

Les auteurs proposent SMCEVOLVE, un cadre qui reformule la recherche de programmes à haute récompense comme un échantillonnage à partir d'une distribution cible inclinée par la récompense.

Fondement Théorique

Le problème est formulé comme la recherche d'un programme $x$ maximisant une récompense $R(x)$ tout en adhérant à une a priori LLM $p_0(x|q)$. Ceci est modélisé comme un problème d'optimisation variationnelle régularisé par la divergence de Kullback-Leibler (KL), dont la solution est une distribution cible :
$$p^*(x | q) \propto p_0(x | q) e^{\beta R(x)}$$
où $\beta$ contrôle le compromis entre l'a priori et la maximisation de la récompense. Étant donné que l'échantillonnage direct à partir de $p^*$ est intraitable en raison de la constante de normalisation et de l'immensité de l'espace des programmes, SMCEVOLVE approxime cela en utilisant des échantillonneurs Monte Carlo Séquentiel (SMC). La méthode fait le pont entre l'a priori $p_0$ et la cible $p^*$ à travers une séquence de distributions intermédiaires « pontantes » avec une intensité de récompense croissante.

Mécanismes Principaux

Trois mécanismes principiels émergent directement de la théorie SMC pour instancier la boucle évolutive :

1. R échantillonnage Adaptatif des Parents :
   Au lieu de règles de sélection fixes, les parents sont rééchantillonnés en fonction de poids d'importance dérivés de la distribution de pontage actuelle. Le poids est un softmax basé sur la température sur les récompenses des particules :
   $$W_t^{(n)} \propto \exp\left((\beta_t - \beta_{t-1}) R(x_{t-1}^{(n)})\right)$$
   Au début de la recherche (faible $\beta_t$), l'échantillonnage est presque uniforme pour encourager l'exploration. À mesure que la recherche progresse et que $\beta_t$ augmente, la distribution s'affine, concentrant le rééchantillonnage sur les parents à haute récompense pour favoriser l'exploitation.

2. Mélange de Mutation avec Acceptation :
   Pour garantir que le noyau de mutation satisfait les propriétés d'invariance et d'ergodicité requises pour la convergence SMC, le cadre emploie un mécanisme d'acceptation/rejet Metropolis–Hastings (MH).

   • Mélange de Propositions : Le LLM génère des propositions via un mélange de quatre noyaux, variant selon deux axes : l'étendue de l'édition (diff local vs rewrite complet) et la source d'information (parent unique vs inspiration inter-programme).
   • Sélection Adaptative : L'échantillonnage de Thompson est utilisé pour sélectionner de manière adaptative parmi ces noyaux en fonction de leur succès récent à produire des propositions à haute récompense.
   • Acceptation : Un candidat $x'$ est accepté avec une probabilité $\alpha_t(x, x') = \min\{1, e^{\beta_t(R(x') - R(x))}\}$. Cette approximation basée uniquement sur la récompense est utilisée car le ratio complet MH (nécessitant des ratios de densité LLM) est inaccessible via des API en boîte noire.

3. Contrôle Automatique de la Convergence :
   Le nombre d'itérations n'est pas fixé à l'avance. Au lieu de cela, le programme de température $\lambda_t$ (où $\beta_t = \lambda_t \beta$) est déterminé de manière adaptative en utilisant la Taille d'Échantillon Effective (ESS). Le système augmente $\lambda_t$ par étapes jusqu'à ce que l'ESS descende en dessous d'un seuil $\kappa N$, indiquant que la population se concentre sur des régions à haute récompense. Le processus se termine automatiquement lorsque $\lambda_t = 1$, garantissant que la recherche s'arrête une fois la distribution cible atteinte.

Complexité à Échantillon Fini

L'article fournit une analyse théorique bornant le budget total d'appels LLM $B = N \times T \times K$ (particules $\times$ étapes $\times$ étapes de mutation) nécessaire pour atteindre une erreur d'approximation cible $\epsilon$. La borne dépend de l'oscillation de la récompense $\Delta R$, du taux de mélange du noyau de mutation $\rho$, et du seuil ESS $\kappa$ :
$$B = \tilde{O}\left( \frac{\epsilon^{-2} \vee \kappa^{-1}}{1 - \rho} \cdot \beta \Delta R \right)$$

Résultats Expérimentaux

SMCEVOLVE a été évalué sur quatre domaines diversifiés :

1. Mathématiques : Problèmes de géométrie combinatoire (par exemple, Empilement de cercles, Triangle de Heilbronn).
2. Efficacité Algorithmique : Tâches d'optimisation du temps d'exécution (par exemple, FFT, factorisation LU).
3. Régression Symbolique : Découverte d'équations scientifiques (par exemple, croissance biologique, réactions chimiques).
4. ML de Bout en Bout : Pré-entraînement automatisé de GPT sur le jeu de données TinyStories.

Principales Constatations :

• Performance : SMCEVOLVE a surpassé les systèmes évolutifs de l'état de l'art (REEVO, OPENEVOLVE, SHINKAEVOLVE) sur la majorité des tâches dans tous les domaines.
• Efficacité : Malgré l'obtention de récompenses plus élevées, SMCEVOLVE a utilisé moins d'appels LLM que les lignes de base. Ce gain d'efficacité est attribué au mécanisme d'arrêt automatique, qui évite les exécutions à itérations fixes et gaspilleuses des lignes de base.
• Ablation : La suppression du rééchantillonnage adaptatif (remplacé par une sélection uniforme ou gloutonne) ou du mélange de noyaux de mutation (remplacé par des noyaux uniques) a considérablement dégradé les performances, confirmant la nécessité des mécanismes couplés proposés.

Importance et Revendications

L'article revendique fournir le premier cadre principiel pour l'évolution de programmes pilotée par les LLM où les composants sont dérivés de la théorie SMC plutôt que d'heuristiques conçues à la main. Ses contributions principales sont :

1. Cadre Unifié : Il établit une vue probabiliste rigoureuse de l'évolution de programmes, unifiant le rééchantillonnage des parents, la mutation et le contrôle de la convergence sous une seule bannière SMC.
2. Garanties de Convergence : Il offre la première analyse de convergence à échantillon fini pour la recherche de programmes évolutifs, fournissant des bornes explicites sur le coût computationnel requis pour atteindre une erreur d'approximation cible.
3. Efficacité Pratique : En remplaçant les comptes d'itérations fixes par un arrêt adaptatif piloté par l'ESS, le cadre atteint des performances de l'état de l'art tout en réduisant la surcharge computationnelle.

Les auteurs positionnent SMCEVOLVE non pas comme un remplacement pour tous les agents existants, mais comme une généralisation où les méthodes existantes peuvent être considérées comme des cas particuliers (par exemple, $\beta$ fixe, stratégie de mutation unique, $T$ fixe). Le travail suggère que l'ancrage de la recherche évolutive dans la théorie de l'échantillonnage probabiliste offre une voie vers une découverte scientifique automatisée plus fiable et efficace.