Vector Index

The primary reason to use a vector index is to escape the O(N) linear time complexity of brute-force search. Advanced indices achieve sub-linear scaling, often O(log N) or better, by partitioning the vector space or building navigable graph structures. This logarithmic scaling is what makes billion-scale semantic search economically viable, reducing query latency from seconds to milliseconds.

All approximate indices sacrifice a small amount of accuracy for speed. This tradeoff is quantified by Recall@K, which measures the fraction of true nearest neighbors retrieved. A well-tuned HNSW index can achieve >99% recall while searching only a tiny fraction of the dataset. The index's search parameters act as a dial, allowing operators to dynamically trade higher recall for lower latency based on application requirements.

Raw float32 vectors consume significant RAM. A vector index adds structural overhead for its graph edges, tree nodes, or codebooks. Techniques like Product Quantization (PQ) compress vectors by up to 16x, enabling billion-scale indices to fit entirely in memory. The tradeoff is quantization error, which introduces a slight degradation in recall that must be managed against the hardware cost savings.

The mutability of an index is a critical operational property. In-place indices allow inserting, deleting, and modifying individual vectors without a full rebuild, essential for dynamic catalogs. Out-of-place indices are immutable and require a complete re-indexing from scratch to incorporate new data. Graph-based structures like HNSW support in-place insertion natively, while many IVF-based indices are fundamentally batch-oriented.

An index must be constructed to optimize for a specific distance function. While Euclidean Distance (L2) and Cosine Similarity are the most common, specialized use cases require Maximum Inner Product Search (MIPS) for attention mechanisms or matrix factorization. Not all index algorithms support all metrics efficiently; ScaNN, for instance, is specifically optimized for the anisotropic nature of inner product space.

Real-world queries often combine semantic similarity with structured metadata filters. The index must support filtered ANN, where results are constrained by a WHERE clause. The integration strategy—pre-filtering (filter then search) or post-filtering (search then filter)—has profound implications for recall. Pre-filtering can miss valid results if the filter shrinks the candidate pool too aggressively, while post-filtering can return empty pages if the ANN search ignores the filter.

The foundational algorithmic paradigm that trades a small, quantifiable amount of accuracy for massive speedups in high-dimensional space. Unlike exact brute-force search, ANN algorithms use smart indexing structures to avoid computing the distance to every database vector. Key families include graph-based, clustering-based, and hashing-based approaches, each with distinct recall-performance tradeoffs.

A state-of-the-art graph-based ANN algorithm that builds a multi-layered proximity graph. Search begins in the sparsest top layer, taking long-range hops to quickly approach the query region, then descends to denser lower layers for refinement. This logarithmic scaling makes it the default choice for many production vector databases. Critical hyperparameters include M (graph degree) and efConstruction (build-time search width).

A clustering-based ANN structure that partitions the vector space into Voronoi cells using a coarse quantizer like k-means. At query time, only the most promising partitions are searched, drastically reducing distance computations. The number of probes is a critical parameter: more probes increase recall at the cost of speed. Often combined with Product Quantization (PQ) for compression in the popular IVFPQ composite index.

A powerful vector compression technique that decomposes high-dimensional vectors into smaller subvectors and quantizes each independently using a distinct codebook. This dramatically reduces memory footprint, enabling billion-scale datasets to fit in RAM. Distance calculations are performed using pre-computed lookup tables via Asymmetric Distance Computation (ADC) for higher accuracy.

The dominant distance metric in semantic search, measuring the cosine of the angle between two vectors. It captures orientation similarity independent of magnitude, making it robust to variations in embedding vector length. Values range from -1 (diametrically opposed) to 1 (identical direction). Essential for comparing text embeddings where semantic meaning is encoded in direction.

The standard evaluation metric for ANN index quality, measuring the fraction of true nearest neighbors found within the top K retrieved results. A Recall@10 of 0.95 means 95% of the exact top-10 neighbors were captured. This metric directly quantifies the accuracy loss introduced by approximate search and is the primary dial traded against query latency.