Résumé Technique : CGF-Softmax

Énoncé du Problème

Le Chiffrement Homomorphe (HE) permet l'apprentissage automatique préservant la vie privée en autorisant le calcul sur des données chiffrées sans déchiffrement. Cependant, la mise en œuvre d'opérations non polynomiales, en particulier la fonction softmax centrale aux architectures Transformer, reste un goulot d'étranglement majeur dans les contextes HE strictement non interactifs.

La formulation standard du softmax, $\text{softmax}(x)_i = \frac{\exp(x_i)}{\sum_j \exp(x_j)}$, présente trois défis principaux en HE :

1. Instabilité Numérique : La fonction exponentielle provoque une croissance rapide, entraînant un débordement. L'inférence en clair standard atténue cela en soustrayant la valeur d'entrée maximale ($x_{\max}$), mais l'opération de maximum nécessite une logique de comparaison complexe incompatible avec le HE et exige des approximations polynomiales coûteuses.
2. Opérations de Division : L'étape de normalisation nécessite une division, que les schémas HE ne supportent pas nativement. Les travaux antérieurs s'appuient sur des approximations polynomiales itératives (par exemple, l'algorithme de Goldschmidt ou les polynômes de Tchebychev) pour les fonctions réciproques, augmentant drastiquement la profondeur multiplicative.
3. Coût Computations : Les approximations polynomiales de haut degré requises pour les fonctions exponentielle et de division consomment le budget de niveaux limité des schémas HE à niveaux (comme CKKS), nécessitant souvent des opérations de bootstrapping coûteuses pour rafraîchir les textes chiffrés.

Les approches existantes se divisent en deux catégories : approximation du softmax (haute précision mais profondeur élevée due à la division/maximum) et remplacement du softmax (faible profondeur mais dégradation significative de la précision, en particulier sur les modèles à grande échelle et les benchmarks complexes).

Méthodologie : CGF-Softmax

Les auteurs proposent CGF-Softmax, une reformulation de la fonction softmax qui élimine à la fois la division homomorphe et les opérations explicites de soustraction du maximum. L'innovation centrale réside dans l'interprétation du dénominateur du softmax à travers la Fonction Génératrice des Cumulants (CGF).

Reformulation Théorique

Étant donné un vecteur d'entrée $x$, les auteurs interprètent le dénominateur $\sum \exp(x_i)$ comme une moyenne d'échantillon mise à l'échelle de termes exponentiels. En remplaçant la moyenne d'échantillon par la moyenne d'ensemble (espérance), le dénominateur est remplacé par $n M_X(1)$, où $M_X(t)$ est la Fonction Génératrice des Moments (MGF).

En utilisant la CGF, définie comme $K_X(t) = \ln M_X(t)$, le softmax reformulé s'exprime comme suit :
$$\text{softmax}_{\text{CGF}}(x)_i = \exp(x_i - K_X(1) - \ln n)$$

Cette formulation offre trois avantages critiques :

1. Élimination de l'Opération Max : Au lieu de soustraire la valeur maximale, l'entrée est décalée par $K_X(1) + \ln n$. Puisque $K_X(1)$ peut être approximé à l'aide de cumulants d'ordre inférieur (moyenne $\mu$ et variance $\sigma^2$), ce décalage est adaptatif aux données et calculable via des opérations HE de base (addition et multiplication) sans comparaisons.
2. Élimination de la Division : Le terme de normalisation est absorbé dans l'exposant. Le résultat est une fonction exponentielle unique, éliminant le besoin de division homomorphe.
3. Mise à l'Échelle du Domaine : La méthode prend naturellement en charge la mise à l'échelle du domaine. En mettant l'exposant à l'échelle par $1/2^k$, la fonction exponentielle est évaluée sur un intervalle plus petit, et l'échelle originale est récupérée en élevant au carré $k$ fois. Cela évite le processus itératif « normaliser-et-carrer » requis par le softmax standard, qui implique des divisions répétées.

Réalisation Pratique

Pour l'évaluation pratique en HE, les auteurs adoptent une approximation par cumulants du second ordre :
$$K_X(1) \approx \mu + \frac{\sigma^2}{2}$$
Les termes d'ordre supérieur ($\kappa_j/j!$ pour $j \ge 3$) sont omis. Les auteurs soutiennent que le dénominateur factoriel supprime intrinsèquement ces termes, et que le réglage fin empirique réduit davantage l'amplitude des cumulants d'ordre supérieur, rendant l'approximation suffisamment précise pour l'inférence.

Contributions Clés

1. Formulation CGF-Softmax : Une reformulation novatrice qui supprime le besoin de division homomorphe et de soustraction du maximum, réduisant substantiellement la profondeur multiplicative.
2. Analyse Théorique : L'article établit les propriétés clés du CGF-softmax, notamment :
   • Positivité : Sorties strictement positives.
   • Préservation de l'Ordre et du Rapport Pair : Il préserve l'ordre relatif des logits et les rapports de sortie exacts par paires ($\exp(x_i - x_j)$) du softmax standard.
   • Invariance au Décalage : Comme le softmax standard, il est invariant aux décalages constants.
   • Bornes d'Erreur Asymptotiques : En utilisant le théorème de Berry–Esseen, les auteurs prouvent que l'erreur relative converge vers zéro en probabilité lorsque la dimension d'entrée $n$ augmente.
3. Validation Expérimentale : Évaluation extensive sur des Vision Transformers (ViT/DeiT) et des modèles de langage de grande taille (LLaMA-3.2-1B) démontrant une haute précision avec un coût computationnel réduit.

Résultats Expérimentaux

Les auteurs ont évalué CGF-softmax sur ImageNet-1k (Vision Transformers) et plusieurs benchmarks NLP (Clinc150, Banking77, SST-2) en utilisant le modèle LLaMA-3.2-1B.

• Profondeur Multiplicative : CGF-softmax atteint une profondeur multiplicative de 7–10 pour les modèles à grande échelle (par exemple, LLaMA-3.2-1B, ViT-Base). En revanche, les méthodes d'approximation antérieures (par exemple, Cho et al., EncryptedLLM) nécessitent des profondeurs de 14–52 pour des modèles ou des tâches plus petits.
• Temps d'Exécution : Sur une matrice d'entrée de 256×256, CGF-softmax a réduit la latence totale de 107,65 s (Cho et al.) à 3,25 s, principalement en éliminant le bootstrapping et en réduisant les multiplications de textes chiffrés (CMult).
• Précision :
  • CGF-softmax maintient une précision d'inférence à moins de 1 % de la référence exacte du softmax en clair sur tous les benchmarks.
  • Il surpasse nettement les méthodes de remplacement du softmax (par exemple, BPMax), qui subissent des baisses de précision substantielles sur des tâches complexes.
  • Il atteint une précision proche de celle du clair tout en nécessitant 4–6 fois moins de profondeur que les bases de référence d'approximation haute précision.
• Comportement du Bruit : En éliminant la division, CGF-softmax réduit le bruit accumulé. À une profondeur de 7, il atteint un bruit total de $3,05 \times 10^{-10}$, inférieur aux formulations softmax standard même à des profondeurs plus grandes.

Importance et Revendications

L'article revendique que CGF-softmax offre une solution évolutive et efficace pour l'inférence sécurisée dans les modèles basés sur Transformer. En conciliant haute précision et profondeur multiplicative substantiellement réduite, il adresse le goulot d'étranglement principal du PPML basé sur HE.

Les auteurs soulignent que si les méthodes de remplacement du softmax peuvent suffire pour de petits modèles sur des tâches simples, CGF-Softmax est nécessaire pour les architectures à grande échelle et les benchmarks complexes où les remplacements existants échouent à maintenir la précision. La méthode permet une inférence entièrement externalisée et non interactive sur de grands modèles (comme LLaMA-3.2-1B) avec des coûts computationnels auparavant inatteignables pour une inférence HE haute précision.

L'article note modestement que pour des modèles relativement petits (par exemple, BERT) sur des tâches simples, les méthodes de remplacement à faible profondeur existantes pourraient encore suffire, mais que CGF-Softmax offre un compromis supérieur pour des scénarios plus exigeants.