AI › 생성형 AI › LLM › 활용

벡터 검색Vector Search

질의 벡터와 거리가 가장 가까운 저장 벡터 k개를 찾는 검색이다. 모든 벡터와 거리를 재는 대신 그래프 · 군집 · 압축 색인으로 일부만 재어, 정확도를 조금 내주고 속도와 메모리를 얻는다.

1요약

  1. 벡터 검색은 임베딩 모델과 응용 사이에서 최근접 이웃 색인을 맡는 계층으로, 곱 양자화(2011) · HNSW(2016) 같은 방법을 Faiss 같은 오픈소스가 구현하고, 그 위에서 RAG 의 검색기 · 추천 · 중복 탐지가 돈다.
  2. 384차원 벡터 10만 개를 전수 검색하면 질의마다 거리 계산 10만 번(곱셈 · 덧셈 3,840만 번)이 들어 14.7 ms 가 걸렸고, 같은 데이터에서 HNSW 는 거리 계산 1,844번으로 정답 10개 중 평균 9.73개를 찾았다(본문 사례).
  3. 「검색 결과가 이상하다」는 전수 검색 결과와 겹치는 비율(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곳」 명단을 적어 들고, 명단이 더 나아지지 않을 때까지 이웃 집을 둘러본다.

고속도로 계층 4 · 3 진입점 1 손님 쪽 출구로 큰길 계층 2 · 1 2 골목 0계층 · 10만 집 3 질의 벡터 손님 집 4 top-10 5 기사의 도구 수첩 명단 64곳까지 적음 후보 목록 ef 가까운 10집 명단의 앞 10곳 top-10 결과 모든 집 방문 100,000번 전수 검색 번호 = 기사가 움직이는 순서 집 = 저장 벡터 · 집 사이 거리 = 벡터 거리 · 지도 세 장 = 같은 집들을 이웃 수를 달리해 엮은 계층 그래프

그림 1 · 기사는 고속도로 출구에서 손님 쪽으로 가며 지도를 한 장씩 내려오고, 골목에서만 수첩 명단을 들고 둘러봐 집집마다 가 보지 않고 가까운 10집을 찾는다.

출구에서 출발고속도로 지도 맨 위 한 곳
손님 쪽으로더 가까운 출구로만 이동
지도 갈아타기큰길 · 골목 지도로 내려감
수첩 명단가까운 집 64곳을 적어 둠
이웃 둘러보기명단이 나아지지 않으면 멈춤
10집 확정명단 앞쪽 10곳
비유 — 수첩 명단의 길이 16곳 수첩 명단이 금방 차서 옆 동네에서 멈춤 가까운 10집 중 0집 64곳 수첩 더 둘러본 뒤 손님 동네에 닿음 10집 모두 찾음 실제 — 질의 #0 의 efSearch ef 16 거리 계산 524번 10번째 거리 1.743 > 정답 1.424 0 / 10 찾음 ef 64 거리 계산 2,526번 10번째 거리 1.424 = 정답 10 / 10 찾음 막대 = 거리 계산 횟수 · 거리 = L2 제곱 · 정답 = 전수 검색의 10번째 이웃 거리

그림 2 · 수첩 명단이 짧으면 기사는 옆 동네에서 멈추고, 명단을 늘리면 더 걷는 대신 손님 동네에 닿는다 — 실제로 efSearch 16 은 질의 #0 의 정답을 하나도 못 찾았고 64 는 10개를 모두 찾았다.

비유 속 역할실제 이름실제로 하는 일
도시의 집 10만 채저장 벡터384차원 벡터 100,000개를 색인에 넣는다
손님 집질의 벡터같은 공간의 벡터 하나로 가까운 이웃을 묻는다
집 사이 거리거리 척도L2 거리 · 내적 · 코사인 중 하나로 가깝다를 정한다
겹친 지도 세 장계층 그래프위 계층일수록 노드가 적고 먼 이웃을 잇는다
고속도로 출구진입점맨 위 계층의 한 노드에서 탐색을 시작한다
수첩 명단 64곳후보 목록 efSearch0계층에서 가까운 후보를 이만큼 들고 넓힌다
가까운 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 이다.

HNSW(M 16) — 계층별 노드 수 4계층 · 1개(진입점) 3계층 · 20개 2계층 · 371개 1계층 · 6,374개 · 이웃 ≤ 16 0계층 · 100,000개 · 이웃 ≤ 32 탐색 — 4 ~ 1계층은 가장 가까운 한 점만(ef = 1), 0계층만 후보 ef 개 막대 길이 = 노드 수의 로그 비율 · 노드 = 저장 벡터 · 화살 = 질의가 내려가는 방향 벡터 하나의 바이트 벡터 1,536 연결 144(실측) 연결 = (32 + 16/ln16) × 4 = 151바이트(식) 이웃 상한 M 16 · 0계층 32 위로 오르는 비율 1/16 기댓값 6,250 · 실측 6,374 저장 벡터 · 노드 그래프 연결(이웃 번호 4바이트씩) 식 = Malkov 2018 4.2.3절 · 실측 = 사례 색인

그림 3 · HNSW 는 계층마다 노드의 약 1/16 만 위 계층에 올리므로 10만 개가 다섯 계층에 쌓이고, 벡터 하나에 붙는 연결은 벡터 크기의 약 1/10 이다.

IVF-PQ — 목록을 고르고, 목록 안은 부호로 잰다 원 벡터 1,536바이트 8차원 8차원 8차원 … 조각 48개(384차원) … 8차원 조각마다 중심 256개 중 가장 가까운 번호 = 1바이트 PQ 부호 48바이트 + ID 8 17 203 5 … 번호 48개 … 88 번호 = 예시 질의는 압축하지 않음 — 질의마다 48 × 256 크기 거리표를 한 번 계산(곱셈 · 덧셈 98,304번) 벡터 하나 = 표 칸 48개 조회 · 덧셈 48번(원 벡터는 곱셈 · 덧셈 384번) IVF 목록 1,024개 nprobe 8 최소 21 중앙 54 평균 98 최대 724 목록 크기가 고르지 않아 목록 안 거리 계산은 식 기대값 781번(8 × 100,000 ÷ 1,024)보다 많은 3,197번(질의 평균)

그림 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절)
후보 목록 efefConstruction · 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@k0 ~ 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)) · 시간은 이 실행 환경의 값이다.

  1. 정답 만들기 — 384차원 벡터 100,000개에 IndexFlatL2 로 질의 #0 을 전수 검색하면 거리 계산 100,000번 · 14.7 ms 이고, 1위는 #61542(L2 제곱 1.247), 10번째 이웃 거리는 1.424 다.
  2. 색인 구축 — IndexHNSWFlat(M 16 · efConstruction 100)에 100,000개를 넣는 데 72.6초가 걸리고, 노드가 0 ~ 4계층에 100,000 · 6,374 · 371 · 20 · 1개로 쌓인다.
  3. 상위 계층 하강 — 4계층의 유일한 노드 #20288(거리 2.186)에서 시작해 3계층 이웃 30개를 재고 #31374(1.730)로 한 번 옮긴 뒤, 2 · 1계층에서는 이웃 28개 중 더 가까운 것이 없어 그대로 내려간다(Malkov 2018 알고리즘 5).
  4. 0계층 · efSearch 16 — 후보 목록 16개로 넓히다 거리 계산 524번에서 멈추고, 10번째 거리 1.743 이 정답 1.424 보다 커서 정답 10개 중 0개를 찾는다.
  5. 0계층 · efSearch 64 — 같은 질의를 후보 64개로 다시 찾으면 거리 계산 2,526번(전수의 2.5%) 끝에 정답 10개를 모두 찾는다.
  6. 질의 1,000개 평균 — efSearch 64 는 recall@10 0.973 · 거리 계산 1,844번 · 0.54 ms 로, 전수 검색 14.7 ms 의 약 1/27 시간이 걸린다.
단계 사례 값 1 정답 만들기 전수 거리 100,000번 · 14.7 ms → 1위 #61542(1.247) · 10번째 1.424 2 색인 구축 M 16 · efConstruction 100 · 72.6초 · 계층별 100,000 / 6,374 / 371 / 20 / 1 3 상위 계층 하강 4계층 #20288 거리 2.186 3계층 #31374 이웃 30개 · 거리 1.730 2 · 1계층 이웃 28개 · 이동 없음 4 ef 16 0계층 거리 524번 · 10번째 1.743 > 1.424 정답 0 / 10 5 ef 64 0계층 거리 2,526번(전수의 2.5%) · 10번째 1.424 정답 10 / 10 6 1,000개 평균 efSearch 64 → recall@10 0.973 · 거리 1,844번 · 0.54 ms 전수 검색 14.7 ms 의 약 1/27 정답 · 성공 색인 탐색 규칙 정답 놓침 거리 = L2 제곱 · #번호 = 벡터 ID

그림 5 · 질의 #0 은 위 계층에서 한 번만 옮겨 0계층에 닿고, 같은 진입 뒤에도 efSearch 16 은 정답 0개 · 64 는 10개를 찾는다.

재현율 ↔ 계산량 — 질의 1,000개 평균 1,000 10,000 100,000 질의당 거리 계산 횟수(로그 눈금) 0.4 0.6 0.8 0.95 1.0 recall @10 ef 10 ef 16 ef 32 ef 64 128 256 512 np 1 4 8 16 32 np 64 전수 1.0 recall 0.95 에 드는 계산 HNSW 약 1,650번 IVF 약 24,300번(약 15배) HNSW(efSearch) IVF-Flat(nprobe · 중심 1,024번 포함) 전수 검색 굵은 테두리 = 사례 6

그림 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@101.0000.8150.9730.517 · 재순위 100개 뒤 0.814
질의당 거리 계산100,000번4,221번(중심 1,024 포함)1,844번4,221번(표 조회)
질의당 시간14.7 ms0.64 ms0.54 ms0.35 ms · 재순위 0.37 ms
색인 크기153.6 MB156.0 MB168.0 MB7.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.linalg.norm(xb, axis=1) · index.metric_type노름이 1이 아니면 내적 ≠ 코사인(Faiss 문서 IndexFlatIP)
2전수는 맞고 색인 결과만 다름efSearch · nprobe 부족탐색질의 100개로 IndexFlat 대비 recall@10목표 미만이면 efSearch · nprobe 를 올리며 다시 잼 · 구축은 그대로(Douze 2024 3.4절)
3평균은 높은데 0 / 10 질의가 있음그래프가 군집 경계에서 막힘구축질의별 recall 분포 · faiss.cvar.hnsw_stats.nhops경계에서 막힘 = 이웃 선택 휴리스틱 · M · efConstruction 확인(Malkov 2018 4.1절)
4IVF 질의 시간이 질의마다 들쭉날쭉목록 크기 불균형구축index.invlists.list_size(i) 분포식 18 은 같은 크기 목록을 가정(Douze 2024 5.1절)
5압축 뒤 recall 급락PQ 부호 오차압축IndexRefineFlat 재순위 전후 recall재순위로 회복되면 압축 탓(Douze 2024 3.5절)
6메모리 초과원 벡터 + 그래프 연결저장len(faiss.serialize_index(index))연결 = (Mmax0 + mL × Mmax) × 4바이트(Malkov 2018 4.2.3절)

전수 결과와 비교할 질의 묶음을 고정해 두면 efSearch · nprobe 를 바꿀 때마다 그림 6 같은 곡선을 다시 그려 목표 recall 의 최소 비용 지점을 고를 수 있다.

8시험 대비

출제 정보 정보관리(140회, 137회, 133회)문제 원문 — 큐넷 자료실 「기출문제(기술사)」 www.q-net.or.kr

시험에서는 근사 최근접 이웃 검색이 왜 필요하고 HNSW 가 어떻게 탐색하는지 묻는 정의 · 특징형, HNSW · IVF · PQ 를 정확도 · 속도 · 메모리로 견주는 비교형이 나올 수 있다. 정의형은 전수 검색 비용(N × 차원)에서 출발해 계층 그래프 그림으로 답하고, 비교형은 같은 데이터의 recall ↔ 계산량 곡선과 비교표로 «무엇을 내주고 무엇을 얻는가»를 보인다. 임베딩과 함께 물으면 「임베딩 = 무엇이 가까운가 · 벡터 검색 = 가까운 것을 빨리 찾음」으로 경계를 짓는다.

답안 목차
  1. 개요 — 정의 · 전수 검색 비용 N × d · 차원이 약 10을 넘으면 트리 색인 무력화(Weber 1998)
  2. 거리 척도 — L2 · 내적 · 코사인과 정규화 시 L2 제곱 = 2 − 2 × 코사인 · 벡터당 곱셈 · 덧셈 d번
  3. HNSW 구조 — 그림 3 계층별 노드 수(1/16 씩 위로 · mL = 1/ln M) · M · efConstruction · 연결 바이트 식
  4. 탐색 절차 — 그림 5 사례 순서(상위 계층 ef = 1 하강 → 0계층 후보 ef · 16 은 0/10 · 64 는 10/10)
  5. IVF · PQ 와 비교 — 그림 4 부호 배치(1,536 → 48바이트) + 비교표(recall · 거리 계산 · 메모리 · 구축 시간)
  6. 재현율 ↔ 속도 조정 — 그림 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,5361.000
IVF-Flat열어 보는 목록 수nprobenlist · 군집 학습4 × d + 80.815(nprobe 8)
HNSW따라가는 이웃 수efSearchM · efConstruction4 × d + 연결 약 1510.973(ef 64)
IVF-PQ목록 수 + 벡터 크기nprobenlist · m · nbitsm × nbits ÷ 8 + 80.517(nprobe 8)
재순위압축 오차후보 수 k′원 벡터 보관원 벡터 따로0.814(k′ 100)
LSH무작위 투영 버킷버킷 수투영 방향 수해시 길이데이터에 맞춰지지 않음(Douze 2024 5절)

11참고 문헌

  1. 먼저 볼 문헌
  2. ★ Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs (Malkov · Yashunin · IEEE TPAMI) — 계층 그래프의 구축 · 탐색 알고리즘과 M · ef 인자를 원문으로 볼 때
    arXiv · 2018-08 · arxiv.org/abs/1603.09320 · 확인 2026-11-03
  3. ★ Product Quantization for Nearest Neighbor Search (Jégou · Douze · Schmid · IEEE TPAMI 33(1)) — 벡터를 조각 부호로 압축하는 방법과 비대칭 거리 계산을 볼 때
    IEEE · 2011-01 · doi.org/10.1109/TPAMI.2010.57 · 확인 2026-11-03
  4. ★ The Faiss library (Douze et al. · arXiv 2401.08281v4) — IVF · 그래프 · 압축 색인의 선택 기준과 거리 계산 수 식을 볼 때
    arXiv · 2025-10 · arxiv.org/abs/2401.08281 · 확인 2026-11-03
  5. ★ Faiss wiki — Faiss indexes — 색인 종류별 인자 이름과 벡터당 바이트 식을 볼 때
    Meta AI Research · 2026-11 · github.com/facebookresearch/faiss/wiki/Faiss-indexes · 확인 2026-11-03
  6. 본문 근거
  7. 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
  8. 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
  9. Billion-scale similarity search with GPUs (Johnson · Douze · Jégou) — arXiv · 2017-02 · arxiv.org/abs/1702.08734 · 확인 2026-11-03