Comment la recherche HNSW échange-t-elle de la mémoire contre du rappel dans une base de données vectorielle locale ?

HNSW échange de la mémoire contre le rappel en stockant un graphe de voisins navigable, dont la connectivité et l’ampleur de la recherche déterminent la profondeur d’exploration des vecteurs proches par les requêtes.

Une base de données vectorielle locale peut contenir les représentations vectorielles de documents domestiques, de textes OCR, de métadonnées photo, de manuels, de transcriptions et d’enregistrements d’applications. La recherche par force brute compare la requête à chaque vecteur, tandis que HNSW tente d’atteindre le même voisinage utile en parcourant un graphe à plusieurs niveaux. Cette approche est rapide, car la base stocke à l’avance une structure de graphe supplémentaire, et sa précision dépend du niveau de connexion de ce graphe ainsi que du nombre de candidats qu’une requête est autorisée à explorer.

HNSW ajoute un graphe de proximité hiérarchisé autour des vecteurs stockés

Chaque vecteur devient un nœud relié à des voisins sélectionnés. Un petit sous-ensemble de nœuds apparaît également dans les niveaux supérieurs, créant des itinéraires longue distance qui aident la recherche à se diriger rapidement vers la région où se trouvent probablement les vecteurs proches.

Un graphe de proximité à plusieurs niveaux fournit à HNSW des itinéraires grossiers dans les niveaux supérieurs, puis une navigation de plus en plus précise entre les voisins à mesure que l’on se rapproche de la base de la hiérarchie.

Ces arêtes stockées constituent le premier compromis en matière de mémoire. Contrairement à un tableau plat de vecteurs, l’index conserve une topologie qui doit rester disponible pendant le parcours.

La hiérarchie réduit la quantité de la collection parcourue par une requête normale, mais l’approche reste approximative : le chemin peut manquer un véritable voisin lorsque le graphe ou le budget de recherche ne permet pas d’emprunter le bon itinéraire.

Le paramètre M utilise davantage de mémoire pour créer plus d’itinéraires

Les implémentations HNSW exposent un paramètre de connectivité généralement appelé `m` ou `M`. L’augmenter permet aux nœuds de conserver davantage de liens vers leurs voisins, ce qui crée des chemins alternatifs dans les zones denses ou irrégulières de l’espace vectoriel.

Une valeur m plus élevée dans HNSW stocke davantage de connexions entre voisins pour chaque nœud, ce qui améliore généralement les possibilités de navigation et le rappel, tout en augmentant la mémoire du graphe et le travail de construction.

L’augmentation de la mémoire provient des arêtes du graphe et des structures d’index associées, et non d’un agrandissement des valeurs originales des représentations vectorielles. Avec des millions de vecteurs, quelques liens supplémentaires par nœud s’accumulent dans toute la collection. Réduire `m` peut rendre un serveur domestique limité en mémoire plus confortable, mais un graphe trop clairsemé offre moins de moyens de contourner les impasses locales et peut réduire le rappel.

La construction avec Ef utilise davantage de travail pour améliorer le graphe lui-même

La qualité du graphe est également façonnée lors de l’insertion des vecteurs. `ef_construct` contrôle l’ampleur du voisinage de candidats examiné par le générateur avant de sélectionner les liens d’un nouveau nœud.

Utiliser efConstruction comme levier de qualité de construction permet à la construction de l’index d’examiner un voisinage de candidats plus large avant de choisir les arêtes, ce qui améliore la qualité du graphe au prix d’un travail accru lors de la construction.

Ce coût est payé lors de la construction ou de la reconstruction, et non à chaque requête. Pour un corpus privé qui évolue lentement, consacrer davantage de temps à la construction peut être acceptable si cela améliore la qualité de la recherche sans augmenter durablement la précision des vecteurs.

Toutefois, l’effort de construction ne peut pas compenser indéfiniment un graphe largement sous-dimensionné. `m`, l’ampleur de la construction, la distribution des données et l’historique des insertions interagissent.

Featured

ZimaCube 2 NAS personnel Cloud à domicile

ZimaCube2

$799.00 - $2,499.00

Buy Now

Ef Search utilise davantage de travail par requête plutôt que de la mémoire permanente du graphe

Au moment de la requête, HNSW maintient une frontière de candidats et explore les nœuds prometteurs du graphe. Un paramètre généralement appelé `ef`, `ef_search` ou `hnsw_ef` contrôle le nombre de candidats conservés pendant ce parcours.

Augmenter l’ampleur de l’exploration de la requête permet à une requête d’examiner davantage de candidats du graphe avant de sélectionner les résultats les plus proches, ce qui augmente généralement le rappel tout en accroissant la latence de la requête.

Contrairement à `m`, une valeur `ef` plus élevée pour une requête n’oblige pas chaque nœud stocké à conserver davantage d’arêtes permanentes. Son coût principal se manifeste par des calculs de distance supplémentaires, davantage d’accès mémoire et une latence accrue pour cette requête. Cette distinction fournit deux réglages différents sur un serveur domestique : la connectivité du graphe détermine l’empreinte persistante de l’index, tandis que l’ampleur de la requête peut être augmentée uniquement pour les recherches difficiles qui justifient ce travail supplémentaire.

La compression des vecteurs ne supprime pas le coût du graphe HNSW

La quantification des représentations vectorielles peut réduire considérablement la taille de chaque vecteur stocké, mais HNSW a toujours besoin de ses relations entre voisins. L’index total contient donc au moins deux grands composants mémoire : les données vectorielles et la topologie du graphe.

Même lorsque les valeurs vectorielles sont compressées, la quantification ne réduit pas les liens du graphe ; HNSW a toujours besoin de la topologie, des identifiants et des structures associées autour de ces vecteurs.

C’est pourquoi un taux de compression des vecteurs de 4× ou plus ne produit pas automatiquement une réduction équivalente de la mémoire globale de HNSW. Les arêtes du graphe, les identifiants des objets, les métadonnées, la surcharge de l’allocateur et les caches restent présents.

Sur un petit serveur domestique, mesurez l’ensemble de la mémoire résidente occupée par la collection au lieu d’estimer la RAM à partir des seules dimensions des vecteurs.

Le rappel doit être mesuré par rapport aux voisins exacts, et non déduit des réglages

Des valeurs `m` et `ef` plus élevées orientent généralement le système vers un meilleur rappel, mais aucune valeur de paramètre ne garantit une précision fixe pour tous les modèles de représentations vectorielles, toutes les tailles de corpus ou toutes les distributions de documents.

Le coût de la mémoire des graphes HNSW dans plusieurs collections RAG s’accumule lorsque plusieurs collections privées restent actives aux côtés de modèles locaux, d’index de métadonnées, de caches et d’autres services de serveur domestique.

Créez un ensemble représentatif de requêtes et comparez les résultats approximatifs à une analyse exacte sur un échantillon de taille gérable. Suivez le rappel, la latence, la RAM de l’index, le temps de construction et l’effet des requêtes simultanées. Le compromis pratique de HNSW n’est donc pas « davantage de RAM signifie toujours une meilleure recherche ». Il consiste à choisir une connectivité du graphe et une ampleur d’exploration suffisantes pour atteindre le rappel mesuré souhaité, sans évincer le reste de la pile d’IA domestique.