Technical Summary: HE-LRM

Problem Statement

Fully Homomorphic Encryption (FHE) enables privacy-preserving neural inference on encrypted data, yet existing solutions primarily address models with dense inputs (e.g., CNNs, MLPs). Deep Learning Recommendation Models (DLRMs) present a distinct challenge due to their reliance on large, sparse categorical inputs processed through massive embedding tables.

In a standard DLRM, sparse features are mapped to dense vectors via embedding table lookups. In an FHE context (specifically using the CKKS scheme), direct indexing is not natively supported; only SIMD addition, multiplication, and cyclic rotation are available. Naive approaches to encrypted lookups face severe scalability issues:

1. Communication Overhead: A "one-hot" encoding of an index for a table with $k$ rows requires a vector of size $k$. For industry-scale datasets like Criteo (33.8 million rows), this necessitates uploading over 1,000 ciphertexts (>1 GiB) per inference.
2. Server-Side Compute Costs: Prior work (e.g., Kim et al. [10]) attempts to mitigate upload costs by having the server construct the one-hot selector from an encrypted index. However, this requires deep arithmetic circuits (indicator functions) that consume significant multiplicative depth, often necessitating expensive bootstrapping operations.
3. Memory and Structure Leakage: Existing compression techniques often require the client to store learned code mappings (revealing embedding correlations) or result in inefficient slot utilization and high memory footprints on the server.

Methodology: HE-LRM

The authors propose HE-LRM, an end-to-end FHE system optimized for DLRM inference. The solution addresses the embedding lookup bottleneck through three core technical innovations:

1. Client-Side Digit Decomposition Compression

Instead of relying on server-side construction of one-hot vectors or learned code mappings that leak structure, HE-LRM employs a deterministic, client-side compression technique based on digit decomposition.

• Mechanism: An original embedding table of size $k \times d$ is decomposed into $\ell$ smaller tables of size $p \times d$ (where $k \approx p^\ell$).
• Process: The client takes a categorical index $i$ and decomposes it into a tuple of base-$p$ digits $(i_0, i_1, \dots, i_{\ell-1})$.
• Privacy: The client locally constructs one-hot encodings for these smaller digits and encrypts them. The server never sees the original index, nor does it need to perform expensive homomorphic indicator functions. The compression is learned end-to-end during training without revealing the mapping structure to the client.

2. Block-Diagonal Packing Strategy

DLRMs typically utilize multiple embedding tables (e.g., 26 for Criteo). HE-LRM introduces a block-diagonal packing strategy to handle these simultaneously.

• Implementation: Multiple embedding tables are concatenated diagonally into a single large weight matrix.
• Benefit: This allows the client to concatenate the one-hot encodings for all features into a single vector. The server can then perform a single Baby-Step Giant-Step (BSGS) matrix-vector multiplication to retrieve embeddings for all tables in parallel. This maximizes ciphertext slot utilization and avoids the overhead of processing tables sequentially.

3. Optimized Linear Transform

The system leverages the double-hoisted BSGS algorithm for the matrix-vector multiplication.

• Unlike prior "Table-Mult" approaches that require separate rotations for every dimension of the embedding vector (consuming extra multiplicative levels), the BSGS approach treats the lookup as a standard linear transformation.
• This reduces the operation to a single multiplicative level, eliminating the need for intermediate bootstrapping during the lookup phase.

Key Contributions

1. First End-to-End FHE DLRM: HE-LRM is the first system to support both dense and sparse features in a DLRM under FHE, validated on the UCI Heart Disease and Criteo datasets.
2. 56× Speedup: The proposed client-side digit decomposition and BSGS lookup strategy achieves a 56× speedup over the state-of-the-art (CodedHeLUT) for large embedding dimensions (768). This is achieved by avoiding server-side indicator functions, reducing multiplicative depth consumption (from ~10 levels to 1), and eliminating the need for bootstrapping during the lookup phase.
3. Parallel Multi-Table Lookup: The block-diagonal packing strategy enables efficient parallel lookups across multiple embedding tables, significantly reducing communication and computational overhead compared to processing tables individually.
4. Clean Leakage Profile: The method adheres to a semi-honest threat model where the client only knows input dimensions and table sizes, but learns nothing about the embedding values, correlations, or model parameters.

Experimental Results

The authors evaluated HE-LRM using the open-source Orion FHE framework on a single-threaded CPU (Intel Xeon Gold 5218).

• UCI Heart Disease: Achieved an end-to-end inference latency of 24 seconds.
• Criteo Dataset: Achieved latencies ranging from 228 to 489 seconds depending on the compression ratio (ranging from $10\times$ to $10^5\times$ compression).
  • Highly compressed models ($\approx 10^3\times$ to $10^5\times$) showed similar latencies (~230s) because the embedding lookup time became negligible (3–5 seconds) compared to the rest of the network, and the BSGS operation could be performed on a single ciphertext.
  • Less compressed models required more ciphertexts, increasing the matrix-vector product latency.
• Hardware Projections:
  • GPU: Projections using the Cheddar accelerator suggest a ~200× speedup over CPU, reducing Criteo inference to approximately 1 second.
  • ASIC: Projections using the Osiris cost model suggest sub-second latencies (~0.037 seconds) for compressed models.

Significance and Claims

The paper claims that HE-LRM bridges a critical gap in private inference, demonstrating that privacy-preserving recommendation systems are approaching practical deployment.

• Scalability: The work proves that the "embedding bottleneck" in FHE can be resolved without sacrificing privacy or requiring the client to possess model weights.
• System Efficiency: By shifting the complexity of index encoding to the client (via deterministic decomposition) and utilizing efficient linear algebra (BSGS) on the server, the system avoids the prohibitive costs of bootstrapping and massive communication overheads associated with naive one-hot encodings.
• Broader Applicability: The authors note that the encrypted embedding lookup primitive is not limited to DLRMs but is also relevant for Transformer-based models, suggesting a reusable abstraction for future private inference systems.

The authors remain modest regarding the current CPU performance (minutes for large models), emphasizing that the demonstrated speedups on GPU and ASIC hardware are necessary for real-world production deployment.