🤖 machine learning

VERITAS: Verifier-Guided Proof Search for Zero-Shot Formal Theorem Proving

Das Paper stellt VERITAS vor, ein Zero-Shot-Framework, das das formale Theorembeweisen verbessert, indem es reichhaltige Verifiersignale über ein zweiphasiges Best-of-N- und Critic-gesteuertes MCTS-Protokoll zurück in den Suchprozess leitet und damit State-of-the-Art-Leistung auf Benchmarks wie miniF2F und einem neuen Kombinatorik-Datensatz erzielt.

Ursprüngliche Autoren: Manish Acharya, Zhenyu Liao, Yueke Zhang, Kevin Leach, Yu Huang, Yifan Zhang

Veröffentlicht 2026-06-19

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Manish Acharya, Zhenyu Liao, Yueke Zhang, Kevin Leach, Yu Huang, Yifan Zhang

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

Stellen Sie sich vor, Sie versuchen, ein sehr schwieriges Rätsel zu lösen, wie zum Beispiel ein komplexes mathematisches Problem, aber Sie tun dies mit einem Team von KI-Assistenten. Normalerweise versuchen diese KI-Assistenten, ein Problem zu lösen, indem sie eine Lösung raten, prüfen, ob sie funktioniert, und wenn sie fehlschlägt, erhalten sie nur ein einfaches „Nein, versuch es nochmal“-Signal. Dabei werfen sie alle Details darüber weg, warum es fehlgeschlagen ist.

VERITAS ist ein neues System, das das Spiel verändert. Anstatt nur „Nein“ zu sagen, hört es auf die spezifischen Gründe, warum der Beweis fehlgeschklagen ist, und nutzt diese Gründe, um den nächsten Versuch zu leiten. Denken Sie an einen Detektiv, der nicht nur sagt: „Der Verdächtige ist unschuldig“, sondern sagt: „Der Verdächtige ist unschuldig, weil er um 17 Uhr im Geschäft war, also lass uns nach jemand anderem suchen, der auch im Geschäft war.“

So funktioniert VERITAS, unterteilt in einfache Teile:

1. Das Team aus vier Spezialisten

VERITAS verlässt sich nicht nur auf ein einzelnes KI-Gehirn. Es nutzt ein Team von vier spezialisierten „Agenten“, die miteinander kommunizieren:

Der Stratege: Bevor dieser Agent versucht, das Problem zu lösen, entscheidet er sich für einen übergeordneten Plan (z. B. „Lass uns versuchen, dies durch Fallunterscheidung aufzuteilen“ oder „Lass uns versuchen, es durch einen Widerspruchsbeweis zu führen“). Er schränkt die Suche ein, damit das Team keine Zeit mit schlechten Ideen verschwendet.
Der Retriever: Dieser Agent ist wie ein Bibliothekar. Er findet schnell die richtigen Referenzbücher (mathematische Regeln und Lemmata), die helfen könnten, den aktuellen Schritt zu lösen.
Der Taktiker: Dies ist der Hauptarbeiter. Er versucht, die eigentlichen Schritte des Beweises zu schreiben. Entscheidend ist, dass er eine Liste der gescheiterten Versuche aus der Vergangenheit betrachtet. Wenn ein vorheriger Versuch fehlschlug, weil eine falsche Bezeichnung für eine Regel verwendet wurde, wird dem Taktiker gesagt: „Verwende diesen Namen nicht noch einmal; hier ist die Fehlermeldung.“
Der Kritiker: Dieser Agent fungiert als Coach. Er beobtert den Fortschritt und sagt: „Du kommst dem Ziel näher“ oder „Du steuerst auf eine Sackgasse zu“, basierend auf dem spezifischen Feedback des Computers, der die Mathematik überprüft.

2. Der Zwei-Phasen-Schlachtplan

Das System spielt das Spiel in zwei unterschiedlichen Runden, um effizient zu sein:

Phase 1: Die „Schnelle Durchmusterung“ (Best-of-N)
Das Team macht 5 schnelle, unabhängige Vermutungen zur Lösung. Wenn eine davon funktioniert, großartig! Sie stoppen sofort. Das ist schnell und bewältigt die „einfachen“ Probleme.
Phase 2: Das „Tiefe Eintauchen“ (Kritiker-gesteuerte Suche)
Wenn die schnelle Durchmusterung fehlschlägt, wechselt das System in einen sorgfältigeren Modus. Es nimmt alle Fehler aus Phase 1 und speist sie als „negative Beispiele“ zurück in den Taktiker.
- Analogie: Stellen Sie sich vor, Sie versuchen, eine verschlossene Tür zu öffnen. In Phase 1 probieren Sie schnell 5 verschiedene Schlüssel aus. Keiner funktioniert. In Phase 2, anstatt einfach nur zufällige Schlüssel auszuprobieren, schauen Sie sich die 5 Schlüssel an, die im Schloss klemmten, notieren sich genau, wie sie klemmten, und nutzen diese Informationen, um einen neuen Schlüssel zu fertigen, der genau auf die Form des Schlosses passt.

3. Warum das wichtig ist: Das „Kombinatorik“-Problem

Das Paper testete dies an zwei Arten von mathematischen Problemen.

Standard-Mathematikprobleme: VERITAS löste mehr von diesen als bisherige Methoden (40,6 % gegenüber 36,9 %).
Kombinatorik (Zählprobleme): Hier glänzte VERITAS wirklich. In diesen Problemen muss man oft sehr spezifische, exakte Namen für mathematische Regeln verwenden.
- Das Problem: Standard-KI-Raten „halluziniert“ (erfindet) oft Namen für Regeln, die nicht existieren. Wenn eine KI einen erfundenen Regelnamen rät, sagt ein Standardsystem nur „Fehlgeschlagen“ und macht weiter.
- Die VERITAS-Lösung: Da VERITAS die spezifische Fehlermeldung liest („Unbekannte Konstante 'X'“), lernt es in Echtzeit, dass „X“ nicht existiert. Es korrigiert den Namen iterativ, bis es den echten findet.
- Ergebnis: Bei diesen schwierigen Zählproblemen wurde das Standard-Raten mit jedem Versuch eigentlich schlechter (weil es immer wieder gefälschte Namen erfand). VERITAS wurde hingegen besser, weil es aus seinen Fehlern lernte.

4. Die „Monotonie“-Garantie

Die Autoren haben sichergestellt, dass VERITAS eine bereits gefundene Lösung niemals verliert.

Die Garantie: Wenn die „Schnelle Durchmusterung“ (Phase 1) ein Problem löst, behält VERITAS diese Lösung bei und rührt sie nicht an. Das „Tiefe Eintauchen“ (Phase 2) arbeitet nur an den Problemen, die die erste Phase nicht lösen konnte.
Warum das wichtig ist: Dies beweist, dass jeder zusätzliche Erfolg, den VERITAS erzielt, spezifisch aus der intelligenten, feedbackgesteuerten Suche resultiert und nicht nur daraus, dass mehr zufällige Versuche unternommen wurden.

5. Der „Batch“-Trick

Einer der cleveren technischen Tricks im Paper ist die Art und Weise, wie die Antworten überprüft werden.

Alter Weg: Einen Versuch prüfen, warten, bis der Computer „Nein“ sagt, den nächsten prüfen, warten, den nächsten prüfen... Das ist langsam.
VERITAS-Weg: Sie packen 6 Versuche in eine einzige Datei und bitten den Computer, alle gleichzeitig zu prüfen. Dies macht das System etwa 10- bis 20-mal schneller, was viel Zeit und Geld spart.

Zusammenfassung

VERITAS ist ein System, das Fehlermeldungen des Computers nicht als „Stoppschild“, sondern als Landkarte betrachtet. Indem es die spezifischen Gründe liest, warum ein Beweis fehlschlug (Syntaxfehler, falsche Typen, fehlende Schritte), und diese Information in den nächsten Versuch der KI einspeist, kann es schwierige mathematische Probleme lösen, bei denen andere Systeme aufgeben würden. Es kombiniert einen schnellen „Versuch-und-sie-mal“-Ansatz mit einem intelligenten „Lernen-aus-Fehlern“-Ansatz, um die besten Ergebnisse zu erzielen.

Technisches Resümee: VERITAS: Verifier-Guided Proof Search for Zero-Shot Formal Theorem Proving

Problemstellung

Aktuelle auf Large Language Models (LLMs) basierende formale Theorembeweiser kollabieren die reichen, strukturierten Signale von formalen Verifizierern (wie Lean 4) typischerweise zu einem binären Pass/Fail-Ergebnis. Verifizierer liefern granulares Feedback, einschließlich Syntaxfehlern, Typ-Fehlpaarungen, teilweisem Fortschritt des Ziels und Beweisabschlussstatus. Diese Standard-Pipelines verwerfen jedoch diese intermediären Artefakte, indem sie sie zu skalaren Belohnungen zusammenfassen oder ganz ignorieren. Dies zwingt den Suchalgorithmus dazu, Informationen „neu zu lernen“, die der Verifizierer bereits explizit bereitgestellt hat – eine Einschränkung, die besonders kostspielig ist bei Beweisen, die Ketten abhängiger Taktiken erfordern, bei denen die Korrektheit jedes Schritts von der Auswirkung des vorherigen Schritts auf das Ziel abhängt.

Methodik: Das VERITAS-Framework

VERITAS ist ein Zero-Shot-Framework, das darauf ausgelegt ist, jedes Verifiersignal zurück in den Beweisgenerierungsprozess zu leiten. Es verwendet eine Vier-Agenten-Architektur, die durch einen gemeinsamen Beweisstatus und ein Zwei-Phasen-Suchprotokoll koordiniert wird.

1. Vier spezialisierte Agenten

Alle Agenten operieren auf einem gemeinsamen ProofState, der das Theorem, das aktuelle Ziel, Hypothesen, die Taktik-Historie und vier strukturierte Signale aus Lean enthält:

Strategist: Bildet den Beweisstatus auf eine von sechs High-Level-Strategien ab (direct, induction, contradiction, cases, rewrite, apply_lemma) und schätzt die Tiefe ein, um die Suche auf einen relevanten Unterraum zu beschränken.
Retriever: Liefert relevante Mathlib-Prämissen bereit, indem er die Keyword-Überlappung gegen Ziel-Token, Lemma-Namen und Signaturen bewertet.
Critic: Ein leichtgewichtiges Modell, das partielle Beweiszustände bewertet, nächste Taktiken vorschlägt und Pruning-Empfehlungen gibt. Er ersetzt zufällige Rollouts in MCTS durch eine Wertschätzung, die das Vier-Wege-Feedback von Lean integriert.
Tactician: Generiert $K$ Taktik-Kandidaten, die von der Strategie, den abgerufenen Prämissen, der Critic-Steuerung und entscheidend von einer Liste zuvor gescheiterter Taktiken mit deren spezifischen Lean-Fehlermeldungen als negative Beispiele abhängig sind.

2. Zwei-Phasen-Protokoll mit Monotonie-Garantie

Das Framework nutzt ein konservatives Zwei-Phasen-Protokoll, um sicherzustellen, dass Gewinne auf das Feedback-gesteuerte Suchen zurückzuführen sind:

Phase 1 (Best-of-N): Ein Standard Best-of-N Sweep (z. B. $N=5$ ) generiert Taktiken in einem einzigen Batch. Wenn irgendeine davon erfolgreich ist, wird das Theorem sofort gelöst.
Phase 2 (Critic-Guided MCTS): Wird nur aktiviert, wenn Phase 1 fehlschlägt. Die Fehler aus Phase 1 (Taktiken und deren Fehler) werden in den System-Prompt des Tacticians als negative Beispiele injiziert. Der Critic leitet eine Monte Carlo Tree Search (MCTS) an, bei der:
- Selection: Eine erweiterte UCB-Formel verwendet, die den Wert des Critics und die Strategie-Ausrichtung einbezieht.
- Expansion: Agenten laufen sequenziell ab; Kandidaten werden via eines Batched Lean Validation Tricks validiert.
- Simulation: Ersetzt zufällige Rollouts durch den Wert des Critics, ergänzt durch strukturierte Signale ( $\sigma_A$ Syntax, $\sigma_B$ Typ, $\sigma_C$ Fortschritt, $\sigma_D$ Abschluss).
- Backpropagation: Trägt die strukturierten Signale nach oben, anstatt sie zu einem binären Win/Loss zu kollabieren, wodurch die Kreditierung für Teilfortschritte erhalten bleibt.

Batched Lean Validation: Anstatt Lean $K$ -mal pro Expansion aufzurufen, werden die Kandidaten in eine einzige .lean-Datei als private Theoreme kompiliert und in einem einzigen Aufruf validiert. Dies reduziert die Verifizierungskosten von $O(K)$ auf $O(1)$ und liefert eine $\sim10\times$ Beschleunigung.

Monotonie: Das Protokoll garantiert, dass die endgültige Menge gelöster Theoreme eine Obermenge der durch Phase 1 allein gelösten Theoreme ist ( $S \supseteq S_1$ ). Dies isoliert den Beitrag von Phase 2 und stellt sicher, dass alle zusätzlichen Lösungen strikt auf die verifizierer-gesteuerte MCTS zurückzuführen sind.

Kernbeiträge

Zero-Shot Vier-Agenten-Framework: Ein System, das strukturiertes Lean-Feedback (Syntax, Typ, Fortschritt, Abschluss) in jede Generierungsentscheidung einspeist, ohne Trace-Fine-Tuning zu benötigen.
Zwei-Phasen-Protokoll: Ein Best-of-N $\to$ Critic-MCTS Design mit einer internen Monotonie-Garantie, die eine saubere Attribuierung der Suchbeiträge ermöglicht.
Effizienz-Optimierung: Ein Batched-Lean-Validation-Trick, der den Verifizierungsaufwand um etwa das Zehnfache reduziert.
VERITAS-CombiBench: Ein neuer Benchmark aus 55 autor-verifizierten, schweren Kombinatorik-Theoremen in Lean 4, der veröffentlicht wurde, um die Grenzen von ungesteuertem Sampling aufzuzeigen.
Attributionsanalyse: Empirische Belege dafür, dass 11 miniF2F-Theoreme ausschließlich durch die MCTS-Phase lösbar waren, was durch flaches Sampling nicht erreicht werden konnte.

Experimentelle Ergebnisse

Die Experimente wurden auf miniF2F (244 Theoreme) und VERITAS-CombiBench (55 Theoreme) durchgeführt.

miniF2F Performance: VERITAS erreichte eine Lösungsrate von 40,6 % (99/244) und übertraf damit einen unabhängigen Best-of-5 Baseline (36,9 %) sowie ein handgefertigtes Portfolio (26,2 %).
- Phase 2 trug 11 einzigartige Lösungen bei, die flaches Sampling nicht erreichen konnte, primär bei Problemen, die 2–4 abhängige Taktiken erfordern.
- Bei „harten“ Non-Sorry-Problemen erreichte VERITAS 28,9 % gegenüber 25,9 % für Best-of-5.
VERITAS-CombiBench Performance: Dieser Benchmark verdeutlichte das Versagen von ungesteuertem Sampling. Best-of-5 erreichte nur 1,8 % und fiel damit unter das Portfolio (3,6 %), da LLMs inkorrekte Namen von Mathlib-Lemmata halluzinierten. VERITAS erreichte 7,3 %, indem es diese Namen iterativ mithilfe des Lean-Fehlerfeedbacks korrigierte.
Effizienz: VERITAS dominiert die Pareto-Front für Inference-only Methoden und erreicht eine 40,6 % Lösungsrate mit ca. 27 Lean-Aufrufen pro Theorem zu API-Kosten von ~$150 pro Sweep.
Fehlermodi: Die Analyse zeigte, dass 32 % der Fehler auf der Syntax-Ebene lagen (halluzinierte Namen), 17 % typisch korrekt, aber inhaltlich falsch waren, und 10 % „Near-Misses“ (partialer Zielfortschritt) darstellten, bei denen der Critic hochgradig wertvolles Feedback hätte geben können.

Bedeutung und Behauptungen

Das Paper postuliert ein allgemeines Designprinzip: Wenn ein deterministischer Verifizierer strukturierte intermediäre Signale emittiert, verstärkt das Zurückführen dieser in die Generierung das LLM wesentlich stärker als zusätzliches Sampling allein.

VERITAS demonstriert, dass:

Verifier-Signale als Zustand: Deterministische Verifizierer-Signale als Inference-Zeit-Zustand dienen können, nicht nur als Endkontrolle.
Synergie der Komponenten: Die enge Kopplung des Verifizierers mit der Generierung ist effektiver als die Skalierung des LLMs oder der Suche isoliert.
Iterative Korrektur: Für Domänen, die präzise Lemma-Retrieval erfordern (wie Kombinatorik), ist die iterative Korrektur aus Verifizierer-Fehlern überlegen gegenüber flachem Sampling, welches dazu neigt, lexikalisch inkorrekte Namen zu halluzinieren.

Die Autoren kommen zu dem Schluss, dass VERITAS zwar kein Heilmittel für IMO-Level-Kreativität oder interaktive Latenz ist, sein primärer Beitrag aber im Routing liegt: Effizientes Sammeln einfacher Beweise in Phase 1 und gezieltes Einsatz des Rechenbudgets in Phase 2 dort, wo Verifizierer-Fehler die nächste Taktik führen können. Als zukünftige Arbeit wird die Verbesserung des Retrievals, die Schaffung billigerer Critics und die Destillation von Phase-2-Traces identifiziert, um dieses Prinzip auf den verbleibenden harten „Tail“ von Problemen zu skalieren.