기술 요약: CGF-Softmax

문제 제기

동형 암호화 (HE) 는 복호화 없이 암호화된 데이터에 대한 연산을 허용함으로써 프라이버시를 보호하는 머신러닝을 가능하게 합니다. 그러나 Transformer 아키텍처의 핵심인 소프트맥스 (softmax) 함수와 같은 비다항식 연산을 구현하는 것은 엄격한 비상호작용 HE 환경에서 여전히 주요 병목 현상으로 남아 있습니다.

표준 소프트맥스 공식 $\text{softmax}(x)_i = \frac{\exp(x_i)}{\sum_j \exp(x_j)}$ 은 HE 환경에서 세 가지 주요 과제를 제시합니다:

1. 수치적 불안정성: 지수 함수는 급격한 증가를 유발하여 오버플로우를 초래합니다. 일반적인 평문 추론은 최대 입력 값 ($x_{\max}$) 을 빼는 방식으로 이를 완화하지만, 최대값 연산은 HE 와 호환되지 않는 복잡한 비교 논리를 요구하며 고비용의 다항식 근사를 필요로 합니다.
2. 나눗셈 연산: 정규화 단계는 나눗셈을 필요로 하는데, HE 방식은 이를 기본적으로 지원하지 않습니다. 기존 연구는 역함수를 위한 반복적 다항식 근사 (예: Goldschmidt 알고리즘 또는 체비셰프 다항식) 에 의존하여 **승법 깊이 (multiplicative depth)**를 급격히 증가시킵니다.
3. 연산 비용: 지수 함수와 나눗셈 함수 모두에 필요한 고차 다항식 근사는 CKKS 와 같은 레벨형 HE 방식의 제한된 레벨 예산을 소모하며, 종종 암호문을 갱신하기 위한 비용이 큰 부트스트래핑 (bootstrapping) 연산을 필요로 합니다.

기존 접근법은 두 가지 범주로 나뉩니다: 소프트맥스 근사 (높은 정확도이지만 나눗셈/최대값으로 인해 높은 깊이) 와 소프트맥스 대체 (낮은 깊이이지만 대규모 모델과 복잡한 벤치마크에서 심각한 정확도 저하).

방법론: CGF-Softmax

저자들은 동형 나눗셈과 명시적인 최대값 빼기 연산을 모두 제거하는 소프트맥스 함수의 재공식화인 CGF-Softmax를 제안합니다. 핵심 혁신은 **누적 생성 함수 (Cumulant Generating Function, CGF)**를 통해 소프트맥스 분모를 해석하는 데 있습니다.

이론적 재공식화

입력 벡터 $x$가 주어졌을 때, 저자들은 분모 $\sum \exp(x_i)$를 지수 항의 스케일링된 표본 평균으로 해석합니다. 표본 평균을 앙상블 평균 (기대값) 으로 대체함으로써, 분모는 $n M_X(1)$로 대체되며, 여기서 $M_X(t)$는 모멘트 생성 함수 (MGF) 입니다.

$K_X(t) = \ln M_X(t)$로 정의된 CGF 를 사용하여 재공식화된 소프트맥스는 다음과 같이 표현됩니다:
$$\text{softmax}_{\text{CGF}}(x)_i = \exp(x_i - K_X(1) - \ln n)$$

이 공식은 세 가지 결정적인 이점을 제공합니다:

1. 최대값 연산 제거: 최대값을 빼는 대신, 입력은 $K_X(1) + \ln n$만큼 이동됩니다. $K_X(1)$은 저차 누적량 (평균 $\mu$와 분산 $\sigma^2$) 을 사용하여 근사할 수 있으므로, 이 이동은 데이터 적응적이며 비교 없이 기본 HE 연산 (덧셈과 곱셈) 으로 계산 가능합니다.
2. 나눗셈 제거: 정규화 항은 지수 내부로 흡수됩니다. 결과는 단일 지수 함수가 되어 동형 나눗셈의 필요성을 완전히 제거합니다.
3. 도메인 스케일링: 이 방법은 자연스럽게 도메인 스케일링을 지원합니다. 지수를 $1/2^k$로 스케일링하면 지수 함수가 더 작은 구간에서 평가되며, 원래 스케일은 $k$번 제곱하여 복구됩니다. 이는 반복적인 나눗셈을 포함하는 표준 소프트맥스에 필요한 반복적인 "정규화 - 제곱" 과정을 피합니다.

실용적 구현

실용적인 HE 평가를 위해 저자들은 2 차 누적량 근사를 채택합니다:
$$K_X(1) \approx \mu + \frac{\sigma^2}{2}$$
3 차 이상의 항 ($j \ge 3$에 대한 $\kappa_j/j!$) 은 생략됩니다. 저자들은 계승 분모가 이러한 항을 본질적으로 억제하며, 경험적 미세 조정이 더 높은 차수의 누적량 크기를 추가로 줄여 근사가 추론에 충분히 정확하다고 주장합니다.

주요 기여

1. CGF-Softmax 공식: 동형 나눗셈과 최대값 빼기의 필요성을 제거하여 승법 깊이를 실질적으로 줄이는 새로운 재공식화.
2. 이론적 분석: CGF-소프트맥스의 주요 속성을 확립합니다.
   • 양수성: 엄격히 양수인 출력.
   • 순서 및 쌍별 비율 보존: 로짓의 상대적 순서와 표준 소프트맥스의 정확한 쌍별 출력 비율 ($\exp(x_i - x_j)$) 을 보존합니다.
   • 이동 불변성: 표준 소프트맥스와 마찬가지로 상수 이동에 대해 불변입니다.
   • 점근적 오차 한계: Berry–Esseen 정리를 사용하여, 입력 차원 $n$이 증가함에 따라 상대 오차가 확률적으로 0 으로 수렴함을 증명합니다.
3. 실험적 검증: 비전 트랜스포머 (ViT/DeiT) 와 대규모 언어 모델 (LLaMA-3.2-1B) 에 대한 광범위한 평가를 통해 높은 정확도와 감소된 연산 비용을 입증했습니다.

실험 결과

저자들은 ImageNet-1k(비전 트랜스포머) 와 여러 NLP 벤치마크 (Clinc150, Banking77, SST-2) 에서 LLaMA-3.2-1B 모델을 사용하여 CGF-소프트맥스를 평가했습니다.

• 승법 깊이: 대규모 모델 (예: LLaMA-3.2-1B, ViT-Base) 의 경우 CGF-소프트맥스는 7–10의 승법 깊이를 달성합니다. 반면, 기존 근사 방법 (예: Cho et al., EncryptedLLM) 은 더 작은 모델이나 작업에서도 14–52의 깊이가 필요합니다.
• 실행 시간: 256×256 입력 행렬에서 CGF-소프트맥스는 부트스트래핑 제거와 암호문 곱셈 (CMult) 감소를 통해 총 지연 시간을 107.65 초(Cho et al.) 에서 3.25 초로 단축했습니다.
• 정확도:
  • CGF-소프트맥스는 모든 벤치마크에서 정확한 평문 소프트맥스 기준 대비 <1% 이내의 추론 정확도를 유지합니다.
  • 복잡한 작업에서 상당한 정확도 저하를 겪는 소프트맥스 대체 방법 (예: BPMax) 보다 훨씬 우수한 성능을 보입니다.
  • 고정밀 근사 기준 대비 4–6 배 적은 깊이를 요구하면서도 평문에 가까운 정확도를 달성합니다.
• 노이즈 동작: 나눗셈을 제거함으로써 CGF-소프트맥스는 누적 노이즈를 줄입니다. 깊이 7 에서 총 노이즈는 $3.05 \times 10^{-10}$으로, 더 큰 깊이에서도 표준 소프트맥스 공식보다 낮습니다.

중요성과 주장

이 논문은 CGF-소프트맥스가 트랜스포머 기반 모델의 안전한 추론을 위한 확장 가능하고 효율적인 솔루션을 제공한다고 주장합니다. 높은 정확도와 실질적으로 감소된 승법 깊이를 조화시킴으로써 HE 기반 프라이버시 보호 머신러닝 (PPML) 의 주요 병목 현상을 해결합니다.

저자들은 작은 모델의 간단한 작업에서는 소프트맥스 대체 방법이 충분할 수 있지만, 기존 대체 방법이 정확도 유지를 실패하는 대규모 아키텍처와 복잡한 벤치마크에서는 CGF-소프트맥스가 필수적이라고 강조합니다. 이 방법은 LLaMA-3.2-1B 와 같은 대규모 모델에 대해 이전에 고정밀 HE 추론에서는 달성 불가능했던 연산 비용으로 완전히 외부 위탁된 비상호작용 추론을 가능하게 합니다.

이 논문은 상대적으로 작은 모델 (예: BERT) 의 간단한 작업에서는 기존 저깊이 대체 방법이 여전히 충분할 수 있음을 겸손하게 지적하지만, CGF-소프트맥스는 더 까다로운 시나리오에 대해 더 우수한 절충안을 제공한다고 명시합니다.