Structured Transforms for Low-Overhead Quantization of Language Models¶

会议: NeurIPS 2026
arXiv: 2609.11687
OpenReview: https://openreview.net/forum?id=UrdhHjjT3j
领域: 模型压缩
关键词: 训练后量化, 大语言模型, Kashin分解, 离散余弦变换, 贪心算法

一句话总结¶

本文提出基于符号随机化离散余弦变换（DCT）的交替贪心 Kashin 分解算法，以 $\mathcal{O}(N \log N)$ 复杂度将 LLM 权重拆解为两个具备对称四峰分布的有界低范数因子，并通过解析聚类中心消除多重重启 $k$-means，在 4-bit 权重量化下兼顾极佳的吞吐伸缩性与极高数值稳定性。

研究背景与动机¶

现代大语言模型参数体量庞大，在推理阶段带来了沉重的显存带宽与占用开销。训练后量化（PTQ）无需高昂的全参数微调即可直接压缩模型，是工业落地的首选技术路线。然而，随着位宽压缩至 4-bit 甚至更低，传统的均匀标量量化极易受到激活与权重中离群值（outliers）的冲击导致精度崩溃；基于二阶误差补偿的 OPTQ 以及引入正交旋转的 QuIP、QuIP# 等方案，虽然能够缓解不相干性（incoherence）问题，但在面临特殊结构或病态 Hessian 矩阵时极易出现数值不稳定。另一方面，向量量化（VQ）方案（如 AQLM、QTIP）虽在低比特取得优异指标，却依赖额外的可学习码本存储与梯度微调，且无法良好适配硬件底层的标量反量化计算。

利用数学上的 Kashin 分解（Kashin Decomposition）将稠密权重向量分解为两个无穷范数严格受限的分量，天然契合神经网络低比特量化压制离群值的需求。早期探索（Merkulov et al., 2024）发现贪心 Kashin 分解能诱导出利于 2-bit 聚类的四峰分布，但在实际应用中暴露出三大致命瓶颈：其一，为了降低复杂度而采取的矩阵化松弛破坏了原定理的逐向量收敛保证，导致部分网络层迭代发散；其二，经验上的四峰分布难以稳定复现，两因子的联合分布极易坍塌；其三，聚类严重依赖多重随机初始化的 $k$-means 搜索（通常需重启 50 次），占据了绝大部分量化耗时，且显式随机正交矩阵存储与计算开销高达 $\mathcal{O}(N^2)$。

为了彻底释放 Kashin 分解在 LLM 压缩中的理论与工程潜力，本文重新回到具备严格收敛证明的逐向量分析框架，旨在用结构化快速变换替代密集随机旋转，并在算法层面保证模式可分与解析初始化。核心 idea：利用基于符号随机化 DCT-II 的快速正交算子替代密集矩阵，将单步复杂度降至 $\mathcal{O}(N \log N)$，并设计固定四步交替更新的贪心调度算法，在理论上证明残差几何收敛的同时，严格诱导两因子的对称四峰分布，从而实现聚类中心的解析闭式初值计算并彻底移除多重启 $k$-means 开销。

方法详解¶

整体框架¶

本文构建的训练后量化流程采用自适应逐列（或分块）推进架构。对于给定的层权重矩阵，算法逐列提取权重向量，通过符号随机化 DCT 构建的正交算子进行交替块贪心分解，将其拆分为两个在无穷范数上严格有界的因子向量 $u$ 与 $\hat{v}$；随后利用两步残差解析导出的闭式中心快速完成 2-bit 标量聚类，将双因子离散化为硬件友好的 2-bit 编码并存入因子矩阵；最后借鉴 OPTQ 机制利用二阶逆 Hessian 信息对未量化列实施误差补偿，循环直至整层完成。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入待量化权重列 x 与校准 Hessian"] --> B["符号随机化 DCT 正交算子构建"]
    B --> C["交替块贪心分解调度<br/>4 步循环交替更新 u 与 v^"]
    C --> D["解析闭式聚类中心初值计算<br/>±c1 ± c2 直接命中四峰峰位"]
    D --> E["双因子 2-bit 标量聚类量化"]
    E --> F["二阶误差补偿更新未量化列"]
    F -->|下一列直至全层完成| G["输出双因子 2-bit 权重矩阵 U 与 V^"]

关键设计¶

1. 符号随机化 DCT 正交算子构建：彻底消除 $\mathcal{O}(N^2)$ 存储与计算瓶颈 针对经典 Kashin 定理依赖密集随机正交矩阵 $P \in \mathbb{O}^N$、单步乘法计算复杂度 $\mathcal{O}(N^2)$ 且需显式驻留矩阵的问题，本文基于 Kashin et al. (2025) 的最新正交基理论，选取标准正交离散余弦变换（orthonormal DCT-II，满足 $P_{\mathrm{IDCT}} = P_{\mathrm{DCT}}^\top$ 且基向量满足 $\|\phi_j\|_\infty \leqslant \sqrt{2/N}$），构建紧致正交算子： $$Pz := \mathrm{IDCT}(\varepsilon \odot \mathrm{DCT}(z))$$ 其中 $\varepsilon \in \{-1, +1\}^N$ 为层内共享的随机符号掩码。该算子具备对称对合性（symmetric involution，即 $P^\top = P$ 且 $P^2 = I$）。借由快速傅里叶算法体系下的快速余弦变换，正交映射的计算复杂度从 $\mathcal{O}(N^2)$ 骤降至 $\mathcal{O}(N \log N)$，且无需显式在显存中存储任何稠密正交参数矩阵，仅需保留一个随机符号种子即可在推理或量化时动态恢复。

2. 交替块贪心分解调度：理论收敛与稳定四峰形态的双重保证 早期矩阵松弛方案因破坏逐向量范数约束而导致优化发散，而纯全局贪心选择又无法稳定产生四峰边缘分布。本文设计了以 4 个原子步为基本周期（block）的交替贪心算法（Algorithm 1）。在每个周期内，算法强制执行固定调度：前 2 步仅从超立方体顶点集合 $Q_N$ 中选择基向量更新因子 $u$，后 2 步则强制从变换后集合 $U_{\mathcal{E},\Phi} Q_N$ 中选择基向量更新因子 $\hat{v}$： $$\Delta u \leftarrow \mathrm{sign}(\rho) \cdot \frac{\|\rho\|_1}{N}, \quad \Delta \hat{v} \leftarrow \mathrm{sign}(P\rho) \cdot \frac{\|P\rho\|_1}{N}$$ 理论证明表明，尽管固定更新次序相比无约束全局最优贪心存在收敛速率的微弱常数衰减（单周期残差收缩因子为 $(1 - \beta(N))^{1/2}$，其中 $\beta(N) = \alpha^2(N)/36$），但其几何残差衰减依然成立，且两因子的无穷范数严格收敛在 $\mathcal{O}(\frac{(\log N)^2 (\log \log N)^{12}}{\sqrt{N}})$ 上限内。更重要的是，这种两两配对的更新模式在因子的边缘分布上强制生成了四个对称尖锐的模态，彻底消除了联合分布坍塌与第二因子单峰退化现象。

3. 解析闭式聚类中心初值计算：移除多重启 $k$-means 搜索开销 在原先的 Kashin 量化流程中，两因子的 2-bit 聚类依赖高达 50 次随机重启的 $k$-means 算法，占据了整体量化耗时的绝大部分。本文揭示了交替贪心迭代的核心代数特性：在前两步贪心更新中，更新增量严格具有 $\pm c_k(r_k) = \pm \frac{\|r_k\|_1}{N}$ 的形式。因此，经历两次原子更新后，因子边缘分布的主导峰值坐标在数学上严格精确落于解析点： $$\pm c_1 \pm c_2 = \pm \frac{\|r_0\|_1}{N} \pm \frac{\|r_1\|_1}{N}$$ 由于贪心残差随步数迅速几何衰减，后续高阶微小扰动无法偏移该峰位骨架。本文直接将 $\pm c_1 \pm c_2$ 计算出的 4 个解析标量作为 $k$-means 的初始聚类中心，仅需运行极少轮局部微调即可收敛，完全剔除了外层随机多重启循环，将聚类耗时降低达 10 倍。

损失函数 / 训练策略¶

量化过程采用逐层二阶误差补偿策略，不引入任何可训练参数反向传播。以 WikiText-2 校准集（1000 条长度 2048 的样本序列）计算层输入的经验 Hessian 矩阵 $H = X^\top X$。在逐列完成 Kashin 分解与 2-bit 四峰量化后，生成量化误差向量 $W_{:,i} - Q_{:,i}$，并利用逆 Hessian 矩阵的第 $i$ 列切片对后续未量化权重列执行一阶纠偏更新： $$W_{:, i+1:} \leftarrow W_{:, i+1:} - \frac{W_{:, i} - Q_{:, i}}{[H^{-1}]_{ii}} [H^{-1}]_{i, i+1:}$$ 该管线深度契合 JAX 的编译优化与多 GPU pmap 算子并行机制，保证了自适应量化在大规模模型上的高吞吐执行。

实验关键数据¶

主实验¶

在 4-bit per-output-channel 预算下，测试 OPT、Llama-2 及 Pythia 系列在 WikiText-2 与 C4 语言建模困惑度（PPL，越低越好）以及零样本常识问答任务（HellaSwag、PiQA、Winogrande 准确率，越高越好）上的综合表现。

模型	方法	WikiText-2 (PPL) ↓	C4 (PPL) ↓	HellaSwag (%) ↑	PiQA (%) ↑	Winogrande (%) ↑
OPT-1.3B	FP16 基准	16.47	39.41	41.36	71.00	59.75
	RTN	29.46	73.25	34.31	67.52	53.59
	OPTQ	17.63 ± 0.01	42.45 ± 0.17	40.46 ± 0.14	70.51 ± 0.28	58.51 ± 0.40
	QuIP# (无微调/VQ)	17.83 ± 0.11	42.75 ± 0.36	40.53 ± 0.12	70.19 ± 0.48	58.09 ± 1.10
	Kashin-DCT+H (本文)	17.19 ± 0.02	41.12 ± 0.02	40.59 ± 0.12	70.68 ± 0.28	58.32 ± 0.13
Llama-2-7B	FP16 基准	9.20	19.40	76.14	78.73	69.46
	RTN	10.56	22.78	74.43	78.56	68.75
	OPTQ	9.80 ± 0.01	21.30 ± 0.06	74.79 ± 0.13	77.82 ± 0.27	68.25 ± 0.51
	QuIP (LDLQ)	48.30† ± 29.84	133.00† ± 83.57	48.10† ± 9.88	68.41† ± 3.99	57.06† ± 3.42
	QuIP# (无微调/VQ)	9.47 ± 0.01	20.16 ± 0.13	74.98 ± 0.08	78.49 ± 0.14	69.32 ± 0.43
	Kashin-DCT+H (本文)	9.60 ± 0.02	20.36 ± 0.03	75.04 ± 0.16	78.24 ± 0.11	69.27 ± 0.87
Llama-2-13B	FP16 基准	8.11	17.59	79.64	80.36	72.53
	OPTQ	8.48 ± 0.00	18.59 ± 0.08	78.27 ± 0.34	80.11 ± 0.28	71.64 ± 0.59
	QuIP# (无微调/VQ)	8.31 ± 0.00	18.19 ± 0.01	78.86 ± 0.09	80.16 ± 0.16	72.43 ± 0.18
	Kashin-DCT+H (本文)	8.37 ± 0.01	18.19 ± 0.01	78.90 ± 0.23	80.12 ± 0.17	72.53 ± 0.21

消融实验¶

针对重度异常值及 Hessian 极度病态的模型配置（Pythia-6.9B 与 Mistral-7B v0.1）进行极限鲁棒性压力测试，以验证有界 $\ell_\infty$ 因子分解与自适应码本相对固定网格量化的结构性优势。

模型与评估场景	配置 / 方法	Wiki-2 (PPL) ↓	C4 (PPL) ↓	HellaSwag (%) ↑	状态说明
Mistral-7B v0.1	FP16 基准	8.63	21.42	81.23	浮点金标
(SwiGLU 离群值致 Hessian 病态)	GPTQ / OPTQ	379.73 ± 15.71	1948.81 ± 542.4	31.68 ± 0.86	误差纠偏严重跑出网格，精度崩溃
	QuIP 系列 (LDLQ/Hadamard)	Aborted (NaN)	Aborted (NaN)	—	Cholesky 因子对角近零导致回代溢出崩溃
	Kashin-DCT+K (Kronecker)	8.95 ± 0.01	22.26 ± 0.01	79.99 ± 0.15	完美收敛，仅微增 0.32 PPL
	Kashin-DCT+H (Hadamard)	8.92 ± 0.01	22.21 ± 0.01	80.09 ± 0.01	极度稳定，接近无损压缩 (+0.29 PPL)
Pythia-6.9B	FP16 基准	11.41	30.11	63.87	浮点金标
(不相干预处理不稳定)	QuIP (LDLQ)	2486.39 ± 569.0	8605.29 ± 2456.1	34.01 ± 1.56	严重发散，模型完全破坏
	QuIP# (无微调/VQ)	324.93 ± 47.63	799.77 ± 96.96	41.13 ± 0.48	困惑度暴涨至三位数
	OPTQ	12.02 ± 0.00	32.06 ± 0.02	62.95 ± 0.32	维持在基准附近
	Kashin-DCT+H (本文)	20.64 ± 1.63	49.91 ± 3.13	58.66 ± 0.47	比 QuIP# 好一个数量级以上

关键发现¶

对病态离群值的极致抗性：在 Mistral-7B 这种因 SwiGLU 模块引发极端通道异常值的网络层上，QuIP 体系因逆矩阵与 LDL 分解除零而彻底报 NaN 崩溃，OPTQ 亦因更新残差甩出量化截断边界而恶化至近 380 PPL；Kashin-DCT 凭借两因子解析中心自适应跟随残差尺度（$\pm c_1 \pm c_2 \propto \|r_k\|_1 / N$）的有界分解特性，在无需任何特殊手工调优下保持了坚若磐石的数值稳定性，PPL 距 FP16 仅有 0.29 的极微差距。
算力扩展壁垒打破：在单卡 NVIDIA H100 上的耗时统计表明，从 Llama-2-7B 扩展至 13B 时，参数量激增约 1.9 倍，OPTQ 和 QuIP# 的量化耗时分别膨胀了 1.90 倍和 1.70 倍，而 Kashin-DCT+H 的端到端耗时仅轻微上浮 18%（从 1313.6s 增至 1544.9s），体现出在大参数量尺度下极为平缓的耗时增长优势。

亮点与洞察¶

正交算子的轻量化创新：巧妙利用符号随机化 DCT-II 的正交对合特性（$P^\top = P$ 且 $P^2 = I$），不仅在量化阶段将单次正交变换压入 $\mathcal{O}(N \log N)$，更在推理阶段推导出折叠等式 $XW = [X \mid XP] [U^\top, \hat{V}^\top]^\top$，使得激活变换开销远小于矩阵乘法本身。
理论结构直接反哺离散工程：算法设计的精妙之处在于没有把贪心步数随意堆叠，而是约束为前 2 步在原域、后 2 步在频域的正交循环，直接在代数上锁定了峰值位置的解析公式 $\pm c_1 \pm c_2$，一举消除了最耗时的多重重启聚类瓶颈。
硬件友好的原生 2-bit 映射潜力：该分解把 4-bit 权重量化解耦成两个独立的 2-bit 码本通道，在支持原生 INT2/FP4 的现代硬件加速器上，天然契合寄存器打包和无共享访存冲突的连续寻址，避免了带非零偏移 4-bit 反量化带来的 cross-lane 数据重排。

局限与展望¶

作者指出的局限：当前实验重点评估无监督标量 PTQ 设定，未涵盖集成可学习旋转的激活感知算法（如 SpinQuant、QuaRot）以及依赖复杂微调的网格/格点向量量化（如 QuIP# 的完整版 E8 格点、QTIP）。
实验与工程层面的局限：当前推理阶段主要依赖加载时重建浮点权重或模拟验证，尚未在底层 CUDA/Triton 中实现深度融合的低延迟 2-bit GEMM + 共享掩码 DCT 专用算子，端到端实际加速比尚未完全展现。
未来改进方向：可进一步将 Kashin 双因子结构与可学习正交预处理相结合扩展至权活联合量化，或在每个因子内部引入小型向量码本，向 2-bit 以下极致压缩空间探索。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 巧妙结合现代泛函分析中的 Kashin 快速定理与 LLM 量化工程，推导出解析聚类初值并实现无损复杂度缩减。
实验充分度: ⭐⭐⭐⭐⭐ 涵盖多主流模型族在语言建模、零样本评测以及两类极端恶劣病态场景的全面验证，方差与失败分析极度详实。
写作质量: ⭐⭐⭐⭐⭐ 理论推导清晰严谨，从引理命题到工程落地的脉络连贯透彻，图表表现力与问题定位极佳。
价值: ⭐⭐⭐⭐⭐ 为超大规模模型低比特鲁棒量化与下一代原生 2-bit 硬件加速提供了极具说服力的算法范式。