Imagine you need to compress a massive collection of high-dimensional vectors—such as image embeddings, database descriptors, or neural network weights—into a tiny memory footprint while preserving their geometric relationships.
Standard Vector Quantization (VQ), like classical $K$-means, maps every vector to a single closest centroid chosen from a codebook. If you want high precision, say a bit budget of $B$ bits, your codebook must contain $2^B$ centroids. For a modest budget of 32 bits, storing and searching through $2^{32}$ (over 4 billion) high-dimensional vectors is computationally and financially impossible.
To bypass this bottleneck, traditional approaches often turn to Product Quantization (PQ). As utilized in generative modeling by Denis Zavadski et al. in PQGAN: Product-Quantised Image Representation for High-Quality Image Synthesis, PQ splits a high-dimensional vector into $M$ distinct, orthogonal subspaces and quantizes each subspace independently. While PQ successfully scales the representational space, it forces a strict coordinate-wise independence, which introduces severe quantization distortion when features span across those arbitrary subspace boundaries.
Additive Vector Quantization (AQ) provides a more powerful alternative. Instead of splitting a vector into disjoint pieces or picking a single holistic centroid, AQ represents the entire vector as the sum of multiple components chosen from independent codebooks.
The Combinatorial Explosion of Addition
The core magic of Additive Quantization lies in its combinatorial capacity. Mathematically, a vector $x$ is approximated as the summation of $M$ codewords chosen from $M$ distinct codebooks:
$$x \approx \sum_{m=1}^M c_{m, i_m}$$
where $c_{m, i_m}$ is the $i_m$-th codeword from the $m$-th codebook.
If you maintain $M$ codebooks, each containing $K$ entries, you can represent $K^M$ unique vector configurations. Crucially, you only need to store $M \times K$ total vectors in memory.
Standard VQ: [ Codeword ] ---> 1 choice out of K
Product VQ: [ Subspace 1 ] [ Subspace 2 ] [ Subspace 3 ] ---> Concatenation of M choices
Additive VQ: [ Codeword 1 ] + [ Codeword 2 ] + [ Codeword 3 ] ---> Summation of M choices
This structural shift turns an exponential storage requirement into a linear one. For example, with just 4 codebooks of 256 entries each, AQ can represent $256^4 = 4,294,967,296$ unique virtual centroids while only storing $4 \times 256 = 1,024$ actual vectors.
Early roots of this concept appeared in generative modeling. David A Ross et al. introduced this combinatorial perspective in Multiple Cause Vector Quantization, demonstrating how decomposing complex signals into independent factors with discrete states yields massive representational capacity. To scale this concept for high-precision retrieval, Mohammad Norouzi et al. developed Cartesian K-Means, proving that an astronomical number of cluster centers could be tracked and searched with minimal memory overhead.
Why Summation Beats Concatenation
To understand why adding codewords is fundamentally more expressive than concatenating them, consider how they occupy space. In Product Quantization, each codebook entry is strictly confined to its assigned coordinates; it has zero influence over the rest of the vector.
As highlighted by Jin Zhang 0035 et al. in Anisotropic Additive Quantization for Fast Inner Product Search, additive quantization allows every single dictionary entry to potentially span and affect all dimensions of the vector. This structural flexibility means that instead of slicing the vector space into rigid, axis-aligned hypercubes, the model can dynamically layer vectors on top of one another to fit the true distribution of the data.
The authors of Composite Quantization for Approximate Nearest Neighbor Search formalized this advantage, showing that treating vector approximation as a summation over distinct dictionaries yields a much more flexible reconstruction than partitioning the space into independent, lower-dimensional subspaces. To push this resolution even higher, Jianfeng Wang et al. proposed Optimized Cartesian K-Means, which allows multiple sub-codewords from different sub-codebooks to represent a single data subspace, drastically minimizing quantization distortion within a fixed bit budget.
Further refinements introduce continuous scaling to this discrete framework. For instance, Herve Jegou et al. developed a hybrid approach in Approximate search with quantized sparse representations, representing vectors as linear combinations of dictionary atoms paired with secondary quantized scalar weights to maximize approximation accuracy.
High-Resolution Retrieval and Cross-Modal Alignment
Because Additive Quantization compresses vectors into compact indices while preserving high-fidelity distance approximations, it has become a cornerstone for fast similarity search.
In supervised settings, Xiaojuan Wang et al. demonstrated in Supervised Quantization for Similarity Search that learning an additive codebook jointly with a discriminative subspace enforces class separability, allowing for high-resolution distance estimation using very few bits.
This expressiveness becomes especially critical when bridging different data modalities, such as matching text queries to images. In Collaborative Quantization for Cross-Modal Similarity Search, Jingdong Wang et al. utilized the additive framework to jointly learn quantizers that align disparate modalities into a shared latent space. Similarly, Mingsheng Long et al. designed Composite Correlation Quantization for Efficient Multimodal Retrieval, which unifies embedding alignment and additive quantization into a single optimization problem, preserving rich semantic information in highly compact binary codes.
Extreme Compression for Deep Learning
While Additive Quantization was popularized in information retrieval, its ability to squeeze maximum precision out of ultra-low bit budgets has triggered a major resurgence in compressing large deep learning models.
In speech processing, Chen Wang et al. leveraged this capability in Discrete Cross-Modal Alignment Enables Zero-Shot Speech Translation. By utilizing grouped discrete codebooks, the model constructs an exponentially large representational space out of a limited set of virtual tokens, enabling high-resolution semantic mapping with a tiny parameter footprint.
The most dramatic modern application of this technique lies in compressing Large Language Models (LLMs) down to 2 or 3 bits per parameter. Vage Egiazarian et al. introduced this to the LLM space with Extreme Compression of Large Language Models via Additive Quantization. By grouping weight matrices and modeling them as sums of vectors selected from multiple learned lookup tables, they achieved near-lossless compression at extreme bitrates, making compressed models Pareto-optimal for the first time.
Weight Vector [w1, w2, ..., wn]
│
├─► Codebook 1 Entry [ 0.1, -0.4, ..., 0.2 ]
├─► Codebook 2 Entry [ 0.0, 0.5, ..., -0.1 ]
└─► Codebook 3 Entry [-0.2, 0.1, ..., 0.0 ]
───────────────────────────────────────────────
SUMMED RECONSTRUCTION [ -0.1, 0.2, ..., 0.1 ]
To push the boundaries of post-training quantization even further, Yuzhuang Xu proposed CRVQ: Channel-relaxed Vector Quantization for Extreme Compression of LLMs. Recognizing that neural network performance is often bottlenecked by a tiny subset of highly sensitive "critical" channels, Xu designed an additive strategy that uses a uniform base codebook for all weights, overlaid with an additional extended codebook exclusively for those critical channels. Summing entries from both codebooks effectively increases the bit-depth exactly where precision matters most, while maintaining ultra-low bit-widths for the rest of the network.
Key Foundational Work
Cartesian K-Means (2013) — contributed 2 concept elements to this direction.
Multiple Cause Vector Quantization (2002) — contributed 2 concept elements to this direction.