HNSW

HNSW, 100만 개 중에서 수백 개만 보고 최근접을 찾는 법

요약

• HNSW는 벡터들을 근접 그래프로 잇고 그 위에 계층을 쌓은 근사 최근접 이웃(ANN) 인덱스입니다. 전신인 단층 NSW에 고속도로 층을 얹은 구조입니다.
• 핵심은 위층의 성긴 그래프에서 거칠게 진입해 아래층의 촘촘한 그래프로 내려가며 greedy 탐색하는 것입니다. 전체가 아니라 일부 노드만 보고 최근접을 찾습니다.
• 그래서 검색 비용이 노드 수에 로그 스케일로만 늘어납니다. 100만 개 중 수백 개만 보고 끝납니다.
• 손잡이가 셋입니다. M(노드당 이웃 수), efConstruction(빌드 품질), efSearch(질의 시 정확도와 속도). 이 중 efSearch만 런타임에 바꿀 수 있습니다.
• 반드시 알아야 할 것. exact가 아니라 근사입니다. recall이 100퍼센트가 아니고, 얼마나 정확한지는 측정해야 압니다.

---

왜 정확도를 포기하나

벡터 검색의 목표는 단순합니다. 질의 벡터가 들어오면 저장된 수백만 개 벡터 중 가장 가까운 k개를 찾는 것입니다. RAG에서 관련 문서 top-k를 회수하는 게 전부 이 연산입니다.

가장 정직한 방법은 전수 비교입니다. 질의와 모든 벡터의 거리를 하나하나 재서 정렬합니다. 정확하지만 100만 개면 질의마다 100만 번 거리를 계산해야 합니다.

그래서 정확도를 조금 양보하고 속도를 크게 얻는 근사 최근접 탐색이 등장했습니다. 여기서 "조금 양보한다"는 게 무슨 뜻인지가 중요합니다. 반환한 top-10이 진짜 최근접 10개와 100퍼센트 일치한다는 보장이 없다는 뜻입니다.

ANN에는 여러 계열이 있습니다. 클러스터로 나누는 IVF, 벡터를 압축하는 PQ 같은 것들이고, HNSW는 그중 그래프 계열입니다.

발상은 이렇습니다. 벡터들을 미리 가까운 것끼리 그래프로 이어두면, 질의가 들어왔을 때 아무 노드에서나 시작해 더 가까운 이웃 쪽으로 계속 이동하면 목표 근처에 도달합니다. 전체를 훑지 않고 길을 따라가는 겁니다.

계층이라는 아이디어

이 그래프 발상의 원형이 NSW(Navigable Small World) 입니다. 여기서 small world는 소셜 네트워크의 "여섯 다리 건너면 다 아는 사이" 같은 성질을 말합니다. 노드가 많아도 몇 번의 점프로 어디든 닿는 그래프입니다.

문제는 NSW가 단층이라는 것입니다. 그래프가 커지면 greedy 탐색이 초반에 헤매는 구간이 길어져 성능이 떨어집니다. Malkov와 Yashunin은 여기에 계층을 얹어 해결했습니다. 이것이 Hierarchical NSW, 곧 HNSW입니다.

skip list와 닮았습니다. 정렬 리스트 위에 고속도로 층을 얹어 점프로 빠르게 접근하는 자료구조가 skip list입니다. HNSW의 계층이 정확히 이 직관입니다. 위층일수록 노드가 적은 성긴 그래프라 멀리 점프하고, 아래로 내려올수록 촘촘해져 정밀하게 좁힙니다. 1차원 skip list를 고차원 그래프로 확장한 것으로 보면 단번에 이해됩니다.

구조

두 축으로 되어 있습니다.

근접 그래프는 각 층 내부의 구조입니다. 노드를 가까운 것끼리 양방향 엣지로 잇습니다. 노드당 최대 이웃 수가 M입니다.

계층은 층 사이의 구조입니다. 노드마다 최대 레벨을 무작위로, 지수 분포를 따라 배정합니다. 위로 갈수록 확률이 지수적으로 줄어 노드가 적습니다. 최상위층은 소수의 허브이고, 최하위 0층에는 전체 노드가 있습니다. 상위 레벨을 받은 노드는 자기 레벨부터 0층까지 모든 층에 동시에 존재합니다.

Layer 2   성긴 그래프 (소수 허브)
          진입점 ──greedy──► 허브
                             │
                             │ 한 층 내려감
                             ▼
Layer 1   중간 밀도
          o ─── o ───► o ───► o
                             │
                             │ 한 층 내려감
                             ▼
Layer 0   전체 노드 (촘촘)
          o ─── o ─── o ──► [목표 top-k] ─── o
                    └────────────┘
                    efSearch 폭으로 후보 탐색

위층에서 큰 점프로 목표 근방까지 오고, 0층에서 efSearch 폭으로 후보를 모아 top-k를 확정하는 흐름입니다.

탐색은 이렇게 돌아갑니다

질의가 들어오면 네 단계를 거칩니다.

1. 최상위층의 진입점에서 시작합니다. 진입점은 고정된 소수 허브 중 하나입니다.

2. 현재 층에서 greedy로 이동합니다. 지금 노드의 이웃들 중 질의에 더 가까운 이웃으로 계속 옮겨갑니다. 더는 가까워지지 않으면 그 지점에서 한 층 내려갑니다.

3. 아래층에서 반복합니다. 위층에서 이미 목표 근처까지 왔으므로, 아래층에선 좁은 영역만 정밀 탐색합니다.

4. 0층에서 후보를 모읍니다. 마지막 0층에서는 하나의 최근접만 쫓지 않고 efSearch 크기의 후보 집합을 유지하며 탐색한 뒤 그중 top-k를 반환합니다.

핵심은 분업입니다. 위층의 성긴 그래프가 목표의 대략적 위치까지 몇 번의 큰 점프로 데려다주고, 아래층의 촘촘한 그래프가 그 근방을 정밀하게 마무리합니다.

삽입할 때는

새 벡터를 넣을 때도 비슷합니다.

먼저 새 노드의 최대 레벨을 무작위로 뽑습니다. 대부분 0층에만 들어가고 가끔 높은 레벨까지 올라갑니다.

그다음 자기 레벨의 층부터 시작해 각 층에서 가장 가까운 이웃 후보를 찾습니다. 이때 후보 탐색 폭이 efConstruction입니다.

각 층에서 가장 가까운 M개 이웃과 양방향으로 연결합니다. 여기서 이웃 선택이 단순 최근접이 아니라 다양성 휴리스틱을 씁니다. 선택된 이웃들끼리 너무 몰리지 않게 하는 건데, 이래야 멀리 가는 지름길이 살아남아 그래프가 항해 가능한 상태로 유지됩니다.

100만 벡터에서 한 번의 검색

임베딩 100만 개가 3개 층으로 인덱싱돼 있다고 해봅시다. 지수 분포 배정 결과 Layer 2에 허브 4개, Layer 1에 수백 개, Layer 0에 100만 개 전부가 있습니다. 질의의 최근접 10개를 찾는 과정입니다.

단계	층	하는 일	거리 계산
1	Layer 2	진입점에서 허브 4개 중 가장 가까운 곳으로 greedy 이동	수 회
2	Layer 1	그 허브에서 내려와 이웃을 따라 목표 근방까지 좁힘	수십 회
3	Layer 0	efSearch 폭으로 후보 집합을 유지하며 정밀 탐색	수백 회

전체 방문 노드가 수백 개 수준에서 끝납니다. 전수 비교라면 100만 번 계산했을 일을 0.1퍼센트 미만만 보고 마칩니다.

대신 반환한 top-10이 진짜 최근접 10개와 100퍼센트 일치한다는 보장은 없습니다. 그게 근사의 의미이고, 얼마나 정확한지는 efSearch를 키우면 올라갑니다.

위 층 분포와 방문 수는 원리 설명용입니다. 실제로는 데이터와 파라미터에 따라 달라집니다.

손잡이 셋

파라미터	무엇을 정하나	올리면	비고
M	노드당 최대 이웃 수	recall 상승, 메모리 상승	빌드 시 고정. 보통 16, 범위 12에서 48. 고차원 임베딩은 48에서 64가 유리
efConstruction	삽입 시 탐색 후보 폭, 곧 빌드 품질	그래프 품질 상승, 빌드 느려짐	빌드 시 고정. 보통 100에서 200
efSearch	질의 시 후보 집합 크기	recall 상승, 검색 느려짐	런타임 조절 가능. 반드시 k 이상

읽는 법은 이렇습니다.

M은 그래프를 얼마나 촘촘히 이을지입니다. 이웃이 많을수록 길이 많아 recall이 오르지만, 노드당 링크를 다 저장하니 메모리가 커집니다. 고차원 데이터일수록 더 촘촘해야 제 성능이 납니다.

efConstruction은 빌드 때 얼마나 공들일지입니다. 크게 잡으면 더 좋은 이웃을 골라 그래프 품질이 좋아지지만 인덱싱이 느려집니다. 한 번 빌드하면 끝이라 보통 넉넉히 줍니다.

efSearch는 유일한 런타임 손잡이입니다. 같은 인덱스에서도 질의마다 바꿀 수 있어서, 정확도가 중요한 검색이면 키우고 빠른 응답이 중요하면 줄입니다.

튜닝 순서. recall이 목표에 못 미치면 먼저 efSearch를 올립니다. 런타임이라 공짜입니다. 그래도 안 되면 M이나 efConstruction을 키워 재빌드합니다.

다른 ANN 방식과 비교

방식	언제 고르나
전수 비교	정확하고 단순합니다. 수천 개 이하이거나 그래프 이득이 작을 때
HNSW	수십만에서 수백만, 속도와 정확도 균형이 필요할 때의 기본 선택. 메모리 여유가 있을 때
IVF-PQ	메모리가 관건인 초대규모. 벡터를 양자화해 메모리를 수십 배 줄입니다. 정확도 일부 희생
NSW	단층 그래프. HNSW가 계층을 더해 사실상 대체했습니다

핵심 분기는 메모리입니다. 여유가 있으면 HNSW, 빡빡하고 초대규모면 IVF-PQ 같은 양자화 계열입니다.

한 가지 더 있습니다. 차원이 아주 높으면 HNSW의 이득이 줄어 전수 비교와 격차가 좁아질 수 있습니다. 전환 전에 실측으로 확인하는 게 안전합니다.

한계와 주의

메모리가 큽니다. 벡터 원본에 더해 노드당 M개 링크를 얹으니 원본보다 큰 메모리를 씁니다.

삭제와 업데이트가 까다롭습니다. 노드를 지우면 그래프 연결이 끊겨서, 단순 삭제 대신 tombstone 처리 후 주기적으로 재구성해야 하는 경우가 많습니다. 데이터가 자주 바뀌는 환경이라면 이 비용을 미리 계산해둬야 합니다.

recall은 측정 대상입니다. efSearch에 크게 의존하므로 "HNSW니까 정확하다"고 단정하면 안 됩니다. 목표 recall을 정해놓고 실측해야 합니다.

메타데이터 필터와 함께 쓸 때 주의합니다. 필터 조건이 그래프 연결을 끊어 recall이 떨어질 수 있습니다. 이를 완화하려고 필터를 탐색에 통합하는 filterable HNSW 변형을 지원하는 DB도 있습니다.

구현과 벡터 DB

라이브러리로는 원저자 C++ 구현인 hnswlib, 단일 헤더에 Rust 바인딩이 있는 usearch, FAISS의 HNSW 인덱스가 있습니다.

벡터 DB는 Qdrant, Weaviate, pgvector, Milvus 등 대부분이 HNSW를 기본 인덱스로 제공합니다. 파라미터명은 m, ef_construct, ef 처럼 조금씩 다르지만 개념은 같습니다.

여기서 확인해둘 게 하나 있습니다. sqlite-vec처럼 전수 비교만 쓰는 경량 엔진도 있습니다. 인덱스 방식은 도입 전에 문서로 확인해야 합니다. 벡터 DB라고 다 HNSW를 쓰는 게 아닙니다.

RAG 파이프라인에서는 문서 임베딩을 HNSW로 인덱싱해두고 질의 임베딩으로 top-k를 밀리초 이하에 회수합니다. 이후 BM25와 합치거나 크로스인코더로 재정렬하는 단계로 이어집니다.

마치며

핵심 세 가지로 정리합니다.

1. HNSW는 근접 그래프에 skip-list식 계층을 얹어, 위층에서 거칠게 진입하고 아래층에서 정밀하게 좁히는 그래프 기반 ANN 인덱스입니다.
2. 이 계층 분업 덕에 검색이 로그 스케일로 끝나 전체의 극히 일부만 보고 최근접을 찾습니다.
3. 손잡이는 M과 efConstruction(빌드), efSearch(런타임) 셋이며, exact가 아닌 근사라 recall은 측정해야 합니다.

용어 정리

용어	한 줄 뜻
ANN (근사 최근접 이웃)	정확도를 조금 양보하고 속도를 크게 얻어 최근접을 찾는 검색
HNSW	다층 근접 그래프 위에서 greedy로 최근접을 찾는 ANN 인덱스
NSW	단층 근접 그래프. HNSW의 전신
근접 그래프	가까운 벡터끼리 엣지로 이은 그래프
greedy 탐색	현재 노드에서 질의에 더 가까운 이웃으로 계속 이동하는 탐색
계층, 레벨	위로 갈수록 성긴 그래프. skip list의 고속도로 층과 유사
M	노드당 최대 이웃 수. recall과 메모리를 좌우
efConstruction	삽입 시 후보 탐색 폭. 그래프 빌드 품질을 좌우
efSearch	질의 시 후보 집합 크기. recall과 속도의 런타임 손잡이
recall	반환한 top-k가 진짜 최근접과 얼마나 일치하는지의 비율

참고자료

• Malkov & Yashunin, "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs" (IEEE TPAMI, arXiv:1603.09320)
• Malkov et al., "Approximate nearest neighbor algorithm based on navigable small world graphs" (Information Systems 45, 2014)
• hnswlib, 원저자 C++ 구현
• hnswlib ALGO_PARAMS, M과 efConstruction, ef 파라미터 설명
• Qdrant, HNSW 인덱스 설정 공식 문서