PaperlayerView exact revision on arXiv

Source-linked AI summary

The Faiss library

Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, Hervé Jégou

arXiv:2401.08281v4cs.LGcs.CVcs.SE

TL;DR

Growing collections of embedding vectors require scalable similarity search, but selecting among indexing strategies involves trade-offs and constraints. This paper presents Faiss as a flexible ANNS toolkit, explains its design and optimization principles, and reviews benchmarks and applications. Faiss provides a broad set of index types and components whose suitable choice depends on the problem’s constraints, while remaining limited to local indexing functions rather than a full database system.

  • Problem

    Growing embedding collections make scalable vector similarity search important, while approximate-nearest-neighbor indexing involves trade-offs among constraints.

  • Method

    The paper describes Faiss’s indexing structures, vector compression, non-exhaustive search, optimization settings, interfaces, benchmarks, and selected applications.

  • Results

    Faiss offers a dozen index types and a toolbox of chained components, with the optimal index usually depending on the problem’s constraints.

  • Takeaways & Limitations

    Faiss provides a broad vector-search toolkit used across applications including trillion-scale indexing, text retrieval, data mining, and content moderation.

  • Takeaways & Limitations

    Faiss does not extract features, operate as a service, or provide database capabilities such as sharding, transactions, or query optimization.

Abstract

from arXiv · show

Vector databases typically manage large collections of embedding vectors. Currently, AI applications are growing rapidly, and so is the number of embeddings that need to be stored and indexed. The Faiss library is dedicated to vector similarity search, a core functionality of vector databases. Faiss is a toolkit of indexing methods and related primitives used to search, cluster, compress and transform vectors. This paper describes the trade-off space of vector search and the design principles of Faiss in terms of structure, approach to optimization and interfacing. We benchmark key features of the library and discuss a few selected applications to highlight its broad applicability.

1 Introduction

Faiss addresses the growing need to store and search embedding vectors by providing a flexible approximate-nearest-neighbor search toolbox. The paper presents its design principles, trade-offs, applications, and scope as an indexing library rather than a feature extractor, service, or database.

  • Motivation: Embeddings represent media items as vectors whose locality encodes semantics, enabling neighborhood search to implement similarity search between media items.The embedding extractor aligns distances with the task, while the index searches those vectors according to the agreed distance metric.
  • Motivation: Similarity search supports applications such as k-nearest-neighbor classification, which can incorporate new training samples more efficiently than retraining a classification neural network.This use of similarity search has contributed to increased adoption of vector storage and search in database management systems.
  • Faiss design: Faiss is a C++ library with a Python wrapper that offers multiple index implementations and chains components such as preprocessing, compression, and non-exhaustive search.The paper reports a choice among a dozen index types, with the optimal choice usually depending on the problem’s constraints.
  • Scope: Faiss indexes previously extracted embeddings and runs locally, but does not provide feature extraction, concurrent database access, load balancing, sharding, transactions, or query optimization.The paper intentionally limits its scope to ANNS algorithmic implementation.
  • Capabilities: The library supports nearest-neighbor variants, range search, parallel batch queries, multiple distance metrics, and CPU or GPU execution.An index stores progressively added database vectors and returns vectors closest to a submitted query under the selected metric.
  • Faiss design: Faiss exposes design principles for trading off vector-search constraints through vector compression and non-exhaustive search, while reviewing applications including trillion-scale indexing, text retrieval, data mining, and content moderation.Its structure and interfaces are designed to support both simple scripts and use as a DBMS building block.

2 Related work

Related work spans compressed codes, partitioning, graph-based indexing, theoretical analyses, benchmarks, datasets, and software packages. Faiss encompasses this broad algorithmic landscape while using experimental comparisons to evaluate approximate search quality and speed.

  • Compression: Compression methods include binary sketches and quantization, with compact codes supporting storage and search of very large media databases without retaining original embeddings.Cosine sketches use Hamming distance as an estimator of cosine similarity, while product quantization is described as an alternative to binary codes.
  • Partitioning: Data-aware partitioning methods include kd-trees and hierarchical k-means, often combined with compressed representations for very large-scale settings.The paper distinguishes these methods from LSH scenarios based on multiple partitions, which it does not consider because performance is generally inferior to learnt partitions.
  • Graph methods: Graph-based approximate-nearest-neighbor methods emerged as an alternative to space partitioning after NN-descent, with HNSW notably implemented in HNSWlib for medium-sized datasets.HNSW is identified as currently the most popular indexing method in this related-work discussion.
  • Software packages: Faiss-related software spans comprehensive vector-search packages and optimized libraries, including FLANN, Yael, NMSlib, HNSWlib, SCANN, and DiskANN.The paper presents Faiss as complementing earlier work focused on GPU implementations by describing the library as a whole.
  • Evaluation: Approximate-search quality is typically evaluated experimentally because execution speed matters and theoretical objectives may only proxy the nearest-neighbor problem.ANN-benchmarks compares about 50 ANNS implementations, while the big-ANN challenge introduced datasets containing 1 billion vectors each.
  • Datasets: The paper uses BIGANN SIFT features, Deep1B neural image features, and a newly introduced dataset of 768-dimensional Contriever text embeddings compared with inner-product similarity.Its datasets contain 10k query vectors and 20M to 350M training vectors, and the work does not address out-of-distribution data.

3 Performance axes of a vector search library

Faiss vector search balances accuracy against computational and storage resources across exact and approximate search settings. Its design exposes distance metrics, accuracy measures, resource constraints, and Pareto-optimal hyperparameter choices for navigating these trade-offs.

  • Search operations and metrics: Faiss supports nearest-neighbor, k-nearest-neighbor, and range search over database vectors using configurable distance metrics.Its common metrics include L2 distance, cosine similarity, and inner-product similarity; preprocessing can map some metrics to others.
  • Exact versus approximate search: Approximate nearest-neighbor search trades imperfect results for faster or more compact indexed search when small distance differences are not application-critical.Unlike exact search over a plain matrix, ANNS may preprocess the database into an index.
  • Accuracy metrics: Accuracy is evaluated against exact-search results using n-recall@k, precision-recall metrics for range search, and reconstruction MSE for vector encoder-decoder pairs.For range search, sweeping the approximate threshold produces a precision-recall curve whose area can be summarized by mean average precision.
  • Resource metrics: Search time, memory, index-building time, and I/O operations form the main resource axes, with their importance depending on the deployment setting.Memory includes training and per-vector overhead, while build time separates training from vector-addition time.
  • Exploring search-time settings: Faiss prunes search-time parameter settings to Pareto-optimal operating points, reducing 5808 combined settings to 398 experiments and 87 optimal settings.The pruning retains settings that are fastest for a given accuracy or most accurate for a given speed.

4 Compression levels

Faiss compresses vectors through codecs that trade memory, encoding cost, and accuracy, while supporting approximate distance computation directly on compressed representations. Its codec hierarchy increases flexibility and accuracy but also increases resource requirements, producing different practical trade-offs across quantizer families.

  • Codec representation and search: Faiss codecs map vectors to compact integer codes and decode them into approximations, enabling compressed storage and approximate search.Most indexes use asymmetric distance computation because retaining uncompressed queries avoids query-side accuracy loss; distances can often be computed without decompression.
  • Single-codebook quantization: K-means is highly accurate, but its memory usage and encoding complexity grow exponentially, making it impractical beyond roughly 3-byte codes or 16M centroids.
  • Multi-codebook quantization: Product quantization splits vectors into sub-vectors encoded independently, while additive quantizers sum reconstructions from multiple codebooks and require heuristic encoding because optimal encoding is NP-hard.
  • Quantizer hierarchy: The quantizer hierarchy increases reproduction-value flexibility and accuracy, but each higher level has greater capacity and consumes more training time or storage overhead.The hierarchy progresses from binary and scalar quantization through product, product-additive, and general additive quantization.
  • Transformations: PCA can reduce dimensionality before quantization, while rotations preserve cosine, L2, and inner-product comparisons and may improve quantizer effectiveness.PCA is often beneficial for large vectors because k-means quantizers are more likely to reach local minima in high-dimensional spaces.
  • Benchmark trade-offs: Additive quantizers favor small codes, product-additive variants become beneficial at larger code sizes, and scalar quantizers remain fast for very long codes.LSQ is more accurate than RQ for small codes but does not scale well to longer codes; PLSQ and PRQ become more competitive for larger memory budgets and are faster on smaller vectors.

5 Non-exhaustive search

Faiss accelerates large-scale vector search by pruning candidate vectors through inverted files or graph-based indexes, while trading search speed, memory, build cost, and accuracy. Its benchmarks show that these trade-offs depend on dataset size, accuracy targets, quantization choices, and data distribution.

  • Non-exhaustive search focuses computation on a subset of database vectors likely to contain the results, which is central for datasets larger than roughly N=10k.
  • Faiss implements inverted-file and graph-based approaches with different memory-versus-speed trade-offs.
  • Inverted files: IVF clusters vectors into KIVF inverted lists and searches only PIVF selected clusters, reducing the database portion examined at query time.
  • Inverted files: KIVF has a theoretical minimum at KIVF = √PIVFN, but practical settings must account for accuracy, list imbalance, and non-exhaustive coarse quantization.
  • Inverted files: For larger databases, increasing KIVF can help; with HNSW coarse quantization, larger KIVF becomes more useful because coarse quantization is relatively cheap.
  • Inverted files: Residual encoding benefits shorter codes, while larger codes gain less from residual information; higher KIVF also improves residual-quantizer accuracy.
  • Inverted files: For MIPS, IP assignment reduces imbalance on Contriever1M, and spherical k-means reduces it further.
  • Graph based: NSG generally offers better speed-accuracy trade-offs than HNSW, but requires longer graph construction and is difficult to extend after its first batch.

6 Database operations

Faiss supports evolving indexes, identifier management, and filtered search, while exposing trade-offs between flexibility, efficiency, and exactness. Data-distribution changes and graph-index mutation impose important operational boundaries.

  • Index updates: Faiss supports batch-oriented experiments as well as indexes that evolve through vector additions, removals, updates, metadata-aware searches, and external-storage interfaces.Specific APIs support dynamic operations and fine-grained external-storage control.
  • Identifiers: Arbitrary 63-bit identifiers are supported, but Faiss does not store arbitrary metadata with vectors.Sequential identifiers are also available, while identifier-based access may require auxiliary mappings or scans depending on the index.
  • Index updates: Techniques fitted to the data distribution, including IVF and PQ compression, become less efficient after significant vector-distribution changes unless the index structure is explicitly updated.This is an operational limitation for additions, removals, and updates that substantially alter the indexed distribution.
  • Index updates: IVF supports user-provided identifiers and optional DirectMap mappings for lookup, removal, and updates, whereas HNSW lacks suppression and mutation support and NSG cannot add vectors incrementally.Graph mutation support may require rebuilding heuristics that are described as suboptimal for indexing.
  • Filtered search: Vector-first filtering uses an IDSelector predicate, while metadata-first filtering compares only a selected subset with brute force, preserving exact results when that subset is small.Choosing between the approaches depends on subset size; the subset can be estimated from metadata-list sizes and empirical word probabilities.
  • Filtered search: Bit signatures accelerate bag-of-words filtering by pre-filtering candidates with a few register-level instructions before the full predicate, and the best tested setting avoided the full predicate more than 4/5 times.The method uses unused identifier bits to encode word signatures; signature selection controls filtering ability.

7 Faiss applications

Faiss is used across large-scale indexing, retrieval, dataset mining, and content moderation. Its applications combine compressed or partitioned indexes with distributed construction and search to handle very large vector collections.

  • Applications: Faiss applications include trillion-scale indexing, natural-language retrieval, large-dataset mining and curation, image deduplication, and harmful-content detection.These examples demonstrate applications with large scale or significant practical impact.
  • 7.1 Trillion-scale indexing: 1.5 trillion 144-dimensional vectors are indexed with compression limited to 54 bytes, using PCA to 72 dimensions and a 6-bit scalar quantizer.The example uses PCAR72,SQ6 because indexing accuracy is required.
  • 7.1 Trillion-scale indexing: Distributed construction shards vectors over ids, then inverted lists over machines, and finally memory-maps 100 indexes totaling 83 TiB on a central machine.The first two phases run as independent cluster jobs across hundreds of servers.
  • 7.1 Trillion-scale indexing: Roughly 1 s per query is achieved after distributing search across 20 intermediate servers to address the central machine’s network-bandwidth bottleneck.The central machine performs coarse quantization and loads inverted lists from distributed disk before the workload is spread across intermediate servers.
  • 7.2 Text retrieval: Faiss supports retrieval for fact checking, entity linking, slot filling, and open-domain question answering, where relevant content must be retrieved from large corpora.Language models also integrate textual retrieval to improve accuracy, factuality, or compute efficiency.
  • 7.4 Content Moderation: In content moderation, embedded labeled examples are searched with Faiss, often using range queries, and results feed additional machine classification or human verification.Accurate similarity search is required because mistakes have high impact and the system operates at billion-to-trillion scale.

8 Conclusion

Faiss has expanded from a vector-indexing toolkit to incorporate research advances across quantization, hardware support, and new indexing forms. The conclusion emphasizes continued extension of the library’s technical scope.

  • 8 Conclusion: Faiss continuously expanded its focus to include relevant vector-indexing techniques from research, including novel quantization techniques and better hardware support.The paper presents this expansion as an ongoing direction.
  • 8 Conclusion: Faiss also added new indexing forms, such as associative vector memories for transformer architectures.This extends the library beyond conventional vector-indexing techniques.

A Appendix

Faiss began in a research environment and grew organically alongside indexing research. Its appendix explains the principles, structure, optimization, database interfacing, and index-selection guidance that organize the implementation.

  • A Appendix: Faiss started in a research environment and consequently grew organically as indexing research progressed.The appendix presents this history as context for the library’s implementation.
  • A Appendix: The appendix summarizes Faiss’s guiding principles, dependencies, optimization approach, vector-database interfacing, and a flowchart for choosing an index.These topics address both internal coherence and practical embedding in external systems.

A.1 Code structure

Faiss uses an open, modular C++ core focused exclusively on vector search, with concrete data types and customization points that ease integration.

  • Faiss’s C++ core is designed to expose implementation details, embed easily in external libraries, and focus exclusively on vector search.
  • All class fields are public, and the core targets relatively old compilers while currently using C++17.
  • Vectors use portable 32-bit floats, while vector identifiers use 64-bit integers suited to database identifiers.
  • Faiss’s few dependencies and subclassable callback classes make C++ linking and index customization straightforward.

A.2 High-level interface

Faiss presents complex indexing pipelines through a unified, serializable Index interface and supports experimentation through comprehensive Python and C APIs.

  • The C++ core and GPU add-on minimize dependencies, requiring only a BLAS implementation and CUDA for GPU functionality.
  • Python wrappers cover Faiss classes, methods, and variables, while the Python layer includes benchmarking and dataset tooling; a pure C API supports language bindings.
  • An Index appears as one monolithic object even when it contains quantizers, refinement indexes, or sharded subindexes.
  • Indexes can be cloned and serialized or deserialized through generic single-function operations.
  • Factory strings instantiate multi-stage indexes by specifying preprocessing, coarse quantization, product quantization, and result refinement.

A.3 Optimization

Faiss prioritizes broad index coverage before optimization, then specializes implementations for workload, hardware, and execution architecture across CPU and GPU systems.

  • Faiss implements a non-optimal version of each index first, then optimizes runtime-critical indexes while using the original version to check correctness.
  • CPU optimization: CPU optimization combines SIMD support, specialized kernels, hardware-specific tuning, and data layouts adapted for parallel lookups.
  • GPU Faiss: GPU vector search favors parallel distance computation, table lookup, and pipelined scanning, while irregular graph traversal remains latency-bound.
  • GPU Faiss: GPU k-selection is a central challenge because heap operations can take an order of magnitude longer than the remaining arithmetic.
  • GPU Faiss: Faiss supports GPU brute-force and IVF indexes with CPU-GPU conversion and multi-GPU operation.
  • Parameterization: Advanced parameters expose trade-offs such as iteration counts and batch sizes, with defaults intended to work reasonably well in most cases.

A.4 Interfacing with external storage

Faiss separates vector indexing from storage and exposes composable APIs for inverted lists, scanning, quantization, and common index operations. Its index-selection guidance prioritizes memory constraints before accuracy and construction-time trade-offs.

  • Storage: Faiss’s default IVF storage uses simple vectors, while lower-level APIs let database developers control inverted-list storage.
  • Storage: Inverted lists may use in-memory arrays, memory-mapped storage, or key-value stores accessed through iterable interfaces.
  • Scanning: InvertedListScanner lets calling code control loops over fragmented or metadata-filtered lists while Faiss computes distances and updates results.
  • Index selection: The decision tree chooses CPU Euclidean k-nearest-neighbor indexes by database size and memory constraints before considering construction time versus accuracy.
  • Index composition: The index factory encodes combinations of pruning and compression methods, and Faiss groups resulting implementations into broad index families.
  • Index API: Faiss indexes expose training, vector addition, identifier assignment, nearest-neighbor search, range search, removal, reconstruction, and quantizer operations.
Loading 2401.08281v4…