HNSW Explorer: 시각화된 계층적 탐색 가능 스몰 월드

검색이 계층화된 그래프를 따라 이동하는 과정을 지켜보세요 — 묽은 최상위 계층(고속도로)에서 밀집된 최하위 계층(지방 도로)까지 내려가는 과정을 볼 수 있습니다. 레이어 0의 쿼리 지점을 드래그하고 M / ef 값을 조정하여 그래프가 어떻게 변하는지 확인해 보세요.

노드당 최대 이웃 수

ef8

Layer-0 후보 벡터 풀

속도450ms

단계별

현재 단계

14 / 14

검색이 완료되었습니다. Top-3: [3, 10, 4].

검색 통계

방문한

17 / 30

레이어

항목

노드 0

Top-3

[3, 10, 4]

레이어 분포

HNSW 의 작동 방식

계층형 그래프: 각 노드에는 지수 분포를 사용하여 무작위로 최대 계층이 할당됩니다. 대부분의 노드는 계층 0에만 존재하며, 최상위 계층에 도달하는 노드는 극히 드뭅니다.
각 레이어 내에서: 모든 노드는 M 에 명시된 가장 가까운 이웃 노드들과 연결됩니다. 상위 레이어는 스파스(노드가 적고, 긴 에지 = “고속도로”)입니다. 레이어 0은 덴스(모든 노드, 짧은 에지 = “지역 도로”)입니다.
검색은 상단에서 시작됩니다: 고정된 진입점에서 쿼리에 가장 가까운 이웃으로 탐욕적으로 이동하며, 더 이상 개선되지 않을 때까지 이 과정을 반복합니다.
레이어를 한 단계 내려가고 반복합니다: 이전 레이어의 위치가 다음 레이어의 탐색 시작점이 됩니다. 레이어를 한 단계 내려갈 때마다 더 세분화된 에지를 통해 결과가 정교해집니다.
ef 를 적용한 레이어 0: 최하위 레이어에서, 첫 번째 국소 최소점에서 멈추는 대신, HNSW 는 ef 최상의 후보 벡터 풀을 유지하고 이들의 근방 영역을 확장합니다. 더 큰 ef → 정확도는 높아지지만 속도는 느려집니다.

왜 빠른가: 최상위 계층은 인덱스 위에 또 다른 인덱스처럼 작동합니다. 단 몇 번의 홉만으로 거대한 거리를 이동한 다음, 확대하여 세부 영역을 탐색합니다. N개의 점에 대해, 검색은 N 대신 대략 O(log N) 개의 노드를 방문합니다.

HNSW 란 무엇인가요?

HNSW (Hierarchical Navigable Small World) 는 그래프 기반의 근사 최인접 이웃 알고리즘입니다. 이 알고리즘은 벡터들을 탐색 가능한 스몰 월드 그래프의 스택으로 구성합니다. 상층부는 거친 경로를 위한 장거리 에지가 있는 희소 그래프이고, 하층부는 최종적인 세밀한 탐색을 위한 짧은 에지가 있는 고밀도 그래프입니다. 검색은 각 층에서 쿼리 방향으로 탐욕적으로 이동한 다음 아래로 내려가며, 전체 N개의 노드를 모두 스캔하는 대신 대략 O(log N) 개의 노드를 방문합니다.

HNSW 는 가장 널리 사용되는 인메모리 벡터 인덱스이며, Milvus 의 기본 그래프 인덱스입니다. Milvus 에서도 HNSW_SQ 와 HNSW_PQ 변형 버전을 제공하며, 이는 저장된 벡터를 양자화하여 리콜 정확도를 약간 희생하는 대가로 메모리 사용량을 줄입니다.

HNSW 매개변수 Milvus

M (구축 시간): 노드당 최대 에지 수로, 위의 슬라이더와 동일한 조절 기능입니다. 일반적인 값은 8~64입니다. M 값이 높을수록 리콜과 그래프 연결성은 향상되지만, 메모리 사용량은 선형적으로 증가하고 구축 속도는 느려집니다.
efConstruction (구축 시간): 노드를 삽입할 때 사용되는 후보 풀의 크기입니다. 값이 높을수록 인덱스 구축 속도는 느려지지만, 더 높은 품질의 그래프(더 높은 리콜 달성 가능)를 구축할 수 있습니다. 일반적인 값은 100~500입니다.
ef / ef_search (쿼리 시간): Layer-0 탐색 중에 유지되는 후보 풀 — 검색 시 리콜/지연 시간을 조절하는 주요 매개변수입니다. 이 값은 반드시 top-K 이상이어야 합니다. 리콜이 정체될 때까지 이 값을 늘리십시오. 지연 시간은 이 값에 따라 대략 선형적으로 증가합니다.

HNSW vs IVF vs DiskANN

HNSW 일반적으로 인메모리 검색에서 높은 리콜을 유지하면서 최상의 쿼리 지연 시간을 제공합니다. 따라서 데이터셋(그래프 오버헤드 포함)이 RAM 에 들어갈 때 기본 선택지로 사용됩니다. 이 알고리즘의 비용은 메모리와 구축 시간입니다. 그래프는 벡터당 눈에 띄는 오버헤드를 추가하며, 삽입 속도는 IVF 의 k-means 할당보다 느립니다. 빠른 인덱스 구축이나 강력한 양자화가 필요한 경우에는 IVF 를 선택하고, 데이터셋이 RAM 에 들어갈 수 없을 정도로 크지만 여전히 높은 리콜이 필요한 경우에는 DiskANN 를 선택하십시오.

자주 묻는 질문

HNSW 의 M 매개변수는 무엇을 제어합니까?

M은 각 노드가 레이어당 유지하는 에지의 수를 제한합니다. M이 클수록 그래프의 연결성이 향상되어(리콜이 높아지고 라우팅이 더 견고해짐) 하지만 메모리 사용량은 M에 비례하여 선형적으로 증가하며 인덱스 구축 속도가 느려집니다. 8에서 64 사이의 값이면 대부분의 워크로드를 처리할 수 있으며, 16~32가 일반적으로 최적의 범위입니다.

ef 와 efConstruction 의 차이점은 무엇인가요?

둘 다 후보 풀의 크기이며, 서로 다른 시점에 적용됩니다. 인덱스 구축 시에는 ‘ efConstruction ’가 사용됩니다. 이는 삽입된 각 노드가 이웃을 얼마나 철저하게 검색할지를 결정하므로 그래프 품질을 제어합니다. 쿼리 시에는 ‘ ef ’(ef_search)가 사용됩니다. 이는 Layer-0 검색의 범위를 제어하며, 모든 쿼리에서 지연 시간을 리콜과 절충합니다.

HNSW 인덱스에는 얼마나 많은 메모리가 필요합니까?

대략 원시 벡터와 그래프를 합친 크기입니다: float32 데이터의 경우 벡터당 약 d × 4바이트, 여기에 노드당 M × 2 × 8바이트 규모의 에지 데이터가 추가됩니다. 메모리 제약이 있는 배포 환경의 경우, Milvus 에서는 저장된 벡터를 양자화하는 HNSW_SQ 및 HNSW_PQ 를 제공하며, 전체 벡터를 SSD 로 이동시키는 DiskANN 도 제공합니다.

언제 IVF 대신 HNSW 를 사용해야 합니까?

높은 리콜률에서 쿼리 지연 시간을 우선시하고 인덱스가 메모리에 들어갈 수 있는 경우에는 HNSW 를 사용하십시오. — 이 방법이 대개 더 유리합니다. 인덱스를 자주 재구축하는 경우(구축 속도가 훨씬 빠름)나, 제한된 메모리 예산을 맞추기 위해 SQ8/PQ 양자화와 결합하는 경우에는 IVF 를 선호하십시오.

더 자세히 알아보기: 정확한 인덱스 매개변수에 대해서는 ` HNSW ` 문서를 참조하거나, 전체 결정 가이드를 보려면 ` Index Explained `를 참조하십시오.