ScaNN

Overview

ScaNN, short for Scalable Nearest Neighbors, is an open-source library from Google Research for fast approximate vector similarity search. Its main target is maximum inner-product search (MIPS): given a query embedding, find the stored embeddings with the largest dot product. It also supports other distances such as squared Euclidean.

What sets ScaNN apart is how it compresses vectors. Most quantization methods try to keep every vector as close as possible to its compressed version. ScaNN instead uses anisotropic quantization, which accepts more error in directions that barely change the search result and less error in the direction that matters most. The outcome is better ranking accuracy for the same memory and speed.

An everyday analogy: when you sketch a map for a friend, you draw the main road to your house carefully and roughly scribble the side streets. Errors on the side streets do little harm. ScaNN spends its precision on the "main road" of each vector, the part that decides whether it ranks highly.

What it is

ScaNN is a C++ library with Python bindings and an optional TensorFlow integration. A search is built from up to three stages.

Brute-force scoring can also be quantized to 8-bit integers per dimension, which gives about four times compression over 32-bit floats with little accuracy loss. Asymmetric hashing is ScaNN's product-quantization-style scorer, trained with the anisotropic loss.

ScaNN is released under the Apache 2.0 licence. Its prebuilt Python wheels are for Linux on x86-64 (with AVX and FMA) and ARM64.

Where it came from

ScaNN was announced by Google Research in July 2020, alongside the ICML 2020 paper "Accelerating Large-Scale Inference with Anisotropic Vector Quantization" by Ruiqi Guo, Philip Sun and colleagues. The announcement reported that on the glove-100-angular benchmark at ann-benchmarks.com, ScaNN handled roughly twice as many queries per second as the next-fastest tuned library at the same accuracy.

The code lives in the google-research repository and is published on PyPI. Version 1.4.0, released in March 2025, stopped enabling TensorFlow integration by default; it now needs the scann[tf] extra. Version 1.4.2 followed in August 2025.

In 2023 the team presented SOAR (Spilling with Orthogonality-Amplified Residuals) at NeurIPS. Google described it in an April 2024 blog post as an improvement that adds a small amount of redundancy to the index to make search faster.

ScaNN also powers Google Cloud services. Vertex AI Vector Search uses it, and AlloyDB, Google's PostgreSQL-compatible database, offers a ScaNN index for vector search.

How it works

1. Partition the data

ScaNN runs k-means-style training to split the dataset into num_leaves partitions. At query time it picks the num_leaves_to_search partitions whose centres score best against the query. The ratio between the two controls how much data is skipped. The docs suggest num_leaves near the square root of the number of points as a starting point.

2. Score with anisotropic quantization

Inside the chosen partitions, each vector is stored as a compressed code. Think of the error between a vector and its code as having two parts: one parallel to the vector and one at right angles to it. For inner-product search, the parallel part changes the score of a high-scoring match much more. ScaNN's loss penalises parallel error more heavily, so codes preserve the scores of likely matches. Distances are then estimated with lookup tables, as in other product-quantization methods. The docs recommend dimensions_per_block = 2 for this scorer.

3. Rescore the best candidates

The top reordering_num_neighbors candidates are rescored with more precise vectors. This value must exceed the final number of results k. Raising it improves accuracy at some cost in speed.

4. Optional spilling with SOAR

Standard partitioning puts each vector in one cluster. A query can miss a true neighbour if it lines up badly with that cluster. SOAR assigns some vectors a second, backup cluster chosen so that its residual points in a different direction. If the first assignment fails for a query, the second is likely to succeed.

import scann
searcher = (scann.scann_ops_pybind.builder(dataset, 10, "dot_product")
    .tree(num_leaves=2000, num_leaves_to_search=100, training_sample_size=250000)
    .score_ah(2, anisotropic_quantization_threshold=0.2)
    .reorder(100)
    .build())
neighbors, distances = searcher.search_batched(queries)

Rules of thumb from the docs

• Under about 20,000 points: brute force.
• Under about 100,000 points: asymmetric hashing plus rescoring.
• Above that: partitioning, asymmetric hashing and rescoring.

Key concepts and terms

A worked example

This is an illustrative scenario.

An online shop has 5 million product embeddings of 256 dimensions from a two-tower recommendation model. The model was trained with dot-product scores, so the task is MIPS.

1. The team computes exact top-10 results for 2,000 sample queries using brute force. This is their ground truth.
2. Following the rules of thumb, they use partitioning: num_leaves near the square root of 5 million, about 2,000, and start with num_leaves_to_search = 100.
3. They score with score_ah(2, anisotropic_quantization_threshold=0.2) and reorder the top 100.
4. Recall@10 is below target, so they raise num_leaves_to_search to 150 and reorder 200. Recall rises; latency per query grows modestly.
5. They then compare against an HNSW index on the same queries at the same recall, and keep whichever is faster on their hardware.

The decision rests on their measurements, not on published benchmarks.

Strengths and limitations

Strengths:

• Excellent speed–accuracy trade-off for inner-product search.
• Compression designed around ranking accuracy, not reconstruction error.
• Simple builder API with clear rules of thumb.
• Backed by Google research and used in managed Google Cloud services.
• Apache 2.0 licence.

Limitations:

• Prebuilt wheels are Linux-only; other platforms need a source build.
• A library, not a database: no persistence layer, filtering service or replication.
• Fewer index types and less community tooling than FAISS.
• Designed for CPU search; teams needing GPU search usually pick other libraries.
• Large changes to the data usually call for rebuilding the index.

How it compares with alternatives

Practical guidance and best practices

1. Confirm your similarity measure. Use dot_product only if your embeddings were trained for it; otherwise normalise or use squared L2.
2. Compute exact ground truth on a sample before tuning anything.
3. Follow the size-based rules of thumb for which stages to use.
4. Set num_leaves near the square root of the dataset size, then tune num_leaves_to_search for recall.
5. Keep dimensions_per_block = 2 with asymmetric hashing, as the docs advise.
6. Always enable reordering with asymmetric hashing and set it well above k.
7. Serialise the built searcher and reload it in serving processes instead of rebuilding.
8. Plan regular rebuilds as the catalogue changes.

Common mistakes

• Using dot product on embeddings meant for cosine similarity without normalising.
• Setting reordering_num_neighbors at or below k.
• Comparing libraries without matching recall levels.
• Expecting database features such as metadata filtering out of the box.
• Installing on an unsupported platform and assuming the build will work.

Frequently asked questions

What is anisotropic quantization in simple terms?

It is a way of compressing vectors that cares about the direction of the error. Error along the vector's own direction changes its inner product with likely matches the most, so it is penalised more. Error at right angles is tolerated. This keeps rankings accurate for the same code size.

Does ScaNN only support inner product?

No. Inner product is its main use case, but it also supports squared Euclidean distance. For cosine similarity, normalise vectors and use dot product.

Does ScaNN run on GPUs?

The open-source library is designed for CPUs and its wheels rely on SIMD instructions such as AVX and NEON. If you need GPU search, libraries such as FAISS offer GPU indexes.

Do I need TensorFlow?

No. Since version 1.4.0, the default install uses native Python bindings. TensorFlow ops are available through the scann[tf] extra.

How is ScaNN related to Google Cloud?

Google reports that Vertex AI Vector Search uses ScaNN and that AlloyDB offers a ScaNN-based index. The open-source library is the same family of algorithms you can run yourself.

Glossary

• Embedding: a numeric vector representing an item or query.
• Dot product: sum of element-wise products of two vectors.
• Quantization: storing values with fewer bits using a codebook.
• Codebook: learned set of representative vectors used to encode data.
• Brute force: scoring every stored vector.
• Spilling: placing a vector in more than one partition.
• SIMD: CPU instructions that process several numbers at once.

Summary

ScaNN is Google's open-source library for fast approximate vector search, built around partitioning, anisotropic quantization and rescoring. Its key idea is to compress vectors in the way that best preserves inner-product rankings rather than overall shape. It is a strong choice for CPU-based maximum inner-product search, especially for recommendation and embedding retrieval. Treat it as a library, measure recall against exact search, and compare it fairly with alternatives at matched accuracy.

Related

It belongs to Vector indexes in my stack, under Generative AI and LLMs. Others in the same group: