벡터 검색 알고리즘 — kNN에서 HNSW까지

임베딩으로 텍스트를 벡터로 바꾸고 나면, "질문 벡터와 가장 가까운 문서 벡터"를 찾아야 한다. 이 글은 그 검색을 담당하는 알고리즘을 kNN(개념) → 왜 느린가 → ANN → HNSW(실전 표준) 순서로 정리한다.

kNN — 가장 가까운 k개를 찾는다

• kNN(k-Nearest Neighbors) = 어떤 벡터(쿼리)와 가장 가까운 k개의 이웃 벡터를 찾는 알고리즘
• 예를 들어
  • 문서 임베딩이 1536차원 벡터로 저장되어 있고
  • 사용자가 질문했을 때 질문도 벡터로 변환되면
  • "질문 벡터와 가장 가까운 문서 벡터 k개를 찾아라"가 곧 kNN

벡터 간 "가까움"은 어떻게 계산하나

• Cosine Similarity (RAG에서 거의 표준)
  • 각도 기반 유사도 — 두 벡터의 방향이 얼마나 비슷한가
  • 텍스트 임베딩에 가장 잘 맞아 보통 이걸 쓴다
• Euclidean Distance (L2 거리)
  • 벡터 좌표 간 물리적 거리
• Dot Product (내적)
  • 크기 + 방향을 모두 고려
  • OpenAI 등 최신 모델은 dot product 기반 검색이 더 잘 나오는 경우도 있다

어떤 거리를 쓰는지는 임베딩 모델이 권장하는 것을 따르는 게 안전하다 — 모델이 그 거리로 학습됐기 때문이다.

코사인은 사실 내적으로 계산된다. cos = (A·B) / (|A|·|B|) 인데, 저장할 때 벡터를 L2 정규화(크기를 1로)하면 |A|=|B|=1 이라 코사인이 그냥 내적(A·B)이 된다. 그래서 대부분의 벡터 DB가 정규화 후 빠른 내적으로 코사인을 처리한다(OpenSearch cosinesimil, faiss cosine). HNSW는 유사도가 아니라 거리로 다루므로 1 − 코사인으로 변환해 쓴다.

kNN의 한계 — brute force는 느리다

정직하게 kNN을 하려면 쿼리 벡터와 모든 문서 벡터의 거리를 다 계산해야 한다.

• 쿼리 벡터 1개
• 문서 벡터 N개 (예: 1천만 개)
• 계산량 = 1천만 번 거리 계산

이걸 brute-force kNN이라고 한다. 차원이 높고 데이터가 많으면 실시간 서비스가 불가능하다. 그래서 "정확함을 조금 포기하고 훨씬 빠르게" 찾는 기술이 필요해진다.

ANN — 근사 최근접 이웃

ANN(Approximate Nearest Neighbor)은 정확한 이웃을 찾는 대신 이런 목표를 갖는다.

• 정확도 98~99% 수준
• 속도는 brute-force 대비 수백~수천 배 빠름

대표 ANN 알고리즘으로 HNSW, FAISS의 IVF+PQ, ScaNN, Annoy 등이 있다. 이 중 벡터 DB·검색 엔진이 사실상 표준으로 채택한 것이 HNSW다.

HNSW — 그래프로 빠르게 좁힌다

HNSW(Hierarchical Navigable Small World graph)는 이름에 구조가 다 들어 있다.

• Hierarchical — 여러 계층(layer)으로 구성됨
• Navigable — 그래프를 탐색하기 쉬움
• Small World graph — "작은 세계 네트워크" 구조. 멀어 보이는 노드도 몇 개의 링크만 타면 도달 가능

핵심 아이디어 — 층을 내려가며 좁힌다

1. 임베딩 벡터들을 여러 층(layer)의 그래프로 저장한다
   • 위층은 거칠고 넓은 탐색
   • 아래층은 정교하고 근접한 탐색
2. 쿼리 벡터가 들어오면 높은 층에서 시작해 후보 노드를 찾고
3. 점점 아래층으로 내려오며 더 가까운 이웃을 좁힌다

이 구조 덕에 데이터가 늘어도 속도 저하가 적고, 검색 속도가 O(log N)에 가까워진다.

한 줄로 줄이면 — "kNN을 실시간에 쓸 수 있게 만든 알고리즘이 HNSW"다.

왜 HNSW가 가장 많이 쓰이나

• 정확도가 높다 — LSH·IVF·PQ·Annoy 등에 비해 정확도가 앞선다. 데이터 100만 개, ef_search=200 기준 97~99%.
• 검색이 빠르다 — 데이터가 늘어도 성능 저하가 작다(logarithmic).
• 증분 삽입(incremental insert) 지원 — 벡터를 추가해도 전체 인덱스를 다시 만들 필요가 없다. "문서 추가 → 임베딩 → 저장" 구조인 RAG에 특히 중요하다. (FAISS의 IVF-PQ는 index rebuild가 필요해 불편)
• 산업 표준 — OpenSearch·Pinecone·Milvus·FAISS·NMSLIB 등 거의 모든 벡터 DB가 지원한다.

파라미터 3개만 알면 된다

HNSW는 튜닝이 직관적이다.

• M — 그래프의 branching factor(노드당 연결 수)
• ef_construction — 인덱스 빌드 시 정확도
• ef_search — 검색 시 품질

특히 ef_search는 속도 ↔ 정확도 슬라이더처럼 쓴다.

• 높이면 → 정확도 ↑, 속도 ↓
• 낮추면 → 속도 ↑, 정확도 ↓

운영 중에 품질과 속도를 조절하기 쉽다.

파라미터 상호작용(M↔ef_construction), 구현체별(FAISS·Lucene·Qdrant·pgvector·Milvus) 성능 차이, 필터링 충돌 같은 심화 주제는 HNSW 심화 — 파라미터 튜닝과 구현체별 성능 차이에서 다룬다.

HNSW의 약점

• 메모리 사용량이 크다 — 그래프를 유지해야 해서 벡터 하나당 메모리 오버헤드가 생긴다.
• 인덱스 빌드 비용이 크다 — 빌드 시간이 PQ 기반보다 느릴 수 있다.
• 초대규모에는 부담 — 수십억 벡터 이상이면 IVF-PQ 같은 다른 솔루션이 필요하다. 다만 대부분 서비스(수백만~수천만)는 HNSW로 충분하고, RAG도 대개 HNSW를 선호한다.

메모리에 무엇이 올라가나

HNSW가 빠른 대가는 메모리다. 세 가지가 올라간다.

1. 벡터 원본 — 거리 계산에 실제 값이 필요해서, 양자화를 안 하면 원본이 그대로 메모리에 있어야 한다. 1024차원이면 노드당 4KB(float32 기준). 이게 메모리의 대부분이다.
2. 그래프 링크 — 각 노드가 가진 이웃 id 리스트. 노드당 최대 M개(최하층은 2M)라 벡터보다는 작지만 무시할 수 없다.
3. id 매핑 — 내부 id와 외부 문서 id의 대응.

예를 들어 1천만 벡터에 1024차원이면 벡터만 약 40GB다. "벡터를 메모리에 올린다"가 곧 HNSW의 비용이다.

메모리 줄이기 — 양자화·DiskANN

• 양자화 — PQ/SQ로 벡터를 압축한다. float32 → int8이면 약 1/4. recall을 조금 내주고 메모리를 크게 아낀다.
• DiskANN·mmap — 그래프·벡터를 디스크에 두고 일부만 메모리에 올린다. 검색 지연이 늘지만, 트래픽이 낮으면 충분히 감당된다.

즉 "HNSW = 무조건 풀 메모리"가 아니라, 규모와 트래픽에 따라 일부를 디스크로 내릴 수 있다.

OpenSearch에서는 어떻게 동작하나

OpenSearch에서 vector 인덱스를 만들 때 이렇게 설정한다.

{
  "method": {
    "name": "hnsw",
    "engine": "faiss",
    "space_type": "cosinesimil"
  }
}

• name: hnsw → ANN 기반 그래프 사용
• engine: faiss → Facebook FAISS 엔진(가장 빠른 축)
• space_type: cosinesimil → 코사인 유사도로 계산

즉 OpenSearch는 내부적으로 kNN을 ANN(HNSW) 방식으로 최적화한 그래프 탐색으로 처리한다.

OpenSearch 를 벡터 DB 로 운영하는 실전(native 메모리·샤드)은 OpenSearch를 벡터 DB로 굴리며 알게 된 것, 검색 품질(hybrid·rerank)은 OpenSearch로 RAG 검색 품질 높이기에서 다룬다.

정리

• kNN은 "가장 가까운 k개"라는 개념이고, brute-force로는 느리다.
• 그래서 정확도를 조금 양보하고 빠르게 찾는 ANN이 등장했다.
• ANN의 실전 표준이 HNSW — 계층 그래프로 후보를 좁혀 O(log N)에 가깝게 검색하고, ef_search로 속도와 정확도를 조절한다.
• 대부분의 RAG·벡터 DB가 HNSW를 기본으로 쓴다.