Riepilogo Tecnico: Archivi KV-Cache Frattali

Problema

Servire modelli linguistici transformer su contesti lunghi ha spostato la sfida da un limite di calcolo a un limite di memoria. La cache Key-Value (KV), necessaria per l'attenzione autoregressiva, cresce linearmente con la lunghezza del contesto, spesso superando in dimensioni i pesi del modello e limitando le dimensioni dei batch. Mentre le soluzioni esistenti si concentrano sulla compressione lossy (quantizzazione, espulsione, offloading), questo articolo affronta una domanda a valle, spesso implicita: una volta che uno stato KV è stato ridotto a un flusso di simboli tramite la quantizzazione vettoriale, come dovrebbe essere memorizzato tale flusso?

Gli autori sostengono che lo strato di archiviazione non debba essere un blob inerte, ma un componente attivo capace di supportare i pattern di accesso specifici di una cache in crescita: append O(1) ammortizzato (mentre arrivano nuovi token) e accesso casuale O(1) (per recuperare posizioni passate), offrendo potenzialmente funzionalità aggiuntive come il recupero in loco (in-place retrieval).

Metodologia

1. Il Primitivo di Archiviazione: Codici a Mappa Iterata Contrattiva

L'articolo propone l'uso di un codice a mappa iterata contrattiva lossless (specificamente, una generalizzazione della Rappresentazione del Gioco del Caos e delle Mappe di Sequenza Universali) come strato di serializzazione per gli indici KV quantizzati.

• Meccanismo: Una sequenza di simboli su un alfabeto di dimensione $N$ viene mappata in una traiettoria di punti in un piano 2D. Un poligono regolare a $N$ lati è fissato con un vertice per ogni simbolo. Ogni simbolo $c_k$ mappa il punto corrente $p_{k-1}$ in un nuovo punto $p_k$ tramite la contrazione $p_k = V(c_k) + r(p_{k-1} - V(c_k))$, dove $r$ è un rapporto di contrazione.
• Proprietà:
  • Lossless: La mappa è invertibile a patto che il rapporto di contrazione $r$ sia sufficientemente piccolo da garantire "celle" disgiunte per ogni simbolo.
  • Efficienza: La codifica è in tempo lineare. La decodifica consente l'accesso casuale a qualsiasi posizione ricostruendo solo l'intervallo necessario dall'ancora più vicina memorizzata.
  • Auto-similarità: L'insieme dei punti raggiungibili forma un attrattore frattale (ad esempio, un gasket di Sierpinski per $N=3$).
• Implementazione: Per mitigare l'amplificazione dell'errore di virgola mobile durante l'inversione, il codec memorizza un punto per ogni intervallo di lunghezza fissa e ricostruisce gli intervalli tramite una ricerca inversa ancorata.

2. Strategia di Quantizzazione

Gli autori conducono uno studio controllato su GPT-2 (124M) con contesti di 1024 token per determinare lo schema di quantizzazione ottimale che alimenta questo archivio:

• Finestra Esatta: Per mantenere le prestazioni, viene mantenuta una piccola finestra esatta (4 token di "attention sink" + 32 token recenti). Il resto del contesto viene archiviato.
• Varianti di Quantizzazione:
  • Pooled vs. Per-Head: Confronto tra un unico codebook condiviso tra tutte le teste di attenzione rispetto a codebook individuali per ogni testa.
  • Residual Vector Quantization (RVQ): Memorizzazione dei vettori come somma di $s$ indici da codebook.
  • Asimmetria Key/Value: Investigazione dell'impatto differenziale della quantizzazione delle Chiavi (K) rispetto ai Valori (V).

3. Recupero In-Place

L'articolo sfrutta una proprietà geometrica del codice a mappa iterata: i punti che condividono un suffisso comune di lunghezza $s$ sono spazialmente vicini (distanza $\approx 2r^s$). Ciò consente l'esecuzione di query di sottostringa approssimative direttamente sui vettori 2D memorizzati tramite ricerca del vicino più prossimo, senza decompressare il testo circostante.

Risultati Chiave

1. Prestazioni del Codec

Il codec frattale agisce come un primitivo di archiviazione ad alte prestazioni indipendente dal modello:

• Codifica: 0,68 µs/carattere (tempo lineare).
• Accesso Casuale: 311 µs/lookup per un documento di 1M di caratteri.
• Append: 175 µs/token (ammortizzato).

2. Risultati della Quantizzazione (GPT-2, 1024 token)

• Superiorità Per-Head: I codebook per testa superano significativamente i codebook pooled a parità di budget di bit. Un RVQ per-head (profondità 2) riduce l'aumento della perplessità al +15,0% rispetto al +29,2% di un RVQ pooled.
• Asimmetria Key/Value: Quantizzare le Chiavi è circa 4 volte più dannoso per la perplessità rispetto alla quantizzazione dei Valori.
  • Solo Valori (Chiavi esatte): +4,0% perplessità.
  • Solo Chiavi (Valori esatti): +14,5% perplessità.
  • Questo conferma che le Chiavi determinano il routing dell'attenzione (alta sensibilità), mentre i Valori vengono mediati (attenuazione dell'errore).
• Schema Ibrido Ottimale: Allocare più bit alle Chiavi (4 stadi RVQ) e meno ai Valori (2 stadi) offre il miglior compromesso:
  • Compressione: Riduzione di 36× rispetto a una cache fp16.
  • Costo di Perplessità: +11,2% (specificamente +16,6% nella "seconda metà" del contesto dove l'archivio domina).
  • Storage: 1025 byte/token.

3. Capacità di Recupero

• Richiamo Esatto: Il superamento della soglia di distanza tra i punti memorizzati recupera tutte le posizioni con un suffisso corrispondente di lunghezza $\ell$ con un richiamo (recall) di 1,00.
• Precisione: Controllata dalla precisione numerica. Gli indici a doppia precisione ottengono una precisione compresa tra 0,89 e 1,00; la precisione singola serve come filtro grossolano.
• Efficienza: La ricerca brute-force del vicino più prossimo su 100K posizioni nello spazio 2D richiede circa ~0,9 ms/query.
• Decodifica: Il contesto corrispondente viene decodificato all'indietro dal vettore corrispondente senza accedere al testo esterno.

Significato e Rivendicazioni

L'articolo rivendica tre contributi primari, distinguendosi dai lavori concorrenti (es. FibQuant, RetroInfer) che si concentrano sulla geometria del codebook o sui motori di storage vettoriale:

1. Un Formato di Archivio Unificato: Inquadra il codice a mappa iterata contrattiva come un pratico archivio KV che è simultaneamente un archivio lossless, un decodificatore ad accesso casuale e un indice di ricerca in loco. Questa unificazione di storage e recupero in una singola rappresentazione è presentata come il contributo innovativo.
2. Intuizioni sulla Quantizzazione: Quantifica l'asimmetria Key/Value come un budget specifico di perplessità, dimostrando che uno schema ibrido asimmetrico di bit (4x bit per le Chiavi, 2x per i Valori) è il punto operativo ottimale per la compressione di contesti lunghi.
3. Memoria Ricercabile: Dimostra che l'archivio supporta il matching dei suffissi direttamente sulla rappresentazione compressa, consentendo il decoding potenziato dal recupero (retrieval-augmented decoding) in cui il modello può localizzare i contesti passati rilevanti senza materializzare l'intera cache.

Limitazioni Riconosciute dagli Autori

• Scala: Gli esperimenti sono limitati a GPT-2 (124M) e un singolo contesto di 1024 token. I risultati su modelli più grandi non sono stati testati (sebbene siano probabilmente più tolleranti alla quantizzazione).
• Addestramento del Codebook: I codebook sono addestrati per corpus, non ammortizzati su più dati.
• Ambito di Recupero: Il recupero è strettamente basato sul matching della struttura della sequenza (suffissi), non sul recupero semantico tramite embedding.
• Rapporto di Compressione: Il rapporto di compressione grezza del codec frattale è paragonabile ai normali byte-packer; il suo vantaggio risiede nel pattern di accesso (accesso casuale/ricerca) piuttosto che nella riduzione pura delle dimensioni.
• Benchmarking: L'articolo non effettua il benchmarking contro i design specifici dei codebook dei lavori concorrenti, riconoscendo che combinare i loro quantizzatori con questo formato di storage è un lavoro futuro.