Technische Samenvatting: SMCEVOLVE

Probleemstelling

LLM-gedreven programma-evolutie is een krachtig paradigma voor geautomatiseerde wetenschappelijke ontdekking, dat agenten in staat stelt om autonoom naar programma's te zoeken die doelstellingen optimaliseren in domeinen variërend van wiskundige ontdekking tot algoritme-efficiëntie. Bestaande kaders (bijv. AlphaEvolve, ShinkaEvolve) vertrouwen echter grotendeels op empirische, handgemaakte pijplijnen. Deze systemen missen een verenigend theoretisch kader, wat leidt tot verschillende kritieke beperkingen:

1. Gebrek aan Principieel Ontwerp: Componenten zoals ouderselectie, contextopbouw en populatiebeheer zijn geïsoleerd ontworpen en gevalideerd via uitgebreide ablatiestudies in plaats van afgeleid uit een coherent principe.
2. Geen Convergentiegaranties: Het zoekproces is niet gegarandeerd convergent, wat leidt tot hoge variantie tussen runs. Bovendien kunnen bestaande systemen geen onderscheid maken tussen echte convergentie naar een gebied met hoge beloning en stagnatie in een lokaal maximum, wat het gebruik van vaste iteratieaantallen dwingt die ofwel ontoereikend zijn of computationeel verspillend.

De centrale vraag die door dit werk wordt behandeld, is of LLM-gedreven programma-evolutie kan worden geworteld in een rigoureus probabilistisch kader dat zijn componenten verenigt en convergentiegaranties biedt.

Methodologie: SMCEVOLVE

De auteurs stellen SMCEVOLVE voor, een kader dat de zoektocht naar programma's met hoge beloning herformuleert als bemonstering uit een belonings-georiënteerde doelprior.

Theoretische Grondslag

Het probleem wordt geformuleerd als het vinden van een programma $x$ dat een beloning $R(x)$ maximaliseert, terwijl het voldoet aan een LLM-prior $p_0(x|q)$. Dit wordt gemodelleerd als een KL-geregulariseerd variatieel optimalisatieprobleem, waarvan de oplossing een doelprior is:
$$p^*(x | q) \propto p_0(x | q) e^{\beta R(x)}$$
waarbij $\beta$ de afweging controleert tussen de prior en beloningsmaximalisatie. Omdat directe bemonstering uit $p^*$ onhaalbaar is vanwege de normalisatieconstante en de enorme programmaruimte, benadert SMCEVOLVE dit met Sequential Monte Carlo (SMC)-bemonsteraars. De methode overbrugt de prior $p_0$ naar de doel $p^*$ via een reeks tussenliggende "overbruggings"-priors met toenemende beloningsintensiteit.

Kernmechanismen

Drie principiële mechanismen ontstaan rechtstreeks uit SMC-theorie om de evolutionaire lus te concretiseren:

1. Adaptieve Ouderherbemonstering:
   In plaats van vaste selectieregels worden ouders herbemonsterd op basis van belangsgewichten afgeleid uit de huidige overbruggingsprior. Het gewicht is een temperatuur-gebaseerde softmax over de deeltjesbeloningen:
   $$W_t^{(n)} \propto \exp\left((\beta_t - \beta_{t-1}) R(x_{t-1}^{(n)})\right)$$
   Vroeg in de zoektocht (lage $\beta_t$) is bemonstering bijna uniform om exploratie te stimuleren. Naarmate de zoektocht vordert en $\beta_t$ toeneemt, verscherpt de verdeling, waardoor herbemonstering focust op ouders met hoge beloningen om exploitatie te drijven.

2. Mixture van Mutatie met Acceptatie:
   Om ervoor te zorgen dat de mutatiekern voldoet aan de invariantie- en ergodische eigenschappen die vereist zijn voor SMC-convergentie, hanteert het kader een Metropolis–Hastings (MH) acceptatie-/verwerpmecanisme.

   • Voorgestelde Mixture: De LLM genereert voorstellen via een mixture van vier kernen, variërend langs twee assen: bewerkingsomvang (lokale diff versus volledige rewrite) en informatiebron (enkel-ouder versus cross-programma inspiratie).
   • Adaptieve Selectie: Thompson-sampling wordt gebruikt om adaptief te kiezen tussen deze kernen op basis van hun recente succes in het produceren van voorstellen met hoge beloning.
   • Acceptatie: Een kandidaat $x'$ wordt geaccepteerd met waarschijnlijkheid $\alpha_t(x, x') = \min\{1, e^{\beta_t(R(x') - R(x))}\}$. Deze benadering die alleen rekening houdt met de beloning wordt gebruikt omdat de volledige MH-ratio (die LLM-dichtheidsverhoudingen vereist) ontoegankelijk is via black-box API's.

3. Automatische Convergentiecontrole:
   Het aantal iteraties is niet van tevoren vastgesteld. In plaats daarvan wordt het temperatuurschema $\lambda_t$ (waarbij $\beta_t = \lambda_t \beta$) adaptief bepaald met behulp van de Effective Sample Size (ESS). Het systeem verhoogt $\lambda_t$ in stappen totdat de ESS onder een drempelwaarde $\kappa N$ zakt, wat aangeeft dat de populatie zich concentreert op gebieden met hoge beloning. Het proces stopt automatisch wanneer $\lambda_t = 1$, waardoor wordt gegarandeerd dat de zoektocht stopt zodra de doelprior is bereikt.

Complexiteit bij Beperkte Steekproeven

Het artikel biedt een theoretische analyse die de totale LLM-aanroepbegroting $B = N \times T \times K$ (deeltjes $\times$ stadia $\times$ mutatiestappen) begrenst die nodig is om een doelbenaderingsfout $\epsilon$ te bereiken. De grens hangt af van de beloningsoscillatie $\Delta R$, het mengsnelheid van de mutatiekern $\rho$, en de ESS-drempel $\kappa$:
$$B = \tilde{O}\left( \frac{\epsilon^{-2} \vee \kappa^{-1}}{1 - \rho} \cdot \beta \Delta R \right)$$

Experimentele Resultaten

SMCEVOLVE werd geëvalueerd in vier diverse domeinen:

1. Wiskunde: Combinatorische meetkundeproblemen (bijv. Cirkelpakking, Heilbronn-driehoek).
2. Algoritme-efficiëntie: Runtime-optimalisatietaken (bijv. FFT, LU-factorisatie).
3. Symbolische Regressie: Ontdekking van wetenschappelijke vergelijkingen (bijv. biologische groei, chemische reacties).
4. End-to-End ML: Geautomatiseerde GPT-pretraining op de TinyStories-dataset.

Belangrijkste Bevindingen:

• Prestaties: SMCEVOLVE overtrof state-of-the-art evoluerende systemen (REEVO, OPENEVOLVE, SHINKAEVOLVE) op het merendeel van de taken in alle domeinen.
• Efficiëntie: Ondanks het behalen van hogere beloningen, gebruikte SMCEVOLVE minder LLM-aanroepen dan de baselines. Deze winst in efficiëntie wordt toegeschreven aan het automatische stopmechanisme, dat de verspillende runs met vaste iteraties van de baselines vermijdt.
• Ablatie: Het verwijderen van adaptieve herbemonstering (vervangen door uniforme of greedige selectie) of de mixture van mutatiekernen (vervangen door enkele kernen) degradeerde de prestaties aanzienlijk, wat de noodzaak bevestigt van de voorgestelde gekoppelde mechanismen.

Betekenis en Claims

Het artikel claimt het eerste principiële kader te bieden voor LLM-gedreven programma-evolutie waarbij componenten zijn afgeleid uit SMC-theorie in plaats van handgemaakte heuristieken. De primaire bijdragen zijn:

1. Verenigd Kader: Het vestigt een rigoureuze probabilistische visie op programma-evolutie, die ouderherbemonstering, mutatie en convergentiecontrole verenigt onder één SMC-paraplu.
2. Convergentiegaranties: Het biedt de eerste convergentieanalyse voor beperkte steekproeven voor evolutionaire programmazoektochten, met expliciete grenzen voor de computatiekosten die nodig zijn om een doelbenaderingsfout te bereiken.
3. Praktische Efficiëntie: Door vaste iteratieaantallen te vervangen door adaptieve, ESS-gedreven stopcondities, bereikt het kader state-of-the-art prestaties terwijl het de computationele overhead verlaagt.

De auteurs positioneren SMCEVOLVE niet als vervanging voor alle bestaande agenten, maar als een generalisatie waarbij bestaande methoden kunnen worden beschouwd als speciale gevallen (bijv. vaste $\beta$, enkele mutatiestrategie, vaste $T$). Het werk suggereert dat het grondvesten van evolutionaire zoektochten in probabilistische bemonsteringstheorie een weg biedt naar betrouwbaardere en efficiëntere geautomatiseerde wetenschappelijke ontdekking.