💻 computer science

Stop Indexing at Full Precision: Revisiting Clustering for Vector Embeddings

This paper demonstrates that applying dimensionality reduction, quantization, and dimension pruning before clustering allows vector embeddings to be indexed with 1-bit codes, achieving near-optimal search quality while reducing storage requirements by 60x and accelerating clustering time compared to full-precision methods.

Original authors: Leonardo Kuffo, Peter Boncz

Published 2026-08-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Leonardo Kuffo, Peter Boncz

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the modern digital world, computers are increasingly asked to find meaning in vast oceans of data. When a user searches for a song, a product, or a similar image, the system does not simply look for an exact match of words or pixels. Instead, it translates every item into a long list of numbers, known as an embedding, which captures the essence of that item's meaning. These lists are so long and the collections so huge that finding the most similar items by checking every single one is impossible. To solve this, engineers use a method called clustering. Imagine sorting a massive library not by reading every book, but by grouping them into piles based on their general themes. Once the books are grouped, a search only needs to look inside the most relevant piles, ignoring the rest. This process of grouping is the backbone of many modern search systems, allowing them to deliver results in a fraction of a second. However, building these groups is a slow and expensive task, often requiring the computer to hold the entire library in its memory at once and perform billions of calculations to decide where each book belongs.

A team of researchers at CWI in Amsterdam has discovered that this expensive process is far more wasteful than necessary. For years, systems have built these groups using the most precise, detailed version of the data possible, treating every single number in the long lists with extreme care. The researchers found that this level of precision is excessive. They demonstrated that the computer can build these groups just as well using a much cruder, compressed version of the data. By simplifying the numbers before the grouping begins, they were able to shrink the memory required for the task by sixty times. More surprisingly, this simplification did not make the groups worse. The resulting clusters were nearly identical to those built with the full, detailed data, allowing the system to find the right answers just as reliably.

The study tested this idea on massive collections of data, including millions of text embeddings and image descriptions. The researchers applied three different methods to simplify the data before the grouping started. One method reduced the length of the number lists, another compressed the numbers themselves into smaller codes, and a third removed unnecessary parts of the data. They found that even the most aggressive compression, which reduced the data to just a single bit per number, produced groups that were less than one percent different from the ideal. This tiny difference was so small that it had no noticeable impact on the final search results. In fact, using these simplified numbers made the grouping process significantly faster, sometimes up to seventeen times quicker, because the computer had less information to juggle and could use its processing power more efficiently.

One of the most striking findings was how resilient the grouping process is to these shortcuts. When the researchers looked at how the data points were assigned to their groups, they saw that the most important decision—choosing the closest group—was rarely confused by the simplification. The gap between the best group and the second-best group was usually so large that even a rough estimate could easily tell them apart. This means that the system does not need perfect precision to make the right choice; it only needs enough clarity to see the obvious winner. This insight allowed the team to combine different simplification techniques, such as shrinking the data lists and compressing the numbers, to achieve even greater speed and storage savings without sacrificing quality.

The researchers also explored how to handle the final step of the process. Once the groups are formed, the system needs to know where to find the original items. They showed that the same simplified data used to build the groups could be used to store the final index, eliminating the need to go back and retrieve the original, heavy data files. This creates a streamlined pipeline where the data is simplified once and then used for both building the index and searching it. While some methods, like a specific type of one-bit compression, occasionally created slightly uneven groups, the researchers found that a simple adjustment in the final step could fix this issue. The result is a system that is not only faster to build but also much cheaper to run, as it requires far less memory and computing power.

This work challenges the long-held assumption that high-quality search indexes must be built with high-precision data. The study proves that for the specific task of grouping vectors, the extra detail is often just noise. By embracing approximation early in the process, systems can handle larger datasets with greater ease. The researchers have made their tools available to the public, allowing others to test these methods on their own data. As the demand for searching through massive amounts of information continues to grow, these findings offer a practical path forward: a way to make search systems faster, cheaper, and more scalable without losing the accuracy that users rely on. The future of vector search may not lie in calculating every detail with perfect precision, but in knowing exactly which details can be safely left out.

Technical Summary: Stop Indexing at Full Precision: Revisiting Clustering for Vector Embeddings

Problem Statement

Approximate Vector Similarity Search (VSS) relies heavily on clustering algorithms, such as $k$ -means, to partition large collections of high-dimensional vectors into clusters. These clusters serve as entry points for partition-based indexes (e.g., Inverted File Indexes), significantly reducing search latency by avoiding the need to scan the entire dataset. However, the construction of these indexes is a critical bottleneck. Unlike VSS queries, which prune most of the collection, clustering requires accessing the entire raw vector collection multiple times. This process is both memory-bound and heavily compute-bound, often preventing users from querying a collection until the index is fully built.

Current systems typically index vectors at full precision (float32 or float16) during the clustering phase, applying quantization or dimensionality reduction only after the centroids are computed. This paper argues that using full-precision vectors for clustering is excessive. It posits that approximation techniques widely used in vector search can be applied before clustering to drastically reduce storage footprints and accelerate the indexing pipeline without sacrificing the quality of the resulting centroids.

Methodology

The authors propose a novel indexing pipeline where dimensionality reduction, quantization, and dimension pruning are applied to the raw vectors prior to the clustering process. The pipeline consists of the following stages:

Preprocessing (Approximation First):
- Dimensionality Reduction: Techniques include Johnson-Lindenstrauss Transform (JLT), Principal Component Analysis (PCA), and utilizing Matryoshka embeddings (which naturally concentrate energy in front dimensions).
- Quantization: The paper adapts several quantization schemes for pre-clustering use:
  - SQ8/SQ4: Global bias and scaling allow for direct integer arithmetic distance calculations.
  - LVQ4 (Local Vector Quantization): The authors derive a mathematical reformulation of the L2 distance that fuses reconstruction and distance calculation, enabling the use of 4-bit GEMM kernels while handling per-vector bias and scale.
  - RabitQ: A 1-bit quantization method based on random rotation and sign preservation. The authors adapt the unbiased estimator for L2 distance to work within the clustering loop, encoding data points with 1-bit codes and centroids with SQ4.
- Dimension Pruning: The authors integrate SuperKMeans, which interleaves General Matrix Multiplication (GEMM) routines with progressive pruning kernels. This technique uses the front dimensions to filter candidates, reducing the number of full distance calculations required.
Clustering:
- The $k$ -means algorithm (Lloyd's algorithm) is executed on the approximated vectors.
- Centroid Initialization: Random sampling is used, as $k$ -means++ was found to offer marginal improvements at a high runtime cost for embedding datasets.
- Assignment: Distance calculations are performed using the approximated representations (e.g., 4-bit GEMM, FastScan for RabitQ).
- Update: Centroids are updated by averaging assigned vectors. For quantized schemes, this involves fusing decoding and averaging, then re-encoding the new centroid.
Index Materialization:
- The final centroids are materialized as float32 vectors for the IVF index. The paper notes that these can be recomputed from the raw vectors (if available) or derived from the quantized codes.

Key Contributions

Pipeline Redesign: The authors shift the paradigm from "Cluster then Quantize" to "Quantize then Cluster," demonstrating that approximation techniques can be applied early in the indexing pipeline.
Algorithmic Adaptations:
- Adaptation of LVQ and RabitQ for the many-to-many distance calculations inherent in clustering, including specific derivations to handle per-vector parameters and 1-bit codes efficiently.
- Integration of SuperKMeans (dimension pruning) with various quantization schemes (SQ, LVQ, RabitQ), overcoming previous limitations where pruning required full-precision L2 distances.
Empirical Evaluation: A comprehensive evaluation across six diverse vector embedding datasets (Cohere, OpenAI, arXiv, Jina, MXBAI, ImageNet) measuring clustering quality (Recall@k, WCSS), storage reduction, and build time.

Results

The experiments reveal that clustering is highly resilient to approximation techniques:

Quality Preservation: Even aggressive approximations yield near-optimal clustering quality.
- SQ8 achieves parity with full-precision clustering.
- LVQ4 and RabitQ (1-bit codes) achieve clustering quality within 1% of the ideal (full-precision) result.
- PCA is identified as the most effective dimensionality reduction technique; preserving 60–70% of variance is sufficient to maintain near-optimal quality.
Storage Reduction: The proposed pipeline reduces the storage footprint required for clustering iterations by up to 60x (using RabitQ with PCA).
Performance Gains:
- Speedup: Clustering speed improves significantly. RabitQ combined with SuperKMeans achieves up to 17x speedup on the Cohere dataset.
- Hierarchical $k$ -means: When combined with RabitQ, hierarchical clustering achieves up to 91x speedup compared to vanilla $k$ -means on full-precision data.
- Scalability: The pipeline scales sublinearly with the number of clusters ( $k$ ), allowing the construction of indexes for 50M vectors with 200K clusters in under one minute.
Trade-offs:
- PQ (Product Quantization) struggles when applied before clustering because it builds a global codebook on raw vectors rather than residuals, leading to lower quality.
- RabitQ introduces a slight imbalance in cluster sizes due to systematic reconstruction bias in peripheral clusters, though this can be mitigated by using raw vectors in the final iteration.

Significance and Claims

The paper claims that the standard practice of indexing at full precision is unnecessary and inefficient. By moving approximation techniques to the front of the pipeline, systems can achieve:

Drastic Resource Savings: Reducing memory footprint by 60x and compute time by up to 91x.
Maintained Index Quality: The resulting centroids guide vector search with negligible degradation (often <1% loss in recall).
Unified Representations: The same approximated representations can be used for both the clustering phase and the final vector search index, streamlining data ingestion and eliminating the need for round-trips to raw data during index materialization.

The authors conclude that this approach is particularly vital for large-scale cloud vector systems where compute time directly impacts billing and ingestion latency is a critical bottleneck. They suggest that future work should explore specialized hardware (e.g., Intel AMX) and graph-based assignment strategies to further optimize this pipeline.