Stellen Sie sich vor, Sie bringen einem superintelligenten Roboter bei, eine Geschichte zu schreiben. Sie geben dem Roboter einen Prompt, und er spuckt eine Erzählung aus. Aber hier ist der Haken: Sie wollen nicht nur eine Geschichte; Sie wollen eine Geschichte, die mathematisch garantiert wahr ist, ohne Logikfehler, ohne Magie, die die Gesetze der Physik bricht, und ohne Charaktere, die ohne Erklärung verschwinden. Dies ist die Welt der verifizierten Codegenerierung. Es ist ein Bereich der Informatik, in dem wir Künstliche Intelligenz nicht nur bitten, Software zu schreiben, sondern Software, die ihr eigenes „Beweis der Korrektheit“ mitliefert – ein mathematisches Zertifikat, das sagt: „Ich verspreche, dass dieser Code genau das tun wird, was ich gesagt habe, für jede erdenkliche Situation.“

Lange Zeit war die Standardmethode dafür wie ein zweistufiger Tanz: Zuerst schreibt der Roboter den Code (die Geschichte), und dann versucht ein separates Team von Roboter-Lektoren zu prüfen, ob die Geschichte Sinn ergibt. Wenn die Lektoren einen Logikfehler finden, schicken sie die Geschichte zurück an den Autor, damit dieser sie korrigiert. Der Autor flickt die Geschichte aus, schickt sie zurück, und der Zyklus wiederholt sich. Aber dieses Papier legt nahe, dass dieser „Schreiben-dann-Prüfen“-Tanz oft umständlich und ineffizient ist. Es ist, als würde man versuchen, eine Brücke zu bauen, und erst nachdem sie fertiggestellt wurde, feststellen, dass man vergessen hat, die Stützbalken einzusetzen, was dazu führt, dass man sie abreißen und neu aufbauen muss. Die Autoren dieses Papers schlagen einen neuen Weg vor: Anstatt den Code und den Beweis separat zu schreiben, sollte der Roboter die gesamte Brücke planen – sowohl die Fahrbahn als auch die Stützen – und gleichzeitig sicherstellen, dass sie von der ersten Skizze an perfekt zusammenpassen.

Das Problem: Die „Schreiben-dann-Prüfen“-Falle

Das Paper mit dem Titel „Joint Program-and-Proof Planning for Verified Code Generation“ befasst sich mit einem frustrierenden Flaschenhals in der Art und Weise, wie KI verifizierte Software schreibt. Derzeit folgen die meisten Systeme einem „Programm-dann-Beweis“-Workflow. Es ist, als würde man einen Koch bitten, eine komplexe Mahlzeit zuzubereiten, und ihn dann, nachdem das Essen auf dem Tisch steht, einen Lebensmittelkritiker fragen, ob er beweisen kann, dass die Zutaten frisch waren und die Kochmethode sicher war. Wenn der Kritiker ein Problem findet (wie etwa unterkochtes Hähnchen), muss der Koch zurückgehen, das Gericht neu kochen und hoffen, dass es dem Kritiker diesmal gefällt.

Die Autoren argumentieren, dass dieser sequentielle Ansatz fehlerhaft ist. Wenn die KI sich dazu entscheidet, zuerst den Code zu schreiben, wählt sie vielleicht eine Struktur, die oberflächlich betrachtet gut aussieht, aber ein Albtraum zu beweisen ist. Stellen Sie sich vor, die KI schreibt ein Programm, um die größte Zahl in einer Liste zu finden. Sie könnte eine Methode wählen, die kurz und knackig zu schreiben ist, aber eine unglaublich komplexe, verborgene mathematische Regel erfordert, um ihre Korrektheit zu beweisen. Soblich der Code geschrieben ist, steckt die KI fest: Sie muss entweder einen superkomplexen Beweis für diesen spezifischen Code erfinden oder den Code zerreißen und von vorne beginnen. Dies führt zu viel verschwendeter Zeit, Geld und „Reparatur-Schleifen“, in denen die KI versucht, den Code und den Beweis immer wieder zu flicken, sie aber nie ganz zusammenpassen.

Die Lösung: P3 (Der „Hand-in-Hand“-Planer)

Um dies zu beheben, führen die Forscher P3 ein, einen neuen Workflow, bei dem die KI wie ein Meisterarchitekt agiert, der den Entwurf für das Gebäude und die Sicherheitsinspektion zeichnet, bevor sie den ersten Stein legt.

Anstatt direkt mit dem Schreiben des Codes zu beginnen, erstellt P3 zuerst einen gemeinsamen Plan. Dieser Plan ist eine hochgradige Skizze, die zwei Fragen gleichzeitig beantwortet:

1. Wie wird der Code funktionieren? (Der „Programmentwurf“)
2. Wie werden wir beweisen, dass er funktioniert? (Der „Beweisentwurf“)

Der Plan legt die Struktur der Lösung fest. Er wählt die richtige „Form“ für den Code (wie die Entscheidung zwischen einer rekursiven Schleife oder einem Fold) und wählt gleichzeitig die passenden mathematischen Regeln (Invarianten), die nötig sind, um diese Form als sicher zu beweisen. Es ist wie die Entscheidung: „Wir werden eine Brücke mit Hängekabeln bauen, also muss unser Beweisplan die Prüfung der Spannung dieser Kabel beinhalten.“

Sob[ie der gemeinsame Plan feststeht, „elaboriert“ die KI die Details. Sie schreibt den eigentlichen Code und den eigentlichen Beweis, aber sie füllt dabei nur die Lücken eines bereits vereinbarten Bauplans aus. Wenn der Beweis fehlschlägt, weiß die KI genau, wo sie suchen muss, da die Struktur bereits festgelegt wurde. Wenn der Plan selbst schlecht ist (z. B. das Brückendesign ist unmöglich), kehrt die KI zur Planungsphase zurück, um den Entwurf neu zu zeichnen, anstatt verzweifelt das fertige Gebäude zu flicken.

Das neue Testfeld: Lean4Commit0

Den Autoren wurde klar, dass bisherige Tests für diese KI-Systeme zu einfach waren, als würde man den Roboter bitten, mathematische Rätsel aus einem Lehrbuch zu lösen. Echte Software ist chaotischer. Um ihre neue Methode angemessen zu testen, haben sie einen neuen Benchmark namens Lean4Commit0 entwickelt.

Sie haben 108 reale Open-Source-Softwarebibliotheken (geschrieben in Python, Rust, C/C++ und Java) durchsucht und deren Kernfunktionen in „verifizierte Code“-Herausforderungen umgewandelt. Anstatt einfacher Aufgaben wie „addiere zwei Zahlen“ beinhalten diese Herausforderungen komplexe Beziehungen zwischen verschiedenen Teilen eines Programms. In einem Konfigurationssystem könnten sie beispielsweise die KI bitten zu beweisen, dass „wenn man eine Einstellung auf 'Hoch' setzt und später auf 'Niedrig' ändert, das System sich korrekt an die Einstellung 'Niedrig' erinnert“. Diese Aufgaben erfordern, dass die KI versteht, wie verschiedene Funktionen miteinander kommunizieren, was sie viel schwieriger macht als Lehrbuchprobleme.

Was sie herausfanden: Schlaues Planen gewinnt

Das Team testete P3 gegen vier der leistungsfähigsten verfügbaren KI-Modelle (einschließlich Versionen von Codex, Gemini und Claude) über drei verschiedene Benchmarks hinweg: Verina, AlgoVeri und ihr neues Lean4Commit0.

Die Ergebnisse waren eindeutig: Gemeinsames Planen funktioniert besser als separates Schreiben.

• Erfolgsrate: P3 löste mehr Aufgaben als jede andere Methode in jedem einzelnen Test. Bei den schwierigsten Aufgaben verbesserte es die Erfolgsrate im Vergleich zu den besten bestehenden Methoden um 4,6 bis 11,2 Prozentpunkte.
• Effizienz: Es ging nicht nur darum, mehr Probleme zu lösen; es ging darum, sie schneller und günstiger zu lösen. Bei schwierigen Aufgaben reduzierte P3 die Kosten für API-Aufrufe um bis zu 40 % und senkte die Zeitspanne um bis zu 37 %. Dies liegt daran, dass die KI keine Zeit damit verschwendet hat, unmögliche Dinge zu beweisen oder Code neu zu schreiben, der strukturell falsch war.
• Der „Joint“-Vorteil: Um zu beweisen, dass das „gemeinsame Planen“ das Geheimrezept war, führten sie einen Test durch, bei dem die KI den Code plante, aber den Beweis nicht im Voraus plante. Diese „Code-only-Planung“-Methode schnitt schlechter ab als P3, was bestätigte, dass das Denken über den Beweis während der Planung des Codes der entscheidende Unterschied ist.

Ein Praxisbeispiel: Der Rot-Schwarz-Baum

Um zu zeigen, wie dies in der Praxis funktioniert, betrachteten die Autoren ein klassisches Informatikproblem: das Löschen eines Knotens aus einem „Rot-Schwarz-Baum“ (einer komplexen Datenstruktur, die zur effizienten Organisation von Daten verwendet wird).

• Der alte Weg (Programm-dann-Beweis): Die KI legte sich auf eine bestimmte Art und Weise fest, den Knoten zu löschen. Es stellte sich heraus, dass dieser Weg strukturell so unordentlich war, dass der Beweis über 6.300 Zeilen Code benötigte, nur um die Lücken zu schließen, oder er scheiterte gänzlich.
• Der P3-Weg: Die KI plante zuerst die Löschung. Sie erkannte, dass ein anderer struktureller Ansatz einfacher zu beweisen wäre. Sie hielt sich an diesen Plan und löste das Problem in nur 1.105 Zeilen.

Warum das wichtig ist

Dieses Paper legt nahe, dass wir für die Entwicklung wirklich zuverlässiger Software aufhören müssen, „Code“ und „Beweis“ als zwei getrennte Aufgaben zu behandeln. Indem wir die KI zwingen, über die mathematische Sicherheit des Codes nachzudenken, während sie den Code selbst entwirft, erhalten wir Software, die nicht nur durch Konstruktion korrekt ist, sondern auch kostengünstiger und schneller zu produzieren ist. Es ist ein Wechsel von „später reparieren“ zu „beim ersten Mal richtig bauen“, um sicherzustellen, dass die Software, auf die wir uns verlassen, so solide ist wie die Mathematik, die ihre Korrektheit beweist.