💬 NLP

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

Die Arbeit stellt KG-prover vor, ein neuartiges Framework, das allgemeine Large Language Models durch aus mathematischen Texten extrahierte Wissensgraphen erweitert, um das automatisierte Theorembeweisen zu verbessern, und zeigt signifikante Leistungssteigerungen über mehrere Datensätze hinweg, ohne dass zusätzliche Feinabstimmung erforderlich ist.

Ursprüngliche Autoren: Vincent Li, Tim Knappe, Yule Fu, Kevin Han, Kevin Zhu

Veröffentlicht 2026-05-26

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Vincent Li, Tim Knappe, Yule Fu, Kevin Han, Kevin Zhu

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Die große Idee: Mathematikmodellen einen „Spickzettel" geben

Stellen Sie sich vor, Sie versuchen, ein sehr schwieriges mathematisches Rätsel zu lösen. Sie haben einen superklugen Freund (ein Large Language Model, oder LLM), der viel von Mathematik versteht, aber manchmal stecken bleibt, weil er sich eine bestimmte Regel nicht merken kann oder nicht sieht, wie zwei verschiedene Ideen zusammenhängen.

Normalerweise muss man diese Freunde, um sie schlauer zu machen, jahrelang zur Schule schicken (Feinabstimmung). Dieses Papier sagt: „Kein Bedarf für zusätzliche Schule!" Stattdessen können wir ihnen einfach eine bessere Karte und eine bessere Bibliothek während sie an dem Problem arbeiten, zur Verfügung stellen.

Die Autoren bauten ein System namens KG-Prover. Es ist, als würde man seinem klugen Freund ein riesiges, vernetztes Netz mathematischer Fakten (ein Wissensgraph) geben und ihm erlauben, während er versucht, das Rätsel zu lösen, in Echtzeit die richtigen Hinweise nachzuschlagen.

Wie es funktioniert: Die Detektiv-Analogie

Stellen Sie sich die KI als Detektiv vor, der ein Verbrechen aufklären muss (den mathematischen Satz).

Der Tatort (Das Problem): Dem Detektiv wird eine Aussage gegeben, die er beweisen muss, dass sie wahr ist.
Die Bibliothek (Der Wissensgraph): Die Autoren bauten eine massive Bibliothek aus ProofWiki (eine Website voller mathematischer Beweise). Sie verwandelten diese Bibliothek in ein riesiges Spinnennetz, bei dem jedes mathematische Konzept ein Knoten ist und die Linien, die sie verbinden, zeigen, wie sie zusammenhängen (z. B. „Satz A verwendet Definition B").
Die Ermittlung (Die Suche):
- Anstatt zu raten, betrachtet der Detektiv das Spinnennetz.
- Er startet am Tatort und fragt: „Wer ist damit verbunden?"
- Er folgt den Linien, um ähnliche Konzepte, Definitionen und frühere Beweise zu finden.
- Wenn er feststeckt, gibt er nicht auf; er geht tiefer ins Netz, folgt weiteren Linien, um versteckte Hinweise zu finden. Dies wird als „Scaling test-time compute" bezeichnet – im Grunde mehr Zeit und Aufwand während der Ermittlung zu investieren, um die Antwort zu finden.
Der Entwurf (Informeller Beweis): Der Detektiv schreibt einen rohen Entwurf der Lösung in einfachem Englisch (natürliche Sprache), unter Verwendung der Hinweise, die er fand.
Die Übersetzung (Formalisierung): Ein spezialisierter Übersetzer (eine andere KI) nimmt diesen englischen Entwurf und verwandelt ihn in strikten, computerlesbaren Code (Lean 4).
Der Richter (Verifikation): Ein strenger Schiedsrichter prüft den Code. Wenn er falsch ist, erhält der Detektiv einen Hinweis darüber, was schiefgelaufen ist, kehrt zum Spinnennetz zurück, findet einen neuen Hinweis und versucht es erneut.

Der „Spickzettel", der funktioniert

Das Papier behauptet, dass sie durch diesen „Suchen und Abrufen"-Prozess die KI-Modelle nicht neu trainieren mussten. Sie verwendeten einfach bestehende, allgemeine Modelle (wie GPT-4o-mini oder Llama 3) und ließen sie die Karte nutzen.

Die Ergebnisse:

Bessere Scores: Als sie diese „Spinnennetz-Karte" hinzufügten, stieg die Erfolgsrate der KI bei mathematischen Problemen signifikant (je nach Test um 2 % bis 21 %).
Der „Deep Dive"-Effekt: Je tiefer die KI erlaubt wurde, in den Graphen einzutauchen (mehr Verbindungen zu verfolgen), desto besser wurde sie darin, schwierige Probleme zu lösen. Es ist, als würde man sagen: „Wenn Sie es nicht in einer Minute lösen können, nehmen Sie sich zehn Minuten Zeit und schauen Sie jedes verwandte Buch in der Bibliothek durch."
Kein zusätzliches Training: Der größte Gewinn ist, dass sie nicht Millionen von Dollar für das Training eines neuen Modells ausgeben mussten. Sie gaben den alten Modellen einfach ein besseres Werkzeug, das sie während ihrer Arbeit nutzen konnten.

Die Grenzen (Wo der Detektiv stecken bleibt)

Das Papier ist ehrlich darüber, wo diese Methode versagt:

Die Übersetzungslücke: Manchmal schreibt der Detektiv eine perfekte englische Erklärung, aber der Übersetzer macht Fehler, wenn er sie in strikten Code verwandelt. Die mathematische Logik war richtig, aber die „Grammatik" der Computersprache war falsch.
Fehlende Hinweise: Wenn die Antwort eine sehr obskure mathematische Tatsache erfordert, die nicht in ihrer Bibliothek (ProofWiki) enthalten ist, kann der Detektiv sie nicht finden, egal wie tief er sucht.
Zu viel Rauschen: Wenn das Spinnennetz zu unordentlich ist, könnte der Detektiv durch irrelevante Informationen verwirrt werden.

Zusammenfassung

Dieses Papier stellt eine Methode vor, um KI-Mathematikexperten schlauer zu machen, ohne sie neu zu trainieren. Es ist, als würde man einem genialen Schüler ein Smartphone mit einer perfekten, vernetzten Enzyklopädie geben und ihm sagen: „Nehmen Sie sich Zeit, schlagen Sie jeden benötigten verwandten Fakt nach und schreiben Sie den Beweis." Indem man der KI erlaubt, während des Tests „schärfer zu denken" und tiefer in ihren Wissensgraphen zu suchen, löst sie mehr Probleme korrekt.

Technische Zusammenfassung: Skalierung von testzeitbasiertem Compute für graphbasierte natürliche Sprache im automatisierten Beweisen von Theoremen

Problemstellung

Während Large Language Models (LLMs) Fähigkeiten im mehrstufigen logischen Schlussfolgern unter Beweis gestellt haben, bleibt das automatisierte Beweisen von Theoremen eine Herausforderung. Spezifische Hürden umfassen die genaue Identifizierung zentraler mathematischer Konzepte, das Verständnis ihrer wechselseitigen Beziehungen sowie die korrekte Formalisierung von Beweisen innerhalb natürlicher Sprache oder formaler Systeme. Bestehende Ansätze verlassen sich häufig auf intensive Feinabstimmung, Experteniterationen oder das Training mit großen Mengen formaler Daten (z. B. Lean), was ressourcenintensiv sein kann und die Fähigkeit des Modells einschränkt, breiteres, informelles mathematisches Wissen zu nutzen. Darüber hinaus können rein formale Ansätze mit der Flexibilität natürlichen Schlussfolgerns Schwierigkeiten haben, während rein auf natürlicher Sprache basierende Ansätze bei der Übersetzung in formale Verifikationssysteme mit Mehrdeutigkeiten konfrontiert sind.

Methodik: KG-Prover

Die Autoren stellen KG-Prover vor, ein neuartiges Framework, das allgemeine LLMs durch einen Wissensgraphen (KG) erweitert, der aus seriösen mathematischen Texten (speziell ProofWiki) extrahiert wurde, um Beweise zu konstruieren und zu formalisieren. Das System arbeitet ohne zusätzliche Feinabstimmung des Basis-LLMs und setzt stattdessen auf Skalierung des Compute-Aufwands zur Laufzeit sowie retrieval-gestützte Generierung.

Kernkomponenten

Konstruktion des Wissensgraphen:
- Quelle: Der Graph wird durch Parsen von ProofWiki erstellt, wobei Knoten aus Namensräumen wie „Definition", „Axiom" und „Beweis" extrahiert werden.
- Struktur: Jeder Knoten repräsentiert eine in sich geschlossene mathematische Aussage (z. B. eine Theoremaussage oder Definition). Kanten repräsentieren im Text gefundene Hyperlinks und erfassen Abhängigkeiten sowie konzeptionelle Beziehungen.
- Skala: Der resultierende Graph enthält über 60.000 Knoten und 300.000 Kanten.
- Embeddings: Knoten werden mit voraufbereiteten Embedding-Vektoren (unter Verwendung von text-embedding-3-large) angereichert, um semantische Retrieval-Prozesse zu erleichtern.
Inferenz-Pipeline:
- Retrieval & Traversierung: Gegeben eine Aussage $P$ berechnet das System deren Embedding und ruft die top- $k$ ähnlichsten Knoten ab. Falls der initiale Beweisversuch fehlschlägt, erweitert das System den Kontext iterativ durch Traversierung des Graphen bis zur Tiefe $d$ , wobei die top- $k$ Nachbarn der zuvor besuchten Knoten ausgewählt werden.
- Generierung informeller Beweise: Das LLM generiert einen informellen Beweis in natürlicher Sprache unter Verwendung des abgerufenen Kontexts. Dies nutzt die emergenten Schlussfolgerungsfähigkeiten des Modells sowie das breite Korpus informeller Beweise, das im KG verfügbar ist.
- Autoformalisierung: Ein separates Modell (DeepSeek-Prover-V1.5) übersetzt den informellen Beweis in Lean-4-Code.
- Verifikation & Verfeinerung: Der generierte Lean-Code wird mit dem Lean-4-Theorembeweiser verifiziert. Falls die Verifikation fehlschlägt, werden Fehlermeldungen an den Autoformalisierer zurückgespeist, um eine Verfeinerung vorzunehmen. Falls der Beweis weiterhin fehlschlägt, kann das System die Traversierungstiefe des Graphen erhöhen oder Suchstrategien einsetzen.
Skalierungsstrategien (Test-Time Compute):
- Best-of-N: Das System generiert $n$ unabhängige informelle Beweise, formalisiert diese automatisch und verwendet ein dediziertes „Judge"-Modell, um sie basierend auf Korrektheit und Klarheit zu bewerten und den Kandidaten mit der höchsten Punktzahl auszuwählen.
- Beam Search: Beweis-Kandidaten werden in einem Beam der Breite $w$ organisiert. In jedem Schritt werden Kandidaten basierend auf Feedback des Verifizierers erweitert, bewertet und die top- $k$ für die nächste Iteration beibehalten. Dies balanciert die Exploration diverser Beweispfade mit einer verifikationsgesteuerten Verfeinerung.

Hauptbeiträge

KG-Prover-Framework: Ein System, das die Generierung informeller Beweise in natürlicher Sprache mit einer iterativen, wissensgraphbasierten Traversierung und einem LLM-as-a-Judge-Mechanismus integriert und damit die Notwendigkeit spezialisierter Trainings oder Experteniterationen eliminiert.
Großskaliger mathematischer KG: Die Konstruktion eines Wissensgraphen aus ProofWiki mit über 60.000 Knoten und 300.000 Kanten, der komplexe Beziehungen zwischen mathematischen Konzepten modelliert.
System zur iterativen Verfeinerung: Ein heuristisches Bewertungs- und Beam-Search-Mechanismus, der die Leistung um bis zu 26,4 % gegenüber Baselines und um 21,8 % gegenüber nicht-skalierten KG-Prover-Konfigurationen verbessert.
Demonstration der Test-Time-Skalierung: Nachweise, dass die Modulation der Traversierungstiefe des Graphen und der Einsatz von Suchstrategien (Best-of-N, Beam Search) die Leistung signifikant steigern, ohne die zugrundeliegenden Modelle neu zu trainieren.

Experimentelle Ergebnisse

Das Framework wurde an drei Benchmarks evaluiert: miniF2F-test, ProofNet und MUSTARDSAUCE.

Leistungssteigerungen:
- KG-Prover übertraf Baselinesysteme und standardmäßige Retrieval-Augmented Generation (RAG) konsistent über alle Datensätze hinweg.
- Die Verbesserungen lagen zwischen 2 % und 11 % gegenüber Baselines über mehrere Modelle hinweg (Llama 3.1 8B, GPT-4o, o1-mini, etc.).
- Auf miniF2F-test verbesserten sich allgemeine LLMs um bis zu 21 %, wenn sie mit KG-Prover kombiniert wurden.
- Die Konfiguration von KG-Prover mit o4-mini erreichte eine **50 %**ige Bestehensquote auf miniF2F-test.
- In der höchsten Skalierungskonfiguration erreichten die Verbesserungen 26,4 % gegenüber Baselines.
Skalierungseffekte:
- Traversierungstiefe: Die Genauigkeit stieg mit zunehmender Traversierungstiefe ( $r$ ), insbesondere für kleinere Parametermodelle wie Llama 3.1 8B. Die ersten few Erhöhungen der Tiefe erbrachten die signifikantesten Gewinne.
- Suchstrategien: Die Kombination des KG mit Beam Search und Best-of-N-Sampling verbesserte die Genauigkeit weiter und erreichte bis zu 10,75 % auf ProofNet und 50,40 % auf MUSTARDSAUCE.
- Feinabgestimmte Modelle: Selbst bei Anwendung auf Modelle, die bereits für Lean feinabgestimmt wurden (z. B. TheoremLlama, DeepSeek-Prover-V1.5), lieferte KG-Prover zusätzliche Leistungssteigerungen (z. B. +1,85 % gegenüber einer feinabgestimmten Baseline auf miniF2F).

Bedeutung und Behauptungen

Die Arbeit postuliert, dass KG-Prover einen vielversprechenden, skalierbaren Ansatz für das automatisierte Beweisen von Theoremen bietet, der keine zusätzliche Feinabstimmung oder intensive Experteniteration erfordert. Durch die Nutzung der eingebauten Schlussfolgerungsfähigkeiten in natürlicher Sprache allgemeiner LLMs und deren Ergänzung durch strukturierte, graph-retrieval-basierte Informationen überbrückt das Framework effektiv die Lücke zwischen informellem Schlussfolgern und formaler Verifikation.

Die Autoren betonen, dass diese Methode es bestehenden Foundation-Modellen ermöglicht, eine Leistung zu erzielen, die der spezialisierter, feinabgestimmter Systeme entspricht oder diese übertrifft, indem sie einfach während der Inferenz verwandte Konzepte injiziert. Die Arbeit unterstreicht das Potenzial von Test-Time-Compute-Skalierung – durch Modulation der Traversierungstiefe des Graphen und Einsatz von Suchstrategien – als viable Alternative zur Skalierung von Modellparametern für komplexe Schlussfolgerungsaufgaben. Obwohl der Ansatz Herausforderungen im Schritt der Übersetzung von informell zu formal mit sich bringt, mildert das Zwei-Agenten-System (Generierung + Autoformalisierung), unterstützt durch Graph-Retrieval, diese Probleme erfolgreich und liefert interpretierbare Schlussfolgerungsspuren sowie neue Strategien zur Beweisgenerierung.