🤖 machine learning

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

本文介绍了 GPTQ-2D，这是一种立方时间复杂度的算法，它通过沿反对角线并行处理条目，高效地对矩阵执行双向自适应舍入，从而在产生相同结果的同时，将计算复杂度从标准向量化方法所需的四次方时间降低下来。

原作者： Jiale Chen, Torsten Hoefler, Dan Alistarh

发布于 2026-07-30

📖 1 分钟阅读☕ 轻松阅读

原作者： Jiale Chen, Torsten Hoefler, Dan Alistarh

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图将一座巨大且摇晃的积木塔（Jenga 积木）装进一个整齐、坚固的盒子里。在人工智能的世界里，这些“积木”就是存储在巨型电子表格（矩阵）中的数字，它们教会了计算机如何思考。为了让这些计算机运行得更快、消耗更少的能量，工程师们尝试将这些数字缩小为简单的整数，这个过程被称为“量化”。但问题在于，如果你只是随机地切掉小数部分，积木塔就会倒塌，导致计算机开始犯傻。

为了解决这个问题，科学家们使用了一个聪明的技巧，叫做“自适应舍入”（adaptive rounding）。把这想象成一场多米诺骨牌游戏。当你推倒一个骨牌（舍入一个数字）时，会产生一个微小的晃动。自适应舍入并没有忽略这个晃动，而是捕捉它并将其向前传递给下一个骨牌，通过轻微调整使其保持整齐。这种被称为 GPTQ 的方法多年来一直表现出色，但它只在骨牌排列成单行时效果最好。然而，现代 AI 模型更像是巨大的二维多米诺骨牌网格，推倒一个骨牌会影响到它右侧和下方的邻居。试图用旧的“单行”方法来修复这个二维网格，就像是试图通过只拉住绳结的一端来解开一个结——虽然能解开，但过程极其缓慢，且容易陷入循环，速度比必要的慢了四倍。

这篇论文介绍了一种解开这个绳结的新方法，叫做 GPTQ-2D。作者 Jiale Chen、Torsten Hoefler 和 Dan Alistarh 发现，你不需要一个接一个地去拉动多米诺骨牌，而是可以抓取整条对角线上的骨牌，并同时修复它们。通过意识到一个方块产生的“晃动”只会向右下方传播，他们找到了一个捷径，让处理整个网格的速度大幅提升。他们从数学上证明了，这种新方法产生的完美积木塔与旧的慢速方法完全一致，但它的运行时间是“立方级”（很快）而非“四次方级”（极其缓慢）。这意味着我们现在可以更高效地缩小这些庞大的 AI 大脑，而不会破坏它们，从而让强大的 AI 在日常设备上变得更加触手可及。

双面谜题的故事

让我们深入研究这个谜题的机制。在旧的一侧方法（GPTQ）中，想象你有一排人正在传递一个沉重的背包。如果第一个人掉落了一枚硬币，他会告诉下一个人要多背一点重量来补偿。这发生在一个接一个人的过程中，沿着队伍向下移动。对于单列队伍来说，这效果很好。

但在现实世界的 AI 中，“人”是排列在网格（如棋盘）中的。现在，如果中间的一个人掉落了一枚硬币，这个重量需要由站在他下方和右侧的所有人共同承担。如果你试图通过逐个遍历每一个方格（“向量化”方法）来修复这个网格，你会做大量的重复劳动。这就像是为了清理整个房间，反复擦拭地板上的每一个角落，甚至包括那些你已经擦干净的地方。数学表明，这需要耗费巨大的时间，其增长速度极快：如果你将网格的大小增加一倍，工作量会增加四倍（甚至更多）。

这篇论文的作者观察了这个网格，并发现了一个神奇的现象：任何单个方格产生的“晃动”或误差，只会向特定的方向——即向右下方——传播。这创造了一个看起来像阶梯一样的依赖图。如果你从右上到左下观察这个网格的对角线，你会看到同一条对角线上的所有方格都是相互独立的。它们彼此互不影响！

这就是“顿悟”时刻。因为它们是独立的，你可以像海浪席卷棋盘一样，同时舍入同一条对角线上的所有数字。这就是 GPTQ-2D 的核心。

“懒惰”缓冲区的魔力

那么，他们是如何实现快速处理的呢？在旧的“慢速”方法中，每当你修复一个数字时，你都会立即去更新其下方和右侧巨大的矩形区域内的每一个方格。那是大量的无用功。

新的 GPTQ-2D 算法要“懒惰”得多（在好的意义上）。它不会立即更新整个矩形，而是仅仅将误差向下推入它所在的列，并向右推入它所在的行，留下一个“便条”在缓冲区中。这就像一位老师，他不再走到每个学生的课桌前去纠正错误，而是直接在学生自己的课桌以及右侧同学的课桌上写下修正说明。下游的学生最终会看到这些便条并自行修正。

通过使用这种“懒惰”的方法，该算法避免了不断更新整个网格的繁重工作。它以“波浪”（反对角线）的形式处理网格。每一波消耗的时间极短，由于这些波可以并行发生，整个过程的速度得到了显著提升。

论文证明了这种“懒惰”的对角线方法产生的结果与原结果完全相同，这并非近似值，而是数学上的保证。作者展示了无论是逐个修复骨牌，还是通过对角线波进行修复，最终建立的积木塔是完全一样的。

这为什么很重要

这篇论文不仅仅是猜测它更快，他们通过数学计算进行了证明。对于一个正方形网格（行数等于列数），旧方法所需的时间与网格大小的四次方成正比（ $O(m^2n^2)$ ）。而新的 GPTQ-2D 方法所需的时间与大小的三次方成正比（ $O(m^3)$ ）。

为了让你有个直观的概念：如果你有一个 1,000 x 1,000 的网格，旧方法所做的功比新方法多出了十亿倍。新方法将修复二维网格的成本降低到了与修复简单一维线条相同的水平。

作者还描述了该算法的一个“分块”（blocked）版本（算法 4），该版本将这些对角线波组合成块。这是为了更好地适配现代计算机芯片，因为芯片更喜欢一次处理大块的数学运算，而不是零散的小块。这使得该理论具备了投入实用的能力。

简而言之，这篇论文解决了一个对于大型复杂 AI 模型来说过于缓慢、难以实际应用的问题，并赋予了它速度上的飞跃，使其变得可行。它表明，通过改变我们观察数据的方式——将直线换成对角线波浪——我们可以像解决一维问题一样轻松地解决二维问题，且不会损失任何精度。这提醒我们，有时最快解决问题的方法不是更努力地工作，而是从不同的角度去看待问题。

GPTQ-2D 技术摘要：三次复杂度双侧自适应舍入

1. 问题陈述

本文探讨了**双侧自适应舍入（two-sided adaptive rounding）**问题，这是对 GPTQ (Frantar et al., 2023) 和 Babai 最近平面算法 (Babai, 1986) 等量化方法中所使用的标准单侧矩阵舍入问题的推广。

单侧情况： 给定实矩阵 $X \in \mathbb{R}^{m \times n}$ 和一个固定的非奇异基矩阵 $A \in \mathbb{R}^{m \times m}$ ，目标是找到一个整数矩阵 $Z$ ，使 $\|A(Z - X)\|_F^2$ 最小化。该问题通过按固定顺序（例如列优先）处理条目，并通过三角反馈矩阵传播舍入误差来贪婪地解决。这种方法的时间复杂度为 $O(m^2 \max(m, n))$ （对于方阵为三次复杂度）。
双侧情况： 本文引入了第二个作用于右侧的固定非奇异基矩阵 $B \in \mathbb{R}^{n \times n}$ ，将目标函数变为：
$\|A(Z - X)B\|_F^2 = \|(B^\top \otimes A)(\text{vec}(Z) - \text{vec}(X))\|_2^2$
这里 $\otimes$ 表示克罗内克积（Kronecker product）。虽然可以通过将矩阵向量化为一个长度为 $mn$ 的向量并应用标准的一维自适应舍入来解决此问题，但生成的 Gram 矩阵为 $H \otimes G$ （其中 $H=BB^\top, G=A^\top A$ ）。直接对所有 $mn $个坐标进行遍历会产生$ O(m^2 n^2)$ 的时间复杂度（对于方阵为四次复杂度），这在计算上是难以承受的。

核心挑战在于：如何在实现与向量化一维方法完全相同的舍入轨迹的同时，降低计算复杂度，理想情况下应达到与单侧情况一致的三次复杂度。

2. 方法论

作者提出了 GPTQ-2D 算法，利用克罗内克积的特定结构将复杂度从四次降低到三次。

核心理论洞察：

克罗内克反馈结构： 向量化问题的反馈矩阵为 $F = U^\top \otimes L$ ，其中 $L$ 和 $U$ 是由 Gram 矩阵 $G$ 和 $H$ 的逆导出的单位下三角和上三角因子。
秩一更新（Rank-One Updates）： 条目 $(i, j)$ 处的舍入误差会产生形式为 $L_{:,i} E_{ij} U_{j,:}$ 的反馈更新。这是一个仅在右下矩形区域 $\{i, \dots, m\} \times \{j, \dots, n\}$ 上有值的秩一更新。
反对角线独立性： 由于来自 $(i, j)$ 的更新仅影响满足 $p \ge i$ 且 $q \ge j$ 的条目 $(p, q)$ ，因此位于同一条反对角线（即 $i+j = s$ ）上的条目在彼此之间是独立的。一旦完成所有先前的对角线，这些条目可以并行处理。

算法流程：

反对角线扫描（Anti-Diagonal Sweep）： 算法不是采用列优先或行优先扫描，而是通过 $m+n-1$ 个阶段进行处理，每个阶段对应一条反对角线。
延迟传播（“缓冲区”技巧）：
- 朴素的反对角线扫描实现仍需 $O(m^2 n^2)$ 的工作量，因为应用秩一更新 $L_{:,i} E_{ij} U_{j,:}$ 会密集地触及矩阵的大块区域。
- GPTQ-2D 通过维护一个辅助缓冲区 $C = LE$ 来避免这种情况。
- 当一个条目 $(i, j)$ 被舍入时，误差 $E_{ij}$ 会立即沿着其特定的列（通过 $L$ ）和行（通过 $U$ ）进行传播。
- 矩形更新的“主体部分”被推迟处理。算法将误差向下推入列缓冲区 $C$ ，随后缓冲区中的值再沿行向右推送。
- 这种“推送”策略确保每个条目在每个依赖关系中仅被更新一次，从而将扫描成本降低到 $O(mn \max(m, n))$ 。
分块实现： 为了提高在并行硬件上的实际性能，作者引入了分块变体（算法 4）。它一次处理 $w$ 条反对角线，在块中累积误差，并使用类似于 GPTQ 中延迟块更新的带状矩阵乘法将误差刷新到矩阵其余部分。

3. 主要贡献

公式化： 本文将双侧矩阵舍入重新表述为克罗内克度量下的向量舍入，并证明了由此产生的反馈是秩一且可分离的。
复杂度降低： 文中证明了双侧问题可以在 $O((\max(m, n))^3)$ 时间内解决，这与单侧 GPTQ 的渐近成本一致，而非直接向量化扫描的 $O(m^2 n^2)$ 成本。
等价性证明： 定理 2 证明，只要使用确定性的平局处理规则（tie-breaking rule），GPTQ-2D 生成的舍入矩阵与应用于向量化输入后的标准一维自适应舍入算法生成的矩阵是完全一致的。
顺序不变性： 本文确立了（定理 1）自适应舍入对于处理顺序具有不变性，前提是该顺序遵循反馈依赖关系（即依赖图的拓扑排序）。这证明了反对角线并行扫描的合理性。

4. 结果与复杂度分析

时间复杂度：
- 分解： 计算逆 Gram 矩阵的 LDL 分解需要 $O((\max(m, n))^3)$ 。
- 扫描： 舍入扫描过程需要 $O(mn \max(m, n))$ 。
- 总计： 对于方阵（ $m=n$ ），总复杂度为 $O(m^3)$ ，相比直接进行稠密处理的 $O(m^4)$ 有显著提升。
并行性： 算法天然支持以 $m+n-1$ 个阶段进行的并行处理。在每个阶段（反对角线）内，所有条目可以同时处理。
内存： 用于因子的工作存储空间为 $O((\max(m, n))^2)$ ，用于扫描缓冲区的空间为 $O(mn)$。

5. 重要性与主张

本文将 GPTQ-2D 定位为单侧 GPTQ 的必要扩展，而非竞争对手，旨在应对需要双侧度量（例如量化中的克罗内克因子化海森矩阵）的场景。

GPTQ 的扩展： 作者指出，当 $B=I$ 时，单侧舍入是其特例。GPTQ-2D 将这种能力扩展到了双侧情况，且没有引入 $\Theta(\min(m, n))$ 倍的计算成本增加。
实际效用： 该算法旨在作为现有双侧方法（如 YAQA, Tseng et al., 2026）中舍入步骤的无缝替换方案。虽然 YAQA 也利用了反对角线扫描，但其参考实现使用了稠密矩阵乘法，导致了四次复杂度。GPTQ-2D 在提供相同舍入轨迹的同时，实现了三次复杂度的效率，使其在大规模应用中变得可行。
研究范围： 本文明确避免了关于全局最优性的主张（指出寻找精确最近格点是 NP 难问题），而是专注于优化由给定度量定义的贪婪、自适应舍入轨迹的计算效率。它并非提出新的应用场景，而是优化了现有双侧舍入公式的计算成本。