HNSW 알고리즘의 원리를 NSW 그래프에서부터 다층 구조까지 단계별로 분석하고, 핵심 파라미터 튜닝과 성능 특성, 적합한 사용 시나리오를 다룹니다.
HNSW를 이해하려면 먼저 그 기반이 되는 NSW(Navigable Small World) 그래프를 알아야 합니다. NSW는 그래프 이론의 **스몰 월드 현상(Small World Phenomenon)**에서 영감을 받았습니다. "여섯 다리의 법칙"처럼, 임의의 두 노드 사이를 소수의 홉으로 연결할 수 있는 그래프 구조입니다.
NSW 그래프에서 벡터 검색은 다음과 같이 작동합니다.
이 방식의 문제점은 로컬 미니멈에 빠질 수 있다는 것입니다. 시작 노드가 최적 경로에서 멀리 떨어져 있으면, 진짜 최근접 이웃을 찾지 못할 수 있습니다.
**HNSW(Hierarchical Navigable Small World)**는 2016년 Malkov와 Yashunin이 제안한 알고리즘으로, NSW의 한계를 계층적 구조로 해결합니다. 핵심 아이디어는 지도의 축척과 유사합니다.
HNSW 인덱스를 구축하는 과정은 벡터를 하나씩 삽입하면서 그래프를 점진적으로 만들어가는 방식입니다.
새 벡터가 삽입될 때, 해당 벡터가 존재할 최대 레이어는 확률적으로 결정됩니다. 지수 분포를 따르며, 대부분의 벡터는 레이어 0에만 존재하고, 극소수만 상위 레이어에 배치됩니다.
import math
import random
def assign_layer(m_l: float) -> int:
"""새 벡터의 최대 레이어를 확률적으로 결정"""
# m_l은 보통 1/ln(M)으로 설정
return int(-math.log(random.random()) * m_l)
# M=16일 때 레이어 분포 시뮬레이션
m_l = 1.0 / math.log(16)
layer_counts = [0] * 10
for _ in range(100000):
layer = assign_layer(m_l)
if layer < 10:
layer_counts[layer] += 1
for i, count in enumerate(layer_counts):
print(f"Layer {i}: {count:>6d} ({count/1000:.1f}%)")
# Layer 0: ~93.7%, Layer 1: ~5.9%, Layer 2: ~0.4%, ...벡터가 삽입되면, 각 레이어에서 가장 가까운 M개의 이웃과 양방향 에지로 연결됩니다. 이 과정에서 efConstruction 파라미터가 탐색 범위를 결정합니다.
HNSW는 온라인 인덱싱을 지원합니다. 인덱스를 처음부터 다시 만들지 않고도 새 벡터를 추가할 수 있습니다. 다만 삽입 순서에 따라 그래프 품질이 달라질 수 있으므로, 대규모 인덱스에서는 주기적인 최적화가 권장됩니다.
쿼리 벡터가 주어졌을 때 HNSW의 검색 과정은 다음과 같습니다.
def hnsw_search(query, entry_point, top_k, ef_search):
"""HNSW 검색 과정 의사 코드"""
current_node = entry_point
# 상위 레이어: 그리디 탐색 (후보 1개만 유지)
for layer in range(top_layer, 1, -1):
current_node = greedy_search(query, current_node, layer, ef=1)
# 레이어 0: 정밀 탐색 (ef_search 크기 후보 집합)
candidates = beam_search(query, current_node, layer=0, ef=ef_search)
# 상위 K개 반환
return candidates[:top_k]핵심은 상위 레이어에서 "대략적으로 좋은 출발점"을 잡고, 최하위 레이어에서 "정밀하게 최근접 이웃"을 찾는 2단계 전략입니다. 이를 통해 로컬 미니멈에 빠지는 문제를 효과적으로 회피합니다.
HNSW의 성능은 세 가지 핵심 파라미터에 의해 결정됩니다.
각 노드가 각 레이어에서 가질 수 있는 최대 이웃 수입니다. 레이어 0에서는 2 x M개까지 허용됩니다.
| M 값 | 효과 |
|---|---|
| 작은 값 (4-8) | 메모리 절약, 빌드 빠름, 검색 recall 낮음 |
| 중간 값 (12-16) | 범용적, 대부분의 사용 사례에 적합 |
| 큰 값 (32-64) | 높은 recall, 메모리 많이 사용, 고차원 데이터에 유리 |
권장값: 일반적으로 M=16이 좋은 출발점입니다. 고차원 (768 이상) 벡터에서는 M=32-64가 더 나은 recall을 보입니다.
인덱스 구축 시 이웃 후보를 찾기 위한 탐색 범위입니다. 값이 클수록 더 좋은 이웃을 찾지만 빌드 시간이 증가합니다.
권장값: 최소 2 x M 이상, 일반적으로 100-200이 적절합니다. 빌드는 한 번만 수행하므로 넉넉하게 설정하는 것이 좋습니다.
검색 시 후보 집합의 크기입니다. 값이 클수록 recall이 높아지지만 지연시간이 증가합니다.
권장값: 최소 K (반환할 결과 수) 이상. recall 요구사항에 따라 동적으로 조절합니다.
# Qdrant에서 HNSW 파라미터 설정 예시
from qdrant_client import QdrantClient
from qdrant_client.models import VectorParams, HnswConfigDiff
client = QdrantClient(url="http://localhost:6333")
# 컬렉션 생성 시 HNSW 파라미터 지정
client.create_collection(
collection_name="articles",
vectors_config=VectorParams(
size=1536,
distance="Cosine",
hnsw_config=HnswConfigDiff(
m=16, # 이웃 수
ef_construct=200, # 빌드 탐색 범위
)
)
)
# 검색 시 efSearch 동적 조절
results = client.query_points(
collection_name="articles",
query=[0.1, 0.2, ...], # 쿼리 벡터
limit=10,
search_params={"hnsw_ef": 128} # 검색 탐색 범위
)efSearch를 너무 낮게 설정하면 recall이 급격히 떨어집니다. 프로덕션에서는 반드시 recall 벤치마크를 수행하여 적절한 값을 찾아야 합니다. efSearch=64일 때 recall 90%이던 것이 efSearch=128에서 recall 98%로 뛰는 경우가 흔합니다.
HNSW의 가장 큰 제약은 모든 벡터와 그래프 구조를 메모리에 유지해야 한다는 점입니다.
메모리 사용량은 대략 다음과 같이 계산할 수 있습니다.
벡터 저장에 필요한 메모리는 벡터 수 x 차원 수 x 4바이트(float32)입니다. 그래프 구조에 필요한 메모리는 벡터 수 x M x 2 x 4바이트(int32 노드 ID)입니다.
def estimate_hnsw_memory(
n_vectors: int,
dimensions: int,
m: int = 16,
bytes_per_float: int = 4
) -> dict:
"""HNSW 메모리 사용량 추정"""
vector_memory = n_vectors * dimensions * bytes_per_float
# 레이어 0은 2*M, 상위 레이어는 M (평균적으로 약 1.5*M)
graph_memory = n_vectors * m * 2 * 4 # 양방향 에지
total = vector_memory + graph_memory
return {
"vector_memory_gb": vector_memory / (1024**3),
"graph_memory_gb": graph_memory / (1024**3),
"total_gb": total / (1024**3)
}
# 1억 개의 1536차원 벡터, M=16
mem = estimate_hnsw_memory(100_000_000, 1536, m=16)
print(f"벡터: {mem['vector_memory_gb']:.1f} GB") # ~572 GB
print(f"그래프: {mem['graph_memory_gb']:.1f} GB") # ~12 GB
print(f"합계: {mem['total_gb']:.1f} GB") # ~584 GB1억 개의 1536차원 벡터를 HNSW로 서비스하려면 약 584GB의 메모리가 필요합니다. 이는 상당히 고가의 인프라를 요구합니다.
| 적합한 경우 | 부적합한 경우 |
|---|---|
| 벡터 수 1억 미만 | 수십억 규모 |
| 충분한 메모리 확보 가능 | 메모리 제약이 심한 환경 |
| 높은 recall 요구 | 비용이 최우선 |
| 실시간 업데이트 필요 | 배치 처리 위주 |
메모리 부담을 줄이는 방법으로 **PQ(Product Quantization)**와 HNSW를 결합하는 HNSW+PQ 방식이 있습니다. 벡터를 압축하여 메모리를 절약하되, 그래프 구조의 장점은 유지합니다. 다음 장에서 PQ를 상세히 다룹니다.
이번 장에서는 HNSW 알고리즘의 원리를 NSW 그래프에서 다층 구조까지 단계별로 분석했습니다. HNSW는 계층적 그래프 구조를 통해 높은 검색 속도와 recall을 동시에 달성하며, M, efConstruction, efSearch 세 가지 파라미터로 성능을 세밀하게 조절할 수 있습니다. 다만 모든 데이터를 메모리에 유지해야 하는 제약이 있어, 대규모 데이터셋에서는 대안이 필요합니다.
다음 장에서는 메모리 효율적인 ANN 알고리즘인 **IVF(Inverted File Index)**와 **PQ(Product Quantization)**를 심층 분석합니다. 특히 IVF+PQ 조합이 수십억 규모의 데이터셋에서 어떻게 작동하는지 살펴보겠습니다.
이 글이 도움이 되셨나요?
IVF 클러스터링 기반 검색과 Product Quantization의 원리를 분석하고, IVF+PQ 조합의 대규모 데이터셋 최적화 전략과 메모리-정확도 트레이드오프를 다룹니다.
임베딩의 원리와 텍스트, 이미지, 멀티모달 임베딩 모델을 비교하고, 유사도 메트릭의 수학적 배경과 차원의 저주, 임베딩 모델 선택 가이드를 다룹니다.
DiskANN의 Vamana 그래프 아키텍처와 SSD 최적화 전략을 분석하고, 10억+ 벡터 스케일에서의 성능, Fresh DiskANN과 Filtered DiskANN을 다룹니다.