HNSW 알고리즘 시각적 가이드: 벡터 검색의 핵심

게시일: 2025년 11월 22일 | 원문 작성일: 2024년 5월 26일 | 저자: Christopher Fu | 원문 보기

왜 HNSW인가?

현대 AI 애플리케이션의 핵심은 의미적 검색이에요. 텍스트를 임베딩으로 변환하고, 가장 유사한 벡터를 찾는 것. 하지만 수백만 개의 벡터에서 가장 가까운 이웃을 어떻게 효율적으로 찾을까요?

단순한 선형 검색은 O(N)이에요 - 100만 개 벡터라면 100만 번 비교해야 하죠. KD-Tree나 Ball-Tree 같은 전통적인 방법들은 고차원 공간에서 “차원의 저주”로 인해 성능이 크게 저하돼요.

HNSW는 이 문제를 해결하는 가장 실용적인 알고리즘 중 하나예요. 실제로 많은 프로덕션 벡터 데이터베이스가 HNSW를 사용해요.

기초: Skip List에서 시작하기

HNSW를 이해하려면 먼저 Skip List를 이해해야 해요. Skip List는 멀티 레이어 연결 리스트예요:

• 레이어 0: 모든 요소를 포함하는 기본 연결 리스트
• 상위 레이어: 일부 요소만 포함하는 “고속도로” - 빠른 탐색을 위한 지름길

탐색 방법:

1. 최상위 레이어에서 시작
2. 현재 레이어에서 목표값을 넘지 않는 최대한 멀리까지 이동
3. 더 이동할 수 없으면 한 레이어 아래로 내려가기
4. 레이어 0에 도달할 때까지 반복

이 계층적 구조가 O(log N) 탐색 시간을 가능하게 해요. Skip List의 핵심 아이디어는 “대략적인 경로를 빠르게 찾고, 점진적으로 정확도를 높인다”는 거예요.

NSW: Navigable Small World 그래프

Skip List는 1차원 데이터에 좋아요. 하지만 고차원 벡터 공간은? 여기서 NSW (Navigable Small World) 그래프가 등장해요.

Small World 네트워크란?

Small World 네트워크는 두 가지 속성을 가져요:

• 짧은 경로 길이: 어떤 두 노드 사이든 적은 수의 홉(hop)으로 도달 가능
• 높은 클러스터링: 이웃들끼리도 서로 연결되는 경향

실제 세계의 예: “6단계 분리 이론” - 모든 사람이 평균 6명의 지인을 통해 연결된다는 이론이죠.

NSW 구축 알고리즘

삽입 (Insertion):

__FENCED_UNDER_0__

검색 (Search):

__FENCED_UNDER_1__

NSW의 문제점? 진입점이 목표와 멀리 떨어져 있으면 많은 홉이 필요해요. 평균 O(log N)이지만 최악의 경우 O(N)까지 가능하죠.

HNSW: 계층적 구조의 마법

HNSW는 Skip List의 계층적 아이디어를 NSW에 적용한 거예요!

핵심 아이디어

• 여러 레이어의 NSW 그래프를 만들어요
• 상위 레이어: 적은 수의 노드, 긴 거리 연결 (고속도로)
• 하위 레이어: 많은 노드, 짧은 거리 연결 (정밀 탐색)
• 레이어 0: 모든 요소를 포함

HNSW 삽입 알고리즘

__FENCED_UNDER_2__

HNSW 검색 알고리즘

__FENCED_UNDER_3__

왜 빠른가?

• 상위 레이어: 긴 거리를 빠르게 이동 (대략적 위치 찾기)
• 하위 레이어: 짧은 거리로 정밀 탐색
• 각 레이어에서 O(log N) 탐색 → 전체 O(log N)

복잡도 분석

파라미터 튜닝 가이드

주요 파라미터

1. M (최대 연결 수)

• 각 노드가 가질 수 있는 최대 이웃 수
• 작은 M: 메모리 절약, 검색 속도 느림, recall 낮음
• 큰 M: 메모리 많이 사용, 검색 빠름, recall 높음
• 권장값: M = 16~48 (대부분 경우 32가 좋은 시작점)

2. efConstruction (구축 시 탐색 크기)

• 삽입 시 고려할 후보 수
• 작은 값: 빠른 구축, 낮은 품질
• 큰 값: 느린 구축, 높은 품질
• 권장값: efConstruction = 100~200

3. ef (검색 시 탐색 크기)

• 검색 시 고려할 후보 수
• 작은 ef: 빠른 검색, recall 낮음
• 큰 ef: 느린 검색, recall 높음
• 권장값: ef >= K (반환할 이웃 수)

4. M_L (레벨 승수)

• 레이어 수 결정에 사용
• 권장값: M_L = 1/ln(M) ≈ 0.36 (M=16일 때)

실전 튜닝 전략

실전 사례: 벡터 데이터베이스

HNSW는 프로덕션 벡터 검색에서 사실상 표준이에요:

• Faiss (Facebook): IndexHNSWFlat 제공
• Pinecone: HNSW 기반 관리형 벡터 DB
• Weaviate: GraphQL 기반 벡터 검색 엔진
• Qdrant: Rust로 작성된 고성능 벡터 DB
• Milvus: 대규모 벡터 검색 시스템

실제 성능 예시

1백만 개의 768차원 벡터 (BERT 임베딩):

• 선형 검색: ~200ms per query
• HNSW (M=32): ~2ms per query (100배 빠름!)
• Recall: 95%+ (대부분 애플리케이션에 충분)

HNSW의 한계와 대안

한계점

• 메모리 집약적: 모든 벡터를 메모리에 보관
• 삭제 비용: 노드 삭제 시 그래프 재구성 필요
• 동적 데이터: 지속적인 삽입/삭제에는 비효율적
• 초고차원: 1000+ 차원에서는 성능 저하

대안 및 보완

• Product Quantization: 메모리 사용량 감소
• DiskANN: 디스크 기반 벡터 검색
• SPANN: 분산 환경을 위한 HNSW 확장
• ScaNN (Google): 압축 + HNSW 하이브리드

구현 예제: Python

HNSW를 사용하는 가장 간단한 방법은 __CODE_UNDER_0__ 라이브러리예요:

__FENCED_UNDER_4__

결론: HNSW가 중요한 이유

HNSW는 단순한 알고리즘이 아니에요. 현대 AI 인프라의 기초예요:

• LLM 애플리케이션: RAG (Retrieval-Augmented Generation)의 핵심
• 추천 시스템: 유사 아이템 빠르게 찾기
• 이미지 검색: 시각적 유사도 기반 검색
• 이상 탐지: 정상 패턴에서 벗어난 데이터 찾기

Skip List의 계층적 구조와 Small World 네트워크의 탐색 효율성을 결합한 HNSW는 이론과 실전이 만나는 아름다운 예예요.

다음에 ChatGPT가 여러분의 문서를 검색할 때, 또는 추천 시스템이 완벽한 제품을 찾아줄 때, 그 뒤에는 HNSW가 있을 가능성이 높아요. 보이지 않지만, 모든 곳에서 작동하고 있죠.