How Vector Search Actually Works: IVF and HNSW

개요

벡터 검색은 임베딩 벡터의 유사도를 기준으로 대규모 데이터셋에서 가장 가까운 벡터를 찾는 기술로, RAG, 추천 시스템, 이미지 검색 등 다양한 분야에 활용됩니다. 높은 차원의 데이터 공간의 특성상 정확한 검색은 비효율적이므로, 실제 시스템에서는 근사치로 빠르게 결과를 찾는 Approximate Nearest Neighbor (ANN) 검색 알고리즘이 사용됩니다.

주요 내용

* ANN 검색의 필요성: 고차원 공간에서는 데이터 포인트 간의 거리가 거의 균일해져 트리 기반의 정확한 인덱스(Exact Index)가 효과를 발휘하지 못하고 결국 모든 데이터를 탐색하는 성능 저하를 초래합니다. 따라서 속도를 위해 정확성을 일부 희생하는 ANN 검색이 사용되며, 이는 주로 '재현율(Recall)'로 측정됩니다.
* 유사도 측정: 벡터 간의 '가까움'은 L2(유클리드 거리), 내적(Inner Product), 코사인 유사도(Cosine Similarity) 등 다양한 척도로 측정될 수 있습니다. 벡터를 단위 길이로 정규화하면 내적과 코사인 유사도는 같아지고 L2는 코사인 유사도의 함수가 되어, 대부분의 경우 정규화 후 코사인 유사도를 사용하는 것이 일반적입니다.
* IVF (Inverted File Index):
* 데이터셋을 k-means 알고리즘으로 nlist개의 클러스터로 분할하고, 각 클러스터의 중심(centroid)과 해당 클러스터에 속하는 벡터들의 목록을 저장합니다.
* 쿼리가 들어오면 쿼리 벡터와 가장 가까운 nprobe개의 클러스터 중심을 찾고, 해당 클러스터 내의 벡터들만 탐색하여 가장 가까운 벡터를 반환합니다.
* nlist (클러스터 수)와 nprobe (탐색할 클러스터 수)가 주요 튜닝 파라미터이며, nprobe를 높이면 재현율이 증가하지만 지연 시간도 늘어납니다.
* Product Quantization (PQ): IVF와 함께 사용되어 메모리 사용량을 크게 줄이는 압축 기법입니다. 벡터를 여러 부분으로 나누어 각 부분에 대한 코드북을 만들고, 각 부분의 가장 가까운 코드북 항목 인덱스만 저장하여 벡터를 압축합니다.
* HNSW (Hierarchical Navigable Small World graph):
* 계층적인 그래프 구조를 사용하여 검색합니다. 가장 상위 계층은 적은 노드와 긴 연결을 가지며, 하위 계층으로 갈수록 더 많은 노드와 짧은 연결을 갖습니다. 최하위 계층에는 모든 벡터가 포함됩니다.
* 검색은 최상위 계층에서 시작하여 쿼리 벡터에 가장 가까운 이웃을 따라 계층을 내려가면서 진행됩니다. 각 계층에서 더 이상 가까워질 수 없을 때 하위 계층으로 내려가는 방식으로, 마치 지도를 확대하듯 정밀도를 높여갑니다.
* M (각 노드의 이웃 수), ef_construction (빌드 시 이웃 탐색 깊이), ef_search (쿼리 시 후보 목록 크기)가 주요 튜닝 파라미터입니다. ef_search를 높이면 재현율이 향상되지만 속도는 느려집니다.
* IVF와 HNSW 선택 기준:
* HNSW: 최상의 속도-재현율 트레이드오프를 제공하며, RAM이 충분한 중소 규모 데이터셋에 적합합니다. 대부분의 벡터 데이터베이스에서 기본값으로 사용되는 경우가 많습니다.
* IVF (+PQ): 데이터셋이 매우 크거나 메모리가 제한적인 경우에 유리합니다. PQ 압축을 통해 낮은 메모리 사용량과 뛰어난 확장성을 제공하지만, 재현율 확보를 위해 nprobe 튜닝이 필요합니다.
* 실제 적용: pgvector, Qdrant, FAISS 등 다양한 시스템에서 IVF와 HNSW를 구현하거나 조합하여 제공합니다. 사용자는 이러한 시스템의 인덱스 타입을 선택하고 파라미터를 튜닝하여 성능을 최적화합니다.
* 튜닝 및 고려사항:
* 측정 기반 튜닝: 재현율 대비 지연 시간 곡선을 측정하여 목표 성능을 만족하는 최적의 파라미터 값을 찾는 것이 중요합니다.
* 필터링: 메타데이터 필터링과 벡터 검색을 결합하는 것은 복잡하며, 포스트 필터링(검색 후 필터링)은 결과 손실을 야기할 수 있고, 프리 필터링(필터링 후 검색)은 인덱스 효율성을 저하시킬 수 있습니다. 최신 벡터 데이터베이스는 효율적인 필터링 검색을 지원합니다.
* 단순 검색의 이점: 데이터셋이 수천 ~ 수만 개 규모로 작을 때는 IVF나 HNSW 같은 ANN 인덱스 없이 모든 벡터를 직접 비교하는 완전 탐색(brute-force)이 더 빠르고 정확하며 관리하기 쉽습니다.

시사점

IVF와 HNSW는 고차원 벡터 검색의 속도와 정확성 사이의 근본적인 트레이드오프를 해결하기 위한 핵심 알고리즘으로, 데이터의 규모와 메모리 제약, 그리고 요구되는 검색 성능에 따라 적절한 알고리즘과 파라미터 튜닝이 필수적입니다. 또한, 메타데이터 필터링과의 결합은 실제 시스템 구현 시 중요한 고려사항이 됩니다.