HNSW : comment trouver le plus proche voisin parmi des millions de vecteurs

Comparer un vecteur de requête à un million d'autres vecteurs de manière exhaustive nécessite un million d'opérations à chaque recherche. Ce n'est pas viable à grande échelle. HNSW privilégie la vitesse au détriment de la précision absolue, et ce compromis s'avère très avantageux.

Graphique à plusieurs niveaux

L'idée s'inspire du trajet que l'on effectue pour aller de Hanoï à Hô Chi Minh-Ville : on commence par un vol long-courrier, puis on prend un taxi une fois sur place, et enfin on marche. HNSW a créé plusieurs niveaux de graphiques :

• L'étage supérieur est très clairsemé, chaque arête effectuant un grand saut dans l'espace vectoriel
• La couche inférieure devient progressivement plus dense, les arêtes raccourcissent
• La couche inférieure contient tous les points ; les arêtes relient des points réellement proches les uns des autres

La recherche commence à l'étage supérieur, progresse de manière gloutonne vers le point le plus proche de la requête ; lorsqu'elle atteint une impasse, elle redescend à l'étage inférieur et recommence. Le nombre d'étapes augmente selon une fonction logarithmique du nombre de points, et non de manière linéaire.

Les deux paramètres que vous devrez régler

• M — le nombre de voisins conservés pour chaque nœud. Plus ce nombre est élevé, plus la recherche est précise, mais plus elle consomme de mémoire vive
• efSearch — le nombre de candidats conservés dans la file d’attente pendant la recherche. Il s’agit d’un compromis entre vitesse et précision, que l’on peut ajuster à l’exécution sans avoir à reconstruire l’index

Ce qu'il faut savoir avant de faire son choix

HNSW conserve presque toujours l'intégralité de son index en mémoire vive — c'est là la principale contrainte en termes de coût à grande échelle. La suppression d'éléments est également difficile : la plupart des implémentations se contentent de marquer les éléments comme supprimés et doivent les reconstruire périodiquement.

Le résultat est « à peu près correct ». Avec la recherche sémantique, on passe à côté d'un résultat classé huitième, ce que personne ne remarque. Avec la correspondance exacte, il vaut mieux ne pas l'utiliser.