한양과기고 에듀테크 수업도구 대시보드

벡터 검색 & HNSW

AI가 문장·이미지를 임베딩(고차원 숫자 벡터)으로 바꾸면, "의미가 비슷한 것"을 찾는 문제는 "좌표가 가까운 벡터를 찾는 문제"가 된다. 그런데 수백만 개 벡터 중 진짜 최근접 이웃을 매번 완전탐색 O(N)으로 찾는 건 너무 느리다. HNSW(Hierarchical Navigable Small World)는 스킵 리스트처럼 층을 쌓은 그래프를 만들어, 위층에서 성큼성큼 이동하다 아래층으로 내려가며 "거의 맞는" 답을 O(log N)급으로 빠르게 찾는다. RAG·시맨틱 검색·추천 시스템의 핵심 엔진이다.

인터랙티브 데모 — 2D로 축소한 임베딩 공간

상위 레이어 (Layer 1) — 성긴 그래프, 진입점에서 장거리 이동

지역 최적(더 가까운 이웃 없음) 도달 → 현재 노드를 진입점 삼아 한 층 아래로

최하위 레이어 (Layer 0) — 촘촘한 그래프, 전체 노드 포함

–

그래프 탐색 이동 횟수

–

전수조사 필요 비교 횟수 N

–

절약한 비교 비율

–

진짜 최근접과 일치?

노란 별 = 쿼리 벡터. 보라색 경로 = HNSW가 실제로 밟은 노드. 초록 = HNSW가 찾은 답, 분홍 점선 테두리 = 전수조사로 확인한 진짜 최근접 이웃(같으면 겹쳐서 초록 하나만 보임). 가끔 두 개가 다를 수 있는데, 이것이 바로 HNSW가 근사(approximate) 알고리즘인 이유다.

왜 층을 쌓는가

스킵 리스트가 정렬된 1차원 리스트 위에 급행 노선을 쌓듯, HNSW는 벡터 공간 위에 급행 노선을 쌓는다. 각 노드가 위층에 속할 확률은 지수적으로 감소하므로(예: 1/2, 1/4, ...) 위층일수록 노드 수가 적고 간선은 더 멀리 뻗는다. 탐색은 항상 맨 위층의 고정된 진입점에서 시작해 "지금 있는 곳보다 쿼리에 더 가까운 이웃이 있으면 그쪽으로 이동"하는 그리디(탐욕) 탐색을 반복하고, 더 가까운 이웃이 없어 멈추면(지역 최적) 같은 위치에서 한 층 아래로 내려가 더 정밀하게 탐색을 이어간다. 맨 아래층(전체 노드 포함)에서 멈춘 지점이 최종 답이다.

탐색 의사코드

# query와 가장 가까운 노드를 근사적으로 찾는다
def search(query):
    current = ENTRY_POINT              # 맨 위층 고정 진입점
    for layer in range(TOP_LAYER, -1, -1):
        while True:
            best = min(neighbors(current, layer),
                       key=lambda nb: dist(nb, query))
            if dist(best, query) < dist(current, query):
                current = best          # 더 가까우면 이동 (그리디)
            else:
                break                  # 지역 최적 → 다음 층으로
    return current                    # 최하위층에서 멈춘 곳 = 근사 최근접 이웃

다른 최근접 이웃 탐색 방법과 비교

방법	탐색 복잡도	정확도	특징
완전탐색 (Brute-force)	`O(N)`	정확	모든 벡터와 거리 계산, 작은 데이터셋엔 충분
KD-Tree / Ball Tree	저차원 `O(log N)`	정확	차원이 커지면(차원의 저주) 사실상 전수조사와 비슷해짐
LSH (지역 민감 해싱)	`O(1)`~	근사	비슷한 벡터를 같은 해시 버킷에 모음, 블룸 필터와 사촌 관계
HNSW	`O(log N)` 근사	근사(매우 높음)	그래프 기반, 현재 벡터 DB 업계 표준(Faiss·Pinecone·Milvus·pgvector)

핵심 정리

임베딩

문장·이미지를 의미가 가까울수록 가까운 좌표에 놓이는 고차원 벡터로 변환. 검색을 기하학 문제로 바꾼다.

정확도-속도 트레이드오프

HNSW는 진짜 최근접이 아닐 수도 있는 근사 답을 내주는 대신, 수백만 벡터도 밀리초 단위로 검색한다.

RAG의 핵심 엔진

LLM이 질문과 의미가 비슷한 문서 조각을 찾아 답변에 참고하는 검색 증강 생성이 바로 이 위에서 동작한다.

스킵 리스트의 후예

확률적으로 성긴 상위 레이어를 쌓는 아이디어는 스킵 리스트의 다층 구조를 벡터 공간으로 확장한 것.