Technische Samenvatting: HE-LRM

Probleemstelling

Fully Homomorphic Encryption (FHE) maakt privacy-bewuste neurale inferentie op versleutelde gegevens mogelijk, maar bestaande oplossingen richten zich primair op modellen met dichte inputs (bijv. CNN's, MLP's). Deep Learning Recommendation Models (DLRMs) vormen een specifieke uitdaging vanwege hun afhankelijkheid van grote, ijle (sparse) categorische inputs die worden verwerkt via massieve embedding-tabellen.

In een standaard DLRM worden ijle kenmerken via embedding-tabel-lookups naar dichte vectoren gemapt. In een FHE-context (specifiek bij het gebruik van het CKKS-schema) wordt directe indexering niet van nature ondersteund; alleen SIMD-optelling, vermenigvuldiging en cyclische rotatie zijn beschikbaar. Naïeve benaderingen voor versleutelde lookups kampen met ernstige schaalbaarheidsproblemen:

1. Communicatie-overhead: Een "one-hot" codering van een index voor een tabel met $k$ rijen vereist een vector van grootte $k$. Voor industriële datasets zoals Criteo (33,8 miljoen rijen) is dit nodig om meer dan 1.000 ciphertexts (>1 GiB) per inferentie te uploaden.
2. Computatiekosten aan de serverzijde: Voorgaand werk (bijv. Kim et al. [10]) probeert de uploadkosten te beperken door de server de one-hot selector vanuit een versleutelde index te laten construeren. Dit vereist echter diepe rekenkundige circuits (indicatorfuncties) die een aanzienlijke multiplicatieve diepte verbruiken, wat vaak dure bootstrapping-operaties noodzakelijk maakt.
3. Geheugen- en structuurlek: Bestaande compressietechnieken vereisen vaak dat de cliënt geleerde code-mappings opslaat (wat embedding-correlaties onthult) of resulteren in inefficiënt gebruik van slots en een hoge geheugenvoetafdruk op de server.

Methodologie: HE-LRM

De auteurs stellen HE-LRM voor, een end-to-end FHE-systeem dat is geoptimaliseerd voor DLRM-inferentie. De oplossing pakt de bottleneck van de embedding lookup aan via drie kerntechnische innovaties:

1. Client-zijde Digit Decomposition Compressie

In plaats van te vertrouwen op de constructie van one-hot vectoren aan de serverzijde of geleerde code-mappings die de structuur lekken, gebruikt HE-LRM een deterministische, client-zijde compressietechniek gebaseerd op digit decomposition.

• Mechanisme: Een originele embedding-tabel van grootte $k \times d$ wordt gedecomposeerd in $\ell$ kleinere tabellen van grootte $p \times d$ (waarbij $k \approx p^\ell$).
• Proces: De cliënt neemt een categorische index $i$ en decomponeert deze in een tuple van base-$p$ cijfers $(i_0, i_1, \dots, i_{\ell-1})$.
• Privacy: De cliënt construeert lokaal one-hot encodings voor deze kleinere cijfers en versleutelt deze. De server ziet de originele index nooit, noch hoeft deze dure homomorfe indicatorfuncties uit te voeren. De compressie wordt end-to-end geleerd tijdens de training zonder de mapping-structuur aan de cliënt te onthullen.

2. Block-Diagonal Packing Strategie

DLRMs maken doorgaans gebruik van meerdere embedding-tabellen (bijv. 26 voor Criteo). HE-LRM introduceert een block-diagonal packing strategie om deze gelijktijdig te verwerken.

• Implementatie: Meerdere embedding-tabellen worden diagonaal samengevoegd in één grote gewichtsmatrix.
• Voordeel: Dit stelt de cliënt in staat om de one-hot encodings voor alle kenmerken samen te voegen tot één enkele vector. De server kan vervolgens een enkele Baby-Step Giant-Step (BSGS) matrix-vector vermenigvuldiging uitvoeren om de embeddings voor alle tabellen parallel op te halen. Dit maximaliseert de benutting van de ciphertext-slots en voorkomt de overhead van het sequentieel verwerken van tabellen.

3. Geoptimaliseerde Lineaire Transformatie

Het systeem maakt gebruik van het double-hoisted BSGS algoritme voor de matrix-vector vermenigvuldiging.

• In tegenstelling tot eerdere "Table-Mult" benaderingen die aparte rotaties vereisen voor elke dimensie van de embedding-vector (wat extra multiplicatieve niveaus verbruikt), behandelt de BSGS-benadering de lookup als een standaard lineaire transformatie.
• Dit reduceert de operatie tot een enkel multiplicatief niveau, waardoor de noodzaak voor tussenliggende bootstrapping tijdens de lookup-fase wordt geëlimineerd.

Belangrijkste Bijdragen

1. Eerste End-to-End FHE DLRM: HE-LRM is het eerste systeem dat zowel dichte als ijle kenmerken in een DLRM onder FHE ondersteunt, gevalideerd op de UCI Heart Disease en Criteo datasets.
2. 56× Versnelling: De voorgestelde client-zijde digit decomposition en BSGS lookup strategie bereikt een 56× versnelling ten opzichte van de state-of-the-art (CodedHeLUT) voor grote embedding dimensies (768). Dit wordt bereikt door het vermijden van server-zijde indicatorfuncties, het reduceren van de multiplicatieve diepte consumptie (van ~10 niveaus naar 1), en het elimineren van de noodzaak voor bootstrapping tijdens de lookup-fase.
3. Parallel Multi-Table Lookup: De block-diagonal packing strategie maakt efficiënte parallelle lookups mogelijk over meerdere embedding-tabellen, wat de communicatie- en computationele overhead aanzienlijk vermindert vergeleken met het individueel verwerken van tabellen.
4. Zuiver Lekprofiel: De methode voldoet aan een semi-honest dreigingsmodel waarbij de cliënt alleen de inputdimensies en tabelgroottes kent, maar niets leert over de embedding-waarden, correlaties of modelparameters.

Experimentele Resultaten

De auteurs hebben HE-LRM geëvalueerd met behulp van het open-source Orion FHE-framework op een single-threaded CPU (Intel Xeon Gold 5218).

• UCI Heart Disease: Behaalde een end-to-end inferentie latentie van 24 seconden.
• Criteo Dataset: Behaalde latenties variërend van 228 tot 489 seconden, afhankelijk van de compressieratio (variërend van $10\times$ tot $10^5\times$ compressie).
  • Sterk gecomprimeerde modellen ($\approx 10^3\times$ tot $10^5\times$) vertoonden vergelijkbare latenties (~230s) omdat de embedding lookup tijd verwaarloosbaar werd (3–5 seconden) vergeleken met de rest van het netwerk, en de BSGS operatie op een enkele ciphertext kon worden uitgevoerd.
  • Minder gecomprimeerde modellen vereisten meer ciphertexts, wat de matrix-vector product latentie verhoogde.
• Hardware Projecties:
  • GPU: Projecties met de Cheddar accelerator suggereren een ~200× versnelling over CPU, waardoor Criteo inferentie wordt teruggebracht naar ongeveer 1 seconde.
  • ASIC: Projecties met het Osiris kostenmodel suggereren sub-seconde latenties (~0,037 seconden) voor gecomprimeerde modellen.

Betekenis en Claims

Het artikel claimt dat HE-LRM een kritieke kloof in privacy-bewuste inferentie overbrugt, door aan te tonen dat privacy-bewuste aanbevelingssystemen de praktische implementatie naderen.

• Schaalbaarheid: Het werk bewijst dat de "embedding bottleneck" in FHE kan worden opgelost zonder de privacy op te offeren of te vereisen dat de cliënt de modelgewichten bezit.
• Systeemefficiëntie: Door de complexiteit van de index codering naar de cliënt te verschuiven (via deterministische decompositie) en efficiënte lineaire algebra (BSGS) op de server te gebruiken, vermijdt het systeem de prohibitieve kosten van bootstrapping en de enorme communicatie-overhead die gepaard gaat met naïeve one-hot encodings.
• Brede Toepasbaarheid: De auteurs merken op dat de versleutelde embedding lookup primitief niet beperkt is tot DLRMs, maar ook relevant is voor Transformer-gebaseerde modellen, wat suggereert dat het een herbruikbare abstractie is voor toekomstige private inferentie systemen.

De auteurs blijven bescheiden over de huidige CPU-prestaties (minuten voor grote modellen), waarbij ze benadrukken dat de gedemonstreerde versnellingen op GPU en ASIC hardware noodzakelijk zijn voor echte productie-implementatie.