acceptodds
Withdrawn from ICLR 2027

ELLMo: Encrypted Transformers with Efficient Linear Algebra and Automated Approximations

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Cloud-based large language model inference exposes sensitive inputs in plaintext. Fully Homomorphic Encryption removes this exposure by computing on encrypted inputs, but its cost keeps encrypted inference impractical for billion-scale models. Two overheads dominate: i) rotations for indexing elements in matrix multiplication in the linear layers, and ii) frequent bootstrapping to support nonlinearities through polynomial approximations. We present ELLMo, a framework for encrypted transformer inference that optimizes both linear and nonlinear layers. First, ELLMo proposes ShallowPCMM, a novel plaintext-ciphertext matrix multiplication algorithm that minimizes rotations and weight memory. Second, ELLMo automates parameter selection for nonlinear layers: it emulates encrypted inference to select the lowest precision the model can tolerate, measures per-layer input ranges, then chooses nonlinear approximations that minimize the number of times bootstrapping is required. On a single NVIDIA A100, ELLMo classifies one encrypted 128-token input in under 58s with BERT-Base and 625s with Llama-3-8B. With ELLMo, Llama-3-8B decodes one token in 80s to 101s at context lengths of 256 to 512, up to 3.1x faster than prior work. Encrypted accuracy and teacher-forced perplexity stay within 0.35% of plaintext on every model. On BERT-Base, ELLMo is 1.1x to 12x faster than prior unamortized systems with 3.2x to 5.2x less weight memory. Source code will be released upon publication.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Fully Homomorphic Encryption, Privacy-Preserving Machine Learning, Large Language Models

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_54W5OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces ELLMo, a secure transformer inference framework via fully homomorphic encryption. Specifically, ELLMo proposes ShallowPCMM to reduces rotations and weight memory, and automates parameter selection for nonlinear operation to minimize the number of bootstrapping. For BERT-Base and Llama-3-8B, the paper reported a 1.1x to 12x speedup and 3.2x to 5.2x less weight memory occupation on a A100 GPU.

Critical strengths
  • This paper raise the GPU memory bottleneck of FHE, which is a critical issue for practical FHE-based tranformer inference that single GPU memory is limited. The strategy is interesting that place all the PCMM at lowest level if the bootstrapping is fast enough.

  • The implementation of sparse encoding and corresponding kernel fusion is a useful engineering contribution. The authors also promise to release their source code upon publication.

Critical weaknesses
  • The main concern is algorithmic novelty of ShallowPCMM that it appears closely relate to standard diagonal decomposition of a plaintext linear transformation under row-major packing. And techniques such as BSGS, hoisting, and sparse plaintext encoding have already been explored in prior work. For the amount of KeySwitch operations in Table 2, where I don't see the advantage of ShallowPCMM over optimized diagonal-BSGS PCMM but the author claims it reduces rotations. The permanformance gains comes from low level and other techniques which should be also applicable to other baselines. Apart from that, ShallowPCMM uses 2 multplicative levels whereas a standard plaintext linear transformation only need 1 level usually. Futhermore, a comparison against baselines with the same optimizations for ShallowPCMM is needed.

  • The second concern is that ELLMo places all PCMM at the lowest level, which means it forces bootstrapping. As the bootstrapping is still the slowest operation in FHE, it is unfair to compare matrix multiplication without denoting the level and further influence of following computation. In addition, the bootstrapping placement, the multiplicative level change and non-linear approximation level consumption are unclear to me, which make it hard to assess the efficiency improvement of ELLMo without the code closure. The improvements currently is not well separated and not distinguished from those of existing techniques, such as hoisting, sparse encoding, and GPU kernel fusion, which make improvement seems like a combination of engineering optimization instead of proposed ShallowPCMM.

Questions for authors
  1. Could the author clarify the advantage and fundamental difference between ShallowPCMM and diagonal-BSGS PCMM with precomputed plaintext diagonals, and compare it to baselines on the same level and applying the same techniques?

  2. Could the authors provide a detailed breakdown of ciphertext levels, bootstrap placements and non-linear approximation consumption for BERT-Base and LLama?

  3. Appendix A.3.3 states that decoding uses BSGS matrix-vector products instead of ShallowPCMM. Could the authors clarify the reported decoding performance gains with ELLMo?

4 comments

We thank the reviewer for the detailed review.

  1. Novelty in SPCMM. We respectfully disagree that SPCMM has no algorithmic novelty. Please see point 1 of our response to the Reviewer toit for the prior work and our novelty.
  2. PCMM at the lowest levels. We agree that this is a trade-off. ELLMo runs every PCMM at the lowest levels to keep the weight memory small. As a result, a bootstrap follows every linear projection in BERT-Base. In return, the encoded weights of BERT-Base take 5.0 GB, against 16.6 GB in CERIUM. The extra bootstraps are included in every end-to-end number: bootstrapping is 30.1 s of the 50.2 s total in Table 10.
  3. Levels and bootstrap placement (Question 2). SPCMM with complex packing uses two levels, and CCMM uses four. A Chebyshev polynomial of degree δ uses about ⌈log2(δ + 1)⌉ levels, and the pre-NR stage uses 2k1 + 2. In BERT-Base, a bootstrap follows every linear projection. In the Llama models, a bootstrap follows every projection except the FFN up projection. The planner places the remaining bootstraps where the level budget runs out.
  4. Decoding (Question 3). The reviewer is correct. In decoding, the weight projections run as BSGS matrix-vector products and not as SPCMM. The decoding performance comes from the CCMM of Section 3.2, the separate calibrated plan, and the GPU kernels. Updated results. We would also like to share our updated results. Please see our response to Reviewer zXSS for a description of these optimizations. The table below updates Table 3. Accuracy is for SST-2, RTE, and QNLI, and F1 is for MRPC, all measured under encryption and averaged over three runs. Latency is for one unamortized 128-token input on an A100 with no model change. Against the state of the art on one A100, ELLMo is faster in all three settings: | Workload | State of the art | Prior (s) | ELLMo (s) | Speedup | |---|---|---|---|---| | BERT-Base, RTE | CERIUM | 66.1 | 44.07 | 1.5x | | Llama-3-8B prefill, 128 tokens | CERIUM | 555 | 491 | 1.1x | | Llama-3-8B decode, 512 context, per layer per token | Cachemir | 3.02 | 2.1 | 1.4x | For the 32 layers of Llama-3-8B, one decoded token takes about 97 s in Cachemir and 66 s in ELLMo.

We present our full results below.

BERT SST-2BERT MRPCBERT RTEBERT QNLI1B SST-21B MRPC8B SST-28B MRPC8B Prefill8B Decode
Plaintext92.320.902669.6790.9995.180.875493.460.827416.95n/a
Encrypted92.320.902669.6790.9995.150.876993.430.829216.98n/a
Latency (s)45.4545.6144.0746.53143.9157.648650249166

Thank you for the clarification and additional result.

My concerns about i) fair comparison to separate SPCMM from bootstrapping placement and other optimization settings, ii) no fundamental advantage or novelty of SPCMM over optimized diagonal-BSGS PCMM, iii) what does 8B Prefill (16.95 and 16.98) stand for in full results table? they remains unresolved.

Also, the main papre's Table 4 present ELLMo as 50.2–57.4s lantency, and here is 44.07s. If this improvement comes from further optimizations, the updated results still do not isolate the contribution of SPCMM, making it even harder to assess its actual benefit.

I appreciate the additional clarification, since my primary concerns remains unresovled, I will maintain my original score.

We thank the reviewer for the reply.

i) Isolating SPCMM. Table 8 in the paper (repeated below) incrementally adds one technique per row within our library. Each product is timed independently at Level 2, ensuring the impact of SPCMM is isolated from bootstrapping placement. For the optimization settings, we apply standard techniques such as hoisting and kernel fusion. A comparison with prior art using this same library is provided in Part (ii). The "+ SPCMM" row introduces only SPCMM, prior to the application of sparse encoding, hoisting, or kernel fusion. By itself, this technique cuts latency by 1.6 to 2.6 due to a reduction in ciphertext-side transforms.

Variant (#KS / ms)×W_Q/K/V×W_O×W_FFN1×W_FFN2
JKLS, complex packing2520 / 1505840 / 5023360 / 19862496 / 1481
+ SPCMM2358 / 913426 / 2413144 / 1208642 / 567
+ Sparse encoding2358 / 702426 / 1723144 / 928642 / 359
+ Hoisting output tiles198 / 280110 / 109222 / 355186 / 262
+ Kernel fusion198 / 76110 / 36222 / 90186 / 71

ii) Comparison with diagonal-BSGS. We reimplemented THOR (diagonal-BSGS), Powerformer, and Tricycle in FIDESlib, verified each against its paper's key-switch counts, and ran each at its lowest level on the same A100. Each implementation used the efficient FIDESlib kernels for dot products and key-switches. Per BERT-Base layer:

SystemTotal #KSTotal (s)ELLMo speedup
THOR15932.3854.7x
Powerformer11951.4352.8x
Tricycle21882.7765.4x
ELLMo17590.510

ELLMo does not issue the fewest keyswitches. Compared to THOR, its benefit lies in lower operational levels: THOR requires 4-5 limbs to start every PCMM, whereas ELLMo requires 2. Compared to Powerformer, all additional keyswitches in ELLMo occur in the baby steps of the BSGS, which are hoisted and therefore incur less cost than a regular rotation. For the second most expensive CKKS primitive, Rescale, ELLMo issues 7.4x fewer operations than Powerformer. This is because ELLMo’s plaintext operations are done offline and stored sparsely at no additional cost due to its repetitive diagonal packing. This is also reflected in the PtMult (plaintext x ciphertext element-wise multiplication) kernel calls. Tricycle also runs at the same low levels as ELLMo, 2 limbs per PCMM, but issues more keyswitches. Although we reimplemented Tricycle based on their published paper, we could not find an open-source GPU implementation; therefore, our implementation may suffer from suboptimalities due to the inaccessibility of all their optimizations.

iii) 8B Prefill column. The numbers in the Llama-3-8B column stand for the WikiText-2 perplexities of Llama-3-8B (teacher-forced, 128-token windows). Encrypted is 0.18% above plaintext.

iv) Updated latency. The drop from 50.2 s to 57.4 s to 44 s to 47 s comes from the post-submission optimizations described in our response to Reviewer zXSS. We kindly ask the reviewer to see our response above.

Thank you for your additional experiment. However, (i) hoisting seems contribute more than SPCMM, the ablation is incomplete. (ii) The advantage cannot be simply attributed to limbs number consumption in case SPCMM don't contribute to it. (iii) diagonal-BSGS consumes 1 level while ELLMo consumes 2 levels, lower operational levels advantage is unconvincing.

The experiments result seems unconvincing for me and my concerns remain unresolved. Therefore, I will maintain my original score.

Reviewer_toitOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

ELLMo targets unamortized CKKS inference on unmodified transformers (BERT-Base, GPT-2, Llama-3.2-1B, and Llama-3-8B) running on a single A100. The system has two parts. The first is ShallowPCMM (SPCMM) and the second is an offline calibrator. The ciphertext only ever gets column shifts, while the plaintext-side transforms are precomputed and stored compactly using CERIUM's SparseEncode. They also provide experimental evaluation to support their claim.

Critical strengths
  • It runs an unmodified Llama-3-8B end-to-end under encryption and reports the accuracy and perplexity, under encryption.
  • There is considerable amount of engineering in this work with very careful combination of building blocks.
  • I also found the ablation to be very useful.
  • I appreciate the checkpoint and revision table and the precise evaluation sizes.
Critical weaknesses

My concerns for the paper are primarily on the novelty.

  1. SPCMM is not new. It is the standard way of multiplying an encrypted matrix by a plain one, with the extra work moved over to the unencrypted side, where it can be done ahead of time. This is already common practice, and many existing systems do exactly this. The one new observation is that the precomputed plaintext has a repeated structure, so an existing compact encoding can be used to store it. The two supporting lemmas are borrowed, and the remaining tricks are also well known. I do not see a new algorithmic insight here.

  2. The complex packing in Section 3.3 comes from Powerformer, with the packing folded into plaintexts that already exist. This is an implementation detail rather than a contribution.

  3. The calibrator is a rule of thumb, not a principled method. The paper makes the search problem sound huge, but nobody would search it that way in the first place. In practice, the calibrator fixes most of the choices up front, uses one precision setting for the whole model, and then makes simple greedy choices one place at a time. This is close to what earlier work already does. The ranges it picks for the inputs are estimates from sample data, with nothing to guarantee they hold. As the paper itself says, if an input falls outside these ranges the output is silently wrong, and this is never tested on data the calibrator has not seen. Finally, the new inverse square root is a well-known way of shrinking the input range before approximating, and nothing about it is new.

  4. I am not convinced that the claimed speedups are actually valid. Table 2 compares ELLMo with THOR, Powerformer, and Tricycle. However, the baseline numbers are taken from each paper on its own hardware and library, and Tricycle's FFN counts are derived from a complexity analysis rather than measured. None of the baselines is re-implemented in FIDESlib with the same level of engineering, so I cannot separate the algorithmic contribution from the quality of the library and kernels.

  5. The headline results are framed selectively. The decoding claim of "up to 3.1x faster than prior work" is against ROSETTA. Against Cachemir, ELLMo is only comparable (101 s vs. about 97 s), and the Cachemir figure is the authors' own extrapolation. The "1.1x faster than CERIUM" claim compares one A100 against CERIUM's reported number under a different configuration. Meanwhile, MOAI, Euston, and STIP are batched, so the same table mixes unamortized and amortized metrics.

  6. I am not convinced ICLR is the right venue. There is essentially no learning component, and calibration on a public dataset is the only part that touches ML. The paper reads as a cryptographic systems paper (CCS, USENIX Security, or an IACR venue), and there its contributions would likely be seen as incremental (look at the next point).

  7. The threat model is minimal. The server is semi-honest, and output leakage and weight confidentiality are out of scope. Leakage of the input length and of the dataset-dependent calibration plan is not discussed.

Questions for authors
  1. What exactly does SPCMM do that a JKLS or Halevi-Shoup PCMM, with all plaintext-side transforms precomputed, does not? Could you compare against such a baseline implemented in FIDESlib with the same hoisting and fusion?
  2. Could you report THOR and Powerformer PCMM re-implemented in your stack, so that the algorithm can be separated from the kernel engineering?
  3. What happens when an input falls outside a calibrated interval, and how often does this happen on held-out datasets or long-context inputs?
  4. How is the per-task calibration plan chosen at inference time without knowing the user's task? Does this leak information?
  5. What are the latency and bootstrap costs with Leff=14L_{\text{eff}} = 14 vs. 10? In other words, what is the true memory/latency trade-off?
1 comment

We thank the reviewer for the detailed review.

  1. Novelty in SPCMM. We respectfully disagree that SPCMM has no new contribution. In prior work, JKLS multiplies matrices with the transforms σ and τ, and the transform on the ciphertext costs rotations and a level. To the best of our knowledge, the closest prior work to Equation 1 is BOLT, which shows a column-packed form in the BFV scheme. CERIUM introduces a sparse encoding for periodic plaintexts. In contrast, the novelty in our work is: (i) a row-major form in CKKS that builds on JKLS. It keeps the transforms φ and τ of JKLS, removes the transform on the ciphertext, and adds a row-select transform ζ on the plaintext (Proposition 3.1). We derived this form using the JKLS blueprint and not any other work. In this form a column shift wraps inside each row and needs a masked double rotation (Section 3.1); (ii) the result that this form and its masks keep the periodic structure, so the d plaintexts of a tile take the space of one under the sparse encoding; (iii) a fused fold for products with many input and output tiles, shown in the ablation of Table 8; and (iv) a GPU implementation that reduces memory accesses and kernel launches.
  2. Novelty in Complex Packing. We respectfully disagree that the complex packing is only an implementation detail. In prior work, Powerformer packs two real matrices into one complex ciphertext, and it packs the outputs in a separate step that costs an extra level. In contrast, the novelty in our work is the fusion of the complex input and output into the BSGS transforms of the whole PCMM pipeline, at no extra level. We do not add the packing to a separate mask outside the BSGS transforms. This has two requirements. The fused plaintexts must stay compatible with the sparse encoding, and the precomputed plaintext memory must not grow; both hold for our formulation.
  3. Novelty in Calibrator. We respectfully disagree that the calibrator is close to earlier work, and that it is never tested on data it has not seen. In prior work, ATLAS searches the approximations automatically, but it minimizes their depth and sets each fit interval to the range measured on a small data subset. The inverse square root is usually computed from a Chebyshev seed refined by Newton-Raphson iterations. In contrast, the novelty in our work is: (i) a search objective of bootstrapped ciphertexts; (ii) fit intervals widened by a tail estimate (Appendix A.4.2); and (iii) to the best of our knowledge, the NR-Chebyshev-NR form of the inverse square root with a checked convergence margin (Appendix A.4.4). We compare against ATLAS in Section 5.1. The calibrator never sees the test data. It uses the training split, and Tables 3 and 5 use the validation and test splits (Appendix A.5.1).
  4. Speedups. To avoid any misrepresentation of the published work due to an incorrect reimplementation, we used the common practice to use the numbers from published work for a fair comparison. When we compare with prior work, we compare the absolute performance numbers in seconds. To address any ambiguity resulting from library differences, we present an ablation study, and we compare against an implementation in our own library without our proposed techniques (first rows of Tables 8 and 9).
  5. Framing. Cachemir is the only comparison without an exact number, because we could not find its implementation details, such as whether the full decoding loop is encrypted or whether parts such as the de-embedding and the argmax run in plaintext. The 3.1x in the abstract is ROSETTA at a 512-token context, 101.1 s against 310.8 s. The CERIUM comparison on BERT-Base uses the same hardware, 57.4 s against 66.1 s on one A100.
  6. Threat model and Question 4. We use the semi-honest model of THOR, Powerformer, and CERIUM. Each task is a separate checkpoint, and the server already knows which model it runs, so the plan leaks nothing about the input.
Reviewer_zXSSOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes ELLMo, a method to make encrypted LLM inference faster and less memory-heavy. ELLMo combines 2 main tricks. First is ShallowPCMM that lowers linear layer computation as well as memory usage. Second is calibration-based nonlinear approximations that reduce bootstrapped ciphertexts with performance guarantee on a given calibration dataset. Together the paper shows that the method is 1.15x faster than the most competitive method with lower memory usage.

Critical strengths

The method is practical and sound and the combination of the two tricks as a single system/method makes a lot of sense.

Critical weaknesses

It's unclear which level of guarantee the calibration would give. Either providing more empirical evidence or some theoretical arguments on "generalization" would help. Also, for the baseline comparisons, it seems that many of the baseline numbers are cited rom their original paper. Given this is a system-level work, it would make me concerned if our improvement is purely because of better implementation or it's because of what we claim here. Having baselines implemented in the same codebase and compare again would make the numbers more reliable.

Questions for authors

Are baseline numbers cited or produced by reimplementation?

1 comment

We thank the reviewer for the review and the positive assessment.

  1. Guarantee of the calibration. The guarantee is statistical. We fit a bounded extreme value distribution to the measured ranges and place each interval edge at a value so that a new input falls outside it with a probability of at most 10^-6 per inference (Appendix A.4.2). This probability is tunable. With about 1,000 calibration samples, it was about 10^-6 in our experiments, and we recommend a smaller value for a larger test set. The second is about the inverse square root, and it holds by construction. Inside the interval, the Newton-Raphson iterations converge for every input, because the calibrator accepts an approximation only if it checks this on the whole interval (Appendix A.4.4). The calibrator never sees the test data. It uses the training split, and Tables 3 and 5 use the validation and test splits, where encrypted results stay within 0.35% of plaintext.
  2. Baseline numbers. The baseline numbers are cited from the published papers. Please see point 4 of our response to the Reviewer toit for further explanation.

Updated results. We would also like to share our updated results to address the remaining weaknesses in our work. We detail our optimizations below.

  1. Bootstrapping. For the rebuttal, we revised the FIDESlib bootstrapping to fuse the affine scaling before the Chebyshev evaluation of the approximate cosine into the earlier CtoS FFT stages. This saves one level and gives about 4 more bits of precision after bootstrapping, because the CtoS linear transform now runs on a smaller scale. During the submission, we used two parameter sets. P1 (used for BERT-Base): 49-bit scaling moduli, a 56-bit first modulus, L = 27 levels (28 limbs), and dnum = 4, giving log PQ = 1739 bits. P2 (others, more precision-hungry models): 53-bit scaling moduli, a 60-bit first modulus, L = 25 levels (26 limbs), and dnum = 5, giving log PQ = 1745 bits. For the rebuttal, the improved bootstrapping lets all models use P1 due to increased precision. BERT-Base stays at P1, so it now runs with 4 more bits of precision and 1 more usable level after each bootstrap. The other models move from P2 to P1. The 4 extra bits make up for the smaller scale (53->49), and the smaller scale fits L = 27 in the same modulus budget, so these models gain 3 usable levels (2 from the longer chain, 1 from the fusion). More usable levels per bootstrap means fewer bootstraps: latency drops by 10% to 23% on BERT-Base and 18% to 24% on the Llama models.

  2. Bootstrapping Placement. We carefully addressed the fixed bootstrapping placement in the calibrator. In some places, such as the gated FFN, we placed the SPCMM of Up at higher levels to save bootstrapping calls, although this resulted in an increase in the memory footprint. Below is an analysis of how the memory scales vs the bootstrapping savings for our configuration:

  3. GPU Optimizations. For the rebuttal, we iterated on our GPU kernel implementations and carefully profiled the parts of memory allocations that are not well-overlapped with computation. We also swept the batching parameters (calling SPCMM kernels on d<{1,d_i} tiles for a d_in x d_i x d_i x d_out SPCMM). These GPU optimizations provided an additional 1.1x speed up on top of the cryptoparameter optimizations.

Against the state of the art on one A100, ELLMo is faster in all three settings:

WorkloadState of the artPrior (s)ELLMo (s)Speedup
BERT-Base, RTECERIUM66.144.071.5x
Llama-3-8B prefill, 128 tokensCERIUM5554911.1x
Llama-3-8B decode, 512 context, per layer per tokenCachemir3.022.11.4x
For the 32 layers of Llama-3-8B, one decoded token takes about 97 s in Cachemir and 66 s in ELLMo.

We present our full results below.

BERT SST-2BERT MRPCBERT RTEBERT QNLI1B SST-21B MRPC8B SST-28B MRPC8B Prefill8B Decode
Plaintext92.320.902669.6790.9995.180.875493.460.827416.95n/a
Encrypted92.320.902669.6790.9995.150.876993.430.829216.98n/a
Latency (s)45.4545.6144.0746.53143.9157.648650249166

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.