[LLM Wiki 21] HNSW는 어떻게 수백만 벡터에서 가까운 문서를 찾을까
HNSW의 발음부터 벡터, 근사 최근접 이웃, 계층형 그래프의 탐색 과정, M과 ef 설정, 필터 검색의 주의점까지 그림으로 설명합니다.
HNSW는 보통 알파벳 그대로 “에이치 엔 에스 더블유”라고 읽습니다. 전체 이름은 Hierarchical Navigable Small World입니다. 직역하면 ‘계층형 탐색 가능 소세계’인데, 이름만으로는 무슨 일을 하는지 알기 어렵습니다.
한 문장으로 줄이면 이렇습니다.
HNSW는 수많은 벡터를 여러 층의 그래프로 연결해 두고, 모든 벡터를 확인하지 않으면서 질문과 가까운 벡터를 빠르게 찾는 검색 인덱스입니다.
여기서 인덱스(index)는 검색을 빠르게 하려고 미리 만들어 두는 탐색용 구조입니다. 책 뒤의 찾아보기나 지도와 비슷한 역할을 합니다.
먼저 벡터가 무엇인가
AI 검색에서는 문장, 이미지, 상품 같은 데이터를 숫자 배열로 바꿉니다. 이 숫자 배열을 벡터(vector)라고 합니다. 문장을 벡터로 바꾸는 작업은 임베딩(embedding)이라고 부릅니다.
예를 들어 실제 벡터는 훨씬 길지만, 개념만 단순화하면 다음과 같습니다.
“점포 침수 대응 절차” → [0.12, -0.41, 0.73, ...]
“폭우 피해 처리 방법” → [0.09, -0.38, 0.69, ...]
“직원 휴가 신청 방법” → [-0.52, 0.20, 0.11, ...]의미가 비슷한 문장끼리는 벡터 공간에서도 가까운 곳에 놓이도록 임베딩 모델을 학습합니다. 사용자의 질문도 벡터로 바꾼 뒤 가까운 문서 벡터를 찾으면 의미 검색을 할 수 있습니다.
이때 두 벡터가 얼마나 가까운지는 거리 함수(distance metric)로 계산합니다. 자주 쓰는 방법으로 코사인 거리, 유클리드 거리, 내적이 있습니다. 어떤 거리 함수를 사용할지는 임베딩 모델의 특성과 검색 시스템 설정에 맞춰야 합니다.
모든 벡터와 비교하면 정확하지만 느리다
질문과 가장 가까운 문서를 찾는 가장 단순한 방법은 질문 벡터를 저장된 모든 벡터와 비교하는 것입니다. 이를 전수 검색(full scan) 또는 brute-force search라고 합니다.
문서가 1,000개라면 1,000개를 비교하고, 1,000만 개라면 1,000만 개를 비교합니다. 가장 가까운 결과를 정확하게 찾을 수 있지만 데이터가 커질수록 계산량과 응답시간이 증가합니다.
HNSW는 모든 벡터를 확인하는 대신, 가까운 벡터끼리 미리 연결한 그래프에서 유망한 경로만 따라갑니다. 이런 문제를 근사 최근접 이웃 검색(Approximate Nearest Neighbor Search, ANN)이라고 합니다.
- 최근접 이웃은 질문 벡터와 가장 가까운 벡터를 뜻합니다.
- 근사는 모든 후보를 확인하지 않으므로 진짜 1등을 놓칠 수 있다는 뜻입니다.
HNSW는 정확한 정답 보장 일부를 포기하고 검색 속도를 얻습니다. 대신 설정을 조정해 속도와 검색 품질 사이의 균형을 바꿀 수 있습니다.
NSW, 가까운 점과 먼 지름길을 함께 연결한다
HNSW를 이해하려면 이름 뒤쪽의 NSW(Navigable Small World)부터 보는 것이 좋습니다.
그래프(graph)는 데이터를 점으로, 데이터 사이의 관계를 선으로 표현한 구조입니다. HNSW에서는 벡터 하나가 점 하나가 되고, 서로 가까운 벡터를 선으로 연결합니다. 그래프 용어로 점은 노드(node), 선은 엣지(edge)라고 합니다.
가까운 노드끼리만 연결하면 주변을 정밀하게 탐색하기는 좋지만 멀리 이동하기 어렵습니다. 반대로 먼 곳으로 건너가는 연결이 조금 섞여 있으면 적은 단계만으로 다른 지역에 도달할 수 있습니다. 이를 small-world network, 즉 소세계 네트워크라고 부릅니다.
사람 관계를 떠올리면 이해하기 쉽습니다. 대부분은 가까운 동료나 친구와 연결돼 있지만, 몇 사람을 거치면 다른 나라의 전문가에게도 도달할 수 있습니다. HNSW도 촘촘한 지역 연결과 멀리 건너가는 연결을 이용해 질문과 비슷한 벡터가 모여 있는 지역으로 이동합니다.
H, 여러 층을 만들어 탐색을 빠르게 한다
HNSW의 앞 글자 H는 Hierarchical, 즉 계층형이라는 뜻입니다. 그래프를 한 층으로만 만들지 않고 여러 층으로 쌓습니다.
- 상위층에는 일부 노드만 있어 연결이 성깁니다.
- 아래층으로 내려갈수록 노드가 많아지고 연결이 촘촘해집니다.
- 바닥층인 Layer 0에는 모든 벡터가 들어갑니다.
새 벡터가 어느 높이까지 올라갈지는 무작위 확률에 따라 결정됩니다. 대부분은 바닥층에만 있고, 일부는 중간층까지, 더 적은 일부만 최상위층까지 올라갑니다. 그래서 위로 갈수록 노드 수가 빠르게 줄어듭니다.
탐색 과정은 고속도로에서 골목길로 들어가는 과정과 닮았습니다.
- 최상위층의 진입점에서 시작합니다.
- 현재 노드와 연결된 이웃 중 질문에 더 가까운 노드로 이동합니다.
- 더 가까워지는 이웃이 없으면 한 층 아래로 내려갑니다.
- 같은 과정을 반복해 바닥층에 도착합니다.
- 바닥층에서 여러 후보를 비교해 가까운 이웃
k개를 반환합니다.
여기서 k는 사용자가 받고 싶은 검색 결과 수입니다. k=5라면 가장 가깝다고 판단한 벡터 5개를 돌려줍니다.
‘항상 가장 가까운 이웃 하나로만 이동한다’고 생각하면 개념은 잡히지만 실제 검색은 조금 더 넓습니다. 바닥층에서는 후보 목록과 이미 방문한 노드를 관리하면서 여러 경로를 탐색합니다. 이 후보 폭을 조정하는 대표적인 값이 ef입니다.
인덱스는 어떻게 만들어지나
새 벡터를 넣을 때도 검색과 비슷한 길을 걷습니다.
- 기존 그래프의 상위층에서 새 벡터와 가까운 지역을 찾습니다.
- 층을 내려가면서 이웃 후보를 모읍니다.
- 후보 중 연결할 이웃을 선택합니다.
- 새 노드와 선택된 기존 노드를 엣지로 연결합니다.
단순히 가장 가까운 노드만 고르는 것은 아닙니다. 가까우면서도 탐색 경로가 한곳에만 몰리지 않도록 이웃을 고르는 휴리스틱을 사용합니다. 휴리스틱(heuristic)은 항상 최적임을 수학적으로 보장하지는 않지만 실제로 좋은 결과를 빠르게 찾기 위한 규칙입니다.
이 때문에 HNSW 인덱스는 원본 벡터만 저장하는 것보다 메모리를 더 사용하고, 처음 구축하는 데도 시간이 걸립니다. 저장한 벡터 외에 층 정보와 이웃 연결도 보관해야 하기 때문입니다.
M, ef_construct, ef
HNSW를 사용할 때 자주 만나는 설정은 M, ef_construct, ef입니다. 제품에 따라 이름과 세부 동작은 조금씩 다르지만 역할은 비슷합니다.
M, 노드의 연결 수
M은 노드가 유지할 수 있는 이웃 연결 수를 정하는 대표 설정입니다. 구현에 따라 바닥층의 연결 수를 다르게 처리할 수 있으므로 모든 층에서 정확히 같은 수가 된다는 뜻은 아닙니다.
M을 키우면 탐색할 수 있는 경로가 많아져 가까운 벡터를 찾을 가능성이 높아집니다. 대신 그래프가 커지므로 메모리 사용량과 인덱스 구축 비용도 증가합니다.
ef_construct, 인덱스를 만들 때의 후보 폭
ef_construct는 새 노드를 그래프에 넣을 때 이웃 후보를 얼마나 넓게 살필지 정합니다.
값이 크면 좋은 연결을 찾을 가능성이 높아져 그래프 품질이 좋아질 수 있습니다. 대신 인덱스를 만드는 시간이 길어집니다. 이 값은 주로 구축 시점의 품질과 비용을 조정합니다.
ef, 검색할 때의 후보 폭
ef는 질의할 때 후보 목록을 얼마나 넓게 유지하며 탐색할지 정합니다. Qdrant에서는 검색 요청의 hnsw_ef, hnswlib에서는 ef 같은 이름으로 노출됩니다.
값이 크면 더 많은 후보를 확인하므로 진짜 가까운 이웃을 찾을 가능성이 높아집니다. 대신 검색 시간이 증가합니다. 일반적으로 요청한 결과 수 k보다 작지 않게 설정해야 합니다.
| 조정 | 기대 효과 | 함께 늘어나는 비용 |
|---|---|---|
M 증가 | 탐색 경로와 recall 개선 가능 | 메모리, 구축시간 |
ef_construct 증가 | 인덱스 품질 개선 가능 | 구축시간 |
ef 증가 | 검색 recall 개선 가능 | 질의 latency |
여기서 recall(재현율)은 전수 검색이 찾아낸 진짜 가까운 이웃을 HNSW도 얼마나 되찾았는지 나타냅니다. latency(지연시간)는 검색 요청 한 건에 걸리는 시간입니다.
설정값을 크게 만든다고 항상 좋은 것은 아닙니다. 실제 데이터와 질문으로 recall, p95 latency, 메모리, 인덱스 구축시간을 함께 측정해야 합니다. p95 latency는 검색 요청 100건 중 느린 쪽 다섯 번째 요청에 해당하는 응답시간으로, 평균만 봤을 때 가려지는 느린 요청을 확인하는 지표입니다.
HNSW가 검색 결과를 만드는 전부는 아니다
RAG(Retrieval-Augmented Generation, 검색 증강 생성)는 관련 문서를 먼저 찾고 그 문서를 근거로 LLM이 답하도록 만드는 방식입니다. 여기서 LLM(Large Language Model, 대규모 언어 모델)은 문장을 이해하고 생성하는 AI 모델입니다.
RAG 안에서 HNSW의 자리는 검색 후보를 빠르게 찾는 단계입니다.
질문
→ 임베딩 모델이 질문을 벡터로 변환
→ HNSW가 가까운 문서 벡터 후보를 검색
→ 필터와 reranker가 후보를 정리
→ LLM이 근거 문서를 읽고 답변 생성필터(filter)는 사용자 권한, 문서 종류, 작성일 같은 조건에 맞지 않는 결과를 제외합니다. reranker(재정렬 모델)는 처음 검색된 후보와 질문의 관련성을 더 정밀하게 평가해 순서를 다시 정합니다.
따라서 HNSW가 빠르다고 답변이 자동으로 정확해지는 것은 아닙니다. 임베딩 모델, 문서 분할 방식, 거리 함수, 권한 필터, 재정렬, 최종 답변 생성까지 모두 검색 품질에 영향을 줍니다.
필터가 강하면 그래프가 끊긴 것처럼 보일 수 있다
HNSW는 연결된 노드를 따라 이동합니다. 그런데 “인사팀 문서만”, “2026년에 작성된 문서만”, “이 사용자가 읽을 수 있는 문서만” 같은 필터를 적용하면 이동 경로에 있던 노드가 검색 대상에서 제외될 수 있습니다.
필터가 매우 엄격하면 가까운 결과로 가는 중간 경로가 막혀 그래프 탐색 품질이 떨어질 수 있습니다. Qdrant가 payload 필터를 고려한 추가 엣지를 만들거나, 조건에 따라 HNSW 대신 전수 검색을 선택하는 이유가 여기에 있습니다.
따라서 통합 컬렉션에 여러 조직의 문서를 넣고 권한 필터로 구분할 때는 다음을 함께 검증해야 합니다.
- 필터를 적용한 검색에서도 recall이 유지되는가
- 권한 없는 문서가 후보나 답변에 섞이지 않는가
- 필터 선택도에 따라 latency가 급격히 늘지 않는가
- 작은 검색 범위라면 전수 검색이 오히려 빠르지 않은가
필터와 HNSW는 별개의 부가기능이 아니라 함께 설계하고 측정해야 하는 검색 경로입니다.
HNSW가 잘 맞는 경우와 그렇지 않은 경우
| 상황 | 판단 | 이유 |
|---|---|---|
| 벡터가 많고 검색 요청이 자주 들어옴 | HNSW가 잘 맞음 | 매번 전수 비교하는 비용을 줄일 수 있음 |
| 높은 recall과 짧은 응답시간의 균형이 필요함 | HNSW가 잘 맞음 | M, ef 등으로 균형을 조정할 수 있음 |
| 데이터가 아주 적음 | 전수 검색도 검토 | 인덱스 구축과 관리 비용이 더 클 수 있음 |
| 반드시 정확한 최근접 결과가 필요함 | 전수 검색 또는 사후 검증 | HNSW는 근사 알고리즘임 |
| 메모리가 매우 제한적임 | 다른 인덱스와 비교 | 그래프 연결 정보가 추가 메모리를 사용함 |
| 강한 권한 필터 조합이 많음 | 제품별 필터 전략 검증 | 필터가 그래프 탐색 경로를 약화할 수 있음 |
처음 질문으로 돌아가면
HNSW는 “에이치 엔 에스 더블유”라고 읽습니다. 검색하려는 문서나 상품을 벡터로 바꾸고 가까운 벡터끼리 그래프로 연결한 다음, 성긴 상위층에서 크게 이동하고 촘촘한 아래층에서 정밀하게 찾습니다.
빠른 이유는 모든 벡터를 비교하지 않기 때문이고, 한계도 같은 이유에서 생깁니다. 유망하다고 판단한 경로만 보기 때문에 진짜 가까운 결과를 놓칠 수 있습니다. 그래서 HNSW를 운영할 때는 단순히 “검색이 된다”가 아니라 recall, latency, 메모리, 필터 적용 후의 품질을 함께 측정해야 합니다.
HNSW를 고속도로와 골목길에 비유하는 것은 이해를 위한 개념도입니다. 실제 그래프 연결과 탐색 결과는 데이터 분포, 입력 순서, 거리 함수, 구현체와 설정에 따라 달라집니다.