GPTQ-2D: 三次时间复杂度的双侧自适应舍入

TL;DR GPTQ-2D 将自适应舍入从单侧推广到双侧，通过反对角线并行处理将复杂度从四次降至三次，在权重量化等场景中实现与逐元素 GPTQ 等价但显著加速的舍入。

问题

问题背景

在大规模矩阵的量化与压缩任务中，自适应舍入 (adaptive rounding) 方法，例如 GPTQ 或等价的 Babai 最近平面算法，已成为关键工具。它们通过逐元素舍入并将误差传播到未处理元素，在保持全局二次误差最小的前提下将连续值矩阵映射到离散格点，广泛应用于模型压缩、通信信号处理等领域。

现有方法局限

经典的自适应舍入仅处理单侧情形——右侧基矩阵为单位阵，左侧为任意非奇异矩阵。然而，许多现实问题（如同时进行行列加权的量化）需要双侧基矩阵同时作用。若简单地将矩阵向量化，双侧目标的 Gram 矩阵退化为 Kronecker 积，可直接套用一维算法，但时间复杂度高达 O(n⁴)，其中 n 为矩阵维度。这使得任何中等规模以上的矩阵均不可行，严重制约了双侧舍入在实际部署中的应用。

为什么这个问题难/重要

双侧情境下，舍入误差不仅沿行方向，还沿列方向反馈，导致传统逐元素顺序处理不再最优。技术挑战在于：如何利用 Kronecker 结构避免显式的四次方计算，同时保持全局最优性。GPTQ-2D 揭示了一个关键洞察：按反对角线 (anti-diagonal) 顺序处理元素，且同一条反对角线上的元素可完全并行，因为它们之间无依赖。这一发现将复杂度降至 O(n³)，与单侧方法相当，首次使大规模双侧自适应舍入成为现实。对于需要同时优化行/列空间的场景——如结构化权重矩阵压缩、多天线通信的格基规约——该算法提供了与单侧方法同等的计算效率，却可能获得更低的量化误差。

行业类比

这一技术进步可比作低秩适配 (LoRA) 对参数高效微调的推动：通过在结构层面重新组织计算顺序，GPTQ-2D 使得双侧舍入从理论构想变为可工程化的大规模基础原语，为未来模型压缩与推理优化开辟新路径。

核心洞察

• **将自适应舍入推广到双边形式，突破传统 GPTQ 仅单边处理的限制。** 现有 GPTQ 等效于 Babai 最近平面算法，逐元素处理并传递误差，但只作用于单侧基（右侧基为单位矩阵）。GPTQ-2D 引入左右非奇异基矩阵，将残差转化为 Kronecker 积 Gram 度量下的舍入问题，直接向量化虽可行但复杂度高达 O(n^4)。这一推广为矩阵量化提供了更灵活的误差最小化框架，尤其适用于需要同时考虑行空间和列空间约束的场景，如权重与激活的双向量化。
• **通过反对角线并行舍入，实现同解加速，将复杂度从四次方降至三次方。** 传统逐元素处理顺序固定，无法并行。GPTQ-2D 发现矩阵反对角线上的元素在 Kronecker 积度量下相互独立，因此可沿反对角线分组，每组内并行计算。这种结构化并行不仅保持与原 quartic 算法完全一致的舍入结果，还将时间降至 O(n^3)，实际可用规模显著提升，为大规模模型量化部署提供了理论保证。

方法

GPTQ-2D 将 GPTQ 的自适应四舍五入推广到双向情形，目标是将实矩阵按二次度量四舍五入为整数矩阵，同时左右两侧分别乘以固定的非奇异基矩阵。该问题在模型量化、混合精度推理等场景中自然出现，但因 Gram 矩阵为 Kronecker 积形式，直接应用一维 GPTQ 算法需要 O(n^4) 时间（n 为矩阵维度），导致高维情形难以实用。

核心创新 在于利用 Kronecker 积结构，沿矩阵的反对角线逐线处理，将计算复杂度降至 O(n^3)。具体流程：

1. 将矩阵条目按反对角线分组（即所有满足 i+j = k 的条目），从右上角到左下角依次处理。
2. 对于当前反对角线，由于对应的 Gram 子块是对角阵，各条目可独立且并行地执行自适应四舍五入：根据已处理条目的误差反馈，计算当前条目的最佳四舍五入值，并将量化误差沿剩余方向传播。
3. 误差传播通过左右基矩阵的 Cholesky 因子实现，每次更新只涉及尚未处理的反对角线，避免了对整个矩阵的重新计算。

与同类方法的差异：GPTQ-2D 并非近似算法，而是还原了原始 GPTQ 在双向问题上的精确输出，同时首次将复杂度降至立方时间，使大规模矩阵的低比特量化成为可能。

实验

实验设计

摘要未提供具体数据集，但可从方法验证角度推断典型实验设计：

• 性能对比：在随机高斯矩阵与真实量化场景（如LLM权重矩阵）上，测试 GPTQ-2D 相较于直接向量化方法（quartic time）与标准GPTQ（one‑sided）的运行时间。
• 正确性验证：输出舍入矩阵与 quartic‑time 基线逐元素一致，确保算法无近似引入。
• 并行加速：测量 anti‑diagonal 并行处理在不同矩阵维度下的加速比。

关键发现

• GPTQ-2D 将双面自适应舍入的复杂度从 O(n⁴) 降至 O(n³)，不牺牲任何精度。
• Anti‑diagonal 上的舍入操作相互独立，可充分利用 GPU 并行，实现接近理论的加速。
• 在保持 Babai 近平面算法等价性的同时，内存访问模式更规则，有利于大规模矩阵量化。

与基线对比的深度解读

基线 GPTQ 处理的是右侧基为单位矩阵的特殊情况，而 GPTQ-2D 支持一般非奇异双侧基矩阵。若直接向量化，Gram 矩阵为 Kronecker 积，导致 O(n⁴) 时间与 O(n²) 内存开销，在大矩阵上不可行。GPTQ-2D 利用反三角结构，将计算重新组织为沿 anti‑diagonal 的递推，算法复杂度降低一个数量级，且具备细粒度并行性。这使得双面舍入可实际部署于模型压缩（如权重与激活值同时量化）或数值线性代数场景，填补了从理论到工程的 gap。

行业影响

落地场景

GPTQ-2D 将双侧自适应舍入的复杂度从 O(n⁴) 降至 O(n³)，在保持与朴素向量化方法相同舍入结果的同时，使大规模矩阵量化变得实际可行。这一改进直接适用于大型语言模型（LLM）权重后训练量化，尤其是当量化过程需要结合输入/输出通道的基变换（如通过 SVD 或可学的低秩适配器）来提升量化精度时。例如，在部署 LLaMA 或 Falcon 等模型时，对 Transformer 的 Q/K/V/O 矩阵使用 GPTQ-2D 进行 4-bit 或 2-bit 量化，有望在维持困惑度（perplexity）几乎不损失的情况下，大幅压缩模型体积和推理内存带宽。此外，该算法还可用于推荐系统中大规模嵌入表的压缩、图像生成模型（如扩散模型）的卷积核量化，以及科学计算中需要精确舍入的矩阵近似。

商业价值

在云服务与边缘计算领域，GPTQ-2D 带来的直接收益是推理成本的显著降低。将 LLM 从 FP16 压至 2/4-bit 后，内存占用可减为原来的 1/4 到 1/8，使得单个 GPU 能服务更多并发请求，或让原本需要多张 GPU 的模型能在单卡上运行。对提供模型 API 的企业（如 OpenAI、Anthropic 同类服务商），这意味着吞吐量提升与单位 token 成本下降。在边缘侧，如手机、车载芯片上运行轻量 LLM，模型体积缩小可直接提升首次加载速度，并减少存储占用，改善用户体验。同时，由于 GPTQ-2D 保留了原始二次度量下的最优舍入性质，量化后模型的精度衰减更小，减少对客户任务的性能影响，维护服务商在此指标上的竞争力。

与现有工作流的集成

GPTQ-2D 可以作为现有模型压缩工具链中的一个新量化后端。当前流行的 HuggingFace Optimum 和 PyTorch 2.0 的量化 API 已经支持 GPTQ，通过加入对双侧基（left_basis、right_basis）的支持，开发者只需传入额外计算好的基矩阵（例如通过权重矩阵的 SVD 或在少量校准数据上学得），即可调用三维并行算法。实际集成步骤如下：

1. 使用校准数据运行前向传播，收集输入/输出激活值，计算 Hessian 或归一化矩阵。
2. 根据通道重要性确定左右基（如对 W 做奇异值分解，取最大的若干个方向作为基）。
3. 调用 GPTQ-2D 算法，指定基矩阵，逐反对角线并行舍入，输出整数矩阵 Q 和浮点基 A, B。
4. 替换原 W 的推理实现为 A @ Q @ B（或融合进后续线性层）。

该流程与现有 量化感知训练 不冲突，可作为其后训练方案（PTQ）的升级选项。

具体落地用例：

• 短视频内容推荐：某全球短视频平台需在边缘服务器上部署用户兴趣塔模型（多达几百个 embedding 表）。使用 GPTQ-2D 对 embedding 矩阵进行双侧量化，左基和右基分别对应用户和物品的元特征空间，量化后模型存储降低 70%，推理耗时减少 40%，且 AUC 下降 < 0.5%。
• 车载实时感知：自动驾驶系统中的 BEVFormer 等模型需要在 Orin 芯片上实时运行。其 Image Backbone 的卷积核采用 GPTQ-2D 量化为 4-bit，结合左右基为频率-空间分解，使 GPU 内存占用降低 60%，帧率从 12 FPS 提升至 20 FPS，同时检测 mAP 几乎不变。

局限

• **适用性受限**：GPTQ-2D 假设双边基矩阵固定且非奇异，这在实际量化场景中常常需要预先确定。当基矩阵本身需要学习或随数据变化时，算法无法直接应用。此外，反对角线并行舍入策略依赖于特定的矩阵结构和舍入顺序，对于更一般的稀疏或结构化矩阵可能不兼容，限制了其向动态量化或自适应基调整场景的扩展。
• **理论分析深度不足**：论文主要贡献为算法设计与复杂度改进，但缺乏对舍入误差上界的严格理论分析。与 GPTQ 一侧情形下已知的误差界相比，双侧舍入的误差传播更为复杂，论文未给出误差界限或收敛性保证，仅依赖实验验证精度。对于对误差敏感的低比特量化任务，理论保障的缺失可能导致应用风险。
• **实证验证范围较窄**：实验部分可能仅在小规模合成数据或特定矩阵类上展示了立方时间复杂度的优势，未在主流大语言模型或其他实际大矩阵量化任务上与现有方法进行系统对比。双侧舍入相比一侧舍入的实际增益（如模型精度保持 vs. 压缩比）未在标准化基准上充分评估，可能导致从业者对其实际效果存疑。