IVF vs HNSW

11 câu hỏi đã được viết

1

안녕하세요 도현님. 좋은 질문 감사드립니다.

일반적인 RAG 시스템을 만들때는 기본적으로 HNSW를 인덱스로 선택하는 경우가 많습니다. 실제로 여러 벡터 DB와 검색 엔진에서 HNSW를 기본 인덱스로 제공하고 있습니다.

HNSW의 장점은 보통 동일한 Recall(실제로 유사한 벡터들 중 얼마나 많이 찾아내는지)을 목표로 할 때 IVF보다 빠르게 검색할 수 있다는 것입니다. 그래프를 따라 가까운 벡터가 있을 가능성이 높은 영역을 탐색하기 때문에 클러스터 경계로 인한 누락 문제도 상대적으로 적습니다. 다만 벡터뿐만 아니라 각 벡터의 이웃을 나타내는 그래프 연결 정보도 저장해야해서 인덱스의 메모리 오버헤드가 크다는 단점이 있습니다. 신규 데이터를 삽입할 때도 가까운 노드를 탐색하고 그래프의 연결 관계를 구성해야 해서 일반적으로 IVF보다 삽입 비용이 큽니다.

그래서 데이터 규모가 커져서 메모리 비용이나 데이터 삽입 비용이 중요해지면 IVF를 고려하게됩니다. IVF는 인덱스 구조의 메모리 오버헤드가 비교적 작고, 신규 벡터를 가까운 클러스터에 추가하는 방식이어서 일반적으로 삽입 비용도 HNSW보다 작습니다. 다만 IVF는 인덱스를 만들기 전에 데이터의 분포를 바탕으로 클러스터 중심점을 학습하는 과정이 필요하고, 데이터 분포가 크게 달라지면 클러스터 중심점을 다시 학습하고 인덱스를 재구성해야 할 수도 있다는 단점이 있습니다.

참고로 실무에서는 데이터가 수백만~수천만 개 이상으로 늘어나서 메모리 비용이 더욱 중요해지면, 벡터를 압축하는 PQ를 IVF나 HNSW와 함께 사용하거나 대규모 인덱스의 주요 데이터를 SSD에 저장하도록 설계된 DiskANN 같은 방식도 고려합니다.

강의에서는 인덱스 구성에 관한 기본적인 내용만 다루었는데요. 실제 인덱스를 선택할 때는 위에서 언급한 메모리 사용량 같이 고려해야 할 점이 많습니다. 그래서 사용하려는 벡터 DB의 공식 문서를 읽고, 가능하다면 실제 데이터와 쿼리 패턴으로 테스트한 뒤에 인덱스를 선택하는 것이 가장 좋은 방법 같습니다. 한 가지 예시로 Milvus의 인덱스 선택 가이드가 잘 정리되어 있어서 참고해 보시면 좋을 것 같습니다!

감사합니다.