# Gradual Binary Search and Dimension Expansion: A general method for activation quantization in LLMs

Lucas Maisonnave, Cyril Moineau, Olivier Bichler, Fabrice Rastello

<figure><img src="image_1.png" /></figure>

## To cite this version:

Lucas Maisonnave, Cyril Moineau, Olivier Bichler, Fabrice Rastello. Gradual Binary Search and Dimension Expansion: A general method for activation quantization in LLMs. CORSE - Compiler Optimization and Run-time Systems. 2025. hal-05460223

HAL Id: hal-05460223

https://inria.hal.science/hal-05460223v1

Submitted on 15 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Gradual Binary Search and Dimension Expansion : A general method for activation quantization in LLMs

**Lucas Maisonnave**

Université Paris-Saclay
CEA, List
F-91120, Palaiseau, France
lucas.maisonnave@cea.fr

**Cyril Moineau**

Université Paris-Saclay
CEA, List
F-91120, Palaiseau, France
cyril.moineau@cea.fr

**Olivier Bichler**

Université Paris-Saclay
CEA, List
F-91120, Palaiseau, France
olivier.bichler@cea.fr

**Fabrice Rastello**

Univ. Grenoble Alpes,
Inria, CNRS, Grenoble INP, LIG,
38000 Grenoble, France
fabrice.rastello@inria.fr

## Abstract

Large language models (LLMs) have become pivotal in artificial intelligence, demonstrating strong capabilities in reasoning, understanding, and generating data. However, their deployment on edge devices is hindered by their substantial size, often reaching several billion parameters. Quantization is a widely used method to reduce memory usage and inference time, however LLMs present unique challenges due to the prevalence of outliers in their activations. In this work, we leverage the theoretical advantages of Hadamard matrices over random rotation matrices to push the boundaries of quantization in LLMs. We demonstrate that Hadamard matrices are more effective in reducing outliers, which are a significant obstacle in achieving low-bit quantization. Our method based on a gradual binary search enables 3-bit quantization for weights, activations, and key-value (KV) caches, resulting in a 40% increase in accuracy on common benchmarks compared to SoTA methods. We extend the use of rotation matrices to support non-power-of-2 embedding dimensions, similar to the Qwen architecture, by employing the Paley's algorithm. Our experimental results on multiple models family like Mistral, LLaMA, and Qwen demonstrate the effectiveness of our approach, outperforming existing methods and enabling practical 3-bit quantization.

## 1 Introduction

Large Language Models (LLMs) have become a central component of artificial intelligence due to their strong capabilities in reasoning, understanding, and generating data. These impressive capabilities are attributed to the quality of the data used during training, the model architecture, and the size of the model, which often reaches several billion parameters. This size limitation restricts their deployment on edge devices. Quantization is a widely used method to reduce memory usage and inference time [12, 13], but the challenges differ compared to those faced with Convolutional Neural Networks (CNNs) [9, 29].

Weights are relatively easy to quantize for both CNNs and LLMs and can often achieve ternary quantization without significant loss of accuracy [20, 32]. However, activations behave differently in transformer architectures [23]. The presence of outliers in activations makes conventional quantization (symmetric uniform) very challenging, hindering our ability to achieve 4-bit quantization. LLMs are
known to produce spikes in its layers and for some tokens that can be handled separately or diffused in the tensor [7, 29].

One very promising approach to overcome this limitation is to use rotation matrices to redistribute weights and activation values, thereby minimizing the impact of outliers [19, 2]. Additionally, methods such as prefix tokens have shown very interesting results in managing outliers in LLMs [4, 24].

In this work, we leverage results on rotation matrices to push the boundaries further and enable 3-bit Weights, Activations, KV cache (WAKV) quantization by employing a binary search. We extend this method to a more general approach capable of handling non-power-of-2 embedding dimensions, similar to Qwen. Our main contributions are:

* A theoretical demonstration that Hadamard matrices are more effective in reducing outliers than rotation matrices drawn on the unit sphere.

* 3-bit quantization for weights, activations, and KV cache, resulting in a 40% increase in accuracy on common benchmarks using a gradual binary search.

* Extension of rotation matrices to support non-power-of-2 embedding dimensions using the Paley's algorithm.

* The introduction of dimension expansion to build a more general rotation pipeline allowing architectures like Qwen to work with rotations.

# 2 Related Works

## 2.1 Quantization

Quantizing models involves reducing the number of bits required to store and compute model activations. This process is crucial for deploying LLMs on resource-constrained devices. To achieve this, we define a scaling factor that determines the distance between quantization bins and the range of values to be compressed.

For symmetric uniform quantization, we apply a rounding function to a scaled distribution:

$$ \hat{X} = \text{round} \left( \frac{X}{\Delta} \right) \Delta, \Delta = \frac{\max |X|}{2^b - 1} $$

where $\Delta$ is the scaling factor, $b$ is the bitwidth, and $\max |X|$ is the maximum absolute value of the distribution, preserving extreme values for activations.

Such quantization can be applied per-token, where each token has a different scaling factor, or per-tensor, where a single scaling factor is used for each activation tensor [12, 13]. Per-token quantization is more challenging to implement efficiently in practice compared to per-tensor quantization but results in better quantization performances. Scaling factors can be static during inference, based on statistics computed on a subset of the dataset, or dynamic, recomputed at each step.

Quantization can lead to a significant drop in performance when applied post-training (PTQ) [30]. To mitigate this, some methods adapt weights to the noise introduced during a training phase (QAT) [18, 8]. Typically, for LLMs, only linear layers are quantized, as they account for most of the computation cost, while normalization layers, matrix multiplications, and the softmax function within the attention block are left unquantized.

## 2.2 Outliers

Quantizing LLM weights is relatively straightforward and does not require extensive efforts to achieve. Techniques like GPTQ [11] enables 8-bit quantization without retraining, preserving model accuracy. Some QAT methods can even push the boundaries to 1-bit quantization, as seen in BitNet [26] or ternary quantization [20].

However, LLMs present unique challenges due to the prevalence of extreme high values in their activations [27, 23, 15, 17]. The scaling factor, which is directly tied to the maximum absolute value, often causes most of the distribution to be rounded to zero, leading to performance degradation. To
<figure><img src="image_3.png" /><figcaption>Figure 1: Architecture's pipeline with rotation matrices $R_1, R_2, R_3, R_4$ and dimension expansion. Red lines represent expanded tokens in $4096+d$ dimensions and green lines represent non expanded tokens. Projections in red (QKV, Gate, Up and $LM_{head}$) have their input weights dimension expanded and projections in green (Out, Down and Embeddings) have their output weights dimension expanded</figcaption></figure>

address this, techniques like LLM.int8() [7] cluster these outliers and quantize them separately from the main distribution.

Alternative methods, such as SmoothQuant [29], shift the quantization challenge from activations to weights by introducing a scaling parameter between them. Other approaches attempt to relocate these spikes into "sink tokens" before quantization [24]. Some research focuses on understanding the upstream causes of these spikes during the learning process to limit their impact post-training [23]. Additionally, efforts are made to better locate these outliers by visualizing the layers, dimensions, and tokens that may be their source [22].

## 2.3 Rotation Matrices

### 2.3.1 Random orthogonal matrices

Rotation matrices play a pivotal role in various applications, including signal processing, computer vision, and machine learning. These matrices are orthogonal and invertible by their transpose, meaning they preserve the length of vectors and the angles between them. In the context of quantization, rotation matrices can be used to decorrelate and redistribute the energy of model activations [1, 2, 3], making them more amenable to quantization. The idea is to apply orthogonal matrices before quantization to flatten the distribution and then recover the tensor by applying its inverse (see Figure 1). Part of this process can be pre-computed and fused with weights and the rest needs to be done at inference [1].

However, the effectiveness of rotation matrices depends on the specific matrix used. Randomly drawn orthogonal rotation matrices can introduce noise and reduce the overall performance of the model. To mitigate this, some methods adapt the rotation matrices during a training phase to better align with the model's weights and activations [19].

In practice, rotation matrices are often used in conjunction with other quantization techniques, such as GPTQ. This combination allows for more robust and efficient quantization of large language models, enabling their deployment on resource-constrained devices.

### 2.3.2 Hadamard matrices

Hadamard matrices are another powerful tool in the quantization arsenal. These matrices are orthogonal matrices and all their entries are either +1 or -1 making them very efficient to compute (eq 1). Hadamard matrices have been extensively used in signal processing, error-correcting codes [14], and more recently, in the quantization of neural networks [1, 2].

One of the key advantages of Hadamard matrices is their ability to decorrelate the activations of a model. By applying a Hadamard matrix, the activations are transformed into a new basis where the correlations between different dimensions are minimized. This decorrelation property is particularly
useful in reducing the impact of outliers, as the extreme values are spread out across multiple dimensions.

Hadamard matrices of order $2^n$ can be constructed recursively using the Fast Hadamard Transform (FHT) method: For $n \ge 1$, construct the $2^{n+1} \times 2^{n+1}$ Hadamard matrix $H_{2^{n+1}}$ using the $2^n \times 2^n$ Hadamard matrix $H_{2^n}$ as follows:

$$H_2 = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}, \quad H_4 = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{pmatrix}, \quad H_{2^{n+1}} = \begin{pmatrix} H_{2^n} & H_{2^n} \\ H_{2^n} & -H_{2^n} \end{pmatrix} \quad (1)$$

This method is highly efficient for generating Hadamard matrices and can be applied in real-time. In summary, both rotation matrices and Hadamard matrices are essential for the quantization of large language models. However, Hadamard matrices offer several advantages: they can be generated more efficiently, their structure of containing only 1 and -1 makes them highly efficient for matrix multiplication, and they are known to handle outliers in activations more effectively [19]. In the following sections, we will theoretically demonstrate that Hadamard matrices are more effective than random rotation matrices drawn from the unit sphere in reducing the amplitude of outliers.

### 2.3.3 Paley algorithm

To generate other dimensions $n$ for Hadamard matrix we can use known small matrices and apply power of 2 algorithm as used in QuaRot [2] but it can be limiting and doesn't cover a lot of values. To overcome this issue we can use the Paley's Algorithm that generate a Hadamard matrix $n \times n$ if $n-1$ is a prime number and $n-1 \equiv 3 \pmod 4$. This algorithm is described below (Algorithm 2) and needs to generate Legendre symbols $(\frac{a}{p})$ which take any integer number $a$ and prime number $p$ to produce a value in $\{-1, 0, 1\}$ as below:

* If $a$ is a quadratic residue modulo $p$, then there exists an integer $x$ such that $x^2 \equiv a \pmod p$. In this case, $(\frac{a}{p}) = 1$.

* If $a$ is a quadratic non-residue modulo $p$, then there is no integer $x$ such that $x^2 \equiv a \pmod p$. In this case, $(\frac{a}{p}) = -1$.

* If $a \equiv 0 \pmod p$, then $(\frac{a}{p}) = 0$.

Generating Legendre symbols can be time-consuming, especially for high-dimensional matrices. However, in the following sections, we will use this algorithm to generate non-power-of-2 Hadamard matrices and fuse them with the weights, so we only need to compute the Legendre symbols once.

# 3 Analysis and theoretical demonstrations

## 3.1 Clipping Ratio

To perform quantization we can play on several parameters to improve the effectiveness of the process, for example in LSQ [9] they optimise the scaling factor trough training, or FracBits [31] which tries to find the best precision for every layer. Other works highlighted the importance of the clipping ratio like PACT [5] where the optimization is done during training. Some others apply a Grid Search [4] to find the best configuration particularly useful for LLMs where training or fine tuning can be very time consuming.

Clipping ratios are essential for managing outliers, as they establish the balance between maintaining high precision for small values and preserving a maximum value close to its original. However, the model exhibits significant variability in how quantization responds to changes in the clipping ratio. While some projections can tolerate very low clipping ratios, others experience a substantial accuracy drop with even slight adjustments (see Appendix C). Therefore, to effectively manage this variability, a tailored clipping ratio must be determined for each projection.
Previous studies have shown that quantization error is not always the best metric to guide the optimization process for quantization parameters [21]. Specifically, at very low precision levels, such as 4 or 3 bits, the set of quantized weights deviates significantly from the optimized configuration obtained during training. Attempting to recover this configuration using quantization error often results in an ineffective set of weights. To address this issue, we can use perplexity as an objective function. Perplexity provides a more accurate representation of model performance and is computationally efficient, as it is based on Cross Entropy Loss, which is frequently used during training for its smoothness.

## 3.2 Hadamard Matrices reduce outliers more

Experimentally, it is observed that Hadamard matrices tend to reduce better the amplitude of outliers present in the layers of LLMs, which directly impacts the performance of these models. However, the question of why such a phenomenon occurs has remained open from a theoretical perspective. We now provide an answer to this question.

**Theorem 3.1 (Hadamard reduction).** $\forall x \in \mathbb{R}^n$ containing an outlier, i.e., $x = (c, \epsilon, ..., \epsilon)^T$ with $c \gg \epsilon$ we have

$$ \max_{1 \le i \le n} |(Hx)_i| \le \max_{1 \le i \le n} |(Qx)_i| $$

with $H$ a Hadamard matrix belonging to $\mathbb{R}^{n \times n}$ and $Q$ a rotation matrix drawn randomly on the unit sphere $S^{n-1} = \{x \in \mathbb{R}^n : ||x||_2 = 1\}$.

To demonstrate Theorem 3.1, we can calculate the two terms of the inequality and thus show the superiority of one over the other.

**Lemma 3.1 (Hadamard incoherence).** For $H$ a Hadamard matrix belonging to $\mathbb{R}^{n \times n}$ and $x = (c, \epsilon, ..., \epsilon)^T$ with $c \gg \epsilon$

$$ \max_{1 \le i \le n} |(Hx)_i| = \frac{c}{\sqrt{n}} $$

**Lemma 3.2 (Rotation incoherence).** For $Q$ a rotation matrix drawn randomly on the unit sphere $S^{n-1} = \{x \in \mathbb{R}^n : ||x||_2 = 1\}$ and $x = (c, 0, ..., 0)^T$ with $c \gg 1$

$$ \max_{1 \le i \le n} |(Qx)_i| = c \sqrt{\frac{2 \log n}{n}} $$

We can prove in Lemma 3.1 and Lemma 3.2 that the reduction of outliers with a Hadamard matrix is of order $O(\frac{1}{\sqrt{n}})$ and $O(\sqrt{\frac{2 \log n}{n}})$ for a random orthogonal matrix (demonstrations are done in Appendix A). These results prove Theorem 3.1 and also show the close link between reduction and the dimension of embeddings in LLMs. The higher the dimension is the stronger the reduction will be. We can also demonsatrate in Theorem 3.2 that Hadamard matrices are optimal and the best group of matrices to reduce outliers.

**Theorem 3.2 (Hadamard optimality).** For any orthogonal matrix $Q \in \mathbb{R}^{n \times n}$ we have:

$$ \max_{1 \le i,j \le n} |Q_{ij}| \ge \frac{1}{\sqrt{n}} $$

And a Hadamard matrix reaches this bound.

# 4 Method

## 4.1 Gradual Binary Search

In Section 3.1, we emphasize the importance of the clipping ratio parameter and its significant impact on model performance. We stress the need to optimize each projection with its own clipping ratio for best results. Our primary contribution is an algorithm that determines the optimal clipping ratio for each quantizer using a binary search (Algorithm 1). To drive the binary search, we minimize perplexity across various clipping ratios, assuming a single minimum and a convex landscape.
**Algorithm 1 Gradual Binary Search**

**Require:** A model *M*, a dataset *D*, a threshold *ϵ*
**Ensure:** A list L of clipping ratios
1: *n* ← number of projections in *M*
2: *L* ← []
3: **for** *i* ← 1 to *n* − 1 **do**
4:     *a* ← 0
5:     *b* ← 1
6:     *m* ← (*a* + *b*)/2
7:     *M* ← quantize Proj(*M*, *i*)
8:     *f*<sub>*m*</sub> = evaluate(*M*, *D*, *L* + *m*)
9:     iteration ← 0
10:    **while** *b* − *a* > *ϵ* **do**
11:        **if** iteration is even **then**
12:            *x* ← (*a* + *m*)/2
13:            **else**
14:                *x* ← (*b* + *m*)/2
15:            **end if**
16:        *f*<sub>*x*</sub> ← evaluate(*M*, *D*, *L* + *x*)
17:        **if** *f*<sub>*x*</sub> < *f*<sub>*m*</sub> **then**
18:            **if** *x* < *m* **then**
19:                *b* ← *m*
20:            **else**
21:                *a* ← *m*
22:            **end if**
23:        *m*, *f*<sub>*m*</sub> ← *x*, *f*<sub>*x*</sub>
24:        **else**
25:            **if** *x* < *m* **then**
26:                *a* ← *x*
27:            **else**
28:                *b* ← *x*
29:            **end if**
30:        **end if**
31:    iteration ← iteration + 1
32:    **end while**
33:    *L* = *L* + *m*
34: **end for**
35: **return** *L*

▷ + operand on L means concatenation

▷ We keep track of the middle element
▷ Quantize projection *i* of model *M*
▷ Evaluate model *M* on dataset *D* with clipping ratios *L*

▷ We iterate until we converge
▷ Allows to use only one loop for binary search

▷ Evaluate model on a new clipping ratio
▷ If we improve PPL (the lower the better) we keep it
▷ If the target is less than the middle, search the left half

▷ If not, search the right half

▷ Add new element to the list

Additionally, we quantize our model gradually: first, we quantize and optimize the initial linear projection while keeping the rest in FP16, then use the obtained parameters to quantize and optimize the next projection, and so on. This process is discussed in Appendix C where we experimentally show the necessity to optimize gradually the clipping ratio.

## 4.2 Increasing dimensions

**Lemma 4.1 (Expanding limit).** For a matrix product *AB* with *A* ∈ ℝ<sup>*m*×*n*</sup> and *B* ∈ ℝ<sup>*n*×*p*</sup> in *b* bits and *A'* *B'* with *A'* ∈ ℝ<sup>*m*×(*n*+*d*)</sup> and *B'* ∈ ℝ<sup>(*n+*d)×*p*</sup> in *b'* bits we must have *d* ≤ <sup>*n*(*b*−*b'*)</sup>⁄<sub>*b'*</sub> so that BitOps(*A'* *B'*') ≤ BitOps(*AB*), with *m*, *n*, *p*, *b*, *b'* ∈ N and *b'* ≤ *b*

One important limitation of QuaRot's implementation of rotation matrices in LLMs is the necessity to have embeddings in a power of 2 dimension which can be very limiting in some architectures like Qwen2.5-1.5B which have features in dimension 1536 and can not be quantized with QuaRot. To overcome this problem we increase manually the dimension of embedding by adding zeros in the weights (independently developed in [10]) to reach a dimension suitable to generate a Hadamard matrix with the Paley's algorithm 2. Then we save the matrix product of weights padded with 0s and the Hadamard matrix as our new weights (see figure 1 and Eq 2 for an example in dimension 4). The primary goal is to create a more versatile pipeline compatible with any architecture but it also
enhance performance through increased dimensionality.

$$W \leftarrow \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{pmatrix} \times \begin{pmatrix} a & b \\ c & d \\ 0 & 0 \\ 0 & 0 \end{pmatrix} \quad (2)$$

Indeed theorem 3.1 ensures that increasing the dimension helps reduce the impact of outliers in any tensor. Consequently, by adding zeros to the weight tensors, we also improve the effectiveness of quantization. The intuition behind it is that by adding more dimensions in our tensors we create more space to store information and especially outliers which will be sliced in more parts and recovered better after quantization. This process increases the model size and computational cost, necessitating a trade-off to achieve better accuracy without a significant increase in computational requirements.

Since we only expand the input and output dimensions of the attention block and Multi-Layer Perceptron (MLP), there is no additional computational cost at inference. The new weights are stored, and the Hadamard matrices required for inference remain unchanged, allowing them to be efficiently computed using the FHT.

Lemma 4.1 shows the threshold after which the increase in dimensionality is worse than just quantizing with one more bit. For example with a LLaMA3-8B which has embeddings in 4096 dimensions we are only allowed to increase to $d = 1366$ dimensions in 3 bits before reaching the computational cost in 4 bits.

# 5 Experiments

## 5.1 Setup

We conduct our experiment based on the code of QuaRot which performs per-token quantization for activations and GPTQ for weights. We also quantize KV caches using asymmetric quantization with a group size of 128. We compare our results on several metrics: perplexity (PPL) on WikiText2, and 6 benchmarks: PIQA, hellaswag (HS), arc-easy (ARC-E), arc-challenge (ARC-C), winogrande (WINO) and lambada, we also compute the average value (AVG) of these 6 benchmarks. We performs our experiments in 4 and 3 bits quantization on 6 different models from the Mistral library, LLaMA architecture and Qwen. We used only one GPU A100 to perform quantization and Gradual Binary Search (GBS) with 10% of the train set of WikiText2 for 4 days for the biggest models.

## 5.2 Results

### 5.2.1 Gradual Binary Search performances

Table 1 and Table 2 shows the results in 4 and 3 bits quantization on the perplexity and 6 benchmarks. In 4 bits our method GBS clearly outperforms previous methods for all models improving up to almost 6% for LLaMA3-8B, 5% on Qwen2.5 1.5B Instruct, 4% on Mistral 7B and 3% on Mistral 7B Instruct.

In 3 bits GBS made activation quantization possible with an increase of accuracy reaching 40% for Mistral 7B (Table 2). All other models have been greatly affected by GBS reducing the gap with 4 bits quantization. PPL is also significantly impacted by GBS reducing by a factor of 100 in the case of LLaMA3-8B. We now have a method reaching decent performances in 3 bits like with Mistral 7B Instruct which is only 10% less than FP16 and reach 61.32% accuracy on our benchmarks.

GBS appears to be highly effective in enhancing quantization performance, supporting our hypothesis that optimizing Perplexity via binary search is preferable to minimizing quantization error. We assumed a single minimum and a convex function, allowing us to leverage binary search while relying on the smoothness of CrossEntropy—an assumption that appears to hold true. Perplexity emerges as a strong objective for guiding our optimization, as it correlates well with improved benchmark performance (see Appendix D for more details).

We also evaluated GBS using two additional methods: SpinQuant [19] and DFRot [28], both relying on rotation matrices (see Appendix E). Our binary search approach, particularly when restricted to 3 bits, significantly enhances their performance, thus validating the broad effectiveness of our method
<table><caption>Table 1: Results in 4 bits WAKV quantization on perplexity (PPL), PIQA, hellaswag (HS), arc-easy (ARC-E), arc-challenge (ARC-C), winogrande (WINO) and lambada, we also compute the average value (AVG) which represents a % of success. We compare our method, GBS, with QuaRot (where QuaRot+ indicates the use of dimension expansion) and clearly observe that GBS outperforms QuaRot across all computed metrics. Additionally, dimension expansion enables QuaRot to be compatible with Qwen's family of models.</caption><thead><tr><th>Model</th><th>Method</th><th>PPL↓</th><th>PIQA</th><th>HS</th><th>ARC-E</th><th>ARC-C</th><th>Wino</th><th>Lambada</th><th>AVG↑</th></tr></thead><tbody><tr><td rowspan="3">Mistral 7B Inst v0.3</td><td>FP16</td><td>5.49</td><td>71.27</td><td>74.6</td><td>67.94</td><td>74.27</td><td>58.96</td><td>82.66</td><td>71.62</td></tr><tr><td>QuaRot</td><td>5.98</td><td>67.7</td><td>71.45</td><td>63.94</td><td>69.53</td><td>55.2</td><td>79.46</td><td>67.88</td></tr><tr><td>QuaRot + GBS</td><td><strong>5.75</strong></td><td><strong>70.55</strong></td><td><strong>74.44</strong></td><td><strong>66.66</strong></td><td><strong>71.82</strong></td><td><strong>56.66</strong></td><td><strong>80.77</strong></td><td><strong>70.15</strong></td></tr><tr><td rowspan="3">Mistral 7B v0.1</td><td>FP16</td><td>5.25</td><td>72.49</td><td>75.59</td><td>69.4</td><td>73.95</td><td>54.86</td><td>80.18</td><td>71.08</td></tr><tr><td>QuaRot</td><td>5.82</td><td>67.62</td><td>71.88</td><td>63.36</td><td>70.01</td><td>48.98</td><td>76.6</td><td>66.41</td></tr><tr><td>QuaRot + GBS</td><td><strong>5.57</strong></td><td><strong>71.47</strong></td><td><strong>74.95</strong></td><td><strong>68</strong></td><td><strong>72.22</strong></td><td><strong>51.54</strong></td><td><strong>79.21</strong></td><td><strong>69.56</strong></td></tr><tr><td rowspan="3">Llama2 7B</td><td>FP16</td><td>5.47</td><td>71.08</td><td>73.9</td><td>68.25</td><td>68.98</td><td>46.33</td><td>74.58</td><td>67.19</td></tr><tr><td>QuaRot</td><td>6.21</td><td>64.65</td><td>69.09</td><td>60.22</td><td>64.64</td><td><strong>43.17</strong></td><td>69.78</td><td>61.92</td></tr><tr><td>QuaRot + GBS</td><td><strong>6.04</strong></td><td><strong>65.64</strong></td><td><strong>69.88</strong></td><td><strong>61.4</strong></td><td><strong>66.46</strong></td><td>42.32</td><td><strong>70.75</strong></td><td><strong>62.74</strong></td></tr><tr><td rowspan="3">Llama3 8B</td><td>FP16</td><td>6.13</td><td>72.62</td><td>76.01</td><td>69.22</td><td>72.93</td><td>53.41</td><td>77.69</td><td>70.3</td></tr><tr><td>QuaRot</td><td>8.33</td><td>61.66</td><td>66.27</td><td>57.05</td><td>64.72</td><td>42.06</td><td>68.06</td><td>59.97</td></tr><tr><td>QuaRot + GBS</td><td><strong>7.4</strong></td><td><strong>67.87</strong></td><td><strong>72.02</strong></td><td><strong>63.73</strong></td><td><strong>71.03</strong></td><td><strong>45.9</strong></td><td><strong>73.7</strong></td><td><strong>65.71</strong></td></tr><tr><td rowspan="3">Qwen2.5 7B Inst</td><td>FP16</td><td>7.45</td><td>66.23</td><td>69.73</td><td>62.74</td><td>70.56</td><td>55.12</td><td>81.02</td><td>67.57</td></tr><tr><td>QuaRot</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>QuaRot<sup>+</sup></td><td>9.21</td><td>56.66</td><td>59.31</td><td>54.01</td><td>63.54</td><td>48.89</td><td>69.78</td><td>58.7</td></tr><tr><td rowspan="3">Qwen2.5 1.5B Inst</td><td>QuaRot<sup>+</sup> + GBS</td><td><strong>8.23</strong></td><td><strong>62.58</strong></td><td><strong>64.91</strong></td><td><strong>60.24</strong></td><td><strong>66.61</strong></td><td><strong>49.4</strong></td><td><strong>72.39</strong></td><td><strong>62.69</strong></td></tr><tr><td>FP16</td><td>9.64</td><td>58.09</td><td>61.21</td><td>54.98</td><td>63.3</td><td>46.59</td><td>75.8</td><td>60.0</td></tr><tr><td>QuaRot<sup>+</sup></td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td></td><td>QuaRot<sup>+</sup> + GBS</td><td><strong>12.05</strong></td><td><strong>43.94</strong></td><td><strong>45.24</strong></td><td><strong>42.64</strong></td><td><strong>58.64</strong></td><td><strong>39.33</strong></td><td><strong>65.61</strong></td><td><strong>49.23</strong></td></tr></tbody></table>

<figure><img src="image_4.png" /><figcaption>Figure 2: Effect of expanding dimensions on 6 benchmarks average (AVG) for different models in 3 bits WAKV quantization and the computational limit of Lemma 4.1. Due to memory constraints on GPU A100 we could not increase more than 2036 dimensions for LLaMA3-8B.</figcaption></figure>

### 5.2.2 Matrix expansion effect

To execute QuaRot on Qwen2.5 1.5B, as shown in Tables 1 and 2, we needed to increase the embedding dimension (as detailed in Section 4.2) to a value that can generate a Hadamard matrix. Initially, 1536 was not suitable since it is neither a power of 2 nor divisible by a known dimensions like 172, 156, or 140. We first chose to add 8 dimensions, reaching 1542, which can be managed by the Paley algorithm without excessive computational costs. This algorithm is also used for Qwen2.5 7B to generate a Hadamard matrix of dimension 3584 and expand MLP to 32 dimensions, enabling the Qwen architecture to work with QuaRot. This process is applicable to any architecture and any embedding dimension without increasing computational costs making this method very general.

We now study the impact of expanding dimensions on performance. Figure 2 shows the evolution of AVG with the number of dimensions added to our tokens and we clearly see the positive impact
<table><caption>Table 2: Results in 3 bits WAKV quantization on perplexity (PPL), PIQA, hellaswag (HS), arc-easy (ARC-E), arc-challenge (ARC-C), winogrande (WINO) and lambada, we also compute the average value (AVG) which represents a % of success. We compare our method, GBS, with QuaRot (where QuaRot+ indicates the use of dimension expansion) and clearly observe that GBS outperforms QuaRot across all computed metrics. Additionally, dimension expansion enables QuaRot to be compatible with Qwen's family of models.</caption><thead><tr><th>Model</th><th>Method</th><th>PPL↓</th><th>PIQA</th><th>HS</th><th>ARC-E</th><th>ARC-C</th><th>Wino</th><th>Lambada</th><th>AVG↑</th></tr></thead><tbody><tr><td rowspan="3">Mistral 7B Inst v0.3</td><td>FP16</td><td>5.49</td><td>71.27</td><td>74.6</td><td>67.94</td><td>74.27</td><td>58.96</td><td>82.66</td><td>71.62</td></tr><tr><td>QuaRot</td><td>38.28</td><td>7.66</td><td>9.49</td><td>5.82</td><td>51.46</td><td>23.55</td><td>34.39</td><td>22.06</td></tr><tr><td>QuaRot + GBS</td><td><strong>7.04</strong></td><td><strong>62.17</strong></td><td><strong>66.93</strong></td><td><strong>57.4</strong></td><td><strong>61.56</strong></td><td><strong>46.42</strong></td><td><strong>73.44</strong></td><td><strong>61.32</strong></td></tr><tr><td rowspan="3">Mistral 7B v0.1</td><td>FP16</td><td>5.25</td><td>72.49</td><td>75.59</td><td>69.4</td><td>73.95</td><td>54.86</td><td>80.18</td><td>71.08</td></tr><tr><td>QuaRot</td><td>100.85</td><td>3.07</td><td>4.13</td><td>2.0</td><td>48.62</td><td>22.18</td><td>30.6</td><td>18.43</td></tr><tr><td>QuaRot + GBS</td><td><strong>7.31</strong></td><td><strong>59.22</strong></td><td><strong>64.41</strong></td><td><strong>54.03</strong></td><td><strong>63.3</strong></td><td><strong>40.53</strong></td><td><strong>68.39</strong></td><td><strong>58.31</strong></td></tr><tr><td rowspan="3">Llama2 7B</td><td>FP16</td><td>5.47</td><td>71.08</td><td>73.9</td><td>68.25</td><td>68.98</td><td>46.33</td><td>74.58</td><td>67.19</td></tr><tr><td>QuaRot</td><td>332.56</td><td>0.25</td><td>0.47</td><td>0.04</td><td>51.14</td><td>26.11</td><td>30.39</td><td>18.07</td></tr><tr><td>QuaRot + GBS</td><td><strong>9.18</strong></td><td><strong>39.03</strong></td><td><strong>49.91</strong></td><td><strong>28.14</strong></td><td><strong>56.12</strong></td><td><strong>31.91</strong></td><td><strong>54.92</strong></td><td><strong>43.34</strong></td></tr><tr><td rowspan="3">Llama3 8B</td><td>FP16</td><td>6.13</td><td>72.62</td><td>76.01</td><td>69.22</td><td>72.93</td><td>53.41</td><td>77.69</td><td>70.3</td></tr><tr><td>QuaRot</td><td>1315</td><td>0.05</td><td>0.08</td><td>0.02</td><td>49.41</td><td>23.72</td><td>27.78</td><td>16.84</td></tr><tr><td>QuaRot + GBS</td><td><strong>12.62</strong></td><td><strong>44.92</strong></td><td><strong>50.32</strong></td><td><strong>39.51</strong></td><td><strong>60.22</strong></td><td><strong>32.85</strong></td><td><strong>53.7</strong></td><td><strong>46.92</strong></td></tr><tr><td rowspan="4">Qwen2.5 7B Inst</td><td>FP16</td><td>7.45</td><td>66.23</td><td>69.73</td><td>62.74</td><td>70.56</td><td>55.12</td><td>81.02</td><td>67.57</td></tr><tr><td>QuaRot</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>QuaRot<sup>+</sup></td><td>251</td><td>1.14</td><td>1.14</td><td>1.14</td><td>49.33</td><td>25.0</td><td>32.15</td><td>18.32</td></tr><tr><td>QuaRot<sup>+</sup> + GBS</td><td><strong>12.33</strong></td><td><strong>41.9</strong></td><td><strong>42.62</strong></td><td><strong>41.18</strong></td><td><strong>56.59</strong></td><td><strong>40.53</strong></td><td><strong>61.83</strong></td><td><strong>47.44</strong></td></tr><tr><td rowspan="4">Qwen2.5 1.5B Inst</td><td>FP16</td><td>9.64</td><td>58.09</td><td>61.21</td><td>54.98</td><td>63.3</td><td>46.59</td><td>75.8</td><td>60.0</td></tr><tr><td>QuaRot</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>QuaRot<sup>+</sup></td><td>3411</td><td>0.06</td><td>0.12</td><td>0.0</td><td>49.72</td><td><strong>23.98</strong></td><td>27.99</td><td>16.98</td></tr><tr><td>QuaRot<sup>+</sup> + GBS</td><td><strong>34.97</strong></td><td><strong>13.84</strong></td><td><strong>14.81</strong></td><td><strong>12.87</strong></td><td><strong>52.17</strong></td><td>23.72</td><td><strong>38.89</strong></td><td><strong>26.05</strong></td></tr></tbody></table>

on performances. We can reach 68.95% of accuracy for Mistral-7B Instruct but at a very high computational cost.

Another beneficial aspect of dimension expansion is seen in Group Local Rotation, introduced in QuaRot and explored in [16]. This technique involves decomposing a tensor into smaller sub-tensors and applying the same small power-of-2 Hadamard matrix to each of these sub-tensors. This approach leverages efficient Hadamard transforms (as introduced in Section 2.3.2) and significantly speeds up inference. Particularly for MLP layers that often operate in high-dimensional spaces, expanding dimensions can help identify a more suitable divisor, resulting in efficient power-of-2 sub-tensors.

# 6 Conclusion

In this work, we introduced an approach to optimize the quantization of LLMs using Gradual Binary Search and Hadamard matrices. Our method achieves efficient 3-bit quantization for weights, activations, and key-value caches, significantly improving model performance. We also theoretically demonstrated that Hadamard matrices are more effective than random rotation matrices in reducing extreme values in activations.

We also extended the use of rotation matrices to support non-power-of-2 embedding dimensions using the Paley algorithm and dimension expansion. This generalization allows our method to be applied to various architectures, including those with unique embedding dimensions. Experimental results on models from the Mistral library, LLaMA architecture, and Qwen show the effectiveness of our approach, outperforming existing methods.

Overall, our findings suggest that GBS and Hadamard matrices have great potential for advancing LLM quantization, making them more suitable for resource-constrained devices. Future work will explore mix computation and combining GBS with other methods.
# 7 Limitations

As explained in the previous part expanding dimensions has a big computational cost and it worsen with context length that is why we need to be aware of the expanding limit. One potential solution is to implement a Mixed Computation pipeline, where dimensions are only expanded in specific layers based on the presence of outliers, thereby substantially reducing computational overhead.

Another challenge arises with GBS, which involves computing perplexity at each step—a process that can be time-consuming for PTQ methods, sometimes taking several days. To mitigate this, we could use less than 10% of WikiText2 which might be excessive and unnecessary.
References

[1] Saleh Ashkboos, Maximilian L. Croci, Marcelo Gennari do Nascimento, Torsten Hoefler, and James Hensman. SliceGPT: Compress Large Language Models by Deleting Rows and Columns, February 2024. URL http://arxiv.org/abs/2401.15024. arXiv:2401.15024.

[2] Saleh Ashkboos, Amirkeivan Mohtashami, Maximilian L. Croci, Bo Li, Pashmina Cameron, Martin Jaggi, Dan Alistarh, Torsten Hoefler, and James Hensman. QuaRot: Outlier-Free 4-Bit Inference in Rotated LLMs, October 2024. URL http://arxiv.org/abs/2404.00456. arXiv:2404.00456 [cs].

[3] Jerry Chee, Volodymyr Kuleshov, and Yaohui Cai. QuIP: 2-Bit Quantization of Large Language Models With Guarantees.

[4] Mengzhao Chen, Yi Liu, Jiahao Wang, Yi Bin, Wenqi Shao, and Ping Luo. PrefixQuant: Static Quantization Beats Dynamic through Prefixed Outliers in LLMs, October 2024. URL http://arxiv.org/abs/2410.05265. arXiv:2410.05265.

[5] Jungwook Choi, Zhuo Wang, Swagath Venkataramani, Pierce I.-Jen Chuang, Vijayalakshmi Srinivasan, and Kailash Gopalakrishnan. PACT: Parameterized Clipping Activation for Quantized Neural Networks, July 2018. URL http://arxiv.org/abs/1805.06085. arXiv:1805.06085 [cs].

[6] Laurens De Haan and Ana Ferreira. *Extreme Value Theory*. Springer Series in Operations Research and Financial Engineering. Springer, New York, NY, 2006. ISBN 978-0-387-23946-0 978-0-387-34471-3. doi: 10.1007/0-387-34471-3. URL http://link.springer.com/10.1007/0-387-34471-3.

[7] Tim Dettmers, Mike Lewis, Younes Belkada, and Luke Zettlemoyer. LLM.int8(): 8-bit Matrix Multiplication for Transformers at Scale.

[8] Alexandre Défossez, Yossi Adi, and Gabriel Synnaeve. Differentiable Model Compression via Pseudo Quantization Noise, October 2022. URL http://arxiv.org/abs/2104.09987. arXiv:2104.09987 [cs, stat].

[9] Steven K. Esser, Jeffrey L. McKinstry, Deepika Bablani, Rathinakumar Appuswamy, and Dharmendra S. Modha. Learned Step Size Quantization, May 2020. URL http://arxiv.org/abs/1902.08153. arXiv:1902.08153 [cs, stat].

[10] Giuseppe Franco, Pablo Monteagudo-Lago, Ian Colbert, Nicholas Fraser, and Michaela Blott. Improving Quantization with Post-Training Model Expansion, March 2025. URL http://arxiv.org/abs/2503.17513. arXiv:2503.17513 [cs].

[11] Elias Frantar, Saleh Ashkboos, Torsten Hoefler, and Dan Alistarh. GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers, March 2023. URL http://arxiv.org/abs/2210.17323. arXiv:2210.17323 [cs].

[12] Amir Gholami, Sehoon Kim, Zhen Dong, Zhewei Yao, Michael W. Mahoney, and Kurt Keutzer. A Survey of Quantization Methods for Efficient Neural Network Inference, June 2021. URL http://arxiv.org/abs/2103.13630. arXiv:2103.13630 [cs].

[13] Yunhui Guo. A Survey on Methods and Theories of Quantized Neural Networks, December 2018. URL http://arxiv.org/abs/1808.04752. arXiv:1808.04752 [cs, stat].

[14] K. J. Horadam. *Hadamard Matrices and Their Applications*. Princeton University Press, January 2012. ISBN 978-1-4008-4290-2. Google-Books-ID: oR_HDgAAQBAJ.

[15] Xijie Huang, Zechun Liu, Shih-Yang Liu, and Kwang-Ting Cheng. RoLoRA: Fine-tuning Rotated Outlier-free LLMs for Effective Weight-Activation Quantization, July 2024. URL http://arxiv.org/abs/2407.08044. arXiv:2407.08044 [cs].
[16] Sangjin Kim, Yuseon Choi, Jungjun Oh, Byeongcheol Kim, and Hoi-Jun Yoo. LightRot: A Light-weighted Rotation Scheme and Architecture for Accurate Low-bit Large Language Model Inference. *IEEE Journal on Emerging and Selected Topics in Circuits and Systems*, pages 1–1, 2025. ISSN 2156-3365. doi: 10.1109/JETCAS.2025.3558300. URL https://ieeexplore.ieee.org/document/10950449/.

[17] Haokun Lin, Haobo Xu, Yichen Wu, Jingzhi Cui, Yingtao Zhang, Linzhan Mou, Linqi Song, Zhenan Sun, and Ying Wei. DuQuant: Distributing Outliers via Dual Transformation Makes Stronger Quantized LLMs.

[18] Ji Lin, Chuang Gan, and Song Han. Defensive Quantization: When Efficiency Meets Robustness, April 2019. URL http://arxiv.org/abs/1904.08444. arXiv:1904.08444 [cs, stat].

[19] Zechun Liu, Changsheng Zhao, Igor Fedorov, Bilge Soran, Dhruv Choudhary, Raghuraman Krishnamoorthi, Vikas Chandra, Yuandong Tian, and Tijmen Blankevoort. SpinQuant: LLM quantization with learned rotations, May 2024. URL http://arxiv.org/abs/2405.16406. arXiv:2405.16406 [cs].

[20] Shuming Ma, Hongyu Wang, Lingxiao Ma, Lei Wang, Wenhui Wang, Shaohan Huang, Li Dong, Ruiping Wang, Jilong Xue, and Furu Wei. The Era of 1-bit LLMs: All Large Language Models are in 1.58 Bits, February 2024. URL http://arxiv.org/abs/2402.17764. arXiv:2402.17764 [cs].

[21] Lucas Maisonnave, Cyril Moineau, Olivier Bichler, and Fabrice Rastello. Applying maximum entropy principle on quantized neural networks correlates with high accuracy.

[22] Lucas Maisonnave, Cyril Moineau, Olivier Bichler, and Fabrice Rastello. Precision Where It Matters: A Novel Spike Aware Mixed-Precision Quantization Strategy for LLaMA-based Language Models, April 2025. URL http://arxiv.org/abs/2504.21553. arXiv:2504.21553 [cs].

[23] Aniruddha Nrusimha, Mayank Mishra, Naigang Wang, Dan Alistarh, Rameswar Panda, and Yoon Kim. Mitigating the Impact of Outlier Channels for Language Model Quantization with Activation Regularization, April 2024. URL http://arxiv.org/abs/2404.03605. arXiv:2404.03605 [cs] version: 1.

[24] Seungwoo Son, Wonpyo Park, Woohyun Han, Kyuyeun Kim, and Jaeho Lee. Prefixing Attention Sinks can Mitigate Activation Outliers for Large Language Model Quantization. June 2024. URL https://www.semanticscholar.org/paper/1601ad7616681ed9d7e1b9a04b64c1ad9c7196c7.

[25] Roman Vershynin. *High-Dimensional Probability: An Introduction with Applications in Data Science*. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2018. ISBN 978-1-108-41519-4. doi: 10.1017/9781108231596. URL https://www.cambridge.org/core/books/highdimensional-probability/797C466DA29743D2C8213493BD2D2102.

[26] Hongyu Wang, Shuming Ma, Li Dong, Shaohan Huang, Huaijie Wang, Lingxiao Ma, Fan Yang, Ruiping Wang, Yi Wu, and Furu Wei. BitNet: Scaling 1-bit Transformers for Large Language Models, October 2023. URL http://arxiv.org/abs/2310.11453. arXiv:2310.11453 [cs].

[27] Xiuying Wei, Yunchen Zhang, Yuhang Li, Xiangguo Zhang, Ruihao Gong, Jinyang Guo, and Xianglong Liu. Outlier Suppression+: Accurate quantization of large language models by equivalent and optimal shifting and scaling, October 2023. URL http://arxiv.org/abs/2304.09145. arXiv:2304.09145 [cs].

[28] Jingyang Xiang and Sai Qian Zhang. DFRot: Achieving Outlier-Free and Massive Activation-Free for Rotated LLMs with Refined Rotation, December 2024. URL http://arxiv.org/abs/2412.00648. arXiv:2412.00648 [cs].

[29] Guangxuan Xiao, Ji Lin, Mickael Seznec, Hao Wu, Julien Demouth, and Song Han. SmoothQuant: Accurate and Efficient Post-Training Quantization for Large Language Models. In *Proceedings of the 40th International Conference on Machine Learning*, pages 38087–38099.
PMLR, July 2023. URL https://proceedings.mlr.press/v202/xiao23c.html. ISSN: 2640-3498.

[30] Dawei Yang, Ning He, Xing Hu, Zhihang Yuan, Jiangyong Yu, Chen Xu, and Zhe Jiang. Post-Training Quantization for Re-parameterization via Coarse & Fine Weight Splitting, December 2023. URL http://arxiv.org/abs/2312.10588. arXiv:2312.10588 [cs].

[31] Linjie Yang and Qing Jin. FracBits: Mixed Precision Quantization via Fractional Bit-Widths. Proceedings of the AAAI Conference on Artificial Intelligence, 35(12):10612–10620, May 2021. ISSN 2374-3468, 2159-5399. doi: 10.1609/aaai.v35i12.17269. URL https://ojs.aaai.org/index.php/AAAI/article/view/17269.

[32] Chenzhuo Zhu, Song Han, Huizi Mao, and William J. Dally. Trained Ternary Quantization, February 2017. URL http://arxiv.org/abs/1612.01064. arXiv:1612.01064 [cs].

# A Theoretical proofs

## A.1 Hadamard matrices

### A.1.1 Proof

*Proof of Lemma 3.1.* We define a Hadamard matrix as a rotation matrix with values equal to 1 or -1 only. By definition, the equality $HH^T = I_n$ must be respected, but without normalization, we have $HH^T = nI_n$. If we decide to normalize this Hadamard matrix by a factor of $\frac{1}{\sqrt{n}}$, we obtain the identity by multiplying it by its transpose. In the case of a vector $x = (c, \epsilon, ..., \epsilon)^T$ with $c \gg \epsilon$, applying a Hadamard matrix to it amounts to multiplying the maximum absolute value by $\frac{1}{\sqrt{n}}$ since all the values of $H$ are either $\frac{1}{\sqrt{n}}$ or $-\frac{1}{\sqrt{n}}$, hence the desired result. □

*Proof of Lemma 3.2.* Let $Q$ be a rotation matrix drawn on the unit sphere $S^{n-1}$. We assume that the problem is in high dimension, which allows us to approximate the distribution of the elements of the matrix $Q$:

$$Q_{ij} \sim \mathcal{N}\left(0, \frac{1}{n}\right)$$

This theorem is a classic result of high-dimensional probability theory [25]. It is this result that allows the entire demonstration, because it is from this approximation that we can use the fundamental properties of the extreme values of a normal law. Indeed, for all $i, j \le n$, $Z_{ij} \sim \mathcal{N}(0, 1)$, then $Q_{ij} = \frac{Z_{ij}}{\sqrt{n}}$. We can show [6] that

$$\mathbb{E}\left[\max_{1 \le i, j \le n} |Z_{ij}|\right] = \sqrt{2 \log n} \quad (3)$$

Therefore,

$$\mathbb{E}\left[\max_{1 \le i, j \le n} |Q_{ij}|\right] = \sqrt{\frac{2 \log n}{n}} \quad (4)$$

Using Talagrand's inequality for a Lipschitz function ($Qx$ is indeed a Lipschitz function) we have:

$$\mathbb{P}\left(\left|\max_{1 \le i, j \le n} |Q_{ij}| - \sqrt{\frac{2 \log n}{n}}\right| > \epsilon\right) \le 2e^{-Cn\epsilon^2} \quad (5)$$

With $C > 0$. Thus, for sufficiently large $n$, we have a very high probability of having:

$$\max_{1 \le i, j \le n} |Q_{ij}| = \sqrt{\frac{2 \log n}{n}} \quad (6)$$

We now use this result when applying $Q$ to a vector $x = (c, \epsilon, ..., \epsilon)^T$ with $c \gg \epsilon$

$$\max_{1 \le i \le n} |(Qx)_i| = c \max_{1 \le i, j \le n} |Q_{ij}| = c \sqrt{\frac{2 \log n}{n}} \quad \square$$
Finally, using Lemmas 3.1 and 3.2, we show that for sufficiently large $n$

$$ \max_{1 \le i \le n} |(Hx)_i| \le \max_{1 \le i \le n} |(Qx)_i| $$

We even show that we cannot do better than the Hadamard matrix to redistribute the energy of a matrix.

*Proof of Theorem 3.2.* Let $Q \in \mathbb{R}^{n \times n}$ be an orthogonal matrix. By definition, for any column $i$ of this matrix:

$$ ||Q_i||_2 = 1 \Rightarrow \sum_j |Q_{i,j}|^2 = 1 $$

However,

$$ \sum_j \max_{p,k} |Q_{p,k}|^2 \ge \sum_j |Q_{i,j}|^2 \qquad (7) $$

$$ \Rightarrow \sum_j \max_{p,k} |Q_{p,k}|^2 \ge 1 \qquad (8) $$

$$ \Rightarrow n \max_{p,k} |Q_{p,k}|^2 \ge 1 \qquad (9) $$

$$ \Rightarrow \max_{p,k} |Q_{p,k}| \ge \frac{1}{\sqrt{n}} \qquad (10) $$

We have just shown that an orthogonal matrix cannot reduce an outlier by more than a factor of $\frac{1}{\sqrt{n}}$, and as seen with Lemma 3.1, a Hadamard matrix can reach this bound, it is therefore optimal. □

### A.1.2 Experimental Verifications

<figure><img src="image_5.png" /><figcaption>Figure 3: Maximum absolute value as a function of dimension for a randomly drawn rotation matrix and a Hadamard matrix applied to a vector containing a peak at 200 obtained experimentally (blue) and theoretically (red)</figcaption></figure>

To verify the previous theoretical results, we set up a simple experiment where we apply a randomly drawn rotation matrix and a Hadamard matrix to a vector of dimension $n$ following a standard normal distribution with a standard deviation of 0.1 to which we add a peak at 200. We plot the curve of the maximum absolute value after applying our matrices as a function of the dimension $n$ as well as the theoretical curve in Figure 3.

It clearly shows that the theoretical and experimental curves follow each other perfectly, which seems to confirm the previously demonstrated theorems. Hadamard matrices are therefore theoretically and experimentally the most suitable matrices for reducing the impact of an outlier in a vector.
## A.2 Increasing dimensions

*Proof of Lemma 4.1.* We define BitOps as the function that compute the number of operations for a matrix multiplication: $\text{BitOps}(AB) = mn^2pb^2$. And we want to find a condition that ensure

$$ \text{BitOps}(A'B') \leq \text{BitOps}(AB) \qquad (11) $$

$$ \Rightarrow m(n+d)^2pb'^2 \leq mn^2pb^2 \qquad (12) $$

$$ \Rightarrow (n+d)^2b'^2 \leq n^2b^2 \qquad (13) $$

$$ \Rightarrow (n+d)b' \leq nb \qquad (14) $$

$$ \Rightarrow nb' + db' \leq nb \qquad (15) $$

$$ \Rightarrow d \leq \frac{n(b-b')}{b'} \qquad (16) $$

□

## B Paley Algorithm

**Algorithm 2** Hadamard Matrix Construction using the Paley Method

**Require:** A prime number $p$

**Ensure:** A Hadamard matrix $H$ of order $p+1$

1: $n \leftarrow p+1$ ▷ Determine the order of the matrix

2: Initialize $H$ as a $n \times n$ matrix with all entries set to 1 ▷ Start with a matrix of all ones

3: **for** $i \leftarrow 1$ to $n-1$ **do** ▷ Loop over rows (except the first row)

4: $H[i, 0] \leftarrow -1$ ▷ Set the first column entry to -1 for current row

5: $H[0, i] \leftarrow -1$ ▷ Set the first row entry to -1 for current column

6: **for** $j \leftarrow 1$ to $n-1$ **do** ▷ Loop over columns (except the first column)

7: **if** $i = j$ **then**

8: $H[i, j] \leftarrow -1$ ▷ Set diagonal entries to -1

9: **else**

10: $H[i, j] \leftarrow \text{legendre\_symbol}((i-1)-(j-1), p)$

11: **end if**

12: **end for**

13: **end for**

14: **return** $H$ ▷ Return the constructed Hadamard matrix

## C Gradual Binary Search process

In this analysis, we examine the evolution of clipping ratios through GBS to better understand the dynamics of these parameters in LLMs. Figure 4 illustrates the perplexity (PPL) evolution during the optimization of a LLaMA3-8B model quantized to 4 bits. The graph displays the various tested values for each projection, optimized under two different configurations: starting the model in FP16 (blue line) and initiating the process in 4 bits. It is clear that starting in FP16 yields a better PPL on the training set of WikiText2, achieving 7.62, compared to starting in 4 bits, which results in a PPL of 7.94. On the test set we have the same dynamic with a PPL of 7.4 starting in FP16 and 7.69 starting in 4 bits.

Figure 5 illustrates the final configuration achieved by GBS for the same architecture, starting the process in both FP16 and 4-bit precision. It is clear that initiating in 4 bits results in a significantly more unstable configuration compared to starting in FP16. Many values remain at 1, and there is a high variance, indicating that the algorithm struggles to find a stable configuration when the entire model is in 4 bits. It also appears to have difficulty understanding the impact of small changes in the clipping ratio.

In contrast, starting in FP16 results in a stable configuration for every projection, with distinct dynamics. For instance, the qk_rotate projection exhibits minimal changes in the clipping ratio, with most layers close to 1. Conversely, the o Project has values below 0.3, suggesting
<figure><img src="image_6.png" /><figcaption>Figure 4: PPL vs Layer during Gradual Binary Search on 10% of Train WikiText2 for a LLaMA3-8B in 4-bit quantization and rotated with QuaRot. For better visualization we set a maximum PPL to 9. Points opacity represents the clipping ratio, the value is closer to 0 as transparency increases</figcaption></figure>

that clipping to 30% of the maximum value can enhance performance. This figure underscores the importance of GBS in improving the model's quality by identifying the optimal clipping configuration, which is clearly not only ones.

<figure><img src="image_7.png" /><figcaption>Figure 5: Final configurations obtained with GBS started in 4 bits and in FP16 for a LLaMA3-8B</figcaption></figure>

## D Perplexity as objective

Perplexity is the central part of our optimization, it drives our search and it is supposed to reach a configuration which will perform better than all others with a bigger PPL. In figure 6 we can see how the average value on 6 benchmarks evolves with the perplexity. It clearly appears that a smaller PPL usually represents a better AVG.

<figure><img src="image_8.png" /><figcaption>Figure 6: AVG over Perplexity for all results obtained in Tab 2 and 1</figcaption></figure>
# E More results

## E.1 SpinQuant

<table><caption>Table 3: Results in 4 bits WAKV quantization on perplexity (PPL), PIQA, hellaswag (HS), arc-easy (ARC-E), arc-challenge (ARC-C), winogrande (WINO) and lambada, we also compute the average value (AVG) which represents a % of success. We compare our method, GBS, with SpinQuant and clearly observe that GBS outperforms SpinQuant across almost all computed metrics.</caption><thead><tr><th>Model</th><th>Method</th><th>PPL↓</th><th>PIQA</th><th>HS</th><th>ARC-E</th><th>ARC-C</th><th>Wino</th><th>Lambada</th><th>AVG↑</th></tr></thead><tbody><tr><td rowspan="3">Mistral 7B Inst v0.3</td><td>FP16</td><td>5.49</td><td>71.27</td><td>74.6</td><td>67.94</td><td>74.27</td><td>58.96</td><td>82.66</td><td>71.62</td></tr><tr><td>SpinQuant</td><td>5.88</td><td>69</td><td>72.66</td><td>65.34</td><td>69.93</td><td>55.12</td><td>78.41</td><td>68.41</td></tr><tr><td>SpinQuant + GBS</td><td><strong>5.83</strong></td><td><strong>69.01</strong></td><td><strong>72.66</strong></td><td><strong>65.36</strong></td><td><strong>72.14</strong></td><td><strong>56.91</strong></td><td><strong>79.5</strong></td><td><strong>69.26</strong></td></tr><tr><td rowspan="3">Mistral 7B v0.1</td><td>FP16</td><td>5.25</td><td>72.49</td><td>75.59</td><td>69.4</td><td>73.95</td><td>54.86</td><td>80.18</td><td>71.08</td></tr><tr><td>SpinQuant</td><td>5.71</td><td>69.55</td><td><strong>73.45</strong></td><td>65.65</td><td>69.38</td><td><strong>48.98</strong></td><td><strong>76.98</strong></td><td>67.33</td></tr><tr><td>SpinQuant + GBS</td><td><strong>5.62</strong></td><td><strong>70.02</strong></td><td>73.37</td><td><strong>66.66</strong></td><td><strong>71.19</strong></td><td>48.29</td><td>76.47</td><td><strong>67.67</strong></td></tr><tr><td rowspan="3">Llama2 7B</td><td>FP16</td><td>5.47</td><td>71.08</td><td>73.9</td><td>68.25</td><td>68.98</td><td>46.33</td><td>74.58</td><td>67.19</td></tr><tr><td>SpinQuant</td><td>6.57</td><td>61.73</td><td>68.46</td><td>55.0</td><td>63.46</td><td>40.61</td><td>67.63</td><td>59.48</td></tr><tr><td>SpinQuant + GBS</td><td><strong>6.15</strong></td><td><strong>63.24</strong></td><td><strong>69.01</strong></td><td><strong>57.46</strong></td><td><strong>65.04</strong></td><td><strong>41.04</strong></td><td><strong>68.43</strong></td><td><strong>60.7</strong></td></tr><tr><td rowspan="3">Llama3 8B</td><td>FP16</td><td>6.13</td><td>72.62</td><td>76.01</td><td>69.22</td><td>72.93</td><td>53.41</td><td>77.69</td><td>70.3</td></tr><tr><td>SpinQuant</td><td>7.97</td><td><strong>65.11</strong></td><td><strong>69.01</strong></td><td><strong>61.21</strong></td><td>66.61</td><td>45.22</td><td>72.52</td><td>63.28</td></tr><tr><td>SpinQuant + GBS</td><td><strong>7.69</strong></td><td>63.84</td><td>67.84</td><td>59.83</td><td><strong>70.4</strong></td><td><strong>47.35</strong></td><td><strong>73.36</strong></td><td><strong>63.77</strong></td></tr></tbody></table>

<table><caption>Table 4: Results in 3 bits WAKV quantization on perplexity (PPL), PIQA, hellaswag (HS), arc-easy (ARC-E), arc-challenge (ARC-C), winogrande (WINO) and lambada, we also compute the average value (AVG) which represents a % of success. We compare our method, GBS, with SpinQuant and clearly observe that GBS outperforms SpinQuant across almost all computed metrics.</caption><thead><tr><th>Model</th><th>Method</th><th>PPL↓</th><th>PIQA</th><th>HS</th><th>ARC-E</th><th>ARC-C</th><th>Wino</th><th>Lambada</th><th>AVG↑</th></tr></thead><tbody><tr><td rowspan="3">Mistral 7B Inst v0.3</td><td>FP16</td><td>5.49</td><td>71.27</td><td>74.6</td><td>67.94</td><td>74.27</td><td>58.96</td><td>82.66</td><td>71.62</td></tr><tr><td>SpinQuant</td><td>14.31</td><td>20.39</td><td>28.39</td><td>12.38</td><td>49.72</td><td>24.57</td><td>40.57</td><td>29.34</td></tr><tr><td>SpinQuant + GBS</td><td><strong>8.11</strong></td><td><strong>52.93</strong></td><td><strong>58.99</strong></td><td><strong>46.87</strong></td><td><strong>60.06</strong></td><td><strong>40.78</strong></td><td><strong>66.67</strong></td><td><strong>54.38</strong></td></tr><tr><td rowspan="3">Mistral 7B v0.1</td><td>FP16</td><td>5.25</td><td>72.49</td><td>75.59</td><td>69.4</td><td>73.95</td><td>54.86</td><td>80.18</td><td>71.08</td></tr><tr><td>SpinQuant</td><td>18.88</td><td>16.58</td><td>21.97</td><td>11.2</td><td>51.3</td><td>24.23</td><td>37.67</td><td>27.16</td></tr><tr><td>SpinQuant + GBS</td><td><strong>7.98</strong></td><td><strong>52.81</strong></td><td><strong>60.59</strong></td><td><strong>45.04</strong></td><td><strong>59.27</strong></td><td><strong>35.67</strong></td><td><strong>63.68</strong></td><td><strong>52.84</strong></td></tr><tr><td rowspan="3">Llama2 7B</td><td>FP16</td><td>5.47</td><td>71.08</td><td>73.9</td><td>68.25</td><td>68.98</td><td>46.33</td><td>74.58</td><td>67.19</td></tr><tr><td>SpinQuant</td><td>425.2</td><td>0.24</td><td>0.45</td><td>0.04</td><td><strong>51.46</strong></td><td>28.33</td><td>27.57</td><td>18.02</td></tr><tr><td>SpinQuant + GBS</td><td><strong>15.65</strong></td><td><strong>20.77</strong></td><td><strong>26.51</strong></td><td><strong>15.04</strong></td><td>50.67</td><td><strong>26.19</strong></td><td><strong>42.93</strong></td><td><strong>30.35</strong></td></tr><tr><td rowspan="3">Llama3 8B</td><td>FP16</td><td>6.13</td><td>72.62</td><td>76.01</td><td>69.22</td><td>72.93</td><td>53.41</td><td>77.69</td><td>70.3</td></tr><tr><td>SpinQuant</td><td>316.6</td><td>2.71</td><td>3.1</td><td>2.31</td><td>50.51</td><td>22.35</td><td>29.0</td><td>18.33</td></tr><tr><td>SpinQuant + GBS</td><td><strong>20.26</strong></td><td><strong>21.42</strong></td><td><strong>23.95</strong></td><td><strong>18.9</strong></td><td><strong>54.38</strong></td><td><strong>26.96</strong></td><td><strong>43.1</strong></td><td><strong>31.45</strong></td></tr></tbody></table>
## E.2 DFRot

<table><caption>Table 5: Results in 4 bits WAKV quantization on perplexity (PPL), PIQA, hellaswag (HS), arc-easy (ARC-E), arc-challenge (ARC-C), winogrande (WINO) and lambada, we also compute the average value (AVG) which represents a % of success. We compare our method, GBS, with DFRot and clearly observe that GBS outperforms DFRot across all computed metrics.</caption><thead><tr><th>Model</th><th>Method</th><th>PPL↓</th><th>PIQA</th><th>HS</th><th>ARC-E</th><th>ARC-C</th><th>Wino</th><th>Lambada</th><th>AVG↑</th></tr></thead><tbody><tr><td rowspan="3">Mistral 7B Inst v0.3</td><td>FP16</td><td>5.49</td><td>71.27</td><td>74.6</td><td>67.94</td><td>74.27</td><td>58.96</td><td>82.66</td><td>71.62</td></tr><tr><td>DFRot</td><td>5.94</td><td>68.11</td><td>79.43</td><td>68.5</td><td>72.42</td><td>64.58</td><td><strong>80.3</strong></td><td>72.22</td></tr><tr><td>DFRot + GBS</td><td><strong>5.81</strong></td><td><strong>71.35</strong></td><td><strong>81.23</strong></td><td><strong>69.3</strong></td><td><strong>73.18</strong></td><td><strong>65.42</strong></td><td>80.13</td><td><strong>73.43</strong></td></tr><tr><td rowspan="3">Mistral 7B v0.1</td><td>FP16</td><td>5.25</td><td>72.49</td><td>75.59</td><td>69.4</td><td>73.95</td><td>54.86</td><td>80.18</td><td>71.08</td></tr><tr><td>DFRot</td><td>5.75</td><td><strong>71.03</strong></td><td>78.94</td><td>69.83</td><td>74.03</td><td>65.63</td><td>78.28</td><td>72.96</td></tr><tr><td>DFRot + GBS</td><td><strong>5.62</strong></td><td>70.88</td><td><strong>80.9</strong></td><td><strong>70.93</strong></td><td><strong>75.0</strong></td><td><strong>66.85</strong></td><td><strong>78.85</strong></td><td><strong>73.9</strong></td></tr><tr><td rowspan="3">Llama2 7B</td><td>FP16</td><td>5.47</td><td>71.08</td><td>73.9</td><td>68.25</td><td>68.98</td><td>46.33</td><td>74.58</td><td>67.19</td></tr><tr><td>DFRot</td><td>6.23</td><td>65.04</td><td>76.66</td><td>65.75</td><td>69.47</td><td>62.02</td><td>72.61</td><td>68.59</td></tr><tr><td>DFRot + GBS</td><td><strong>6.05</strong></td><td><strong>65.67</strong></td><td><strong>77.75</strong></td><td><strong>66.41</strong></td><td><strong>69.63</strong></td><td><strong>63.19</strong></td><td><strong>72.74</strong></td><td><strong>69.23</strong></td></tr><tr><td rowspan="3">Llama3 8B</td><td>FP16</td><td>6.13</td><td>72.62</td><td>76.01</td><td>69.22</td><td>72.93</td><td>53.41</td><td>77.69</td><td>70.3</td></tr><tr><td>DFRot</td><td>7.95</td><td>68.11</td><td>76.01</td><td>64.92</td><td>68.5</td><td>61.34</td><td>74.17</td><td>68.84</td></tr><tr><td>DFRot + GBS</td><td><strong>7.56</strong></td><td><strong>72.53</strong></td><td><strong>76.82</strong></td><td><strong>66.35</strong></td><td><strong>69.53</strong></td><td><strong>63.17</strong></td><td><strong>75.0</strong></td><td><strong>70.57</strong></td></tr></tbody></table>

<table><caption>Table 6: Results in 3 bits WAKV quantization on perplexity (PPL), PIQA, hellaswag (HS), arc-easy (ARC-E), arc-challenge (ARC-C), winogrande (WINO) and lambada, we also compute the average value (AVG) which represents a % of success. We compare our method, GBS, with DFRot and clearly observe that GBS outperforms DFRot across all computed metrics.</caption><thead><tr><th>Model</th><th>Method</th><th>PPL↓</th><th>PIQA</th><th>HS</th><th>ARC-E</th><th>ARC-C</th><th>Wino</th><th>Lambada</th><th>AVG↑</th></tr></thead><tbody><tr><td rowspan="3">Mistral 7B Inst v0.3</td><td>FP16</td><td>5.49</td><td>71.27</td><td>74.6</td><td>67.94</td><td>74.27</td><td>58.96</td><td>82.66</td><td>71.62</td></tr><tr><td>DFRot</td><td>11.26</td><td>53.28</td><td>67.57</td><td>35.6</td><td>40.33</td><td>30.88</td><td>57.57</td><td>47.54</td></tr><tr><td>DFRot + GBS</td><td><strong>7.58</strong></td><td><strong>63.22</strong></td><td><strong>75.35</strong></td><td><strong>59.32</strong></td><td><strong>65.19</strong></td><td><strong>53.46</strong></td><td><strong>71.73</strong></td><td><strong>64.71</strong></td></tr><tr><td rowspan="3">Mistral 7B v0.1</td><td>FP16</td><td>5.25</td><td>72.49</td><td>75.59</td><td>69.4</td><td>73.95</td><td>54.86</td><td>80.18</td><td>71.08</td></tr><tr><td>DFRot</td><td>13.63</td><td>55.01</td><td>65.45</td><td>27.89</td><td>32.52</td><td>23.25</td><td>50.63</td><td>42.46</td></tr><tr><td>DFRot + GBS</td><td><strong>7.64</strong></td><td><strong>62.83</strong></td><td><strong>73.72</strong></td><td><strong>56.99</strong></td><td><strong>64.33</strong></td><td><strong>49.64</strong></td><td><strong>68.12</strong></td><td><strong>62.6</strong></td></tr><tr><td rowspan="3">Llama2 7B</td><td>FP16</td><td>5.47</td><td>71.08</td><td>73.9</td><td>68.25</td><td>68.98</td><td>46.33</td><td>74.58</td><td>67.19</td></tr><tr><td>DFRot</td><td>26.64</td><td>49.96</td><td>58.81</td><td>13.19</td><td>14.81</td><td>11.57</td><td>39.14</td><td>31.25</td></tr><tr><td>DFRot + GBS</td><td><strong>10.96</strong></td><td><strong>56.12</strong></td><td><strong>66.81</strong></td><td><strong>34.43</strong></td><td><strong>40.4</strong></td><td><strong>28.45</strong></td><td><strong>55.01</strong></td><td><strong>46.87</strong></td></tr><tr><td rowspan="3">Llama3 8B</td><td>FP16</td><td>6.13</td><td>72.62</td><td>76.01</td><td>69.22</td><td>72.93</td><td>53.41</td><td>77.69</td><td>70.3</td></tr><tr><td>DFRot</td><td>140.78</td><td>52.41</td><td>54.62</td><td>2.82</td><td>3.38</td><td>2.27</td><td>31.85</td><td>24.56</td></tr><tr><td>DFRot + GBS</td><td><strong>22.14</strong></td><td><strong>54.85</strong></td><td><strong>61.92</strong></td><td><strong>25.53</strong></td><td><strong>29.58</strong></td><td><strong>21.48</strong></td><td><strong>48.67</strong></td><td><strong>40.34</strong></td></tr></tbody></table>