ScaNN e DiskANN: quantizzare per il ranking, indicizzare oltre la RAM

Perché due idee — spendere i byte di compressione dove cambiano il ranking, e tenere il grafo su un disco economico invece che in memoria cara — sono ciò che porta la ricerca vettoriale dal benchmark alla produzione su miliardi di vettori.

Perché questo capitolo

La mini-serie ANN ha costruito un vocabolario. Approximate nearest neighbor: il problema ha posto la domanda — trovare i vicini di un vettore in un dataset enorme senza confrontarli tutti — e ha disegnato la frontiera di Pareto fra recall e velocità. HNSW ha mostrato la famiglia a grafo, la più forte su quella frontiera quando i vettori stanno comodi in RAM. IVF e product quantization ha mostrato la famiglia a partizionamento e quantizzazione, quella che comprime per entrare in un budget di memoria. Restano due domande che le idee di base non chiudono, e questo capitolo le affronta.

La prima domanda è sottile. La product quantization sceglie i suoi codici minimizzando l’errore di ricostruzione: la distanza media fra ogni vettore e la sua versione compressa. Ma la ricerca vettoriale moderna non ordina i risultati per distanza euclidea — li ordina per prodotto interno, perché gli embedding di un modello si confrontano così. Minimizzare l’errore di ricostruzione e minimizzare l’errore sul prodotto interno non sono la stessa cosa. C’è uno scollamento fra ciò che PQ ottimizza e ciò che conta davvero per il ranking. ScaNN, il sistema di Google, parte proprio da questo scollamento e lo chiude.

La seconda domanda è di scala. HNSW e IVFPQ assumono entrambi che qualcosa stia in RAM: HNSW i vettori grezzi più il grafo, IVFPQ almeno i codici compressi. Un miliardo di embedding a 768 dimensioni in virgola mobile a 32 bit occupa circa 3 terabyte da non compresso. Su una macchina ordinaria non entra. DiskANN, il sistema di Microsoft, risponde con una mossa diversa: mette il grafo e i vettori esatti su un SSD economico, tiene in RAM solo una versione compressa usata come bussola, e naviga l’indice con poche letture mirate da disco. È ciò che rende possibile un indice da un miliardo di vettori su una singola macchina con 64 GB di RAM.

Queste due domande non sono curiosità accademiche. La prima decide quanto recall ottieni a parità di memoria spesa — e in un sistema RAG con un budget fisso, ogni punto di recall perso sono risposte sbagliate per l’utente. La seconda decide se il tuo indice gira su una macchina o su una flotta — e questo è un fattore di decine sul costo dell’infrastruttura. Sono entrambe domande da cui dipende, molto concretamente, se un sistema di retrieval è sostenibile o no. Le due risposte chiudono la serie e completano la mappa: dopo questo capitolo, le quattro grandi famiglie ANN sono tutte sul tavolo, e con esse i sei assi lungo cui si sceglie un indice.

Contesto

I due sistemi nascono a un anno di distanza, in due laboratori industriali, da due paper che oggi sono riferimenti standard del settore.

DiskANN viene da Microsoft Research, dal gruppo in India che portava avanti il progetto Akupara sulla ricerca semantica su larga scala. Il paper è DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node, di Suhas Jayaram Subramanya, Devvrit, Rohan Kadekodi, Ravishankar Krishnaswamy e Harsha Vardhan Simhadri, presentato a NeurIPS 2019, la principale conferenza di machine learning. Subramanya era ricercatore a Microsoft Research India e poi dottorando alla Carnegie Mellon University. Nel sistema di review di NeurIPS lo stesso lavoro compare anche con il titolo provvisorio “Rand-NSG”, un dettaglio utile a chi cerca il preprint. Il risultato dichiarato era forte: indicizzare un miliardo di punti su una singola workstation con 64 GB di RAM e un SSD economico, servendo oltre 5000 query al secondo con latenza media sotto i 3 millisecondi e oltre il 95% di recall sul dataset SIFT1B — un dataset standard di un miliardo di descrittori SIFT, usato come prova del nove per i metodi billion-scale. Gli algoritmi billion-scale con un footprint di memoria simile, all’epoca, si fermavano intorno al 50% di recall.

Vale la pena soffermarsi sul perché quel risultato fece notizia. Prima di DiskANN, l’opzione per un indice da un miliardo di vettori era una di due: o una flotta di macchine con molta RAM, sharded e costosa; oppure un indice su disco con un recall mediocre, intorno al 50%, troppo basso per essere utile. DiskANN ha rotto questo dilemma — un miliardo di punti, una macchina sola, recall sopra il 95%, latenza di pochi millisecondi — e ha mostrato che “indice su disco” e “alta qualità” non erano alternative incompatibili. Era una combinazione che la comunità riteneva fuori portata, ed è la ragione per cui DiskANN è diventato rapidamente un riferimento.

ScaNN — il nome sta per Scalable Nearest Neighbors — viene da Google Research. Il paper è Accelerating Large-Scale Inference with Anisotropic Vector Quantization, di Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern e Sanjiv Kumar, presentato a ICML 2020 (la International Conference on Machine Learning); il preprint su arXiv è dell’agosto 2019. La libreria open source omonima è stata annunciata sul blog di Google Research nel luglio 2020. Per anni ScaNN è stato il sistema da battere su ann-benchmarks.com, il benchmark pubblico standard per i metodi ANN: sul dataset glove-100-angular gli autori riportavano circa il doppio del throughput del concorrente più vicino a parità di accuratezza.

Il titolo del paper merita una nota, perché rivela l’inquadramento originale. Non parla di “ricerca”, parla di “inferenza su larga scala”: Accelerating Large-Scale Inference. Il problema, per gli autori, era quello dei sistemi di recommendation di Google — un modello produce un embedding-query e bisogna trovare, fra milioni di embedding-prodotto, quelli col prodotto interno più alto. Quel passo di retrieval è, a tutti gli effetti, parte dell’inferenza del sistema di recommendation, e il suo costo conta. La cornice MIPS — maximum inner product search — non è un dettaglio: è il problema da cui ScaNN nasce, ed è la ragione per cui ottimizza il prodotto interno e non la distanza euclidea.

Vale la pena fissare la cronologia rispetto al resto della mini-serie. La product quantization è del 2011, HNSW del 2016, DiskANN del 2019, ScaNN del 2020. Come ann-intro insisteva, tutta questa tecnologia nasce e matura prima dell’esplosione degli LLM. Era ricerca su descrittori di immagini e su sistemi di recommendation, non su RAG. Il caso d’uso di massa — retrieval per modelli linguistici, memoria degli agenti, vector database — arriva dopo, quando produrre embedding di buona qualità per testo arbitrario diventa facile. ScaNN e DiskANN sono algoritmi da benchmark che hanno passato la prova della produzione su scala enorme: torneremo nella sezione applicazioni sui prodotti che li impacchettano.

Conviene anche fissare da dove arrivano le radici tecniche dei due sistemi. ScaNN si appoggia sulla product quantization del 2011 e sull’inverted file: tutta la pipeline partizionamento-scoring-rerank è quella di IVFPQ, e il contributo di ScaNN è interno a quella struttura. DiskANN si appoggia invece sui grafi di prossimità navigabili — la famiglia di HNSW e di NSG (Navigating Spreading-out Graph, un grafo ANN del 2019) — e il contributo di DiskANN è un grafo nuovo, Vamana, pensato perché un grafo di quel tipo possa vivere su disco. Due sistemi, due lignaggi distinti, ciascuno radicato in una delle due grandi famiglie della mini-serie.

Una nota sulla classe di affermazione, perché in questo capitolo si collegano sistemi diversi. ScaNN sta nella stessa famiglia di IVF e PQ — partizionamento più quantizzazione più rerank — e ne è un raffinamento tecnico documentato: il paper di Guo et al. costruisce esplicitamente sopra la product quantization. Questa è una filiazione. DiskANN e HNSW sono invece entrambi grafi di prossimità, ma DiskANN non discende da HNSW: il suo grafo Vamana è progettato in modo diverso, per un vincolo diverso. Il loro rapporto è un confronto fra parenti, non una discendenza. Teniamo distinte le due cose lungo tutto il capitolo.

L’intuizione

I due sistemi risolvono problemi diversi, quindi vanno avvicinati con intuizioni separate. Un angolo per ciascuno, prima di qualunque formula.

ScaNN, angolo economico — spendere i byte dove cambiano il ranking

Immagina di avere un budget fisso: puoi spendere, diciamo, otto byte per descrivere ogni vettore del tuo dataset. La product quantization classica, vista in ann-ivf-pq, spende quegli otto byte per fare la fotografia più fedele possibile del vettore: sceglie i suoi codici in modo che il vettore ricostruito a partire dai codici assomigli il più possibile all’originale. È un obiettivo ragionevole, ma è l’obiettivo sbagliato.

Perché sbagliato? Perché tu non vuoi una buona fotografia del vettore. Vuoi sapere bene una cosa sola: dato un vettore-query, quali sono i pochi vettori del dataset che hanno il prodotto interno più alto con quella query — i candidati che finiranno in cima alla lista dei risultati. Tutto ciò che non cambia quel ranking è dettaglio sprecato.

ScaNN parte da qui. Prende lo stesso budget di byte e lo spende in modo diverso: non per ricostruire fedelmente il vettore, ma per preservare con precisione il suo prodotto interno con le query che lo troverebbero rilevante. Accetta — deliberatamente — una fotografia più sfocata in cambio di un ranking più accurato sui top candidati. Stesso budget, speso dove conta. Il nome tecnico di questa idea è anisotropic quantization, quantizzazione anisotropa, ed è il cuore del sistema. “Anisotropo” significa: che tratta le direzioni in modo diverso. La meccanica chiarirà quali direzioni e perché.

ScaNN, angolo geometrico — un errore che si vede e uno che non si vede

C’è un secondo modo di guardarci, più geometrico, e aiuta a vedere perché l’idea funziona invece di solo che funziona. Disegna un vettore-datapoint $x$ come una freccia. Quantizzarlo significa sostituirlo con una freccia leggermente diversa: la punta si sposta. Lo spostamento della punta può andare in due direzioni. Può scivolare lungo la freccia — la freccia si allunga o si accorcia — oppure può scivolare di lato — la freccia ruota un po’.

Ora arriva una query, anch’essa una freccia, e il prodotto interno con $x$ misura, in sostanza, quanto $x$ “si sporge” nella direzione della query. Una query che troverebbe $x$ rilevante punta più o meno dove punta $x$ . Pensa allora a cosa fa lo spostamento della punta. Se la punta è scivolata lungo la freccia, la lunghezza di $x$ nella direzione della query è cambiata: il prodotto interno si sposta in modo visibile. Se la punta è scivolata di lato, $x$ continua a portarsi avanti nella direzione della query quasi quanto prima: il prodotto interno cambia pochissimo. Lo stesso spostamento, la stessa “quantità di errore”, produce un danno grande o un danno trascurabile a seconda di dove va. ScaNN, quando sceglie i codici, evita gli spostamenti del primo tipo e tollera quelli del secondo. È la stessa idea dell’angolo economico, ma vista come geometria invece che come budget.

DiskANN, angolo della gerarchia di memoria — bussola in RAM, mappa su disco

Un computer ha una gerarchia di memorie. La RAM è veloce — leggere un dato costa circa 100 nanosecondi — ma è cara e limitata. L’SSD è lento per gli accessi sparsi — leggere una pagina da 4 kilobyte a caso costa circa 20.000 nanosecondi, duecento volte tanto — ma è economico e capiente. HNSW vive interamente nel piano caro: vuole l’intero grafo e tutti i vettori in RAM.

DiskANN si chiede una cosa semplice: cosa deve davvero stare nel piano caro? Per decidere dove andare durante una ricerca su grafo non serve la mappa dettagliata di ogni strada. Basta una bussola: una stima approssimata di quale nodo è più vicino alla meta. La bussola può essere imprecisa, perché la useremo solo per orientarci, e poi confermeremo con la mappa vera.

Allora: DiskANN tiene nel piano caro, la RAM, solo la bussola — una versione compressa di tutti i vettori, abbastanza piccola da entrare anche a un miliardo di punti. E mette nel piano economico, l’SSD, la mappa dettagliata: il grafo completo dei collegamenti e i vettori esatti. Naviga la mappa con poche letture mirate, una per ogni passo della camminata sul grafo. È esattamente la logica di una cache: tieni vicino e veloce ciò che serve a decidere, lascia lontano e lento ciò che serve solo a confermare. La meccanica mostra come si fa concretamente.

DiskANN, angolo del numero di letture — meno passi, meno accessi al disco

L’angolo della gerarchia di memoria spiega cosa va in RAM e cosa su disco. Ma c’è un secondo vincolo, e spiega perché il grafo deve essere fatto in un certo modo. Una lettura random da SSD è duecento volte più lenta di una lettura dalla RAM. Se ogni passo della camminata sul grafo costa una lettura da disco, allora il costo totale di una query è, in prima approssimazione, il numero di passi moltiplicato per quel costo. Ridurre la latenza significa, prima di tutto, ridurre i passi.

Qui sta la ragione per cui DiskANN non può semplicemente prendere HNSW e metterlo su disco. Un grafo a cui interessa solo la qualità della ricerca in RAM può permettersi di essere “profondo”, di richiedere molti passi, perché ogni passo è quasi gratis. Un grafo che vive su disco no: ogni passo è una lettura costosa, e un grafo profondo diventa lento in modo intollerabile. DiskANN ha bisogno di un grafo con il diametro più piccolo possibile — il minor numero di passi per andare da un punto qualsiasi alla meta. Tutto il design di Vamana, e in particolare il parametro alpha che vedremo nella meccanica, esiste per questo: comprimere il numero di passi, perché ogni passo risparmiato è una lettura da disco risparmiata.

La meccanica

ScaNN: perché la direzione dell’errore conta

Partiamo dal problema che ScaNN chiama MIPS, maximum inner product search: data una query $q$ , trovare i datapoint $x$ del dataset che massimizzano il prodotto interno $\langle q, x \rangle$ . Il prodotto interno, trattato nella wiki nel capitolo prodotto scalare, misura quanto due vettori sono allineati: è la base con cui si confrontano gli embedding.

Perché MIPS e non distanza euclidea? Perché gli embedding di un modello — il testo, le immagini trasformati in vettori — codificano la similarità semantica nell’allineamento delle direzioni, e il prodotto interno misura proprio quello. Spesso i vettori vengono normalizzati a lunghezza unitaria, e in quel caso massimizzare il prodotto interno equivale a minimizzare la distanza euclidea: i due problemi coincidono. Ma il modo naturale di pensare il ranking degli embedding resta il prodotto interno, ed è la grandezza che ScaNN sceglie di proteggere.

Quando comprimiamo un datapoint $x$ con la quantizzazione, lo sostituiamo con una versione approssimata $\tilde{x}$ . La differenza $r = x - \tilde{x}$ è il residuo, l’errore di quantizzazione. PQ classico sceglie i codici per rendere $r$ piccolo in media — minimizza $\lVert r \rVert^2$ , la lunghezza al quadrato del residuo. Tutte le direzioni dell’errore pesano uguale: è una scelta isotropa.

L’intuizione di ScaNN è che non tutte le direzioni del residuo fanno lo stesso danno. Scomponiamo $r$ in due parti rispetto alla direzione del datapoint originale $x$ :

$r = r_{\parallel} + r_{\perp}$

In parole povere: $r_{\parallel}$ è la componente del residuo parallela a $x$ , cioè quella che allunga o accorcia $x$ lungo la sua stessa direzione; $r_{\perp}$ è la componente ortogonale, perpendicolare a $x$ , quella che lo fa deviare di lato. La decomposizione di un vettore in componente parallela e ortogonale rispetto a una direzione è la stessa proiezione vista in norme e distanze.

Ora la domanda: quale delle due componenti distorce di più il prodotto interno $\langle q, x \rangle$ per le query $q$ che troverebbero $x$ rilevante? Una query rilevante per $x$ è, per definizione, una query allineata con $x$ — punta più o meno nella sua stessa direzione. La componente $r_{\parallel}$ , essendo anch’essa lungo la direzione di $x$ , si proietta quasi per intero su una query allineata: il suo errore entra quasi tutto nel prodotto interno stimato. La componente $r_{\perp}$ , perpendicolare a $x$ , si proietta poco o niente su una query allineata: il suo errore si scarica in larga parte fuori dal prodotto interno che ci interessa.

La conclusione è netta: l’errore parallelo danneggia il ranking dei top candidati molto più dell’errore ortogonale. ScaNN trasforma questa osservazione in una loss di quantizzazione anisotropa: invece di minimizzare $\lVert r \rVert^2$ , minimizza una somma pesata in cui la componente parallela ha un peso maggiore di quella ortogonale. In forma schematica:

$\text{loss}(x, \tilde{x}) = h_{\parallel} \cdot \lVert r_{\parallel} \rVert^2 + h_{\perp} \cdot \lVert r_{\perp} \rVert^2 \qquad \text{con } h_{\parallel} > h_{\perp}$

dove $h_{\parallel}$ e $h_{\perp}$ sono i due pesi. In parole povere, questa loss dice: “sbaglia pure di più in media, ma non sbagliare lungo la direzione del datapoint, perché è lì che il prodotto interno si rovina”. I valori esatti dei pesi, nel paper, derivano da un’assunzione statistica naturale — le query distribuite in modo isotropo e l’interesse concentrato sui candidati ad alto prodotto interno. Il punto da interiorizzare non è la formula esatta, è il baratto: ScaNN accetta consapevolmente un errore di ricostruzione medio più alto in cambio di un errore sul prodotto interno dei top candidati più basso.

Si noti che con $h_{\parallel} = h_{\perp}$ la loss anisotropa collassa esattamente nella loss isotropa di PQ classico: pesi uguali su parallelo e ortogonale significano $\lVert r \rVert^2$ e basta. ScaNN, in questo senso, non rimpiazza PQ — lo generalizza. PQ classico è il caso particolare in cui non si distinguono le direzioni; ScaNN aggiunge un grado di libertà, il rapporto fra i due pesi, e lo regola in favore della direzione che conta per il ranking. È il senso preciso in cui “raffinamento” è la parola giusta: l’idea vecchia è dentro la nuova, come caso limite.

ScaNN: la pipeline a tre fasi

Con la loss anisotropa in mano, ScaNN la inserisce in una pipeline che è la stessa famiglia di IVF+PQ: partizionare, comprimere, riordinare. Tre fasi, le ultime due opzionali a seconda della scala.

Fase 1 — partizionamento. In fase di build lo spazio è diviso in partizioni, le foglie di un albero. A query time si selezionano solo le num_leaves_to_search partizioni più vicine alla query, e solo i vettori che vi cadono passano alla fase successiva. È esattamente il ruolo di IVF: ridurre quanti vettori si esaminano. La documentazione del progetto suggerisce di impostare num_leaves intorno alla radice quadrata del numero di datapoint.

Questa fase è opzionale, e il motivo è istruttivo. Per un dataset piccolo non c’è niente da potare: scorare tutti i vettori è già veloce, e un partizionamento aggiungerebbe solo il rischio di scartare la foglia che conteneva il vero vicino. Il partizionamento serve quando il numero di datapoint è grande abbastanza che esaminarli tutti, anche con lo scoring SIMD, costa troppo. È la stessa gradualità di ann-intro: si paga la complessità di un indice solo quando la scala lo impone, non prima.

Fase 2 — scoring. Si calcolano le distanze sui candidati sopravvissuti. Due modi. Il brute-force calcola la distanza esatta (con una compressione opzionale a 8 bit per dimensione). L’asymmetric hashing, abbreviato AH, è l’approccio veloce: la query resta in piena precisione, mentre i vettori del database sono confrontati nella loro forma quantizzata. La parola “asimmetrico” significa proprio questo — query precisa contro database compresso. È qui che si applica la quantizzazione anisotropa: i codici dei vettori del database sono quelli scelti dalla loss score-aware. AH offre il miglior compromesso velocità/accuratezza salvo quando serve un’accuratezza quasi perfetta.

Fase 3 — rescoring. Lo scoring approssimato produce i migliori $k'$ candidati. ScaNN ne ricalcola la distanza in modo accurato, sui vettori non compressi, e da quei $k'$ seleziona i top $k$ finali. Il parametro reordering_num_neighbors è proprio $k'$ , e deve essere maggiore di $k$ . È lo stesso passo di rerank che ann-intro descriveva come ultimo anello di quasi ogni pipeline ANN: l’indice approssimato recupera un insieme largo, un calcolo esatto riordina solo quello.

La logica del rescoring merita una riga, perché spiega perché ScaNN può permettersi una quantizzazione aggressiva. Lo scoring approssimato non deve azzeccare il ranking: deve solo garantire che i veri top $k$ siano da qualche parte nei $k'$ candidati che passano al rescoring. Finché è così, il calcolo esatto della fase 3 li riordina correttamente. La quantizzazione anisotropa serve esattamente a questo — a non perdere i candidati buoni nel passaggio approssimato — e il rescoring ripulisce il ranking. Le due cose insieme: quantizzazione score-aware per non perdere nessuno, rescoring esatto per ordinare bene i pochi rimasti.

La struttura, dunque, non è nuova: è IVF + quantizzazione + rerank. L’innovazione di ScaNN sta in due punti dentro questa struttura — la loss di quantizzazione resa score-aware, e un’implementazione molto curata.

C’è un punto che vale la pena chiarire, perché è il fraintendimento più comune. ScaNN non sostituisce PQ con qualcosa di diverso: usa ancora la product quantization, lo stesso meccanismo di codebook per blocchi di ann-ivf-pq. Cambia solo il criterio con cui i codebook vengono addestrati. PQ classico addestra ogni codebook con un k-means standard, che minimizza la distanza media fra i vettori e i loro centroidi — l’errore di ricostruzione. ScaNN addestra gli stessi codebook con un k-means modificato, la cui funzione obiettivo è la loss anisotropa. Il risultato è ancora un insieme di centroidi, ancora indicizzato da codici a 4 bit, ancora consultabile via lookup table. La differenza vive tutta nella fase di training: a parità di forma dell’indice, i centroidi finiscono in posizioni diverse — posizioni scelte per proteggere il prodotto interno invece che la ricostruzione. Questo è il senso preciso in cui ScaNN è una filiazione di PQ, non un metodo alternativo.

ScaNN: 4-bit PQ e SIMD

Il secondo punto merita un paragrafo, perché senza di esso il fattore due sui benchmark non si spiega. Ricordiamo come PQ calcola una distanza, da ann-ivf-pq: il vettore è spezzato in blocchi, ogni blocco è codificato dall’indice di un centroide, e la distanza fra query e datapoint si somma blocco per blocco leggendo da una lookup table — una tabella che, per ogni blocco, dà la distanza parziale fra la query e ciascun centroide possibile di quel blocco. Il costo di scorare un candidato è dunque una sequenza di accessi a quella tabella, uno per blocco.

ScaNN usa codebook con 16 centroidi per blocco — cioè codici a 4 bit, dato che $2^4 = 16$ . La scelta non è solo questione di compressione. Sedici valori entrano interi in un registro vettoriale dei processori moderni, e la riga della lookup table di un blocco — 16 distanze parziali — può quindi stare dentro un registro. Consultarla per molti candidati in una volta diventa una singola istruzione di shuffle vettoriale: sugli x86 moderni, istruzioni della famiglia VPSHUFB, che riordinano i byte di un registro secondo un indice anch’esso in un registro.

La differenza pratica è grande. Con codebook più grandi — i 256 centroidi tipici di PQ classico, codici a 8 bit — la tabella non sta in un registro, e consultarla significa accessi sparsi alla RAM: lenti, imprevedibili, ostili alla cache. Con 16 centroidi la tabella vive nei registri e lo scoring di molti candidati diventa una manciata di istruzioni SIMD — single instruction, multiple data, una sola istruzione che opera su più valori in parallelo. La larghezza di 4 bit è scelta dall’hardware, non dalla teoria: è la più grande che rende la tabella SIMD-friendly. È la combinazione delle tre cose — quantizzazione anisotropa, PQ a 4 bit, scoring SIMD — a produrre il vantaggio di ScaNN. Non una sola idea, ma tre che si incastrano: la prima decide dove mettere l’errore, le altre due rendono veloce il calcolo che ne segue.

DiskANN: il grafo Vamana e il parametro alpha

Passiamo a DiskANN. Il suo indice è un grafo di prossimità chiamato Vamana. La prima differenza con HNSW va detta subito: HNSW è gerarchico, impila più livelli di grafo, con i livelli alti radi che fanno da scorciatoia. Vamana è un unico grafo, un solo livello. Niente gerarchia.

Senza la gerarchia, come fa Vamana a restare navigabile in pochi passi? Con un parametro, alpha, che governa la costruzione del grafo. Vediamo la costruzione in tre passi.

costruzione di Vamana (schematica):

1. inizializza: ogni nodo riceve R archi uscenti casuali
   (R = grado massimo del grafo)

2. per ogni nodo v del dataset:
     a. esegui GreedySearch verso v partendo dal medoide,
        raccogliendo l'insieme dei nodi visitati come candidati
     b. RobustPrune(v, candidati, R, alpha):
        scegli al più R archi uscenti per v secondo la regola alpha

3. ripeti il passo 2 due volte: prima con alpha = 1,
   poi con l'alpha scelto (> 1)

Prima di RobustPrune c’è GreedySearch, e vale la pena spendere due righe su cosa fa, perché è la stessa routine usata sia in costruzione sia a query time. È una camminata avida sul grafo:

GreedySearch(grafo, ingresso, target, L):
    visitati = {}                 # nodi già espansi
    frontiera = { ingresso }      # candidati da espandere, ordinati per distanza dal target
    finché frontiera ha un nodo non visitato:
        n = nodo non visitato più vicino al target nella frontiera
        marca n come visitato
        per ogni vicino w di n nel grafo:
            aggiungi w alla frontiera
        tieni nella frontiera solo i L nodi più vicini al target
    ritorna i nodi più vicini trovati, e l'insieme visitati

In parole: parte da un nodo di ingresso, espande sempre il candidato più vicino al target, e mantiene una frontiera larga L dei migliori candidati visti finora. Il parametro L controlla quanto larga tenere quella frontiera — più è larga, più la ricerca è accurata e lenta. A query time GreedySearch è la ricerca; in costruzione serve a raccogliere, per ogni nodo, l’insieme dei nodi che incontra lungo il cammino — ed è quell’insieme visitati a diventare la lista di candidati passata a RobustPrune.

Il cuore della costruzione è poi RobustPrune, e dentro RobustPrune la regola che usa alpha. La GreedySearch ha prodotto per ogni nodo $v$ un insieme di candidati a diventare suoi vicini. Da quei candidati ne vanno tenuti al più $R$ . La regola di potatura ragiona così: un arco diretto $v \to p$ è ridondante se esiste un altro vicino già scelto $p'$ tale che andare prima a $p'$ è “abbastanza buono”. Formalmente, l’arco $v \to p$ viene scartato se esiste $p'$ con

$\text{dist}(v, p') \cdot \alpha \le \text{dist}(v, p)$

In parole povere: se da $v$ posso raggiungere $p'$ , e $p'$ è più vicino a $v$ di quanto lo sia $p$ (con un margine regolato da alpha), allora l’arco verso $p$ è superfluo — ci arrivo passando per $p'$ .

Qui entra alpha. Con $\alpha = 1$ la regola è severa: ogni arco per cui esiste un detour non peggiore viene tagliato. Con $\alpha > 1$ — tipicamente fra 1.0 e 1.5 — la regola lascia uno slack: un arco sopravvive anche se esiste un detour, purché il detour non sia molto migliore. L’effetto pratico è tenere in vita più archi long-range, archi lunghi che scavalcano grandi distanze nel grafo.

Perché gli archi lunghi contano? Perché accorciano il diametro del grafo — il numero di passi necessari per andare da un nodo qualsiasi a un altro. Con un buon alpha il diametro di Vamana risulta circa logaritmico (in base alpha) nel numero di nodi: poche decine di passi anche per un miliardo di punti. HNSW e NSG, l’altro grafo di prossimità da cui DiskANN prende ispirazione, non hanno questo parametro — usano implicitamente $\alpha = 1$ — e HNSW recupera gli archi lunghi con la gerarchia di livelli. Vamana ottiene lo stesso effetto — un grafo a diametro piccolo — dentro un singolo livello, grazie ad alpha. E questa è esattamente la proprietà che serve per il passo successivo: meno passi significa meno letture da disco.

Un dettaglio sul punto di partenza della camminata. La GreedySearch ha bisogno di un nodo di ingresso, e Vamana ne sceglie uno fisso: il medoide del dataset, cioè il punto più centrale, quello la cui distanza media da tutti gli altri è minima. Partire sempre dal medoide ha due vantaggi. Primo: è un punto “equidistante” da tutto, quindi nessuna regione del grafo è strutturalmente svantaggiata come punto di arrivo. Secondo, e cruciale per DiskANN: poiché tutte le query partono di lì, i nodi attorno al medoide sono i più visitati di tutto il grafo, e tenerli in cache in RAM elimina le prime letture da disco di ogni singola query. Il punto di ingresso fisso e la cache lavorano insieme: è una scelta di design, non un dettaglio.

DiskANN: il layout su SSD

Ecco l’idea che dà il nome al sistema. L’indice DiskANN è diviso fra due memorie.

Su SSD stanno due cose insieme: il grafo Vamana completo e i vettori full-precision. La memoria di ogni nodo, sul disco, contiene sia la lista dei suoi vicini sia il suo vettore esatto, impacchettati nella stessa zona. Visitare un nodo significa leggere una pagina, e quella pagina porta con sé entrambe le cose.

In RAM sta solo una versione PQ-compressa di tutti i vettori — gli stessi codici di product quantization di ann-ivf-pq. Compressi a pochi byte l’uno, tutti i vettori di un dataset da un miliardo di punti entrano comodamente in 64 GB.

A query time la GreedySearch cammina sul grafo come in HNSW. Ma il ragionamento “fra i vicini del nodo corrente, dove vado adesso” usa le distanze approssimate calcolate sui codici PQ in RAM — la bussola dell’intuizione. Le letture da SSD servono solo a una cosa: recuperare la lista dei vicini del nodo che si sta espandendo. Poiché il diametro del grafo è piccolo, i passi sono pochi, e quindi le letture random da disco sono poche.

DiskANN aggiunge due accorgimenti per spremere ancora l’I/O:

Beam search. Invece di espandere un nodo alla volta, la ricerca espande un fascio di nodi e ne richiede le pagine dal disco in parallelo. L’SSD serve molte letture contemporaneamente meglio di quanto serva una lettura isolata: il throughput aggregato di un SSD è alto anche se la latenza di una singola lettura è cattiva, e il fascio ammortizza proprio quella latenza distribuendola su più letture concorrenti. È la stessa idea di beam search — tenere vivi più candidati insieme invece di committarsi al singolo migliore — applicata qui non per la qualità del risultato ma per nascondere la latenza del disco. La larghezza del fascio è una manopola: un fascio largo fa più letture in parallelo (più I/O ammortizzato) ma espande anche nodi che forse non servivano.
Caching. I nodi vicini al punto di ingresso sono visitati da quasi tutte le query. DiskANN li tiene in RAM. Si pagano letture da disco solo per i nodi raggiunti “in profondità”, quando la camminata si avvicina alla meta.

Un dettaglio elegante chiude il quadro. Quando la ricerca visita un nodo, la pagina che legge dal disco contiene già il vettore full-precision di quel nodo. Quindi la distanza esatta per il ranking finale arriva gratis, insieme agli archi, senza un passo di rescoring separato come quello che ScaNN e IVFPQ devono fare. Il layout di DiskANN fonde routing e verifica nella stessa lettura.

Vale la pena seguire una query, passo per passo, per vedere come le due memorie collaborano. La query $q$ arriva. DiskANN parte dal nodo di ingresso — il medoide, già in cache — e ne guarda i vicini. Per decidere verso quale vicino muoversi, calcola la distanza approssimata fra $q$ e ciascun vicino usando i codici PQ in RAM: nessuna lettura da disco, solo la bussola. Sceglie il vicino più promettente e ci si sposta. Solo a questo punto, per espandere il nuovo nodo, serve sapere chi sono i suoi vicini: ed è qui che parte una lettura dall’SSD, una pagina che porta indietro la lista degli archi più il vettore esatto del nodo. La beam search fa partire più letture di questo tipo insieme. Il ciclo si ripete — stima approssimata in RAM per decidere, lettura su disco per espandere — finché la frontiera di ricerca smette di migliorare. I vettori esatti raccolti lungo il cammino, arrivati gratis con le pagine, danno il ranking finale. Una query tocca quindi solo qualche decina di nodi, e di quelli solo i non-cachati costano una lettura: poche letture random per query, ed è esattamente l’obiettivo che il diametro piccolo del grafo rende raggiungibile.

DiskANN: perché due passate di costruzione

Torniamo un momento sulla costruzione di Vamana, perché lo schema mostrava “ripeti due volte: prima con alpha = 1, poi con alpha > 1”, e quel dettaglio non è un capriccio.

L’idea di fondo è semplice: costruire un grafo di buona qualità in un passaggio solo è difficile, perché le decisioni prese all’inizio — quando il grafo è ancora quasi casuale — sono di scarsa qualità. Fare due passate permette alla seconda di lavorare su un grafo già ragionevole invece che su uno casuale.

La prima passata, con $\alpha = 1$ , costruisce un grafo potato in modo aggressivo. Ogni arco per cui esiste un detour viene tagliato: il grafo risultante è rado, con pochi archi per nodo, fatto quasi solo di collegamenti corti verso i vicini immediati. È un grafo “localmente sensato” ma con un diametro grande — per andare lontano servono molti passi corti.

La seconda passata, con l’alpha scelto maggiore di 1, riparte da quel grafo e rilassa la potatura. Lo slack di alpha lascia sopravvivere archi che la prima passata avrebbe tagliato, e in particolare lascia sopravvivere gli archi lunghi. Il grafo finale ha quindi due tipi di collegamenti: i collegamenti corti che danno precisione locale, ereditati dalla prima passata, e i collegamenti lunghi che danno le scorciatoie, aggiunti dalla seconda. Fare le due passate in quest’ordine — prima il grafo locale pulito, poi le scorciatoie — produce un grafo migliore che non partire subito con alpha alto. È un dettaglio di ingegneria, ma spiega perché il diametro finale di Vamana è davvero piccolo.

DiskANN: costruire l’indice oltre la RAM

C’è anche un problema di scala nella costruzione. Per costruire il grafo Vamana servono i vettori grezzi, e un miliardo di vettori grezzi non entra in RAM nemmeno in fase di build. DiskANN risolve con un divide-and-conquer: partiziona il dataset in sottoinsiemi sovrapposti, costruisce un grafo Vamana per ciascun sottoinsieme — questo sì entra in RAM — e poi fonde i sottografi in un unico grafo.

La sovrapposizione fra le partizioni è la chiave. Se le partizioni fossero disgiunte, la fusione produrrebbe un grafo a isole: sottografi ben connessi al loro interno ma senza ponti fra loro, e una ricerca che parte in un’isola non raggiungerebbe mai le altre. Assegnando invece ogni vettore a più partizioni, i nodi condivisi compaiono in più sottografi e, dopo la fusione, ereditano archi che attraversano i confini. Sono questi nodi-ponte a garantire che il grafo finale resti un unico componente connesso, navigabile da qualsiasi punto a qualsiasi altro. È divide-and-conquer con una cucitura deliberata, non un semplice taglia-e-incolla.

FreshDiskANN: inserimenti e cancellazioni

DiskANN, come descritto finora, costruisce un indice statico. Per riflettere una modifica al corpus — un documento aggiunto, una email cancellata — bisogna ricostruirlo. Per molti casi reali, dove il corpus cambia in continuazione, ricostruire periodicamente è troppo costoso.

FreshDiskANN è il successore che risolve questo. Il paper è FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search, di Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy e Harsha Vardhan Simhadri (Microsoft Research, 2021). L’idea è tenere due indici: uno di lungo termine, grande, read-only, su SSD; e uno temporaneo, piccolo, in RAM, che assorbe gli inserimenti recenti. Una nuova query interroga entrambi e unisce i risultati.

Le cancellazioni non rimuovono subito il punto dal grafo — operazione costosa, perché lascia buchi fra i vicini. Vanno invece in una DeleteList: il punto è solo marcato come cancellato, un semplice append. È per questo che cancellare costa pochissimo, intorno a 0.1 microsecondi. A query time un nodo presente nella DeleteList viene saltato come risultato, ma resta nel grafo come passaggio: la camminata può ancora attraversarlo per raggiungere altri nodi. Le sue cicatrici nel grafo, insomma, non sono ancora rimarginate, sono solo invisibili nei risultati.

La rimarginazione vera avviene periodicamente, con un’operazione di consolidamento chiamata StreamingMerge. Lo StreamingMerge fonde l’indice temporaneo in quello di lungo termine e applica davvero le cancellazioni: rimuove fisicamente dal grafo i nodi della DeleteList e riesegue RobustPrune su tutti i nodi che avevano un vicino cancellato, ricucendo gli archi dove i vuoti si erano aperti. È un’operazione pesante — tocca un’ampia porzione del grafo — ma viene fatta di rado e in modo asincrono, fuori dal percorso critico delle query.

I numeri raccontano il trade-off. L’inserimento ha latenza intorno a 1 millisecondo, la cancellazione intorno a 0.1 microsecondi: entrambe le operazioni di update sono economiche, perché il lavoro pesante è rimandato al consolidamento. FreshDiskANN dichiara recall stabile sotto un flusso continuo di inserimenti e cancellazioni, e un costo di mantenimento della “freschezza” dell’indice 5-10 volte inferiore alla ricostruzione periodica. Il prezzo, come sempre, c’è: lo StreamingMerge va schedulato, e nella finestra fra due consolidamenti il grafo porta con sé le cicatrici delle cancellazioni — un degrado piccolo e temporaneo del recall, accettabile in cambio di update quasi gratuiti.

Esempi

Esempio numerico — dove vanno i byte in ScaNN

Prendiamo un datapoint $x$ e supponiamo, per semplicità, di lavorare in due dimensioni così da poter ragionare a mano. Sia $x = (10,\ 0)$ — un vettore che punta lungo l’asse orizzontale, di lunghezza 10.

La quantizzazione lo sostituisce con un $\tilde{x}$ scelto da un codebook. Confrontiamo due candidati con lo stesso errore di ricostruzione totale, $\lVert r \rVert = 1$ :

Candidato A: $\tilde{x}_A = (9,\ 0)$ . Il residuo è $r_A = (1,\ 0)$ , interamente parallelo a $x$ .
Candidato B: $\tilde{x}_B = (10,\ 1)$ . Il residuo è $r_B = (0,\ 1)$ , interamente ortogonale a $x$ .

Per PQ classico A e B sono equivalenti: stesso $\lVert r \rVert$ . Ora prendiamo una query allineata, $q = (1,\ 0)$ — una query che troverebbe $x$ rilevante. Il prodotto interno vero è $\langle q, x \rangle = 10$ . Le stime:

Con A: $\langle q, \tilde{x}_A \rangle = 9$ . Errore sul prodotto interno: $1$ .
Con B: $\langle q, \tilde{x}_B \rangle = 10$ . Errore sul prodotto interno: $0$ .

Stesso errore di ricostruzione, errore sul prodotto interno completamente diverso. Il residuo parallelo di A si scarica tutto nella stima; quello ortogonale di B sparisce. La loss anisotropa di ScaNN penalizza A più di B, e così facendo guida la scelta dei codici verso quantizzazioni che proteggono il ranking. PQ classico, cieco alla direzione, sceglierebbe A e B a caso.

Una precisazione onesta: l’esempio è scelto per essere limpido, con residui perfettamente paralleli o perfettamente ortogonali. Nella realtà il residuo di una quantizzazione ha entrambe le componenti mescolate, e la query non è mai esattamente allineata al datapoint. La loss anisotropa lavora in media, su tutte le query plausibili e su residui generici: pesa di più la frazione parallela, qualunque essa sia. L’esempio in due dimensioni mostra il meccanismo allo stato puro; il sistema reale lo applica in forma sfumata, ma la direzione dell’effetto è la stessa.

Esempio in codice — le tre fasi di ScaNN

Lo schema d’uso della libreria ScaNN rende visibile la pipeline a tre fasi. In pseudocodice vicino all’API reale:

# dataset: N vettori di embedding, normalizzati per il dot product

searcher = (
    scann.builder(dataset, num_neighbors=10, distance="dot_product")
    # fase 1 — partizionamento: ~sqrt(N) foglie, a query
    # time se ne visitano 100
    .tree(num_leaves=2000, num_leaves_to_search=100)
    # fase 2 — scoring: asymmetric hashing, 2 dimensioni per
    # blocco, quantizzazione anisotropa con la soglia score-aware
    .score_ah(2, anisotropic_quantization_threshold=0.2)
    # fase 3 — rescoring: ricalcola esatto i 100 migliori,
    # poi tieni i top 10
    .reorder(100)
    .build()
)

vicini, distanze = searcher.search(query, final_num_neighbors=10)

Si leggono le tre fasi una per riga. .tree(...) è il partizionamento IVF-like. .score_ah(...) è lo scoring con asymmetric hashing: il parametro anisotropic_quantization_threshold è la manopola che attiva e regola la loss score-aware — è la traduzione pratica della teoria di questo capitolo. .reorder(100) è il rerank: ricalcola esatte le distanze dei 100 candidati migliori e da quelli estrae i 10 finali. Cambiare num_leaves_to_search e reorder muove il punto sulla frontiera recall-velocità, esattamente come nprobe e il rerank in ann-ivf-pq.

Una cosa che il codice rende evidente: la pipeline è componibile a stadi, e ogni stadio è un punto di taratura indipendente. Si può togliere .tree(...) per un dataset piccolo, abbassare .reorder(...) per guadagnare latenza a scapito del recall, alzare num_leaves_to_search per il contrario. Non c’è una configurazione giusta in assoluto: c’è la configurazione giusta per il proprio dataset e il proprio vincolo, e va trovata misurando — la stessa disciplina empirica che ann-intro raccomandava per ogni indice ANN.

Esempio numerico — RobustPrune e lo slack di alpha

Vediamo all’opera la regola di potatura su un caso minuscolo. Stiamo decidendo gli archi uscenti del nodo $v$ . La GreedySearch ha raccolto tre candidati, e abbiamo già misurato le distanze da $v$ :

$p_1$ : $\text{dist}(v, p_1) = 2$
$p_2$ : $\text{dist}(v, p_2) = 5$
$p_3$ : $\text{dist}(v, p_3) = 9$

RobustPrune esamina i candidati dal più vicino. Tiene subito $p_1$ , il più vicino in assoluto: nessun arco lo può rendere ridondante. Ora valuta $p_2$ . La domanda è: esiste un vicino già scelto — qui solo $p_1$ — che renda $p_2$ raggiungibile abbastanza bene? Serve la distanza $\text{dist}(p_1, p_2)$ ; supponiamo valga $4$ . La regola scarta l’arco $v \to p_2$ se $\text{dist}(v, p_1) \cdot \alpha \le \text{dist}(v, p_2)$ , cioè se $2\alpha \le 5$ .

Con $\alpha = 1$ : $2 \le 5$ è vero, l’arco $v \to p_2$ viene tagliato. Per andare da $v$ a $p_2$ si dovrà passare per $p_1$ . Con $\alpha = 1.5$ : $3 \le 5$ è ancora vero, tagliato lo stesso. Con $\alpha = 2.5$ : $5 \le 5$ è al limite, e oltre quel valore — diciamo $\alpha = 3$ — la disuguaglianza $6 \le 5$ diventa falsa e l’arco $v \to p_2$ sopravvive.

Questo è lo slack in azione. Un alpha più alto è più indulgente: lascia in vita archi che un alpha basso avrebbe tagliato in favore di un detour. Su scala reale, gli archi che sopravvivono grazie allo slack sono spesso quelli lunghi — quelli verso $p_3$ e oltre — e sono proprio le scorciatoie che accorciano il diametro del grafo. Tagliarli tutti, come fa $\alpha = 1$ , dà un grafo rado e profondo; lasciarne sopravvivere alcuni dà un grafo un po’ più denso ma molto meno profondo. Vamana sceglie il secondo, ed è perché può navigare un miliardo di nodi in poche letture da disco.

Scenario reale — un indice da un miliardo di chunk per un sistema RAG

Un team costruisce un sistema RAG su un corpus di documentazione tecnica enorme: dopo il chunking, circa un miliardo di frammenti, ciascuno con un embedding a 768 dimensioni. In float32 sono circa 3 terabyte di vettori grezzi. HNSW richiederebbe quei 3 TB più il grafo, tutto in RAM: significa una flotta di macchine con molta memoria, sharding dell’indice, e un costo che cresce con il corpus.

Con DiskANN il conto cambia. I vettori PQ-compressi di un miliardo di punti stanno in poche decine di GB di RAM; il grafo Vamana e i vettori full-precision stanno su un SSD da qualche terabyte, hardware economico. Una singola macchina con 64 GB di RAM serve l’indice. Una query di retrieval costa qualche millisecondo: il tempo di alcune letture random da disco, ammortizzate dalla beam search. Il recall resta alto perché Vamana ha un diametro piccolo e i pochi passi raggiungono comunque i veri vicini.

Se il corpus viene aggiornato di continuo — nuova documentazione che entra, pagine deprecate che escono — si passa a FreshDiskANN, che assorbe gli inserimenti senza ricostruire. Lo stesso retrieval che richiedeva un cluster di RAM diventa una macchina sola con un disco. È la differenza fra un’architettura che scala in costo e una che scala in capacità di disco. E in un sistema RAG il retrieval è solo uno dei costi: spostare il suo footprint da una flotta a una macchina libera budget per il resto — il modello, il reranker, l’inferenza.

Applicazioni pratiche

ScaNN e DiskANN non sono curiosità da paper: sono in produzione, dentro prodotti che molti usano senza saperlo.

ScaNN dentro Google e Google Cloud. ScaNN alimenta sistemi di recommendation e di retrieval interni a Google. Nel cloud è la base di Vertex AI Vector Search (in origine Matching Engine), il servizio gestito di ricerca vettoriale, e dell’indice TreeAH di BigQuery — dove la sigla TreeAH è letteralmente “Tree” più “Asymmetric Hashing”, le prime due fasi della pipeline vista sopra. Chi crea un indice vettoriale su quei servizi sta usando la quantizzazione anisotropa, anche se l’API non la nomina.

Questo è un punto che vale per entrambi i sistemi e merita di essere reso esplicito. Un servizio cloud gestito espone all’utente parametri di alto livello — quanti vicini, che metrica, che soglia di recall — e nasconde l’algoritmo. Ma l’algoritmo sotto determina i veri limiti: quanto recall si ottiene a parità di costo, quanto velocemente l’indice si aggiorna, fino a che scala regge. Sapere che TreeAH è ScaNN, o che l’indice vettoriale di Cosmos DB è DiskANN, significa poter prevedere quei limiti invece di scoprirli in produzione. È la differenza fra usare uno strumento e capirlo.

DiskANN dentro Microsoft e Azure. DiskANN nasce dal progetto Akupara di Microsoft Research, pensato per la ricerca semantica su scala web, ed è stato usato nella ricerca semantica di Bing. Nel cloud Azure è il motore di ricerca vettoriale di più servizi: Azure Cosmos DB, Azure Database for PostgreSQL e Azure AI Search. La scelta di DiskANN in questi prodotti è coerente con la sua natura: un database gestito vuole indici grandi che stiano su disco a basso costo e che reggano aggiornamenti, due cose che — con FreshDiskANN — DiskANN offre.

C’è una ragione strutturale per cui DiskANN finisce dentro i database e non solo dentro motori di ricerca dedicati. Un database memorizza già i dati su disco: aggiungere un indice vettoriale che vive anch’esso su disco si incastra naturalmente nel suo modello di storage, mentre un indice tutto-in-RAM imporrebbe un componente con caratteristiche di costo completamente diverse. DiskANN, nato per minimizzare gli accessi a disco, parla la stessa lingua del motore di storage che lo ospita. Non è un caso che la ricerca vettoriale nei database relazionali e documentali sia arrivata insieme all’adozione di algoritmi come DiskANN.

RAG e memoria degli agenti su larga scala. I due sistemi coprono i due regimi del retrieval a scala. Quando il corpus compresso sta in RAM e si vuole la massima frontiera recall-QPS, ScaNN è la scelta tipica. Quando il corpus non sta in RAM nemmeno compresso — miliardi di chunk — DiskANN serve il retrieval da una singola macchina con SSD. Per la memoria a lungo termine di un agente, che accumula episodi nel tempo e ha quindi bisogno di inserimenti continui su un volume che cresce, FreshDiskANN è il candidato naturale: aggiorna l’indice senza ricostruirlo e tiene il recall stabile.

C’è un dettaglio operativo che vale la pena rendere esplicito. In una pipeline RAG l’indice ANN è quasi sempre il primo stadio del retrieval, non l’unico. Recupera in fretta un insieme largo di candidati — qualche centinaio — che un secondo stadio più costoso, un reranker o un modello, riordina con cura. In questo schema il recall dell’indice ANN non deve essere altissimo: deve solo garantire che i veri vicini siano da qualche parte fra i candidati passati al reranker. Questo cambia come si dimensiona ScaNN o DiskANN: non come l’anello finale che deve azzeccare il ranking, ma come un filtro veloce che non deve perdere i candidati buoni. Tarare l’indice come se fosse l’ultimo passo significa spendere latenza e memoria dove non servono.

Quando invece nessuno dei due serve. Vale la pena dire anche il contrario, perché la tentazione di usare l’indice più sofisticato è reale. Per un dataset di poche decine di migliaia di vettori, la scansione esatta — confrontare la query con tutti, il brute-force di ann-intro — è già abbastanza veloce, e non ha errori di approssimazione. La stessa documentazione di ScaNN lo dice: sotto una certa soglia conviene il brute-force puro. ScaNN e DiskANN risolvono problemi di scala; applicarli a un dataset piccolo aggiunge complessità di build, parametri da tarare e un recall imperfetto, senza nessun guadagno. La scelta dell’indice parte sempre dalla scala reale dei dati, non dall’eleganza dell’algoritmo.

Benchmark come segnale, non come verdetto. Per anni ScaNN ha dominato ann-benchmarks.com: un segnale forte che la sua frontiera recall-velocità in memoria è ottima. DiskANN ha invece definito il regime billion-scale su singolo nodo. I due primati non si contraddicono perché misurano cose diverse: ann-benchmarks misura indici in RAM, DiskANN compete su un asse — la scala oltre la RAM — che quel benchmark non tocca. È la lezione di ann-intro: leggere un benchmark significa prima sapere quale asse misura.

Il caso pratico: 3 TB di RAM diventano 96 GB. Un esempio documentato rende concreto il salto. Un motore di ricerca con un indice HNSW sharded su una flotta di macchine per un totale di circa 3 terabyte di RAM è stato riportato a girare su una singola macchina da 96 GB di RAM passando a DiskANN — l’indice grande spostato su SSD, i codici compressi tenuti in memoria. Lo stesso ordine di grandezza compare in altri resoconti: indici da un miliardo di vettori serviti in pochi millisecondi da terabyte di dati su disco. Il punto non sono le cifre esatte, che dipendono dall’hardware e dal dataset, ma il rapporto: la differenza fra DiskANN e un indice tutto-in-RAM è un fattore di decine sul costo della memoria. Per un sistema dove la memoria domina la bolletta, è la differenza fra sostenibile e no.

Sei fraintendimenti da disinnescare

Prima dei limiti veri e propri, conviene sgombrare il campo da alcuni equivoci ricorrenti. Sono fraintendimenti che fanno scegliere male o diagnosticare male, e ognuno ha una correzione netta.

“ScaNN è un nuovo tipo di indice.” No. ScaNN è la pipeline IVF + PQ + rerank di ann-ivf-pq, con la quantizzazione resa score-aware e una forte ingegneria SIMD. L’innovazione vive nella loss di quantizzazione e nell’implementazione, non in una struttura dati nuova. Chi cerca in ScaNN un’architettura inedita cerca la cosa sbagliata.

“La quantizzazione anisotropa riduce l’errore.” Riduce l’errore sul prodotto interno dei top candidati, e al tempo stesso aumenta l’errore di ricostruzione medio. Chi misura solo l’errore di ricostruzione conclude che ScaNN quantizza peggio di PQ classico. È vero, e voluto: è il baratto centrale del sistema, non un difetto.

“DiskANN è HNSW messo su disco.” No. HNSW è gerarchico e progettato per accessi in RAM; usarlo da disco è troppo lento. Vamana è un grafo a un solo livello, con il parametro alpha che gli dà archi long-range e diametro piccolo proprio per minimizzare le letture random da SSD. Sono due grafi diversi, costruiti per due vincoli diversi.

“Il parametro alpha di Vamana è come ef di HNSW.” No, e confonderli porta a tarare la cosa sbagliata. ef è un parametro di query time: allarga la frontiera di ricerca a indice già costruito. alpha è un parametro di build time: decide quali archi tenere nel grafo. Uno regola la ricerca, l’altro la struttura su cui la ricerca cammina.

“DiskANN ha bisogno di un passo di rescoring come IVFPQ.” No, ed è una conseguenza elegante del layout. I codici PQ in RAM servono solo al routing. Quando la ricerca visita un nodo, legge dal disco la pagina che contiene già il suo vettore full-precision: la distanza esatta per il ranking arriva insieme agli archi, senza un passo separato.

“DiskANN supporta inserimenti e cancellazioni.” Non nella sua forma base, che costruisce un indice statico. Gli aggiornamenti in tempo reale sono di FreshDiskANN, il successore del 2021, con i suoi due indici e la DeleteList. Confondere i due porta a promettere una freschezza che l’indice base non ha.

Dove si rompe

ScaNN e DiskANN sono ottimi, ciascuno nel suo regime. Ma “ottimo nel suo regime” è precisamente il punto: ognuno ha un lato che cede, e conoscerlo prima di scegliere evita di portare in produzione l’indice sbagliato.

ScaNN è quasi tutto un sistema in memoria. La quantizzazione anisotropa e lo scoring SIMD presuppongono che i codici dei vettori stiano in RAM. ScaNN non risolve il problema “il dataset non entra in memoria” — quello è il problema di DiskANN. Se i vettori, anche compressi, superano la RAM disponibile, ScaNN non è la risposta. Il suo vantaggio è reale solo dentro il regime in memoria: lì spinge la frontiera recall-QPS più in alto degli altri, fuori da lì non gioca proprio la partita.

La loss anisotropa è tarata per il prodotto interno. Tutto il vantaggio di ScaNN viene dall’osservazione che la componente parallela del residuo danneggia il prodotto interno. Se il caso d’uso non è MIPS — se serve davvero la distanza euclidea pura, o una metrica diversa — il presupposto si indebolisce e il guadagno dell’anisotropia si assottiglia. ScaNN dà il meglio sugli embedding normalizzati confrontati per dot product, che è il caso comune ma non l’unico.

ScaNN, come indice, è prevalentemente statico. È costruito e sintonizzato per un dataset dato. Non ha un meccanismo nativo di aggiornamento incrementale paragonabile all’inserimento in HNSW o a FreshDiskANN: un corpus che cambia molto richiede ricostruzioni. Per dati molto dinamici, la famiglia a grafo aggiornabile è più comoda.

DiskANN paga la latenza del disco. Un indice in RAM risponde in microsecondi o in pochi millisecondi; DiskANN, dovendo fare letture random da SSD, ha una latenza strutturalmente più alta. Beam search e caching la riducono, non la annullano: l’I/O resta nel percorso critico di ogni query. Quando il dataset sta comodo in RAM, mettere il grafo su disco è una pessimizzazione netta — si paga l’I/O senza nessun motivo, e un HNSW in memoria farebbe meglio su ogni asse. DiskANN conviene solo quando la RAM è davvero il vincolo, ed è un errore comune adottarlo “per sicurezza” su dataset che in RAM ci starebbero benissimo.

La latenza di DiskANN dipende dall’hardware del disco. Le cifre di DiskANN — pochi millisecondi per query — assumono un SSD decente. Su un disco lento, o su uno storage di rete con latenza variabile, il profilo cambia. La latenza di coda, in particolare, è esposta agli alti e bassi dell’I/O molto più di un indice in memoria. Un sistema che misura solo la latenza media può nascondere una coda lunga e brutta.

La costruzione di DiskANN è pesante. Costruire un indice billion-scale richiede il partizionamento del dataset, la costruzione di un grafo Vamana per partizione e la fusione dei sottografi. È un processo lungo e dispendioso. Anche la StreamingMerge di FreshDiskANN è un’operazione di consolidamento non gratuita: l’aggiornamento incrementale è economico, ma il consolidamento periodico va messo in conto nel budget operativo.

DiskANN base non si aggiorna. Senza FreshDiskANN, l’indice è statico: ogni modifica al corpus impone una ricostruzione. È un limite reale per chi ha un corpus vivo, e va risolto adottando esplicitamente FreshDiskANN — che però aggiunge la sua complessità (due indici, DeleteList, merge).

Il problema del filtraggio sui metadati resta. Come ann-intro e ann-ivf-pq segnalavano, nei sistemi reali la query raramente è “i vicini di $q$ ” e basta: è “i vicini di $q$ fra i documenti di questo utente”. Né ScaNN né DiskANN sciolgono gratis il filtered ANN. Esistono varianti dedicate — Filtered-DiskANN, per esempio — ma il “trova i vicini” pulito di questo capitolo resta un caso ideale che la produzione complica.

La quantizzazione anisotropa non recupera un recall perso altrove. ScaNN è un sistema con più stadi, e l’anisotropia agisce solo su uno — lo scoring. Se il partizionamento è troppo aggressivo e scarta la partizione che conteneva il vero vicino, nessuna loss di quantizzazione lo può recuperare: il candidato è stato escluso prima ancora di essere scorato. È lo stesso errore di omissione che IVFPQ ha già mostrato. Diagnosticare un recall basso in ScaNN significa chiedersi quale stadio sta perdendo i candidati — il partizionamento, lo scoring, o il rerank troppo corto — e l’anisotropia cura solo il secondo.

DiskANN dipende dalla qualità della bussola PQ. Il routing di DiskANN si fida delle distanze approssimate calcolate sui codici PQ in RAM. Se quella compressione è troppo aggressiva, la bussola mente: indica come promettente un vicino che non lo è, e la camminata devia. I vettori esatti su disco correggono il ranking finale, ma non correggono le decisioni di percorso già prese male. Comprimere troppo i codici in RAM per risparmiare memoria può quindi degradare il recall in modo indiretto e poco intuitivo — non perché il ranking finale sia sbagliato, ma perché la ricerca ha camminato verso la regione sbagliata del grafo.

I benchmark misurano indici statici e regimi diversi. ann-benchmarks misura indici in RAM, costruiti una volta e interrogati. Non misura la freschezza sotto aggiornamenti, non misura il regime su disco, non misura la latenza di coda con I/O reale. Il primato di ScaNN su ann-benchmarks e il primato di DiskANN sul billion-scale non sono confrontabili direttamente: vivono su assi diversi della frontiera di Pareto. Scegliere fra i due partendo da una sola classifica è l’errore tipico.

Entrambi i sistemi sono complessi da implementare bene. Un ultimo limite, di natura diversa. La distanza fra l’idea di ScaNN o DiskANN e una loro implementazione che davvero raggiunge i numeri dei paper è grande. ScaNN deve la sua velocità a un’ingegneria SIMD attenta, sensibile all’architettura del processore; DiskANN deve la sua a un layout su disco curato, alla beam search, alla gestione della cache. Riprodurre questi sistemi da zero, e ottenerne le prestazioni dichiarate, non è banale. È una ragione pratica per cui, nella maggioranza dei casi, si usano le librerie ufficiali o i servizi gestiti che le impacchettano, invece di reimplementare. Capire l’algoritmo serve a scegliere e a tarare; reimplementarlo è un progetto a sé.

Messi in fila, questi limiti dicono una cosa sola e già nota: non esiste l’indice ANN universale. ScaNN domina la frontiera recall-velocità in memoria per MIPS; DiskANN domina la scala oltre la RAM. La scelta non è “quale è migliore” ma “quale vincolo mi sta stringendo” — la memoria, la latenza, la freschezza, il costo di build. È la stessa lezione con cui si era aperta la mini-serie, vista ora dall’altro capo.

Confronto: le quattro famiglie ANN

Conviene chiudere la serie mettendo le quattro famiglie sullo stesso tavolo. Non per eleggere un vincitore — non c’è — ma per rendere esplicito quale angolo della frontiera ognuna occupa.

Un avvertimento prima di leggere il confronto: ogni “vince” e ogni “il prezzo è” qui sotto vanno letti come tendenze, non come verdetti assoluti. Le prestazioni reali dipendono dal dataset, dalla dimensionalità, dall’hardware, dalla taratura. La tabella che segue serve a costruire un’intuizione di prima approssimazione — a sapere da dove partire — non a sostituire la misura sul proprio caso. Con questa cautela, il quadro è il seguente.

HNSW è il grafo gerarchico in RAM. Vince su recall e latenza quando i vettori stanno comodi in memoria, ed è aggiornabile per inserimento in modo nativo. Ha sostanzialmente una sola manopola di query time, ef_search, e un comportamento prevedibile: è l’indice più semplice da gestire fra i quattro.

Il suo prezzo è la memoria. HNSW vuole i vettori grezzi più il grafo dei collegamenti: la memoria che occupa è maggiore dei dati grezzi, non minore. Non scala oltre la RAM disponibile, ed è proprio il vincolo che apre la strada agli altri tre.

IVF+PQ è il partizionamento più la quantizzazione. Vince sulla memoria: comprime i vettori in pochi byte l’uno e ci sta in budget ridotti, abilitando indici che HNSW non potrebbe ospitare.

Il prezzo è un recall più basso a parità di tutto, perché la quantizzazione è lossy; una fase di training k-means sensibile alla distribuzione dei dati, che invecchia se i dati cambiano; più manopole da tarare insieme; e cancellazioni che lasciano lapidi nelle liste invertite.

ScaNN è la stessa famiglia di IVF+PQ, raffinata. La quantizzazione resa score-aware e l’implementazione SIMD gli danno la migliore frontiera recall-QPS in memoria per MIPS — per anni il riferimento su ann-benchmarks.

Il prezzo è che resta un sistema prevalentemente in RAM e prevalentemente statico: costruito e sintonizzato per un dataset dato, senza un meccanismo nativo di aggiornamento incrementale. Per dati molto dinamici è meno comodo di un grafo aggiornabile.

DiskANN/Vamana è il grafo singolo su SSD più la PQ in RAM. Vince sulla scala oltre la RAM: un miliardo di vettori su una macchina con 64 GB, un regime che gli altri tre non raggiungono su singolo nodo.

Il prezzo è una latenza più alta di un indice in memoria — si paga l’I/O del disco, e la latenza di coda è esposta agli alti e bassi dell’SSD — una costruzione complessa fatta di partizioni e fusione, e l’aggiornabilità che arriva solo adottando FreshDiskANN, con la complessità aggiuntiva che comporta.

Resta da chiarire un confronto interno al regime in memoria: HNSW contro ScaNN, quando entrambi sono applicabili. Non c’è una risposta secca, ma ci sono due tendenze. HNSW, come grafo, supporta l’inserimento incrementale in modo nativo e ha essenzialmente una manopola di query time, ef_search: è semplice da gestire e adatto a dati che cambiano. ScaNN, sulla frontiera recall-QPS pura per MIPS su dati statici, tende a spingere più in alto grazie alla quantizzazione anisotropa e allo scoring SIMD — è stato per anni il riferimento dei benchmark — ma è più un sistema da costruire e sintonizzare una volta che da aggiornare di continuo. In pratica: dati dinamici e gestione semplice spingono verso HNSW; un indice statico dove ogni punto percentuale di throughput conta spinge verso ScaNN.

La sintesi operativa sta in poche righe di decisione. Se i vettori stanno in RAM e serve la massima frontiera recall-latenza: HNSW o ScaNN. Se la memoria è il vincolo ma i vettori compressi ci stanno: IVF+PQ o ScaNN. Se i vettori non ci stanno proprio, nemmeno compressi: DiskANN. Se servono aggiornamenti frequenti: HNSW in modo nativo, o FreshDiskANN. La frontiera di Pareto che ann-intro aveva disegnato con due assi — recall e velocità — ne ha in realtà almeno sei: recall, latenza, memoria, scala oltre il disco, costo di build, aggiornabilità. Ogni famiglia occupa un vertice diverso di quel poliedro. La scelta giusta non si legge da una classifica: si legge dal vincolo che, nel proprio sistema, sta stringendo per primo.

C’è una conclusione più generale da portare via dall’intera mini-serie. Le quattro famiglie non sono quattro tentativi di risolvere lo stesso problema, di cui uno alla fine vince. Sono quattro punti di equilibrio diversi fra vincoli reali — memoria, latenza, scala, freschezza, costo — e la ragione per cui coesistono tutte è che i sistemi reali abitano regimi diversi. Un prototipo con un milione di vettori e un motore di ricerca web con dieci miliardi non hanno lo stesso problema, e non vogliono lo stesso indice. Capire ANN non significa sapere “qual è il migliore”: significa saper leggere il proprio sistema, identificare quale risorsa sta diventando il collo di bottiglia, e scegliere la famiglia il cui baratto rilascia proprio quella risorsa.

Collegamenti

Approximate nearest neighbor: il problema — il problema ANN, le famiglie di metodi, la frontiera di Pareto: questo capitolo la completa mostrando che gli assi sono più di due.
HNSW: la ricerca vettoriale come passeggiata su un grafo — la famiglia a grafo gerarchica; Vamana è il termine di paragone diretto, un grafo di prossimità non gerarchico.
IVF e product quantization — la famiglia partizionamento più quantizzazione; ScaNN ne è il raffinamento score-aware, e DiskANN riusa la sua PQ come bussola in RAM.
Prodotto scalare come proiezione e somiglianza — il prodotto interno e MIPS, l’oggetto che la quantizzazione anisotropa protegge.
Norme e distanze — la decomposizione di un residuo in componente parallela e ortogonale è una proiezione.
La maledizione della dimensionalità — perché serve quantizzare e partizionare invece di confrontare ogni vettore.
Embedding: spazi e direzioni semantiche — da dove vengono i vettori densi che questi indici comprimono e cercano.
Beam search e suoi limiti — la beam search che DiskANN usa per nascondere la latenza del disco è la stessa idea, in un altro contesto.
lsh (in preparazione) — l’altra grande famiglia ANN, l’hashing sensibile alla località, che chiude la mini-serie.
rag-base (in preparazione) — il consumatore principale a scala: il retrieval di un sistema RAG su corpora da miliardi di chunk.
vector-databases (in preparazione) — i prodotti gestiti che impacchettano ScaNN e DiskANN dietro un’API operativa.

Un’ultima riga sulla traiettoria. La mini-serie ANN ha seguito un arco preciso: dal problema puro di ann-intro, alle due grandi famiglie di ann-hnsw e ann-ivf-pq, fino ai due sistemi di questo capitolo che spingono ciascuna famiglia al suo estremo pratico. Manca un tassello, e lo copre il capitolo lsh (in preparazione): l’hashing sensibile alla località, la terza grande strada all’ANN, diversa per natura sia dai grafi sia dalla quantizzazione. Con quello, la mappa dei metodi per la ricerca approssimata dei vicini è completa.

Per andare oltre

Guo, Sun, Lindgren, Geng, Simcha, Chern, Kumar, Accelerating Large-Scale Inference with Anisotropic Vector Quantization (ICML 2020; preprint arXiv:1908.10396). Il paper primario di ScaNN: la famiglia di loss anisotrope, la decomposizione del residuo, il risultato sui benchmark. Lettura primaria sulla teoria.
Subramanya, Devvrit, Kadekodi, Krishnaswamy, Simhadri, DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node (NeurIPS 2019). Il paper primario di DiskANN: il grafo Vamana, RobustPrune e il parametro alpha, il layout SSD più PQ in RAM, i numeri su SIFT1B.
Singh, Subramanya, Krishnaswamy, Simhadri, FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search (arXiv:2105.09613, 2021). Il successore per inserimenti e cancellazioni in tempo reale: i due indici, la DeleteList, lo StreamingMerge.
Google Research Blog, Announcing ScaNN: Efficient Vector Similarity Search (luglio 2020). Spiegazione accessibile dell’intuizione anisotropa, con figure: perché l’errore parallelo danneggia il ranking più di quello ortogonale.
Documentazione di ScaNN (repository google-research/google-research, cartella scann/docs). La pipeline a tre fasi, i parametri num_leaves, num_leaves_to_search, reordering_num_neighbors e le linee guida per sceglierli in base alla dimensione del dataset.
Repository microsoft/DiskANN e progetto Akupara di Microsoft Research. Il codice di riferimento per costruire e interrogare un indice DiskANN e FreshDiskANN, e i workflow di esempio per il caso billion-scale.