HNSW
HNSW (hierarchical navigable small world) est un index à base de graphe pour la recherche approximative des plus proches voisins. Il relie les vecteurs à leurs voisins sur plusieurs couches, afin qu'une recherche puisse progresser rapidement vers les correspondances les plus proches.
Aussi appelé : hierarchical navigable small world, HNSW index
Par Divya Sharma · Vérifié le 15 nov. 2026 · Notre méthode
HNSW est l'index par défaut de nombreuses bases de données vectorielles. Il a été décrit par Malkov et Yashunin dans un article mis en ligne pour la première fois en 2016, et il est populaire parce qu'il offre un rappel élevé avec des requêtes rapides et ne nécessite aucune étape d'entraînement.
Comment ça marche
Chaque vecteur devient un nœud relié à certains de ses plus proches voisins. Le graphe comporte plusieurs couches. La couche du bas contient tous les vecteurs ; chaque couche supérieure en contient un sous-ensemble aléatoire de plus en plus réduit, si bien que le sommet est clairsemé avec de longues liaisons. Une recherche commence au sommet, se rapproche de façon gloutonne de la requête, puis descend d'une couche et recommence à pas plus fins jusqu'à atteindre le bas. L'article indique que le coût de recherche croît de façon logarithmique.
Imaginez la recherche d'une adresse : d'abord l'autoroute, puis les routes principales, puis les petites rues.
Les réglages que vous verrez
Les principaux réglages sont le nombre de liaisons que garde chaque nœud (souvent appelé M), la largeur de la recherche pendant la construction du graphe (ef_construction) et sa largeur au moment de la requête (ef ou ef_search). Des valeurs plus élevées augmentent le rappel et coûtent davantage de mémoire ou de temps. Réglez-les d'après des métriques de récupération sur vos propres données.
Limites
HNSW garde le graphe, et généralement les vecteurs, en mémoire, ce qui devient coûteux à grande échelle. La suppression d'éléments peut laisser le graphe moins bien connecté, et le combiner avec un filtrage par métadonnées strict peut réduire le rappel. D'autres index de recherche approximative des plus proches voisins arbitrent différemment entre ces coûts.
Termes liés
- Recherche approximative des plus proches voisins
- La recherche approximative des plus proches voisins (ANN, approximate nearest neighbor) trouve des vecteurs proches d'une requête sans vérifier chaque vecteur stocké. Elle renonce à la garantie d'obtenir exactement la meilleure correspondance en échange d'une recherche bien plus rapide sur de grandes collections.
- Base de données vectorielle
- Une base de données vectorielle (vector database) stocke des embeddings avec leurs enregistrements source et retrouve les vecteurs stockés les plus proches d'un vecteur de requête, généralement à l'aide d'un index approximatif pour que la recherche reste rapide sur des millions d'éléments.
- Recherche vectorielle
- La recherche vectorielle (vector search) trouve des éléments en comparant leurs embeddings à celui d'une requête et en renvoyant les plus proches, si bien que les résultats correspondent par le sens plutôt que par des mots-clés communs.
- Filtrage par métadonnées
- Le filtrage par métadonnées (metadata filtering) limite une recherche aux éléments dont les attributs stockés, comme la date, l'auteur, la langue ou le groupe d'accès, remplissent des conditions données, en complément ou en amont du classement par similarité vectorielle.
- Métriques de recherche (recall@k, nDCG, MRR)
- Les métriques de recherche (retrieval metrics) mesurent la capacité d'un système de recherche à renvoyer des documents pertinents. Recall@k vérifie combien d'éléments pertinents figurent dans les k premiers, nDCG récompense un classement élevé de ces éléments, et MRR mesure à quel rang apparaît le premier résultat correct.