HNSW 심화 — 파라미터 튜닝과 구현체별 성능 차이

벡터 검색 알고리즘 입문에서 HNSW가 kNN을 실시간에 쓰게 만든 표준 알고리즘이라는 걸 봤다. 이 글은 그 다음 단계다 — 파라미터를 어떻게 튜닝하고, 왜 같은 설정인데 제품마다 성능이 다른가.

먼저 가져갈 결론

• HNSW 튜닝은 파라미터 3개로 끝난다 — M(그래프 밀도), ef_construction(빌드 품질), ef_search(검색 품질). 앞 둘은 인덱스에 고정되고, ef_search만 질의 시점에 바꿀 수 있다. recall과 속도를 실시간으로 맞바꾸는 유일한 손잡이다.
• 같은 M/ef를 줘도 구현체마다 recall·QPS가 갈린다. 이건 버그가 아니라 정상이다. 이웃 선택 방식, SIMD 거리계산, 메모리 레이아웃, 필터 처리가 다르기 때문이다.
• 구현체 간 최대 차별점은 필터링 처리와 메모리 모델이다. 순수 속도보다 이 둘이 제품 선택을 가르는 경우가 많다.
• 아래 수치는 대부분 벤더·공개 벤치의 "출처 주장"이다. 우리 워크로드로 재검증하기 전에는 단정하지 않는다.

파라미터 3개 심화

세 파라미터는 **빌드 시점(1회) vs 검색 시점(매 쿼리)**으로 성격이 갈린다.

M — 노드당 연결 수 (빌드, 그래프 밀도)

각 노드가 유지하는 양방향 링크 수(최하층은 2M). 그래프가 얼마나 촘촘한지를 정한다.

• 높을수록 연결이 많아져 지역 최소값(local minima)에 갇힐 확률이 줄어 recall이 오른다.
• 메모리가 M에 선형 비례해 늘어난다(노드마다 링크를 저장).
• 그래프가 촘촘해져 빌드가 느려진다.
• 권장 범위는 8-64, 기본 16. 저차원·저용량이면 8-16, 고차원·고정밀이면 32-64.

ef_construction — 빌드 시 탐색 폭 (빌드, 그래프 품질)

벡터를 삽입할 때 이웃 후보를 몇 개까지 탐색하는지. 그래프 자체의 품질을 정한다.

• 높을수록 삽입 때 더 좋은 이웃을 찾아, 같은 ef_search에서도 recall이 오른다.
• 대신 빌드가 느려진다. 검색 속도·메모리에는 거의 영향이 없다(빌드가 끝나면 그래프에 흡수된다).
• 일정 지점 이상은 수익이 체감된다 — 그래프 품질은 안 오르고 빌드만 느려진다.
• 권장 범위는 100-500, 프로덕션 시작점 200. 조건은 ef_construction ≥ M.

ef_search — 검색 시 탐색 폭 (매 쿼리, recall-속도 슬라이더)

바닥 레이어에서 유지하는 후보 리스트 크기. 질의마다 바꿀 수 있는 유일한 파라미터다.

• 높을수록 더 많은 노드를 방문해 recall이 오르고 QPS가 떨어진다.
• ef_search ≥ k는 필수다. 후보 리스트가 k보다 작으면 top-k를 반환할 수 없다(Milvus는 아예 ef < k 설정을 막는다).
• 권장은 k보다 넉넉히 — 10(빠름·저recall) → 100(균형) → 500(고recall·느림).

상호작용 — 한 장으로

M과 ef_construction은 역할이 다르다. M은 "이웃을 몇 개 저장할지"(구조·메모리)이고, ef_construction은 "그 이웃을 얼마나 잘 고를지"(탐색 품질)다. M을 키우면 채울 슬롯이 늘어나므로, 좋은 후보로 채우려면 ef_construction도 함께 올려야 효과가 난다. M만 키우고 ef_construction을 낮추면 슬롯이 부실한 이웃으로 채워져 메모리만 쓰고 recall이 안 오른다.

멘탈모델은 이렇다 — M·ef_construction으로 그래프의 "recall 천장"을 정하고, ef_search로 그 천장 안에서 recall-속도 지점을 고른다. 그래서 여러 제품을 공정하게 비교하려면 재빌드 없이 ef_search만 여러 값으로 훑어(sweep) 같은 recall 지점에서 QPS를 비교한다.

거리 계산 — 코사인 유사도는 사실 내적이다

HNSW가 "가깝다"를 판정하는 건 결국 벡터 간 거리 계산이고, RAG의 표준인 코사인 유사도는 실제로 내적으로 계산된다.

코사인 유사도 공식은 이렇다.

cos(θ) = (A · B) / (|A| · |B|)

• A · B = 내적 = 성분끼리 곱해서 합한 값. 크기와 방향을 모두 반영한다.
• |A|, |B| = 각 벡터의 크기(L2 norm).
• 내적을 크기로 나눠 방향(각도)만 남긴 게 코사인이다.

실무에서는 매 검색마다 나눗셈이 비싸서, 저장할 때 모든 벡터를 L2 정규화(크기를 1로)한다. 그러면 |A|=|B|=1이 되어 cos = A·B — 코사인이 그냥 내적으로 단순화된다. OpenSearch space_type=cosinesimil, faiss cosine이 내부적으로 이 방식(정규화 후 inner product)이다.

임베딩 모델이 의미가 비슷한 텍스트를 벡터 공간에서 방향이 비슷하게 배치하도록 학습되기 때문에, 각도(코사인)가 의미 유사도를 대변한다. HNSW는 유사도가 아니라 "거리"로 다루므로 코사인 거리 = 1 − 코사인 유사도로 변환해 쓴다(작을수록 가깝다).

구현체별 성능 차이

같은 M/ef라도 recall·속도가 갈리는 원인은 넷이다.

• 이웃 선택 휴리스틱 — 단순 최근접 vs 다양성(diverse) 기반 가지치기.
• 거리계산 SIMD — AVX2/AVX512 지원 여부와 런타임 자동 선택.
• 메모리 레이아웃 — 인메모리 연속 배열 vs 세그먼트 파일 vs 디스크.
• 필터·refine 처리 — 필터를 탐색 중에 적용하는지, 결과를 원본 벡터로 재정렬하는지.

특히 눈여겨볼 지점이 둘 있다.

첫째, Lucene HNSW의 역사적 함정이다. 초기 Lucene HNSW는 논문의 계층 구조를 안 따르고 단일 그래프 레이어만 썼다. 그 탓에 같은 데이터셋에서 hnswlib 대비 QPS가 약 9배 낮았다는 벤치가 있다(2021 무렵, 출처 주장). 기본 beamWidth(=ef_construction)가 16으로 너무 낮았던 것도 원인이다. 다만 이후 계층 구조 도입, SIMD(Panama Vector API), 양자화로 크게 개선됐으므로, 현행 OpenSearch를 이 옛 수치로 판단하면 안 된다.

둘째, 필터 처리 방식의 차이다. 메타데이터 필터를 걸면 그래프 탐색이 깨진다 — 필터를 탐색 전에 적용하면 그래프 연결이 끊겨 recall이 급락하고, 탐색 후에 적용하면 필터가 빡셀 때 k개를 못 채운다.

• Qdrant는 payload 값 기반으로 그래프에 추가 엣지를 넣어 탐색 중 필터를 적용한다(filterable HNSW).
• Milvus는 Dual-Pool — 필터로 걸러진 노드도 네비게이션용으로만 유지해, 탐색 예산이 필터된 벡터에 잠식되지 않게 한다. 같은 문제를 서로 다르게 푼 것이라, 필터를 많이 쓰는 워크로드에서는 이 설계 차이가 곧 성능 차이가 된다.

ann-benchmarks에서의 위치

ann-benchmarks(erikbern)는 표준 데이터셋에서 recall@k·QPS·빌드시간·메모리를 재는 사실상 표준 도구다.

• recall-QPS 곡선 최상단은 양자화를 얹은 HNSW 변종(Glass 등)이고, 순정 HNSW 중에서는 hnswlib가 오래 기준선이었다.
• 주의할 점 — ann-benchmarks는 라이브러리(hnswlib·FAISS·Glass 등)를 비교하지, 완제품 DB(OpenSearch·Qdrant 서버·Milvus 서버·pgvector)의 엔드투엔드 성능을 비교하지 않는다.
• DB 완제품 비교는 vector-db-benchmark가 쓰이는데, 이건 Qdrant가 주최하므로 결과 해석 시 주최측 편향을 감안해야 한다.

즉 "누가 제일 빠른가"는 라이브러리 벤치와 DB 벤치, 그리고 벤더 자사 벤치가 다 다르게 말한다. 그래서 자체 워크로드 실측이 필요하다.

한계와 함정

• 필터링과의 충돌 — 위에서 본 대로 HNSW의 가장 큰 실무 함정이다. ACORN·UNIFY 등 최근 연구의 활발한 주제다.
• 삭제·갱신 — 갱신이 그래프 전반에 연쇄 수정을 일으켜 write amplification이 크다. 삭제·재삽입이 쌓이면 도달 불가 노드가 생겨 recall이 조용히 떨어진다. 통상 일정량 누적 후 재빌드한다 — 실시간 대량 갱신에는 부적합하다.
• 메모리 상주 요구 — HNSW는 전체 그래프가 RAM에 있다고 가정한다. 메모리가 조금만 부족해 디스크로 스왑되면 성능이 부드럽게 저하되지 않고 절벽처럼 떨어진다. DiskANN·pgvectorscale 같은 디스크 기반 대안이 나온 이유다.
• 고차원에서의 거동 — 거리계산마다 고차원 벡터를 반복해 읽어 read amplification이 심하다. 여기서 SIMD·양자화가 성능을 좌우한다. 또 그래프가 커질수록 같은 ef_search로는 상대적으로 덜 탐색하게 되므로, 규모에 맞춰 ef_search를 올려야 한다.

정리 — 벤치를 설계한다면

• 파라미터를 맞추되 이름이 다름을 명시하라 — pgvector ef_search, Milvus ef, Lucene beamWidth, Qdrant hnsw_ef. 같은 개념이라도 제품마다 플래그가 다르다.
• 같은 M/ef여도 recall이 다르게 나오는 게 정상이다. 그래서 QPS를 그냥 비교하지 말고 ef_search를 sweep해 같은 recall 지점에서 비교한다.
• 필터링 성능을 반드시 축으로 넣어라 — 순수 벡터 검색 속도만으로는 Qdrant·Milvus의 필터 설계 강점이 드러나지 않는다.
• 메모리 상주 vs on-disk를 먼저 계산하라 — HNSW는 RAM 상주 전제라, 목표 규모가 인스턴스 메모리에 올라가는지(M에 비례하는 그래프 오버헤드 포함) 확인해야 한다.

이 글의 수치는 공개 벤치·벤더 문서 기반의 "출처 주장"이다. 실제 제품 선택은 자체 워크로드 벤치로 재검증한 뒤 판단한다.