벡터 DB 기본 개념 : ANN 인덱스 (3)

2025.12.09 - [Data Science] - 벡터 DB 검색 기본 개념 : Embedding (2)

벡터 DB 검색 기본 개념 : Embedding (2)

지난 글에서는 벡터 DB의 기본 개념 중 Embedding의 역할과 중요성에 대해서 정리했다. 이번 글에서는 Embedding된 벡터를 어떻게 빨리 찾느냐에 대한 주제로 ANN 인덱스를 다뤄보고자 한다. 

ANN 인덱스란?

• Embedding된 벡터를 어떻게 빠르게 찾을 것인가에 대한 질문에서 ANN 인덱스의 필요성이 등장한다. 
• 벡터 DB의 기본 개념은 Embedding된 벡터를 사용자가 정의한 유사도(혹은 거리)에 따라, 빠르게 범위 내 다른 벡터들과 비교하여, 가장 유사한 것을 찾는 것이다.
• 이때, Embedding된 벡터는 일반적으로 고차원의 값(대략 1024~1536)을 가지고, 벡터의 개수도 많다. 또한, 정보가 늘어날수록 그 개수는 계속 증가한다.
• 어떤 벡터와 다른 벡터 사이의 거리를 계속하는 가장 정확한 방식은 Brute-force 방식이지만, 현실적으로 너무 느리고, 연산 비용(O(N*d) : N: 벡터 개수, d: 벡터 차원)이 크다. (특히, FAISS가 아닌 다른 벡터 DB를 사용하거나, GPU 없이 사용하는 경우)
• 일반적으로 벡터 DB는 유사한 것을 찾는 것에서 끝나기보다는 RAG 같은 활용 단까지 연결되기에 정확함을 조금 포기하고, 더 빠르게 찾는 방식을 선택한다. 
• 이때 HNSW, IVF, PQ와 같은 ANN(Approximate Nearest Neighbor)을 사용한다. 
• 즉, ANN은 현재 벡터와 유사한 벡터를 찾을때 전체와 다 비교하여 완벽한 답을 찾는 것이 아닌, 가까울 것 같은 후보만을 빠르게 비교하여 속도를 향상시킨 방법이다.

 

ANN 인덱스 원리

• HNSW, IVF, PQ 등은 모두 구현 방식은 다르지만, 아래 3가지 중 하나를 줄여 속도를 향상시킨다.
  1. 탐색 범위를 어떻게 줄일것인가?
  2. 유사도에 대한 정확도를 얼마나 포기할 것인가?
  3. 메모리와 속도를 어떻게 트레이드오프 할 것인가?

 

ANN 인덱스 종류

1. HNSW (Hierarchical Navigable Small World)

• 실활용 시 가장 많이 쓰이는 ANN 인덱스 중 하나이다. 
• 벡터 DB에 그래프 개념을 적용한 것으로, 벡터를 비슷한 것끼리 미리 연결한 그래프로 만들고, 그 그래프를 여러 층으로 쌓아, 검색 시 상위 레벨(희소, 노드 적음)에서는 유사한 벡터를 대략적으로 찾고, 아래층(조밀, 노드 많음)을 거치면서 점점 정밀하게 좁혀 유사 벡터를 탐색하는 ANN 인덱스이다.

 

[인덱스 구축]

• 새 벡터를 하나 삽입할때, 이미 만들어진 그래프에서 그 노드의 이웃 후보를 찾고, 그중 일부만 골라 양방향 링크를 만든다. 
• 이때 이웃후보는 마찬가지로 ANN 탐색으로 가까운 후보 집합을 먼저 찾는데, 이때 새 노드의 이웃을 고르기 위해 얼마나 많은 후보를 넓게 볼 것인가를 efConstruction(후보 몇개)이라는 파라미터로 결정한다.
• 이때 efConstruction 개의 벡터 중 삽입되는 벡터와 가장 유사한 벡터들로 이웃을 정하면, 그래프는 한쪽 방향으로만 촘촘해지고, 반대 방향으로 가는 길이 없어, 추후 검색할때 greedy 탐색이 쉽게 끝난다. (즉, 가까운 것을 이웃으로하는 그래프가 좋은 탐색 경로는 아니다.)
• 이때 탐색 경로가 local minimum에 빠지지 않게 하기 위해, 다양성 개념이 등장하는데, efConstruction 개의 벡터 중, 후보 노드 p에 대해 이미 선택된 이웃 s가 p에 더 가깝다면, p를 제거하는 방식으로 다양성을 부여한다. 
• 이렇게 M개(하이퍼파라미터)의 이웃을 가지는 HNSW를 구축한다.
• 과정을 정리하면 다음과 같다.
  1. efConstruction개의 후보 C를 v(삽입 벡터)와 거리 기준으로 정렬
  2. C를 앞에서부터 하나씩 비교
  3. 각 후보 p에 대해:
     1. 이미 선택된 이웃 s와 비교
     2. dist(s,p) < dist(v,p)인 것이 하나라도 있으면, p는 대체 가능(이웃으로 선정 안하더라도 도달 가능)으로 보고 후보 탈락
  4. 대체 불가능하다면 R에 추가
  5. R 크기가 M이 되면 종료
• 조금 더 심화하면, 분포 독립성, 전역 연결성을 위해, HNSW에서 어느 데이터가 어느 층에 들어갈지는 랜덤 확률에 의해 결정되고, 한번 삽입되면 레벨은 절대 바뀌지 않는다. 

 

[인덱스 검색]

• HNSW 검색 과정은 역할이 완전히 다른 두단계로 나뉜다.
• 과정을 나타내면 다음과 같다.
  1. 상위 레벨 : greedy 탐색 (방향 잡기)
  2. 레벨 0 : efSearch 기반 탐색 (정밀 후보 수집)
• 상위 레벨 단에서는 entry point에서 시작하여, 현재 레벨에서 이웃들을 보며, q와 더 가까운 이웃이 있으면 이동하고, 더이상 개선이 없으면 한 레벨 내려간다. 이 과정을 최고 레벨부터 레벨 1까지 반복한다. (즉 현재 레벨에서 가장 쿼리 벡터와 가장 가까운 벡터를 찾아, 레벨을 내린다.)
• 상위 레벨단은 특히 벡터의 개수가 많지 않도록 설계되었기 때문에 검색이 빠르다.
• 레벨 0의 탐색 단위에서는 실제 벡터 검색이 이뤄진다. 이때 efSearch라는 개념이 등장하는데, 최대 몇 개의 후보 동시에 유지하면서 탐색할 것인가에 대한 파라미터이다.
• 조금 더 자세하게, 레벨0에서는 min-heap(가까운 순), max-heap(멀리 있는 것 제거)를 동시에 쓰는데, 더 봐도 top-k가 바뀔 가능성이 없을때 멈춘다. 
• 즉, 탐색 큐의 가장 query 벡터와 가까운 벡터가 efSearch개수의 후보들에 있는 벡터들보다 더 멀다면 더이상 검색하지 않고, 종료한다. 
• 따라서, efSearch가 커지면, 종료 조건이 더 커지고, 검색 성능은 올라가지면, 검색 속도가 떨어진다.

 

2.  IVF(Inverted File Index)

• 전체 벡터를 K개의 Cluster로 미리 구분해놓고, 각 Cluster의 중심을 centroid라 부른다. 이때 생성시에는 각 벡터는 하나의 Cluster에만 소속된다. 
• 검색 시, query 벡터에 대해 centroid 등과 비교하고, 가장 가까운 nprobe 개의 Cluster를 선택하여, 그 Cluster들에 속하는 벡터들 안에서만 탐색하고, 그중 top-k개를 반환하는 형식이다.
• 직관적으로 K-means Clustering 개념을 생각하면 되고, 현재 벡터와 유사한 Cluster의 벡터만 찾기 때문에 검색 속도가 빠르다.
• K-means Clustering의 단점처럼 몇개의 Cluster로 나눌것인지를 하이퍼파라미터로 미리 정해야하기 때문에, 데이터의 삽입과 삭제가 빈번한 벡터들에 대해서 불리하다. 
• IVF에는 두개의 하이퍼파라미터만 생각하면 되는데 아래와 같다.
  • nlist : 클러스터 개수, 클수록 각 클러스터 작아지지만, 검색 범위가 줄어듬. 대신 학습/관리 비용 증가
  • nprobe : 검색 시 볼 클러스터 , 클수록 검색 품질은 좋아지지만 속도가 느려진다. (brute-force와 점점 유사해지기 때문에)

 

 

3.  PQ(Product Quantization)

• HNSW와 IVF가 벡터 DB내 데이터들간의 관계성을 미리 구조화 시켜놔서, 탐색 범위를 줄이는데 목적을 둔다면 PQ는 검색 시 비교하는 비용을 줄이는 데 목적을 둔다. 
• PQ는 벡터 자체를 압축해서 저장하고, 검색 시 진짜 거리 계산 대신 미리 계산된 근사 거리를 빠르게 합산하는 방식이다.
• 엄밀하게 ANN 인덱스가 아니라 거리를 근사하는 방식으로 활용한다. 따라서 HNSW나 IVF와 같이 활용하기도 한다. 
• 고차원의 벡터는 차원이 크기 때문에, 거리 계산 비용이 크고, 메모리 사용량이 크다는 단점이 있다. PQ는 이 문제를 해결하기 위해 벡터를 통째로 비교하지 않고, 나눠서 비교한다.
• PQ의 순서는 아래와 같다. 
  1. 벡터 분할 : d차원을 가진 벡터가 있을 때, m개의 서브 벡터로 분할한다. 서브벡터는 d/m개의 차원을 가진다. [v1, v2, v3, .. vm]
  2. 서브 벡터에 코드 북 학습 : 각 서브 공간마다 k개의 대표 벡터를 학습한다.(k는 일반적으로 256이 된다)
  3. 벡터 저장 : 벡터 하나는 m개의 코드 배열을 가지게 된다. [v1_code, v2_code, v3_code... , vm_code) 각 sub vector마다 몇번째 코드북의 벡터와 가장 유사한지
  4. 벡터 검색 : 벡터 검색 시, query 벡터를 같은 방식으로 분할 후, lookup 테이블을 통해 비슷한 유사 벡터를 지닌 벡터들을 검색한다.
• 따라서, PQ는 엄밀하게 진짜 거리계산이 아닌 대표 벡터로 치환하여 비슷한 모양을 가지는 벡터를 찾는 방식이다. 
• 다만, 유사도 연산이 진짜 거리가 아니기 때문에 IVF나 Rerank 방식을 붙여서 많이 활용한다.

 

 

전체 정리

구분	HNSW	IVF	PQ
장점	조회 정확도 높음	대규모 데이터에 안정적	메모리·연산 비용 최소
단점	메모리 많이 씀	클러스터 품질 의존	정확도 손실 큼
삽입 속도	빠름	느림 (재학습 필요)	매우 느림
삭제 속도	보통	느림	사실상 불가
조회 속도	빠름	빠름	매우 빠름
정확도	높음	중간	낮음 (단독 기준)
사용 환경	정확도 중요하고, 데이터 변화가 빈번	데이터 많고, 구조가 단순, 데이터 변화가 적음	메모리와 속도 최우선, rerank가 별도로 존재할때