🤖 machine learning

GPTQ-2D: Cubic-Time Two-Sided Adaptive Rounding

Cet article présente GPTQ-2D, un algorithme de complexité cubique qui effectue efficacement l'arrondi adaptatif bilatéral sur des matrices en traitant les entrées en parallèle le long des anti-diagonales, réduisant ainsi la complexité computationnelle de l'ordre quartique requise par les méthodes de vectorisation standard tout en produisant des résultats identiques.

Auteurs originaux : Jiale Chen, Torsten Hoefler, Dan Alistarh

Publié 2026-07-30

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Jiale Chen, Torsten Hoefler, Dan Alistarh

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayiez de ranger une tour de blocs Jenga massive et vacillante dans une boîte nette et rigide. Dans le monde de l'intelligence artificielle, ces « blocs » sont des nombres à l'intérieur d'un immense tableur (une matrice) qui enseigne à un ordinateur comment réfléchir. Pour que ces ordinateurs fonctionnent plus rapidement et utilisent moins d'énergie, les ingénieurs tentent de réduire la taille de ces nombres en les transformant en simples nombres entiers (des entiers), un processus appelé « quantification ». Mais voici le piège : si vous coupez simplement les décimales de manière aléatoire, la tour s'effondre et l'ordinateur commence à faire des erreurs stupides.

Pour corriger cela, les scientifiques utilisent une astuce ingénieuse appelée « arrondi adaptatif ». Voyez cela comme un jeu de dominos. Quand vous renversez un domino (arrondissez un nombre), cela crée un léger vacillement. Au lieu d'ignorer ce vacillement, l'arrondi adaptatif le attrape et le pousse vers le domino suivant dans la file, en l'ajustant légèrement pour que toute la ligne reste droite. Cette méthode, connue sous le nom de GPTQ, a été une star pendant des années, mais elle ne fonctionne bien que lorsque les dominos sont disposés en une seule longue ligne. Cependant, les modèles d'IA modernes ressemblent davantage à une gigantesque grille bidimensionnelle de dominos, où renverser un domino affecte ses voisins à la fois à sa droite et en dessous de lui. Essayer de réparer cette grille 2D avec l'ancienne méthode de la « ligne unique », c'est comme essayer de démêler un nœud en tirant sur un seul bout : cela fonctionne, mais cela prend un temps infini et finit par tourner en boucle quatre fois plus lentement que nécessaire.

Ce document présente une nouvelle façon de démêler ce nœud, appelée GPTQ-2D. Les auteurs, Jiale Chen, Torsten Hoefler et Dan Alistarh, ont découvert qu'il n'est pas nécessaire de tirer sur les dominos un par un dans une longue ligne. Au lieu de cela, vous pouvez saisir des rangées diagonales entières de dominos et les réparer tous en même temps. En réalisant que le « vacillement » d'un bloc ne voyage que vers le bas et vers la droite, ils ont trouvé un raccourci qui leur permet de traiter toute la grille en une fraction du temps. Ils ont prouvé mathématiquement que cette nouvelle méthode produit exactement la même tour parfaite que l'ancienne méthode lente, mais qu'elle le fait en un temps « cubique » (ce qui est rapide) plutôt qu'en un temps « quartique » (ce qui est douloureusement lent). Cela signifie que nous pouvons désormais rétrécir ces cerveaux d'IA géants beaucoup plus efficacement sans les briser, rendant l'IA puissante plus accessible sur les appareils du quotidien.

L'histoire du puzzle à deux côtés

Plongeons dans la mécanique de ce puzzle. Dans l'ancienne méthode à un seul côté (GPTQ), imaginez une file de personnes se passant un sac à dos lourd. Si la première personne fait tomber une pièce, elle dit à la suivante de porter un peu plus de poids pour compenser. Cela se produit une personne à la fois, en descendant la file. Cela fonctionne très bien pour une file indienne.

Mais dans le monde réel de l'IA, les « personnes » sont disposées en une grille, comme un damier. Maintenant, si une personne au milieu fait tomber une pièce, ce poids doit être partagé avec tous ceux qui se trouvent en dessous d'elle et à sa droite. Si vous essayez de réparer cette grille en parcourant chaque case une par une (l'approche « vectorisée »), vous finissez par faire un travail redondant massif. C'est comme essayer de nettoyer toute une pièce en essuyant chaque centimètre carré du sol, même les parties que vous avez déjà nettoyées, encore et encore. Les mathématiques montrent que cela prend énormément de temps, la charge de travail augmentant si vite que si vous doublez la taille de la grille, le travail est quadruplé (ou plus).

Les auteurs de ce document ont regardé cette grille et ont réalisé quelque chose de magique : le « vacillement » ou l'erreur de n'importe quelle case ne voyage que dans une direction spécifique : vers le bas et vers la droite. Cela crée un graphe de dépendance qui ressemble à un escalier. Si vous regardez la grille diagonalement (du haut à droite vers le bas à gauche), vous verrez que toutes les cases sur une même ligne diagonale sont indépendantes les unes des autres. Elles ne s'affectent pas entre elles !

C'est le moment de l'« Aha ! ». Parce qu'elles sont indépendantes, vous pouvez arrondir tous les nombres sur une seule ligne diagonale en même temps, comme une vague déferlant sur le plateau. C'est le cœur de GPTQ-2D.

La magie du tampon « paresseux »

Alors, comment rendent-ils cela rapide ? Dans l'ancienne méthode « lente », chaque fois que vous répariez un nombre, vous alliez immédiatement mettre à jour chaque case dans le grand rectangle situé en dessous et à la droite de celui-ci. C'est beaucoup de travail inutile.

Le nouvel algorithme GPTQ-2D est beaucoup plus paresseux (dans le bon sens du terme). Au lieu de mettre à jour tout le rectangle immédiatement, il pousse simplement l'erreur le long de sa propre colonne et de sa propre ligne, en laissant une « note » dans un tampon (buffer). C'est comme un professeur qui, au lieu de se rendre au bureau de chaque élève pour corriger une erreur, se contenterait d'écrire la correction sur le bureau de l'élève et sur le bureau de l'élève à sa droite. Les élèves plus loin dans la file verront finalement ces notes et se corrigeront eux-mêmes.

En utilisant cette approche « paresseuse », l'algorithme évite le travail colossal de mise à jour constante de toute la grille. Il traite la grille par « vagues » (les anti-diagonales). Chaque vague prend un peu de temps, et comme les vagues peuvent se produire en parallèle, l'ensemble du processus s'accélère de façon spectaculaire.

Le document prouve que cet abord diagonal et paresseux produit exactement le même résultat que la méthode lente, une par une. Ce n'est pas une approximation ; c'est une garantie mathématique. Les auteurs montrent que que vous répariez les dominos un par un ou par vagues diagonales, la tour finale se tient exactement de la même manière.

Pourquoi cela importe

Le document ne se contente pas de supposer que c'est plus rapide ; ils ont fait les calculs pour le prouver. Pour une grille carrée (où le nombre de lignes est égal au nombre de colonnes), l'ancienne méthode prend un temps proportionnel à la taille de la grille à la puissance quatre ( $O(m^2n^2)$ ). La nouvelle méthode GPTQ-2D prend un temps proportionnel à la taille à la puissance trois ( $O(m^3)$ ).

Pour donner une perspective : si vous avez une grille de 1 000 par 1 000, l'ancienne méthode fait un milliard de fois plus de travail que nécessaire par rapport à la nouvelle méthode. La nouvelle méthode ramène le coût de la réparation d'une grille à deux côtés au même niveau que la réparation d'une simple ligne à un côté.

Les auteurs décrivent également une version « par blocs » de cet algorithme (Algorithme 4), qui regroupe ces vagues diagonales en blocs. Cela est conçu pour fonctionner encore mieux sur les puces informatiques modernes, qui adorent traiter de gros blocs de mathématiques d'un coup plutôt que des petits morceaux éparpillés. Cela rend la théorie prête pour une utilisation dans le monde réel.

En bref, ce document prend un problème qui était trop lent pour être pratique pour les grands modèles d'IA complexes et lui donne un coup de boost qui le rend réalisable. Il montre qu'en changeant l'ordre dans lequel nous regardons les données — en remplaçant une ligne droite par une vague diagonale — nous pouvons résoudre un puzzle à deux côtés aussi facilement qu'un puzzle à un seul côté, sans perdre aucune précision. C'est un rappel que parfois, la façon la plus rapide de résoudre un problème n'est pas de travailler plus dur, mais de regarder le problème sous un autre angle.

Résumé technique de « GPTQ-2D : Arrondi adaptatif bilatéral en temps cubique »

1. Énoncé du problème

Le papier traite du problème de l'arrondi adaptatif bilatéral (two-sided adaptive rounding), une généralisation de l'arrondi matriciel unilatéral standard utilisé dans les méthodes de quantification comme GPTQ (Frantar et al., 2023) et l'algorithme des plans les plus proches de Babai (Babai, 1986).

Cas unilatéral : Étant donné une matrice réelle $X \in \mathbb{R}^{m \times n}$ et une matrice de base non singulière fixe $A \in \mathbb{R}^{m \times m}$ , l'objectif est de trouver une matrice entière $Z$ minimisant $\|A(Z - X)\|_F^2$ . Cela est résolu de manière gloutonne en traitant les entrées selon un ordre fixe (par exemple, par colonnes), en propageant les erreurs d'arrondi via une matrice de rétroaction triangulaire. Cette approche s'exécute en $O(m^2 \max(m, n))$ temps (cubique pour les matrices carrées).
Cas bilatéral : Le papier introduit une seconde matrice de base non singulière fixe $B \in \mathbb{R}^{n \times n}$ agissant à droite, modifiant l'objectif en :
$\|A(Z - X)B\|_F^2 = \|(B^\top \otimes A)(\text{vec}(Z) - \text{vec}(X))\|_2^2$
Ici, $\otimes$ désigne le produit de Kronecker. Bien que cela puisse être résolu en vectorisant la matrice en un vecteur de longueur $mn$ et en appliquant un arrondi adaptatif 1D standard, la matrice de Gram résultante est $H \otimes G$ (où $H=BB^\top, G=A^\top A$ ). Un balayage direct sur tous les $mn$ coordonnées incurre une complexité temporelle de $O(m^2 n^2)$ (quartique pour les matrices carrées), ce qui est prohibitivement coûteux pour de grandes matrices.

Le défi central est de parvenir au même trajet d'arrondi que l'approche de vectorisation 1D, mais avec une complexité de calcul réduite, idéalement égale au coût cubique du cas unilatéral.

2. Méthodologie

Les auteurs proposent GPTQ-2D, un algorithme qui exploite la structure spécifique du produit de Kronecker pour réduire la complexité de quartique à cubique.

Éclairages théoriques clés :

Structure de rétroaction de Kronecker : La matrice de rétroaction pour le problème vectorisé est $F = U^\top \otimes L$ , où $L$ et $U$ sont les facteurs triangulaires inférieurs et supérieurs unitaires dérivés des inverses des matrices de Gram.
Mises à jour de rang un : Une erreur d'arrondi à l'entrée $(i, j)$ génère une mise à jour de rétroaction de la forme $L_{:,i} E_{ij} U_{j,:}$ . Il s'agit d'une mise à jour de rang un supportée uniquement sur le rectangle inférieur droit $\{i, \dots, m\} \times \{j, \dots, n\}$ .
Indépendance des anti-diagonales : Parce que la mise à jour de $(i, j)$ n'affecte que les entrées $(p, q)$ où $p \ge i$ et $q \ge j$ , les entrées sur une même anti-diagonale ( $i+j = s$ ) sont mutuellement indépendantes. Elles peuvent être traitées en parallèle une fois que toutes les anti-diagonales précédentes sont terminées.

Approche algorithmique :

Balayage par anti-diagonales : Au lieu d'un balayage par colonnes ou par lignes, l'algorithme traite la matrice en $m+n-1$ étapes, correspondant aux anti-diagonales.
Propagation paresseuse (l'astuce du « Buffer ») :
- Une implémentation naïve du balayage par anti-diagonales nécessiterait toujours un travail de $O(m^2 n^2)$ car l'application de la mise à jour de rang un $L_{:,i} E_{ij} U_{j,:}$ touche de manière dense un grand bloc de la matrice.
- GPTQ-2D évite cela en maintenant un tampon auxiliaire $C = LE$.
- Lorsqu'une entrée $(i, j)$ est arrondie, l'erreur $E_{ij}$ est propagée uniquement le long de sa colonne spécifique (via $L$ ) et de sa ligne (via $U$ ) immédiatement.
- La mise à jour « massive » du rectangle est différée. L'algorithme pousse l'erreur vers le bas de la colonne dans le tampon $C$ , et plus tard, les valeurs du tampon sont poussées vers la droite le long des lignes.
- Cette stratégie de « poussée » garantit que chaque entrée est mise à jour exactement une fois par dépendance, réduisant le coût du balayage à $O(mn \max(m, n))$ .
Implémentation par blocs : Pour améliorer les performances pratiques sur le matériel parallèle, les auteurs introduisent une variante par blocs (Algorithme 4). Celle-ci traite $w$ anti-diagonales à la fois, accumulant les erreurs dans un bloc et les déversant vers le reste de la matrice en utilisant des produits de matrices de type bande, de manière similaire aux mises à jour de blocs paresseuses de GPTQ.

3. Contributions clés

Formulation : Le papier reformule l'arrondi matriciel bilatéral comme un arrondi vectoriel sous une métrique de Kronecker, prouvant que la rétroaction résultante est de rang un et séparable.
Réduction de la complexité : Il démontre que le problème bilatéral peut être résolu en $O((\max(m, n))^3)$ temps, égalant le coût asymptotique du GPTQ unilatéral, plutôt que le coût $O(m^2 n^2)$ d'un balayage vectorisé direct et dense.
Équivalence exacte : Le Théorème 2 prouve que GPTQ-2D produit la matrice arrondie identique à l'algorithme d'arrondi adaptatif 1D standard appliqué à l'entrée vectorisée, à condition d'utiliser une règle de départage (tie-breaking) déterministe.
Invariance de l'ordre : Le papier établit (Théorème 1) que l'arrondi adaptatif est invariant à l'ordre de traitement, à condition que l'ordre respecte les dépendances de rétroaction (c'est-à-dire un tri topologique du graphe de dépendance). Cela justifie le balayage parallèle par anti-diagonales.

4. Résultats et analyse de complexité

Complexité temporelle :
- Factorisation : Le calcul des décompositions LDL des inverses des matrices de Gram prend $O((\max(m, n))^3)$ .
- Balayage : Le balayage d'arrondi prend $O(mn \max(m, n))$ .
- Total : Pour les matrices carrées ( $m=n$ ), la complexité totale est de $O(m^3)$ , une amélioration significative par rapport au $O(m^4)$ de l'approche dense directe.
Parallélisme : L'algorithme supporte naturellement le parallélisme avec $m+n-1$ étapes. Au sein de chaque étape (anti-diagonale), toutes les entrées peuvent être traitées simultanément.
Mémoire : Le stockage de travail est de $O((\max(m, n))^2)$ pour les facteurs et de $O(mn)$ pour les tampons de balayage.

5. Signification et affirmations

Le papier positionne GPTQ-2D non pas comme un concurrent de GPTQ unilatéral, mais comme une extension nécessaire pour les scénarios nécessitant des métriques bilatérales (par exemple, les Hessiennes factorisées par Kronecker dans la quantification).

Extension de GPTQ : Les auteurs affirment que l'arrondi unilatéral est le cas particulier où $B=I$ . GPTQ-2D étend cette capacité au cas bilatéral sans subir une augmentation du coût de calcul de l'ordre de $\Theta(\min(m, n))$ .
Utilité pratique : L'algorithme est conçu pour être un remplacement direct de l'étape d'arrondi dans les méthodes bilatérales existantes comme YAQA (Tseng et al., 2026). Bien que YAQA utilise également des balayages par anti-diagonales, son implémentation de référence utilise des produits de matrices denses, ce qui entraîne une complexité quartique. GPTQ-2D fournit le même trajet d'arrondi avec une complexité cubique, rendant l'opération réalisable pour des applications à grande échelle.
Portée modeste : Le papier évite explicitement toute prétention d'optimalité globale (notant que trouver le point de réseau exact est NP-difficile) et se concentre strictement sur l'efficacité du trajet d'arrondi glouteux et adaptatif défini par la métrique. Il ne propose pas de nouvelles applications mais optimise le coût de calcul des formulations d'arrondi bilatéral existantes.