Recherche vectorielle sans force brute : comment fonctionnent IVF et HNSW

Recherche Vectorielle Sans Force Brute : Comment Fonctionnent IVF et HNSW

Lorsqu'une base de données vectorielle contient des millions d'embeddings, rechercher des vecteurs similaires par force brute devient impossible. Deux algorithmes — IVF et HNSW — résolvent cette tâche par recherche approximative, trouvant des réponses en millisecondes au lieu de minutes. Un nouvel article détaillé sur Habr décompose les deux approches de la théorie mathématique à l'implémentation en Python.

Pourquoi la Recherche Exacte Ne Fonctionne Pas

En faibles dimensions (2D, 3D), vous pouvez construire des index spatiaux — arbres k-d, arbres R. Ils utilisent la géométrie : si une requête est loin d'une partie de l'espace, elle peut être exclue de la recherche sans perdre de résultats. Mais en hautes dimensions (768D pour BERT, 3072D pour GPT-4 Turbo), cette idée s'effondre. Les distances deviennent non-locales — presque tous les points sont à presque la même distance les uns des autres. Ce phénomène s'appelle la malédiction de la dimensionnalité. Les index traditionnels perdent en efficacité, cessent de réduire l'espace de recherche, et nous revenons à la force brute — comparer la requête avec tous les millions de vecteurs dans la base de données.

IVF : Le Clustering Vient à la Rescousse

IVF (Inverted File Index) résout la tâche par clustering préalable. L'algorithme utilise k-means classique pour diviser l'espace en "seau"-clusters conditionnels. L'intuition est simple : si les vecteurs sont proches dans l'espace, ils doivent être dans le même cluster, et lors de la recherche, nous n'avons besoin de vérifier que quelques clusters pertinents, pas toute la base de données.

Le processus fonctionne en deux étapes. Lors de l'indexation, chaque vecteur de la base de données est assigné à son cluster le plus proche (son centroïde). Lors de la recherche, le système trouve d'abord K clusters les plus proches de la requête par recherche rapide, puis cherche les correspondances exactes uniquement à l'intérieur d'eux.

Cela réduit considérablement le nombre de comparaisons — au lieu de millions de comparaisons, nous n'avons besoin que de quelques milliers.

• Première étape : k-means divise l'espace en centaines ou milliers de clusters
• Deuxième étape : chaque vecteur de la base de données est indexé dans son cluster (l'ID du centroïde est sauvegardé)
• Lors de la recherche : trouver K clusters les plus proches, puis recherche complète uniquement à l'intérieur d'eux

IVF se met à l'échelle bien pour des milliards de vecteurs et nécessite relativement peu de mémoire. Habr présente l'implémentation en Python avec des exemples de code concrets et des métriques de performance.

HNSW : Petit Monde Navigable Hiérarchique

HNSW (Hierarchical Navigable Small World) utilise une approche complètement différente — construisant un graphe de voisinage au lieu de clusters. Chaque vecteur devient un nœud du graphe, les arêtes connectent les vecteurs voisins (proches). Le graphe est construit hiérarchiquement : aux niveaux inférieurs, il y a un voisinage local dense de chaque vecteur, aux niveaux supérieurs, il y a des connexions clairsemées à longue distance pour une descente approximative globale rapide.

Lors de la recherche, l'algorithme commence à partir d'un point d'entrée au niveau supérieur et descend à travers la hiérarchie, en sélectionnant à chaque étape des voisins qui sont plus proches de la requête cible. C'est comme naviguer dans une grande ville : d'abord vous voyagez sur les autoroutes principales, puis vous passez à des rues locales jusqu'à ce que vous trouviez l'adresse que vous recherchez.

« HNSW fonctionne comme un navigateur dans une ville inconnue : vous commencez par les autoroutes principales, puis vous descendez aux rues locales », expliquent les auteurs de l'article sur

Habr.

En pratique, HNSW est généralement plus rapide que IVF pour la recherche à faible latence, mais nécessite plus de mémoire pour stocker la structure du graphe et les connexions entre les nœuds.

Ce Que Cela Signifie

Les deux algorithmes sont utilisés dans les bases de données vectorielles modernes : Pinecone, Weaviate, Qdrant, Milvus. Pour les applications LLM — systèmes RAG, recherche de documents, recommandations sémantiques, chatbots intelligents — le choix de l'algorithme de recherche affecte directement la vitesse de réponse et l'expérience utilisateur. IVF est préférable pour les énormes bases de données avec mémoire limitée, HNSW offre un avantage quand une latence minimale est requise et quand vous travaillez avec des ensembles de données plus compacts.