Index vectoriels : recherche exacte, HNSW et IVF
La recherche vectorielle représente les questions et les documents par des vecteurs, puis cherche les documents les plus proches d’une question. À mesure que le corpus grandit, comparer tous les vecteurs à chaque requête devient plus coûteux. La recherche approximative de plus proches voisins (Approximate Nearest Neighbor, ANN) réduit les comparaisons, mais peut manquer des vecteurs qui devraient figurer parmi les premiers résultats.
Embeddings, rerankers et classifieurs explique d’où viennent les vecteurs ; le pipeline de recherche décrit comment les candidats deviennent des éléments de preuve. L’index intervient entre les deux : il détermine quels vecteurs seront visités. Pour juger de son intérêt, il faut d’abord définir la proximité, puis mesurer ce qu’il économise et ce qu’il manque par rapport à une recherche exacte.
Fixer la métrique et la normalisation
Les choix courants sont la distance euclidienne (L2), le produit scalaire et la similarité cosinus. La documentation des métriques de Faiss précise que L2 renvoie une distance au carré : plus elle est faible, plus les vecteurs sont proches. Pour le produit scalaire, une valeur élevée est préférable, mais sans normalisation, ce produit n’est pas la similarité cosinus.
Pour des vecteurs non nuls, la similarité cosinus compare les directions. Diviser chaque vecteur, côté requête comme côté corpus, par sa propre norme rend le produit scalaire égal à la similarité cosinus. Les vecteurs unitaires vérifient aussi :
Avec des vecteurs unitaires, classer par L2 croissante ou par produit scalaire décroissant donne donc le même ordre. Un vecteur nul ne peut pas être normalisé ainsi ; il faut le traiter séparément avant l’indexation.
Un exemple à deux dimensions montre l’effet de la métrique. Prenons la requête q = (1, 0) et les deux vecteurs suivants ; les décimales sont arrondies à trois chiffres :
Le produit scalaire brut place b en tête ; le cosinus et, dans cet exemple, L2 brute placent a en tête. Choisissez la métrique selon les conventions de recherche du modèle d’embedding. La normalisation supprime l’information de longueur : elle n’est pas un prétraitement sans conséquence pour tous les modèles. Sinon, un index qui retrouve parfaitement les voisins peut tout de même répondre à une autre définition de la proximité.
La recherche exacte sert de référence
La documentation des index Faiss présente IndexFlatL2 et IndexFlatIP comme des recherches exhaustives : conserver les vecteurs sans compression, les comparer un à un, puis sélectionner les k premiers. « Exact » signifie ici retrouver les vrais top-k pour les vecteurs, la métrique et la précision numérique retenus. Cela ne prouve pas la pertinence des documents.
Avec N vecteurs de dimension d, le travail de calcul des distances d’un balayage complet simple croît avec N × d ; sélectionner les top-k ajoute du travail. Par exemple, un million de vecteurs float32 de dimension 768 contiennent 768,000,000 coordonnées. Les seuls vecteurs occupent 1,000,000 × 768 × 4 = 3,072,000,000 octets, soit 3,072 Go en unités décimales. Une requête compare ces coordonnées ; des requêtes simultanées augmentent le travail total.
Le traitement par lots, la vectorisation et le matériel accéléré peuvent réduire le temps écoulé. La taille du corpus ne suffit donc pas à décider d’utiliser ANN. Mesurez d’abord la latence d’un balayage complet sur le matériel et sous la charge prévus. Avec peu de données, peu de requêtes ou l’obligation de retrouver tous les plus proches voisins, construire un index complexe peut ne pas être rentable.
HNSW parcourt un graphe à plusieurs couches
La section 4 et les algorithmes 1, 2 et 5 de l’article original sur HNSW décrivent sa construction et sa recherche. HNSW signifie Hierarchical Navigable Small World. Les vecteurs sont les nœuds d’un graphe : la couche inférieure les contient tous, tandis que les couches supérieures sont de plus en plus clairsemées.
À l’insertion, la couche maximale du nouveau nœud est tirée au hasard selon une distribution à décroissance exponentielle. L’algorithme part du sommet du graphe existant et descend. Dans les couches auxquelles le nouveau nœud appartient, il cherche des candidats, choisit des voisins et établit des connexions dans les deux sens ; les connexions des nœuds existants sont élaguées si elles deviennent trop nombreuses. Une heuristique de sélection tient compte des distances entre candidats pour conserver des connexions dans plusieurs directions, au lieu de ne relier qu’un petit groupe de nœuds proches.
La requête commence au point d’entrée de la couche supérieure, avance de façon gloutonne vers des voisins plus proches, puis utilise sa position comme point d’entrée de la couche suivante. En bas, la recherche conserve un ensemble de bons résultats et explore en priorité les candidats proches en attente. Elle s’arrête lorsque le candidat en attente le plus proche est plus éloigné que le nœud le plus lointain de l’ensemble conservé. Les k résultats finaux proviennent des nœuds découverts ; un nœud non visité peut encore être plus proche.
La documentation des paramètres HNSW de Faiss décrit trois paramètres qui règlent des coûts différents : M contrôle le nombre de connexions, efConstruction la taille de l’ensemble de candidats conservé à l’insertion et efSearch cette taille à la recherche. Celle-ci doit permettre de conserver au moins k résultats. Ces tailles ne sont pas le nombre effectif de calculs de distance. Un effort de construction accru peut améliorer le graphe ; une exploration plus large améliore généralement le rappel, sans garantir une réponse exacte pour chaque requête.
IVF choisit des partitions avant de comparer leurs vecteurs
IVF, pour Inverted File, répartit les vecteurs dans nlist listes inversées. La description de la recherche par partitions dans Faiss présente une méthode courante avec L2 : k-means produit des centroïdes, chaque vecteur rejoint la liste du centroïde le plus proche, puis une requête sélectionne nprobe listes et en parcourt les vecteurs. Un index utilisant le produit scalaire choisit les centroïdes par produit scalaire maximal : les frontières obtenues avec L2 ne s’appliquent donc pas directement. Voir l’explication de Faiss sur le regroupement par produit scalaire.
Un vrai voisin situé dans une liste non sélectionnée ne devient jamais candidat. Le rapport nprobe / nlist n’est qu’une estimation grossière de la fraction parcourue : des listes de tailles différentes empêchent de l’assimiler au travail réel. Augmenter nprobe élargit les candidats et le balayage.
IndexIVFFlat calcule encore les distances sur des vecteurs non compressés dans les listes sélectionnées ; l’approximation vient donc principalement des listes ignorées. Le guide de Faiss sur les pertes de précision explique que nprobe = nlist parcourt toutes les listes. IVFFlat retrouve alors les résultats d’un balayage complet si la sélection des centroïdes est exacte, la métrique et la précision numérique sont identiques, et aucune limite de balayage supplémentaire n’est appliquée ; l’ordre des ex æquo peut toutefois différer. IndexIVFPQ compresse aussi les vecteurs par quantification produit (PQ), ce qui ajoute une approximation des distances. Augmenter nprobe ne suffit pas à supprimer cette erreur de compression.
Exemple complet : manquer un voisin au-delà d’une frontière
Prenons six vecteurs fictifs à une dimension, la requête q = 4 et deux voisins à retrouver. Avec des centres fixés à 0 et 10, les points inférieurs à 5 vont dans la liste 0, ceux supérieurs à 5 dans la liste 1 ; un point égal à 5 rejoint la liste 0, le plus petit numéro de liste départageant les ex æquo. Les centres sont choisis à la main pour isoler la sélection des candidats ; aucun entraînement k-means n’est effectué.
Les distances au carré entre la requête et les centres valent 16 et 36 : sonder une seule liste sélectionne donc la liste 0. Les top-2 exacts sont C et D, mais les deux meilleurs de la liste 0 sont C et B. D est plus proche que B, pourtant sa liste n’a jamais été visitée.
Ce programme Python 3 utilise uniquement la bibliothèque standard. Il effectue l’affectation, le balayage complet, le balayage des partitions et le calcul du rappel. Les distances égales sont départagées par ID, et les distances égales aux centroïdes par numéro de liste ; il n’y a pas d’égalité à la frontière des top-2 dans cet exemple. Le programme exige au moins un centre et un entier k tel que 1 <= k <= len(points) ; sinon, il lève ValueError.
points = {"A": 0, "B": 1, "C": 3, "D": 6, "E": 8, "F": 10}
centers = [0, 10]
query, k = 4, 2
if not centers:
raise ValueError("centers must not be empty")
if type(k) is not int or not 1 <= k <= len(points):
raise ValueError("k must be an integer between 1 and len(points)")
def distance2(a, b):
return (a - b) ** 2
def rank(ids):
return sorted(ids, key=lambda i: (distance2(query, points[i]), i))
lists = {j: [] for j in range(len(centers))}
for i, x in points.items():
j = min(lists, key=lambda j: (distance2(x, centers[j]), j))
lists[j].append(i)
exact = rank(points)[:k]
print("lists:", lists)
print("distances:", [(i, distance2(query, points[i])) for i in rank(points)])
print("exact:", exact)
for nprobe in (1, 2):
selected = sorted(lists, key=lambda j: (distance2(query, centers[j]), j))[:nprobe]
candidates = [i for j in selected for i in lists[j]]
found = rank(candidates)[:k]
recall = len(set(found) & set(exact)) / k
print(f"nprobe={nprobe}: lists={selected}, scanned={len(candidates)}, "
f"found={found}, ANN recall@{k}={recall:.3f}")
Sortie :
lists: {0: ['A', 'B', 'C'], 1: ['D', 'E', 'F']}
distances: [('C', 1), ('D', 4), ('B', 9), ('A', 16), ('E', 16), ('F', 36)]
exact: ['C', 'D']
nprobe=1: lists=[0], scanned=3, found=['C', 'B'], ANN recall@2=0.500
nprobe=2: lists=[0, 1], scanned=6, found=['C', 'D'], ANN recall@2=1.000
Sonder une liste réduit de 6 à 3 le nombre de vecteurs du corpus parcourus et retrouve un voisin exact ; sonder les deux en retrouve deux. Choisir les centres demande deux calculs de distance supplémentaires. Ce petit exemple utilise donc respectivement 5 et 8 calculs de distance par requête, contre 6 pour le balayage complet. Il montre le mécanisme des omissions, sans donner un facteur d’accélération pour un index réel.
Construction, mémoire, mises à jour et suppression
Un index reporte une partie du travail des requêtes sur sa construction. Le guide de choix de Faiss distingue Flat et HNSW, sans entraînement, d’IVF, qui commence par un regroupement à partir d’un échantillon représentatif de vecteurs. Le tableau compare les variantes sans compression et reprend les éléments de stockage du tableau des index Faiss :
Ces éléments ne donnent pas la mémoire totale du processus : textes des documents, métadonnées, surcoût d’allocation et espace temporaire des requêtes s’y ajoutent. HNSW et IVF peuvent aussi être combinés : IVF peut utiliser HNSW pour chercher les centroïdes.
La suppression et le remplacement dépendent de l’implémentation. La documentation des opérations spéciales de Faiss explique qu’une suppression dans Flat décale les ID séquentiels suivants. IVF stocke des ID explicites et conserve les autres ID lors d’une suppression. L’accès et les mises à jour par ID dans IVF font intervenir DirectMap : le mode Array ne permet pas la suppression ; Hashtable avec IDSelectorArray peut éviter un parcours complet de l’index lors de la suppression. Ne liez pas l’identité d’un document à une position séquentielle susceptible de changer.
HNSW dans Faiss ne permet pas de supprimer directement un vecteur. Si l’application recourt à des marqueurs d’invalidation, au filtrage des résultats et à des reconstructions périodiques, il faut concevoir ces mécanismes de maintenance en plus de l’index. Le filtrage peut laisser moins de k résultats ; les marqueurs ne libèrent ni le stockage des vecteurs ni celui du graphe. Après modification d’un texte, invalidez son ancien vecteur et placez le nouveau dans un index interrogeable. Si le modèle d’embedding ou la convention de normalisation change, migrez ensemble le corpus et les requêtes. Après des ajouts incrémentaux, remesurez le rappel et la répartition des listes pour décider d’une reconstruction. Pour réentraîner les centroïdes IVF, entraînez un nouvel index et réaffectez tous les vecteurs encore valides : Faiss ne permet pas de réentraîner directement un index déjà rempli.
Mesurer le rappel ANN par rapport aux voisins exacts
Pour une requête, E est l’ensemble des ID des top-k exacts, et A celui des top-k renvoyés par ANN. On définit :
Cela correspond au critère par intersection R-recall@R de l’implémentation de IntersectionCriterion dans Faiss. Il diffère de 1-recall@R, défini dans le même fichier, qui vérifie si le premier voisin exact figure parmi R résultats. La documentation de réglage présente les deux critères. Ici, k doit être un entier strictement positif et il doit y avoir au moins k vecteurs admissibles. A contient uniquement les ID de voisins réellement renvoyés ; les -1 qui complètent une liste de résultats trop courte ne comptent pas comme voisins. Si des distances sont égales, utilisez le même ordre déterministe ou définissez à l’avance un score qui accepte les ex æquo.
Pour effectuer la mesure :
- Figez le corpus, les embeddings, la normalisation, la métrique, k et les filtres. Calculez la référence exacte sur le même corpus admissible.
- Calculez les top-k exacts pour des requêtes représentatives de l’usage, puis lancez ANN. Mesurez le rappel par intersection pour chaque requête, publiez la moyenne et examinez les requêtes à faible rappel.
- Conservez l’index et faites varier
efSearchpour HNSW ounprobepour IVF. Relevez le rappel, la distribution des latences, le débit et la mémoire, en gardant fixes matériel, taille des lots, concurrence et conditions de cache. - Si élargir le budget de recherche ne suffit pas, examinez la construction du graphe, l’entraînement des centroïdes, le filtrage et la compression des vecteurs. Confirmez le réglage sur un jeu de requêtes indépendant. Intégrez aussi au choix le temps de construction, le pic de mémoire et le coût des mises à jour.
Ne poussez pas automatiquement le budget de recherche au maximum : choisissez un réglage qui atteint le rappel requis dans le budget de latence et de ressources. Un rappel de 1,0 sur une requête ne démontre pas une recherche exacte sur tout le corpus.
Rappel des voisins, pertinence des preuves et justesse de la réponse
Ces jugements reposent sur des références différentes :
Même avec un rappel ANN de 1,0, les voisins exacts peuvent être des instructions périmées qui partagent seulement le sujet. Inversement, un autre passage peut fournir des preuves suffisantes malgré un voisin vectoriel manqué. L’évaluation de la recherche et de la génération couvre les deux autres jugements ; le reclassement ne peut réordonner que les passages déjà présents parmi les candidats.
Avec un outil de recherche sémantique comme zvec-grep, cette distinction permet de séparer « l’index a manqué des voisins vectoriels » de « les voisins vectoriels ne répondent pas à la question ». Consultez l’implémentation propre à l’outil pour connaître son index et les paramètres exposés, puis ouvrez les fichiers sources renvoyés pour vérifier leur contenu.