Stop Indexing at Full Precision: Revisiting Clustering for Vector Embeddings

1 INTRODUCTION

• Clustering bottlenecks queries until index construction finishes because it is both memory- and compute-bound [41] [42] and repeatedly accesses the entire raw-vector collection.Once built, cluster centroids guide queries toward likely nearest-neighbor clusters, avoiding access to most vectors; clustering-based indexing nevertheless receives comparatively little research attention.Source: §1 · p. 1
• 60x storage reduction accompanies less than 1% clustering-quality degradation using 1-bit RabitQ codes of PCA-projected vectors instead of full-precision vectors.Figure 1 compares clustering performance on 10M 1024-dimensional Cohere embeddings.Source: Figure 1 · p. 1, §1 · p. 1
• The proposed pipeline applies dimensionality reduction, quantization, and dimension pruning before clustering, unlike systems that cluster full-precision vectors and quantize afterward [16] [60] [72].The study also explores pipeline design decisions affecting performance and cluster quality for vector search.Source: §1 · p. 1
• Adapting dimension-pruning techniques SuperKMeans [42] and ADSampling [22] to integrate with quantization further accelerates clustering without sacrificing quality.Figure 1 also shows SuperKMeans delivering additional clustering speedups without hurting index quality.Source: §1 · p. 1, Figure 1 · p. 1

2.1 Vector Search

• Approximate vector search accepts inexact neighbors to reduce compute and storage requirements, making exact search unnecessary for many applications such as RAG and recommendation.Quantization [3] [16] [21] [23] [93], dimension pruning [22] [96], and dimensionality reduction [45] [47] [92] reduce query-time costs. Graph indexes need fewer distance comparisons [53] but longer builds [42] [51] and more complex updates [89] and filtering, making partition-based indexes attractive for large or distributed collections [48] [57] [77].Source: §2.1 · p. 2

2.2 The Role of Clustering in Vector Search

• Clustering remains an indexing bottleneck despite being orders of magnitude faster than graph-index construction, motivating low-latency, low-memory indexing [51].IVF clusters vectors using methods such as k-means [16] [33] and searches nearby clusters, trading speed against quality through the number explored [16]. Clustering repeatedly accesses the collection and is heavily compute-bound, making fast, on-the-fly indexing attractive for filtered similarity joins.Source: §2.2 · p. 2

2.3 Clustering in Vector Systems

• Nearest-centroid assignment is clustering’s main bottleneck because it computes every point–centroid distance, efficiently implemented through optimized GEMM routines.Systems use Lloyd k-means [49] or hierarchical variants with random initialization; k-means++ [6] offers marginal improvements at substantially higher runtime [42]. Updates average assigned vectors and can split large clusters to replace empty ones [33] [57]; typically 5 to 10 assignment/update iterations precede a final assignment pass [42].Source: §2.3 · p. 2

2.4 Efforts to Optimize Vector Clustering

• Dimensionality reduction lowers clustering memory and computation, but its impact on clustering quality remains insufficiently studied.VectorChord uses a Johnson–Lindenstrauss Transform before clustering, while LindormVector uses PCA to concentrate energy in leading dimensions. Matryoshka embeddings [45] are trained to concentrate energy in front dimensions.Source: §2.4 · p. 3
• PQk-means reduces memory usage and accelerates distance calculations at the cost of clustering quality, whereas SuperKMeans achieves substantial speedups through dimension pruning without sacrificing clustering quality [42].PQk-means uses Product Quantization; LVQ [3] [4] and RabitQ [21] [23] [27] have not been used for vector clustering. SuperKMeans interleaves GEMM routines and pruning kernels.Source: §2.4 · p. 3
• Applying approximation before clustering reduces raw-data passes and memory requirements while improving performance and mostly preserving clustering quality.Conventional pipelines cluster at full precision before reducing dimensionality or quantizing vectors. Vector-clustering optimization and the effects of approximation on clustering quality remain comparatively understudied.Source: §2.4 · pp. 2–3

2.5 Keys for the Performance of Clustering

• Quantized clustering performance depends on efficient many-to-many distance computation and hardware support for smaller data types.Dimensionality reduction accelerates optimized float32 GEMM by reducing dimensions, while pruning reduces distance calculations. Quantization benefits depend on suitable SIMD [13] [41] or specialized hardware such as Intel AMX for 8-bit processing.Source: §2.5 · p. 3

2.6 The Resilience of Clustering

• 2-3x larger relative L2 gaps between first- and second-nearest centroids than second- and third-nearest centroids help make clustering more approximation-resilient than vector search [44].Assignment consists of top-1 nearest-neighbor searches, with data vectors acting as queries and centroids as the searched collection; approximation errors are consequently less likely to change the nearest-centroid assignment.Source: Figure 3 · p. 3, §2.6 · p. 3

3 OUR PIPELINE: APPROXIMATE FIRST, THEN CLUSTER

• The pipeline approximates vectors before clustering, applies dimension pruning during clustering, and permits final assignments in projected or quantized space.Unlike systems that cluster full-precision vectors before quantization [16] [60] [72], this pipeline never requires touching raw vectors after preprocessing.Source: §3 · p. 3, Figure 4 · p. 4

3.1 Adapting Techniques for Vector Clustering

• 8- and 4-bit GEMM routines compute SQ distances directly using integer arithmetic, while centroid updates average dimensions in the quantized domain.Direct quantized-domain computation is possible because all vectors share the same transformation parameters.Source: §3.1 · p. 4
• 4-bit GEMM kernels compute part of reformulated LVQ distances, avoiding repeated float32 reconstruction during many-to-many comparisons.Additional scalar operations complete the distances, with N_x and A_x cached across iterations and N_y computed once per iteration. Because averaging LVQ codes is undefined, centroid updates fuse decoding with averaging and then re-encode.Source: §3.1 · p. 4
• 1-bit RabitQ encodes data points while SQ4 encodes centroids, targeting the data points that dominate clustering memory.Data vectors are centered, normalized, randomly rotated, and sign-quantized; data-only scalar factors are cached across iterations, while centroid factors are computed once per iteration. FastScan uses PSHUFB for 32 simultaneous lookups; centroid updates fuse decoding and averaging before SQ4 re-encoding.Source: §3.1 · pp. 4–5
• PQ4 uses FastScan, whereas PQ8 uses scalar lookups; both assign clusters through code-to-code distances and update centroids using PQk-means sparse voting.PQ8 provides 256 codes per subspace, while PQ4 provides 16; PQ8 codes are incompatible with PSHUFB.Source: §3.1 · p. 5
• 12.5% of dimensions feed initial SuperKMeans GEMM calculations, followed by progressive-pruning kernels every 64 dimensions on surviving candidates [42].A random orthogonal rotation preserves L2 distances while distributing variance more evenly for ADSampling [22]. SQ8/SQ4 replace float32 GEMM with integer GEMM, but LVQ/RabitQ face limitations because pruning requires distances over partial dimensions.Source: §3.1 · p. 5
• Dimensionality-reduced and Matryoshka vectors integrate without extra engineering because they remain float32, with energy concentrated in their front dimensions.Dimensionality reduction preserves global variance; Matryoshka embedding models already produce front-loaded energy [45].Source: §3.1 · p. 5

4.1 Quantization Techniques

• Up to 17x acceleration accompanies RabitQ with SuperKMeans, while SQ8 matches raw-vector clustering quality and LVQ4 and RabitQ remain within 1% recall difference.SQ8 provides 4x storage reduction and up to 8x speedups with SuperKMeans; LVQ4 and RabitQ provide 8x and 30x storage reduction, respectively. LVQ4 outperforms equally compressed SQ4, while RabitQ slightly worsens cluster balance and SuperKMeans metadata reduces its storage savings by around 10%.Source: Figure 5 · p. 6, Table 3 · p. 6, §4.1 · p. 6
• 0.84 to 0.85 recall on Cohere results from updating PQ centroids with raw vectors in the final iteration, requiring raw-vector access.PQ offers the greatest storage reduction but worsens recall and balance because its global codebook uses raw vectors rather than cluster-centered residuals, its typical application [16]. Encoding and constant-term precomputation are negligible for SQ, LVQ, and RabitQ, whereas PQ encoding limits speedup; partial L2 computations also consume considerable assignment time for LVQ and RabitQ.Source: §4.1 · p. 7, Table 4 · p. 7
• Updating RabitQ centroids from raw vectors in the final iteration restores near-ideal quality across metrics by correcting peripheral-centroid reconstruction bias.Outward reconstruction bias largely cancels within central clusters but survives aligned sign patterns in peripheral clusters, causing boundary points to enter denser clusters and increasing vectors explored. The correction requires accessing raw vectors, potentially making it impractical when they reside on slower storage.Source: Figure 5 · p. 6, §4.1 · p. 7

4.2 Dimensionality Reduction Techniques

• Preserving 60–70% of total variance with PCA achieves clustering quality within 1% of ideal, preserving centroid quality better than JLT projections and Matryoshka prefixes on the evaluated datasets.Preserving 80% variance achieves optimal quality with 3–4x dimensionality reduction; Matryoshka prefixes perform comparably to JLT on OpenAI, Jina, and MXBAI. Dimensionality-reduction speedups are sublinear, but SuperKMeans provides 20%–2x speedups, giving wider vectors speedups comparable to thinner vectors without sacrificing quality; SuperKMeans is disabled for d < 128 [42].Source: §4.2 · pp. 7–8
• Recomputing full-dimensional centroids gives the best quality after dimensionality reduction, but unprojected or projected centroids approach it when preserved variance is high.The reported reduction experiments recompute full-dimensional centroids from raw vectors; alternatives lose discarded-dimensional energy but can avoid raw-vector access after preprocessing, although unprojection is unavailable for Matryoshka vectors. PCA preprocessing is negligible relative to clustering and unnecessary for Matryoshka representations; prior projected-space search approaches [92] still store PCA residuals for re-ranking.Source: Table 6 · p. 8, §4.2 · p. 8

4.3 Mixing Techniques

• 80% preserved PCA variance makes LVQ preferable for raw-vector-equivalent quality and RabitQ preferable when allowing up to 1% quality deviation on Cohere/1024.For speed with near-optimal quality, RabitQ with SuperKMeans is preferred. Adding PCA can reduce its performance because partial L2 computations burden pruning, especially for thinner vectors; SQ8 consistently benefits from SuperKMeans.Source: Figure 9 · p. 9, §4.3 · p. 9

4.4 Other Accelerators

• Up to 91x acceleration results from combining hierarchical k-means with RabitQ, although its more balanced clusters reduce recall and require probing more clusters.Graph-based assignments use top-1 searches over a centroid index such as HNSW, accelerate vanilla k-means but produce less balanced clusters, and require tuning ef_search between speed and quality; graph construction takes less than 0.1% of runtime. Sampling reduces runtime proportionally [42], with around 20–30% sufficient to maintain quality and balance [42], but final assignment and index materialization still require all vectors.Source: Table 7 · p. 9, §4.4 · p. 9, Table 8 · p. 9

4.5 Scalability

• 200K clusters train in under 1 minute with hierarchical k-means and RabitQ on 50M Cohere embeddings.This scalability experiment uses 200GB of embeddings, 512GB RAM, and 64 cores. Hierarchical k-means with RabitQ is fastest, while both hierarchical k-means and graph-based assignments scale sublinearly with the number of clusters.Source: Figure 10 · p. 10, §4.5 · p. 10

5 DISCUSSION

• Full-precision vectors are excessive for clustering; applying approximation techniques first can improve vector-system ingestion performance.Clustering remains the preferred indexing method for large-scale cloud vector systems, where compute time contributes directly to billing.Source: §5 · p. 10
• Approximation choices should follow the vector-search pipeline: systems using LVQ should encode vectors before clustering.The same principle applies to dimensionality reduction, which recent studies propose combining with quantization [47] [78] [79] [92].Source: §5 · p. 10
• Reusing vector representations for search and clustering streamlines indexing and ingestion, opening research directions for quantization methods that efficiently serve both tasks.The proposed design allows the same representations to support both vector search and clustering.Source: §5 · p. 10

• Up to 60x storage reduction and substantially faster clustering are achievable with RabitQ, PCA, and SuperKMeans dimension pruning while maintaining near-optimal clustering quality.The pipeline applies approximation before clustering, adapting quantization techniques for clustering and integrating them with dimension pruning.Source: §6 · p. 10
• Future work includes replicating the study with graph-based indexes such as HNSW and DiskANN.For graph-based assignment, the authors also propose evaluating different graph indexes or developing indexes tailored to that purpose.Source: §6 · p. 10
• Specialized hardware units for particular data types, such as Intel’s AMX, could change the trade-offs between clustering speed and storage reduction.Exploring these hardware-dependent trade-offs remains future work.Source: §6 · p. 10
• Evaluating multi-vector embeddings [38] and classic datasets not derived from AI embedding models, such as SIFT and GIST, would broaden the pipeline’s applicability.Source: §6 · p. 10