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