High-Rate Quantized Matrix Multiplication II

Riepilogo Tecnico: Moltiplicazione di Matrici Quantizzate ad Alto Tasso II

Enunciato del Problema
Questo articolo indaga i limiti teorici e pratici della quantizzazione solo dei pesi per i Modelli Linguistici di Grande Dimensione (LLM). Il setting specifico assume che la matrice di attivazione $X$ sia disponibile in precisione completa durante l'inferenza, mentre la matrice dei pesi $W$ deve essere quantizzata in una rappresentazione a bassa risoluzione $\hat{W}$ per ridurre la larghezza di banda della memoria e i requisiti di archiviazione. L'obiettivo è minimizzare la distorsione attesa dell'errore quadratico medio pesato (WMSE):
$$D = \frac{1}{n} \mathbb{E} \| X^\top (W - \hat{W}) \|_F^2 = \frac{1}{n} \text{tr}((W - \hat{W})^\top \Sigma_X (W - \hat{W}))$$
dove $\Sigma_X = \mathbb{E}[XX^\top]$ è la matrice di covarianza delle attivazioni, che si assume nota (tramite calibrazione), ma il decoder (motore di inferenza) non ha accesso a $\Sigma_X$ o alla sua base, bensì solo ai bit quantizzati.

Metodologia e Quadro Teorico
Gli autori affrontano il problema attraverso due prospettive: limiti teorico-informatici e progettazione algoritmica pratica.

1. Limiti Teorico-Informatici (Regime ad Alto Tasso):

   • Codifica Isotropa vs Anisotropa: L'articolo contrappone la quantizzazione "isotropa" (che utilizza un codice standard ignaro di $\Sigma_X$) alla quantizzazione "anisotropa" (che si adatta a $\Sigma_X$).
   • Soluzione Waterfilling: Attingendo alla teoria classica della codifica di sorgente, gli autori derivano che la distorsione ottimale $D^*$ nel regime ad alto tasso è ottenuta da una strategia di reverse waterfilling. Questa alloca i tassi di quantizzazione in modo disuguale tra le coordinate in base agli autovalori di $\Sigma_X$, risultando in una distorsione proporzionale alla media geometrica degli autovalori: $D^* \propto |\Sigma_X|^{1/n} 2^{-2R}$.
   • Il Divario: La codifica isotropa standard produce una distorsione proporzionale alla media aritmetica degli autovalori. Il divario tra le soluzioni ottimale e isotropa è governato dalla disuguaglianza tra Media Aritmetica e Media Geometrica (AM-GM).
   • Decoder Ignaro: Crucialmente, l'articolo dimostra che anche se il decoder è ignaro di $\Sigma_X$ (non può applicare la base SVD), un encoder adattivo che utilizza un codicebook isotropo può asintoticamente raggiungere il limite di distorsione waterfilling nel regime ad alto tasso, a condizione che l'arrotondamento verso il codicebook sia ottimale.

2. Algoritmi Pratici (Cancellazione Successiva delle Interferenze):

   • L'articolo analizza l'algoritmo GPTQ (e l'equivalente LDLQ), che utilizza un tasso fisso per voce e un approccio di cancellazione successiva delle interferenze (SIC) (algoritmo di Babai) basato sulla decomposizione di Cholesky $\Sigma_X = U^\top U$.
   • Limite Teorico di GPTQ: Gli autori mostrano che il GPTQ standard (con spaziatura uguale) raggiunge una distorsione proporzionale alla media aritmetica dei quadrati degli elementi diagonali di $U$ ($U_{i,i}^2$). Questa prestazione è sensibile alla base di $\Sigma_X$; in particolare, performa peggio nella base PCA (dove $U$ è diagonale) e meglio in basi casuali.
   • Algoritmo WaterSIC: Motivati dalla teoria waterfilling, gli autori propongono WaterSIC. Questo algoritmo regola la dimensione del passo di quantizzazione (spaziatura) per ogni coordinata in base agli elementi diagonali del fattore di Cholesky $U$. Nello specifico, alloca più bit alle coordinate con valori $U_{i,i}$ più grandi.
   • Prestazioni: WaterSIC raggiunge una distorsione proporzionale alla media geometrica di $U_{i,i}^2$. Poiché il prodotto di $U_{i,i}$ è uguale a $\sqrt{|\Sigma_X|}$, WaterSIC ottiene una distorsione entro un fattore moltiplicativo di $\frac{2\pi e}{12}$ (circa 1.423, o 0.25 bit/voce) dal limite inferiore teorico-informatico.

Risultati Chiave

• Quasi-Otimalità di WaterSIC: L'algoritmo WaterSIC risulta essere "indipendente dalla base" (la sua prestazione dipende solo dal determinante di $\Sigma_X$, rendendolo immune a rotazioni casuali dello spazio di input) e si trova entro 0.25 bit/voce dall'ottimo teorico nel regime ad alto tasso.
• Prestazioni di GPTQ: Sebbene il GPTQ standard sia subottimale in basi specifiche, gli autori rilevano che per i layer di Llama-3-8B, il GPTQ con una rotazione casuale dei pesi performa sorprendentemente bene, spesso entro 0.1 bit da WaterSIC. Ciò suggerisce che la base standard utilizzata negli LLM (probabilmente influenzata dalla dinamica dell'ottimizzatore Adam) non è lo scenario peggiore per GPTQ, e che la rotazione casuale può mitigare la sensibilità alla base.
• Validazione Empirica: Esperimenti su layer di Llama-3-8B utilizzando dati di calibrazione Wikitext-2 confermano che WaterSIC con codifica entropica traccia da vicino il limite teorico waterfilling, mentre il GPTQ standard mostra prestazioni variabili a seconda del layer e della base.

Significato e Affermazioni
L'articolo afferma di colmare il divario tra la teoria dell'informazione astratta e la quantizzazione pratica degli LLM:

1. Giustificazione Teorica: Fornisce una rigorosa giustificazione teorico-informatica del motivo per cui l'allocazione del tasso per coordinata (waterfilling) è superiore all'allocazione uniforme nella quantizzazione solo dei pesi.
2. Miglioramento Algoritmico: Introduce WaterSIC come un algoritmo pratico a bassa complessità che realizza questi guadagni teorici, offrendo una via dimostrabile verso una distorsione quasi ottimale.
3. Insight sui Metodi Esistenti: Chiarisce il comportamento di GPTQ, spiegando la sua sensibilità alla base di $\Sigma_X$ e dimostrando che le rotazioni casuali possono renderlo quasi ottimale, validando così il suo uso diffuso mentre si evidenzia il potenziale per ulteriori guadagni tramite WaterSIC.
4. Limitazioni e Lavori Futuri: Gli autori notano modestamente che le loro approssimazioni ad alto tasso assumono alta risoluzione. Identificano che a bassi tassi (es. < 2 bit), altri fattori come la riduzione della dimensionalità e strutture specifiche dei pesi diventano critici. Inoltre, evidenziano che, sebbene la codifica entropica (EC) sia teoricamente ottimale, il suo costo computazionale sulle GPU può essere proibitivo, e metodi di shaping efficienti per le GPU rimangono una sfida aperta. Notano anche che il divario di 0.25 bit di WaterSIC deriva dalla sub-ottimalità del reticolo intero $\mathbb{Z}^n$, che potrebbe essere ridotto utilizzando reticoli di dimensione superiore, sebbene ciò complichi la codifica entropica.