HE-LRM: Encrypted Deep Learning Recommendation Models using Fully Homomorphic Encryption
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.
Nadia: We're looking at the paper: "HE-LRM: Encrypted Deep Learning Recommendation Models using Fully Homomorphic Encryption".
Paper summary: Nadia: We’ve been looking at HE-LRM: Encrypted Deep Learning Recommendation Models using Fully Homomorphic Encryption. To recap, this paper tackles the challenge of performing private lookups into massive embedding tables required by deep learning recommendation models when you are using fully homomorphic encryption.
Elias: The thesis is that existing solutions face significant bottlenecks because exact one-hot lookups require vectors whose length matches the number of rows in each embedding table, which leads to huge data uploads for clients and massive server side memory requirements for the embedding matrices themselves <ref:2506.18150#pg2>.
Priya: So, what's the core claim about how they solve that? Are they just using standard FHE operators directly?
Nadia: No, they propose an embedding compression technique using client side digit decomposition that achieves a fifty-six times speedup over the state of the art <ref:2506.18150#pg1>. They also introduce a multi embedding packing strategy to operate over multiple tables in parallel.
Elias: That packing strategy is key because it’s designed to maximize how much ciphertext slot utilization they get, and this strategy works with both compressed and uncompressed embedding tables.
Priya: That sounds like a system level optimization that tackles the resource constraints of FHE, rather than just focusing on the pure cryptographic primitives.
Nadia: Right. And they also examined two distinct lookup approaches: matrix vector lookup which uses only one multiplicative level, versus column wise table multiplication which introduces ciphertext materialization and packing overhead via an extra multiplicative level <ref:2506.18150#pg3>.
Elias: The trade off there is between simplicity in terms of homomorphic levels and the actual overhead of ciphertext manipulation.
Priya: From a privacy standpoint, if they are doing this compression client side, does that mean the server never sees the original embedding table structure at all?
Nadia: They claim that their client side digit decomposition maps tokens to deterministic coded tokens without needing any hints from the server <ref:2506.18150#pg1>. This is a direct way of mitigating revealing embedding-table structure.
Elias: It’s an orthogonal solution to other approaches, like Private Information Retrieval which relies on different FHE schemes such as BFV or CKKS <ref:2506.18150#pg2>.
Priya: So, HE-LRM is positioned as a holistic architecture that addresses the communication and memory bottlenecks inherent in applying FHE to sparse recommendation models.
Nadia: It is presented as the first end to end FHE encrypted DLRM architecture supporting both dense and sparse features under FHE <ref:2506.18150#pg1>.
Elias: The main takeaway from this summary is that the bottleneck for encrypted DLRMs isn't just homomorphic latency, but also managing system level resources like memory and communication costs <ref:2506.18150#pg2>.
Conclusion: Nadia: So we've covered a lot on HE-LRM: Encrypted Deep Learning Recommendation Models using Fully Homomorphic Encryption. We’ve discussed the embedding compression, the lookup strategies, and how this fits into the broader picture of FHE for neural inference.
Elias: The authors argue that this work provides a performance optimized solution by combining client side digit decomposition with a block diagonal packing strategy to maximize ciphertext slot utilization.
Priya: From what I’ve gathered, the implication is that we can move beyond naive solutions where compression leaks correlations to the client, instead using deterministic mapping for speed and privacy.
Nadia: That’s right. And they show that even with these optimizations, hardware acceleration on GPUs and ASICs can reduce end to end latencies from minutes down to seconds or even sub second times <ref:2506.18150#pg3>.
Elias: The paper highlights that the system level costs, like key switching and bootstrapping in CKKS, remain very high, but the HE-LRM approach is designed to manage those costs more effectively for DLRMs.
Priya: So what does this mean for someone who only listens to the show? It means that while FHE inference is still slow on a CPU, these architectural solutions are making it feasible to run complex recommendation models in the cloud with user data remaining encrypted.
Nadia: Exactly. And they’ve also pointed out that supporting both prefill and autoregressive decoding lookups efficiently under FHE is a major future direction for work.
Elias: It suggests that encrypted embedding lookup is a broader systems primitive for private inference, not just recommendation models, and it could apply to transformer based language models too.
Priya: So, the work shifts the focus from just making the math work to designing an entire system around minimizing those specific FHE system level costs.
New York University · LG Electronics USA, Inc.
cs.CR
Submitted: 2025-06-22
Updated: 2026-11-17
Comments: 16 pages, 12 figures, 2 tables. Akshath Mahajan and Karthik Garimella contributed equally
Code: https://github.com/baahl-nyu/orion
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 97/100
The gist: Fully Homomorphic Encryption (FHE) enables computation directly on encrypted data and privacy-preserving neural inference in the cloud The paper presents HE-LRM…
Key concepts
- Fully Homomorphic Encryption (FHE)
- A cryptographic technique that allows computations to be performed directly on encrypted data without ever decrypting it. This ensures complete privacy, as the server processes the sensitive information while it remains scrambled. It enables complex mathematical operations like addition and multiplication on these encrypted values.
- Embedding Compression
- A client-side technique used to reduce the size of embedding vectors before encryption. By mapping original tokens to smaller, deterministic coded tokens using digit decomposition, this method significantly shrinks the data that needs to be processed in FHE, leading to a 56x speedup.
- Matrix-Vector Lookup
- One optimization strategy for finding a dense vector from an encrypted embedding matrix. This approach performs a dense matrix-vector product using only one multiplicative level, which is computationally efficient and minimizes the overhead associated with accessing the correct row in the encrypted table.
- Bootstrapping
- The most computationally demanding operation within FHE schemes like CKKS. It is necessary to refresh or 're-encrypt' ciphertexts to prevent noise accumulation during complex computations. This process is extremely slow, taking about 20 seconds on a single-threaded CPU.
Terminology
Summary
Fully Homomorphic Encryption (FHE) enables computation directly on encrypted data and privacy-preserving neural inference in the cloud The paper presents HE-LRM, a performance optimized solution for executing recommendation with FHE
The Core Challenge
Deep Learning Recommendation Models (DLRMs) pose a different challenge than models with dense inputs because sparse categorical inputs require private lookups into large embedding tables, which must be implemented using FHE’s restrictive operators In the cleartext setting, performing the embedding table lookups in DLRMs is as simple as indexing into the correct row for each of the embedding matrices and concatenating the output vectors However, in a ciphertext setting, we must now perform encrypted indexing under the constraints of FHE The standard workaround is to replace the lookup with a one-hot selector multiplied by the embedding table
Embedding Compression and Packing
The authors introduce an FHE-friendly embedding compression technique using client-side digit decomposition that achieves 56× speedup over the state-of-the-art This technique maps original embedding tokens to deterministic coded tokens via digit decomposition that may be done client-side without any hints from the server Furthermore, they propose a block-diagonal packing strategy to operate over multiple embedding tables in a parallel fashion, ensuring that we maximize ciphertext slot utilization This strategy is interoperable with both compressed and uncompressed embedding tables
Lookup Optimization Strategies
The paper examines two orthogonal approaches to extracting the correct dense vector from an embedding matrix given the encrypted one-hot selector The first is Matrix-Vector Lookup, which performs a dense matrix-vector product, consuming only one multiplicative level The second is Column-Wise Table Multiplication, which introduces ciphertext materialization and packing overhead by requiring an extra multiplicative level
Performance and Results
HE-LRM was evaluated on the UCI Heart Disease and Criteo click-through rate datasets On a single-threaded CPU, it achieved inference latencies of 24 seconds on UCI and 228 to 489 seconds, respectively, on Criteo The authors show that GPU and ASIC FHE acceleration can reduce end-to-end latencies to seconds and even sub-seconds
Key Contributions
The paper makes three main contributions
-
HE-LRM: the first end-to-end FHE encrypted DLRM architecture supporting both dense and sparse features under FHE
-
An FHE-friendly embedding compression scheme that outperforms prior work [10] by 56× through client-side digit-decomposition
-
A block-diagonal embedding packing strategy to perform parallel lookups across multiple embedding tables, maximizing ciphertext slot utilization while remaining compatible with a state-of-the-art FHE linear transformation called baby-step giant-step (BSGS)
Future Directions
The work suggests that encrypted embedding lookup is a broader systems primitive for private inference beyond recommendation models It notes that Transformer-based language models also rely on embedding matrices, and supporting both prefill and autoregressive decoding lookups efficiently under FHE remains an important direction for future work
Hardware Acceleration Impact
The paper demonstrates that even GPU acceleration provides roughly 200× speedup over CPU, bringing previously impractical runtimes from minutes down to seconds The ASIC maintains sub-second latency at approximately 0.037 seconds for the least compressed model
Training Dynamics
Training DLRMs on the Criteo dataset showed that all models follow similar training dynamics and fall naturally on the loss spectrum based on the compression ratio The authors also found that SiLU networks exhibit both lower test AUC and higher training losses compared to ReLU-based models, introducing a latency-performance tradeoff
FHE Scheme Details
CKKS encrypts large floating-point vectors of a fixed power-of-two length and enables SIMD addition, SIMD multiplication, and cyclic rotation upon these encrypted vectors Bootstrapping is the most computationally expensive CKKS operation, taking roughly 20 seconds on a single-threaded CPU
System-Level Costs
CKKS operations are both compute and memory intensive, and they require special evaluation keys for key-switching during ciphertext-ciphertext multiplication or rotation The paper highlights that the communication cost of sending encrypted selectors can become comparable to expensive homomorphic operations such as bootstrapping
Related Work Context
Prior work like Kim et al. [10] performs one-hot index encoding serverside but requires additional homomorphic operations that incur a high latency penalty, i. p. 1 The prior work of
Kim et al. [10] perform the one-hot index encoding serverside to mitigate uploading sparse ciphertexts but requires
additional homomorphic operations server-side that incur a
high latency penalty (i.Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
FHE-LRM can perform end-to-end encrypted inference of Deep Learning Recommendation Models (DLRMs) by developing an FHE friendly embedding compression technique that achieves up to 56 times speedup over prior work. This allows for private DLRM inference on industry-scale datasets like Criteo, where naive solutions incur massive communication and memory costs.
-
The system can execute private lookups into large embedding tables by proposing a block-diagonal packing strategy to operate over multiple tables in parallel, maximizing ciphertext slot utilization while remaining compatible with the baby-step giant-step linear transformation. This enables efficient processing of models with numerous sparse features simultaneously within a single packed matrix-vector product.
-
The AI system can handle complex neural network operations by implementing an FHE friendly embedding compression scheme that maps original embedding tokens to deterministic coded tokens via client-side digit decomposition, consuming only one multiplicative level for the lookup operation. This reduces the reliance on expensive bootstrapping compared to prior work that required many levels or high multiplicative depth.
-
The system can maintain data privacy while performing lookups by allowing clients to construct an FHE friendly embedding compression technique locally without any hints from the server, ensuring
the client only needs to know the size of these compressed tables to perform private twoparty inference.
This adheres to a semi-honest threat model where the client does not leak embedding tables. -
The system can achieve practical deployment on hardware by projecting performance using state-of-the-art GPU and ASIC FHE accelerators, showing that hardware acceleration can reduce end-to-end encrypted DLRM inference to seconds or even subseconds. This demonstrates that privacy preserving recommendation systems are approaching practical deployment targets.
-
The system can adapt its level management policy based on activation functions by showing that SiLU based models require just 5 bootstrap operations whereas ReLU based models require 12, leading to lower overall FHE latencies for specific network architectures. This allows the system to optimize the trade-off between accuracy and latency by selecting smoother activation functions.
Abstract
FHE inference systems primarily target models with dense inputs, while Deep Learning Recommendation Models (DLRMs) contain sparse categorical features that require lookups into embedding tables. Encrypted lookups are challenging because indexing is not natively supported and must be expressed using SIMD arithmetic. A direct one-hot formulation does not scale. Prior work addresses parts of this problem through embedding compression or compact encrypted queries. However, it does not address complete DLRM inference, leaving open how private lookup interacts with downstream computation and memory constraints. We present HE-LRM, the first end-to-end FHE system for private DLRM inference. We use deterministic compositional embedding compression with client-side digit decomposition, avoiding expensive homomorphic selector construction while consuming only one multiplicative level. We further develop a block-diagonal packing strategy that performs lookups across multiple embedding tables using optimized BSGS linear transformations and produces encrypted embeddings directly compatible with downstream inference. We extend Orion with a high-performance GPU backend and achieve 9 ms for single-inference embedding lookup. We also show that GPU memory capacity limits batching and therefore the latency-bound throughput in such systems. On Criteo, HE-LRM achieves complete encrypted inference with server-side latencies of 154-247 ms on a single GPU. We open-source HE-LRM at https://github.com/baahl-nyu/orion
Sources
- The Architectural Implications of Facebook's DNN-based Personalized Recommendation
- Deep Learning Recommendation Model for Personalization and Recommendation Systems
- Attention Is All You Need
- Osiris: A Systolic Approach to Accelerating Fully Homomorphic Encryption
- TT-Rec: Tensor Train Compression for Deep Learning Recommendation Models
- Privacy-Preserving Text Classification on BERT Embeddings with Homomorphic Encryption
- THE-X: Privacy-Preserving Transformer Inference with Homomorphic Encryption
- DQRM: Deep Quantized Recommendation Models
- Post-Training 4-bit Quantization on Embedding Tables
- Learning to Collide: Recommendation System Model Compression with Learned Hash Functions
- TenSEAL: A Library for Encrypted Tensor Operations Using Homomorphic Encryption
- SEALion: a Framework for Neural Network Inference on Encrypted Data
- HeLayers: A Tile Tensors Framework for Large Neural Networks on Encrypted Data
Related papers
- From Strategy Search to Policy Learning: MCTS-Guided Adversarial Co-Evolution for LLM Safety Alignment
- Privacy Leakage from Recurrent State in LLM Inference
- Incrementally Verifiable Oracle Aided Computation
- Privilege and confidentiality in generative AI workflows
- BadMoE: Backdooring Mixture-of-Experts LLMs via Routing-Aware Triggers and Task-Underutilized Experts
- CoVault: Secure, Scalable Analytics of Personal Data