2025-11-13T04:07:09.837900

Optimal Quantization for Matrix Multiplication

Ordentlich, Polyanskiy
Recent work in machine learning community proposed multiple methods for performing lossy compression (quantization) of large matrices. This quantization is important for accelerating matrix multiplication (main component of large language models), which is often bottlenecked by the speed of loading these matrices from memory. Unlike classical vector quantization and rate-distortion theory, the goal of these new compression algorithms is to be able to approximate not the matrices themselves, but their matrix product. Specifically, given a pair of real matrices $A,B$ an encoder (compressor) is applied to each of them independently producing descriptions with $R$ bits per entry. These representations subsequently are used by the decoder to estimate matrix product $A^\top B$. In this work, we provide a non-asymptotic lower bound on the mean squared error of this approximation (as a function of rate $R$) for the case of matrices $A,B$ with iid Gaussian entries. Algorithmically, we construct a universal quantizer based on nested lattices with an explicit guarantee of approximation error for any (non-random) pair of matrices $A$, $B$ in terms of only Frobenius norms $\|\bar{A}\|_F, \|\bar{B}\|_F$ and $\|\bar{A}^\top \bar{B}\|_F$, where $\bar{A},\bar{B}$ are versions of $A,B$ with zero-centered columns, respectively. For iid Gaussian matrices our quantizer achieves the lower bound and is, thus, asymptotically optimal. A practical low-complexity version of our quantizer achieves performance quite close to optimal. In addition, we derive rate-distortion function for matrix multiplication of iid Gaussian matrices, which exhibits an interesting phase-transition at $R\approx 0.906$ bit/entry, showing necessity of Johnson-Lindestrauss dimensionality reduction (sketching) in the low-rate regime.
academic

Quantification Optimale pour la Multiplication Matricielle

Informations Fondamentales

  • ID de l'article: 2410.13780
  • Titre: Optimal Quantization for Matrix Multiplication
  • Auteurs: Or Ordentlich (Hebrew University of Jerusalem), Yury Polyanskiy (MIT)
  • Classification: cs.IT cs.AI cs.CL cs.LG math.IT
  • Date de publication: Octobre 2024 (prépublication arXiv)
  • Lien de l'article: https://arxiv.org/abs/2410.13780

Résumé

Cet article approfondit la question de la quantification pour la multiplication matricielle à grande échelle. Contrairement à la quantification vectorielle traditionnelle, l'objectif n'est pas d'approximer les matrices elles-mêmes, mais d'approximer leur produit matriciel. Étant donné deux matrices réelles A et B, l'encodeur compresse indépendamment chaque matrice, chaque entrée étant décrite avec R bits, puis le décodeur utilise ces représentations compressées pour estimer le produit matriciel A⊤B. L'article fournit des bornes inférieures non-asymptotiques approximatives de l'erreur quadratique moyenne pour le cas de matrices avec entrées gaussiennes indépendantes et identiquement distribuées, construit un quantificateur universel basé sur des réseaux imbriqués, et découvre un phénomène de transition de phase intéressant à R ≈ 0,906 bits/entrée, indiquant que la réduction de dimensionnalité de Johnson-Lindenstrauss est nécessaire dans le régime de faible débit.

Contexte et Motivation de la Recherche

Définition du Problème

Avec l'émergence des réseaux de neurones profonds et des grands modèles de langage, la multiplication matricielle devient le principal goulot d'étranglement du calcul. Le matériel informatique moderne est souvent limité par la bande passante mémoire plutôt que par la capacité de calcul. Par conséquent, la compression avec perte des matrices pour réduire les transferts mémoire devient une question importante.

Besoins Pratiques

Pour les grands modèles de langage, les auteurs ont estimé les débits de quantification requis:

  • Pendant la phase de génération, le CPU nécessite un débit de quantification de 1-3 bits/entrée pour utiliser pleinement les ressources de calcul
  • Pendant la phase de pré-remplissage, pour les petits LLM exécutés sur des GPU rapides, un débit de quantification d'environ 11,7 bits/entrée est nécessaire

Limitations des Méthodes Existantes

  1. Quantification vectorielle classique: La quantification indépendante directe des matrices A et B, suivie du calcul du produit des matrices quantifiées, entraîne une erreur O(n²)
  2. Méthodes de croquis: Bien qu'elles fournissent des estimations sans biais, la variance reste O(n²)
  3. Quantificateurs déterministes: Il existe une borne inférieure Ω(n²) pour les vecteurs sur la sphère

Contributions Principales

  1. Bornes théoriques inférieures: Fournit des bornes inférieures non-asymptotiques pour la quantification de la multiplication matricielle avec entrées gaussiennes iid
  2. Quantificateur universel: Construit un quantificateur universel basé sur des réseaux imbriqués avec des garanties d'erreur explicites pour toute matrice
  3. Optimalité asymptotique: Prouve que le quantificateur proposé atteint la borne inférieure pour les matrices gaussiennes iid, et est donc asymptotiquement optimal
  4. Phénomène de transition de phase: Découvre une transition de phase à R ≈ 0,906 bits/entrée, révélant la nécessité de la réduction de dimensionnalité à faible débit
  5. Algorithme pratique: Fournit une implémentation de faible complexité avec des performances proches de l'optimalité

Détails de la Méthode

Définition de la Tâche

Étant donné les matrices A ∈ ℝ^(n×a) et B ∈ ℝ^(n×b), l'objectif est de concevoir les encodeurs f₁: ℝ^(n×a) → 2^(naR) et f₂: ℝ^(n×b) → 2^(nbR) ainsi que le décodeur g, de sorte que:

E∥A⊤B−g(f1(A),f2(B))∥F2E\|A^⊤B - g(f_1(A), f_2(B))\|_F^2

soit minimisé, où chaque entrée de matrice est décrite avec R bits.

Fonction Centrale Γ(R)

L'article définit la fonction débit-distorsion clé:

Γ(R)={1−(1−(2⋅2−2R∗−2−4R∗))RR∗R<R∗2⋅2−2R−2−4RR≥R∗\Gamma(R) = \begin{cases} 1 - \left(1 - (2 \cdot 2^{-2R^*} - 2^{-4R^*})\right) \frac{R}{R^*} & R < R^* \\ 2 \cdot 2^{-2R} - 2^{-4R} & R \geq R^* \end{cases}

où R* ≈ 0,906 est la solution de l'équation de point fixe R = ½log₂(1 + 4R ln 2).

Schéma de Quantification par Réseaux Imbriqués

1. Quantification du Produit Scalaire (Bloc de Construction Fondamental)

Pour les vecteurs U et V corrélés avec ρ sur la sphère, utilisant les réseaux imbriqués Λc ⊂ Λf:

Processus d'encodage:

  • Ajouter indépendamment les vecteurs de bruit Z₁ et Z₂ à U et V
  • Quantifier au réseau fin Λf
  • Produire la représentation de classe résiduelle dans le réseau grossier Λc

Processus de décodage:

  • Récupérer le point quantifié à partir de la classe résiduelle
  • Supprimer le bruit
  • Calculer l'estimation du produit scalaire

2. Quantification de la Multiplication Matricielle

Étapes de prétraitement:

  1. Centrage à zéro: Calculer Ā = A - (1/n)1·1^⊤A, B̄ = B - (1/n)1·1^⊤B
  2. Quantification de norme: Description haute précision de la moyenne et de la norme de chaque colonne
  3. Rotation aléatoire: Appliquer la même matrice orthogonale S à Ā et B̄

Étapes de quantification:

  • Appliquer le quantificateur de produit scalaire à chaque colonne tournée
  • Utiliser le partage temporel des paramètres κ et le paramètre de mise à l'échelle MMSE α

Points d'Innovation Technique

  1. Technique de bruit: Rend l'erreur de quantification indépendante de l'entrée, évitant l'erreur O(n²) des quantificateurs déterministes
  2. Structure de réseaux imbriqués: Fournit des performances de quantification satisfaisantes tout en maintenant un débit fini
  3. Partage temporel: Réalise l'optimalité à faible débit par réduction de dimensionnalité
  4. Rotation aléatoire: Convertit les vecteurs arbitraires en distribution uniforme sur la sphère, facilitant l'analyse

Configuration Expérimentale

Expériences de Vérification Théorique

Génération de données:

  • Matrices A, B ∈ ℝ^(n×n), entrées iid N(0,1)
  • n = 3 × 2¹¹

Détails d'implémentation:

  • Réseau de base: réseau D₃ (3 dimensions)
  • Ratio d'imbrication: q = 6
  • Taille de la table de consultation: < 64 KB (peut tenir dans le cache L1)
  • Débit effectif: ≈ 3,015 bits/symbole

Méthodes de Comparaison

  • Quantificateur scalaire 3 bits (normalisation ℓ∞)
  • Borne théorique inférieure Γ(R)

Résultats Expérimentaux

Résultats Principaux

Comparaison de performance:

  • Méthode proposée: 1/n³ ∥Â⊤B - A⊤B∥²F ≈ 0,0593
  • Quantification scalaire 3 bits: ≈ 0,1668 (écart d'environ 3 fois)
  • Borne théorique inférieure: Γ(3,015) = 0,0304

Découvertes clés:

  1. Le schéma basé sur le réseau D₃ surpasse significativement la quantification scalaire
  2. Les performances sont proches de l'optimum théorique (écart d'environ 2 fois)
  3. L'écart de performance diminuera davantage avec la croissance de n

Analyse de Complexité

Complexité d'encodage: O(n log n) (utilisant la transformée de Hadamard rapide) Complexité de décodage: O(1) (utilisant une table de consultation) Surcharge de stockage: Chaque quantificateur nécessite O(log n) bits supplémentaires pour décrire les facteurs d'échelle

Travaux Connexes

Algèbre Linéaire Aléatoire

  • Multiplication Matricielle Monte Carlo (MCMM): Échantillonnage aléatoire de lignes pour approximation
  • Hachage Sensible à la Localité (LSH): Pour croquis de faible dimension de similarité cosinus
  • Limitations: L'erreur relative croît avec ∥A∥²F∥B∥²F/∥A⊤B∥²F

Quantification de Réseaux de Neurones

  • Quantification post-entraînement: Méthodes OPTQ, GPTQ, etc.
  • Techniques de rotation: QuIP, QuaRot utilisant la transformée de Hadamard
  • Quantification par réseaux: QUIP# utilisant le réseau E₈ pour la quantification de poids

Théorie de l'Information

  • Compression distribuée: Compression pour le calcul de fonctions linéaires
  • Conception de codebooks: Codes de Voronoi et codes de réseaux imbriqués

Conclusion et Discussion

Conclusions Principales

  1. Optimalité: Pour les matrices gaussiennes iid, le schéma proposé atteint la borne théorique de l'information
  2. Universalité: Fournit des garanties de performance explicites pour toute matrice
  3. Phénomène de transition de phase: R* ≈ 0,906 bits/entrée est un seuil critique
  4. Praticité: L'implémentation de faible complexité approche les performances théoriques

Limitations

  1. Aléatoire partagée: Nécessite que l'encodeur et le décodeur partagent une graine aléatoire
  2. Conditions sur les matrices: Nécessite que les entrées de matrice soient bornées (M = n^(10^22000))
  3. Réseaux de haute dimension: L'optimalité théorique nécessite des réseaux "bons" de haute dimension, tandis que la pratique utilise des produits de réseaux de faible dimension
  4. Schémas déterministes: Il n'est pas clair s'il existe des schémas déterministes optimaux sans nécessiter d'aléatoire

Directions Futures

  1. Produits de multiples matrices: Extension à k > 2 matrices
  2. Autres mesures de distance: Mesures non-MSE comme la divergence KL
  3. Quantificateurs déterministes: Exploration de schémas sans aléatoire partagée
  4. Applications aux réseaux profonds: Déploiement et optimisation dans les LLM réels

Évaluation Approfondie

Points Forts

  1. Rigueur théorique: Fournit une analyse informationnelle complète, incluant les bornes supérieures et inférieures
  2. Valeur pratique: Résout le goulot d'étranglement réel dans l'inférence des LLM
  3. Innovation technique: Combine astucieusement la quantification par réseaux, la rotation aléatoire et le partage temporel
  4. Universalité: Ne dépend pas d'hypothèses de distribution matricielle spécifiques

Insuffisances

  1. Complexité: L'analyse théorique est plutôt complexe, l'implémentation réelle nécessitant plusieurs composants techniques
  2. Facteurs constants: Bien qu'asymptotiquement optimal, les constantes pour les échantillons finis peuvent être importantes
  3. Adaptation matérielle: Nécessite l'optimisation de l'implémentation pour différentes plates-formes matérielles
  4. Extensibilité: L'extension de 2 matrices à plusieurs matrices n'est pas triviale

Impact

Contributions théoriques:

  • Établit les fondations informationnelles de la quantification de multiplication matricielle
  • Révèle le phénomène de transition de phase et la nécessité de la réduction de dimensionnalité
  • Fournit un repère théorique important pour le domaine

Applications pratiques:

  • Fournit une nouvelle orientation théorique pour la quantification des LLM
  • Les travaux ultérieurs NestQuant ont atteint des performances SOTA sur les LLM réels
  • Fournit des bases théoriques pour la conception d'accélérateurs matériels

Scénarios d'Application

  1. Inférence de grands modèles de langage: Quantification conjointe des poids et activations
  2. Informatique en périphérie: Opérations matricielles dans les environnements à mémoire limitée
  3. Calcul distribué: Multiplication matricielle avec communication limitée
  4. Calcul scientifique: Problèmes d'algèbre linéaire numérique à grande échelle

Références

L'article cite 44 références connexes, couvrant plusieurs domaines incluant la théorie de l'information, la théorie des réseaux, l'algèbre linéaire aléatoire et la quantification de réseaux de neurones. Les travaux particulièrement dignes d'attention incluent:

  • La monographie sur le codage par réseaux de Zamir fournissant les fondations théoriques
  • Les travaux fondateurs d'Erez et Zamir sur les réseaux imbriqués
  • Les méthodes récentes de quantification des LLM comme OPTQ, QuIP, etc.
  • Les résultats de la théorie des matrices aléatoires et de la géométrie sphérique

Évaluation globale: Ceci est un excellent article avec des contributions importantes tant sur le plan théorique que pratique, fournissant des fondations informationnelles solides au problème de quantification de multiplication matricielle et démontrant des algorithmes pratiques proches de l'optimalité. Ce travail est d'une importance significative pour la compréhension et l'amélioration des techniques de quantification dans les systèmes d'apprentissage automatique à grande échelle.