Technische Samenvatting: Toewijzing van Rekenkracht bij Evolutionair Zoeken

Probleemstelling

Systemen voor evolutionair zoeken geleid door Large Language Models (LLM's) (bijvoorbeeld FunSearch, AlphaEvolve, CodeEvolve) hebben state-of-the-art resultaten behaald in wiskundige ontdekking en combinatorische optimalisatie. De bestaande literatuur rapporteert echter voornamelijk het beste resultaat uit een niet-gespecificeerd aantal runs, waardoor de verdeling van run-tot-run niet gedocumenteerd is. Bovendien variëren de gerapporteerde rekenkosten met groottenordes, wat het moeilijk maakt om de betrouwbaarheid van een enkele run onder een vast budget te beoordelen.

Het kernprobleem dat wordt aangepakt is toewijzing van rekenkracht: gegeven een vast budget aan LLM-aanroepen ($C$), hoe moet dit budget worden verdeeld tussen diepte (sequentiële verfijning van een enkele traject) en breedte (parallelle exploratie van meerdere trajecten)? Huidige systemen stellen deze hyperparameters vaak vast (bijvoorbeeld populatiegrootte en aantal generaties) zonder een systematisch inzicht in hoe de toewijzing de verwachte prestaties en betrouwbaarheid beïnvloedt.

Methodologie

1. Empirische Karakterisering van Diepte-Breedte Toewijzing

De auteurs voerden een systematische empirische studie uit over drie geometrische optimalisatietaken (Cirkelpacking, MinMaxDist, Heilbronn-driehoek) en vier modelgroottes (Qwen3-1.7B tot 14B, plus Llama-3.1-8B). Ze definieerden het toewijzingsprobleem als het splitsen van het budget $C$ in $T$ generaties van $N$ parallelle kinderen ($C = T \times N$).

• Fitness-Rekenkracht-omhullende: Ze analyseerden de relatie tussen bereikbare fitness en effectieve FLOPs (rekening houdend met modelgrootte en cache-efficiëntie). Ze observeerden dat hoewel grotere modellen bij gelijke aantallen aanroepen vooroplopen, hun prestatievolgorde grotendeels instort wanneer gemeten tegen effectieve FLOPs, mits het model-taakpaar "bekwaam" is.
• Diepte-Breedte Regulariteit: Ze pasten een parametrisch bilineair model aan op het fitnesslandschap:
  $$\log(1 - V) = \beta_0 + a \log T + b \log N + c \log T \log N$$
  waarbij $V$ de fitness is. De interactiecoëfficiënt $c$ bepaalt de geometrie van de optimale toewijzing:
  • Hoekoptima ($|c| \approx 0$): Taken zoals Cirkelpacking vertonen brede plateaus waar veel toewijzingen vergelijkbare resultaten opleveren, vaak met een voorkeur voor diepte.
  • Interne Ruggen ($c < 0$): Taken zoals MinMaxDist vertonen een scherpe rug waar een gebalanceerde mix van diepte en breedte vereist is voor optimale prestaties.
  • Bekwaamheidsbeperking: Deze regulariteiten gelden alleen voor modellen die een bekwaamheidsthorshold voor de specifieke taak hebben overschreden; zwakke modellen vertonen geen gestructureerde diepte-breedte trade-offs.

2. BaSE: Bandit-gebaseerd Zelf-evolueren

Gedreven door de hoge variantie in run-uitkomsten (waarbij identieke configuraties aanzienlijk verschillende eindfitnessscores produceren door stochasticiteit in het mutatieproces van de LLM), stelden de auteurs BaSE voor.

• Mechanisme: BaSE behandelt het evolutionaire zoeken als een Multi-Armed Bandit (MAB) probleem. In plaats van het volledige budget te besteden aan een enkel traject (Gierig) of een vast aantal eilanden (Eilandprotocol), onderhoudt BaSE $K$ parallelle trajecten.
• Adaptieve Toewijzing: Bij elke stap selecteert een banditalgoritme (UCB, EXP3.P of Thompson Sampling) welk traject wordt uitgebreid met de volgende LLM-aanroep. Dit routeert rekenkracht dynamisch weg van stagnerende runs naar veelbelovende.
• Orthogonaliteit: BaSE verandert het basismodel, de prompt of de logica voor ouder-selectie binnen een traject niet. Het werkt strikt op het niveau van toewijzing van middelen tussen trajecten.

Belangrijkste Resultaten

1. Empirische Regulariteiten

• Bekwaamheidsinstorting: Voor bekwame modellen wordt het prestatieomhulsel bepaald door effectieve FLOPs en niet alleen door modelgrootte.
• Taak-afhankelijke Geometrie: De optimale diepte-breedte-verdeling is niet universeel; deze hangt af van de "algoritmische familie" van de taak (bijvoorbeeld of de oplossing een specifieke bibliotheek zoals scipy vereist of een specifieke analytische constructie).
• Stochasticiteit: Zelfs met een vaste toewijzing variëren individuele runs aanzienlijk. Sommige runs convergeren naar hoge fitness, terwijl anderen vroeg stagneren door vast te komen zitten in een suboptimale algoritmische familie.

2. Prestaties van BaSE

• Gemiddelde Fitnessverbetering: Over 8 (model, taak) cellen verbeterde BaSE de gemiddelde beste fitness met 12,3% ten opzichte van de sterkste eilandprotocol-baselines (bijvoorbeeld OpenEvolve, CodeEvolve, ShinkaEvolve) zonder het model of de prompt te wijzigen.
• Betrouwbaarheidswinst: De meest significante winsten werden waargenomen in omgevingen met hoge variantie. Bijvoorbeeld, op de Heilbronn-driehoek-taak met Llama-3.1-8B faalden niet-BaSE-methoden vaak om geldige oplossingen te produceren (fitness $\approx 0$), terwijl BaSE (Thompson Sampling) een gemiddelde fitness van 0,4387 bereikte.
• Staal-efficiëntie: BaSE bereikte target-fitnessdrempels aanzienlijk sneller (minder generaties en FLOPs) dan gierige of vast-toegewezen baselines. Bijvoorbeeld, op MinMaxDist bereikte UCB een drempel van 0,95 in 92 generaties, terwijl de gierige baseline 485 vereiste.
• Ablatie: Matige poolgroottes voor armen ($K \in \{5, 10, 20\}$) boden de beste trade-off tussen diversiteit en diepte van verfijning.

Betekenis en Claims

Het artikel stelt dat toewijzing van rekenkracht een onderscheidende en kritische hefboom is voor het verbeteren van evolutionair zoeken geleid door LLM's, los van modelscaling of prompt-engineering.

• Toewijzing versus Engineering: De auteurs benadrukken dat hun verbeteringen niet het gevolg zijn van betere prompts of modellen. Sterker nog, ze merken op dat sommige baselines (zoals ShinkaEvolve) hoge scores op specifieke taken deels bereikten door prompt-geïnduceerde hints (bijvoorbeeld het suggereren van scipy.optimize), terwijl BaSE winsten uitsluitend behaalt door adaptieve resource-routing.
• Betrouwbaarheid: De primaire bijdrage is het verschuiven van de focus van "best-case" rapportage naar "verwachte" prestaties. BaSE biedt een winst in betrouwbaarheid, waardoor een gebruiker minder waarschijnlijk een vast budget verspilt aan een traject dat al is gestagneerd.
• Complementariteit: BaSE wordt gepresenteerd als complementair aan bestaande mechanismen binnen een run (zoals ouder-selectie). Het kan worden gelegd bovenop bestaande protocollen (Gierig, Eiland) om de prestaties verder te verbeteren, met name in instabiele omgevingen of omgevingen met hoge variantie.

Het werk concludeert dat hoewel modelbekwaamheid het plafond bepaalt voor wat haalbaar is, toewijzing bepaalt hoe efficiënt een methode dat plafond benadert, en dat adaptieve toewijzing via bandits een robuuste strategie is voor zoeken met een eindig budget.