벡터 검색 엔진을 밑바닥부터 구축하기: HNSW의 수학과 메커니즘

이것은 발췌본입니다. 전체 기사에는 실시간 2D 벡터 공간 샌드박스가 포함되어 있습니다. — 쿼리 벡터를 의미론적 좌표 필드 위로 드래그하면, Brute Force KNN과 HNSW 스킵 그래프 (skip-graph) 탐색 모드 간의 전환을 통해 9개의 프레임워크 노드에서 코사인 유사도 (cosine similarity) 점수가 실시간으로 업데이트되는 것을 확인할 수 있습니다. 전체 인터랙티브 버전 읽기 →

의미론의 기하학 (The Geometry of Semantics)

대규모 언어 모델 (LLM) 시대에 비정형 텍스트는 단순한 원시 문자가 아니라, **고차원 수학적 공간에서의 벡터 좌표 (vector coordinate)**로 취급됩니다.

텍스트를 임베딩 모델 (예: Google의 text-embedding-004)에 전달하면, 모델은 의미론적 의미를 부동 소수점 숫자 배열로 매핑합니다:

"Redis In-Memory Cache" → [ 0.01249, -0.04581, 0.08914, ..., -0.00312 ]  // 3072 차원 (dimensions)
"PostgreSQL Database"   → [ 0.01183, -0.04491, 0.08877, ..., -0.00298 ]  // 3072 차원 (dimensions)
"PyTorch Model"         → [-0.09214,  0.07321, -0.03812, ...,  0.06441 ]  // 3072 차원 (dimensions)

이 잠재 공간 (latent space) 내에서 개념적으로 유사한 텍스트는 기하학적으로 가깝게 위치합니다. "Redis"와 "PostgreSQL"은 서로 가까운 곳에 클러스터링됩니다 (둘 다 데이터베이스임). "PyTorch"는 멀리 떨어져 있습니다 (AI/ML 도메인).

의미론적 검색 (Semantic search) = 쿼리 벡터에 대해 K-최근접 이웃 (K-nearest neighbor, KNN) 좌표를 찾는 것.

수학적 거리 측정 지표 (The Mathematical Distance Metrics)

벡터 유사도 계산에는 세 가지 지표가 주로 사용됩니다:

1. 코사인 유사도 (Cosine Similarity, NLP에서 가장 흔히 사용됨)

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

두 벡터 사이의 **각도 투영 (angular projection)**을 측정합니다. 범위는 -1에서 1 사이입니다. 크기 (magnitude)를 완전히 무시합니다. 즉, 두 벡터가 같은 방향을 가리키고 있다면 하나가 100배 더 길더라도 점수는 1.0이 됩니다. 이는 크기가 의미론적 정보를 담고 있지 않은 텍스트 임베딩에 이상적입니다.

2. 내적 (Dot Product, 정규화된 벡터에 가장 빠름)

A · B = Σ(Aᵢ × Bᵢ)

벡터가 L2-정규화(L2-normalized, 단위 길이 = 1)된 경우, 내적(Dot Product)은 코사인 유사도(Cosine Similarity)와 **동일한 순위(identical rankings)**를 산출하면서도 계산량은 현저히 적습니다. 데이터를 수집(Ingestion)할 때 임베딩(Embedding)을 정규화한 다음, 쿼리(Query) 시점에 내적을 사용하십시오.

3. L2 유클리드 거리 (L2 Euclidean Distance, 공간 데이터용)

d(A, B) = √(Σ(Aᵢ - Bᵢ)²)

벡터 끝점 사이의 가공되지 않은 물리적 거리를 측정합니다. 크기(Magnitude) 변화에 매우 민감합니다. 원시 텍스트 임베딩(Raw text embeddings)보다는 좌표 기반의 공간 시스템(Coordinate-based spatial systems)에 선호됩니다.

확장성의 병목 현상: 브루트 포스(Brute Force)가 실패하는 이유

단순한 브루트 포스 KNN (Brute Force KNN) 방식에서는 쿼리 벡터를 데이터베이스 내의 모든 문서와 비교합니다.

복잡도: O(D × N)  — 여기서 D = 차원(Dimensions), N = 문서 수(Document count)

규모가 커지면 브루트 포스는 CPU를 포화시키고 실시간 응답 요구 사항을 파괴합니다. 따라서 근사 최근접 이웃 (Approximate Nearest Neighbor, ANN) 인덱싱이 필요합니다.

HNSW: 계층적 탐색 가능 소세계 (Hierarchical Navigable Small World)

HNSW는 스킵 리스트(Skip List) 데이터 구조를 다층 그래프(Multi-layered graph)로 변환합니다.

LAYER 2 (Sparse Highway) ─── node_A ──────────────────── node_B ───
LAYER 1 (Intermediate)   ─── node_A ─── node_C ─── node_B ─── node_D
LAYER 0 (Dense Ground)   ─ 모든 노드가 이웃과 완전히 연결됨 ──

이를 통해 탐색 복잡도를 다음과 같이 줄입니다.

Brute Force: O(N)         → 선형(Linear) — 대규모에서 실패
HNSW:        O(log N)     → 로그(Logarithmic) — 1,000만 개 이상의 문서에서 5ms 미만

TypeScript HNSW 구현

class HNSWIndex {
  private layers: Map<string, string[]>[] = [];
  private vectors: Map<string, number[]> = new Map();
...

프로덕션 확장 (Production Scaling)

메모리 맵 파일 (Memory-Mapped Files, mmap): 대규모 인덱스를 RAM에 유지하면 OOM(Out of Memory) 충돌이 발생합니다. 바이너리 인덱스 파일을 가상 주소 공간(Virtual address space)에 직접 바인딩하십시오. 그러면 운영체제(OS)가 쿼리 패턴에 따라 벡터 블록을 디스크 캐시로 자동으로 스왑(Swap)합니다.

곱 양자화 (Product Quantization, PQ): 각 고차원 벡터를 하위 벡터(Sub-vectors)로 나누고 이를 중심점(Centroids)에 매핑합니다. 이를 통해 재현율(Recall) 저하를 최소화하면서 메모리 사용량을 최대 95%까지 줄일 수 있습니다.

엔지니어링 시사점 (Engineering Takeaways)

**임베딩 (embeddings) 삽입 시 항상 L2-정규화 (L2-normalize)**를 수행하여, 전체 코사인 유사도 계산 대신 빠른 내적 (dot product) 점수 산출이 가능하도록 하세요.
HNSW는 $O(N)$을 $O(\log N)$으로 줄여줍니다 — 이는 대규모 벡터 검색 (vector search)에서 가장 영향력 있는 단일 최적화 요소입니다.
프로덕션 환경에서 수천만 개의 벡터를 메모리 부족 (OOM) 없이 처리하려면 **mmap + 곱 양자화 (Product Quantization)**를 사용하세요.

전체 기사에는 드래그 앤 드롭 방식의 2D 의미 공간 (semantic space) 샌드박스가 포함되어 있습니다 — 잠재 좌표계 (latent coordinate field)에 배치된 9개의 프레임워크 노드, 실시간 코사인 유사도 (cosine similarity) 리더보드, 브루트 포스 (Brute Force)와 HNSW 스킵 그래프 (skip-graph) 모드 간의 전환, 그리고 실시간 레이어 순회 (layer traversal) 시각화를 제공합니다.

전체 인터랙티브 기사 읽기 →

작성자: Ebenezer Akinseinde — 소프트웨어 개발자 및 AI 자동화 엔지니어 (AI Automations Engineer).

포트폴리오 (Portfolio) · GitHub