Product Quantization (PQ)

The fundamental operation of PQ is to split a high-dimensional vector into m distinct subvectors. For a D-dimensional vector, it is divided into m subvectors of dimension D/m each. This decomposition treats the original vector space as the Cartesian product of these lower-dimensional subspaces. This step is critical because it allows quantization to be performed on more manageable, lower-dimensional spaces where codebooks can be learned effectively, rather than attempting the intractable task of quantizing the entire high-dimensional space directly.

For each of the m subspaces, a separate codebook is learned via k-means clustering on the subvectors from the training dataset. Each codebook contains k codewords (centroids).

• A typical configuration uses k=256, allowing each codeword index to be stored in a single byte (8 bits).
• This results in m independent codebooks. The key is that the total number of possible centroids in the reconstructed space is k^m, which is astronomically large (e.g., 256^8 ≈ 1.8e19), enabling a rich representation, while only storing m * k * (D/m) values = k * D values for all codebooks.

To encode a new vector, it is first split into m subvectors. Each subvector is then quantized by replacing it with the index of its nearest codeword in that subspace's codebook.

• The final encoded representation of the original vector is simply the concatenation of these m integer indices.
• This transforms a dense vector (e.g., 128 dimensions of 32-bit floats = 512 bytes) into a compact code of m bytes (for k=256). This achieves compression ratios of 50x or more, drastically reducing memory storage requirements for billion-scale vector databases.

PQ enables fast approximate search using Asymmetric Distance Computation. During query time:

• The query vector is split into subvectors but is not quantized.
• For each subspace codebook, a partial distance table is pre-computed, storing the distance between the query subvector and every codeword in that codebook.
• To compute the approximate distance to a database vector, its m byte codes are used as lookup indices into these m partial distance tables. The m looked-up distances are summed. This avoids computationally expensive reconstruction of the database vectors and allows distances to be computed using only table lookups and addition, which is extremely fast.

In production systems, PQ is rarely used alone. It is combined with a coarse quantizer in the Inverted File with Product Quantization (IVF-PQ) architecture.

• A first-level Inverted File (IVF) clusters all vectors into nprobe Voronoi cells using k-means.
• Within each cell, residuals (the vector minus the cluster centroid) are compressed using PQ.
• During search, the query is compared to cluster centroids to select the nprobe nearest cells. Only the PQ-compressed residuals within those cells are searched using ADC. This two-tiered approach combines fast filtering (IVF) with efficient, accurate distance calculation (PQ) on a subset of data.

PQ introduces a controlled trade-off between memory/performance and recall accuracy.

• Parameters: Accuracy is governed by m (number of subvectors) and k (centroids per subcodebook). Increasing either generally improves accuracy at the cost of storage and slower distance computation.
• Memory Footprint: Storage is O(m * bytes_per_vector). For m=8, k=256, it's 8 bytes per vector.
• Search Speed: Distance computation is O(m) operations (table lookups and adds), independent of original dimensionality D.
• Limitation: It is a lossy compression method. Fine-grained distance information within a subspace is lost when a subvector is replaced by a single centroid index, which can lead to reduced recall, especially for very high-dimensional data.

Quantization is a model compression technique that reduces the numerical precision of values, typically converting 32-bit floating-point numbers to lower-bit integers (e.g., 8-bit). This drastically reduces the memory footprint and computational cost of storing and comparing vectors.

• Purpose: Enables the deployment of large models on memory-constrained devices (edge, mobile) and accelerates inference.
• Types: Includes Post-Training Quantization (PTQ) and Quantization-Aware Training (QAT).
• Trade-off: Introduces a minor loss in precision (quantization error) for significant gains in efficiency.

Approximate Nearest Neighbor (ANN) search is a class of algorithms that find approximate closest vectors in high-dimensional spaces, trading perfect accuracy for orders-of-magnitude improvements in speed and memory efficiency. It is the fundamental query operation for vector databases.

• Core Problem: Exact nearest neighbor search becomes computationally intractable at scale (the "curse of dimensionality").
• Common Algorithms: HNSW, IVF-PQ, and LSH (Locality-Sensitive Hashing).
• Use Case: Powers the semantic search and retrieval step in Retrieval-Augmented Generation (RAG) pipelines and agentic memory lookups.

IVF-PQ is a composite ANN algorithm that combines two techniques for highly efficient search. First, an Inverted File (IVF) index clusters the dataset (coarse quantization). Then, Product Quantization (PQ) compresses the residuals within each cluster (fine quantization).

• IVF Stage: Divides the vector space into Voronoi cells using k-means, allowing the search to focus on a few promising clusters.
• PQ Stage: Compresses vectors within a cluster, enabling them to be stored in RAM and compared using fast lookup tables.
• Performance: This combination is a standard for billion-scale vector search, balancing recall, speed, and memory usage.

A Vector Store or Vector Database is a specialized database designed to store, index, and query high-dimensional vector embeddings. It is the primary persistence layer for agentic memory, enabling long-term storage and fast semantic retrieval of experiences, facts, and context.

• Core Function: Performs ANN search at scale to find semantically similar vectors.
• Features: Often include metadata filtering, hybrid search (combining vector + keyword), and dynamic data ingestion.
• Examples: Pinecone, Weaviate, Qdrant, and Milvus. These systems frequently use PQ-based indices like IVF-PQ under the hood.

Memory Compression in agentic systems refers to techniques for reducing the storage footprint of memories (e.g., past interactions, knowledge, states) while preserving their utility for future reasoning and retrieval. PQ is a leading technique for compressing the vector representations of these memories.

• Objective: Allow agents to maintain longer histories and larger knowledge bases within fixed memory budgets.
• Beyond PQ: Includes other methods like pruning less important memories, summarization, and dimensionality reduction.
• Impact: Directly affects an agent's operational context window and its ability to reason over extended timeframes.