Diversifying to Verify: When Task-Equivalent Programs Differ in Verifiability
Dieses Paper führt Diversify2Verify ein, eine auf LLMs basierende Pipeline, die demonstriert, wie das Generieren diverser, aufgabenäquivalenter Programmimplementierungen die Erfolgsraten der automatisierten Verifizierung signifikant verbessert, indem Varianten identifiziert werden, die besser für den formalen Beweis geeignet sind.
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, einen Roboter zu bauen, der ein mathematisches Rätsel lösen kann. Sie haben einen superintelligenten KI-Assistenten (ein Large Language Model), der großartig darin ist, Code zu schreiben. Normalerweise fragen wir die KI: „Schreibe Code, der dieses Rätsel löst“, und prüfen, ob der Roboter ein paar Testläufe besteht. Wenn er besteht, sagen wir: „Gut gemacht!“
Aber in der Welt der formalen Verifikation reicht es nicht aus, nur ein paar Tests zu bestehen. Es ist, als würde man eine Brücke bauen und nur ein Spielzeugauto darüber fahren lassen. Um wirklich sicher zu sein, benötigt man einen mathematischen Beweis, dass die Brücke jedes Auto, zu jeder Zeit und unter jeder Bedingung tragen wird. Das ist das, was das Paper als „deduktive Verifikation“ bezeichnet.
Das Problem? Die KI dazu zu bringen, Code zu schreiben, der nicht nur korrekt, sondern auch leicht zu beweisen ist, ist unglaublich schwer. Manchmal schreibt die KI eine Lösung, die perfekt funktioniert, aber so unordentlich oder seltsam strukturiert ist, dass der „Proof Checker“ (ein Werkzeug namens Why3) verwirrt wird und sie nicht verifizieren kann.
Die große Idee: Versuche nicht nur einen Weg
Die Autoren, Shirley Yu und Ruben Martins, stellten eine einfache Frage: Was wäre, wenn wir nicht nur nach einer Lösung fragen, sondern nach vielen verschiedenen Versionen derselben Lösung?
Denken Sie an den Versuch, ein hartnäckiges Glas zu öffnen:
- Version A: Sie versuchen, den Deckel mit der rechten Hand zu drehen.
- Version B: Sie versuchen, ihn mit der linken Hand zu drehen.
- Version C: Sie versuchen, mit einem Löffel gegen den Deckel zu klopfen.
- Version D: Sie versuchen, ihn unter heißes Wasser zu halten.
Vielleicht ist der „Rechtsdreher“ (der erste Code, den die KI schreibt) zu glatt, damit der Proof Checker ihn greifen kann. Aber der „Linksdreher“ hat vielleicht eine Form, die perfekt in die Logik des Checkers passt. Das Paper nennt dies Diversify2Verify. Anstatt auf einen perfekten Code zu hoffen, generieren sie vier verschiedene „Geschmacksrichtungen“ derselben Aufgabe:
- Array + Imperativ: Wie das Durchgehen einer Schlange von Menschen, wobei man einen nach dem anderen prüft.
- Array + Rekursiv: Wie ein Spiel von „Stille Post“, bei dem man die Aufgabe an eine Reihe von Helfern weitergibt.
- List + Imperativ: Wie das Durchblättern eines Stapels Karteikarten.
- List + Rekursiv: Wie eine Matroschka-Puppe, bei der jede Puppe den nächsten Schritt in sich enthält.
Das Experiment: 73 Rätsel, 292 Versuche
Das Team baute einen speziellen Spielplatz mit 73 verschiedenen Programmierrätseln (hauptsächlich mit Zahlen, Listen und Arrays). Für jedes Rätsel baten sie die KI, alle vier dieser „Geschmacksrichtungen“ zu generieren. Das ergab 292 verschiedene Code-Versuche zum Testen.
Sie ließen die KI nicht einfach nur Code schreiben; sie richteten einen strengen dreistufigen Prozess ein:
- Stufe 1 (Der Kontrakt): Zuerst ließen sie die KI einen „Kontrakt“ (eine formale Regel) schreiben, der beschreibt, was der Code tun muss, ohne sich darum zu kümmern, wie er es tut. Sie prüften dieses Regelwerk anhand von Beispielen, um sicherzustellen, dass es Sinn ergibt. Sobald ein Regelwerk akzeptiert wurde, wurde es eingefroren. Es durften keine Regeln mehr geändert werden!
- Stufe 2 (Der Code): Als Nächstes baten sie die KI, den eigentlichen Code für jede der vier Geschmacksrichtungen zu schreiben, wobei sichergestellt wurde, dass er einige grundlegende Testläufe besteht.
- Stufe 3 (Der Beweis): Schließlich versuchten sie zu beweisen, dass jede Code-Version das eingefrorene Regelwerk erfüllt. Falls der Beweis fehlschlug, gaben sie der KI einen Hinweis (eine „Reparatur“), um den Beweis zu korrigieren, aber nur den Beweis, nicht den Code oder die Regeln.
Die Ergebnisse: Vielfalt gewinnt
Hier ist, was geschah, als sie die Zahlen auswerteten:
- Das „One-Shot“-Versagen: Wenn man einfach den ersten Code nahm, den die KI schrieb, und versuchte, ihn zu beweisen, funktionierten nur 96 von 292 (etwa 32,9 %). Das ist weniger als eins von drei!
- Die Kraft der Reparatur: Als sie der KI erlaubten, die Beweise zweimal zu korrigieren, sprang die Zahl auf 154 von 292 (etwa 52,7 %).
- Die Kraft der Diversität (Der wahre Gewinner): Wenn sie die 73 Rätsel als Ganzes betrachteten, stellten sie fest, dass für 49 von ihnen (eine Erfolgsquote von 67,1 %) mindestens eine der vier verschiedenen Versionen korrekt bewiesen werden konnte.
Dies ist die Hauptfindung: Aufgabenäquivalente Implementierungen können sich in ihrer Verifizierbarkeit erheblich unterscheiden. Mit anderen Worten: Zwei Code-Stücke, die exakt dasselbe tun, können in der Art und Weise, wie leicht sie zu beweisen sind, Welten voneinander entfernt sein.
Was sie ausschlossen (Was es NICHT ist)
Das Paper ist sehr vorsichtig mit dem, was es nicht behauptet:
- Es geht nicht um besseren Code: Sie fanden nicht heraus, dass „Arrays besser als Listen sind“ oder „Rekursion besser als Schleifen ist“. Tatsächlich waren die Ergebnisse gemischt. Rekursiver Code war im Allgemeinen leichter zu beweisen als imperativer (schleifenbasierter) Code, aber Arrays und Listen schnitten insgesamt ähnlich ab. Der Schlüssel war nicht, den „besten“ Stil zu wählen, sondern Optionen zu haben.
- Es geht nicht um das Ändern der Regeln: Sie untersagten der KI strikt, den „Kontrakt“ (das Ziel) während der Reparaturphase zu ändern. Wenn die KI versuchte, das Ziel zu ändern, um den Beweis zu erleichtern, galt dies als Fehlschlag. Sie wollten das ursprüngliche Ziel beweisen, nicht ein schwächeres.
- Es ist kein Allheilmittel für alles: Die Studie untersuchte nur Rätsel, die ganze Zahlen, Arrays und Listen betrafen. Sie behaupten nicht, dass dies auch für Gleitkommazahlen, komplexe 3D-Grafiken oder Programme, die mit dem Internet kommunizieren, funktioniert.
Wie sicher sind sie?
Die Autoren sind sich ihrer Messungen bewusst, bleiben aber vorsichtig in Bezug auf das Gesamtbild.
- Gemessen: Sie haben harte Zahlen. Sie ließen die Werkzeuge laufen, zählten die Erfolge und sahen, dass die Diversität die Erfolgsquote von 32,9 % auf 52,7 % für einzelne Artefakte und auf 67,1 % für Aufgaben steigerte.
- Suggeriert: Sie vermuten, dass der Grund, warum imperativer Code (Schleifen) schwieriger zu beweisen war, darin liegt, dass er „Schleifeninvarianten“ (Regeln darüber, was innerhalb einer Schleife passiert) erfordert, die eine KI nur schwer automatisch erfinden kann. Sie vermuten, dass sich die Lücke schließen würde, wenn man der KI bessere Werkzeuge zur Vermutung dieser Regeln gäbe.
- Nicht bewiesen (noch nicht): Sie geben zu, dass sie nicht bewiesen haben, dass der „Array-Kontrakt“ und der „List-Kontrakt“ mathematisch identisch sind. Sie haben lediglich angenommen, dass sie aufgrund der Aufgabenbeschreibung dasselbe bedeuten. Sie merken auch an, dass ihr „Richter“ (eine KI, die prüft, ob die Regeln zum Rätsel passen) kein perfekter menschlicher Experte ist, sodass einige subtile Fehler durchgeschlüpft sein könnten.
Das Fazit
Das Paper legt nahe, dass wir, wenn wir eine KI bitten, „verifizierte“ Software zu schreiben, nicht einfach nur nach einer Antwort fragen und auf das Beste hoffen sollten. Stattdessen sollten wir nach einem Menü an Optionen fragen. Indem wir verschiedene Wege generieren, um dasselbe Problem zu lösen, erhöhen wir unsere Chancen, genau die Version zu finden, die der Proof Checker tatsächlich verstehen kann.
Es ist wie der Versuch, einen Schlüssel zu finden, der in ein Schloss passt. Wenn man nur einen einzigen Schlüssel hat, kommt man vielleicht nicht weiter. Aber wenn man einen ganzen Schlüsselring hat, selbst wenn alle dieselbe Tür öffnen sollen, ist die Wahrscheinlichkeit hoch, dass einer davon perfekt in das Schloss passt.
Ertrinken Sie in Arbeiten in Ihrem Fachgebiet?
Erhalten Sie tägliche Digests der neuesten Arbeiten passend zu Ihren Forschungsbegriffen — mit technischen Zusammenfassungen, in Ihrer Sprache.