💬 NLP

Probabilistic Programs of Thought

Dit paper introduceert 'Probabilistic Programs of Thought', een testtijd-framework dat de kansverdeling van een LLM gebruikt om exponentieel veel deterministische programma's compact te vertegenwoordigen, waardoor nieuwe programma's kunnen worden bemonsterd zonder extra GPU-berekeningen en met verbeterde prestaties op taken zoals codegeneratie en wiskundig redeneren.

Oorspronkelijke auteurs: Poorva Garg, Renato Lui Geh, Daniel Israel, Todd Millstein, Kyle Richardson, Guy Van den Broeck

Gepubliceerd 2026-04-21

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Poorva Garg, Renato Lui Geh, Daniel Israel, Todd Millstein, Kyle Richardson, Guy Van den Broeck

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

Stel je voor dat je een zeer slimme, maar soms wat slordige assistent hebt die code schrijft of wiskundige problemen oplost. We noemen deze assistent een "Groot Taalmodel" (LLM).

Het probleem is dat deze assistent soms een foutje maakt. Als je hem vraagt: "Schrijf een programma dat dit rekent," kan hij een antwoord geven dat er goed uitziet, maar een klein foutje bevat (bijvoorbeeld een verkeerd cijfer of een verkeerd rekenoperator).

Hoe werkt het nu?
Normaal gesproken, als je twijfelt of het antwoord klopt, vraag je de assistent: "Probeer het nog eens." En nog eens. En nog eens. Je vraagt hem dus 10, 20 of 50 keer om een nieuw antwoord te genereren.

Het nadeel: Elke keer dat je hem iets vraagt, moet je een enorme, dure computer (een GPU) laten werken. Dit kost veel tijd, geld en energie. Het is alsof je 50 keer een nieuwe auto moet bestellen om er één te vinden die niet lek is.

De nieuwe oplossing: "Probabilistische Programma's van Gedachte" (PPoT)
De auteurs van dit papier hebben een slimme truc bedacht. Ze zeggen: "Wacht even, we hoeven de assistent niet 50 keer te vragen. We kunnen al zijn twijfels en onzekerheden uit één antwoord halen."

Hier is hoe het werkt, met een creatieve vergelijking:

1. De "Magische Koffiemachine" (De LLM)

Stel je een koffiemachine voor die elke keer een kopje koffie zet. Soms zet hij een kopje met 100% koffie, soms met 90% koffie en 10% water, en soms met 80% koffie.

De oude manier: Als je een kopje koffie wilt dat precies 100% koffie is, bestel je 50 kopjes en proeft je ze allemaal. Je gooit er 49 weg. Dit kost veel bonen (rekenkracht).
De nieuwe manier (PPoT): De koffiemachine geeft je niet alleen het kopje koffie, maar ook een recept met de exacte percentages. "Dit kopje is 90% koffie, maar er is 10% kans dat het 95% was, en 5% kans dat het 80% was."

2. Het "Zwarte Doosje" met wisselstukken

In plaats van de machine opnieuw aan te zetten, nemen de onderzoekers het recept en maken ze er een probabilistisch programma van.
Ze kijken naar de delen van de code die de machine "onzeker" was over (bijvoorbeeld een getal of een rekenoperator). Ze vervangen die specifieke delen door magische dobbelstenen.

In plaats van vast te zetten dat het getal 20 is, zeggen ze: "Het is een dobbelsteen die kan vallen op 10, 20, 30 of 40, met bepaalde kansen."
Ze hebben nu één programma dat in feite duizenden mogelijke programma's in zich draagt, allemaal tegelijkertijd.

3. De "Snelle Simulatie"

Nu hoeven ze de dure koffiemachine (de GPU) niet meer aan te zetten. Ze nemen hun magische dobbelstenen en gooien ze gewoon op een tafel (dit gebeurt op een gewone CPU, wat heel goedkoop en snel is).

Ze gooien de dobbelstenen 50 keer.
Soms valt het getal op 20, soms op 30.
Ze draaien het programma met die nieuwe getallen.
Het resultaat: Ze hebben nu 50 verschillende oplossingen gegenereerd, maar ze hebben de dure machine maar één keer gebruikt.

Waarom is dit zo geweldig?

Kostenbesparing: Het kost bijna niets om die dobbelstenen te gooien (geen extra GPU-tijd).
Beter resultaat: Omdat ze zo veel verschillende variaties kunnen testen, vinden ze sneller de juiste oplossing. Het is alsof je in plaats van één keer te gokken, 50 keer gokt met dezelfde inzet.
Fouten oplossen: Als de assistent een fout maakt (bijvoorbeeld een verkeerd getal), zit de juiste kans vaak al in het "onzekerheidsgebied" van dat getal. Door de dobbelsteen te gooien, kunnen ze toevallig de juiste oplossing vinden zonder de assistent opnieuw te hoeven vragen.

Kort samengevat:
In plaats van een dure robot 50 keer te laten werken om 50 antwoorden te krijgen, laten we de robot één keer werken, nemen we zijn "twijfels" mee, en spelen we een snel spelletje dobbelen om die 50 antwoorden uit die twijfels te halen. Het is een slimme manier om meer uit minder te halen.

Titel: Probabilistic Programs of Thought (PPoT)

Auteurs: Poorva Garg, Renato Lui Geh, Daniel Israel, Todd Millstein, Kyle Richardson, Guy Van den Broeck (UCLA & Allen Institute for AI)

1. Het Probleem

Grote Taalmodellen (LLMs) worden steeds vaker ingezet voor taken die gestructureerde output vereisen, zoals codegeneratie, wiskundig redeneren en het uitvoeren van "Programs of Thought" (het redeneren via het genereren van code). De huidige standaardaanpak voor deze taken is een sample-execute-verify lus:

Het model wordt geprompt om code te genereren.
De gegenereerde code wordt uitgevoerd om de juistheid te verifiëren.
Als de code fout is, wordt het proces herhaald (vaak met strategieën zoals Best-of-n of beam search).

De beperking:
Elke poging om een nieuw programma te genereren vereist een volledige GPU-berekening (inference) door het LLM. Voor grote modellen wordt het genereren van een groot aantal samples ( $n$ ) om een correct antwoord te vinden, prohibitief duur in termen van rekentijd en energie. De huidige methode gooit de kansverdelingen (next-token probabilities) weg zodra een token is gesampled, waardoor het onmogelijk is om efficiënt nieuwe varianten van een reeds gegenereerd programma te creëren zonder het model opnieuw aan te roepen.

2. Methodologie: Probabilistic Programs of Thought (PPoT)

De auteurs stellen een nieuw test-tijd framework voor genaamd Probabilistic Programs of Thought (PPoT). In plaats van het LLM herhaaldelijk aan te roepen, gebruiken ze de interne kansverdeling van het model om een probabilistisch programma te bouwen dat compact duizenden deterministische programma's vertegenwoordigt.

Kernprincipes:

Van Deterministisch naar Probabilistisch:
Wanneer een LLM een programma genereert, worden de tokens die hoge entropie hebben (onzekere tokens, zoals cijfers, operatoren of variabelen) niet als vaste waarden behandeld. In plaats daarvan worden ze omgezet in stochastische variabelen ( $X_i$ ).
- De verdeling van deze variabelen wordt geparametriseerd door de oorspronkelijke next-token logits van het LLM.
- Het resultaat is een probabilistisch programma dat de onzekerheid van het LLM behoudt.
Efficiënt Inferentie:
Het gegenereerde probabilistische programma kan worden gebruikt om nieuwe, geldige uitvoeringen te "samplen" via probabilistische inferentie op de CPU. Dit vereist geen extra GPU-forward passes.
- Het systeem kan exponentieel veel nieuwe programma's genereren uit één enkele LLM-aanroep.
- Deze nieuwe samples worden getest op correctheid (via een verifier).
Compilatie en Selectie:
- Token-analyse: Het systeem identificeert welke tokens (bijv. getallen, rekenkundige operatoren) als random variables moeten worden behandeld.
- Aannames: Om de berekening tractabel te houden, maken de auteurs de aanname dat hersamplede tokens onafhankelijk zijn van de daaropvolgende tokens in de sequentie (Assumptie 1). Onder deze aanname convergeert de empirische verdeling van de samples naar de oorspronkelijke LLM-verdeling.
- Conditionering: Het systeem kan conditioneren op het niet reproduceren van het originele (foute) LLM-antwoord, waardoor de diversiteit van de samples wordt vergroot.

Werkingsflow (Algorithm 2):

Het LLM genereert één initieel programma ( $k=1$ ).
De next-token probabilities worden opgeslagen.
Een subset van tokens wordt omgezet in random variables met de bijbehorende verdelingen.
Dit probabilistische programma wordt $m$ keer gesampled (op de CPU) om nieuwe varianten te genereren.
Alle $m$ varianten worden uitgevoerd en verifieerd.

3. Belangrijkste Bijdragen

Nieuwe Decoding-techniek: Introductie van PPoT, een methode om gestructureerde output (code) efficiënter te genereren door probabilistisch programmeren toe te passen op de output van LLMs.
Theoretische Onderbouwing: Bewijs dat de aanpak distributie-technisch correct (sound) is onder bepaalde onafhankelijkheidsaannames, wat betekent dat de gegenereerde samples de onderliggende LLM-verdeling respecteren.
Empirische Validatie: Demonstratie van consistente verbeteringen in pass@k prestaties op drie benchmarks zonder extra GPU-kosten.
Rekenkundige Efficiëntie: Kwantitatief bewijs dat PPoT aanzienlijke besparingen oplevert ten opzichte van het direct sample-en-verifiëren van het LLM.

4. Resultaten

De auteurs hebben PPoT getest op Qwen2.5 modellen (0.5B, 3B, 7B parameters) over drie verschillende benchmarks:

GSM8k (Wiskundig Redeneren):
- Met slechts $m=5$ PPoT-samples per LLM-generatie steeg de nauwkeurigheid met 2% tot 7%.
- Om dezelfde prestatie te bereiken als 20 LLM-samples, volstaat het gebruik van slechts 8 LLM-samples aangevuld met PPoT-samples.
Plot2Code (Codegeneratie voor Visualisatie):
- Verbetering van 0,5% tot 6% in tekst-match scores.
- PPoT kon runtime-fouten in de originele LLM-code corrigeren door kleine aanpassingen in variabelen of parameters te maken.
CRUXEval (Gestructureerde Output/Programma Inversie):
- Verbetering van 3% tot 7% in nauwkeurigheid.
- Toont aan dat de methode werkt voor complexe gestructureerde objecten (zoals lijsten en strings), niet alleen voor code.

Efficiëntie:

De compilatie en sampling van PPoT vinden plaats op de CPU en zijn verwaarloosbaar in rekentijd vergeleken met de GPU-inference van het LLM.
De grafieken tonen aan dat de totale runtime voor $k$ LLM-samples plus $k \times m$ PPoT-samples bijna identiek is aan die van alleen $k$ LLM-samples.
Effectieve samples: 20 PPoT-samples per LLM-generatie zijn equivalent aan ongeveer 39 extra LLM-samples in termen van nauwkeurigheidswinst.

5. Betekenis en Toekomstperspectief

Dit werk opent een nieuwe richting in het onderzoek naar LLMs door probabilistische programma's te gebruiken als abstractie voor de generaties van taalmodellen.

Kostenreductie: Het biedt een manier om de "rekenkosten" van het vinden van een correct antwoord drastisch te verlagen, wat essentieel is voor de schaalbaarheid van LLM-toepassingen in de praktijk.
Uitbreidbaarheid: De auteurs zien mogelijkheden om de random variables uit te breiden van enkel cijfers en operatoren naar complexere structuren zoals controle-flow en sub-expressies.
Toepassingen: Het framework kan worden gebruikt voor conditionering, het berekenen van verwachtingen, en het ondersteunen van andere probabilistische queries binnen taalmodellen.

Samenvattend transformeert PPoT de LLM van een "zwarte doos" die slechts één kansrijke uitkomst per call levert, naar een probabilistische engine die duizenden varianten van een oplossing kan verkennen met de kosten van slechts één call.