Field Log · Entry

ANN Vector Index: Flat·HNSW·IVF·PQ 선택법 (5/10)

동일한 vector 공간을 Flat 전수 비교, HNSW graph 탐색, IVF cluster 탐색, PQ 압축 code로 검색하는 ANN index 비교

오늘의 결론

ANN은 embedding 품질을 높이는 기술이 아니라 일부 비교를 건너뛰어 더 빨리 찾는 index입니다.

Flat exact search 결과를 ground truth로 두고 ANN 자체의 Recall@k를 측정합니다.

HNSW는 graph 탐색, IVF는 가까운 cluster만 탐색, PQ는 vector를 짧은 code로 압축합니다.

latency, recall, memory뿐 아니라 build·update·delete·filter 비용을 함께 봅니다.

exact search가 정답을 놓치면 efSearch가 아니라 embedding과 chunk를 고칩니다.

앞 글에서는 모든 passage vector와 query vector의 dot product를 계산했습니다. vector가 1만 개일 때는 단순하지만 1억 개가 되면 query마다 모든 vector를 읽는 비용이 커집니다.

Approximate Nearest Neighbor, 즉 ANN index는 가까울 가능성이 낮은 vector를 건너뛰어 탐색량을 줄입니다. 대신 exact top-k 일부를 놓칠 수 있습니다.

Flat, HNSW, IVF, PQ의 vector 탐색 방식 비교

그림 1. Flat은 모든 점을 비교하고, HNSW는 graph edge를 따라가며, IVF는 가까운 cluster만 열고, PQ는 원본 vector 대신 짧은 code로 거리를 근사한다.

먼저 exact kNN 비용을 본다

passage vector 수가 N, 차원이 d일 때 query 하나와 모든 vector의 dot product는 대략 O(Nd) 계산입니다.

q ∈ Rᵈ
P ∈ Rᴺˣᵈ
scores = Pq

matrix multiplication은 매우 최적화돼 있고 GPU batch에서는 강력합니다. 따라서 “vector가 많으니 무조건 ANN”은 아닙니다.

Flat exact search의 장점:

index가 단순합니다.
검색 오차가 없습니다.
build가 거의 필요 없습니다.
batch query에서 hardware 효율이 좋습니다.
다른 ANN index의 정답 기준이 됩니다.

단점:

매 query가 전체 vector를 읽습니다.
N이 커지면 memory bandwidth와 latency가 증가합니다.
CPU single-query serving에서 규모가 커질수록 비쌉니다.

ANN의 정확도는 두 종류로 나눈다

1. Index Recall@k

같은 query에서 exact top-k와 ANN top-k가 얼마나 겹치는지 봅니다.

ANN Recall@k = |ANN_top_k ∩ Exact_top_k| / k

예를 들어 exact top-5가 {A,B,C,D,E}, ANN top-5가 {A,B,C,E,F}이면 4/5 = 0.8입니다.

이 metric은 index가 exact neighbor를 얼마나 재현했는지 측정합니다. 문서가 실제 정답인지 여부는 보지 않습니다.

2. Task Recall@k

gold evidence가 top-k에 들어왔는지 측정합니다.

Task Recall@k = gold evidence를 찾은 query 수 / 전체 query 수

두 metric을 함께 보면 원인을 분리할 수 있습니다.

Dense exact Task Recall 낮음
→ embedding·chunk·query 문제

Dense exact Task Recall 높음 + ANN Index Recall 낮음
→ index 탐색 parameter 문제

ANN Index Recall 높음 + end-to-end answer 낮음
→ rerank·context·generation 문제

Flat: 모든 vector를 비교하는 기준선

FAISS에서 normalized vector의 cosine search를 inner product로 실행할 수 있습니다.

import faiss
import numpy as np

def unit_rows(vectors: np.ndarray) -> np.ndarray:
    values = np.asarray(vectors, dtype=np.float32).copy()
    faiss.normalize_L2(values)
    return values

passages = unit_rows(passage_vectors)
queries = unit_rows(query_vectors)

dimension = passages.shape[1]
flat = faiss.IndexFlatIP(dimension)
flat.add(passages)

exact_scores, exact_ids = flat.search(queries, k=10)

IndexFlatIP는 inner product를 사용합니다. cosine을 원하면 query와 passage를 모두 normalize해야 합니다.

ID mapping을 row number에 의존하지 않으려면 application의 stable ID와 index ID mapping을 versioning하거나 IndexIDMap2 같은 wrapper를 사용합니다.

HNSW: 가까운 이웃 graph를 따라간다

Hierarchical Navigable Small World graph는 vector를 node로, 가까운 node 사이 연결을 edge로 저장합니다.

직관은 고속도로와 동네 길입니다.

상위 layer: 적은 node, 긴 거리 이동
      ↓ 가까운 영역으로 내려감
하위 layer: 많은 node, 촘촘한 local 탐색

query는 entry point에서 시작해 더 가까운 neighbor로 이동합니다. 모든 vector를 보지 않고 graph 경로를 따라 후보를 확장합니다.

핵심 parameter

parameter	역할	크게 하면
`M`	node당 연결 수	recall·memory·build 비용 증가
`efConstruction`	build 중 탐색 후보 폭	graph 품질·build 시간 증가
`efSearch`	query 중 탐색 후보 폭	recall·latency 증가

efSearch는 online에서 가장 직접적인 recall-latency knob입니다. 보통 k보다 충분히 크게 두고 evaluation set에서 조정합니다.

M = 32
hnsw = faiss.IndexHNSWFlat(
    dimension,
    M,
    faiss.METRIC_INNER_PRODUCT,
)
hnsw.hnsw.efConstruction = 200
hnsw.hnsw.efSearch = 64
hnsw.add(passages)

ann_scores, ann_ids = hnsw.search(queries, k=10)

HNSW의 장점

높은 recall과 낮은 single-query latency를 내기 쉽습니다.
별도 coarse quantizer training 없이 사용할 수 있습니다.
많은 구현에서 online add를 지원합니다.

HNSW의 비용

원본 vector 외 graph edge memory가 큽니다.
build가 Flat보다 비쌉니다.
delete가 tombstone과 rebuild/compaction을 요구할 수 있습니다.
매우 선택적인 metadata filter가 graph 경로를 끊으면 recall이 떨어질 수 있습니다.

구현별 update와 filter 방식이 다르므로 “HNSW”라는 이름만으로 운영 특성을 가정하지 않습니다.

IVF: vector 공간을 먼저 cluster로 나눈다

Inverted File Index(IVF)는 vector를 nlist개의 coarse cluster로 나눕니다.

training vectors → k-means centroids c₁ ... cₙₗᵢₛₜ
passage vector → 가장 가까운 centroid의 list에 저장

query → 가까운 centroid nprobe개 선택
      → 그 list 안의 vector만 비교

nlist가 너무 작으면 list 하나가 커서 많이 비교합니다. 너무 크면 training과 memory overhead가 커지고 각 cluster가 불안정할 수 있습니다.

nprobe를 늘리면 더 많은 cluster를 열어 recall이 오르지만 latency도 증가합니다.

nlist = 1024
quantizer = faiss.IndexFlatIP(dimension)
ivf = faiss.IndexIVFFlat(
    quantizer,
    dimension,
    nlist,
    faiss.METRIC_INNER_PRODUCT,
)

# production에서는 corpus 분포를 대표하는 충분한 training sample 사용
ivf.train(training_vectors)
ivf.add(passages)
ivf.nprobe = 16

ivf_scores, ivf_ids = ivf.search(queries, k=10)

training_vectors도 passage와 같은 normalization·dtype 계약을 따라야 합니다.

IVF가 맞는 상황

corpus가 매우 커서 memory locality가 중요함
offline training과 batch build를 감당할 수 있음
query마다 탐색할 cluster 수를 조절하고 싶음
IVF-PQ 등 압축과 결합하려 함

주의할 상황

작은 corpus
분포가 빠르게 변해 centroid가 오래된 경우
training sample이 corpus를 대표하지 못함
filter 후 특정 cluster의 후보가 거의 사라지는 경우

PQ: vector를 여러 조각의 code로 압축한다

Product Quantization은 d차원 vector를 m개 subvector로 나누고, 각 subspace에서 가까운 codeword ID만 저장합니다.

원본 vector 768 × float32 = 3,072 bytes

m = 96, 각 subvector code를 8 bit로 저장
→ 96 bytes code

개념적으로 약 32배 작아지지만 codebook, ID, index overhead가 별도로 있습니다.

v = [v¹ | v² | ... | vᵐ]
       ↓ 각 subvector를 가장 가까운 centroid ID로
code(v) = [17, 203, ..., 4]

query와 codeword 간 거리 table을 먼저 계산하면 원본 vector를 복원하지 않고 approximate distance를 빠르게 합산할 수 있습니다.

PQ의 trade-off

장점: vector memory와 bandwidth 대폭 감소
단점: quantization error로 ranking 변동
m 증가: 더 긴 code, 보통 더 정확
codeword bit 증가: 더 큰 codebook과 code, 더 정확할 수 있음

IVF와 PQ를 결합한 IVF-PQ는 가까운 cluster만 열고 그 안의 vector도 압축 code로 비교합니다.

네 방법을 같은 축으로 비교한다

Index	검색 방식	Training	추가 memory	Update	오차 원인
Flat	전수 비교	없음	낮음	쉬움	없음
HNSW	graph 탐색	graph build	graph edge 큼	구현 의존	탐색 경로
IVF-Flat	cluster 일부 탐색	centroid 필요	list/centroid	재학습 고려	cluster 미탐색
PQ	압축 code 거리	codebook 필요	vector는 작음	재학습 고려	quantization
IVF-PQ	cluster + 압축	둘 다 필요	작음	복잡	두 오차 결합

“가장 좋은 index”가 아니라 제약에 맞는 지점을 찾습니다.

Metric 계약을 먼저 맞춘다

index 생성 전에 다음을 고정합니다.

{
  "model_revision": "...",
  "dimension": 768,
  "dtype": "float32",
  "normalized": true,
  "metric": "inner_product",
  "index_family": "hnsw",
  "index_params": {
    "M": 32,
    "efConstruction": 200,
    "efSearch": 64
  }
}

흔한 오류:

cosine model인데 passage만 normalize
inner product용 index에 L2 distance score 해석 적용
384차원 index에 768차원 query 사용
새 model vector를 이전 index에 일부 섞음
distance는 작을수록 좋은데 similarity처럼 역순 정렬

index library마다 score의 방향과 metric 이름을 확인합니다.

ANN benchmark harness

정확도와 latency를 같은 query batch에서 측정합니다.

from time import perf_counter
import numpy as np

def index_recall_at_k(exact: np.ndarray, approx: np.ndarray) -> float:
    if exact.shape != approx.shape:
        raise ValueError("shape mismatch")
    recalls = []
    for gold_row, ann_row in zip(exact, approx):
        recalls.append(len(set(gold_row) & set(ann_row)) / len(gold_row))
    return float(np.mean(recalls))

def benchmark(index, queries: np.ndarray, k: int, repeats: int = 5):
    # warm-up 결과는 latency sample에서 제외
    index.search(queries[: min(10, len(queries))], k)

    samples_ms = []
    result_ids = None
    for _ in range(repeats):
        started = perf_counter()
        _, result_ids = index.search(queries, k)
        samples_ms.append((perf_counter() - started) * 1000 / len(queries))

    return {
        "ids": result_ids,
        "mean_ms_per_query": float(np.mean(samples_ms)),
        "p95_run_ms_per_query": float(np.percentile(samples_ms, 95)),
    }

실제 serving에서는 batch 평균 외에 개별 request의 p50/p95/p99, concurrency, queue time을 측정해야 합니다.

HNSW parameter sweep 예시

rows = []
for ef_search in [16, 32, 64, 128, 256]:
    hnsw.hnsw.efSearch = ef_search
    result = benchmark(hnsw, queries, k=10)
    rows.append({
        "efSearch": ef_search,
        "index_recall@10": index_recall_at_k(
            exact_ids,
            result["ids"],
        ),
        "mean_ms": result["mean_ms_per_query"],
    })

목표를 먼저 정합니다.

constraint: p95 vector search ≤ 25 ms
objective: 그 안에서 Index Recall@10 최대화

반대로 task Recall@20이 0.95 이상이어야 한다는 constraint를 둘 수도 있습니다.

Benchmark에서 함께 측정할 것

범주	metric
정확도	Index Recall@k, Task Recall@k
latency	p50, p95, p99, timeout rate
처리량	QPS at fixed concurrency
memory	raw vector, index, process RSS, replica
build	training·add 시간, peak memory
update	add/delete visibility latency
filter	selectivity bucket별 recall·latency
운영	snapshot size, load time, recovery time

benchmark hardware, thread 수, batch size, query 수, warm-up, cache 상태를 함께 기록합니다.

Metadata filter가 ANN을 어렵게 하는 이유

질문은 가까운 vector를 찾지만 실제 후보는 tenant와 ACL을 만족해야 합니다.

vector top-100 검색 → ACL filter → 3개 남음

post-filter만 쓰면 결과 수가 부족할 수 있습니다. top-k를 크게 하면 latency가 늘고 unauthorized candidate를 내부 trace에서 다룰 위험도 생깁니다.

pre-filter는 안전하지만 index 구현에 따라 graph/cluster 탐색 효율과 recall에 영향을 줍니다.

선택지:

tenant별 물리 index 분리
bitmap·payload pre-filter를 지원하는 engine 사용
filter-aware graph/index
작은 tenant는 Flat exact search
매우 선택적인 filter에서 oversampling 후 authorized rerank

권한은 정확도 최적화보다 우선하는 hard constraint입니다.

Filter selectivity별로 따로 평가한다

selectivity 50%  : 후보 절반 허용
selectivity 1%   : 후보 100개 중 1개 허용
selectivity 0.01%: 매우 작은 tenant/ACL group

평균 filter 하나로는 극단적인 tenant의 empty result를 놓칩니다.

Update와 delete는 제품 기능이 아니라 index 특성이다

운영 질문을 미리 답합니다.

add 후 언제 query에 보이는가?
동일 stable ID upsert가 atomic한가?
delete는 즉시 물리 삭제인가 tombstone인가?
tombstone이 graph 품질과 memory에 어떤 영향을 주는가?
compaction/rebuild 중 serving은 가능한가?
snapshot과 WAL로 어떤 RPO/RTO를 보장하는가?
replica마다 index version이 같은가?

embedding model을 바꾸면 dimension이 같아도 전체 re-embedding과 새 index build가 필요합니다. blue/green index로 전환하고 trace에 version을 남깁니다.

dense-v7 build → offline evaluation → shadow traffic
→ active alias를 v6에서 v7로 전환 → rollback window 유지

Index 선택의 현실적인 시작점

Flat부터 시작

corpus가 작거나 batch GPU 검색이 가능
exact baseline이 아직 없음
update와 운영 단순성이 중요

HNSW 후보

CPU single-query latency가 중요
memory에 graph와 vector를 올릴 수 있음
높은 recall과 online add가 필요

IVF 후보

corpus가 매우 큼
representative training sample과 batch build가 가능
memory locality와 probe 수 제어가 중요

PQ 또는 IVF-PQ 후보

raw vector memory가 가장 큰 제약
일부 quantization 오차를 감당 가능
codebook training과 품질 검증이 가능

한 index family 안에서도 구현, hardware, filter, parameter에 따라 결과가 크게 달라집니다.

흔한 진단 실수

증상	잘못된 첫 반응	먼저 할 진단
gold 문서가 없음	efSearch 증가	exact top-k에는 있는가?
p95만 높음	embedding 교체	concurrency·queue·filter selectivity
새 문서가 안 보임	query rewrite	add visibility와 active version
특정 tenant만 빈 결과	k 증가	pre/post filter와 index partition
memory 급증	PQ 즉시 도입	graph edge·replica·metadata breakdown
점수 방향 반대	reranker 추가	metric과 score ordering

Production 체크리스트

스스로 확인하기

ANN Index Recall@k와 gold evidence Task Recall@k는 무엇이 다른가?
HNSW에서 efSearch를 늘리면 왜 recall과 latency가 함께 오르는가?
IVF의 nlist와 nprobe는 각각 build와 query에서 어떤 역할을 하는가?
PQ가 memory를 줄이는 대신 어떤 종류의 ranking 오차를 만드는가?
exact top-k에도 정답이 없을 때 ANN parameter를 바꾸면 안 되는 이유는 무엇인가?

다음 글에서는 서로 다른 실패를 가진 sparse와 dense 후보를 RRF와 score fusion으로 합치는 Hybrid Search를 구현합니다.