HNSW Explorer: “Small World” gerarchico navigabile, visualizzato

Osserva il percorso di una ricerca attraverso il grafico a strati — dallo strato superiore rado (autostrade) fino allo strato inferiore denso (strade locali). Trascina il punto di query sullo Strato 0 e regola M / ef per osservare come cambia il grafico.

Numero massimo di vicini per nodo

ef8

Pool di candidati di livello 0

Velocità450ms

Per ogni fase

Passo corrente

14 / 14

Ricerca completata. Top-3: [3, 10, 4].

Statistiche di ricerca

Visitato

17 / 30

Livelli

Voce

Nodo 0

Top-3

[3, 10, 4]

Distribuzione dei livelli

Come funziona " HNSW "

Grafo a livelli: a ogni nodo viene assegnato in modo casuale un livello massimo utilizzando una distribuzione esponenziale. La maggior parte dei nodi si trova solo al Livello 0; pochissimi raggiungono il livello più alto.
All’interno di ogni strato: ogni nodo si collega ai suoi vicini più prossimi M. Gli strati superiori sono sparsi (pochi nodi, spigoli lunghi = “autostrade”). Lo strato 0 è denso (tutti i nodi, spigoli corti = “strade locali”).
La ricerca inizia dall’alto: partendo da un punto di ingresso fisso, procedere in modo avido verso il vicino più prossimo alla query, ripetendo l’operazione finché non si ottengono miglioramenti.
Abbassare di un livello e ripetere: la posizione del livello precedente diventa il punto di partenza del percorso del livello successivo. Ogni abbassamento affina il risultato con bordi più dettagliati.
Livello 0 con " ef": al livello più basso, invece di fermarsi al primo minimo locale, " HNSW " mantiene un insieme dei ef migliori candidati e ne espande i vicinati. Più ampio ef → maggiore precisione ma minore velocità.

Perché è veloce: i livelli superiori agiscono come un indice sull’indice — si coprono enormi distanze in pochi salti, per poi ingrandire. Per N punti, la ricerca visita circa O(log N) nodi invece di N.

Che cos’è “ HNSW ”?

HNSW (Hierarchical Navigable Small World) è un algoritmo approssimativo del vicino più prossimo basato su grafi. Organizza i vettori in una pila di grafi navigabili di tipo “small world”: strati superiori sparsi con archi a lungo raggio per il routing grossolano e uno strato inferiore denso con archi corti per il percorso finale a grana fine. Una ricerca salta avidamente verso la query su ogni strato, per poi scendere — visitando approssimativamente O(log N) nodi invece di scansionarli tutti N.

HNSW è l’indice vettoriale in memoria più diffuso e l’indice grafico predefinito in Milvus. Milvus offre inoltre HNSW_SQ e HNSW_PQ varianti che quantizzano i vettori memorizzati per ridurre l’utilizzo di memoria a un costo minimo in termini di recall.

HNSW parametri in Milvus

M (tempo di costruzione): il numero massimo di spigoli per nodo, la stessa manopola del cursore sopra. I valori tipici sono compresi tra 8 e 64. Un valore di M più alto migliora il recall e la connettività del grafo, ma aumenta linearmente l’utilizzo di memoria e rallenta la costruzione.
efConstruction (tempo di costruzione): la dimensione del pool di candidati utilizzata durante l’inserimento dei nodi. Valori più elevati consentono di costruire un grafo di qualità migliore (maggiore recall ottenibile) a costo di una costruzione dell’indice più lenta. I valori tipici sono compresi tra 100 e 500.
ef / ef_search (tempo di query): il pool di candidati mantenuto durante il percorso Layer-0 — la principale manopola di recall/latenza in fase di ricerca. Deve essere almeno pari al vostro top-K. Aumentatelo fino a quando il recall non raggiunge un plateau; la latenza cresce in modo approssimativamente lineare con esso.

HNSW vs IVF vs DiskANN

HNSW in genere offre la migliore latenza di query con un recall elevato per la ricerca in memoria — ecco perché è la scelta predefinita quando il set di dati (più l’overhead del grafo) rientra in RAM. I suoi costi sono la memoria e il tempo di costruzione: il grafo aggiunge un overhead notevole per ogni vettore e gli inserimenti sono più lenti rispetto all’assegnazione k-means di IVF. Scegliete IVF quando avete bisogno di creazioni di indici veloci o di una quantizzazione aggressiva, e DiskANN quando il set di dati è troppo grande per RAM ma avete comunque bisogno di un recall elevato.

Domande frequenti

Cosa controlla il parametro M in HNSW?

M limita il numero di spigoli che ogni nodo conserva per ogni strato. Un valore maggiore di M rende il grafo meglio connesso — con un recall più elevato e un instradamento più robusto — ma la memoria cresce linearmente con M e la creazione degli indici rallenta. Valori compresi tra 8 e 64 coprono la maggior parte dei carichi di lavoro; 16–32 è un punto di equilibrio comune.

Qual è la differenza tra ef e efConstruction?

Entrambe sono dimensioni del pool di candidati, applicate in momenti diversi. La " efConstruction " viene utilizzata durante la creazione dell’indice: determina con quanta accuratezza ogni nodo inserito cerchi i vicini, controllando così la qualità del grafo. La " ef " (ef_search) viene utilizzata al momento della query: controlla l’ampiezza della ricerca a livello Layer-0, bilanciando la latenza con il recall per ogni query.

Quanta memoria richiede un indice “ HNSW ”?

Approssimativamente i vettori grezzi più il grafo: circa d × 4 byte per vettore per i dati float32, più dell’ordine di M × 2 × 8 byte di spigoli per nodo. Per le implementazioni con memoria limitata, Milvus offre HNSW_SQ e HNSW_PQ, che quantizzano i vettori memorizzati, oppure DiskANN, che sposta i vettori completi su SSD.

Quando devo usare « HNSW » invece di « IVF »?

Utilizzare " HNSW " quando la priorità è la latenza della query con un recall elevato e l’indice rientra nella memoria — di solito è la soluzione vincente. Preferire " IVF " quando si ricostruiscono frequentemente gli indici (creazione molto più veloce), oppure quando combinato con la quantizzazione " SQ8" / "PQ " per adattarsi a un budget di memoria limitato.

Approfondisci: leggi la documentazione "HNSW " per i parametri esatti dell’indice, oppure consulta " Index Explained " per la guida completa alle decisioni.