벡터 인덱스 & ANN — "수백만 개에서 밀리초 안에 찾기"

임베딩과 유사도 측정 방법을 알았다면, 이제 현실적인 문제에 직면합니다. 100만 개의 문서 벡터에서 가장 유사한 5개를 찾으려면 100만 번의 유사도 계산이 필요합니다. 이 페이지에서는 이 문제를 해결하는 벡터 인덱스의 동작 원리를 깊이 있게 다룹니다.

​

문제 정의: 왜 Brute Force는 안 되는가

문서 100만 개 × 768차원 벡터 × 코사인 유사도 계산
= 약 7.68억 번의 곱셈 + 덧셈

→ 단일 쿼리: ~100ms (참을 수 있음)
→ 초당 100 쿼리: ~10초/쿼리 (서비스 불가)
→ 문서 1억 개: 단일 쿼리도 ~10초 (서비스 불가)

​

Brute Force vs ANN: 정확도와 속도의 트레이드오프

참고 핵심 통찰: ANN이 가능한 이유는 벡터 공간에서 가까운 점들은 구조적으로 연결되어 있기 때문 입니다. 마치 친구의 친구는 나와도 비슷한 관심사를 가질 확률이 높은 것처럼, 벡터 공간에서도 이웃의 이웃은 나와도 가까울 확률이 높습니다.

​

HNSW (Hierarchical Navigable Small World) 상세

• Small World: 네트워크 이론에서 “6단계의 분리(six degrees of separation)“로 유명한 개념입니다. 대부분의 노드 쌍이 소수의 연결만 거치면 도달 가능한 그래프 구조를 말합니다. HNSW는 각 벡터(노드)를 가까운 벡터들과 연결하되, 일부 장거리 연결(shortcut) 을 추가하여 Small World 특성을 만듭니다. 이 덕분에 그래프의 어느 지점에서 시작해도 소수의 홉(hop)만으로 목표 근처에 도달할 수 있습니다.
• Navigable: 각 노드에서 쿼리 벡터에 더 가까운 이웃으로 탐욕적(greedy) 으로 이동하여 목표에 접근합니다. 마치 나침반만 보고 목적지를 향해 걷는 것처럼, 매 단계에서 “현재 위치보다 목표에 더 가까운 이웃”을 선택합니다.
• Hierarchical: 단일 레이어의 한계(시작점이 목표와 멀면 많은 홉이 필요)를 해결하기 위해, 밀도가 다른 여러 레이어를 쌓습니다.

​

계층적 그래프 구조

Layer 3 (최상위):  A ---- D           ← 소수의 노드, 넓은 연결
                   |      |
Layer 2:           A -- C -- D -- G    ← 중간 수의 노드
                   |  / |    | \  |
Layer 1:           A-B-C-E--D-F-G-H   ← 많은 노드, 촘촘한 연결
                   |/|\|/|\|/|\|/|\|
Layer 0 (최하위):  A B C E D F G H I J K  ← 모든 노드 포함

• 상위 레이어: 소수의 노드만 포함, 넓은 범위를 빠르게 이동 (고속도로)
• 중간 레이어: 중간 밀도, 방향을 좁혀감 (국도)
• 하위 레이어: 모든 노드 포함, 정밀한 탐색 (골목길)

​

검색 과정

1. 최상위 레이어에서 시작: 쿼리 벡터에 가장 가까운 노드를 찾음 (대략적 위치)
2. 한 레이어씩 내려감: 현재 위치에서 시작하여 더 가까운 이웃으로 이동
3. 최하위 레이어에서 정밀 탐색: 주변의 촘촘한 연결을 따라 최종 Top-K 확정

• Layer 3: 고속도로로 부산 진입 (KTX)
• Layer 2: 부산 시내에서 해운대 방향으로 이동
• Layer 1: 해운대구에서 특정 거리로 이동
• Layer 0: 거리에서 정확한 식당 찾기

​

핵심 파라미터

M=4 (적은 연결):   A--B--C--D     → 빠르지만 부정확 (지름길 부족)
M=16 (많은 연결):  A==B==C==D     → 정확하지만 메모리 사용 증가
                   |\\/||\\/|
                   E==F==G==H

주의 실무 주의: M과 ef_search를 무작정 높이면 메모리 사용량이 급증합니다. 100만 문서 + 768차원 + M=16 기준으로 약 4-6GB의 메모리가 필요합니다. M=64로 올리면 12-18GB까지 증가할 수 있습니다.

​

IVF (Inverted File Index): 클러스터링 기반 접근

​

동작 원리

1. 사전 클러스터링: 모든 벡터를 K개의 클러스터로 나눕니다. 이때 사용하는 K-means 알고리즘은 다음과 같이 동작합니다: (1) K개의 임의 중심점(centroid)을 선정, (2) 각 벡터를 가장 가까운 중심점에 할당, (3) 각 클러스터의 평균을 새 중심점으로 갱신, (4) 수렴할 때까지 (2)-(3)을 반복. 이 과정을 거치면 의미적으로 비슷한 벡터들이 같은 클러스터에 모이게 됩니다.
2. 검색 시: 쿼리 벡터와 K개 중심점(centroid)의 거리를 먼저 계산하여, 가장 가까운 nprobe 개의 클러스터만 탐색합니다. nprobe=1이면 가장 가까운 1개 클러스터만, nprobe=10이면 10개 클러스터를 탐색합니다. nprobe가 클수록 정확도는 높아지지만 속도는 느려집니다.

클러스터 1: [문서A, 문서B, 문서C]  ← 기술 문서
클러스터 2: [문서D, 문서E, 문서F]  ← 마케팅 문서
클러스터 3: [문서G, 문서H, 문서I]  ← 재무 문서
...
클러스터 K: [문서X, 문서Y, 문서Z]

쿼리: "AI 모델 성능" → 클러스터 1에 가장 가까움 → 클러스터 1만 탐색

​

HNSW vs IVF 비교

​

Databricks Vector Search: 서버리스 벡터 인덱스

​

사용자가 신경 쓸 필요 없는 것들

• 알고리즘 선택 (자동 최적화)
• 파라미터 튜닝 (M, ef 등)
• 인덱스 리빌드 (Delta 테이블 변경 시 자동 동기화)
• 인프라 관리 (서버리스)

​

사용자가 결정해야 하는 것

참고 핵심 장점: Databricks Vector Search의 Delta Sync Index는 소스 Delta 테이블이 변경되면 자동으로 인덱스를 업데이트 합니다. 별도의 인덱스 리빌드 파이프라인을 구축할 필요가 없습니다.

다음: 벡터 검색(Dense)만으로는 부족한 경우가 있습니다. 키워드 기반 검색의 왕, BM25를 알아봅시다 → BM25 & 키워드 검색