Diversifying to Verify: When Task-Equivalent Programs Differ in Verifiability
Dit artikel introduceert Diversify2Verify, een op LLM gebaseerde pipeline die laat zien hoe het genereren van diverse, taakequivalente programma-implementaties de succesratio van automatische verificatie aanzienlijk verbetert door varianten te identificeren die beter geschikt zijn voor formeel bewijs.
Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer
Stel je voor dat je een robot probeert te bouwen die een wiskundige puzzel kan oplossen. Je hebt een superintelligente AI-assistent (een Large Language Model) die erg goed is in het schrijven van code. Meestal vragen we de AI: "Schrijf code die deze puzzel oplost," en we controleren of de robot een paar testruns doorstaat. Als hij slaagt, zeggen we: "Goed gedaan!"
Maar in de wereld van formele verificatie is het passeren van een paar tests niet genoeg. Het is alsof je een brug bouwt en er alleen een speelgoedautootje overheen rijdt. Om echt veilig te zijn, heb je een wiskundig bewijs nodig dat de brug elke auto kan dragen, elke keer, onder elke omstandigheid. Dit is wat het papier "deductieve verificatie" noemt.
Het probleem? De AI de opdracht geven om niet alleen correcte code te schrijven, maar ook code die makkelijk te bewijzen is, is ontzettend moeilijk. Soms schrijft de AI een oplossing die perfect werkt, maar die zo slordig of vreemd gestructureerd is dat de "bewijscontroleur" (een tool genaamd Why3) in de war raakt en het niet kan verifiëren.
Het Grote Idee: Probeer Niet Slechts Eén Manier
De auteurs, Shirley Yu en Ruben Martins, stelden een simpele vraag: Wat als we niet alleen om één oplossing vragen, maar om veel verschillende versies van diezelfde oplossing?
Denk aan het proberen te openen van een hardnekkige pot.
- Versie A: Je probeert de deksel met je rechterhand te draaien.
- Versie B: Je probeert de deksel met je linkerhand te draaien.
- Versie C: Je probeert op de deksel te tikken met een lepel.
- Versie D: Je probeert de deksel onder warm water te houden.
Misschien is de "draai met de rechterhand" (de eerste code die de AI schrijft) te glad voor de bewijscontroleur om grip op te krijgen. Maar de "draai met de linkerhand" heeft misschien een vorm die perfect past bij de logica van de controleur. Het papier noemt dit Diversify2Verify. In plaats van te hopen op één perfecte code, genereren ze vier verschillende "smaken" van dezelfde taak:
- Array + Imperatief: Zoals het één voor één door een rij mensen lopen om hun namen te controleren.
- Array + Recursief: Zoals een spelletje "telefoontje" waarbij je de taak doorgeeft aan een reeks helpers.
- List + Imperatief: Zoals het doorbladeren van een stapel indexkaarten.
- List + Recursief: Zoals een Russische matroesjka-pop waarbij elke pop de volgende stap bevat.
Het Experiment: 73 Puzzels, 292 Pogingen
Het team bouwde een speciale speeltuin met 73 verschillende programmeerpuzzels (voornamelijk gericht op getallen, lijsten en arrays). Voor elke puzzel vroegen ze de AI om alle vier de "smaken" te genereren. Dat leverde 292 verschillende code-pogingen op om te testen.
Ze lieten de AI niet zomaar code schrijven; ze stelden een strikt driefasenproces op:
- Fase 1 (Het Contract): Eerst lieten ze de AI een "contract" (een formele regelset) schrijven die beschrijft wat de code moet doen, zonder zich zorgen te maken over hoe het gebeurt. Ze controleerden deze regelset tegen voorbeelden om er zeker van te zijn dat deze klopte. Zodra een regelset was geaccepteerd, werd deze bevroren. Er mochten geen regels meer worden gewijzigd!
- Fase 2 (De Code): Vervolgens vroegen ze de AI om de eigenlijke code voor elk van de vier smaken te schrijven, waarbij ze ervoor zorgden dat deze aan enkele basis testruns voldeed.
- Fase 3 (Het Bewijs): Ten slotte probeerden ze te bewijzen dat elke codeversie aan de bevroren regelset voldeed. Als het bewijs faalde, gaven ze de AI een hint (een "reparatie") om het bewijs te herstellen, maar alleen het bewijs, niet de code of de regels.
De Resultaten: Diversiteit Wint
Dit is wat er gebeurde toen ze de cijfers bekeken:
- De "One-Shot" Mislukking: Als je simpelweg de eerste code zou nemen die de AI schreef en probeerde te bewijzen, slaagde slechts 96 van de 292 (ongeveer 32,9%). Dat is minder dan één op de drie!
- De Kracht van Reparatie: Wanneer ze de AI twee keer lieten proberen het bewijs te herstellen, steeg het aantal naar 154 van de 292 (ongeveer 52,7%).
- De Kracht van Diversiteit (De Echte Winnaar): Wanneer ze naar de 73 puzzels als geheel keken, ontdekten ze dat voor 49 van hen (een succespercentage van 67,1%), ten minste één van de vier verschillende versies correct bewezen kon worden.
Dit is de belangrijkste bevinding: Taak-equivalente implementaties kunnen aanzienlijk verschillen in verifieerbaarheid. Met andere woorden: twee stukken code die exact hetzelfde doen, kunnen mijlenver uit elkaar liggen in hoe makkelijk ze te bewijzen zijn.
Wat Ze Uitgesloten Hebben (Wat het NIET is)
Het paper is zeer voorzichtig over wat het niet claimt:
- Het gaat niet over betere code: Ze hebben niet gevonden dat "Arrays beter zijn dan Lists" of "Recursie beter is dan Loops". Sterker nog, de resultaten waren gemengd. Recursieve code was over het algemeen makkelijker te bewijzen dan imperatieve (loop-gebaseerde) code, maar arrays en lists presteerden overall vergelijkbaar. De sleutel was niet het kiezen van de "beste" stijl, maar het hebben van opties.
- Het gaat niet over het veranderen van de regels: Ze verboden de AI strikt om het "contract" (het doel) te wijzigen tijdens de reparatiefase. Als de AI probeerde het doel te veranderen om het bewijs makkelijker te maken, werd dat als een fout beschouwd. Ze wilden het oorspronkelijke doel bewijzen, niet een zwakkere versie daarvan.
- Het is geen wondermiddel voor alles: De studie keek alleen naar puzzels met betrekking tot gehele getallen, arrays en lijsten. Ze beweren niet dat dit werkt voor drijvende komma's, complexe 3D-graphics of programma's die communiceren met het internet.
Hoe Zeker Zijn Ze?
De auteurs zijn zelfverzekerd over hun metingen, maar voorzichtig over het grotere plaatje.
- Gemeten: Ze hebben harde cijfers. Ze hebben de tools gedraaid, de successen geteld en gezien dat diversiteit het succespercentage verhoogde van 32,9% naar 52,7% voor individuele artefacten, en naar 67,1% voor taken.
- Gesuggereerd: Ze suggereren dat de reden dat imperatieve code (loops) moeilijker te bewijzen was, komt doordat dit "loop invarianten" vereist (regels over wat er binnen een loop gebeurt), die lastig automatisch door AI te verzinnen zijn. Ze vermoeden dat als je de AI betere hulpmiddelen geeft om deze regels te raden, het gat gedicht kan worden.
- Niet bewezen (Nog): Ze geven toe dat ze niet bewezen hebben dat het "Array Contract" en het "List Contract" wiskundig identiek zijn. Ze gingen er simpelweg vanuit dat ze hetzelfde betekenen op basis van de taakbeschrijving. Ze merken ook op dat hun "rechter" (een AI die controleert of de regels overeenkomen met de puzzel) geen perfect menselijke expert is, dus een paar subtiele foutjes zouden erdoorheen geglipt kunnen zijn.
De Kernboodschap
Het paper suggereert dat wanneer we een AI vragen om "geverifieerde" software te schrijven, we niet alleen om één antwoord moeten vragen en dan maar hopen op het beste. In plaats daarvan moeten we vragen om een menu aan opties. Door verschillende manieren te genereren om hetzelfde probleem op te lossen, vergroten we de kans dat we de versie vinden die de bewijscontroleur daadwerkelijk kan begrijpen.
Het is als het zoeken naar een sleutel die in een slot past. Als je maar één sleutel hebt, kun je vast komen te zitten. Maar als je een hele ring met sleutels hebt, waarbij ze allemaal dezelfde deur openen, is de kans groot dat er eentje tussen zit die perfect in het slot past.
Verdrinkt u in papers in uw vakgebied?
Ontvang dagelijkse digests van de nieuwste papers die bij uw onderzoekswoorden passen — met technische samenvattingen, in uw taal.