HNSW vs. LSH: Elasticsearch가 15,000 QPS에서 recall@10 0.99를 달성한 방법과 비용
출처: Elastic Blog
HNSW, 양자화, 그리고 재현율/속도 트레이드오프
초당 15,000개의 쿼리에서 Elasticsearch 계층형 탐색 가능한 작은 세계(HNSW)는 float32 벡터에 대해 recall@10이 0.99에 도달합니다. DiskBBQ 양자화를 적용하면 초당 55,000 QPS에서 0.97의 recall을 제공하는데, 이는 recall이 0.02 감소하면서도 처리량이 3.7배 증가한 결과이며, 이는 Elasticsearch Labs 벤치마크에 기반합니다. 이 블로그에서는 다음과 같은 내용이 어떻게 가능한지 설명합니다.
- 정확한 최근접 이웃 검색이 규모에 따라 왜 붕괴되는지
- 근사 최근접 이웃(ANN) 인덱스가 문제를 어떻게 변형시키는지
- HNSW가 레이어별로 어떻게 동작하는지
- 양자화가 메모리를 줄이면서도 recall을 파괴하지 않는 방법
- 오늘날 여러분이 작성하는 Elasticsearch 매핑 및 쿼리에 이 모든 것이 의미하는 바
각 섹션마다 코드, 수치, 혹은 다이어그램이 포함됩니다.
정확한 최근접 이웃 검색이 확장되지 않는 이유
쿼리와 가장 유사한 벡터를 찾는 일은 직관적으로 간단해 보입니다. 쿼리와 데이터셋의 모든 벡터 사이 거리를 계산하고 가장 가까운 것을 반환하면 됩니다. 1,000개의 768차원 벡터라면 쿼리당 약 150만 번의 부동소수점 연산이 필요합니다. 충분히 빠릅니다.
하지만 1천만 벡터가 되면 150억 연산, 10억 벡터가 되면 7500억 연산이 필요합니다. 쿼리 지연시간은 데이터셋 크기에 비례해 선형적으로 증가합니다. 정확한 검색에서는 이를 피할 방법이 없습니다.
첫 번째 직관은 공간 인덱스를 사용하는 것입니다. KD-트리는 좌표축을 따라 공간을 분할하는데, 이는 2~10차원에서 잘 동작합니다. KD-트리 쿼리는 가장 가까운 이웃이 있을 법한 파티션만 방문하므로 데이터셋의 대부분을 건너뛸 수 있습니다. 실제로 저차원 데이터에서는 탐색 시간을 O(n)에서 대략 O(log n) 수준으로 낮출 수 있습니다.
문제는 대부분의 임베딩 모델이 384~1,536 차원의 벡터를 만든다는 점입니다. 고차원 공간에서는 모든 점이 서로 거의 같은 거리를 갖게 됩니다. 이 현상—차원의 저주— 때문에 KD-트리의 파티션 경계가 서브트리를 후보에서 제외하는 경우가 거의 없습니다. 결국 트리 탐색은 대부분의 노드를 방문하게 됩니다. 실험적으로 KD-트리는 차원이 약 20을 넘으면 완전 탐색보다 성능이 좋지 않다는 것이 밝혀졌습니다.
Ball‑tree와 R‑tree도 같은 문제를 안고 있습니다. 파티셔닝 기하를 바꾸긴 하지만, 차원의 저주는 고차원에서 모든 정확한 파티션 기반 구조에 영향을 미칩니다.
핵심은 정확한 검색과 고차원 데이터가 서로 충돌한다는 점입니다. 근사 최근접 이웃(ANN) 검색은 작은, 제어 가능한 recall 손실을 감수함으로써 쿼리 시간을 수십 배 빠르게 만들면서 이 문제를 해결합니다.
ANN 인덱스가 검색 문제를 변형시키는 방식
정확한 최근접 이웃을 찾는 대신, ANN 인덱스는 실제 최근접 이웃을 포함할 가능성이 높은 결과 집합을 반환합니다. 대부분의 검색 애플리케이션—시맨틱 서치, Retrieval‑Augmented Generation(RAG) 파이프라인, 추천 시스템—에서는 실제 최근접 이웃과 거의 동일한 결과면 충분히 유용합니다. 예를 들어 코사인 유사도가 0.94인 경우는 문서 검색에서 0.95와 의미 차이가 거의 없습니다.
ANN 인덱스는 인덱스 구축 단계에서 데이터 구조를 만들고, 쿼리 시 대부분의 데이터셋을 건너뛰면서도 올바른 이웃 영역에 도달하도록 합니다. 현재 주류를 이루는 세 가지 인덱스 구조는 다음과 같습니다.
flowchart TD
A[Raw vectors] --> B[Index construction]
B --> C{Index type}
C --> D[HNSW graph]
C --> E[IVF clusters]
C --> F[LSH buckets]
D --> G[Query vector]
E --> G
F --> G
G --> H[Index traversal]
H --> I[Approximate top-k results]- HNSW는 다층 근접 그래프를 구축합니다.
- IVF(역파일) 인덱스는 벡터를 클러스터링하고, 쿼리 시 가장 관련성 높은 클러스터만 탐색합니다.
- **LSH(지역 민감 해싱)**는 유사한 벡터가 동일한 해시 버킷에 들어가도록 매핑합니다.
각 구조는 구축 시간과 메모리를 희생해 더 빠른 쿼리를 제공하며, recall 수준은 조정 가능합니다.
HNSW는 현재 밀집 벡터 검색에서 가장 널리 사용되는 프로덕션 선택지입니다. 코사인 및 유클리드 유사도에서 IVF나 LSH보다 높은 recall을 더 높은 QPS와 함께 제공하며, 인덱스를 재구축하지 않고도 recall/속도 트레이드오프를 조정할 수 있습니다.
HNSW: 프로덕션 벡터 검색을 이끄는 알고리즘
HNSW는 2016년 Malkov와 Yashunin이 제안했으며, 그 이후 대부분의 프로덕션‑급 밀집 벡터 검색 시스템의 기반이 되어 왔습니다. 이 알고리즘은 여러 레이어로 구성된 그래프를 만들며, 각 레이어는 전체 데이터셋의 부분집합이고, 상위 레이어일수록 노드 수가 적고 장거리 연결이 많습니다.
구조는 고속도로 시스템과 비슷합니다.
- Layer 2: 소수의 노드가 장거리(고속도로) 엣지로 연결돼 있어 큰 거리를 빠르게 건널 수 있습니다.
- Layer 1: 더 많은 노드가 지역 도로 수준의 짧은 엣지로 연결됩니다.
- Layer 0: 데이터셋의 모든 노드가 존재하며, 인접 이웃과 촘촘히 연결됩니다.
쿼리는 위에서 아래로 진행됩니다.
- 가장 높은 레이어의 고정 진입점(entry point)으로 그래프에 진입합니다.
- 현재 레이어에서 가장 가까운 이웃으로 탐욕적으로 이동합니다.
- 동일 노드에서 다음 하위 레이어로 내려갑니다.
- Layer 0에 도달할 때까지 반복합니다.
- Layer 0에서는 빔 서치를 수행해 근사 k‑nearest neighbors를 찾습니다.
이 탐욕적 탐색은 각 레이어가 검색 영역을 크게 축소한 뒤 하위 레이어로 내려가기 때문에 매우 빠릅니다. 쿼리가 Layer 0에 도달했을 때 이미 올바른 이웃 근처에 위치하게 됩니다.
인덱스 구축 시 조정 가능한 두 파라미터
- m: 노드가 삽입될 때 생성하는 양방향 연결 수. m이 클수록 노드당 연결이 많아져 recall이 상승하지만 메모리 사용량과 구축 시간이 증가합니다. 일반적인 값: 16 ~ 64.
- ef_construction: 그래프 구축 중 후보 리스트의 크기. 값이 클수록 더 좋은 연결을 찾아내어 recall이 향상하지만 인덱싱 속도가 느려집니다. 일반적인 값: 100 ~ 500.
쿼리 시 조정 가능한 세 번째 파라미터
- num_candidates(일부 구현에서는
ef): Layer 0에서 빔 서치의 폭을 제어합니다. 값을 높이면 recall이 상승하지만 개별 쿼리 응답 속도가 느려집니다. 이 파라미터는 인덱스를 재구축하지 않고도 쿼리마다 조정할 수 있어, 서로 다른 recall 요구사항을 가진 다양한 사용 사례에 실용적입니다.
한 가지 솔직한 트레이드오프: HNSW 인덱스는 메모리를 많이 잡아먹습니다. 10 백만 개의 768‑차원 벡터를 float32 형식으로 저장한 HNSW 인덱스는 그래프 구조 오버헤드를 제외하고도 약 30 GB의 메모리를 차지합니다. 양자화는 이 문제를 직접 해결합니다.
양자화: 더 작은 인덱스, 더 빠른 검색
양자화는 각 차원을 더 적은 비트로 표현해 벡터 데이터를 압축합니다. 압축 강도에 따라 recall 손실이 발생하지만, 최신 방법은 메모리를 4배에서 32배까지 줄이면서도 대부분의 recall을 유지합니다.
스칼라 양자화
스칼라 양자화는 각 float32 차원을 int8 값으로 매핑합니다. 차원당 4바이트에서 1바이트로 줄어들어 4배 압축이 됩니다. 예를 들어 768‑차원 벡터는 3,072 바이트가 아니라 768 바이트만 차지합니다. 1천만 개 벡터라면 메모리 사용량이 29 GB에서 7.3 GB로 감소합니다.
int8‑양자화된 벡터 간 거리 비교