PaperlayerView exact revision on arXiv

Source-linked AI summary

SAQ: Pushing the Limits of Vector Quantization through Code Adjustment and Dimension Segmentation

Hui Li, Shiyuan Deng, Xiao Yan, Xiangyu Zhi, James Cheng

arXiv:2509.12086v2cs.DBcs.DScs.IR

TL;DR

State-of-the-art vector quantization faces a trade-off between encoding efficiency and accuracy, alongside conflicting dimension-balancing and dimension-reduction designs. SAQ combines code adjustment with dimension segmentation and reports lower quantization error and faster encoding than Extended RaBitQ. Its segmentation advantage depends on a skewed eigenvalue distribution; with a uniform distribution, it matches CAQ.

  • Problem

    State-of-the-art vector quantization faces prolonged quantization time and conflicting dimension-balancing and dimension-reduction designs, complicating efforts to improve efficiency while retaining search accuracy.

    Source: §1 · p. 2

  • Method

    SAQ combines code adjustment, which independently quantizes and refines dimensions, with PCA-based dimension segmentation and bit allocation across segments.

    Source: §1 · p. 2

  • Results

    SAQ achieves up to 80% lower quantization error and 80× faster encoding than Extended RabitQ.

    Source: §7 · p. 13

  • Takeaways & Limitations

    SAQ's accuracy gains translate to higher query throughput for ANNS.

    Source: §1 · p. 2

    Dimension segmentation's chance for improvement vanishes with a uniform eigenvalue distribution, though its plan then matches CAQ's performance.

    Source: §4.2 · p. 8

Abstract

from arXiv · show

Approximate Nearest Neighbor Search (ANNS) plays a critical role in applications such as search engines, recommender systems, and RAG for LLMs. Vector quantization (VQ), a crucial technique for ANNS, is commonly used to reduce space overhead and accelerate distance computations. However, despite significant research advances, state-of-the-art VQ methods still face challenges in balancing encoding efficiency and quantization accuracy. To address these limitations, we propose a novel VQ method called SAQ. To improve accuracy, SAQ employs a new dimension segmentation technique to strategically partition PCA-projected vectors into segments along their dimensions. By prioritizing leading dimension segments with larger magnitudes, SAQ allocates more bits to high-impact segments, optimizing the use of the available space quota. An efficient dynamic programming algorithm is developed to optimize dimension segmentation and bit allocation, ensuring minimal quantization error. To speed up vector encoding, SAQ devises a code adjustment technique to first quantize each dimension independently and then progressively refine quantized vectors using a coordinate-descent-like approach to avoid exhaustive enumeration. Extensive experiments demonstrate SAQ's superiority over classical methods (e.g., PQ, PCA) and recent state-of-the-art approaches (e.g., LVQ, Extended RabitQ). SAQ achieves up to 80% reduction in quantization error and accelerates encoding speed by over 80x compared to Extended RabitQ.

1 Introduction

The introduction frames SAQ as addressing costly encoding and the tension between dimension balancing and dimension reduction. It combines code adjustment with dimension segmentation and reports improvements in quantization accuracy, encoding speed, and ANNS throughput.

1 Introduction

  • Vector quantization compresses vectors to reduce storage and speed approximate distances, while ANNS trades exactness for efficiency because exact high-dimensional search requires linear scans.The paper describes vector datasets with billions of vectors and thousands of dimensions, potentially reaching terabytes.Source: §1 · p. 1
  • Existing designs either equalize dimensions through random projection or discard small PCA tails, while E-RaBitQ's O(2^B·D log D) enumeration makes encoding costly.The paper identifies these design paradigms as contradictory; it reports more than 3,600 CPU hours to quantize one billion vectors at B=9 and D=3,072.Source: §1 · pp. 1–2
  • CAQ independently quantizes dimensions with B bits, then adjusts codes toward better alignment in O(D), replacing E-RaBitQ enumeration.The introduction characterizes this refinement as coordinate-descent-like and reports the same quantization accuracy as RaBitQ.Source: §1 · p. 2
  • After PCA, SAQ segments dimensions, allocates more bits to leading high-magnitude segments, and uses dynamic programming to minimize error under quota B·D.Trailing segments receive fewer bits or are discarded.Source: §1 · p. 2
  • SAQ also adds SIMD distance estimators, progressive b-bit approximations, and multi-stage distance bounds for ANNS pruning.Progressive approximation uses the first b < B bits per dimension; the multi-stage bounds use segmented approximate vectors.Source: §1 · p. 2
  • Up to 5.4× accuracy improvement, 80× faster quantization, and 12.5x higher query throughput at 95% recall are reported for SAQ; on GIST, 5–6 bits/dimension match 8-bit RaBitQ accuracy.The GIST comparison is shown in Figure 2; RaBitQ denotes extended RaBitQ in these experiments.Source: §1 · pp. 2–3, Figure 2 · p. 3

2 Preliminaries

This section introduces locally adaptive quantization and RaBitQ variants that balance encoding choices with distance-estimation accuracy. Extended RaBitQ supports multiple bits per dimension but uses an expensive search over its codebook.

2.1 Locally-adaptive Vector Quantization

  • LVQ mean-centers each vector and quantizes coordinates over a per-vector range, improving accuracy over global quantization at equal bit budgets but potentially degrading under high compression.The range is divided into 2^B equal intervals.Source: §2.1 · p. 3

2.2 RaBitQ

  • RaBitQ projects normalized vectors with a random orthonormal matrix, uses each projected dimension's sign for 1-bit quantization, and estimates distances with an unbiased estimator and bit operations.The projection preserves inner products, and the estimator reuses precomputed quantities.Source: §2.2 · p. 3

2.3 Extended RaBitQ

  • Extended RaBitQ supports B-bit quantization per dimension, but its pruned codeword enumeration has complexity O(2^B · D log D), making encoding slow at higher bit counts.Its reported estimator error scales with 2^-B, and its progressive strategy supports the most-significant-bit prefix but not arbitrary prefixes with 1 < b < B.Source: §2.3 · p. 4

3 Code Adjustment

Code adjustment quantization (CAQ) replaces exhaustive codeword search with independent dimension handling and iterative refinement. It supports flexible progressive distance approximation, while its codebook is equivalent to RaBitQ's.

3 Code Adjustment

  • CAQ reduces quantization complexity from O(2^B · D log D) to O(D), while maintaining RaBitQ's empirical error and distance-estimation efficiency.It also permits valid progressive quantized vectors from prefixes of more than one bit per dimension.Source: §3 · p. 4

3.1 Quantization Procedure

  • CAQ initializes a uniform-grid code like LVQ, then adjusts one coordinate by a step Δ over limited rounds to improve cosine alignment with the data vector.Each adjustment costs O(1), giving overall complexity O(r · D); the authors recommend r in [4, 8].Source: §3.1 · p. 5

3.2 Distance Estimation

  • CAQ estimates distances from arbitrary-length prefixes of each dimension's code, enabling progressive refinement beyond RaBitQ's restriction to 1-bit prefixes.The paper reports that a prefix estimator has almost the same error as native CAQ quantization using the same number of bits.Source: §3.2 · p. 6

3.3 Analysis

  • CAQ's codebook is equivalent to RaBitQ's, and experiments report identical estimation errors despite the coordinate-descent-style search not necessarily reaching the optimum.The equivalence follows because codeword normalization changes norms but not directions, and codeword norms do not affect the estimated inner product.Source: §3.3 · p. 6

4 Dimension Segmentation

SAQ combines dimension balancing and reduction by assigning bits according to variance across PCA-projected dimensions. It constructs a quantization plan under a bit quota and uses that plan for progressive distance estimation.

4.1 Motivation and Problem Formulation

  • SAQ assigns more bits to high-variance dimensions and fewer bits to low-variance dimensions, addressing the limits of equal-bit quantization and fixed-ratio dimension reduction.PCA orders dimensions by variance; the plan uses a total bit quota, and segments may be discarded when their variance is negligible.Source: §4.1 · pp. 6–7

4.2 Quantization Plan Construction

  • Dynamic programming searches for the minimum-error quantization plan under the total bit quota by extending plans with new dimension segments and bit allocations.The plan's error model draws on the observed near-normal, near-zero-mean value distribution after PCA; the paper also notes an assumption that query vectors share the data distribution.Source: §4.2 · p. 7
  • Segmentation relies on skewed eigenvalue distributions; with uniform eigenvalues, the plan uses one segment and matches CAQ performance.Source: §4.2 · p. 8

4.3 Multi-Stage Distance Estimation

  • The multi-stage estimator refines distance estimates from high-variance segments toward lower-variance ones and prunes a candidate when its estimate exceeds the current best nearest-neighbor distance.A segment-based lower-bound estimate is combined with the CAQ estimator; the paper reports average bit access below the dataset dimension and says most candidates can be pruned without computing every segment.Source: §4.3 · p. 8

5 EXPERIMENTAL Evaluation

The evaluation compares CAQ and SAQ with four quantization baselines across public datasets, compression settings, quantization accuracy, encoding efficiency, and ANNS performance. SAQ's main results show lower error at matched compression, while the micro-results examine iteration counts, memory access, progressive approximation, and storage overhead.

5.1 Main Results

  • SAQ achieves consistently better average relative error and recall than all baselines at the same compression rate.Its maximum relative error is less stable on low-dimensional data because SIMD segmentation has a minimum granularity of 64 dimensions; average and maximum errors decrease as dimension increases.Source: §5.1 · p. 9, Figure 8 · p. 10
  • At 𝐵=0.5, SAQ's average relative error is 4.8× lower than PQ on GIST, and at 𝐵=0.2 it remains more accurate than PQ.At 𝐵=0.5, SAQ also has lower error than RaBitQ at 𝐵=1; at higher compression rates, SAQ's average relative error is 2.5× to 5× lower than RaBitQ on high-dimensional datasets.Source: §5.1 · pp. 9–10
  • At 𝐵=9, SAQ quantizes vectors over 80× faster than RaBitQ.RaBitQ's quantization time increases exponentially with 𝐵 and reaches 11.8 CPU hours at 𝐵=9.Source: §5.1 · pp. 10–11, Table 4 · p. 10
  • On high-dimensional datasets, SAQ consistently outperforms RaBitQ in QPS, recall, and average distance ratio at the same compression rate.For MSMARCO, SAQ's QPS is 14.6× RaBitQ's at 𝐵=3; 𝐵=3 suffices for 95% recall on the high-dimensional datasets, while SAQ at 𝐵=2 reaches a maximum recall of 94.4% on MSMARCO.Source: §5.1 · p. 11, Table 5 · p. 11, Figure 9 · p. 12

5.2 Micro Results

  • SAQ's storage consumption is slightly higher than the baseline because its multi-stage estimator stores additional dataset statistics and factors.The overhead is reported as negligible for large-scale datasets; space consumption is almost proportional to 𝐵.Source: §5.2 · p. 11, Table 6 · p. 11
  • With 𝐵=4 and 𝑟=32, code adjustment produces average relative error only 0.7% worse than optimal; the authors recommend 𝑟∈[4, 8] for CAQ.The first few adjustment rounds substantially refine the code, while further increases in 𝑟 yield only slight accuracy improvement.Source: §5.2 · p. 11, Figure 10 · p. 12
  • SAQ's multi-stage estimator reduces bits accessed by about 1.9–4.0× versus RaBitQ's estimator, with little recall harm when 𝑚≥4.Bits accessed decrease as 𝑚 decreases, but 𝑚=2 also lowers recall; the authors recommend 𝑚=4 as the default.Source: §5.2 · p. 12, Figure 11 · p. 13
  • For progressive distance approximation, sampled-code error is almost the same as native-code error when 𝑏>4, and slightly higher when 2≤𝑏≤4.Sampled-code error is consistently lower than LVQ's; at 𝑏=1 it is almost the same as native-code error.Source: §5.2 · p. 12, Figure 12 · p. 13

6 Related Work

Related work covers clustering-based and projection-based vector quantization, along with optimizations to codebook learning and distance computation. SAQ is distinguished from dimension reduction by retaining projected dimensions and quantizing them rather than discarding the tail.

Clustering-based vector quantization

  • PQ partitions vectors into subspaces and learns codebooks with K-means [51], while RQ learns codebooks sequentially over residuals and AQ jointly learns codebooks [51].OPQ applies a rotation to distribute energy across subspaces, and LOPQ trains codebooks per IVF cluster.Source: §6 · p. 13
  • LSQ and LSQ++ optimize AQ's codebook-learning algorithms and use GPU acceleration [33, 34].Other codebook structures include composite quantization and TreeQ.Source: §6 · p. 13
  • Clustering-based methods aggregate codeword distances through lookup tables, but smaller codebooks that fit CPU registers degrade accuracy at the same space quota [51].The cited register-fitting design uses codebooks of size 𝐾=16 rather than 𝐾=256 [45].Source: §6 · p. 13

Projection-based vector quantization

  • PCA-based methods exploit energy concentrated in leading dimensions, while RaBitQ uses random orthonormal projection and 1-bit quantization; E-RaBitQ is described as state of the art in accuracy [18] [16].Unlike dimension-reduction approaches, SAQ is reported to improve on E-RaBitQ in encoding speed and quantization accuracy.Source: §6 · p. 13

7 Conclusions

SAQ addresses encoding efficiency and quantization accuracy through dimension segmentation and code adjustment. The authors report up to 80% lower quantization error and 80× faster encoding than Extended RaBitQ.

7 Conclusions

  • SAQ achieves up to 80% lower quantization error and 80× faster encoding than Extended RaBitQ through dimension segmentation and code adjustment.The conclusion presents these results as advances for efficient, high-accuracy vector quantization in large-scale ANNS applications.Source: §7 · p. 13

Related papers

Loading 2509.12086v2…