TL;DR

The main purpose of this PR is to provide a 4-bit quantization type that can be used when k- and i-quants that use blocks of 256 are not available (because the number of columns in some tensors are not a multiple of 256).

In short

• IQ4_NL uses blocks of 32 weights with a fp16 block scales exactly like Q4_0, so models quantized with IQ4_NL are the exact same size as Q4_0 and Q4_K_S.
• IQ4_NL uses a non-linear mapping to convert quants to weights (more on this below)
• Quantization quality as measured by perplexity is much better compared to Q4_0 and almost on par with Q4_K_S.
• Inference performance is almost the same as Q4_0 except on Metal, where it is 8% (prompt processing) or 20% (token generation) slower than Q4_0.
• If implemented row-wise, where the fp16 block scales are replaced with int8_t block scales (plus one floating point scale per row, which adds a negligible amount of bits), this would be a 4.25 bpw quantization, which has the same quantization error as the 4.5 bpw IQ4_NL added by this PR.

PPL comparisons

The following tables show PPL comparisons between Q4_0, Q4_K_S, and IQ4_NL. We start with the case of not using an importance matrix (I find this to be an important use case as at 4-bit quantization ideally one should not worry too much about having a suitable imatrix to quantize a model).

Table 1 PPL comparison without imatrix for context of 512 tokens

The next table is with an imatrix created from wiki.train.raw

Table 2 PPL comparison with imatrix for context of 512 tokens

Just in case researchers working on quantization happen to see this PR, here are some PPL results for a context of 4096 (LLaMA-v2 and Mistral) or 2048 (LLaMA-v1)

Table 3 PPL comparison with imatrix for context of 4096/2048 tokens

To make the comparison with the approaches that are currently claiming to be SOTA, the next table shows the quantization error defined as QErr = PPL(Qunatized)/PPL(fp16) - 1. I took the values for AQLM and QuIP# from the latest QuIP# paper.

Table 4 Quantization error comparisons

Performance comparisons

Table 5 shows PP-512 and TG-128 values for a 7B LLaMA on various platforms

• Metal is on an M2-Max 30-core GPU
• ARM_NEON is on an M2-Max CPU using the 8 performance cores
• CUDA is on an RTX-4080
• AVX2 is on a Ryzen-7950X CPU using 16 (PP-512) or 8 (TG-128) threads.

Additional details

It all comes down to this set of 16 magic values

static const int8_t kvalues_iq4nl[16] = {-127, -104, -83, -65, -49, -35, -22, -10, 1, 13, 25, 38, 53, 69, 89, 113};

Where do they come from? I had implemented a K-means clustering based quantization in my private repository (similar to what, e.g., SqeezeLLM does), with clustering done per tensor row. Although I was getting similar or even slightly better results than SqeezeLLM, I was not particularly happy with the quantization quality, so decided to see what happens if I apply block-wise scaling before clustering. It turned out that the cluster means end up being (nearly) independent of the tensor/tensor row. I collected statistics of the cluster means from a few quantized model, and saw that the 16 means of the cluster means can be fit with a 3rd order polynomial that maps quant index to a (scaled) model weight. Using the polynomial fit directly results in a very decent performance on CUDA, acceptable performance on Metal, but is a no-go for CPU SIMD instructions. On the CPU the only thing that gives a good performance is a lookup table containing int8_t values. So, after scaling the polynomial fit to the full int8_t range and rounding to the nearest integer, we end up with the above 16 values.

The initial work on this was done before I implemented the importance matrix. Without imatrix, the non-linear quantization was basically on par with Q4_K in terms of quantization error (see Table 1), while using ~7% fewer bits (if implemented row-wise with blocks of 32). But after the imatrix was added, Q4_K became again slightly better (Tables 2 and 3). The non-linear quantization outperforms Q4_K with blocks of 16. If implemented using super-blocks of 256 with 6-bit block scales, this would be a 4.4375 bpw SOTA quantization (SOTA in the sense that I'm not aware of a quantization approach that achieves a lower quantization error with less than 5 bpw).