HNSW Explorer : « Hierarchical Navigable Small World », visualisé

Observez le parcours d’une recherche à travers le graphe en couches — de la couche supérieure clairsemée (autoroutes) jusqu’à la couche inférieure dense (routes locales). Faites glisser le point de requête sur la couche 0 et réglez l’ M e / ef pour observer comment le graphe évolue.

Nombre maximal de voisins par nœud

ef8

Ensemble de candidats de couche 0

Vitesse450ms

À chaque étape

Étape en cours

14 / 14

Recherche terminée. Top-3: [3, 10, 4].

Statistiques de recherche

Visité

17 / 30

Couches

Entrée

Nœud 0

Top-3

[3, 10, 4]

Répartition des couches

Fonctionnement d’ HNSW

Graphique en couches : chaque nœud se voit attribuer aléatoirement une couche maximale selon une distribution exponentielle. La plupart des nœuds ne se trouvent qu’au niveau de la couche 0 ; très peu atteignent le sommet.
Au sein de chaque couche : chaque nœud est connecté à ses voisins les plus proches M. Les couches supérieures sont clairsemées (peu de nœuds, arêtes longues = « autoroutes »). La couche 0 est dense (tous les nœuds, arêtes courtes = « routes locales »).
La recherche commence par le haut : à partir d’un point d’entrée fixe, parcourez de manière gloutonne jusqu’au voisin le plus proche de la requête, et répétez l’opération jusqu’à ce qu’il n’y ait plus d’amélioration.
Descendez d’un niveau et répétez l’opération : la position du niveau précédent devient le point de départ du parcours du niveau suivant. Chaque descente affine le résultat avec des arêtes plus fines.
Couche 0 avec « ef » : à la couche inférieure, au lieu de s’arrêter au premier minimum local, « HNSW » conserve un ensemble de ef meilleurs candidats et élargit leur voisinage. Plus grand ef → plus précis mais plus lent.

Pourquoi est-ce rapide ? Les couches supérieures agissent comme un index sur l’index : vous parcourez d’énormes distances en seulement quelques sauts, puis vous zoomez. Pour N points, la recherche visite environ O(log N) nœuds au lieu de N.

Qu’est-ce que « HNSW » ?

HNSW (Hierarchical Navigable Small World) est un algorithme approximatif de plus proche voisin basé sur des graphes. Il organise les vecteurs en une pile de graphes « small world » navigables : des couches supérieures clairsemées avec des arêtes de longue portée pour un routage grossier, et une couche inférieure dense avec des arêtes courtes pour la traversée finale à granularité fine. Une recherche progresse de manière gloutonne vers la requête à chaque couche, puis redescend — visitant environ O(log N) nœuds au lieu de parcourir l’ensemble des N.

HNSW est l’index vectoriel en mémoire le plus largement utilisé, et l’index de graphe par défaut dans Milvus. Milvus propose également HNSW_SQ et HNSW_PQ des variantes qui quantifient les vecteurs stockés afin de réduire l’empreinte mémoire au prix d’une légère perte de rappel.

HNSW paramètres dans Milvus

M (temps de construction) : nombre maximal d’arêtes par nœud, le même paramètre que le curseur ci-dessus. Les valeurs typiques sont comprises entre 8 et 64. Une valeur M plus élevée améliore le rappel et la connectivité du graphe, mais augmente la consommation de mémoire de manière linéaire et ralentit la construction.
efConstruction (temps de construction) : taille du pool de candidats utilisée lors de l’insertion des nœuds. Des valeurs plus élevées permettent de construire un graphe de meilleure qualité (rappel plus élevé) au prix d’une construction d’index plus lente. Les valeurs typiques sont comprises entre 100 et 500.
ef / ef_search (durée de la requête) : l’ensemble de candidats conservé pendant le parcours de la couche 0 — le principal paramètre de rappel/latence au moment de la recherche. Il doit être au moins égal à votre top-K. Augmentez-le jusqu’à ce que le rappel atteigne un plateau ; la latence augmente de manière à peu près linéaire avec ce paramètre.

HNSW vs IVF vs DiskANN

HNSW offre généralement la meilleure latence de requête avec un rappel élevé pour la recherche en mémoire — c’est pourquoi c’est le choix par défaut lorsque le jeu de données (plus la surcharge du graphe) tient dans RAM. Ses coûts sont la mémoire et le temps de construction : le graphe ajoute une surcharge notable par vecteur, et les insertions sont plus lentes que l’affectation k-means de IVF. Optez pour IVF lorsque vous avez besoin d’une construction rapide des index ou d’une quantification agressive, et pour DiskANN lorsque le jeu de données est trop volumineux pour RAM mais que vous avez tout de même besoin d’un taux de rappel élevé.

Foire aux questions

Que contrôle le paramètre M dans « HNSW » ?

M limite le nombre d’arêtes que chaque nœud conserve par couche. Une valeur de M plus élevée améliore la connectivité du graphe — rappel plus élevé et routage plus robuste — mais la mémoire augmente linéairement avec M et la construction de l’index ralentit. Les valeurs comprises entre 8 et 64 couvrent la plupart des charges de travail ; la plage 16–32 constitue généralement un bon compromis.

Quelle est la différence entre ef et efConstruction?

Ces deux paramètres correspondent à la taille du pool de candidats, appliqués à des moments différents. La « densité de recherche » ( efConstruction ) est utilisée lors de la construction de l’index : elle détermine avec quelle rigueur chaque nœud inséré recherche ses voisins, contrôlant ainsi la qualité du graphe. La « largeur de recherche » ( ef ) (ef_search) est utilisée au moment de la requête : elle contrôle l’étendue de la recherche au niveau de la couche 0 (Layer-0), en faisant un compromis entre la latence et le rappel pour chaque requête.

De combien de mémoire un index « HNSW » a-t-il besoin ?

En gros, les vecteurs bruts plus le graphe : environ d × 4 octets par vecteur pour les données float32, plus de l’ordre de M × 2 × 8 octets d’arêtes par nœud. Pour les déploiements à mémoire limitée, Milvus propose HNSW_SQ et HNSW_PQ, qui quantifient les vecteurs stockés, ou DiskANN, qui déplace les vecteurs complets vers SSD.

Quand dois-je utiliser « HNSW » plutôt que « IVF » ?

Utilisez « HNSW » lorsque la latence de la requête avec un rappel élevé est la priorité et que l’index tient en mémoire — cette option l’emporte généralement. Privilégiez « IVF » lorsque vous reconstruisez fréquemment des index (constructions bien plus rapides), ou lorsqu’elle est combinée à la quantification « SQ8 » / «PQ » pour s’adapter à un budget mémoire restreint.

Pour aller plus loin : consultez la documentation «HNSW » pour connaître les paramètres exacts de l’index, ou consultez «Index Explained» pour obtenir le guide de décision complet.