Il contesto della ricerca MIPS e le limitazioni dei metodi tradizionali

La ricerca del massimo prodotto interno (Maximum Inner Product Search, MIPS) è alla base di sistemi di raccomandazione, ricerca testuale e, più recentemente, della generazione aumentata da recupero (Retrieval‑Augmented Generation, RAG). In pratica, data una query rappresentata da un vettore, il sistema deve individuare, all’interno di un database contenente milioni di chiavi vettoriali, quella che massimizza il prodotto interno con la query. Il documento associato a quella chiave viene poi utilizzato per rispondere alla domanda dell’utente.

Man mano che il numero di chiavi sale a decine di milioni e le dimensioni dei vettori raggiungono migliaia, il costo di confrontare la query con tutte le chiavi diventa proibitivo. Per ridurre la complessità, sono stati proposti numerosi metodi approssimativi basati su clustering, quantizzazione e strutture di indicizzazione avanzate. Tuttavia, questi approcci si focalizzano quasi esclusivamente sulla geometria del set di chiavi, assumendo implicitamente che la distribuzione delle query sia simile a quella delle chiavi o ignorando del tutto le caratteristiche delle query.

Questa assunzione è particolarmente problematica nel contesto RAG, dove le query sono tipicamente brevi domande generate dagli utenti, mentre le chiavi rappresentano lunghi testi curati e informativi. Inoltre, molti casi d’uso di MIPS in produzione servono una base utenti stabile, con una distribuzione delle query ben definita, lasciando inutilizzati potenziali guadagni di efficienza derivanti da metodi specifici per quella distribuzione.

Support function e apprendimento supervisionato: la nuova proposta di Apple

Il lavoro presentato al ICML 2026, “Amortizing Maximum Inner Product Search with Learned Support Functions”, propone di addestrare piccole reti neurali (NN) offline per un database di chiavi fisso, al fine di guidare le query verso la chiave migliore in modo più rapido.

Il principio chiave è riconoscere che la funzione che, data una query, restituisce il più alto prodotto interno con le chiavi è la funzione di supporto del set di chiavi, un concetto ben noto nell’analisi convessa. Tale funzione possiede due proprietà fondamentali:

    • è convessa, perciò può essere approssimata da Input Convex Neural Networks (ICNN), reti progettate per modellare funzioni convesse;
    • il suo gradiente in un punto di query restituisce direttamente la chiave ottimale.

Con questa osservazione, gli autori propongono due architetture:

SupportNet

Una ICNN che apprende la funzione di supporto per ogni cluster di chiavi. L’output è lo score di supporto, cioè una stima della qualità del miglior elemento del cluster rispetto alla query. Questo consente un routing più preciso rispetto al semplice confronto con il centroide.

KeyNet

Una rete che, data la query, restituisce direttamente il vettore della chiave migliore. Per mantenere coerenza geometrica, le predizioni sono regolarizzate con una perdita derivata dal teorema di Eulero per funzioni omogenee, garantendo che il risultato rimanga allineato alla struttura della funzione di supporto.

Processo di addestramento e generazione del dataset

Entrambe le reti vengono addestrate su esempi estratti dalla distribuzione reale delle query. Il flusso di lavoro è il seguente:

    • Campionare un gran numero di query (tipicamente embedding di domande testuali);
    • Eseguire una ricerca esaustiva per ogni query, ottenendo la chiave ottimale e lo score di supporto corrispondente;
    • Costruire un dataset supervisionato contenente (query, score) per SupportNet e (query, chiave) per KeyNet;
    • Allenare le reti tramite regressione, minimizzando la differenza tra le predizioni e i valori di riferimento.

Poiché il training è effettuato una sola volta per un database fisso, l’onere computazionale è amortizzato: il costo iniziale di generare il dataset e addestrare le reti viene compensato da un notevole risparmio durante l’inferenza, quando le query devono essere elaborate in tempo reale.

Vantaggi del routing basato su SupportNet rispetto ai centroidi

Nei tradizionali sistemi a clustering, la query viene confrontata con i centroidi dei k cluster; il cluster più vicino viene poi esplorato esaustivamente. Questo approccio riduce il numero di confronti da n a n/k, ma introduce errori perché il centroide non cattura la dispersione interna del cluster.

SupportNet, invece, fornisce per ogni cluster uno score di supporto che stima il miglior prodotto interno possibile all’interno del cluster. In presenza di outlier (chiavi lontane dal centroide ma vicine alla query), il metodo basato sui centroidi può assegnare un punteggio basso al cluster, saltandolo e perdendo la soluzione ottimale. Con i support scores, la decisione di routing è più informata e tende a includere il cluster contenente la chiave ideale.

Risultati sperimentali su Natural Questions

Gli esperimenti sono stati condotti sul benchmark Natural Questions, che associa domande di conoscenza generale a passaggi estratti da un archivio di circa 2,6 milioni di documenti. I dati sono stati suddivisi in 128 cluster.

SupportNet è stato addestrato in quattro dimensioni (XS, S, M, L) corrispondenti al 1 %, 5 %, 10 % e 20 % della dimensione totale del database. Le metriche chiave valutate sono:

    • Recall di routing: percentuale di query il cui cluster contenente la chiave ottimale è tra quelli selezionati per la ricerca;
    • Recall di recupero: frazione di query per cui il documento corretto è stato effettivamente restituito nella top‑k risultati;
    • Costo computazionale: numero medio di prodotti interni calcolati per query.

I grafici (Figure 4 del paper) mostrano che, a parità di costi, il modello L (20 %) raggiunge un recall di routing superiore del 12 % rispetto al metodo tradizionale basato su centroidi, e un recall di recupero migliorato di oltre il 15 % nella top‑10. Inoltre, il numero medio di confronti richiesti si riduce di circa il 30 % rispetto alla ricerca esaustiva, dimostrando l’efficacia dell’approccio amortizzato.

Implicazioni per la generazione aumentata da recupero (RAG)

Nel contesto RAG, la rapidità e la precisione del recupero dei documenti sono determinanti per la qualità della risposta generata. Un routing più accurato garantisce che il documento più pertinente sia incluso nel prompt fornito al modello di linguaggio, migliorando la coerenza e la factualità della risposta. Inoltre, la riduzione dei costi computazionali consente di scalare a collezioni più grandi senza sacrificare la latenza, aprendo la porta a applicazioni in tempo reale su dispositivi edge.

Conclusioni e prospettive future

Il lavoro di Apple introduce un cambio di paradigma nella ricerca MIPS: invece di costruire indici agnostici rispetto alle query, si apprende una mappatura ottimale dal punto di vista della distribuzione reale delle richieste. Grazie alla teoria delle funzioni di supporto e alle ICNN, è possibile realizzare router intelligenti (SupportNet) e predittori di chiavi (KeyNet) che, una volta addestrati, offrono velocità e accuratezza superiori.

Le prospettive future includono:

    • Estendere il framework a scenari dinamici, dove le chiavi vengono aggiornate periodicamente;
    • Integrare tecniche di distillazione per ridurre ulteriormente le dimensioni delle reti senza perdita di performance;
    • Applicare il concetto di support function a altri compiti di ricerca vettoriale, come il nearest neighbor search con metriche diverse dal prodotto interno.

In sintesi, l’amortizzazione della ricerca MIPS mediante funzioni di supporto apprese rappresenta un passo decisivo verso sistemi di recupero più intelligenti, economici e adatti alle esigenze specifiche delle applicazioni RAG moderne.