High-Rate Quantized Matrix Multiplication I

Technische Samenvatting: Gekwantiseerde Matrixvermenigvuldiging met Hoge Snelheid I

Probleemstelling
Dit artikel behandelt het probleem van gekwantiseerde matrixvermenigvuldiging (MatMul), een kritieke bewerking voor de efficiënte implementatie van Large Language Models (LLMs). De auteurs richten zich op een "Generic MatMul"-setting waarbij beide matrices (gewichten en activaties) gekwantiseerd moeten worden zonder specifieke a priori statistische kennis (kalibratie) van de factoren. De kernuitdaging is het karakteriseren van de fundamentele informatie-theoretische afweging tussen de kwantisatiesnelheid (bits per invoer, $R$) en de resulterende vervorming (fout) in het matrixproduct. Het artikel onderscheidt tussen de informatie-theoretische definitie van "snelheid" (waarbij een vector van $N$ invoeren globaal wordt gecodeerd in $NR$ bits) en de praktische definitie die in AI wordt gebruikt (waarbij elke invoer individueel of in kleine groepen wordt gekwantiseerd).

Methodologie en Theoretisch Kader
De analyse steunt op kwantisatietheorie met hoge snelheid, waarbij wordt aangenomen dat de kwantisatieruis aanzienlijk zwakker is dan het signaal ($R$ is voldoende groot). Onder deze aanname wordt de kwantisatiefout gemodelleerd als additieve, onafhankelijke en uniform verdeelde ruis. De auteurs negeren ook "lineaire krimp"-effecten, die van de orde $O(2^{-4R})$ zijn, om de vervormingsanalyse te vereenvoudigen.

Het artikel formaliseert het probleem met behulp van een kwantisatieschema met snelheid $R$ dat encoders en een decoder omvat, waarbij mogelijk gedeelde willekeur (publieke munten) wordt gebruikt. Het beoordeelt de prestaties in twee settings:

1. Worst-case: Matrices $A$ en $B$ hebben begrensde $\ell_2$-normen, maar geen verdelingsaannames.
2. Gemiddelde-case (Gaussisch): Invoeren van $A$ en $B$ zijn onafhankelijk en identiek verdeeld (i.i.d.) Gaussisch.

Belangrijkste Bijdragen en Resultaten

1. Fundamentele Grenzen voor Generic MatMul:
   Het artikel stelt vast dat voor generieke matrices de kleinste verwachte vervorming voor de $(i,j)$-de invoer van het product $A^\top B$ wordt gekarakteriseerd door:
   $$D^*_{ij} = \frac{\|a_i\|^2 \cdot \|b_j\|^2}{n} \cdot 2 \cdot 2^{-2R}$$
   waarbij $a_i$ en $b_j$ de kolommen van $A$ en $B$ zijn, en $n$ de dimensie is. Deze grens wordt getoond als strak voor Gaussische invoer. De auteurs demonstreren dat niet-gewillekeurde schema's of eenvoudige schetsbenaderingen over het algemeen lijden onder vervorming die lineair schaalt met de dimensie $n$ ($\Omega(n)$), terwijl schema's die willekeur (willekeurige rotatie/dither) combineren met roosterkwantisatie het fundamentele limiet kunnen bereiken.

2. Analyse van Populaire Kwantisatieschema's:
   De auteurs leiden accurate heuristische benaderingen af voor de vervorming van veelgebruikte schema's, uitgedrukt in de vorm $K(i,j) \cdot 2 \cdot 2^{-2R_{\text{eff}}}$, waarbij $R_{\text{eff}}$ de "effectieve snelheid" in bits is.

   • INT-vermenigvuldigers (absmax): Voor standaard INT$M$ met absmax-schaling is de effectieve snelheid $R_{\text{eff}} \approx M - \frac{1}{2}\log_2(\frac{2 \ln n}{3})$. Dit duidt op een aanzienlijke snelheidsstraf vanwege de $\ell_\infty$-schalingsfactor. Het artikel toont aan dat het toepassen van een willekeurige rotatie (bijvoorbeeld een Hadamard-transformatie) vóór kwantisatie de vervormingsfactor $\Delta_{\text{INT}}$ reduceert tot concentratie rond $2 \ln n$, waardoor rotatie cruciaal is voor INT-kwantisatie.
   • Floating-Point (FP)-vermenigvuldigers: Met behulp van een "Infinite-Exponent Independent Noise" (IEIN)-model leiden de auteurs af dat voor FP met $M$ mantisse-bits, $R_{\text{eff}} \approx M + 2.23$ bits. In tegenstelling tot INT suggereert de analyse dat voor FP-kwantisatie willekeurige rotatie vaak onnodig is en zelfs schadelijk kan zijn, aangezien de vervormingsfactor $\Delta_{\text{FP}}$ zonder rotatie voor bepaalde verdelingen de neiging heeft kleiner dan 1 te zijn.
   • Multi-geschaalde Formatte (NVFP4/NVINT4): Het artikel analyseert 4-bit formaten (NVFP4, NVINT4) die multi-schaling (groepsschaling) gebruiken. Het betoogt dat NVFP4 effectief gedraagt als een schema met 1 mantisse-bit met een effectieve snelheid van ongeveer 3,24 bits, terwijl NVINT4 lijdt onder dezelfde schalingsstraffen als standaard INT tenzij zorgvuldig beheerd.
   • NestQuant: De auteurs bespreken het NestQuant-raamwerk, dat geneste roostercodes (specifiek het $E_8$-rooster) en een bank van schalen gebruikt. Zij merken op dat NestQuant aanzienlijk beter presteert dan INT- en FP-schema's bij vergelijkbare bitsnelheden, met ongeveer 0,6 extra bits nauwkeurigheid.

3. Empirische Validatie:
   Met behulp van activatiematrices uit de 15e laag van Llama3-8B valideert het artikel de theoretische benaderingen.

   • De afgeleide formules voor INT- en FP-vervorming komen opmerkelijk goed overeen met empirische Root Mean Squared Error (RMSE)-metingen.
   • Histogrammen bevestigen dat willekeurige rotatie de variantie van de vervormingsfactor voor INT-kwantisatie drastisch reduceert, maar een ander, vaak negatief, effect heeft op FP-kwantisatie.
   • Vergelijkingen bij $R=4,5$ bits tonen aan dat NestQuant aanzienlijk beter presteert dan zowel NVINT4 als NVFP4.

Betekenis en Claims
Het artikel claimt de eerste informatie-theoretische benchmarks te bieden voor generieke gekwantiseerde MatMul waarbij geen kalibratiestatistieken beschikbaar zijn. De primaire betekenis ligt in het kwantificeren van de kloof tussen fundamentele grenzen en restrictieve praktische benaderingen (zoals standaard INT/FP-formaten).

De auteurs benadrukken dat hoewel aannames met hoge snelheid mogelijk niet gelden voor zeer lage bitsnelheden ($R < 2$), ze voldoende nauwkeurige uitdrukkingen bieden voor de snelheden die typisch worden gebruikt in LLM's (bijvoorbeeld 4 tot 8 bits). Het werk dient als theoretische basis om huidige kwantisatiestrategieën te evalueren, met de nadruk op:

• Willekeurige rotatie is een kritiek onderdeel voor INT-kwantisatie om de fundamentele grenzen te benaderen.
• FP-kwantisatie gedraagt zich anders, waarbij rotatie mogelijk niet voordelig is.
• Er is een aanzienlijke prestatiekloof tussen standaard schema's en de theoretische optimum, die kan worden verkleind door geavanceerde technieken zoals NestQuant.

Het artikel concludeert met de opmerking dat deel II van dit werk de setup voor alleen gewichten-kwantisatie zal behandelen, waarbij tweede-orde statistieken van activaties beschikbaar zijn.