Getting Free Bits Back from Rotational Symmetries in LLMs

## Abstract

Abstract Current methods for compressing neural network weights, such as decomposition, pruning, quantization, and channel simulation, often overlook the inherent symmetries within these networks and thus waste bits on encoding redundant information.
In this paper, we propose a format based on bits-back coding for storing rotationally symmetric Transformer weights more efficiently than the usual array layout at the same floating-point precision.
We evaluate our method on Large Language Models (LLMs) pruned by SliceGPT (Ashkboos et al., 2024 ) and achieve a 3-5% reduction in total bit usage for free across different model sizes and architectures without impacting model performance within a certain numerical precision.

## 1 Introduction

Modern neural networks, particularly Large Language Models (LLMs), typically contain billions of parameters.
Therefore, encoding and transmitting these models efficiently is gaining widespread interest.
Currently, compression techniques of model weights mainly fall into four categories, including decomposition (e.g., Hu et al., ; Saha et al., ), pruning (e.g., Hoefler et al., ; Frantar & Alistarh, ; Ashkboos et al., ), quantization (e.g., Wang et al., ; Xu et al., ), and channel simulation (e.g., Havasi et al., ; Isik et al., ; He et al., ).

However, these techniques ignore the fact that neural networks typically exhibit symmetries in their weight space.
For example, in feedforward networks, applying a random permutation to the neurons in one layer and its inverse to the weights in the subsequent layer leaves the output unchanged.
Encoding weights without accounting for these symmetries will lead to suboptimal codelength.

In this work, we address this redundancy by developing a practical storage format for model weights that takes symmetries into account to reduce the compressed model size.
We demonstrate the practicality of our method by compressing popular model architectures.
Specifically, our contributions are as follows:

- •
We propose a practical bits-back coding scheme for rotational symmetries.
We apply our approach to Large Language Models (LLMs) pruned by SliceGPT (Ashkboos et al., ) and demonstrate that our proposed approach can save additional free bits while preserving prediction accuracy within a certain numerical precision.
- •
We further showcase that by transmitting a small number of bits as a correction code, we can rescue the performance drops due to numerical inaccuracies.
- •
We perform experiments on the OPT (Zhang et al., ) and Llama-2 (Touvron et al., ) across different sizes, where we can save 3-5% additional bits *for free*.
Notably, our method is completely training-free and can be executed on a consumer-grade CPU.

## 2 Background

Figure: (a) A standard transformer block.
Refer to caption: /html/2410.01309/assets/x1.png

Before delving into our methods, we provide a brief introduction to bits-back coding (Frey & Hinton, ), Transformer (Vaswani et al., ), and SliceGPT (Ashkboos et al., ).

Bits-back Coding.
The motivating idea behind bits-back coding (Hinton & Van Camp, ; Townsend et al., ) can be summarised as follows: “*If we can make multiple equivalent choices to encode something, we should make our choice at random.*”
Note that transmitting this random choice requires some bits, and the bits-back coding algorithm provides a concrete procedure to recover the bits we used to randomize our choice.
The procedure is based on the following insight from compression: assuming we have the right coding distribution $P$, the encoding function of a compressor will output a sequence of uniformly random bits.
Therefore, if we run this process in reverse and run the decoder on a sequence of uniformly random bits, it will output a sample following $P$!
Therefore, lossless de-compression can be viewed as a computational way of performing inverse transform sampling, which provides an invertible way to make the aforementioned random choice.

To make the bits-back mechanism more precise, assume we have some data $x$ that belongs to some equivalence class $[x]$.
In many cases, encoding only the equivalence class $[x]$ instead of a specific instance $x$ would be enough for the task at hand.
Given a new item $x$ and a stream of already compressed bits $\mathcal{M}$, bits-back coding uses the decoder of lossless compressor on $\mathcal{M}$ to decode a random element of the equivalence class $x^{\prime}\sim P_{x\mid[x]}$ and leaves a shorter message $\mathcal{M}^{\prime}$.
After this, bits-back coding uses the encoder of the compressor to encode $x^{\prime}$ using $P_{x}$ as the coding distribution and append it to $\mathcal{M}^{\prime}$.
This procedure is reversible and hence decodable, so long as the receiver of the message can recover $x$ upon seeing $x^{\prime}$.
This ensures that $x^{\prime}$ can be coded back into the stream to recover the original message $\mathcal{M}$.
As one of our contributions, in [section 3.2](#S3.SS2), we explain how such a recovery step can be carried out when $x$ is a weight matrix and $[x]$ is an equivalence class under a certain rotational symmetry.

A concern with bits-back coding is its initialization: we need an initial stream of bits $\mathcal{M}_{0}$ to encode the first item.
While $\mathcal{M}_{0}$ represents a significant overhead if we only encode a few items, it only causes a constant overhead and quickly becomes negligible as the number of encoded items grows.

Transformer Architecture and SliceGPT.
Transformer (Vaswani et al., ) is the cornerstone of most Large Language Models.
Its basic component is the transformer block, as shown in [Figure 1(a)](#S2.F1.sf1).
Each block consists of a multi-head attention layer, a LayerNorm (Ba et al., ), and a feedforward network (FFN).
Two residual connections are added around the attention layer and FFN.

SliceGPT (Ashkboos et al., ) is a recently proposed method for pruning weights in Transformer models.
The approach leverages the insight that the outcome of LayerNorm (more precisely, RMSNorm, i.e., ${\mathbf{x}}\leftarrow{\mathbf{x}}/||{\mathbf{x}}||$) is invariant if we apply a rotation to the input and its inverse to the output.
This rotation matrix and its inverse can be absorbed into the weights before and after the normalization layer.
Therefore, by performing PCA on the hidden states, we can choose rotation matrices that align with the principal components. This allows us to prune the rows and columns corresponding to the less significant eigenvalues in the hidden states, effectively reducing the model’s complexity without drastically hurting the performance.
We visualize each transformer block after rotation and pruning in [Figure 1(b)](#S2.F1.sf2).
The shadow indices the pruned columns and rows.

## 3 Getting bits back from Rotation Symmetries

Figure: Algorithm 1 Rotate Transformer to its Canonical Direction.

In this section, we describe our method, which is based on the observation of rotational symmetries in the Transformer block pruned by SliceGPT.
Comparing [Figure 1(b)](#S2.F1.sf2) and [Figure 1(a)](#S2.F1.sf1), we can see SliceGPT not only reduces the number of parameters (by pruning out columns and rows), but also introduces rotational symmetries.
We should note that these rotational symmetries do not exist in the standard transformer due to the skip connections.
Concretely, in a SliceGPT-pruned Transformer, denoting the weights in the $\ell$-th transformer block with superscripts, we have:

###### Remark 3.1 .

Outputs remain unchanged if rotating ${\mathbf{W}}_{2}^{(\ell-1)}$, ${\mathbf{b}}_{2}^{(\ell-1)}$ (if any) and ${\mathbf{Q}}_{\text{skip_mlp}}^{(\ell-1)}$ by an arbitrary orthogonal matrix ${\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}$ (^1^11Throughout this paper, we will use orange-colored ${\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}$ to denote orthogonal matrices.), and rotating ${\mathbf{Q}}_{\text{skip_att}}^{(\ell)},{\mathbf{W}}_{qkv}^{(\ell)}=\left[{\mathbf{W}}_{k}^{(\ell)},{\mathbf{W}}_{q}^{(\ell)},{\mathbf{W}}_{v}^{(\ell)}\right]$ by ${\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}^{\top}$ as follows:

$$ $\displaystyle{\mathbf{W}}_{2}^{(\ell-1)}\leftarrow{\mathbf{W}}_{2}^{(\ell-1)}{\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}},\quad{\mathbf{b}}^{(\ell-1)}\leftarrow{\mathbf{b}}^{(\ell-1)}{\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}},\quad{\mathbf{Q}}_{\text{skip_mlp}}^{(\ell-1)}\leftarrow{\mathbf{Q}}_{\text{skip_mlp}}^{(\ell-1)}{\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}$ (1) $\displaystyle{\mathbf{Q}}_{\text{skip_att}}^{(\ell)}\leftarrow{\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}^{\top}{\mathbf{Q}}_{\text{skip_att}}^{(\ell)},\ {\mathbf{W}}_{qkv}^{(\ell)}\leftarrow{\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}^{\top}{\mathbf{W}}_{qkv}^{(\ell)}$ (2) $$

Similarly, outputs remain unchanged if rotating ${\mathbf{W}}_{o}^{(\ell)}$, ${\mathbf{b}}_{o}^{(\ell)}$ (if any) and ${\mathbf{Q}}^{(\ell)}_{\text{skip_att}}$ by ${\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}$, and rotating ${\mathbf{Q}}_{\text{skip_mlp}}^{(\ell)}$ and ${\mathbf{W}}_{1}^{(\ell)}$ by ${\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}^{\top}$ as follows:

$$ $\displaystyle{\mathbf{W}}_{o}^{(\ell)}\leftarrow{\mathbf{W}}_{o}^{(\ell)}{\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}},\quad{\mathbf{b}}_{o}^{(\ell)}\leftarrow{\mathbf{b}}_{o}^{(\ell)}{\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}},\quad{\mathbf{Q}}^{(\ell)}_{\text{skip_att}}\leftarrow{\mathbf{Q}}^{(\ell)}_{\text{skip_att}}{\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}$ (3) $\displaystyle{\mathbf{Q}}_{\text{skip_mlp}}^{(\ell)}\leftarrow{\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}^{\top}{\mathbf{Q}}_{\text{skip_mlp}}^{(\ell)},\quad{\mathbf{W}}_{1}^{(\ell)}\leftarrow{\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}^{\top}{\mathbf{W}}_{1}^{(\ell)}$ (4) $$

This symmetry suggests that directly encoding the weights (e.g., in float16) would use more bits than necessary.
In the following, we offer an informal explanation to clarify this redundancy:

For simplicity, let’s denote the weights in a transformer as $\bm{\Theta}$.
Assuming the coding distribution is $P$(^2^22If we encode the weights using float16, we are essentially assuming that all possible floating-point values ($2^{16}$ in total) have the same probability mass.), we need to spend about
$-\log_{2}P(\bm{\Theta})$ bits to encode the weights directly.
On the other hand, as discussed above, applying rotations (and its inversion) to some weights leaves the output invariant.
Therefore, if we define *equivalence* in terms of outputs (and we do!), the weights with different rotations form an *equivalence class*, denoted by $[\bm{\Theta}]$.
Encoding this equivalence class will require $-\log_{2}\left(\sum_{\bm{\Theta}\in[\bm{\Theta}]}P(\bm{\Theta})\right)$ bits.
In a finite-precision system, where the number of possible rotation matrices is limited, the equivalence class is finite. Assuming that each entry in the equivalence class has the same probability, and denoting the cardinality of the equivalence class by $\mathcal{C}$, we have $-\log_{2}\left(\sum_{\bm{\Theta}\in[\bm{\Theta}]}P(\bm{\Theta})\right)=-\log_{2}\left(\mathcal{C}P(\bm{\Theta})\right)=-\log_{2}P(\bm{\Theta})-\log_{2}\mathcal{C}$.
This implies that directly encoding the weights wastes $-\log_{2}\mathcal{C}$ bits more than necessary.

We apply bits-back coding to eliminate this redundancy.
In short, each time we encode the weights in one transformer block (more precisely, ${\mathbf{W}}^{(\ell)}_{2}$ and ${\mathbf{W}}^{(\ell)}_{o}$), we start by decoding a random rotation from the current bitstream and applying it to the weights.
We then encode the rotated weights into the bitstream.
When decoding, we first decode the rotated weights and recover the rotation we applied to the original weights.
Then, we encode the rotation matrix back to the bitstream.
This process is repeated for every transformer block.
One concern the reader might have regarding our proposed method is that bits-back coding is known to have poor one-shot compression performance and is only effective when encoding large datasets.
This poor performance is mainly due to the fact that we need some initial bits to perform bits-back, causing overhead that will only be eliminated asymptotically.
However, this is not an issue in our approach due to two reasons:
(1) in the Transformer, besides the transformer blocks, we also need to store a relatively large head and embedding layer.
We can simply use this as the initial bits for bits-back;
and (2) note that we apply our coding technique to *each* transformer block in the Transformer.
We can view this single Transformer as a dataset consisting of transformer blocks as the elements.
For large enough architectures (such as the ones we used in our experiments), the bits-back coding is already efficient.

However, there are two questions that remain unsolved:
(a) *How can we recover the rotation given a rotated weight matrix?*
(b) *How can we decode/encode a rotation (Orthogonal) matrix from/to the current bitstream?*
We will answer these questions in [Section 3.1](#S3.SS1) and [Section 3.2](#S3.SS2), respectively.
We then put things all together in [Section 3.3](#S3.SS3) and describe the full encoding and decoding algorithms in [Algorithms 5](#alg5) and [6](#alg6).
Finally, as we only apply rotations to weight matrices with finite precision (e.g., float16), we may suffer from numerical inaccuracy, impacting the transformer’s outputs.
To handle this, we propose to send a simple correction code, which we discuss at the end of [Section 3.3](#S3.SS3).

###### Remark 3.1 .

### 3.1 Rotating Transformer Weights to Their Canonical Direction

We now discuss how to recover the rotation from a rotated weight matrix.
This is, in general, not feasible without additional information about the original weights.
Fortunately, as noted in [Remark 3.1](#S3.Thmtheorem1), we can apply any rotation to the weights.
This allows us to first rotate the weights to a *canonical direction* as a reference.
We can define this canonical direction in multiple ways as long as we can recover it easily after applying a random rotation.
In this work, we adopt eigenvalue decomposition to define the canonical direction, while future works could explore more sophisticated methods.

We detail the algorithm for the canonical direction in [Algorithm 1](#alg1).
In short, for each transformer block, we can apply two free rotations according to [Remark 3.1](#S3.Thmtheorem1): the first rotation is applied to ${\mathbf{W}}_{2}^{(\ell-1)}$, ${\mathbf{b}}_{2}^{(\ell-1)}$, ${\mathbf{Q}}_{\text{skip_mlp}}^{(\ell-1)}$, ${\mathbf{Q}}_{\text{skip_att}}^{(\ell)}$, and ${\mathbf{W}}_{qkv}^{(\ell)}$.
We hence define the canonical direction such that ${{\mathbf{W}}_{2}^{(\ell-1)}}^{\top}{\mathbf{W}}_{2}^{(\ell-1)}$ is diagnoal;
the second rotation is applied to ${\mathbf{W}}_{o}^{(\ell)}$, ${\mathbf{b}}_{o}^{(\ell)}$, ${\mathbf{Q}}^{(\ell)}_{\text{skip_att}}$, ${\mathbf{Q}}_{\text{skip_mlp}}^{(\ell)}$ and ${\mathbf{W}}_{1}^{(\ell)}$.
We hence define the canonical direction such that ${{\mathbf{W}}_{o}^{(\ell)}}^{\top}{\mathbf{W}}_{o}^{(\ell)}$ is diagnoal.

After rotating the transformer to its canonical direction, we can recover any rotation that is applied to the canonical ${{\mathbf{W}}_{2}^{(\ell-1)}}$ or ${{\mathbf{W}}_{o}^{(\ell)}}$ by eigenvalue decomposition.
Specifically, let’s consider a random rotation ${\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}$ applied to ${{\mathbf{W}}_{2}^{(\ell-1)}}$ in its canonical direction as an example.
Denoting the matrix after rotation is $\tilde{{\mathbf{W}}}_{2}^{(\ell-1)}\leftarrow{{\mathbf{W}}_{2}^{(\ell-1)}}{\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}$,
we can perform eigenvalue decomposition on ${\tilde{{\mathbf{W}}}_{2}^{(\ell-1)}}\ ^{\top}\tilde{{\mathbf{W}}}_{2}^{(\ell-1)}$, and the rotation matrix ${\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}$ can then be recovered by stacking the eigenvectors together in columns.
The weight matrix in the canonical direction can be obtained by ${{\mathbf{W}}_{2}^{(\ell-1)}}\leftarrow\tilde{{\mathbf{W}}}_{2}^{(\ell-1)}{\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}^{\top}={{\mathbf{W}}_{2}^{(\ell-1)}}{\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}{\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}^{\top}$.

A caveat exists in the above procedure: eigenvalue decomposition can result in eigenvectors with opposite signs.
This will lead to undesired results when recovering the canonical weight matrix.
We include a detailed explanation in [Appendix A](#A1).
To address this, we encode the sign of the summation of each row of the rotation matrix as side information. This only requires
$D$ bits for a $D$-dimensional rotation matrix.
After recovering eigenvectors through eigenvalue decomposition, we can use this side information to correct the sign for each eigenvector (i.e., rows in the rotation matrix).
[Algorithm 2](#alg2) describes this process.

Another concern arises when ${{{\mathbf{W}}}_{2}^{(\ell-1)}}^{\top}{{\mathbf{W}}}_{2}^{(\ell-1)}$ (or
${{{\mathbf{W}}}_{o}^{(\ell)}}\ ^{\top}{{\mathbf{W}}}_{o}^{(\ell)}$) is not full-rank.
In such cases, eigenvalue decomposition will not recover the rotation applied to these canonical weights.
To address this, we can define the canonical direction by applying eigenvalue decomposition to ${\mathbf{B}}^{\top}{\mathbf{B}}$, where
${\mathbf{B}}^{\top}=\left[{{\mathbf{W}}_{2}^{(\ell-1)}}^{\top},{{\mathbf{b}}_{2}^{(\ell-1)}}^{\top},{\mathbf{W}}_{k}^{(\ell)},{\mathbf{W}}_{q}^{(\ell)},{\mathbf{W}}_{v}^{(\ell)}\right]$ (or ${\mathbf{B}}^{\top}=\left[{{\mathbf{W}}_{o}^{(\ell)}}^{\top},{{\mathbf{b}}_{o}^{(\ell)}}^{\top},{\mathbf{W}}_{1}^{(\ell)}\right]$).
However, we actually found ${{{\mathbf{W}}}_{2}^{(\ell-1)}}^{\top}{{\mathbf{W}}}_{2}^{(\ell-1)}$ and
${{{\mathbf{W}}}_{o}^{(\ell)}}\ ^{\top}{{\mathbf{W}}}_{o}^{(\ell)}$ were already full-rank across all architectures in our experiments.
This may be because SliceGPT has already pruned insignificant principal components in the hidden states, leading to more compact weight matrices.

### 3.2 Decoding and Encoding Rotation Matrices

Now, we discuss *how to decode/encode a rotation matrix from/to a given bitstream.*
A naive approach is to directly decode and encode these $D^{2}$ entries in a rotation matrix ${\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}\in\mathbb{R}^{D\times D}$, e.g., by float16.
However, it is difficult to guarantee that $D^{2}$ elements decoded from a given bitstream can form a rotation matrix.
In fact, a $D$-dimensional rotation matrix ${\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}$ has only $D(D-1)/2$ degrees of freedom (DOF), which means that we only need to decode and encode $D(D-1)/2$ floats for the entire matrix.
Therefore, the question becomes:
*(a) how can we construct a random rotation matrix from $D(D-1)/2$ random floats; (b) how can we recover these floats given a rotation matrix?*

Ideally, we aim to generate a uniformly distributed random rotation matrix, i.e., a random rotation matrix from the Haar distribution.
Following the method by Stewart (), we can construct the matrix by iteratively applying Householder transformations (Householder, ).

However, this algorithm is difficult to reverse:
we need to reverse the householder transformations one by one, and hence, we will suffer from large numerical instability.
Therefore, we propose a simple method to generate a rotation matrix.
This approach does not result in a uniformly distributed rotation matrix.
However, we found our approach works well in practice.
Since our goal is not to design a theoretically optimal algorithm but rather a more practical approach to perform bits-back, we leave a better design for the rotation matrix to future works.

We describe the process of decoding and encoding a rotation matrix in [Algorithms 3](#alg3) and [4](#alg4).
Again, we employ a bits-back approach for efficiency.
In brief, to decode a rotation matrix, we first decode a symmetric matrix from the bitstream by decoding its diagonal and upper triangular parts and performing an eigenvalue decomposition.
The eigenvalues are then encoded back into the bitstream.
To encode this rotation matrix, we first decode its eigenvalues from the bitstream, reconstruct the symmetric matrix via matrix multiplication, and then encode its diagonal and upper triangular parts back into the bitstream.
Notably, our approach requires only the number of bits corresponding to $D(D-1)/2$ floats, which aligns with the degrees of freedom of a random rotation matrix.

### 3.3 Putting Things Together and Handling Numerical Inaccuracy

Figure: Algorithm 5 Bits-back Encoding for transformers (processed by SliceGPT). We use red to represent adding bits to the bitstream; green to represent removing bits from the bitstream.

Having discussed the canonical direction for the transformer and the algorithm for decoding and encoding a rotation matrix, we detail the complete algorithm for encoding and decoding the entire transformer using bits-back in [Algorithms 5](#alg5) and [6](#alg6), respectively.
In these algorithms, we use Encode_to and Decode_from to represent the process of appending or popping arrays of float16 values into or from the current bitstream.

However, since we only save rotated weights in finite precision (e.g., float16), we may suffer from numerical inaccuracy, and hence the rotation matrix recovered by [Algorithm 2](#alg2) in decoding will have deviations from the original rotation matrix applied to the canonical weights in encoding.
This will lead to two undesirable outcomes:
(1) the bitstream after re-encoding the rotation matrices (as shown in lines 7 and 13 in [Algorithm 6](#alg6)) will contain errors, which will affect the weights decoded subsequently from this bitstream;
(2) the weight matrices rotated back to the canonical direction (as shown in lines 6 and 12 in [Algorithm 6](#alg6)) will contain errors.

The first error can be fatal in standard bits-back coding algorithms, as they are usually implemented using a variable-length code, such as asymmetric numeral systems (Duda, ; Townsend et al., ).
Such a system is very sensitive to decoding errors: since by design the code assigns different codelengths to symbols, if the decoder can only approximately recover the compressed data due to numerical errors, not only are they not getting the correct bits back, they might not even get the correct number of bits back.
If the decoder makes such an error even once, it misaligns the rest of the bitstream (i.e., it will be longer or shorter than it should be) and this will cause catastrophic decoding errors.

On the other hand, our proposed method is robust to such errors because we implement bits-back coding with a fixed-length code: we set a floating-point precision (e.g., 16 bits) ahead of time.
Then, each encoding and decoding operation will change the message length by the same amount: for a fixed precision, we can compute the total codelength of the model ahead of time.
Importantly, this means that any decoding error remains local: if we do not recover a given weight $w$ exactly, this will only affect the value of $w$ but will not affect the rest of the bitstream.

However, although our bits-back process will not propagate local decoding errors, individual errors itself can still impact the model performance.
Therefore, we propose transmitting an additional correction code to correct errors exceeding a certain threshold.
Specifically, errors in (a) occur in the $D(D+1)/2$ floats obtained by [Algorithm 3](#alg3) when encoding the rotation matrix to the bitstream, and errors in (b) occur when rotating the weight matrices back to the canonical direction.
Note that the encoder can simulate both procedures during encoding to determine the exact value that the decoder will obtain.
If the error between the value obtained by the decoder and the one held by the encoder exceeds a certain threshold, the encoder can send a correction code containing the positions and the true values in float16.
Correcting each value will require approximately $16+\lceil\log_{2}L\rceil$ bits, where $L$ is the total number of values the decoder will reconstruct that can have errors.
For example, $L=D(D+1)/2$ for the error caused by (a), and $L$ represents the total number of parameters in the weight matrix for the error caused by (b).

A natural concern is that the correction code could become large if there are too many errors. Fortunately, as we show in [Figure 3](#S4.F3), only a tiny portion of values have relatively large errors.
Therefore, the correction code requires only a small number of bits to transmit and does not significantly impact the overall coding efficiency.
It is worth noting that this correcting strategy can be considered a simple error-correction code.
Therefore, we may be able to adopt more complex error-correction codes, but we leave this design for future exploration.

### 3.4 Analysis of the Codelength

Here, we analyze the codelength reduction achieved by our proposed approach from a practical standpoint.
A more rigorous theoretical analysis is provided in [Appendix B](#A2).
For simplicity’s sake, we assume there is no bias vector in our transformer architecture.
This is a reasonable assumption, as some modern architectures like Llama (Touvron et al., ) omit the bias too.
Additionally, we assume the transformer has no output head or embedding layer.
This assumption can be interpreted as modeling an extremely deep transformer, where the effects of the head and embedding layers become negligible.
However, it is important to note that this is not a realistic assumption in practical scenarios.
This is the main reason for the discrepancy between our analysis in this section and the results we present in [Section 4](#S4).

In one transformer block, as shown in [Figure 1(b)](#S2.F1.sf2), there exist eight matrices after SliceGPT, including six sliced weight matrices and two skip connection matrices.
If the slicing rate is $s$ and the weights are stored at $\delta$ bits precision (for example, $\delta=16$ in float16), the total codelength (in bits) can be expressed as:

$$ $\displaystyle(\underbrace{6\cdot rD^{2}}_{\text{6 weight matrices}}+\underbrace{2\cdot(rD)^{2}}_{\text{2 skip connection}})\cdot\delta$ (5) $$

where we denote $r=1-s$ as the remaining rate after slicing.
Using bits-back, we decode two rotation matrices from the bitstream during encoding, leading to a reduction in codelength by:

$$ $\displaystyle\left({2\cdot\frac{(rD)(rD-1)}{2}}\right)\cdot\delta=(rD)\cdot(rD-1)\cdot\delta$ (6) $$

We disregard the overhead from storing the signs of the eigenvectors (line 9 in [Algorithm 5](#alg5)) and the correction codes (discussed in [Section 3.3](#S3.SS3)), as these contributions are negligible.

Thus, the overall reduction in codelength is:

$$ $\displaystyle(rD)\cdot(rD-1)/(6\cdot rD^{2}+2\cdot(rD)^{2})\approx r/(6+2r)$ (7) $$

For a slice rate of $s=20-30\%$, this results in approximately a $10\%$ reduction in codelength.

## 4 Experiments and Results

We evaluate our proposed approach in this section.
We first test our method on the Open Pre-trained Transformer Language Models (OPT, Zhang et al., ) and Llama-2 (Touvron et al., ) pruned by SliceGPT (Ashkboos et al., ) with different slicing rates.
Then, we investigate the effectiveness of the correction codes proposed in [Section 3.3](#S3.SS3).
We conduct our bits-back algorithms on AMD Ryzen 9 7950X CPU and evaluate the performance on one NVIDIA RTX 4090 GPU.

Compression rate and performances.
We evaluate our method on OPT-1.3B/2.7B/6.7B/13B and Llama-2-7B, pruned by SliceGPT with different slicing rates.
We report perplexity (PPL) and accuracy on three downstream tasks (PIQA, Bisk et al. (); WinoGrande, Sakaguchi et al. (); and HellaSwag, Zellers et al. ()) to assess our method’s impact on performance.
Our approach saves an additional 3-5% in bits with negligible impact on performance.
Notably, the performance changes are inconsistent, with occasional improvements after bits-back, suggesting that the changes in the performance are more likely due to randomness than a clear degradation.
We also note that this codelength reduction is smaller than the theoretical estimates provided in [Section 3.4](#S3.SS4).
The primary reason for this discrepancy is that our analysis does not account for the substantial size of the head and embedding layers.

**Table 1: Compression rates and prediction performances before and after our proposed method. Our method reduces further 3-5% bits and has very minor influence on the performance.**
|  |  |  |  | Performance (before/after bits-back) |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Model | SliceGPT<br>Slicing | Compress Rate<br>after SliceGPT | Compress Rate<br>after bits-back | PPL ($\downarrow$) | PIQA (%, $\uparrow$) | WinoGrande (%, $\uparrow$) | HellaSwag (%, $\uparrow$) |
|  | 20% | -9.53% | -13.77% | 16.59/16.60 | 64.91/64.80 | 54.78/54.38 | 45.26/45.32 |
|  | 25% | -14.84% | -18.61% | 17.78/17.86 | 63.55/63.33 | 52.80/53.28 | 43.20/43.11 |
| OPT-1.3B | 30% | -20.53% | -23.81% | 19.60/19.66 | 60.88/60.50 | 52.88/53.28 | 40.25/40.06 |
|  | 20% | -9.19% | -13.84% | 13.89/13.95 | 68.44/68.12 | 58.88/58.72 | 51.35/51.17 |
|  | 25% | -15.07% | -19.09% | 14.85/14.87 | 66.70/66.76 | 57.30/57.70 | 48.41/48.38 |
| OPT-2.7B | 30% | -20.88% | -24.43% | 16.31/16.33 | 64.64/64.69 | 55.80/56.04 | 44.52/44.57 |
|  | 20% | -9.29% | -14.07% | 11.63/11.71 | 72.91/73.01 | 61.33/61.17 | 60.53/60.55 |
|  | 25% | -15.16% | -19.29% | 12.12/12.15 | 71.00/71.22 | 60.30/60.77 | 57.76/57.55 |
| OPT-6.7B | 30% | -21.18% | -24.84% | 12.81/12.91 | 69.31/69.42 | 59.75/59.59 | 53.64/52.94 |
|  | 20% | -9.18% | -14.01% | 10.75/10.77 | 74.27/74.27 | 64.96/64.88 | 65.74/65.79 |
|  | 25% | -15.27% | -19.51% | 11.08/11.07 | 74.27/73.72 | 63.46/63.93 | 63.48/63.09 |
| OPT-13B | 30% | -21.29% | -24.97% | 11.55/11.59 | 72.69/73.01 | 61.96/62.43 | 60.12/60.05 |
|  | 20% | -9.38% | -14.13% | 6.86/6.98 | 69.53/69.42 | 64.17/64.72 | 58.96/58.89 |
|  | 25% | -15.34% | -19.53% | 7.56/7.59 | 67.03/67.57 | 62.98/63.38 | 54.29/53.93 |
| Llama-2-7B | 30% | -21.45% | -25.09% | 8.63/8.69 | 64.69/64.09 | 62.75/62.12 | 49.13/49.07 |

Figure: Figure 2: Histogram and empirical CDF of the error between the reconstructed weights and the original weights before encoding, using ${\mathbf{W}}_{o}$ in the final layer of OPT-6.7B as an example. The pattern in this plot generalizes well to other weights and models. As shown, only a small fraction of the weights exhibit relatively large deviations. Therefore, we can allocate a negligible number of bits to transmit the positions and true values of these weights, effectively correcting the error caused by numerical inaccuracies.
Refer to caption: /html/2410.01309/assets/x3.png

Numerical inaccuracy and the effectiveness of the correction codes. We now examine the impact of numerical inaccuracies and the effectiveness of correction codes proposed in [Section 3.3](#S3.SS3).
To provide an intuitive understanding of the numerical issue, we use the weights matrix ${\mathbf{W}}_{o}$ from the last layer of OPT-6.7B as an example and visualize the error between the reconstructed weights and the original weights in [Figure 3](#S4.F3).
As we can see, only a tiny fraction of the weights exhibit relatively large errors.
Therefore, we can transmit the positions and true values of weights whose deviations exceed a certain threshold, using negligible bits to correct the numerical error.

The threshold is a hyperparameter that balances the codelength and accuracy.
In [Figure 3](#S4.F3), we examine the impact of threshold selection using the OPT-2.7B model.
Setting a relatively small threshold (0.005-0.01) effectively mitigates nearly all performance drops due to numerical inaccuracies, while still providing a significant reduction compared to the compression rate without bits-back coding.
In our experiments, we use a threshold of 0.01 for OPT models and 0.005 for Llama models.

## 5 Conclusion and Limitations

In this work, we introduce bits-back coding to encode Large Language Models pruned with SliceGPT.
Our approach can save 3-5% additional bits almost *for free* across several different architectures and sizes.
While bits-back coding has long been applied in data compression, its application to neural networks, where redundancy and symmetry are prevalent, has been underexplored.
Our work attempts to bridge this gap, opening a new direction for model compression.
A key takeaway is that by re-parameterizing and pre-processing network weights to explicitly capture symmetries, as demonstrated in SliceGPT, we can leverage bits-back coding to eliminate redundant bits.

Future research can focus on designing improved algorithms for encoding and decoding the random rotation matrix, developing better error-correction codes to manage large deviations caused by numerical instability, and integrating our method with other model compression techniques, such as the extremely quantized networks proposed by Ma et al. ().
Our method’s major concern is the numerical instability.
While we discuss reducing large deviations by sending a small number of bits as a correction code, the challenge of making this approach efficient for extremely quantized networks remains open.

## Acknowledgments

JH was supported by the University of Cambridge Harding Distinguished Postgraduate Scholars Programme.
JH and JMHL acknowledge support from a Turing AI Fellowship under grant EP/V023756/1.
GF acknowledges funding from DeepMind.

## Appendix A Why we need to encode the sign of each eigenvector?

First, assume we apply a random rotation matrix ${\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}$ to some canonical weight matrix ${\mathbf{W}}$, and obtain $\tilde{{\mathbf{W}}}\leftarrow{\mathbf{W}}{\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}$.
We can write this rotation matrix as a stack of orthonormal vectors:

$$ $\displaystyle{\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}=\begin{bmatrix}\text{---}&{\mathbf{q}}_{1}^{\top}&\text{---}\\ &\cdots&\\ \text{---}&{\mathbf{q}}_{D}^{\top}&\text{---}\end{bmatrix}$ (8) $$

When we recover the canonical weight matrix, we apply eigenvalue decomposition to $\tilde{{\mathbf{W}}}^{\top}\tilde{{\mathbf{W}}}$.
This is possible as ${{\mathbf{W}}^{\top}{\mathbf{W}}}$ is defined to be diagonal.
Therefore, ${\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}$ is one solution of eigenvalue decomposition:

$$ $\displaystyle\tilde{{\mathbf{W}}}^{\top}\tilde{{\mathbf{W}}}={\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}^{\top}{{\mathbf{W}}^{\top}{\mathbf{W}}}{\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}={\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}^{\top}\bm{\Lambda}{\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}$ (9) $$

However, the solution is not unique.
We can write

$$ $\displaystyle{\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}^{\top}\bm{\Lambda}{\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}=\begin{bmatrix}|&\cdot&|\\ {\mathbf{q}}_{1}&\cdot&{\mathbf{q}}_{D}\\ |&\cdot&|\end{bmatrix}\bm{\Lambda}\begin{bmatrix}\text{---}&{\mathbf{q}}_{1}^{\top}&\text{---}\\ \cdot&\cdot&\cdot\\ \text{---}&{\mathbf{q}}_{D}^{\top}&\text{---}\end{bmatrix}=\sum_{d}\lambda_{d}{\mathbf{q}}_{d}{\mathbf{q}}_{d}^{\top}$ (10) $$

Changing the sign of any ${\mathbf{q}}_{d}$ will not influence the results of its outer product.
Therefore, we can change the sign of each ${\mathbf{q}}_{d}$, and this will still be a valid solution to the eigenvalue decomposition.
As an example, WLG, assume by eigenvalue decomposition, we obtain

$$ $\displaystyle{\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}^{\prime}=\begin{bmatrix}\text{---}&-{\mathbf{q}}_{1}^{\top}&\text{---}\\ \text{---}&{\mathbf{q}}_{2}^{\top}&\text{---}\\ &\cdots&\\ \text{---}&{\mathbf{q}}_{D}^{\top}&\text{---}\end{bmatrix}$ (11) $$

We recover canonical weight matrix by

$$ $\displaystyle\tilde{{\mathbf{W}}}{\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}^{\prime\top}={\mathbf{W}}{\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}{\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}^{\prime\top}={\mathbf{W}}\begin{bmatrix}\text{---}&{\mathbf{q}}_{1}^{\top}&\text{---}\\ &\cdots&\\ \text{---}&{\mathbf{q}}_{D}^{\top}&\text{---}\end{bmatrix}\begin{bmatrix}|&\cdot&|\\ -{\mathbf{q}}_{1}&\cdot&{\mathbf{q}}_{D}\\ |&\cdot&|\end{bmatrix}={\mathbf{W}}\begin{bmatrix}-1&&&\\ &1&&\\ &&\ddots&\\ &&&1\end{bmatrix}\neq{\mathbf{W}}$ (12) $$

Therefore, if we do not control the sign of each eigenvector.
We cannot recover the original canonical weight matrix.

## Appendix B Bits-back justification

In this section, we justify our scheme by showing that it can be viewed as a particular instantiation of a bits-back scheme (Townsend et al., ; Kunze et al., ) with a particular discretization of the probability densities involved.
We will first explain why bits-back coding is applicable to networks with rotational invariants in a formal manner.
Following that, we will calculate the bits saved through bits-back coding in a more rigorous way.
For the sake of generality, we will perform singular value decomposition (SVD) on the weight matrix in this section, which, is equivalent to the eigenvalue decomposition we described in the main text.

Let ${\mathbf{W}}$ be a $\mathbb{R}^{n\times m}$ real-valued matrix, without loss of generality assume that $n\leq m$.
Then, we can always write ${\mathbf{W}}$ via its singular value decomposition (SVD):

$$ $\displaystyle{\mathbf{W}}={\mathbf{U}}\bm{\Sigma}{\mathbf{V}}^{\top},$ (13) $$

where ${\mathbf{U}}$ is a $\mathbb{R}^{n\times n}$ orthogonal matrix, $\bm{\Sigma}$ is a $\mathbb{R}^{n\times n}$ diagonal matrix and ${\mathbf{V}}$ is a $\mathbb{R}^{m\times n}$ orthogonal matrix.
For brevity, we can write ${\mathbf{B}}=\bm{\Sigma}{\mathbf{V}}^{\top}$, and thus we have that any $n\times m$ matrix ${\mathbf{W}}$ can be written as

$$ $\displaystyle{\mathbf{W}}={\mathbf{U}}{\mathbf{B}}.$ (14) $$

Now, we will say that two matrices ${\mathbf{A}},{\mathbf{B}}$ over the same space are rotationally equivalent ${\mathbf{A}}\sim{\mathbf{B}}$ if there exists an orthogonal matrix ${\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}$ such that ${\mathbf{A}}={\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}{\mathbf{B}}$; denote the equivalence class of ${\mathbf{A}}$ as $[{\mathbf{B}}]$.

Now, assume that ${\mathbf{B}}\sim P_{\mathbf{B}}$ and let $P_{{\mathbf{W}}\mid{\mathbf{B}}}({\mathbf{W}})\,\propto\,\mathbbm{1}\{{\mathbf{W}}\in[{\mathbf{B}}]\}$ be the uniform distribution on $[{\mathbf{B}}]$, i.e. for an orthogonal matrix ${\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}$ we have $P_{{\mathbf{W}}\mid{\mathbf{B}}}({\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}{\mathbf{W}})=P_{{\mathbf{W}}\mid{\mathbf{B}}}({\mathbf{W}})$.
Letting $f^{\mathbf{B}}({\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}})={\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}{\mathbf{B}}$, this actually shows that $P_{{\mathbf{W}}\mid{\mathbf{B}}}({\mathbf{W}})=f^{\mathbf{B}}\,\#\,\mathrm{Unif}(\mathcal{O}(n))$, where $\mathcal{O}(n)$ denotes the $n$-dimensional real orthogonal group, $\#$ denotes a pushforward measure, and $\mathrm{Unif}(\mathcal{O}(n))$ is the Haar measure on $\mathcal{O}(n)$.
Note, that this immediately implies that the marginal is also rotationally invariant:

$$ $\displaystyle P_{\mathbf{W}}({\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}{\mathbf{W}})=\int P_{{\mathbf{W}}\mid{\mathbf{B}}}({\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}{\mathbf{W}}\mid{\mathbf{B}})\,dP_{\mathbf{B}}({\mathbf{B}})=\int P_{{\mathbf{W}}\mid{\mathbf{B}}}({\mathbf{W}}\mid{\mathbf{B}})\,dP_{\mathbf{B}}({\mathbf{B}})=P_{\mathbf{W}}({\mathbf{W}}).$ (15) $$

Now, if the neural network we wish to encode is rotationally invariant, then we can always “standardize” ${\mathbf{W}}$ first by computing its SVD ${\mathbf{W}}={\mathbf{U}}{\mathbf{B}}$ and setting ${\mathbf{W}}\leftarrow{\mathbf{B}}$.
Then, to encode ${\mathbf{B}}$, we sample a random rotation ${\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}$, and encode
Importantly, we can always recover ${\mathbf{B}}$ (up to the signs of the rows of ${\mathbf{V}}$) by performing an SVD.
Therefore, we have the following procedure:

Before encoding:

- 1.
Run training algorithm to get ${\mathbf{W}}$ for a rotationally invariant NN.
- 2.
Compute the SVD ${\mathbf{W}}={\mathbf{U}}{\mathbf{B}}$, where ${\mathbf{B}}=\bm{\Sigma}{\mathbf{V}}^{\top}$.
- 3.
Set ${\mathbf{W}}\leftarrow{\mathbf{B}}$; this doesn’t change the NN output.

During encoding:

- 1.
Decode an orthogonal matrix ${\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}\sim\mathrm{Unif}(\mathcal{O}(n))$ from the message.
- 2.
Encode ${\mathbf{W}}^{\prime}={\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}{\mathbf{B}}$ using $P_{\mathbf{W}}$ into the message.
- 3.
Compute the SVD of ${\mathbf{W}}^{\prime}={\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}{\mathbf{B}}={\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}^{\prime}{\mathbf{B}}^{\prime}$ and record the $n$ signs of ${\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}^{\prime}$ relative to ${\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}$.
Concretely, compute the diagonal sign matrix $\sigma$ such that $\sigma{\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}^{\prime}={\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}$.
Then, $\sigma$ can be encoded using $n$ bits, one for each sign on the diagonal.

During decoding

- 1.
Decode $\sigma$ and ${\mathbf{W}}^{\prime}$ using $P_{\mathbf{W}}$.
- 2.
Compute the SVD of ${\mathbf{W}}^{\prime}={\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}^{\prime}{\mathbf{B}}^{\prime}$, use ${\mathbf{W}}^{\prime}$ (or ${\mathbf{B}}^{\prime}$) in the NN.
- 3.
Compute ${\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}=\sigma{\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}^{\prime}$.
- 4.
Code ${\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}$ back into the stream using $\mathrm{Unif}(\mathcal{O}(n))$.

Computing the coding cost.
Since ${\mathbf{W}}$ is continuous, let $p_{{\mathbf{W}}\mid{\mathbf{B}}}$ and and $p_{\mathbf{W}}$ denote the densities of $P_{{\mathbf{W}}\mid{\mathbf{B}}}$ and $P_{\mathbf{W}}$, respectively.
Since we cannot encode continuous variables, we now make two approximations.
First, we discretize the densities: we fix a precision $\delta$ bits, so given that ${\mathbf{W}}$ is $n\times m$-dimensional, this gives us a set $\mathcal{W}$ of $2^{nm\delta}$ values we can represent.
For a representable matrix $w\in\mathcal{W}$, we set $\hat{P}_{\mathbf{W}}(w)\approx p_{\mathbf{W}}(w)\cdot 2^{-nm\delta}$ and $\hat{P}_{{\mathbf{W}}\mid B}(w\mid{\mathbf{B}})\approx p_{{\mathbf{W}}\mid{\mathbf{B}}}(w\mid{\mathbf{B}})\cdot 2^{-nm\delta}$.
These approximations are accurate when the densities are piecewise constant, which is true in this case as $p_{{\mathbf{W}}\mid{\mathbf{B}}}$ is constant by definition, and we shall assume in a moment that $p_{{\mathbf{W}}}$ is constant as well.

Concretely by our earlier definition,
$p_{{\mathbf{W}}\mid{\mathbf{B}}}(w\mid{\mathbf{B}})\propto\mathbbm{1}[w\in[{\mathbf{B}}]]$.
However, note that since $[{\mathbf{B}}]$ is a proper *subspace* of $\mathbb{R}^{n\times m}$ (it is a copy of $\mathcal{O}(n)$), it has zero volume.
Thus, as our second approximation, we discretize the conditional distribution by extending its support to the ambient space.
Namely, we set $\hat{P}_{{\mathbf{W}}\mid{\mathbf{B}}}(w\mid{\mathbf{B}})\propto\mathbbm{1}[w\in\mathcal{W}\cap[{\mathbf{B}}]_{\delta/2}]\cdot 2^{-nm\delta}$, where $[{\mathbf{B}}]_{\delta/2}$ is the uniform $\delta/2$-expansion of $[{\mathbf{B}}]$:

$$ $\displaystyle[{\mathbf{B}}]_{\delta/2}=\{{\mathbf{W}}\in\mathbb{R}^{n\times m}\mid\exists{\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}\in\mathcal{O}(n):\lVert{\mathbf{W}}-{\color[rgb]{1,0.49,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0.49,0}\pgfsys@color@cmyk@stroke{0}{0.51}{1}{0}\pgfsys@color@cmyk@fill{0}{0.51}{1}{0}{\mathbf{Q}}}{\mathbf{B}}\rVert_{\infty}\leq\delta/2\}.$ (16) $$

What is the size of $\mathcal{W}\cap[{\mathbf{B}}]_{\delta/2}$?
Since $[{\mathbf{B}}]$ is a $n(n-1)/2$ dimensional subspace of $\mathbb{R}^{n\times m}$, for a large-enough precision $\delta$ we will have $\lvert\mathcal{W}\cap[{\mathbf{B}}]_{\delta/2}\rvert\approx 2^{-\delta\cdot n(n-1)/2}$.
Though this approximation should be quite accurate, we do not expect equality in any practical situation; and the lack of this equality contributes to the numerical issues we describe in [section 3.3](#S3.SS3).

Now, for large enough $\delta$, we have

$$ $\displaystyle\hat{P}_{{\mathbf{W}}\mid{\mathbf{B}}}(w\mid{\mathbf{B}})\approx\mathbbm{1}[w\in[{\mathbf{B}}]_{\delta/2}]\cdot 2^{-(nm-n(n-1)/2)\delta}.$ $$

Finally, assuming that $P_{\mathbf{B}}$ is uniform results in $P_{\mathbf{W}}$ being uniform as well, hence we have

$$ $\displaystyle\hat{P}_{\mathbf{W}}(w)=2^{-nm\delta}.$ $$

Therefore, decoding ${\mathbf{W}}\mid{\mathbf{B}}$ saves approximately $-\log_{2}\hat{P}_{{\mathbf{W}}\mid{\mathbf{B}}}({\mathbf{W}}\mid{\mathbf{B}})$ bits and encoding it costs $-\log_{2}\hat{P}_{\mathbf{W}}({\mathbf{W}})+n$ bits (where the $+n$ term comes from encoding the sign matrix $\sigma$), the total coding cost is

$$ $\displaystyle\approx\log_{2}\frac{\hat{P}_{{\mathbf{W}}\mid{\mathbf{B}}}({\mathbf{W}}\mid{\mathbf{B}})}{\hat{P}_{\mathbf{W}}({\mathbf{W}})}+n\approx\log_{2}\frac{2^{-(nm-n(n-1)/2)\delta}}{2^{-nm\delta}}+n=\frac{n(n-1)}{2}\delta+n\text{ bits},$ $$

which matches the coding cost of our proposed scheme.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: See the weaknesses.
soundness: 3
strengths: 1. The proposed method is novel and insightful
2. The proposed method is well-motivated and has the potential to make a broader impact.
3. The experiment results are promising.
summary: In this paper, the authors highlight that the rotational symmetries of SliceGPT introduce redundancies. Based on SliceGPT, they propose further compressing the weights by the bits-back coding algorithm. Specifically, rather than treating all weight configurations as unique, they encode weights up to an equivalence class defined by rotations, enabling smaller memory requirements. They conducted experiments on several benchmarks with multiple models. The results verify the effectiveness of their proposed method.

**Strengths**
1. The proposed method is novel and insightful
2. The proposed method is well-motivated and has the potential to make a broader impact.
3. The experiment results are promising.

**Weaknesses**
1. The writing is not self-contained. Specifically, the paper relies heavily on bits-back coding. However, they do not properly connect SliceGPT with the previously proposed bits-back coding. It is hard to understand the actual algorithm.
2. It is questionable if the method can be applied in the real world given the compression/decompression and matrix decomposition procedures involved. The run speed of this method could be slower than that of the vanilla Transformer model.

In summary, the paper is insightful and well-motivated. However, the writing is not self-contained and the overhead could hinder the real-world application. As a result, I recommend a weak acceptance.
weaknesses: 1. The writing is not self-contained. Specifically, the paper relies heavily on bits-back coding. However, they do not properly connect SliceGPT with the previously proposed bits-back coding. It is hard to understand the actual algorithm.
2. It is questionable if the method can be applied in the real world given the compression/decompression and matrix decomposition procedures involved. The run speed of this method could be slower than that of the vanilla Transformer model.

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 3
questions: * How does the proposed method perform in terms of inference latency and throughput gains compared to SliceGPT when applied on actual hardware like GPUs? If the effectiveness of this aspect is demonstrated, I would be inclined to increase my rating.
soundness: 3
strengths: * The paper proposes a method to compress the rotation matrix Q introduced by SliceGPT using the bits-back algorithm, effectively reducing the parameter overhead.
* It demonstrates that the rotation matrix Q can be encoded and decoded using the bits-back algorithm without requiring a calibration set, relying solely on the weight matrix.
* The study shows that while the actual compression rate of SliceGPT with the rotation matrix Q is approximately 9%, the proposed method can achieve a closer-to-expected compression rate of 13%. It also demonstrates that applying the proposed encoding method to the rotation matrix Q in models such as OPT and LLaMA2-7B does not result in significant differences in Commonsense Reasoning (CSR) performance.
summary: This paper proposes the application of the bits-back algorithm to reduce the overhead of additional matrices introduced by pruning large language models (LLMs) using SliceGPT. In the SliceGPT method, an additional matrix is introduced for the rotation matrix, which helps in maintaining accuracy but results in additional computational overhead, thereby acting as a compression overhead. To address this issue, we propose an algorithm that encodes/decodes the rotation matrix using the bits-back algorithm, demonstrating that the rotation matrix can be computed solely through the decoding process during inference. Our proposed method shows an additional 3-5% improvement in compression efficiency compared to the practical compression rate of SliceGPT.
weaknesses: * The paper lacks sufficient analysis and experimentation regarding the practical impact on latency and throughput during inference when decoding the rotation matrix Q using the proposed method.
* The proposed method is somewhat limited in scope, as it can only be applied after the implementation of SliceGPT, thereby restricting its applicability.
* The actual benefits of encoding the rotation matrix Q in terms of inference latency and throughput might be minimal. It is likely that during the prefill stage, the additional decoding step for the rotation matrix Q could result in higher inference latency and lower throughput compared to SliceGPT alone.

---

confidence: 2
contribution: 3
initial_rating: 6
presentation: 3
questions: - What is the prospective effectiveness of the method when it comes to implementation on the models with precision format lower than float16? 
- Is it possible to apply the bits-back coding method to the architectures that are not transformers or the architectures compressed with different methods?
soundness: 3
strengths: - The paper presents bits-back coding used on neural network models, mainly focusing on enlarging language compression. 
- The proposed method is computationally feasible since it runs without retraining. 
- The paper's novel technique is evaluated on models, such as OPT and Llama-2, demonstrating performance metrics are not significantly affected in terms of perplexities drop.
summary: The paper presents a novel training-free compression technique of large language models that exploits rotational symmetries in the weight space. It uses bits-back coding, a compression strategy that takes advantage of these rotational symmetries to compress Transformer models by about three to five percent while impacting the model's perplexity in a negligible way. The method was tested on SliceGPT-pruned Transformers, namely the OPT and Llama-2.
weaknesses: -  This approach is inherently SliceGPT pruning and Transformer-specific architecture, which may also limit its use to other neural networks or pruning techniques.
- The methodology relies only on Transformer architectures, so applicability to lighter models suited to edge devices could be considered.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: The beginning of Section 2 uses the word “delving” prominently. As the word “delve” is strongly associated with large language model outputs, we advise the authors to rephrase the sentence.
soundness: 2
strengths: 1. The proposed method is training-free, making the result independent from the choice of calibration set.
2. The proposed method can be computed using only a CPU, without heavy computational requirements. This will make adoption easier.
summary: This work proposes to apply a coding scheme to utilize symmetries made available by the SliceGPT method for training-free weight-only quantization. The resulting method achieves an additional 3-5% reduction in the total weight sizes for SliceGPT compressed models. The authors show that their resulting models do not diverge significantly from the original models when evaluated on tasks such as PIQA, WinoGrande, and HellaSwag.
weaknesses: 1. The improvement of 3~5% appears small unless the method does not impose other overheads. However, there is no detailed analysis of how much memory the other components, such as the correction code, use.

2. Additionally, the work does not include any analysis of the overhead in terms of the time required for inference caused by applying additional computations to the model. Even if computing the rotation can be performed on CPU, there should be an analysis of the effect on inference latency when measured end-to-end.

Meta-review: This paper proposes a method to compress rotationally symmetric weight matrices. Due to their rotational symmetry, the encoding of these weight matrices can be redundant. To address this, the authors propose the bits-back coding algorithm for compression.
Main strengths:
- The paper makes an interesting algorithmic contribution.

Main weaknesses:
- The proposed method has only been benchmarked on SliceGPT pruning and Transformers.
- The achieved savings are limited.

It will help if the authors take concrete steps to demonstrate broader applicability of the method.

Decision: Reject