🤖 machine learning

LLM Priors for ERM over Programs

Dieses Paper stellt \textsc{LLM-PV} vor, ein Propose-and-Verify-Framework, das vortrainierte LLM-Priors nutzt, um effizient empirische Risikominimierung über diskrete Programklassen durchzuführen, ohne eine erschöpfende Enumeration oder Gradienten-Updates zu benötigen, wodurch eine robuste Generalisierung bei algorithmischen Aufgaben ermöglicht wird, bei denen traditionelle Methoden versagen.

Ursprüngliche Autoren: Shivam Singhal, Priyadarsi Mishra, Eran Malach, Tomer Galanti

Veröffentlicht 2026-07-03

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Shivam Singhal, Priyadarsi Mishra, Eran Malach, Tomer Galanti

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

Das große Problem: Die Nadel im Heuhaufen finden

Stellen Sie sich vor, Sie versuchen, einem Computer eine geheime Regel beizubringen. Die Regel ist einfach, wie zum Beispiel: „Wenn die Zahl durch 3 teilbar ist, sage ‚Ja‘; andernfalls sage ‚Nein‘.“ Aber der Computer kennt die Regel nicht; er sieht nur ein paar Beispiele von Zahlen und die dazugehörigen Antworten.

In der Welt der Informatik gibt es zwei Hauptwege, um diese Regel zu finden:

Der „Brute Force“-Detektiv: Diese Methode versucht, jede einzelne mögliche Regel im Universum aufzuschreiben, eine nach der anderen, und prüft, ob sie zu den Beispielen passt.
- Das Problem: Wenn die Regel auch nur ein wenig komplex ist, ist die Anzahl der möglichen Regeln so gewaltig (wie die Anzahl der Sandkörner an allen Stränden der Erde), dass diese Methode länger als das Alter des Universums dauern würde, um fertig zu werden. Sie ist zu langsam.
Der „Gradient Descent“-Schüler: So lernt die moderne KI (wie die Chatbots, die Sie verwenden) normalerweise. Sie beginnt mit einer Vermutung und dreht dann langsam an ihren internen Reglern, um besser zu werden – wie ein Schüler, der für eine Prüfung lernt, indem er kleine Fehler macht und diese korrigiert.
- Das Problem: Für bestimmte Arten von logischen Regeln (wie das Überprüfen, ob eine Zahl eine Primzahl ist, oder das Zählen spezifischer Muster) kommt diese „Nachjustierungs“-Methode nicht weiter. Sie lernt vielleicht die Übungsprüfung perfekt auswendig, scheitert aber völlig, wenn sie eine neue, leicht andere Frage erhält. Es ist wie ein Schüler, der die Antworten auswendig gelernt hat, aber nicht die Mathematik dahinter verstanden hat.

Die neue Lösung: LLM-PV (Der kluge Bibliothekar)

Die Autoren schlagen einen dritten Weg namens LLM-PV vor. Stellen Sie sich das wie das Einstellen eines klugen Bibliothekars vor, der Ihnen hilft, die Regel zu finden.

So funktioniert der Prozess Schritt für Schritt:

Der Vorschlag (Die Vermutung des Bibliothekars): Anstatt jedes einzelne Buch in der Bibliothek zu prüfen (Brute Force) oder zu versuchen, die ganze Bibliothek von Grund auf neu zu schreiben (Gradient Descent), bitten Sie den Klugen Bibliothekar (ein vortrainiertes Large Language Model) um ein paar Vorschläge.
- Die Magie: Der Bibliothekar hat Millionen von Büchern und Code-Schnipseln gelesen. Wenn Sie ihm Ihre Beispiele zeigen, rät er nicht wahllos. Er nutzt seine „Intuition“ (Vorwissen), um einige plausible Regeln vorzuschlagen, die funktionieren könnten. Er verengt die Suche von „allen möglichen Regeln“ auf „einige wahrscheinliche Kandidaten“.
Die Verifizierung (Die Testfahrt): Der Bibliothekar schreibt diese Regeln als tatsächlichen Computercode auf. Sie nehmen diese Code-Schnipsel dann und lassen sie gegen Ihre Beispiele laufen, um zu sehen, welcher tatsächlich funktioniert.
- Wichtiger Punkt: Dem Bibliothekar ist es nicht erlaubt, seine Meinung basierend auf den Testergebnissen zu ändern. Er macht lediglich die Vorschläge. Die Auswahl des Gewinners erfolgt strikt durch die Überprüfung des Codes gegen die Daten.
Die Auswahl (Der Gewinner): Sie wählen den Code-Schnipsel aus, der die meisten Antworten richtig liefert.

Warum das eine große Sache ist

Die Arbeit zeigt, dass dieser „Kluge Bibliothekar“-Ansatz unglaublich effizient ist.

Es ist schnell: Es müssen nicht Milliarden von Regeln geprüft werden. Es werden nur eine Handvoll kluger Vermutungen geprüft.
Es ist genau: Im Gegensatz zu den „nachjustierenden“ KI-Methoden, die bei Logikrätseln oft scheitern, findet diese Methode die exakte mathematische Regel (wie den Miller-Rabin-Primzahltest zur Überprüfung von Primzahlen).
Es generalisiert: Das ist der beeindruckendste Teil. Wenn Sie das System mit kurzen Zahlen lehren (z. B. 10 Stellen), lernt es die Regel, nicht nur die Zahlen. Wenn Sie es also fragen, ob eine 100-stellige Zahl eine Primzahl ist, funktioniert es immer noch perfekt. Die „nachjustierende“ KI scheitert hier meistens und kommt bei längeren Zahlen durcheinander.

Eine Analogie aus der realen Welt: Backen lernen

Stellen Sie sich vor, Sie möchten das Geheimrezept für einen Kuchen lernen.

Brute Force: Sie versuchen, einen Kuchen mit jeder möglichen Kombination von Zutaten zu backen (Salz, Zucker, Sand, Steine usw.), bis einer gut schmeckt. Das dauert ewig.
Gradient Descent (Standard-KI): Sie backen einen Kuchen, probieren ihn und sagen: „Braucht mehr Zucker.“ Sie backen erneut: „Weniger Mehl.“ Sie machen das immer wieder. Irgendwann backen Sie vielleicht einen Kuchen, der exakt wie der spezifische Kuchen schmeckt, den Sie kopiert haben, aber wenn Sie die Ofentemperatur ändern oder eine andere Marke Mehl verwenden, fällt Ihr Kuchen auseinander, weil Sie nur gelernt haben, diese eine Charge nachzuahmen, und nicht das Prinzip des Backens.
LLM-PV: Sie fragen einen Meisterkoch (das LLM), der schon Millionen von Rezepten gesehen hat. Sie zeigen ihm ein paar Hinweise auf den Kuchen. Der Koch sagt: „Ich wette, es ist ein Schokoladenkuchen mit einer speziellen Gewürzmischung.“ Er schreibt drei spezifische Rezepte auf. Sie backen diese drei. Eines davon ist perfekt. Sie mussten nicht eine Million Kuchen backen und Sie mussten das Rezept nicht endlos nachjustieren. Sie haben das tatsächliche Rezept bekommen, das in jedem Ofen funktioniert.

Das Fazit

Die Arbeit argumentiert, dass wir KI nicht nur dazu nutzen sollten, Antworten direkt vorherzusagen. Stattdessen sollten wir KI als Suchwerkzeug einsetzen, um potenzielle Lösungen (Programme) zu generieren, und dann durch striktes Testen die beste Lösung auswählen. Dies kombiniert den „gesunden Menschenverstand“ eines Large Language Models mit der Zuverlässigkeit eines Computerprogramms und ermöglicht es uns, komplexe Regeln aus sehr wenigen Beispielen zu lernen.

Technisches Resümee: LLM-Priors für ERM über Programme

Problemstellung

Das Paper adressiert das fundamentale Spannungsfeld zwischen Dateneffizienz (Sample Efficiency) und Recheneffizienz bei der Erlernung kurzer, diskreter Programmbeschreibungen (z. B. „Python-Code“) aus gelabelten Daten.

Die klassische Lerntheorie (PAC-Learning) legt nahe, dass, falls eine Zielfunktion eine kurze Programmbeschreibung der Länge $L$ über einem Alphabet $\Sigma$ besitzt, sie mittels Empirical Risk Minimization (ERM) über der Klasse der Programme aus $\tilde{O}(L \log |\Sigma|)$ Beispielen gelernt werden kann. Die Implementierung von ERM erfordert jedoch eine exhaustive Enumeration (vollständige Aufzählung) potenzieller Programme, was als $\Theta(|\Sigma|^L)$ skaliert und somit selbst für moderate $L$ rechnerisch unmöglich ist.

Im Gegensatz dazu vermeiden moderne Deep-Learning-Ansätze unter Verwendung von Stochastic Gradient Descent (SGD) auf hochkapazitiven neuronalen Netzen die explizite Enumeration und sind recheneffizient. Dennoch zeigen theoretische Ergebnisse im Rahmen des Statistical Query (SQ)-Frameworks, dass gradientenbasierte Methoden Schwierigkeiten mit strukturierten, „SQ-harten“ Familien haben (wie etwa Paritätsfunktionen und kryptographischen Primitiven). Diese Methoden benötigen oft exponentiell viele Beispiele, um erfolgreich zu sein, da die Gradienten-Schnittstelle schlecht auf die diskrete Struktur der Zielregel abgestimmt ist, was zu einem Scheitern der Generalisierung über die Trainingssequenzlängen hinaus führt.

Die zentrale Frage lautet: Können wir die Dateneffizienz von ERM über kurze Programme wiederherstellen, ohne den vollen Aufwand einer exhaustiven Enumeration zu tragen?

Methodik: LLM-PV

Die Autoren schlagen LLM-PV (LLM Propose-and-Verify) vor, einen Lernalgorithmus, der ein vortrainiertes Large Language Model (LLM) nicht als Prädiktor, sondern als Such-Prior für ERM behandelt.

Der Algorithmus

LLM-PV entkoppelt die Rollen von Vorschlag (Proposal) und Selektion:

Vorschlag (Der Prior): Ein vortrainiertes LLM wird mit einem Trainingssatz $S_{tr}$ gepromptet, um eine datenabhängige Verteilung über Kandidatenprogramme zu induzieren. Das LLM generiert eine kleine Anzahl von Kandidatsprogrammen (oder Edits), von denen hypothetisch angenommen wird, dass sie die Daten erklären.
Verifizierung (Der ERM-Schritt): Jedes Kandidatsprogramm wird kompiliert und auf einem gehaltenen Validierungssatz $S_{val}$ ausgeführt. Programme, die nicht kompilieren, nicht terminieren oder ungültige Ausgaben produzieren, werden verworfen.
Selektion: Der Algorithmus wählt das Programm mit dem niedrigsten Validierungsfehler aus. Entscheidend ist, dass keine Gradienten-Updates am LLM durchgeführt werden und kein Feedback aus der Validierung genutzt wird, um die Sampling-Verteilung des LLMs während der Suche anzupassen. Das LLM fungiert rein als Mechanismus für den induktiven Bias.

Theoretischer Rahmen

Das Paper formalisiert die Leistung von LLM-PV mittels einer „Propose-and-Verify“-Garantie. Wenn die Vorschlagsverteilung des LLM eine nicht vernachlässigbare Masse $p_\epsilon(S_{tr})$ auf Programmen mit einem Populationsfehler $\le \epsilon$ platziert, skaliert die Anzahl der Versuche $k$ , die benötigt werden, um eine gute Hypothese zu finden, als $O(\log(1/\delta) / p_\epsilon(S_{tr}))$ . Dies ersetzt den exponentiellen Suchraum $|\Sigma|^L$ durch eine effektive Suchgröße von $1/p_\epsilon(S_{tr})$ .

Die Autoren liefern zudem theoretische Untergrenzen, die zeigen, dass für geplante $k$ -Paritäts-Probleme das Mini-Batch-Koordinaten-SGD mit endlicher Präzision $\Omega(\sqrt{N}/2^b)$ frische Beispiele benötigt (wobei $N$ die Anzahl der möglichen Ziele ist), während die Enumeration $\Theta(|\Sigma|^L)$ Zeit erfordert. Dies etabliert ein Regime, in dem sowohl naive Enumeration als auch Standard-Gradienten-Training scheitern, was den LLM-PV-Ansatz motiviert.

Zentrale Beiträge

Formalisierung des Compute-Sample-Tensions: Das Paper isoliert ein spezifisches Small-Data-Regime (geplante $k$ -Parität), in dem endliches Klassen-ERM dateneffizient, aber rechnerisch unpraktikabel ist, während gradientenbasiertes Training recheneffizient, aber datenineffizient aufgrund von SQ-Härte ist.
LLM-PV Algorithmus: Die Einführung einer sauberen „Propose-and-Verify“-Pipeline, die vortrainierte LLMs strikt als Vorschlagsmechanismus nutzt. Dies bewahrt die Auditierbarkeit und die theoretischen Garantien von ERM (Selektion basierend auf gehaltenem Fehler), während es die Fähigkeit des LLM nutzt, die Suche auf plausible Hypothesen zu konzentrieren.
Empirischer Nachweis der Regel-Rekonstruktion: Umfangreiche Experimente über diverse algorithmische Aufgaben hinweg (Paritäts-Varianten, Cellular Automata, Palindrome, Dyck-2, Primzahltests, Cellular Automata, SHA-256 Parität) zeigen, dass LLM-PV oft die exakte zugrunde liegende Regel aus so wenig wie 200 gelabelten Beispielen rekonstruiert.
Längen-Generalisierung: Im Gegensatz zu SGD-trainierten Transformern, Fine-tuned Modellen oder In-Context Learning (ICL) Baselines, die oft Trainingsverteilungen memorieren und bei längeren Eingabesequenzen versagen, synthetisiert LLM-PV häufig dimensionsinvariante Programme, die perfekt auf deutlich längere Eingabelängen als den Trainingssatz generalisieren.
Auditierbarkeit: Die Methode erzeugt ausführbaren, menschenlesbaren Code und einen vollständigen Reasoning-Trace (die Sequenz der vorgeschlagenen Programme und deren Validierungsfehler), was eine direkte Fehlersuche und mechanistische Validierung des Lernprozesses ermöglicht.

Ergebnisse

Die Autoren evaluierten LLM-PV gegen eine breite Palette von Baselines, einschließlich klassischem ML (XGBoost, SVM, Genetische Algorithmen), SGD-trainierten Modellen (von Grund auf und feinjustiert) sowie In-Context Learning (ICL) mit großen Instruction-tuned Modellen.

Algorithmische Aufgaben: Bei Aufgaben wie 10-Parity, Cellular Automata Parity und Primzahltests zeigten Standard-Baselines (einschließlich 30B+ Parameter ICL-Modelle) bei Testlängen ( $n=100$ ) eine Leistung nahe der Zufallsschwelle (50 % Genauigkeit), selbst wenn sie auf 200 Beispielen trainiert wurden. Im Gegensatz dazu erreichte LLM-PV auf diesen Aufgaben mit denselben 200 Beispielen eine Genauigkeit von 100 %.
Generalisierung: Wenn auf kurzen Sequenzen ( $n=10$ ) trainiert und auf langen Sequenzen ( $n=100$ ) getestet wurde, brachen SGD- und Fine-tuning-Baselines auf Zufallsgenauigkeit zusammen. LLM-PV behielt eine hohe Genauigkeit bei und synthetisierte erfolgreich Regeln, die invariant gegenüber der Eingabelänge sind.
Daten-Skalierung: Die Erhöhung der Trainingsmenge für SGD-basierte Modelle (bis zu 100k Beispiele) löste das Generalisierungsversagen bei Paritäts- und Cellular-Automata-Aufgaben nicht auf, was die SQ-harte Natur dieser Probleme für gradientenbasierte Lerner bestätigt.
Tool-Nutzung: Das Paper stellt fest, dass Tool-augmentiertes ICL (bei dem das Modell Code ausführen kann) die Leistung gegenüber direktem Prompting verbessert, aber dennoch nicht zuverlässig algorithmische Regeln rekonstruiert. Der Erfolg von LLM-PV wird dem spezifischen Suchziel (Vorschlagen von Programmen und Selektion durch Validierungsfehler) zugeschrieben und nicht allein dem Zugriff auf Tools.
Tabellarische Daten: Auf Standard-Tabellen-Benchmarks performte LLM-PV vergleichbar mit starken tabellarischen Lernern, was darauf hindeutet, dass der Ansatz nicht auf synthetische Sequenzaufgaben beschränkt ist.

Bedeutung und Ansprüche

Das Paper behauptet, dass vortrainierte LLM-Priors als effektive Such-Biases für ERM dienen können und erfolgreich die Lücke zwischen statistischer und rechnerischer Effizienz beim Lernen von Programmen schließen.

Die Kernbedeutung liegt in der Trennung der Rollen: Das LLM wird nur verwendet, um Hypothesen vorzuschlagen, während das Lernziel durch ausführbare Verifizierung und gehaltenen Fehler fundiert bleibt. Dieser Ansatz:

Vermeidet die „Black Box“-Natur gradientenbasierter Prädiktoren, indem er expliziten, verifizierbaren Code ausgibt.
Überwindet die Stichprobenineffizienz von gradientenbasierten Methoden bei strukturierten, diskreten Aufgaben, für die eine kurze Beschreibung existiert.
Bietet einen Mechanismus für Längen-Generalisierung, an dem Standard-Deep-Learning-Methoden bei algorithmischen Aufgaben scheitern.

Die Autoren sind zurückhaltend in der Reichweite ihrer Aussagen und räumen ein, dass die Methode von der Fähigkeit des LLM abhängt, eine ausreichende Masse auf korrekte Programme zu legen, und dass der Ansatz derzeit auf strukturierte Low-Data-Regime zugeschnitten ist und keinen allgemeinen Ersatz für überwachtes Deep Learning auf unstrukturierten Daten darstellt. Der Erfolg hängt davon ab, dass der „Proposer“ fähig und der „Verification“-Schritt robust ist.