Breve introduzione all'indice ScaNN

ScaNN è la risposta di Google a una sfida familiare nella ricerca vettoriale su larga scala: come aumentare il throughput delle query e ridurre l'utilizzo della memoria senza incidere in modo inaccettabile sulla qualità dei risultati. Concettualmente, ScaNN parte dalla classica ricetta IVF+PQ - clustering grossolano e quantizzazione aggressiva del prodotto - ma aggiunge due importanti innovazioni che spostano significativamente la frontiera delle prestazioni:

• Un obiettivo di quantizzazione consapevole del punteggio che preserva meglio l'ordinamento relativo dei veri vicini, migliorando la qualità del ranking anche in caso di forte compressione.

• FastScan è un percorso di ricerca PQ a 4 bit ottimizzato SIMD che riduce il tradizionale collo di bottiglia del carico di memoria mantenendo più lavoro nei registri della CPU.

In pratica, si tratta di una scelta forte quando si è disposti a barattare un po' di richiamo per un QPS elevato e un ingombro di memoria molto più ridotto (spesso comprimendo i vettori a ~1/16 della dimensione originale), come nel caso dei carichi di lavoro di raccomandazione non sensibili al richiamo.

In questo post, esamineremo IVFPQ come base di riferimento, esploreremo le ottimizzazioni chiave che ScaNN introduce su di esso e concluderemo con risultati sperimentali che fondano la discussione sulle prestazioni misurate.

Riassunto di IVFPQ

ScaNN è stato proposto da Google nel 2020 e il documento riporta un miglioramento delle prestazioni di 3 volte rispetto a HNSW sul set di dati GloVe. Per i dettagli è possibile consultare il documento originale e l'implementazione open-source.

Prima di introdurre ScaNN, ricapitoliamo brevemente IVFPQ, dato che ScaNN è costruito sulla stessa struttura generale.

IVFPQ è l'acronimo di Inverted File with Product Quantization (File invertito con quantizzazione del prodotto), un algoritmo utilizzato per la ricerca approssimativa dei vicini (ANN) efficiente e su larga scala in database vettoriali ad alta dimensione. Si tratta di un approccio ibrido che combina due tecniche, l'indice di file invertito (IVF) e la quantizzazione del prodotto (PQ), per bilanciare la velocità di ricerca, l'utilizzo della memoria e la precisione.

Come funziona l'IVFPQ

Il processo prevede due fasi principali durante l'indicizzazione e la ricerca:

• Livello IVF: i vettori vengono raggruppati in elenchi invertiti (cluster) nlist. Al momento dell'interrogazione, si visita solo un sottoinsieme di cluster (nprobe) per trovare un compromesso tra richiamo e latenza/throughput.

• Livello PQ: all'interno di ogni cluster visitato, ogni vettore di dimensioni D viene suddiviso in m sottovettori, ciascuno di dimensioni (D/m). Ogni sottovettore viene quantizzato assegnandolo al centroide più vicino nel suo sottocodice. Se un sottocodice ha 256 centroidi, ogni sottovettore può essere rappresentato da un codice uint8 (un ID in [0, 255]).

Il calcolo della distanza può quindi essere riscritto come somma di sottovettori:

D(q, X) = D(q, u0) + D(q, u1) + D(q, u2) + ... + D(q, un)

= L(q, id1) + L(q, id2) + L(q, id3) + ... + L(q, idn)

L rappresenta una tabella di ricerca. Al momento dell'interrogazione, la tabella di ricerca viene costruita, registrando la distanza tra l'interrogazione e ogni sottovettore quantizzato. Tutti i calcoli successivi della distanza sono convertiti in ricerche nella tabella seguite da una somma.

Ad esempio, per vettori a 128 dimensioni suddivisi in 32 sottovettori di 4 dimensioni ciascuno, se ogni sottovettore è codificato da un ID uint8, il costo di memorizzazione per vettore scende da (128 x 4) byte a (32 x 1) byte, con una riduzione di 1/16.

Ottimizzazioni di ScaNN basate su IVFPQ

In sintesi, ScaNN migliora IVFPQ sotto due aspetti:

1. Quantizzazione: ScaNN propone un obiettivo che va oltre la semplice sostituzione di ogni sottovettore con il centroide k-means più vicino (cioè la minimizzazione dell'errore di ricostruzione).

2. Efficienza di ricerca: ScaNN accelera la ricerca basata su LUT, che spesso è vincolata alla memoria, attraverso un percorso FastScan SIMD-friendly.

Perdita di quantizzazione consapevole del punteggio

Poiché l'analisi si basa sulla metrica IP, dopo che ScaNN decompone l'errore di quantizzazione in componenti parallele e perpendicolari, solo la componente parallela influisce sul risultato, quindi è necessario applicare un termine di penalità maggiore. Di conseguenza, la funzione di perdita può essere riscritta come segue:

$$\begin{array}{r}{\displaystyle \ell ({\mathrm{xi}}_{},{\mathrm{x~i}}_{},w)}\end{array}$$$$∥2\begin{aligned} \´ell'left(x_i, ´tilde{x}_i, w\right) &=h_{\|}\left(w,\left\|x_i\right\|\right)\left\|r_{\|}\left(x_i, \tilde{x}_i\right)\right\|^2 +h_{\perp}\left(w,\left\|x_i\right\|\right)\left\|r_{\perp}\left(x_i,$$ \tilde{x}_i\right$$)\right\|^2 \end{aligned}$$ ℓ$$\begin{array}{r}(x\end{array}$$i, x~i,w) =h∥ $$\begin{array}{l}(w,\end{array}$$∥xi$$\begin{array}{l}\Vert )\end{array}$$ $$\begin{array}{l}r\end{array}$$∥ $$\begin{array}{l}(x\end{array}$$i, x~i) 2+h⊥ $$\begin{array}{l}(w,\Vert x\end{array}$$i$$\begin{array}{l}\Vert )\Vert r\end{array}$$⊥ $$\begin{array}{l}(x\end{array}$$i,

La figura seguente mostra un esempio bidimensionale che illustra come l'errore causato dalla componente parallela sia maggiore e possa portare a risultati di nearest neighbor errati, giustificando quindi una penalizzazione più severa.

La figura di sinistra mostra una quantizzazione scadente perché l’offset parallelo influisce sul risultato finale, mentre la figura di destra mostra una quantizzazione migliore.

PQ FastScan a 4 bit

Rivediamo innanzitutto il processo di calcolo del PQ: durante l’interrogazione, le distanze tra i centri dei cluster della query e del sottovettore vengono precalcolate per costruire una tabella di ricerca. Il calcolo della distanza viene quindi eseguito attraverso le ricerche nella tabella per ottenere le distanze tra i segmenti e sommarle.

Tuttavia, le frequenti letture di memoria diventano un collo di bottiglia per le prestazioni. Se la tabella di ricerca può essere resa abbastanza piccola da essere inserita nei registri, le operazioni di lettura della memoria possono essere trasformate in efficienti istruzioni SIMD della CPU.

Innanzitutto, ogni sottovettore viene raggruppato in 16 classi, in modo che un valore a 4 bit possa rappresentare il centro di un cluster: questa è l'origine del nome "PQ a 4 bit". Quindi, le distanze, tipicamente rappresentate come float, vengono ulteriormente convertite in uint8 utilizzando la quantizzazione scalare (SQ). In questo modo, la tabella di ricerca per un sottovettore può essere memorizzata in un registro che utilizza 16 × 8 = 128 bit.

Infine, esaminiamo il layout di memorizzazione dei registri (utilizzando il set di istruzioni AVX2 come esempio): i sottovettori di 32 vettori sono collocati in un registro a 128 bit, insieme alla tabella di ricerca. L'operazione di "lookup" può quindi essere completata in modo efficiente utilizzando una singola istruzione SIMD shuffle della CPU.

disposizione dei registri

SIMD Shuffle per il lookup

Ecco un'osservazione interessante: l'articolo di ScaNN si concentra interamente sulla prima ottimizzazione, il che è ragionevole dal momento che può essere considerato un documento di algoritmi che enfatizza le derivazioni matematiche. Tuttavia, i risultati sperimentali presentati nell'articolo sono notevolmente impressionanti.

I risultati sperimentali presentati nell’articolo di ScaNN.

Intuitivamente, l'ottimizzazione della sola perdita non dovrebbe produrre effetti così drammatici. Anche un altro blog lo ha sottolineato: ciò che fa davvero la differenza è la parte PQ FastScan a 4 bit.

Risultati sperimentali

Utilizzando lo strumento di benchmark per database vettoriali VectorDBBench, abbiamo condotto un semplice test. Il vantaggio prestazionale di ScaNN rispetto ai tradizionali IVFFLAT e IVF_PQ è abbastanza evidente. Dopo l'integrazione in Milvus, sul dataset Cohere1M, a parità di tasso di richiamo, il QPS può raggiungere 5 volte quello di IVFFLAT e 6 volte quello di IVF_PQ.

Tuttavia, il QPS è leggermente inferiore a quello di indici basati su grafi come HNSW, quindi non è la prima scelta per casi d'uso ad alto QPS. Tuttavia, per scenari con richiami più bassi, è accettabile (come in alcuni sistemi di raccomandazione), l'uso di ScaNN senza caricare i dati grezzi può raggiungere QPS impressionanti con un ingombro di memoria estremamente ridotto (1/16 dei dati originali), rendendolo una scelta eccellente per l'indice.

Tipo_indice	Caso	QPS	latenza(p99)	richiamo	memoria
IVFFLAT	Prestazioni1M	266	0.0173s	0.9544	3G
HNSW	Prestazioni1M	1885	0.0054s	0.9438	3.24G
FIV_PQ	Prestazioni1M	208	0.0292s	0.928	0.375G
ScaNN (con dati grezzi): vero）	Prestazioni1M	1215	0.0069s	0.9389	3.186G
ScaNN（con_dati_raw: false）	Prestazioni1M	1265	0.0071s	0.7066	0.186G

Conclusione

ScaNN si basa sul noto framework IVFPQ, ma lo spinge significativamente più in là grazie a un profondo lavoro di ingegneria sia nella quantizzazione che nell'accelerazione del lookup di basso livello. Allineando l'obiettivo della quantizzazione con la qualità del ranking ed eliminando i colli di bottiglia della memoria nel ciclo interno, ScaNN combina una quantizzazione consapevole del punteggio con un percorso PQ FastScan a 4 bit che trasforma un processo tradizionalmente legato alla memoria in un calcolo efficiente e SIMD-friendly.

In pratica, ScaNN ha una nicchia chiara e ben definita. Non è destinato a sostituire gli indici a grafo come HNSW in contesti ad alto richiamo. Invece, per i carichi di lavoro non sensibili al richiamo e con budget di memoria limitati, ScaNN offre un elevato throughput con un ingombro molto ridotto. Nei nostri esperimenti, dopo l'integrazione in Milvus VectorDB, ScaNN ha raggiunto circa 5 volte il QPS di IVFFLAT sul set di dati Cohere1M, il che lo rende una valida scelta per il recupero di RNA ad alta velocità e bassa latenza, dove la compressione e l'efficienza contano più del richiamo perfetto.

Se siete interessati ad approfondire ScaNN o a discutere della selezione dell'indice in sistemi reali, unitevi al nostro canale Slack per chiacchierare con i nostri ingegneri e con altri ingegneri AI della comunità. È anche possibile prenotare una sessione individuale di 20 minuti per ottenere approfondimenti, indicazioni e risposte alle vostre domande attraverso Milvus Office Hours.