Faiss

페북 (현 메타) 에서 만든 ANN 라이브러리.

ColBERT 논문에서 빠른 retrieval 을 위해 faiss IVFPQ 버전을 사용했다고 한다.

네이버에서는 4ms 도 느리다고 판단하고, 보다 빠른 검색을 위해 Hnswlib 을 사용하는 것 같다.

B) Faiss의 핵심 동작 원리: IVF, PQ Indexing

1. IVF (Inverted File Index): 검색 공간을 줄이는 ‘클러스터링’
   • 개념: 전체 데이터를 k-means와 같은 알고리즘으로 여러 개의 클러스터(Voronoi Cells)로 미리 나눕니다. 비유하자면, 전국 도서관의 모든 책을 찾는 대신 ‘강남구’에 있는 도서관 몇 군데만 찾아보는 것과 같습니다.
   • 동작: 검색 쿼리 벡터가 들어오면, 가장 가까운 몇 개의 클러스터만 선택해서 그 안에서만 검색을 수행합니다.
   • 파라미터: nprobe 라는 파라미터로 검색할 클러스터의 개수를 조절하며, nprobe 가 클수록 정확도는 높아지지만 속도는 느려집니다.
2. PQ (Product Quantization): 벡터를 압축해 메모리를 줄이는 ‘양자화’
   • 개념: 고차원 벡터를 여러 개의 작은 하위 벡터(sub-vector)로 나눈 뒤, 각 하위 벡터를 대표하는 코드(code)로 변환하여 저장합니다. 이는 원본 벡터보다 훨씬 적은 메모리를 차지합니다. 비유하자면, 책의 모든 내용을 저장하는 대신, 각 챕터의 핵심 요약본만 저장하는 것과 같습니다.
   • 장점: 벡터를 압축하여 메모리 사용량을 크게 줄일 수 있고, 압축된 상태에서 거리 계산이 가능하여 검색 속도도 빨라집니다.

C) 트레이드오프 (고려사항)

Faiss를 사용할 때 무조건 좋은가요? 어떤 점을 트레이드오프해야 하나요?

• 속도(Speed) vs 정확도(Accuracy): IVF 인덱스에서 nprobe 값을 높이면 더 많은 클러스터를 탐색하므로 정확도는 올라가지만 검색 속도는 느려집니다. 비즈니스 요구사항에 따라 이 둘 사이의 균형을 맞추는 것이 중요합니다.
• 메모리(Memory) vs 정확도(Accuracy): PQ에서 벡터를 얼마나 압축할지(e.g., m 값)에 따라 메모리 사용량과 정확도가 달라집니다. 압축률이 높을수록 메모리는 절약되지만, 벡터 정보 손실이 커져 정확도는 떨어집니다.
• 인덱싱 시간(Indexing Time): 수억 개의 데이터를 인덱싱하는 데는 상당한 시간이 소요될 수 있습니다. 데이터가 자주 변경된다면, 인덱스를 다시 빌드하는 주기를 어떻게 가져갈지 정책을 수립해야 합니다.
• 데이터 타입: Faiss는 밀집 벡터(Dense Vector)에 최적화되어 있습니다. 희소 벡터(Sparse Vector)가 주를 이루는 데이터에는 적합하지 않을 수 있습니다.

D) PQ

D.1) PQ는 어떤 식으로 Sub-vector를 가져오나요?

D.1.1) Sub-vector를 가져오는 방식

가장 기본적인 방식은 **단순 분할(Simple Splitting)**입니다.

• 예를 들어 128차원의 벡터가 있고, 이를 8개의 sub-vector로 나누기로 결정했다면 (Faiss의 m 파라미터), 그냥 벡터를 8조각으로 자릅니다.
  • 1번째 sub-vector: 1~16차원
  • 2번째 sub-vector: 17~32차원
  • …
  • 8번째 sub-vector: 113~128차원
• 이렇게 생성된 16차원짜리 sub-vector 8개에 대해 각각 k-means 클러스터링을 적용하여 대표 코드(centroid)를 찾고, 원본 sub-vector를 가장 가까운 코드의 ID로 변환합니다. 이것이 Product Quantization(PQ)의 기본 원리입니다.

D.1.2) PCA 같은 차원 축소도 적용할 수 있나요?

네, 적용할 수 있고, 이는 매우 중요한 최적화 기법입니다.

단순히 벡터를 조각내는 것보다 더 좋은 방법은 없을까요? 예를 들어, 중요한 정보가 116차원에 몰려 있고 113128차원에는 별로 없다면, 단순 분할은 정보의 불균형을 야기합니다.

이 문제를 해결하기 위해 **PCA(Principal Component Analysis)**와 같은 차원 축소 기법을 전처리(Pre-transform) 단계로 사용합니다.

• 동작 방식:

  1. 회전(Rotation): 먼저 전체 데이터에 PCA를 적용합니다. PCA는 데이터의 분산이 가장 큰 방향(주성분)으로 축을 회전시키는 역할을 합니다. 이렇게 하면 벡터의 정보(분산)가 앞쪽 차원에 집중됩니다.
  2. 분할(Splitting): 이렇게 회전된 벡터를 위에서 설명한 것처럼 단순 분할합니다.

• 효과:

  • 각 sub-vector가 원본 데이터의 정보를 더 균등하게 나눠 갖게 됩니다.
  • 정보 손실이 줄어들어 양자화(Quantization) 이후에도 원본 벡터의 특징을 더 잘 보존하게 되고, 이는 검색 정확도 향상으로 이어집니다.

• Faiss에서의 구현: Faiss에서는 IndexPreTransform이라는 객체로 이를 구현합니다. 예를 들어 IndexIVFPQ 앞에 PCA 변환을 추가하여 IndexPreTransform(pca_transform, IndexIVFPQ(...)) 와 같은 형태로 사용합니다.

D.2) PQ와 IVF를 같이 사용할 수 있나요?

네, 같이 사용하는 것이 일반적이며, 이 조합이 Faiss의 가장 강력하고 널리 쓰이는 인덱스 중 하나입니다.

이 조합을 IndexIVFPQ 라고 부릅니다. 두 기법은 서로 다른 문제를 해결하여 완벽한 시너지를 냅니다.

• IVF (Inverted File Index): “어디를 찾을 것인가?” 의 문제를 해결합니다.
  • 수백만 개의 데이터 포인트를 모두 비교하는 대신, 쿼리와 가장 가까운 몇 개의 클러스터(nprobe개)만 후보로 선택하여 검색 공간을 크게 줄입니다. (Coarse-level search)
• PQ (Product Quantization): “어떻게 빠르게 비교할 것인가?” 의 문제를 해결합니다.
  • IVF로 좁혀진 클러스터 내의 벡터들을 원본 그대로 저장하는 것이 아니라, 압축된 PQ 코드로 저장합니다.
  • 따라서 ① 메모리 사용량이 획기적으로 줄고, ② 압축된 코드 간의 거리 계산은 원본 벡터 간의 거리 계산보다 훨씬 빠릅니다. (Fine-grained search)

IndexIVFPQ는 IVF로 검색 대상을 수천 개로 줄이고, PQ로 그 수천 개와의 비교를 초고속으로 처리하는, 두 단계의 최적화를 거친 효율적인 방식입니다.

D.3) Query 가 주어졌을때 실제 검색을 수행하는 방법이 궁금합니다

1. 사전 계산 (Query 당 1회): 쿼리 벡터(Q)가 들어오면, Q를 sub-vector로 나눈 뒤 각 sub-vector와 그에 해당하는 모든 센트로이드(centroid)들 간의 거리를 미리 계산해 놓습니다. 이것이 바로 ‘조회 테이블(Lookup Table)’ 입니다.

2. 초고속 근사 (DB 벡터 개수만큼 반복): DB에 있는 수백만 개의 벡터들을 순회할 때는,

   • 각 DB 벡터의 원본 값을 보지 않습니다.
   • 대신 그 벡터가 어떤 센트로이드 ID들로 압축되었는지(PQ Code)만 봅니다.
   • 이 ID를 이용해 1번에서 만든 조회 테이블에서 값을 꺼내와 더하기만 합니다.

이 방식 덕분에, 검색 루프 안에서는 비싼 고차원 벡터 간의 거리 계산이 전혀 없고, 오직 미리 계산된 값을 조회해서 더하는 단순 연산만으로 거리를 근사할 수 있습니다.

이것이 Product Quantization이 극단적으로 빠른 검색 속도를 제공하는 핵심 원리입니다.

D.3.1) Step-by-Step 검색 과정 (예시 포함)

핵심은 비대칭 거리 계산(Asymmetric Distance Computation) 이라는 개념입니다.

• Query Vector (Q): 원본 형태의 고차원 벡터(e.g., 128차원 float)를 그대로 사용합니다. 압축하지 않습니다.
• Database Vector (D): 메모리에 PQ Code (e.g., 8개의 정수 ID) 형태로 압축되어 저장되어 있습니다.

검색은 distance(Q, D)를 계산하는 과정입니다. 하지만 원본 D는 메모리에 없으므로, 우리는 distance(Q, D)를 근사하는 계산을 수행합니다.

사전 준비 (Indexing 단계에서 완료됨):

1. DB 벡터 인코딩: 데이터베이스의 모든 128차원 벡터 D가 8개의 16차원 sub-vector [d1, d2, ..., d8] 로 나뉘고, 각 sub-vector는 가장 가까운 센트로이드(centroid)의 ID로 변환되어 있습니다.

   • 예시: Vector_D의 PQ Code는 [42, 198, 7, 55, 123, 99, 210, 15] 입니다.

2. 센트로이드 저장: 각 sub-vector 공간(1~8번)마다 학습된 256개의 센트로이드(16차원 벡터)는 Faiss가 별도로 저장하고 있습니다. (Codebook)

---

실제 검색 과정 (Query 시점):

어떤 쿼리 벡터 Q가 들어왔고, 우리는 이 Q와 DB에 있는 Vector_D 사이의 거리를 계산하고 싶습니다.

1. 쿼리 벡터 분할 쿼리 벡터 Q도 DB 벡터와 동일한 방식으로 8개의 16차원 sub-vector [q1, q2, ..., q8] 로 자릅니다. Q는 압축되지 않은 원본 float 벡터입니다.

2. (핵심) 거리 근사를 위한 ‘조회 테이블’ 생성 이 단계가 가장 중요합니다. Vector_D의 코드를 보기 전에, 쿼리 Q를 기반으로 미리 계산을 해둡니다.

• q1과 1번 Codebook의 모든 센트로이드(0~255번) 사이의 거리를 모두 계산하여 저장합니다. (dist(q1, C1_0), dist(q1, C1_1), …)
• q2와 2번 Codebook의 모든 센트로이드(0~255번) 사이의 거리를 모두 계산하여 저장합니다. (dist(q2, C2_0), dist(q2, C2_1), …)
• …
• q8과 8번 Codebook의 모든 센트로이드(0~255번) 사이의 거리를 모두 계산하여 저장합니다.

이렇게 하면, 쿼리 1개당 8개 x 256개의 거리 값을 가진 **조회 테이블(Lookup Table)**이 만들어집니다. 이 계산은 DB 벡터 수와 무관하게 딱 한 번만 수행됩니다.

3. DB 벡터와의 거리 ‘근사’ 계산 이제 DB에 저장된 Vector_D의 PQ Code [42, 198, 7, 55, 123, 99, 210, 15]를 가져옵니다.

그리고 방금 만든 조회 테이블에서 값을 찾아 더하기만 하면 됩니다.

• Vector_D의 첫 번째 sub-vector(d1)는 42번 센트로이드로 양자화되었습니다. q1과 d1의 근사 거리는 dist(q1, C1_42) 입니다. 이 값은 조회 테이블의 1번째 줄, 42번째 칸에 이미 계산되어 있습니다.
• d2는 198번 센트로이드로 양자화되었습니다. q2와 d2의 근사 거리는 dist(q2, C2_198) 입니다. 이 값은 조회 테이블의 2번째 줄, 198번째 칸에 있습니다.
• d3는 7번 센트로이드로 양자화되었습니다. q3와 d3의 근사 거리는 dist(q3, C3_7) 입니다. 이 값은 조회 테이블의 3번째 줄, 7번째 칸에 있습니다.
• … 이 과정을 8번 반복합니다.

4. 결과 취합 (Aggregation)

취합은 간단합니다. 위에서 조회한 8개의 거리 값을 모두 더합니다(Summation).

Approx_Dist(Q, D) = dist(q1, C1_42) + dist(q2, C2_198) + dist(q3, C3_7) + ... + dist(q8, C8_15)

이 최종 합계가 Q와 D 사이의 전체 거리 근사치가 됩니다.

Faiss는 DB에 있는 모든 벡터에 대해 이 ‘조회 + 덧셈’ 연산을 초고속으로 반복하여 Q와 가장 가까운 (근사 거리가 가장 작은) 벡터들을 찾아냅니다.

D.3.2) 비유

잘못된 이해: “1번 sub-vector에서 1등 찾고, 2번 sub-vector에서 1등 찾고… 이 1등들을 조합한다.” (X)

올바른 이해: “전체 벡터 D에 대한 거리 점수를 계산하는데, 그 점수를 8개의 파트 점수의 합으로 구한다. 각 파트 점수는 ‘쿼리의 해당 파트’와 ‘DB 벡터가 양자화된 대표값’ 사이의 거리로 계산한다.” (O)

자동차 부품 비유:

• DB의 자동차들: 각 자동차(Vector_D)를 그대로 저장하지 않고, “엔진: A타입, 바퀴: C타입, 핸들: B타입, …” 과 같이 표준 부품 코드로 저장합니다. (PQ Code)

• 찾고 싶은 자동차 (쿼리): 내가 가진 실제 엔진, 실제 바퀴, 실제 핸들(Query Vector Q)을 가져옵니다.

• 유사도 계산:

  1. 내 실제 엔진과 표준 엔진 타입(A, B, C…)들 간의 성능 차이를 모두 계산해 둡니다. (조회 테이블)
  2. 내 실제 바퀴와 표준 바퀴 타입(A, B, C…)들 간의 성능 차이를 모두 계산해 둡니다.
  3. DB의 첫 번째 자동차 코드가 “엔진:A, 바퀴:C, …” 라면, 조회 테이블에서 (내 엔진 vs A타입 차이) + (내 바퀴 vs C타입 차이) + … 를 더해서 총 유사도 점수를 매깁니다.

E) QnA

E.1) 왜 Dense Vector에만 최적화되어 있나요? Sparse Vector가 불리한 이유는 뭔가요?

이는 Faiss의 알고리즘과 계산 방식이 근본적으로 **기하학적 거리(Geometric Distance)**와 고성능 컴퓨팅(HPC) 최적화에 기반하기 때문입니다.

알고리즘적 이유 (기하학적 가정)

• Faiss의 핵심 알고리즘(k-means, 거리 계산)은 벡터를 연속적인 다차원 공간상의 ‘점(point)‘으로 가정합니다.
  • k-means (IVF에서 사용): 여러 점들의 기하학적 중심(centroid)을 찾는 알고리즘입니다. Dense vector는 이런 공간상의 점으로 표현하기 자연스럽습니다.
  • 거리 계산 (PQ에서 사용): 유클리드 거리(L2 distance)나 내적(Inner Product)을 기반으로 점들 사이의 ‘가까움’을 측정합니다.
• Sparse vector는 이러한 기하학적 가정이 잘 맞지 않습니다.
  • 대부분의 값이 0인 Sparse vector는 공간상에 매우 편향되게 분포합니다. 예를 들어, 두 문서 벡터가 단 하나의 공통 단어도 없다면 유클리드 거리는 멀지만, 의미적으로는 관련이 있을 수도 있습니다.
  • ‘중심’이라는 개념이 모호해져 k-means 클러스터링의 효율이 떨어집니다.

계산 및 하드웨어 최적화 이유

• 메모리 구조:
  • Dense Vector: float 값들이 메모리에 연속적으로(contiguous) 저장됩니다. 이는 CPU의 SIMD(Single Instruction, Multiple Data) 연산이나 GPU의 병렬 처리에 극도로 유리한 구조입니다. 한 번의 명령으로 여러 데이터를 동시에 처리할 수 있어 속도가 매우 빠릅니다.
  • Sparse Vector: 0이 아닌 값의 ‘인덱스’와 ‘값’을 쌍으로 저장합니다 (e.g., [(10, 0.5), (1024, 0.8), ...]). 이는 메모리에 비연속적으로 흩어져 있어, 값을 읽을 때마다 **간접적인 메모리 접근(indirect memory access)**이 발생합니다. 이는 캐시 효율을 떨어뜨리고 병렬화에 불리하여 계산 속도를 크게 저하시킵니다.
• 라이브러리 의존성: Faiss는 내부적으로 BLAS, LAPACK 같은 고성능 선형대수 라이브러리를 사용합니다. 이 라이브러리들은 모두 Dense Matrix/Vector 연산에 최적화되어 있습니다.

결과적으로 Sparse vector가 불리한 이유는 ① Faiss의 핵심 알고리즘이 가정하는 기하학적 공간에 잘 부합하지 않고, ② 데이터 구조상 하드웨어 가속과 병렬 처리에 매우 비효율적이기 때문입니다.

Sparse vector 기반의 유사도 검색에는 Faiss 대신, 전통적인 정보 검색(IR)에서 사용하는 역 인덱스(Inverted Index) 구조를 가진 Lucene, Elasticsearch 같은 시스템이 훨씬 더 적합합니다.