🤖 machine learning

LLM Priors for ERM over Programs

Dit artikel introduceert \textsc{LLM-PV}, een propose-and-verify-framework dat gebruikmaakt van vooraf getrainde LLM-priors om efficiënt empirische risicominimalisatie uit te voeren over discrete programma-klassen zonder uitputtende enumeratie of gradiëntupdates, wat robuuste generalisatie mogelijk maakt op algoritmische taken waar traditionele methoden falen.

Oorspronkelijke auteurs: Shivam Singhal, Priyadarsi Mishra, Eran Malach, Tomer Galanti

Gepubliceerd 2026-07-03

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Shivam Singhal, Priyadarsi Mishra, Eran Malach, Tomer Galanti

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Het Grote Probleem: Een Naald in een Hooiberg Zoeken

Stel je voor dat je een computer probeert te leren wat een geheime regel is. De regel is simpel, zoals: "Als het getal deelbaar is door 3, zeg dan 'Ja'; anders zeg 'Nee'." Maar de computer kent de regel niet; hij ziet alleen een paar voorbeelden van getallen en de bijbehorende antwoorden.

In de wereld van de informatica zijn er twee belangrijke manieren om deze regel te proberen te vinden:

De "Brute Force" Detective: Deze methode probeert elke mogelijke regel in het universum één voor één op te schrijven en te controleren of deze bij de voorbeelden past.
- Het Probleem: Als de regel zelfs maar een klein beetje complex is, is het aantal mogelijke regels zo enorm groot (zoals het aantal zandkorrels op alle stranden van de aarde samen) dat deze methode langer zou duren dan het huidige tijdperk van het universum. Het is te traag.
De "Gradient Descent" Student: Dit is hoe moderne AI (zoals de chatbots die je gebruikt) meestal leert. Het begint met een gok en past langzaam zijn interne knoppen aan om beter te worden, zoals een student die voor een toets studeert door kleine fouten te maken en deze te correllen.
- Het Probleem: Voor bepaalde soorten logische regels (zoals het controleren of een getal een priemgetal is of het tellen van specifieke patronen) loopt deze "aanpassingsmethode" vast. De student kan de oefentoets perfect uit het hoofd leren, maar faalt volledig wanneer hij een nieuwe, iets andere vraag krijgt. Het is alsof een student de antwoorden heeft uit het hoofd geleerd, maar de wiskunde niet echt heeft begrepen.

De Nieuwe Oplossing: LLM-PV (De Slimme Bibliothecaris)

De auteurs stellen een derde manier voor genaamd LLM-PV. Zie dit als het inhuren van een Slimme Bibliothecaris om je te helpen de regel te vinden.

Zo werkt het proces, stap voor stap:

Het Voorstel (De Gok van de Bibliothecaris): In plaats van elk boek in de bibliotheek te controleren (Brute Force) of te proberen de hele bibliotheek vanaf nul te herschrijven (Gradient Descent), vraag je de Slimme Bibliothecaris (een vooraf getraind Large Language Model) om een paar suggesties.
- De Magie: De Bibliothecaris heeft miljoenen boeken en stukjes code gelezen. Wanneer je de voorbeelden aan hem laat zien, gokt hij niet willekeurig. Hij gebruikt zijn "intuïtie" (voorkennis) om een paar aannemelijke regels voor te stellen die zouden kunnen werken. Hij verkleint de zoektocht van "alle mogelijke regels" naar "een handvol waarschijnlijke kandidaten".
De Verificatie (De Proefrit): De Bibliothecaris schrijft deze regels op als echte computercode. Je neemt deze codefragmenten vervolgens en voert ze uit tegen je voorbeelden om te zien welke daadwerkelijk werkt.
- Cruciaal Punt: De Bibliothecaris mag zijn mening niet veranderen op basis van de testresultaten. Hij doet alleen de suggesties. De selectie van de winnaar gebeurt strikt door de code te controleren tegen de data.
De Selectie (De Winnaar): Je kiest het codefragment dat de meeste antwoorden goed heeft.

Waarom dit een Groot Ding is

Het paper laat zien dat deze "Slimme Bibliothecaris"-aanpak ongelooflijk efficiënt is.

Het is Snel: Het hoeft niet miljarden regels te controleren. Het controleert slechts een handvol slimme gokken.
Het is Nauwkeurig: In tegen tegenstelling tot de "aanpassende" AI-methoden die vaak falen bij logische puzzels, vindt deze methode de exacte wiskundige regel (zoals de Miller-Rabin primality test voor het controleren van priemgetallen).
Het Generaliseert: Dit is het meest indrukwekkende deel. Als je het systeem leert met korte getallen (bijv. 10 cijfers), leert het de regel, niet alleen de getallen. Dus wanneer je het vraagt om een 100-cijferig getal te controleren, werkt het nog steeds perfect. De "aanpassende" AI faalt hier meestal en raakt in de war door de langere getallen.

Een Analogie uit de Beroepspraktijk: Leren Bakken

Stel je voor dat je het geheime recept voor een cake wilt leren.

Brute Force: Je probeert een cake te bakken met elke mogelijke combinatie van ingrediënten (zout, suiker, zand, stenen, etc.) totdat er één goed smaakt. Dit duurt eeuwig.
Gradient Descent (Standaard AI): Je bakt een cake, proeft hem en zegt: "Meer suiker nodig." Je bakt er weer een: "Minder bloem nodig." Je blijft dit doen. Uiteindelijk maak je misschien een cake die precies smaakt als de specifieke cake die je probeerde na te maken, maar als je de oven temperatuur verandert of een ander merk bloem gebruikt, valt je cake uit elkaar omdat je alleen die ene specifieke batch hebt nagebootst, en niet het principe van het bakken hebt geleerd.
LLM-PV: Je vraagt een Meesterkok (de LLM) die miljoenen recepten heeft gezien. Je laat hem een paar aanwijzingen over de cake zien. De Chef zegt: "Ik wed dat het een chocoladecake is met een specifieke kruidenmix." Hij schrijft drie specifieke recepten op. Jij bakt die drie. Eén daarvan is perfect. Je hoefde niet een miljoen cakes te bakken en je hoefde het recept niet eindeloos aan te passen. Je kreeg het werkelijke recept dat werkt voor elke oven.

De Kern van het Verhaal

Het paper betoogt dat we AI niet alleen moeten gebruiken om antwoorden direct te voorspellen. In plaats daarvan moeten we AI gebruiken als een zoekinstrument om potentiële oplossingen (programma's) te genereren, en vervolgens strikte tests gebruiken om de beste te kiezen. Dit combineert het "gezond verstand" van een groot taalmodel met de betrouwbaarheid van een computerprogramma, waardoor we complexe regels kunnen leren van zeer weinig voorbeelden.

Technische Samenvatting: LLM Priors voor ERM over Programma's

Probleemstelling

Het artikel behandelt de fundamentele spanning tussen steekproefefficiëntie (sample efficiency) en computationele efficiëntie bij het leren van korte, discrete programcabeschrijvingen (bijv. "Python-code") uit gelabelde data.

Klassieke leertheorie (PAC-leren) suggereert dat als een doelunctie een korte programcabeschrijving van lengte $L$ over een alfabet $\Sigma$ toelaat, deze geleerd kan worden uit $\tilde{O}(L \log |\Sigma|)$ voorbeelden via Empirical Risk Minimization (ERM) over de klasse van programma's. Echter, het implementeren van ERM vereist een uitputtende enumeratie van kandidaatprogramma's, wat schaalt als $\Theta(|\Sigma|^L)$ , wat computationeel onhaalbaar is zelfs voor een matige $L$ .

Daartegenover staan moderne deep learning-benaderingen die gebruikmaken van Stochastic Gradient Descent (SGD) op hoog-capacitieve neurale netwerken, die de expliciete enumeratie vermijden en computationeel efficiënt zijn. Toch wijzen theoretische resultaten in het Statistical Query (SQ) kader erop dat gradiëntgebaseerde methoden moeite hebben met gestructureerde, "SQ-harde" families (zoals pariteitsfuncties en cryptografische primitieven). Deze methoden vereisen vaak exponentieel veel steekproeven om te slagen, omdat de gradiënt-interface slecht afgestemd is op de discrete structuur van de doelregel, wat leidt tot falen in het generaliseren buiten de trainingssequentielengtes.

De centrale vraag is: Kunnen we de steekproefefficiëntie van ERM over korte programma's terugwinnen zonder de volledige kosten van uitputtende enumeratie te betalen?

Methodologie: LLM-PV

De auteurs stellen LLM-PV (LLM Propose-and-Verify) voor, een leeralgoritme dat een voorgetraind Large Language Model (LLM) niet behandelt als een voorspeller, maar als een zoek-prior voor ERM.

Het Algoritme

LLM-PV ontkoppelt de rollen van voorstel (proposal) en selectie:

Voorstel (De Prior): Een voorgetraind LLM wordt geprompt met een trainingsset $S_{tr}$ om een datarijke distributie over kandidaatprogramma's te induceren. Het LLM genereert een klein aantal kandidaatprogramma's (of edits) die verondersteld worden de data te verklaren.
Verificatie (De ERM-stap): Elk kandidaatprogramma wordt gecompileerd en uitgevoerd op een uit de training gehouden validatieset $S_{val}$ . Programma's die niet compileren, niet stoppen, of ongeldige outputs produceren, worden weggegooid.
Selectie: Het algoritme selecteert het programma met de laagste validatiefout. Cruciaal is dat er geen gradiëntupdates worden uitgevoerd op het LLM, en dat er geen validatiefeedback wordt gebruikt om de steekproefverdeling van het LLM tijdens de zoektocht aan te passen. Het LLM fungeert uitsluitend als een mechanisme voor inductieve bias.

Theoretisch Kader

Het artikel formaliseert de prestaties van LLM-PV met een "propose-and-verify" garantie. Als de voorstelverdeling van het LLM een niet-verwaarloosbare massa $p_\epsilon(S_{tr})$ plaatst op programma's met een populatiefout $\le \epsilon$ , dan schaalt het aantal pogingen $k$ die nodig zijn om een goede hypothese te vinden als $O(\log(1/\delta) / p_\epsilon(S_{tr}))$ . Dit vervangt de exponentiële zoekruimte $|\Sigma|^L$ door een effectieve zoekgrootte van $1/p_\epsilon(S_{tr})$ .

De auteurs bieden ook theoretische ondergrenzen aan die aantonen dat voor geplante $k$ -pariteitsproblemen, own-precision mini-batch coördinaat SGD $\Omega(\sqrt{N}/2^b)$ nieuwe voorbeelden vereist (waarbij $N$ het aantal mogelijke doelwitten is), terwijl enumeratie $\Theta(|\Sigma|^L)$ tijd vereist. Dit vestigt een regime waarin zowel naïeve enumeratie als standaard gradiëntgebaseerde training falen, wat de LLM-PV-benadering motiveert.

Belangrijkste Bijdragen

Formalisering van de Compute-Sample Spanning: Het artikel isoleert een specifiek kleine-data-regime (geplante $k$ -pariteit) waar eindige-klasse ERM steekproefefficiënt maar computationeel onhandelbaar is, terwijl gradiëntgebaseerde training computationeel handzaam maar steekproefinefficiënt is vanwege SQ-hardheid.
LLM-PV Algoritme: De introductie van een heldere "propose-and-verify" pijplijn die voorgetrainde LLM's strikt gebruikt als voorstelmechanisme. Dit behoudt de controleerbaarheid en de theoretische garanties van ERM (selectie gebaseerd op de fout op de validatieset) terwijl het de capaciteit van het LLM benut om de zoektocht te concentreren op plausibele hypothesen.
Empirisch Bewijs van Regelherstel: Uitgebreide experimenten over diverse algoritmische taken (pariteitvarianten, cellulaire automata, palindromen, Dyck-2, primality testing, cellulaire automata, en SHA-256 pariteit) tonen aan dat LLM-PV vaak de exacte onderliggende regel herstelt met slechts 200 gelabelde voorbeelden.
Lengte-generalisatie: In tegen tegenover SGD-getrainde transformers, fine-tuned modellen of In-Context Learning (ICL) baselines, die vaak trainingsdistributies memoriseren en falen bij langere inputsequenties, synthetiseert LLM-PV regelmatig dimensie-invariante programma's die perfect generaliseren naar inputlengtes die de trainingsset ver overstijgen.
Controleerbaarheid: De methode produceert uitvoerbare, menselijk leesbare code en een volledig redeneerspoor (de sequentie van voorgestelde programma's en hun validatiefouten), wat directe debugging en mechanistische validatie van het leerproces mogelijk maakt.

Resultaten

De auteurs evalueerden LLM-PV tegen een breed scala aan baselines, waaronder klassieke ML (XGBoost, SVM, Genetische Algoritmen), SGD-getrainde modellen (vanaf nul en fine-tuned), en In-Context Learning (ICL) met grote instruction-tuned modellen.

Algoritmische Taken: Op taken zoals 10-Parity, Cellular Automata Parity en Primality testing presteerden standaard baselines (inclusief 30B+ parameter ICL-modellen) nabij toeval (50% nauwkeurigheid) bij testlengtes ( $n=100$ ), zelfs wanneer ze getraind waren op 200 voorbeelden. In contrast bereikte LLM-PV 100% testnauwkeurigheid op deze taken met dezelfde 200 voorbeelden.
Generalisatie: Wanneer getraind op korte sequenties ( $n=10$ ) en getest op lange sequenties ( $n=100$ ), stortten SGD en fine-tuning baselines in naar toevalsnauwkeurigheid. LLM-PV behield een hoge nauwkeurigheid door regels te synthetiseren die invariant zijn voor de inputlengte.
Data Schaling: Het vergroten van de trainingssetgrootte voor SGD-gebaseerde modellen (tot 100k voorbeelden) loste het generalisatiefalen op pariteit en cellulaire automata taken niet op, wat het SQ-harde karakter van deze problemen voor gradiëntgebaseerde leerders bevestigt.
Toolgebruik: Het artikel merkt op dat hoewel tool-augmented ICL (waarbij het model code kan draaien) de prestaties verbetert ten opzichte van directe prompting, het nog steeds faalt in het betrouwbaar herstellen van algoritmische regels. Het succes van LLM-PV wordt toegeschreven aan het specifieke zoekdoel (het voorstellen van programma's en selecteren op basis van validatiefout) in plaats van enkel toegang tot tools.
Tabulaire Data: Op standaard tabulaire benchmarks presteerde LLM-PV vergelijkbaar met sterke tabulaire leerders, wat suggereert dat de benadering niet beperkt is tot synthetische sequentietaken.

Betekenis en Claims

Het artikel claimt dat voorgetrainde LLM priors effectieve zoek-biases kunnen dienen voor ERM, waardoor de kloof tussen statistische en computationele efficiëntie bij het leren van programma's wordt verkleind.

De kernbetekenis ligt in de scheiding van rollen: het LLM wordt alleen gebruikt om hypothesen voor te stellen, terwijl het leerdoel geworteld blijft in uitvoerbare verificatie en de fout op de validatieset. Deze aanpak:

Vermijdt het "black box"-karakter van gradiëntgebaseerde voorspellers door expliciete, verifieerbare code te produceren.
Overkomt de steekproefinefficiëntie van gradiëntgebaseerde methoden op gestructureerde, discrete taken waarbij de doelfunctie een korte beschrijving toelaat.
Biedt een mechanisme voor lengte-generalisatie dat standaard deep learning methoden niet bereiken op algoritmische taken.

De auteurs zijn bescheiden over de reikwijdte en erkennen dat de methode afhankelijk is van het vermogen van het LLM om voldoende massa op correcte programma's te plaatsen en dat de aanpak momenteel is afgestemd op gestructureerde, low-data regimes in plaats van te dienen als een algemene vervanging voor supervised deep learning op ongestructureerde data. Het succes hangt af van de bekwaamheid van de "proposer" en de robuustheid van de "verifier".