💬 NLP

Scaling Natural-Language Graph-Based Test Time Compute for Automated Theorem Proving

Il documento introduce KG-prover, un nuovo framework che potenzia i modelli linguistici di grandi dimensioni a scopo generale con grafi della conoscenza estratti da testi matematici per migliorare la dimostrazione automatica di teoremi, dimostrando significativi miglioramenti delle prestazioni su più dataset senza richiedere ulteriore affinamento.

Autori originali: Vincent Li, Tim Knappe, Yule Fu, Kevin Han, Kevin Zhu

Pubblicato 2026-05-26

📖 4 min di lettura☕ Lettura da pausa caffè

CC BY 4.0

Autori originali: Vincent Li, Tim Knappe, Yule Fu, Kevin Han, Kevin Zhu

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

L'Idea Principale: Dare ai Modelli Matematici una "Briciola"

Immagina di dover risolvere un puzzle matematico molto difficile. Hai un amico super-intelligente (un Large Language Model, o LLM) che conosce molta matematica, ma a volte rimane bloccato perché non ricorda una regola specifica o non riesce a vedere come due idee diverse siano collegate.

Di solito, per rendere questi amici più intelligenti, devi rimandarli a scuola per anni di formazione (fine-tuning). Questo lavoro dice: "Nessun bisogno di scuola extra!" Invece, possiamo semplicemente dare loro una mappa migliore e una biblioteca migliore mentre lavorano al problema.

Gli autori hanno costruito un sistema chiamato KG-Prover. È come dare al tuo amico intelligente una gigantesca rete interconnessa di fatti matematici (un Knowledge Graph) e permettergli di "consultare" gli indizi giusti in tempo reale mentre cerca di risolvere il puzzle.

Come Funziona: L'Analogia del Detective

Pensa all'AI come a un detective che cerca di risolvere un crimine (il teorema matematico).

La Scena del Crimine (Il Problema): Al detective viene data un'affermazione che deve provare essere vera.
La Biblioteca (Il Knowledge Graph): Gli autori hanno costruito una biblioteca massiccia da ProofWiki (un sito web pieno di dimostrazioni matematiche). Hanno trasformato questa biblioteca in una gigantesca ragnatela in cui ogni concetto matematico è un nodo, e le linee che li collegano mostrano come si relazionano (ad esempio, "Il Teorema A usa la Definizione B").
L'Investigazione (La Ricerca):
- Invece di indovinare, il detective guarda la ragnatela.
- Parte dalla scena del crimine e chiede: "Chi è correlato a questo?"
- Segue le linee per trovare concetti simili, definizioni e dimostrazioni precedenti.
- Se rimane bloccato, non si arrende; va più a fondo nella ragnatela, seguendo più linee per trovare indizi nascosti. Questo è chiamato "scaling test-time compute" — fondamentalmente, spendere più tempo e sforzo durante l'investigazione per trovare la risposta.
La Bozza (Dimostrazione Informale): Il detective scrive una bozza grezza della soluzione in inglese semplice (linguaggio naturale), utilizzando gli indizi trovati.
La Traduzione (Formalizzazione): Un traduttore specializzato (un'altra AI) prende quella bozza in inglese e la trasforma in codice rigoroso e leggibile dal computer (Lean 4).
Il Giudice (Verifica): Un arbitro rigoroso controlla il codice. Se è sbagliato, il detective riceve un indizio su cosa è andato storto, torna alla ragnatela, trova un nuovo indizio e riprova.

Il "Trucco" che Funziona

Il lavoro afferma che, eseguendo questo processo di "ricerca e recupero", non hanno dovuto riaddestrare i modelli AI. Hanno semplicemente utilizzato modelli esistenti e generici (come GPT-4o-mini o Llama 3) e permesso loro di usare la mappa.

I Risultati:

Punteggi Migliori: Quando hanno aggiunto questa "mappa a ragnatela", il tasso di successo dell'AI sui problemi matematici è aumentato significativamente (dal 2% al 21% a seconda del test).
L'Effetto "Approfondimento": Più l'AI è stata autorizzata a cercare più a fondo nel grafico (seguendo più connessioni), meglio è riuscita a risolvere problemi difficili. È come dire: "Se non riesci a risolverlo in un minuto, prendine dieci e guarda ogni libro correlato in biblioteca".
Nessun Addestramento Extra: Il più grande successo è che non hanno dovuto spendere milioni di dollari per addestrare un nuovo modello. Hanno semplicemente dato ai vecchi modelli uno strumento migliore da usare mentre lavoravano.

I Limiti (Dove il Detective Rimane Bloccato)

Il lavoro è onesto su dove questo metodo fallisce:

Il Divario di Traduzione: A volte il detective scrive una spiegazione inglese perfetta, ma il traduttore sbaglia quando la trasforma in codice rigoroso. La logica matematica era corretta, ma la "grammatica" del linguaggio informatico era sbagliata.
Indizi Mancanti: Se la risposta richiede un fatto matematico molto oscuro che non è nella loro biblioteca (ProofWiki), il detective non riesce a trovarlo, non importa quanto a fondo cerchi.
Troppo Rumore: Se la ragnatela è troppo disordinata, il detective potrebbe confondersi con informazioni irrilevanti.

Sintesi

Questo lavoro introduce un modo per rendere gli esperti matematici AI più intelligenti senza riaddestrarli. È come dare a uno studente geniale uno smartphone con un'enciclopedia perfetta e interconnessa e dirgli: "Prenditi il tuo tempo, consulta ogni fatto correlato di cui hai bisogno e scrivi la dimostrazione". Consentendo all'AI di "pensare più a fondo" e cercare più a fondo nel suo knowledge graph durante il test, risolve più problemi correttamente.

Riepilogo Tecnico: Scalabilità del Calcolo al Momento dell'Esecuzione Basato su Grafi in Linguaggio Naturale per la Dimostrazione Automatica di Teoremi

Enunciato del Problema

Sebbene i Modelli Linguistici su Larga Scala (LLM) abbiano dimostrato capacità nel ragionamento logico multistep, la dimostrazione automatica di teoremi rimane una sfida. Ostacoli specifici includono l'identificazione accurata di concetti matematici chiave, la comprensione delle loro interrelazioni e la corretta formalizzazione delle dimostrazioni all'interno di sistemi in linguaggio naturale o formali. Gli approcci esistenti spesso si affidano a un fine-tuning intensivo, iterazioni esperte o all'addestramento su grandi volumi di dati formali (ad esempio Lean), il che può essere oneroso in termini di risorse e limitare la capacità del modello di sfruttare conoscenze matematiche più ampie e informali. Inoltre, gli approcci puramente formali potrebbero faticare con la flessibilità del ragionamento naturale, mentre gli approcci basati esclusivamente sul linguaggio naturale affrontano ambiguità nella traduzione verso sistemi di verifica formale.

Metodologia: KG-Prover

Gli autori introducono KG-Prover, un nuovo framework che potenzia gli LLM generici con un grafo della conoscenza (KG) estratto da testi matematici autorevoli (specificamente ProofWiki) per costruire e formalizzare dimostrazioni. Il sistema opera senza ulteriore fine-tuning dell'LLM di base, affidandosi invece alla scalabilità del calcolo al momento dell'esecuzione e alla generazione aumentata dal recupero.

Componenti Principali

Costruzione del Grafo della Conoscenza:
- Fonte: Il grafo è costruito analizzando ProofWiki, estraendo nodi da spazi dei nomi come "Definizione", "Assioma" e "Dimostrazione".
- Struttura: Ogni nodo rappresenta un'affermazione matematica autonoma (ad esempio, una proposizione di teorema o una definizione). Gli archi rappresentano i collegamenti ipertestuali presenti nel testo, catturando dipendenze e relazioni concettuali.
- Scala: Il grafo risultante contiene oltre 60.000 nodi e 300.000 archi.
- Embedding: I nodi sono arricchiti con vettori di embedding pre-calcolati (utilizzando text-embedding-3-large) per facilitare il recupero semantico.
Pipeline di Inferenza:
- Recupero e Navigazione: Data una proposizione $P$ , il sistema ne calcola l'embedding e recupera i nodi più simili (top- $k$ ). Se il tentativo iniziale di dimostrazione fallisce, il sistema espande iterativamente il contesto navigando nel grafo fino alla profondità $d$ , selezionando i top- $k$ vicini dei nodi precedentemente visitati.
- Generazione di Dimostrazioni Informali: L'LLM genera una dimostrazione informale in linguaggio naturale utilizzando il contesto recuperato. Questo sfrutta le capacità di ragionamento emergenti del modello e il vasto corpus di dimostrazioni informali disponibile nel KG.
- Autoformalizzazione: Un modello separato (DeepSeek-Prover-V1.5) traduce la dimostrazione informale in codice Lean 4.
- Verifica e Raffinamento: Il codice Lean generato viene verificato utilizzando il dimostratore di teoremi Lean 4. Se la verifica fallisce, i messaggi di errore vengono reimmessi nell'autoformalizzatore per il raffinamento. Se la dimostrazione fallisce ancora, il sistema può aumentare la profondità di navigazione del grafo o impiegare strategie di ricerca.
Strategie di Scalabilità (Calcolo al Momento dell'Esecuzione):
- Best-of-N: Il sistema genera $n$ dimostrazioni informali indipendenti, le autoformalizza e utilizza un modello "giudice" dedicato per valutarle in base a correttezza e chiarezza, selezionando il candidato con il punteggio più alto.
- Ricerca a Fascio (Beam Search): I candidati di dimostrazione sono organizzati in un fascio di larghezza $w$ . Ad ogni passo, i candidati vengono espansi in base al feedback del verificatore, valutati e i top- $k$ vengono mantenuti per la prossima iterazione. Questo bilancia l'esplorazione di percorsi di dimostrazione diversi con il raffinamento guidato dalla verifica.

Contributi Chiave

Framework KG-Prover: Un sistema che integra la generazione di dimostrazioni informali in linguaggio naturale con una navigazione iterativa basata su grafi della conoscenza e un meccanismo LLM-as-a-judge, eliminando la necessità di addestramento specializzato o iterazioni esperte.
Grafo della Conoscenza Matematica su Larga Scala: La costruzione di un grafo della conoscenza da ProofWiki con oltre 60.000 nodi e 300.000 archi, che modella relazioni complesse tra concetti matematici.
Sistema di Raffinamento Iterativo: Un meccanismo di valutazione euristica e ricerca a fascio che migliora le prestazioni fino al 26,4% rispetto alle linee di base e del 21,8% rispetto alle configurazioni KG-Prover senza scalabilità.
Dimostrazione della Scalabilità al Momento dell'Esecuzione: Evidenza che la modulazione della profondità di navigazione del grafo e l'impiego di strategie di ricerca (Best-of-N, Beam Search) aumentano significativamente le prestazioni senza riaddestrare i modelli sottostanti.

Risultati Sperimentali

Il framework è stato valutato su tre benchmark: miniF2F-test, ProofNet e MUSTARDSAUCE.

Miglioramenti delle Prestazioni:
- KG-Prover ha costantemente superato i sistemi di base e la Generazione Aumentata dal Recupero (RAG) standard su tutti i dataset.
- I miglioramenti sono variati dal 2% all'11% rispetto alle linee di base su più modelli (Llama 3.1 8B, GPT-4o, o1-mini, ecc.).
- Su miniF2F-test, gli LLM generici hanno migliorato le prestazioni fino al 21% quando combinati con KG-Prover.
- La configurazione di KG-Prover con o4-mini ha raggiunto un tasso di superamento del 50% su miniF2F-test.
- Nella configurazione di scalabilità più elevata, i miglioramenti hanno raggiunto il 26,4% rispetto alle linee di base.
Effetti della Scalabilità:
- Profondità di Navigazione: L'accuratezza è aumentata con una maggiore profondità di navigazione ( $r$ ), in particolare per modelli con parametri più piccoli come Llama 3.1 8B. I primi incrementi di profondità hanno prodotto i guadagni più significativi.
- Strategie di Ricerca: La combinazione del KG con Beam Search e campionamento Best-of-N ha ulteriormente migliorato l'accuratezza, raggiungendo fino al 10,75% su ProofNet e al 50,40% su MUSTARDSAUCE.
- Modelli Fine-tuned: Anche quando applicato a modelli già fine-tuned per Lean (ad esempio TheoremLlama, DeepSeek-Prover-V1.5), KG-Prover ha fornito ulteriori guadagni di prestazioni (ad esempio, +1,85% rispetto a una linea di base fine-tuned su miniF2F).

Significato e Affermazioni

Il documento sostiene che KG-Prover offre un approccio promettente e scalabile alla dimostrazione automatica di teoremi che non richiede ulteriore fine-tuning o iterazioni esperte intensive. Sfruttando le capacità di ragionamento in linguaggio naturale integrate negli LLM generici e potenziandole con informazioni strutturate recuperate tramite grafi, il framework colma efficacemente il divario tra ragionamento informale e verifica formale.

Gli autori sottolineano che questo metodo permette ai modelli fondazionali esistenti di raggiungere prestazioni paragonabili o superiori a quelle di sistemi specializzati e fine-tuned, semplicemente iniettando concetti correlati durante l'inferenza. Il lavoro evidenzia il potenziale della scalabilità del calcolo al momento dell'esecuzione — modulando la profondità di navigazione del grafo e impiegando strategie di ricerca — come alternativa valida alla scalabilità dei parametri del modello per compiti di ragionamento complesso. Sebbene l'approccio introduca sfide nel passaggio di traduzione da informale a formale, il sistema a due agenti (generazione + autoformalizzazione) supportato dal recupero tramite grafo mitiga con successo questi problemi, fornendo tracce di ragionamento interpretabili e nuove strategie per la generazione di dimostrazioni.