- FunSearch von Google DeepMind kombiniert ein vortrainiertes LLM mit einem automatischen Evaluator, um bei Problemen aus Mathematik und Informatik überprüfbare neue Lösungsansätze in Form von Code zu suchen
- Das LLM erzeugt neue Programme, der automatische Evaluator bewertet sie, und Programme mit hoher Punktzahl werden in einer evolutionären Iteration wieder in den Pool aufgenommen, um die Lösungen zu verbessern
- Beim Cap-Set-Problem fand FunSearch in einigen Einstellungen die bislang größten entdeckten Cap Sets und zeigte auch in Größenordnungen Leistung, die für bisherige State-of-the-Art-Rechensolver schwer zu bewältigen sind
- Derselbe Ansatz wurde auch auf Online Bin Packing angewandt; dabei packten an die Dateneigenschaften angepasste Programme die gleiche Anzahl von Items in weniger Bins als bestehende Heuristiken
- Da die Ergebnisse als für Menschen lesbare kurze Programme vorliegen, können Forschende die Struktur der Lösungen prüfen und sie für eine Mensch-KI-Zusammenarbeit zur Verbesserung der Problemformulierung nutzen
Grundidee von FunSearch
- FunSearch sucht nach als Computercode geschriebenen Funktionen, um neue Lösungen in Mathematik und Informatik zu finden
- Der Name leitet sich davon ab, dass nach Funktionen (functions) gesucht wird
- Da LLMs sachlich falsche Informationen erzeugen können, kombiniert FunSearch ein LLM, das kreative Vorschläge macht, mit einem automatischen Evaluator, um fehlerhafte Ideen herauszufiltern
- Es gilt als erster Fall, in dem mit einem LLM neue Entdeckungen bei schwierigen offenen Problemen aus Wissenschaft und Mathematik erzielt wurden
Evolutionäre Iterationsstruktur
- Zunächst beschreibt der Nutzer das Problem in Codeform
- Dazu gehört ein Verfahren zur Bewertung von Programmen
- Außerdem gibt es ein Seed-Programm, mit dem der Programmpool initialisiert wird
- In jeder Iteration wird ein Teil des aktuellen Programmpools in das LLM eingegeben
- Das LLM erzeugt auf Basis bestehender Programme neue Programme
- Die neuen Programme werden automatisch ausgeführt und bewertet
- Programme mit hoher Punktzahl werden wieder in die Programmdatenbank aufgenommen
- Der Nutzer kann jederzeit das bislang gefundene Programm mit der höchsten Punktzahl abrufen
- FunSearch nutzte Google PaLM 2, ist aber auch mit anderen auf Code trainierten LLMs kompatibel
- Um schwierige kombinatorische Probleme zu bewältigen, wurde auch die Suchstruktur verstärkt
- Sie beginnt mit allgemeinem Wissen über das Problem und konzentriert sich dann auf die zentralen Ideen, die für neue Entdeckungen nötig sind
- Sie erhöht die Vielfalt der Ideen, um Stagnation zu vermeiden
- Sie führt den Evolutionsprozess parallel aus, um die Effizienz zu steigern
Ergebnisse beim Cap-Set-Problem
- Das erste Anwendungsgebiet war das Cap-Set-Problem, das Mathematikerinnen und Mathematiker aus verschiedenen Forschungsfeldern seit Jahrzehnten beschäftigt
- Dabei geht es darum, in einem hochdimensionalen Gitter die maximale Größe einer Punktmenge zu finden, in der keine drei Punkte auf einer Geraden liegen – also eines Cap Sets
- Das Problem dient auch als Modell für andere Fragen der extremalen Kombinatorik (extremal combinatorics)
- Da die Zahl der möglichen Fälle schnell größer wird als die Zahl der Atome im Universum, funktioniert Brute-Force-Berechnung nicht
- FunSearch erzeugte Lösungen in Form von Programmen und fand in einigen Einstellungen die bislang größten entdeckten Cap Sets
- Dieses Ergebnis entspricht dem größten Zuwachs bei der Größe von Cap Sets in den vergangenen 20 Jahren und zeigte bessere Leistung auch in Bereichen, in denen die Problemgröße über die aktuellen Fähigkeiten bisheriger State-of-the-Art-Rechensolver hinausgeht
- FunSearch zeigte, dass sich bei kombinatorischen Problemen, für die sich nur schwer Intuition entwickeln lässt, bestehende Ergebnisse übertreffen lassen; künftig könnte dies auf ähnliche theoretische Probleme der Kombinatorik und auf Bereiche wie die Kommunikationstheorie übertragen werden
Kurze Programme, die Menschen interpretieren können
- FunSearch ist keine Blackbox, die nur Antwortlisten ausgibt, sondern erzeugt Programme, die zeigen, wie eine Lösung aufgebaut ist
- Das knüpft auch an die übliche wissenschaftliche Vorgehensweise an, neue Entdeckungen oder Phänomene über ihren Erzeugungsprozess zu erklären
- FunSearch bevorzugt Lösungen, die als kompakte Programme mit niedriger Kolmogorov-Komplexität dargestellt werden
- Die Kolmogorov-Komplexität ist die Länge des kürzesten Computerprogramms, das eine Lösung ausgibt
- Kurze Programme können sehr große Objekte beschreiben und helfen dabei, auf großskalige „Nadel-im-Heuhaufen“-Probleme zu skalieren
- Die Programmausgabe ist für Forschende leichter zu verstehen
- In einigen ausgegebenen Codes mit hoher Punktzahl wurden interessante Symmetrien beobachtet; darauf aufbauend wurde die Problemformulierung verfeinert, um bessere Lösungen zu erhalten
- Jordan Ellenberg sagte, FunSearch biete einen „völlig neuen Mechanismus zur Entwicklung von Angriffsstrategien“, und die erzeugten Lösungen seien konzeptionell deutlich reichhaltiger als Zahlenlisten
Anwendung auf Online Bin Packing
- FunSearch wurde auch auf das praktische Informatikproblem Bin Packing angewandt
- Beim Bin Packing geht es darum, Items unterschiedlicher Größe in möglichst wenige Bins zu packen
- Praktische Anwendungsbeispiele sind das Beladen von Containern oder die Zuweisung von Rechenjobs in Rechenzentren zur Kostensenkung
- Online Bin Packing wird meist mit Heuristiken behandelt, die auf menschlicher Erfahrung beruhen
- Für konkrete Situationen mit unterschiedlichen Größen, Zeitpunkten und Kapazitäten kann es schwierig sein, geeignete Regelmengen zu finden
- Obwohl das Problem sich stark vom Cap-Set-Problem unterscheidet, ließ sich FunSearch leicht darauf einstellen und erzeugte Programme, die automatisch an die Dateneigenschaften angepasst waren
- Die erzeugten Programme packten die gleiche Anzahl von Items in weniger Bins als bestehende Heuristiken
- Auch andere KI-Ansätze wie neuronale Netze oder Reinforcement Learning können bei schwierigen kombinatorischen Problemen wirksam sein, erfordern für die Bereitstellung aber unter Umständen erhebliche Ressourcen
- Da FunSearch leicht überprüfbaren und deploybaren Code ausgibt, kann es Lösungsformen erzeugen, die sich in verschiedene reale Industriesysteme integrieren lassen
Updates und Erweiterungen 2024
- Ein im Dezember 2024 veröffentlichter arXiv-Bericht zeigte, dass der FunSearch-Ansatz genutzt werden kann, um menschliche Leistung im kombinatorischen Competitive Programming zu verstärken
- Klassische Programmierwettbewerbe wie Codeforces verlangen vollständige Lösungen für klassische algorithmische Probleme innerhalb von Zeit- und Speichergrenzen
- Kombinatorische Wettbewerbe behandeln komplexe Probleme, bei denen nicht eine einzige richtige Antwort gesucht wird, sondern die bestmögliche Näherungslösung
- Dieser Ansatz kann bessere Lösungen erzeugen als diejenigen, die von Teilnehmenden im obersten Perzentil gefunden wurden
- Er nutzt eine Kooperationsstruktur, bei der menschliche Programmiererinnen und Programmierer das Backbone des Lösungscodes schreiben und das LLM die steuernde Funktion kreativ weiterentwickelt
- Mit der Verbesserung allgemeiner LLMs wurden keine codespezifischen Modelle mehr benötigt; als Basis kann Gemini 1.5 Flash verwendet werden
- Neben Competitive Programming wurde FunSearch auch eingesetzt, um Methoden zu finden, mit denen sich Funktionen in einem Bayesian-Optimization-Framework besser optimieren lassen
Richtung LLM-basierter Entdeckungen
- FunSearch zeigt, dass sich LLMs nicht nur für neue mathematische Entdeckungen, sondern auch zur Erzeugung potenzieller Lösungen für wichtige reale Probleme nutzen lassen, wenn Mechanismen zur Vermeidung von Halluzinationen eingebaut sind
- Bei alten und neuen Problemen in Wissenschaft und Industrie könnte es üblich werden, mit LLM-basierten Ansätzen wirksame und maßgeschneiderte Algorithmen zu erzeugen
- FunSearch kann sich mit dem allgemeinen Fortschritt von LLMs verbessern und soll künftig erweitert werden, um seine Fähigkeiten auf verschiedene wissenschaftliche und technische Probleme auszudehnen
1 Kommentare
Hacker-News-Meinungen
Ich frage mich, wie sehr ein LLM hier wirklich nötig ist.
Auf den ersten Blick scheint die Rolle des LLM darin zu bestehen, etwas Plausibles wie eine Python-Funktion zu erzeugen, die einer vorgegebenen Typsignatur folgt.
Aber auch ohne LLM müsste man zufällige, gültige Python-Funktionen erzeugen können, die eine gegebene Typsignatur erfüllen. Das wäre eine Übung wie [1], nur für eine deutlich komplexere Sprache; eine eingeschränkte Sprache wäre womöglich sogar einfacher zu verwenden. Auch Ansätze wie PushGP [2] könnten möglich sein.
Die Fragen sind: (1) Worin besteht hier der Mehrwert des LLM, reduziert es die Zahl der für die Konvergenz nötigen Evaluierungen stark, und wenn ja, wie? (2) Sind andere Genetic-Programming-Verfahren beim selben Problem weniger konkurrenzfähig und liefern Lösungen mit niedrigerer Fitness? (3) Wenn traditionelleres Genetic Programming eine ähnliche Fitness erreicht, wie unterscheidet sich dann der Rechenaufwand inklusive der Trainingskosten des LLM?
[1] http://www.davidmontana.net/papers/stgp.pdf
[2] https://faculty.hampshire.edu/lspector/push.html
Affen und Schreibmaschinen reichen nicht aus; der Grund, warum hier Palm2 verwendet wird, ist, dass Kandidaten nicht zufällig, sondern plausibel sein müssen. Man will keine Zeit mit unsinnigen Programmen verschwenden.
Außerdem haben genetische Algorithmen, die auf der Erzeugung zufälliger Programme basieren, ein sehr großes Cold-Start-Problem. Wenn die Fitness aller Kandidaten 0 ist, gibt es am Anfang — und vermutlich bis zum Ende — wahrscheinlich keinen Fortschritt.
Ich bin mit genetischen Algorithmen nicht extrem vertraut, aber so etwas scheint mir nicht außerhalb dessen zu liegen, was ein genetischer Algorithmus finden könnte. Allerdings wäre ich überrascht, wenn es schon viele Leute tatsächlich ausprobiert hätten.
Andererseits dürfte ein genetischer Ansatz ohne LLM, wie in Anhang A.2 des Papers zu sehen, mehr manuelles Design erfordern als der LLM-Ansatz.
Der Unterschied, den das LLM hier macht, besteht darin, den möglichen Mutationsraum weitgehend auf semantisch plausible Programme zu beschränken.
Zu Punkt 3: Ein trainiertes LLM ist für sehr viele Zwecke nützlich, daher sind die Kosten für das Training von Grund auf bei Amortisierung nicht groß. Es kann zusätzliche Kosten für das Fine-Tuning auf das FunSearch-Framework geben, aber Fine-Tuning-Kosten sind ziemlich gering. Der Einsatz in diesem Framework ist wahrscheinlich vorteilhaft gegenüber reinem Genetic Programming.
LLMs verkleinern den Suchraum stark; natürlich oft auch auf falsche Weise, aber danach kann man induktive Programmsynthese anwenden, um zu verfeinern und zu testen. Ohne LLM ist so ein Ansatz nach aktuellem Wissensstand unmöglich, weil man selbst in trivialen Fällen Milliarden völlig unsinniger Programme testen würde.
Der wichtige Kontext ist, dass diese Entdeckung gezeigt hat, dass eine bestimmte Zahl aus der Kombinatorik nicht mehr in dem im letzten Jahr bekannten Bereich von 2,218 bis 2,756 liegt, sondern jetzt zwischen 2,2202 und 2,756.
Die Verbesserung wurde weniger durch einen logikzentrierten mathematischen Beweis erreicht, sondern durch das Finden bestimmter Folgen mit speziellen Eigenschaften. Das heißt aber nicht, dass es nicht rigoros wäre.
Es ist eine interessante und wahrscheinlich nützliche Methode, Beispiele zu erzeugen, und kommt im Grunde einem genetischen Algorithmus mit LLM-Zusatz nahe.
Subbaraos Kommentar zu „Self-Play“: https://twitter.com/rao2z/status/1728121216479949048
Dem Beitrag zufolge nutzt FunSearch eine vom LLM angetriebene evolutionäre Methode, um Ideen mit hohen Scores zu fördern und weiterzuentwickeln. Diese Ideen liegen in Form von Computerprogrammen vor und können daher automatisch ausgeführt und bewertet werden.
Der Nutzer schreibt die Problembeschreibung in Codeform. Diese Beschreibung enthält ein Verfahren zur Bewertung der Programme sowie Seed-Programme zur Initialisierung des Programmpools.
In jeder Iteration wählt FunSearch einige Programme aus dem aktuellen Pool aus, das LLM erweitert sie kreativ zu neuen Programmen, und diese neuen Programme werden automatisch bewertet. Die besten werden wieder dem bestehenden Pool hinzugefügt und erzeugen so eine Selbstverbesserungsschleife.
Bei der Websuche verwende ich pplx.ai und phind.com ähnlich als Evaluatoren. Ich stelle eine Frage, schaue, welche Referenzen und Weblinks sie abrufen, und verfeinere dann die Frage oder stelle Anschlussfragen, um tiefere oder andere Materialien hervorzuholen. Das funktioniert besser, um versteckte Perlen zu finden, als reddit oder Google zu durchforsten.
Auch auf Tech Twitter gibt es viele hervorragende Inhalte; da Grok nun für alle verfügbar ist, hoffe ich, dass es für Recherchen genutzt wird.
https://twitter.com/gfodor/status/1735348301812383906
Es gibt die Aussage: „Wenn DeepMind endgültig bewiesen hat, dass neuronale Netze wirklich neues Wissen erzeugen können, dann ist das die wichtigste Entdeckung seit dem Feuer.“
Falls das tatsächlich so ist, frage ich mich, warum nicht alle darüber sprechen. Beeindruckend ist, dass sie es mit PaLM 2 geschafft haben, das weniger fortgeschritten ist als GPT-4 oder Gemini. Es dürfte enorm sein, was die nächsten paar Modellgenerationen mit solchen Methoden leisten können.
Das LLM ersetzt den Operator für zufällige Mutationen und bekommt im Grunde eine Anfrage wie: „Schlage eine sinnvolle Änderung an diesen 20 Zeilen Python vor.“ Es wirkt wie eine großzügige Einschätzung, den Verdienst für die Wissensgenerierung dem neuronalen Netz zuzuschreiben.
Außerdem ist es nicht nur nötig, dass die Struktur „schwer zu erzeugen, leicht zu bewerten“ ist; es hängt auch stark von der Art des Problems ab. Der Teil, den man evolvieren möchte, muss sich in eine sehr kurze einzelne Python-Funktion zerlegen lassen.
Dass ein LLM eine neue Lösung in der hochdimensionalen Geometrie finden kann, wo es seit 20 Jahren keinen Fortschritt gab, geht weit darüber hinaus, bloß plagiiert wirkende Stücke aus Trainingsdaten plausibel aneinanderzureihen.
Es deutet darauf hin, dass in den Fähigkeiten von LLMs eine verborgene Tiefe steckt, wenn man nur herausfindet, wie man sie richtig promptet und bewertet.
Das Ergebnis hat meine Erwartungen deutlich übertroffen. Man weiß nicht, welche Entdeckungen sich hinter dem nächsten Prompt und einem zufälligen Seed verbergen.
Für LLMs gilt das ebenfalls: https://www.nature.com/articles/s41587-022-01618-2
a) Es gibt einen effizienten Evaluator, b) es gibt reichhaltiges Score-Feedback, das das Ausmaß der Verbesserung quantifiziert, also kein binäres Signal, c) man kann ein Gerüst mit einem isolierten Teil bereitstellen, der evolviert werden soll.
Die Erzeugung von Beweisen für Theoreme liegt zum Beispiel außerhalb dieses Bereichs, weil nicht klar ist, wie man ein ausreichend reichhaltiges Score-Signal bereitstellen soll.
Es ist zwar eine großartige Leistung, aber im Vergleich zur Entdeckung des Feuers und zu vielen Dingen dazwischen, etwa Elektrizität, scheint es nicht in derselben Liga zu spielen.
Kurz gesagt: Wenn ein Programm-Template/-Gerüst und eine Fitness-Funktion gegeben sind, erzeugt man mit einem LLM Populationen von Programmen und verwendet Prompts, die aus k anderen Versionen ein neues Programm machen; dabei fanden sie heraus, dass k=2 gut funktioniert. Das ist ein wenig biologisch. Anschließend werden die Programme auf Inputs ausgeführt und mit der Fitness-Funktion bewertet; für die Evolution wird ein Inselmodell verwendet.
Der Prompt fühlt sich vom Prinzip her wohl etwa so an:
def foo_v1(a, b): ...def foo_v2(a, b): ...# Erstelle mithilfe von foo_v1 und foo_v2 eine neue Funktion. Du darfst nur das ändern, was wie {{ THIS }} in doppelten geschweiften Klammern stehtdef foo(a, b): return a + {{}}Wenn es nur etwa 1e6 LLM-Aufrufe brauchte, um neue Ergebnisse zu erzielen, ist das eine ziemlich beeindruckend kleine Zahl. Es heißt auch, dass Auswertung/Scoring einige Minuten dauert.
Hier lohnt es sich, über den Trade-off zwischen Tiefe und Breite nachzudenken. Das hängt mit Latenz und Durchsatz beim Bewerten einzelner Programme und Populationen zusammen. Was wäre, wenn man für alle Programme Memoization einsetzt? Wenn man die Loss-Funktion mehrdimensional hält, mit je einer Dimension pro Input oder Input-Bucket, könnte man dann nicht zuerst Populationen von Programmen finden, die in unterschiedlichen Bereichen gut sind, und sie später kombinieren?
Ich frage mich auch, ob es Vorwissen darüber gab, wie selten Cap Sets sind. Ich frage mich, ob es zuvor rechnerische Versuche gab, die erfolglos blieben, aber so oder so ist es cool.
Um den Twitter-/X-Beitrag anders zu formulieren: Von jetzt an wird es nur noch besser.
Das heißt: KI-Fähigkeiten wachsen monoton, und das schon seit Jahrzehnten; in diesem Fall verbessern sich die Fähigkeiten rekursiv selbst. Ich sehe bereits, dass KI-Autovervollständigung, KI-gestütztes Refactoring und von KI automatisch erzeugte Code-Review-Diffs in Kommentaren meine persönliche Coding-Produktivität um etwa 20–30 % steigern.
Es fühlt sich an, als wäre KI in einer Phase wie Intel in den 90ern angekommen. Wenn man Code doppelt so schnell machen wollte, musste man nur auf die nächste Revision der Intel-CPU warten. Jetzt übernehmen KI-Modelle diese Rolle. Wenn man Teile von Geschäftsabläufen wie Coding, Kundensupport oder Bug-Triage an ein LLM-System angeschlossen hat, besteht die „Verbesserung“ des Systems nur noch darin, den Modellnamen zu ändern.
Nach der anfänglichen Integration kann man in den nächsten Jahren mit minimalem Aufwand erwarten, dass „alles auf magische Weise Schritt für Schritt ein bisschen besser wird“.
Insbesondere wurden die Ergebnisse mit und ohne LLM nicht verglichen. So wie ich es verstehe, zeigt dieses Paper Ergebnisse von genetischer Programmierung, bei der mit einem LLM Python-Kernelfunktionen erzeugt werden, die vermutlich einer gegebenen Typsignatur folgen. Für diese Aufgabe ist ein LLM nicht unbedingt erforderlich.
Daher bleibt es eine offene Frage, ob das LLM hier tatsächlich etwas Besonderes leistet.
Eines der angegangenen Probleme war das Cap-Set-Problem.
https://en.m.wikipedia.org/wiki/Cap_set
Bei diesem Problem geht es darum, in einem hochdimensionalen Gitter die größte Punktmenge zu finden, bei der keine drei Punkte auf einer Geraden liegen, also ein Cap Set. Es ist wichtig, weil es als Modell für andere Probleme der extremalen Kombinatorik dient. Die extremale Kombinatorik untersucht, wie groß oder klein Sammlungen von Zahlen, Graphen oder anderen Objekten sein können. Brute-Force-Berechnung funktioniert bei diesem Problem nicht, weil die Zahl der zu berücksichtigenden Möglichkeiten schnell die Zahl der Atome im Universum übersteigt.
FunSearch erzeugte Lösungen in Form von Programmen und fand in einigen Einstellungen die größten bisher entdeckten Cap Sets. Das ist die größte Steigerung der Cap-Set-Größe in den letzten 20 Jahren. Außerdem wächst dieses Problem in Dimensionen hinein, die weit jenseits der Fähigkeiten aktueller State-of-the-Art-Rechensolver liegen, sodass FunSearch diese Solver übertraf.
Ich frage mich, wie man symbolisches Schließen in LLMs integrieren kann, oder ob das überhaupt möglich ist.
Das jüngste FunSearch-Paper von DeepMind betonte, dass es ein vortrainiertes großes Sprachmodell nutzte, um Code-Verbesserungen zu generieren.
Interessanterweise war das primäre LLM zwar Codey auf Basis der PaLM2-Modellfamilie, in den Zusatzmaterialien wird aber auch das Open-Source-LLM StarCoder erwähnt.
Im GitHub-Repository von FunSearch ist eine solche LLM-Implementierung jedoch nicht enthalten. In
sampler.pyfindet sich zum Beispiel folgender Code:Dieser Code zeigt, dass eine externe LLM-Implementierung erforderlich ist. Wenn StarCoder erfolgreich eingesetzt wurde, ist es überraschend, dass es keine Integrationsanleitung oder Basisimplementierung dafür oder für ein ähnliches Open-Source-LLM gibt. Solche Inhalte hätten die Reproduzierbarkeit und Zugänglichkeit der Forschung deutlich verbessert.
Unabhängig davon, ob es sich dabei um überprüfbares neues Wissen handelt, ist dies mit Blick auf das Problem, den Zugang zu KI über Modellgröße oder andere regulatorische Mittel zu beschränken, eine interessante Fallstudie.
Solche Beschränkungen verschaffen Unternehmen einen unfairen Vorteil, die neues Wissen oder Naturgesetze entdecken und monetarisieren können, ohne sie zu teilen.