Résumé technique : Récupération de descripteurs de patch exacte et déterministe via la normalisation hiérarchique

Énoncé du problème

La recherche de plus proches voisins (NN) en haute dimension est fondamentale pour les applications d'IA modernes, incluant la génération augmentée par récupération (RAG), la vérification faciale et la reconnaissance de lieux visuels. Les approches standard reposent souvent sur des index de plus proches voisins approximatifs (ANN) comme HNSW ou IVF-PQ pour obtenir des temps de recherche sous-linéaires. Cependant, ces méthodes introduisent deux limitations critiques :

1. Approximation : Elles sacrifient l'exactitude au profit de la vitesse, pouvant ainsi retourner un résultat qui n'est pas le véritable plus proche voisin.
2. Non-déterminisme : Les résultats peuvent varier d'une exécution à l'autre en raison de l'ordre de construction du graphe, du nombre de threads ou des différences matérielles, ce qui est problématique pour l'A/B testing, la mise en cache des résultats et l'audit de sécurité.

HN-Desc introduit une normalisation hiérarchique pour contraindre 96,9 % de l'énergie du descripteur à 8 dimensions, permettant une récupération exacte et prouvable des plus proches voisins sans utiliser d'index approximatifs. Le concept d'importance dimensionnelle non uniforme pour la récupération remonte à 2020 [Brevet 11,797,603], précédant l'apprentissage de représentations Matryoshka (2022) qui se concentre sur des embeddings élastiques imbriqués pour la représentation à usage général. Le défi consiste à obtenir des accélérations significatives par rapport à la recherche par force brute tout en maintenant des résultats provablement exacts et pleinement déterministes.

Méthodologie : Normalisation Hiérarchique (HN)

La contribution centrale est la Normalisation Hiérarchique (HN), une modification de la couche de normalisation du réseau de descripteurs qui permet une stratégie de recherche par division et en présence de bornes (branch-and-bound) en deux phases.

1. Schéma de normalisation hiérarchique

La normalisation $L_2$ standard est remplacée par un schéma qui divise le vecteur de caractéristiques pré-normalisation $f \in \mathbb{R}^D$ (où $D=128$ pour HardNet) en deux composantes :

• Composante majeure ($f_{major}$) : Les $K$ premières dimensions, normalisées pour avoir une norme au carré de $1-\alpha$.
• Composante mineure ($f_{minor}$) : Les $D-K$ dimensions restantes, normalisées pour avoir une norme au carré de $\alpha$.

Le scalaire $\alpha \in [0, 1)$ contrôle la répartition de l'énergie. Le vecteur complet est $[f_{major}, f_{minor}]$, maintenant une norme unitaire.

Nécessité de l'entraînement : L'application simple de cette normalisation a posteriori à un modèle HardNet pré-entraîné est insuffisante car HardNet distribue l'énergie uniformément sur toutes les dimensions. L'article démontre qu'un ajustement fin (fine-tuning) du réseau avec la HN est nécessaire pour déplacer l'énergie discriminante vers le préfixe majeur, rendant les $K$ premières dimensions prédictives fiables de la similitude complète.

2. Borne supérieure admissible

La méthode repose sur l'inégalité de Cauchy-Schwarz pour établir une borne supérieure serrée sur le produit scalaire complet. Pour une requête $q$ et une entrée de la base de données $x$ :
$$\langle q, x \rangle = \langle q_{major}, x_{major} \rangle + \langle q_{minor}, x_{minor} \rangle$$
Puisque $\|q_{minor}\| = \|x_{minor}\| = \sqrt{\alpha}$, le produit scalaire mineur est borné par $\alpha$ :
$$\langle q, x \rangle \leq \text{dot}_K(q, x) + \alpha$$
Ici, $\text{dot}_K(q, x)$ est le produit scalaire des seules composantes majeures de dimension $K$.

3. Algorithme de recherche exacte en deux phases

Le processus de récupération (Algorithme 1) procède comme suit :

1. Phase 1 (Scan majeur) : Calculer le produit scalaire de dimension $K$ pour toutes les $N$ entrées de la base de données. Identifier le candidat $b$ ayant le score le plus élevé $s_b$.
2. Initialisation : Calculer le produit scalaire complet en 128 dimensions pour $b$ afin d'établir le score actuel le meilleur $s_{best}$.
3. Phase 2 (Élagage admissible) : Itérer à travers les entrées restantes. Pour chaque entrée $i$ :
   • Calculer la borne supérieure : $s_i + \alpha$.
   • Élagage : Si $s_i + \alpha \leq s_{best}$, ignorer l'évaluation complète (l'entrée ne peut pas être le plus proche voisin).
   • Évaluation : Si la borne est dépassée, calculer le produit scalaire complet en 128 dimensions. Si celui-ci dépasse $s_{best}$, mettre à jour $s_{best}$ et l'indice optimal.

4. Déterminisme et efficacité

• Déterminisme : L'algorithme est déterministe pour un ordre de base de données fixe. Les égalités dans le score majeur sont départagées par l'ordre des indices. Comme les descripteurs en virgule flottante produisent rarement des égalités exactes de produit scalaire, le résultat est effectivement indépendant de l'ordre de la base de données.
• Disposition mémoire : Pour maximiser la vitesse, les auteurs utilisent une disposition de type Structure de Tableaux (SOA). Cela stocke les composantes majeures et mineures dans des tableaux contigus séparés, permettant à la Phase 1 de scanner uniquement le tableau compact des composantes majeures (par exemple, 16 Mo pour $K=8, N=500k$) sans charger la banque complète de descripteurs de 256 Mo, réduisant ainsi considérablement l'utilisation de la bande passante mémoire et améliorant l'utilisation du cache.

Contributions clés

1. Récupération exacte (Théorème 1) : L'article prouve que la recherche en deux phases basée sur la HN retourne exactement le même indice qu'une recherche exhaustive sur le vecteur complet. L'accélération n'entraîne aucun taux d'erreur de récupération.
2. Déterminisme (Théorème 2) : La méthode est reproductible à travers les exécutions, les constructions d'index et les nombres de threads, à condition que l'ordre de la base de données soit fixé. Cela contraste fortement avec HNSW et IVF-PQ, qui sont non déterministes.
3. Efficacité : En exploitant la borne admissible et la disposition SOA, la méthode atteint des accélérations significatives en temps réel (wall-clock) tout en n'évaluant qu'une infime fraction de la base de données de manière complète.

Résultats expérimentaux

La méthode a été évaluée sur le jeu de données de patchs UBC (entraînement sur Notre Dame, tests sur Trevi et Halfdome) en utilisant un squelette HardNet affiné avec la HN.

Compromis Qualité-Vitesse

• Configuration $K=16, \alpha=1/8$ :
  • Accélération : $7,2\times$ sur Trevi et $5,8\times$ sur Halfdome (vs force brute).
  • Qualité : Le FPR@95 n'a augmenté que marginalement par rapport à la ligne de base pré-entraînée (0,0062) à 0,0064 sur Trevi.
  • Élagage : 98,8 % des entrées ont évité l'évaluation complète.
• Configuration $K=8, \alpha=1/32$ :
  • Accélération : $13,7\times$ sur Trevi et $12,7\times$ sur Halfdome.
  • Qualité : Le FPR@95 est de 0,0397 sur Trevi (plus élevé que $K=16$ mais toujours compétitif).
  • Élagage : Seules 0,4 % des entrées ont nécessité une évaluation complète.

Comparaison avec HNSW

• Petits jeux de données ($N=1\,000$) : HN ($K=16$) a atteint une accélération de $9,5\times$ avec un rappel de 100 % exact. Les configurations HNSW étaient soit plus lentes que la force brute, soit fournissaient un rappel inférieur.
• Grands jeux de données ($N=99\,000$) : HNSW ($ef=50$) a atteint un débit plus élevé ($111,9\times$) mais avec un rappel non garanti (tombant à environ 94 % sur des données synthétiques). HN a maintenu un rappel exact de 100 % avec une accélération de $12,5\times$.
• Scalabilité : L'accélération de HN est largement indépendante de $N$ (limitée par la bande passante mémoire), tandis que l'avantage de HNSW croît avec $N$ en raison de sa complexité sous-linéaire.

Signification et affirmations

L'article positionne ce travail comme une solution au dilemme "exactitude vs vitesse".

• Sécurité et fiabilité : Les auteurs soulignent que pour les applications critiques (ex: identification médico-légale, navigation autonome), les "erreurs silencieuses" des méthodes ANN sont inacceptables. La HN fournit un certificat mathématique de correction (Théorème 1).
• Reproductibilité : Le caractère déterministe de la HN est essentiel pour le suivi des régressions, l'A/B testing et la mise en cache des résultats, des domaines où les pipelines HNSW et MRL échouent en raison de la variance entre les exécutions.
• Insight sur l'entraînement : Ce travail démontre que la qualité des descripteurs peut être préservée lors de la compression en entraînant activement le réseau à concentrer l'information discriminante dans un préfixe, plutôt que de compter sur une réduction de dimensionnalité post-hoc (comme la PCA) qui échoue pour les descripteurs HardNet.

Les auteurs concluent que les praticiens peuvent choisir n'importe quel point sur la frontière de Pareto qualité-vitesse (en ajustant $K$ et $\alpha$) sans sacrifier l'exactitude ni le déterminisme, offrant une alternative robuste à l'indexation approximative pour les scénarios où la reproductibilité et la justesse sont primordiales.