🤖 machine learning

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

Dit artikel introduceert GPTQ-2D, een algoritme met een kubische complexiteit dat efficiënt tweezijdige adaptieve afronding op matrices uitvoert door de invoer parallel langs anti-diagonalen te verwerken, waardoor de computationele complexiteit wordt verminderd van de quartische tijd die vereist is door standaard vectorisatiemethoden, terwijl identieke resultaten worden geproduceerd.

Oorspronkelijke auteurs: Jiale Chen, Torsten Hoefler, Dan Alistarh

Gepubliceerd 2026-07-30

📖 7 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Jiale Chen, Torsten Hoefler, Dan Alistarh

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een enorme, wiebelige toren van Jenga-blokjes probeert in te pakken in een nette, stijve doos. In de wereld van kunstmatige intelligentie zijn deze "blokjes" getallen binnen een gigantische spreadsheet (een matrix) die een computer leren hoe hij moet denken. Om deze computers sneller te laten draaien en minder energie te laten verbruiken, proberen ingenieurs deze getallen terug te brengen naar eenvoudige gehele getallen (integers), een proces dat "kwantisatie" wordt genoemd. Maar hier is het addertje onder het gras: als je de decimalen willekeurig afkapt, stort de toren in en begint de computer stomme fouten te maken.

Om dit op te lossen, gebruiken wetenschappers een slimme truc genaamd "adaptieve afronding". Denk aan dit als een spelletje domino. Wanneer je één domino omgooit (een getal afrondt), veroorzaakt dat een kleine wiebel. In plaats van die wiebel te negeren, vangt adaptieve afronding deze op en duwt deze door naar de volgende domino in de rij, waarbij de hele lijn licht wordt aangepast zodat deze recht blijft. Deze methode, bekend als GPTQ, is al jaren een superster, maar het werkt alleen goed wanneer de domino's in een enkele, lange lijn zijn gerangschikt. Moderne AI-modellen zijn echter meer als een gigantisch, tweedimensionaal rooster van domino's, waarbij het omverwerpen van één domino invloed heeft op zijn buren zowel rechts als eronder. Proberen dit 2D-rooster te herstellen met de oude "één-lijn"-methode is als het ontwarren van een knoop door slechts aan één uiteinde te trekken—het werkt, maar het duurt eeuwig en raakt vast in een lus die vier keer zo traag is als nodig.

Dit paper introduceert een nieuwe manier om die knoop te ontwarren, genaamd GPTQ-2D. De auteurs, Jiale Chen, Torsten Hoefler en Dan Alistarh, ontdekten dat je niet de domino's één voor één in een lange lijn hoeft te trekken. In plaats daarvan kun je hele diagonale rijen domino's pakken en ze allemaal tegelijkertijd herstellen. Door te beseffen dat de "wiebel" van één blok alleen naar beneden en naar rechts reist, vonden ze een kortere route waarmee ze het hele rooster in een fractie van de tijd kunnen verwerken. Ze bewezen wiskundig dat deze nieuwe methode exact dezelfde perfecte toren produceert als de trage, oude manier, maar dat hij dit doet in "kubische" tijd (wat snel is) in plaats van "quartische" tijd (wat pijnlijk traag is). Dit betekent dat we deze gigantische AI-hersenen nu veel efficiënter kunnen verkleinen zonder ze te breken, waardoor krachtige AI toegankelijker wordt op alledaagse apparaten.

Het Verhaal van de Tweezijdige Puzzel

Laten we duiken in de mechanica van deze puzzel. In de oude eenzijdige methode (GPTQ), stel je je een rij mensen voor die een zware rugzak doorgeven. Als de eerste persoon een muntje laat vallen, vertelt hij de volgende persoon om een beetje extra gewicht te dragen om dit te compenseren. Dit gebeurt één persoon per keer, terwijl men de lijn afloopt. Het werkt geweldig voor een enkele rij.

Maar in de echte wereld van AI zijn de "mensen" gerangschikt in een rooster, zoals een schaakbord. Nu, als een persoon in het midden een muntje laat vallen, moet dat gewicht worden gedeeld met iedereen die onder hen staat en iedereen die rechts van hen staat. Als je dit rooster probeert te herstellen door elk vakje één voor één af te gaan (de "vectorized" aanpak), eindig je met een enorme hoeveelheid redundant werk. Het is alsof je een hele kamer probeert schoon te maken door elke vierkante centimeter van de vloer af te vegen, zelfs de delen die je al hebt schoongemaakt, keer op keer opnieuw. De wiskunde laat zien dat dit een enorme hoeveelheid tijd kost; als je de grootte van het rooster verdubbelt, neemt de hoeveelheid werk kwadratisch (of zelfs meer) toe.

De auteurs van dit paper keken naar dit rooster en realiseerden zich iets magisch: de "wiebel" of fout van een enkel vierkant reist slechts in een specifieke richting—naar beneden en naar rechts. Dit creëert een afhankelijkheidsgrafiek die lijkt op een trap. Als je het rooster diagonaal bekijkt (van rechtsboven naar linksonder), zul je zien dat alle vierkanten op dezelfde diagonale lijn onafhankelijk van elkaar zijn. Ze beïnvloeden elkaar niet!

Dit is het "Aha!"-moment. Omdat ze onafhankelijk zijn, kun je alle getallen op een enkele diagonale lijn tegelijkertijd afronden, als een golf die over het bord slaat. Dit is de kern van GPTQ-2D.

De Magie van de "Luie" Buffer

Dus, hoe maken ze dit snel? In de oude "trage" manier, telkens wanneer je een getal corrigeerde, zou je onmiddellijk elk vierkant in het enorme rechthoek onder en rechts van het getal bijwerken. Dat is een hoop zinloos werk.

Het nieuwe GPTQ-2D algoritme is veel luier (in een goede zin). In plaats van de hele rechthoek onmiddellijk bij te werken, duwt het de fout gewoon naar beneden in de eigen kolom en naar de zijkant in de eigen rij, waarbij het een "briefje" achterlaat in een buffer. Het is als een leraar die, in plaats van naar elk bureau van een leerling te lopen om een fout te corrigeren, gewoon de correctie op het bureau van de leerling en op het bureau van de leerling rechts daarvan schrijft. De leerlingen verderop in de rij zullen de aantekeningen uiteindelijk zien en zichzelf corrigeren.

Door deze "luie" aanpak te gebruiken, vermijdt het algoritme het zware werk van het constant bijwerken van het hele rooster. Het verwerkt het rooster in "golven" (de anti-diagonalen). Elke golf kost een klein beetje tijd, en omdat de golven parallel kunnen plaatsvinden, versnelt het hele proces drastisch.

Het paper bewijst dat deze luie, diagonale aanpak exact hetzelfde resultaat oplevert als de trage, één-voor-één methode. Het is geen benadering; het is een wiskundige garantie. De auteurs laten zien dat of je de domino's nu één voor één herstelt of in diagonale golven, de uiteindelijke toren er exact hetzelfde bij staat.

Waarom Dit Ertoe Doet

Het paper gokt niet alleen dat dit sneller is; ze hebben de wiskunde gedaan om het te bewijzen. Voor een vierkant rooster (waarbij het aantal rijen gelijk is aan het aantal kolommen), neemt de oude methode een tijd in beslag die evenredig is aan de grootte van het rooster tot de vierde macht ( $O(m^2n^2)$ ). De nieuwe GPTQ-2D methode neemt een tijd in beslag die evenredig is aan de grootte tot de derde macht ( $O(m^3)$ ).

Om dat in perspectief te plaatsen: als je een rooster hebt van 1.000 bij 1.000, doet de oude methode een miljard keer meer werk dan nodig is vergeleken met de nieuwe methode. De nieuwe methode brengt de kosten van het herstellen van een tweezijdig rooster omlaag naar hetzelfde niveau als het herstellen van een eenvoudige eenzijdige lijn.

De auteurs beschrijven ook een "geblokte" versie van dit algoritme (Algoritme 4), die deze diagonale golven groepeert in blokken. Dit is ontworpen om nog beter te werken op moderne computerchips, die houden van grote blokken wiskunde tegelijkertijd verwerken in plaats van kleine, verspreide stukjes. Dit maakt de theorie klaar voor echt gebruik.

Kortom, dit paper neemt een probleem dat te traag was om praktisch te zijn voor grote, complexe AI-modellen en geeft het een snelheidsslag die het haalbaar maakt. Het laat zien dat door de volgorde te veranderen waarop we naar de data kijken—een rechte lijn vervangen door een diagonale golf—we een tweezijdig puzzel even gemakkelijk kunnen oplossen als een eenzijdige, zonder aan nauwkeurigheid in te boeten. Het is een herinnering dat de snelste manier om een probleem op te lossen soms niet is om harder te werken, maar om het probleem vanuit een andere hoek te bekijken.

Technische Samenvatting van "GPTQ-2D: Cubic-Time Two-Sided Adaptive Rounding"

1. Probleemstelling

Het artikel behandelt het probleem van two-sided adaptive rounding (tweezijdige adaptieve afronding), een generalisatie van de standaard one-sided matrix afronding die wordt gebruikt in kwantiseringsmethoden zoals GPTQ (Frantar et al., 2023) en Babai's nearest plane algoritme (Babai, 1986).

One-Sided Case: Gegeven een reële matrix $X \in \mathbb{R}^{m \times n}$ en een vaste niet-singuliere basismatrix $A \in \mathbb{R}^{m \times m}$ , is het doel om een gehele matrix $Z$ te vinden die $\|A(Z - X)\|_F^2$ minimaliseert. Dit wordt greedily opgelost door de entries in een vaste volgorde te verwerken (bijv. kolom-major), waarbij afrondingsfouten worden gepropageerd via een driehoekige feedbackmatrix. Deze aanpak heeft een complexiteit van $O(m^2 \max(m, n))$ (kubisch voor vierkante matrices).
Two-Sided Case: Het artikel introduceert een tweede vaste niet-singuliere basismatrix $B \in \mathbb{R}^{n \times n}$ die aan de rechterzijde werkt, waardoor het doel verandert naar:
$\|A(Z - X)B\|_F^2 = \|(B^\top \otimes A)(\text{vec}(Z) - \text{vec}(X))\|_2^2$
Hierbij staat $\otimes$ voor het Kronecker-product. Hoewel dit kan worden opgelost door de matrix te vectoriseren naar een vector van lengte-$mn$ en een standaard 1D adaptive rounding toe te passen, is de resulterende Gram-matrix $H \otimes G$ (waarbij $H=BB^\top$ en $G=A^\top A$ ). Een directe sweep over alle $mn$ coördinaten brengt een tijdcomplexiteit van $O(m^2 n^2)$ met zich mee (quartisch voor vierkante matrices), wat computationeel onhaalbaar is voor grote matrices.

De kernuitdaging is om exact hetzelfde afrondingstraject te bereiken als de gevectoriseerde 1D-aanpak, maar met een verminderde computationele complexiteit, idealiter overeenkomend met de kubische kosten van het one-sided geval.

2. Methodologie

De auteurs stellen GPTQ-2D voor, een algoritme dat de specifieke structuur van het Kronecker-product exploiteert om de complexiteit te reduceren van quartisch naar kubisch.

Belangrijke theoretische inzichten:

Kronecker Feedback Structuur: De feedbackmatrix voor het gevectoriseerde probleem is $F = U^\top \otimes L$ , waarbij $L$ en $U$ de eenheidsonder- en bovendriehoeksfactoren zijn afgeleid van de inversen van de Gram-matrices $G$ en $H$ .
Rank-One Updates: Een afrondingsfout bij entry $(i, j)$ genereert een feedback-update van de vorm $L_{:,i} E_{ij} U_{j,:}$ . Dit is een rank-one update die alleen wordt ondersteund op het onder-rechter de rectangle $\{i, \dots, m\} \times \{j, \dots, n\}$ .
Anti-Diagonaal Onafhankelijkheid: Omdat de update van $(i, j)$ alleen entries $(p, q)$ beïnvloedt waar $p \ge i$ en $q \ge j$ , zijn entries op dezelfde anti-diagonaal ( $i+j = s$ ) onderling onafhankelijk. Ze kunnen parallel worden verwerkt zodra alle voorgaande anti-diagonalen zijn voltooid.

Algoritmische aanpak:

Anti-Diagonal Sweep: In plaats van een kolom-major of rij-major sweep, verwerkt het algoritme de matrix in $m+n-1$ stadia, overeenkomend met de anti-diagonalen.
Lazy Propagation (De "Buffer" Truc):
- Een naïeve implementatie van de anti-diagonaal sweep zou nog steeds $O(m^2 n^2)$ werk vereisen omdat het toepassen van de rank-one update $L_{:,i} E_{ij} U_{j,:}$ een grote blok van de matrix dicht beïnvloedt.
- GPTQ-2D vermijdt dit door een hulpbuffer $C = LE$ bij te houden.
- Wanneer een entry $(i, j)$ wordt afgerond, wordt de fout $E_{ij}$ onmiddellijk gepropageerd langs de specifieke kolom (via $L$ ) en rij (via $U$ ).
- De "bulk" van de rectangle-update wordt uitgesteld. Het algoritme duwt de fout naar beneden de kolom in naar de buffer $C$ , en later worden de bufferwaarden naar rechts langs de rijen geduwd.
- Deze "push"-strategie zorgt ervoor dat elke entry precies één keer per afhankelijkheid wordt bijgewerkt, waardoor de sweep-kosten worden teruggebracht naar $O(mn \max(m, n))$ .
Geblokte Implementatie: Om de praktische prestaties op parallelle hardware te verbeteren, introduceren de auteurs een geblokte variant (Algoritme 4). Deze verwerkt $w$ anti-diagonalen tegelijk, accumuleert fouten in een blok en voert ze vervolgens door naar de rest van de matrix met behulp van band-achtige matrixproducten, vergelijkbaar met de lazy block updates in GPTQ.

3. Belangrijkste Bijdragen

Formulering: Het artikel herformuleert two-sided matrix afronding als vector afronding onder een Kronecker-metriek, en bewijst dat de resulterende feedback rank-one en scheidbaar is.
Complexiteitsreductie: Het demonstreert dat het two-sided probleem kan worden opgelost in $O((\max(m, n))^3)$ tijd, wat overeenkomt met de asymptotische kosten van one-sided GPTQ, in plaats van de $O(m^2 n^2)$ kosten van een directe gevectoriseerde sweep.
Exacte Equivalentie: Theorem 2 bewijst dat GPTQ-2D de identieke afgeronde matrix produceert als de standaard 1D adaptive rounding algoritme toegepast op de gevectoriseerde input, mits er een deterministische tie-breaking regel wordt gebruikt.
Orde-invariantie: Het artikel stelt vast (Theorem 1) dat adaptive rounding invariant is voor de volgorde van verwerking, mits de volgorde de feedback-afhankelijkheden respecteert (d.w.z. een topologische sortering van de afhankelijkheidsgraaf). Dit rechtvaardigt de parallelle anti-diagonaal sweep.

4. Resultaten en Complexiteitsanalyse

Tijdcomplexiteit:
- Factorisatie: Het berekenen van de LDL-decompositie van de inverse Gram-matrices kost $O((\max(m, n))^3)$ .
- Sweep: De afrondingssweep kost $O(mn \max(m, n))$ .
- Totaal: Voor vierkante matrices ( $m=n$ ) is de totale complexiteit $O(m^3)$ , een significante verbetering ten opzichte van de $O(m^4)$ van de directe dense aanpak.
Parallellisme: Het algoritme ondersteunt van nature parallellisme met $m+n-1$ stadia. Binnen elk stadium (anti-diagonaal) kunnen alle entries gelijktijdig worden verwerkt.
Geheugen: De werkgeheugenruimte is $O((\max(m, n))^2)$ voor de factoren en $O(mn)$ voor de sweep-buffers.

5. Betekenis en Claims

Het artikel positioneert GPTQ-2D niet als een concurrent van one-sided GPTQ, maar als een noodzakelijke uitbreiding voor scenario's die twee-zijdige metrieken vereisen (bijv. Kronecker-gefactoreerde Hessians in kwantisering).

Extensie van GPTQ: De auteurs stellen dat one-sided rounding het speciale geval is waarbij $B=I$ . GPTQ-2D breidt deze capaciteit uit naar het two-sided geval zonder een factor $\Theta(\min(m, n))$ toename in computationele kosten te veroorzaken.
Praktisch Nut: Het algoritme is ontworpen als een "drop-in replacement" voor de afrondingsstap in bestaande two-sided methoden zoals YAQA (Tseng et al., 2026). Hoewel YAQA ook anti-diagonaal sweeps gebruikt, gebruikt de referentie-implementatie van YAQA dense matrixproducten, wat resulteert in een quartic complexiteit. GPTQ-2D biedt hetzelfde afrondingstraject met een kubische complexiteit, wat het haalbaar maakt voor grootschalige toepassingen.
Beperkte Omvang: Het artikel vermijdt expliciet claims van globale optimaliteit (er wordt opgemerkt dat het vinden van het exacte dichtstbijzijnde roosterpunt NP-hard is) en richt zich strikt op de efficiëntie van het greedy, adaptive rounding traject gedefinieerd door de metriek. Het stelt geen nieuwe toepassingen voor, maar optimaliseert de computationele kosten van bestaande two-sided afrondingsformuleringen.