IVF e product quantization: partizionare lo spazio, comprimere i vettori

Perché un miliardo di embedding non sta in RAM da non compresso, e perché due idee semplici — visitare solo i cluster giusti e sostituire ogni vettore con una manciata di byte — sono ciò che rende la ricerca vettoriale praticabile a quella scala.

Perché questo capitolo

Il capitolo HNSW: la ricerca vettoriale come passeggiata su un grafo ha mostrato la famiglia a grafo: la più forte sulla frontiera recall-latenza quando i vettori stanno comodi nella RAM. Ma quel “quando” è un vincolo, non una garanzia. Un miliardo di embedding a 768 dimensioni in virgola mobile a 32 bit occupa circa 3 terabyte. HNSW vuole quei vettori in memoria e ci aggiunge sopra il suo grafo di collegamenti: la memoria cresce rispetto ai dati grezzi. A quella scala, su hardware ordinario, semplicemente non entra.

Questo capitolo apre la seconda famiglia ANN, quella che ann-intro chiamava “a partizionamento e quantizzazione”. È la famiglia che non cerca di battere HNSW sul recall, ma di risolvere un problema diverso: far entrare in un budget di RAM ragionevole un dataset che, da non compresso, non ci starebbe mai. La risposta arriva da due idee distinte, e tenerle separate è metà del capitolo.

La prima è IVF, l’inverted file index: dividere lo spazio in cluster e, a query time, guardare solo i pochi cluster vicini alla domanda invece di tutto il dataset. Riduce quanti vettori si esaminano. La seconda è PQ, la product quantization: comprimere ogni vettore in una manciata di byte, riducendo insieme la memoria che occupa e il costo di calcolargli una distanza. Riduce quanto costa esaminarne uno. Sono ortogonali — si usano da sole o insieme — e la loro combinazione, in FAISS la stringa IVFx,PQy, è il workhorse della ricerca su miliardi di vettori. Capire questo capitolo significa capire perché un vector database con un corpus enorme espone parametri come nprobe e quanti byte per vettore, e cosa controllano davvero.

C’è anche un motivo concettuale per studiare questa famiglia, al di là della sua utilità pratica. PQ introduce un’idea — comprimere un vettore sostituendolo con codici da un alfabeto piccolo, accettando un errore controllato — che ritorna, sotto un altro nome e in un altro contesto, nella compressione dei pesi dei modelli. Vedere la stessa mossa applicata ai vettori-dato di un indice di ricerca aiuta a riconoscerla quando ricompare nei pesi di una rete neurale. Il capitolo chiude proprio su questo ponte, marcandone con cura la classe: è un’analogia, non una discendenza.

Contesto

Prima della product quantization, la ricerca approssimata su descrittori di immagini si appoggiava a due strade: l’hashing sensibile alla località e gli alberi randomizzati. Entrambe avevano un limite a scala. Gli alberi non comprimevano — servivano i vettori grezzi in memoria — e l’hashing, per recall decente, richiedeva molte tabelle e quindi parecchia RAM. Il problema “un dataset più grande della memoria” restava aperto.

La svolta è un paper del 2011: Hervé Jégou, Matthijs Douze e Cordelia Schmid, Product Quantization for Nearest Neighbor Search, pubblicato su IEEE Transactions on Pattern Analysis and Machine Intelligence (vol. 33, n. 1, gennaio 2011; preprint INRIA inria-00514462 e arXiv:1102.3828). I tre lavoravano nel gruppo LEAR di INRIA Grenoble, un centro di ricerca francese, sul problema della ricerca di immagini su larga scala — descrittori SIFT e GIST, i vettori numerici che catturano texture e forme locali di un’immagine. Il paper fa due cose in un colpo solo: introduce la product quantization come metodo di compressione, e la combina con un inverted file in un sistema chiamato IVFADC. La validazione era impressionante per l’epoca: due miliardi di vettori, una scala che nel 2011 quasi nessuno trattava.

Il termine inverted file non nasce qui. La ricerca testuale lo usa da decenni per la struttura “termine → lista dei documenti che lo contengono”: è l’indice analitico in fondo a un libro, che inverte la relazione naturale documento → parole in parola → documenti. Jégou e colleghi riprendono il nome e lo applicano ai vettori: “centroide di un cluster → lista dei vettori assegnati a quel cluster”. La parola “invertito” va decodificata così — il file mappa la chiave (la cella) ai contenuti (i vettori che vi cadono).

Nel 2017 lo stesso gruppo, passato nel frattempo a Facebook AI Research, pubblica Billion-scale similarity search with GPUs (Johnson, Douze, Jégou, arXiv:1702.08734; poi IEEE Transactions on Big Data, 2019) e rilascia FAISS (Facebook AI Similarity Search), la libreria open source che impacchetta IVF, PQ, HNSW e le loro combinazioni dietro un’API uniforme. FAISS rende IVFx,PQy lo standard de facto della ricerca su miliardi di vettori, ed è ancora oggi la cassetta degli attrezzi di riferimento del settore.

Un’idea di FAISS che vale la pena conoscere è la index factory: una sintassi a stringhe per descrivere un indice composito come una pipeline. Una stringa come OPQ64,IVF4096,PQ64 si legge da sinistra a destra come una catena di stadi — una rotazione OPQ, un partizionamento IVF in 4096 celle, una compressione PQ a 64 byte — e FAISS la traduce nell’indice corrispondente. È una notazione comoda perché rende esplicita la composizione: cambiare uno stadio della stringa cambia un punto del trade-off, e tornerà utile negli esempi.

Sulla product quantization si innestano poi delle varianti. La più citata è OPQ (Optimized Product Quantization), di Tiezheng Ge, Kaiming He, Qifa Ke e Jian Sun (Microsoft Research), presentata a CVPR 2013 e poi su TPAMI: applica una rotazione dei vettori, scelta in modo da rendere la compressione PQ più efficace, e la vedremo nella sezione sulle varianti. Vale la pena fissare la cronologia: PQ è del 2011, OPQ del 2013, FAISS del 2017. Tutto questo precede l’esplosione degli LLM. È un altro caso, come ann-intro insisteva, di tecnologia matura nata per la computer vision che trova il suo caso d’uso di massa — RAG, memoria degli agenti, vector database — solo dopo il 2020, quando produrre embedding di buona qualità per testo arbitrario diventa facile.

C’è un equivoco che la cronologia aiuta a sciogliere. La parola “quantizzazione” oggi richiama soprattutto la compressione dei pesi dei modelli — int8, int4, i metodi della Parte XXIII. Ma la product quantization non discende da lì, e nemmeno il contrario: il termine “quantizzazione” è anteriore a entrambi, viene dalla teoria del segnale e indica genericamente la sostituzione di un valore continuo con uno preso da un insieme finito. PQ lo applica ai vettori-dato di un indice di ricerca; la quantizzazione dei pesi lo applica ai parametri di una rete. Sono cugini lontani con un antenato comune nella teoria dell’informazione, non l’uno figlio dell’altro. La sezione sulle applicazioni torna su questo parallelo, dichiarandone esplicitamente la classe.

L’intuizione

IVF e PQ risolvono problemi diversi, quindi vanno avvicinate con intuizioni separate. Due angoli per ciascuna, prima di qualunque formula.

IVF, angolo 1 — la città divisa in quartieri

Cercare una persona in una città di un milione di abitanti bussando a ogni porta è impraticabile: è il brute-force. Ma una città è divisa in quartieri. Se sai che chi cerchi abita “vicino al fiume”, visiti i due o tre quartieri sul fiume e ignori tutti gli altri. Non hai più garanzia di trovarla — potrebbe essersi trasferita — ma hai ridotto la ricerca di un fattore enorme con una mossa banale.

IVF fa esattamente questo. In fase di build, l’algoritmo k-means — il metodo di clustering che raggruppa i punti attorno a centroidi, trattato nella wiki nel capitolo k-means (in preparazione) — divide lo spazio in nlist quartieri, le celle. Ogni vettore del dataset “abita” nella cella del centroide a lui più vicino. A query time la domanda, anch’essa un vettore, calcola quali centroidi le sono più vicini e cerca solo dentro quelle celle. Se nlist è mille e si visitano dieci celle, la query tocca circa l’1% dei vettori.

C’è un guaio, ed è il cuore di IVF: il problema di bordo. La persona che cerchi potrebbe abitare appena oltre il confine del quartiere giusto, dall’altra parte di una strada. Se visiti solo il quartiere col centroide più vicino alla query, la perdi. Vedremo che la cura è semplice — visitare anche i quartieri confinanti — e che ha un parametro: nprobe.

IVF, angolo 2 — le celle di Voronoi

Il secondo angolo è geometrico e rende preciso “quartiere”. I nlist centroidi di k-means inducono una tassellazione di Voronoi dello spazio: a ogni punto dello spazio si associa il centroide più vicino, e l’insieme dei punti che condividono lo stesso centroide forma una cella di Voronoi. Le celle sono poliedri convessi che pavimentano lo spazio senza buchi né sovrapposizioni — come le piastrelle di un pavimento, ma in centinaia di dimensioni.

Un vettore del dataset finisce nella cella in cui cade. La query è un punto: cade anch’essa in una cella. Ma — ed è qui che nasce il problema di bordo — il suo vero vicino più prossimo può trovarsi in una cella adiacente, perché la query è capitata vicino a un confine. La cella della query non contiene necessariamente il vicino più prossimo della query. Visitare le nprobe celle con i centroidi più vicini espande la ricerca oltre il confine, recuperando i vicini “appena di là”. È un errore strutturale, non un bug: più nprobe, meno errore di bordo, più lavoro.

Figura in preparazione

fig-1: tassellazione di Voronoi in 2D. Lo spazio diviso in celle poligonali, un centroide per cella, punti del dataset sparsi. Una query marcata vicino a un confine: la sua cella evidenziata, e le 2 celle adiacenti pure evidenziate (nprobe=3). Un vero vicino della query sta nella cella adiacente, non in quella della query. Label: “cella della query”, “celle adiacenti visitate”, “vicino oltre il bordo”, “centroide”. Titolo “IVF: il problema di bordo e perché nprobe>1”

IVF, angolo 3 — l’indice analitico in fondo al libro

Il terzo angolo spiega il nome, e il nome spiega la struttura. Un libro di testo ha, in fondo, un indice analitico: una lista di termini, e per ogni termine le pagine in cui compare. È un inverted file nel senso classico della ricerca testuale — inverte la relazione naturale “pagina → parole che contiene” nella relazione utile “parola → pagine che la contengono”. Senza quell’indice, trovare tutte le occorrenze di un termine richiederebbe di sfogliare il libro intero.

IVF prende esattamente questa struttura e cambia la chiave. Al posto di “termine → pagine” mette “centroide → vettori della sua cella”. La inverted list di una cella è la lista delle pagine sotto una voce d’indice. La query, invece di sfogliare tutto il libro, va alle poche voci d’indice pertinenti — le nprobe celle — e legge solo le pagine elencate lì. È la stessa idea che rende veloce la ricerca testuale, trasportata da “parole nei documenti” a “vettori nello spazio”. Capire questo rende il nome trasparente: “inverted file” non è un termine nuovo coniato per i vettori, è un prestito dalla ricerca testuale, e va decodificato come tale.

PQ, angolo 1 — l’indirizzo postale come codice composito

Un indirizzo postale scritto per esteso è lungo. Ma si può comprimere in un codice composito: nazione (un simbolo scelto da un elenco di circa duecento), regione (un simbolo), città (un simbolo da un elenco di città di quella nazione). Tre simboli brevi, presi da tre cataloghi distinti, ricostruiscono approssimativamente la posizione. Si perde il numero civico, ma il grosso dell’informazione sta in pochissimi byte.

La product quantization fa lo stesso con un vettore. Lo spezza in m blocchi, e ogni blocco viene sostituito dall’indice dell’elemento più simile in un piccolo catalogo — un codebook — dedicato a quel blocco. Un vettore di 512 numeri in virgola mobile, che da grezzo occupa 2048 byte, diventa m indici: con m = 64 e cataloghi da 256 voci, sono 64 byte. Trentadue volte più piccolo. Il prezzo è che il vettore ricostruito dal codice non è quello originale, ma il suo “indirizzo approssimato”.

PQ, angolo 2 — il prodotto cartesiano di quantizzatori

Il secondo angolo spiega da dove viene il nome e perché la tecnica è furba. Quantizzare un vettore vorrebbe dire sostituirlo con il centroide più vicino in un codebook. Ma quantizzare un vettore di dimensione d con un unico codebook richiederebbe un numero di centroidi sufficiente a coprire tutto lo spazio d-dimensionale: per dimensioni alte quel numero esplode in modo combinatorio, l’ennesima faccia della maledizione della dimensionalità.

PQ aggira il muro con un prodotto cartesiano. Spezza lo spazio in m sotto-spazi e quantizza ciascuno separatamente con un codebook di k* centroidi — tipicamente k* = 256. Il codebook “effettivo” del vettore intero è il prodotto cartesiano degli m codebook: la sua griglia di centroidi possibili è enorme — con m = 8 e k* = 256 sono 256 elevato a 8, cioè 2 elevato a 64 centroidi virtuali — ma di vettori-centroide se ne memorizzano solo m per k*, cioè 8 per 256 = 2048. Una griglia combinatoriamente gigantesca costruita da otto piccoli alfabeti. È il senso di “product”: prodotto nel senso di prodotto cartesiano di spazi, non moltiplicazione di numeri.

C’è un modo concreto di sentire perché lo split funziona. Immagina di dover descrivere un volto a parole. Un unico “catalogo di volti interi” dovrebbe contenere una voce per ogni volto possibile: impossibile. Ma se descrivi separatamente la forma degli occhi (un catalogo piccolo), quella del naso, quella della bocca, della mascella, allora pochi cataloghi di poche voci ciascuno generano, combinandosi, miliardi di volti distinti. La perdita di informazione è reale — due volti con occhi, naso, bocca e mascella della stessa categoria diventano indistinguibili — ma è locale e controllata. PQ è esattamente questo: descrivere un vettore non come un tutto, ma come la combinazione di poche parti, ciascuna scelta da un alfabeto piccolo.

Le due idee insieme — perché si combinano bene

Un ultimo angolo, che anticipa la sezione meccanica: IVF e PQ non solo convivono, si potenziano. IVF risponde alla domanda “quali vettori vale la pena guardare”, PQ alla domanda “come guardarne uno senza pagarlo caro”. La prima è una riduzione di quantità, la seconda di costo unitario. Moltiplicate, danno il risultato che né l’una né l’altra raggiungerebbe da sola: visitare l’uno per cento dei vettori e, per ciascuno di quelli, spendere una somma di byte invece di un prodotto scalare pieno.

C’è anche una sinergia più sottile, che vedremo nella meccanica. Una volta che IVF ha assegnato un vettore a una cella, PQ non comprime il vettore grezzo ma il suo residuo — quanto il vettore si discosta dal centroide della cella. I residui sono vettori più piccoli e più “ordinati” dei dati grezzi, e un alfabeto piccolo li descrive meglio. È come dare un indirizzo: invece di coordinate assolute sul pianeta, “a 200 metri dalla piazza, in direzione nord” — più corto e più preciso, una volta che la piazza è fissata. IVF fissa la piazza, PQ descrive lo scostamento.

Il resto del capitolo segue questa divisione del lavoro. La sezione meccanica tratta prima PQ — come si codifica, come si stima una distanza da un codice — poi IVF — come si partiziona, come si interroga — e infine la loro fusione nell’indice IVFADC. Gli esempi numerici e di codice mostrano i due meccanismi in azione separatamente e insieme; la sezione “Dove si rompe” raccoglie i limiti di entrambi, perché un indice IVFPQ eredita le debolezze di tutte e due le tecniche, non solo di una.

La meccanica

PQ — come si codifica un vettore

Si parte da un vettore x in R^d. Si sceglie m, il numero di sotto-vettori, con d divisibile per m; e k*, il numero di centroidi per ogni sotto-quantizzatore — quasi sempre 256, perché un indice tra 0 e 255 sta esattamente in un byte (256 = 2 elevato a 8).

La costruzione ha tre passi:

1. Spezza x in m sotto-vettori: x = (u_1, ..., u_m), ognuno in R^(d/m). Lo split è posizionale: le prime d/m coordinate formano u_1, le successive d/m formano u_2, e così via. Niente di sofisticato — è OPQ, più avanti, a rendere intelligente questo taglio.
2. Addestra i codebook: per ogni sotto-spazio j, in fase di build, si esegue k-means su tutti i sotto-vettori u_j del dataset. Si ottengono m codebook C_1, ..., C_m, ognuno con k* centroidi. Notare che i codebook sono m e distinti: il sotto-spazio 1 ha il suo alfabeto, il sotto-spazio 2 il suo, perché le coordinate iniziali e finali di un embedding hanno in genere statistiche diverse.
3. Codifica x: per ogni j, si trova nel codebook C_j il centroide più vicino a u_j e si salva il suo indice i_j, un numero tra 0 e k* - 1. Il codice di x è la tupla (i_1, ..., i_m). Da questo momento il vettore x non serve più: l’indice conserva solo il codice. Ricostruirlo, se servisse, significa concatenare gli m centroidi indicati dal codice — e si riottiene non x ma la sua approssimazione.

La dimensione del codice è m × log2(k*) bit. Con m = 8 e k* = 256: 8 × 8 = 64 bit, cioè 8 byte. Confronto: un vettore di 128 numeri in virgola mobile a 32 bit occupa 512 byte. Il codice PQ a 8 byte è 64 volte più piccolo. Un vettore di 512 dimensioni — 2048 byte da grezzo — con m = 64 codici da un byte diventa 64 byte: 32 volte più piccolo. È la “riduzione di memoria drastica” che rende PQ interessante.

Due parametri controllano la compressione, e conviene tenerli separati. m regola in quanti pezzi si spezza il vettore: più pezzi significa pezzi più corti, ognuno più facile da quantizzare bene, ma anche più byte di codice. k* regola quante voci ha ogni codebook: più voci significa quantizzazione più fine di ogni pezzo, ma più bit per indice. Quasi tutti gli indici reali fissano k* = 256 — un byte tondo per indice, comodo per la memoria e per le istruzioni della CPU — e usano m come unica leva della compressione. Aumentare m riduce l’errore di quantizzazione e allunga il codice; ridurlo fa il contrario. Il valore di m è quindi la traduzione diretta del budget di byte per vettore in una scelta di accuratezza.

Figura in preparazione

fig-2: l’encoding PQ di un vettore. In alto un vettore lungo diviso in m=4 blocchi colorati. Ogni blocco punta al suo codebook (4 piccole griglie di centroidi); dentro ciascun codebook un centroide è cerchiato. In basso il codice risultante: 4 numeri (indici), una riga di byte. A lato il confronto dimensioni: “vettore grezzo: d float” vs “codice PQ: m byte”. Label: “sotto-vettore”, “codebook del sotto-spazio”, “centroide più vicino”, “codice = m indici”. Titolo “Product quantization: da un vettore lungo a m byte”

PQ — il calcolo della distanza: SDC e ADC

Comprimere serve a poco se poi calcolare una distanza richiede di decomprimere. Il colpo di genio di PQ è che la distanza si stima direttamente dai codici, e quasi gratis. Ci sono due modi.

Il primo è la SDC (Symmetric Distance Computation, calcolo simmetrico della distanza): si quantizza anche la query, e si stima la distanza tra query e vettore database come distanza tra le loro due versioni quantizzate. Le distanze tra centroidi sono tutte precalcolabili in tabelle, quindi il confronto è velocissimo, e l’indice può tenere in memoria una tabella centroide-contro-centroide che vale per qualunque query. Il difetto è di precisione: anche la query è approssimata, e l’errore di quantizzazione si somma su entrambi i lati. Due vettori realmente vicini possono, una volta quantizzati entrambi, finire su centroidi che li fanno sembrare più distanti — o, peggio, più vicini — di quanto siano.

Il secondo, e quello che si usa quasi sempre, è la ADC (Asymmetric Distance Computation, calcolo asimmetrico). Qui la query non viene quantizzata: resta esatta. È “asimmetrica” proprio perché i due lati sono trattati diversamente — la query esatta, i vettori database codificati — e questa asimmetria è una scelta deliberata, non un caso: tenere esatto il lato query riduce l’errore rispetto alla SDC. È un punto su cui ci si confonde spesso, e conviene fissarlo: ADC non quantizza la query.

Perché ADC sia più precisa di SDC c’è una ragione che vale la pena rendere esplicita. La quantizzazione introduce un errore su ogni vettore che tocca. SDC quantizza due vettori — query e database — quindi accumula due errori; ADC ne quantizza uno solo. Il paper del 2011 lo formalizza mostrando che la stima ADC è uno stimatore della distanza vera con un bias più contenuto di SDC, e per questo, a parità di codici, dà un recall più alto. Il costo extra di ADC è minimo: una tabella in più da costruire per query, contro tabelle centroide-contro-centroide precalcolate una volta sola di SDC. Nella pratica quasi nessuno usa SDC; serve soprattutto come termine di paragone concettuale che chiarisce cosa ADC tiene esatto e perché conviene.

Ecco come funziona ADC. Arrivata la query q, la si spezza nei suoi m sotto-vettori. Per ogni sotto-spazio j e ogni centroide i del codebook C_j, si calcola la distanza al quadrato tra il sotto-vettore j della query e quel centroide. Il risultato è una lookup table (tabella di consultazione) di m righe per k* colonne — con m = 8 e k* = 256, una tabella di 2048 numeri. Questa tabella si calcola una volta sola per query.

Poi, per ogni vettore del database con codice (i_1, ..., i_m), la distanza stimata è:

dist_ADC(q, x)^2  ≈  table[1][i_1] + table[2][i_2] + ... + table[m][i_m]

m valori letti dalla tabella e sommati. Niente moltiplicazioni, niente accesso ai sotto-vettori originali: per ogni vettore database, m lookup e m addizioni. Il calcolo della distanza, il costo dominante del brute-force, diventa quasi gratuito.

In pseudocodice, riga per riga:

def adc_search(q, codes, codebooks, m, k_star, topk):
    # codebooks[j]: matrice k_star x (d/m), i centroidi del sotto-spazio j
    # codes[v]:     tupla di m indici, il codice PQ del vettore database v

    # FASE 1 — costruisci la lookup table.
    # Per ogni sotto-spazio e ogni centroide: distanza al quadrato
    # tra il pezzo j della query e quel centroide. Costo: m * k_star,
    # indipendente da N (la dimensione del dataset).
    sub = split(q, m)                          # m sotto-vettori della query
    table = [[l2_sq(sub[j], codebooks[j][i])
              for i in range(k_star)]
             for j in range(m)]

    # FASE 2 — scorri i vettori database. Per ognuno, somma m valori
    # letti dalla tabella. Nessuna moltiplicazione, nessun accesso
    # ai vettori grezzi. Costo: N * m addizioni.
    best = max_heap()
    for v, code in enumerate(codes):
        d = 0.0
        for j in range(m):
            d += table[j][code[j]]             # un lookup, una somma
        best.push((d, v))
        if len(best) > topk:
            best.pop_max()                     # tieni solo i topk migliori
    return sorted(best)

La fase 1 costa m × k* calcoli di distanza su sotto-vettori corti, e non dipende da N. La fase 2 è lineare in N, ma con m piccolo e solo addizioni: nessuna moltiplicazione, nessun accesso alla memoria dei vettori grezzi. Il lavoro pesante, quello che cresce con la dimensione d, è confinato nella fase 1 a costo fisso. È questo che rende ADC veloce: non riduce il numero di vettori esaminati — quello lo fa IVF — ma rende quasi nullo il costo di esaminarne uno.

IVF — costruzione e query

IVF è più semplice da descrivere. In fase di build si esegue k-means con nlist centroidi z_1, ..., z_nlist sull’intero dataset. Questo k-means si chiama coarse quantizer, quantizzatore grossolano, per distinguerlo dai sotto-quantizzatori fini di PQ. Per ogni vettore x del dataset si trova il centroide più vicino e si aggiunge x alla inverted list di quella cella — la lista dei vettori che le appartengono.

La query usa un parametro, nprobe (nel paper del 2011 è chiamato w):

1. Si calcola la distanza dalla query q ai nlist centroidi e si selezionano i nprobe centroidi più vicini.
2. Si scorrono solo le inverted list di quelle nprobe celle.
3. Sui candidati raccolti si calcola la distanza e si tengono i topk migliori.

In pseudocodice, build e query di un IVF puro:

def ivf_build(dataset, nlist):
    # FASE BUILD — addestra il coarse quantizer e riempi le liste.
    centroidi = kmeans(dataset, nlist)         # nlist celle di Voronoi
    liste = [[] for _ in range(nlist)]
    for vid, x in enumerate(dataset):
        c = argmin_index(dist(x, z) for z in centroidi)
        liste[c].append(vid)                   # x entra nella lista della sua cella
    return centroidi, liste

def ivf_query(q, centroidi, liste, dataset, nprobe, topk):
    # FASE QUERY — scegli le nprobe celle, scorri solo quelle.
    ordine = sorted(range(len(centroidi)),
                    key=lambda c: dist(q, centroidi[c]))
    celle = ordine[:nprobe]                    # le nprobe celle più vicine
    best = max_heap()
    for c in celle:
        for vid in liste[c]:                   # solo i vettori di queste celle
            d = dist(q, dataset[vid])
            best.push((d, vid))
            if len(best) > topk:
                best.pop_max()
    return sorted(best)

Riga per riga: il build esegue un k-means per ottenere nlist centroidi e poi smista ogni vettore nella lista del centroide più vicino. La query ordina i centroidi per vicinanza alla query, prende i primi nprobe, e calcola le distanze solo sui vettori che vivono in quelle celle. Tutto il resto del dataset non viene mai toccato. In un IVFADC, l’unica differenza è la riga d = dist(q, dataset[vid]): al posto della distanza esatta sul vettore grezzo si legge la stima ADC dal codice PQ, e i vettori grezzi non servono nemmeno più in memoria.

nprobe è la manopola recall/velocità di IVF. A nprobe = 1 si guarda solo la cella della query: veloce, ma il problema di bordo morde — recall basso. Alzando nprobe si visitano più celle, il recall sale, la latenza sale. All’estremo nprobe = nlist si ricade nella scansione completa: il senso di IVF è tenere nprobe molto più piccolo di nlist.

I numeri della documentazione di FAISS rendono concreto l’effetto. Su un indice IVF256,PQ32 con un milione di vettori, passare da nprobe = 1 a nprobe = 8 alza il recall da circa il 30 per cento a circa il 74 per cento, mentre la latenza per query sale da circa 136 microsecondi a circa 729 microsecondi. È il volto di IVF della curva recall-QPS già vista in ann-intro: i primi punti di recall costano poco, gli ultimi costano cari. Visitare otto celle invece di una recupera la gran parte dei vicini persi al bordo; spingere oltre raccoglie sempre meno vicini nuovi per ogni cella in più.

C’è poi nlist stesso, una scelta di build. Tante celle piccole significano che ognuna contiene pochi vettori — query più veloce, ma più celle da considerare e più rischio che il vicino finisca appena oltre il bordo. Una regola pratica diffusa nella documentazione di FAISS è nlist dell’ordine della radice quadrata di N. Vale la pena notare che il coarse quantizer è esso stesso un problema di nearest neighbor — “trova i nprobe centroidi più vicini” — su scala ridotta: per nlist molto grande, FAISS lo accelera usando un HNSW come coarse quantizer, ed è la IVF..._HNSW,... che si incontra nelle stringhe di configurazione.

IVF + PQ: l’indice IVFADC

Le due tecniche si combinano nell’indice che FAISS chiama, nella sua sintassi, IVFx,PQy — l’IVFADC del paper del 2011. Funziona così:

1. IVF partiziona lo spazio in x = nlist celle, con il coarse quantizer.
2. Dentro ogni cella, i vettori non sono memorizzati grezzi: sono codificati con PQ a y byte. E qui c’è un raffinamento importante. Non si quantizza il vettore x, ma il suo residuo r = x − z, la differenza tra il vettore e il centroide della sua cella IVF. I residui sono vettori più piccoli e più concentrati attorno all’origine dei vettori grezzi, quindi PQ li codifica con meno errore a parità di byte. È il flag by_residual di FAISS, attivo per default in questo indice.
3. Query: IVF seleziona le nprobe celle; dentro ciascuna, ADC stima le distanze leggendo dalla lookup table. Poiché si quantizzano i residui, la tabella va costruita relativamente al centroide di ogni cella visitata — un dettaglio implementativo, ma è la ragione per cui ADC e IVF si incastrano bene.

Il guadagno è la somma dei due: IVF taglia il numero di vettori esaminati, PQ taglia memoria e costo per vettore. Un miliardo di vettori a y = 8 byte occupa circa 8 gigabyte di codici — più i centroidi e l’overhead delle liste — invece dei terabyte dei float grezzi. È, in una riga, il motivo per cui IVFPQ scala a miliardi di vettori su una sola macchina mentre HNSW no.

Figura in preparazione

fig-3: schema dell’indice IVFADC. A sinistra lo spazio diviso in celle IVF (coarse quantizer, k-means con nlist centroidi). Una cella ingrandita: dentro, i vettori non sono grezzi ma codici PQ corti (rappresentati come righe di byte). Una query in alto: una freccia “1. seleziona nprobe celle” verso 3 celle evidenziate; una freccia “2. ADC con lookup table” dentro le celle selezionate. Label: “coarse quantizer (IVF)”, “residuo r = x - z”, “codice PQ (y byte)”, “lookup table ADC”. Titolo “IVFADC: IVF sceglie le celle, PQ comprime i vettori dentro”

Il build: due fasi di addestramento

Vale la pena fermarsi sul momento del build, perché IVFPQ ha un costo di costruzione che il brute-force e, in parte, HNSW non hanno. Costruire un indice IVFADC richiede due addestramenti distinti, entrambi a base di k-means.

Il primo addestra il coarse quantizer: k-means con nlist centroidi su un campione del dataset. È l’addestramento dell’IVF, e produce le celle di Voronoi.

Il secondo addestra i codebook PQ: per ciascuno degli m sotto-spazi, k-means con k* centroidi sui sotto-vettori — più precisamente, sui sotto-vettori dei residui, dato che l’indice quantizza i residui. È l’addestramento della PQ, e produce gli m cataloghi.

Solo dopo questi due addestramenti l’indice può ricevere i vettori veri: ogni vettore viene assegnato a una cella (coarse quantizer) e il suo residuo codificato (codebook PQ). In FAISS questi due passi corrispondono alle chiamate train e add, ed è il motivo per cui un indice IVFPQ va addestrato prima di essere riempito — un dettaglio che sorprende chi arriva dal brute-force, dove il dataset è già la struttura. L’addestramento va fatto su un campione rappresentativo: se i vettori usati per il train non rispecchiano la distribuzione di quelli che finiranno nell’indice, le celle e i codebook nascono già storti. È una differenza pratica forte rispetto a HNSW, che non ha una fase di training separata e si costruisce per inserimenti successivi.

I conti del costo: dove vanno i soldi

Conviene mettere in fila i costi di una query IVFADC, perché chiariscono dove ciascuna tecnica interviene. La query si scompone in tre voci.

La prima è la ricerca del coarse quantizer: confrontare la query con i nlist centroidi IVF per trovare le nprobe celle più vicine. È un nearest neighbor in piccolo, costo proporzionale a nlist × d. Per nlist modesto è trascurabile; per nlist molto grande diventa il collo di bottiglia, ed è il motivo per cui FAISS può mettere un HNSW al posto del confronto esaustivo.

La seconda è la costruzione della lookup table di ADC: m × k* distanze su sotto-vettori corti. Con i numeri tipici — m = 8, k* = 256 — sono qualche migliaio di operazioni, e soprattutto non dipendono da N. Pagata una volta per query.

La terza è la scansione delle inverted list selezionate: per ognuno dei vettori nelle nprobe celle, m lookup e m addizioni. È l’unica voce che cresce con la dimensione del dataset, ma cresce piano: con nprobe/nlist piccolo si tocca una frazione minuscola di N, e ogni tocco costa m somme invece di d moltiplicazioni.

Il confronto con il brute-force di ann-intro è istruttivo. Il brute-force paga N × d moltiplicazioni-e-somme. IVFADC paga, in ordine di grandezza, (nprobe/nlist) × N × m addizioni — la frazione di vettori toccati per il costo ridotto di ognuno. Con nprobe/nlist di un centesimo e m molto più piccolo di d, sono due o tre ordini di grandezza in meno. Il guadagno è il prodotto di due fattori indipendenti: ne guadagna IVF, ne guadagna PQ.

Questa scomposizione del costo ha anche un valore diagnostico. Se una query IVFADC è inaspettatamente lenta, le tre voci dicono dove guardare. Coarse quantizer lento: nlist è troppo grande per un confronto esaustivo, serve un HNSW come quantizzatore. Scansione lenta: o nprobe è alto, o si è capitati in una cella sovradimensionata. Costruzione della tabella che pesa: m × k* è grande, raro con i valori tipici. Sapere in quale delle tre voci finisce il tempo evita di tarare il parametro sbagliato.

I conti della memoria

Vale la pena fare i conti della memoria di un indice IVFADC, perché è il vincolo che giustifica tutta la tecnica. Le voci sono tre.

I codici PQ sono il grosso: N vettori, ognuno y byte di codice. Per un miliardo di vettori a y = 8 byte sono 8 gigabyte; a y = 64 byte, 64 gigabyte. È una funzione lineare di N e di y, e y è la leva diretta.

Gli identificatori dei vettori: ogni inverted list, oltre ai codici, tiene gli ID dei vettori che contiene, tipicamente 8 byte l’uno. Per un miliardo di vettori sono altri 8 gigabyte. Una voce che molti dimenticano nel preventivo, e che a y piccolo può addirittura superare i codici stessi.

I centroidi: il coarse quantizer ha nlist centroidi da d float; i codebook PQ hanno m × k* sotto-centroidi. Per nlist = 65536, d = 768, sono circa 200 megabyte; i codebook PQ qualche megabyte. È la voce più piccola, e non scala con N: una volta addestrato, l’indice paga questo costo fisso indipendentemente da quanti vettori contiene.

La somma chiarisce la regola pratica. La memoria è dominata da N × (y + 8) byte. A parità di N, l’unica leva grossa è y, cioè m. Ed è il motivo per cui la prima domanda nel dimensionare un IVFPQ è “quanti byte per vettore mi posso permettere”, e da lì discende tutto il resto.

Le varianti: OPQ e residual quantization

Due raffinamenti meritano una riga, perché compaiono spesso nelle configurazioni reali.

OPQ (Optimized Product Quantization) parte da un’osservazione: PQ spezza il vettore in blocchi contigui, ma se l’informazione è distribuita male tra le coordinate — alcuni blocchi pieni di varianza, altri quasi piatti — la compressione spreca centroidi sui blocchi piatti e ne ha troppo pochi su quelli ricchi. OPQ applica al vettore una rotazione ortogonale R, appresa in fase di build, scelta per bilanciare la varianza tra i sotto-spazi e decorrelarli prima dello split. È una rotazione, quindi non altera le distanze: cambia solo come lo spazio viene tagliato in blocchi, rendendo PQ più efficace a parità di byte. In FAISS è il prefisso OPQ nella stringa, per esempio OPQ64,IVF4096,PQ64.

Un’immagine aiuta. Immagina di dover dividere in quattro mazzi un mucchio di carte di valore molto diverso, e di doverlo fare tagliando il mucchio in quattro fette senza rimescolarlo. Se le carte preziose sono tutte in fondo, tre fette saranno povere e una ricchissima: una divisione pessima. Rimescolare il mucchio prima di tagliarlo distribuisce il valore in modo uniforme, e le quattro fette diventano comparabili. La rotazione di OPQ è quel rimescolamento: ridistribuisce la varianza tra le coordinate in modo che, quando PQ taglia in blocchi contigui, nessun blocco resti povero e nessuno sovraccarico. Su molti dataset di embedding reali OPQ aggiunge qualche punto di recall senza costare un byte in più — il costo è solo una moltiplicazione matrice-vettore in più per query, irrisoria.

La residual quantization è l’idea, già vista sopra, di quantizzare i residui invece dei vettori grezzi. La sua versione spinta — LOPQ (Locally Optimized Product Quantization, Kalantidis e Avrithis, CVPR 2014) — addestra un product quantizer diverso per ogni cella IVF, ottimizzato sulla distribuzione locale dei residui di quella cella. Più accurato, più pesante da costruire e memorizzare. È la stessa logica del residuo portata all’estremo: i residui di una singola cella sono ancora più unimodali, quindi ancora più facili da quantizzare bene.

IVF e PQ da sole, e come scegliere

Conviene non perdere di vista che IVF e PQ restano due tecniche autonome. Si può usare IVF senza PQ — in FAISS è IVFx,Flat: lo spazio è partizionato, ma dentro le celle i vettori sono grezzi. Si guadagna velocità rispetto al brute-force perché si visitano poche celle, ma non si guadagna memoria: i vettori occupano i loro byte interi. È la scelta giusta quando i dati stanno comodi in RAM e si vuole solo accelerare la query senza accettare l’errore di quantizzazione.

Si può usare PQ senza IVF — in FAISS PQy puro: i vettori sono compressi ma non partizionati, e una query li scorre tutti, valutando ciascuno con ADC. Si guadagna memoria e si abbassa il costo per vettore, ma il costo resta lineare in N senza lo sconto del partizionamento. Ha senso per dataset di taglia media dove la memoria è il problema ma N non è ancora così grande da rendere insostenibile una scansione di codici corti.

La combinazione IVFx,PQy prende entrambi gli sconti, ed è la configurazione che si incontra di gran lunga più spesso a scala. Ma la scelta tra le tre non è automatica: dipende da cosa stringe. Se stringe solo la latenza e la RAM abbonda, IVF,Flat o addirittura HNSW. Se stringe la memoria ma N è gestibile, PQ puro. Se stringono entrambe — il caso dei miliardi di vettori — IVF,PQ. La regola pratica della guida di FAISS “choose an index” è proprio questa: si parte dalla domanda “cosa non entra nel budget”, non dalla domanda “qual è l’indice migliore”.

Una mappa sintetica delle configurazioni, prima degli esempi:

Stringa FAISS	IVF	PQ	Memoria	Quando
Flat	no	no	massima (vettori grezzi)	dataset piccolo, recall esatto
IVFx,Flat	sì	no	come i dati grezzi	latenza il vincolo, RAM abbonda
PQy	no	sì	compressa, nessuno sconto su N	memoria stretta, N moderato
IVFx,PQy	sì	sì	compressa, sconto su N	miliardi di vettori, RAM stretta
OPQy,IVFx,PQy	sì	sì	come sopra	come sopra, qualche punto di recall in più

Le righe sono i punti che il resto del capitolo ha costruito: ogni “sì” è uno sconto, ogni sconto ha un prezzo in recall, e la riga giusta è quella che entra nel budget del caso concreto.

Esempi

Esempio numerico: la lookup table di ADC

Si prenda un caso minuscolo per vedere i numeri. Dimensione d = 8, numero di sotto-spazi m = 2 — quindi due blocchi di dimensione 4 — e k* = 4 centroidi per codebook (un codebook giocattolo).

Un vettore database x è stato codificato come (i_1, i_2) = (3, 1): il suo primo blocco è stato assegnato al centroide numero 3 del codebook 1, il secondo blocco al centroide 1 del codebook 2.

Arriva la query q. La si spezza in due pezzi e si costruisce la tabella 2×4. La riga 1 sono le quattro distanze al quadrato tra il primo pezzo di q e i quattro centroidi del codebook 1; la riga 2 idem per il secondo pezzo. Supponiamo di ottenere:

table[1] = [0.9, 0.4, 1.2, 0.1]
table[2] = [0.3, 0.7, 0.5, 0.6]

La distanza stimata di x è table[1][3] + table[2][1] = 0.1 + 0.7 = 0.8. Per un altro vettore con codice (0, 2) sarebbe table[1][0] + table[2][2] = 0.9 + 0.5 = 1.4. Il primo è più vicino alla query. Per stimare la distanza di un milione di vettori si ripete solo l’ultimo passo — due lookup e una somma a testa — senza mai ricostruire un vettore né moltiplicare nulla. La tabella, costruita una volta, è il lavoro; tutto il resto è lettura.

Si noti dove sta l’approssimazione. Il valore 0.8 non è la distanza vera tra la query e il vettore x originale: è la distanza tra la query e la versione quantizzata di x, quella che cade sui centroidi 3 e 1. Se nel blocco 1 ci fossero due vettori database diversi entrambi assegnati al centroide 3, riceverebbero lo stesso identico contributo table[1][3] — diventerebbero indistinguibili in quel blocco. È l’errore di quantizzazione reso visibile su un caso minuscolo: la stima è buona, ma è una stima, e due vettori vicini in uno stesso blocco perdono la loro differenza. Aumentare k* o m rende i blocchi più fini e questo collasso più raro, al prezzo di codici più lunghi.

Esempio numerico: assegnazione a una cella e problema di bordo

Un caso bidimensionale, per vedere il problema di bordo con i numeri. Tre centroidi IVF, ottenuti da k-means: z_1 = (0, 0), z_2 = (10, 0), z_3 = (5, 9). Un vettore database x = (4, 1). Le distanze al quadrato dai tre centroidi sono: da z_1, 16 + 1 = 17; da z_2, 36 + 1 = 37; da z_3, 1 + 64 = 65. Il minimo è z_1: x finisce nella inverted list della cella 1.

Arriva una query q = (5, 0), esattamente a metà strada tra z_1 e z_2. Le distanze al quadrato: da z_1, 25; da z_2, 25; da z_3, 81. La cella più vicina è z_1 (a pari merito con z_2, ma si sceglie una): con nprobe = 1 si visita solo la lista di z_1. La distanza vera tra q e x è 1 + 1 = 2: minuscola, x è quasi certamente il vicino cercato, e per fortuna x sta nella cella 1. Ma se x fosse stato (6, 1) — distanza da z_1 pari a 37, da z_2 pari a 17 — sarebbe finito nella cella 2, mentre la query, assegnata alla cella 1, non l’avrebbe mai visto. Eppure la distanza vera tra q = (5,0) e (6,1) è solo 2. È il problema di bordo in numeri: la query e il suo vicino, vicinissimi tra loro, cadono in celle diverse perché il confine di Voronoi passa proprio in mezzo. Con nprobe = 2 si visita anche la cella 2 e il vicino si recupera. Nessun valore di nprobe inferiore a nlist elimina del tutto il rischio: lo si rende solo raro.

Esempio in codice: leggere una stringa index_factory di FAISS

FAISS costruisce gli indici da stringhe descrittive, leggibili da sinistra a destra come una pipeline. Prendiamo:

index = faiss.index_factory(512, "IVF4096,PQ64")
index.train(vettori_di_addestramento)   # k-means: coarse quantizer + codebook PQ
index.add(tutti_i_vettori)
index.nprobe = 32                        # manopola recall/velocità a query time
distanze, indici = index.search(query, k=10)

Decodifichiamo la stringa. Il 512 è la dimensione dei vettori. IVF4096 significa 4096 celle: in fase di train, k-means apprende 4096 centroidi — il coarse quantizer. PQ64 significa 64 sotto-vettori, con il default di 8 bit ciascuno, quindi 64 byte per vettore: 512 numeri in virgola mobile, da 2048 byte, compressi a 64 byte, un fattore 32. A query time index.nprobe = 32 dice di visitare 32 celle su 4096.

Per confronto, "IVF4096,Flat" userebbe IVF senza compressione — vettori grezzi nelle celle: più recall, molta più memoria. E "OPQ64,IVF4096,PQ64" antepone una rotazione OPQ appresa. La stringa rende esplicita la composizione: ogni segmento è uno stadio, e cambiare un segmento cambia un punto del trade-off.

Esempio di dimensionamento: scegliere nlist, nprobe e m

Un esempio di ragionamento, non di codice, perché dimensionare un indice IVFPQ è la decisione che più spesso viene presa a caso. Dataset: 100 milioni di embedding a d = 768. Vincoli: l’indice deve stare in 16 gigabyte di RAM, e il recall@10 deve superare 0,9 prima del rerank.

Si parte dalla memoria, perché è il vincolo rigido. 100 milioni di vettori in 16 gigabyte danno un budget di circa 160 byte per vettore, comprensivo di overhead. Lasciando margine per liste e centroidi, il codice PQ può stare sui 96-128 byte. Con codici da un byte significa m tra 96 e 128 sotto-vettori: 768 è divisibile per entrambi (768/96 = 8, 768/128 = 6), quindi i sotto-vettori avrebbero dimensione 8 o 6. Si parte da m = 96 e si misura.

Poi nlist. La regola pratica della radice quadrata di N darebbe circa 10000 celle; per un dataset di questa taglia un valore tra 4096 e 16384 è ragionevole. nlist più alto rende le celle più piccole — query più rapida una volta scelte le celle — ma sposta lavoro sul coarse quantizer e acuisce il problema di bordo. Si fissa un valore di partenza, per esempio 8192, e lo si lascia.

Resta nprobe, l’unico parametro che si tocca dopo il build. Si parte basso, nprobe = 1, si misura il recall su un set di query con ground-truth da brute-force, e lo si alza — 4, 8, 16, 32 — finché il recall non supera la soglia. Ogni raddoppio di nprobe aggiunge latenza; ci si ferma al primo valore che passa. Se nemmeno nprobe alto raggiunge 0,9, il problema non è di bordo ma di compressione: m è troppo piccolo, e va rifatto il build con codici più lunghi — o ci si appoggia di più al rerank. Questa è la sequenza: memoria fissa m, una stima fissa nlist, e nprobe si accorda a posteriori. Confondere quale parametro tocca quale errore è la causa numero uno di indici tarati male.

Esempio reale: una knowledge base da un miliardo di chunk

Una knowledge base web-scale per un sistema RAG: un miliardo di chunk di testo, ognuno un embedding a d = 768 in virgola mobile a 32 bit. Da non compressi sono circa 3 terabyte — fuori da qualunque RAM di una singola macchina.

Con un indice IVF65536,PQ96 — 65536 celle, 96 byte per vettore — i conti cambiano. La memoria dei codici è un miliardo per 96 byte, cioè circa 96 gigabyte; aggiungendo centroidi e overhead delle liste si resta nell’ordine del centinaio di gigabyte, una cifra che un server con molta RAM regge, o che si distribuisce su pochi nodi. A query time nprobe = 64 visita 64 celle su 65536, circa lo 0,1% dei vettori, e ciascun candidato è valutato con ADC a costo quasi nullo.

Il prezzo è onesto: le distanze sono stimate, non esatte, e il recall è più basso di quello di un indice non compresso. Per questo lo schema reale spesso aggiunge un passo di rerank — i migliori candidati di IVFPQ vengono riordinati ricalcolando la distanza sui vettori grezzi, tenuti su SSD proprio per questo. IVFPQ fa il grosso del filtraggio in memoria; il rerank rifinisce su disco solo la manciata di candidati che conta. In FAISS questa combinazione si scrive aggiungendo ,RFlat in coda alla stringa dell’indice: lo stadio finale di refine ricalcola le distanze esatte sui candidati prima di restituire il top-k. La divisione del lavoro è netta: IVFPQ è un filtro veloce e approssimato che lavora in RAM su miliardi di vettori, il rerank è un controllo esatto e costoso che lavora su disco su poche decine di candidati. Insieme danno recall alto a memoria bassa, cosa che nessuno dei due raggiungerebbe da solo.

Esempio di confronto: IVFPQ contro HNSW in numeri

Per fissare il trade-off, alcuni numeri dalla documentazione di FAISS e dai tutorial di Pinecone, su un milione di vettori SIFT a d = 128:

Indice	Memoria	Recall	Latenza per query
Flat (esatto, brute-force)	~520 MB	100%	alta
IVF256,PQ32	~40 MB	~74% (a nprobe=8)	~730 µs
IVF4096_HNSW,Flat	~523 MB	~90%	~550 µs

La lettura è netta. HNSW sta più in alto sulla frontiera recall-latenza, ma occupa più o meno la memoria dei dati grezzi — qui circa tredici volte l’indice IVFPQ. IVFPQ rinuncia a un po’ di recall e a un po’ di latenza, e in cambio comprime di un ordine di grandezza. A un milione di vettori la differenza è una comodità; a un miliardo è la differenza tra “entra in RAM” e “non entra”. Non c’è un vincitore assoluto: c’è una scelta dettata dal budget di memoria e dal recall che il prodotto richiede davvero.

Applicazioni pratiche

IVF e product quantization, da sole o combinate, sono l’ossatura della ricerca vettoriale alla scala più grande.

I vector database per corpora enormi le usano come indice di default quando i dati non entrano in RAM da non compressi. FAISS è la libreria di riferimento; Milvus e altri database vettoriali espongono IVFx,PQy (o la variante con OPQ) tra i tipi di indice selezionabili. Quando un vector database, configurando un indice, chiede quante celle e quanti byte per vettore, sta chiedendo nlist e m: i parametri di questo capitolo.

La ricerca su disco è un’applicazione diretta della compressione. I codici PQ sono così piccoli che molti possono restare in RAM mentre i vettori grezzi — necessari solo per l’eventuale rerank finale — stanno su SSD. PQ è ciò che rende praticabile cercare in un dataset più grande della memoria. Il capitolo successivo, ann-scann-diskann (in preparazione), mostra DiskANN, che spinge oltre l’idea di un indice che vive su disco.

Il RAG su grandi corpora è il consumatore moderno: knowledge base aziendali o web-scale con un numero di chunk nell’ordine dei miliardi. IVFPQ tiene l’indice in un budget di RAM sostenibile dove un indice non compresso costerebbe un’infrastruttura sproporzionata. Stessa logica per la memoria a lungo termine degli agenti: un archivio di esperienze che cresce senza limite, e la compressione tiene il costo sotto controllo.

Per la memoria di un agente c’è un’aggravante che rende IVFPQ interessante e insieme delicato. Quella memoria non è un corpus statico: cresce a ogni interazione, e i nuovi vettori possono cadere in regioni dello spazio che il train iniziale non ha visto. IVF inserisce comunque — assegna il vettore alla cella più vicina, qualunque essa sia — ma se la distribuzione si sposta a lungo, le celle e i codebook addestrati all’inizio invecchiano. Per archivi che evolvono molto, va messa in conto una riaddestramento periodico dell’indice, esattamente la situazione che la sezione “Dove si rompe” descrive in dettaglio.

Fuori dal mondo LLM resta viva l’applicazione storica: la visual search e la reverse image search su descrittori SIFT e GIST — il caso d’uso per cui Jégou e colleghi inventarono la tecnica nel 2011. E ci sono i sistemi di raccomandazione su cataloghi enormi, dove utenti e prodotti sono vettori e “item simili a questo” è una query k-NN: a centinaia di milioni di item, la compressione PQ è ciò che tiene l’indice in un singolo nodo.

Un punto operativo che lega tutti questi casi: quando un vector database con un corpus grande chiede, in fase di configurazione dell’indice, un numero di “partizioni” o “liste” e un numero di “byte per vettore” o “sotto-quantizzatori”, sta chiedendo nlist e m. Non sono dettagli esoterici da lasciare al default: sono il punto sulla frontiera recall-memoria, e questo capitolo è la mappa per sceglierli con cognizione invece che a caso.

Il ponte: PQ e la quantizzazione dei pesi dei modelli

Vale la pena segnare un parallelo, dichiarandone la classe. La product quantization comprime vettori-dato sostituendo numeri ad alta precisione con codici da un alfabeto piccolo, e accetta in cambio un errore controllato. La quantizzazione dei pesi dei modelli — int8, int4, e i metodi GPTQ, AWQ, GGUF della Parte XXIII — comprime vettori-peso con la stessa identica mossa: meno bit per numero, errore in cambio di memoria e velocità.

È un’analogia strutturale, non una filiazione. Storicamente sono filoni separati: PQ nasce nella computer vision per la ricerca di similarità, la quantizzazione dei pesi nasce per l’inferenza efficiente delle reti neurali, e nessuno dei due discende dall’altro. Ma la mossa concettuale è la stessa, e i due campi usano davvero la parola “quantizzazione” per operazioni imparentate. Riconoscere l’analogia aiuta a leggere entrambi i temi; spacciarla per filiazione sarebbe un errore di classe.

Dove si rompe

IVFPQ è un compromesso fatto di compromessi, e ciascuno ha un lato che cede. Conoscerli prima di metterlo in produzione evita diagnosi sbagliate.

La distanza ADC è una stima, non la vera distanza. È il punto da interiorizzare per primo. PQ è compressione lossy: due vettori diversi che, in un dato blocco, cadono sullo stesso centroide diventano indistinguibili in quel blocco. L’errore di quantizzazione è reale e misurabile, ed è la ragione strutturale per cui IVFPQ ha recall più basso di un indice non compresso a parità di tutto il resto. Non è un difetto da correggere: è il prezzo della compressione. Quando le risposte non bastano, una delle leve è aumentare m — più byte per vettore, meno errore — oppure aggiungere il rerank sui vettori grezzi.

Il problema di bordo non sparisce. nprobe lo riduce, non lo elimina, e a costo crescente. Il vero vicino di una query può sempre trovarsi in una cella che nprobe non ha incluso. Alzare nprobe fino a nlist lo eliminerebbe, ma a quel punto si è tornati alla scansione completa e IVF non serve più a niente. La cura non è solo nprobe alto: è anche scegliere bene nlist in fase di build, perché celle troppo grandi o troppo piccole spostano il punto di equilibrio.

Due fasi di approssimazione, due errori distinti. IVFPQ sbaglia in due modi indipendenti, e confonderli porta a debuggare la cosa sbagliata. C’è l’errore di omissione — IVF non ha visitato la cella giusta, il vicino è stato proprio escluso dai candidati — e c’è l’errore di stima — il vicino era tra i candidati, ma ADC ne ha stimato male la distanza e lo ha scartato. Il primo si cura con nprobe e nlist; il secondo con più byte PQ o con OPQ. Se il recall è basso, la domanda diagnostica è: i veri vicini non vengono raccolti, o vengono raccolti e poi mal ordinati? Sono due interventi diversi.

Il recall ha più di una manopola. A differenza di HNSW, che espone essenzialmente ef_search, IVFPQ ha almeno tre parametri che muovono il recall: nlist e nprobe dal lato IVF, e il numero di byte m dal lato PQ. Vanno tarati insieme: un nprobe generoso non recupera il recall perso da un PQ troppo aggressivo, e viceversa. È più potente come spazio di configurazione, ma anche più facile da sbagliare. Non esiste un default universale; va misurato sul proprio dataset, come insegnava la frontiera di Pareto di ann-intro.

Il training non è gratis e va fatto su dati rappresentativi. IVF e PQ richiedono entrambi un k-means in fase di build — il coarse quantizer e gli m sotto-quantizzatori. Questo k-means va addestrato su un campione di vettori rappresentativo del dataset reale. Se la distribuzione dei dati cambia nel tempo — query e documenti che migrano verso regioni dello spazio non viste in addestramento — i centroidi e i codebook invecchiano: le celle si sbilanciano, l’errore di quantizzazione cresce, e il recall si degrada in modo silenzioso. A differenza di un indice a grafo, che si aggiorna per inserimento incrementale, IVFPQ a volte va ri-addestrato da capo.

Le celle sbilanciate degradano il recall in modo non uniforme. k-means non garantisce celle di dimensione simile. Su dati con cluster densissimi accanto a regioni quasi vuote, alcune inverted list diventano enormi e altre quasi vuote. Le query che cadono nelle celle grandi sono lente — c’è molto da scorrere — e quelle vicine ai confini di regioni dense soffrono più il problema di bordo. Il recall medio può sembrare buono mentre una coda di query è servita male. Conviene guardare i percentili bassi, non solo la media.

La compressione PQ peggiora dove la dimensionalità intrinseca è alta. PQ assume implicitamente che ogni sotto-spazio abbia una struttura abbastanza semplice da essere catturata da k* centroidi. Quando i dati hanno una dimensionalità intrinseca molto alta — sono realmente complessi, al di là del numero nominale di coordinate — quei centroidi non bastano, e l’errore di quantizzazione cresce. OPQ aiuta, ridistribuendo la varianza tra i blocchi, ma non fa miracoli. Per dati molto complessi, la combinazione “compressione aggressiva + recall alto” semplicemente non è disponibile: si sceglie un lato.

Le cancellazioni lasciano cicatrici. Inserire un nuovo vettore in un indice IVFPQ è facile: lo si assegna alla cella più vicina e si codifica il residuo. Cancellarne uno lo è molto meno. Rimuovere fisicamente un codice da una inverted list significa rimaneggiare la lista; molte implementazioni preferiscono marcare il vettore come cancellato e ignorarlo a query time — le “lapidi” già incontrate in ann-intro. Le lapidi si accumulano: la lista resta lunga da scorrere anche se molti dei suoi elementi sono morti, e il recall effettivo cala perché i candidati utili sono diluiti tra i cancellati. Per un indice soggetto a molte cancellazioni va messa in conto una compattazione periodica, o una ricostruzione. I benchmark, che misurano quasi sempre indici statici, non lo mostrano.

Il filtraggio sui metadati non si combina gratis. Nei sistemi reali la query raramente è “i vicini di q” e basta: è “i vicini di q tra i documenti di questo cliente”. IVFPQ raccoglie candidati per prossimità geometrica, non per metadato; se il filtro è selettivo e lo si applica dopo, dei candidati raccolti ne sopravvivono pochissimi e il recall effettivo crolla. Applicarlo prima significa cercare in un sottoinsieme su cui le celle non sono state pensate. È lo stesso problema di filtered ANN che ann-intro segnalava per la famiglia a grafo: vale identico qui, e il “trova i vicini” pulito di questo capitolo resta un caso ideale che la produzione complica.

IVFPQ è quasi sempre un anello, non la catena. Come ann-intro notava per l’ANN in generale, IVFPQ raramente è l’ultimo passo. Il pattern tipico a scala è: IVFPQ recupera in fretta e in poca memoria un insieme largo di candidati, e un passo di rerank — distanza esatta sui vettori grezzi, o un modello più costoso — riordina solo quelli. In questo schema il recall di IVFPQ non deve essere altissimo: deve solo garantire che i veri vicini siano da qualche parte tra i candidati passati al rerank. Dimensionare l’indice come se fosse l’anello finale porta a spendere byte e nprobe dove non servono.

Messi in fila, questi limiti raccontano una sola cosa: IVFPQ è un indice da configurare, non da accendere. HNSW ha sostanzialmente una manopola e un comportamento prevedibile; IVFPQ ne ha tre, una fase di addestramento sensibile ai dati, e un degrado silenzioso se la distribuzione cambia. In cambio offre l’unica cosa che HNSW non può dare — entrare in un budget di RAM quando i vettori sono miliardi. È un baratto onesto, a patto di conoscerne tutte le clausole.

Collegamenti

• Approximate nearest neighbor: il problema — il problema ANN, le tre famiglie di metodi, la frontiera di Pareto recall-QPS e le metriche di distanza. IVF+PQ è la famiglia “a partizionamento e quantizzazione” annunciata lì.
• HNSW: la ricerca vettoriale come passeggiata su un grafo — la famiglia a grafo, il termine di paragone diretto: HNSW vince in recall e latenza, IVFPQ vince in memoria e scala a miliardi.
• La maledizione della dimensionalità — perché un unico codebook su tutto lo spazio non scala, e PQ deve spezzarlo in sotto-spazi.
• Norme e distanze — la distanza euclidea che ADC stima e il prodotto interno delle varianti per il maximum inner product search.
• Embedding: spazi e direzioni semantiche — da dove vengono i vettori densi che un indice IVFPQ comprime e indicizza.
• ann-scann-diskann (in preparazione) — ScaNN raffina la quantizzazione per il maximum inner product search; DiskANN spinge la ricerca su disco, idea imparentata con i codici PQ compatti.
• k-means (in preparazione) — l’algoritmo di clustering che addestra sia i centroidi IVF sia i codebook PQ: IVF e PQ sono entrambi k-means applicato in modo diverso.
• quantization-base (in preparazione) — il ponte: comprimere i pesi di un modello e comprimere vettori-dato condividono la stessa mossa, sostituire numeri ad alta precisione con codici da un alfabeto piccolo.
• rag-base (in preparazione) — il consumatore principale: RAG su corpora a scala di miliardi di chunk, dove l’indice deve stare in un budget di RAM ragionevole.
• vector-databases (in preparazione) — i prodotti che impacchettano IVFPQ dietro un’API operativa.

Per andare oltre

• Jégou, Douze, Schmid, Product Quantization for Nearest Neighbor Search (IEEE TPAMI 33(1), 2011; preprint arXiv:1102.3828). Il paper fondativo: introduce la product quantization, SDC e ADC, la lookup table e il sistema IVFADC. Validato fino a 2 miliardi di vettori. Lettura primaria sulla meccanica.
• 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 a scala da miliardi di vettori e sull’implementazione GPU.
• Ge, He, Ke, Sun, Optimized Product Quantization (CVPR 2013 / IEEE TPAMI). Introduce OPQ: la rotazione ortogonale appresa che bilancia la varianza tra i sotto-spazi prima dello split PQ.
• Documentazione di FAISS (faiss.ai), in particolare le pagine “The index factory” e “Guidelines to choose an index”: la sintassi delle stringhe IVFx,PQy e un percorso pratico per scegliere l’indice in base a numero di vettori, memoria disponibile e recall richiesto.
• Pinecone, Faiss: The Missing Manual — i capitoli “Composite Indexes & the Faiss Index Factory” e “Product Quantization”: tutorial con numeri concreti su memoria, recall e latenza ai vari nprobe, e una spiegazione accessibile di SDC e ADC.
• Kalantidis, Avrithis, Locally Optimized Product Quantization for Approximate Nearest Neighbor Search (CVPR 2014). La variante LOPQ: un product quantizer locale per ogni cella, addestrato sui residui di quella cella. Utile per capire fino a che punto si può spingere l’idea del residuo.
• Documentazione IndexIVF di FAISS (faiss.ai, sezione C++ API): la descrizione della struttura a inverted list, del coarse quantizer, del flag by_residual e dei parametri nprobe e max_codes. Riferimento per chi vuole leggere o estendere il codice.