🤖 AI

Contrastive Concept-Tree Search for LLM-Assisted Algorithm Discovery

Dieses Paper führt die Contrastive Concept-Tree Search (CCTS) ein, eine Methode, welche die LLM-gestützte Algorithmusentdeckung durch das Erlernen eines hierarchischen Konzeptmodells verbessert, um die Elternauswahl durch kontrastives Reweighting zu steuern und dadurch die Effizienz sowie Interpretierbarkeit der Suche zu steigern, indem unproduktive Konzeptkombinationen identifiziert und vermieden werden.

Ursprüngliche Autoren: Timothee Leleu, Sudeera Gunathilaka, Federico Ghimenti, Surya Ganguli

Veröffentlicht 2026-02-04

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Timothee Leleu, Sudeera Gunathilaka, Federico Ghimenti, Surya Ganguli

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, einem sehr talentierten, aber leicht verwirrten Lehrling beizubringen, ein komplexes Rätsel zu lösen, wie etwa das Packen von Kreisen in ein Quadrat oder das Anordnen von Punkten, um winzige Dreiecke zu vermeiden. Sie verfügen über ein mächtiges Werkzeug: ein Large Language Model (LLM), das wie ein superintelligenter, belesener Roboter ist, der Computer-Code schreiben kann.

Es gibt jedoch ein Problem: Wenn Sie den Roboter bitten, eine neue Lösung auszuprobieren, rät er oft nur zufällig oder verändert den vorherigen Versuch nur geringfügig, ohne wirklich zu verstehen, warum eine Lösung besser als eine andere ist. Es ist, als würde man jemanden bitten, ein Rezept zu verbessern, indem man wahllos Zutaten austauscht, ohne zu wissen, welche Gewürze das Gericht tatsächlich besser schmecken lassen.

Dieses Paper stellt eine neue Methode namens Contrastive Concept-Tree Search (CCTS) vor, um dies zu beheben. So funktioniert sie, unterteilt in einfache Ideen:

1. Das Problem: Suchen im Dunkeln

Derzeit arbeiten die meisten Systeme wie ein „Fitness-Wettbewerb“. Sie generieren einen Haufen Code, sehen, welcher die höchste Punktzahl erreicht, und fragen den Roboter dann, ob er genau diesen speziellen Gewinner noch besser machen kann.

Der Fehler: Dies ist so, als würde man einen Berg besteigen, indem man nur auf den Gipfel schaut, auf dem man sich gerade befindet. Man könnte auf einem kleinen Hügel stecken bleiben und denken, es sei der Gipfel, oder man könnte einen besseren Pfad verpassen, weil man zu sehr auf den einen konzentriert ist, auf dem man gerade steht. Der Roboter versteht nicht die Konzepte hinter dem Code; er sieht nur die Endpunktzahl.

2. Die Lösung: Der „Konzept-Baum“

Die Autoren erkannten, dass wir, anstatt nur auf die Endpunktzahl zu schauen, auf die Zutaten (Konzepte) innerhalb des Codes schauen sollten.

Die Metapher: Stellen Sie sich vor, der Code ist nicht nur ein Textblock, sondern ein Stammbaum von Ideen.
- Ganz oben haben Sie breite Ideen wie „Optimierung“.
- Davon zweigen sich spezifischere Ideen ab, wie „Gradientenabstieg“.
- Weiter unten folgen winzige Details wie „Adaptive Lernrate“.
Die CCTS-Methode zwingt den Roboter dazu, jedes Stück Code, das er schreibt, mit diesen „Konzept-Tags“ zu versehen.

3. Der magische Trick: „Gute“ vs. „Schlechte“ Listen

Dies ist der Kern der neuen Methode. Anstatt nur den einen besten Code auszuwählen, teilt das System alle Versuche in zwei Stapel auf:

Der „Gute“ Stapel: Die Versuche, die gut punktiert haben.
Der „Schlechte“ Stapel: Die Versuche, die schlecht punktiert haben.

Dann spielt es ein Spiel des „Unterschiede-Findens“.

Es fragt: „Welche Konzepte kommen häufig im Guten Stapel vor, fehlen aber im Schlechten Stapel?“ (Dies sind die Nützlichen Konzepte).
Es fragt auch: „Welche Konzepte kommen häufig im Schlechten Stapel vor, fehlen aber im Guten Stapel?“ (Dies sind die Fallen-Konzepte).

4. Das Ergebnis: Lernen, was man vermeiden muss

Die Forscher fanden etwas Überraschendes heraus: Das System erzielt den größten Leistungsschub nicht nur dadurch, dass es lernt, was es tun soll, sondern vor allem dadurch, dass es lernt, was es NICHT tun soll.

Analogie: Stellen Sie sich vor, Sie versuchen, den perfekten Kuchen zu backen. Die alte Methode war lediglich, immer wieder Kuchen zu backen, die „okay“ schmeckten, und zu hoffen, dass sie besser werden. Die neue Methode (CCTS) ist wie ein Koch, der erkennt: „Jedes Mal, wenn ich zu viel Salz verwende, misslingt der Kuchen. Jedes Mal, wenn ich das Backpulver vergesse, misslingt er.“
Durch das aktive Vermeiden der „Fallen-Konzepte“ (wie das Salz) wird die Suche viel effizienter. Man verschwendet keine Zeit mehr mit Sackgassen.

5. Wie sie es getestet haben

Die Forscher testeten dies an mehreren schwierigen mathematischen Rätseln (wie dem „Kreispackungsproblem“, bei dem man versucht, so viele Kreise wie möglich in eine Box zu passen).

Sie verglichen ihre neue Methode mit den alten „Fitness-basierten“ Methoden.
Das Ergebnis: Die neue Methode fand bessere Lösungen schneller.
Der „Synthetische“ Test: Um zu beweisen, dass es sich nicht nur um einen Zufall durch den spezifischen Roboter handelte, bauten sie eine künstliche, vereinfachte Version des Problems (eine „Spielwelt“), in der sie die perfekte Antwort kannten. Selbst in dieser künstlichen Welt funktionierte die neue Methode perfekt, was beweist, dass die Logik auch ohne den komplexen Roboter Bestand hat.

Zusammenfassung

Kurz gesagt: Dieses Paper lehrt die KI, aufzuhören zu raten und statgehend die Regeln des Spiels zu lernen. Indem es Ideen in einem Baum organisiert und vergleicht, was funktioniert und was nicht, lernt das System, schlechte Ideen zu vermeiden und gute zu kombinieren. Es verwandelt eine blinde Suche in eine geführte Tour und macht die Entdeckung neuer Algorithmen viel schneller und intelligenter.

Wichtigste Erkenntnis: Der größte Gewinn kommt dadurch, dass das System lernt, die falschen Konzepte zu vermeiden, und nicht nur, die richtigen zu finden.

Technisches Resümee: Kontrastiver Konzept-Baum-Suchprozess für die LLM-gestützte Algorithmen-Entdeckung

Problemstellung

Die durch Large Language Models (LLM) unterstützte Entdeckung von Algorithmen operiert als ein iterativer, Black-Box-Optimierungsprozess, bei dem ein LLM Kandidatenprogramme vorschlägt und ein externer Evaluator Feedback zur Aufgabe liefert. Während jüngste Paradigmen (z. B. FunSearch, AlphaEvolve) erfolgreich Lösungen für kombinatorische Probleme (wie etwa Erdős-artige Probleme) wiederentdeckt oder verbessert haben, stützen sie sich weitgehend auf fitnessgetriebene evolutionäre Updates. In diesen bestehenden Systemen wird die Elternselektion durch die rohe Performance (Fitness) der Programme bestimmt, und die Suche verläuft als ein Pfad über die Abstammungslinie der Programme, geordnet nach ihrer Leistung.

Eine kritische Einschränkung dieses Ansatzes besteht darin, dass der Programmbereich schwach strukturiert bleibt. Selbst wenn durch ein LLM eingeschränkt, fehlt generierten Algorithmen oft ein klares Verständnis von Lokalität, glatter Variation oder kompositorischer Struktur, die durch Suchalgorithmen genutzt werden könnten. Folglich leitet sich die Führung primär aus rohen Fitnesssignalen und dem impliziten Vorwissen des LLMs ab, statt aus einem expliziten, gelernten Verständnis darüber, welche semantischen Komponenten der Algorithmen tatsächlich nützlich sind. Diese Arbeit adressiert die offene Frage, wie das interne Repräsentationsvermögen des LLM bezüglich des Programmbereichs maximal ausgenutzt werden kann, um die Effizienz und Interpretierbarkeit der Suche zu verbessern.

Methodik: Kontrastiver Konzept-Baum-Suchprozess (CCTS)

Die Autoren führen den Contrastive Concept-Tree Search (CCTS) ein, ein Framework, das die Suchsteuerung von der rohen Fitness hin zu einem gelernten, hierarchischen semantischen Konzeptraum verschiebt. Die Kernhypothese ist, dass Algorithmen durch einen zugrunde liegenden semantischen Konzeptraum beschrieben werden können, der als Hierarchie organisiert ist, wobei Knoten Konzepte repräsentieren und Kanten Verfeinerung oder Spezialisierung kodieren.

1. Konzeptrepräsentation und Baumkonstruktion

Merkmalsextraktion: Jedes Kandidatenprogramm $x$ wird auf eine semantische Merkmalsrepräsentation $b = \Phi(x)$ abgebildet, die durch das Prompting des LLM extrahiert wird, um eine Liste relevanter Konzepte zu generieren.
Hierarchische Struktur: Diese Konzepte werden in einem wurzelbasierten Konzeptbaum organisiert. Ein Konzeptvektor $b$ ist ein Indikatorvektor, bei dem die Aktivierungen ahnen-geschlossen sind (die Aktivierung eines Kind-Konzepts impliziert die Aktivierung aller seiner Vorfahren). Der Baum ist dynamisch und wächst mit der Entdeckung neuer Konzepte während der Suche.

2. Kontrastives Lernen der Konzept-Nützlichkeit

Anstatt Eltern allein basierend auf ihrem Fitness-Score zu selektieren, lernt CCTS, welche Konzepte empirisch mit hoher Performance assoziiert sind, durch einen kontrastiven Ansatz:

Partitionierung: Das Archiv der evaluierten Programme wird in „gute“ ( $y_i \ge \tau_t$ ) und „schlechte“ ( $y_i < \tau_t$ ) Teilmengen unterteilt, basierend auf einem Leistungsschwellenwert.
Modellanpassung: Zwei probabilistische Modelle, $\hat{p}_{\eta^+}(b)$ und $\hat{p}_{\eta^-}(b)$ , werden auf die Merkmalsverteilungen der guten bzw. schlechten Teilmengen angepasst. Die Autoren nutzen einen Tree-structured Parzen Estimator (TPE)-ähnlichen Ansatz mit einem faktorisierte hierarchischen Bernoulli-Modell. Dieses Modell nimmt die bedingte Unabhängigkeit der Merkmale gegeben ihren jeweiligen Elternknoten an.
Likelihood-Ratio-Scoring: Ein Likelihood-Ratio-Score (Log-Konzept-Nützlichkeit) wird für jedes Programm berechnet:
$\log w(b) = \log \hat{p}_{\eta^+}(b) - \log \hat{p}_{\eta^-}(b)$
Dieser Score quantifiziert, wie stark eine spezifische Menge an Konzepten hochperformante Lösungen von minderwertigen unterscheidet.

3. Elternselektion und Suchdynamik

Biasierte Stichprobenziehung: Eltern werden aus dem Archiv mit einer Wahrscheinlichkeit ausgewählt, die proportional zu ihrem Likelihood-Ratio-Score ist. Dies lenkt die Suche hin zu Programmen, die Kombinationen von Konzepten enthalten, die empirisch mit Verbesserungen assoziiert sind.
Explorationsmechanismus: Um vorzeitige Konvergenz zu verhindern und die Entdeckung neuer Konzepte zu fördern, integriert CCTS einen leichtgewichtigen Explorationsmechanismus. Dieser umfasst:
- Beta-Priors: Glättung der Zählwerte, um sicherzustellen, dass neu entdeckte Konzepte niemals eine Wahrscheinlichkeit von Null haben.
- Neuheits-Bias: Abwertung von Konzepten, die häufig ausprobiert wurden, um unerschlossene Regionen des Konzeptbaums zu bevorzugen.
- Mischstrategie: Eine Mischung aus Exploitation (basierend auf dem gelernten kontrastiven Modell) und Exploration (basierend auf Neuheit) leitet die Auswahl der Konzepte, die in den Prompt des LLM für die Generierung der Kinder injiziert werden sollen.

Zentrale Beiträge

Explizite semantische Struktur: Die Arbeit schlägt vor, die latente Struktur des Algorithmenraums explizit zu machen, indem ein hierarchischer Konzeptbaum gelernt wird, wodurch man über den unstrukturierten Programmbereich hinausgeht, der in Standard-Evolutionären Algorithmen verwendet wird.
Kontrastive Führung: Es wird ein kontrastiver statistischer Rahmen eingeführt, der lernt, welche Konzepte priorisiert werden müssen und – entscheidend – welche Konzepte vermieden werden sollten, anstatt nur zu verfolgen, welche Programme am besten abschneiden.
Interpretierbarkeit: Die Methode erzeugt interpretierbare, aufgabenspezifische Konzeptbäume, die die während der Suche explorierte semantische Struktur offenlegen und Einblicle in die entdeckten algorithmischen Strategien bieten.
Synthetische Validierung: Die Autoren konstruieren eine kontrollierte synthetische Umgebung mit einem „Lehrer“-Konzeptbaum und Ground-Truth-Nützlichkeiten. Dies ermöglicht es ihnen zu validieren, dass CCTS die zugrunde liegende semantische Struktur rekonstruiert und dass die beobachteten Suchdynamiken durch das Lernen von Konzept-Nützlichkeiten und nicht durch spezifische LLM-Artefakte getrieben werden.

Experimentelle Ergebnisse

Die Autoren evaluierten CCTS auf einem Benchmark von offenen Erdős-artigen Kombinatorik-Problemen, einschließlich Kreispackung (circle packing), der arithmetischen Kakeya-Vermutung, dem Heilbronn-Dreieck-Problem und dem Quadrat-im-Quadrat-Problem.

Leistungssteigerungen: CCTS erreichte konsistent höhere Scores und eine schnellere Verbesserung im Vergleich zu Baseline-Strategien (Uniform, Greedy und $k$ -elite Selektion) über mehrere Aufgaben hinweg.
Mechanismus der Verbesserung: Die Analyse ergab, dass die Leistungssteigerungen maßgeblich dadurch getrieben werden, welche Konzepte zu vermeiden sind. Erfolgreiche Durchläufe identifizierten eine ähnliche Menge an hochnützlichen Konzepten wie erfolglose Durchläufe, zeigten aber eine signifikant bessere Fähigkeit, minderwertige (schädliche) Konzepte zu unterdrücken. Dies deutet darauf hin, dass CCTS die Suche stabilisiert, indem es unproduktive Exploration reduziert, die durch irreführende Korrelationen im ursprünglichen Prior des LLM verursacht wird.
Synthetische Validierung: In der synthetischen Umgebung zeigten die gelernten Konzept-Nützlichkeiten eine starke Korrelation ( $r=0.94$ ) mit den Ground-Truth-Lehrer-Nützlichkeiten, was bestätigt, dass die Methode effektiv aussagekräftige semantische Repräsentationen rekonstruiert.
Strukturabhängigkeit: Das optimale Gleichgewicht zwischen Exploration und Exploitation hing von der Struktur des zugrunde liegenden Konzeptbaums ab (z. B. Verzweigungsrate), was darauf hindeutet, dass Suchstrategien an die spezifische Topologie des Problemraums angepasst werden sollten.

Bedeutung und Ansprüche

Das Paper behauptet, dass CCTS ein fundamentales Missverhältnis in der aktuellen LLM-gestützten Algorithmen-Entdeckung adressiert: Hochperformante Algorithmen erzeugen nicht zwangsläufig starke Nachkommen, da Fitness ein schlechter Stellvertreter für die Evolvierbarkeit in einem schwach strukturierten Raum ist. Durch die Verschiebung der Selektion von roher Fitness hin zu semantischen Belegen für Verbesserung ermöglicht CCTS der Suche, in einem Konzeptraum zu operieren, in dem Distanz, Rekombination und Suchrichtung eine Bedeutung besitzen.

Die Autoren positionieren diese Arbeit als methodischen Fortschritt hin zu einer zuverlässigeren und skalierbareren Algorithmen-Entdeckung. Sie betonen, dass, während die aktuellen Ergebnisse relative Verbesserungen gegenüber Baselines auf spezifischen Benchmarks zeigen, der primäre Beitrag in der Demonstration dessen liegt, wie explizite, menschenkompatible semantische Konzeptstrukturen die automatisierte Entdeckung transparenter, kontrollierbarer und effizienter machen können. Die Arbeit legt nahe, dass zukünftige Systeme sich auf das Lernen und Ausnutzen dieser latenten semantischen Hierarchien konzentrieren sollten, anstatt sich rein auf Black-Box-Fitnesssignale zu verlassen.