HNSW (Hierarchical Navigable Small World graph)

Hierarchical -> 여러 계층으로 구성됨
Navigable -> 그래프를 탐색하기 쉬움
Small World graph -> "작은 세계 네트워크" 구조를 기반으로 함
- (노드들이 멀어 보이지만 몇 개의 링크만 타면 도달 가능)
즉, 고차원 벡터를 빠르게 탐색하기 위해 만든 계층적 그래프 알고리즘

HNSW는 어떤 종류의 알고리즘인가?

ANN(Aproximate Nearest Neighbor) 알고리즘의 한 종류

즉, 정확한 최근접 이웃(kNN)을 찾는 대신, 거의 정확한 결과(98~99%)를 아주 빠르게 찾는 알고리즘

HNSW는 ANN 계열 알고리즘 중에서도 성능(속도, 정확도, 메모리) 균형이 가장 좋다고 평가받아서 사실상 "표준"처럼 자리 잡음

HNSW의 핵심 아이디어

HNSW는 다음 구조로 동작함

1. 여러 층(Layer)의 그래프 구조로 벡터를 저장
- 위층은 거친/넓은 탐색
- 아래층은 정교/근접 탐색
2. 쿼리 벡터가 들어오면
- 높은 층에서 시작해서 candidate node를 찾고
- 점점 아래층으로 "내려오며" 더 가까운 이웃을 탐색
3. 최종적으로 가장 가까운 k개의 이웃(kNN 후보)을 빠르게 찾음
- 그래서 속도는 O(log N)에 가깝고, 정확도는 brute-force 대비 매우 높음

왜 HNSW가 ANN 알고리즘 중 가장 많이 쓰일까?

1. 정확도가 매우 높다
- 다른 ANN 기법(LSH, IVF, PQ, Annoy)에 비해 정확도가 압도적으로 높다
- (예) 데이터 100만개, ef_search=200 기준
  - 정확도 97 ~ 99%
- HNSW의 강점은
  
  "저렴한 비용으로 높은 정확도"를 유지할 수 있다는 점
2. 검색 속도가 매우 빠르다 (logarithmic)
- 데이터 수가 증가해도 성능 저하가 크지 않다
3. Incremental Insert 지원
- HNSW는 온라인 삽입(insert)을 빠르게 처리할 수 있다
- 벡터를 추가해도 전체 인덱스를 다시 만들 필요 없음
- RAG 시스템은 "문서 추가 -> embedding -> 저장" 구조라 이 기능이 매우 중요함
- Faiss의 IVF-PQ는 index rebuild가 필요해 불편
4. 모든 곳에서 지원됨 (산업 표준)
- 거의 모든 벡터 DB와 검색 엔진이 HNSW 지원
  - OpenSearch
  - Pinecone
  - Milvus
  - Faiss
  - NMSLIB 등
- 왜냐면
  - 운영 난이도가 낮고
  - 품질이 좋고
  - 튜닝이 쉬움
5. 파라미터 튜닝이 직관적이며 효과가 좋다
- HNSW 주요 파라미터 3개만 조절하면 됨
- M : 그래프 branching factor
- ef_construction : 인덱스 빌드 정확도
- ef_search : 검색 품질 (정확도)
- 특히 ef_search는 검색속도 <-> 정확도 사이의 슬라이더처럼 사용
  - ef_search를 높이면 -> 정확도 올라감, 속도 낮아짐
  - ef_search를 낮추면 -> 속도 올라감, 정확도 낮아짐
- 운영 환경에서 품질/속도를 조절하기 쉬움

HNSW의 약점은?

메모리 사용량이 크다
- 그래프를 유지해야 하므로 embedding 하나 저장할 떄 메모리 오버헤드가 생김
인덱스 빌드 비용이 크다
- HNSW index build 시간은 PQ 기반 알고리즘보다 느릴 수 있음
정말 초대규모(수십업 벡터 이상)면 다른 솔루션(IVF-PQ)가 필요
- 하지만, 대부분 서비스(수백만 ~ 수천만)는 HNSW로 ㅊ우분
- RAG 시스템도 대부분 HNSW 선호

HNSW (Hierarchical Navigable Small World graph)

Hierarchical -> 여러 계층으로 구성됨

Navigable -> 그래프를 탐색하기 쉬움

Small World graph -> "작은 세계 네트워크" 구조를 기반으로 함

(노드들이 멀어 보이지만 몇 개의 링크만 타면 도달 가능)

즉, 고차원 벡터를 빠르게 탐색하기 위해 만든 계층적 그래프 알고리즘

HNSW는 어떤 종류의 알고리즘인가?

ANN(Aproximate Nearest Neighbor) 알고리즘의 한 종류

즉, 정확한 최근접 이웃(kNN)을 찾는 대신, 거의 정확한 결과(98~99%)를 아주 빠르게 찾는 알고리즘

HNSW는 ANN 계열 알고리즘 중에서도 성능(속도, 정확도, 메모리) 균형이 가장 좋다고 평가받아서 사실상 "표준"처럼 자리 잡음

HNSW의 핵심 아이디어

HNSW는 다음 구조로 동작함

1. 여러 층(Layer)의 그래프 구조로 벡터를 저장

위층은 거친/넓은 탐색
아래층은 정교/근접 탐색

2. 쿼리 벡터가 들어오면

높은 층에서 시작해서 candidate node를 찾고
점점 아래층으로 "내려오며" 더 가까운 이웃을 탐색

3. 최종적으로 가장 가까운 k개의 이웃(kNN 후보)을 빠르게 찾음

그래서 속도는 O(log N)에 가깝고, 정확도는 brute-force 대비 매우 높음

왜 HNSW가 ANN 알고리즘 중 가장 많이 쓰일까?

1. 정확도가 매우 높다

다른 ANN 기법(LSH, IVF, PQ, Annoy)에 비해 정확도가 압도적으로 높다
(예) 데이터 100만개, ef_search=200 기준
- 정확도 97 ~ 99%
HNSW의 강점은

"저렴한 비용으로 높은 정확도"를 유지할 수 있다는 점

2. 검색 속도가 매우 빠르다 (logarithmic)

데이터 수가 증가해도 성능 저하가 크지 않다

3. Incremental Insert 지원

HNSW는 온라인 삽입(insert)을 빠르게 처리할 수 있다
벡터를 추가해도 전체 인덱스를 다시 만들 필요 없음
RAG 시스템은 "문서 추가 -> embedding -> 저장" 구조라 이 기능이 매우 중요함
Faiss의 IVF-PQ는 index rebuild가 필요해 불편

4. 모든 곳에서 지원됨 (산업 표준)

거의 모든 벡터 DB와 검색 엔진이 HNSW 지원
- OpenSearch
- Pinecone
- Milvus
- Faiss
- NMSLIB 등
왜냐면
- 운영 난이도가 낮고
- 품질이 좋고
- 튜닝이 쉬움

5. 파라미터 튜닝이 직관적이며 효과가 좋다

HNSW 주요 파라미터 3개만 조절하면 됨
M : 그래프 branching factor
ef_construction : 인덱스 빌드 정확도
ef_search : 검색 품질 (정확도)
특히 ef_search는 검색속도 <-> 정확도 사이의 슬라이더처럼 사용
- ef_search를 높이면 -> 정확도 올라감, 속도 낮아짐
- ef_search를 낮추면 -> 속도 올라감, 정확도 낮아짐
운영 환경에서 품질/속도를 조절하기 쉬움

HNSW의 약점은?

메모리 사용량이 크다

그래프를 유지해야 하므로 embedding 하나 저장할 떄 메모리 오버헤드가 생김

인덱스 빌드 비용이 크다

HNSW index build 시간은 PQ 기반 알고리즘보다 느릴 수 있음

정말 초대규모(수십업 벡터 이상)면 다른 솔루션(IVF-PQ)가 필요

하지만, 대부분 서비스(수백만 ~ 수천만)는 HNSW로 ㅊ우분
RAG 시스템도 대부분 HNSW 선호