💬 NLP

ReaComp: Compiling LLM Reasoning into Symbolic Solvers for Efficient Program Synthesis

Das Papier stellt ReaComp vor, ein Framework, das LLM-Reasoning-Spuren in wiederverwendbare, token-freie symbolische Löser kompiliert, die auf Programmiersynthese-Benchmarks State-of-the-Art-Genauigkeit erreichen, den Token-Verbrauch in Kombination mit LLMs erheblich reduzieren und erfolgreich auf reale linguistische Aufgaben übertragen werden.

Ursprüngliche Autoren: Atharva Naik, Yash Mathur, Prakam, Carolyn Rose, David Mortensen

Veröffentlicht 2026-05-08

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Atharva Naik, Yash Mathur, Prakam, Carolyn Rose, David Mortensen

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: Der „Überdenker"

Stellen Sie sich vor, Sie haben einen sehr klugen, kreativen Assistenten (eine KI), der hervorragend Rätsel lösen kann. Doch wenn das Rätsel wirklich schwierig oder lang wird, gerät dieser Assistent in Panik. Er versucht, es zu lösen, indem er rät, prüft, erneut rät und riesige, unordentliche Notizen schreibt. Am Ende erhält er zwar die richtige Antwort, verbraucht dafür aber eine massive Menge an Papier (Rechenleistung) und Zeit. Manchmal gerät er in eine Schleife und wiederholt dieselben Fehler immer und immer wieder.

Die Forscher stellten fest, dass diese KI-Assistenten zwar leistungsstark sind, aber bei komplexen, mehrstufigen logischen Problemen (wie dem Umformen von Textzeichenfolgen oder dem Finden von Regeln in Daten) ineffizient und teuer sind.

Die Lösung: Das „Rezeptbuch" (REACOMP)

Anstatt den klugen Assistenten zu bitten, jedes neue Rätsel von Grund auf neu zu lösen, entwickelten die Forscher eine neue Methode namens REACOMP.

Stellen Sie es sich so vor:

Die Beobachtungsphase: Zuerst beobachten sie, wie der kluge Assistent eine kleine Reihe von Übungsrätseln löst. Sie schauen zu, wie der Assistent denkt, wo er stecken bleibt und welche Strategien er anwendet, um erfolgreich zu sein.
Die Kompilierungsphase: Sie beauftragen einen „Codierungs-Agenten" (einen spezialisierten KI-Programmierer), diese Übungssitzungen zu beobachten. Dieser Programmierer kopiert nicht nur die Antworten; er schreibt ein dauerhaftes Regelbuch (einen symbolischen Löser) basierend auf den Mustern, die er gesehen hat. Dieses Regelbuch ist eine Reihe strikter, logischer Anweisungen, die diese Art von Rätsel sofort lösen kann.
Die Ausführungsphase: Wenn nun ein neues Rätsel kommt, bitten sie den klugen Assistenten nicht, nachzudenken. Sie geben das Rätsel einfach dem Regelbuch. Das Regelbuch löst es sofort, ohne dass der kluge Assistent auch nur eine Sekunde „nachdenken" muss.

Falls das Regelbuch bei einem wirklich seltsamen Rätsel stecken bleibt, rufen sie dann (und nur dann) den klugen Assistenten zur Hilfe.

Die Ergebnisse: Geschwindigkeit, Einsparungen und Intelligenz

Das Papier testete dies an zwei Arten schwieriger logischer Rätsel (genannt PBEBench und SLR-Bench). Hier ist, was passierte:

Der „Kostenlose" Sieg: Die Regelbücher (symbolische Löser) waren so gut, dass sie die schwierigsten Rätsel 84,7 % bis 91,3 % der Zeit lösten, ohne den klugen Assistenten überhaupt um Hilfe zu bitten. Das bedeutet, dass die Kosten für die Lösung dieser Probleme für die „Gehirn"-Nutzung der KI auf null sanken.
Die Riesen schlagen: Bei den schwierigsten Rätseln schnitten die Regelbücher tatsächlich besser ab als der kluge Assistent, der sein Bestes gab (selbst wenn dem Assistenten erlaubt wurde, viele Versuche zu unternehmen). Die Regelbücher waren um 16 % genauer als die besten „Raten-und-Prüfen"-Methoden, die allein von der KI verwendet wurden.
Die Hybrid-Superkraft: Als sie das Regelbuch mit dem klugen Assistenten kombinierten (zuerst das Regelbuch, und den Assistenten nur als Backup), bekamen sie das Beste aus beiden Welten. Sie erreichten die höchste je auf diesen Tests verzeichnete Genauigkeit und verwendeten dabei 78 % weniger Rechenleistung (Tokens) als die KI allein.
Realitäts-Test: Sie probierten dies sogar an einem realen Sprachrätsel aus, wie sich Laute in alten Sprachen verändern. Die Regelbücher, die nie speziell über dieses Thema unterrichtet worden waren, lösten es mit 80 % Genauigkeit, indem sie einfach die Logik nutzten, die sie aus den Übungsrätseln gelernt hatten.

Die Kernaussage

Das Papier argumentiert, dass wir die KI nicht einfach bei jedem neuen Problem dazu anhalten sollten, „stärker nachzudenken". Stattdessen sollten wir die KI einmalig lernen lassen, wie man lernt, dieses Lernen in ein dauerhaftes, wiederverwendbares Werkzeug (einen Löser) verwandeln und dann dieses Werkzeug für alles verwenden.

Es ist der Unterschied zwischen der Einstellung eines Genies, das jedes Mal ein mathematisches Problem von Grund auf neu löst (teuer und langsam), und der Einstellung eines Genies, das einmal eine Taschenrechner-App schreibt, und dann diese App für immer nutzt (günstig, schnell und zuverlässig).

Zusammenfassung der Behauptungen

Effizienz: Sie können KI-Schlussfolgerungsspuren in wiederverwendbare Werkzeuge verwandeln, die Probleme lösen, ohne dass die KI erneut benötigt wird.
Leistung: Diese Werkzeuge sind bei schwierigen, langen Aufgaben oft besser als die KI selbst.
Kosten: Diese Methode reduziert drastisch das Geld und die Energie, die zum Betreiben von KI-Systemen benötigt werden.
Verallgemeinerung: Diese Werkzeuge können auf neue, reale Aufgaben (wie Linguistik) angewendet werden, ohne dass sie neu trainiert werden müssen.

Technische Zusammenfassung: REACOMP

Problemstellung

Large Language Models (LLMs) haben ihre Fähigkeit zur Programmsynthese, insbesondere im Paradigma des „Programming by Example" (PBE), unter Beweis gestellt. Allerdings leiden sie bei schwierigen Instanzen, die umfangreiche kombinatorische Suchen erfordern, unter erheblichen Ineffizienzen und Unzuverlässigkeit. Analysen zeigen, dass schwierigere Instanzen unverhältnismäßig hohen Token-Verbrauch und mehrere Versuche auslösen, bedingt durch Misserfolge bei der kompositionellen Generalisierung und ineffiziente Suchstrategien (z. B. Schleifen, redundante Exploration). Während bestehende Ansätze versuchen, LLMs durch gelernte Bibliotheken oder Werkzeuge zu erweitern, verlassen sich diese Methoden oft auf iteratives Schlussfolgern und Werkzeugaufrufe zur Inferenzzeit, bleiben empfindlich gegenüber Rechenbudgets und scheitern daran, gelernte Strukturen konsistent über verschiedene Instanzen hinweg wiederzuverwenden. Folglich führen LLMs weiterhin weitgehend unstrukturierte Suchen im Lösungsraum durch, was zu verschwendeter Rechenleistung führt, sobald die Lösungslänge zunimmt.

Methodik: REACOMP

Die Autoren schlagen REACOMP vor, ein Framework, das die Schlussfolgerungsspuren von LLMs in wiederverwendbare symbolische Löser kompiliert, anstatt die Inferenzzeit-Schlussfolgerung direkt zu verbessern. Der Ansatz besteht aus zwei distincten Phasen:

1. Offline-Löser-Induktion

Dies ist ein einmaliges Verfahren, bei dem ein Coding-Agent wiederkehrende Strategien und Fehlermodi aus LLM-Schlussfolgerungsspuren in einen eigenständigen symbolischen Programmsynthesizer destilliert, der über eine eingeschränkte domänenspezifische Sprache (DSL) operiert.

Trace-Datensatz: Ein Datensatz von Schlussfolgerungsspuren wird aus einem LLM (z. B. gpt-oss-120b) erstellt, das einen kleinen Teil der Benchmark-Aufgaben löst. Diese Spuren umfassen Zwischenschritte, Kandidatenprogramme und Ergebnisse, die über Schwierigkeitsgrade und Erfolg/Misserfolg hinweg ausgewogen sind.
Coding-Agent-Induktion: Ein Coding-Agent (z. B. Claude Code oder Qwen + OpenHands) arbeitet in einer sandgeboxten Umgebung, die den Trace-Datensatz und einen schreibgeschützten Verifizierer enthält. Der Agent bearbeitet iterativ einen Arbeitsbereich, um eine Löser-Implementierung (z. B. SOLVER.py) zu konstruieren.
Prozess: Der Agent schlägt Code-Änderungen vor, führt sie aus und verfeinert den Löser basierend auf der Leistung über den Trace-Datensatz. Der Agent beobachtet nur die Eingabe-Ausgabe-Beispiele, die zur Testzeit verfügbar sind, wodurch sichergestellt wird, dass der induzierte Löser ein eigenständiges System ist, das während der Inferenz keine LLM-Aufrufe benötigt.
Ausgabe: Ein eigenständiger Python-Löser und eine Algorithmus-Beschreibungsdatei.

2. Effiziente hybride Inferenz

Zur Testzeit setzt das System eine Zwei-Phasen-Strategie ein, um Effizienz und Genauigkeit in Einklang zu bringen:

Symbolischer erster Durchlauf: Der induzierte symbolische Löser ( $S_\phi$ ) schlägt für eine gegebene Aufgabe $D$ eine Reihe von Kandidaten vor. Wenn ein Kandidat eine perfekte Belohnung ( $R=1$ ) erzielt, wird er sofort ohne Kosten für LLM-Inferenz zurückgegeben.
LLM-Fallback: Falls der symbolische Löser keine perfekte Lösung findet, weicht das System auf Standard-LLM-Suchverfahren aus (Best-of-K-Sampling oder iterative Verfeinerung durch direktes Feedback), um die verbleibenden „schwierigen" Fälle zu lösen.

Diese Struktur amortisiert die geringen einmaligen Konstruktionskosten des Löser über viele Token-freie Ausführungen und reserviert teure LLM-Inferenz nur für Restfälle.

Hauptbeiträge

Methode zur Induktion: Eine neuartige Methode zur Induktion wiederverwendbarer symbolischer Löser aus LLM-Schlussfolgerungsspuren unter Verwendung von Coding-Agenten, die unstrukturierte Suchspuren in strukturierte, eigenständige Synthesizer transformiert.
Starke Eigenleistung: Belege dafür, dass induzierte Löser als leistungsstarke eigenständige Systeme fungieren und bei schwierigen Instanzen (z. B. PBEBench-Hard) die LLM-Skalierung zur Testzeit übertreffen, bei null LLM-Inferenzkosten pro Aufgabe.
Pareto-dominante hybride Pipeline: Eine neuro-symbolische hybride Pipeline, die den Token-Verbrauch erheblich reduziert (bis zu 78 %) und gleichzeitig State-of-the-Art-Ergebnisse erzielt, wodurch sie Ansätze, die Coding-Agenten direkt auf jede Aufgabe anwenden, effektiv dominiert.
Zero-Shot-Generalisierung: Der Nachweis, dass die meisten induzierten Löser zero-shot auf reale Verteilungen generalisieren, speziell in einer Fallstudie zur historischen Linguistik, die die Vorwärtsrekonstruktion von Lautwandel beinhaltet.

Experimentelle Ergebnisse

Die Autoren bewerteten REACOMP auf PBEBench (String-Transformation) und SLR-Bench (induktive Logikprogrammierung).

PBEBench-Lite: Ensembles aus symbolischen Lösern erreichten 91,3 % Genauigkeit und entsprachen oder übertrafen LLM-Baselines. Die hybride Inferenz (Symbolisch + LLM-Fallback) reduzierte den Token-Verbrauch um 36 %, bei gleichzeitiger Beibehaltung der Spitzen-Genauigkeit (93,9 %).
PBEBench-Hard: Bei der Synthese von Kaskaden mit langem Horizont erreichte die LLM-Skalierung zur Testzeit (Best-of-K) eine Genauigkeit von 68,4 %. Induzierte symbolische Löser übertrafen dies signifikant; das Ensemble „All Symbolic" erreichte 84,7 % Genauigkeit (ein Gewinn von +16,3 Prozentpunkten) bei null LLM-Inferenzkosten. Die hybride Inferenz verbesserte dies weiter auf 85,8 %, bei gleichzeitiger Reduktion des Token-Verbrauchs um 78 % im Vergleich zu reinen LLM-Baselines.
SLR-Bench: Auf der schwierigsten Ebene erreichte der CC-symbolische Löser 46,8 % Genauigkeit und entsprach damit Frontier-Modellen (o3, GPT-5) bei null Inferenzkosten. Der hybride Ansatz (DF + CC) hob die Genauigkeit auf der schwierigen Ebene auf 58,0 % und übertraf damit alle zuvor berichteten Baselines. Der beste hybride Ansatz (DF + CC + QO) erreichte eine Gesamtgenauigkeit von 86,7 % bei einem Bruchteil der Kosten von Frontier-Modellen.
Effizienz: Symbolische Löser sind hoch effizient und führen die Inferenz für über 1.000 Aufgaben in unter 5 Minuten durch (reines Python), im Vergleich zu etwa 2 Tagen für LLM-basierte Methoden.
Transfer in die reale Welt: Bei einer Vorwärtsrekonstruktion für historische Linguistik (Vorhersage von Lautwandel) erreichten induzierte Löser unter Ensembling eine Genauigkeit von 80,1 % und stellten plausible linguistische Regeln ohne Nachtraining wieder her.

Bedeutung und Behauptungen

Die Arbeit behauptet, dass REACOMP einen skalierbaren Weg zur domänenübergreifenden Löser-Induktion aufzeigt. Durch das Kompilieren von Schlussfolgerungsspuren in wiederverwendbare symbolische Strukturen adressiert der Ansatz die fundamentale Diskrepanz zwischen unabhängiger LLM-Stichprobenziehung und Aufgaben mit langem Horizont und kompositionellem Charakter. Die Autoren argumentieren, dass:

Effizienz bei Sättigung: In Regimen, in denen die LLM-Genauigkeit nahe der Sättigung liegt, bietet die Löser-Induktion primäre Vorteile in Bezug auf Effizienz und nicht auf Genauigkeit.
Komplementarität bei schwierigen Aufgaben: Bei schwierigen Aufgaben mit langem Horizont glänzen symbolische Löser dort, wo LLMs versagen (aufgrund strukturierter Suche), während LLMs die verbleibenden Aufgaben abdecken, wodurch ein komplementäres hybrides System entsteht.
Amortisierung: Der Ansatz amortisiert die geringen einmaligen Konstruktionskosten über viele Token-freie Ausführungen und ist damit erheblich pareto-effizienter als die Anwendung von Coding-Agenten pro Instanz.
Generalisierung: Die Fähigkeit der Löser, zero-shot auf nicht gesehene Verteilungen zu transferieren (z. B. reale linguistische Daten), deutet darauf hin, dass die induzierten Algorithmen generalisierbare strukturelle Einsichten erfassen und nicht bloßes Auswendiglernen.

Die Autoren weisen auf Einschränkungen hin, darunter die Empfindlichkeit der Löserqualität gegenüber den Fähigkeiten des Coding-Agenten und die spezifische Natur der verwendeten DSLs. Sie stellen zudem fest, dass Löser zwar plausible Regeln wiederherstellen, aber manchmal verifizierer-füllende Lösungen gegenüber kompakten, generalisierbaren Strukturen bevorzugen, was auf die Notwendigkeit zukünftiger Arbeiten zur Ausrichtung der Belohnungsfunktion und zu Suchstrategien für die Löser-Induktion hindeutet.