🤖 machine learning

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

Este artigo apresenta o GPTQ-2D, um algoritmo de tempo cúbico que realiza eficientemente o arredondamento adaptativo de dois lados em matrizes ao processar entradas em paralelo ao longo de antidiagonais, reduzindo assim a complexidade computacional do tempo quártico exigido pelos métodos de vetorização padrão, enquanto produz resultados idênticos.

Autores originais: Jiale Chen, Torsten Hoefler, Dan Alistarh

Publicado 2026-07-30

📖 7 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Jiale Chen, Torsten Hoefler, Dan Alistarh

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você está tentando empacotar uma torre enorme e instável de blocos de Jenga em uma caixa pequena e rígida. No mundo da inteligência artificial, esses "blocos" são números dentro de uma planilha gigante (uma matriz) que ensina um computador a pensar. Para fazer esses computadores rodarem mais rápido e usarem menos energia, engenheiros tentam reduzir esses números para números inteiros simples, um processo chamado "quantização". Mas há um problema: se você apenas cortar as casas decimais aleatoriamente, a torre desmorona e o computador começa a cometer erros bobos.

Para resolver isso, cientistas usam um truque inteligente chamado "arredondamento adaptativo". Pense nisso como um jogo de dominós. Quando você derruba um dominó (arredonda um número), isso cria um pequeno balanço. Em vez de ignorar esse balanço, o arredondamento adaptativo o captura e o empurra para o próximo dominó na linha, ajustando-o levemente para que toda a linha permaneça reta. Este método, conhecido como GPTQ, tem sido um astro por anos, mas só funciona bem quando os dominós estão organizados em uma única linha longa. No entanto, os modelos de IA modernos são mais como uma grade gigante e bidimensional de dominós, onde derrubar um afeta seus vizinhos tanto à direita quanto abaixo. Tentar consertar essa grade 2D com o antigo método de "uma linha" é como tentar desatar um nó puxando apenas uma das pontas — funciona, mas leva uma eternidade e fica preso em um loop quatro vezes mais lento do que o necessário.

Este artigo apresenta uma nova maneira de desatar esse nó, chamada GPTQ-2D. Os autores, Jiale Chen, Torsten Hoefler e Dan Alistarh, descobriram que você não precisa puxar os dominós um por um em uma linha longa. Em vez disso, você pode agarrar fileiras diagonais inteiras de dominós e consertá-las todas ao mesmo tempo. Ao perceber que o "balanço" de um bloco só viaja para baixo e para a direita, eles encontraram um atalho que permite processar toda a grade em uma fração do tempo. Eles provaram matematicamente que este novo método produz exatamente a mesma torre perfeita que o método antigo e lento, mas o faz em tempo "cúbico" (que é rápido), em vez de tempo "quártico" (que é dolorosamente lento). Isso significa que agora podemos encolher esses cérebros gigantes de IA de forma muito mais eficiente sem quebrá-los, tornando a IA poderosa mais acessível em dispositivos comuns.

A História do Quebra-Cabeça de Dois Lados

Vamos mergulhar na mecânica deste quebra-cabeça. No antigo método de um lado só (GPTQ), imagine que você tem uma fila de pessoas passando uma mochila pesada. Se a primeira pessoa deixa cair uma moeda, ela diz à próxima pessoa para carregar um pouco de peso extra para compensar. Isso acontece uma pessoa de cada vez, movendo-se ao longo da fila. Funciona muito bem para uma fila indiana.

Mas no mundo real da IA, as "pessoas" estão organizadas em uma grade, como um tabuleiro de xadrez. Agora, se uma pessoa no meio deixa cair uma moeda, esse peso precisa ser compartilhado com todos que estão abaixo dela e todos que estão à direita dela. Se você tentar consertar esta grade percorrendo cada quadrado individualmente (a abordagem "vetorizada"), acabará fazendo uma quantidade enorme de trabalho redundante. É como tentar limpar um quarto inteiro limpando cada centímetro do chão, mesmo as partes que você já limpou, repetidamente. A matemática mostra que isso leva um tempo enorme, crescendo tão rápido que, se você dobrar o tamanho da grade, o trabalho quadruplica (ou até mais).

Os autores deste artigo olharam para esta grade e perceberam algo mágico: o "balanço" ou erro de qualquer quadrado viaja apenas em uma direção específica — para baixo e para a direita. Isso cria um gráfico de dependência que se parece com uma escada. Se você olhar para a grade diagonalmente (da parte superior direita para a parte inferior esquerda), verá que todos os quadrados na mesma linha diagonal são independentes entre si. Eles não afetam uns aos outros!

Este é o momento "Aha!". Como eles são independentes, você pode arredondar todos os números em uma única linha diagonal ao mesmo tempo, como uma onda quebrando sobre o tabuleiro. Este é o núcleo do GPTQ-2D.

A Magia do Buffer "Preguiçoso"

Então, como eles tornam isso rápido? No antigo modo "lento", toda vez que você corrigia um número, você imediatamente ia e atualizava cada quadrado no enorme retângulo abaixo e à direita dele. Isso é muito trabalho inútil.

O novo algoritmo GPTQ-2D é muito mais preguiçoso (de um jeito bom). Em vez de atualizar todo o retângulo imediatamente, ele apenas empurra o erro para baixo em sua própria coluna e através de sua própria linha, deixando uma "nota" em um buffer. É como um professor que, em vez de caminhar até a mesa de cada aluno para corrigir um erro, apenas escreve a correção na própria mesa do aluno e na mesa do aluno à direita dele. Os alunos mais adiante na linha eventualmente verão essas notas e se corrigirão.

Ao usar essa abordagem "preguiçosa", o algoritmo evita o trabalho pesado de atualizar toda a grade constantemente. Ele processa a grade em "ondas" (as anti-diagonais). Cada onda leva um tempo minúsculo e, como as ondas podem acontecer em paralelo, todo o processo acelera dramaticamente.

O artigo prova que essa abordagem diagonal preguiçosa produz o mesmo resultado exato que o método lento, um por um. Não é uma aproximação; é uma garantia matemática. Os autores mostram que, quer você conserte os dominós um por um ou em ondas diagonais, a torre final permanece exatamente a mesma.

Por Que Isso Importa

O artigo não apenas supõe que isso é mais rápido; eles fizeram as contas para provar. Para uma grade quadrada (onde o número de linhas é igual ao número de colunas), o método antigo leva um tempo proporcional ao tamanho da grade à quarta potência ( $O(m^2n^2)$ ). O novo método GPTQ-2D leva um tempo proporcional ao tamanho à terceira potência ( $O(m^3)$ ).

Para colocar em perspectiva: se você tiver uma grade de 1.000 por 1.000, o método antigo está fazendo um bilhão de vezes mais trabalho do que o necessário em comparação ao novo método. O novo método reduz o custo de consertar uma grade de dois lados para o mesmo nível de consertar uma simples linha de um lado só.

Os autores também descrevem uma versão "em blocos" deste algoritmo (Algoritmo 4), que agrupa essas ondas diagonais em pedaços. Isso é projetado para funcionar ainda melhor em chips de computador modernos, que adoram fazer grandes blocos de matemática de uma só vez, em vez de pequenos bits espalhados. Isso torna a teoria pronta para o uso no mundo real.

Em resumo, este artigo pega um problema que era lento demais para ser prático para grandes e complexos modelos de IA e lhe dá um impulso de velocidade que o torna viável. Ele mostra que, ao mudar a ordem em que olhamos para os dados — trocando uma linha reta por uma onda diagonal — podemos resolver um quebra-cabeça de dois lados tão facilmente quanto um de um lado só, sem perder nenhuma precisão. É um lembrete de que, às vezes, a maneira mais rápida de resolver um problema não é trabalhar mais duro, mas olhar para o problema de um ângulo diferente.

Resumo Técnico de "GPTQ-2D: Cubic-Time Two-Sided Adaptive Rounding"

1. Definição do Problema

O artigo aborda o problema do arredondamento adaptativo de dois lados (two-sided adaptive rounding), uma generalização do arredondamento de matriz padrão de um lado utilizado em métodos de quantização como o GPTQ (Frantar et al., 2023) e o algoritmo de plano mais próximo de Babai (Babai, 1986).

Caso de um lado: Dado uma matriz real $X \in \mathbb{R}^{m \times n}$ e uma matriz de base não singular fixa $A \in \mathbb{R}^{m \times m}$ , o objetivo é encontrar uma matriz inteira $Z$ que minimize $\|A(Z - X)\|_F^2$ . Isso é resolvido de forma gulosa processando as entradas em uma ordem fixa (ex: ordem de coluna), propagando erros de arredondamento via uma matriz de feedback triangular. Esta abordagem executa em $O(m^2 \max(m, n))$ tempo (cúbico para matrizes quadradas).
Caso de dois lados: O artigo introduz uma segunda matriz de base não singular $B \in \mathbb{R}^{n \times n}$ atuando à direita, alterando o objetivo para:
$\|A(Z - X)B\|_F^2 = \|(B^\top \otimes A)(\text{vec}(Z) - \text{vec}(X))\|_2^2$
Aqui, $\otimes$ denota o produto de Kronecker. Embora isso possa ser resolvido vetorizando a matriz em um vetor de comprimento $mn$ e aplicando o arredondamento adaptativo 1D padrão, a matriz de Gram resultante é $H \otimes G$ (onde $H=BB^\top, G=A^\top A$ ). Uma varredura direta sobre todos os $mn$ coordenadas incorre em uma complexidade de tempo de $O(m^2 n^2)$ (quártica para matrizes quadradas), o que é computacionalmente proibitivo para matrizes grandes.

O desafio central é alcançar exatamente a mesma trajetória de arredondamento da abordagem de vetorização 1D, mas com complexidade computacional reduzida, idealmente igualando o custo cúbico do caso de um lado.

2. Metodologia

Os autores propõem o GPTQ-2D, um algoritmo que explora a estrutura específica do produto de Kronecker para reduzir a complexidade de quártica para cúbica.

Insights Teóricos Principais:

Estrutura de Feedback de Kronecker: A matriz de feedback para o problema vetorizado é $F = U^\top \otimes L$ , onde $L$ e $U$ são os fatores triangulares inferiores e superiores unitários derivados das inversas das matrizes de Gram $G$ e $H$ .
Atualizações de Posto Um (Rank-One): Um erro de arredondamento na entrada $(i, j)$ gera uma atualização de feedback da forma $L_{:,i} E_{ij} U_{j,:}$ . Esta é uma atualização de posto um suportada apenas no retângulo inferior-direito $\{i, \dots, m\} \times \{j, \dots, n\}$ .
Independência de Antidiagonal: Como a atualização de $(i, j)$ afeta apenas as entradas $(p, q)$ onde $p \ge i$ e $q \ge j$ , as entradas na mesma antidiagonal ( $i+j = s$ ) são mutuamente independentes. Elas podem ser processadas em paralelo assim que todas as antidiagonais precedentes forem concluídas.

Abordagem Algorítmica:

Varredura por Antidiagonal: Em vez de uma varredura por coluna ou linha, o algoritmo processa a matriz em $m+n-1$ estágios, correspondentes às antidiagonais.
Propagação Preguiçosa (O Truque do "Buffer"):
- Uma implementação ingênua da varredura de antidiagonal ainda exigiria um trabalho de $O(m^2 n^2)$ porque aplicar a atualização de posto um $L_{:,i} E_{ij} U_{j,:}$ toca densamente um grande bloco da matriz.
- O GPTQ-2D evita isso mantendo um buffer auxiliar $C = LE$.
- Quando uma entrada $(i, j)$ é arredondada, o erro $E_{ij}$ é propagado apenas ao longo de sua coluna específica (via $L$ ) e linha (via $U$ ) imediatamente.
- A "massa" da atualização do retângulo é adiada. O algoritmo empurra o erro para baixo na coluna para o buffer $C$ , e posteriormente, os valores do buffer são empurrados para a direita ao longo das linhas.
- Esta estratégia de "empurrar" garante que cada entrada seja atualizada exatamente uma vez por dependência, reduzindo o custo da varredura para $O(mn \max(m, n))$ .
Implementação em Blocos: Para melhorar o desempenho prático em hardware paralelo, os autores introduzem uma variante em blocos (Algoritmo 4). Esta processa $w$ antidiagonais por vez, acumulando erros em um bloco e descarregando-os no restante da matriz usando produtos de matrizes do tipo banda, similar às atualizações de bloco preguiçosas do GPTQ.

3. Principais Contribuições

Formulação: O artigo recasualiza o arredondamento de matriz de dois lados como arredondamento de vetor sob uma métrica de Kronecker, provando que o feedback resultante é de posto um e separável.
Redução de Complexidade: Demonstra que o problema de dois lados pode ser resolvido em $O((\max(m, n))^3)$ tempo, igualando o custo assintótico do GPTQ de um lado, em vez do custo $O(m^2 n^2)$ de uma varredura direta vetorizada.
Equivalência Exata: O Teorema 2 prova que o GPTQ-2D produz a matriz arredondada idêntica ao algoritmo de arredondamento adaptativo 1D padrão aplicado à entrada vetorizada, desde que uma regra de desempate determinística seja utilizada.
Invariância de Ordem: O artigo estabelece (Teorema 1) que o arredondamento adaptativo é invariante à ordem de processamento, desde que a ordem respeite as dependências de feedback (ou seja, uma ordenação topológica do grafo de dependência). Isso justifica a varredura paralela por antidiagonal.

4. Resultados e Análise de Complexidade

Complexidade de Tempo:
- Fatoração: Calcular as decomposições LDL das inversas das matrizes de Gram leva $O((\max(m, n))^3)$ .
- Varredura: A varredura de arredondamento leva $O(mn \max(m, n))$ .
- Total: Para matrizes quadradas ( $m=n$ ), a complexidade total é $O(m^3)$ , uma melhoria significativa em relação ao $O(m^4)$ da abordagem densa direta.
Paralelismo: O algoritmo suporta naturalmente o paralelismo com $m+n-1$ estágios. Dentro de cada estágio (antidiagonal), todas as entradas podem ser processadas simultaneamente.
Memória: O armazenamento de trabalho é $O((\max(m, n))^2)$ para os fatores e $O(mn)$ para os buffers de varredura.

5. Significância e Alegações

O artigo posiciona o GPTQ-2D não como um competidor do GPTQ de um lado, mas como uma extensão necessária para cenários que exigem métricas de dois lados (ex: matrizes Hessianas fatoradas por Kronecker em quantização).

Extensão do GPTQ: Os autores afirmam que o arredondamento de um lado é o caso especial onde $B=I$ . O GPTQ-2D estende essa capacidade para o caso de dois lados sem incorrer em um aumento de custo computacional de $\Theta(\min(m, n))$ .
Utilidade Prática: O algoritmo foi desenhado para ser um substituto direto (drop-in replacement) para a etapa de arredondamento em métodos de dois lados existentes, como o YAQA (Tseng et al., 2026). Embora o YAQA também utilize varreduras de antidiagonal, sua implementação de referência utiliza produtos de matrizes densas, resultando em complexidade quártica. O GPTQ-2D fornece a mesma trajetória de arredondamento com complexidade cúbica, tornando-o viável para aplicações de larga escala.
Escopo Modesto: O artigo evita explicitamente alegações de otimalidade global (notando que encontrar o ponto de rede mais próximo exato é NP-difícil) e foca estritamente na eficiência da trajetória de arredondamento adaptativo guloso definida pela métrica. Não propõe novas aplicações, mas sim otimiza o custo computacional de formulações de arredondamento de dois lados já existentes.