Technical Tutorials

À l'ère de l'IA générative et de la recherche sémantique, la capacité à récupérer efficacement des embeddings pertinents à partir de jeux de données massifs est primordiale. Alors que les représentations vectorielles denses sont devenues la norme en traitement du langage naturel (NLP) et en vision par ordinateur, la mise à l'échelle de ces systèmes à des milliards de vecteurs introduit des défis importants en termes de latence et de consommation de mémoire. FAISS (Facebook AI Similarity Search) reste la bibliothèque de référence pour cette tâche, mais la recherche brute-force par défaut est souvent insuffisante pour les applications de niveau production. Cet article explore trois stratégies distinctes pour optimiser la récupération : les Index de Fichier Inversé (IVF), les graphes HNSW (Hierarchical Navigable Small World) et les solutions de stockage basées sur DiskANN.

Comprendre les compromis de performance

Avant de plonger dans l'implémentation, il est crucial de comprendre que l'optimisation de la recherche vectorielle est un exercice d'équilibre entre la rappel (recall), la latence et la consommation de mémoire. La recherche brute-force garantit un rappel de 100 % mais évolue linéairement avec la taille du jeu de données ($O(N)$), ce qui la rend peu pratique pour les systèmes à grande échelle. Les techniques d'indexation approchent la recherche du plus proche voisin (ANN) pour atteindre une complexité logarithmique, sacrifiant un petit pourcentage de rappel pour des gains massifs en vitesse.

Stratégie 1 : IVF (Index de Fichier Inversé) pour l'efficacité mémoire

L'index IVF partitionne l'espace vectoriel en $k$ clusters en utilisant k-means. Lors de l'indexation, chaque vecteur est assigné à son centroïde le plus proche. Au moment de la recherche, seuls les centroïdes les plus proches du vecteur de requête sont examinés. Cela réduit l'espace de recherche de $N$ à $N/k$, accélérant considérablement la récupération.

IVF est très économe en mémoire par rapport aux méthodes basées sur des graphes et offre des performances prévisibles, bien qu'il nécessite un réglage minutieux du nombre de clusters ($nlist$) et des paramètres de sonde ($nprobe$).

import faiss
import numpy as np

# Création d'un index plat pour comparaison (Brute Force)
d = 128  # Dimensionnalité
nlist = 100  # Nombre de clusters
k = 5  # Nombre de voisins les plus proches

# Initialisation de l'index IVF
quantizer = faiss.IndexFlatL2(d)
index = faiss.IndexIVFFlat(quantizer, d, nlist, faiss.METRIC_L2)

# Entraînement sur un sous-ensemble de données
train_data = np.random.random((10000, d)).astype('float32')
index.train(train_data)

# Ajout des vecteurs
index.add(train_data)

# Recherche avec sondes contrôlées
nprobe = 10  # Nombre de clusters à rechercher
index.nprobe = nprobe

Stratégie 2 : HNSW pour une latence ultra-faible

Pour les scénarios où une latence inférieure à la milliseconde est critique, comme dans les moteurs de recommandation en temps réel, HNSW est souvent le choix supérieur. HNSW construit une structure de graphe multicouche où les nœuds représentent les vecteurs. Les couches supérieures offrent une "voie rapide" pour la navigation à longue distance, tandis que les couches inférieures affinent la recherche localement.

L'avantage principal de HNSW est son élevé rappel à faible latence. Cependant, il présente une empreinte mémoire plus élevée en raison du stockage de la connectivité du graphe et est plus coûteux en calcul lors de la phase de construction de l'index.

# Note : L'implémentation HNSW de FAISS est disponible dans les versions récentes
# ou via le package faiss.contrib

# Construction de l'index HNSW
M = 16  # Nombre de liens bidirectionnels créés pour chaque nouvel élément
maxM = 16
efConstruction = 200  # Paramètre de qualité

index_hnsw = faiss.IndexHNSWFlat(d, M, faiss.METRIC_L2)
index_hnsw.hnsw.efConstruction = efConstruction
index_hnsw.hnsw.M = M

# Construction de l'index (peut être lent pour les grands jeux de données)
index_hnsw.add(train_data)

# Configuration de la requête
ef_search = 50  # Taille de la liste dynamique pour la recherche
index_hnsw.hnsw.efSearch = ef_search

Stratégie 3 : DiskANN pour une mise à l'échelle à l'échelle du milliard

Lorsque la taille des jeux de données dépasse la RAM disponible, les index en mémoire traditionnels comme IVF et HNSW échouent. C'est ici que DiskANN (Disk Accelerated Nearest Neighbor) brille. DiskANN exploite la vitesse d'accès aléatoire des SSD modernes pour stocker les structures de graphe sur le disque tout en ne conservant que les métadonnées critiques en mémoire. Il utilise une approche de recherche en deux phases : une recherche grossière pour identifier les blocs candidats sur le disque, suivie d'une recherche fine au sein de ces blocs.

Bien que l'intégration directe de DiskANN avec FAISS nécessite des builds spécialisés ou des wrappers, cette stratégie est vitale pour les bases de données vectorielles à l'échelle de l'entreprise gérant des pétaoctets de données d'embedding.

Conclusion

L'optimisation de FAISS n'est pas une solution unique. Pour les applications générales avec des contraintes de mémoire modérées, IVF offre un équilibre robuste entre vitesse et utilisation de la mémoire. Pour les exigences de haute performance où la latence est le goulot d'étranglement, HNSW offre des ratios rappel-latence supérieurs. Enfin, pour les jeux de données massifs qui ne tiennent pas dans la RAM, l'adoption d'une architecture DiskANN est essentielle. En comprenant les compromis de chaque stratégie, les développeurs peuvent construire des systèmes de récupération d'embeddings évolutifs et efficaces qui alimentent la prochaine génération d'applications IA.