벡터 데이터베이스가 근사 최근접 이웃(ANN)이 필요한 이유: HNSW 그래프와 차원의 저주

만약 검색 증강 생성(RAG) 파이프라인이나 의미론적 검색 엔진을 구축하고 있다면, 당신의 벡터 데이터베이스는 아마도 마법 같은 일을 하고 있을 것입니다. 1000만 개의 문서 중 가장 관련성이 높은 상위 5개를 20밀리초 이내에 반환하는 식입니다.

대부분의 개발자에게 벡터 검색은 마치 마법처럼 느껴집니다. 임베딩 벡터(예를 들어 OpenAI에서 나온 1536차원)를 전달하면, 데이터베이스가 즉시 가장 가까운 벡터들을 찾아냅니다.

# 단순한 벡터 유사성의 착각
results = vector_db.similarity_search(query_vector, k=5)

하지만 내부적으로 볼 때, 당신의 벡터 데이터베이스는 컴퓨터 과학의 근본적인 법칙을 깨고 있습니다. 이는 정확한 검색(exact search) 대신 근사 최근접 이웃(Approximate Nearest Neighbor, ANN) 검색을 사용하고 있기 때문입니다. 만약 정확한 검색을 사용한다면, 하나의 쿼리만 처리하는 데 몇 초 또는 심지어 몇 분이 걸릴 것입니다.

정확한 벡터 검색이 대규모에서 왜 실패하는지, 차원의 저주(curse of dimensionality)가 실제로 무엇인지, 그리고 HNSW (Hierarchical Navigable Small World)와 같은 알고리즘이 어떻게 번개처럼 빠른 의미론적 검색을 가능하게 하는지에 대해 깊이 파헤쳐 보겠습니다.

1. 순진한 접근 방식: 정확 최근접 이웃(Exact Nearest Neighbor, KNN)

쿼리에 가장 유사한 벡터를 찾기 위한 가장 직관적인 방법은 쿼리 벡터와 데이터셋의 모든 단일 벡터 간의 거리(코사인, 유클리드 또는 내적)를 계산하는 것입니다.

import numpy as np

def exact_knn(query, database, k=5):
...

이것을 K-최근접 이웃(K-Nearest Neighbors, KNN) 또는 플랫 인덱싱(flat indexing)이라고 부릅니다.

플랫 인덱싱이 대규모에서 실패하는 이유

복잡도 이론에서 정확한 KNN은 시간 복잡도가 **$O(N \cdot D)$**입니다. 여기서:

• $N$은 데이터베이스의 벡터 개수입니다.
• $D$는 각 벡터의 차원성입니다 (예: OpenAI text-embedding-3-small의 1536).

만약 당신이 1000만 개의 벡터를 가지고 있고, 각각이 32비트 부동 소수점(float)으로 된 1536차원($1536 \times 4$ 바이트 $\approx$ 벡터당 6KB)이라면, 데이터셋 크기는 약 60 GB에 달합니다.

모든 단일 질의(query)마다, CPU나 GPU는 거리 공식(distance formulas)을 계산하기 위해 산술 논리 장치(arithmetic logic units)를 거쳐 60 GB의 RAM을 스트림으로 처리해야 합니다. 최신 하드웨어에서 메모리 대역폭은 심각한 병목 현상을 일으킵니다. 1,000만 개의 벡터에 대한 단일 정확 검색(exact search)만 해도 500ms에서 2초가 걸릴 수 있으며, 이는 실시간 채팅 애플리케이션의 사용자 경험을 완전히 망가뜨립니다.

2. 차원의 저주 (The Curse of Dimensionality)

'왜 표준 데이터베이스 인덱싱(B-Trees나 KD-Trees 같은)을 사용할 수 없는 걸까?'라고 궁금해할 수 있습니다.

그 답은 Richard Bellman이 만든 수학적 현상인 차원의 저주에 있습니다. 벡터 차원(2D/3D에서 768D, 1536D, 또는 4096D로)이 증가함에 따라 공간의 기하학적 속성이 근본적으로 무너집니다.

1. 거리 집중 (Distance Concentration): 고차원 공간에서는 임의의 지점에서 가장 가까운 이웃과 가장 먼 이웃 사이의 거리가 거의 같은 값으로 수렴합니다. 모든 것이 서로에게 등거리에 있습니다.
2. 희소성 (Sparsity): 고차원 공간은 압도적으로 비어 있습니다. 공간을 조밀하게 채우려면 필요한 데이터 포인트 수가 차원에 따라 기하급수적으로 증가합니다.
3. 인덱스 퇴화 (Index Degeneration): 공간 분할 트리(KD-Trees, R-Trees, Quad-Trees 같은)는 공간을 초직육면체(hyperrectangles)로 나눕니다. 고차원에서는 트리 순회가 거의 모든 리프 노드를 방문하는 것으로 저하됩니다. 1536 차원의 KD-트리는 평평한 선형 스캔보다 성능이 떨어집니다!

전통적인 공간 인덱스가 실패하기 때문에, 벡터 데이터베이스는 **공간 분할(space-partitioning), 양자화(quantization), 또는 그래프 기반 근사(graph-based approximation)**에 의존해야 합니다.

3. 근사 최근접 이웃 (Approximate Nearest Neighbor, ANN)의 등장

100% 정확도(절대적으로 수학적으로 가장 가까운 벡터를 찾는 것)를 보장하는 대신, ANN 알고리즘은 아주 작은 정확도의 손실(예: 95%99% 재현율(recall))을 감수하고 엄청난 속도 향상(100배1000배 빠름)을 얻습니다.

주요 ANN 알고리즘 계열은 세 가지가 있습니다:

1. Inverted File Index (IVF): 벡터를 클러스터로 양자화(K-Means 사용)한 다음, 쿼리에 가장 가까운 클러스터만 검색합니다.
2. Product Quantization (PQ): 고차원 벡터를 서브벡터로 분할하고 각 서브벡터를 양자화하여 압축함으로써 메모리 사용량을 대폭 줄이고 조회 테이블을 통해 거리 계산 속도를 높입니다.
3. Graph-Based Indexes (HNSW): 벡터가 노드(node)가 되고 유사도가 엣지(edge)로 표현되는 근접성 그래프를 구성합니다. 검색은 탐욕적(greedy) 그래프 순회 과정이 됩니다.

이러한 방법들 중, **HNSW (Hierarchical Navigable Small World)**는 Qdrant, Milvus, Chroma, pgvector와 같은 고성능 벡터 데이터베이스의 표준으로 자리 잡았습니다.

4. HNSW 작동 원리

HNSW는 스몰 월드 네트워크 현상(

1. 진입점(Entry Point): 질의(query)가 도착하면 지정된 진입 노드에서 최상위 레이어(가장 희소한 그래프)를 통해 시작합니다.
2. 탐욕적 라우팅(Greedy Routing): 알고리즘은 현재 노드의 모든 이웃을 살펴보고, 질의 벡터에 가장 가까운 이웃을 찾아 그곳으로 '점프'합니다. 이 탐욕적인 검색을 해당 레이어에서 지역 최소값(local minimum)에 도달할 때까지 반복합니다.
3. 레이어 하강(Layer Drop): 지역 최소값에 도달하면, 아래 레이어의 대응하는 노드로 내려갑니다 (이 레이어는 더 밀집된 연결을 가집니다).
4. 최종 정제(Final Refinement): Layer 0(모든 벡터를 포함하는 최하단 레이어)에서는 상위 $K$개의 최근접 이웃을 찾기 위해 철저한 지역 검색을 수행합니다.

Layer 2 (Sparse):    (A) -------------------> (B)
                      |                        |
Layer 1 (Medium):    (A) ---------> (C) ----> (B) -------> (D)
...

HNSW가 매우 빠른 이유

• 로그 시간 복잡도 (Logarithmic Complexity): HNSW 그래프 검색은 $O(N)$이 아닌 **$O(\log N)$**으로 확장됩니다.
• 전체 스캔 없음 (No Exhaustive Scan): 98%+의 재현율(recall) 정확도를 유지하면서 데이터베이스의 아주 작은 부분(종종 1% 미만)의 노드만을 방문합니다.

5. 트레이드오프 및 엔지니어링 고려 사항

HNSW는 질의에 대해 매우 빠르지만, 특정한 엔지니어링 트레이드오프를 수반합니다:

1. 높은 RAM 사용량: HNSW 그래프는 벡터 자체 외에도 벡터 간의 포인터(간선)를 RAM에 저장합니다. HNSW 인덱스는 원본 벡터 메모리 크기의 1.5배에서 2배에 달하는 용량을 쉽게 소비할 수 있습니다.
2. 느린 인덱스 구축 시간: HNSW 그래프를 구축하려면 벡터를 하나씩 삽입하고, 거리를 계산하여 지역적 이웃을 찾으며, 양방향 링크를 업데이트해야 합니다. 대량 데이터(Bulk ingestion)의 경우 플랫 인덱스보다 훨씬 느릴 수 있습니다.
3. efSearch 및 M 매개변수:
   • M: 그래프 내 노드당 최대 양방향 링크 개수입니다. M 값이 높을수록 재현율(recall)이 향상되지만, 메모리와 구축 시간이 증가합니다.
   • efConstruction / efSearch: 그래프 구축 및 검색 중 동적 후보 목록의 크기입니다. 이 값들이 높을수록 정확도가 높아지지만, 쿼리 지연 시간(query latency)을 감수해야 합니다.

요약

벡터 데이터베이스가 마법을 부리는 것은 아닙니다. 대신 복잡한 그래프 이론과 확률적 자료 구조를 활용하여 차원의 저주(curse of dimensionality)를 우회합니다.

• 정확한 KNN ($O(N)$): 메모리 대역폭 병목 현상 때문에 수백만 개의 고차원 벡터에는 너무 느립니다.
• 차원의 저주: 전통적인 공간 트리 구조는 고차원 공간이 희소하고 모든 점들이 등거리(equidistant)하다는 문제 때문에 실패합니다.
• HNSW ($O(\log N)$): 다층 근접 그래프(skip list와 유사함)를 사용하여 최소한의 정확도 손실로 서브밀리초(sub-millisecond) 근사 최근접 이웃 검색을 가능하게 합니다.

ANN이 내부적으로 어떻게 작동하는지 이해하면 M 및 efSearch 같은 매개변수를 적절하게 조정하고, 메모리 예산을 관리하며, 프로덕션 RAG 시스템에 맞는 올바른 벡터 저장 백엔드를 선택할 수 있습니다.