ScaNN

ScaNN (Scalable Nearest Neighbors) is a vector-search library developed at Google Research, open-sourced in 2020 and described in the Guo, Sun, Lindgren, Geng, Simcha, Chern, Kumar 2020 ICML paper “Accelerating Large-Scale Inference with Anisotropic Vector Quantization”. ScaNN’s headline contribution is anisotropic vector quantization — a refinement of Product Quantization that explicitly accounts for the direction of similarity (relevant for inner-product search where the goal is to maximize a directional inner product, not minimize an isotropic Euclidean distance) rather than treating quantization error symmetrically. The result is substantially better recall on inner-product search benchmarks at the same query budget compared to standard PQ. ScaNN is the engine behind Google’s vertex AI Matching Engine (the managed vector search service) and is used internally for many of Google’s deep-retrieval applications. In the recommender systems setting, ScaNN is one of the two leading open-source ANN libraries (the other is FAISS) and is particularly favored for two-tower retrieval because of its specialization for inner-product search.

1. Why Anisotropic Quantization

Standard Product Quantization minimizes the isotropic Euclidean distance between the original vector and its quantized representation: min ||v − v̂||². This treats all directions of error equally.

For Maximum Inner Product Search (MIPS) — the dominant problem in two-tower retrieval, where the score is the dot product q · v — the isotropic objective is misaligned with the actual goal. The reason: an error in the direction of the query (parallel to q) directly affects the dot product, while an error perpendicular to q does not. Optimizing isotropically wastes some quantization capacity on perpendicular errors that don’t matter.

ScaNN’s anisotropic quantization optimizes a weighted objective that puts more emphasis on parallel errors (which affect the inner product) than on perpendicular errors (which do not). The exact weighting depends on the distribution of query vectors. The result: for the same number of bytes per vector, anisotropic quantization preserves inner-product rankings substantially better than isotropic quantization.

The 2020 paper reports approximately 2× speedup at the same recall versus the prior state of the art (FAISS’s IVF-PQ). The advantage is particularly pronounced for high-recall regimes where the small differences in quantization quality compound.

2. The Architecture

ScaNN’s architecture combines several techniques:

Partitioning — typically a coarse IVF-style partitioning to narrow the search to a subset of the database per query.

Scoring within partitions — anisotropic vector quantization (AVQ) for compressed distance computation, or full-precision computation for smaller indexes.

Reranking (optional) — after finding the top-K candidates via the compressed distance, optionally re-rank using full-precision vectors for the very top results. This trades a small amount of latency for accuracy.

The same composite-index approach used by FAISS (IVF + PQ + reranking), with the PQ replaced by anisotropic quantization.

3. The ScaNN API

import scann
 
# Build the index for a numpy array of database vectors.
searcher = scann.scann_ops_pybind.builder(
    db_vectors,
    num_neighbors=10,            # default top-K
    distance_measure="dot_product"
).tree(
    num_leaves=2000,             # number of IVF partitions
    num_leaves_to_search=100,    # n_probe equivalent
    training_sample_size=250000  # sample for k-means training
).score_ah(
    dimensions_per_block=2       # anisotropic quantization parameter
).reorder(
    reordering_num_neighbors=100 # rerank top-100 with full precision
).build()
 
# Query
neighbors, distances = searcher.search_batched(query_vectors)

The fluent API explicitly composes the partitioning, scoring, and reranking stages. The score_ah step is the anisotropic quantization (AH = “asymmetric hash”). Defaults are reasonable for most use cases.

4. When to Use ScaNN

ScaNN is appropriate when:

• You need maximum-inner-product search (typical for Two-Tower Retrieval Model retrieval).
• You want the best recall at a given byte budget.
• Inference is on CPU (ScaNN is highly CPU-optimized; FAISS has stronger GPU support).
• You can integrate a Python/C++ library into your serving stack.

For generic Euclidean nearest-neighbour search, FAISS’s standard PQ may be equally good. The ScaNN advantage is specifically for inner-product (and cosine) search.

5. Strengths

• Best-in-class recall for inner-product search at given byte budget.
• CPU-optimized for production serving.
• Production-proven at Google.
• Supports the same composite-index pattern as FAISS (IVF + PQ + reranking).

6. Weaknesses

• Less feature-complete than FAISS — fewer index types, smaller community.
• GPU support more limited than FAISS.
• Tuning anisotropic parameters requires care.

7. See Also

• FAISS — alternative ANN library
• Product Quantization — the technique ScaNN refines
• Inverted File Index — coarse partitioning component
• HNSW — graph-based ANN alternative
• Two-Tower Retrieval Model — primary recommender consumer
• Recommender Algorithms Catalog
• Recommender Systems