Riepilogo Tecnico: CachePrune

Enunciato del Problema

I Modelli Linguistici di Grandi Dimensioni (LLM) si affidano alla memorizzazione nella cache Key-Value (KV) per accelerare l'inferenza, e i moderni sistemi di servizio condividono spesso le cache KV tra diversi utenti per ridurre il calcolo ridondante e l'utilizzo della memoria. Tuttavia, la condivisione illimitata tra utenti introduce vulnerabilità significative di canale laterale. Gli avversari possono sondare il sistema con sequenze di token specifiche; se il sistema riutilizza le voci KV memorizzate nella cache (rilevate tramite latenza ridotta o priorità di scheduling), l'avversario può inferire la presenza di tali token nel prompt di una vittima, ricostruendo potenzialmente input sensibili.

Le difese attuali disabilitano tipicamente l'intera condivisione tra utenti per prevenire la fuoriuscita di dati. Questo approccio "tutto o niente" è eccessivamente grossolano. In pratica, i prompt degli utenti contengono contenuti sostanzialmente irrilevanti per la privacy (ad esempio, istruzioni di sistema, modelli pubblici o passaggi recuperati nelle pipeline RAG), dove i token sensibili (come i dati personali identificabili, PII) costituiscono spesso una minuscola frazione dell'input totale (ad esempio, ~2,3% dell'input dell'utente). Disabilitare tutta la condivisione sacrifica guadagni significativi di efficienza. Inoltre, i meccanismi di condivisione a grana fine esistenti (ad esempio, CacheBlend, CacheCraft) operano a livelli di blocchi fissi (ad esempio, 512 token). Se un singolo token sensibile cade all'interno di un blocco, l'intero blocco deve essere scartato, portando a una sostanziale perdita di contenuti riutilizzabili.

Metodologia: CachePrune

Gli autori propongono CachePrune, un meccanismo di condivisione della cache KV consapevole della privacy che abilita il riutilizzo a grana fine, a livello di token, delle voci KV non sensibili. Il sistema è progettato per rompere il compromesso tra privacy ed efficienza condividendo selettivamente solo i segmenti irrilevanti per la privacy.

Architettura di Sistema

CachePrune integra cinque componenti principali sopra framework esistenti come vLLM:

1. Rilevatore di Sensibilità: Un'interfaccia pluggabile (che supporta regole definite dall'utente, espressioni regolari o classificatori come Presidio) che identifica i token sensibili in un prompt e genera una maschera di sensibilità binaria.
2. Annotatore KV: Dopo l'inferenza, questo modulo analizza la matrice dei punteggi di attenzione per derivare segmenti riutilizzabili dai token non sensibili. Identifica segmenti "auto-contextualizzati" dove l'attenzione intra supera l'attenzione inter.
3. Recuperatore KV: Prima di generare una risposta, questo modulo cerca nella KV Pool segmenti che corrispondono ai token non sensibili della richiesta in arrivo utilizzando un algoritmo basato su hash scorrevole (rolling-hash).
4. Motore LLM: Completa l'inferenza calcolando le voci KV mancanti e ricalcolando token specifici all'interno dei segmenti riutilizzati per mantenere la qualità della generazione.
5. KV Pool: Archivia e indicizza i segmenti KV riutilizzabili, gestendone il ciclo di vita e l'evizione.

Soluzioni Algoritmiche Chiave

Il sistema affronta due sfide principali:

1. Derivazione Efficiente di Segmenti KV Riutilizzabili (Sfida 1)

• Problema: Determinare la riutilizzabilità a livello di token richiede di valutare le dipendenze di attenzione per sottostringhe arbitrarie. Un approccio ingenuo che controlla tutte le sottostringhe contro la matrice di attenzione risulta in una complessità di $O(n^4)$, che è proibitiva.
• Soluzione: CachePrune impiega un algoritmo di tabella ad area sommata (immagine integrale) sulla matrice dei punteggi di attenzione. Ciò permette al sistema di calcolare le somme di attenzione intra e inter per qualsiasi sottostringa candidata in tempo $O(1)$ dopo una fase di pre-elaborazione di $O(n^2)$. Questo riduce la complessità complessiva della ricerca di segmenti riutilizzabili ottimali a $O(n^2)$.
• Strategia di Ricalcolo: All'interno di un segmento riutilizzabile, i token con alta attenzione inter (dipendenza dal contesto esterno) sono contrassegnati per il ricalcolo per preservare la qualità dell'output.

2. Recupero Efficiente di Segmenti a Lunghezza Variabile (Sfida 2)

• Problema: A differenza dei blocchi di dimensioni fisse, la condivisione a livello di token produce segmenti a lunghezza variabile. Le ricerche dirette tramite hash falliscono perché uno spostamento di un singolo token rompe l'allineamento, rendendo il recupero un problema di contenimento di sottostringhe con complessità $O(n \times m)$ per la ricerca ingenua.
• Soluzione: Il sistema utilizza un algoritmo di recupero basato su hash scorrevole.
  • Filtraggio del Prefisso: Pre-calcola gli hash per i primi 128 token dei segmenti memorizzati nella cache. Le richieste in arrivo vengono scansionate con una finestra scorrevole per trovare potenziali corrispondenze in tempo $O(n)$.
  • Verifica Completa: I candidati subiscono un controllo rapido dell'hash del prefisso seguito da una verifica con hash crittografico (SHA-256) per garantire la correttezza senza confronto token per token.

Contributi Chiave

1. Primo Sistema Pratico di Condivisione a Grana Fine: CachePrune è il primo sistema ad abilitare la condivisione selettiva della cache KV a livello di token, rompendo efficacemente il compromesso privacy-efficienza riutilizzando le voci non sensibili mentre blocca quelle sensibili.
2. Innovazioni Algoritmiche: Il documento introduce un algoritmo adattivo che utilizza tabelle ad area sommata per la derivazione efficiente dei segmenti e un meccanismo a hash scorrevole per il recupero a lunghezza variabile, superando i limiti degli approcci a blocchi fissi.
3. Valutazione Completa: Gli autori implementano CachePrune su vLLM e lo valutano su tre dataset (QASPER, NarrativeQA, QMSum) e molteplici modelli (Mistral-7B, Qwen2.5).

Risultati

La valutazione dimostra che CachePrune ottiene guadagni significativi di efficienza senza compromettere la privacy o la qualità della generazione:

• Privacy:
  • Fuoriuscita Diretta: I token contrassegnati come sensibili non possono essere recuperati tramite canali laterali basati sul riutilizzo (tasso di recupero esatto 0%).
  • Fuoriuscita Contestuale: L'inferenza di contenuti sensibili da token non sensibili rimane limitata (2,2% di recupero esatto e 6,4% di recupero semantico sotto attacchi SOTA).
  • Rilevamento Imperfetto: Il sistema è robusto agli errori di rilevamento; i falsi negativi aumentano la fuoriuscita diretta, mentre i falsi positivi riducono conservativamente la fuoriuscita contestuale.
• Efficienza:
  • Riduzione del TTFT: CachePrune riduce il Time-to-First-Token (TTFT) fino a 4,5 volte rispetto alle baseline senza condivisione.
  • Tassi di Hit: Raggiunge un riutilizzo della cache KV fino al 94,57%.
  • Vantaggio a Grana Fine: Anche senza vincoli di privacy, la condivisione a livello di token di CachePrune migliora i tassi di hit della cache del 44% rispetto ai metodi a blocchi fissi all'avanguardia (CacheCraft, CacheBlend, EPIC).
• Qualità: La qualità della generazione (misurata tramite punteggio F1 e ROUGE-L) rimane comparabile al ricalcolo completo, con deviazioni trascurabili.

Significato e Affermazioni

Il documento afferma che CachePrune fornisce una base pratica per il servizio sicuro di LLM in ambienti multi-tenant. Superando la frammentazione a blocchi di dimensioni fisse, massimizza il potenziale di riutilizzo dei contenuti irrilevanti per la privacy (come prompt di sistema e dati pubblici) isolando rigorosamente gli input sensibili degli utenti. Gli autori sottolineano che il loro approccio non richiede nuovi meccanismi di rilevamento della privacy, ma si integra con quelli esistenti per fornire un'interfaccia unificata per inferenze sicure e ad alte prestazioni. Il lavoro evidenzia che la gestione KV a grana fine non è solo fattibile, ma essenziale per bilanciare le esigenze concorrenti di privacy ed efficienza nell'infrastruttura moderna degli LLM.