PaperlayerView exact revision on arXiv

Source-linked AI summary

Accelerating Large-Scale Inference with Anisotropic Vector Quantization

Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, Sanjiv Kumar

arXiv:1908.10396v5cs.LGstat.ML

TL;DR

Traditional quantization minimizes database-point reconstruction error, although MIPS errors on high-inner-product pairs matter more to ranking. This paper proposes score-aware losses that weight those pairs and induce anisotropic quantization under stated statistical assumptions. The approach improves retrieval and inner-product estimation over reconstruction-based methods and reports strong performance on public benchmarks.

  • Problem

    Traditional quantization minimizes reconstruction error across database points, although errors on high-inner-product query–point pairs matter more to MIPS ranking.

    Source: §1 · p. 1, §3 · p. 3

  • Method

    The paper weights inner-product approximation error by a chosen function of the true inner product, producing anisotropic quantization that penalizes parallel residuals more than orthogonal ones.

    Source: §1 · p. 1, §3 · p. 3

  • Results

    The proposed method improves retrieval recall and inner-product value estimation over reconstruction-error methods and outperforms state-of-the-art baselines on public speed-recall benchmarks.

    Source: §1 · p. 2, §6 · p. 9

  • Takeaways & Limitations

    The loss is applicable across quantization methods, including product and vector quantization procedures that can be adapted to it.

    Source: §1 · p. 1

    The analysis assumes unit-norm, uniformly spherically distributed queries when their distribution is unknown; the expectation can be recomputed for a known or empirically estimated distribution.

    Source: §3 · p. 3

Abstract

from arXiv · show

Quantization based techniques are the current state-of-the-art for scaling maximum inner product search to massive databases. Traditional approaches to quantization aim to minimize the reconstruction error of the database points. Based on the observation that for a given query, the database points that have the largest inner products are more relevant, we develop a family of anisotropic quantization loss functions. Under natural statistical assumptions, we show that quantization with these loss functions leads to a new variant of vector quantization that more greatly penalizes the parallel component of a datapoint's residual relative to its orthogonal component. The proposed approach achieves state-of-the-art results on the public benchmarks available at \url{ann-benchmarks.com}.

1 Introduction

The paper argues that reconstruction error is misaligned with MIPS because errors on high-inner-product pairs matter more, and proposes score-aware quantization losses for that objective. Under natural statistical assumptions, these losses yield anisotropic weighting and improve MIPS performance on large-scale benchmarks.

1 Introduction

  • Score-aware quantization weights errors according to inner-product values, focusing more on query–database pairs with larger inner products.The authors argue that errors on these pairs matter more because they are more likely to affect search results.Source: §1 · p. 1
  • Under natural statistical assumptions, the loss can be calculated efficiently and penalizes residual error parallel to a datapoint more than orthogonal error.This produces anisotropic weighting of quantization error.Source: §1 · p. 1
  • The loss applies across quantization methods, with codebook learning and quantization procedures for product and vector quantization efficiently adapted to it.The paper describes the loss as generally applicable to many quantization methods.Source: §1 · pp. 1–2
  • The method achieves state-of-the-art performance on standard large-scale benchmarks and improves retrieval recall and inner-product value estimates over reconstruction-loss methods.The paper also reports outperforming state-of-the-art baselines on public speed-recall benchmarks.Source: §1 · p. 2

2 Background and Related Works

MIPS inference appears in recommendation and extreme classification, while practical systems combine methods that reduce the number of scored items with methods that accelerate scoring. Quantization supports efficient scoring and compact storage, and this paper distinguishes its downstream-MIPS objective from reconstruction-error objectives.

2.1 Inference as Maximum Inner Product Search

  • In recommendation and extreme classification, inference involves finding item or class embeddings with the largest inner product against a query embedding.The passage also describes MIPS applications in retrieval and scalable machine-learning tasks.Source: §2.1 · p. 2

2.2 Methods for accelerating MIPS

  • MIPS systems need both fewer scored items, typically through space partitioning, and faster scoring, typically through quantization.The paper compares with available MIPS libraries and emphasizes that both tasks matter for successful systems.Source: §2.2 · p. 2

2.2.1 Reducing the Number of Evaluations

  • Space-partitioning approaches include tree search, locality-sensitive hashing, and graph search, which navigate or partition the space to limit item evaluations.Graph search greedily selects neighbors with the highest dot product.Source: §2.2.1 · p. 2

2.2.2 Quantization

  • Lookup tables can compute dot products for quantized points in O(dk+mn) time, while quantization also reduces memory-bandwidth use and storage needs.The stated lookup-table complexity is compared with O(nd) for exact computation; smaller storage can allow more datapoints on one machine.Source: §2.2.2 · pp. 2–3
  • Prior quantization methods include data-oblivious projections and data-adaptive binary, product, additive, and ternary quantization, while this work targets downstream MIPS rather than reconstruction error.Related work also considers learned transformations and quantization from observed data distributions; May et al. (2019) target downstream NLP training performance.Source: §2.2.2 · p. 3

3 Problem Formulation

Traditional quantization minimizes database reconstruction error, which matches expected inner-product error under isotropic queries but treats all query–point pairs alike. The score-aware loss instead emphasizes high inner products and decomposes into weighted parallel and orthogonal residual errors, with threshold weighting as a tractable special case.

3 Problem Formulation

  • Traditional reconstruction-error minimization is equivalent to minimizing expected inner-product error when the query distribution is isotropic.The paper notes that this objective averages over all query–point pairs, although high-inner-product pairs are more likely to affect retrieval rankings.Source: §3 · p. 3
  • The score-aware quantization loss weights inner-product approximation error by an arbitrary function of the true inner-product score.The query distribution may be assumed uniform on the unit sphere when unknown, or the expectation can be recomputed for a known or empirically estimated distribution.Source: §3 · p. 3

3.1 Analyzing Score-Aware Quantization Loss

  • For any weight function, the score-aware loss decomposes into weighted parallel and orthogonal residual errors.The residual is x_i − x̃_i, and the relative component weights are determined by the choice of w.Source: §3.1 · p. 4
  • When queries are uniform on the d-dimensional unit sphere, the score-aware loss has the parallel–orthogonal weighted form given by Theorem 3.2.The theorem’s stated query-distribution assumption is uniformity on the unit sphere.Source: §3.1 · p. 4
  • A nonnegative, non-decreasing weight on nonnegative scores makes parallel quantization error more heavily weighted than orthogonal error.This condition describes weights that vanish for negative scores and are monotonically non-decreasing for nonnegative scores.Source: §3.1 · p. 4

3.2 Special case of w(t) = I(t ≥T)

  • The threshold weight w(t) = I(t ≥ T) includes quantization loss only for inner products at or above T and more heavily penalizes parallel error.For this special case, η/(d−1) is computed analytically as a function of dimension and quickly approaches its limit.Source: §3.2 · pp. 4–5, Figure 2 · p. 5
  • At T = 0, parallel and orthogonal errors receive equal weight; at T = ||x_i||, only parallel error is considered.The component weights depend on ||x_i||; for a constant-norm database, the paper gives a simplified form.Source: §3.2 · p. 5

4 Application to Quantization Techniques

The paper adapts vector and product quantization to the anisotropic loss by learning codebooks with parallel and orthogonal residual weights. Its iterative assignment and update procedures retain the standard reconstruction-loss methods as special cases and converge to a fixed point.

4 Application to Quantization Techniques

  • With k codewords, quantized database inner products can be computed in O(kd + n) time using a query–codeword lookup table.The table is computed in O(kd) time, followed by one lookup for each of the n datapoints.Source: §4 · p. 5
  • Anisotropic vector quantization replaces the k-means reconstruction objective with a weighted objective over parallel and orthogonal residual errors.When the component weights are equal, codeword updates reduce to weighted partition averages; with w(t) = 1, they reduce to the standard k-means average.Source: §4 · pp. 5–6
  • The vector-quantization procedure alternates assigning each datapoint to its lowest-loss codeword and updating each codeword for its assigned partition.The update has a closed-form solution, and the procedure repeats until a fixed point or the maximum iteration count.Source: §4 · p. 6

4.1 Product Quantization

  • Product quantization splits each datapoint into M subspaces and uses M dictionaries of k codewords to represent k^M possible codewords.Query–codeword partial dot products are summed across subspaces; the anisotropic loss yields an anisotropic product-quantization objective.Source: §4.1 · p. 6
  • Product-quantization training alternates partition assignment and dictionary updates, with convex updates for fixed partitions and convergence to a fixed point.The codebook can optionally be initialized by training under ℓ2 reconstruction loss, which the paper says speeds training.Source: §4.1 · p. 7

5 Experiments

The experiments find that score-aware quantization improves retrieval and inner-product estimation over reconstruction loss, and achieves strong end-to-end speed–recall performance on Glove1.2M. Comparisons include fixed-bitrate quantization baselines and 11 public benchmark baselines.

5.1 Direct comparison with reconstruction loss

  • The Glove1.2M experiments unit-normalize datapoints at training time to adapt the method to cosine similarity search.MIPS is equivalent to cosine similarity search when all datapoints have equal norm.Source: §5.1 · p. 7

5.3 Recall-Speed benchmark

  • On Glove1.2M, the method is fastest in the high-recall regime of the end-to-end speed–recall benchmark.The benchmark uses 11 baselines with pre-tuned parameters.Source: §5 · p. 7, Figure 4 · p. 8, §5.3 · p. 9

5.1 Direct comparison with reconstruction loss

  • Score-aware loss improves Recall1@10 over reconstruction loss when the threshold T is chosen reasonably, and reduces relative error in top-1 inner-product estimates across bitrate settings.The experiments use product quantization on Glove1.2M.Source: §5.1 · pp. 7–8

5.2 Maximum inner product search retrieval

  • At 100 and 200 bits per datapoint, score-aware quantization outperforms LSQ and three QUIPS variants across all tested ranges of N.Recall 1@N measures the proportion of queries whose top N retrieved results contain the true top-1 datapoint.Source: §5.2 · p. 8, Figure 4 · p. 8

5.3 Recall-Speed benchmark

  • The end-to-end benchmark uses one CPU thread on an Intel Xeon W-2135 and combines product quantization, SIMD-based ADC, and a vector-quantization tree.The benchmark follows the public ANN-Benchmarks protocol.Source: §5.3 · p. 9

6 Conclusion

The conclusion presents score-aware quantization as a theoretically supported alternative to reconstruction error for inner-product search. It reports improvements in retrieval, score estimation, and public benchmark performance.

6 Conclusion

  • The proposed quantization loss replaces traditional reconstruction error and weights query–database pairs according to their inner-product values.Source: §6 · p. 9
  • The loss is theoretically proven and applicable to a wide range of quantization methods, including product and binary quantization.Source: §6 · p. 9
  • Experiments report superior retrieval recall and inner-product value estimation versus methods using reconstruction error.Source: §6 · p. 9
  • On public datasets, the speed–recall benchmark indicates that the method outperforms state-of-the-art baselines.Source: §6 · p. 9

7 Appendix

The appendix proof analyzes quantization error under a uniformly spherically distributed query. It decomposes query and residual components into directions parallel and orthogonal to the datapoint.

7.1 Proof of Theorem 3.2

  • The proof assumes queries are uniformly spherically distributed and decomposes each query into components parallel and orthogonal to x.Source: §7.1 · p. 12
  • Conditioned on the inner product with x, the expected squared score error splits into parallel- and orthogonal-residual terms, with the cross term vanishing by symmetry.Source: §7.1 · p. 12
  • The proof evaluates the parallel contribution using the conditional query component and treats the orthogonal query component as uniformly distributed in the subspace orthogonal to x.Source: §7.1 · p. 12

7.2 Proof of Theorem 3.3

The proof of Theorem 3.3 uses a nondecreasing weight function and a condition that it vanishes for negative inner products. Its argument yields equality only when the weight function is constant.

7.2 Proof of Theorem 3.3

  • The proof identifies constant w as the equality case for the relevant inequality, provided w is not identically zero.Source: §7.2 · p. 13
  • For nonnegative inner products, the proof uses that a nondecreasing w has nonnegative derivative, making the integral nonnegative.Source: §7.2 · p. 13
  • The argument also assumes w(t)=0 for t<0, which simplifies the integral.Source: §7.2 · p. 13

7.3 Proof of Results for w(t) = I(t ≥T)

For the threshold weighting w(t) = I(t ≥ T), the proof defines α from T and ||x_i|| and establishes that I_d is non-increasing as d increases.

7.3 Proof of Results for w(t) = I(t ≥T)

  • For w(t) = I(t ≥ T), the proof sets α := arccos(T/||x_i||).This specializes the preceding analysis to an indicator weighting at threshold T.Source: §7.3 · p. 13
  • The proof invokes Cauchy–Schwarz for integrals in its analysis of I_d.Source: §7.3 · p. 13
  • I_d is monotonically non-increasing with d, and the stated ratio I_d/I_{d+2} has a limit.The passage says this limit exists after establishing monotonicity.Source: §7.3 · p. 14

7.4 Proof of Theorem 4.2

The proof splits each quantization residual into orthogonal parallel and perpendicular components, then uses their weighted losses to obtain a convex quadratic center update. Product-quantization codebooks are optimized through a second convex quadratic problem.

7.4 Proof of Theorem 4.2

  • The residual is decomposed into parallel and orthogonal components, r∥ and r⊥.The proof states that these components sum to x_i − x̃_i and are orthogonal.Source: §7.4 · p. 14
  • Because h_i,∥ ≥ h_i,⊥, the center loss is convex quadratic and its optimal center can be calculated.The proof first drops a constant term and sums the loss over points assigned to the center.Source: §7.4 · pp. 14–15

7.5 Codebook Optimization in Product Quantization

  • In product quantization, each quantized point is represented as B_i c, and optimizing the shared codebook c is a convex quadratic minimization.The matrix X is full rank if every codeword is observed at least once.Source: §7.5 · p. 15

7.6 Results on the Amazon-670k Extreme Classification Dataset

On Amazon-670k, anisotropic vector quantization benefits are especially evident for Recall 1@N at lower bitrates and lower N. The paper also reports improved recall when score-aware loss is applied to binary hashing, and identifies Glove1.2M as a better-aligned MIPS benchmark than the other datasets discussed.

7.6 Results on the Amazon-670k Extreme Classification Dataset

  • Anisotropic vector quantization benefits on Amazon-670k Recall 1@N are especially evident at lower bitrates and lower N.The evaluation uses a classifier with 670,091 classes and a 1,024-dimensional final layer.Source: §7.6 · p. 15, Table 1 · p. 16

7.7 Results on Binary Quantization

  • On SIFT1M, score-aware loss greatly improves recall for Stochastic Generative Hashing compared with reconstruction-loss training.The table compares SGH with SGH-score-aware.Source: §7.7 · p. 16, Table 2 · p. 16

7.8 Dataset Selection for MIPS evaluation

  • Glove1.2M is the only discussed dataset with nearly uncorrelated dimensions and roughly equal variance, properties sought for MIPS benchmarking.SIFT1M and GIST1M have strong inter-dimension correlations; MovielensSVD and NetflixSVD have large variance differences across dimensions.Source: §7.8 · p. 17, Figure 5 · p. 18

Related papers

Loading 1908.10396v5…