Source-linked AI summary
Stop Indexing at Full Precision: Revisiting Clustering for Vector Embeddings
Leonardo Kuffo, Peter Boncz
TL;DR
Clustering is a compute- and memory-intensive bottleneck in vector indexing, yet relatively few studies address it. This paper applies approximation techniques before clustering and finds that 1-bit codes achieve near-optimal quality with 60x storage reduction.
Problem
Clustering is a compute- and memory-intensive vector-indexing bottleneck that has received relatively little research attention.
Method
The proposed pipeline applies dimensionality reduction and quantization before clustering, while using dimension pruning during clustering.
Results
Less than 1% degradation in clustering quality is achieved with 1-bit RabitQ codes and 60x storage reduction.
Takeaways & Limitations
Full-precision vectors are excessive for clustering, and approximation techniques can substantially accelerate indexing while maintaining near-optimal clustering quality.
Takeaways & Limitations
Applicability beyond AI embedding models, multi-vector embeddings, and graph-based indexes remains unevaluated.
Abstract
from arXiv · showhide
In this study, we revisit three widely used techniques in vector search and utilize them to optimize vector embedding indexing through clustering: dimensionality reduction, quantization, and dimension pruning. We propose an indexing pipeline in which these techniques are applied before clustering, and we focus on how they affect storage footprint, clustering time, and the quality of the resulting centroids for vector search tasks. Our results reveal that using full-precision vectors for clustering is excessive, as even 1-bit codes can achieve near-optimal clustering quality (within 1% of ideal) while reducing storage requirements by 60x and delivering attractive performance gains (Figure 1). We open-source our implementations at https://github.com/cwida/SuperKMeans.
1 INTRODUCTION
The paper argues that full-precision vectors are unnecessary for clustering-based vector indexing and introduces a preprocessing pipeline using reduction, quantization, and dimension pruning to reduce storage and improve performance without sacrificing index quality.
- Motivation: Clustering bottlenecks index construction because it is memory- and compute-intensive and repeatedly accesses the entire raw-vector collection, unlike query-time VSS, which prunes most vectors.This bottleneck persists despite clustering’s role in producing centroids that guide approximate vector similarity search.
- Main result: 1-bit RabitQ codes on PCA-projected vectors achieve near-optimal clustering quality, with less than 1% degradation and 60x lower storage than full-precision vectors.Figure 1 reports near-optimal quality with 60x storage reduction and improved clustering speed, including further gains from SuperKMeans without hurting index quality.
- Approach: The proposed indexing pipeline applies dimensionality reduction, quantization, and dimension pruning before clustering to reduce storage and accelerate indexing without sacrificing index quality.The studied techniques include JLT, PCA, Matryoshka vectors, SQ, LVQ, RabitQ, PQ, and dimension-pruning methods.
- Approach: The work adapts SuperKMeans [42] and ADSampling [22] to integrate dimension pruning with quantization, further accelerating clustering without sacrificing quality.These adaptations target faster clustering while preserving the resulting index quality.
2 PRELIMINARIES
Approximate nearest-neighbor search trades exactness for practical efficiency, with partition-based indexes clustering vectors to guide queries. Although clustering enables these indexes, it remains costly, motivating dimensionality reduction, quantization, and pruning before clustering.
- Approximate nearest-neighbor search (ANNS) returns sufficiently accurate results when exact nearest-neighbor search is impractical because of compute and storage costs.Modern retrieval-augmented generation and recommender-system applications commonly use ANNS or vector similarity search.
- Partition-based indexes such as inverted files cluster vectors with k-means, then search centroids and evaluate vectors in the nearest clusters to balance speed and quality.The number of explored clusters controls the search-speed–quality trade-off.
- Clustering is an index-construction bottleneck because it repeatedly accesses the full collection or a large subsample, delaying query availability despite being faster than graph-index construction.This workload differs from vector search, which typically accesses only portions of a collection.
- Lloyd k-means initializes centroids, assigns every vector to its nearest centroid using pairwise distances, updates centroids by averaging assignments, and repeats until termination.The assignment step is the main bottleneck and is efficiently implemented with GEMM; typical vector-embedding workloads use 5–10 iterations before final assignments.
- Prior work applies dimensionality reduction, quantization, or dimension pruning to reduce clustering cost, but quantization can reduce quality and their combined use remains unclear.Existing pipelines generally index full-precision vectors before projection or quantization, motivating approximation earlier in the pipeline.
3 OUR PIPELINE: APPROXIMATE FIRST, THEN CLUSTER
The proposed pipeline applies dimensionality reduction and quantization before clustering, while dimension pruning reduces distance calculations during clustering. It supports clustering and final assignments in approximate domains without requiring access to raw vectors after preprocessing.
- Pipeline design: The pipeline performs dimensionality reduction and quantization before clustering, unlike systems that cluster full-precision vectors and quantize afterward [16] [60] [72].Dimension pruning further reduces distance calculations during clustering.
- Quantization methods: SQ8 and SQ4 enable integer-domain distance calculations and centroid averaging, whereas LVQ4 fuses decoding with distance computation and re-encodes averaged centroids.LVQ codes cannot be directly averaged because each vector has its own scale and bias.
- Quantization methods: RabitQ uses 1-bit sign codes with an unbiased L2-distance estimator, while cached scalar factors amortize repeated k-means calculations.The pipeline combines RabitQ’s binary codes with SQ4 residual quantization and FastScan lookup tables for efficient distance computation.
- Quantization methods: Product quantization splits vectors into subspaces and uses code-to-code distance comparisons; PQ4 uses FastScan, while PQ8 uses scalar lookup.PQ8 provides 256 codes per subspace and PQ4 provides 16 codes.
- Distance acceleration: SuperKMeans combines GEMM on the first 12.5% of dimensions with progressive pruning every 64 dimensions, using rotation to preserve L2 distances and support reliable pruning [42] [22].Dimensionality reduction preserves global variance by concentrating vector energy in leading dimensions, including for Matryoshka vectors [45].
4 EVALUATION
The evaluation measures clustering quality, storage reduction, and clustering speed for an indexing pipeline combining quantization, dimensionality reduction, and clustering methods. Results show that several reduced representations preserve near-ideal vector-search quality while reducing storage or accelerating clustering, with trade-offs for PQ, RabitQ, and graph-based assignment.
- Quantization: SQ8 matches raw float32 clustering quality across all reported aspects while reducing storage 4x and achieving up to 8x speedups with SuperKMeans.Figure 5 and Table 3 evaluate centroid quality for IVF search, including recall and cluster-quality metrics.
- Quantization: PQ provides the highest storage reduction but harms recall and cluster balance because its global codebook is built before clustering rather than on residuals.The passage attributes PQ’s quality loss to applying product quantization to raw vectors instead of residuals centered around cluster means [16].
- Clustering Speed: Encoding and constant-term preprocessing are negligible for SQ, LVQ, and RabitQ, whereas PQ encoding limits speedup and partial-distance overhead slows LVQ and RabitQ assignments.Table 4 breaks clustering time into phases; all techniques except PQ4 and PQ8 use SuperKMeans.
- Dimensionality Reduction: PCA preserves clustering quality within 1% of ideal with 60–70% of variance, while retaining 80% of variance reduces dimensionality 3–4x.PCA is identified as the most effective dimensionality-reduction method for preserving centroid quality.
- Combining Techniques: On Cohere/1024, LVQ with 80% preserved PCA variance maintains raw-vector quality, while RabitQ with 80% variance is preferred when up to 1% deviation is acceptable.These combinations are evaluated for quality, storage, and speed trade-offs in Figure 9.
- Clustering Methods: Graph-based assignments accelerate clustering but produce less balanced clusters and require tuning ef_search, which trades speed against clustering quality.Setting ef_search too low compromises quality, while setting it too high reduces speed improvements.
5 DISCUSSION
The discussion argues that full-precision vectors are excessive for clustering in large-scale cloud vector systems, where compute affects billing. It recommends applying approximation techniques before clustering, with method selection guided by the algorithms used in the vector-search pipeline.
- Full-precision vectors are excessive for clustering in large-scale cloud vector systems, where every second of compute contributes to billing.
- Applying approximation techniques before clustering can improve vector-indexing data-ingestion performance.
- Approximation-method selection can be guided by the algorithms used in the vector-search pipeline.
6 CONCLUSIONS AND FUTURE WORK
The proposed pipeline applies vector-search approximation techniques before clustering, achieving up to 60x storage reduction and substantially faster clustering while maintaining near-optimal clustering quality. Future work targets hardware-specific trade-offs and graph-based vector indexes.
- Conclusions: Up to 60x storage reduction and substantially faster clustering are achieved with RabitQ, PCA, and dimension pruning while maintaining near-optimal clustering quality.The pipeline applies these approximation techniques before clustering and finds clustering highly resilient to them.
- Future Work: Future work will study how specialized hardware such as Intel’s AMX changes the trade-off between speed and storage reduction.
- Future Work: Replicating the study with graph-based indexes such as HNSW and DiskANN is proposed for systems implementing graph-based vector indexes.