Technische Zusammenfassung: CGF-Softmax

Problemstellung

Homomorphe Verschlüsselung (HE) ermöglicht privatsphäreschonendes maschinelles Lernen, indem Berechnungen auf verschlüsselten Daten ohne Entschlüsselung erlaubt werden. Die Implementierung nicht-polynomieller Operationen, insbesondere der Softmax-Funktion, die für Transformer-Architekturen zentral ist, bleibt jedoch in strikt nicht-interaktiven HE-Umgebungen ein erheblicher Engpass.

Die Standard-Softmax-Formulierung, $\text{softmax}(x)_i = \frac{\exp(x_i)}{\sum_j \exp(x_j)}$, stellt in HE drei Hauptprobleme dar:

1. Numerische Instabilität: Die Exponentialfunktion führt zu schnellem Wachstum und damit zu Überläufen. Die Standard-Inferenz im Klartext mildert dies durch Subtraktion des maximalen Eingabewerts ($x_{\max}$), doch die Maximalwert-Operation erfordert komplexe Vergleichslogik, die mit HE unvereinbar ist und teure polynomielle Approximationen notwendig macht.
2. Divisionsoperationen: Der Normalisierungsschritt erfordert Division, die HE-Schemata nativ nicht unterstützen. Vorherige Arbeiten verlassen sich auf iterative polynomielle Approximationen (z. B. Goldschmidt-Algorithmus oder Tschebyschow-Polynome) für Kehrwertfunktionen, was die multiplikative Tiefe drastisch erhöht.
3. Berechnungskosten: Hochgradige polynomielle Approximationen, die sowohl für die Exponential- als auch für die Divisionsfunktion erforderlich sind, verbrauchen das begrenzte Stufenbudget von gestuften HE-Schemata (wie CKKS) und erfordern oft kostspielige Bootstrapping-Operationen, um Chiffretexte zu aktualisieren.

Bestehende Ansätze lassen sich in zwei Kategorien einteilen: Softmax-Approximation (hohe Genauigkeit, aber hohe Tiefe aufgrund von Division/Maximum) und Softmax-Ersatz (geringe Tiefe, aber signifikante Genauigkeitsverschlechterung, insbesondere bei großskaligen Modellen und komplexen Benchmarks).

Methodik: CGF-Softmax

Die Autoren schlagen CGF-Softmax vor, eine Neuformulierung der Softmax-Funktion, die sowohl die homomorphe Division als auch die explizite Subtraktion des Maximums eliminiert. Die Kerninnovation besteht in der Interpretation des Softmax-Nenners durch die Kumulantenerzeugende Funktion (CGF).

Theoretische Neuformulierung

Gegeben einen Eingabevektor $x$ interpretieren die Autoren den Nenner $\sum \exp(x_i)$ als skaliertes Stichprobenmittel von Exponentialtermen. Durch Ersetzen des Stichprobenmittels durch das Ensemble-Mittel (Erwartungswert) wird der Nenner durch $n M_X(1)$ ersetzt, wobei $M_X(t)$ die Momentenerzeugende Funktion (MGF) ist.

Unter Verwendung der CGF, definiert als $K_X(t) = \ln M_X(t)$, wird die reformulierte Softmax-Funktion ausgedrückt als:
$$\text{softmax}_{\text{CGF}}(x)_i = \exp(x_i - K_X(1) - \ln n)$$

Diese Formulierung bietet drei entscheidende Vorteile:

1. Eliminierung der Max-Operation: Anstatt den Maximalwert zu subtrahieren, wird die Eingabe um $K_X(1) + \ln n$ verschoben. Da $K_X(1)$ mittels niedriger Ordnungskumulanten (Mittelwert $\mu$ und Varianz $\sigma^2$) approximiert werden kann, ist diese Verschiebung datenadaptiv und über grundlegende HE-Operationen (Addition und Multiplikation) ohne Vergleiche berechenbar.
2. Eliminierung der Division: Der Normalisierungsterm wird in den Exponenten integriert. Das Ergebnis ist eine einzelne Exponentialfunktion, wodurch die Notwendigkeit einer homomorphen Division vollständig entfällt.
3. Domänenskalierung: Die Methode unterstützt natürlicherweise die Domänenskalierung. Durch Skalierung des Exponenten mit $1/2^k$ wird die Exponentialfunktion über ein kleineres Intervall ausgewertet, und die ursprüngliche Skala wird durch $k$-maliges Quadrieren wiederhergestellt. Dies vermeidet den iterativen „Normalisieren-und-quadrieren"-Prozess, der für die Standard-Softmax erforderlich ist und wiederholte Divisionen beinhaltet.

Praktische Umsetzung

Für die praktische HE-Auswertung übernehmen die Autoren eine Approximation zweiter Ordnung der Kumulanten:
$$K_X(1) \approx \mu + \frac{\sigma^2}{2}$$
Höhere Ordnungen ($\kappa_j/j!$ für $j \ge 3$) werden weggelassen. Die Autoren argumentieren, dass der Fakultätsnenner diese Terme intrinsisch unterdrückt, und dass eine empirische Feinabstimmung die Größe höherer Ordnungskumulanten weiter reduziert, was die Approximation für die Inferenz ausreichend genau macht.

Hauptbeiträge

1. CGF-Softmax-Formulierung: Eine neuartige Neuformulierung, die die Notwendigkeit homomorpher Division und Maximum-Subtraktion beseitigt und die multiplikative Tiefe erheblich reduziert.
2. Theoretische Analyse: Die Arbeit etabliert Schlüsseleigenschaften von CGF-Softmax, darunter:
   • Positivität: Streng positive Ausgaben.
   • Erhaltung von Reihenfolge und paarweisen Verhältnissen: Sie erhält die relative Reihenfolge der Logits und die exakten paarweisen Ausgabeverhältnisse ($\exp(x_i - x_j)$) der Standard-Softmax-Funktion.
   • Verschiebungsinvarianz: Wie die Standard-Softmax-Funktion ist sie gegenüber konstanten Verschiebungen invariant.
   • Asymptotische Fehlerschranke: Unter Verwendung des Berry–Esseen-Theorems beweisen die Autoren, dass der relative Fehler mit wachsender Eingabedimension $n$ in der Wahrscheinlichkeit gegen Null konvergiert.
3. Experimentelle Validierung: Umfassende Evaluierung an Vision Transformern (ViT/DeiT) und Large Language Models (LLaMA-3.2-1B), die hohe Genauigkeit bei reduzierten Berechnungskosten demonstrieren.

Experimentelle Ergebnisse

Die Autoren evaluierten CGF-Softmax auf ImageNet-1k (Vision Transformer) und mehreren NLP-Benchmarks (Clinc150, Banking77, SST-2) unter Verwendung des LLaMA-3.2-1B-Modells.

• Multiplikative Tiefe: CGF-Softmax erreicht für großskalige Modelle (z. B. LLaMA-3.2-1B, ViT-Base) eine multiplikative Tiefe von 7–10. Im Gegensatz dazu erfordern vorherige Approximationsmethoden (z. B. Cho et al., EncryptedLLM) Tiefen von 14–52 für kleinere Modelle oder Aufgaben.
• Laufzeit: Bei einer Eingabematrix von 256×256 reduzierte CGF-Softmax die Gesamtlatenz von 107,65 s (Cho et al.) auf 3,25 s, hauptsächlich durch die Eliminierung von Bootstrapping und die Reduktion von Chiffretext-Multiplikationen (CMult).
• Genauigkeit:
  • CGF-Softmax hält die Inferenzgenauigkeit über alle Benchmarks hinweg innerhalb von <1 % der exakten Standard-Softmax-Baseline im Klartext.
  • Es übertrifft Softmax-Ersatzmethoden (z. B. BPMax) signifikant, die bei komplexen Aufgaben erhebliche Genauigkeitsverluste erleiden.
  • Es erreicht nahezu Klartext-Genauigkeit bei gleichzeitig 4–6× geringerer Tiefe als hochpräzise Approximations-Baselines.
• Verhalten des Rauschens: Durch die Eliminierung der Division reduziert CGF-Softmax das kumulierte Rauschen. Bei einer Tiefe von 7 wird ein Gesamtrauschen von $3,05 \times 10^{-10}$ erreicht, das selbst bei größeren Tiefen niedriger ist als bei Standard-Softmax-Formulierungen.

Bedeutung und Behauptungen

Die Arbeit behauptet, dass CGF-Softmax eine skalierbare und effiziente Lösung für sichere Inferenz in Transformer-basierten Modellen bietet. Durch die Vereinbarkeit hoher Genauigkeit mit erheblich reduzierter multiplikativer Tiefe adressiert es den primären Engpass in HE-basiertem PPML.

Die Autoren betonen, dass zwar Softmax-Ersatzmethoden für kleine Modelle bei einfachen Aufgaben ausreichen mögen, CGF-Softmax jedoch für großskalige Architekturen und komplexe Benchmarks notwendig ist, bei denen bestehende Ersatzmethoden die Genauigkeit nicht aufrechterhalten können. Die Methode ermöglicht vollständig ausgelagerte, nicht-interaktive Inferenz auf großen Modellen (wie LLaMA-3.2-1B) mit Berechnungskosten, die für hochpräzise HE-Inferenz zuvor unerreichbar waren.

Die Arbeit vermerkt bescheiden, dass für relativ kleine Modelle (z. B. BERT) bei einfachen Aufgaben bestehende Ersatzmethoden mit geringer Tiefe möglicherweise noch ausreichen, CGF-Softmax jedoch einen überlegenen Kompromiss für anspruchsvollere Szenarien bietet.