Resumo Técnico: CGF-Softmax

Declaração do Problema

A Criptografia Homomórfica (HE) permite a aprendizagem automática que preserva a privacidade, permitindo computação sobre dados criptografados sem descriptografia. No entanto, a implementação de operações não polinomiais, particularmente a função softmax central às arquiteturas Transformer, permanece um gargalo significativo em configurações de HE estritamente não interativas.

A formulação padrão do softmax, $\text{softmax}(x)_i = \frac{\exp(x_i)}{\sum_j \exp(x_j)}$, apresenta três desafios principais em HE:

1. Instabilidade Numérica: A função exponencial causa crescimento rápido, levando ao overflow. A inferência em texto plano padrão mitiga isso subtraindo o valor de entrada máximo ($x_{\max}$), mas a operação de máximo requer lógica de comparação complexa incompatível com HE e necessita de aproximações polinomiais dispendiosas.
2. Operações de Divisão: A etapa de normalização requer divisão, que os esquemas de HE não suportam nativamente. Trabalhos anteriores dependem de aproximações polinomiais iterativas (por exemplo, algoritmo de Goldschmidt ou polinômios de Chebyshev) para funções recíprocas, aumentando drasticamente a profundidade multiplicativa.
3. Custo Computacional: Aproximações polinomiais de alto grau necessárias tanto para as funções exponencial quanto de divisão consomem o orçamento limitado de níveis de esquemas de HE escalonados (como CKKS), frequentemente necessitando de operações custosas de bootstrapping para atualizar os textos cifrados.

As abordagens existentes dividem-se em duas categorias: aproximação de softmax (alta precisão, mas alta profundidade devido à divisão/máximo) e substituição de softmax (baixa profundidade, mas degradação significativa da precisão, especialmente em modelos de grande escala e benchmarks complexos).

Metodologia: CGF-Softmax

Os autores propõem o CGF-Softmax, uma reformulação da função softmax que elimina tanto a divisão homomórfica quanto as operações explícitas de subtração do máximo. A inovação central reside na interpretação do denominador do softmax através da Função Geradora de Cumulantes (CGF).

Reformulação Teórica

Dado um vetor de entrada $x$, os autores interpretam o denominador $\sum \exp(x_i)$ como uma média amostral escalonada de termos exponenciais. Ao substituir a média amostral pela média do conjunto (esperança), o denominador é substituído por $n M_X(1)$, onde $M_X(t)$ é a Função Geradora de Momentos (MGF).

Usando a CGF, definida como $K_X(t) = \ln M_X(t)$, o softmax reformulado é expresso como:
$$\text{softmax}_{\text{CGF}}(x)_i = \exp(x_i - K_X(1) - \ln n)$$

Esta formulação oferece três vantagens críticas:

1. Eliminação da Operação de Máximo: Em vez de subtrair o valor máximo, a entrada é deslocada por $K_X(1) + \ln n$. Como $K_X(1)$ pode ser aproximado usando cumulantes de baixa ordem (média $\mu$ e variância $\sigma^2$), este deslocamento é adaptativo aos dados e computável via operações básicas de HE (adição e multiplicação) sem comparações.
2. Eliminação da Divisão: O termo de normalização é absorvido no expoente. O resultado é uma única função exponencial, removendo a necessidade de divisão homomórfica inteiramente.
3. Escalonamento de Domínio: O método suporta naturalmente o escalonamento de domínio. Ao escalar o expoente por $1/2^k$, a função exponencial é avaliada sobre um intervalo menor, e a escala original é recuperada elevando ao quadrado $k$ vezes. Isso evita o processo iterativo de "normalizar-e-elevar-ao-quadrado" exigido pelo softmax padrão, que envolve divisões repetidas.

Instanciação Prática

Para avaliação prática em HE, os autores adotam uma aproximação de cumulante de segunda ordem:
$$K_X(1) \approx \mu + \frac{\sigma^2}{2}$$
Termos de ordem superior ($\kappa_j/j!$ para $j \ge 3$) são omitidos. Os autores argumentam que o denominador fatorial suprime intrinsecamente esses termos, e o ajuste fino empírico reduz ainda mais a magnitude dos cumulantes de ordem superior, tornando a aproximação suficientemente precisa para inferência.

Contribuições Principais

1. Formulação CGF-Softmax: Uma reformulação inovadora que remove a necessidade de divisão homomórfica e subtração de máximo, reduzindo substancialmente a profundidade multiplicativa.
2. Análise Teórica: O artigo estabelece propriedades-chave do CGF-softmax, incluindo:
   • Positividade: Saídas estritamente positivas.
   • Preservação de Ordem e Razão Par a Par: Preserva a ordenação relativa dos logits e as razões exatas de saída par a par ($\exp(x_i - x_j)$) do softmax padrão.
   • Invariância a Deslocamento: Assim como o softmax padrão, é invariante a deslocamentos constantes.
   • Limite de Erro Assintótico: Usando o teorema de Berry–Esseen, os autores provam que o erro relativo converge para zero em probabilidade à medida que a dimensão de entrada $n$ aumenta.
3. Validação Experimental: Avaliação extensa em Vision Transformers (ViT/DeiT) e Modelos de Linguagem de Grande Escala (LLaMA-3.2-1B) demonstrando alta precisão com custo computacional reduzido.

Resultados Experimentais

Os autores avaliaram o CGF-softmax no ImageNet-1k (Vision Transformers) e em múltiplos benchmarks de NLP (Clinc150, Banking77, SST-2) usando o modelo LLaMA-3.2-1B.

• Profundidade Multiplicativa: O CGF-softmax alcança uma profundidade multiplicativa de 7–10 para modelos de grande escala (por exemplo, LLaMA-3.2-1B, ViT-Base). Em contraste, métodos de aproximação anteriores (por exemplo, Cho et al., EncryptedLLM) requerem profundidades de 14–52 para modelos ou tarefas menores.
• Tempo de Execução: Em uma matriz de entrada de 256×256, o CGF-softmax reduziu a latência total de 107,65s (Cho et al.) para 3,25s, principalmente ao eliminar o bootstrapping e reduzir multiplicações de texto cifrado (CMult).
• Precisão:
  • O CGF-softmax mantém a precisão de inferência dentro de <1% da linha de base exata de softmax em texto plano em todos os benchmarks.
  • Supera significativamente os métodos de substituição de softmax (por exemplo, BPMax), que sofrem quedas substanciais de precisão em tarefas complexas.
  • Alcança precisão próxima à de texto plano enquanto requer 4–6× menos profundidade do que as linhas de base de aproximação de alta precisão.
• Comportamento de Ruído: Ao eliminar a divisão, o CGF-softmax reduz o ruído acumulado. Na profundidade 7, alcança um ruído total de $3,05 \times 10^{-10}$, que é menor do que formulações padrão de softmax mesmo em profundidades maiores.

Significado e Afirmações

O artigo afirma que o CGF-softmax oferece uma solução escalável e eficiente para inferência segura em modelos baseados em Transformer. Ao reconciliar alta precisão com profundidade multiplicativa substancialmente reduzida, aborda o gargalo principal na PPML baseada em HE.

Os autores enfatizam que, embora métodos de substituição de softmax possam ser suficientes para modelos pequenos em tarefas simples, o CGF-softmax é necessário para arquiteturas de grande escala e benchmarks complexos onde substituições existentes falham em manter a precisão. O método permite inferência totalmente terceirizada e não interativa em modelos grandes (como LLaMA-3.2-1B) com custos computacionais anteriormente inatingíveis para inferência HE de alta precisão.

O artigo nota modestamente que, para modelos relativamente pequenos (por exemplo, BERT) em tarefas simples, métodos de substituição de baixa profundidade existentes ainda podem ser suficientes, mas o CGF-softmax oferece um compromisso superior para cenários mais exigentes.