Google ScaNN

01 · CONTEXT

When to search by meaning

This case starts from a July 2020 Google Research post that presents ScaNN, a vector similarity search library, and the paper "Accelerating Large-Scale Inference with Anisotropic Vector Quantization", which describes the compression technique behind it.

Embedding search serves queries that depend on meaning rather than on easily indexed fields. ML models turn text and images into high-dimensional vectors in which similar inputs end up close together, and this is the starting point of search systems vector search.

In the two-tower model, one neural network maps the query and another maps the database items to the same space. To answer, the system maps the query and then looks for the closest ones among all the database embeddings.

1. The application sends the query, for example a text, to the search API.

2. The API passes the query to the query tower, which maps it to the embedding space.

3. The item tower maps the database items to the same space, and the resulting vectors are stored.

4. The index receives the query embedding and looks for the closest ones among the database embeddings.

02 · THE PROBLEM

Finding neighbors at scale

A common way to measure similarity between query and items is the inner product, and nearest-neighbor search under this criterion is called maximum inner-product search, or MIPS. The set of embeddings is usually too large for exhaustive search, and high dimensionality makes it hard to prune candidates.

With databases of millions or billions of items, MIPS is usually the inference speed bottleneck and exhaustive search is impractical. This leads to approximate algorithms, which trade a little accuracy for a large speed gain over brute force.

03 · COMPRESSION

Quantization that targets MIPS

Several state-of-the-art MIPS solutions compress the database items to compute an approximation of the inner product in a fraction of the brute-force time. In learned quantization, a codebook of vectors is trained from the database and used to approximately represent its elements.

Earlier schemes quantized to minimize the average distance between each vector and its quantized form. The post observes that this is not equivalent to optimizing search accuracy, and that encodings with a larger average distance can give higher MIPS accuracy.

The reason is the direction of the error. The error parallel to the vector is more harmful because it disproportionately affects the high inner products, the ones MIPS wants to estimate well. That is why the technique, called anisotropic quantization, penalizes this error more and accepts larger errors in the low inner products.

1. The database vectors feed the training of a codebook, the set of vectors used to represent them approximately.

2. The loss used in training penalizes the error parallel to the original vector more.

3. The quantizer represents each database vector by a codebook center, and the compressed index keeps these representations.

4. At query time, the estimator computes approximate inner products over the compressed representations, in a fraction of the brute-force time.

5. The estimates feed the selection of the best items; anisotropic quantization improves precisely the estimation of the inner products likely to be among the best.

04 · RESULT

Speed versus accuracy

The post measures the result on an ann-benchmarks benchmark, glove-100-angular: ScaNN outperformed eleven other vector similarity search libraries, handling about twice as many queries per second, for a given accuracy, as the second fastest.

Accuracy is measured by recall@k, a common accuracy metric for nearest-neighbor search. The post shows ScaNN consistently performing better at several points of the speed-accuracy trade-off.

05 · LESSONS

What to take into the interview

The authors see anisotropic quantization as an example of a gain obtained by optimizing the algorithm for the final objective, search accuracy, and not for an intermediate goal such as compression distortion.

In a vector search design, it is worth stating what recall the product requires, what speed it needs, and how vector compression changes that trade-off. Choosing the compression error metric based on the search task is the central lesson of this case.