Brain487. ANN (HNSW 인덱스) 근사 탐색 구조망
⚠️ 이 문서는 벡터 데이터베이스에 저장된 1억 개의 문서 중에서 나와 가장 비슷한 문서를 찾을 때, **1억 번의 각도 계산(Full Scan)을 하다가 서버가 터지는 것을 막기 위해 "정확도 100%는 포기할 테니까, 대충 99% 비슷한 놈으로 0.01초 만에 찾아줘!"라고 타협하는 'ANN' 기술과 그 끝판왕인 'HNSW 인덱스'**를 다룹니다.
핵심 인사이트 (3줄 요약)
- 본질: ANN(Approximate Nearest Neighbor)은 우주 공간에 뿌려진 수억 개의 점(벡터) 중에서 가장 가까운 이웃을 '대략적(Approximate)'으로 빨리 찾아내는 알고리즘들의 총칭이다.
- HNSW: ANN 알고리즘 중 현재 전 세계 벡터 DB(Milvus, Pinecone 등)가 표준으로 채택하고 있는 가장 압도적인 성능의 인덱스 구조다.
- 작동 원리: 데이터를 여러 층(Layer)의 네트워크망으로 연결해 두고, 꼭대기 층(듬성듬성한 망)에서 대충 위치를 찾은 뒤 $\rightarrow$ 점점 아래층(촘촘한 망)으로 내려가며 정확한 이웃을 찾아가는 '스킵 리스트 + 그래프 탐색'의 혼합 기술이다.
Ⅰ. 개요: 1억 명과 일일이 악수하기 (Context & Necessity)
"내 질문 벡터([0.1, 0.5])랑 가장 거리가 가까운 문서 5개를 찾아줘!"
- KNN (K-Nearest Neighbor, K-최근접 이웃): 가장 정확한 방법이다. 1억 개의 문서와 내 질문 사이의 코사인 유사도(486번 문서)를 1억 번 계산한다. 결과는 100% 정확하지만 검색에 10분이 걸린다. (실무 사용 불가)
이 문제를 해결하기 위해 등장한 것이 **ANN (근사 최근접 이웃)**이다. "1억 개를 다 계산하지 마! 미리 점들끼리 가깝게 뭉쳐있는 애들끼리 선을 그어놔(그래프 인덱스). 그리고 내 질문이 떨어지면, 그 근처에 있는 점들 1,000개 정도만 찔러보고 그 안에서 제일 가까운 놈을 리턴해버려!" 이 방식은 100% 가장 가까운 놈을 찾았다는 보장은 없지만, 99% 가까운 놈을 0.01초 만에 찾아낸다.
📢 섹션 요약 비유: KNN이 서울에서 강동원을 찾기 위해 **'천만 시민의 얼굴을 일일이 다 확인하는 무식한 경찰'**이라면, ANN(HNSW)은 **'지하철 노선도를 타고 가는 똑똑한 탐정'**입니다. 1호선을 타고 큰 동네를 대충 찾은 뒤, 동네 버스로 갈아타고, 마지막엔 골목길을 걸어서 강동원과 제일 비슷하게 생긴 사람을 순식간에 찾아냅니다.
Ⅱ. HNSW의 작동 원리 (Hierarchical Navigable Small World) ★
현재 모든 벡터 DB가 사용하는 마법의 인덱스, HNSW의 이름 뜻을 뜯어보자.
1. Navigable Small World (NSW - 작은 세상 그래프)
- "여섯 다리만 건너면 전 세계 사람을 다 안다"는 스몰 월드 이론에서 따왔다.
- 점(벡터)들을 거미줄처럼 다 연결해 놓되, 가까운 점들끼리 촘촘하게 묶고, 가끔 아주 멀리 있는 점과도 '고속도로(Long-range link)'를 뚫어놓은 형태다.
2. Hierarchical (H - 계층적 구조)
- NSW 그래프 하나만 있으면 탐색이 여전히 좀 느리다. 그래서 이 거미줄을 **아파트처럼 여러 층(Layer)**으로 쌓아 올렸다.
- Layer 3 (꼭대기 층): 점이 딱 3개만 있다. (고속도로 역할, 듬성듬성함)
- Layer 2 (중간 층): 점이 30개 있다.
- Layer 0 (바닥 층): 1억 개의 모든 점이 촘촘하게 다 연결되어 있다.
3. HNSW 탐색 과정 (Top-Down Search)
내 질문이 우주 공간에 떨어졌다.
- **꼭대기 층(Layer 3)**에서 시작한다. 점 3개 중 내 질문과 가장 가까운 1개를 찾는다.
- 그 점을 딛고 **아래층(Layer 2)**으로 내려간다. 아까 찾은 점 근처에 있는 거미줄을 타고 조금 더 정밀하게 가까운 점을 찾는다.
- 계속 파고 내려가서 **바닥 층(Layer 0)**에 도착하면, 최종적으로 내 질문과 가장 찰떡같이 붙어있는 점 5개를 찾아서 리턴한다.
┌──────────────────────────────────────────────────────────────┐
│ HNSW (계층적 네비게이션 스몰 월드) 탐색 시각화 │
├──────────────────────────────────────────────────────────────┤
│ │
│ [ 🏢 Layer 2 (꼭대기 층) ] 듬성듬성한 고속도로 │
│ (시작점) ──▶ (목표물 근처로 단숨에 50km 점프!) │
│ │ │
│ ▼ │
│ [ 🏢 Layer 1 (중간 층) ] 조금 더 촘촘한 국도 │
│ (착지) ──▶ ──▶ (목표물 근처로 5km 점프!) │
│ │ │
│ ▼ │
│ [ 🏢 Layer 0 (바닥 층) ] 모든 데이터가 있는 촘촘한 골목길 │
│ (착지) ──▶ ──▶ 🎯 (목표물 도착! 반경 100m 탐색 완료) │
│ │
│ ★ 특징: 1억 개를 다 비교하는 게 아니라, 층을 내려오며 몇십 번의 비교만으로 끝냄!│
└──────────────────────────────────────────────────────────────┘
Ⅲ. 실무 팁: 재현율(Recall)과 속도의 딜레마
ANN 인덱스를 만들 때 개발자는 파라미터를 조절해야 한다.
efConstruction/M(인덱스 생성 파라미터)- 거미줄을 얼마나 촘촘하게 칠 것인가?
- 촘촘하게 칠수록 나중에 찾을 때 100% 정답을 찾을 확률(Recall)이 올라가지만, 처음에 인덱스를 만드는 데 시간이 엄청나게 오래 걸리고 메모리 용량도 터져나간다.
- 실무의 타협점:
- 사람의 언어를 다루는 RAG(488번 문서) 시스템에서 정답이 '1등'이 아니라 '3등' 문서로 나와도 AI가 읽고 대답하는 데는 아무 지장이 없다.
- 따라서 속도를 위해 Recall을 95% 수준으로 살짝 양보하는 것이 벡터 DB 튜닝의 기본이다.
Ⅳ. 결론
"완벽함을 포기하는 순간, 무한한 확장의 문이 열린다." HNSW 알고리즘은 검색의 정확도를 1% 양보하는 대가로, 속도를 10,000배 끌어올린 컴퓨터 공학의 걸작이다. 만약 이 알고리즘이 없었다면 챗GPT에 수백만 장의 회사 문서를 집어넣고 질문하는 RAG 아키텍처는 매번 대답을 들을 때마다 1시간씩 기다려야 하는 쓰레기 시스템이 되었을 것이다. '벡터화된 데이터(Embedding)'와 이 데이터를 0.01초 만에 썰어내는 'HNSW 인덱스', 이 두 개의 날개가 결합하여 현대 AI 데이터베이스 혁명을 완성해 냈다.
📌 관련 개념 맵
- 기반 시스템: Vector DB (벡터 데이터베이스 - 485번 문서)
- 계산 공식: Cosine Similarity (코사인 유사도 - 486번 문서)
- 대척점 알고리즘: KNN (K-Nearest Neighbor - 100% 정확하지만 느린 풀스캔)
- 다른 ANN 알고리즘: LSH (Locality-Sensitive Hashing), IVF (Inverted File Index)
👶 어린이를 위한 3줄 비유 설명
- 1억 개의 구슬 중에서 파란색 구슬과 제일 비슷한 색깔을 찾으려고 해요.
- KNN 방식은 1억 개를 다 꺼내서 파란색이랑 대보는 거예요. 100년이 걸리겠죠.
- HNSW 방식은 헬기를 타고 하늘 높이(꼭대기 층) 올라가서 대충 '푸르스름한 동네'를 찾은 다음, 낙하산을 타고 그 동네에 딱 내려서 근처 구슬 10개만 확인하는 거랍니다! (0.1초 컷)