🤖 machine learning

Scaling Neural Network Verification with Tensor Parallelism and Fully Sharded Data Parallelism

Diese Arbeit adaptiert Tensor Parallelism und Fully Sharded Data Parallelism an das $\alpha$ -CROWN Verifizierungsframework, um den GPU-Speicherverbrauch signifikant zu reduzieren, was die formale Verifizierung großer neuronaler Netze wie ResNet-large auf CIFAR-100 ermöglicht, die zuvor aufgrund von Speicherbeschränkungen nicht durchführbar waren.

Ursprüngliche Autoren: Sergei Vorobyov, Eugene Ilyushin

Veröffentlicht 2026-06-09

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Sergei Vorobyov, Eugene Ilyushin

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 zu beweisen, dass ein selbstfahrendes Auto niemals einen Unfall bauen wird, egal wie das Wetter ist oder wie plötzlich ein Fußgänger auf die Straße springt. Sie können das Auto nicht einfach eine Million Mal testen; Sie benötigen einen mathematischen „Beweis“, der zeigt, dass es in jedem erdenklichen Szenario sicher ist. Dies nennt man Formale Verifizierung neuronaler Netze.

Das Problem ist, dass das Erstellen eines solchen Beweises extrem speicherintensiv ist. Es ist, als würde man versuchen, ein riesiges Puzzle zu lösen, aber alle Teile (die Daten und die Regeln) müssen auf einen einzigen, kleinen Tisch (eine einzige Grafikkarte) passen. Wenn das Puzzle zu groß ist, läuft der Tisch über und der Beweis scheitert.

Dieses Paper stellt zwei neue Wege vor, um dieses Puzzle zu lösen, indem es Ideen nutzt, wie heute bereits riesige KI-Modelle trainiert werden, und dabei mehrere Tische (GPUs) nutzt, die zusammenarbeiten.

Hier ist die Aufschlüsselung ihrer zwei Hauptlösungen, erklärt mit einfachen Analogien:

1. Der „Puzzle-Teilen“-Ansatz (Tensor-Parallelismus)

Die Idee: Stellen Sie sich vor, Sie haben ein riesiges Puzzle. Anstatt dass eine Person das ganze Teil hält, teilen Sie das Puzzle in der Mitte. Person A hält die linke Hälfte und Person B die rechte Hälfte. Beide arbeiten an ihren eigenen Teilen und rufen sich gegenseitig die Ergebnisse zu.

Wie es funktioniert: Die Forscher verteilen die „Gewichte“ (die Puzzleteile) und die „Regeln“ (die Mathematik) auf zwei GPUs.
Die gute Nachricht: Dies reduziert den Speicherbedarf auf jedem Computer fast um die Hälfte (ca. 2-fache Reduktion). Es ist sehr effizient für kleine oder flache Puzzles.
Der Haken: Wenn das Puzzle tiefer wird (viele Schichten hat), müssen die beiden Personen die Verbindung zwischen ihren Hälften schätzen, ohne das gesamte Bild sehen zu können. Um Zeit zu sparen, verwenden sie eine „schnelle und ungenaue“ Schätzmethethode (genannt IBP) für die mittleren Teile.
Das Ergebnis: Der endgültige Beweis bleibt sicher (er wird nicht sagen, dass ein Auto sicher ist, wenn es eigentlich gefährlich ist), aber das Ergebnis wird etwas „unscharfer“ oder weniger präzise, je tiefer das Puzzle wird. Es ist, als würde man die Entfernung zu einem Berg anhand des Horizonts schätzen, anstatt sie exakt zu messen.

2. Der „Gemeinsame Bibliothek“-Ansatz (Fully Sharded Data Parallelism – FSDP)

Die Idee: Stellen Sie sich eine Bibliothek vor, in der die Bücher zu groß sind, um in ein einziges Regal zu passen. Anstatt das ganze Buch für jeden Leser zu kopieren, teilt die Bibliothek das Buch in Seiten auf.

Wie es funktioniert: Die Forscher verteilen die „Gewichte“ (die Buchseiten) über die GPUs.
Der magische Trick: Wenn ein Computer eine Berechnung durchführen muss, sammelt er schnell alle Seiten, die er benötigt, von den anderen Computern ein, führt die Mathematik aus und legt die Seiten sofort wieder zurück. In einem einzigen Moment hält kein Computer das gesamte Buch.
Die gute Nachricht:
- Perfekte Genauigkeit: Da die Mathematik exakt so durchgeführt wird, wie wenn ein einzelner Computer das ganze Buch hätte, ist das Ergebnis bitgenau identisch mit der Single-Computer-Version. Keine „Unschärfe“.
- Speichereffizienz: Es spart eine enorme Menge an Speicher (80–90 % für das Basisszenario und 34–39 % für die Spitzenbelastung).
Der Haken: Es erfordert ein wenig „Kommunikation“ zwischen den Computern, um die Seiten zu sammeln, was ein klein wenig Zeit kostet, aber die Speichereinsparung ist es wert.

Die große Überraschung: Was verstopft eigentlich den Speicher?

Die Forscher erwarteten, dass die „Gewichte“ (die Puzzleteile oder Buchseiten) das Hauptproblem sein würden. Sie lagen falsch.

Nachdem sie diese neuen Methoden genutzt hatten, um Platz für die Gewichte zu schaffen, entdeckten sie den wirklichen Flaschenhals: eine spezielle Art von Daten, die „Alpha-Tensoren“ genannt werden.

Die Analogie: Stellen Sie sich vor, Sie lösen das Puzzle. Die „Gewichte“ sind die Puzzleteile, aber die „Alpha-Tensoren“ sind die Klebezettel, die Sie für jedes einzelne Teil schreiben müssen, um Ihren Fortschritt zu verfolen.
Die Erkenntnis: In der fortschrittlichsten Verifizierungsmodi (bei der sie Abstürze mithilfe einer Methode namens Branch-and-Bound prüfen) nehmen diese Klebezettel 99 % des Speichers ein, nicht die Puzzleteile.
Das Fazrazit: Selbst wenn sie die Puzzleteile erfolgreich auf verschiedene Computer verteilt haben, sind die „Klebezettel“ immer noch zu groß, um hineinzupassen. Um die größten Probleme zu lösen (wie die Verifizierung komplexer KI für selbstfahrende Autos), muss die zukünftige Arbeit darauf abzielen, auch diese Klebezettel über mehrere Computer hinweg zu verteilen.

Zusammenfassung der Ergebnisse

Tensor-Parallelismus: Gut, um Speicher zu sparen, macht die Antwort aber bei tiefen Netzwerken etwas weniger präzise.
FSDP: Behält die Antwort perfekt präzise bei und spart viel Speicher. Es konnte erfolgreich ein komplexes Bilderkennungsmodell (ResNet) verifizieren, das zuvor zu groß war, um überprüft zu werden.
Die Zukunft: Der Schlüssel zur Verifizierung noch größerer KI-Systeme liegt nicht mehr nur darin, die Gewichte zu teilen; es geht darum, die „Klebezettel“ (Alpha-Tensoren), die den Verifizierungsprozess verfolgen, ebenfalls zu teilen.

Kurz gesagt zeigt das Paper, wie man mehrere Computer nutzen kann, um die Sicherheit von KI zu verifizieren, aber es enthüllt auch, dass wir noch eine große Speicherhürde zu nehmen haben, bevor wir die größten, komplexesten KI-Systeme verifizieren können.

Technisches Resümee: Skalierung der Verifizierung neuronaler Netze mittels Tensor-Parallelismus und Fully Sharded Data Parallelism

1. Problemstellung

Die formale Verifizierung neuronaler Netze zielt darauf ab, mathematisch zu beweisen, dass ein Netzwerk Sicherheits-Eigenschaften für alle Eingaben innerhalb eines spezifizierten Bereichs erfüllt. Während Bound-Propagation-Algorithmen wie IBP, CROWN und $\alpha$ -CROWN der Stand der Technik für diese Aufgabe sind, ist ihre praktische Anwendung durch GPU-Speicher stark begrenzt. Standardimplementierungen erfordern, dass die Gewichtmatrizen und die linearen Relaxations- $A$ -Matrizen vollständig auf einem einzigen Beschleuniger vorliegen. Für große Netzwerke (z. B. eine einzelne verborgene Schicht mit einer Breite von $h=262.144$ ) können allein die Gewichtmatrizen 4 GB in float32 überschreiten, wodurch nicht genügend Speicher für die $A$ -Matrizen, das Batching oder die erforderlichen Zwischen-Tensoren zur Verifizierung bleibt. Diese Arbeit adressiert die Notwendigkeit, den Single-GPU-Speicherengpass zu beseitigen, indem Parameter-Sharding-Strategien aus dem großskaligen Modelltraining auf das Verifizierungs-Framework adaptiert werden.

2. Methodik

Die Autoren adaptieren zwei Parallelisierungstechniken – Tensor Parallelism (TP) und Fully Sharded Data Parallelism (FSDP) – an das auto LiRPA / $\alpha, \beta$ -CROWN Verifizierungs-Framework.

2.1 Tensor Parallelism (TP)

TP teilt Matrixmultiplikationen innerhalb einer einzelnen Schicht auf $P$ GPUs auf.

Implementierung: Die Autoren implementierten benutzerdefinierte BoundLinearTP Col und BoundLinearTP Row Operatoren. Die Gewichte werden entlang der Ausgabekolonne (Column) oder der Eingaberelation (Row) partitioniert.
Mechanismus: In einem Column–Row-Paar wird die Berechnung verteilt, was eine AllReduce-Operation erfordert, um das Ergebnis wiederherzustellen.
Limitierung: Wenn ReLU-Aktivierungen innerhalb einer partitionierten Zone auftreten (zwischen Column- und Row-Schichten), erfordert der CROWN-Backward-Pass Zwischenbounds, um die Steigungen der Relaxation ( $\lambda_i$ ) zu bestimmen. Um die exakte Berechnung zu vermeiden, die inter-GPU-Kommunikation bei jedem Schritt erfordern würde, ersetzen die Autoren diese Zwischenbounds durch die einfachere Interval Bound Propagation (IBP). Dies führt zu einem „Wrapping-Effekt“, wodurch die Tightness der Bounds abnimmt, je tiefer die partitionierte Zone ist.

2.2 Fully Sharded Data Parallelism (FSDP)

FSDP partitioniert die Parameter-Tensoren gleichmäßig über $P$ GPUs, rekonstruiert sie jedoch für die Berechnung.

Implementierung: Implementiert mit etwa 100 Zeilen Python, ersetzt FSDP die BoundParams-Tensoren durch Shards. Vor der Berechnung einer Schicht setzt ein AllGather die vollständige Gewichtmatrix zusammen; unmittelbar danach wird der vollständige Tensor freigegeben und nur der Shard beibehalten.
Mechanismus: Dieser Ansatz stellt sicher, dass zu keinem Zeitpunkt mehr als eine vollständige Gewichtmatrix im GPU-Speicher existiert. Entscheidend ist, dass FSDP die Reihenfolge oder den Typ der arithmetischen Operationen nicht verändert; es ändert lediglich den Speicherort der Gewichte.
Korrektheit: Da die Arithmetik identisch mit der Single-GPU-Baseline bleibt, erzeugt FSDP bitidentische Bounds ( $\Delta = 0$ ).
Integration: FSDP lässt sich nahtlos in die vollständige Verifizierung ( $\beta$ -CROWN + Branch-and-Bound) und in Faltungsschichten (BoundConv) integrieren.

2.3 Experimenteller Aufbau

Die Experimente wurden auf NVIDIA A40 GPUs unter Verwendung von PyTorch 2.x und der auto LiRPA-Bibliothek durchgeführt. Die Autoren führten ein bab.force_synchronous Flag ein, um einen fairen Vergleich zwischen Single-GPU- und Distributed-Modus zu gewährleisten, indem sie das automatische Batch-Resizing und Pruning im Single-GPU-Pfad deaktivierten, um identische Arbeitslasten sicherzustellen.

3. Kernbeiträge

TP-Implementierung für die Verifizierung: Die Autoren implementierten TP für auto LiRPA unter Verwendung benutzerdefinierter Operatoren, wobei sie eine Reduktion des Peak-Speichers um etwa das 2-fache bei $P=2$ erreichten. Sie analysierten den Trade-off formal und bestätigten, dass die Korrektheit gewahrt bleibt, die Tightness der Bounds jedoch mit der Anzahl der partitionierten Zonen aufgrund der IBP-Substitution abnimmt.
FSDP-Implementierung: Sie implementierten FSDP für die Bound-Propagation, was eine Reduktion des Baseline-Speichers um 80–90 % und eine Reduktion des Peak-Speichers um 34–39 % bei weiten MLPs erreichte. Entscheidend ist, dass diese Methode bitidentische Bounds zur Single-GPU-Baseline liefert.
Integration in die vollständige Verifizierung: FSDP wurde erfolgreich in $\beta$ -CROWN und Branch-and-Bound (BaB) integriert, was die erste vollständige Verifizierung (UNSAT-Ergebnis) eines CIFAR-100 ResNet-large Modells unter FSDP ermöglichte.
Identifikation des Engpasses: Durch umfangreiche Experimente identifizierten die Autoren, dass in $\alpha$ -CROWN + BaB Modus der primäre Speicherengpass nicht die Gewichtmatrizen sind, sondern die Alpha-Tensoren pro Neuron (ReLU-Steigungen).

4. Ergebnisse

4.1 Speicherreduktion

TP: Erreichte einen Peak-Speicher-Reduktionsfaktor von $\approx 1,985$ (nahe am theoretischen $P=2$ ) für ein weites MLP ( $h=262.144$ ).
FSDP:
- Baseline-Speicher: Reduziert um 80–90 % über verschiedene Modellgrößen hinweg, da nur Shards vor der Bound-Berechnung alloziert werden.
- Peak-Speicher: Reduziert um 34–39 % bei weiten MLPs ( $h \ge 4096$ ). Die Einsparungen sind geringer als die Baseline-Einsparungen, da die unpartitionierten $A$ -Matrizen (die mit der Breite quadratisch skalieren) im Speicher verbleiben.

4.2 Genauigkeit und Korrektheit der Bounds

TP:
- Modelle mit einer partitionierten Zone (kein Zwischen-ReLU) erreichten eine Übereinstimmung auf Maschinengenauigkeit ( $\sim 10^{-8}$ ) mit der Single-GPU-Referenz.
- Modelle mit mehreren partitionierten Zonen zeigten signifikante Abweichungen (z. B. $\sim 750$ Einheiten bei einem 3-Zonen-Modell) aufgrund der IBP-Substitution, wobei die Korrektheit (einseitige Überapproximation) jedoch gewahrt blieb.
FSDP:
- Erreichte eine exakt null Abweichung ( $\Delta lb = \Delta ub = 0,00$ ) über alle getesteten Modelle (MLPs und ONNX-Benchmarks) sowohl für IBP als auch für CROWN.
- Verifizierte erfolgreich ein Transformer-Modell (ViT) und konvolutionale ResNets mit bitidentischen Ergebnissen zur Baseline.

4.3 Vollständige Verifizierung (BaB)

Im $\beta$ -CROWN + BaB Modus wird der Speicherverbrauch von den Alpha-Tensoren dominiert (z. B. 1,5 GB für Alpha-Tensoren gegenüber 1,5 MB für Gewichte in einem spezifischen MNIST-Netzwerk).

Das Sharding der Gewichte via FSDP lieferte in diesem Modus vernachlässigbare Peak-Speicher-Einsparungen, da die Alpha-Tensoren nicht partitioniert wurden.
Dennoch ermöglichte FSDP erfolgreich die Verifizierung eines ResNet-large Modells (VNN-COMP 2024), das andernfalls unmöglich oder schwer zu handhaben gewesen wäre, und bestätigte eine UNSAT-Eigenschaft ohne BaB-Branching.

5. Bedeutung und Limitierungen

Die Arbeit zeigt, dass Strategien zum Partitionieren von Parametern aus dem Training mit moderatem technischem Aufwand auf die formale Verifizierung übertragen werden können.

Bedeutung: FSDP bietet einen Weg, größere Netzwerke mit exakten Bounds zu verifizieren, während TP die höchste Speicherreduktion auf Kosten der Tightness der Bounds für tiefe Netzwerke bietet. Die Arbeit etabliert, dass FSDP mit den komplexen Anforderungen der vollständigen Verifizierung (BaB) und diversen Architekturen (CNNs, Transformer) kompatibel ist.
Limitierungen:
- Skalierbarkeit: Die Experimente waren auf $P=2$ beschränkt. Die Autoren merken an, dass mit steigendem $P$ die unpartitionierten $A$ -Matrizen wahrscheinlich zum dominierenden Kostenfaktor werden, was zu abnehmenden Grenzerträgen führt.
- TP-Tightness: Die Verschlechterung der Tightness der Bounds in TP für tiefe Netzwerke schränkt deren Nutzen für die präzise Verifizierung tiefer Architekturen ein.
- Verschiebung des Engpasses: Die Experimente zeigen, dass zukünftige Multi-GPU-Verifizierungsforschung sich auf das Partitionieren der Alpha-Tensoren pro Neuron konzentrieren muss, nicht nur auf die Gewichte, um eine signifikante Skalierung in Modi der vollständigen Verifizierung zu erreichen.

Die Autoren kommen zu dem Schluss, dass während FSDP das Problem des Gewichts-Speichers löst, der Engpass durch die Alpha-Tensoren weiterhin die kritische Herausforderung für die Skalierung der vollständigen Verifizierung auf größere Modelle darstellt.