🤖 AI

Goedel-Code-Prover: Hierarchical Proof Search for Open State-of-the-Art Code Verification

Il paper presenta Goedel-Code-Prover, un modello di linguaggio da 8 miliardi di parametri che utilizza una ricerca di prove gerarchica e un punteggio di decomposizione unificato per verificare formalmente il codice in Lean 4, ottenendo prestazioni superiori rispetto a modelli molto più grandi e raggiungendo un tasso di successo del 62,0% su benchmark complessi.

Autori originali: Zenan Li (Mike), Ziran Yang (Mike), Deyuan (Mike), He, Haoyu Zhao, Andrew Zhao, Shange Tang, Kaiyu Yang, Aarti Gupta, Zhendong Su, Chi Jin

Pubblicato 2026-03-23

📖 4 min di lettura☕ Lettura da pausa caffè

CC BY 4.0

Autori originali: Zenan Li (Mike), Ziran Yang (Mike), Deyuan (Mike), He, Haoyu Zhao, Andrew Zhao, Shange Tang, Kaiyu Yang, Aarti Gupta, Zhendong Su, Chi Jin

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di dover costruire un grattacielo. Se chiedi a un architetto molto intelligente (ma un po' distratto, come un'intelligenza artificiale generica) di disegnare tutto il piano in un unico colpo, probabilmente otterrai un edificio che sembra bello da fuori, ma che crollerà appena ci provi a salire. I "bug" (errori) sono come crepe invisibili che i test normali non vedono.

Questo articolo presenta Goedel-Code-Prover, un nuovo metodo per insegnare alle intelligenze artificiali a scrivere codice che sia matematicamente perfetto, non solo "sembra funzionare".

Ecco come funziona, spiegato con parole semplici e metafore:

1. Il Problema: L'Architetto Distratto

Le attuali intelligenze artificiali (LLM) sono bravissime a scrivere codice. Possono creare app, giochi e siti web. Ma quando si tratta di garantire che quel codice non abbia nessun errore logico (nemmeno uno!), falliscono.
È come se un architetto ti dicesse: "Ho disegnato un ponte che sembra solido, ma non ho mai calcolato se reggerà il peso di un camion". I test normali (come farci passare sopra delle auto) non bastano: serve una prova matematica che il ponte non crollerà mai.

2. La Soluzione: Dividere e Comandare (Gerarchia)

Il metodo proposto non chiede all'AI di risolvere tutto in una volta. Immagina di dover pulire una casa enorme e molto sporca.

Il vecchio modo: Chiedere a un robot di pulire la casa intera in un solo tentativo. Risultato: fa confusione e lascia angoli sporchi.
Il nuovo modo (Goedel-Code-Prover): L'AI agisce come un capo cantiere intelligente.
1. Fase 1 (Scomposizione): Prima di pulire, il capo divide la casa in stanze, poi le stanze in angoli, e gli angoli in oggetti specifici. "Oggi puliamo solo il divano del salotto".
2. Fase 2 (Completamento): Una volta diviso il lavoro in piccoli pezzi gestibili, l'AI pulisce ogni singolo pezzo con cura estrema.

In termini tecnici, l'AI prende un obiettivo di verifica complesso (es. "questo programma non deve mai bloccarsi") e lo spezza in piccoli teoremi più semplici (lemmi) che sono più facili da provare.

3. Il "Voto di Qualità": Il Termometro della Fiducia

Come fa l'AI a sapere se la sua divisione del lavoro è buona o no?
Hanno creato un "Voto di Qualità" (chiamato Decomposition Score) che funziona come un termometro:

Giustificazione Costruttiva: "Ho diviso il problema in modo che, se i pezzi piccoli funzionano, anche il grande funziona?" (Se la risposta è sì, il voto sale).
Semplicità Strutturale: "I pezzi che ho creato sono davvero più semplici dell'originale?" (Se sì, il voto sale ancora di più).

Questo voto è fondamentale perché viene usato per due scopi:

Durante l'allenamento: Insegna all'AI quali divisioni sono migliori (come un insegnante che dà un voto a un compito).
Durante l'uso: Quando l'AI lavora su un problema reale, usa questo voto per scegliere la strada migliore da percorrere, scartando quelle che sembrano promettenti ma sono in realtà trappole.

4. L'Allenamento: Imparare con l'Errore e la Ripetizione

Hanno addestrato questo modello (chiamato Gödel-Code-Prover-8B) in due fasi:

Imparare dai maestri: Hanno mostrato all'AI migliaia di esempi di come dividere e risolvere problemi (come un apprendista che guarda i lavori di un maestro).
Allenamento Ibrido: Hanno lasciato che l'AI provasse a risolvere problemi da sola. Se sbagliava, riceveva un feedback immediato. Se trovava una buona divisione del lavoro, riceveva un "premio" (il voto di qualità). Questo l'ha resa bravissima sia a pianificare (dividere il problema) che a eseguire (scrivere la prova).

5. I Risultati: Un Gigante in un Corpo Piccolo

Il risultato è sorprendente. Hanno creato un modello "piccolo" (8 miliardi di parametri, che per gli standard attuali è come un'auto di media cilindrata) che batte modelli "giganti" (fino a 84 volte più grandi) e modelli che costano milioni di dollari.

Perché? Perché non cerca di fare tutto a memoria. Impara a pensare passo dopo passo.
Efficienza: Più tempo e risorse dai all'AI per cercare la soluzione (più "tentativi"), più aumenta la probabilità di successo, in modo costante. Non si blocca mai.

In Sintesi

Immagina che Goedel-Code-Prover sia un detective privato molto metodico.
Invece di saltare alle conclusioni ("Il colpevole è X!"), il detective:

Analizza la scena del crimine.
Divide il caso in piccoli indizi gestibili (chi era nell'edificio? che ora era? cosa mancava?).
Verifica ogni singolo indizio con prove matematiche inconfutabili.
Solo quando ogni piccolo indizio è confermato, costruisce il caso finale.

Grazie a questo metodo, il codice prodotto non è solo "probabilmente corretto", ma è matematicamente garantito come corretto. È un passo enorme verso un futuro in cui il software che usiamo ogni giorno (dalle banche ai sistemi medici) non avrà mai bug critici.

1. Il Problema: Verifica Formale del Codice con LLM

Il lavoro affronta la sfida critica di garantire la corretteza formale del codice generato dai Large Language Models (LLM). Sebbene gli LLM siano eccellenti nella generazione di codice e nella scrittura di test unitari, questi metodi empirici non possono certificare l'assenza di errori logici sottili o violazioni delle specifiche.

La verifica formale, che richiede la costruzione di prove verificabili da macchina (ad esempio in Lean 4), è il metodo standard per colmare questo divario. Tuttavia, l'automazione di questo processo è estremamente difficile per due motivi fondamentali che distinguono la verifica del codice dalla dimostrazione di teoremi matematici:

Decomposizione non fondata (Ungrounded decomposition): A differenza della matematica, dove esiste un vasto corpus di ragionamenti informali (libri di testo, articoli) che insegna agli LLM come scomporre i problemi, per la correttezza del codice non esiste un corpus equivalente. Gli sviluppatori raramente formalizzano il ragionamento sul loro codice, rendendo difficile per gli LLM proporre sottoproblemi (lemmi) significativi e semanticamente validi.
Spostamento di dominio e proliferazione concettuale: Ogni programma introduce un "universo concettuale" nuovo (comportamenti computazionali, invarianti di strutture dati) che non può essere risolto semplicemente attingendo a librerie preesistenti come Mathlib. Inoltre, le tattiche necessarie per la verifica del codice (es. grind, riflessione computazionale) differiscono sostanzialmente da quelle algebriche usate in matematica, causando un fallimento dei modelli addestrati principalmente su dati matematici.

2. Metodologia: Framework di Ricerca Gerarchica

Gli autori propongono Goedel-Code-Prover, un framework di ricerca gerarchica per la verifica automatica in Lean 4. L'approccio si basa su un'unica policy unificata che gestisce sia la decomposizione che la completamento delle prove, operando in un ciclo di "pianificazione e prova".

A. Scomposizione Gerarchica (Planning)

Invece di tentare di generare l'intera prova in un unico passaggio, il sistema scompone ricorsivamente l'obiettivo di verifica principale in una serie di lemmi intermedi più semplici.

Obiettivo: Trasformare un teorema complesso in sottobiettivi strutturalmente più semplici che, se dimostrati, implicano la correttezza dell'originale.

B. Il Punteggio di Decomposizione (Decomposition Score)

Il cuore innovativo del lavoro è un punteggio principiato ( $S$ ) che guida sia l'addestramento che l'inferenza. Questo punteggio valuta le candidate decomposizioni lungo due assi:

Giustificazione Costruttiva (Constructive Justification):
- Ricostruzione della prova: I lemmi proposti devono logicamente implicare il teorema genitore.
- Filtro Quickcheck: Viene eseguito un controllo automatico di controesempi (random sampling) sui lemmi proposti. Se un lemma è falso o non dimostrabile, la decomposizione viene scartata immediatamente.
Efficacia Strutturale (Structural Effectiveness):
- Viene misurata la riduzione della complessità attraverso il "footprint degli operatori" ( $d(\cdot)$ ), ovvero il numero totale di operatori logici e specifici del dominio nell'AST (Abstract Syntax Tree) del goal.
- Una decomposizione è efficace se riduce il footprint degli operatori rispetto al goal originale.

Il punteggio finale è definito come $S = r \cdot v$ , dove $v$ è un gate binario di validità (ricostruzione + quickcheck) e $r$ è il rapporto di riduzione strutturale. Questo punteggio funge da ricompensa densa e continua durante l'addestramento, risolvendo il problema della scarsità di segnali (reward sparsity) tipico della verifica formale.

C. Pipeline di Addestramento Ibrida (Hybrid RL)

Il modello (basato su Qwen-3-8B) viene addestrato in due fasi:

Inizializzazione Supervisionata (SFT): Utilizzo di dati generati da modelli frontier (GPT-5.2, Gemini-3-Flash) per creare traiettorie di decomposizione e completamento.
Reinforcement Learning Ibrido:
- Decomposizione: Ottimizzata tramite GRPO (Group Relative Policy Optimization) utilizzando il punteggio continuo $S$ come ricompensa per guidare l'esplorazione.
- Completamento: Stabilizzato tramite replay supervisionato di traiettorie di prova di alta qualità, evitando di affidarsi a segnali binari sparsi (successo/fallimento della prova).
- Questo approccio bilancia l'esplorazione strutturale con la generazione stabile delle prove.

3. Risultati Sperimentali

Il framework è stato valutato su tre benchmark basati su Lean 4, comprendenti un totale di 427 task (Verina, Clever, AlgoVeri).

Performance: Il modello Goedel-Code-Prover-8B (8 miliardi di parametri) ha raggiunto un tasso di successo nella prova del 62.0% complessivo.
Confronto: Questo risultato rappresenta un miglioramento di 2.6 volte rispetto alla baseline più forte (modelli di ragionamento frontier o prover neurali esistenti).
Efficienza: Il modello da 8B supera prover neurali fino a 84 volte più grandi (es. modelli da 671B), dimostrando che la decomposizione gerarchica è più efficace della semplice scalabilità delle dimensioni del modello.
Scalabilità all'Inferenza: Si osserva una scalabilità monotona: il tasso di successo migliora all'aumentare delle iterazioni di ricerca e del budget di campionamento parallelo ($pass@k$), indicando che il modello non ha ancora saturato il suo potenziale.
Complessità delle Prove: Le prove verificate richiedono in media 8-17 lemmi decomposti e oltre 130 righe di codice di prova, con casi complessi che superano le 680 righe, dimostrando la capacità del sistema di gestire ragionamenti strutturati profondi.

4. Contributi Chiave

Framework Gerarchico: Un nuovo paradigma per la verifica del codice che separa la pianificazione (decomposizione in lemmi) dalla generazione tattica, superando i limiti dei metodi "flat" (singolo passaggio).
Punteggio di Decomposizione Unificato: Un meccanismo di scoring che combina validità semantica (quickcheck) e riduzione strutturale, utilizzato coerentemente come ricompensa di addestramento e criterio di ordinamento durante l'inferenza.
Pipeline RL Ibrida: Una strategia di addestramento che risolve il mismatch delle ricompense tra decomposizione (segnale continuo) e completamento (segnale binario), permettendo a un'unica policy di eccellere in entrambe le fasi.
Efficacia del Modello Piccolo: Dimostrazione che un modello di dimensioni moderate (8B), se specializzato con un'architettura di ragionamento adeguata, può superare modelli massicci generici nel dominio della verifica formale.

5. Significato e Implicazioni

Questo lavoro segna un passo avanti significativo nel colmare il divario tra la generazione di codice "che sembra funzionare" e il codice "provabilmente corretto".

Superamento del Gap Matematica-Codice: Il paper identifica e risolve le specifiche difficoltà della verifica del codice (mancanza di corpus di ragionamento informale, proliferazione concettuale) che hanno finora limitato l'applicazione diretta delle tecniche di dimostrazione di teoremi matematici.
Scalabilità ed Efficienza: Dimostra che l'intelligenza artificiale per la verifica formale non deve necessariamente puntare su modelli giganti, ma può beneficiare enormemente di architetture di ricerca gerarchica e di addestramento mirato.
Futuro della Sicurezza del Software: Fornisce un approccio pratico e scalabile per integrare la verifica formale nei flussi di lavoro di sviluppo software, rendendo possibile l'adozione di sistemi critici con garanzie di sicurezza matematica.

In sintesi, Goedel-Code-Prover trasforma la verifica del codice da un compito di generazione monolitica in un processo di pianificazione gerarchica, rendendo la verifica formale automatizzata accessibile ed efficace anche per problemi algoritmici complessi.