관련 포스트벡터 검색 임베딩 추천 시스템 검색 증강 생성

근사 최근접 이웃 탐색(Approximate Nearest Neighbor)

•

2026년 11월 08일 발행•2026년 11월 08일 수정

요약

정확도를 일부 양보하는 대신 고차원 벡터 집합에서 가까운 이웃을 빠르게 찾는 탐색 기법

중급

벡터 거리 척도와 임베딩 개념을 이해하고, 색인 구조별 재현율·지연·메모리 절충을 판단할 수 있어야 한다.

태그

벡터 검색 임베딩 추천 시스템 검색 증강 생성

#개념

근사 최근접 이웃 탐색(Approximate Nearest Neighbor Search, ANN)은 고차원 벡터 집합에서 질의 벡터와 가장 가까운 벡터를 정확히 찾는 대신, 일부 정확도를 양보하고 훨씬 빠르게 찾는 탐색 기법이다. 임베딩 기반 검색, 추천, 검색 증강 생성처럼 수백만에서 수십억 개의 벡터를 밀리초 단위로 조회해야 하는 시스템의 핵심 구성 요소다.

정확한 k-최근접 이웃(k-Nearest Neighbors, kNN) 탐색은 질의마다 $N$개의 $d$차원 벡터와 거리를 모두 계산하므로 $O(Nd)$의 비용이 든다. 1억 개의 768차원 벡터라면 질의 하나에 약 770억 번의 곱셈이 필요하고, 초당 수천 건의 요청을 처리해야 하는 서비스에서는 감당하기 어렵다. 저차원에서 잘 동작하던 KD-트리 같은 공간 분할 구조도 차원의 저주(Curse of Dimensionality) 때문에 고차원에서는 대부분의 노드를 방문하게 되어 사실상 전수 탐색과 비슷해진다.

근사 탐색은 "가장 가까운 이웃 몇 개를 놓쳐도 결과 품질에 큰 차이가 없다"는 실무적 관찰에 기대어 이 문제를 푼다. 색인을 미리 구축해 탐색 공간을 좁히고, 그 대가로 일부 참 이웃을 놓칠 수 있음을 받아들인다. 따라서 근사 탐색의 설계는 하나의 최적점이 아니라 여러 지표 사이의 절충으로 이해해야 하며, 주요 절충 축은 다음과 같다.

근사 탐색의 절충 축

재현율(Recall): 정확한 탐색 결과 가운데 근사 탐색이 찾아낸 비율로, 결과 품질을 나타낸다.
지연 시간과 처리량: 질의당 응답 시간과 초당 처리 질의 수(QPS)로, 탐색 범위를 넓힐수록 재현율은 오르지만 지연 시간도 늘어난다.
메모리 사용량: 원본 벡터와 색인 구조를 메모리에 올리는 비용으로, 압축을 강하게 할수록 메모리는 줄지만 재현율이 떨어진다.
색인 구축과 갱신 비용: 색인을 만드는 시간과 벡터 추가·삭제를 반영하는 난이도로, 데이터가 자주 바뀌는 서비스에서 중요하다.

근사 탐색 알고리즘은 탐색 공간을 줄이는 방식에 따라 크게 네 계열로 나뉜다. 실제 시스템에서는 여러 계열을 결합해 쓰는 경우가 많다.

근사 탐색 알고리즘 계열

해싱 기반: 지역 민감 해싱(Locality-Sensitive Hashing, LSH)은 가까운 벡터가 같은 버킷에 들어갈 확률이 높은 해시 함수를 여러 개 사용해 후보를 추린다. 이론적 보장이 명확하지만 높은 재현율을 얻으려면 해시 테이블이 많이 필요하다.
트리 기반: 공간을 재귀적으로 분할하는 방식으로, Annoy는 무작위 초평면으로 공간을 나누는 트리를 여러 개 만들어 고차원에서의 KD-트리 한계를 완화한다.
그래프 기반: 가까운 벡터끼리 간선으로 연결한 근접 그래프를 만들고 탐욕적으로 이동하며 탐색한다. HNSW, NSG, DiskANN이 대표적이며 현재 재현율 대비 속도가 가장 우수한 계열로 평가된다.
양자화 기반: 벡터를 짧은 코드로 압축해 메모리와 거리 계산 비용을 줄인다. PQ, IVF-PQ, ScaNN이 대표적이다.

계층적 탐색 가능 작은 세상 그래프(Hierarchical Navigable Small World, HNSW)는 Malkov와 Yashunin이 제안한 그래프 기반 기법으로, 상위 층일수록 노드가 적고 간선이 긴 다층 그래프를 구성한다. 탐색은 최상위 층에서 시작해 질의에 가까워지는 방향으로 탐욕적으로 이동한 뒤 아래 층으로 내려가며 정밀하게 좁힌다. 노드당 간선 수 M, 구축 시 후보 크기 efConstruction, 탐색 시 후보 크기 efSearch가 재현율과 속도, 메모리를 조절하는 핵심 파라미터다.

HNSW는 모든 벡터와 그래프를 메모리에 올려야 하므로 데이터가 수십억 개 규모로 커지면 비용이 급격히 늘어난다. NSG는 그래프의 차수를 줄여 메모리 효율을 높였고, DiskANN은 Vamana라는 그래프 구축 방식과 압축 벡터를 결합해 대부분의 데이터를 SSD에 두고도 높은 재현율과 낮은 지연을 유지하도록 설계되었다.

곱 양자화(Product Quantization, PQ)는 Jégou, Douze, Schmid(2011)가 제안한 압축 기법으로, $d$차원 벡터를 $m$개의 부분 벡터로 나누고 각 부분 공간마다 k-평균으로 학습한 256개의 중심점 중 가장 가까운 것의 번호로 표현한다. 128차원 float32 벡터는 512바이트지만 $m=16$이면 16바이트 코드로 압축된다. 질의와 중심점 사이의 거리를 미리 표로 계산해 두고 코드별로 합산하는 비대칭 거리 계산(Asymmetric Distance Computation)으로 압축된 상태에서도 빠르게 거리를 근사한다.

역파일 색인(Inverted File Index, IVF)은 k-평균으로 벡터 공간을 nlist개의 셀로 나누고, 질의와 가까운 nprobe개의 셀만 탐색한다. IVF와 PQ를 결합한 IVF-PQ는 셀 중심으로부터의 잔차를 PQ로 압축해 대규모 데이터를 적은 메모리로 다루는 표준 구성이다. 구글의 ScaNN은 내적 검색에서 중요한 방향의 오차를 더 강하게 줄이는 이방성 양자화(anisotropic quantization)로 같은 압축률에서 더 높은 재현율을 얻는다.

거리 척도의 선택도 중요하다. 유클리드 거리(L2), 내적(Inner Product), 코사인 유사도(Cosine Similarity)가 주로 쓰이며, 벡터를 L2 정규화하면 코사인 유사도 검색은 내적 검색과 같아진다. 추천 모델의 사용자·아이템 임베딩처럼 점수가 내적으로 정의되는 경우를 최대 내적 탐색(Maximum Inner Product Search, MIPS)이라 하며, 색인이 지원하는 척도와 모델 학습에 쓴 척도를 일치시켜야 품질 저하를 막을 수 있다.

근사 탐색의 성능은 하나의 숫자가 아니라 곡선으로 비교해야 한다. 주요 평가 방법은 다음과 같다.

근사 탐색 평가 지표

Recall@k: 근사 탐색이 반환한 상위 $k$개 집합 $R$과 정확한 상위 $k$개 집합 $G$에 대해 $|R \cap G| / k$로 계산한다.
QPS와 꼬리 지연 시간: 초당 처리 질의 수와 p95·p99 지연 시간으로, 서비스 수준 목표를 만족하는지 판단한다.
메모리와 구축 시간: 색인 크기와 구축·재구축에 걸리는 시간으로, 운영 비용과 데이터 갱신 주기를 결정한다.
재현율-QPS 곡선: 탐색 파라미터를 바꿔 가며 재현율과 QPS를 함께 그린 곡선으로, ann-benchmarks(Aumüller 외, 2019)가 이 방식으로 여러 라이브러리를 공개 데이터셋에서 비교한다.

실제 서비스에서는 "재고가 있는 상품 중에서", "특정 카테고리 안에서"처럼 속성 조건을 함께 거는 필터링 검색(Filtered Search)이 자주 필요하다. 근사 탐색 후 조건을 거르는 사후 필터링은 조건을 만족하는 결과가 부족해질 수 있고, 조건으로 먼저 거른 뒤 탐색하는 사전 필터링은 그래프 연결성이 깨져 재현율이 떨어질 수 있다. 조건의 선택도에 따라 전수 탐색으로 전환하거나 필터를 그래프 탐색 중에 반영하는 방식이 쓰인다.

널리 쓰이는 오픈소스 라이브러리는 다음과 같다.

근사 탐색 라이브러리

Faiss: 메타가 개발한 밀집 벡터 유사도 검색 라이브러리로, IVF·PQ·HNSW 등 다양한 색인과 GPU 가속을 지원한다.
hnswlib: HNSW 저자들이 공개한 헤더 전용 C++·파이썬 구현으로, 가볍고 빠르며 증분 추가를 지원한다.
Annoy: 스포티파이가 개발한 무작위 투영 트리 기반 라이브러리로, 색인을 파일로 저장해 메모리 매핑으로 여러 프로세스가 공유할 수 있다.
ScaNN: 구글 리서치가 공개한 라이브러리로, 이방성 양자화를 이용해 내적 검색에서 높은 성능을 낸다.

근사 탐색은 벡터 데이터베이스(Vector Database)의 핵심 엔진이며, 검색 증강 생성에서 질문과 관련된 문서 조각을 찾는 단계, 이미지·상품 유사도 검색, 중복 콘텐츠 탐지 등에 쓰인다. 추천 시스템에서는 투 타워 모델이 만든 사용자 임베딩으로 수백만 개의 아이템 임베딩을 탐색해 수백 개의 후보를 뽑는 후보 생성 단계에 쓰이며, 이후 정교한 랭킹 모델이 후보를 재정렬한다.

운영 시에는 몇 가지를 함께 고려해야 한다. 그래프 색인은 삭제를 표시만 하고 실제 정리는 재구축 시 수행하는 경우가 많아 갱신이 잦으면 주기적 재색인이 필요하다. 또한 탐색 파라미터는 실제 질의 분포에서 정확한 kNN 결과를 정답으로 삼아 Recall@k와 지연 시간을 함께 측정하며 조정해야 하며, 압축 색인을 쓸 때는 후보를 넉넉히 뽑은 뒤 원본 벡터로 거리를 다시 계산하는 재순위화로 정확도를 보완한다.

#관련 용어

임베딩

데이터를 의미를 보존하는 저차원 연속 벡터로 표현한 것

코사인 유사도

두 벡터 사이 각도의 코사인 값으로 방향의 유사성을 측정하는 척도

차원의 저주

차원이 높아질수록 데이터가 희소해지고 거리 기반 방법의 효율이 떨어지는 현상

곱 양자화(PQ)

벡터를 부분 벡터로 나누어 각 부분을 중심점 번호로 압축하는 양자화 기법

벡터 데이터베이스

벡터의 저장과 유사도 검색에 특화된 데이터베이스

#직무 연관도

Data Analyst낮음

유사 상품·유사 사용자 탐색 결과를 해석하고 활용하는 데 필요한 배경 지식

Data Scientist높음

임베딩 모델의 검색 품질 평가와 후보 생성 모델 설계에 활용

Data Engineer밀접

대규모 벡터 색인의 구축·튜닝·운영과 지연 시간 목표 달성에 필수

#사용 사례

전자상거래인터넷 서비스미디어금융통신

개요

근사 최근접 이웃 탐색은 대규모 임베딩을 실시간으로 조회해야 하는 서비스에 쓰인다. 전자상거래와 미디어 분야에서는 추천 후보 생성과 유사 상품·콘텐츠 검색에, 인터넷 서비스에서는 의미 기반 검색과 검색 증강 생성에, 금융과 통신 분야에서는 이상 거래·이상 패턴과 유사한 사례를 빠르게 찾는 데 활용된다.

사례

전자상거래 추천 시스템에서 투 타워 모델의 사용자 임베딩으로 수백만 개 상품 임베딩을 HNSW 색인에서 탐색해 수십 밀리초 안에 상위 수백 개 후보를 생성하고, 랭킹 모델로 재정렬