Quantifying Incoherence in the QuIP Method

In the QuIP quantization method, one key concept is the introduction of incoherence.

For an existing model's parameters, requantization is the process of converting the neural network's weight matrices from a high-precision representation (such as 32-bit floating point) to a low-precision representation (such as 2-bit or 4-bit integers). This process can significantly reduce the model's storage requirements and computational complexity, thereby improving its running efficiency. However, quantization may degrade model performance, because the low-precision representation may fail to fully capture the information in the original weight matrices.

The QuIP method addresses this problem by introducing incoherence between the weight matrix and the Hessian matrix. Incoherence means that the elements of these two matrices vary relatively little across different coordinate axes. During quantization, this incoherence helps ensure that the quantized weight matrix approximates the original weight matrix more closely, thereby reducing quantization error.

To achieve this incoherence, QuIP uses Kronecker products of random orthogonal matrices in the pre- and post-processing stages of its adaptive rounding procedure. This approach realizes matrix incoherence without significantly increasing computational complexity, thereby improving accuracy during quantization.

The term “incoherence” here is somewhat vague in meaning; its actual function is to expand the original weight matrix onto variation across more different coordinate axes.

More intuitively: for example, in three-dimensional space, an orthogonal matrix can be likened to a cube placed askew within the three coordinate axes. An orthogonal matrix can become an upright cube through diagonalization, and this uprighting can be achieved by the orthogonal matrix itself—just multiply by its inverse—because, in essence, under any set of coordinate axes an orthogonal matrix remains mutually orthogonal (perpendicular).

Taking three-dimensional space as an example, multiplying by a three-dimensional orthogonal matrix is equivalent to rotating it in that space; to rotate back, once you know which matrix was multiplied, you simply multiply by its inverse.

Multiplying a three-dimensional vector by a Kronecker product matrix (A ⊗ B) amounts to a rotation and scaling in the original three-dimensional space, and then a further rotation within that rotated and scaled space. This metaphor is not perfectly apt—it offers only an intuitive feel. Fundamentally, one should still view it as a series of transformations of the vector across two orthogonal spaces.

It can therefore be understood that, since orthogonality means the column vectors of a random orthogonal matrix are pairwise orthogonal (perpendicular) and of unit length, when a matrix (such as a weight matrix or Hessian matrix) undergoes a Kronecker product with a random orthogonal matrix, these orthogonal column vectors act on the rows and columns of the original matrix, thereby producing a new set of orthogonal bases in the resulting matrix. These new orthogonal bases make the new matrix's distribution across different coordinate axes more uniform.

There is another important factor: the introduction of randomness. The elements of the random orthogonal matrix are randomly generated; this randomness helps break the correlations among the original matrices, making the newly generated matrix more dispersed across different coordinate axes. Such dispersion helps achieve incoherence between matrices, thereby improving accuracy during quantization.

Put simply: generate a random orthogonal matrix, then take the Kronecker product of the original weights with that orthogonal matrix. Because the Kronecker product does not change the rank of the original matrices, the newly generated matrix still retains most of the information of the originals.

From an image perspective, the Kronecker product can be likened to expanding each pixel of the original image. Multiplying by the identity matrix would produce an effect similar to scaling the image; multiplying by an orthogonal matrix, however, amounts to a “multi-axis-invariant” expansion applied to each pixel.