Résumé technique : Hachage Multi-Sonde à Collision Zéro (MPZCH)

1. Énoncé du problème

Les systèmes de recommandation à grande échelle reposent sur des tables d'incorporation (embedding tables) pour mapper des caractéristiques catégorielles à haute cardinalité (par exemple, les identifiants d'utilisateurs, les identifiants d'éléments) vers des représentations vectorielles denses. Cependant, à mesure que le volume d'identifiants uniques augmente, les méthodes d'indexation traditionnelles basées sur le hachage font face à deux défis critiques :

1. Collisions d'incorporation : En raison des contraintes de mémoire, la « technique de hachage » (hashing trick) mappe plusieurs identifiants distincts vers le même index. Lorsque des utilisateurs ou des éléments non liés partagent un vecteur d'incorporation, cela confond leurs sémantiques, dégradant les performances du modèle et la qualité de la personnalisation.
2. Obsolescence du modèle et transfert négatif : Dans des environnements dynamiques, de nouveaux éléments entrent fréquemment en collision avec des slots occupés par des identifiants obsolètes ou périmés. Les méthodes de hachage standard manquent de mécanismes pour retirer ces anciens identifiants. Par conséquent, les nouveaux éléments « héritent » d'incorporations pré-entraînées provenant d'entités non liées, contraignant le modèle à désapprendre du bruit avant de converger vers des signaux utiles. Ce « transfert négatif » entrave l'apprentissage de représentations précises pour les nouvelles caractéristiques.

Bien que l'augmentation de la taille de la table réduise la probabilité de collision, elle ne peut pas éliminer les collisions entièrement en raison des limites de mémoire, et les algorithmes de hachage standard peuvent encore produire des collisions significatives même avec de grandes tables.

2. Méthodologie : MPZCH

Les auteurs proposent le Hachage Multi-Sonde à Collision Zéro (MPZCH), un mécanisme d'indexation novateur implémenté sous forme d'un noyau CUDA haute performance. Il combine l'exploration linéaire (linear probing) avec une gestion d'état auxiliaire pour atténuer les collisions et gérer activement les cycles de vie des identifiants.

2.1 Composants principaux

• Tenseurs auxiliaires : MPZCH maintient deux tenseurs parallèlement à la table d'incorporation :
  • Tenseur des identités : Enregistre l'identifiant spécifique occupant chaque slot (initialisé à -1). Cela permet au noyau de distinguer strictement les slots occupés des slots disponibles.
  • Tenseur de métadonnées : Stocke des informations auxiliaires, telles que des valeurs de durée de vie (TTL) ou des horodatages, pour guider les décisions d'éviction.
• Exploration linéaire en deux passes : Pour garantir la cohérence et prévenir le stockage dupliqué ou l'éviction prématurée, le noyau exécute un balayage en deux passes pour chaque identifiant :
  1. Passage 1 (Découverte) : Balaye la plage de sondage pour déterminer si l'identifiant existe déjà. Aucune opération d'écriture n'est effectuée.
  2. Passage 2 (Action) : Basé sur les résultats du Passage 1 :
     • Mise à jour : Si l'identifiant existe, les métadonnées (par exemple, l'horodatage) sont rafraîchies.
     • Allocation : Si l'identifiant est nouveau, le noyau tente de trouver un slot vide ou d'évincer une entrée expirée.
     • Fallback en cas de collision : Si aucun slot vide ou évictable n'est trouvé dans la plage de sondage, le système revient au slot de hachage initial (bien qu'avec un dimensionnement de table suffisant et une profondeur de sondage adéquate, cela soit rare).

2.2 Stratégies d'éviction et de fraîcheur

MPZCH introduit des politiques d'éviction configurables pour gérer la capacité de la table et assurer la fraîcheur :

• Politique TTL (Time-To-Live) : Les slots sont marqués comme expirés si leur horodatage de métadonnées est inférieur à l'horodatage d'entraînement actuel. L'éviction est paresseuse, déclenchée uniquement lorsqu'un nouvel identifiant nécessite une allocation.
• Politique LRU (Least Recently Used) : Le noyau balaye la plage de sondage pour évincer l'entrée ayant le plus vieil horodatage.
• Réinitialisation de l'optimiseur : Crucialement, lors de l'éviction, à la fois les poids d'incorporation et l'état de l'optimiseur (par exemple, la quantité de mouvement) sont réinitialisés. Cela empêche les nouveaux éléments d'hériter d'incorporations périmées, garantissant qu'ils apprennent à partir de zéro.

2.3 Intégration système

• Intégration TorchRec : MPZCH est conçu pour une intégration transparente avec la bibliothèque TorchRec de Meta. Les tenseurs d'identité et de métadonnées sont partagés par ligne (row-wise sharded) à travers les rangs pour correspondre à la table d'incorporation, garantissant que toutes les opérations restent locales au shard sans synchronisation complexe inter-rangs.
• Optimisation de l'inférence : Lors de la publication du modèle, le tenseur de métadonnées est omis pour réduire la taille du modèle, et le tenseur d'identités est figé. Le service d'inférence devient strictement en lecture seule, fournissant des recherches déterministes et efficaces.
• Mises à jour en flux continu : Le système prend en charge l'entraînement en ligne avec des mises à jour en flux continu, garantissant que le tenseur d'identités reste cohérent avec les modifications des lignes d'incorporation.

3. Contributions clés

1. Garantie de collision zéro : En combinant un dimensionnement de table suffisant avec des profondeurs de sondage configurables, MPZCH élimine efficacement les collisions d'incorporation pour les incorporations d'utilisateurs, une prouesse difficile à réaliser avec le hachage standard.
2. Gestion active du cycle de vie : Contrairement aux tables de hachage statiques, MPZCH retire activement les identifiants obsolètes et réinitialise les états des optimiseurs, abordant directement le problème du « transfert négatif » et améliorant la fraîcheur du modèle.
3. Implémentation haute performance : L'algorithme est implémenté comme un noyau CUDA personnalisé qui gère des dizaines de milliers d'identifiants en parallèle. Les benchmarks montrent que la surcharge de l'exploration linéaire est négligeable (la latence reste stable même avec une profondeur de sondage accrue), maintenant un QPS d'entraînement et une latence d'inférence comparables aux méthodes existantes.
4. Publication open-source : La solution a été publiée au sein de la bibliothèque open-source TorchRec.

4. Résultats expérimentaux

Les auteurs ont évalué MPZCH grâce à des tests A/B en ligne rigoureux et des benchmarks hors ligne :

• Taux de collision : Dans des expériences avec 150 millions d'identifiants d'utilisateurs uniques, MPZCH a atteint zéro collision avec une taille de table de 200 millions (capacité 1,33x) et une profondeur de sondage de 256. En revanche, le hachage Sigrid de base a maintenu un taux de collision d'environ 30 % même avec une taille de table triple la cardinalité des identifiants.
• Incorporations d'utilisateurs (Classement vidéo) : Déployé dans un modèle de classement vidéo de production servant 3 milliards d'utilisateurs actifs mensuels. L'élimination des collisions a entraîné des améliorations statistiquement significatives de l'Entropie Normalisée (NE) pour 14 tâches de prédiction sur 17, notamment le Partage (+0,38 %) et la Durée de visionnage des vidéos (+0,12 %).
• Incorporations d'éléments (Récupération vidéo) : Intégré dans un modèle de récupération basé sur HSTU avec éviction basée sur le TTL (24h pour les publications, 72h pour les propriétaires).
  • Performance : Les nouvelles vidéos (publiées dans les 48 heures) ont enregistré une augmentation de 0,83 % des impressions.
  • Qualité sémantique : L'analyse t-SNE a révélé que MPZCH a considérablement amélioré le regroupement (clustering) des incorporations pour les vidéos d'un même créateur. La similarité intra-créateur est passée de 0,66 % à 0,91 % pour les publications du même jour (+38 % de gain relatif).
  • Stabilité de l'apprentissage : Les trajectoires d'incorporation sont devenues plus lisses et plus cohérentes, éliminant les fluctuations volatiles observées dans le modèle de base causées par les collisions de hachage.

5. Importance

L'article postule que MPZCH offre une solution à double avantage pour les systèmes de recommandation modernes. Premièrement, en garantissant un environnement sans collision, il élève la qualité des incorporations et la précision des prédictions en éliminant les interférences stochastiques. Deuxièmement, en introduisant des mécanismes d'éviction active et de réinitialisation de l'optimiseur, il améliore fondamentalement la fraîcheur des incorporations, permettant aux modèles de s'adapter rapidement aux distributions de données changeantes sans croissance de mémoire illimitée. Les auteurs concluent que ces améliorations empiriques tant de la fraîcheur que de la qualité du modèle valident MPZCH comme une solution robuste pour les recommandateurs à grande échelle.