💬 NLP

Probabilistic Programs of Thought

Diese Arbeit stellt „Probabilistic Programs of Thought" vor, ein Testzeit-Framework, das die Verteilung von Sprachmodellen in generierten Programmen nutzt, um exponentiell viele deterministische Programme kompakt darzustellen und so durch kostengünstiges probabilistisches Reasoning auf CPU-Basis die Effizienz bei Code- und Mathematikaufgaben ohne zusätzliche GPU-Kosten zu steigern.

Ursprüngliche Autoren: Poorva Garg, Renato Lui Geh, Daniel Israel, Todd Millstein, Kyle Richardson, Guy Van den Broeck

Veröffentlicht 2026-04-21

📖 3 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Poorva Garg, Renato Lui Geh, Daniel Israel, Todd Millstein, Kyle Richardson, Guy Van den Broeck

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

Stell dir vor, du hast einen sehr klugen, aber manchmal etwas vergesslichen Koch, den wir „LLM" (Large Language Model) nennen. Dieser Koch ist ein Meister darin, Rezepte (also Code) zu erfinden, um komplexe mathematische Probleme zu lösen.

Das Problem:
Wenn du dem Koch eine Aufgabe gibst, sagt er dir oft: „Ich habe das Rezept!" Aber manchmal ist das Rezept falsch. Vielleicht hat er eine Zahl vertippt oder ein Minuszeichen vergessen.
Der übliche Weg, um sicherzugehen, ist: „Probier es einfach aus!" Du lässt den Koch 10, 20 oder sogar 100 verschiedene Rezepte aufschreiben. Dann kochst du jedes davon nach, um zu sehen, welches schmeckt (funktioniert).
Das Problem dabei: Jeder einzelne Versuch kostet viel Zeit und Energie (Rechenleistung/GPU). Wenn du 20 Rezepte willst, musst du den Koch 20 Mal anrufen. Das ist teuer und langsam.

Die Lösung: „Probabilistische Gedankenprogramme" (PPoT)
Die Autoren dieses Papiers haben eine geniale Idee entwickelt, die wir uns wie einen magischen Kochbuch-Zauber vorstellen können.

Statt den Koch 20 Mal zu rufen, rufen wir ihn nur einmal.

Der erste Versuch: Der Koch schreibt ein Rezept auf.
Der Zaubertrick: Anstatt das Rezept einfach so hinzunehmen, schauen wir uns genau an, wie sicher der Koch bei jedem Wort war.
- Bei „200" war er sich 100% sicher.
- Bei der Zahl „3" war er sich aber nicht ganz sicher. Vielleicht meinte er „3", vielleicht auch „2" oder „4".
Das probabilistische Rezept: Wir nehmen das geschriebene Rezept und verwandeln die unsicheren Wörter in Wahrscheinlichkeits-Würfel.
- Statt einer festen Zahl schreiben wir: „Nimm eine Zahl, die zu 80% eine 3 ist, zu 10% eine 2 und zu 10% eine 4."
- Das ist jetzt kein festes Rezept mehr, sondern ein Rezept-Generator.

Warum ist das so toll?
Jetzt müssen wir den Koch nicht mehr anrufen! Wir nehmen dieses eine „Wahrscheinlichkeits-Rezept" und lassen einen ganz einfachen Computer (den CPU) die Würfel rollen.

Würfelwurf 1: Die 3 wird zur 2. -> Rezept A ist fertig.
Würfelwurf 2: Die 3 bleibt eine 3, aber das Pluszeichen wird zu einem Minus. -> Rezept B ist fertig.
Würfelwurf 3: Die 3 wird zur 4. -> Rezept C ist fertig.

Wir können so tausende neue Rezepte aus diesem einen einzigen Rezept-Generator zaubern, ohne den teuren Koch (die GPU) noch einmal zu stören. Das kostet fast nichts an Zeit oder Energie.

Die Analogie zum Autofahren:
Stell dir vor, du fährst mit einem Auto (dem LLM) eine Strecke.

Der alte Weg: Du fährst die Strecke 20 Mal hintereinander, um zu sehen, ob du an der richtigen Abbiegung (der richtigen Lösung) landest. Das kostet 20 Tankfüllungen (Rechenleistung).
Der neue Weg (PPoT): Du fährst die Strecke nur einmal. Aber während du fährst, markierst du alle Stellen, an denen du unsicher warst („Hier hätte ich auch links abbiegen können").
Danach stellst du das Auto ab. Ein kleiner Roboter (der Computer) nimmt deine Notizen und simuliert 100 verschiedene Fahrten, basierend auf deinen Unsicherheiten. Er berechnet, welche dieser Fahrten zum Ziel führen.
Ergebnis: Du hast 100 Fahrten simuliert, hast aber nur eine Tankfüllung verbraucht.

Was bringt das?
In Tests haben die Autoren gezeigt, dass diese Methode die Erfolgsrate drastisch erhöht. Sie konnten mit weniger Anrufen beim KI-Modell genau so gute Ergebnisse erzielen wie mit viel mehr Anrufen. Es ist wie ein „Effizienz-Booster": Wir holen mehr aus dem heraus, was die KI bereits gesagt hat, ohne extra bezahlen zu müssen.

Zusammenfassung:
Statt die KI zu zwingen, immer wieder neu zu raten, nutzen wir ihre eigene Unsicherheit als Werkzeug. Wir verwandeln einen einzigen, unsicheren Vorschlag in einen ganzen Garten voller möglicher Lösungen, die wir kostenlos „ernten" können.

Titel: Probabilistic Programs of Thought (PPoT)

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

1. Problemstellung

Große Sprachmodelle (LLMs) werden zunehmend für Aufgaben zur Code-Generierung und mathematischen Argumentation eingesetzt, bei denen strukturierte Ausgaben erforderlich sind. Der etablierte Workflow („Sample-Execute-Verify") besteht darin, das Modell mehrfach zu befragen, um mehrere Kandidatenprogramme zu generieren, diese auszuführen und zu verifizieren.

Herausforderung: Um die Erfolgsrate (z. B. pass@k) zu erhöhen, müssen viele unabhängige Stichproben (Samples) generiert werden. Da jede neue Stichprobe eine vollständige, rechenintensive GPU-Forward-Pass-Generierung durch das LLM erfordert, wird dieser Prozess bei größeren Modellen oder hohen Werten für $k$ prohibitiv teuer.
Limitierung: Herkömmliche Methoden wie „Best-of-n" oder Beam Search verschwenden die bereits vom Modell generierten Wahrscheinlichkeitsverteilungen (Logits), sobald ein Token festgelegt wurde.

2. Methodik: Probabilistic Programs of Thought (PPoT)

Die Autoren schlagen einen neuen Testzeit-Rahmen vor, der die interne Wahrscheinlichkeitsverteilung des LLMs innerhalb der generierten Programme selbst nutzt, um weitere Stichproben ohne zusätzliche GPU-Rechenzeit zu erzeugen.

Kernidee

Statt ein deterministisches Programm als endgültige Antwort zu betrachten, wird das generierte Programm in ein probabilistisches Programm umgewandelt. Dabei werden ausgewählte Token (z. B. Zahlen, Operatoren) nicht als feste Werte, sondern als Zufallsvariablen behandelt, deren Verteilungen durch die ursprünglichen Next-Token-Logits des LLMs parametrisiert sind.

Algorithmischer Ablauf (Algorithmus 2)

Initiale Generierung: Das LLM generiert ein deterministisches Programm (ein „Sample").
Token-Analyse & Kompilierung: Bestimmte Token-Positionen (z. B. Ziffern, arithmetische Operatoren) werden identifiziert und in Zufallsvariablen $X_i$ $X_{i}$ umgewandelt. Die Verteilung $P(X_i)$ $P (X_{i})$ wird direkt aus den Logits des LLMs an dieser Position abgeleitet.
- Beispiel: Wenn das LLM return 0 + 2 ausgibt, wird die 0 zu einer Zufallsvariable $X \sim \text{categorical}(P_{\text{LM}})$ , wobei die Wahrscheinlichkeiten für andere Ziffern aus dem Modell stammen.
Probabilistisches Inferenz: Aus diesem probabilistischen Programm werden $m$ $m$ neue deterministische Programme durch Resampling der Zufallsvariablen generiert.
- Dies geschieht rein auf der CPU und erfordert keine weiteren GPU-Forward-Passes.
- Um die Diversität zu erhöhen, wird oft bedingt darauf abgezielt, nicht das ursprüngliche LLM-Ergebnis erneut zu sampeln (Sampling without replacement).

Theoretische Fundierung

Verteilungsgültigkeit: Unter der Annahme, dass die Resampling-Positionen unabhängig von den nachfolgenden Token sind (Assumption 1), konvergiert die empirische Verteilung der PPoT-Stichproben fast sicher gegen die ursprüngliche Verteilung des LLMs ( $P_{\text{code}}$ ).
Effizienz: Ein einzelnes LLM-Call generiert $k$ Programme, aus denen jeweils $m$ weitere Programme abgeleitet werden können. Insgesamt werden $k \cdot (1+m)$ Kandidaten mit nur $k$ GPU-Generierungen erzeugt.

3. Wichtige Beiträge

Neue Decodierungstechnik: Einführung von PPoT als effiziente Methode zur Generierung strukturierter Ausgaben, die die Verteilung des LLMs explizit nutzt.
Theoretische Korrektheit: Nachweis, dass PPoT unter bestimmten Unabhängigkeitsannahmen verteilungsgemäß korrekt (distributionally sound) ist.
Empirische Validierung: Demonstration konsistenter Verbesserungen bei pass@k auf drei Benchmarks (GSM8k, Plot2Code, CRUXEval) ohne zusätzliche GPU-Kosten.
Recheneffizienz: Quantitativer Nachweis, dass PPoT signifikante Einsparungen gegenüber direktem Sampling aus dem LLM bietet.

4. Ergebnisse

Die Evaluation wurde mit Qwen2.5 Coder (0.5B, 3B, 7B) und Qwen2.5 VL auf folgenden Datensätzen durchgeführt:

GSM8k (Mathematische Argumentation):
- Mit nur $m=5$ PPoT-Samples pro LLM-Sample stieg die Genauigkeit um 2–7 % (z. B. von 82,71 % auf 84,76 % beim 7B-Modell bei 1 LLM-Sample).
- PPoT erreicht die Leistung von 20 LLM-Samples bereits mit nur 8 LLM-Samples (plus PPoT-Samples).
Plot2Code (Code-Generierung für Visualisierungen):
- Verbesserung der Text-Übereinstimmung um 0,5–6 %.
- PPoT konnte Laufzeitfehler korrigieren, indem es falsche Dimensionen oder Parameter in den generierten Matplotlib-Codes durch Resampling korrigierte.
CRUXEval (Strukturierte Ausgabe / Code-Verständnis):
- Steigerung der Genauigkeit um 3–7 % durch Resampling von Token in strukturierten Objekten (z. B. Listen, Strings).

Effizienz:

Die Kompilierung und das Sampling von PPoT-Programmen sind rechnerisch vernachlässigbar im Vergleich zur LLM-Inferenz.
Die Zeitkurven für $m=0$ und $m=20$ sind nahezu identisch, was zeigt, dass die Genauigkeitsgewinne zu fast null zusätzlichen Kosten erzielt werden.
Skalierungsgesetze zeigen, dass 20 PPoT-Samples pro LLM-Sample einer zusätzlichen Generierung von ca. 39 reinen LLM-Samples entsprechen.

5. Bedeutung und Ausblick

Paradigmenwechsel: Das Paper schlägt vor, generierten Code nicht nur als Text, sondern als probabilistisches Programm zu interpretieren. Dies ermöglicht es, Unsicherheiten des Modells systematisch zu nutzen, um bessere Lösungen zu finden, ohne das Modell erneut abfragen zu müssen.
Ressourcenschonung: PPoT bietet einen Weg, die Rechenleistung von LLMs effizienter zu nutzen, was besonders für ressourcenbeschränkte Umgebungen oder teure große Modelle relevant ist.
Zukünftige Arbeiten: Die Autoren sehen Potenzial darin, die Struktur der Zufallsvariablen zu erweitern (z. B. auf Sub-Ausdrücke oder Kontrollflussstrukturen) und PPoT für andere probabilistische Abfragen (z. B. Erwartungswerte) zu nutzen.

Zusammenfassend stellt PPoT einen effizienten Testzeit-Ansatz dar, der die „verlorenen" Wahrscheinlichkeiten von LLM-Generierungen nutzt, um die Erfolgsrate bei Code- und Reasoning-Aufgaben signifikant zu steigern, ohne die GPU-Kosten proportional zu erhöhen.