Riepilogo Tecnico: FibQuant: Quantizzazione Vettoriale Universale per la Compressione della KV-Cache ad Accesso Casuale

1. Enunciato del Problema

L'inferenza in contesti lunghi nei trasformatori autoregressivi è sempre più vincolata dalla larghezza di banda e dalla capacità della memoria, principalmente a causa della cache Key-Value (KV). Le dimensioni della cache crescono linearmente con la lunghezza del contesto, la dimensione del batch, il numero di livelli e il numero di teste, e deve essere accessibile ad ogni passo di decodifica.

I metodi di compressione esistenti affrontano un vincolo critico dei sistemi: l'accesso casuale. Un codec di cache deployabile deve memorizzare le rappresentazioni a indirizzi fissi in modo che la chiave o il valore di qualsiasi token possano essere decodificati indipendentemente tramite semplice aritmetica degli indirizzi. Questo vincolo esclude la codifica a lunghezza variabile e le rappresentazioni dipendenti dal contesto, imponendo l'uso di quantizzatori a tasso fisso.

I codec a accesso casuale all'avanguardia attuali, come TURBOQUANT, adottano un approccio "normalizza–ruota–quantizza":

1. Memorizzare la norma del vettore.
2. Applicare una rotazione ortogonale casuale condivisa (Haar).
3. Quantizzare ogni coordinata ruotata indipendentemente utilizzando una tabella scalare Lloyd–Max.

Sebbene questa interfaccia sia universale e ad accesso casuale, il paper sostiene che sia geometricamente subottimale. Una volta normalizzato un vettore e sottoposto a rotazione Haar, un blocco di $k$ coordinate consecutive non forma un prodotto indipendente di marginali scalari. Invece, forma una sorgente sferico-Beta sulla palla unitaria. I codec scalari trattano le coordinate come indipendenti, scartando la struttura geometrica (correlazioni radiali e angolari) intrinseca nel blocco ruotato. Inoltre, i metodi scalari faticano a operare efficacemente al di sotto di un bit per coordinata, creando un "divario sub-un-bit" in cui i codec universali attuali privi di calibrazione falliscono.

2. Metodologia: FibQuant

FibQuant propone un quantizzatore vettoriale universale a tasso fisso che mantiene la stessa interfaccia "normalizza–ruota" dei metodi scalari, ma sostituisce le tabelle delle coordinate scalari con un codice vettoriale radiale–angolare condiviso.

2.1 La Sorgente Canonica

Gli autori dimostrano che l'interfaccia normalizza–poi-rotazione Haar induce una distribuzione di sorgente universale indipendentemente dalla distribuzione originale dei dati KV.

• Normalizzazione: Rimuove la scala.
• Rotazione Haar: Rimuove l'orientamento.
• Risultato: Il vettore unitario ruotato è uniformemente distribuito secondo Haar sulla sfera $S^{d-1}$. Di conseguenza, qualsiasi blocco di $k$ coordinate consecutive segue una specifica densità sferico-Beta $f_{d,k}$ sulla palla unitaria $B^k$.
• Implicazione: Un singolo codice offline può servire tutti i livelli, le teste, i prompt e i modelli, poiché la distribuzione della sorgente è invariante rispetto all'input specifico.

2.2 Costruzione del Codice

Il codice FibQuant è costruito per adattarsi alla sorgente sferico-Beta, combinando tre componenti:

1. Raggi ($r_n$): Adattati alla densità radiale della sorgente sferico-Beta utilizzando le regole di compansione Bennett–Gersho. Per $k=2$, ciò produce una soluzione in forma chiusa che coinvolge raggi quantili Beta.
2. Direzioni ($u_n$): Approssimate utilizzando insiemi di punti sferici quasi uniformi per garantire un impaccamento angolare uniforme:
   • $k=2$: Spirale di Fibonacci planare (Quantizzatore Aureo).
   • $k=3$: Sfera di Fibonacci.
   • $k \ge 4$: Sequenze a bassa discrepanza Roberts–Kronecker.
3. Raffinamento: Un algoritmo Lloyd–Max multi-riavvio raffina l'inizializzazione deterministica per minimizzare l'Errore Quadratico Medio (MSE) per la dimensione specifica del codice finito $N$.

2.3 Codifica e Decodifica

• Codificatore: Calcola la norma $\nu = \|x\|_2$, ruota il vettore unitario $\Pi x / \nu$, lo divide in $d/k$ blocchi di dimensione $k$, ed esegue una ricerca del vettore di codice più vicino nel codice condiviso.
• Decodificatore: Recupera il vettore di codice, ricostruisce il blocco, concatena i blocchi, applica la rotazione inversa e scala per la norma.
• Tasso: Il tasso di bit è $b = (\log_2 N) / k$ bit per coordinata. Variando $N$ e $k$, FibQuant realizza un asse di tasso denso, abilitando punti operativi a frazione di bit e sub-un-bit senza indirizzamento a lunghezza variabile.

3. Contributi Chiave

3.1 Identificazione della Sorgente Canonica

Il paper dimostra (Teorema 1) che l'interfaccia norma–poi-rotazione Haar mappa qualsiasi distribuzione di input non nulla sulla stessa marginale sferico-Beta $f_{d,k}$. Ciò stabilisce che un codice offline condiviso è l'oggetto universale teoricamente corretto per la compressione della KV-cache.

3.2 Vantaggio Vettoriale rispetto alla Specializzazione Scalare

Gli autori dimostrano (Teorema 2) che il codice vettoriale ottimale $k$ domina strettamente la specializzazione del prodotto scalare (dove $k=1$) a tassi equivalenti. Il guadagno ad alto tasso è scomposto in due componenti:

1. Fattore di Modellazione della Cella ($\gamma_{cell}$): Le celle di quantizzazione vettoriale (es. esagonali in 2D) sono più efficienti delle celle scalari rettangolari.
2. Fattore di Adattamento alla Densità ($\gamma_{dens}$): Adattare la densità congiunta sferico-Beta è superiore all'adattare solo le marginali scalari.

3.3 Asse di Tasso Denso

A differenza delle tabelle Lloyd–Max scalari limitate a tassi a bit interi, FibQuant realizza un insieme denso di tassi $b \in (0, \infty)$. Ciò permette l'operazione nel regime sub-un-bit (es. $b \approx 0.19$), un regime in cui i codec universali a accesso casuale attuali cessano di funzionare.

4. Risultati Sperimentali

4.1 Prestazioni di Codifica della Sorgente

Sulla sorgente canonica sferico-Beta, FibQuant dimostra una dominanza stretta su TURBOQUANT scalare a tutti i tassi interi. Colma inoltre i vuoti tra i tassi interi, fornendo punti operativi che i metodi scalari non possono raggiungere.

4.2 Compressione della KV-Cache (GPT-2 Small)

Valutato su cache KV di GPT-2 small con la similarità del coseno dell'output dell'attenzione come metrica:

• FibQuant traccia un fronte memoria–fedeltà da 5× compressione (a similarità 0.99) a 34.1× compressione (a similarità 0.946).
• A rapporti di compressione elevati (>10×), FibQuant è l'unico metodo universale privo di calibrazione che mantiene la fedeltà, superando i metodi di proiezione a rango ridotto che richiedono calibrazione per livello.
• Il paper nota che i codici vettoriali completi ($k=d$) performano meglio a compressione estrema rispetto ai codici a metà vettore ($k=d/2$) perché spendono tutti i bit sull'impaccamento angolare, che correla direttamente con i prodotti interni dell'attenzione.

4.3 Prestazioni End-to-End del Modello Linguistico (TinyLlama-1.1B)

Valutato sulla perplessità WikiText-103 e sull'accuratezza HellaSwag:

• A $b=4$ (4× compressione): FibQuant è entro 0.10 di perplessità dalla baseline fp16 e supera TURBOQUANT scalare.
• A $b=2$ (8× compressione): FibQuant raggiunge una perplessità di 15.88, superando significativamente TURBOQUANT scalare (56.72) e la quantizzazione INT per token (che collassa a 4450.5).
• Tassi Frazionari: FibQuant fornisce punti operativi intermedi (es. $b=2.5, 3.5$) non disponibili ai codec scalari, permettendo di scegliere prima il budget della cache e sintonizzare il codec per adattarvisi.

5. Significato e Affermazioni

Il paper afferma che il vincolo di accesso casuale, spesso visto come una limitazione ingegneristica, ha una profonda conseguenza matematica: costringe i dati in una specifica geometria sferico-Beta. Riconoscendo questa sorgente canonica, FibQuant recupera i "guadagni di modellazione e adattamento alla densità" che la quantizzazione scalare lascia sul tavolo.

Il significato risiede in:

1. Universalità: Un singolo codice funziona su tutte le configurazioni del modello senza calibrazione.
2. Operazione Sub-Un-Bit: Abilita una compressione ad alta fedeltà in regimi in cui i metodi scalari falliscono, espandendo efficacemente il budget di memoria utilizzabile per l'inferenza in contesti lunghi.
3. Compatibilità di Sistema: Mantiene l'interfaccia a indirizzo fisso e ad accesso casuale richiesta per fondere la decompressione con i kernel di attenzione, rendendolo immediatamente deployabile nei framework di servizio esistenti.

Gli autori concludono che l'accesso casuale non preclude una buona codifica della sorgente; piuttosto, detta esattamente quale sorgente deve essere codificata.