Approximate nearest neighbor: il problema

Perché trovare il vettore più vicino in un grande insieme diventa impossibile in alta dimensione, e perché rinunciare a un po’ di precisione — accettare un risultato approssimato — è la mossa che rende la ricerca vettoriale praticabile su miliardi di embedding.

Perché questo capitolo

Un milione di documenti, ognuno trasformato in un vettore di 768 numeri. Arriva una domanda, anch’essa trasformata in un vettore di 768 numeri. La domanda operativa è una sola: quali dei milione di vettori sono più vicini a quello della query? Da quella risposta dipende cosa un sistema RAG infila nel prompt, cosa un agente “ricorda” della sua memoria, quali prodotti un motore di raccomandazione propone. È il passo più banale da descrivere e il più insidioso da realizzare in fretta.

Banale perché la soluzione esatta si scrive in tre righe: confronta la query con tutti i vettori, tieni i più vicini. Insidiosa perché quel “confronta con tutti” non scala. A un milione di vettori una scansione completa è ancora gestibile; a un miliardo, con migliaia di query al secondo da servire, diventa un costo che nessun budget di latenza assorbe.

E il rimedio istintivo — “indicizzo lo spazio con un albero, come farei in due dimensioni” — qui non funziona. In alta dimensione gli alberi spaziali collassano in qualcosa che non è più veloce della scansione lineare. Questo fallimento ha un nome, maledizione della dimensionalità, e capirlo è metà del capitolo.

L’altra metà è la via d’uscita. Non un algoritmo più astuto per la ricerca esatta — quella strada è chiusa da un risultato teorico — ma un cambio di problema: accettare di sbagliare ogni tanto. Restituire un vicino quasi il più prossimo invece del vicino esattamente più prossimo. È il passaggio da exact a Approximate Nearest Neighbor, ANN, e da quel piccolo compromesso nascono guadagni di velocità di ordini di grandezza. Questo capitolo apre una mini-serie: dopo di esso vengono i capitoli su HNSW, su IVF e product quantization, su ScaNN e DiskANN, su LSH. Qui si pone il problema; lì si vedono le soluzioni in dettaglio.

Contesto

Il problema del vicino più prossimo non nasce con gli LLM. Ha radici nella geometria computazionale e, soprattutto, nella computer vision degli anni 2000.

Un’immagine veniva descritta da centinaia di descrittori SIFT o GIST — vettori numerici che catturano texture e forme locali — e cercare immagini simili voleva dire cercare descrittori vicini in un archivio enorme. I paper fondativi della ricerca vettoriale su larga scala, come quello sulla product quantization di Hervé Jégou e colleghi (2011), sono validati proprio su SIFT e GIST, non su testo. Il problema esisteva, era studiato, e aveva già soluzioni industriali — semplicemente, l’applicazione era la ricerca di immagini, non il recupero di documenti per un modello linguistico.

Il termine maledizione della dimensionalità (curse of dimensionality) è ancora più vecchio: lo conia Richard Bellman, matematico statunitense, negli anni ‘50, lavorando su programmazione dinamica e controllo ottimo. Indicava un fenomeno generale: molti problemi diventano esponenzialmente più difficili man mano che cresce il numero di variabili in gioco. La ricerca del vicino più prossimo ne è un caso da manuale, e la wiki gli dedica un capitolo a sé in La maledizione della dimensionalità.

Il punto di svolta teorico è un paper di Piotr Indyk e Rajeev Motwani, presentato allo STOC 1998 e poi ampliato — Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality (la versione consolidata, con Sariel Har-Peled, è del 2012 su Theory of Computing). Il titolo dichiara il programma: la maledizione si può rimuovere, a patto di accontentarsi di un risultato approssimato. Quel paper introduce anche il locality-sensitive hashing, una delle tre grandi famiglie di metodi ANN.

La svolta pratica arriva dopo, con due ondate. La prima, intorno al 2011-2017, è la ricerca su scala industriale: la product quantization di Jégou, e poi FAISS (Facebook AI Similarity Search), la libreria di Meta descritta nel paper Billion-scale similarity search with GPUs (Johnson, Douze, Jégou, 2017), che costruisce per la prima volta un grafo dei vicini su un miliardo di vettori. La seconda ondata è il presente: gli embedding prodotti da reti neurali — vettori densi che rappresentano testo, immagini, codice — hanno reso “essere semanticamente simili” sinonimo di “essere vicini in uno spazio vettoriale”. Da quel momento la ricerca ANN smette di essere una tecnica di nicchia per la vision e diventa l’organo centrale di RAG, della memoria degli agenti, dei vector database. Questo capitolo sta a valle di embedding: spazi e direzioni semantiche, che spiega da dove vengono quei vettori, e a monte dei quattro capitoli ANN che seguono.

Vale la pena fissare la cronologia, perché chiarisce un equivoco frequente — l’idea che la ricerca vettoriale sia “una cosa nata con ChatGPT”. Non lo è.

Il filone teorico parte negli anni ‘90 ed è puro problema di algoritmi e geometria. Il filone industriale matura negli anni 2010 attorno alla vision e alla ricerca di immagini. Il filone a grafo, con HNSW nel 2016, nasce anch’esso prima dell’esplosione degli LLM.

Ciò che è cambiato dal 2020 in poi non sono gli algoritmi — sono in larga parte gli stessi — ma il fatto che produrre embedding di buona qualità per testo arbitrario sia diventato facile ed economico. Una volta che chiunque può trasformare un documento in un vettore semanticamente significativo, l’intera infrastruttura ANN, già pronta da anni, trova un’applicazione di massa. È un caso di tecnologia matura che aspetta il suo caso d’uso, non di invenzione improvvisa.

L’intuizione

Tre angoli per entrare nel problema prima di qualunque formula.

Angolo 1 — la biblioteca senza catalogo

Immagina una biblioteca con un milione di libri, e una regola strana: i libri non sono ordinati per autore o per tema, ma disposti nello spazio in modo che due libri “simili nel contenuto” stiano fisicamente vicini. Entri con un libro in mano e chiedi: qual è il libro più simile a questo?

Senza catalogo, l’unico metodo sicuro è camminare lungo tutti gli scaffali, prendere ogni libro, confrontarlo con quello che hai in mano, e ricordarti il più simile visto finora. Un milione di confronti. È la ricerca esatta per scansione lineare (brute-force): garantisce la risposta giusta, e ha un costo proporzionale alla dimensione della biblioteca.

Ora immagina di poter installare un catalogo che ti porta direttamente nello scaffale giusto. In una biblioteca normale — libri su una sola stanza, una griglia bidimensionale — funziona benissimo: il catalogo dimezza lo spazio di ricerca a ogni passo.

Il guaio è che i libri-vettore di cui parliamo non vivono in due dimensioni: vivono in 768, o 1536, o 3072. E in quel numero di dimensioni, come vedremo, il catalogo smette di funzionare. Il punto di partenza del capitolo è capire perché quel catalogo, che pare ovvio, fallisce; e cosa lo sostituisce.

Angolo 2 — la geometria che inganna l’intuito

Il secondo angolo è geometrico, e va contro l’intuizione. In due o tre dimensioni il concetto di “vicino” è solido: alcuni punti sono chiaramente accanto a te, altri chiaramente lontani, c’è contrasto. La nostra intuizione spaziale è tarata su queste dimensioni.

In alta dimensione quel contrasto svanisce. Prendi un punto query e misura la distanza da tutti gli altri punti: in 1000 dimensioni, la distanza dal punto più vicino e quella dal punto più lontano diventano quasi uguali in rapporto.

Non perché i punti siano disposti male, ma perché lo spazio ad alta dimensione ha questa proprietà: il volume si addensa in gusci sottili lontano dal centro, e quasi tutte le coppie di punti finiscono a distanze simili tra loro. È come se, salendo di dimensione, tutti i libri della biblioteca arretrassero fino a sembrare appartenere allo stesso scaffale lontano.

Questa è la maledizione della dimensionalità vista dal lato delle distanze: la concentrazione delle distanze. Ha una conseguenza diretta sugli indici. Un albero spaziale taglia rami della ricerca dicendo “in quella regione non ci può essere nulla di più vicino di quanto ho già trovato”. Ma se quasi tutti i punti sono a distanza simile, quella garanzia non scatta quasi mai: l’albero non riesce a scartare nulla e finisce per guardare tutto.

Si tornerà su questo in dettaglio nella sezione meccanica; per ora basta l’immagine: in alta dimensione lo spazio non offre più appigli per “saltare” verso la risposta.

Angolo 3 — sbagliare di poco costa pochissimo

Il terzo angolo è il più importante, ed è economico più che geometrico. Davanti a un muro, una strategia è cercare un attrezzo più potente per sfondarlo. Un’altra è chiedersi se il muro vada davvero sfondato.

Per la ricerca esatta del vicino più prossimo il muro è reale: lo dice un teorema, non un’implementazione pigra. Ma riformuliamo la domanda.

In un sistema RAG, qual è il danno se su dieci documenti recuperati ne perdo uno e al suo posto ne prendo un altro quasi altrettanto rilevante? Quasi nullo. Il modello a valle riceve comunque nove documenti buoni su dieci e un decimo accettabile. Il valore del risultato cade pochissimo. Il costo di pretendere il decimo esatto, invece, è enorme: significa restare aggrappati alla scansione lineare.

Questo squilibrio — perdita di qualità minuscola, guadagno di velocità gigantesco — è la leva di tutta la ricerca approssimata. Si rinuncia alla garanzia “il risultato è il più vicino” e la si sostituisce con “il risultato è quasi il più vicino, quasi sempre”. In cambio, la query smette di toccare tutti i punti e ne tocca una frazione. È il passaggio da exact a Approximate Nearest Neighbor. Tutto il resto del capitolo, e l’intera mini-serie, vive dentro questa scelta.

Angolo 4 — il giornalista che chiede in giro

Un ultimo angolo, operativo, perché anticipa come lavorano davvero i metodi ANN. Immagina di dover trovare la persona più esperta su un argomento dentro una grande azienda, e di non avere un organigramma delle competenze. Una strada è intervistare tutti, uno per uno: è il brute-force, esatto e lentissimo. Un’altra è fare il giornalista. Parti da una persona qualsiasi e le chiedi: “chi conosci che ne sa più di te su questo?”. Vai da chi ti indica, ripeti la domanda, ti sposti di nuovo. A ogni passo ti avvicini, e ti fermi quando nessuno sa indicarti qualcuno di più competente.

Questa passeggiata da contatto a contatto non garantisce di trovare in assoluto il massimo esperto: potresti fermarti su un ottimo locale, una persona molto brava circondata da gente meno esperta di lei ma che non conosce il vero numero uno in un altro reparto. In compenso arrivi a una risposta molto buona dopo una manciata di salti, non dopo migliaia di interviste.

È esattamente lo schema dei metodi a grafo, HNSW in testa: la rete di “chi conosce chi” è il grafo di prossimità, e la query è questa navigazione greedy. L’ottimo locale in cui ci si può incagliare è la ragione per cui questi metodi sono approssimati e non esatti — e la ragione per cui hanno parametri che regolano quanto a fondo esplorare prima di accontentarsi.

Figura in preparazione

fig-1: tre pannelli affiancati. (1) Brute-force: una query confrontata con tutti i punti, frecce a ognuno. (2) Albero che degenera: in alta dimensione quasi nessun ramo potato, l’albero visita tutte le foglie. (3) ANN: la query tocca solo una piccola regione dei punti. Titolo “Esatto contro approssimato: cosa cambia per la query”

La meccanica

Il problema, formalmente

Si parte da un insieme di $N$ punti, ognuno un vettore di $d$ numeri reali: $P = \{x_1, x_2, \dots, x_N\}$ con ogni $x_i$ in $\mathbb{R}^d$. Arriva una query $q$, anch’essa un vettore in $\mathbb{R}^d$. Serve una funzione di distanza $\text{dist}(\cdot, \cdot)$ — più sotto vediamo quali.

Il problema del nearest neighbor (vicino più prossimo) chiede il punto del dataset a distanza minima dalla query:

$\text{NN}(q) = \arg\min_{x_i \in P} \text{dist}(q, x_i)$

In parole povere: scorri tutti i punti, restituisci quello che minimizza la distanza. La versione usata in pratica è il k-NN: invece di un solo vicino, restituire i $k$ più vicini (i primi 10, i primi 100). $N$ è la dimensione del dataset, $d$ è la dimensionalità dei vettori, $k$ è quanti vicini si vogliono — tre numeri che torneranno di continuo.

La versione approssimata rilassa la richiesta. Si introduce un fattore di tolleranza $c > 1$. Il problema c-approximate nearest neighbor chiede di restituire un qualsiasi punto $p$ del dataset tale che:

$\text{dist}(q, p) \le c \cdot \text{dist}(q, p^*)$

dove $p^*$ è il vero vicino più prossimo. In parole povere: il risultato non deve essere il più vicino, basta che non sia più lontano di $c$ volte il più vicino. Con $c = 1$ si ricade nell’esatto; con $c$ leggermente sopra 1 (per esempio 1.1) si concede un piccolo errore.

Questa è la definizione del paper di Har-Peled, Indyk e Motwani, e il fattore $c$ è la manopola formale che apre la porta a tutti i metodi veloci. C’è una differenza di linguaggio da tenere a mente: la teoria ragiona con il fattore $c$, garanzia sul quanto è peggiore il risultato restituito; i sistemi reali, come vedremo, ragionano con il recall, garanzia statistica su quante volte l’indice trova i veri vicini. Sono due modi di quantificare lo stesso compromesso. La teoria preferisce il primo perché si presta alle dimostrazioni; la pratica preferisce il secondo perché è ciò che si misura davvero su un dataset.

Il brute-force, e perché è il riferimento

La ricerca esatta per scansione si scrive così:

def knn_bruteforce(query, dataset, k, dist):
    # un heap dei k candidati migliori visti finora
    best = []  # coppie (distanza, indice)
    for i, x in enumerate(dataset):
        d = dist(query, x)
        if len(best) < k:
            heap_push(best, (d, i))
        elif d < heap_max(best):
            heap_replace_max(best, (d, i))
    return sorted(best)

Riga per riga: si scorre l’intero dataset; per ogni punto si calcola la distanza dalla query; si mantengono i $k$ migliori in una coda di priorità — uno heap, la struttura che restituisce sempre l’elemento estremo, descritta in Heap e priority queue. Se il nuovo punto è migliore del peggiore tra i $k$ candidati, lo si sostituisce.

Il costo è $N$ calcoli di distanza, ognuno dei quali tocca $d$ coordinate: in totale $O(N \cdot d)$ per query. Per $N$ piccolo va benissimo, ed è anche imbattibile in semplicità.

Il brute-force resta il riferimento per due motivi. Primo: dà sempre la risposta esatta, quindi è il ground truth contro cui si misura ogni metodo approssimato — senza un brute-force con cui confrontarsi, la parola “recall” non avrebbe nemmeno senso. Secondo: per dataset fino a qualche decina di migliaia di vettori, su hardware moderno, è già abbastanza veloce, e non sempre serve un indice. La regola pratica è non costruire un indice ANN finché il brute-force regge: aggiunge complessità, build time e un parametro di recall da governare.

Il problema nasce con lo scaling. A $N$ di un miliardo e $d$ di 1536, ogni query è circa $1{,}5 \cdot 10^{12}$ operazioni; moltiplicato per migliaia di query al secondo, è fuori da qualunque budget. È qui, e solo qui, che l’indice approssimato diventa necessario.

Perché gli alberi spaziali degenerano

L’idea più naturale per battere il brute-force è il k-d tree (k-dimensional tree, albero che partiziona lo spazio): un albero binario che a ogni livello taglia lo spazio con un iperpiano perpendicolare a una dimensione, alternando le dimensioni. La query scende nell’albero e — questo è il punto — pota interi sottoalberi: se la distanza dalla query al miglior candidato trovato finora è più piccola della distanza della query al piano di split, allora dall’altro lato del piano non può esserci nulla di meglio, e quel sottoalbero si salta.

In 2 o 3 dimensioni questa potatura è efficacissima: l’albero scarta grandi porzioni dello spazio e la ricerca costa $O(\log N)$. È il “catalogo” della biblioteca dell’angolo 1.

In alta dimensione la potatura smette di scattare. Il motivo è la concentrazione delle distanze dell’angolo 2: il raggio del miglior candidato è quasi sempre più grande della distanza ai piani di split, perché tutti i punti sono a distanze simili. La condizione “scarta questo sottoalbero” diventa quasi sempre falsa.

L’albero, invece di potare, visita praticamente tutte le foglie. Il costo torna a $O(N \cdot d)$ — come il brute-force, ma con in più l’overhead di navigare i nodi dell’albero. È peggio del brute-force. Empiricamente la soglia di degenerazione è bassa: già intorno a 10-20 dimensioni il vantaggio dell’albero svanisce, e gli embedding moderni vivono a 384, 768, 1536, 3072 dimensioni.

Questa non è una debolezza di una singola struttura dati. Il risultato di Har-Peled, Indyk e Motwani lo afferma in forma generale: per il nearest neighbor esatto in alta dimensione, le strutture dati conosciute hanno spazio oppure tempo di query con dipendenza esponenziale in $d$. È la maledizione della dimensionalità nella sua forma più cruda. Non c’è un albero più astuto in attesa di essere inventato: c’è un muro.

Figura in preparazione

fig-2: la maledizione della dimensionalità. A sinistra, istogramma delle distanze query-punti in dimensione bassa: distribuzione larga, contrasto netto tra vicini e lontani. A destra, lo stesso istogramma in dimensione alta: distribuzione stretta e concentrata, vicini e lontani indistinguibili. Titolo “In alta dimensione tutte le distanze si assomigliano”

Due tempi distinti: build e query

Prima di parlare di come si misurano gli indici, conviene separare due momenti che il brute-force non distingue e che invece sono il cuore di ogni metodo ANN.

Il primo momento è il build: si prende il dataset e lo si trasforma una volta sola in una struttura dati ausiliaria — un grafo, un insieme di cluster, una tabella di hash. È un lavoro pesante, fatto in anticipo, prima che arrivi qualunque query. Il brute-force non ha un build: il “dataset” è già la sua struttura.

Il secondo momento è la query: arriva $q$, e si usa la struttura costruita per restringere la ricerca a una frazione dei punti. Qui si paga la latenza che l’utente percepisce.

Questa separazione spiega gran parte dei trade-off. Un indice può avere un build lentissimo e una query fulminea — accettabile se costruisci una volta e interroghi milioni di volte. Oppure può avere un build veloce ma supportare male le cancellazioni — un problema se i dati cambiano in continuazione. Quando un capitolo della mini-serie dirà che HNSW “costa in costruzione” o che la product quantization “addestra un codebook”, sta parlando del tempo di build. Tenere mentalmente separati i due tempi evita la confusione più comune nel leggere i benchmark.

Le metriche di distanza

Il problema parla di “distanza”, ma quale? Tre scelte dominano la ricerca vettoriale, e la wiki le tratta in dettaglio in Norme e distanze.

La distanza euclidea, o norma $L2$, è la distanza “in linea d’aria”:

$\text{dist}_{L2}(a, b) = \sqrt{\sum_{j=1}^{d} (a_j - b_j)^2}$

In parole povere: la radice della somma dei quadrati delle differenze, coordinata per coordinata. Più è piccola, più i due vettori sono simili.

La similarità coseno misura l’angolo tra i due vettori, ignorando la loro lunghezza:

$\cos(a, b) = \frac{a \cdot b}{\|a\| \, \|b\|}$

dove $a \cdot b$ è il prodotto scalare (la somma dei prodotti coordinata per coordinata) e $\|a\|$ è la norma, cioè la lunghezza del vettore. Vale tra $-1$ e $1$; più è grande, più i vettori puntano nella stessa direzione.

Il prodotto interno (inner product, o dot product) è il prodotto scalare grezzo, $a \cdot b$, senza dividere per le norme. Più è grande, più i vettori sono “allineati e lunghi”. Cercare il punto di massimo prodotto interno ha un nome proprio, MIPS (maximum inner product search). Una sottigliezza: il prodotto interno non è una distanza vera — non rispetta la disuguaglianza triangolare — e questo complica alcuni indici. Il metodo ScaNN, che vedremo nella mini-serie, nasce proprio per ottimizzare MIPS.

C’è un legame che semplifica molto la vita pratica. Numerosi modelli di embedding producono, o vengono normalizzati a, vettori di norma unitaria ($\|a\| = 1$). Su vettori normalizzati il prodotto interno coincide con il coseno, e vale l’identità $\|a-b\|^2 = 2 - 2\cos(a,b)$: ordinare i punti per distanza euclidea crescente dà esattamente lo stesso ordine che ordinarli per coseno decrescente.

Quindi su embedding normalizzati la scelta tra le tre metriche non cambia chi sono i vicini, cambia solo la formula con cui li si calcola. Il benchmark di riferimento del settore, ANN-Benchmarks, riflette questa distinzione raggruppando i suoi dataset in “angular” (basati su coseno: glove, nytimes) ed “euclidean” (basati su $L2$: sift, gist, fashion-mnist). La regola operativa è una sola: usare la metrica con cui il modello di embedding è stato addestrato, perché è quella rispetto a cui le sue distanze sono semanticamente sensate.

Come si misura un indice approssimato

Un metodo esatto si misura solo sulla velocità: la risposta è per definizione corretta. Un metodo approssimato no — può sbagliare, e va misurato anche su quanto sbaglia.

La metrica di qualità è il recall@k: la frazione dei veri $k$ vicini che l’indice approssimato ha effettivamente recuperato, mediata su molte query. Recall@10 pari a $0{,}95$ significa che, in media, l’indice trova 9,5 dei 10 veri vicini; gli altri 0,5 sono persi e sostituiti da punti leggermente peggiori.

Da notare bene: il “ground truth” qui è il risultato del brute-force. Il recall misura la fedeltà dell’indice alla scansione esatta, non la bontà semantica delle risposte. È una metrica relativa, non assoluta — dice quanto l’indice si avvicina alla risposta esatta, non quanto la risposta esatta è utile.

La metrica di costo è la latenza per query, o equivalentemente il QPS (queries per second, query al secondo) in regime multi-thread. Ma costo e qualità non bastano: pesano anche la memoria occupata dall’indice (byte per vettore) e il tempo di build, quanto costa costruire l’indice e aggiornarlo quando arrivano nuovi vettori o se ne cancellano.

Lo strumento standard per confrontare i metodi è ANN-Benchmarks, una suite aperta mantenuta da Martin Aumüller, Erik Bernhardsson e Alec Faithfull. Per ogni algoritmo, variando i suoi parametri di tuning, si ottiene una curva nel piano recall-QPS: alzando la qualità si abbassa la velocità, e viceversa. Si confrontano le frontiere di Pareto di queste curve. Un metodo “domina” un altro se, a parità di recall, fa più QPS; a parità di QPS, ha recall più alto. Il punto chiave è che nessun metodo domina ovunque: ognuno è migliore in una regione del piano. Scegliere un indice ANN significa scegliere un punto su una frontiera di Pareto, in base al recall che il prodotto richiede e al budget di memoria disponibile — non cercare un fantomatico “algoritmo migliore”.

Figura in preparazione

fig-3: piano recall-QPS. Asse x recall da 0,8 a 1,0, asse y QPS in scala logaritmica. Tre curve etichettate “a grafo”, “a quantizzazione”, “a hashing”, ciascuna che cala salendo verso recall alto. Una curva orizzontale bassa etichettata “brute-force (recall 1,0 sempre)”. Titolo “La frontiera di Pareto: nessun metodo vince ovunque”

Perché la curva recall-QPS ha quella forma

Una proprietà conviene capirla fino in fondo, perché torna in ogni capitolo della mini-serie: la curva recall-QPS non è una retta, è una curva che si impenna. Nella regione di recall medio — diciamo da $0{,}80$ a $0{,}95$ — guadagnare qualche punto di recall costa poco in velocità. Nella regione di recall alto — da $0{,}98$ a $1{,}0$ — ogni frazione di punto costa carissimo: il QPS crolla.

Il motivo è strutturale. Un indice ANN raccoglie candidati e spera che tra essi ci siano i veri vicini. I primi candidati che raccoglie sono i più promettenti: con poco lavoro cattura la gran parte dei veri vicini, perché quelli “facili” stanno proprio dove l’indice guarda per primo.

I veri vicini mancanti, quel residuo che separa recall $0{,}95$ da recall $1{,}0$, sono i casi difficili: vicini che per la struttura dell’indice si trovano in posizioni scomode, raggiungibili solo allargando molto la raccolta di candidati. Allargare la raccolta ha un costo che cresce in fretta, e cattura sempre meno vicini nuovi per ogni candidato in più. È il classico rendimento decrescente: l’ultimo 5% di recall costa più del primo 80%.

La conseguenza operativa è netta. La domanda “che recall mi serve?” va posta con onestà al prodotto. Per un RAG su documentazione, recall $0{,}9$-$0{,}95$ è quasi sempre più che sufficiente, e sta nella parte economica della curva. Pretendere $0{,}999$ “per sicurezza”, quando il modello a valle non se ne accorgerebbe, significa pagare un ordine di grandezza di QPS per un beneficio che nessuno misurerà. Il recall richiesto è una decisione, non un default da massimizzare.

Le tre famiglie di metodi ANN

Tutti i metodi ANN condividono la stessa idea: non toccare tutti i punti, toccarne pochi e sperare che tra quei pochi ci siano i veri vicini.

Differiscono nel come scelgono quei pochi. Tre grandi famiglie, e a ciascuna la mini-serie dedica un capitolo proprio.

A grafo. Si costruisce un grafo in cui ogni vettore è un nodo collegato ad alcuni dei suoi vicini. La query diventa una passeggiata: si parte da un nodo qualsiasi e ci si sposta, passo dopo passo, verso il vicino più vicino alla query, finché non si riesce più a migliorare. È la discesa greedy dell’angolo 4, il giornalista che chiede in giro.

Il capostipite moderno è HNSW (Hierarchical Navigable Small World), introdotto da Yury Malkov e Dmitry Yashunin nel 2016: un grafo a più livelli, con i livelli alti radi — per coprire grandi distanze in pochi salti — e i livelli bassi densi, per la rifinitura locale. Tende a stare sulla frontiera di Pareto nella regione ad alto recall, al prezzo di un consumo di memoria elevato. Dettaglio nel capitolo ann-hnsw (in preparazione).

A partizionamento e quantizzazione. Questa famiglia combina due idee distinte, che conviene tenere separate.

Il partizionamento raggruppa i vettori in cluster, tipicamente con l’algoritmo k-means. A query time si calcola quali cluster hanno il centroide più vicino alla query e si guardano solo quelli, ignorando tutti gli altri. È l’IVF (inverted file, file invertito): il parametro che regola quanti cluster ispezionare — nprobe — è la manopola recall/velocità di questa tecnica.

La quantizzazione comprime ogni vettore in un codice compatto, riducendo insieme la memoria e il costo di ogni calcolo di distanza. La product quantization di Jégou, Douze e Schmid (2011) spezza ogni vettore in sotto-vettori, ne quantizza ciascuno con un piccolo dizionario di centroidi appreso in fase di build, e stima le distanze leggendole da una tabella precalcolata invece di ricalcolarle. La combinazione IVF + product quantization è ciò che ha reso possibile la ricerca su miliardi di vettori, ed è il cuore di FAISS.

Sulla stessa famiglia si innestano due varianti specializzate. ScaNN di Google (Guo et al., 2020) è una quantizzazione con una funzione di errore “anisotropa”, pensata su misura per il maximum inner product search. DiskANN sposta un indice a grafo dal RAM al disco SSD, per scalare oltre quanto la memoria contiene. Dettagli nei capitoli ann-ivf-pq (in preparazione) e ann-scann-diskann (in preparazione).

A hashing. L’LSH (Locality-Sensitive Hashing, hashing sensibile alla località) usa famiglie di funzioni hash con una proprietà rovesciata rispetto agli hash crittografici: invece di disperdere uniformemente gli input, fanno collidere apposta i punti vicini. Due vettori simili finiscono nello stesso bucket con alta probabilità; la query calcola il proprio hash e guarda solo il bucket corrispondente. È la famiglia con le garanzie teoriche più solide — i bound di Indyk e Motwani — e quella da cui storicamente è partita la teoria dell’ANN. Dettaglio nel capitolo lsh (in preparazione).

Una buona regola mentale: a grafo per il recall più alto, a quantizzazione quando la memoria è il vincolo stretto, a hashing per le garanzie formali. Ma il confronto vero si fa sempre sulla frontiera di Pareto del proprio dataset.

In forma di tabella, per fissare le coordinate prima di entrare nei capitoli dedicati:

Famiglia	Idea centrale	Capitolo dedicato	Forte su	Debole su
A grafo	Navigazione greedy su un grafo di prossimità	ann-hnsw	Recall alto, latenza bassa	Memoria, build da zero
A partizionamento/quantizzazione	Cluster da guardare + codici compressi	ann-ivf-pq, ann-scann-diskann	Memoria, scala a miliardi	Recall altissimo
A hashing	Hash che fanno collidere i vicini	lsh	Garanzie teoriche, semplicità	Recall empirico, tuning

I quattro capitoli successivi della mini-serie scendono dentro queste righe. ann-hnsw spiega come si costruisce un grafo navigabile a più livelli e perché la gerarchia dà uno scaling logaritmico. ann-ivf-pq mostra la meccanica dell’inverted file e della product quantization, con le tabelle di lookup che rendono il calcolo delle distanze quasi gratuito. ann-scann-diskann affronta due esigenze specializzate: ScaNN per il maximum inner product search, DiskANN per gli indici che non entrano in RAM e vivono su SSD. lsh chiude con la famiglia a hashing e le sue garanzie probabilistiche. Questo capitolo è la mappa; quei quattro sono i territori.

Esempi

Esempio numerico: quando il brute-force smette di bastare

Un dataset di $N = 1\,000\,000$ embedding, dimensione $d = 768$. Una query brute-force calcola un milione di distanze euclidee, ognuna circa $768$ sottrazioni, $768$ quadrati e $768$ somme: dell’ordine di $2 \cdot 10^9$ operazioni in virgola mobile per query. Su una CPU moderna che, ben ottimizzata, gira a qualche decina di miliardi di operazioni al secondo, sono decine di millisecondi. Per una singola query offline è accettabile.

Ora si moltiplica per il traffico. Mille query al secondo significano $2 \cdot 10^{12}$ operazioni al secondo richieste, oltre la capacità di una singola macchina, e la latenza per utente sale. E questo è solo un milione di vettori: a un miliardo, il fattore è altri mille.

Un indice ANN che, a recall $0{,}95$, tocca diciamo l’1-2% dei punti per query riduce il lavoro di uno o due ordini di grandezza. Quel 5% di vicini persi è il prezzo; la latenza che scende da decine di millisecondi a una manciata è ciò che si compra. È lo scambio dell’angolo 3 messo in numeri.

Vale la pena notare un effetto secondario. La memoria grezza del dataset — un milione di vettori a 768 dimensioni in virgola mobile a 32 bit — è circa 3 gigabyte, una cifra che sta comodamente nella RAM di un portatile. È un altro modo di vedere perché il primo problema che si incontra crescendo non è la memoria ma la latenza: i vettori ci stanno, ma confrontarli tutti a ogni query costa troppo tempo. La memoria torna a essere il vincolo dominante solo molto più avanti, alla scala dei miliardi di vettori, dove entrano in gioco le tecniche di compressione.

Esempio in codice: lo scheletro di una query ANN

Tutti i metodi della sezione precedente, sotto la varietà di strutture, eseguono lo stesso schema in tre fasi:

def ann_query(query, index, k):
    # 1. RESTRINGI: dalla struttura dell'indice, scegli un piccolo
    #    insieme di candidati senza toccare tutto il dataset.
    #    - a grafo:     navighi il grafo partendo da un entry point
    #    - a partizioni: prendi i punti dei cluster vicini
    #    - a hashing:   prendi i punti che cadono nei tuoi bucket
    candidates = index.gather_candidates(query)

    # 2. VALUTA: calcola la distanza esatta (o stimata) solo
    #    sui candidati. Sono pochi, quindi è veloce.
    scored = [(dist(query, c), c) for c in candidates]

    # 3. SELEZIONA: tieni i k migliori, di nuovo con un heap.
    return k_smallest(scored, k)

Le fasi 2 e 3 sono identiche a quelle del brute-force: calcola distanze, tieni i migliori con un heap. La differenza sta tutta nella fase 1: il brute-force mette in candidates l’intero dataset, un metodo ANN ce ne mette una piccola frazione. Ogni famiglia è semplicemente un modo diverso di scrivere gather_candidates.

I parametri di tuning di un vector database — ef_search per HNSW, nprobe per IVF — controllano quanti candidati raccogliere: più candidati, più recall, meno velocità. Sono la manopola della frontiera di Pareto esposta all’utente.

Per rendere concreta la fase 1, segue una raccolta candidati a grafo, scritta come pseudocodice. È l’angolo 4 in forma di algoritmo:

def gather_candidates_graph(query, graph, ef):
    # ef: quanti candidati tenere "vivi" durante la ricerca.
    # Più alto significa più recall e più lavoro.
    start = graph.entry_point()
    visited = {start}
    # frontiera: nodi da esplorare, ordinati per vicinanza alla query
    frontier = min_heap([(dist(query, start), start)])
    best = max_heap([(dist(query, start), start)])  # i migliori ef finora

    while frontier:
        d, node = heap_pop_min(frontier)
        # stop: se il candidato più promettente è peggiore
        # del peggiore tra i migliori ef, non si migliora oltre
        if d > heap_max(best):
            break
        for neighbor in graph.neighbors(node):
            if neighbor in visited:
                continue
            visited.add(neighbor)
            dn = dist(query, neighbor)
            if dn < heap_max(best) or len(best) < ef:
                heap_push(frontier, (dn, neighbor))
                heap_push(best, (dn, neighbor))
                if len(best) > ef:
                    heap_pop_max(best)
    return [node for _, node in best]

Riga per riga: si parte da un punto di ingresso fisso del grafo; si tiene una frontiera dei nodi da esplorare, ordinata per vicinanza alla query, e un insieme dei migliori ef candidati visti finora. A ogni passo si estrae dalla frontiera il nodo più promettente, si guardano i suoi vicini nel grafo, e quelli abbastanza buoni entrano sia nella frontiera sia nei migliori. La ricerca si ferma quando il nodo più promettente della frontiera è già peggiore del peggiore tra i migliori ef: da lì in poi non si può che peggiorare.

Il numero di nodi visitati è una piccola frazione del dataset — è il guadagno. Il parametro ef è la manopola: alzarlo tiene viva una frontiera più larga, esplora di più, alza il recall e abbassa la velocità. È esattamente lo stesso pseudocodice che il capitolo ann-hnsw (in preparazione) prenderà e raffinerà aggiungendo la gerarchia di livelli; qui basta vedere che gather_candidates non è magia, è una passeggiata greedy con una condizione di arresto.

Esempio reale: il retrieval di un sistema RAG

Una knowledge base aziendale, diciamo la documentazione interna: migliaia di pagine.

La pipeline RAG la spezza in chunk — paragrafi o sezioni — e per ciascun chunk un modello di embedding produce un vettore. Centinaia di migliaia di vettori finiscono in un indice ANN.

A runtime un dipendente fa una domanda. La domanda diventa un vettore con lo stesso modello di embedding. Il sistema esegue una query ANN, recupera i, poniamo, 8 chunk più vicini, e li inserisce nel prompt del modello generativo, che risponde basandosi su quel contesto. Il passo “recupera gli 8 chunk più vicini” è esattamente il problema di questo capitolo. Se la knowledge base cresce a milioni di chunk, il brute-force non regge la latenza interattiva, e l’indice ANN diventa obbligatorio. Il parametro di recall dell’indice diventa allora una decisione di prodotto: recall più alto significa meno rischio di mancare il chunk decisivo, ma latenza e costo più alti. È la stessa scelta, ora vestita da requisito di business.

Esempio di scelta: memoria contro qualità su un miliardo di vettori

Un quarto scenario chiarisce perché la decisione non si gioca solo su recall e velocità. Un miliardo di embedding a $d = 768$, in virgola mobile a 32 bit, occupano circa $1\,000\,000\,000 \times 768 \times 4$ byte, cioè dell’ordine di 3 terabyte. Tenere tutto questo in RAM, su una sola macchina, è impraticabile o costosissimo.

Qui le tre famiglie offrono risposte diverse, e la scelta è prima di tutto economica.

Un indice a grafo come HNSW vuole i vettori in RAM e aggiunge la sua struttura di collegamenti: la memoria cresce rispetto ai dati grezzi. Ottimo per il recall, fuori budget a questa scala su hardware ordinario.

La product quantization fa l’opposto: comprime ogni vettore in un codice di poche decine di byte invece di 3072, riducendo la memoria di uno o due ordini di grandezza — al prezzo di distanze stimate, non esatte, e quindi di un recall un po’ più basso. DiskANN sceglie un’altra via ancora: tiene l’indice a grafo su SSD invece che in RAM, accettando la latenza più alta del disco in cambio della capacità di scalare oltre la memoria.

Non c’è una risposta universale: c’è la combinazione che sta nel budget di RAM, di SSD e di latenza del caso concreto. Questo è il senso pieno del trade-off a quattro grandezze — recall, latenza, memoria, build — e il motivo per cui la mini-serie dedica un capitolo a testa a queste famiglie.

Applicazioni pratiche

La ricerca ANN è oggi un mattone trasversale, non una tecnica di nicchia.

Il caso d’uso che l’ha portata al centro è RAG (retrieval-augmented generation): ogni sistema che recupera documenti per nutrire il contesto di un LLM esegue, nel suo cuore, una query ANN su un indice di embedding. È il consumatore numero uno della ricerca vettoriale; la wiki gli dedica il capitolo rag-base (in preparazione).

Strettamente imparentata è la memoria a lungo termine degli agenti. Un agente che accumula esperienze, note, fatti su un utente li conserva come embedding; “ricordare qualcosa di rilevante” significa fare una query ANN su quella memoria.

A differenza di un corpus RAG, spesso statico, la memoria di un agente cresce in continuazione: ogni interazione vi aggiunge vettori. Questo rende il costo di aggiornamento dell’indice, non solo quello di query, un fattore di progettazione. Dettaglio nel capitolo memoria-agentica (in preparazione).

Fuori dal mondo LLM la ricerca ANN ha un raggio d’azione ampio. Alimenta i sistemi di raccomandazione, dove utenti e prodotti sono vettori e “item simili a questo” è una query k-NN. Sostiene la deduplicazione e il rilevamento di quasi-duplicati, in cui documenti o immagini quasi identici sono vettori a distanza sotto una soglia.

È il cuore della visual search e della reverse image search — l’applicazione storica, su descrittori SIFT/GIST. E serve a costruire il k-NN graph, un grafo dei vicini usato come passo preliminare per clustering, visualizzazione e apprendimento semi-supervisionato.

A impacchettare questi algoritmi dietro un’API ci sono i vector database. FAISS di Meta è la cassetta degli attrezzi di riferimento — più una libreria che un database. Milvus, Weaviate e Qdrant sono database vettoriali dedicati, con persistenza, indicizzazione, filtri sui metadati. Pinecone è un servizio gestito. pgvector è un’estensione che porta la ricerca vettoriale dentro PostgreSQL, accanto ai dati relazionali già esistenti.

Quasi tutti, sotto il cofano, usano HNSW o IVF con product quantization — gli stessi algoritmi della mini-serie. Capire questo capitolo significa capire cosa fa davvero un vector database quando lo si interroga, e perché le sue manopole controllano proprio il triangolo recall-latenza-memoria. Quando un vector database espone un parametro come ef_search o nprobe, non sta offrendo una configurazione esoterica: sta esponendo direttamente il punto sulla frontiera di Pareto. La wiki tratta i vector database come categoria di prodotto nel capitolo vector-databases (in preparazione).

Quando non serve un indice ANN

Una nota controcorrente, ma utile. La ricerca approssimata è la risposta giusta per dataset grandi; non è la risposta giusta sempre. Un indice ANN aggiunge codice, un tempo di build, una struttura da tenere in memoria e almeno un parametro di recall da governare. Tutto questo si ripaga solo se il brute-force non regge.

Per dataset piccoli — diciamo 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 un indice ANN qui è prematura ottimizzazione: si paga complessità per un guadagno che nessuno percepisce, e si rischiano bug sottili sul recall.

La regola pratica è semplice: parti dal brute-force, misura la latenza reale sul tuo traffico, e passa a un indice ANN solo quando quella misura sfora il budget. La domanda non è “qual è l’algoritmo più sofisticato”, ma “il più semplice basta?”. Spesso, sotto una certa scala, la risposta è sì.

Dove si rompe

La ricerca approssimata è un compromesso, e ogni compromesso ha un lato che cede. Vale la pena conoscerlo prima di affidarvi un sistema in produzione.

“Approssimato” non significa “distanza sbagliata”. È il fraintendimento più comune. Un indice ANN non calcola distanze imprecise — le distanze sui candidati che raccoglie sono esatte, o nel caso della quantizzazione stimate con un errore di precisione noto e controllato.

L’approssimazione sta altrove: l’indice può non vedere alcuni veri vicini, perché la fase di restringimento li ha lasciati fuori dai candidati. L’errore è di omissione, non di calcolo, e si misura come recall, non come scarto numerico sulle distanze. Capire questa distinzione cambia il modo di debuggare: se le risposte sono cattive, non si controlla la formula della distanza, si controlla se la fase di raccolta candidati sta tagliando troppo.

Recall alto non significa risposte buone. Il recall@k misura la fedeltà dell’indice al brute-force. Se gli embedding sono di scarsa qualità — il modello non cattura bene la similarità semantica del dominio — un recall di $1{,}0$ recupera comunque i documenti sbagliati, perfettamente fedele a un brute-force a sua volta sbagliato.

La ricerca ANN risolve “trova i vicini in fretta”; non risolve “i vicini sono semanticamente quelli giusti”. Quel secondo problema sta a monte, nella scelta del modello di embedding. Confondere i due porta a debuggare l’indice quando il difetto è nei vettori — un errore diagnostico che fa perdere giornate.

Le distribuzioni difficili degradano il recall in modo non uniforme. I metodi ANN danno il loro recall medio su dati “ben distribuiti”. Su dati molto sbilanciati — cluster densissimi accanto a regioni quasi vuote, oppure molti vettori quasi identici — alcune query stanno in zone dove l’indice fa fatica, e il recall su quelle query crolla ben sotto la media.

Una media di $0{,}95$ può nascondere una coda di query servite male. Le query fuori distribuzione, su regioni dello spazio mai viste in fase di build, sono particolarmente esposte. Conviene guardare non solo il recall medio ma anche i percentili bassi: il caso peggiore racconta più della media.

Aggiornamenti e cancellazioni non sono gratis. Quasi tutti i benchmark misurano indici statici: costruisci una volta, interroghi tante volte. La realtà è spesso dinamica: arrivano vettori nuovi, altri vanno cancellati.

Alcuni indici inseriscono bene ma cancellano male — lasciano “lapidi”, segnaposto dei punti rimossi che vanno periodicamente compattati; altri richiedono una ricostruzione completa dell’indice. Per una knowledge base che cambia ogni ora, il costo di build e di aggiornamento conta quanto la latenza di query, e i benchmark che lo ignorano danno un quadro ottimistico. Prima di scegliere un indice, vale la pena chiedersi non solo “quanto è veloce a interrogare” ma “quanto è veloce a cambiare”.

Non esiste l’algoritmo migliore. È implicito nella frontiera di Pareto, ma va detto esplicitamente perché è una trappola frequente. Chi cerca “il miglior algoritmo ANN” pone una domanda mal formata.

HNSW domina nella regione ad alto recall ma divora memoria; le tecniche a quantizzazione dominano quando la memoria è stretta ma faticano a recall altissimi; LSH ha le garanzie teoriche più forti ma in pratica viene spesso battuto sui benchmark empirici. La risposta giusta dipende da $N$, da $d$, dal recall richiesto, dal budget di RAM, dal pattern di aggiornamento. Va misurata sul proprio caso, non importata da una classifica generica.

La maledizione della dimensionalità non sparisce davvero. Il titolo del paper fondativo dice “towards removing” — verso la rimozione, non “rimossa”. L’approssimazione abbassa enormemente il costo, ma non azzera il fenomeno.

A parità di recall i metodi ANN faticano di più man mano che $d$ cresce e, soprattutto, man mano che cresce la dimensionalità intrinseca dei dati — quanto sono realmente complessi, al di là del numero nominale di coordinate. Per dati a dimensionalità intrinseca molto alta, anche l’ANN paga un prezzo. Una mossa ortogonale e spesso efficace è ridurre la dimensione a monte, con tecniche come la PCA, prima ancora di costruire l’indice.

Il filtraggio sui metadati incrina le garanzie. 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”. Filtrare per metadati combinato con la ricerca vettoriale è un problema noto come filtered ANN, e non è gratis. Filtrare prima significa cercare in un sottoinsieme su cui l’indice non è stato costruito; filtrare dopo significa che, se il filtro è selettivo, dei vicini recuperati ne sopravvivono pochissimi e il recall effettivo crolla. Esistono indici progettati apposta per i filtri — Filtered-DiskANN ne è un esempio — ma la lezione per questo capitolo è che il “trova i vicini” pulito di cui abbiamo parlato è un caso ideale; la produzione lo complica.

Il top-k dell’indice non è il top-k finale. Un pattern diffuso, e una trappola se non lo si conosce, è l’oversampling con rerank: l’indice ANN recupera molti più candidati del necessario — 100 invece dei 10 richiesti — e poi un passo successivo, spesso con un modello più costoso e accurato, riordina quei 100 e ne tiene 10.

In questo schema il recall dell’indice ANN non deve essere altissimo: deve solo garantire che i 10 veri vicini siano da qualche parte tra i 100 candidati. Chi dimensiona l’indice ignorando il rerank a valle finisce per spendere troppo in recall dove non serve. La ricerca ANN è quasi sempre un anello di una catena, non l’anello finale.

Collegamenti

• Norme e distanze — $L1$, $L2$ e coseno: le metriche di distanza su cui ogni ricerca vettoriale opera, e il perché della loro scelta.
• Prodotto scalare — il prodotto interno come misura di somiglianza, base del maximum inner product search e quindi di ScaNN.
• Embedding: spazi e direzioni semantiche — da dove vengono i vettori che si indicizzano, e perché “vicino” finisce per voler dire “semanticamente simile”.
• La maledizione della dimensionalità — il fenomeno geometrico, trattato a sé, che rende impraticabile la ricerca esatta in alta dimensione.
• Complessità: Big-O — il linguaggio per dire perché $O(N \cdot d)$ per query non scala e cosa significa “sublineare in $N$”.
• Heap e priority queue — la struttura con cui si mantiene il top-k dei candidati, identica nel brute-force e nella fase di selezione di ogni indice ANN.
• ann-hnsw (in preparazione) — la famiglia a grafo: HNSW in dettaglio, il primo capitolo che apre la scatola dei metodi.
• ann-ivf-pq (in preparazione) — la famiglia a partizionamento e quantizzazione: inverted file e product quantization.
• ann-scann-diskann (in preparazione) — ScaNN per MIPS e DiskANN per indici che vivono su SSD.
• lsh (in preparazione) — la famiglia a hashing: locality-sensitive hashing e le sue garanzie teoriche.
• rag-base (in preparazione) — il consumatore principale della ricerca vettoriale: come il retrieval alimenta il contesto di un LLM.
• memoria-agentica (in preparazione) — la memoria semantica di un agente vista come un indice ANN che cresce nel tempo.
• vector-databases (in preparazione) — i prodotti che impacchettano questi algoritmi dietro un’API operativa.

Per andare oltre

• Har-Peled, Indyk, Motwani, Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality (Theory of Computing, vol. 8, 2012; versioni originali STOC 1998 e FOCS 2001). Il paper che definisce formalmente il c-approximate nearest neighbor e introduce il locality-sensitive hashing. Disponibile su theoryofcomputing.org.
• Aumüller, Bernhardsson, Faithfull, ANN-Benchmarks — la suite di benchmark di riferimento, con risultati interattivi recall-QPS su decine di algoritmi e dataset. ann-benchmarks.com.
• Johnson, Douze, Jégou, Billion-scale similarity search with GPUs (arXiv:1702.08734, 2017; IEEE Transactions on Big Data, 2019). Il paper dietro FAISS, riferimento sulla ricerca su scala da miliardi di vettori.
• Jégou, Douze, Schmid, Product Quantization for Nearest Neighbor Search (IEEE TPAMI 33(1), 2011). Introduce la product quantization; lettura propedeutica al capitolo ann-ivf-pq.
• Documentazione di FAISS (faiss.ai), in particolare la guida “Guidelines to choose an index”: un percorso pratico per scegliere il tipo di indice in base a $N$, memoria e requisito di recall.