Passage Retrieval - Scaling Up

MIPS (Maximum Inner Product Search)

주어진 질문 벡터 q에 대해 passage 벡터 v들 중 가장 질문과 관련된 벡터를 찾아야함

• 관련성은 내적이 가장 큰 것

 

Challenges in MIPS

실제로 검색해야할 데이터는 매우 방대하다 → 모든 문서 임베딩을 보면서 일일히 보면서 검색할 수 없다

 

Tradeoffs of similiarity search

1. search speed → 가지고 있는 문서 양이 많을수록 오래걸림
2. memory usage → RAM에 모두 올려둘 수 있다면 빠르지만, 많은 RAM용량 요구
3. accuracy → 속도를 증가시키려면 정확도 희생

---

Apporximating Similarity Search

• Compression: vector를 압축하여, 하나의 vector가 적은 용량을 차지 (e.g. Scalar quantization: 4-byte fp → 1-byte (8bit) unsigned integer로 압축)
• Pruning: Search space를 줄여 search 속도를 개선 (dataset의 subset만 방문) → clustering + inverted file을 활용한 search
  • Clustering: 전체 vector space를 k개의 kluster로 나눔 (ex. k-means clustering)
  • Inverted File (IVF): vector의 index = inverted list structure → 각 cluster의 centroid id와 해당 cluster의 vector들이 연결되어있는 형태 
  • Searching with clustering and IVF
    • 주어진 query vector에 근접한 centroid vector를 찾음
    • 찾은 cluster의 inverted list 내 vector에 대해 서치 수행

---

FAISS

https://engineering.fb.com/2017/03/29/data-infrastructure/faiss-a-library-for-efficient-similarity-search/

Faiss: A library for efficient similarity search

1. Train index and map vectors (Scalar quantization을 할때만 학습이 필요)
2. Search based on FAISS index 

 

IVF with FAISS

• IVF 인덱스 만들기
• 클러스터링을 통해서 가까운 클러스터 내 벡터들만 비교
• 빠른 검색
• 클러스터 내에서는 여전히 전체 벡터와 거리 비교 (Flat)

IVF-PQ with FAISS

• 벡터 압축 기법 (PQ) 활용하기
• 메모리 사용량을 더 줄일 수 있다