Source-linked AI summary
Quantization based Fast Inner Product Search
Ruiqi Guo, Sanjiv Kumar, Krzysztof Choromanski, David Simcha
TL;DR
Large-scale MIPS is costly to solve by linear scan, particularly when vector norms vary. This paper learns subspace quantizers directly for inner-product approximation and adds an optional query-informed learning procedure. QUIP outperforms state-of-the-art techniques across recommendation and deep-learning classification datasets, while its concentration results depend on stated assumptions.
Problem
Exact MIPS by linear scan costs O(nd), and varying database-vector norms prevent reducing the problem to ordinary L2 or angular nearest-neighbor search.
Source: §1 · p. 1Method
QUIP quantizes database vectors in multiple subspaces using codebooks learned to minimize inner-product error, with optional constraints from example queries.
Source: §1 · p. 1, §3.1 · p. 4Results
Across four recommendation and deep-learning classification datasets, QUIP consistently outperforms state-of-the-art techniques under fixed-space and fixed-time scenarios.
Source: §1 · p. 2Takeaways & Limitations
The reported advantage holds across retrieval and classification tasks, and the paper presents tree-quantization hybrids as a way to further accelerate search for very large databases.
Source: §6 · p. 8, §7 · p. 9The paper's exponential concentration results require boundedness and balancedness conditions on datapoints; stronger bounds also assume independent subspaces.
Source: §4 · p. 6, §8.2.2 · p. 13
Abstract
from arXiv · showhide
We propose a quantization based approach for fast approximate Maximum Inner Product Search (MIPS). Each database vector is quantized in multiple subspaces via a set of codebooks, learned directly by minimizing the inner product quantization error. Then, the inner product of a query to a database vector is approximated as the sum of inner products with the subspace quantizers. Different from recently proposed LSH approaches to MIPS, the database vectors and queries do not need to be augmented in a higher dimensional feature space. We also provide a theoretical analysis of the proposed approach, consisting of the concentration results under mild assumptions. Furthermore, if a small sample of example queries is given at the training time, we propose a modified codebook learning procedure which further improves the accuracy. Experimental results on a variety of datasets including those arising from deep neural networks show that the proposed approach significantly outperforms the existing state-of-the-art.
1 Introduction
MIPS seeks database vectors with the largest query inner products, but exact linear scans become prohibitive at scale. QUIP addresses this by learning quantizers that minimize inner-product approximation error, with query-informed training and strong benchmark results.
1 Introduction
- Linear scans require O(nd) time and space, motivating compressed approximate search for large databases.MIPS supports retrieval and classification tasks, including recommendation over large inventories.Source: §1 · p. 1
- When database-vector norms vary, MIPS is challenging and does not reduce to L2 or angular nearest-neighbor search.The paper considers both database and query vectors with arbitrary norms.Source: §1 · p. 1
- QUIP learns codebooks by directly minimizing inner-product quantization error.A constrained learning framework can further improve accuracy when example queries are available.Source: §1 · pp. 1–2
- Across four recommendation and deep-learning classification datasets, QUIP consistently outperforms state-of-the-art methods under fixed-space and fixed-time budgets.The experiments cover Movielens, Netflix, ImageNet, and VideoRec.Source: §1 · p. 2
2 Related works
Prior MIPS approaches include randomized sampling, modified tree search, and transformations that recast MIPS as nearest-neighbor search. QUIP instead takes a quantization-based approach and reports better accuracy under fixed-space and fixed-time budgets.
2 Related works
- Earlier work used randomized sampling, modified tree-based search, or transformed MIPS into L2 nearest-neighbor search.The transformed approaches include PCA-Tree and ALSH.Source: §2 · p. 2
- ALSH maps database vectors and queries asymmetrically into a higher-dimensional space, where MIPS becomes L2 nearest-neighbor search as m approaches infinity.A later variant represents transformed vectors as binary codes and uses Hamming distance.Source: §2 · p. 2
- QUIP takes a quantization-based view and reports better accuracy than prior approaches under fixed-space and fixed-time budgets.The cited symmetric-transformation approach restricts queries to unit norm.Source: §2 · p. 2
3 Quantization-based inner product (QUIP) search
QUIP partitions permuted vectors into subspaces, quantizes database blocks, and approximates inner products by combining their quantized contributions. Its codebooks are learned to reduce inner-product error, with an optional query-informed objective that favors correct top-dot-product retrieval.
3 Quantization-based inner product (QUIP) search
- QUIP permutes vector elements and chunks vectors into subspaces, where each database block is represented by a codebook entry.Random rotation is another possible subspace construction and offers improved theoretical guarantees, at somewhat greater cost.Source: §3 · pp. 2–3
- The inner-product approximation is unbiased when each subspace codebook entry is the mean of its assigned database vectors.The paper states that this condition holds for the learned quantizers.Source: §3 · p. 3, §3.1 · p. 4
3.1 Learning quantization codebooks from database
- With database vectors alone, codebook learning minimizes expected squared inner-product error using a modified k-Means objective.Assignments use Mahalanobis distance specified by the non-centered query covariance matrix.Source: §3.1 · pp. 3–4
- Without training query samples, the method may assume query and database vectors share a covariance matrix; the paper reports this version performs reasonably well.With example queries, the covariance can instead be estimated from those samples.Source: §3.1 · p. 4
3.2 Learning quantization codebook from database and example query samples
- With example queries, additional constraints favor assigning the top-dot-product database vector a quantizer with higher query dot product than competing quantizers.The example queries differ from the actual queries used at test time.Source: §3.2 · p. 4
- The query-informed procedure relaxes its constraints with slack variables and alternates codebook and assignment updates.When no constraints are violated, its assignment step reduces to nearest-neighbor search in the same Mahalanobis space used in the database-only procedure.Source: §3.2 · pp. 4–5
4 Theoretical analysis
The analysis bounds the chance that quantized inner products substantially misestimate large exact inner products, under stated balance and martingale conditions. It also relates random chunking to balanced subspaces and shows the failure probability decreases exponentially with the number of blocks.
4 Theoretical analysis
- Randomly permuting vector entries preserves dot products and makes the permuted vector 1-balanced in expectation.The paper also notes that a fixed random rotation preserves dot products and can provide an even better balancedness property.Source: §4 · p. 5
- The probability of a large relative error for a large exact inner product decreases exponentially with the number of subspaces when the stated assumptions hold.The theorem assumes bounded data around a center, η-balanced centered vectors, and a martingale condition; it establishes the existence of codebooks meeting the bound.Source: §4 · pp. 5–6
- Under the stronger assumption that subspaces are independent, the analysis uses the Berry–Esseen inequality to obtain a stronger upper bound.This independence condition is more restrictive than the martingale assumption used for the preceding theorem.Source: §4 · p. 6
5 Experimental results
Experiments compare QUIP variants with LSH baselines on recommendation and deep-learning classification datasets under fixed-bit and fixed-time settings. Quantization-based methods outperform LSH, and QUIP-opt performs best among the quantization variants when example queries are available.
5 Experimental results
- The experiments cover Movielens and Netflix recommendation, ImageNet classification, and VideoRec recommendations, with retrieval evaluated at task-specific top-k cutoffs.The datasets include deep-network embeddings or classifier weights for ImageNet and VideoRec.Source: §5 · p. 6
- QUIP-cov(x) uses database vectors for codebook learning, QUIP-cov(q) uses held-out queries, and QUIP-opt applies constrained optimization.QUIP-opt's constraints steer learning toward retrieving maximum-dot-product neighbors as well as minimizing quantization error.Source: §5 · pp. 6, 8
- Fixed-bit tests use 64, 128, 256, or 512 bits; fixed-time tests increase LSH bit counts threefold because POPCNT is two to three times faster than table lookup.QUIP uses 8 bits per subspace, with the number of subspaces varied to set the total bit count.Source: §5 · pp. 6, 8
- Quantization methods outperform LSH baselines on all four datasets under fixed-bit and fixed-time comparisons; QUIP-opt beats the other QUIP variants when example queries are available.In fixed-time tests, quantization methods use three times fewer bits than LSH, reducing memory footprint.Source: Figure 1 · p. 7, §5 · p. 8, Figure 2 · p. 8
6 Tree-Quantization Hybrids for Large Scale Search
Tree-quantization hybrids combine recursive data partitioning with QUIP within each partition to reduce the linear-scan burden of quantization search. On VideoRec, they substantially accelerate search while retaining comparable fixed-bit accuracy and improving fixed-time accuracy over non-hybrid methods.
6 Tree-Quantization Hybrids for Large Scale Search
- The hybrid method applies QUIPS within partitions formed by a locality-preserving tree, typically a shallow tree with a few thousand points per leaf.At query time, soft assignment to multiple partitions addresses errors from hard partitioning; flat k-means partitioning is also possible.Source: §6 · p. 8
- At 512 bits, tree-quantization hybrids have nearly the same precision-recall accuracy as non-hybrid methods while running about six times faster.In the fixed-time comparison, hybrids return much better results at the same 2.256 ms retrieval budget.Source: Figure 3 · p. 9, §6 · p. 9
- 42.81x overall end-to-end speedup over brute-force search is reported for Tree-QUIP, including a 5.97x additional speedup over QUIPS on VideoRec.The non-hybrid quantization approaches alone reduce search time by a factor of 7.17 versus brute force.Source: §6 · pp. 8–9, Figure 3 · p. 9
- The reported VideoRec hybrid uses 2,000 partitions and assigns each query to the 100 nearest partitions by dot product with their centers.This configuration underlies the reported hybrid speedups.Source: §6 · p. 9
7 Conclusion
The conclusion presents QUIP as a fast approximate inner-product search method based on codebooks learned across multiple subspaces. It reports advantages over existing techniques and identifies theoretical analysis of constrained optimization and joint tree-codebook training as future work.
7 Conclusion
- QUIP uses codebooks learned across multiple subspaces for fast approximate inner-product search.The conclusion describes a k-means-like variant and constrained quantization-error minimization that produces codebooks tuned to highest-dot-product search.Source: §7 · p. 9
- Experiments on retrieval and classification tasks show advantages over existing techniques.The conclusion characterizes the experiments as extensive but does not provide additional numerical results here.Source: §7 · p. 9
- Future work includes analyzing guarantees for constrained optimization and jointly training tree partitions with quantization codebooks.The hybrid approach currently trains tree partitioning and codebooks separately.Source: §7 · p. 9
8 Appendix
The appendix adds ImageNet and VideoRec retrieval curves and proofs concerning balancedness and concentration for the quantization-based method. Its theoretical results examine random rotation, concentration without boundedness or balancedness, and tighter bounds under independent blocks.
8.1 Additional Experimental Results
- Figure 4 presents precision–recall curves on ImageNet and VideoRec, while Figure 5 presents recall against the percentage of database points returned.Figure 5 uses 512 bits for most methods, but 1536 bits for Signed ALSH-FixedTime, L2 ALSH-FixedTime, and Simple LSH-FixedTime; PCA-Tree performs poorly on the stated 150–1025-dimensional datasets.Source: §8.1 · p. 9, Figure 4 · p. 10, Figure 5 · p. 11
8.2.1 Vectors’ balancedness - proof of Theorem 4.1
- Random normalized Hadamard rotation preserves dot products, and the appendix reports that the balancedness failure probability decreases exponentially as the number of blocks K increases.The appendix also establishes that the transformed vector is 1-balanced in expectation.Source: §8.2.1 · pp. 12–13
8.2.2 Proof of Theorem 4.2
- Theorem 4.2’s concentration result does not require boundedness or balancedness, and minimizing its objective minimizes the variance of the quantized dot-product discrepancy.The proof relates the objective to the variance of the error for each fixed block.Source: §8.2.2 · pp. 13–15
8.2.3 Independent blocks - the proof of Theorem 4.3
- When dimensions in different blocks are independent, the analysis can strengthen its concentration inequalities; the appendix treats this as an assumption that may be reasonable in practice.The proof first considers the general case without assuming balancedness.Source: §8.2.3 · p. 15