Index HNSW expliqué : le graphe qui accélère la recherche

HNSW (Hierarchical Navigable Small World) est l'index le plus répandu pour chercher vite les vecteurs les plus proches d'une question. Au lieu de comparer la question à tous les vecteurs, il parcourt un graphe à plusieurs niveaux : quelques points très reliés en haut pour traverser vite l'espace, tous les points en bas pour affiner. La recherche est approximative : très rapide, mais elle peut manquer quelques voisins, selon les réglages.

Le problème qu'il résout

Sans index, chercher les cinq passages les plus proches d'une question, c'est calculer la distance avec chaque passage, puis trier : la recherche exacte. Le rappel est parfait, mais le temps croît avec le nombre de passages. La documentation de Sentence Transformers situe autour d'un million d'entrées la limite d'une recherche exacte faite à la main, et renvoie au-delà vers des bibliothèques de recherche approximative (Sentence Transformers), parmi lesquelles hnswlib et FAISS.

Le principe, d'après l'article d'origine

La méthode a été publiée par Yu. A. Malkov et D. A. Yashunin, dans un article déposé le 30/03/2016. Les idées clés :

1. Une pile de graphes de proximité. Chaque vecteur est un nœud relié à ses voisins proches. Les niveaux supérieurs ne contiennent qu'une partie des nœuds, chacun étant inclus dans le niveau du dessous.
2. Un niveau maximal tiré au hasard. À l'insertion, chaque élément reçoit un niveau maximal tiré selon une loi dont la probabilité décroît de façon exponentielle : beaucoup de nœuds restent en bas, très peu montent en haut.
3. Une recherche du haut vers le bas. On part du niveau supérieur, où les liens couvrent de grandes distances, on se rapproche de la cible, puis on descend d'un niveau pour affiner avec des liens plus courts. Les auteurs annoncent une complexité qui croît de façon logarithmique.
4. Un choix des voisins réfléchi. Une heuristique de sélection des voisins améliore nettement les performances à rappel élevé et sur des données très regroupées.

Une image, illustrative : pour trouver une rue dans une ville inconnue, on prend d'abord l'autoroute (niveau haut), puis la nationale, puis les rues du quartier (niveau bas).

Les trois réglages

Le dernier se change sans reconstruire l'index : c'est le levier à essayer en premier.

Les valeurs par défaut selon les bases

D'après la documentation de chacune, lue le 15/11/2026 :

Deux particularités : Qdrant préfère un parcours complet sous un seuil de taille (full_scan_threshold, 10 000 kilooctets par défaut) ; OpenSearch indique que pour les index créés en version 2.11 ou avant, le moteur Lucene utilisait ef_construction = 512.

Ce que coûte un index HNSW

La documentation de pgvector résume le compromis : HNSW offre un meilleur rapport vitesse-rappel que l'index IVFFlat, mais sa construction est plus lente et il consomme plus de mémoire. Il n'a pas d'étape d'entraînement, donc il se crée même sur une table vide. Deux conséquences pratiques :

• Prévoyez la mémoire. Dans pgvector, la construction est nettement plus rapide quand le graphe tient dans maintenance_work_mem.
• Les résultats changent après sa création. La recherche devient approximative ; la documentation recommande de surveiller le rappel en comparant avec une recherche exacte.

Et avec des filtres

Un index HNSW cherche les plus proches voisins, puis la base applique les filtres. Si le filtre est très sélectif, il peut rester trop peu de résultats. Les bases ont chacune leur parade : parcours itératifs dans pgvector depuis la version 0.8.0, index HNSW tenant compte des filtres chez Qdrant, à condition de créer les index de métadonnées avant l'ingestion. Le détail pour PostgreSQL est sur pgvector : HNSW ou IVFFlat.