Faiss

Faiss implements several fundamental ANN algorithm families, each with different performance characteristics for the recall/latency/memory trade-off space.

• Inverted File Index (IVF): A cell-probe method. Divides the vector space into nlist clusters (Voronoi cells) using k-means. Search probes only the nprobe nearest clusters. Offers excellent speed and controllable accuracy.
• Hierarchical Navigable Small World (HNSW): A graph-based method. Builds a multi-layer graph where search performs a greedy traversal from coarse to fine layers. Often provides the highest recall for a given latency but uses more memory.
• Product Quantization (PQ): A compression method. Encodes vectors as short codes by splitting the dimension space into sub-spaces and quantizing each. Dramatically reduces memory footprint (e.g., 128-dim float32 → 64 bits) enabling billion-scale indexes in RAM.

Faiss supports multiple distance metrics and is optimized for batch processing, which is essential for real-world, high-throughput applications.

• Distance Metrics: Primarily optimized for inner product (for cosine similarity on normalized vectors) and L2 (Euclidean) distance. The index structure is often independent of the metric.
• Batched Queries: The search() method accepts a matrix of query vectors, enabling highly parallelized execution. GPU implementations particularly benefit from large batches, saturating processor cores.
• Batched Add/Remove: Supports adding and removing vectors in batches, and some index types support online updates (e.g., IndexIDMap) without full retraining, facilitating dynamic memory stores for agents.

The library's performance stems from assembly-level optimizations and efficient use of modern CPU instruction sets, making it a benchmark for raw speed.

• SIMD Instructions: Heavily utilizes AVX2 and AVX-512 Single Instruction, Multiple Data instructions for parallel distance computations on CPU.
• Memory Alignment: Data structures are carefully aligned in memory to maximize cache efficiency and enable SIMD loads/stores.
• Manual Loop Unrolling: Critical inner loops (like distance calculations) are manually unrolled and optimized, often written in platform-specific intrinsics. This is why pure Python/NumPy implementations are orders of magnitude slower for the same algorithm.

The Inverted File Index is a core indexing method in Faiss for partitioning the vector space. It works by:

1. Clustering: Using k-means to partition the dataset into nlist Voronoi cells (clusters).
2. Inverted Lists: Storing an inverted list for each cluster, containing the IDs of all vectors belonging to that cell.
3. Search: For a query, searching only the nprobe nearest clusters, drastically reducing the number of distance computations.

• Faiss Implementation: IndexIVFFlat is the standard IVF index. Performance is tuned via nlist (granularity of partitioning) and nprobe (number of cells to search).
• Use Case: Ideal for large-scale datasets where a coarse, fast filtering step is beneficial before finer-grained comparison.

Product Quantization is a lossy compression technique for vectors that Faiss uses to reduce memory footprint. It operates by:

• Subspace Splitting: Dividing the high-dimensional vector (e.g., 768D) into m lower-dimensional subvectors (e.g., 8 subvectors of 96D each).

• Codebook Creation: Creating a separate codebook of k centroids for each subspace via k-means.

• Encoding: Representing each original vector by a tuple of m centroid IDs (a PQ code).

• Faiss Indexes: IndexIVFPQ combines IVF with PQ for massive, memory-efficient search. Distance calculations are performed using pre-computed lookup tables.

• Impact: Can reduce vector storage by 96% or more (e.g., 768-dim float32 → 8 bytes) with a controlled accuracy loss.

HNSW is a graph-based ANN algorithm renowned for its high recall and query speed. Faiss includes a highly optimized implementation (IndexHNSW). Its principles are:

• Layered Graph: Constructs a multi-layered graph where the bottom layer contains all vectors, and higher layers are exponentially sparser subsets.

• Greedy Traversal: Search starts at a random entry point in the top layer and navigates to the nearest neighbor, then moves down a layer and repeats, refining the result.

• Proximity Links: Each node maintains links to its nearest neighbors within the same layer, creating a "small world" network for efficient navigation.

• Faiss Parameters: efConstruction controls graph quality during build; efSearch controls the depth of the search frontier at query time.

These are the distance metrics used to measure similarity between vectors in Faiss. The choice of metric defines the geometry of the vector space.

• L2 Distance (Euclidean): Measures the straight-line distance between two points. Faiss optimizes for minimizing L2 distance. IndexFlatL2 is the brute-force baseline.
• Inner Product (IP): Calculates the dot product. For normalized vectors (unit length), Inner Product is equivalent to Cosine Similarity (cosine of the angle between vectors).
• Faiss Handling: Faiss typically requires vectors to be normalized (using faiss.normalize_L2) before indexing for cosine similarity. It then uses the Max Inner Product search.
• Mathematical Relationship: For normalized vectors ||a|| = ||b|| = 1, Cosine(a,b) = a · b. Minimizing L2 distance is equivalent to maximizing Inner Product: ||a - b||^2 = 2 - 2*(a·b).