🤖 machine learning

Synthesis and Verification of Transformer Programs (Technical Report)

Dit artikel presenteert nieuwe algoritmische technieken voor het automatisch verifiëren en leren van C-RASP-programma's—taalconstructies die de expressiviteit van transformers vastleggen—door gebruik te maken van connecties met Lustre-modelcontrole en lokale zoektochten, waardoor toepassingen mogelijk worden gemaakt in transformer-programma-optimalisatie en beperkt leren.

Oorspronkelijke auteurs: Hongjian Jiang, Matthew Hague, Philipp Rümmer, Anthony Widjaja Lin

Gepubliceerd 2026-05-19

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Hongjian Jiang, Matthew Hague, Philipp Rümmer, Anthony Widjaja Lin

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 zeer slimme, krachtige robot hebt (een "Transformer") die verhalen kan lezen, e-mails kan schrijven en puzzels kan oplossen. Deze robot is ongelooflijk goed in zijn werk, maar is ook een beetje een "black box". Je kunt zien wat hij doet, maar je kunt niet gemakkelijk zien hoe hij denkt of bewijzen dat hij nooit een specifieke fout zal maken.

Dit artikel introduceert een nieuwe manier om een blauwdruk voor deze robots te bouwen. In plaats van te proberen het rommelige, complexe brein van de robot direct te begrijpen, hebben de auteurs een eenvoudigere, schonere taal ontwikkeld die C-RASP heet. Denk aan C-RASP als een "vereenvoudigde handleiding" die de robot volgt. Het is simpel genoeg om te lezen, te begrijpen en op fouten te controleren, maar krachtig genoeg om precies te beschrijven wat de robot doet.

Hier is de uiteenzetting van hun twee belangrijkste prestaties, uitgelegd met alledaagse analogieën:

1. De "Veiligheidsinspecteur" (Verificatie)

Het Probleem: Je hebt een C-RASP-handleiding (een programma) en je wilt weten: "Doet dit programma altijd het juiste ding? Neemt het ooit een slecht woord aan of wijst het een goed woord af?" Dit handmatig controleren is als proberen een boek van een miljoen pagina's te lezen om een enkele typefout te vinden; het is bijna onmogelijk en soms wiskundig onmogelijk om 100% zeker te zijn.

De Oplossing: De auteurs bouwden een "Veiligheidsinspecteur". Zij bedachten hoe ze deze C-RASP-handleidingen konden vertalen naar een andere, zeer strenge taal die Lustre heet.

De Analogie: Stel je voor dat je een complex recept hebt dat in een rommelig, handgeschreven notitieboekje staat (C-RASP). Je kunt de rekenkunde niet gemakkelijk controleren. Vertaal daarom dat rommelige recept naar een stijve, door de computer leesbare indeling (Lustre) die een supersnelle robot (een "Model Checker") direct kan lezen.
Het Resultaat: Deze robot kan het recept direct scannen en zeggen: "Ja, dit is veilig," of "Nee, hier is de exacte stap waar het misgaat." Het artikel toont aan dat dit ongelooflijk snel werkt (in seconden) in vergelijking met het trainen van een nieuwe AI-robot, wat uren kan duren.

2. De "Auto-Editor" (Synthese)

Het Probleem: Stel je hebt een lijst met voorbeelden (bijvoorbeeld: "Dit zijn goede zinnen, dit zijn slechte") en je wilt een C-RASP-handleiding schrijven die hierbij past. Je hebt de handleiding nog niet; je moet deze vanaf nul uitvinden.

De Oplossing: De auteurs creëerden een "Auto-Editor" die een techniek gebruikt die Simulated Annealing heet.

De Analogie: Stel je voor dat je probeert de perfecte combinatie van ingrediënten voor een taart te vinden, maar je kunt hem pas proeven als je hem hebt gebakken.
1. Je begint met een willekeurig, rommelig recept.
2. Je bakt het en kijkt of het overeenkomt met je voorbeelden.
3. Als het dichtbij zit, maak je een kleine verandering (vervang suiker door honing, voeg een snufje zout toe).
4. Als de nieuwe taart beter is, bewaar je hem. Als hij slechter is, kun je hem nog steeds bewaren (voor het geval dit later leidt tot een betere taart), maar je neemt langzaam minder risico naarmate je dichter bij het perfecte recept komt.
Het Resultaat: Dit proces schrijft automatisch een C-RASP-programma dat perfect bij je voorbeelden past. Het is alsof je een chef-kok hebt die een recept kan reconstrueren door alleen de eindtaart te proeven.

Waarom Dit Belangrijk Is (Volgens Het Artikel)

De auteurs testten hun tools op een verscheidenheid aan "puzzels" (zoals controleren of haakjes in balans zijn of letters tellen).

Snelheid: Hun tools losten deze puzzels op in seconden.
Vergelijking: Zij merkten op dat als je zou proberen een standaard AI (zoals GPT-2) dezezelfde puzzels vanaf nul te laten leren, dit uren zou kunnen duren en het nog steeds niet goed zou kunnen krijgen.
Twee Coole Gebruiksmogelijkheden:
1. Minimalisatie: Als je een enorme, opgeblazen handleiding hebt, kan hun tool deze verkleinen tot de kleinste, eenvoudigste versie die nog steeds werkt.
2. Beperkte Lering: Als je een gedeeltelijk idee hebt van wat het programma zou moeten doen (een "specificatie"), kan hun tool de gaten opvullen om ervoor te zorgen dat het eindprogramma zowel bij je voorbeelden als bij je regels past.

In het kort: Het artikel geeft ons een manier om de mysterieuze "black box" van AI om te zetten in een duidelijke, controleerbare en bewerkbare handleiding, waardoor we de veiligheid kunnen verifiëren en nieuwe kunnen bouwen veel sneller dan voorheen.

Technische Samenvatting: Synthese en Verificatie van Transformer-programma's

Probleemstelling

Transformers, de fundamentele architectuur van Large Language Models (LLM's), staan berucht om hun moeilijkheid voor formele analyse. Hoewel ze expressief en paralleliseerbaar zijn, is het verifiëren van hun eigenschappen onbeslisbaar, en maakt hun uitbreiding met Chain of Thoughts ze Turing-volledig. Om dit aan te pakken, hebben onderzoekers declaratieve talen ontwikkeld zoals RASP (Restricted Access Sequence Processing Language) en zijn variant C-RASP (Counting RASP) om het gedrag van transformers met precieze semantiek vast te leggen.

Echter, ondanks de theoretische connectie tussen C-RASP en transformers, blijven twee kritieke gaten bestaan:

Verificatie: Er bestaat geen automatische methode om C-RASP-programma's te verifiëren. Controleren of een C-RASP een triviaal taal herkent, is in het algemene geval onbeslisbaar, en er bestaat geen praktisch hulpmiddel om eigenschappen zoals taalequivalentie of -inclusie te analyseren.
Synthese: Er is geen bekende methode om automatisch een C-RASP-programma te leren of te synthetiseren uit voorbeelden. Bestaande benaderingen vertrouwen op het trainen van neurale netwerken en het extraheren van regels, wat vaak faalt in het produceren van implementeerbare vertalingen of idealistische aannames vereist.

Dit artikel adresseert deze uitdagingen door de eerste automatische technieken te ontwikkelen voor zowel de verificatie als de synthese van C-RASP-programma's.

Methodologie

1. Verificatie via Reductie naar Lustre

De auteurs leggen een formele connectie tussen C-RASP en Lustre, een synchroon dataflow-taal gebruikt voor ingebouwde systemen.

Vertaling: Een C-RASP-programma wordt vertaald naar een Lustre-node. De vertaling koppelt C-RASP-regels aan Lustre-variabelen (Booleaanse en gehele getallen-stromen).
- Tellersoperatoren: De C-RASP telleroperator #φ (het tellen van posities waar φ geldt) wordt in Lustre gesimuleerd met behulp van hulpgehele getallen-variabelen die waarden accumuleren over een oneindige stroom.
- Eindig versus Oneindig: Aangezien C-RASP werkt op eindige woorden en Lustre op oneindige stromen, wordt de invoer gecodeerd als een oneindige stroom met een specifiek einde-stroom marker (#) en een eeuwigheids-marker (Ω).
Modelcontrole: Eenmaal vertaald, worden eigenschappen zoals taalequivalentie, -inclusie en leegheid geverifieerd met state-of-the-art modelcheckers (specifiek Kind2) gekoppeld aan geoptimaliseerde SMT-oplossers (CVC5, Z3).
Complexiteit: De vertaling is polynomiaal in grootte, op voorwaarde dat de range-parameters in de #rs,re-operator in unair formaat worden gecodeerd.

2. Synthese via Gesimuleerde Temperen

Het artikel stelt een lokaal zoekalgoritme voor op basis van gesimuleerde temperen om C-RASP-programma's te synthetiseren uit positieve en negatieve voorbeelden.

Toestandsruimte: De zoektocht is beperkt tot een vaste "programmaschikking" gedefinieerd door het aantal Booleaanse regels ( $N_b$ ), telregels ( $N_c$ ) en een bovengrens aan numerieke constanten ( $K$ ).
Mutatieoperatoren: Het algoritme verkent de toestandsruimte door syntactische mutaties toe te passen op het huidige programma. Deze omvatten:
- Herverstalen: Het volledig vervangen van de rechterkant van een regel.
- Micro-mutaties: Lokale wijzigingen zoals het verwisselen van logische connectieven, het toggelen van negatie, of het omdraaien van de strengheid van vergelijkingen.
- Beperkingen: Mutaties zijn beperkt tot ondiepe syntaxisfragmenten (bijvoorbeeld diepte-2 voor teluitdrukkingen) om de zoektocht te biasen naar eenvoudige, interpreteerbare modellen.
Doelfunctie: De scorefunctie $E(P)$ prioriteert het minimaliseren van misclassificaties ( $\lambda_{mis}$ ), gevolgd door het straffen van onbereikbare regels ( $\lambda_U$ ) en de totale grootte van de abstracte syntaxboom ( $\lambda_S$ ).
Temperendynamiek: Het algoritme accepteert slechtere oplossingen met een waarschijnlijkheid die afhankelijk is van een koeltemperatuur-schema, waardoor het lokaal optima kan ontsnappen.

3. Geïntegreerde Toepassingen

De auteurs integreren deze twee componenten in een unificerend raamwerk dat twee toepassingen ondersteunt:

Minimalisatie van Transformer-programma's: Gegeven een C-RASP-programma, synthetiseert het systeem een structureel kleiner, equivalent programma. Het wisselt af tussen lokale zoektocht en equivalentiecontrole; tegenvoorbeelden van de verificateur sturen de zoektocht.
Gelimiteerd Leren: Gegeven een gedeeltelijke specificatie (een C-RASP-programma $P_{spec}$ ) en gelabelde voorbeelden, synthetiseert het systeem een programma dat past bij de voorbeelden en is opgenomen in de taal van $P_{spec}$ ( $L(P) \subseteq L(P_{spec})$ ).

Belangrijkste Bijdragen

Eerste Automatische Verificatiemethode: Het artikel presenteert de eerste techniek om C-RASP-programma's automatisch te verifiëren door ze te reduceren tot Lustre en modelcontrole te gebruiken. Dit maakt verificatie van taalequivalentie, -inclusie en leegheid mogelijk.
Eerste Automatische Synthesemethode: De auteurs introduceren een lokaal zoekalgoritme (gesimuleerde temperen) dat in staat is C-RASP-programma's direct uit voorbeelden te synthetiseren, waarbij de noodzaak voor intermediair trainen van neurale netwerken wordt omzeild.
Implementatie en Benchmarking: Een unificerende Scala-toolchain is geïmplementeerd en geëvalueerd tegen een reeks benchmarks uit de literatuur, waaronder reguliere, op telling gebaseerde en contextvrije-achtige talen.

Experimentele Resultaten

De auteurs evalueerden hun tool op een benchmark-suite met talen zoals Dyck-1, Majority en diverse Tomita-automata.

Efficiëntie: De tool synthetiseerde succesvol correcte C-RASP-programma's voor de meeste benchmarks binnen een time-out van 300 seconden. Bijvoorbeeld, het synthetiseren van een programma voor Dyck-1 duurde ongeveer 3,92 seconden, terwijl AnBnCn 80,05 seconden nodig had.
Nauwkeurigheid: De synthese bereikte hoge trainings- en evaluatienauwkeurigheid (vaak 100%) op talen binnen de expressieve kracht van C-RASP.
Vergelijking met Transformers: Het artikel merkt op dat voor bepaalde benchmarks het trainen van een transformer (bijvoorbeeld GPT-2 via HuggingFace) om de juiste taal te bereiken enkele uren kon duren, terwijl de C-RASP-synthesetool de taak in seconden voltooide.
Beperkingen: Zoals verwacht op basis van expressiviteitstheorie, konden talen buiten de kracht van C-RASP (bijvoorbeeld Parity, Tomita 3, Tomita 5) niet met hoge nauwkeurigheid worden geleerd, waarbij de beste trainingsnauwkeurigheden onder de 80% bleven.

Betekenis en Claims

Het artikel positioneert C-RASP niet louter als een theoretisch hulpmiddel voor het begrijpen van transformer-expressiviteit, maar als een interpreteerbaar surrogaatmodel. Door automatische methoden voor verificatie en synthese te bieden, betogen de auteurs dat C-RASP kan worden geanalyseerd met formele methoden (FXAI), waardoor de kloof wordt overbrugd tussen het "black box"-karakter van neurale netwerken en de behoefte aan verklaarbaarheid.

De betekenis ligt in:

Beslisbaarheid in de Praktijk: Hoewel algemene verificatie onbeslisbaar is, biedt de reductie naar Lustre een praktische, geautomatiseerde weg voor het verifiëren van specifieke, real-world transformer-gedragingen.
Directe Synthese: De synthesemethode biedt een directe route naar het genereren van interpreteerbare programma's zonder de instabiliteit of ondoorzichtigheid van het trainen van diepe neurale netwerken.
Optimalisatie: Het vermogen om bestaande transformer-programma's te minimaliseren en ze onder beperkingen te leren, demonstreert de bruikbaarheid van C-RASP voor programmarefinement en veiligheidskritieke toepassingen.

De auteurs concluderen dat hun werk de grondslag legt voor formele analyse van transformers, met toekomstige richtingen die robuustheidsverificatie en de integratie van Chain of Thoughts (CoT)-mechanismen omvatten.