Probabilistic Programs of Thought

Titolo: Probabilistic Programs of Thought (PPoT)

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

---

1. Il Problema

I Large Language Models (LLM) sono ampiamente utilizzati per la generazione di codice e il ragionamento matematico, spesso attraverso il paradigma dei "Programmi di Pensiero" (Programs of Thought), dove il modello genera codice per risolvere un problema.
Il flusso di lavoro standard prevede:

1. Promptare il modello.
2. Generare un campione di codice.
3. Esecuzione e verifica.
4. Se il codice è errato, ripetere il processo (spesso con strategie come Best-of-n o Beam Search).

Limitazioni attuali:

• Costo Computazionale: Ottenere $n$ campioni validi richiede $n$ generazioni distinte dall'LLM. Poiché ogni generazione richiede un passaggio in avanti (forward pass) su GPU, questo diventa proibitivamente costoso per modelli grandi o per un alto numero di campioni ($n$).
• Inefficienza: Il metodo tradizionale scarta le probabilità dei token (logits) dopo aver campionato un token concreto, perdendo l'informazione sulla distribuzione sottostante che potrebbe essere sfruttata per generare varianti a basso costo.

2. Metodologia: Probabilistic Programs of Thought (PPoT)

Gli autori propongono un nuovo framework di decoding a tempo di test (test-time) che espone la distribuzione di probabilità dell'LLM all'interno del programma generato stesso.

Concetto Chiave:
Invece di trattare il codice generato come un programma deterministico statico, PPoT lo trasforma in un programma probabilistico.

1. Generazione Iniziale: L'LLM genera un programma deterministico.
2. Identificazione delle Variabili: Vengono identificati token specifici (es. numeri, operatori aritmetici, operatori di confronto) che hanno un'alta entropia o sono critici per la logica.
3. Trasformazione: Questi token vengono convertiti in variabili casuali ($X_i$). La distribuzione di ciascuna variabile è parametrizzata dai logits (probabilità dei prossimi token) forniti dall'LLM al momento della generazione.
4. Programma Probabilistico: Il risultato è un programma che rappresenta compattamente un numero esponenziale di programmi deterministici possibili.

Algoritmo di Inferenza:

• Fase 1 (Costosa): Si esegue una singola generazione dall'LLM ($k$ volte) per ottenere il programma base e i logits associati.
• Fase 2 (Economica): Si compila un programma probabilistico. Da questo programma, si possono campionare $m$ nuove varianti di codice senza ulteriori chiamate alla GPU.
• Assunzione di Indipendenza: Il metodo si basa sull'assunzione che i token riscampionati siano indipendenti dai token successivi nel contesto della sequenza originale, permettendo un campionamento efficiente senza dover rigenerare l'intera sequenza.

Vantaggio Computazionale:
Mentre il campionamento diretto richiede $O(k \cdot m)$ chiamate GPU, PPoT richiede solo $O(k)$ chiamate GPU, spostando il costo computazionale aggiuntivo su operazioni CPU molto più economiche (inferenza probabilistica sul programma compilato).

3. Contributi Chiave

1. Nuova Tecnica di Decoding: Introduzione di PPoT, un metodo che permette di generare efficientemente più campioni strutturati (codice) a partire da una singola generazione LLM.
2. Correttezza Distribuzionale: Dimostrazione teorica che, sotto specifiche ipotesi di indipendenza, la distribuzione empirica dei campioni ottenuti tramite PPoT converge alla distribuzione originale dell'LLM ($P_{code}$).
3. Mappatura Token-Programma: Trasformazione diretta del codice Python generato in un programma probabilistico, trattando costanti e operatori come variabili casuali con supporti definiti sintatticamente (es. un operatore + può diventare una variabile su $\{+, -, *, /\}$).
4. Validazione Empirica: Sperimentazione su tre benchmark diversi (GSM8k, Plot2Code, CRUXEval) che dimostra miglioramenti significativi nelle prestazioni con un costo computazionale marginale.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su modelli Qwen2.5 Coder e Qwen2.5 VL (dalle dimensioni 0.5B a 7B).

• Ragionamento Matematico (GSM8k):
  • Utilizzando solo 5 campioni PPoT aggiuntivi per ogni generazione LLM, l'accuratezza è aumentata del 2-7% senza costi GPU aggiuntivi.
  • Per raggiungere la stessa accuratezza di 20 campioni LLM puri, PPoT necessita di soli 8 campioni LLM (più i campioni PPoT), riducendo drasticamente il carico GPU.
• Generazione di Codice (Plot2Code):
  • Miglioramento del punteggio di corrispondenza testuale (text match) del 0.5-6%.
  • Esempi qualitativi mostrano come PPoT corregga errori di runtime (es. dimensioni di array errate) o parametri di visualizzazione che l'LLM aveva sbagliato, generando grafici corretti partendo da un codice errato.
• Generazione di Output Strutturati (CRUXEval):
  • Applicato a task di inversione di codice (dato un output, trovare l'input). PPoT ha migliorato l'accuratezza del 3-7% riscampionando sottoinsiemi di token (es. virgole, parentesi) per trovare input validi alternativi.

Efficienza:

• I tempi di compilazione e campionamento del programma probabilistico sono trascurabili rispetto al tempo di inferenza dell'LLM. Le curve di runtime mostrano che aggiungere 20 campioni PPoT non aumenta significativamente il tempo totale rispetto a un solo campione LLM.
• Analisi delle "Scaling Laws": PPoT aumenta l'esponente di scaling, riducendo l'errore più rapidamente all'aumentare del numero di campioni totali.

5. Significato e Impatto

Il lavoro di PPoT rappresenta un cambio di paradigma nell'uso degli LLM per compiti strutturati:

• Democratizzazione dell'Inferenza: Permette di ottenere benefici simili all'aumento massiccio del numero di campioni (Best-of-n) senza i costi energetici e finanziari associati.
• Interpretabilità: Trasforma il codice generato in un modello statistico esplicito, permettendo di ragionare sull'incertezza del modello direttamente nel dominio del codice.
• Futuro della Ricerca: Apre la strada all'uso di programmi probabilistici come astrazioni per le generazioni degli LLM, permettendo query probabilistiche complesse (es. calcolo di valori attesi, condizionamento su vincoli) con un numero minimo di chiamate al modello.

In sintesi, PPoT risolve il collo di bottiglia computazionale della generazione di codice iterativa, sfruttando l'informazione probabilistica già presente nell'LLM per "estrarre" più soluzioni a costo quasi zero.