HNSW

Hierarchical Navigable Small World, HNSW; HNSW
여러 층의 근접 그래프를 위층부터 탐욕적으로 내려가며 탐색해 고차원 벡터의 근사 최근접 이웃을 빠르게 찾는 색인 알고리즘

HNSW(Hierarchical Navigable Small World)는 고차원 벡터 집합에서 질의 벡터와 가까운 k개를 모든 벡터와 비교하지 않고 찾는 근사 최근접 이웃(approximate nearest neighbor, ANN) 탐색 알고리즘이다. 유리 말코프(Yury Malkov)와 드미트리 야슈닌(Dmitry Yashunin)이 2016년 arXiv에 공개하고 2020년 IEEE TPAMI에 게재했다.^[1] 벡터를 노드로, 가까운 벡터끼리를 간선으로 잇는 그래프를 여러 층으로 쌓고, 위층에서 크게 이동한 뒤 아래층에서 세밀하게 찾는다.

파이스 (FAISS), hnswlib 같은 라이브러리와 대부분의 벡터 데이터베이스, 루씬·엘라스틱서치, PostgreSQL의 pgvector가 HNSW 색인을 제공한다. RAG와 의미 검색에서 문장 임베딩을 찾는 단계가 대개 HNSW 위에서 돈다. 이 문서는 자료 구조, 탐색·삽입 알고리즘, 매개변수, IVF·PQ와의 비교, 코드를 다룬다.

배경

정확한 k-최근접 이웃 탐색은 질의마다 N개 벡터와 거리를 계산하므로 $O (N d)$ 가 든다. 벡터 1억 개, 768차원이면 질의 하나에 수백억 번의 곱셈이 필요하다. k-d 트리 같은 공간 분할 트리는 차원이 높아지면 거의 전수 탐색과 다를 바 없어진다(차원의 저주). 그래서 정확도를 조금 내주고 속도를 얻는 근사 방법이 쓰인다.

계열	아이디어	예
해싱	가까운 벡터가 같은 버킷에 들어가게 하는 해시	지역 민감 해싱(LSH)
군집 분할	벡터를 군집으로 나누고 질의와 가까운 군집만 탐색	IVF
양자화	벡터를 짧은 코드로 압축해 거리 계산을 싸게 함	PQ, 스칼라 양자화
그래프	가까운 벡터끼리 연결한 그래프를 따라 이동	NSW, HNSW, NSG, DiskANN

HNSW는 말코프 등이 앞서 제안한 탐색 가능한 작은 세상(Navigable Small World, NSW) 그래프에 계층을 더한 것이다. 원 논문은 이 구조가 스킵 리스트와 닮았다고 설명한다.^[1] 스킵 리스트가 위층의 듬성듬성한 연결 리스트로 멀리 건너뛰고 아래층에서 촘촘히 찾듯, HNSW도 위층의 적은 노드로 멀리 이동하고 0층의 전체 노드에서 정밀하게 찾는다.

구조

0층에는 모든 벡터가 있고, 위층으로 갈수록 노드 수가 지수적으로 줄어든다.
각 벡터가 올라갈 최고 층 $l$ 은 삽입 때 무작위로 정한다. $l = ⌊ - \ln (u n i f (0, 1)) \cdot m_{L} ⌋$ 이고, 원 논문은 $m_{L} = 1 / \ln (M)$ 을 권한다.^[1] 이때 어떤 노드가 l층 이상에 있을 확률은 $M^{- l}$ 이 되어, 위층으로 갈 때마다 노드 수가 약 1/M로 준다.
각 노드는 자기가 속한 층마다 이웃 목록을 가진다. 1층 이상에서는 최대 $M_{m a x} = M$ 개, 0층에서는 최대 $M_{m a x 0}$ 개다. 원 논문의 실험은 $M_{m a x 0} = 2 M$ 을 좋은 선택으로 제시했다.^[1]
맨 위층의 노드 하나가 진입점(entry point)이다.

탐색

층 하나 안에서의 탐색(SEARCH-LAYER)은 크기 ef의 후보 목록을 유지하는 탐욕적 빔 탐색이다.

import heapq

def search_layer(q, entry_points, ef, layer, dist, neighbors):
    """dist(q, v): 거리 함수, neighbors(v, layer): 그 층에서 v의 이웃 목록"""
    visited = set(entry_points)
    candidates = [(dist(q, e), e) for e in entry_points]        # 최소 힙: 가까운 것부터 확장
    heapq.heapify(candidates)
    results = [(-d, e) for d, e in candidates]                   # 최대 힙: 지금까지 찾은 ef개
    heapq.heapify(results)
    while candidates:
        d_c, c = heapq.heappop(candidates)
        if d_c > -results[0][0]:                                 # 가장 가까운 후보도 결과의 최악보다 멀면 종료
            break
        for e in neighbors(c, layer):
            if e in visited:
                continue
            visited.add(e)
            d_e = dist(q, e)
            if len(results) < ef or d_e < -results[0][0]:
                heapq.heappush(candidates, (d_e, e))
                heapq.heappush(results, (-d_e, e))
                if len(results) > ef:
                    heapq.heappop(results)                       # 가장 먼 것 제거
    return sorted((-d, e) for d, e in results)

전체 k-NN 탐색은 다음과 같다.

맨 위층의 진입점에서 시작해, 1층까지는 ef=1로 탐색한다. 즉 각 층에서 질의와 가장 가까운 노드 하나로 탐욕적으로 이동한 뒤 그 노드에서 아래층으로 내려간다.
0층에서는 ef=efSearch로 탐색해 후보 efSearch개를 얻는다.
그중 가까운 k개를 반환한다. 그래서 efSearch는 k 이상이어야 한다.

efSearch를 키우면 더 많은 노드를 방문해 재현율이 오르고 느려진다. 원 논문은 이 구조로 탐색 복잡도가 데이터 크기에 대해 로그 규모로 늘어난다고 보고했다.^[1]

삽입

새 벡터 q의 최고 층 l을 위 공식으로 뽑는다.
현재 최고 층부터 l+1층까지는 ef=1 탐욕 탐색으로 내려오며 진입점을 정한다.
l층부터 0층까지 각 층에서 ef=efConstruction으로 탐색해 후보를 얻고, 그중 M개를 이웃으로 골라 양방향 간선을 만든다.
이웃의 간선 수가 최댓값을 넘으면 그 이웃의 목록도 다시 골라 줄인다.
l이 기존 최고 층보다 높으면 q가 새 진입점이 된다.

이웃 선택 휴리스틱

후보 중 단순히 가장 가까운 M개를 고르면, 군집이 뚜렷한 데이터에서 같은 군집 안의 노드끼리만 연결되어 군집 사이를 건너는 간선이 사라진다. 원 논문의 휴리스틱은 가까운 후보부터 보면서, 후보 e가 이미 고른 어떤 이웃보다도 q에 더 가까울 때만 e를 고른다. 이미 고른 이웃 쪽 방향에 있는 후보는 건너뛰므로 여러 방향으로 퍼진 간선이 남는다. 이 휴리스틱은 높은 재현율 구간과 군집이 뚜렷한 데이터에서 성능을 크게 높였다.^[1]

매개변수

매개변수	의미	키우면	권장·참고
M	노드당 이웃 수(0층은 보통 2M)	재현율 상승, 메모리·구축 시간 증가	원 논문: 5~48이 합리적 범위, 저차원·낮은 재현율엔 작게, 고차원·높은 재현율엔 크게^[1]. FAISS 안내: 4~64^[2]
efConstruction	삽입 때 후보 목록 크기	그래프 품질 상승, 구축 느려짐	구축 중 k-NN 재현율이 1에 가까울 만큼(대부분 0.95면 충분)^[1]
efSearch (ef)	탐색 때 후보 목록 크기	재현율 상승, 질의 느려짐	k 이상. 색인을 다시 만들지 않고 질의마다 바꿀 수 있음

구현마다 기본값이 다르다.

구현	M	efConstruction	efSearch
hnswlib	16	200	10(`set_ef`로 변경)^[3]
FAISS IndexHNSW	생성자에서 지정(기본 32)	40	16^[4]
pgvector	16	64	40(`hnsw.ef_search`)^[5]
엘라스틱서치 dense_vector	16	100	질의의 num_candidates로 조절^[6]
Qdrant	16	100(ef_construct)	기본은 ef_construct와 같음^[7]

다른 제품의 벤치마크 수치를 비교할 때는 이 기본값 차이부터 맞춰야 한다.

메모리

FAISS 안내에 따르면 HNSW(Flat 저장)의 메모리는 벡터당 $(4 d + 8 M)$ 바이트다(float32 벡터 + 0층 기준 2M개의 4바이트 이웃 번호).^[2] 768차원, M=32이면 벡터당 3,072 + 256 = 3,328바이트로, 벡터 1억 개면 약 333GB가 된다. 대부분 벡터 자체가 차지하므로, 메모리를 줄이려면 벡터를 양자화한다. FAISS의 HNSW32,SQ8(8비트 스칼라 양자화)이나 IndexHNSWPQ, 엘라스틱서치의 int8_hnsw·bbq_hnsw 같은 양자화 HNSW가 그런 예다. 엘라스틱서치는 9.1부터 384차원 이상 float 벡터의 기본 색인을 bbq_hnsw로 바꿨다.^[6]

IVF, PQ와 비교

IVF(inverted file): k-평균으로 벡터를 nlist개 군집으로 나누고, 질의와 가까운 nprobe개 군집 안에서만 찾는다. FAISS는 군집 수를 데이터 크기 N에 대해 $4 \sqrt{N}$ ~ $16 \sqrt{N}$ 로 안내한다.^[2]
PQ(product quantization): d차원 벡터를 m개 부분 벡터로 나누고, 부분마다 256개 중심점 중 하나의 번호(1바이트)로 바꿔 벡터를 m바이트로 압축한다. 질의와 중심점 사이 거리를 표로 미리 계산해 두고 더하기만으로 거리를 근사한다.^[8]

색인	학습 필요	메모리(벡터당)	재현율·속도	추가·삭제	언제 쓰나
Flat(전수 탐색)	없음	4d 바이트	정확, 가장 느림	쉬움	수십만 개 이하, 정답 기준선
HNSW	없음	4d + 8M 바이트(원본 저장 시)	높은 재현율에서 빠름	추가 쉬움, 삭제는 표시 방식	메모리에 다 올릴 수 있는 수백만~수억 개
IVF-Flat	k-평균 학습	약 4d 바이트	nprobe로 조절, HNSW보다 대체로 느림	쉬움(군집이 고정)	빠른 구축, GPU 일괄 처리
IVF-PQ	k-평균 + PQ 학습	약 m 바이트	압축 손실로 재현율 상한이 낮음, 재순위화 필요	쉬움	메모리가 부족한 수억~수십억 개
HNSW + 양자화	양자화 학습(방식에 따라)	원본보다 수 배 작음	HNSW보다 약간 낮은 재현율	HNSW와 같음	메모리를 줄이면서 그래프 탐색 유지

FAISS 문서는 정확한 결과를 보장하는 색인은 IndexFlatL2와 IndexFlatIP뿐이며, HNSW는 학습이 필요 없지만 색인에서 벡터를 지우는 기능을 지원하지 않는다고 안내한다.^[2]

코드

FAISS

faiss-cpu 1.15.1에서 실행한 예다. 정확한 결과(IndexFlatL2)를 기준으로 efSearch에 따른 재현율을 잰다.

import numpy as np
import faiss

d, nb, nq, k = 128, 100_000, 1_000, 10
rng = np.random.default_rng(0)
xb = rng.standard_normal((nb, d)).astype("float32")
xq = rng.standard_normal((nq, d)).astype("float32")

flat = faiss.IndexFlatL2(d)               # 정답 기준선
flat.add(xb)
_, gt = flat.search(xq, k)

index = faiss.IndexHNSWFlat(d, 32)        # M = 32
index.hnsw.efConstruction = 200           # 기본값 40
index.add(xb)                             # 학습(train) 단계 없음

for ef in (16, 64, 256):
    index.hnsw.efSearch = ef              # 기본값 16
    _, I = index.search(xq, k)
    recall = np.mean([len(set(I[i]) & set(gt[i])) / k for i in range(nq)])
    print(ef, round(recall, 3))

이 예처럼 구조가 없는 무작위 정규분포 데이터는 근사 탐색에 가장 불리한 경우라, efSearch를 16에서 256으로 올리는 동안 재현율이 0.33에서 0.92로 크게 변했다. 실제 임베딩은 군집 구조가 있어 같은 설정에서 재현율이 훨씬 높게 나오는 것이 보통이지만, 반드시 자기 데이터로 재현율 곡선을 그려 efSearch를 정한다. 색인 문자열로 만들 수도 있다: faiss.index_factory(d, "HNSW32,Flat"), "HNSW32,SQ8", "IVF4096,PQ32".

hnswlib

import numpy as np
import hnswlib

dim, n = 384, 50_000
data = np.random.default_rng(0).standard_normal((n, dim)).astype("float32")

p = hnswlib.Index(space="cosine", dim=dim)        # "l2", "ip", "cosine"
p.init_index(max_elements=n, M=16, ef_construction=200)
p.add_items(data, np.arange(n))
p.set_ef(100)                                     # 탐색 후보 크기, k 이상
labels, distances = p.knn_query(data[:5], k=3)    # 자기 자신이 1위(코사인 거리 0)

p.mark_deleted(0)                                 # 삭제는 표시만 하고 결과에서 뺀다
p.save_index("index.bin")

hnswlib 0.8.0에서 실행을 확인했다. 결과는 (번호, 거리) 순서로 돌려주며, FAISS의 search가 (거리, 번호) 순서인 것과 반대다.

실무에서 부딪히는 문제

메모리 상주: 그래프 탐색은 무작위 메모리 접근이 많아 디스크에 두면 매우 느려진다. 색인 전체를 RAM에 올릴 수 있는지가 HNSW를 쓸지 정하는 첫 기준이다. 메모리가 부족하면 양자화, IVF-PQ, 디스크용 그래프 색인을 검토한다.
삭제와 갱신: 노드를 지우면 그 노드를 거쳐 가던 경로가 끊기므로, 대부분 구현은 삭제 표시만 하고 탐색 결과에서 뺀다. 삭제가 많이 쌓이면 품질과 속도가 떨어져 주기적으로 다시 구축한다.
필터 검색: "부서=인사팀인 문서 중에서" 같은 조건을 그래프 탐색 뒤에 적용하면 결과가 모자랄 수 있다. pgvector 문서는 조건에 맞는 행이 10%일 때 기본 ef_search 40으로는 평균 4행만 남는다고 설명하고, 더 많이 찾아 보는 반복 색인 스캔(iterative index scan)을 제공한다.^[5]
구축 시간: 삽입마다 탐색을 하므로 구축이 IVF보다 느리다. 대량 적재 때는 병렬 구축을 쓰고, efConstruction을 지나치게 키우지 않는다.
최악의 경우: 인디크(Indyk)와 쉬(Xu)는 HNSW 등 여러 그래프 기반 방법에서 "적당한" 정확도를 얻는 데 필요한 탐색 시간이 데이터 크기에 선형으로 늘어나는 입력이 존재함을 보였다.^[9] 벤치마크에서 빠르다는 것이 모든 데이터에서 보장되는 것은 아니다.

같이 보기

각주

↑ ^1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 ^1.6 ^1.7 Yury A. Malkov, Dmitry A. Yashunin, 〈Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs〉, IEEE Transactions on Pattern Analysis and Machine Intelligence 42(4), 824~836, 2020. arXiv:1603.09320
↑ ^2.0 ^2.1 ^2.2 ^2.3 FAISS 위키, Guidelines to choose an index
↑ hnswlib README
↑ FAISS HNSW.h; IndexHNSW.h
↑ ^5.0 ^5.1 pgvector README
↑ ^6.0 ^6.1 Elasticsearch 문서, Dense vector field type
↑ Qdrant 문서, Indexing
↑ Hervé Jégou, Matthijs Douze, Cordelia Schmid, 〈Product Quantization for Nearest Neighbor Search〉, IEEE TPAMI 33(1), 2011. DOI
↑ Piotr Indyk, Haike Xu, 〈Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations〉, NeurIPS 2023. arXiv:2310.19126

참고 문헌

[hnsw-1] 1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 ^1.6 ^1.7 Yury A. Malkov, Dmitry A. Yashunin, 〈Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs〉, IEEE Transactions on Pattern Analysis and Machine Intelligence 42(4), 824~836, 2020. arXiv:1603.09320

[faissguide-2] 2.0 ^2.1 ^2.2 ^2.3 FAISS 위키, Guidelines to choose an index

[hnswlib-3] swlib README

[faisssrc-4] FAISS HNSW.h; IndexHNSW.h

[pgvector-5] 5.0 ^5.1 pgvector README

[esdense-6] 6.0 ^6.1 Elasticsearch 문서, Dense vector field type

[qdrantidx-7] Qdrant 문서, Indexing

[pq-8] Hervé Jégou, Matthijs Douze, Cordelia Schmid, 〈Product Quantization for Nearest Neighbor Search〉, IEEE TPAMI 33(1), 2011. DOI

[indyk-9] Piotr Indyk, Haike Xu, 〈Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations〉, NeurIPS 2023. arXiv:2310.19126

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]