🤖 machine learning

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

Este artículo presenta GPTQ-2D, un algoritmo de tiempo cúbico que realiza eficientemente el redondeo adaptativo de dos lados en matrices procesando las entradas en paralelo a lo largo de las antidiagonales, reduciendo así la complejidad computacional del tiempo cuártico requerido por los métodos de vectorización estándar al tiempo mismo de producir resultados idénticos.

Autores originales: Jiale Chen, Torsten Hoefler, Dan Alistarh

Publicado 2026-07-30

📖 7 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Jiale Chen, Torsten Hoefler, Dan Alistarh

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que estás intentando empacar una torre masiva y tambaleante de bloques Jenga en una caja rígida y ordenada. En el mundo de la inteligencia artificial, estos "bloques" son números dentro de una hoja de cálculo gigante (una matriz) que le enseña a una computadora cómo pensar. Para que estas computadoras funcionen más rápido y consuman menos energía, los ingenieros intentan reducir estos números a números enteros simples, un proceso llamado "cuantización". Pero aquí está el truco: si simplemente cortas los decimales al azar, la torre se derrumba y la computadora empieza a cometer errores tontos.

Para solucionar esto, los científicos utilizan un trucreto llamado "redondeo adaptativo". Piensa en esto como un juego de dominó. Cuando derribas un dominó (redondeas un número), creas un pequeño tambaleo. En lugar de ignorar este tambaleo, el redondeo adaptativo lo atrapa y lo empuja hacia adelante al siguiente dominó en la línea, ajustándolo ligeramente para que toda la línea se mantenga recta. Este método, conocido como GPTQ, ha sido una superestrella durante años, pero solo funciona bien cuando los dominós están dispuestos en una sola línea larga. Sin embargo, los modelos de IA modernos son más bien una gigantesca cuadrícula bidimensional de dominós, donde derribar uno afecta a sus vecinos tanto a la derecha como abajo. Intentar arreglar esta cuadrícula 2D con el viejo método de "una sola línea" es como intentar desenredar un nudo tirando de un solo extremo: funciona, pero toma una eternidad y se queda atrapado en un bucle que es cuatro veces más lento de lo necesario.

Este artículo presenta una nueva forma de desenredar ese nudo, llamada GPTQ-2D. Los autores, Jiale Chen, Torsten Hoefler y Dan Alistarh, descubrieron que no necesitas tirar de los dominós uno por uno en una línea larga. En su lugar, puedes agarrar filas diagonales enteras de dominós y arreglarlas todas al mismo tiempo. Al darse cuenta de que el "tambaleo" de un bloque solo viaja hacia abajo y hacia la derecha, encontraron un atajo que les permite procesar toda la cuadrícula en una fracción del tiempo. Demostraron matemáticamente que este nuevo método produce exactamente la misma torre perfecta que el viejo y lento método, pero lo hace en un tiempo "cúbico" (que es rápido) en lugar de un tiempo "cuártico" (que es dolorosamente lento). Esto significa que ahora podemos encoger estos gigantescos cerebros de IA de manera mucho más eficiente sin romperlos, haciendo que la IA poderosa sea más accesible en dispositivos cotidianos.

La historia del rompecabezas de dos lados

Sumerjámonos en la mecánica de este rompecabezas. En el viejo método de un solo lado (GPTQ), imagina que tienes una fila de personas pasándose una mochila pesada. Si la primera persona deja caer una moneda, le dice a la siguiente persona que cargue un poco de peso extra para compensar. Esto sucede una persona a la vez, moviéndose a lo largo de la línea. Funciona muy bien para una fila de un solo archivo.

Pero en el mundo real de la IA, las "personas" están dispuestas en una cuadrícula, como un tablero de ajedrez. Ahora, si una persona en el medio deja caer una moneda, ese peso debe repartirse entre todos los que están debajo de ella y todos los que están a su derecha. Si intentas arreglar esta cuadrícula pasando por cada uno de los cuadros uno por uno (el enfoque "vectorizado"), terminarás haciendo una cantidad enorme de trabajo redundante. Es como intentar limpiar toda una habitación limpiando cada pulgada del suelo, incluso las partes que ya has limpiado, una y otra vez. Las matemáticas muestran que esto toma una cantidad de tiempo enorme, creciendo tan rápido que si duplicas el tamaño de la cuadrícula, el trabajo se cuadruplica (o incluso más).

Los autores de este artículo miraron esta cuadrícula y se dieron cuenta de algo mágico: el "tambaleo" o error de cualquier cuadro individual solo viaja en una dirección específica: hacia abajo y hacia la derecha. Esto crea un grafo de dependencia que parece una escalera. Si miras la cuadrícula diagonalmente (de arriba a la derecha hacia abajo a la izquierda), verás que todos los cuadros en una misma línea diagonal son independientes entre sí. ¡No se afectan unos a otros!

Este es el momento del "¡Ajá!". Debido a que son independientes, puedes redondear todos los números en una sola línea diagonal al mismo tiempo, como una ola rompiendo a través del tablero. Este es el núcleo de GPTQ-2D.

La magia del búfer "perezoso"

Entonces, ¿cómo hacen esto rápido? En el viejo método "lento", cada vez que arreglabas un número, ibas inmediatamente y actualizabas cada uno de los cuadros en el enorme rectángulo debajo y a la derecha de este. Eso es mucho trabajo innecesario.

El nuevo algoritmo GPTQ-2D es mucho más perezoso (en el buen sentido). En lugar de actualizar todo el rectángulo inmediatamente, simplemente empuja el error hacia abajo en su propia columna y a través de su propia fila, dejando una "nota" en un búfer. Es como un profesor que, en lugar de caminar hasta el escritorio de cada estudiante para corregir un error, simplemente escribe la corrección en el propio escritorio del estudiante y en el escritorio del estudiante a su derecha. Los estudiantes más adelante en la línea eventualmente verán estas notas y se corregirán a sí mismos.

Al usar este enfoque "perezoso", el algoritmo evita el trabajo pesado de actualizar toda la cuadrícula constantemente. Procesa la cuadrícula en "olas" (las antidiagonales). Cada ola toma un poco de tiempo y, debido a que las olas pueden ocurrir en paralelo, todo el proceso se acelera drásticamente.

El artículo demuestra que este enfoque diagonal y perezoso produce exactamente el mismo resultado que el método lento de uno por uno. No es una aproximación; es una garantía matemática. Los autores demuestran que ya sea que arregles los dominós uno por uno o en ondas diagonales, la torre final se mantiene exactamente igual.

Por qué esto es importante

El artículo no solo supone que esto es más rápido; hicieron las matemáticas para demostrarlo. Para una cuadrícula cuadrada (donde el número de filas es igual al número de columnas), el método antiguo toma un tiempo proporcional al tamaño de la cuadrícula elevado a la cuarta potencia ( $O(m^2n^2)$ ). El nuevo método GPTQ-2D toma un tiempo proporcional al tamaño elevado al cubo ( $O(m^3)$ ).

Para ponerlo en perspectiva: si tienes una cuadrícula de 1,000 por 1,000, el método antiguo está haciendo un billón de veces más trabajo del necesario en comparación con el nuevo método. El nuevo método reduce el costo de arreglar una cuadrícula de dos lados al mismo nivel que arreglar una simple línea de un solo lado.

Los autores también describen una versión "bloqueada" de este algoritmo (Algoritmo 4), que agrupa estas ondas diagonales en bloques. Esto está diseñado para funcionar aún mejor en los chips de computadora modernos, que aman hacer grandes bloques de matemáticas todos a la vez en lugar de bits pequeños y dispersos. Esto hace que la teoría esté lista para el uso en el mundo real.

En resumen, este artículo toma un problema que era demasiado lento para ser práctico para modelos de IA grandes y complejos y le da un impulso de velocidad que lo hace factible. Demuestra que al cambiar el orden en el que miramos los datos —cambiando una línea recta por una onda diagonal— podemos resolver un rompecabezas de dos lados tan fácilmente como uno de un solo lado, sin perder nada de precisión. Es un recordatorio de que, a veces, la forma más rápida de solucionar un problema no es trabajar más duro, sino mirar el problema desde un ángulo diferente.

Resumen Técnico de "GPTQ-2D: Redondeo Adaptativo Bidireccional de Tiempo Cúbico"

1. Planteamiento del Problema

El artículo aborda el problema del redondeo adaptativo bidireccional, una generalización del redondeo matricial unidireccional estándar utilizado en métodos de cuantización como GPTQ (Frantar et al., 2023) y el algoritmo de plano más cercano de Babai (Babai, 1986).

Caso Unidireccional: Dada una matriz real $X \in \mathbb{R}^{m \times n}$ y una matriz de base no singular fija $A \in \mathbb{R}^{m \times m}$ , el objetivo es encontrar una matriz entera $Z$ que minimice $\|A(Z - X)\|_F^2$ . Esto se resuelve de forma codiciosa (greedy) procesando las entradas en un orden fijo (por ejemplo, por orden de columna), propagando los errores de redondeo mediante una matriz de retroalimentación triangular. Este enfoque se ejecuta en un tiempo de $O(m^2 \max(m, n))$ (cúbico para matrices cuadradas).
Caso Bidireccional: El artículo introduce una segunda matriz de base no singular fija $B \in \mathbb{R}^{n \times n}$ que actúa por la derecha, cambiando el objetivo a:
$\|A(Z - X)B\|_F^2 = \|(B^\top \otimes A)(\text{vec}(Z) - \text{vec}(X))\|_2^2$
Aquí, $\otimes$ denota el producto de Kronecker. Aunque esto puede resolverse vectorizando la matriz en un vector de longitud-$mn$ y aplicando el redondeo adaptativo 1D estándar, la matriz de Gram resultante es $H \otimes G$ (donde $H=BB^\top, G=A^\top A$ ). Un barrido directo sobre todas las $mn$ coordenadas incurre en una complejidad temporal de $O(m^2 n^2)$ (cuártica para matrices cuadradas), lo cual es computacionalmente prohibitivo para matrices grandes.

El desafío central es lograr exactamente la misma trayectoria de redondeo que el enfoque de vectorización 1D, pero con una complejidad computacional reducida, idealmente igualando el costo cúbico del caso unidireccional.

2. Metodología

Los autores proponen GPTQ-2D, un algoritmo que aprovecha la estructura específica del producto de Kronecker para reducir la complejidad de cuártica a cúbica.

Percepciones Teóricas Clave:

Estructura de Retroalimentación de Kronecker: La matriz de retroalimentación para el problema vectorizado es $F = U^\top \otimes L$ , donde $L$ y $U$ son los factores triangulares unitarios inferior y superior derivados de las inversas de las matrices de Gram $G$ y $H$ .
Actualizaciones de Rango Uno: Un error de redondeo en la entrada $(i, j)$ genera una actualización de retroalimentación de la forma $L_{:,i} E_{ij} U_{j,:}$ . Esta es una actualización de rango uno soportada únicamente en el rectángulo inferior derecho $\{i, \dots, m\} \times \{j, \dots, n\}$ .
Independencia de la Antidiagonal: Debido a que la actualización de $(i, j)$ solo afecta a las entradas $(p, q)$ donde $p \ge i$ y $q \ge j$ , las entradas en la misma antidiagonal ( $i+j = s$ ) son mutuamente independientes. Pueden procesarse en paralelo una vez completadas todas las antidiagonales precedentes.

Enfoque Algorítmico:

Barrido de Antidiagonales: En lugar de un barrido por columnas o filas, el algoritmo procesa la matriz en $m+n-1$ etapas, correspondientes a las antidiagonales.
Propagación Perezosa (El Truco del "Buffer"):
- Una implementación ingenua del barrido de antidiagonales seguiría requiriendo un trabajo de $O(m^2 n^2)$ porque la aplicación de la actualización de rango uno $L_{:,i} E_{ij} U_{j,:}$ toca densamente un bloque grande de la matriz.
- GPTQ-2D evita esto manteniendo un buffer auxiliar $C = LE$.
- Cuando se redondea una entrada $(i, j)$ , el error $E_{ij}$ se propaga solo a lo largo de su columna específica (vía $L$ ) y su fila (vía $U$ ) de forma inmediata.
- La actualización "masiva" del rectángulo se difiere. El algoritmo empuja el error hacia abajo en la columna hacia el buffer $C$ , y más tarde, los valores del buffer se empujan hacia la derecha a lo largo de las filas.
- Esta estrategia de "empuje" asegura que cada entrada sea actualizada exactamente una vez por dependencia, reduciendo el costo del barrido a $O(mn \max(m, n))$ .
Implementación Bloqueada: Para mejorar el rendimiento práctico en hardware paralelo, los autores introducen una variante bloqueada (Algoritmo 4). Esta procesa $w$ antidiagonales a la vez, acumulando errores en un bloque y liberándolos al resto de la matriz utilizando productos de matrices de tipo banda, de forma similar a las actualizaciones de bloques perezosas en GPTQ.

3. Contribuciones Clave

Formulación: El artículo reformula el redondeo de matrices bidireccional como un redondeo vectorial bajo una métrica de Kronecker, demostrando que la retroalimentación resultante es de rango uno y separable.
Reducción de Complejidad: Demuestra que el problema bidireccional puede resolverse en $O((\max(m, n))^3)$ tiempo, igualando el costo asintótico del GPTQ unidireccional, en lugar del costo de $O(m^2 n^2)$ de un barrido directo vectorizado.
Equivalencia Exacta: El Teorema 2 demuestra que GPTQ-2D produce la matriz redondeada idéntica que el algoritmo de redondeo adaptativo 1D estándar aplicado a la entrada vectorizada, siempre que se utilice una regla de desempate determinista.
Invariancia de Orden: El artículo establece (Teorema 1) que el redondeo adaptativo es invariante al orden de procesamiento, siempre que el orden respete las dependencias de retroalimentación (es decir, un ordenamiento topológico del grafo de dependencia). Esto justifica el barrido paralelo de antidiagonales.

4. Resultados y Análisis de Complejidad

Complejidad Temporal:
- Factorización: El cálculo de las descomposiciones LDL de las inversas de las matrices de Gram toma $O((\max(m, n))^3)$ .
- Barrido: El barrido de redondeo toma $O(mn \max(m, n))$ .
- Total: Para matrices cuadradas ( $m=n$ ), la complejidad total es $O(m^3)$ , una mejora significativa respecto al $O(m^4)$ del enfoque denso directo.
Paralelismo: El algoritmo soporta naturalmente el paralelismo con $m+n-1$ etapas. Dentro de cada etapa (antidiagonal), todas las entradas pueden procesarse simultáneamente.
Memoria: El almacenamiento de trabajo es $O((\max(m, n))^2)$ para los factores y $O(mn)$ para los buffers de barrido.

5. Significado y Reivindicaciones

El artículo posiciona a GPTQ-2D no como un competidor de GPTQ unidireccional, sino como una extensión necesaria para escenarios que requieren métricas bidireccionales (por ejemplo, Hessianos factorizados por Kronecker en cuantización).

Extensión de GPTQ: Los autores afirman que el redondeo unidireccional es el caso especial donde $B=I$ . GPTQ-2D extiende esta capacidad al caso bidireccional sin incurrir en un aumento de factor de $\Theta(\min(m, n))$ en el costo computacional.
Utilidad Práctica: El algoritmo está diseñado para ser un reemplazo directo para el paso de redondeo en métodos bidireccionales existentes como YAQA (Tseng et al., 2026). Aunque YAQA también utiliza barridos de antidiagonales, su implementación de referencia utiliza productos de matrices densas, lo que resulta en una complejidad cuártica. GPTQ-2D proporciona la misma trayectoria de redondeo con complejidad cúbica, haciéndolo factible para aplicaciones a gran escala.
Alcance Modesto: El artículo evita explícitamente las afirmaciones de optimalidad global (señalando que encontrar el punto de red más cercano exacto es NP-duro) y se centra estrictamente en la eficiencia de la trayectoria de redondeo adaptativo codicioso definida por la métrica. No propone nuevas aplicaciones, sino que optimiza el costo computacional de las formulaciones de redondeo bidireccional existentes.