用±1向量线性组合实现高效1比特张量压缩，内存减半误差仍小。
Efficient $1$-bit tensor approximations
- 用±1向量的张量积组合逼近矩阵和高阶张量，大幅降低存储需求。
- 对Mistral-7B模型压缩50%后，226个权重矩阵相对误差均<6%，性能几乎不变。
- 代码仅20行，支持AVX2/AVX512加速，适用于大模型量化与图像压缩。
我们提出一种空间高效的矩阵与任意阶张量分解方法，将其表示为{-1, 1}取值向量的张量积的线性组合。对于任意实数矩阵 $A \in \mathbb{R}^{m \times n}$，其 $w$-宽度符号割分解为 $A - R_w = S_w C_w T_w^\top = \sum_{j=1}^w c_j \cdot \mathbf{s}_j \mathbf{t}_j^\top$，其中 $S_w, T_w$ 及向量 $\mathbf{s}_j, \mathbf{t}_j$ 均取值于 {-1, 1}，$C_w = \text{diag}(\mathbf{c}_w)$。存储 $(S_w, T_w, C_w)$ 仅需 $w \cdot (m + n)$ 位比特和 $w$ 个浮点数。当 $A$ 为独立同分布 $\mathcal{N}(0,1)$ 的 #f32 矩阵时，$\|R_w\|_F$ 随 $w$ 呈指数衰减。选择 $w$ 使存储开销等同于 #f16 或 #bf16 矩阵时，相对误差相当。算法仅20行伪代码，源自Frieze和Kannan（1999）工作的简单改进。首次应用中，将开源模型 Mistral-7B-v0.1 的权重矩阵压缩50%，所有226个余项矩阵相对误差<6%，扩展模型在Hugging Face排行榜表现接近原版。压缩率从50%降至25%时性能缓慢下降。我们使用SIMD指令在AVX2和AVX512架构上优化了开源Rust实现，并将算法扩展至任意阶张量，用于压缩第一作者猫的照片。
原文摘要 · Abstract (English)
We present a spatially efficient decomposition of matrices and arbitrary-order tensors as linear combinations of tensor products of $\{-1, 1\}$-valued vectors. For any matrix $A \in \mathbb{R}^{m \times n}$, $$A - R_w = S_w C_w T_w^\top = \sum_{j=1}^w c_j \cdot \mathbf{s}_j \mathbf{t}_j^\top$$ is a {\it $w$-width signed cut decomposition of $A$}. Here $C_w = "diag"(\mathbf{c}_w)$ for some $\mathbf{c}_w \in \mathbb{R}^w,$ and $S_w, T_w$, and the vectors $\mathbf{s}_j, \mathbf{t}_j$ are $\{-1, 1\}$-valued. To store $(S_w, T_w, C_w)$, we may pack $w \cdot (m + n)$ bits, and require only $w$ floating point numbers. As a function of $w$, $\|R_w\|_F$ exhibits exponential decay when applied to #f32 matrices with i.i.d. $\mathcal N (0, 1)$ entries. Choosing $w$ so that $(S_w, T_w, C_w)$ has the same memory footprint as a \textit{f16} or \textit{bf16} matrix, the relative error is comparable. Our algorithm yields efficient signed cut decompositions in $20$ lines of pseudocode. It reflects a simple modification from a celebrated 1999 paper [1] of Frieze and Kannan. As a first application, we approximate the weight matrices in the open \textit{Mistral-7B-v0.1} Large Language Model to a $50\%$ spatial compression. Remarkably, all $226$ remainder matrices have a relative error $<6\%$ and the expanded model closely matches \textit{Mistral-7B-v0.1} on the {\it huggingface} leaderboard [2]. Benchmark performance degrades slowly as we reduce the spatial compression from $50\%$ to $25\%$. We optimize our open source \textit{rust} implementation [3] with \textit{simd} instructions on \textit{avx2} and \textit{avx512} architectures. We also extend our algorithm from matrices to tensors of arbitrary order and use it to compress a picture of the first author's cat Angus.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。