> ## Documentation Index
> Fetch the complete documentation index at: https://docs.sifi.life/llms.txt
> Use this file to discover all available pages before exploring further.

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

> 이 문서는 **[RAG](/blog/guides/rag/overview)** 섹션의 일부입니다.

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

***

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

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

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

문서 수가 늘어나면 검색 시간이 **선형으로** 증가합니다. 실제 프로덕션 환경에서는 밀리초 단위의 응답이 필요하므로, 모든 벡터를 순차적으로 비교하는 Brute Force는 사용할 수 없습니다.

***

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

| 특성         | Brute Force (정확) | ANN (근사)             |
| ---------- | ---------------- | -------------------- |
| 정확도        | 100% (정확한 Top-K) | 95\~99% (근사 Top-K)   |
| 시간 복잡도     | O(n) — 문서 수에 비례  | O(log n) \~ O(n^0.5) |
| 100만 문서 검색 | \~100ms          | \~1-5ms              |
| 1억 문서 검색   | \~10s            | \~5-20ms             |
| 사용 시나리오    | 소규모 데이터, 평가용     | 프로덕션 서비스             |

**ANN (Approximate Nearest Neighbor)** 은 "100% 정확한 Top-5" 대신 "99% 확률로 정확한 Top-5"를 찾되, 속도를 수십\~수백 배 향상시킵니다. 실무에서 이 1%의 정확도 손실은 거의 무시할 수 있습니다.

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

***

## HNSW (Hierarchical Navigable Small World) 상세

HNSW는 현재 가장 널리 사용되는 ANN 알고리즘입니다. Databricks Vector Search, Pinecone, Weaviate 등 주요 벡터 데이터베이스가 내부적으로 HNSW를 사용합니다.

이름의 의미를 풀면 알고리즘의 핵심 원리가 드러납니다:

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

### 계층적 그래프 구조

HNSW는 데이터를 **여러 레이어의 그래프** 로 구성합니다:

```
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**                | 각 노드의 연결 수     | 높을수록 정확하지만 메모리 증가 (기본: 16) |
| **ef\_construction** | 인덱스 구축 시 탐색 범위 | 높을수록 인덱스 품질 향상, 구축 시간 증가   |
| **ef\_search**       | 검색 시 탐색 범위     | 높을수록 정확하지만 검색 느려짐 (기본: 64) |

```
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): 클러스터링 기반 접근

IVF는 FAISS(Facebook AI Similarity Search, Meta가 개발한 벡터 검색 라이브러리)에서 주로 사용되는 방식입니다.

### 동작 원리

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 비교

| 특성     | HNSW            | IVF               |
| ------ | --------------- | ----------------- |
| 검색 속도  | 매우 빠름           | 빠름                |
| 메모리 사용 | 높음 (그래프 저장)     | 낮음 (센트로이드만 저장)    |
| 인덱스 구축 | 느림              | 빠름 (K-means)      |
| 동적 추가  | 쉬움 (그래프에 노드 추가) | 어려움 (클러스터 재구성 필요) |
| 주 사용처  | 실시간 서비스         | 배치 검색, 비용 민감 환경   |

HNSW가 동적 추가에 유리한 이유는, 새 벡터를 기존 그래프에 연결하기만 하면 되기 때문입니다. 반면 IVF는 새 벡터가 기존 클러스터 경계와 맞지 않을 수 있어, 클러스터 중심점을 주기적으로 재계산(re-training)해야 합니다. 데이터가 지속적으로 추가되는 RAG 파이프라인에서는 이 차이가 운영 부담으로 직결됩니다.

***

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

Databricks Vector Search는 내부적으로 **DiskANN/HNSW 기반** 의 서버리스 인덱스를 제공합니다. **DiskANN** (Microsoft Research에서 개발)은 HNSW의 메모리 한계를 극복한 알고리즘으로, 그래프의 대부분을 SSD(디스크)에 저장하고 소량의 압축된 벡터만 메모리에 유지합니다. 검색 시 디스크 I/O를 최소화하도록 그래프 레이아웃을 최적화하여, HNSW에 근접한 검색 속도를 10분의 1 수준의 메모리로 달성합니다. 이 덕분에 수억 건 이상의 대규모 벡터도 비용 효율적으로 서빙할 수 있습니다.

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

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

### 사용자가 결정해야 하는 것

| 설정     | 선택지                               | 가이드               |
| ------ | --------------------------------- | ----------------- |
| 인덱스 유형 | Delta Sync / Direct Vector Access | 대부분 Delta Sync 권장 |
| 임베딩 방식 | 자동(모델 지정) / 사전 계산                 | 처음에는 자동, 이후 사전 계산 |
| 유사도 함수 | Cosine / Dot Product / Euclidean  | 대부분 Cosine        |

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

***

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