Riepilogo Tecnico: CGF-Softmax

Enunciato del Problema

La Crittografia Omomorfica (HE) abilita l'apprendimento automatico che preserva la privacy consentendo il calcolo su dati cifrati senza decrittazione. Tuttavia, l'implementazione di operazioni non polinomiali, in particolare la funzione softmax centrale nelle architetture Transformer, rimane un collo di bottiglia significativo in contesti HE strettamente non interattivi.

La formulazione standard della softmax, $\text{softmax}(x)_i = \frac{\exp(x_i)}{\sum_j \exp(x_j)}$, presenta tre sfide principali in HE:

1. Instabilità Numerica: La funzione esponenziale causa una rapida crescita, portando a overflow. L'inferenza in testo normale standard mitiga ciò sottraendo il valore di ingresso massimo ($x_{\max}$), ma l'operazione di massimo richiede una logica di confronto complessa incompatibile con HE e necessita di costose approssimazioni polinomiali.
2. Operazioni di Divisione: Il passo di normalizzazione richiede la divisione, che gli schemi HE non supportano nativamente. Lavori precedenti si affidano ad approssimazioni polinomiali iterative (ad esempio, l'algoritmo di Goldschmidt o i polinomi di Chebyshev) per le funzioni reciproche, aumentando drasticamente la profondità moltiplicativa.
3. Costo Computazionale: Le approssimazioni polinomiali di alto grado richieste sia per la funzione esponenziale che per la divisione consumano il budget di livelli limitato degli schemi HE a livelli (come CKKS), spesso rendendo necessarie costose operazioni di bootstrapping per aggiornare i testi cifrati.

Gli approcci esistenti rientrano in due categorie: approssimazione della softmax (alta accuratezza ma alta profondità a causa di divisione/massimo) e sostituzione della softmax (bassa profondità ma significativa degradazione dell'accuratezza, specialmente su modelli su larga scala e benchmark complessi).

Metodologia: CGF-Softmax

Gli autori propongono CGF-Softmax, una riformulazione della funzione softmax che elimina sia la divisione omomorfica che le operazioni esplicite di sottrazione del massimo. L'innovazione fondamentale risiede nell'interpretare il denominatore della softmax attraverso la Funzione Generatrice dei Cumulanti (CGF).

Riformulazione Teorica

Dato un vettore di ingresso $x$, gli autori interpretano il denominatore $\sum \exp(x_i)$ come una media campionaria scalata di termini esponenziali. Sostituendo la media campionaria con la media dell'insieme (valore atteso), il denominatore è sostituito da $n M_X(1)$, dove $M_X(t)$ è la Funzione Generatrice dei Momenti (MGF).

Utilizzando la CGF, definita come $K_X(t) = \ln M_X(t)$, la softmax riformulata è espressa come:
$$\text{softmax}_{\text{CGF}}(x)_i = \exp(x_i - K_X(1) - \ln n)$$

Questa formulazione offre tre vantaggi critici:

1. Eliminazione dell'Operazione di Massimo: Invece di sottrarre il valore massimo, l'ingresso è spostato di $K_X(1) + \ln n$. Poiché $K_X(1)$ può essere approssimato utilizzando cumulanti di basso ordine (media $\mu$ e varianza $\sigma^2$), questo spostamento è adattivo ai dati e calcolabile tramite operazioni HE di base (addizione e moltiplicazione) senza confronti.
2. Eliminazione della Divisione: Il termine di normalizzazione è assorbito nell'esponente. Il risultato è una singola funzione esponenziale, eliminando la necessità di divisione omomorfica.
3. Scalatura del Dominio: Il metodo supporta naturalmente la scalatura del dominio. Scalando l'esponente per $1/2^k$, la funzione esponenziale è valutata su un intervallo più piccolo, e la scala originale è recuperata elevando al quadrato $k$ volte. Ciò evita il processo iterativo "normalizza-e-quadra" richiesto dalla softmax standard, che comporta divisioni ripetute.

Istanteazione Pratica

Per la valutazione pratica HE, gli autori adottano un'approssimazione del cumulante del secondo ordine:
$$K_X(1) \approx \mu + \frac{\sigma^2}{2}$$
I termini di ordine superiore ($\kappa_j/j!$ per $j \ge 3$) sono omessi. Gli autori sostengono che il denominatore fattoriale sopprima intrinsecamente questi termini, e l'ottimizzazione empirica riduce ulteriormente la grandezza dei cumulanti di ordine superiore, rendendo l'approssimazione sufficientemente accurata per l'inferenza.

Contributi Chiave

1. Formulazione CGF-Softmax: Una riformulazione innovativa che rimuove la necessità di divisione omomorfica e sottrazione del massimo, riducendo sostanzialmente la profondità moltiplicativa.
2. Analisi Teorica: Il documento stabilisce le proprietà chiave della softmax-CGF, tra cui:
   • Positività: Output strettamente positivi.
   • Preservazione dell'Ordine e del Rapporto Coppia: Preserva l'ordinamento relativo dei logit e i rapporti di output esatti tra coppie ($\exp(x_i - x_j)$) della softmax standard.
   • Invarianza allo Spostamento: Come la softmax standard, è invariante rispetto a spostamenti costanti.
   • Limite di Errore Asintotico: Utilizzando il teorema di Berry–Esseen, gli autori dimostrano che l'errore relativo converge a zero in probabilità all'aumentare della dimensione dell'ingresso $n$.
3. Validazione Sperimentale: Valutazione estesa su Vision Transformers (ViT/DeiT) e Large Language Models (LLaMA-3.2-1B) che dimostra alta accuratezza con costi computazionali ridotti.

Risultati Sperimentali

Gli autori hanno valutato CGF-softmax su ImageNet-1k (Vision Transformers) e su molteplici benchmark NLP (Clinc150, Banking77, SST-2) utilizzando il modello LLaMA-3.2-1B.

• Profondità Moltiplicativa: CGF-softmax raggiunge una profondità moltiplicativa di 7–10 per modelli su larga scala (ad esempio, LLaMA-3.2-1B, ViT-Base). Al contrario, i precedenti metodi di approssimazione (ad esempio, Cho et al., EncryptedLLM) richiedono profondità di 14–52 per modelli o compiti più piccoli.
• Tempo di Esecuzione: Su una matrice di ingresso 256×256, CGF-softmax ha ridotto la latenza totale da 107,65s (Cho et al.) a 3,25s, principalmente eliminando il bootstrapping e riducendo le moltiplicazioni di testo cifrato (CMult).
• Accuratezza:
  • CGF-softmax mantiene l'accuratezza dell'inferenza entro <1% rispetto alla baseline esatta della softmax in testo normale su tutti i benchmark.
  • Supera significativamente i metodi di sostituzione della softmax (ad esempio, BPMax), che soffrono di sostanziali cali di accuratezza su compiti complessi.
  • Raggiunge un'accuratezza vicina a quella in testo normale richiedendo 4–6 volte meno profondità rispetto alle baseline di approssimazione ad alta precisione.
• Comportamento del Rumore: Eliminando la divisione, CGF-softmax riduce il rumore accumulato. A profondità 7, raggiunge un rumore totale di $3.05 \times 10^{-10}$, che è inferiore alle formulazioni standard della softmax anche a profondità maggiori.

Significato e Affermazioni

Il documento afferma che CGF-softmax offre una soluzione scalabile ed efficiente per l'inferenza sicura in modelli basati su Transformer. Conciliando alta accuratezza con una sostanziale riduzione della profondità moltiplicativa, affronta il principale collo di bottiglia nel PPML basato su HE.

Gli autori sottolineano che, sebbene i metodi di sostituzione della softmax possano essere sufficienti per modelli piccoli su compiti semplici, CGF-softmax è necessario per architetture su larga scala e benchmark complessi dove le sostituzioni esistenti non riescono a mantenere l'accuratezza. Il metodo abilita inferenze completamente esternalizzate e non interattive su modelli grandi (come LLaMA-3.2-1B) con costi computazionali precedentemente irraggiungibili per inferenze HE ad alta accuratezza.

Il documento nota con modestia che per modelli relativamente piccoli (ad esempio, BERT) su compiti semplici, i metodi di sostituzione a bassa profondità esistenti potrebbero essere ancora sufficienti, ma CGF-Softmax offre un compromesso superiore per scenari più esigenti.