Technische Samenvatting: Algoritmediscoverie met LLM's: Evolutionaire Zoekopdracht ontmoet Versterkend Leren

Probleemstelling

De ontdekking van efficiënte algoritmen voor complexe problemen, met name in de wiskunde en combinatorische optimalisatie, heeft historisch gezien afhankelijkheid van aanzienlijke menselijke expertise. Hoewel recente vooruitgang in Large Language Models (LLM's) in combinatie met evolutionaire zoekopdrachten (bijvoorbeeld de FunSearch-methode) veelbelovend is gebleken voor het automatiseren van deze ontdekking, behandelen bestaande benaderingen de LLM als een statische generator. Deze methoden gebruiken de LLM om nieuwe programma's voor te stellen op basis van eerdere successen, maar slagen er niet in om de interne parameters van het model bij te werken op basis van de signalen die tijdens de evolutionaire exploratie worden verkregen. Bijgevolg missen ze de kans om het parametrische karakter van de LLM te benutten om het zoekbeleid in de loop van de tijd te verfijnen, wat kan leiden tot suboptimale convergentie of inefficiënte exploratie van de oplossingsruimte.

Methodologie: EvoTune

De auteurs stellen EvoTune voor, een raamwerk dat evolutionaire zoekopdracht nauw integreert met Versterkend Leren (RL) om de LLM-zoekoperator continu te verfijnen. De methode werkt in een iteratieve lus die bestaat uit twee afwisselende fasen:

1. Evolutionaire Zoekopdracht (Exploratie):

   • De LLM genereert kandidaat-Pythonprogramma's (algoritmen) op basis van prompts die zijn samengesteld uit programma's met hoge scores die in eerdere iteraties zijn ontdekt.
   • Deze programma's worden geëvalueerd op specifieke combinatorische optimalisatietaken (bijvoorbeeld Bin Packing, Traveling Salesman Problem, Flatpack) om beloningsscores te verkrijgen (doorgaans de negatieve optimaliteitskloof).
   • Geldige programma's en hun scores worden opgeslagen in een programmabasis, georganiseerd in "eilanden" om diversiteit te behouden en voortijdige convergentie te voorkomen.
   • De zoekopdracht hanteert een "bootstrapping"-strategie, waarbij de LLM de verschillen analyseert tussen goed presterende en slecht presterende programma's om de generatie van nieuwe kandidaten te sturen.

2. RL-training (Verfijning):

   • Periodiek (elke $f_{RL}$ iteraties) wordt het generatiebeleid van de LLM ($\pi_\theta$) bijgewerkt met behulp van de geaccumuleerde data uit de evolutionaire zoekopdracht.
   • De auteurs formuleren dit als een Preference Optimization-probleem. Ze construeren een preferentiedataset $D_{pref}$ bestaande uit tripletten $(x, y^+, y^-)$, waarbij $x$ de prompt is, $y^+$ een programma met een hogere beloning is, en $y^-$ een programma met een lagere beloning.
   • Het model wordt fijnge tuneerd met Direct Preference Optimization (DPO). In tegenstelling tot standaard offline DPO, werkt EvoTune in een off-policy setting waarbij de data dynamisch wordt gegenereerd door het evoluerende model zelf.
   • Behoud van Diversiteit: Een cruciale ontwerpkeuze is het gebruik van Forward KL-regularisatie (in tegenstelling tot de gebruikelijkere Reverse KL) binnen de DPO-doelstelling. Dit stimuleert "mass-covering"-gedrag, voorkomt dat het model instort in een enkele modus en behoudt de outputdiversiteit die essentieel is voor effectieve evolutionaire zoekopdrachten.

Belangrijkste Bijdragen

1. Integratie van RL in Evolutionaire Zoekopdracht: Het artikel claimt de eerste te zijn die het potentieel aantoont van het nauw integreren van op LLM's gebaseerde evolutionaire zoekopdracht met RL-fijnafstemming in de lus. In tegenstelling tot eerdere methoden die LLM's uitsluitend als statische generators gebruiken, werkt EvoTune de modelgewichten bij om beter gebruik te maken van inzichten die uit exploratie zijn verkregen.
2. Versnelde Algoritmediscoverie: Door het zoekbeleid via RL te verfijnen, versnelt de methode de ontdekking van superieure algoritmen. Experimenten met drie instructie-getuneerde LLM's (Llama3.2 1B, Phi 3.5 Mini, Granite 3.1 2B) tonen consistente prestatiewinsten ten opzichte van de baseline FunSearch-methode.
3. Diversiteitsbehoudende Uitlijning: De auteurs tonen het voordeel aan van het gebruik van een aangepaste uitlijningsdoelstelling (Forward KL-geregulariseerde DPO) om outputdiversiteit te behouden. Dit is cruciaal voor evolutionaire strategieën, omdat modale instorting de ontdekking van nieuwe oplossingen kan belemmeren.
4. Brede Toepasbaarheid: De methode is gevalideerd op diverse benchmarks, waaronder standaard combinatorische problemen (Bin Packing, TSP, Flatpack), real-world Google Hash Code-uitdagingen (Datacenter Optimization, Self-Driving Rides) en symbolische regressietaken (LLM-SR).

Experimentele Resultaten

De auteurs hebben EvoTune geëvalueerd tegen een FunSearch-stijl baseline (evolutionaire zoekopdracht zonder modeltraining) over meerdere taken en modellen:

• Prestatiewinsten: EvoTune behaalde consistent hogere uiteindelijke beloningsscores (lagere optimaliteitskloven) voor de top 50 ontdekte programma's in vergelijking met de baseline. De prestatiekloof werd vaak groter naarmate het sampling-budget toenam, wat suggereert dat grotere budgetten de voordelen van de methode versterken.
• Generalisatie: De geëvolueerde programma's toonden robuustheid op validatie-geperturbeerde sets en testsets afkomstig uit dezelfde verdeling, wat aangeeft dat de geleerde beleidslijnen generaliseren buiten de specifieke instanties die tijdens de training zijn gezien.
• Real-world Benchmarks:
  • Op de taak Google Hash Code Datacenter Optimization behaalde EvoTune een score van 418, waarmee het de top menselijke score van 407 overtrof en de FunSearch-baseline (414) versloeg.
  • Op Symbolische Regressie-taken (LLM-SR) overtrof EvoTune de evolutionaire baseline en, opmerkelijk, baselines die grotere of propriëtaire modellen gebruikten (bijvoorbeeld Mixtral 8x7B, GPT-3.5-turbo) terwijl het een kleiner model gebruikte (Phi-3.5 Mini, 3,8 miljard parameters).
• Ablatiestudies:
  • Forward versus Reverse KL: Experimenten bevestigden dat Forward KL-regularisatie hogere beloningen en een groter aantal unieke oplossingen oplevert in vergelijking met Reverse KL, wat het belang van diversiteitsbehoud valideert.
  • Alternatief RL: De auteurs testten ReSTEM (Supervised Fine-Tuning op programma's met hoge scores) als alternatief voor DPO. Resultaten gaven aan dat DPO consistent beter presteerde dan ReSTEM en minder gevoelig was voor hyperparameter-tuning.

Betekenis en Claims

Het artikel positioneert EvoTune als een belangrijke stap voorwaarts in geautomatiseerd algoritmedesign door de "Bitter Lesson" (Sutton, 2019) aan te pakken, die stelt dat zoeken en leren synergetisch zijn. De auteurs claimen dat:

• Synergie: Zoeken nieuwe data genereert, terwijl leren patronen uit die data destilleert om toekomstige exploratie effectiever te sturen.
• Efficiëntie: Het integreren van RL stelt het systeem in staat om verder te gaan dan het enkel verhogen van de gemiddelde score van een populatie; het leidt de evolutionaire zoekopdracht actief naar superieure oplossingen (gemeten aan de hand van top-k prestaties) terwijl het de diversiteit behoudt die nodig is voor innovatie.
• Schaalbaarheid: De methode toont potentieel voor schaalbaarheid naar real-world settings, zoals blijkt uit het succes op complexe, niet-synthetische problemen zoals datacenteroptimalisatie en spanning-rekmodellen.

De auteurs erkennen nederig beperkingen, met de opmerking dat hun experimenten zijn uitgevoerd met modellen variërend van 1 miljard tot 3,8 miljard parameters en dat verdere schaalvergroting van modelgrootte en sampling-budgetten nodig is om het potentieel van de methode volledig te begrijpen. Ze wijzen ook op de afweging tussen de extra rekentkosten van de RL-trainingsfase en de winst in inferentie-efficiëntie en oplossingskwaliteit.