ScaNN

Unlike traditional Product Quantization (PQ) which minimizes reconstruction error uniformly, ScaNN's anisotropic quantization explicitly optimizes for the preservation of inner product scores. It learns a quantization codebook that allocates more precision to vector components with higher variance, recognizing that not all dimensions contribute equally to the dot product. This is critical for MIPS workloads where the magnitude of the query-database interaction matters. The technique reduces quantization error along dimensions that most impact the inner product, yielding higher recall at equivalent compression ratios compared to isotropic methods.

ScaNN introduces a novel score-aware quantization loss function that directly penalizes errors in the approximated inner product rather than Euclidean distance. The loss is formulated as:

• Minimizing the difference between the true dot product and the quantized dot product
• Weighting the loss by the query distribution to focus on high-probability query regions
• Jointly optimizing the coarse and fine quantization codebooks end-to-end This design ensures that the compressed vectors maintain the correct ranking order when scored against typical queries, directly optimizing for the Recall@K metric used in production retrieval systems.

ScaNN combines an Inverted File Index (IVF) for coarse partitioning with anisotropic quantization for fine-grained compression in a two-level structure:

• Level 1 (Coarse Quantizer): Partitions the vector space into Voronoi cells using K-means clustering, assigning each database vector to its nearest centroid
• Level 2 (Fine Quantizer): Applies anisotropic quantization to the residual vectors (the difference between the original vector and its assigned coarse centroid)
• Asymmetric Distance Computation (ADC): Queries remain in full precision while only database vectors are compressed, yielding higher accuracy than symmetric approaches This architecture enables sub-linear search complexity while maintaining high fidelity for inner product ranking.

Standard ANN algorithms optimized for Euclidean distance or cosine similarity perform poorly on Maximum Inner Product Search (MIPS) because inner product is not a metric—it violates the triangle inequality. ScaNN addresses this with:

• Query-dependent pruning: Dynamically adjusts search radii based on the query vector's magnitude, since high-magnitude queries require exploring more partitions
• Inner product upper bound estimation: Computes tight theoretical upper bounds on the maximum possible inner product within each Voronoi cell to safely prune unpromising partitions
• Adaptive candidate selection: Varies the number of coarse partitions searched based on the query's norm, balancing speed and recall per-query This makes ScaNN particularly effective for attention mechanisms and matrix factorization models where MIPS is the core operation.

ScaNN leverages SIMD (Single Instruction, Multiple Data) instructions extensively to parallelize the inner product computations that dominate search latency:

• Uses AVX2 and AVX-512 instruction sets on x86 processors for 8-way or 16-way parallel floating-point operations
• Implements cache-friendly memory layouts that store quantized codes contiguously to maximize cache line utilization
• Batches distance computations across multiple query vectors simultaneously for amortized throughput gains
• Achieves sub-millisecond latency per query on billion-scale datasets when deployed on optimized hardware These low-level optimizations are critical for production deployments requiring high queries-per-second throughput.

ScaNN is designed to serve as the fast candidate generation stage in a two-stage retrieval pipeline:

• Stage 1: ScaNN retrieves a candidate set (e.g., top-1000) using quantized vectors with high recall
• Stage 2: A more expensive re-ranking step computes exact inner products on the full-precision vectors for the candidate set only
• The anisotropic quantization ensures that the true top-K results are included in the candidate set with high probability, minimizing recall loss
• Configurable tradeoff: Adjust the number of coarse partitions searched and the candidate set size to balance latency against Recall@K targets This architecture is the standard pattern for production semantic search systems requiring both speed and accuracy.

The core innovation of ScaNN. Unlike standard quantization that minimizes reconstruction error, anisotropic quantization explicitly optimizes the quantization process to preserve the inner product between the query and database vectors. It learns a quantization distortion that penalizes errors parallel to the original vector direction more heavily than orthogonal errors, ensuring the dot product score—critical for Maximum Inner Product Search (MIPS)—remains highly accurate even after aggressive compression.

The baseline compression technique that ScaNN improves upon. PQ decomposes a high-dimensional vector into smaller subvectors and quantizes each independently using a distinct codebook. While PQ minimizes reconstruction error (how close the compressed vector is to the original), it is agnostic to the final search metric. ScaNN modifies this by scoring quantization centroids based on their impact on the dot product rather than Euclidean distance, achieving higher recall for MIPS at the same compression ratio.

The custom loss function that differentiates ScaNN from traditional vector compression. Standard quantization minimizes ||x - ilde{x}||^2. ScaNN's loss function is ||x - ilde{x}||^2 + \lambda \cdot f(\langle q, x angle, \langle q, ilde{x} angle), where the second term explicitly penalizes discrepancies in the inner product score. This score-aware optimization ensures that the relative ordering of database vectors by relevance to a query is preserved, even when the absolute vector reconstruction is imperfect.

ScaNN combines its anisotropic quantization with an Inverted File Index (IVF) for coarse partitioning. The vector space is first partitioned into Voronoi cells using a coarse quantizer. During search, only the most promising partitions are visited. Within each partition, the residual vectors are compressed using ScaNN's anisotropic PQ. This two-level approach dramatically reduces the number of distance computations, while the anisotropic compression ensures high recall within the probed partitions.

The efficient distance approximation scheme used at query time. The query vector remains in full precision, while only the database vectors are compressed via anisotropic quantization. The inner product is approximated by computing the dot product between the uncompressed query and the quantized database vectors using pre-computed lookup tables. This asymmetry yields significantly higher accuracy than symmetric computation (where both are compressed) and is a key factor in ScaNN's state-of-the-art recall-speed Pareto frontier.