Locality-sensitive hashing: una funzione hash progettata per far collidere i simili

Perché capovolgere la regola d’oro delle hash table — invece di disperdere gli input, far collidere apposta quelli vicini — produce una struttura dati con garanzie teoriche, e perché oggi serve più a deduplicare i corpora di training che a indicizzare embedding.

Perché questo capitolo

Una funzione hash, quella che sta sotto a un dict di Python o a una hash table del C++, ha una regola d’oro: disperdere. Due chiavi diverse devono finire, per quanto possibile, in posti scorrelati della tabella. Se hash("gatto") e hash("gatta") cadono nello stesso slot è una sfortuna — una collisione — che la tabella gestisce con catene o probing, e che, se diventa frequente, fa degradare la ricerca da costante a lineare. Disperdere bene è ciò che rende O(1) la hash table.

Il locality-sensitive hashing capovolge esattamente questa regola. È una funzione hash progettata perché due input vicini — due documenti quasi identici, due vettori quasi paralleli — finiscano nello stesso bucket con alta probabilità, e due input lontani ci finiscano con bassa probabilità. La collisione, che per la hash table è il difetto da minimizzare, qui diventa il segnale: se due elementi collidono spesso, probabilmente sono simili. È un’idea che, la prima volta che la si incontra, suona sbagliata. Vale la pena fermarsi finché non suona ovvia, perché tutto il capitolo poggia su questo ribaltamento.

Da quel ribaltamento nasce una struttura dati con un risultato teorico forte: la ricerca dei vicini diventa sublineare nel numero di elementi, con garanzie dimostrate. Per anni LSH è stato il riferimento accademico per la ricerca del vicino più prossimo.

Oggi la sua collocazione è cambiata. Come indice per la ricerca su embedding densi gli altri metodi della mini-serie ANN lo battono, ma come motore della deduplicazione dei corpora di training — rimuovere documenti quasi-identici da terabyte di testo prima di addestrare un modello linguistico — è oggi più centrale che mai. Questo capitolo chiude la mini-serie sull’approximate nearest neighbor e con essa la Parte VIII.

Vale la pena dire fin da subito perché un capitolo su LSH non è un’appendice erudita. La deduplicazione dei dati di training è uno dei pochi interventi che migliorano un modello linguistico senza toccarne l’architettura e senza spendere compute di addestramento: ripulisce solo l’input. E lo strumento standard con cui la si fa, su scala di miliardi di documenti, è MinHash combinato con LSH. Capire LSH significa capire come si decide cosa entra in un corpus di pre-training — una decisione che ha effetti misurabili sulla memorizzazione, sull’efficienza del training e sulla qualità finale del modello. È un pezzo dell’infrastruttura invisibile su cui poggiano i modelli moderni.

Contesto

LSH nasce nel filone teorico della ricerca del vicino più prossimo, lo stesso che Approximate nearest neighbor: il problema ha già tracciato. Il filone teorico — algoritmi e geometria computazionale — parte negli anni ‘90; quello industriale, attorno alla product quantization e a FAISS, matura negli anni 2010; quello a grafo, con HNSW, è del 2016. LSH è il più vecchio della famiglia, e la sua storia ha un dettaglio curioso: la pratica precede la teoria.

Nel 1997 Andrei Broder, ricercatore allora ad AltaVista — il principale motore di ricerca del web prima dell’arrivo di Google — pubblica con Steven Glassman, Mark Manasse e Geoffrey Zweig il paper Syntactic Clustering of the Web (Computer Networks, 1997). Il problema era concreto e fastidioso: l’indice di AltaVista conteneva milioni di pagine, molte delle quali erano copie quasi-identiche le une delle altre — mirror, ripubblicazioni, pagine con lo stesso contenuto e header diversi.

Restituirle tutte nei risultati di ricerca era inutile per l’utente. Servendo confrontare le pagine a coppie, con milioni di pagine, era impensabile. Broder introduce MinHash, una tecnica per stimare quanto due pagine si somigliano senza confrontarle parola per parola, abbastanza economica da girare sull’intero indice. MinHash è, a tutti gli effetti, una costruzione locality-sensitive — ma il nome generale della classe non esiste ancora.

Arriva un anno dopo. Nel 1998 Piotr Indyk, allora dottorando alla Stanford University, e il suo relatore Rajeev Motwani (informatico indo-statunitense, figura di riferimento degli algoritmi randomizzati) presentano a STOC 1998 — il Symposium on Theory of Computing dell’ACM, la conferenza di punta dell’informatica teorica — il paper Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. È lo stesso paper che ann-intro indica come punto di svolta teorico.

Il titolo dichiara il programma. La maledizione della dimensionalità — il fenomeno per cui la ricerca esatta dei vicini, in spazi a centinaia di dimensioni, degrada fino a non battere più la scansione di tutti i punti — si può “rimuovere”, a patto di accontentarsi di un risultato approssimato. Lo strumento con cui lo dimostrano è il locality-sensitive hashing: Indyk e Motwani danno alla classe il nome, la definizione formale, e la prima dimostrazione che produce una struttura dati sublineare.

Dopo il 1998 arrivano le costruzioni per le altre metriche. Nel 2002, sempre a STOC, Moses Charikar (informatico, allora a Princeton) pubblica Similarity Estimation Techniques from Rounding Algorithms e introduce lo schema basato su iperpiani casuali, oggi popolarmente chiamato SimHash: una famiglia LSH per la similarità coseno.

Nel 2004, al Symposium on Computational Geometry, Mayur Datar, Nicole Immorlica, Piotr Indyk e Vahab Mirrokni pubblicano Locality-Sensitive Hashing Scheme Based on p-Stable Distributions e danno la costruzione per la distanza euclidea diretta — senza bisogno, come dichiarano gli autori, di passare per un embedding intermedio. A metà degli anni 2000 LSH è quindi una cassetta degli attrezzi completa: una costruzione per ogni metrica importante.

Conviene anche fissare la cronologia rispetto al resto della mini-serie, perché chiarisce un equivoco. MinHash è del 1997, LSH come framework del 1998, SimHash del 2002, lo schema euclideo del 2004. La product quantization è del 2011, HNSW del 2016. LSH è dunque il più vecchio dei metodi ANN trattati nella Parte, di quasi due decenni rispetto a HNSW. È nato come risultato di teoria degli algoritmi su problemi di geometria computazionale e di deduplicazione web, molto prima che esistessero gli embedding densi, RAG o i vector database. Come ann-intro insisteva per l’intera famiglia: questa tecnologia precede gli LLM, non li segue.

Una nota sulla classe di affermazioni, perché in questo capitolo si collegano metodi diversi. MinHash, SimHash e lo schema p-stable non sono “ispirati” da LSH: sono istanze della stessa definizione astratta — ne soddisfano la proprietà formale, ognuna per una metrica diversa. MinHash storicamente precede la definizione generale, gli altri due la seguono: questo è il lineage documentato, non un’analogia.

LSH come framework, invece, è il parente teorico dei metodi della mini-serie — HNSW, IVF+PQ, ScaNN — ma non il loro antenato: quei metodi hanno radici tecniche autonome. Il rapporto fra LSH e gli altri ANN è un confronto fra famiglie, non una discendenza. Tenere distinte queste due cose — istanza di una definizione, confronto fra famiglie — evita lo scivolamento tipico fra analogia e filiazione.

Un’ultima collocazione, perché aiuta a inquadrare LSH nella mappa più ampia delle strutture dati probabilistiche. LSH appartiene alla stessa famiglia concettuale di altri strumenti che, negli stessi decenni, hanno scelto di barattare una piccola probabilità di errore per un guadagno enorme di tempo o memoria: i Bloom filter (Burton Bloom, 1970) per il test di appartenenza a un insieme, gli sketch come il Count-Min sketch (Cormode e Muthukrishnan, 2005) per le statistiche su flussi di dati. Tutti rispondono a una domanda con un “quasi certamente sì” o “quasi certamente no” invece che con una certezza, e tutti per la stessa ragione: la certezza, su dati abbastanza grandi, costa troppo. LSH è la declinazione di questa filosofia applicata alla domanda “questi due elementi sono simili?”.

L’intuizione

Tre angoli, prima di qualunque formula. Il primo spiega cosa fa LSH ribaltando la hash table; il secondo come lo fa concretamente, guardando le tre costruzioni; il terzo perché funziona, in termini di probabilità e di budget.

Angolo 1 — la hash table al contrario

Riprendiamo la regola d’oro della hash table e guardiamola da vicino. La proprietà desiderata è: input diversi producono output scorrelati. È questo che permette di cercare una chiave in tempo costante — vai direttamente allo slot, non c’è niente da scandire. Le collisioni sono nemiche: troppe, e la tabella rallenta.

LSH vuole la proprietà opposta. Vuole che due input simili producano lo stesso output con alta probabilità. La collisione non è più rumore da minimizzare: è il segnale che cerchiamo.

E da questa inversione discende una scorciatoia. Per trovare gli elementi simili a una query, basta hashare la query e guardare nel suo bucket: lì dentro ci sono quasi solo elementi simili, e abbiamo ignorato in un colpo solo la grande maggioranza degli elementi lontani. Il problema è passato da “confronta la query con tutti gli n elementi” a “confronta la query con i pochi del suo bucket”.

C’è un costo nascosto in questa intuizione, ed è il seme di tutto il resto del capitolo. Una singola funzione hash LSH non separa abbastanza nettamente i vicini dai lontani. Non è come un test perfetto che dice “simile” o “diverso”: fa collidere i vicini magari l’80% delle volte, ma fa collidere anche i lontani magari il 30% delle volte.

Trenta per cento di falsi positivi in ogni bucket è troppo: il bucket si riempie di roba lontana e la scorciatoia perde valore. Il rimedio non è cercare una funzione hash più intelligente. È combinarne molte deboli — ed è la parte che la sezione meccanica chiamerà amplificazione.

Figura in preparazione

fig-1: due pannelli affiancati. A sinistra “Hash table classica”: tre input simili (gatto, gatta, gatti) con frecce divergenti verso tre bucket diversi, etichetta “dispersione: simili separati”. A destra “LSH”: gli stessi tre input con frecce convergenti verso lo stesso bucket, un quarto input lontano (martello) verso un altro bucket, etichetta “concentrazione: simili insieme”. Titolo “La regola della hash table, capovolta”

Angolo 2 — geometrico: tre modi di tagliare lo spazio

Il secondo angolo è geometrico, e si vede meglio guardando come ciascuna delle tre costruzioni classiche taglia lo spazio. Sono tre tagli diversi, ma rispettano tutti la stessa regola: i vicini cadono insieme più spesso dei lontani.

SimHash, il taglio con un iperpiano (per la similarità coseno). Gli elementi da confrontare sono vettori, frecce che partono dall’origine; la loro similarità è l’angolo fra loro — due frecce quasi parallele sono molto simili. Una funzione hash SimHash prende un iperpiano casuale che passa per l’origine. Un iperpiano, in uno spazio a tante dimensioni, è la generalizzazione di una retta nel piano: divide lo spazio in due metà.

L’hash di un vettore è un solo bit: da quale lato dell’iperpiano cade. Ora il punto. Due frecce vicine in angolo cadono quasi sempre dalla stessa parte di un iperpiano scelto a caso — solo un iperpiano che passa proprio nello stretto spicchio fra loro le separa, ed è raro.

Due frecce quasi opposte, invece, vengono separate da quasi ogni iperpiano. La vicinanza angolare si traduce in “stesso bit con alta probabilità”: esattamente la proprietà LSH, ottenuta con il taglio più semplice immaginabile.

MinHash, il taglio con una permutazione (per la similarità di Jaccard). Qui gli elementi non sono vettori ma insiemi. Un documento, per esempio, diventa l’insieme dei suoi shingle: le sue sottostringhe di k parole consecutive (o k caratteri). La frase “il gatto dorme sul tappeto”, con shingle di tre parole, diventa l’insieme {il gatto dorme, gatto dorme sul, dorme sul tappeto}.

La similarità di due insiemi A e B si misura con la Jaccard: la dimensione dell’intersezione divisa per la dimensione dell’unione — quanta parte hanno in comune sul totale. Una funzione MinHash prende una permutazione casuale di tutti gli elementi possibili — immagina di mescolare a caso un mazzo che contiene ogni shingle pensabile — e l’hash di un insieme è l’elemento dell’insieme che viene primo in quel mescolamento. Il fatto notevole, che dimostreremo, è che due insiemi hanno lo stesso MinHash con probabilità esattamente uguale alla loro Jaccard.

Schema p-stable, il taglio con una griglia su una retta (per la distanza euclidea). Qui i punti vivono in uno spazio euclideo e contano le distanze L2 ordinarie. Una funzione hash proietta il punto su una retta orientata a caso, e poi divide quella retta in segmenti di larghezza fissata; l’hash è l’indice del segmento in cui la proiezione cade. Punti vicini nello spazio proiettano vicino sulla retta e cadono spesso nello stesso segmento; punti lontani no.

Tre tagli — un iperpiano, una permutazione, una griglia — per tre metriche diverse, ma una sola idea sotto: un partizionamento casuale dello spazio in cui i vicini hanno una buona probabilità di finire nella stessa cella.

Angolo 3 — economico: tante prove deboli al posto di una forte

Il terzo angolo spiega perché LSH, pur partendo da uno strumento mediocre, finisce per funzionare bene. È un angolo probabilistico, e ha un’eco familiare per chiunque abbia ragionato su un sondaggio o su una giuria.

Una singola funzione hash LSH è un giudice debole. Sentenzia “questi due elementi sono simili” facendoli collidere, oppure “sono diversi” mandandoli in bucket diversi — ma sbaglia spesso in entrambe le direzioni: lascia scappare veri vicini e cattura falsi vicini. Da sola non è affidabile.

La tentazione è cercare un giudice migliore: una funzione hash più sofisticata, più precisa. LSH rinuncia a questa strada e ne sceglie un’altra: convoca molti giudici deboli e indipendenti, e prende la decisione finale aggregando i loro voti.

L’intuizione del perché funzioni è la stessa che rende affidabile la media di tanti sondaggi imperfetti, o il verdetto di una giuria numerosa anche se ogni giurato è fallibile. Se ogni giudice sbaglia in modo indipendente dagli altri, gli errori non si sommano: si elidono a vicenda. Con un solo giudice un errore è un errore. Con cento giudici indipendenti, la probabilità che la maggioranza sbagli nello stesso modo crolla.

LSH non ha bisogno di una funzione hash brillante, perché ha bisogno solo che ogni funzione sia “leggermente meglio del caso” — che $p_1$ sia un po’ più grande di $p_2$ — e poi lascia che la statistica dei grandi numeri faccia il lavoro. È un’inversione di prospettiva: la fatica non sta nel progettare la singola funzione, sta nel comporne tante.

C’è una sfumatura, ed è il motivo per cui l’amplificazione ha due operazioni e non una. Aggregare i voti “a maggioranza” andrebbe bene se l’errore fosse simmetrico, ma per la ricerca dei vicini i due tipi di errore costano in modo diverso, e in momenti diversi. Catturare un falso vicino costa poco — lo si scarta nella verifica esatta a valle. Lasciar scappare un vero vicino costa molto — quel risultato è perso per sempre.

L’amplificazione AND/OR è esattamente un modo di aggregare i voti che tratta i due errori in modo asimmetrico: la parte AND schiaccia i falsi positivi, la parte OR recupera i veri positivi. La meccanica lo rende preciso. Per ora basta tenere l’immagine: LSH è un parlamento di giudici scadenti, non un singolo oracolo.

La meccanica

La definizione formale

Mettiamo nome e numeri a ciò che l’intuizione ha già detto. Una famiglia di funzioni hash $H$ — un insieme di funzioni dal quale possiamo pescarne una a caso — si dice $(r_1, r_2, p_1, p_2)$-sensitive rispetto a una metrica di distanza $d$ se, presi due punti qualsiasi $x$ e $y$ e scelta una funzione $h$ a caso da $H$, valgono due condizioni:

$\text{se } d(x, y) \le r_1 \quad\Rightarrow\quad \Pr[h(x) = h(y)] \ge p_1$

$\text{se } d(x, y) \ge r_2 \quad\Rightarrow\quad \Pr[h(x) = h(y)] \le p_2$

In parole povere: se due punti distano al massimo $r_1$ — sono vicini — collidono con probabilità almeno $p_1$; se distano almeno $r_2$ — sono lontani — collidono con probabilità al massimo $p_2$. I quattro simboli: $r_1$ e $r_2$ sono due soglie di distanza ($r_1$ piccola, $r_2$ grande), $p_1$ e $p_2$ due soglie di probabilità.

C’è una zona grigia, ed è voluta. La definizione non dice nulla su cosa succede fra $r_1$ e $r_2$: per i punti a distanza intermedia, la probabilità di collisione può essere qualunque cosa. È il prezzo dell’approssimazione — LSH garantisce di separare bene i chiaramente vicini dai chiaramente lontani, e si disinteressa della fascia ambigua nel mezzo.

Perché la definizione sia utile servono $r_1 < r_2$ — c’è una zona “vicino” e una zona “lontano” distinte — e $p_1 > p_2$ — i vicini collidono più spesso dei lontani. Una famiglia in cui $p_1 = p_2$ non distinguerebbe nulla. Quanto bene una famiglia separa è catturato da un solo numero, il parametro

$\rho = \frac{\ln(1/p_1)}{\ln(1/p_2)}$

che è sempre compreso fra 0 e 1: più $\rho$ è piccolo, migliore è la famiglia. Indyk e Motwani hanno dimostrato che con una famiglia LSH si costruisce una struttura dati che risolve l’approximate near neighbor in tempo $O(n^\rho)$, con $\rho < 1$: sublineare nel numero di punti $n$. Non un’osservazione empirica, ma un teorema. È la prima dimostrazione che la maledizione della dimensionalità si può aggirare con garanzie — la ragione per cui il paper del 1998 è una pietra miliare.

Perché MinHash stima la Jaccard

La definizione astratta dice “vicini collidono spesso”. MinHash dice qualcosa di più preciso e più bello, ed è dimostrabile in poche righe. Prendi due insiemi $A$ e $B$, e una permutazione casuale di tutti gli elementi possibili. Il MinHash di $A$ è il primo elemento di $A$ nella permutazione; quello di $B$, il primo di $B$.

Quando i due MinHash coincidono? Esattamente quando l’elemento che viene primo, considerando l’unione $A \cup B$, appartiene anche all’intersezione $A \cap B$.

Pensa di scorrere la permutazione dall’inizio. Il primo elemento che incontri appartenente a $A \cup B$ decide entrambi i MinHash. Se quell’elemento sta in $A \cap B$ — sta in tutti e due — allora è il minimo sia per $A$ sia per $B$, e i MinHash coincidono. Se sta solo in $A$ o solo in $B$, i due minimi differiscono. Poiché la permutazione è casuale, ogni elemento di $A \cup B$ ha la stessa probabilità di essere il primo. Quindi:

$\Pr[\text{MinHash}(A) = \text{MinHash}(B)] = \frac{|A \cap B|}{|A \cup B|} = J(A, B)$

La probabilità di collisione è esattamente la similarità di Jaccard. Un singolo MinHash è quindi uno stimatore — grezzo, vale 0 o 1 — della Jaccard. Calcolandone molti, indipendenti, e contando la frazione di accordi, si ottiene una stima sempre più precisa. Con 200 funzioni MinHash, due insiemi con Jaccard reale 0,5 daranno lo stesso valore in circa 100 casi.

Quanto precisa è la stima dipende da quante funzioni si usano. Ogni MinHash è una prova bernoulliana — accordo o disaccordo — con probabilità di successo $J$. La media di $m$ prove indipendenti ha un errore standard che scala come $1/\sqrt{m}$: per dimezzare l’incertezza della stima bisogna quadruplicare il numero di funzioni. Con $m = 200$ l’errore tipico sulla stima di Jaccard è dell’ordine di qualche punto percentuale — abbastanza per le applicazioni di deduplicazione, dove la soglia è larga (0,8 o 0,9) e non serve la terza cifra decimale. È un compromesso classico: più funzioni significano firme più lunghe e più memoria, in cambio di stime più strette.

Una nota implementativa chiude la dimostrazione. Generare permutazioni vere di un universo enorme è impraticabile, e in pratica non si fa. Si usano famiglie di funzioni hash che approssimano una permutazione casuale — tipicamente $h_i(x) = (a_i x + b_i) \bmod p$ con coefficienti casuali e $p$ primo grande.

Il MinHash dell’insieme rispetto a $h_i$ è il minimo di $h_i$ applicato a tutti gli elementi. Queste funzioni sono “min-wise independent” abbastanza da rendere la stima quasi non distorta. Il nome completo del metodo nel paper di Broder, “min-wise independent permutations”, si riferisce esattamente a questa proprietà.

Amplificazione: AND, OR, e la curva a S

Una singola funzione LSH separa male: $p_1$ non è 1 e $p_2$ non è 0. La meccanica vera di LSH sta nel comporre molte funzioni deboli in un indice forte, con due operazioni di segno opposto.

AND — concatenazione, dentro una banda. Prendi $k$ funzioni hash LSH indipendenti e concatena le loro uscite in un’unica firma. Due elementi collidono su questa firma composta solo se collidono su tutte e $k$ le funzioni. Se la probabilità di collisione su una funzione è $p$, sulla firma di $k$ funzioni è $p^k$.

Questo è ottimo per i falsi positivi — $p_2^k$ diventa minuscolo, i lontani smettono di collidere — ma è duro anche con i veri positivi: $p_1^k$ scende anch’esso. La concatenazione taglia tutto, alla cieca. Da sola renderebbe l’indice troppo selettivo: perderebbe quasi ogni vicino.

OR — più bande, più tabelle. Ripeti la concatenazione $L$ volte in modo indipendente: costruisci $L$ tabelle hash separate, ognuna con la propria firma da $k$ funzioni. Due elementi sono candidati se collidono in almeno una delle $L$ bande.

Se la probabilità di collidere in una banda è $P$, la probabilità di collidere in almeno una è $1 - (1 - P)^L$. Questo recupera i veri positivi — basta che una banda li catturi — al prezzo di rialzare un po’ i falsi positivi. La parte OR è il contrappeso della parte AND: dove la concatenazione tagliava troppo, la ripetizione su più bande ricuce.

Combinando i due livelli, la probabilità che due elementi con similarità $s$ diventino candidati è:

$P(s) = 1 - (1 - s^k)^L$

dove $s$ è la similarità — per MinHash, la Jaccard. Disegnando $P(s)$ in funzione di $s$ si ottiene una curva a S: bassa e piatta per $s$ piccolo (i lontani quasi mai candidati), una salita ripida intorno a una soglia, alta e piatta per $s$ grande (i vicini quasi sempre candidati).

La soglia — il punto di flesso, dove la curva passa da “quasi mai” a “quasi sempre” — sta approssimativamente a

$s^* \approx \left(\frac{1}{L}\right)^{1/k}$

Questa è la manopola di LSH, e non è un tuning oscuro. Aumentare $k$ sposta la soglia verso destra: serve più similarità per essere candidati, l’indice diventa più selettivo. Aumentare $L$ la sposta a sinistra: l’indice diventa più permissivo. Aumentare entrambi mantenendo il rapporto irripidisce il gradino, rendendo la decisione più netta.

In pratica si parte dalla soglia di similarità che interessa — “voglio catturare i documenti con Jaccard almeno 0,8” — e si scelgono $k$ e $L$ perché il flesso cada lì. La soglia si progetta, non si indovina: è la differenza fra LSH e un filtro tarato a occhio.

Figura in preparazione

fig-2: grafico della curva a S. Asse x “similarità s (0 a 1)”, asse y “probabilità di diventare candidato P(s)”. Tre curve sovrapposte per tre coppie (k, L) diverse, con il punto di flesso marcato su ciascuna e l’etichetta “soglia s* ≈ (1/L)^(1/k)”. Zona sinistra ombreggiata “lontani: scartati”, zona destra “vicini: catturati”. Titolo “La curva a S dell’amplificazione AND/OR”

SimHash e lo schema euclideo, in formule

MinHash è la costruzione con la dimostrazione più pulita, ma le altre due meritano un passaggio meccanico, perché mostrano che la stessa idea si declina su geometrie diverse.

Per SimHash, l’hash di un vettore $x$ rispetto a un vettore casuale $r$ — con le componenti di $r$ estratte da una gaussiana standard — è il bit

$h_r(x) = \begin{cases} 1 & \text{se } \langle r, x \rangle \ge 0 \\ 0 & \text{altrimenti} \end{cases}$

dove $\langle r, x \rangle$ è il prodotto scalare. Il vettore $r$ definisce un iperpiano — quello perpendicolare a $r$ che passa per l’origine — e il segno del prodotto scalare dice da quale lato cade $x$.

Charikar ha dimostrato che la probabilità che due vettori $x$ e $y$ ricevano lo stesso bit è

$\Pr[h_r(x) = h_r(y)] = 1 - \frac{\theta(x, y)}{\pi}$

dove $\theta(x, y)$ è l’angolo fra i due vettori. In parole povere: due vettori paralleli ($\theta = 0$) collidono con probabilità 1, due ortogonali ($\theta = \pi/2$) con probabilità $1/2$, due opposti ($\theta = \pi$) con probabilità 0. La probabilità di collisione decresce in modo lineare con l’angolo — una relazione semplice fra geometria e probabilità, ed è ciò che rende SimHash una famiglia LSH per la similarità coseno.

Per lo schema p-stable (distanza euclidea), l’hash di un punto $x$ è

$h_{r,b}(x) = \left\lfloor \frac{\langle r, x \rangle + b}{w} \right\rfloor$

dove $r$ è un vettore casuale a componenti gaussiane, $b$ uno scostamento casuale uniforme fra 0 e $w$, e $w$ la larghezza dei segmenti. Il prodotto $\langle r, x \rangle$ proietta $x$ su una retta; lo scostamento $b$ sposta la griglia in modo che i suoi bordi non cadano sempre negli stessi punti; la divisione per $w$ seguita dalla parte intera $\lfloor \cdot \rfloor$ dice in quale segmento di larghezza $w$ la proiezione è caduta.

Il nome “p-stable” viene da una proprietà delle distribuzioni usate per $r$. La gaussiana è una distribuzione 2-stabile, e questo garantisce che la proiezione di $x - y$ abbia una lunghezza proporzionale alla distanza euclidea $\lVert x - y \rVert$. Punti vicini proiettano vicino, e cadono spesso nello stesso segmento; il parametro $w$ regola quanto spesso. Un $w$ piccolo rende l’hash selettivo (pochi punti per segmento, pochi falsi positivi); un $w$ grande lo rende permissivo.

Tre formule, tre geometrie, una sola struttura: in tutte, una scelta casuale ($r$, una permutazione, $r$ e $b$) produce una partizione dello spazio in cui la probabilità che due elementi finiscano insieme è una funzione decrescente della loro distanza. È la definizione $(r_1, r_2, p_1, p_2)$-sensitive, vista dall’interno di ogni costruzione.

Il costo dell’indice

Vale la pena fissare quanto costa, perché spiega sia i pregi sia i limiti di LSH.

La costruzione richiede, per ogni elemento, il calcolo di $k \cdot L$ funzioni hash. Ogni funzione è economica — un prodotto scalare, un minimo, una proiezione — e tutte le funzioni sono indipendenti, quindi il calcolo si parallelizza banalmente. Su $n$ elementi il costo totale è $O(n \cdot k \cdot L)$: lineare in $n$. È questa linearità, insieme alla parallelizzabilità, a rendere LSH praticabile su corpora di miliardi di documenti, dove un confronto a coppie $O(n^2)$ sarebbe fuori discussione.

La memoria dell’indice è $L$ tabelle hash, ognuna con $n$ voci: $O(n \cdot L)$ puntatori, più le firme. Per $L$ grande — e $L$ può arrivare a decine o centinaia — questo è un costo reale, ed è uno dei motivi per cui LSH, su embedding densi, perde contro metodi più parsimoniosi.

La query calcola la firma della query — $O(k \cdot L)$ — poi guarda $L$ bucket e raccoglie i candidati. Il costo dipende da quanti candidati cadono nei bucket.

Se il tuning è buono e i bucket sono piccoli, la query tocca una frazione minuscola degli $n$ elementi, ed è qui che si materializza la sublinearità $O(n^\rho)$ del teorema. Se il tuning è cattivo e i bucket si gonfiano, la verifica esatta a valle diventa il collo di bottiglia. Il costo della query non è fisso: dipende dalla forma della curva a S che hai scelto.

L’indice, passo per passo

Mettendo insieme i pezzi, ecco la costruzione e la query di un indice MinHash+LSH per la deduplicazione di documenti:

# costruzione dell'indice
for ogni documento d:
    shingles = insieme dei k-gram di d
    firma   = [minhash_i(shingles) for i in 1..(k*L)]   # lunga k*L
    for banda b in 1..L:
        sotto_firma = firma[b*k : (b+1)*k]              # k valori
        bucket = hash(sotto_firma)
        tabella[b][bucket].append(d)

# query: trovare i near-duplicate di q
candidati = insieme vuoto
for banda b in 1..L:
    sotto_firma = firma_di_q[b*k : (b+1)*k]
    candidati |= tabella[b][hash(sotto_firma)]
# verifica esatta SOLO sui candidati
return [c for c in candidati if jaccard(q, c) >= soglia]

L’ultimo passo merita attenzione. LSH non restituisce i vicini: restituisce un insieme di candidati, piccolo. La similarità vera — la Jaccard esatta — si calcola solo su quei pochi.

LSH è un filtro che riduce lo spazio di ricerca da $n$ a una manciata; il giudizio finale è un controllo esatto a valle. Confondere il filtro con il giudizio è uno degli errori tipici, e la sezione “Dove si rompe” ci tornerà sopra.

Scegliere k e L: un esempio di tuning

La formula $s^* \approx (1/L)^{1/k}$ dà la posizione del flesso, ma in pratica si sceglie $k$ e $L$ con un ragionamento un po’ più articolato. Vediamolo su un caso concreto: un sistema di deduplicazione dove vogliamo catturare tutti i documenti con Jaccard almeno 0,8 e scartare quelli sotto 0,4.

Il primo vincolo riguarda i veri positivi. A $s = 0{,}8$, vogliamo che $P(0{,}8)$ sia vicino a 1 — diciamo almeno 0,99 — perché perdere un near-duplicate è il costo che vogliamo evitare. Il secondo vincolo riguarda i falsi positivi. A $s = 0{,}4$, vogliamo $P(0{,}4)$ piccolo — diciamo sotto 0,05 — perché ogni candidato spurio va poi verificato a costo pieno.

Si procede provando coppie $(k, L)$ e calcolando $P(s) = 1 - (1 - s^k)^L$ ai due punti. Con $k = 5$ e $L = 40$: $P(0{,}8) = 1 - (1 - 0{,}8^5)^{40} \approx 1 - (1 - 0{,}328)^{40} \approx 1{,}0$, ottimo; ma $P(0{,}4) = 1 - (1 - 0{,}4^5)^{40} \approx 1 - (1 - 0{,}010)^{40} \approx 0{,}34$, troppo alto — troppi falsi positivi.

Aumentiamo $k$ per spostare la soglia a destra. Con $k = 10$ e $L = 40$: $P(0{,}8) \approx 1 - (1 - 0{,}107)^{40} \approx 0{,}99$, ancora buono; $P(0{,}4) \approx 1 - (1 - 0{,}0001)^{40} \approx 0{,}004$, ora sotto la soglia. La coppia $(10, 40)$ soddisfa entrambi i vincoli, ed è quella che si manda in produzione.

Il ragionamento generale: $k$ controlla dove sta il gradino, $L$ controlla quanto è alto e quanto è ripido. Si fissa prima $k$ guardando dove deve cadere la soglia, poi si alza $L$ finché i veri positivi non sono al sicuro. Il prezzo di $k$ e $L$ grandi è la memoria — $L$ tabelle — e il tempo di calcolo della firma — $k \cdot L$ funzioni hash. C’è sempre un compromesso fra nettezza della curva e costo dell’indice.

Le varianti, in breve

Lo schema base — $k$ funzioni per banda, $L$ bande, una tabella per banda — è quello che ha senso conoscere per primo, ed è abbastanza per la maggior parte dei casi di deduplicazione. Esistono raffinamenti, che vale la pena solo nominare per sapere che ci sono.

Il multi-probe LSH affronta il costo della memoria. Invece di tenere $L$ tabelle grandi, ne tiene poche e, in query, ispeziona non solo il bucket esatto della query ma anche i bucket “vicini” — quelli che differiscono di poco nella firma — perché un vero vicino potrebbe esserci finito per un soffio. Recupera recall senza moltiplicare le tabelle.

La LSH Forest rende adattivo il parametro $k$, lasciando che ogni ramo di una struttura ad albero scelga la propria profondità a seconda della densità locale dei dati. Esistono poi famiglie LSH più sofisticate per la distanza euclidea, come la cross-polytope LSH, e perfino schemi data-dependent che rinunciano alla purezza data-oblivious in cambio di un $\rho$ migliore.

Sono tutte oltre lo scopo di un capitolo introduttivo. La cosa da portare via è che lo schema $k$-$L$ con la curva a S è il nucleo, e tutto il resto sono ottimizzazioni di costo o di recall attorno a quel nucleo.

Esempi

Esempio numerico — MinHash su due frasi

Documento A: “the cat sat on the mat”, con shingle di tre parole {the cat sat, cat sat on, sat on the, on the mat}. Documento B: “the cat sat on the rug”, shingle {the cat sat, cat sat on, sat on the, on the rug}.

I due insiemi condividono i primi tre shingle e differiscono solo nell’ultimo. L’intersezione contiene 3 shingle, l’unione ne contiene 5. La similarità di Jaccard è quindi $3/5 = 0{,}6$: i due documenti sono simili ma non identici, esattamente il caso che la deduplicazione vuole intercettare.

Con 200 funzioni MinHash indipendenti, mi aspetto che circa $0{,}6 \times 200 = 120$ di esse diano lo stesso valore su A e B, perché la probabilità di collisione di ogni singola funzione è esattamente la Jaccard. Contando gli accordi e dividendo per 200 ottengo una stima della Jaccard senza aver mai calcolato esplicitamente intersezione e unione sugli insiemi grandi.

Con i parametri $k = 5$, $L = 20$, la soglia è $s^* \approx (1/20)^{1/5} \approx 0{,}55$: due documenti con Jaccard 0,6 cadono appena oltre il flesso e hanno una probabilità alta — ma non schiacciante — di diventare candidati; due documenti con Jaccard 0,9 sono catturati quasi con certezza.

Esempio in codice — SimHash a 64 bit per il near-duplicate web

Per rilevare pagine web quasi-identiche su scala enorme, Google ha descritto (Manku, Jain, Das Sarma, Detecting Near-Duplicates for Web Crawling, WWW 2007) l’uso di SimHash a 64 bit. Ogni pagina diventa una firma di 64 bit, e due pagine sono considerate near-duplicate se le firme differiscono per al massimo 3 bit — una soglia di Hamming molto stretta, tarata sul caso d’uso del crawling.

def simhash(features, iperpiani):       # 64 iperpiani casuali
    bits = 0
    for i, r in enumerate(iperpiani):   # un iperpiano per bit
        if dot(features, r) >= 0:       # da quale lato cade
            bits |= (1 << i)
    return bits                          # firma a 64 bit

def near_duplicate(sig_a, sig_b, soglia=3):
    hamming = bin(sig_a ^ sig_b).count("1")  # bit diversi
    return hamming <= soglia

Lo XOR di due firme accende esattamente i bit in cui differiscono; contarli dà la distanza di Hamming. Confrontare due interi a 64 bit costa una manciata di istruzioni macchina, contro la scansione parola per parola dei due testi originali.

La firma da 8 byte sostituisce un documento intero per il solo scopo del confronto di similarità. È una compressione brutale — un articolo di mille parole ridotto a otto byte — ma è esattamente la compressione giusta: butta via tutto tranne ciò che serve a dire “questo testo è quasi uguale a quell’altro”. Su un archivio di miliardi di pagine, la differenza fra confrontare firme da 8 byte e confrontare documenti interi è la differenza fra fattibile e impossibile.

Scenario reale — deduplicare un corpus di training LLM

Prima di addestrare un modello linguistico si ripuliscono i dati dai documenti quasi-identici. I duplicati esatti e i near-duplicate gonfiano il corpus, spingono il modello a memorizzare testo ripetuto invece di apprendere, e sprecano compute su contenuto ridondante.

Ma un corpus di pre-training è fatto di terabyte di testo crawlato dal web. Il confronto esatto di ogni coppia di documenti è $O(n^2)$: con miliardi di documenti, semplicemente impraticabile. Serve un metodo che produca le coppie sospette in tempo lineare, e quel metodo è MinHash combinato con LSH.

Il dataset C4 (Colossal Clean Crawled Corpus), usato per addestrare i modelli T5 di Google e fonte di buona parte del training di GPT-3, è stato deduplicato con MinHash su Common Crawl. Il paper Deduplicating Training Data Makes Language Models Better (Lee et al., ACL 2022) descrive il metodo NearDup: MinHash sugli n-gram dei documenti, LSH per generare le coppie candidate, e infine un controllo di edit-similarity con soglia 0,8 per confermare ogni coppia.

I risultati misurati sono netti. I modelli addestrati su dati deduplicati emettono testo memorizzato circa dieci volte meno spesso e raggiungono la stessa accuratezza con meno passi di training. Lo stesso lavoro ha trovato in C4 una singola frase inglese di 61 parole ripetuta oltre 60.000 volte. Pipeline analoghe basate su MinHash+LSH sono usate per The Pile di EleutherAI e per FineWeb. È, oggi, l’applicazione di massa di LSH.

Esempio geometrico — perché due iperpiani separano meglio di uno

Un ultimo esempio, piccolo e visivo, per fissare l’amplificazione AND su SimHash. Immagina due vettori che formano fra loro un angolo di 30 gradi, cioè $\theta = \pi/6$. Sono abbastanza vicini.

Con un solo iperpiano casuale, la probabilità che cadano dalla stessa parte è $1 - \theta/\pi = 1 - (1/6) \approx 0{,}83$: l’83% delle volte ricevono lo stesso bit. Un giudice debole, come dicevamo, ma meglio del lancio di una moneta.

Ora prendi due vettori quasi ortogonali, con un angolo di 80 gradi. Con un solo iperpiano collidono con probabilità $1 - 80/180 \approx 0{,}56$: il 56%. La differenza fra “vicini” e “quasi ortogonali”, con un solo bit, è 83% contro 56% — un divario c’è, ma è modesto: un bucket basato su un solo bit raccoglie un sacco di vettori quasi ortogonali insieme a quelli davvero vicini.

Concatena ora $k = 10$ iperpiani indipendenti (la parte AND). La coppia a 30 gradi collide su tutti e dieci con probabilità $0{,}83^{10} \approx 0{,}16$. La coppia a 80 gradi, con probabilità $0{,}56^{10} \approx 0{,}003$. Il divario si è trasformato: 16% contro 0,3%, un rapporto di oltre cinquanta a uno. La concatenazione ha schiacciato i quasi-ortogonali quasi a zero — ma ha schiacciato anche i veri vicini, dal 83% al 16%.

Ecco perché serve la parte OR. Con $L = 20$ ripetizioni, la coppia vicina diventa candidata con probabilità $1 - (1 - 0{,}16)^{20} \approx 0{,}97$, mentre la coppia quasi ortogonale resta a $1 - (1 - 0{,}003)^{20} \approx 0{,}06$. Il risultato finale — 97% contro 6% — è la separazione netta che un solo bit non sapeva dare. Sono numeri che si possono rifare a mano, e che mostrano la curva a S all’opera su una coppia concreta.

LSH contro gli altri metodi ANN

Questo capitolo chiude la mini-serie, quindi vale la pena mettere LSH a fianco delle altre tre famiglie e dire con chiarezza dove sta e dove non sta.

La distinzione di fondo è una sola, ed è quella fra metodi data-oblivious e data-adaptive. LSH è data-oblivious: sceglie i suoi iperpiani, le sue permutazioni, le sue griglie a caso, senza mai guardare come sono distribuiti i dati che dovrà indicizzare. Lo stesso indice LSH funziona su qualunque dataset, e questa universalità è ciò che permette di dimostrare un teorema valido per ogni distribuzione.

HNSW, IVF, ScaNN sono invece data-adaptive: HNSW costruisce un grafo che segue la forma reale della nuvola di punti, IVF apprende i centroidi delle partizioni dai dati, ScaNN apprende un dizionario di quantizzazione tarato sui dati. Guardare i dati permette di sfruttarne la struttura — i cluster, le direzioni dense, le simmetrie — e quel vantaggio, su dati reali, è grande.

La conseguenza pratica è netta. Sugli embedding densi prodotti da reti neurali — vettori di centinaia o migliaia di dimensioni che codificano la semantica di testo, immagini, codice — i metodi data-adaptive battono LSH nettamente sulla frontiera recall-latenza. Su ann-benchmarks, il benchmark pubblico standard della comunità, LSH sta tipicamente sotto la curva di Pareto: a parità di latenza ottiene meno recall, a parità di recall è più lento. Non di poco. È la ragione per cui i vector database moderni e i sistemi RAG usano HNSW o IVF+PQ, non LSH.

Ma “perde sugli embedding densi” non vuol dire “obsoleto”. Le garanzie teoriche di LSH — la sublinearità dimostrata $O(n^\rho)$, valida per ogni distribuzione — restano sue e di nessun altro: HNSW e IVF non hanno garanzie di questo tipo, sono ottimi in pratica ma senza teorema. La natura data-oblivious, che è uno svantaggio sulla precisione, è un vantaggio sulla semplicità: un indice LSH non ha una fase di training né di costruzione del grafo, si aggiorna in streaming, si implementa in poche righe.

E sui problemi per cui LSH è nato — la deduplicazione di insiemi di shingle, il near-duplicate detection — LSH non perde affatto: lì la similarità di Jaccard fra insiemi è la metrica giusta, MinHash la stima in modo non distorto, e nessun metodo a grafo offre qualcosa di paragonabile. La collocazione corretta di LSH oggi non è “metodo ANN superato”: è “lo strumento giusto per la deduplicazione e il near-duplicate, e lo strumento sbagliato per la ricerca di precisione su embedding densi”.

Figura in preparazione

fig-3: tabella visiva a quattro colonne, una per famiglia ANN (LSH, HNSW, IVF+PQ, ScaNN). Righe: “tipo” (data-oblivious / data-adaptive), “garanzia teorica” (sublinearità provata solo per LSH), “recall su embedding densi” (gli altri tre alti, LSH medio), “punto di forza” (LSH: deduplicazione e streaming; HNSW: recall in RAM; IVF+PQ: footprint compresso; ScaNN: ranking su prodotto interno). Titolo “Le quattro famiglie ANN, dove sta ciascuna”

Applicazioni pratiche

Deduplicazione di corpora per il training LLM. È l’uso dominante di LSH oggi. MinHash+LSH trasforma un confronto a coppie $O(n^2)$ in un filtro che produce solo le coppie candidate, in tempo lineare e parallelizzabile. C4, The Pile, RedPajama, FineWeb adottano tutti varianti di MinHash+LSH per il dedup, e il legame fra deduplicazione e qualità del modello è documentato.

Il motivo per cui questo passo non si può saltare: un corpus di pre-training crawlato dal web contiene un’enorme quantità di ridondanza — pagine mirror, articoli sindacati, boilerplate ripetuto, frammenti copiati. Un modello addestrato su dati ridondanti spende capacità a memorizzare il testo che si ripete invece di apprendere struttura linguistica, e il rischio di rigurgitare verbatim materiale di training cresce. La deduplicazione è una delle leve più economiche per migliorare un modello: non cambia l’architettura, non costa compute di training, ripulisce solo l’input. Questo collega il capitolo direttamente al lavoro sui dati di pre-training, trattato in pretraining-dati (in preparazione) nella Parte sul training.

Near-duplicate detection e anti-plagio. Rilevare pagine web duplicate — l’uso originale di AltaVista — articoli ripubblicati, copie quasi-identiche di file di codice, plagio in elaborati d’esame. SimHash e MinHash sono lo standard: firma compatta, confronto rapidissimo, soglia regolabile.

La logica è sempre la stessa: si comprime ogni documento in una firma piccola, si indicizza con LSH, e quando arriva un nuovo documento si recuperano in tempo quasi costante i pochi candidati a essere suoi quasi-duplicati. Senza LSH, controllare se un nuovo documento è già presente in un archivio di milioni richiederebbe milioni di confronti per ogni inserimento.

Clustering di near-duplicate e content moderation. Raggruppare le varianti minime dello stesso contenuto — spam che cambia poche parole a ogni invio, immagini ricodificate, disinformazione riconfezionata. LSH produce i cluster candidati senza confronto a coppie.

Una piattaforma che modera contenuti riceve spesso ondate dello stesso messaggio con variazioni minime, pensate per eludere i filtri esatti. LSH cattura la famiglia di varianti come un unico cluster, permettendo di agire una volta sola sull’intero gruppo invece di rincorrere ogni singola variante.

Streaming e sketching. LSH lavora su un elemento alla volta e produce una firma compatta: si presta a flussi di dati in cui non si può tenere tutto in memoria. È imparentato concettualmente con i Bloom filter — strutture che dicono “questo elemento l’ho già visto?” con una piccola probabilità di falso positivo — e con gli sketch come il Count-Min sketch.

Tutte queste strutture barattano una piccola probabilità di errore per un footprint di memoria minuscolo: è la stessa filosofia di LSH, applicata a domande diverse. Il legame non è solo di stile. In una pipeline di deduplicazione in streaming si usa spesso un Bloom filter per scartare in fretta i duplicati esatti, e LSH per la passata successiva sui near-duplicate. Sono strumenti complementari della stessa cassetta probabilistica.

Privacy. Alcune pipeline usano le firme LSH come rappresentazione che non rivela il contenuto originale: due parti possono confrontare le firme dei loro dati per stimarne la sovrapposizione senza scambiarsi i documenti grezzi.

La firma è una proiezione che perde l’informazione necessaria a ricostruire l’originale ma conserva quella necessaria a stimare la similarità — esattamente ciò che serve quando si vuole sapere “quanto si sovrappongono i nostri dataset?” senza rivelarne il contenuto. È un uso di nicchia, ma illustra bene la natura di LSH: una compressione che conserva la similarità e butta via il resto.

Memoria e retrieval leggeri. Anche se HNSW e gli altri metodi dominano la ricerca ANN di precisione, LSH resta interessante per casi in cui il vincolo dominante è la semplicità implementativa o la natura streaming dei dati.

Un indice LSH si scrive in poche decine di righe, non richiede una fase di costruzione del grafo, e accetta nuovi elementi uno alla volta senza ricostruire nulla. Per un prototipo, per un sistema con churn elevato dove i dati cambiano in continuazione, o per un retrieval dove un recall del 90% basta, può essere la scelta pragmatica: meno potente di HNSW, ma molto più facile da mettere in piedi e da mantenere.

Dove si rompe

LSH non è il metodo ANN da usare per gli embedding densi. È la cosa più importante da capire, e va detta senza ambiguità. LSH ha garanzie teoriche di sublinearità, ed è stato per anni il riferimento accademico per la ricerca del vicino più prossimo. Ma sulla ricerca ANN di embedding densi — vettori di 768 o 1536 dimensioni prodotti da una rete neurale — i metodi a grafo come HNSW e quelli a quantizzazione come IVF+PQ e ScaNN lo battono nettamente, su recall a parità di latenza.

La ragione è strutturale, ed è la stessa già vista nella sezione di confronto: LSH è data-oblivious, gli altri data-adaptive. Un metodo che guarda i dati può sfruttarne la struttura; uno che non li guarda lascia quel vantaggio sul tavolo. Su ann-benchmarks LSH sta tipicamente sotto la frontiera di Pareto. Oggi LSH è poco usato come indice ANN generale; resta forte dove la semplicità, la natura streaming e le garanzie contano più del recall massimo — ed è esattamente la deduplicazione e il near-duplicate detection. Non è un difetto di LSH: è un disallineamento fra lo strumento e il compito a cui qualcuno prova a forzarlo.

Una sola funzione hash non basta. Senza l’amplificazione AND/OR, un singolo hash LSH fa collidere troppi elementi lontani: i bucket si riempiono di rumore e la scorciatoia perde valore.

L’amplificazione non è un dettaglio implementativo, è la metà del metodo. Saltare quel ragionamento — pensare che basti una funzione “abbastanza buona” — porta a un indice inutilizzabile, perché nessuna singola funzione hash, per quanto ben progettata, può avere $p_1$ vicino a 1 e $p_2$ vicino a 0 nello stesso tempo.

LSH restituisce candidati, non vicini. Il bucket della query contiene quasi solo elementi simili, ma “quasi” non è “solo”: ci sono falsi positivi. Va sempre seguito da una verifica esatta — la Jaccard vera, la distanza vera — sui soli candidati.

Chi tratta l’output di LSH come risultato finale, senza il filtro di verifica, accetta i falsi positivi senza accorgersene. È un errore frequente proprio perché silenzioso: l’indice restituisce qualcosa di plausibile, e solo un controllo a campione rivela che fra i risultati ci sono elementi che non superano la soglia di similarità dichiarata.

Il tuning sbagliato di $k$ e $L$ fa fallire l’indice in modi opposti. Troppo $k$ e troppo poco $L$: la curva a S ha la soglia troppo alta, molti veri near-duplicate vengono persi, il recall crolla. Troppo poco $k$ e troppo $L$: la soglia scende, i bucket si gonfiano di candidati spurii, la verifica esatta a valle diventa costosa, e la latenza sale.

I due fallimenti hanno sintomi opposti — uno perde risultati, l’altro rallenta — e diagnosticare quale dei due si sta vedendo richiede di tornare alla forma della curva, non di girare le manopole a caso. È il motivo per cui vale la pena disegnare $P(s)$ ai punti che contano prima di mandare l’indice in produzione.

MinHash è per insiemi, SimHash per vettori — e si confondono. MinHash stima la Jaccard fra insiemi; SimHash stima la similarità coseno fra vettori. Usare la costruzione sbagliata significa misurare una similarità che non è quella che interessa. Un documento può essere visto come insieme di shingle — e allora MinHash — o come vettore TF-IDF — e allora SimHash. Sono due modellazioni diverse dello stesso oggetto, con metriche diverse, e scegliere la modellazione viene prima di scegliere lo schema LSH.

LSH è sensibile alla scelta della rappresentazione. Per i documenti, MinHash lavora sugli shingle: la dimensione dello shingle è un parametro nascosto e decisivo. Shingle troppo corti (poche parole) rendono quasi ogni documento simile a ogni altro — l’insieme di bigram di due testi qualsiasi della stessa lingua si sovrappone parecchio.

Shingle troppo lunghi, all’opposto, rendono fragile il match: basta una parola cambiata per spezzare uno shingle e abbassare la Jaccard. La qualità del risultato dipende da una scelta che sta a monte di LSH, non dentro l’algoritmo. È un caso generale: LSH è solido sul suo compito, ma eredita tutti i difetti della rappresentazione che gli viene data in pasto.

Il caso adversariale. Chi vuole eludere un sistema di near-duplicate detection basato su LSH conosce la leva: cambiare abbastanza contenuto da scendere sotto la soglia di similarità. Lo spam che riscrive ogni frase, il plagio che parafrasa sistematicamente, riescono a sfuggire a MinHash perché abbassano la Jaccard sotto il flesso della curva.

La radice del problema è che LSH cattura la similarità sintattica — testo letteralmente sovrapposto — non quella semantica. Due testi che dicono la stessa cosa con parole diverse hanno Jaccard bassa, e MinHash non li vede come simili. Per la similarità semantica servono gli embedding, e per cercarli velocemente servono gli altri metodi della mini-serie. È il limite che spiega perché LSH e la ricerca su embedding densi sono strumenti complementari, non concorrenti.

La natura probabilistica non si elimina, si controlla. LSH è un metodo randomizzato: due esecuzioni dello stesso indice, costruito con seed casuali diversi, danno risultati leggermente diversi. Per un vicino genuino la probabilità di essere trovato è alta ma non 1; per un lontano la probabilità di intrufolarsi come candidato è bassa ma non 0. Questo non è un bug — è la natura del metodo, ed è il prezzo della sublinearità.

Ma va capito. Un sistema che richiede garanzie deterministiche — “questo documento non è certamente presente nell’archivio” — non può fidarsi del solo LSH: il falso negativo, per quanto raro, esiste. Si controlla scegliendo $k$ e $L$ in modo che la probabilità di errore scenda sotto una soglia accettabile, e si documenta quel tasso residuo. Trattare LSH come se fosse esatto, dimenticando che ogni risposta ha una probabilità di errore, porta a sorprese difficili da diagnosticare proprio perché rare.

Bucket sbilanciati su dati skewed. La teoria di LSH assume implicitamente che i punti siano sparsi in modo ragionevole. Su dati molto sbilanciati — un corpus con un gruppo enorme di documenti quasi identici e una lunga coda di documenti unici — qualche bucket può diventare gigantesco: tutti i quasi-duplicati di una famiglia molto numerosa finiscono insieme.

La query che cade in quel bucket raccoglie migliaia di candidati, e la verifica esatta a valle, che doveva essere il passo economico, diventa il collo di bottiglia. È un fallimento subdolo perché non dipende dal tuning di $k$ e $L$ in sé, ma dall’interazione fra il tuning e la distribuzione reale dei dati: lo stesso indice che vola su un dataset uniforme arranca su uno sbilanciato.

L’eredità: cosa è rimasto

Questo capitolo chiude la mini-serie ANN e la Parte VIII, e LSH è un buon punto in cui tirare le fila, perché la sua parabola insegna qualcosa che vale per molti algoritmi.

LSH nasce nel 1998 come il risultato teorico che “rimuove la maledizione della dimensionalità”: per un decennio è stato il metodo ANN di riferimento, quello con il teorema. Poi sono arrivati i metodi data-adaptive — HNSW, IVF, ScaNN — che, senza teorema ma con migliore aderenza ai dati reali, lo hanno superato sul terreno per cui era stato pensato, la ricerca dei vicini. Un osservatore frettoloso concluderebbe che LSH è stato “battuto” e archiviato.

La conclusione corretta è diversa. Un algoritmo non vive o muore sul benchmark per cui è nato: vive finché c’è un problema per cui è lo strumento giusto. LSH ha trovato quel problema altrove — la deduplicazione di insiemi, il near-duplicate detection — dove la metrica naturale è la Jaccard, dove la natura streaming conta, dove la semplicità implementativa vale più dell’ultimo punto di recall. E in quel ruolo, oggi, LSH è più diffuso che mai: ogni grande corpus di pre-training degli LLM passa per una pipeline MinHash+LSH.

È la stessa lezione che attraversa la Parte VIII. La programmazione dinamica, il Viterbi, il beam search, gli algoritmi su grafi, le quattro famiglie ANN: nessuno di questi è “il migliore” in assoluto. Ciascuno è la risposta giusta a una forma precisa di problema. Saper riconoscere quella forma — distanza fra insiemi o fra vettori densi, ricerca esatta o approssimata, garanzia teorica o recall empirico — è ciò che separa l’uso competente di questi strumenti dal cargo cult.

Collegamenti

• Approximate nearest neighbor: il problema — pone il problema della ricerca dei vicini e cita Indyk-Motwani 1998: LSH è la famiglia che quel paper introduce, e questo capitolo la sviluppa.
• HNSW: la ricerca vettoriale come passeggiata su un grafo — il metodo a grafo che batte LSH sulla ricerca di embedding densi; il contrasto data-oblivious contro data-adaptive si capisce mettendoli a confronto.
• IVF e product quantization — l’altra famiglia che supera LSH come indice ANN, basata su partizionamento e quantizzazione appresi dai dati.
• ScaNN e DiskANN — chiude la serie sui metodi che dominano i benchmark; LSH è il parente teorico che resta competitivo sulla deduplicazione, non sull’indicizzazione.
• Grafi e algoritmi fondamentali — il vocabolario di base su hash, bucket e strutture dati su cui poggia la costruzione dell’indice LSH.
• Heap e priority queue — l’altra struttura dati di servizio della Parte; come LSH, è un mattone che si incastra dentro algoritmi più grandi piuttosto che essere usato da solo.
• Norme e distanze — coseno, L1, L2, Jaccard: ogni costruzione LSH è legata a una metrica precisa, e la scelta della metrica viene prima della scelta dello schema.
• Prodotto scalare come proiezione e somiglianza — il segno del prodotto scalare con un iperpiano casuale è letteralmente il bit di SimHash.
• Embedding: spazi e direzioni semantiche — gli embedding densi sono il dato su cui LSH perde contro HNSW; chiariscono perché LSH cattura la similarità sintattica e non quella semantica.
• La maledizione della dimensionalità — il fenomeno che LSH è stato il primo metodo a dimostrare di poter aggirare con garanzie teoriche.
• pretraining-dati (in preparazione) — la deduplicazione dei corpora di training, applicazione di massa di LSH oggi: il ponte fra questo capitolo e il lavoro sui dati degli LLM.
• privacy-modelli (in preparazione) — la memorizzazione e l’estrazione di dati di training: la deduplicazione via LSH è una delle leve documentate per ridurre quanto un modello rigurgita verbatim.

Per andare oltre

• Indyk, Motwani, Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality (STOC 1998). Il paper fondativo: definizione di famiglia LSH e prova del tempo sublineare $O(n^\rho)$.
• Charikar, Similarity Estimation Techniques from Rounding Algorithms (STOC 2002). Introduce lo schema a iperpiani casuali (SimHash) per la similarità coseno.
• Broder, Glassman, Manasse, Zweig, Syntactic Clustering of the Web (Computer Networks, 1997). MinHash e il suo uso storico in AltaVista per eliminare le pagine duplicate.
• Lee et al., Deduplicating Training Data Makes Language Models Better (ACL 2022). MinHash+LSH applicato alla deduplicazione dei corpora di training LLM, con misure sull’effetto nella qualità del modello.
• Leskovec, Rajaraman, Ullman, Mining of Massive Datasets, capitolo 3 “Finding Similar Items”. Trattazione didattica completa di shingling, MinHash e LSH, con la derivazione della curva a S; il libro è disponibile gratuitamente online.