Binary Quadratic Quantization: Beyond First-Order Quantization for Real-Valued Matrix Compression¶

会议: NeurIPS 2025
arXiv: 2510.18650
代码: 待确认
领域: 模型压缩 / 量化
关键词: 二值量化, 二次编码, 混合整数规划, ViT压缩, 极低位宽

一句话总结¶

BQQ 提出二次二值量化——用二值矩阵的乘积（而非线性组合）表示权重矩阵，突破传统一阶量化的表达能力限制，通过扩展 AMFD（退火均场下降）到 PUBO 问题求解混合整数优化，在 2-bit 无数据 ViT 量化上实现从 10.83% 到 58.25% 的准确率飞跃。

领域现状：传统量化（均匀量化、二值编码 BCQ）使用二值矩阵的线性组合 \(W \approx \sum_i \alpha_i B_i\)，属于一阶量化。极低位宽（2-bit）下表达能力严重不足。

现有痛点：BCQ 在 2-bit 无数据量化 DeiT-S 上仅 10.83% 准确率（接近随机），因为线性组合只能覆盖矩阵空间的有限子集。增加二值矩阵数量只能线性提高表达力。

核心矛盾：极压缩条件下存储预算极有限，线性组合的表达能力增长太慢——\(k\) 个二值矩阵只覆盖 \(O(k)\) 的信息。需要在同样存储下获得更强的表达能力。

本文目标 设计一种超越线性组合的二值量化方案，在相同存储预算下获得更高的重建精度。

切入角度：用二值矩阵的乘积（二次项）替代线性组合——\(Y_i Z_i\) 的乘积在相同存储下提供指数级更多的组合可能性。

核心 idea：用 \(W \approx \sum_i (r_i Y_i Z_i + s_i Y_i \mathbb{1} + t_i \mathbb{1} Z_i) + u\mathbb{1}\) 的二次二值表示替代线性二值编码，通过 PUBO 优化求解。

输入权重矩阵 \(W\) → 贪心逐项分解 → 每项求解一个 PUBO（多项式无约束二值优化）子问题 → 用扩展 AMFD 的连续松弛+温度退火求解 → 阶跃函数二值化 → 闭式求解缩放系数 → 残差传播到下一项

二次二值表示（BQQ Representation）:
- 功能：用二值矩阵乘积表示权重
- 核心思路：\(W \approx \sum_i (r_i Y_i Z_i + s_i Y_i \mathbf{1}_Z + t_i \mathbf{1}_Y Z_i) + u\mathbf{1}\)，其中 \(Y_i \in \{0,1\}^{m \times l}\)，\(Z_i \in \{0,1\}^{l \times n}\)
- 设计动机：\(Y_i Z_i\) 的乘积在 \(l\) 维中间维度上生成 \(m \times n\) 矩阵，组合可能性为 \(2^{m \cdot l + l \cdot n}\)，远超线性组合的 \(2^{m \cdot n}\)（当 \(l\) 选取合理时）。额外的交叉项 \(Y_i \mathbf{1}\) 和 \(\mathbf{1} Z_i\) 处理行/列偏移
PUBO 求解（扩展 AMFD）:
- 功能：求解每个子问题的二值矩阵 \(Y_i, Z_i\)
- 核心思路：将离散优化松弛为连续优化——\(x_k \in [0,1]\) 代表二值变量的概率。目标变为最小化 \(KL(P_{MF} \| P_C)\)。温度退火从 \(T=0.2\) 降到 \(T=0.005\) 经过 50000 步，逐步逼近离散解
- 设计动机：AMFD 原本只处理 QUBO（二次），本文扩展到 PUBO（多项式）以处理 \(Y_i Z_i\) 这样的二值矩阵乘积项
缩放系数闭式解:
- 功能：固定二值矩阵后最优化缩放系数 \(r_i, s_i, t_i, u\)
- 核心思路：构建 Hessian 矩阵求逆得到闭式解（Algorithm 2, Eq. 10），计算量极小
- 设计动机：将非凸混合整数问题分解为"二值变量用 AMFD"+"连续系数用闭式解"的交替优化

模型	方法	无数据 2-bit	有校准 2-bit
DeiT-S	BCQ	10.83%	60.13%
DeiT-S	BQQ	58.25%	69.41%
DeiT-B	BCQ	12.99%	—
DeiT-B	BQQ	72.09%	—