Index Memory Footprint

The core indexing algorithm dictates the fundamental memory layout. Graph-based indices like HNSW store adjacency lists for each vector node, requiring memory proportional to the number of vectors and connections. Inverted File (IVF) indices store cluster centroids and inverted lists of vector IDs, which can be more memory-efficient for large datasets. Hashing-based methods like LSH store compact hash tables. The choice directly trades off memory for query speed and accuracy.

Product Quantization (PQ) is the dominant technique for drastic memory reduction. It compresses original vectors (e.g., 1024-dimensional floats = 4KB) into short codes (e.g., 64 bytes). Memory footprint is determined by:

• Number of Subquantizers (m): Splits the vector into m sub-vectors.
• *Centroids per Subquantizer (k)**: Each sub-space has k* centroids (e.g., 256).
• Total Codebook Size: m * k* * (d/m) floats. The dataset itself is stored as integer codes, not full vectors.

Memory scales with the cardinality (N) and dimensionality (d) of the dataset.

• Cardinality (N): The total number of vectors. Memory is typically O(N), though the constant factor varies greatly (e.g., full vectors vs. PQ codes).
• Dimensionality (d): For uncompressed storage, memory is O(N * d). High d exponentially worsens the curse of dimensionality, often necessitating compression. Raw vector memory = N * d * sizeof(float).

For graph and IVF indices, configurable parameters directly control memory use.

• HNSW M / efConstruction: The M parameter sets the maximum number of bi-directional links per layer. Higher M increases recall and speed but grows memory as O(N * M).
• IVF nlist: The number of Voronoi cells (clusters). Memory stores nlist centroid vectors and the inverted lists. Larger nlist can improve search granularity but increases centroid storage and list overhead.

Beyond PQ, the numerical precision of stored data is a key lever.

• Scalar Quantization (SQ): Reduces precision of vector components from 32-bit floats to 8-bit or 4-bit integers, yielding a 4x or 8x memory reduction.
• Mixed Precision: Storing graph links or IDs in 32-bit vs. 64-bit integers.
• PQ Codebook Precision: Storing PQ centroids in FP32 vs. FP16. This creates a trade-off: lower precision saves memory but can reduce distance calculation accuracy and thus recall.

The index memory includes overhead beyond the core vectors and links.

• Vector IDs: Mapping internal indices to application IDs.
• Metadata for Filtered Search: Storing attributes for hybrid search filtering.
• Distance Lookup Tables: Pre-computed tables for Asymmetric Distance Computation (ADC) in PQ, which trade memory for faster query speed.
• Graph Entry Points: Storage for the entry nodes for each layer in HNSW. In distributed systems, overhead for sharding and replication state also contributes.

A cornerstone technique for memory-efficient indexing. PQ compresses high-dimensional vectors by splitting them into subvectors and quantizing each subspace into a small set of centroids. A vector is represented by a short code of centroid indices.

• Key Mechanism: Reduces memory footprint by 10x to 100x compared to storing full-precision (e.g., float32) vectors.
• Trade-off: Introduces quantization error, making it a lossy compression method. Distance calculations become approximate.
• Use Case: Essential for billion-scale vector databases where storing raw vectors in RAM is prohibitive.

A two-stage index that reduces search scope to save memory and compute. It uses a coarse quantizer (like k-means) to partition the dataset into Voronoi cells (a 'inverted file' of vector lists).

• Memory Impact: The primary memory cost is storing the coarse quantizer centroids and the lists of vector identifiers (or compressed vectors).
• Search Process: For a query, only vectors in the most promising cell(s) are searched, drastically cutting the number of distance computations.
• Combination: Often paired with PQ (as IVFPQ or IVFADC) to achieve both scoped search and high compression.

A graph-based ANN algorithm known for high recall and speed, but with a significant memory footprint. It constructs a multi-layered graph where each layer is a Navigable Small World (NSW) graph.

• Memory Overhead: Must store the graph connectivity (edges between nodes) in addition to the vector data. This can require 4-8x the memory of the raw vectors themselves.
• Trade-off: Delivers exceptionally fast, logarithmic-time search but is less memory-efficient than quantization-based methods like PQ.
• Optimization: Often used with vector compression (e.g., HNSW with SQ or PQ) to balance memory and accuracy.

The distance calculation method used when query vectors are raw (uncompressed) but database vectors are compressed (e.g., with PQ). It is more accurate than symmetric distance computation between two compressed vectors.

• Memory Benefit: Enables the use of highly compressed database vectors (small memory footprint) while maintaining higher query accuracy.
• Process: The query's subvectors are compared directly to the PQ codebook centroids referenced by the database vector's codes.
• Application: Core to the IVFADC index structure, combining IVF's scoped search with PQ's compression and ADC's accurate distances.

A library from Google Research optimized for Maximum Inner Product Search (MIPS). It uses anisotropic vector quantization, which learns quantization boundaries that are more aligned with the data distribution for the MIPS objective.

• Memory Efficiency: Provides state-of-the-art accuracy-per-memory-footprint for MIPS problems, common in recommendation systems.
• Mechanism: Its quantization is anisotropic (direction-sensitive), unlike PQ's axis-aligned splits, better preserving inner product relationships.
• Result: For a given memory budget, ScaNN often achieves higher recall than other quantization methods on MIPS tasks.

The fundamental engineering compromise in ANN systems. Recall measures how many true nearest neighbors are found. Precision (in system performance) relates to speed and resource use like memory.

• Memory's Role: A larger index (e.g., more PQ centroids, a denser HNSW graph) typically improves recall but increases memory footprint.
• Operational Decision: Engineers must choose an index type and parameters that fit within the available RAM while meeting the application's minimum recall requirements.
• Tuning: Parameters like nlist in IVF, M in HNSW, or m (subvectors) in PQ are directly tuned against this trade-off.