벡터 검색과 근사 최근접 이웃: 평탄 · IVF · PQ · HNSW

벡터 검색과 근사 최근접 이웃: 평탄 · IVF · PQ · HNSW

문서를 임베딩 벡터로 바꿔 두면 "질문과 가장 가까운 벡터 찾기"가 곧 검색입니다. 문서가 1,000개면 전부 비교해도 되지만, 1,000만 개면 질문 하나마다 1,000만 번 거리를 재야 합니다. 근사 최근접 이웃(ANN, approximate nearest neighbor) 검색은 정확도를 조금 내주고 속도와 메모리를 크게 얻는 방법입니다. 이 수업에서는 벡터 DB 안에서 실제로 쓰이는 네 가지 방식 — 평탄(전수) 검색, IVF(군집으로 나누기), PQ(벡터 압축), HNSW(그래프 타고 가기) — 를 작은 숫자로 직접 계산합니다.

들어가기 전에

• 검색의 기초: TF-IDF · BM25 · 벡터 검색 · 검색 평가 지표 — 벡터 검색과 recall@k.
• 임베딩과 벡터 유사도 — 코사인 · 내적 · 유클리드 거리.
• 오픈 도메인 질의응답을 위한 밀집 문단 검색 (DPR) — 문단 수백만 개를 벡터로 만들어 찾는 예. DPR도 Faiss를 썼습니다.

한눈에 보기

• 정확한 최근접 이웃 검색이 왜 규모가 커지면 비싼지 숫자로 압니다.
• IVF가 "가까운 군집 몇 개만 뒤지는" 원리와 nprobe의 의미를 압니다.
• PQ가 768차원 실수 벡터를 수십 바이트로 줄이는 방법과 그 대가(거리 해상도 손실)를 계산합니다.
• HNSW가 여러 층 그래프를 위에서 아래로 내려가며 찾는 방식과 M · ef 파라미터의 역할을 압니다.
• 데이터 규모 · 메모리 · 정확도 요구에 따라 어떤 인덱스를 고를지 판단합니다.

1. 문제: k-최근접 이웃과 '근사'의 뜻

정의. 질의 벡터 $x$ 와 문서 벡터 $y_1,\dots,y_N$ 이 있을 때, 거리가 가장 작은 $k$ 개를 찾는 것이 k-최근접 이웃(k-NN) 검색입니다. Faiss 논문(1702.08734)은 이를 다음처럼 씁니다.

근사의 품질은 어떻게 재나. ANN이 돌려준 $k$ 개 가운데 정확한 검색의 결과와 겹치는 비율을 재현율(recall)로 잽니다. 예를 들어 정확한 상위 10개 중 9개를 찾았다면 10-recall@10 = 0.9입니다. ANN 인덱스는 거의 모두 "속도 ↔ 재현율 ↔ 메모리" 셋 사이에서 조절하는 손잡이(파라미터)를 가집니다.

왜 근사가 필요한가(해설용 계산). 768차원 float32 벡터 1,000만 개는 $10^7\times768\times4$ 바이트 $\approx30.7$GB입니다. 질의마다 이걸 전부 읽어 거리를 재면 메모리도 시간도 큽니다.

2. 평탄(Flat) 검색: 전부 비교하기

방식. 모든 벡터와 거리를 잽니다. Faiss의 IndexFlat 이 이 전수(brute force) 검색입니다. 결과가 정확하므로 다른 인덱스를 평가할 때 정답 기준 으로 씁니다.

숫자로 해 보기(해설용). 2차원 문서 6개와 질의 $q=(7,7)$.

가장 가까운 것은 문서 4, 그다음은 5 · 6(동점)입니다. 거리 계산 6번이 필요했습니다. $N$ 이 커지면 계산이 $N$ 에 비례해 늘어납니다.

언제 쓰나. 문서가 수만~수십만 개 정도이고 정확도가 가장 중요하면 평탄 검색으로도 충분한 경우가 많습니다. 인덱스 구축 · 튜닝이 필요 없다는 장점도 큽니다.

3. IVF: 군집으로 나눠 가까운 칸만 뒤지기

직관(해설용 비유). 도서관 책을 주제별 서가로 나눠 둡니다. 질문이 들어오면 가장 관련 있는 서가 몇 개만 가서 찾습니다. 서가 = 군집, 서가 목록 = 역파일(inverted file)입니다.

단계.

1. 학습: 문서 벡터를 k-평균으로 $K_{IVF}$ 개 군집으로 나눕니다. 각 군집의 중심이 센트로이드(centroid)입니다(Faiss에서는 nlist).
2. 색인: 각 문서를 가장 가까운 센트로이드의 목록(역목록)에 넣습니다.
3. 검색: 질의와 가장 가까운 센트로이드 $P_{IVF}$ 개(nprobe)를 고르고, 그 목록 안의 문서들만 거리를 잽니다.

계산량. Faiss 라이브러리 논문(2401.08281)은 목록 크기가 고르다고 할 때 거리 계산 횟수를 다음처럼 씁니다.

앞 항은 센트로이드와의 비교, 뒤 항은 고른 목록 안의 비교입니다. 이 값은 $K_{IVF}=\sqrt{P_{IVF}N}$ 에서 가장 작아지고, 그래서 "$K_{IVF}$ 를 $\sqrt N$ 에 비례해 잡으라"는 흔한 권장이 나온다고 논문은 설명합니다(실제로는 대략적인 기준이라고 덧붙입니다).

숫자로 해 보기(해설용). 위 6개 문서를 두 군집으로 나누면 센트로이드는 $(1.33,1.33)$ 과 $(8.33,8.33)$ 입니다. 질의 $(7,7)$ 과의 거리²는 64.2와 3.6이므로 nprobe=1이면 두 번째 군집만 뒤집니다. 센트로이드 2번 + 문서 3번 = 거리 계산 5번으로 같은 답을 얻습니다. 규모를 키우면 효과가 커집니다. $N=10^6$, $K=1000$, nprobe=1이면 $1000+1000=2000$ 번, nprobe=8이면 $1000+8000=9000$ 번으로, 전수 $10^6$ 번에 비해 훨씬 적습니다.

대가. 정답이 군집 경계 너머에 있으면 놓칩니다. nprobe를 늘리면 재현율이 오르고 속도는 느려집니다. 이것이 IVF의 손잡이입니다.

4. PQ: 벡터를 짧은 코드로 압축하기

직관. 긴 벡터를 몇 토막으로 자르고, 토막마다 "대표 모양 256개 중 몇 번과 가장 비슷한가"라는 번호 하나(1바이트)만 저장합니다. 768차원 float32(3,072바이트)를 토막 96개로 자르면 벡터 하나가 96바이트가 됩니다 — 32분의 1입니다.

단계(Jégou 외의 곱 양자화, product quantization).

1. 벡터를 $M$ 개의 부분 벡터로 자릅니다.
2. 부분 벡터 위치마다 따로 k-평균을 돌려 코드북(보통 $2^8=256$ 개 중심)을 만듭니다.
3. 각 문서는 부분마다 가장 가까운 중심의 번호만 저장합니다($M$ 바이트).
4. 검색 때는 질의의 부분 벡터와 각 코드북 중심 사이 거리를 미리 표(조회표, lookup table)로 계산해 두고, 문서마다 번호로 표를 찾아 더하기만 합니다. 질의는 압축하지 않고 문서만 압축된 상태로 재므로 비대칭 거리(asymmetric distance)라 부릅니다.

숫자로 해 보기(해설용, 4차원 · 토막 2개 · 코드북 크기 2). 문서 $(1,0,5,5)$, $(1,1,4,5)$, $(0,1,5,4)$, $(9,9,0,1)$ 을 앞 2칸 · 뒤 2칸으로 자릅니다. k-평균 결과 코드북이 앞쪽 $\{(0.67,0.67),\ (9,9)\}$, 뒤쪽 $\{(4.67,4.67),\ (0,1)\}$ 이라 하면 코드는 앞 세 문서가 (0,0), 마지막이 (1,1)입니다.

질의 $q=(1,1,5,5)$ 의 조회표는 앞쪽 $(0.222,\ 128)$, 뒤쪽 $(0.222,\ 41)$ 입니다.

먼 문서 4는 확실히 걸러지지만, 가까운 세 문서는 구분이 안 됩니다(모두 0.444). 압축으로 거리의 세밀함을 잃은 것입니다. 실제로는 코드북을 256개로 크게 두어 이 손실을 줄이고, 후보를 추린 뒤 원래 벡터로 다시 정렬(re-ranking)하기도 합니다.

IVF와 묶기. Faiss 논문(1702.08734)은 IVF로 후보 군집을 고르고 PQ 코드로 거리를 재는 IVFADC 구조를 GPU에서 구현했습니다. 이 논문은 k-선택 설계로 이전 GPU 최고 기록보다 8.5배 빠른 최근접 이웃 구현을 보고했고, 10억 개 벡터를 잇는 k-NN 그래프를 12시간 안에 만들었다고 밝힙니다.

양자화 수업과의 관계. 수치 형식 · 혼합 정밀도 · 양자화 에서 다루는 모델 가중치 양자화는 숫자 하나하나의 비트 수를 줄이는 것이고, PQ는 벡터 토막을 대표 번호로 바꾸는 것이라는 점이 다릅니다.

5. HNSW: 여러 층 그래프를 타고 내려가기

직관(해설용 비유). 낯선 도시에서 주소를 찾을 때, 먼저 고속도로로 근처 도시까지 가고, 국도로 동네까지, 골목길로 집 앞까지 갑니다. HNSW(Hierarchical Navigable Small World)는 벡터들을 이런 여러 층의 도로망(그래프) 으로 잇습니다. 위층에는 점이 적고 긴 연결이, 아래층에는 모든 점과 짧은 연결이 있습니다.

단계(Malkov · Yashunin 2016).

1. 층 정하기: 새 벡터를 넣을 때 최대 층 $l$ 을 무작위로 뽑습니다. $l=\lfloor -\ln(\mathrm{unif}(0,1))\cdot m_L\rfloor$ — 높은 층일수록 지수적으로 드뭅니다.
2. 연결: 각 층에서 가까운 이웃 최대 $M$ 개와 잇습니다(맨 아래층은 $M_{max0}$ 개까지).
3. 검색: 맨 위층 진입점에서 출발해, 질의에 더 가까운 이웃으로 계속 옮겨 가는 탐욕적 이동을 합니다. 더 가까워지지 않으면 한 층 내려가 반복합니다.
4. 맨 아래층: 후보 목록 크기 ef 만큼 넓게 탐색해 최종 $k$ 개를 고릅니다.

파라미터(논문 권장).

숫자로 해 보기(해설용). $M=16$ 이면 $m_L=1/\ln16\approx0.361$ 입니다. 이때 벡터가 1층 이상에 올라갈 확률은 $e^{-1/m_L}=1/16=0.0625$, 2층 이상은 $1/256\approx0.0039$ 입니다. 100만 개를 넣으면 1층에 약 6만 개, 2층에 약 4천 개 … 로 층마다 16분의 1씩 줄어 맨 위에는 몇 개만 남습니다. 그래서 위층 몇 번의 이동으로 목표 근처에 빠르게 닿습니다. 논문은 이 구조가 검색 복잡도의 로그 규모 증가를 가능하게 한다고 설명합니다.

장단점. 메모리에 원래 벡터와 그래프 연결을 모두 두므로 메모리를 많이 쓰지만, 높은 재현율에서 속도가 아주 좋습니다. 여러 벡터 DB가 HNSW 인덱스를 제공합니다.

12345678910flowchart TB
  Q[질의 벡터] --> C{데이터 규모 · 메모리}
  C -->|작다 · 정확도 최우선| F[평탄 검색<br/>전수 비교]
  C -->|크다 · 메모리 여유| H[HNSW<br/>위층에서 아래층으로 탐욕 이동]
  C -->|아주 크다 · 메모리 부족| I[IVF로 군집 nprobe개 선택]
  I --> P[PQ 코드로 조회표 거리 계산]
  P --> R[상위 후보를 원래 벡터로 다시 정렬]
  H --> K[상위 k개]
  F --> K
  R --> K

6. 무엇을 고르나 · 벡터 DB가 더하는 것

벡터 DB 제품들은 대개 위 인덱스에 더해 메타데이터 필터(날짜 · 부서 · 권한), 문서 추가 · 삭제, 복제 · 분산, 키워드 검색과의 결합 같은 운영 기능을 제공합니다. 핵심 검색 알고리즘 자체는 이 수업의 네 가지 계열에서 크게 벗어나지 않습니다. 어떤 제품을 쓰든 "인덱스 종류 · 거리 함수 · 재현율 손잡이(nprobe, ef)"를 확인하는 습관이 중요합니다.

주의할 점. 인덱스를 바꿔도 임베딩 모델이 거리를 의미에 맞게 배치했을 때만 좋은 검색이 됩니다. Faiss 라이브러리 논문은 이를 임베딩 추출기와 벡터 인덱스 사이의 '계약'이라고 부릅니다. 추출기는 거리가 과제에 맞도록 학습되고, 인덱스는 그 거리로 정확한 검색을 최대한 흉내 냅니다. 검색 품질 문제가 생기면 인덱스보다 임베딩 · 청킹부터 의심하는 편이 낫습니다.

연습 문제

1. $N=10^8$, nprobe=1일 때 IVF의 거리 계산을 가장 적게 하는 $K_{IVF}$ 와 그때의 계산 횟수는?
   • 풀이: $K=\sqrt{10^8}=10^4$, 계산 $10^4+10^8/10^4=2\times10^4$ 번입니다.
2. 1,024차원 float32 벡터를 토막 64개 · 코드북 256개 PQ로 압축하면 벡터당 몇 바이트이고 몇 배 줄었나요?
   • 풀이: 토막마다 1바이트라 64바이트, 원래 $1024\times4=4096$ 바이트이므로 64배 줄었습니다.
3. HNSW에서 $M=32$ 이고 $m_L=1/\ln M$ 이면 1층 이상에 오를 확률은?
   • 풀이: $e^{-\ln 32}=1/32\approx0.031$ 입니다.
4. 4절 표에서 PQ가 문서 1 · 2 · 3을 구분하지 못한 이유와 해결책은?
   • 풀이: 세 문서가 두 토막 모두 같은 중심에 배정돼 코드가 같았기 때문입니다. 코드북을 크게 하거나 토막 수를 늘리고, PQ로 추린 후보를 원래 벡터로 다시 정렬하면 됩니다.

스스로 점검

1. ANN의 '근사' 품질을 무엇으로 재나요?
   • 답: 정확한 전수 검색 결과와 비교한 재현율(예: 10-recall@10)로 잽니다.
2. IVF에서 nprobe를 늘리면 무엇이 좋아지고 무엇이 나빠지나요?
   • 답: 더 많은 군집을 뒤져 재현율이 오르고, 거리 계산이 늘어 속도가 느려집니다.
3. HNSW가 위층부터 탐색하는 이유는?
   • 답: 위층에는 점이 적고 연결이 길어, 몇 번의 이동만으로 목표 근처에 닿을 수 있기 때문입니다. 그다음 촘촘한 아래층에서 정밀하게 찾습니다.

용어 정리

더 깊이 보려면

• ColBERT: BERT 기반 지연 상호작용 검색 — 토큰마다 벡터를 두는 검색에서 인덱스 크기가 왜 문제인지
• ColBERTv2: 가볍고 효과적인 지연 상호작용 검색 — 잔차 압축으로 인덱스를 줄인 사례
• 수조 토큰에서 검색해 언어 모델 키우기 (RETRO) — 아주 큰 검색 DB를 언어 모델에 붙인 예
• Faiss 위키 「Guidelines to choose an index」: github.com/facebookresearch/faiss/wiki

다음에 볼 것

• ColBERT: BERT 기반 지연 상호작용 검색 — 문서 벡터 하나 대신 토큰 벡터 여러 개로 찾는 방식
• RAG 파이프라인 설계: 청킹 · 하이브리드 검색 · 리랭킹 · 쿼리 재작성 — 인덱스 앞뒤에 붙는 RAG 부품 전체

라이선스

본문은 KAITABASE 자체 해설입니다. 참고 자료 Faiss는 MIT 라이선스로 공개되어 있습니다. 숫자 예는 이 수업을 위해 만든 해설용 예이며 파이썬으로 검산했습니다. 논문 수치는 각 원문에서 확인한 것만 옮겼습니다.

출처

• Malkov · Yashunin, Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs (2016): arxiv.org/abs/1603.09320
• Johnson · Douze · Jégou, Billion-scale similarity search with GPUs (2017): arxiv.org/abs/1702.08734
• Douze 외, The Faiss Library (2024): arxiv.org/abs/2401.08281
• Jégou · Douze · Schmid, Product Quantization for Nearest Neighbor Search, IEEE Transactions on Pattern Analysis and Machine Intelligence (Faiss 논문 참고문헌 [44])
• Faiss 위키: github.com/facebookresearch/faiss/wiki