🤖 machine learning

The Complexity of Verifying Feedforward Neural Networks in Quantised Settings

Dit artikel schetst het landschap van de computationele complexiteit voor het verifiëren van feedforward-neurale netwerken in gekwantiseerde settings, waarbij wordt aangetoond dat verificatie NP-compleet blijft voor netwerken met vaste rekenprecisie onder zowel lineaire als bit-vector specificaties, terwijl er nieuwe bovengrenzen worden geleverd voor dynamisch gekwantiseerde netwerken onder bit-vector specificaties.

Oorspronkelijke auteurs: Eric Alsmann, Martin Lange, Marco Sälzer

Gepubliceerd 2026-05-29

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Eric Alsmann, Martin Lange, Marco Sälzer

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 een zeer slimme robot voor (een Feedforward Neuraal Netwerk) die beslissingen neemt, zoals het herkennen van een kat op een foto of het sturen van een zelfrijdende auto. Voordat we deze robot in de echte wereld loslaten, moeten we 100% zeker weten dat hij geen gevaarlijke fouten zal maken. Dit proces heet verificatie.

Lange tijd probeerden wetenschappers deze robots te verifiëren door te doen alsof ze waren opgebouwd uit perfecte wiskunde met oneindige precisie (zoals het gebruik van een liniaal die tot op de grootte van een atoom kan meten, voor altijd). Maar in de echte wereld zijn computers niet perfect. Ze gebruiken gekwantiseerde rekenkunde, wat vergelijkbaar is met het gebruik van een liniaal die alleen streepjes heeft op elke millimeter. Je moet dingen afronden, en soms raak je de opslagruimte op (overflow).

Dit artikel stelt een grote vraag: Maakt de overstap van "perfecte wiskunde" naar "wereldse, afgeronde wiskunde" het veel moeilijker om te bewijzen dat de robot veilig is?

Hier is de uiteenzetting van hun bevindingen, met behulp van alledaagse analogieën:

1. De Drie Typen Robots

De auteurs keken naar drie verschillende manieren waarop deze robots zijn gebouwd:

De Ideale Robot (Rationeel FNN): Gebouwd met perfecte wiskunde met oneindige precisie.
De Pre-Gekwantiseerde Robot (Gekwantiseerd FNN): Van meet af aan gebouwd met de "millimeterliniaal" (wiskunde met eindige breedte).
De Geconverteerde Robot (Dynamisch Gekwantiseerd): Een perfecte robot die we forceren om de "millimeterliniaal" te gebruiken nadat deze al getraind was.

2. De Twee Typen Veiligheidsregels

Om te controleren of de robot veilig is, geven we hem regels. Het artikel bekijkt twee soorten regelboeken:

De Lineaire Regels (LP): Dit zijn simpele, rechte lijnregels. Denk aan een verkeersbord dat zegt: "Als de snelheid onder de 50 ligt, ben je veilig." Deze regels zijn makkelijk te visualiseren als een gladde, convexe vorm.
De Bit-vector Regels (BV): Dit zijn complexe regels op "bit-niveau". Denk aan een beveiligingssysteem dat specifieke schakelaars in het brein van de computer controleert. "Als bit 3 aan staat EN bit 7 uit, maar bit 2 aan, dan is er een probleem." Deze kunnen zeer hoekige, complexe, niet-lineaire vormen beschrijven.

3. De Hoofdbevindingen: Is het Moeilijker?

Scenario A: Simpele Regels (Lineaire Beperkingen)

Het Resultaat: Nee, het is niet moeilijker.
Of de robot nu perfect is of de "millimeterliniaal" gebruikt, en of de regels simpel of complex zijn, het controleren van de veiligheid blijft NP-compleet.

De Analogie: Stel je voor dat je probeert een specifieke sleutel te vinden in een gigantische, rommelige la. Of de sleutels nu van goud zijn (perfecte wiskunde) of van plastic (afgeronde wiskunde), en of de la georganiseerd of chaotisch is, de moeilijkheidsgraad om de sleutel te vinden verandert niet. Het is nog steeds een "moeilijk" probleem, maar het is hetzelfde niveau van moeilijk als voorheen.
Waarom dit belangrijk is: Dit betekent dat we geen volledig nieuwe, superkrachtige computers hoeven uit te vinden om robots uit de echte wereld te verifiëren. De tools die we al hebben voor perfecte wiskunde kunnen worden aangepast voor wereldse wiskunde zonder exponentieel langzamer te worden.

Scenario B: Complexe Regels (Bit-vector Beperkingen)

Het Resultaat: Het hangt af van de "hersengrootte" van de robot.

Als de robot al is gebouwd met de "millimeterliniaal": Het controleren van de veiligheid is nog steeds NP-compleet (zelfde moeilijkheidsgraad als voorheen).
Als we een perfecte robot nemen en hem forceren om de "millimeterliniaal" te gebruiken (Dynamische Kwantisering): Dit wordt veel moeilijker. Het springt naar PSPACE-compleet.
- De Analogie: Stel je voor dat je een perfect recept hebt (de perfecte robot). Nu moet je het koken in een kleine keuken met een specifieke, beperkte set potten en pannen (de rekenkunde met eindige breedte). Als je vanaf het begin alleen de beperkte potten gebruikt, is het prima. Maar als je probeert het perfecte recept terwijl je kookt te vertalen naar de beperkte keuken, explodeert het aantal mogelijke manieren waarop dingen mis kunnen gaan. Je moet zoveel "wat-als"-scenario's bijhouden (zoals het uitlijnen van getallen van verschillende groottes) dat de geheugenruimte die nodig is om ze allemaal te controleren enorm groeit.

4. Het Vlakke-Punt Mysterie

Het artikel keek ook naar drijvende-kommagetallen (de standaard manier waarop computers decimalen verwerken, zoals 3,14).

Vaste Exponent: Als het bereik van getallen vaststaat (zoals een liniaal met een vast maximum), blijft de moeilijkheidsgraad beheersbaar (PSPACE).
Algemene Vloeiende-Punt: Als het bereik wild kan variëren, kan de moeilijkheidsgraad nog hoger springen (NEXPTIME).
De Analogie: Bij drijvende-kommawiskunde kunnen getallen zeer klein of zeer groot zijn. Om ze op te tellen, moet de computer ze eerst "uitlijnen" (zoals het op één lijn brengen van decimalen). Als de getallen wild verschillende groottes hebben, moet de computer een enorme hoeveelheid data bufferen om deze uitlijning te doen. De auteurs ontdekten dat deze "uitlijning"-stap is wat het probleem potentieel veel, veel moeilijker maakt op te lossen.

Samenvatting

Het artikel zegt in essentie:

Goed nieuws: Voor het meest voorkomende type veiligheidscontrole (lineaire regels) maakt de overstap naar wereldse, afgeronde wiskunde de taak niet onmogelijk. Het blijft op hetzelfde niveau van moeilijkheid als de theoretische perfecte wiskunde.
Slecht nieuws: Als je zeer complexe, bit-niveau regels gebruikt op een perfecte robot die je forceren om afgeronde wiskunde te gebruiken, wordt de taak aanzienlijk moeilijker (PSPACE).
Het Onbekende: Als je standaard drijvende-kommawiskunde gebruikt met wilde bereiken, kan de taak nog moeilijker zijn, maar de auteurs zijn nog niet 100% zeker; ze weten alleen dat het ten minste zo moeilijk is als het "PSPACE"-niveau.

Kortom: Kwantisering ( afronden) breekt verificatie niet voor simpele regels, maar maakt het wel aanzienlijk rekenkundig duurder voor complexe, dynamische scenario's.

Technische Samenvatting: De Complexiteit van het Verifiëren van Feedforward Neuronale Netwerken in Gekwantiseerde Omgevingen

Probleemstelling

Het artikel onderzoekt de computationele complexiteit van het formeel verifiëren van Feedforward Neuronale Netwerken (FNN's) onder gekwantiseerde omstandigheden. Hoewel het bereikbaarheidsprobleem voor FNN's die werken met reëelwaardige rekenkunde (rationele gewichten) is vastgesteld als NP-volledig, vertrouwen praktische implementaties op rekenkunde met eindige breedte (bijvoorbeeld 64-bits floating-point of vastepuntgetallen). Deze verschuiving introduceert kwantisatie-effecten zoals afronding, overflow en underflow.

De auteurs adresseren een mogelijk gat in het begrip: leidt de overstap van geïdealiseerde reëelwaardige rekenkunde naar discrete, eindig-brede rekenkunde tot een toename van de computationele complexiteit van verificatie? Bovendien onderzoeken zij hoe de complexiteit verandert op basis van:

Specificatieformalismen: Lineaire Programmering (LP) beperkingen versus Bit-vector (BV) logica's (die niet-lineaire, bit-niveau redenering toestaan).
Netwerkdefinitie: Of het FNN wordt gedefinieerd met exacte rationele gewichten (Rationeel FNN) of vooraf gekwantiseerde gewichten (Gekwantiseerd FNN).
Parametercodering: Of de bit-breedte van de rekenkunde wordt gegeven als onderdeel van de invoer in unair (realistisch voor hardware-registergroottes) of binair (realistisch voor decimale specificaties).

Methodologie

De auteurs formaliseren vijf verschillende bereikbaarheidsbeslissingsproblemen, aangeduid als REACH, die variëren per rekenkundetype en specificatietaal:

REACHQ(LP): Rationele FNN's met LP-specificaties (standaard instelling).
REACHF(LP): Gekwantiseerde FNN's (gewichten al in rekenkunde met eindige breedte) met LP-specificaties.
REACHF(BV): Gekwantiseerde FNN's met Bit-vector-specificaties.
REACH(F, LP): Rationele FNN's waarbij de doel-rekenkunde met eindige breedte $F$ onderdeel is van de invoer (dynamische kwantisatie) met LP-specificaties.
REACH(F, BV): Rationele FNN's met dynamische kwantisatie en Bit-vector-specificaties.

Analytische Aanpak:

Complexiteitsondergrenzen: De auteurs maken gebruik van reducties van bekende moeilijke problemen (bijvoorbeeld 3SAT) om NP-hardheid en PSPACE-hardheid vast te stellen. Zij tonen aan dat standaard "gadgets" die worden gebruikt om Booleaanse logica te coderen in FNN's (met ReLU-activaties) ook geldig blijven onder rekenkunde met eindige breedte, mits de rekenkunde kleine gehele getallen en breuken zoals $1/2$ kan representeren.
Complexiteitbovengrenzen:
- Voor LP-specificaties vertrouwen de auteurs op de polynomiale begrenzing van oplossingsgroottes in lineaire programmering (Stelling 1) om aan te tonen dat een getuige (invoervector) kan worden geraadpleegd en geverifieerd in polynomiale tijd.
- Voor BV-specificaties met dynamische kwantisatie maken de auteurs gebruik van Korte Niet-deterministische Eindige Automata (NFA). Zij construeren automata die de invoer-uitvoerrelatie van het gekwantiseerde FNN en de specificatieformules representeren. De toestandsruimte van deze automata is exponentieel groot, maar wordt compact (kort) beschreven.
- Zij onderscheiden tussen vastepunt en floating-point rekenkunde. Voor floating-point merken zij op dat algemene rekenkunde uitlijningverschuivingen vereist die afhankelijk zijn van het verschil in exponent. Als de exponent-breedte onbegrensd is (gegeven in binair), wordt de grootte van de uitlijnbuffer exponentieel, wat mogelijk de PSPACE-grenzen doorbreekt. Zij beperken hun PSPACE-bovengrens-bewijzen tot gevallen waarbij de exponent-breedte constant is.

Belangrijkste Bijdragen en Resultaten

Het artikel vestigt een uitgebreid complexiteitslandschap, samengevat in Tabel 1 van de tekst:

1. Lineaire Programmering (LP) Specificaties

REACHQ(LP): Bevestigd als NP-volledig (verwijzend naar Sälzer en Lange, 2021).
REACHF(LP): Bewezen NP-volledig. De auteurs tonen aan dat zelfs met vooraf gekwantiseerde gewichten het probleem in NP blijft, omdat de invoergrootte van de getuige polynomiaal is ten opzichte van de netwerkgrootte.
REACH(F, LP): Bewezen NP-volledig. Zelfs wanneer de bit-breedte parameters onderdeel zijn van de invoer (dynamische kwantisatie), blijft het probleem NP-volledig. De auteurs betogen dat de grootte van de getuige polynomiaal begrensd blijft ten opzichte van de invoergrootte, ongeacht of bit-breedtes in unair of binair worden gecodeerd.

2. Bit-vector (BV) Specificaties

REACHF(BV): Bewezen NP-volledig. Voor netwerken die al gekwantiseerd zijn, verhoogt het gebruik van bit-vector logica de complexiteit niet verder dan NP.
REACH(F, BV) (Vastepunt & Floating-point met constante exponent-breedte): Bewezen PSPACE-volledig.
- Ondergrens: Komt overeen met het eerder vastgestelde PSPACE-hardheid resultaat van Henzinger et al. (2021).
- Bovengrens: De auteurs leveren de eerste overeenkomstige PSPACE-bovengrens. Zij bereiken dit door het probleem te reduceren tot het niet-leegheidsprobleem van kort weergegeven NFA's.
REACH(F, BV) (Algemene Floating-point): Het probleem is PSPACE-hard en ligt binnen NEXPTIME.
- De auteurs merken op dat voor algemene floating-point rekenkunde (waarbij de exponent-breedte variabel is en in binair wordt gegeven), de uitlijnstap bij optelling/vermenigvuldiging een buffergrootte vereist die afhankelijk is van het exponent-verschil. Dit verhindert de constructie van een korte NFA met een polynomiale beschrijvingsgrootte, waardoor de exacte bovengrens open blijft (momenteel NEXPTIME).

Betekenis en Claims

Het artikel claimt een "wijdverbreid misverstand" op te lossen met betrekking tot de complexiteit van de verificatie van gekwantiseerde FNN's, specifiek gericht op de resultaten van Henzinger et al. (2021).

Verduidelijking van Complexiteitsdrijvers: De auteurs betogen dat de sprong van NP naar PSPACE die in eerdere werken werd waargenomen, niet wordt veroorzaakt door kwantisatie zelf, maar door de combinatie van dynamische kwantisatie (waarbij de rekenkunde onderdeel is van de invoer) en het gebruik van Bit-vector specificaties. Voor standaard lineaire specificaties verhoogt kwantisatie de complexiteitsklasse niet; deze blijft NP-volledig.
Haalbaarheid van Tools: De resultaten suggereren dat het ontwikkelen van sounde verificatietools voor gekwantiseerde FNN's met lineaire specificaties haalbaar is zonder asymptotische overhead in vergelijking met bestaande reëelwaardige oplosprogramma's, aangezien beide NP-volledig blijven.
Bovengrenzen voor BV: Het artikel vult de bekende PSPACE-hardheid van dynamische gekwantiseerde verificatie met BV-specificaties aan door PSPACE-volledigheid vast te stellen voor vastepunt en floating-point rekenkunde met begrenste exponenten.
Open Problemen: De auteurs identificeren bescheiden dat voor algemene floating-point rekenkunde met onbegrensde exponenten, de uitlijnvereiste het probleem mogelijk buiten PSPACE kan duwen (naar NEXPTIME), en het blijft een open vraag of een overeenkomstige ondergrens kan worden bewezen.

Concluderend biedt het artikel een rigoureuze classificatie die aantoont dat, hoewel bit-vector specificaties op dynamisch gekwantiseerde netwerken PSPACE-complexiteit introduceren, het standaardgeval van lineaire beperkingen op gekwantiseerde netwerken de NP-volledigheid van het rationele geval behoudt.