Getting Free Bits Back from Rotational Symmetries in LLMs

Thank you for your valuable feedback, which helped us improve our manuscript. We are glad that you appreciate that our method is easy to adopt. Below, we reply to your concerns one by one.

1 Weakness 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.

This a misunderstanding. The 3-5% bits already take the correction code into account, so the 3-5% savings are net. In fact, the length of the correction code is negligible. We appreciate that you pointed out this potential confusion, and therefore, we have updated the caption of Table 1 to clarify this.

2. Weakness 2:

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.

Thank you for raising this question. We have updated our manuscript to include the results and discussion on the encoding and decoding time. Please refer to Table 2 and the runtime analysis paragraph on page 10. We also list Table 2 below for easier reference:

As we can see, our algorithm only takes seconds to minutes on a consumer-grade GPU. We also provide the runtime on CPU in Appendix C.1. Also, as we discussed in lines 501-511, we can even parallelize this process to accelerate the execution further.

Additionally, we note that our approach aims to reduce the storage space and transmission cost. Therefore, we will only run the encoding algorithm when saving the model and decoding when loading the model. Once the model is decoded and loaded into memory, the inference time will be identical to the vanilla Transformer. Therefore, when measured end-to-end, our approach only increases the whole procedure by a few seconds/minutes. Therefore, this is not a big obstacle for practical usage.

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.

Thank you for your suggestions! We have rephrased this sentence.

Thank you once again for taking the time to review our work and our response. We believe we have addressed your questions. We are happy to discuss any further concerns you might have. However, If you find our clarifications satisfactory, we kindly invite you to raise the score.

I thank the authors for their detailed response. It has helped clarify the scope and motivation of the work. However, if the aim of the paper is to reduce disk storage, I believe that much more extensive comparisons should be made with compression methods such as Zstandard and byte shuffling, which also have the advantage of being lossless. Lossy algorithms for floating-point data compression also exist. In general, the model compression algorithms are designed to reduce the amount of memory in the GPU, not disk storage. This is because GPU memory is a scarcer resource, and reducing the required GPU memory allows models to run using fewer GPUs, which reduces costs. In addition, GPU memory must be accessed once per decoding step of the model, whereas storage needs only be accessed once at the very beginning when the model is being loaded to RAM. Because of this dynamic, I am curious whether there is a motivating use case in mind. For example, if many user-defined models need to be saved and transferred frequently, there may be a case to reduce the storage requirements, even at the cost of introducing lossy compression. However, even in this case, a rigorous comparison against both lossless and lossy techniques for model weight compression should be conducted for a fair comparison. Due to the difficulty of understanding the motivation of the work, I will keep my score.

Thank you again for the effort you put into our work. As only a few working days are left in the discussion period, we would like to ask if our response has satisfied your concerns. If so, we kindly invite you to consider raising the score. If any concerns remain, we are happy to discuss them further here.

Thank you for your reply; you make excellent points, and they made us see our work from a new angle.

I believe that much more extensive comparisons should be made with compression methods such as Zstandard and byte shuffling, which also have the advantage of being lossless.

You are correct that if we are storing the weights on the disk, then it is sensible to use a universal source coding algorithm such as the ones you mention to ensure we save as much space as possible.

However, our proposed method is not directly comparable to these source coding algorithms. In fact, we can view our proposed algorithm as a pre-processing step before universal source coding. To be completely clear, we suggest that we combine our proposed method with a source coding algorithm to form the following "bits-back" pipeline:

1. We obtain some network weights with rotational symmetries.
2. We use our method to eliminate the redundancies induced by the rotational symmetries in the weights.
3. We apply a universal source coding algorithm (e.g. Zstandard) to the output of our algorithm.
4. We save the output of this pipeline to the disk.

In our paper, we only looked at the gains we get if we apply our method only, without any universal source coding. Hence, an important concern arises: do we retain significant gains if we run the pipeline we suggest above, compared to just running universal source coding without our method?

Fortunately, the answer is positive. In particular, we compared the pipeline suggested above to universal source coding (we used ZIP in our experiment) on the OPT-2.7B model. Using ZIP only, the compressed size comes to 3.97 GB while using our suggested bits-back pipeline, it reduces to 3.79 GB, and approximately 5% gain in storage size as before. Note, that while the exact gain my vary depending on the universal source coding algorithm we use, these models are large enough that the gains we report here should be fairly robust across different source coding algorithms.

There is an intuitive reason for retaining the gain even after source coding: ZIP (or any other general-purpose universal source code) is unaware of the redundancies introduced by the rotational symmetry in the weights and, therefore, cannot utilise it to reduce storage size. From this perspective, the storage savings resulting from our bits-back method are "orthogonal" to the savings that result from source coding. Essentially, to the best of our knowledge, we are the first to address these structural redundancies in neural networks through bits-back coding. As such, our approach is not directly comparable to other compression algorithms that do not account for this specific type of redundancy.

Once again, thank you for this excellent point; we have also updated our paper to include the above discussion in the appendix!

Regarding your second concern about the motivation of our approach, we want to highlight 3 points:

1. We agree GPU is scarcer compared to disk. However, bandwidth is also another bottleneck. Therefore, reducing storage not only reduces disk costs but also reduces transmission costs and speeds up weights sharing.
2. One potential application that reflects point 1 is applying Federated Learning for LLMs, or for LoRAs. In these applications, the client needs to frequently send messages of weights/gradients to the server. Therefore, our approach can gain potential application in these areas.
3. we also want to note that, our approach can save 3-5% bits mostly for free and there is almost no drawback for applying our approach given its minimal runtime overhead and negligible influence on performance. Therefore, it is always beneficial to apply this approach in the cases where we need to store and transmit weights.

We thank you again for your detailed reply. If you find our further clarifications satisfactory, we kindly invite you to consider raising the score.

Thank you for your reply. However, given your comments, we believe there are three fundamental facts that we haven’t communicated clearly enough, and thus you appear to have misunderstood:

1. Our method is NOT a lossy quantization algorithm. Rather, our method is a lossless operation (up to floating-point precision) that we can apply before saving the weights.
2. Our method is NOT comparable with the methods you suggest. The methods you list, such as byteshuffle, are general preprocessing methods to improve the compressibility of model weights, and GZip and ZStandard are universal source codes. On the other hand, our method’s sole purpose is to eliminate the description inefficiency induced by rotational symmetries in the weights. This incomparability also means that we can freely combine our method with those you mention. Our previous response demonstrated how our method retains the ~5% gain in storage space when we combine it with Zip. We have now run some experiments where we apply Zstd with and without bshuffling as well as with and without applying our method on OPT-2.7 model weights:

As you can see, our algorithm still provides ~5% gain, regardless of whether we use shuffling, or not.

3. We are NOT proposing to apply our method to reduce GPU usage, only storage. Reducing GPU cost is out of the scope of design intent, as outlined in our manuscript and previous discussion.

To summarise, our method aims to reduce the storage cost of network weights, e.g., LLMs, at a negligible additional computational cost. Our method eliminates a redundancy that no other method can/does by leveraging the extra knowledge that there are rotational symmetries in the model weights. As such, we believe that our method is a significant and valuable addition to the LLM and the broader model compression literature. Thank you for the time you have invested in reviewing our paper and actively engaging in discussion with us. We believe we have addressed your concerns and thus kindly invite you once more to raise your score.

Thank you for your insightful review and questions, which have helped us improve our manuscript. We now reply to the stated weaknesses and questions.

1. weaknesses 1 & 3, and question (regarding impact on latency and throughput):

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 actual benefits of encoding the rotation matrix Q in terms of inference latency and throughput might be minimal. How does the proposed method perform in terms of inference latency and throughput gains compared to SliceGPT when applied on actual hardware like GPUs?

Thank you for raising this concern. While our approach requires additional time for decoding, there is no influence on the latency and throughput during inference:

(1) Our approach aims to reduce storage space and transmission costs. Therefore, we will only run the encoding algorithm when saving the model and decoding when loading the model. Once the model is decoded and loaded into memory, there is no overhead on the influence of the inference time and throughput.

(2) We measured the encoding and decoding time and updated our manuscript to include the results and discussion. Please refer to Table 2 and the runtime analysis paragraph on page 10. We also show Table 2 here for easy reference:

We can see that decoding the entire network is actually fast on the consumer-grade GPU. Therefore, even if we measure the inference time end-to-end, the influence of our approach on runtime is minimal.

(3) Additionally, we did not optimize our implementation for the decoding runtime, and there are ways to improve it. We discuss one such possibility in lines 501-511 in our updated manuscript: parallelizing the encoding and decoding to accelerate the execution.

2. weakness 2:

The proposed method is somewhat limited in scope, as it can only be applied after the implementation of SliceGPT, thereby restricting its applicability.

We agree that our approach focuses on SilceGPT. However, we emphasize that the concept of bits-back coding applied to neural networks is general and can be extended to any architecture exhibiting symmetries. One of our key contributions, as noted in the conclusion section, is establishing a connection between bits-back coding and statistical models that exhibit invariance under rotations and, more generally, under the action of the elements of a symmetry group. Below, we provide two examples where our algorithm (or its variations) can be employed to achieve free bits-back. We have also included these discussions in the Conclusion, Limitations, and Future Directions Section in our updated manuscript.

(1) Applying our approach to encoding LoRA modulation or weights decomposed in LoRA-style. Specifically, LoRA approximates a matrix $M$ by $M=AB$. We can see applying $Q$ to $A$ (as $AQ$) and $Q^T$ to $B$ (as $Q^TB$) will leave M invariant. Therefore, our proposed approach can be seamlessly applied in this context.

(2) Neural networks with permutation symmetry. It is well known that in many architectures, such as standard MLPs, permuting the hidden units in one layer and applying the reverse permutation to the subsequent layer leaves the output unchanged. We can modify our approach to apply bits-back coding in this case. Specifically, we can define a canonical order for hidden units based on a predefined criterion (e.g., sorting the weights or biases corresponding to each unit in descending order). During encoding, a permutation can be randomly selected by decoding bits from the current bitstream. During decoding, this permutation can be easily recovered by rearranging the hidden units back to their canonical order. In fact, it is a standard fact that permutation matrices are orthogonal (i.e., they can be thought of as rotations). Therefore, they can also be seen as a special case of our approach. However, the gain here is smaller than for the rotational symmetry case, as the permutation invariance of the hidden units introduces significantly less redundancy compared to rotations in general.

Thank you once again for taking the time to review our work and our response. We are happy to discuss any further questions you might have. However, should we have addressed your concerns, we kindly invite you to raise the score.

Thank you again for the effort and time you put into our paper. As only a few working days are left in the discussion, we would like to ask if our response has satisfied your concerns. If so, we kindly invite you to consider raising the score. If any concerns remain, we are happy to discuss them further here.

Thank you for your valuable feedback. We are encouraged by the positive comments around soundness and novelty. We address your concerns in the following.

1. Weakness 1 & Question 2

This approach is inherently SliceGPT pruning and Transformer-specific architecture, which may also limit its use to other neural networks or pruning techniques.

Is it possible to apply the bits-back coding method to the architectures that are not transformers or the architectures compressed with different methods?

We agree that the algorithm described in our manuscript focuses on SilceGPT. However, we emphasize that the concept of bits-back coding applied to neural networks is general and can be extended to other architecture exhibiting symmetries. One of our key contributions, as noted in the conclusion section, is establishing a connection between bits-back coding and networks with symmetrical properties. Below, we provide two examples where our algorithm (or its variations) can be employed to achieve free bits-back. We have also included these discussions in the Conclusion, Limitations, and Future Directions Section in our updated manuscript.

(1) Applying our approach to encoding LoRA modulation or weights decomposed in LoRA-style. Specifically, LoRA approximates a matrix $M$ by $M=BA$. We can see applying $Q$ to $B$ and $Q^T$ to $A$ will leave M invariant. Therefore, our proposed approach can be seamlessly applied in this context.

(2) Neural networks with permutation symmetry. It is well known that in many architectures, such as standard MLPs, permuting the hidden units in one layer and applying the reverse permutation to the subsequent layer leaves the output unchanged. We can modify our approach to apply bits-back coding in this case. Specifically, we can define a canonical order for hidden units based on a predefined criterion (e.g., sorting the weights or biases corresponding to each unit in descending order). During encoding, a permutation can be randomly selected by decoding bits from the current bitstream. During decoding, this permutation can be easily recovered by rearranging the hidden units back to their canonical order. In fact, it is a standard fact that permutation matrices are orthogonal (i.e., they can be thought of as rotations). Therefore, they can also be seen as a special case of our approach. However, the gain here is smaller than for the rotational symmetry case, as the permutation invariance of the hidden units introduces significantly less redundancy compared to rotations in general.

2. Weakness 2

Applicability to lighter models suited to edge devices could be considered.

Thank you for your valuable suggestion; applying our method to smaller models could be quite impactful! We only considered SliceGPT in our paper, because its parameters exhibit a very clear rotational invariance that we could exploit. If the reviewer can recommend other, smaller architectures with well-known parameter symmetries, we would be very grateful and interested to hear!

3. Question

What is the prospective effectiveness of the method when it comes to implementation on the models with precision format lower than float16?

Quantization can impact the performance of our approach. In our algorithm, the rotated matrix $WQ$ is encoded into the bitstream. During decoding, we use eigenvalue decomposition to recover $Q$ from $WQ$. If $WQ$ is quantized to a low precision, the quantized version may differ from the original $WQ$. As a result, performing eigenvalue decomposition on the quantized matrix may produce a recovered $\hat{Q}$ that has a larger difference compared to the original $Q$.

To illustrate this impact, we provide an extra experiment in Appendix C.2 in our updated manuscript. We apply simple linear quantization to reduce the precision to 11-15 bits and measure the compression rate with bits-back coding. We can see that as the precision decreases, the bits saved by our approach become smaller. This is because the size of the correction code increases to compensate for the error caused by lower precision. Our proposed approach consistently delivers gains when the precision is larger than 12-13 bits. We also want to note that we apply the simplest linear quantization in this simple demonstration. A better quantization strategy and correction code can further improve the performance of our approach. Designing a method that would allow us to quantize the weights below 12-bit precision is an interesting avenue for future research.

Thank you once again for taking the time to review our work and our response. We are happy to discuss any further questions you might have. However, should we have addressed your concerns, we kindly invite you to raise the score.

Thank you once again for the effort you put into reviewing our paper. As only a few working days are left in the discussion period, we would like to ask if our response has satisfied your concerns. If so, we kindly invite you to consider raising the score. If any concerns remain, we are happy to discuss them further here.

Thank you for your detailed review and constructive questions. We are glad that you found our paper novel, insightful, and to have the potential to have a broader impact. We now reply to your two questions below.

1. Question 1:

the paper relies heavily on bits-back coding. However, the paper does not properly connect SliceGPT with the previously proposed bits-back coding. It is hard to understand the actual algorithm.

This seems to be a misunderstanding. There is no a priori connection between SliceGPT and bits-back coding. In fact, making this connection is one of our contributions.

Bits-back coding is a data compression algorithm that works in cases where multiple choices are acceptable or equally good. In our case, as we explained in Remark 3.1, SliceGPT introduces symmetries into Transformers. Specifically, different weights, up to any random rotation, are equally good. Therefore, we can connect bits-back coding to SliceGPT. We then explain the benefit of this connection through an informal calculation of the codelength.

We appreciate this concern and agree that this connection does not seem crystal clear at first glance. Therefore, we have added a more detailed motivation from Lines 140-144.

2. Question 2:

It is questionable if the method can be applied in the real world … the run speed of this method could be slower than that of the vanilla Transformer model.

Thank you for raising this question. However, this is not a concern:

(1) Our approach aims to reduce the storage space and transmission cost. Therefore, we will only run the encoding algorithm when saving the model and decoding when loading the model. Once the model is decoded and loaded into memory, the inference time will be identical to the vanilla SliceGPT.

(2) We measured the encoding and decoding time and updated our manuscript to include the results and discussion. We list Table 2 in the updated manuscript for an easier reference:

For a more detailed discussion, please refer to the runtime analysis paragraph on page 10. As we can see, our algorithm only takes seconds to minutes on a consumer-grade GPU. Also, as we discussed in lines 501-511, we can even parallelize this process to accelerate the execution further.

Therefore, the runtime does not pose an obstacle to deploying our algorithm in real-world applications. Moreover, our algorithm can also be executed on a CPU, further broadening its applicability. We also include the encoding and decoding times for CPU execution in Appendix C.1 in the updated manuscript.

Thank you once again for taking the time to review our work and our response. We believe we have addressed your questions. If you find our clarifications satisfactory, we kindly invite you to consider raising your score.

Thank you once again for the effort you put into reviewing our paper. As only a few working days are left in the discussion period, we would like to ask if our response has satisfied your concerns. If so, we kindly invite you to consider raising the score. If any concerns remain, we are happy to discuss them further here.

3. Review cA7j raised a good question: as our aim is to reduce the storage and transmit cost, why we do not just use some source coding algorithm? We believe that question allows us to see our work from a new angle and, hence, also respond to it in the global response:

To answer this question, we highlight that we should not directly compare our proposed method to these source coding algorithms. In fact, we can view our proposed algorithm as a pre-processing step before universal source coding. To be completely clear, we suggest that we combine our proposed method with a source coding algorithm as follows:

1. We obtain some network weights with rotational symmetries.

2. We use our method to eliminate the redundancies induced by the rotational symmetries in the weights.

3. We apply a universal source coding algorithm (e.g. Zstandard) to the output of our algorithm.

4. We save the output of this pipeline to the disk.

In our paper, we looked at the gains we get if we apply our method only, without any universal source coding. In this response, we showcased that we still retain significant gains if we run the pipeline we suggest above, compared to just running universal source coding without our method. In particular, we compared the pipeline suggested above to universal source coding (we used ZIP in our experiment) on the OPT-2.7B model. Using ZIP only, the compressed size comes to 3.97 GB while using our suggested bits-back pipeline, it reduces to 3.79 GB, and approximately 5% gain in storage size as before. There is an intuitive reason for retaining the gain even after source coding: ZIP (or any other general-purpose universal source code) is unaware of the redundancies introduced by the rotational symmetry in the weights and, therefore, cannot utilize it to reduce space. From this perspective, the storage savings resulting from our bits-back method are “orthogonal” to the savings that result from source coding.