Source-linked AI summary
Stop Indexing at Full Precision: Revisiting Clustering for Vector Embeddings
Leonardo Kuffo, Peter Boncz
TL;DR
Clustering은 vector indexing에서 계산량과 메모리 사용량이 큰 병목이지만, 이를 다룬 연구는 상대적으로 적다. 이 논문은 Clustering 전에 근사 기법을 적용하고, 1-bit code가 storage를 60x 줄이면서도 거의 최적의 품질을 달성함을 보인다.
문제
Clustering은 계산량과 메모리 사용량이 큰 vector indexing 병목이지만, 상대적으로 연구가 적게 이루어졌다.
방법
제안하는 pipeline은 Clustering 전에 dimensionality reduction과 quantization을 적용하고, Clustering 중에는 dimension pruning을 사용한다.
결과
1-bit RabitQ code를 사용하면 Clustering 품질 저하를 1% 미만으로 유지하면서 storage를 60x 줄일 수 있다.
시사점 및 한계
Clustering에 full-precision vector를 사용하는 것은 과도하며, 근사 기법은 거의 최적의 Clustering 품질을 유지하면서 indexing을 크게 가속할 수 있다.
시사점 및 한계
AI embedding model, multi-vector embedding, graph-based index를 넘어선 적용 가능성은 아직 평가되지 않았다.
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 서론
이 논문은 clustering 기반 vector indexing에서 full-precision vectors가 불필요하다고 주장하며, index quality를 희생하지 않고 storage를 줄이고 성능을 향상하기 위해 reduction, quantization, dimension pruning을 사용하는 preprocessing pipeline을 소개한다.
- 동기: Clustering은 memory- 및 compute-intensive하고 전체 raw-vector collection에 반복적으로 접근하기 때문에 index construction의 병목이 된다. 이는 대부분의 vector를 prune하는 query-time VSS와 대조된다.Clustering이 approximate vector similarity search를 유도하는 centroids를 생성하는 역할을 하더라도 이 병목은 지속된다.
- 주요 결과: PCA-projected vectors에 대한 1-bit RabitQ codes는 near-optimal clustering quality를 달성하며, full-precision vectors보다 degradation은 1% 미만이고 storage는 60x 낮다.Figure 1은 60x storage reduction과 향상된 clustering speed를 포함해 near-optimal quality를 보고하며, index quality를 저해하지 않으면서 SuperKMeans를 통해 추가적인 향상을 얻을 수 있음을 보인다.
- 접근법: 제안하는 indexing pipeline은 clustering 전에 dimensionality reduction, quantization, dimension pruning을 적용해 index quality를 희생하지 않고 storage를 줄이고 indexing을 가속한다.연구 대상 기법에는 JLT, PCA, Matryoshka vectors, SQ, LVQ, RabitQ, PQ 및 dimension-pruning methods가 포함된다.
- 접근법: 이 연구는 SuperKMeans [42]와 ADSampling [22]을 적용해 dimension pruning을 quantization과 통합하고, quality를 희생하지 않으면서 clustering을 더욱 가속한다.이러한 적용은 결과 index quality를 유지하면서 더 빠른 clustering을 달성하는 것을 목표로 한다.
2 사전 지식
근사 최근접 이웃 검색은 정확성을 실용적 효율성과 맞바꾸며, partition-based index는 vector를 clustering해 query를 유도한다. Clustering은 이러한 index를 가능하게 하지만 여전히 비용이 커서, clustering 전에 dimensionality reduction, quantization, pruning을 적용할 동기가 된다.
- 근사 최근접 이웃 검색(Approximate nearest-neighbor search, ANNS)은 계산 및 저장 비용 때문에 정확한 최근접 이웃 검색이 비현실적인 경우에도 충분히 정확한 결과를 반환한다.현대의 retrieval-augmented generation 및 recommender-system 애플리케이션은 일반적으로 ANNS 또는 vector similarity search를 사용한다.
- inverted file과 같은 partition-based index는 k-means로 vector를 clustering한 뒤 centroid를 검색하고 가장 가까운 cluster의 vector를 평가해 속도와 품질의 균형을 맞춘다.탐색하는 cluster 수가 검색 속도와 품질 사이의 trade-off를 조절한다.
- Clustering은 전체 collection 또는 대규모 subsample에 반복적으로 접근하므로 index-construction bottleneck이 되며, graph-index construction보다 빠르더라도 query 제공을 지연시킨다.이 workload는 일반적으로 collection의 일부에만 접근하는 vector search와 다르다.
- Lloyd k-means는 centroid를 초기화하고, pairwise distance를 사용해 모든 vector를 가장 가까운 centroid에 할당하며, 할당 결과를 평균내 centroid를 갱신하고, 종료할 때까지 이를 반복한다.assignment 단계가 주요 bottleneck이며 GEMM으로 효율적으로 구현된다. 일반적인 vector-embedding workload는 최종 할당 전에 5–10회 iteration을 사용한다.
- 기존 연구는 clustering 비용을 줄이기 위해 dimensionality reduction, quantization 또는 dimension pruning을 적용하지만, quantization은 품질을 저하시킬 수 있고 이들의 combined use는 여전히 불명확하다.기존 pipeline은 일반적으로 projection 또는 quantization 전에 full-precision vector를 index하므로, pipeline의 더 이른 단계에서 approximation을 적용할 동기가 된다.
3 OUR PIPELINE: 먼저 근사화한 뒤 클러스터링
제안하는 pipeline은 클러스터링 전에 dimensionality reduction과 quantization을 적용하며, dimension pruning을 통해 클러스터링 중 거리 계산을 줄인다. 전처리 후 raw vector에 접근하지 않고도 approximate domain에서 클러스터링과 최종 assignment를 수행할 수 있다.
- Pipeline 설계: 이 pipeline은 full-precision vector를 클러스터링한 뒤 quantization하는 시스템과 달리, 클러스터링 전에 dimensionality reduction과 quantization을 수행한다 [16] [60] [72].Dimension pruning은 클러스터링 중 거리 계산을 추가로 줄인다.
- Quantization 방법: SQ8과 SQ4는 integer domain에서 거리 계산과 centroid averaging을 가능하게 하는 반면, LVQ4는 decoding을 거리 계산과 결합하고 평균화된 centroid를 다시 encode한다.각 vector가 고유한 scale과 bias를 가지므로 LVQ code는 직접 평균화할 수 없다.
- Quantization 방법: RabitQ는 unbiased L2-distance estimator를 사용하는 1-bit sign code를 활용하며, cached scalar factor는 반복되는 k-means 계산을 amortize한다.이 pipeline은 RabitQ의 binary code를 SQ4 residual quantization 및 효율적인 거리 계산을 위한 FastScan lookup table과 결합한다.
- Quantization 방법: Product quantization은 vector를 subspace로 나누고 code-to-code distance comparison을 사용한다. PQ4는 FastScan을 사용하는 반면 PQ8은 scalar lookup을 사용한다.PQ8은 subspace당 256개의 code를 제공하고 PQ4는 16개의 code를 제공한다.
- 거리 가속: SuperKMeans는 차원의 첫 12.5%에 GEMM을 적용하고 64차원마다 progressive pruning을 수행하며, L2 distance를 보존하고 신뢰할 수 있는 pruning을 지원하기 위해 rotation을 사용한다 [42] [22].Dimensionality reduction은 vector energy를 앞쪽 차원에 집중해 global variance를 보존하며, Matryoshka vector에도 적용된다 [45].
4 평가
평가는 양자화, 차원 축소, clustering 방법을 결합한 indexing pipeline의 clustering 품질, storage 감소율, clustering 속도를 측정한다. 결과는 여러 축약 표현이 vector-search 품질을 이상적인 수준에 가깝게 유지하면서 storage를 줄이거나 clustering을 가속하지만, PQ, RabitQ, graph-based assignment에서는 trade-off가 있음을 보여준다.
- 양자화: SQ8은 보고된 모든 측면에서 raw float32 clustering 품질과 일치하면서 storage를 4x 줄이고 SuperKMeans로 최대 8x speedups를 달성한다.Figure 5와 Table 3은 recall 및 cluster-quality metric을 포함해 IVF search를 위한 centroid 품질을 평가한다.
- 양자화: PQ는 storage를 가장 크게 줄이지만, clustering 전에 residual이 아니라 global codebook을 구축하기 때문에 recall과 cluster balance를 저하시킨다.이 내용은 cluster mean을 중심으로 한 residual이 아니라 raw vector에 product quantization을 적용한 것이 PQ의 품질 저하 원인이라고 설명한다 [16].
- Clustering 속도: Encoding과 constant-term preprocessing은 SQ, LVQ, RabitQ에서 무시할 수 있는 수준인 반면, PQ encoding은 speedup을 제한하고 partial-distance overhead는 LVQ와 RabitQ assignment를 느리게 한다.Table 4는 clustering 시간을 phase별로 나눈다. PQ4와 PQ8을 제외한 모든 기법은 SuperKMeans를 사용한다.
- 차원 축소: PCA는 variance의 60–70%만으로도 clustering 품질을 이상적인 수준의 1% 이내로 유지하며, variance의 80%를 유지하면 dimensionality가 3–4x 감소한다.PCA는 centroid 품질을 보존하는 데 가장 효과적인 dimensionality-reduction 방법으로 식별된다.
- 기법 결합: Cohere/1024에서는 PCA variance를 80% 보존한 LVQ가 raw-vector 품질을 유지하며, 최대 1% deviation을 허용할 수 있을 때는 variance를 80% 보존한 RabitQ가 선호된다.이 조합들은 Figure 9에서 품질, storage, speed의 trade-off를 평가한다.
- Clustering 방법: Graph-based assignment는 clustering을 가속하지만 덜 균형 잡힌 cluster를 생성하며, speed와 clustering 품질 사이의 trade-off를 만드는 ef_search tuning이 필요하다.ef_search를 너무 낮게 설정하면 품질이 저하되고, 너무 높게 설정하면 speed 개선 효과가 감소한다.
5 논의
대규모 cloud vector system에서는 compute가 billing에 영향을 미치므로 clustering에 full-precision vectors를 사용하는 것이 과도하다는 점을 논의한다. vector-search pipeline에서 사용되는 algorithm에 따라 method를 선택하고, clustering 전에 approximation technique을 적용할 것을 권고한다.
- 대규모 cloud vector system에서는 매 compute 초가 billing에 반영되므로 clustering에 full-precision vectors를 사용하는 것은 과도하다.
- clustering 전에 approximation technique을 적용하면 vector-indexing data-ingestion performance를 개선할 수 있다.
- approximation method의 선택은 vector-search pipeline에서 사용되는 algorithm에 따라 결정할 수 있다.
6 결론 및 향후 연구
제안한 pipeline은 clustering 전에 vector-search 근사 기법을 적용해, clustering 품질을 거의 최적 수준으로 유지하면서 최대 60x의 storage reduction과 상당히 빠른 clustering을 달성한다. 향후 연구에서는 hardware별 trade-off와 graph-based vector index를 다룬다.
- 결론: RabitQ, PCA, dimension pruning을 사용하면 clustering 품질을 거의 최적 수준으로 유지하면서 최대 60x의 storage reduction과 상당히 빠른 clustering을 달성할 수 있다.이 pipeline은 clustering 전에 이러한 근사 기법을 적용하며, clustering이 이들 기법에 매우 강건하다는 점을 확인한다.
- 향후 연구: 향후 연구에서는 Intel’s AMX와 같은 specialized hardware가 속도와 storage reduction 사이의 trade-off를 어떻게 변화시키는지 연구한다.
- 향후 연구: HNSW와 DiskANN 같은 graph-based index를 사용해 연구를 재현하는 방안은 graph-based vector index를 구현하는 시스템을 대상으로 제안된다.