量化-02-OBQ

Summary

OBQ是一种经典的训练后量化方法,其核心思想是通过调整未量化权重来补偿量化误差,以最小化输出误差。算法基于Hessian矩阵,逐行贪心地选择量化误差最小的权重进行量化,并更新其他权重以补偿误差。然而,OBQ的复杂度为O(d_out * d_in^3),在大规模模型中计算成本过高,这促使了后续GPTQ等更高效方法的出现。

因为GPTQ是基于OBQ改进的,所以我们这里先讲OBQ算法

OBQ算法

OBQ (Optimal Brain Quantization) 是在大模型量化领域非常经典的一种 PTQ(训练后量化)方法。它的核心思想源自于神经网络剪枝领域的 OBS (Optimal Brain Surgeon)。

OBQ 的底层哲学非常直观:当我们把某一个全精度权重压缩成低比特(引入了量化误差)时,我们可以通过调整同一层中其他尚未量化的权重,来“补偿”这个误差,从而使得最终输出的特征图(Feature Map)尽可能保持不变。

我们从目标函数开始一步步推导。


预备:维度定义

假设我们正在处理一个线性层(比如 o_proj 层),权重矩阵为 W∈ℝd_out×d_inW \in \mathbb{R}^{d\_{out} \times d\_{in}},输入激活值为 X∈ℝd_in×NX \in \mathbb{R}^{d\_{in} \times N}(NN 是 BatchSize ×\times SeqLen)。

  • 行(Row) →\rightarrow 输出通道(Output Channel, doutd_{out}):每一行对应一个独立的输出特征。
  • 列(Column) →\rightarrow 输入特征(Input Feature, dind_{in}):每一列对应前一层传过来的一个特征维度。
  • Hessian 矩阵 HH:H=XXT∈ℝdin×dinH = XX^T \in \mathbb{R}^{d_{in} \times d_{in}}。注意,Hessian 矩阵的维度只与列(输入特征 dind_{in})有关,与行(输出通道 doutd_{out})无关。

第一步:定义目标函数与 Hessian 矩阵

在逐层量化(Layer-wise Quantization)中,我们的目标是让量化后的权重矩阵 𝑾̂\hat{\mathbf{W}} 产生的输出,尽可能逼近原始权重矩阵 𝑾\mathbf{W} 的输出。假设输入激活值为 𝑿\mathbf{X},目标函数为最小化输出的平方误差:

E=12∥𝑾𝑿−𝑾̂𝑿∥22E = \frac{1}{2} \| \mathbf{W}\mathbf{X} - \hat{\mathbf{W}}\mathbf{X} \|_2^2(1)

因为在线性层中,权重矩阵的不同行(对应不同的输出通道)的计算是彼此独立的,我们可以将问题拆解为独立优化每一行。对于权重矩阵的某一行 𝒘∈ℝ1×din\mathbf{w}\in \mathbb{R}^{1 \times d_{in}},它包含 dind_{in} 个元素(对应 dind_{in} 个列),后续的索引 p,qp, q 指的都是该行内第几个元素,即列号。它的误差函数可以写为:

E=12∥𝒘𝑿−𝒘̂𝑿∥22=12(𝒘−𝒘̂)𝑿𝑿T(𝒘−𝒘̂)TE = \frac{1}{2} \| \mathbf{w}\mathbf{X} - \hat{\mathbf{w}}\mathbf{X} \|_2^2 = \frac{1}{2} (\mathbf{w} - \hat{\mathbf{w}}) \mathbf{X} \mathbf{X}^T (\mathbf{w} - \hat{\mathbf{w}})^T(2)

我们将误差对权重的二阶导数(Hessian 矩阵)记为 𝑯\mathbf{H}。在这个二次型中,Hessian 矩阵是一个常数矩阵:

𝑯=𝑿𝑿T\mathbf{H} = \mathbf{X}\mathbf{X}^T(3)

此时,我们的目标函数可以化简为标准的二次型形式:

E=12δ𝒘T𝑯δ𝒘E = \frac{1}{2} \delta \mathbf{w}^T \mathbf{H} \delta \mathbf{w}(4)

其中 δ𝒘=𝒘−𝒘̂\delta \mathbf{w} = \mathbf{w} - \hat{\mathbf{w}} 是权重发生的变化。


第二步:带约束的优化问题(引入拉格朗日乘子)

现在我们要量化第 pp 个权重 wpw_p,使其变为 ŵp=quant(wp)\hat{w}_p = \text{quant}(w_p)。

由于量化,第 pp 个权重发生了固定的变化,误差为 c=quant(wp)−wpc = \text{quant}(w_p) - w_p。

此时的问题变成了:在给定第 pp 个权重变化量为 cc 的约束下,如何调整整个权重向量 δ𝒘\delta \mathbf{w}(对未量化权重的更新),使得整体误差 EE 最小?

我们引入指示向量 𝒆p\mathbf{e}_p(第 pp 个元素为 1,其余为 0)。约束条件可以写为:

𝒆pTδ𝒘=c\mathbf{e}_p^T \delta \mathbf{w} = c(5)

使用拉格朗日乘数法构建目标函数 LL:

L(δ𝒘,λ)=12δ𝒘T𝑯δ𝒘+λ(𝒆pTδ𝒘−c)L(\delta \mathbf{w}, \lambda) = \frac{1}{2} \delta \mathbf{w}^T \mathbf{H} \delta \mathbf{w} + \lambda (\mathbf{e}_p^T \delta \mathbf{w} - c)(6)


第三步:求解最优权重更新公式(核心推导)

对 δ𝒘\delta \mathbf{w} 求偏导并令其为 0:

∂L∂δ𝒘=𝑯δ𝒘+λ𝒆p=0\frac{\partial L}{\partial \delta \mathbf{w}} = \mathbf{H} \delta \mathbf{w} + \lambda \mathbf{e}_p = 0(7)

左乘 𝑯−1\mathbf{H}^{-1},解出 δ𝒘\delta \mathbf{w}:

δ𝒘=−λ𝑯−1𝒆p\delta \mathbf{w} = -\lambda \mathbf{H}^{-1} \mathbf{e}_p(8)

这就是说,最优的权重更新方向与 Hessian 逆矩阵的第 pp 列成正比。接下来我们需要求出 λ\lambda。将上式代入我们的约束条件 𝒆pTδ𝒘=c\mathbf{e}_p^T \delta \mathbf{w} = c:

𝒆pT(−λ𝑯−1𝒆p)=c\mathbf{e}_p^T (-\lambda \mathbf{H}^{-1} \mathbf{e}_p) = c(9)

注意 𝒆pT𝑯−1𝒆p\mathbf{e}_p^T \mathbf{H}^{-1} \mathbf{e}_p 提取出的刚好是 𝑯−1\mathbf{H}^{-1} 对角线上的第 pp 个元素,记作 [𝑯−1]pp[\mathbf{H}^{-1}]_{pp}。于是:

−λ[𝑯−1]pp=c⟹λ=−c[𝑯−1]pp-\lambda [\mathbf{H}^{-1}]_{pp} = c \implies \lambda = -\frac{c}{[\mathbf{H}^{-1}]_{pp}}(10)

将 λ\lambda 代回 δ𝒘\delta \mathbf{w} 的公式中,得到最优权重更新公式:

δ𝒘=c[𝑯−1]pp𝑯−1𝒆p\delta \mathbf{w} = \frac{c}{[\mathbf{H}^{-1}]_{pp}} \mathbf{H}^{-1} \mathbf{e}_p(11)

(物理意义:当前 wpw_p 量化引入了 cc 的误差,我们通过 𝑯−1\mathbf{H}^{-1} 的第 pp 列按比例将其分摊给其他所有的权重。)


第四步:计算当前权重的量化敏感度(Saliency)

OBQ 是一个贪心算法,它需要决定先量化哪一个权重对整体误差影响最小。

我们将求得的最优 δ𝒘\delta \mathbf{w} 代回原始的误差公式 E=12δ𝒘T𝑯δ𝒘E = \frac{1}{2} \delta \mathbf{w}^T \mathbf{H} \delta \mathbf{w}:

Ep=12(−λ𝑯−1𝒆p)T𝑯(−λ𝑯−1𝒆p)E_p = \frac{1}{2} \left( -\lambda \mathbf{H}^{-1} \mathbf{e}_p \right)^T \mathbf{H} \left( -\lambda \mathbf{H}^{-1} \mathbf{e}_p \right)(12)

Ep=12λ2𝒆pT(𝑯−1)T𝑯𝑯−1𝒆pE_p = \frac{1}{2} \lambda^2 \mathbf{e}_p^T (\mathbf{H}^{-1})^T \mathbf{H} \mathbf{H}^{-1} \mathbf{e}_p(13)

因为 Hessian 及其逆矩阵是对称的,(𝑯−1)T𝑯𝑯−1=𝑯−1(\mathbf{H}^{-1})^T \mathbf{H} \mathbf{H}^{-1} = \mathbf{H}^{-1},所以:

Ep=12λ2𝒆pT𝑯−1𝒆p=12λ2[𝑯−1]ppE_p = \frac{1}{2} \lambda^2 \mathbf{e}_p^T \mathbf{H}^{-1} \mathbf{e}_p = \frac{1}{2} \lambda^2 [\mathbf{H}^{-1}]_{pp}(14)

将求得的 λ=−c[𝑯−1]pp\lambda = -\frac{c}{[\mathbf{H}^{-1}]_{pp}} 代入,得到误差(敏感度)公式:

Ep=c22[𝑯−1]pp=(quant(wp)−wp)22[𝑯−1]ppE_p = \frac{c^2}{2 [\mathbf{H}^{-1}]_{pp}} = \frac{(\text{quant}(w_p) - w_p)^2}{2 [\mathbf{H}^{-1}]_{pp}}(15)

(物理意义:误差大小不仅取决于量化前后的绝对差值平方,还与该权重在 Hessian 逆矩阵对角线上的值成反比。)


第五步:Hessian 逆矩阵的更新(避免重复求逆)

当第 pp 个权重被量化固定后,它就不再参与后续的补偿更新了。这意味着在下一步中,我们需要在剩下的维度上求解。

幸运的是,我们不需要对剩下的 (d−1)×(d−1)(d-1) \times (d-1) 矩阵重新求逆。利用高斯消元(或矩阵分块求逆的性质),可以用 O(d2)O(d^2) 的复杂度直接更新当前的逆矩阵:

[𝑯new−1]ij=[𝑯−1]ij−[𝑯−1]ip[𝑯−1]pj[𝑯−1]pp[\mathbf{H}^{-1}_{new}]_{ij} = [\mathbf{H}^{-1}]_{ij} - \frac{[\mathbf{H}^{-1}]_{ip} [\mathbf{H}^{-1}]_{pj}}{[\mathbf{H}^{-1}]_{pp}}(16)

这一步在代码中通常表示为从 𝑯−1\mathbf{H}^{-1} 中去除第 pp 行和第 pp 列的影响。


完整计算流程总结

对于权重矩阵的一行 𝒘\mathbf{w}(长度为 dind_{in}):

  1. 初始化:传入校准数据集,计算 𝑯=𝑿𝑿T\mathbf{H} = \mathbf{X}\mathbf{X}^T。

  2. 求逆:对 Hessian 矩阵加上一个极小的阻尼项(防止奇异)并求逆:𝑯−1=(𝑯+ϵ𝑰)−1\mathbf{H}^{-1} = (\mathbf{H} + \epsilon \mathbf{I})^{-1}。

  3. 循环量化(执行 dind_{in} 次):

    • (a) 贪心选择:遍历所有尚未量化的权重 pp,计算其量化误差 Ep=(quant(wp)−wp)22[𝑯−1]ppE_p = \frac{(\text{quant}(w_p) - w_p)^2}{2 [\mathbf{H}^{-1}]_{pp}}。找出令 EpE_p 最小的索引 qq。
    • (b) 执行量化:将 wqw_q 量化为 ŵq\hat{w}_q。
    • (c) 补偿更新:计算误差 c=ŵq−wqc = \hat{w}_q - w_q,对所有剩下未量化的权重执行更新:𝒘←𝒘+c[𝑯−1]qq𝑯:,q−1\mathbf{w} \leftarrow \mathbf{w} + \frac{c}{[\mathbf{H}^{-1}]_{qq}} \mathbf{H}^{-1}_{:, q}。
    • (d) 矩阵更新:使用高斯消元公式更新 𝑯−1\mathbf{H}^{-1},去除第 qq 个维度的影响。

复杂度分析与工程痛点

假设权重矩阵的大小是 𝑾∈ℝdout×din\mathbf{W} \in \mathbb{R}^{d_{out} \times d_{in}}:

  1. 计算初始 Hessian 逆矩阵:需要 O(din3)O(d_{in}^3)。
  2. 贪心选择与更新:每次选择需要 O(din)O(d_{in}),更新权重需要 O(din)O(d_{in}),更新 Hessian 逆矩阵需要 O(din2)O(d_{in}^2)。因为要量化 dind_{in} 个权重,所以这一步的复杂度是 O(din⋅din2)=O(din3)O(d_{in} \cdot d_{in}^2) = O(d_{in}^3)。
  3. 最致命的问题(Row-wise 依赖):由于 OBQ 是贪心选择,每一行权重的数值不同,导致每一行选出来的量化顺序完全不同。这意味着你不能在 doutd_{out} 个通道之间共享 Hessian 逆矩阵的更新过程。你必须为每一行维护一个单独的 𝑯−1\mathbf{H}^{-1} 并独立进行上述循环。

最终总复杂度:O(dout⋅din3)O(d_{out} \cdot d_{in}^3)

在实际的大模型推理基建(如部署支持大规模并行计算的 sglang, TensorRT-LLM 架构)中,当我们面对像 Qwen 这样规模的模型,比如 din=4096,dout=4096d_{in} = 4096, d_{out} = 4096,哪怕是一个线性层,O(dout⋅din3)O(d_{out} \cdot d_{in}^3) 的复杂度也是无法忍受的(校准阶段耗时按天计算)。

这正是为什么后来会诞生 GPTQ——它对 OBQ 做了巧妙的近似,从而大幅降低了复杂度。GPTQ 破除这种行依赖,将复杂度降到 O(dout⋅din2)O(d_{out} \cdot d_{in}^2)

Join the discussion Powered by GitHub Discussions