IVF 클러스터링 기반 검색과 Product Quantization의 원리를 분석하고, IVF+PQ 조합의 대규모 데이터셋 최적화 전략과 메모리-정확도 트레이드오프를 다룹니다.
**IVF(Inverted File Index)**는 벡터 공간을 여러 개의 **보로노이 셀(Voronoi Cell)**로 분할하는 접근법입니다. 핵심 아이디어는 단순합니다. 전체 벡터를 K개의 클러스터로 나누고, 검색 시에는 쿼리 벡터와 가까운 클러스터만 탐색하여 검색 범위를 좁힙니다.
구축 과정은 다음과 같습니다.
import numpy as np
from sklearn.cluster import KMeans
def build_ivf_index(vectors: np.ndarray, n_clusters: int = 256):
"""IVF 인덱스 구축 (개념 설명용)"""
# 1. K-means로 클러스터링
kmeans = KMeans(n_clusters=n_clusters, random_state=42)
kmeans.fit(vectors)
# 2. 각 벡터를 클러스터에 할당
labels = kmeans.labels_
inverted_lists = {}
for idx, label in enumerate(labels):
if label not in inverted_lists:
inverted_lists[label] = []
inverted_lists[label].append(idx)
return kmeans.cluster_centers_, inverted_lists
def ivf_search(query, centroids, inverted_lists, vectors, nprobe=10, top_k=10):
"""IVF 검색"""
# 쿼리와 가장 가까운 nprobe개 클러스터 찾기
distances_to_centroids = np.linalg.norm(centroids - query, axis=1)
nearest_clusters = np.argsort(distances_to_centroids)[:nprobe]
# 선택된 클러스터의 벡터만 탐색
candidates = []
for cluster_id in nearest_clusters:
for vec_id in inverted_lists[cluster_id]:
dist = np.linalg.norm(vectors[vec_id] - query)
candidates.append((vec_id, dist))
# 상위 K개 반환
candidates.sort(key=lambda x: x[1])
return candidates[:top_k]nprobe는 검색 시 탐색할 클러스터 수를 결정합니다. 이 파라미터가 IVF의 recall-속도 트레이드오프를 직접 제어합니다.
| nprobe | 효과 |
|---|---|
| 1 | 가장 빠름, recall 매우 낮음 |
| 전체 클러스터의 5-10% | 일반적인 시작점 |
| 전체 클러스터의 20-30% | 높은 recall, 속도 감소 |
| 전체 클러스터 수 | Brute-force와 동일 (의미 없음) |
클러스터 수(nlist)는 보통 벡터 수의 제곱근 정도로 설정합니다. 100만 개의 벡터라면 nlist=1000 정도가 적절합니다. nprobe는 nlist의 5-10%에서 시작하여 recall을 측정하며 조절합니다.
장점:
단점:
**PQ(Product Quantization)**는 고차원 벡터를 압축하여 메모리 사용량을 극적으로 줄이는 기법입니다. 핵심 아이디어는 고차원 벡터를 여러 **서브벡터(subvector)**로 분할하고, 각 서브벡터를 독립적으로 양자화(quantize)하는 것입니다.
예를 들어 128차원 벡터를 8개의 16차원 서브벡터로 분할한다고 가정하겠습니다.
PQ의 압축률은 서브벡터 수(M)와 코드북 크기(K)에 의해 결정됩니다.
원본 벡터가 D차원 float32라면 D x 4 바이트입니다. PQ 코드는 M x log2(K) / 8 바이트입니다.
def pq_compression_ratio(
dimensions: int,
n_subvectors: int,
codebook_size: int = 256
) -> dict:
"""PQ 압축률 계산"""
import math
original_bytes = dimensions * 4 # float32
bits_per_code = math.log2(codebook_size)
pq_bytes = int(n_subvectors * bits_per_code / 8)
return {
"original_bytes": original_bytes,
"pq_bytes": pq_bytes,
"compression_ratio": original_bytes / pq_bytes
}
# 1536차원 벡터, 48개 서브벡터, 코드북 256 (8비트)
result = pq_compression_ratio(1536, 48, 256)
print(f"원본: {result['original_bytes']} bytes") # 6144 bytes
print(f"PQ: {result['pq_bytes']} bytes") # 48 bytes
print(f"압축률: {result['compression_ratio']:.0f}x") # 128x1536차원 벡터를 48개 서브벡터로 분할하면 128배 압축이 가능합니다. 10억 개의 벡터 기준으로 원본은 약 5.7TB이지만 PQ 압축 후에는 약 45GB로 줄어듭니다.
PQ는 손실 압축입니다. 압축률을 높일수록 recall이 떨어집니다. 서브벡터 수가 너무 적으면 (예: 1536차원에서 8개) 각 서브벡터의 차원이 커져 양자화 오차가 증가합니다. 서브벡터 수와 recall 사이의 균형을 찾는 것이 중요합니다.
PQ에서 거리를 계산할 때 가장 효율적인 방법은 **ADC(Asymmetric Distance Computation)**입니다. 쿼리 벡터는 원본 그대로 유지하고, 데이터베이스 벡터만 PQ 코드로 비교합니다.
검색 시 쿼리 벡터와 각 서브공간의 코드북 사이 거리를 미리 테이블로 계산해 두면, 개별 벡터와의 거리 계산이 테이블 룩업과 합산으로 대체됩니다. 이는 원본 벡터 비교보다 훨씬 빠릅니다.
IVF와 PQ를 결합하면 각각의 장점을 모두 활용할 수 있습니다.
import faiss
import numpy as np
# 인덱스 파라미터
dimension = 1536
n_clusters = 4096 # IVF 클러스터 수
n_subvectors = 48 # PQ 서브벡터 수
bits_per_code = 8 # 코드북 크기 = 2^8 = 256
# IVF+PQ 인덱스 생성
quantizer = faiss.IndexFlatL2(dimension)
index = faiss.IndexIVFPQ(
quantizer,
dimension,
n_clusters,
n_subvectors,
bits_per_code
)
# 학습 (클러스터링 + PQ 코드북)
training_data = np.random.randn(100000, dimension).astype("float32")
index.train(training_data)
# 벡터 추가
vectors = np.random.randn(1000000, dimension).astype("float32")
index.add(vectors)
# 검색
index.nprobe = 64 # 탐색할 클러스터 수
query = np.random.randn(1, dimension).astype("float32")
distances, indices = index.search(query, k=10)최근에는 IVF의 클러스터 선택 과정에서도 HNSW를 활용하는 IVF_HNSW 변형이 등장했습니다. 수만 개의 클러스터 중심점 중 가장 가까운 것을 찾을 때 HNSW 그래프를 사용하면, 클러스터 선택 자체도 빨라집니다.
**RaBitQ(Randomized Binary Quantization)**는 2024년에 제안된 양자화 기법으로, 벡터를 1비트로 극단적으로 양자화하면서도 높은 정확도를 유지합니다. 랜덤 회전을 통해 양자화 오차를 균등하게 분산시키는 것이 핵심입니다.
pgvector의 확장인 pgvectorscale에서 StreamingDiskANN 인덱스와 함께 RaBitQ를 채택하여, 50M 벡터 벤치마크에서 99% recall과 471 QPS를 달성한 바 있습니다.
양자화 기법은 빠르게 발전하고 있습니다. PQ가 표준이지만, RaBitQ, ScaNN의 Anisotropic Quantization 등 새로운 기법들이 더 나은 압축률-정확도 트레이드오프를 제공하고 있습니다.
IVF+PQ 조합에서 조절할 수 있는 주요 파라미터와 그 영향을 정리합니다.
| 파라미터 | 증가 시 효과 | 감소 시 효과 |
|---|---|---|
| nlist (클러스터 수) | 빌드 시간 증가, 세밀한 분할 | 각 클러스터 크기 증가 |
| nprobe (탐색 클러스터 수) | recall 향상, 지연시간 증가 | 속도 향상, recall 저하 |
| M_pq (서브벡터 수) | recall 향상, 메모리 증가 | 메모리 절약, recall 저하 |
| nbits (코드 비트 수) | recall 향상, 메모리 증가 | 메모리 절약, recall 저하 |
# 리랭킹 전략 예시 (Faiss)
import faiss
# 1단계: IVF+PQ로 후보 100개 추출 (빠르지만 근사)
index_ivfpq = faiss.IndexIVFPQ(quantizer, dim, nlist, m_pq, nbits)
index_ivfpq.nprobe = 32
distances_pq, candidates = index_ivfpq.search(query, k=100)
# 2단계: 원본 벡터로 100개 중 상위 10개 재정렬 (정확)
candidate_vectors = original_vectors[candidates[0]]
exact_distances = np.linalg.norm(candidate_vectors - query, axis=1)
top_10_indices = np.argsort(exact_distances)[:10]
final_results = candidates[0][top_10_indices]이번 장에서는 IVF의 클러스터링 기반 검색과 PQ의 벡터 압축 기법을 심층적으로 분석했습니다. IVF는 검색 범위를 클러스터 단위로 좁혀 속도를 높이고, PQ는 벡터를 수십에서 수백 배로 압축하여 메모리 부담을 크게 줄입니다. 이 두 기법의 조합인 IVF+PQ는 수십억 규모의 벡터 검색을 현실적인 비용으로 가능하게 합니다.
다음 장에서는 디스크 기반 ANN의 대표 주자인 DiskANN을 심층 분석합니다. 메모리에 모든 벡터를 올리지 않고도 10억 개 이상의 벡터를 효율적으로 검색하는 방법을 살펴보겠습니다.
이 글이 도움이 되셨나요?
DiskANN의 Vamana 그래프 아키텍처와 SSD 최적화 전략을 분석하고, 10억+ 벡터 스케일에서의 성능, Fresh DiskANN과 Filtered DiskANN을 다룹니다.
HNSW 알고리즘의 원리를 NSW 그래프에서부터 다층 구조까지 단계별로 분석하고, 핵심 파라미터 튜닝과 성능 특성, 적합한 사용 시나리오를 다룹니다.
Pinecone의 완전 관리형 아키텍처, 서버리스와 팟 배포 모델, 네임스페이스, 메타데이터 필터링, 하이브리드 검색, 보안 컴플라이언스, Python SDK 실습을 다룹니다.