Technische Zusammenfassung: Algorithmus-Entdeckung mit LLMs: Evolutionäre Suche trifft auf Reinforcement Learning

Problemstellung

Die Entdeckung effizienter Algorithmen für komplexe Probleme, insbesondere in der Mathematik und kombinatorischen Optimierung, war historisch stark von erheblicher menschlicher Expertise abhängig. Zwar haben jüngste Fortschritte bei Large Language Models (LLMs) in Kombination mit evolutionärer Suche (z. B. die FunSearch-Methode) vielversprechende Ergebnisse bei der Automatisierung dieser Entdeckung gezeigt, doch behandeln bestehende Ansätze das LLM als statischen Generator. Diese Methoden nutzen das LLM, um basierend auf früheren Erfolgen neue Programme vorzuschlagen, aktualisieren jedoch nicht die internen Parameter des Modells anhand der Signale, die während der evolutionären Exploration gewonnen werden. Folglich verpassen sie die Gelegenheit, die parametrische Natur des LLMs zu nutzen, um seine Suchstrategie im Laufe der Zeit zu verfeinern, was potenziell zu suboptimaler Konvergenz oder ineffizienter Exploration des Lösungsraums führt.

Methodik: EvoTune

Die Autoren schlagen EvoTune vor, ein Framework, das evolutionäre Suche eng mit Reinforcement Learning (RL) integriert, um den LLM-Suchoperator kontinuierlich zu verfeinern. Die Methode arbeitet in einer iterativen Schleife, die aus zwei abwechselnden Phasen besteht:

1. Evolutionäre Suche (Exploration):

   • Das LLM generiert Kandidaten-Python-Programme (Algorithmen) basierend auf Prompts, die aus hochbewerteten Programmen konstruiert wurden, die in vorherigen Iterationen entdeckt wurden.
   • Diese Programme werden an spezifischen kombinatorischen Optimierungsaufgaben (z. B. Bin Packing, Traveling Salesman Problem, Flatpack) evaluiert, um Belohnungswerte zu erhalten (typischerweise der negative Optimalitätslücke).
   • Gültige Programme und ihre Werte werden in einer Programm-Datenbank gespeichert, die in „Inseln" organisiert ist, um die Vielfalt zu erhalten und vorzeitige Konvergenz zu verhindern.
   • Die Suche employs eine „Bootstrapping"-Strategie, bei der das LLM die Unterschiede zwischen hoch- und niedrigperformanten Programmen analysiert, um die Generierung neuer Kandidaten zu steuern.

2. RL-Training (Verfeinerung):

   • Periodisch (alle $f_{RL}$ Iterationen) wird die Generierungsstrategie ($\pi_\theta$) des LLMs unter Verwendung der aus der evolutionären Suche akkumulierten Daten aktualisiert.
   • Die Autoren formulieren dies als Preference Optimization-Problem. Sie konstruieren einen Präferenzdatensatz $D_{pref}$, der aus Triplets $(x, y^+, y^-)$ besteht, wobei $x$ der Prompt ist, $y^+$ ein Programm mit höherer Belohnung und $y^-$ ein Programm mit niedrigerer Belohnung.
   • Das Modell wird mittels Direct Preference Optimization (DPO) feinabgestimmt. Im Gegensatz zum Standard-Offline-DPO operiert EvoTune in einem off-policy-Setting, bei dem die Daten dynamisch vom sich entwickelnden Modell selbst generiert werden.
   • Erhaltung der Vielfalt: Eine kritische Designentscheidung ist die Verwendung von Forward KL-Regularisierung (im Gegensatz zur häufiger verwendeten Reverse KL) innerhalb des DPO-Ziels. Dies fördert ein „Mass-Covering"-Verhalten, verhindert, dass das Modell in einen einzigen Modus kollabiert, und erhält die für eine effektive evolutionäre Suche essentielle Ausgabenvielfalt.

Hauptbeiträge

1. Integration von RL in die evolutionäre Suche: Das Papier beansprucht, als Erstes das Potenzial einer engen Integration von LLM-basierter evolutionärer Suche mit RL-Feinabstimmung in der Schleife zu demonstrieren. Im Gegensatz zu früheren Methoden, die LLMs ausschließlich als statische Generatoren nutzen, aktualisiert EvoTune die Modellgewichte, um besser Erkenntnisse zu nutzen, die aus der Exploration gewonnen wurden.
2. Beschleunigte Algorithmus-Entdeckung: Durch die Verfeinerung der Suchstrategie via RL beschleunigt die Methode die Entdeckung überlegener Algorithmen. Experimente mit drei instruktionsfeinabgestimmten LLMs (Llama3.2 1B, Phi 3.5 Mini, Granite 3.1 2B) zeigen konsistente Leistungssteigerungen gegenüber der Baseline-FunSearch-Methode.
3. Vielfalt-erhaltende Ausrichtung: Die Autoren demonstrieren den Vorteil der Verwendung eines modifizierten Ausrichtungsziels (Forward KL-regularisiertes DPO) zur Erhaltung der Ausgabevielfalt. Dies ist für evolutionäre Strategien entscheidend, da ein Kollaps in einen Modus die Entdeckung neuer Lösungen behindern kann.
4. Breite Anwendbarkeit: Die Methode wurde an diversen Benchmarks validiert, darunter Standard-kombinatorische Probleme (Bin Packing, TSP, Flatpack), reale Google Hash Code-Herausforderungen (Rechenzentrums-Optimierung, Self-Driving Rides) und Aufgaben der symbolischen Regression (LLM-SR).

Experimentelle Ergebnisse

Die Autoren evaluierten EvoTune gegenüber einer FunSearch-ähnlichen Baseline (evolutionäre Suche ohne Modelltraining) über mehrere Aufgaben und Modelle hinweg:

• Leistungssteigerungen: EvoTune erzielte konsistent höhere finale Belohnungswerte (niedrigere Optimalitätslücken) für die Top-50-entdeckten Programme im Vergleich zur Baseline. Die Leistungslücke weitete sich oft aus, wenn das Sampling-Budget erhöht wurde, was darauf hindeutet, dass größere Budgets die Vorteile der Methode verstärken.
• Generalisierung: Die entwickelten Programme zeigten Robustheit auf validierungs-perturbierten Sets und Test-Sets, die aus derselben Verteilung gezogen wurden, was darauf hindeutet, dass die gelernten Strategien über die spezifischen Instanzen hinaus generalisieren, die während des Trainings gesehen wurden.
• Reale Benchmarks:
  • Bei der Google Hash Code Datacenter Optimization-Aufgabe erzielte EvoTune eine Punktzahl von 418 und übertraf damit die beste menschliche Punktzahl von 407 sowie die FunSearch-Baseline (414).
  • Bei Symbolic Regression-Aufgaben (LLM-SR) übertraf EvoTune die evolutionäre Baseline und, bemerkenswerterweise, auch Baselines, die größere oder proprietäre Modelle verwendeten (z. B. Mixtral 8x7B, GPT-3.5-turbo), während es ein kleineres Modell (Phi-3.5 Mini, 3,8 Mrd. Parameter) einsetzte.
• Ablationsstudien:
  • Forward vs. Reverse KL: Experimente bestätigten, dass Forward KL-Regularisierung höhere Belohnungen und eine größere Anzahl einzigartiger Lösungen im Vergleich zu Reverse KL liefert, was die Bedeutung der Vielfaltserhaltung validiert.
  • Alternatives RL: Die Autoren testeten ReSTEM (Supervised Fine-Tuning auf hochbewerteten Ausgaben) als Alternative zu DPO. Die Ergebnisse zeigten, dass DPO ReSTEM konsistent übertraf und weniger empfindlich gegenüber Hyperparameter-Tuning war.

Bedeutung und Behauptungen

Das Papier positioniert EvoTune als einen bedeutenden Schritt vorwärts im automatisierten Algorithmus-Design, indem es die „Bitter Lesson" (Sutton, 2019) adressiert, die argumentiert, dass Suche und Lernen synergetisch wirken. Die Autoren behaupten, dass:

• Synergie: Suche neue Daten generiert, während Lernen Muster aus diesen Daten destilliert, um die zukünftige Exploration effektiver zu steuern.
• Effizienz: Die Integration von RL ermöglicht es dem System, über die bloße Erhöhung des Durchschnittswerts einer Population hinauszugehen; es steuert die evolutionäre Suche aktiv auf überlegene Lösungen zu (gemessen an der Top-k-Leistung), während die für Innovation erforderliche Vielfalt erhalten bleibt.
• Skalierbarkeit: Die Methode zeigt Potenzial für die Skalierung auf reale Szenarien, wie durch ihren Erfolg bei komplexen, nicht-synthetischen Problemen wie der Rechenzentrums-Optimierung und der Spannungs-Dehnungs-Modellierung belegt wird.

Die Autoren erkennen bescheiden Limitationen an und stellen fest, dass ihre Experimente mit Modellen im Bereich von 1 bis 3,8 Milliarden Parametern durchgeführt wurden und dass eine weitere Skalierung der Modellgröße und der Sampling-Budgets erforderlich ist, um das Potenzial der Methode vollständig zu verstehen. Sie heben auch den Trade-off zwischen den zusätzlichen Rechenkosten der RL-Trainingsphase und den Gewinnen in der Inferenzeffizienz und Lösungsqualität hervor.