Skip to content

Fast and Accurate Homomorphic Softmax Evaluation

Authors: Wonhee Cho; Guillaume Hanrot; Taeseong Kim; Minje Park; Damien Stehlé
Year: 2024
Venue: CCS 2024

type: technique collection: catalogue, sok-references status: auto

Links: DOI · arXiv:2410.11184

Summary

Auto-extracted summary (unreviewed)

The paper introduces a normalize-and-square strategy for evaluating Softmax under CKKS that interleaves exponentiation over a wide input range with cheap partial normalizations, reaching O(log n) multiplicative depth for a fixed range and an amortized O(1 + m/N) depth per ciphertext when many Softmax calls are packed, as in LLM attention. Implemented in HEaaN, it is 2.5-8x faster than prior homomorphic Softmax with about 16-20 bits of precision; 8192 Softmax of dimension 256 take 486 s single-threaded (0.06 s amortized), and all Softmax calls of LLaMA-7B at context length 128 take about 1.5 minutes on an RTX 6000 GPU.

Abstract

Homomorphic encryption is one of the main solutions for building secure and privacy-preserving solutions for Machine Learning as a Service. This motivates the development of homomorphic algorithms for the main building blocks of AI, typically for the components of the various types of neural networks architectures. Among those components, we focus on the Softmax function, defined by $\mathrm{SM}(\mathbf{x}) = \left(\exp(x_i) / \sum_{j=1}^n \exp(x_j) \right)_{1\le i\le n}$. This function is deemed to be one of the most difficult to evaluate homomorphically, because of its multivariate nature and of the very large range of values for $\exp(x_i)$. The available homomorphic algorithms remain restricted, especially in large dimensions, while important applications such as Large Language Models (LLM) require computing Softmax over large dimensional vectors. In terms of multiplicative depth of the computation (a suitable measure of cost for homomorphic algorithms), our algorithm achieves $O(\log n)$ complexity for a fixed range of inputs, where $n$ is the Softmax dimension. Our algorithm is especially adapted to the situation where we must compute many Softmax at the same time, for instance, in the LLM situation. In that case, assuming that all Softmax calls are packed into $m$ ciphtertexts, the asymptotic amortized multiplicative depth cost per ciphertext is, again over a fixed range, $O(1 + m/N)$ for $N$ the homomorphic ring degree. The main ingredient of our algorithms is a normalize-and-square strategy, which interlaces the exponential computation over a large range and normalization, decomposing both in stabler and cheaper smaller steps. Comparing ourselves to the state of the art, our experiments show, in practice, a good accuracy and a gain of a factor 2.5 to 8 compared to state of the art solutions.
Source: arxiv

Extracted details

Field Value Source Confidence
contribution normalize-and-square algorithm for homomorphic Softmax over large input ranges and dimensions llm 0.90
contribution O(log n) multiplicative depth for a fixed input range llm 0.90
contribution many-ciphertext variant with amortized O(1 + m/N) depth per ciphertext for the LLM setting llm 0.90
contribution HEaaN/CKKS implementation with 2.5-8x gain over the state of the art llm 0.90
contribution experiments calibrated on Meta's LLaMA-7B llm 0.90
schemes CKKS llm 0.90
libraries HEaaN llm 0.90
libraries Sollya llm 0.90
models LLaMA-7B llm 0.90
tasks homomorphic Softmax evaluation llm 0.90
tasks private LLM inference (attention) llm 0.90
hardware single-thread CPU llm 0.90
hardware RTX 6000 GPU llm 0.90
security level 128-bit (HEaaN FGb parameter set, N=2^16) llm 0.90
threat model Machine Learning as a Service; server computes on client-encrypted data llm 0.90
interaction non-interactive FHE llm 0.90
limitations near-practicality for LLMs would require dedicated hardware llm 0.90
limitations bootstrapping-free Algorithm 4 is evaluated only on the input range [-128, 0] llm 0.90
llm relevance high llm 0.90
key result speed-up: 2.5x to 8x (vs state-of-the-art homomorphic Softmax) llm 0.90
key result precision: about 16 bits worst case, about 20 bits on average (HEaaN FGb parameters) llm 0.90
key result latency: 486 s total, 0.06 s amortized per Softmax (8192 Softmax of dimension 256, single-thread CPU) llm 0.90
key result latency: about 1.5 minutes (all Softmax calls of 32-layer LLaMA-7B, context length 128, RTX 6000 GPU) llm 0.90
key result latency: under 3 s (final Softmax of dimension 32768 for token generation) llm 0.90
key result bootstrapping time: 17 s (HEaaN FGb, single-thread CPU) llm 0.90

System card: Fast homomorphic Softmax

Group 3. CKKS bootstrapping and operation advances
Family CKKS non-linear evaluation
Arithmetic -
Interaction -
Model scale -
Status Active SOTA
Relation to the SoK Normalize-and-square Softmax used by SplitPrompt and THOR.
Note SoK's recommended model-preserving Softmax algorithm.
Systems page Fast homomorphic Softmax

SoK reference [21]

W. Cho, G. Hanrot, T. Kim, M. Park, and D. Stehl´e, “Fast and accurate homomorphic softmax evaluation,” in ACM CCS 2024: 31st Conference on Computer and Communications Security, B. Luo, X. Liao, J. Xu, E. Kirda, and D. Lie, Eds. Salt Lake City, UT, USA: ACM Press, Oct. 14–18, 2024, pp. 4391–4404.

Listed on the reference page of the site.

Keyword mentions

Counts of vocabulary terms in the full text (first page of occurrence in brackets).

  • scheme: CKKS 23 [p.1], TFHE 3 [p.3], RSA 2 [p.12]
  • library: HEaaN (library) 5 [p.1]
  • model: LLaMA 6 [p.1], Transformer 1 [p.13]
  • hardware: GPU 7 [p.1], Intel Xeon 1 [p.10]
  • technique: Softmax 100 [p.1], Bootstrapping 31 [p.2], Rotations 13 [p.2], Polynomial approximation 10 [p.2], Minimax approximation 5 [p.4], SIMD packing 4 [p.2], Taylor expansion 3 [p.13], Convolution 3 [p.2], ReLU 2 [p.2]
  • task: Language modeling / generation 2 [p.1]
  • topic: Homomorphic encryption 49 [p.1], Large language models 6 [p.1], Privacy-preserving machine learning 3 [p.1], Private / secure inference 2 [p.12]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/catalogue/3-045_fast-and-accurate-homomorphic-softmax-evaluation.pdf catalogue 16 861.2 KB 5f999f828b6f
references/sok-references/021_fast-and-accurate-homomorphic-softmax-evaluation.pdf sok-references 16 861.2 KB 5f999f828b6f byte-identical to references/catalogue/3-045_fast-and-accurate-homomorphic-softmax-evaluation.pdf

Database key: fast-and-accurate-homomorphic-softmax-evaluation · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set fast-and-accurate-homomorphic-softmax-evaluation COLUMN VALUE