SCANN (Scalable Nearest Neighbors)

Anisotropic Vector Quantization (AVQ) is SCANN's core compression technique. Unlike standard Product Quantization (PQ), which assumes uniform variance across dimensions, AVQ learns a rotation of the vector space that aligns the principal components with the quantization axes. This allows it to allocate more bits to dimensions with higher variance, significantly reducing quantization error for the same compression rate. This leads to more accurate distance approximations, which is critical for maintaining high recall in compressed searches.

The Tree-AH index is SCANN's hierarchical search structure. It combines a tree-based index for coarse partitioning with an asymmetric distance computation (ADC) stage for fine-grained scoring.

• Tree Partitioning: The dataset is recursively partitioned using a balanced tree, enabling logarithmic-time traversal to narrow the search to a leaf node.
• Asymmetric Hashing: Within each leaf partition, database vectors are compressed using AVQ, while the query remains in full precision. Distances are computed asymmetrically between the full-precision query and the quantized database vectors, maximizing accuracy. This two-stage design provides an excellent balance between search speed and recall.

SCANN is specifically engineered for the Maximum Inner Product Search (MIPS) problem, which is fundamental to recommendation systems and retrieval where similarity is defined by dot product. It handles this by:

• Transforming MIPS into a cosine similarity search on unit vectors, which is equivalent under certain constraints.
• Utilizing its AVQ and Tree-AH design to efficiently approximate and rank inner products.
• Providing configurable reordering stages that use exact distances on a shortlist of candidates to guarantee final result accuracy. This makes it superior to algorithms primarily optimized for Euclidean distance (L2) when inner product is the target metric.

To bridge the gap between approximate and exact results, SCANN employs a sophisticated reordering strategy. After the Tree-AH index retrieves an initial candidate set, a brute-force re-ranking step is performed:

• A subset of the top candidates (e.g., top 1000) is extracted.
• Exact distances (inner product or cosine) are computed between the full-precision query and the full-precision versions of these candidate vectors.
• The final results are sorted based on these exact scores. This score-aware process ensures the final output's Recall@k is extremely high, often matching near-exact search quality, while the bulk of the work is done efficiently via the approximate index.

A defining feature of SCANN is its exceptional performance on batched queries. Its algorithms are designed for modern hardware, leveraging:

• SIMD (Single Instruction, Multiple Data) instructions for parallel distance computations.
• Efficient memory access patterns during tree traversal and AVQ table lookups.
• Multithreading to process multiple queries or index partitions concurrently. This architecture allows it to achieve orders-of-magnitude higher queries per second (QPS) compared to algorithms optimized for single-query latency, making it ideal for serving environments where high throughput is critical.

SCANN provides multiple levers to tune the trade-off between search latency and recall accuracy, allowing engineers to match performance to application requirements. Key hyperparameters include:

• Leaves to Search: The number of leaf partitions (from the tree) to probe during query time. Increasing this number improves recall but increases latency.
• Reordering Budget: The number of candidates to re-score with exact distances. A larger budget improves final accuracy.
• AVQ Configuration: The number of bits and subspaces used for quantization, affecting both memory footprint and approximation quality. By adjusting these, SCANN can be configured for ultra-low-latency serving or for high-accuracy offline batch retrieval.

SCANN is engineered for Maximum Inner Product Search (MIPS), the core mathematical operation behind user-item matching in recommendation engines. Its anisotropic vector quantization is optimized for the angular geometry of inner product spaces, unlike algorithms designed purely for Euclidean distance.

• High Throughput: Achieves millions of queries per second on a single machine, critical for serving recommendations to massive user bases.
• High Recall: Maintains >99% recall for top-k retrieval, ensuring users see the most relevant items.
• Example: Retrieving candidate products from a catalog of 100M+ embeddings for real-time personalization.

For RAG pipelines and semantic search engines, SCANN provides fast, accurate retrieval of text chunks based on cosine similarity of their embeddings. Its tree-AH (Asymmetric Hashing) index allows for efficient filtering of billions of passages.

• Low Latency: Delivers sub-10ms p95 latency for retrieving context from a billion-scale vector index, keeping overall LLM response time low.
• Accuracy: High recall ensures the retrieved context is relevant, directly reducing the chance of LLM hallucinations.
• Use Case: Grounding enterprise chatbots by searching internal knowledge bases of documentation, tickets, and transcripts.

Modern search has moved beyond keywords to dense retrieval, where queries and documents are encoded into vectors. SCANN's scalability handles web-scale corpora where traditional inverted indexes struggle with semantic matching.

• Hybrid Readiness: Works efficiently alongside traditional keyword (sparse) indexes for hybrid scoring.
• Memory Efficiency: Product Quantization compression reduces the memory footprint by 4x-8x, enabling larger datasets to reside in RAM.
• Example: Powering the "similar documents" or "semantically related news" features for large content platforms.

Systems that need to search across modalities—like finding images with a text query, or audio matching a video clip—rely on cross-modal embeddings in a shared vector space. SCANN's high-dimensional efficiency is key.

• Unified Index: Can index embeddings from different encoders (CLIP for image-text, AudioCLIP for audio) into a single, searchable space.
• High-Dimensional Performance: Maintains performance in spaces of 512 to 2048 dimensions, common for modern multi-modal models.
• Application: Building media libraries where users can search using natural language descriptions of visual or auditory content.

Identifying near-identical items in massive datasets, such as duplicate product listings, plagiarized content, or redundant user profiles, requires finding vectors with near-perfect similarity. SCANN's precision at the top of the result list is ideal.

• High Precision @1: Optimized to find the single closest match with extreme accuracy.
• Batch Processing: Efficiently processes large batch queries for offline deduplication pipelines.
• Real-World Scale: Used to deduplicate web-scale image datasets or user-generated content platforms with billions of items.

In domains like molecular similarity search for drug discovery or facial recognition, datasets are enormous and vectors are high-dimensional. SCANN's algorithmic optimizations provide a practical balance of speed and accuracy where exact search is computationally impossible.

• Structured Data: Excels with vectors that have inherent geometric structure, such as chemical compound fingerprints or biometric templates.
• Reproducible Research: As a library from Google Research, it is built for rigorous, reproducible benchmarking common in scientific computing.
• Example: Searching a database of 1B+ molecular embeddings to find potential drug candidates similar to a known effective compound.