벡터 검색 알고리즘 — 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 기반 검색이 더 잘 나오는 경우도 있다

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

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 — "작은 세계 네트워크" 구조. 멀어 보이는 노드도 몇 개의 링크만 타면 도달 가능

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

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

이 구조 덕에 데이터가 늘어도 속도 저하가 적고, 검색 속도가 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는 속도 ↔ 정확도 슬라이더처럼 쓴다.

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

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

HNSW의 약점

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

OpenSearch에서는 어떻게 동작하나

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

json

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

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

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

벡터 스토어 운영의 실전 설정은 OpenSearch를 VectorStore로 활용하기에서 더 다룬다.

정리

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

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

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

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

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

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

kNN의 한계 — brute force는 느리다

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

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

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 — "작은 세계 네트워크" 구조. 멀어 보이는 노드도 몇 개의 링크만 타면 도달 가능

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

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

이 구조 덕에 데이터가 늘어도 속도 저하가 적고, 검색 속도가 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는 속도 ↔ 정확도 슬라이더처럼 쓴다.

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

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

HNSW의 약점

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

OpenSearch에서는 어떻게 동작하나

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

json

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

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

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

벡터 스토어 운영의 실전 설정은 OpenSearch를 VectorStore로 활용하기에서 더 다룬다.

정리

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

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

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

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

kNN의 한계 — brute force는 느리다

ANN — 근사 최근접 이웃

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

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

왜 HNSW가 가장 많이 쓰이나

파라미터 3개만 알면 된다

HNSW의 약점

OpenSearch에서는 어떻게 동작하나

정리

이런 글도

댓글 (0)

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

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

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

kNN의 한계 — brute force는 느리다

ANN — 근사 최근접 이웃

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

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

왜 HNSW가 가장 많이 쓰이나

파라미터 3개만 알면 된다

HNSW의 약점

OpenSearch에서는 어떻게 동작하나

정리

이런 글도

댓글 (0)