QuaRot

Summary

• Activation quantization!
• Use rotation to remove outliers from the hidden state without changing the output.
• Computational invariance.
• Applied to hidden states (residual), activations of feed forward components, attention mechanism, and KV cache.
• 99% accuracy retain on 4-bit quantized Llama-2-70B.
• Lossless 6 & 8-bit without any calibration data using RTN.

Methodology

Background

Hadamard Transform

• Walsh-Hadamard matrix:

  $${\mathbf{H}}_2=\frac{1}{\sqrt{2}}\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]{\mathbf{H}}_n=\frac{1}{\sqrt{2}}\left[\begin{array}{cc}{\mathbf{H}}_{n-1}& {\mathbf{H}}_{n-1}\\ {\mathbf{H}}_{n-1}& -{\mathbf{H}}_{n-1}\end{array}\right]$$
  • The computation complexity of ${\mathbf{H}}_d\mathbf{x}$ is $O(d{\log }_2(d))$

• Randomized Hadamard matrix:

  $$\mathbf{s}\in {\left\{-1,1\right\}}^d\tilde{\mathbf{H}}=\mathbf{H}\cdot \text{Diag}\left(\mathbf{s}\right)$$
  • $\tilde{\mathbf{H}}$ is also orthogonal.

Incoherence Processing

• Introduced by QuiP.
• A weight matrix $\mathbf{W}\in {\mathbb{R}}^{m\times n}$ is $\mu$-incoherent if $$\max \left(\mathbf{W}\right)\le \mu \cdot \frac{{\Vert \mathbf{W}\Vert }_F}{\sqrt{mn}}$$
  • $\max$ is the element-wise max of the matrix.
    • Is this different from $\Vert \mathbf{W}{\Vert }_{\infty }$?
• A matrix that has high incoherence is hard to quantize: the largest element is an outlier relative to the magnitude of the average element.

Computational Invariance

$$\text{RMSNorm}(\mathbf{X})=\text{RMSNorm}(\mathbf{X}{\mathbf{Q}}^{\top })\mathbf{Q}$$

• No re-scaling happens in the RMSNorm block.
  • In practice, re-scaling is absorbed into the adjacent weight matrices first.

Method

Feed Forward Network (FFN)

• RMSNorm scales $\mathbf{\alpha }$ is absorbed into ${\mathbf{W}}_{\text{gate}}$ and ${\mathbf{W}}_{\text{up}}$: $${\mathbf{W}}_k\leftarrow {\mathbf{Q}}^{\top }\text{diag}(\mathbf{\alpha }){\mathbf{W}}_k$$
• An additional Hadamard transform is inserted before down projection to smooth out the outliers then apply online symmetric per-token quantization. The second half of that Hadamard transform is merged into down_proj.

Attention