> For the complete documentation index, see [llms.txt](https://lswkim322.gitbook.io/til/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lswkim322.gitbook.io/til/til-ml/boostcamp/p-stage-mrc/6-scaling-up-with-faiss.md).

# (6강) Scaling up with FAISS

> * scale이 커진 상황에서 효율적인 검색을 수행하기 위한 방법
> * similarity search의 개념 복습
> * approximate search 이해
>   * faiss 활용법
>
> **\[Reference & Further Reading]**
>
> * [FAISS blog](https://engineering.fb.com/2017/03/29/data-infrastructure/faiss-a-library-for-efficient-similarity-search/)
> * [FAISS github](https://github.com/facebookresearch/faiss)
> * [FAISS tutorial](https://github.com/facebookresearch/faiss/tree/master/tutorial/python)
> * [Getting started with Faiss](https://www.pinecone.io/learn/faiss-tutorial/)

## 1. passage retrieval and similarity search

### 1.1. review

![](/files/Qqc9TdZ1xhuyUq4HM5O4)

![](/files/foKJCfyIO0ivUHt5No1i)

실시간으로 유사도를 측정하기 위한 검색 기법에 대해 알아본다

### 1.2. MIPS(Maximum Inner Product Search)

주어진 질문(query) 벡터 q에 대해 passage 벡터 v들 중 가장 질문과 관련된 벡터를  찾아야함 -> 여기서 관련성을 내적(inner product)이 가장 큰 것

4,5 강에서는 brute-force(exhaustive) search를 사용하였다. 이는 저장해둔 모든 sparse/ dense 임베딩에 대해 일일히 내적값을 계산하여 가장 값이 큰 passage를 추출하는 것으로 passage 갯수가 방대해짐에 따라 원하는 속도를 얻을 수 없게 된다.

하여 **passage를 indexing하여 벡터를 저장**하고, 인덱싱된 벡터들 중 질문벡터와 가장 **내적값이 큰 상위 k개의 벡터를 찾는 과정**을 거친다.

$$\underset{v\_i\in V}{argmax} (q^Tv\_i)$$

![](/files/upUXAi4HSBz6fiuQ5iRK)

하지만 인덱싱을 함에도 실제로 검색해야하는 데이터는 훨씬 방대하다. 5백만 개의 위키피티아 데이터 뿐만 아니라 수십억, 조 단위로 커질 수 있다.

### 1.3. Tradeoffs of similarity search

* **Search speed**
  * 쿼리당 유사한 벡터를 k개 찾는데 얼마나 걸리는지
  * Pruning
* **Memory Usage**
  * RAM에 모두 올려둘 수 있으면 빠르지만, 많은 RAM 용량을 요구함
  * Compression
* **Accuracy**
  * brute-force 검색 결과와 얼마나 비슷한지?
  * 속도를 위해 정확도를 포기하는 경우도 있음
  * Exhaustice search

### 1.4. Increasing search space by bigger corpus

Corpus의 크기가 커질수록 탐색공간이 커지고, 검색이 어려워지며, Memory Space가 많이 필요하다. 또한 Sparse Embedding의 경우는 용량 문제가 더 크다고 볼 수 있다.

## 2. Approximation Similarity Search

용량과 속도측면의 문제를 해결하기 위한 방법에 대해 알아본다.

### 2.1. Compression - Scalar Quantization (SQ)

* vector를 압축하여, 하나의 vector가 적은 용량을 차지하도록 한다.
* 이를 통해 압축량은 증가하고, 사용되는 메모리 감소하지만 정보 손실이 증가한다.
* ex) Scalar quantization: 4-byte floating point -> 1-byte unsigned integer로 압축

![](/files/v7D5mW1gfPE4ozkNBW3d)

💭 sparse 대신 dense를 쓰는 것 같은 느낌?

### 2.2. Pruning - Inverted File (IVF)

Search space를 줄여 search 속도 개선 (dataset의 subset만 방문)

-> Clustering + Inverted file을 활용한 search

* Clustering: 전체 vector space를 k개의 cluster로 나눔(k-means clustering)

![](/files/kBs5F3P5ahNazTlK95AL)

* Inverted File (IVF)
  * Vector의 index => inverted list structure
  * 각 cluster의 centroid id 와 해당 cluster의 vector들 이 연결되어있는 형태

💭 단순히 index를 주는 것과 군집형태로 하는 것이 가지는 차이가 무엇인가..?? 결국 해당하는 군집을 찾는다는 개념이면 데이터 양이 커짐에 따라 같은 문제가 발생하는게 아닌가??

![](/files/8itGOVbSK3QKjwCxfSLQ)

* 주어진 query vector에 근접한 centroid 벡터를 찾고,
* 찾은 clusterd의 inverted list내 vector들에 대해 서치를 수행한다.

💭 mrc 할 때보면 우선 passage를 찾고 그 안에서 정답을 찾는것처럼 일단 군집을 찾고 그 안에서 vector를 찾는 개념

## 3. Introduction to FAISS

### 3.1. FAISS

* Facebook에서 만든 속도향상을 위한 오픈소스 라이브러리
* 인덱싱쪽에 도움을 줌

![](/files/VgDxCsWCf3yoZymZGOQF)

### 3.2. 활용방법

#### Train index and map vectors

![](/files/9AQG4Ni88v4msZBRZoe8)

* 데이터 분포를 보고 Cluster를 나누기 위한 학습이 필요함. index.train()
* Scalar Quantization 과정에서도 어느정도로 할 지를 정하기 위해 학습이 필요하다.
* 그 후 cluster안에 vector들을 넣어주게 된다.
  * 보통은 train과 add를 동일한 데이터로 하지만, 데이터양이 너무 크다면 1/40로 하는 경우도 있음.

#### Search based on FAISS index

![](/files/ioccUbnyjaKxf2oqGDRQ)

nprobe: 몇개의 가장 가까운 cluster를 방문하여 search 할것이지

## 4. Scaling up with FAISS

![](/files/PCzHZ6uGKKhWTUYCTWrE)

💭 Gitbook 패치하더니 python code block 쓰는게 안된다.... 화가 난다...

이상은 생략하고 실습 코드로 보기로한다.

## 실습코드 Link

{% embed url="<https://drive.google.com/file/d/1VbfTLUIDAIJaJxEtMI_I9WVlAATj0cdl/view?usp=sharing>" %}


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://lswkim322.gitbook.io/til/til-ml/boostcamp/p-stage-mrc/6-scaling-up-with-faiss.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.