AI for Everyone
데이터·DB

HNSW

에이치엔에스더블유

벡터 검색 분야에서 쓰이는 Hierarchical Navigable Small World(계층적 탐색 가능 소세계 그래프)의 약자로, 근사 최근접 이웃(ANN) 탐색에 쓰는 그래프 인덱스입니다. 벡터를 여러 층의 근접 그래프로 쌓고 위층에서 탐색 시작점을 좁혀 내려가는 구조이며, 원 논문은 로그 수준의 복잡도 확장을 보고했습니다 [1]. 정확도와 속도의 균형은 M, efConstruction, efSearch 값으로 조절합니다 [1]. 그래프와 벡터를 메모리에 올려 두는 방식이라 메모리 사용량이 큽니다 [7].

쉽게 말하면?

Hierarchical Navigable Small World는 계층으로 쌓은, 오갈 수 있는 좁은 세상 그래프라는 뜻입니다. 목적지를 찾을 때 고속도로로 대략의 방향을 잡고, 국도로 내려와 범위를 줄이고, 마지막에 골목에서 집 앞에 서는 것과 같아요. 위층 그래프는 성기게 연결돼 멀리 건너뛰고, 아래층으로 갈수록 촌촌해져 정밀하게 좁힙니다. 모든 벡터를 하나씩 다 비교하지 않고도 가까운 이웃을 찾아내는 방식입니다.

한 줄로 비유하면?

고속도로에서 방향을 잡고 국도로 내려온 뒤 골목에서 집 앞에 서는, 축척을 단계적으로 줄여 가는 지도입니다.

어디에 쓰이나?

케이스 1원 논문 — HNSW를 제안하고 기존 ANN 라이브러리와 비교한 벤치마크

2016년 3월 arXiv에 공개되고 2018년 8월 v4로 갱신된 논문입니다 [1]. SIFT 100만 건(128차원), GloVe 120만 건(100차원), CoPhIR 200만 건(272차원) 등에서 NSW, FLANN, Annoy, FALCONN, FAISS와 비교했습니다 [1]. 저자들은 M의 적정 범위를 5~48, 최하층 연결 수를 2배로 권고했습니다 [1]. 원소 갱신과 삭제 지원은 향후 과제로 남겼습니다 [1].
도입효과: 인덱스 메모리(데이터 제외) 객체당 약 60~450바이트, M 6~48 구간 기준 [1]

케이스 2Amazon Aurora PostgreSQL — pgvector HNSW 인덱스의 적재·질의 성능 측정

2023년 11월 AWS 데이터베이스 블로그가 pgvector 0.5.0과 0.5.1을 비교한 측정입니다 [2]. 1,536차원 벡터 1,000만 건 기준으로 테이블 39GB, HNSW 인덱스 38GB를 차지했습니다 [2]. 기본값 m=16, ef_construction=64를 두고 ef_search를 20부터 800까지 바꿔 가며 측정했습니다 [2]. 인덱스 크기가 원본 테이블과 맞먹는다는 점이 용량 계획의 기준점입니다 [2].
도입효과: 128차원 1,000만 건 적재 처리량 2,758 TPS에서 8,960 TPS로 증가, 클라이언트 64개 기준 [2]

케이스 3Elasticsearch — dense_vector 기본 인덱스를 양자화 결합 HNSW로 전환

공식 매핑 문서 기준 m 기본값은 16, ef_construction 기본값은 100입니다 [3]. float 벡터의 기본 인덱스 유형은 384차원 미만이면 int8_hnsw, 384차원 이상이면 bbq_hnsw입니다 [3]. 원본 float 값은 재순위와 재색인을 위해 디스크에 그대로 남겨 둡니다 [3]. 이 때문에 디스크는 int8 약 25%, int4 약 12.5%, bbq 약 3.1%만큼 더 씁니다 [3].
도입효과: 메모리 사용량 int8 4배·int4 8배·bbq 32배 감소, 무압축 HNSW 기준 [3]

케이스 4미리디 미리캔버스 — Amazon OpenSearch k-NN 기반 듀얼 벡터 검색 운영 국내 사례

2026년 7월 AWS 코리아 기술 블로그에 공동 명의로 공개된 국내 사례입니다 [4]. 약 4,000만 건 문서에 벡터 필드 5개를 두고 벡터마다 k=200으로 탐색했습니다 [4]. 글은 recall을 올리려 ef_search나 m을 키우면 같은 트레이드오프가 따른다고 적었고, k-NN 네이티브 메모리 사용률이 16%인데 OS 메모리 사용률은 99%에 달한 점을 병목으로 지목했습니다 [4]. 범용 인스턴스 8대에서 메모리 최적화 인스턴스 12대로 옮겨 총 메모리를 512GB에서 768GB로 늘렸습니다 [4].
도입효과: 검색 레이턴시 평균 18.2ms에서 14.4ms로 21% 개선, 최대 Read IOPS 5,130에서 3,410으로 감소, 인스턴스 전환 전후 기준 [4]

주의할 점은?

오늘 바로 해보기
01. 보유한 벡터의 개수와 차원부터 셉니다. 1,536차원 1,000만 건이면 인덱스만 38GB라는 공개 측정치가 용량 계획의 기준점입니다 [2].
02. 쓰고 있는 엔진의 기본값을 확인합니다. m 16·ef_construction 100(Elasticsearch), m 16·ef_construction 64(pgvector 측정 사례)로 제각각입니다 [3][2].
03. efSearch만 먼저 바꿔 가며 recall과 지연시간을 한 표에 같이 기록합니다. 인덱스를 다시 만들지 않고 돌릴 수 있는 손잡이입니다 [2].
04. 필터 검색을 쓴다면 페이로드 인덱스를 데이터 적재 전에 만들어 둡니다. Qdrant 문서는 컬렉션 생성 직후 생성을 권고합니다 [5].
05. 삭제가 잦은 데이터라면 튀스톤 정리 주기를 점검합니다. Weaviate는 기본값 300초로 정리를 돌립니다 [6].

한계와 진화
한계는 세 갈래입니다. 첫째는 메모리입니다. 원 논문은 데이터를 미포함한 인덱스만으로 객체당 60~450바이트를 쓴다고 적었고 [1], Elastic은 HNSW가 제 성능을 내려면 벡터가 전부 RAM에 있어야 하며 메모리가 줄면 지연시간이 급격히 늘어난다고 설명합니다 [7]. 둘째는 삭제입니다. 원 논문 단계에서 원소 갱신과 삭제는 향후 과제였고 [1], 실제 엔진들은 튀스톤으로 우회합니다. Weaviate는 큰 인덱스에서 튀스톤 정리가 자원을 많이 쓴다고 밝혔고 [6], Qdrant는 소프트 삭제 지점이 쌓이면 필터 검색 정확도가 떨어진다고 적었습니다 [5]. 셋째는 인덱스 빌드 비용입니다. Elastic의 100만 벡터 실험에서 HNSW 색인에 1,054,319ms가 걸렸습니다 [7].
진화는 디스크와 압축 두 방향입니다. NeurIPS 2019에 발표된 DiskANN은 SSD를 함께 쓰는 방식으로 64GB RAM 워크스테이션 한 대에서 10억 개 벡터를 색인했고, SIFT1B에서 초당 5,000질의 이상·평균 3ms 미만·1-recall@1 95% 이상을 보고했습니다 [8]. 양자화 결합도 자리를 잡았습니다. Elasticsearch는 int8·int4·이진 양자화를 HNSW에 붙여 각각 4배·8배·32배 메모리 절감을 문서화했고 [3], 2025년 10월에는 계층적 k-means와 이진 양자화를 쓰는 DiskBBQ를 HNSW 대안으로 공개했습니다 [7]. 같은 100만 벡터 실험에서 DiskBBQ는 색인 94,075ms·지연 약 4.0ms·recall 91%, HNSW는 색인 1,054,319ms·지연 약 3.4ms·recall 92%였습니다 [7].

참고 자료

  1. Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs — 학술 논문·arXiv(Malkov, Yashunin)·2016(v4 2018) — https://arxiv.org/abs/1603.09320
  2. Accelerate HNSW indexing and searching with pgvector on Amazon Aurora PostgreSQL-compatible edition and Amazon RDS for PostgreSQL — 기술 블로그·AWS·2023 — https://aws.amazon.com/blogs/database/accelerate-hnsw-indexing-and-searching-with-pgvector-on-amazon-aurora-postgresql-compatible-edition-and-amazon-rds-for-postgresql/
  3. Dense vector field type — 공식 문서·Elastic·2026년 8월 확인 — https://www.elastic.co/docs/reference/elasticsearch/mapping-reference/dense-vector
  4. Amazon OpenSearch Service로 미리캔버스의 듀얼 벡터 검색 도입과 성능 최적화 — 기술 블로그·AWS 코리아·2026 — https://aws.amazon.com/ko/blogs/tech/miricanvas-dual-vector-search-opensearch-3-3-upgrade-1/
  5. Indexing — 공식 문서·Qdrant·2026년 8월 확인 — https://qdrant.tech/documentation/manage-data/indexing/
  6. Vector index — 공식 문서·Weaviate·2026년 8월 확인 — https://docs.weaviate.io/weaviate/config-refs/indexing/vector-index
  7. Elastic DiskBBQ introduction: An alternative to HNSW — 기술 블로그·Elasticsearch Labs·2025 — https://www.elastic.co/search-labs/blog/diskbbq-elasticsearch-introduction
  8. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node — 학술 논문·NeurIPS·2019 — https://suhasjs.github.io/files/diskann_neurips19.pdf

대표 출처

arXiv 논문 (2016) · Malkov & Yashunin, Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
카드뉴스로 공유하기 다른 AI 용어 보기