The Faiss library

In plain words

Finding the stored items closest to a query is easy when there are few of them: compare the query with every item. With millions or billions of vectors that becomes too slow and too large to hold in memory. Faiss is a toolbox of ways to make this search cheaper. Every option trades three things against each other: how fast a search runs, how much memory the index uses, and how often the answer is the true closest item.

Two tools do most of the work. The first squeezes each vector into a few bytes and estimates distances from those bytes. The second skips most of the data: vectors are grouped into clusters or linked in a graph, and only the nearby groups are searched. Faiss does not create the embeddings; it only indexes vectors that another model has produced. Its parts can be chained into one index, and the paper's advice is to pick settings by measuring the speed and accuracy curve on your own data rather than by guessing.

TL;DR

Faiss is an open-source library with a C++ core and a Python wrapper for approximate nearest-neighbour (ANN) search over embedding vectors §1. An index usually chains a vector codec, a non-exhaustive pruning step (inverted file or graph) and sometimes exact re-ranking §3.5 §4 §5. The paper's guidance: use graph indexes when memory is not the limit (typically below about 1M vectors), and compressed inverted files for larger sets §5.3. Headline results are author-reported: a 1.5-trillion-vector index at about 1 s per query §7.1, and Faiss faster than SCANN and roughly on par with Vamana on Deep10M §5.5.

Problem

• Exact search computes a distance from the query to every database vector and keeps the k smallest §3 eq. 2. Brute force gets slow as N grows and large dimensions defeat branch-and-bound methods §3.1.
• Storing raw float32 vectors can exceed memory at scale. Compression lowers memory but makes results approximate §4.
• Approximate search is judged against exact results. End-to-end quality also depends on whether the embedding distance matches the task, which the index cannot fix §3.2.
• Speed, memory and accuracy are the active constraints in the paper's experiments. Build time, I/O operations and extra lookup memory matter only in some deployments §3.2 §3.3.
• LSH and tree-based pruning are described as not scaling well above about 10 dimensions §5.
• The paper assumes an "embedding contract": the extractor and the index agree on the distance. The usual choices are Euclidean distance (default), cosine (metric learning) and maximum inner product (recommendation) §1 §3.

Method

Index model and search API

• A Faiss index holds database vectors, added with add (sequential ids) or add_with_ids (64-bit ids; the sign bit is reserved for invalid results) §6.1. Vectors are 32-bit floats and ids are 64-bit integers app. A.1.
• search(x, k) returns the k nearest neighbours of each query row, and range_search(x, ε) returns everything within radius ε app. A.7. They implement eq. 2 and eq. 3; approximate indexes return approximate results.
• index_factory builds an index from a string. The paper's example, PCA160,IVF20000_HNSW,PQ20x10,RFlat, applies a PCA to 160 dimensions, uses an IVF with 20000 lists whose coarse quantizer is HNSW, encodes residuals with a 20-sub-quantizer product quantizer of 10 bits each, and re-ranks exactly app. A.2.

n = \underset{i=1..N}{\mathrm{argmin}} \, \| q - x_i \| eq. 1

(n_1, \dots, n_k) = \underset{i=1..N}{\mathrm{argsort}} \, \| q - x_i \| eq. 2

R = \{ n : \| q - x_n \| \le \varepsilon \} eq. 3

Codecs (compression)

• A codec maps a vector to an integer code and back. Search then uses approximate distances between the query and the decoded codes §4 eq. 10.
• Asymmetric distance computation (ADC) compares the raw query with the decoded database vector. It is the default for most indexes because the query loses no accuracy §4 eq. 10. Symmetric distance computation (SDC) compresses the query too; it helps when queries are also stored compressed §4 eq. 11.
• Codec families §4.1:
  • k-means quantizer: the exact MSE-optimal codebook, impractical beyond about 3-byte codes (16M centroids) §4.1.
  • Scalar quantizers: LSH bits (one bit per component, fixed or trained threshold), uniform SQ8, SQ6, SQ4 with per-dimension or whole-vector ranges, and SQfp16 / SQbf16 §4.1.
  • Product quantizer (PQ): M sub-vectors, each with its own k-means codebook of K entries. The notation PQ6x10 means M = 6 and K = 2^10 §4.1.
  • Additive quantizers: residual quantizer (RQ) and local search quantizer (LSQ); the notation RQ6x10 means 6 codebooks of 2^10. Product-additive quantizers (PRQ) split the vector first, so PRQ2x6x10 means 12 codebooks of 2^10 in total §4.1.
  • Binary codes with Hamming distance, through the IndexBinary* classes §4.5.
• The paper's hierarchy, from weakest to most general: 1-bit scalar, scalar, PQ, product-additive, additive. Each step can reproduce any value of the one before it, at more training and storage cost §4.1.
• Vector preprocessing §4.2: a random rotation (spreads variance over the dimensions without changing distances), PCA to d′ dimensions, OPQ (rotation that decorrelates PQ sub-vectors), and ITQ (rotation before binarisation).

Residual quantizer encoding (RQ, the beam search form) §4.3:

c_m = \underset{j=1..K}{\mathrm{argmin}} \; \Big\| \sum_{i=1}^{m-1} T_i[c_i] + T_m[j] - x \Big\|^2 eq. 13

The greedy choice can get stuck, so the encoder keeps a beam of up to max_beam_size partial codes and keeps the best at the last stage §4.3.

Lookup-table distance for additive codes (inner product) §4.3:

\langle q, x' \rangle = \sum_{m=1}^{M} \mathrm{LUT}_m[c_m] eq. 14

where LUT_m holds the inner products of the query with each entry of codebook m, computed once per query §4.3. L2 cannot use this sum directly. Faiss uses eq. 15 and needs ‖x′‖² at search time. It is stored with the code, optionally quantised, or computed from the lookup tables (ST_norm_from_LUT), trading search time for code memory §4.3.

\| q - x' \|^2 = \| q \|^2 + \| x' \|^2 - 2 \langle q, x' \rangle eq. 15

Non-exhaustive search

• Inverted file (IVF) §5.1: a coarse quantizer with nlist centroids partitions the database. A query visits the nprobe nearest lists and scores only those. Lists store compressed codes contiguously.
• With exhaustive coarse search, fixed nprobe, uncompressed lists and equal list sizes, the number of distance computations is eq. 18, which is minimal at nlist = √(nprobe · N) §5.1.

N_{\mathrm{distances}} = \mathrm{nlist} + \mathrm{nprobe} \times N / \mathrm{nlist} eq. 18

• Residual encoding (IndexIVF.by_residual, default true) encodes database vectors relative to their centroid. The paper says this is more accurate because residuals are smaller, and it helps most for short codes §5.1 fig. 5.
• For inner-product search, Faiss offers spherical k-means, which renormalises centroids every iteration, and IP assignment, to reduce list imbalance §5.1 fig. 6.
• Big-batch search loads only the quantizer, then streams the index in chunks (contrib.big_batch_search) §5.1.
• Graph indexes §5.2: HNSW (hierarchical; supports adding vectors online) and NSG (built from a k-NN graph, optionally by NN-descent; the graph is frozen after the first batch). The search-time knob is the number of traversal steps (efSearch for HNSW, search_L for NSG). More than 64 edges per node did not help in the paper's test §5.2 fig. 7.
• Graphs suit indexes below about 1M vectors when memory is not limiting; beyond about 10M, build time becomes the limit; compression that must fit the data in memory leaves IVF as the only option §5.3 app. A.5 fig. 10.
• Refinement (IndexRefine): a fast index returns a shortlist, and an exact or slower distance re-ranks it §3.5. The paper suggests tracking 1-recall at the shortlist size rather than at 1 §3.5.

Benchmarking and search-time tuning

• Search-time parameters are treated as monotone: a higher value means slower and more accurate. Faiss keeps only the Pareto-optimal settings. Parameter tuples that a previous evaluation dominates are skipped, using bounds derived from monotonicity §3.4 eq. 5 eq. 6 eq. 7 eq. 8 eq. 9.

\pi' \ge \pi \Rightarrow S(\pi') \le S(\pi), \; A(\pi') \ge A(\pi) eq. 6

• In the paper's example, 5808 configurations reduced to 398 measured runs, of which 87 were Pareto-optimal. Random evaluation order makes pruning more effective §3.4 fig. 1.
• The benchmark framework bench_fw evaluates coarse quantizers and IVF components separately and benchmarks only the Pareto-optimal combinations §5.4.

Metric equivalences tab. 2

• Several metrics can be made equivalent by rewriting query and database vectors, so one index type serves them. The paper's table covers L2, inner product (IP) and cosine §3 tab. 2.
• The table uses positive scalars α and β, which the paper says are chosen so the square root stays non-negative. It does not give values.
• Cosine becomes IP or L2 by normalising both vectors. To search by L2 on an IP index, append −α/2 to the query and ‖y‖²/α to each database vector, which gives the same ranking as L2 tab. 2.
• Such rewrites make the vectors anisotropic, which hurts PQ and scalar quantizers §3.

Database operations and filtering

• remove_ids and update_vectors change indexes. Flat indexes accept only sequential ids; IndexIDMap and IndexIDMap2 add arbitrary ids §6.1.
• IVF can keep a DirectMap from id to list position, which supports lookup, removal and update at memory and add-time cost. It is off by default §6.1.
• HNSW does not support removal or mutation, and NSG cannot add vectors after its first batch §6.1 §5.2.
• Filtering with a predicate callback (IDSelector) is the basic option. The paper's bag-of-words example packs 39 bits of word signatures into the unused id bits, so most rejections are a bitwise test §6.2 eq. 19.
• The signature test is a pre-filter. A vector can only contain both query words if no query bit is missing from its signature §6.2.

\{w_1, w_2\} \subset W_i \Rightarrow \neg s_i \wedge s_q = 0 eq. 19

# Signature pre-filter for a two-word query  [§6.2] [eq. 19]
# Input:  query_signature (39-bit int), stored_signature (39-bit int)
# Output: False if the stored vector cannot contain both query words

def may_contain_both(query_signature, stored_signature):
    # Query bits that the stored signature lacks  [§6.2] [eq. 19]
    missing_bits = query_signature & ~stored_signature
    # Any missing bit rules the stored vector out  [§6.2]
    return missing_bits == 0

• Metadata-first search is chosen when the expected subset is small. The expected intersection is L_w1 · L_w2 / N, and the paper uses metadata-first when that is below an empirical 3 × 10⁻⁴ of N §6.2.

Search pipeline (IVF with compressed codes)

# IVF search over compressed codes  [§5.1] [§4] [eq. 14]
# Input:  query (d,), centroids (nlist, d), lists (codes and ids per list)
# Output: ids of the k nearest stored vectors

def ivf_search(query, centroids, lists, nprobe, k):
    # Pick the nprobe centroids nearest to the query  [§5.1]
    probed = nearest_indices(query, centroids, nprobe)
    # Precompute per-query lookup tables once  [§4.3] [eq. 14]
    tables = build_lookup_tables(query)
    best = empty_top_k(k)
    # Visit only the probed inverted lists  [§5.1]
    for list_id in probed:
        for code, vector_id in lists[list_id]:
            # Distance from the codes, without decoding  [§4] [eq. 10]
            distance = table_distance(tables, code)
            best.offer(distance, vector_id)
    return best.ids()

Note: the paper does not spell out how lookup tables are built when residual encoding is on. Read the code (see Paper vs code) before implementing that case.

Engineering (appendix)

• Feature-complete first: every index runs a non-optimised version, which checks the optimised one. Only some sizes are fully optimised, for example PQ with K = 2^8 or 2^4 and d/M in {2, 4, 8, 16, 20} app. A.3.
• SIMD on AVX, AVX2, AVX512 and NEON. The 4-bit PQ and additive quantizers ("FastScan") interleave codes so that LUT lookups run in parallel, inspired by SCANN app. A.3.
• GPU Faiss covers flat, IVF-flat, IVF-SQ and IVF-PQ indexes, with index_cpu_to_gpu and index_gpu_to_cpu to convert between CPU and GPU objects app. A.3.
• Queries should be sent in batches. A single query is not multi-threaded, and a batch is faster than many threads each calling search app. A.3.
• Storage can be replaced: InvertedLists can be memory-mapped (OnDiskInvertedLists) or backed by a key-value store, and an InvertedListScanner lets the caller control the scan loop app. A.4.
• Metric types app. A.6 tab. 3: inner product, L2 (squared), L1, L∞, Lp, Canberra, Bray–Curtis, Jensen–Shannon, Jaccard and NaN-aware Euclidean. Only inner product and L2 work for every index type.

Hyperparameters

Results

Author-reported. Setups differ between rows, and the paper gives no single score table. Speed numbers come from the paper's hardware, which it does not fully describe.

Applications named without numbers: text retrieval for knowledge-intensive NLP §7.2, dataset mining and deduplication (1.3B images) §7.3, and content moderation with range queries §7.4.

Paper vs code

Repository: https://github.com/facebookresearch/faiss, linked from the paper §1 (footnote). Commit 56c96d5efcfd3b498f70bd3be61e75da4455e491, MIT licence. The paper is v4 (2025-10-23) and the code is the commit above, so details may have changed since the paper was written.

• Name mismatch, behaviour matches. The paper says ST_norm_float32 §4.3. The code enum is ST_norm_float, which stores float32 norms with the vectors AdditiveQuantizer.h. Use the code name.
• Module not in this repository. The footnote for the bag-of-words filter points to the big-ann-benchmarks repository §6.2. No bow_id_selector definition exists in this faiss commit (checked under faiss/, contrib/ and benchs/), so that filter must come from the benchmark code.
• Spherical k-means is opt-in. The paper describes it as implemented §5.1. The code offers it as spherical, which defaults to false Clustering.h. The MIPS gains need it enabled.
• Residual encoding, DirectMap and metric names agree with the paper. by_residual defaults to true IndexIVF.h; the direct map defaults to NoMap DirectMap.h; METRIC_L2 is the squared distance, as the paper's metric table says app. A.6.
• Training subsampling is not in the paper. Clustering subsamples the training set to 256 points per centroid and warns below 39 Clustering.h Clustering.h. Training with few vectors changes the codebooks silently.
• Lookup tables with residual encoding. The paper does not describe them §4.3 §5.1. The implementation behind by_residual is not read in this card. Check faiss/IndexIVF.h#L248 and the IVF search code before implementing that case.

Pitfalls

• Not a single algorithm. The paper describes a library and a design philosophy. No training recipe or single method exists to copy. Choose components from the decision tree app. A.5 fig. 10 and the trade-off text §5.3, and then benchmark.
• Most numbers are in figures. Speed and accuracy values are only in fig. 2 to fig. 8. The text gives few exact values, and no table of results. Read the figures from the arXiv PDF before quoting a number.
• Unstated choices with consequences. The paper gives no defaults for nprobe, HNSW M/efConstruction/efSearch, NSG R, max_beam_size or encode_ils_iters. The code defaults are in the Hyperparameters table.
• nprobe rule is ambiguous. The paper derives nlist = √(nprobe · N) from eq. 18, then says the usual recommendation is "nprobe proportional to √N" §5.1. The formula implies that the nlist-to-√N ratio is what matters for a fixed nprobe, not nprobe. Follow the measured nlist ratio §5.1 and tune nprobe by benchmark.
• Distance rewriting is sensitive. Equivalent metrics need extra dimensions whose values depend on α and β tab. 2. The paper does not give those values, and the extra dimension is anisotropic, which hurts PQ and scalar quantizers §3. Use PCA or rotation before quantizing §4.2.
• Brute-force and tree methods. Branch-and-bound gives no speed-up in high dimensions §3.1. The paper says LSH and trees do not scale above about 10 dimensions §5.
• Batching matters for speed. A single query does not use multiple threads. Batch queries before calling search app. A.3.
• Metric type naming. METRIC_L2 is the squared distance. Taking the square root is needed to get Euclidean distances app. A.6 tab. 3.
• Updates can break fitted structures. If the vector distribution shifts because of additions, removals or updates, IVF and PQ lose efficiency. The paper points to explicit index updates as the remedy §6.1.
• Filter hit rate is undefined. The paper's table does not say whether "hit rate" counts rejected or accepted vectors. The text says the best p avoids running the full predicate more than 4/5 of the time, which fits a rate of rejected candidates §6.2. Confirm the definition before reusing the table.
• Filtering cost. Predicate callbacks run in the innermost loop. Indirect metadata lookups are slow, and the bit signature pre-filter reduces them but cannot filter complex metadata §6.2.
• Cost of compression and graphs. Additive quantizer encoding is slow. Option choice depends on code size: the paper finds that LSQ does not scale to longer codes, and GPU encoding for LSQ does not help systematically §4.3 §4.4. Graphs cost memory per vector (edges), and NSG cannot add vectors after the first batch §5.2.
• Search latency at scale is network-bound. At trillion scale the central machine's bandwidth was the limit, so the paper spreads the load over 20 servers §7.1. The 1 s figure needs that setup.

Lineage

• Builds on: product quantization and asymmetric distance computation (named for ADC and PQ in §4 §4.1); the residual and local-search additive quantizers §4.1; OPQ and ITQ rotations §4.2; HNSW and NSG graphs §5.2; spherical k-means §5.1. No cards exist for these in this wiki.
• Compared against: SCANN and Vamana (DiskANN), on ANN-benchmarks §5.5.
• Superseded by: none stated. The conclusion names new quantization methods, GPU graph search and associative memories for transformers as future work §8.