Brain💡 핵심 인사이트 HNSW(Hierarchical Navigable Small World)는 "다층 그래프(Multi-layer Graph) 구조를 이용해 벡터 공간에서 가까운 이웃을 계층적으로 탐색하는" 대표적인 ANN(Approximate Nearest Neighbor) 알고리즘입니다. 상위 레이어에서는 **대략적인 위치**를 빠르게 파악하고, 하위 레이어로 점진적으로 내려가며 (세밀하게 탐색) 합니다. 이 "_ Hierarchical_" 구조 덕분에 **수천 차원의 벡터에서도 수십 밀리초 내에 정확한 유사 이웃을 발견**할 수 있습니다. Milvus, Weaviate, Qdrant 등 **주요 벡터 데이터베이스의 기본 인덱싱 알고리즘**으로 사용됩니다.
Ⅰ. HNSW의 탄생: NSW의 한계를 극복
HNSW은 NSW(Navigable Small World) 알고리즘에서 영감을 받았습니다.
[NSW의 문제점]
NSW는 단일 레이어의 그래프입니다.
- 가까운 노드를 순차적으로 탐색
- 시작 위치에 따라 탐색 경로가 크게 달라질 수 있음
- 전역적 최적값을 보장하기 어려움
NSW 그래프 예시:
●────────────────●
/ \
●───────●────────────●
| | /
| | /
●───────●─────────●
문제: 시작점이 "좌측 상단"이면
"우측 하단"의 노드를 못 찾을 수 있음
HNSW의 해결책:
- 다층 레이어 도입 → 상위 레이어에서 넓은 범위 탐색, 하위 레이어에서 세밀한 탐색
- 점진적 세분화 (Progressive Refinement)
- O(log N) 시간 복잡도 달성
Ⅱ. HNSW의 구조: 다층 그래프
[HNSW 다층 구조]
┌─────────────────────────────────────────────────────────────────┐
│ HNSW 다층 구조 │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Layer 3 (최상위): │
│ ●━━━━━━━━━━━━━━━━━━━━━━━━━● │
│ │ │ │
│ │ (검색 시작 시 랜덤 엔트리 포인트에서 시작) │
│ │ 전역적으로 가장 가까운 클러스터 발견 │
│ │ │
│ Layer 2: │
│ ●━━━●━━━●━━━●━━━●━━━●━━━●━━━●━━━●━━━●━━━● │
│ │ │
│ │ (발견된 클러스터 내 하위 레이어로 이동) │
│ │ │
│ Layer 1: │
│ ●━●━●━●━●━●━●━●━●━●━●━●━●━●━●━●━●━●━●━● │
│ │ │
│ │ (더 세밀한 지역 탐색) │
│ │ │
│ Layer 0: │
│ ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● │
│ │ │
│ │ (가장 세밀한 레벨, 모든 벡터가 이 레벨에 존재) │
│ │ ef 파라미터만큼 탐색하여最近的 이웃 도출 │
│ │
└─────────────────────────────────────────────────────────────────┘
각 레이어의 역할:
- Layer 3, 2 (상위): (전역적으로) (가장 가까운) (노드를) (빠르게) (발견)
- Layer 1 (중간): (지역적) (세분화)
- Layer 0 (최하위): (가장 세밀한) (탐색, (ef) (파라미터) (만큼) (탐색) (_))
Ⅲ. HNSW 탐색 알고리즘: Greedy Search
HNSW의 검색은 greedy traversal 방식으로 이루어집니다.
[HNSW 탐색 과정]
입력: 쿼리 벡터 q, 파라미터 ef (탐색 범위)
1. 최상위 레이어에서 시작 (엔트리 포인트)
- 랜덤하게 선택된 노드에서 시작
- 또는 사전에 지정된 엔트리 포인트
2. 현재 레이어에서 q와 가장 가까운 노드 탐색
while (현재 레이어에서 개선 가능한 이웃이 있으면):
가장 가까운 이웃 = ef개의 후보 중 q와 거리 가장 가까운 노드
if (가장 가까운 이웃 != 현재 노드):
현재 노드 = 가장 가까운 이웃
else:
break
3. 더 하위 레이어가 있으면:
- 현재 노드에서 하위 레이어로 이동
- 2번 과정 반복
4. 최하위 레이어에서 ef개의最近的 이웃 반환
시간 복잡도:
탐색 시간 = Σ(1/M)^i (i = 0부터 레이어 수-1)
≈ 1 / (1 - 1/M) (상수)
→ O(log N) (N = 전체 벡터 수)
Ⅳ. HNSW 파라미터와 성능 조절
# HNSWlib (Python) 예시
import hnswlib
# 인덱스 초기화
dim = 1536 # 벡터 차원
max_elements = 1000000 # 벡터 수
index = hnswlib.Index(space='cosine', dim=dim)
index.init_index(max_elements=max_elements, ef_construction=200, M=16)
# 벡터 추가
index.add_items(vectors, ids=range(len(vectors)))
# 검색
index.set_ef(100) # 검색 시 탐색 범위
labels, distances = index.knn_query(query_vectors, k=10)
핵심 파라미터:
┌─────────────────────────────────────────────────────────────────┐
│ HNSW 파라미터 설명 │
├─────────────────────────────────────────────────────────────────┤
│ │
│ M (Maximum connections per node): │
│ - 각 노드가 상위 레이어에서 가질 수 있는 최대 연결 수 │
│ - 기본값: 16 │
│ - ↑ M: 정확도↑, 메모리↑, 빌드 시간↑ │
│ - ↓ M: 정확도↓, 메모리↓, 빌드 시간↓ │
│ │
│ efConstruction (Build time search breadth): │
│ - 인덱스 빌드 시 각 레이어에서 탐색할 후보 수 │
│ - 기본값: 200 │
│ - ↑ efConstruction: 정확도↑, 빌드 시간↑ │
│ - ↓ efConstruction: 정확도↓, 빌드 시간↓ │
│ │
│ efSearch (Query time search breadth): │
│ - 검색 시 최하위 레이어에서 탐색할 후보 수 │
│ - 기본값: M과 efConstruction에 따라 결정 │
│ - ↑ efSearch: 정확도↑, 검색 시간↑ │
│ - ↓ efSearch: 정확도↓, 검색 시간↓ │
│ │
│ 권장 조합: │
│ - 빠른 응답 (추천 시스템): M=8, efConstruction=100, ef=50 │
│ - 균형: M=16, efConstruction=200, ef=100 │
│ - 고정확도 (RAG): M=32, efConstruction=400, ef=200 │
│ │
└─────────────────────────────────────────────────────────────────┘
Ⅴ. HNSW의 메모리 관리와 📢 비유
메모리 사용량:
# 메모리估算
# 대략: (M * 2 * bytes_per_float + overhead) * num_vectors
# 예시:
M = 16
dim = 1536
num_vectors = 10_000_000
bytes_per_float = 4
memory_per_vector = M * 2 * dim * bytes_per_float # 양방향 연결
memory = memory_per_vector * num_vectors
# = 16 * 2 * 1536 * 4 * 10,000,000
# = 약 2.5 GB
메모리 최적화 기법:
- _PQ (Product Quantization): 벡터를 저차원으로 압축하여 메모리 절감
- 자연적 계층 활용: 자주アクセス되는データを上層에配置
📢 섹션 요약 비유: HNSW는 **"대형 도시에서 가장近い 맛집을 찾는 것에 비유"**할 수 있습니다. (전체) (도시간) (道路) (네트워크) (에서) ('가장 가까운 맛집') (을) (찾는) (것은) (거의) (불가능) (합니다) (→) (KNN의) (수백만) (계산) (문제) ()。(HNSW는) (지도를) (3단계) (계층으로) (나누어) (探します: (1단계) (_ Province/시_) (단위) (에서) (검색) (→) (2단계) (区/군) (단위) (에서) (검색) (→) (3단계) (개별) (맛집) (에서) (세밀한) (비교) (→) (거의) (정확한) (최 가까운) (맛집) (을) (수) (분) (안에) (발견) (하는) (것) (과) (같습니다) ())。(다만) (가끔) (_ Province_) (단계) (에서) (잘못된) (시) (를) (선택) (하면) (최종) (결과가) (100%) (정확하지) (않을) (수) (있는) (것처럼) (HNSW도) (근사값) (을) (반환하는) (것을) (감안) (해야) (합니다) ())。