Riepilogo Tecnico: RISCOSET per la Quantificazione dell'Incertezza nella Generazione di Codice basata su LLM

Enunciato del Problema

I Large Language Models (LLM) sono sempre più utilizzati per la generazione di codice, ma soffrono di allucinazioni e della generazione di output tossici o distorti, limitandone il dispiegamento in applicazioni ad alto rischio. Sebbene la Predizione Conformale (CP) offra un quadro per la quantificazione dell'incertezza con garanzie indipendenti dalla distribuzione, adattarla a compiti di generazione strutturata come il codice è una sfida.

Gli approcci esistenti, come gli insiemi di previsione PAC (Probabilmente Approssimativamente Corretti) per il codice (Khakhar et al., 2023), affrontano due limitazioni critiche:

1. Vincoli di Monotonia: Si basano su una forte assunzione di monotonia riguardo al rischio e alla dimensione dell'insieme di previsione. Ciò restringe lo spazio dei programmi parziali ammissibili, portando spesso a soluzioni subottimali che rimuovono troppi nodi di codice.
2. Assunzione di Etichetta Singola: Sono progettati per la classificazione a etichetta singola. Tuttavia, la generazione di codice è intrinsecamente un problema a etichette multiple, dove più programmi sintatticamente diversi possono possedere semantica identica e corretta. I metodi esistenti non riescono ad accogliere questa molteplicità, limitando severamente lo spazio dei candidati.

Metodologia: RISCOSET

Gli autori propongono RISCOSET, un metodo che costruisce insiemi di previsione a controllo del rischio per la generazione di codice basata su LLM, riformulando il problema come un compito di classificazione a etichette multiple e sfruttando il quadro Learn Then Test (LTT) (Angelopoulos et al., 2025).

Componenti Principali

1. Riformulazione a Etichette Multiple e Rischio Strutturato:
   Invece di imporre la monotonia, RISCOSET definisce una funzione di rischio strutturata basata sulla correttezza semantica. Per un dato input, l'obiettivo è produrre un insieme di previsione (rappresentato come un programma parziale o un sottoalbero AST) che contenga almeno un programma corretto da un insieme di etichette potenziato $\tilde{Y}$. Il rischio empirico è definito come la frazione di istanze di calibrazione in cui l'insieme di previsione non interseca l'insieme dei programmi corretti.

2. Ottimizzazione per Programmi Parziali:
   Per generare l'insieme di previsione, il metodo risolve un problema di ottimizzazione per potare nodi dall'Albero della Sintesi Astratta (AST) del codice generato.

   • Obiettivo: Mantenere il maggior numero possibile di nodi garantendo che l'incertezza totale (log-probabilità negativa) del programma parziale rimanente non superi una soglia $\lambda$.
   • Vincoli: La soluzione deve soddisfare la connettività dell'albero (se un genitore viene rimosso, anche i figli devono essere rimossi) e un limite sul numero di rimozioni di sottoalberi ammissibili ($t_{max}$). Crucialmente, questa ottimizzazione rimuove il vincolo di monotonia stretta trovato nei metodi PAC, consentendo uno spazio di etichette ammissibili più ampio.

3. Test di Ipotesi Multiple (LTT):
   RISCOSET impiega il quadro LTT per selezionare il parametro ottimale $\hat{\lambda}$ che controlla il rischio.

   • Tratta la selezione di $\lambda$ come un problema di test di ipotesi multiple.
   • Per un insieme di valori candidati di $\lambda$, calcola i valori $p$ basati sul rischio strutturato empirico.
   • Utilizzando un algoritmo di controllo del Tasso di Errore Familiare (FWER), identifica un insieme valido di parametri $\Lambda_{valid}$ che garantisce che il rischio rimanga al di sotto di una tolleranza specificata dall'utente $\alpha$ con alta confidenza ($1-\delta$).

4. Strategia di Esecuzione Selettiva:
   Poiché la generazione di codice è a etichette multiple, il processo di calibrazione richiede il campionamento di più programmi candidati e la loro verifica tramite esecuzione di casi di test, il che è computazionalmente costoso. Per mitigare ciò, RISCOSET introduce una strategia di esecuzione selettiva:

   • Utilizza punteggi di incertezza (ad esempio, la perplessità) per decidere quali programmi campionati richiedono l'esecuzione dei test.
   • I programmi con bassa incertezza sono accettati come corretti senza esecuzione, mentre quelli ad alta incertezza vengono verificati.
   • Questa strategia utilizza il campionamento per importanza e la disuguaglianza di Hoeffding per stimare un limite superiore dell'errore, garantendo che il tasso di errore delle etichette rimanga entro un limite controllato $\epsilon$ riducendo significativamente i costi computazionali.

Contributi Chiave

1. Quadro RISCOSET: La prima applicazione del quadro LTT alla generazione strutturata di codice, riformulando la costruzione dell'insieme di previsione come un problema a etichette multiple con vincoli più deboli rispetto agli approcci basati su PAC.
2. Ottimizzazione del Rischio Strutturato: Una nuova formulazione di ottimizzazione per generare programmi parziali (sottoalberi AST) che massimizza le informazioni mantenute soddisfacendo le garanzie di controllo del rischio, libera da assunzioni di monotonia restrittive.
3. Calibrazione Efficiente: Una strategia di esecuzione selettiva che bilancia il compromesso tra controllo del rischio e costo computazionale della verifica delle etichette, supportata da limiti di errore non asintotici.
4. Validazione Empirica: Esperimenti completi che dimostrano l'efficacia del metodo su tre LLM (Deepseek-Coder, Qwen2.5-Coder, Llama3.1) e tre dataset (HumanEval, MBPP, APPS).

Risultati Sperimentali

Gli autori hanno valutato RISCOSET rispetto a baseline all'avanguardia, inclusi l'approccio all'insieme di previsione PAC e una variante greedy.

• Riduzione della Rimozione di Nodi: RISCOSET riduce significativamente il numero di nodi AST rimossi rispetto alle baseline mantenendo lo stesso livello di controllo del rischio. Ad esempio, sul dataset MBPP con $\alpha=0.15$, il metodo ha ridotto la rimozione di codice del 24,5% rispetto al miglior concorrente.
• Garanzie di Copertura: Gli insiemi di previsione costruiti hanno costantemente raggiunto tassi di copertura superiori al limite target ($1-\alpha$), validando le garanzie teoriche di controllo del rischio.
• Scalabilità del Modello: Il metodo ha funzionato bene sia su modelli specializzati per il codice (Qwen2.5-Coder) sia su modelli generici (Llama3.1), mostrando che le prestazioni migliorano con modelli generativi più potenti.
• Efficienza dell'Esecuzione Selettiva: La strategia di esecuzione selettiva ha ridotto con successo la proporzione di programmi che richiedono l'esecuzione di casi di test (ad esempio, evitando l'esecuzione per circa il 30% dei programmi a un tasso di errore delle etichette di $\epsilon=0.1$) mantenendo la copertura al di sopra della soglia target.

Significato e Affermazioni

Il documento afferma di essere il primo lavoro a introdurre il quadro LTT nei compiti di generazione di codice strutturato. Il suo significato principale risiede nell'affrontare le limitazioni dei metodi esistenti basati su PAC attraverso:

• L'eliminazione della necessità di forti assunzioni di monotonia, espandendo così lo spazio dei programmi candidati e riducendo la rimozione non necessaria di codice.
• L'accoglienza naturale della natura a etichette multiple della generazione di codice (multiple soluzioni valide per un singolo compito).
• La fornitura di garanzie statistiche rigorose per la correttezza degli insiemi di codice generati senza fare affidamento su assunzioni di indipendenza che falliscono in domini strutturati come il codice.

Gli autori concludono che, sebbene il loro focus sia sulla generazione di codice, il metodo proposto è adattabile ad altri problemi di previsione strutturata in cui la quantificazione dell'incertezza è critica. Riconoscono il sovraccarico computazionale della fase di calibrazione, ma sottolineano che la strategia di esecuzione selettiva mitiga efficacemente questo costo.