Efficient Vector Search in the Wild: One Model for Multi-K Queries

Each language version is independently generated for its own context, not a direct translation.

🚀 OMEGA: Il "Super-Chef" che cucina per tutti senza riaccendere il forno

Immagina di avere un ristorante di lusso (il tuo database di vettori) dove i clienti (le applicazioni) ordinano piatti.

A volte un cliente vuole solo un antipasto (cerca 1 risultato, $K=1$ ).
Altre volte ne vuole cinque (cerca 5 risultati, $K=5$ ).
E a volte ne vuole cinquanta (cerca 50 risultati, $K=50$ ).

Il problema è che, finora, i cuochi (i sistemi di ricerca attuali) erano specializzati: se imparavi a cucinare perfettamente un solo antipasto, quando arrivava l'ordine per 50 piatti, o sbagliavi tutto (troppa poca accuratezza) o ci mettevi un'eternità a cucinarli (troppo lento).

OMEGA è la nuova ricetta che risolve questo caos. È un sistema che impara a cucinare un solo piatto alla volta (il primo), ma è così intelligente che può servire qualsiasi numero di piatti, velocemente e perfettamente, senza dover riaccendere il forno ogni volta.

1. Il Problema: Il "Chef" troppo rigido

Attualmente, i sistemi di ricerca usano modelli "addestrati" su un numero specifico di risultati (diciamo, sempre 10).

Se chiedi 10 risultati: funziona bene.
Se chiedi 100 risultati: lo chef si ferma troppo presto perché è abituato a fermarsi a 10. Il cliente riceve piatti sbagliati (bassa accuratezza).
Se chiedi 2 risultati: lo chef continua a cucinare fino a 10 per sicurezza, sprecando tempo e risorse (bassa velocità).

Inoltre, per addestrare uno chef per ogni possibile numero di piatti (da 1 a 100), ci vorrebbe un tempo di preparazione (preprocessing) enorme, come se dovessi riorganizzare l'intera cucina ogni volta che cambia il menu.

2. La Soluzione OMEGA: "Impara il Primo, Trova gli Altri"

OMEGA cambia completamente strategia. Invece di addestrare 100 chef diversi, ne addestra uno solo, specializzato a trovare il miglior piatto in assoluto (il Top-1).

Ecco come funziona la sua magia:

A. Il Trucco del "Mascheramento" (Cercare uno alla volta)

Immagina che lo chef OMEGA trovi il miglior antipasto.

Lo mette nel piatto del cliente.
Poi dice: "Ok, ora nascondiamo quel piatto dalla cucina e cerchiamo il secondo migliore tra quelli rimasti".
Lo chef, che è bravissimo a trovare il "migliore", trova subito il secondo migliore (che era il migliore tra i restanti).
Ripete il processo: "Nascondi il secondo, trova il terzo migliore tra i restanti".

In pratica, OMEGA trasforma la ricerca di 50 piatti in 50 ricerche veloci di 1 piatto. Non serve un nuovo modello, basta riutilizzare quello che già sa fare benissimo.

B. La "Bussola" delle Orme (Traiettoria)

C'era un problema: quando nascondi un piatto, la cucina cambia leggermente e le vecchie regole non funzionavano più.
OMEGA ha scoperto una nuova "bussola". Invece di guardare la distanza esatta di un singolo piatto (che cambia se ne nascondi uno), guarda il percorso (la traiettoria) che fa lo chef mentre cerca.

È come se lo chef guardasse il modo in cui scende le scale verso il piano terra. Che tu nasconda un gradino o no, la tendenza a scendere rimane la stessa.
Questa "traiettoria" è così robusta che il modello impara una volta sola e funziona per qualsiasi numero di piatti.

C. La "Pallina di Cristallo" Statistica (Per non chiamare lo chef troppe volte)

Chiamare lo chef 50 volte per trovare 50 piatti potrebbe essere comunque lento. OMEGA ha un altro trucco: la statistica.
Immagina di aver già trovato i primi 20 piatti. OMEGA sa, grazie a una tabella statistica preparata in anticipo, che "se ho trovato 20 piatti, c'è il 90% di probabilità che i prossimi 30 siano già nella mia lista".
Invece di chiamare lo chef per controllare ogni singolo piatto, OMEGA guarda la sua "pallina di cristallo" (la tabella statistica) e dice: "Ok, siamo sicuri al 95% che abbiamo abbastanza piatti, fermiamoci!".
Questo riduce drasticamente il numero di volte in cui deve "pensare" (chiamare il modello), risparmiando tempo.

3. I Risultati: Perché è un miracolo?

Risparmio di tempo in cucina (Preprocessing): OMEGA ha bisogno di solo il 16-30% del tempo necessario agli altri sistemi per prepararsi. È come se invece di dover cucinare 100 menu diversi, ne cucinassi uno solo e poi lo adattassi.
Velocità di servizio (Latency): Rispetto ai migliori sistemi attuali, OMEGA è più veloce del 6-33%. Non spreca tempo a cercare piatti che non servono.
Precisione: Raggiunge lo stesso livello di accuratezza degli altri, ma senza sprecare risorse.

In Sintesi

OMEGA è come un investitore geniale: invece di comprare 100 azioni diverse (addestrare 100 modelli), compra una sola azione di altissima qualità (il modello Top-1) e usa la sua intelligenza per prevedere come si comporterà il mercato per qualsiasi numero di azioni (qualsiasi $K$ ).

Grazie a questo approccio, i database vettoriali (usati per raccomandazioni, chatbot AI, ricerca immagini) diventano più veloci, più economici e più precisi, anche quando gli utenti chiedono cose molto diverse tra loro.

Il messaggio finale: Non serve un sistema diverso per ogni richiesta. Serve un sistema intelligente che sappia adattarsi, e OMEGA è proprio quello.

Each language version is independently generated for its own context, not a direct translation.

Titolo: Ricerca Vettoriale Efficiente nel Mondo Reale: Un Modello per Query Multi-K

Autori: Yifan Peng, Jiafei Fan, Xingda Wei, et al. (Shanghai Jiao Tong University, Boston University, Alibaba Group)

1. Il Problema

Le basi di dati vettoriali sono fondamentali per applicazioni a bassa latenza come i motori di raccomandazione e la generazione aumentata tramite recupero (RAG). L'operazione chiave è la Ricerca del Vicino più Vicino Approssimato (ANNS), che restituisce i primi $K$ vettori più simili a una query.

Esistono due sfide principali nel deployment reale ("in the wild"):

Query Multi-K: Le applicazioni reali richiedono spesso risultati con valori di $K$ diversi e variabili (es. da 1 a centinaia) per la stessa collezione di dati.
Costo di Preprocessing: L'aggiornamento degli indici (compattazione) richiede risorse computazionali significative. I fornitori di servizi cloud (come Alibaba) non addebitano i costi di preprocessing agli utenti, rendendo cruciale minimizzare questo onere.

Limiti degli approcci attuali:

I metodi di ricerca appresi (Learned Search) esistenti, come DARTH e LAET, sono addestrati per un valore specifico di $K$ .
Se un modello addestrato su $K^*$ viene usato per una query con $K > K^*$ , si verifica una degradazione dell'accuratezza (under-searching, poiché l'area di ricerca necessaria è più grande).
Se viene usato per $K < K^*$ , si verifica una perdita di prestazioni (over-searching, poiché l'area di ricerca è più grande del necessario).
Addestrare modelli separati per ogni $K$ frequente o un unico modello generalizzato richiede un tempo di preprocessing ordini di grandezza superiore, rendendolo impraticabile per ambienti di produzione dinamici.

2. Metodologia: OMEGA

OMEGA (One-Model Efficient Generalized ANNS) è il primo metodo di ricerca appresa generalizzabile a $K$ che utilizza un singolo modello addestrato su $K=1$ per gestire query con qualsiasi $K$ .

Idea Fondamentale

Il problema di trovare i primi $K$ risultati può essere ridotto a $K$ problemi di ricerca del primo risultato ( $K$ volte il top-1).

Una volta trovato il vettore top-1, questo viene "mascherato" (escluso) dal set di ricerca.
La ricerca del top-2 diventa quindi una ricerca del top-1 sul set rimanente.
Questo processo si ripete iterativamente fino a trovare tutti i $K$ risultati.

Sfide Risolte e Soluzioni Tecniche

Sfida 1: Come addestrare un modello base efficace e generalizzabile?

Problema: I modelli esistenti usano caratteristiche come le "distanze minime" assolute. Quando si mascherano i vettori trovati, la distribuzione delle distanze cambia, rendendo il modello inaffidabile per le iterazioni successive.
Soluzione OMEGA: Introduzione delle Traiettorie di Distanza (Distance-Trajectory).
- Invece di guardare la distanza assoluta, il modello analizza la tendenza di riduzione della distanza durante la traversa del grafo.
- Questa tendenza (un calo rapido man mano che ci si avvicina al target) rimane valida anche dopo aver mascherato i vettori precedenti.
- Il modello viene addestrato solo su query top-1 utilizzando queste caratteristiche basate sulla traiettoria (estratte tramite una finestra scorrevole sulle ultime distanze visitate).

Sfida 2: Come ridurre l'overhead delle invocazioni del modello?

Problema: Chiamare il modello $K$ volte per ogni query introdurrebbe un overhead computazionale eccessivo, annullando i benefici della ricerca anticipata.
Soluzione OMEGA: Previsione Statistica (Statistical Forecast).
- Sfrutta una proprietà statistica: data la scoperta di $N$ vicini (dove $N < K$ ), la probabilità che il $r$ -esimo vero vicino sia già nel set di ricerca segue una distribuzione prevedibile.
- Viene costruita una tabella di lookup 2D offline che mappa la coppia $(N, r)$ alla probabilità di successo.
- Durante la ricerca, se la previsione statistica indica che la recall target è già soddisfatta senza bisogno di invocare il modello, la ricerca viene interrotta anticipatamente. Questo riduce drasticamente il numero di chiamate al modello per $K$ elevati.

3. Contributi Chiave

Generalizzazione a $K$ con un solo modello: OMEGA addestra un unico modello su $K=1$ , eliminando la necessità di addestrare modelli multipli per diversi $K$ , riducendo i costi di preprocessing.
Feature Engineering Robusto: L'uso delle "Traiettorie di Distanza" invece delle distanze assolute permette al modello di generalizzare efficacemente anche quando i vettori vengono mascherati durante il processo iterativo.
Ottimizzazione Statistica: L'introduzione di una previsione basata su statistiche permette di saltare le invocazioni del modello per le iterazioni finali, bilanciando accuratezza e latenza.
Implementazione Open Source: OMEGA è stato integrato in hnswlib e sta per essere integrato nel database vettoriale open source di Alibaba, Zvec.

4. Risultati Sperimentali

Valutazioni condotte su dataset pubblici (BIGANN, DEEP, GIST) e su collezioni di produzione reali di Alibaba.

Latenza:
- Rispetto ai metodi di ricerca appresa più avanzati (DARTH, LAET), OMEGA riduce la latenza media del 6–33% a parità di budget di preprocessing.
- Rispetto ai metodi ANNS tradizionali con iperparametri manuali, riduce la latenza del 25–65% mantenendo la stessa recall.
Costo di Preprocessing:
- OMEGA richiede solo il 16–30% del tempo di preprocessing necessario ai baselines per raggiungere la latenza ottimale.
- Addestrare modelli multipli per coprire il 39% delle query più frequenti aumenterebbe i costi di preprocessing di 1.95x; OMEGA mantiene il costo minimo (addestramento top-1).
Accuratezza (Recall):
- OMEGA mantiene costantemente la recall target (es. 0.95 o 0.99) su tutte le query multi-K, superando i modelli addestrati su $K$ specifici che falliscono quando il $K$ di query cambia.
Efficienza Totale (CPU):
- Considerando sia il tempo di preprocessing che quello di servizio, OMEGA riduce il tempo totale di CPU del 4–24% rispetto ai baselines, grazie alla drastica riduzione della latenza di servizio.

5. Significato e Impatto

OMEGA risolve il compromesso fondamentale tra accuratezza, latenza e costo di preprocessing nelle basi di dati vettoriali reali.

Per i fornitori di servizi: Riduce i costi operativi (CPU) e permette di servire carichi di lavoro dinamici e multi-K senza penalizzare le prestazioni.
Per gli sviluppatori: Offre un'implementazione "plug-and-play" che non richiede una complessa gestione di modelli multipli o tuning manuale degli iperparametri per ogni valore di $K$ .
Innovazione: Dimostra che è possibile generalizzare l'apprendimento automatico per la ricerca vettoriale non addestrando modelli complessi su tutti i casi d'uso, ma sfruttando le proprietà strutturali dei grafi (traiettorie) e le statistiche dei dati.

In sintesi, OMEGA rappresenta un passo avanti significativo verso l'adozione diffusa di metodi di ricerca appresa in ambienti di produzione scalabili ed economici.