FAISS 내부 동작 원리: 10억 개 벡터 유사도 검색

Who Should Read

FAISS나 벡터 DB를 RAG 파이프라인에 사용 중이거나 도입을 고려 중인 백엔드/ML 개발자. 알고리즘 이론보다 '왜 이렇게 설계됐는지'를 직관적으로 이해하고 싶은 사람에게 적합하다.

Core Mechanics

• 이미지, 텍스트, 오디오 같은 데이터는 신경망을 통해 숫자 배열인 '임베딩(embedding)'으로 변환되고, 의미적으로 비슷한 항목들은 이 고차원 공간에서 서로 가까운 위치에 놓인다.
• 가장 단순한 최근접 이웃(NN) 검색은 쿼리 벡터와 DB의 모든 벡터 사이 거리를 전부 계산하는 브루트 포스 방식인데, 10억 개(n=10^9) SIFT 벡터(D=128) 기준으로 512GB RAM이 필요하고 쿼리당 10억 번 거산을 해야 해서 실시간 시스템에서는 사용이 불가능하다.
• FAISS는 이 문제를 두 가지 방향으로 해결한다. 첫째는 IVF(Inverted File Index)로 검색 공간 자체를 줄이는 파티셔닝이고, 둘째는 Product Quantization(PQ)으로 각 벡터를 압축해서 비교 비용을 낮추는 것이다. 실제 프로덕션 시스템은 이 둘을 함께 쓴다.
• IVF는 K-Means 클러스터링으로 벡터 공간을 Voronoi cell(가장 가까운 중심점 기준으로 나눈 영역)로 분할한다. 검색 시에는 쿼리 벡터가 속하는 셀(과 인접 셀 몇 개)에 있는 벡터만 비교하므로, 전체 DB를 다 뒤지지 않아도 된다.
• FAISS의 인덱스 타입은 크게 세 가지다. Flat은 브루트 포스로 정확하지만 느리고, IVF는 파티셔닝으로 속도를 높이되 정확도를 약간 포기하며, HNSW(그래프 기반 인덱스)는 또 다른 근사 검색 방식이다.
• 근사 검색(approximate search)은 정확도를 '조금' 희생하는 대신 속도를 수십~수백 배 높인다. 예를 들어 진짜 1위 벡터 대신 2위 벡터를 반환할 수도 있지만, 실용적인 검색 시스템에서는 이 정도 차이가 허용 가능한 경우가 많다.
• 이 글은 원논문(Johnson, Douze & Jégou, 2017, 'Billion-scale similarity search with GPUs')의 시각적 보조 자료로, 인터랙티브 다이어그램과 벤치마크를 통해 알고리즘의 기하학적 직관을 전달하는 데 초점을 맞췄다. 실제 구현 코드 실험은 Meta의 공식 FAISS 데모 저장소(facebookresearch/faiss/demos)에서 해볼 수 있다.

Evidence

• 원 논문이 동료 검토(peer review)를 거치지 않았다는 점을 지적하는 댓글이 있었고, 요즘 같은 시대에 peer review 없는 논문은 읽기 망설여진다는 개인적 의견을 밝혔다. 다만 FAISS 자체는 특정 유스케이스에서 매우 유용했다고 인정했다.
• Meta가 FAISS 유지보수를 사실상 중단한 것에 의문을 제기하는 댓글이 있었다. faiss-cpu 패키지 외에는 최신 패키지들과 잘 통합이 안 된다는 실용적 문제를 언급하며, 속도 문제인지 우선순위 변화 때문인지 이유가 궁금하다고 했다.
• 인터랙티브 시각화 품질 자체에 대한 호평이 있었다. 알고리즘을 이해하는 데 인터랙티브 다이어그램이 큰 도움이 된다는 긍정적 반응이었다.

How to Apply

• RAG 파이프라인에서 벡터 수가 수백만 개 이상으로 늘어나 검색 속도가 느려진다면, FAISS의 IVF 인덱스를 도입해서 검색 대상 공간을 줄이는 방향을 검토할 수 있다. IVF는 K-Means로 클러스터를 미리 만들고 쿼리 시 관련 클러스터만 탐색하므로 brute-force 대비 큰 속도 이득을 얻을 수 있다.
• 벡터 DB의 메모리 사용량이 문제라면(예: 512차원 벡터 수억 개를 RAM에 올려야 하는 상황), IVF + Product Quantization을 조합한 FAISS 인덱스(IVFFlat 대신 IVFPQ)를 고려할 수 있다. PQ는 벡터를 압축 저장해서 동일한 RAM으로 훨씬 많은 벡터를 담을 수 있게 해준다.
• FAISS를 직접 실험해보고 싶다면 Meta 공식 저장소의 데모 코드(facebookresearch/faiss/demos)를 클론해서 자신의 데이터와 파라미터로 인덱스 타입별 성능을 직접 비교해볼 수 있다. 글에서 제공하는 인터랙티브 벤치마크(Flat vs IVF vs HNSW, 최대 100만 벡터)도 파라미터 튜닝 전 감을 잡는 용도로 활용할 수 있다.
• FAISS의 유지보수 현황(faiss-cpu 외 최신 패키지 통합 미흡)을 고려할 때, 새로운 프로젝트에서는 Weaviate, Qdrant, Milvus 같은 관리형 벡터 DB와 비교 검토하고, FAISS는 라이브러리 수준 직접 통합이 필요한 성능 최적화 케이스에 한정해서 사용하는 것이 현실적이다.

Terminology

관련 논문

• Airbyte Agents – 여러 데이터 소스를 아우르는 Agent용 Context Layer

  Airbyte가 Slack, Salesforce, Linear 등 여러 SaaS 시스템의 데이터를 미리 인덱싱해서 Agent가 API를 일일이 뒤지지 않아도 되는 Context Store를 출시했다. 기존 MCP 방식보다 토큰을 최대 90%까지 줄이는 효과를 확인했다.

• Polynomial Autoencoder가 Transformer Embedding에서 PCA를 능가하는 방법

  PCA 인코더에 2차 다항식 디코더를 붙여서 닫힌 형태(closed-form)로 embedding 압축 품질을 크게 개선하는 기법으로, SGD 없이 numpy만으로 구현 가능하다.

• 비정형 Recall에서 Schema 기반 Memory로: 반복적 Schema-Aware Extraction을 통한 신뢰할 수 있는 AI Memory

  RAG 스타일 텍스트 검색 대신 Schema로 정의된 구조화 레코드에 메모리를 저장하면, 정확한 사실 조회·상태 추적·집계 쿼리에서 압도적으로 높은 정확도를 얻을 수 있다.

• Atomic – Local-first, AI 기반 개인 지식 그래프 앱

  노트, 웹 클립, RSS 피드를 자동으로 임베딩·태깅·연결해주는 오픈소스 개인 지식 그래프 앱으로, 시맨틱 검색과 LLM 기반 위키 합성, MCP 통합까지 지원한다.

• RAG 대신 Virtual Filesystem으로 AI 문서 어시스턴트 만든 이야기

  Mintlify의 ChromaFs(Chroma DB 위의 UNIX 명령어 흉내 가상 파일시스템)가 RAG 청킹 한계를 극복해 세션 부팅 시간을 46초에서 100ms로 단축한다.

• Chroma Context-1: Self-Editing 기능을 갖춘 검색 에이전트 학습 방법

  Chroma의 20B 파라미터 agentic search 모델이 프론티어급 LLM 수준의 검색 성능을 1/10의 비용과 10배 빠른 속도로 달성한다.

Related Resources

• Inside FAISS: Billion-Scale Similarity Search (원문)
• Johnson, Douze & Jégou (2017): Billion-scale similarity search with GPUs (원논문)
• Meta FAISS 공식 GitHub 데모