Elamur Research
☰
home / papers / 2024 / The Faiss library

The Faiss library

Written for the Research library (claude-opus-5-5) from the paper text. Original — arxiv.org/pdf/2401.08281

Summary

Modern AI systems represent text, images and other media as embedding vectors, so they need fast ways to find the nearest neighbours among very large numbers of vectors. This paper describes Faiss, Meta's open-source library for approximate nearest neighbor search (ANNS). Faiss is written in C++ with no external dependencies, has a full Python wrapper, and runs on both CPUs and GPUs. It is not a single algorithm. Instead it provides a toolbox of index types that combine preprocessing, vector compression (quantization) and non-exhaustive search such as IVF partitioning and HNSW graphs. The authors set out the trade-offs between speed, memory, accuracy and build time, and explain the library's design. They benchmark it on BIGANN, Deep1B and a new 768-dimensional Contriever dataset made from English Wikipedia passages. Case studies cover trillion-scale indexing, text retrieval and filtered search. The paper shows that no single index is best: the right choice depends on the constraints of each application. Faiss matters because many vector databases build on it, and it is a reference baseline for retrieval and RAG systems.

Key points

  • Faiss has been public since 2017. The paper reports about 37k GitHub stars, more than 5,200 citations of its earlier GPU paper and around 6M package downloads. Milvus (through its Knowhere library) uses Faiss as one of its core engines, and Pinecone first built on it.
  • The scope is deliberately narrow. Faiss does not extract embeddings, does not run as a service and is not a database: it has no sharding, transactions or concurrent writes.
  • Trillion-scale example: 1.5 trillion 144-dimensional vectors are compressed to 54 bytes each with PCAR72,SQ6, using an HNSW coarse quantizer with 10M centroids. The 83 TiB index is memory-mapped as OnDiskInvertedLists, and searches take about 1 s per query when spread over 20 intermediate servers.
  • Faiss was a baseline in the big-ANN challenges, including the 2023 filtered-search track. A pre-filter there using bit signatures stored in unused ID bits removes up to about 82% of the costly metadata checks (best setting: p = 0.1).

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: AI & machine learning

Cited by

366 papers of our library cite it (of the 140673 whose bibliographies we read); 3 of them have a page here, 363 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2401.08281 · arXiv 2401.08281

@misc{douze2024faiss,
  title = {{The Faiss library}},
  author = {Douze, Matthijs and Guzhva, Alexandr and Deng, Chengqi and Johnson, Jeff and Szilvasy, Gergely and Mazare, Pierre-Emmanuel and Lomeli, Maria and Hosseini, Lucas and Jegou, Herve},
  year = {2024},
  doi = {10.48550/arxiv.2401.08281},
  eprint = {2401.08281},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2401.08281}
}

References

18 references, 1 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Kenza Amara, Matthijs Douze, Alexandre Sablayrolles, and Hervé Jégou. Nearest neighbor search with compact codes: A decoder perspective. In ICMR, 2022. find
  2. Alexandr Andoni and Ilya Razenshteyn. Optimal data-dependent hashing for approximate near neighbors. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 793–801, 2015. find
  3. Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. Ann-benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems, 87:101374, 2020. find
  4. Artem Babenko and Victor Lempitsky. Additive quantization for extreme vector compression. In Conference on Computer Vision and Pattern Recognition, 2014. find
  5. Artem Babenko and Victor Lempitsky. Tree quantization for large-scale similarity search and classification. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4240–4248, 2015. find
  6. Artem Babenko and Victor Lempitsky. Efficient indexing of billion-scale datasets of deep descriptors. In Conference on Computer Vision and Pattern Recognition, 2016. find
  7. Yoram Bachrach, Yehuda Finkelstein, Ran Gilad-Bachrach, Liran Katzir, Noam Koenigstein, Nir Nice, and Ulrich Paquet. Speeding up the xbox recommender system using a euclidean transformation for inner-product spaces. In Proceedings of the 8th ACM Conference on Recommender systems, pages 257–264, 2014… find
  8. Dmitry Baranchuk, Matthijs Douze, Yash Upadhyay, and I Zeki Yalniz. Dedrift: Robust similarity search under content drift. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 11026–11035, 2023. find
  9. Loı̈c Barrault, Yu-An Chung, Mariano Cora Meglioli, David Dale, Ning Dong, Paul-Ambroise Duquenne, Hady Elsahar, Hongyu Gong, Kevin Heffernan, John Hoffman, et al. Seamlessm4t-massively multilingual & multimodal machine translation. arXiv preprint arXiv:2308.11596, 2023. Throughout the years, Faiss… find our card
  10. Piotr Bojanowski, Edouard Grave, Armand ing techniques from research. We continue doing this Joulin, and Tomas Mikolov. Enriching word vec-to include novel quantization techniques [39], better tors with subword information. Transactions of the association for computational linguistics, 5:135–146, [2… find
  11. Leonid Boytsov, David Novak, Yury Malkov, and Advances in Neural Information Processing Systems, Eric Nyberg. Off the beaten path: Let’s replace 35:15489–15501, 2022. term-based retrieval with k-nn search. In Proceedings of the 25th ACM international on conference [22] Mayur Datar, Nicole Immorlica,… — [arXiv:2301.10622](https://arxiv.org/abs/2301.10622) find
  12. Zhangjie Cao, Mingsheng Long, Jianmin Wang, Pattern Recognition (CVPR), June 2019. and Philip S. Yu. Hashnet: Deep learning to hash by continuation. In Proceedings of the IEEE Inter- [24] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep national Conference… find
  13. Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for [25] Inderjit S Dhillon and Dharmendra S Modha. Concept decompositions for large sparse text unsupervised learning of visual features. In Pro-data using clustering. Machine learning, 42:143– ceedings of the Euro… find
  14. Mathilde Caron, Hugo Touvron, Ishan Misra, [26] Wei Dong, Charikar Moses, and Kai Li. Efficient k-nearest neighbor graph construction for Hervé Jégou, Julien Mairal, Piotr Bojanowski, generic similarity measures. In Proceedings of the and Armand Joulin. Emerging properties in self-20th internation… find
  15. Moses Charikar. Similarity estimation techniques conference on Multimedia, pages 687–690, 2014. from rounding algorithms. In Proc. ACM symp. Theory of computing, 2002. [28] Matthijs Douze, Hervé Jégou, and Florent Perronnin. Polysemous codes. In European Confer-[17] Meng Chen, Kai Zhang, Zhenying… — [arXiv:2408.08933](https://arxiv.org/abs/2408.08933) find
  16. Ting Chen, Simon Kornblith, Mohammad pattern recognition, pages 3646–3654, 2018. Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual [30] Matthijs Douze, Giorgos Tolias, Ed Pizzi, Zoë representations. In Proceedings of the 37th Papakipos, Lowik Chanussot, Filip Raden… — [arXiv:2106.09672](https://arxiv.org/abs/2106.09672) find
  17. Yongjian Chen, Tao Guan, and Cheng Wang. Approximate nearest neighbor search by residual [31] Paul-Ambroise Duquenne, Holger Schwenk, and vector quantization. Sensors, 10(12):11259–11273, Benoı̂t Sagot. Sentence-level multimodal and 2010. language-agnostic representations. arXiv preprint arXiv:2308.… find
  18. Zhuoming Chen, Ranajoy Sadhukhan, Zihao Ye, Yang Zhou, Jianyu Zhang, Niklas Nolte, Yuan- [32] Cong Fu, Chao Xiang, Changxu Wang, and Deng dong Tian, Matthijs Douze, Leon Bottou, Zhihao Cai. Fast approximate nearest neighbor search Jia, et al. Magicpig: Lsh sampling for efficient llm with the navigat… find