vault

Inverted File Index

5 min read

Inverted File Index

Inverted File Index (IVF) is an Approximate Nearest Neighbour (ANN) data structure that partitions the vector space into Voronoi cells (one cell per coarse cluster) via k-means clustering, and indexes each database vector under the cell of its nearest cluster centroid. At query time, the query vector’s n_probe nearest cells are identified, and exact (or further-approximated) distance computation is performed only against the vectors in those cells. This coarse partitioning is a foundational ANN technique, dating to the information-retrieval inverted-index literature of the 1970s and adapted to dense-vector search by Jégou, Douze & Schmid (TPAMI 2011) and FAISS. IVF is rarely used alone — its accuracy is moderate — but it is the dominant first stage in composite ANN indexes, especially when combined with Product Quantization (the IVF-PQ index in FAISS) or with full-precision distance refinement (IVF-Flat). The combination of IVF (coarse partitioning) and PQ (vector compression) is one of the most-deployed ANN configurations in production at billion-vector scale.

1. The Coarse-Partitioning Idea

Exact nearest-neighbour search is O(n · d) per query in dataset size n and dimension d. Two complementary strategies reduce this:

Vector compression (Product Quantization) reduces the per-vector cost from d to a much smaller M.

Coarse partitioning (IVF) reduces the number of vectors searched from n to roughly n / K_IVF where K_IVF is the number of partitions.

Combining both gives the multiplicative speedup: total cost from O(n · d) to O((n / K_IVF) · M), which is a (d / M) · K_IVF improvement. With typical K_IVF = 1000 partitions and PQ compression d/M = 16, this is a 16,000× speedup.

IVF is the canonical implementation of coarse partitioning for dense-vector ANN.

2. The IVF Structure

Training (offline):

  1. Run k-means on all database vectors (or a representative sample) with K_IVF cluster centroids. Common K_IVF: square root of dataset size, e.g., K_IVF ≈ 1000 for n = 10⁶, K_IVF ≈ 31623 for n = 10⁹.
  2. The K_IVF cluster centroids define the Voronoi partitioning of ℝ^d — each point in space belongs to the cell of its nearest centroid.

Indexing (per database vector):

  1. For each database vector v, compute its nearest centroid (the cell it belongs to).
  2. Append v (or its compressed representation) to the inverted list for that cell.

The result is K_IVF inverted lists, each containing the database vectors assigned to that cell.

Query:

  1. Find the n_probe nearest centroids to the query vector. (n_probe is a tunable parameter; typically 1 to 100.)
  2. For each of those n_probe cells, scan the inverted list and compute distances to the query.
  3. Return the top-K nearest among the scanned vectors.

3. The n_probe Trade-off

n_probe controls the recall-speed trade-off:

  • n_probe = 1: query searches only the single nearest cell. Fast but low recall — true nearest neighbours in adjacent cells are missed.
  • n_probe = K_IVF: query searches every cell — exact search; no benefit over flat search.
  • n_probe ∈ [5, 50]: typical production range. Recall in the 90–99% range; substantial speedup over exact search.

The n_probe parameter can be tuned at query time without rebuilding the index, which makes it a convenient knob for per-query recall-vs-latency adjustments.

4. IVF-Flat vs IVF-PQ

The two main composite IVF variants in FAISS:

IVF-Flat: vectors are stored at full precision in the inverted lists. Distance computation within each cell is exact. Higher accuracy, more memory.

IVF-PQ: vectors are stored as PQ codes (see Product Quantization). Distance computation uses the asymmetric-distance lookup tables. Lower memory, slightly lower accuracy.

For small-to-medium datasets (up to ~10⁷ vectors), IVF-Flat is usually the right choice. For billion-scale datasets, IVF-PQ is often the only feasible option due to memory constraints.

A third common variant, IVFADC (IVF with Asymmetric Distance Computation), is essentially IVF-PQ; the names are sometimes used interchangeably.

5. Hyperparameters

HyperparameterTypical rangeEffect
K_IVF (number of cells)√n typicalMore cells = finer partition, faster queries with same n_probe, slower training.
n_probe (cells searched per query)1 to 100Larger improves recall; linear cost increase.
Vector storage (Flat / PQ / SQ)n/aChoice depends on memory budget.

6. Limitations and Alternatives

IVF’s main weakness is boundary effects: vectors near the boundary of multiple Voronoi cells may be missed if the query’s nearest cells do not include all of them. Increasing n_probe mitigates but does not eliminate this.

Graph-based ANN (HNSW) does not have this boundary problem because navigation can cross cell boundaries naturally. For high-recall requirements, HNSW often outperforms IVF at similar query budgets, especially at moderate dataset sizes (10⁵ to 10⁸).

For very large datasets (10⁹+) and tight memory budgets, IVF-PQ remains the dominant choice because the alternative graph indexes (HNSW) have prohibitive memory overhead at that scale.

7. When to Use IVF

IVF (alone or combined with PQ) is appropriate when:

  • The dataset is large enough (10⁶+) that exact search is too slow.
  • You need a tunable recall-speed trade-off.
  • You can afford the offline k-means training.
  • For large datasets (10⁹+) where memory constraints rule out HNSW.

8. Strengths

  • Conceptually simple — partition the space, search nearby partitions.
  • Tunable n_probe at query time without re-indexing.
  • Composes well with PQ for memory savings.
  • Mature implementation in FAISS.

9. Weaknesses

  • Boundary effects miss vectors near cell boundaries.
  • K-means training can be expensive for very large K_IVF.
  • Lower recall than HNSW at the same query budget for moderate dataset sizes.

10. See Also

Graph View

Backlinks