💻 computer science

Compute Allocation in Evolutionary Search: From Depth-Breadth to Multi-Armed Bandits

Dieser Beitrag analysiert die empirischen Regularitäten der von LLMs geleiteten evolutionären Suche, um BaSE vorzustellen, einen Multi-Armed-Bandit-Algorithmus, der Rechenleistung dynamisch über parallele Trajektorien verteilt und so eine Verbesserung der mittleren Fitness um 12,3 % sowie eine erhöhte Zuverlässigkeit gegenüber traditionellen Tiefen-Breiten-Strategien erzielt, ohne das zugrundeliegende Modell oder die Prompts zu modifizieren.

Ursprüngliche Autoren: Sixue Xing, Haoyu He, Kerui Wu, Zhuo Yang, Haozheng Luo, Tianfan Fu, Aarthy Nagarajan

Veröffentlicht 2026-05-29

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Sixue Xing, Haoyu He, Kerui Wu, Zhuo Yang, Haozheng Luo, Tianfan Fu, Aarthy Nagarajan

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen, ein sehr schwieriges Puzzle zu lösen, wie zum Beispiel das perfekte Einpassen von 26 Kreisen in ein Quadrat oder das Anordnen von Punkten, um den Abstand zwischen ihnen zu maximieren. Sie haben einen superintelligenten Assistenten (ein Large Language Model, oder LLM), der neue Wege vorschlagen kann, die Teile anzuordnen. Allerdings haben Sie nur eine begrenzte Menge an „Energie" oder „Budget", um den Assistenten um Vorschläge zu bitten.

Dieser Artikel dreht sich darum, den besten Weg zu finden, diese Energie auszugeben, um die bestmögliche Puzzle-Lösung zu erhalten.

Das Problem: Wie gibt man sein „Frag-Budget" aus?

In der Vergangenheit versuchten Forscher zwei Hauptmethoden, ihr begrenztes Budget an Fragen an die KI zu nutzen:

Der „Tiefe Blick" (Tiefe): Man bittet die KI, eine einzelne Idee zu nehmen, sie zu verbessern, eine bessere Version davon zu verlangen und diesen einen Pfad lange Zeit weiterzuverfolgen. Es ist wie das Graben eines sehr tiefen Lochs.
Das „weite Netz" (Breite): Man bittet die KI, 100 verschiedene zufällige Ideen gleichzeitig zu generieren, die beste auszuwählen und dann aufzuhören. Es ist wie das Auswerfen eines weiten Netzes, bei dem man jedoch nur einen Fisch herauszieht.

Die meisten früheren Studien berichteten lediglich über das beste Ergebnis, das sie je erhielten, oft nachdem sie hunderte verschiedener Kombinationen ausprobiert hatten. Sie sagten uns nicht, wie zuverlässig diese Ergebnisse waren oder wie man sie mit einem festen Budget konsistent erzielen kann.

Die Entdeckung: Es kommt auf das Puzzle an

Die Autoren führten Tausende von Experimenten mit verschiedenen KI-Modellen und drei verschiedenen Arten von Puzzles durch. Sie fanden zwei große Regeln:

Die „Fähigkeits-Obergrenze": Wenn die KI für das spezifische Puzzle nicht intelligent genug ist, spielt es keine Rolle, wie Sie Ihr Budget ausgeben; sie wird es nicht lösen. Aber wenn die KI intelligent genug ist, verschwindet der Unterschied zwischen einer kleinen und einer riesigen KI oft, wenn man die tatsächliche „Rechenarbeit" misst.
Die „Form der Lösung":
- Puzzle A (Kreispackung): Dieses Puzzle ist wie eine breite, flache Hochebene. Sie können tief oder breit gehen, und Sie werden wahrscheinlich eine gute Lösung finden. Es ist verzeihend.
- Puzzle B (MinMax-Abstände): Dieses Puzzle ist wie ein scharfer Bergkamm. Sie müssen das genaue richtige Gleichgewicht zwischen tiefem Graben und weitem Auswerfen finden. Wenn Sie zu tief oder zu breit gehen, verpassen Sie den Gipfel.

Die Lösung: BaSE (Der intelligente Verkehrspolizist)

Die Autoren erkannten, dass die einfache Wahl zwischen „Tiefe" oder „Breite" nicht ausreicht, weil die KI unvorhersehbar ist. Manchmal bleibt ein einzelner Lauf in einer schlechten Idee stecken, und manchmal findet er eine Goldmine.

Sie entwickelten eine neue Methode namens BaSE (Bandit-based Self-Evolving).

Die Analogie: Die Strategie der Spielautomaten
Stellen Sie sich vor, Sie befinden sich in einem Casino mit 10 verschiedenen Spielautomaten (diese sind 10 verschiedene KI-„Läufe", die versuchen, das Puzzle zu lösen). Sie haben eine feste Anzahl an Münzen (Ihr Budget).

Der alte Weg: Sie wählen eine Maschine aus und ziehen den Hebel, bis Ihre Münzen ausgehen. Wenn diese Maschine ein „Verlierer" ist, verlieren Sie alles.
Die BaSE-Methode: Sie ziehen den Hebel an allen 10 Maschinen einmal. Dann schauen Sie, welche am meisten auszahlen. Sie hören auf, Münzen an die verlierenden Maschinen zu geben, und schütten alle Ihre verbleibenden Münzen in die Gewinnmaschinen.

BaSE fungiert wie ein intelligenter Verkehrspolizist. Es verändert weder das Gehirn der KI noch die Puzzle-Regeln. Es überwacht lediglich ständig, welche „Pfade" funktionieren, und verlagert das Budget auf die Gewinner, während es die Verlierer aufgibt.

Die Ergebnisse

Bessere Konsistenz: Durch die Verwendung von BaSE verbesserte sich der Durchschnittswert der Lösungen um 12,3 % im Vergleich zu den besten bestehenden Methoden.
Zuverlässigkeit: Es machte die Ergebnisse viel zuverlässiger. Anstatt einmal in hundert Versuchen einen glücklichen „Jackpot" zu erzielen, erhalten Sie konsistent eine hohe Punktzahl.
Keine Zaubertricks: Sie verwendeten kein intelligenteres KI-Modell oder einen besseren Prompt. Sie gaben einfach das gleiche Geld intelligenter aus.

Das Fazit

Wenn Sie ein begrenztes Budget haben, um eine KI zu bitten, ein schwieriges Problem zu lösen, bleiben Sie nicht einfach bei einem Pfad oder werfen Sie alles auf einmal hinein. Verwenden Sie eine Strategie, die mehrere Versuche gleichzeitig überwacht und Ihre Ressourcen schnell auf diejenigen verlagert, die tatsächlich funktionieren. Dieser Artikel beweist, dass wie Sie Ihre Rechenleistung zuweisen, genauso wichtig ist wie das KI-Modell, das Sie verwenden.

Technische Zusammenfassung: Rechenzuweisung in der evolutionären Suche

Problemstellung

Von Large Language Models (LLM) geführte Systeme für evolutionäre Suche (z. B. FunSearch, AlphaEvolve, CodeEvolve) haben in mathematischen Entdeckungen und kombinatorischen Optimierungsproblemen state-of-the-art-Ergebnisse erzielt. Die bestehende Literatur berichtet jedoch überwiegend nur über das einzelne beste Ergebnis aus einer nicht spezifizierten Anzahl von Läufen, wodurch die Verteilung zwischen den Läufen nicht dokumentiert bleibt. Darüber hinaus variieren die berichteten Rechenkosten um Größenordnungen, was eine Bewertung der Zuverlässigkeit eines einzelnen Laufs unter einem festen Budget erschwert.

Das behandelte Kernproblem ist die Rechenzuweisung: Gegeben ein festes Budget an LLM-Aufrufen ( $C$ ), wie sollte dieses Budget zwischen Tiefe (sequenzielle Verfeinerung einer einzelnen Trajektorie) und Breite (parallele Exploration mehrerer Trajektorien) verteilt werden? Aktuelle Systeme fixieren diese Hyperparameter (z. B. Populationsgröße und Anzahl der Generationen) oft ohne ein systematisches Verständnis dafür, wie die Zuweisung die erwartete Leistung und Zuverlässigkeit beeinflusst.

Methodik

1. Empirische Charakterisierung der Tiefen-Breiten-Zuweisung

Die Autoren führten eine systematische empirische Studie über drei geometrische Optimierungsaufgaben (Circle Packing, MinMaxDist, Heilbronn Triangle) und vier Modellgrößen (Qwen3-1.7B bis 14B sowie Llama-3.1-8B) durch. Sie definierten das Zuweisungsproblem als Aufteilung des Budgets $C$ in $T$ Generationen von $N$ parallelen Kindern ( $C = T \times N$ ).

Fitness-Rechen-Umschlag: Sie analysierten die Beziehung zwischen erreichbarer Fitness und effektiven FLOPs (unter Berücksichtigung der Modellgröße und Cache-Effizienz). Sie beobachteten, dass zwar größere Modelle bei gleicher Anzahl von Aufrufen führen, ihre Leistungsreihenfolge jedoch weitgehend kollabiert, wenn sie gegen effektive FLOPs gemessen werden, sofern das Modell-Aufgaben-Paar „fähig" ist.
Tiefen-Breiten-Regularität: Sie passten ein parametrisches bilineares Modell an die Fitnesslandschaft an:
$\log(1 - V) = \beta_0 + a \log T + b \log N + c \log T \log N$
wobei $V$ $V$ die Fitness ist. Der Interaktionskoeffizient $c$ $c$ bestimmt die Geometrie der optimalen Zuweisung:
- Eckoptima ( $|c| \approx 0$ ): Aufgaben wie Circle Packing zeigen breite Plateaus, bei denen viele Zuweisungen ähnliche Ergebnisse liefern, wobei oft die Tiefe bevorzugt wird.
- Innere Grate ( $c < 0$ ): Aufgaben wie MinMaxDist zeigen einen scharfen Grat, bei dem eine ausgewogene Mischung aus Tiefe und Breite für optimale Leistung erforderlich ist.
- Fähigkeits-Gating: Diese Regularitäten gelten nur für Modelle, die eine Fähigkeitsgrenze für die spezifische Aufgabe überschritten haben; schwache Modelle zeigen keine strukturierten Tiefen-Breiten-Abwägungen.

2. BaSE: Bandit-basierte Selbstentwicklung

Motiviert durch die hohe Varianz der Läufergebnisse (bei der identische Konfigurationen aufgrund von Stochastizität im Mutationsprozess des LLM stark unterschiedliche Endfitness-Werte produzieren), schlugen die Autoren BaSE vor.

Mechanismus: BaSE behandelt die evolutionäre Suche als Multi-Armed Bandit (MAB)-Problem. Anstatt das gesamte Budget einer einzigen Trajektorie (Greedy) oder einem festen Satz von Inseln (Insel-Protokoll) zu widmen, verwaltet BaSE $K$ parallele Trajektorien.
Adaptive Zuweisung: In jedem Schritt wählt ein Bandit-Algorithmus (UCB, EXP3.P oder Thompson Sampling), welche Trajektorie mit dem nächsten LLM-Aufruf erweitert wird. Dies leitet Rechenleistung dynamisch von stagnierenden Läufen weg hin zu vielversprechenden.
Orthogonalität: BaSE verändert weder das Basismodell, den Prompt noch die Logik zur Elternauswahl innerhalb einer Trajektorie. Es operiert strikt auf der Ebene der Ressourcenverteilung zwischen Trajektorien.

Wichtige Ergebnisse

1. Empirische Regularitäten

Fähigkeitskollaps: Für fähige Modelle wird die Leistungsumhüllende durch effektive FLOPs und nicht allein durch die Modellgröße bestimmt.
Aufgabenabhängige Geometrie: Die optimale Tiefen-Breiten-Aufteilung ist nicht universell; sie hängt von der „algorithmischen Familie" der Aufgabe ab (z. B. ob die Lösung eine spezifische Bibliothek wie scipy oder eine spezifische analytische Konstruktion erfordert).
Stochastizität: Selbst bei fester Zuweisung variieren einzelne Läufe erheblich. Einige Läufe konvergieren zu hoher Fitness, während andere früh stagnieren, weil sie sich auf eine suboptimale algorithmische Familie festlegen.

2. Leistung von BaSE

Verbesserung der mittleren Fitness: Über 8 (Modell, Aufgabe)-Zellen hinweg verbesserte BaSE die mittlere beste Fitness um 12,3 % gegenüber den stärksten Baselines des Insel-Protokolls (z. B. OpenEvolve, CodeEvolve, ShinkaEvolve), ohne Modell oder Prompt zu ändern.
Gewinne in der Zuverlässigkeit: Die signifikantesten Gewinne wurden in Umgebungen mit hoher Varianz beobachtet. Beispielsweise gelang es bei der Heilbronn-Triangle-Aufgabe mit Llama-3.1-8B nicht-BaSE-Methoden oft nicht, gültige Lösungen zu produzieren (Fitness $\approx 0$ ), während BaSE (Thompson Sampling) eine mittlere Fitness von 0,4387 erreichte.
Proben-Effizienz: BaSE erreichte Ziel-Fitness-Schwellenwerte signifikant schneller (weniger Generationen und FLOPs) als Greedy- oder Festzuweisungs-Baselines. Beispielsweise erreichte UCB bei MinMaxDist einen Schwellenwert von 0,95 in 92 Generationen, während die Greedy-Baseline 485 benötigte.
Ablation: Moderate Pool-Größen der Arme ( $K \in \{5, 10, 20\}$ ) boten den besten Kompromiss zwischen Vielfalt und Verfeinerungstiefe.

Bedeutung und Behauptungen

Die Arbeit behauptet, dass die Rechenzuweisung ein eigenständiger und kritischer Hebel zur Verbesserung von LLM-gesteuerter evolutionärer Suche ist, getrennt von Modellskalierung oder Prompt-Engineering.

Zuweisung vs. Engineering: Die Autoren betonen, dass ihre Verbesserungen nicht auf bessere Prompts oder Modelle zurückzuführen sind. Tatsächlich stellen sie fest, dass einige Baselines (wie ShinkaEvolve) auf bestimmten Aufgaben teilweise aufgrund prompt-induzierter Hinweise hohe Scores erzielten (z. B. Vorschlag von scipy.optimize), während BaSE Gewinne rein durch adaptive Ressourcenlenkung erzielt.
Zuverlässigkeit: Der Hauptbeitrag liegt in der Verschiebung des Fokus von „Best-Case"-Berichterstattung hin zu „erwarteter" Leistung. BaSE bietet einen Zuverlässigkeitsgewinn und stellt sicher, dass ein Praktiker weniger wahrscheinlich ein festes Budget für eine Trajektorie verschwendet, die bereits stagniert.
Komplementarität: BaSE wird als komplementär zu bestehenden Mechanismen innerhalb eines Laufs (wie Elternauswahl) präsentiert. Es kann über bestehenden Protokollen (Greedy, Island) aufgelegt werden, um die Leistung weiter zu verbessern, insbesondere in instabilen Umgebungen oder bei hoher Varianz.

Die Arbeit kommt zu dem Schluss, dass zwar die Modellfähigkeit die Obergrenze für das Erreichbare setzt, die Zuweisung jedoch regelt, wie effizient eine Methode diese Obergrenze annähert, und dass adaptive Zuweisung durch Bandits eine robuste Strategie für die Suche mit festem Budget darstellt.