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 선호