HNSW(Hierarchical Navigable Small World)는 모든 벡터를 매번 비교하는 대신, 근접 이웃으로 연결된 그래프를 내려가며 후보를 좁히는 approximate nearest-neighbor 구조입니다. 여기서 approximate는 “가끔 틀려도 된다”는 뜻만이 아니라, 정확한 최근접 탐색과 비교해 어떤 후보를 방문할지와 언제 멈출지를 비용으로 조절한다는 뜻입니다. 따라서 M, efConstruction, efSearch를 독립적인 마법 숫자로 외우기보다 삽입 시 그래프를 얼마나 잘 만들었는지, 질의 시 그래프를 얼마나 넓게 펼쳤는지, 그리고 exact baseline과 비교해 무엇을 잃었는지를 함께 기록해야 합니다.
검색 문제와 근접 이웃 그래프
벡터 집합에서 질의 q와 거리가 가까운 순서로 top-k를 찾는 exact search는 모든 벡터의 거리를 계산한 뒤 정렬하거나 선택합니다. 문서가 N개이고 벡터 차원이 d라면 한 질의의 거리 계산량은 대략 N·d에 비례합니다. HNSW는 각 벡터를 정점으로 두고 가까운 이웃 후보에 간선을 두어, 현재 정점보다 질의에 가까운 방향으로 이동하는 경로를 만들려 합니다. 모든 간선을 보장하지 않으므로 exact top-k와 결과가 달라질 수 있고, 그 비율을 보통 recall@k로 측정합니다.
한 질의의 recall@10은 exact 결과의 상위 10개 중 ANN 결과 상위 10개에 들어온 항목 수를 10으로 나눈 값입니다. 검색 결과가 10개 미만이면 실제 API의 반환 계약에 따라 분모와 결측 처리를 정해야 합니다. 중요한 점은 ANN의 score만으로 recall을 알 수 없다는 것입니다. 같은 질의 집합을 exact로 먼저 계산해 정답 집합을 만들고, 동일한 필터·동일한 distance metric으로 HNSW 결과를 비교해야 합니다.
계층과 진입점 이동
HNSW는 여러 계층의 그래프를 둡니다. 상위 계층은 일부 정점만 포함해 긴 이동을 빠르게 만들고, 하위 계층은 더 많은 정점을 포함해 최종 후보를 정밀하게 고릅니다. 질의는 진입점에서 시작해 상위 계층에서 더 가까운 이웃으로 greedy하게 이동하다가, 더 이상 개선이 없으면 한 계층 아래로 내려갑니다. 최하위 계층에서는 greedy 한 점만 반환하지 않고 후보 집합을 넓게 유지하며 top-k를 뽑는 탐색을 합니다.
그림을 글로 읽기
- 진입점: 상위 계층
- greedy 이동: 더 가까운 이웃
- 하위 계층: 재진입
- 후보 확장: efSearch
- top-k 결과: ANN 후보
- 진입점 → greedy 이동: 시작
- greedy 이동 → 하위 계층: 층 하강
- 하위 계층 → 후보 확장: 탐색 폭
- 후보 확장 → top-k 결과: 거리 선택
상위 계층에서 잘못된 지역으로 들어가면 하위 계층 탐색이 그 손실을 만회해야 합니다. 그래프 연결성이 좋고 최하위 탐색 폭이 충분하면 회복 가능성이 커지지만, 어떤 데이터 분포에서도 보장되는 것은 아닙니다. 특히 임베딩이 여러 군집으로 분리되거나 필터가 후보를 많이 제거하면, 거리상 가까운 그래프 경로와 실제 허용 문서 집합의 경로가 달라집니다.
M과 링크 저장량
M은 삽입 때 한 정점이 유지하는 이웃 연결 수의 핵심 상한입니다. 구현에 따라 상위 레이어와 최하위 레이어의 실제 연결 제한, 양방향 링크 처리, 내부 기본값이 다를 수 있으므로 여기서는 HNSW 논문의 파라미터 의미와 일반적인 메모리 관계만 고정합니다. 링크를 한 개 저장할 때 정점 ID, 배열 오버헤드, 정렬·삭제 메타데이터가 필요합니다. 따라서 대략적인 링크 메모리는 정점 수 × 평균 degree × ID 바이트에 비례하며, 양방향으로 보관하면 한 연결이 양쪽 adjacency에 반영될 수 있습니다.
예를 들어 1,000,000개 정점, 이웃 ID 4바이트, 최하위 평균 degree를 단순히 M으로 근사하면 M=16일 때 한 방향 링크만 약 64MB, M=48일 때 약 192MB입니다. 이는 실제 index 메모리가 아니라 링크 ID의 설명용 하한에 가까운 계산입니다. 벡터 원본, 레이어 메타데이터, allocator 여유, 삭제 표시, 정렬·압축 구조는 별도입니다. 그러므로 “M을 세 배로 했으니 전체 메모리도 정확히 세 배”라고 보고하면 안 됩니다.
M이 커지면 연결 선택 단계에서 더 많은 후보를 유지할 여지가 생기고, 질의가 이동할 수 있는 경로도 늘어날 수 있습니다. 그러나 모든 새 링크가 유익한 것은 아닙니다. 이웃을 저장·순회하는 거리 계산과 캐시 접근이 증가하고, 인덱스가 메모리 계층을 벗어나면 평균보다 p99가 크게 나빠질 수 있습니다. 데이터가 작은 경우에는 M 증가의 recall 이득보다 메모리 비용이 먼저 드러날 수도 있습니다.
efConstruction과 삽입 품질
efConstruction은 새 정점을 삽입할 때 이웃을 선택하기 위한 탐색 후보 폭입니다. M이 최종 그래프의 연결 상한이라면, efConstruction은 그 상한 안에서 어떤 연결을 선택할지 더 넓게 살펴보는 build-time 예산입니다. 작은 폭으로 일찍 멈추면 빠르게 index를 만들 수 있지만, 새 정점이 좋은 이웃을 놓치거나 서로 다른 군집을 연결하는 간선이 약해질 수 있습니다. 큰 폭은 build 시간과 임시 후보 메모리를 늘리지만, 같은 M에서 더 유리한 링크 선택을 가능하게 합니다.
중간 상태를 기록하면 두 파라미터를 구분할 수 있습니다. 예를 들어 한 삽입에서 후보 heap에 64개를 유지하다가 거리 순으로 16개 링크를 선택했다면, efConstruction=64, M=16은 “64개를 검토하고 16개를 저장”한 설정입니다. 후보 512개를 검토해도 최종 링크 수는 16개일 수 있습니다. 이 둘을 모두 “그래프가 넓어졌다”라고 합치면 build 비용과 저장 비용의 원인을 구분할 수 없습니다.
efSearch와 후보 상태
efSearch는 질의 시 최하위 계층에서 유지·확장하는 후보 폭입니다. 구현마다 후보 heap의 정확한 내부 이름과 최소 보장 조건은 다를 수 있지만, 개념적으로는 방문한 정점 집합과 아직 확장할 후보 집합, 현재 최종 결과 집합을 분리합니다. efSearch가 10이라고 해서 거리 계산이 정확히 10번이라는 뜻도 아니고, 결과가 항상 10개라는 뜻도 아닙니다. 방문·중복 제거·레이어 진입점에 따라 실제 계산 수가 달라질 수 있습니다.
설명용 trace를 보겠습니다. 최종 k=10이고 efSearch를 32에서 128로 올렸다면, 질의 시작 직후 후보 heap에 최대 32개 또는 128개 수준의 경쟁 후보를 보관할 수 있습니다. 확장할 후보의 최선 거리가 현재 결과 경계보다 충분히 나빠지는 순간 중단할 수 있으므로 실제 방문 수가 cap과 같지 않을 수 있습니다. 같은 1M 벡터와 같은 query set에서 ef=32가 10,000 distance evaluations, ef=128이 32,000 evaluations를 냈다면 검색 CPU는 대략 세 배 방향으로 움직이지만 실제 배수는 cache hit와 조기 종료에 좌우됩니다.
efSearch를 키우면 탐색할 경로와 후보가 많아져 exact top-k를 포함할 가능성이 대체로 증가합니다. 그러나 monotonic recall은 특정 구현·필터·동시성·삭제 처리까지 포함해 자동 보장된다고 단정하지 않습니다. 비교 시 query order, warm-up, thread 수, filter, 결과 tie-breaker를 고정하고 recall@k, 평균, p95, p99, distance 계산 수를 함께 기록합니다.
파라미터 교차 선택과 필터
M, efConstruction, efSearch는 한 축씩 튜닝하면 상호작용을 놓칩니다. 예를 들어 build efConstruction=64/512, search efSearch=16/128 네 조합을 같은 index 크기 조건과 같은 질의 집합에서 비교하면 그래프 품질과 탐색 폭의 역할을 나눌 수 있습니다. M을 바꾼 조합은 별도 index를 만들어야 하며, 동일 index에서 검색 ef만 바꾼 경우와 표를 섞으면 안 됩니다.
필터가 있는 검색은 특히 주의합니다. unfiltered graph에서 가까운 이웃 100개를 찾은 뒤 필터로 95개를 버리는 방식은, 허용 문서가 그래프에서 멀리 연결돼 있을 때 recall이 낮아질 수 있습니다. 필터가 사전 적용인지, 검색 중 방문 후 적용인지, 필터 selectivity가 어느 정도인지에 따라 필요한 탐색 폭이 달라집니다. 따라서 “전체 recall 0.98”만으로 tenant·언어·기간별 recall을 대표하지 말고, 작은 필터 집합과 큰 필터 집합을 분리합니다.
삭제와 갱신의 상태 경계
HNSW 논문은 계층 그래프의 구성·탐색 범위를 다루지만, 읽을 수 있었던 범위만으로 특정 엔진의 삭제·compaction·업데이트 계약을 근거화할 수 없습니다. 실제 엔진의 삭제·compaction·업데이트 계약은 제품 구현에 따라 다릅니다. 문서를 삭제했다고 그래프 링크가 즉시 물리적으로 사라진다고 가정하면 안 됩니다. 일반적인 검증 모델에서는 먼저 visibility 상태를 logical deleted로 표시하고, 탐색기가 deleted ID를 최종 결과에서 제외하는지 확인합니다. 링크가 남아 있으면 traversal 후보에는 나타날 수 있으나 반환 결과에는 나타나지 않아야 합니다.
갱신은 같은 ID의 벡터를 in-place로 덮는지, 새 벡터를 새 정점으로 삽입하고 옛 정점을 tombstone 처리하는지에 따라 다릅니다. 설명용 테스트에서는 A의 옛 벡터와 새 벡터를 의도적으로 멀리 둡니다. 갱신 직후 옛 위치의 query가 old A를 계속 반환하는지, 새 위치의 query가 new A를 반환하는지, 두 결과에 동일 logical ID가 중복되는지 분리 측정합니다. 이후 compaction 또는 rebuild 시 메모리와 traversal candidate 수가 줄어드는 시점도 별도로 기록해야 합니다.
정확도·지연 검증 절차
첫 단계는 작은 벡터 집합에서 exact 거리 행렬을 계산해 정답을 고정하는 것입니다. 그 다음 HNSW index를 M, efConstruction 조합별로 새로 만들고, 검색은 efSearch만 바꿔 같은 질의를 반복합니다. 측정 결과에는 index build 시간, 링크·전체 메모리, query QPS, p50/p95/p99, recall@1·@10·@100, 필터별 recall, 삭제·갱신 후 stale hit를 포함합니다.
1M 벡터의 예시 계획은 다음과 같습니다. k=10, query 1,000개, efSearch=32,128,512를 순차 실행하되 warm-up과 cold-start를 구분합니다. 실제 숫자를 실행하지 않았다면 설정 예시일 뿐이며, 예상 결과를 측정 결과처럼 쓰지 않습니다. 비교표에는 exact baseline 시간도 넣습니다. ANN의 p99가 목표를 넘으면 ef를 무조건 줄이기보다, recall 손실이 어느 query bucket에서 발생했는지와 memory pressure가 latency를 만들었는지를 확인합니다.
비용·한계와 참고 범위
HNSW는 높은 recall과 낮은 query latency를 노릴 수 있지만, 그래프를 메모리에 유지하는 비용, build 시간이 긴 비용, 삭제·업데이트의 tombstone 관리, 필터·동적 데이터에서의 품질 변화가 있습니다. M과 ef를 높이는 것이 저장장치·CPU·메모리를 무한히 교환해 주는 것도 아니며, 데이터 분포에 따라 링크가 추가되어도 recall이 거의 늘지 않을 수 있습니다. 정확한 top-k가 법적·정산 기준이면 ANN 결과를 확정값으로 사용하지 말고 exact 재확인 또는 별도 보장 경로를 둡니다.
근거 범위는 Malkov와 Yashunin의 HNSW 논문에서 확인 가능한 계층 그래프 구성·탐색의 개요입니다. 이번 검토에서는 abstract 중심으로 읽었으므로 M·ef의 세부 정의, 삭제 API와 monotonic recall을 논문이 직접 보장한다고 쓰지 않습니다. 이 문서에서는 특정 Elasticsearch·FAISS·hnswlib의 기본값이나 삭제 API를 일반 규칙으로 확대하지 않았습니다. 실제 엔진을 선택할 때는 해당 버전의 filter, update, delete, persistence 계약을 읽고, 위 exact baseline 실험으로 구현을 검증해야 합니다.