Large language models (LLMs) have shown impressive performance on language
tasks but face challenges when deployed on resource-constrained devices due to
their extensive parameters and reliance on dense multiplications, resulting in
high memory demands and latency bottlenecks. Shift-and-add reparameterization
offers a promising solution by replacing costly multiplications with
hardware-friendly primitives in both the attention and multi-layer perceptron
(MLP) layers of an LLM. However, current reparameterization techniques require
training from scratch or full parameter fine-tuning to restore accuracy, which
is resource-intensive for LLMs. To address this, we propose accelerating
pretrained LLMs through post-training shift-and-add reparameterization,
creating efficient multiplication-free models, dubbed ShiftAddLLM.
Specifically, we quantize each weight matrix into binary matrices paired with
group-wise scaling factors. The associated multiplications are reparameterized
into (1) shifts between activations and scaling factors and (2) queries and
adds according to the binary matrices. To reduce accuracy loss, we present a
multi-objective optimization method to minimize both weight and output
activation reparameterization errors. Additionally, based on varying
sensitivity across layers to reparameterization, we develop an automated bit
allocation strategy to further reduce memory usage and latency. Experiments on
five LLM families and eight tasks consistently validate the effectiveness of
ShiftAddLLM, achieving average perplexity improvements of 5.6 and 22.7 points
at comparable or lower latency compared to the most competitive quantized LLMs
at 3 and 2 bits, respectively, and more than 80% memory and energy reductions
over the original LLMs. Codes and models are available at
this https URL

本研究提出了一种通过后期训练的 ShiftAndAddLLM 来加速预训练的大型语言模型，通过将每个权重矩阵量化为与分组缩放因子配对的二进制矩阵，并将与二进制矩阵相关的乘法重新参数化为在激活和缩放因子之间进行的移位和加法操作，以减少内存使用和延迟，并且通过多目标优化方法来最小化权重和输出激活重新参数化误差，进一步降低了精度损失。

ShiftAddLLM：通过后期训练的无乘法重参数化加速预先训练的 LLMs

ShiftAddLLM: Accelerating Pretrained LLMs via Post-Training  Multiplication-Less Reparameterization

We propose a novel non-negative spherical relaxation for optimization
problems over binary matrices with injectivity constraints, which in particular
has applications in multi-matching and clustering. We relax respective binary
matrix constraints to the (high-dimensional) non-negative sphere. To optimize
our relaxed problem, we use a conditional power iteration method to iteratively
improve the objective function, while at same time sweeping over a continuous
scalar parameter that is (indirectly) related to the universe size (or number
of clusters). Opposed to existing procedures that require to fix the integer
universe size before optimization, our method automatically adjusts the
analogous continuous parameter. Furthermore, while our approach shares
similarities with spectral multi-matching and spectral clustering, our
formulation has the strong advantage that we do not rely on additional
post-processing procedures to obtain binary results. Our method shows
compelling results in various multi-matching and clustering settings, even when
compared to methods that use the ground truth universe size (or number of
clusters).

我们提出了一种新颖的非负球面松弛算法，用于具有单射性约束的二值矩阵优化问题，特别适用于多匹配和聚类。

非负球面松弛与宇宙自由多匹配和聚类

Non-Negative Spherical Relaxations for Universe-Free Multi-Matching and  Clustering

Sample compression schemes were defined by Littlestone and Warmuth (1986) as
an abstraction of the structure underlying many learning algorithms. Roughly
speaking, a sample compression scheme of size $k$ means that given an arbitrary
list of labeled examples, one can retain only $k$ of them in a way that allows
to recover the labels of all other examples in the list. They showed that
compression implies PAC learnability for binary-labeled classes, and asked
whether the other direction holds. We answer their question and show that every
concept class $C$ with VC dimension $d$ has a sample compression scheme of size
exponential in $d$. The proof uses an approximate minimax phenomenon for binary
matrices of low VC dimension, which may be of interest in the context of game
theory.

本文提出采样压缩序列作为一种学习算法的抽象形式，并回答了问题：每个概念类别 C 具有 VC 维度 d 的序列都具有指数大小的采样压缩序列，这得益于对 VC 维下二进制矩阵的逼近极小现象。

VC 类样本压缩方案

Sample compression schemes for VC classes

In standard clustering problems, data points are represented by vectors, and
by stacking them together, one forms a data matrix with row or column cluster
structure. In this paper, we consider a class of binary matrices, arising in
many applications, which exhibit both row and column cluster structure, and our
goal is to exactly recover the underlying row and column clusters by observing
only a small fraction of noisy entries. We first derive a lower bound on the
minimum number of observations needed for exact cluster recovery. Then, we
propose three algorithms with different running time and compare the number of
observations needed by them for successful cluster recovery. Our analytical
results show smooth time-data trade-offs: one can gradually reduce the
computational complexity when increasingly more observations are available.

通过观察少量的噪声数据，本文提出了三种算法用于精确恢复二进制矩阵中的行和列聚类结构，分析结果展示了时间和数据间平滑的折衷关系。