Sub-4-Bit Quantization: AQLM, QuIP#, & HQQ

Table of Contents

1. Learning Objectives
2. Notation
3. Core Intuition
4. Why Sub-4-Bit Is Hard
5. AQLM: Additive Quantization
6. QuIP#: Incoherence Processing
7. HQQ: Half-Quadratic Quantization
8. SqueezeLLM: Sensitivity-Based Sparsity
9. Quality at 2-3 Bits
10. Information-Theoretic Limits
11. Common Pitfalls
12. Summary
13. Exercises

Learning Objectives

1. Explain why standard quantization fails below 4 bits.
2. Describe AQLM's multi-codebook approach.
3. Derive QuIP#'s incoherence transformation and its benefit.
4. Compare 2-bit methods (AQLM, QuIP#, HQQ) against each other.
5. Analyze the theoretical minimum bits needed to represent a model without quality loss.

Notation

• $\mathcal{C} = \{c_1, \ldots, c_K\}$ — codebook
• $r$ — number of residual codebooks (AQLM)
• $\mathbf{U}$ — random orthogonal matrix (incoherence processing)

Core Intuition

Below 4 bits, the number of representable values is so small (8 at 3 bits, 4 at 2 bits) that scalar quantization cannot preserve weight distributions. Advanced methods overcome this by: (1) quantizing GROUPS of weights jointly (vector quantization/codebooks), (2) making the weight matrix "easier" to quantize via random rotations (incoherence), or (3) combining sparse outlier storage with aggressive low-bit compression of the remaining weights.

Why Sub-4-Bit Is Hard

The fundamental problem: At 2 bits, only 4 values represent each weight. For a Gaussian with $\sigma = 0.01$:

16x more error at 2-bit vs 4-bit. This compounds across layers.

Additional problems:

• Weight correlations are ignored by scalar quantization.
• Outlier weights cannot be represented with so few levels.
• Per-group overhead becomes prohibitive (need very small groups → more scales).

AQLM: Additive Quantization

Key idea (Egiazarian et al., 2024): Instead of scalar quantization, use VECTOR quantization with multiple additive codebooks:

where each $\mathcal{C}_r$ is a learned codebook with $K$ entries, and $i_r$ is the codebook index.

Bits per weight: Group of $g$ weights represented by $R$ codebook indices of $\log_2(K)$ bits each:

For $R=2, K=256 (8\text{-bit index}), g=8$: BPW = $2 \times 8 / 8 = 2$ bits.

Training: Alternate between:

1. Fix codebooks, optimize assignments (beam search).
2. Fix assignments, optimize codebooks (least squares).
3. Fine-tune with STE.

Result: At 2 bits, AQLM achieves perplexity close to GPTQ at 3 bits.

QuIP#: Incoherence Processing

Key idea (Chee et al., 2024): Make the weight matrix "maximally spread out" before quantization.

Incoherence: A matrix is incoherent if its entries are roughly uniform in magnitude (no outliers). Quantization error is lower for incoherent matrices.

Random Hadamard rotation:

where $\mathbf{U}_1, \mathbf{U}_2$ are random orthogonal matrices (implemented via Hadamard + random signs for $O(d\log d)$ cost).

Why it helps: Outlier weights are "spread" across many entries after rotation. Each entry becomes more uniform → standard quantization works better.

Lattice quantization: After incoherence processing, use E8 lattice (8D geometric structure) for vector quantization — provably optimal packing at 2 bits.

Result: State-of-the-art 2-bit quantization. LLaMA-2 70B at 2 bits approaches 4-bit GPTQ quality.

HQQ: Half-Quadratic Quantization

Key idea (Badri & Shaji, 2023): Formulate quantization as an optimization problem with a half-quadratic penalty:

Solved via alternating minimization:

1. Optimize continuous relaxation.
2. Project to quantization grid.
3. Repeat.

Advantages:

• No calibration data needed (unlike GPTQ, AWQ).
• Very fast (minutes, not hours).
• Comparable quality to GPTQ at 4 bits; competitive at 2-3 bits.

SqueezeLLM: Sensitivity-Based Sparsity

Hybrid approach (Kim et al., 2024):

1. Identify sensitive weights via second-order information (Hessian diagonal).
2. Store sensitive weights as sparse FP16 values.
3. Quantize remaining weights aggressively (3-4 bits).

Typical sparsity: 0.5-1% of weights stored in FP16. These are the "outliers" that would ruin quantization.

BPW calculation: $(1-p) \times 3 + p \times 16 \approx 3.07$ BPW for $p=0.5\%$ sparsity.

Quality at 2-3 Bits

LLaMA-2 70B perplexity (WikiText-2):

Key takeaway: At 2 bits, advanced methods (AQLM, QuIP#) maintain usable quality. RTN and even GPTQ struggle significantly. The gap narrows at 3-4 bits.

Information-Theoretic Limits

Rate-distortion theory: For a source with distribution $p(w)$ and MSE distortion $D$:

For near-zero distortion: Need approximately $\frac{1}{2}\log(1/\text{MSE}) \approx 4$-$5$ bits for typical weight distributions.

Practical minimum: Around 1.5-2 bits before quality degrades irrecoverably (assuming optimal coding like AQLM). This aligns with BitNet b1.58 results.

Implication: There IS a hard floor. Below 1.5 bits, no method can maintain quality without increasing model width.

Common Pitfalls

Pitfall 1. Evaluating 2-bit models on perplexity alone. Perplexity may look acceptable but downstream task quality (reasoning, coding) degrades disproportionately at extreme quantization.

Pitfall 2. Using GPTQ/AWQ at 2 bits. These methods are designed for 4-bit; they lose competitiveness below 3 bits. Use AQLM or QuIP# instead.

Pitfall 3. Ignoring the decoding overhead of vector quantization. Codebook lookups add latency; actual inference speed may not improve proportionally to memory savings.

Summary

• Sub-4-bit requires fundamentally different approaches than scalar quantization.
• AQLM: Multi-codebook vector quantization; best quality at 2 bits.
• QuIP#: Random rotation for incoherence + lattice quantization.
• HQQ: No calibration data needed; fast; competitive quality.
• SqueezeLLM: Sparse outliers in FP16 + aggressive low-bit dense.
• Limits: 1.5-2 bits is the information-theoretic floor for Gaussian weights.
• Below 3 bits: specialized methods essential; above 3 bits: GPTQ/AWQ sufficient.

Exercises

Exercise 1. For AQLM with $R=2, K=256, g=8$: compute BPW and total model size for a 7B model.

Exercise 2. Prove that multiplying by a random orthogonal matrix reduces the maximum entry of a matrix in expectation (incoherence argument).

Exercise 3. Compute the rate-distortion function $R(D)$ for a Gaussian with $\sigma=0.02$. What MSE corresponds to 2 bits? Is this tolerable?

Exercise 4. Design a codebook with $K=16$ entries optimized for a standard normal distribution. Where should the 16 centroids be placed?

Exercise 5. Compare the decode throughput (tokens/sec) of AQLM-2bit vs GPTQ-4bit on GPU, accounting for codebook lookup overhead.