七、LUT-GEMM[2022]

论文：《LUT-GEMM: Quantized Matrix Multiplication based on LUTs for Efficient Inference in Large-Scale Generative Language Models》

修改之前的论文标题：《nuQmm: Quantized MatMul for Efficient Inference of Large-Scale Generative Language Models》

1. 近年来，大型语言模型在各种自然语言处理（NLP）任务上呈现出 SOTA的性能。这种 NLP 性能的快速进步在很大程度上得益于自监督学习方法。由于预训练主导了整个训练过程而不需要昂贵的标注过程，训练数据集的规模可以大幅增加。结合效率较高的 sequence-to-sequence模型架构（如 Transformer ），模型参数数量也显著增加。

   之前的研究（《Language models are few-shot learners》、《Training compute-optimal large language models》、《Scaling Laws for Neural Language Models》）报告称：LM 的性能随着模型大小遵循可预测的 power-law scaling 。因此，近年来出现了几种大型生成式语言模型，包括 GPT-3(175B) 、HyperCLOVA(204B)、Gopher(280B)、Chinchilla(70B)、Megatron Turing NLG(530B) 、和 PaLM(540B)，从而进一步提升 SOTA 性能。然而，数十亿参数的模型由于 GPU 内存大小有限，无法容纳在单个 GPU 上，GPU 内存通常被牺牲以提高带宽（《8-bit Inference with TensorRT》、《Up or Down? Adaptive Rounding for Post-Training Quantization》）。为解决这一问题，研究人员提出了模型并行（model parallelism），通过 GPU-to-GPU 通信将计算分布在多个 GPU 上（《Efficient large-scale language model training on GPU clusters using megatron-LM》、《Megatron-lm: Training multi-billion parameter language models using model parallelism》）。如 Figure 1 所示，模型并行将大型 LM 模型的参数分布到多个GPU 上，允许训练/推理期间通过专用通道在 GPU 之间共享信息。

   

   模型并行可以分为张量并行和流水线并行，从而分别提高延迟和吞吐量。但是，这种并行方案需要各种通信原语来同步 GPU 产生的部分输出，如 AllReduce 、Reduce、Broadcast 和 AllGather （《Optimized broadcast for deep learning workloads on dense-GPU InfiniBand clusters:MPI or NCCL?》）。尽管 GPU-specific 的外部通信协议（如 NVLink ）可以减少通信延迟，但GPU 性能的固有 variance （由各种随机因素引起，如制程 variance 和操作系统条件）仍是另一个性能瓶颈（《Pathways: Asynchronous Distributed Dataflow for ML》）。此外，由于大型矩阵被分成子矩阵，每个 GPU 面临高纵横比（tall-and-skinny）的矩阵乘法，资源利用率较低（《Efficient sparse matrix-vector multiplication on CUDA》、《Biqgemm: matrix multiplication with lookup table for binary-coding-based quantized dnns》）。因此，模型并行获得的性能提升随 GPU 数量呈亚线性（sublinear ）函数。

   为了缓解模型并行相关的挑战，参数量化（parameter quantization ）提供了最小化模型大小的实用解决方案，从而减少推理所需的 GPU 数量，如 Figure 1 所示。在各种量化方案中，均匀量化（uniform quantization ）受青睐，可以利用基于整数的算术单元（integer-based arithmetic units ）。尽管如此，均匀量化实际上被限制在 8-bit，非线性操作（如 softmax 和 normalization) ）可能产生不精确的结果（《Efficient 8-Bit Quantization of Transformer Neural Machine Language Translation Model》、《I-bert: Integer-only bert quantization》）。此外，为了充分利用整数算术单元，实现 activation 的实时量化/逆量化、以及对 activation 分布的精确估计是必要的（《LLM.int8 (): 8-bit Matrix Multiplication for Transformers at Scale》、《ZeroQuant: Efficient and Affordable Post-Training Quantization for Large-Scale Transformers》）。近期研究提出了 4-bit weight-only quantization 作为内存压缩方法（《GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers》、《GLM-130B: An Open Bilingual Pre-trained Model》），需要实时转换为 full-precision。尽管这牺牲了使用整数算术的计算优势，但大型语言模型中 weight-only quantization 提供了经验证据，即与同时量化 weights and activations 相比，可以在给定目标准确率下获得明显更高的 weight compression ratio （GPTQ, GLM-130B ）。各种采用 non-uniform 格式的 weight-only quantization 方法也被提出以提高压缩率（《Biqgemm: matrix multiplication with lookup table for binary-coding-based quantized dnns》、《AlphaTuning: Quantization-Aware Parameter-Efficient Adaptation o fLarge-Scale Pre-Trained Language Models》）。

   在本文中，我们介绍了 LUT-GEMM kernel，旨在促进当权重使用 uniform 或 non-uniform 方法量化而保持 full-precision activations 时的 quantized matrix multiplications 。如 Figure 2 所示，LUT-GEMM 有效地解决了之前量化方法中存在的两个问题：

   • 1)：因 quantized activations 导致的不可避免的准确率降低。

   • 2)：额外的 dequantization implementation的需要。

   LUT-GEMM 本质上适用于 quantized weights and full-precision activations，可以在保持所需 precision level 的同时加速推理过程。具体而言，LUT-GEMM 采用 binary-coding quantization: BCQ格式（《XNOR-Net: ImageNet Classification Using Binary Convolutional Neural Networks》），从而利用简单的算术操作。值得注意的是，BCQ 最初是为支持 non-uniform 量化而提出的，需要定制硬件进行 bit-level 操作。在本文中，我们证明了以前的 uniform 量化可以重构为 BCQ 形式，使 LUT-GEMM 能同时支持non-uniform 量化和 uniform 量化格式。因此，LUT-GEMM 能够执行各种 weight-only quantization 方案的矩阵乘法，实现低的inference latency 、以及消除对 activation quantization 的需要。

   

   我们在本工作中的主要贡献包括：

   • 我们证明了 BCQ 能同时表示 uniform and non-uniform weight quantization 。

   • 我们展示了对于 BCQ 格式，LUT-GEMM 可以提供压缩率和延迟之间的广泛 trade-offs （基于 GPU-specific 的高效硬件利用的方法来实现各种 BCQ 配置）。

   • 对大型语言模型，我们演示 LUT-GEMM 可以显着加速 small quantization bits的矩阵乘法，同时通过减少 GPU 数量从而大幅节省功耗。因此，LUT-GEMM 实现了低能耗。

   • 假设对 OPT-175B 的权重采用 3-bit BCQ 格式，由单个 GPU 来 serve，我们的实验结果显示：与 GPTQ （《GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers》）结果相比，LUT-GEMM 可以将生成每个 token 的延迟加速 2.1 倍。

7.1 背景知识

7.1.1 生成式语言模型

1. 大型生成式语言模型，如 GPT-3，是一种自回归模型，它以 feed-forward 方式使用 previous tokens 来预测 future tokens 。例如，Figure 3 所示，如果提供了 input context （如 in-context learning 中所做的，参考 《Language models are few-shot learners》），则可以使用先前所生成的 tokens 来预测 next token 。

   

   采用自注意力机制和并行训练算法的 Transformer 架构在大型生成式语言模型中被广泛使用。多亏了自监督学习和 scaling-law （《Language models are few-shot learners》、《Scaling Laws for Neural Language Models》），可以在增加模型大小时预测交叉熵损失，生成式语言模型中的参数数量也在不断增加。一些超大规模语言模型令人惊讶的定性评估结果（例如 human-like writing ）也推动了模型大小的竞争（《What Changes Can Large-scale Language Models Bring? Intensive Study on HyperCLOVA: Billions-scale Korean Generative Pretrained Transformers》、《Scaling Language Models: Methods, Analysis & Insights from Training Gopher》）。

7.1.2 GPU-Accelerated Generative LMs

1. 对于大型语言模型，矩阵乘法的处理时间主导了整个 inference latency ，因为与激活函数、normalization layers 等相比，矩阵乘法的时间复杂度更高（《LLM.int8 (): 8-bit Matrix Multiplication for Transformers at Scale》）。为了验证这一结论，Figure 4 展示了不同大小（OPT 6.7B/13B/30B/66B/175B ）的各种大规模生成式语言模型，在不同 input tokens 数量下的延迟的分解。OPT 模型遵循 Transformer 架构，由相同的层组成。设 hidden size $d_{\text{model}}$$d_\text{model}$ 为 $m$$m$ 。每个层包含 multi-head attention 和一个 feed-forward network ，包括四个主要的线性计算，其时间复杂度更高（与其他非线性操作相比）。这些操作包括将一个（$m\times 1$$m\times 1$）activation matrix 与下列四个矩阵相乘：

   • 1) ：一个 （$3m\times m$$3m\times m$）矩阵用于注意力的 key, query, value 。

   • 2)：一个 （$m\times m$$m\times m$）矩阵用于注意力的输出。

   • 3)：一个 （$4m\times m$$4m\times m$）矩阵用于第一个 feed-forward sub-layer 。

   • 4)：一个 （$m\times 4m$$m\times 4m$）用于第二个 feed-forward sub-layer 。

   所有层具有相同的结构，矩阵乘法主导整个推理延迟（《Extremely Low Bit Transformer Quantization for On-Device Neural Machine Translation》）。Figure 4 是用 A100(80GB) 和 FasterTransformer （Nvidia 的推理框架）获得的。对于各种规模的语言模型、以及不同的 input token lengths ，矩阵乘法至少占用了 75% 的处理时间（请注意，由于单个 GPU 的内存容量有限，大型语言模型可能需要多个 GPU ，从而增加了通信延迟）。GPU 常被采用从而加速推理，因为 GPU 内嵌了大量算术单元（arithmetic units ），并支持多个线程，这对加速矩阵乘法至关重要（《8-bit Inference with TensorRT》、《Efficient large-scale language model training on GPU clusters using megatron-LM.》）。但是，从 GPU 中获取高性能取决于算术强度（arithmetic intensity ），因此 batch size 必须足够大，从而确保从主内存（main memory ）中获得高的 reuse ratio （《Nvidia tensor core programmability, performance & precision》）。

   

2. 张量并行：对于高度并行的计算系统，高内存带宽对于为大量算术单元提供数据从而维持高资源利用率至关重要。因此，GPU 的主内存系统倾向于关注高带宽而不是大容量。相应地，即使提出了崭新的内存架构（如 HBM ，参考 《Zero-infinity: Breaking the gpu memory wall for extreme scale deep learning》），单个 GPU 的最大内存容量仍然只有几十 GB （《Evaluating modern gpu interconnect: Pcie, nvlink, nv-sli, nvswitch and gpudirect》）。这种有限的 GPU 内存容量导致了各种并行思想从而在多个 GPU 上划分大型语言模型（《Efficient large-scale language modeltraining on GPU clusters using megatron-LM》、《Megatron-lm: Training multi-billion parameter language models using model parallelism》）。张量并行可以将矩阵乘法划分到多个 GPU 上，从而同时生成更小的子任务。请注意，这种并行会引入额外的同步（synchronization ）开销、和 GPU-to-GPU 通信开销。

3. 内存受限的 Text Generation：Figure 3 中 summarization 阶段对计算资源有很大需求，权重重用的可能性也很高。因此，在多个 GPU 上采用张量并行可能会有效提高推理性能。相反，Figue 3 中的 generation 阶段由于其自回归特性而呈现受限于内存的工作负载（memory-bound workload ）。因此，增加 GPU 数量且结合张量并行可能不是一个经济有效的解决方案，特别是考虑到 GPU 之间的通信开销。随着 ChatGPT 等服务的日益重要，解决有限内存带宽的问题变得至关重要。不幸的是，通过 hardware advancements 来增加内存带宽通常会遇到物理限制，并与高功耗相关（《Digital integratedcircuits- A design perspective》、《Cambricon-S: Addressing Irregularity in Sparse Neural Networks through A Cooperative Software/Hardware Approach》）。因此，关注能够缓解内存瓶颈的模型压缩技术的研究工作势在必行。

   

7.1.3 量化方法及其局限性

1. 各种研究工作致力于通过改进延迟和吞吐量来增强大型且笨重的深度神经网络的 serving 性能。这些工作包括量化、剪枝、知识蒸馏、以及低秩近似。在这些方法中，量化是研究最广泛的领域，它涉及使用更快的、更高效的计算单元，以及减少内存使用。特别是采用 INT8 算子的 uniform quantization 在各种量化格式中研究最充分，目前正被积极应用于大语言模型中（《LLM.int8 (): 8-bit Matrix Multiplication for Transformers at Scale》、《SmoothQuant: Accurate and Efficient Post-Training Quantization for Large Language Models》、《ZeroQuant: Efficient and Affordable Post-Training Quantization for Large-Scale Transformers》）。

   与 FP16 相比，当代计算系统中常见的 INT8 算术单元提供了降低延迟（得益于其较低的面积和功耗）和高达 50% 的内存减少。因此，目前的 NVIDIA GPU 采用支持 INT8 操作的 Tensor cores 来加速计算（《Nvidia tensor core programmability, performance & precision》）。但是，利用 INT8 需要 activation quantization ，这对采用 INT8 单元实现压缩和加速的模型提出了重大挑战。例如，当 scaling factors 离线确定时，由于异常值被近似， activation quantization 可能导致模型准确率大幅下降。为了避免这种准确率下降， token-based dynamic quantization 已成为量化大语言模型的关键技术（《LLM.int8 (): 8-bit Matrix Multiplication for Transformers at Scale》、《ZeroQuant: Efficient and Affordable Post-Training Quantization for Large-Scale Transformers》）。LLM.int8() 方法（《LLM.int8 (): 8-bit Matrix Multiplication for Transformers at Scale》）通过提出分解方法，大部分计算用 INT8 进行，只对有限数量的异常值用 FP16 ，解决了大语言模型中异常值系统性出现的问题，从而仅导致语言模型延迟轻微下降。

   SmoothQuant （《SmoothQuant: Accurate and Efficient Post-Training Quantization for Large Language Models》）采用了更高级的方法，通过数学方法将 activations 中的方差转移到权重中，而权重相对更容易量化； activations 更难量化，因为存在异常值。该技术使得采用 INT8 计算单元（如 W8A8 ）高效地计算大语言模型成为可能，即使在对 activations 进行静态量化的情况下。根据 SmoothQuant 的结果，当系统性地出现异常值时，大语言模型的加速可以达到 1.5 倍、GPU 使用量减少 2 倍。然而，应注意的是，要在新的大语言模型中应用 SmoothQuant ，有必要在应用迁移技术之前经验性地观察和验证异常值的出现。

   另一方面，如前所述，token generation 过程的自回归特性限制了硬件的最大吞吐量，即使采用 INT8 precision 。因此，需要生成大量 token 的服务（如 chatGPT ），可能不会通过采用 INT8 precision 获得显著的性能改进。

   最近的研究关注 generation 步骤的低效率，并相应地提出了利用 W4A16 格式（《GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers》、《GLM-130B: An Open Bilingual Pre-trained Model》），即将模型权重压缩为 4-bit 整数而不量化 activations 。鉴于当前计算系统无法加速 W4A16 格式，GPTQ （《GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers》）通过首先即时地将权重逆量化为 FP16 格式、然后执行矩阵乘法操作来解决此问题。通过利用 generation 步骤的受限于内存的特点，这种方法可以减少 GPU 的数量并改进 generation latency ，尽管存在逆量化的开销。

7.1.4 Binary-Coding Quantization

1. 在本文中，我们提出了 binary-coding quantization: BCQ 的应用。BCQ 是一种通用的 non-uniform quantization 方案，它包含了 uniform quantization ，正如我们在后面的部分所讨论的。BCQ 首先在 《XNOR-Net: ImageNet Classification Using Binary Convolutional Neural Networks》 中被提出，作为一种与传统 uniform quantization 方法形成对比的可行方案。当权重向量 $\overrightarrow{\mathbf{w}}\in {\mathbb{R}}^n$$\mathbf {\vec w}\in \mathbb R^n$ 被 BCQ 量化，且 quantization bits 数量为 $q$$q$ 时，$\overrightarrow{\mathbf{w}}$$\mathbf{\vec w}$ 被逼近为：

   $$\begin{array}{}\text{(1)}& \widehat{\overrightarrow{\mathbf{w}}}=\sum _{i=0}^{q-1}{\alpha }_i{\overrightarrow{\mathbf{b}}}_i\end{array}$$

   其中：

   • ${\alpha }_i\in {\mathbb{R}}^{+}$$\alpha_i\in \mathbb R^+$ 为 scaling factor 。

   • ${\overrightarrow{\mathbf{b}}}_i\in \{-1,+1{\}}^n$$\mathbf{\vec b}_i\in \{-1, +1\}^n$ 为 binary vector 。

   ${\overrightarrow{\mathbf{b}}}_i$$\mathbf{\vec b}_i$ 的每个元素可以用 1 bit 来表示，因此整个向量只需要 n bit 来表示。

   对于 $\overrightarrow{\mathbf{w}}\in {\mathbb{R}}^n$$\mathbf{\vec w}\in \mathbb R^n$ ，它的每个元素需要 $q\times n/n=q$$q\times n/n = q$ 个 bit 来表示，因此 $q$$q$ 表示 quantization bits 数量。

   注意， scaling factor $({\alpha }_0,\cdots ,{\alpha }_{q-1})$$(\alpha_0,\cdots,\alpha_{q-1})$ 被多个权重所共享（注：例如权重矩阵的各行 ${\overrightarrow{\mathbf{w}}}_1,\cdots ,{\overrightarrow{\mathbf{w}}}_N$$\mathbf{\vec w}_1,\cdots,\mathbf{\vec w}_N$，$N$$N$ 为权重矩阵的行数 ），这样更大的 $n$$n$ 值导致相对更小的内存空间从而用于 scaling factors 。

   量化过程大致包括找到 scaling factors 和 binary vectors 以最小化量化误差，即：

   $$\begin{array}{}\text{(2)}& \arg \underset{\overrightarrow{\alpha },\mathbf{B}}{min}{\Vert \overrightarrow{\mathbf{w}}-\sum _{i=0}^{q-1}{\alpha }_i{\overrightarrow{\mathbf{b}}}_i\Vert }_2^2\end{array}$$

   其中 $\overrightarrow{\alpha }=({\alpha }_0,\cdots ,{\alpha }_{q-1})\in {\mathbb{R}}^q$$\vec \alpha = (\alpha_0,\cdots,\alpha_{q-1})\in \mathbb R^q$ ，$\mathbf{B}=({\overrightarrow{\mathbf{b}}}_0,\cdots ,{\overrightarrow{\mathbf{b}}}_{q-1})\in {\mathbb{R}}^{n\times q}$$\mathbf{ B} = \left(\mathbf{\vec b}_0,\cdots, \mathbf{\vec b}_{q-1}\right)\in \mathbb R^{n\times q}$。

   上式就是 LUT-GEMM 的核心思想。后面的技巧都是为了加速这个求解过程而设计的。

   除非 $q=1$$q=1$ ，否则没有解析解。因此， scaling factors 和 binary vectors 是通过迭代搜索（iterative search ）方法（《Network sketching: exploiting binary structure in deep CNNs》、《Alternating Multi-bit Quantization for Recurrent Neural Networks》）、或量化感知训练（quantization-aware training ）获得的（《Extremely Low Bit Transformer Quantization for On-Device Neural Machine Translation》）。最近，《AlphaTuning: Quantization-Aware Parameter-Efficient Adaptation of Large-Scale Pre-Trained Language Models》提出了 AlphaTuning ，一种结合 parameter-efficient adaptation 和 BCQ 方案的方法，展示了各种生成式语言模型可以在微调下游数据集的同时实现极端的 low-bit quantization 、甚至低至 1-bit 或 2-bit 。

7.2 LUT-GEMM的设计方法

1. LUT-GEMM 是为了开发高性能、低能耗的大语言模型推理系统而设计的。为实现此目标，LUT-GEMM 采用了几种创新方法。

   • 首先，我们通过添加 bias 项来扩展常规的 BCQ 方法，这显著增强了表达能力。这个简单的 addition 使得 extended BCQ 格式可以同时表示 non-uniform and uniform quantization 方法，允许我们利用各种量化方法（依赖于具体的 LLM 要求）。

   • 其次，我们进一步 refine 了 BCQ 方案的实现细节，使压缩比（compression ratio ）与量化误差之间的权衡更好地利用语言模型的特点。

   • 最后，由于大多数 non-uniform quantization 方法通常涉及低并行度的复杂操作，并且可能缺乏硬件支持，我们设计了 LUT-GEMM 以高效适配 BCQ 格式。我们提出的 LUT-GEMM kernel 直接利用 BCQ 格式，消除了额外的开销（如 dequantization ）。因此，LUT-GEMM 展示了降低的延迟、和/或减少的语言模型推理所需 GPU 数量，同时本质上适配各种 weight-only quantization 的方法。

7.2.1 Extension of Binary-Coding Quantization

1. 非对称的 Binary-Coding Quantization ：常规的 BCQ 方法基本上局限于相对于零点呈现对称的 quantization shape 。BCQ 方法的另一个约束源于其无法表示零值，这是由于其对称量化的特性。为增强 BCQ 的表达能力，我们通过引入 bias 项 $z$$z$ 来扩展常规的BCQ 方法：

   $$\begin{array}{}\text{(3)}& \widehat{\overrightarrow{\mathbf{w}}}=\left(\sum _{i=0}^{q-1}{\alpha }_i{\overrightarrow{\mathbf{b}}}_i\right)+z\end{array}$$

   因此， 修改后的BCQ 格式可以表示以 $z$$z$ 为中心的 asymmetry quantization，如 Figure 5(a) 所示。

   因为 ${\overrightarrow{\mathbf{b}}}_i$$\mathbf{\vec b}_i$ 的取值为 {+1, -1} ，因此下图展示为一棵二叉树。假设考虑 $\widehat{\overrightarrow{\mathbf{w}}}$$\hat{\mathbf{\vec w}}$ 的第 $k$$k$ 个元素 ${\hat{w}}_k$$\hat w_k$ ：

   • 如果 $b_{2,k}>0$$b_{2,k} > 0$ ，则从根节点开始考虑右子树；否则考虑左子树。

   • 假设考虑右子树。如果 $b_{1,k}>0$$b_{1,k} \gt 0$ ，则考虑右子节点；否则考虑左子节点。

   • 以此类推，最终的叶节点代表 ${\hat{w}}_k$$\hat w_k$ 的取值。

   所有的叶节点代表 ${\hat{w}}_k$$\hat w_k$ 的取值空间。

   

2. Uniform Quantization：我们表明，在 BCQ 格式中引入 bias 项使其能表示 uniform quantization ，方法是通过仔细调整 scaling factors 和 bias 项（Figure 5(b) ）。让我们详细说明如何将 asymmetric uniform quantization 转换为具有 bias 项的 symmetric BCQ 。一个 b-bit 的 uniformly quantized weight $\widehat{\overrightarrow{\mathbf{w}}}$$\hat{\mathbf{\vec w}}$ ，且具有 scaling factor $s$$s$ 可以表达为：

   $$\begin{array}{}\text{(4)}& \widehat{\overrightarrow{\mathbf{w}}}=s\sum _{i=0}^{q-1}{2}^i{\widehat{\overrightarrow{\mathbf{b}}}}_i+\hat{z},{\widehat{\overrightarrow{\mathbf{b}}}}_i\in [0,1]\end{array}$$

   然后，$\widehat{\overrightarrow{\mathbf{w}}}$$\hat{\mathbf{\vec w}}$ 可以重写为：

   $$\begin{array}{}\text{(5)}& \begin{array}{c}\widehat{\overrightarrow{\mathbf{w}}}=s\sum _{i=0}^{q-1}{2}^i{\widehat{\overrightarrow{\mathbf{b}}}}_i+\hat{z}=\frac{1}{2}s\sum _{i=0}^{q-1}{2}^i\times \left(2\widehat{\overrightarrow{\mathbf{b}}}\right)+\hat{z}\\ =\sum _{i=0}^{q-1}\frac{1}{2}s\times 2^i(2{\overrightarrow{\mathbf{b}}}_i-1)+\sum _{i=0}^{q-1}\frac{1}{2}s\times 2^i+\hat{z}\end{array}\end{array}$$

   给定 BCQ 格式的 binary weight $\overrightarrow{\mathbf{b}}$$\mathbf{\vec b}$ ，则我们定义 $\overrightarrow{\mathbf{b}}=2\widehat{\overrightarrow{\mathbf{b}}}-1$$\mathbf{\vec b} = 2\hat{\mathbf{\vec b}} - 1$，则有：

   $$\begin{array}{}\text{(6)}& \widehat{\overrightarrow{\mathbf{w}}}=\sum _{i=0}^{q-1}(2^{i-1}s\times {\overrightarrow{\mathbf{b}}}_i)+(\sum _{i=0}^{q-1}\frac{1}{2}s\times 2^i+\hat{z})\end{array}$$

   则这可以视为 BCQ 的一个特例，其中：

   $$\begin{array}{}\text{(7)}& {\alpha }_i=2^{i-1}s,z=\sum _{i=0}^{q-1}\frac{1}{2}s\times 2^i+\hat{z}\end{array}$$

   从 Figure 5 中我们可以看到，对于 q-bit 量化，uniform quantization 方法采用单 scaling factor ，而 non-uniform 量化技术需要使用 $q$$q$ 个不同的 scaling factors 。因此，由于采用了 extended BCQ 格式，我们提出的 LUT-based 的矩阵乘法方案同时适用于 uniform quantization 和 binary-coding-based non-uniform quantization 方法。

7.2.2 Group-wise $\alpha$$\alpha$ 赋值

1. 在实践中，常规的 BCQ 方法假设每个权重矩阵的行（甚至整个矩阵）共享一个 scaling factor ，从而支持 CPU 或 GPU 的向量指令 （vector instructions ）（《XNOR-Net: ImageNet Classification Using Binary Convolutional Neural Networks》、《Alternating Multi-bit Quantization for Recurrent Neural Networks》）。但是，随着大型语言模型引入更深的和更宽的模型结构、以及参数数量的不断增加（《Scaling Language Models: Methods, Analysis & Insights from Training Gopher》、《Megatron-lm: Training multi-billion parameter language models using model parallelism》），我们认为这种常规的 row-wise BCQ 格式面临各种挑战。

   • 假设选择了一个相对较小的 hidden size （例如 OPT 350M 的 $d_{\text{model}}=1024$$d_\text{model}=1024$），以及相应较小的权重矩阵，scaling factors 的 row-wise assignment 可能是合理的，以获得低的量化误差。

   • 另一方面，如果 hidden size 迅速增加（例如 GPT-3 175B 的 $d_{\text{model}}=12288$$d_\text{model}=12288$），随着大型语言模型的出现，计算一个适当的 scaling factors 从而与更多权重共享，这将更具挑战性。

   为实现 low-bit quantization 方案，我们有必要研究 assigning scaling factors 的不同方式，只要这些新的分配方式可以实现。

   作为 row-wise quantization 的替代方案，我们提出了 group-wise quantization，其中一个 scaling factor 可以由任意数量的权重共享。我们提出的新的 BCQ 格式引入了一个新的超参数 $g$$g$ 作为group size，表示要共享一个 scaling factor 的权重数量。在本文中，$g$$g$ 是一个固定数，范围是从 $32$$32$ 到矩阵宽度（等效于 row-wise quantization ）。由于 $g$$g$ 是一个常数，hidden size 不影响我们的 group-wise BCQ 格式。

   group-wise quantization 的物理意义：对于权重矩阵的给定行 $\overrightarrow{\mathbf{w}}\in {\mathbb{R}}^n$$\mathbf{\vec w} \in \mathbb R^n$ ，将它拆分为 $n/g$$n/g$ 组。为方便表述，这里令 $g=n/2$$g=n/2$ 。因此将 $\overrightarrow{\mathbf{w}}$$\mathbf{\vec w}$ 拆分为两组：${\overrightarrow{\mathbf{w}}}^{(1)}\in {\mathbb{R}}^{n/2},{\overrightarrow{\mathbf{w}}}^{(2)}\in {\mathbb{R}}^{n/2}$$\mathbf{\vec w}^{(1)}\in \mathbb R^{n/2},\mathbf{\vec w}^{(2)}\in \mathbb R^{n/2}$ 。

   然后针对每个 ${\overrightarrow{\mathbf{w}}}^{(j)}$$\mathbf{\vec w}^{(j)}$ ，最小化残差：

   $$\begin{array}{}\text{(8)}& \arg \underset{\overrightarrow{\alpha },\mathbf{B}}{min}{\Vert {\overrightarrow{\mathbf{w}}}^{(j)}-\sum _{i=0}^{q-1}{\alpha }_i^{(j)}{\overrightarrow{\mathbf{b}}}_i^{(j)}\Vert }_2^2\end{array}$$

   其中， scaling factor 在各个分组内部共享。

   为什么按列进行分组，而不是按行进行分组？论文并未说明原因。

2. 对压缩比（Compression Ratio ）的影响：设 $q$$q$ 为 quantization bits 数量。对于给定的 $q$$q$ ，更小的group size $g$$g$ 可以通过增加 scaling factors 的内存占用为代价来降低量化误差。然后，target quantization error 作为约束来确定 $q$$q$ 和 $g$$g$ 之间的权衡，因此导致一系列可实现的压缩比。换言之，由于引入 $g$$g$ ，我们可以控制 scaling factors 和 binary vectors 的数量作为 trade-off 过程。请注意，如果矩阵宽度足够大， row-wise quantization 的内存占用主要由 binary vectors 的大小决定，因为 scaling factors 的大小通常可以忽略。

   与常规方案相比，我们提出的 group-wise BCQ 为满足 target compression ratio 提供了新的大搜索空间。 Figure 6 以两个$(g,b)$$(g,b)$ 配置作为示例，展示量化一个 $(4\times 8)$$(4\times 8)$ 矩阵。确实，即使 quantization bits 数量 $q$$q$ 更小，当group size $g$$g$ 很小（即使用更多 scaling factors ）时，内存占用也可能很大。

   

7.2.3 LUT based Quantized Matrix Multiplication

1. 我们采用 BCQ 格式用于 weight quantization 而为 activations 保持 full precision 的量化方案，会导致朴素的矩阵乘法中出现重复的和冗余的部分计算（partial computations ）。为说明这一点，假设给定 binary matrix $\mathbf{B}\in \{-1,+1{\}}^{4\times 4}$$\mathbf B\in \{-1,+1\}^{4\times 4}$ 和 activation vector $\overrightarrow{\mathbf{x}}\in {\mathbb{R}}^4$$\mathbf{\vec x} \in \mathbb R^4$ ：

   $$\begin{array}{}\text{(9)}& \begin{array}{c}\mathbf{B}=\left[\begin{array}{cccc}+1& -1& -1& +1\\ +1& -1& +1& -1\\ +1& -1& -1& -1\\ -1& +1& -1& +1\end{array}\right],{\overrightarrow{\mathbf{x}}}^{\mathrm{\top }}=\left[\begin{array}{c}1.2\\ -0.7\\ 0.3\\ 0.6\end{array}\right]\end{array}\end{array}$$

   则计算 $\mathbf{B}{\overrightarrow{\mathbf{x}}}^{\mathrm{\top }}$$\mathbf B\mathbf{\vec x}^\top$ （最终结果需要与 scaling factors 相乘）会重复计算 $1.2-(-0.7)$$1.2 - (-0.7)$ 三次、$(-0.3+0.6)$$(-0.3 + 0.6)$ 两次。这种冗余计算是由 $\mathbf{B}$$\mathbf B$ 的二元化元素而引起的，因此我们期望随着矩阵 $\mathbf{B}$$\mathbf B$ 大小的增长，重复计算会更多。此外，加载 $\mathbf{B}$$\mathbf B$ 的每个元素需要 bit-level 的内存访问，这对商用 CPU 和 GPU 来说可能较慢。

   为避免 bit-level 的内存访问并高效计算 $\mathbf{B}{\overrightarrow{\mathbf{x}}}^{\mathrm{\top }}$$\mathbf B\mathbf{\vec x}^\top$ ，我们可以预先计算 full-precision activations 和 binary patterns 的所有可能组合。请注意，当大量计算产生的值集中在一个受限集合时，lookup table: LUT 已被广泛用于节省处理时间（《LUT filters for quantized processing of signals》、《LUT Optimization for Memory-Based Computation》、《Multiplication Through a Single Look-Up-Table (LUT) in CNN Inference Computation》）。当从 LUT 中检索一个值要比进行原始计算要快得多时，基于 LUT 的计算尤其合理。BCQ 格式也适合 LUT-based 的方法实现。注意，这里的 BCQ 格式没有 quantizing activations ，其中 quantizing activations 需要大量修改训练代码和模型结构（《Quantization and training of neural networks for efficient integer-arithmetic-only inference》、《Training and Inference with Integers in Deep Neural Networks》）。

   例如，对 $\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$ 中的每个 3 个元素 $\{x_1,x_2,x_3\}$$\{x_1,x_2,x_3\}$ ，我们可以像 Table 1 所示预先计算 $2^3=8$$2^3=8$ 个所有可能的值，并将这些值存储在 LUT 中。假设 $\mu$$\mu$ 为 $\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$ 中用于构造 LUT 的子向量长度（因此 Table 1 中 $\mu =3$$\mu=3$ ），一旦使用 $\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$ 的子向量生成 LUT 的 $2^{\mu }$$2^\mu$ 个值，获取 $\mathbf{B}{\overrightarrow{\mathbf{x}}}^{\mathrm{\top }}$$\mathbf B\mathbf{\vec x}^\top$ 的部分点积的运算就被 LUT 检索操作所替代；同时，检索的 key 由 $\mathbf{B}$$\mathbf B$ 中的 $\mu$$\mu$ 个 binary elements 拼接而成。

   为完成$\mathbf{B}{\overrightarrow{\mathbf{x}}}^{\mathrm{\top }}$$\mathbf B\mathbf{\vec x}^\top$ 的计算，所有的部分内积（partial products）被累加起来，然后乘以 scaling factors 。当 $\mathbf{B}$$\mathbf B$ 的 row dimension 增加时（例如随着生成式 LM 越来越大），LUT 的利用率增加，因为出现了越来越多的冗余计算。

   这个 lookup table 的存储会消耗大量资源；同时 lookup table 的预先生成需要消耗大量时间。更重要的是，在推断过程中，lookup table 是一次性的消耗品：针对不同的输入需要生成不同的 lookup table 。

   

2. 让我们简要解释一下如何优化 $\mu$$\mu$，这在 《Biqgemm: matrix multiplication with lookup table for binary-coding-based quantized dnns》 中也有讨论。如果 $\mu$$\mu$ 增加，则 LUT 的构建成本也会增加 $2^{\mu }$$2^\mu$。然而，增加的 $\mu$$\mu$ 可以提高计算并行性，因为我们可以用单次 LUT 检索操作取代 $\mu$$\mu$ 次 FP16 additions 操作。因此，正如 《Biqgemm: matrix multiplication with lookup table for binary-coding-based quantized dnns》 所报告的，存在一个最优的 $\mu$$\mu$，可以最大限度地提高速度。请注意，优化 $\mu$$\mu$ 还需要考虑 aligned memory accesses 。在我们的工作中，$\mu =8$$\mu = 8$ 是一个实用的选择。

7.2.4 Proposed LUT-GEMM

1. 除了 LUT-based 的方案（消除冗余计算和 bit-level 内存访问）之外，我们提出的 LUT-GEMM 还需要与 group-wise quantization 配合，从而在给定 $q$$q$ 的情况下提高准确率。我们在 GPU 上优化 single-batch operations 的策略如下：

   • 为提高并行度，我们创建尽可能多的线程，同时每个线程都可以执行独立的 LUT 访问。

   • 一个线程所访问的 binary weights 可以共享一个公共 scaling factor ，这样 scaling factors 相关的操作不会降低线程的性能。

   • 如果向线程分配的资源太小，则 LUT 利用率会很低，synchronization 开销会增加。因此，我们需要经验性地优化线程配置。

   为了简单起见，我们将提出的 group-wise quantized matrix multiplication 公式化为：

   $$\begin{array}{}\text{(10)}& \overrightarrow{\mathbf{y}}=\sum _{i=0}^q({\mathbf{A}}_i\circ \left({\mathbf{B}}_i\overrightarrow{\mathbf{x}}\right))\end{array}$$

   其中：

   • $\mathbf{A}$$\mathbf A$ 是一个 $(m\times n)$$(m\times n)$ 的 FP16 的 scaling matrix 。

   • $\mathbf{B}$$\mathbf B$ 为一个 $(m\times n)$$(m\times n)$ 的 FP16 的 binary matrix 。

   • $\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$ 为一个 FP16 的长度为 $n$$n$ 的 input vector 。

   • $\circ$$\circ$ 为逐元素乘法算子。

   请注意，在实际情况下，由于每 $g$$g$ 个权重共享一个 scaling factor ，因此 $\mathbf{A}$$\mathbf A$ 的内存占用降低了。

2. 整体架构：对于 LUT-GEMM ，我们将 $l$$l$ 个 LUT 分配给 GPU 的一个线程块（thread block: TB ）。然后，分配给每个 TB 的 $\mathbf{A}$$\mathbf A$ 和 $\mathbf{B}$$\mathbf B$ 的子矩阵的大小变为 $(t_h\times t_w)$$(t_h\times t_w)$，其中 $t_w=l\times \mu$$t_w=l\times \mu$。小的 $t_h$$t_h$ 可以增加可用线程数，而大的 $t_h$$t_h$ 可以提高 TB 内 LUT 的利用率。因此， $t_h$$t_h$ 通过经验性地确定（对大型语言模型，2048 是一个实用数字）。请注意，分配给每个 TB 的资源足够小，使得只要 $g$$g$ 大于 $l\times \mu$$l\times\mu$，多个 TB 就可以共享一个 scaling factor 。

   Figure 7 展示了在 GPU 上实现 LUT-GEMM 的整体方案，其中我们假设 $\mu =8,l=4,t_w=32,t_h=4,q=1,g=32$$\mu=8, l=4,t_w=32,t_h=4, q=1,g=32$。 对于$q>1$$q>1$，可以对 Figure 7 的整个过程迭代 $q$$q$ 次，同时累加中间结果。

   该方案需要硬件级的编程支持，因此读者觉得实践的价值不大。因为换一种硬件（如手机芯片），算法是否仍然可行，是个未知数。

   

3. 详细实现：

   • 首先，每个 TB 使用分配的部分 $\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$ 值进行预计算以填充 $l$$l$ 个 LUT 。

   • 然后，TB 中的所有线程可以共享 $l$$l$ 个 LUT （以减少全局内存访问）；多个线程可以并行处理 $\mathbf{B}$$\mathbf B$ 的子矩阵的多行（以提高吞吐量）。

   • 当线程完成检索、以及对 LUT 的值求和之后，获取 scaling factors （每个线程只获取一次）并将其乘以产生 partial outputs 。

   • 最后，将来自不同 TB 的 $\frac{n}{l\times \mu }$$\frac{n}{l\times \mu}$ 个 partial outputs 累加（通过 atomicAdd 操作，如 Figurer 7 所示）以生成最终输出。

   LUT 存储在 GPU 中的共享内存中，共享内存提供高带宽（例如 A100 的 19TB/s ）。因此，LUT 的高内存访问（同时，一次 LUT 访问可以代替多个 FLOPs ）实现了快速的矩阵计算。关于 LUT 内存大小，every 8 hidden dimensions只需要 1KB ，共享内存大小超过几 MB （例如 A100 with 192KB per SM 的共享内存大小是 20MB，一共 108 SMs ），因此整个 LUT 可以安全存储在共享内存中。例如，对于A100，hidden dimension 最多可达 324,000 ，而 GPT-3 175B 的 hidden dimension 为 12,288 。

4. 为研究 LUT-GEMM 对 group size $g$$g$ 的延迟的方差，我们在 $g$$g$ 值变化时执行矩阵乘法（使用 $(m\times n)$$(m\times n)$ 矩阵和一个 $(n\times 1)$$(n\times 1)$ 矩阵）。在 Figure 8 中，对每个 $m$$m$ （或者 $n$$n$ ）的选择，我们将不同 $g$$g$ 的矩阵乘法延迟与 row-wise （即，$g=n$$g=n$）的 BCQ 格式进行了比较。有趣的是，当 $g>32$$g>32$ 时，不管 $m$$m$ 如何，group-wise LUT-GEMM 都与 row-wise LUT-GEMM 一样快。换句话说，合理的大 $g$$g$ （如 128 和 256 ）可以使 LUT-GEMM 很快，同时 group-wise 可以大幅提高准确率。

   

5. 为深入理解 Figure 8 中的机制，我们分析了 LUT-GEMM 的内存占用，因为 single-batch operations 主要受限于内存，而延迟与内存占用成正比。设 binary weights 和 scaling factors 的空间复杂度分别为 $S_b$$S_b$和 $S_{\alpha }$$S_\alpha$ ，则总空间复杂度$S$$S$可以描述为：

   $$\begin{array}{}\text{(11)}& S=S_b+S_{\alpha }=\mathcal{O}(1\times m\times n\times q+16\times m\times \frac{n}{g}\times q)=\mathcal{O}\left(mnq(1+\frac{16}{g})\right)\end{array}$$

   因此，如果 $g\gg 16$$g\gg 16$ ，则 $S$$S$ 可以独立于$g$$g$，并近似为 $\mathcal{O}(mnq)$$\mathcal O(mnq)$。为验证 single-batch operations 下 LUT-GEMM 延迟与内存占用成正比的说法，在$m=n=12288$$m=n=12288$ 时，我们探索了各种 (q, g) pair 以及相应的压缩比，并测量了矩阵乘法的延迟，如 Figure 9 所示。

   可以注意到，超参数 $g$$g$ 允许对压缩比进行细粒度搜索，这是单独搜索超参数 $q$$q$ 所无法实现的。在 Figure 9 中的所有可用压缩比中，latency 是压缩比的函数。例如，如果两个不同的 pairs $(q_1,g_1)$$(q_1,g_1)$ 和 $(q_2,g_2)$$(q_2,g_2)$ 显示出相似的内存占用，那么我们就可以通过 LUT-GEMM 得到相似的延迟。

   

7.3 实验

1. 在本节中，我们介绍在各种复杂度水平上使用 LUT-GEMM 获得的实验结果，从 single-layer experimental setup （不考虑 group size ）、到完整的 model level 。

   • 首先，我们在不考虑 group size 的情况下检查 LUT-GEMM 对特定 layer 的影响。

   • 接下来，我们比较张量并行与 LUT-GEMM ，然后研究 group size 的影响。

   • 最后，我们分析 OPT 模型的端到端延迟，以确定 LUT-GEMM 整体对性能的影响。

7.3.1 与各种 Kernels 的简单比较

1. Table 2 给出了在 OPT-175B 模型的前馈神经网络（Feedforward Neural Network: FFN ）第一层上的延迟测量结果。结果是通过各种 input and weight quantization 方法获得的，包括 FP-FP(baseline) 、INT-INT、FP-INT 和 FP-BCQ 。所选 kernels 包括：cuBLAS （用于 FP-FP 或 INT-INT ）、GPTQ （用于 FP-INT ）、或 LUT-GEMM （用于 FP-INT 或 FP-BCQ ）。注意，GPTQ kernel 包括 dequantization 过程，然后紧跟着 GEMM ；而 LUT-GEMM 直接接受 row-wise quantized weights ，不需要 dequantization 。

   我们可以观察到：

   • INT8-INT8 （使用 cuBLAS ）实现的延迟相比 FP-FP 仅略有改善，因为 cuBLAS 没有针对 single-batch operations 进行很好的优化。

   • 与 INT8-INT8 量化相比， GPTQ kernel 延迟更低，但由于 dequantization 开销，其速度慢于 LUT-GEMM 。

   • 支持 BCQ 和 INT 量化的所提出的 LUT-GEMM kernel 在考虑的 kernels 中实现了最低延迟。

   

7.3.2 与 FP16 张量并行的比较

1. Table 3 总结了使用 cuBLAS （具有张量并行）或 LUT-GEMM （具有一个 GPU ）执行的矩阵乘法的分析结果。使用 nvidia-smi 工具收集了 GPU 功率和其他指标。同样,一个 $(m\times m)$$(m\times m)$ 矩阵与一个 $(m\times 1)$$(m\times 1)$ 矩阵相乘，其中我们设置 $m$$m$ 为 8192 和 12288 。这个操作与我们对 GPT-3 175B 的研究相关，其 hidden size 为 12288 。我们对 LUT-GEMM 包含 $q=2$$q=2$ 的情况，因为通过具有 BCQ 格式的 quantization-aware training ，一些文献报告对 Transformer 的 2-bit 量化是可行的（《Extremely Low Bit Transformer Quantization for On-Device Neural Machine Translation》）。我们注意到：

   • cuBLAS 中张量并行使用额外的GPU 会显著降低 GPU 利用率、内存利用率、以及 computation latency ratios 。如通信延迟占比的增加所示，这种利用率的降低表明一些 GPU 可能暂时闲置，直到所有 GPU 都被同步。相应地，张量并行可以获得的加速程度远小于 GPU 的数量。因此，使用更多 GPU 的 cuBLAS 会增加矩阵乘法的能耗。

   • 另一方面，LUT-GEMM （具有一个 GPU ）可以提供高速加速（这是张量并行无法实现的），同时保持高的 GPU/memory 利用率。因此，LUT-GEMM 通过结合低延迟和减少 GPU 数量，极大地节省了矩阵乘法的能耗。例如，当 $m=12288$$m=12288$ 时，相比cuBLAS ，LUT-GEMM （$q=2$$q=2$ 且仅使用单个 GPU ）实现了 4.8 倍的能耗降低、以及 6.0 倍的加速。

   

7.3.3 压缩比的探索

1. 为研究 group-wise BCQ 从而扩大 compression 的搜索空间的能力，我们在三个公开可用的 pre-trained OPT 模型上进行了实验。具体而言，我们在 pre-trained OPT 模型上应用 post-training quantization （使用 《Alternating Multi-bit Quantization for Recurrent Neural Networks》 中介绍的 iterative solver ），同时调整 $g$$g$ 和 $q$$q$。然后，对每个 quantized model 在 LAMBADA 数据集上进行评估，找到压缩比和准确率之间的关系。Figure 10 显示了尝试各种 $q$$q$ 值和 $g$$g$ 值时的准确率和压缩比。从 Figure 10 可以观察到：

   • 与传统的 row-wise quantization 相比，group-wise BCQ 提供了新的最优配置（见附录中的 Figure 11 从而查看更广泛的结果）。因此，为了实现最佳压缩比（或最小的准确率退化），有必要同时探索不同的 $q$$q$ 和 $g$$g$ 值。

   • 注意，对于 OPT-13B 和 OPT-30B ，正如我们讨论的大型语言模型的 row-wise quantization 的局限性，小的 $g$$g$ 值对于实现低的准确率退化至关重要（而延迟不会受小 $g$$g$ 值的严重影响）。

   总之，对每个模型，$q$$q$ 和 $g$$g$ 对准确率的影响不同，因此 $q$$q$ 和 $g$$g$ 是需要优化的超参数。

   

   

7.3.4 端到端延迟

1. 现在，我们评估保持 full precision activations 并采用 quantized weights下，各种 OPT 模型的 single-batch size 端到端的推理延迟。Table 4 展示了使用 round-to-nearest: RTN 方法进行均匀量化时，end-to-end latency per token 和困惑度。注意，延迟测量是在 FasterTransformer 框架内进行的。我们利用不同数量的 GPU 来获得 model parallelism 可以实现的潜在加速增益。从 Table 4 的观察我们可以得出以下结论：

   • 1) ：减小group size （$g$$g$ ）可以有效降低困惑度，即使是使用简单的 RTN 量化方案，代价是延迟略有增加。

   • 2)：增加 GPU 数量（即，并行度增加）并不能显著降低延迟，因为存在各种开销，如 GPU-to-GPU通信成本，如 Figure 4 所述。值得一提的是，在 LUT-GEMM 的 case 中（其中矩阵乘法被加速），相较 cuBLAS ， GPU-to-GPU相对通信开销更加突出。因此，对于 LUT-GEMM ，模型并行似乎不太有效。换言之，对于高性能的矩阵乘法引擎，通信开销更加突出。

   以 OPT-30B 模型为例，使用 FP16 权重可以在单个 GPU 上执行端到端推理。但是，对于具有 FP16 权重的 OPT-66B 模型，由于模型大小超过单个 GPU 的内存容量（ A100 为 80GB ），必须使用模型并行技术。然而，当 OPT-66B 模型的权重被量化到 3-bit 或 4-bit 时，这被证明是可行的（《GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers》），推理可以容纳在单个 GPU 上。假设采用 3-bit 量化、以及用 $g=32$$g=32$ 来实现 LUT-GEMM ，可以对 OPT-30B （使用 1 个 GPU ）实现 2.43 倍的加速、对 OPT-66B （使用 2 个 GPU ）实现 2.25 倍的加速。请注意，我们在 Table 4 中展示 LUT-GEMM 性能的方法依赖于 basic post-training quantization ，而大语言模型有更高级的量化方法。例如，在构建 pre-trained 模型后进行微调，如 ChatGPT 中所展示的，更有效的量化技术如 AlphaTuning （《AlphaTuning: Quantization-Aware Parameter-Efficient Adaptation of Large-Scale Pre-Trained Language Models》）甚至可以实现 2-bit 量化。当与先进的量化方法相结合以减少 quantization bits 时，LUT-GEMM 的效用进一步增强。附录 A.1 中提供了额外的评估结果。

   

   

   

   

7.4 加速 Quantized OPT-175B

1. Table 5 比较了在 FasterTransformer 框架中生成 OPT-175B 的一个 token 的端到端延迟。我们评估了三种不同的实现：

   • 1) ：原始 FP16 cuBLAS 。

   • 2)：集成了 FP16 cuBLAS （使用 GPTQ 的 library ）的 dequantization （从 3-bit ）。

   • 3)：假设 uniform quantization 的 LUT-GEMM 。

   通过只关注前面讨论的四个特定矩阵乘法，LUT-GEMM 展示了它降低所需 GPU 数量的能力，同时随着 $q$$q$ 的降低或 GPU 的增加从而降低延迟。对于具有 FP16 的 OPT-175B ，运行推理至少需要 8 个 GPU 。但是，应用 BCQ 格式进行量化后，LUT-GEMM 能够只使用单个 GPU 执行推理，同时保持可比的整体延迟。值得注意的是，当比较相同的 3-bit 量化场景时（weight-only 和row-wise ），使用 LUT-GEMM 的 latency for token generation 比 GPTQ 库降低了 2.1 倍。这种显著的延迟减少主要归因于 LUT-GEMM 可以直接接受 quantized weights 的能力，从而消除了 dequantization 的需要。

   

2. 让我们证明 LUT-GEMM 的灵活特性（归因于 extended BCQ 格式）可以加速现有的 uniform quantization方法。Table 6 显示了使用 GPTQ 方法在各种 $q$$q$ 和 $g$$g$ 的配置下，OPT-175B 的困惑度。该 Table 还显示了 LUT-GEMM （不包括 FP16 ）实现的相应延迟（per generated token）。结果清楚地表明：随着 $q$$q$ 的减小，LUT-GEMM 提供了更低的延迟，尽管过小的 $g$$g$ 可能会对延迟产生轻微的不利影响。

   总之，通过集成 LUT-GEMM 和 GPTQ ，以可接受的困惑度增加为代价，可以将运行 OPT-175B 推理所需的 GPU 数量从 8 个降低到 1 个，同时保持高性能。值得强调的是，如果包含 dequantization ，则无法实现这样的性能改进。

   

7.5 使用 Quantized Weights 的上下文处理

1. 如前所述，生成式语言模型推理由两个阶段组成：使用 input context 的 summarization 、以及 generation ，如 Figure 3 所示。这些阶段需要不同的 batch size 。summarization 允许并行处理多个 tokens ，而generation 由于其自回归特性是 single-batch operation 。因此，生成式语言模型的推理需要平衡：受限于计算（高并行的上下文处理）和受限于内存（低并行的 generation ）。

   我们提出的推理策略涉及存储 quantized weights （使用 extended BCQ ）。然后这些权重：

   • 1)：在上下文处理（context processing ）阶段 dequantized 从而执行 full-precision cuBLAS 的矩阵乘法。

   • 2)：并在 generation 阶段作为 LUT-GEMM 的输入。

   请注意，即使在上下文处理过程中，weight quantization 对有效的内存使用也是必不可少的。此外，由于 weight reuse ratio 很高，context processing 阶段的 dequantization latency 相比 generation 阶段较低。因此，LUT-GEMM 是 generation 阶段的理想方法，因为 generation 阶段通常主导整体推理延迟，因为需要生成更多的 tokens （生成式语言模型的常见要求）。

八、K-bit Inference Scaling Laws [2022]

论文：《The case for 4-bit precision: k-bit Inference Scaling Laws》

1. 大型语言模型（LLM ）广泛用于 zero/few-shot inference，但由于其庞大的内存占用（175B 参数的模型高达 352GB GPU 内存）和高延迟，这些模型使用起来具有挑战性。然而，内存和延迟主要由模型的参数中的比特总数决定。因此，如果我们通过量化来减少 model bits，我们可以期望模型的延迟会相应地减少，可能以任务准确率为代价（《Gptq: Accurate post-training quantization for generative pretrained transformers》、《nuqmm: Quantized matmul for efficient inference of large-scale generative language models》、 《Zeroquant: Efficient and affordable post-training quantization for large-scale transformers》）。

   由于我们可以将训练好的模型的参数量化到任意 bit-precision ，这引出了一个问题：给定当前的 base 方法从而用于 model quantization ，为了在准确率和 total model bits 之间取得最佳 trade-off ，应该使用多少比特？例如，如果我们有一个 4-bit 精度的 60B 参数模型、以及一个 8-bit 精度的 30B 参数模型，哪个模型的准确率会更高？为了研究这种 trade-offs ，采用 scaling laws（《Scaling laws for neural language models》、《Scaling laws for autoregressive generative modeling》） 的角度是很有帮助的，它们评估变量的基本趋势从而推广单个数据点。

   在本文中，我们研究了 zero-shot quantization 的 bit-level inference scaling laws ，以确定在给定模型 total bits 数量的情况下，什么精度可以最大化 zero-shot accuracy 。我们的主要发现是：在所有测试的模型规模和模型族中，4-bit 参数都可以为固定数量的 model bits 提供最佳性能。

   我们研究了五个不同的模型族，OPT 、Pythia/NeoX、GPT-2、BLOOM 和 BLOOMZ ，参数范围从 19M 到 176B 不等，精度范围从 3-bit 到 16-bit 。此外，我们运行了超过 35,000 个 zero-shot experiments，以测试量化精度的许多最近研究的进步，包括底层数据类型和 quantization block size。我们发现，将精度稳步从 16-bit 降低到 4-bit 可以在固定数量的 model bits 下提高 zero-shot 性能；而在 3-bit 时，zero-shot 性能会下降。这种关系贯穿了所有被研究的模型，并且在从 19M 参数扩展到 176B 参数时没有改变，这使得 4-bit 量化在所有测试案例中都是通用的最佳选择。

   此外，我们分析了哪些量化方法可以改进 bit-level scaling 、而哪些量化方法会降级（degrade ） bit-level scaling 。我们发现，在 6-bit 到 8-bit 精度下，我们测试的所有量化方法都无法改进 scaling behavior。对于 4-bit 精度，数据类型和小的quantization block size 是增强 bit-level scaling 趋势的最佳方法。我们发现 quantile quantization 数据类型和浮点数据类型是最有效的，而整数类型和 dynamic exponent 数据类型通常产生较差的 scaling 趋势。对于大多数 4-bit 模型，在我们的研究中，64 到 128 之间的 block size是最佳的。

   根据我们的结果，我们可以对使用 zero-shot quantized models 进行推理提出直接的建议：始终使用 4-bit 模型、以及小的 block size 、以及浮点数据类型。如果需要在 total model bits 和预测性能之间进行 trade-off ，保持 4-bit 精度但改变模型的参数数量。

   尽管早期的工作已经表明，通过使用 outlier-dependent quantization 可以显着提高 quantized models的预测性能（《LLM.int8(): 8-bit matrix multiplication for transformers at scale》、《Smoothquant: Accurate and efficient post-training quantization for large language models》），但我们发现这对于 bit-level scaling 并不有效。具体而言，我们分析了 3-bit OPT and Pythia 模型的不稳定性，并表明尽管这些模型可以通过 outlier-dependent quantization （我们称之为 proxy quantization）来稳定，但与 4-bit 精度相比，这并没有改进 bit-level scaling 。另一方面，我们强调 one-shot quantization 方法，即该方法通过 a single mini-batch of data 来优化 quantization ，潜在地可以扩展到 4-bit level 以下。总体而言，这些发现表明，改进 zero-shot bit-level scaling laws 的最有希望的方向是开发新的数据类型和技术，这些技术可以用高精度来量化异常值而不需要大量的 additional bits 。我们还强调了 one-shot quantization方法的潜力，作为一种实现 low-bit transformers 的方法，如果与我们的见解相结合。

   

2. 相关工作：

   • 大型语言模型的量化：最相关的工作是针对具有十亿级以上参数的大型语言模型的量化。与小型模型相比，LLM 量化具有一些独特的挑战，例如出现的异常值、以及针对 LLM 的 optimized low-bit inference。方法之间的一个主要区分因素是： zero-shot quantization 方法（它直接量化一个模型而不需要任何额外信息），以及 one-shot quantization 方法（它需要 a mini-batch of data进行量化）。虽然 one-shot 方法更加准确，例如 GPTQ 通过 a mini-batch of data 来优化量化期间的 rounding （《Gptq: Accurate post-training quantization for generative pretrained transformers》），但它们也更复杂，可能需要几个小时的优化才能使用模型。另一方面，zero-shot 方法的优点是它们可以立即使用，这使它们很容易使用，但 zero-shot 量化方法在更低的精度下通常会失败。

   • 量化方法：与我们的工作相关的另一个方面是量化方法，可以分为几类。例如，存在与 blocking and grouping 相关的方法、 centering 相关的方法、通过聚类找到 learned data types 的方法、或 direct codebook optimization 的方法。虽然我们的工作研究了 grouping and blocking，但我们只研究了一种通过整个 input tensor 的分位数（quantiles ）对相似权重进行分组的数据类型（《8-bit optimizers via block-wise quantization》）。虽然我们没有深入研究 learned data types ，但我们是第一项工作来展示这些对改进 LLM 的 bit-level scaling 是至关重要的。

   • Scaling Laws for Inference：早期关于 scaling laws 的工作强调了研究变量随规模变化的重要性，因为规模是模型性能的最佳预测指标之一（《Scaling laws for neural language models》、《A constructive prediction of the generalization error across scales》、《Deep learning scaling is predictable, empirically》）。特别是对于推理，已经有工作研究了 4-bit 与 16-bit 模型的 zero-shot 性能的 scaling 趋势（《Glm-130b:An open bilingual pre-trained model》）。我们研究了从 3-bit 到 16-bit 的精度，并分解了改善 scaling 的因素。

     《Efficiently scaling transformer inference》 的工作查看了 production setting （其中 large batch size 很常见）中的 scaling inference 。虽然他们只对量化进行了基本研究，但他们分解了导致更好 model FLOPS utilization: MFU 的因素。由于减少模型的 bit-precision 可以提高 MFU ，这与我们研究 bit-level scaling 的方法类似。主要区别在于：我们改变模型的 bit-width ，并研究消费者和小型组织常见的 small batch size 。

8.1 背景知识

1. 对于 LLM，减少模型的 bits 数量与推理延迟（ inference latency ）直接相关，这一点可能并不直观。接下来将阐述这种关系的背景知识。之后，我们将介绍quantization 的数据类型和方法。

8.1.1 Inference Latency 和 Total Model Bits 的关系

1. 尽管我们的工作的主要目标是为大型语言模型找到 model bits 和 zero-shot accuracy 之间的最佳 trade-offs ，但 total model bits 也与inference latency密切相关。整体的计算延迟（从计算开始到结束的时间）主要由两个因素决定：

   • (1) ：从主内存（mainn memory）加载数据到缓存和寄存器需要多长时间。

   • (2)：执行计算需要多长时间。

   例如，对于现代硬件（如 GPU），加载一个 number 通常需要比用那个 number 进行算术运算花费 100 倍以上的时间（《Dissecting the nvidia turing t4 gpu via microbenchmarking》、《A not so simple matter of software》)。因此，减少从主内存加载数据的时间通常是加速整体计算延迟（overall computation latency）的最佳方法。这种减少主要可以通过 caching 、以及更低精度的 numbers 来实现。

2. 如果两个矩阵都不完全适合设备的 L1 缓存，caching 可以将矩阵乘法的总延迟减少 10 倍或更多（《Dissecting the nvidia turing t4 gpu via microbenchmarking》）。在矩阵乘法中，$\mathbf{B}\mathbf{W}=\mathbf{H}$$\mathbf B \mathbf W= \mathbf H$ ，其中 $\mathbf{B}$$\mathbf B$ 是 batched input ，$\mathbf{W}$$\mathbf W$ 是参数矩阵，我们加载 $\mathbf{b}$$\mathbf b$ 的每一行和 $\mathbf{W}$$\mathbf W$ 的每一列并将它们相乘，因此每个行/列会从全局内存（ global memory ）进行多次加载，可以被缓存。

   如果 $\mathbf{B}$$\mathbf B$ 完全适合 L1 缓存，则不可能进行重用，因为 $\mathbf{W}$$\mathbf W$ 和 $\mathbf{B}$$\mathbf B$ 都只从全局内存加载一次。对于 RTX 3090 or RTX 4090 GPU ，这发生在 inference batch size 低于 60 or 200 时。因此，在这些 batch size 以下，caching 是无效的，inference latency 完全由从加载 $\mathbf{W}$$\mathbf W$ 的内存来决定。

   因此，在 mini-batch 适合 L1 缓存的情况下，可以通过使用较小的 $\mathbf{W}$$\mathbf W$ （即，更小的模型、或通过压缩现有模型从而使用 lower bit-precision per parameter ）从而来减少推理延迟。例如，除了为 quantization 改善 rounding 的算法创新之外，《Gptq:Accurate post-training quantization for generative pretrained transformers》 还为 “ 16-bit 浮点输入且 3-bit 整数型权重” 开发了 inference CUDA kernels，与“ 16-bit 浮点输入且 16-bit 浮点权重” 相比，这为 OPT-175B 带来了高达 4.46 倍的 inference latency 改善，接近 5.33 倍的 model bits 减少。因此，对于 small inference batch sizes，total model bits 的减少与 inference latency 高度相关。我们在附录 E 中提供了 roofline model 和初步的 unoptimized implementations 的数据。

8.1.2 数据类型

1. 这里我们简要概述被研究的的数据类型。有关这些数据类型的完整规范，请参见附录 A 。我们使用四种不同的数据类型：

   • 对于整数类型和浮点数据类型，使用 IEEE 标准。我们的浮点数据类型具有 $2^{E-1}$$2^{E-1}$ 的 exponent bias，其中 $E$$E$ 是 exponent bits 。

   • 我们还使用分位数量化（quantile quantization ），这是一种无损最大熵量化数据类型（lossy maximum entropy quantization data type）（《8-bit optimizers via block-wise quantization》），其中每个 quantization bin 包含相等数量的值。这确保每个 bit pattern 出现的频率相等。

     quantile quantization 可以被定义为：

     $$\begin{array}{}\text{(12)}& q_i=\frac{Q_X\left(\frac{i}{2^k+1}\right)+Q_X\left(\frac{i+1}{2^k+1}\right)}{2}\end{array}$$

     其中：

     • $Q_X(\cdot )$$Q_X(\cdot)$ 为 quantile function，它是累计分布函数的逆函数 $Q_X=F_X^{-1}$$Q_X=F_X^{-1}$ 。

     • $k$$k$ 为 bit 数量；$i$$i$ 表示第 $i$$i$ 个 bin ，$i=0,\cdots ,2^k-1$$i=0,\cdots,2^k-1$ ；$q_i$$q_i$ 表示quantile quantization 的第 $i$$i$ 个 value 。

     我们使用 SRAM Quantiles 算法来估计 $Q_X(\cdot )$$Q_X(\cdot)$ ，它通过 input tensor 的经验累计分布函数来逼近 input tensor 的 quantiles 。

   • 最后，我们使用动态指数量化（dynamic exponent quantization ）（《8-bit approximations for parallelism in deep learning》），它使用 indicator bit 将 exponent bit region 和 linear quantization region 分开。通过移动 indicator bit ，exponent 可以在不同的值之间变化。这种数据类型对于数值变化跨越多个数量级的张量具有较低的量化误差。

     

8.1.3 Blocking / Grouping

1. 量化精度（quantization precision ）在一定程度上取决于是否所有 quantization bins 被均匀地使用。例如，4-bit 数据类型有 16 个 bins，但如果平均只使用了 8 个 bins，那么就相当于 3-bit 数据类型。因此，帮助增加数据类型中所有 quantization bins 的平均使用率的方法可以增加量化精度。在这一小节中，我们介绍了 blocking 。blocking/grouping 方法将张量分割成更小的 blocks ，并独立地对每个 block 进行量化。这有助于将异常值限制在特定的 blocks 中，从而增加其他 blocks 使用的 bins 的平均数量，进而提高平均的量化精度。

2. Blocking/Grouping：blocking 和 grouping 是相似的概念。

   • 在 grouping 中，我们沿着某个维度将张量细分为 $n$$n$ 个部分，并为每个子张量（称为 group）分配其自己的归一化常数 $c$$c$ （通常是该组的 absolute maximum ）。

   • 在 blocking 中，我们将张量看作是一个一维的数值序列，并将这个序列划分为大小为 $n$$n$ 的部分，称为 blocks 。

   在我们的工作中，我们使用 blocking ，因为与 grouping 不同，它提供了 additional bits per parameter 的指标，独立于 hidden dimension 。例如，使用 16-bit normalization constants 和 block size 64 意味着，我们每 64 个参数有额外的 16 bits，或者说使用 block-wise quantization 的每个参数增加了 16/64=0.25 bit 的成本；这对于每个模型都是成立的，与 hidden dimension 无关。对于 grouping ，确切的成本将取决于每个模型的 hidden dimension 大小。

3. 对于 block-wise quantization，我们使用 《8-bit optimizers via block-wise quantization》 的符号，其中定义了：具有 k bits 的 block-wise quantization 、block-size $B$$B$ 、具有 $n$$n$ 个元素的输入张量 $\mathbf{T}$$\mathbf T$ ，共有 $n/B$$n/B$ 个 blocks 。

   如果并且我们用索引 $b$$b$ 定义每个 block 在 $0,\cdots ,n/B$$0,\cdots,n/B$ 中的索引。那么，block-wise quantization 可以通过找到 quantization map 的值的最小距离来定义：

   $$\begin{array}{}\text{(13)}& \arg min\sum _b|{\hat{\mathbf{T}}}_b-{\mathbf{T}}_b|,0<b<B\end{array}$$

   其中：

   • ${\mathbf{T}}_b$$\mathbf T_b$ 表示第 $b$$b$ 个 block，${\hat{\mathbf{T}}}_b$$\hat{\mathbf T}_b$ 为逆量化之后的结果。

   • ${\hat{T}}_{b,j}={\mathcal{Q}}_k^{\text{dequant}}({\mathcal{Q}}_k^{\text{map}}(T_{b,j}))$$\hat T_{b,j} = \mathcal Q_{k}^{\text {dequant}}\left(\mathcal Q_k^\text{map}(T_{b,j})\right)$ ， ${\mathcal{Q}}_k^{\text{map}}(\cdot )$$\mathcal Q_k^\text{map}(\cdot)$ 为量化函数， ${\mathcal{Q}}_k^{\text{dequant}}(\cdot )$$\mathcal Q_k^\text{dequant}(\cdot)$ 为逆量化函数。

8.2 通过 Proxy Quantization 实现 Outlier-dependent Quantization

1. 大型语言模型中出现的异常值特征会导致大的量化误差和严重的性能退化。尽管已经证明使用 16-bit 输入和 8-bit 权重就足以避免这种破坏（《Glm-130b:An open bilingual pre-trained model 》），但如果我们使用 16-bit 输入和低于 8-bit 精度的权重，异常值特征是否仍会导致性能退化还不清楚。

   为此，我们通过 proxy quantization 开发了 outlier-dependent quantization ，其中我们对与 outlier feature dimensions 对应的权重进行更高精度的量化，以测试权重需要多少精度。一个重大挑战是，每个模型具有不同数量的异常值特征，异常值部分地取决于每个 zero-shot task 不同的输入。因此，我们寻求一个 model-independent 的方法，该方法在所有模型和任务上都具有恒定的内存占用。

   在初步实验中，我们注意到 《LLM.int8(): 8-bit matrix multiplication for transformers at scale》 开发的准则（即，用阈值来衡量 hidden states 从而检测异常值特征）是不可靠的，因为它取决于 hidden state 的标准差。这会引起问题，因为对于诸如 OPT 之类的模型，hidden state 的标准差在后面的层中增加，这会导致检测到太多的异常值。这也已经得到 《Glm-130b: An open bilingual pre-trained model》 的注意。通过检查 OPT 模型中的这种异常情况，我们发现检测 outlier dimensions 的更好测量是： previous layer 中每个 hidden unit 权重的标准差。产生异常值的 hidden unit 权重的标准差，要比其他维度的标准差高出 20 倍。我们在附录 D 中提供了标准差与异常值大小之间关系的相关性分析的进一步数据。

   由于神经网络的全连接特性，每一个 hidden unit 会与多个下一层的hidden unit 相连接。因此，每个 hidden unit 对应了多个权重。

    

   

2. 有了这一见解，我们开发了所谓的 proxy quantization 。proxy quantization 与输入无关，因此与任务无关，因为它使用每个层 hidden unit 权重的标准差作为哪些维度具有异常值特征的代理。例如，给定一个具有 $n$$n$ 个线性层（FFN 和注意力投影层）的transformer ，权重矩阵 ${\mathbf{W}}_i\in {\mathbb{R}}^{h\times o}$$\mathbf W_i \in \mathbb R^{h\times o}$ ，其中 $h$$h$ 是输入维度，$o$$o$ 是输出维度（即 $o$$o$ 个 hidden units ）。对于第 $i+1$$i+1$ 层，我们定义要被以高精度量化的索引集合 ${\mathcal{J}}_{i+1}$$\mathcal J_{i+1}$ 为：

   $$\begin{array}{}\text{(14)}& {\mathcal{J}}_{i+1}=\arg \underset{1\le j\le o}{max}\text{std}({\mathbf{W}}_{i,:,j})\end{array}$$

   其中：$\text{std}(\cdot )$$\text{std}(\cdot)$ 是输出维度 $o$$o$ 上的标准差。

   上式的物理含义为：寻找 ${\mathbf{W}}_i$$\mathbf W_i$ 上标准差最大的列。

   如果 ${\mathbf{W}}_{i+1}$$\mathbf W_{i+1}$ 的输入维度（即，行的编号）在集合 ${\mathcal{J}}_{i+1}$$\mathcal J_{i+1}$ 中，则我们将其量化为 16-bit ；否则为 k-bit 。

   第 $i+1$$i+1$ 层的输入为：$\mathbf{X}{\mathbf{W}}_i=(\mathbf{X}{\overrightarrow{\mathbf{w}}}_{i,1},\cdots ,\mathbf{X}{\overrightarrow{\mathbf{w}}}_{i,o})$$\mathbf X \mathbf W_i = \left(\mathbf X \mathbf {\vec w}_{i,1}, \cdots,\mathbf X \mathbf {\vec w}_{i,o} \right)$ 。假设原始输入 $\mathbf{X}$$\mathbf X$ 的方差很小，那么：如果 $\mathbf{W}$$\mathbf W$ 的第 $j$$j$ 列方差较大，则第 $i+1$$i+1$ 层的第 $j$$j$ 列的方差也较大。

8.3 实验

1. 配置：

   • 在我们的实验中，我们使用 16-bit inputs 和 k-bit quantized parameters，$3\le k\le 8$$3\le k \le 8$ 。注意力矩阵不进行量化，因为它们不包含参数。我们还使用不包含任何量化的 16-bit baseline （ 16-bit 浮点数）。

   • 为了衡量 k-bit quantization 方法的推理性能，我们使用 The Pile 的 CommonCrawl 子集上的困惑度指标，以及 EleutherAI LM Evaluation harness 上的平均 zero-shot 性能。具体而言，对于 zero-shot setting ，我们在 GPT-2 setting 下使用 EleutherAI LM eval harness ，在 LAMBADA、Winogrande、HellaSwag 和 PiQA 等任务。

     选择这些特定的 zero-shot 任务主要是由于前人的工作。但是，在我们的评估中，我们发现困惑度是一个更好的指标，因为每个样本的 continuous value 导致 less noisy evaluations 。这也得到了 《Gptq: Accurate post-training quantization for generative pretrained transformers》的注意。例如，当使用困惑度来评估数据类型时，quantile quantization 是最佳的数据类型。然而，当我们使用 zero-shot accuracy 作为评估指标时，由于 zero-shot accuracy 存在更多噪声，浮点数据类型有时会较好。

     此外，我们发现在超过 35,000 次 zero-shot experiments 中，CommonCrawl 困惑度与 zero-shot performance 之间的皮尔逊相关系数为 -0.94 。这突出表明：困惑度用于评估已经足够，且更可取。

     一个严重的缺点是困惑度难以解释。因此，为了清楚起见，我们在论文主体中使用了 zero-shot accuracy ，但鼓励读者使用附录中的困惑度指标进行复现和比较。由于困惑度评估非常可靠，我们可以通过评估 a small number of samples 的困惑度来复制我们的工作，这使得构建 scaling laws 的计算量不那么大。

   • Scaling Laws：我们试图将 power laws 拟合我们的数据，但我们发现关于参数数量和 bit-precision 的双变量幂函数（bivariate power function ）的拟合效果很差。但是，当我们拟合线性插值来表示 scaling curves 时，我们发现不同 bit-precisions 几乎是平行的，这表明不同精度的 scaling 趋势可以由一个 base function 、以及每个 bit-precision 的偏移量来准确表示。因此，我们选择使用线性插值来表示 scaling 趋势。

8.3.1 Bit-level Inference Scaling Laws

1. 主要结果如 Figure 2所示，其中描绘了在 Lambada 、PiQA、HellaSwag 和 Winogrande 任务上的平均 zero-shot accuracy，给定 OPT 、BLOOM 、Pythia 和 GPT-2 的 total number of bits ，但是参数精度从 3-bit 到 16-bit 。我们得出以下观察：

   • 对于给定的 zero-shot 性能，4-bit 精度对于几乎所有模型族和模型规模都提供了最佳的 scaling 。唯一的例外是 BLOOM-176B ，其中 3-bit 略好但不明显。

   • scaling curves 几乎是平行的，这表明 bit-level scaling 在很大程度上与 scale 无关。3-bit 量化是一个例外。

     即，Bit-level Inference Scaling Law 与 bit 无关。

   • 对于 3-bit 推理，Pythia 和 OPT 不稳定，其中最大的 Pythia/OPT 模型的性能接近随机的准确率。

   这个实验的量化是采用类似于 LLM.int8() 的方式进行的，其中高精度量化的权重矩阵列的集合为：

   $$\begin{array}{}\text{(15)}& {\mathcal{J}}_{i+1}=\arg \underset{1\le j\le o}{max}\text{std}({\mathbf{W}}_{i,:,j})\end{array}$$

   

   

   

8.3.2 改进 Scaling Laws

1. 鉴于 Figure 2 中的 main scaling results ，一个重要的后续问题是我们如何进一步改进 scaling 趋势。为此，我们运行了超过35,000 次 zero-shot 实验，以测试 quantization precision 的许多最近研究进展，包括基础数据类型、quantization block size 、以及 outlier-dependent quantization 。

   这些方法通常以少量 additional bits 为代价来改进量化误差。例如：

   • block size = 64 且使用 16-bit quantization constant，意味着每 64 个参数增加 16 个 additional bits （或每个参数增加 16/64 = 0.25 bit）。

   • outlier-dependent quantization 以 16-bit 精度存储 top p 的权重向量，从而将每个参数的 bits 增加 $p(16-k)$$p(16-k)$ ，其中 $k$$k$ 是常规权重的精度。例如，对于 $p=0.02$$p = 0.02$ 和 $k=4$$k = 4$ ，额外的内存占用为 0.24 bits per parameter 。

2. 6-bit precision 到 8-bit precision 没有改善 scaling ：我们将所有可能的量化方法（数据类型、blocking ）与 6-bit 到 8-bit 量化组合，我们发现这些方法都没有改进 bit-level scaling （参见附录 C.3 ）。对于 6-bit 到 8-bit 精度，模型参数似乎有足够的精度，与 16-bit 权重相比，不会造成明显的性能降低。因此，scaling behavior 只能通过其它方法使用低于 6-bit 的精度（而不是提高 quantization precision ）来改进。

   

   

3. small block size 改善了 scaling ：对于 3-bit 至 5-bit 精度，我们确实看到各种量化方法在 scaling 上的改进。 Figure 3 显示，对于 4-bit Pythia 模型，使用 small block size 可以实现可观的 bit-level scaling 改进。为了给出这一 improvement 的视角：从 block size = 1024 降低到 block size = 64 增加了 0.24 bits per parameter，但 zero-shot accuracy 的改进几乎与从 4-bit 提升到 5-bit 一样大。因此，对于 4-bit precision ，使用 small block size 增加了几个 extra bits 从而提高了 zero-shot accuracy 。

   除了 Pythia 之外，GPT-2 模型也有很大程度的改进。BLOOM 、BLOOMZ 和 OPT 模型有明显改进，但与 Pythia 和 GPT-2 相比，改善的幅度较小，（参见附录 C.2 ）。这种关系可能起源于 emergent outlier features。

   对于 5-bit 模型，使用 small block size的改进很小但仍然显著。 small block size可显著改进 3-bit 的scaling ，但仍无法与 4-bit precision 的 scaling 相竞争。

   

   

   

4. 数据类型改善了scaling：从 Figure 3 中可以看出，数据类型改善了 4-bit Pythia 的 scaling 趋势。具体而言，quantile quantization 和浮点数据类型提供了比整数类型和 dynamic exponent quantization 更好的 scaling 。

   我们发现：

   • quantile quantization 通常是所有模型、scales、精度中最好的数据类型（参见附录 C.5 ）。

   • 浮点数据类型似乎优于整数类型，只有少数例外：整数类型对于 5-bit 优于浮点类型。这似乎是因为浮点数据类型高度依赖指数位和小数位之间的平衡，根据特定的 bit precision ，浮点数据类型可以更好或更差。

   

   

5. outlier-dependent quantization 提高了稳定性，但没有提高 scaling：最后，我们注意到了 OPT 和 Pythia 中的 3-bit 不稳定性，并将其与 emergent outlier features 相关联（《LLM.int8(): 8-bit matrix multiplication for transformers at scale》、《Smoothquant: Accurate and efficient post-training quantization for large language models》）。如果我们使用 proxy quantization将 2% 最重要的异常维度量化为16-bit 而不是 3-bit，我们可以提高 3-bit Pythia and OPT 模型的稳定性和整体 scaling 。这在 Figure 4(left) 的 OPT 中显示。然而，尽管有这一改进，4-bit precision 仍然提供了更好的scaling 。对于 4-bit precision ，Figure 4(right) 所示的 outlier-dependent quantization 在 scaling 上没有好处，这意味着尽管使用 proxy quantization 时 3-bit precision 有可观的改进，但 4-bit precision 仍是最佳的。因此，似乎异值常特征不需要超过 4-bit precision 的权重就可以提供最佳的 bit-level scaling 。

   

8.4 建议和未来工作

1. 我们提出以下建议：

   • 默认使用 4-bit quantization 进行 LLM 推理，因为它在 total model bits 和 zero-shot accuracy 之间提供了最佳 trade-offs。

   • 使用 128 或更小的 block size 来稳定 4-bit quantization 并提高 zero-shot 性能。

   • 使用浮点类型或 quantile quantization 数据类型。在某些情况下，整数类型可能更可取，从而改进 inference latency （依赖于实现和硬件支持）。

   需要高于 4-bit precision 的一个场景是：当 GPU 具有足够的内存来容纳更高的 bit precision 而不是容纳更大的模型时。例如，48 GB GPU 有足够的内存以 5-bit precision 使用 66B 参数模型，但不能以 4-bit 容纳 175B 参数模型。因此，如果需要最大化 zero-shot accuracy ，则对于这种场景，5-bit precision 且 66B 参数模型是可取的。

2. 未来工作的有希望方向：

   • 我们的结果表明当前 4-bit precision 在 bit-level 是最有效率的，但我们也展示了 3-bit scaling 可以明显地被改进。因此，一个有希望的研究方向是关注 4-bit 以下的 low-bit precisions 并改善它们的 scaling 趋势。已经证明 one-shot quantization（例如使用输入样本优化 quantization 的 GPTQ ）在 low-bit precisions 更有效（《Gptq: Accurate post-training quantization for generative pretrained transformers》）。Table 1 显示，与 zero-shot 3-bit Float 相比，2-bit GPTQ with blocking 可以获得更好的性能。这突出表明 one-shot 方法对于 low-bit precisions 非常有希望。

     

   • 另一方面，Figure 5 也表明，与 3-bit Float with a blocksize of 64 相比，3-bit GPTQ without blocking的 scaling 更差；而 4-bit GPTQ without blocking 与 4-bit Float with a blocksize of 64 的scaling 相似。从这些结果可以看出，我们从 zero-shot scaling laws 中获得的见解可以传递到 one-shot quantization 方法。这表明 zero-shot quantization research 非常适合于分离和理解 quantization scaling 中的各个因素，而 one-shot 方法可以最大化性能。相比之下，当前的 one-shot方法研究起来非常昂贵。例如，仅对 OPT-175B 和 BLOOM-176B 模型重复我们的 scaling experiments ，估计需要 5120 GPU days 的计算。因此，zero-shot quantization scaling insights 和 one-shot quantization methods的组合可能产生最佳的未来方法。

     

3. 我们工作中未解决的一个挑战是数据类型也应该能在硬件级别上高效地使用。例如，尽管 quantile quantization 数据类型展示最佳的 scaling 趋势，但它需要一个小的 lookup table，这在高度并行的 setup 中很难实现，因为并行内存访问（parallel memory access ）通常会由于序列化而导致性能较差。这个问题可以通过设计新的数据类型来解决，其中这个数据类型既具有 bit-level scaling 效率、又具有硬件效率。解决这个问题的另一种方法是硬件设计：我们能设计什么硬件来高效地使用 quantile quantization 等数据类型？

4. block-size 和 outlier-dependent quantization 都可以改进异常值的 quantization precision 。虽然 outlier-dependent quantization在 scaling 上没有改进，但是有理由表明：存在 unknown quantization 方法可以帮助处理异常值，并同时改进 scaling 趋势。因此，未来研究的另一个重点应该集中在最大限度地保留异常值信息，但是最小化使用 additional bits 。

8.5 讨论和局限性

1. 局限性：

   • 尽管我们运行了超过 35,000 次实验，但一个主要局限性是我们没有考虑某些类别的量化方法。例如，存在一些量化方法，其中数据类型使用额外的输入数据进行优化、或数据类型仅从模型的权重进行优化。仅从权重进行优化，与我们研究中最有效的 quantile quantization 类似。因此，这暗示这样的量化方法可以改进 inference 的 scaling ，但我们错过了将其纳入研究的机会。然而，我们的研究是重要一步从而认识到这些方法对于优化 model-bits-accuracy trade-off 的重要性，而这种视角以前不存在。

   • 另一个局限性是缺乏 optimized GPU implementations 。目前还不清楚其他依赖 lookup tables 的数据类型是否能实现明显的加速。然而，我们的 Int/Float 数据类型可以实现高效的实现；即使对于其他数据类型，我们的结果对于未来产生 strong scaling and efficient implementations的数据类型的开发仍然有用。

   • 虽然我们只通过研究 model-bits-accuracy trade-off 间接地研究了 latency-optimal 视角，但 latency-optimal 视角的一个实际局限性是：low-bit models with 16-bit inputs 可能是 less latency efficient 的，如果这样的模型被部署用于许多用户（《Efficiently scaling transformer inference》 ）。给定一个 busy deployed API ，其中每秒处理数千个请求，那么large mini-batch 将不再 fit cache 。这意味着在这种情况下，bit-level scaling laws与 inference latency 的相关性会越来越小。对于这样的高吞吐量系统，需要建模 low-bit weights and low-bit inputs 的 scaling laws 来研究最佳的 inference latency scaling 。简而言之，我们的 scaling laws 仅对 mini-batch 不适合设备 L1 cache 的 case 有效；除此之外，需要一套新的 scaling laws 。

   • 最后一个局限性是，加载权重矩阵只是 inference latency 优化的一部分。例如，如果不优化 attention operations ，多头注意力可以占据很大一部分推理延迟（《Sparseis enough in scaling transformers》、《Efficiently scaling transformer inf》）。然而，模型的整体内存占用仍然被减小，这使得在 GPU 内存有限时，大型语言模型更易于使用。

九、SparseGPT[2023]

论文：《SparseGPT: Massive Language Models Can be Accurately Pruned in One-Shot》

1. 来自 Generative Pretrained Transformer: GPT 家族的大型语言模型（Large Language Models: LLMs ）在广泛的任务中展现出了显著的性能，但由于其巨大的大小和计算成本而难以部署。例如，性能最佳的 GPT-175B 模型拥有 175B 个参数，即使以半精度（FP16 ）格式存储也至少需要 320GB （以 1024 为基数计数）的存储空间，这意味着推理至少需要 5 个 80GB A100 GPU 。因此，通过模型压缩来降低这些成本自然受到了广泛的关注。到目前为止，几乎所有现有的 GPT 压缩方法都集中在量化（《LLM.int8(): 8-bit matrix multiplication for transformers at scale》、《ZeroQuant: Efficient and affordable post-training quantization for large-scale transformers》、《Smoothquant: Accurate and efficient post-training quantization for large language models》 、《GPTQ: Accurate post-training compression for generative pretrained transformers》）上，即降低模型 numerical representation 的精度。

   与量化相辅相成的压缩方法是剪枝（pruning ），即移除网络元素，从移除单个权重（非结构化剪枝）到移除更高粒度的结构（如权重矩阵的行或列，即结构化剪枝）。剪枝具有悠久的历史（《Optimal brain damage》、《Optimal brain surgeon and general network pruning》），并且在计算机视觉模型、以及较小规模的语言模型中得到了成功的应用（《Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks》）。然而，性能最佳的剪枝方法需要对模型进行大量的重新训练以恢复准确率。反过来，这对于 GPT-scale 的模型来说非常昂贵。尽管存在一些准确的 one-shot pruning 方法（《Accelerated sparse neural training: A provable and efficient method to find N:M transposable masks》、《Optimal Brain Compression: A framework for accurate post-training quantization and pruning》），即无需重新训练模型就可以进行压缩，但不幸的是，这些方法在应用于数十亿参数的模型时也变得非常昂贵。因此，到目前为止，准确地剪枝数十亿参数模型的工作几乎为空白。

   在本文中，我们提出了 SparseGPT ，这是第一种在成百上千亿参数模型规模上高效工作的 accurate one-shot pruning 方法。SparseGPT 的工作原理是将剪枝问题简化为大量的稀疏回归（sparse regression ），然后通过一种新的近似稀疏回归求解器（approximate sparse regression solver）来解决这些实例。该求解器足够高效，可以在几小时内在最大的公开可用GPT 模型（175B 参数）上单 GPU 执行。同时，SparseGPT 足够准确，在裁剪后仅有微乎其微的准确率下降，无需任何微调。例如，当在最大的公开可用的生成式语言模型（OPT-175B 和 BLOOM-176B ）上执行时，SparseGPT 可以在 one-shot 中诱导（induce ）50-60% 的稀疏度，accuracy loss 很小，无论是从困惑度还是 zero-shot accuracy 来衡量。

   我们的实验结果（我们在 Figure 1 和 Figure 2 中提供了概览）得出以下观察。

   • 首先，如 Figure 1 所示，SparseGPT 可以在例如 OPT 家族的 175B 参数变体中诱导高达 60% 的 uniform layer-wise sparsity，accuracy loss 很小。相比之下，目前已知的可以轻松扩展到这种规模的唯一 one-shot baseline （Magnitude Pruning ，参考《A simple and effective method for removal of hidden units and weights》 、 《Learning both weights and connections for efficient neural networks》）只能在稀疏度达到 10% 时保持准确率，而在稀疏率超过 30% 时则完全崩溃。

   • 其次，如 Figure 2 所示，SparseGPT 还能在更严格但对硬件友好的 2:4 和 4:8 半结构化稀疏模式中准确地施加稀疏性（《Accelerating sparse deep neural networks》）；不过对于更小的模型，相对于 dense baseline ，其准确率会有所下降。

   

   一个关键的 positive 发现是，如 Figure 2 所示，更大的模型更容易压缩：在固定的稀疏度下，它们相对于较小的对应模型，损失更少的准确性。（例如，OPT 和 BLOOM 家族中最大的模型可以稀疏化到 50% 而困惑度几乎无增加。）此外，我们的方法允许稀疏度与 weight quantization 技术（《GPTQ: Accurate post-training compression for generative pretrained transformers》）结合：例如，我们可以在 OPT-175B 上同时诱导 50% 的 weight sparsity 和 4-bit weight quantization，而困惑度几乎无增加。

   一个显著的特点是，SparseGPT 完全是局部的，意味着它仅依赖于 weight updates ，而 weight updates 是为保留每个层的 input-output relationship 而设计的，而 weight updates 是在没有任何 global gradient information 的情况下计算的。因此，我们发现直接在 dense pretrained models 的 “邻域” 中识别这样的 sparse models 是令人惊讶的，其中 sparse models 的输出与 dense model 的输出有极高的相关性。

2. 相关工作：

   • 剪枝的方法：据我们所知，我们是首次研究裁剪大型 GPT 模型的，例如超过 10B 参数的模型。针对这个令人惊讶的 gap 的一个解释是：大多数现有的剪枝方法，例如（《Deep compression: Compressing deep neural networks with pruning, trained quantization and Huffman coding》、《The state of sparsity in deep neural networks》、《Well-tuned global magnitude pruning can outperform most bert-pruning methods》）在剪枝后需要大量的 retraining 从而恢复准确率，而 GPT-scale 的模型无论是训练还是微调通常都需要大量的计算和参数调优（《OPT: Open pre-trained transformer language models》）。 SparseGPT 是一种 GPT-scale 模型的 post-training 方法，因为它不执行任何微调。到目前为止，post-training pruning 方法只在经典的 CNN 或 BERT-style 模型的规模下进行了研究，这些模型的参数比我们关注的模型少 100-1000 倍。我们在正文部分讨论了这些方法的 scaling 的挑战，以及其与 SparseGPT 的关系。

   • Post-Training Quantization：相比之下，对公开的 GPT-scale 模型进行 post-training quantization 有大量工作。具体来说：

     • ZeroQuant 、LLM.int8() 和 nuQmm 方法研究了对数十亿参数模型进行 round-to-nearest quantization的可行性，表明通过这种方法可以实现权重的 8-bit quantization ；但由于存在 outlier features ，activation quantization 可能很困难。

     • 《GPTQ: Accurate post-training compression for generative pretrained transformers》 利用近似的二阶信息准确地将权重量化到 2-4 bits；对于最大的模型，并展示了当与有效的 GPU kernels 相结合时，生成式的 batch-size = 1 的推理可以获得 2-5 倍的加速。

     • 后续工作 《Smoothquant: Accurate and efficient post-training quantization for large language models》 研究了 activation and weight quantization 的联合 8-bits 量化，提出了一种平滑的方案，减少了 activation quantization 的困难，并配合高效的 GPU kernels 。

     • 《Quadapter: Adapter for gpt-2 quantization》 通过 quadapters （可学习参数的目标是 channel-wise 地缩放 activations ，同时保持其他模型参数不变）来解决量化 activation outliers 的困难。

     • 《The case for 4-bit precision: k-bit inference scaling laws》研究了模型大小、quantization bits 和不同准确率概念之间的 scaling relationships ，观察到 perplexity scores 与跨任务汇总的 zero-shot accuracy 之间存在高度相关性。

     正如我们在正文中所示，SparseGPT 算法可以与 GPTQ （目前 SOTA 的 weight quantization算法）结合使用，并且与 activation quantization 方法（Smoothquant 、Quadapter ）兼容。

9.1 背景知识

1. Post-Training Pruning：Post-Training Pruning 是一个实际场景，其中我们得到一个经过良好优化的模型 ${\theta }^{\ast }$$\theta^*$，以及一些校准数据（calibration data ），并且必须获得 ${\theta }^{\ast }$$θ^*$ 的压缩版本（例如 sparse and/or quantized 版本）。这一 setting 最初在 quantization 的背景下流行，最近也已成功地拓展到剪枝。

2. Layer-Wise Pruning：post-training compression 通常通过将 full-model compression 问题拆分为 layer-wise 子问题来完成，其 solution quality 通过如下的方式来衡量：给定输入 ${\mathbf{X}}_l$$\mathbf X_l$ ，测量 uncompressed layer （权重为 ${\mathbf{W}}_l$$\mathbf W_l$ ）的输出与 compressed layer 的输出之间的 $l_2$$l_2$ 误差。具体而言，对于剪枝，《Accelerated sparse neural training: A provable and efficient method to find N:M transposable masks》 将此问题表述为：对每个层 $l$$l$ 找到一个稀疏掩码 ${\mathbf{M}}_l$$\mathbf M_l$ ，具有一定的目标稠密度（target density ），以及可能的 updated weights ${\hat{\mathbf{W}}}_l$$\hat{\mathbf W}_l$，使得：

   $$\begin{array}{}\text{(16)}& \arg \underset{{\mathbf{M}}_l,\widehat{{\mathbf{W}}_l}}{min}{\Vert {\mathbf{W}}_l{\mathbf{X}}_l-({\mathbf{M}}_l\odot {\hat{\mathbf{W}}}_l){\mathbf{X}}_l\Vert }_2^2\end{array}$$

   其中 $\odot$$\odot$ 为逐元素乘法。

   然后通过 “拼接” 各个 compressed layers 来获得 overall compressed model 。

3. Mask Selection & Weight Reconstruction：上式中 layer-wise pruning 问题的一个关键方面是：掩码 ${\mathbf{M}}_l$$\mathbf M_l$ 和 remaining weights ${\hat{\mathbf{W}}}_l$$\hat{\mathbf W}_l$ 都是联合优化的，这使该问题成为 NP-hard 问题。因此，对较大的层（即，参数量较多）进行精确求解是不现实的，这导致所有现有方法都采用近似方法。

   一个特别流行的方法是：将问题分解为掩码选择（mask selection ）和权重重构（weight reconstruction ）（《AMC: AutoML for model compression and acceleration on mobile devices》、《A fast post-training pruning framework for transformers》、《Accelerated sparse neural training: A provable and efficient method to find N:M transposable masks》）。具体来说，这意味着：

   • 首先根据一些显著性标准（如权重幅值）（《To prune, or not to prune: exploring the efficacy of pruning for model compression》）选择一个 pruning mask $\mathbf{M}$$\mathbf M$ 。

   • 然后在保持掩码不变的情况下优化 remaining unpruned weights。重要的是，一旦掩码固定，上式变为一个易于优化的线性平方误差问题。

4. Existing Solvers：

   • 早期工作 （《Hypothesising Neural Nets》）将迭代线性回归应用于小型网络。

   • 更近期的 AdaPrune 方法（《Accelerated sparse neural training: A provable and efficient method to find N:M transposable masks》）通过 magnitude-based weight selection、以及应用 SGD steps 来重构 remaining weights ，在现代模型上为此问题显示了良好的结果。

   • 后续工作表明，通过消除 mask selection 和 weight reconstruction 之间的严格分离，可以进一步改进 pruning accuracy 。

   • Iterative AdaPrune （《SPDY: Accurate pruning with speedup guarantees》）在 gradual steps with re-optimization 中进行剪枝。

   • OBC （《Optimal Brain Compression: A framework for accurate post-training quantization and pruning》）引入了一个贪心求解器（greedy solver ），每次移除一个权重，并在每次迭代后通过有效的闭式方程完全重构 remaining weights 。

5. 扩展到 100B 以上参数的困难：以前的 post-training 技术都是为了准确地压缩最多几亿参数的模型，计算时间在几分钟到几小时。然而，我们的目标是使规模高达 1000 倍的模型稀疏化。

   即使是 AdaPrune 这种为理想的 speed/accuracy trade-off 而优化的方法，也需要几个小时才能使仅有 1.3B 参数的模型稀疏化（参见实验部分）；如果线性扩展到 175B Transformers ，则需要数百个小时（几周时间）。比 AdaPrune 更准确的方法至少要贵几倍（《SPDY: Accurate pruning with speedup guarantees》），或者甚至表现出比 linear scaling 更糟的扩展性（《Optimal Brain Compression: A framework for accurate post-training quantization and pruning》）。

   这表明，将现有的 accurate post-training 技术扩展到极大的模型是一项艰巨的任务。因此，我们提出了一种新的基于 careful approximations to closed form equations的 layer-wise 求解器，SparseGPT ，它可以轻松地扩展到巨大的模型，无论是运行时间还是准确性方面。

9.2 SparseGPT 算法

SparseGPT 的核心思想与 GPTQ 一致：layer-by-layer 地最小化重构误差：

$$\begin{array}{}\text{(17)}& {\Vert \overrightarrow{\mathbf{w}}\mathbf{X}-\widehat{\overrightarrow{\mathbf{w}}}\mathbf{X}\Vert }_2^2\end{array}$$

其中 $\overrightarrow{\mathbf{w}}$$\mathbf{\vec w}$ 为权重矩阵中的某一行。

$\widehat{\overrightarrow{\mathbf{w}}}$$\hat{\mathbf{\vec w}}$ 可以是 quantized weights、可以是 sparsified weights ，甚至可以同时包含稀疏化和量化。

9.2.1 Fast Approximate Reconstruction

1. 动机：如前所述，对于固定的 pruning mask $\mathbf{M}\in {\mathbb{R}}^{d_{\text{col}}\times d_{\text{col}}}$$\mathbf M\in \mathbb R^{d_\text{col}\times d_\text{col}}$ ，mask 中所有权重的最优值，可以通过求解对应于矩阵中每一行 ${\overrightarrow{\mathbf{w}}}^i$$\mathbf{\vec w}^i$ 的 sparse reconstruction 问题来精确地计算（即，采用闭式解）。

   一共有 $d_{\text{row}}$$d_\text{row}$ 行。

   总的时间复杂度为 $O(d_{\text{row}}\times d_{\text{col}}^3)$$O(d_\text{row}\times d_\text{col}^3)$。对于 Transformer 模型，这意味着总运行时间随 hidden dimmension $d_{\text{hidden}}$$d_\text{hidden}$ 的 4 次方扩展；我们需要至少减少一个 $d_{\text{hidden}}$$d_\text{hidden}$ 因子才能得到一个实用的算法。

2. Equivalent Iterative Perspective：为了推导我们的算法，我们首先必须从不同的迭代视角来看待 row-wise weight reconstruction ，使用经典的 OBS update 。对于给定的行，假设损失函数的二次逼近，对于当前权重 $\overrightarrow{\mathbf{w}}$$\mathbf {\vec w}$ 是最优的，则 OBS update ${\overrightarrow{\delta }}_m$$\vec \delta_m$ 提供了remaining weights 的最佳调整，从而来补偿移除索引 $m$$m$ 处的权重 $w_m$$w_m$ 所产生误差 ${ϵ}_m$$\epsilon_m$：

   $$\begin{array}{}\text{(18)}& {\overrightarrow{\delta }}_m=-\frac{w_m}{{\left[{\mathbf{H}}^{-1}\right]}_{m,m}}{\left({\mathbf{H}}^{-1}\right)}_{:,m},{ϵ}_m=\frac{w_m^2}{{\left[{\mathbf{H}}^{-1}\right]}_{m,m}}\end{array}$$

   由于对应于 layer-wise 裁剪 $\mathbf{W}$$\mathbf W$ 中一行的损失函数是一个二次函数，OBS 公式在这种情况下是精确的。因此，$\overrightarrow{\mathbf{w}}+{\overrightarrow{\delta }}_m$$\mathbf {\vec w}+\vec\delta_m$ 是对应于掩码 $\{m{\}}^C$$\{m\}^C$ 的 optimal weight reconstruction 。此外，给定对应于掩码 $\mathbf{M}$$\mathbf M$ 的optimal sparse reconstruction ${\overrightarrow{\mathbf{w}}}^{\mathbf{M}}$$\mathbf {\vec w}^{\mathbf M}$，我们可以再次应用 OBS 来找到掩码 ${\mathbf{M}}^{\prime }=\mathbf{M}-\{m\}$$\mathbf M^\prime = \mathbf M-\{m\}$ 的 optimal reconstruction 。因此，这意味着：我们并不是直接地求解 full mask $\mathbf{M}=\{m_1,\cdots ,m_p{\}}^C$$\mathbf M = \{m_1,\cdots,m_p\}^C$，我们可以迭代地将 OBS 应用于逐个裁剪权重 $m_1$$m_1$ 直到 $m_p$$m_p$ ，一次一个，最终会到达直接应用 full mask $\mathbf{M}$$\mathbf M$ 的闭式 regression reconstruction 相同的最优解。

   $\{m{\}}^C$$\{m\}^C$ 表示这样的掩码：裁剪位置 $m$$m$ 并保留所有其它位置。

3. Optimal Partial Updates：应用 OBS 更新 ${\overrightarrow{\delta }}_m$$\vec\delta_m$ 可能会调整 all available parameters 的值（在当前掩码 $\mathbf{M}$$\mathbf M$ 中）从而补偿对 $w_m$$w_m$ 的移除。然而，如果我们只更新 remaining unpruned weights 的权重会怎样呢？因此，我们仍然可以从误差补偿（error compensation ）中受益，仅使用子集 $\mathbf{U}$$\mathbf U$ 中的权重（即，当前掩码中尚未被更新的权重），同时减少应用 OBS 的成本。

   这样的 partial update 确实可以通过简单地使用对应于 $\mathbf{U}$$\mathbf U$ 的海森矩阵 ${\mathbf{H}}_{\mathbf{U}}$$\mathbf H_\mathbf U$ 而不是 ${\mathbf{H}}_{\mathbf{M}}$$\mathbf H_\mathbf M$ 来计算 OBS update ，并仅更新 ${\overrightarrow{\mathbf{w}}}_{\mathbf{U}}$$\mathbf {\vec w}_\mathbf U$ 来实现。重要的是，我们特定的 layer-wise 问题的损失函数对于 $\mathbf{U}$$\mathbf U$ 仍然是二次的，OBS update 仍然是最优的：对 $\mathbf{U}$$\mathbf U$ 的限制本身不会引入任何额外的 approximation error，只是误差补偿可能不那么有效，因为可供调整的权重更少。与此同时，如果 $|\mathbf{U}|<|\mathbf{M}|$$|\mathbf U|\lt |\mathbf M|$ ，则求解 ${\mathbf{H}}_{\mathbf{U}}$$\mathbf H_\mathbf U$ 的逆矩阵将比求解 ${\mathbf{H}}_{\mathbf{M}}$$\mathbf H_\mathbf M$ 的逆矩阵快得多。我们现在将利用这种机制在 $\mathbf{W}$$\mathbf W$ 的所有行之间同步 masked Hessians 。

4. Hessian Synchronization：接下来，假设输入特征的固定顺序 $j=1,\cdots ,d_{\text{col}}$$j=1,\cdots,d_\text{col}$ 。由于这些特征通常是随机排列的，为简单起见，我们将保留所给定的顺序，但原则上可以选择任何排列。接下来，对于每一行，我们递归地定义由 $d_{\text{col}}$$d_\text{col}$ 索引定义的一组子集：

   $$\begin{array}{}\text{(19)}& U_{j+1}=U_j-\{j\},U_1=\{1,\cdots ,d_{\text{col}}\}\end{array}$$

   换句话说，从包含所有索引的 $U_1$$U_1$ 开始，每个子集 $U_{j+1}$$U_{j+1}$ 都是通过从前一个子集 $U_j$$U_j$ 中删除最小索引来创建的。这些子集对应了一组 inverse Hessians $({\mathbf{H}}_{U_j}{)}^{-1}={\left({\left(\mathbf{X}{\mathbf{X}}^{\mathrm{\top }}\right)}_{U_j}\right)}^{-1}$$(\mathbf H_{U_j})^{-1} = \left(\left(\mathbf X\mathbf X^\top\right)_{U_j}\right)^{-1}$ ，我们将在 $\mathbf{W}$$\mathbf W$ 的所有行中共享这些矩阵。关键是，根据《Optimal Brain Compression: A framework for accurate posttraining quantization and pruning》，通过高斯消元法可以在 $O(d_{\text{col}}^2)$$O(d_\text{col}^2)$ 时间内从 $\mathbf{B}=({\mathbf{H}}_{U_j}{)}^{-1}$$\mathbf B = (\mathbf H_{U_j})^{-1}$ 中删除对应的第 $j$$j$ 行和第 $j$$j$ 列来有效计算 updated inverse $({\mathbf{H}}_{U_{j+1}}{)}^{-1}$$(\mathbf H_{U_{j+1}})^{-1}$：

   $$\begin{array}{}\text{(20)}& ({\mathbf{H}}_{U_{j+1}}{)}^{-1}={(\mathbf{B}-\frac{1}{[\mathbf{B}{]}_{1,1}}{\mathbf{B}}_{:1}{\mathbf{B}}_{1:})}_{2:2}\end{array}$$

   其中 $({\mathbf{H}}_{U_1}{)}^{-1}={\mathbf{H}}^{-1}$$(\mathbf H_{U_1})^{-1} = \mathbf H^{-1}$ 。因此，$d_{\text{col}}$$d_\text{col}$ 个 inverse Hessians 可以在 $O(d_{\text{col}}^3)$$O(d_\text{col}^3)$ 时间内递归计算，即除了 ${\mathbf{H}}^{-1}$$\mathbf H^{-1}$ 的初始求逆之外，额外的矩阵求逆具有相似的成本。

   一旦某个权重 $w_k$$w_k$ 被裁剪，就不应该再对其进行更新。此外，我们裁剪 $w_k$$w_k$ 时，我们希望尽可能更新更多 unpruned weights 以实现最大的误差补偿。这导致以下策略：对于所有的行 $i$$i$ ，按顺序遍历 $U_j$$U_j$ 及其对应的 inverse Hessians $({\mathbf{H}}_{U_j}{)}^{-1}$$(\mathbf H_{U_{j}})^{-1}$，并裁剪 $w_j$$w_j$ 如果 $j\ne M_i$$j\ne M_i$。重要的是，每个 inverse Hessians $({\mathbf{H}}_{U_j}{)}^{-1}$$(\mathbf H_{U_{j}})^{-1}$ 仅计算一次，并被 reused 从而在所有行中 remove weight j （当权重 $j$$j$ 是 pruning mask 的一部分时）。该算法的可视化描述见 Figure 4 。

   

5. 计算复杂度：总成本由三部分组成：

   • (a) ：计算初始海森矩阵，需要时间 $\mathrm{\Theta }(n\times d_{\text{col}}^2)$$\Theta(n\times d_\text{col}^2)$ ，其中 $n$$n$ 是所使用的输入样本的数量。我们发现选择 $n$$n$ 比 $d_{\text{col}}$$d_\text{col}$ 大一个小的倍数就足以获得良好稳定的结果，即使在非常大的模型上（见附录 A ）。

   • (b) ：遍历 inverse Hessian 集合需要时间 $O(d_{\text{col}}^2)$$O(d_\text{col}^2)$。

   • (c) ：reconstruction/pruning 本身。后者成本可以用对 $\mathbf{W}$$\mathbf W$ 的所有 $d_{\text{row}}$$d_\text{row}$行对所有 $d_{\text{col}}$$d_\text{col}$列依次应用公式 ${\delta }_m=-\frac{w_m}{{\left[{\mathbf{H}}^{-1}\right]}_{m,m}}{\left({\mathbf{H}}^{-1}\right)}_{:,m},{ϵ}_m=\frac{w_m^2}{{\left[{\mathbf{H}}^{-1}\right]}_{m,m}}$$\delta_m = -\frac{w_m}{\left[\mathbf H^{-1}\right]_{m,m}} \left(\mathbf H^{-1}\right)_{:,m}, \quad \epsilon_m = \frac{w_m^2}{\left[\mathbf H^{-1}\right]_{m,m}}$ 的时间上界来表示，即 $O(d_{\text{col}}{d}_{\text{row}}{d}_{\text{col}})$$O(d_\text{col}d_\text{row}d_\text{col})$ 。

   总共这些加起来为 $O(d_{\text{col}}^3+d_{\text{row}}{d}_{\text{col}}^2)$$O(d_\text{col}^3+d_\text{row}d_\text{col}^2)$ 。对于 Transformer 模型，这简单地是 $O(d_{\text{hidden}}^3)$$O(d_\text{hidden}^3)$ ，比 exact reconstruction 快了整整一个 $d_{\text{hidden}}$$d_\text{hidden}$ 因子。这意味着我们已经达到了初始目标，因为即使对极其大的模型，这个复杂度也足以使方案实用。

6. Weight Freezing Interpretation：虽然我们将 SparseGPT 算法表示为对 exact reconstruction 的逼近，使用 optimal partial updates ，但这个方案还有另一种有趣的视角。具体来说，考虑一个 exact greedy framework ，它按列压缩权重矩阵，在每一步总是最优地更新所有尚未压缩的权重。乍看之下，SparseGPT 似乎不适合这个框架，因为我们在每列中只压缩一些权重，也只更新一部分未压缩的权重。然而，从原理上讲，“压缩”一个权重最终意味着将其固定为某个特定值，并确保它不会通过某些未来的更新再次 “解压缩”，即固定它。因此，将 column-wise compression 定义为：

   $$\begin{array}{}\text{(21)}& \text{compress}{\left({\mathbf{w}}^j\right)}_i=0\text{ if }j\ne M_i\text{ and }{w}_i^j\text{ otherwise }\end{array}$$

   即，将不在掩码中的权重置零，并将其余权重固定为当前值，那么我们的算法可以解释为精确的 column-wise 贪心方案。这种视角将允许我们干净地将 sparsification 和 quantization 合并为单个压缩过程。