Efficient AI · Quantization notes

Dealing with outliers via rotation

Rotate (or randomly project) a vector before quantization so that extreme coordinates are mixed across dimensions and clipping becomes unlikely.

Usual clipping setup

Consider a matrix $R$ and a given vector $x$.

Let $M$ be a clipped factor (threshold). If every coordinate satisfies $|x_i| \le M$, nothing is clipped.
If for some $i$ we have $|x_i| > M$, then $\Pr(\text{clip } x_i) = 1$.

This is the usual outlier / range-clipping setup.

Rotate first

Instead, map

\[ y = R x. \]

Take $R$ to be a random Gaussian / random projection matrix that is almost orthogonal (eigenvalues $1 \pm \varepsilon$).

Coordinates of $y$

Look at a single output coordinate:

\[ y_i = \vec{r}_i \cdot \vec{x} = \sum_j r_{ij}\, x_j, \]

with entries of the row behaving like $r_{ij} \approx \dfrac{1}{\sqrt{d}}\,\mathcal{N}(0,1)$.

Mean

\[ \mathbb{E}[y_i] = 0 \]

By linearity of expectation.

Variance

\[ \mathrm{Var}(y_i) = \sum_j x_j^2 \, \mathrm{Var}(r_{ij}) = \|x\|_2^2 \, \mathrm{Var}\!\left(\tfrac{1}{\sqrt{d}}\,\mathcal{N}(0,1)\right) = \frac{\|x\|^2}{d}. \]

\[ y_i \sim \mathcal{N}\!\left(0,\, \frac{\|x\|^2}{d}\right) \qquad \text{(equiv. std.\ } \sigma = \|x\|/\sqrt{d}\text{)}. \]

Probability of clipping after rotation

\[ \Pr\!\left(|y_i| > M\right) = 2\,\Phi\!\left(-\frac{M\sqrt{d}}{\|x\|}\right), \]

$\Phi$ is the CDF of the standard normal.

Chernoff bound

\[ \Pr\!\left(|y_i| > M\right) \le \exp\!\left(-\frac{M^2 d}{2\|x\|^2}\right). \]

Takeaway. The probability of clipping goes down exponentially in the dimension $d$.

Rotation (e.g. a normalized Hadamard transform) spreads outliers across coordinates, so a fixed clip range $M$ is much less likely to hit after the transform.