Skip to content
Last Dictionary
Plane
AI Engineering & MLOpsMathematics & StatisticsInference & Efficiency

product quantization

nounAlso: PQ, IVFPQ, optimized product quantization, OPQ

In plain wordsA compression trick for embeddings: chop each long list of numbers into short pieces and replace each piece with the ID of its closest typical piece, shrinking storage many times over while keeping search workable.

  1. A vector-compression method for approximate nearest neighbor searchapproximate nearest neighbor search, n.: A family of shortcuts for finding the most similar items in a huge collection without checking every one — accepting an occasional miss in exchange for answers thousands of times faster. that splits each D-dimensional vector into m subvectors, learns a separate small codebook for each subspace by k-means clusteringk-means clustering, n.: A simple way to split data into a chosen number of groups: guess group centers, assign every point to its nearest center, move each center to the middle of its points, and repeat. (commonly 256 centroids, so each subvector is stored in one byte), and represents the vector by its m centroid indices; a 768-dimensional float32 embedding of 3,072 bytes can thus shrink to 64 or 96 bytes. Distances between a query and compressed vectors are estimated quickly from per-subspace lookup tables (asymmetric distance computation) without decompressing them. PQ is usually combined with an inverted-file coarse partition (IVFPQ) and followed by re-scoring with exact vectors; variants rotate the space first (optimized PQ) or learn additive codebooks. It differs from quantizationquantization, n.: Storing an AI model's numbers with fewer digits, like rounding prices to the nearest dollar, so the model takes less memory and runs faster, usually with only a small loss of accuracy. of model weights, though both trade numeric precision for memory.

    Product quantization let the billion-vector index fit in 64 GB of RAM.

Origin

Introduced by Hervé Jégou, Matthijs Douze and Cordelia Schmid of INRIA in 'Product quantization for nearest neighbor search' (IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011). 'Product' refers to the Cartesian product of the subspace codebooks. It became a core component of FAISSFAISS, prop. n.: A free software library from Meta for searching huge collections of embeddings very fast, on ordinary processors or graphics cards. Many AI search systems use it under the hood..

Related

See also
  • approximate nearest neighbor searchapproximate nearest neighbor search, n.: A family of shortcuts for finding the most similar items in a huge collection without checking every one — accepting an occasional miss in exchange for answers thousands of times faster.
  • FAISSFAISS, prop. n.: A free software library from Meta for searching huge collections of embeddings very fast, on ordinary processors or graphics cards. Many AI search systems use it under the hood.
  • vector databasevector database, n.: A database built to store embeddings — lists of numbers that represent meaning — and to quickly find the stored items most similar to a new one. It is the memory behind many AI search tools.
  • quantizationquantization, n.: Storing an AI model's numbers with fewer digits, like rounding prices to the nearest dollar, so the model takes less memory and runs faster, usually with only a small loss of accuracy.
  • k-means clusteringk-means clustering, n.: A simple way to split data into a chosen number of groups: guess group centers, assign every point to its nearest center, move each center to the middle of its points, and repeat.
  • HNSWHNSW, abbr.: A popular way to organize millions of embeddings for fast similarity search: a layered web of links where the search starts with long jumps on sparse top layers, then takes ever shorter steps.
Contrast with
  • quantizationquantization, n.: Storing an AI model's numbers with fewer digits, like rounding prices to the nearest dollar, so the model takes less memory and runs faster, usually with only a small loss of accuracy.

Sources

  1. Jégou, H., Douze, M. & Schmid, C. (2011). Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence 33(1): 117–128.

Mentioned in

approximate nearest neighbor searchapproximate nearest neighbor search, n.: A family of shortcuts for finding the most similar items in a huge collection without checking every one — accepting an occasional miss in exchange for answers thousands of times faster., FAISSFAISS, prop. n.: A free software library from Meta for searching huge collections of embeddings very fast, on ordinary processors or graphics cards. Many AI search systems use it under the hood., HNSWHNSW, abbr.: A popular way to organize millions of embeddings for fast similarity search: a layered web of links where the search starts with long jumps on sparse top layers, then takes ever shorter steps., vector databasevector database, n.: A database built to store embeddings — lists of numbers that represent meaning — and to quickly find the stored items most similar to a new one. It is the memory behind many AI search tools., Matryoshka embeddingMatryoshka embedding, n.: An embedding built like a set of Russian nesting dolls: its first few numbers already give a rough summary, so you can cut it short to save space and still search reasonably well., vector quantizationvector quantization, n.: Compressing data by replacing each item with the nearest entry from a small catalog of representative examples, so that only the catalog number needs to be stored or sent.