Aller au contenu principal

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, reclasseurs et classificateurs : similarité, pertinence et décision explique d’où viennent les vecteurs ; Recherche documentaire : découpage, rappel, reclassement et citations 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 une relation : le carré de la distance entre deux vecteurs unitaires vaut 2 moins deux fois leur produit scalaire.

∥q−x∥2=2−2(q⊤x).\|q-x\|^2 = 2 - 2(q^\top x).

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 :

VecteurProduit scalaire brutSimilarité cosinusL2 au carré bruteL2 au carré après normalisation
a = (1, 1)10.70710.586
b = (3, 4)30.600200.800

Le tableau confirme cette relation : après normalisation, le produit scalaire de a avec q est son cosinus, 0,707, et 2 − 2 × 0,707 = 0,586, soit exactement la L2 au carré après normalisation ; pour b, 2 − 2 × 0,600 = 0,800.

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.

Où un projet individuel stocke ses vecteurs​

De quelques milliers à quelques centaines de milliers de passages, trois solutions suffisent ; elles diffèrent selon que les vecteurs vivent ou non avec le reste des données. La plus simple se passe de base de données : garder les vecteurs dans un tableau en mémoire ou un IndexFlat de Faiss et les comparer un par un, comme la base minimale de la recherche documentaire. Pour réunir vecteurs, texte et métadonnées dans un seul fichier local, utiliser l’extension SQLite sqlite-vec : pip install sqlite-vec, puis des requêtes SQL ; Basic Memory l’utilise sur SQLite. sqlite-vec n’a pas encore atteint la version 1.0 : son interface peut changer. Si les données sont déjà dans Postgres, utiliser pgvector : les vecteurs sont dans la même base que le reste, avec jointures et transactions. pgvector fait par défaut une recherche exacte ; ajouter un index HNSW ou IVFFlat rend la recherche approximative, et le rappel peut alors baisser.

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.

On peut y penser comme à un long voyage : l’avion jusqu’à la ville la plus proche de la destination, le train jusqu’au quartier, puis la marche jusqu’au numéro de la rue. Les couches hautes ont peu de nœuds et de longues liaisons, si bien qu’un pas traverse une grande partie du graphe ; plus on descend, plus les nœuds sont denses et les pas courts.

Suivons le parcours avec six points unidimensionnels inventés : A = 0, B = 1, C = 3, D = 6, E = 8, F = 10. La requête est q = 4 et l’on cherche deux voisins ; les carrés des distances à la requête valent 16, 9, 1, 4, 16 et 36, donc les deux vrais plus proches voisins sont C et D. L’exemple IVF de la section suivante reprend ces six points. Supposons le graphe déjà construit avec ces nœuds et ces liaisons :

CoucheNœudsLiaisons
2A, FA–F
1A, C, FA–C, C–F
0A, B, C, D, E, FA–B, B–C, C–E, D–E, D–F, E–F
  1. La couche 2 part du point d’entrée F (36). Le voisin A (16) est plus proche : on va en A ; A n’a pas de voisin plus proche, on s’arrête.
  2. La couche 1 part de A. Le voisin C (1) est plus proche : on va en C ; les voisins A et F de C sont tous deux plus loin, on s’arrête.
  3. La couche 0 part de C avec efSearch = 2 : l’ensemble des résultats garde au plus deux nœuds. Le voisin B (9) de C entre dans les résultats ; E (16) est plus loin que B, le résultat le plus lointain, et il est écarté. Le voisin A (16) de B est aussi plus loin. Il ne reste aucun candidat à explorer : la recherche s’arrête et renvoie C, B.

Le carré de la distance de D n’est que de 4, plus proche que B, mais D n’est relié qu’à E et F, et E a été écarté d’emblée : D n’est jamais visité. Avec efSearch = 3, E reste dans l’ensemble des résultats et il est exploré, D est trouvé et la recherche renvoie C, D ; en contrepartie, la couche 0 calcule des distances pour 6 nœuds au lieu de 4.

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​

Reprenons les six vecteurs fictifs à une dimension de la section précédente, 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é.

IDCoordonnéeListeDistance au carré à la requête
A0016
B109
C301
D614
E8116
F10136

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.

points = {"A": 0, "B": 1, "C": 3, "D": 6, "E": 8, "F": 10}
centers = [0, 10]
query, k = 4, 2

# Input checks: centers must be non-empty and k an integer with
# 1 <= k <= len(points); otherwise the program raises ValueError.
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. En comptant les deux calculs de distance nécessaires pour choisir les centres, ce petit exemple utilise respectivement 5 et 8 calculs de distance par requête, contre 6 pour le balayage complet : six points sont trop peu pour que le partitionnement économise du travail, et ce qui compte ici est la manière dont D est manqué.

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 :

IndexTravail de constructionStockage et coût des requêtesAjout de vecteurs
FlatSans entraînement ; stocker les vecteurs4d octets par vecteur float32 ; chaque requête les parcourt tousAjouter à la suite
HNSWFlatChercher, relier et élaguer à chaque insertion ; un budget d’exploration accru ajoute du travailVecteurs complets et connexions entre couches ; un M plus grand conserve plus de connexionsParcourir le graphe existant et relier le nouveau nœud
IVFFlatEntraîner les centroïdes, puis affecter les vecteurs aux listesVecteurs et ID occupent 4d + 8 octets par entrée, auxquels s’ajoutent centroïdes et listes ; sélectionner les centres puis parcourir les listesAffecter aux listes des centroïdes existants

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 posent le plus de problèmes. HNSW dans Faiss ne permet pas de supprimer directement un vecteur ; il faut des marqueurs d’invalidation, un filtrage des résultats et des reconstructions périodiques. Le filtrage peut laisser moins de k résultats ; les marqueurs ne libèrent pas le stockage. Ne liez pas l’identité d’un document à une position séquentielle susceptible de changer ; la documentation des opérations spéciales de Faiss indique comment les ID évoluent lors d’une suppression pour chaque type d’index. 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 :

ANN recall@k⁡=∣A∩E∣k.\operatorname{ANN\ recall@k} = \frac{|A \cap E|}{k}.

C’est le critère par intersection R-recall@R de l’implémentation de IntersectionCriterion dans Faiss. Dans l’exemple IVF, sonder une seule liste renvoie {C, B} alors que les voisins exacts sont {C, D} ; seul C est commun, donc recall@2 = 1 / 2 = 0,5.

Pour effectuer la mesure :

  1. 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.
  2. 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.
  3. Conservez l’index et faites varier efSearch pour HNSW ou nprobe pour 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.
  4. 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.

La référence exacte et l’exécution ANN doivent utiliser le même k, les mêmes filtres et la même règle de départage des ex æquo. Quand moins de k résultats reviennent, les -1 ajoutés par Faiss ne comptent pas comme voisins ; et ce rappel n’est pas le 1-recall@R de la documentation de réglage, qui ne regarde que le premier voisin exact.

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 :

JugementRéférenceProblème qu’il permet de localiser
Rappel ANNVoisins exacts pour les mêmes vecteurs et la même métriqueL’index manque des voisins
Pertinence de la recherche et rappel des preuvesPassages pertinents annotés et faits nécessairesEmbeddings, découpage ou classement manquent des preuves utilisables
Justesse et complétude de la réponseFaits applicables et conditions nécessairesLa génération utilise mal les preuves

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é. Évaluer la recherche et la génération : des preuves aux réponses correctes 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 : rechercher du code et des documents par le sens, 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.

Explorer les liensOuvrir le réseau