벡터 검색Vector Search
질의 벡터와 거리가 가장 가까운 저장 벡터 k개를 찾는 검색이다. 모든 벡터와 거리를 재는 대신 그래프 · 군집 · 압축 색인으로 일부만 재어, 정확도를 조금 내주고 속도와 메모리를 얻는다.
1요약
- 벡터 검색은 임베딩 모델과 응용 사이에서 최근접 이웃 색인을 맡는 계층으로, 곱 양자화(2011) · HNSW(2016) 같은 방법을 Faiss 같은 오픈소스가 구현하고, 그 위에서 RAG 의 검색기 · 추천 · 중복 탐지가 돈다.
- 384차원 벡터 10만 개를 전수 검색하면 질의마다 거리 계산 10만 번(곱셈 · 덧셈 3,840만 번)이 들어 14.7 ms 가 걸렸고, 같은 데이터에서 HNSW 는 거리 계산 1,844번으로 정답 10개 중 평균 9.73개를 찾았다(본문 사례).
- 「검색 결과가 이상하다」는 전수 검색 결과와 겹치는 비율(recall@k)로 가른다 — 전수 검색도 엉뚱하면 임베딩 · 거리 척도 문제, 전수는 맞고 색인만 놓치면 색인 인자(efSearch · nprobe) 문제다.
2등장 배경
질의 하나에 저장 벡터 N개와 모두 거리를 재면 비용이 N × 차원에 비례한다. 1998년 Weber 등은 k-d 트리 · R-트리 같은 공간 분할 색인이 차원이 약 10을 넘으면 평균적으로 순차 탐색보다 느려짐을 보였다(Weber 1998 요약 · 3절).
2011년 Jégou · Douze · Schmid 는 벡터를 조각마다 짧은 번호로 바꾸는 곱 양자화(PQ)와, 가까운 군집 목록만 여는 역파일(IVF)을 묶어 메모리와 계산을 함께 줄였다(Jégou 2011). 2016년 Malkov · Yashunin 은 계층 그래프 HNSW 를 내놓아 탐색 비용이 O(log N) 으로 늘게 했고(Malkov 2018 4.2.1절), 2017년 Johnson 등은 Faiss 의 GPU 구현으로 10억 개 벡터의 k-NN 그래프를 GPU 4개에서 12시간 안에 만들었다(Johnson 2017 초록).
임베딩으로 문서 · 이미지를 찾는 응용이 늘면서 이 색인은 벡터 데이터베이스의 핵심 기능이 됐다. 벡터 데이터베이스는 여기에 식별자 기반 추가 · 삭제와 조건 필터를 더한다(Douze 2024 6절).
3쉽게 이해하기 — 지도 세 장으로 가까운 집을 찾는 택배 기사
택배 기사가 10만 가구가 사는 도시에서 새 손님 집과 가장 가까운 집 10곳을 찾아 전단지를 돌려야 한다. 집집마다 걸어가 거리를 재면 하루가 다 간다. 그래서 기사는 고속도로 · 큰길 · 골목 지도 세 장을 겹쳐 두고, 고속도로 출구에서 시작해 손님 집 쪽으로 가까워지는 길만 골라 큰길 · 골목으로 내려온다. 골목에서는 수첩에 「지금까지 가장 가까운 집 64곳」 명단을 적어 들고, 명단이 더 나아지지 않을 때까지 이웃 집을 둘러본다.
그림 1 · 기사는 고속도로 출구에서 손님 쪽으로 가며 지도를 한 장씩 내려오고, 골목에서만 수첩 명단을 들고 둘러봐 집집마다 가 보지 않고 가까운 10집을 찾는다.
그림 2 · 수첩 명단이 짧으면 기사는 옆 동네에서 멈추고, 명단을 늘리면 더 걷는 대신 손님 동네에 닿는다 — 실제로 efSearch 16 은 질의 #0 의 정답을 하나도 못 찾았고 64 는 10개를 모두 찾았다.
| 비유 속 역할 | 실제 이름 | 실제로 하는 일 |
|---|---|---|
| 도시의 집 10만 채 | 저장 벡터 | 384차원 벡터 100,000개를 색인에 넣는다 |
| 손님 집 | 질의 벡터 | 같은 공간의 벡터 하나로 가까운 이웃을 묻는다 |
| 집 사이 거리 | 거리 척도 | L2 거리 · 내적 · 코사인 중 하나로 가깝다를 정한다 |
| 겹친 지도 세 장 | 계층 그래프 | 위 계층일수록 노드가 적고 먼 이웃을 잇는다 |
| 고속도로 출구 | 진입점 | 맨 위 계층의 한 노드에서 탐색을 시작한다 |
| 수첩 명단 64곳 | 후보 목록 efSearch | 0계층에서 가까운 후보를 이만큼 들고 넓힌다 |
| 가까운 10집 | top-k 결과 · recall@k | 결과를 전수 검색 정답과 비교해 품질을 잰다 |
| 지도를 새로 그림 | 색인 재구축 | M · efConstruction 을 바꾸면 그래프를 다시 만든다 |
⚠ 비유가 맞지 않는 곳: 실제 공간은 2차원 지도가 아니라 384차원이라 「가까운 동네」가 눈에 보이지 않고, 계층 그래프의 위 계층은 도로처럼 따로 놓인 것이 아니라 0계층 노드 중 약 1/16 을 골라 다시 엮은 것이다(Malkov 2018 4.1절).
4구조 — 거리 척도와 세 가지 색인
색인은 거리 계산의 «횟수»를 줄이고, 거리 척도는 «무엇이 가까운가»를 정한다. 정규화된 벡터에서는 L2 거리 제곱 = 2 − 2 × 코사인 이라 두 척도의 순서가 같다 — 사례 질의 #0 의 1위 #61542 는 L2 제곱 1.2467, 코사인 0.3767 이다.
그림 3 · HNSW 는 계층마다 노드의 약 1/16 만 위 계층에 올리므로 10만 개가 다섯 계층에 쌓이고, 벡터 하나에 붙는 연결은 벡터 크기의 약 1/10 이다.
그림 4 · IVF-PQ 는 1,024개 목록 중 가까운 8개만 열고, 목록 안 벡터는 1,536바이트 대신 48바이트 부호로 거리를 어림한다.
| 요소 | 크기 · 단위 | 역할 | 값 · 근거 |
|---|---|---|---|
| 저장 벡터 | 384차원 float32 | 검색 대상 | 4 × d = 1,536바이트(Faiss 문서 IndexFlat) |
| 거리 척도 | 벡터당 곱셈 · 덧셈 384번 | 가깝다를 정함 | L2 · 내적 · 코사인은 전처리로 서로 바뀜(Douze 2024 3절) |
| HNSW 계층 | 계층 l = ⌊−ln(U) × mL⌋ | 위에서 아래로 좁힘 | mL = 1/ln(M) · 0계층 이웃 상한 2M(Malkov 2018 4 · 4.1절) |
| 후보 목록 ef | efConstruction · efSearch | 탐색 폭 | 클수록 recall 과 거리 계산이 함께 늘어남(Malkov 2018 알고리즘 2) |
| IVF 목록 | nlist 개 · nprobe 개 방문 | 열 목록만 고름 | 거리 계산 ≈ nlist + nprobe × N ÷ nlist(Douze 2024 5.1절 식 18) |
| PQ 부호 | m 조각 × nbits | 벡터 압축 | m × nbits ÷ 8 + 8바이트(Faiss 문서 IndexIVFPQ) · 질의는 압축 않는 비대칭 거리(Douze 2024 4절) |
| 재순위 | 후보 k′ 개 | 원 벡터로 다시 잼 | 빠른 색인의 후보만 정확히 다시 계산(Douze 2024 3.5절) |
| recall@k | 0 ~ 1 | 근사 품질 | 전수 검색 정답 k개 중 결과에 든 비율(Aumüller 2020 2절) |
🔑 근사 색인이 줄이는 것은 거리 계산의 횟수이지 정답의 기준이 아니다 — recall 은 언제나 같은 척도의 전수 검색 결과와 비교해 잰다.
5동작 — 질의 하나의 HNSW 탐색
사례 = 직접 실행 — faiss-cpu 1.15.1 · numpy 2.5.4 · 1 스레드 · 합성 데이터(군집 중심 2,000개 + 표준편차 1.8 잡음 · 정규화 · default_rng(0)) · 시간은 이 실행 환경의 값이다.
- 정답 만들기 — 384차원 벡터 100,000개에 IndexFlatL2 로 질의 #0 을 전수 검색하면 거리 계산 100,000번 · 14.7 ms 이고, 1위는 #61542(L2 제곱 1.247), 10번째 이웃 거리는 1.424 다.
- 색인 구축 — IndexHNSWFlat(M 16 · efConstruction 100)에 100,000개를 넣는 데 72.6초가 걸리고, 노드가 0 ~ 4계층에 100,000 · 6,374 · 371 · 20 · 1개로 쌓인다.
- 상위 계층 하강 — 4계층의 유일한 노드 #20288(거리 2.186)에서 시작해 3계층 이웃 30개를 재고 #31374(1.730)로 한 번 옮긴 뒤, 2 · 1계층에서는 이웃 28개 중 더 가까운 것이 없어 그대로 내려간다(Malkov 2018 알고리즘 5).
- 0계층 · efSearch 16 — 후보 목록 16개로 넓히다 거리 계산 524번에서 멈추고, 10번째 거리 1.743 이 정답 1.424 보다 커서 정답 10개 중 0개를 찾는다.
- 0계층 · efSearch 64 — 같은 질의를 후보 64개로 다시 찾으면 거리 계산 2,526번(전수의 2.5%) 끝에 정답 10개를 모두 찾는다.
- 질의 1,000개 평균 — efSearch 64 는 recall@10 0.973 · 거리 계산 1,844번 · 0.54 ms 로, 전수 검색 14.7 ms 의 약 1/27 시간이 걸린다.
그림 5 · 질의 #0 은 위 계층에서 한 번만 옮겨 0계층에 닿고, 같은 진입 뒤에도 efSearch 16 은 정답 0개 · 64 는 10개를 찾는다.
그림 6 · 같은 recall@10 0.95 에 HNSW 는 거리 계산 약 1,650번, IVF 는 약 24,300번이 들어 — 질의 인자를 올릴수록 recall 은 1 에 다가가고 비용은 전수 검색 100,000번 쪽으로 늘어난다.
🔑 efSearch · nprobe 는 색인을 다시 만들지 않고 질의마다 바꾸는 재현율 ↔ 속도 조정 인자이고, M · efConstruction · nlist 는 바꾸려면 색인을 다시 만드는 구축 인자다.
6비교 — 전수 · IVF · HNSW · IVF-PQ
같은 데이터(384차원 100,000개 · 질의 1,000개 · 1 스레드)에서 잰 값이다.
| 기준 | 전수(Flat) | IVF-Flat(nlist 1,024 · nprobe 8) | HNSW(M 16 · efSearch 64) | IVF-PQ(48바이트 · nprobe 8) |
|---|---|---|---|---|
| recall@10 | 1.000 | 0.815 | 0.973 | 0.517 · 재순위 100개 뒤 0.814 |
| 질의당 거리 계산 | 100,000번 | 4,221번(중심 1,024 포함) | 1,844번 | 4,221번(표 조회) |
| 질의당 시간 | 14.7 ms | 0.64 ms | 0.54 ms | 0.35 ms · 재순위 0.37 ms |
| 색인 크기 | 153.6 MB | 156.0 MB | 168.0 MB | 7.6 MB |
| 구축 시간 | 없음 | 3.8초(군집 학습) | 72.6초 | 53.7초(군집 · 부호책 학습) |
분석원 벡터가 메모리에 들어가는 1,000만 개 이하 규모는 HNSW, 메모리가 모자라면 IVF-PQ 에 원 벡터 재순위, 10만 개 안팎이거나 정확한 답이 필수면 전수 검색이 맞다. 근거는 Douze 2024 5.3절(그래프 색인은 메모리 제약이 없을 때 · 1,000만 개를 넘으면 구축 시간이 한계 · 압축이 필요하면 IVF)과 표의 색인 크기 · 구축 시간 행이다.
7실무 진단 — 검색 품질 · 비용 원인 가르기
분석같은 질의의 전수 검색 결과부터 만든다. 전수 검색도 엉뚱하면 색인 인자로는 고칠 수 없는 척도 · 임베딩 문제이고, 전수 결과가 있어야 recall@k 로 인자 변경의 효과를 잴 수 있다(Douze 2024 3.2절).
| # | 증상 | 의심 원인 | 단계 | 확인 명령 | 판정 기준(근거) |
|---|---|---|---|---|---|
| 1 | 전수 검색 결과도 엉뚱함 | 척도 불일치(코사인 학습 모델을 정규화 없이 내적) | 척도 | np. · index.metric_type | 노름이 1이 아니면 내적 ≠ 코사인(Faiss 문서 IndexFlatIP) |
| 2 | 전수는 맞고 색인 결과만 다름 | efSearch · nprobe 부족 | 탐색 | 질의 100개로 IndexFlat 대비 recall@10 | 목표 미만이면 efSearch · nprobe 를 올리며 다시 잼 · 구축은 그대로(Douze 2024 3.4절) |
| 3 | 평균은 높은데 0 / 10 질의가 있음 | 그래프가 군집 경계에서 막힘 | 구축 | 질의별 recall 분포 · faiss. | 경계에서 막힘 = 이웃 선택 휴리스틱 · M · efConstruction 확인(Malkov 2018 4.1절) |
| 4 | IVF 질의 시간이 질의마다 들쭉날쭉 | 목록 크기 불균형 | 구축 | index. 분포 | 식 18 은 같은 크기 목록을 가정(Douze 2024 5.1절) |
| 5 | 압축 뒤 recall 급락 | PQ 부호 오차 | 압축 | IndexRefineFlat 재순위 전후 recall | 재순위로 회복되면 압축 탓(Douze 2024 3.5절) |
| 6 | 메모리 초과 | 원 벡터 + 그래프 연결 | 저장 | len(faiss. | 연결 = (Mmax0 + mL × Mmax) × 4바이트(Malkov 2018 4.2.3절) |
전수 결과와 비교할 질의 묶음을 고정해 두면 efSearch · nprobe 를 바꿀 때마다 그림 6 같은 곡선을 다시 그려 목표 recall 의 최소 비용 지점을 고를 수 있다.
8시험 대비
www.q-net.or.kr시험에서는 근사 최근접 이웃 검색이 왜 필요하고 HNSW 가 어떻게 탐색하는지 묻는 정의 · 특징형, HNSW · IVF · PQ 를 정확도 · 속도 · 메모리로 견주는 비교형이 나올 수 있다. 정의형은 전수 검색 비용(N × 차원)에서 출발해 계층 그래프 그림으로 답하고, 비교형은 같은 데이터의 recall ↔ 계산량 곡선과 비교표로 «무엇을 내주고 무엇을 얻는가»를 보인다. 임베딩과 함께 물으면 「임베딩 = 무엇이 가까운가 · 벡터 검색 = 가까운 것을 빨리 찾음」으로 경계를 짓는다.
- 개요 — 정의 · 전수 검색 비용 N × d · 차원이 약 10을 넘으면 트리 색인 무력화(Weber 1998)
- 거리 척도 — L2 · 내적 · 코사인과 정규화 시 L2 제곱 = 2 − 2 × 코사인 · 벡터당 곱셈 · 덧셈 d번
- HNSW 구조 — 그림 3 계층별 노드 수(1/16 씩 위로 · mL = 1/ln M) · M · efConstruction · 연결 바이트 식
- 탐색 절차 — 그림 5 사례 순서(상위 계층 ef = 1 하강 → 0계층 후보 ef · 16 은 0/10 · 64 는 10/10)
- IVF · PQ 와 비교 — 그림 4 부호 배치(1,536 → 48바이트) + 비교표(recall · 거리 계산 · 메모리 · 구축 시간)
- 재현율 ↔ 속도 조정 — 그림 6 곡선(recall 0.95 에 1,650번 ↔ 24,300번) · 재순위 · 선택 기준
꼭 쓸 키워드
근사 최근접 이웃HNSWefSearchIVFnprobe곱 양자화비대칭 거리 계산recall@k재순위차원의 저주
다른 답안과 차이를 내는 한 가지 — recall 0.95 에 드는 거리 계산 수를 HNSW · IVF 두 곡선으로 그려 「근사 검색 = 정확도를 계산량과 맞바꾸는 조정」을 숫자로 보인다.
9오해와 사실
- 오해벡터 데이터베이스는 가장 가까운 벡터를 정확히 돌려준다.사실HNSW · IVF 는 근사 색인이라 사례에서 efSearch 16 의 recall@10 은 0.672 였고, 정확한 답은 전수 검색(IndexFlat)만 보장한다(Douze 2024 3.1 · 3.2절).
- 오해코사인 유사도와 L2 거리는 결과 순서가 다르다.사실노름이 1인 벡터에서는 L2 제곱 = 2 − 2 × 코사인 이라 순서가 같고, 사례 #61542 도 1.2467 = 2 − 2 × 0.3767 이다(Douze 2024 3절 표 2).
- 오해벡터를 압축해도 검색만 빨라지고 정확도는 그대로다.사실1,536바이트를 48바이트 PQ 부호로 줄이자 recall@10 이 0.815 에서 0.517 로 떨어졌고, 원 벡터 재순위를 더해야 0.814 로 돌아왔다(본문 사례).
10핵심 정리
| 방식 | 줄이는 것 | 질의 인자 | 구축 인자 | 벡터당 바이트 | 사례 recall@10 |
|---|---|---|---|---|---|
| 전수(Flat) | 없음(정답 기준) | — | — | 4 × d = 1,536 | 1.000 |
| IVF-Flat | 열어 보는 목록 수 | nprobe | nlist · 군집 학습 | 4 × d + 8 | 0.815(nprobe 8) |
| HNSW | 따라가는 이웃 수 | efSearch | M · efConstruction | 4 × d + 연결 약 151 | 0.973(ef 64) |
| IVF-PQ | 목록 수 + 벡터 크기 | nprobe | nlist · m · nbits | m × nbits ÷ 8 + 8 | 0.517(nprobe 8) |
| 재순위 | 압축 오차 | 후보 수 k′ | 원 벡터 보관 | 원 벡터 따로 | 0.814(k′ 100) |
| LSH | 무작위 투영 버킷 | 버킷 수 | 투영 방향 수 | 해시 길이 | 데이터에 맞춰지지 않음(Douze 2024 5절) |
11참고 문헌
- 먼저 볼 문헌
- ★ Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs (Malkov · Yashunin · IEEE TPAMI) — 계층 그래프의 구축 · 탐색 알고리즘과 M · ef 인자를 원문으로 볼 때
- ★ Product Quantization for Nearest Neighbor Search (Jégou · Douze · Schmid · IEEE TPAMI 33(1)) — 벡터를 조각 부호로 압축하는 방법과 비대칭 거리 계산을 볼 때
- ★ The Faiss library (Douze et al. · arXiv 2401.08281v4) — IVF · 그래프 · 압축 색인의 선택 기준과 거리 계산 수 식을 볼 때
- ★ Faiss wiki — Faiss indexes — 색인 종류별 인자 이름과 벡터당 바이트 식을 볼 때
- 본문 근거
- ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms (Aumüller · Bernhardsson · Faithfull · Information Systems 87) — arXiv · 2018-07 ·
arxiv.org/abs/1807.05614· 확인 2026-11-03 - A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces (Weber · Schek · Blott · VLDB 1998) — VLDB Endowment · 1998-08 ·
www.vldb.org/conf/1998/p194.pdf· 확인 2026-11-03 - Billion-scale similarity search with GPUs (Johnson · Douze · Jégou) — arXiv · 2017-02 ·
arxiv.org/abs/1702.08734· 확인 2026-11-03