A Comparative Study of Vector Indexing Strategies Using Facebook AI Similarity Search as a Case Study

Imaginez que vous vous tenez dans une bibliothèque qui contient tous les livres jamais écrits, mais que ces livres ne sont pas organisés par titre ou par auteur. À la place, ils sont triés selon la façon dont ils se « ressemblent ». Si vous demandez l'histoire d'un chat courageux, le bibliothécaire ne se contente pas de trouver des livres contenant les mots « courageux » et « chat » ; il trouve des histoires qui capturent l'essence de cette idée, même si les mots sont différents. C'est la magie de l'intelligence artificielle moderne : transformer des idées en listes de nombres (appelés vecteurs) et trouver ensuite les correspondances les plus proches dans un océan de données.

Mais voici le problème : si votre bibliothèque contient un milliard de livres, vérifier chaque livre pour trouver la meilleure correspondance prendrait une éternité. C'est comme essayer de trouver un grain de sable spécifique sur une plage en ramassant chaque grain un par un. Pour résoudre cela, les scientifiques ont inventé des « index » — des raccourcis spéciaux qui aident l'ordinateur à sauter les parties ennuyeuses pour passer directement aux choses intéressantes. Certains raccourcis sont comme une carte super organisée (recherche exacte), tandis que d'autres sont comme un jeu de devinettes intelligent qui vous amène à 99 % du but en une fraction de seconde (recherche approximative). La grande question est : quel raccourci est le meilleur ? Cela dépend-il de la taille de votre bibliothèque ? Est-ce important si vous avez un petit carnet de notes ou un immense entrepôt pour stocker vos livres ?

C'est exactement ce qu'une équipe de chercheurs de l'Université européenne d'Arménie a cherché à déterminer. Ils ont pris un outil populaire appelé FAISS (Facebook AI Similarity Search), qui est comme un couteau suisse pour ces raccourcis de vecteurs, et ont mis ses différents outils à l'épreuve. Ils voulaient voir comment chaque outil performait lorsque les données devenaient massives, lorsque les chiffres devenaient complexes et lorsque la mémoire était limitée. Considérez cela comme une course massive où différents types de moteurs de recherche s'affrontent pour voir qui peut trouver la bonne réponse le plus vite sans manquer de souffle ou de mémoire.

Les chercheurs ont testé plusieurs stratégies différentes, allant de la méthode de la « force brute » (vérifier tout) à des astuces intelligentes impliquant le regroupement (clustering), la compression (réduire la taille des données pour gagner de l'espace) et la navigation par graphes (utiliser un réseau de connexions pour bondir vers la réponse). Ils ont mesuré deux éléments principaux : le Rappel (avez-vous trouvé la bonne réponse ?) et la Latence (combien de temps cela a-t-il pris ?).

Voici ce qu'ils ont découvert lors de leurs expériences :

Le champion de la « Force Brute » (IndexFlat)
Imaginez un détective qui refuse de deviner ; il vérifie chaque suspect dans le rang. C'est la méthode IndexFlat. Les chercheurs ont constaté que cette approche est parfaite : elle ne manque jamais la bonne réponse (100 % de rappel). Cependant, elle est incroyablement lente. À mesure que le nombre de « suspects » (vecteurs) passait de 1 000 à 10 000, le temps nécessaire pour trouver la réponse augmentait régulièrement. Si vous avez un petit ensemble de données, c'est parfait. Mais si vous avez des millions de vecteurs, cette méthode devient trop lente pour être utile dans le monde réel. C'est comme utiliser un microscope pour trouver une aiguille dans une botte de foin ; cela fonctionne, mais cela prend un temps infini.

La stratégie de « Groupement » (IVFFlat)
Ensuite, ils ont essayé une méthode qui regroupe les vecteurs similaires en grappes, comme le tri de livres dans des bacs étiquetés « Aventure », « Romance » et « Mystère ». C'est l'IndexIVFFlat. Lorsqu'une requête arrive, le système ne vérifie que les bacs les plus susceptibles de contenir la réponse. L'étude a montré que c'est un excellent compromis. C'est beaucoup plus rapide que de tout vérifier, et vous pouvez l'ajuster pour être plus précis en vérifiant plus de grappes. Les chercheurs ont constaté que si vous vérifiez plus de clusters (un paramètre appelé nprobe), vous obtenez de meilleurs résultats, mais cela prend un peu plus de temps. C'est un outil flexible qui équilibre bien vitesse et précision pour les ensembles de données de taille moyenne à grande.

Les experts de la « Compression » (IVFPQ et IVFSQ)
Et si vous aviez un milliard de vecteurs mais pas assez d'espace sur votre disque dur pour tous les stocker ? Les chercheurs ont examiné l'IndexIVFPQ et l'IndexIVFSQ, qui sont comme la compression d'un film haute définition en un fichier plus petit. Ils compressent les données pour qu'elles occupent moins de mémoire.

• IVFPQ (Product Quantization) divise les vecteurs en petites parties et les compresse. L'étude a montré que c'est le champion pour les ensembles de données massifs où la mémoire est le problème principal. C'est incroyablement rapide et utilise très peu d'espace, bien qu'il puisse occasionnellement manquer la réponse parfaite (rappel légèrement inférieur).
• IVFSQ (Scalar Quantization) est une version plus simple de la compression. C'est un bon « enfant du milieu » — il économise de l'espace et est plus rapide que les versions non compressées, mais il ne compresse pas aussi agressivement que l'IVFPQ. Les chercheurs ont noté que, bien qu'il perde un peu de précision par rapport à la version non compressée, les économies de mémoire en valent souvent la peine pour les systèmes à grande échelle.

Le « Réseau de Connexions » (HNSW)
Enfin, il y avait l'IndexHNSW, qui organise les données en un réseau multicouche, comme une carte de métro avec des lignes express et des arrêts locaux. Vous commencez au niveau supérieur (la ligne express) pour prendre une direction générale, puis vous zoomez couche par couche pour trouver l'arrêt exact. L'étude a montré que c'est le grand gagnant en termes de vitesse et de précision. Il est « Très Rapide » et possède un rappel « Très Élevé ». Cependant, il nécessite un peu plus de mémoire pour construire le réseau, et les chercheurs ont noté qu'il faut le régler avec soin. Si vous rendez le réseau trop dense (trop de connexions), la recherche devient plus lente ; si vous le rendez trop clairsemé, vous pourriez manquer la meilleure réponse. Mais lorsqu'il est bien réglé, il offre le meilleur équilibre entre vitesse et précision.

Le Verdict
L'article conclut qu'il n'existe pas d'outil unique « meilleur » pour chaque tâche. C'est comme demander si un marteau, un tournevis ou une clé est le meilleur outil ; cela dépend de ce que vous construisez.

• Si vous avez un petit ensemble de données et que vous avez besoin d'une précision parfaite, utilisez l'index Flat.
• Si vous avez un ensemble de données de taille moyenne et que vous avez besoin d'un équilibre, IVFFlat est un choix solide.
• Si vous gérez des milliards de vecteurs et que votre ordinateur manque de mémoire, IVFPQ est votre meilleur allié.
• Si vous avez besoin de la recherche la plus rapide possible avec une grande précision et que vous avez assez de mémoire, HNSW est le vainqueur.

Les chercheurs ont également testé différentes façons de mesurer la « similitude » (comme la proximité de deux points dans l'espace). Ils ont confirmé que pour certains types de modèles d'IA (comme ceux utilisés pour le langage), vous devez d'abord normaliser les données pour que les calculs fonctionnent correctement, mais une fois cela fait, les différentes stratégies d'indexation tiennent bien la route.

En résumé, cette étude constitue un guide pratique pour toute personne construisant des systèmes d'IA. Elle nous apprend que, bien que nous ne puissions pas tout avoir (vitesse parfaite, précision parfaite et utilisation nulle de la mémoire en même temps), nous pouvons choisir le bon compromis pour nos besoins spécifiques. Que vous construisiez un système de détection de fraude pour une banque ou un moteur de recherche pour des dossiers médicaux, il existe une stratégie d'indexation spécifique dans cette boîte à outils qui vous aidera à trouver l'aiguille dans la botte de foin sans vous perdre.