Pangram verdict · v3.3
We believe that this document is a mix of AI-generated, AI-assisted, and human-written content
AI likelihood · overall
MixedArticle text · 1,801 words · 6 segments analyzed
1. Everything is a VectorIn modern AI, images, text, and audio are not understood by computers as "cat" or "symphony". Instead, they are converted into lists of numbers called embeddings or vectors.These vectors live in a high-dimensional geometric space. The core idea is simple: items that are semantically similar are placed close together in this space.Foundations · Vectors & similaritystep 1 / 41. The ChallengeComputers don't have eyes or ears. They only understand numbers. How do we explain the concept of a 'Dog' or a 'Cat' to a machine?step 2 / 42. VectorizationWe use Neural Networks to transform raw data (pixels, text) into a list of numbers. This list is the 'Embedding'. It captures the semantic meaning.step 3 / 43. The Vector SpaceThese numbers act as coordinates (X, Y, Z...). We can plot every image or word as a single point in a high-dimensional space.step 4 / 44. Similarity is DistanceIn this space, concepts that are similar are placed close together. 'Cat' is close to 'Dog', but far from 'Car'. We measure this using distance (Euclidean or Cosine).Above, we visualize a simplified 2D slice of this space. Imagine this in 1024 dimensions. Finding the "nearest neighbor" for a query point is equivalent to finding the most similar item in your database.2. The NN Problem at ScaleFormally, given a query and a database of vectors, exact nearest-neighbor search solves:The naive Brute Force solution evaluates every distance explicitly. Cost per query: time and memory to hold the database in full precision. For SIFT descriptors (, 4 bytes per float), that is 512 GB of RAM and one billion distance evaluations per search, a non-starter for real-time systems like web-scale retrieval or live LLM memory.The rest of this article explores the two escape routes FAISS exploits:Partitioning: skip most of at query time (IVF).Compression: make each comparison cheap, and make the database fit in RAM (Product Quantization).Production systems combine both.3. FAISS to the RescueFAISS (Facebook AI Similarity Search) introduces approximate search methods.
By sacrificing a tiny bit of accuracy (maybe you get the 2nd best match instead of the 1st), we can speed up search by orders of magnitude.Let's explore two key indexing strategies:Flat: The baseline brute-force. Slow but accurate.IVF (Inverted File):Partitions the space into "Voronoi cells". We only look in the most promising cells.Try it yourself. Increase the dataset size and see how different indexes perform.Interactive Index BenchmarkCompare the performance of different indexing algorithms on random datasets.Precomputed benchmarksDataset Size (N)Index Type4. Partitioning with IVFThe Inverted File (IVF)index works like a library classification system. Instead of looking at every book to find a specific title, you go to the "Science Fiction" section first.Mathematically, it uses K-Means clustering to partition the vector space into Voronoi cells. When we search, we first identify which cell our query vector falls into (using a "coarse quantizer"), and then we only calculate distances for vectors inside that cell (and perhaps a few neighboring ones).IVF Clustering1. Raw DataK-means partitions random vectors into the Voronoi cells that IVF searches.Start: Here is our raw dataset. 80 vectors in a 2D space. Searching this linearly (Brute Force) would require calculating distance to 80 points.5. Compressing with Product QuantizationIVF makes search fast by skipping most of the database, but leaves every vector uncompressed. One billion SIFT descriptors still cost 512 GB of RAM. Product Quantization (PQ), introduced by Jégou, Douze and Schmid (2011), is the compression trick FAISS builds on to shrink each vector to 8 bytes while keeping distance estimates meaningful.Same centroids, a different job§4 used centroids to partition the search space. PQ uses them to compresseach vector. Same K-Means math, new purpose: the centroid's index becomes the vector. If your codebook has centroids, any vector collapses to one integer in .A pixel-sized analogyA 24-bit RGB pixel can be any of 16.7 million colors. A GIF gives up some of that range: it picks a 256-color palette and replaces every pixel with an 8-bit index into it.
Storage drops 3×, the picture still looks like the picture. That palette is a codebook; the index is a code.A 128-D SIFT descriptor is just a very long pixel. We want the same trick: find a palette of representative vectors, replace every descriptor with its nearest palette index.How many bits does an index cost?To label centroids uniquely you need enough bits to distinguish all of them. Each bit doubles the number of labels, so the code length is bits. Concretely: centroids → bits per code (1 byte) centroids → bits centroids → 64 bits (8 bytes)More centroids means the quantizer discriminates finer detail, and the code grows accordingly. The codebook designer is playing a bit-budget game.The paper's aggressive targetJégou et al. want each 128-D SIFT descriptor to become a 64-bit code, which is 0.5 bit per dimension, a 64× compression ratio against the 512-byte original. Half a bit per dimension is ambitious: it means the quantizer has to encode all the variation along each axis with a single binary-ish choice.Hitting 64 bits with one flat codebook means picking centroids. That is roughly 18 quintillion, more than the number of grains of sand on Earth. Let's feel that number before we dismiss it.Flat codebook feasibilityPick a vector dimension and a bit budget per dimension to see the centroid count and storage footprint a single flat quantizer would need.Vector dimension (D)Bits per dimensionTotal bits per code64bitsCentroids needed (k = 2^64)1.84 × 10^19centroidsCodebook storage9.44ZBImpossibleBigger than all cloud storage on Earth. Lloyd's algorithm would need roughly 5.53 × 10^20 training samples.Why 264 is not a codebookThree walls hit simultaneously when gets that large:Storage.Each centroid is 128 floats × 4 bytes = 512 bytes. Times centroids gives about 9.4 zettabytes, more than all cloud storage on Earth in 2025. You cannot persist the codebook, let alone page through it at query time.
Training data.Lloyd's algorithm needs at least tens of samples per centroid to converge. That is training vectors. No dataset in existence is that large.Query cost.To encode one descriptor you compare it to every centroid. 18 quintillion distance computations per vector is not a latency you can ship.The flat codebook dies on all three fronts. The paper's move is to keep the effective vocabulary the same size while shrinking the stored codebook by many orders of magnitude.The factoring trickBack to the GIF analogy. Instead of finding one 256-color palette that works for the whole image, cut the image into 8 tiles and give each tile its own 256-color palette. Each tile is now one byte; the image is 8 bytes; every tile had access to a full 256-color palette tuned to its own pixels. PQ does exactly this for vectors.Formally: split into sub-vectors and learn one small sub-quantizer per block. The product quantizer is the tuple of their outputs:With and centroids per block, the effective codebook has possible combinations (same order of magnitude as the impossible flat case), but we only store centroid vectors in each. Total codebook storage is (paper §II.B, Table I), small enough to live in L2 cache.Each encoded vector fits in , one byte per block index. Ratio: 512 B to 8 B, a 64× drop in memory, with a codebook that actually fits on the machine.The walkthrough below builds the full index on the paper's reference SIFT setting (), turning each concept above into a concrete operation on real numbers.Compression · Product Quantizationstep 1 / 81. One descriptor, zoomed all the way inA 128-D vector is 128 floats. Zoom into a single one and you find IEEE 754: 1 sign bit, 8 exponent bits, 23 mantissa bits.Four bytes per dimension, 512 bytes per vector.step 2 / 82. Cut it into 8 sub-vectorsSame 128 numbers, regrouped into 8 contiguous blocks of 16 dimensions each.Each block gets its own colour because each one will get its own codebook.step 3 / 83.
Now multiply: a tiny demo databaseA codebook needs a population, not a single vector. This demo uses 4 example vectors; the paper trains on millions.Every database vector gets the same 8-block split, and each block contributes one point per vector to its own subspace.step 4 / 84. Focus on one codebook: u₁Each subspace gets its own codebook, trained alone. That independence is the product in Product Quantization.To see the whole recipe, we zoom into just one subvector, u₁, rendered in 2-D for readability (the paper's subspaces live in d* = D/m = 16 dimensions, with D = 128 and m = 8). Four training vectors is a pedagogical cartoon; real PQ trains each subspace on roughly 10⁶ descriptors.Lloyd's algorithm runs k-means on this subspace alone: assign every point to its nearest centroid, move each centroid to its cluster mean, repeat until the within-block distortion MSE(q₁) = 𝔼‖u₁(x) − q₁(u₁(x))‖² stops falling.The 6 centroids you end with (k* = 256 in the paper) form the codebook C₁. Encoding any future vector's first block is then a nearest-centroid lookup: emit the index i of c₁,ᵢ.step 5 / 85. Same thing, 8 times in parallelAll 8 subspaces are quantized the same way at once, each block over its own slice of the data with its own codebook.
Lloyd's runs per block, independently (k* = 256 clusters per codebook in the paper, shown here with 6).step 6 / 86. Encoding a brand-new vectorA query x arrives at search time, it was never in the training set.Split it into 8 sub-vectors and, in each plot, snap to the nearest centroid. The 8 indices concatenate into the 8-byte code.step 7 / 87. Decoding and per-block errorReconstruction is a table lookup: replace each index by its centroid.The gap between the unknown raw point and its centroid is the per-block quantization error; the total reconstruction error is their sum of squares.step 8 / 88. Distance without decoding: SDC vs ADCTwo ways to compute query-to-database distance from codes.SDC quantises both points and reads centroid-to-centroid distances. ADC keeps the query in full precision and reads raw-to-centroid distances.ADC has a tighter error bound; FAISS defaults to it.Once encoded, how do we measure distances without decoding every vector back to its 512 bytes? The paper gives two options.SDC (symmetric) quantizes both the query and the database vector and reads a pairwise centroid distance from a precomputed table per sub-quantizer. ADC (asymmetric) leaves the query in full precision and precomputes only query-to-centroid distances per block, then sums one lookup per block:Per-query cost is similar (Jégou et al., Table II), but ADC has a tighter error bound: the mean squared distance error satisfies for ADC(Eq 18) versus for SDC. FAISS defaults to ADC.6. Combining: IVFPQIVFPQ (also called IVFADC in the paper) stacks the two previous techniques: a coarse quantizer prunes the database to a handful of cells, and a product quantizer compresses what remains to 8 bytes per vector. One subtle choice makes the combination work: PQ encodes not the raw vector but its residual with respect to the coarse centroid.