How ScaNN Uses Anisotropic Vector Quantization for AI

This article provides a comprehensive overview of how Google's Scalable Nearest Neighbors (ScaNN) algorithm optimizes Maximum Inner Product Search (MIPS) in artificial intelligence applications. By moving away from traditional reconstruction-based compression, ScaNN introduces anisotropic vector quantization to drastically improve search recall and speed. The core mechanism behind this breakthrough involves decomposing quantization error into two parts and heavily penalizing parallel error over orthogonal error, directly aligning the data compression process with the mathematical goals of inner product calculations.

Understanding Maximum Inner Product Search (MIPS)

In modern artificial intelligence, machine learning models frequently convert complex data—such as text, audio, and user preferences—into high-dimensional numerical vectors called embeddings. Finding the most relevant results for a user query requires calculating the inner product (or dot product) between a query vector and millions or billions of database vectors. This process is known as Maximum Inner Product Search (MIPS).

Calculating the exact inner product across billions of vectors in real-time is computationally too expensive. To solve this, AI systems use Vector Quantization (VQ). VQ compresses the database vectors into smaller representations (codewords), allowing the system to estimate the inner products rapidly without scanning the full, uncompressed dataset.

The Flaw in Traditional Vector Quantization

Traditional quantization methods, such as Product Quantization (PQ) and k-means clustering, are isotropic. This means they treat errors in all spatial directions equally.

When compressing a database vector \(x\) into a quantized approximation \(\tilde{x}\), traditional methods aim to minimize the Euclidean distance between \(x\) and \(\tilde{x}\). The assumption is that if \(\tilde{x}\) is as physically close to \(x\) as possible in the vector space, the inner product between a query \(q\) and \(\tilde{x}\) will be a good estimate of the true inner product between \(q\) and \(x\).

However, ScaNN researchers realized that minimizing the distance between the original vector and the compressed vector is not the optimal way to preserve the accuracy of the inner product.

Parallel Error vs. Orthogonal Error

To understand why isotropic quantization fails to optimize MIPS, ScaNN breaks the quantization error (\(x - \tilde{x}\)) into two distinct geometric components relative to the original vector \(x\):

Parallel Error: The component of the quantization error that lies in the exact same direction (parallel) as the original vector \(x\). This error changes the magnitude (length) of the vector.
Orthogonal Error: The component of the quantization error that runs perpendicular (orthogonal) to the original vector \(x\). This error shifts the angle of the vector slightly without drastically altering its projection along its original path.

In MIPS, we care about the pairs of queries and database vectors that yield the highest inner products. Mathematically, the inner product of two vectors is highest when the vectors are aligned in the same direction. Therefore, for the most relevant results, the query vector \(q\) and the database vector \(x\) are nearly parallel.

Why Parallel Error Matters More

Because the query vector \(q\) and a relevant database vector \(x\) are nearly parallel, the two types of quantization errors impact the inner product calculation very differently:

When \(q\) is parallel to \(x\), orthogonal error in \(\tilde{x}\) is also perpendicular to \(q\). The inner product of two perpendicular vectors is zero. Consequently, orthogonal error cancels out and has almost no impact on the final inner product score.
Conversely, parallel error in \(\tilde{x}\) runs directly along the path of \(q\). When you calculate the inner product, this error is multiplied by the full magnitude of the query vector.

Therefore, parallel error severely distorts the inner product of the most relevant search results, leading to poor ranking and degraded AI performance. Orthogonal error is largely harmless to the final score of top-ranking candidates.

How ScaNN Implements Anisotropic Vector Quantization

ScaNN (Scalable Nearest Neighbors) solves this problem by replacing traditional isotropic quantization with anisotropic vector quantization. "Anisotropic" means having different properties in different directions.

Instead of using a standard loss function that penalizes all error directions equally, ScaNN uses a custom loss function during the quantization training phase. This loss function applies a heavy mathematical weight to the parallel error and a much lighter weight to the orthogonal error.

During the compression of the database vectors, ScaNN actively sacrifices overall geometric accuracy to protect the parallel alignment. It allows the quantized vector \(\tilde{x}\) to drift quite far from the original vector \(x\) in the perpendicular direction, provided that doing so minimizes the error in the parallel direction.

If you were to visualize the error tolerance around a vector in traditional quantization, it would look like a sphere (equal tolerance in all directions). In ScaNN, the error tolerance looks like a flat pancake or a disc oriented perpendicular to the vector—wide tolerance for orthogonal drift, and razor-thin tolerance for parallel drift.

The Impact on Artificial Intelligence

By prioritizing parallel error over orthogonal error, ScaNN fundamentally changes how vector compression works for AI. Even though ScaNN's compressed vectors might technically be "further away" from the original vectors in standard Euclidean space compared to traditional methods, they produce vastly more accurate inner product estimates for the queries that matter most.

This allows AI systems, such as large language models, recommendation engines, and semantic search platforms, to compress their vector databases much more aggressively. The result is a massive reduction in memory usage and a significant increase in search speed, all while maintaining the high recall accuracy required for state-of-the-art artificial intelligence.