💻 computer science

Entropy-Constrained Adaptive Stochastic Quantization

本文引入了熵约束自适应随机量化（ECASQ），这是一种通过在熵和无偏性约束下联合优化自适应量化值以最小化均方误差的新型框架，该框架既提供了最优的动态规划解，也提供了一种具有强理论保证且高效、对 GPU 友好的近似方案。

原作者： Ran Ben Basat, Yaniv Ben-Itzhak, Michael Mitzenmacher, Shay Vargaftik

发布于 2026-08-20

📖 1 分钟阅读☕ 轻松阅读

原作者： Ran Ben Basat, Yaniv Ben-Itzhak, Michael Mitzenmacher, Shay Vargaftik

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

在现代计算领域，机器正不断尝试从海量数据中学习。为此，它们进行着数十亿次的计算，在内存芯片和处理器之间来回移动数字。这些数字通常以极高的精度存储，就像一张拥有所有可能灰色调的照片。然而，这种高精度代价高昂：它需要大量的内存，并在网络中造成瓶颈，从而减慢了整个学习过程。为了解决这个问题，工程师们使用了一种称为“量化”（quantization）的技术。可以将它想象成将复杂的图像简化为有限的调色板。系统不再保留每一个微小的色调，而是将每个数字舍入到预定义的小列表中最近的值。这使得数据变得更小，传输也更快。但问题在于，如果只是简单地将数字舍入到最近的值，就会引入误差，这些误差可能会累积并破坏机器的学习能力。为了防止这种情况，研究人员使用了一种称为“随机量化”（stochastic quantization）的方法，它增加了一层随机性。系统不再总是向上或向下舍入，而是根据数值距离两个可用选项的远近来“掷硬币”。这确保了即使单个数字不完全准确，但在平均意义上，舍入后的数字是完美准确的。

VMware Research、伦敦大学学院和哈佛大学的研究人员最近面临的挑战是，当数据即将被进一步压缩时，如何让这种舍入过程变得更加智能。在许多实际系统中，在数字经过舍入后，会使用无损编码器进行压缩，类似于 ZIP 文件的压缩方式。这种编码器会为出现频繁的值分配较短的代码，为稀有值分配较长的代码。其目标是最小化数据的总大小。以往的舍入方法在最小化误差方面表现出色，但它们忽略了某些舍入值会比其他值更常见这一事实，从而导致压缩效率低下。而其他试图优化压缩大小的方法则往往牺牲了至关重要的“无偏性”（unbiased）属性，这意味着舍入后数字的平均值会偏离真实平均值，导致机器学习模型失效。研究人员致力于寻找一种能够同时实现这两个目标的方法：选择最佳的舍入值以最小化误差，同时确保生成的数据能够尽可能高效地压缩，且不丢失那至关重要的统计准确性。

该团队开发了一种名为“熵约束自适应随机量化”（Entropy-Constrained Adaptive Stochastic Quantization）的新方法。他们将这个问题视为一个复杂的拼图，必须选择一组特定的值来代表数据。规则非常严格：这组值的集合必须足够小以保持系统运行速度；舍入后数字的平均值必须与原始数字完全匹配；并且生成的数值模式必须能在特定的尺寸限制内实现可压缩性。为了解决这个问题，他们创建了一种精密的数学策略，其运作方式就像一位仔细的探险家在绘制地形图。他们构建了一个系统，该系统可以观察数据并决定确切使用哪些值，在准确性需求与文件大小需求之间取得平衡。他们证明了其方法可以找到该问题的绝对最优解，但实现这一目标需要大量的计算内存和时间，因此对于超大规模数据集来说并不实用。

为了使该解决方案在现实世界中可用，研究人员还设计了一个更快的近似版本。这个版本牺牲了一点点理论上的完美性，以换取巨大的速度和效率提升。它的工作原理是对数据的行为做一个稍微简单的假设，这使得它可以在现代计算机使用的标准图形处理器（GPU）上运行。他们展示了这种快速方法产生的结果几乎与完美解一样好，但运行速度快了数十倍。在测试中，他们发现这种新方法在处理压缩数据时的误差显著低于现有技术，同时保持了较小的文件体积。他们还发现，通过运行他们的快速近似算法，然后对数值进行一些细微且有针对性的调整，可以得到与缓慢的完美解几乎无法区分的结果，而耗费的时间却极短。

研究人员谨慎地指出，他们的方法并非依靠魔法或猜测。这是一个严谨的数学过程，保证了数据在平均意义上保持准确。他们还探讨了结合两种不同舍入策略是否能产生更好的结果，这种技术被称为“时间共享”（time-sharing）。他们的分析表明，虽然这在某些非常特定的边缘情况下理论上可能有帮助，但他们开发的单一优化策略对于几乎所有的实际情况都是足够的。这项工作为任何构建大规模机器学习系统的人提供了一个全新的、高效的工具。通过解决如何同时实现准确性和压缩性的舍入问题，该团队为在有限硬件上训练和部署强大的人工智能模型扫清了一个重大障碍。其结果是一个能够处理更多数据、移动更快、学习更有效的系统，且无需对底层硬件进行根本性的改变。

技术摘要：熵约束自适应随机量化 (ECASQ)

1. 问题定义

本文解决了现有量化方法在现代机器学习工作负载中的局限性，特别是关于无偏性 (unbiasedness)、自适应性 (adaptivity) 与熵效率 (entropy efficiency) 之间的权衡问题。

背景： 自适应随机量化 (ASQ) 在保持无偏性 ( $E[\hat{X}] = X$ ) 的同时，优化给定输入的均方误差 (MSE)。然而，标准的 ASQ 在选择量化值时并未考虑后续的无损熵编码阶段，而该阶段会为高频值分配较短的比特串。
差距： 现有的熵感知方法（如熵约束矢量量化）不强制执行无偏性，而无偏方法（如 QSGD、ASQ）通常是非自适应的，或者忽略了熵约束。
ECASQ 问题： 作者提出了熵约束自适应随机量化 (ECASQ) 问题。给定输入向量 $X \in \mathbb{R}^d$ $X \in R^{d}$ 、允许的字母表 $P$ $P$ 、最大码本大小 $s$ $s$ 以及熵预算 $b$ $b$ ，目标是选择一个码本 $Q \subseteq P$ $Q \subseteq P$ ( $|Q| \le s$ $∣ Q ∣ \leq s$ )，在满足以下条件的同时最小化 MSE：
1. 无偏性： $E[\hat{X}] = X$ 。
2. 熵约束： 平均分量熵 $H(\hat{X}) \le b$ 。

2. 方法论

2.1 拉格朗日松弛 (Lagrangian Relaxation)

作者通过引入拉格朗日乘子 $\lambda \ge 0$ ，将硬约束问题转化为最小化：
$\text{MSE}(Q, X) + \lambda \cdot H(\hat{X})$
目标是在满足 $|Q| \le s$ 和无偏性的条件下。通过改变 $\lambda$ ，可以追踪 MSE 与熵之间的帕累托最优 (Pareto-optimal) 权衡曲线。论文指出，由于问题的离散性质，单个 $\lambda$ 可能无法精确达到熵预算 $b$ ，但通过双向时间共享 (two-way time-sharing)（在输入的随机划分上运行两个量化器），可以实现对任何 $b$ 的最优解的恢复。

2.2 最优动态规划 (DP)

标准的 ASQ DP 无法扩展到 ECASQ，因为量化值的熵取决于其左侧和右侧的邻居，这使得代价函数不再具有可分性。

状态定义： 作者定义了一个新的 DP 状态 $dp_{OPT}(i, \ell, j)$ ，表示使用 $i-1$ 个量化值（包括 $x_\ell$ ）量化前 $\ell$ 个条目的最小代价，外加假设 $x_\ell$ 和 $x_j$ 为连续量化值的区间 $[x_\ell, x_j]$ 的 MSE。
复杂度： 直接实现需要 $O(d^3 s)$ 的时间复杂度和 $O(d^2 s)$ 的空间复杂度。
加速手段：
- SMAWK 算法： 利用代价矩阵的四边形不等式（Monge 性质）在 $O(d)$ 时间内寻找行最小值，从而将时间复杂度降至 $O(d^2 s)$ 。
- Hirschberg 算法： 通过采用分治策略（仅存储 DP 表的两层），将空间复杂度降低至 $O(d^2)$ 。
泛化： 该算法可扩展到任意规模为 $p$ 的允许集合 $P$ ，时间复杂度为 $O(p^2 s + d)$ ，空间复杂度为 $O(p^2 + d)$ 。

2.3 高效空间近似算法

为了处理输入规模和允许集合较大（导致 $O(d^2)$ 空间不可行）的情况，作者提出了一种近似方法，该方法优化的是替代熵度量 $H(I, B)$ （区间索引与舍入比特的联合熵），而非精确的输出熵 $H(\hat{X})$ 。

保证： 该方案满足 $H(\hat{X}) \le H(I, B) \le H(\hat{X}) + 1$ 。因此，具有熵预算 $b$ 的近似解所产生的 MSE 不会大于预算为 $b-1$ 的最优解。
复杂度： 该方法将空间降低至 $O(d)$ （对于一般集合 $P$ 为 $O(p+d)$ ），同时保持 $O(d^2 s)$ 的时间复杂度。它被设计为对 GPU 友好。

2.4 迭代精炼 (Iterative Refinement)

为了弥补近似解与最优解之间的精度差距，作者引入了一种精炼程序。从近似解开始，通过在局部区间内进行二分查找，并行地优化量化值的子集 ( $Q_0, Q_1, Q_2$ )。该过程保持了无偏性，并且通常能在几次迭代内收敛到接近最优的结果。

3. 核心贡献

问题建模： 定义了 ECASQ，这是第一个同时优化 MSE、无偏性和熵约束的自适应随机量化框架。
最优算法： 开发了一个利用 SMAWK 和 Hirschberg 技术的 $O(d^2 s)$ 时间、 $O(d^2)$ 空间的动态规划算法，用于求解精确解。
带保证的近似法： 提出了一种空间高效 ( $O(d)$ ) 的近似算法，并具有可证明的界限：其 MSE 被限制在比熵减少一个比特的最优解之内。
精炼策略： 引入了一种快速、可并行的迭代精炼方法，能以显著更低的计算成本实现接近最优的精度。
理论完备性： 证明了通过时间共享，拉格朗日松弛可以恢复任何熵预算下的最优解，即使单个量化器无法精确达到约束。

4. 实验结果

作者在合成向量（正态分布、对数正态分布、Student-t 分布、稀疏异常值）以及真实模型张量（来自 Qwen2.5, Gemma, Llama, Phi 等模型的权重、激活值、KV-cache）上评估了其方法。

精度：
- 精炼近似 ECASQ (Refined Approx ECASQ) 将合成数据上的平均超额 vNMS（相对于 Optimal ECASQ）从约 4.97%（未精炼）降低至 1.37%。
- 在真实模型张量上，精炼近似法在各种比特率（每值 1.5 到 4 bits）下均一致优于基准方法（QSGD, QUIVER, Uniform + Entropy）。
运行时间：
- 当向量大小 $d = 262,144$ 时，Optimal ECASQ 耗时约 6.39 秒。
- Approx ECASQ 耗时约 0.26 秒（24 倍加速）。
- Refined Approx 耗时约 0.33 秒（19 倍加速）。
时间共享： 实验表明，相比于单个最优量化器，时间共享带来的潜在收益较小（中位数 < 2%，最大约 21%，且出现在极窄的低速率区间），这说明在实践中，一个调优良好的单量化器通常已经足够。

5. 重要性与主张

本文声称 ECASQ 为“精度损失”问题提供了一个原则性的解决方案，即现有的无偏量化器忽略了熵编码成本。

实用性： 空间高效的近似算法与快速精炼程序的结合，使得该方法适用于大规模机器学习工作负载（如梯度压缩、KV-cache 缩减），在这些场景下，最优 DP 过于缓慢或内存消耗过高。
通用性： 该框架支持任意允许的字母表（例如 BF16 或 FP32 可表示的值），从而实现了硬件感知的约束。
审慎性： 作者承认，虽然时间共享在理论上保证了对于任何熵预算的最优性，但在实验中其增益往往很小，通过（通过拉格朗日优化）使用单量化器的方法通常已足够。他们还指出，近似法的“一个比特”保证是一个最坏情况界限，实验结果显示其实际表现更为紧凑。