Approximate Nearest Neighbor Search for Modern AI: A Projection-Augmented Graph Approach

Ce papier présente PAG, un nouveau cadre de recherche de voisins les plus proches approximatifs qui intègre des techniques de projection dans un index graphique pour répondre simultanément aux exigences de performance, de mémoire et d'évolutivité des applications d'IA modernes, surpassant ainsi HNSW en vitesse de requête tout en conservant une précision élevée.

L'essentiel

Imaginez que vous êtes le bibliothécaire d'une bibliothèque gigantesque contenant des milliards de livres (les données). Chaque livre a une "étiquette" invisible qui décrit son contenu (un vecteur mathématique).

Votre travail consiste à répondre à une question simple : "Quels sont les 10 livres les plus similaires à celui que je tiens en main ?"

C'est ce qu'on appelle la Recherche de Voisins Approximatifs (ANNS). Aujourd'hui, avec l'IA, cette bibliothèque grandit à une vitesse folle, et les livres deviennent de plus en plus complexes (des milliers de mots sur l'étiquette). Les méthodes actuelles sont comme des bibliothécaires qui courent partout, mais qui s'essoufflent vite, perdent du temps à vérifier des livres inutiles, ou ont besoin de trop d'espace pour ranger leurs cartes.

Voici comment l'article propose une nouvelle solution, appelée PAG (Graph Augmenté par Projection), expliquée simplement.

1. Le Problème : Le Dilemme du Bibliothécaire Épuisé

Les méthodes actuelles (comme HNSW) sont bonnes, mais elles ont des défauts :

• Lentes à construire : Prendre des années pour classer la bibliothèque.
• Gourmandes en mémoire : Elles ont besoin d'un énorme bureau pour poser leurs cartes.
• Peu flexibles : Elles fonctionnent bien pour trouver 10 livres, mais s'effondrent si vous en voulez 1000.
• Peu adaptées aux mises à jour : Si vous ajoutez un nouveau livre, il faut souvent tout reclasser.

2. La Solution : PAG, le Bibliothécaire "Super-Puissant"

L'équipe propose PAG. Imaginez que PAG est un bibliothécaire qui utilise une loupe magique (la projection) et un système de tri intelligent (le graphe).

Voici les trois astuces secrètes de ce bibliothécaire :

A. La Loupe Magique (Le Test de Routage Probabiliste - PRT)

Au lieu de comparer exactement chaque livre avec celui que vous cherchez (ce qui prend du temps), le bibliothécaire utilise d'abord une projection.

• L'analogie : Imaginez que vous cherchez un livre sur "les chats". Au lieu de lire le résumé de chaque livre, le bibliothécaire lance une petite pierre (une projection) sur l'étiquette. Si la pierre ne touche pas la zone "animaux", il sait immédiatement qu'il ne faut pas lire ce livre. Il ne perd pas de temps à faire le calcul exact.
• Le résultat : Il élimine 90% des livres inutiles en une fraction de seconde, ne gardant que les candidats sérieux pour une vérification précise.

B. Le Carnet de Notes Réutilisable (Le Tampon de Retour - TFB)

Parfois, la loupe magique se trompe un peu (elle dit "c'est un chat" alors que c'est un "tigre"). Les méthodes actuelles jettent ces erreurs.

• L'analogie : PAG, lui, note ces "fausses alertes" dans un carnet spécial. La prochaine fois qu'il cherche un livre, il regarde ce carnet. Il se dit : "Ah, ce livre a failli passer la fois dernière, il est peut-être proche, je vais le vérifier plus soigneusement."
• Le résultat : Il apprend de ses erreurs et n'a pas besoin de recommencer tout le travail de zéro. Cela rend la recherche et l'ajout de nouveaux livres beaucoup plus rapides.

C. Le Réseau de Chemins (Sélection de Bords Probabiliste - PES)

Pour que la recherche soit rapide, les livres doivent être reliés entre eux par des chemins logiques (un graphe).

• L'analogie : Parfois, le bibliothécaire classique ne voit qu'un seul chemin vers un livre. PAG, grâce à sa loupe, voit des chemins cachés. Il ajoute des raccourcis entre des livres qui semblent éloignés mais qui sont en fait proches.
• Le résultat : Même si vous cherchez un livre très spécifique, le bibliothécaire trouve un chemin rapide pour y arriver, même si la bibliothèque est immense.

3. Pourquoi c'est génial ? (Les Résultats)

Grâce à ces astuces, PAG bat les champions actuels (comme HNSW) sur tous les fronts :

1. Vitesse d'indexation (Construction) : Il classe la bibliothèque 5 fois plus vite que les autres. C'est comme passer d'un tri manuel à un tri par robot.
2. Vitesse de recherche : Il trouve les livres 5 fois plus vite tout en étant aussi précis.
3. Mémoire : Il a besoin de moins d'espace de bureau (mémoire) pour faire son travail.
4. Robustesse : Que vous cherchiez 10 livres ou 1000, il garde la même vitesse.
5. Mises à jour en direct : Vous pouvez ajouter de nouveaux livres pendant qu'il travaille, sans arrêter le service. C'est crucial pour les IA qui apprennent en continu.

En Résumé

PAG est comme un bibliothécaire cybernétique qui ne lit pas chaque mot de chaque livre. Il utilise des astuces statistiques (la projection) pour deviner rapidement quels livres sont pertinents, apprend de ses erreurs pour ne pas les répéter, et dessine des raccourcis intelligents dans la bibliothèque.

C'est une solution clé pour le futur de l'IA, permettant de gérer des quantités astronomiques de données (images, textes, vidéos) sans ralentir, tout en s'adaptant en temps réel aux nouvelles informations.

Résumé technique

1. Problématique et Contexte

La recherche de voisins approximaux les plus proches (ANNS) est fondamentale pour les applications d'IA modernes telles que la recherche d'images, les systèmes de recommandation et la génération augmentée par récupération (RAG). Cependant, les solutions existantes (comme HNSW, IVFPQ, ScaNN) présentent des limitations majeures face aux nouvelles exigences des charges de travail modernes :

• Inadéquation des benchmarks : Les benchmarks actuels (ANN-Benchmarks) utilisent souvent des jeux de données obsolètes (SIFT, GIST) et se concentrent uniquement sur le compromis vitesse-précision pour $K=10$, ignorant les besoins réels.
• Six exigences critiques non satisfaites simultanément :
  1. Efficacité de requête (QPS-Rappel) : Nécessité d'une vitesse élevée sans perte de précision.
  2. Temps d'indexation : Les graphes hiérarchiques (HNSW) sont souvent trop lents à construire pour un déploiement instantané.
  3. Empreinte mémoire : Besoin d'un compromis ajustable entre la taille de l'index et la précision.
  4. Passage à l'échelle en haute dimension : Les modèles d'embedding modernes (CLIP, etc.) ont des dimensions très élevées (jusqu'à 3072), où les méthodes traditionnelles peinent.
  5. Robustesse à la taille de récupération ($K$) : Les applications varient de $K=10$ (RAG) à $K=1000+$ (recommandation), et les performances doivent rester stables.
  6. Support des insertions en ligne : Capacité à mettre à jour l'index dynamiquement sans reconstruction complète (crucial pour les agents auto-évoluant).

Aucune méthode actuelle ne satisfait simultanément ces six critères, en particulier le compromis entre la vitesse d'indexation, la mémoire et la précision en haute dimension.

2. Méthodologie : PAG (Projection-Augmented Graph)

Les auteurs proposent PAG, un nouveau cadre ANNS qui intègre des techniques de projection aléatoire directement dans la construction d'un graphe de similarité. Contrairement aux méthodes précédentes qui ajoutent la projection comme un module externe, PAG l'utilise comme brique fondamentale pour déterminer quand calculer une distance exacte et quand l'approximer.

Le cadre repose sur trois composants clés unifiés :

A. Test de Routage Probabiliste (PRT - Probabilistic Routing Test)

• Objectif : Éviter les calculs de distances exacts inutiles lors de la recherche et de la construction du graphe.
• Fonctionnement : Pour un nœud visité $u$ et un candidat $w$, le PRT utilise une projection aléatoire pour estimer si l'angle entre les vecteurs $(w-u)$ et $(v-u)$ est suffisamment petit pour justifier un calcul de distance exacte.
• Avantage : Il remplace les comparaisons symétriques (coûteuses) par des comparaisons asymétriques basées sur des tests statistiques, réduisant drastiquement le nombre de calculs de distances exactes.

B. Tampon de Retour d'Information de Test (TFB - Test Feedback Buffer)

• Objectif : Optimiser le seuil du PRT et réutiliser les "faux positifs".
• Mécanisme : Le TFB maintient une structure de données (anneaux doubles) pour stocker les nœuds qui ont passé le test PRT mais qui se sont révélés être des faux positifs (trop éloignés pour être ajoutés à la liste finale).
• Innovation : Au lieu de rejeter ces nœuds, le TFB ajuste dynamiquement le seuil $\tau$ pour les réutiliser dans les tours de recherche suivants. Cela permet une augmentation incrémentielle du seuil, rendant le processus plus efficace que les méthodes statiques (comme PEOs ou KS2).

C. Sélection de Arêtes Probabiliste (PES - Probabilistic Edge Selection)

• Objectif : Améliorer la connectivité du graphe, en particulier pour les nœuds avec un faible degré d'entrée.
• Problème résolu : Les méthodes classiques (RobustPrune) ne considèrent que les voisins sortants $N_{out}(v)$ pour déterminer les voisins entrants, ce qui peut limiter la connectivité.
• Fonctionnement : Le PES étend la recherche aux tous les nœuds visités lors de la construction, pas seulement les voisins directs. Il identifie des arêtes prometteuses qui auraient été ignorées par RobustPrune, renforçant ainsi la robustesse du graphe sans coût d'indexation significatif.

Algorithme de Construction :
L'indexation suit un paradigme "recherche-et-insertion". Pour chaque nouveau nœud $v$, PAG effectue une recherche ANNS assistée par PRT-TFB pour trouver les voisins, utilise PES pour enrichir les candidats, puis applique RobustPrune pour finaliser les arêtes.

3. Contributions Techniques Clés

1. Cadre Unifié PAG : Première intégration réussie de la projection aléatoire comme composant central de la construction de graphe, permettant de traiter les distances exactes et approximatives dans un même cadre théorique.
2. Théorie Fondamentale (Théorème 3.1) : Démonstration que les projections aléatoires peuvent asymptotiquement estimer les relations angulaires entre plusieurs voisins, fournissant une base théorique solide pour PRT et PES.
3. Optimisation du Seuil (TFB) : Introduction d'un mécanisme de rétroaction qui réutilise les faux positifs, améliorant l'efficacité de l'indexation et de la recherche par rapport aux méthodes statiques.
4. Support Natif des Insertions : L'architecture hérite de la flexibilité des graphes hiérarchiques (comme HNSW), permettant des mises à jour incrémentielles avec un coût amorti constant.

4. Résultats Expérimentaux

Les auteurs ont évalué PAG sur six jeux de données modernes (textes, images, multimodaux) avec des dimensions allant de 384 à 3072, ainsi que sur des benchmarks legacy.

• Performance de Recherche (QPS-Rappel) :
  • PAG-Base est jusqu'à 5 fois plus rapide que HNSW pour un même niveau de rappel.
  • Il surpasse systématiquement les méthodes quantifiées (SymQG, ScaNN) et les graphes purs sur les jeux de données modernes, en particulier en haute dimension.
• Temps d'Indexation :
  • PAG-Base est 2 à 5 fois plus rapide que HNSW pour la construction de l'index.
  • PAG-Lite (version optimisée pour la vitesse) atteint des temps d'indexation comparables aux méthodes de quantification (IVFPQ), tout en conservant une meilleure précision.
• Empreinte Mémoire :
  • PAG offre un compromis mémoire compétitif. PAG-Lite utilise moins de mémoire que HNSW et SymQG sur la plupart des jeux de données.
• Robustesse :
  • Dimensionnalité : PAG maintient sa supériorité même lorsque la dimension $d$ augmente (jusqu'à 3072), là où SymQG échoue.
  • Taille de récupération ($K$) : Les performances de PAG restent stables pour $K=10$, $K=100$ et $K=1000$, contrairement aux méthodes quantifiées qui dégradent fortement leur rappel pour de grands $K$.
  • Insertions en ligne : PAG gère les flux de requêtes mixtes (recherche + insertion) avec une efficacité supérieure à HNSW (jusqu'à 5x plus rapide pour les insertions).

5. Signification et Conclusion

Ce travail marque une avancée significative dans le domaine de la recherche vectorielle pour l'IA moderne.

• Dépassement des limites actuelles : PAG résout le dilemme classique entre la vitesse d'indexation, la précision de recherche et la consommation mémoire, offrant une solution "tout-en-un" adaptée aux modèles d'embedding de nouvelle génération.
• Adaptabilité : Sa capacité à s'adapter dynamiquement aux tailles de récupération ($K$) et aux dimensions élevées en fait un candidat idéal pour les applications RAG, les systèmes de recommandation et les agents autonomes.
• Impact Pratique : En réduisant le temps de construction de l'index et en permettant des mises à jour en ligne efficaces, PAG facilite le déploiement de systèmes de recherche vectorielle à grande échelle et en temps réel.

En résumé, PAG représente un nouveau standard pour les solveurs ANNS, combinant la robustesse des graphes de similarité avec l'efficacité des techniques de projection, validé par des résultats empiriques supérieurs sur des données réelles et modernes.