Towards Functional Correctness of Large Code Models with Selective Generation

Sintesi Tecnica: Verso la Correttezza Funzionale dei Modelli di Codice tramite la Generazione Selettiva

Problema

I Large Language Models (LLM) hanno dimostrato prestazioni significative nei compiti di generazione di codice; tuttavia, la loro applicabilità in sistemi critici per la sicurezza è ostacolata dalla "allucinazione del codice", in cui il codice generato non soddisfa le specifiche funzionali desiderate. Un collo di bottiglia critico nel mitigare questo problema è la difficoltà di identificare la correttezza funzionale del codice generato. A differenza del linguaggio naturale, dove l'implicazione semantica può essere annotata dagli esseri umani, il codice possiede una struttura complessa e innaturale che rende difficile la verifica manuale dell'equivalenza funzionale. I benchmark esistenti spesso si affidano a suite di test unitari limitate e curate manualmente, che potrebbero non coprire un numero sufficiente di percorsi di esecuzione per garantire la correttezza. Inoltre, gli attuali metodi per controllare l'allucinazione si concentrano spesso sul miglioramento delle prestazioni del modello tramite fine-tuning o ranking, mancando di meccanismi diretti e teoricamente fondati per controllare il tasso di output falsi durante l'inferenza.

Metodologia

Gli autori propongono un framework per la Generazione Selettiva di Codice che controlla teoricamente il tasso di allucinazione utilizzando una metrica di False Discovery Rate con Code Entailment (FDR-CE). La metodologia consiste in tre componenti principali:

1. $\alpha$-Code Entailment e Fuzzing

Per affrontare la difficoltà di definire la correttezza funzionale, il paper ridefinisce l'implicazione (entailment) per il codice utilizzando la natura eseguibile dei programmi.

• $\alpha$-Code Entailment: Invece di richiedere l'equivalenza esatta, gli autori definiscono un frammento di codice $\hat{y}$ come $\alpha$-implicato da un generatore di test unitari $F(x)$ se la probabilità che $\hat{y}$ superi i test è almeno $1-\alpha$. Ciò consente una misura probabilistica della correttezza funzionale.
• FuzzEval: Per generare automaticamente e rigorosamente i necessari test unitari, gli autori impiegano il fuzzing, una tecnica di analisi dinamica del codice. Campionando e mutando casualmente i seed di input, il fuzzing esplora un'ampia gamma di percorsi di esecuzione per generare coppie input-output. Questo processo, denominato FuzzEval, serve a due scopi:
  • Apprendimento: Generare un grande insieme di test unitari per stimare l'insieme di implicazione per il generatore selettivo.
  • Valutazione: Fornire un benchmark di valutazione più rigoroso rispetto ai test statici curati manualmente.

2. Framework di Generazione Selettiva

Il sistema introduce un generatore selettivo $\hat{S}(x)$ che agisce come un post-processore per un generatore di codice base $G(x)$.

• Meccanismo di Astensione: Per un dato prompt $x$, il sistema calcola un punteggio $f(x, G(x))$ (ad esempio, log-probabilità normalizzata per lunghezza). Se il punteggio supera una soglia calibrata $\tau$, il codice viene restituito; altrimenti, il sistema si astiene (restituisce "I don't know").
• Controllo del Rischio: L'obiettivo è garantire che la probabilità che il codice selezionato sia funzionalmente errato (ovvero, non $\alpha$-implicato) rimanga al di sotto di un livello desiderato $\epsilon_S$. Ciò è formalizzato come il controllo del FDR-CE:
  $$R_\alpha(\hat{S}) := P\{ \hat{S}(x) \notin E_\alpha(x) \mid \hat{S}(x) \neq \text{IDK} \}$$
  dove $E_\alpha(x)$ è l'insieme dei frammenti di codice che soddisfano la condizione di $\alpha$-implicazione.

3. Garanzie Teoriche e Algoritmo (ASCG)

Gli autori propongono l'algoritmo di apprendimento ASCG (Algorithm for Selective Code Generation).

• Stima: Poiché il vero insieme di implicazione $E_\alpha$ è sconosciuto, l'algoritza utilizza un limite binomiale inferiore $\hat{L}$ derivato dai test unitari generati per stimare l'insieme di implicazione $\hat{E}_{\alpha, \epsilon_E}$.
• Calibrazione: Utilizzando un set di calibrazione, l'algoritmo cerca la soglia $\tau$ ottimale che minimizza la soglia (massimizzando l'efficienza di selezione) garantendo al contempo che il limite superiore del FDR-CE non superi il target $\epsilon_S$.
• Garanzia: Il Teorema 4.3 fornisce una garanzia teorica che il generatore selettivo appreso soddisfi il vincolo FDR-CE desiderato con alta probabilità ($1-\delta_S$), anche senza etichette di implicazione annotate da esseri umani.

Contributi Chiave

1. Generazione Selettiva per il Codice: Il paper estende il concetto di predizione selettiva (precedentemente applicato al linguaggio naturale) alla generazione di codice, introduendo un meccanismo per controllare il tasso di allucinazione tramite l'astensione.
2. Paradigma FuzzEval: Propone l'uso di strumenti di fuzzing per generare automaticamente test unitari sia per l'apprendimento della funzione di selezione che per la valutazione della correttezza del codice, superando i limiti delle piccole suite di test manuali.
3. Controllo Teorico del FDR-CE: Il lavoro fornisce un algoritmo di apprendimento con una garanzia di tipo PAC, assicurando che il tasso di codice generato falsamente (tra le risposte non soggette ad astensione) sia limitato da un parametro definito dall'utente.
4. Definizione di $\alpha$-Code Entailment: Formalizza una definizione probabilistica della correttezza del codice adatta all'analisi automatizzata, colmando il divario tra l'implicazione semantica nel NLP e l'equivalenza funzionale nel codice.

Risultati Sperimentali

Gli autori hanno valutato il loro metodo su diverse configurazioni, tra cui:

• Modelli: Quattro generatori di codice (GPT-4o, Gemini 1.5 Pro, GPT-4.1, CodeLlama 13B, DeepSeek-R1).
• Dataset: Quattro benchmark (APPS, Mercury, HumanEval, MBPP) convertiti in versioni "Fuzz" (APPS-f, ecc.) tramite test unitari generati automaticamente.
• Linguaggi: Python, C++, Java, JavaScript e Perl.

Risultati Chiave:

• Controllabilità: Il metodo proposto (SCG) riesce a limitare il FDR-CE al livello desiderato ($\epsilon_S$) attraverso vari modelli e dataset, mentre i metodi baseline (ad esempio, SCG-EM, SCG-manual) o non riescono a limitare il rischio o mostrano un'efficienza banale (astendendosi troppo frequentemente).
• Efficienza: SCG raggiunge un'efficienza di selezione ragionevole (il rapporto tra le risposte non soggette ad astensione) mantenendo la garanzia di sicurezza. Ad esempio, su GPT-4o con $\epsilon_S=0.3$, SCG ha mantenuto un FDR-CE al di sotto del target mantenendo circa il 33-50% delle risposte generate, a seconda del dataset.
• Beneficio del Fuzzing: Gli esperimenti hanno dimostrato che l'uso di test unitari generati tramite fuzzing (SCG) supera significativamente i metodi che utilizzano test manuali limitati (SCG-small) o nessun test (SCG-EM) sia in termini di controllo del rischio che di efficienza.
• Estensione ai Lavori Precedenti: Il metodo agisce come un post-processore che può essere applicato sopra i modelli avanzati esistenti (ad esempio, DeepSeek-R1 con fine-tuning GRPO), fornendo un ulteriore livello di garanzie di sicurezza statistica.

Significato e Rivendicazioni

Il paper sostiene che il suo contributo principale risieda nell'algoritmo di apprendimento della generazione selettiva che controlla direttamente il tasso di allucinazione dei modelli di codice. Sfruttando la natura eseguibile del codice attraverso il fuzzing, gli autori sostengono che sia possibile andare oltre i miglioramenti delle prestazioni euristici per raggiungere una sicurezza teoricamente controllata.

La significanza del lavoro è inquadrata come la fornitura di una "garanzia di controllabilità" sul False Discovery Rate, rendendo i generatori di codice più affidabili per sistemi che richiedono standard di sicurezza più elevati. Gli autori notano con modestia che, sebbene il metodo controlli il tasso di allucinazione, l'efficienza complessiva della selezione dipende ancora dalla qualità sottostante del generatore di codice, e l'assunzione i.i.d. per la garanzia teorica potrebbe limitarne l'applicabilità in ambienti con spostamento della distribuzione (distribution-shifting). Il lavoro non pretende di eliminare interamente l'allucinazione, ma piuttosto di fornire un meccanismo per gestirla e limitarla con rigore statistico.