Technische Samenvatting: CGF-Softmax

Probleemstelling

Homomorf Versleuteling (HE) maakt privacybehoudend machine learning mogelijk door berekeningen op versleutelde data uit te voeren zonder decryptie. Het implementeren van niet-polynomiale operaties, met name de softmax-functie die centraal staat in Transformer-architecturen, blijft echter een aanzienlijke bottleneck in strikt niet-interactieve HE-omgevingen.

De standaard softmax-formulering, $\text{softmax}(x)_i = \frac{\exp(x_i)}{\sum_j \exp(x_j)}$, presenteert drie hoofduitdagingen in HE:

1. Numerieke Instabiliteit: De exponentiële functie veroorzaakt snelle groei, wat leidt tot overflow. Standaard inferentie in platte tekst mitigeert dit door de maximale invoerwaarde ($x_{\max}$) af te trekken, maar de maximale operatie vereist complexe vergelijkingslogica die incompatibel is met HE en kostbare polynomiale benaderingen noodzakelijk maakt.
2. Delingsoperaties: De normalisatiestap vereist deling, wat door HE-schema's niet natief wordt ondersteund. Eerdere werken vertrouwen op iteratieve polynomiale benaderingen (bijvoorbeeld het algoritme van Goldschmidt of Chebyshev-polynomen) voor reciproke functies, wat de multiplicatieve diepte drastisch verhoogt.
3. Berekeningskosten: Hoogwaardige polynomiale benaderingen die nodig zijn voor zowel de exponentiële als de delingsfuncties, verbruiken het beperkte niveau-budget van op niveau gebaseerde HE-schema's (zoals CKKS), wat vaak kostbare bootstrapping-operaties vereist om ciphertexts te verversen.

Bestaande benaderingen vallen in twee categorieën: softmax-benadering (hoge nauwkeurigheid maar hoge diepte door deling/max) en softmax-vervanging (lage diepte maar aanzienlijke degradatie van de nauwkeurigheid, vooral bij grootschalige modellen en complexe benchmarks).

Methodologie: CGF-Softmax

De auteurs stellen CGF-Softmax voor, een herformulering van de softmax-functie die zowel de homomorfe deling als de expliciete aftrekking van het maximum elimineert. De kerninnovatie ligt in het interpreteren van de softmax-nominator via de Cumulant Generating Function (CGF).

Theoretische Herformulering

Gegeven een invoervector $x$, interpreteren de auteurs de nominator $\sum \exp(x_i)$ als een geschaald steekproefgemiddelde van exponentiële termen. Door het steekproefgemiddelde te vervangen door het ensemble-gemiddelde (verwachting), wordt de nominator vervangen door $n M_X(1)$, waarbij $M_X(t)$ de Moment Generating Function (MGF) is.

Met behulp van de CGF, gedefinieerd als $K_X(t) = \ln M_X(t)$, wordt de herformuleerde softmax uitgedrukt als:
$$\text{softmax}_{\text{CGF}}(x)_i = \exp(x_i - K_X(1) - \ln n)$$

Deze formulering biedt drie kritieke voordelen:

1. Eliminatie van de Max-Operatie: In plaats van de maximale waarde af te trekken, wordt de invoer verschoven met $K_X(1) + \ln n$. Aangezien $K_X(1)$ kan worden benaderd met behulp van cumulanten van lage orde (gemiddelde $\mu$ en variantie $\sigma^2$), is deze verschuiving data-adaptief en berekenbaar via basis HE-operaties (optelling en vermenigvuldiging) zonder vergelijkingen.
2. Eliminatie van Deling: De normalisatieterm wordt geabsorbeerd in de exponent. Het resultaat is een enkele exponentiële functie, waardoor de noodzaak voor homomorfe deling volledig wordt verwijderd.
3. Schaal van het Domein: De methode ondersteunt op natuurlijke wijze schaalvergroting van het domein. Door de exponent te schalen met $1/2^k$, wordt de exponentiële functie geëvalueerd over een kleiner interval, en wordt de oorspronkelijke schaal hersteld door $k$ keer te kwadrateren. Dit vermijdt het iteratieve "normaliseren-en-kwadrateren"-proces dat nodig is bij standaard softmax, wat herhaalde delingen vereist.

Praktische Instantiatie

Voor praktische HE-evaluatie hanteren de auteurs een benadering van cumulanten van de tweede orde:
$$K_X(1) \approx \mu + \frac{\sigma^2}{2}$$
Hogere-orde termen ($\kappa_j/j!$ voor $j \ge 3$) worden weggelaten. De auteurs betogen dat de faculteit in de noemer deze termen intrinsiek onderdrukt, en dat empirische fine-tuning de grootte van cumulanten van hogere orde verder verkleint, waardoor de benadering nauwkeurig genoeg is voor inferentie.

Belangrijkste Bijdragen

1. CGF-Softmax Formulier: Een nieuwe herformulering die de behoefte aan homomorfe deling en aftrekking van het maximum verwijdert, wat de multiplicatieve diepte aanzienlijk verlaagt.
2. Theoretische Analyse: Het artikel vestigt belangrijke eigenschappen van CGF-softmax, waaronder:
   • Positiviteit: Strikt positieve uitkomsten.
   • Behoud van Orde en Paarsgewijze Ratio's: Het behoudt de relatieve volgorde van logits en de exacte paarsgewijze uitkomstverhoudingen ($\exp(x_i - x_j)$) van standaard softmax.
   • Shift-invariantie: Net als standaard softmax is het invariant voor constante verschuivingen.
   • Asymptotische Foutgrens: Met behulp van de Berry–Esseen-stelling bewijzen de auteurs dat de relatieve fout in waarschijnlijkheid convergeert naar nul naarmate de invoerdimensie $n$ toeneemt.
3. Experimentele Validatie: Uitgebreide evaluatie op Vision Transformers (ViT/DeiT) en Large Language Models (LLaMA-3.2-1B) die hoge nauwkeurigheid demonstreren met verminderde berekeningskosten.

Experimentele Resultaten

De auteurs hebben CGF-softmax geëvalueerd op ImageNet-1k (Vision Transformers) en meerdere NLP-benchmarks (Clinc150, Banking77, SST-2) met het LLaMA-3.2-1B-model.

• Multiplicatieve Diepte: CGF-softmax bereikt een multiplicatieve diepte van 7–10 voor grootschalige modellen (bijvoorbeeld LLaMA-3.2-1B, ViT-Base). In tegenstelling hiermee vereisen eerdere benaderingsmethoden (bijvoorbeeld Cho et al., EncryptedLLM) dieptes van 14–52 voor kleinere modellen of taken.
• Uitvoeringstijd: Op een invoermatrix van 256×256 verlaagde CGF-softmax de totale latentie van 107,65s (Cho et al.) naar 3,25s, voornamelijk door het elimineren van bootstrapping en het verminderen van ciphertext-vermenigvuldigingen (CMult).
• Nauwkeurigheid:
  • CGF-softmaint behoudt de inferentenauwkeurigheid binnen <1% van de exacte baseline van plaintext softmax over alle benchmarks.
  • Het presteert aanzienlijk beter dan softmax-vervangingsmethoden (bijvoorbeeld BPMax), die te kampen hebben met aanzienlijke dalingen in nauwkeurigheid bij complexe taken.
  • Het bereikt bijna-platte-tekstnauwkeurigheid terwijl het 4–6× minder diepte vereist dan baselines voor hoogwaardige benaderingen.
• Gedrag van Ruis: Door deling te elimineren, vermindert CGF-softmax de geaccumuleerde ruis. Bij een diepte van 7 bereikt het een totale ruis van $3.05 \times 10^{-10}$, wat lager is dan standaard softmax-formuleringen zelfs bij grotere dieptes.

Betekenis en Claims

Het artikel stelt dat CGF-softmax een schaalbare en efficiënte oplossing biedt voor veilige inferentie in op Transformer gebaseerde modellen. Door hoge nauwkeurigheid te verzoenen met aanzienlijk verminderde multiplicatieve diepte, adresseert het de primaire bottleneck in HE-gebaseerd PPML.

De auteurs benadrukken dat hoewel softmax-vervangingsmethoden misschien volstaan voor kleine modellen op eenvoudige taken, CGF-softmax noodzakelijk is voor grootschalige architecturen en complexe benchmarks waar bestaande vervangingen falen om de nauwkeurigheid te handhaven. De methode maakt volledig uitbesteede, niet-interactieve inferentie mogelijk op grote modellen (zoals LLaMA-3.2-1B) met berekeningskosten die voorheen onbereikbaar waren voor inferentie met HE en hoge nauwkeurigheid.

Het artikel merkt bescheiden op dat voor relatief kleine modellen (bijvoorbeeld BERT) op eenvoudige taken, bestaande vervangingsmethoden met lage diepte misschien nog steeds voldoende zijn, maar dat CGF-softmax een superieure afweging biedt voor veeleisendere scenario's.