Technische Samenvatting: REACOMP

Probleemstelling

Grote Taalmodellen (LLM's) hebben hun bekwaamheid aangetoond in taken voor programmasynthese, met name binnen het paradigma van Programmeren door Voorbeelden (PBE). Ze lijden echter aan aanzienlijke inefficiënties en onbetrouwbaarheid bij moeilijke instanties die grote combinatorische zoekopdrachten vereisen. Analyse toont aan dat moeilijkere instanties onevenredig hoog tokenverbruik en meerdere pogingen veroorzaken als gevolg van falen in compositieve generalisatie en inefficiënte zoekstrategieën (zoals lussen en redundante verkenning). Hoewel bestaande benaderingen proberen LLM's aan te vullen met geleerde bibliotheken of hulpmiddelen, vertrouwen deze methoden vaak op iteratief redeneren en tooloproepen tijdens de inferentie, blijven ze gevoelig voor rekenbudgetten en slagen ze er niet in om geleerde structuren consistent over instanties heen te hergebruiken. Bijgevolg voeren LLM's grotendeels ongestructureerde zoekopdrachten uit over de oplossingsruimte, wat leidt tot verspilde berekening naarmate de oplossingslengte toeneemt.

Methodologie: REACOMP

De auteurs stellen REACOMP voor, een raamwerk dat redeneringssporen van LLM's compileert tot herbruikbare symbolische oplossers in plaats van de redenering tijdens de inferentie direct te verbeteren. De aanpak bestaat uit twee distincte fasen:

1. Offline Oplosser-Inductie

Dit is een eenmalige procedure waarbij een coderingsagent terugkerende strategieën en faalmodi uit redeneringssporen van LLM's distilleert tot een zelfstandige symbolische programmasynthesizer die werkt binnen een beperkte domeinspecifieke taal (DSL).

• Trace-dataset: Een dataset van redeneringssporen wordt samengesteld uit een LLM (bijv. gpt-oss-120b) die een kleine subset van benchmarktaken oplost. Deze sporen omvatten tussenstappen, kandidaatprogramma's en uitkomsten, gebalanceerd over moeilijkheidsgraad en succes/mislukking.
• Inductie van Coderingsagent: Een coderingsagent (bijv. Claude Code of Qwen + OpenHands) werkt binnen een afgesloten omgeving die de trace-dataset en een alleen-lezen verifieerder bevat. De agent bewerkt iteratief een werkruimte om een implementatie van een oplosser te construeren (bijv. SOLVER.py).
• Proces: De agent stelt codebewerkingen voor, voert ze uit en verfijnt de oplosser op basis van prestaties over de trace-dataset. De agent observeert alleen de input-outputvoorbeelden die beschikbaar zijn tijdens de testfase, zodat de geïnduceerde oplosser een zelfstandig systeem is dat geen LLM-oproepen vereist tijdens de inferentie.
• Output: Een zelfstandige Python-oplosser en een algoritmebeschrijvingsbestand.

2. Efficiënte Hybride Inferentie

Tijdens de testfase hanteert het systeem een tweestapsstrategie om efficiëntie en nauwkeurigheid in evenwicht te brengen:

1. Symbolische Eerste Pass: De geïnduceerde symbolische oplosser ($S_\phi$) stelt een reeks kandidaten voor een gegeven taak $D$ voor. Als een kandidaat een perfecte beloning bereikt ($R=1$), wordt deze onmiddellijk teruggegeven tegen nul kosten voor LLM-inferentie.
2. LLM Fallback: Als de symbolische oplosser geen perfecte oplossing vindt, grijpt het systeem terug op standaard LLM-zoekprocedures (Best-of-K-sampling of Direct Feedback iteratieve verfijning) om de resterende "moeilijke" gevallen op te lossen.

Deze structuur amortiseert de kleine eenmalige constructiekost van de oplosser over vele uitvoeringen zonder tokens, waarbij dure LLM-inferentie alleen wordt gereserveerd voor residugevallen.

Belangrijkste Bijdragen

1. Methode voor Inductie: Een nieuwe methode voor het induceren van herbruikbare symbolische oplossers uit redeneringssporen van LLM's met behulp van coderingsagenten, waardoor ongestructureerde zoeksporen worden omgezet in gestructureerde, zelfstandige synthesizers.
2. Sterke Zelfstandige Prestaties: Bewijs dat geïnduceerde oplossers fungeren als krachtige zelfstandige systemen, die LLM-schaalbaarheid tijdens de testfase op moeilijke instanties (bijv. PBEBench-Hard) overtreffen met nul kosten voor LLM-inferentie per taak.
3. Pareto-dominante Hybride Pijplijn: Een neuro-symbolische hybride pijplijn die het tokenverbruik aanzienlijk reduceert (tot 78%) terwijl state-of-the-art resultaten worden behaald, en die effectief benaderingen domineert die coderingsagenten direct toepassen op elke taak.
4. Zero-Shot Generalisatie: Aantonen dat de meeste geïnduceerde oplossers zero-shot generaliseren naar real-world distributies, specifiek in een case study uit de historische linguïstiek die betrekking heeft op voorwaartse reconstructie van klankveranderingen.

Experimentele Resultaten

De auteurs evalueerden REACOMP op PBEBench (stringtransformatie) en SLR-Bench (inductieve logische programmering).

• PBEBench-Lite: Ensembles van symbolische oplossers bereikten 91,3% nauwkeurigheid, wat gelijkstaat aan of beter is dan LLM-baselines. Hybride inferentie (Symbolisch + LLM-fallback) reduceerde het tokenverbruik met 36% terwijl de pieknauwkeurigheid (93,9%) behouden bleef.
• PBEBench-Hard: Bij cascade-synthese met lange horizon bereikte LLM-schaalbaarheid tijdens de testfase (Best-of-K) 68,4% nauwkeurigheid. Geïnduceerde symbolische oplossers presteerden hier aanzienlijk beter op, waarbij het ensemble "All Symbolic" 84,7% nauwkeurigheid bereikte (een winst van +16,3 procentpunten) tegen nul kosten voor LLM-inferentie. Hybride inferentie verbeterde dit verder tot 85,8% terwijl het tokenverbruik met 78% werd gereduceerd ten opzichte van LLM-only baselines.
• SLR-Bench: Op de moeilijkste tier bereikte de CC-symbolische oplosser 46,8% nauwkeurigheid, wat gelijkstaat aan frontiermodellen (o3, GPT-5) tegen nul inferentiekosten. De hybride aanpak (DF + CC) tilde de nauwkeurigheid op de moeilijke tier naar 58,0%, waarmee alle eerder gerapporteerde baselines werden overtroffen. De beste hybride (DF + CC + QO) bereikte 86,7% algehele nauwkeurigheid tegen een fractie van de kosten van frontiermodellen.
• Efficiëntie: Symbolische oplossers zijn zeer efficiënt en voltooien inferentie voor meer dan 1.000 taken in minder dan 5 minuten (pure Python), vergeleken met ongeveer 2 dagen voor LLM-gebaseerde methoden.
• Real-world Transfer: In een voorwaartse reconstructietask voor historische linguïstiek (voorspellen van klankveranderingen) bereikten geïnduceerde oplossers 80,1% nauwkeurigheid onder ensembling, waardoor plausibele linguïstische regels werden hersteld zonder hertraining.

Betekenis en Claims

Het artikel beweert dat REACOMP een schaalbare route demonstreert naar domein-generale oplosser-inductie. Door redeneringssporen te compileren tot herbruikbare symbolische structuren, adresseert de aanpak het fundamentele misverstand tussen onafhankelijke LLM-sampling en compositieve taken met lange horizon. De auteurs betogen dat:

• Efficiëntie onder Saturatie: In regimes waar de LLM-nauwkeurigheid dicht bij saturatie ligt, biedt oplosser-inductie primaire voordelen in efficiëntie in plaats van nauwkeurigheid.
• Complementariteit bij Moeilijke Taken: Bij moeilijke taken met lange horizon excelleren symbolische oplossers waar LLM's falen (vanwege gestructureerde zoekopdrachten), terwijl LLM's de resterende taken overnemen, waardoor een complementair hybride systeem ontstaat.
• Amortisatie: De aanpak amortiseert een kleine eenmalige constructiekost over vele uitvoeringen zonder tokens, waardoor het aanzienlijk Pareto-efficiënter is dan het toepassen van coderingsagenten per instantie.
• Generalisatie: Het vermogen van oplossers om zero-shot over te dragen naar ongezette distributies (bijv. echte linguïstische data) suggereert dat de geïnduceerde algoritmen generaliseerbare structurele inzichten vangen in plaats van louter memorisatie.

De auteurs merken beperkingen op, waaronder de gevoeligheid van de oplosserkwaliteit voor de bekwaamheid van de coderingsagent en de specifieke aard van de gebruikte DSL's. Ze merken ook op dat hoewel oplossers plausibele regels herstellen, ze soms oplossingen die de verifieerder bevredigen verkiezen boven compacte, generaliseerbare structuren, wat wijst op de noodzaak van toekomstig werk op het gebied van uitlijning van beloningsfuncties en zoekstrategieën voor oplosser-inductie.