HNSW: la ricerca vettoriale come passeggiata su un grafo

Perché collegare ogni vettore ai suoi vicini trasforma la ricerca del più prossimo in una camminata greedy, e perché impilare quel grafo su più livelli — radi in cima, densi in basso — è la mossa che mette HNSW sulla frontiera recall-latenza.

Perché questo capitolo

Il capitolo precedente, Approximate nearest neighbor: il problema, ha posto la domanda e ne ha rimandato le risposte. La domanda: trovare i vettori più vicini a una query in un dataset di milioni o miliardi di embedding, senza confrontarli tutti. Le risposte sono tre famiglie di metodi — a grafo, a partizionamento e quantizzazione, a hashing. Questo capitolo apre la prima famiglia, quella a grafo, ed entra nel suo esponente più usato: HNSW.

C’è un motivo pratico per cominciare da qui. HNSW non è solo uno dei metodi: è quello che, alla scala in cui i vettori stanno comodi nella RAM, sta più spesso sulla frontiera di Pareto recall-latenza. È anche, per ragioni quasi storiche, l’indice di default di gran parte dei vector database — Qdrant, Weaviate, Milvus, pgvector lo usano senza che chi li interroga debba saperlo. Quando un sistema RAG espone una manopola chiamata ef_search, sta esponendo un parametro di HNSW. Capire HNSW significa capire cosa fa davvero un vector database quando lo si interroga, e perché le sue manopole controllano proprio il triangolo recall-latenza-memoria.

L’altro motivo è didattico. HNSW è una struttura elegante costruita assemblando idee semplici, ciascuna delle quali ha un capitolo proprio nella wiki: un grafo, una ricerca greedy, una coda di priorità, un livello casuale estratto da una distribuzione. Vista come somma di quelle parti, smette di essere un acronimo opaco e diventa una macchina trasparente, leggibile pezzo per pezzo. È quello che questo capitolo prova a fare.

Contesto

HNSW sta per Hierarchical Navigable Small World. Lo introducono Yury Malkov e Dmitry Yashunin, due ricercatori russi attivi sulla ricerca di similarità, in un paper depositato su arXiv nel marzo 2016 (arXiv:1603.09320) e poi pubblicato nella versione peer-reviewed su IEEE Transactions on Pattern Analysis and Machine Intelligence nel 2018. Il titolo per esteso — Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs — contiene già le tre parole da decodificare.

Small world è un concetto che viene dalla teoria delle reti. Una rete “small world” è una rete in cui due nodi qualsiasi sono collegati da un cammino corto — pochi passi — anche se la rete è enorme. È l’idea dei “sei gradi di separazione” tra le persone: il pianeta ha miliardi di abitanti, ma una catena di conoscenti che collega due persone a caso è sorprendentemente breve. La wiki tratta queste reti nel capitolo reti-complesse (in preparazione). Navigable aggiunge una condizione più forte: non solo esiste un cammino corto, ma lo si può trovare con una regola locale e greedy, senza vista d’insieme. Hierarchical è ciò che HNSW aggiunge ai suoi predecessori, e sarà il cuore del capitolo.

La distinzione tra “small world” e “navigable small world” non è pedanteria. Negli anni Sessanta lo psicologo statunitense Stanley Milgram aveva mostrato sperimentalmente che catene corte di conoscenti esistono — l’esperimento dei “sei gradi”. Ma esistere non basta: nell’esperimento di Milgram le persone trovavano davvero quelle catene, inoltrando una lettera al conoscente che sembrava più vicino al destinatario, senza conoscere la rete globale. Negli anni Duemila Jon Kleinberg, informatico statunitense, ha dimostrato che questa “navigabilità” — la possibilità di trovare il cammino corto con sola informazione locale — richiede una struttura particolare degli archi lunghi, e non emerge in qualsiasi rete small world. HNSW è, in fondo, un modo di costruire deliberatamente una rete che sia non solo small world ma navigabile, così che la ricerca greedy locale funzioni.

Quei predecessori hanno un nome: NSW, Navigable Small World. Lo stesso Malkov, con altri coautori, lo aveva proposto in un paper del 2014 su Information Systems (Approximate nearest neighbor algorithm based on navigable small world graphs). NSW è un grafo di prossimità piatto — un solo livello — in cui ogni vettore è collegato ad alcuni dei suoi vicini, e la ricerca è una passeggiata greedy. Funziona, ma ha un limite preciso che vedremo: la sua complessità di ricerca è polilogaritmica, non logaritmica. HNSW del 2016 è la correzione di quel limite. La relazione tra NSW e HNSW è una filiazione documentata, non un’analogia: stesso autore principale, stessa idea di base, miglioramento esplicito e dichiarato.

L’idea di cercare i vicini camminando su un grafo, va detto, è più vecchia di NSW. I grafi di prossimità — strutture in cui i punti vicini nello spazio sono collegati da archi — sono studiati in geometria computazionale da decenni: il grafo di Delaunay, per esempio, ha la proprietà teorica che una ricerca greedy verso un punto qualsiasi trova sempre il vicino più prossimo. Il guaio del grafo di Delaunay è che in alta dimensione il numero di archi per nodo esplode, e costruirlo diventa impraticabile. La storia dei metodi a grafo per l’ANN è in gran parte la ricerca di un’approssimazione del grafo di Delaunay: abbastanza archi per restare navigabili, abbastanza pochi da essere costruibili e leggeri. NSW e HNSW stanno dentro questa storia. L’euristica di selezione dei vicini di HNSW, che vedremo, è proprio un modo economico di tenere il grafo “abbastanza simile a Delaunay” senza calcolarlo.

Vale la pena collocare HNSW nel tempo. Il 2016 è prima dell’esplosione degli LLM: HNSW nasce per la ricerca di similarità su descrittori di immagini e su dataset vettoriali generici, non per RAG. È un altro caso, come si diceva in ann-intro, di tecnologia matura che aspetta il suo caso d’uso di massa. Quel caso d’uso arriva dopo il 2020, quando produrre embedding di buona qualità per testo arbitrario diventa facile, e l’intera infrastruttura della ricerca vettoriale — HNSW incluso — trova un’applicazione enorme. L’algoritmo è del 2016; la sua centralità è del 2023.

L’intuizione

Prima di qualunque pseudocodice, tre angoli per entrare nella struttura.

Angolo 1 — la mappa stradale a più zoom

Per andare da una città a un indirizzo preciso in un’altra città, nessuno parte dalla mappa di quartiere. Si parte dalla mappa autostradale: pochi nodi — i caselli, gli svincoli — collegati da archi lunghi che coprono mezzo paese in un salto. Si arriva nella regione giusta. Poi si scende alla mappa delle strade provinciali: più nodi, archi più corti, granularità più fine. Infine alla mappa delle vie cittadine, per trovare l’isolato esatto.

Ogni livello di zoom ha la sua scala. Il livello alto ti porta nella zona giusta in pochissimi salti, ma non saprebbe dirti il numero civico. Il livello basso conosce ogni via, ma percorrerlo da un capo all’altro del paese richiederebbe migliaia di passi. La furbizia sta nell’usarli in sequenza: salti lunghi prima, salti corti poi.

HNSW è esattamente questa idea applicata a uno spazio di vettori. Il grafo è impilato su più strati. Lo strato in cima è rado: contiene pochi nodi, ognuno con archi che coprono grandi distanze nello spazio vettoriale. La ricerca lassù fa salti lunghi e arriva in fretta nella regione giusta. Poi scende di strato: più nodi, archi più corti, rifinitura più fine. All’ultimo strato — lo strato 0, che contiene tutti i vettori del dataset — si fa la ricerca locale precisa. Il guadagno è lo stesso del viaggio: invece di attraversare un grafo piatto con migliaia di hop corti, si fanno pochi hop lunghi in alto e pochi hop corti in basso.

Angolo 2 — lo skip list portato in mille dimensioni

Il secondo angolo è informatico, e svela da dove viene la struttura. Lo skip list è una struttura dati classica, proposta da William Pugh nel 1990, per cercare in una lista ordinata in tempo logaritmico atteso. Funziona impilando più liste collegate. La lista in basso contiene tutti gli elementi, in ordine. Ogni lista superiore ne contiene un sottoinsieme casuale, saltando gli intermedi: di fatto un’autostrada di scorciatoie sopra la strada locale.

Si cerca dall’alto. Si avanza sulla lista rada finché il prossimo elemento non supererebbe il target; a quel punto si scende di un livello e si riparte. I livelli alti danno salti lunghi, i livelli bassi danno la precisione. Il livello di ogni elemento si decide a caso: si lancia una moneta, e finché esce testa l’elemento sale di un livello. Così circa metà degli elementi sta a livello 1, un quarto a livello 2, un ottavo a livello 3, e così via.

HNSW è lo skip list generalizzato da una dimensione a uno spazio vettoriale a centinaia o migliaia di dimensioni. Lo skip list lavora su un ordine totale: gli elementi sono allineati su una retta, c’è un “prima” e un “dopo”. Uno spazio di embedding non ha ordine totale — esistono solo distanze tra punti, non un allineamento. HNSW sostituisce la lista collegata di ogni livello con un grafo di prossimità: invece di “il prossimo elemento”, “i nodi vicini nello spazio”. E sostituisce “avanza finché non superi il target” con la discesa greedy verso la query. Ma l’ossatura è la stessa: livelli impilati, livello casuale per elemento, ricerca dall’alto verso il basso.

Questa parentela non è una metafora che si propone qui per comodità didattica. È filiazione esplicita: il paper di Malkov e Yashunin dichiara la “similarity of the algorithm to the skip list structure” e ne fa un argomento di design — la somiglianza con lo skip list, scrivono, rende immediata un’implementazione distribuita bilanciata. Gli autori si sono ispirati allo skip list, e lo scrivono. Tenere a mente lo skip list mentre si legge il resto del capitolo è il modo più rapido di non perdersi.

Conviene però segnare anche dove la parentela si ferma, per non spingerla troppo. Lo skip list garantisce la ricerca esatta: in una lista ordinata trova sempre l’elemento giusto, perché l’ordine totale non lascia ambiguità su dove andare. HNSW, lavorando su uno spazio senza ordine totale, perde questa garanzia: la sua ricerca è greedy e approssimata, come ha mostrato l’angolo 3. Lo skip list dà la struttura — i livelli, l’estrazione casuale, la discesa dall’alto — ma non la garanzia di correttezza. È un caso pulito di filiazione che eredita il meccanismo senza ereditare le proprietà: HNSW prende l’ossatura dello skip list e la innesta su un problema più difficile, dove quell’ossatura compra velocità ma non più certezza.

Angolo 3 — lo scalatore che sale sempre verso l’alto

Il terzo angolo isola il motore della ricerca dentro un singolo strato, prima che la gerarchia entri in gioco. Immagina uno scalatore che vuole raggiungere la vetta di una collina, di notte, con una torcia che illumina solo i pochi metri intorno a sé. Non ha una mappa. La sua regola è semplice: guarda i punti raggiungibili da dove si trova, va su quello più in alto, ripete. Si ferma quando nessun punto vicino è più alto del suo. È una salita greedy: a ogni passo la mossa localmente migliore, senza visione d’insieme.

La ricerca dentro uno strato di HNSW è questa salita, con la “quota” sostituita dalla vicinanza alla query — più vicino significa “più in alto” — e i “punti raggiungibili” che sono i vicini di un nodo nel grafo. Si parte da un nodo, si guarda chi è collegato a esso, ci si sposta sul vicino più vicino alla query, si ripete. Ci si ferma quando nessun vicino migliora.

Questo angolo rende visibile, da subito, il limite del metodo. Lo scalatore può fermarsi su una collina secondaria: una cima locale, circondata da terreno più basso, mentre la vetta vera sta altrove, oltre una valle che la regola greedy non gli fa attraversare. È l’ottimo locale. Tradotto in HNSW: la ricerca può arrivare a un nodo i cui vicini sono tutti più lontani dalla query, fermarsi, e mancare un nodo ancora più vicino che si trova in un’altra zona del grafo. È la ragione per cui HNSW è approssimato. Le contromisure le vedremo — tenere viva una frontiera larga, non un solo candidato; e la gerarchia stessa, che sceglie un punto di partenza così buono da rendere raro l’intrappolamento. Ma il rischio non si azzera mai, ed è sano vederlo fin dall’intuizione.

La meccanica

La struttura: strati, nodi, entry point

Il grafo di HNSW ha più strati, numerati da 0 verso l’alto. Lo strato 0, in basso, contiene tutti i nodi del dataset. Ogni strato superiore ne contiene un sottoinsieme sempre più piccolo. Ogni nodo ha un livello massimo $l$ , deciso a caso quando il nodo viene inserito: un nodo con livello massimo $3$ esiste negli strati $0$ , $1$ , $2$ , $3$ ; un nodo con livello massimo $0$ esiste solo nello strato base. La grande maggioranza dei nodi ha livello $0$ ; pochissimi arrivano in cima.

C’è un solo entry point: il nodo che si trova nello strato più alto attualmente esistente. Ogni ricerca, e ogni inserimento, parte da lì. L’entry point non è fisso: cambia man mano che si costruisce l’indice. Quando viene inserito un nodo con un livello più alto di qualunque altro, quel nodo diventa il nuovo entry point e il numero di strati cresce. È un evento raro — la distribuzione esponenziale dei livelli lo rende tale — ed è il modo in cui la gerarchia si auto-organizza senza che nessuno decida a priori quanti strati servono. Il numero di strati emerge dai dati e dal caso, non da un parametro.

Dentro ogni strato, i nodi sono collegati da archi a una parte dei loro vicini più prossimi in quello strato. Gli archi sono bidirezionali. Il grafo di uno strato alto, avendo pochi nodi sparsi nello spazio, ha per forza archi che coprono grandi distanze: ecco i “salti lunghi”. Il grafo dello strato 0, fitto di nodi, ha archi corti: la rifinitura. Lo stesso nodo, presente in più strati, ha vicini diversi in ciascuno: i suoi vicini nello strato $2$ sono i nodi vicini tra i pochi che esistono lassù, i suoi vicini nello strato $0$ sono i nodi vicini tra i milioni che popolano la base. Un nodo non ha “un vicinato”, ne ha uno per strato.

L’assegnazione del livello: la distribuzione esponenziale

Quando si inserisce un nuovo nodo, la prima cosa è estrarre il suo livello massimo $l$ . La formula è:

$l = \lfloor -\ln(U) \cdot m_L \rfloor$

dove $U$ è un numero casuale estratto uniformemente nell’intervallo $(0, 1]$ , $\ln$ è il logaritmo naturale, e $\lfloor \cdot \rfloor$ è l’arrotondamento all’intero inferiore. $m_L$ è un fattore di normalizzazione, un parametro fissato una volta.

In parole povere, questa formula produce un livello che è quasi sempre $0$ , qualche volta $1$ , raramente $2$ , e così via con probabilità che cala esponenzialmente. È la versione continua del “lancia la moneta finché esce testa” dello skip list. Il termine $-\ln(U)$ ha una proprietà nota: se $U$ è uniforme, $-\ln(U)$ segue una distribuzione esponenziale. Moltiplicarlo per $m_L$ e arrotondare in basso dà una distribuzione geometrica sui livelli interi.

Il valore di $m_L$ decide quanto è ripida la discesa. La scelta consigliata dal paper è:

$m_L = \frac{1}{\ln(M)}$

dove $M$ è il parametro che vedremo tra poco — il numero di archi per nodo. Con questa scelta, in media una frazione $1/M$ dei nodi di uno strato sale allo strato superiore. È, di nuovo, lo skip list: ma con base $M$ invece che base $2$ . Se $M = 16$ , circa un nodo su 16 sale di strato; un nodo su 256 sale di due strati; e così via. Il numero totale di strati cresce come $\log_M(N)$ — logaritmico nella dimensione del dataset.

Una nota sul caso limite. Se $m_L = 0$ , la formula dà sempre $l = 0$ : tutti i nodi finiscono solo nello strato base, e HNSW collassa esattamente in NSW, il grafo piatto. La gerarchia è interamente codificata in quel parametro. Aumentare troppo $m_L$ , all’opposto, crea molti strati con molto overlap, e la ricerca paga discese inutili. Il valore $1/\ln(M)$ è il compromesso che il paper trova ottimo empiricamente.

C’è una ragione per cui il livello si estrae a caso invece di calcolarlo. Si potrebbe pensare a un’assegnazione “intelligente” — mettere agli strati alti i nodi più centrali, o più rappresentativi. Ma una scelta del genere richiederebbe una visione globale del dataset, costosa da mantenere mentre i nodi arrivano uno alla volta. L’estrazione casuale, invece, è locale e immediata: ogni nodo decide il proprio livello senza sapere nulla degli altri. È lo stesso motivo per cui lo skip list usa una moneta e non un’analisi della lista. La casualità qui non è una rinuncia alla qualità — è ciò che rende la struttura costruibile in modo incrementale e, come notava il paper, distribuibile su più macchine senza coordinamento.

L’inserimento

Costruire l’indice significa inserire i nodi uno alla volta. Ecco l’inserimento di un nodo $q$ in pseudocodice:

def insert(q, M, ef_construction, m_L):
    l = floor(-ln(uniform(0, 1)) * m_L)   # livello del nuovo nodo
    ep = entry_point                       # nodo dello strato superiore

    # FASE 1: discesa rapida dagli strati sopra l, con ef = 1
    for lc in range(top_layer, l, -1):
        W = search_layer(q, ep, ef=1, layer=lc)
        ep = nearest(W, q)

    # FASE 2: dallo strato l fino a 0, ricerca larga e collegamento
    for lc in range(min(top_layer, l), -1, -1):
        W = search_layer(q, ep, ef=ef_construction, layer=lc)
        neighbors = select_neighbors(q, W, M, layer=lc)
        add_bidirectional_edges(q, neighbors, layer=lc)
        for e in neighbors:                # pota chi supera il grado massimo
            if degree(e, lc) > max_degree(lc):
                prune(e, layer=lc)
        ep = W

    if l > top_layer:                      # il nuovo nodo sale sopra tutti
        entry_point = q
        top_layer = l

Riga per riga. Si estrae il livello $l$ del nuovo nodo. Si parte dall’entry point, in cima. Fase 1: per tutti gli strati che stanno sopra $l$ , si fa solo una discesa greedy stretta — ef=1, un solo candidato vivo per volta — il cui unico scopo è arrivare a un buon punto di partenza per lo strato dove il nodo dovrà davvero collegarsi. In questi strati il nodo non esisterà, quindi non c’è niente da collegare: si attraversa e basta. Fase 2: dallo strato $l$ fino allo strato $0$ , si fa una ricerca larga — ef=ef_construction — per raccogliere molti candidati, se ne scelgono $M$ come vicini, e si creano archi bidirezionali tra $q$ e quei vicini.

L’asimmetria tra le due fasi vale la pena di essere notata, perché è la stessa che governa la query. In entrambe le fasi si usa la stessa funzione search_layer; cambia solo il parametro ef. Nella fase 1, ef=1: la discesa è un puro spostamento, veloce, il cui unico prodotto è un buon punto di partenza. Nella fase 2, ef=ef_construction: la ricerca è larga, perché qui si decide la qualità degli archi del nuovo nodo, e archi scelti male impoveriscono il grafo in modo permanente. È lo stesso schema della ricerca-query: discesa stretta sopra, ricerca larga dove conta. Capito una volta, vale per entrambe le procedure — l’inserimento è una query che, arrivata a destinazione, invece di restituire risultati crea collegamenti.

C’è un altro dettaglio che conta: gli archi bidirezionali. Quando $q$ si collega a un vicino $e$ , anche $e$ acquista un arco verso $q$ . Ma $e$ potrebbe già avere il suo numero massimo di archi. In quel caso lo si pota: si riselezionano i suoi $M$ archi migliori tra quelli vecchi e il nuovo, scartando il peggiore. La potatura usa la stessa euristica di selezione dei vicini che vedremo tra un attimo, non un semplice “scarta il più lontano”: questo mantiene la diversità di direzione anche dopo l’inserimento. Il grado massimo non è lo stesso ovunque: per gli strati sopra lo $0$ è $M$ ; per lo strato $0$ è tipicamente $2M$ , perché lo strato base, contenendo tutti i nodi, ha bisogno di più connettività per restare ben navigabile. Infine, se il nuovo nodo ha un livello più alto di qualunque nodo esistente, diventa il nuovo entry point.

La selezione dei vicini: un’euristica, non i più vicini

Il passo select_neighbors merita attenzione, perché la scelta ingenua è una trappola. La scelta ingenua è: tra i candidati raccolti, prendi i $M$ più vicini a $q$ . Sembra ovvio. Funziona male su dati clusterizzati.

Il problema: se $q$ sta dentro un cluster denso, i suoi $M$ vicini più vicini sono tutti dentro lo stesso cluster. Tutti gli archi di $q$ puntano “verso l’interno”. Nessun arco esce dal cluster verso il resto dello spazio. Ripetuto su tutti i nodi, il grafo si frammenta in isole dense scollegate: una ricerca greedy entrata in un cluster non riesce più a uscirne, e resta intrappolata in un ottimo locale.

L’euristica del paper (è l’Algorithm 4) risolve questo. Invece di prendere ciecamente i più vicini, scorre i candidati dal più vicino al più lontano e accetta un candidato $e$ come vicino di $q$ solo se $e$ è più vicino a $q$ che a uno qualsiasi dei vicini già accettati. In altre parole: si rifiuta un candidato che sta “nella stessa direzione” di uno già scelto, preferendogli uno che apre una direzione nuova. Il risultato è un insieme di archi che puntano in direzioni diverse — alcuni dentro il cluster, altri verso l’esterno. Il grafo resta connesso e navigabile anche su dati molto clusterizzati. Questa euristica è una delle ragioni principali per cui HNSW, ad alto recall, batte NSW.

Un esempio concreto chiarisce la regola. Si supponga di inserire $q$ e che i candidati più vicini siano, in ordine di distanza, $e_1, e_2, e_3$ , dove $e_1$ ed $e_2$ stanno entrambi nel cluster a destra di $q$ e $e_3$ in un cluster a sinistra. La selezione ingenua, con $M = 2$ , prenderebbe $e_1$ ed $e_2$ : due archi che vanno nella stessa direzione, nessuno verso sinistra. L’euristica, invece, accetta $e_1$ (primo, sempre accettato); valuta $e_2$ e nota che $e_2$ è più vicino a $e_1$ che a $q$ — sono nello stesso cluster denso — quindi lo rifiuta; valuta $e_3$ e nota che $e_3$ è più vicino a $q$ che a $e_1$ , perché sta da tutt’altra parte, quindi lo accetta. Gli archi finali di $q$ sono $e_1$ ed $e_3$ : uno verso destra, uno verso sinistra. Il nodo $q$ diventa un ponte tra i due cluster invece di un vicolo cieco dentro uno solo. Ripetuto su tutti i nodi, è questo che tiene il grafo intero attraversabile.

Vale la pena notare il legame con il grafo di Delaunay del Contesto: l’euristica è, in piccolo, un modo economico di approssimare la proprietà di Delaunay — avere archi in tutte le direzioni utili — senza pagarne il costo di costruzione. Non è il grafo di Delaunay, ma ne cattura ciò che serve alla navigabilità.

La ricerca

La query è più semplice dell’inserimento, perché non deve collegare nulla. Ecco la ricerca dei $K$ vicini più prossimi:

def search_knn(q, K, ef_search):
    ep = entry_point
    # discesa greedy stretta dagli strati alti
    for lc in range(top_layer, 0, -1):
        W = search_layer(q, ep, ef=1, layer=lc)
        ep = nearest(W, q)
    # ricerca larga nello strato 0
    W = search_layer(q, ep, ef=ef_search, layer=0)
    return k_nearest(W, q, K)

La struttura ricalca il viaggio dell’angolo 1. Negli strati sopra lo $0$ , si fa una discesa greedy stretta con ef=1: un solo candidato vivo, salti rapidi, l’obiettivo è solo arrivare nella regione giusta. Arrivati allo strato $0$ , si allarga la ricerca a ef=ef_search e si fa la rifinitura locale fitta. Alla fine, dai candidati raccolti si tengono i $K$ più vicini.

Il cuore è search_layer, la ricerca dentro un singolo strato:

def search_layer(q, ep, ef, layer):
    visited = {ep}
    candidates = min_heap([(dist(q, ep), ep)])  # frontiera da esplorare
    W = max_heap([(dist(q, ep), ep)])           # i migliori ef finora

    while candidates:
        c = pop_nearest(candidates)             # il candidato migliore
        f = farthest(W)                         # il peggiore tra i top-ef
        if dist(q, c) > dist(q, f):
            break                               # non si migliora oltre
        for e in neighbors(c, layer):
            if e in visited:
                continue
            visited.add(e)
            if dist(q, e) < dist(q, f) or len(W) < ef:
                push(candidates, (dist(q, e), e))
                push(W, (dist(q, e), e))
                if len(W) > ef:
                    pop_farthest(W)
    return W

Riga per riga. Si mantengono due strutture. candidates è la frontiera: i nodi ancora da esplorare, organizzati in un min-heap così che estrarre il più vicino alla query costi poco. W è l’insieme dei migliori ef nodi visti finora, organizzato in un max-heap così che si possa leggere e scartare in fretta il peggiore. Sono due code di priorità, la struttura che restituisce sempre l’elemento estremo: una orientata al minimo, una al massimo.

Il ciclo estrae dalla frontiera il candidato più promettente $c$ . Se $c$ è già più lontano del peggiore tra i migliori ef, ci si ferma: la frontiera è ordinata per vicinanza, quindi tutto ciò che resta è ancora peggio, e non si può migliorare. Altrimenti si guardano i vicini di $c$ nel grafo: ogni vicino non ancora visitato, se è abbastanza buono — più vicino del peggiore in W, oppure W non è ancora pieno — entra sia nella frontiera sia in W. Se W sfora la dimensione ef, si butta via il peggiore.

È la stessa identica passeggiata greedy dello pseudocodice gather_candidates_graph mostrato in ann-intro. HNSW non la cambia: la avvolge nella gerarchia. La discesa dall’alto sceglie un punto di partenza eccellente per lo strato 0; search_layer sullo strato 0 fa il lavoro fine.

Due dettagli di search_layer meritano una sosta, perché sono il punto dove la ricerca smette di essere puramente greedy. Il primo è la frontiera larga. Lo scalatore dell’angolo 3 teneva un solo punto vivo per volta — la salita greedy pura. search_layer con ef maggiore di 1 ne tiene ef: non si sposta sul singolo migliore e basta, mantiene viva una rosa di candidati promettenti e li esplora tutti. È questo che permette di scavalcare le “valli”: se il candidato in testa porta a un ottimo locale, ce ne sono altri ef - 1 in lista da cui ripartire. Più larga la frontiera, più rara la trappola, più alto il recall — e più lavoro. È, in concreto, perché il parametro ef governa il recall.

Il secondo dettaglio è la condizione di arresto. La riga if dist(q, c) > dist(q, f): break dice: se il candidato più promettente rimasto nella frontiera è già più lontano del peggiore tra i migliori ef trovati, fermati. La frontiera è un min-heap ordinato per vicinanza, quindi se il suo primo elemento è scadente, tutti gli altri lo sono ancora di più: continuare non può che peggiorare. Senza questa condizione la ricerca esplorerebbe l’intero grafo, e il guadagno di HNSW svanirebbe. È il taglio che rende la ricerca sublineare: si visita una piccola frazione dei nodi e ci si ferma appena la frazione promettente è esaurita.

I tre parametri

Tutta la meccanica si governa con tre parametri. Vale la pena tenerli separati con cura, perché confonderli è l’errore più comune.

$M$ — il numero di connessioni per nodo. Quanti archi ogni nodo mantiene negli strati. Più alto significa grafo più connesso, quindi più recall — più strade per raggiungere i veri vicini, meno rischio di restare intrappolati in un ottimo locale. Ma più archi significano più memoria, e un build più lento. È l’unico parametro strutturale: decide la forma del grafo e la sua occupazione di memoria, si fissa alla creazione dell’indice, e cambiarlo richiede di ricostruire tutto. Valori tipici stanno tra $8$ e $48$ ; un default frequente è $16$ .

$ef_{construction}$ — l’ampiezza della ricerca durante l’inserimento. Quanti candidati si tengono vivi mentre si cercano i vicini di un nodo da inserire. Più alto significa un grafo di qualità migliore — gli archi scelti sono più vicini all’ottimo — e quindi recall più alto a parità di tutto il resto. Ma il build diventa più lento, perché ogni inserimento fa più calcoli di distanza. Non incide sulla memoria dell’indice finito: è un parametro di processo, non di struttura. Valori tipici tra $100$ e $500$ ; un default frequente è $200$ .

$ef_{search}$ — l’ampiezza della ricerca durante la query. Quanti candidati si tengono vivi durante una ricerca. Più alto significa più recall e query più lenta. È la manopola query-time della frontiera di Pareto: la si gira a runtime, query per query, senza ricostruire niente. È lo stesso ef di cui parlava ann-intro. Deve essere almeno pari a $K$ , il numero di vicini richiesti.

La distinzione che salva tempo: solo $M$ tocca la memoria. $ef_{construction}$ ed $ef_{search}$ sono ampiezze di ricerca, non pezzi di struttura. Alzare $ef_{search}$ non fa crescere l’indice di un byte; cambiarlo non richiede ricostruzioni. $M$ invece è scolpito nella struttura.

La memoria dell’indice si stima così: occupazione dei vettori grezzi, più circa $N \cdot M$ archi, ognuno dei quali costa una manciata di byte (8 byte se gli identificatori dei nodi sono interi a 64 bit, qualcosa di più con overhead). Su un dataset come Sift1M — un milione di vettori a 128 dimensioni — con $M = 32$ l’indice occupa dell’ordine di mezzo gigabyte; spingendo $M$ a valori molto alti l’indice cresce in proporzione. Il punto da fissare: la struttura a grafo aggiunge memoria rispetto ai vettori grezzi. Non è un dettaglio — è il difetto principale di HNSW, e lo riprenderemo.

In pratica, come si tarano i tre parametri? Una procedura che funziona quasi sempre. Si fissa $M$ in base al budget di memoria: più alto è $M$ , più memoria e più recall potenziale, ma oltre $48$ i guadagni si appiattiscono e il costo no — $16$ è un punto di partenza solido, $32$ - $48$ per dati ad alta dimensionalità intrinseca o quando il recall conta molto. Si fissa $ef_{construction}$ abbastanza alto da non strozzare la qualità del grafo: poiché si paga una volta sola, conviene essere generosi — $200$ è un default ragionevole, $400$ se il build offline ha tempo. Questi due si congelano e si costruisce l’indice. Poi, a indice costruito, si cerca $ef_{search}$ : si misura la curva recall-latenza facendo girare un set di query di test a $ef_{search}$ crescente — $64, 128, 256, \dots$ — confrontando i risultati con il brute-force, e si sceglie il valore più basso che raggiunge il recall richiesto dal prodotto. È l’unico parametro che si può tarare dopo, sul comportamento reale, ed è quindi quello su cui concentrare la sperimentazione. Tarare $M$ “per tentativi” è costoso, perché ogni tentativo è una ricostruzione; tarare $ef_{search}$ è economico, perché è solo una variabile di sessione.

Lo scaling logaritmico, e perché NSW non ce la faceva

Resta da chiudere il conto con NSW, il grafo piatto. Perché la gerarchia migliora le cose?

Su un grafo NSW piatto, la ricerca greedy ha una proprietà a metà buona. Il numero di hop — di passi da un nodo all’altro — per arrivare alla risposta scala come $\log(N)$ : buono. Ma c’è un secondo fattore. Lungo il cammino, man mano che ci si avvicina alla query, i nodi che si incontrano hanno un grado sempre più alto — più archi da esaminare a ogni passo. E quel grado medio dei nodi visitati cresce anch’esso come $\log(N)$ . Il costo totale di una query è il numero di hop moltiplicato per il lavoro a ogni hop: $\log(N) \times \log(N)$ , cioè $\log^2(N)$ . È la complessità polilogaritmica che il paper NSW del 2014 riconosce come limite.

HNSW spezza questo prodotto. La discesa attraverso gli strati alti, fatta con ef=1, costa pochi hop su nodi di grado contenuto: porta la ricerca nella regione giusta a costo logaritmico senza il fattore moltiplicativo. La ricerca larga avviene solo nello strato $0$ , ma partendo già vicino alla risposta, quindi tocca pochi nodi. Sotto le ipotesi del paper, la complessità di query scende a $\log(N)$ pulito. La costruzione dell’indice resta $O(N \log N)$ : $N$ inserimenti, ognuno a costo logaritmico.

Conviene essere precisi su cosa significa “sotto le ipotesi del paper”. Il risultato logaritmico non è un teorema dimostrato per ogni dataset possibile: è un’analisi che vale quando i dati hanno una dimensionalità intrinseca contenuta e una distribuzione ragionevole. Su dati patologici — dimensionalità intrinseca altissima, o distribuzioni estreme — anche HNSW degrada, perché degrada la navigabilità del grafo stesso. Il punto solido, e quello che conta in pratica, è il confronto relativo: a parità di dataset, HNSW elimina il fattore $\log(N)$ in più che NSW pagava. È un miglioramento di un fattore logaritmico, misurabile sui benchmark, non una promessa di scaling logaritmico assoluto in ogni condizione.

La gerarchia, in una frase, serve a separare due lavori che NSW faceva insieme e male: coprire grandi distanze (gli strati alti) e rifinire localmente (lo strato 0). Separati, ognuno costa poco.

Due tempi da non confondere: build e query

C’è una distinzione che ann-intro ha già introdotto in generale e che per HNSW conviene rendere concreta: il build e la query sono due momenti separati, con costi separati.

Il build è la costruzione dell’indice: gli $N$ inserimenti, fatti una volta, prima che arrivi qualunque query. È un lavoro pesante — $O(N \log N)$ — e i parametri $M$ ed $ef_{construction}$ lo governano. Alzare $ef_{construction}$ raddoppia tranquillamente il tempo di build per guadagnare qualche punto di recall: accettabile, perché si paga una sola volta. Per un dataset di milioni di vettori il build è questione di minuti, decine di minuti per i casi grandi.

La query è ciò che l’utente percepisce: arriva $q$ , e la latenza che conta è quella. Qui agisce solo $ef_{search}$ . La separazione tra i due tempi spiega un’asimmetria pratica: si può investire molto nel build — è offline, lo si fa di notte — per avere query veloci di giorno. È lo schema “costruisci una volta, interroga milioni di volte”, e HNSW ci sta dentro bene finché il dataset è statico. Quando il dataset cambia in continuazione, la distinzione si incrina: ogni nuovo vettore è un mini-build a runtime, e la cancellazione — lo vedremo — non ha nemmeno un meccanismo pulito. Tenere separati i due tempi è il modo giusto di leggere qualunque benchmark di HNSW: un numero di QPS spettacolare può nascondere un build di ore, o un degrado silenzioso sotto cancellazioni.

Una proprietà comoda: HNSW non sa nulla di metrica

C’è un aspetto di HNSW che lo rende particolarmente flessibile, e che vale la pena rendere esplicito. In tutta la meccanica vista finora — l’inserimento, la ricerca, la selezione dei vicini, la condizione di arresto — l’unica cosa che si fa con i vettori è chiamare una funzione $\text{dist}(a, b)$ . HNSW non guarda mai dentro i vettori, non assume che siano normalizzati, non sfrutta proprietà geometriche specifiche. Tratta la funzione di distanza come una scatola nera.

La conseguenza pratica è grande: lo stesso identico algoritmo funziona con la distanza euclidea $L2$ , con la similarità coseno, con il prodotto interno, e in linea di principio con qualunque misura di dissimilarità ragionevole — la wiki tratta queste metriche in Norme e distanze. Cambiare metrica significa cambiare una riga, la definizione di dist, non l’algoritmo. È per questo che un vector database può offrire HNSW “con metrica coseno” o “con metrica euclidea” come semplice opzione di configurazione. Va detta una cautela: alcune misure non rispettano la disuguaglianza triangolare — il prodotto interno è il caso noto — e su quelle il greedy routing è teoricamente meno solido, anche se in pratica HNSW se la cava bene anche lì. La regola operativa resta quella di ann-intro: usare la metrica con cui il modello di embedding è stato addestrato.

Esempi

Esempio numerico: quanti strati per un miliardo di vettori

Si prenda $M = 16$ , quindi $m_L = 1/\ln(16) \approx 0{,}36$ . In media una frazione $1/M = 1/16$ dei nodi di uno strato sale a quello sopra. Partendo da $N = 10^9$ nodi nello strato $0$ :

strato $1$ : circa $10^9 / 16 \approx 6{,}3 \cdot 10^7$ nodi;
strato $2$ : circa $3{,}9 \cdot 10^6$ ;
strato $3$ : circa $2{,}4 \cdot 10^5$ ;
strato $4$ : circa $1{,}5 \cdot 10^4$ ;
e così via, fino a una manciata di nodi in cima.

Il numero di strati è dell’ordine di $\log_{16}(10^9) \approx 7$ - $8$ . Una query attraversa quei $7$ - $8$ strati, facendo solo pochi hop per strato. Il conto finale è dell’ordine di poche decine, forse un centinaio, di calcoli di distanza per query — contro il miliardo del brute-force. È lo scaling logaritmico messo in numeri: il dataset cresce di mille volte, il costo di query cresce di pochi punti percentuali.

Un secondo conto, sulla memoria, chiarisce il prezzo. Quel miliardo di vettori a $768$ dimensioni in virgola mobile a 32 bit pesa circa $3$ terabyte di soli dati grezzi. La struttura a grafo aggiunge gli archi: con $M = 16$ , ogni nodo ha fino a $2M = 32$ archi nello strato $0$ e fino a $M = 16$ negli strati superiori; sommando su tutti gli strati si arriva a circa $1{,}1 \cdot M$ archi medi per nodo nel conteggio del paper. A $8$ byte per identificatore di nodo, sono dell’ordine di un centinaio di byte di soli archi per vettore: per un miliardo di vettori, dell’ordine di un centinaio di gigabyte in aggiunta ai $3$ terabyte. La struttura non è gratis, e il suo peso scala linearmente con $M$ . È il motivo per cui, più avanti, “HNSW divora memoria” sarà tra i punti deboli.

Esempio: una ricerca tracciata passo passo

Per vedere search_layer in moto, si segua una ricerca con ef = 2 su un piccolo grafo dello strato 0. I nodi siano $A, B, C, D, E$ , e le distanze dalla query $q$ valgano: $\text{dist}(q,A)=9$ , $\text{dist}(q,B)=4$ , $\text{dist}(q,C)=6$ , $\text{dist}(q,D)=2$ , $\text{dist}(q,E)=7$ . Gli archi: $A$ collegato a $B$ e $C$ ; $B$ collegato a $A, C, D$ ; $C$ collegato a $A, B, E$ ; $D$ collegato a $B$ ; $E$ collegato a $C$ . L’entry point sia $A$ .

Passo 0: la frontiera contiene $(9, A)$ , l’insieme dei migliori $W$ contiene $(9, A)$ .

Passo 1: si estrae il candidato più vicino dalla frontiera, $A$ a distanza $9$ . Il peggiore in $W$ è $A$ a $9$ : la condizione di arresto non scatta ( $9$ non è maggiore di $9$ ). Si guardano i vicini di $A$ : $B$ a $4$ ed $C$ a $6$ . Entrambi migliori del peggiore in $W$ (o $W$ non pieno), entrano. Ora $W$ tiene i due migliori: $(4, B)$ e $(6, C)$ — $A$ a $9$ viene scartato perché $W$ non può superare ef = 2. La frontiera contiene $B$ e $C$ .

Passo 2: si estrae $B$ a $4$ . Il peggiore in $W$ è $C$ a $6$ ; $4 < 6$ , si prosegue. Vicini di $B$ : $A$ (già visitato, saltato), $C$ (già visitato), $D$ a $2$ . $D$ a $2$ è migliore del peggiore in $W$ : entra. $W$ diventa $(2, D)$ e $(4, B)$ ; $C$ a $6$ esce. La frontiera contiene $C$ e $D$ .

Passo 3: si estrae $D$ a $2$ . Vicini di $D$ : solo $B$ , già visitato. Niente di nuovo.

Passo 4: si estrae $C$ a $6$ . Il peggiore in $W$ è ora $B$ a $4$ . Siccome $6 > 4$ , scatta la condizione di arresto: break. La ricerca si ferma senza nemmeno espandere $C$ .

Risultato: i due vicini restituiti sono $D$ (distanza $2$ ) e $B$ (distanza $4$ ). Nota che $E$ , a distanza $7$ , non è mai stato toccato: era raggiungibile solo da $C$ , e la condizione di arresto ha tagliato $C$ prima di espanderlo. Questo è il punto — la ricerca ha visitato 4 nodi su 5 e si è fermata appena la parte promettente del grafo era esaurita. Su un grafo di un milione di nodi, la stessa logica visita poche centinaia di nodi invece di un milione.

Un’osservazione su questa traccia chiarisce il ruolo di ef. Con ef = 2 la ricerca ha tenuto vivi due candidati e ha trovato i due vicini corretti, $D$ e $B$ . Se la si fosse fatta con ef = 1 — la salita greedy pura dell’angolo 3 — da $A$ si sarebbe andati su $B$ (il più vicino tra i vicini di $A$ ), da $B$ su $D$ , e ci si sarebbe fermati a $D$ : un solo risultato. La frontiera larga è ciò che ha permesso di restituire anche $B$ e, su grafi più insidiosi, di non incagliarsi. Alzare ef allarga la rosa e alza il recall; il prezzo è che si espandono più nodi prima che la condizione di arresto scatti.

Esempio in codice: una query su un vector database

I tre parametri non sono un’astrazione accademica: ogni vector database li espone. In pgvector — l’estensione che porta la ricerca vettoriale dentro PostgreSQL — la sintassi è questa:

-- build: M e ef_construction si fissano alla creazione dell'indice
CREATE INDEX ON documenti
  USING hnsw (embedding vector_cosine_ops)
  WITH (m = 16, ef_construction = 64);

-- query: ef_search si cambia a runtime, per sessione
SET hnsw.ef_search = 100;

SELECT id, contenuto
FROM documenti
ORDER BY embedding <=> '[0.12, -0.45, ...]'
LIMIT 10;

L’operatore <=> è la distanza coseno; vector_cosine_ops dice all’indice quale metrica usare. I parametri m ed ef_construction sono congelati nella struttura dell’indice: cambiarli significa fare un DROP INDEX e ricostruire. hnsw.ef_search, invece, si imposta con un semplice SET valido per la sessione corrente: lo si alza quando una query ha bisogno di più recall, lo si abbassa quando conta la latenza. È la frontiera di Pareto resa una riga di SQL. Lo schema è identico altrove: in Qdrant gli stessi tre parametri vivono nel blocco di configurazione hnsw_config, in Weaviate e Milvus nelle rispettive configurazioni dell’indice, e nella libreria hnswlib ef_search si cambia con il metodo set_ef.

Lo stesso indice, vista la libreria standalone hnswlib, si costruisce e si interroga così:

import hnswlib

# build: M e ef_construction si fissano qui
index = hnswlib.Index(space='cosine', dim=1024)
index.init_index(max_elements=3_000_000, M=24, ef_construction=256)
index.add_items(vettori, ids)          # inserimento incrementale

# query: ef_search si cambia a runtime
index.set_ef(192)                       # >= k
etichette, distanze = index.knn_query(query, k=20)

Le tre righe che contano sono init_index (dove vivono M ed ef_construction), add_items (il build incrementale, $O(N \log N)$ ) e set_ef (la manopola query-time). È la stessa identica struttura dell’esempio SQL: cambia la sintassi, non la sostanza. Riconoscere questo schema sotto API diverse è metà del lavoro di chi usa un vector database.

Esempio reale: il retrieval di un sistema RAG

Una knowledge base aziendale, cinque milioni di chunk di documentazione, ognuno trasformato in un embedding a 1024 dimensioni da un modello di embedding. I cinque milioni di vettori vengono indicizzati con HNSW, $M = 16$ , $ef_{construction} = 200$ . Il build, eseguito una volta, richiede minuti.

A runtime un dipendente fa una domanda. La domanda diventa un vettore con lo stesso modello di embedding. Il sistema esegue una query HNSW con $ef_{search} = 128$ , recupera i $20$ chunk più vicini, raggiungendo un recall di circa $0{,}97$ in un paio di millisecondi, e li inserisce nel prompt del modello generativo. Il passo “recupera i 20 chunk più vicini” è esattamente HNSW al lavoro.

Se il prodotto pretendesse un recall di $0{,}999$ , basterebbe alzare $ef_{search}$ a diverse centinaia — nessuna ricostruzione, solo un parametro. Ma lo si pagherebbe in latenza, e qui torna la curva recall-QPS di ann-intro: nella regione ad alto recall ogni frazione di punto costa carissimo. La domanda “che recall mi serve?” va posta al prodotto con onestà, non massimizzata per default.

Un pattern frequente sgancia in parte la pressione sul recall di HNSW. Molti sistemi RAG non usano direttamente i risultati di HNSW: fanno oversampling con rerank. HNSW recupera molti più candidati del necessario — $100$ chunk invece di $20$ — e poi un modello più costoso e accurato, un reranker, riordina quei $100$ e ne tiene i $20$ migliori. In questo schema il recall di HNSW non deve essere altissimo: deve solo garantire che i $20$ chunk davvero rilevanti siano da qualche parte tra i $100$ candidati. È un recall@ $100$ , non un recall@ $20$ , ed è più facile da raggiungere con $ef_{search}$ modesto. Chi dimensiona HNSW ignorando il rerank a valle spende troppo in recall dove non serve. HNSW è quasi sempre un anello di una catena, non l’anello finale.

Esempio di scelta: HNSW contro la quantizzazione a budget di RAM stretto

Un miliardo di embedding a $768$ dimensioni, in virgola mobile a 32 bit, sono circa $3$ terabyte di soli vettori grezzi. HNSW vuole quei vettori in RAM e ci aggiunge la struttura a grafo: la memoria cresce rispetto ai dati. A questa scala, su hardware ordinario, HNSW è fuori budget.

Le altre famiglie di ann-intro rispondono diversamente. La product quantization comprime ogni vettore in poche decine di byte, riducendo la memoria di uno o due ordini di grandezza, al prezzo di distanze stimate e recall un po’ più basso — sarà il capitolo ann-ivf-pq (in preparazione). DiskANN tiene un indice a grafo su SSD invece che in RAM, accettando la latenza del disco — sarà ann-scann-diskann (in preparazione).

La lezione: HNSW domina la frontiera recall-latenza alla scala in cui i vettori stanno in memoria — milioni, decine di milioni. Alla scala dei miliardi, dove la RAM diventa il vincolo dominante, vince chi comprime o chi va su disco. Non esiste il metodo migliore in assoluto: esiste la combinazione che sta nel budget di RAM, di SSD e di latenza del caso concreto.

Applicazioni pratiche

HNSW è oggi il cavallo di battaglia della ricerca vettoriale in memoria, e lo si incontra quasi sempre senza vederlo, perché è impacchettato dentro strumenti di livello più alto.

Il caso d’uso che lo ha reso onnipresente è RAG (retrieval-augmented generation): ogni sistema che recupera documenti per nutrire il contesto di un LLM esegue, nel suo cuore, una query su un indice ANN, e quell’indice è quasi sempre HNSW. La wiki dedica al meccanismo il capitolo rag-base (in preparazione). Strettamente imparentata è la memoria a lungo termine degli agenti: un agente che accumula note, fatti, esperienze come embedding fa una query HNSW ogni volta che deve “ricordare” qualcosa di rilevante. C’è però una differenza che conta — un corpus RAG è spesso statico, la memoria di un agente cresce a ogni interazione. Questo rende l’inserimento incrementale e la cancellazione, due punti deboli di HNSW che vedremo, un fattore di progettazione reale. Il tema è il capitolo memoria-agentica (in preparazione).

A impacchettare HNSW dietro un’API ci sono i vector database. HNSW è l’indice di default o l’indice principale di Qdrant, Weaviate, Milvus, e di pgvector; è una delle scelte centrali di FAISS di Meta, la cassetta degli attrezzi della ricerca vettoriale, dove vive nella classe IndexHNSW. La libreria standalone di riferimento è hnswlib, scritta dagli stessi autori del paper: è spesso il motore che gira sotto i database citati. La wiki tratta questa categoria di prodotto nel capitolo vector-databases (in preparazione).

Fuori dal mondo LLM, HNSW alimenta i sistemi di raccomandazione (utenti e prodotti come vettori, “item simili a questo” come query k-NN), la deduplicazione e il rilevamento di quasi-duplicati, e la visual search — la ricerca di immagini per somiglianza, che era l’applicazione storica della ricerca vettoriale ben prima degli embedding di testo.

La cosa da portare via: quando uno di questi strumenti espone una manopola chiamata ef_search, ef, hnsw.ef_search, non sta offrendo una configurazione esoterica. Sta esponendo direttamente il punto sulla frontiera di Pareto recall-latenza di HNSW. Saperlo trasforma quella manopola da magia a decisione informata.

Uno scenario di tuning concreto

Si immagini il lavoro reale di chi mette in piedi il retrieval di un assistente interno. La knowledge base ha tre milioni di chunk, l’SLA di prodotto chiede una latenza di retrieval sotto i $10$ millisecondi al novantacinquesimo percentile, e il team ha stabilito — testando a mano alcune risposte — che un recall@ $20$ di $0{,}97$ è sufficiente perché il modello generativo non manchi i chunk decisivi. La macchina ha $64$ GB di RAM.

La sequenza di decisioni. Prima la memoria: tre milioni di vettori a $1024$ dimensioni in virgola mobile sono circa $12$ GB di dati grezzi; con $M = 16$ la struttura a grafo aggiunge meno di un gigabyte. Sta comodamente nei $64$ GB, quindi $M$ non è vincolato dalla memoria e si può scegliere per il recall: $M = 24$ è un buon compromesso, più connettività senza sprechi. Poi il build: è offline, gira di notte, quindi $ef_{construction} = 256$ — generoso, qualche minuto in più di build, grafo migliore. Si costruisce l’indice. Infine il tuning vero, su $ef_{search}$ : si fa girare un set di mille query di test a $ef_{search} \in \{64, 96, 128, 192, 256\}$ , si misura recall (contro il brute-force) e latenza al novantacinquesimo percentile. Supponiamo che a $ef_{search} = 128$ il recall sia $0{,}968$ con latenza $6$ ms, e a $192$ sia $0{,}974$ con $9$ ms. Si sceglie $192$ : è il valore più basso che supera $0{,}97$ restando sotto i $10$ ms. Se il traffico crescesse e la latenza sforasse, la prima leva sarebbe abbassare $ef_{search}$ , accettando un filo di recall in meno — e quella leva non richiede di toccare nulla dell’indice. È il triangolo recall-latenza-memoria attraversato una decisione alla volta.

Dove si rompe

HNSW è un compromesso ben riuscito, ma ha lati che cedono. Conoscerli prima di metterlo in produzione evita diagnosi sbagliate.

HNSW è approssimato, non esatto. È il fraintendimento di base. La ricerca greedy può restare incagliata in un ottimo locale: arriva a un nodo i cui vicini sono tutti più lontani dalla query del nodo stesso, e quindi si ferma — ma da un’altra parte del grafo, irraggiungibile da lì con passi greedy, c’è un nodo ancora più vicino. Alzare $ef_{search}$ tiene viva una frontiera più larga e riduce questo rischio, ma non lo azzera mai. Per questo HNSW dà un recall, non una garanzia. Chi ha bisogno della certezza matematica di trovare il vicino più prossimo non deve usare HNSW — deve usare il brute-force, o accettare che il risultato sia “quasi sempre” giusto.

I tre parametri non sono intercambiabili. Un errore frequente è trattare $M$ , $ef_{construction}$ ed $ef_{search}$ come tre versioni della stessa manopola. Non lo sono. $M$ è strutturale: decide la memoria, si fissa al build, cambiarlo impone una ricostruzione completa. $ef_{construction}$ è la qualità del build, pagata una volta sola in tempo di costruzione. $ef_{search}$ è la manopola query-time, l’unica che si tocca a caldo. Confonderli porta a errori concreti: credere di poter ridurre la memoria abbassando $ef_{search}$ (non la tocca affatto), o aspettarsi di cambiare $M$ senza ricostruire (impossibile).

Inserimenti e, soprattutto, cancellazioni sono scomodi. I benchmark misurano quasi sempre indici statici: costruisci una volta, interroghi tante volte. HNSW supporta l’inserimento incrementale — è proprio così che si costruisce l’indice — ma la cancellazione è il punto dolente. Il paper originale non definisce un meccanismo di cancellazione pulito. Le implementazioni reali ricorrono a tombstone (in inglese, “lapidi”): il nodo cancellato viene marcato come rimosso ed escluso dai risultati, ma resta fisicamente nel grafo, dove continua a fare da ponte tra altri nodi — hnswlib lo fa con mark_deleted. Funziona, ma cancellazioni frequenti accumulano nodi-lapide e degradano nel tempo la qualità del grafo, finché non lo si ricostruisce. Per un corpus statico è un non-problema; per la memoria di un agente che cambia in continuazione, è un fattore di progettazione da mettere in conto.

HNSW divora memoria. La struttura a grafo si somma ai vettori grezzi, che peraltro HNSW vuole tutti in RAM. È il prezzo della sua posizione sulla frontiera: HNSW domina sul recall e sulla latenza, ma è la famiglia ANN più affamata di memoria. È esattamente il motivo per cui, alla scala dei miliardi di vettori, le tecniche a quantizzazione — che comprimono — gli tolgono il primato. La scelta tra HNSW e un metodo a quantizzazione è prima di tutto una scelta di budget di RAM.

Recall alto non significa risposte buone. Vale per HNSW come per ogni metodo ANN, e va ripetuto. Il recall misura la fedeltà al brute-force: quante volte HNSW trova gli stessi vicini che troverebbe la scansione esatta. Se gli embedding sono di scarsa qualità — il modello non cattura bene la similarità semantica del dominio — un recall di $1{,}0$ recupera fedelmente i documenti sbagliati. HNSW risolve “trova i vicini in fretta”; non risolve “i vicini sono semanticamente quelli giusti”. Quel secondo problema sta a monte, nel modello di embedding. Debuggare l’indice quando il difetto è nei vettori fa perdere giornate.

La gerarchia forse non serve quanto sembra. Una sfumatura recente e onesta. Un paper del dicembre 2024, Down with the Hierarchy: The ‘H’ in HNSW Stands for ‘Hubs’ (Coleman e colleghi, arXiv:2412.01940), mostra che sui dataset ad alta dimensione — diciamo $d \geq 32$ , quindi praticamente tutti gli embedding moderni — la gerarchia a strati di HNSW non porta vantaggi misurabili: un grafo piatto fa lo stesso recall e la stessa latenza, risparmiando memoria (gli autori riportano circa un 38% di picco in meno). La spiegazione che propongono è elegante: in alta dimensione il grafo di prossimità sviluppa spontaneamente nodi hub, molto connessi, che le query attraversano presto e che fanno da “autostrada” — esattamente il lavoro per cui era stata progettata la gerarchia. La gerarchia continua a essere utile in bassa dimensione ( $d < 32$ ), dove gli hub non emergono. Questo non invalida HNSW — resta in pratica lo stato dell’arte per la ricerca in memoria — ma ridimensiona il “perché” della sua struttura: l’angolo 1, la mappa a più zoom, è una bella intuizione e regge in bassa dimensione, ma in alta dimensione il merito potrebbe stare più nei nodi hub che nella gerarchia esplicita. È un buon promemoria che gli algoritmi di successo a volte funzionano per ragioni diverse da quelle per cui erano stati progettati.

Il filtraggio sui metadati complica tutto. Nei sistemi reali la query raramente è “i vicini di $q$ ” e basta: è “i vicini di $q$ tra i documenti di questo cliente, scritti dopo gennaio”. Combinare un filtro sui metadati con la ricerca su grafo è il problema noto come filtered ANN, e non è gratis. Filtrare dopo la ricerca HNSW significa che, se il filtro è selettivo, dei vicini recuperati ne sopravvivono pochissimi e il recall effettivo crolla. Filtrare durante la navigazione del grafo è possibile ma snatura la struttura: un nodo che non passa il filtro non può essere un risultato, però potrebbe servire come ponte verso nodi validi, e saltarlo spezza la navigabilità. I vector database moderni hanno strategie dedicate per questo, ma la lezione è che il “trova i vicini” pulito di questo capitolo è un caso ideale; la produzione lo complica.

Il recall non è uniforme tra le query. Un indice HNSW configurato per un recall medio di $0{,}95$ non dà $0{,}95$ su ogni query: dà $0{,}95$ in media. Alcune query, quelle che cadono in zone difficili dello spazio — cluster densissimi accanto a regioni quasi vuote, oppure punti su cui il grafo ha sviluppato pochi archi utili — possono essere servite con recall molto più basso. Le query fuori distribuzione, lontane da dove i dati indicizzati si addensano, sono particolarmente esposte: la ricerca greedy parte dall’entry point e non trova archi che la guidino bene verso una regione poco popolata. Una media rassicurante può nascondere una coda di query servite male. Conviene guardare non solo il recall medio ma anche i percentili bassi — il decimo percentile racconta più della media — e, se la coda è un problema, alzare $ef_{search}$ ricade soprattutto su quelle query difficili.

L’ordine di inserimento lascia un’impronta. HNSW costruisce il grafo incrementalmente, un nodo alla volta, e ogni inserimento vede solo i nodi già presenti. I primi vettori inseriti formano lo scheletro del grafo quando l’indice è ancora quasi vuoto; gli ultimi si collegano a un grafo già ricco. Il risultato finale non è del tutto indipendente dall’ordine in cui i dati sono arrivati. In pratica, su dataset grandi e ben mescolati, l’effetto è piccolo e $ef_{construction}$ alto lo attenua. Ma se i dati arrivano molto ordinati — per esempio tutti i documenti di un cliente, poi tutti quelli di un altro — il grafo può risultare meno uniforme. È un buon argomento per mescolare i dati prima del build quando è possibile, e una ragione in più per cui due indici HNSW “identici” sugli stessi dati possono dare recall leggermente diversi.

Non esiste l’indice migliore in assoluto. È implicito in tutto il capitolo, ma va detto chiaro perché è una trappola frequente. Chi cerca “il miglior algoritmo ANN” pone una domanda mal formata. HNSW domina la frontiera recall-latenza quando i vettori stanno in RAM e il dataset è ragionevolmente statico; in quelle condizioni è difficile da battere. Fuori da quelle condizioni — budget di memoria stretto, scala dei miliardi, dati che cambiano ogni minuto, query con filtri pesanti — altri metodi lo superano. La risposta giusta dipende da $N$ , da $d$ , dal recall richiesto, dal budget di RAM, dal pattern di aggiornamento. Va misurata sul proprio caso, sulla propria frontiera di Pareto, non importata da una classifica generica.

E un promemoria a monte: HNSW non serve sempre. L’ultima trappola non è un difetto di HNSW, è un eccesso di entusiasmo nell’usarlo. Un indice HNSW aggiunge codice, un tempo di build, una struttura da tenere in memoria e tre parametri da governare. Tutto questo si ripaga solo se il brute-force non regge. Per dataset piccoli — fino a qualche decina di migliaia di vettori — la scansione lineare su hardware moderno risponde in pochi millisecondi, con recall esatto e zero parametri da tarare. Introdurre HNSW lì è prematura ottimizzazione: si paga complessità per un guadagno che nessuno percepisce. La regola, ripresa da ann-intro, resta: parti dal brute-force, misura la latenza reale sul tuo traffico, e passa a HNSW solo quando quella misura sfora il budget. Il capitolo descrive una macchina potente; usarla quando non serve è comunque un errore.

Collegamenti

Approximate nearest neighbor: il problema — il capitolo che pone il problema ANN, definisce le tre famiglie di metodi e introduce recall, frontiera di Pareto e l’angolo del giornalista. HNSW è la famiglia a grafo annunciata lì.
Grafi e algoritmi fondamentali — nodi, archi, vicinato, ricerca su grafo: il vocabolario su cui HNSW è interamente costruito.
Heap e priority queue — la struttura dei due heap, uno min per la frontiera e uno max per il top-ef, che governa search_layer.
A* e euristiche ammissibili — HNSW è, vista da vicino, una ricerca best-first greedy in cui la “euristica” è la distanza dalla query; il confronto con A* chiarisce cosa significa greedy e dove sta la differenza con una ricerca con garanzie.
La maledizione della dimensionalità — il fenomeno geometrico per cui gli alberi spaziali degenerano e diventa necessario un metodo a grafo come HNSW.
Norme e distanze — $L2$ , coseno e prodotto interno: le metriche di distanza rispetto a cui HNSW cerca i vicini.
Embedding: spazi e direzioni semantiche — da dove vengono i vettori che HNSW indicizza, e perché “vicino nel grafo” finisce per voler dire “semanticamente simile”.
Complessità: Big-O — il linguaggio per dire perché $\log^2(N)$ di NSW e $\log(N)$ di HNSW sono cose diverse, e cosa significa scaling logaritmico.
ann-ivf-pq (in preparazione) — la famiglia a partizionamento e quantizzazione, il principale concorrente di HNSW quando la memoria è il vincolo stretto.
ann-scann-diskann (in preparazione) — DiskANN porta un indice a grafo su SSD: la risposta a “HNSW divora memoria” alla scala dei miliardi.
lsh (in preparazione) — la famiglia a hashing, il terzo approccio ANN, con garanzie teoriche più forti ma recall empirico spesso inferiore.
rag-base (in preparazione) — il consumatore numero uno di HNSW: come il retrieval alimenta il contesto di un LLM.
memoria-agentica (in preparazione) — la memoria semantica di un agente come indice HNSW che cresce nel tempo, dove inserimento e cancellazione contano davvero.
vector-databases (in preparazione) — i prodotti che impacchettano HNSW dietro un’API, e che espongono i suoi parametri come configurazione.

Per andare oltre

Malkov, Yashunin, Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs (arXiv:1603.09320, 2016; IEEE TPAMI 42(4), 2018). Il paper che introduce HNSW: struttura a strati, distribuzione esponenziale dei livelli, algoritmi di inserimento e ricerca, euristica di selezione dei vicini. La fonte primaria, ed è leggibile.
Malkov, Ponomarenko, Logvinov, Krylov, Approximate nearest neighbor algorithm based on navigable small world graphs (Information Systems, vol. 45, 2014). Il paper NSW che precede HNSW: utile per capire da cosa HNSW nasce e quale limite — la complessità polilogaritmica — corregge.
hnswlib (github.com/nmslib/hnswlib). L’implementazione di riferimento, C++ con binding Python, scritta dagli autori del paper. Leggere add_items e searchKnn è il modo più diretto per vedere la meccanica in codice reale.
Hierarchical Navigable Small Worlds (HNSW), parte della serie sulla ricerca vettoriale di Pinecone (pinecone.io/learn). Una spiegazione divulgativa accurata, con il legame allo skip list e i valori consigliati dei parametri.
Coleman et al., Down with the Hierarchy: The ‘H’ in HNSW Stands for ‘Hubs’ (arXiv:2412.01940, 2024). Il paper che mette in discussione l’utilità della gerarchia in alta dimensione e propone l’ipotesi della “hub highway”: una lettura che insegna a non dare per scontato il perché di un algoritmo di successo.