A Comparative Study of Vector Indexing Strategies Using Facebook AI Similarity Search as a Case Study

당신이 지금까지 쓰인 모든 책이 들어 있는 도서관에 서 있다고 상상해 보세요. 하지만 이 책들은 제목이나 저자별로 정리되어 있지 않습니다. 대신, 서로 얼마나 "유사한지"에 따라 분류되어 있습니다. 만약 당신이 용감한 고양이에 대한 이야기를 찾아달라고 요청한다면, 사서는 단순히 "용감한"과 "고양이"라는 단어가 들어 있는 책을 찾는 것이 아니라, 비록 단어는 다를지라도 그 아이디어와 '느낌'이 유사한 이야기들을 찾아냅니다. 이것이 현대 인공지능의 마법입니다. 아이디어를 숫자 리스트(벡터라고 불리는)로 변환한 다음, 방대한 데이터의 바다 속에서 가장 가까운 일치 항목을 찾아내는 것입니다.

하지만 여기 함정이 있습니다. 만약 당신의 도서관에 10억 권의 책이 있다면, 최적의 일치 항목을 찾기 위해 모든 책을 하나하나 확인하는 것은 영원히 걸릴 것입니다. 이는 마치 해변에서 모래알 하나를 찾기 위해 모래알을 하나씩 전부 집어 드는 것과 같습니다. 이를 해결하기 위해 과학자들은 "인덱스(index)"라는 것을 발명했습니다. 이는 컴퓨터가 지루한 부분을 건너뛰고 흥미로운 부분으로 바로 뛰어들 수 있게 도와주는 특별한 지름길입니다. 어떤 지름길은 매우 정교하게 조직된 지도(정확한 탐색)와 같고, 다른 지름길은 순식간에 99%까지 도달하는 영리한 추측 게임(근사 탐색)과 같습니다. 큰 질문은 이것입니다: 어떤 지름길이 가장 좋을까요? 당신의 도서관 규모에 따라 달라질까요? 아주 작은 공책을 가지고 있느냐, 아니면 거대한 창고를 가지고 있느냐에 따라 달라질까요?

이것이 바로 아르메니아 유럽 대학교의 연구진이 밝혀내고자 했던 핵심입니다. 그들은 FAISS(Facebook AI Similarity Search)라고 불리는, 이러한 벡터 지름길들을 위한 스위스 아미 나이프(다용도 칼)와 같은 인기 있는 툴킷을 가져와 그 도구들을 테스트했습니다. 그들은 데이터가 거대해지고, 숫자가 복잡해지며, 메모리가 부족해질 때 각 도구가 얼마나 잘 작동하는지 확인하고자 했습니다. 이것은 서로 다른 유형의 검색 엔진들이 누가 가장 빠르게, 그리고 숨이 차지 않은 채로 정답을 찾는지 경쟁하는 거대한 경주와 같습니다.

연구진은 "브루트 포스(brute force)" 방식(모든 것을 확인하는 방식)부터 클러스터링(유사한 항목들을 그룹화하는 것), 압축(공간을 절약하기 위해 데이터를 찌그러뜨리는 것), 그래프 기반 탐색(연결망을 이용해 정답을 향해 점프하는 것)을 포함한 여러 가지 전략을 테스트했습니다. 그들은 두 가지 주요 지표를 측정했습니다: **재현율(Recall, 정답을 찾았는가?)**과 지연 시간(Latency, 얼마나 오래 걸렸는가?).

실험을 통해 발견한 내용은 다음과 같습니다:

"브루트 포스"의 챔피언 (IndexFlat)
단 한 명의 용의자도 놓치지 않으려 모든 용의자를 대조하는 형사를 상상해 보세요. 이것이 IndexFlat 방식입니다. 연구진은 이 접근 방식이 완벽하다는 것을 발견했습니다. 결코 정답을 놓치지 않습니다(재현율 100%). 하지만 믿을 수 없을 정도로 느립니다. "용의자"(벡터)의 수가 1,000개에서 10,000개로 늘어남에 따라, 답을 찾는 데 걸리는 시간도 꾸준히 증가했습니다. 데이터셋이 작다면 이 방식은 훌륭합니다. 하지만 수백만 개의 벡터를 다룬다면, 이 방식은 현실 세계에서 사용하기에는 너무 느려집니다. 그것은 마치 건초더미에서 바늘을 찾기 위해 현미경을 사용하는 것과 같습니다. 효과는 있지만, 시간이 너무 오래 걸립니다.

"그룹화" 전략 (IVFFlat)
다음으로, 그들은 벡터를 "모험", "로맨스", "미스터리"라고 라벨이 붙은 빈(bin)에 분류하는 것처럼 유사한 벡터들을 클러스터로 묶는 방법을 시도했습니다. 이것이 IndexIVFFlat입니다. 쿼리가 들어오면 시스템은 정답이 포함될 가능성이 가장 높은 빈들만 확인합니다. 연구는 이것이 아주 훌륭한 절충안임을 보여주었습니다. 모든 것을 확인하는 것보다 훨씬 빠르며, 더 많은 빈을 확인하도록 설정(tuning)하여 정확도를 높일 수 있습니다. 연구진은 더 많은 클러스터를 확인할수록(nprobe라고 불리는 설정) 결과는 좋아지지만, 시간이 조금 더 걸린다는 것을 발견했습니다. 이는 중대형 데이터셋에 대해 속도와 정확도의 균 l을 잘 맞추는 유연한 도구입니다.

"압축" 전문가 (IVFPQ 및 IVFSQ)
만약 10억 개의 벡터가 있지만, 그것들을 모두 저장할 하드 드라이브 공간이 부족하다면 어떻게 될까요? 연구진은 고화질 영화를 더 작은 파일 크기로 압축하는 것과 같은 IndexIVFPQ와 IndexIVFSQ를 살펴보았습니다. 이들은 데이터를 압축하여 메모리를 적게 사용하도록 만듭니다.

• IVFPQ (Product Quantization)는 벡터를 아주 작은 조각으로 나누어 압축합니다. 연구 결과, 이 방식은 메모리가 가장 큰 문제인 거대 데이터셋에서 챔피언입니다. 매우 빠르고 공간을 아주 적게 사용하지만, 가끔 완벽한 정답을 놓칠 수도 있습니다(약간 낮은 재현율).
• IVFSQ (Scalar Quantization)는 압축의 더 단순한 버전입니다. 이것은 좋은 "중간 단계"입니다. 공간을 절약하고 압축되지 않은 버전보다 빠르지만, IVFPQ만큼 공격적으로 압축하지는 않습니다. 연구진은 압축되지 않은 버전에 비해 정확도가 약간 떨어지지만, 대규모 시스템에서는 메모리 절감 효과가 그만한 가치가 있다는 점을 언급했습니다.

"연결의 웹" (HNSW)
마지막으로, IndexHNSW가 있었습니다. 이것은 급행 노선과 완행 노선이 있는 지하철 노선도처럼 데이터를 다층 구조의 웹으로 구성합니다. 당신은 일반적인 방향을 잡기 위해 상위 레이어(급행 노선)에서 시작하여, 정답을 찾을 때까지 레이어를 하나씩 내려가며 좁혀나갑니다. 연구는 이 방식이 속도와 정확도 면에서 전반적인 슈퍼스타라는 것을 발견했습니다. 이 방식은 "매우 빠르고" "매우 높은" 재현율을 가집니다. 하지만 웹을 구축하는 데 더 많은 메모리가 필요하며, 연구진은 이를 세밀하게 조정해야 한다고 언급했습니다. 웹을 너무 밀도 있게 만들면(연결이 너무 많으면) 검색이 느려지고, 너무 희소하게 만들면 최선의 답을 놓칠 수 있습니다. 하지만 제대로 조정된다면, 속도와 정밀함 사이에서 최고의 균형을 제공합니다.

결론
논문은 모든 작업에 적합한 단 하나의 "최고" 도구란 없다고 결론짓습니다. 이것은 망치, 드라이버, 렌치가 각각 무엇을 만드는 데 가장 좋은지 묻는 것과 같습니다. 그것은 당신이 무엇을 만들고 있느냐에 달려 있습니다.

• 데이터셋이 작고 완벽한 정확도가 필요하다면, Flat 인덱스를 사용하세요.
• 중간 규모의 데이터셋에서 균형이 필요하다면, IVFFlat이 견고한 선택입니다.
• 수십억 개의 벡터를 다루고 있고 컴퓨터의 메모리가 부족하다면, IVFPQ가 당신의 가장 친한 친구가 될 것입니다.
• 높은 정확도와 함께 가능한 가장 빠른 검색이 필요하고 충분한 메모리가 있다면, HNSW가 승자입니다.

연구진은 또한 "유사성"을 측정하는 다양한 방법(예: 공간에서 두 점이 얼마나 가까운지)을 테스트했습니다. 그들은 특정 유형의 AI 모델(언어 모델 등)의 경우, 수학적 계산이 올바르게 작동하도록 먼저 데이터를 정규화(normalize)해야 한다는 점을 확인했습니다. 하지만 일단 정규화가 완료되면, 서로 다른 인덱싱 전략들이 잘 작동한다는 것을 확인했습니다.

요약하자면, 이 연구는 AI 시스템을 구축하려는 모든 이들에게 실질적인 가이드를 제공합니다. 우리는 완벽한 속도, 완벽한 정확도, 그리고 제로에 가까운 메모리 사용량을 동시에 가질 수는 없지만, 우리의 구체적인 필요에 맞는 최적의 절충안을 선택할 수 있다는 것을 알려줍니다. 당신이 은행을 위한 부정 결제 탐지 시스템을 만들든, 의료 기록을 위한 검색 엔진을 만들든, 이 툴킷 안에는 건초더미에서 바늘을 찾을 때 길을 잃지 않도록 도와줄 특정 인덱싱 전략이 있습니다.