Technische Samenvatting: LLaMEA-SAGE

Probleemstelling

Geautomatiseerd Algoritme Ontwerp (Automated Algorithm Design, AAD) met behulp van Large Language Models (LLMs) is een veelbelovend paradigma geworden voor het ontdekken van optimalisatiealgoritmen direct vanuit natuurlijke taalprompts. De huidige LLM-gebaseerde benaderingen, zoals LLaMEA, vertrouwen echter bijna uitsluitend op fitness-feedback (prestaties op benchmarks) om de evolutionaire zoektocht te sturen. Deze "black-box"-feedbackloop laat een aanzienlijke hoeveelheid informatie binnen de gegenereerde code onbenut. Bijgevolg hebben zoekstrategieën vaak moeite met het balanceren van exploratie en exploitatie in grote, heterogene coderuimtes, wat leidt tot voortijdige stagnatie of inefficiënt gebruik van dure LLM-queries. Bovendien is er beperkte kennis over hoe men door de mens gegenereerde algoritmen systematisch kan verbeteren na de initiële generatie en hoe deze verbeteringen zich verhouden tot state-of-the-art (SOTA) methoden onder gecontroleerde benchmarks.

Methodologie: LLaMEA-SAGE

Het paper stelt LLaMEA-SAGE voor, een framework dat gestructureerde, uitlegbare AI (XAI)-feedback integreert in het LLaMEA-evolutionaire ontwerpproces. Het kernmechanisme bestaat uit het extraheren van structurele kenmerken uit de code van kandidaat-algoritmen en het gebruiken van deze kenmerken om daaropvolgende mutaties te sturen.

1. Extractie van Structurele Kenmerken

Elk kandidaat-algoritme wordt gerepresenteerd als uitvoerbare Python-code. Het systeem parseert de code naar een Abstract Syntax Tree (AST) om een gerichte graaf te construeren. Vanuit deze graaf extraheert het systeem een rijke set kenmerken, waaronder:

• Grafentheoretische statistieken: Aantal knopen/randen, graadstatistieken (gemiddelde, variantie, entropie), boomdiepte, clusteringcoëfficiënten en pad-gebaseerde metrieken (diameter, gemiddeld kortste pad).
• Complexiteitsindicatoren: Cyclomatische complexiteit, functie-tokenaantallen en parameteraantallen geaggregeerd over functies.

2. Archief-gebaseerde Surrogaatmodellering

Tijdens het evolutionaire proces worden alle geëvalueerde oplossingen, hun fitness-scores en hun geëxtraheerde codekenmerken opgeslagen in een archief. Zodra een minimaal archiefformaat is bereikt, wordt een gradient-boosted regression tree model (XGBoost) getraind om de relatie tussen codekenmerken en geobserveerde fitness te benaderen. Dit surrogaatmodel leert niet-lineaire relaties tussen algoritmische structuur en prestaties.

3. Explainable AI (SHAP) voor Sturing

Om bruikbare instructies af te leiden, past het systeem SHAP (SHapley Additive exPlanations) toe op het getrainde surrogaatmodel. SHAP-waarden kwantificeren de bijdrage van elk kenmerk aan de voorspelde fitness. Het kenmerk met de grootste absolute attributie wordt geselecteerd, en het teken van de SHAP-waarde bepaalt of de waarde van het kenmerk moet worden verhoogd of verlaagd om de prestaties te verbeteren.

4. Geleide Mutatie-prompting

De structurele sturing wordt vertaald naar een instructie in natuurlijke taal die de standaard mutatieprompt voor de LLM aanvult. Bijvoorbeeld, als de analyse suggereert dat het verhogen van de cyclomatische complexiteit correleert met betere prestaties, wordt de prompt aangepast naar: "Based on archive analysis, try to increase the total cyclomatic complexity of the solution."
Cruciaal is dat deze sturing de generatie van de LLM richting empirisch voordelige structurele regio's stuurt zonder rigide syntactische beperkingen of vooraf gedefinieerde templates op te leggen, waardoor de expressiviteit van de LLM behouden blijft.

Belangrijkste Bijdragen

1. LLaMEA-SAGE Framework: De voorstel van een nieuw mechanisme dat AAD stuurt met behulp van feature-gedreven feedback afgeleid van AST en complexiteitsanalyse, bemiddeld door een surrogaatmodel en SHAP-analyse.
2. Systematische Benchmarking: Een uitgebreide experimentele vergelijking met SOTA LLM-gebaseerde heuristische ontwerpmethoden, specifiek MCTS-AHD (Monte Carlo Tree Search voor Algoritme Heuristische Design) en LHNS (LLM-gestuurde Heuristische Neighborhood Search), naast de standaard LLaMEA-baseline.
3. Empirische Validatie: Demonstratie dat gestructureerde sturing de kwaliteit en robuustheid van algoritmen verbetert op black-box optimalisatie-benchmarks, ondersteund door uitgebreide analyse met Code Evolution Graphs (CEGs) en statistische tests.

Experimentele Resultaten

De auteurs evalueerden LLaMEA-SAGE over twee primaire experimenten met behulp van de IOH-BLADE benchmarking toolbox.

Experiment 1: Gecontroleerde Vergelijking (SBOX-COST)

• Setup: Vergelijking van vanilla LLaMEA tegen LLaMEA-SAGE op een subset van de SBOX-COST suite (10 dimensies, 5 instanties).
• Bevindingen: LLaMEA-SAGE behaalde sneller een betere prestatie dan vanilla LLaMEA, met name in de vroege stadia van het evolutionaire proces. Hoewel beide methoden een vergelijkbare uiteindelijke prestatie bereikten binnen het budget, vertoonde de geleide aanpak minder variantie tussen de runs.
• Statistische Significantie: LLaMEA-SAGE liet een gemiddelde verbetering zien van 11,1 Area Under the Convergence Curve (AUC) eenheden met een grote effectgrootte (Cliff's $\delta$ = 0,60). Echter, door het beperkte aantal onafhankelijke runs (5 seeds), was het verschil niet statistisch significant ($p=0,44$).
• Gedragsanalyse: Code Evolution Graphs toonden aan dat de sturing de structurele exploratie succesvol beïnvloedde. Opvallend genoeg leidde de "refine" prompt tot een toename van de codecomplexiteit wanneer gestuurd, terwijl de "random new" prompt de sturing vaak negeerde of resulteerde in een lagere complexiteit.

Experiment 2: Grootschalige Benchmark (MA-BBOB)

• Setup: Evaluatie op de Many Affine BBOB (MA-BBOB) suite, een standaard voor GECCO-competities, waarbij LLaMEA-SAGE werd vergeleken met vanilla LLaMEA, MCTS-AHD en LHNS.
• Bevindingen: LLaMEA-SAGE presteerde consequent beter dan alle baselines, inclusief de SOTA MCTS-AHD en LHNS methoden. Het bereikte fitnessniveaus die vanilla LLaMEA niet kon bereiken, zelfs niet na het volledige evaluatiebudget.
• Efficiëntie: Wat betreft tokengebruik was LLaMEA-SAGE marginaal duurder dan vanilla LLaMEA, maar aanzienlijk efficiënter dan MCTS-AHD (dat de LLM meerdere keren per oplossing bevraagt).
• Generalisatie: De uiteindelijke validatie op ongeziene instanties (andere dimensies en probleeminstanties) toonde aan dat het beste door LLaMEA-SAGE ontdekte algoritme andere automatisch ontworpen algoritmen en de 2025 MA-BBOB competitiewinnaar op 10- en 20-dimensionale taken versloeg, hoewel het de specifiek geoptimaliseerde 5-dimensionale competitiewinnaar niet overtrof.

Betekenis en Claims

Het paper claimt dat LLaMEA-SAGE erin slaagt de kloof te overbruggen tussen codestructuur en menselijk begrijpelijke prestatiefeedback in geautomatiseerd algoritmeontwerp. Door structurele signalen te vertalen naar natuurlijke taal, biedt de methode een data-gedreven inductieve bias die de LLM-gestuurde evolutie stuurt zonder de creatieve capaciteit van het model te beperken.

De auteurs benadrukken dat zelfs imperfecte, ruisgevoelige correlaties afgeleid van codekenmerken voldoende zijn om de exploratie in de vroege stadia van AAD gunstig te beïnvloeden. Het werk demonstreert dat signalen afgeleid van code effectief de efficiëntie en stabiliteit van algoritmeontdekking kunnen verbeteren, wat een schaalbaar, template-vrij alternatief biedt voor bestaande heuristiek-gecentreerde benaderingen.

Beperkingen en Toekomstig Werk

De auteurs merken bescheiden enkele beperkingen op:

• LLM Afhankelijkheid: Experimenten werden uitgevoerd met één enkele LLM-backend (GPT-5-mini), hoewel voorlopige ablatie op Gemini consistente trends liet zien.
• Scope: De evaluatie was beperkt tot continue black-box optimalisatie bij matige dimensies; generalisatie naar hoog-dimensionale, ruisgevoelige of fundamenteel andere probleemklassen blijft een open vraag.
• Statische Analyse: De huidige set kenmerken vangt alleen statische structurele eigenschappen, waarbij dynamisch executiegedrag of interactie-effecten tijdens optimalisatieruns worden genegeerd.

Toekomstig werk stelt voor om structurele kenmerken te combineren met runtime-beschrijvers, adaptieve multi-feature sturing te verkennen en de mechanisme te integreren in andere LLM-gebaseerde AAD-frameworks.