Resumen Técnico: HE-LRM

Planteamiento del Problema

El cifrado totalmente homomórfico (FHE) permite la inferencia de redes neuronales preservando la privacidad sobre datos cifrados, sin embargo, las soluciones existentes abordan principalmente modelos con entradas densas (por ejemplo, CNNs, MLPs). Los Modelos de Recomendación de Aprendizaje Profundo (DLRM) presentan un desafío distinto debido a su dependencia de entradas categóricas dispersas y masivas procesadas a través de tablas de incrustación (embedding tables) de gran tamaño.

En un DLRM estándar, las características dispersas se mapean a vectores densos mediante búsquedas en tablas de incrustación. En un contexto de FHE (específicamente utilizando el esquema CKKS), el indexado directo no es soportado de forma nativa; solo están disponibles las sumas, multiplicaciones y rotaciones cíclicas SIMD. Los enfoques ingenuos para las búsquedas cifradas enfrentan graves problemas de escalabilidad:

1. Sobrecarga de Comunicación: Un codificación "one-hot" de un índice para una tabla con $k$ filas requiere un vector de tamaño $k$. Para conjuntos de datos a escala industrial como Criteo (33.8 millones de filas), esto requiere subir más de 1,000 cifrados (>1 GiB) por cada inferencia.
2. Costos de Cómputo en el Servidor: El trabajo previo (por ejemplo, Kim et al. [10]) intenta mitigar los costos de subida haciendo que el servidor construya el selector one-hot a partir de un índice cifrado. Sin embargo, esto requiere circuitos aritméticos profundos (funciones indicadoras) que consumen una profundidad multiplicativa significativa, lo que a menudo requiere operaciones de bootstrapping costosas.
3. Fuga de Memoria y Estructura: Las técnicas de compresión existentes a menudo requieren que el cliente almacene mapeos de códigos aprendidos (lo que revela correlaciones de las incrustaciones) o resultan en un uso ineficiente de los slots y altas huellas de memoria en el servidor.

Metodología: HE-LRM

Los autores proponen HE-LRM, un sistema de FHE de extremo a extremo optimizado para la inferencia de DLRM. La solución aborda el cuello de botella de la búsqueda de incrustaciones a través de tres innovaciones técnicas centrales:

1. Compresión por Descomposición de Dígitos en el Lado del Cliente

En lugar de depender de la construcción de vectores one-hot en el servidor o de mapeos de códigos aprendidos que filtran la estructura, HE-LRM emplea una técnica de compresión determinista en el lado del cliente basada en la descomposición de dígitos.

• Mecanismo: Una tabla de incrustación original de tamaño $k \times d$ se descompone en $\ell$ tablas más pequeñas de tamaño $p \times d$ (donde $k \approx p^\ell$).
• Proceso: El cliente toma un índice categórico $i$ y lo descompone en una tupla de dígitos en base-$p$ $(i_0, i_1, \dots, i_{\ell-1})$.
• Privacidad: El cliente construye localmente las codificaciones one-hot para estos dígitos más pequeños y las cifra. El servidor nunca ve el índice original, ni necesita realizar funciones indicadoras homomórficas costosas. La compresión se aprende de extremo a extremo durante el entrenamiento sin revelar la estructura del mapeo al cliente.

2. Estrategia de Empaquetado Diagonal de Bloques

Los DLRM suelen utilizar múltiples tablas de incrustación (por ejemplo, 26 para Criteo). HE-LRM introduce una estrategia de empaquetado diagonal de bloques para manejar estas simultáneamente.

• Implementación: Múltiples tablas de incrustación se concatenan diagonalmente en una única matriz de pesos de gran tamaño.
• Beneficio: Esto permite al cliente concatenar las codificaciones one-hot de todas las características en un solo vector. El servidor puede entonces realizar una multiplicación de matriz por vector Baby-Step Giant-Step (BSGS) única para recuperar las incrustaciones de todas las tablas en paralelo. Esto maximiza la utilización de los slots de los cifrados y evita la sobrecarga de procesar las tablas secuencialmente.

3. Transformación Lineal Optimizada

El sistema aprovecha el algoritmo double-hoisted BSGS para la multiplicación de matriz por vector.

• A diferencia de los enfoques previos de "Table-Mult" que requieren rotaciones separadas para cada dimensión del vector de incrustación (consumiendo niveles multiplicativos adicionales), el enfoque BSGS trata la búsqueda como una transformación lineal estándar.
• Esto reduce la operación a un solo nivel multiplicativo, eliminando la necesidad de bootstrapping intermedio durante la fase de búsqueda.

Contribuciones Clave

1. Primer DLRM de FHE de Extremo a Extremo: HE-LRM es el primer sistema que soporta tanto características densas como dispersas en un DLRM bajo FHE, validado en los conjuntos de datos UCI Heart Disease y Criteo.
2. Aceleración de 56×: La propuesta de descomposición de dígitos en el lado del cliente y la estrategia de búsqueda BSGS logra una aceleración de 56× respecto al estado del arte (CodedHeLUT) para dimensiones de incrustación grandes (768). Esto se logra evitando las funciones indicadoras en el servidor, reduciendo el consumo de profundidad multiplicativa (de ~10 niveles a 1) y eliminando la necesidad de bootstrapping durante la fase de búsqueda.
3. Búsqueda de Múltiples Tablas en Paralelo: La estrategia de empaquetado diagonal de bloques permite búsquedas paralelas eficientes a través de múltiples tablas de incrustación, reduciendo significativamente la sobrecarga de comunicación y computación en comparación con el procesamiento individual de las tablas.
4. Perfil de Fuga Limpio: El método se adhiere a un modelo de amenaza de semi-honestidad donde el cliente solo conoce las dimensiones de entrada y los tamaños de las tablas, pero no aprende nada sobre los valores de las incrustaciones, las correlaciones o los parámetros del modelo.

Resultados Experimentales

Los autores evaluaron HE-LRM utilizando el marco de trabajo FHE de código abierto Orion en una CPU de un solo hilo (Intel Xeon Gold 5218).

• UCI Heart Disease: Logró una latencia de inferencia de extremo a extremo de 24 segundos.
• Conjunto de Datos Criteo: Logró latencias que oscilan entre 228 y 489 segundos dependiendo de la relación de compresión (que varía de $10\times$ a $10^5\times$).
  • Los modelos altamente comprimidos ($\approx 10^3\times$ a $10^5\times$) mostraron latencias similares (~230s) porque el tiempo de búsqueda de la incrustación se volvió insignificante (3–5 segundos) en comparación con el resto de la red, y la operación BSGS pudo realizarse en un solo cifrado.
  • Los modelos menos comprimidos requirieron más cifrados, aumentando la latencia del producto matriz-vector.
• Proyecciones de Hardware:
  • GPU: Las proyecciones usando el acelerador Cheddar sugieren una aceleración de ~200× sobre la CPU, reduciendo la inferencia de Criteo a aproximadamente 1 segundo.
  • ASIC: Las proyecciones usando el modelo de costos Osiris sugieren latencias de sub-segundo (~0.037 segundos) para modelos comprimidos.

Significancia y Reivindicaciones

El artículo afirma que HE-LRM cierra una brecha crítica en la inferencia privada, demostrando que los sistemas de recomendación que preservan la privacidad se están acercando a una implementación práctica.

• Escalabilidad: El trabajo demuestra que el "cuello de botella de la incrustación" en FHE puede resolverse sin sacrificar la privacidad ni requerir que el cliente posea los pesos del modelo.
• Eficiencia del Sistema: Al desplazar la complejidad de la codificación de índices al cliente (mediante la descomposición determinista) y utilizar álgebra lineal eficiente (BSGS) en el servidor, el sistema evita los costos prohibitivos de bootstrapping y la enorme sobrecarga de comunicación asociada con las codificaciones one-hot ingenuas.
• Aplicabilidad Amplia: Los autores señalan que la primitiva de búsqueda de incrustación cifrada no se limita a los DLRM, sino que también es relevante para modelos basados en Transformers, lo que sugiere una abstracción reutilizable para futuros sistemas de inferencia privada.

Los autores mantienen la modestia respecto al rendimiento actual de la CPU (minutos para modelos grandes), enfatizando que las aceleraciones demostradas en hardware GPU y ASIC son necesarias para un despliegue en producción en el mundo real.