Stop Indexing at Full Precision: Revisiting Clustering for Vector Embeddings

1 서론

• 클러스터링은 메모리와 연산 자원 모두에 제약을 받고 [41] [42] 원본 벡터 전체에 반복적으로 접근하므로, 인덱스 구축이 끝날 때까지 질의 처리의 병목이 된다.구축된 클러스터 중심점은 최근접 이웃이 있을 법한 클러스터로 질의를 유도해 대부분의 벡터에 접근하지 않도록 한다. 그런데도 클러스터링 기반 인덱싱에 대한 연구 관심은 상대적으로 적다.출처: §1 · p. 1
• 전체 정밀도 벡터 대신 PCA로 투영한 벡터의 1-bit RabitQ 코드를 사용하면 저장 공간을 60x 줄이면서 클러스터링 품질 저하를 1% 미만으로 유지할 수 있다.Figure 1은 10M개의 1024차원 Cohere 임베딩에서 클러스터링 성능을 비교한다.출처: Figure 1 · p. 1, §1 · p. 1
• 제안하는 파이프라인은 전체 정밀도 벡터를 클러스터링한 뒤 양자화하는 시스템들과 달리 [16] [60] [72], 클러스터링 전에 차원 축소, 양자화, 차원 가지치기를 적용한다.이 연구는 벡터 검색의 성능과 클러스터 품질에 영향을 미치는 파이프라인 설계 선택도 탐구한다.출처: §1 · p. 1
• 차원 가지치기 기법인 SuperKMeans [42]와 ADSampling [22]을 양자화와 결합하도록 조정하면 품질 저하 없이 클러스터링을 더욱 가속할 수 있다.Figure 1은 SuperKMeans가 인덱스 품질을 떨어뜨리지 않고 클러스터링 속도를 추가로 높인다는 점도 보여준다.출처: §1 · p. 1, Figure 1 · p. 1

2.1 벡터 검색

• 근사 벡터 검색은 연산량과 저장 공간 요구량을 줄이기 위해 부정확한 이웃을 허용하므로, RAG와 추천 등 많은 응용에서 정확 검색이 불필요하다.양자화 [3] [16] [21] [23] [93], 차원 가지치기 [22] [96], 차원 축소 [45] [47] [92]는 질의 시점의 비용을 줄인다. 그래프 인덱스는 거리 비교 횟수가 적지만 [53], 구축 시간이 길고 [42] [51] 갱신 [89]과 필터링 이 더 복잡하므로, 대규모 또는 분산 데이터 집합에서는 분할 기반 인덱스가 매력적이다 [48] [57] [77].출처: §2.1 · p. 2

2.2 벡터 검색에서 클러스터링의 역할

• 클러스터링은 그래프 인덱스 구축보다 수십~수천 배 빠르지만 여전히 인덱싱의 병목이므로, 지연 시간과 메모리 사용량이 적은 인덱싱이 필요하다 [51].IVF는 k-means 등의 방법으로 벡터를 클러스터링하고 [16] [33] 가까운 클러스터를 검색하며, 탐색하는 클러스터 수로 속도와 품질을 절충한다 [16]. 클러스터링은 데이터 집합에 반복적으로 접근하고 연산 성능에 크게 제약받으므로, 필터링된 유사도 조인에는 실행 중 즉석에서 수행하는 빠른 인덱싱이 매력적이다.출처: §2.2 · p. 2

2.3 벡터 시스템의 클러스터링

• 최근접 중심점 할당은 모든 점–중심점 간 거리를 계산하므로 클러스터링의 주된 병목이며, 최적화된 GEMM 루틴으로 효율적으로 구현된다.시스템은 Lloyd k-means [49] 또는 무작위 초기화를 사용하는 계층적 변형 을 사용한다. k-means++ [6]는 실행 시간이 상당히 늘어나는 데 비해 개선 폭은 작다 [42]. 갱신 단계에서는 할당된 벡터의 평균을 구하며, 큰 군집을 분할해 빈 군집을 대체할 수 있다 [33] [57]. 일반적으로 할당/갱신을 5–10회 반복한 뒤 최종 할당을 수행한다 [42].출처: §2.3 · p. 2

2.4 벡터 클러스터링 최적화 시도

• 차원 축소는 클러스터링의 메모리 사용량과 연산량을 줄이지만, 클러스터링 품질에 미치는 영향은 아직 충분히 연구되지 않았다.VectorChord는 클러스터링 전에 Johnson–Lindenstrauss Transform 을 적용하고, LindormVector 는 PCA로 앞쪽 차원에 에너지를 집중시킨다. Matryoshka 임베딩 [45]은 앞쪽 차원에 에너지가 집중되도록 학습된다.출처: §2.4 · p. 3
• PQk-means 는 클러스터링 품질을 희생해 메모리 사용량을 줄이고 거리 계산을 가속하는 반면, SuperKMeans는 차원 가지치기로 클러스터링 품질을 희생하지 않고도 속도를 크게 높인다 [42].PQk-means는 곱 양자화 를 사용한다. LVQ [3] [4]와 RabitQ [21] [23] [27]는 벡터 클러스터링에 사용된 바 없다. SuperKMeans는 GEMM 루틴과 가지치기 커널을 교차 실행한다.출처: §2.4 · p. 3
• 클러스터링 전에 근사를 적용하면 원본 데이터 순회 횟수와 메모리 요구량을 줄이면서 성능을 높이고 클러스터링 품질을 대부분 유지할 수 있다.기존 파이프라인은 최대 정밀도로 클러스터링한 뒤 벡터의 차원을 축소하거나 양자화한다. 벡터 클러스터링 최적화와 근사가 클러스터링 품질에 미치는 영향은 상대적으로 연구가 부족하다.출처: §2.4 · pp. 2–3

2.5 클러스터링 성능의 핵심 요소

• 양자화된 클러스터링의 성능은 효율적인 다대다 거리 계산과 작은 자료형에 대한 하드웨어 지원에 달려 있다.차원 축소는 차원 수를 줄여 최적화된 float32 GEMM을 가속하고, 가지치기는 거리 계산을 줄인다. 양자화의 이점은 8-bit 처리에 적합한 SIMD [13] [41] 또는 Intel AMX 같은 전용 하드웨어의 지원 여부에 달려 있다.출처: §2.5 · p. 3

2.6 클러스터링의 강건성

• 첫 번째와 두 번째로 가까운 중심점 사이의 상대적 L2 거리 격차가 두 번째와 세 번째로 가까운 중심점 사이보다 2-3x 더 크다는 점은 클러스터링이 벡터 검색보다 근사에 더 강건한 이유 중 하나다 [44].할당은 데이터 벡터를 질의로, 중심점을 검색 대상 집합으로 삼는 top-1 최근접 이웃 검색으로 이루어진다. 따라서 근사 오차로 최근접 중심점 할당이 달라질 가능성이 더 낮다.출처: Figure 3 · p. 3, §2.6 · p. 3

3 제안 파이프라인: 먼저 근사한 뒤 클러스터링

• 이 파이프라인은 클러스터링 전에 벡터를 근사하고, 클러스터링 중에 차원 가지치기를 적용하며, 투영 또는 양자화 공간에서 최종 할당을 수행할 수 있다.원본 정밀도의 벡터를 클러스터링한 뒤 양자화하는 시스템 [16] [60] [72]과 달리, 이 파이프라인은 전처리 후 원본 벡터에 접근할 필요가 없다.출처: §3 · p. 3, Figure 4 · p. 4

3.1 벡터 클러스터링을 위한 기법 조정

• 8비트 및 4비트 GEMM 루틴 은 정수 연산으로 SQ 거리를 직접 계산하며, 중심점은 양자화 영역에서 각 차원의 평균을 구해 갱신한다.모든 벡터가 동일한 변환 매개변수를 공유하므로 양자화 영역에서 직접 계산할 수 있다.출처: §3.1 · p. 4
• 4비트 GEMM 커널은 재정식화한 LVQ 거리의 일부를 계산하여, 다대다 비교 중 반복적인 float32 복원을 피한다.추가 스칼라 연산으로 거리 계산을 완성하며, N_x와 A_x는 반복 간에 캐싱하고 N_y는 반복마다 한 번 계산한다. LVQ 코드의 평균은 정의되지 않으므로, 중심점 갱신 시 디코딩과 평균 계산을 융합한 뒤 다시 인코딩한다.출처: §3.1 · p. 4
• 1비트 RabitQ로 데이터 포인트를, SQ4로 중심점을 인코딩하여 클러스터링 메모리의 대부분을 차지하는 데이터 포인트를 집중적으로 압축한다.데이터 벡터는 중심화, 정규화, 무작위 회전, 부호 양자화를 거친다. 데이터에만 의존하는 스칼라 계수는 반복 간에 캐싱하고, 중심점 계수는 반복마다 한 번 계산한다. FastScan 은 PSHUFB 로 32개 조회를 동시에 수행한다. 중심점 갱신은 디코딩과 평균 계산을 융합한 뒤 SQ4로 다시 인코딩한다.출처: §3.1 · pp. 4–5
• PQ4는 FastScan 을, PQ8은 스칼라 조회를 사용한다. 둘 다 코드 간 거리로 클러스터를 할당하고 PQk-means 의 희소 투표로 중심점을 갱신한다.부분공간당 PQ8은 256개 코드를, PQ4는 16개 코드를 제공한다. PQ8 코드는 PSHUFB와 호환되지 않는다.출처: §3.1 · p. 5
• 전체 차원의 12.5%로 SuperKMeans의 초기 GEMM 계산을 수행한 뒤, 남은 후보에 대해 64차원마다 점진적 가지치기 커널을 적용한다 [42].무작위 직교 회전은 L2 거리를 보존하면서 분산을 더 고르게 분포시켜 ADSampling [22]에 유리하게 한다. SQ8/SQ4는 float32 GEMM을 정수 GEMM으로 대체하지만, LVQ/RabitQ는 가지치기에 일부 차원에 대한 거리가 필요하므로 제약을 받는다.출처: §3.1 · p. 5
• 차원 축소 벡터와 Matryoshka 벡터는 float32를 유지하므로 추가 구현 작업 없이 통합되며, 에너지는 앞쪽 차원에 집중되어 있다.차원 축소는 전체 분산을 보존하며, Matryoshka 임베딩 모델은 이미 앞쪽 차원에 에너지가 집중된 벡터를 생성한다 [45].출처: §3.1 · p. 5

4.1 양자화 기법

• RabitQ와 SuperKMeans를 결합하면 최대 17x의 속도 향상을 얻으며, SQ8은 원본 벡터 클러스터링과 동등한 품질을, LVQ4와 RabitQ는 재현율 차이 1% 이내의 품질을 유지한다.SQ8은 저장 공간을 4x 절감하고 SuperKMeans와 함께 사용하면 최대 8x의 속도 향상을 제공한다. LVQ4와 RabitQ는 저장 공간을 각각 8x와 30x 절감한다. LVQ4는 압축률이 같은 SQ4보다 우수하다. RabitQ는 클러스터 균형을 약간 악화시키며, SuperKMeans 메타데이터로 인해 저장 공간 절감 효과가 약 10% 줄어든다.출처: Figure 5 · p. 6, Table 3 · p. 6, §4.1 · p. 6
• 마지막 반복에서 원본 벡터로 PQ 중심점을 갱신하면 Cohere의 재현율이 0.84에서 0.85로 높아지지만, 원본 벡터에 접근해야 한다.PQ는 저장 공간 절감 효과가 가장 크지만 재현율과 균형을 악화시킨다. 일반적인 적용 방식인 클러스터 중심 기준 잔차 대신 원본 벡터에 전역 코드북을 적용하기 때문이다 [16]. SQ, LVQ, RabitQ의 인코딩과 상수항 사전 계산 비용은 무시할 만하지만, PQ 인코딩은 속도 향상을 제한한다. LVQ와 RabitQ에서는 부분 L2 계산도 할당 시간의 상당 부분을 차지한다.출처: §4.1 · p. 7, Table 4 · p. 7
• 마지막 반복에서 원본 벡터로 RabitQ 중심점을 갱신하면 외곽 중심점의 복원 편향이 교정되어 모든 지표에서 이상적인 수준에 가까운 품질을 회복한다.바깥쪽으로 치우치는 복원 편향은 중앙 클러스터 내부에서는 대부분 상쇄되지만, 외곽 클러스터에서는 부호 패턴이 같은 방향으로 정렬되어 남는다. 이로 인해 경계점이 더 밀집된 클러스터로 유입되고 탐색하는 벡터 수가 늘어난다. 교정에는 원본 벡터 접근이 필요하므로, 원본 벡터가 느린 저장 장치에 있으면 실용적이지 않을 수 있다.출처: Figure 5 · p. 6, §4.1 · p. 7

4.2 차원 축소 기법

• PCA로 전체 분산의 60–70%를 보존하면 이상적인 수준과의 차이가 1% 이내인 클러스터링 품질을 얻으며, 평가한 데이터셋에서 JLT 투영과 Matryoshka 접두 벡터보다 중심점 품질을 잘 유지한다.분산의 80%를 보존하면 차원을 3–4x 축소하면서 최적의 품질을 달성한다. OpenAI, Jina, MXBAI에서 Matryoshka 접두 벡터는 JLT와 비슷한 성능을 보인다. 차원 축소에 따른 속도 향상은 선형에 못 미치지만, SuperKMeans는 20%–2x의 속도 향상을 제공하여 고차원 벡터도 품질 저하 없이 저차원 벡터에 견줄 만한 속도 향상을 얻는다. d < 128에서는 SuperKMeans를 비활성화한다 [42].출처: §4.2 · pp. 7–8
• 차원 축소 후 전체 차원의 중심점을 다시 계산하면 품질이 가장 좋지만, 보존한 분산이 크면 역투영한 중심점이나 투영 공간의 중심점도 이에 가까운 품질을 낸다.보고된 차원 축소 실험에서는 원본 벡터로 전체 차원의 중심점을 다시 계산한다. 대안들은 제거한 차원의 에너지를 잃지만 전처리 후 원본 벡터에 접근하지 않아도 된다. 다만 Matryoshka 벡터에는 역투영을 적용할 수 없다. PCA 전처리 비용은 클러스터링에 비해 무시할 만하며, Matryoshka 표현에는 필요하지 않다. 기존 투영 공간 검색 방식 [92]도 재순위화를 위해 PCA 잔차를 저장한다.출처: Table 6 · p. 8, §4.2 · p. 8

4.3 기법 결합

• Cohere/1024에서 PCA 분산의 80%를 보존할 때, 원본 벡터와 동등한 품질이 필요하면 LVQ가, 최대 1%의 품질 차이를 허용하면 RabitQ가 더 적합하다.최적에 가까운 품질과 속도를 함께 얻으려면 RabitQ와 SuperKMeans의 결합이 유리하다. PCA를 추가하면 부분 L2 계산이 가지치기에 부담을 주어 성능이 떨어질 수 있으며, 특히 저차원 벡터에서 두드러진다. SQ8은 SuperKMeans를 통해 일관되게 성능이 향상된다.출처: Figure 9 · p. 9, §4.3 · p. 9

4.4 기타 가속 기법

• 계층적 k-means와 RabitQ를 결합하면 최대 91x의 속도 향상을 얻지만, 클러스터가 더 균형 있게 형성되어 재현율이 낮아지고 더 많은 클러스터를 탐색해야 한다.그래프 기반 할당은 HNSW 같은 중심점 인덱스에서 top-1 검색을 수행한다. 기본 k-means를 가속하지만 클러스터 균형이 나빠지며, 속도와 품질 사이에서 ef_search를 조정해야 한다. 그래프 구축은 실행 시간의 0.1% 미만을 차지한다. 샘플링은 샘플 비율에 비례해 실행 시간을 줄이며 [42], 약 20–30%면 품질과 균형을 유지하기에 충분하다 [42]. 다만 최종 할당과 인덱스 생성에는 여전히 모든 벡터가 필요하다.출처: Table 7 · p. 9, §4.4 · p. 9, Table 8 · p. 9

4.5 확장성

• 50M개의 Cohere 임베딩에서 계층적 k-means와 RabitQ를 사용하면 200K개의 클러스터를 1분 미만에 학습한다.이 확장성 실험은 200GB의 임베딩, 512GB RAM, 64개 코어를 사용한다. 계층적 k-means와 RabitQ의 결합이 가장 빠르며, 계층적 k-means와 그래프 기반 할당 모두 클러스터 수가 늘어날 때 실행 시간이 선형 미만으로 증가한다.출처: Figure 10 · p. 10, §4.5 · p. 10

5 논의

• 클러스터링에는 전체 정밀도 벡터까지 필요하지 않으며, 근사 기법 을 먼저 적용하면 벡터 시스템의 데이터 적재 성능을 높일 수 있다.연산 시간이 요금에 직접 반영되는 대규모 클라우드 벡터 시스템 에서는 여전히 클러스터링이 선호되는 인덱싱 방법이다.출처: §5 · p. 10
• 근사 기법은 벡터 검색 파이프라인에 맞춰 선택해야 한다. LVQ 를 사용하는 시스템은 클러스터링 전에 벡터를 인코딩해야 한다.최근 연구에서 양자화와의 결합을 제안한 차원 축소에도 같은 원칙이 적용된다 [47] [78] [79] [92].출처: §5 · p. 10
• 검색과 클러스터링에 벡터 표현을 재사용하면 인덱싱과 데이터 적재가 간소화되며, 두 작업을 모두 효율적으로 지원하는 양자화 기법에 대한 연구 가능성이 열린다.제안한 설계에서는 동일한 표현으로 벡터 검색과 클러스터링을 모두 지원할 수 있다.출처: §5 · p. 10

• RabitQ, PCA, SuperKMeans 차원 가지치기를 사용하면 최적에 가까운 군집화 품질을 유지하면서 저장 공간을 최대 60x 줄이고 군집화를 크게 가속할 수 있다.이 파이프라인은 양자화 기법을 군집화에 맞게 조정하고 차원 가지치기와 통합해 군집화 전에 근사를 적용한다.출처: §6 · p. 10
• 향후 연구에서는 HNSW, DiskANN 같은 그래프 기반 인덱스로 본 연구를 재현할 계획이다.저자들은 그래프 기반 할당을 위해 서로 다른 그래프 인덱스를 평가하거나 이 용도에 맞춘 인덱스를 개발하는 방안도 제안한다.출처: §6 · p. 10
• Intel의 AMX처럼 특정 자료형을 위한 특화 하드웨어 연산 장치는 군집화 속도와 저장 공간 절감 사이의 절충 관계를 바꿀 수 있다.이러한 하드웨어 의존적 절충 관계의 탐색은 향후 연구 과제로 남아 있다.출처: §6 · p. 10
• 다중 벡터 임베딩 [38]과 SIFT, GIST처럼 AI 임베딩 모델에서 생성되지 않은 전통적인 데이터셋을 평가하면 파이프라인의 적용 범위를 넓힐 수 있다.출처: §6 · p. 10