🤖 AI

P $^{3}$ : Joint Program-and-Proof Planning for Verified Code Generation

Il documento introduce $P^3$ , un workflow agentico basato su LLM che pianifica congiuntamente programmi e le loro prove formali per superare le inefficienze della generazione sequenziale, raggiungendo prestazioni allo stato dell'arte e riduzioni significative dei costi su benchmark di generazione di codice verificato, incluso un nuovo dataset derivato da un repository chiamato Lean4Commit0.

Autori originali: Zenan Li, Ziran Yang, Peiyang Song, Zhaoyu Li, Kaiyu Yang

Pubblicato 2026-08-11

📖 7 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Zenan Li, Ziran Yang, Peiyang Song, Zhaoyu Li, Kaiyu Yang

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 insegnare a un robot super intelligente come scrivere una storia. Gli dai un suggerimento e il robot sputa fuori un racconto. Ma ecco il trucco: non vuoi solo una storia; vuoi una storia che sia matematicamente garantita come vera, senza buchi di trama, senza magie che violano le leggi della fisica e senza personaggi che scompaiono senza spiegazione. Questo è il mondo della generazione di codice verificato. È un angolo dell'informatica dove chiediamo all'Intelligenza Artificiale non solo di scrivere software, ma di scrivere software che venga accompagnato dal proprio "certificato di correttezza" — un certificato matematico che dice: "Prometto che questo codice farà esattamente ciò che ho detto che avrebbe fatto, per ogni possibile situazione".

Per molto tempo, il modo standard per farlo è stato come una danza in due tempi: prima il robot scrive il codice (la storia), e poi un team separato di robot-correttori di bozze cerca di controllare se la storia ha senso. Se i correttori trovano un buco nella trama, rimandano la storia allo scrittore per correggerla. Lo scrittore ripara la storia, la rimanda indietro, e il ciclo si ripete. Ma questo articolo suggerisce che questa danza "scrivi-e-poi-controlla" è spesso goffa ed inefficiente. È come cercare di costruire un ponte e poi, dopo averlo finito, rendersi conto che avevi dimenticato di inserire i pilastri di supporto, costringendoti a demolirlo e ricostruirlo. Gli autori di questo articolo propongono un nuovo modo: invece di scrivere il codice e poi la prova separatamente, il robot dovrebbe pianificare l'intero ponte — sia la strada che i supporti — contemporaneamente, assicurando che si incastrino perfettamente fin dal primo schizzo.

Il Problema: La trappola del "Scrivi-e-Poi-Controlla"

L'articolo, intitolato "Joint Program-and-Proof Planning for Verified Code Generation", affronta un collo di bottiglia frustrante nel modo in cui l'IA scrive software verificato. Attualmente, la maggior parte dei sistemi segue un flusso di lavoro "programma-e-poi-prova". È come chiedere a uno chef di cucinare un pasto complesso e poi, una volta che il cibo è sulla tavola, chiedere a un critico gastronomico di provare che gli ingredienti fossero freschi e il metodo di cottura sicuro. Se il critico trova un problema (come del pollo poco cotto), lo chef deve tornare indietro, ricucinare il piatto e sperare che il critico gli piaccia questa volta.

Gli autori sostengono che questo approccio sequenziale è difettoso. Quando l'IA si impegna a scrivere prima il codice, potrebbe scegliere una struttura che sembra corretta in superficie ma che è un incubo da provare. Per esempio, immagina che l'IA scriva un programma per trovare il numero più grande in una lista. Potrebbe scegliere un metodo che è breve e rapido da scrivere ma che richiede una regola matematica incredibilmente complessa e nascosta per dimostrare che funziona. Una volta scritto il codice, l'IA è bloccata: deve o inventare una prova super difficile per adattarsi a quel codice specifico o distruggere il codice e ricominciare da capo. Ciò porta a molto tempo perso, denaro e "cicli di riparazione" in cui l'IA continua a mettere pezze al codice e alla prova, ma non si incastrano mai perfettamente.

La Soluzione: P3 (Il pianificatore "Mano nella Mano")

Per risolvere questo problema, i ricercatori introducono P3, un nuovo flusso di lavoro in cui l'IA agisce come un maestro architetto che disegna la planimetria sia dell'edificio che dell'ispezione di sicurezza prima di posare anche un solo mattone.

Inveve di saltare direttamente alla scrittura del codice, P3 crea prima un piano unificato. Questo piano è uno schizzo di alto livello che risponde a due domande contemporaneamente:

Come funzionerà il codice? (Lo "Sketch del Programma")
Come proveremo che funziona? (Lo "Sketch della Prova")

Il piano decide la struttura della soluzione. Sceglie la "forma" giusta per il codice (come scegliere tra un ciclo ricorsivo o un fold) e simultaneamente sceglie le regole matematiche corrispondenti (invarianti) necessarie per provare che quella forma è sicura. È come decidere: "Costruiremo un ponte usando cavi di sospensione, quindi il nostro piano di prova deve includere il controllo della tensione di quei cavi".

Una volta che il piano condiviso è bloccato, l'IA passa all' "elaborazione" dei dettagli. Scrive il codice effettivo e la prova effettiva, ma sta solo riempiendo gli spazi vuoti di un progetto pre-concordato. Se la prova fallisce, l'IA sa esattamente dove guardare perché la struttura era già stata decisa. Se il piano stesso è cattivo (ad esempio, il design del ponte è impossibile), l'IA torna alla fase di pianificazione per ridisegnare la planimetria, invece di riparare freneticamente l'edificio finito.

Il Nuovo Campo di Prova: Lean4Commit0

Gli autori si sono resi conto che i test precedenti per questi sistemi di IA erano troppo facili, come chiedere a un robot di risolvere enigmi matematici da un libro di testo. Il software del mondo reale è molto più disordinato. Per testare correttamente il loro nuovo metodo, hanno costruito un nuovo benchmark chiamato Lean4Commit0.

Hanno analizzato 108 librerie software open-source reali (scritte in Python, Rust, C/C++ e Java) e hanno trasformato le loro caratteristiche principali in sfide di "codice verificato". Inveve di semplici compiti come "sommare due numeri", queste sfide coinvolgono relazioni complesse tra diverse parti di un programma. Ad esempio, in un sistema di configurazione, potrebbero chiedere all'IA di provare che "se imposti un'impostazione su 'Alto' e poi la imposti su 'Basso', il sistema ricorda correttamente l'impostazione 'Basso'". Questi compiti richiedono che l'IA comprenda come diverse funzioni comunicano tra loro, rendendoli molto più difficili dei problemi da manuale.

Cosa Hanno Scoperto: La Pianificazione Intelligente Vince

Il team ha testato P3 contro quattro dei modelli di IA più potenti disponibili (incluse versioni di Codex, Gemini e Claude) attraverso tre diversi benchmark: Verina, AlgoVeri e il loro nuovo Lean4Commit0.

I risultati sono stati chiari: Pianificare insieme funziona meglio che scrivere separatamente.

Tasso di Successo: P3 ha risolto più compiti di qualsiasi altro metodo in ogni singolo test. Nei compiti più difficili, ha migliorato il tasso di successo di 4,6 - 11,2 punti percentuali rispetto ai migliori metodi esistenti.
Efficienza: Non si è trattato solo di risolvere più problemi; si è trattato di risolverli più velocemente e a costi inferiori. Nei compiti difficili, P3 ha ridotto il costo delle chiamate API fino al 40% e ha tagliato il tempo impiegato fino al 37%. Questo perché l'IA non ha perso tempo cercando di provare cose impossibili o riscrivendo codice che era strutturalmente errato.
Il Vantaggio "Congiunto": Per dimostrare che la "pianificazione congiunta" era l'ingrediente segreto, hanno eseguito un test in cui l'IA pianificava il codice ma non pianificava la prova in anticipo. Questo metodo di "pianificazione del solo codice" ha ottenuto prestazioni peggiori rispetto a P3, confermando che pensare alla prova mentre si pianifica il codice è ciò che fa la differenza.

Un Esempio del Mondo Reale: L'Albero Rosso-Nero

Per mostrare come questo funzioni in pratica, gli autori hanno esaminato un classico problema dell'informatica: eliminare un nodo da un "albero rosso-nero" (una struttura dati complessa utilizzata per organizzare i dati in modo efficiente).

Il Vecchio Modo (Programma-e-Poi-Prova): L'IA si è impegnata in un modo specifico per eliminare il nodo. Si è scoperto che questo modo era così strutturalmente disordinato che la prova richiedeva oltre 6.300 righe di codice solo per tappare i buchi, o falliva del tutto.
Il Modo P3: L'IA ha prima pianificato l'eliminazione. Ha capito che un approccio strutturale diverso sarebbe stato più facile da provare. Si è attenuta a quel piano e ha risolto il problema in sole 1.105 righe.

Perché Questo è Importante

Questo articolo suggerisce che, affinché l'IA possa scrivere software veramente affidabili, dobbiamo smettere di trattare il "codice" e la "prova" come due lavori separati. Obbligando l'IA a pensare alla sicurezza matematica del codice mentre sta progettando il codice stesso, otteniamo software che non è solo corretto per costruzione, ma anche più economico e veloce da produrre. È un passaggio dal "riparalo dopo" al "costruiscilo bene al primo colpo", assicurando che il software su cui facciamo affidamento sia solido quanto la matematica che ne prova il funzionamento.

Riepilogo Tecnico: P3 – Pianificazione Congiunta di Programma e Dimostrazione per la Generazione di Codice Verificato

1. Definizione del Problema

Il documento affronta la generazione di codice verificato, un compito in cui un Large Language Model (LLM) deve sintetizzare sia un programma eseguibile ( $\pi$ ) sia una dimostrazione verificabile da macchina ( $\kappa$ ) che attesti come il programma soddisfi una specifica formale ( $\sigma = (P, Q)$ ). A differenza della generazione basata su test, la correttezza deve valere per tutti gli input ammissibili, non solo per un insieme finito di esempi.

Gli autori identificano un collo di bottiglia critico nell'attuale flusso di lavoro de facto, che segue un programma sequenziale "programma-poi-dimostrazione":

L'LLM si impegna su un'implementazione concreta.
Una fase separata di dimostrazione tenta di soddisfare gli obblighi di prova.
Se la verifica fallisce, il sistema entra in un fragile ciclo di "correzione e riprova" (patch-and-retry), alternando la correzione del codice alla correzione delle dimostrazioni.

Questo approccio sequenziale soffre di due problemi principali:

Efficacia: Un programma generato senza anticipare la sua dimostrazione potrebbe mancare di proprietà strutturali necessarie (ad esempio, specifici invarianti di induzione o strategie di decomposizione). Le riparazioni locali spesso falliscono nel recuperare una struttura favorevole alla dimostrazione che non era stata pianificata.
Efficienza: Significative risorse computazionali (token e tempo) vengono sprecate esplorando riparazioni per implementazioni che sono strutturalmente incompatibili con i requisiti di dimostrazione della specifica.

Il documento trae ispirazione dal principio di Dijkstra secondo cui programmi e le loro argomentazioni di correttezza dovrebbero essere sviluppati "mano nella mano", sostenendo che l'implementazione e la struttura della dimostrazione si vincolino reciprocamente.

2. Metodologia: Il Framework P3

Gli autori propongono P3, un workflow agentico che scinde la pianificazione dall'elaborazione per garantire la coerenza strutturale tra il programma e la dimostrazione prima che uno dei due sia pienamente realizzato.

2.1 Pianificazione Congiunta di Programma e Dimostrazione

Nella prima fase, l'agente LLM genera un piano unificato ( $\rho$ ) basato sulla specifica $\sigma$ . Questo piano non è semplicemente codice; è uno schema di alto livello che contiene quattro impegni specifici:

Contratto Formale: Istruzioni algoritmiche e vincoli asintotici.
Decomposizione del Programma: La variabile di ricorsione, la struttura dei rami, la rappresentazione dei dati e le misure di terminazione.
Dipendenze dalle Librerie: Funzioni concrete e lemmi esistenti da utilizzare.
Obblighi di Dimostrazione: Il predicato di collegamento (bridging predicate), la struttura di induzione/caso e le dichiarazioni di necessari lemmi ausiliari.

L'agente valida questi piani candidati a livello di schema. Un piano viene rifiutato se lo schema del programma viola le istruzioni, se la decomposizione non preserva il predicato di collegamento o se il predicato non implica la post-condizione. L'agente seleziona il piano che minimizza l'onere di dimostrazione anticipato.

2.2 Elaborazione Guidata dal Piano

Una volta selezionato un piano $\rho$ , l'agente entra nella fase di elaborazione:

Implementazione: L'agente scrive il codice ( $\pi$ ) aderendo strettamente alla decomposizione e alla struttura fissate in $\rho$ .
Scaffold della Dimostrazione: L'agente scrive uno scheletro di dimostrazione ( $\kappa$ ) che rispecchia la struttura del piano (ad esempio, specifici principi di induzione o suddivisioni di casi), lasciando lacune locali (rappresentate come sorry) per tattiche dettagliate.
Raffinamento: L'agente utilizza il feedback di Lean 4 (tramite LSP/MCP) per colmare queste lacune. Fondamentalmente, se le riparazioni locali falliscono ripetutamente o se il predicato di collegamento si rivela troppo debole, l'agente identifica questo come un fallimento a livello di piano. Invece di oscillare tra l'editing del codice e quello della dimostrazione, l'agente torna alla fase di pianificazione per rivedere $\rho$ .

Questa separazione permette all'agente di distinguere tra errori di livello di elaborazione (riparabili localmente) ed errori di livello di piano (che richiedono un ripensamento strutturale), riducendo significativamente lo spazio di ricerca.

3. Benchmark: Lean4Commit0

Per valutare la generazione di codice verificato in contesti realistici oltre gli algoritmi da manuale, gli autori introducono Lean4Commit0.

Fonte: Derivato da 108 librerie open-source reali in Python, Rust, C/C++ e Java.
Ambito: Estrae le API core e ne codifica i comportamenti come task in Lean, inclusi i vincoli relazionali che limitano il comportamento congiunto di più funzioni (ad esempio, la coerenza tra le operazioni di set e get).
Controllo Qualità: Una pipeline a tre stadi garantisce la qualità della specifica:
1. Soddisfazione del Riferimento: Verifica che l'implementazione originale della libreria soddisfi la specifica in Lean.
2. Rifiuto della Mutazione: Assicura che la specifica rifiuti comportamenti alterati da mutazioni (per prevenire specifiche sotto-vincolate).
3. Revisione LLM: Segnala specifiche banali o irrilevanti.
Scala: Il benchmark finale contiene 511 placeholder di implementazione e 519 placeholder di teoremi.

4. Risultati Sperimentali

Gli autori hanno valutato P3 contro due baseline — un agente PLAIN (senza strategia specifica) e un agente SEQ (programma-poi-dimostrazione) — utilizzando quattro backend di modelli LLM di frontiera (Codex-GPT-5.5, Gemini-3-Pro, Claude-Sonnet-4.6, Claude-Opus-4.7) su tre benchmark: Verina, AlgoVeri e Lean4Commit0.

Tassi di Risoluzione: P3 ha ottenuto il tasso di risoluzione più alto in ogni configurazione (benchmark, modello).
- Rispetto alla baseline più forte, P3 ha migliorato i tassi di risoluzione di 4,6–11,2 punti percentuali.
- Sui subset più difficili dei benchmark, P3 ha ridotto i costi API per task fino a ~40% e il tempo di esecuzione fino a ~37%.
Studio di Ablazione: Un confronto con PLAN-SEQ (che pianifica le scelte di implementazione ma non la struttura della dimostrazione) ha mostrato che la pianificazione congiunta contribuisce specificamente a un ulteriore guadagno di 3,3–8,3 punti percentuali. Ciò isola il beneficio dell'anticipare la struttura della dimostrazione durante la fase di pianificazione.
Caso di Studio: In un compito di cancellazione di un albero rosso-nero bilanciato a sinistra, la baseline programma-poi-dimostrazione o falliva dopo aver generato 6.344 linee di codice o riusciva con invarianti di ricostruzione ridondanti (1.176 linee). P3, confrontando i piani prima di impegnarsi, ha risolto il compito in 1.105 linee.

5. Significato e Rivendicazioni

Il documento sostiene che P3 dimostra che la generazione di codice verificato può essere resa più efficace ed efficiente trattando il programma e la dimostrazione come artefatti co-progettati piuttosto che come output sequenziali.

Coerenza Strutturale: Stabilendo un piano strutturale condiviso, P3 assicura che l'implementazione e la dimostrazione siano coerenti "per costruzione", evitando la necessità di riconciliazione post-hoc.
Scalabilità al Codice Reale: L'introduzione di Lean4Commit0 colma il divario tra i benchmark accademici (algoritmi da manuale) e il software di produzione (vincoli API relazionali), mostrando che la pianificazione congiunta è particolarmente vantaggiosa per compiti complessi a livello di libreria.
Efficienza: Il framework riduce il comportamento di "oscillazione" (thrashing) comune nei cicli di riparazione iterativi, portando a significativi risparmi di risorse computazionali e tempo.

Gli autori concludono che, sebbene il verificatore (Lean 4) rimanga l'autorità finale, la capacità dell'agente di pianificare congiuntamente il programma e la dimostrazione aumenta significativamente la probabilità di produrre una soluzione verificata entro limiti di risorse pratici.