🤖 machine learning

Quokka: Accelerating Program Verification with LLMs via Invariant Synthesis

Die Arbeit stellt Quokka vor, ein evalutionsorientiertes Framework, das große Sprachmodelle nutzt, um durch direkte Validierung generierter Schleifeninvarianten die Programmvérifikation effizienter zu gestalten und dabei den Stand der Technik zu übertreffen.

Ursprüngliche Autoren: Anjiang Wei, Tianran Sun, Tarun Suresh, Haoze Wu, Ke Wang, Alex Aiken

Veröffentlicht 2026-04-03

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Anjiang Wei, Tianran Sun, Tarun Suresh, Haoze Wu, Ke Wang, Alex Aiken

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

Das Problem: Der verlorene Schlüssel im Labyrinth

Stellen Sie sich vor, Sie müssen ein riesiges, sich ständig wiederholendes Labyrinth (ein Computerprogramm mit einer Schleife) überprüfen, um sicherzustellen, dass am Ende alles sicher ist. Ein Computer-Verifizierer (ein strenger Prüfer) versucht, das Labyrinth zu durchlaufen, um zu beweisen, dass es keine Fallen gibt.

Das Problem ist: Das Labyrinth ist so groß und komplex, dass der Prüfer oft stundenlang herumirrt und die Geduld verliert, bevor er das Ziel erreicht. Er braucht einen Schlüssel – eine Regel, die ihm sagt: „Hey, an dieser Stelle im Labyrinth ist immer alles in Ordnung, egal wie oft du hier herumläufst."

In der Informatik nennen wir diese Regel eine Invariante.

Ein schwacher Schlüssel sagt nur: „Hier ist es hell." Das hilft dem Prüfer kaum, er läuft trotzdem weiter.
Ein starker Schlüssel sagt: „Hier ist es hell, und du bist immer genau 3 Schritte von der Wand entfernt." Das ist mächtig! Damit kann der Prüfer sofort sehen, dass er sicher ist, und spart enorm viel Zeit.

Bisher war es extrem schwer, diese starken Schlüssel automatisch zu finden.

Die alte Lösung: Der mühsame Handwerker

Frühere Versuche, Künstliche Intelligenz (LLMs) zu nutzen, waren wie ein mühsamer Handwerker, der einen Haufen roher Steine (die Antworten der KI) bekommt. Die KI schreit oft Unsinn oder halbfertige Ideen heraus. Der Handwerker muss dann:

Die Steine sortieren.
Die kaputten reparieren.
Sie mit Kleber (komplexen Algorithmen) wieder zusammenfügen.
Hoffen, dass das Gebäude steht.

Das war langsam, kompliziert und oft fehleranfällig. Die Forscher fragten sich: „Müssen wir wirklich so viel Kleber und Reparaturarbeit machen, wenn die KI eigentlich schon schlau genug ist?"

Die neue Lösung: Quokka – Der direkte Prüfer

Das Team um Anjiang Wei hat Quokka entwickelt. Der Name kommt von dem niedlichen, schnellen Tier, das für Geschwindigkeit steht.

Wie Quokka funktioniert (Die Analogie):
Statt die KI-Antworten wie einen Haufen roher Steine zu behandeln, behandelt Quokka sie wie Vorschläge für einen neuen Schlüssel.

Der Vorschlag: Die KI (z. B. ein großes Sprachmodell) schreit einen Schlüssel aus: „Vielleicht ist die Regel: Die Zahl ist immer durch 7 teilbar."
Der direkte Test: Quokka nimmt diesen Schlüssel und steckt ihn sofort in das Schloss des Verifizierers.
- Funktioniert der Schlüssel? (Ist die Regel wahr?)
- Hilft der Schlüssel, das Ziel zu erreichen? (Können wir damit beweisen, dass das Programm sicher ist?)
Das Ergebnis:
- Wenn ja: Super! Das Programm ist in Sekundenbruchteilen verifiziert.
- Wenn nein: Nächster Versuch! Wir werfen den Schlüssel weg und probieren einen anderen aus.

Quokka repariert nichts. Es schmiert keinen Kleber. Es fragt einfach: „Hilft das?" Wenn ja, großartig. Wenn nein, weiter. Das macht den Prozess unglaublich schnell und sauber.

Was haben die Forscher herausgefunden?

Die KI wird besser: Wenn man die KI speziell trainiert (sie mit vielen Beispielen von richtigen Schlüsseln füttert) und ihr erlaubt, mehrere Vorschläge gleichzeitig zu machen und den besten auszuwählen („Best-of-N"), wird sie deutlich besser. Sie findet die starken Schlüssel häufiger.
Einfachheit schlägt Komplexität: Quokka ist schneller und besser als alle vorherigen Systeme, die versucht haben, die KI-Antworten kompliziert zu reparieren. Es zeigt, dass wir nicht mehr so viel „Reparaturarbeit" brauchen, wenn die KI gut genug ist.
Ein neuer Maßstab: Die Forscher haben einen riesigen Testkoffer mit 866 verschiedenen Labyrinthen gebaut, um zu testen, welche KI am besten ist. Sie haben gezeigt, dass die besten Modelle (wie GPT-5 oder Claude) bereits jetzt viel schneller verifizieren können als die alten Methoden.

Zusammenfassung

Stellen Sie sich vor, Sie suchen nach dem Weg aus einem Labyrinth.

Die alten Methoden waren wie ein Architekt, der versucht, die Vorschläge eines verrückten Genies zu verstehen, zu korrigieren und in einen Bauplan zu verwandeln.
Quokka ist wie ein mutiger Abenteurer, der einfach sagt: „Hier ist ein Vorschlag von der KI. Probieren wir ihn sofort aus. Wenn er funktioniert, rennen wir los. Wenn nicht, nehmen wir den nächsten."

Das Ergebnis: Programme werden schneller und sicherer überprüft, und wir müssen weniger Zeit mit komplizierten Reparaturen verschwenden. Quokka macht die KI zu einem echten Turbo für die Software-Sicherheit.

1. Problemstellung

Die formale Programmverifikation zielt darauf ab, Software korrekt und fehlerfrei zu garantieren, was besonders in sicherheitskritischen Bereichen essenziell ist. Ein zentrales und seit Jahrzehnten ungelöstes Problem ist die automatische Synthese von Schleifeninvarianten (Loop Invariants).

Herausforderung: Schleifeninvarianten sind Bedingungen, die vor, während und nach jeder Iteration einer Schleife gelten. Um Verifikationsaufgaben zu beschleunigen, müssen diese Invarianten nicht nur korrekt, sondern auch stark genug sein, um die Zielbehauptung (Assertion) zu beweisen. Schwache, aber korrekte Invarianten (z. B. $x > 0$ ) helfen dem Verifizierer wenig, während starke Invarianten (z. B. $x \equiv 3 \pmod 7$ ) den Suchraum drastisch reduzieren und die Verifikationszeit verkürzen.
Limitationen bestehender Ansätze: Frühere Arbeiten, die Large Language Models (LLMs) zur Invariantenfindung nutzten, hatten zwei Hauptmängel:
1. Sie prüften oft nur die Korrektheit der Invarianten (z. B. durch Vergleich mit dynamischen Analyse-Tools wie Daikon), nicht aber deren Stärke oder ihren tatsächlichen Nutzen für die Verifikation.
2. Sie behandelten LLM-Ausgaben als „raues" symbolisches Material, das komplexe Nachbearbeitungsschritte (Filtern, Kombinieren, Reparieren, Backtracking) erforderte, bevor sie verwendet werden konnten.

2. Methodik: Das Quokka-Framework

Quokka ist ein bewertungsorientiertes Framework, das einen Paradigmenwechsel darstellt: Statt LLM-Ausgaben algorithmisch zu reparieren, wird direkt evaluiert, ob eine generierte Invariante die Verifikation beschleunigt.

Verifizierer-basierter Ansatz: Quokka nutzt einen formalen Verifizierer (im Paper UAutomizer) als einzige Instanz zur Validierung.
Der Evaluierungs-Workflow: Für ein gegebenes Programm $P$ $P$ und eine Zielbehauptung $p^*$ $p^{*}$ schlägt das LLM eine Kandidaten-Invariante $q$ $q$ vor. Quokka führt zwei parallele Verifizierungsabfragen durch:
1. Korrektheitsprüfung ( $d_a$ ): Ist $q$ eine gültige Invariante für $P$ ? (Prüfung ohne Annahmen).
2. Nutzungsprüfung ( $d_b$ ): Hält die Zielbehauptung $p^*$ unter der Annahme, dass $q$ wahr ist? (Prüfung mit $q$ als assume-Anweisung).
Entscheidungslogik:
- Wenn $q$ korrekt ist und $p^*$ unter $q$ bewiesen werden kann, ist die Verifikation erfolgreich und beschleunigt.
- Wenn $q$ falsch ist oder $p^*$ nicht bewiesen werden kann, wird dies als Misserfolg gewertet.
- Das System verzichtet auf komplexe Heuristiken zur Reparatur von Invarianten. Stattdessen wird die „Stärke" der Invariante direkt durch die Beschleunigung der Verifikation gemessen.
Training und Sampling:
- Fine-Tuning: Es wurde ein Datensatz von 3.589 synthetischen Programmen erstellt, die durch Verifizierer gefiltert wurden, um hochwertige Ground-Truth-Invarianten zu erhalten. Daraufhin wurde ein Modell (Qwen2.5-7B) mittels LoRA (Low-Rank Adaptation) feinabgestimmt.
- Best-of-N Sampling: Es werden $N$ Kandidaten generiert, und derjenige wird ausgewählt, der die schnellste Verifikationszeit liefert.

3. Wichtige Beiträge

Quokka-Framework: Einführung eines einfachen, aber sounden (korrekten) Evaluierungsansatzes, der LLM-Ausgaben direkt als Beweis-Kandidaten validiert, anstatt sie durch komplexe symbolische Pipelines zu reparieren.
Benchmark-Datensatz: Erstellung eines umfangreichen Benchmarks mit 866 Instanzen aus dem SV-COMP (Software Verification Competition). Dieser Datensatz ist deutlich komplexer als frühere Benchmarks (enthält mehrere Schleifen, Funktionen, Arrays und Zeiger) und ermöglicht eine differenzierte Bewertung von LLM-Fähigkeiten.
Umfassende Evaluation: Evaluation von 9 State-of-the-Art LLMs (inkl. GPT-5, Claude, Qwen, Llama) über verschiedene Modellfamilien hinweg.
Techniken zur Leistungssteigerung: Demonstration, dass sowohl Supervised Fine-Tuning als auch Best-of-N Sampling messbare Verbesserungen bei der Beschleunigung der Verifikation erzielen.

4. Ergebnisse

Leistungsüberlegenheit: Quokka übertrifft alle bisherigen LLM-basierten Verifizierer (wie LaM4Inv, Clause2Inv, LEMUR, Loopy) konsistent. Auf dem Benchmark wurden signifikant mehr Instanzen gelöst und die durchschnittliche Lösungszeit drastisch reduziert.
- Beispiel: Mit dem Modell gpt-5.2 und Best-of-8 Sampling wurden unter einem 60-Sekunden-Timeout 25 zusätzliche Instanzen gelöst (im Vergleich zum Basis-Verifizierer), während frühere Methoden oft nur 0–1 zusätzliche Instanzen lösten.
Modellvergleich: Größere und leistungsfähigere Modelle (z. B. gpt-5.2, Claude Opus) generieren deutlich mehr korrekte und starke Invarianten als kleinere Modelle.
Effizienz von Fine-Tuning: Das Fine-Tuning von Qwen2.5-7B führte zu einer Steigerung der korrekten Invarianten von 419 auf 431 und löste mehr zusätzliche Instanzen.
Best-of-N: Die Leistung steigt mit der Anzahl der Samples ( $N$ ) bis zu $N=8$ , danach flacht die Kurve aufgrund von Ressourcenkonkurrenz ab.
Fehleranalyse: Die meisten Fehler (Timeouts) traten nicht wegen falscher Invarianten auf, sondern weil die Verifizierungsabfragen selbst zu komplex waren. Viele LLMs generierten jedoch Invarianten, die der Zielbehauptung zu ähnlich waren (keine echte Dekomposition des Problems).

5. Bedeutung und Fazit

Das Paper zeigt, dass LLMs das Potenzial haben, die Programmverifikation erheblich zu beschleunigen, wenn der Fokus von der „Reparatur" von LLM-Ausgaben auf eine direkte, verifizierer-gestützte Bewertung ihrer Nützlichkeit gelegt wird.

Paradigmenwechsel: Quokka beweist, dass komplexe Algorithmen zur Kombination und Filterung von Invarianten oft unnötig sind, wenn die Modelle leistungsfähig genug sind. Ein einfacherer, evaluiert-zentrierter Ansatz ist effektiver.
Neuer State-of-the-Art: Quokka setzt einen neuen Standard für LLM-basierte Programmverifikation und bietet eine fundierte Basis für zukünftige Forschung.
Praktische Relevanz: Durch die Nutzung von Parallelisierung und der direkten Validierung gegen den Zielbeweis wird die Latenz reduziert, was LLMs zu einem praktikablen Werkzeug für die automatische Verifikation komplexer Software macht.

Die Code- und Datengrundlagen sind öffentlich verfügbar, was die Reproduzierbarkeit und Weiterentwicklung des Feldes fördert.