GPTQ-2D：立方时间的双侧自适应舍入 GPTQ-2D: Cubic-Time Two-Sided Adaptive Rounding
将双侧矩阵舍入从四次方时间降到立方时间，且结果与向量化舍入完全等价。
前置知识
GPTQ / 自适应舍入
GPTQ 是大模型权重量化的主流方法，本质是在二次度量 $\|A(Z-X)\|_F^2$ 下把实矩阵 $X$ 贪心地逐列舍入为整数矩阵 $Z$：每舍入一个元素，就把该元素的舍入误差通过一个由逆 Gram 矩阵 LDL 分解得到的单位下三角反馈矩阵传播到尚未处理的元素，使得后续元素在修正后的值上再舍入。由于误差反馈只耦合列内元素，各列可独立处理，方阵的总开销是 $O(m^3)$。
GPTQ-2D 直接把这套一维舍入原语推广到二维，理解它才能理解论文为什么要保留‘相同的舍入轨迹’这个等价目标。
Babai 最近平面算法
这是格上最近向量问题（CVP）的经典近似算法：在一个由二次度量诱导的格中，沿 Cholesky/反馈因子的方向逐坐标做投影并就近取整。Chen et al. (2026) 和 Birnick (2026) 指出 GPTQ 的列序舍入恰好等价于 Babai 的投影扫描。本文则把该视角推广到 Kronecker 度量诱导的张量积格，左/右轴各自做最近平面。
论文用格论视角证明等价性并给出 GPTQ 的误差界背景，同时点明精确最近格点是 NP-hard，所以方法不做全局最优保证。
Kronecker 积与 vec 恒等式
核心恒等式是 $\text{vec}(ARB)=(B^\top\otimes A)\text{vec}(R)$，它把双侧度量化为单侧向量度量，Gram 矩阵变成 Kronecker 积 $H\otimes G$（其中 $G=A^\top A$，$H=BB^\top$）。Kronecker 积的 LDL 因子等于各轴 LDL 因子的 Kronecker 积，所以二维反馈矩阵可写为 $F=U^\top\otimes L$，这正是 GPTQ-2D 一切推导的起点。
没有这个恒等式就无法把二维问题映射回一维舍入原语，也无法得到秩一可分的反馈结构。
LDL / Cholesky 分解
GPTQ 把逆 Gram 矩阵做单位下三角的 LDL 分解 $G^{-1}=L\Lambda_L L^\top$（Cholesky 的对称变体），得到误差反馈因子 $L$；本文对行 Gram $G=A^\top A$ 得下三角 $L$，对列 Gram $H=BB^\top$ 得上三角 $U$，二者一次性计算，开销 $O((\max(m,n))^3)$，是总开销的主要部分。
理解 $L$、$U$ 的三角支撑范围才能看懂为何反馈只作用于右下矩形、为何反对角线上的元素相互独立。
Kronecker 海森与 LLM 量化
在大模型逐层量化中，一层的目标通常是 $\|W X - \hat{W}X\|$ 的输入二阶矩（单侧）。若要同时建模输出方向，可用左右两侧的基矩阵 $A$、$B$（如 YAQA 的 Kronecker 海森近似）构造双侧目标 $\|A(Z-X)B\|_F^2$。这能更准地刻画权重扰动对激活的影响。
这是双侧舍入被提出的应用动机——单侧 GPTQ 忽略了输出方向耦合，而本文为双侧目标提供了高效求解器。
研究动机
主流量化方法 GPTQ 处理的是单侧目标 $\|A(Z-X)\|_F^2$：只用一个基矩阵 $A$（逐行输入海森），误差反馈只耦合同一列内的元素，因此 $n$ 列可独立地在 $O(m^2n)$ 内完成舍入，方阵总开销 $O(m^3)$。但这种单侧度量忽略了输出方向的耦合——当真实损失需要同时建模输入和输出方向时（例如用 Kronecker 海森近似的 YAQA 设定），目标变为双侧 $\|A(Z-X)B\|_F^2$。此时列之间不再解耦，朴素做法是把矩阵向量化后在 $mn$ 维上跑一维舍入，反馈矩阵是 Kronecker 积 $H\otimes G$，代价飙到 $O(m^2n^2)$，对方阵是四次方，对大语言模型的大权重层根本无法承受。最接近的已有工作 YAQA（Tseng et al., 2026）已经按反对角线块扫描权重矩阵，但每个块仍把反馈当作稠密矩阵乘施加，整体仍是 $O(mn(\max(m,n))^2)$ 的四次方级，成为实际使用的瓶颈。
本文的目标是作者的目标是设计一个算法，在不改变舍入结果的前提下，把双侧目标的舍入轨迹计算从四次方 $O(m^2n^2)$ 降到立方时间 $O(mn\max(m,n))$ 的扫描开销。更具体地，该算法必须产生与‘向量化 vec(X) 后在 Kronecker 度量 $H\otimes G$ 下做一维自适应舍入’完全相同的整数矩阵 $Z$（定理 2 的精确等价），而且端到端（含一次性 Gram 因子分解）总开销 $O((\max(m,n))^3)$ 对方阵与单侧 GPTQ 同阶。这样 GPTQ-2D 可以直接替换 YAQA 的舍入步骤，而保持 YAQA 的 Kronecker 海森草图不变，使双侧量化在算力上变成‘几乎免费’的扩展。
与已有工作不同的是，本文的独特切入点是利用 Kronecker 反馈的秩一可分性而非把矩阵稠密地向量化。作者证明：单个误差 $E_{ij}$ 在修正矩阵上贡献的是秩一更新 $L_{:,i}E_{ij}U_{j,:}$，由于 $L$ 下三角、$U$ 上三角，该更新只支撑在以 $(i,j)$ 为锚点的右下矩形内。由此推出同一反对角线 $I_s=\{(i,j):i+j=s\}$ 上的元素互不可达、可并行舍入。配合一个缓冲 $C=LE$，每个误差只需沿自身所在行（经 $U$）和列（经 $L$）各推一次，矩形的其余部分由后续元素的推送‘惰性填满’。这正是把 GPTQ 的惰性块更新思想移植到反对角线扫描，把稠密矩形更新折叠成每块两个带状矩阵乘。
核心方法
整体思路先有直觉再走技术路线。直觉上：二维问题向量化后度量的 Gram 是 Kronecker 积 $H\otimes G$，一维舍入算法原样适用但代价四次方；然而 Kronecker 结构带来捷径——误差反馈是秩一的 $L_{:,i}E_{ij}U_{j,:}$ 且只覆盖右下矩形，所以同一反对角线 $I_s=\{(i,j):i+j=s\}$ 上的元素彼此独立、可并行处理。技术路线分四步：(1) 由行/列 Gram 的逆做 LDL 分解得单位下三角 $L$（$G^{-1}=L\Lambda_L L^\top$）与单位上三角 $U$（$H^{-1}=U^\top\Lambda_U U$）；(2) 在修正矩阵 $Y=X+LEU$ 上按反对角线 $s=2,\dots,m+n$ 逐条扫描，元素并行取整 $Z_{ij}=\lfloor Y_{ij}\rceil$；(3) 维护缓冲 $C=LE$，把误差沿列折入并向下/向右推送；(4) 用分块（Algorithm 4，块宽 $w$）把短更新合并成每块两个带状矩阵乘，再用 padded skew 布局让三类访问都是定步长切片。
核心创新在于把‘沿右下矩形稠密地施加秩一反馈’替换为‘只沿自身行列推送一次，矩形其余部分惰性由后续元素补足’，并证明这种局部推送与全局稠密更新产生逐位相同的舍入轨迹（定理 2）。这与已有方法的本质区别是：直接稠密实现（Algorithm 2）和 YAQA 都把每个反对角线的反馈融合成一个覆盖整个 $m\times n$ 块的稠密更新，开销 $O(m^2n^2)$；而 GPTQ-2D 引入辅助缓冲 $C=LE$，使每个元素的反馈降为长度 $O(\max(m,n))$ 的两次推送（向下沿列、向右沿行），总扫描开销 $O(mn\max(m,n))$，对方阵是立方。第二个关键点是秩序不变性定理（定理 1）：任何尊重反馈依赖的拓扑序都产生相同结果，从而允许偏离列优先序、改用反对角线并行扫描而不改变数值。第三是 padded skew 布局：在 $m+n-1$ 行、行步长 $r=2m+n-2$ 的填充数组里，反对角线是行内连续段（步长 1）、矩阵列是垂直 $r$ 步长线、矩阵行是 $r+1$ 对角步长线，三种访问模式都成为定步长切片，避免退化成 gather。
方法步骤详情
以 Algorithm 3 为主线。输入：$X\in\mathbb{R}^{m\times n}$ 与非奇异基 $A$、$B$。先算 $L=\text{LDL}(A^\top A)^{-1}$、$U=\text{LDL}(BB^\top)^{-1}$（开销 $O((\max(m,n))^3)$），初始化 $Y=X$、缓冲 $C=0$（恒为 $LE$）。再按 $s=2,\dots,m+n$ 扫描反对角线 $I_s=\{(i,j):i+j=s\}$。对每个 $(i,j)\in I_s$（并行）：取整 $Z_{ij}=\lfloor Y_{ij}\rceil$、记误差 $E_{ij}$；把误差沿 $L$ 第 $i$ 列缩放得 $M=L_{:,i}E_{ij}$，折入 $C_{:,j}$ 并向下推 $Y_{i+1:,j}$。随后对该反对角线所有元素（并行）向右推 $Y_{i,j+1:}$，系数为 $C_{ij}U_{j,j+1:}$。共 $m+n-1$ 个并行级。分块版 Algorithm 4 把每 $w$ 条反对角线打包，块内截断 fold/推送，块尾用两个带状矩阵乘做 down-flush（同时补全 $C=LE$）与 right-flush，反馈开销仍为 $O(mn\max(m,n))$。
技术新颖性
技术新颖性体现在三点。第一，把 GPTQ 的惰性块更新从一维列序推广到二维反对角线序：一维 GPTQ 靠 Cholesky 预计算把单层代价从四次方降到立方；本文靠反对角线独立性与缓冲 $C=LE$，把二维向量化扫描的 $O(m^2n^2)$ 同样降到立方，且对方阵与单侧 GPTQ 同阶 $O(m^3)$，使双侧扩展‘渐近免费’（表 1）。第二，给出严格等价证明：定理 1（秩序不变性）保证反对角线序与列优先序等价；定理 2 用对反对角线指标 $s$ 的归纳证明 Algorithm 3 在每个 $(i,j)$ 处的修正值恰为 $Y_{ij}=X_{ij}+(LEU)_{ij}$（公式 15–17），即与向量化一维舍入逐位相同。第三，工程层面提出 padded skew 布局（图 2），把算法中三类访问模式统一为定步长切片，使方法能在 PyTorch 等框架上高效实现而不退化为 gather；并指出可在核级实现中保持自然布局、用掩码处理越界通道，从而免去填充开销。
实验结果
本文是理论与算法论文，无真实大模型量化实验，结论围绕复杂度与精确等价展开。其一，扫描开销：GPTQ-2D 舍入扫描为 $O(mn\max(m,n))$，而向量化舍入与稠密反对角线更新（Algorithm 2）都是 $O(m^2n^2)$，对方阵从四次方降到立方，提升因子 $\Theta(\min(m,n))$；端到端含 Gram 因子分解总开销 $O((\max(m,n))^3)$，与单侧 GPTQ 同阶。其二，并行深度仅 $m+n-1$ 级，远少于向量化一维的 $mn$ 级。其三，工作存储 $O((\max(m,n))^2)$ 存因子、$O(mn)$ 存缓冲。其四，精确等价（定理 2）：Algorithm 2、3 与一维舍入在反馈 $U^\top\otimes L$ 下产生逐位相同的 $Z$。其五，YAQA 逆序、GPTQ-2D 正序，方向相反但舍入相同，可直接替换 YAQA 的 $O(mn(\max(m,n))^2)$ 稠密舍入步而不动其海森草图。其六，分块版对任意块宽 $w$ 反馈开销仍为 $O(mn\max(m,n))$。
查看结构化数据
| 任务 | 指标 | 本文 | 基线 | 提升 |
|---|---|---|---|---|
| 双侧矩阵舍入扫描工作量 | 渐近复杂度（方阵 $m\!=\!n$） | $O(mn\max(m,n))=O(m^3)$ 扫描，$O((\max(m,n))^3)=O(m^3)$ 总开销 | 向量化/稠密反对角线 $O(m^2n^2)=O(m^4)$；YAQA $O(mn(\max(m,n))^2)=O(m^4)$ | 降低 $\Theta(\min(m,n))$ 因子，对方阵从四次方降到立方，且与单侧 GPTQ 同阶 |
| 并行扫描深度 | 串行阶段数 | $m+n-1$ 个并行级 | 向量化一维扫描 $mn$ 个串行级；GPTQ 单侧 $O(m)$ 级 | 深度从 $O(mn)$ 降到 $O(m+n)$，反对角线元素可并行取整 |
| 舍入结果正确性 | 与向量化舍入的逐位等价 | 定理 2 保证 Algorithm 2/3 与一维舍入产生完全相同的 $Z$ | YAQA 逆序扫描，方向相反但舍入相同 | 首次给出立方时间内精确等价于向量化轨迹的双侧算法，无近似损失 |
局限与改进
作者明确指出两点局限。第一，等价保证（定理 2）要求基矩阵 $A$、$B$（从而反馈因子 $L$、$U$）在整个扫描中保持固定；若它们随中间舍入决策自适应变化（例如数据相关的缩放），则与固定向量化过程不再精确等价。第二，GPTQ-2D 计算的是固定序的贪心轨迹，不做全局最优保证——这是从一维自适应舍入（及 GPTQ）继承的，而非二维设定新引入；精确最近格点在一般情况下是 NP-hard（Dinur et al., 2003）。此外，方法不解决建模问题：如何为给定应用选择 $A$、$B$（如 Kronecker 海森的估计）不在本文范围内，方法应被理解为‘给定 Kronecker 舍入的高效执行器’而非新舍入规则。我的补充观察：论文无任何真实 LLM 量化的端到端实验（无 perplexity、无精度对比），难以判断立方级算法在实际 GPU 上的常数因子是否真有竞争力；padded skew 布局对长方形矩阵（如 $m\gg n$）填充开销 $\Theta((\max(m,n))^2)$ 会变大，虽可转置问题以减小，但仍是工程负担。
独立分析的弱点
独立分析的弱点有三。第一，缺乏实证验证：全篇是复杂度与等价性理论，没有在真实大模型（如 LLaMA 级别）上对比 GPTQ-2D/YAQA/GPTQ 的下游精度（perplexity、零样本准确率）和实际墙钟时间，无法证实‘立方级’在工程上真的优于‘四次方级’（常数因子、GPU 利用率、kernel 融合都未知）。改进方向：补充端到端 LLM 量化实验，报告 perplexity 与吞吐。第二，等价性对‘固定基’敏感：实际量化中常用输入相关的校准与缩放（如 per-channel scale、SmoothQuant 式迁移），这会破坏 $L$、$U$ 的固定性，使 GPTQ-2D 的精确等价失效。改进方向：研究在何种自适应基变动下能保留近似等价并给出可控误差界。第三，padded skew 布局对高长宽比矩阵填充开销大（$\Theta((\max(m,n))^2)$），且在 PyTorch 中需自定义 stride 管理。改进方向：提供 kernel 级实现（论文已建议用掩码替代填充）或自动转置策略，并给出不同长宽比下的实测开销。
未来方向
作者明确划定的开放问题是‘建模’一侧：给定应用如何选择基矩阵 $A$、$B$（例如从 Kronecker 海森近似、KFAC 式因子中估计），本文不涉及。基于该成果可延伸的方向包括：(1) 端到端集成 GPTQ-2D 到 YAQA 流水线并实测，验证立方级算法是否在 GPU 上真正快于四次方级；(2) 把精确等价框架推广到自适应/数据相关基的情形，给出可控误差界，以兼容带缩放的现代量化流程；(3) 探索 padded skew 布局之外的内存布局或 kernel 级实现，降低填充开销并提高并行度；(4) 将反对角线独立性思想用于其他 Kronecker 结构问题（如 Kronecker 海森下的剪枝、二阶优化），看能否同样获得 $\Theta(\min(m,n))$ 的加速；(5) 结合格论视角研究更强的舍入规则（在保持高效的同时逼近全局最优，而非仅复现固定序贪心轨迹）。
复现评估
复现评估中等偏理论。论文未提供代码或数据集链接，也未给出超参（块宽 $w$、具体 LLM、硬件）的实测结果，属于纯算法/定理贡献。好在算法描述非常完整：Algorithm 1–4 给出了可直接落地的伪代码，定理 1、2 给出严格证明，表 1 列出所有变体的 setup/sweep/depth 复杂度，图 2 给出 padded skew 布局的具体坐标（行 $s=i+j$、行内位置 $m-1+j$、行步长 $r=2m+n-2$），图 1 给出依赖图。一名熟悉 GPTQ 的研究者可据此用 PyTorch 复现核心扫描与分块逻辑，算力需求低（验证等价只需中小矩阵）；但要复现端到端 LLM 量化效果则缺乏必要细节。主要复现障碍是 padded skew 布局的 stride 管理与块状带状矩阵乘的实现细节，论文给了方向但未给参考实现。
论文图表