Vector Index

HNSW is a graph-based ANN algorithm that constructs a multi-layered graph where each layer is a subset of the previous one. Search begins at the top layer (fewest nodes) to find an approximate entry point, then greedily traverses down through the hierarchy to refine the result. It offers an excellent trade-off between query speed, recall, and memory usage, making it a popular default choice.

• Key Mechanism: Multi-layered proximity graph with long-range links ("small world" property) for fast navigation.
• Performance: Typically achieves >95% recall with sub-millisecond query times on million-scale datasets.
• Use Case: General-purpose semantic search where low latency and high accuracy are critical.

IVF partitions the vector space into k clusters (Voronoi cells) using an algorithm like k-means. Each cluster has a centroid, and all vectors are assigned to their nearest centroid's list. During search, the query is compared to all centroids to identify the nprobe most promising clusters; only vectors within those clusters are exhaustively searched. It balances speed and accuracy by limiting the search scope.

• Key Mechanism: Space partitioning via clustering; search is restricted to nearest clusters.
• Tuning Parameter: nprobe controls the number of clusters searched (higher = more accurate, slower).
• Use Case: Large-scale datasets where controlled, tunable search speed is required, often combined with compression.

PQ is primarily a vector compression technique that drastically reduces memory footprint, enabling billion-scale indexes to reside in RAM. It splits the original high-dimensional vector into m subvectors, each quantized into one of k centroids learned from the data. A vector is represented by a short code (the concatenated centroid IDs). Distance calculations use pre-computed lookup tables.

• Key Mechanism: Subspace decomposition and quantization. Enables memory-efficient exhaustive search or is combined with IVF.
• Compression: Can reduce memory usage by 16x to 32x with minimal accuracy loss.
• Use Case: IVF-PQ is a standard industry pattern for in-memory search on massive vector datasets.

Scalar Quantization compresses vectors by reducing the numerical precision of each vector component (e.g., from 32-bit floats to 8-bit integers). It is simpler than PQ and provides faster distance calculations due to the use of integer SIMD instructions. While offering lower compression ratios than PQ, it often has lower reconstruction error for the same memory budget.

• Key Mechanism: Per-component precision reduction (e.g., FP32 -> INT8).
• Performance: Enables faster distance computations and reduced memory bandwidth usage.
• Use Case: Scenarios where maximizing query speed and minimizing CPU cache misses is paramount, often used with HNSW.

For datasets that exceed available RAM, disk-based indexes trade query speed for virtually unlimited capacity. They use techniques like memory-mapped files and specialized on-disk graph or tree structures to minimize random I/O. Performance is heavily dependent on SSD throughput and caching strategies.

• Key Mechanism: Graph or tree structures persisted to disk with optimized access patterns.
• Consideration: Query latency is orders of magnitude higher than in-memory indexes (milliseconds vs. tens of milliseconds).
• Use Case: Billion-scale vector databases where the entire dataset cannot fit into physical memory.

In RAG architectures, a vector index stores embeddings of an enterprise knowledge base (documents, FAQs, code). When a user query is embedded, the index performs an approximate nearest neighbor (ANN) search to retrieve the most semantically relevant context, which is then passed to a large language model to generate a grounded, factual answer. This is the dominant use case, eliminating hallucinations by providing source-attributed context.

Approximate Nearest Neighbor search is a class of algorithms designed to efficiently find the closest vectors to a query point in high-dimensional space, trading off perfect accuracy for immense gains in speed and scalability. Unlike exact K-NN, which becomes computationally prohibitive at scale, ANN algorithms use techniques like pruning, hashing, or graph traversal to search a subset of the data.

• Core Trade-off: Balances recall (finding the true nearest neighbors) against query latency and memory usage.
• Key Algorithms: Includes HNSW, IVF, and Locality-Sensitive Hashing (LSH).
• Use Case: The fundamental operation enabled by a vector index, making semantic search over millions of embeddings feasible in milliseconds.

Hierarchical Navigable Small World is a state-of-the-art, graph-based algorithm for approximate nearest neighbor search. It constructs a multi-layered graph where each layer is a subset of the previous one, enabling highly efficient logarithmic-time search complexity.

• Mechanism: Search begins at the topmost, sparsest layer using long-range connections, then "zooms in" through lower, denser layers to refine the result.
• Advantages: Often provides the best recall/latency trade-off for in-memory indices and is relatively simple to implement and tune.
• Implementation: A popular choice for vector databases and libraries like FAISS and Weaviate.

This is a two-part indexing strategy common in large-scale vector search. First, an Inverted File Index partitions the vector space into clusters (e.g., using k-means). Search is limited to the nearest clusters' centroids. Second, Product Quantization compresses vectors by splitting them into subvectors and assigning each to a centroid in a sub-codebook, drastically reducing memory footprint.

• IVF Role: Provides a coarse quantizer for fast candidate selection.
• PQ Role: Acts as a fine quantizer for compressing residuals, enabling billion-scale indices to fit in RAM.
• Combined Use: IVF-PQ is the backbone of billion-scale search in libraries like FAISS, optimizing for memory-efficient, disk-based search.

FAISS is an open-source library developed by Meta's Fundamental AI Research team for efficient similarity search and clustering of dense vectors. It provides optimized C++ implementations with Python bindings for a wide range of ANN algorithms.

• Core Functionality: Implements HNSW, IVF, Product Quantization, and their combinations, allowing engineers to choose the optimal index for their recall, speed, and memory constraints.
• GPU Support: Includes GPU-accelerated kernels for massively parallel search, reducing latency for ultra-large datasets.
• Industry Standard: A foundational tool used within vector databases and directly integrated into many machine learning pipelines for retrieval.